2 * Copyright (c) 2013-2015 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@dragonflybsd.org>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 #include <sys/param.h>
35 #include <sys/systm.h>
36 #include <sys/kernel.h>
37 #include <sys/fcntl.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>
49 #define H2FMBASE(key, radix) ((key) & ~(((hammer2_off_t)1 << (radix)) - 1))
50 #define H2FMSHIFT(radix) ((hammer2_off_t)1 << (radix))
53 * breadth-first search
55 typedef struct hammer2_chain_save {
56 TAILQ_ENTRY(hammer2_chain_save) entry;
57 hammer2_chain_t *chain;
59 } hammer2_chain_save_t;
61 TAILQ_HEAD(hammer2_chain_save_list, hammer2_chain_save);
62 typedef struct hammer2_chain_save_list hammer2_chain_save_list_t;
64 typedef struct hammer2_bulkfree_info {
67 hammer2_off_t sbase; /* sub-loop iteration */
69 hammer2_bmap_data_t *bmap;
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 */
77 long count_linadjusts;
78 long count_inodes_scanned;
79 long count_dedup_factor;
81 hammer2_off_t adj_free;
83 hammer2_tid_t saved_mirror_tid;
85 hammer2_chain_save_list_t list;
86 hammer2_dedup_t *dedup;
88 } hammer2_bulkfree_info_t;
90 static int h2_bulkfree_test(hammer2_bulkfree_info_t *info,
91 hammer2_blockref_t *bref, int pri);
94 * General bulk scan function with callback. Called with a referenced
95 * but UNLOCKED parent. The parent is returned in the same state.
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)
104 hammer2_blockref_t bref;
105 hammer2_chain_t *chain;
106 int cache_index = -1;
112 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS |
113 HAMMER2_RESOLVE_SHARED);
117 * Generally loop on the contents if we have not been flagged
120 * Remember that these chains are completely isolated from
121 * the frontend, so we can release locks temporarily without
124 while ((doabort & HAMMER2_BULK_ABORT) == 0 &&
125 hammer2_chain_scan(parent, &chain, &bref, &first,
127 HAMMER2_LOOKUP_NODATA |
128 HAMMER2_LOOKUP_SHARED) != NULL) {
130 * Process bref, chain is only non-NULL if the bref
131 * might be recursable (its possible that we sometimes get
132 * a non-NULL chain where the bref cannot be recursed).
135 kprintf("SCAN %p/%p %016jx.%02x\n",
136 parent, chain, bref.data_off, bref.type);
137 int xerr = tsleep(&info->pri, PCATCH, "slp", hz / 10);
138 if (xerr == EINTR || xerr == ERESTART) {
139 doabort |= HAMMER2_BULK_ABORT;
143 if (h2_bulkfree_test(info, &bref, 1))
146 doabort |= func(info, &bref);
148 if (doabort & HAMMER2_BULK_ABORT)
152 * A non-null chain is always returned if it is
153 * recursive, otherwise a non-null chain might be
154 * returned but usually is not when not recursive.
160 * Else check type and setup depth-first scan.
162 * Account for bytes actually read.
164 info->bytes_scanned += chain->bytes;
166 switch(chain->bref.type) {
167 case HAMMER2_BREF_TYPE_INODE:
168 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
169 case HAMMER2_BREF_TYPE_INDIRECT:
170 case HAMMER2_BREF_TYPE_VOLUME:
171 case HAMMER2_BREF_TYPE_FREEMAP:
173 if (info->depth > 16) {
174 hammer2_chain_save_t *save;
175 save = kmalloc(sizeof(*save), M_HAMMER2,
178 hammer2_chain_ref(chain);
179 TAILQ_INSERT_TAIL(&info->list, save, entry);
184 int savepri = info->pri;
186 hammer2_chain_unlock(chain);
188 doabort |= hammer2_bulk_scan(chain, func, info);
189 info->pri += savepri;
190 hammer2_chain_lock(chain,
191 HAMMER2_RESOLVE_ALWAYS |
192 HAMMER2_RESOLVE_SHARED);
197 /* does not recurse */
202 hammer2_chain_unlock(chain);
203 hammer2_chain_drop(chain);
207 * Save with higher pri now that we know what it is.
209 h2_bulkfree_test(info, &parent->bref, info->pri + 1);
211 hammer2_chain_unlock(parent);
220 * Chain flush (partial synchronization) XXX removed
221 * Scan the whole topology - build in-memory freemap (mark 11)
222 * Reconcile the in-memory freemap against the on-disk freemap.
223 * ondisk xx -> ondisk 11 (if allocated)
224 * ondisk 11 -> ondisk 10 (if free in-memory)
225 * ondisk 10 -> ondisk 00 (if free in-memory) - on next pass
228 * The topology scan may have to be performed multiple times to window
229 * freemaps which are too large to fit in kernel memory.
231 * Races are handled using a double-transition (11->10, 10->00). The bulkfree
232 * scan snapshots the volume root's blockset and thus can run concurrent with
233 * normal operations, as long as a full flush is made between each pass to
234 * synchronize any modified chains (otherwise their blocks might be improperly
237 * Temporary memory in multiples of 64KB is required to reconstruct the leaf
238 * hammer2_bmap_data blocks so they can later be compared against the live
239 * freemap. Each 64KB block represents 128 x 16KB x 1024 = ~2 GB of storage.
240 * A 32MB save area thus represents around ~1 TB. The temporary memory
241 * allocated can be specified. If it is not sufficient multiple topology
242 * passes will be made.
246 * Bulkfree callback info
248 static void hammer2_bulkfree_thread(void *arg __unused);
249 static void cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size);
250 static int h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo,
251 hammer2_blockref_t *bref);
252 static void h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo);
253 static void h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
254 hammer2_off_t data_off, hammer2_bmap_data_t *live,
255 hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base);
258 hammer2_bulkfree_init(hammer2_dev_t *hmp)
260 hammer2_thr_create(&hmp->bfthr, NULL, hmp,
261 hmp->devrepname, -1, -1,
262 hammer2_bulkfree_thread);
266 hammer2_bulkfree_uninit(hammer2_dev_t *hmp)
268 hammer2_thr_delete(&hmp->bfthr);
272 hammer2_bulkfree_thread(void *arg)
274 hammer2_thread_t *thr = arg;
275 hammer2_ioc_bulkfree_t bfi;
279 hammer2_thr_wait_any(thr,
280 HAMMER2_THREAD_STOP |
281 HAMMER2_THREAD_FREEZE |
282 HAMMER2_THREAD_UNFREEZE |
283 HAMMER2_THREAD_REMASTER,
288 if (flags & HAMMER2_THREAD_STOP)
290 if (flags & HAMMER2_THREAD_FREEZE) {
291 hammer2_thr_signal2(thr, HAMMER2_THREAD_FROZEN,
292 HAMMER2_THREAD_FREEZE);
295 if (flags & HAMMER2_THREAD_UNFREEZE) {
296 hammer2_thr_signal2(thr, 0,
297 HAMMER2_THREAD_FROZEN |
298 HAMMER2_THREAD_UNFREEZE);
301 if (flags & HAMMER2_THREAD_FROZEN)
303 if (flags & HAMMER2_THREAD_REMASTER) {
304 hammer2_thr_signal2(thr, 0, HAMMER2_THREAD_REMASTER);
305 bzero(&bfi, sizeof(bfi));
306 bfi.size = 8192 * 1024;
307 /* hammer2_bulkfree_pass(thr->hmp, &bfi); */
311 hammer2_thr_signal(thr, HAMMER2_THREAD_STOPPED);
312 /* structure can go invalid at this point */
316 hammer2_bulkfree_pass(hammer2_dev_t *hmp, hammer2_chain_t *vchain,
317 hammer2_ioc_bulkfree_t *bfi)
319 hammer2_bulkfree_info_t cbinfo;
320 hammer2_chain_save_t *save;
326 * We have to clear the live dedup cache as it might have entries
327 * that are freeable as of now. Any new entries in the dedup cache
328 * made after this point, even if they become freeable, will have
329 * previously been fully allocated and will be protected by the
332 hammer2_dedup_clear(hmp);
335 * Setup for free pass
337 bzero(&cbinfo, sizeof(cbinfo));
338 size = (bfi->size + HAMMER2_FREEMAP_LEVELN_PSIZE - 1) &
339 ~(size_t)(HAMMER2_FREEMAP_LEVELN_PSIZE - 1);
341 cbinfo.bmap = kmem_alloc_swapbacked(&cbinfo.kp, size, VM_SUBSYS_HAMMER);
342 cbinfo.saved_mirror_tid = hmp->voldata.mirror_tid;
344 cbinfo.dedup = kmalloc(sizeof(*cbinfo.dedup) * HAMMER2_DEDUP_HEUR_SIZE,
345 M_HAMMER2, M_WAITOK | M_ZERO);
348 * Normalize start point to a 2GB boundary. We operate on a
349 * 64KB leaf bitmap boundary which represents 2GB of storage.
351 cbinfo.sbase = bfi->sbase;
352 if (cbinfo.sbase > hmp->voldata.volu_size)
353 cbinfo.sbase = hmp->voldata.volu_size;
354 cbinfo.sbase &= ~HAMMER2_FREEMAP_LEVEL1_MASK;
355 TAILQ_INIT(&cbinfo.list);
358 * Loop on a full meta-data scan as many times as required to
359 * get through all available storage.
361 while (cbinfo.sbase < hmp->voldata.volu_size) {
363 * We have enough ram to represent (incr) bytes of storage.
364 * Each 64KB of ram represents 2GB of storage.
366 * We must also clean out our de-duplication heuristic for
367 * each (incr) bytes of storage, otherwise we wind up not
368 * scanning meta-data for later areas of storage because
369 * they had already been scanned in earlier areas of storage.
370 * Since the ranging is different, we have to restart
371 * the dedup heuristic too.
373 cbinfo_bmap_init(&cbinfo, size);
374 bzero(cbinfo.dedup, sizeof(*cbinfo.dedup) *
375 HAMMER2_DEDUP_HEUR_SIZE);
376 incr = size / HAMMER2_FREEMAP_LEVELN_PSIZE *
377 HAMMER2_FREEMAP_LEVEL1_SIZE;
378 if (hmp->voldata.volu_size - cbinfo.sbase < incr)
379 cbinfo.sstop = hmp->voldata.volu_size;
381 cbinfo.sstop = cbinfo.sbase + incr;
382 if (hammer2_debug & 1) {
383 kprintf("bulkfree pass %016jx/%jdGB\n",
384 (intmax_t)cbinfo.sbase,
385 (intmax_t)incr / HAMMER2_FREEMAP_LEVEL1_SIZE);
389 * Scan topology for stuff inside this range.
391 hammer2_trans_init(hmp->spmp, 0);
392 cbinfo.mtid = hammer2_trans_sub(hmp->spmp);
394 doabort |= hammer2_bulk_scan(vchain, h2_bulkfree_callback,
397 while ((save = TAILQ_FIRST(&cbinfo.list)) != NULL &&
399 TAILQ_REMOVE(&cbinfo.list, save, entry);
401 doabort |= hammer2_bulk_scan(save->chain,
402 h2_bulkfree_callback,
404 hammer2_chain_drop(save->chain);
405 kfree(save, M_HAMMER2);
408 TAILQ_REMOVE(&cbinfo.list, save, entry);
409 hammer2_chain_drop(save->chain);
410 kfree(save, M_HAMMER2);
411 save = TAILQ_FIRST(&cbinfo.list);
414 kprintf("bulkfree lastdrop %d %d doabort=%d\n",
415 vchain->refs, vchain->core.chain_count, doabort);
418 * If complete scan succeeded we can synchronize our
419 * in-memory freemap against live storage. If an abort
420 * did occur we cannot safely synchronize our partially
421 * filled-out in-memory freemap.
424 h2_bulkfree_sync(&cbinfo);
426 hammer2_voldata_lock(hmp);
427 hammer2_voldata_modify(hmp);
428 hmp->voldata.allocator_free += cbinfo.adj_free;
429 hammer2_voldata_unlock(hmp);
433 * Cleanup for next loop.
435 hammer2_trans_done(hmp->spmp);
438 cbinfo.sbase = cbinfo.sstop;
441 kmem_free_swapbacked(&cbinfo.kp);
442 kfree(cbinfo.dedup, M_HAMMER2);
445 bfi->sstop = cbinfo.sbase;
447 incr = bfi->sstop / (hmp->voldata.volu_size / 10000);
451 kprintf("bulkfree pass statistics (%d.%02d%% storage processed):\n",
455 kprintf(" transition->free %ld\n", cbinfo.count_10_00);
456 kprintf(" transition->staged %ld\n", cbinfo.count_11_10);
457 kprintf(" ERR(00)->allocated %ld\n", cbinfo.count_00_11);
458 kprintf(" ERR(01)->allocated %ld\n", cbinfo.count_01_11);
459 kprintf(" staged->allocated %ld\n", cbinfo.count_10_11);
460 kprintf(" ~2MB segs cleaned %ld\n", cbinfo.count_l0cleans);
461 kprintf(" linear adjusts %ld\n", cbinfo.count_linadjusts);
462 kprintf(" dedup factor %ld\n", cbinfo.count_dedup_factor);
468 cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size)
470 hammer2_bmap_data_t *bmap = cbinfo->bmap;
471 hammer2_key_t key = cbinfo->sbase;
475 lokey = (cbinfo->hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) &
477 hikey = cbinfo->hmp->voldata.volu_size & ~HAMMER2_SEGMASK64;
481 if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
482 HAMMER2_ZONE_SEG64) {
483 lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
486 if (key < lokey || key >= hikey) {
487 memset(bmap->bitmapq, -1,
488 sizeof(bmap->bitmapq));
490 bmap->linear = HAMMER2_SEGSIZE;
492 bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX);
494 size -= sizeof(*bmap);
495 key += HAMMER2_FREEMAP_LEVEL0_SIZE;
501 h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref)
503 hammer2_bmap_data_t *bmap;
504 hammer2_off_t data_off;
511 * Check for signal and allow yield to userland during scan
513 if (hammer2_signal_check(&cbinfo->save_time))
514 return HAMMER2_BULK_ABORT;
515 if (bref->type == HAMMER2_BREF_TYPE_INODE) {
516 ++cbinfo->count_inodes_scanned;
517 if ((cbinfo->count_inodes_scanned & 65535) == 0)
518 kprintf(" inodes %6ld bytes %9ld\n",
519 cbinfo->count_inodes_scanned,
520 cbinfo->bytes_scanned);
524 * Calculate the data offset and determine if it is within
525 * the current freemap range being gathered.
528 data_off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX;
529 if (data_off < cbinfo->sbase || data_off >= cbinfo->sstop)
531 if (data_off < cbinfo->hmp->voldata.allocator_beg)
533 if (data_off >= cbinfo->hmp->voldata.volu_size)
537 * Calculate the information needed to generate the in-memory
540 * Hammer2 does not allow allocations to cross the L1 (2GB) boundary,
541 * it's a problem if it does. (Or L0 (2MB) for that matter).
543 radix = (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
544 KKASSERT(radix != 0);
545 bytes = (size_t)1 << radix;
546 class = (bref->type << 8) | hammer2_devblkradix(radix);
548 if (data_off + bytes >= cbinfo->sstop) {
549 kprintf("hammer2_bulkfree_scan: illegal 2GB boundary "
550 "%016jx %016jx/%d\n",
551 (intmax_t)bref->data_off,
554 bytes = cbinfo->sstop - data_off; /* XXX */
558 * Convert to a storage offset relative to the beginning of the
559 * storage range we are collecting. Then lookup the level0 bmap entry.
561 data_off -= cbinfo->sbase;
562 bmap = cbinfo->bmap + (data_off >> HAMMER2_FREEMAP_LEVEL0_RADIX);
565 * Convert data_off to a bmap-relative value (~4MB storage range).
566 * Adjust linear, class, and avail.
568 * Hammer2 does not allow allocations to cross the L0 (4MB) boundary,
570 data_off &= HAMMER2_FREEMAP_LEVEL0_MASK;
571 if (data_off + bytes > HAMMER2_FREEMAP_LEVEL0_SIZE) {
572 kprintf("hammer2_bulkfree_scan: illegal 4MB boundary "
573 "%016jx %016jx/%d\n",
574 (intmax_t)bref->data_off,
577 bytes = HAMMER2_FREEMAP_LEVEL0_SIZE - data_off;
580 if (bmap->class == 0) {
582 bmap->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
584 if (bmap->class != class) {
585 kprintf("hammer2_bulkfree_scan: illegal mixed class "
586 "%016jx %016jx/%d (%04x vs %04x)\n",
587 (intmax_t)bref->data_off,
594 * Just record the highest byte-granular offset for now. Do not
595 * match against allocations which are in multiples of whole blocks.
597 * Make sure that any in-block linear offset at least covers the
598 * data range. This can cause bmap->linear to become block-aligned.
600 if (bytes & HAMMER2_FREEMAP_BLOCK_MASK) {
601 if (bmap->linear < (int32_t)data_off + (int32_t)bytes)
602 bmap->linear = (int32_t)data_off + (int32_t)bytes;
603 } else if (bmap->linear >= (int32_t)data_off &&
604 bmap->linear < (int32_t)data_off + (int32_t)bytes) {
605 bmap->linear = (int32_t)data_off + (int32_t)bytes;
609 * Adjust the hammer2_bitmap_t bitmap[HAMMER2_BMAP_ELEMENTS].
610 * 64-bit entries, 2 bits per entry, to code 11.
612 * NOTE: data_off mask to 524288, shift right by 14 (radix for 16384),
613 * and multiply shift amount by 2 for sets of 2 bits.
615 * NOTE: The allocation can be smaller than HAMMER2_FREEMAP_BLOCK_SIZE.
616 * also, data_off may not be FREEMAP_BLOCK_SIZE aligned.
619 hammer2_bitmap_t bmask;
622 bindex = (int)data_off >> (HAMMER2_FREEMAP_BLOCK_RADIX +
623 HAMMER2_BMAP_INDEX_RADIX);
624 bmask = (hammer2_bitmap_t)3 <<
625 ((((int)data_off & HAMMER2_BMAP_INDEX_MASK) >>
626 HAMMER2_FREEMAP_BLOCK_RADIX) << 1);
629 * NOTE! The (avail) calculation is bitmap-granular. Multiple
630 * sub-granular records can wind up at the same bitmap
633 if ((bmap->bitmapq[bindex] & bmask) == 0) {
634 if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE) {
635 bmap->avail -= HAMMER2_FREEMAP_BLOCK_SIZE;
637 bmap->avail -= bytes;
639 bmap->bitmapq[bindex] |= bmask;
641 data_off += HAMMER2_FREEMAP_BLOCK_SIZE;
642 if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE)
645 bytes -= HAMMER2_FREEMAP_BLOCK_SIZE;
651 * Synchronize the in-memory bitmap with the live freemap. This is not a
652 * direct copy. Instead the bitmaps must be compared:
654 * In-memory Live-freemap
655 * 00 11 -> 10 (do nothing if live modified)
656 * 10 -> 00 (do nothing if live modified)
657 * 11 10 -> 11 handles race against live
658 * ** -> 11 nominally warn of corruption
662 h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo)
664 hammer2_off_t data_off;
666 hammer2_key_t key_dummy;
667 hammer2_bmap_data_t *bmap;
668 hammer2_bmap_data_t *live;
669 hammer2_chain_t *live_parent;
670 hammer2_chain_t *live_chain;
671 int cache_index = -1;
674 kprintf("hammer2_bulkfree - range ");
676 if (cbinfo->sbase < cbinfo->hmp->voldata.allocator_beg)
678 (intmax_t)cbinfo->hmp->voldata.allocator_beg);
681 (intmax_t)cbinfo->sbase);
683 if (cbinfo->sstop > cbinfo->hmp->voldata.volu_size)
685 (intmax_t)cbinfo->hmp->voldata.volu_size);
688 (intmax_t)cbinfo->sstop);
690 data_off = cbinfo->sbase;
693 live_parent = &cbinfo->hmp->fchain;
694 hammer2_chain_ref(live_parent);
695 hammer2_chain_lock(live_parent, HAMMER2_RESOLVE_ALWAYS);
699 * Iterate each hammer2_bmap_data_t line (128 bytes) managing
702 while (data_off < cbinfo->sstop) {
704 * The freemap is not used below allocator_beg or beyond
708 if (data_off < cbinfo->hmp->voldata.allocator_beg)
710 if (data_off >= cbinfo->hmp->voldata.volu_size)
714 * Locate the freemap leaf on the live filesystem
716 key = (data_off & ~HAMMER2_FREEMAP_LEVEL1_MASK);
718 if (live_chain == NULL || live_chain->bref.key != key) {
720 hammer2_chain_unlock(live_chain);
721 hammer2_chain_drop(live_chain);
723 live_chain = hammer2_chain_lookup(
727 key + HAMMER2_FREEMAP_LEVEL1_MASK,
729 HAMMER2_LOOKUP_ALWAYS);
733 * If recent allocations were made we avoid races by
734 * not staging or freeing any blocks. We can still
735 * remark blocks as fully allocated.
738 if (hammer2_debug & 1) {
739 kprintf("live_chain %016jx\n",
742 if (live_chain->bref.mirror_tid >
743 cbinfo->saved_mirror_tid) {
744 kprintf("hammer2_bulkfree: "
754 if (live_chain == NULL) {
756 * XXX if we implement a full recovery mode we need
757 * to create/recreate missing freemap chains if our
758 * bmap has any allocated blocks.
761 bmap->avail != HAMMER2_FREEMAP_LEVEL0_SIZE) {
762 kprintf("hammer2_bulkfree: cannot locate "
763 "live leaf for allocated data "
769 if (live_chain->error) {
770 kprintf("hammer2_bulkfree: error %s looking up "
771 "live leaf for allocated data near %016jx\n",
772 hammer2_error_str(live_chain->error),
774 hammer2_chain_unlock(live_chain);
775 hammer2_chain_drop(live_chain);
780 bmapindex = (data_off & HAMMER2_FREEMAP_LEVEL1_MASK) >>
781 HAMMER2_FREEMAP_LEVEL0_RADIX;
782 live = &live_chain->data->bmdata[bmapindex];
785 * Shortcut if the bitmaps match and the live linear
786 * indicator is sane. We can't do a perfect check of
787 * live->linear because the only real requirement is that
788 * if it is not block-aligned, that it not cover the space
789 * within its current block which overlaps one of the data
790 * ranges we scan. We don't retain enough fine-grained
791 * data in our scan to be able to set it exactly.
793 * TODO - we could shortcut this by testing that both
794 * live->class and bmap->class are 0, and both avails are
795 * set to HAMMER2_FREEMAP_LEVEL0_SIZE (4MB).
797 if (bcmp(live->bitmapq, bmap->bitmapq,
798 sizeof(bmap->bitmapq)) == 0 &&
799 live->linear >= bmap->linear) {
802 if (hammer2_debug & 1) {
803 kprintf("live %016jx %04d.%04x (avail=%d)\n",
804 data_off, bmapindex, live->class, live->avail);
807 hammer2_chain_modify(live_chain, cbinfo->mtid, 0, 0);
808 live = &live_chain->data->bmdata[bmapindex];
810 h2_bulkfree_sync_adjust(cbinfo, data_off, live, bmap,
811 live_chain->bref.key +
813 HAMMER2_FREEMAP_LEVEL0_SIZE);
815 data_off += HAMMER2_FREEMAP_LEVEL0_SIZE;
819 hammer2_chain_unlock(live_chain);
820 hammer2_chain_drop(live_chain);
823 hammer2_chain_unlock(live_parent);
824 hammer2_chain_drop(live_parent);
829 * Merge the bulkfree bitmap against the existing bitmap.
833 h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
834 hammer2_off_t data_off, hammer2_bmap_data_t *live,
835 hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base)
839 hammer2_off_t tmp_off;
840 hammer2_bitmap_t lmask;
841 hammer2_bitmap_t mmask;
845 for (bindex = 0; bindex < HAMMER2_BMAP_ELEMENTS; ++bindex) {
846 lmask = live->bitmapq[bindex]; /* live */
847 mmask = bmap->bitmapq[bindex]; /* snapshotted bulkfree */
848 if (lmask == mmask) {
849 tmp_off += HAMMER2_BMAP_INDEX_SIZE;
854 scount < HAMMER2_BMAP_BITS_PER_ELEMENT;
856 if ((mmask & 3) == 0) {
858 * in-memory 00 live 11 -> 10
861 * Storage might be marked allocated or
862 * staged and must be remarked staged or
869 kprintf("hammer2_bulkfree: cannot "
870 "transition m=00/l=01\n");
872 case 2: /* 10 -> 00 */
873 live->bitmapq[bindex] &=
874 ~((hammer2_bitmap_t)2 << scount);
876 HAMMER2_FREEMAP_BLOCK_SIZE;
878 HAMMER2_FREEMAP_LEVEL0_SIZE) {
880 HAMMER2_FREEMAP_LEVEL0_SIZE;
883 HAMMER2_FREEMAP_BLOCK_SIZE;
884 ++cbinfo->count_10_00;
885 hammer2_io_dedup_assert(
888 HAMMER2_FREEMAP_BLOCK_RADIX,
889 HAMMER2_FREEMAP_BLOCK_SIZE);
891 case 3: /* 11 -> 10 */
892 live->bitmapq[bindex] &=
893 ~((hammer2_bitmap_t)1 << scount);
894 ++cbinfo->count_11_10;
895 hammer2_io_dedup_delete(
897 HAMMER2_BREF_TYPE_DATA,
899 HAMMER2_FREEMAP_BLOCK_RADIX,
900 HAMMER2_FREEMAP_BLOCK_SIZE);
903 } else if ((mmask & 3) == 3) {
905 * in-memory 11 live 10 -> 11
908 * Storage might be incorrectly marked free
909 * or staged and must be remarked fully
914 ++cbinfo->count_00_11;
916 HAMMER2_FREEMAP_BLOCK_SIZE;
918 HAMMER2_FREEMAP_BLOCK_SIZE;
919 if ((int32_t)live->avail < 0)
923 ++cbinfo->count_01_11;
925 case 2: /* 10 -> 11 */
926 ++cbinfo->count_10_11;
931 live->bitmapq[bindex] |=
932 ((hammer2_bitmap_t)3 << scount);
936 tmp_off += HAMMER2_FREEMAP_BLOCK_SIZE;
941 * Determine if the live bitmap is completely free and reset its
942 * fields if so. Otherwise check to see if we can reduce the linear
945 for (bindex = HAMMER2_BMAP_ELEMENTS - 1; bindex >= 0; --bindex) {
946 if (live->bitmapq[bindex] != 0)
951 * Completely empty, reset entire segment
954 kprintf("hammer2: cleanseg %016jx.%04x (%d)\n",
955 alloc_base, live->class, live->avail);
957 live->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
960 ++cbinfo->count_l0cleans;
961 } else if (bindex < 7) {
963 * Partially full, bitmapq[bindex] != 0. The live->linear
964 * offset can legitimately be just about anything, but
965 * our bulkfree pass doesn't record enough information to
966 * set it exactly. Just make sure that it is set to a
967 * safe value that also works in our match code above (the
968 * bcmp and linear test).
970 * We cannot safely leave live->linear at a sub-block offset
971 * unless it is already in the same block as bmap->linear.
973 * If it is not in the same block, we cannot assume that
974 * we can set it to bmap->linear on a sub-block boundary,
975 * because the live system could have bounced it around.
976 * In that situation we satisfy our bcmp/skip requirement
977 * above by setting it to the nearest higher block boundary.
978 * This alignment effectively kills any partial allocation it
979 * might have been tracking before.
981 if (live->linear < bmap->linear &&
982 ((live->linear ^ bmap->linear) &
983 ~HAMMER2_FREEMAP_BLOCK_MASK) == 0) {
984 live->linear = bmap->linear;
985 ++cbinfo->count_linadjusts;
988 (bmap->linear + HAMMER2_FREEMAP_BLOCK_MASK) &
989 ~HAMMER2_FREEMAP_BLOCK_MASK;
990 ++cbinfo->count_linadjusts;
994 * Completely full, effectively disable the linear iterator
996 live->linear = HAMMER2_SEGSIZE;
1001 kprintf("%016jx %04d.%04x (avail=%7d) "
1002 "%08x %08x %08x %08x %08x %08x %08x %08x\n",
1005 HAMMER2_FREEMAP_LEVEL1_MASK) >>
1006 HAMMER2_FREEMAP_LEVEL0_RADIX),
1009 bmap->bitmap[0], bmap->bitmap[1],
1010 bmap->bitmap[2], bmap->bitmap[3],
1011 bmap->bitmap[4], bmap->bitmap[5],
1012 bmap->bitmap[6], bmap->bitmap[7]);
1018 * BULKFREE DEDUP HEURISTIC
1020 * WARNING! This code is SMP safe but the heuristic allows SMP collisions.
1021 * All fields must be loaded into locals and validated.
1025 h2_bulkfree_test(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref,
1028 hammer2_dedup_t *dedup;
1033 n = hammer2_icrc32(&bref->data_off, sizeof(bref->data_off));
1034 dedup = cbinfo->dedup + (n & (HAMMER2_DEDUP_HEUR_MASK & ~7));
1036 for (i = best = 0; i < 8; ++i) {
1037 if (dedup[i].data_off == bref->data_off) {
1038 if (dedup[i].ticks < pri)
1039 dedup[i].ticks = pri;
1041 cbinfo->count_dedup_factor += dedup[i].ticks;
1044 if (dedup[i].ticks < dedup[best].ticks)
1047 dedup[best].data_off = bref->data_off;
1048 dedup[best].ticks = pri;