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