sys/kern/subr_blist.c

   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.5 2004/07/16 05:51:10 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 ((daddr_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 malloc(a,b,c)   malloc(a)
 125 #define free(a,b)       free(a)
 126
 127 typedef unsigned int u_daddr_t;
 128
 129 #include <sys/blist.h>
 130
 131 void panic(const char *ctl, ...);
 132
 133 #endif
 134
 135 /*
 136  * static support functions
 137  */
 138
 139 static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
 140 static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk,
 141                                 daddr_t count, daddr_t radix, int skip);
 142 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
 143 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
 144                                         daddr_t radix, int skip, daddr_t blk);
 145 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
 146                                 daddr_t skip, blist_t dest, daddr_t count);
 147 static daddr_t  blst_radix_init(blmeta_t *scan, daddr_t radix,
 148                                                 int skip, daddr_t count);
 149 #ifndef _KERNEL
 150 static void     blst_radix_print(blmeta_t *scan, daddr_t blk,
 151                                         daddr_t radix, int skip, int tab);
 152 #endif
 153
 154 #ifdef _KERNEL
 155 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
 156 #endif
 157
 158 /*
 159  * blist_create() - create a blist capable of handling up to the specified
 160  *                  number of blocks
 161  *
 162  *      blocks must be greater then 0
 163  *
 164  *      The smallest blist consists of a single leaf node capable of
 165  *      managing BLIST_BMAP_RADIX blocks.
 166  */
 167
 168 blist_t
 169 blist_create(daddr_t blocks)
 170 {
 171         blist_t bl;
 172         int radix;
 173         int skip = 0;
 174
 175         /*
 176          * Calculate radix and skip field used for scanning.
 177          */
 178         radix = BLIST_BMAP_RADIX;
 179
 180         while (radix < blocks) {
 181                 radix *= BLIST_META_RADIX;
 182                 skip = (skip + 1) * BLIST_META_RADIX;
 183         }
 184
 185         bl = malloc(sizeof(struct blist), M_SWAP, M_WAITOK);
 186
 187         bzero(bl, sizeof(*bl));
 188
 189         bl->bl_blocks = blocks;
 190         bl->bl_radix = radix;
 191         bl->bl_skip = skip;
 192         bl->bl_rootblks = 1 +
 193             blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
 194         bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, M_WAITOK);
 195
 196 #if defined(BLIST_DEBUG)
 197         printf(
 198                 "BLIST representing %d blocks (%d MB of swap)"
 199                 ", requiring %dK of ram\n",
 200                 bl->bl_blocks,
 201                 bl->bl_blocks * 4 / 1024,
 202                 (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
 203         );
 204         printf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks);
 205 #endif
 206         blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks);
 207
 208         return(bl);
 209 }
 210
 211 void
 212 blist_destroy(blist_t bl)
 213 {
 214         free(bl->bl_root, M_SWAP);
 215         free(bl, M_SWAP);
 216 }
 217
 218 /*
 219  * blist_alloc() - reserve space in the block bitmap.  Return the base
 220  *                   of a contiguous region or SWAPBLK_NONE if space could
 221  *                   not be allocated.
 222  */
 223
 224 daddr_t
 225 blist_alloc(blist_t bl, daddr_t count)
 226 {
 227         daddr_t blk = SWAPBLK_NONE;
 228
 229         if (bl) {
 230                 if (bl->bl_radix == BLIST_BMAP_RADIX)
 231                         blk = blst_leaf_alloc(bl->bl_root, 0, count);
 232                 else
 233                         blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip);
 234                 if (blk != SWAPBLK_NONE)
 235                         bl->bl_free -= count;
 236         }
 237         return(blk);
 238 }
 239
 240 /*
 241  * blist_free() -       free up space in the block bitmap.  Return the base
 242  *                      of a contiguous region.  Panic if an inconsistancy is
 243  *                      found.
 244  */
 245
 246 void
 247 blist_free(blist_t bl, daddr_t blkno, daddr_t count)
 248 {
 249         if (bl) {
 250                 if (bl->bl_radix == BLIST_BMAP_RADIX)
 251                         blst_leaf_free(bl->bl_root, blkno, count);
 252                 else
 253                         blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0);
 254                 bl->bl_free += count;
 255         }
 256 }
 257
 258 /*
 259  * blist_resize() -     resize an existing radix tree to handle the
 260  *                      specified number of blocks.  This will reallocate
 261  *                      the tree and transfer the previous bitmap to the new
 262  *                      one.  When extending the tree you can specify whether
 263  *                      the new blocks are to left allocated or freed.
 264  */
 265
 266 void
 267 blist_resize(blist_t *pbl, daddr_t count, int freenew)
 268 {
 269     blist_t newbl = blist_create(count);
 270     blist_t save = *pbl;
 271
 272     *pbl = newbl;
 273     if (count > save->bl_blocks)
 274             count = save->bl_blocks;
 275     blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count);
 276
 277     /*
 278      * If resizing upwards, should we free the new space or not?
 279      */
 280     if (freenew && count < newbl->bl_blocks) {
 281             blist_free(newbl, count, newbl->bl_blocks - count);
 282     }
 283     blist_destroy(save);
 284 }
 285
 286 #ifdef BLIST_DEBUG
 287
 288 /*
 289  * blist_print()    - dump radix tree
 290  */
 291
 292 void
 293 blist_print(blist_t bl)
 294 {
 295         printf("BLIST {\n");
 296         blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4);
 297         printf("}\n");
 298 }
 299
 300 #endif
 301
 302 /************************************************************************
 303  *                        ALLOCATION SUPPORT FUNCTIONS                  *
 304  ************************************************************************
 305  *
 306  *      These support functions do all the actual work.  They may seem
 307  *      rather longish, but that's because I've commented them up.  The
 308  *      actual code is straight forward.
 309  *
 310  */
 311
 312 /*
 313  * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
 314  *
 315  *      This is the core of the allocator and is optimized for the 1 block
 316  *      and the BLIST_BMAP_RADIX block allocation cases.  Other cases are
 317  *      somewhat slower.  The 1 block allocation case is log2 and extremely
 318  *      quick.
 319  */
 320
 321 static daddr_t
 322 blst_leaf_alloc(
 323         blmeta_t *scan,
 324         daddr_t blk,
 325         int count
 326 ) {
 327         u_daddr_t orig = scan->u.bmu_bitmap;
 328
 329         if (orig == 0) {
 330                 /*
 331                  * Optimize bitmap all-allocated case.  Also, count = 1
 332                  * case assumes at least 1 bit is free in the bitmap, so
 333                  * we have to take care of this case here.
 334                  */
 335                 scan->bm_bighint = 0;
 336                 return(SWAPBLK_NONE);
 337         }
 338         if (count == 1) {
 339                 /*
 340                  * Optimized code to allocate one bit out of the bitmap
 341                  */
 342                 u_daddr_t mask;
 343                 int j = BLIST_BMAP_RADIX/2;
 344                 int r = 0;
 345
 346                 mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX/2);
 347
 348                 while (j) {
 349                         if ((orig & mask) == 0) {
 350                             r += j;
 351                             orig >>= j;
 352                         }
 353                         j >>= 1;
 354                         mask >>= j;
 355                 }
 356                 scan->u.bmu_bitmap &= ~(1 << r);
 357                 return(blk + r);
 358         }
 359         if (count <= BLIST_BMAP_RADIX) {
 360                 /*
 361                  * non-optimized code to allocate N bits out of the bitmap.
 362                  * The more bits, the faster the code runs.  It will run
 363                  * the slowest allocating 2 bits, but since there aren't any
 364                  * memory ops in the core loop (or shouldn't be, anyway),
 365                  * you probably won't notice the difference.
 366                  */
 367                 int j;
 368                 int n = BLIST_BMAP_RADIX - count;
 369                 u_daddr_t mask;
 370
 371                 mask = (u_daddr_t)-1 >> n;
 372
 373                 for (j = 0; j <= n; ++j) {
 374                         if ((orig & mask) == mask) {
 375                                 scan->u.bmu_bitmap &= ~mask;
 376                                 return(blk + j);
 377                         }
 378                         mask = (mask << 1);
 379                 }
 380         }
 381         /*
 382          * We couldn't allocate count in this subtree, update bighint.
 383          */
 384         scan->bm_bighint = count - 1;
 385         return(SWAPBLK_NONE);
 386 }
 387
 388 /*
 389  * blist_meta_alloc() - allocate at a meta in the radix tree.
 390  *
 391  *      Attempt to allocate at a meta node.  If we can't, we update
 392  *      bighint and return a failure.  Updating bighint optimize future
 393  *      calls that hit this node.  We have to check for our collapse cases
 394  *      and we have a few optimizations strewn in as well.
 395  */
 396
 397 static daddr_t
 398 blst_meta_alloc(
 399         blmeta_t *scan,
 400         daddr_t blk,
 401         daddr_t count,
 402         daddr_t radix,
 403         int skip
 404 ) {
 405         int i;
 406         int next_skip = ((u_int)skip / BLIST_META_RADIX);
 407
 408         if (scan->u.bmu_avail == 0)  {
 409                 /*
 410                  * ALL-ALLOCATED special case
 411                  */
 412                 scan->bm_bighint = count;
 413                 return(SWAPBLK_NONE);
 414         }
 415
 416         if (scan->u.bmu_avail == radix) {
 417                 radix /= BLIST_META_RADIX;
 418
 419                 /*
 420                  * ALL-FREE special case, initialize uninitialize
 421                  * sublevel.
 422                  */
 423                 for (i = 1; i <= skip; i += next_skip) {
 424                         if (scan[i].bm_bighint == (daddr_t)-1)
 425                                 break;
 426                         if (next_skip == 1) {
 427                                 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 428                                 scan[i].bm_bighint = BLIST_BMAP_RADIX;
 429                         } else {
 430                                 scan[i].bm_bighint = radix;
 431                                 scan[i].u.bmu_avail = radix;
 432                         }
 433                 }
 434         } else {
 435                 radix /= BLIST_META_RADIX;
 436         }
 437
 438         for (i = 1; i <= skip; i += next_skip) {
 439                 if (count <= scan[i].bm_bighint) {
 440                         /*
 441                          * count fits in object
 442                          */
 443                         daddr_t r;
 444                         if (next_skip == 1) {
 445                                 r = blst_leaf_alloc(&scan[i], blk, count);
 446                         } else {
 447                                 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1);
 448                         }
 449                         if (r != SWAPBLK_NONE) {
 450                                 scan->u.bmu_avail -= count;
 451                                 if (scan->bm_bighint > scan->u.bmu_avail)
 452                                         scan->bm_bighint = scan->u.bmu_avail;
 453                                 return(r);
 454                         }
 455                 } else if (scan[i].bm_bighint == (daddr_t)-1) {
 456                         /*
 457                          * Terminator
 458                          */
 459                         break;
 460                 } else if (count > radix) {
 461                         /*
 462                          * count does not fit in object even if it were
 463                          * complete free.
 464                          */
 465                         panic("blist_meta_alloc: allocation too large");
 466                 }
 467                 blk += radix;
 468         }
 469
 470         /*
 471          * We couldn't allocate count in this subtree, update bighint.
 472          */
 473         if (scan->bm_bighint >= count)
 474                 scan->bm_bighint = count - 1;
 475         return(SWAPBLK_NONE);
 476 }
 477
 478 /*
 479  * BLST_LEAF_FREE() -   free allocated block from leaf bitmap
 480  *
 481  */
 482
 483 static void
 484 blst_leaf_free(
 485         blmeta_t *scan,
 486         daddr_t blk,
 487         int count
 488 ) {
 489         /*
 490          * free some data in this bitmap
 491          *
 492          * e.g.
 493          *      0000111111111110000
 494          *          \_________/\__/
 495          *              v        n
 496          */
 497         int n = blk & (BLIST_BMAP_RADIX - 1);
 498         u_daddr_t mask;
 499
 500         mask = ((u_daddr_t)-1 << n) &
 501             ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
 502
 503         if (scan->u.bmu_bitmap & mask)
 504                 panic("blst_radix_free: freeing free block");
 505         scan->u.bmu_bitmap |= mask;
 506
 507         /*
 508          * We could probably do a better job here.  We are required to make
 509          * bighint at least as large as the biggest contiguous block of
 510          * data.  If we just shoehorn it, a little extra overhead will
 511          * be incured on the next allocation (but only that one typically).
 512          */
 513         scan->bm_bighint = BLIST_BMAP_RADIX;
 514 }
 515
 516 /*
 517  * BLST_META_FREE() - free allocated blocks from radix tree meta info
 518  *
 519  *      This support routine frees a range of blocks from the bitmap.
 520  *      The range must be entirely enclosed by this radix node.  If a
 521  *      meta node, we break the range down recursively to free blocks
 522  *      in subnodes (which means that this code can free an arbitrary
 523  *      range whereas the allocation code cannot allocate an arbitrary
 524  *      range).
 525  */
 526
 527 static void
 528 blst_meta_free(
 529         blmeta_t *scan,
 530         daddr_t freeBlk,
 531         daddr_t count,
 532         daddr_t radix,
 533         int skip,
 534         daddr_t blk
 535 ) {
 536         int i;
 537         int next_skip = ((u_int)skip / BLIST_META_RADIX);
 538
 539 #if 0
 540         printf("FREE (%x,%d) FROM (%x,%d)\n",
 541             freeBlk, count,
 542             blk, radix
 543         );
 544 #endif
 545
 546         if (scan->u.bmu_avail == 0) {
 547                 /*
 548                  * ALL-ALLOCATED special case, with possible
 549                  * shortcut to ALL-FREE special case.
 550                  */
 551                 scan->u.bmu_avail = count;
 552                 scan->bm_bighint = count;
 553
 554                 if (count != radix)  {
 555                         for (i = 1; i <= skip; i += next_skip) {
 556                                 if (scan[i].bm_bighint == (daddr_t)-1)
 557                                         break;
 558                                 scan[i].bm_bighint = 0;
 559                                 if (next_skip == 1) {
 560                                         scan[i].u.bmu_bitmap = 0;
 561                                 } else {
 562                                         scan[i].u.bmu_avail = 0;
 563                                 }
 564                         }
 565                         /* fall through */
 566                 }
 567         } else {
 568                 scan->u.bmu_avail += count;
 569                 /* scan->bm_bighint = radix; */
 570         }
 571
 572         /*
 573          * ALL-FREE special case.
 574          */
 575
 576         if (scan->u.bmu_avail == radix)
 577                 return;
 578         if (scan->u.bmu_avail > radix)
 579                 panic("blst_meta_free: freeing already free blocks (%d) %d/%d", count, scan->u.bmu_avail, radix);
 580
 581         /*
 582          * Break the free down into its components
 583          */
 584
 585         radix /= BLIST_META_RADIX;
 586
 587         i = (freeBlk - blk) / radix;
 588         blk += i * radix;
 589         i = i * next_skip + 1;
 590
 591         while (i <= skip && blk < freeBlk + count) {
 592                 daddr_t v;
 593
 594                 v = blk + radix - freeBlk;
 595                 if (v > count)
 596                         v = count;
 597
 598                 if (scan->bm_bighint == (daddr_t)-1)
 599                         panic("blst_meta_free: freeing unexpected range");
 600
 601                 if (next_skip == 1) {
 602                         blst_leaf_free(&scan[i], freeBlk, v);
 603                 } else {
 604                         blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
 605                 }
 606                 if (scan->bm_bighint < scan[i].bm_bighint)
 607                     scan->bm_bighint = scan[i].bm_bighint;
 608                 count -= v;
 609                 freeBlk += v;
 610                 blk += radix;
 611                 i += next_skip;
 612         }
 613 }
 614
 615 /*
 616  * BLIST_RADIX_COPY() - copy one radix tree to another
 617  *
 618  *      Locates free space in the source tree and frees it in the destination
 619  *      tree.  The space may not already be free in the destination.
 620  */
 621
 622 static void blst_copy(
 623         blmeta_t *scan,
 624         daddr_t blk,
 625         daddr_t radix,
 626         daddr_t skip,
 627         blist_t dest,
 628         daddr_t count
 629 ) {
 630         int next_skip;
 631         int i;
 632
 633         /*
 634          * Leaf node
 635          */
 636
 637         if (radix == BLIST_BMAP_RADIX) {
 638                 u_daddr_t v = scan->u.bmu_bitmap;
 639
 640                 if (v == (u_daddr_t)-1) {
 641                         blist_free(dest, blk, count);
 642                 } else if (v != 0) {
 643                         int i;
 644
 645                         for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) {
 646                                 if (v & (1 << i))
 647                                         blist_free(dest, blk + i, 1);
 648                         }
 649                 }
 650                 return;
 651         }
 652
 653         /*
 654          * Meta node
 655          */
 656
 657         if (scan->u.bmu_avail == 0) {
 658                 /*
 659                  * Source all allocated, leave dest allocated
 660                  */
 661                 return;
 662         }
 663         if (scan->u.bmu_avail == radix) {
 664                 /*
 665                  * Source all free, free entire dest
 666                  */
 667                 if (count < radix)
 668                         blist_free(dest, blk, count);
 669                 else
 670                         blist_free(dest, blk, radix);
 671                 return;
 672         }
 673
 674
 675         radix /= BLIST_META_RADIX;
 676         next_skip = ((u_int)skip / BLIST_META_RADIX);
 677
 678         for (i = 1; count && i <= skip; i += next_skip) {
 679                 if (scan[i].bm_bighint == (daddr_t)-1)
 680                         break;
 681
 682                 if (count >= radix) {
 683                         blst_copy(
 684                             &scan[i],
 685                             blk,
 686                             radix,
 687                             next_skip - 1,
 688                             dest,
 689                             radix
 690                         );
 691                         count -= radix;
 692                 } else {
 693                         if (count) {
 694                                 blst_copy(
 695                                     &scan[i],
 696                                     blk,
 697                                     radix,
 698                                     next_skip - 1,
 699                                     dest,
 700                                     count
 701                                 );
 702                         }
 703                         count = 0;
 704                 }
 705                 blk += radix;
 706         }
 707 }
 708
 709 /*
 710  * BLST_RADIX_INIT() - initialize radix tree
 711  *
 712  *      Initialize our meta structures and bitmaps and calculate the exact
 713  *      amount of space required to manage 'count' blocks - this space may
 714  *      be considerably less then the calculated radix due to the large
 715  *      RADIX values we use.
 716  */
 717
 718 static daddr_t
 719 blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count)
 720 {
 721         int i;
 722         int next_skip;
 723         daddr_t memindex = 0;
 724
 725         /*
 726          * Leaf node
 727          */
 728
 729         if (radix == BLIST_BMAP_RADIX) {
 730                 if (scan) {
 731                         scan->bm_bighint = 0;
 732                         scan->u.bmu_bitmap = 0;
 733                 }
 734                 return(memindex);
 735         }
 736
 737         /*
 738          * Meta node.  If allocating the entire object we can special
 739          * case it.  However, we need to figure out how much memory
 740          * is required to manage 'count' blocks, so we continue on anyway.
 741          */
 742
 743         if (scan) {
 744                 scan->bm_bighint = 0;
 745                 scan->u.bmu_avail = 0;
 746         }
 747
 748         radix /= BLIST_META_RADIX;
 749         next_skip = ((u_int)skip / BLIST_META_RADIX);
 750
 751         for (i = 1; i <= skip; i += next_skip) {
 752                 if (count >= radix) {
 753                         /*
 754                          * Allocate the entire object
 755                          */
 756                         memindex = i + blst_radix_init(
 757                             ((scan) ? &scan[i] : NULL),
 758                             radix,
 759                             next_skip - 1,
 760                             radix
 761                         );
 762                         count -= radix;
 763                 } else if (count > 0) {
 764                         /*
 765                          * Allocate a partial object
 766                          */
 767                         memindex = i + blst_radix_init(
 768                             ((scan) ? &scan[i] : NULL),
 769                             radix,
 770                             next_skip - 1,
 771                             count
 772                         );
 773                         count = 0;
 774                 } else {
 775                         /*
 776                          * Add terminator and break out
 777                          */
 778                         if (scan)
 779                                 scan[i].bm_bighint = (daddr_t)-1;
 780                         break;
 781                 }
 782         }
 783         if (memindex < i)
 784                 memindex = i;
 785         return(memindex);
 786 }
 787
 788 #ifdef BLIST_DEBUG
 789
 790 static void
 791 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab)
 792 {
 793         int i;
 794         int next_skip;
 795         int lastState = 0;
 796
 797         if (radix == BLIST_BMAP_RADIX) {
 798                 printf(
 799                     "%*.*s(%04x,%d): bitmap %08x big=%d\n",
 800                     tab, tab, "",
 801                     blk, radix,
 802                     scan->u.bmu_bitmap,
 803                     scan->bm_bighint
 804                 );
 805                 return;
 806         }
 807
 808         if (scan->u.bmu_avail == 0) {
 809                 printf(
 810                     "%*.*s(%04x,%d) ALL ALLOCATED\n",
 811                     tab, tab, "",
 812                     blk,
 813                     radix
 814                 );
 815                 return;
 816         }
 817         if (scan->u.bmu_avail == radix) {
 818                 printf(
 819                     "%*.*s(%04x,%d) ALL FREE\n",
 820                     tab, tab, "",
 821                     blk,
 822                     radix
 823                 );
 824                 return;
 825         }
 826
 827         printf(
 828             "%*.*s(%04x,%d): subtree (%d/%d) big=%d {\n",
 829             tab, tab, "",
 830             blk, radix,
 831             scan->u.bmu_avail,
 832             radix,
 833             scan->bm_bighint
 834         );
 835
 836         radix /= BLIST_META_RADIX;
 837         next_skip = ((u_int)skip / BLIST_META_RADIX);
 838         tab += 4;
 839
 840         for (i = 1; i <= skip; i += next_skip) {
 841                 if (scan[i].bm_bighint == (daddr_t)-1) {
 842                         printf(
 843                             "%*.*s(%04x,%d): Terminator\n",
 844                             tab, tab, "",
 845                             blk, radix
 846                         );
 847                         lastState = 0;
 848                         break;
 849                 }
 850                 blst_radix_print(
 851                     &scan[i],
 852                     blk,
 853                     radix,
 854                     next_skip - 1,
 855                     tab
 856                 );
 857                 blk += radix;
 858         }
 859         tab -= 4;
 860
 861         printf(
 862             "%*.*s}\n",
 863             tab, tab, ""
 864         );
 865 }
 866
 867 #endif
 868
 869 #ifdef BLIST_DEBUG
 870
 871 int
 872 main(int ac, char **av)
 873 {
 874         int size = 1024;
 875         int i;
 876         blist_t bl;
 877
 878         for (i = 1; i < ac; ++i) {
 879                 const char *ptr = av[i];
 880                 if (*ptr != '-') {
 881                         size = strtol(ptr, NULL, 0);
 882                         continue;
 883                 }
 884                 ptr += 2;
 885                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
 886                 exit(1);
 887         }
 888         bl = blist_create(size);
 889         blist_free(bl, 0, size);
 890
 891         for (;;) {
 892                 char buf[1024];
 893                 daddr_t da = 0;
 894                 daddr_t count = 0;
 895
 896
 897                 printf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
 898                 fflush(stdout);
 899                 if (fgets(buf, sizeof(buf), stdin) == NULL)
 900                         break;
 901                 switch(buf[0]) {
 902                 case 'r':
 903                         if (sscanf(buf + 1, "%d", &count) == 1) {
 904                                 blist_resize(&bl, count, 1);
 905                         } else {
 906                                 printf("?\n");
 907                         }
 908                 case 'p':
 909                         blist_print(bl);
 910                         break;
 911                 case 'a':
 912                         if (sscanf(buf + 1, "%d", &count) == 1) {
 913                                 daddr_t blk = blist_alloc(bl, count);
 914                                 printf("    R=%04x\n", blk);
 915                         } else {
 916                                 printf("?\n");
 917                         }
 918                         break;
 919                 case 'f':
 920                         if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
 921                                 blist_free(bl, da, count);
 922                         } else {
 923                                 printf("?\n");
 924                         }
 925                         break;
 926                 case '?':
 927                 case 'h':
 928                         puts(
 929                             "p          -print\n"
 930                             "a %d       -allocate\n"
 931                             "f %x %d    -free\n"
 932                             "r %d       -resize\n"
 933                             "h/?        -help"
 934                         );
 935                         break;
 936                 default:
 937                         printf("?\n");
 938                         break;
 939                 }
 940         }
 941         return(0);
 942 }
 943
 944 void
 945 panic(const char *ctl, ...)
 946 {
 947         __va_list va;
 948
 949         __va_start(va, ctl);
 950         vfprintf(stderr, ctl, va);
 951         fprintf(stderr, "\n");
 952         __va_end(va);
 953         exit(1);
 954 }
 955
 956 #endif
 957