sys/vfs/hammer2/hammer2_chain.c

   1 /*
   2  * Copyright (c) 2011-2013 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@dragonflybsd.org>
   6  * by Venkatesh Srinivas <vsrinivas@dragonflybsd.org>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  * 3. Neither the name of The DragonFly Project nor the names of its
  19  *    contributors may be used to endorse or promote products derived
  20  *    from this software without specific, prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  26  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  30  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  31  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  32  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35 /*
  36  * This subsystem implements most of the core support functions for
  37  * the hammer2_chain and hammer2_chain_core structures.
  38  *
  39  * Chains represent the filesystem media topology in-memory.  Any given
  40  * chain can represent an inode, indirect block, data, or other types
  41  * of blocks.
  42  *
  43  * This module provides APIs for direct and indirect block searches,
  44  * iterations, recursions, creation, deletion, replication, and snapshot
  45  * views (used by the flush and snapshot code).
  46  *
  47  * Generally speaking any modification made to a chain must propagate all
  48  * the way back to the volume header, issuing copy-on-write updates to the
  49  * blockref tables all the way up.  Any chain except the volume header itself
  50  * can be flushed to disk at any time, in any order.  None of it matters
  51  * until we get to the point where we want to synchronize the volume header
  52  * (see the flush code).
  53  *
  54  * The chain structure supports snapshot views in time, which are primarily
  55  * used until the related data and meta-data is flushed to allow the
  56  * filesystem to make snapshots without requiring it to first flush,
  57  * and to allow the filesystem flush and modify the filesystem concurrently
  58  * with minimal or no stalls.
  59  */
  60 #include <sys/cdefs.h>
  61 #include <sys/param.h>
  62 #include <sys/systm.h>
  63 #include <sys/types.h>
  64 #include <sys/lock.h>
  65 #include <sys/kern_syscall.h>
  66 #include <sys/uuid.h>
  67
  68 #include "hammer2.h"
  69
  70 static int hammer2_indirect_optimize;   /* XXX SYSCTL */
  71
  72 static hammer2_chain_t *hammer2_chain_create_indirect(
  73                 hammer2_trans_t *trans, hammer2_chain_t *parent,
  74                 hammer2_key_t key, int keybits, int for_type, int *errorp);
  75 static void adjreadcounter(hammer2_blockref_t *bref, size_t bytes);
  76
  77 /*
  78  * We use a red-black tree to guarantee safe lookups under shared locks.
  79  *
  80  * Chains can be overloaded onto the same index, creating a different
  81  * view of a blockref table based on a transaction id.  The RBTREE
  82  * deconflicts the view by sub-sorting on delete_tid.
  83  *
  84  * NOTE: Any 'current' chain which is not yet deleted will have a
  85  *       delete_tid of HAMMER2_MAX_TID (0xFFF....FFFLLU).
  86  */
  87 RB_GENERATE(hammer2_chain_tree, hammer2_chain, rbnode, hammer2_chain_cmp);
  88
  89 int
  90 hammer2_chain_cmp(hammer2_chain_t *chain1, hammer2_chain_t *chain2)
  91 {
  92         if (chain1->index < chain2->index)
  93                 return(-1);
  94         if (chain1->index > chain2->index)
  95                 return(1);
  96         if (chain1->delete_tid < chain2->delete_tid)
  97                 return(-1);
  98         if (chain1->delete_tid > chain2->delete_tid)
  99                 return(1);
 100         return(0);
 101 }
 102
 103 static __inline
 104 int
 105 hammer2_isclusterable(hammer2_chain_t *chain)
 106 {
 107         if (hammer2_cluster_enable) {
 108                 if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT ||
 109                     chain->bref.type == HAMMER2_BREF_TYPE_INODE ||
 110                     chain->bref.type == HAMMER2_BREF_TYPE_DATA) {
 111                         return(1);
 112                 }
 113         }
 114         return(0);
 115 }
 116
 117 /*
 118  * Recursively set the SUBMODIFIED flag up to the root starting at chain's
 119  * parent.  SUBMODIFIED is not set in chain itself.
 120  *
 121  * This function only operates on current-time transactions and is not
 122  * used during flushes.  Instead, the flush code manages the flag itself.
 123  */
 124 void
 125 hammer2_chain_setsubmod(hammer2_trans_t *trans, hammer2_chain_t *chain)
 126 {
 127         hammer2_chain_core_t *above;
 128
 129         if (trans->flags & HAMMER2_TRANS_ISFLUSH)
 130                 return;
 131         while ((above = chain->above) != NULL) {
 132                 spin_lock(&above->cst.spin);
 133                 chain = above->first_parent;
 134                 while (hammer2_chain_refactor_test(chain, 1))
 135                         chain = chain->next_parent;
 136                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_SUBMODIFIED);
 137                 spin_unlock(&above->cst.spin);
 138         }
 139 }
 140
 141 /*
 142  * Allocate a new disconnected chain element representing the specified
 143  * bref.  chain->refs is set to 1 and the passed bref is copied to
 144  * chain->bref.  chain->bytes is derived from the bref.
 145  *
 146  * chain->core is NOT allocated and the media data and bp pointers are left
 147  * NULL.  The caller must call chain_core_alloc() to allocate or associate
 148  * a core with the chain.
 149  *
 150  * NOTE: Returns a referenced but unlocked (because there is no core) chain.
 151  */
 152 hammer2_chain_t *
 153 hammer2_chain_alloc(hammer2_mount_t *hmp, hammer2_trans_t *trans,
 154                     hammer2_blockref_t *bref)
 155 {
 156         hammer2_chain_t *chain;
 157         u_int bytes = 1U << (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
 158
 159         /*
 160          * Construct the appropriate system structure.
 161          */
 162         switch(bref->type) {
 163         case HAMMER2_BREF_TYPE_INODE:
 164         case HAMMER2_BREF_TYPE_INDIRECT:
 165         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 166         case HAMMER2_BREF_TYPE_DATA:
 167         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 168                 chain = kmalloc(sizeof(*chain), hmp->mchain, M_WAITOK | M_ZERO);
 169                 break;
 170         case HAMMER2_BREF_TYPE_VOLUME:
 171         case HAMMER2_BREF_TYPE_FREEMAP:
 172                 chain = NULL;
 173                 panic("hammer2_chain_alloc volume type illegal for op");
 174         default:
 175                 chain = NULL;
 176                 panic("hammer2_chain_alloc: unrecognized blockref type: %d",
 177                       bref->type);
 178         }
 179
 180         chain->hmp = hmp;
 181         chain->bref = *bref;
 182         chain->index = -1;              /* not yet assigned */
 183         chain->bytes = bytes;
 184         chain->refs = 1;
 185         chain->flags = HAMMER2_CHAIN_ALLOCATED;
 186         chain->delete_tid = HAMMER2_MAX_TID;
 187         if (trans)
 188                 chain->modify_tid = trans->sync_tid;
 189
 190         return (chain);
 191 }
 192
 193 /*
 194  * Associate an existing core with the chain or allocate a new core.
 195  *
 196  * The core is not locked.  No additional refs on the chain are made.
 197  */
 198 void
 199 hammer2_chain_core_alloc(hammer2_chain_t *chain, hammer2_chain_core_t *core)
 200 {
 201         hammer2_chain_t **scanp;
 202
 203         KKASSERT(chain->core == NULL);
 204         KKASSERT(chain->next_parent == NULL);
 205
 206         if (core == NULL) {
 207                 core = kmalloc(sizeof(*core), chain->hmp->mchain,
 208                                M_WAITOK | M_ZERO);
 209                 RB_INIT(&core->rbtree);
 210                 core->sharecnt = 1;
 211                 chain->core = core;
 212                 ccms_cst_init(&core->cst, chain);
 213                 core->first_parent = chain;
 214         } else {
 215                 atomic_add_int(&core->sharecnt, 1);
 216                 chain->core = core;
 217                 spin_lock(&core->cst.spin);
 218                 if (core->first_parent == NULL) {
 219                         core->first_parent = chain;
 220                 } else {
 221                         scanp = &core->first_parent;
 222                         while (*scanp)
 223                                 scanp = &(*scanp)->next_parent;
 224                         *scanp = chain;
 225                         hammer2_chain_ref(chain);       /* next_parent link */
 226                 }
 227                 spin_unlock(&core->cst.spin);
 228         }
 229 }
 230
 231 /*
 232  * Add a reference to a chain element, preventing its destruction.
 233  */
 234 void
 235 hammer2_chain_ref(hammer2_chain_t *chain)
 236 {
 237         atomic_add_int(&chain->refs, 1);
 238 }
 239
 240 /*
 241  * Drop the caller's reference to the chain.  When the ref count drops to
 242  * zero this function will disassociate the chain from its parent and
 243  * deallocate it, then recursely drop the parent using the implied ref
 244  * from the chain's chain->parent.
 245  *
 246  * WARNING! Just because we are able to deallocate a chain doesn't mean
 247  *          that chain->core->rbtree is empty.  There can still be a sharecnt
 248  *          on chain->core and RBTREE entries that refer to different parents.
 249  */
 250 static hammer2_chain_t *hammer2_chain_lastdrop(hammer2_chain_t *chain);
 251
 252 void
 253 hammer2_chain_drop(hammer2_chain_t *chain)
 254 {
 255         u_int refs;
 256         u_int need = 0;
 257
 258 #if 1
 259         if (chain->flags & HAMMER2_CHAIN_MOVED)
 260                 ++need;
 261         if (chain->flags & HAMMER2_CHAIN_MODIFIED)
 262                 ++need;
 263         KKASSERT(chain->refs > need);
 264 #endif
 265
 266         while (chain) {
 267                 refs = chain->refs;
 268                 cpu_ccfence();
 269                 KKASSERT(refs > 0);
 270
 271                 if (refs == 1) {
 272                         chain = hammer2_chain_lastdrop(chain);
 273                 } else {
 274                         if (atomic_cmpset_int(&chain->refs, refs, refs - 1))
 275                                 break;
 276                         /* retry the same chain */
 277                 }
 278         }
 279 }
 280
 281 /*
 282  * Safe handling of the 1->0 transition on chain.  Returns a chain for
 283  * recursive drop or NULL, possibly returning the same chain of the atomic
 284  * op fails.
 285  *
 286  * The cst spinlock is allowed nest child-to-parent (not parent-to-child).
 287  */
 288 static
 289 hammer2_chain_t *
 290 hammer2_chain_lastdrop(hammer2_chain_t *chain)
 291 {
 292         hammer2_mount_t *hmp;
 293         hammer2_chain_core_t *above;
 294         hammer2_chain_core_t *core;
 295         hammer2_chain_t *rdrop1;
 296         hammer2_chain_t *rdrop2;
 297
 298         /*
 299          * Spinlock the core and check to see if it is empty.  If it is
 300          * not empty we leave chain intact with refs == 0.
 301          */
 302         if ((core = chain->core) != NULL) {
 303                 spin_lock(&core->cst.spin);
 304                 if (RB_ROOT(&core->rbtree)) {
 305                         if (atomic_cmpset_int(&chain->refs, 1, 0)) {
 306                                 /* 1->0 transition successful */
 307                                 spin_unlock(&core->cst.spin);
 308                                 return(NULL);
 309                         } else {
 310                                 /* 1->0 transition failed, retry */
 311                                 spin_unlock(&core->cst.spin);
 312                                 return(chain);
 313                         }
 314                 }
 315         }
 316
 317         hmp = chain->hmp;
 318         rdrop1 = NULL;
 319         rdrop2 = NULL;
 320
 321         /*
 322          * Spinlock the parent and try to drop the last ref.  On success
 323          * remove chain from its parent.
 324          */
 325         if ((above = chain->above) != NULL) {
 326                 spin_lock(&above->cst.spin);
 327                 if (!atomic_cmpset_int(&chain->refs, 1, 0)) {
 328                         /* 1->0 transition failed */
 329                         spin_unlock(&above->cst.spin);
 330                         if (core)
 331                                 spin_unlock(&core->cst.spin);
 332                         return(chain);
 333                         /* stop */
 334                 }
 335
 336                 /*
 337                  * 1->0 transition successful
 338                  */
 339                 KKASSERT(chain->flags & HAMMER2_CHAIN_ONRBTREE);
 340                 RB_REMOVE(hammer2_chain_tree, &above->rbtree, chain);
 341                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_ONRBTREE);
 342                 chain->above = NULL;
 343
 344                 /*
 345                  * Calculate a chain to return for a recursive drop.
 346                  *
 347                  * XXX this needs help, we have a potential deep-recursion
 348                  * problem which we try to address but sometimes we wind up
 349                  * with two elements that have to be dropped.
 350                  *
 351                  * If the chain has an associated core with refs at 0
 352                  * the chain must be the first in the core's linked list
 353                  * by definition, and we will recursively drop the ref
 354                  * implied by the chain->next_parent field.
 355                  *
 356                  * Otherwise if the rbtree containing chain is empty we try
 357                  * to recursively drop our parent (only the first one could
 358                  * possibly have refs == 0 since the rest are linked via
 359                  * next_parent).
 360                  *
 361                  * Otherwise we try to recursively drop a sibling.
 362                  */
 363                 if (chain->next_parent) {
 364                         KKASSERT(core != NULL);
 365                         rdrop1 = chain->next_parent;
 366                 }
 367                 if (RB_EMPTY(&above->rbtree)) {
 368                         rdrop2 = above->first_parent;
 369                         if (rdrop2 == NULL || rdrop2->refs ||
 370                             atomic_cmpset_int(&rdrop2->refs, 0, 1) == 0) {
 371                                 rdrop2 = NULL;
 372                         }
 373                 } else {
 374                         rdrop2 = RB_ROOT(&above->rbtree);
 375                         if (atomic_cmpset_int(&rdrop2->refs, 0, 1) == 0)
 376                                 rdrop2 = NULL;
 377                 }
 378                 spin_unlock(&above->cst.spin);
 379                 above = NULL;   /* safety */
 380         } else {
 381                 if (chain->next_parent) {
 382                         KKASSERT(core != NULL);
 383                         rdrop1 = chain->next_parent;
 384                 }
 385         }
 386
 387         /*
 388          * We still have the core spinlock (if core is non-NULL).  The
 389          * above spinlock is gone.
 390          */
 391         if (core) {
 392                 KKASSERT(core->first_parent == chain);
 393                 if (chain->next_parent) {
 394                         /* parent should already be set */
 395                         KKASSERT(rdrop1 == chain->next_parent);
 396                 }
 397                 core->first_parent = chain->next_parent;
 398                 chain->next_parent = NULL;
 399                 chain->core = NULL;
 400
 401                 if (atomic_fetchadd_int(&core->sharecnt, -1) == 1) {
 402                         /*
 403                          * On the 1->0 transition of core we can destroy
 404                          * it.
 405                          */
 406                         spin_unlock(&core->cst.spin);
 407                         KKASSERT(core->cst.count == 0);
 408                         KKASSERT(core->cst.upgrade == 0);
 409                         kfree(core, hmp->mchain);
 410                 } else {
 411                         spin_unlock(&core->cst.spin);
 412                 }
 413                 core = NULL;    /* safety */
 414         }
 415
 416         /*
 417          * All spin locks are gone, finish freeing stuff.
 418          */
 419         KKASSERT((chain->flags & (HAMMER2_CHAIN_MOVED |
 420                                   HAMMER2_CHAIN_MODIFIED)) == 0);
 421
 422         switch(chain->bref.type) {
 423         case HAMMER2_BREF_TYPE_VOLUME:
 424         case HAMMER2_BREF_TYPE_FREEMAP:
 425                 chain->data = NULL;
 426                 break;
 427         case HAMMER2_BREF_TYPE_INODE:
 428                 if (chain->data) {
 429                         kfree(chain->data, hmp->mchain);
 430                         chain->data = NULL;
 431                 }
 432                 break;
 433         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 434                 if (chain->data) {
 435                         kfree(chain->data, hmp->mchain);
 436                         chain->data = NULL;
 437                 }
 438                 break;
 439         default:
 440                 KKASSERT(chain->data == NULL);
 441                 break;
 442         }
 443
 444         KKASSERT(chain->bp == NULL);
 445         chain->hmp = NULL;
 446
 447         if (chain->flags & HAMMER2_CHAIN_ALLOCATED) {
 448                 chain->flags &= ~HAMMER2_CHAIN_ALLOCATED;
 449                 kfree(chain, hmp->mchain);
 450         }
 451         if (rdrop1 && rdrop2) {
 452                 hammer2_chain_drop(rdrop1);
 453                 return(rdrop2);
 454         } else if (rdrop1)
 455                 return(rdrop1);
 456         else
 457                 return(rdrop2);
 458 }
 459
 460 /*
 461  * Ref and lock a chain element, acquiring its data with I/O if necessary,
 462  * and specify how you would like the data to be resolved.
 463  *
 464  * Returns 0 on success or an error code if the data could not be acquired.
 465  * The chain element is locked on return regardless of whether an error
 466  * occurred or not.
 467  *
 468  * The lock is allowed to recurse, multiple locking ops will aggregate
 469  * the requested resolve types.  Once data is assigned it will not be
 470  * removed until the last unlock.
 471  *
 472  * HAMMER2_RESOLVE_NEVER - Do not resolve the data element.
 473  *                         (typically used to avoid device/logical buffer
 474  *                          aliasing for data)
 475  *
 476  * HAMMER2_RESOLVE_MAYBE - Do not resolve data elements for chains in
 477  *                         the INITIAL-create state (indirect blocks only).
 478  *
 479  *                         Do not resolve data elements for DATA chains.
 480  *                         (typically used to avoid device/logical buffer
 481  *                          aliasing for data)
 482  *
 483  * HAMMER2_RESOLVE_ALWAYS- Always resolve the data element.
 484  *
 485  * HAMMER2_RESOLVE_SHARED- (flag) The chain is locked shared, otherwise
 486  *                         it will be locked exclusive.
 487  *
 488  * NOTE: Embedded elements (volume header, inodes) are always resolved
 489  *       regardless.
 490  *
 491  * NOTE: Specifying HAMMER2_RESOLVE_ALWAYS on a newly-created non-embedded
 492  *       element will instantiate and zero its buffer, and flush it on
 493  *       release.
 494  *
 495  * NOTE: (data) elements are normally locked RESOLVE_NEVER or RESOLVE_MAYBE
 496  *       so as not to instantiate a device buffer, which could alias against
 497  *       a logical file buffer.  However, if ALWAYS is specified the
 498  *       device buffer will be instantiated anyway.
 499  *
 500  * WARNING! If data must be fetched a shared lock will temporarily be
 501  *          upgraded to exclusive.  However, a deadlock can occur if
 502  *          the caller owns more than one shared lock.
 503  */
 504 int
 505 hammer2_chain_lock(hammer2_chain_t *chain, int how)
 506 {
 507         hammer2_mount_t *hmp;
 508         hammer2_chain_core_t *core;
 509         hammer2_blockref_t *bref;
 510         hammer2_off_t pbase;
 511         hammer2_off_t pmask;
 512         hammer2_off_t peof;
 513         ccms_state_t ostate;
 514         size_t boff;
 515         size_t psize;
 516         int error;
 517         char *bdata;
 518
 519         /*
 520          * Ref and lock the element.  Recursive locks are allowed.
 521          */
 522         if ((how & HAMMER2_RESOLVE_NOREF) == 0)
 523                 hammer2_chain_ref(chain);
 524         atomic_add_int(&chain->lockcnt, 1);
 525
 526         hmp = chain->hmp;
 527         KKASSERT(hmp != NULL);
 528
 529         /*
 530          * Get the appropriate lock.
 531          */
 532         core = chain->core;
 533         if (how & HAMMER2_RESOLVE_SHARED)
 534                 ccms_thread_lock(&core->cst, CCMS_STATE_SHARED);
 535         else
 536                 ccms_thread_lock(&core->cst, CCMS_STATE_EXCLUSIVE);
 537
 538         /*
 539          * If we already have a valid data pointer no further action is
 540          * necessary.
 541          */
 542         if (chain->data)
 543                 return (0);
 544
 545         /*
 546          * Do we have to resolve the data?
 547          */
 548         switch(how & HAMMER2_RESOLVE_MASK) {
 549         case HAMMER2_RESOLVE_NEVER:
 550                 return(0);
 551         case HAMMER2_RESOLVE_MAYBE:
 552                 if (chain->flags & HAMMER2_CHAIN_INITIAL)
 553                         return(0);
 554                 if (chain->bref.type == HAMMER2_BREF_TYPE_DATA)
 555                         return(0);
 556 #if 0
 557                 if (chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE)
 558                         return(0);
 559 #endif
 560                 if (chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF)
 561                         return(0);
 562                 /* fall through */
 563         case HAMMER2_RESOLVE_ALWAYS:
 564                 break;
 565         }
 566
 567         /*
 568          * Upgrade to an exclusive lock so we can safely manipulate the
 569          * buffer cache.  If another thread got to it before us we
 570          * can just return.
 571          */
 572         ostate = ccms_thread_lock_upgrade(&core->cst);
 573         if (chain->data) {
 574                 ccms_thread_lock_downgrade(&core->cst, ostate);
 575                 return (0);
 576         }
 577
 578         /*
 579          * We must resolve to a device buffer, either by issuing I/O or
 580          * by creating a zero-fill element.  We do not mark the buffer
 581          * dirty when creating a zero-fill element (the hammer2_chain_modify()
 582          * API must still be used to do that).
 583          *
 584          * The device buffer is variable-sized in powers of 2 down
 585          * to HAMMER2_MIN_ALLOC (typically 1K).  A 64K physical storage
 586          * chunk always contains buffers of the same size. (XXX)
 587          *
 588          * The minimum physical IO size may be larger than the variable
 589          * block size.
 590          */
 591         bref = &chain->bref;
 592
 593         psize = hammer2_devblksize(chain->bytes);
 594         pmask = (hammer2_off_t)psize - 1;
 595         pbase = bref->data_off & ~pmask;
 596         boff = bref->data_off & (HAMMER2_OFF_MASK & pmask);
 597         KKASSERT(pbase != 0);
 598         peof = (pbase + HAMMER2_SEGMASK64) & ~HAMMER2_SEGMASK64;
 599
 600         /*
 601          * The getblk() optimization can only be used on newly created
 602          * elements if the physical block size matches the request.
 603          */
 604         if ((chain->flags & HAMMER2_CHAIN_INITIAL) &&
 605             chain->bytes == psize) {
 606                 chain->bp = getblk(hmp->devvp, pbase, psize, 0, 0);
 607                 error = 0;
 608         } else if (hammer2_isclusterable(chain)) {
 609                 error = cluster_read(hmp->devvp, peof, pbase, psize,
 610                                      psize, HAMMER2_PBUFSIZE*4,
 611                                      &chain->bp);
 612                 adjreadcounter(&chain->bref, chain->bytes);
 613         } else {
 614                 error = bread(hmp->devvp, pbase, psize, &chain->bp);
 615                 adjreadcounter(&chain->bref, chain->bytes);
 616         }
 617
 618         if (error) {
 619                 kprintf("hammer2_chain_get: I/O error %016jx: %d\n",
 620                         (intmax_t)pbase, error);
 621                 bqrelse(chain->bp);
 622                 chain->bp = NULL;
 623                 ccms_thread_lock_downgrade(&core->cst, ostate);
 624                 return (error);
 625         }
 626
 627         /*
 628          * Zero the data area if the chain is in the INITIAL-create state.
 629          * Mark the buffer for bdwrite().  This clears the INITIAL state
 630          * but does not mark the chain modified.
 631          */
 632         bdata = (char *)chain->bp->b_data + boff;
 633         if (chain->flags & HAMMER2_CHAIN_INITIAL) {
 634                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_INITIAL);
 635                 bzero(bdata, chain->bytes);
 636                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 637         }
 638
 639         /*
 640          * Setup the data pointer, either pointing it to an embedded data
 641          * structure and copying the data from the buffer, or pointing it
 642          * into the buffer.
 643          *
 644          * The buffer is not retained when copying to an embedded data
 645          * structure in order to avoid potential deadlocks or recursions
 646          * on the same physical buffer.
 647          */
 648         switch (bref->type) {
 649         case HAMMER2_BREF_TYPE_VOLUME:
 650         case HAMMER2_BREF_TYPE_FREEMAP:
 651                 /*
 652                  * Copy data from bp to embedded buffer
 653                  */
 654                 panic("hammer2_chain_lock: called on unresolved volume header");
 655 #if 0
 656                 /* NOT YET */
 657                 KKASSERT(pbase == 0);
 658                 KKASSERT(chain->bytes == HAMMER2_PBUFSIZE);
 659                 bcopy(bdata, &hmp->voldata, chain->bytes);
 660                 chain->data = (void *)&hmp->voldata;
 661                 bqrelse(chain->bp);
 662                 chain->bp = NULL;
 663 #endif
 664                 break;
 665         case HAMMER2_BREF_TYPE_INODE:
 666                 /*
 667                  * Copy data from bp to embedded buffer, do not retain the
 668                  * device buffer.
 669                  */
 670                 KKASSERT(chain->bytes == sizeof(chain->data->ipdata));
 671                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_EMBEDDED);
 672                 chain->data = kmalloc(sizeof(chain->data->ipdata),
 673                                       hmp->mchain, M_WAITOK | M_ZERO);
 674                 bcopy(bdata, &chain->data->ipdata, chain->bytes);
 675                 bqrelse(chain->bp);
 676                 chain->bp = NULL;
 677                 break;
 678         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 679                 KKASSERT(chain->bytes == sizeof(chain->data->bmdata));
 680                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_EMBEDDED);
 681                 chain->data = kmalloc(sizeof(chain->data->bmdata),
 682                                       hmp->mchain, M_WAITOK | M_ZERO);
 683                 bcopy(bdata, &chain->data->bmdata, chain->bytes);
 684                 bqrelse(chain->bp);
 685                 chain->bp = NULL;
 686                 break;
 687         case HAMMER2_BREF_TYPE_INDIRECT:
 688         case HAMMER2_BREF_TYPE_DATA:
 689         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 690         default:
 691                 /*
 692                  * Point data at the device buffer and leave bp intact.
 693                  */
 694                 chain->data = (void *)bdata;
 695                 break;
 696         }
 697
 698         /*
 699          * Make sure the bp is not specifically owned by this thread before
 700          * restoring to a possibly shared lock, so another hammer2 thread
 701          * can release it.
 702          */
 703         if (chain->bp)
 704                 BUF_KERNPROC(chain->bp);
 705         ccms_thread_lock_downgrade(&core->cst, ostate);
 706         return (0);
 707 }
 708
 709 /*
 710  * Asynchronously read the device buffer (dbp) and execute the specified
 711  * callback.  The caller should pass-in a locked chain (shared lock is ok).
 712  * The function is responsible for unlocking the chain and for disposing
 713  * of dbp.
 714  *
 715  * NOTE!  A NULL dbp (but non-NULL data) will be passed to the function
 716  *        if the dbp is integrated into the chain, because we do not want
 717  *        the caller to dispose of dbp in that situation.
 718  */
 719 static void hammer2_chain_load_async_callback(struct bio *bio);
 720
 721 void
 722 hammer2_chain_load_async(hammer2_chain_t *chain,
 723         void (*func)(hammer2_chain_t *, struct buf *, char *, void *),
 724         void *arg)
 725 {
 726         hammer2_cbinfo_t *cbinfo;
 727         hammer2_mount_t *hmp;
 728         hammer2_blockref_t *bref;
 729         hammer2_off_t pbase;
 730         hammer2_off_t pmask;
 731         hammer2_off_t peof;
 732         struct buf *dbp;
 733         size_t boff;
 734         size_t psize;
 735         char *bdata;
 736
 737         if (chain->data) {
 738                 func(chain, NULL, (char *)chain->data, arg);
 739                 return;
 740         }
 741
 742         /*
 743          * We must resolve to a device buffer, either by issuing I/O or
 744          * by creating a zero-fill element.  We do not mark the buffer
 745          * dirty when creating a zero-fill element (the hammer2_chain_modify()
 746          * API must still be used to do that).
 747          *
 748          * The device buffer is variable-sized in powers of 2 down
 749          * to HAMMER2_MIN_ALLOC (typically 1K).  A 64K physical storage
 750          * chunk always contains buffers of the same size. (XXX)
 751          *
 752          * The minimum physical IO size may be larger than the variable
 753          * block size.
 754          */
 755         bref = &chain->bref;
 756
 757         psize = hammer2_devblksize(chain->bytes);
 758         pmask = (hammer2_off_t)psize - 1;
 759         pbase = bref->data_off & ~pmask;
 760         boff = bref->data_off & (HAMMER2_OFF_MASK & pmask);
 761         KKASSERT(pbase != 0);
 762         peof = (pbase + HAMMER2_SEGMASK64) & ~HAMMER2_SEGMASK64;
 763
 764         hmp = chain->hmp;
 765
 766         /*
 767          * The getblk() optimization can only be used on newly created
 768          * elements if the physical block size matches the request.
 769          */
 770         if ((chain->flags & HAMMER2_CHAIN_INITIAL) &&
 771             chain->bytes == psize) {
 772                 dbp = getblk(hmp->devvp, pbase, psize, 0, 0);
 773                 /*atomic_clear_int(&chain->flags, HAMMER2_CHAIN_INITIAL);*/
 774                 bdata = (char *)dbp->b_data + boff;
 775                 bzero(bdata, chain->bytes);
 776                 /*atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);*/
 777                 func(chain, dbp, bdata, arg);
 778                 return;
 779         }
 780
 781         adjreadcounter(&chain->bref, chain->bytes);
 782         cbinfo = kmalloc(sizeof(*cbinfo), hmp->mchain, M_INTWAIT | M_ZERO);
 783         cbinfo->chain = chain;
 784         cbinfo->func = func;
 785         cbinfo->arg = arg;
 786         cbinfo->boff = boff;
 787
 788         cluster_readcb(hmp->devvp, peof, pbase, psize,
 789                 HAMMER2_PBUFSIZE*4, HAMMER2_PBUFSIZE*4,
 790                 hammer2_chain_load_async_callback, cbinfo);
 791 }
 792
 793 static void
 794 hammer2_chain_load_async_callback(struct bio *bio)
 795 {
 796         hammer2_cbinfo_t *cbinfo;
 797         hammer2_mount_t *hmp;
 798         struct buf *dbp;
 799         char *data;
 800
 801         /*
 802          * Nobody is waiting for bio/dbp to complete, we are
 803          * responsible for handling the biowait() equivalent
 804          * on dbp which means clearing BIO_DONE and BIO_SYNC
 805          * and calling bpdone() if it hasn't already been called
 806          * to restore any covered holes in the buffer's backing
 807          * store.
 808          */
 809         dbp = bio->bio_buf;
 810         if ((bio->bio_flags & BIO_DONE) == 0)
 811                 bpdone(dbp, 0);
 812         bio->bio_flags &= ~(BIO_DONE | BIO_SYNC);
 813
 814         /*
 815          * Extract the auxillary info and issue the callback.
 816          * Finish up with the dbp after it returns.
 817          */
 818         cbinfo = bio->bio_caller_info1.ptr;
 819         /*ccms_thread_lock_setown(cbinfo->chain->core);*/
 820         data = dbp->b_data + cbinfo->boff;
 821         hmp = cbinfo->chain->hmp;
 822
 823         cbinfo = bio->bio_caller_info1.ptr;
 824         cbinfo->func(cbinfo->chain, dbp, data, cbinfo->arg);
 825         /* cbinfo->chain is stale now */
 826         bqrelse(dbp);
 827         kfree(cbinfo, hmp->mchain);
 828 }
 829
 830 /*
 831  * Unlock and deref a chain element.
 832  *
 833  * On the last lock release any non-embedded data (chain->bp) will be
 834  * retired.
 835  */
 836 void
 837 hammer2_chain_unlock(hammer2_chain_t *chain)
 838 {
 839         hammer2_chain_core_t *core = chain->core;
 840         ccms_state_t ostate;
 841         long *counterp;
 842         u_int lockcnt;
 843
 844         /*
 845          * The core->cst lock can be shared across several chains so we
 846          * need to track the per-chain lockcnt separately.
 847          *
 848          * If multiple locks are present (or being attempted) on this
 849          * particular chain we can just unlock, drop refs, and return.
 850          *
 851          * Otherwise fall-through on the 1->0 transition.
 852          */
 853         for (;;) {
 854                 lockcnt = chain->lockcnt;
 855                 KKASSERT(lockcnt > 0);
 856                 cpu_ccfence();
 857                 if (lockcnt > 1) {
 858                         if (atomic_cmpset_int(&chain->lockcnt,
 859                                               lockcnt, lockcnt - 1)) {
 860                                 ccms_thread_unlock(&core->cst);
 861                                 hammer2_chain_drop(chain);
 862                                 return;
 863                         }
 864                 } else {
 865                         if (atomic_cmpset_int(&chain->lockcnt, 1, 0))
 866                                 break;
 867                 }
 868                 /* retry */
 869         }
 870
 871         /*
 872          * On the 1->0 transition we upgrade the core lock (if necessary)
 873          * to exclusive for terminal processing.  If after upgrading we find
 874          * that lockcnt is non-zero, another thread is racing us and will
 875          * handle the unload for us later on, so just cleanup and return
 876          * leaving the data/bp intact
 877          *
 878          * Otherwise if lockcnt is still 0 it is possible for it to become
 879          * non-zero and race, but since we hold the core->cst lock
 880          * exclusively all that will happen is that the chain will be
 881          * reloaded after we unload it.
 882          */
 883         ostate = ccms_thread_lock_upgrade(&core->cst);
 884         if (chain->lockcnt) {
 885                 ccms_thread_unlock_upgraded(&core->cst, ostate);
 886                 hammer2_chain_drop(chain);
 887                 return;
 888         }
 889
 890         /*
 891          * Shortcut the case if the data is embedded or not resolved.
 892          *
 893          * Do NOT NULL out chain->data (e.g. inode data), it might be
 894          * dirty.
 895          *
 896          * The DIRTYBP flag is non-applicable in this situation and can
 897          * be cleared to keep the flags state clean.
 898          */
 899         if (chain->bp == NULL) {
 900                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 901                 ccms_thread_unlock_upgraded(&core->cst, ostate);
 902                 hammer2_chain_drop(chain);
 903                 return;
 904         }
 905
 906         /*
 907          * Statistics
 908          */
 909         if ((chain->flags & HAMMER2_CHAIN_DIRTYBP) == 0) {
 910                 ;
 911         } else if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 912                 switch(chain->bref.type) {
 913                 case HAMMER2_BREF_TYPE_DATA:
 914                         counterp = &hammer2_ioa_file_write;
 915                         break;
 916                 case HAMMER2_BREF_TYPE_INODE:
 917                         counterp = &hammer2_ioa_meta_write;
 918                         break;
 919                 case HAMMER2_BREF_TYPE_INDIRECT:
 920                         counterp = &hammer2_ioa_indr_write;
 921                         break;
 922                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 923                 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 924                         counterp = &hammer2_ioa_fmap_write;
 925                         break;
 926                 default:
 927                         counterp = &hammer2_ioa_volu_write;
 928                         break;
 929                 }
 930                 *counterp += chain->bytes;
 931         } else {
 932                 switch(chain->bref.type) {
 933                 case HAMMER2_BREF_TYPE_DATA:
 934                         counterp = &hammer2_iod_file_write;
 935                         break;
 936                 case HAMMER2_BREF_TYPE_INODE:
 937                         counterp = &hammer2_iod_meta_write;
 938                         break;
 939                 case HAMMER2_BREF_TYPE_INDIRECT:
 940                         counterp = &hammer2_iod_indr_write;
 941                         break;
 942                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 943                 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 944                         counterp = &hammer2_iod_fmap_write;
 945                         break;
 946                 default:
 947                         counterp = &hammer2_iod_volu_write;
 948                         break;
 949                 }
 950                 *counterp += chain->bytes;
 951         }
 952
 953         /*
 954          * Clean out the bp.
 955          *
 956          * If a device buffer was used for data be sure to destroy the
 957          * buffer when we are done to avoid aliases (XXX what about the
 958          * underlying VM pages?).
 959          *
 960          * NOTE: Freemap leaf's use reserved blocks and thus no aliasing
 961          *       is possible.
 962          */
 963 #if 0
 964         /*
 965          * XXX our primary cache is now the block device, not
 966          * the logical file. don't release the buffer.
 967          */
 968         if (chain->bref.type == HAMMER2_BREF_TYPE_DATA)
 969                 chain->bp->b_flags |= B_RELBUF;
 970 #endif
 971
 972         /*
 973          * The DIRTYBP flag tracks whether we have to bdwrite() the buffer
 974          * or not.  The flag will get re-set when chain_modify() is called,
 975          * even if MODIFIED is already set, allowing the OS to retire the
 976          * buffer independent of a hammer2 flus.
 977          */
 978         chain->data = NULL;
 979         if (chain->flags & HAMMER2_CHAIN_DIRTYBP) {
 980                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 981                 if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 982                         atomic_clear_int(&chain->flags,
 983                                          HAMMER2_CHAIN_IOFLUSH);
 984                         chain->bp->b_flags |= B_RELBUF;
 985                         cluster_awrite(chain->bp);
 986                 } else {
 987                         chain->bp->b_flags |= B_CLUSTEROK;
 988                         bdwrite(chain->bp);
 989                 }
 990         } else {
 991                 if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 992                         atomic_clear_int(&chain->flags,
 993                                          HAMMER2_CHAIN_IOFLUSH);
 994                         chain->bp->b_flags |= B_RELBUF;
 995                         brelse(chain->bp);
 996                 } else {
 997                         /* bp might still be dirty */
 998                         bqrelse(chain->bp);
 999                 }
