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