1 /*
2 * Copyright (c) 2013-2019 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/proc.h>
38 #include <sys/mount.h>
39 #include <vm/vm_kern.h>
40 #include <vm/vm_extern.h>
41
42 #include "hammer2.h"
43
44 /*
45 * breadth-first search
46 */
47 typedef struct hammer2_chain_save {
48 TAILQ_ENTRY(hammer2_chain_save) entry;
49 hammer2_chain_t *chain;
50 } hammer2_chain_save_t;
51
52 TAILQ_HEAD(hammer2_chain_save_list, hammer2_chain_save);
53 typedef struct hammer2_chain_save_list hammer2_chain_save_list_t;
54
55 typedef struct hammer2_bulkfree_info {
56 hammer2_dev_t *hmp;
57 kmem_anon_desc_t kp;
58 hammer2_off_t sbase; /* sub-loop iteration */
59 hammer2_off_t sstop;
60 hammer2_bmap_data_t *bmap;
61 int depth;
62 long count_10_00; /* staged->free */
63 long count_11_10; /* allocated->staged */
64 long count_00_11; /* (should not happen) */
65 long count_01_11; /* (should not happen) */
66 long count_10_11; /* staged->allocated */
67 long count_l0cleans;
68 long count_linadjusts;
69 long count_inodes_scanned;
70 long count_dirents_scanned;
71 long count_dedup_factor;
72 long count_bytes_scanned;
73 long count_chains_scanned;
74 long count_chains_reported;
75 long bulkfree_calls;
76 int bulkfree_ticks;
77 int list_alert;
78 hammer2_off_t adj_free;
79 hammer2_tid_t mtid;
80 time_t save_time;
81 hammer2_chain_save_list_t list;
82 long list_count;
83 long list_count_max;
84 hammer2_chain_save_t *backout; /* ins pt while backing out */
85 hammer2_dedup_t *dedup;
86 int pri;
87 } hammer2_bulkfree_info_t;
88
89 static int h2_bulkfree_test(hammer2_bulkfree_info_t *info,
90 hammer2_blockref_t *bref, int pri, int saved_error);
91 static uint32_t bigmask_get(hammer2_bmap_data_t *bmap);
92 static int bigmask_good(hammer2_bmap_data_t *bmap, uint32_t live_bigmask);
93
94 /*
95 * General bulk scan function with callback. Called with a referenced
96 * but UNLOCKED parent. The parent is returned in the same state.
97 */
98 static
99 int
hammer2_bulkfree_scan(hammer2_chain_t * parent,int (* func)(hammer2_bulkfree_info_t * info,hammer2_blockref_t * bref),hammer2_bulkfree_info_t * info)100 hammer2_bulkfree_scan(hammer2_chain_t *parent,
101 int (*func)(hammer2_bulkfree_info_t *info,
102 hammer2_blockref_t *bref),
103 hammer2_bulkfree_info_t *info)
104 {
105 hammer2_blockref_t bref;
106 hammer2_chain_t *chain;
107 hammer2_chain_save_t *tail;
108 hammer2_chain_save_t *save;
109 int first = 1;
110 int rup_error;
111 int error;
112 int e2;
113
114 ++info->pri;
115
116 chain = NULL;
117 rup_error = 0;
118 error = 0;
119
120 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS |
121 HAMMER2_RESOLVE_SHARED);
122
123 /*
124 * End of scan if parent is a PFS
125 */
126 tail = TAILQ_FIRST(&info->list);
127
128 /*
129 * The parent was previously retrieved NODATA and thus has not
130 * tested the CRC. Now that we have locked it normally, check
131 * for a CRC problem and skip it if we found one. The bulk scan
132 * cannot safely traverse invalid block tables (we could end up
133 * in an endless loop or cause a panic).
134 */
135 if (parent->error & HAMMER2_ERROR_CHECK) {
136 error = parent->error;
137 goto done;
138 }
139
140 /*
141 * Report which PFS is being scanned
142 */
143 if (parent->bref.type == HAMMER2_BREF_TYPE_INODE &&
144 (parent->bref.flags & HAMMER2_BREF_FLAG_PFSROOT)) {
145 kprintf("hammer2_bulkfree: Scanning %s\n",
146 parent->data->ipdata.filename);
147 }
148
149 /*
150 * Generally loop on the contents if we have not been flagged
151 * for abort.
152 *
153 * Remember that these chains are completely isolated from
154 * the frontend, so we can release locks temporarily without
155 * imploding.
156 */
157 for (;;) {
158 error |= hammer2_chain_scan(parent, &chain, &bref, &first,
159 HAMMER2_LOOKUP_NODATA |
160 HAMMER2_LOOKUP_SHARED);
161
162 /*
163 * Handle EOF or other error at current level. This stops
164 * the bulkfree scan.
165 */
166 if (error & ~HAMMER2_ERROR_CHECK)
167 break;
168
169 /*
170 * Account for dirents before thre data_off test, since most
171 * dirents do not need a data reference.
172 */
173 if (bref.type == HAMMER2_BREF_TYPE_DIRENT)
174 ++info->count_dirents_scanned;
175
176 /*
177 * Ignore brefs without data (typically dirents)
178 */
179 if ((bref.data_off & ~HAMMER2_OFF_MASK_RADIX) == 0)
180 continue;
181
182 /*
183 * Process bref, chain is only non-NULL if the bref
184 * might be recursable (its possible that we sometimes get
185 * a non-NULL chain where the bref cannot be recursed).
186 *
187 * If we already ran down this tree we do not have to do it
188 * again, but we must still recover any cumulative error
189 * recorded from the time we did.
190 */
191 ++info->pri;
192 e2 = h2_bulkfree_test(info, &bref, 1, 0);
193 if (e2) {
194 error |= e2 & ~HAMMER2_ERROR_EOF;
195 continue;
196 }
197
198 if (bref.type == HAMMER2_BREF_TYPE_INODE)
199 ++info->count_inodes_scanned;
200
201 error |= func(info, &bref);
202 if (error & ~HAMMER2_ERROR_CHECK)
203 break;
204
205 /*
206 * A non-null chain is always returned if it is
207 * recursive, otherwise a non-null chain might be
208 * returned but usually is not when not recursive.
209 */
210 if (chain == NULL)
211 continue;
212
213 info->count_bytes_scanned += chain->bytes;
214 ++info->count_chains_scanned;
215
216 if (info->count_chains_scanned >=
217 info->count_chains_reported + 1000000 ||
218 (info->count_chains_scanned < 1000000 &&
219 info->count_chains_scanned >=
220 info->count_chains_reported + 100000)) {
221 kprintf(" chains %-7ld inodes %-7ld "
222 "dirents %-7ld bytes %5ldMB\n",
223 info->count_chains_scanned,
224 info->count_inodes_scanned,
225 info->count_dirents_scanned,
226 info->count_bytes_scanned / 1000000);
227 info->count_chains_reported =
228 info->count_chains_scanned;
229 }
230
231 /*
232 * Else check type and setup depth-first scan.
233 *
234 * Account for bytes actually read.
235 */
236 switch(chain->bref.type) {
237 case HAMMER2_BREF_TYPE_INODE:
238 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
239 case HAMMER2_BREF_TYPE_INDIRECT:
240 case HAMMER2_BREF_TYPE_VOLUME:
241 case HAMMER2_BREF_TYPE_FREEMAP:
242 ++info->depth;
243 if (chain->error & HAMMER2_ERROR_CHECK) {
244 /*
245 * Cannot safely recurse chains with crc
246 * errors, even in emergency mode.
247 */
248 /* NOP */
249 } else if (info->depth > 16 ||
250 info->backout ||
251 (info->depth > hammer2_limit_saved_depth &&
252 info->list_count >=
253 (hammer2_limit_saved_chains >> 2)))
254 {
255 /*
256 * We must defer the recursion if it runs
257 * too deep or if too many saved chains are
258 * allocated.
259 *
260 * In the case of too many saved chains, we
261 * have to stop recursing ASAP to avoid an
262 * explosion of memory use since each radix
263 * level can hold 512 elements.
264 *
265 * If we had to defer at a deeper level
266 * backout is non-NULL. We must backout
267 * completely before resuming.
268 */
269 if (info->list_count >
270 hammer2_limit_saved_chains &&
271 info->list_alert == 0)
272 {
273 kprintf("hammer2: during bulkfree, "
274 "saved chains exceeded %ld "
275 "at depth %d, "
276 "backing off to less-efficient "
277 "operation\n",
278 hammer2_limit_saved_chains,
279 info->depth);
280 info->list_alert = 1;
281 }
282
283 /*
284 * Must be placed at head so pfsroot scan
285 * can exhaust saved elements for that pfs
286 * first.
287 *
288 * Must be placed at head for depth-first
289 * recovery when too many saved chains, to
290 * limit number of chains saved during
291 * saved-chain reruns. The worst-case excess
292 * is (maximum_depth * 512) saved chains above
293 * the threshold.
294 *
295 * The maximum_depth generally occurs in the
296 * inode index and can be fairly deep once
297 * the radix tree becomes a bit fragmented.
298 * nominally 100M inodes would be only 4 deep,
299 * plus a maximally sized file would be another
300 * 8 deep, but with fragmentation it can wind
301 * up being a lot more.
302 *
303 * However, when backing out, we have to place
304 * all the entries in each parent node not
305 * yet processed on the list too, and because
306 * these entries are shallower they must be
307 * placed after each other in order to maintain
308 * our depth-first processing.
309 */
310 save = kmalloc(sizeof(*save), M_HAMMER2,
311 M_WAITOK | M_ZERO);
312 save->chain = chain;
313 hammer2_chain_ref(chain);
314
315 if (info->backout) {
316 TAILQ_INSERT_AFTER(&info->list,
317 info->backout,
318 save, entry);
319 } else {
320 TAILQ_INSERT_HEAD(&info->list,
321 save, entry);
322 }
323 info->backout = save;
324 ++info->list_count;
325 if (info->list_count_max < info->list_count)
326 info->list_count_max = info->list_count;
327
328 /* guess */
329 info->pri += 10;
330 } else {
331 int savepri = info->pri;
332
333 hammer2_chain_unlock(chain);
334 hammer2_chain_unlock(parent);
335 info->pri = 0;
336 rup_error |= hammer2_bulkfree_scan(chain,
337 func, info);
338 info->pri += savepri;
339 hammer2_chain_lock(parent,
340 HAMMER2_RESOLVE_ALWAYS |
341 HAMMER2_RESOLVE_SHARED);
342 hammer2_chain_lock(chain,
343 HAMMER2_RESOLVE_ALWAYS |
344 HAMMER2_RESOLVE_SHARED);
345 }
346 --info->depth;
347 break;
348 case HAMMER2_BREF_TYPE_DATA:
349 break;
350 default:
351 /* does not recurse */
352 break;
353 }
354 if (rup_error & HAMMER2_ERROR_ABORTED)
355 break;
356 }
357 if (chain) {
358 hammer2_chain_unlock(chain);
359 hammer2_chain_drop(chain);
360 }
361
362 /*
363 * If this is a PFSROOT, also re-run any defered elements
364 * added during our scan so we can report any cumulative errors
365 * for the PFS.
366 */
367 if (parent->bref.type == HAMMER2_BREF_TYPE_INODE &&
368 (parent->bref.flags & HAMMER2_BREF_FLAG_PFSROOT)) {
369 for (;;) {
370 int opri;
371
372 save = TAILQ_FIRST(&info->list);
373 if (save == tail) /* exhaust this PFS only */
374 break;
375
376 TAILQ_REMOVE(&info->list, save, entry);
377 info->backout = NULL;
378 --info->list_count;
379 opri = info->pri;
380 info->pri = 0;
381 rup_error |= hammer2_bulkfree_scan(save->chain, func, info);
382 hammer2_chain_drop(save->chain);
383 kfree(save, M_HAMMER2);
384 info->pri = opri;
385 }
386 }
387
388 error |= rup_error;
389
390 /*
391 * Report which PFS the errors were encountered in.
392 */
393 if (parent->bref.type == HAMMER2_BREF_TYPE_INODE &&
394 (parent->bref.flags & HAMMER2_BREF_FLAG_PFSROOT) &&
395 (error & ~HAMMER2_ERROR_EOF)) {
396 kprintf("hammer2_bulkfree: Encountered errors (%08x) "
397 "while scanning \"%s\"\n",
398 error, parent->data->ipdata.filename);
399 }
400
401 /*
402 * Save with higher pri now that we know what it is.
403 */
404 h2_bulkfree_test(info, &parent->bref, info->pri + 1,
405 (error & ~HAMMER2_ERROR_EOF));
406
407 done:
408 hammer2_chain_unlock(parent);
409
410 return (error & ~HAMMER2_ERROR_EOF);
411 }
412
413 /*
414 * Bulkfree algorithm
415 *
416 * Repeat {
417 * Chain flush (partial synchronization) XXX removed
418 * Scan the whole topology - build in-memory freemap (mark 11)
419 * Reconcile the in-memory freemap against the on-disk freemap.
420 * ondisk xx -> ondisk 11 (if allocated)
421 * ondisk 11 -> ondisk 10 (if free in-memory)
422 * ondisk 10 -> ondisk 00 (if free in-memory) - on next pass
423 * }
424 *
425 * The topology scan may have to be performed multiple times to window
426 * freemaps which are too large to fit in kernel memory.
427 *
428 * Races are handled using a double-transition (11->10, 10->00). The bulkfree
429 * scan snapshots the volume root's blockset and thus can run concurrent with
430 * normal operations, as long as a full flush is made between each pass to
431 * synchronize any modified chains (otherwise their blocks might be improperly
432 * freed).
433 *
434 * Temporary memory in multiples of 32KB is required to reconstruct the leaf
435 * hammer2_bmap_data blocks so they can later be compared against the live
436 * freemap. Each 32KB represents 256 x 16KB x 256 = ~1 GB of storage.
437 * A 32MB save area thus represents around ~1 TB. The temporary memory
438 * allocated can be specified. If it is not sufficient multiple topology
439 * passes will be made.
440 */
441
442 /*
443 * Bulkfree callback info
444 */
445 static void hammer2_bulkfree_thread(void *arg __unused);
446 static void cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size);
447 static int h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo,
448 hammer2_blockref_t *bref);
449 static int h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo);
450 static void h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
451 hammer2_off_t data_off, hammer2_bmap_data_t *live,
452 hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base);
453
454 void
hammer2_bulkfree_init(hammer2_dev_t * hmp)455 hammer2_bulkfree_init(hammer2_dev_t *hmp)
456 {
457 hammer2_thr_create(&hmp->bfthr, NULL, hmp,
458 hmp->devrepname, -1, -1,
459 hammer2_bulkfree_thread);
460 }
461
462 void
hammer2_bulkfree_uninit(hammer2_dev_t * hmp)463 hammer2_bulkfree_uninit(hammer2_dev_t *hmp)
464 {
465 hammer2_thr_delete(&hmp->bfthr);
466 }
467
468 static void
hammer2_bulkfree_thread(void * arg)469 hammer2_bulkfree_thread(void *arg)
470 {
471 hammer2_thread_t *thr = arg;
472 hammer2_ioc_bulkfree_t bfi;
473 uint32_t flags;
474
475 for (;;) {
476 hammer2_thr_wait_any(thr,
477 HAMMER2_THREAD_STOP |
478 HAMMER2_THREAD_FREEZE |
479 HAMMER2_THREAD_UNFREEZE |
480 HAMMER2_THREAD_REMASTER,
481 hz * 60);
482
483 flags = thr->flags;
484 cpu_ccfence();
485 if (flags & HAMMER2_THREAD_STOP)
486 break;
487 if (flags & HAMMER2_THREAD_FREEZE) {
488 hammer2_thr_signal2(thr, HAMMER2_THREAD_FROZEN,
489 HAMMER2_THREAD_FREEZE);
490 continue;
491 }
492 if (flags & HAMMER2_THREAD_UNFREEZE) {
493 hammer2_thr_signal2(thr, 0,
494 HAMMER2_THREAD_FROZEN |
495 HAMMER2_THREAD_UNFREEZE);
496 continue;
497 }
498 if (flags & HAMMER2_THREAD_FROZEN)
499 continue;
500 if (flags & HAMMER2_THREAD_REMASTER) {
501 hammer2_thr_signal2(thr, 0, HAMMER2_THREAD_REMASTER);
502 bzero(&bfi, sizeof(bfi));
503 bfi.size = 8192 * 1024;
504 /* hammer2_bulkfree_pass(thr->hmp, &bfi); */
505 }
506 }
507 thr->td = NULL;
508 hammer2_thr_signal(thr, HAMMER2_THREAD_STOPPED);
509 /* structure can go invalid at this point */
510 }
511
512 int
hammer2_bulkfree_pass(hammer2_dev_t * hmp,hammer2_chain_t * vchain,hammer2_ioc_bulkfree_t * bfi)513 hammer2_bulkfree_pass(hammer2_dev_t *hmp, hammer2_chain_t *vchain,
514 hammer2_ioc_bulkfree_t *bfi)
515 {
516 hammer2_bulkfree_info_t cbinfo;
517 hammer2_chain_save_t *save;
518 hammer2_off_t incr;
519 size_t size;
520 int error;
521
522 /*
523 * We have to clear the live dedup cache as it might have entries
524 * that are freeable as of now. Any new entries in the dedup cache
525 * made after this point, even if they become freeable, will have
526 * previously been fully allocated and will be protected by the
527 * 2-stage bulkfree.
528 */
529 hammer2_dedup_clear(hmp);
530
531 /*
532 * Setup for free pass using the buffer size specified by the
533 * hammer2 utility, 32K-aligned.
534 */
535 bzero(&cbinfo, sizeof(cbinfo));
536 size = (bfi->size + HAMMER2_FREEMAP_LEVELN_PSIZE - 1) &
537 ~(size_t)(HAMMER2_FREEMAP_LEVELN_PSIZE - 1);
538
539 /*
540 * Cap at 1/4 physical memory (hammer2 utility will not normally
541 * ever specify a buffer this big, but leave the option available).
542 */
543 if (size > kmem_lim_size() * 1024 * 1024 / 4) {
544 size = kmem_lim_size() * 1024 * 1024 / 4;
545 kprintf("hammer2: Warning: capping bulkfree buffer at %jdM\n",
546 (intmax_t)size / (1024 * 1024));
547 }
548
549 #define HAMMER2_FREEMAP_SIZEDIV \
550 (HAMMER2_FREEMAP_LEVEL1_SIZE / HAMMER2_FREEMAP_LEVELN_PSIZE)
551
552 /*
553 * Cap at the size needed to cover the whole volume to avoid
554 * making an unnecessarily large allocation.
555 */
556 if (size > hmp->total_size / HAMMER2_FREEMAP_SIZEDIV)
557 size = howmany(hmp->total_size, HAMMER2_FREEMAP_SIZEDIV);
558
559 /*
560 * Minimum bitmap buffer size, then align to a LEVELN_PSIZE (32K)
561 * boundary.
562 */
563 if (size < 1024 * 1024)
564 size = 1024 * 1024;
565 size = (size + HAMMER2_FREEMAP_LEVELN_PSIZE - 1) &
566 ~(size_t)(HAMMER2_FREEMAP_LEVELN_PSIZE - 1);
567
568 cbinfo.hmp = hmp;
569 cbinfo.bmap = kmem_alloc_swapbacked(&cbinfo.kp, size, VM_SUBSYS_HAMMER);
570 cbinfo.dedup = kmalloc(sizeof(*cbinfo.dedup) * HAMMER2_DEDUP_HEUR_SIZE,
571 M_HAMMER2, M_WAITOK | M_ZERO);
572
573 kprintf("hammer2: bulkfree buf=%jdM\n",
574 (intmax_t)size / (1024 * 1024));
575
576 /*
577 * Normalize start point to a 1GB boundary. We operate on a
578 * 32KB leaf bitmap boundary which represents 1GB of storage.
579 */
580 cbinfo.sbase = bfi->sbase;
581 if (cbinfo.sbase > hmp->total_size)
582 cbinfo.sbase = hmp->total_size;
583 cbinfo.sbase &= ~HAMMER2_FREEMAP_LEVEL1_MASK;
584 TAILQ_INIT(&cbinfo.list);
585
586 cbinfo.bulkfree_ticks = ticks;
587
588 /*
589 * Loop on a full meta-data scan as many times as required to
590 * get through all available storage.
591 */
592 error = 0;
593 while (cbinfo.sbase < hmp->total_size) {
594 /*
595 * We have enough ram to represent (incr) bytes of storage.
596 * Each 32KB of ram represents 1GB of storage.
597 *
598 * We must also clean out our de-duplication heuristic for
599 * each (incr) bytes of storage, otherwise we wind up not
600 * scanning meta-data for later areas of storage because
601 * they had already been scanned in earlier areas of storage.
602 * Since the ranging is different, we have to restart
603 * the dedup heuristic too.
604 */
605 int allmedia;
606
607 cbinfo_bmap_init(&cbinfo, size);
608 bzero(cbinfo.dedup, sizeof(*cbinfo.dedup) *
609 HAMMER2_DEDUP_HEUR_SIZE);
610 cbinfo.count_inodes_scanned = 0;
611 cbinfo.count_dirents_scanned = 0;
612 cbinfo.count_bytes_scanned = 0;
613 cbinfo.count_chains_scanned = 0;
614 cbinfo.count_chains_reported = 0;
615
616 incr = size / HAMMER2_FREEMAP_LEVELN_PSIZE *
617 HAMMER2_FREEMAP_LEVEL1_SIZE;
618 if (hmp->total_size - cbinfo.sbase <= incr) {
619 cbinfo.sstop = hmp->total_size;
620 allmedia = 1;
621 } else {
622 cbinfo.sstop = cbinfo.sbase + incr;
623 allmedia = 0;
624 }
625 kprintf("hammer2: pass %016jx-%016jx ",
626 (intmax_t)cbinfo.sbase,
627 (intmax_t)cbinfo.sstop);
628 if (allmedia && cbinfo.sbase == 0)
629 kprintf("(all media)\n");
630 else if (allmedia)
631 kprintf("(remaining media)\n");
632 else
633 kprintf("(%jdGB of media)\n",
634 (intmax_t)incr / (1024L*1024*1024));
635
636 /*
637 * Scan topology for stuff inside this range.
638 *
639 * NOTE - By not using a transaction the operation can
640 * run concurrent with the frontend as well as
641 * with flushes.
642 *
643 * We cannot safely set a mtid without a transaction,
644 * and in fact we don't want to set one anyway. We
645 * want the bulkfree to be passive and no interfere
646 * with crash recovery.
647 */
648 #undef HAMMER2_BULKFREE_TRANS /* undef - don't use transaction */
649 #ifdef HAMMER2_BULKFREE_TRANS
650 hammer2_trans_init(hmp->spmp, 0);
651 cbinfo.mtid = hammer2_trans_sub(hmp->spmp);
652 #else
653 cbinfo.mtid = 0;
654 #endif
655 cbinfo.pri = 0;
656 error |= hammer2_bulkfree_scan(vchain,
657 h2_bulkfree_callback, &cbinfo);
658
659 while ((save = TAILQ_FIRST(&cbinfo.list)) != NULL &&
660 (error & ~HAMMER2_ERROR_CHECK) == 0) {
661 TAILQ_REMOVE(&cbinfo.list, save, entry);
662 --cbinfo.list_count;
663 cbinfo.pri = 0;
664 cbinfo.backout = NULL;
665 error |= hammer2_bulkfree_scan(save->chain,
666 h2_bulkfree_callback,
667 &cbinfo);
668 hammer2_chain_drop(save->chain);
669 kfree(save, M_HAMMER2);
670 }
671 while (save) {
672 TAILQ_REMOVE(&cbinfo.list, save, entry);
673 --cbinfo.list_count;
674 hammer2_chain_drop(save->chain);
675 kfree(save, M_HAMMER2);
676 save = TAILQ_FIRST(&cbinfo.list);
677 }
678 cbinfo.backout = NULL;
679
680 /*
681 * If the complete scan succeeded we can synchronize our
682 * in-memory freemap against live storage. If an abort
683 * occured we cannot safely synchronize our partially
684 * filled-out in-memory freemap.
685 *
686 * We still synchronize on CHECK failures. That is, we still
687 * want bulkfree to operate even if the filesystem has defects.
688 */
689 if (error & ~HAMMER2_ERROR_CHECK) {
690 kprintf("bulkfree lastdrop %d %d error=0x%04x\n",
691 vchain->refs, vchain->core.chain_count, error);
692 } else {
693 if (error & HAMMER2_ERROR_CHECK) {
694 kprintf("bulkfree lastdrop %d %d "
695 "(with check errors)\n",
696 vchain->refs, vchain->core.chain_count);
697 } else {
698 kprintf("bulkfree lastdrop %d %d\n",
699 vchain->refs, vchain->core.chain_count);
700 }
701
702 error = h2_bulkfree_sync(&cbinfo);
703
704 hammer2_voldata_lock(hmp);
705 hammer2_voldata_modify(hmp);
706 hmp->voldata.allocator_free += cbinfo.adj_free;
707 hammer2_voldata_unlock(hmp);
708 }
709
710 /*
711 * Cleanup for next loop.
712 */
713 #ifdef HAMMER2_BULKFREE_TRANS
714 hammer2_trans_done(hmp->spmp, 0);
715 #endif
716 if (error & ~HAMMER2_ERROR_CHECK)
717 break;
718 cbinfo.sbase = cbinfo.sstop;
719 cbinfo.adj_free = 0;
720 }
721 kmem_free_swapbacked(&cbinfo.kp);
722 kfree(cbinfo.dedup, M_HAMMER2);
723 cbinfo.dedup = NULL;
724
725 bfi->sstop = cbinfo.sbase;
726
727 incr = bfi->sstop / (hmp->total_size / 10000);
728 if (incr > 10000)
729 incr = 10000;
730
731 kprintf("bulkfree pass statistics (%d.%02d%% storage processed):\n",
732 (int)incr / 100,
733 (int)incr % 100);
734
735 if (error & ~HAMMER2_ERROR_CHECK) {
736 kprintf(" bulkfree was aborted\n");
737 } else {
738 if (error & HAMMER2_ERROR_CHECK) {
739 kprintf(" WARNING: bulkfree "
740 "encountered CRC errors\n");
741 }
742 kprintf(" transition->free %ld\n", cbinfo.count_10_00);
743 kprintf(" transition->staged %ld\n", cbinfo.count_11_10);
744 kprintf(" ERR(00)->allocated %ld\n", cbinfo.count_00_11);
745 kprintf(" ERR(01)->allocated %ld\n", cbinfo.count_01_11);
746 kprintf(" staged->allocated %ld\n", cbinfo.count_10_11);
747 kprintf(" ~4MB segs cleaned %ld\n", cbinfo.count_l0cleans);
748 kprintf(" linear adjusts %ld\n",
749 cbinfo.count_linadjusts);
750 kprintf(" dedup factor %ld\n",
751 cbinfo.count_dedup_factor);
752 kprintf(" max saved chains %ld\n", cbinfo.list_count_max);
753 }
754
755 return error;
756 }
757
758 static void
cbinfo_bmap_init(hammer2_bulkfree_info_t * cbinfo,size_t size)759 cbinfo_bmap_init(hammer2_bulkfree_info_t *cbinfo, size_t size)
760 {
761 hammer2_bmap_data_t *bmap = cbinfo->bmap;
762 hammer2_key_t key = cbinfo->sbase;
763 hammer2_key_t lokey;
764 hammer2_key_t hikey;
765
766 lokey = (cbinfo->hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) &
767 ~HAMMER2_SEGMASK64;
768 hikey = cbinfo->hmp->total_size & ~HAMMER2_SEGMASK64;
769
770 bzero(bmap, size);
771 while (size) {
772 bzero(bmap, sizeof(*bmap));
773 if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX))
774 lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX);
775 if (lokey < H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64)
776 lokey = H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64;
777 if (key < lokey || key >= hikey) {
778 memset(bmap->bitmapq, -1,
779 sizeof(bmap->bitmapq));
780 bmap->avail = 0;
781 bmap->linear = HAMMER2_SEGSIZE;
782 } else {
783 bmap->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
784 }
785 size -= sizeof(*bmap);
786 key += HAMMER2_FREEMAP_LEVEL0_SIZE;
787 ++bmap;
788 }
789 }
790
791 static int
h2_bulkfree_callback(hammer2_bulkfree_info_t * cbinfo,hammer2_blockref_t * bref)792 h2_bulkfree_callback(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref)
793 {
794 hammer2_bmap_data_t *bmap;
795 hammer2_off_t data_off;
796 uint16_t class;
797 size_t bytes;
798 int radix;
799
800 /*
801 * Check for signal and allow yield to userland during scan.
802 */
803 if (hammer2_signal_check(&cbinfo->save_time))
804 return HAMMER2_ERROR_ABORTED;
805
806 /*
807 * Deal with kernel thread cpu or I/O hogging by limiting the
808 * number of chains scanned per second to hammer2_bulkfree_tps.
809 * Ignore leaf records (DIRENT and DATA), no per-record I/O is
810 * involved for those since we don't load their data.
811 */
812 if (bref->type != HAMMER2_BREF_TYPE_DATA &&
813 bref->type != HAMMER2_BREF_TYPE_DIRENT) {
814 ++cbinfo->bulkfree_calls;
815 if (cbinfo->bulkfree_calls > hammer2_bulkfree_tps) {
816 int dticks = ticks - cbinfo->bulkfree_ticks;
817 if (dticks < 0)
818 dticks = 0;
819 if (dticks < hz) {
820 tsleep(&cbinfo->bulkfree_ticks, 0,
821 "h2bw", hz - dticks);
822 }
823 cbinfo->bulkfree_calls = 0;
824 cbinfo->bulkfree_ticks = ticks;
825 }
826 }
827
828 /*
829 * Calculate the data offset and determine if it is within
830 * the current freemap range being gathered.
831 */
832 data_off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX;
833 if (data_off < cbinfo->sbase || data_off >= cbinfo->sstop)
834 return 0;
835 if (data_off < cbinfo->hmp->voldata.allocator_beg)
836 return 0;
837 if (data_off >= cbinfo->hmp->total_size)
838 return 0;
839
840 /*
841 * Calculate the information needed to generate the in-memory
842 * freemap record.
843 *
844 * Hammer2 does not allow allocations to cross the L1 (1GB) boundary,
845 * it's a problem if it does. (Or L0 (4MB) for that matter).
846 */
847 radix = (int)(bref->data_off & HAMMER2_OFF_MASK_RADIX);
848 KKASSERT(radix != 0);
849 bytes = (size_t)1 << radix;
850 class = (bref->type << 8) | HAMMER2_PBUFRADIX;
851
852 if (data_off + bytes > cbinfo->sstop) {
853 kprintf("hammer2_bulkfree_scan: illegal 1GB boundary "
854 "%016jx %016jx/%d\n",
855 (intmax_t)bref->data_off,
856 (intmax_t)bref->key,
857 bref->keybits);
858 bytes = cbinfo->sstop - data_off; /* XXX */
859 }
860
861 /*
862 * Convert to a storage offset relative to the beginning of the
863 * storage range we are collecting. Then lookup the level0 bmap entry.
864 */
865 data_off -= cbinfo->sbase;
866 bmap = cbinfo->bmap + (data_off >> HAMMER2_FREEMAP_LEVEL0_RADIX);
867
868 /*
869 * Convert data_off to a bmap-relative value (~4MB storage range).
870 * Adjust linear, class, and avail.
871 *
872 * Hammer2 does not allow allocations to cross the L0 (4MB) boundary,
873 */
874 data_off &= HAMMER2_FREEMAP_LEVEL0_MASK;
875 if (data_off + bytes > HAMMER2_FREEMAP_LEVEL0_SIZE) {
876 kprintf("hammer2_bulkfree_scan: illegal 4MB boundary "
877 "%016jx %016jx/%d\n",
878 (intmax_t)bref->data_off,
879 (intmax_t)bref->key,
880 bref->keybits);
881 bytes = HAMMER2_FREEMAP_LEVEL0_SIZE - data_off;
882 }
883
884 if (bmap->class == 0) {
885 bmap->class = class;
886 bmap->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
887 }
888
889 /*
890 * NOTE: bmap->class does not have to match class. Classification
891 * is relaxed when free space is low, so some mixing can occur.
892 */
893 #if 0
894 /*
895 * XXX removed
896 */
897 if (bmap->class != class) {
898 kprintf("hammer2_bulkfree_scan: illegal mixed class "
899 "%016jx %016jx/%d (%04x vs %04x)\n",
900 (intmax_t)bref->data_off,
901 (intmax_t)bref->key,
902 bref->keybits,
903 class, bmap->class);
904 }
905 #endif
906
907 /*
908 * Just record the highest byte-granular offset for now. Do not
909 * match against allocations which are in multiples of whole blocks.
910 *
911 * Make sure that any in-block linear offset at least covers the
912 * data range. This can cause bmap->linear to become block-aligned.
913 */
914 if (bytes & HAMMER2_FREEMAP_BLOCK_MASK) {
915 if (bmap->linear < (int32_t)data_off + (int32_t)bytes)
916 bmap->linear = (int32_t)data_off + (int32_t)bytes;
917 } else if (bmap->linear >= (int32_t)data_off &&
918 bmap->linear < (int32_t)data_off + (int32_t)bytes) {
919 bmap->linear = (int32_t)data_off + (int32_t)bytes;
920 }
921
922 /*
923 * Adjust the hammer2_bitmap_t bitmap[HAMMER2_BMAP_ELEMENTS].
924 * 64-bit entries, 2 bits per entry, to code 11.
925 *
926 * NOTE: data_off mask to 524288, shift right by 14 (radix for 16384),
927 * and multiply shift amount by 2 for sets of 2 bits.
928 *
929 * NOTE: The allocation can be smaller than HAMMER2_FREEMAP_BLOCK_SIZE.
930 * also, data_off may not be FREEMAP_BLOCK_SIZE aligned.
931 */
932 while (bytes > 0) {
933 hammer2_bitmap_t bmask;
934 int bindex;
935
936 bindex = (int)data_off >> (HAMMER2_FREEMAP_BLOCK_RADIX +
937 HAMMER2_BMAP_INDEX_RADIX);
938 bmask = (hammer2_bitmap_t)3 <<
939 ((((int)data_off & HAMMER2_BMAP_INDEX_MASK) >>
940 HAMMER2_FREEMAP_BLOCK_RADIX) << 1);
941
942 /*
943 * NOTE! The (avail) calculation is bitmap-granular. Multiple
944 * sub-granular records can wind up at the same bitmap
945 * position.
946 */
947 if ((bmap->bitmapq[bindex] & bmask) == 0) {
948 if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE) {
949 bmap->avail -= HAMMER2_FREEMAP_BLOCK_SIZE;
950 } else {
951 bmap->avail -= bytes;
952 }
953 bmap->bitmapq[bindex] |= bmask;
954 }
955 data_off += HAMMER2_FREEMAP_BLOCK_SIZE;
956 if (bytes < HAMMER2_FREEMAP_BLOCK_SIZE)
957 bytes = 0;
958 else
959 bytes -= HAMMER2_FREEMAP_BLOCK_SIZE;
960 }
961 return 0;
962 }
963
964 /*
965 * Synchronize the in-memory bitmap with the live freemap. This is not a
966 * direct copy. Instead the bitmaps must be compared:
967 *
968 * In-memory Live-freemap
969 * 00 11 -> 10 (do nothing if live modified)
970 * 10 -> 00 (do nothing if live modified)
971 * 11 10 -> 11 handles race against live
972 * ** -> 11 nominally warn of corruption
973 *
974 * We must also fixup the hints in HAMMER2_BREF_TYPE_FREEMAP_LEAF.
975 */
976 static int
h2_bulkfree_sync(hammer2_bulkfree_info_t * cbinfo)977 h2_bulkfree_sync(hammer2_bulkfree_info_t *cbinfo)
978 {
979 hammer2_off_t data_off;
980 hammer2_key_t key;
981 hammer2_key_t key_dummy;
982 hammer2_bmap_data_t *bmap;
983 hammer2_bmap_data_t *live;
984 hammer2_chain_t *live_parent;
985 hammer2_chain_t *live_chain;
986 int bmapindex;
987 int error;
988
989 kprintf("hammer2_bulkfree - range ");
990
991 if (cbinfo->sbase < cbinfo->hmp->voldata.allocator_beg)
992 kprintf("%016jx-",
993 (intmax_t)cbinfo->hmp->voldata.allocator_beg);
994 else
995 kprintf("%016jx-",
996 (intmax_t)cbinfo->sbase);
997
998 if (cbinfo->sstop > cbinfo->hmp->total_size)
999 kprintf("%016jx\n",
1000 (intmax_t)cbinfo->hmp->total_size);
1001 else
1002 kprintf("%016jx\n",
1003 (intmax_t)cbinfo->sstop);
1004
1005 data_off = cbinfo->sbase;
1006 bmap = cbinfo->bmap;
1007
1008 live_parent = &cbinfo->hmp->fchain;
1009 hammer2_chain_ref(live_parent);
1010 hammer2_chain_lock(live_parent, HAMMER2_RESOLVE_ALWAYS);
1011 live_chain = NULL;
1012 error = 0;
1013
1014 /*
1015 * Iterate each hammer2_bmap_data_t line (128 bytes) managing
1016 * 4MB of storage.
1017 */
1018 while (data_off < cbinfo->sstop) {
1019 /*
1020 * The freemap is not used below allocator_beg or beyond
1021 * total_size.
1022 */
1023
1024 if (data_off < cbinfo->hmp->voldata.allocator_beg)
1025 goto next;
1026 if (data_off >= cbinfo->hmp->total_size)
1027 goto next;
1028
1029 /*
1030 * Locate the freemap leaf on the live filesystem
1031 */
1032 key = (data_off & ~HAMMER2_FREEMAP_LEVEL1_MASK);
1033
1034 if (live_chain == NULL || live_chain->bref.key != key) {
1035 if (live_chain) {
1036 hammer2_chain_unlock(live_chain);
1037 hammer2_chain_drop(live_chain);
1038 }
1039 live_chain = hammer2_chain_lookup(
1040 &live_parent,
1041 &key_dummy,
1042 key,
1043 key + HAMMER2_FREEMAP_LEVEL1_MASK,
1044 &error,
1045 HAMMER2_LOOKUP_ALWAYS);
1046 if (error) {
1047 kprintf("hammer2_bulkfree: freemap lookup "
1048 "error near %016jx, error %s\n",
1049 (intmax_t)data_off,
1050 hammer2_error_str(live_chain->error));
1051 break;
1052 }
1053 }
1054 if (live_chain == NULL) {
1055 /*
1056 * XXX if we implement a full recovery mode we need
1057 * to create/recreate missing freemap chains if our
1058 * bmap has any allocated blocks.
1059 */
1060 if (bmap->class &&
1061 bmap->avail != HAMMER2_FREEMAP_LEVEL0_SIZE) {
1062 kprintf("hammer2_bulkfree: cannot locate "
1063 "live leaf for allocated data "
1064 "near %016jx\n",
1065 (intmax_t)data_off);
1066 }
1067 goto next;
1068 }
1069 if (live_chain->error) {
1070 kprintf("hammer2_bulkfree: unable to access freemap "
1071 "near %016jx, error %s\n",
1072 (intmax_t)data_off,
1073 hammer2_error_str(live_chain->error));
1074 hammer2_chain_unlock(live_chain);
1075 hammer2_chain_drop(live_chain);
1076 live_chain = NULL;
1077 goto next;
1078 }
1079
1080 bmapindex = (data_off & HAMMER2_FREEMAP_LEVEL1_MASK) >>
1081 HAMMER2_FREEMAP_LEVEL0_RADIX;
1082 live = &live_chain->data->bmdata[bmapindex];
1083
1084 /*
1085 * Shortcut if the bitmaps match and the live linear
1086 * indicator is sane. We can't do a perfect check of
1087 * live->linear because the only real requirement is that
1088 * if it is not block-aligned, that it not cover the space
1089 * within its current block which overlaps one of the data
1090 * ranges we scan. We don't retain enough fine-grained
1091 * data in our scan to be able to set it exactly.
1092 *
1093 * TODO - we could shortcut this by testing that both
1094 * live->class and bmap->class are 0, and both avails are
1095 * set to HAMMER2_FREEMAP_LEVEL0_SIZE (4MB).
1096 */
1097 if (bcmp(live->bitmapq, bmap->bitmapq,
1098 sizeof(bmap->bitmapq)) == 0 &&
1099 live->linear >= bmap->linear &&
1100 (hammer2_aux_flags & 1) == 0 &&
1101 bigmask_good(bmap, live_chain->bref.check.freemap.bigmask))
1102 {
1103 goto next;
1104 }
1105 if (hammer2_debug & 1) {
1106 kprintf("live %016jx %04d.%04x (avail=%d) "
1107 "bigmask %08x->%08x\n",
1108 data_off, bmapindex, live->class, live->avail,
1109 live_chain->bref.check.freemap.bigmask,
1110 live_chain->bref.check.freemap.bigmask |
1111 bigmask_get(bmap));
1112 }
1113
1114 if (hammer2_chain_modify(live_chain, cbinfo->mtid, 0, 0)) {
1115 kprintf("hammer2_bulkfree: unable to modify freemap "
1116 "at %016jx for data-block %016jx, error %s\n",
1117 live_chain->bref.data_off,
1118 (intmax_t)data_off,
1119 hammer2_error_str(live_chain->error));
1120 hammer2_chain_unlock(live_chain);
1121 hammer2_chain_drop(live_chain);
1122 live_chain = NULL;
1123 goto next;
1124 }
1125 live_chain->bref.check.freemap.bigmask = -1;
1126 cbinfo->hmp->freemap_relaxed = 0; /* reset heuristic */
1127 live = &live_chain->data->bmdata[bmapindex];
1128
1129 h2_bulkfree_sync_adjust(cbinfo, data_off, live, bmap,
1130 live_chain->bref.key +
1131 bmapindex *
1132 HAMMER2_FREEMAP_LEVEL0_SIZE);
1133 next:
1134 data_off += HAMMER2_FREEMAP_LEVEL0_SIZE;
1135 ++bmap;
1136 }
1137 if (live_chain) {
1138 hammer2_chain_unlock(live_chain);
1139 hammer2_chain_drop(live_chain);
1140 }
1141 if (live_parent) {
1142 hammer2_chain_unlock(live_parent);
1143 hammer2_chain_drop(live_parent);
1144 }
1145 return error;
1146 }
1147
1148 /*
1149 * Merge the bulkfree bitmap against the existing bitmap.
1150 */
1151 static
1152 void
h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t * cbinfo,hammer2_off_t data_off,hammer2_bmap_data_t * live,hammer2_bmap_data_t * bmap,hammer2_key_t alloc_base)1153 h2_bulkfree_sync_adjust(hammer2_bulkfree_info_t *cbinfo,
1154 hammer2_off_t data_off, hammer2_bmap_data_t *live,
1155 hammer2_bmap_data_t *bmap, hammer2_key_t alloc_base)
1156 {
1157 int bindex;
1158 int scount;
1159 hammer2_off_t tmp_off;
1160 hammer2_bitmap_t lmask;
1161 hammer2_bitmap_t mmask;
1162
1163 tmp_off = data_off;
1164
1165 for (bindex = 0; bindex < HAMMER2_BMAP_ELEMENTS; ++bindex) {
1166 lmask = live->bitmapq[bindex]; /* live */
1167 mmask = bmap->bitmapq[bindex]; /* snapshotted bulkfree */
1168 if (lmask == mmask) {
1169 tmp_off += HAMMER2_BMAP_INDEX_SIZE;
1170 continue;
1171 }
1172
1173 for (scount = 0;
1174 scount < HAMMER2_BMAP_BITS_PER_ELEMENT;
1175 scount += 2) {
1176 if ((mmask & 3) == 0) {
1177 /*
1178 * in-memory 00 live 11 -> 10
1179 * live 10 -> 00
1180 *
1181 * Storage might be marked allocated or
1182 * staged and must be remarked staged or
1183 * free.
1184 */
1185 switch (lmask & 3) {
1186 case 0: /* 00 */
1187 break;
1188 case 1: /* 01 */
1189 kprintf("hammer2_bulkfree: cannot "
1190 "transition m=00/l=01\n");
1191 break;
1192 case 2: /* 10 -> 00 */
1193 live->bitmapq[bindex] &=
1194 ~((hammer2_bitmap_t)2 << scount);
1195 live->avail +=
1196 HAMMER2_FREEMAP_BLOCK_SIZE;
1197 if (live->avail >
1198 HAMMER2_FREEMAP_LEVEL0_SIZE) {
1199 live->avail =
1200 HAMMER2_FREEMAP_LEVEL0_SIZE;
1201 }
1202 cbinfo->adj_free +=
1203 HAMMER2_FREEMAP_BLOCK_SIZE;
1204 ++cbinfo->count_10_00;
1205 hammer2_io_dedup_assert(
1206 cbinfo->hmp,
1207 tmp_off |
1208 HAMMER2_FREEMAP_BLOCK_RADIX,
1209 HAMMER2_FREEMAP_BLOCK_SIZE);
1210 break;
1211 case 3: /* 11 -> 10 */
1212 live->bitmapq[bindex] &=
1213 ~((hammer2_bitmap_t)1 << scount);
1214 ++cbinfo->count_11_10;
1215 hammer2_io_dedup_delete(
1216 cbinfo->hmp,
1217 HAMMER2_BREF_TYPE_DATA,
1218 tmp_off |
1219 HAMMER2_FREEMAP_BLOCK_RADIX,
1220 HAMMER2_FREEMAP_BLOCK_SIZE);
1221 break;
1222 }
1223 } else if ((mmask & 3) == 3) {
1224 /*
1225 * in-memory 11 live 10 -> 11
1226 * live ** -> 11
1227 *
1228 * Storage might be incorrectly marked free
1229 * or staged and must be remarked fully
1230 * allocated.
1231 */
1232 switch (lmask & 3) {
1233 case 0: /* 00 */
1234 /*
1235 * This case is not supposed to
1236 * happen. If it does, it means
1237 * that an allocated block was
1238 * thought by the filesystem to be
1239 * free.
1240 */
1241 kprintf("hammer2_bulkfree: "
1242 "00->11 critical freemap "
1243 "transition for datablock "
1244 "%016jx\n",
1245 tmp_off);
1246 ++cbinfo->count_00_11;
1247 cbinfo->adj_free -=
1248 HAMMER2_FREEMAP_BLOCK_SIZE;
1249 live->avail -=
1250 HAMMER2_FREEMAP_BLOCK_SIZE;
1251 if ((int32_t)live->avail < 0)
1252 live->avail = 0;
1253 break;
1254 case 1: /* 01 */
1255 ++cbinfo->count_01_11;
1256 break;
1257 case 2: /* 10 -> 11 */
1258 ++cbinfo->count_10_11;
1259 break;
1260 case 3: /* 11 */
1261 break;
1262 }
1263 live->bitmapq[bindex] |=
1264 ((hammer2_bitmap_t)3 << scount);
1265 }
1266 mmask >>= 2;
1267 lmask >>= 2;
1268 tmp_off += HAMMER2_FREEMAP_BLOCK_SIZE;
1269 }
1270 }
1271
1272 /*
1273 * Determine if the live bitmap is completely free and reset its
1274 * fields if so. Otherwise check to see if we can reduce the linear
1275 * offset.
1276 */
1277 for (bindex = HAMMER2_BMAP_ELEMENTS - 1; bindex >= 0; --bindex) {
1278 if (live->bitmapq[bindex] != 0)
1279 break;
1280 }
1281 if (bindex < 0) {
1282 /*
1283 * Completely empty, reset entire segment
1284 */
1285 #if 0
1286 kprintf("hammer2: cleanseg %016jx.%04x (%d)\n",
1287 alloc_base, live->class, live->avail);
1288 #endif
1289 live->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
1290 live->class = 0;
1291 live->linear = 0;
1292 ++cbinfo->count_l0cleans;
1293 } else if (bindex < 7) {
1294 /*
1295 * Partially full, bitmapq[bindex] != 0. Our bulkfree pass
1296 * does not record enough information to set live->linear
1297 * exactly.
1298 *
1299 * NOTE: Setting live->linear to a sub-block (16K) boundary
1300 * forces the live code to iterate to the next fully
1301 * free block. It does NOT mean that all blocks above
1302 * live->linear are available.
1303 *
1304 * Setting live->linear to a fragmentary (less than
1305 * 16K) boundary allows allocations to iterate within
1306 * that sub-block.
1307 */
1308 if (live->linear < bmap->linear &&
1309 ((live->linear ^ bmap->linear) &
1310 ~HAMMER2_FREEMAP_BLOCK_MASK) == 0) {
1311 /*
1312 * If greater than but still within the same
1313 * sub-block as live we can adjust linear upward.
1314 */
1315 live->linear = bmap->linear;
1316 ++cbinfo->count_linadjusts;
1317 } else {
1318 /*
1319 * Otherwise adjust to the nearest higher or same
1320 * sub-block boundary. The live system may have
1321 * bounced live->linear around so we cannot make any
1322 * assumptions with regards to available fragmentary
1323 * allocations.
1324 */
1325 live->linear =
1326 (bmap->linear + HAMMER2_FREEMAP_BLOCK_MASK) &
1327 ~HAMMER2_FREEMAP_BLOCK_MASK;
1328 ++cbinfo->count_linadjusts;
1329 }
1330 } else {
1331 /*
1332 * Completely full, effectively disable the linear iterator
1333 */
1334 live->linear = HAMMER2_SEGSIZE;
1335 }
1336
1337 #if 0
1338 if (bmap->class) {
1339 kprintf("%016jx %04d.%04x (avail=%7d) "
1340 "%08x %08x %08x %08x %08x %08x %08x %08x\n",
1341 (intmax_t)data_off,
1342 (int)((data_off &
1343 HAMMER2_FREEMAP_LEVEL1_MASK) >>
1344 HAMMER2_FREEMAP_LEVEL0_RADIX),
1345 bmap->class,
1346 bmap->avail,
1347 bmap->bitmap[0], bmap->bitmap[1],
1348 bmap->bitmap[2], bmap->bitmap[3],
1349 bmap->bitmap[4], bmap->bitmap[5],
1350 bmap->bitmap[6], bmap->bitmap[7]);
1351 }
1352 #endif
1353 }
1354
1355 /*
1356 * BULKFREE DEDUP HEURISTIC
1357 *
1358 * WARNING! This code is SMP safe but the heuristic allows SMP collisions.
1359 * All fields must be loaded into locals and validated.
1360 */
1361 static
1362 int
h2_bulkfree_test(hammer2_bulkfree_info_t * cbinfo,hammer2_blockref_t * bref,int pri,int saved_error)1363 h2_bulkfree_test(hammer2_bulkfree_info_t *cbinfo, hammer2_blockref_t *bref,
1364 int pri, int saved_error)
1365 {
1366 hammer2_dedup_t *dedup;
1367 int best;
1368 int n;
1369 int i;
1370
1371 n = hammer2_icrc32(&bref->data_off, sizeof(bref->data_off));
1372 dedup = cbinfo->dedup + (n & (HAMMER2_DEDUP_HEUR_MASK & ~7));
1373
1374 for (i = best = 0; i < 8; ++i) {
1375 if (dedup[i].data_off == bref->data_off) {
1376 if (dedup[i].ticks < pri)
1377 dedup[i].ticks = pri;
1378 if (pri == 1)
1379 cbinfo->count_dedup_factor += dedup[i].ticks;
1380 return (dedup[i].saved_error | HAMMER2_ERROR_EOF);
1381 }
1382 if (dedup[i].ticks < dedup[best].ticks)
1383 best = i;
1384 }
1385 dedup[best].data_off = bref->data_off;
1386 dedup[best].ticks = pri;
1387 dedup[best].saved_error = saved_error;
1388
1389 return 0;
1390 }
1391
1392 /*
1393 * Calculate what the bigmask should be. bigmask is permissive, so the
1394 * bits returned must be set at a minimum in the live bigmask. Other bits
1395 * might also be set in the live bigmask.
1396 */
1397 static uint32_t
bigmask_get(hammer2_bmap_data_t * bmap)1398 bigmask_get(hammer2_bmap_data_t *bmap)
1399 {
1400 hammer2_bitmap_t mask; /* 64-bit mask to check */
1401 hammer2_bitmap_t scan;
1402 uint32_t bigmask;
1403 uint32_t radix_mask;
1404 int iter;
1405 int i;
1406 int j;
1407
1408 bigmask = 0;
1409 for (i = 0; i < HAMMER2_BMAP_ELEMENTS; ++i) {
1410 mask = bmap->bitmapq[i];
1411
1412 radix_mask = 1U << HAMMER2_FREEMAP_BLOCK_RADIX;
1413 radix_mask |= radix_mask - 1;
1414 iter = 2; /* each bitmap entry is 2 bits. 2, 4, 8... */
1415 while (iter <= HAMMER2_BMAP_BITS_PER_ELEMENT) {
1416 if (iter == HAMMER2_BMAP_BITS_PER_ELEMENT)
1417 scan = -1;
1418 else
1419 scan = (1LU << iter) - 1;
1420 j = 0;
1421 while (j < HAMMER2_BMAP_BITS_PER_ELEMENT) {
1422 /*
1423 * Check if all bits are 0 (free block).
1424 * If so, set the bit in bigmask for the
1425 * allocation radix under test.
1426 */
1427 if ((scan & mask) == 0) {
1428 bigmask |= radix_mask;
1429 }
1430 scan <<= iter;
1431 j += iter;
1432 }
1433 iter <<= 1;
1434 radix_mask = (radix_mask << 1) | 1;
1435 }
1436 }
1437 return bigmask;
1438 }
1439
1440 static int
bigmask_good(hammer2_bmap_data_t * bmap,uint32_t live_bigmask)1441 bigmask_good(hammer2_bmap_data_t *bmap, uint32_t live_bigmask)
1442 {
1443 uint32_t bigmask;
1444
1445 bigmask = bigmask_get(bmap);
1446 return ((live_bigmask & bigmask) == bigmask);
1447 }
1448