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