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 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 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 463 hammer2_bulkfree_uninit(hammer2_dev_t *hmp) 464 { 465 hammer2_thr_delete(&hmp->bfthr); 466 } 467 468 static void 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 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 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 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 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 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 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 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 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