subr_blist.c revision 42956
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 64#ifdef KERNEL 65 66#include <sys/param.h> 67#include <sys/systm.h> 68#include <sys/lock.h> 69#include <sys/kernel.h> 70#include <sys/blist.h> 71#include <sys/malloc.h> 72#include <vm/vm.h> 73#include <vm/vm_prot.h> 74#include <vm/vm_object.h> 75#include <vm/vm_kern.h> 76#include <vm/vm_extern.h> 77#include <vm/vm_page.h> 78 79#else 80 81#ifndef BLIST_NO_DEBUG 82#define BLIST_DEBUG 83#endif 84 85#define SWAPBLK_NONE ((daddr_t)-1) 86 87#include <sys/types.h> 88#include <stdio.h> 89#include <string.h> 90#include <stdlib.h> 91#include <stdarg.h> 92 93#define malloc(a,b,c) malloc(a) 94#define free(a,b) free(a) 95 96typedef unsigned int u_daddr_t; 97 98#include <sys/blist.h> 99 100void panic(const char *ctl, ...); 101 102#endif 103 104/* 105 * static support functions 106 */ 107 108static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count); 109static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, 110 daddr_t count, daddr_t radix, int skip); 111static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count); 112static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, 113 daddr_t radix, int skip, daddr_t blk); 114static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, 115 daddr_t skip, blist_t dest, daddr_t count); 116static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, 117 int skip, daddr_t count); 118#ifndef KERNEL 119static void blst_radix_print(blmeta_t *scan, daddr_t blk, 120 daddr_t radix, int skip, int tab); 121#endif 122 123#ifdef KERNEL 124static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); 125#endif 126 127/* 128 * blist_create() - create a blist capable of handling up to the specified 129 * number of blocks 130 * 131 * blocks must be greater then 0 132 * 133 * The smallest blist consists of a single leaf node capable of 134 * managing BLIST_BMAP_RADIX blocks. 135 */ 136 137blist_t 138blist_create(daddr_t blocks) 139{ 140 blist_t bl; 141 int radix; 142 int skip = 0; 143 144 /* 145 * Calculate radix and skip field used for scanning. 146 */ 147 radix = BLIST_BMAP_RADIX; 148 149 while (radix < blocks) { 150 radix <<= BLIST_META_RADIX_SHIFT; 151 skip = (skip + 1) << BLIST_META_RADIX_SHIFT; 152 } 153 154 bl = malloc(sizeof(struct blist), M_SWAP, M_WAITOK); 155 156 bzero(bl, sizeof(*bl)); 157 158 bl->bl_blocks = blocks; 159 bl->bl_radix = radix; 160 bl->bl_skip = skip; 161 bl->bl_rootblks = 1 + 162 blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 163 bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, M_WAITOK); 164 165#if defined(BLIST_DEBUG) 166 printf( 167 "BLIST representing %d blocks (%d MB of swap)" 168 ", requiring %dK of ram\n", 169 bl->bl_blocks, 170 bl->bl_blocks * 4 / 1024, 171 (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 172 ); 173 printf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks); 174#endif 175 blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 176 177 return(bl); 178} 179 180void 181blist_destroy(blist_t bl) 182{ 183 free(bl->bl_root, M_SWAP); 184 free(bl, M_SWAP); 185} 186 187/* 188 * blist_alloc() - reserve space in the block bitmap. Return the base 189 * of a contiguous region or SWAPBLK_NONE if space could 190 * not be allocated. 191 */ 192 193daddr_t 194blist_alloc(blist_t bl, daddr_t count) 195{ 196 daddr_t blk = SWAPBLK_NONE; 197 198 if (bl) { 199 if (bl->bl_radix == BLIST_BMAP_RADIX) 200 blk = blst_leaf_alloc(bl->bl_root, 0, count); 201 else 202 blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 203 if (blk != SWAPBLK_NONE) 204 bl->bl_free -= count; 205 } 206 return(blk); 207} 208 209/* 210 * blist_free() - free up space in the block bitmap. Return the base 211 * of a contiguous region. Panic if an inconsistancy is 212 * found. 213 */ 214 215void 216blist_free(blist_t bl, daddr_t blkno, daddr_t count) 217{ 218 if (bl) { 219 if (bl->bl_radix == BLIST_BMAP_RADIX) 220 blst_leaf_free(bl->bl_root, blkno, count); 221 else 222 blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 223 bl->bl_free += count; 224 } 225} 226 227/* 228 * blist_resize() - resize an existing radix tree to handle the 229 * specified number of blocks. This will reallocate 230 * the tree and transfer the previous bitmap to the new 231 * one. When extending the tree you can specify whether 232 * the new blocks are to left allocated or freed. 233 */ 234 235void 236blist_resize(blist_t *pbl, daddr_t count, int freenew) 237{ 238 blist_t newbl = blist_create(count); 239 blist_t save = *pbl; 240 241 *pbl = newbl; 242 if (count > save->bl_blocks) 243 count = save->bl_blocks; 244 blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 245 246 /* 247 * If resizing upwards, should we free the new space or not? 248 */ 249 if (freenew && count < newbl->bl_blocks) { 250 blist_free(newbl, count, newbl->bl_blocks - count); 251 } 252 blist_destroy(save); 253} 254 255#ifdef BLIST_DEBUG 256 257/* 258 * blist_print() - dump radix tree 259 */ 260 261void 262blist_print(blist_t bl) 263{ 264 printf("BLIST {\n"); 265 blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 266 printf("}\n"); 267} 268 269#endif 270 271/************************************************************************ 272 * ALLOCATION SUPPORT FUNCTIONS * 273 ************************************************************************ 274 * 275 * These support functions do all the actual work. They may seem 276 * rather longish, but that's because I've commented them up. The 277 * actual code is straight forward. 278 * 279 */ 280 281/* 282 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 283 * 284 * This is the core of the allocator and is optimized for the 1 block 285 * and the BLIST_BMAP_RADIX block allocation cases. Other cases are 286 * somewhat slower. The 1 block allocation case is log2 and extremely 287 * quick. 288 */ 289 290static daddr_t 291blst_leaf_alloc( 292 blmeta_t *scan, 293 daddr_t blk, 294 int count 295) { 296 u_daddr_t orig = scan->u.bmu_bitmap; 297 298 if (orig == 0) { 299 /* 300 * Optimize bitmap all-allocated case. Also, count = 1 301 * case assumes at least 1 bit is free in the bitmap, so 302 * we have to take care of this case here. 303 */ 304 scan->bm_bighint = 0; 305 return(SWAPBLK_NONE); 306 } 307 if (count == 1) { 308 /* 309 * Optimized code to allocate one bit out of the bitmap 310 */ 311 u_daddr_t mask; 312 int j = BLIST_BMAP_RADIX/2; 313 int r = 0; 314 315 mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX/2); 316 317 while (j) { 318 if ((orig & mask) == 0) { 319 r += j; 320 orig >>= j; 321 } 322 j >>= 1; 323 mask >>= j; 324 } 325 scan->u.bmu_bitmap &= ~(1 << r); 326 return(blk + r); 327 } 328 if (count <= BLIST_BMAP_RADIX) { 329 /* 330 * non-optimized code to allocate N bits out of the bitmap. 331 * The more bits, the faster the code runs. It will run 332 * the slowest allocating 2 bits, but since there aren't any 333 * memory ops in the core loop (or shouldn't be, anyway), 334 * you probably won't notice the difference. 335 */ 336 int j; 337 int n = BLIST_BMAP_RADIX - count; 338 u_daddr_t mask; 339 340 mask = (u_daddr_t)-1 >> n; 341 342 for (j = 0; j <= n; ++j) { 343 if ((orig & mask) == mask) { 344 scan->u.bmu_bitmap &= ~mask; 345 return(blk + j); 346 } 347 mask = (mask << 1); 348 } 349 } 350 /* 351 * We couldn't allocate count in this subtree, update bighint. 352 */ 353 scan->bm_bighint = count - 1; 354 return(SWAPBLK_NONE); 355} 356 357/* 358 * blist_meta_alloc() - allocate at a meta in the radix tree. 359 * 360 * Attempt to allocate at a meta node. If we can't, we update 361 * bighint and return a failure. Updating bighint optimize future 362 * calls that hit this node. We have to check for our collapse cases 363 * and we have a few optimizations strewn in as well. 364 */ 365 366static daddr_t 367blst_meta_alloc( 368 blmeta_t *scan, 369 daddr_t blk, 370 daddr_t count, 371 daddr_t radix, 372 int skip 373) { 374 int i; 375 int next_skip = (skip >> BLIST_META_RADIX_SHIFT); 376 377 if (scan->u.bmu_avail == 0) { 378 /* 379 * ALL-ALLOCATED special case 380 */ 381 scan->bm_bighint = count; 382 return(SWAPBLK_NONE); 383 } 384 385 if (scan->u.bmu_avail == radix) { 386 radix >>= BLIST_META_RADIX_SHIFT; 387 388 /* 389 * ALL-FREE special case, initialize uninitialize 390 * sublevel. 391 */ 392 for (i = 1; i <= skip; i += next_skip) { 393 if (scan[i].bm_bighint == (daddr_t)-1) 394 break; 395 if (next_skip == 1) { 396 scan[i].u.bmu_bitmap = (u_daddr_t)-1; 397 scan[i].bm_bighint = BLIST_BMAP_RADIX; 398 } else { 399 scan[i].bm_bighint = radix; 400 scan[i].u.bmu_avail = radix; 401 } 402 } 403 } else { 404 radix >>= BLIST_META_RADIX_SHIFT; 405 } 406 407 for (i = 1; i <= skip; i += next_skip) { 408 if (count <= scan[i].bm_bighint) { 409 /* 410 * count fits in object 411 */ 412 daddr_t r; 413 if (next_skip == 1) { 414 r = blst_leaf_alloc(&scan[i], blk, count); 415 } else { 416 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 417 } 418 if (r != SWAPBLK_NONE) { 419 scan->u.bmu_avail -= count; 420 if (scan->bm_bighint > scan->u.bmu_avail) 421 scan->bm_bighint = scan->u.bmu_avail; 422 return(r); 423 } 424 } else if (scan[i].bm_bighint == (daddr_t)-1) { 425 /* 426 * Terminator 427 */ 428 break; 429 } else if (count > radix) { 430 /* 431 * count does not fit in object even if it were 432 * complete free. 433 */ 434 panic("blist_meta_alloc: allocation too large"); 435 } 436 blk += radix; 437 } 438 439 /* 440 * We couldn't allocate count in this subtree, update bighint. 441 */ 442 if (scan->bm_bighint >= count) 443 scan->bm_bighint = count - 1; 444 return(SWAPBLK_NONE); 445} 446 447/* 448 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 449 * 450 */ 451 452static void 453blst_leaf_free( 454 blmeta_t *scan, 455 daddr_t blk, 456 int count 457) { 458 /* 459 * free some data in this bitmap 460 * 461 * e.g. 462 * 0000111111111110000 463 * \_________/\__/ 464 * v n 465 */ 466 int n = blk & (BLIST_BMAP_RADIX - 1); 467 u_daddr_t mask; 468 469 mask = ((u_daddr_t)-1 << n) & 470 ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 471 472 if (scan->u.bmu_bitmap & mask) 473 panic("blst_radix_free: freeing free block"); 474 scan->u.bmu_bitmap |= mask; 475 476 /* 477 * We could probably do a better job here. We are required to make 478 * bighint at least as large as the biggest contiguous block of 479 * data. If we just shoehorn it, a little extra overhead will 480 * be incured on the next allocation (but only that one typically). 481 */ 482 scan->bm_bighint = BLIST_BMAP_RADIX; 483} 484 485/* 486 * BLST_META_FREE() - free allocated blocks from radix tree meta info 487 * 488 * This support routine frees a range of blocks from the bitmap. 489 * The range must be entirely enclosed by this radix node. If a 490 * meta node, we break the range down recursively to free blocks 491 * in subnodes (which means that this code can free an arbitrary 492 * range whereas the allocation code cannot allocate an arbitrary 493 * range). 494 */ 495 496static void 497blst_meta_free( 498 blmeta_t *scan, 499 daddr_t freeBlk, 500 daddr_t count, 501 daddr_t radix, 502 int skip, 503 daddr_t blk 504) { 505 int i; 506 int next_skip = (skip >> BLIST_META_RADIX_SHIFT); 507 508#if 0 509 printf("FREE (%x,%d) FROM (%x,%d)\n", 510 freeBlk, count, 511 blk, radix 512 ); 513#endif 514 515 if (scan->u.bmu_avail == 0) { 516 /* 517 * ALL-ALLOCATED special case, with possible 518 * shortcut to ALL-FREE special case. 519 */ 520 scan->u.bmu_avail = count; 521 scan->bm_bighint = count; 522 523 if (count != radix) { 524 for (i = 1; i <= skip; i += next_skip) { 525 if (scan[i].bm_bighint == (daddr_t)-1) 526 break; 527 scan[i].bm_bighint = 0; 528 if (next_skip == 1) { 529 scan[i].u.bmu_bitmap = 0; 530 } else { 531 scan[i].u.bmu_avail = 0; 532 } 533 } 534 /* fall through */ 535 } 536 } else { 537 scan->u.bmu_avail += count; 538 /* scan->bm_bighint = radix; */ 539 } 540 541 /* 542 * ALL-FREE special case. 543 */ 544 545 if (scan->u.bmu_avail == radix) 546 return; 547#if !defined(MAX_PERF) 548 if (scan->u.bmu_avail > radix) 549 panic("blst_meta_free: freeing already free blocks (%d) %d/%d", count, scan->u.bmu_avail, radix); 550#endif 551 552 /* 553 * Break the free down into its components 554 */ 555 556 radix >>= BLIST_META_RADIX_SHIFT; 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 593static 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_SHIFT; 647 next_skip = (skip >> BLIST_META_RADIX_SHIFT); 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 689static daddr_t 690blst_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_SHIFT; 720 next_skip = (skip >> BLIST_META_RADIX_SHIFT); 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 761static void 762blst_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_SHIFT; 808 next_skip = (skip >> BLIST_META_RADIX_SHIFT); 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 842int 843main(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 915void 916panic(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