1 /* 2 * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting 3 * 4 * Copyright (c) 1998,2004 The DragonFly Project. All rights reserved. 5 * 6 * This code is derived from software contributed to The DragonFly Project 7 * by Matthew Dillon <dillon@backplane.com> 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 3. Neither the name of The DragonFly Project nor the names of its 20 * contributors may be used to endorse or promote products derived 21 * from this software without specific, prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * 37 * This module implements a general bitmap allocator/deallocator. The 38 * allocator eats around 2 bits per 'block'. The module does not 39 * try to interpret the meaning of a 'block' other then to return 40 * SWAPBLK_NONE on an allocation failure. 41 * 42 * A radix tree is used to maintain the bitmap. Two radix constants are 43 * involved: One for the bitmaps contained in the leaf nodes (typically 44 * 32), and one for the meta nodes (typically 16). Both meta and leaf 45 * nodes have a hint field. This field gives us a hint as to the largest 46 * free contiguous range of blocks under the node. It may contain a 47 * value that is too high, but will never contain a value that is too 48 * low. When the radix tree is searched, allocation failures in subtrees 49 * update the hint. 50 * 51 * The radix tree also implements two collapsed states for meta nodes: 52 * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is 53 * in either of these two states, all information contained underneath 54 * the node is considered stale. These states are used to optimize 55 * allocation and freeing operations. 56 * 57 * The hinting greatly increases code efficiency for allocations while 58 * the general radix structure optimizes both allocations and frees. The 59 * radix tree should be able to operate well no matter how much 60 * fragmentation there is and no matter how large a bitmap is used. 61 * 62 * Unlike the rlist code, the blist code wires all necessary memory at 63 * creation time. Neither allocations nor frees require interaction with 64 * the memory subsystem. In contrast, the rlist code may allocate memory 65 * on an rlist_free() call. The non-blocking features of the blist code 66 * are used to great advantage in the swap code (vm/nswap_pager.c). The 67 * rlist code uses a little less overall memory then the blist code (but 68 * due to swap interleaving not all that much less), but the blist code 69 * scales much, much better. 70 * 71 * LAYOUT: The radix tree is layed out recursively using a 72 * linear array. Each meta node is immediately followed (layed out 73 * sequentially in memory) by BLIST_META_RADIX lower level nodes. This 74 * is a recursive structure but one that can be easily scanned through 75 * a very simple 'skip' calculation. In order to support large radixes, 76 * portions of the tree may reside outside our memory allocation. We 77 * handle this with an early-termination optimization (when bighint is 78 * set to -1) on the scan. The memory allocation is only large enough 79 * to cover the number of blocks requested at creation time even if it 80 * must be encompassed in larger root-node radix. 81 * 82 * NOTE: The allocator cannot currently allocate more then 83 * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too 84 * large' if you try. This is an area that could use improvement. The 85 * radix is large enough that this restriction does not effect the swap 86 * system, though. Currently only the allocation code is effected by 87 * this algorithmic unfeature. The freeing code can handle arbitrary 88 * ranges. 89 * 90 * NOTE: The radix may exceed 32 bits in order to support up to 2^31 91 * blocks. The first divison will drop the radix down and fit 92 * it within a signed 32 bit integer. 93 * 94 * This code can be compiled stand-alone for debugging. 95 */ 96 97 #ifdef _KERNEL 98 99 #include <sys/param.h> 100 #include <sys/systm.h> 101 #include <sys/lock.h> 102 #include <sys/kernel.h> 103 #include <sys/blist.h> 104 #include <sys/malloc.h> 105 106 #else 107 108 #ifndef BLIST_NO_DEBUG 109 #define BLIST_DEBUG 110 #endif 111 112 #define SWAPBLK_NONE ((swblk_t)-1) 113 114 #include <sys/types.h> 115 #include <stdio.h> 116 #include <string.h> 117 #include <stdlib.h> 118 #include <stdarg.h> 119 120 #define kmalloc(a,b,c) malloc(a) 121 #define kfree(a,b) free(a) 122 #define kprintf printf 123 #define KKASSERT(exp) 124 125 #include <sys/blist.h> 126 127 void panic(const char *ctl, ...); 128 129 #endif 130 131 /* 132 * static support functions 133 */ 134 135 static swblk_t blst_leaf_alloc(blmeta_t *scan, swblk_t blk, int count); 136 static swblk_t blst_meta_alloc(blmeta_t *scan, swblk_t blk, 137 swblk_t count, int64_t radix, int skip); 138 static void blst_leaf_free(blmeta_t *scan, swblk_t relblk, int count); 139 static void blst_meta_free(blmeta_t *scan, swblk_t freeBlk, swblk_t count, 140 int64_t radix, int skip, swblk_t blk); 141 static swblk_t blst_leaf_fill(blmeta_t *scan, swblk_t blk, int count); 142 static swblk_t blst_meta_fill(blmeta_t *scan, swblk_t fillBlk, swblk_t count, 143 int64_t radix, int skip, swblk_t blk); 144 static void blst_copy(blmeta_t *scan, swblk_t blk, int64_t radix, 145 swblk_t skip, blist_t dest, swblk_t count); 146 static swblk_t blst_radix_init(blmeta_t *scan, int64_t radix, 147 int skip, swblk_t count); 148 #ifndef _KERNEL 149 static void blst_radix_print(blmeta_t *scan, swblk_t blk, 150 int64_t radix, int skip, int tab); 151 #endif 152 153 #ifdef _KERNEL 154 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); 155 #endif 156 157 /* 158 * blist_create() - create a blist capable of handling up to the specified 159 * number of blocks 160 * 161 * blocks must be greater then 0 162 * 163 * The smallest blist consists of a single leaf node capable of 164 * managing BLIST_BMAP_RADIX blocks. 165 */ 166 167 blist_t 168 blist_create(swblk_t blocks) 169 { 170 blist_t bl; 171 int64_t radix; 172 int skip = 0; 173 174 /* 175 * Calculate radix and skip field used for scanning. 176 * 177 * Radix can exceed 32 bits even if swblk_t is limited to 32 bits. 178 */ 179 radix = BLIST_BMAP_RADIX; 180 181 while (radix < blocks) { 182 radix *= BLIST_META_RADIX; 183 skip = (skip + 1) * BLIST_META_RADIX; 184 KKASSERT(skip > 0); 185 } 186 187 bl = kmalloc(sizeof(struct blist), M_SWAP, M_WAITOK | M_ZERO); 188 189 bl->bl_blocks = blocks; 190 bl->bl_radix = radix; 191 bl->bl_skip = skip; 192 bl->bl_rootblks = 1 + 193 blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 194 bl->bl_root = kmalloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, M_WAITOK); 195 196 #if defined(BLIST_DEBUG) 197 kprintf( 198 "BLIST representing %d blocks (%d MB of swap)" 199 ", requiring %dK of ram\n", 200 bl->bl_blocks, 201 bl->bl_blocks * 4 / 1024, 202 (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 203 ); 204 kprintf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks); 205 #endif 206 blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 207 208 return(bl); 209 } 210 211 void 212 blist_destroy(blist_t bl) 213 { 214 kfree(bl->bl_root, M_SWAP); 215 kfree(bl, M_SWAP); 216 } 217 218 /* 219 * blist_alloc() - reserve space in the block bitmap. Return the base 220 * of a contiguous region or SWAPBLK_NONE if space could 221 * not be allocated. 222 */ 223 224 swblk_t 225 blist_alloc(blist_t bl, swblk_t count) 226 { 227 swblk_t blk = SWAPBLK_NONE; 228 229 if (bl) { 230 if (bl->bl_radix == BLIST_BMAP_RADIX) 231 blk = blst_leaf_alloc(bl->bl_root, 0, count); 232 else 233 blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 234 if (blk != SWAPBLK_NONE) 235 bl->bl_free -= count; 236 } 237 return(blk); 238 } 239 240 /* 241 * blist_free() - free up space in the block bitmap. Return the base 242 * of a contiguous region. Panic if an inconsistancy is 243 * found. 244 */ 245 246 void 247 blist_free(blist_t bl, swblk_t blkno, swblk_t count) 248 { 249 if (bl) { 250 if (bl->bl_radix == BLIST_BMAP_RADIX) 251 blst_leaf_free(bl->bl_root, blkno, count); 252 else 253 blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 254 bl->bl_free += count; 255 } 256 } 257 258 /* 259 * blist_fill() - mark a region in the block bitmap as off-limits 260 * to the allocator (i.e. allocate it), ignoring any 261 * existing allocations. Return the number of blocks 262 * actually filled that were free before the call. 263 */ 264 265 swblk_t 266 blist_fill(blist_t bl, swblk_t blkno, swblk_t count) 267 { 268 swblk_t filled; 269 270 if (bl) { 271 if (bl->bl_radix == BLIST_BMAP_RADIX) { 272 filled = blst_leaf_fill(bl->bl_root, blkno, count); 273 } else { 274 filled = blst_meta_fill(bl->bl_root, blkno, count, 275 bl->bl_radix, bl->bl_skip, 0); 276 } 277 bl->bl_free -= filled; 278 return (filled); 279 } else { 280 return 0; 281 } 282 } 283 284 /* 285 * blist_resize() - resize an existing radix tree to handle the 286 * specified number of blocks. This will reallocate 287 * the tree and transfer the previous bitmap to the new 288 * one. When extending the tree you can specify whether 289 * the new blocks are to left allocated or freed. 290 */ 291 292 void 293 blist_resize(blist_t *pbl, swblk_t count, int freenew) 294 { 295 blist_t newbl = blist_create(count); 296 blist_t save = *pbl; 297 298 *pbl = newbl; 299 if (count > save->bl_blocks) 300 count = save->bl_blocks; 301 blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 302 303 /* 304 * If resizing upwards, should we free the new space or not? 305 */ 306 if (freenew && count < newbl->bl_blocks) { 307 blist_free(newbl, count, newbl->bl_blocks - count); 308 } 309 blist_destroy(save); 310 } 311 312 #ifdef BLIST_DEBUG 313 314 /* 315 * blist_print() - dump radix tree 316 */ 317 318 void 319 blist_print(blist_t bl) 320 { 321 kprintf("BLIST {\n"); 322 blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 323 kprintf("}\n"); 324 } 325 326 #endif 327 328 /************************************************************************ 329 * ALLOCATION SUPPORT FUNCTIONS * 330 ************************************************************************ 331 * 332 * These support functions do all the actual work. They may seem 333 * rather longish, but that's because I've commented them up. The 334 * actual code is straight forward. 335 * 336 */ 337 338 /* 339 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 340 * 341 * This is the core of the allocator and is optimized for the 1 block 342 * and the BLIST_BMAP_RADIX block allocation cases. Other cases are 343 * somewhat slower. The 1 block allocation case is log2 and extremely 344 * quick. 345 */ 346 347 static swblk_t 348 blst_leaf_alloc(blmeta_t *scan, swblk_t blk, int count) 349 { 350 u_swblk_t orig = scan->u.bmu_bitmap; 351 352 if (orig == 0) { 353 /* 354 * Optimize bitmap all-allocated case. Also, count = 1 355 * case assumes at least 1 bit is free in the bitmap, so 356 * we have to take care of this case here. 357 */ 358 scan->bm_bighint = 0; 359 return(SWAPBLK_NONE); 360 } 361 if (count == 1) { 362 /* 363 * Optimized code to allocate one bit out of the bitmap 364 */ 365 u_swblk_t mask; 366 int j = BLIST_BMAP_RADIX/2; 367 int r = 0; 368 369 mask = (u_swblk_t)-1 >> (BLIST_BMAP_RADIX/2); 370 371 while (j) { 372 if ((orig & mask) == 0) { 373 r += j; 374 orig >>= j; 375 } 376 j >>= 1; 377 mask >>= j; 378 } 379 scan->u.bmu_bitmap &= ~(1 << r); 380 return(blk + r); 381 } 382 if (count <= BLIST_BMAP_RADIX) { 383 /* 384 * non-optimized code to allocate N bits out of the bitmap. 385 * The more bits, the faster the code runs. It will run 386 * the slowest allocating 2 bits, but since there aren't any 387 * memory ops in the core loop (or shouldn't be, anyway), 388 * you probably won't notice the difference. 389 */ 390 int j; 391 int n = BLIST_BMAP_RADIX - count; 392 u_swblk_t mask; 393 394 mask = (u_swblk_t)-1 >> n; 395 396 for (j = 0; j <= n; ++j) { 397 if ((orig & mask) == mask) { 398 scan->u.bmu_bitmap &= ~mask; 399 return(blk + j); 400 } 401 mask = (mask << 1); 402 } 403 } 404 /* 405 * We couldn't allocate count in this subtree, update bighint. 406 */ 407 scan->bm_bighint = count - 1; 408 return(SWAPBLK_NONE); 409 } 410 411 /* 412 * blist_meta_alloc() - allocate at a meta in the radix tree. 413 * 414 * Attempt to allocate at a meta node. If we can't, we update 415 * bighint and return a failure. Updating bighint optimize future 416 * calls that hit this node. We have to check for our collapse cases 417 * and we have a few optimizations strewn in as well. 418 */ 419 static swblk_t 420 blst_meta_alloc(blmeta_t *scan, swblk_t blk, swblk_t count, 421 int64_t radix, int skip) 422 { 423 int i; 424 int next_skip = ((u_int)skip / BLIST_META_RADIX); 425 426 /* 427 * ALL-ALLOCATED special case 428 */ 429 if (scan->u.bmu_avail == 0) { 430 scan->bm_bighint = 0; 431 return(SWAPBLK_NONE); 432 } 433 434 /* 435 * ALL-FREE special case, initialize uninitialized 436 * sublevel. 437 * 438 * NOTE: radix may exceed 32 bits until first division. 439 */ 440 if (scan->u.bmu_avail == radix) { 441 scan->bm_bighint = radix; 442 443 radix /= BLIST_META_RADIX; 444 for (i = 1; i <= skip; i += next_skip) { 445 if (scan[i].bm_bighint == (swblk_t)-1) 446 break; 447 if (next_skip == 1) { 448 scan[i].u.bmu_bitmap = (u_swblk_t)-1; 449 scan[i].bm_bighint = BLIST_BMAP_RADIX; 450 } else { 451 scan[i].bm_bighint = (swblk_t)radix; 452 scan[i].u.bmu_avail = (swblk_t)radix; 453 } 454 } 455 } else { 456 radix /= BLIST_META_RADIX; 457 } 458 459 for (i = 1; i <= skip; i += next_skip) { 460 if (count <= scan[i].bm_bighint) { 461 /* 462 * count fits in object 463 */ 464 swblk_t r; 465 if (next_skip == 1) { 466 r = blst_leaf_alloc(&scan[i], blk, count); 467 } else { 468 r = blst_meta_alloc(&scan[i], blk, count, 469 radix, next_skip - 1); 470 } 471 if (r != SWAPBLK_NONE) { 472 scan->u.bmu_avail -= count; 473 if (scan->bm_bighint > scan->u.bmu_avail) 474 scan->bm_bighint = scan->u.bmu_avail; 475 return(r); 476 } 477 /* bighint was updated by recursion */ 478 } else if (scan[i].bm_bighint == (swblk_t)-1) { 479 /* 480 * Terminator 481 */ 482 break; 483 } else if (count > (swblk_t)radix) { 484 /* 485 * count does not fit in object even if it were 486 * complete free. 487 */ 488 panic("blist_meta_alloc: allocation too large"); 489 } 490 blk += (swblk_t)radix; 491 } 492 493 /* 494 * We couldn't allocate count in this subtree, update bighint. 495 */ 496 if (scan->bm_bighint >= count) 497 scan->bm_bighint = count - 1; 498 return(SWAPBLK_NONE); 499 } 500 501 /* 502 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 503 */ 504 static void 505 blst_leaf_free(blmeta_t *scan, swblk_t blk, int count) 506 { 507 /* 508 * free some data in this bitmap 509 * 510 * e.g. 511 * 0000111111111110000 512 * \_________/\__/ 513 * v n 514 */ 515 int n = blk & (BLIST_BMAP_RADIX - 1); 516 u_swblk_t mask; 517 518 mask = ((u_swblk_t)-1 << n) & 519 ((u_swblk_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 520 521 if (scan->u.bmu_bitmap & mask) 522 panic("blst_radix_free: freeing free block"); 523 scan->u.bmu_bitmap |= mask; 524 525 /* 526 * We could probably do a better job here. We are required to make 527 * bighint at least as large as the biggest contiguous block of 528 * data. If we just shoehorn it, a little extra overhead will 529 * be incured on the next allocation (but only that one typically). 530 */ 531 scan->bm_bighint = BLIST_BMAP_RADIX; 532 } 533 534 /* 535 * BLST_META_FREE() - free allocated blocks from radix tree meta info 536 * 537 * This support routine frees a range of blocks from the bitmap. 538 * The range must be entirely enclosed by this radix node. If a 539 * meta node, we break the range down recursively to free blocks 540 * in subnodes (which means that this code can free an arbitrary 541 * range whereas the allocation code cannot allocate an arbitrary 542 * range). 543 */ 544 545 static void 546 blst_meta_free(blmeta_t *scan, swblk_t freeBlk, swblk_t count, 547 int64_t radix, int skip, swblk_t blk) 548 { 549 int i; 550 int next_skip = ((u_int)skip / BLIST_META_RADIX); 551 552 #if 0 553 kprintf("FREE (%x,%d) FROM (%x,%lld)\n", 554 freeBlk, count, 555 blk, (long long)radix 556 ); 557 #endif 558 559 /* 560 * ALL-ALLOCATED special case, initialize for recursion. 561 * 562 * We will short-cut the ALL-ALLOCATED -> ALL-FREE case. 563 */ 564 if (scan->u.bmu_avail == 0) { 565 scan->u.bmu_avail = count; 566 scan->bm_bighint = count; 567 568 if (count != radix) { 569 for (i = 1; i <= skip; i += next_skip) { 570 if (scan[i].bm_bighint == (swblk_t)-1) 571 break; 572 scan[i].bm_bighint = 0; 573 if (next_skip == 1) { 574 scan[i].u.bmu_bitmap = 0; 575 } else { 576 scan[i].u.bmu_avail = 0; 577 } 578 } 579 /* fall through */ 580 } 581 } else { 582 scan->u.bmu_avail += count; 583 /* scan->bm_bighint = radix; */ 584 } 585 586 /* 587 * ALL-FREE special case. 588 * 589 * Set bighint for higher levels to snoop. 590 */ 591 if (scan->u.bmu_avail == radix) { 592 scan->bm_bighint = radix; 593 return; 594 } 595 596 /* 597 * Break the free down into its components 598 */ 599 if (scan->u.bmu_avail > radix) { 600 panic("blst_meta_free: freeing already " 601 "free blocks (%d) %d/%lld", 602 count, scan->u.bmu_avail, (long long)radix); 603 } 604 605 radix /= BLIST_META_RADIX; 606 607 i = (freeBlk - blk) / (swblk_t)radix; 608 blk += i * (swblk_t)radix; 609 i = i * next_skip + 1; 610 611 while (i <= skip && blk < freeBlk + count) { 612 swblk_t v; 613 614 v = blk + (swblk_t)radix - freeBlk; 615 if (v > count) 616 v = count; 617 618 if (scan->bm_bighint == (swblk_t)-1) 619 panic("blst_meta_free: freeing unexpected range"); 620 621 if (next_skip == 1) { 622 blst_leaf_free(&scan[i], freeBlk, v); 623 } else { 624 blst_meta_free(&scan[i], freeBlk, v, 625 radix, next_skip - 1, blk); 626 } 627 628 /* 629 * After having dealt with the becomes-all-free case any 630 * partial free will not be able to bring us to the 631 * becomes-all-free state. 632 * 633 * We can raise bighint to at least the sub-segment's 634 * bighint. 635 */ 636 if (scan->bm_bighint < scan[i].bm_bighint) { 637 scan->bm_bighint = scan[i].bm_bighint; 638 } 639 count -= v; 640 freeBlk += v; 641 blk += (swblk_t)radix; 642 i += next_skip; 643 } 644 } 645 646 /* 647 * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap 648 * 649 * Allocates all blocks in the specified range regardless of 650 * any existing allocations in that range. Returns the number 651 * of blocks allocated by the call. 652 */ 653 static swblk_t 654 blst_leaf_fill(blmeta_t *scan, swblk_t blk, int count) 655 { 656 int n = blk & (BLIST_BMAP_RADIX - 1); 657 swblk_t nblks; 658 u_swblk_t mask, bitmap; 659 660 mask = ((u_swblk_t)-1 << n) & 661 ((u_swblk_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 662 663 /* Count the number of blocks we're about to allocate */ 664 bitmap = scan->u.bmu_bitmap & mask; 665 for (nblks = 0; bitmap != 0; nblks++) 666 bitmap &= bitmap - 1; 667 668 scan->u.bmu_bitmap &= ~mask; 669 return (nblks); 670 } 671 672 /* 673 * BLST_META_FILL() - allocate specific blocks at a meta node 674 * 675 * Allocates the specified range of blocks, regardless of 676 * any existing allocations in the range. The range must 677 * be within the extent of this node. Returns the number 678 * of blocks allocated by the call. 679 */ 680 static swblk_t 681 blst_meta_fill(blmeta_t *scan, swblk_t fillBlk, swblk_t count, 682 int64_t radix, int skip, swblk_t blk) 683 { 684 int i; 685 int next_skip = ((u_int)skip / BLIST_META_RADIX); 686 swblk_t nblks = 0; 687 688 if (count == radix || scan->u.bmu_avail == 0) { 689 /* 690 * ALL-ALLOCATED special case 691 */ 692 nblks = scan->u.bmu_avail; 693 scan->u.bmu_avail = 0; 694 scan->bm_bighint = count; 695 return (nblks); 696 } 697 698 if (scan->u.bmu_avail == radix) { 699 radix /= BLIST_META_RADIX; 700 701 /* 702 * ALL-FREE special case, initialize sublevel 703 */ 704 for (i = 1; i <= skip; i += next_skip) { 705 if (scan[i].bm_bighint == (swblk_t)-1) 706 break; 707 if (next_skip == 1) { 708 scan[i].u.bmu_bitmap = (u_swblk_t)-1; 709 scan[i].bm_bighint = BLIST_BMAP_RADIX; 710 } else { 711 scan[i].bm_bighint = (swblk_t)radix; 712 scan[i].u.bmu_avail = (swblk_t)radix; 713 } 714 } 715 } else { 716 radix /= BLIST_META_RADIX; 717 } 718 719 if (count > (swblk_t)radix) 720 panic("blst_meta_fill: allocation too large"); 721 722 i = (fillBlk - blk) / (swblk_t)radix; 723 blk += i * (swblk_t)radix; 724 i = i * next_skip + 1; 725 726 while (i <= skip && blk < fillBlk + count) { 727 swblk_t v; 728 729 v = blk + (swblk_t)radix - fillBlk; 730 if (v > count) 731 v = count; 732 733 if (scan->bm_bighint == (swblk_t)-1) 734 panic("blst_meta_fill: filling unexpected range"); 735 736 if (next_skip == 1) { 737 nblks += blst_leaf_fill(&scan[i], fillBlk, v); 738 } else { 739 nblks += blst_meta_fill(&scan[i], fillBlk, v, 740 radix, next_skip - 1, blk); 741 } 742 count -= v; 743 fillBlk += v; 744 blk += (swblk_t)radix; 745 i += next_skip; 746 } 747 scan->u.bmu_avail -= nblks; 748 return (nblks); 749 } 750 751 /* 752 * BLIST_RADIX_COPY() - copy one radix tree to another 753 * 754 * Locates free space in the source tree and frees it in the destination 755 * tree. The space may not already be free in the destination. 756 */ 757 758 static void 759 blst_copy(blmeta_t *scan, swblk_t blk, int64_t radix, 760 swblk_t skip, blist_t dest, swblk_t count) 761 { 762 int next_skip; 763 int i; 764 765 /* 766 * Leaf node 767 */ 768 769 if (radix == BLIST_BMAP_RADIX) { 770 u_swblk_t v = scan->u.bmu_bitmap; 771 772 if (v == (u_swblk_t)-1) { 773 blist_free(dest, blk, count); 774 } else if (v != 0) { 775 int i; 776 777 for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { 778 if (v & (1 << i)) 779 blist_free(dest, blk + i, 1); 780 } 781 } 782 return; 783 } 784 785 /* 786 * Meta node 787 */ 788 789 if (scan->u.bmu_avail == 0) { 790 /* 791 * Source all allocated, leave dest allocated 792 */ 793 return; 794 } 795 if (scan->u.bmu_avail == radix) { 796 /* 797 * Source all free, free entire dest 798 */ 799 if (count < radix) 800 blist_free(dest, blk, count); 801 else 802 blist_free(dest, blk, (swblk_t)radix); 803 return; 804 } 805 806 807 radix /= BLIST_META_RADIX; 808 next_skip = ((u_int)skip / BLIST_META_RADIX); 809 810 for (i = 1; count && i <= skip; i += next_skip) { 811 if (scan[i].bm_bighint == (swblk_t)-1) 812 break; 813 814 if (count >= (swblk_t)radix) { 815 blst_copy( 816 &scan[i], 817 blk, 818 radix, 819 next_skip - 1, 820 dest, 821 (swblk_t)radix 822 ); 823 count -= (swblk_t)radix; 824 } else { 825 if (count) { 826 blst_copy( 827 &scan[i], 828 blk, 829 radix, 830 next_skip - 1, 831 dest, 832 count 833 ); 834 } 835 count = 0; 836 } 837 blk += (swblk_t)radix; 838 } 839 } 840 841 /* 842 * BLST_RADIX_INIT() - initialize radix tree 843 * 844 * Initialize our meta structures and bitmaps and calculate the exact 845 * amount of space required to manage 'count' blocks - this space may 846 * be considerably less then the calculated radix due to the large 847 * RADIX values we use. 848 */ 849 850 static swblk_t 851 blst_radix_init(blmeta_t *scan, int64_t radix, int skip, swblk_t count) 852 { 853 int i; 854 int next_skip; 855 swblk_t memindex = 0; 856 857 /* 858 * Leaf node 859 */ 860 861 if (radix == BLIST_BMAP_RADIX) { 862 if (scan) { 863 scan->bm_bighint = 0; 864 scan->u.bmu_bitmap = 0; 865 } 866 return(memindex); 867 } 868 869 /* 870 * Meta node. If allocating the entire object we can special 871 * case it. However, we need to figure out how much memory 872 * is required to manage 'count' blocks, so we continue on anyway. 873 */ 874 875 if (scan) { 876 scan->bm_bighint = 0; 877 scan->u.bmu_avail = 0; 878 } 879 880 radix /= BLIST_META_RADIX; 881 next_skip = ((u_int)skip / BLIST_META_RADIX); 882 883 for (i = 1; i <= skip; i += next_skip) { 884 if (count >= (swblk_t)radix) { 885 /* 886 * Allocate the entire object 887 */ 888 memindex = i + blst_radix_init( 889 ((scan) ? &scan[i] : NULL), 890 radix, 891 next_skip - 1, 892 (swblk_t)radix 893 ); 894 count -= (swblk_t)radix; 895 } else if (count > 0) { 896 /* 897 * Allocate a partial object 898 */ 899 memindex = i + blst_radix_init( 900 ((scan) ? &scan[i] : NULL), 901 radix, 902 next_skip - 1, 903 count 904 ); 905 count = 0; 906 } else { 907 /* 908 * Add terminator and break out 909 */ 910 if (scan) 911 scan[i].bm_bighint = (swblk_t)-1; 912 break; 913 } 914 } 915 if (memindex < i) 916 memindex = i; 917 return(memindex); 918 } 919 920 #ifdef BLIST_DEBUG 921 922 static void 923 blst_radix_print(blmeta_t *scan, swblk_t blk, int64_t radix, int skip, int tab) 924 { 925 int i; 926 int next_skip; 927 int lastState = 0; 928 929 if (radix == BLIST_BMAP_RADIX) { 930 kprintf( 931 "%*.*s(%04x,%lld): bitmap %08x big=%d\n", 932 tab, tab, "", 933 blk, (long long)radix, 934 scan->u.bmu_bitmap, 935 scan->bm_bighint 936 ); 937 return; 938 } 939 940 if (scan->u.bmu_avail == 0) { 941 kprintf( 942 "%*.*s(%04x,%lld) ALL ALLOCATED\n", 943 tab, tab, "", 944 blk, 945 (long long)radix 946 ); 947 return; 948 } 949 if (scan->u.bmu_avail == radix) { 950 kprintf( 951 "%*.*s(%04x,%lld) ALL FREE\n", 952 tab, tab, "", 953 blk, 954 (long long)radix 955 ); 956 return; 957 } 958 959 kprintf( 960 "%*.*s(%04x,%lld): subtree (%d/%lld) big=%d {\n", 961 tab, tab, "", 962 blk, (long long)radix, 963 scan->u.bmu_avail, 964 (long long)radix, 965 scan->bm_bighint 966 ); 967 968 radix /= BLIST_META_RADIX; 969 next_skip = ((u_int)skip / BLIST_META_RADIX); 970 tab += 4; 971 972 for (i = 1; i <= skip; i += next_skip) { 973 if (scan[i].bm_bighint == (swblk_t)-1) { 974 kprintf( 975 "%*.*s(%04x,%lld): Terminator\n", 976 tab, tab, "", 977 blk, (long long)radix 978 ); 979 lastState = 0; 980 break; 981 } 982 blst_radix_print( 983 &scan[i], 984 blk, 985 radix, 986 next_skip - 1, 987 tab 988 ); 989 blk += (swblk_t)radix; 990 } 991 tab -= 4; 992 993 kprintf( 994 "%*.*s}\n", 995 tab, tab, "" 996 ); 997 } 998 999 #endif 1000 1001 #ifdef BLIST_DEBUG 1002 1003 int 1004 main(int ac, char **av) 1005 { 1006 int size = 1024; 1007 int i; 1008 blist_t bl; 1009 1010 for (i = 1; i < ac; ++i) { 1011 const char *ptr = av[i]; 1012 if (*ptr != '-') { 1013 size = strtol(ptr, NULL, 0); 1014 continue; 1015 } 1016 ptr += 2; 1017 fprintf(stderr, "Bad option: %s\n", ptr - 2); 1018 exit(1); 1019 } 1020 bl = blist_create(size); 1021 blist_free(bl, 0, size); 1022 1023 for (;;) { 1024 char buf[1024]; 1025 swblk_t da = 0; 1026 swblk_t count = 0; 1027 1028 1029 kprintf("%d/%d/%lld> ", 1030 bl->bl_free, size, (long long)bl->bl_radix); 1031 fflush(stdout); 1032 if (fgets(buf, sizeof(buf), stdin) == NULL) 1033 break; 1034 switch(buf[0]) { 1035 case 'r': 1036 if (sscanf(buf + 1, "%d", &count) == 1) { 1037 blist_resize(&bl, count, 1); 1038 size = count; 1039 } else { 1040 kprintf("?\n"); 1041 } 1042 case 'p': 1043 blist_print(bl); 1044 break; 1045 case 'a': 1046 if (sscanf(buf + 1, "%d", &count) == 1) { 1047 swblk_t blk = blist_alloc(bl, count); 1048 kprintf(" R=%04x\n", blk); 1049 } else { 1050 kprintf("?\n"); 1051 } 1052 break; 1053 case 'f': 1054 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 1055 blist_free(bl, da, count); 1056 } else { 1057 kprintf("?\n"); 1058 } 1059 break; 1060 case 'l': 1061 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 1062 printf(" n=%d\n", 1063 blist_fill(bl, da, count)); 1064 } else { 1065 kprintf("?\n"); 1066 } 1067 break; 1068 case '?': 1069 case 'h': 1070 puts( 1071 "p -print\n" 1072 "a %d -allocate\n" 1073 "f %x %d -free\n" 1074 "l %x %d -fill\n" 1075 "r %d -resize\n" 1076 "h/? -help" 1077 ); 1078 break; 1079 default: 1080 kprintf("?\n"); 1081 break; 1082 } 1083 } 1084 return(0); 1085 } 1086 1087 void 1088 panic(const char *ctl, ...) 1089 { 1090 __va_list va; 1091 1092 __va_start(va, ctl); 1093 vfprintf(stderr, ctl, va); 1094 fprintf(stderr, "\n"); 1095 __va_end(va); 1096 exit(1); 1097 } 1098 1099 #endif 1100 1101