sys/kern/subr_blist.c

   1 /*-
   2  * Copyright (c) 1998 Matthew Dillon.  All Rights Reserved.
   3  * Redistribution and use in source and binary forms, with or without
   4  * modification, are permitted provided that the following conditions
   5  * are met:
   6  * 1. Redistributions of source code must retain the above copyright
   7  *    notice, this list of conditions and the following disclaimer.
   8  * 2. Redistributions in binary form must reproduce the above copyright
   9  *    notice, this list of conditions and the following disclaimer in the
  10  *    documentation and/or other materials provided with the distribution.
  11  * 4. Neither the name of the University nor the names of its contributors
  12  *    may be used to endorse or promote products derived from this software
  13  *    without specific prior written permission.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  16  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  19  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  21  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  22  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  24  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27 /*
  28  * BLIST.C -    Bitmap allocator/deallocator, using a radix tree with hinting
  29  *
  30  *      This module implements a general bitmap allocator/deallocator.  The
  31  *      allocator eats around 2 bits per 'block'.  The module does not
  32  *      try to interpret the meaning of a 'block' other than to return
  33  *      SWAPBLK_NONE on an allocation failure.
  34  *
  35  *      A radix tree is used to maintain the bitmap.  Two radix constants are
  36  *      involved:  One for the bitmaps contained in the leaf nodes (typically
  37  *      32), and one for the meta nodes (typically 16).  Both meta and leaf
  38  *      nodes have a hint field.  This field gives us a hint as to the largest
  39  *      free contiguous range of blocks under the node.  It may contain a
  40  *      value that is too high, but will never contain a value that is too
  41  *      low.  When the radix tree is searched, allocation failures in subtrees
  42  *      update the hint.
  43  *
  44  *      The radix tree also implements two collapsed states for meta nodes:
  45  *      the ALL-ALLOCATED state and the ALL-FREE state.  If a meta node is
  46  *      in either of these two states, all information contained underneath
  47  *      the node is considered stale.  These states are used to optimize
  48  *      allocation and freeing operations.
  49  *
  50  *      The hinting greatly increases code efficiency for allocations while
  51  *      the general radix structure optimizes both allocations and frees.  The
  52  *      radix tree should be able to operate well no matter how much
  53  *      fragmentation there is and no matter how large a bitmap is used.
  54  *
  55  *      The blist code wires all necessary memory at creation time.  Neither
  56  *      allocations nor frees require interaction with the memory subsystem.
  57  *      The non-blocking features of the blist code are used in the swap code
  58  *      (vm/swap_pager.c).
  59  *
  60  *      LAYOUT: The radix tree is layed out recursively using a
  61  *      linear array.  Each meta node is immediately followed (layed out
  62  *      sequentially in memory) by BLIST_META_RADIX lower level nodes.  This
  63  *      is a recursive structure but one that can be easily scanned through
  64  *      a very simple 'skip' calculation.  In order to support large radixes,
  65  *      portions of the tree may reside outside our memory allocation.  We
  66  *      handle this with an early-termination optimization (when bighint is
  67  *      set to -1) on the scan.  The memory allocation is only large enough
  68  *      to cover the number of blocks requested at creation time even if it
  69  *      must be encompassed in larger root-node radix.
  70  *
  71  *      NOTE: the allocator cannot currently allocate more than
  72  *      BLIST_BMAP_RADIX blocks per call.  It will panic with 'allocation too
  73  *      large' if you try.  This is an area that could use improvement.  The
  74  *      radix is large enough that this restriction does not effect the swap
  75  *      system, though.  Currently only the allocation code is effected by
  76  *      this algorithmic unfeature.  The freeing code can handle arbitrary
  77  *      ranges.
  78  *
  79  *      This code can be compiled stand-alone for debugging.
  80  */
  81
  82 #include <sys/cdefs.h>
  83 __FBSDID("$FreeBSD$");
  84
  85 #ifdef _KERNEL
  86
  87 #include <sys/param.h>
  88 #include <sys/systm.h>
  89 #include <sys/lock.h>
  90 #include <sys/kernel.h>
  91 #include <sys/blist.h>
  92 #include <sys/malloc.h>
  93 #include <sys/proc.h>
  94 #include <sys/mutex.h>
  95
  96 #else
  97
  98 #ifndef BLIST_NO_DEBUG
  99 #define BLIST_DEBUG
 100 #endif
 101
 102 #define SWAPBLK_NONE ((daddr_t)-1)
 103
 104 #include <sys/types.h>
 105 #include <stdio.h>
 106 #include <string.h>
 107 #include <stdlib.h>
 108 #include <stdarg.h>
 109
 110 #define malloc(a,b,c)   calloc(a, 1)
 111 #define free(a,b)       free(a)
 112
 113 typedef unsigned int u_daddr_t;
 114
 115 #include <sys/blist.h>
 116
 117 void panic(const char *ctl, ...);
 118
 119 #endif
 120
 121 /*
 122  * static support functions
 123  */
 124
 125 static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
 126 static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk,
 127                                 daddr_t count, daddr_t radix, int skip);
 128 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
 129 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
 130                                         daddr_t radix, int skip, daddr_t blk);
 131 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
 132                                 daddr_t skip, blist_t dest, daddr_t count);
 133 static int blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);
 134 static int blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count,
 135                                 daddr_t radix, int skip, daddr_t blk);
 136 static daddr_t  blst_radix_init(blmeta_t *scan, daddr_t radix,
 137                                                 int skip, daddr_t count);
 138 #ifndef _KERNEL
 139 static void     blst_radix_print(blmeta_t *scan, daddr_t blk,
 140                                         daddr_t radix, int skip, int tab);
 141 #endif
 142
 143 #ifdef _KERNEL
 144 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
 145 #endif
 146
 147 /*
 148  * blist_create() - create a blist capable of handling up to the specified
 149  *                  number of blocks
 150  *
 151  *      blocks - must be greater than 0
 152  *      flags  - malloc flags
 153  *
 154  *      The smallest blist consists of a single leaf node capable of
 155  *      managing BLIST_BMAP_RADIX blocks.
 156  */
 157
 158 blist_t
 159 blist_create(daddr_t blocks, int flags)
 160 {
 161         blist_t bl;
 162         int radix;
 163         int skip = 0;
 164
 165         /*
 166          * Calculate radix and skip field used for scanning.
 167          */
 168         radix = BLIST_BMAP_RADIX;
 169
 170         while (radix < blocks) {
 171                 radix *= BLIST_META_RADIX;
 172                 skip = (skip + 1) * BLIST_META_RADIX;
 173         }
 174
 175         bl = malloc(sizeof(struct blist), M_SWAP, flags | M_ZERO);
 176
 177         bl->bl_blocks = blocks;
 178         bl->bl_radix = radix;
 179         bl->bl_skip = skip;
 180         bl->bl_rootblks = 1 +
 181             blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
 182         bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, flags);
 183
 184 #if defined(BLIST_DEBUG)
 185         printf(
 186                 "BLIST representing %lld blocks (%lld MB of swap)"
 187                 ", requiring %lldK of ram\n",
 188                 (long long)bl->bl_blocks,
 189                 (long long)bl->bl_blocks * 4 / 1024,
 190                 (long long)(bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
 191         );
 192         printf("BLIST raw radix tree contains %lld records\n",
 193             (long long)bl->bl_rootblks);
 194 #endif
 195         blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks);
 196
 197         return(bl);
 198 }
 199
 200 void
 201 blist_destroy(blist_t bl)
 202 {
 203         free(bl->bl_root, M_SWAP);
 204         free(bl, M_SWAP);
 205 }
 206
 207 /*
 208  * blist_alloc() - reserve space in the block bitmap.  Return the base
 209  *                   of a contiguous region or SWAPBLK_NONE if space could
 210  *                   not be allocated.
 211  */
 212
 213 daddr_t
 214 blist_alloc(blist_t bl, daddr_t count)
 215 {
 216         daddr_t blk = SWAPBLK_NONE;
 217
 218         if (bl) {
 219                 if (bl->bl_radix == BLIST_BMAP_RADIX)
 220                         blk = blst_leaf_alloc(bl->bl_root, 0, count);
 221                 else
 222                         blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip);
 223                 if (blk != SWAPBLK_NONE)
 224                         bl->bl_free -= count;
 225         }
 226         return(blk);
 227 }
 228
 229 /*
 230  * blist_free() -       free up space in the block bitmap.  Return the base
 231  *                      of a contiguous region.  Panic if an inconsistancy is
 232  *                      found.
 233  */
 234
 235 void
 236 blist_free(blist_t bl, daddr_t blkno, daddr_t count)
 237 {
 238         if (bl) {
 239                 if (bl->bl_radix == BLIST_BMAP_RADIX)
 240                         blst_leaf_free(bl->bl_root, blkno, count);
 241                 else
 242                         blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0);
 243                 bl->bl_free += count;
 244         }
 245 }
 246
 247 /*
 248  * blist_fill() -       mark a region in the block bitmap as off-limits
 249  *                      to the allocator (i.e. allocate it), ignoring any
 250  *                      existing allocations.  Return the number of blocks
 251  *                      actually filled that were free before the call.
 252  */
 253
 254 int
 255 blist_fill(blist_t bl, daddr_t blkno, daddr_t count)
 256 {
 257         int filled;
 258
 259         if (bl) {
 260                 if (bl->bl_radix == BLIST_BMAP_RADIX)
 261                         filled = blst_leaf_fill(bl->bl_root, blkno, count);
 262                 else
 263                         filled = blst_meta_fill(bl->bl_root, blkno, count,
 264                             bl->bl_radix, bl->bl_skip, 0);
 265                 bl->bl_free -= filled;
 266                 return filled;
 267         } else
 268                 return 0;
 269 }
 270
 271 /*
 272  * blist_resize() -     resize an existing radix tree to handle the
 273  *                      specified number of blocks.  This will reallocate
 274  *                      the tree and transfer the previous bitmap to the new
 275  *                      one.  When extending the tree you can specify whether
 276  *                      the new blocks are to left allocated or freed.
 277  */
 278
 279 void
 280 blist_resize(blist_t *pbl, daddr_t count, int freenew, int flags)
 281 {
 282     blist_t newbl = blist_create(count, flags);
 283     blist_t save = *pbl;
 284
 285     *pbl = newbl;
 286     if (count > save->bl_blocks)
 287             count = save->bl_blocks;
 288     blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count);
 289
 290     /*
 291      * If resizing upwards, should we free the new space or not?
 292      */
 293     if (freenew && count < newbl->bl_blocks) {
 294             blist_free(newbl, count, newbl->bl_blocks - count);
 295     }
 296     blist_destroy(save);
 297 }
 298
 299 #ifdef BLIST_DEBUG
 300
 301 /*
 302  * blist_print()    - dump radix tree
 303  */
 304
 305 void
 306 blist_print(blist_t bl)
 307 {
 308         printf("BLIST {\n");
 309         blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4);
 310         printf("}\n");
 311 }
 312
 313 #endif
 314
 315 /************************************************************************
 316  *                        ALLOCATION SUPPORT FUNCTIONS                  *
 317  ************************************************************************
 318  *
 319  *      These support functions do all the actual work.  They may seem
 320  *      rather longish, but that's because I've commented them up.  The
 321  *      actual code is straight forward.
 322  *
 323  */
 324
 325 /*
 326  * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
 327  *
 328  *      This is the core of the allocator and is optimized for the 1 block
 329  *      and the BLIST_BMAP_RADIX block allocation cases.  Other cases are
 330  *      somewhat slower.  The 1 block allocation case is log2 and extremely
 331  *      quick.
 332  */
 333
 334 static daddr_t
 335 blst_leaf_alloc(
 336         blmeta_t *scan,
 337         daddr_t blk,
 338         int count
 339 ) {
 340         u_daddr_t orig = scan->u.bmu_bitmap;
 341
 342         if (orig == 0) {
 343                 /*
 344                  * Optimize bitmap all-allocated case.  Also, count = 1
 345                  * case assumes at least 1 bit is free in the bitmap, so
 346                  * we have to take care of this case here.
 347                  */
 348                 scan->bm_bighint = 0;
 349                 return(SWAPBLK_NONE);
 350         }
 351         if (count == 1) {
 352                 /*
 353                  * Optimized code to allocate one bit out of the bitmap
 354                  */
 355                 u_daddr_t mask;
 356                 int j = BLIST_BMAP_RADIX/2;
 357                 int r = 0;
 358
 359                 mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX/2);
 360
 361                 while (j) {
 362                         if ((orig & mask) == 0) {
 363                             r += j;
 364                             orig >>= j;
 365                         }
 366                         j >>= 1;
 367                         mask >>= j;
 368                 }
 369                 scan->u.bmu_bitmap &= ~(1 << r);
 370                 return(blk + r);
 371         }
 372         if (count <= BLIST_BMAP_RADIX) {
 373                 /*
 374                  * non-optimized code to allocate N bits out of the bitmap.
 375                  * The more bits, the faster the code runs.  It will run
 376                  * the slowest allocating 2 bits, but since there aren't any
 377                  * memory ops in the core loop (or shouldn't be, anyway),
 378                  * you probably won't notice the difference.
 379                  */
 380                 int j;
 381                 int n = BLIST_BMAP_RADIX - count;
 382                 u_daddr_t mask;
 383
 384                 mask = (u_daddr_t)-1 >> n;
 385
 386                 for (j = 0; j <= n; ++j) {
 387                         if ((orig & mask) == mask) {
 388                                 scan->u.bmu_bitmap &= ~mask;
 389                                 return(blk + j);
 390                         }
 391                         mask = (mask << 1);
 392                 }
 393         }
 394         /*
 395          * We couldn't allocate count in this subtree, update bighint.
 396          */
 397         scan->bm_bighint = count - 1;
 398         return(SWAPBLK_NONE);
 399 }
 400
 401 /*
 402  * blist_meta_alloc() - allocate at a meta in the radix tree.
 403  *
 404  *      Attempt to allocate at a meta node.  If we can't, we update
 405  *      bighint and return a failure.  Updating bighint optimize future
 406  *      calls that hit this node.  We have to check for our collapse cases
 407  *      and we have a few optimizations strewn in as well.
 408  */
 409
 410 static daddr_t
 411 blst_meta_alloc(
 412         blmeta_t *scan,
 413         daddr_t blk,
 414         daddr_t count,
 415         daddr_t radix,
 416         int skip
 417 ) {
 418         int i;
 419         int next_skip = ((u_int)skip / BLIST_META_RADIX);
 420
 421         if (scan->u.bmu_avail == 0)  {
 422                 /*
 423                  * ALL-ALLOCATED special case
 424                  */
 425                 scan->bm_bighint = count;
 426                 return(SWAPBLK_NONE);
 427         }
 428
 429         if (scan->u.bmu_avail == radix) {
 430                 radix /= BLIST_META_RADIX;
 431
 432                 /*
 433                  * ALL-FREE special case, initialize uninitialize
 434                  * sublevel.
 435                  */
 436                 for (i = 1; i <= skip; i += next_skip) {
 437                         if (scan[i].bm_bighint == (daddr_t)-1)
 438                                 break;
 439                         if (next_skip == 1) {
 440                                 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 441                                 scan[i].bm_bighint = BLIST_BMAP_RADIX;
 442                         } else {
 443                                 scan[i].bm_bighint = radix;
 444                                 scan[i].u.bmu_avail = radix;
 445                         }
 446                 }
 447         } else {
 448                 radix /= BLIST_META_RADIX;
 449         }
 450
 451         for (i = 1; i <= skip; i += next_skip) {
 452                 if (count <= scan[i].bm_bighint) {
 453                         /*
 454                          * count fits in object
 455                          */
 456                         daddr_t r;
 457                         if (next_skip == 1) {
 458                                 r = blst_leaf_alloc(&scan[i], blk, count);
 459                         } else {
 460                                 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1);
 461                         }
 462                         if (r != SWAPBLK_NONE) {
 463                                 scan->u.bmu_avail -= count;
 464                                 if (scan->bm_bighint > scan->u.bmu_avail)
 465                                         scan->bm_bighint = scan->u.bmu_avail;
 466                                 return(r);
 467                         }
 468                 } else if (scan[i].bm_bighint == (daddr_t)-1) {
 469                         /*
 470                          * Terminator
 471                          */
 472                         break;
 473                 } else if (count > radix) {
 474                         /*
 475                          * count does not fit in object even if it were
 476                          * complete free.
 477                          */
 478                         panic("blist_meta_alloc: allocation too large");
 479                 }
 480                 blk += radix;
 481         }
 482
 483         /*
 484          * We couldn't allocate count in this subtree, update bighint.
 485          */
 486         if (scan->bm_bighint >= count)
 487                 scan->bm_bighint = count - 1;
 488         return(SWAPBLK_NONE);
 489 }
 490
 491 /*
 492  * BLST_LEAF_FREE() -   free allocated block from leaf bitmap
 493  *
 494  */
 495
 496 static void
 497 blst_leaf_free(
 498         blmeta_t *scan,
 499         daddr_t blk,
 500         int count
 501 ) {
 502         /*
 503          * free some data in this bitmap
 504          *
 505          * e.g.
 506          *      0000111111111110000
 507          *          \_________/\__/
 508          *              v        n
 509          */
 510         int n = blk & (BLIST_BMAP_RADIX - 1);
 511         u_daddr_t mask;
 512
 513         mask = ((u_daddr_t)-1 << n) &
 514             ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
 515
 516         if (scan->u.bmu_bitmap & mask)
 517                 panic("blst_radix_free: freeing free block");
 518         scan->u.bmu_bitmap |= mask;
 519
 520         /*
 521          * We could probably do a better job here.  We are required to make
 522          * bighint at least as large as the biggest contiguous block of
 523          * data.  If we just shoehorn it, a little extra overhead will
 524          * be incured on the next allocation (but only that one typically).
 525          */
 526         scan->bm_bighint = BLIST_BMAP_RADIX;
 527 }
 528
 529 /*
 530  * BLST_META_FREE() - free allocated blocks from radix tree meta info
 531  *
 532  *      This support routine frees a range of blocks from the bitmap.
 533  *      The range must be entirely enclosed by this radix node.  If a
 534  *      meta node, we break the range down recursively to free blocks
 535  *      in subnodes (which means that this code can free an arbitrary
 536  *      range whereas the allocation code cannot allocate an arbitrary
 537  *      range).
 538  */
 539
 540 static void
 541 blst_meta_free(
 542         blmeta_t *scan,
 543         daddr_t freeBlk,
 544         daddr_t count,
 545         daddr_t radix,
 546         int skip,
 547         daddr_t blk
 548 ) {
 549         int i;
 550         int next_skip = ((u_int)skip / BLIST_META_RADIX);
 551
 552 #if 0
 553         printf("free (%llx,%lld) FROM (%llx,%lld)\n",
 554             (long long)freeBlk, (long long)count,
 555             (long long)blk, (long long)radix
 556         );
 557 #endif
 558
 559         if (scan->u.bmu_avail == 0) {
 560                 /*
 561                  * ALL-ALLOCATED special case, with possible
 562                  * shortcut to ALL-FREE special case.
 563                  */
 564                 scan->u.bmu_avail = count;
 565                 scan->bm_bighint = count;
 566
 567                 if (count != radix)  {
 568                         for (i = 1; i <= skip; i += next_skip) {
 569                                 if (scan[i].bm_bighint == (daddr_t)-1)
 570                                         break;
 571                                 scan[i].bm_bighint = 0;
 572                                 if (next_skip == 1) {
 573                                         scan[i].u.bmu_bitmap = 0;
 574                                 } else {
 575                                         scan[i].u.bmu_avail = 0;
 576                                 }
 577                         }
 578                         /* fall through */
 579                 }
 580         } else {
 581                 scan->u.bmu_avail += count;
 582                 /* scan->bm_bighint = radix; */
 583         }
 584
 585         /*
 586          * ALL-FREE special case.
 587          */
 588
 589         if (scan->u.bmu_avail == radix)
 590                 return;
 591         if (scan->u.bmu_avail > radix)
 592                 panic("blst_meta_free: freeing already free blocks (%lld) %lld/%lld",
 593                     (long long)count, (long long)scan->u.bmu_avail,
 594                     (long long)radix);
 595
 596         /*
 597          * Break the free down into its components
 598          */
 599
 600         radix /= BLIST_META_RADIX;
 601
 602         i = (freeBlk - blk) / radix;
 603         blk += i * radix;
 604         i = i * next_skip + 1;
 605
 606         while (i <= skip && blk < freeBlk + count) {
 607                 daddr_t v;
 608
 609                 v = blk + radix - freeBlk;
 610                 if (v > count)
 611                         v = count;
 612
 613                 if (scan->bm_bighint == (daddr_t)-1)
 614                         panic("blst_meta_free: freeing unexpected range");
 615
 616                 if (next_skip == 1) {
 617                         blst_leaf_free(&scan[i], freeBlk, v);
 618                 } else {
 619                         blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
 620                 }
 621                 if (scan->bm_bighint < scan[i].bm_bighint)
 622                     scan->bm_bighint = scan[i].bm_bighint;
 623                 count -= v;
 624                 freeBlk += v;
 625                 blk += radix;
 626                 i += next_skip;
 627         }
 628 }
 629
 630 /*
 631  * BLIST_RADIX_COPY() - copy one radix tree to another
 632  *
 633  *      Locates free space in the source tree and frees it in the destination
 634  *      tree.  The space may not already be free in the destination.
 635  */
 636
 637 static void blst_copy(
 638         blmeta_t *scan,
 639         daddr_t blk,
 640         daddr_t radix,
 641         daddr_t skip,
 642         blist_t dest,
 643         daddr_t count
 644 ) {
 645         int next_skip;
 646         int i;
 647
 648         /*
 649          * Leaf node
 650          */
 651
 652         if (radix == BLIST_BMAP_RADIX) {
 653                 u_daddr_t v = scan->u.bmu_bitmap;
 654
 655                 if (v == (u_daddr_t)-1) {
 656                         blist_free(dest, blk, count);
 657                 } else if (v != 0) {
 658                         int i;
 659
 660                         for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) {
 661                                 if (v & (1 << i))
 662                                         blist_free(dest, blk + i, 1);
 663                         }
 664                 }
 665                 return;
 666         }
 667
 668         /*
 669          * Meta node
 670          */
 671
 672         if (scan->u.bmu_avail == 0) {
 673                 /*
 674                  * Source all allocated, leave dest allocated
 675                  */
 676                 return;
 677         }
 678         if (scan->u.bmu_avail == radix) {
 679                 /*
 680                  * Source all free, free entire dest
 681                  */
 682                 if (count < radix)
 683                         blist_free(dest, blk, count);
 684                 else
 685                         blist_free(dest, blk, radix);
 686                 return;
 687         }
 688
 689
 690         radix /= BLIST_META_RADIX;
 691         next_skip = ((u_int)skip / BLIST_META_RADIX);
 692
 693         for (i = 1; count && i <= skip; i += next_skip) {
 694                 if (scan[i].bm_bighint == (daddr_t)-1)
 695                         break;
 696
 697                 if (count >= radix) {
 698                         blst_copy(
 699                             &scan[i],
 700                             blk,
 701                             radix,
 702                             next_skip - 1,
 703                             dest,
 704                             radix
 705                         );
 706                         count -= radix;
 707                 } else {
 708                         if (count) {
 709                                 blst_copy(
 710                                     &scan[i],
 711                                     blk,
 712                                     radix,
 713                                     next_skip - 1,
 714                                     dest,
 715                                     count
 716                                 );
 717                         }
 718                         count = 0;
 719                 }
 720                 blk += radix;
 721         }
 722 }
 723
 724 /*
 725  * BLST_LEAF_FILL() -   allocate specific blocks in leaf bitmap
 726  *
 727  *      This routine allocates all blocks in the specified range
 728  *      regardless of any existing allocations in that range.  Returns
 729  *      the number of blocks allocated by the call.
 730  */
 731
 732 static int
 733 blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
 734 {
 735         int n = blk & (BLIST_BMAP_RADIX - 1);
 736         int nblks;
 737         u_daddr_t mask, bitmap;
 738
 739         mask = ((u_daddr_t)-1 << n) &
 740             ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
 741
 742         /* Count the number of blocks we're about to allocate */
 743         bitmap = scan->u.bmu_bitmap & mask;
 744         for (nblks = 0; bitmap != 0; nblks++)
 745                 bitmap &= bitmap - 1;
 746
 747         scan->u.bmu_bitmap &= ~mask;
 748         return nblks;
 749 }
 750
 751 /*
 752  * BLIST_META_FILL() -  allocate specific blocks at a meta node
 753  *
 754  *      This routine allocates the specified range of blocks,
 755  *      regardless of any existing allocations in the range.  The
 756  *      range must be within the extent of this node.  Returns the
 757  *      number of blocks allocated by the call.
 758  */
 759 static int
 760 blst_meta_fill(
 761         blmeta_t *scan,
 762         daddr_t allocBlk,
 763         daddr_t count,
 764         daddr_t radix,
 765         int skip,
 766         daddr_t blk
 767 ) {
 768         int i;
 769         int next_skip = ((u_int)skip / BLIST_META_RADIX);
 770         int nblks = 0;
 771
 772         if (count == radix || scan->u.bmu_avail == 0)  {
 773                 /*
 774                  * ALL-ALLOCATED special case
 775                  */
 776                 nblks = scan->u.bmu_avail;
 777                 scan->u.bmu_avail = 0;
 778                 scan->bm_bighint = count;
 779                 return nblks;
 780         }
 781
 782         if (scan->u.bmu_avail == radix) {
 783                 radix /= BLIST_META_RADIX;
 784
 785                 /*
 786                  * ALL-FREE special case, initialize sublevel
 787                  */
 788                 for (i = 1; i <= skip; i += next_skip) {
 789                         if (scan[i].bm_bighint == (daddr_t)-1)
 790                                 break;
 791                         if (next_skip == 1) {
 792                                 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 793                                 scan[i].bm_bighint = BLIST_BMAP_RADIX;
 794                         } else {
 795                                 scan[i].bm_bighint = radix;
 796                                 scan[i].u.bmu_avail = radix;
 797                         }
 798                 }
 799         } else {
 800                 radix /= BLIST_META_RADIX;
 801         }
 802
 803         if (count > radix)
 804                 panic("blist_meta_fill: allocation too large");
 805
 806         i = (allocBlk - blk) / radix;
 807         blk += i * radix;
 808         i = i * next_skip + 1;
 809
 810         while (i <= skip && blk < allocBlk + count) {
 811                 daddr_t v;
 812
 813                 v = blk + radix - allocBlk;
 814                 if (v > count)
 815                         v = count;
 816
 817                 if (scan->bm_bighint == (daddr_t)-1)
 818                         panic("blst_meta_fill: filling unexpected range");
 819
 820                 if (next_skip == 1) {
 821                         nblks += blst_leaf_fill(&scan[i], allocBlk, v);
 822                 } else {
 823                         nblks += blst_meta_fill(&scan[i], allocBlk, v,
 824                             radix, next_skip - 1, blk);
 825                 }
 826                 count -= v;
 827                 allocBlk += v;
 828                 blk += radix;
 829                 i += next_skip;
 830         }
 831         scan->u.bmu_avail -= nblks;
 832         return nblks;
 833 }
 834
 835 /*
 836  * BLST_RADIX_INIT() - initialize radix tree
 837  *
 838  *      Initialize our meta structures and bitmaps and calculate the exact
 839  *      amount of space required to manage 'count' blocks - this space may
 840  *      be considerably less than the calculated radix due to the large
 841  *      RADIX values we use.
 842  */
 843
 844 static daddr_t
 845 blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count)
 846 {
 847         int i;
 848         int next_skip;
 849         daddr_t memindex = 0;
 850
 851         /*
 852          * Leaf node
 853          */
 854
 855         if (radix == BLIST_BMAP_RADIX) {
 856                 if (scan) {
 857                         scan->bm_bighint = 0;
 858                         scan->u.bmu_bitmap = 0;
 859                 }
 860                 return(memindex);
 861         }
 862
 863         /*
 864          * Meta node.  If allocating the entire object we can special
 865          * case it.  However, we need to figure out how much memory
 866          * is required to manage 'count' blocks, so we continue on anyway.
 867          */
 868
 869         if (scan) {
 870                 scan->bm_bighint = 0;
 871                 scan->u.bmu_avail = 0;
 872         }
 873
 874         radix /= BLIST_META_RADIX;
 875         next_skip = ((u_int)skip / BLIST_META_RADIX);
 876
 877         for (i = 1; i <= skip; i += next_skip) {
 878                 if (count >= radix) {
 879                         /*
 880                          * Allocate the entire object
 881                          */
 882                         memindex = i + blst_radix_init(
 883                             ((scan) ? &scan[i] : NULL),
 884                             radix,
 885                             next_skip - 1,
 886                             radix
 887                         );
 888                         count -= radix;
 889                 } else if (count > 0) {
 890                         /*
 891                          * Allocate a partial object
 892                          */
 893                         memindex = i + blst_radix_init(
 894                             ((scan) ? &scan[i] : NULL),
 895                             radix,
 896                             next_skip - 1,
 897                             count
 898                         );
 899                         count = 0;
 900                 } else {
 901                         /*
 902                          * Add terminator and break out
 903                          */
 904                         if (scan)
 905                                 scan[i].bm_bighint = (daddr_t)-1;
 906                         break;
 907                 }
 908         }
 909         if (memindex < i)
 910                 memindex = i;
 911         return(memindex);
 912 }
 913
 914 #ifdef BLIST_DEBUG
 915
 916 static void
 917 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab)
 918 {
 919         int i;
 920         int next_skip;
 921         int lastState = 0;
 922
 923         if (radix == BLIST_BMAP_RADIX) {
 924                 printf(
 925                     "%*.*s(%08llx,%lld): bitmap %08llx big=%lld\n",
 926                     tab, tab, "",
 927                     (long long)blk, (long long)radix,
 928                     (long long)scan->u.bmu_bitmap,
 929                     (long long)scan->bm_bighint
 930                 );
 931                 return;
 932         }
 933
 934         if (scan->u.bmu_avail == 0) {
 935                 printf(
 936                     "%*.*s(%08llx,%lld) ALL ALLOCATED\n",
 937                     tab, tab, "",
 938                     (long long)blk,
 939                     (long long)radix
 940                 );
 941                 return;
 942         }
 943         if (scan->u.bmu_avail == radix) {
 944                 printf(
 945                     "%*.*s(%08llx,%lld) ALL FREE\n",
 946                     tab, tab, "",
 947                     (long long)blk,
 948                     (long long)radix
 949                 );
 950                 return;
 951         }
 952
 953         printf(
 954             "%*.*s(%08llx,%lld): subtree (%lld/%lld) big=%lld {\n",
 955             tab, tab, "",
 956             (long long)blk, (long long)radix,
 957             (long long)scan->u.bmu_avail,
 958             (long long)radix,
 959             (long long)scan->bm_bighint
 960         );
 961
 962         radix /= BLIST_META_RADIX;
 963         next_skip = ((u_int)skip / BLIST_META_RADIX);
 964         tab += 4;
 965
 966         for (i = 1; i <= skip; i += next_skip) {
 967                 if (scan[i].bm_bighint == (daddr_t)-1) {
 968                         printf(
 969                             "%*.*s(%08llx,%lld): Terminator\n",
 970                             tab, tab, "",
 971                             (long long)blk, (long long)radix
 972                         );
 973                         lastState = 0;
 974                         break;
 975                 }
 976                 blst_radix_print(
 977                     &scan[i],
 978                     blk,
 979                     radix,
 980                     next_skip - 1,
 981                     tab
 982                 );
 983                 blk += radix;
 984         }
 985         tab -= 4;
 986
 987         printf(
 988             "%*.*s}\n",
 989             tab, tab, ""
 990         );
 991 }
 992
 993 #endif
 994
 995 #ifdef BLIST_DEBUG
 996
 997 int
 998 main(int ac, char **av)
 999 {
1000         int size = 1024;
1001         int i;
1002         blist_t bl;
1003
1004         for (i = 1; i < ac; ++i) {
1005                 const char *ptr = av[i];
1006                 if (*ptr != '-') {
1007                         size = strtol(ptr, NULL, 0);
1008                         continue;
1009                 }
1010                 ptr += 2;
1011                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
1012                 exit(1);
1013         }
1014         bl = blist_create(size, M_WAITOK);
1015         blist_free(bl, 0, size);
1016
1017         for (;;) {
1018                 char buf[1024];
1019                 daddr_t da = 0;
1020                 daddr_t count = 0;
1021
1022
1023                 printf("%lld/%lld/%lld> ", (long long)bl->bl_free,
1024                     (long long)size, (long long)bl->bl_radix);
1025                 fflush(stdout);
1026                 if (fgets(buf, sizeof(buf), stdin) == NULL)
1027                         break;
1028                 switch(buf[0]) {
1029                 case 'r':
1030                         if (sscanf(buf + 1, "%lld", &count) == 1) {
1031                                 blist_resize(&bl, count, 1);
1032                         } else {
1033                                 printf("?\n");
1034                         }
1035                 case 'p':
1036                         blist_print(bl);
1037                         break;
1038                 case 'a':
1039                         if (sscanf(buf + 1, "%lld", &count) == 1) {
1040                                 daddr_t blk = blist_alloc(bl, count);
1041                                 printf("    R=%08llx\n", (long long)blk);
1042                         } else {
1043                                 printf("?\n");
1044                         }
1045                         break;
1046                 case 'f':
1047                         if (sscanf(buf + 1, "%llx %lld",
1048                             (long long *)&da, (long long *)&count) == 2) {
1049                                 blist_free(bl, da, count);
1050                         } else {
1051                                 printf("?\n");
1052                         }
1053                         break;
1054                 case 'l':
1055                         if (sscanf(buf + 1, "%llx %lld",
1056                             (long long *)&da, (long long *)&count) == 2) {
1057                                 printf("    n=%d\n",
1058                                     blist_fill(bl, da, count));
1059                         } else {
1060                                 printf("?\n");
1061                         }
1062                         break;
1063                 case '?':
1064                 case 'h':
1065                         puts(
1066                             "p          -print\n"
1067                             "a %d       -allocate\n"
1068                             "f %x %d    -free\n"
1069                             "l %x %d    -fill\n"
1070                             "r %d       -resize\n"
1071                             "h/?        -help"
1072                         );
1073                         break;
1074                 default:
1075                         printf("?\n");
1076                         break;
1077                 }
1078         }
1079         return(0);
1080 }
1081
1082 void
1083 panic(const char *ctl, ...)
1084 {
1085         va_list va;
1086
1087         va_start(va, ctl);
1088         vfprintf(stderr, ctl, va);
1089         fprintf(stderr, "\n");
1090         va_end(va);
1091         exit(1);
1092 }
1093
1094 #endif
1095