sys/vfs/hammer/hammer_ondisk.c

   1 /*
   2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * $DragonFly: src/sys/vfs/hammer/hammer_ondisk.c,v 1.1 2007/11/01 20:53:05 dillon Exp $
  35  */
  36 /*
  37  * Manage HAMMER's on-disk structures.  These routines are primarily
  38  * responsible for interfacing with the kernel's I/O subsystem and for
  39  * managing in-memory structures.
  40  */
  41
  42 #include "hammer.h"
  43 #include <sys/fcntl.h>
  44 #include <sys/nlookup.h>
  45 #include <sys/buf.h>
  46 #include <sys/buf2.h>
  47
  48 static void hammer_free_volume(struct hammer_volume *volume);
  49 static void initbuffer(hammer_alist_t live, hammer_fsbuf_head_t head,
  50                         u_int64_t type);
  51 static void alloc_new_buffer(struct hammer_cluster *cluster,
  52                         hammer_alist_t live, u_int64_t type, int32_t nelements,
  53                         int32_t start,
  54                         int *errorp, struct hammer_buffer **bufferp);
  55 #if 0
  56 static void readhammerbuf(struct hammer_volume *vol, void *data,
  57                         int64_t offset);
  58 static void writehammerbuf(struct hammer_volume *vol, const void *data,
  59                         int64_t offset);
  60 #endif
  61 static int64_t calculate_cluster_offset(struct hammer_volume *vol,
  62                         int32_t clu_no);
  63 static int64_t calculate_supercl_offset(struct hammer_volume *vol,
  64                         int32_t scl_no);
  65
  66
  67 struct hammer_alist_config Buf_alist_config;
  68 struct hammer_alist_config Vol_normal_alist_config;
  69 struct hammer_alist_config Vol_super_alist_config;
  70 struct hammer_alist_config Supercl_alist_config;
  71 struct hammer_alist_config Clu_master_alist_config;
  72 struct hammer_alist_config Clu_slave_alist_config;
  73
  74 /*
  75  * Red-Black tree support for various structures
  76  */
  77 static int
  78 hammer_ino_rb_compare(struct hammer_inode *ip1, struct hammer_inode *ip2)
  79 {
  80         if (ip1->obj_id < ip2->obj_id)
  81                 return(-1);
  82         if (ip1->obj_id > ip2->obj_id)
  83                 return(1);
  84         if (ip1->obj_asof < ip2->obj_asof)
  85                 return(-1);
  86         if (ip1->obj_asof > ip2->obj_asof)
  87                 return(1);
  88         return(0);
  89 }
  90
  91 static int
  92 hammer_inode_info_cmp(hammer_inode_info_t info, struct hammer_inode *ip)
  93 {
  94         if (info->obj_id < ip->obj_id)
  95                 return(-1);
  96         if (info->obj_id > ip->obj_id)
  97                 return(1);
  98         if (info->obj_asof < ip->obj_asof)
  99                 return(-1);
 100         if (info->obj_asof > ip->obj_asof)
 101                 return(1);
 102         return(0);
 103 }
 104
 105 static int
 106 hammer_vol_rb_compare(struct hammer_volume *vol1, struct hammer_volume *vol2)
 107 {
 108         if (vol1->vol_no < vol2->vol_no)
 109                 return(-1);
 110         if (vol1->vol_no > vol2->vol_no)
 111                 return(1);
 112         return(0);
 113 }
 114
 115 static int
 116 hammer_scl_rb_compare(struct hammer_supercl *cl1, struct hammer_supercl *cl2)
 117 {
 118         if (cl1->scl_no < cl2->scl_no)
 119                 return(-1);
 120         if (cl1->scl_no > cl2->scl_no)
 121                 return(1);
 122         return(0);
 123 }
 124
 125 static int
 126 hammer_clu_rb_compare(struct hammer_cluster *cl1, struct hammer_cluster *cl2)
 127 {
 128         if (cl1->clu_no < cl2->clu_no)
 129                 return(-1);
 130         if (cl1->clu_no > cl2->clu_no)
 131                 return(1);
 132         return(0);
 133 }
 134
 135 static int
 136 hammer_buf_rb_compare(struct hammer_buffer *buf1, struct hammer_buffer *buf2)
 137 {
 138         if (buf1->buf_no < buf2->buf_no)
 139                 return(-1);
 140         if (buf1->buf_no > buf2->buf_no)
 141                 return(1);
 142         return(0);
 143 }
 144
 145 /*
 146  * Note: The lookup function for hammer_ino_rb_tree winds up being named
 147  * hammer_ino_rb_tree_RB_LOOKUP_INFO(root, info).  The other lookup
 148  * functions are normal, e.g. hammer_clu_rb_tree_RB_LOOKUP(root, clu_no).
 149  */
 150 RB_GENERATE(hammer_ino_rb_tree, hammer_inode, rb_node, hammer_ino_rb_compare);
 151 RB_GENERATE_XLOOKUP(hammer_ino_rb_tree, INFO, hammer_inode, rb_node,
 152                 hammer_inode_info_cmp, hammer_inode_info_t);
 153 RB_GENERATE2(hammer_vol_rb_tree, hammer_volume, rb_node,
 154              hammer_vol_rb_compare, int32_t, vol_no);
 155 RB_GENERATE2(hammer_scl_rb_tree, hammer_supercl, rb_node,
 156              hammer_scl_rb_compare, int32_t, scl_no);
 157 RB_GENERATE2(hammer_clu_rb_tree, hammer_cluster, rb_node,
 158              hammer_clu_rb_compare, int32_t, clu_no);
 159 RB_GENERATE2(hammer_buf_rb_tree, hammer_buffer, rb_node,
 160              hammer_buf_rb_compare, int32_t, buf_no);
 161
 162 /*
 163  * Load a HAMMER volume by name.  Returns 0 on success or a positive error
 164  * code on failure.  Volumes must be loaded at mount time, get_volume() will
 165  * not load a new volume.
 166  *
 167  * Calls made to hammer_load_volume() or single-threaded
 168  */
 169 int
 170 hammer_load_volume(struct hammer_mount *hmp, const char *volname)
 171 {
 172         struct mount *mp;
 173         struct hammer_volume *volume;
 174         struct hammer_volume_ondisk *ondisk;
 175         struct nlookupdata nd;
 176         struct buf *bp = NULL;
 177         int error;
 178         int ronly;
 179
 180         mp = hmp->mp;
 181         ronly = ((mp->mnt_flag & MNT_RDONLY) ? 1 : 0);
 182
 183         /*
 184          * Allocate a volume structure
 185          */
 186         volume = kmalloc(sizeof(*volume), M_HAMMER, M_WAITOK|M_ZERO);
 187         volume->vol_name = kstrdup(volname, M_HAMMER);
 188         volume->hmp = hmp;
 189
 190         /*
 191          * Get the device vnode
 192          */
 193         error = nlookup_init(&nd, volume->vol_name, UIO_SYSSPACE, NLC_FOLLOW);
 194         if (error == 0)
 195                 error = nlookup(&nd);
 196         if (error == 0)
 197                 error = cache_vref(&nd.nl_nch, nd.nl_cred, &volume->devvp);
 198         nlookup_done(&nd);
 199         if (error == 0) {
 200                 vn_isdisk(volume->devvp, &error);
 201         }
 202         if (error == 0) {
 203                 vn_lock(volume->devvp, LK_EXCLUSIVE | LK_RETRY);
 204                 error = VOP_OPEN(volume->devvp, (ronly ? FREAD : FREAD|FWRITE),
 205                                  FSCRED, NULL);
 206                 vn_unlock(volume->devvp);
 207         }
 208         if (error) {
 209                 hammer_free_volume(volume);
 210                 return(error);
 211         }
 212
 213         /*
 214          * Extract the volume number from the volume header and do various
 215          * sanity checks.
 216          */
 217         error = bread(volume->devvp, 0LL, HAMMER_BUFSIZE, &bp);
 218         if (error)
 219                 goto late_failure;
 220         ondisk = (void *)bp->b_data;
 221         if (ondisk->head.buf_type != HAMMER_FSBUF_VOLUME) {
 222                 kprintf("hammer_mount: volume %s has an invalid header\n",
 223                         volume->vol_name);
 224                 error = EFTYPE;
 225                 goto late_failure;
 226         }
 227         volume->vol_no = ondisk->vol_no;
 228         volume->cluster_base = ondisk->vol_beg;
 229         volume->vol_clsize = ondisk->vol_clsize;
 230         volume->vol_flags = ondisk->vol_flags;
 231         RB_INIT(&volume->rb_clus_root);
 232         RB_INIT(&volume->rb_scls_root);
 233
 234         if (RB_EMPTY(&hmp->rb_vols_root)) {
 235                 hmp->fsid = ondisk->vol_fsid;
 236         } else if (bcmp(&hmp->fsid, &ondisk->vol_fsid, sizeof(uuid_t))) {
 237                 kprintf("hammer_mount: volume %s's fsid does not match "
 238                         "other volumes\n", volume->vol_name);
 239                 error = EFTYPE;
 240                 goto late_failure;
 241         }
 242
 243         /*
 244          * Insert the volume structure into the red-black tree.
 245          */
 246         if (RB_INSERT(hammer_vol_rb_tree, &hmp->rb_vols_root, volume)) {
 247                 kprintf("hammer_mount: volume %s has a duplicate vol_no %d\n",
 248                         volume->vol_name, volume->vol_no);
 249                 error = EEXIST;
 250         }
 251
 252         /*
 253          * Set the root volume and load the root cluster.
 254          */
 255         if (error == 0 && ondisk->vol_rootvol == ondisk->vol_no) {
 256                 hmp->rootvol = volume;
 257                 hmp->rootcl = hammer_get_cluster(volume,
 258                                                  ondisk->vol0_root_clu_no,
 259                                                  &error, 0);
 260         }
 261 late_failure:
 262         if (bp)
 263                 brelse(bp);
 264         if (error) {
 265                 /*vinvalbuf(volume->devvp, V_SAVE, 0, 0);*/
 266                 VOP_CLOSE(volume->devvp, ronly ? FREAD : FREAD|FWRITE);
 267                 hammer_free_volume(volume);
 268         }
 269         return (error);
 270 }
 271
 272 /*
 273  * Unload and free a HAMMER volume.  Must return >= 0 to continue scan
 274  * so returns -1 on failure.
 275  */
 276 int
 277 hammer_unload_volume(struct hammer_volume *volume, void *data __unused)
 278 {
 279         struct hammer_mount *hmp = volume->hmp;
 280
 281         /*
 282          * Sync clusters, sync volume
 283          */
 284         /* flush_volume */
 285
 286         /*
 287          * Destroy the structure
 288          */
 289         RB_REMOVE(hammer_vol_rb_tree, &hmp->rb_vols_root, volume);
 290         hammer_free_volume(volume);
 291         return(0);
 292 }
 293
 294 static
 295 void
 296 hammer_free_volume(struct hammer_volume *volume)
 297 {
 298         if (volume->vol_name) {
 299                 kfree(volume->vol_name, M_HAMMER);
 300                 volume->vol_name = NULL;
 301         }
 302         if (volume->devvp) {
 303                 vrele(volume->devvp);
 304                 volume->devvp = NULL;
 305         }
 306         kfree(volume, M_HAMMER);
 307 }
 308
 309 /*
 310  * Get a HAMMER volume.  The volume must already exist.
 311  */
 312 struct hammer_volume *
 313 hammer_get_volume(struct hammer_mount *hmp, int32_t vol_no, int *errorp)
 314 {
 315         struct hammer_volume *volume;
 316         struct hammer_volume_ondisk *ondisk;
 317
 318         /*
 319          * Locate the volume structure
 320          */
 321         volume = RB_LOOKUP(hammer_vol_rb_tree, &hmp->rb_vols_root, vol_no);
 322         if (volume == NULL) {
 323                 *errorp = ENOENT;
 324                 return(NULL);
 325         }
 326
 327         /*
 328          * Load the ondisk buffer if necessary
 329          */
 330         hammer_lock(&volume->lock);
 331         if (volume->ondisk == NULL) {
 332                 *errorp = bread(volume->devvp, 0LL, HAMMER_BUFSIZE,
 333                                 &volume->bp);
 334                 if (*errorp) {
 335                         hammer_unlock(&volume->lock);
 336                         return(NULL);
 337                 }
 338                 volume->ondisk = ondisk = (void *)volume->bp->b_data;
 339
 340                 /*
 341                  * Configure the volume's A-lists.  These are used to
 342                  * allocate clusters.
 343                  */
 344                 if (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL) {
 345                         volume->alist.config = &Vol_super_alist_config;
 346                         volume->alist.meta = ondisk->vol_almeta.super;
 347                         volume->alist.info = volume;
 348                 } else {
 349                         volume->alist.config = &Vol_normal_alist_config;
 350                         volume->alist.meta = ondisk->vol_almeta.normal;
 351                         volume->alist.info = NULL;
 352                 }
 353                 hammer_alist_init(&volume->alist);
 354         }
 355         *errorp = 0;
 356         return(volume);
 357 }
 358
 359 void
 360 hammer_put_volume(struct hammer_volume *volume)
 361 {
 362         if (hammer_islastref(&volume->lock)) {
 363                 if (volume->bp) {
 364                         if (volume->modified) {
 365                                 bdwrite(volume->bp);
 366                         } else {
 367                                 brelse(volume->bp);
 368                         }
 369                         volume->bp = NULL;
 370                         volume->ondisk = NULL;
 371                 }
 372                 volume->modified = 0;
 373         }
 374         hammer_unlock(&volume->lock);
 375 }
 376
 377 struct hammer_supercl *
 378 hammer_get_supercl(struct hammer_volume *volume, int32_t scl_no,
 379                    int *errorp, int isnew)
 380 {
 381         struct hammer_supercl_ondisk *ondisk;
 382         struct hammer_supercl *supercl;
 383
 384         /*
 385          * Locate and lock the super-cluster structure, creating one
 386          * if necessary.
 387          */
 388 again:
 389         supercl = RB_LOOKUP(hammer_scl_rb_tree, &volume->rb_scls_root, scl_no);
 390         if (supercl == NULL) {
 391                 supercl = kmalloc(sizeof(*supercl), M_HAMMER, M_WAITOK|M_ZERO);
 392                 supercl->scl_no = scl_no;
 393                 supercl->volume = volume;
 394                 supercl->scl_offset = calculate_supercl_offset(volume, scl_no);
 395                 hammer_lock(&supercl->lock);
 396
 397                 /*
 398                  * Insert the cluster into the RB tree and handle late
 399                  * collisions.
 400                  */
 401                 if (RB_INSERT(hammer_scl_rb_tree, &volume->rb_scls_root, supercl)) {
 402                         hammer_unlock(&supercl->lock);
 403                         kfree(supercl, M_HAMMER);
 404                         goto again;
 405                 }
 406         } else {
 407                 hammer_lock(&supercl->lock);
 408         }
 409
 410         /*
 411          * Load the cluster's on-disk info
 412          */
 413         *errorp = 0;
 414         if (supercl->ondisk == NULL) {
 415                 if (isnew) {
 416                         supercl->bp = getblk(volume->devvp, supercl->scl_offset,
 417                                              HAMMER_BUFSIZE, 0, 0);
 418                         vfs_bio_clrbuf(supercl->bp);
 419                         supercl->modified = 1;
 420                 } else {
 421                         *errorp = bread(volume->devvp, supercl->scl_offset,
 422                                         HAMMER_BUFSIZE, &supercl->bp);
 423                 }
 424                 if (*errorp) {
 425                         hammer_unlock(&supercl->lock);
 426                         return(NULL);
 427                 }
 428                 supercl->ondisk = ondisk = (void *)supercl->bp->b_data;
 429
 430                 supercl->alist.config = &Supercl_alist_config;
 431                 supercl->alist.meta = ondisk->scl_meta;
 432                 supercl->alist.info = NULL;
 433
 434                 /*
 435                  * If this is a new super-cluster we have to initialize
 436                  * various ondisk structural elements.  The caller is
 437                  * responsible for the remainder.
 438                  */
 439                 if (isnew) {
 440                         struct hammer_alist_live dummy;
 441
 442                         dummy.config = &Buf_alist_config;
 443                         dummy.meta = ondisk->head.buf_almeta;
 444                         dummy.info = NULL;
 445                         initbuffer(&dummy, &ondisk->head, HAMMER_FSBUF_SUPERCL);
 446                         hammer_alist_init(&supercl->alist);
 447                 }
 448         } else if (isnew) {
 449                 vfs_bio_clrbuf(supercl->bp);
 450                 supercl->modified = 1;
 451         }
 452         return (supercl);
 453 }
 454
 455 void
 456 hammer_put_supercl(struct hammer_supercl *supercl)
 457 {
 458         if (hammer_islastref(&supercl->lock)) {
 459                 if (supercl->bp) {
 460                         if (supercl->modified) {
 461                                 bdwrite(supercl->bp);
 462                         } else {
 463                                 brelse(supercl->bp);
 464                         }
 465                         supercl->bp = NULL;
 466                         supercl->ondisk = NULL;
 467                 }
 468                 supercl->modified = 0;
 469         }
 470         hammer_unlock(&supercl->lock);
 471 }
 472
 473 struct hammer_cluster *
 474 hammer_get_cluster(struct hammer_volume *volume, int32_t clu_no,
 475                    int *errorp, int isnew)
 476 {
 477         struct hammer_cluster_ondisk *ondisk;
 478         struct hammer_cluster *cluster;
 479
 480         /*
 481          * Locate and lock the cluster structure, creating one if necessary.
 482          */
 483 again:
 484         cluster = RB_LOOKUP(hammer_clu_rb_tree, &volume->rb_clus_root, clu_no);
 485         if (cluster == NULL) {
 486                 cluster = kmalloc(sizeof(*cluster), M_HAMMER, M_WAITOK|M_ZERO);
 487                 cluster->clu_no = clu_no;
 488                 cluster->volume = volume;
 489                 cluster->clu_offset = calculate_cluster_offset(volume, clu_no);
 490                 RB_INIT(&cluster->rb_bufs_root);
 491                 hammer_lock(&cluster->lock);
 492
 493                 /*
 494                  * Insert the cluster into the RB tree and handle late
 495                  * collisions.
 496                  */
 497                 if (RB_INSERT(hammer_clu_rb_tree, &volume->rb_clus_root, cluster)) {
 498                         hammer_unlock(&cluster->lock);
 499                         kfree(cluster, M_HAMMER);
 500                         goto again;
 501                 }
 502         } else {
 503                 hammer_lock(&cluster->lock);
 504         }
 505
 506         /*
 507          * Load the cluster's on-disk info
 508          */
 509         *errorp = 0;
 510         if (cluster->ondisk == NULL) {
 511                 if (isnew) {
 512                         cluster->bp = getblk(volume->devvp, cluster->clu_offset,
 513                                              HAMMER_BUFSIZE, 0, 0);
 514                         vfs_bio_clrbuf(cluster->bp);
 515                         cluster->modified = 1;
 516                 } else {
 517                         *errorp = bread(volume->devvp, cluster->clu_offset,
 518                                         HAMMER_BUFSIZE, &cluster->bp);
 519                 }
 520                 if (*errorp) {
 521                         hammer_unlock(&cluster->lock);
 522                         return(NULL);
 523                 }
 524                 cluster->ondisk = ondisk = (void *)cluster->bp->b_data;
 525
 526                 cluster->alist_master.config = &Clu_master_alist_config;
 527                 cluster->alist_master.meta = ondisk->clu_master_meta;
 528                 cluster->alist_btree.config = &Clu_slave_alist_config;
 529                 cluster->alist_btree.meta = ondisk->clu_btree_meta;
 530                 cluster->alist_btree.info = cluster;
 531                 cluster->alist_record.config = &Clu_slave_alist_config;
 532                 cluster->alist_record.meta = ondisk->clu_record_meta;
 533                 cluster->alist_record.info = cluster;
 534                 cluster->alist_mdata.config = &Clu_slave_alist_config;
 535                 cluster->alist_mdata.meta = ondisk->clu_mdata_meta;
 536                 cluster->alist_mdata.info = cluster;
 537
 538                 /*
 539                  * If this is a new cluster we have to initialize
 540                  * various ondisk structural elements.  The caller is
 541                  * responsible for the remainder.
 542                  */
 543                 if (isnew) {
 544                         struct hammer_alist_live dummy;
 545
 546                         dummy.config = &Buf_alist_config;
 547                         dummy.meta = ondisk->head.buf_almeta;
 548                         dummy.info = NULL;
 549                         initbuffer(&dummy, &ondisk->head, HAMMER_FSBUF_CLUSTER);
 550
 551                         hammer_alist_init(&cluster->alist_master);
 552                         hammer_alist_init(&cluster->alist_btree);
 553                         hammer_alist_init(&cluster->alist_record);
 554                         hammer_alist_init(&cluster->alist_mdata);
 555                 }
 556         } else if (isnew) {
 557                 vfs_bio_clrbuf(cluster->bp);
 558                 cluster->modified = 1;
 559         }
 560         return(cluster);
 561 }
 562
 563 void
 564 hammer_put_cluster(struct hammer_cluster *cluster)
 565 {
 566         if (hammer_islastref(&cluster->lock)) {
 567                 if (cluster->bp) {
 568                         if (cluster->modified) {
 569                                 bdwrite(cluster->bp);
 570                         } else {
 571                                 brelse(cluster->bp);
 572                         }
 573                         cluster->bp = NULL;
 574                         cluster->ondisk = NULL;
 575                 }
 576                 cluster->modified = 0;
 577         }
 578         hammer_unlock(&cluster->lock);
 579 }
 580
 581 /*
 582  * Get a buffer from a cluster.  Note that buffer #0 is the cluster header
 583  * itself and may not be retrieved with this function.
 584  *
 585  * If buf_type is 0 the buffer already exists in-memory or on-disk.
 586  * Otherwise a new buffer is initialized with the specified buffer type.
 587  */
 588 struct hammer_buffer *
 589 hammer_get_buffer(struct hammer_cluster *cluster, int32_t buf_no,
 590                   int64_t buf_type, int *errorp)
 591 {
 592         hammer_fsbuf_ondisk_t ondisk;
 593         struct hammer_buffer *buffer;
 594
 595         /*
 596          * Find the buffer.  Note that buffer 0 corresponds to the cluster
 597          * header and should never be requested.
 598          */
 599         KKASSERT(buf_no != 0);
 600
 601         /*
 602          * Locate and lock the buffer structure, creating one if necessary.
 603          */
 604 again:
 605         buffer = RB_LOOKUP(hammer_buf_rb_tree, &cluster->rb_bufs_root, buf_no);
 606         if (buffer == NULL) {
 607                 buffer = kmalloc(sizeof(*cluster), M_HAMMER, M_WAITOK|M_ZERO);
 608                 buffer->buf_no = buf_no;
 609                 buffer->cluster = cluster;
 610                 buffer->volume = cluster->volume;
 611                 buffer->buf_offset = cluster->clu_offset +
 612                                      (buf_no * HAMMER_BUFSIZE);
 613                 hammer_lock(&cluster->lock);
 614
 615                 /*
 616                  * Insert the cluster into the RB tree and handle late
 617                  * collisions.
 618                  */
 619                 if (RB_INSERT(hammer_buf_rb_tree, &cluster->rb_bufs_root, buffer)) {
 620                         hammer_unlock(&buffer->lock);
 621                         kfree(buffer, M_HAMMER);
 622                         goto again;
 623                 }
 624         } else {
 625                 hammer_lock(&buffer->lock);
 626         }
 627
 628         *errorp = 0;
 629         if (buffer->ondisk == NULL) {
 630                 if (buf_type) {
 631                         buffer->bp = getblk(buffer->volume->devvp,
 632                                             buffer->buf_offset,
 633                                             HAMMER_BUFSIZE, 0, 0);
 634                         vfs_bio_clrbuf(buffer->bp);
 635                         buffer->modified = 1;
 636                 } else {
 637                         *errorp = bread(buffer->volume->devvp,
 638                                         buffer->buf_offset,
 639                                         HAMMER_BUFSIZE, &buffer->bp);
 640                 }
 641                 if (*errorp) {
 642                         hammer_unlock(&buffer->lock);
 643                         return(NULL);
 644                 }
 645                 buffer->ondisk = ondisk = (void *)buffer->bp->b_data;
 646                 buffer->alist.config = &Buf_alist_config;
 647                 buffer->alist.meta = ondisk->head.buf_almeta;
 648
 649                 if (buf_type) {
 650                         initbuffer(&buffer->alist, &ondisk->head, buf_type);
 651                 }
 652         } else if (buf_type) {
 653                 vfs_bio_clrbuf(buffer->bp);
 654                 buffer->modified = 1;
 655         }
 656         return (buffer);
 657 }
 658
 659 void
 660 hammer_put_buffer(struct hammer_buffer *buffer)
 661 {
 662         if (hammer_islastref(&buffer->lock)) {
 663                 if (buffer->bp) {
 664                         if (buffer->modified) {
 665                                 bdwrite(buffer->bp);
 666                         } else {
 667                                 brelse(buffer->bp);
 668                         }
 669                         buffer->bp = NULL;
 670                         buffer->ondisk = NULL;
 671                 }
 672                 buffer->modified = 0;
 673         }
 674         hammer_unlock(&buffer->lock);
 675 }
 676
 677 void
 678 hammer_dup_buffer(struct hammer_buffer **bufferp, struct hammer_buffer *buffer)
 679 {
 680         if (buffer != *bufferp) {
 681                 if (buffer)
 682                         hammer_lock(&buffer->lock);
 683                 if (*bufferp)
 684                         hammer_put_buffer(*bufferp);
 685                 *bufferp = buffer;
 686         }
 687 }
 688
 689 void
 690 hammer_dup_cluster(struct hammer_cluster **clusterp,
 691                    struct hammer_cluster *cluster)
 692 {
 693         if (cluster != *clusterp) {
 694                 if (cluster)
 695                         hammer_lock(&cluster->lock);
 696                 if (*clusterp)
 697                         hammer_put_cluster(*clusterp);
 698                 *clusterp = cluster;
 699         }
 700 }
 701
 702 /*
 703  * Allocate HAMMER elements - btree nodes, data storage, and record elements
 704  *
 705  * The passed *bufferp should be initialized to NULL.  On successive calls
 706  * *bufferp caches the most recent buffer used until put away by the caller.
 707  * Note that previously returned pointers using the cached buffer become
 708  * invalid on successive calls which reuse *bufferp.
 709  *
 710  * All allocations first attempt to use the block found at the specified
 711  * iterator.  If that fails the first available block is used.  If that
 712  * fails a new buffer is allocated and associated with the buffer type
 713  * A-list and the element is allocated out of the new buffer.
 714  */
 715 void *
 716 hammer_alloc_btree(struct hammer_cluster *cluster,
 717                     int *errorp, struct hammer_buffer **bufferp)
 718 {
 719         struct hammer_buffer *buffer;
 720         hammer_alist_t live;
 721         int32_t elm_no;
 722         int32_t buf_no;
 723         void *item;
 724
 725         /*
 726          * Allocate a B-Tree element
 727          */
 728         live = &cluster->alist_btree;
 729         elm_no = hammer_alist_alloc_fwd(live, 1, cluster->ondisk->idx_index);
 730         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 731                 elm_no = hammer_alist_alloc_fwd(live, 1, 0);
 732         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 733                 alloc_new_buffer(cluster, live,
 734                                  HAMMER_FSBUF_BTREE, HAMMER_BTREE_NODES,
 735                                  cluster->ondisk->idx_index, errorp, bufferp);
 736                 elm_no = hammer_alist_alloc(live, 1);
 737                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 738         }
 739         cluster->ondisk->idx_index = elm_no;
 740
 741         /*
 742          * Load and return the B-Tree element
 743          */
 744         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 745         buffer = *bufferp;
 746         if (buffer == NULL || buffer->cluster != cluster ||
 747             buffer->buf_no != buf_no) {
 748                 if (buffer)
 749                         hammer_put_buffer(buffer);
 750                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 751                 *bufferp = buffer;
 752         }
 753         KKASSERT(buffer->ondisk->head.buf_type == HAMMER_FSBUF_BTREE);
 754         item = &buffer->ondisk->btree.nodes[elm_no & HAMMER_FSBUF_BLKMASK];
 755         bzero(item, sizeof(union hammer_btree_node));
 756         return(item);
 757 }
 758
 759 void *
 760 hammer_alloc_data(struct hammer_cluster *cluster, int32_t bytes,
 761                    int *errorp, struct hammer_buffer **bufferp)
 762 {
 763         struct hammer_buffer *buffer;
 764         hammer_alist_t live;
 765         int32_t elm_no;
 766         int32_t buf_no;
 767         int32_t nblks;
 768         void *item;
 769
 770         /*
 771          * Allocate a data element
 772          */
 773         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 774         live = &cluster->alist_mdata;
 775         elm_no = hammer_alist_alloc_fwd(live, nblks, cluster->ondisk->idx_data);
 776         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 777                 elm_no = hammer_alist_alloc_fwd(live, 1, 0);
 778         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 779                 alloc_new_buffer(cluster, live,
 780                                  HAMMER_FSBUF_DATA, HAMMER_DATA_NODES,
 781                                  cluster->ondisk->idx_data, errorp, bufferp);
 782                 elm_no = hammer_alist_alloc(live, nblks);
 783                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 784         }
 785         cluster->ondisk->idx_index = elm_no;
 786
 787         /*
 788          * Load and return the B-Tree element
 789          */
 790         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 791         buffer = *bufferp;
 792         if (buffer == NULL || buffer->cluster != cluster ||
 793             buffer->buf_no != buf_no) {
 794                 if (buffer)
 795                         hammer_put_buffer(buffer);
 796                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 797                 *bufferp = buffer;
 798         }
 799         KKASSERT(buffer->ondisk->head.buf_type == HAMMER_FSBUF_BTREE);
 800         item = &buffer->ondisk->data.data[elm_no & HAMMER_FSBUF_BLKMASK];
 801         bzero(item, nblks * HAMMER_DATA_BLKSIZE);
 802         return(item);
 803 }
 804
 805 void *
 806 hammer_alloc_record(struct hammer_cluster *cluster,
 807                      int *errorp, struct hammer_buffer **bufferp)
 808 {
 809         struct hammer_buffer *buffer;
 810         hammer_alist_t live;
 811         int32_t elm_no;
 812         int32_t buf_no;
 813         void *item;
 814
 815         /*
 816          * Allocate a record element
 817          */
 818         live = &cluster->alist_record;
 819         elm_no = hammer_alist_alloc_rev(live, 1, cluster->ondisk->idx_record);
 820         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 821                 elm_no = hammer_alist_alloc_rev(live, 1,HAMMER_ALIST_BLOCK_MAX);
 822         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 823                 alloc_new_buffer(cluster, live,
 824                                  HAMMER_FSBUF_RECORDS, HAMMER_RECORD_NODES,
 825                                  cluster->ondisk->idx_record, errorp, bufferp);
 826                 elm_no = hammer_alist_alloc(live, 1);
 827                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 828         }
 829         cluster->ondisk->idx_record = elm_no;
 830
 831         /*
 832          * Load and return the B-Tree element
 833          */
 834         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 835         buffer = *bufferp;
 836         if (buffer == NULL || buffer->cluster != cluster ||
 837             buffer->buf_no != buf_no) {
 838                 if (buffer)
 839                         hammer_put_buffer(buffer);
 840                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 841                 *bufferp = buffer;
 842         }
 843         KKASSERT(buffer->ondisk->head.buf_type != 0);
 844         item = &buffer->ondisk->record.recs[elm_no & HAMMER_FSBUF_BLKMASK];
 845         bzero(item, sizeof(union hammer_record_ondisk));
 846         return(item);
 847 }
 848
 849 /*
 850  * Free HAMMER elements based on either a hammer_buffer and element pointer
 851  * or a cluster-relative byte offset.
 852  */
 853 void
 854 hammer_free_btree_ptr(struct hammer_buffer *buffer, hammer_btree_node_t node)
 855 {
 856         int32_t elm_no;
 857         hammer_alist_t live;
 858
 859         elm_no = node - buffer->ondisk->btree.nodes;
 860         KKASSERT(elm_no >= 0 && elm_no < HAMMER_BTREE_NODES);
 861         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 862         live = &buffer->cluster->alist_btree;
 863         hammer_alist_free(live, elm_no, 1);
 864 }
 865
 866 void
 867 hammer_free_data_ptr(struct hammer_buffer *buffer, void *data, int bytes)
 868 {
 869         int32_t elm_no;
 870         int32_t nblks;
 871         hammer_alist_t live;
 872
 873         elm_no = ((char *)data - (char *)buffer->ondisk->data.data) /
 874                  HAMMER_DATA_BLKSIZE;
 875         KKASSERT(elm_no >= 0 && elm_no < HAMMER_DATA_NODES);
 876         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 877         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 878         live = &buffer->cluster->alist_mdata;
 879         hammer_alist_free(live, elm_no, nblks);
 880 }
 881
 882 void
 883 hammer_free_record_ptr(struct hammer_buffer *buffer,
 884                        union hammer_record_ondisk *rec)
 885 {
 886         int32_t elm_no;
 887         hammer_alist_t live;
 888
 889         elm_no = rec - &buffer->ondisk->record.recs[0];
 890         KKASSERT(elm_no >= 0 && elm_no < HAMMER_BTREE_NODES);
 891         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 892         live = &buffer->cluster->alist_record;
 893         hammer_alist_free(live, elm_no, 1);
 894 }
 895
 896 void
 897 hammer_free_btree(struct hammer_cluster *cluster, int32_t bclu_offset)
 898 {
 899         const int32_t blksize = sizeof(union hammer_btree_node);
 900         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 901         hammer_alist_t live;
 902         int32_t elm_no;
 903
 904         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 905         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, btree.nodes[0]);
 906         live = &cluster->alist_btree;
 907         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 908         elm_no += fsbuf_offset / blksize;
 909         hammer_alist_free(live, elm_no, 1);
 910 }
 911
 912 void
 913 hammer_free_data(struct hammer_cluster *cluster, int32_t bclu_offset,
 914                  int32_t bytes)
 915 {
 916         const int32_t blksize = HAMMER_DATA_BLKSIZE;
 917         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 918         hammer_alist_t live;
 919         int32_t elm_no;
 920         int32_t nblks;
 921
 922         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 923         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, data.data[0][0]);
 924         live = &cluster->alist_mdata;
 925         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 926         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 927         elm_no += fsbuf_offset / blksize;
 928         hammer_alist_free(live, elm_no, nblks);
 929 }
 930
 931 void
 932 hammer_free_record(struct hammer_cluster *cluster, int32_t bclu_offset)
 933 {
 934         const int32_t blksize = sizeof(union hammer_record_ondisk);
 935         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 936         hammer_alist_t live;
 937         int32_t elm_no;
 938
 939         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 940         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, record.recs[0]);
 941         live = &cluster->alist_record;
 942         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 943         elm_no += fsbuf_offset / blksize;
 944         hammer_alist_free(live, elm_no, 1);
 945 }
 946
 947
 948 /*
 949  * Allocate a new filesystem buffer and assign it to the specified
 950  * filesystem buffer type.  The new buffer will be added to the
 951  * type-specific A-list and initialized.
 952  */
 953 static void
 954 alloc_new_buffer(struct hammer_cluster *cluster, hammer_alist_t live,
 955                  u_int64_t type, int32_t nelements,
 956                  int start, int *errorp, struct hammer_buffer **bufferp)
 957 {
 958         struct hammer_buffer *buffer;
 959         int32_t buf_no;
 960
 961         start = start / HAMMER_FSBUF_MAXBLKS;   /* convert to buf_no */
 962
 963         if (type == HAMMER_FSBUF_RECORDS) {
 964                 buf_no = hammer_alist_alloc_rev(&cluster->alist_master,
 965                                                 1, start);
 966                 if (buf_no == HAMMER_ALIST_BLOCK_NONE) {
 967                         buf_no = hammer_alist_alloc_rev(&cluster->alist_master,
 968                                                 1, HAMMER_ALIST_BLOCK_MAX);
 969                 }
 970         } else {
 971                 buf_no = hammer_alist_alloc_fwd(&cluster->alist_master,
 972                                                 1, start);
 973                 if (buf_no == HAMMER_ALIST_BLOCK_NONE) {
 974                         buf_no = hammer_alist_alloc_fwd(&cluster->alist_master,
 975                                                 1, 0);
 976                 }
 977         }
 978         KKASSERT(buf_no != HAMMER_ALIST_BLOCK_NONE); /* XXX */
 979
 980         /*
 981          * The new buffer must be initialized (type != 0) regardless of
 982          * whether we already have it cached or not, so don't try to
 983          * optimize the cached buffer check.  Just call hammer_get_buffer().
 984          */
 985         buffer = hammer_get_buffer(cluster, buf_no, type, errorp);
 986         if (*bufferp)
 987                 hammer_put_buffer(*bufferp);
 988         *bufferp = buffer;
 989 }
 990
 991 #if 0
 992
 993 /*
 994  * Flush various tracking structures to disk
 995  */
 996
 997 /*
 998  * Flush various tracking structures to disk
 999  */
