1 /* 2 * ALIST.C - Bitmap allocator/deallocator, using a radix tree with hinting. 3 * Unlimited-size allocations, power-of-2 only, power-of-2 4 * aligned results only. 5 * 6 * Copyright (c) 2007 The DragonFly Project. All rights reserved. 7 * 8 * This code is derived from software contributed to The DragonFly Project 9 * by Matthew Dillon <dillon@backplane.com> 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in 19 * the documentation and/or other materials provided with the 20 * distribution. 21 * 3. Neither the name of The DragonFly Project nor the names of its 22 * contributors may be used to endorse or promote products derived 23 * from this software without specific, prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 29 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 30 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 33 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 34 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 35 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 * 38 * $DragonFly: src/sys/kern/subr_alist.c,v 1.1 2007/04/09 17:10:00 dillon Exp $ 39 */ 40 /* 41 * This module has been adapted from the BLIST module, which was written 42 * by Matthew Dillon many years ago. 43 * 44 * This module implements a general power-of-2 bitmap allocator/deallocator. 45 * All allocations must be in powers of 2 and will return similarly aligned 46 * results. The module does not try to interpret the meaning of a 'block' 47 * other then to return ALIST_BLOCK_NONE on an allocation failure. 48 * 49 * A maximum of 2 billion blocks is supported so, for example, if one block 50 * represented 64 bytes a maximally sized ALIST would represent 51 * 128 gigabytes. 52 * 53 * A radix tree is used to maintain the bitmap and layed out in a manner 54 * similar to the blist code. Meta nodes use a radix of 16 and 2 bits per 55 * block while leaf nodes use a radix of 32 and 1 bit per block (stored in 56 * a 32 bit bitmap field). Both meta and leaf nodes have a hint field. 57 * This field gives us a hint as to the largest free contiguous range of 58 * blocks under the node. It may contain a value that is too high, but 59 * will never contain a value that is too low. When the radix tree is 60 * searched, allocation failures in subtrees update the hint. 61 * 62 * The radix tree is layed out recursively using a linear array. Each meta 63 * node is immediately followed (layed out sequentially in memory) by 64 * ALIST_META_RADIX lower level nodes. This is a recursive structure but one 65 * that can be easily scanned through a very simple 'skip' calculation. In 66 * order to support large radixes, portions of the tree may reside outside our 67 * memory allocation. We handle this with an early-terminate optimization 68 * in the meta-node. The memory allocation is only large enough to cover 69 * the number of blocks requested at creation time even if it must be 70 * encompassed in larger root-node radix. 71 * 72 * This code can be compiled stand-alone for debugging. 73 */ 74 75 #ifdef _KERNEL 76 77 #include <sys/param.h> 78 #include <sys/systm.h> 79 #include <sys/lock.h> 80 #include <sys/kernel.h> 81 #include <sys/alist.h> 82 #include <sys/malloc.h> 83 #include <vm/vm.h> 84 #include <vm/vm_object.h> 85 #include <vm/vm_kern.h> 86 #include <vm/vm_extern.h> 87 #include <vm/vm_page.h> 88 89 #else 90 91 #ifndef ALIST_NO_DEBUG 92 #define ALIST_DEBUG 93 #endif 94 95 #include <sys/types.h> 96 #include <stdio.h> 97 #include <assert.h> 98 #include <string.h> 99 #include <stdlib.h> 100 #include <stdarg.h> 101 102 #define kmalloc(a,b,c) malloc(a) 103 #define kfree(a,b) free(a) 104 #define kprintf printf 105 #define KKASSERT(exp) assert(exp) 106 struct malloc_type; 107 108 typedef unsigned int u_daddr_t; 109 110 #include <sys/alist.h> 111 112 void panic(const char *ctl, ...); 113 114 #endif 115 116 /* 117 * static support functions 118 */ 119 120 static daddr_t alst_leaf_alloc(almeta_t *scan, daddr_t blk, int count); 121 static daddr_t alst_meta_alloc(almeta_t *scan, daddr_t blk, 122 daddr_t count, daddr_t radix, int skip); 123 static void alst_leaf_free(almeta_t *scan, daddr_t relblk, int count); 124 static void alst_meta_free(almeta_t *scan, daddr_t freeBlk, daddr_t count, 125 daddr_t radix, int skip, daddr_t blk); 126 static daddr_t alst_radix_init(almeta_t *scan, daddr_t radix, 127 int skip, daddr_t count); 128 #ifndef _KERNEL 129 static void alst_radix_print(almeta_t *scan, daddr_t blk, 130 daddr_t radix, int skip, int tab); 131 #endif 132 133 /* 134 * alist_create() - create a alist capable of handling up to the specified 135 * number of blocks 136 * 137 * blocks must be greater then 0 138 * 139 * The smallest alist consists of a single leaf node capable of 140 * managing ALIST_BMAP_RADIX blocks. 141 */ 142 143 alist_t 144 alist_create(daddr_t blocks, struct malloc_type *mtype) 145 { 146 alist_t bl; 147 int radix; 148 int skip = 0; 149 150 /* 151 * Calculate radix and skip field used for scanning. 152 */ 153 radix = ALIST_BMAP_RADIX; 154 155 while (radix < blocks) { 156 radix *= ALIST_META_RADIX; 157 skip = (skip + 1) * ALIST_META_RADIX; 158 } 159 160 bl = kmalloc(sizeof(struct alist), mtype, M_WAITOK); 161 162 bzero(bl, sizeof(*bl)); 163 164 bl->bl_blocks = blocks; 165 bl->bl_radix = radix; 166 bl->bl_skip = skip; 167 bl->bl_rootblks = 1 + 168 alst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 169 bl->bl_root = kmalloc(sizeof(almeta_t) * bl->bl_rootblks, mtype, M_WAITOK); 170 171 #if defined(ALIST_DEBUG) 172 kprintf( 173 "ALIST representing %d blocks (%d MB of swap)" 174 ", requiring %dK of ram\n", 175 bl->bl_blocks, 176 bl->bl_blocks * 4 / 1024, 177 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024 178 ); 179 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks); 180 #endif 181 alst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 182 183 return(bl); 184 } 185 186 void 187 alist_destroy(alist_t bl, struct malloc_type *mtype) 188 { 189 kfree(bl->bl_root, mtype); 190 kfree(bl, mtype); 191 } 192 193 /* 194 * alist_alloc() - reserve space in the block bitmap. Return the base 195 * of a contiguous region or ALIST_BLOCK_NONE if space 196 * could not be allocated. 197 */ 198 199 daddr_t 200 alist_alloc(alist_t bl, daddr_t count) 201 { 202 daddr_t blk = ALIST_BLOCK_NONE; 203 204 KKASSERT((count | (count - 1)) == (count << 1) - 1); 205 206 if (bl && count < bl->bl_radix) { 207 if (bl->bl_radix == ALIST_BMAP_RADIX) 208 blk = alst_leaf_alloc(bl->bl_root, 0, count); 209 else 210 blk = alst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 211 if (blk != ALIST_BLOCK_NONE) 212 bl->bl_free -= count; 213 } 214 return(blk); 215 } 216 217 /* 218 * alist_free() - free up space in the block bitmap. Return the base 219 * of a contiguous region. Panic if an inconsistancy is 220 * found. 221 */ 222 223 void 224 alist_free(alist_t bl, daddr_t blkno, daddr_t count) 225 { 226 if (bl) { 227 KKASSERT(blkno + count <= bl->bl_blocks); 228 if (bl->bl_radix == ALIST_BMAP_RADIX) 229 alst_leaf_free(bl->bl_root, blkno, count); 230 else 231 alst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 232 bl->bl_free += count; 233 } 234 } 235 236 #ifdef ALIST_DEBUG 237 238 /* 239 * alist_print() - dump radix tree 240 */ 241 242 void 243 alist_print(alist_t bl) 244 { 245 kprintf("ALIST {\n"); 246 alst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 247 kprintf("}\n"); 248 } 249 250 #endif 251 252 /************************************************************************ 253 * ALLOCATION SUPPORT FUNCTIONS * 254 ************************************************************************ 255 * 256 * These support functions do all the actual work. They may seem 257 * rather longish, but that's because I've commented them up. The 258 * actual code is straight forward. 259 * 260 */ 261 262 /* 263 * alist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 264 * 265 * This is the core of the allocator and is optimized for the 1 block 266 * and the ALIST_BMAP_RADIX block allocation cases. Other cases are 267 * somewhat slower. The 1 block allocation case is log2 and extremely 268 * quick. 269 */ 270 271 static daddr_t 272 alst_leaf_alloc( 273 almeta_t *scan, 274 daddr_t blk, 275 int count 276 ) { 277 u_daddr_t orig = scan->bm_bitmap; 278 279 /* 280 * Optimize bitmap all-allocated case. Also, count = 1 281 * case assumes at least 1 bit is free in the bitmap, so 282 * we have to take care of this case here. 283 */ 284 if (orig == 0) { 285 scan->bm_bighint = 0; 286 return(ALIST_BLOCK_NONE); 287 } 288 289 /* 290 * Optimized code to allocate one bit out of the bitmap 291 */ 292 if (count == 1) { 293 u_daddr_t mask; 294 int j = ALIST_BMAP_RADIX/2; 295 int r = 0; 296 297 mask = (u_daddr_t)-1 >> (ALIST_BMAP_RADIX/2); 298 299 while (j) { 300 if ((orig & mask) == 0) { 301 r += j; 302 orig >>= j; 303 } 304 j >>= 1; 305 mask >>= j; 306 } 307 scan->bm_bitmap &= ~(1 << r); 308 return(blk + r); 309 } 310 311 /* 312 * non-optimized code to allocate N bits out of the bitmap. 313 * The more bits, the faster the code runs. It will run 314 * the slowest allocating 2 bits, but since there aren't any 315 * memory ops in the core loop (or shouldn't be, anyway), 316 * you probably won't notice the difference. 317 * 318 * Similar to the blist case, the alist code also requires 319 * allocations to be power-of-2 sized and aligned to the 320 * size of the allocation, which simplifies the algorithm. 321 */ 322 { 323 int j; 324 int n = ALIST_BMAP_RADIX - count; 325 u_daddr_t mask; 326 327 mask = (u_daddr_t)-1 >> n; 328 329 for (j = 0; j <= n; j += count) { 330 if ((orig & mask) == mask) { 331 scan->bm_bitmap &= ~mask; 332 return(blk + j); 333 } 334 mask = mask << count; 335 } 336 } 337 338 /* 339 * We couldn't allocate count in this subtree, update bighint. 340 */ 341 scan->bm_bighint = count - 1; 342 return(ALIST_BLOCK_NONE); 343 } 344 345 /* 346 * alist_meta_alloc() - allocate at a meta in the radix tree. 347 * 348 * Attempt to allocate at a meta node. If we can't, we update 349 * bighint and return a failure. Updating bighint optimize future 350 * calls that hit this node. We have to check for our collapse cases 351 * and we have a few optimizations strewn in as well. 352 */ 353 354 static daddr_t 355 alst_meta_alloc( 356 almeta_t *scan, 357 daddr_t blk, 358 daddr_t count, 359 daddr_t radix, 360 int skip 361 ) { 362 int i; 363 u_daddr_t mask; 364 u_daddr_t pmask; 365 int next_skip = ((u_int)skip / ALIST_META_RADIX); 366 367 /* 368 * ALL-ALLOCATED special case 369 */ 370 if (scan->bm_bitmap == 0) { 371 scan->bm_bighint = 0; 372 return(ALIST_BLOCK_NONE); 373 } 374 375 radix /= ALIST_META_RADIX; 376 377 /* 378 * Radix now represents each bitmap entry for this meta node. If 379 * the number of blocks being allocated can be fully represented, 380 * we allocate directly out of this meta node. 381 * 382 * Meta node bitmaps use 2 bits per block. 383 * 384 * 00 ALL-ALLOCATED 385 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED 386 * 10 (RESERVED) 387 * 11 ALL-FREE 388 */ 389 if (count >= radix) { 390 int n = count / radix * 2; /* number of bits */ 391 int j; 392 393 mask = (u_daddr_t)-1 >> (ALIST_BMAP_RADIX - n); 394 for (j = 0; j < ALIST_META_RADIX; j += n / 2) { 395 if ((scan->bm_bitmap & mask) == mask) { 396 scan->bm_bitmap &= ~mask; 397 return(blk + j); 398 } 399 mask <<= n; 400 } 401 if (scan->bm_bighint >= count) 402 scan->bm_bighint = count >> 1; 403 return(ALIST_BLOCK_NONE); 404 } 405 406 /* 407 * If not we have to recurse. 408 */ 409 mask = 0x00000003; 410 pmask = 0x00000001; 411 for (i = 1; i <= skip; i += next_skip) { 412 if (scan[i].bm_bighint == (daddr_t)-1) { 413 /* 414 * Terminator 415 */ 416 break; 417 } 418 if ((scan->bm_bitmap & mask) == mask) { 419 scan[i].bm_bitmap = (u_daddr_t)-1; 420 scan[i].bm_bighint = radix; 421 } 422 423 if (count <= scan[i].bm_bighint) { 424 /* 425 * count fits in object 426 */ 427 daddr_t r; 428 if (next_skip == 1) { 429 r = alst_leaf_alloc(&scan[i], blk, count); 430 } else { 431 r = alst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 432 } 433 if (r != ALIST_BLOCK_NONE) { 434 if (scan[i].bm_bitmap == 0) { 435 scan->bm_bitmap &= ~mask; 436 } else { 437 scan->bm_bitmap &= ~mask; 438 scan->bm_bitmap |= pmask; 439 } 440 return(r); 441 } 442 } else if (scan[i].bm_bighint == (daddr_t)-1) { 443 /* 444 * Terminator 445 */ 446 break; 447 } else if (count > radix) { 448 /* 449 * count does not fit in object even if it were 450 * completely free. 451 */ 452 break; 453 } 454 blk += radix; 455 mask <<= 2; 456 pmask <<= 2; 457 } 458 459 /* 460 * We couldn't allocate count in this subtree, update bighint. 461 */ 462 if (scan->bm_bighint >= count) 463 scan->bm_bighint = count >> 1; 464 return(ALIST_BLOCK_NONE); 465 } 466 467 /* 468 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 469 * 470 */ 471 static void 472 alst_leaf_free( 473 almeta_t *scan, 474 daddr_t blk, 475 int count 476 ) { 477 /* 478 * free some data in this bitmap 479 * 480 * e.g. 481 * 0000111111111110000 482 * \_________/\__/ 483 * v n 484 */ 485 int n = blk & (ALIST_BMAP_RADIX - 1); 486 u_daddr_t mask; 487 488 mask = ((u_daddr_t)-1 << n) & 489 ((u_daddr_t)-1 >> (ALIST_BMAP_RADIX - count - n)); 490 491 if (scan->bm_bitmap & mask) 492 panic("alst_radix_free: freeing free block"); 493 scan->bm_bitmap |= mask; 494 495 /* 496 * We could probably do a better job here. We are required to make 497 * bighint at least as large as the biggest contiguous block of 498 * data. If we just shoehorn it, a little extra overhead will 499 * be incured on the next allocation (but only that one typically). 500 */ 501 scan->bm_bighint = ALIST_BMAP_RADIX; 502 } 503 504 /* 505 * BLST_META_FREE() - free allocated blocks from radix tree meta info 506 * 507 * This support routine frees a range of blocks from the bitmap. 508 * The range must be entirely enclosed by this radix node. If a 509 * meta node, we break the range down recursively to free blocks 510 * in subnodes (which means that this code can free an arbitrary 511 * range whereas the allocation code cannot allocate an arbitrary 512 * range). 513 */ 514 515 static void 516 alst_meta_free( 517 almeta_t *scan, 518 daddr_t freeBlk, 519 daddr_t count, 520 daddr_t radix, 521 int skip, 522 daddr_t blk 523 ) { 524 int next_skip = ((u_int)skip / ALIST_META_RADIX); 525 u_daddr_t mask; 526 u_daddr_t pmask; 527 int i; 528 529 /* 530 * Break the free down into its components. Because it is so easy 531 * to implement, frees are not limited to power-of-2 sizes. 532 * 533 * Each block in a meta-node bitmap takes two bits. 534 */ 535 radix /= ALIST_META_RADIX; 536 537 i = (freeBlk - blk) / radix; 538 blk += i * radix; 539 mask = 0x00000003 << (i * 2); 540 pmask = 0x00000001 << (i * 2); 541 542 i = i * next_skip + 1; 543 544 while (i <= skip && blk < freeBlk + count) { 545 daddr_t v; 546 547 v = blk + radix - freeBlk; 548 if (v > count) 549 v = count; 550 551 if (scan->bm_bighint == (daddr_t)-1) 552 panic("alst_meta_free: freeing unexpected range"); 553 554 if (freeBlk == blk && count >= radix) { 555 /* 556 * All-free case, no need to update sub-tree 557 */ 558 scan->bm_bitmap |= mask; 559 scan->bm_bighint = radix * ALIST_META_RADIX;/*XXX*/ 560 } else { 561 /* 562 * Recursion case 563 */ 564 if (next_skip == 1) 565 alst_leaf_free(&scan[i], freeBlk, v); 566 else 567 alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 568 if (scan[i].bm_bitmap == (u_daddr_t)-1) 569 scan->bm_bitmap |= mask; 570 else 571 scan->bm_bitmap |= pmask; 572 if (scan->bm_bighint < scan[i].bm_bighint) 573 scan->bm_bighint = scan[i].bm_bighint; 574 } 575 mask <<= 2; 576 pmask <<= 2; 577 count -= v; 578 freeBlk += v; 579 blk += radix; 580 i += next_skip; 581 } 582 } 583 584 /* 585 * BLST_RADIX_INIT() - initialize radix tree 586 * 587 * Initialize our meta structures and bitmaps and calculate the exact 588 * amount of space required to manage 'count' blocks - this space may 589 * be considerably less then the calculated radix due to the large 590 * RADIX values we use. 591 */ 592 593 static daddr_t 594 alst_radix_init(almeta_t *scan, daddr_t radix, int skip, daddr_t count) 595 { 596 int i; 597 int next_skip; 598 daddr_t memindex = 0; 599 u_daddr_t mask; 600 u_daddr_t pmask; 601 602 /* 603 * Leaf node 604 */ 605 if (radix == ALIST_BMAP_RADIX) { 606 if (scan) { 607 scan->bm_bighint = 0; 608 scan->bm_bitmap = 0; 609 } 610 return(memindex); 611 } 612 613 /* 614 * Meta node. If allocating the entire object we can special 615 * case it. However, we need to figure out how much memory 616 * is required to manage 'count' blocks, so we continue on anyway. 617 */ 618 619 if (scan) { 620 scan->bm_bighint = 0; 621 scan->bm_bitmap = 0; 622 } 623 624 radix /= ALIST_META_RADIX; 625 next_skip = ((u_int)skip / ALIST_META_RADIX); 626 mask = 0x00000003; 627 pmask = 0x00000001; 628 629 for (i = 1; i <= skip; i += next_skip) { 630 if (count >= radix) { 631 /* 632 * Allocate the entire object 633 */ 634 memindex = i + alst_radix_init( 635 ((scan) ? &scan[i] : NULL), 636 radix, 637 next_skip - 1, 638 radix 639 ); 640 count -= radix; 641 /* already marked as wholely allocated */ 642 } else if (count > 0) { 643 /* 644 * Allocate a partial object 645 */ 646 memindex = i + alst_radix_init( 647 ((scan) ? &scan[i] : NULL), 648 radix, 649 next_skip - 1, 650 count 651 ); 652 count = 0; 653 654 /* 655 * Mark as partially allocated 656 */ 657 if (scan) 658 scan->bm_bitmap |= pmask; 659 } else { 660 /* 661 * Add terminator and break out 662 */ 663 if (scan) 664 scan[i].bm_bighint = (daddr_t)-1; 665 /* already marked as wholely allocated */ 666 break; 667 } 668 mask <<= 2; 669 pmask <<= 2; 670 } 671 if (memindex < i) 672 memindex = i; 673 return(memindex); 674 } 675 676 #ifdef ALIST_DEBUG 677 678 static void 679 alst_radix_print(almeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) 680 { 681 int i; 682 int next_skip; 683 int lastState = 0; 684 u_daddr_t mask; 685 686 if (radix == ALIST_BMAP_RADIX) { 687 kprintf( 688 "%*.*s(%04x,%d): bitmap %08x big=%d\n", 689 tab, tab, "", 690 blk, radix, 691 scan->bm_bitmap, 692 scan->bm_bighint 693 ); 694 return; 695 } 696 697 if (scan->bm_bitmap == 0) { 698 kprintf( 699 "%*.*s(%04x,%d) ALL ALLOCATED\n", 700 tab, tab, "", 701 blk, 702 radix 703 ); 704 return; 705 } 706 if (scan->bm_bitmap == (u_daddr_t)-1) { 707 kprintf( 708 "%*.*s(%04x,%d) ALL FREE\n", 709 tab, tab, "", 710 blk, 711 radix 712 ); 713 return; 714 } 715 716 kprintf( 717 "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n", 718 tab, tab, "", 719 blk, radix, 720 radix, 721 scan->bm_bitmap, 722 scan->bm_bighint 723 ); 724 725 radix /= ALIST_META_RADIX; 726 next_skip = ((u_int)skip / ALIST_META_RADIX); 727 tab += 4; 728 mask = 0x00000003; 729 730 for (i = 1; i <= skip; i += next_skip) { 731 if (scan[i].bm_bighint == (daddr_t)-1) { 732 kprintf( 733 "%*.*s(%04x,%d): Terminator\n", 734 tab, tab, "", 735 blk, radix 736 ); 737 lastState = 0; 738 break; 739 } 740 if ((scan->bm_bitmap & mask) == mask) { 741 kprintf( 742 "%*.*s(%04x,%d): ALL FREE\n", 743 tab, tab, "", 744 blk, radix 745 ); 746 } else if ((scan->bm_bitmap & mask) == 0) { 747 kprintf( 748 "%*.*s(%04x,%d): ALL ALLOCATED\n", 749 tab, tab, "", 750 blk, radix 751 ); 752 } else { 753 alst_radix_print( 754 &scan[i], 755 blk, 756 radix, 757 next_skip - 1, 758 tab 759 ); 760 } 761 blk += radix; 762 mask <<= 2; 763 } 764 tab -= 4; 765 766 kprintf( 767 "%*.*s}\n", 768 tab, tab, "" 769 ); 770 } 771 772 #endif 773 774 #ifdef ALIST_DEBUG 775 776 int 777 main(int ac, char **av) 778 { 779 int size = 1024; 780 int i; 781 alist_t bl; 782 783 for (i = 1; i < ac; ++i) { 784 const char *ptr = av[i]; 785 if (*ptr != '-') { 786 size = strtol(ptr, NULL, 0); 787 continue; 788 } 789 ptr += 2; 790 fprintf(stderr, "Bad option: %s\n", ptr - 2); 791 exit(1); 792 } 793 bl = alist_create(size, NULL); 794 alist_free(bl, 0, size); 795 796 for (;;) { 797 char buf[1024]; 798 daddr_t da = 0; 799 daddr_t count = 0; 800 801 802 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix); 803 fflush(stdout); 804 if (fgets(buf, sizeof(buf), stdin) == NULL) 805 break; 806 switch(buf[0]) { 807 case 'p': 808 alist_print(bl); 809 break; 810 case 'a': 811 if (sscanf(buf + 1, "%d", &count) == 1) { 812 daddr_t blk = alist_alloc(bl, count); 813 kprintf(" R=%04x\n", blk); 814 } else { 815 kprintf("?\n"); 816 } 817 break; 818 case 'f': 819 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 820 alist_free(bl, da, count); 821 } else { 822 kprintf("?\n"); 823 } 824 break; 825 case '?': 826 case 'h': 827 puts( 828 "p -print\n" 829 "a %d -allocate\n" 830 "f %x %d -free\n" 831 "h/? -help" 832 ); 833 break; 834 default: 835 kprintf("?\n"); 836 break; 837 } 838 } 839 return(0); 840 } 841 842 void 843 panic(const char *ctl, ...) 844 { 845 __va_list va; 846 847 __va_start(va, ctl); 848 vfprintf(stderr, ctl, va); 849 fprintf(stderr, "\n"); 850 __va_end(va); 851 exit(1); 852 } 853 854 #endif 855 856