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