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 /* 39 * This module has been adapted from the BLIST module, which was written 40 * by Matthew Dillon many years ago. 41 * 42 * This module implements a general power-of-2 bitmap allocator/deallocator. 43 * All allocations must be in powers of 2 and will return similarly aligned 44 * results. The module does not try to interpret the meaning of a 'block' 45 * other then to return ALIST_BLOCK_NONE on an allocation failure. 46 * 47 * A maximum of 2 billion blocks is supported so, for example, if one block 48 * represented 64 bytes a maximally sized ALIST would represent 49 * 128 gigabytes. 50 * 51 * A radix tree is used to maintain the bitmap and layed out in a manner 52 * similar to the blist code. Meta nodes use a radix of 16 and 2 bits per 53 * block while leaf nodes use a radix of 32 and 1 bit per block (stored in 54 * a 32 bit bitmap field). Both meta and leaf nodes have a hint field. 55 * This field gives us a hint as to the largest free contiguous range of 56 * blocks under the node. It may contain a value that is too high, but 57 * will never contain a value that is too low. When the radix tree is 58 * searched, allocation failures in subtrees update the hint. 59 * 60 * The radix tree is layed out recursively using a linear array. Each meta 61 * node is immediately followed (layed out sequentially in memory) by 62 * ALIST_META_RADIX lower level nodes. This is a recursive structure but one 63 * that can be easily scanned through a very simple 'skip' calculation. In 64 * order to support large radixes, portions of the tree may reside outside our 65 * memory allocation. We handle this with an early-terminate optimization 66 * in the meta-node. The memory allocation is only large enough to cover 67 * the number of blocks requested at creation time even if it must be 68 * encompassed in larger root-node radix. 69 * 70 * This code can be compiled stand-alone for debugging. 71 */ 72 73 #ifdef _KERNEL 74 75 #include <sys/param.h> 76 #include <sys/systm.h> 77 #include <sys/lock.h> 78 #include <sys/kernel.h> 79 #include <sys/alist.h> 80 #include <sys/malloc.h> 81 #include <vm/vm.h> 82 #include <vm/vm_object.h> 83 #include <vm/vm_kern.h> 84 #include <vm/vm_extern.h> 85 #include <vm/vm_page.h> 86 87 #else 88 89 #ifndef ALIST_NO_DEBUG 90 #define ALIST_DEBUG 91 #endif 92 93 #include <sys/types.h> 94 #include <stdio.h> 95 #include <assert.h> 96 #include <string.h> 97 #include <stdlib.h> 98 #include <stdarg.h> 99 100 #define kmalloc(a,b,c) malloc(a) 101 #define kfree(a,b) free(a) 102 #define kprintf printf 103 #define KKASSERT(exp) assert(exp) 104 struct malloc_type; 105 106 #include <sys/alist.h> 107 108 void panic(const char *ctl, ...); 109 110 #endif 111 112 /* 113 * static support functions 114 */ 115 116 static alist_blk_t alst_leaf_alloc(almeta_t *scan, alist_blk_t blk, 117 alist_blk_t start, alist_blk_t count); 118 static alist_blk_t alst_meta_alloc(almeta_t *scan, alist_blk_t blk, 119 alist_blk_t start, alist_blk_t count, 120 alist_blk_t radix, alist_blk_t skip); 121 static void alst_leaf_free(almeta_t *scan, alist_blk_t relblk, 122 alist_blk_t count); 123 static void alst_meta_free(almeta_t *scan, alist_blk_t freeBlk, 124 alist_blk_t count, alist_blk_t radix, 125 alist_blk_t skip, alist_blk_t blk); 126 static alist_blk_t alst_radix_init(almeta_t *scan, alist_blk_t blk, 127 alist_blk_t radix, alist_blk_t skip, 128 alist_blk_t count); 129 #ifndef _KERNEL 130 static void alst_radix_print(almeta_t *scan, alist_blk_t blk, 131 alist_blk_t radix, alist_blk_t skip, 132 int tab); 133 #endif 134 135 /* 136 * Create a alist capable of handling up to the specified number of blocks. 137 * Blocks must be greater then 0 but does not have to be a power of 2. 138 * 139 * The smallest alist consists of a single leaf node capable of 140 * managing ALIST_BMAP_RADIX blocks. 141 */ 142 alist_t 143 alist_create(alist_blk_t blocks, struct malloc_type *mtype) 144 { 145 alist_t bl; 146 alist_blk_t radix; 147 alist_blk_t skip = 0; 148 149 /* 150 * Calculate radix and skip field used for scanning. 151 */ 152 radix = ALIST_BMAP_RADIX; 153 154 while (radix < blocks) { 155 radix *= ALIST_META_RADIX; 156 skip = (skip + 1) * ALIST_META_RADIX; 157 } 158 159 bl = kmalloc(sizeof(struct alist), mtype, M_WAITOK | M_ZERO); 160 161 bl->bl_blocks = blocks; 162 bl->bl_radix = radix; 163 bl->bl_skip = skip; 164 bl->bl_rootblks = 1 + alst_radix_init(NULL, 0, bl->bl_radix, 165 bl->bl_skip, blocks); 166 bl->bl_root = kmalloc(sizeof(almeta_t) * bl->bl_rootblks, 167 mtype, M_WAITOK); 168 169 #if defined(ALIST_DEBUG) 170 kprintf( 171 "ALIST representing %d blocks (%d MB of swap)" 172 ", requiring %dK (%d bytes) of ram\n", 173 bl->bl_blocks, 174 bl->bl_blocks * 4 / 1024, 175 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024, 176 (bl->bl_rootblks * sizeof(almeta_t)) 177 ); 178 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks); 179 #endif 180 alst_radix_init(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, blocks); 181 182 return(bl); 183 } 184 185 void 186 alist_init(alist_t bl, alist_blk_t blocks, 187 almeta_t *records, alist_blk_t nrecords) 188 { 189 alist_blk_t radix; 190 alist_blk_t skip = 0; 191 192 /* 193 * Calculate radix and skip field used for scanning. 194 */ 195 radix = ALIST_BMAP_RADIX; 196 197 while (radix < blocks) { 198 radix *= ALIST_META_RADIX; 199 skip = (skip + 1) * ALIST_META_RADIX; 200 } 201 bzero(bl, sizeof(*bl)); 202 203 bl->bl_blocks = blocks; 204 bl->bl_radix = radix; 205 bl->bl_skip = skip; 206 bl->bl_rootblks = 1 + alst_radix_init(NULL, 0, bl->bl_radix, 207 bl->bl_skip, blocks); 208 KKASSERT(bl->bl_rootblks <= nrecords); 209 bl->bl_root = records; 210 211 #if defined(ALIST_DEBUG) 212 kprintf( 213 "ALIST representing %d blocks (%d MB of swap)" 214 ", requiring %dK (%d bytes) of ram\n", 215 bl->bl_blocks, 216 bl->bl_blocks * 4 / 1024, 217 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024, 218 (bl->bl_rootblks * sizeof(almeta_t)) 219 ); 220 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks); 221 #endif 222 alst_radix_init(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, blocks); 223 } 224 225 void 226 alist_destroy(alist_t bl, struct malloc_type *mtype) 227 { 228 kfree(bl->bl_root, mtype); 229 kfree(bl, mtype); 230 } 231 232 /* 233 * Reserve space in the block bitmap. Return the base of a contiguous 234 * region or ALIST_BLOCK_NONE if space could not be allocated. 235 * 236 * This nominally allocates a power-of-2 number of blocks. However, 237 * non-powers of 2 are accepted and implemented by first allocating 238 * the nearest power of 2 and then freeing the remainder. 239 */ 240 alist_blk_t 241 alist_alloc(alist_t bl, alist_blk_t start, alist_blk_t count) 242 { 243 alist_blk_t blk = ALIST_BLOCK_NONE; 244 245 /* 246 * Check non power-of-2 247 */ 248 KKASSERT(count); 249 if ((count | (count - 1)) != (count << 1) - 1) { 250 alist_blk_t ncount = (count < 256) ? 1 : 256; 251 while (ncount < count) 252 ncount <<= 1; 253 blk = alist_alloc(bl, start, ncount); 254 if (blk != ALIST_BLOCK_NONE) 255 alist_free(bl, blk + count, ncount - count); 256 return (blk); 257 } 258 259 /* 260 * Power of 2 261 */ 262 if (bl && count < bl->bl_radix) { 263 if (bl->bl_radix == ALIST_BMAP_RADIX) { 264 blk = alst_leaf_alloc(bl->bl_root, 0, start, count); 265 } else { 266 blk = alst_meta_alloc(bl->bl_root, 0, start, count, 267 bl->bl_radix, bl->bl_skip); 268 } 269 if (blk != ALIST_BLOCK_NONE) 270 bl->bl_free -= count; 271 } 272 return(blk); 273 } 274 275 /* 276 * Free up space in the block bitmap. The starting block and count do not 277 * need to be power-of-2 aligned. The related blocks must be in an allocated 278 * state. 279 */ 280 void 281 alist_free(alist_t bl, alist_blk_t blkno, alist_blk_t count) 282 { 283 if (bl) { 284 KKASSERT(blkno + count <= bl->bl_blocks); 285 if (bl->bl_radix == ALIST_BMAP_RADIX) { 286 alst_leaf_free(bl->bl_root, blkno, count); 287 } else { 288 alst_meta_free(bl->bl_root, blkno, count, 289 bl->bl_radix, bl->bl_skip, 0); 290 } 291 bl->bl_free += count; 292 } 293 } 294 295 /* 296 * Returns the current total number of free blocks and the 297 * approximate trailing largest contiguous free block available. 298 */ 299 alist_blk_t 300 alist_free_info(alist_t bl, alist_blk_t *startp, alist_blk_t *countp) 301 { 302 alist_blk_t radix = bl->bl_radix; 303 alist_blk_t skip = bl->bl_skip; 304 alist_blk_t next_skip; 305 alist_blk_t i; 306 alist_bmap_t mask; 307 almeta_t *scan = bl->bl_root; 308 309 *startp = 0; 310 *countp = 0; 311 312 while (radix != ALIST_BMAP_RADIX) { 313 radix /= ALIST_META_RADIX; 314 next_skip = skip / ALIST_META_RADIX; 315 316 /* 317 * Find the biggest fully allocated chunk. 318 */ 319 for (i = ALIST_META_RADIX - 1; i != ALIST_BLOCK_NONE; --i) { 320 mask = (scan->bm_bitmap >> (i * 2)) & 3; 321 if (mask == 0) { 322 /* 323 * All allocated, continue the loop 324 */ 325 continue; 326 } 327 if (mask == 1) { 328 /* 329 * Partially allocated, push into this guy 330 */ 331 break; 332 } 333 if (mask == 2) { 334 /* 335 * Unknown state 336 */ 337 return(bl->bl_free); 338 } 339 /* 340 * All free, we can return the chunk. 341 */ 342 *startp += i * radix; 343 *countp = radix; 344 return(bl->bl_free); 345 } 346 347 /* 348 * If we failed to find anything stop here, otherwise push 349 * in. 350 */ 351 if (i == ALIST_BLOCK_NONE) 352 return(bl->bl_free); 353 *startp += i * radix; 354 scan += 1 + next_skip * i; 355 skip = next_skip - 1; 356 } 357 358 /* 359 * If we got all the way down to a leaf node locate the last block, 360 * power-of-2 aligned and power-of-2 sized. Well, the easiest way 361 * to deal with this is to just return 1 block. 362 */ 363 if (radix == ALIST_BMAP_RADIX) { 364 mask = scan->bm_bitmap; 365 for (i = ALIST_BMAP_RADIX - 1; i != ALIST_BLOCK_NONE; --i) { 366 if ((mask & ((alist_bmap_t)1U << i))) 367 break; 368 } 369 370 /* 371 * did not find free entry 372 */ 373 if (i == ALIST_BLOCK_NONE) 374 return(bl->bl_free); 375 376 /* 377 * Return one block. 378 */ 379 *startp += i; 380 *countp = 1; 381 return(bl->bl_free); 382 } 383 return(bl->bl_free); 384 } 385 386 #ifdef ALIST_DEBUG 387 388 /* 389 * alist_print() - dump radix tree 390 */ 391 392 void 393 alist_print(alist_t bl) 394 { 395 kprintf("ALIST {\n"); 396 alst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 397 kprintf("}\n"); 398 } 399 400 #endif 401 402 /************************************************************************ 403 * ALLOCATION SUPPORT FUNCTIONS * 404 ************************************************************************ 405 * 406 * These support functions do all the actual work. They may seem 407 * rather longish, but that's because I've commented them up. The 408 * actual code is straight forward. 409 * 410 */ 411 412 /* 413 * alist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 414 * 415 * This is the core of the allocator and is optimized for the 1 block 416 * and the ALIST_BMAP_RADIX block allocation cases. Other cases are 417 * somewhat slower. The 1 block allocation case is log2 and extremely 418 * quick. 419 * 420 * mask bit is 0 allocated, not available 421 * mask bit is 1 free, available for allocation 422 */ 423 424 static alist_blk_t 425 alst_leaf_alloc(almeta_t *scan, alist_blk_t blk, alist_blk_t start, 426 alist_blk_t count) 427 { 428 alist_bmap_t orig = scan->bm_bitmap; 429 430 /* 431 * Allocate only beyond the start point. Mask to 0 the low bits 432 * below start. If start == blk no bits get cleared so don't 433 * bother. 434 */ 435 if (start >= blk + ALIST_BMAP_RADIX) 436 return(ALIST_BLOCK_NONE); 437 438 if (start > blk && start < blk + ALIST_BMAP_RADIX) 439 orig &= ~(((alist_bmap_t)1U << (start - blk)) - 1); 440 441 start &= ALIST_BMAP_RADIX - 1; 442 443 /* 444 * Optimize bitmap all-allocated case. Also, count = 1 445 * case assumes at least 1 bit is free in the bitmap, so 446 * we have to take care of this case here. 447 */ 448 if (orig == 0) { 449 if (start <= blk) 450 scan->bm_bighint = 0; 451 return(ALIST_BLOCK_NONE); 452 } 453 454 /* 455 * Optimized code to allocate one bit out of the bitmap 456 */ 457 if (count == 1) { 458 alist_bmap_t mask; 459 alist_blk_t j = ALIST_BMAP_RADIX/2; 460 alist_blk_t r = 0; 461 462 mask = (alist_bmap_t)-1 >> (ALIST_BMAP_RADIX/2); 463 464 while (j) { 465 if ((orig & mask) == 0) { 466 r += j; 467 orig >>= j; 468 } 469 j >>= 1; 470 mask >>= j; 471 } 472 scan->bm_bitmap &= ~(1 << r); 473 return(blk + r); 474 } 475 476 /* 477 * non-optimized code to allocate N bits out of the bitmap. 478 * The more bits, the faster the code runs. It will run 479 * the slowest allocating 2 bits, but since there aren't any 480 * memory ops in the core loop (or shouldn't be, anyway), 481 * you probably won't notice the difference. 482 * 483 * Similar to the blist case, the alist code also requires 484 * allocations to be power-of-2 sized and aligned to the 485 * size of the allocation, which simplifies the algorithm. 486 */ 487 { 488 alist_blk_t j; 489 alist_blk_t n = ALIST_BMAP_RADIX - count; 490 alist_bmap_t mask; 491 492 mask = (alist_bmap_t)-1 >> n; 493 494 for (j = 0; j <= n; j += count) { 495 if ((orig & mask) == mask) { 496 scan->bm_bitmap &= ~mask; 497 return(blk + j); 498 } 499 mask = mask << count; 500 } 501 } 502 503 /* 504 * We couldn't allocate count in this subtree, update bighint 505 * if we were able to check the entire node. 506 */ 507 if (start <= blk) 508 scan->bm_bighint = count - 1; 509 return(ALIST_BLOCK_NONE); 510 } 511 512 /* 513 * Attempt to allocate at a meta node. If we can't, we update 514 * bighint and return a failure. Updating bighint optimize future 515 * calls that hit this node. We have to check for our collapse cases 516 * and we have a few optimizations strewn in as well. 517 */ 518 static alist_blk_t 519 alst_meta_alloc(almeta_t *scan, alist_blk_t blk, alist_blk_t start, 520 alist_blk_t count, alist_blk_t radix, alist_blk_t skip) 521 { 522 alist_blk_t i; 523 alist_bmap_t mask; 524 alist_bmap_t pmask; 525 alist_blk_t next_skip = ((u_int)skip / ALIST_META_RADIX); 526 alist_blk_t orig_blk; 527 528 /* 529 * ALL-ALLOCATED special case 530 */ 531 if (scan->bm_bitmap == 0) { 532 scan->bm_bighint = 0; 533 return(ALIST_BLOCK_NONE); 534 } 535 536 radix /= ALIST_META_RADIX; 537 538 /* 539 * Radix now represents each bitmap entry for this meta node. If 540 * the number of blocks being allocated can be fully represented, 541 * we allocate directly out of this meta node. 542 * 543 * Meta node bitmaps use 2 bits per block. 544 * 545 * 00 ALL-ALLOCATED 546 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED 547 * 10 (RESERVED) 548 * 11 ALL-FREE 549 */ 550 if (count >= radix) { 551 alist_blk_t n = count / radix * 2; /* number of bits */ 552 alist_blk_t j; 553 554 mask = (alist_bmap_t)-1 >> (ALIST_BMAP_RADIX - n); 555 for (j = 0; j < ALIST_META_RADIX; j += n / 2) { 556 if ((scan->bm_bitmap & mask) == mask && 557 blk + j * radix >= start) { 558 scan->bm_bitmap &= ~mask; 559 return(blk + j * radix); 560 } 561 mask <<= n; 562 } 563 if (scan->bm_bighint >= count && start <= blk) 564 scan->bm_bighint = count >> 1; 565 return(ALIST_BLOCK_NONE); 566 } 567 568 /* 569 * If not we have to recurse. 570 */ 571 mask = 0x00000003; 572 pmask = 0x00000001; 573 orig_blk = blk; 574 for (i = 1; i <= skip; i += next_skip) { 575 if (scan[i].bm_bighint == (alist_blk_t)-1) { 576 /* 577 * Terminator 578 */ 579 break; 580 } 581 582 /* 583 * If the element is marked completely free (11), initialize 584 * the recursion. 585 */ 586 if ((scan->bm_bitmap & mask) == mask) { 587 scan[i].bm_bitmap = (alist_bmap_t)-1; 588 scan[i].bm_bighint = radix; 589 } 590 591 if ((scan->bm_bitmap & mask) == 0) { 592 /* 593 * Object marked completely allocated, recursion 594 * contains garbage. 595 */ 596 /* Skip it */ 597 } else if (blk + radix <= start) { 598 /* 599 * Object does not contain or is not beyond our 600 * start point. 601 */ 602 /* Skip it */ 603 } else if (count <= scan[i].bm_bighint) { 604 /* 605 * count fits in object. If successful and the 606 * deeper level becomes all allocated, mark our 607 * level as all-allocated. 608 */ 609 alist_blk_t r; 610 if (next_skip == 1) { 611 r = alst_leaf_alloc(&scan[i], blk, start, 612 count); 613 } else { 614 r = alst_meta_alloc(&scan[i], blk, start, 615 count, 616 radix, next_skip - 1); 617 } 618 if (r != ALIST_BLOCK_NONE) { 619 if (scan[i].bm_bitmap == 0) { 620 scan->bm_bitmap &= ~mask; 621 } else { 622 scan->bm_bitmap &= ~mask; 623 scan->bm_bitmap |= pmask; 624 } 625 return(r); 626 } 627 } 628 blk += radix; 629 mask <<= 2; 630 pmask <<= 2; 631 } 632 633 /* 634 * We couldn't allocate count in this subtree, update bighint 635 * if we were able to check the entire node. 636 */ 637 if (scan->bm_bighint >= count && start <= orig_blk) 638 scan->bm_bighint = count >> 1; 639 return(ALIST_BLOCK_NONE); 640 } 641 642 /* 643 * Free allocated block from leaf bitmap 644 */ 645 static void 646 alst_leaf_free(almeta_t *scan, alist_blk_t blk, alist_blk_t count) 647 { 648 /* 649 * free some data in this bitmap 650 * 651 * e.g. 652 * 0000111111111110000 653 * \_________/\__/ 654 * v n 655 */ 656 alist_blk_t n = blk & (ALIST_BMAP_RADIX - 1); 657 alist_bmap_t mask; 658 659 mask = ((alist_bmap_t)-1 << n) & 660 ((alist_bmap_t)-1 >> (ALIST_BMAP_RADIX - count - n)); 661 662 if (scan->bm_bitmap & mask) 663 panic("alst_radix_free: freeing free block"); 664 scan->bm_bitmap |= mask; 665 666 /* 667 * We could probably do a better job here. We are required to make 668 * bighint at least as large as the biggest contiguous block of 669 * data. If we just shoehorn it, a little extra overhead will 670 * be incured on the next allocation (but only that one typically). 671 */ 672 scan->bm_bighint = ALIST_BMAP_RADIX; 673 } 674 675 /* 676 * Free allocated blocks from radix tree meta info. This support routine 677 * frees a range of blocks from the bitmap. The range must be entirely 678 * enclosed by this radix node. If a meta node, we break the range down 679 * recursively to free blocks in subnodes (which means that this code 680 * can free an arbitrary range whereas the allocation code cannot allocate 681 * an arbitrary range). 682 */ 683 static void 684 alst_meta_free(almeta_t *scan, alist_blk_t freeBlk, alist_blk_t count, 685 alist_blk_t radix, alist_blk_t skip, alist_blk_t blk) 686 { 687 alist_blk_t next_skip = ((u_int)skip / ALIST_META_RADIX); 688 alist_bmap_t mask; 689 alist_bmap_t pmask; 690 alist_blk_t i; 691 692 /* 693 * Break the free down into its components. Because it is so easy 694 * to implement, frees are not limited to power-of-2 sizes. 695 * 696 * Each block in a meta-node bitmap takes two bits. 697 */ 698 radix /= ALIST_META_RADIX; 699 700 i = (freeBlk - blk) / radix; 701 blk += i * radix; 702 mask = 0x00000003 << (i * 2); 703 pmask = 0x00000001 << (i * 2); 704 705 i = i * next_skip + 1; 706 707 while (i <= skip && blk < freeBlk + count) { 708 alist_blk_t v; 709 710 v = blk + radix - freeBlk; 711 if (v > count) 712 v = count; 713 714 if (scan->bm_bighint == (alist_blk_t)-1) 715 panic("alst_meta_free: freeing unexpected range"); 716 717 /* 718 * WARNING on bighint updates. When we free an element in 719 * a chunk if the chunk becomes wholely free it is possible 720 * that the whole node is now free, so bighint must be set 721 * to cover the whole node. Otherwise address-specific 722 * allocations may fail. 723 * 724 * We don't bother figuring out how much of the node is 725 * actually free in this case. 726 */ 727 if (freeBlk == blk && count >= radix) { 728 /* 729 * The area being freed covers the entire block, 730 * assert that we are marked all-allocated and 731 * then mark it all-free. 732 */ 733 KKASSERT((scan->bm_bitmap & mask) == 0); 734 scan->bm_bitmap |= mask; 735 scan->bm_bighint = radix * ALIST_META_RADIX; 736 } else { 737 /* 738 * If we were previously marked all-allocated, fix-up 739 * the next layer so we can recurse down into it. 740 */ 741 if ((scan->bm_bitmap & mask) == 0) { 742 scan[i].bm_bitmap = (alist_bmap_t)0; 743 scan[i].bm_bighint = 0; 744 } 745 746 /* 747 * Recursion case, then either mark all-free or 748 * partially free. 749 */ 750 if (next_skip == 1) { 751 alst_leaf_free(&scan[i], freeBlk, v); 752 } else { 753 alst_meta_free(&scan[i], freeBlk, v, 754 radix, next_skip - 1, blk); 755 } 756 if (scan[i].bm_bitmap == (alist_bmap_t)-1) { 757 scan->bm_bitmap |= mask; 758 scan->bm_bighint = radix * ALIST_META_RADIX; 759 } else { 760 scan->bm_bitmap &= ~mask; 761 scan->bm_bitmap |= pmask; 762 if (scan->bm_bighint < scan[i].bm_bighint) 763 scan->bm_bighint = scan[i].bm_bighint; 764 } 765 } 766 mask <<= 2; 767 pmask <<= 2; 768 count -= v; 769 freeBlk += v; 770 blk += radix; 771 i += next_skip; 772 } 773 } 774 775 /* 776 * Initialize our meta structures and bitmaps and calculate the exact 777 * amount of space required to manage 'count' blocks - this space may 778 * be considerably less then the calculated radix due to the large 779 * RADIX values we use. 780 */ 781 static alist_blk_t 782 alst_radix_init(almeta_t *scan, alist_blk_t blk, alist_blk_t radix, 783 alist_blk_t skip, alist_blk_t count) 784 { 785 alist_blk_t i; 786 alist_blk_t next_skip; 787 alist_bmap_t mask; 788 alist_bmap_t pmask; 789 alist_blk_t memindex; 790 791 /* 792 * Leaf node 793 */ 794 if (radix == ALIST_BMAP_RADIX) { 795 if (scan) { 796 scan->bm_bighint = 0; 797 scan->bm_bitmap = 0; 798 } 799 return(0); 800 } 801 802 /* 803 * Meta node. If allocating the entire object we can special 804 * case it. However, we need to figure out how much memory 805 * is required to manage 'count' blocks, so we continue on anyway. 806 */ 807 if (scan) { 808 scan->bm_bighint = 0; 809 scan->bm_bitmap = 0; 810 } 811 memindex = 0; 812 813 radix /= ALIST_META_RADIX; 814 next_skip = skip / ALIST_META_RADIX; 815 mask = 0x00000003; 816 pmask = 0x00000001; 817 818 for (i = 1; i <= skip; i += next_skip) { 819 if (count >= blk + radix) { 820 /* 821 * Allocate the entire object 822 */ 823 memindex += alst_radix_init(((scan) ? &scan[i] : NULL), 824 blk, radix, 825 next_skip - 1, count); 826 /* already marked as wholely allocated */ 827 } else if (count > blk) { 828 /* 829 * Allocate a partial object, well it's really 830 * all-allocated, we just aren't allowed to 831 * free the whole thing. 832 */ 833 memindex += alst_radix_init(((scan) ? &scan[i] : NULL), 834 blk, radix, 835 next_skip - 1, count); 836 /* already marked as wholely allocated */ 837 } else { 838 /* 839 * Add terminator but continue the loop. Populate 840 * all terminators. 841 */ 842 if (scan) { 843 scan[i].bm_bighint = (alist_blk_t)-1; 844 scan[i].bm_bitmap = 0; 845 } 846 /* already marked as wholely allocated */ 847 } 848 mask <<= 2; 849 pmask <<= 2; 850 blk += radix; 851 } 852 memindex += ALIST_META_RADIX; 853 return(memindex); 854 } 855 856 #ifdef ALIST_DEBUG 857 858 static void 859 alst_radix_print(almeta_t *scan, alist_blk_t blk, alist_blk_t radix, 860 alist_blk_t skip, int tab) 861 { 862 alist_blk_t i; 863 alist_blk_t next_skip; 864 alist_bmap_t mask; 865 866 if (radix == ALIST_BMAP_RADIX) { 867 kprintf( 868 "%*.*s(%04x,%d): bitmap %08x big=%d\n", 869 tab, tab, "", 870 blk, radix, 871 scan->bm_bitmap, 872 scan->bm_bighint 873 ); 874 return; 875 } 876 877 if (scan->bm_bitmap == 0) { 878 kprintf( 879 "%*.*s(%04x,%d) ALL ALLOCATED\n", 880 tab, tab, "", 881 blk, 882 radix 883 ); 884 return; 885 } 886 if (scan->bm_bitmap == (alist_bmap_t)-1) { 887 kprintf( 888 "%*.*s(%04x,%d) ALL FREE\n", 889 tab, tab, "", 890 blk, 891 radix 892 ); 893 return; 894 } 895 896 kprintf( 897 "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n", 898 tab, tab, "", 899 blk, radix, 900 radix, 901 scan->bm_bitmap, 902 scan->bm_bighint 903 ); 904 905 radix /= ALIST_META_RADIX; 906 next_skip = skip / ALIST_META_RADIX; 907 tab += 4; 908 mask = 0x00000003; 909 910 for (i = 1; i <= skip; i += next_skip) { 911 if (scan[i].bm_bighint == (alist_blk_t)-1) { 912 kprintf( 913 "%*.*s(%04x,%d): Terminator\n", 914 tab, tab, "", 915 blk, radix 916 ); 917 break; 918 } 919 if ((scan->bm_bitmap & mask) == mask) { 920 kprintf( 921 "%*.*s(%04x,%d): ALL FREE\n", 922 tab, tab, "", 923 blk, radix 924 ); 925 } else if ((scan->bm_bitmap & mask) == 0) { 926 kprintf( 927 "%*.*s(%04x,%d): ALL ALLOCATED\n", 928 tab, tab, "", 929 blk, radix 930 ); 931 } else { 932 alst_radix_print( 933 &scan[i], 934 blk, 935 radix, 936 next_skip - 1, 937 tab 938 ); 939 } 940 blk += radix; 941 mask <<= 2; 942 } 943 tab -= 4; 944 945 kprintf("%*.*s}\n", tab, tab, ""); 946 } 947 948 #endif 949 950 #ifdef ALIST_DEBUG 951 952 int 953 main(int ac, char **av) 954 { 955 alist_blk_t size = 1024; 956 alist_blk_t da = 0; 957 alist_blk_t count = 0; 958 alist_t bl; 959 int i; 960 961 for (i = 1; i < ac; ++i) { 962 const char *ptr = av[i]; 963 if (*ptr != '-') { 964 size = strtol(ptr, NULL, 0); 965 continue; 966 } 967 ptr += 2; 968 fprintf(stderr, "Bad option: %s\n", ptr - 2); 969 exit(1); 970 } 971 bl = alist_create(size, NULL); 972 alist_free(bl, 0, size); 973 974 for (;;) { 975 char buf[1024]; 976 alist_blk_t bfree; 977 978 979 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix); 980 fflush(stdout); 981 if (fgets(buf, sizeof(buf), stdin) == NULL) 982 break; 983 switch(buf[0]) { 984 case 'p': 985 alist_print(bl); 986 break; 987 case 'a': 988 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 989 da = alist_alloc(bl, da, count); 990 kprintf(" R=%04x\n", da); 991 } else if (sscanf(buf + 1, "%d", &count) == 1) { 992 da = alist_alloc(bl, 0, count); 993 kprintf(" R=%04x\n", da); 994 } else if (count) { 995 kprintf("alloc 0x%04x/%d\n", da, count); 996 alist_blk_t blk = alist_alloc(bl, da, count); 997 kprintf(" R=%04x\n", blk); 998 } else { 999 kprintf("?\n"); 1000 } 1001 break; 1002 case 'f': 1003 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) { 1004 alist_free(bl, da, count); 1005 } else if (count) { 1006 kprintf("free 0x%04x/%d\n", da, count); 1007 alist_free(bl, da, count); 1008 } else { 1009 kprintf("?\n"); 1010 } 1011 break; 1012 case '?': 1013 case 'h': 1014 puts("p -print\n" 1015 "a %d -allocate\n" 1016 "f %x %d -free\n" 1017 "h/? -help"); 1018 break; 1019 case 'i': 1020 bfree = alist_free_info(bl, &da, &count); 1021 kprintf("info: %d free trailing: 0x%04x/%d\n", 1022 bfree, da, count); 1023 break; 1024 default: 1025 kprintf("?\n"); 1026 break; 1027 } 1028 } 1029 return(0); 1030 } 1031 1032 void 1033 panic(const char *ctl, ...) 1034 { 1035 __va_list va; 1036 1037 __va_start(va, ctl); 1038 vfprintf(stderr, ctl, va); 1039 fprintf(stderr, "\n"); 1040 __va_end(va); 1041 exit(1); 1042 } 1043 1044 #endif 1045