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