2 * Copyright (c) 2013-2018 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>
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
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))
59 * breadth-first search
61 typedef struct hammer2_chain_save
{
62 TAILQ_ENTRY(hammer2_chain_save
) entry
;
63 hammer2_chain_t
*chain
;
65 } hammer2_chain_save_t
;
67 TAILQ_HEAD(hammer2_chain_save_list
, hammer2_chain_save
);
68 typedef struct hammer2_chain_save_list hammer2_chain_save_list_t
;
70 typedef struct hammer2_bulkfree_info
{
73 hammer2_off_t sbase
; /* sub-loop iteration */
75 hammer2_bmap_data_t
*bmap
;
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 */
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
;
92 hammer2_off_t adj_free
;
94 hammer2_tid_t saved_mirror_tid
;
96 hammer2_chain_save_list_t list
;
97 hammer2_dedup_t
*dedup
;
99 } hammer2_bulkfree_info_t
;
101 static int h2_bulkfree_test(hammer2_bulkfree_info_t
*info
,
102 hammer2_blockref_t
*bref
, int pri
);
105 * General bulk scan function with callback. Called with a referenced
106 * but UNLOCKED parent. The parent is returned in the same state.
110 hammer2_bulk_scan(hammer2_chain_t
*parent
,
111 int (*func
)(hammer2_bulkfree_info_t
*info
,
112 hammer2_blockref_t
*bref
),
113 hammer2_bulkfree_info_t
*info
)
115 hammer2_blockref_t bref
;
116 hammer2_chain_t
*chain
;
123 hammer2_chain_lock(parent
, HAMMER2_RESOLVE_ALWAYS
|
124 HAMMER2_RESOLVE_SHARED
);
130 * Generally loop on the contents if we have not been flagged
133 * Remember that these chains are completely isolated from
134 * the frontend, so we can release locks temporarily without
138 error
|= hammer2_chain_scan(parent
, &chain
, &bref
, &first
,
139 HAMMER2_LOOKUP_NODATA
|
140 HAMMER2_LOOKUP_SHARED
);
143 * Handle EOF or other error at current level. This stops
150 * Account for dirents before thre data_off test, since most
151 * dirents do not need a data reference.
153 if (bref
.type
== HAMMER2_BREF_TYPE_DIRENT
)
154 ++info
->count_dirents_scanned
;
157 * Ignore brefs without data (typically dirents)
159 if ((bref
.data_off
& ~HAMMER2_OFF_MASK_RADIX
) == 0)
163 * Process bref, chain is only non-NULL if the bref
164 * might be recursable (its possible that we sometimes get
165 * a non-NULL chain where the bref cannot be recursed).
168 if (h2_bulkfree_test(info
, &bref
, 1))
171 if (bref
.type
== HAMMER2_BREF_TYPE_INODE
)
172 ++info
->count_inodes_scanned
;
174 error
|= func(info
, &bref
);
179 * A non-null chain is always returned if it is
180 * recursive, otherwise a non-null chain might be
181 * returned but usually is not when not recursive.
187 info
->count_bytes_scanned
+= chain
->bytes
;
188 ++info
->count_chains_scanned
;
190 if (info
->count_chains_scanned
>=
191 info
->count_chains_reported
+ 50000) {
192 kprintf(" chains %-7ld inodes %-7ld "
193 "dirents %-7ld bytes %5ldMB\n",
194 info
->count_chains_scanned
,
195 info
->count_inodes_scanned
,
196 info
->count_dirents_scanned
,
197 info
->count_bytes_scanned
/ 1000000);
198 info
->count_chains_reported
+= 50000;
204 * Else check type and setup depth-first scan.
206 * Account for bytes actually read.
208 switch(chain
->bref
.type
) {
209 case HAMMER2_BREF_TYPE_INODE
:
210 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
211 case HAMMER2_BREF_TYPE_INDIRECT
:
212 case HAMMER2_BREF_TYPE_VOLUME
:
213 case HAMMER2_BREF_TYPE_FREEMAP
:
215 if (info
->depth
> 16) {
216 hammer2_chain_save_t
*save
;
217 save
= kmalloc(sizeof(*save
), M_HAMMER2
,
220 hammer2_chain_ref(chain
);
221 TAILQ_INSERT_TAIL(&info
->list
, save
, entry
);
226 int savepri
= info
->pri
;
228 hammer2_chain_unlock(chain
);
229 hammer2_chain_unlock(parent
);
232 hammer2_bulk_scan(chain
, func
, info
);
233 info
->pri
+= savepri
;
234 hammer2_chain_lock(parent
,
235 HAMMER2_RESOLVE_ALWAYS
|
236 HAMMER2_RESOLVE_SHARED
);
237 hammer2_chain_lock(chain
,
238 HAMMER2_RESOLVE_ALWAYS
|
239 HAMMER2_RESOLVE_SHARED
);
243 case HAMMER2_BREF_TYPE_DATA
:
246 /* does not recurse */
249 if (rup_error
& HAMMER2_ERROR_ABORTED
)
253 hammer2_chain_unlock(chain
);
254 hammer2_chain_drop(chain
);
258 * Save with higher pri now that we know what it is.
260 h2_bulkfree_test(info
, &parent
->bref
, info
->pri
+ 1);
262 hammer2_chain_unlock(parent
);
264 return ((error
| rup_error
) & ~HAMMER2_ERROR_EOF
);
271 * Chain flush (partial synchronization) XXX removed
272 * Scan the whole topology - build in-memory freemap (mark 11)
273 * Reconcile the in-memory freemap against the on-disk freemap.
274 * ondisk xx -> ondisk 11 (if allocated)
275 * ondisk 11 -> ondisk 10 (if free in-memory)
276 * ondisk 10 -> ondisk 00 (if free in-memory) - on next pass
279 * The topology scan may have to be performed multiple times to window
280 * freemaps which are too large to fit in kernel memory.
282 * Races are handled using a double-transition (11->10, 10->00). The bulkfree
283 * scan snapshots the volume root's blockset and thus can run concurrent with
284 * normal operations, as long as a full flush is made between each pass to
285 * synchronize any modified chains (otherwise their blocks might be improperly
288 * Temporary memory in multiples of 64KB is required to reconstruct the leaf
289 * hammer2_bmap_data blocks so they can later be compared against the live
290 * freemap. Each 64KB block represents 128 x 16KB x 1024 = ~2 GB of storage.
291 * A 32MB save area thus represents around ~1 TB. The temporary memory
292 * allocated can be specified. If it is not sufficient multiple topology
293 * passes will be made.
297 * Bulkfree callback info
299 static void hammer2_bulkfree_thread(void *arg __unused
);
300 static void cbinfo_bmap_init(hammer2_bulkfree_info_t
*cbinfo
, size_t size
);
301 static int h2_bulkfree_callback(hammer2_bulkfree_info_t
*cbinfo
,
302 hammer2_blockref_t
*bref
);
303 static int h2_bulkfree_sync(hammer2_bulkfree_info_t
*cbinfo
);
304 static void h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t
*cbinfo
,
305 hammer2_off_t data_off
, hammer2_bmap_data_t
*live
,
306 hammer2_bmap_data_t
*bmap
, hammer2_key_t alloc_base
);
309 hammer2_bulkfree_init(hammer2_dev_t
*hmp
)
311 hammer2_thr_create(&hmp
->bfthr
, NULL
, hmp
,
312 hmp
->devrepname
, -1, -1,
313 hammer2_bulkfree_thread
);
317 hammer2_bulkfree_uninit(hammer2_dev_t
*hmp
)
319 hammer2_thr_delete(&hmp
->bfthr
);
323 hammer2_bulkfree_thread(void *arg
)
325 hammer2_thread_t
*thr
= arg
;
326 hammer2_ioc_bulkfree_t bfi
;
330 hammer2_thr_wait_any(thr
,
331 HAMMER2_THREAD_STOP
|
332 HAMMER2_THREAD_FREEZE
|
333 HAMMER2_THREAD_UNFREEZE
|
334 HAMMER2_THREAD_REMASTER
,
339 if (flags
& HAMMER2_THREAD_STOP
)
341 if (flags
& HAMMER2_THREAD_FREEZE
) {
342 hammer2_thr_signal2(thr
, HAMMER2_THREAD_FROZEN
,
343 HAMMER2_THREAD_FREEZE
);
346 if (flags
& HAMMER2_THREAD_UNFREEZE
) {
347 hammer2_thr_signal2(thr
, 0,
348 HAMMER2_THREAD_FROZEN
|
349 HAMMER2_THREAD_UNFREEZE
);
352 if (flags
& HAMMER2_THREAD_FROZEN
)
354 if (flags
& HAMMER2_THREAD_REMASTER
) {
355 hammer2_thr_signal2(thr
, 0, HAMMER2_THREAD_REMASTER
);
356 bzero(&bfi
, sizeof(bfi
));
357 bfi
.size
= 8192 * 1024;
358 /* hammer2_bulkfree_pass(thr->hmp, &bfi); */
362 hammer2_thr_signal(thr
, HAMMER2_THREAD_STOPPED
);
363 /* structure can go invalid at this point */
367 hammer2_bulkfree_pass(hammer2_dev_t
*hmp
, hammer2_chain_t
*vchain
,
368 hammer2_ioc_bulkfree_t
*bfi
)
370 hammer2_bulkfree_info_t cbinfo
;
371 hammer2_chain_save_t
*save
;
377 * We have to clear the live dedup cache as it might have entries
378 * that are freeable as of now. Any new entries in the dedup cache
379 * made after this point, even if they become freeable, will have
380 * previously been fully allocated and will be protected by the
383 hammer2_dedup_clear(hmp
);
386 * Setup for free pass
388 bzero(&cbinfo
, sizeof(cbinfo
));
389 size
= (bfi
->size
+ HAMMER2_FREEMAP_LEVELN_PSIZE
- 1) &
390 ~(size_t)(HAMMER2_FREEMAP_LEVELN_PSIZE
- 1);
391 if (size
< 1024 * 1024)
393 if (size
> 64 * 1024 * 1024)
394 size
= 64 * 1024 * 1024;
397 cbinfo
.bmap
= kmem_alloc_swapbacked(&cbinfo
.kp
, size
, VM_SUBSYS_HAMMER
);
398 cbinfo
.saved_mirror_tid
= hmp
->voldata
.mirror_tid
;
400 cbinfo
.dedup
= kmalloc(sizeof(*cbinfo
.dedup
) * HAMMER2_DEDUP_HEUR_SIZE
,
401 M_HAMMER2
, M_WAITOK
| M_ZERO
);
404 * Normalize start point to a 2GB boundary. We operate on a
405 * 64KB leaf bitmap boundary which represents 2GB of storage.
407 cbinfo
.sbase
= bfi
->sbase
;
408 if (cbinfo
.sbase
> hmp
->voldata
.volu_size
)
409 cbinfo
.sbase
= hmp
->voldata
.volu_size
;
410 cbinfo
.sbase
&= ~HAMMER2_FREEMAP_LEVEL1_MASK
;
411 TAILQ_INIT(&cbinfo
.list
);
413 cbinfo
.bulkfree_ticks
= ticks
;
416 * Loop on a full meta-data scan as many times as required to
417 * get through all available storage.
420 while (cbinfo
.sbase
< hmp
->voldata
.volu_size
) {
422 * We have enough ram to represent (incr) bytes of storage.
423 * Each 64KB of ram represents 2GB of storage.
425 * We must also clean out our de-duplication heuristic for
426 * each (incr) bytes of storage, otherwise we wind up not
427 * scanning meta-data for later areas of storage because
428 * they had already been scanned in earlier areas of storage.
429 * Since the ranging is different, we have to restart
430 * the dedup heuristic too.
432 cbinfo_bmap_init(&cbinfo
, size
);
433 bzero(cbinfo
.dedup
, sizeof(*cbinfo
.dedup
) *
434 HAMMER2_DEDUP_HEUR_SIZE
);
435 cbinfo
.count_inodes_scanned
= 0;
436 cbinfo
.count_dirents_scanned
= 0;
437 cbinfo
.count_bytes_scanned
= 0;
438 cbinfo
.count_chains_scanned
= 0;
439 cbinfo
.count_chains_reported
= 0;
441 incr
= size
/ HAMMER2_FREEMAP_LEVELN_PSIZE
*
442 HAMMER2_FREEMAP_LEVEL1_SIZE
;
443 if (hmp
->voldata
.volu_size
- cbinfo
.sbase
< incr
)
444 cbinfo
.sstop
= hmp
->voldata
.volu_size
;
446 cbinfo
.sstop
= cbinfo
.sbase
+ incr
;
447 if (hammer2_debug
& 1) {
448 kprintf("bulkfree pass %016jx/%jdGB\n",
449 (intmax_t)cbinfo
.sbase
,
450 (intmax_t)incr
/ HAMMER2_FREEMAP_LEVEL1_SIZE
);
454 * Scan topology for stuff inside this range.
456 * NOTE - By not using a transaction the operation can
457 * run concurrent with the frontend as well as
460 * We cannot safely set a mtid without a transaction,
461 * and in fact we don't want to set one anyway. We
462 * want the bulkfree to be passive and no interfere
463 * with crash recovery.
465 #undef HAMMER2_BULKFREE_TRANS /* undef - don't use transaction */
466 #ifdef HAMMER2_BULKFREE_TRANS
467 hammer2_trans_init(hmp
->spmp
, 0);
468 cbinfo
.mtid
= hammer2_trans_sub(hmp
->spmp
);
473 error
|= hammer2_bulk_scan(vchain
, h2_bulkfree_callback
,
476 while ((save
= TAILQ_FIRST(&cbinfo
.list
)) != NULL
&&
478 TAILQ_REMOVE(&cbinfo
.list
, save
, entry
);
480 error
|= hammer2_bulk_scan(save
->chain
,
481 h2_bulkfree_callback
,
483 hammer2_chain_drop(save
->chain
);
484 kfree(save
, M_HAMMER2
);
487 TAILQ_REMOVE(&cbinfo
.list
, save
, entry
);
488 hammer2_chain_drop(save
->chain
);
489 kfree(save
, M_HAMMER2
);
490 save
= TAILQ_FIRST(&cbinfo
.list
);
493 kprintf("bulkfree lastdrop %d %d error=0x%04x\n",
494 vchain
->refs
, vchain
->core
.chain_count
, error
);
497 * If the complete scan succeeded we can synchronize our
498 * in-memory freemap against live storage. If an abort
499 * occured we cannot safely synchronize our partially
500 * filled-out in-memory freemap.
503 error
= h2_bulkfree_sync(&cbinfo
);
505 hammer2_voldata_lock(hmp
);
506 hammer2_voldata_modify(hmp
);
507 hmp
->voldata
.allocator_free
+= cbinfo
.adj_free
;
508 hammer2_voldata_unlock(hmp
);
512 * Cleanup for next loop.
514 #ifdef HAMMER2_BULKFREE_TRANS
515 hammer2_trans_done(hmp
->spmp
);
519 cbinfo
.sbase
= cbinfo
.sstop
;
522 kmem_free_swapbacked(&cbinfo
.kp
);
523 kfree(cbinfo
.dedup
, M_HAMMER2
);
526 bfi
->sstop
= cbinfo
.sbase
;
528 incr
= bfi
->sstop
/ (hmp
->voldata
.volu_size
/ 10000);
532 kprintf("bulkfree pass statistics (%d.%02d%% storage processed):\n",
537 kprintf(" bulkfree was aborted\n");
539 kprintf(" transition->free %ld\n", cbinfo
.count_10_00
);
540 kprintf(" transition->staged %ld\n", cbinfo
.count_11_10
);
541 kprintf(" ERR(00)->allocated %ld\n", cbinfo
.count_00_11
);
542 kprintf(" ERR(01)->allocated %ld\n", cbinfo
.count_01_11
);
543 kprintf(" staged->allocated %ld\n", cbinfo
.count_10_11
);
544 kprintf(" ~2MB segs cleaned %ld\n", cbinfo
.count_l0cleans
);
545 kprintf(" linear adjusts %ld\n",
546 cbinfo
.count_linadjusts
);
547 kprintf(" dedup factor %ld\n",
548 cbinfo
.count_dedup_factor
);
555 cbinfo_bmap_init(hammer2_bulkfree_info_t
*cbinfo
, size_t size
)
557 hammer2_bmap_data_t
*bmap
= cbinfo
->bmap
;
558 hammer2_key_t key
= cbinfo
->sbase
;
562 lokey
= (cbinfo
->hmp
->voldata
.allocator_beg
+ HAMMER2_SEGMASK64
) &
564 hikey
= cbinfo
->hmp
->voldata
.volu_size
& ~HAMMER2_SEGMASK64
;
568 bzero(bmap
, sizeof(*bmap
));
569 if (lokey
< H2FMBASE(key
, HAMMER2_FREEMAP_LEVEL1_RADIX
))
570 lokey
= H2FMBASE(key
, HAMMER2_FREEMAP_LEVEL1_RADIX
);
571 if (lokey
< H2FMZONEBASE(key
) + HAMMER2_ZONE_SEG64
)
572 lokey
= H2FMZONEBASE(key
) + HAMMER2_ZONE_SEG64
;
573 if (key
< lokey
|| key
>= hikey
) {
574 memset(bmap
->bitmapq
, -1,
575 sizeof(bmap
->bitmapq
));
577 bmap
->linear
= HAMMER2_SEGSIZE
;
579 bmap
->avail
= H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX
);
581 size
-= sizeof(*bmap
);
582 key
+= HAMMER2_FREEMAP_LEVEL0_SIZE
;
588 h2_bulkfree_callback(hammer2_bulkfree_info_t
*cbinfo
, hammer2_blockref_t
*bref
)
590 hammer2_bmap_data_t
*bmap
;
591 hammer2_off_t data_off
;
597 * Check for signal and allow yield to userland during scan.
599 if (hammer2_signal_check(&cbinfo
->save_time
))
600 return HAMMER2_ERROR_ABORTED
;
603 * Deal with kernel thread cpu or I/O hogging by limiting the
604 * number of chains scanned per second to hammer2_bulkfree_tps.
605 * Ignore leaf records (DIRENT and DATA), no per-record I/O is
606 * involved for those since we don't load their data.
608 if (bref
->type
!= HAMMER2_BREF_TYPE_DATA
&&
609 bref
->type
!= HAMMER2_BREF_TYPE_DIRENT
) {
610 ++cbinfo
->bulkfree_calls
;
611 if (cbinfo
->bulkfree_calls
> hammer2_bulkfree_tps
) {
612 int dticks
= ticks
- cbinfo
->bulkfree_ticks
;
616 tsleep(&cbinfo
->bulkfree_ticks
, 0,
617 "h2bw", hz
- dticks
);
619 cbinfo
->bulkfree_calls
= 0;
620 cbinfo
->bulkfree_ticks
= ticks
;
625 * Calculate the data offset and determine if it is within
626 * the current freemap range being gathered.
628 data_off
= bref
->data_off
& ~HAMMER2_OFF_MASK_RADIX
;
629 if (data_off
< cbinfo
->sbase
|| data_off
>= cbinfo
->sstop
)
631 if (data_off
< cbinfo
->hmp
->voldata
.allocator_beg
)
633 if (data_off
>= cbinfo
->hmp
->voldata
.volu_size
)
637 * Calculate the information needed to generate the in-memory
640 * Hammer2 does not allow allocations to cross the L1 (2GB) boundary,
641 * it's a problem if it does. (Or L0 (2MB) for that matter).
643 radix
= (int)(bref
->data_off
& HAMMER2_OFF_MASK_RADIX
);
644 KKASSERT(radix
!= 0);
645 bytes
= (size_t)1 << radix
;
646 class = (bref
->type
<< 8) | hammer2_devblkradix(radix
);
648 if (data_off
+ bytes
> cbinfo
->sstop
) {
649 kprintf("hammer2_bulkfree_scan: illegal 2GB boundary "
650 "%016jx %016jx/%d\n",
651 (intmax_t)bref
->data_off
,
654 bytes
= cbinfo
->sstop
- data_off
; /* XXX */
658 * Convert to a storage offset relative to the beginning of the
659 * storage range we are collecting. Then lookup the level0 bmap entry.
661 data_off
-= cbinfo
->sbase
;
662 bmap
= cbinfo
->bmap
+ (data_off
>> HAMMER2_FREEMAP_LEVEL0_RADIX
);
665 * Convert data_off to a bmap-relative value (~4MB storage range).
666 * Adjust linear, class, and avail.
668 * Hammer2 does not allow allocations to cross the L0 (4MB) boundary,
670 data_off
&= HAMMER2_FREEMAP_LEVEL0_MASK
;
671 if (data_off
+ bytes
> HAMMER2_FREEMAP_LEVEL0_SIZE
) {
672 kprintf("hammer2_bulkfree_scan: illegal 4MB boundary "
673 "%016jx %016jx/%d\n",
674 (intmax_t)bref
->data_off
,
677 bytes
= HAMMER2_FREEMAP_LEVEL0_SIZE
- data_off
;
680 if (bmap
->class == 0) {
682 bmap
->avail
= HAMMER2_FREEMAP_LEVEL0_SIZE
;
686 * NOTE: bmap->class does not have to match class. Classification
687 * is relaxed when free space is low, so some mixing can occur.
693 if (bmap
->class != class) {
694 kprintf("hammer2_bulkfree_scan: illegal mixed class "
695 "%016jx %016jx/%d (%04x vs %04x)\n",
696 (intmax_t)bref
->data_off
,
704 * Just record the highest byte-granular offset for now. Do not
705 * match against allocations which are in multiples of whole blocks.
707 * Make sure that any in-block linear offset at least covers the
708 * data range. This can cause bmap->linear to become block-aligned.
710 if (bytes
& HAMMER2_FREEMAP_BLOCK_MASK
) {
711 if (bmap
->linear
< (int32_t)data_off
+ (int32_t)bytes
)
712 bmap
->linear
= (int32_t)data_off
+ (int32_t)bytes
;
713 } else if (bmap
->linear
>= (int32_t)data_off
&&
714 bmap
->linear
< (int32_t)data_off
+ (int32_t)bytes
) {
715 bmap
->linear
= (int32_t)data_off
+ (int32_t)bytes
;
719 * Adjust the hammer2_bitmap_t bitmap[HAMMER2_BMAP_ELEMENTS].
720 * 64-bit entries, 2 bits per entry, to code 11.
722 * NOTE: data_off mask to 524288, shift right by 14 (radix for 16384),
723 * and multiply shift amount by 2 for sets of 2 bits.
725 * NOTE: The allocation can be smaller than HAMMER2_FREEMAP_BLOCK_SIZE.
726 * also, data_off may not be FREEMAP_BLOCK_SIZE aligned.
729 hammer2_bitmap_t bmask
;
732 bindex
= (int)data_off
>> (HAMMER2_FREEMAP_BLOCK_RADIX
+
733 HAMMER2_BMAP_INDEX_RADIX
);
734 bmask
= (hammer2_bitmap_t
)3 <<
735 ((((int)data_off
& HAMMER2_BMAP_INDEX_MASK
) >>
736 HAMMER2_FREEMAP_BLOCK_RADIX
) << 1);
739 * NOTE! The (avail) calculation is bitmap-granular. Multiple
740 * sub-granular records can wind up at the same bitmap
743 if ((bmap
->bitmapq
[bindex
] & bmask
) == 0) {
744 if (bytes
< HAMMER2_FREEMAP_BLOCK_SIZE
) {
745 bmap
->avail
-= HAMMER2_FREEMAP_BLOCK_SIZE
;
747 bmap
->avail
-= bytes
;
749 bmap
->bitmapq
[bindex
] |= bmask
;
751 data_off
+= HAMMER2_FREEMAP_BLOCK_SIZE
;
752 if (bytes
< HAMMER2_FREEMAP_BLOCK_SIZE
)
755 bytes
-= HAMMER2_FREEMAP_BLOCK_SIZE
;
761 * Synchronize the in-memory bitmap with the live freemap. This is not a
762 * direct copy. Instead the bitmaps must be compared:
764 * In-memory Live-freemap
765 * 00 11 -> 10 (do nothing if live modified)
766 * 10 -> 00 (do nothing if live modified)
767 * 11 10 -> 11 handles race against live
768 * ** -> 11 nominally warn of corruption
770 * We must also fixup the hints in HAMMER2_BREF_TYPE_FREEMAP_LEAF.
773 h2_bulkfree_sync(hammer2_bulkfree_info_t
*cbinfo
)
775 hammer2_off_t data_off
;
777 hammer2_key_t key_dummy
;
778 hammer2_bmap_data_t
*bmap
;
779 hammer2_bmap_data_t
*live
;
780 hammer2_chain_t
*live_parent
;
781 hammer2_chain_t
*live_chain
;
785 kprintf("hammer2_bulkfree - range ");
787 if (cbinfo
->sbase
< cbinfo
->hmp
->voldata
.allocator_beg
)
789 (intmax_t)cbinfo
->hmp
->voldata
.allocator_beg
);
792 (intmax_t)cbinfo
->sbase
);
794 if (cbinfo
->sstop
> cbinfo
->hmp
->voldata
.volu_size
)
796 (intmax_t)cbinfo
->hmp
->voldata
.volu_size
);
799 (intmax_t)cbinfo
->sstop
);
801 data_off
= cbinfo
->sbase
;
804 live_parent
= &cbinfo
->hmp
->fchain
;
805 hammer2_chain_ref(live_parent
);
806 hammer2_chain_lock(live_parent
, HAMMER2_RESOLVE_ALWAYS
);
811 * Iterate each hammer2_bmap_data_t line (128 bytes) managing
814 while (data_off
< cbinfo
->sstop
) {
816 * The freemap is not used below allocator_beg or beyond
820 if (data_off
< cbinfo
->hmp
->voldata
.allocator_beg
)
822 if (data_off
>= cbinfo
->hmp
->voldata
.volu_size
)
826 * Locate the freemap leaf on the live filesystem
828 key
= (data_off
& ~HAMMER2_FREEMAP_LEVEL1_MASK
);
830 if (live_chain
== NULL
|| live_chain
->bref
.key
!= key
) {
832 hammer2_chain_unlock(live_chain
);
833 hammer2_chain_drop(live_chain
);
835 live_chain
= hammer2_chain_lookup(
839 key
+ HAMMER2_FREEMAP_LEVEL1_MASK
,
841 HAMMER2_LOOKUP_ALWAYS
);
843 kprintf("hammer2_bulkfree: freemap lookup "
844 "error near %016jx, error %s\n",
846 hammer2_error_str(live_chain
->error
));
850 if (live_chain
== NULL
) {
852 * XXX if we implement a full recovery mode we need
853 * to create/recreate missing freemap chains if our
854 * bmap has any allocated blocks.
857 bmap
->avail
!= HAMMER2_FREEMAP_LEVEL0_SIZE
) {
858 kprintf("hammer2_bulkfree: cannot locate "
859 "live leaf for allocated data "
865 if (live_chain
->error
) {
866 kprintf("hammer2_bulkfree: unable to access freemap "
867 "near %016jx, error %s\n",
869 hammer2_error_str(live_chain
->error
));
870 hammer2_chain_unlock(live_chain
);
871 hammer2_chain_drop(live_chain
);
876 bmapindex
= (data_off
& HAMMER2_FREEMAP_LEVEL1_MASK
) >>
877 HAMMER2_FREEMAP_LEVEL0_RADIX
;
878 live
= &live_chain
->data
->bmdata
[bmapindex
];
881 * Shortcut if the bitmaps match and the live linear
882 * indicator is sane. We can't do a perfect check of
883 * live->linear because the only real requirement is that
884 * if it is not block-aligned, that it not cover the space
885 * within its current block which overlaps one of the data
886 * ranges we scan. We don't retain enough fine-grained
887 * data in our scan to be able to set it exactly.
889 * TODO - we could shortcut this by testing that both
890 * live->class and bmap->class are 0, and both avails are
891 * set to HAMMER2_FREEMAP_LEVEL0_SIZE (4MB).
893 if (bcmp(live
->bitmapq
, bmap
->bitmapq
,
894 sizeof(bmap
->bitmapq
)) == 0 &&
895 live
->linear
>= bmap
->linear
) {
898 if (hammer2_debug
& 1) {
899 kprintf("live %016jx %04d.%04x (avail=%d)\n",
900 data_off
, bmapindex
, live
->class, live
->avail
);
903 hammer2_chain_modify(live_chain
, cbinfo
->mtid
, 0, 0);
904 live_chain
->bref
.check
.freemap
.bigmask
= -1;
905 cbinfo
->hmp
->freemap_relaxed
= 0; /* reset heuristic */
906 live
= &live_chain
->data
->bmdata
[bmapindex
];
908 h2_bulkfree_sync_adjust(cbinfo
, data_off
, live
, bmap
,
909 live_chain
->bref
.key
+
911 HAMMER2_FREEMAP_LEVEL0_SIZE
);
913 data_off
+= HAMMER2_FREEMAP_LEVEL0_SIZE
;
917 hammer2_chain_unlock(live_chain
);
918 hammer2_chain_drop(live_chain
);
921 hammer2_chain_unlock(live_parent
);
922 hammer2_chain_drop(live_parent
);
928 * Merge the bulkfree bitmap against the existing bitmap.
932 h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t
*cbinfo
,
933 hammer2_off_t data_off
, hammer2_bmap_data_t
*live
,
934 hammer2_bmap_data_t
*bmap
, hammer2_key_t alloc_base
)
938 hammer2_off_t tmp_off
;
939 hammer2_bitmap_t lmask
;
940 hammer2_bitmap_t mmask
;
944 for (bindex
= 0; bindex
< HAMMER2_BMAP_ELEMENTS
; ++bindex
) {
945 lmask
= live
->bitmapq
[bindex
]; /* live */
946 mmask
= bmap
->bitmapq
[bindex
]; /* snapshotted bulkfree */
947 if (lmask
== mmask
) {
948 tmp_off
+= HAMMER2_BMAP_INDEX_SIZE
;
953 scount
< HAMMER2_BMAP_BITS_PER_ELEMENT
;
955 if ((mmask
& 3) == 0) {
957 * in-memory 00 live 11 -> 10
960 * Storage might be marked allocated or
961 * staged and must be remarked staged or
968 kprintf("hammer2_bulkfree: cannot "
969 "transition m=00/l=01\n");
971 case 2: /* 10 -> 00 */
972 live
->bitmapq
[bindex
] &=
973 ~((hammer2_bitmap_t
)2 << scount
);
975 HAMMER2_FREEMAP_BLOCK_SIZE
;
977 HAMMER2_FREEMAP_LEVEL0_SIZE
) {
979 HAMMER2_FREEMAP_LEVEL0_SIZE
;
982 HAMMER2_FREEMAP_BLOCK_SIZE
;
983 ++cbinfo
->count_10_00
;
984 hammer2_io_dedup_assert(
987 HAMMER2_FREEMAP_BLOCK_RADIX
,
988 HAMMER2_FREEMAP_BLOCK_SIZE
);
990 case 3: /* 11 -> 10 */
991 live
->bitmapq
[bindex
] &=
992 ~((hammer2_bitmap_t
)1 << scount
);
993 ++cbinfo
->count_11_10
;
994 hammer2_io_dedup_delete(
996 HAMMER2_BREF_TYPE_DATA
,
998 HAMMER2_FREEMAP_BLOCK_RADIX
,
999 HAMMER2_FREEMAP_BLOCK_SIZE
);
1002 } else if ((mmask
& 3) == 3) {
1004 * in-memory 11 live 10 -> 11
1007 * Storage might be incorrectly marked free
1008 * or staged and must be remarked fully
1011 switch (lmask
& 3) {
1013 ++cbinfo
->count_00_11
;
1015 HAMMER2_FREEMAP_BLOCK_SIZE
;
1017 HAMMER2_FREEMAP_BLOCK_SIZE
;
1018 if ((int32_t)live
->avail
< 0)
1022 ++cbinfo
->count_01_11
;
1024 case 2: /* 10 -> 11 */
1025 ++cbinfo
->count_10_11
;
1030 live
->bitmapq
[bindex
] |=
1031 ((hammer2_bitmap_t
)3 << scount
);
1035 tmp_off
+= HAMMER2_FREEMAP_BLOCK_SIZE
;
1040 * Determine if the live bitmap is completely free and reset its
1041 * fields if so. Otherwise check to see if we can reduce the linear
1044 for (bindex
= HAMMER2_BMAP_ELEMENTS
- 1; bindex
>= 0; --bindex
) {
1045 if (live
->bitmapq
[bindex
] != 0)
1050 * Completely empty, reset entire segment
1053 kprintf("hammer2: cleanseg %016jx.%04x (%d)\n",
1054 alloc_base
, live
->class, live
->avail
);
1056 live
->avail
= HAMMER2_FREEMAP_LEVEL0_SIZE
;
1059 ++cbinfo
->count_l0cleans
;
1060 } else if (bindex
< 7) {
1062 * Partially full, bitmapq[bindex] != 0. The live->linear
1063 * offset can legitimately be just about anything, but
1064 * our bulkfree pass doesn't record enough information to
1065 * set it exactly. Just make sure that it is set to a
1066 * safe value that also works in our match code above (the
1067 * bcmp and linear test).
1069 * We cannot safely leave live->linear at a sub-block offset
1070 * unless it is already in the same block as bmap->linear.
1072 * If it is not in the same block, we cannot assume that
1073 * we can set it to bmap->linear on a sub-block boundary,
1074 * because the live system could have bounced it around.
1075 * In that situation we satisfy our bcmp/skip requirement
1076 * above by setting it to the nearest higher block boundary.
1077 * This alignment effectively kills any partial allocation it
1078 * might have been tracking before.
1080 if (live
->linear
< bmap
->linear
&&
1081 ((live
->linear
^ bmap
->linear
) &
1082 ~HAMMER2_FREEMAP_BLOCK_MASK
) == 0) {
1083 live
->linear
= bmap
->linear
;
1084 ++cbinfo
->count_linadjusts
;
1087 (bmap
->linear
+ HAMMER2_FREEMAP_BLOCK_MASK
) &
1088 ~HAMMER2_FREEMAP_BLOCK_MASK
;
1089 ++cbinfo
->count_linadjusts
;
1093 * Completely full, effectively disable the linear iterator
1095 live
->linear
= HAMMER2_SEGSIZE
;
1100 kprintf("%016jx %04d.%04x (avail=%7d) "
1101 "%08x %08x %08x %08x %08x %08x %08x %08x\n",
1104 HAMMER2_FREEMAP_LEVEL1_MASK
) >>
1105 HAMMER2_FREEMAP_LEVEL0_RADIX
),
1108 bmap
->bitmap
[0], bmap
->bitmap
[1],
1109 bmap
->bitmap
[2], bmap
->bitmap
[3],
1110 bmap
->bitmap
[4], bmap
->bitmap
[5],
1111 bmap
->bitmap
[6], bmap
->bitmap
[7]);
1117 * BULKFREE DEDUP HEURISTIC
1119 * WARNING! This code is SMP safe but the heuristic allows SMP collisions.
1120 * All fields must be loaded into locals and validated.
1124 h2_bulkfree_test(hammer2_bulkfree_info_t
*cbinfo
, hammer2_blockref_t
*bref
,
1127 hammer2_dedup_t
*dedup
;
1132 n
= hammer2_icrc32(&bref
->data_off
, sizeof(bref
->data_off
));
1133 dedup
= cbinfo
->dedup
+ (n
& (HAMMER2_DEDUP_HEUR_MASK
& ~7));
1135 for (i
= best
= 0; i
< 8; ++i
) {
1136 if (dedup
[i
].data_off
== bref
->data_off
) {
1137 if (dedup
[i
].ticks
< pri
)
1138 dedup
[i
].ticks
= pri
;
1140 cbinfo
->count_dedup_factor
+= dedup
[i
].ticks
;
1143 if (dedup
[i
].ticks
< dedup
[best
].ticks
)
1146 dedup
[best
].data_off
= bref
->data_off
;
1147 dedup
[best
].ticks
= pri
;