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