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.4 2008/04/23 17:21:08 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 (%d bytes) of ram\n", 175 bl->bl_blocks, 176 bl->bl_blocks * 4 / 1024, 177 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024, 178 (bl->bl_rootblks * sizeof(almeta_t)) 179 ); 180 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks); 181 #endif 182 alst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 183 184 return(bl); 185 } 186 187 void 188 alist_destroy(alist_t bl, struct malloc_type *mtype) 189 { 190 kfree(bl->bl_root, mtype); 191 kfree(bl, mtype); 192 } 193 194 /* 195 * alist_alloc() - reserve space in the block bitmap. Return the base 196 * of a contiguous region or ALIST_BLOCK_NONE if space 197 * could not be allocated. 198 */ 199 200 daddr_t 201 alist_alloc(alist_t bl, daddr_t count) 202 { 203 daddr_t blk = ALIST_BLOCK_NONE; 204 205 KKASSERT((count | (count - 1)) == (count << 1) - 1); 206 207 if (bl && count < bl->bl_radix) { 208 if (bl->bl_radix == ALIST_BMAP_RADIX) 209 blk = alst_leaf_alloc(bl->bl_root, 0, count); 210 else 211 blk = alst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 212 if (blk != ALIST_BLOCK_NONE) 213 bl->bl_free -= count; 214 } 215 return(blk); 216 } 217 218 /* 219 * alist_free() - free up space in the block bitmap. Return the base 220 * of a contiguous region. Panic if an inconsistancy is 221 * found. 222 */ 223 224 void 225 alist_free(alist_t bl, daddr_t blkno, daddr_t count) 226 { 227 if (bl) { 228 KKASSERT(blkno + count <= bl->bl_blocks); 229 if (bl->bl_radix == ALIST_BMAP_RADIX) 230 alst_leaf_free(bl->bl_root, blkno, count); 231 else 232 alst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 233 bl->bl_free += count; 234 } 235 } 236 237 #ifdef ALIST_DEBUG 238 239 /* 240 * alist_print() - dump radix tree 241 */ 242 243 void 244 alist_print(alist_t bl) 245 { 246 kprintf("ALIST {\n"); 247 alst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 248 kprintf("}\n"); 249 } 250 251 #endif 252 253 /************************************************************************ 254 * ALLOCATION SUPPORT FUNCTIONS * 255 ************************************************************************ 256 * 257 * These support functions do all the actual work. They may seem 258 * rather longish, but that's because I've commented them up. The 259 * actual code is straight forward. 260 * 261 */ 262 263 /* 264 * alist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 265 * 266 * This is the core of the allocator and is optimized for the 1 block 267 * and the ALIST_BMAP_RADIX block allocation cases. Other cases are 268 * somewhat slower. The 1 block allocation case is log2 and extremely 269 * quick. 270 */ 271 272 static daddr_t 273 alst_leaf_alloc( 274 almeta_t *scan, 275 daddr_t blk, 276 int count 277 ) { 278 u_daddr_t orig = scan->bm_bitmap; 279 280 /* 281 * Optimize bitmap all-allocated case. Also, count = 1 282 * case assumes at least 1 bit is free in the bitmap, so 283 * we have to take care of this case here. 284 */ 285 if (orig == 0) { 286 scan->bm_bighint = 0; 287 return(ALIST_BLOCK_NONE); 288 } 289 290 /* 291 * Optimized code to allocate one bit out of the bitmap 292 */ 293 if (count == 1) { 294 u_daddr_t mask; 295 int j = ALIST_BMAP_RADIX/2; 296 int r = 0; 297 298 mask = (u_daddr_t)-1 >> (ALIST_BMAP_RADIX/2); 299 300 while (j) { 301 if ((orig & mask) == 0) { 302 r += j; 303 orig >>= j; 304 } 305 j >>= 1; 306 mask >>= j; 307 } 308 scan->bm_bitmap &= ~(1 << r); 309 return(blk + r); 310 } 311 312 /* 313 * non-optimized code to allocate N bits out of the bitmap. 314 * The more bits, the faster the code runs. It will run 315 * the slowest allocating 2 bits, but since there aren't any 316 * memory ops in the core loop (or shouldn't be, anyway), 317 * you probably won't notice the difference. 318 * 319 * Similar to the blist case, the alist code also requires 320 * allocations to be power-of-2 sized and aligned to the 321 * size of the allocation, which simplifies the algorithm. 322 */ 323 { 324 int j; 325 int n = ALIST_BMAP_RADIX - count; 326 u_daddr_t mask; 327 328 mask = (u_daddr_t)-1 >> n; 329 330 for (j = 0; j <= n; j += count) { 331 if ((orig & mask) == mask) { 332 scan->bm_bitmap &= ~mask; 333 return(blk + j); 334 } 335 mask = mask << count; 336 } 337 } 338 339 /* 340 * We couldn't allocate count in this subtree, update bighint. 341 */ 342 scan->bm_bighint = count - 1; 343 return(ALIST_BLOCK_NONE); 344 } 345 346 /* 347 * alist_meta_alloc() - allocate at a meta in the radix tree. 348 * 349 * Attempt to allocate at a meta node. If we can't, we update 350 * bighint and return a failure. Updating bighint optimize future 351 * calls that hit this node. We have to check for our collapse cases 352 * and we have a few optimizations strewn in as well. 353 */ 354 355 static daddr_t 356 alst_meta_alloc( 357 almeta_t *scan, 358 daddr_t blk, 359 daddr_t count, 360 daddr_t radix, 361 int skip 362 ) { 363 int i; 364 u_daddr_t mask; 365 u_daddr_t pmask; 366 int next_skip = ((u_int)skip / ALIST_META_RADIX); 367 368 /* 369 * ALL-ALLOCATED special case 370 */ 371 if (scan->bm_bitmap == 0) { 372 scan->bm_bighint = 0; 373 return(ALIST_BLOCK_NONE); 374 } 375 376 radix /= ALIST_META_RADIX; 377 378 /* 379 * Radix now represents each bitmap entry for this meta node. If 380 * the number of blocks being allocated can be fully represented, 381 * we allocate directly out of this meta node. 382 * 383 * Meta node bitmaps use 2 bits per block. 384 * 385 * 00 ALL-ALLOCATED 386 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED 387 * 10 (RESERVED) 388 * 11 ALL-FREE 389 */ 390 if (count >= radix) { 391 int n = count / radix * 2; /* number of bits */ 392 int j; 393 394 mask = (u_daddr_t)-1 >> (ALIST_BMAP_RADIX - n); 395 for (j = 0; j < ALIST_META_RADIX; j += n / 2) { 396 if ((scan->bm_bitmap & mask) == mask) { 397 scan->bm_bitmap &= ~mask; 398 return(blk + j * radix); 399 } 400 mask <<= n; 401 } 402 if (scan->bm_bighint >= count) 403 scan->bm_bighint = count >> 1; 404 return(ALIST_BLOCK_NONE); 405 } 406 407 /* 408 * If not we have to recurse. 409 */ 410 mask = 0x00000003; 411 pmask = 0x00000001; 412 for (i = 1; i <= skip; i += next_skip) { 413 if (scan[i].bm_bighint == (daddr_t)-1) { 414 /* 415 * Terminator 416 */ 417 break; 418 } 419 420 /* 421 * If the element is marked completely free (11), initialize 422 * the recursion. 423 */ 424 if ((scan->bm_bitmap & mask) == mask) { 425 scan[i].bm_bitmap = (u_daddr_t)-1; 426 scan[i].bm_bighint = radix; 427 } 428 429 if ((scan->bm_bitmap & mask) == 0) { 430 /* 431 * Object marked completely allocated, recursion 432 * contains garbage. 433 */ 434 /* Skip it */ 435 } else if (count <= scan[i].bm_bighint) { 436 /* 437 * count fits in object 438 */ 439 daddr_t r; 440 if (next_skip == 1) { 441 r = alst_leaf_alloc(&scan[i], blk, count); 442 } else { 443 r = alst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 444 } 445 if (r != ALIST_BLOCK_NONE) { 446 if (scan[i].bm_bitmap == 0) { 447 scan->bm_bitmap &= ~mask; 448 } else { 449 scan->bm_bitmap &= ~mask; 450 scan->bm_bitmap |= pmask; 451 } 452 return(r); 453 } 454 } 455 blk += radix; 456 mask <<= 2; 457 pmask <<= 2; 458 } 459 460 /* 461 * We couldn't allocate count in this subtree, update bighint. 462 */ 463 if (scan->bm_bighint >= count) 464 scan->bm_bighint = count >> 1; 465 return(ALIST_BLOCK_NONE); 466 } 467 468 /* 469 * BLST_LEAF_FREE() - free allocated block from leaf bitmap 470 * 471 */ 472 static void 473 alst_leaf_free( 474 almeta_t *scan, 475 daddr_t blk, 476 int count 477 ) { 478 /* 479 * free some data in this bitmap 480 * 481 * e.g. 482 * 0000111111111110000 483 * \_________/\__/ 484 * v n 485 */ 486 int n = blk & (ALIST_BMAP_RADIX - 1); 487 u_daddr_t mask; 488 489 mask = ((u_daddr_t)-1 << n) & 490 ((u_daddr_t)-1 >> (ALIST_BMAP_RADIX - count - n)); 491 492 if (scan->bm_bitmap & mask) 493 panic("alst_radix_free: freeing free block"); 494 scan->bm_bitmap |= mask; 495 496 /* 497 * We could probably do a better job here. We are required to make 498 * bighint at least as large as the biggest contiguous block of 499 * data. If we just shoehorn it, a little extra overhead will 500 * be incured on the next allocation (but only that one typically). 501 */ 502 scan->bm_bighint = ALIST_BMAP_RADIX; 503 } 504 505 /* 506 * BLST_META_FREE() - free allocated blocks from radix tree meta info 507 * 508 * This support routine frees a range of blocks from the bitmap. 509 * The range must be entirely enclosed by this radix node. If a 510 * meta node, we break the range down recursively to free blocks 511 * in subnodes (which means that this code can free an arbitrary 512 * range whereas the allocation code cannot allocate an arbitrary 513 * range). 514 */ 515 516 static void 517 alst_meta_free( 518 almeta_t *scan, 519 daddr_t freeBlk, 520 daddr_t count, 521 daddr_t radix, 522 int skip, 523 daddr_t blk 524 ) { 525 int next_skip = ((u_int)skip / ALIST_META_RADIX); 526 u_daddr_t mask; 527 u_daddr_t pmask; 528 int i; 529 530 /* 531 * Break the free down into its components. Because it is so easy 532 * to implement, frees are not limited to power-of-2 sizes. 533 * 534 * Each block in a meta-node bitmap takes two bits. 535 */ 536 radix /= ALIST_META_RADIX; 537 538 i = (freeBlk - blk) / radix; 539 blk += i * radix; 540 mask = 0x00000003 << (i * 2); 541 pmask = 0x00000001 << (i * 2); 542 543 i = i * next_skip + 1; 544 545 while (i <= skip && blk < freeBlk + count) { 546 daddr_t v; 547 548 v = blk + radix - freeBlk; 549 if (v > count) 550 v = count; 551 552 if (scan->bm_bighint == (daddr_t)-1) 553 panic("alst_meta_free: freeing unexpected range"); 554 555 if (freeBlk == blk && count >= radix) { 556 /* 557 * All-free case, no need to update sub-tree 558 */ 559 scan->bm_bitmap |= mask; 560 scan->bm_bighint = radix * ALIST_META_RADIX;/*XXX*/ 561 } else { 562 /* 563 * If we were previously marked all-allocated, fix-up 564 * the next layer so we can recurse down into it. 565 */ 566 if ((scan->bm_bitmap & mask) == 0) { 567 scan[i].bm_bitmap = (u_daddr_t)0; 568 scan[i].bm_bighint = 0; 569 } 570 571 /* 572 * Recursion case 573 */ 574 if (next_skip == 1) 575 alst_leaf_free(&scan[i], freeBlk, v); 576 else 577 alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 578 if (scan[i].bm_bitmap == (u_daddr_t)-1) 579 scan->bm_bitmap |= mask; 580 else 581 scan->bm_bitmap |= pmask; 582 if (scan->bm_bighint < scan[i].bm_bighint) 583 scan->bm_bighint = scan[i].bm_bighint; 584 } 585 mask <<= 2; 586 pmask <<= 2; 587 count -= v; 588 freeBlk += v; 589 blk += radix; 590 i += next_skip; 591 } 592 } 593 594 /* 595 * BLST_RADIX_INIT() - initialize radix tree 596 * 597 * Initialize our meta structures and bitmaps and calculate the exact 598 * amount of space required to manage 'count' blocks - this space may 599 * be considerably less then the calculated radix due to the large 600 * RADIX values we use. 601 */ 602 603 static daddr_t 604 alst_radix_init(almeta_t *scan, daddr_t radix, int skip, daddr_t count) 605 { 606 int i; 607 int next_skip; 608 daddr_t memindex = 0; 609 u_daddr_t mask; 610 u_daddr_t pmask; 611 612 /* 613 * Leaf node 614 */ 615 if (radix == ALIST_BMAP_RADIX) { 616 if (scan) { 617 scan->bm_bighint = 0; 618 scan->bm_bitmap = 0; 619 } 620 return(memindex); 621 } 622 623 /* 624 * Meta node. If allocating the entire object we can special 625 * case it. However, we need to figure out how much memory 626 * is required to manage 'count' blocks, so we continue on anyway. 627 */ 628 629 if (scan) { 630 scan->bm_bighint = 0; 631 scan->bm_bitmap = 0; 632 } 633 634 radix /= ALIST_META_RADIX; 635 next_skip = ((u_int)skip / ALIST_META_RADIX); 636 mask = 0x00000003; 637 pmask = 0x00000001; 638 639 for (i = 1; i <= skip; i += next_skip) { 640 if (count >= radix) { 641 /* 642 * Allocate the entire object 643 */ 644 memindex = i + alst_radix_init( 645 ((scan) ? &scan[i] : NULL), 646 radix, 647 next_skip - 1, 648 radix 649 ); 650 count -= radix; 651 /* already marked as wholely allocated */ 652 } else if (count > 0) { 653 /* 654 * Allocate a partial object 655 */ 656 memindex = i + alst_radix_init( 657 ((scan) ? &scan[i] : NULL), 658 radix, 659 next_skip - 1, 660 count 661 ); 662 count = 0; 663 664 /* 665 * Mark as partially allocated 666 */ 667 if (scan) 668 scan->bm_bitmap |= pmask; 669 } else { 670 /* 671 * Add terminator and break out 672 */ 673 if (scan) 674 scan[i].bm_bighint = (daddr_t)-1; 675 /* already marked as wholely allocated */ 676 break; 677 } 678 mask <<= 2; 679 pmask <<= 2; 680 } 681 if (memindex < i) 682 memindex = i; 683 return(memindex); 684 } 685 686 #ifdef ALIST_DEBUG 687 688 static void 689 alst_radix_print(almeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) 690 { 691 int i; 692 int next_skip; 693 int lastState = 0; 694 u_daddr_t mask; 695 696 if (radix == ALIST_BMAP_RADIX) { 697 kprintf( 698 "%*.*s(%04x,%d): bitmap %08x big=%d\n", 699 tab, tab, "", 700 blk, radix, 701 scan->bm_bitmap, 702 scan->bm_bighint 703 ); 704 return; 705 } 706 707 if (scan->bm_bitmap == 0) { 708 kprintf( 709 "%*.*s(%04x,%d) ALL ALLOCATED\n", 710 tab, tab, "", 711 blk, 712 radix 713 ); 714 return; 715 } 716 if (scan->bm_bitmap == (u_daddr_t)-1) { 717 kprintf( 718 "%*.*s(%04x,%d) ALL FREE\n", 719 tab, tab, "", 720 blk, 721 radix 722 ); 723 return; 724 } 725 726 kprintf( 727 "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n", 728 tab, tab, "", 729 blk, radix, 730 radix, 731 scan->bm_bitmap, 732 scan->bm_bighint 733 ); 734 735 radix /= ALIST_META_RADIX; 736 next_skip = ((u_int)skip / ALIST_META_RADIX); 737 tab += 4; 738 mask = 0x00000003; 739 740 for (i = 1; i <= skip; i += next_skip) { 741 if (scan[i].bm_bighint == (daddr_t)-1) { 742 kprintf( 743 "%*.*s(%04x,%d): Terminator\n", 744 tab, tab, "", 745 blk, radix 746 ); 747 lastState = 0; 748 break; 749 } 750 if ((scan->bm_bitmap & mask) == mask) { 751 kprintf( 752 "%*.*s(%04x,%d): ALL FREE\n", 753 tab, tab, "", 754 blk, radix 755 ); 756 } else if ((scan->bm_bitmap & mask) == 0) { 757 kprintf( 758 "%*.*s(%04x,%d): ALL ALLOCATED\n", 759 tab, tab, "", 760 blk, radix 761 ); 762 } else { 763 alst_radix_print( 764 &scan[i], 765 blk, 766 radix, 767 next_skip - 1, 768 tab 769 ); 770 } 771 blk += radix; 772 mask <<= 2; 773 } 774 tab -= 4; 775 776 kprintf( 777 "%*.*s}\n", 778 tab, tab, "" 779 ); 780 } 781 782 #endif 783 784 #ifdef ALIST_DEBUG 785 786 int 787 main(int ac, char **av) 788 { 789 int size = 1024; 790 int i; 791 alist_t bl; 792 793 for (i = 1; i < ac; ++i) { 794 const char *ptr = av[i]; 795 if (*ptr != '-') { 796 size = strtol(ptr, NULL, 0); 797 continue; 798 } 799 ptr += 2; 800 fprintf(stderr, "Bad option: %s\n", ptr - 2); 801 exit(1); 802 } 803 bl = alist_create(size, NULL); 804 alist_free(bl, 0, size); 805 806 for (;;) { 807 char buf[1024]; 808 daddr_t da = 0; 809 daddr_t count = 0; 810 811 812 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix); 813 fflush(stdout); 814 if (fgets(buf, sizeof(buf), stdin) == NULL) 815 break; 816 switch(buf[0]) { 817 case 'p': 818 alist_print(bl); 819 break; 820 case 'a': 821 if (sscanf(buf + 1, "%d", &count) == 1) { 822 daddr_t blk = alist_alloc(bl, count); 823 kprintf(" R=%04x\n", blk); 824 } else { 825 kprintf("?\n"); 826 } 827 break; 828 case 'f': 829 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 830 alist_free(bl, da, count); 831 } else { 832 kprintf("?\n"); 833 } 834 break; 835 case '?': 836 case 'h': 837 puts( 838 "p -print\n" 839 "a %d -allocate\n" 840 "f %x %d -free\n" 841 "h/? -help" 842 ); 843 break; 844 default: 845 kprintf("?\n"); 846 break; 847 } 848 } 849 return(0); 850 } 851 852 void 853 panic(const char *ctl, ...) 854 { 855 __va_list va; 856 857 __va_start(va, ctl); 858 vfprintf(stderr, ctl, va); 859 fprintf(stderr, "\n"); 860 __va_end(va); 861 exit(1); 862 } 863 864 #endif 865 866