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 * $FreeBSD: src/sys/kern/subr_blist.c,v 1.5.2.2 2003/01/12 09:23:12 dillon Exp $ 97 * $DragonFly: src/sys/kern/subr_blist.c,v 1.8 2008/08/10 22:09:50 dillon Exp $ 98 */ 99 100 #ifdef _KERNEL 101 102 #include <sys/param.h> 103 #include <sys/systm.h> 104 #include <sys/lock.h> 105 #include <sys/kernel.h> 106 #include <sys/blist.h> 107 #include <sys/malloc.h> 108 109 #else 110 111 #ifndef BLIST_NO_DEBUG 112 #define BLIST_DEBUG 113 #endif 114 115 #define SWAPBLK_NONE ((swblk_t)-1) 116 117 #include <sys/types.h> 118 #include <stdio.h> 119 #include <string.h> 120 #include <stdlib.h> 121 #include <stdarg.h> 122 123 #define kmalloc(a,b,c) malloc(a) 124 #define kfree(a,b) free(a) 125 #define kprintf printf 126 #define KKASSERT(exp) 127 128 #include <sys/blist.h> 129 130 void panic(const char *ctl, ...); 131 132 #endif 133 134 /* 135 * static support functions 136 */ 137 138 static swblk_t blst_leaf_alloc(blmeta_t *scan, swblk_t blk, int count); 139 static swblk_t blst_meta_alloc(blmeta_t *scan, swblk_t blk, 140 swblk_t count, int64_t radix, int skip); 141 static void blst_leaf_free(blmeta_t *scan, swblk_t relblk, int count); 142 static void blst_meta_free(blmeta_t *scan, swblk_t freeBlk, swblk_t count, 143 int64_t radix, int skip, swblk_t blk); 144 static swblk_t blst_leaf_fill(blmeta_t *scan, swblk_t blk, int count); 145 static swblk_t blst_meta_fill(blmeta_t *scan, swblk_t fillBlk, swblk_t count, 146 int64_t radix, int skip, swblk_t blk); 147 static void blst_copy(blmeta_t *scan, swblk_t blk, int64_t radix, 148 swblk_t skip, blist_t dest, swblk_t count); 149 static swblk_t blst_radix_init(blmeta_t *scan, int64_t radix, 150 int skip, swblk_t count); 151 #ifndef _KERNEL 152 static void blst_radix_print(blmeta_t *scan, swblk_t blk, 153 int64_t radix, int skip, int tab); 154 #endif 155 156 #ifdef _KERNEL 157 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); 158 #endif 159 160 /* 161 * blist_create() - create a blist capable of handling up to the specified 162 * number of blocks 163 * 164 * blocks must be greater then 0 165 * 166 * The smallest blist consists of a single leaf node capable of 167 * managing BLIST_BMAP_RADIX blocks. 168 */ 169 170 blist_t 171 blist_create(swblk_t blocks) 172 { 173 blist_t bl; 174 int64_t radix; 175 int skip = 0; 176 177 /* 178 * Calculate radix and skip field used for scanning. 179 * 180 * Radix can exceed 32 bits even if swblk_t is limited to 32 bits. 181 */ 182 radix = BLIST_BMAP_RADIX; 183 184 while (radix < blocks) { 185 radix *= BLIST_META_RADIX; 186 skip = (skip + 1) * BLIST_META_RADIX; 187 KKASSERT(skip > 0); 188 } 189 190 bl = kmalloc(sizeof(struct blist), M_SWAP, M_WAITOK); 191 192 bzero(bl, sizeof(*bl)); 193 194 bl->bl_blocks = blocks; 195 bl->bl_radix = radix; 196 bl->bl_skip = skip; 197 bl->bl_rootblks = 1 + 198 blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 199 bl->bl_root = kmalloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, M_WAITOK); 200 201 #if defined(BLIST_DEBUG) 202 kprintf( 203 "BLIST representing %d blocks (%d MB of swap)" 204 ", requiring %dK of ram\n", 205 bl->bl_blocks, 206 bl->bl_blocks * 4 / 1024, 207 (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 208 ); 209 kprintf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks); 210 #endif 211 blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 212 213 return(bl); 214 } 215 216 void 217 blist_destroy(blist_t bl) 218 { 219 kfree(bl->bl_root, M_SWAP); 220 kfree(bl, M_SWAP); 221 } 222 223 /* 224 * blist_alloc() - reserve space in the block bitmap. Return the base 225 * of a contiguous region or SWAPBLK_NONE if space could 226 * not be allocated. 227 */ 228 229 swblk_t 230 blist_alloc(blist_t bl, swblk_t count) 231 { 232 swblk_t blk = SWAPBLK_NONE; 233 234 if (bl) { 235 if (bl->bl_radix == BLIST_BMAP_RADIX) 236 blk = blst_leaf_alloc(bl->bl_root, 0, count); 237 else 238 blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 239 if (blk != SWAPBLK_NONE) 240 bl->bl_free -= count; 241 } 242 return(blk); 243 } 244 245 /* 246 * blist_free() - free up space in the block bitmap. Return the base 247 * of a contiguous region. Panic if an inconsistancy is 248 * found. 249 */ 250 251 void 252 blist_free(blist_t bl, swblk_t blkno, swblk_t count) 253 { 254 if (bl) { 255 if (bl->bl_radix == BLIST_BMAP_RADIX) 256 blst_leaf_free(bl->bl_root, blkno, count); 257 else 258 blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 259 bl->bl_free += count; 260 } 261 } 262 263 /* 264 * blist_fill() - mark a region in the block bitmap as off-limits 265 * to the allocator (i.e. allocate it), ignoring any 266 * existing allocations. Return the number of blocks 267 * actually filled that were free before the call. 268 */ 269 270 swblk_t 271 blist_fill(blist_t bl, swblk_t blkno, swblk_t count) 272 { 273 swblk_t filled; 274 275 if (bl) { 276 if (bl->bl_radix == BLIST_BMAP_RADIX) { 277 filled = blst_leaf_fill(bl->bl_root, blkno, count); 278 } else { 279 filled = blst_meta_fill(bl->bl_root, blkno, count, 280 bl->bl_radix, bl->bl_skip, 0); 281 } 282 bl->bl_free -= filled; 283 return (filled); 284 } else { 285 return 0; 286 } 287 } 288 289 /* 290 * blist_resize() - resize an existing radix tree to handle the 291 * specified number of blocks. This will reallocate 292 * the tree and transfer the previous bitmap to the new 293 * one. When extending the tree you can specify whether 294 * the new blocks are to left allocated or freed. 295 */ 296 297 void 298 blist_resize(blist_t *pbl, swblk_t count, int freenew) 299 { 300 blist_t newbl = blist_create(count); 301 blist_t save = *pbl; 302 303 *pbl = newbl; 304 if (count > save->bl_blocks) 305 count = save->bl_blocks; 306 blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 307 308 /* 309 * If resizing upwards, should we free the new space or not? 310 */ 311 if (freenew && count < newbl->bl_blocks) { 312 blist_free(newbl, count, newbl->bl_blocks - count); 313 } 314 blist_destroy(save); 315 } 316 317 #ifdef BLIST_DEBUG 318 319 /* 320 * blist_print() - dump radix tree 321 */ 322 323 void 324 blist_print(blist_t bl) 325 { 326 kprintf("BLIST {\n"); 327 blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 328 kprintf("}\n"); 329 } 330 331 #endif 332 333 /************************************************************************ 334 * ALLOCATION SUPPORT FUNCTIONS * 335 ************************************************************************ 336 * 337 * These support functions do all the actual work. They may seem 338 * rather longish, but that's because I've commented them up. The 339 * actual code is straight forward. 340 * 341 */ 342 343 /* 344 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 345 * 346 * This is the core of the allocator and is optimized for the 1 block 347 * and the BLIST_BMAP_RADIX block allocation cases. Other cases are 348 * somewhat slower. The 1 block allocation case is log2 and extremely 349 * quick. 350 */ 351 352 static swblk_t 353 blst_leaf_alloc(blmeta_t *scan, swblk_t blk, int count) 354 { 355 u_swblk_t orig = scan->u.bmu_bitmap; 356 357 if (orig == 0) { 358 /* 359 * Optimize bitmap all-allocated case. Also, count = 1 360 * case assumes at least 1 bit is free in the bitmap, so 361 * we have to take care of this case here. 362 */ 363 scan->bm_bighint = 0; 364 return(SWAPBLK_NONE); 365 } 366 if (count == 1) { 367 /* 368 * Optimized code to allocate one bit out of the bitmap 369 */ 370 u_swblk_t mask; 371 int j = BLIST_BMAP_RADIX/2; 372 int r = 0; 373 374 mask = (u_swblk_t)-1 >> (BLIST_BMAP_RADIX/2); 375 376 while (j) { 377 if ((orig & mask) == 0) { 378 r += j; 379 orig >>= j; 380 } 381 j >>= 1; 382 mask >>= j; 383 } 384 scan->u.bmu_bitmap &= ~(1 << r); 385 return(blk + r); 386 } 387 if (count <= BLIST_BMAP_RADIX) { 388 /* 389 * non-optimized code to allocate N bits out of the bitmap. 390 * The more bits, the faster the code runs. It will run 391 * the slowest allocating 2 bits, but since there aren't any 392 * memory ops in the core loop (or shouldn't be, anyway), 393 * you probably won't notice the difference. 394 */ 395 int j; 396 int n = BLIST_BMAP_RADIX - count; 397 u_swblk_t mask; 398 399 mask = (u_swblk_t)-1 >> n; 400 401 for (j = 0; j <= n; ++j) { 402 if ((orig & mask) == mask) { 403 scan->u.bmu_bitmap &= ~mask; 404 return(blk + j); 405 } 406 mask = (mask << 1); 407 } 408 } 409 /* 410 * We couldn't allocate count in this subtree, update bighint. 411 */ 412 scan->bm_bighint = count - 1; 413 return(SWAPBLK_NONE); 414 } 415 416 /* 417 * blist_meta_alloc() - allocate at a meta in the radix tree. 418 * 419 * Attempt to allocate at a meta node. If we can't, we update 420 * bighint and return a failure. Updating bighint optimize future 421 * calls that hit this node. We have to check for our collapse cases 422 * and we have a few optimizations strewn in as well. 423 */ 424 425 static swblk_t 426 blst_meta_alloc(blmeta_t *scan, swblk_t blk, swblk_t count, 427 int64_t radix, int skip) 428 { 429 int i; 430 int next_skip = ((u_int)skip / BLIST_META_RADIX); 431 432 if (scan->u.bmu_avail == 0) { 433 /* 434 * ALL-ALLOCATED special case 435 */ 436 scan->bm_bighint = count; 437 return(SWAPBLK_NONE); 438 } 439 440 /* 441 * note: radix may exceed 32 bits until first division. 442 */ 443 if (scan->u.bmu_avail == radix) { 444 radix /= BLIST_META_RADIX; 445 446 /* 447 * ALL-FREE special case, initialize uninitialize 448 * sublevel. 449 */ 450 for (i = 1; i <= skip; i += next_skip) { 451 if (scan[i].bm_bighint == (swblk_t)-1) 452 break; 453 if (next_skip == 1) { 454 scan[i].u.bmu_bitmap = (u_swblk_t)-1; 455 scan[i].bm_bighint = BLIST_BMAP_RADIX; 456 } else { 457 scan[i].bm_bighint = (swblk_t)radix; 458 scan[i].u.bmu_avail = (swblk_t)radix; 459 } 460 } 461 } else { 462 radix /= BLIST_META_RADIX; 463 } 464 465 for (i = 1; i <= skip; i += next_skip) { 466 if (count <= scan[i].bm_bighint) { 467 /* 468 * count fits in object 469 */ 470 swblk_t r; 471 if (next_skip == 1) { 472 r = blst_leaf_alloc(&scan[i], blk, count); 473 } else { 474 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 475 } 476 if (r != SWAPBLK_NONE) { 477 scan->u.bmu_avail -= count; 478 if (scan->bm_bighint > scan->u.bmu_avail) 479 scan->bm_bighint = scan->u.bmu_avail; 480 return(r); 481 } 482 } else if (scan[i].bm_bighint == (swblk_t)-1) { 483 /* 484 * Terminator 485 */ 486 break; 487 } else if (count > (swblk_t)radix) { 488 /* 489 * count does not fit in object even if it were 490 * complete free. 491 */ 492 panic("blist_meta_alloc: allocation too large"); 493 } 494 blk += (swblk_t)radix; 495 } 496 497 /* 498 * We couldn't allocate count in this subtree, update bighint. 499 */ 500 if (scan->bm_bighint >= count) 501 scan->bm_bighint = count - 1; 502 return(SWAPBLK_NONE); 503 } 504 505 /* 506 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 507 * 508 */ 509 510 static void 511 blst_leaf_free(blmeta_t *scan, swblk_t blk, int count) 512 { 513 /* 514 * free some data in this bitmap 515 * 516 * e.g. 517 * 0000111111111110000 518 * \_________/\__/ 519 * v n 520 */ 521 int n = blk & (BLIST_BMAP_RADIX - 1); 522 u_swblk_t mask; 523 524 mask = ((u_swblk_t)-1 << n) & 525 ((u_swblk_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 526 527 if (scan->u.bmu_bitmap & mask) 528 panic("blst_radix_free: freeing free block"); 529 scan->u.bmu_bitmap |= mask; 530 531 /* 532 * We could probably do a better job here. We are required to make 533 * bighint at least as large as the biggest contiguous block of 534 * data. If we just shoehorn it, a little extra overhead will 535 * be incured on the next allocation (but only that one typically). 536 */ 537 scan->bm_bighint = BLIST_BMAP_RADIX; 538 } 539 540 /* 541 * BLST_META_FREE() - free allocated blocks from radix tree meta info 542 * 543 * This support routine frees a range of blocks from the bitmap. 544 * The range must be entirely enclosed by this radix node. If a 545 * meta node, we break the range down recursively to free blocks 546 * in subnodes (which means that this code can free an arbitrary 547 * range whereas the allocation code cannot allocate an arbitrary 548 * range). 549 */ 550 551 static void 552 blst_meta_free(blmeta_t *scan, swblk_t freeBlk, swblk_t count, 553 int64_t radix, int skip, swblk_t blk) 554 { 555 int i; 556 int next_skip = ((u_int)skip / BLIST_META_RADIX); 557 558 #if 0 559 kprintf("FREE (%x,%d) FROM (%x,%lld)\n", 560 freeBlk, count, 561 blk, (long long)radix 562 ); 563 #endif 564 565 /* 566 * NOTE: radix may exceed 32 bits until first division. 567 */ 568 if (scan->u.bmu_avail == 0) { 569 /* 570 * ALL-ALLOCATED special case, with possible 571 * shortcut to ALL-FREE special case. 572 */ 573 scan->u.bmu_avail = count; 574 scan->bm_bighint = count; 575 576 if (count != radix) { 577 for (i = 1; i <= skip; i += next_skip) { 578 if (scan[i].bm_bighint == (swblk_t)-1) 579 break; 580 scan[i].bm_bighint = 0; 581 if (next_skip == 1) { 582 scan[i].u.bmu_bitmap = 0; 583 } else { 584 scan[i].u.bmu_avail = 0; 585 } 586 } 587 /* fall through */ 588 } 589 } else { 590 scan->u.bmu_avail += count; 591 /* scan->bm_bighint = radix; */ 592 } 593 594 /* 595 * ALL-FREE special case. 596 */ 597 598 if (scan->u.bmu_avail == radix) 599 return; 600 if (scan->u.bmu_avail > radix) 601 panic("blst_meta_free: freeing already free blocks (%d) %d/%lld", count, scan->u.bmu_avail, (long long)radix); 602 603 /* 604 * Break the free down into its components 605 */ 606 607 radix /= BLIST_META_RADIX; 608 609 i = (freeBlk - blk) / (swblk_t)radix; 610 blk += i * (swblk_t)radix; 611 i = i * next_skip + 1; 612 613 while (i <= skip && blk < freeBlk + count) { 614 swblk_t v; 615 616 v = blk + (swblk_t)radix - freeBlk; 617 if (v > count) 618 v = count; 619 620 if (scan->bm_bighint == (swblk_t)-1) 621 panic("blst_meta_free: freeing unexpected range"); 622 623 if (next_skip == 1) { 624 blst_leaf_free(&scan[i], freeBlk, v); 625 } else { 626 blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 627 } 628 if (scan->bm_bighint < scan[i].bm_bighint) 629 scan->bm_bighint = scan[i].bm_bighint; 630 count -= v; 631 freeBlk += v; 632 blk += (swblk_t)radix; 633 i += next_skip; 634 } 635 } 636 637 /* 638 * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap 639 * 640 * Allocates all blocks in the specified range regardless of 641 * any existing allocations in that range. Returns the number 642 * of blocks allocated by the call. 643 */ 644 static swblk_t 645 blst_leaf_fill(blmeta_t *scan, swblk_t blk, int count) 646 { 647 int n = blk & (BLIST_BMAP_RADIX - 1); 648 swblk_t nblks; 649 u_swblk_t mask, bitmap; 650 651 mask = ((u_swblk_t)-1 << n) & 652 ((u_swblk_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 653 654 /* Count the number of blocks we're about to allocate */ 655 bitmap = scan->u.bmu_bitmap & mask; 656 for (nblks = 0; bitmap != 0; nblks++) 657 bitmap &= bitmap - 1; 658 659 scan->u.bmu_bitmap &= ~mask; 660 return (nblks); 661 } 662 663 /* 664 * BLST_META_FILL() - allocate specific blocks at a meta node 665 * 666 * Allocates the specified range of blocks, regardless of 667 * any existing allocations in the range. The range must 668 * be within the extent of this node. Returns the number 669 * of blocks allocated by the call. 670 */ 671 static swblk_t 672 blst_meta_fill(blmeta_t *scan, swblk_t fillBlk, swblk_t count, 673 int64_t radix, int skip, swblk_t blk) 674 { 675 int i; 676 int next_skip = ((u_int)skip / BLIST_META_RADIX); 677 swblk_t nblks = 0; 678 679 if (count == radix || scan->u.bmu_avail == 0) { 680 /* 681 * ALL-ALLOCATED special case 682 */ 683 nblks = scan->u.bmu_avail; 684 scan->u.bmu_avail = 0; 685 scan->bm_bighint = count; 686 return (nblks); 687 } 688 689 if (scan->u.bmu_avail == radix) { 690 radix /= BLIST_META_RADIX; 691 692 /* 693 * ALL-FREE special case, initialize sublevel 694 */ 695 for (i = 1; i <= skip; i += next_skip) { 696 if (scan[i].bm_bighint == (swblk_t)-1) 697 break; 698 if (next_skip == 1) { 699 scan[i].u.bmu_bitmap = (u_swblk_t)-1; 700 scan[i].bm_bighint = BLIST_BMAP_RADIX; 701 } else { 702 scan[i].bm_bighint = (swblk_t)radix; 703 scan[i].u.bmu_avail = (swblk_t)radix; 704 } 705 } 706 } else { 707 radix /= BLIST_META_RADIX; 708 } 709 710 if (count > (swblk_t)radix) 711 panic("blst_meta_fill: allocation too large"); 712 713 i = (fillBlk - blk) / (swblk_t)radix; 714 blk += i * (swblk_t)radix; 715 i = i * next_skip + 1; 716 717 while (i <= skip && blk < fillBlk + count) { 718 swblk_t v; 719 720 v = blk + (swblk_t)radix - fillBlk; 721 if (v > count) 722 v = count; 723 724 if (scan->bm_bighint == (swblk_t)-1) 725 panic("blst_meta_fill: filling unexpected range"); 726 727 if (next_skip == 1) { 728 nblks += blst_leaf_fill(&scan[i], fillBlk, v); 729 } else { 730 nblks += blst_meta_fill(&scan[i], fillBlk, v, 731 radix, next_skip - 1, blk); 732 } 733 count -= v; 734 fillBlk += v; 735 blk += (swblk_t)radix; 736 i += next_skip; 737 } 738 scan->u.bmu_avail -= nblks; 739 return (nblks); 740 } 741 742 /* 743 * BLIST_RADIX_COPY() - copy one radix tree to another 744 * 745 * Locates free space in the source tree and frees it in the destination 746 * tree. The space may not already be free in the destination. 747 */ 748 749 static void 750 blst_copy(blmeta_t *scan, swblk_t blk, int64_t radix, 751 swblk_t skip, blist_t dest, swblk_t count) 752 { 753 int next_skip; 754 int i; 755 756 /* 757 * Leaf node 758 */ 759 760 if (radix == BLIST_BMAP_RADIX) { 761 u_swblk_t v = scan->u.bmu_bitmap; 762 763 if (v == (u_swblk_t)-1) { 764 blist_free(dest, blk, count); 765 } else if (v != 0) { 766 int i; 767 768 for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { 769 if (v & (1 << i)) 770 blist_free(dest, blk + i, 1); 771 } 772 } 773 return; 774 } 775 776 /* 777 * Meta node 778 */ 779 780 if (scan->u.bmu_avail == 0) { 781 /* 782 * Source all allocated, leave dest allocated 783 */ 784 return; 785 } 786 if (scan->u.bmu_avail == radix) { 787 /* 788 * Source all free, free entire dest 789 */ 790 if (count < radix) 791 blist_free(dest, blk, count); 792 else 793 blist_free(dest, blk, (swblk_t)radix); 794 return; 795 } 796 797 798 radix /= BLIST_META_RADIX; 799 next_skip = ((u_int)skip / BLIST_META_RADIX); 800 801 for (i = 1; count && i <= skip; i += next_skip) { 802 if (scan[i].bm_bighint == (swblk_t)-1) 803 break; 804 805 if (count >= (swblk_t)radix) { 806 blst_copy( 807 &scan[i], 808 blk, 809 radix, 810 next_skip - 1, 811 dest, 812 (swblk_t)radix 813 ); 814 count -= (swblk_t)radix; 815 } else { 816 if (count) { 817 blst_copy( 818 &scan[i], 819 blk, 820 radix, 821 next_skip - 1, 822 dest, 823 count 824 ); 825 } 826 count = 0; 827 } 828 blk += (swblk_t)radix; 829 } 830 } 831 832 /* 833 * BLST_RADIX_INIT() - initialize radix tree 834 * 835 * Initialize our meta structures and bitmaps and calculate the exact 836 * amount of space required to manage 'count' blocks - this space may 837 * be considerably less then the calculated radix due to the large 838 * RADIX values we use. 839 */ 840 841 static swblk_t 842 blst_radix_init(blmeta_t *scan, int64_t radix, int skip, swblk_t count) 843 { 844 int i; 845 int next_skip; 846 swblk_t memindex = 0; 847 848 /* 849 * Leaf node 850 */ 851 852 if (radix == BLIST_BMAP_RADIX) { 853 if (scan) { 854 scan->bm_bighint = 0; 855 scan->u.bmu_bitmap = 0; 856 } 857 return(memindex); 858 } 859 860 /* 861 * Meta node. If allocating the entire object we can special 862 * case it. However, we need to figure out how much memory 863 * is required to manage 'count' blocks, so we continue on anyway. 864 */ 865 866 if (scan) { 867 scan->bm_bighint = 0; 868 scan->u.bmu_avail = 0; 869 } 870 871 radix /= BLIST_META_RADIX; 872 next_skip = ((u_int)skip / BLIST_META_RADIX); 873 874 for (i = 1; i <= skip; i += next_skip) { 875 if (count >= (swblk_t)radix) { 876 /* 877 * Allocate the entire object 878 */ 879 memindex = i + blst_radix_init( 880 ((scan) ? &scan[i] : NULL), 881 radix, 882 next_skip - 1, 883 (swblk_t)radix 884 ); 885 count -= (swblk_t)radix; 886 } else if (count > 0) { 887 /* 888 * Allocate a partial object 889 */ 890 memindex = i + blst_radix_init( 891 ((scan) ? &scan[i] : NULL), 892 radix, 893 next_skip - 1, 894 count 895 ); 896 count = 0; 897 } else { 898 /* 899 * Add terminator and break out 900 */ 901 if (scan) 902 scan[i].bm_bighint = (swblk_t)-1; 903 break; 904 } 905 } 906 if (memindex < i) 907 memindex = i; 908 return(memindex); 909 } 910 911 #ifdef BLIST_DEBUG 912 913 static void 914 blst_radix_print(blmeta_t *scan, swblk_t blk, int64_t radix, int skip, int tab) 915 { 916 int i; 917 int next_skip; 918 int lastState = 0; 919 920 if (radix == BLIST_BMAP_RADIX) { 921 kprintf( 922 "%*.*s(%04x,%lld): bitmap %08x big=%d\n", 923 tab, tab, "", 924 blk, (long long)radix, 925 scan->u.bmu_bitmap, 926 scan->bm_bighint 927 ); 928 return; 929 } 930 931 if (scan->u.bmu_avail == 0) { 932 kprintf( 933 "%*.*s(%04x,%lld) ALL ALLOCATED\n", 934 tab, tab, "", 935 blk, 936 (long long)radix 937 ); 938 return; 939 } 940 if (scan->u.bmu_avail == radix) { 941 kprintf( 942 "%*.*s(%04x,%lld) ALL FREE\n", 943 tab, tab, "", 944 blk, 945 (long long)radix 946 ); 947 return; 948 } 949 950 kprintf( 951 "%*.*s(%04x,%lld): subtree (%d/%lld) big=%d {\n", 952 tab, tab, "", 953 blk, (long long)radix, 954 scan->u.bmu_avail, 955 (long long)radix, 956 scan->bm_bighint 957 ); 958 959 radix /= BLIST_META_RADIX; 960 next_skip = ((u_int)skip / BLIST_META_RADIX); 961 tab += 4; 962 963 for (i = 1; i <= skip; i += next_skip) { 964 if (scan[i].bm_bighint == (swblk_t)-1) { 965 kprintf( 966 "%*.*s(%04x,%lld): Terminator\n", 967 tab, tab, "", 968 blk, (long long)radix 969 ); 970 lastState = 0; 971 break; 972 } 973 blst_radix_print( 974 &scan[i], 975 blk, 976 radix, 977 next_skip - 1, 978 tab 979 ); 980 blk += (swblk_t)radix; 981 } 982 tab -= 4; 983 984 kprintf( 985 "%*.*s}\n", 986 tab, tab, "" 987 ); 988 } 989 990 #endif 991 992 #ifdef BLIST_DEBUG 993 994 int 995 main(int ac, char **av) 996 { 997 int size = 1024; 998 int i; 999 blist_t bl; 1000 1001 for (i = 1; i < ac; ++i) { 1002 const char *ptr = av[i]; 1003 if (*ptr != '-') { 1004 size = strtol(ptr, NULL, 0); 1005 continue; 1006 } 1007 ptr += 2; 1008 fprintf(stderr, "Bad option: %s\n", ptr - 2); 1009 exit(1); 1010 } 1011 bl = blist_create(size); 1012 blist_free(bl, 0, size); 1013 1014 for (;;) { 1015 char buf[1024]; 1016 swblk_t da = 0; 1017 swblk_t count = 0; 1018 1019 1020 kprintf("%d/%d/%lld> ", 1021 bl->bl_free, size, (long long)bl->bl_radix); 1022 fflush(stdout); 1023 if (fgets(buf, sizeof(buf), stdin) == NULL) 1024 break; 1025 switch(buf[0]) { 1026 case 'r': 1027 if (sscanf(buf + 1, "%d", &count) == 1) { 1028 blist_resize(&bl, count, 1); 1029 size = count; 1030 } else { 1031 kprintf("?\n"); 1032 } 1033 case 'p': 1034 blist_print(bl); 1035 break; 1036 case 'a': 1037 if (sscanf(buf + 1, "%d", &count) == 1) { 1038 swblk_t blk = blist_alloc(bl, count); 1039 kprintf(" R=%04x\n", blk); 1040 } else { 1041 kprintf("?\n"); 1042 } 1043 break; 1044 case 'f': 1045 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 1046 blist_free(bl, da, count); 1047 } else { 1048 kprintf("?\n"); 1049 } 1050 break; 1051 case 'l': 1052 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 1053 printf(" n=%d\n", 1054 blist_fill(bl, da, count)); 1055 } else { 1056 kprintf("?\n"); 1057 } 1058 break; 1059 case '?': 1060 case 'h': 1061 puts( 1062 "p -print\n" 1063 "a %d -allocate\n" 1064 "f %x %d -free\n" 1065 "l %x %d -fill\n" 1066 "r %d -resize\n" 1067 "h/? -help" 1068 ); 1069 break; 1070 default: 1071 kprintf("?\n"); 1072 break; 1073 } 1074 } 1075 return(0); 1076 } 1077 1078 void 1079 panic(const char *ctl, ...) 1080 { 1081 __va_list va; 1082 1083 __va_start(va, ctl); 1084 vfprintf(stderr, ctl, va); 1085 fprintf(stderr, "\n"); 1086 __va_end(va); 1087 exit(1); 1088 } 1089 1090 #endif 1091 1092