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.2 2007/04/19 03:16:33 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 * radix); 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 (count > radix) { 443 /* 444 * count does not fit in object even if it were 445 * completely free. 446 */ 447 break; 448 } 449 blk += radix; 450 mask <<= 2; 451 pmask <<= 2; 452 } 453 454 /* 455 * We couldn't allocate count in this subtree, update bighint. 456 */ 457 if (scan->bm_bighint >= count) 458 scan->bm_bighint = count >> 1; 459 return(ALIST_BLOCK_NONE); 460 } 461 462 /* 463 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 464 * 465 */ 466 static void 467 alst_leaf_free( 468 almeta_t *scan, 469 daddr_t blk, 470 int count 471 ) { 472 /* 473 * free some data in this bitmap 474 * 475 * e.g. 476 * 0000111111111110000 477 * \_________/\__/ 478 * v n 479 */ 480 int n = blk & (ALIST_BMAP_RADIX - 1); 481 u_daddr_t mask; 482 483 mask = ((u_daddr_t)-1 << n) & 484 ((u_daddr_t)-1 >> (ALIST_BMAP_RADIX - count - n)); 485 486 if (scan->bm_bitmap & mask) 487 panic("alst_radix_free: freeing free block"); 488 scan->bm_bitmap |= mask; 489 490 /* 491 * We could probably do a better job here. We are required to make 492 * bighint at least as large as the biggest contiguous block of 493 * data. If we just shoehorn it, a little extra overhead will 494 * be incured on the next allocation (but only that one typically). 495 */ 496 scan->bm_bighint = ALIST_BMAP_RADIX; 497 } 498 499 /* 500 * BLST_META_FREE() - free allocated blocks from radix tree meta info 501 * 502 * This support routine frees a range of blocks from the bitmap. 503 * The range must be entirely enclosed by this radix node. If a 504 * meta node, we break the range down recursively to free blocks 505 * in subnodes (which means that this code can free an arbitrary 506 * range whereas the allocation code cannot allocate an arbitrary 507 * range). 508 */ 509 510 static void 511 alst_meta_free( 512 almeta_t *scan, 513 daddr_t freeBlk, 514 daddr_t count, 515 daddr_t radix, 516 int skip, 517 daddr_t blk 518 ) { 519 int next_skip = ((u_int)skip / ALIST_META_RADIX); 520 u_daddr_t mask; 521 u_daddr_t pmask; 522 int i; 523 524 /* 525 * Break the free down into its components. Because it is so easy 526 * to implement, frees are not limited to power-of-2 sizes. 527 * 528 * Each block in a meta-node bitmap takes two bits. 529 */ 530 radix /= ALIST_META_RADIX; 531 532 i = (freeBlk - blk) / radix; 533 blk += i * radix; 534 mask = 0x00000003 << (i * 2); 535 pmask = 0x00000001 << (i * 2); 536 537 i = i * next_skip + 1; 538 539 while (i <= skip && blk < freeBlk + count) { 540 daddr_t v; 541 542 v = blk + radix - freeBlk; 543 if (v > count) 544 v = count; 545 546 if (scan->bm_bighint == (daddr_t)-1) 547 panic("alst_meta_free: freeing unexpected range"); 548 549 if (freeBlk == blk && count >= radix) { 550 /* 551 * All-free case, no need to update sub-tree 552 */ 553 scan->bm_bitmap |= mask; 554 scan->bm_bighint = radix * ALIST_META_RADIX;/*XXX*/ 555 } else { 556 /* 557 * Recursion case 558 */ 559 if (next_skip == 1) 560 alst_leaf_free(&scan[i], freeBlk, v); 561 else 562 alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 563 if (scan[i].bm_bitmap == (u_daddr_t)-1) 564 scan->bm_bitmap |= mask; 565 else 566 scan->bm_bitmap |= pmask; 567 if (scan->bm_bighint < scan[i].bm_bighint) 568 scan->bm_bighint = scan[i].bm_bighint; 569 } 570 mask <<= 2; 571 pmask <<= 2; 572 count -= v; 573 freeBlk += v; 574 blk += radix; 575 i += next_skip; 576 } 577 } 578 579 /* 580 * BLST_RADIX_INIT() - initialize radix tree 581 * 582 * Initialize our meta structures and bitmaps and calculate the exact 583 * amount of space required to manage 'count' blocks - this space may 584 * be considerably less then the calculated radix due to the large 585 * RADIX values we use. 586 */ 587 588 static daddr_t 589 alst_radix_init(almeta_t *scan, daddr_t radix, int skip, daddr_t count) 590 { 591 int i; 592 int next_skip; 593 daddr_t memindex = 0; 594 u_daddr_t mask; 595 u_daddr_t pmask; 596 597 /* 598 * Leaf node 599 */ 600 if (radix == ALIST_BMAP_RADIX) { 601 if (scan) { 602 scan->bm_bighint = 0; 603 scan->bm_bitmap = 0; 604 } 605 return(memindex); 606 } 607 608 /* 609 * Meta node. If allocating the entire object we can special 610 * case it. However, we need to figure out how much memory 611 * is required to manage 'count' blocks, so we continue on anyway. 612 */ 613 614 if (scan) { 615 scan->bm_bighint = 0; 616 scan->bm_bitmap = 0; 617 } 618 619 radix /= ALIST_META_RADIX; 620 next_skip = ((u_int)skip / ALIST_META_RADIX); 621 mask = 0x00000003; 622 pmask = 0x00000001; 623 624 for (i = 1; i <= skip; i += next_skip) { 625 if (count >= radix) { 626 /* 627 * Allocate the entire object 628 */ 629 memindex = i + alst_radix_init( 630 ((scan) ? &scan[i] : NULL), 631 radix, 632 next_skip - 1, 633 radix 634 ); 635 count -= radix; 636 /* already marked as wholely allocated */ 637 } else if (count > 0) { 638 /* 639 * Allocate a partial object 640 */ 641 memindex = i + alst_radix_init( 642 ((scan) ? &scan[i] : NULL), 643 radix, 644 next_skip - 1, 645 count 646 ); 647 count = 0; 648 649 /* 650 * Mark as partially allocated 651 */ 652 if (scan) 653 scan->bm_bitmap |= pmask; 654 } else { 655 /* 656 * Add terminator and break out 657 */ 658 if (scan) 659 scan[i].bm_bighint = (daddr_t)-1; 660 /* already marked as wholely allocated */ 661 break; 662 } 663 mask <<= 2; 664 pmask <<= 2; 665 } 666 if (memindex < i) 667 memindex = i; 668 return(memindex); 669 } 670 671 #ifdef ALIST_DEBUG 672 673 static void 674 alst_radix_print(almeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) 675 { 676 int i; 677 int next_skip; 678 int lastState = 0; 679 u_daddr_t mask; 680 681 if (radix == ALIST_BMAP_RADIX) { 682 kprintf( 683 "%*.*s(%04x,%d): bitmap %08x big=%d\n", 684 tab, tab, "", 685 blk, radix, 686 scan->bm_bitmap, 687 scan->bm_bighint 688 ); 689 return; 690 } 691 692 if (scan->bm_bitmap == 0) { 693 kprintf( 694 "%*.*s(%04x,%d) ALL ALLOCATED\n", 695 tab, tab, "", 696 blk, 697 radix 698 ); 699 return; 700 } 701 if (scan->bm_bitmap == (u_daddr_t)-1) { 702 kprintf( 703 "%*.*s(%04x,%d) ALL FREE\n", 704 tab, tab, "", 705 blk, 706 radix 707 ); 708 return; 709 } 710 711 kprintf( 712 "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n", 713 tab, tab, "", 714 blk, radix, 715 radix, 716 scan->bm_bitmap, 717 scan->bm_bighint 718 ); 719 720 radix /= ALIST_META_RADIX; 721 next_skip = ((u_int)skip / ALIST_META_RADIX); 722 tab += 4; 723 mask = 0x00000003; 724 725 for (i = 1; i <= skip; i += next_skip) { 726 if (scan[i].bm_bighint == (daddr_t)-1) { 727 kprintf( 728 "%*.*s(%04x,%d): Terminator\n", 729 tab, tab, "", 730 blk, radix 731 ); 732 lastState = 0; 733 break; 734 } 735 if ((scan->bm_bitmap & mask) == mask) { 736 kprintf( 737 "%*.*s(%04x,%d): ALL FREE\n", 738 tab, tab, "", 739 blk, radix 740 ); 741 } else if ((scan->bm_bitmap & mask) == 0) { 742 kprintf( 743 "%*.*s(%04x,%d): ALL ALLOCATED\n", 744 tab, tab, "", 745 blk, radix 746 ); 747 } else { 748 alst_radix_print( 749 &scan[i], 750 blk, 751 radix, 752 next_skip - 1, 753 tab 754 ); 755 } 756 blk += radix; 757 mask <<= 2; 758 } 759 tab -= 4; 760 761 kprintf( 762 "%*.*s}\n", 763 tab, tab, "" 764 ); 765 } 766 767 #endif 768 769 #ifdef ALIST_DEBUG 770 771 int 772 main(int ac, char **av) 773 { 774 int size = 1024; 775 int i; 776 alist_t bl; 777 778 for (i = 1; i < ac; ++i) { 779 const char *ptr = av[i]; 780 if (*ptr != '-') { 781 size = strtol(ptr, NULL, 0); 782 continue; 783 } 784 ptr += 2; 785 fprintf(stderr, "Bad option: %s\n", ptr - 2); 786 exit(1); 787 } 788 bl = alist_create(size, NULL); 789 alist_free(bl, 0, size); 790 791 for (;;) { 792 char buf[1024]; 793 daddr_t da = 0; 794 daddr_t count = 0; 795 796 797 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix); 798 fflush(stdout); 799 if (fgets(buf, sizeof(buf), stdin) == NULL) 800 break; 801 switch(buf[0]) { 802 case 'p': 803 alist_print(bl); 804 break; 805 case 'a': 806 if (sscanf(buf + 1, "%d", &count) == 1) { 807 daddr_t blk = alist_alloc(bl, count); 808 kprintf(" R=%04x\n", blk); 809 } else { 810 kprintf("?\n"); 811 } 812 break; 813 case 'f': 814 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 815 alist_free(bl, da, count); 816 } else { 817 kprintf("?\n"); 818 } 819 break; 820 case '?': 821 case 'h': 822 puts( 823 "p -print\n" 824 "a %d -allocate\n" 825 "f %x %d -free\n" 826 "h/? -help" 827 ); 828 break; 829 default: 830 kprintf("?\n"); 831 break; 832 } 833 } 834 return(0); 835 } 836 837 void 838 panic(const char *ctl, ...) 839 { 840 __va_list va; 841 842 __va_start(va, ctl); 843 vfprintf(stderr, ctl, va); 844 fprintf(stderr, "\n"); 845 __va_end(va); 846 exit(1); 847 } 848 849 #endif 850 851