sys/vfs/hammer2/hammer2_chain.c

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