1000 void
1001 flush_all_volumes(void)
1002 {
1003         struct hammer_volume *vol;
1004
1005         for (vol = VolBase; vol; vol = vol->next)
1006                 flush_volume(vol);
1007 }
1008
1009 void
1010 flush_volume(struct hammer_volume *vol)
1011 {
1012         struct hammer_supercl *supercl;
1013         struct hammer_cluster *cl;
1014
1015         for (supercl = vol->supercl_base; supercl; supercl = supercl->next)
1016                 flush_supercl(supercl);
1017         for (cl = vol->cluster_base; cl; cl = cl->next)
1018                 flush_cluster(cl);
1019         writehammerbuf(vol, vol->ondisk, 0);
1020 }
1021
1022 void
1023 flush_supercl(struct hammer_supercl *supercl)
1024 {
1025         int64_t supercl_offset;
1026
1027         supercl_offset = supercl->scl_offset;
1028         writehammerbuf(supercl->volume, supercl->ondisk, supercl_offset);
1029 }
1030
1031 void
1032 flush_cluster(struct hammer_cluster *cl)
1033 {
1034         struct hammer_buffer *buf;
1035         int64_t cluster_offset;
1036
1037         for (buf = cl->buffer_base; buf; buf = buf->next)
1038                 flush_buffer(buf);
1039         cluster_offset = cl->clu_offset;
1040         writehammerbuf(cl->volume, cl->ondisk, cluster_offset);
1041 }
1042
1043 void
1044 flush_buffer(struct hammer_buffer *buf)
1045 {
1046         int64_t buffer_offset;
1047
1048         buffer_offset = buf->buf_offset + buf->cluster->clu_offset;
1049         writehammerbuf(buf->volume, buf->ondisk, buffer_offset);
1050 }
1051
1052 #endif
1053
1054 /*
1055  * Generic buffer initialization
1056  */
1057 static void
1058 initbuffer(hammer_alist_t live, hammer_fsbuf_head_t head, u_int64_t type)
1059 {
1060         head->buf_type = type;
1061         hammer_alist_init(live);
1062 }
1063
1064 #if 0
1065 /*
1066  * Core I/O operations
1067  */
1068 static void
1069 readhammerbuf(struct hammer_volume *vol, void *data, int64_t offset)
1070 {
1071         ssize_t n;
1072
1073         n = pread(vol->fd, data, HAMMER_BUFSIZE, offset);
1074         if (n != HAMMER_BUFSIZE)
1075                 err(1, "Read volume %d (%s)", vol->vol_no, vol->name);
1076 }
1077
1078 static void
1079 writehammerbuf(struct hammer_volume *vol, const void *data, int64_t offset)
1080 {
1081         ssize_t n;
1082
1083         n = pwrite(vol->fd, data, HAMMER_BUFSIZE, offset);
1084         if (n != HAMMER_BUFSIZE)
1085                 err(1, "Write volume %d (%s)", vol->vol_no, vol->name);
1086 }
1087
1088 #endif
1089
1090 /*
1091  * Calculate the cluster's offset in the volume.  This calculation is
1092  * slightly more complex when using superclusters because superclusters
1093  * are grouped in blocks of 16, followed by 16 x N clusters where N
1094  * is the number of clusters a supercluster can manage.
1095  */
1096 static int64_t
1097 calculate_cluster_offset(struct hammer_volume *volume, int32_t clu_no)
1098 {
1099         int32_t scl_group;
1100         int64_t scl_group_size;
1101         int64_t off;
1102
1103         if (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL) {
1104                 scl_group = clu_no / HAMMER_VOL_SUPERCLUSTER_GROUP /
1105                             HAMMER_SCL_MAXCLUSTERS;
1106                 scl_group_size =
1107                             ((int64_t)HAMMER_BUFSIZE *
1108                              HAMMER_VOL_SUPERCLUSTER_GROUP) +
1109                             ((int64_t)HAMMER_VOL_SUPERCLUSTER_GROUP *
1110                              volume->vol_clsize * HAMMER_SCL_MAXCLUSTERS);
1111                 scl_group_size +=
1112                             HAMMER_VOL_SUPERCLUSTER_GROUP * HAMMER_BUFSIZE;
1113
1114                 off = volume->cluster_base +
1115                       scl_group * scl_group_size +
1116                       (HAMMER_BUFSIZE * HAMMER_VOL_SUPERCLUSTER_GROUP) +
1117                       ((int64_t)clu_no % ((int64_t)HAMMER_SCL_MAXCLUSTERS *
1118                        HAMMER_VOL_SUPERCLUSTER_GROUP))
1119                       * HAMMER_BUFSIZE;
1120         } else {
1121                 off = volume->cluster_base +
1122                       (int64_t)clu_no * volume->vol_clsize;
1123         }
1124         return(off);
1125 }
1126
1127 /*
1128  * Calculate a super-cluster's offset in the volume.
1129  */
1130 static int64_t
1131 calculate_supercl_offset(struct hammer_volume *volume, int32_t scl_no)
1132 {
1133         int64_t off;
1134         int32_t scl_group;
1135         int64_t scl_group_size;
1136
1137         KKASSERT (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL);
1138         scl_group = scl_no / HAMMER_VOL_SUPERCLUSTER_GROUP;
1139         if (scl_group) {
1140                 scl_group_size =
1141                             ((int64_t)HAMMER_BUFSIZE *
1142                              HAMMER_VOL_SUPERCLUSTER_GROUP) +
1143                             ((int64_t)HAMMER_VOL_SUPERCLUSTER_GROUP *
1144                              volume->vol_clsize * HAMMER_SCL_MAXCLUSTERS);
1145                 scl_group_size +=
1146                             HAMMER_VOL_SUPERCLUSTER_GROUP * HAMMER_BUFSIZE;
1147                 off = volume->cluster_base + (scl_group * scl_group_size) +
1148                       (scl_no % HAMMER_VOL_SUPERCLUSTER_GROUP) * HAMMER_BUFSIZE;
1149         } else {
1150                 off = volume->cluster_base + (scl_no * HAMMER_BUFSIZE);
1151         }
1152         return(off);
1153 }
1154
1155 /*
1156  * A-LIST SUPPORT
1157  *
1158  * Setup the parameters for the various A-lists we use in hammer.  The
1159  * supercluster A-list must be chained to the cluster A-list and cluster
1160  * slave A-lists are chained to buffer A-lists.
1161  *
1162  * See hammer_init_alist_config() below.
1163  */
1164
1165 /*
1166  * A-LIST - cluster recursion into a filesystem buffer
1167  */
1168 static int
1169 buffer_alist_init(void *info, int32_t blk, int32_t radix)
1170 {
1171         struct hammer_cluster *cluster = info;
1172         struct hammer_buffer *buffer;
1173         int32_t buf_no;
1174         int error = 0;
1175
1176         /*
1177          * Calculate the buffer number, initialize based on the buffer type.
1178          * The buffer has already been allocated so assert that it has been
1179          * initialized.
1180          */
1181         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1182         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1183         if (buffer)
1184                 hammer_put_buffer(buffer);
1185         return (error);
1186 }
1187
1188 static int
1189 buffer_alist_destroy(void *info, int32_t blk, int32_t radix)
1190 {
1191         return (0);
1192 }
1193
1194 static int
1195 buffer_alist_alloc_fwd(void *info, int32_t blk, int32_t radix,
1196                       int32_t count, int32_t atblk, int32_t *fullp)
1197 {
1198         struct hammer_cluster *cluster = info;
1199         struct hammer_buffer *buffer;
1200         int32_t buf_no;
1201         int32_t r;
1202         int error = 0;
1203
1204         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1205         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1206         if (buffer) {
1207                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1208
1209                 r = hammer_alist_alloc_fwd(&buffer->alist, count, atblk - blk);
1210                 if (r != HAMMER_ALIST_BLOCK_NONE)
1211                         r += blk;
1212                 *fullp = hammer_alist_isfull(&buffer->alist);
1213                 hammer_put_buffer(buffer);
1214         } else {
1215                 r = HAMMER_ALIST_BLOCK_NONE;
1216         }
1217         return(r);
1218 }
1219
1220 static int
1221 buffer_alist_alloc_rev(void *info, int32_t blk, int32_t radix,
1222                       int32_t count, int32_t atblk, int32_t *fullp)
1223 {
1224         struct hammer_cluster *cluster = info;
1225         struct hammer_buffer *buffer;
1226         int32_t buf_no;
1227         int32_t r;
1228         int error = 0;
1229
1230         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1231         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1232         if (buffer) {
1233                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1234
1235                 r = hammer_alist_alloc_rev(&buffer->alist, count, atblk - blk);
1236                 if (r != HAMMER_ALIST_BLOCK_NONE)
1237                         r += blk;
1238                 *fullp = hammer_alist_isfull(&buffer->alist);
1239                 hammer_put_buffer(buffer);
1240         } else {
1241                 r = HAMMER_ALIST_BLOCK_NONE;
1242                 *fullp = 0;
1243         }
1244         return(r);
1245 }
1246
1247 static void
1248 buffer_alist_free(void *info, int32_t blk, int32_t radix,
1249                  int32_t base_blk, int32_t count, int32_t *emptyp)
1250 {
1251         struct hammer_cluster *cluster = info;
1252         struct hammer_buffer *buffer;
1253         int32_t buf_no;
1254         int error = 0;
1255
1256         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1257         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1258         if (buffer) {
1259                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1260                 hammer_alist_free(&buffer->alist, base_blk, count);
1261                 *emptyp = hammer_alist_isempty(&buffer->alist);
1262                 hammer_put_buffer(buffer);
1263         } else {
1264                 *emptyp = 0;
1265         }
1266 }
1267
1268 static void
1269 buffer_alist_print(void *info, int32_t blk, int32_t radix, int tab)
1270 {
1271 }
1272
1273 /*
1274  * A-LIST - super-cluster recursion into a cluster and cluster recursion
1275  * into a filesystem buffer.  A-List's are mostly self-contained entities,
1276  * but callbacks must be installed to recurse from one A-List to another.
1277  *
1278  * Implementing these callbacks allows us to operate a multi-layered A-List
1279  * as a single entity.
1280  */
1281 static int
1282 super_alist_init(void *info, int32_t blk, int32_t radix)
1283 {
1284         struct hammer_volume *volume = info;
1285         struct hammer_supercl *supercl;
1286         int32_t scl_no;
1287         int error = 0;
1288
1289         /*
1290          * Calculate the super-cluster number containing the cluster (blk)
1291          * and obtain the super-cluster buffer.
1292          */
1293         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1294         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1295         if (supercl)
1296                 hammer_put_supercl(supercl);
1297         return (error);
1298 }
1299
1300 static int
1301 super_alist_destroy(void *info, int32_t blk, int32_t radix)
1302 {
1303         return(0);
1304 }
1305
1306 static int
1307 super_alist_alloc_fwd(void *info, int32_t blk, int32_t radix,
1308                       int32_t count, int32_t atblk, int32_t *fullp)
1309 {
1310         struct hammer_volume *volume = info;
1311         struct hammer_supercl *supercl;
1312         int32_t scl_no;
1313         int32_t r;
1314         int error = 0;
1315
1316         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1317         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1318         if (supercl) {
1319                 r = hammer_alist_alloc_fwd(&supercl->alist, count, atblk - blk);
1320                 if (r != HAMMER_ALIST_BLOCK_NONE)
1321                         r += blk;
1322                 *fullp = hammer_alist_isfull(&supercl->alist);
1323                 hammer_put_supercl(supercl);
1324         } else {
1325                 r = HAMMER_ALIST_BLOCK_NONE;
1326                 *fullp = 0;
1327         }
1328         return(r);
1329 }
1330
1331 static int
1332 super_alist_alloc_rev(void *info, int32_t blk, int32_t radix,
1333                       int32_t count, int32_t atblk, int32_t *fullp)
1334 {
1335         struct hammer_volume *volume = info;
1336         struct hammer_supercl *supercl;
1337         int32_t scl_no;
1338         int32_t r;
1339         int error = 0;
1340
1341         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1342         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1343         if (supercl) {
1344                 r = hammer_alist_alloc_rev(&supercl->alist, count, atblk - blk);
1345                 if (r != HAMMER_ALIST_BLOCK_NONE)
1346                         r += blk;
1347                 *fullp = hammer_alist_isfull(&supercl->alist);
1348                 hammer_put_supercl(supercl);
1349         } else {
1350                 r = HAMMER_ALIST_BLOCK_NONE;
1351                 *fullp = 0;
1352         }
1353         return(r);
1354 }
1355
1356 static void
1357 super_alist_free(void *info, int32_t blk, int32_t radix,
1358                  int32_t base_blk, int32_t count, int32_t *emptyp)
1359 {
1360         struct hammer_volume *volume = info;
1361         struct hammer_supercl *supercl;
1362         int32_t scl_no;
1363         int error = 0;
1364
1365         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1366         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1367         if (supercl) {
1368                 hammer_alist_free(&supercl->alist, base_blk, count);
1369                 *emptyp = hammer_alist_isempty(&supercl->alist);
1370                 hammer_put_supercl(supercl);
1371         } else {
1372                 *emptyp = 0;
1373         }
1374 }
1375
1376 static void
1377 super_alist_print(void *info, int32_t blk, int32_t radix, int tab)
1378 {
1379 }
1380
1381 void
1382 hammer_init_alist_config(void)
1383 {
1384         hammer_alist_config_t config;
1385
1386         hammer_alist_template(&Buf_alist_config, HAMMER_FSBUF_MAXBLKS,
1387                               1, HAMMER_FSBUF_METAELMS);
1388         hammer_alist_template(&Vol_normal_alist_config, HAMMER_VOL_MAXCLUSTERS,
1389                               1, HAMMER_VOL_METAELMS_1LYR);
1390         hammer_alist_template(&Vol_super_alist_config,
1391                               HAMMER_VOL_MAXSUPERCLUSTERS,
1392                               HAMMER_SCL_MAXCLUSTERS, HAMMER_VOL_METAELMS_2LYR);
1393         hammer_alist_template(&Supercl_alist_config, HAMMER_VOL_MAXCLUSTERS,
1394                               1, HAMMER_SUPERCL_METAELMS);
1395         hammer_alist_template(&Clu_master_alist_config, HAMMER_CLU_MAXBUFFERS,
1396                               1, HAMMER_CLU_MASTER_METAELMS);
1397         hammer_alist_template(&Clu_slave_alist_config, HAMMER_CLU_MAXBUFFERS,
1398                               HAMMER_FSBUF_MAXBLKS, HAMMER_CLU_SLAVE_METAELMS);
1399
1400         config = &Vol_super_alist_config;
1401         config->bl_radix_init = super_alist_init;
1402         config->bl_radix_destroy = super_alist_destroy;
1403         config->bl_radix_alloc_fwd = super_alist_alloc_fwd;
1404         config->bl_radix_alloc_rev = super_alist_alloc_rev;
1405         config->bl_radix_free = super_alist_free;
1406         config->bl_radix_print = super_alist_print;
1407
1408         config = &Clu_slave_alist_config;
1409         config->bl_radix_init = buffer_alist_init;
1410         config->bl_radix_destroy = buffer_alist_destroy;
1411         config->bl_radix_alloc_fwd = buffer_alist_alloc_fwd;
1412         config->bl_radix_alloc_rev = buffer_alist_alloc_rev;
1413         config->bl_radix_free = buffer_alist_free;
1414         config->bl_radix_print = buffer_alist_print;
1415 }
1416
1417