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