1000         }
1001         chain->bp = NULL;
1002         ccms_thread_unlock_upgraded(&core->cst, ostate);
1003         hammer2_chain_drop(chain);
1004 }
1005
1006 /*
1007  * Resize the chain's physical storage allocation in-place.  This may
1008  * replace the passed-in chain with a new chain.
1009  *
1010  * Chains can be resized smaller without reallocating the storage.
1011  * Resizing larger will reallocate the storage.
1012  *
1013  * Must be passed an exclusively locked parent and chain, returns a new
1014  * exclusively locked chain at the same index and unlocks the old chain.
1015  * Flushes the buffer if necessary.
1016  *
1017  * This function is mostly used with DATA blocks locked RESOLVE_NEVER in order
1018  * to avoid instantiating a device buffer that conflicts with the vnode
1019  * data buffer.  That is, the passed-in bp is a logical buffer, whereas
1020  * any chain-oriented bp would be a device buffer.
1021  *
1022  * XXX flags currently ignored, uses chain->bp to detect data/no-data.
1023  * XXX return error if cannot resize.
1024  */
1025 void
1026 hammer2_chain_resize(hammer2_trans_t *trans, hammer2_inode_t *ip,
1027                      struct buf *bp,
1028                      hammer2_chain_t *parent, hammer2_chain_t **chainp,
1029                      int nradix, int flags)
1030 {
1031         hammer2_mount_t *hmp;
1032         hammer2_chain_t *chain;
1033         hammer2_off_t pbase;
1034         size_t obytes;
1035         size_t nbytes;
1036         size_t bbytes;
1037         int boff;
1038
1039         chain = *chainp;
1040         hmp = chain->hmp;
1041
1042         /*
1043          * Only data and indirect blocks can be resized for now.
1044          * (The volu root, inodes, and freemap elements use a fixed size).
1045          */
1046         KKASSERT(chain != &hmp->vchain);
1047         KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_DATA ||
1048                  chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT);
1049
1050         /*
1051          * Nothing to do if the element is already the proper size
1052          */
1053         obytes = chain->bytes;
1054         nbytes = 1U << nradix;
1055         if (obytes == nbytes)
1056                 return;
1057
1058         /*
1059          * Delete the old chain and duplicate it at the same (parent, index),
1060          * returning a new chain.  This allows the old chain to still be
1061          * used by the flush code.  Duplication occurs in-place.
1062          *
1063          * The parent does not have to be locked for the delete/duplicate call,
1064          * but is in this particular code path.
1065          *
1066          * NOTE: If we are not crossing a synchronization point the
1067          *       duplication code will simply reuse the existing chain
1068          *       structure.
1069          */
1070         hammer2_chain_delete_duplicate(trans, &chain, 0);
1071
1072         /*
1073          * Set MODIFIED and add a chain ref to prevent destruction.  Both
1074          * modified flags share the same ref.  (duplicated chains do not
1075          * start out MODIFIED unless possibly if the duplication code
1076          * decided to reuse the existing chain as-is).
1077          *
1078          * If the chain is already marked MODIFIED then we can safely
1079          * return the previous allocation to the pool without having to
1080          * worry about snapshots.  XXX check flush synchronization.
1081          */
1082         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0) {
1083                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
1084                 hammer2_chain_ref(chain);
1085         }
1086
1087         /*
1088          * Relocate the block, even if making it smaller (because different
1089          * block sizes may be in different regions).
1090          */
1091         hammer2_freemap_alloc(trans, chain->hmp, &chain->bref, nbytes);
1092         chain->bytes = nbytes;
1093         /*ip->delta_dcount += (ssize_t)(nbytes - obytes);*/ /* XXX atomic */
1094
1095         /*
1096          * The device buffer may be larger than the allocation size.
1097          */
1098         bbytes = hammer2_devblksize(chain->bytes);
1099         pbase = chain->bref.data_off & ~(hammer2_off_t)(bbytes - 1);
1100         boff = chain->bref.data_off & HAMMER2_OFF_MASK & (bbytes - 1);
1101
1102         /*
1103          * For now just support it on DATA chains (and not on indirect
1104          * blocks).
1105          */
1106         KKASSERT(chain->bp == NULL);
1107
1108         /*
1109          * Make sure the chain is marked MOVED and SUBMOD is set in the
1110          * parent(s) so the adjustments are picked up by flush.
1111          */
1112         if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
1113                 hammer2_chain_ref(chain);
1114                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
1115         }
1116         hammer2_chain_setsubmod(trans, chain);
1117         *chainp = chain;
1118 }
1119
1120 /*
1121  * Set a chain modified, making it read-write and duplicating it if necessary.
1122  * This function will assign a new physical block to the chain if necessary
1123  *
1124  * Duplication of already-modified chains is possible when the modification
1125  * crosses a flush synchronization boundary.
1126  *
1127  * Non-data blocks - The chain should be locked to at least the RESOLVE_MAYBE
1128  *                   level or the COW operation will not work.
1129  *
1130  * Data blocks     - The chain is usually locked RESOLVE_NEVER so as not to
1131  *                   run the data through the device buffers.
1132  *
1133  * This function may return a different chain than was passed, in which case
1134  * the old chain will be unlocked and the new chain will be locked.
1135  *
1136  * ip->chain may be adjusted by hammer2_chain_modify_ip().
1137  */
1138 hammer2_inode_data_t *
1139 hammer2_chain_modify_ip(hammer2_trans_t *trans, hammer2_inode_t *ip,
1140                         hammer2_chain_t **chainp, int flags)
1141 {
1142         atomic_set_int(&ip->flags, HAMMER2_INODE_MODIFIED);
1143         hammer2_chain_modify(trans, chainp, flags);
1144         if (ip->chain != *chainp)
1145                 hammer2_inode_repoint(ip, NULL, *chainp);
1146         return(&ip->chain->data->ipdata);
1147 }
1148
1149 void
1150 hammer2_chain_modify(hammer2_trans_t *trans, hammer2_chain_t **chainp,
1151                      int flags)
1152 {
1153         hammer2_mount_t *hmp;
1154         hammer2_chain_t *chain;
1155         hammer2_off_t pbase;
1156         hammer2_off_t pmask;
1157         hammer2_off_t peof;
1158         hammer2_tid_t flush_tid;
1159         struct buf *nbp;
1160         int error;
1161         int wasinitial;
1162         size_t psize;
1163         size_t boff;
1164         void *bdata;
1165
1166         /*
1167          * Data must be resolved if already assigned unless explicitly
1168          * flagged otherwise.
1169          */
1170         chain = *chainp;
1171         hmp = chain->hmp;
1172         if (chain->data == NULL && (flags & HAMMER2_MODIFY_OPTDATA) == 0 &&
1173             (chain->bref.data_off & ~HAMMER2_OFF_MASK_RADIX)) {
1174                 hammer2_chain_lock(chain, HAMMER2_RESOLVE_ALWAYS);
1175                 hammer2_chain_unlock(chain);
1176         }
1177
1178         /*
1179          * data is not optional for freemap chains (we must always be sure
1180          * to copy the data on COW storage allocations).
1181          */
1182         if (chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
1183             chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
1184                 KKASSERT((chain->flags & HAMMER2_CHAIN_INITIAL) ||
1185                          (flags & HAMMER2_MODIFY_OPTDATA) == 0);
1186         }
1187
1188         /*
1189          * If the chain is already marked MODIFIED we can usually just
1190          * return.  However, if a modified chain is modified again in
1191          * a synchronization-point-crossing manner we have to issue a
1192          * delete/duplicate on the chain to avoid flush interference.
1193          */
1194         if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
1195                 /*
1196                  * Which flush_tid do we need to check?  If the chain is
1197                  * related to the freemap we have to use the freemap flush
1198                  * tid (free_flush_tid), otherwise we use the normal filesystem
1199                  * flush tid (topo_flush_tid).  The two flush domains are
1200                  * almost completely independent of each other.
1201                  */
1202                 if (chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
1203                     chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
1204                         flush_tid = hmp->topo_flush_tid; /* XXX */
1205                         goto skipxx;    /* XXX */
1206                 } else {
1207                         flush_tid = hmp->topo_flush_tid;
1208                 }
1209
1210                 /*
1211                  * Main tests
1212                  */
1213                 if (chain->modify_tid <= flush_tid &&
1214                     trans->sync_tid > flush_tid) {
1215                         /*
1216                          * Modifications cross synchronization point,
1217                          * requires delete-duplicate.
1218                          */
1219                         KKASSERT((flags & HAMMER2_MODIFY_ASSERTNOCOPY) == 0);
1220                         hammer2_chain_delete_duplicate(trans, chainp, 0);
1221                         chain = *chainp;
1222                         /* fall through using duplicate */
1223                 }
1224 skipxx: /* XXX */
1225                 /*
1226                  * Quick return path, set DIRTYBP to ensure that
1227                  * the later retirement of bp will write it out.
1228                  *
1229                  * quick return path also needs the modify_tid
1230                  * logic.
1231                  */
1232                 if (chain->bp)
1233                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
1234                 if ((flags & HAMMER2_MODIFY_NO_MODIFY_TID) == 0)
1235                         chain->bref.modify_tid = trans->sync_tid;
1236                 chain->modify_tid = trans->sync_tid;
1237                 return;
1238         }
1239
1240         /*
1241          * modify_tid is only update for primary modifications, not for
1242          * propagated brefs.  mirror_tid will be updated regardless during
1243          * the flush, no need to set it here.
1244          */
1245         if ((flags & HAMMER2_MODIFY_NO_MODIFY_TID) == 0)
1246                 chain->bref.modify_tid = trans->sync_tid;
1247
1248         /*
1249          * Set MODIFIED and add a chain ref to prevent destruction.  Both
1250          * modified flags share the same ref.
1251          */
1252         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0) {
1253                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
1254                 hammer2_chain_ref(chain);
1255         }
1256
1257         /*
1258          * Adjust chain->modify_tid so the flusher knows when the
1259          * modification occurred.
1260          */
1261         chain->modify_tid = trans->sync_tid;
1262
1263         /*
1264          * The modification or re-modification requires an allocation and
1265          * possible COW.
1266          *
1267          * We normally always allocate new storage here.  If storage exists
1268          * and MODIFY_NOREALLOC is passed in, we do not allocate new storage.
1269          */
1270         if (chain != &hmp->vchain &&
1271             chain != &hmp->fchain &&
1272             ((chain->bref.data_off & ~HAMMER2_OFF_MASK_RADIX) == 0 ||
1273              (flags & HAMMER2_MODIFY_NOREALLOC) == 0)
1274         ) {
1275                 hammer2_freemap_alloc(trans, chain->hmp,
1276                                       &chain->bref, chain->bytes);
1277                 /* XXX failed allocation */
1278         }
1279
1280         /*
1281          * Do not COW if OPTDATA is set.  INITIAL flag remains unchanged.
1282          * (OPTDATA does not prevent [re]allocation of storage, only the
1283          * related copy-on-write op).
1284          */
1285         if (flags & HAMMER2_MODIFY_OPTDATA)
1286                 goto skip2;
1287
1288         /*
1289          * Clearing the INITIAL flag (for indirect blocks) indicates that
1290          * we've processed the uninitialized storage allocation.
1291          *
1292          * If this flag is already clear we are likely in a copy-on-write
1293          * situation but we have to be sure NOT to bzero the storage if
1294          * no data is present.
1295          */
1296         if (chain->flags & HAMMER2_CHAIN_INITIAL) {
1297                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_INITIAL);
1298                 wasinitial = 1;
1299         } else {
1300                 wasinitial = 0;
1301         }
1302
1303 #if 0
1304         /*
1305          * We currently should never instantiate a device buffer for a
1306          * file data chain.  (We definitely can for a freemap chain).
1307          *
1308          * XXX we can now do this
1309          */
1310         KKASSERT(chain->bref.type != HAMMER2_BREF_TYPE_DATA);
1311 #endif
1312
1313         /*
1314          * Instantiate data buffer and possibly execute COW operation
1315          */
1316         switch(chain->bref.type) {
1317         case HAMMER2_BREF_TYPE_VOLUME:
1318         case HAMMER2_BREF_TYPE_FREEMAP:
1319         case HAMMER2_BREF_TYPE_INODE:
1320         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
1321                 /*
1322                  * The data is embedded, no copy-on-write operation is
1323                  * needed.
1324                  */
1325                 KKASSERT(chain->bp == NULL);
1326                 break;
1327         case HAMMER2_BREF_TYPE_DATA:
1328         case HAMMER2_BREF_TYPE_INDIRECT:
1329         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1330                 /*
1331                  * Perform the copy-on-write operation
1332                  */
1333                 KKASSERT(chain != &hmp->vchain && chain != &hmp->fchain);
1334
1335                 psize = hammer2_devblksize(chain->bytes);
1336                 pmask = (hammer2_off_t)psize - 1;
1337                 pbase = chain->bref.data_off & ~pmask;
1338                 boff = chain->bref.data_off & (HAMMER2_OFF_MASK & pmask);
1339                 KKASSERT(pbase != 0);
1340                 peof = (pbase + HAMMER2_SEGMASK64) & ~HAMMER2_SEGMASK64;
1341
1342                 /*
1343                  * The getblk() optimization can only be used if the
1344                  * chain element size matches the physical block size.
1345                  */
1346                 if (chain->bp && chain->bp->b_loffset == pbase) {
1347                         nbp = chain->bp;
1348                         error = 0;
1349                 } else if (chain->bytes == psize) {
1350                         nbp = getblk(hmp->devvp, pbase, psize, 0, 0);
1351                         error = 0;
1352                 } else if (hammer2_isclusterable(chain)) {
1353                         error = cluster_read(hmp->devvp, peof, pbase, psize,
1354                                              psize, HAMMER2_PBUFSIZE*4,
1355                                              &nbp);
1356                         adjreadcounter(&chain->bref, chain->bytes);
1357                 } else {
1358                         error = bread(hmp->devvp, pbase, psize, &nbp);
1359                         adjreadcounter(&chain->bref, chain->bytes);
1360                 }
1361                 KKASSERT(error == 0);
1362                 bdata = (char *)nbp->b_data + boff;
1363
1364                 /*
1365                  * Copy or zero-fill on write depending on whether
1366                  * chain->data exists or not.  Retire the existing bp
1367                  * based on the DIRTYBP flag.  Set the DIRTYBP flag to
1368                  * indicate that retirement of nbp should use bdwrite().
1369                  */
1370                 if (chain->data) {
1371                         KKASSERT(chain->bp != NULL);
1372                         if (chain->data != bdata) {
1373                                 bcopy(chain->data, bdata, chain->bytes);
1374                         }
1375                 } else if (wasinitial) {
1376                         bzero(bdata, chain->bytes);
1377                 } else {
1378                         /*
1379                          * We have a problem.  We were asked to COW but
1380                          * we don't have any data to COW with!
1381                          */
1382                         panic("hammer2_chain_modify: having a COW %p\n",
1383                               chain);
1384                 }
1385                 if (chain->bp != nbp) {
1386                         if (chain->bp) {
1387                                 if (chain->flags & HAMMER2_CHAIN_DIRTYBP) {
1388                                         chain->bp->b_flags |= B_CLUSTEROK;
1389                                         bdwrite(chain->bp);
1390                                 } else {
1391                                         chain->bp->b_flags |= B_RELBUF;
1392                                         brelse(chain->bp);
1393                                 }
1394                         }
1395                         chain->bp = nbp;
1396                         BUF_KERNPROC(chain->bp);
1397                 }
1398                 chain->data = bdata;
1399                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
1400                 break;
1401         default:
1402                 panic("hammer2_chain_modify: illegal non-embedded type %d",
1403                       chain->bref.type);
1404                 break;
1405
1406         }
1407 skip2:
1408         hammer2_chain_setsubmod(trans, chain);
1409 }
1410
1411 /*
1412  * Mark the volume as having been modified.  This short-cut version
1413  * does not have to lock the volume's chain, which allows the ioctl
1414  * code to make adjustments to connections without deadlocking.  XXX
1415  *
1416  * No ref is made on vchain when flagging it MODIFIED.
1417  */
1418 void
1419 hammer2_modify_volume(hammer2_mount_t *hmp)
1420 {
1421         hammer2_voldata_lock(hmp);
1422         hammer2_voldata_unlock(hmp, 1);
1423 }
1424
1425 /*
1426  * Locate an in-memory chain.  The parent must be locked.  The in-memory
1427  * chain is returned with a reference and without a lock, or NULL
1428  * if not found.
1429  *
1430  * This function returns the chain at the specified index with the highest
1431  * delete_tid.  The caller must check whether the chain is flagged
1432  * CHAIN_DELETED or not.  However, because chain iterations can be removed
1433  * from memory we must ALSO check that DELETED chains are not flushed.  A
1434  * DELETED chain which has been flushed must be ignored (the caller must
1435  * check the parent's blockref array).
1436  *
1437  * NOTE: If no chain is found the caller usually must check the on-media
1438  *       array to determine if a blockref exists at the index.
1439  */
1440 struct hammer2_chain_find_info {
1441         hammer2_chain_t *best;
1442         hammer2_tid_t   delete_tid;
1443         int index;
1444 };
1445
1446 static
1447 int
1448 hammer2_chain_find_cmp(hammer2_chain_t *child, void *data)
1449 {
1450         struct hammer2_chain_find_info *info = data;
1451
1452         if (child->index < info->index)
1453                 return(-1);
1454         if (child->index > info->index)
1455                 return(1);
1456         return(0);
1457 }
1458
1459 static
1460 int
1461 hammer2_chain_find_callback(hammer2_chain_t *child, void *data)
1462 {
1463         struct hammer2_chain_find_info *info = data;
1464
1465         if (info->delete_tid < child->delete_tid) {
1466                 info->delete_tid = child->delete_tid;
1467                 info->best = child;
1468         }
1469         return(0);
1470 }
1471
1472 static
1473 hammer2_chain_t *
1474 hammer2_chain_find_locked(hammer2_chain_t *parent, int index)
1475 {
1476         struct hammer2_chain_find_info info;
1477         hammer2_chain_t *child;
1478
1479         info.index = index;
1480         info.delete_tid = 0;
1481         info.best = NULL;
1482
1483         RB_SCAN(hammer2_chain_tree, &parent->core->rbtree,
1484                 hammer2_chain_find_cmp, hammer2_chain_find_callback,
1485                 &info);
1486         child = info.best;
1487
1488         return (child);
1489 }
1490
1491 hammer2_chain_t *
1492 hammer2_chain_find(hammer2_chain_t *parent, int index)
1493 {
1494         hammer2_chain_t *child;
1495
1496         spin_lock(&parent->core->cst.spin);
1497         child = hammer2_chain_find_locked(parent, index);
1498         if (child)
1499                 hammer2_chain_ref(child);
1500         spin_unlock(&parent->core->cst.spin);
1501
1502         return (child);
1503 }
1504
1505 /*
1506  * Return a locked chain structure with all associated data acquired.
1507  * (if LOOKUP_NOLOCK is requested the returned chain is only referenced).
1508  *
1509  * Caller must hold the parent locked shared or exclusive since we may
1510  * need the parent's bref array to find our block.
1511  *
1512  * The returned child is locked as requested.  If NOLOCK, the returned
1513  * child is still at least referenced.
1514  */
1515 hammer2_chain_t *
1516 hammer2_chain_get(hammer2_chain_t *parent, int index, int flags)
1517 {
1518         hammer2_blockref_t *bref;
1519         hammer2_mount_t *hmp = parent->hmp;
1520         hammer2_chain_core_t *above = parent->core;
1521         hammer2_chain_t *chain;
1522         hammer2_chain_t dummy;
1523         int how;
1524
1525         /*
1526          * Figure out how to lock.  MAYBE can be used to optimized
1527          * the initial-create state for indirect blocks.
1528          */
1529         if (flags & HAMMER2_LOOKUP_ALWAYS)
1530                 how = HAMMER2_RESOLVE_ALWAYS;
1531         else if (flags & (HAMMER2_LOOKUP_NODATA | HAMMER2_LOOKUP_NOLOCK))
1532                 how = HAMMER2_RESOLVE_NEVER;
1533         else
1534                 how = HAMMER2_RESOLVE_MAYBE;
1535         if (flags & (HAMMER2_LOOKUP_SHARED | HAMMER2_LOOKUP_NOLOCK))
1536                 how |= HAMMER2_RESOLVE_SHARED;
1537
1538 retry:
1539         /*
1540          * First see if we have a (possibly modified) chain element cached
1541          * for this (parent, index).  Acquire the data if necessary.
1542          *
1543          * If chain->data is non-NULL the chain should already be marked
1544          * modified.
1545          */
1546         dummy.flags = 0;
1547         dummy.index = index;
1548         dummy.delete_tid = HAMMER2_MAX_TID;
1549         spin_lock(&above->cst.spin);
1550         chain = RB_FIND(hammer2_chain_tree, &above->rbtree, &dummy);
1551         if (chain) {
1552                 hammer2_chain_ref(chain);
1553                 spin_unlock(&above->cst.spin);
1554                 if ((flags & HAMMER2_LOOKUP_NOLOCK) == 0)
1555                         hammer2_chain_lock(chain, how | HAMMER2_RESOLVE_NOREF);
1556                 return(chain);
1557         }
1558         spin_unlock(&above->cst.spin);
1559
1560         /*
1561          * The parent chain must not be in the INITIAL state.
1562          */
1563         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1564                 panic("hammer2_chain_get: Missing bref(1)");
1565                 /* NOT REACHED */
1566         }
1567
1568         /*
1569          * No RBTREE entry found, lookup the bref and issue I/O (switch on
1570          * the parent's bref to determine where and how big the array is).
1571          */
1572         switch(parent->bref.type) {
1573         case HAMMER2_BREF_TYPE_INODE:
1574                 KKASSERT(index >= 0 && index < HAMMER2_SET_COUNT);
1575                 bref = &parent->data->ipdata.u.blockset.blockref[index];
1576                 break;
1577         case HAMMER2_BREF_TYPE_INDIRECT:
1578         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1579                 KKASSERT(parent->data != NULL);
1580                 KKASSERT(index >= 0 &&
1581                          index < parent->bytes / sizeof(hammer2_blockref_t));
1582                 bref = &parent->data->npdata[index];
1583                 break;
1584         case HAMMER2_BREF_TYPE_VOLUME:
1585                 KKASSERT(index >= 0 && index < HAMMER2_SET_COUNT);
1586                 bref = &hmp->voldata.sroot_blockset.blockref[index];
1587                 break;
1588         case HAMMER2_BREF_TYPE_FREEMAP:
1589                 KKASSERT(index >= 0 && index < HAMMER2_SET_COUNT);
1590                 bref = &hmp->voldata.freemap_blockset.blockref[index];
1591                 break;
1592         default:
1593                 bref = NULL;
1594                 panic("hammer2_chain_get: unrecognized blockref type: %d",
1595                       parent->bref.type);
1596         }
1597         if (bref->type == 0) {
1598                 panic("hammer2_chain_get: Missing bref(2)");
1599                 /* NOT REACHED */
1600         }
1601
1602         /*
1603          * Allocate a chain structure representing the existing media
1604          * entry.  Resulting chain has one ref and is not locked.
1605          *
1606          * The locking operation we do later will issue I/O to read it.
1607          */
1608         chain = hammer2_chain_alloc(hmp, NULL, bref);
1609         hammer2_chain_core_alloc(chain, NULL);  /* ref'd chain returned */
1610
1611         /*
1612          * Link the chain into its parent.  A spinlock is required to safely
1613          * access the RBTREE, and it is possible to collide with another
1614          * hammer2_chain_get() operation because the caller might only hold
1615          * a shared lock on the parent.
1616          */
1617         KKASSERT(parent->refs > 0);
1618         spin_lock(&above->cst.spin);
1619         chain->above = above;
1620         chain->index = index;
1621         if (RB_INSERT(hammer2_chain_tree, &above->rbtree, chain)) {
1622                 chain->above = NULL;
1623                 chain->index = -1;
1624                 spin_unlock(&above->cst.spin);
1625                 hammer2_chain_drop(chain);
1626                 goto retry;
1627         }
1628         atomic_set_int(&chain->flags, HAMMER2_CHAIN_ONRBTREE);
1629         spin_unlock(&above->cst.spin);
1630
1631         /*
1632          * Our new chain is referenced but NOT locked.  Lock the chain
1633          * below.  The locking operation also resolves its data.
1634          *
1635          * If NOLOCK is set the release will release the one-and-only lock.
1636          */
1637         if ((flags & HAMMER2_LOOKUP_NOLOCK) == 0) {
1638                 hammer2_chain_lock(chain, how); /* recusive lock */
1639                 hammer2_chain_drop(chain);      /* excess ref */
1640         }
1641         return (chain);
1642 }
1643
1644 /*
1645  * Lookup initialization/completion API
1646  */
1647 hammer2_chain_t *
1648 hammer2_chain_lookup_init(hammer2_chain_t *parent, int flags)
1649 {
1650         if (flags & HAMMER2_LOOKUP_SHARED) {
1651                 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS |
1652                                            HAMMER2_RESOLVE_SHARED);
1653         } else {
1654                 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS);
1655         }
1656         return (parent);
1657 }
1658
1659 void
1660 hammer2_chain_lookup_done(hammer2_chain_t *parent)
1661 {
1662         if (parent)
1663                 hammer2_chain_unlock(parent);
1664 }
1665
1666 static
1667 hammer2_chain_t *
1668 hammer2_chain_getparent(hammer2_chain_t **parentp, int how)
1669 {
1670         hammer2_chain_t *oparent;
1671         hammer2_chain_t *nparent;
1672         hammer2_chain_core_t *above;
1673
1674         oparent = *parentp;
1675         above = oparent->above;
1676
1677         spin_lock(&above->cst.spin);
1678         nparent = above->first_parent;
1679         while (hammer2_chain_refactor_test(nparent, 1))
1680                 nparent = nparent->next_parent;
1681         hammer2_chain_ref(nparent);     /* protect nparent, use in lock */
1682         spin_unlock(&above->cst.spin);
1683
1684         hammer2_chain_unlock(oparent);
1685         hammer2_chain_lock(nparent, how | HAMMER2_RESOLVE_NOREF);
1686         *parentp = nparent;
1687
1688         return (nparent);
1689 }
1690
1691 /*
1692  * Locate any key between key_beg and key_end inclusive.  (*parentp)
1693  * typically points to an inode but can also point to a related indirect
1694  * block and this function will recurse upwards and find the inode again.
1695  *
1696  * WARNING!  THIS DOES NOT RETURN KEYS IN LOGICAL KEY ORDER!  ANY KEY
1697  *           WITHIN THE RANGE CAN BE RETURNED.  HOWEVER, AN ITERATION
1698  *           WHICH PICKS UP WHERE WE LEFT OFF WILL CONTINUE THE SCAN
1699  *           AND ALL IN-RANGE KEYS WILL EVENTUALLY BE RETURNED (NOT
1700  *           NECESSARILY IN ORDER).
1701  *
1702  * (*parentp) must be exclusively locked and referenced and can be an inode
1703  * or an existing indirect block within the inode.
1704  *
1705  * On return (*parentp) will be modified to point at the deepest parent chain
1706  * element encountered during the search, as a helper for an insertion or
1707  * deletion.   The new (*parentp) will be locked and referenced and the old
1708  * will be unlocked and dereferenced (no change if they are both the same).
1709  *
1710  * The matching chain will be returned exclusively locked.  If NOLOCK is
1711  * requested the chain will be returned only referenced.
1712  *
1713  * NULL is returned if no match was found, but (*parentp) will still
1714  * potentially be adjusted.
1715  *
1716  * This function will also recurse up the chain if the key is not within the
1717  * current parent's range.  (*parentp) can never be set to NULL.  An iteration
1718  * can simply allow (*parentp) to float inside the loop.
1719  *
1720  * NOTE!  chain->data is not always resolved.  By default it will not be
1721  *        resolved for BREF_TYPE_DATA, FREEMAP_NODE, or FREEMAP_LEAF.  Use
1722  *        HAMMER2_LOOKUP_ALWAYS to force resolution (but be careful w/
1723  *        BREF_TYPE_DATA as the device buffer can alias the logical file
1724  *        buffer).
1725  */
1726 hammer2_chain_t *
1727 hammer2_chain_lookup(hammer2_chain_t **parentp,
1728                      hammer2_key_t key_beg, hammer2_key_t key_end,
1729                      int flags)
1730 {
1731         hammer2_mount_t *hmp;
1732         hammer2_chain_t *parent;
1733         hammer2_chain_t *chain;
1734         hammer2_chain_t *tmp;
1735         hammer2_blockref_t *base;
1736         hammer2_blockref_t *bref;
1737         hammer2_key_t scan_beg;
1738         hammer2_key_t scan_end;
1739         int count = 0;
1740         int i;
1741         int how_always = HAMMER2_RESOLVE_ALWAYS;
1742         int how_maybe = HAMMER2_RESOLVE_MAYBE;
1743
1744         if (flags & HAMMER2_LOOKUP_ALWAYS)
1745                 how_maybe = how_always;
1746
1747         if (flags & (HAMMER2_LOOKUP_SHARED | HAMMER2_LOOKUP_NOLOCK)) {
1748                 how_maybe |= HAMMER2_RESOLVE_SHARED;
1749                 how_always |= HAMMER2_RESOLVE_SHARED;
1750         }
1751
1752         /*
1753          * Recurse (*parentp) upward if necessary until the parent completely
1754          * encloses the key range or we hit the inode.
1755          */
1756         parent = *parentp;
1757         hmp = parent->hmp;
1758
1759         while (parent->bref.type == HAMMER2_BREF_TYPE_INDIRECT ||
1760                parent->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE) {
1761                 scan_beg = parent->bref.key;
1762                 scan_end = scan_beg +
1763                            ((hammer2_key_t)1 << parent->bref.keybits) - 1;
1764                 if (key_beg >= scan_beg && key_end <= scan_end)
1765                         break;
1766                 parent = hammer2_chain_getparent(parentp, how_maybe);
1767         }
1768
1769 again:
1770         /*
1771          * Locate the blockref array.  Currently we do a fully associative
1772          * search through the array.
1773          */
1774         switch(parent->bref.type) {
1775         case HAMMER2_BREF_TYPE_INODE:
1776                 /*
1777                  * Special shortcut for embedded data returns the inode
1778                  * itself.  Callers must detect this condition and access
1779                  * the embedded data (the strategy code does this for us).
1780                  *
1781                  * This is only applicable to regular files and softlinks.
1782                  */
1783                 if (parent->data->ipdata.op_flags & HAMMER2_OPFLAG_DIRECTDATA) {
1784                         if (flags & HAMMER2_LOOKUP_NOLOCK)
1785                                 hammer2_chain_ref(parent);
1786                         else
1787                                 hammer2_chain_lock(parent, how_always);
1788                         return (parent);
1789                 }
1790                 base = &parent->data->ipdata.u.blockset.blockref[0];
1791                 count = HAMMER2_SET_COUNT;
1792                 break;
1793         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1794         case HAMMER2_BREF_TYPE_INDIRECT:
1795                 /*
1796                  * Handle MATCHIND on the parent
1797                  */
1798                 if (flags & HAMMER2_LOOKUP_MATCHIND) {
1799                         scan_beg = parent->bref.key;
1800                         scan_end = scan_beg +
1801                                ((hammer2_key_t)1 << parent->bref.keybits) - 1;
1802                         if (key_beg == scan_beg && key_end == scan_end) {
1803                                 chain = parent;
1804                                 hammer2_chain_lock(chain, how_maybe);
1805                                 goto done;
1806                         }
1807                 }
1808                 /*
1809                  * Optimize indirect blocks in the INITIAL state to avoid
1810                  * I/O.
1811                  */
1812                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1813                         base = NULL;
1814                 } else {
1815                         if (parent->data == NULL)
1816                                 panic("parent->data is NULL");
1817                         base = &parent->data->npdata[0];
1818                 }
1819                 count = parent->bytes / sizeof(hammer2_blockref_t);
1820                 break;
1821         case HAMMER2_BREF_TYPE_VOLUME:
1822                 base = &hmp->voldata.sroot_blockset.blockref[0];
1823                 count = HAMMER2_SET_COUNT;
1824                 break;
1825         case HAMMER2_BREF_TYPE_FREEMAP:
1826                 base = &hmp->voldata.freemap_blockset.blockref[0];
1827                 count = HAMMER2_SET_COUNT;
1828                 break;
1829         default:
1830                 panic("hammer2_chain_lookup: unrecognized blockref type: %d",
1831                       parent->bref.type);
1832                 base = NULL;    /* safety */
1833                 count = 0;      /* safety */
1834         }
1835
1836         /*
1837          * If the element and key overlap we use the element.
1838          *
1839          * NOTE! Deleted elements are effectively invisible.  Deletions
1840          *       proactively clear the parent bref to the deleted child
1841          *       so we do not try to shadow here to avoid parent updates
1842          *       (which would be difficult since multiple deleted elements
1843          *       might represent different flush synchronization points).
1844          */
1845         bref = NULL;
1846         scan_beg = 0;   /* avoid compiler warning */
1847         scan_end = 0;   /* avoid compiler warning */
1848
1849         for (i = 0; i < count; ++i) {
1850                 tmp = hammer2_chain_find(parent, i);
1851                 if (tmp) {
1852                         if (tmp->flags & HAMMER2_CHAIN_DELETED) {
1853                                 hammer2_chain_drop(tmp);
1854                                 continue;
1855                         }
1856                         bref = &tmp->bref;
1857                         KKASSERT(bref->type != 0);
1858                 } else if (base == NULL || base[i].type == 0) {
1859                         continue;
1860                 } else {
1861                         bref = &base[i];
1862                 }
1863                 scan_beg = bref->key;
1864                 scan_end = scan_beg + ((hammer2_key_t)1 << bref->keybits) - 1;
1865                 if (tmp)
1866                         hammer2_chain_drop(tmp);
1867                 if (key_beg <= scan_end && key_end >= scan_beg)
1868                         break;
1869         }
1870         if (i == count) {
1871                 if (key_beg == key_end)
1872                         return (NULL);
1873                 return (hammer2_chain_next(parentp, NULL,
1874                                            key_beg, key_end, flags));
1875         }
1876
1877         /*
1878          * Acquire the new chain element.  If the chain element is an
1879          * indirect block we must search recursively.
1880          *
1881          * It is possible for the tmp chain above to be removed from
1882          * the RBTREE but the parent lock ensures it would not have been
1883          * destroyed from the media, so the chain_get() code will simply
1884          * reload it from the media in that case.
1885          */
1886         chain = hammer2_chain_get(parent, i, flags);
1887         if (chain == NULL)
1888                 return (NULL);
1889
1890         /*
1891          * If the chain element is an indirect block it becomes the new
1892          * parent and we loop on it.
1893          *
1894          * The parent always has to be locked with at least RESOLVE_MAYBE
1895          * so we can access its data.  It might need a fixup if the caller
1896          * passed incompatible flags.  Be careful not to cause a deadlock
1897          * as a data-load requires an exclusive lock.
1898          *
1899          * If HAMMER2_LOOKUP_MATCHIND is set and the indirect block's key
1900          * range is within the requested key range we return the indirect
1901          * block and do NOT loop.  This is usually only used to acquire
1902          * freemap nodes.
1903          */
1904         if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT ||
1905             chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE) {
1906                 hammer2_chain_unlock(parent);
1907                 *parentp = parent = chain;
1908                 if (flags & HAMMER2_LOOKUP_NOLOCK) {
1909                         hammer2_chain_lock(chain,
1910                                            how_maybe |
1911                                            HAMMER2_RESOLVE_NOREF);
1912                 } else if ((flags & HAMMER2_LOOKUP_NODATA) &&
1913                            chain->data == NULL) {
1914                         hammer2_chain_ref(chain);
1915                         hammer2_chain_unlock(chain);
1916                         hammer2_chain_lock(chain,
1917                                            how_maybe |
1918                                            HAMMER2_RESOLVE_NOREF);
1919                 }
1920                 goto again;
1921         }
1922 done:
1923         /*
1924          * All done, return the chain
1925          */
1926         return (chain);
1927 }
1928
1929 /*
1930  * After having issued a lookup we can iterate all matching keys.
1931  *
1932  * If chain is non-NULL we continue the iteration from just after it's index.
1933  *
1934  * If chain is NULL we assume the parent was exhausted and continue the
1935  * iteration at the next parent.
1936  *
1937  * parent must be locked on entry and remains locked throughout.  chain's
1938  * lock status must match flags.  Chain is always at least referenced.
1939  *
1940  * WARNING!  The MATCHIND flag does not apply to this function.
1941  */
1942 hammer2_chain_t *
1943 hammer2_chain_next(hammer2_chain_t **parentp, hammer2_chain_t *chain,
1944                    hammer2_key_t key_beg, hammer2_key_t key_end,
1945                    int flags)
1946 {
1947         hammer2_mount_t *hmp;
1948         hammer2_chain_t *parent;
1949         hammer2_chain_t *tmp;
1950         hammer2_blockref_t *base;
1951         hammer2_blockref_t *bref;
1952         hammer2_key_t scan_beg;
1953         hammer2_key_t scan_end;
1954         int i;
1955         int how_maybe = HAMMER2_RESOLVE_MAYBE;
1956         int count;
1957
1958         if (flags & (HAMMER2_LOOKUP_SHARED | HAMMER2_LOOKUP_NOLOCK))
1959                 how_maybe |= HAMMER2_RESOLVE_SHARED;
1960
1961         parent = *parentp;
1962         hmp = parent->hmp;
1963
1964 again:
1965         /*
1966          * Calculate the next index and recalculate the parent if necessary.
1967          */
1968         if (chain) {
1969                 /*
1970                  * Continue iteration within current parent.  If not NULL
1971                  * the passed-in chain may or may not be locked, based on
1972                  * the LOOKUP_NOLOCK flag (passed in as returned from lookup
1973                  * or a prior next).
1974                  */
1975                 i = chain->index + 1;
1976                 if (flags & HAMMER2_LOOKUP_NOLOCK)
1977                         hammer2_chain_drop(chain);
1978                 else
1979                         hammer2_chain_unlock(chain);
1980
1981                 /*
1982                  * Any scan where the lookup returned degenerate data embedded
1983                  * in the inode has an invalid index and must terminate.
1984                  */
1985                 if (chain == parent)
1986                         return(NULL);
1987                 chain = NULL;
1988         } else if (parent->bref.type != HAMMER2_BREF_TYPE_INDIRECT &&
1989                    parent->bref.type != HAMMER2_BREF_TYPE_FREEMAP_NODE) {
1990                 /*
1991                  * We reached the end of the iteration.
1992                  */
1993                 return (NULL);
1994         } else {
1995                 /*
1996                  * Continue iteration with next parent unless the current
1997                  * parent covers the range.
1998                  */
1999                 scan_beg = parent->bref.key;
2000                 scan_end = scan_beg +
2001                             ((hammer2_key_t)1 << parent->bref.keybits) - 1;
2002                 if (key_beg >= scan_beg && key_end <= scan_end)
2003                         return (NULL);
2004
2005                 i = parent->index + 1;
2006                 parent = hammer2_chain_getparent(parentp, how_maybe);
2007         }
2008
2009 again2:
2010         /*
2011          * Locate the blockref array.  Currently we do a fully associative
2012          * search through the array.
2013          */
2014         switch(parent->bref.type) {
2015         case HAMMER2_BREF_TYPE_INODE:
2016                 base = &parent->data->ipdata.u.blockset.blockref[0];
2017                 count = HAMMER2_SET_COUNT;
2018                 break;
2019         case HAMMER2_BREF_TYPE_INDIRECT:
2020         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
2021                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
2022                         base = NULL;
2023                 } else {
2024                         KKASSERT(parent->data != NULL);
2025                         base = &parent->data->npdata[0];
2026                 }
2027                 count = parent->bytes / sizeof(hammer2_blockref_t);
2028                 break;
2029         case HAMMER2_BREF_TYPE_VOLUME:
2030                 base = &hmp->voldata.sroot_blockset.blockref[0];
2031                 count = HAMMER2_SET_COUNT;
2032                 break;
2033         case HAMMER2_BREF_TYPE_FREEMAP:
2034                 base = &hmp->voldata.freemap_blockset.blockref[0];
2035                 count = HAMMER2_SET_COUNT;
2036                 break;
2037         default:
2038                 panic("hammer2_chain_next: unrecognized blockref type: %d",
2039                       parent->bref.type);
2040                 base = NULL;    /* safety */
2041                 count = 0;      /* safety */
2042                 break;
2043         }
2044         KKASSERT(i <= count);
2045
2046         /*
2047          * Look for the key.  If we are unable to find a match and an exact
2048          * match was requested we return NULL.  If a range was requested we
2049          * run hammer2_chain_next() to iterate.
2050          *
2051          * NOTE! Deleted elements are effectively invisible.  Deletions
2052          *       proactively clear the parent bref to the deleted child
2053          *       so we do not try to shadow here to avoid parent updates
2054          *       (which would be difficult since multiple deleted elements
2055          *       might represent different flush synchronization points).
2056          */
2057         bref = NULL;
2058         scan_beg = 0;   /* avoid compiler warning */
2059         scan_end = 0;   /* avoid compiler warning */
2060
2061         while (i < count) {
2062                 tmp = hammer2_chain_find(parent, i);
2063                 if (tmp) {
2064                         if (tmp->flags & HAMMER2_CHAIN_DELETED) {
2065                                 hammer2_chain_drop(tmp);
2066                                 ++i;
2067                                 continue;
2068                         }
2069                         bref = &tmp->bref;
2070                 } else if (base == NULL || base[i].type == 0) {
2071                         ++i;
2072                         continue;
2073                 } else {
2074                         bref = &base[i];
2075                 }
2076                 scan_beg = bref->key;
2077                 scan_end = scan_beg + ((hammer2_key_t)1 << bref->keybits) - 1;
2078                 if (tmp)
2079                         hammer2_chain_drop(tmp);
2080                 if (key_beg <= scan_end && key_end >= scan_beg)
2081                         break;
2082                 ++i;
2083         }
2084
2085         /*
2086          * If we couldn't find a match recurse up a parent to continue the
2087          * search.
2088          */
2089         if (i == count)
2090                 goto again;
2091
2092         /*
2093          * Acquire the new chain element.  If the chain element is an
2094          * indirect block we must search recursively.
2095          */
2096         chain = hammer2_chain_get(parent, i, flags);
2097         if (chain == NULL)
2098                 return (NULL);
2099
2100         /*
2101          * If the chain element is an indirect block it becomes the new
2102          * parent and we loop on it.
2103          *
2104          * The parent always has to be locked with at least RESOLVE_MAYBE
2105          * so we can access its data.  It might need a fixup if the caller
2106          * passed incompatible flags.  Be careful not to cause a deadlock
2107          * as a data-load requires an exclusive lock.
2108          *
2109          * If HAMMER2_LOOKUP_MATCHIND is set and the indirect block's key
2110          * range is within the requested key range we return the indirect
2111          * block and do NOT loop.  This is usually only used to acquire
2112          * freemap nodes.
2113          */
2114         if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT ||
2115             chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_NODE) {
2116                 if ((flags & HAMMER2_LOOKUP_MATCHIND) == 0 ||
2117                     key_beg > scan_beg || key_end < scan_end) {
2118                         hammer2_chain_unlock(parent);
2119                         *parentp = parent = chain;
2120                         chain = NULL;
2121                         if (flags & HAMMER2_LOOKUP_NOLOCK) {
2122                                 hammer2_chain_lock(parent,
2123                                                    how_maybe |
2124                                                    HAMMER2_RESOLVE_NOREF);
2125                         } else if ((flags & HAMMER2_LOOKUP_NODATA) &&
2126                                    parent->data == NULL) {
2127                                 hammer2_chain_ref(parent);
2128                                 hammer2_chain_unlock(parent);
2129                                 hammer2_chain_lock(parent,
2130                                                    how_maybe |
2131                                                    HAMMER2_RESOLVE_NOREF);
2132                         }
2133                         i = 0;
2134                         goto again2;
2135                 }
2136         }
2137
2138         /*
2139          * All done, return chain
2140          */
2141         return (chain);
2142 }
2143
2144 /*
2145  * Loop on parent's children, issuing the callback for each child.
2146  *
2147  * Uses LOOKUP flags.
2148  */
2149 int
2150 hammer2_chain_iterate(hammer2_chain_t *parent,
2151                       int (*callback)(hammer2_chain_t *parent,
2152                                       hammer2_chain_t **chainp,
2153                                       void *arg),
2154                       void *arg, int flags)
2155 {
2156         hammer2_chain_t *chain;
2157         hammer2_blockref_t *base;
2158         int count;
2159         int i;
2160         int res;
2161
2162         /*
2163          * Scan the children (if any)
2164          */
2165         res = 0;
2166         i = 0;
2167         for (;;) {
2168                 /*
2169                  * Calculate the blockref array on each loop in order
2170                  * to allow the callback to temporarily unlock/relock
2171                  * the parent.
2172                  */
2173                 switch(parent->bref.type) {
2174                 case HAMMER2_BREF_TYPE_INODE:
2175                         base = &parent->data->ipdata.u.blockset.blockref[0];
2176                         count = HAMMER2_SET_COUNT;
2177                         break;
2178                 case HAMMER2_BREF_TYPE_INDIRECT:
2179                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
2180                         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
2181                                 base = NULL;
2182                         } else {
2183                                 KKASSERT(parent->data != NULL);
2184                                 base = &parent->data->npdata[0];
2185                         }
2186                         count = parent->bytes / sizeof(hammer2_blockref_t);
2187                         break;
2188                 case HAMMER2_BREF_TYPE_VOLUME:
2189                         base = &parent->hmp->voldata.sroot_blockset.blockref[0];
2190                         count = HAMMER2_SET_COUNT;
2191                         break;
2192                 case HAMMER2_BREF_TYPE_FREEMAP:
2193                         base = &parent->hmp->voldata.freemap_blockset.blockref[0];
2194                         count = HAMMER2_SET_COUNT;
2195                         break;
2196                 default:
2197                         /*
2198                          * The function allows calls on non-recursive
2199                          * chains and will effectively be a nop() in that
2200                          * case.
2201                          */
2202                         base = NULL;
2203                         count = 0;
2204                         break;
2205                 }
2206
2207                 /*
2208                  * Loop termination
2209                  */
2210                 if (i >= count)
2211                         break;
2212
2213                 /*
2214                  * Lookup the child, properly overloading any elements
2215                  * held in memory.
2216                  *
2217                  * NOTE: Deleted elements cover any underlying base[] entry
2218                  *       (which might not have been zero'd out yet).
2219                  *
2220                  * NOTE: The fact that there can be multiple stacked
2221                  *       deleted elements at the same index is hidden
2222                  *       by hammer2_chain_find().
2223                  */
2224                 chain = hammer2_chain_find(parent, i);
2225                 if (chain) {
2226                         if (chain->flags & HAMMER2_CHAIN_DELETED) {
2227                                 hammer2_chain_drop(chain);
2228                                 ++i;
2229                                 continue;
2230                         }
2231                 } else if (base == NULL || base[i].type == 0) {
2232                         ++i;
2233                         continue;
2234                 }
2235                 if (chain)
2236                         hammer2_chain_drop(chain);
2237                 chain = hammer2_chain_get(parent, i, flags);
2238                 if (chain) {
2239                         res = callback(parent, &chain, arg);
2240                         if (chain) {
2241                                 if (flags & HAMMER2_LOOKUP_NOLOCK)
2242                                         hammer2_chain_drop(chain);
2243                                 else
2244                                         hammer2_chain_unlock(chain);
2245                         }
2246                         if (res < 0)
2247                                 break;
2248                 }
2249                 ++i;
2250         }
2251         return res;
2252 }
2253
2254 /*
2255  * Create and return a new hammer2 system memory structure of the specified
2256  * key, type and size and insert it under (*parentp).  This is a full
2257  * insertion, based on the supplied key/keybits, and may involve creating
2258  * indirect blocks and moving other chains around via delete/duplicate.
2259  *
2260  * (*parentp) must be exclusive locked and may be replaced on return
2261  * depending on how much work the function had to do.
2262  *
2263  * (*chainp) usually starts out NULL and returns the newly created chain,
2264  * but if the caller desires the caller may allocate a disconnected chain
2265  * and pass it in instead.  (It is also possible for the caller to use
2266  * chain_duplicate() to create a disconnected chain, manipulate it, then
2267  * pass it into this function to insert it).
2268  *
2269  * This function should NOT be used to insert INDIRECT blocks.  It is
2270  * typically used to create/insert inodes and data blocks.
2271  *
2272  * Caller must pass-in an exclusively locked parent the new chain is to
2273  * be inserted under, and optionally pass-in a disconnected, exclusively
2274  * locked chain to insert (else we create a new chain).  The function will
2275  * adjust (*parentp) as necessary, create or connect the chain, and
2276  * return an exclusively locked chain in *chainp.
2277  */
2278 int
2279 hammer2_chain_create(hammer2_trans_t *trans, hammer2_chain_t **parentp,
2280                      hammer2_chain_t **chainp,
2281                      hammer2_key_t key, int keybits, int type, size_t bytes)
2282 {
2283         hammer2_mount_t *hmp;
2284         hammer2_chain_t *chain;
2285         hammer2_chain_t *child;
2286         hammer2_chain_t *parent = *parentp;
2287         hammer2_chain_core_t *above;
2288         hammer2_blockref_t dummy;
2289         hammer2_blockref_t *base;
2290         int allocated = 0;
2291         int error = 0;
2292         int count;
2293         int i;
2294
2295         above = parent->core;
2296         KKASSERT(ccms_thread_lock_owned(&above->cst));
2297         hmp = parent->hmp;
2298         chain = *chainp;
2299
2300         if (chain == NULL) {
2301                 /*
2302                  * First allocate media space and construct the dummy bref,
2303                  * then allocate the in-memory chain structure.  Set the
2304                  * INITIAL flag for fresh chains.
2305                  */
2306                 bzero(&dummy, sizeof(dummy));
2307                 dummy.type = type;
2308                 dummy.key = key;
2309                 dummy.keybits = keybits;
2310                 dummy.data_off = hammer2_getradix(bytes);
2311                 dummy.methods = parent->bref.methods;
2312                 chain = hammer2_chain_alloc(hmp, trans, &dummy);
2313                 hammer2_chain_core_alloc(chain, NULL);
2314
2315                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_INITIAL);
2316
2317                 /*
2318                  * Lock the chain manually, chain_lock will load the chain
2319                  * which we do NOT want to do.  (note: chain->refs is set
2320                  * to 1 by chain_alloc() for us, but lockcnt is not).
2321                  */
2322                 chain->lockcnt = 1;
2323                 ccms_thread_lock(&chain->core->cst, CCMS_STATE_EXCLUSIVE);
2324                 allocated = 1;
2325
2326                 /*
2327                  * We do NOT set INITIAL here (yet).  INITIAL is only
2328                  * used for indirect blocks.
2329                  *
2330                  * Recalculate bytes to reflect the actual media block
2331                  * allocation.
2332                  */
2333                 bytes = (hammer2_off_t)1 <<
2334                         (int)(chain->bref.data_off & HAMMER2_OFF_MASK_RADIX);
2335                 chain->bytes = bytes;
2336
2337                 switch(type) {
2338                 case HAMMER2_BREF_TYPE_VOLUME:
2339                 case HAMMER2_BREF_TYPE_FREEMAP:
2340                         panic("hammer2_chain_create: called with volume type");
2341                         break;
2342                 case HAMMER2_BREF_TYPE_INODE:
2343                         KKASSERT(bytes == HAMMER2_INODE_BYTES);
2344                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_EMBEDDED);
2345                         chain->data = kmalloc(sizeof(chain->data->ipdata),
2346                                               hmp->mchain, M_WAITOK | M_ZERO);
2347                         break;
2348                 case HAMMER2_BREF_TYPE_INDIRECT:
2349                         panic("hammer2_chain_create: cannot be used to"
2350                               "create indirect block");
2351                         break;
2352                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
2353                         panic("hammer2_chain_create: cannot be used to"
2354                               "create freemap root or node");
2355                         break;
2356                 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
2357                         KKASSERT(bytes == sizeof(chain->data->bmdata));
2358                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_EMBEDDED);
2359                         chain->data = kmalloc(sizeof(chain->data->bmdata),
2360                                               hmp->mchain, M_WAITOK | M_ZERO);
2361                         break;
2362                 case HAMMER2_BREF_TYPE_DATA:
2363                 default:
2364                         /* leave chain->data NULL */
2365                         KKASSERT(chain->data == NULL);
2366                         break;
2367                 }
2368         } else {
2369                 /*
2370                  * Potentially update the existing chain's key/keybits.
2371                  *
2372                  * Do NOT mess with the current state of the INITIAL flag.
2373                  */
2374                 chain->bref.key = key;
2375                 chain->bref.keybits = keybits;
2376                 KKASSERT(chain->above == NULL);
2377         }
2378
2379 again:
2380         above = parent->core;
2381
2382         /*
2383          * Locate a free blockref in the parent's array
2384          */
2385         switch(parent->bref.type) {
2386         case HAMMER2_BREF_TYPE_INODE:
2387                 KKASSERT((parent->data->ipdata.op_flags &
2388                           HAMMER2_OPFLAG_DIRECTDATA) == 0);
2389                 KKASSERT(parent->data != NULL);
2390                 base = &parent->data->ipdata.u.blockset.blockref[0];
2391                 count = HAMMER2_SET_COUNT;
2392                 break;
2393         case HAMMER2_BREF_TYPE_INDIRECT:
2394         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
2395                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
2396                         base = NULL;
2397                 } else {
2398                         KKASSERT(parent->data != NULL);
2399                         base = &parent->data->npdata[0];
2400                 }
2401                 count = parent->bytes / sizeof(hammer2_blockref_t);
2402                 break;
2403         case HAMMER2_BREF_TYPE_VOLUME:
2404                 KKASSERT(parent->data != NULL);
2405                 base = &hmp->voldata.sroot_blockset.blockref[0];
2406                 count = HAMMER2_SET_COUNT;
2407                 break;
2408         case HAMMER2_BREF_TYPE_FREEMAP:
2409                 KKASSERT(parent->data != NULL);
2410                 base = &hmp->voldata.freemap_blockset.blockref[0];
2411                 count = HAMMER2_SET_COUNT;
2412                 break;
2413         default:
2414                 panic("hammer2_chain_create: unrecognized blockref type: %d",
2415                       parent->bref.type);
2416                 count = 0;
2417                 break;
2418         }
2419
2420         /*
2421          * Scan for an unallocated bref, also skipping any slots occupied
2422          * by in-memory chain elements that may not yet have been updated
2423          * in the parent's bref array.
2424          *
2425          * We don't have to hold the spinlock to save an empty slot as
2426          * new slots can only transition from empty if the parent is
2427          * locked exclusively.
2428          */
2429         spin_lock(&above->cst.spin);
2430         for (i = 0; i < count; ++i) {
2431                 child = hammer2_chain_find_locked(parent, i);
2432                 if (child) {
2433                         if (child->flags & HAMMER2_CHAIN_DELETED)
2434                                 break;
2435                         continue;
2436                 }
2437                 if (base == NULL)
2438                         break;
2439                 if (base[i].type == 0)
2440                         break;
2441         }
2442         spin_unlock(&above->cst.spin);
2443
2444         /*
2445          * If no free blockref could be found we must create an indirect
2446          * block and move a number of blockrefs into it.  With the parent
2447          * locked we can safely lock each child in order to move it without
2448          * causing a deadlock.
2449          *
2450          * This may return the new indirect block or the old parent depending
2451          * on where the key falls.  NULL is returned on error.
2452          */
2453         if (i == count) {
2454                 hammer2_chain_t *nparent;
2455
2456                 nparent = hammer2_chain_create_indirect(trans, parent,
2457                                                         key, keybits,
2458                                                         type, &error);
2459                 if (nparent == NULL) {
2460                         if (allocated)
2461                                 hammer2_chain_drop(chain);
2462                         chain = NULL;
2463                         goto done;
2464                 }
2465                 if (parent != nparent) {
2466                         hammer2_chain_unlock(parent);
2467                         parent = *parentp = nparent;
2468                 }
2469                 goto again;
2470         }
2471
2472         /*
2473          * Link the chain into its parent.  Later on we will have to set
2474          * the MOVED bit in situations where we don't mark the new chain
2475          * as being modified.
2476          */
2477         if (chain->above != NULL)
2478                 panic("hammer2: hammer2_chain_create: chain already connected");
2479         KKASSERT(chain->above == NULL);
2480         KKASSERT((chain->flags & HAMMER2_CHAIN_DELETED) == 0);
2481
2482         chain->above = above;
2483         chain->index = i;
2484         spin_lock(&above->cst.spin);
2485         if (RB_INSERT(hammer2_chain_tree, &above->rbtree, chain))
2486                 panic("hammer2_chain_create: collision");
2487         atomic_set_int(&chain->flags, HAMMER2_CHAIN_ONRBTREE);
2488         spin_unlock(&above->cst.spin);
2489
2490         if (allocated) {
2491                 /*
2492                  * Mark the newly created chain modified.
2493                  *
2494                  * Device buffers are not instantiated for DATA elements
2495                  * as these are handled by logical buffers.
2496                  *
2497                  * Indirect and freemap node indirect blocks are handled
2498                  * by hammer2_chain_create_indirect() and not by this
2499                  * function.
2500                  *
2501                  * Data for all other bref types is expected to be
2502                  * instantiated (INODE, LEAF).
2503                  */
2504                 switch(chain->bref.type) {
2505                 case HAMMER2_BREF_TYPE_DATA:
2506                         hammer2_chain_modify(trans, &chain,
2507                                              HAMMER2_MODIFY_OPTDATA |
2508                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2509                         break;
2510                 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
2511                 case HAMMER2_BREF_TYPE_INODE:
2512                         hammer2_chain_modify(trans, &chain,
2513                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2514                         break;
2515                 default:
2516                         /*
2517                          * Remaining types are not supported by this function.
2518                          * In particular, INDIRECT and LEAF_NODE types are
2519                          * handled by create_indirect().
2520                          */
2521                         panic("hammer2_chain_create: bad type: %d",
2522                               chain->bref.type);
2523                         /* NOT REACHED */
2524                         break;
2525                 }
2526         } else {
2527                 /*
2528                  * When reconnecting a chain we must set MOVED and setsubmod
2529                  * so the flush recognizes that it must update the bref in
2530                  * the parent.
2531                  */
2532                 if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
2533                         hammer2_chain_ref(chain);
2534                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
2535                 }
2536                 hammer2_chain_setsubmod(trans, chain);
2537         }
2538
2539 done:
2540         *chainp = chain;
2541
2542         return (error);
2543 }
2544
2545 /*
2546  * Replace (*chainp) with a duplicate.  The original *chainp is unlocked
2547  * and the replacement will be returned locked.  Both the original and the
2548  * new chain will share the same RBTREE (have the same chain->core), with
2549  * the new chain becoming the 'current' chain (meaning it is the first in
2550  * the linked list at core->chain_first).
2551  *
2552  * If (parent, i) then the new duplicated chain is inserted under the parent
2553  * at the specified index (the parent must not have a ref at that index).
2554  *
2555  * If (NULL, -1) then the new duplicated chain is not inserted anywhere,
2556  * similar to if it had just been chain_alloc()'d (suitable for passing into
2557  * hammer2_chain_create() after this function returns).
2558  *
2559  * NOTE! Duplication is used in order to retain the original topology to
2560  *       support flush synchronization points.  Both the original and the
2561  *       new chain will have the same transaction id and thus the operation
2562  *       appears atomic w/regards to media flushes.
2563  */
2564 static void hammer2_chain_dup_fixup(hammer2_chain_t *ochain,
2565                                     hammer2_chain_t *nchain);
2566
2567 void
2568 hammer2_chain_duplicate(hammer2_trans_t *trans, hammer2_chain_t *parent, int i,
2569                         hammer2_chain_t **chainp, hammer2_blockref_t *bref)
2570 {
2571         hammer2_mount_t *hmp;
2572         hammer2_blockref_t *base;
2573         hammer2_chain_t *ochain;
2574         hammer2_chain_t *nchain;
2575         hammer2_chain_t *scan;
2576         hammer2_chain_core_t *above;
2577         size_t bytes;
2578         int count;
2579         int oflags;
2580         void *odata;
2581
2582         /*
2583          * First create a duplicate of the chain structure, associating
2584          * it with the same core, making it the same size, pointing it
2585          * to the same bref (the same media block).
2586          */
2587         ochain = *chainp;
2588         hmp = ochain->hmp;
2589         if (bref == NULL)
2590                 bref = &ochain->bref;
2591         nchain = hammer2_chain_alloc(hmp, trans, bref);
2592         hammer2_chain_core_alloc(nchain, ochain->core);
2593         bytes = (hammer2_off_t)1 <<
2594                 (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
2595         nchain->bytes = bytes;
2596         nchain->modify_tid = ochain->modify_tid;
2597
2598         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_NEVER);
2599         hammer2_chain_dup_fixup(ochain, nchain);
2600
2601         /*
2602          * If parent is not NULL, insert into the parent at the requested
2603          * index.  The newly duplicated chain must be marked MOVED and
2604          * SUBMODIFIED set in its parent(s).
2605          *
2606          * Having both chains locked is extremely important for atomicy.
2607          */
2608         if (parent) {
2609                 /*
2610                  * Locate a free blockref in the parent's array
2611                  */
2612                 above = parent->core;
2613                 KKASSERT(ccms_thread_lock_owned(&above->cst));
2614
2615                 switch(parent->bref.type) {
2616                 case HAMMER2_BREF_TYPE_INODE:
2617                         KKASSERT((parent->data->ipdata.op_flags &
2618                                   HAMMER2_OPFLAG_DIRECTDATA) == 0);
2619                         KKASSERT(parent->data != NULL);
2620                         base = &parent->data->ipdata.u.blockset.blockref[0];
2621                         count = HAMMER2_SET_COUNT;
2622                         break;
2623                 case HAMMER2_BREF_TYPE_INDIRECT:
2624                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
2625                         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
2626                                 base = NULL;
2627                         } else {
2628                                 KKASSERT(parent->data != NULL);
2629                                 base = &parent->data->npdata[0];
2630                         }
2631                         count = parent->bytes / sizeof(hammer2_blockref_t);
2632                         break;
2633                 case HAMMER2_BREF_TYPE_VOLUME:
2634                         KKASSERT(parent->data != NULL);
2635                         base = &hmp->voldata.sroot_blockset.blockref[0];
2636                         count = HAMMER2_SET_COUNT;
2637                         break;
2638                 case HAMMER2_BREF_TYPE_FREEMAP:
2639                         KKASSERT(parent->data != NULL);
2640                         base = &hmp->voldata.freemap_blockset.blockref[0];
2641                         count = HAMMER2_SET_COUNT;
2642                         break;
2643                 default:
2644                         panic("hammer2_chain_create: unrecognized "
2645                               "blockref type: %d",
2646                               parent->bref.type);
2647                         count = 0;
2648                         break;
2649                 }
2650                 KKASSERT(i >= 0 && i < count);
2651
2652                 KKASSERT((nchain->flags & HAMMER2_CHAIN_DELETED) == 0);
2653                 KKASSERT(parent->refs > 0);
2654
2655                 spin_lock(&above->cst.spin);
2656                 nchain->above = above;
2657                 nchain->index = i;
2658                 scan = hammer2_chain_find_locked(parent, i);
2659                 KKASSERT(base == NULL || base[i].type == 0 ||
2660                          scan == NULL ||
2661                          (scan->flags & HAMMER2_CHAIN_DELETED));
2662                 if (RB_INSERT(hammer2_chain_tree, &above->rbtree,
2663                               nchain)) {
2664                         panic("hammer2_chain_duplicate: collision");
2665                 }
2666                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_ONRBTREE);
2667                 spin_unlock(&above->cst.spin);
2668
2669                 if ((nchain->flags & HAMMER2_CHAIN_MOVED) == 0) {
2670                         hammer2_chain_ref(nchain);
2671                         atomic_set_int(&nchain->flags, HAMMER2_CHAIN_MOVED);
2672                 }
2673                 hammer2_chain_setsubmod(trans, nchain);
2674         }
2675
2676         /*
2677          * We have to unlock ochain to flush any dirty data, asserting the
2678          * case (data == NULL) to catch any extra locks that might have been
2679          * present, then transfer state to nchain.
2680          */
2681         oflags = ochain->flags;
2682         odata = ochain->data;
2683         hammer2_chain_unlock(ochain);
2684         KKASSERT((ochain->flags & HAMMER2_CHAIN_EMBEDDED) ||
2685                  ochain->data == NULL);
2686
2687         if (oflags & HAMMER2_CHAIN_INITIAL)
2688                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_INITIAL);
2689
2690         /*
2691          * WARNING!  We should never resolve DATA to device buffers
2692          *           (XXX allow it if the caller did?), and since
2693          *           we currently do not have the logical buffer cache
2694          *           buffer in-hand to fix its cached physical offset
2695          *           we also force the modify code to not COW it. XXX
2696          */
2697         if (oflags & HAMMER2_CHAIN_MODIFIED) {
2698                 if (nchain->bref.type == HAMMER2_BREF_TYPE_DATA) {
2699                         hammer2_chain_modify(trans, &nchain,
2700                                              HAMMER2_MODIFY_OPTDATA |
2701                                              HAMMER2_MODIFY_NOREALLOC |
2702                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2703                 } else if (oflags & HAMMER2_CHAIN_INITIAL) {
2704                         hammer2_chain_modify(trans, &nchain,
2705                                              HAMMER2_MODIFY_OPTDATA |
2706                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2707                 } else {
2708                         hammer2_chain_modify(trans, &nchain,
2709                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2710                 }
2711                 hammer2_chain_drop(nchain);
2712         } else {
2713                 if (nchain->bref.type == HAMMER2_BREF_TYPE_DATA) {
2714                         hammer2_chain_drop(nchain);
2715                 } else if (oflags & HAMMER2_CHAIN_INITIAL) {
2716                         hammer2_chain_drop(nchain);
2717                 } else {
2718                         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_ALWAYS |
2719                                                    HAMMER2_RESOLVE_NOREF);
2720                         hammer2_chain_unlock(nchain);
2721                 }
2722         }
2723         atomic_set_int(&nchain->flags, HAMMER2_CHAIN_SUBMODIFIED);
2724         *chainp = nchain;
2725 }
2726
2727 #if 0
2728                 /*
2729                  * When the chain is in the INITIAL state we must still
2730                  * ensure that a block has been assigned so MOVED processing
2731                  * works as expected.
2732                  */
2733                 KKASSERT (nchain->bref.type != HAMMER2_BREF_TYPE_DATA);
2734                 hammer2_chain_modify(trans, &nchain,
2735                                      HAMMER2_MODIFY_OPTDATA |
2736                                      HAMMER2_MODIFY_ASSERTNOCOPY);
2737
2738
2739         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_MAYBE |
2740                                    HAMMER2_RESOLVE_NOREF); /* eat excess ref */
2741         hammer2_chain_unlock(nchain);
2742 #endif
2743
2744 /*
2745  * Special in-place delete-duplicate sequence which does not require a
2746  * locked parent.  (*chainp) is marked DELETED and atomically replaced
2747  * with a duplicate.  Atomicy is at the very-fine spin-lock level in
2748  * order to ensure that lookups do not race us.
2749  */
2750 void
2751 hammer2_chain_delete_duplicate(hammer2_trans_t *trans, hammer2_chain_t **chainp,
2752                                int flags)
2753 {
2754         hammer2_mount_t *hmp;
2755         hammer2_chain_t *ochain;
2756         hammer2_chain_t *nchain;
2757         hammer2_chain_core_t *above;
2758         size_t bytes;
2759         int oflags;
2760         void *odata;
2761
2762         /*
2763          * First create a duplicate of the chain structure
2764          */
2765         ochain = *chainp;
2766         hmp = ochain->hmp;
2767         nchain = hammer2_chain_alloc(hmp, trans, &ochain->bref);    /* 1 ref */
2768         if (flags & HAMMER2_DELDUP_RECORE)
2769                 hammer2_chain_core_alloc(nchain, NULL);
2770         else
2771                 hammer2_chain_core_alloc(nchain, ochain->core);
2772         above = ochain->above;
2773
2774         bytes = (hammer2_off_t)1 <<
2775                 (int)(ochain->bref.data_off & HAMMER2_OFF_MASK_RADIX);
2776         nchain->bytes = bytes;
2777         nchain->modify_tid = ochain->modify_tid;
2778         nchain->data_count += ochain->data_count;
2779         nchain->inode_count += ochain->inode_count;
2780
2781         /*
2782          * Lock nchain and insert into ochain's core hierarchy, marking
2783          * ochain DELETED at the same time.  Having both chains locked
2784          * is extremely important for atomicy.
2785          */
2786         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_NEVER);
2787         hammer2_chain_dup_fixup(ochain, nchain);
2788         /* extra ref still present from original allocation */
2789
2790         nchain->index = ochain->index;
2791
2792         spin_lock(&above->cst.spin);
2793         atomic_set_int(&nchain->flags, HAMMER2_CHAIN_ONRBTREE);
2794         ochain->delete_tid = trans->sync_tid;
2795         nchain->above = above;
2796         atomic_set_int(&ochain->flags, HAMMER2_CHAIN_DELETED);
2797         if ((ochain->flags & HAMMER2_CHAIN_MOVED) == 0) {
2798                 hammer2_chain_ref(ochain);
2799                 atomic_set_int(&ochain->flags, HAMMER2_CHAIN_MOVED);
2800         }
2801         if (RB_INSERT(hammer2_chain_tree, &above->rbtree, nchain)) {
2802                 panic("hammer2_chain_delete_duplicate: collision");
2803         }
2804         spin_unlock(&above->cst.spin);
2805
2806         /*
2807          * We have to unlock ochain to flush any dirty data, asserting the
2808          * case (data == NULL) to catch any extra locks that might have been
2809          * present, then transfer state to nchain.
2810          */
2811         oflags = ochain->flags;
2812         odata = ochain->data;
2813         hammer2_chain_unlock(ochain);   /* replacing ochain */
2814         KKASSERT(ochain->bref.type == HAMMER2_BREF_TYPE_INODE ||
2815                  ochain->data == NULL);
2816
2817         if (oflags & HAMMER2_CHAIN_INITIAL)
2818                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_INITIAL);
2819
2820         /*
2821          * WARNING!  We should never resolve DATA to device buffers
2822          *           (XXX allow it if the caller did?), and since
2823          *           we currently do not have the logical buffer cache
2824          *           buffer in-hand to fix its cached physical offset
2825          *           we also force the modify code to not COW it. XXX
2826          */
2827         if (oflags & HAMMER2_CHAIN_MODIFIED) {
2828                 if (nchain->bref.type == HAMMER2_BREF_TYPE_DATA) {
2829                         hammer2_chain_modify(trans, &nchain,
2830                                              HAMMER2_MODIFY_OPTDATA |
2831                                              HAMMER2_MODIFY_NOREALLOC |
2832                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2833                 } else if (oflags & HAMMER2_CHAIN_INITIAL) {
2834                         hammer2_chain_modify(trans, &nchain,
2835                                              HAMMER2_MODIFY_OPTDATA |
2836                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2837                 } else {
2838                         hammer2_chain_modify(trans, &nchain,
2839                                              HAMMER2_MODIFY_ASSERTNOCOPY);
2840                 }
2841                 hammer2_chain_drop(nchain);
2842         } else {
2843                 if (nchain->bref.type == HAMMER2_BREF_TYPE_DATA) {
2844                         hammer2_chain_drop(nchain);
2845                 } else if (oflags & HAMMER2_CHAIN_INITIAL) {
2846                         hammer2_chain_drop(nchain);
2847                 } else {
2848                         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_ALWAYS |
2849                                                    HAMMER2_RESOLVE_NOREF);
2850                         hammer2_chain_unlock(nchain);
2851                 }
2852         }
2853
2854         /*
2855          * Unconditionally set the MOVED and SUBMODIFIED bit to force
2856          * update of parent bref and indirect blockrefs during flush.
2857          */
2858         if ((nchain->flags & HAMMER2_CHAIN_MOVED) == 0) {
2859                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_MOVED);
2860                 hammer2_chain_ref(nchain);
2861         }
2862         atomic_set_int(&nchain->flags, HAMMER2_CHAIN_SUBMODIFIED);
2863         hammer2_chain_setsubmod(trans, nchain);
2864         *chainp = nchain;
2865 }
2866
2867 /*
2868  * Helper function to fixup inodes.  The caller procedure stack may hold
2869  * multiple locks on ochain if it represents an inode, preventing our
2870  * unlock from retiring its state to the buffer cache.
2871  *
2872  * In this situation any attempt to access the buffer cache could result
2873  * either in stale data or a deadlock.  Work around the problem by copying
2874  * the embedded data directly.
2875  */
2876 static
2877 void
2878 hammer2_chain_dup_fixup(hammer2_chain_t *ochain, hammer2_chain_t *nchain)
2879 {
2880         if (ochain->data == NULL)
2881                 return;
2882         switch(ochain->bref.type) {
2883         case HAMMER2_BREF_TYPE_INODE:
2884                 KKASSERT(nchain->data == NULL);
2885                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_EMBEDDED);
2886                 nchain->data = kmalloc(sizeof(nchain->data->ipdata),
2887                                        ochain->hmp->mchain, M_WAITOK | M_ZERO);
2888                 nchain->data->ipdata = ochain->data->ipdata;
2889                 break;
2890         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
2891                 KKASSERT(nchain->data == NULL);
2892                 atomic_set_int(&nchain->flags, HAMMER2_CHAIN_EMBEDDED);
2893                 nchain->data = kmalloc(sizeof(nchain->data->bmdata),
2894                                        ochain->hmp->mchain, M_WAITOK | M_ZERO);
2895                 bcopy(ochain->data->bmdata,
2896                       nchain->data->bmdata,
2897                       sizeof(nchain->data->bmdata));
2898                 break;
2899         default:
2900                 break;
2901         }
2902 }
2903
2904 /*
2905  * Create a snapshot of the specified {parent, chain} with the specified
2906  * label.
2907  *
2908  * (a) We create a duplicate connected to the super-root as the specified
2909  *     label.
2910  *
2911  * (b) We issue a restricted flush using the current transaction on the
2912  *     duplicate.
2913  *
2914  * (c) We disconnect and reallocate the duplicate's core.
2915  */
2916 int
2917 hammer2_chain_snapshot(hammer2_trans_t *trans, hammer2_inode_t *ip,
2918                        hammer2_ioc_pfs_t *pfs)
2919 {
2920         hammer2_cluster_t *cluster;
2921         hammer2_mount_t *hmp;
2922         hammer2_chain_t *chain;
2923         hammer2_chain_t *nchain;
2924         hammer2_chain_t *parent;
2925         hammer2_inode_data_t *ipdata;
2926         size_t name_len;
2927         hammer2_key_t lhc;
2928         int error;
2929
2930         name_len = strlen(pfs->name);
2931         lhc = hammer2_dirhash(pfs->name, name_len);
2932         cluster = ip->pmp->mount_cluster;
2933         hmp = ip->chain->hmp;
2934         KKASSERT(hmp == cluster->hmp);  /* XXX */
2935
2936         /*
2937          * Create disconnected duplicate
2938          */
2939         KKASSERT((trans->flags & HAMMER2_TRANS_RESTRICTED) == 0);
2940         nchain = ip->chain;
2941         hammer2_chain_lock(nchain, HAMMER2_RESOLVE_MAYBE);
2942         hammer2_chain_duplicate(trans, NULL, -1, &nchain, NULL);
2943         atomic_set_int(&nchain->flags, HAMMER2_CHAIN_RECYCLE |
2944                                        HAMMER2_CHAIN_SNAPSHOT);
2945
2946         /*
2947          * Create named entry in the super-root.
2948          */
2949         parent = hammer2_chain_lookup_init(hmp->schain, 0);
2950         error = 0;
2951         while (error == 0) {
2952                 chain = hammer2_chain_lookup(&parent, lhc, lhc, 0);
2953                 if (chain == NULL)
2954                         break;
2955                 if ((lhc & HAMMER2_DIRHASH_LOMASK) == HAMMER2_DIRHASH_LOMASK)
2956                         error = ENOSPC;
2957                 hammer2_chain_unlock(chain);
2958                 chain = NULL;
2959                 ++lhc;
2960         }
2961         hammer2_chain_create(trans, &parent, &nchain, lhc, 0,
2962                              HAMMER2_BREF_TYPE_INODE,
2963                              HAMMER2_INODE_BYTES);
2964         hammer2_chain_modify(trans, &nchain, HAMMER2_MODIFY_ASSERTNOCOPY);
2965         hammer2_chain_lookup_done(parent);
2966         parent = NULL;  /* safety */
2967
2968         /*
2969          * Name fixup
2970          */
2971         ipdata = &nchain->data->ipdata;
2972         ipdata->name_key = lhc;
2973         ipdata->name_len = name_len;
2974         ksnprintf(ipdata->filename, sizeof(ipdata->filename), "%s", pfs->name);
2975
2976         /*
2977          * Set PFS type, generate a unique filesystem id, and generate
2978          * a cluster id.  Use the same clid when snapshotting a PFS root,
2979          * which theoretically allows the snapshot to be used as part of
2980          * the same cluster (perhaps as a cache).
2981          */
2982         ipdata->pfs_type = HAMMER2_PFSTYPE_SNAPSHOT;
2983         kern_uuidgen(&ipdata->pfs_fsid, 1);
2984         if (ip->chain == cluster->rchain)
2985                 ipdata->pfs_clid = ip->chain->data->ipdata.pfs_clid;
2986         else
2987                 kern_uuidgen(&ipdata->pfs_clid, 1);
2988
2989         /*
2990          * Issue a restricted flush of the snapshot.  This is a synchronous
2991          * operation.
2992          */
2993         trans->flags |= HAMMER2_TRANS_RESTRICTED;
2994         kprintf("SNAPSHOTA\n");
2995         tsleep(trans, 0, "snapslp", hz*4);
2996         kprintf("SNAPSHOTB\n");
2997         hammer2_chain_flush(trans, nchain);
2998         trans->flags &= ~HAMMER2_TRANS_RESTRICTED;
2999
3000 #if 0
3001         /*
3002          * Remove the link b/c nchain is a snapshot and snapshots don't
3003          * follow CHAIN_DELETED semantics ?
3004          */
3005         chain = ip->chain;
3006
3007
3008         KKASSERT(chain->duplink == nchain);
3009         KKASSERT(chain->core == nchain->core);
3010         KKASSERT(nchain->refs >= 2);
3011         chain->duplink = nchain->duplink;
3012         atomic_clear_int(&nchain->flags, HAMMER2_CHAIN_DUPTARGET);
3013         hammer2_chain_drop(nchain);
3014 #endif
3015
3016         kprintf("snapshot %s nchain->refs %d nchain->flags %08x\n",
3017                 pfs->name, nchain->refs, nchain->flags);
3018         hammer2_chain_unlock(nchain);
3019
3020         return (error);
3021 }
3022
3023 /*
3024  * Create an indirect block that covers one or more of the elements in the
3025  * current parent.  Either returns the existing parent with no locking or
3026  * ref changes or returns the new indirect block locked and referenced
3027  * and leaving the original parent lock/ref intact as well.
3028  *
3029  * If an error occurs, NULL is returned and *errorp is set to the error.
3030  *
3031  * The returned chain depends on where the specified key falls.
3032  *
3033  * The key/keybits for the indirect mode only needs to follow three rules:
3034  *
3035  * (1) That all elements underneath it fit within its key space and
3036  *
3037  * (2) That all elements outside it are outside its key space.
3038  *
3039  * (3) When creating the new indirect block any elements in the current
3040  *     parent that fit within the new indirect block's keyspace must be
3041  *     moved into the new indirect block.
3042  *
3043  * (4) The keyspace chosen for the inserted indirect block CAN cover a wider
3044  *     keyspace the the current parent, but lookup/iteration rules will
3045  *     ensure (and must ensure) that rule (2) for all parents leading up
3046  *     to the nearest inode or the root volume header is adhered to.  This
3047  *     is accomplished by always recursing through matching keyspaces in
3048  *     the hammer2_chain_lookup() and hammer2_chain_next() API.
3049  *
3050  * The current implementation calculates the current worst-case keyspace by
3051  * iterating the current parent and then divides it into two halves, choosing
3052  * whichever half has the most elements (not necessarily the half containing
3053  * the requested key).
3054  *
3055  * We can also opt to use the half with the least number of elements.  This
3056  * causes lower-numbered keys (aka logical file offsets) to recurse through
3057  * fewer indirect blocks and higher-numbered keys to recurse through more.
3058  * This also has the risk of not moving enough elements to the new indirect
3059  * block and being forced to create several indirect blocks before the element
3060  * can be inserted.
3061  *
3062  * Must be called with an exclusively locked parent.
3063  */
3064 static int hammer2_chain_indkey_freemap(hammer2_chain_t *parent,
3065                                 hammer2_key_t *keyp, int keybits,
3066                                 hammer2_blockref_t *base, int count);
3067 static int hammer2_chain_indkey_normal(hammer2_chain_t *parent,
3068                                 hammer2_key_t *keyp, int keybits,
3069                                 hammer2_blockref_t *base, int count);
3070 static
3071 hammer2_chain_t *
3072 hammer2_chain_create_indirect(hammer2_trans_t *trans, hammer2_chain_t *parent,
3073                               hammer2_key_t create_key, int create_bits,
3074                               int for_type, int *errorp)
3075 {
3076         hammer2_mount_t *hmp;
3077         hammer2_chain_core_t *above;
3078         hammer2_chain_core_t *icore;
3079         hammer2_blockref_t *base;
3080         hammer2_blockref_t *bref;
3081         hammer2_chain_t *chain;
3082         hammer2_chain_t *child;
3083         hammer2_chain_t *ichain;
3084         hammer2_chain_t dummy;
3085         hammer2_key_t key = create_key;
3086         int keybits = create_bits;
3087         int count;
3088         int nbytes;
3089         int i;
3090
3091         /*
3092          * Calculate the base blockref pointer or NULL if the chain
3093          * is known to be empty.  We need to calculate the array count
3094          * for RB lookups either way.
3095          */
3096         hmp = parent->hmp;
3097         *errorp = 0;
3098         KKASSERT(ccms_thread_lock_owned(&parent->core->cst));
3099         above = parent->core;
3100
3101         /*hammer2_chain_modify(trans, &parent, HAMMER2_MODIFY_OPTDATA);*/
3102         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
3103                 base = NULL;
3104
3105                 switch(parent->bref.type) {
3106                 case HAMMER2_BREF_TYPE_INODE:
3107                         count = HAMMER2_SET_COUNT;
3108                         break;
3109                 case HAMMER2_BREF_TYPE_INDIRECT:
3110                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
3111                         count = parent->bytes / sizeof(hammer2_blockref_t);
3112                         break;
3113                 case HAMMER2_BREF_TYPE_VOLUME:
3114                         count = HAMMER2_SET_COUNT;
3115                         break;
3116                 case HAMMER2_BREF_TYPE_FREEMAP:
3117                         count = HAMMER2_SET_COUNT;
3118                         break;
3119                 default:
3120                         panic("hammer2_chain_create_indirect: "
3121                               "unrecognized blockref type: %d",
3122                               parent->bref.type);
3123                         count = 0;
3124                         break;
3125                 }
3126         } else {
3127                 switch(parent->bref.type) {
3128                 case HAMMER2_BREF_TYPE_INODE:
3129                         base = &parent->data->ipdata.u.blockset.blockref[0];
3130                         count = HAMMER2_SET_COUNT;
3131                         break;
3132                 case HAMMER2_BREF_TYPE_INDIRECT:
3133                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
3134                         base = &parent->data->npdata[0];
3135                         count = parent->bytes / sizeof(hammer2_blockref_t);
3136                         break;
3137                 case HAMMER2_BREF_TYPE_VOLUME:
3138                         base = &hmp->voldata.sroot_blockset.blockref[0];
3139                         count = HAMMER2_SET_COUNT;
3140                         break;
3141                 case HAMMER2_BREF_TYPE_FREEMAP:
3142                         base = &hmp->voldata.freemap_blockset.blockref[0];
3143                         count = HAMMER2_SET_COUNT;
3144                         break;
3145                 default:
3146                         panic("hammer2_chain_create_indirect: "
3147                               "unrecognized blockref type: %d",
3148                               parent->bref.type);
3149                         count = 0;
3150                         break;
3151                 }
3152         }
3153
3154         /*
3155          * dummy used in later chain allocation (no longer used for lookups).
3156          */
3157         bzero(&dummy, sizeof(dummy));
3158         dummy.delete_tid = HAMMER2_MAX_TID;
3159
3160         /*
3161          * When creating an indirect block for a freemap node or leaf
3162          * the key/keybits must be fitted to static radix levels because
3163          * particular radix levels use particular reserved blocks in the
3164          * related zone.
3165          *
3166          * This routine calculates the key/radix of the indirect block
3167          * we need to create, and whether it is on the high-side or the
3168          * low-side.
3169          */
3170         if (for_type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
3171             for_type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
3172                 keybits = hammer2_chain_indkey_freemap(parent, &key, keybits,
3173                                                        base, count);
3174         } else {
3175                 keybits = hammer2_chain_indkey_normal(parent, &key, keybits,
3176                                                       base, count);
3177         }
3178
3179         /*
3180          * Normalize the key for the radix being represented, keeping the
3181          * high bits and throwing away the low bits.
3182          */
3183         key &= ~(((hammer2_key_t)1 << keybits) - 1);
3184
3185         /*
3186          * How big should our new indirect block be?  It has to be at least
3187          * as large as its parent.
3188          */
3189         if (parent->bref.type == HAMMER2_BREF_TYPE_INODE)
3190                 nbytes = HAMMER2_IND_BYTES_MIN;
3191         else
3192                 nbytes = HAMMER2_IND_BYTES_MAX;
3193         if (nbytes < count * sizeof(hammer2_blockref_t))
3194                 nbytes = count * sizeof(hammer2_blockref_t);
3195
3196         /*
3197          * Ok, create our new indirect block
3198          */
3199         if (for_type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
3200             for_type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
3201                 dummy.bref.type = HAMMER2_BREF_TYPE_FREEMAP_NODE;
3202         } else {
3203                 dummy.bref.type = HAMMER2_BREF_TYPE_INDIRECT;
3204         }
3205         dummy.bref.key = key;
3206         dummy.bref.keybits = keybits;
3207         dummy.bref.data_off = hammer2_getradix(nbytes);
3208         dummy.bref.methods = parent->bref.methods;
3209
3210         ichain = hammer2_chain_alloc(hmp, trans, &dummy.bref);
3211         atomic_set_int(&ichain->flags, HAMMER2_CHAIN_INITIAL);
3212         hammer2_chain_core_alloc(ichain, NULL);
3213         icore = ichain->core;
3214         hammer2_chain_lock(ichain, HAMMER2_RESOLVE_MAYBE);
3215         hammer2_chain_drop(ichain);     /* excess ref from alloc */
3216
3217         /*
3218          * We have to mark it modified to allocate its block, but use
3219          * OPTDATA to allow it to remain in the INITIAL state.  Otherwise
3220          * it won't be acted upon by the flush code.
3221          *
3222          * XXX leave the node unmodified, depend on the SUBMODIFIED
3223          * flush to assign and modify parent blocks.
3224          */
3225         hammer2_chain_modify(trans, &ichain, HAMMER2_MODIFY_OPTDATA);
3226
3227         /*
3228          * Iterate the original parent and move the matching brefs into
3229          * the new indirect block.
3230          *
3231          * At the same time locate an empty slot (or what will become an
3232          * empty slot) and assign the new indirect block to that slot.
3233          *
3234          * XXX handle flushes.
3235          */
3236         spin_lock(&above->cst.spin);
3237         for (i = 0; i < count; ++i) {
3238                 /*
3239                  * For keying purposes access the bref from the media or
3240                  * from our in-memory cache.  In cases where the in-memory
3241                  * cache overrides the media the keyrefs will be the same
3242                  * anyway so we can avoid checking the cache when the media
3243                  * has a key.
3244                  */
3245                 child = hammer2_chain_find_locked(parent, i);
3246                 if (child) {
3247                         if (child->flags & HAMMER2_CHAIN_DELETED) {
3248                                 if (ichain->index < 0)
3249                                         ichain->index = i;
3250                                 continue;
3251                         }
3252                         bref = &child->bref;
3253                 } else if (base && base[i].type) {
3254                         bref = &base[i];
3255                 } else {
3256                         if (ichain->index < 0)
3257                                 ichain->index = i;
3258                         continue;
3259                 }
3260
3261                 /*
3262                  * Skip keys that are not within the key/radix of the new
3263                  * indirect block.  They stay in the parent.
3264                  */
3265                 if ((~(((hammer2_key_t)1 << keybits) - 1) &
3266                     (key ^ bref->key)) != 0) {
3267                         continue;
3268                 }
3269
3270                 /*
3271                  * This element is being moved from the parent, its slot
3272                  * is available for our new indirect block.
3273                  */
3274                 if (ichain->index < 0)
3275                         ichain->index = i;
3276
3277                 /*
3278                  * Load the new indirect block by acquiring or allocating
3279                  * the related chain entries, then move them to the new
3280                  * parent (ichain) by deleting them from their old location
3281                  * and inserting a duplicate of the chain and any modified
3282                  * sub-chain in the new location.
3283                  *
3284                  * We must set MOVED in the chain being duplicated and
3285                  * SUBMODIFIED in the parent(s) so the flush code knows
3286                  * what is going on.  The latter is done after the loop.
3287                  *
3288                  * WARNING! above->cst.spin must be held when parent is
3289                  *          modified, even though we own the full blown lock,
3290                  *          to deal with setsubmod and rename races.
3291                  *          (XXX remove this req).
3292                  */
3293                 spin_unlock(&above->cst.spin);
3294                 chain = hammer2_chain_get(parent, i, HAMMER2_LOOKUP_NODATA);
3295                 hammer2_chain_delete(trans, chain, HAMMER2_DELETE_WILLDUP);
3296                 hammer2_chain_duplicate(trans, ichain, i, &chain, NULL);
3297                 hammer2_chain_unlock(chain);
3298                 KKASSERT(parent->refs > 0);
3299                 chain = NULL;
3300                 spin_lock(&above->cst.spin);
3301         }
3302         spin_unlock(&above->cst.spin);
3303
3304         /*
3305          * Insert the new indirect block into the parent now that we've
3306          * cleared out some entries in the parent.  We calculated a good
3307          * insertion index in the loop above (ichain->index).
3308          *
3309          * We don't have to set MOVED here because we mark ichain modified
3310          * down below (so the normal modified -> flush -> set-moved sequence
3311          * applies).
3312          *
3313          * The insertion shouldn't race as this is a completely new block
3314          * and the parent is locked.
3315          */
3316         if (ichain->index < 0)
3317                 kprintf("indirect parent %p count %d key %016jx/%d\n",
3318                         parent, count, (intmax_t)key, keybits);
3319         KKASSERT(ichain->index >= 0);
3320         KKASSERT((ichain->flags & HAMMER2_CHAIN_ONRBTREE) == 0);
3321         spin_lock(&above->cst.spin);
3322         if (RB_INSERT(hammer2_chain_tree, &above->rbtree, ichain))
3323                 panic("hammer2_chain_create_indirect: ichain insertion");
3324         atomic_set_int(&ichain->flags, HAMMER2_CHAIN_ONRBTREE);
3325         ichain->above = above;
3326         spin_unlock(&above->cst.spin);
3327
3328         /*
3329          * Mark the new indirect block modified after insertion, which
3330          * will propagate up through parent all the way to the root and
3331          * also allocate the physical block in ichain for our caller,
3332          * and assign ichain->data to a pre-zero'd space (because there
3333          * is not prior data to copy into it).
3334          *
3335          * We have to set SUBMODIFIED in ichain's flags manually so the
3336          * flusher knows it has to recurse through it to get to all of
3337          * our moved blocks, then call setsubmod() to set the bit
3338          * recursively.
3339          */
3340         /*hammer2_chain_modify(trans, &ichain, HAMMER2_MODIFY_OPTDATA);*/
3341         atomic_set_int(&ichain->flags, HAMMER2_CHAIN_SUBMODIFIED);
3342         hammer2_chain_setsubmod(trans, ichain);
3343
3344         /*
3345          * Figure out what to return.
3346          */
3347         if (~(((hammer2_key_t)1 << keybits) - 1) &
3348                    (create_key ^ key)) {
3349                 /*
3350                  * Key being created is outside the key range,
3351                  * return the original parent.
3352                  */
3353                 hammer2_chain_unlock(ichain);
3354         } else {
3355                 /*
3356                  * Otherwise its in the range, return the new parent.
3357                  * (leave both the new and old parent locked).
3358                  */
3359                 parent = ichain;
3360         }
3361
3362         return(parent);
3363 }
3364
3365 /*
3366  * Calculate the keybits and highside/lowside of the freemap node the
3367  * caller is creating.
3368  *
3369  * This routine will specify the next higher-level freemap key/radix
3370  * representing the lowest-ordered set.  By doing so, eventually all
3371  * low-ordered sets will be moved one level down.
3372  *
3373  * We have to be careful here because the freemap reserves a limited
3374  * number of blocks for a limited number of levels.  So we can't just
3375  * push indiscriminately.
3376  */
3377 int
3378 hammer2_chain_indkey_freemap(hammer2_chain_t *parent, hammer2_key_t *keyp,
3379                              int keybits, hammer2_blockref_t *base, int count)
3380 {
3381         hammer2_chain_core_t *above;
3382         hammer2_chain_t *child;
3383         hammer2_blockref_t *bref;
3384         hammer2_key_t key;
3385         int locount;
3386         int hicount;
3387         int i;
3388
3389         key = *keyp;
3390         above = parent->core;
3391         locount = 0;
3392         hicount = 0;
3393         keybits = 64;
3394
3395         /*
3396          * Calculate the range of keys in the array being careful to skip
3397          * slots which are overridden with a deletion.
3398          */
3399         spin_lock(&above->cst.spin);
3400         for (i = 0; i < count; ++i) {
3401                 child = hammer2_chain_find_locked(parent, i);
3402                 if (child) {
3403                         if (child->flags & HAMMER2_CHAIN_DELETED)
3404                                 continue;
3405                         bref = &child->bref;
3406                 } else if (base && base[i].type) {
3407                         bref = &base[i];
3408                 } else {
3409                         continue;
3410                 }
3411
3412                 if (keybits > bref->keybits) {
3413                         key = bref->key;
3414                         keybits = bref->keybits;
3415                 } else if (keybits == bref->keybits && bref->key < key) {
3416                         key = bref->key;
3417                 }
3418         }
3419         spin_unlock(&above->cst.spin);
3420
3421         /*
3422          * Return the keybits for a higher-level FREEMAP_NODE covering
3423          * this node.
3424          */
3425         switch(keybits) {
3426         case HAMMER2_FREEMAP_LEVEL0_RADIX:
3427                 keybits = HAMMER2_FREEMAP_LEVEL1_RADIX;
3428                 break;
3429         case HAMMER2_FREEMAP_LEVEL1_RADIX:
3430                 keybits = HAMMER2_FREEMAP_LEVEL2_RADIX;
3431                 break;
3432         case HAMMER2_FREEMAP_LEVEL2_RADIX:
3433                 keybits = HAMMER2_FREEMAP_LEVEL3_RADIX;
3434                 break;
3435         case HAMMER2_FREEMAP_LEVEL3_RADIX:
3436                 keybits = HAMMER2_FREEMAP_LEVEL4_RADIX;
3437                 break;
3438         case HAMMER2_FREEMAP_LEVEL4_RADIX:
3439                 panic("hammer2_chain_indkey_freemap: level too high");
3440                 break;
3441         default:
3442                 panic("hammer2_chain_indkey_freemap: bad radix");
3443                 break;
3444         }
3445         *keyp = key;
3446
3447         return (keybits);
3448 }
3449
3450 /*
3451  * Calculate the keybits and highside/lowside of the indirect block the
3452  * caller is creating.
3453  */
3454 static int
3455 hammer2_chain_indkey_normal(hammer2_chain_t *parent, hammer2_key_t *keyp,
3456                             int keybits, hammer2_blockref_t *base, int count)
3457 {
3458         hammer2_chain_core_t *above;
3459         hammer2_chain_t *child;
3460         hammer2_blockref_t *bref;
3461         hammer2_key_t key;
3462         int nkeybits;
3463         int locount;
3464         int hicount;
3465         int i;
3466
3467         key = *keyp;
3468         above = parent->core;
3469         locount = 0;
3470         hicount = 0;
3471
3472         /*
3473          * Calculate the range of keys in the array being careful to skip
3474          * slots which are overridden with a deletion.  Once the scan
3475          * completes we will cut the key range in half and shift half the
3476          * range into the new indirect block.
3477          */
3478         spin_lock(&above->cst.spin);
3479         for (i = 0; i < count; ++i) {
3480                 child = hammer2_chain_find_locked(parent, i);
3481                 if (child) {
3482                         if (child->flags & HAMMER2_CHAIN_DELETED)
3483                                 continue;
3484                         bref = &child->bref;
3485                 } else if (base && base[i].type) {
3486                         bref = &base[i];
3487                 } else {
3488                         continue;
3489                 }
3490
3491                 /*
3492                  * Expand our calculated key range (key, keybits) to fit
3493                  * the scanned key.  nkeybits represents the full range
3494                  * that we will later cut in half (two halves @ nkeybits - 1).
3495                  */
3496                 nkeybits = keybits;
3497                 if (nkeybits < bref->keybits) {
3498                         if (bref->keybits > 64) {
3499                                 kprintf("bad bref index %d chain %p bref %p\n",
3500                                         i, child, bref);
3501                                 Debugger("fubar");
3502                         }
3503                         nkeybits = bref->keybits;
3504                 }
3505                 while (nkeybits < 64 &&
3506                        (~(((hammer2_key_t)1 << nkeybits) - 1) &
3507                         (key ^ bref->key)) != 0) {
3508                         ++nkeybits;
3509                 }
3510
3511                 /*
3512                  * If the new key range is larger we have to determine
3513                  * which side of the new key range the existing keys fall
3514                  * under by checking the high bit, then collapsing the
3515                  * locount into the hicount or vise-versa.
3516                  */
3517                 if (keybits != nkeybits) {
3518                         if (((hammer2_key_t)1 << (nkeybits - 1)) & key) {
3519                                 hicount += locount;
3520                                 locount = 0;
3521                         } else {
3522                                 locount += hicount;
3523                                 hicount = 0;
3524                         }
3525                         keybits = nkeybits;
3526                 }
3527
3528                 /*
3529                  * The newly scanned key will be in the lower half or the
3530                  * higher half of the (new) key range.
3531                  */
3532                 if (((hammer2_key_t)1 << (nkeybits - 1)) & bref->key)
3533                         ++hicount;
3534                 else
3535                         ++locount;
3536         }
3537         spin_unlock(&above->cst.spin);
3538         bref = NULL;    /* now invalid (safety) */
3539
3540         /*
3541          * Adjust keybits to represent half of the full range calculated
3542          * above (radix 63 max)
3543          */
3544         --keybits;
3545
3546         /*
3547          * Select whichever half contains the most elements.  Theoretically
3548          * we can select either side as long as it contains at least one
3549          * element (in order to ensure that a free slot is present to hold
3550          * the indirect block).
3551          */
3552         if (hammer2_indirect_optimize) {
3553                 /*
3554                  * Insert node for least number of keys, this will arrange
3555                  * the first few blocks of a large file or the first few
3556                  * inodes in a directory with fewer indirect blocks when
3557                  * created linearly.
3558                  */
3559                 if (hicount < locount && hicount != 0)
3560                         key |= (hammer2_key_t)1 << keybits;
3561                 else
3562                         key &= ~(hammer2_key_t)1 << keybits;
3563         } else {
3564                 /*
3565                  * Insert node for most number of keys, best for heavily
3566                  * fragmented files.
3567                  */
3568                 if (hicount > locount)
3569                         key |= (hammer2_key_t)1 << keybits;
3570                 else
3571                         key &= ~(hammer2_key_t)1 << keybits;
3572         }
3573         *keyp = key;
3574
3575         return (keybits);
3576 }
3577
3578 /*
3579  * Sets CHAIN_DELETED and CHAIN_MOVED in the chain being deleted and
3580  * set chain->delete_tid.
3581  *
3582  * This function does NOT generate a modification to the parent.  It
3583  * would be nearly impossible to figure out which parent to modify anyway.
3584  * Such modifications are handled by the flush code and are properly merged
3585  * using the flush synchronization point.
3586  *
3587  * The find/get code will properly overload the RBTREE check on top of
3588  * the bref check to detect deleted entries.
3589  *
3590  * This function is NOT recursive.  Any entity already pushed into the
3591  * chain (such as an inode) may still need visibility into its contents,
3592  * as well as the ability to read and modify the contents.  For example,
3593  * for an unlinked file which is still open.
3594  *
3595  * NOTE: This function does NOT set chain->modify_tid, allowing future
3596  *       code to distinguish between live and deleted chains by testing
3597  *       sync_tid.
3598  *
3599  * NOTE: Deletions normally do not occur in the middle of a duplication
3600  *       chain but we use a trick for hardlink migration that refactors
3601  *       the originating inode without deleting it, so we make no assumptions
3602  *       here.
3603  */
3604 void
3605 hammer2_chain_delete(hammer2_trans_t *trans, hammer2_chain_t *chain, int flags)
3606 {
3607         KKASSERT(ccms_thread_lock_owned(&chain->core->cst));
3608
3609         /*
3610          * Nothing to do if already marked.
3611          */
3612         if (chain->flags & HAMMER2_CHAIN_DELETED)
3613                 return;
3614
3615         /*
3616          * We must set MOVED along with DELETED for the flush code to
3617          * recognize the operation and properly disconnect the chain
3618          * in-memory.
3619          *
3620          * The setting of DELETED causes finds, lookups, and _next iterations
3621          * to no longer recognize the chain.  RB_SCAN()s will still have
3622          * visibility (needed for flush serialization points).
3623          *
3624          * We need the spinlock on the core whos RBTREE contains chain
3625          * to protect against races.
3626          */
3627         spin_lock(&chain->above->cst.spin);
3628         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DELETED);
3629         if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
3630                 hammer2_chain_ref(chain);
3631                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
3632         }
3633         chain->delete_tid = trans->sync_tid;
3634         spin_unlock(&chain->above->cst.spin);
3635
3636         /*
3637          * Mark the underlying block as possibly being free unless WILLDUP
3638          * is set.  Duplication can occur in many situations, particularly
3639          * when chains are moved to indirect blocks.
3640          */
3641         if ((flags & HAMMER2_DELETE_WILLDUP) == 0)
3642                 hammer2_freemap_free(trans, chain->hmp, &chain->bref, 0);
3643         hammer2_chain_setsubmod(trans, chain);
3644 }
3645
3646 void
3647 hammer2_chain_wait(hammer2_chain_t *chain)
3648 {
3649         tsleep(chain, 0, "chnflw", 1);
3650 }
3651
3652 static
3653 void
3654 adjreadcounter(hammer2_blockref_t *bref, size_t bytes)
3655 {
3656         long *counterp;
3657
3658         switch(bref->type) {
3659         case HAMMER2_BREF_TYPE_DATA:
3660                 counterp = &hammer2_iod_file_read;
3661                 break;
3662         case HAMMER2_BREF_TYPE_INODE:
3663                 counterp = &hammer2_iod_meta_read;
3664                 break;
3665         case HAMMER2_BREF_TYPE_INDIRECT:
3666                 counterp = &hammer2_iod_indr_read;
3667                 break;
3668         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
3669         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
3670                 counterp = &hammer2_iod_fmap_read;
3671                 break;
3672         default:
3673                 counterp = &hammer2_iod_volu_read;
3674                 break;
3675         }
3676         *counterp += bytes;
3677 }