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