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.2 2007/11/02 00:57:15 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
 285         /*
 286          * Clean up
 287          */
 288         if (hmp->rootvol == volume) {
 289                 if (hmp->rootcl) {
 290                         hammer_put_cluster(hmp->rootcl);
 291                         hmp->rootcl = NULL;
 292                 }
 293                 hmp->rootvol = NULL;
 294         }
 295
 296         /* flush_volume */
 297         KKASSERT(volume->bp == NULL);
 298
 299         /*
 300          * Destroy the structure
 301          */
 302         RB_REMOVE(hammer_vol_rb_tree, &hmp->rb_vols_root, volume);
 303         hammer_free_volume(volume);
 304         return(0);
 305 }
 306
 307 static
 308 void
 309 hammer_free_volume(struct hammer_volume *volume)
 310 {
 311         if (volume->vol_name) {
 312                 kfree(volume->vol_name, M_HAMMER);
 313                 volume->vol_name = NULL;
 314         }
 315         if (volume->devvp) {
 316                 vrele(volume->devvp);
 317                 volume->devvp = NULL;
 318         }
 319         kfree(volume, M_HAMMER);
 320 }
 321
 322 /*
 323  * Get a HAMMER volume.  The volume must already exist.
 324  */
 325 struct hammer_volume *
 326 hammer_get_volume(struct hammer_mount *hmp, int32_t vol_no, int *errorp)
 327 {
 328         struct hammer_volume *volume;
 329         struct hammer_volume_ondisk *ondisk;
 330
 331         /*
 332          * Locate the volume structure
 333          */
 334         volume = RB_LOOKUP(hammer_vol_rb_tree, &hmp->rb_vols_root, vol_no);
 335         if (volume == NULL) {
 336                 *errorp = ENOENT;
 337                 return(NULL);
 338         }
 339
 340         /*
 341          * Load the ondisk buffer if necessary
 342          */
 343         hammer_lock(&volume->lock);
 344         if (volume->ondisk == NULL) {
 345                 *errorp = bread(volume->devvp, 0LL, HAMMER_BUFSIZE,
 346                                 &volume->bp);
 347                 if (*errorp) {
 348                         hammer_unlock(&volume->lock);
 349                         return(NULL);
 350                 }
 351                 volume->ondisk = ondisk = (void *)volume->bp->b_data;
 352
 353                 /*
 354                  * Configure the volume's A-lists.  These are used to
 355                  * allocate clusters.
 356                  */
 357                 if (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL) {
 358                         volume->alist.config = &Vol_super_alist_config;
 359                         volume->alist.meta = ondisk->vol_almeta.super;
 360                         volume->alist.info = volume;
 361                 } else {
 362                         volume->alist.config = &Vol_normal_alist_config;
 363                         volume->alist.meta = ondisk->vol_almeta.normal;
 364                         volume->alist.info = NULL;
 365                 }
 366                 hammer_alist_init(&volume->alist);
 367         }
 368         *errorp = 0;
 369         return(volume);
 370 }
 371
 372 void
 373 hammer_put_volume(struct hammer_volume *volume)
 374 {
 375         if (hammer_islastref(&volume->lock)) {
 376                 if (volume->bp) {
 377                         if (volume->modified) {
 378                                 bdwrite(volume->bp);
 379                         } else {
 380                                 brelse(volume->bp);
 381                         }
 382                         volume->bp = NULL;
 383                         volume->ondisk = NULL;
 384                 }
 385                 volume->modified = 0;
 386         }
 387         hammer_unlock(&volume->lock);
 388 }
 389
 390 struct hammer_supercl *
 391 hammer_get_supercl(struct hammer_volume *volume, int32_t scl_no,
 392                    int *errorp, int isnew)
 393 {
 394         struct hammer_supercl_ondisk *ondisk;
 395         struct hammer_supercl *supercl;
 396
 397         /*
 398          * Locate and lock the super-cluster structure, creating one
 399          * if necessary.
 400          */
 401 again:
 402         supercl = RB_LOOKUP(hammer_scl_rb_tree, &volume->rb_scls_root, scl_no);
 403         if (supercl == NULL) {
 404                 supercl = kmalloc(sizeof(*supercl), M_HAMMER, M_WAITOK|M_ZERO);
 405                 supercl->scl_no = scl_no;
 406                 supercl->volume = volume;
 407                 supercl->scl_offset = calculate_supercl_offset(volume, scl_no);
 408                 hammer_lock(&supercl->lock);
 409
 410                 /*
 411                  * Insert the cluster into the RB tree and handle late
 412                  * collisions.
 413                  */
 414                 if (RB_INSERT(hammer_scl_rb_tree, &volume->rb_scls_root, supercl)) {
 415                         hammer_unlock(&supercl->lock);
 416                         kfree(supercl, M_HAMMER);
 417                         goto again;
 418                 }
 419         } else {
 420                 hammer_lock(&supercl->lock);
 421         }
 422
 423         /*
 424          * Load the cluster's on-disk info
 425          */
 426         *errorp = 0;
 427         if (supercl->ondisk == NULL) {
 428                 if (isnew) {
 429                         supercl->bp = getblk(volume->devvp, supercl->scl_offset,
 430                                              HAMMER_BUFSIZE, 0, 0);
 431                         vfs_bio_clrbuf(supercl->bp);
 432                         supercl->modified = 1;
 433                 } else {
 434                         *errorp = bread(volume->devvp, supercl->scl_offset,
 435                                         HAMMER_BUFSIZE, &supercl->bp);
 436                 }
 437                 if (*errorp) {
 438                         hammer_unlock(&supercl->lock);
 439                         return(NULL);
 440                 }
 441                 BUF_KERNPROC(supercl->bp);
 442                 supercl->ondisk = ondisk = (void *)supercl->bp->b_data;
 443
 444                 supercl->alist.config = &Supercl_alist_config;
 445                 supercl->alist.meta = ondisk->scl_meta;
 446                 supercl->alist.info = NULL;
 447
 448                 /*
 449                  * If this is a new super-cluster we have to initialize
 450                  * various ondisk structural elements.  The caller is
 451                  * responsible for the remainder.
 452                  */
 453                 if (isnew) {
 454                         struct hammer_alist_live dummy;
 455
 456                         dummy.config = &Buf_alist_config;
 457                         dummy.meta = ondisk->head.buf_almeta;
 458                         dummy.info = NULL;
 459                         initbuffer(&dummy, &ondisk->head, HAMMER_FSBUF_SUPERCL);
 460                         hammer_alist_init(&supercl->alist);
 461                 }
 462         } else if (isnew) {
 463                 vfs_bio_clrbuf(supercl->bp);
 464                 supercl->modified = 1;
 465         }
 466         return (supercl);
 467 }
 468
 469 void
 470 hammer_put_supercl(struct hammer_supercl *supercl)
 471 {
 472         if (hammer_islastref(&supercl->lock)) {
 473                 if (supercl->bp) {
 474                         if (supercl->modified) {
 475                                 bdwrite(supercl->bp);
 476                         } else {
 477                                 brelse(supercl->bp);
 478                         }
 479                         supercl->bp = NULL;
 480                         supercl->ondisk = NULL;
 481                 }
 482                 supercl->modified = 0;
 483         }
 484         hammer_unlock(&supercl->lock);
 485 }
 486
 487 struct hammer_cluster *
 488 hammer_get_cluster(struct hammer_volume *volume, int32_t clu_no,
 489                    int *errorp, int isnew)
 490 {
 491         struct hammer_cluster_ondisk *ondisk;
 492         struct hammer_cluster *cluster;
 493
 494         /*
 495          * Locate and lock the cluster structure, creating one if necessary.
 496          */
 497 again:
 498         cluster = RB_LOOKUP(hammer_clu_rb_tree, &volume->rb_clus_root, clu_no);
 499         if (cluster == NULL) {
 500                 cluster = kmalloc(sizeof(*cluster), M_HAMMER, M_WAITOK|M_ZERO);
 501                 cluster->clu_no = clu_no;
 502                 cluster->volume = volume;
 503                 cluster->clu_offset = calculate_cluster_offset(volume, clu_no);
 504                 RB_INIT(&cluster->rb_bufs_root);
 505                 hammer_lock(&cluster->lock);
 506
 507                 /*
 508                  * Insert the cluster into the RB tree and handle late
 509                  * collisions.
 510                  */
 511                 if (RB_INSERT(hammer_clu_rb_tree, &volume->rb_clus_root, cluster)) {
 512                         hammer_unlock(&cluster->lock);
 513                         kfree(cluster, M_HAMMER);
 514                         goto again;
 515                 }
 516         } else {
 517                 hammer_lock(&cluster->lock);
 518         }
 519
 520         /*
 521          * Load the cluster's on-disk info
 522          */
 523         *errorp = 0;
 524         if (cluster->ondisk == NULL) {
 525                 if (isnew) {
 526                         cluster->bp = getblk(volume->devvp, cluster->clu_offset,
 527                                              HAMMER_BUFSIZE, 0, 0);
 528                         vfs_bio_clrbuf(cluster->bp);
 529                         cluster->modified = 1;
 530                 } else {
 531                         *errorp = bread(volume->devvp, cluster->clu_offset,
 532                                         HAMMER_BUFSIZE, &cluster->bp);
 533                 }
 534                 if (*errorp) {
 535                         hammer_unlock(&cluster->lock);
 536                         return(NULL);
 537                 }
 538                 BUF_KERNPROC(cluster->bp);
 539                 cluster->ondisk = ondisk = (void *)cluster->bp->b_data;
 540
 541                 cluster->alist_master.config = &Clu_master_alist_config;
 542                 cluster->alist_master.meta = ondisk->clu_master_meta;
 543                 cluster->alist_btree.config = &Clu_slave_alist_config;
 544                 cluster->alist_btree.meta = ondisk->clu_btree_meta;
 545                 cluster->alist_btree.info = cluster;
 546                 cluster->alist_record.config = &Clu_slave_alist_config;
 547                 cluster->alist_record.meta = ondisk->clu_record_meta;
 548                 cluster->alist_record.info = cluster;
 549                 cluster->alist_mdata.config = &Clu_slave_alist_config;
 550                 cluster->alist_mdata.meta = ondisk->clu_mdata_meta;
 551                 cluster->alist_mdata.info = cluster;
 552
 553                 /*
 554                  * If this is a new cluster we have to initialize
 555                  * various ondisk structural elements.  The caller is
 556                  * responsible for the remainder.
 557                  */
 558                 if (isnew) {
 559                         struct hammer_alist_live dummy;
 560
 561                         dummy.config = &Buf_alist_config;
 562                         dummy.meta = ondisk->head.buf_almeta;
 563                         dummy.info = NULL;
 564                         initbuffer(&dummy, &ondisk->head, HAMMER_FSBUF_CLUSTER);
 565
 566                         hammer_alist_init(&cluster->alist_master);
 567                         hammer_alist_init(&cluster->alist_btree);
 568                         hammer_alist_init(&cluster->alist_record);
 569                         hammer_alist_init(&cluster->alist_mdata);
 570                 }
 571         } else if (isnew) {
 572                 vfs_bio_clrbuf(cluster->bp);
 573                 cluster->modified = 1;
 574         }
 575         return(cluster);
 576 }
 577
 578 void
 579 hammer_put_cluster(struct hammer_cluster *cluster)
 580 {
 581         if (hammer_islastref(&cluster->lock)) {
 582                 if (cluster->bp) {
 583                         if (cluster->modified) {
 584                                 bdwrite(cluster->bp);
 585                         } else {
 586                                 brelse(cluster->bp);
 587                         }
 588                         cluster->bp = NULL;
 589                         cluster->ondisk = NULL;
 590                 }
 591                 cluster->modified = 0;
 592         }
 593         hammer_unlock(&cluster->lock);
 594 }
 595
 596 /*
 597  * Get a buffer from a cluster.  Note that buffer #0 is the cluster header
 598  * itself and may not be retrieved with this function.
 599  *
 600  * If buf_type is 0 the buffer already exists in-memory or on-disk.
 601  * Otherwise a new buffer is initialized with the specified buffer type.
 602  */
 603 struct hammer_buffer *
 604 hammer_get_buffer(struct hammer_cluster *cluster, int32_t buf_no,
 605                   int64_t buf_type, int *errorp)
 606 {
 607         hammer_fsbuf_ondisk_t ondisk;
 608         struct hammer_buffer *buffer;
 609
 610         /*
 611          * Find the buffer.  Note that buffer 0 corresponds to the cluster
 612          * header and should never be requested.
 613          */
 614         KKASSERT(buf_no != 0);
 615
 616         /*
 617          * Locate and lock the buffer structure, creating one if necessary.
 618          */
 619 again:
 620         buffer = RB_LOOKUP(hammer_buf_rb_tree, &cluster->rb_bufs_root, buf_no);
 621         if (buffer == NULL) {
 622                 buffer = kmalloc(sizeof(*cluster), M_HAMMER, M_WAITOK|M_ZERO);
 623                 buffer->buf_no = buf_no;
 624                 buffer->cluster = cluster;
 625                 buffer->volume = cluster->volume;
 626                 buffer->buf_offset = cluster->clu_offset +
 627                                      (buf_no * HAMMER_BUFSIZE);
 628                 hammer_lock(&buffer->lock);
 629
 630                 /*
 631                  * Insert the cluster into the RB tree and handle late
 632                  * collisions.
 633                  */
 634                 if (RB_INSERT(hammer_buf_rb_tree, &cluster->rb_bufs_root, buffer)) {
 635                         hammer_unlock(&buffer->lock);
 636                         kfree(buffer, M_HAMMER);
 637                         goto again;
 638                 }
 639         } else {
 640                 hammer_lock(&buffer->lock);
 641         }
 642
 643         *errorp = 0;
 644         if (buffer->ondisk == NULL) {
 645                 if (buf_type) {
 646                         buffer->bp = getblk(buffer->volume->devvp,
 647                                             buffer->buf_offset,
 648                                             HAMMER_BUFSIZE, 0, 0);
 649                         vfs_bio_clrbuf(buffer->bp);
 650                         buffer->modified = 1;
 651                 } else {
 652                         *errorp = bread(buffer->volume->devvp,
 653                                         buffer->buf_offset,
 654                                         HAMMER_BUFSIZE, &buffer->bp);
 655                 }
 656                 if (*errorp) {
 657                         hammer_unlock(&buffer->lock);
 658                         return(NULL);
 659                 }
 660                 BUF_KERNPROC(buffer->bp);
 661                 buffer->ondisk = ondisk = (void *)buffer->bp->b_data;
 662                 buffer->alist.config = &Buf_alist_config;
 663                 buffer->alist.meta = ondisk->head.buf_almeta;
 664
 665                 if (buf_type) {
 666                         initbuffer(&buffer->alist, &ondisk->head, buf_type);
 667                 }
 668         } else if (buf_type) {
 669                 vfs_bio_clrbuf(buffer->bp);
 670                 buffer->modified = 1;
 671         }
 672         return (buffer);
 673 }
 674
 675 void
 676 hammer_put_buffer(struct hammer_buffer *buffer)
 677 {
 678         if (hammer_islastref(&buffer->lock)) {
 679                 if (buffer->bp) {
 680                         if (buffer->modified) {
 681                                 bdwrite(buffer->bp);
 682                         } else {
 683                                 brelse(buffer->bp);
 684                         }
 685                         buffer->bp = NULL;
 686                         buffer->ondisk = NULL;
 687                 }
 688                 buffer->modified = 0;
 689         }
 690         hammer_unlock(&buffer->lock);
 691 }
 692
 693 void
 694 hammer_dup_buffer(struct hammer_buffer **bufferp, struct hammer_buffer *buffer)
 695 {
 696         if (buffer != *bufferp) {
 697                 if (buffer)
 698                         hammer_lock(&buffer->lock);
 699                 if (*bufferp)
 700                         hammer_put_buffer(*bufferp);
 701                 *bufferp = buffer;
 702         }
 703 }
 704
 705 void
 706 hammer_dup_cluster(struct hammer_cluster **clusterp,
 707                    struct hammer_cluster *cluster)
 708 {
 709         if (cluster != *clusterp) {
 710                 if (cluster)
 711                         hammer_lock(&cluster->lock);
 712                 if (*clusterp)
 713                         hammer_put_cluster(*clusterp);
 714                 *clusterp = cluster;
 715         }
 716 }
 717
 718 /*
 719  * Allocate HAMMER elements - btree nodes, data storage, and record elements
 720  *
 721  * The passed *bufferp should be initialized to NULL.  On successive calls
 722  * *bufferp caches the most recent buffer used until put away by the caller.
 723  * Note that previously returned pointers using the cached buffer become
 724  * invalid on successive calls which reuse *bufferp.
 725  *
 726  * All allocations first attempt to use the block found at the specified
 727  * iterator.  If that fails the first available block is used.  If that
 728  * fails a new buffer is allocated and associated with the buffer type
 729  * A-list and the element is allocated out of the new buffer.
 730  */
 731 void *
 732 hammer_alloc_btree(struct hammer_cluster *cluster,
 733                     int *errorp, struct hammer_buffer **bufferp)
 734 {
 735         struct hammer_buffer *buffer;
 736         hammer_alist_t live;
 737         int32_t elm_no;
 738         int32_t buf_no;
 739         void *item;
 740
 741         /*
 742          * Allocate a B-Tree element
 743          */
 744         live = &cluster->alist_btree;
 745         elm_no = hammer_alist_alloc_fwd(live, 1, cluster->ondisk->idx_index);
 746         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 747                 elm_no = hammer_alist_alloc_fwd(live, 1, 0);
 748         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 749                 alloc_new_buffer(cluster, live,
 750                                  HAMMER_FSBUF_BTREE, HAMMER_BTREE_NODES,
 751                                  cluster->ondisk->idx_index, errorp, bufferp);
 752                 elm_no = hammer_alist_alloc(live, 1);
 753                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 754         }
 755         cluster->ondisk->idx_index = elm_no;
 756
 757         /*
 758          * Load and return the B-Tree element
 759          */
 760         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 761         buffer = *bufferp;
 762         if (buffer == NULL || buffer->cluster != cluster ||
 763             buffer->buf_no != buf_no) {
 764                 if (buffer)
 765                         hammer_put_buffer(buffer);
 766                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 767                 *bufferp = buffer;
 768         }
 769         KKASSERT(buffer->ondisk->head.buf_type == HAMMER_FSBUF_BTREE);
 770         item = &buffer->ondisk->btree.nodes[elm_no & HAMMER_FSBUF_BLKMASK];
 771         bzero(item, sizeof(union hammer_btree_node));
 772         return(item);
 773 }
 774
 775 void *
 776 hammer_alloc_data(struct hammer_cluster *cluster, int32_t bytes,
 777                    int *errorp, struct hammer_buffer **bufferp)
 778 {
 779         struct hammer_buffer *buffer;
 780         hammer_alist_t live;
 781         int32_t elm_no;
 782         int32_t buf_no;
 783         int32_t nblks;
 784         void *item;
 785
 786         /*
 787          * Allocate a data element
 788          */
 789         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 790         live = &cluster->alist_mdata;
 791         elm_no = hammer_alist_alloc_fwd(live, nblks, cluster->ondisk->idx_data);
 792         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 793                 elm_no = hammer_alist_alloc_fwd(live, 1, 0);
 794         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 795                 alloc_new_buffer(cluster, live,
 796                                  HAMMER_FSBUF_DATA, HAMMER_DATA_NODES,
 797                                  cluster->ondisk->idx_data, errorp, bufferp);
 798                 elm_no = hammer_alist_alloc(live, nblks);
 799                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 800         }
 801         cluster->ondisk->idx_index = elm_no;
 802
 803         /*
 804          * Load and return the B-Tree element
 805          */
 806         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 807         buffer = *bufferp;
 808         if (buffer == NULL || buffer->cluster != cluster ||
 809             buffer->buf_no != buf_no) {
 810                 if (buffer)
 811                         hammer_put_buffer(buffer);
 812                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 813                 *bufferp = buffer;
 814         }
 815         KKASSERT(buffer->ondisk->head.buf_type == HAMMER_FSBUF_BTREE);
 816         item = &buffer->ondisk->data.data[elm_no & HAMMER_FSBUF_BLKMASK];
 817         bzero(item, nblks * HAMMER_DATA_BLKSIZE);
 818         return(item);
 819 }
 820
 821 void *
 822 hammer_alloc_record(struct hammer_cluster *cluster,
 823                      int *errorp, struct hammer_buffer **bufferp)
 824 {
 825         struct hammer_buffer *buffer;
 826         hammer_alist_t live;
 827         int32_t elm_no;
 828         int32_t buf_no;
 829         void *item;
 830
 831         /*
 832          * Allocate a record element
 833          */
 834         live = &cluster->alist_record;
 835         elm_no = hammer_alist_alloc_rev(live, 1, cluster->ondisk->idx_record);
 836         if (elm_no == HAMMER_ALIST_BLOCK_NONE)
 837                 elm_no = hammer_alist_alloc_rev(live, 1,HAMMER_ALIST_BLOCK_MAX);
 838         if (elm_no == HAMMER_ALIST_BLOCK_NONE) {
 839                 alloc_new_buffer(cluster, live,
 840                                  HAMMER_FSBUF_RECORDS, HAMMER_RECORD_NODES,
 841                                  cluster->ondisk->idx_record, errorp, bufferp);
 842                 elm_no = hammer_alist_alloc(live, 1);
 843                 KKASSERT(elm_no != HAMMER_ALIST_BLOCK_NONE);
 844         }
 845         cluster->ondisk->idx_record = elm_no;
 846
 847         /*
 848          * Load and return the B-Tree element
 849          */
 850         buf_no = elm_no / HAMMER_FSBUF_MAXBLKS;
 851         buffer = *bufferp;
 852         if (buffer == NULL || buffer->cluster != cluster ||
 853             buffer->buf_no != buf_no) {
 854                 if (buffer)
 855                         hammer_put_buffer(buffer);
 856                 buffer = hammer_get_buffer(cluster, buf_no, 0, errorp);
 857                 *bufferp = buffer;
 858         }
 859         KKASSERT(buffer->ondisk->head.buf_type != 0);
 860         item = &buffer->ondisk->record.recs[elm_no & HAMMER_FSBUF_BLKMASK];
 861         bzero(item, sizeof(union hammer_record_ondisk));
 862         return(item);
 863 }
 864
 865 /*
 866  * Free HAMMER elements based on either a hammer_buffer and element pointer
 867  * or a cluster-relative byte offset.
 868  */
 869 void
 870 hammer_free_btree_ptr(struct hammer_buffer *buffer, hammer_btree_node_t node)
 871 {
 872         int32_t elm_no;
 873         hammer_alist_t live;
 874
 875         elm_no = node - buffer->ondisk->btree.nodes;
 876         KKASSERT(elm_no >= 0 && elm_no < HAMMER_BTREE_NODES);
 877         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 878         live = &buffer->cluster->alist_btree;
 879         hammer_alist_free(live, elm_no, 1);
 880 }
 881
 882 void
 883 hammer_free_data_ptr(struct hammer_buffer *buffer, void *data, int bytes)
 884 {
 885         int32_t elm_no;
 886         int32_t nblks;
 887         hammer_alist_t live;
 888
 889         elm_no = ((char *)data - (char *)buffer->ondisk->data.data) /
 890                  HAMMER_DATA_BLKSIZE;
 891         KKASSERT(elm_no >= 0 && elm_no < HAMMER_DATA_NODES);
 892         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 893         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 894         live = &buffer->cluster->alist_mdata;
 895         hammer_alist_free(live, elm_no, nblks);
 896 }
 897
 898 void
 899 hammer_free_record_ptr(struct hammer_buffer *buffer,
 900                        union hammer_record_ondisk *rec)
 901 {
 902         int32_t elm_no;
 903         hammer_alist_t live;
 904
 905         elm_no = rec - &buffer->ondisk->record.recs[0];
 906         KKASSERT(elm_no >= 0 && elm_no < HAMMER_BTREE_NODES);
 907         elm_no += buffer->buf_no * HAMMER_FSBUF_MAXBLKS;
 908         live = &buffer->cluster->alist_record;
 909         hammer_alist_free(live, elm_no, 1);
 910 }
 911
 912 void
 913 hammer_free_btree(struct hammer_cluster *cluster, int32_t bclu_offset)
 914 {
 915         const int32_t blksize = sizeof(union hammer_btree_node);
 916         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 917         hammer_alist_t live;
 918         int32_t elm_no;
 919
 920         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 921         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, btree.nodes[0]);
 922         live = &cluster->alist_btree;
 923         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 924         elm_no += fsbuf_offset / blksize;
 925         hammer_alist_free(live, elm_no, 1);
 926 }
 927
 928 void
 929 hammer_free_data(struct hammer_cluster *cluster, int32_t bclu_offset,
 930                  int32_t bytes)
 931 {
 932         const int32_t blksize = HAMMER_DATA_BLKSIZE;
 933         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 934         hammer_alist_t live;
 935         int32_t elm_no;
 936         int32_t nblks;
 937
 938         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 939         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, data.data[0][0]);
 940         live = &cluster->alist_mdata;
 941         nblks = (bytes + HAMMER_DATA_BLKMASK) & ~HAMMER_DATA_BLKMASK;
 942         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 943         elm_no += fsbuf_offset / blksize;
 944         hammer_alist_free(live, elm_no, nblks);
 945 }
 946
 947 void
 948 hammer_free_record(struct hammer_cluster *cluster, int32_t bclu_offset)
 949 {
 950         const int32_t blksize = sizeof(union hammer_record_ondisk);
 951         int32_t fsbuf_offset = bclu_offset & HAMMER_BUFMASK;
 952         hammer_alist_t live;
 953         int32_t elm_no;
 954
 955         elm_no = bclu_offset / HAMMER_BUFSIZE * HAMMER_FSBUF_MAXBLKS;
 956         fsbuf_offset -= offsetof(union hammer_fsbuf_ondisk, record.recs[0]);
 957         live = &cluster->alist_record;
 958         KKASSERT(fsbuf_offset >= 0 && fsbuf_offset % blksize == 0);
 959         elm_no += fsbuf_offset / blksize;
 960         hammer_alist_free(live, elm_no, 1);
 961 }
 962
 963
 964 /*
 965  * Allocate a new filesystem buffer and assign it to the specified
 966  * filesystem buffer type.  The new buffer will be added to the
 967  * type-specific A-list and initialized.
 968  */
 969 static void
 970 alloc_new_buffer(struct hammer_cluster *cluster, hammer_alist_t live,
 971                  u_int64_t type, int32_t nelements,
 972                  int start, int *errorp, struct hammer_buffer **bufferp)
 973 {
 974         struct hammer_buffer *buffer;
 975         int32_t buf_no;
 976
 977         start = start / HAMMER_FSBUF_MAXBLKS;   /* convert to buf_no */
 978
 979         if (type == HAMMER_FSBUF_RECORDS) {
 980                 buf_no = hammer_alist_alloc_rev(&cluster->alist_master,
 981                                                 1, start);
 982                 if (buf_no == HAMMER_ALIST_BLOCK_NONE) {
 983                         buf_no = hammer_alist_alloc_rev(&cluster->alist_master,
 984                                                 1, HAMMER_ALIST_BLOCK_MAX);
 985                 }
 986         } else {
 987                 buf_no = hammer_alist_alloc_fwd(&cluster->alist_master,
 988                                                 1, start);
 989                 if (buf_no == HAMMER_ALIST_BLOCK_NONE) {
 990                         buf_no = hammer_alist_alloc_fwd(&cluster->alist_master,
 991                                                 1, 0);
 992                 }
 993         }
 994         KKASSERT(buf_no != HAMMER_ALIST_BLOCK_NONE); /* XXX */
 995
 996         /*
 997          * The new buffer must be initialized (type != 0) regardless of
 998          * whether we already have it cached or not, so don't try to
 999          * optimize the cached buffer check.  Just call hammer_get_buffer().
1000          */
1001         buffer = hammer_get_buffer(cluster, buf_no, type, errorp);
1002         if (*bufferp)
1003                 hammer_put_buffer(*bufferp);
1004         *bufferp = buffer;
1005 }
1006
1007 #if 0
1008
1009 /*
1010  * Flush various tracking structures to disk
1011  */
1012
1013 /*
1014  * Flush various tracking structures to disk
1015  */
1016 void
1017 flush_all_volumes(void)
1018 {
1019         struct hammer_volume *vol;
1020
1021         for (vol = VolBase; vol; vol = vol->next)
1022                 flush_volume(vol);
1023 }
1024
1025 void
1026 flush_volume(struct hammer_volume *vol)
1027 {
1028         struct hammer_supercl *supercl;
1029         struct hammer_cluster *cl;
1030
1031         for (supercl = vol->supercl_base; supercl; supercl = supercl->next)
1032                 flush_supercl(supercl);
1033         for (cl = vol->cluster_base; cl; cl = cl->next)
1034                 flush_cluster(cl);
1035         writehammerbuf(vol, vol->ondisk, 0);
1036 }
1037
1038 void
1039 flush_supercl(struct hammer_supercl *supercl)
1040 {
1041         int64_t supercl_offset;
1042
1043         supercl_offset = supercl->scl_offset;
1044         writehammerbuf(supercl->volume, supercl->ondisk, supercl_offset);
1045 }
1046
1047 void
1048 flush_cluster(struct hammer_cluster *cl)
1049 {
1050         struct hammer_buffer *buf;
1051         int64_t cluster_offset;
1052
1053         for (buf = cl->buffer_base; buf; buf = buf->next)
1054                 flush_buffer(buf);
1055         cluster_offset = cl->clu_offset;
1056         writehammerbuf(cl->volume, cl->ondisk, cluster_offset);
1057 }
1058
1059 void
1060 flush_buffer(struct hammer_buffer *buf)
1061 {
1062         int64_t buffer_offset;
1063
1064         buffer_offset = buf->buf_offset + buf->cluster->clu_offset;
1065         writehammerbuf(buf->volume, buf->ondisk, buffer_offset);
1066 }
1067
1068 #endif
1069
1070 /*
1071  * Generic buffer initialization
1072  */
1073 static void
1074 initbuffer(hammer_alist_t live, hammer_fsbuf_head_t head, u_int64_t type)
1075 {
1076         head->buf_type = type;
1077         hammer_alist_init(live);
1078 }
1079
1080 #if 0
1081 /*
1082  * Core I/O operations
1083  */
1084 static void
1085 readhammerbuf(struct hammer_volume *vol, void *data, int64_t offset)
1086 {
1087         ssize_t n;
1088
1089         n = pread(vol->fd, data, HAMMER_BUFSIZE, offset);
1090         if (n != HAMMER_BUFSIZE)
1091                 err(1, "Read volume %d (%s)", vol->vol_no, vol->name);
1092 }
1093
1094 static void
1095 writehammerbuf(struct hammer_volume *vol, const void *data, int64_t offset)
1096 {
1097         ssize_t n;
1098
1099         n = pwrite(vol->fd, data, HAMMER_BUFSIZE, offset);
1100         if (n != HAMMER_BUFSIZE)
1101                 err(1, "Write volume %d (%s)", vol->vol_no, vol->name);
1102 }
1103
1104 #endif
1105
1106 /*
1107  * Calculate the cluster's offset in the volume.  This calculation is
1108  * slightly more complex when using superclusters because superclusters
1109  * are grouped in blocks of 16, followed by 16 x N clusters where N
1110  * is the number of clusters a supercluster can manage.
1111  */
1112 static int64_t
1113 calculate_cluster_offset(struct hammer_volume *volume, int32_t clu_no)
1114 {
1115         int32_t scl_group;
1116         int64_t scl_group_size;
1117         int64_t off;
1118
1119         if (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL) {
1120                 scl_group = clu_no / HAMMER_VOL_SUPERCLUSTER_GROUP /
1121                             HAMMER_SCL_MAXCLUSTERS;
1122                 scl_group_size =
1123                             ((int64_t)HAMMER_BUFSIZE *
1124                              HAMMER_VOL_SUPERCLUSTER_GROUP) +
1125                             ((int64_t)HAMMER_VOL_SUPERCLUSTER_GROUP *
1126                              volume->vol_clsize * HAMMER_SCL_MAXCLUSTERS);
1127                 scl_group_size +=
1128                             HAMMER_VOL_SUPERCLUSTER_GROUP * HAMMER_BUFSIZE;
1129
1130                 off = volume->cluster_base +
1131                       scl_group * scl_group_size +
1132                       (HAMMER_BUFSIZE * HAMMER_VOL_SUPERCLUSTER_GROUP) +
1133                       ((int64_t)clu_no % ((int64_t)HAMMER_SCL_MAXCLUSTERS *
1134                        HAMMER_VOL_SUPERCLUSTER_GROUP))
1135                       * HAMMER_BUFSIZE;
1136         } else {
1137                 off = volume->cluster_base +
1138                       (int64_t)clu_no * volume->vol_clsize;
1139         }
1140         return(off);
1141 }
1142
1143 /*
1144  * Calculate a super-cluster's offset in the volume.
1145  */
1146 static int64_t
1147 calculate_supercl_offset(struct hammer_volume *volume, int32_t scl_no)
1148 {
1149         int64_t off;
1150         int32_t scl_group;
1151         int64_t scl_group_size;
1152
1153         KKASSERT (volume->vol_flags & HAMMER_VOLF_USINGSUPERCL);
1154         scl_group = scl_no / HAMMER_VOL_SUPERCLUSTER_GROUP;
1155         if (scl_group) {
1156                 scl_group_size =
1157                             ((int64_t)HAMMER_BUFSIZE *
1158                              HAMMER_VOL_SUPERCLUSTER_GROUP) +
1159                             ((int64_t)HAMMER_VOL_SUPERCLUSTER_GROUP *
1160                              volume->vol_clsize * HAMMER_SCL_MAXCLUSTERS);
1161                 scl_group_size +=
1162                             HAMMER_VOL_SUPERCLUSTER_GROUP * HAMMER_BUFSIZE;
1163                 off = volume->cluster_base + (scl_group * scl_group_size) +
1164                       (scl_no % HAMMER_VOL_SUPERCLUSTER_GROUP) * HAMMER_BUFSIZE;
1165         } else {
1166                 off = volume->cluster_base + (scl_no * HAMMER_BUFSIZE);
1167         }
1168         return(off);
1169 }
1170
1171 /*
1172  * A-LIST SUPPORT
1173  *
1174  * Setup the parameters for the various A-lists we use in hammer.  The
1175  * supercluster A-list must be chained to the cluster A-list and cluster
1176  * slave A-lists are chained to buffer A-lists.
1177  *
1178  * See hammer_init_alist_config() below.
1179  */
1180
1181 /*
1182  * A-LIST - cluster recursion into a filesystem buffer
1183  */
1184 static int
1185 buffer_alist_init(void *info, int32_t blk, int32_t radix)
1186 {
1187         struct hammer_cluster *cluster = info;
1188         struct hammer_buffer *buffer;
1189         int32_t buf_no;
1190         int error = 0;
1191
1192         /*
1193          * Calculate the buffer number, initialize based on the buffer type.
1194          * The buffer has already been allocated so assert that it has been
1195          * initialized.
1196          */
1197         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1198         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1199         if (buffer)
1200                 hammer_put_buffer(buffer);
1201         return (error);
1202 }
1203
1204 static int
1205 buffer_alist_destroy(void *info, int32_t blk, int32_t radix)
1206 {
1207         return (0);
1208 }
1209
1210 static int
1211 buffer_alist_alloc_fwd(void *info, int32_t blk, int32_t radix,
1212                       int32_t count, int32_t atblk, int32_t *fullp)
1213 {
1214         struct hammer_cluster *cluster = info;
1215         struct hammer_buffer *buffer;
1216         int32_t buf_no;
1217         int32_t r;
1218         int error = 0;
1219
1220         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1221         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1222         if (buffer) {
1223                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1224
1225                 r = hammer_alist_alloc_fwd(&buffer->alist, count, atblk - blk);
1226                 if (r != HAMMER_ALIST_BLOCK_NONE)
1227                         r += blk;
1228                 *fullp = hammer_alist_isfull(&buffer->alist);
1229                 hammer_put_buffer(buffer);
1230         } else {
1231                 r = HAMMER_ALIST_BLOCK_NONE;
1232         }
1233         return(r);
1234 }
1235
1236 static int
1237 buffer_alist_alloc_rev(void *info, int32_t blk, int32_t radix,
1238                       int32_t count, int32_t atblk, int32_t *fullp)
1239 {
1240         struct hammer_cluster *cluster = info;
1241         struct hammer_buffer *buffer;
1242         int32_t buf_no;
1243         int32_t r;
1244         int error = 0;
1245
1246         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1247         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1248         if (buffer) {
1249                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1250
1251                 r = hammer_alist_alloc_rev(&buffer->alist, count, atblk - blk);
1252                 if (r != HAMMER_ALIST_BLOCK_NONE)
1253                         r += blk;
1254                 *fullp = hammer_alist_isfull(&buffer->alist);
1255                 hammer_put_buffer(buffer);
1256         } else {
1257                 r = HAMMER_ALIST_BLOCK_NONE;
1258                 *fullp = 0;
1259         }
1260         return(r);
1261 }
1262
1263 static void
1264 buffer_alist_free(void *info, int32_t blk, int32_t radix,
1265                  int32_t base_blk, int32_t count, int32_t *emptyp)
1266 {
1267         struct hammer_cluster *cluster = info;
1268         struct hammer_buffer *buffer;
1269         int32_t buf_no;
1270         int error = 0;
1271
1272         buf_no = blk / HAMMER_FSBUF_MAXBLKS;
1273         buffer = hammer_get_buffer(cluster, buf_no, 0, &error);
1274         if (buffer) {
1275                 KKASSERT(buffer->ondisk->head.buf_type != 0);
1276                 hammer_alist_free(&buffer->alist, base_blk, count);
1277                 *emptyp = hammer_alist_isempty(&buffer->alist);
1278                 hammer_put_buffer(buffer);
1279         } else {
1280                 *emptyp = 0;
1281         }
1282 }
1283
1284 static void
1285 buffer_alist_print(void *info, int32_t blk, int32_t radix, int tab)
1286 {
1287 }
1288
1289 /*
1290  * A-LIST - super-cluster recursion into a cluster and cluster recursion
1291  * into a filesystem buffer.  A-List's are mostly self-contained entities,
1292  * but callbacks must be installed to recurse from one A-List to another.
1293  *
1294  * Implementing these callbacks allows us to operate a multi-layered A-List
1295  * as a single entity.
1296  */
1297 static int
1298 super_alist_init(void *info, int32_t blk, int32_t radix)
1299 {
1300         struct hammer_volume *volume = info;
1301         struct hammer_supercl *supercl;
1302         int32_t scl_no;
1303         int error = 0;
1304
1305         /*
1306          * Calculate the super-cluster number containing the cluster (blk)
1307          * and obtain the super-cluster buffer.
1308          */
1309         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1310         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1311         if (supercl)
1312                 hammer_put_supercl(supercl);
1313         return (error);
1314 }
1315
1316 static int
1317 super_alist_destroy(void *info, int32_t blk, int32_t radix)
1318 {
1319         return(0);
1320 }
1321
1322 static int
1323 super_alist_alloc_fwd(void *info, int32_t blk, int32_t radix,
1324                       int32_t count, int32_t atblk, int32_t *fullp)
1325 {
1326         struct hammer_volume *volume = info;
1327         struct hammer_supercl *supercl;
1328         int32_t scl_no;
1329         int32_t r;
1330         int error = 0;
1331
1332         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1333         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1334         if (supercl) {
1335                 r = hammer_alist_alloc_fwd(&supercl->alist, count, atblk - blk);
1336                 if (r != HAMMER_ALIST_BLOCK_NONE)
1337                         r += blk;
1338                 *fullp = hammer_alist_isfull(&supercl->alist);
1339                 hammer_put_supercl(supercl);
1340         } else {
1341                 r = HAMMER_ALIST_BLOCK_NONE;
1342                 *fullp = 0;
1343         }
1344         return(r);
1345 }
1346
1347 static int
1348 super_alist_alloc_rev(void *info, int32_t blk, int32_t radix,
1349                       int32_t count, int32_t atblk, int32_t *fullp)
1350 {
1351         struct hammer_volume *volume = info;
1352         struct hammer_supercl *supercl;
1353         int32_t scl_no;
1354         int32_t r;
1355         int error = 0;
1356
1357         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1358         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1359         if (supercl) {
1360                 r = hammer_alist_alloc_rev(&supercl->alist, count, atblk - blk);
1361                 if (r != HAMMER_ALIST_BLOCK_NONE)
1362                         r += blk;
1363                 *fullp = hammer_alist_isfull(&supercl->alist);
1364                 hammer_put_supercl(supercl);
1365         } else {
1366                 r = HAMMER_ALIST_BLOCK_NONE;
1367                 *fullp = 0;
1368         }
1369         return(r);
1370 }
1371
1372 static void
1373 super_alist_free(void *info, int32_t blk, int32_t radix,
1374                  int32_t base_blk, int32_t count, int32_t *emptyp)
1375 {
1376         struct hammer_volume *volume = info;
1377         struct hammer_supercl *supercl;
1378         int32_t scl_no;
1379         int error = 0;
1380
1381         scl_no = blk / HAMMER_SCL_MAXCLUSTERS;
1382         supercl = hammer_get_supercl(volume, scl_no, &error, 1);
1383         if (supercl) {
1384                 hammer_alist_free(&supercl->alist, base_blk, count);
1385                 *emptyp = hammer_alist_isempty(&supercl->alist);
1386                 hammer_put_supercl(supercl);
1387         } else {
1388                 *emptyp = 0;
1389         }
1390 }
1391
1392 static void
1393 super_alist_print(void *info, int32_t blk, int32_t radix, int tab)
1394 {
1395 }
1396
1397 void
1398 hammer_init_alist_config(void)
1399 {
1400         hammer_alist_config_t config;
1401
1402         hammer_alist_template(&Buf_alist_config, HAMMER_FSBUF_MAXBLKS,
1403                               1, HAMMER_FSBUF_METAELMS);
1404         hammer_alist_template(&Vol_normal_alist_config, HAMMER_VOL_MAXCLUSTERS,
1405                               1, HAMMER_VOL_METAELMS_1LYR);
1406         hammer_alist_template(&Vol_super_alist_config,
1407                               HAMMER_VOL_MAXSUPERCLUSTERS,
1408                               HAMMER_SCL_MAXCLUSTERS, HAMMER_VOL_METAELMS_2LYR);
1409         hammer_alist_template(&Supercl_alist_config, HAMMER_VOL_MAXCLUSTERS,
1410                               1, HAMMER_SUPERCL_METAELMS);
1411         hammer_alist_template(&Clu_master_alist_config, HAMMER_CLU_MAXBUFFERS,
1412                               1, HAMMER_CLU_MASTER_METAELMS);
1413         hammer_alist_template(&Clu_slave_alist_config, HAMMER_CLU_MAXBUFFERS,
1414                               HAMMER_FSBUF_MAXBLKS, HAMMER_CLU_SLAVE_METAELMS);
1415
1416         config = &Vol_super_alist_config;
1417         config->bl_radix_init = super_alist_init;
1418         config->bl_radix_destroy = super_alist_destroy;
1419         config->bl_radix_alloc_fwd = super_alist_alloc_fwd;
1420         config->bl_radix_alloc_rev = super_alist_alloc_rev;
1421         config->bl_radix_free = super_alist_free;
1422         config->bl_radix_print = super_alist_print;
1423
1424         config = &Clu_slave_alist_config;
1425         config->bl_radix_init = buffer_alist_init;
1426         config->bl_radix_destroy = buffer_alist_destroy;
1427         config->bl_radix_alloc_fwd = buffer_alist_alloc_fwd;
1428         config->bl_radix_alloc_rev = buffer_alist_alloc_rev;
1429         config->bl_radix_free = buffer_alist_free;
1430         config->bl_radix_print = buffer_alist_print;
1431 }
1432
1433