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