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