sys/vfs/hammer2/hammer2_chain.c

   1 /*
   2  * Copyright (c) 2011-2012 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 handles direct and indirect block searches, recursions,
  37  * creation, and deletion.  Chains of blockrefs are tracked and modifications
  38  * are flag for propagation... eventually all the way back to the volume
  39  * header.
  40  */
  41
  42 #include <sys/cdefs.h>
  43 #include <sys/param.h>
  44 #include <sys/systm.h>
  45 #include <sys/types.h>
  46 #include <sys/lock.h>
  47 #include <sys/uuid.h>
  48
  49 #include "hammer2.h"
  50
  51 static int hammer2_indirect_optimize;   /* XXX SYSCTL */
  52
  53 static hammer2_chain_t *hammer2_chain_create_indirect(
  54                         hammer2_mount_t *hmp, hammer2_chain_t *parent,
  55                         hammer2_key_t key, int keybits);
  56
  57 /*
  58  * Splay tree
  59  */
  60 SPLAY_GENERATE(hammer2_chain_splay, hammer2_chain, snode, hammer2_chain_cmp);
  61
  62 int
  63 hammer2_chain_cmp(hammer2_chain_t *chain1, hammer2_chain_t *chain2)
  64 {
  65         return(chain2->index - chain1->index);
  66 }
  67
  68 /*
  69  * Recursively mark the parent chain elements so flushes can find
  70  * modified elements.
  71  *
  72  * NOTE: The flush code will modify a SUBMODIFIED-flagged chain
  73  *       during the flush recursion after clearing the parent's
  74  *       SUBMODIFIED bit.  We don't want to re-set the parent's
  75  *       SUBMODIFIED bit in this case!
  76  *
  77  * XXX rename of parent can create a SMP race
  78  */
  79 static void
  80 hammer2_chain_parent_setsubmod(hammer2_mount_t *hmp, hammer2_chain_t *chain)
  81 {
  82         hammer2_chain_t *parent;
  83
  84         if ((chain->flags & HAMMER2_CHAIN_SUBMODIFIED) == 0) {
  85                 parent = chain->parent;
  86                 while (parent &&
  87                        (parent->flags & HAMMER2_CHAIN_SUBMODIFIED) == 0) {
  88                         atomic_set_int(&parent->flags,
  89                                        HAMMER2_CHAIN_SUBMODIFIED);
  90                         parent = parent->parent;
  91                 }
  92         }
  93 }
  94
  95 /*
  96  * Allocate a new disconnected chain element representing the specified
  97  * bref.  The chain element is locked exclusively and refs is set to 1.
  98  *
  99  * This essentially allocates a system memory structure representing one
 100  * of the media structure types, including inodes.
 101  */
 102 hammer2_chain_t *
 103 hammer2_chain_alloc(hammer2_mount_t *hmp, hammer2_blockref_t *bref)
 104 {
 105         hammer2_chain_t *chain;
 106         hammer2_inode_t *ip;
 107         hammer2_indblock_t *np;
 108         hammer2_data_t *dp;
 109         u_int bytes = 1U << (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
 110
 111         /*
 112          * Construct the appropriate system structure.
 113          */
 114         switch(bref->type) {
 115         case HAMMER2_BREF_TYPE_INODE:
 116                 ip = kmalloc(sizeof(*ip), hmp->minode, M_WAITOK | M_ZERO);
 117                 chain = &ip->chain;
 118                 chain->u.ip = ip;
 119                 lockinit(&chain->lk, "inode", 0, LK_CANRECURSE);
 120                 ip->hmp = hmp;
 121                 break;
 122         case HAMMER2_BREF_TYPE_INDIRECT:
 123                 np = kmalloc(sizeof(*np), hmp->mchain, M_WAITOK | M_ZERO);
 124                 chain = &np->chain;
 125                 chain->u.np = np;
 126                 lockinit(&chain->lk, "iblk", 0, LK_CANRECURSE);
 127                 break;
 128         case HAMMER2_BREF_TYPE_DATA:
 129                 dp = kmalloc(sizeof(*dp), hmp->mchain, M_WAITOK | M_ZERO);
 130                 chain = &dp->chain;
 131                 chain->u.dp = dp;
 132                 lockinit(&chain->lk, "dblk", 0, LK_CANRECURSE);
 133                 break;
 134         case HAMMER2_BREF_TYPE_VOLUME:
 135                 chain = NULL;
 136                 panic("hammer2_chain_alloc volume type illegal for op");
 137         default:
 138                 chain = NULL;
 139                 panic("hammer2_chain_alloc: unrecognized blockref type: %d",
 140                       bref->type);
 141         }
 142         chain->bref = *bref;
 143         chain->index = -1;      /* not yet assigned */
 144         chain->refs = 1;
 145         chain->bytes = bytes;
 146         lockmgr(&chain->lk, LK_EXCLUSIVE);
 147
 148         return (chain);
 149 }
 150
 151 /*
 152  * Free a disconnected chain element
 153  */
 154 void
 155 hammer2_chain_free(hammer2_mount_t *hmp, hammer2_chain_t *chain)
 156 {
 157         void *mem;
 158
 159         if (chain->bref.type == HAMMER2_BREF_TYPE_INODE ||
 160             chain->bref.type == HAMMER2_BREF_TYPE_VOLUME) {
 161                 chain->data = NULL;
 162         }
 163
 164         KKASSERT(chain->bp == NULL);
 165         KKASSERT(chain->data == NULL);
 166         KKASSERT(chain->bref.type != HAMMER2_BREF_TYPE_INODE ||
 167                  chain->u.ip->vp == NULL);
 168
 169         if ((mem = chain->u.mem) != NULL) {
 170                 chain->u.mem = NULL;
 171                 if (chain->bref.type == HAMMER2_BREF_TYPE_INODE)
 172                         kfree(mem, hmp->minode);
 173                 else
 174                         kfree(mem, hmp->mchain);
 175         }
 176 }
 177
 178 /*
 179  * Add a reference to a chain element (for shared access).  The chain
 180  * element must already have at least 1 ref controlled by the caller.
 181  */
 182 void
 183 hammer2_chain_ref(hammer2_mount_t *hmp, hammer2_chain_t *chain)
 184 {
 185         KKASSERT(chain->refs > 0);
 186         atomic_add_int(&chain->refs, 1);
 187 }
 188
 189 /*
 190  * Drop the callers reference to the chain element.  If the ref count
 191  * reaches zero the chain element and its related structure (typically an
 192  * inode or indirect block) will be freed and the parent will be
 193  * recursively dropped.
 194  *
 195  * Modified elements hold an additional reference so it should not be
 196  * possible for the count on a modified element to drop to 0.
 197  *
 198  * The chain element must NOT be locked by the caller.
 199  *
 200  * The parent might or might not be locked by the caller but if so it
 201  * will also be referenced so we shouldn't recurse upward.
 202  */
 203 void
 204 hammer2_chain_drop(hammer2_mount_t *hmp, hammer2_chain_t *chain)
 205 {
 206         hammer2_chain_t *parent;
 207         u_int refs;
 208
 209         while (chain) {
 210                 refs = chain->refs;
 211                 cpu_ccfence();
 212                 KKASSERT(refs > 0);
 213                 if (refs == 1) {
 214                         KKASSERT(chain != &hmp->vchain);
 215                         parent = chain->parent;
 216                         if (parent)
 217                                 lockmgr(&parent->lk, LK_EXCLUSIVE);
 218                         if (atomic_cmpset_int(&chain->refs, 1, 0)) {
 219                                 /*
 220                                  * Succeeded, recurse and drop parent
 221                                  */
 222                                 if (!(chain->flags & HAMMER2_CHAIN_DELETED)) {
 223                                         SPLAY_REMOVE(hammer2_chain_splay,
 224                                                      &parent->shead, chain);
 225                                         atomic_set_int(&chain->flags,
 226                                                        HAMMER2_CHAIN_DELETED);
 227                                         /* parent refs dropped via recursion */
 228                                 }
 229                                 chain->parent = NULL;
 230                                 if (parent)
 231                                         lockmgr(&parent->lk, LK_RELEASE);
 232                                 hammer2_chain_free(hmp, chain);
 233                                 chain = parent;
 234                                 /* recurse on parent */
 235                         } else {
 236                                 if (parent)
 237                                         lockmgr(&parent->lk, LK_RELEASE);
 238                                 /* retry the same chain */
 239                         }
 240                 } else {
 241                         if (atomic_cmpset_int(&chain->refs, refs, refs - 1)) {
 242                                 /*
 243                                  * Succeeded, count did not reach zero so
 244                                  * cut out of the loop.
 245                                  */
 246                                 break;
 247                         }
 248                         /* retry the same chain */
 249                 }
 250         }
 251 }
 252
 253 /*
 254  * Ref and lock a chain element, acquiring its data with I/O if necessary,
 255  * and specify how you would like the data to be resolved.
 256  *
 257  * Returns 0 on success or an error code if the data could not be acquired.
 258  * The chain element is locked either way.
 259  *
 260  * The lock is allowed to recurse, multiple locking ops will aggregate
 261  * the requested resolve types.  Once data is assigned it will not be
 262  * removed until the last unlock.
 263  *
 264  * HAMMER2_RESOLVE_NEVER - Do not resolve the data element.
 265  *                         (typically used to avoid device/logical buffer
 266  *                          aliasing for data)
 267  *
 268  * HAMMER2_RESOLVE_MAYBE - Do not resolve data elements for chains in
 269  *                         the INITIAL-create state (indirect blocks only).
 270  *
 271  *                         Do not resolve data elements for DATA chains.
 272  *                         (typically used to avoid device/logical buffer
 273  *                          aliasing for data)
 274  *
 275  * HAMMER2_RESOLVE_ALWAYS- Always resolve the data element.
 276  *
 277  *
 278  * NOTE: Embedded elements (volume header, inodes) are always resolved
 279  *       regardless.
 280  *
 281  * NOTE: Specifying HAMMER2_RESOLVE_ALWAYS on a newly-created non-embedded
 282  *       element will instantiate and zero its buffer, and flush it on
 283  *       release.
 284  *
 285  * NOTE: (data) elements are normally locked RESOLVE_NEVER or RESOLVE_MAYBE
 286  *       so as not to instantiate a device buffer, which could alias against
 287  *       a logical file buffer.  However, if ALWAYS is specified the
 288  *       device buffer will be instantiated anyway.
 289  */
 290 int
 291 hammer2_chain_lock(hammer2_mount_t *hmp, hammer2_chain_t *chain, int how)
 292 {
 293         hammer2_blockref_t *bref;
 294         hammer2_off_t pbase;
 295         hammer2_off_t peof;
 296         size_t boff;
 297         size_t bbytes;
 298         int error;
 299         char *bdata;
 300
 301         /*
 302          * Lock the element.  Under certain conditions this might end up
 303          * being a recursive lock.
 304          */
 305         KKASSERT(chain->refs > 0);
 306         atomic_add_int(&chain->refs, 1);
 307         lockmgr(&chain->lk, LK_EXCLUSIVE);
 308
 309         /*
 310          * If we already have a valid data pointer no further action is
 311          * necessary.
 312          */
 313         if (chain->data)
 314                 return (0);
 315
 316         /*
 317          * Do we have to resolve the data?
 318          */
 319         switch(how) {
 320         case HAMMER2_RESOLVE_NEVER:
 321                 return(0);
 322         case HAMMER2_RESOLVE_MAYBE:
 323                 if (chain->flags & HAMMER2_CHAIN_INITIAL)
 324                         return(0);
 325                 if (chain->bref.type == HAMMER2_BREF_TYPE_DATA)
 326                         return(0);
 327                 /* fall through */
 328         case HAMMER2_RESOLVE_ALWAYS:
 329                 break;
 330         }
 331
 332         /*
 333          * We must resolve to a device buffer, either by issuing I/O or
 334          * by creating a zero-fill element.  We do not mark the buffer
 335          * dirty when creating a zero-fill element (the hammer2_chain_modify()
 336          * API must still be used to do that).
 337          *
 338          * The device buffer is variable-sized in powers of 2 down
 339          * to HAMMER2_MINALLOCSIZE (typically 1K).  A 64K physical storage
 340          * chunk always contains buffers of the same size. (XXX)
 341          *
 342          * The minimum physical IO size may be larger than the variable
 343          * block size.
 344          */
 345         bref = &chain->bref;
 346
 347         if ((bbytes = chain->bytes) < HAMMER2_MINIOSIZE)
 348                 bbytes = HAMMER2_MINIOSIZE;
 349         pbase = bref->data_off & ~(hammer2_off_t)(bbytes - 1);
 350         peof = (pbase + HAMMER2_PBUFSIZE64) & ~HAMMER2_PBUFMASK64;
 351         boff = bref->data_off & HAMMER2_OFF_MASK & (bbytes - 1);
 352         KKASSERT(pbase != 0);
 353
 354         /*
 355          * The getblk() optimization can only be used on newly created
 356          * elements if the physical block size matches the request.
 357          */
 358         if ((chain->flags & HAMMER2_CHAIN_INITIAL) &&
 359             chain->bytes == bbytes) {
 360                 chain->bp = getblk(hmp->devvp, pbase, bbytes, 0, 0);
 361                 error = 0;
 362         } else if (hammer2_cluster_enable) {
 363                 error = cluster_read(hmp->devvp, peof, pbase, bbytes,
 364                                      HAMMER2_PBUFSIZE, HAMMER2_PBUFSIZE,
 365                                      &chain->bp);
 366         } else {
 367                 error = bread(hmp->devvp, pbase, bbytes, &chain->bp);
 368         }
 369
 370         if (error) {
 371                 kprintf("hammer2_chain_get: I/O error %016jx: %d\n",
 372                         (intmax_t)pbase, error);
 373                 bqrelse(chain->bp);
 374                 chain->bp = NULL;
 375                 return (error);
 376         }
 377
 378         /*
 379          * Zero the data area if the chain is in the INITIAL-create state
 380          */
 381         bdata = (char *)chain->bp->b_data + boff;
 382         if (chain->flags & HAMMER2_CHAIN_INITIAL)
 383                 bzero(bdata, chain->bytes);
 384
 385         /*
 386          * Setup the data pointer, either pointing it to an embedded data
 387          * structure and copying the data from the buffer, or pointing it
 388          * into the buffer.
 389          *
 390          * The buffer is not retained when copying to an embedded data
 391          * structure in order to avoid potential deadlocks or recursions
 392          * on the same physical buffer.
 393          */
 394         switch (bref->type) {
 395         case HAMMER2_BREF_TYPE_VOLUME:
 396                 /*
 397                  * Copy data from bp to embedded buffer
 398                  */
 399                 panic("hammer2_chain_lock: called on unresolved volume header");
 400 #if 0
 401                 /* NOT YET */
 402                 KKASSERT(pbase == 0);
 403                 KKASSERT(chain->bytes == HAMMER2_PBUFSIZE);
 404                 bcopy(bdata, &hmp->voldata, chain->bytes);
 405                 chain->data = (void *)&hmp->voldata;
 406                 bqrelse(chain->bp);
 407                 chain->bp = NULL;
 408 #endif
 409                 break;
 410         case HAMMER2_BREF_TYPE_INODE:
 411                 /*
 412                  * Copy data from bp to embedded buffer, do not retain the
 413                  * device buffer.
 414                  */
 415                 bcopy(bdata, &chain->u.ip->ip_data, chain->bytes);
 416                 chain->data = (void *)&chain->u.ip->ip_data;
 417                 bqrelse(chain->bp);
 418                 chain->bp = NULL;
 419                 break;
 420         case HAMMER2_BREF_TYPE_INDIRECT:
 421         case HAMMER2_BREF_TYPE_DATA:
 422         default:
 423                 /*
 424                  * Point data at the device buffer and leave bp intact.
 425                  */
 426                 chain->data = (void *)bdata;
 427                 break;
 428         }
 429         return (0);
 430 }
 431
 432 /*
 433  * Unlock and deref a chain element.
 434  *
 435  * On the last lock release any non-embedded data (chain->bp) will be
 436  * retired.
 437  */
 438 void
 439 hammer2_chain_unlock(hammer2_mount_t *hmp, hammer2_chain_t *chain)
 440 {
 441         long *counterp;
 442
 443         /*
 444          * Undo a recursive lock
 445          */
 446         if (lockcountnb(&chain->lk) > 1) {
 447                 KKASSERT(chain->refs > 1);
 448                 atomic_add_int(&chain->refs, -1);
 449                 lockmgr(&chain->lk, LK_RELEASE);
 450                 return;
 451         }
 452
 453         /*
 454          * Shortcut the case if the data is embedded or not resolved.
 455          * Do NOT null-out pointers to embedded data (e.g. inode).
 456          */
 457         if (chain->bp == NULL) {
 458                 lockmgr(&chain->lk, LK_RELEASE);
 459                 hammer2_chain_drop(hmp, chain);
 460                 return;
 461         }
 462
 463         /*
 464          * Statistics
 465          */
 466         if ((chain->flags & HAMMER2_CHAIN_DIRTYBP) == 0) {
 467                 ;
 468         } else if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 469                 switch(chain->bref.type) {
 470                 case HAMMER2_BREF_TYPE_DATA:
 471                         counterp = &hammer2_ioa_file_write;
 472                         break;
 473                 case HAMMER2_BREF_TYPE_INODE:
 474                         counterp = &hammer2_ioa_meta_write;
 475                         break;
 476                 case HAMMER2_BREF_TYPE_INDIRECT:
 477                         counterp = &hammer2_ioa_indr_write;
 478                         break;
 479                 default:
 480                         counterp = &hammer2_ioa_volu_write;
 481                         break;
 482                 }
 483                 ++*counterp;
 484         } else {
 485                 switch(chain->bref.type) {
 486                 case HAMMER2_BREF_TYPE_DATA:
 487                         counterp = &hammer2_iod_file_write;
 488                         break;
 489                 case HAMMER2_BREF_TYPE_INODE:
 490                         counterp = &hammer2_iod_meta_write;
 491                         break;
 492                 case HAMMER2_BREF_TYPE_INDIRECT:
 493                         counterp = &hammer2_iod_indr_write;
 494                         break;
 495                 default:
 496                         counterp = &hammer2_iod_volu_write;
 497                         break;
 498                 }
 499                 ++*counterp;
 500         }
 501
 502         /*
 503          * Clean out the bp.
 504          *
 505          * If a device buffer was used for data be sure to destroy the
 506          * buffer when we are done to avoid aliases (XXX what about the
 507          * underlying VM pages?).
 508          */
 509         if (chain->bref.type == HAMMER2_BREF_TYPE_DATA)
 510                 chain->bp->b_flags |= B_RELBUF;
 511
 512         chain->data = NULL;
 513         if (chain->flags & HAMMER2_CHAIN_DIRTYBP) {
 514                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 515                 if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 516                         atomic_clear_int(&chain->flags,
 517                                          HAMMER2_CHAIN_IOFLUSH);
 518                         chain->bp->b_flags |= B_RELBUF;
 519                         cluster_awrite(chain->bp);
 520                 } else {
 521                         chain->bp->b_flags |= B_CLUSTEROK;
 522                         bdwrite(chain->bp);
 523                 }
 524         } else {
 525                 if (chain->flags & HAMMER2_CHAIN_IOFLUSH) {
 526                         atomic_clear_int(&chain->flags,
 527                                          HAMMER2_CHAIN_IOFLUSH);
 528                         chain->bp->b_flags |= B_RELBUF;
 529                         brelse(chain->bp);
 530                 } else {
 531                         /* bp might still be dirty */
 532                         bqrelse(chain->bp);
 533                 }
 534         }
 535         chain->bp = NULL;
 536         lockmgr(&chain->lk, LK_RELEASE);
 537         hammer2_chain_drop(hmp, chain);
 538 }
 539
 540 /*
 541  * Resize the chain's physical storage allocation.  Chains can be resized
 542  * smaller without reallocating the storage.  Resizing larger will reallocate
 543  * the storage.
 544  *
 545  * Must be passed a locked chain.  If you want the resize to copy the data
 546  * you should lock the chain with RESOLVE_MAYBE or RESOLVE_ALWAYS, otherwise
 547  * the resize operation will not copy the data.
 548  *
 549  * This function is mostly used with DATA blocks locked RESOLVE_NEVER in order
 550  * to avoid instantiating a device buffer that conflicts with the vnode
 551  * data buffer.
 552  *
 553  * XXX flags currently ignored, uses chain->bp to detect data/no-data.
 554  */
 555 void
 556 hammer2_chain_resize(hammer2_mount_t *hmp, hammer2_chain_t *chain,
 557                      int nradix, int flags)
 558 {
 559         struct buf *nbp;
 560         hammer2_off_t pbase;
 561         size_t obytes;
 562         size_t nbytes;
 563         size_t bbytes;
 564         int boff;
 565         char *bdata;
 566         int error;
 567
 568         /*
 569          * Only data and indirect blocks can be resized for now
 570          */
 571         KKASSERT(chain != &hmp->vchain);
 572         KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_DATA ||
 573                  chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT);
 574
 575         /*
 576          * Nothing to do if the element is already the proper size
 577          */
 578         obytes = chain->bytes;
 579         nbytes = 1U << nradix;
 580         if (obytes == nbytes)
 581                 return;
 582
 583         /*
 584          * Set MODIFIED and add a chain ref to prevent destruction.  Both
 585          * modified flags share the same ref.
 586          */
 587         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0) {
 588                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MODIFIED |
 589                                               HAMMER2_CHAIN_MODIFY_TID);
 590                 hammer2_chain_ref(hmp, chain);
 591         }
 592
 593         /*
 594          * Relocate the block, even if making it smaller (because different
 595          * block sizes may be in different regions).
 596          */
 597         chain->bref.data_off = hammer2_freemap_alloc(hmp, chain->bref.type,
 598                                                      nbytes);
 599         chain->bytes = nbytes;
 600
 601         /*
 602          * The device buffer may be larger than the allocation size.
 603          */
 604         if ((bbytes = chain->bytes) < HAMMER2_MINIOSIZE)
 605                 bbytes = HAMMER2_MINIOSIZE;
 606         pbase = chain->bref.data_off & ~(hammer2_off_t)(bbytes - 1);
 607         boff = chain->bref.data_off & HAMMER2_OFF_MASK & (bbytes - 1);
 608
 609         /*
 610          * Only copy the data if resolved, otherwise the caller is
 611          * responsible.
 612          */
 613         if (chain->bp) {
 614                 KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT ||
 615                          chain->bref.type == HAMMER2_BREF_TYPE_DATA);
 616                 KKASSERT(chain != &hmp->vchain);        /* safety */
 617
 618                 /*
 619                  * The getblk() optimization can only be used if the
 620                  * physical block size matches the request.
 621                  */
 622                 if (nbytes == bbytes) {
 623                         nbp = getblk(hmp->devvp, pbase, bbytes, 0, 0);
 624                         error = 0;
 625                 } else {
 626                         error = bread(hmp->devvp, pbase, bbytes, &nbp);
 627                         KKASSERT(error == 0);
 628                 }
 629                 bdata = (char *)nbp->b_data + boff;
 630
 631                 if (nbytes < obytes) {
 632                         bcopy(chain->data, bdata, nbytes);
 633                 } else {
 634                         bcopy(chain->data, bdata, obytes);
 635                         bzero(bdata + obytes, nbytes - obytes);
 636                 }
 637
 638                 /*
 639                  * NOTE: The INITIAL state of the chain is left intact.
 640                  *
 641                  * NOTE: Because of the reallocation we have to set DIRTYBP
 642                  *       if INITIAL is not set.
 643                  */
 644                 chain->bp->b_flags |= B_RELBUF;
 645                 brelse(chain->bp);
 646                 chain->bp = nbp;
 647                 chain->data = (void *)bdata;
 648                 if ((chain->flags & HAMMER2_CHAIN_INITIAL) == 0)
 649                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 650         }
 651         hammer2_chain_parent_setsubmod(hmp, chain);
 652 }
 653
 654 /*
 655  * Convert a locked chain that was retrieved read-only to read-write.
 656  *
 657  * If not already marked modified a new physical block will be allocated
 658  * and assigned to the bref.
 659  *
 660  * Non-data blocks - The chain should be locked to at least the RESOLVE_MAYBE
 661  *                   level or the COW operation will not work.
 662  *
 663  * Data blocks     - The chain is usually locked RESOLVE_NEVER so as not to
 664  *                   run the data through the device buffers.
 665  */
 666 void
 667 hammer2_chain_modify(hammer2_mount_t *hmp, hammer2_chain_t *chain, int flags)
 668 {
 669         struct buf *nbp;
 670         int error;
 671         hammer2_off_t pbase;
 672         size_t bbytes;
 673         size_t boff;
 674         void *bdata;
 675
 676         /*
 677          * Tells flush that modify_tid must be updated, otherwise only
 678          * mirror_tid is updated.  This is the default.
 679          */
 680         if ((flags & HAMMER2_MODIFY_NO_MODIFY_TID) == 0)
 681                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MODIFY_TID);
 682
 683         /*
 684          * If the chain is already marked MODIFIED we can just return.
 685          */
 686         if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
 687                 if ((flags & HAMMER2_MODIFY_OPTDATA) == 0 &&
 688                     chain->bp == NULL) {
 689                         goto skip1;
 690                 }
 691                 return;
 692         }
 693
 694         /*
 695          * Set MODIFIED and add a chain ref to prevent destruction.  Both
 696          * modified flags share the same ref.
 697          */
 698         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
 699         hammer2_chain_ref(hmp, chain);
 700
 701         /*
 702          * We must allocate the copy-on-write block.
 703          *
 704          * If the data is embedded no other action is required.
 705          *
 706          * If the data is not embedded we acquire and clear the
 707          * new block.  If chain->data is not NULL we then do the
 708          * copy-on-write.  chain->data will then be repointed to the new
 709          * buffer and the old buffer will be released.
 710          *
 711          * For newly created elements with no prior allocation we go
 712          * through the copy-on-write steps except without the copying part.
 713          */
 714         if (chain != &hmp->vchain) {
 715                 if ((hammer2_debug & 0x0001) &&
 716                     (chain->bref.data_off & HAMMER2_OFF_MASK)) {
 717                         kprintf("Replace %d\n", chain->bytes);
 718                 }
 719                 chain->bref.data_off =
 720                         hammer2_freemap_alloc(hmp, chain->bref.type,
 721                                               chain->bytes);
 722                 /* XXX failed allocation */
 723         }
 724
 725         /*
 726          * If data instantiation is optional and the chain has no current
 727          * data association (typical for DATA and newly-created INDIRECT
 728          * elements), don't instantiate the buffer now.
 729          */
 730         if ((flags & HAMMER2_MODIFY_OPTDATA) && chain->bp == NULL)
 731                 goto skip2;
 732
 733 skip1:
 734         /*
 735          * Setting the DIRTYBP flag will cause the buffer to be dirtied or
 736          * written-out on unlock.  This bit is independent of the MODIFIED
 737          * bit because the chain may still need meta-data adjustments done
 738          * by virtue of MODIFIED for its parent, and the buffer can be
 739          * flushed out (possibly multiple times) by the OS before that.
 740          *
 741          * Clearing the INITIAL flag (for indirect blocks) indicates that
 742          * a zero-fill buffer has been instantiated.
 743          */
 744         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DIRTYBP);
 745         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_INITIAL);
 746
 747         /*
 748          * We currently should never instantiate a device buffer for a
 749          * data chain.
 750          */
 751         KKASSERT(chain->bref.type != HAMMER2_BREF_TYPE_DATA);
 752
 753         /*
 754          * Execute COW operation
 755          */
 756         switch(chain->bref.type) {
 757         case HAMMER2_BREF_TYPE_VOLUME:
 758         case HAMMER2_BREF_TYPE_INODE:
 759                 /*
 760                  * The data is embedded, no copy-on-write operation is
 761                  * needed.
 762                  */
 763                 KKASSERT(chain->bp == NULL);
 764                 break;
 765         case HAMMER2_BREF_TYPE_DATA:
 766         case HAMMER2_BREF_TYPE_INDIRECT:
 767                 /*
 768                  * Perform the copy-on-write operation
 769                  */
 770                 KKASSERT(chain != &hmp->vchain);        /* safety */
 771                 /*
 772                  * The device buffer may be larger than the allocation size.
 773                  */
 774                 if ((bbytes = chain->bytes) < HAMMER2_MINIOSIZE)
 775                         bbytes = HAMMER2_MINIOSIZE;
 776                 pbase = chain->bref.data_off & ~(hammer2_off_t)(bbytes - 1);
 777                 boff = chain->bref.data_off & HAMMER2_OFF_MASK & (bbytes - 1);
 778
 779                 /*
 780                  * The getblk() optimization can only be used if the
 781                  * physical block size matches the request.
 782                  */
 783                 if (chain->bytes == bbytes) {
 784                         nbp = getblk(hmp->devvp, pbase, bbytes, 0, 0);
 785                         error = 0;
 786                 } else {
 787                         error = bread(hmp->devvp, pbase, bbytes, &nbp);
 788                         KKASSERT(error == 0);
 789                 }
 790                 bdata = (char *)nbp->b_data + boff;
 791
 792                 /*
 793                  * Copy or zero-fill on write depending on whether
 794                  * chain->data exists or not.
 795                  */
 796                 if (chain->data) {
 797                         bcopy(chain->data, bdata, chain->bytes);
 798                         KKASSERT(chain->bp != NULL);
 799                 } else {
 800                         bzero(bdata, chain->bytes);
 801                 }
 802                 if (chain->bp) {
 803                         chain->bp->b_flags |= B_RELBUF;
 804                         brelse(chain->bp);
 805                 }
 806                 chain->bp = nbp;
 807                 chain->data = bdata;
 808                 break;
 809         default:
 810                 panic("hammer2_chain_modify: illegal non-embedded type %d",
 811                       chain->bref.type);
 812                 break;
 813
 814         }
 815 skip2:
 816         if ((flags & HAMMER2_MODIFY_NOSUB) == 0)
 817                 hammer2_chain_parent_setsubmod(hmp, chain);
 818 }
 819
 820 /*
 821  * Mark the volume as having been modified.  This short-cut version
 822  * does not have to lock the volume's chain, which allows the ioctl
 823  * code to make adjustments to connections without deadlocking.
 824  */
 825 void
 826 hammer2_modify_volume(hammer2_mount_t *hmp)
 827 {
 828         hammer2_voldata_lock(hmp);
 829         atomic_set_int(&hmp->vchain.flags, HAMMER2_CHAIN_MODIFIED_AUX);
 830         hammer2_voldata_unlock(hmp);
 831 }
 832
 833 /*
 834  * Locate an in-memory chain.  The parent must be locked.  The in-memory
 835  * chain is returned or NULL if no in-memory chain is present.
 836  *
 837  * NOTE: A chain on-media might exist for this index when NULL is returned.
 838  */
 839 hammer2_chain_t *
 840 hammer2_chain_find(hammer2_mount_t *hmp, hammer2_chain_t *parent, int index)
 841 {
 842         hammer2_chain_t dummy;
 843         hammer2_chain_t *chain;
 844
 845         dummy.index = index;
 846         chain = SPLAY_FIND(hammer2_chain_splay, &parent->shead, &dummy);
 847         return (chain);
 848 }
 849
 850 /*
 851  * Return a locked chain structure with all associated data acquired.
 852  *
 853  * Caller must lock the parent on call, the returned child will be locked.
 854  */
 855 hammer2_chain_t *
 856 hammer2_chain_get(hammer2_mount_t *hmp, hammer2_chain_t *parent,
 857                   int index, int flags)
 858 {
 859         hammer2_blockref_t *bref;
 860         hammer2_chain_t *chain;
 861         hammer2_chain_t dummy;
 862         int how;
 863
 864         /*
 865          * Figure out how to lock.  MAYBE can be used to optimized
 866          * the initial-create state for indirect blocks.
 867          */
 868         if (flags & (HAMMER2_LOOKUP_NODATA | HAMMER2_LOOKUP_NOLOCK))
 869                 how = HAMMER2_RESOLVE_NEVER;
 870         else
 871                 how = HAMMER2_RESOLVE_MAYBE;
 872
 873         /*
 874          * First see if we have a (possibly modified) chain element cached
 875          * for this (parent, index).  Acquire the data if necessary.
 876          *
 877          * If chain->data is non-NULL the chain should already be marked
 878          * modified.
 879          */
 880         dummy.index = index;
 881         chain = SPLAY_FIND(hammer2_chain_splay, &parent->shead, &dummy);
 882         if (chain) {
 883                 if (flags & HAMMER2_LOOKUP_NOLOCK)
 884                         hammer2_chain_ref(hmp, chain);
 885                 else
 886                         hammer2_chain_lock(hmp, chain, how);
 887                 return(chain);
 888         }
 889
 890         /*
 891          * the get function must always succeed, panic if there's no
 892          * data to index.
 893          */
 894         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
 895                 panic("hammer2_chain_get: Missing bref(1)");
 896                 /* NOT REACHED */
 897         }
 898
 899         /*
 900          * Otherwise lookup the bref and issue I/O (switch on the parent)
 901          */
 902         switch(parent->bref.type) {
 903         case HAMMER2_BREF_TYPE_INODE:
 904                 KKASSERT(index >= 0 && index < HAMMER2_SET_COUNT);
 905                 bref = &parent->data->ipdata.u.blockset.blockref[index];
 906                 break;
 907         case HAMMER2_BREF_TYPE_INDIRECT:
 908                 KKASSERT(parent->data != NULL);
 909                 KKASSERT(index >= 0 &&
 910                          index < parent->bytes / sizeof(hammer2_blockref_t));
 911                 bref = &parent->data->npdata.blockref[index];
 912                 break;
 913         case HAMMER2_BREF_TYPE_VOLUME:
 914                 KKASSERT(index >= 0 && index < HAMMER2_SET_COUNT);
 915                 bref = &hmp->voldata.sroot_blockset.blockref[index];
 916                 break;
 917         default:
 918                 bref = NULL;
 919                 panic("hammer2_chain_get: unrecognized blockref type: %d",
 920                       parent->bref.type);
 921         }
 922         if (bref->type == 0) {
 923                 panic("hammer2_chain_get: Missing bref(2)");
 924                 /* NOT REACHED */
 925         }
 926
 927         /*
 928          * Allocate a chain structure representing the existing media
 929          * entry.
 930          *
 931          * The locking operation we do later will issue I/O to read it.
 932          */
 933         chain = hammer2_chain_alloc(hmp, bref);
 934
 935         /*
 936          * Link the chain into its parent.  Caller is expected to hold an
 937          * exclusive lock on the parent.
 938          */
 939         chain->parent = parent;
 940         chain->index = index;
 941         if (SPLAY_INSERT(hammer2_chain_splay, &parent->shead, chain))
 942                 panic("hammer2_chain_link: collision");
 943         KKASSERT(parent->refs > 0);
 944         atomic_add_int(&parent->refs, 1);       /* for splay entry */
 945
 946         /*
 947          * Additional linkage for inodes.  Reuse the parent pointer to
 948          * find the parent directory.
 949          */
 950         if (bref->type == HAMMER2_BREF_TYPE_INODE) {
 951                 while (parent->bref.type == HAMMER2_BREF_TYPE_INDIRECT)
 952                         parent = parent->parent;
 953                 if (parent->bref.type == HAMMER2_BREF_TYPE_INODE) {
 954                         chain->u.ip->pip = parent->u.ip;
 955                         chain->u.ip->pmp = parent->u.ip->pmp;
 956                         chain->u.ip->depth = parent->u.ip->depth + 1;
 957                 }
 958         }
 959
 960         /*
 961          * Our new chain structure has already been referenced and locked
 962          * but the lock code handles the I/O so call it to resolve the data.
 963          * Then release one of our two exclusive locks.
 964          *
 965          * If NOLOCK is set the release will release the one-and-only lock.
 966          */
 967         if ((flags & HAMMER2_LOOKUP_NOLOCK) == 0) {
 968                 hammer2_chain_lock(hmp, chain, how);    /* recusive lock */
 969                 hammer2_chain_drop(hmp, chain);         /* excess ref */
 970         }
 971         lockmgr(&chain->lk, LK_RELEASE);                /* from alloc */
 972
 973         return (chain);
 974 }
 975
 976 /*
 977  * Locate any key between key_beg and key_end inclusive.  (*parentp)
 978  * typically points to an inode but can also point to a related indirect
 979  * block and this function will recurse upwards and find the inode again.
 980  *
 981  * WARNING!  THIS DOES NOT RETURN KEYS IN LOGICAL KEY ORDER!  ANY KEY
 982  *           WITHIN THE RANGE CAN BE RETURNED.  HOWEVER, AN ITERATION
 983  *           WHICH PICKS UP WHERE WE LEFT OFF WILL CONTINUE THE SCAN.
 984  *
 985  * (*parentp) must be exclusively locked and referenced and can be an inode
 986  * or an existing indirect block within the inode.
 987  *
 988  * On return (*parentp) will be modified to point at the deepest parent chain
 989  * element encountered during the search, as a helper for an insertion or
 990  * deletion.   The new (*parentp) will be locked and referenced and the old
 991  * will be unlocked and dereferenced (no change if they are both the same).
 992  *
 993  * The matching chain will be returned exclusively locked and referenced.
 994  *
 995  * NULL is returned if no match was found, but (*parentp) will still
 996  * potentially be adjusted.
 997  *
 998  * This function will also recurse up the chain if the key is not within the
 999  * current parent's range.  (*parentp) can never be set to NULL.  An iteration
1000  * can simply allow (*parentp) to float inside the loop.
1001  */
1002 hammer2_chain_t *
1003 hammer2_chain_lookup(hammer2_mount_t *hmp, hammer2_chain_t **parentp,
1004                      hammer2_key_t key_beg, hammer2_key_t key_end,
1005                      int flags)
1006 {
1007         hammer2_chain_t *parent;
1008         hammer2_chain_t *chain;
1009         hammer2_chain_t *tmp;
1010         hammer2_blockref_t *base;
1011         hammer2_blockref_t *bref;
1012         hammer2_key_t scan_beg;
1013         hammer2_key_t scan_end;
1014         int count = 0;
1015         int i;
1016
1017         /*
1018          * Recurse (*parentp) upward if necessary until the parent completely
1019          * encloses the key range or we hit the inode.
1020          */
1021         parent = *parentp;
1022         while (parent->bref.type == HAMMER2_BREF_TYPE_INDIRECT) {
1023                 scan_beg = parent->bref.key;
1024                 scan_end = scan_beg +
1025                            ((hammer2_key_t)1 << parent->bref.keybits) - 1;
1026                 if (key_beg >= scan_beg && key_end <= scan_end)
1027                         break;
1028                 hammer2_chain_ref(hmp, parent);         /* ref old parent */
1029                 hammer2_chain_unlock(hmp, parent);      /* unlock old parent */
1030                 parent = parent->parent;
1031                                                         /* lock new parent */
1032                 hammer2_chain_lock(hmp, parent, HAMMER2_RESOLVE_MAYBE);
1033                 hammer2_chain_drop(hmp, *parentp);      /* drop old parent */
1034                 *parentp = parent;                      /* new parent */
1035         }
1036
1037 again:
1038         /*
1039          * Locate the blockref array.  Currently we do a fully associative
1040          * search through the array.
1041          */
1042         switch(parent->bref.type) {
1043         case HAMMER2_BREF_TYPE_INODE:
1044                 /*
1045                  * Special shortcut for embedded data returns the inode
1046                  * itself.  Callers must detect this condition and access
1047                  * the embedded data (the strategy code does this for us).
1048                  *
1049                  * This is only applicable to regular files and softlinks.
1050                  */
1051                 if (parent->data->ipdata.op_flags & HAMMER2_OPFLAG_DIRECTDATA) {
1052                         if (flags & HAMMER2_LOOKUP_NOLOCK)
1053                                 hammer2_chain_ref(hmp, parent);
1054                         else
1055                                 hammer2_chain_lock(hmp, parent,
1056                                                    HAMMER2_RESOLVE_ALWAYS);
1057                         return (parent);
1058                 }
1059                 base = &parent->data->ipdata.u.blockset.blockref[0];
1060                 count = HAMMER2_SET_COUNT;
1061                 break;
1062         case HAMMER2_BREF_TYPE_INDIRECT:
1063                 /*
1064                  * Optimize indirect blocks in the INITIAL state to avoid
1065                  * I/O.
1066                  */
1067                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1068                         base = NULL;
1069                 } else {
1070                         if (parent->data == NULL)
1071                                 panic("parent->data is NULL");
1072                         base = &parent->data->npdata.blockref[0];
1073                 }
1074                 count = parent->bytes / sizeof(hammer2_blockref_t);
1075                 break;
1076         case HAMMER2_BREF_TYPE_VOLUME:
1077                 base = &hmp->voldata.sroot_blockset.blockref[0];
1078                 count = HAMMER2_SET_COUNT;
1079                 break;
1080         default:
1081                 panic("hammer2_chain_lookup: unrecognized blockref type: %d",
1082                       parent->bref.type);
1083                 base = NULL;    /* safety */
1084                 count = 0;      /* safety */
1085         }
1086
1087         /*
1088          * If the element and key overlap we use the element.
1089          */
1090         bref = NULL;
1091         for (i = 0; i < count; ++i) {
1092                 tmp = hammer2_chain_find(hmp, parent, i);
1093                 if (tmp) {
1094                         bref = &tmp->bref;
1095                         KKASSERT(bref->type != 0);
1096                 } else if (base == NULL || base[i].type == 0) {
1097                         continue;
1098                 } else {
1099                         bref = &base[i];
1100                 }
1101                 scan_beg = bref->key;
1102                 scan_end = scan_beg + ((hammer2_key_t)1 << bref->keybits) - 1;
1103                 if (key_beg <= scan_end && key_end >= scan_beg)
1104                         break;
1105         }
1106         if (i == count) {
1107                 if (key_beg == key_end)
1108                         return (NULL);
1109                 return (hammer2_chain_next(hmp, parentp, NULL,
1110                                            key_beg, key_end, flags));
1111         }
1112
1113         /*
1114          * Acquire the new chain element.  If the chain element is an
1115          * indirect block we must search recursively.
1116          */
1117         chain = hammer2_chain_get(hmp, parent, i, flags);
1118         if (chain == NULL)
1119                 return (NULL);
1120
1121         /*
1122          * If the chain element is an indirect block it becomes the new
1123          * parent and we loop on it.
1124          *
1125          * The parent always has to be locked with at least RESOLVE_MAYBE,
1126          * so it might need a fixup if the caller passed incompatible flags.
1127          */
1128         if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT) {
1129                 hammer2_chain_unlock(hmp, parent);
1130                 *parentp = parent = chain;
1131                 if (flags & HAMMER2_LOOKUP_NOLOCK) {
1132                         hammer2_chain_lock(hmp, chain, HAMMER2_RESOLVE_MAYBE);
1133                         hammer2_chain_drop(hmp, chain); /* excess ref */
1134                 } else if (flags & HAMMER2_LOOKUP_NODATA) {
1135                         hammer2_chain_lock(hmp, chain, HAMMER2_RESOLVE_MAYBE);
1136                         hammer2_chain_unlock(hmp, chain);
1137                 }
1138                 goto again;
1139         }
1140
1141         /*
1142          * All done, return chain
1143          */
1144         return (chain);
1145 }
1146
1147 /*
1148  * After having issued a lookup we can iterate all matching keys.
1149  *
1150  * If chain is non-NULL we continue the iteration from just after it's index.
1151  *
1152  * If chain is NULL we assume the parent was exhausted and continue the
1153  * iteration at the next parent.
1154  *
1155  * parent must be locked on entry and remains locked throughout.  chain's
1156  * lock status must match flags.
1157  */
1158 hammer2_chain_t *
1159 hammer2_chain_next(hammer2_mount_t *hmp, hammer2_chain_t **parentp,
1160                    hammer2_chain_t *chain,
1161                    hammer2_key_t key_beg, hammer2_key_t key_end,
1162                    int flags)
1163 {
1164         hammer2_chain_t *parent;
1165         hammer2_chain_t *tmp;
1166         hammer2_blockref_t *base;
1167         hammer2_blockref_t *bref;
1168         hammer2_key_t scan_beg;
1169         hammer2_key_t scan_end;
1170         int i;
1171         int count;
1172
1173         parent = *parentp;
1174
1175 again:
1176         /*
1177          * Calculate the next index and recalculate the parent if necessary.
1178          */
1179         if (chain) {
1180                 /*
1181                  * Continue iteration within current parent.  If not NULL
1182                  * the passed-in chain may or may not be locked, based on
1183                  * the LOOKUP_NOLOCK flag (passed in as returned from lookup
1184                  * or a prior next).
1185                  */
1186                 i = chain->index + 1;
1187                 if (flags & HAMMER2_LOOKUP_NOLOCK)
1188                         hammer2_chain_drop(hmp, chain);
1189                 else
1190                         hammer2_chain_unlock(hmp, chain);
1191
1192                 /*
1193                  * Any scan where the lookup returned degenerate data embedded
1194                  * in the inode has an invalid index and must terminate.
1195                  */
1196                 if (chain == parent)
1197                         return(NULL);
1198                 chain = NULL;
1199         } else if (parent->bref.type != HAMMER2_BREF_TYPE_INDIRECT) {
1200                 /*
1201                  * We reached the end of the iteration.
1202                  */
1203                 return (NULL);
1204         } else {
1205                 /*
1206                  * Continue iteration with next parent unless the current
1207                  * parent covers the range.
1208                  */
1209                 hammer2_chain_t *nparent;
1210
1211                 scan_beg = parent->bref.key;
1212                 scan_end = scan_beg +
1213                             ((hammer2_key_t)1 << parent->bref.keybits) - 1;
1214                 if (key_beg >= scan_beg && key_end <= scan_end)
1215                         return (NULL);
1216
1217                 i = parent->index + 1;
1218                 nparent = parent->parent;
1219                 hammer2_chain_ref(hmp, nparent);        /* ref new parent */
1220                 hammer2_chain_unlock(hmp, parent);      /* unlock old parent */
1221                                                         /* lock new parent */
1222                 hammer2_chain_lock(hmp, nparent, HAMMER2_RESOLVE_MAYBE);
1223                 hammer2_chain_drop(hmp, nparent);       /* drop excess ref */
1224                 *parentp = parent = nparent;
1225         }
1226
1227 again2:
1228         /*
1229          * Locate the blockref array.  Currently we do a fully associative
1230          * search through the array.
1231          */
1232         switch(parent->bref.type) {
1233         case HAMMER2_BREF_TYPE_INODE:
1234                 base = &parent->data->ipdata.u.blockset.blockref[0];
1235                 count = HAMMER2_SET_COUNT;
1236                 break;
1237         case HAMMER2_BREF_TYPE_INDIRECT:
1238                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1239                         base = NULL;
1240                 } else {
1241                         KKASSERT(parent->data != NULL);
1242                         base = &parent->data->npdata.blockref[0];
1243                 }
1244                 count = parent->bytes / sizeof(hammer2_blockref_t);
1245                 break;
1246         case HAMMER2_BREF_TYPE_VOLUME:
1247                 base = &hmp->voldata.sroot_blockset.blockref[0];
1248                 count = HAMMER2_SET_COUNT;
1249                 break;
1250         default:
1251                 panic("hammer2_chain_next: unrecognized blockref type: %d",
1252                       parent->bref.type);
1253                 base = NULL;    /* safety */
1254                 count = 0;      /* safety */
1255                 break;
1256         }
1257         KKASSERT(i <= count);
1258
1259         /*
1260          * Look for the key.  If we are unable to find a match and an exact
1261          * match was requested we return NULL.  If a range was requested we
1262          * run hammer2_chain_next() to iterate.
1263          */
1264         bref = NULL;
1265         while (i < count) {
1266                 tmp = hammer2_chain_find(hmp, parent, i);
1267                 if (tmp) {
1268                         bref = &tmp->bref;
1269                 } else if (base == NULL || base[i].type == 0) {
1270                         ++i;
1271                         continue;
1272                 } else {
1273                         bref = &base[i];
1274                 }
1275                 scan_beg = bref->key;
1276                 scan_end = scan_beg + ((hammer2_key_t)1 << bref->keybits) - 1;
1277                 if (key_beg <= scan_end && key_end >= scan_beg)
1278                         break;
1279                 ++i;
1280         }
1281
1282         /*
1283          * If we couldn't find a match recurse up a parent to continue the
1284          * search.
1285          */
1286         if (i == count)
1287                 goto again;
1288
1289         /*
1290          * Acquire the new chain element.  If the chain element is an
1291          * indirect block we must search recursively.
1292          */
1293         chain = hammer2_chain_get(hmp, parent, i, flags);
1294         if (chain == NULL)
1295                 return (NULL);
1296
1297         /*
1298          * If the chain element is an indirect block it becomes the new
1299          * parent and we loop on it.
1300          *
1301          * The parent always has to be locked with at least RESOLVE_MAYBE,
1302          * so it might need a fixup if the caller passed incompatible flags.
1303          */
1304         if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT) {
1305                 hammer2_chain_unlock(hmp, parent);
1306                 *parentp = parent = chain;
1307                 chain = NULL;
1308                 if (flags & HAMMER2_LOOKUP_NOLOCK) {
1309                         hammer2_chain_lock(hmp, parent, HAMMER2_RESOLVE_MAYBE);
1310                         hammer2_chain_drop(hmp, parent);        /* excess ref */
1311                 } else if (flags & HAMMER2_LOOKUP_NODATA) {
1312                         hammer2_chain_lock(hmp, parent, HAMMER2_RESOLVE_MAYBE);
1313                         hammer2_chain_unlock(hmp, parent);
1314                 }
1315                 i = 0;
1316                 goto again2;
1317         }
1318
1319         /*
1320          * All done, return chain
1321          */
1322         return (chain);
1323 }
1324
1325 /*
1326  * Create and return a new hammer2 system memory structure of the specified
1327  * key, type and size and insert it RELATIVE TO (PARENT).
1328  *
1329  * (parent) is typically either an inode or an indirect block, acquired
1330  * acquired as a side effect of issuing a prior failed lookup.  parent
1331  * must be locked and held.  Do not pass the inode chain to this function
1332  * unless that is the chain returned by the failed lookup.
1333  *
1334  * Non-indirect types will automatically allocate indirect blocks as required
1335  * if the new item does not fit in the current (parent).
1336  *
1337  * Indirect types will move a portion of the existing blockref array in
1338  * (parent) into the new indirect type and then use one of the free slots
1339  * to emplace the new indirect type.
1340  *
1341  * A new locked, referenced chain element is returned of the specified type.
1342  * The element may or may not have a data area associated with it:
1343  *
1344  *      VOLUME          not allowed here
1345  *      INODE           embedded data are will be set-up
1346  *      INDIRECT        not allowed here
1347  *      DATA            no data area will be set-up (caller is expected
1348  *                      to have logical buffers, we don't want to alias
1349  *                      the data onto device buffers!).
1350  */
1351 hammer2_chain_t *
1352 hammer2_chain_create(hammer2_mount_t *hmp, hammer2_chain_t *parent,
1353                      hammer2_chain_t *chain,
1354                      hammer2_key_t key, int keybits, int type, size_t bytes)
1355 {
1356         hammer2_blockref_t dummy;
1357         hammer2_blockref_t *base;
1358         hammer2_chain_t dummy_chain;
1359         int unlock_parent = 0;
1360         int allocated = 0;
1361         int count;
1362         int i;
1363
1364         if (chain == NULL) {
1365                 /*
1366                  * First allocate media space and construct the dummy bref,
1367                  * then allocate the in-memory chain structure.
1368                  */
1369                 bzero(&dummy, sizeof(dummy));
1370                 dummy.type = type;
1371                 dummy.key = key;
1372                 dummy.keybits = keybits;
1373                 dummy.data_off = hammer2_bytes_to_radix(bytes);
1374                 chain = hammer2_chain_alloc(hmp, &dummy);
1375                 allocated = 1;
1376
1377                 /*
1378                  * We do NOT set INITIAL here (yet).  INITIAL is only
1379                  * used for indirect blocks.
1380                  *
1381                  * Recalculate bytes to reflect the actual media block
1382                  * allocation.
1383                  */
1384                 bytes = (hammer2_off_t)1 <<
1385                         (int)(chain->bref.data_off & HAMMER2_OFF_MASK_RADIX);
1386                 chain->bytes = bytes;
1387
1388                 switch(type) {
1389                 case HAMMER2_BREF_TYPE_VOLUME:
1390                         panic("hammer2_chain_create: called with volume type");
1391                         break;
1392                 case HAMMER2_BREF_TYPE_INODE:
1393                         KKASSERT(bytes == HAMMER2_INODE_BYTES);
1394                         chain->data = (void *)&chain->u.ip->ip_data;
1395                         break;
1396                 case HAMMER2_BREF_TYPE_INDIRECT:
1397                         panic("hammer2_chain_create: cannot be used to"
1398                               "create indirect block");
1399                         break;
1400                 case HAMMER2_BREF_TYPE_DATA:
1401                 default:
1402                         /* leave chain->data NULL */
1403                         KKASSERT(chain->data == NULL);
1404                         break;
1405                 }
1406         } else {
1407                 /*
1408                  * Potentially update the chain's key/keybits.
1409                  */
1410                 chain->bref.key = key;
1411                 chain->bref.keybits = keybits;
1412         }
1413
1414 again:
1415         /*
1416          * Locate a free blockref in the parent's array
1417          */
1418         switch(parent->bref.type) {
1419         case HAMMER2_BREF_TYPE_INODE:
1420                 KKASSERT(parent->data != NULL);
1421                 base = &parent->data->ipdata.u.blockset.blockref[0];
1422                 count = HAMMER2_SET_COUNT;
1423                 break;
1424         case HAMMER2_BREF_TYPE_INDIRECT:
1425                 if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1426                         base = NULL;
1427                 } else {
1428                         KKASSERT(parent->data != NULL);
1429                         base = &parent->data->npdata.blockref[0];
1430                 }
1431                 count = parent->bytes / sizeof(hammer2_blockref_t);
1432                 break;
1433         case HAMMER2_BREF_TYPE_VOLUME:
1434                 KKASSERT(parent->data != NULL);
1435                 base = &hmp->voldata.sroot_blockset.blockref[0];
1436                 count = HAMMER2_SET_COUNT;
1437                 break;
1438         default:
1439                 panic("hammer2_chain_create: unrecognized blockref type: %d",
1440                       parent->bref.type);
1441                 count = 0;
1442                 break;
1443         }
1444
1445         /*
1446          * Scan for an unallocated bref, also skipping any slots occupied
1447          * by in-memory chain elements that may not yet have been updated
1448          * in the parent's bref array.
1449          */
1450         bzero(&dummy_chain, sizeof(dummy_chain));
1451         for (i = 0; i < count; ++i) {
1452                 if (base == NULL) {
1453                         dummy_chain.index = i;
1454                         if (SPLAY_FIND(hammer2_chain_splay,
1455                                        &parent->shead, &dummy_chain) == NULL) {
1456                                 break;
1457                         }
1458                 } else if (base[i].type == 0) {
1459                         dummy_chain.index = i;
1460                         if (SPLAY_FIND(hammer2_chain_splay,
1461                                        &parent->shead, &dummy_chain) == NULL) {
1462                                 break;
1463                         }
1464                 }
1465         }
1466
1467         /*
1468          * If no free blockref count be found we must create an indirect
1469          * block and move a number of blockrefs into it.  With the parent
1470          * locked we can safely lock each child in order to move it without
1471          * causing a deadlock.
1472          *
1473          * This may return the new indirect block or the old parent depending
1474          * on where the key falls.
1475          */
1476         if (i == count) {
1477                 hammer2_chain_t *nparent;
1478
1479                 nparent = hammer2_chain_create_indirect(hmp, parent,
1480                                                         key, keybits);
1481                 if (nparent == NULL) {
1482                         if (allocated)
1483                                 hammer2_chain_free(hmp, chain);
1484                         chain = NULL;
1485                         goto done;
1486                 }
1487                 if (parent != nparent) {
1488                         if (unlock_parent)
1489                                 hammer2_chain_unlock(hmp, parent);
1490                         parent = nparent;
1491                         unlock_parent = 1;
1492                 }
1493                 goto again;
1494         }
1495
1496         /*
1497          * Link the chain into its parent.
1498          */
1499         if (chain->parent != NULL)
1500                 panic("hammer2: hammer2_chain_create: chain already connected");
1501         KKASSERT(chain->parent == NULL);
1502         chain->parent = parent;
1503         chain->index = i;
1504         if (SPLAY_INSERT(hammer2_chain_splay, &parent->shead, chain))
1505                 panic("hammer2_chain_link: collision");
1506         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_DELETED);
1507         KKASSERT(parent->refs > 0);
1508         atomic_add_int(&parent->refs, 1);
1509
1510         /*
1511          * Additional linkage for inodes.  Reuse the parent pointer to
1512          * find the parent directory.
1513          */
1514         if (chain->bref.type == HAMMER2_BREF_TYPE_INODE) {
1515                 hammer2_chain_t *scan = parent;
1516                 while (scan->bref.type == HAMMER2_BREF_TYPE_INDIRECT)
1517                         scan = scan->parent;
1518                 if (scan->bref.type == HAMMER2_BREF_TYPE_INODE) {
1519                         chain->u.ip->pip = scan->u.ip;
1520                         chain->u.ip->pmp = scan->u.ip->pmp;
1521                         chain->u.ip->depth = scan->u.ip->depth + 1;
1522                 }
1523         }
1524
1525         /*
1526          * (allocated) indicates that this is a newly-created chain element
1527          * rather than a renamed chain element.  In this situation we want
1528          * to place the chain element in the MODIFIED state.
1529          *
1530          * The data area will be set up as follows:
1531          *
1532          *      VOLUME          not allowed here.
1533          *
1534          *      INODE           embedded data are will be set-up.
1535          *
1536          *      INDIRECT        not allowed here.
1537          *
1538          *      DATA            no data area will be set-up (caller is expected
1539          *                      to have logical buffers, we don't want to alias
1540          *                      the data onto device buffers!).
1541          */
1542         if (allocated) {
1543                 if (chain->bref.type == HAMMER2_BREF_TYPE_DATA) {
1544                         hammer2_chain_modify(hmp, chain,
1545                                              HAMMER2_MODIFY_OPTDATA);
1546                 } else if (chain->bref.type == HAMMER2_BREF_TYPE_INDIRECT) {
1547                         /* not supported in this function */
1548                         panic("hammer2_chain_create: bad type");
1549                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_INITIAL);
1550                         hammer2_chain_modify(hmp, chain,
1551                                              HAMMER2_MODIFY_OPTDATA);
1552                 } else {
1553                         hammer2_chain_modify(hmp, chain, 0);
1554                 }
1555         } else {
1556                 /*
1557                  * When reconnecting inodes we have to call setsubmod()
1558                  * to ensure that its state propagates up the newly
1559                  * connected parent.
1560                  *
1561                  * We cannot depend on the chain being in a MODIFIED
1562                  * state, or it might already be in that state, so
1563                  * even if the parent calls hammer2_chain_modify()
1564                  * MOVED might not get set.  Thus we have to set it
1565                  * here, too.
1566                  */
1567                 if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
1568                         hammer2_chain_ref(hmp, chain);
1569                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
1570                 }
1571                 hammer2_chain_parent_setsubmod(hmp, chain);
1572         }
1573
1574 done:
1575         if (unlock_parent)
1576                 hammer2_chain_unlock(hmp, parent);
1577         return (chain);
1578 }
1579
1580 /*
1581  * Create an indirect block that covers one or more of the elements in the
1582  * current parent.  Either returns the existing parent with no locking or
1583  * ref changes or returns the new indirect block locked and referenced,
1584  * depending on what the specified key falls into.
1585  *
1586  * The key/keybits for the indirect mode only needs to follow three rules:
1587  *
1588  * (1) That all elements underneath it fit within its key space and
1589  *
1590  * (2) That all elements outside it are outside its key space.
1591  *
1592  * (3) When creating the new indirect block any elements in the current
1593  *     parent that fit within the new indirect block's keyspace must be
1594  *     moved into the new indirect block.
1595  *
1596  * (4) The keyspace chosen for the inserted indirect block CAN cover a wider
1597  *     keyspace the the current parent, but lookup/iteration rules will
1598  *     ensure (and must ensure) that rule (2) for all parents leading up
1599  *     to the nearest inode or the root volume header is adhered to.  This
1600  *     is accomplished by always recursing through matching keyspaces in
1601  *     the hammer2_chain_lookup() and hammer2_chain_next() API.
1602  *
1603  * The current implementation calculates the current worst-case keyspace by
1604  * iterating the current parent and then divides it into two halves, choosing
1605  * whichever half has the most elements (not necessarily the half containing
1606  * the requested key).
1607  *
1608  * We can also opt to use the half with the least number of elements.  This
1609  * causes lower-numbered keys (aka logical file offsets) to recurse through
1610  * fewer indirect blocks and higher-numbered keys to recurse through more.
1611  * This also has the risk of not moving enough elements to the new indirect
1612  * block and being forced to create several indirect blocks before the element
1613  * can be inserted.
1614  */
1615 static
1616 hammer2_chain_t *
1617 hammer2_chain_create_indirect(hammer2_mount_t *hmp, hammer2_chain_t *parent,
1618                               hammer2_key_t create_key, int create_bits)
1619 {
1620         hammer2_blockref_t *base;
1621         hammer2_blockref_t *bref;
1622         hammer2_chain_t *chain;
1623         hammer2_chain_t *ichain;
1624         hammer2_chain_t dummy;
1625         hammer2_key_t key = create_key;
1626         int keybits = create_bits;
1627         int locount = 0;
1628         int hicount = 0;
1629         int count;
1630         int nbytes;
1631         int i;
1632
1633         /*
1634          * Calculate the base blockref pointer or NULL if the chain
1635          * is known to be empty.
1636          */
1637         hammer2_chain_modify(hmp, parent, HAMMER2_MODIFY_OPTDATA);
1638         if (parent->flags & HAMMER2_CHAIN_INITIAL) {
1639                 base = NULL;
1640
1641                 /*
1642                  * We still need to calculate the count for SPLAY lookups
1643                  */
1644                 switch(parent->bref.type) {
1645                 case HAMMER2_BREF_TYPE_INODE:
1646                         count = HAMMER2_SET_COUNT;
1647                         break;
1648                 case HAMMER2_BREF_TYPE_INDIRECT:
1649                         count = parent->bytes / sizeof(hammer2_blockref_t);
1650                         break;
1651                 case HAMMER2_BREF_TYPE_VOLUME:
1652                         count = HAMMER2_SET_COUNT;
1653                         break;
1654                 default:
1655                         panic("hammer2_chain_create_indirect: "
1656                               "unrecognized blockref type: %d",
1657                               parent->bref.type);
1658                         count = 0;
1659                         break;
1660                 }
1661         } else {
1662                 /*
1663                  * Locate a free blockref in the parent's array
1664                  */
1665                 switch(parent->bref.type) {
1666                 case HAMMER2_BREF_TYPE_INODE:
1667                         base = &parent->data->ipdata.u.blockset.blockref[0];
1668                         count = HAMMER2_SET_COUNT;
1669                         break;
1670                 case HAMMER2_BREF_TYPE_INDIRECT:
1671                         base = &parent->data->npdata.blockref[0];
1672                         count = parent->bytes / sizeof(hammer2_blockref_t);
1673                         break;
1674                 case HAMMER2_BREF_TYPE_VOLUME:
1675                         base = &hmp->voldata.sroot_blockset.blockref[0];
1676                         count = HAMMER2_SET_COUNT;
1677                         break;
1678                 default:
1679                         panic("hammer2_chain_create_indirect: "
1680                               "unrecognized blockref type: %d",
1681                               parent->bref.type);
1682                         count = 0;
1683                         break;
1684                 }
1685         }
1686
1687         /*
1688          * Scan for an unallocated bref, also skipping any slots occupied
1689          * by in-memory chain elements that may not yet have been updated
1690          * in the parent's bref array.
1691          */
1692         bzero(&dummy, sizeof(dummy));
1693         for (i = 0; i < count; ++i) {
1694                 int nkeybits;
1695
1696                 /*
1697                  * Optimize the case where the parent is still in its
1698                  * initially created state.
1699                  */
1700                 if (base == NULL || base[i].type == 0) {
1701                         dummy.index = i;
1702                         chain = SPLAY_FIND(hammer2_chain_splay,
1703                                            &parent->shead, &dummy);
1704                         if (chain == NULL)
1705                                 continue;
1706                         bref = &chain->bref;
1707                 } else {
1708                         bref = &base[i];
1709                 }
1710
1711                 /*
1712                  * Expand our calculated key range (key, keybits) to fit
1713                  * the scanned key.  nkeybits represents the full range
1714                  * that we will later cut in half (two halves @ nkeybits - 1).
1715                  */
1716                 nkeybits = keybits;
1717                 if (nkeybits < bref->keybits)
1718                         nkeybits = bref->keybits;
1719                 while ((~(((hammer2_key_t)1 << nkeybits) - 1) &
1720                         (key ^ bref->key)) != 0) {
1721                         ++nkeybits;
1722                 }
1723
1724                 /*
1725                  * If the new key range is larger we have to determine
1726                  * which side of the new key range the existing keys fall
1727                  * under by checking the high bit, then collapsing the
1728                  * locount into the hicount or vise-versa.
1729                  */
1730                 if (keybits != nkeybits) {
1731                         if (((hammer2_key_t)1 << (nkeybits - 1)) & key) {
1732                                 hicount += locount;
1733                                 locount = 0;
1734                         } else {
1735                                 locount += hicount;
1736                                 hicount = 0;
1737                         }
1738                         keybits = nkeybits;
1739                 }
1740
1741                 /*
1742                  * The newly scanned key will be in the lower half or the
1743                  * higher half of the (new) key range.
1744                  */
1745                 if (((hammer2_key_t)1 << (nkeybits - 1)) & bref->key)
1746                         ++hicount;
1747                 else
1748                         ++locount;
1749         }
1750
1751         /*
1752          * Adjust keybits to represent half of the full range calculated
1753          * above.
1754          */
1755         --keybits;
1756
1757         /*
1758          * Select whichever half contains the most elements.  Theoretically
1759          * we can select either side as long as it contains at least one
1760          * element (in order to ensure that a free slot is present to hold
1761          * the indirect block).
1762          */
1763         key &= ~(((hammer2_key_t)1 << keybits) - 1);
1764         if (hammer2_indirect_optimize) {
1765                 /*
1766                  * Insert node for least number of keys, this will arrange
1767                  * the first few blocks of a large file or the first few
1768                  * inodes in a directory with fewer indirect blocks when
1769                  * created linearly.
1770                  */
1771                 if (hicount < locount && hicount != 0)
1772                         key |= (hammer2_key_t)1 << keybits;
1773                 else
1774                         key &= ~(hammer2_key_t)1 << keybits;
1775         } else {
1776                 /*
1777                  * Insert node for most number of keys, best for heavily
1778                  * fragmented files.
1779                  */
1780                 if (hicount > locount)
1781                         key |= (hammer2_key_t)1 << keybits;
1782                 else
1783                         key &= ~(hammer2_key_t)1 << keybits;
1784         }
1785
1786         /*
1787          * How big should our new indirect block be?  It has to be at least
1788          * as large as its parent.
1789          */
1790         if (parent->bref.type == HAMMER2_BREF_TYPE_INODE)
1791                 nbytes = HAMMER2_IND_BYTES_MIN;
1792         else
1793                 nbytes = HAMMER2_IND_BYTES_MAX;
1794         if (nbytes < count * sizeof(hammer2_blockref_t))
1795                 nbytes = count * sizeof(hammer2_blockref_t);
1796
1797         /*
1798          * Ok, create our new indirect block
1799          */
1800         dummy.bref.type = HAMMER2_BREF_TYPE_INDIRECT;
1801         dummy.bref.key = key;
1802         dummy.bref.keybits = keybits;
1803         dummy.bref.data_off = hammer2_bytes_to_radix(nbytes);
1804         ichain = hammer2_chain_alloc(hmp, &dummy.bref);
1805         atomic_set_int(&ichain->flags, HAMMER2_CHAIN_INITIAL);
1806
1807         /*
1808          * Iterate the original parent and move the matching brefs into
1809          * the new indirect block.
1810          */
1811         for (i = 0; i < count; ++i) {
1812                 /*
1813                  * For keying purposes access the bref from the media or
1814                  * from our in-memory cache.  In cases where the in-memory
1815                  * cache overrides the media the keyrefs will be the same
1816                  * anyway so we can avoid checking the cache when the media
1817                  * has a key.
1818                  */
1819                 if (base == NULL || base[i].type == 0) {
1820                         dummy.index = i;
1821                         chain = SPLAY_FIND(hammer2_chain_splay,
1822                                            &parent->shead, &dummy);
1823                         if (chain == NULL) {
1824                                 /*
1825                                  * Select index indirect block is placed in
1826                                  */
1827                                 if (ichain->index < 0)
1828                                         ichain->index = i;
1829                                 continue;
1830                         }
1831                         bref = &chain->bref;
1832                 } else {
1833                         bref = &base[i];
1834                 }
1835
1836                 /*
1837                  * Skip keys not in the chosen half (low or high), only bit
1838                  * (keybits - 1) needs to be compared but for safety we
1839                  * will compare all msb bits plus that bit again.
1840                  */
1841                 if ((~(((hammer2_key_t)1 << keybits) - 1) &
1842                     (key ^ bref->key)) != 0) {
1843                         continue;
1844                 }
1845
1846                 /*
1847                  * This element is being moved, its slot is available
1848                  * for our indirect block.
1849                  */
1850                 if (ichain->index < 0)
1851                         ichain->index = i;
1852
1853                 /*
1854                  * Load the new indirect block by acquiring or allocating
1855                  * the related chain entries, then simply move it to the
1856                  * new parent (ichain).
1857                  *
1858                  * Flagging the new chain entry MOVED will cause a flush
1859                  * to synchronize its block into the new indirect block.
1860                  * The chain is unlocked after being moved but needs to
1861                  * retain a reference for the MOVED state
1862                  *
1863                  * We must still set SUBMODIFIED in the parent but we do
1864                  * that after the loop.
1865                  *
1866                  * XXX we really need a lock here but we don't need the
1867                  *     data.  NODATA feature needed.
1868                  */
1869                 chain = hammer2_chain_get(hmp, parent, i,
1870                                           HAMMER2_LOOKUP_NODATA);
1871                 SPLAY_REMOVE(hammer2_chain_splay, &parent->shead, chain);
1872                 if (SPLAY_INSERT(hammer2_chain_splay, &ichain->shead, chain))
1873                         panic("hammer2_chain_create_indirect: collision");
1874                 chain->parent = ichain;
1875                 if (base)
1876                         bzero(&base[i], sizeof(base[i]));
1877                 atomic_add_int(&parent->refs, -1);
1878                 atomic_add_int(&ichain->refs, 1);
1879                 if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
1880                         hammer2_chain_ref(hmp, chain);
1881                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
1882                 }
1883                 hammer2_chain_unlock(hmp, chain);
1884                 KKASSERT(parent->refs > 0);
1885                 chain = NULL;
1886         }
1887
1888         /*
1889          * Insert the new indirect block into the parent now that we've
1890          * cleared out some entries in the parent.  We calculated a good
1891          * insertion index in the loop above (ichain->index).
1892          */
1893         KKASSERT(ichain->index >= 0);
1894         if (SPLAY_INSERT(hammer2_chain_splay, &parent->shead, ichain))
1895                 panic("hammer2_chain_create_indirect: ichain insertion");
1896         ichain->parent = parent;
1897         atomic_add_int(&parent->refs, 1);
1898
1899         /*
1900          * Mark the new indirect block modified after insertion, which
1901          * will propagate up through parent all the way to the root and
1902          * also allocate the physical block in ichain for our caller,
1903          * and assign ichain->data to a pre-zero'd space (because there
1904          * is not prior data to copy into it).
1905          *
1906          * We have to set SUBMODIFIED in ichain's flags manually so the
1907          * flusher knows it has to recurse through it to get to all of
1908          * our moved blocks, then call setsubmod() to set the bit
1909          * recursively.
1910          */
1911         hammer2_chain_modify(hmp, ichain, HAMMER2_MODIFY_OPTDATA);
1912         atomic_set_int(&ichain->flags, HAMMER2_CHAIN_SUBMODIFIED);
1913         hammer2_chain_parent_setsubmod(hmp, ichain);
1914
1915         /*
1916          * Figure out what to return.
1917          */
1918         if (create_bits >= keybits) {
1919                 /*
1920                  * Key being created is way outside the key range,
1921                  * return the original parent.
1922                  */
1923                 hammer2_chain_unlock(hmp, ichain);
1924         } else if (~(((hammer2_key_t)1 << keybits) - 1) &
1925                    (create_key ^ key)) {
1926                 /*
1927                  * Key being created is outside the key range,
1928                  * return the original parent.
1929                  */
1930                 hammer2_chain_unlock(hmp, ichain);
1931         } else {
1932                 /*
1933                  * Otherwise its in the range, return the new parent.
1934                  */
1935                 parent = ichain;
1936         }
1937
1938         return(parent);
1939 }
1940
1941 /*
1942  * Physically delete the specified chain element.  Note that inodes with
1943  * open descriptors should not be deleted (as with other filesystems) until
1944  * the last open descriptor is closed.
1945  *
1946  * This routine will remove the chain element from its parent and potentially
1947  * also recurse upward and delete indirect blocks which become empty as a
1948  * side effect.
1949  *
1950  * The caller must pass a pointer to the chain's parent, also locked and
1951  * referenced.  (*parentp) will be modified in a manner similar to a lookup
1952  * or iteration when indirect blocks are also deleted as a side effect.
1953  */
1954 void
1955 hammer2_chain_delete(hammer2_mount_t *hmp, hammer2_chain_t *parent,
1956                      hammer2_chain_t *chain)
1957 {
1958         hammer2_blockref_t *base;
1959         int count;
1960
1961         if (chain->parent != parent)
1962                 panic("hammer2_chain_delete: parent mismatch");
1963
1964         /*
1965          * Mark the parent modified so our base[] pointer remains valid
1966          * while we move entries.  For the optimized indirect block
1967          * case mark the parent moved instead.
1968          *
1969          * Calculate the blockref reference in the parent
1970          */
1971         switch(parent->bref.type) {
1972         case HAMMER2_BREF_TYPE_INODE:
1973                 hammer2_chain_modify(hmp, parent, HAMMER2_MODIFY_NO_MODIFY_TID);
1974                 base = &parent->data->ipdata.u.blockset.blockref[0];
1975                 count = HAMMER2_SET_COUNT;
1976                 break;
1977         case HAMMER2_BREF_TYPE_INDIRECT:
1978                 hammer2_chain_modify(hmp, parent, HAMMER2_MODIFY_OPTDATA |
1979                                                   HAMMER2_MODIFY_NO_MODIFY_TID);
1980                 if (parent->flags & HAMMER2_CHAIN_INITIAL)
1981                         base = NULL;
1982                 else
1983                         base = &parent->data->npdata.blockref[0];
1984                 count = parent->bytes / sizeof(hammer2_blockref_t);
1985                 break;
1986         case HAMMER2_BREF_TYPE_VOLUME:
1987                 hammer2_chain_modify(hmp, parent, HAMMER2_MODIFY_NO_MODIFY_TID);
1988                 base = &hmp->voldata.sroot_blockset.blockref[0];
1989                 count = HAMMER2_SET_COUNT;
1990                 break;
1991         default:
1992                 panic("hammer2_chain_delete: unrecognized blockref type: %d",
1993                       parent->bref.type);
1994                 count = 0;
1995                 break;
1996         }
1997
1998         /*
1999          * Disconnect the bref in the parent, remove the chain, and
2000          * disconnect in-memory fields from the parent.
2001          */
2002         KKASSERT(chain->index >= 0 && chain->index < count);
2003         if (base)
2004                 bzero(&base[chain->index], sizeof(*base));
2005
2006         SPLAY_REMOVE(hammer2_chain_splay, &parent->shead, chain);
2007         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DELETED);
2008         atomic_add_int(&parent->refs, -1);      /* for splay entry */
2009         chain->index = -1;
2010         chain->parent = NULL;
2011
2012         /*
2013          * If this is an inode clear the pip.
2014          */
2015         if (chain->bref.type == HAMMER2_BREF_TYPE_INODE) {
2016                 chain->u.ip->pip = NULL;
2017                 chain->u.ip->depth = 0;
2018         }
2019
2020         /*
2021          * The chain is still likely referenced, possibly even by a vnode
2022          * (if an inode), so defer further action until the chain gets
2023          * dropped.
2024          */
2025 }
2026
2027 /*
2028  * Recursively flush the specified chain.  The chain is locked and
2029  * referenced by the caller and will remain so on return.  The chain
2030  * will remain referenced throughout but can temporarily lose its
2031  * lock during the recursion to avoid unnecessarily stalling user
2032  * processes.
2033  *
2034  *
2035  */
2036 TAILQ_HEAD(flush_deferral_list, hammer2_chain);
2037
2038 struct hammer2_flush_info {
2039         struct flush_deferral_list flush_list;
2040         int             depth;
2041         hammer2_tid_t   modify_tid;
2042 };
2043
2044 typedef struct hammer2_flush_info hammer2_flush_info_t;
2045
2046 static void
2047 hammer2_chain_flush_pass1(hammer2_mount_t *hmp, hammer2_chain_t *chain,
2048                           hammer2_flush_info_t *info)
2049 {
2050         hammer2_blockref_t *bref;
2051         hammer2_off_t pbase;
2052         size_t bbytes;
2053         size_t boff;
2054         char *bdata;
2055         struct buf *bp;
2056         int error;
2057
2058         /*
2059          * If we hit the stack recursion depth limit defer the operation.
2060          * The controller of the info structure will execute the deferral
2061          * list and then retry.
2062          *
2063          * This is only applicable if SUBMODIFIED is set.  After a reflush
2064          * SUBMODIFIED will probably be cleared and we want to drop through
2065          * to finish processing the current element so our direct parent
2066          * can process the results.
2067          */
2068         if (info->depth == HAMMER2_FLUSH_DEPTH_LIMIT &&
2069             (chain->flags & HAMMER2_CHAIN_SUBMODIFIED)) {
2070                 if ((chain->flags & HAMMER2_CHAIN_DEFERRED) == 0) {
2071                         hammer2_chain_ref(hmp, chain);
2072                         TAILQ_INSERT_TAIL(&info->flush_list,
2073                                           chain, flush_node);
2074                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_DEFERRED);
2075                 }
2076                 return;
2077         }
2078
2079         if (hammer2_debug & 0x0008)
2080                 kprintf("%*.*sCHAIN type=%d@%08jx %p/%d %04x {\n",
2081                         info->depth, info->depth, "",
2082                         chain->bref.type, chain->bref.data_off,
2083                         chain, chain->refs, chain->flags);
2084
2085         /*
2086          * Flush any children of this chain.
2087          *
2088          * NOTE: If we use a while() here an active filesystem can
2089          *       prevent the flush from ever finishing.
2090          */
2091         if (chain->flags & HAMMER2_CHAIN_SUBMODIFIED) {
2092                 hammer2_blockref_t *base;
2093                 hammer2_chain_t *child;
2094                 hammer2_chain_t *next;
2095                 int count;
2096                 int submodified = 0;
2097                 int submoved = 0;
2098
2099                 /*
2100                  * Clear SUBMODIFIED now.  Flag any races during the flush
2101                  * with the (submodified) local variable and re-arm it
2102                  * as necessary after the loop is done.
2103                  *
2104                  * Delaying the setting of the chain to MODIFIED can reduce
2105                  * unnecessary I/O.
2106                  *
2107                  * Modifications to the children will propagate up, forcing
2108                  * us to become modified and copy-on-write too.  Be sure
2109                  * to modify chain (as a side effect of the recursive
2110                  * flush) ONLY if it is actually being modified by the
2111                  * recursive flush.
2112                  */
2113                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_SUBMODIFIED);
2114
2115                 /*
2116                  * Flush the children and update the blockrefs in the chain.
2117                  * Be careful of ripouts during the loop.
2118                  */
2119                 next = SPLAY_MIN(hammer2_chain_splay, &chain->shead);
2120                 while ((child = next) != NULL) {
2121                         next = SPLAY_NEXT(hammer2_chain_splay,
2122                                           &chain->shead, child);
2123                         /*
2124                          * We only recurse if SUBMODIFIED (internal node)
2125                          * or MODIFIED (internal node or leaf) is set.
2126                          * However, we must still track whether any MOVED
2127                          * entries are present to determine if the chain's
2128                          * blockref's need updating or not.
2129                          */
2130                         if (child->flags & HAMMER2_CHAIN_MOVED)
2131                                 submoved = 1;
2132                         if ((child->flags & (HAMMER2_CHAIN_SUBMODIFIED |
2133                                              HAMMER2_CHAIN_MODIFIED |
2134                                             HAMMER2_CHAIN_MODIFIED_AUX)) == 0) {
2135                                 continue;
2136                         }
2137
2138                         /*
2139                          * Propagate the DESTROYED flag if found set, then
2140                          * recurse the flush.
2141                          */
2142                         hammer2_chain_lock(hmp, child, HAMMER2_RESOLVE_MAYBE);
2143                         if ((chain->flags & HAMMER2_CHAIN_DESTROYED) &&
2144                             (child->flags & HAMMER2_CHAIN_DESTROYED) == 0) {
2145                                 atomic_set_int(&child->flags,
2146                                                HAMMER2_CHAIN_DESTROYED |
2147                                                HAMMER2_CHAIN_SUBMODIFIED);
2148                         }
2149                         ++info->depth;
2150                         hammer2_chain_flush_pass1(hmp, child, info);
2151                         --info->depth;
2152
2153                         /*
2154                          * No point loading blockrefs yet if the
2155                          * child (recursively) is still dirty.
2156                          */
2157                         if (child->flags & (HAMMER2_CHAIN_SUBMODIFIED |
2158                                            HAMMER2_CHAIN_MODIFIED |
2159                                            HAMMER2_CHAIN_MODIFIED_AUX)) {
2160                                 submodified = 1;
2161                                 if (hammer2_debug & 0x0008)
2162                                         kprintf("s");
2163                         }
2164                         if (child->flags & HAMMER2_CHAIN_MOVED) {
2165                                 if (hammer2_debug & 0x0008)
2166                                         kprintf("m");
2167                                 submoved = 1;
2168                         }
2169                         if (hammer2_debug & 0x0008)
2170                                 kprintf("\n");
2171                         hammer2_chain_unlock(hmp, child);
2172                 }
2173
2174                 /*
2175                  * If the sub-tree was not completely synced we currently do
2176                  * not attempt to propagate the bref all the way back up.
2177                  * Our bref pointers to the children are not updated yet in
2178                  * this situation but the children will have CHAIN_MOVED set
2179                  * and cannot be destroyed until the parent synchronizes
2180                  * the brefs.
2181                  *
2182                  * If the sub-tree had to be recursed the bref propagates
2183                  * back up and may require 'chain' to become modified.
2184                  *
2185                  */
2186                 if (submodified ||
2187                     (chain->flags & HAMMER2_CHAIN_SUBMODIFIED)) {
2188                         /*
2189                          * No point loading up the blockrefs if submodified
2190                          * got re-set.  The modified and flushed children
2191                          * will have set HAMMER2_CHAIN_MOVED and cannot be
2192                          * freed until we've synchronized the case.
2193                          *
2194                          * NOTE: Even though we cleared the SUBMODIFIED flag
2195                          *       it can still get re-set by operations
2196                          *       occuring under our chain, so check both.
2197                          */
2198                         atomic_set_int(&chain->flags,
2199                                        HAMMER2_CHAIN_SUBMODIFIED);
2200                 } else if (submoved) {
2201                         /*
2202                          * Ok, we can modify the blockrefs in this chain
2203                          * entry.  Mark it modified.  Calculate the
2204                          * blockref array after marking it modified (since
2205                          * that may change the underlying data ptr).
2206                          *
2207                          * NOTE: We only do this if submoved != 0, otherwise
2208                          *       there may not be any changes and setting
2209                          *       the chain modified will re-arm the MOVED
2210                          *       bit recursively, resulting in O(N^2)
2211                          *       flushes.
2212                          *
2213                          * NOTE: We don't want hammer2_chain_modify() to
2214                          *       recursively set the SUBMODIFIED flag
2215                          *       upward in this case!
2216                          */
2217                         hammer2_chain_modify(hmp, chain,
2218                                              HAMMER2_MODIFY_NOSUB |
2219                                              HAMMER2_MODIFY_NO_MODIFY_TID);
2220
2221                         switch(chain->bref.type) {
2222                         case HAMMER2_BREF_TYPE_INODE:
2223                                 base = &chain->data->ipdata.u.blockset.
2224                                         blockref[0];
2225                                 count = HAMMER2_SET_COUNT;
2226                                 break;
2227                         case HAMMER2_BREF_TYPE_INDIRECT:
2228                                 base = &chain->data->npdata.blockref[0];
2229                                 count = chain->bytes /
2230                                         sizeof(hammer2_blockref_t);
2231                                 break;
2232                         case HAMMER2_BREF_TYPE_VOLUME:
2233                                 base = &hmp->voldata.sroot_blockset.blockref[0];
2234                                 count = HAMMER2_SET_COUNT;
2235                                 break;
2236                         default:
2237                                 base = NULL;
2238                                 panic("hammer2_chain_get: "
2239                                       "unrecognized blockref type: %d",
2240                                       chain->bref.type);
2241                         }
2242
2243                         /*
2244                          * Update the blockrefs.
2245                          *
2246                          * When updating the blockset embedded in the volume
2247                          * header we must also update voldata.mirror_tid.
2248                          */
2249                         next = SPLAY_MIN(hammer2_chain_splay, &chain->shead);
2250                         while ((child = next) != NULL) {
2251                                 next = SPLAY_NEXT(hammer2_chain_splay,
2252                                                   &chain->shead, child);
2253                                 KKASSERT(child->index >= 0 &&
2254                                          child->index < count);
2255                                 hammer2_chain_lock(hmp, child,
2256                                                    HAMMER2_RESOLVE_NEVER);
2257                                 if (child->flags & HAMMER2_CHAIN_MOVED) {
2258                                         base[child->index] = child->bref;
2259                                         if (chain->bref.mirror_tid <
2260                                             child->bref.mirror_tid) {
2261                                                 chain->bref.mirror_tid =
2262                                                         child->bref.mirror_tid;
2263                                         }
2264                                         if (chain->bref.type ==
2265                                              HAMMER2_BREF_TYPE_VOLUME &&
2266                                             hmp->voldata.mirror_tid <
2267                                              child->bref.mirror_tid) {
2268                                                 hmp->voldata.mirror_tid =
2269                                                         child->bref.mirror_tid;
2270                                         }
2271                                         atomic_clear_int(&child->flags,
2272                                                  HAMMER2_CHAIN_MOVED);
2273                                         hammer2_chain_drop(hmp, child);
2274                                 } else if (bcmp(&base[child->index],
2275                                            &child->bref,
2276                                            sizeof(child->bref)) != 0) {
2277                                         panic("hammer2: unflagged bref update");
2278                                 }
2279                                 hammer2_chain_unlock(hmp, child);
2280                         }
2281                 }
2282         }
2283
2284         /*
2285          * If destroying the object we unconditonally clear the MODIFIED
2286          * and MOVED bits, and we destroy the buffer without writing it
2287          * out.
2288          *
2289          * We don't bother updating the hash/crc or the chain bref.
2290          *
2291          * NOTE: The destroy'd object's bref has already been updated.
2292          *       so we can clear MOVED without propagating mirror_tid
2293          *       or modify_tid upward.
2294          *
2295          * XXX allocations for unflushed data can be returned to the
2296          *     free pool.
2297          */
2298         if (chain->flags & HAMMER2_CHAIN_DESTROYED) {
2299                 if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
2300                         if (chain->bp) {
2301                                 chain->bp->b_flags |= B_INVAL|B_RELBUF;
2302                         }
2303                         atomic_clear_int(&chain->flags,
2304                                          HAMMER2_CHAIN_MODIFIED |
2305                                          HAMMER2_CHAIN_MODIFY_TID);
2306                         hammer2_chain_drop(hmp, chain);
2307                 }
2308                 if (chain->flags & HAMMER2_CHAIN_MODIFIED_AUX) {
2309                         atomic_clear_int(&chain->flags,
2310                                          HAMMER2_CHAIN_MODIFIED_AUX);
2311                 }
2312                 if (chain->flags & HAMMER2_CHAIN_MOVED) {
2313                         atomic_clear_int(&chain->flags,
2314                                          HAMMER2_CHAIN_MOVED);
2315                         hammer2_chain_drop(hmp, chain);
2316                 }
2317                 return;
2318         }
2319
2320         /*
2321          * Flush this chain entry only if it is marked modified.
2322          */
2323         if ((chain->flags & (HAMMER2_CHAIN_MODIFIED |
2324                              HAMMER2_CHAIN_MODIFIED_AUX)) == 0) {
2325                 goto done;
2326         }
2327
2328         /*
2329          * Clear MODIFIED and set HAMMER2_CHAIN_MOVED.  The caller
2330          * will re-test the MOVED bit.  We must also update the mirror_tid
2331          * and modify_tid fields as appropriate.
2332          *
2333          * bits own a single chain ref and the MOVED bit owns its own
2334          * chain ref.
2335          */
2336         if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
2337                 chain->bref.mirror_tid = info->modify_tid;
2338                 if (chain->flags & HAMMER2_CHAIN_MODIFY_TID)
2339                         chain->bref.modify_tid = info->modify_tid;
2340                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED |
2341                                                 HAMMER2_CHAIN_MODIFY_TID);
2342                 if (chain->flags & HAMMER2_CHAIN_MOVED) {
2343                         hammer2_chain_drop(hmp, chain);
2344                 } else {
2345                         /* inherit ref from the MODIFIED we cleared */
2346                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
2347                 }
2348         }
2349         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED_AUX);
2350
2351         /*
2352          * If this is part of a recursive flush we can go ahead and write
2353          * out the buffer cache buffer and pass a new bref back up the chain.
2354          *
2355          * This will never be a volume header.
2356          */
2357         switch(chain->bref.type) {
2358         case HAMMER2_BREF_TYPE_VOLUME:
2359                 /*
2360                  * The volume header is flushed manually by the syncer, not
2361                  * here.
2362                  */
2363                 break;
2364         case HAMMER2_BREF_TYPE_DATA:
2365                 /*
2366                  * Data elements have already been flushed via the logical
2367                  * file buffer cache.  Their hash was set in the bref by
2368                  * the vop_write code.
2369                  *
2370                  * Make sure the buffer(s) have been flushed out here.
2371                  */
2372 #if 1
2373                 bbytes = chain->bytes;
2374                 pbase = chain->bref.data_off & ~(hammer2_off_t)(bbytes - 1);
2375                 boff = chain->bref.data_off & HAMMER2_OFF_MASK & (bbytes - 1);
2376
2377                 bp = getblk(hmp->devvp, pbase, bbytes, GETBLK_NOWAIT, 0);
2378                 if (bp) {
2379                         if ((bp->b_flags & (B_CACHE | B_DIRTY)) ==
2380                             (B_CACHE | B_DIRTY)) {
2381                                 kprintf("x");
2382                                 cluster_awrite(bp);
2383                         } else {
2384                                 bp->b_flags |= B_RELBUF;
2385                                 brelse(bp);
2386                         }
2387                 }
2388 #endif
2389                 break;
2390         case HAMMER2_BREF_TYPE_INDIRECT:
2391                 /*
2392                  * Indirect blocks may be in an INITIAL state.
2393                  */
2394                 break;
2395         default:
2396                 /*
2397                  * Embedded elements have to be flushed out.
2398                  */
2399                 KKASSERT(chain->data != NULL);
2400                 bref = &chain->bref;
2401
2402                 KKASSERT((bref->data_off & HAMMER2_OFF_MASK) != 0);
2403
2404                 if (chain->bp == NULL) {
2405                         /*
2406                          * The data is embedded, we have to acquire the
2407                          * buffer cache buffer and copy the data into it.
2408                          */
2409                         if ((bbytes = chain->bytes) < HAMMER2_MINIOSIZE)
2410                                 bbytes = HAMMER2_MINIOSIZE;
2411                         pbase = bref->data_off & ~(hammer2_off_t)(bbytes - 1);
2412                         boff = bref->data_off & HAMMER2_OFF_MASK & (bbytes - 1);
2413
2414                         /*
2415                          * The getblk() optimization can only be used if the
2416                          * physical block size matches the request.
2417                          */
2418                         if (chain->bytes == bbytes) {
2419                                 bp = getblk(hmp->devvp, pbase, bbytes, 0, 0);
2420                                 error = 0;
2421                         } else {
2422                                 error = bread(hmp->devvp, pbase, bbytes, &bp);
2423                                 KKASSERT(error == 0);
2424                         }
2425                         bdata = (char *)bp->b_data + boff;
2426
2427                         /*
2428                          * Copy the data to the buffer, mark the buffer
2429                          * dirty, and convert the chain to unmodified.
2430                          */
2431                         bcopy(chain->data, bdata, chain->bytes);
2432                         bp->b_flags |= B_CLUSTEROK;
2433                         bdwrite(bp);
2434                         bp = NULL;
2435                         chain->bref.check.iscsi32.value =
2436                                 hammer2_icrc32(chain->data, chain->bytes);
2437                         if (chain->bref.type == HAMMER2_BREF_TYPE_INODE)
2438                                 ++hammer2_iod_meta_write;
2439                         else
2440                                 ++hammer2_iod_indr_write;
2441                 } else {
2442                         chain->bref.check.iscsi32.value =
2443                                 hammer2_icrc32(chain->data, chain->bytes);
2444                 }
2445         }
2446
2447         /*
2448          * Adjustments to the bref.  The caller will use this to adjust
2449          * our chain's pointer to this chain element.
2450          */
2451         bref = &chain->bref;
2452
2453         switch(bref->type) {
2454         case HAMMER2_BREF_TYPE_VOLUME:
2455                 KKASSERT(chain->data != NULL);
2456                 KKASSERT(chain->bp == NULL);
2457
2458                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT1]=
2459                         hammer2_icrc32(
2460                                 (char *)&hmp->voldata +
2461                                  HAMMER2_VOLUME_ICRC1_OFF,
2462                                 HAMMER2_VOLUME_ICRC1_SIZE);
2463                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT0]=
2464                         hammer2_icrc32(
2465                                 (char *)&hmp->voldata +
2466                                  HAMMER2_VOLUME_ICRC0_OFF,
2467                                 HAMMER2_VOLUME_ICRC0_SIZE);
2468                 hmp->voldata.icrc_volheader =
2469                         hammer2_icrc32(
2470                                 (char *)&hmp->voldata +
2471                                  HAMMER2_VOLUME_ICRCVH_OFF,
2472                                 HAMMER2_VOLUME_ICRCVH_SIZE);
2473                 break;
2474         default:
2475                 break;
2476
2477         }
2478 done:
2479         if (hammer2_debug & 0x0008) {
2480                 kprintf("%*.*s} %p/%d %04x ",
2481                         info->depth, info->depth, "",
2482                         chain, chain->refs, chain->flags);
2483         }
2484 }
2485
2486 #if 0
2487 /*
2488  * PASS2 - not yet implemented (should be called only with the root chain?)
2489  */
2490 static void
2491 hammer2_chain_flush_pass2(hammer2_mount_t *hmp, hammer2_chain_t *chain)
2492 {
2493 }
2494 #endif
2495
2496 /*
2497  * Stand-alone flush.  If the chain is unable to completely flush we have
2498  * to be sure that SUBMODIFIED propagates up the parent chain.
2499  *
2500  * This routine can be called from several places but the most important
2501  * is from the hammer2_vop_reclaim() function.  We want to try to completely
2502  * clean out the inode structure to prevent disconnected inodes from
2503  * building up and blowing out the kmalloc pool.
2504  *
2505  * If modify_tid is 0 (usual case), a new modify_tid is allocated and
2506  * applied to the flush.  The depth-limit handling code is the only
2507  * code which passes a non-zero modify_tid to hammer2_chain_flush().
2508  */
2509 void
2510 hammer2_chain_flush(hammer2_mount_t *hmp, hammer2_chain_t *chain,
2511                     hammer2_tid_t modify_tid)
2512 {
2513         hammer2_chain_t *parent;
2514         hammer2_chain_t *scan;
2515         hammer2_blockref_t *base;
2516         hammer2_flush_info_t info;
2517         int count;
2518         int reflush;
2519
2520         /*
2521          * Execute the recursive flush and handle deferrals.
2522          *
2523          * Chains can be ridiculously long (thousands deep), so to
2524          * avoid blowing out the kernel stack the recursive flush has a
2525          * depth limit.  Elements at the limit are placed on a list
2526          * for re-execution after the stack has been popped.
2527          */
2528         bzero(&info, sizeof(info));
2529         TAILQ_INIT(&info.flush_list);
2530
2531         if (modify_tid == 0) {
2532                 hammer2_voldata_lock(hmp);
2533                 info.modify_tid = hmp->voldata.alloc_tid++;
2534                 hammer2_voldata_unlock(hmp);
2535         } else {
2536                 info.modify_tid = modify_tid;
2537         }
2538         reflush = 1;
2539
2540         while (reflush) {
2541                 /*
2542                  * Primary recursion
2543                  */
2544                 hammer2_chain_flush_pass1(hmp, chain, &info);
2545                 reflush = 0;
2546
2547                 while ((scan = TAILQ_FIRST(&info.flush_list)) != NULL) {
2548                         /*
2549                          * Secondary recursion.  Note that a reference is
2550                          * retained from the element's presence on the
2551                          * deferral list.
2552                          */
2553                         KKASSERT(scan->flags & HAMMER2_CHAIN_DEFERRED);
2554                         TAILQ_REMOVE(&info.flush_list, scan, flush_node);
2555                         atomic_clear_int(&scan->flags, HAMMER2_CHAIN_DEFERRED);
2556
2557                         /*
2558                          * Now that we've popped back up we can do a secondary
2559                          * recursion on the deferred elements.
2560                          */
2561                         if (hammer2_debug & 0x0040)
2562                                 kprintf("defered flush %p\n", scan);
2563                         hammer2_chain_lock(hmp, scan, HAMMER2_RESOLVE_MAYBE);
2564                         hammer2_chain_flush(hmp, scan, info.modify_tid);
2565                         hammer2_chain_unlock(hmp, scan);
2566
2567                         /*
2568                          * Only flag a reflush if SUBMODIFIED is no longer
2569                          * set.  If SUBMODIFIED is set the element will just
2570                          * wind up on our flush_list again.
2571                          */
2572                         if ((scan->flags & (HAMMER2_CHAIN_SUBMODIFIED |
2573                                             HAMMER2_CHAIN_MODIFIED |
2574                                             HAMMER2_CHAIN_MODIFIED_AUX)) == 0) {
2575                                 reflush = 1;
2576                         }
2577                         hammer2_chain_drop(hmp, scan);
2578                 }
2579                 if ((hammer2_debug & 0x0040) && reflush)
2580                         kprintf("reflush %p\n", chain);
2581         }
2582
2583         /*
2584          * The SUBMODIFIED bit must propagate upward if the chain could not
2585          * be completely flushed.
2586          */
2587         if (chain->flags & (HAMMER2_CHAIN_SUBMODIFIED |
2588                             HAMMER2_CHAIN_MODIFIED |
2589                             HAMMER2_CHAIN_MODIFIED_AUX |
2590                             HAMMER2_CHAIN_MOVED)) {
2591                 hammer2_chain_parent_setsubmod(hmp, chain);
2592         }
2593
2594         /*
2595          * If the only thing left is a simple bref update try to
2596          * pro-actively update the parent, otherwise return early.
2597          */
2598         parent = chain->parent;
2599         if (parent == NULL) {
2600                 return;
2601         }
2602         if (chain->bref.type != HAMMER2_BREF_TYPE_INODE ||
2603             (chain->flags & (HAMMER2_CHAIN_SUBMODIFIED |
2604                              HAMMER2_CHAIN_MODIFIED |
2605                              HAMMER2_CHAIN_MODIFIED_AUX |
2606                              HAMMER2_CHAIN_MOVED)) != HAMMER2_CHAIN_MOVED) {
2607                 return;
2608         }
2609
2610         /*
2611          * We are locking backwards so allow the lock to fail
2612          */
2613         if (lockmgr(&parent->lk, LK_EXCLUSIVE | LK_NOWAIT) != 0) {
2614                 return;
2615         }
2616
2617         /*
2618          * We are updating brefs but we have to call chain_modify()
2619          * because our caller is not being run from a recursive flush.
2620          *
2621          * This will also chain up the parent list and set the SUBMODIFIED
2622          * flag.
2623          *
2624          * We do not want to set HAMMER2_CHAIN_MODIFY_TID here because the
2625          * modification is only related to updating a bref in the parent.
2626          *
2627          * When updating the blockset embedded in the volume header we must
2628          * also update voldata.mirror_tid.
2629          */
2630         hammer2_chain_lock(hmp, parent, HAMMER2_RESOLVE_MAYBE);
2631         hammer2_chain_modify(hmp, parent, HAMMER2_MODIFY_NO_MODIFY_TID);
2632
2633         switch(parent->bref.type) {
2634         case HAMMER2_BREF_TYPE_INODE:
2635                 base = &parent->data->ipdata.u.blockset.
2636                         blockref[0];
2637                 count = HAMMER2_SET_COUNT;
2638                 break;
2639         case HAMMER2_BREF_TYPE_INDIRECT:
2640                 base = &parent->data->npdata.blockref[0];
2641                 count = parent->bytes /
2642                         sizeof(hammer2_blockref_t);
2643                 break;
2644         case HAMMER2_BREF_TYPE_VOLUME:
2645                 base = &hmp->voldata.sroot_blockset.blockref[0];
2646                 count = HAMMER2_SET_COUNT;
2647                 if (chain->flags & HAMMER2_CHAIN_MOVED) {
2648                         if (hmp->voldata.mirror_tid < chain->bref.mirror_tid) {
2649                                 hmp->voldata.mirror_tid =
2650                                         chain->bref.mirror_tid;
2651                         }
2652                 }
2653                 break;
2654         default:
2655                 base = NULL;
2656                 panic("hammer2_chain_flush: "
2657                       "unrecognized blockref type: %d",
2658                       parent->bref.type);
2659         }
2660
2661         /*
2662          * Update the blockref in the parent.  We do not have to set
2663          * MOVED in the parent because SUBMODIFIED has already been
2664          * set, so a normal flush will pick up the changes and propagate
2665          * them upward for us.
2666          *
2667          * We do have to propagate mirror_tid upward.
2668          */
2669         KKASSERT(chain->index >= 0 &&
2670                  chain->index < count);
2671         if (chain->flags & HAMMER2_CHAIN_MOVED) {
2672                 base[chain->index] = chain->bref;
2673                 if (parent->bref.mirror_tid < chain->bref.mirror_tid)
2674                         parent->bref.mirror_tid = chain->bref.mirror_tid;
2675                 atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MOVED);
2676                 hammer2_chain_drop(hmp, chain);
2677         } else if (bcmp(&base[chain->index],
2678                    &chain->bref,
2679                    sizeof(chain->bref)) != 0) {
2680                 panic("hammer2: unflagged bref update(2)");
2681         }
2682
2683         lockmgr(&parent->lk, LK_RELEASE);       /* release manual lockmgr op */
2684         hammer2_chain_unlock(hmp, parent);
2685 }