1 /* 2 * Copyright (c) 2011-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 * by Venkatesh Srinivas <vsrinivas@dragonflybsd.org> 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * 3. Neither the name of The DragonFly Project nor the names of its 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific, prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 31 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 32 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 #include <sys/param.h> 36 #include <sys/systm.h> 37 #include <sys/kernel.h> 38 #include <sys/fcntl.h> 39 #include <sys/buf.h> 40 #include <sys/proc.h> 41 #include <sys/namei.h> 42 #include <sys/mount.h> 43 #include <sys/vnode.h> 44 #include <sys/mountctl.h> 45 46 #include "hammer2.h" 47 48 #define FREEMAP_DEBUG 0 49 50 struct hammer2_fiterate { 51 hammer2_off_t bpref; 52 hammer2_off_t bnext; 53 int loops; 54 int relaxed; 55 }; 56 57 typedef struct hammer2_fiterate hammer2_fiterate_t; 58 59 static int hammer2_freemap_try_alloc(hammer2_chain_t **parentp, 60 hammer2_blockref_t *bref, int radix, 61 hammer2_fiterate_t *iter, hammer2_tid_t mtid); 62 static void hammer2_freemap_init(hammer2_dev_t *hmp, 63 hammer2_key_t key, hammer2_chain_t *chain); 64 static int hammer2_bmap_alloc(hammer2_dev_t *hmp, 65 hammer2_bmap_data_t *bmap, uint16_t class, 66 int n, int sub_key, int radix, hammer2_key_t *basep); 67 static int hammer2_freemap_iterate(hammer2_chain_t **parentp, 68 hammer2_chain_t **chainp, 69 hammer2_fiterate_t *iter); 70 71 static __inline 72 int 73 hammer2_freemapradix(int radix) 74 { 75 return(radix); 76 } 77 78 /* 79 * Calculate the device offset for the specified FREEMAP_NODE or FREEMAP_LEAF 80 * bref. Return a combined media offset and physical size radix. Freemap 81 * chains use fixed storage offsets in the 4MB reserved area at the 82 * beginning of each 2GB zone 83 * 84 * XXX I made a mistake and made the reserved area begin at each LEVEL1 zone, 85 * which is on a 1GB demark. This will eat a little more space but for 86 * now we retain compatibility and make FMZONEBASE every 1GB 87 * 88 * (see same thing in hammer2_bulkfree.c near the top, as well as in 89 * newfs_hammer2). 90 * 91 * Rotate between four possibilities. Theoretically this means we have three 92 * good freemaps in case of a crash which we can use as a base for the fixup 93 * scan at mount-time. 94 */ 95 #define H2FMZONEBASE(key) ((key) & ~HAMMER2_FREEMAP_LEVEL1_MASK) 96 #define H2FMBASE(key, radix) ((key) & ~(((hammer2_off_t)1 << (radix)) - 1)) 97 #define H2FMSHIFT(radix) ((hammer2_off_t)1 << (radix)) 98 99 static 100 int 101 hammer2_freemap_reserve(hammer2_chain_t *chain, int radix) 102 { 103 hammer2_blockref_t *bref = &chain->bref; 104 hammer2_off_t off; 105 int index; 106 int index_inc; 107 size_t bytes; 108 109 /* 110 * Physical allocation size. 111 */ 112 bytes = (size_t)1 << radix; 113 114 /* 115 * Calculate block selection index 0..7 of current block. If this 116 * is the first allocation of the block (verses a modification of an 117 * existing block), we use index 0, otherwise we use the next rotating 118 * index. 119 */ 120 if ((bref->data_off & ~HAMMER2_OFF_MASK_RADIX) == 0) { 121 index = 0; 122 } else { 123 off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX & 124 (((hammer2_off_t)1 << 125 HAMMER2_FREEMAP_LEVEL1_RADIX) - 1); 126 off = off / HAMMER2_PBUFSIZE; 127 KKASSERT(off >= HAMMER2_ZONE_FREEMAP_00 && 128 off < HAMMER2_ZONE_FREEMAP_END); 129 index = (int)(off - HAMMER2_ZONE_FREEMAP_00) / 130 HAMMER2_ZONE_FREEMAP_INC; 131 KKASSERT(index >= 0 && index < HAMMER2_NFREEMAPS); 132 if (++index == HAMMER2_NFREEMAPS) 133 index = 0; 134 } 135 136 /* 137 * Calculate the block offset of the reserved block. This will 138 * point into the 4MB reserved area at the base of the appropriate 139 * 2GB zone, once added to the FREEMAP_x selection above. 140 */ 141 index_inc = index * HAMMER2_ZONE_FREEMAP_INC; 142 143 switch(bref->keybits) { 144 /* case HAMMER2_FREEMAP_LEVEL6_RADIX: not applicable */ 145 case HAMMER2_FREEMAP_LEVEL5_RADIX: /* 2EB */ 146 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 147 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 148 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL5_RADIX) + 149 (index_inc + HAMMER2_ZONE_FREEMAP_00 + 150 HAMMER2_ZONEFM_LEVEL5) * HAMMER2_PBUFSIZE; 151 break; 152 case HAMMER2_FREEMAP_LEVEL4_RADIX: /* 2EB */ 153 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 154 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 155 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL4_RADIX) + 156 (index_inc + HAMMER2_ZONE_FREEMAP_00 + 157 HAMMER2_ZONEFM_LEVEL4) * HAMMER2_PBUFSIZE; 158 break; 159 case HAMMER2_FREEMAP_LEVEL3_RADIX: /* 2PB */ 160 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 161 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 162 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL3_RADIX) + 163 (index_inc + HAMMER2_ZONE_FREEMAP_00 + 164 HAMMER2_ZONEFM_LEVEL3) * HAMMER2_PBUFSIZE; 165 break; 166 case HAMMER2_FREEMAP_LEVEL2_RADIX: /* 2TB */ 167 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 168 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 169 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL2_RADIX) + 170 (index_inc + HAMMER2_ZONE_FREEMAP_00 + 171 HAMMER2_ZONEFM_LEVEL2) * HAMMER2_PBUFSIZE; 172 break; 173 case HAMMER2_FREEMAP_LEVEL1_RADIX: /* 2GB */ 174 KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF); 175 KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 176 off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL1_RADIX) + 177 (index_inc + HAMMER2_ZONE_FREEMAP_00 + 178 HAMMER2_ZONEFM_LEVEL1) * HAMMER2_PBUFSIZE; 179 break; 180 default: 181 panic("freemap: bad radix(2) %p %d\n", bref, bref->keybits); 182 /* NOT REACHED */ 183 off = (hammer2_off_t)-1; 184 break; 185 } 186 bref->data_off = off | radix; 187 #if FREEMAP_DEBUG 188 kprintf("FREEMAP BLOCK TYPE %d %016jx/%d DATA_OFF=%016jx\n", 189 bref->type, bref->key, bref->keybits, bref->data_off); 190 #endif 191 return (0); 192 } 193 194 /* 195 * Normal freemap allocator 196 * 197 * Use available hints to allocate space using the freemap. Create missing 198 * freemap infrastructure on-the-fly as needed (including marking initial 199 * allocations using the iterator as allocated, instantiating new 2GB zones, 200 * and dealing with the end-of-media edge case). 201 * 202 * ip and bpref are only used as a heuristic to determine locality of 203 * reference. bref->key may also be used heuristically. 204 * 205 * This function is a NOP if bytes is 0. 206 */ 207 int 208 hammer2_freemap_alloc(hammer2_chain_t *chain, size_t bytes) 209 { 210 hammer2_dev_t *hmp = chain->hmp; 211 hammer2_blockref_t *bref = &chain->bref; 212 hammer2_chain_t *parent; 213 hammer2_tid_t mtid; 214 int radix; 215 int error; 216 unsigned int hindex; 217 hammer2_fiterate_t iter; 218 219 /* 220 * If allocating or downsizing to zero we just get rid of whatever 221 * data_off we had. 222 */ 223 if (bytes == 0) { 224 chain->bref.data_off = 0; 225 return 0; 226 } 227 228 KKASSERT(hmp->spmp); 229 mtid = hammer2_trans_sub(hmp->spmp); 230 231 /* 232 * Validate the allocation size. It must be a power of 2. 233 * 234 * For now require that the caller be aware of the minimum 235 * allocation (1K). 236 */ 237 radix = hammer2_getradix(bytes); 238 KKASSERT((size_t)1 << radix == bytes); 239 240 if (bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE || 241 bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) { 242 /* 243 * Freemap blocks themselves are assigned from the reserve 244 * area, not allocated from the freemap. 245 */ 246 error = hammer2_freemap_reserve(chain, radix); 247 248 return error; 249 } 250 251 KKASSERT(bytes >= HAMMER2_ALLOC_MIN && bytes <= HAMMER2_ALLOC_MAX); 252 253 /* 254 * Calculate the starting point for our allocation search. 255 * 256 * Each freemap leaf is dedicated to a specific freemap_radix. 257 * The freemap_radix can be more fine-grained than the device buffer 258 * radix which results in inodes being grouped together in their 259 * own segment, terminal-data (16K or less) and initial indirect 260 * block being grouped together, and then full-indirect and full-data 261 * blocks (64K) being grouped together. 262 * 263 * The single most important aspect of this is the inode grouping 264 * because that is what allows 'find' and 'ls' and other filesystem 265 * topology operations to run fast. 266 */ 267 #if 0 268 if (bref->data_off & ~HAMMER2_OFF_MASK_RADIX) 269 bpref = bref->data_off & ~HAMMER2_OFF_MASK_RADIX; 270 else if (trans->tmp_bpref) 271 bpref = trans->tmp_bpref; 272 else if (trans->tmp_ip) 273 bpref = trans->tmp_ip->chain->bref.data_off; 274 else 275 #endif 276 /* 277 * Heuristic tracking index. We would like one for each distinct 278 * bref type if possible. heur_freemap[] has room for two classes 279 * for each type. At a minimum we have to break-up our heuristic 280 * by device block sizes. 281 */ 282 hindex = hammer2_devblkradix(radix) - HAMMER2_MINIORADIX; 283 KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_NRADIX); 284 hindex += bref->type * HAMMER2_FREEMAP_HEUR_NRADIX; 285 hindex &= HAMMER2_FREEMAP_HEUR_TYPES * HAMMER2_FREEMAP_HEUR_NRADIX - 1; 286 KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_SIZE); 287 288 iter.bpref = hmp->heur_freemap[hindex]; 289 iter.relaxed = hmp->freemap_relaxed; 290 291 /* 292 * Make sure bpref is in-bounds. It's ok if bpref covers a zone's 293 * reserved area, the try code will iterate past it. 294 */ 295 if (iter.bpref > hmp->voldata.volu_size) 296 iter.bpref = hmp->voldata.volu_size - 1; 297 298 /* 299 * Iterate the freemap looking for free space before and after. 300 */ 301 parent = &hmp->fchain; 302 hammer2_chain_ref(parent); 303 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS); 304 error = HAMMER2_ERROR_EAGAIN; 305 iter.bnext = iter.bpref; 306 iter.loops = 0; 307 308 while (error == HAMMER2_ERROR_EAGAIN) { 309 error = hammer2_freemap_try_alloc(&parent, bref, radix, 310 &iter, mtid); 311 } 312 hmp->freemap_relaxed |= iter.relaxed; /* heuristical, SMP race ok */ 313 hmp->heur_freemap[hindex] = iter.bnext; 314 hammer2_chain_unlock(parent); 315 hammer2_chain_drop(parent); 316 317 return (error); 318 } 319 320 static int 321 hammer2_freemap_try_alloc(hammer2_chain_t **parentp, 322 hammer2_blockref_t *bref, int radix, 323 hammer2_fiterate_t *iter, hammer2_tid_t mtid) 324 { 325 hammer2_dev_t *hmp = (*parentp)->hmp; 326 hammer2_off_t l0size; 327 hammer2_off_t l1size; 328 hammer2_off_t l1mask; 329 hammer2_key_t key_dummy; 330 hammer2_chain_t *chain; 331 hammer2_off_t key; 332 size_t bytes; 333 uint16_t class; 334 int error; 335 336 /* 337 * Calculate the number of bytes being allocated, the number 338 * of contiguous bits of bitmap being allocated, and the bitmap 339 * mask. 340 * 341 * WARNING! cpu hardware may mask bits == 64 -> 0 and blow up the 342 * mask calculation. 343 */ 344 bytes = (size_t)1 << radix; 345 class = (bref->type << 8) | hammer2_devblkradix(radix); 346 347 /* 348 * Lookup the level1 freemap chain, creating and initializing one 349 * if necessary. Intermediate levels will be created automatically 350 * when necessary by hammer2_chain_create(). 351 */ 352 key = H2FMBASE(iter->bnext, HAMMER2_FREEMAP_LEVEL1_RADIX); 353 l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 354 l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 355 l1mask = l1size - 1; 356 357 chain = hammer2_chain_lookup(parentp, &key_dummy, key, key + l1mask, 358 &error, 359 HAMMER2_LOOKUP_ALWAYS | 360 HAMMER2_LOOKUP_MATCHIND); 361 362 if (chain == NULL) { 363 /* 364 * Create the missing leaf, be sure to initialize 365 * the auxillary freemap tracking information in 366 * the bref.check.freemap structure. 367 */ 368 #if 0 369 kprintf("freemap create L1 @ %016jx bpref %016jx\n", 370 key, iter->bpref); 371 #endif 372 error = hammer2_chain_create(parentp, &chain, 373 hmp->spmp, HAMMER2_METH_DEFAULT, 374 key, HAMMER2_FREEMAP_LEVEL1_RADIX, 375 HAMMER2_BREF_TYPE_FREEMAP_LEAF, 376 HAMMER2_FREEMAP_LEVELN_PSIZE, 377 mtid, 0, 0); 378 KKASSERT(error == 0); 379 if (error == 0) { 380 hammer2_chain_modify(chain, mtid, 0, 0); 381 bzero(&chain->data->bmdata[0], 382 HAMMER2_FREEMAP_LEVELN_PSIZE); 383 chain->bref.check.freemap.bigmask = (uint32_t)-1; 384 chain->bref.check.freemap.avail = l1size; 385 /* bref.methods should already be inherited */ 386 387 hammer2_freemap_init(hmp, key, chain); 388 } 389 } else if (chain->error) { 390 /* 391 * Error during lookup. 392 */ 393 kprintf("hammer2_freemap_try_alloc: %016jx: error %s\n", 394 (intmax_t)bref->data_off, 395 hammer2_error_str(chain->error)); 396 error = HAMMER2_ERROR_EIO; 397 } else if ((chain->bref.check.freemap.bigmask & 398 ((size_t)1 << radix)) == 0) { 399 /* 400 * Already flagged as not having enough space 401 */ 402 error = HAMMER2_ERROR_ENOSPC; 403 } else { 404 /* 405 * Modify existing chain to setup for adjustment. 406 */ 407 hammer2_chain_modify(chain, mtid, 0, 0); 408 } 409 410 /* 411 * Scan 4MB entries. 412 */ 413 if (error == 0) { 414 hammer2_bmap_data_t *bmap; 415 hammer2_key_t base_key; 416 int count; 417 int start; 418 int n; 419 420 KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF); 421 start = (int)((iter->bnext - key) >> 422 HAMMER2_FREEMAP_LEVEL0_RADIX); 423 KKASSERT(start >= 0 && start < HAMMER2_FREEMAP_COUNT); 424 hammer2_chain_modify(chain, mtid, 0, 0); 425 426 error = HAMMER2_ERROR_ENOSPC; 427 for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) { 428 int availchk; 429 430 if (start + count >= HAMMER2_FREEMAP_COUNT && 431 start - count < 0) { 432 break; 433 } 434 435 /* 436 * Calculate bmap pointer from thart starting index 437 * forwards. 438 * 439 * NOTE: bmap pointer is invalid if n >= FREEMAP_COUNT. 440 */ 441 n = start + count; 442 bmap = &chain->data->bmdata[n]; 443 444 if (n >= HAMMER2_FREEMAP_COUNT) { 445 availchk = 0; 446 } else if (bmap->avail) { 447 availchk = 1; 448 } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX && 449 (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) { 450 availchk = 1; 451 } else { 452 availchk = 0; 453 } 454 455 /* 456 * Try to allocate from a matching freemap class 457 * superblock. If we are in relaxed mode we allocate 458 * from any freemap class superblock. 459 */ 460 if (availchk && 461 (bmap->class == 0 || bmap->class == class || 462 iter->relaxed)) { 463 base_key = key + n * l0size; 464 error = hammer2_bmap_alloc(hmp, bmap, 465 class, n, 466 (int)bref->key, 467 radix, 468 &base_key); 469 if (error != HAMMER2_ERROR_ENOSPC) { 470 key = base_key; 471 break; 472 } 473 } 474 475 /* 476 * Calculate bmap pointer from thart starting index 477 * backwards (locality). 478 * 479 * Must recalculate after potentially having called 480 * hammer2_bmap_alloc() above in case chain was 481 * reallocated. 482 * 483 * NOTE: bmap pointer is invalid if n < 0. 484 */ 485 n = start - count; 486 bmap = &chain->data->bmdata[n]; 487 if (n < 0) { 488 availchk = 0; 489 } else if (bmap->avail) { 490 availchk = 1; 491 } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX && 492 (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) { 493 availchk = 1; 494 } else { 495 availchk = 0; 496 } 497 498 /* 499 * Try to allocate from a matching freemap class 500 * superblock. If we are in relaxed mode we allocate 501 * from any freemap class superblock. 502 */ 503 if (availchk && 504 (bmap->class == 0 || bmap->class == class || 505 iter->relaxed)) { 506 base_key = key + n * l0size; 507 error = hammer2_bmap_alloc(hmp, bmap, 508 class, n, 509 (int)bref->key, 510 radix, 511 &base_key); 512 if (error != HAMMER2_ERROR_ENOSPC) { 513 key = base_key; 514 break; 515 } 516 } 517 } 518 519 /* 520 * We only know for sure that we can clear the bitmap bit 521 * if we scanned the entire array (start == 0). 522 */ 523 if (error == HAMMER2_ERROR_ENOSPC && start == 0) { 524 chain->bref.check.freemap.bigmask &= 525 (uint32_t)~((size_t)1 << radix); 526 } 527 /* XXX also scan down from original count */ 528 } 529 530 if (error == 0) { 531 /* 532 * Assert validity. Must be beyond the static allocator used 533 * by newfs_hammer2 (and thus also beyond the aux area), 534 * not go past the volume size, and must not be in the 535 * reserved segment area for a zone. 536 */ 537 KKASSERT(key >= hmp->voldata.allocator_beg && 538 key + bytes <= hmp->voldata.volu_size); 539 KKASSERT((key & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG); 540 bref->data_off = key | radix; 541 542 /* 543 * Record dedupability. The dedup bits are cleared 544 * when bulkfree transitions the freemap from 11->10, 545 * and asserted to be clear on the 10->00 transition. 546 * 547 * We must record the bitmask with the chain locked 548 * at the time we set the allocation bits to avoid 549 * racing a bulkfree. 550 */ 551 if (bref->type == HAMMER2_BREF_TYPE_DATA) 552 hammer2_io_dedup_set(hmp, bref); 553 #if 0 554 kprintf("alloc cp=%p %016jx %016jx using %016jx\n", 555 chain, 556 bref->key, bref->data_off, chain->bref.data_off); 557 #endif 558 } else if (error == HAMMER2_ERROR_ENOSPC) { 559 /* 560 * Return EAGAIN with next iteration in iter->bnext, or 561 * return ENOSPC if the allocation map has been exhausted. 562 */ 563 error = hammer2_freemap_iterate(parentp, &chain, iter); 564 } 565 566 /* 567 * Cleanup 568 */ 569 if (chain) { 570 hammer2_chain_unlock(chain); 571 hammer2_chain_drop(chain); 572 } 573 return (error); 574 } 575 576 /* 577 * Allocate (1<<radix) bytes from the bmap whos base data offset is (*basep). 578 * 579 * If the linear iterator is mid-block we use it directly (the bitmap should 580 * already be marked allocated), otherwise we search for a block in the 581 * bitmap that fits the allocation request. 582 * 583 * A partial bitmap allocation sets the minimum bitmap granularity (16KB) 584 * to fully allocated and adjusts the linear allocator to allow the 585 * remaining space to be allocated. 586 * 587 * sub_key is the lower 32 bits of the chain->bref.key for the chain whos 588 * bref is being allocated. If the radix represents an allocation >= 16KB 589 * (aka HAMMER2_FREEMAP_BLOCK_RADIX) we try to use this key to select the 590 * blocks directly out of the bmap. 591 */ 592 static 593 int 594 hammer2_bmap_alloc(hammer2_dev_t *hmp, hammer2_bmap_data_t *bmap, 595 uint16_t class, int n, int sub_key, 596 int radix, hammer2_key_t *basep) 597 { 598 size_t size; 599 size_t bgsize; 600 int bmradix; 601 hammer2_bitmap_t bmmask; 602 int offset; 603 int i; 604 int j; 605 606 /* 607 * Take into account 2-bits per block when calculating bmradix. 608 */ 609 size = (size_t)1 << radix; 610 611 if (radix <= HAMMER2_FREEMAP_BLOCK_RADIX) { 612 bmradix = 2; 613 /* (16K) 2 bits per allocation block */ 614 } else { 615 bmradix = (hammer2_bitmap_t)2 << 616 (radix - HAMMER2_FREEMAP_BLOCK_RADIX); 617 /* (32K-256K) 4, 8, 16, 32 bits per allocation block */ 618 } 619 620 /* 621 * Use the linear iterator to pack small allocations, otherwise 622 * fall-back to finding a free 16KB chunk. The linear iterator 623 * is only valid when *NOT* on a freemap chunking boundary (16KB). 624 * If it is the bitmap must be scanned. It can become invalid 625 * once we pack to the boundary. We adjust it after a bitmap 626 * allocation only for sub-16KB allocations (so the perfectly good 627 * previous value can still be used for fragments when 16KB+ 628 * allocations are made inbetween fragmentary allocations). 629 * 630 * Beware of hardware artifacts when bmradix == 64 (intermediate 631 * result can wind up being '1' instead of '0' if hardware masks 632 * bit-count & 63). 633 * 634 * NOTE: j needs to be even in the j= calculation. As an artifact 635 * of the /2 division, our bitmask has to clear bit 0. 636 * 637 * NOTE: TODO this can leave little unallocatable fragments lying 638 * around. 639 */ 640 if (((uint32_t)bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) + size <= 641 HAMMER2_FREEMAP_BLOCK_SIZE && 642 (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) && 643 bmap->linear < HAMMER2_SEGSIZE) { 644 /* 645 * Use linear iterator if it is not block-aligned to avoid 646 * wasting space. 647 */ 648 KKASSERT(bmap->linear >= 0 && 649 bmap->linear + size <= HAMMER2_SEGSIZE && 650 (bmap->linear & (HAMMER2_ALLOC_MIN - 1)) == 0); 651 offset = bmap->linear; 652 i = offset / (HAMMER2_SEGSIZE / 8); 653 j = (offset / (HAMMER2_FREEMAP_BLOCK_SIZE / 2)) & 30; 654 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 655 HAMMER2_BMAP_ALLONES : 656 ((hammer2_bitmap_t)1 << bmradix) - 1; 657 bmmask <<= j; 658 bmap->linear = offset + size; 659 } else { 660 /* 661 * Try to index a starting point based on sub_key. This 662 * attempts to restore sequential block ordering on-disk 663 * whenever possible, even if data is committed out of 664 * order. 665 * 666 * i - Index bitmapq[], full data range represented is 667 * HAMMER2_BMAP_SIZE. 668 * 669 * j - Index within bitmapq[i], full data range represented is 670 * HAMMER2_BMAP_INDEX_SIZE. 671 * 672 * WARNING! 673 */ 674 i = -1; 675 j = -1; 676 677 switch(class >> 8) { 678 case HAMMER2_BREF_TYPE_DATA: 679 if (radix >= HAMMER2_FREEMAP_BLOCK_RADIX) { 680 i = (sub_key & HAMMER2_BMAP_MASK) / 681 (HAMMER2_BMAP_SIZE / HAMMER2_BMAP_ELEMENTS); 682 j = (sub_key & HAMMER2_BMAP_INDEX_MASK) / 683 (HAMMER2_BMAP_INDEX_SIZE / 684 HAMMER2_BMAP_BLOCKS_PER_ELEMENT); 685 j = j * 2; 686 } 687 break; 688 case HAMMER2_BREF_TYPE_INODE: 689 break; 690 default: 691 break; 692 } 693 if (i >= 0) { 694 KKASSERT(i < HAMMER2_BMAP_ELEMENTS && 695 j < 2 * HAMMER2_BMAP_BLOCKS_PER_ELEMENT); 696 KKASSERT(j + bmradix <= HAMMER2_BMAP_BITS_PER_ELEMENT); 697 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 698 HAMMER2_BMAP_ALLONES : 699 ((hammer2_bitmap_t)1 << bmradix) - 1; 700 bmmask <<= j; 701 702 if ((bmap->bitmapq[i] & bmmask) == 0) 703 goto success; 704 } 705 706 /* 707 * General element scan. 708 * 709 * WARNING: (j) is iterating a bit index (by 2's) 710 */ 711 for (i = 0; i < HAMMER2_BMAP_ELEMENTS; ++i) { 712 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 713 HAMMER2_BMAP_ALLONES : 714 ((hammer2_bitmap_t)1 << bmradix) - 1; 715 for (j = 0; 716 j < HAMMER2_BMAP_BITS_PER_ELEMENT; 717 j += bmradix) { 718 if ((bmap->bitmapq[i] & bmmask) == 0) 719 goto success; 720 bmmask <<= bmradix; 721 } 722 } 723 /*fragments might remain*/ 724 /*KKASSERT(bmap->avail == 0);*/ 725 return (HAMMER2_ERROR_ENOSPC); 726 success: 727 offset = i * (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS) + 728 (j * (HAMMER2_FREEMAP_BLOCK_SIZE / 2)); 729 if (size & HAMMER2_FREEMAP_BLOCK_MASK) 730 bmap->linear = offset + size; 731 } 732 733 /* 8 x (64/2) -> 256 x 16K -> 4MB */ 734 KKASSERT(i >= 0 && i < HAMMER2_BMAP_ELEMENTS); 735 736 /* 737 * Optimize the buffer cache to avoid unnecessary read-before-write 738 * operations. 739 * 740 * The device block size could be larger than the allocation size 741 * so the actual bitmap test is somewhat more involved. We have 742 * to use a compatible buffer size for this operation. 743 */ 744 if ((bmap->bitmapq[i] & bmmask) == 0 && 745 hammer2_devblksize(size) != size) { 746 size_t psize = hammer2_devblksize(size); 747 hammer2_off_t pmask = (hammer2_off_t)psize - 1; 748 int pbmradix = (hammer2_bitmap_t)2 << 749 (hammer2_devblkradix(radix) - 750 HAMMER2_FREEMAP_BLOCK_RADIX); 751 hammer2_bitmap_t pbmmask; 752 int pradix = hammer2_getradix(psize); 753 754 pbmmask = (pbmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 755 HAMMER2_BMAP_ALLONES : 756 ((hammer2_bitmap_t)1 << pbmradix) - 1; 757 while ((pbmmask & bmmask) == 0) 758 pbmmask <<= pbmradix; 759 760 #if 0 761 kprintf("%016jx mask %016jx %016jx %016jx (%zd/%zd)\n", 762 *basep + offset, bmap->bitmapq[i], 763 pbmmask, bmmask, size, psize); 764 #endif 765 766 if ((bmap->bitmapq[i] & pbmmask) == 0) { 767 hammer2_io_t *dio; 768 769 hammer2_io_newnz(hmp, class >> 8, 770 (*basep + (offset & ~pmask)) | 771 pradix, psize, &dio); 772 hammer2_io_putblk(&dio); 773 } 774 } 775 776 #if 0 777 /* 778 * When initializing a new inode segment also attempt to initialize 779 * an adjacent segment. Be careful not to index beyond the array 780 * bounds. 781 * 782 * We do this to try to localize inode accesses to improve 783 * directory scan rates. XXX doesn't improve scan rates. 784 */ 785 if (size == HAMMER2_INODE_BYTES) { 786 if (n & 1) { 787 if (bmap[-1].radix == 0 && bmap[-1].avail) 788 bmap[-1].radix = radix; 789 } else { 790 if (bmap[1].radix == 0 && bmap[1].avail) 791 bmap[1].radix = radix; 792 } 793 } 794 #endif 795 /* 796 * Calculate the bitmap-granular change in bgsize for the volume 797 * header. We cannot use the fine-grained change here because 798 * the bulkfree code can't undo it. If the bitmap element is already 799 * marked allocated it has already been accounted for. 800 */ 801 if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 802 if (bmap->bitmapq[i] & bmmask) 803 bgsize = 0; 804 else 805 bgsize = HAMMER2_FREEMAP_BLOCK_SIZE; 806 } else { 807 bgsize = size; 808 } 809 810 /* 811 * Adjust the bitmap, set the class (it might have been 0), 812 * and available bytes, update the allocation offset (*basep) 813 * from the L0 base to the actual offset. 814 * 815 * Do not override the class if doing a relaxed class allocation. 816 * 817 * avail must reflect the bitmap-granular availability. The allocator 818 * tests will also check the linear iterator. 819 */ 820 bmap->bitmapq[i] |= bmmask; 821 if (bmap->class == 0) 822 bmap->class = class; 823 bmap->avail -= bgsize; 824 *basep += offset; 825 826 /* 827 * Adjust the volume header's allocator_free parameter. This 828 * parameter has to be fixed up by bulkfree which has no way to 829 * figure out sub-16K chunking, so it must be adjusted by the 830 * bitmap-granular size. 831 */ 832 if (bgsize) { 833 hammer2_voldata_lock(hmp); 834 hammer2_voldata_modify(hmp); 835 hmp->voldata.allocator_free -= bgsize; 836 hammer2_voldata_unlock(hmp); 837 } 838 839 return(0); 840 } 841 842 /* 843 * Initialize a freemap for the storage area (in bytes) that begins at (key). 844 */ 845 static 846 void 847 hammer2_freemap_init(hammer2_dev_t *hmp, hammer2_key_t key, 848 hammer2_chain_t *chain) 849 { 850 hammer2_off_t l1size; 851 hammer2_off_t lokey; 852 hammer2_off_t hikey; 853 hammer2_bmap_data_t *bmap; 854 int count; 855 856 /* 857 * LEVEL1 is 1GB, there are two level1 1GB freemaps per 2GB zone. 858 */ 859 l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 860 861 /* 862 * Calculate the portion of the 1GB map that should be initialized 863 * as free. Portions below or after will be initialized as allocated. 864 * SEGMASK-align the areas so we don't have to worry about sub-scans 865 * or endianess when using memset. 866 * 867 * WARNING! It is possible for lokey to be larger than hikey if the 868 * entire 2GB segment is within the static allocation. 869 */ 870 /* 871 * (1) Ensure that all statically allocated space from newfs_hammer2 872 * is marked allocated, and take it up to the level1 base for 873 * this key. 874 */ 875 lokey = (hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) & 876 ~HAMMER2_SEGMASK64; 877 if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX)) 878 lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX); 879 880 /* 881 * (2) Ensure that the reserved area is marked allocated (typically 882 * the first 4MB of each 2GB area being represented). Since 883 * each LEAF represents 1GB of storage and the zone is 2GB, we 884 * have to adjust lowkey upward every other LEAF sequentially. 885 */ 886 if (lokey < H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64) 887 lokey = H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64; 888 889 /* 890 * (3) Ensure that any trailing space at the end-of-volume is marked 891 * allocated. 892 */ 893 hikey = key + H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 894 if (hikey > hmp->voldata.volu_size) { 895 hikey = hmp->voldata.volu_size & ~HAMMER2_SEGMASK64; 896 } 897 898 /* 899 * Heuristic highest possible value 900 */ 901 chain->bref.check.freemap.avail = 902 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 903 bmap = &chain->data->bmdata[0]; 904 905 /* 906 * Initialize bitmap (bzero'd by caller) 907 */ 908 for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) { 909 if (key < lokey || key >= hikey) { 910 memset(bmap->bitmapq, -1, 911 sizeof(bmap->bitmapq)); 912 bmap->avail = 0; 913 bmap->linear = HAMMER2_SEGSIZE; 914 chain->bref.check.freemap.avail -= 915 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 916 } else { 917 bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 918 } 919 key += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 920 ++bmap; 921 } 922 } 923 924 /* 925 * The current Level 1 freemap has been exhausted, iterate to the next 926 * one, return ENOSPC if no freemaps remain. 927 * 928 * At least two loops are required. If we are not in relaxed mode and 929 * we run out of storage we enter relaxed mode and do a third loop. 930 * The relaxed mode is recorded back in the hmp so once we enter the mode 931 * we remain relaxed until stuff begins to get freed and only do 2 loops. 932 * 933 * XXX this should rotate back to the beginning to handle freed-up space 934 * XXX or use intermediate entries to locate free space. TODO 935 */ 936 static int 937 hammer2_freemap_iterate(hammer2_chain_t **parentp, hammer2_chain_t **chainp, 938 hammer2_fiterate_t *iter) 939 { 940 hammer2_dev_t *hmp = (*parentp)->hmp; 941 942 iter->bnext &= ~(H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX) - 1); 943 iter->bnext += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 944 if (iter->bnext >= hmp->voldata.volu_size) { 945 iter->bnext = 0; 946 if (++iter->loops >= 2) { 947 if (iter->relaxed == 0) 948 iter->relaxed = 1; 949 else 950 return (HAMMER2_ERROR_ENOSPC); 951 } 952 } 953 return(HAMMER2_ERROR_EAGAIN); 954 } 955 956 /* 957 * Adjust the bit-pattern for data in the freemap bitmap according to 958 * (how). This code is called from on-mount recovery to fixup (mark 959 * as allocated) blocks whos freemap upates might not have been committed 960 * in the last crash and is used by the bulk freemap scan to stage frees. 961 * 962 * WARNING! Cannot be called with a empty-data bref (radix == 0). 963 * 964 * XXX currently disabled when how == 0 (the normal real-time case). At 965 * the moment we depend on the bulk freescan to actually free blocks. It 966 * will still call this routine with a non-zero how to stage possible frees 967 * and to do the actual free. 968 */ 969 void 970 hammer2_freemap_adjust(hammer2_dev_t *hmp, hammer2_blockref_t *bref, 971 int how) 972 { 973 hammer2_off_t data_off = bref->data_off; 974 hammer2_chain_t *chain; 975 hammer2_chain_t *parent; 976 hammer2_bmap_data_t *bmap; 977 hammer2_key_t key; 978 hammer2_key_t key_dummy; 979 hammer2_off_t l0size; 980 hammer2_off_t l1size; 981 hammer2_off_t l1mask; 982 hammer2_tid_t mtid; 983 hammer2_bitmap_t *bitmap; 984 const hammer2_bitmap_t bmmask00 = 0; 985 hammer2_bitmap_t bmmask01; 986 hammer2_bitmap_t bmmask10; 987 hammer2_bitmap_t bmmask11; 988 size_t bytes; 989 uint16_t class; 990 int radix; 991 int start; 992 int count; 993 int modified = 0; 994 int error; 995 size_t bgsize = 0; 996 997 KKASSERT(how == HAMMER2_FREEMAP_DORECOVER); 998 999 KKASSERT(hmp->spmp); 1000 mtid = hammer2_trans_sub(hmp->spmp); 1001 1002 radix = (int)data_off & HAMMER2_OFF_MASK_RADIX; 1003 KKASSERT(radix != 0); 1004 data_off &= ~HAMMER2_OFF_MASK_RADIX; 1005 KKASSERT(radix <= HAMMER2_RADIX_MAX); 1006 1007 if (radix) 1008 bytes = (size_t)1 << radix; 1009 else 1010 bytes = 0; 1011 class = (bref->type << 8) | hammer2_devblkradix(radix); 1012 1013 /* 1014 * We can't adjust the freemap for data allocations made by 1015 * newfs_hammer2. 1016 */ 1017 if (data_off < hmp->voldata.allocator_beg) 1018 return; 1019 1020 KKASSERT((data_off & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG); 1021 1022 /* 1023 * Lookup the level1 freemap chain. The chain must exist. 1024 */ 1025 key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL1_RADIX); 1026 l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 1027 l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 1028 l1mask = l1size - 1; 1029 1030 parent = &hmp->fchain; 1031 hammer2_chain_ref(parent); 1032 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS); 1033 1034 chain = hammer2_chain_lookup(&parent, &key_dummy, key, key + l1mask, 1035 &error, 1036 HAMMER2_LOOKUP_ALWAYS | 1037 HAMMER2_LOOKUP_MATCHIND); 1038 1039 /* 1040 * Stop early if we are trying to free something but no leaf exists. 1041 */ 1042 if (chain == NULL && how != HAMMER2_FREEMAP_DORECOVER) { 1043 kprintf("hammer2_freemap_adjust: %016jx: no chain\n", 1044 (intmax_t)bref->data_off); 1045 goto done; 1046 } 1047 if (chain->error) { 1048 kprintf("hammer2_freemap_adjust: %016jx: error %s\n", 1049 (intmax_t)bref->data_off, 1050 hammer2_error_str(chain->error)); 1051 hammer2_chain_unlock(chain); 1052 hammer2_chain_drop(chain); 1053 chain = NULL; 1054 goto done; 1055 } 1056 1057 /* 1058 * Create any missing leaf(s) if we are doing a recovery (marking 1059 * the block(s) as being allocated instead of being freed). Be sure 1060 * to initialize the auxillary freemap tracking info in the 1061 * bref.check.freemap structure. 1062 */ 1063 if (chain == NULL && how == HAMMER2_FREEMAP_DORECOVER) { 1064 error = hammer2_chain_create(&parent, &chain, 1065 hmp->spmp, HAMMER2_METH_DEFAULT, 1066 key, HAMMER2_FREEMAP_LEVEL1_RADIX, 1067 HAMMER2_BREF_TYPE_FREEMAP_LEAF, 1068 HAMMER2_FREEMAP_LEVELN_PSIZE, 1069 mtid, 0, 0); 1070 1071 if (hammer2_debug & 0x0040) { 1072 kprintf("fixup create chain %p %016jx:%d\n", 1073 chain, chain->bref.key, chain->bref.keybits); 1074 } 1075 1076 if (error == 0) { 1077 error = hammer2_chain_modify(chain, mtid, 0, 0); 1078 KKASSERT(error == 0); 1079 bzero(&chain->data->bmdata[0], 1080 HAMMER2_FREEMAP_LEVELN_PSIZE); 1081 chain->bref.check.freemap.bigmask = (uint32_t)-1; 1082 chain->bref.check.freemap.avail = l1size; 1083 /* bref.methods should already be inherited */ 1084 1085 hammer2_freemap_init(hmp, key, chain); 1086 } 1087 /* XXX handle error */ 1088 } 1089 1090 #if FREEMAP_DEBUG 1091 kprintf("FREEMAP ADJUST TYPE %d %016jx/%d DATA_OFF=%016jx\n", 1092 chain->bref.type, chain->bref.key, 1093 chain->bref.keybits, chain->bref.data_off); 1094 #endif 1095 1096 /* 1097 * Calculate the bitmask (runs in 2-bit pairs). 1098 */ 1099 start = ((int)(data_off >> HAMMER2_FREEMAP_BLOCK_RADIX) & 15) * 2; 1100 bmmask01 = (hammer2_bitmap_t)1 << start; 1101 bmmask10 = (hammer2_bitmap_t)2 << start; 1102 bmmask11 = (hammer2_bitmap_t)3 << start; 1103 1104 /* 1105 * Fixup the bitmap. Partial blocks cannot be fully freed unless 1106 * a bulk scan is able to roll them up. 1107 */ 1108 if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 1109 count = 1; 1110 if (how == HAMMER2_FREEMAP_DOREALFREE) 1111 how = HAMMER2_FREEMAP_DOMAYFREE; 1112 } else { 1113 count = 1 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX); 1114 } 1115 1116 /* 1117 * [re]load the bmap and bitmap pointers. Each bmap entry covers 1118 * a 4MB swath. The bmap itself (LEVEL1) covers 2GB. 1119 * 1120 * Be sure to reset the linear iterator to ensure that the adjustment 1121 * is not ignored. 1122 */ 1123 again: 1124 bmap = &chain->data->bmdata[(int)(data_off >> HAMMER2_SEGRADIX) & 1125 (HAMMER2_FREEMAP_COUNT - 1)]; 1126 bitmap = &bmap->bitmapq[(int)(data_off >> (HAMMER2_SEGRADIX - 3)) & 7]; 1127 1128 if (modified) 1129 bmap->linear = 0; 1130 1131 while (count) { 1132 KKASSERT(bmmask11); 1133 if (how == HAMMER2_FREEMAP_DORECOVER) { 1134 /* 1135 * Recovery request, mark as allocated. 1136 */ 1137 if ((*bitmap & bmmask11) != bmmask11) { 1138 if (modified == 0) { 1139 hammer2_chain_modify(chain, mtid, 0, 0); 1140 modified = 1; 1141 goto again; 1142 } 1143 if ((*bitmap & bmmask11) == bmmask00) { 1144 bmap->avail -= 1145 HAMMER2_FREEMAP_BLOCK_SIZE; 1146 bgsize += HAMMER2_FREEMAP_BLOCK_SIZE; 1147 } 1148 if (bmap->class == 0) 1149 bmap->class = class; 1150 *bitmap |= bmmask11; 1151 if (hammer2_debug & 0x0040) { 1152 kprintf("hammer2_freemap_recover: " 1153 "fixup type=%02x " 1154 "block=%016jx/%zd\n", 1155 bref->type, data_off, bytes); 1156 } 1157 } else { 1158 /* 1159 kprintf("hammer2_freemap_recover: good " 1160 "type=%02x block=%016jx/%zd\n", 1161 bref->type, data_off, bytes); 1162 */ 1163 } 1164 } 1165 #if 0 1166 /* 1167 * XXX this stuff doesn't work, avail is miscalculated and 1168 * code 10 means something else now. 1169 */ 1170 else if ((*bitmap & bmmask11) == bmmask11) { 1171 /* 1172 * Mayfree/Realfree request and bitmap is currently 1173 * marked as being fully allocated. 1174 */ 1175 if (!modified) { 1176 hammer2_chain_modify(chain, 0); 1177 modified = 1; 1178 goto again; 1179 } 1180 if (how == HAMMER2_FREEMAP_DOREALFREE) 1181 *bitmap &= ~bmmask11; 1182 else 1183 *bitmap = (*bitmap & ~bmmask11) | bmmask10; 1184 } else if ((*bitmap & bmmask11) == bmmask10) { 1185 /* 1186 * Mayfree/Realfree request and bitmap is currently 1187 * marked as being possibly freeable. 1188 */ 1189 if (how == HAMMER2_FREEMAP_DOREALFREE) { 1190 if (!modified) { 1191 hammer2_chain_modify(chain, 0); 1192 modified = 1; 1193 goto again; 1194 } 1195 *bitmap &= ~bmmask11; 1196 } 1197 } else { 1198 /* 1199 * 01 - Not implemented, currently illegal state 1200 * 00 - Not allocated at all, illegal free. 1201 */ 1202 panic("hammer2_freemap_adjust: " 1203 "Illegal state %08x(%08x)", 1204 *bitmap, *bitmap & bmmask11); 1205 } 1206 #endif 1207 --count; 1208 bmmask01 <<= 2; 1209 bmmask10 <<= 2; 1210 bmmask11 <<= 2; 1211 } 1212 #if HAMMER2_BMAP_ELEMENTS != 8 1213 #error "hammer2_freemap.c: HAMMER2_BMAP_ELEMENTS expected to be 8" 1214 #endif 1215 if (how == HAMMER2_FREEMAP_DOREALFREE && modified) { 1216 bmap->avail += 1 << radix; 1217 KKASSERT(bmap->avail <= HAMMER2_SEGSIZE); 1218 if (bmap->avail == HAMMER2_SEGSIZE && 1219 bmap->bitmapq[0] == 0 && 1220 bmap->bitmapq[1] == 0 && 1221 bmap->bitmapq[2] == 0 && 1222 bmap->bitmapq[3] == 0 && 1223 bmap->bitmapq[4] == 0 && 1224 bmap->bitmapq[5] == 0 && 1225 bmap->bitmapq[6] == 0 && 1226 bmap->bitmapq[7] == 0) { 1227 key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL0_RADIX); 1228 kprintf("Freeseg %016jx\n", (intmax_t)key); 1229 bmap->class = 0; 1230 } 1231 } 1232 1233 /* 1234 * chain->bref.check.freemap.bigmask (XXX) 1235 * 1236 * Setting bigmask is a hint to the allocation code that there might 1237 * be something allocatable. We also set this in recovery... it 1238 * doesn't hurt and we might want to use the hint for other validation 1239 * operations later on. 1240 * 1241 * We could calculate the largest possible allocation and set the 1242 * radii that could fit, but its easier just to set bigmask to -1. 1243 */ 1244 if (modified) { 1245 chain->bref.check.freemap.bigmask = -1; 1246 hmp->freemap_relaxed = 0; /* reset heuristic */ 1247 } 1248 1249 hammer2_chain_unlock(chain); 1250 hammer2_chain_drop(chain); 1251 done: 1252 hammer2_chain_unlock(parent); 1253 hammer2_chain_drop(parent); 1254 1255 if (bgsize) { 1256 hammer2_voldata_lock(hmp); 1257 hammer2_voldata_modify(hmp); 1258 hmp->voldata.allocator_free -= bgsize; 1259 hammer2_voldata_unlock(hmp); 1260 } 1261 } 1262 1263 /* 1264 * Validate the freemap, in three stages. 1265 * 1266 * stage-1 ALLOCATED -> POSSIBLY FREE 1267 * POSSIBLY FREE -> POSSIBLY FREE (type corrected) 1268 * 1269 * This transitions bitmap entries from ALLOCATED to POSSIBLY FREE. 1270 * The POSSIBLY FREE state does not mean that a block is actually free 1271 * and may be transitioned back to ALLOCATED in stage-2. 1272 * 1273 * This is typically done during normal filesystem operations when 1274 * something is deleted or a block is replaced. 1275 * 1276 * This is done by bulkfree in-bulk after a memory-bounded meta-data 1277 * scan to try to determine what might be freeable. 1278 * 1279 * This can be done unconditionally through a freemap scan when the 1280 * intention is to brute-force recover the proper state of the freemap. 1281 * 1282 * stage-2 POSSIBLY FREE -> ALLOCATED (scan metadata topology) 1283 * 1284 * This is done by bulkfree during a meta-data scan to ensure that 1285 * all blocks still actually allocated by the filesystem are marked 1286 * as such. 1287 * 1288 * NOTE! Live filesystem transitions to POSSIBLY FREE can occur while 1289 * the bulkfree stage-2 and stage-3 is running. The live filesystem 1290 * will use the alternative POSSIBLY FREE type (2) to prevent 1291 * stage-3 from improperly transitioning unvetted possibly-free 1292 * blocks to FREE. 1293 * 1294 * stage-3 POSSIBLY FREE (type 1) -> FREE (scan freemap) 1295 * 1296 * This is done by bulkfree to finalize POSSIBLY FREE states. 1297 * 1298 */ 1299