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