sys/vfs/hammer2/hammer2_bulkfree.c

   1 /*
   2  * Copyright (c) 2013-2015 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  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 #include <sys/param.h>
  35 #include <sys/systm.h>
  36 #include <sys/kernel.h>
  37 #include <sys/fcntl.h>
  38 #include <sys/buf.h>
  39 #include <sys/proc.h>
  40 #include <sys/namei.h>
  41 #include <sys/mount.h>
  42 #include <sys/vnode.h>
  43 #include <sys/mountctl.h>
  44 #include <vm/vm_kern.h>
  45 #include <vm/vm_extern.h>
  46
  47 #include "hammer2.h"
  48
  49 /*
  50  * XXX I made a mistake and made the reserved area begin at each LEVEL1 zone,
  51  *     which is on a 1GB demark.  This will eat a little more space but for
  52  *     now we retain compatibility and make FMZONEBASE every 1GB
  53  */
  54 #define H2FMZONEBASE(key)         ((key) & ~HAMMER2_FREEMAP_LEVEL1_MASK)
  55 #define H2FMBASE(key, radix)    ((key) & ~(((hammer2_off_t)1 << (radix)) - 1))
  56 #define H2FMSHIFT(radix)        ((hammer2_off_t)1 << (radix))
  57
  58 /*
  59  * breadth-first search
  60  */
  61 typedef struct hammer2_chain_save {
  62         TAILQ_ENTRY(hammer2_chain_save) entry;
  63         hammer2_chain_t *chain;
  64         int pri;
  65 } hammer2_chain_save_t;
  66
  67 TAILQ_HEAD(hammer2_chain_save_list, hammer2_chain_save);
  68 typedef struct hammer2_chain_save_list hammer2_chain_save_list_t;
  69
  70 typedef struct hammer2_bulkfree_info {
  71         hammer2_dev_t           *hmp;
  72         kmem_anon_desc_t        kp;
  73         hammer2_off_t           sbase;          /* sub-loop iteration */
  74         hammer2_off_t           sstop;
  75         hammer2_bmap_data_t     *bmap;
  76         int                     depth;
  77         long                    count_10_00;    /* staged->free      */
  78         long                    count_11_10;    /* allocated->staged */
  79         long                    count_00_11;    /* (should not happen) */
  80         long                    count_01_11;    /* (should not happen) */
  81         long                    count_10_11;    /* staged->allocated */
  82         long                    count_l0cleans;
  83         long                    count_linadjusts;
  84         long                    count_inodes_scanned;
  85         long                    count_dirents_scanned;
  86         long                    count_dedup_factor;
  87         long                    count_bytes_scanned;
  88         long                    count_chains_scanned;
  89         long                    count_chains_reported;
  90         hammer2_off_t           adj_free;
  91         hammer2_tid_t           mtid;
  92         hammer2_tid_t           saved_mirror_tid;
  93         time_t                  save_time;
  94         hammer2_chain_save_list_t list;
  95         hammer2_dedup_t         *dedup;
  96         int                     pri;
  97 } hammer2_bulkfree_info_t;
  98
  99 static int h2_bulkfree_test(hammer2_bulkfree_info_t *info,
 100                         hammer2_blockref_t *bref, int pri);
 101
 102 /*
 103  * General bulk scan function with callback.  Called with a referenced
 104  * but UNLOCKED parent.  The parent is returned in the same state.
 105  */
 106 static
 107 int
 108 hammer2_bulk_scan(hammer2_chain_t *parent,
 109                   int (*func)(hammer2_bulkfree_info_t *info,
 110                               hammer2_blockref_t *bref),
 111                   hammer2_bulkfree_info_t *info)
 112 {
 113         hammer2_blockref_t bref;
 114         hammer2_chain_t *chain;
 115         int first = 1;
 116         int rup_error;
 117         int error;
 118
 119         ++info->pri;
 120
 121         hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS |
 122                                    HAMMER2_RESOLVE_SHARED);
 123         chain = NULL;
 124         rup_error = 0;
 125         error = 0;
 126
 127         /*
 128          * Generally loop on the contents if we have not been flagged
 129          * for abort.
 130          *
 131          * Remember that these chains are completely isolated from
 132          * the frontend, so we can release locks temporarily without
 133          * imploding.
 134          */
 135         for (;;) {
 136                 error |= hammer2_chain_scan(parent, &chain, &bref, &first,
 137                                             HAMMER2_LOOKUP_NODATA |
 138                                             HAMMER2_LOOKUP_SHARED);
 139
 140                 /*
 141                  * Handle EOF or other error at current level.  This stops
 142                  * the bulkfree scan.
 143                  */
 144                 if (error)
 145                         break;
 146
 147                 if (bref.type == HAMMER2_BREF_TYPE_DIRENT)
 148                         ++info->count_dirents_scanned;
 149
 150                 /*
 151                  * Ignore brefs without data (typically dirents)
 152                  */
 153                 if ((bref.data_off & ~HAMMER2_OFF_MASK_RADIX) == 0)
 154                         continue;
 155
 156                 /*
 157                  * Process bref, chain is only non-NULL if the bref
 158                  * might be recursable (its possible that we sometimes get
 159                  * a non-NULL chain where the bref cannot be recursed).
 160                  */
 161                 ++info->pri;
 162                 if (h2_bulkfree_test(info, &bref, 1))
 163                         continue;
 164
 165                 if (bref.type == HAMMER2_BREF_TYPE_INODE)
 166                         ++info->count_inodes_scanned;
 167
 168                 error |= func(info, &bref);
 169                 if (error)
 170                         break;
 171
 172                 /*
 173                  * A non-null chain is always returned if it is
 174                  * recursive, otherwise a non-null chain might be
 175                  * returned but usually is not when not recursive.
 176                  */
 177                 if (chain == NULL)
 178                         continue;
 179
 180                 if (chain) {
 181                         info->count_bytes_scanned += chain->bytes;
 182                         ++info->count_chains_scanned;
 183
 184                         if (info->count_chains_scanned >=
 185                             info->count_chains_reported + 50000) {
 186                                 kprintf(" chains %-7ld inodes %-7ld "
 187                                         "dirents %-7ld bytes %5ldMB\n",
 188                                         info->count_chains_scanned,
 189                                         info->count_inodes_scanned,
 190                                         info->count_dirents_scanned,
 191                                         info->count_bytes_scanned / 1000000);
 192                                 info->count_chains_reported += 50000;
 193                         }
 194                 }
 195
 196
 197                 /*
 198                  * Else check type and setup depth-first scan.
 199                  *
 200                  * Account for bytes actually read.
 201                  */
 202                 switch(chain->bref.type) {
 203                 case HAMMER2_BREF_TYPE_INODE:
 204                 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 205                 case HAMMER2_BREF_TYPE_INDIRECT:
 206                 case HAMMER2_BREF_TYPE_VOLUME:
 207                 case HAMMER2_BREF_TYPE_FREEMAP:
 208                         ++info->depth;
 209                         if (info->depth > 16) {
 210                                 hammer2_chain_save_t *save;
 211                                 save = kmalloc(sizeof(*save), M_HAMMER2,
 212                                                M_WAITOK | M_ZERO);
 213                                 save->chain = chain;
 214                                 hammer2_chain_ref(chain);
 215                                 TAILQ_INSERT_TAIL(&info->list, save, entry);
 216
 217                                 /* guess */
 218                                 info->pri += 10;
 219                         } else {
 220                                 int savepri = info->pri;
 221
 222                                 hammer2_chain_unlock(chain);
 223                                 hammer2_chain_unlock(parent);
 224                                 info->pri = 0;
 225                                 rup_error |=
 226                                         hammer2_bulk_scan(chain, func, info);
 227                                 info->pri += savepri;
 228                                 hammer2_chain_lock(parent,
 229                                                    HAMMER2_RESOLVE_ALWAYS |
 230                                                    HAMMER2_RESOLVE_SHARED);
 231                                 hammer2_chain_lock(chain,
 232                                                    HAMMER2_RESOLVE_ALWAYS |
 233                                                    HAMMER2_RESOLVE_SHARED);
 234                         }
 235                         --info->depth;
 236                         break;
 237                 case HAMMER2_BREF_TYPE_DATA:
 238                         break;
 239                 default:
 240                         /* does not recurse */
 241                         break;
 242                 }
 243                 if (rup_error & HAMMER2_ERROR_ABORTED)
 244                         break;
 245         }
 246         if (chain) {
 247                 hammer2_chain_unlock(chain);
 248                 hammer2_chain_drop(chain);
 249         }
 250
 251         /*
 252          * Save with higher pri now that we know what it is.
 253          */
 254         h2_bulkfree_test(info, &parent->bref, info->pri + 1);
 255
 256         hammer2_chain_unlock(parent);
 257
 258         return ((error | rup_error) & ~HAMMER2_ERROR_EOF);
 259 }
 260
 261 /*
 262  * Bulkfree algorithm
 263  *
 264  * Repeat {
 265  *      Chain flush (partial synchronization) XXX removed
 266  *      Scan the whole topology - build in-memory freemap (mark 11)
 267  *      Reconcile the in-memory freemap against the on-disk freemap.
 268  *              ondisk xx -> ondisk 11 (if allocated)
 269  *              ondisk 11 -> ondisk 10 (if free in-memory)
 270  *              ondisk 10 -> ondisk 00 (if free in-memory) - on next pass
 271  * }
 272  *
 273  * The topology scan may have to be performed multiple times to window
 274  * freemaps which are too large to fit in kernel memory.
 275  *
 276  * Races are handled using a double-transition (11->10, 10->00).  The bulkfree
 277  * scan snapshots the volume root's blockset and thus can run concurrent with
 278  * normal operations, as long as a full flush is made between each pass to
 279  * synchronize any modified chains (otherwise their blocks might be improperly
 280  * freed).
 281  *
 282  * Temporary memory in multiples of 64KB is required to reconstruct the leaf
 283  * hammer2_bmap_data blocks so they can later be compared against the live
 284  * freemap.  Each 64KB block represents 128 x 16KB x 1024 = ~2 GB of storage.
 285  * A 32MB save area thus represents around ~1 TB.  The temporary memory
 286  * allocated can be specified.  If it is not sufficient multiple topology
 287  * passes will be made.
 288  */
 289
 290 /*
 291  * Bulkfree callback info
 292  */
 293 static void hammer2_bulkfree_thread(void *arg __unused);
 294 static void cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size);
 295 static int h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo,
 296                         hammer2_blockref_t *bref);
 297 static int h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo);
 298 static void h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
 299                         hammer2_off_t data_off, hammer2_bmap_data_t *live,
 300                         hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base);
 301
 302 void
 303 hammer2_bulkfree_init(hammer2_dev_t *hmp)
 304 {
 305         hammer2_thr_create(&hmp->bfthr, NULL, hmp,
 306                            hmp->devrepname, -1, -1,
 307                            hammer2_bulkfree_thread);
 308 }
 309
 310 void
 311 hammer2_bulkfree_uninit(hammer2_dev_t *hmp)
 312 {
 313         hammer2_thr_delete(&hmp->bfthr);
 314 }
 315
 316 static void
 317 hammer2_bulkfree_thread(void *arg)
 318 {
 319         hammer2_thread_t *thr = arg;
 320         hammer2_ioc_bulkfree_t bfi;
 321         uint32_t flags;
 322
 323         for (;;) {
 324                 hammer2_thr_wait_any(thr,
 325                                      HAMMER2_THREAD_STOP |
 326                                      HAMMER2_THREAD_FREEZE |
 327                                      HAMMER2_THREAD_UNFREEZE |
 328                                      HAMMER2_THREAD_REMASTER,
 329                                      hz * 60);
 330
 331                 flags = thr->flags;
 332                 cpu_ccfence();
 333                 if (flags & HAMMER2_THREAD_STOP)
 334                         break;
 335                 if (flags & HAMMER2_THREAD_FREEZE) {
 336                         hammer2_thr_signal2(thr, HAMMER2_THREAD_FROZEN,
 337                                                  HAMMER2_THREAD_FREEZE);
 338                         continue;
 339                 }
 340                 if (flags & HAMMER2_THREAD_UNFREEZE) {
 341                         hammer2_thr_signal2(thr, 0,
 342                                                  HAMMER2_THREAD_FROZEN |
 343                                                  HAMMER2_THREAD_UNFREEZE);
 344                         continue;
 345                 }
 346                 if (flags & HAMMER2_THREAD_FROZEN)
 347                         continue;
 348                 if (flags & HAMMER2_THREAD_REMASTER) {
 349                         hammer2_thr_signal2(thr, 0, HAMMER2_THREAD_REMASTER);
 350                         bzero(&bfi, sizeof(bfi));
 351                         bfi.size = 8192 * 1024;
 352                         /* hammer2_bulkfree_pass(thr->hmp, &bfi); */
 353                 }
 354         }
 355         thr->td = NULL;
 356         hammer2_thr_signal(thr, HAMMER2_THREAD_STOPPED);
 357         /* structure can go invalid at this point */
 358 }
 359
 360 int
 361 hammer2_bulkfree_pass(hammer2_dev_t *hmp, hammer2_chain_t *vchain,
 362                       hammer2_ioc_bulkfree_t *bfi)
 363 {
 364         hammer2_bulkfree_info_t cbinfo;
 365         hammer2_chain_save_t *save;
 366         hammer2_off_t incr;
 367         size_t size;
 368         int error;
 369
 370         /*
 371          * We have to clear the live dedup cache as it might have entries
 372          * that are freeable as of now.  Any new entries in the dedup cache
 373          * made after this point, even if they become freeable, will have
 374          * previously been fully allocated and will be protected by the
 375          * 2-stage bulkfree.
 376          */
 377         hammer2_dedup_clear(hmp);
 378
 379         /*
 380          * Setup for free pass
 381          */
 382         bzero(&cbinfo, sizeof(cbinfo));
 383         size = (bfi->size + HAMMER2_FREEMAP_LEVELN_PSIZE - 1) &
 384                ~(size_t)(HAMMER2_FREEMAP_LEVELN_PSIZE - 1);
 385         if (size < 1024 * 1024)
 386                 size = 1024 * 1024;
 387         if (size > 64 * 1024 * 1024)
 388                 size = 64 * 1024 * 1024;
 389
 390         cbinfo.hmp = hmp;
 391         cbinfo.bmap = kmem_alloc_swapbacked(&cbinfo.kp, size, VM_SUBSYS_HAMMER);
 392         cbinfo.saved_mirror_tid = hmp->voldata.mirror_tid;
 393
 394         cbinfo.dedup = kmalloc(sizeof(*cbinfo.dedup) * HAMMER2_DEDUP_HEUR_SIZE,
 395                                M_HAMMER2, M_WAITOK | M_ZERO);
 396
 397         /*
 398          * Normalize start point to a 2GB boundary.  We operate on a
 399          * 64KB leaf bitmap boundary which represents 2GB of storage.
 400          */
 401         cbinfo.sbase = bfi->sbase;
 402         if (cbinfo.sbase > hmp->voldata.volu_size)
 403                 cbinfo.sbase = hmp->voldata.volu_size;
 404         cbinfo.sbase &= ~HAMMER2_FREEMAP_LEVEL1_MASK;
 405         TAILQ_INIT(&cbinfo.list);
 406
 407         /*
 408          * Loop on a full meta-data scan as many times as required to
 409          * get through all available storage.
 410          */
 411         error = 0;
 412         while (cbinfo.sbase < hmp->voldata.volu_size) {
 413                 /*
 414                  * We have enough ram to represent (incr) bytes of storage.
 415                  * Each 64KB of ram represents 2GB of storage.
 416                  *
 417                  * We must also clean out our de-duplication heuristic for
 418                  * each (incr) bytes of storage, otherwise we wind up not
 419                  * scanning meta-data for later areas of storage because
 420                  * they had already been scanned in earlier areas of storage.
 421                  * Since the ranging is different, we have to restart
 422                  * the dedup heuristic too.
 423                  */
 424                 cbinfo_bmap_init(&cbinfo, size);
 425                 bzero(cbinfo.dedup, sizeof(*cbinfo.dedup) *
 426                                     HAMMER2_DEDUP_HEUR_SIZE);
 427                 cbinfo.count_inodes_scanned = 0;
 428                 cbinfo.count_dirents_scanned = 0;
 429                 cbinfo.count_bytes_scanned = 0;
 430                 cbinfo.count_chains_scanned = 0;
 431                 cbinfo.count_chains_reported = 0;
 432
 433                 incr = size / HAMMER2_FREEMAP_LEVELN_PSIZE *
 434                        HAMMER2_FREEMAP_LEVEL1_SIZE;
 435                 if (hmp->voldata.volu_size - cbinfo.sbase < incr)
 436                         cbinfo.sstop = hmp->voldata.volu_size;
 437                 else
 438                         cbinfo.sstop = cbinfo.sbase + incr;
 439                 if (hammer2_debug & 1) {
 440                         kprintf("bulkfree pass %016jx/%jdGB\n",
 441                                 (intmax_t)cbinfo.sbase,
 442                                 (intmax_t)incr / HAMMER2_FREEMAP_LEVEL1_SIZE);
 443                 }
 444
 445                 /*
 446                  * Scan topology for stuff inside this range.
 447                  *
 448                  * NOTE - By not using a transaction the operation can
 449                  *        run concurrent with the frontend as well as
 450                  *        with flushes.
 451                  *
 452                  *        We cannot safely set a mtid without a transaction,
 453                  *        and in fact we don't want to set one anyway.  We
 454                  *        want the bulkfree to be passive and no interfere
 455                  *        with crash recovery.
 456                  */
 457 #undef HAMMER2_BULKFREE_TRANS   /* undef - don't use transaction */
 458 #ifdef HAMMER2_BULKFREE_TRANS
 459                 hammer2_trans_init(hmp->spmp, 0);
 460                 cbinfo.mtid = hammer2_trans_sub(hmp->spmp);
 461 #else
 462                 cbinfo.mtid = 0;
 463 #endif
 464                 cbinfo.pri = 0;
 465                 error |= hammer2_bulk_scan(vchain, h2_bulkfree_callback,
 466                                            &cbinfo);
 467
 468                 while ((save = TAILQ_FIRST(&cbinfo.list)) != NULL &&
 469                        error == 0) {
 470                         TAILQ_REMOVE(&cbinfo.list, save, entry);
 471                         cbinfo.pri = 0;
 472                         error |= hammer2_bulk_scan(save->chain,
 473                                                      h2_bulkfree_callback,
 474                                                      &cbinfo);
 475                         hammer2_chain_drop(save->chain);
 476                         kfree(save, M_HAMMER2);
 477                 }
 478                 while (save) {
 479                         TAILQ_REMOVE(&cbinfo.list, save, entry);
 480                         hammer2_chain_drop(save->chain);
 481                         kfree(save, M_HAMMER2);
 482                         save = TAILQ_FIRST(&cbinfo.list);
 483                 }
 484
 485                 kprintf("bulkfree lastdrop %d %d error=0x%04x\n",
 486                         vchain->refs, vchain->core.chain_count, error);
 487
 488                 /*
 489                  * If complete scan succeeded we can synchronize our
 490                  * in-memory freemap against live storage.  If an abort
 491                  * did occur we cannot safely synchronize our partially
 492                  * filled-out in-memory freemap.
 493                  */
 494                 if (error == 0) {
 495                         error = h2_bulkfree_sync(&cbinfo);
 496
 497                         hammer2_voldata_lock(hmp);
 498                         hammer2_voldata_modify(hmp);
 499                         hmp->voldata.allocator_free += cbinfo.adj_free;
 500                         hammer2_voldata_unlock(hmp);
 501                 }
 502
 503                 /*
 504                  * Cleanup for next loop.
 505                  */
 506 #ifdef HAMMER2_BULKFREE_TRANS
 507                 hammer2_trans_done(hmp->spmp);
 508 #endif
 509                 if (error)
 510                         break;
 511                 cbinfo.sbase = cbinfo.sstop;
 512                 cbinfo.adj_free = 0;
 513         }
 514         kmem_free_swapbacked(&cbinfo.kp);
 515         kfree(cbinfo.dedup, M_HAMMER2);
 516         cbinfo.dedup = NULL;
 517
 518         bfi->sstop = cbinfo.sbase;
 519
 520         incr = bfi->sstop / (hmp->voldata.volu_size / 10000);
 521         if (incr > 10000)
 522                 incr = 10000;
 523
 524         kprintf("bulkfree pass statistics (%d.%02d%% storage processed):\n",
 525                 (int)incr / 100,
 526                 (int)incr % 100);
 527
 528         if (error) {
 529                 kprintf("    bulkfree was aborted\n");
 530         } else {
 531                 kprintf("    transition->free   %ld\n", cbinfo.count_10_00);
 532                 kprintf("    transition->staged %ld\n", cbinfo.count_11_10);
 533                 kprintf("    ERR(00)->allocated %ld\n", cbinfo.count_00_11);
 534                 kprintf("    ERR(01)->allocated %ld\n", cbinfo.count_01_11);
 535                 kprintf("    staged->allocated  %ld\n", cbinfo.count_10_11);
 536                 kprintf("    ~2MB segs cleaned  %ld\n", cbinfo.count_l0cleans);
 537                 kprintf("    linear adjusts     %ld\n",
 538                         cbinfo.count_linadjusts);
 539                 kprintf("    dedup factor       %ld\n",
 540                         cbinfo.count_dedup_factor);
 541         }
 542
 543         return error;
 544 }
 545
 546 static void
 547 cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size)
 548 {
 549         hammer2_bmap_data_t *bmap = cbinfo->bmap;
 550         hammer2_key_t key = cbinfo->sbase;
 551         hammer2_key_t lokey;
 552         hammer2_key_t hikey;
 553
 554         lokey = (cbinfo->hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) &
 555                 ~HAMMER2_SEGMASK64;
 556         hikey = cbinfo->hmp->voldata.volu_size & ~HAMMER2_SEGMASK64;
 557
 558         bzero(bmap, size);
 559         while (size) {
 560                 bzero(bmap, sizeof(*bmap));
 561                 if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX))
 562                         lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX);
 563                 if (lokey < H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64)
 564                         lokey = H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64;
 565                 if (key < lokey || key >= hikey) {
 566                         memset(bmap->bitmapq, -1,
 567                                sizeof(bmap->bitmapq));
 568                         bmap->avail = 0;
 569                         bmap->linear = HAMMER2_SEGSIZE;
 570                 } else {
 571                         bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
 572                 }
 573                 size -= sizeof(*bmap);
 574                 key += HAMMER2_FREEMAP_LEVEL0_SIZE;
 575                 ++bmap;
 576         }
 577 }
 578
 579 static int
 580 h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref)
 581 {
 582         hammer2_bmap_data_t *bmap;
 583         hammer2_off_t data_off;
 584         uint16_t class;
 585         size_t bytes;
 586         int radix;
 587
 588         /*
 589          * Check for signal and allow yield to userland during scan
 590          */
 591         if (hammer2_signal_check(&cbinfo->save_time))
 592                 return HAMMER2_ERROR_ABORTED;
 593
 594         /*
 595          * Calculate the data offset and determine if it is within
 596          * the current freemap range being gathered.
 597          */
 598         data_off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX;
 599         if (data_off < cbinfo->sbase || data_off >= cbinfo->sstop)
 600                 return 0;
 601         if (data_off < cbinfo->hmp->voldata.allocator_beg)
 602                 return 0;
 603         if (data_off >= cbinfo->hmp->voldata.volu_size)
 604                 return 0;
 605
 606         /*
 607          * Calculate the information needed to generate the in-memory
 608          * freemap record.
 609          *
 610          * Hammer2 does not allow allocations to cross the L1 (2GB) boundary,
 611          * it's a problem if it does.  (Or L0 (2MB) for that matter).
 612          */
 613         radix = (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
 614         KKASSERT(radix != 0);
 615         bytes = (size_t)1 << radix;
 616         class = (bref->type << 8) | hammer2_devblkradix(radix);
 617
 618         if (data_off + bytes > cbinfo->sstop) {
 619                 kprintf("hammer2_bulkfree_scan: illegal 2GB boundary "
 620                         "%016jx %016jx/%d\n",
 621                         (intmax_t)bref->data_off,
 622                         (intmax_t)bref->key,
 623                         bref->keybits);
 624                 bytes = cbinfo->sstop - data_off;       /* XXX */
 625         }
 626
 627         /*
 628          * Convert to a storage offset relative to the beginning of the
 629          * storage range we are collecting.  Then lookup the level0 bmap entry.
 630          */
 631         data_off -= cbinfo->sbase;
 632         bmap = cbinfo->bmap + (data_off >> HAMMER2_FREEMAP_LEVEL0_RADIX);
 633
 634         /*
 635          * Convert data_off to a bmap-relative value (~4MB storage range).
 636          * Adjust linear, class, and avail.
 637          *
 638          * Hammer2 does not allow allocations to cross the L0 (4MB) boundary,
 639          */
 640         data_off &= HAMMER2_FREEMAP_LEVEL0_MASK;
 641         if (data_off + bytes > HAMMER2_FREEMAP_LEVEL0_SIZE) {
 642                 kprintf("hammer2_bulkfree_scan: illegal 4MB boundary "
 643                         "%016jx %016jx/%d\n",
 644                         (intmax_t)bref->data_off,
 645                         (intmax_t)bref->key,
 646                         bref->keybits);
 647                 bytes = HAMMER2_FREEMAP_LEVEL0_SIZE - data_off;
 648         }
 649
 650         if (bmap->class == 0) {
 651                 bmap->class = class;
 652                 bmap->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
 653         }
 654
 655         /*
 656          * NOTE: bmap->class does not have to match class.  Classification
 657          *       is relaxed when free space is low, so some mixing can occur.
 658          */
 659 #if 0
 660         /*
 661          * XXX removed
 662          */
 663         if (bmap->class != class) {
 664                 kprintf("hammer2_bulkfree_scan: illegal mixed class "
 665                         "%016jx %016jx/%d (%04x vs %04x)\n",
 666                         (intmax_t)bref->data_off,
 667                         (intmax_t)bref->key,
 668                         bref->keybits,
 669                         class, bmap->class);
 670         }
 671 #endif
 672
 673         /*
 674          * Just record the highest byte-granular offset for now.  Do not
 675          * match against allocations which are in multiples of whole blocks.
 676          *
 677          * Make sure that any in-block linear offset at least covers the
 678          * data range.  This can cause bmap->linear to become block-aligned.
 679          */
 680         if (bytes & HAMMER2_FREEMAP_BLOCK_MASK) {
 681                 if (bmap->linear < (int32_t)data_off + (int32_t)bytes)
 682                         bmap->linear = (int32_t)data_off + (int32_t)bytes;
 683         } else if (bmap->linear >= (int32_t)data_off &&
 684                    bmap->linear < (int32_t)data_off + (int32_t)bytes) {
 685                 bmap->linear = (int32_t)data_off + (int32_t)bytes;
 686         }
 687
 688         /*
 689          * Adjust the hammer2_bitmap_t bitmap[HAMMER2_BMAP_ELEMENTS].
 690          * 64-bit entries, 2 bits per entry, to code 11.
 691          *
 692          * NOTE: data_off mask to 524288, shift right by 14 (radix for 16384),
 693          *       and multiply shift amount by 2 for sets of 2 bits.
 694          *
 695          * NOTE: The allocation can be smaller than HAMMER2_FREEMAP_BLOCK_SIZE.
 696          *       also, data_off may not be FREEMAP_BLOCK_SIZE aligned.
 697          */
 698         while (bytes > 0) {
 699                 hammer2_bitmap_t bmask;
 700                 int bindex;
 701
 702                 bindex = (int)data_off >> (HAMMER2_FREEMAP_BLOCK_RADIX +
 703                                            HAMMER2_BMAP_INDEX_RADIX);
 704                 bmask = (hammer2_bitmap_t)3 <<
 705                         ((((int)data_off & HAMMER2_BMAP_INDEX_MASK) >>
 706                          HAMMER2_FREEMAP_BLOCK_RADIX) << 1);
 707
 708                 /*
 709                  * NOTE! The (avail) calculation is bitmap-granular.  Multiple
 710                  *       sub-granular records can wind up at the same bitmap
 711                  *       position.
 712                  */
 713                 if ((bmap->bitmapq[bindex] & bmask) == 0) {
 714                         if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE) {
 715                                 bmap->avail -= HAMMER2_FREEMAP_BLOCK_SIZE;
 716                         } else {
 717                                 bmap->avail -= bytes;
 718                         }
 719                         bmap->bitmapq[bindex] |= bmask;
 720                 }
 721                 data_off += HAMMER2_FREEMAP_BLOCK_SIZE;
 722                 if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE)
 723                         bytes = 0;
 724                 else
 725                         bytes -= HAMMER2_FREEMAP_BLOCK_SIZE;
 726         }
 727         return 0;
 728 }
 729
 730 /*
 731  * Synchronize the in-memory bitmap with the live freemap.  This is not a
 732  * direct copy.  Instead the bitmaps must be compared:
 733  *
 734  *      In-memory       Live-freemap
 735  *         00             11 -> 10      (do nothing if live modified)
 736  *                        10 -> 00      (do nothing if live modified)
 737  *         11             10 -> 11      handles race against live
 738  *                        ** -> 11      nominally warn of corruption
 739  *
 740  * We must also fixup the hints in HAMMER2_BREF_TYPE_FREEMAP_LEAF.
 741  */
 742 static int
 743 h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo)
 744 {
 745         hammer2_off_t data_off;
 746         hammer2_key_t key;
 747         hammer2_key_t key_dummy;
 748         hammer2_bmap_data_t *bmap;
 749         hammer2_bmap_data_t *live;
 750         hammer2_chain_t *live_parent;
 751         hammer2_chain_t *live_chain;
 752         int bmapindex;
 753         int error;
 754
 755         kprintf("hammer2_bulkfree - range ");
 756
 757         if (cbinfo->sbase < cbinfo->hmp->voldata.allocator_beg)
 758                 kprintf("%016jx-",
 759                         (intmax_t)cbinfo->hmp->voldata.allocator_beg);
 760         else
 761                 kprintf("%016jx-",
 762                         (intmax_t)cbinfo->sbase);
 763
 764         if (cbinfo->sstop > cbinfo->hmp->voldata.volu_size)
 765                 kprintf("%016jx\n",
 766                         (intmax_t)cbinfo->hmp->voldata.volu_size);
 767         else
 768                 kprintf("%016jx\n",
 769                         (intmax_t)cbinfo->sstop);
 770
 771         data_off = cbinfo->sbase;
 772         bmap = cbinfo->bmap;
 773
 774         live_parent = &cbinfo->hmp->fchain;
 775         hammer2_chain_ref(live_parent);
 776         hammer2_chain_lock(live_parent, HAMMER2_RESOLVE_ALWAYS);
 777         live_chain = NULL;
 778         error = 0;
 779
 780         /*
 781          * Iterate each hammer2_bmap_data_t line (128 bytes) managing
 782          * 4MB of storage.
 783          */
 784         while (data_off < cbinfo->sstop) {
 785                 /*
 786                  * The freemap is not used below allocator_beg or beyond
 787                  * volu_size.
 788                  */
 789
 790                 if (data_off < cbinfo->hmp->voldata.allocator_beg)
 791                         goto next;
 792                 if (data_off >= cbinfo->hmp->voldata.volu_size)
 793                         goto next;
 794
 795                 /*
 796                  * Locate the freemap leaf on the live filesystem
 797                  */
 798                 key = (data_off & ~HAMMER2_FREEMAP_LEVEL1_MASK);
 799
 800                 if (live_chain == NULL || live_chain->bref.key != key) {
 801                         if (live_chain) {
 802                                 hammer2_chain_unlock(live_chain);
 803                                 hammer2_chain_drop(live_chain);
 804                         }
 805                         live_chain = hammer2_chain_lookup(
 806                                             &live_parent,
 807                                             &key_dummy,
 808                                             key,
 809                                             key + HAMMER2_FREEMAP_LEVEL1_MASK,
 810                                             &error,
 811                                             HAMMER2_LOOKUP_ALWAYS);
 812                         if (error) {
 813                                 kprintf("hammer2_bulkfree: freemap lookup "
 814                                         "error near %016jx, error %s\n",
 815                                         (intmax_t)data_off,
 816                                         hammer2_error_str(live_chain->error));
 817                                 break;
 818                         }
 819                 }
 820                 if (live_chain == NULL) {
 821                         /*
 822                          * XXX if we implement a full recovery mode we need
 823                          * to create/recreate missing freemap chains if our
 824                          * bmap has any allocated blocks.
 825                          */
 826                         if (bmap->class &&
 827                             bmap->avail != HAMMER2_FREEMAP_LEVEL0_SIZE) {
 828                                 kprintf("hammer2_bulkfree: cannot locate "
 829                                         "live leaf for allocated data "
 830                                         "near %016jx\n",
 831                                         (intmax_t)data_off);
 832                         }
 833                         goto next;
 834                 }
 835                 if (live_chain->error) {
 836                         kprintf("hammer2_bulkfree: unable to access freemap "
 837                                 "near %016jx, error %s\n",
 838                                 (intmax_t)data_off,
 839                                 hammer2_error_str(live_chain->error));
 840                         hammer2_chain_unlock(live_chain);
 841                         hammer2_chain_drop(live_chain);
 842                         live_chain = NULL;
 843                         goto next;
 844                 }
 845
 846                 bmapindex = (data_off & HAMMER2_FREEMAP_LEVEL1_MASK) >>
 847                             HAMMER2_FREEMAP_LEVEL0_RADIX;
 848                 live = &live_chain->data->bmdata[bmapindex];
 849
 850                 /*
 851                  * Shortcut if the bitmaps match and the live linear
 852                  * indicator is sane.  We can't do a perfect check of
 853                  * live->linear because the only real requirement is that
 854                  * if it is not block-aligned, that it not cover the space
 855                  * within its current block which overlaps one of the data
 856                  * ranges we scan.  We don't retain enough fine-grained
 857                  * data in our scan to be able to set it exactly.
 858                  *
 859                  * TODO - we could shortcut this by testing that both
 860                  * live->class and bmap->class are 0, and both avails are
 861                  * set to HAMMER2_FREEMAP_LEVEL0_SIZE (4MB).
 862                  */
 863                 if (bcmp(live->bitmapq, bmap->bitmapq,
 864                          sizeof(bmap->bitmapq)) == 0 &&
 865                     live->linear >= bmap->linear) {
 866                         goto next;
 867                 }
 868                 if (hammer2_debug & 1) {
 869                         kprintf("live %016jx %04d.%04x (avail=%d)\n",
 870                                 data_off, bmapindex, live->class, live->avail);
 871                 }
 872
 873                 hammer2_chain_modify(live_chain, cbinfo->mtid, 0, 0);
 874                 live_chain->bref.check.freemap.bigmask = -1;
 875                 cbinfo->hmp->freemap_relaxed = 0;       /* reset heuristic */
 876                 live = &live_chain->data->bmdata[bmapindex];
 877
 878                 h2_bulkfree_sync_adjust(cbinfo, data_off, live, bmap,
 879                                         live_chain->bref.key +
 880                                         bmapindex *
 881                                         HAMMER2_FREEMAP_LEVEL0_SIZE);
 882 next:
 883                 data_off += HAMMER2_FREEMAP_LEVEL0_SIZE;
 884                 ++bmap;
 885         }
 886         if (live_chain) {
 887                 hammer2_chain_unlock(live_chain);
 888                 hammer2_chain_drop(live_chain);
 889         }
 890         if (live_parent) {
 891                 hammer2_chain_unlock(live_parent);
 892                 hammer2_chain_drop(live_parent);
 893         }
 894         return error;
 895 }
 896
 897 /*
 898  * Merge the bulkfree bitmap against the existing bitmap.
 899  */
 900 static
 901 void
 902 h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
 903                         hammer2_off_t data_off, hammer2_bmap_data_t *live,
 904                         hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base)
 905 {
 906         int bindex;
 907         int scount;
 908         hammer2_off_t tmp_off;
 909         hammer2_bitmap_t lmask;
 910         hammer2_bitmap_t mmask;
 911
 912         tmp_off = data_off;
 913
 914         for (bindex = 0; bindex < HAMMER2_BMAP_ELEMENTS; ++bindex) {
 915                 lmask = live->bitmapq[bindex];  /* live */
 916                 mmask = bmap->bitmapq[bindex];  /* snapshotted bulkfree */
 917                 if (lmask == mmask) {
 918                         tmp_off += HAMMER2_BMAP_INDEX_SIZE;
 919                         continue;
 920                 }
 921
 922                 for (scount = 0;
 923                      scount < HAMMER2_BMAP_BITS_PER_ELEMENT;
 924                      scount += 2) {
 925                         if ((mmask & 3) == 0) {
 926                                 /*
 927                                  * in-memory 00         live 11 -> 10
 928                                  *                      live 10 -> 00
 929                                  *
 930                                  * Storage might be marked allocated or
 931                                  * staged and must be remarked staged or
 932                                  * free.
 933                                  */
 934                                 switch (lmask & 3) {
 935                                 case 0: /* 00 */
 936                                         break;
 937                                 case 1: /* 01 */
 938                                         kprintf("hammer2_bulkfree: cannot "
 939                                                 "transition m=00/l=01\n");
 940                                         break;
 941                                 case 2: /* 10 -> 00 */
 942                                         live->bitmapq[bindex] &=
 943                                             ~((hammer2_bitmap_t)2 << scount);
 944                                         live->avail +=
 945                                                 HAMMER2_FREEMAP_BLOCK_SIZE;
 946                                         if (live->avail >
 947                                             HAMMER2_FREEMAP_LEVEL0_SIZE) {
 948                                                 live->avail =
 949                                                     HAMMER2_FREEMAP_LEVEL0_SIZE;
 950                                         }
 951                                         cbinfo->adj_free +=
 952                                                 HAMMER2_FREEMAP_BLOCK_SIZE;
 953                                         ++cbinfo->count_10_00;
 954                                         hammer2_io_dedup_assert(
 955                                                 cbinfo->hmp,
 956                                                 tmp_off |
 957                                                 HAMMER2_FREEMAP_BLOCK_RADIX,
 958                                                 HAMMER2_FREEMAP_BLOCK_SIZE);
 959                                         break;
 960                                 case 3: /* 11 -> 10 */
 961                                         live->bitmapq[bindex] &=
 962                                             ~((hammer2_bitmap_t)1 << scount);
 963                                         ++cbinfo->count_11_10;
 964                                         hammer2_io_dedup_delete(
 965                                                 cbinfo->hmp,
 966                                                 HAMMER2_BREF_TYPE_DATA,
 967                                                 tmp_off |
 968                                                 HAMMER2_FREEMAP_BLOCK_RADIX,
 969                                                 HAMMER2_FREEMAP_BLOCK_SIZE);
 970                                         break;
 971                                 }
 972                         } else if ((mmask & 3) == 3) {
 973                                 /*
 974                                  * in-memory 11         live 10 -> 11
 975                                  *                      live ** -> 11
 976                                  *
 977                                  * Storage might be incorrectly marked free
 978                                  * or staged and must be remarked fully
 979                                  * allocated.
 980                                  */
 981                                 switch (lmask & 3) {
 982                                 case 0: /* 00 */
 983                                         ++cbinfo->count_00_11;
 984                                         cbinfo->adj_free -=
 985                                                 HAMMER2_FREEMAP_BLOCK_SIZE;
 986                                         live->avail -=
 987                                                 HAMMER2_FREEMAP_BLOCK_SIZE;
 988                                         if ((int32_t)live->avail < 0)
 989                                                 live->avail = 0;
 990                                         break;
 991                                 case 1: /* 01 */
 992                                         ++cbinfo->count_01_11;
 993                                         break;
 994                                 case 2: /* 10 -> 11 */
 995                                         ++cbinfo->count_10_11;
 996                                         break;
 997                                 case 3: /* 11 */
 998                                         break;
 999                                 }
1000                                 live->bitmapq[bindex] |=
1001                                         ((hammer2_bitmap_t)3 << scount);
1002                         }
1003                         mmask >>= 2;
1004                         lmask >>= 2;
1005                         tmp_off += HAMMER2_FREEMAP_BLOCK_SIZE;
1006                 }
1007         }
1008
1009         /*
1010          * Determine if the live bitmap is completely free and reset its
1011          * fields if so.  Otherwise check to see if we can reduce the linear
1012          * offset.
1013          */
1014         for (bindex = HAMMER2_BMAP_ELEMENTS - 1; bindex >= 0; --bindex) {
1015                 if (live->bitmapq[bindex] != 0)
1016                         break;
1017         }
1018         if (bindex < 0) {
1019                 /*
1020                  * Completely empty, reset entire segment
1021                  */
1022 #if 0
1023                 kprintf("hammer2: cleanseg %016jx.%04x (%d)\n",
1024                         alloc_base, live->class, live->avail);
1025 #endif
1026                 live->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
1027                 live->class = 0;
1028                 live->linear = 0;
1029                 ++cbinfo->count_l0cleans;
1030         } else if (bindex < 7) {
1031                 /*
1032                  * Partially full, bitmapq[bindex] != 0.  The live->linear
1033                  * offset can legitimately be just about anything, but
1034                  * our bulkfree pass doesn't record enough information to
1035                  * set it exactly.  Just make sure that it is set to a
1036                  * safe value that also works in our match code above (the
1037                  * bcmp and linear test).
1038                  *
1039                  * We cannot safely leave live->linear at a sub-block offset
1040                  * unless it is already in the same block as bmap->linear.
1041                  *
1042                  * If it is not in the same block, we cannot assume that
1043                  * we can set it to bmap->linear on a sub-block boundary,
1044                  * because the live system could have bounced it around.
1045                  * In that situation we satisfy our bcmp/skip requirement
1046                  * above by setting it to the nearest higher block boundary.
1047                  * This alignment effectively kills any partial allocation it
1048                  * might have been tracking before.
1049                  */
1050                 if (live->linear < bmap->linear &&
1051                     ((live->linear ^ bmap->linear) &
1052                      ~HAMMER2_FREEMAP_BLOCK_MASK) == 0) {
1053                         live->linear = bmap->linear;
1054                         ++cbinfo->count_linadjusts;
1055                 } else {
1056                         live->linear =
1057                                 (bmap->linear + HAMMER2_FREEMAP_BLOCK_MASK) &
1058                                 ~HAMMER2_FREEMAP_BLOCK_MASK;
1059                         ++cbinfo->count_linadjusts;
1060                 }
1061         } else {
1062                 /*
1063                  * Completely full, effectively disable the linear iterator
1064                  */
1065                 live->linear = HAMMER2_SEGSIZE;
1066         }
1067
1068 #if 0
1069         if (bmap->class) {
1070                 kprintf("%016jx %04d.%04x (avail=%7d) "
1071                         "%08x %08x %08x %08x %08x %08x %08x %08x\n",
1072                         (intmax_t)data_off,
1073                         (int)((data_off &
1074                                HAMMER2_FREEMAP_LEVEL1_MASK) >>
1075                               HAMMER2_FREEMAP_LEVEL0_RADIX),
1076                         bmap->class,
1077                         bmap->avail,
1078                         bmap->bitmap[0], bmap->bitmap[1],
1079                         bmap->bitmap[2], bmap->bitmap[3],
1080                         bmap->bitmap[4], bmap->bitmap[5],
1081                         bmap->bitmap[6], bmap->bitmap[7]);
1082         }
1083 #endif
1084 }
1085
1086 /*
1087  * BULKFREE DEDUP HEURISTIC
1088  *
1089  * WARNING! This code is SMP safe but the heuristic allows SMP collisions.
1090  *          All fields must be loaded into locals and validated.
1091  */
1092 static
1093 int
1094 h2_bulkfree_test(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref,
1095                  int pri)
1096 {
1097         hammer2_dedup_t *dedup;
1098         int best;
1099         int n;
1100         int i;
1101
1102         n = hammer2_icrc32(&bref->data_off, sizeof(bref->data_off));
1103         dedup = cbinfo->dedup + (n & (HAMMER2_DEDUP_HEUR_MASK & ~7));
1104
1105         for (i = best = 0; i < 8; ++i) {
1106                 if (dedup[i].data_off == bref->data_off) {
1107                         if (dedup[i].ticks < pri)
1108                                 dedup[i].ticks = pri;
1109                         if (pri == 1)
1110                                 cbinfo->count_dedup_factor += dedup[i].ticks;
1111                         return 1;
1112                 }
1113                 if (dedup[i].ticks < dedup[best].ticks)
1114                         best = i;
1115         }
1116         dedup[best].data_off = bref->data_off;
1117         dedup[best].ticks = pri;
1118
1119         return 0;
1120 }