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