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