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, NULL, hmp->spmp, 373 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 * Calculate the bitmapq[] index (i) and calculate the 649 * shift count within the 64-bit bitmapq[] entry. 650 * 651 * The freemap block size is 16KB, but each bitmap 652 * entry is two bits so use a little trick to get 653 * a (j) shift of 0, 2, 4, ... 62 in 16KB chunks. 654 */ 655 KKASSERT(bmap->linear >= 0 && 656 bmap->linear + size <= HAMMER2_SEGSIZE && 657 (bmap->linear & (HAMMER2_ALLOC_MIN - 1)) == 0); 658 offset = bmap->linear; 659 i = offset / (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS); 660 j = (offset / (HAMMER2_FREEMAP_BLOCK_SIZE / 2)) & 62; 661 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 662 HAMMER2_BMAP_ALLONES : 663 ((hammer2_bitmap_t)1 << bmradix) - 1; 664 bmmask <<= j; 665 bmap->linear = offset + size; 666 } else { 667 /* 668 * Try to index a starting point based on sub_key. This 669 * attempts to restore sequential block ordering on-disk 670 * whenever possible, even if data is committed out of 671 * order. 672 * 673 * i - Index bitmapq[], full data range represented is 674 * HAMMER2_BMAP_SIZE. 675 * 676 * j - Index within bitmapq[i], full data range represented is 677 * HAMMER2_BMAP_INDEX_SIZE. 678 * 679 * WARNING! 680 */ 681 i = -1; 682 j = -1; 683 684 switch(class >> 8) { 685 case HAMMER2_BREF_TYPE_DATA: 686 if (radix >= HAMMER2_FREEMAP_BLOCK_RADIX) { 687 i = (sub_key & HAMMER2_BMAP_MASK) / 688 (HAMMER2_BMAP_SIZE / HAMMER2_BMAP_ELEMENTS); 689 j = (sub_key & HAMMER2_BMAP_INDEX_MASK) / 690 (HAMMER2_BMAP_INDEX_SIZE / 691 HAMMER2_BMAP_BLOCKS_PER_ELEMENT); 692 j = j * 2; 693 } 694 break; 695 case HAMMER2_BREF_TYPE_INODE: 696 break; 697 default: 698 break; 699 } 700 if (i >= 0) { 701 KKASSERT(i < HAMMER2_BMAP_ELEMENTS && 702 j < 2 * HAMMER2_BMAP_BLOCKS_PER_ELEMENT); 703 KKASSERT(j + bmradix <= HAMMER2_BMAP_BITS_PER_ELEMENT); 704 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 705 HAMMER2_BMAP_ALLONES : 706 ((hammer2_bitmap_t)1 << bmradix) - 1; 707 bmmask <<= j; 708 709 if ((bmap->bitmapq[i] & bmmask) == 0) 710 goto success; 711 } 712 713 /* 714 * General element scan. 715 * 716 * WARNING: (j) is iterating a bit index (by 2's) 717 */ 718 for (i = 0; i < HAMMER2_BMAP_ELEMENTS; ++i) { 719 bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 720 HAMMER2_BMAP_ALLONES : 721 ((hammer2_bitmap_t)1 << bmradix) - 1; 722 for (j = 0; 723 j < HAMMER2_BMAP_BITS_PER_ELEMENT; 724 j += bmradix) { 725 if ((bmap->bitmapq[i] & bmmask) == 0) 726 goto success; 727 bmmask <<= bmradix; 728 } 729 } 730 /*fragments might remain*/ 731 /*KKASSERT(bmap->avail == 0);*/ 732 return (HAMMER2_ERROR_ENOSPC); 733 success: 734 offset = i * (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS) + 735 (j * (HAMMER2_FREEMAP_BLOCK_SIZE / 2)); 736 if (size & HAMMER2_FREEMAP_BLOCK_MASK) 737 bmap->linear = offset + size; 738 } 739 740 /* 8 x (64/2) -> 256 x 16K -> 4MB */ 741 KKASSERT(i >= 0 && i < HAMMER2_BMAP_ELEMENTS); 742 743 /* 744 * Optimize the buffer cache to avoid unnecessary read-before-write 745 * operations. 746 * 747 * The device block size could be larger than the allocation size 748 * so the actual bitmap test is somewhat more involved. We have 749 * to use a compatible buffer size for this operation. 750 */ 751 if ((bmap->bitmapq[i] & bmmask) == 0 && 752 hammer2_devblksize(size) != size) { 753 size_t psize = hammer2_devblksize(size); 754 hammer2_off_t pmask = (hammer2_off_t)psize - 1; 755 int pbmradix = (hammer2_bitmap_t)2 << 756 (hammer2_devblkradix(radix) - 757 HAMMER2_FREEMAP_BLOCK_RADIX); 758 hammer2_bitmap_t pbmmask; 759 int pradix = hammer2_getradix(psize); 760 761 pbmmask = (pbmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 762 HAMMER2_BMAP_ALLONES : 763 ((hammer2_bitmap_t)1 << pbmradix) - 1; 764 while ((pbmmask & bmmask) == 0) 765 pbmmask <<= pbmradix; 766 767 #if 0 768 kprintf("%016jx mask %016jx %016jx %016jx (%zd/%zd)\n", 769 *basep + offset, bmap->bitmapq[i], 770 pbmmask, bmmask, size, psize); 771 #endif 772 773 if ((bmap->bitmapq[i] & pbmmask) == 0) { 774 hammer2_io_t *dio; 775 776 hammer2_io_newnz(hmp, class >> 8, 777 (*basep + (offset & ~pmask)) | 778 pradix, psize, &dio); 779 hammer2_io_putblk(&dio); 780 } 781 } 782 783 #if 0 784 /* 785 * When initializing a new inode segment also attempt to initialize 786 * an adjacent segment. Be careful not to index beyond the array 787 * bounds. 788 * 789 * We do this to try to localize inode accesses to improve 790 * directory scan rates. XXX doesn't improve scan rates. 791 */ 792 if (size == HAMMER2_INODE_BYTES) { 793 if (n & 1) { 794 if (bmap[-1].radix == 0 && bmap[-1].avail) 795 bmap[-1].radix = radix; 796 } else { 797 if (bmap[1].radix == 0 && bmap[1].avail) 798 bmap[1].radix = radix; 799 } 800 } 801 #endif 802 /* 803 * Calculate the bitmap-granular change in bgsize for the volume 804 * header. We cannot use the fine-grained change here because 805 * the bulkfree code can't undo it. If the bitmap element is already 806 * marked allocated it has already been accounted for. 807 */ 808 if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 809 if (bmap->bitmapq[i] & bmmask) 810 bgsize = 0; 811 else 812 bgsize = HAMMER2_FREEMAP_BLOCK_SIZE; 813 } else { 814 bgsize = size; 815 } 816 817 /* 818 * Adjust the bitmap, set the class (it might have been 0), 819 * and available bytes, update the allocation offset (*basep) 820 * from the L0 base to the actual offset. 821 * 822 * Do not override the class if doing a relaxed class allocation. 823 * 824 * avail must reflect the bitmap-granular availability. The allocator 825 * tests will also check the linear iterator. 826 */ 827 bmap->bitmapq[i] |= bmmask; 828 if (bmap->class == 0) 829 bmap->class = class; 830 bmap->avail -= bgsize; 831 *basep += offset; 832 833 /* 834 * Adjust the volume header's allocator_free parameter. This 835 * parameter has to be fixed up by bulkfree which has no way to 836 * figure out sub-16K chunking, so it must be adjusted by the 837 * bitmap-granular size. 838 */ 839 if (bgsize) { 840 hammer2_voldata_lock(hmp); 841 hammer2_voldata_modify(hmp); 842 hmp->voldata.allocator_free -= bgsize; 843 hammer2_voldata_unlock(hmp); 844 } 845 846 return(0); 847 } 848 849 /* 850 * Initialize a freemap for the storage area (in bytes) that begins at (key). 851 */ 852 static 853 void 854 hammer2_freemap_init(hammer2_dev_t *hmp, hammer2_key_t key, 855 hammer2_chain_t *chain) 856 { 857 hammer2_off_t l1size; 858 hammer2_off_t lokey; 859 hammer2_off_t hikey; 860 hammer2_bmap_data_t *bmap; 861 int count; 862 863 /* 864 * LEVEL1 is 1GB, there are two level1 1GB freemaps per 2GB zone. 865 */ 866 l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 867 868 /* 869 * Calculate the portion of the 1GB map that should be initialized 870 * as free. Portions below or after will be initialized as allocated. 871 * SEGMASK-align the areas so we don't have to worry about sub-scans 872 * or endianess when using memset. 873 * 874 * WARNING! It is possible for lokey to be larger than hikey if the 875 * entire 2GB segment is within the static allocation. 876 */ 877 /* 878 * (1) Ensure that all statically allocated space from newfs_hammer2 879 * is marked allocated, and take it up to the level1 base for 880 * this key. 881 */ 882 lokey = (hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) & 883 ~HAMMER2_SEGMASK64; 884 if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX)) 885 lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX); 886 887 /* 888 * (2) Ensure that the reserved area is marked allocated (typically 889 * the first 4MB of each 2GB area being represented). Since 890 * each LEAF represents 1GB of storage and the zone is 2GB, we 891 * have to adjust lowkey upward every other LEAF sequentially. 892 */ 893 if (lokey < H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64) 894 lokey = H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64; 895 896 /* 897 * (3) Ensure that any trailing space at the end-of-volume is marked 898 * allocated. 899 */ 900 hikey = key + H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 901 if (hikey > hmp->voldata.volu_size) { 902 hikey = hmp->voldata.volu_size & ~HAMMER2_SEGMASK64; 903 } 904 905 /* 906 * Heuristic highest possible value 907 */ 908 chain->bref.check.freemap.avail = 909 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 910 bmap = &chain->data->bmdata[0]; 911 912 /* 913 * Initialize bitmap (bzero'd by caller) 914 */ 915 for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) { 916 if (key < lokey || key >= hikey) { 917 memset(bmap->bitmapq, -1, 918 sizeof(bmap->bitmapq)); 919 bmap->avail = 0; 920 bmap->linear = HAMMER2_SEGSIZE; 921 chain->bref.check.freemap.avail -= 922 H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 923 } else { 924 bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 925 } 926 key += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 927 ++bmap; 928 } 929 } 930 931 /* 932 * The current Level 1 freemap has been exhausted, iterate to the next 933 * one, return ENOSPC if no freemaps remain. 934 * 935 * At least two loops are required. If we are not in relaxed mode and 936 * we run out of storage we enter relaxed mode and do a third loop. 937 * The relaxed mode is recorded back in the hmp so once we enter the mode 938 * we remain relaxed until stuff begins to get freed and only do 2 loops. 939 * 940 * XXX this should rotate back to the beginning to handle freed-up space 941 * XXX or use intermediate entries to locate free space. TODO 942 */ 943 static int 944 hammer2_freemap_iterate(hammer2_chain_t **parentp, hammer2_chain_t **chainp, 945 hammer2_fiterate_t *iter) 946 { 947 hammer2_dev_t *hmp = (*parentp)->hmp; 948 949 iter->bnext &= ~(H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX) - 1); 950 iter->bnext += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 951 if (iter->bnext >= hmp->voldata.volu_size) { 952 iter->bnext = 0; 953 if (++iter->loops >= 2) { 954 if (iter->relaxed == 0) 955 iter->relaxed = 1; 956 else 957 return (HAMMER2_ERROR_ENOSPC); 958 } 959 } 960 return(HAMMER2_ERROR_EAGAIN); 961 } 962 963 /* 964 * Adjust the bit-pattern for data in the freemap bitmap according to 965 * (how). This code is called from on-mount recovery to fixup (mark 966 * as allocated) blocks whos freemap upates might not have been committed 967 * in the last crash and is used by the bulk freemap scan to stage frees. 968 * 969 * WARNING! Cannot be called with a empty-data bref (radix == 0). 970 * 971 * XXX currently disabled when how == 0 (the normal real-time case). At 972 * the moment we depend on the bulk freescan to actually free blocks. It 973 * will still call this routine with a non-zero how to stage possible frees 974 * and to do the actual free. 975 */ 976 void 977 hammer2_freemap_adjust(hammer2_dev_t *hmp, hammer2_blockref_t *bref, 978 int how) 979 { 980 hammer2_off_t data_off = bref->data_off; 981 hammer2_chain_t *chain; 982 hammer2_chain_t *parent; 983 hammer2_bmap_data_t *bmap; 984 hammer2_key_t key; 985 hammer2_key_t key_dummy; 986 hammer2_off_t l0size; 987 hammer2_off_t l1size; 988 hammer2_off_t l1mask; 989 hammer2_tid_t mtid; 990 hammer2_bitmap_t *bitmap; 991 const hammer2_bitmap_t bmmask00 = 0; 992 hammer2_bitmap_t bmmask01; 993 hammer2_bitmap_t bmmask10; 994 hammer2_bitmap_t bmmask11; 995 size_t bytes; 996 uint16_t class; 997 int radix; 998 int start; 999 int count; 1000 int modified = 0; 1001 int error; 1002 size_t bgsize = 0; 1003 1004 KKASSERT(how == HAMMER2_FREEMAP_DORECOVER); 1005 1006 KKASSERT(hmp->spmp); 1007 mtid = hammer2_trans_sub(hmp->spmp); 1008 1009 radix = (int)data_off & HAMMER2_OFF_MASK_RADIX; 1010 KKASSERT(radix != 0); 1011 data_off &= ~HAMMER2_OFF_MASK_RADIX; 1012 KKASSERT(radix <= HAMMER2_RADIX_MAX); 1013 1014 if (radix) 1015 bytes = (size_t)1 << radix; 1016 else 1017 bytes = 0; 1018 class = (bref->type << 8) | hammer2_devblkradix(radix); 1019 1020 /* 1021 * We can't adjust the freemap for data allocations made by 1022 * newfs_hammer2. 1023 */ 1024 if (data_off < hmp->voldata.allocator_beg) 1025 return; 1026 1027 KKASSERT((data_off & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG); 1028 1029 /* 1030 * Lookup the level1 freemap chain. The chain must exist. 1031 */ 1032 key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL1_RADIX); 1033 l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 1034 l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 1035 l1mask = l1size - 1; 1036 1037 parent = &hmp->fchain; 1038 hammer2_chain_ref(parent); 1039 hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS); 1040 1041 chain = hammer2_chain_lookup(&parent, &key_dummy, key, key + l1mask, 1042 &error, 1043 HAMMER2_LOOKUP_ALWAYS | 1044 HAMMER2_LOOKUP_MATCHIND); 1045 1046 /* 1047 * Stop early if we are trying to free something but no leaf exists. 1048 */ 1049 if (chain == NULL && how != HAMMER2_FREEMAP_DORECOVER) { 1050 kprintf("hammer2_freemap_adjust: %016jx: no chain\n", 1051 (intmax_t)bref->data_off); 1052 goto done; 1053 } 1054 if (chain->error) { 1055 kprintf("hammer2_freemap_adjust: %016jx: error %s\n", 1056 (intmax_t)bref->data_off, 1057 hammer2_error_str(chain->error)); 1058 hammer2_chain_unlock(chain); 1059 hammer2_chain_drop(chain); 1060 chain = NULL; 1061 goto done; 1062 } 1063 1064 /* 1065 * Create any missing leaf(s) if we are doing a recovery (marking 1066 * the block(s) as being allocated instead of being freed). Be sure 1067 * to initialize the auxillary freemap tracking info in the 1068 * bref.check.freemap structure. 1069 */ 1070 if (chain == NULL && how == HAMMER2_FREEMAP_DORECOVER) { 1071 error = hammer2_chain_create(&parent, &chain, NULL, hmp->spmp, 1072 HAMMER2_METH_DEFAULT, 1073 key, HAMMER2_FREEMAP_LEVEL1_RADIX, 1074 HAMMER2_BREF_TYPE_FREEMAP_LEAF, 1075 HAMMER2_FREEMAP_LEVELN_PSIZE, 1076 mtid, 0, 0); 1077 1078 if (hammer2_debug & 0x0040) { 1079 kprintf("fixup create chain %p %016jx:%d\n", 1080 chain, chain->bref.key, chain->bref.keybits); 1081 } 1082 1083 if (error == 0) { 1084 error = hammer2_chain_modify(chain, mtid, 0, 0); 1085 KKASSERT(error == 0); 1086 bzero(&chain->data->bmdata[0], 1087 HAMMER2_FREEMAP_LEVELN_PSIZE); 1088 chain->bref.check.freemap.bigmask = (uint32_t)-1; 1089 chain->bref.check.freemap.avail = l1size; 1090 /* bref.methods should already be inherited */ 1091 1092 hammer2_freemap_init(hmp, key, chain); 1093 } 1094 /* XXX handle error */ 1095 } 1096 1097 #if FREEMAP_DEBUG 1098 kprintf("FREEMAP ADJUST TYPE %d %016jx/%d DATA_OFF=%016jx\n", 1099 chain->bref.type, chain->bref.key, 1100 chain->bref.keybits, chain->bref.data_off); 1101 #endif 1102 1103 /* 1104 * Calculate the bitmask (runs in 2-bit pairs). 1105 */ 1106 start = ((int)(data_off >> HAMMER2_FREEMAP_BLOCK_RADIX) & 15) * 2; 1107 bmmask01 = (hammer2_bitmap_t)1 << start; 1108 bmmask10 = (hammer2_bitmap_t)2 << start; 1109 bmmask11 = (hammer2_bitmap_t)3 << start; 1110 1111 /* 1112 * Fixup the bitmap. Partial blocks cannot be fully freed unless 1113 * a bulk scan is able to roll them up. 1114 */ 1115 if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 1116 count = 1; 1117 if (how == HAMMER2_FREEMAP_DOREALFREE) 1118 how = HAMMER2_FREEMAP_DOMAYFREE; 1119 } else { 1120 count = 1 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX); 1121 } 1122 1123 /* 1124 * [re]load the bmap and bitmap pointers. Each bmap entry covers 1125 * a 4MB swath. The bmap itself (LEVEL1) covers 2GB. 1126 * 1127 * Be sure to reset the linear iterator to ensure that the adjustment 1128 * is not ignored. 1129 */ 1130 again: 1131 bmap = &chain->data->bmdata[(int)(data_off >> HAMMER2_SEGRADIX) & 1132 (HAMMER2_FREEMAP_COUNT - 1)]; 1133 bitmap = &bmap->bitmapq[(int)(data_off >> (HAMMER2_SEGRADIX - 3)) & 7]; 1134 1135 if (modified) 1136 bmap->linear = 0; 1137 1138 while (count) { 1139 KKASSERT(bmmask11); 1140 if (how == HAMMER2_FREEMAP_DORECOVER) { 1141 /* 1142 * Recovery request, mark as allocated. 1143 */ 1144 if ((*bitmap & bmmask11) != bmmask11) { 1145 if (modified == 0) { 1146 hammer2_chain_modify(chain, mtid, 0, 0); 1147 modified = 1; 1148 goto again; 1149 } 1150 if ((*bitmap & bmmask11) == bmmask00) { 1151 bmap->avail -= 1152 HAMMER2_FREEMAP_BLOCK_SIZE; 1153 bgsize += HAMMER2_FREEMAP_BLOCK_SIZE; 1154 } 1155 if (bmap->class == 0) 1156 bmap->class = class; 1157 *bitmap |= bmmask11; 1158 if (hammer2_debug & 0x0040) { 1159 kprintf("hammer2_freemap_recover: " 1160 "fixup type=%02x " 1161 "block=%016jx/%zd\n", 1162 bref->type, data_off, bytes); 1163 } 1164 } else { 1165 /* 1166 kprintf("hammer2_freemap_recover: good " 1167 "type=%02x block=%016jx/%zd\n", 1168 bref->type, data_off, bytes); 1169 */ 1170 } 1171 } 1172 #if 0 1173 /* 1174 * XXX this stuff doesn't work, avail is miscalculated and 1175 * code 10 means something else now. 1176 */ 1177 else if ((*bitmap & bmmask11) == bmmask11) { 1178 /* 1179 * Mayfree/Realfree request and bitmap is currently 1180 * marked as being fully allocated. 1181 */ 1182 if (!modified) { 1183 hammer2_chain_modify(chain, 0); 1184 modified = 1; 1185 goto again; 1186 } 1187 if (how == HAMMER2_FREEMAP_DOREALFREE) 1188 *bitmap &= ~bmmask11; 1189 else 1190 *bitmap = (*bitmap & ~bmmask11) | bmmask10; 1191 } else if ((*bitmap & bmmask11) == bmmask10) { 1192 /* 1193 * Mayfree/Realfree request and bitmap is currently 1194 * marked as being possibly freeable. 1195 */ 1196 if (how == HAMMER2_FREEMAP_DOREALFREE) { 1197 if (!modified) { 1198 hammer2_chain_modify(chain, 0); 1199 modified = 1; 1200 goto again; 1201 } 1202 *bitmap &= ~bmmask11; 1203 } 1204 } else { 1205 /* 1206 * 01 - Not implemented, currently illegal state 1207 * 00 - Not allocated at all, illegal free. 1208 */ 1209 panic("hammer2_freemap_adjust: " 1210 "Illegal state %08x(%08x)", 1211 *bitmap, *bitmap & bmmask11); 1212 } 1213 #endif 1214 --count; 1215 bmmask01 <<= 2; 1216 bmmask10 <<= 2; 1217 bmmask11 <<= 2; 1218 } 1219 #if HAMMER2_BMAP_ELEMENTS != 8 1220 #error "hammer2_freemap.c: HAMMER2_BMAP_ELEMENTS expected to be 8" 1221 #endif 1222 if (how == HAMMER2_FREEMAP_DOREALFREE && modified) { 1223 bmap->avail += 1 << radix; 1224 KKASSERT(bmap->avail <= HAMMER2_SEGSIZE); 1225 if (bmap->avail == HAMMER2_SEGSIZE && 1226 bmap->bitmapq[0] == 0 && 1227 bmap->bitmapq[1] == 0 && 1228 bmap->bitmapq[2] == 0 && 1229 bmap->bitmapq[3] == 0 && 1230 bmap->bitmapq[4] == 0 && 1231 bmap->bitmapq[5] == 0 && 1232 bmap->bitmapq[6] == 0 && 1233 bmap->bitmapq[7] == 0) { 1234 key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL0_RADIX); 1235 kprintf("Freeseg %016jx\n", (intmax_t)key); 1236 bmap->class = 0; 1237 } 1238 } 1239 1240 /* 1241 * chain->bref.check.freemap.bigmask (XXX) 1242 * 1243 * Setting bigmask is a hint to the allocation code that there might 1244 * be something allocatable. We also set this in recovery... it 1245 * doesn't hurt and we might want to use the hint for other validation 1246 * operations later on. 1247 * 1248 * We could calculate the largest possible allocation and set the 1249 * radii that could fit, but its easier just to set bigmask to -1. 1250 */ 1251 if (modified) { 1252 chain->bref.check.freemap.bigmask = -1; 1253 hmp->freemap_relaxed = 0; /* reset heuristic */ 1254 } 1255 1256 hammer2_chain_unlock(chain); 1257 hammer2_chain_drop(chain); 1258 done: 1259 hammer2_chain_unlock(parent); 1260 hammer2_chain_drop(parent); 1261 1262 if (bgsize) { 1263 hammer2_voldata_lock(hmp); 1264 hammer2_voldata_modify(hmp); 1265 hmp->voldata.allocator_free -= bgsize; 1266 hammer2_voldata_unlock(hmp); 1267 } 1268 } 1269 1270 /* 1271 * Validate the freemap, in three stages. 1272 * 1273 * stage-1 ALLOCATED -> POSSIBLY FREE 1274 * POSSIBLY FREE -> POSSIBLY FREE (type corrected) 1275 * 1276 * This transitions bitmap entries from ALLOCATED to POSSIBLY FREE. 1277 * The POSSIBLY FREE state does not mean that a block is actually free 1278 * and may be transitioned back to ALLOCATED in stage-2. 1279 * 1280 * This is typically done during normal filesystem operations when 1281 * something is deleted or a block is replaced. 1282 * 1283 * This is done by bulkfree in-bulk after a memory-bounded meta-data 1284 * scan to try to determine what might be freeable. 1285 * 1286 * This can be done unconditionally through a freemap scan when the 1287 * intention is to brute-force recover the proper state of the freemap. 1288 * 1289 * stage-2 POSSIBLY FREE -> ALLOCATED (scan metadata topology) 1290 * 1291 * This is done by bulkfree during a meta-data scan to ensure that 1292 * all blocks still actually allocated by the filesystem are marked 1293 * as such. 1294 * 1295 * NOTE! Live filesystem transitions to POSSIBLY FREE can occur while 1296 * the bulkfree stage-2 and stage-3 is running. The live filesystem 1297 * will use the alternative POSSIBLY FREE type (2) to prevent 1298 * stage-3 from improperly transitioning unvetted possibly-free 1299 * blocks to FREE. 1300 * 1301 * stage-3 POSSIBLY FREE (type 1) -> FREE (scan freemap) 1302 * 1303 * This is done by bulkfree to finalize POSSIBLY FREE states. 1304 * 1305 */ 1306