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.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