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