sys/vfs/hammer/hammer_alist.c

   1 /*
   2  * HAMMER_ALIST.C -
   3  *
   4  * Bitmap allocator/deallocator, using a radix tree with hinting.
   5  * Unlimited-size allocations, power-of-2 only, power-of-2 aligned results
   6  * only.  This module has been separated from the generic kernel module and
   7  * written specifically for embedding in HAMMER storage structures.
   8  *
   9  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
  10  *
  11  * This code is derived from software contributed to The DragonFly Project
  12  * by Matthew Dillon <dillon@backplane.com>
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions
  16  * are met:
  17  *
  18  * 1. Redistributions of source code must retain the above copyright
  19  *    notice, this list of conditions and the following disclaimer.
  20  * 2. Redistributions in binary form must reproduce the above copyright
  21  *    notice, this list of conditions and the following disclaimer in
  22  *    the documentation and/or other materials provided with the
  23  *    distribution.
  24  * 3. Neither the name of The DragonFly Project nor the names of its
  25  *    contributors may be used to endorse or promote products derived
  26  *    from this software without specific, prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  31  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  32  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  33  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  34  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  35  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  36  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  37  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  38  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  *
  41  * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.c,v 1.1 2007/10/10 19:37:25 dillon Exp $
  42  */
  43 /*
  44  * This module implements a generic allocator through the use of a hinted
  45  * radix tree.  All allocations must be in powers of 2 and will return
  46  * similarly aligned results.  The radix tree typically recurses within
  47  * a memory buffer and then continues its recursion by chaining to other
  48  * memory buffers, creating a seemless whole capable of managing any amount
  49  * of storage.
  50  *
  51  * The radix tree is layed out recursively using a linear array.  Each meta
  52  * node is immediately followed (layed out sequentially in memory) by
  53  * HAMMER_ALIST_META_RADIX lower level nodes.  This is a recursive structure
  54  * but one that can be easily scanned through a very simple 'skip'
  55  * calculation.
  56  *
  57  * The radix tree supports an early-termination optimization which
  58  * effectively allows us to efficiently mix large and small allocations
  59  * with a single abstraction.  The address space can be partitioned
  60  * arbitrarily without adding much in the way of additional meta-storage
  61  * for the allocator.
  62  *
  63  * This code can be compiled stand-alone for debugging.
  64  */
  65
  66 #ifdef _KERNEL
  67
  68 #include <sys/param.h>
  69 #include <sys/systm.h>
  70 #include <sys/lock.h>
  71 #include <sys/kernel.h>
  72 #include <sys/malloc.h>
  73 #include <vm/vm.h>
  74 #include <vm/vm_object.h>
  75 #include <vm/vm_kern.h>
  76 #include <vm/vm_extern.h>
  77 #include <vm/vm_page.h>
  78
  79 #include "hammerfs.h"
  80
  81 #else
  82
  83 #ifndef ALIST_NO_DEBUG
  84 #define ALIST_DEBUG
  85 #endif
  86
  87 #include <sys/types.h>
  88 #include <stdio.h>
  89 #include <assert.h>
  90 #include <string.h>
  91 #include <stdlib.h>
  92 #include <stdarg.h>
  93
  94 #define kmalloc(a,b,c)  malloc(a)
  95 #define kfree(a,b)      free(a)
  96 #define kprintf         printf
  97 #define KKASSERT(exp)   assert(exp)
  98 struct malloc_type;
  99
 100 #include "hammerfs.h"
 101
 102 void panic(const char *ctl, ...);
 103
 104 #endif
 105
 106 /*
 107  * static support functions
 108  */
 109
 110 static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan,
 111                                         int32_t blk, int count);
 112 static int32_t hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan,
 113                                         int32_t blk, int32_t count,
 114                                         int32_t radix, int skip);
 115 static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t *scan,
 116                                         int32_t blk, int count);
 117 static int32_t hammer_alst_meta_alloc_rev(hammer_almeta_t *scan,
 118                                         int32_t blk, int32_t count,
 119                                         int32_t radix, int skip);
 120 static void hammer_alst_leaf_free(hammer_almeta_t *scan,
 121                                         int32_t relblk, int count);
 122 static void hammer_alst_meta_free(hammer_almeta_t *scan,
 123                                         int32_t freeBlk, int32_t count,
 124                                         int32_t radix, int skip, int32_t blk);
 125 static int32_t  hammer_alst_radix_init(hammer_almeta_t *scan,
 126                                         int32_t radix, int skip, int32_t count);
 127 #ifdef ALIST_DEBUG
 128 static void     hammer_alst_radix_print(hammer_almeta_t *scan,
 129                                         int32_t blk,
 130                                         int32_t radix, int skip, int tab);
 131 #endif
 132
 133 /*
 134  * Initialize an alist for use.  The alist will initially be marked
 135  * all-allocated so the caller must free the portion it wishes to manage.
 136  */
 137 void
 138 hammer_alist_template(hammer_alist_t bl, int blocks, int maxmeta)
 139 {
 140         int radix;
 141         int skip = 0;
 142
 143         /*
 144          * Calculate radix and skip field used for scanning.
 145          */
 146         radix = HAMMER_ALIST_BMAP_RADIX;
 147
 148         while (radix < blocks) {
 149                 radix *= HAMMER_ALIST_META_RADIX;
 150                 skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
 151         }
 152
 153         bzero(bl, sizeof(*bl));
 154
 155         bl->bl_blocks = blocks;
 156         bl->bl_radix = radix;
 157         bl->bl_skip = skip;
 158         bl->bl_rootblks = 1 +
 159             hammer_alst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
 160         KKASSERT(bl->bl_rootblks <= maxmeta);
 161
 162 #if defined(ALIST_DEBUG)
 163         kprintf(
 164                 "ALIST representing %d blocks (%d MB of swap)"
 165                 ", requiring %dK (%d bytes) of ram\n",
 166                 bl->bl_blocks,
 167                 bl->bl_blocks * 4 / 1024,
 168                 (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
 169                 (bl->bl_rootblks * sizeof(hammer_almeta_t))
 170         );
 171         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
 172 #endif
 173 }
 174
 175 void
 176 hammer_alist_init(hammer_alist_t bl, hammer_almeta_t *meta)
 177 {
 178         hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, bl->bl_blocks);
 179 }
 180
 181 #if !defined(_KERNEL) && defined(ALIST_DEBUG)
 182
 183 /*
 184  * hammer_alist_create()        (userland only)
 185  *
 186  *      create a alist capable of handling up to the specified number of
 187  *      blocks.  blocks must be greater then 0
 188  *
 189  *      The smallest alist consists of a single leaf node capable of
 190  *      managing HAMMER_ALIST_BMAP_RADIX blocks.
 191  */
 192
 193 hammer_alist_t
 194 hammer_alist_create(int32_t blocks, struct malloc_type *mtype,
 195                     hammer_almeta_t **metap)
 196 {
 197         hammer_alist_t bl;
 198         hammer_almeta_t *meta;
 199         int radix;
 200         int skip = 0;
 201         int rootblks;
 202         size_t metasize;
 203
 204         /*
 205          * Calculate radix and skip field used for scanning.
 206          */
 207         radix = HAMMER_ALIST_BMAP_RADIX;
 208
 209         while (radix < blocks) {
 210                 radix *= HAMMER_ALIST_META_RADIX;
 211                 skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
 212         }
 213
 214         rootblks = 1 + hammer_alst_radix_init(NULL, radix, skip, blocks);
 215         metasize = sizeof(struct hammer_almeta) * rootblks;
 216         bl = kmalloc(sizeof(struct hammer_alist), mtype, M_WAITOK);
 217         meta = kmalloc(metasize, mtype, M_WAITOK);
 218
 219         bzero(bl, sizeof(*bl));
 220         bzero(meta, metasize);
 221
 222         bl->bl_blocks = blocks;
 223         bl->bl_radix = radix;
 224         bl->bl_skip = skip;
 225         bl->bl_rootblks = rootblks;
 226
 227 #if defined(ALIST_DEBUG)
 228         kprintf(
 229                 "ALIST representing %d blocks (%d MB of swap)"
 230                 ", requiring %dK (%d bytes) of ram\n",
 231                 bl->bl_blocks,
 232                 bl->bl_blocks * 4 / 1024,
 233                 (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
 234                 (bl->bl_rootblks * sizeof(hammer_almeta_t))
 235         );
 236         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
 237 #endif
 238         hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, blocks);
 239
 240         *metap = meta;
 241         return(bl);
 242 }
 243
 244 void
 245 hammer_alist_destroy(hammer_alist_t bl, struct malloc_type *mtype)
 246 {
 247         kfree(bl, mtype);
 248 }
 249
 250 #endif
 251
 252 /*
 253  * hammer_alist_alloc()
 254  *
 255  *      Reserve space in the block bitmap.  Return the base of a contiguous
 256  *      region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
 257  */
 258
 259 int32_t
 260 hammer_alist_alloc(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
 261 {
 262         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
 263
 264         KKASSERT((count | (count - 1)) == (count << 1) - 1);
 265
 266         if (bl && count < bl->bl_radix) {
 267                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
 268                         blk = hammer_alst_leaf_alloc_fwd(meta, 0, count);
 269                 } else {
 270                         blk = hammer_alst_meta_alloc_fwd(
 271                                     meta, 0, count, bl->bl_radix, bl->bl_skip);
 272                 }
 273                 if (blk != HAMMER_ALIST_BLOCK_NONE)
 274                         bl->bl_free -= count;
 275         }
 276         return(blk);
 277 }
 278
 279 int32_t
 280 hammer_alist_alloc_rev(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
 281 {
 282         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
 283
 284         KKASSERT((count | (count - 1)) == (count << 1) - 1);
 285
 286         if (bl && count < bl->bl_radix) {
 287                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
 288                         blk = hammer_alst_leaf_alloc_rev(meta, 0, count);
 289                 } else {
 290                         blk = hammer_alst_meta_alloc_rev(
 291                                     meta, 0, count, bl->bl_radix, bl->bl_skip);
 292                 }
 293                 if (blk != HAMMER_ALIST_BLOCK_NONE)
 294                         bl->bl_free -= count;
 295         }
 296         return(blk);
 297 }
 298
 299 #if 0
 300
 301 /*
 302  * hammer_alist_alloc_from()
 303  *
 304  *      An extended version of hammer_alist_alloc() which locates free space
 305  *      starting at the specified block either forwards or backwards.
 306  *      HAMMER_ALIST_BLOCK_NONE is returned if space could not be allocated.
 307  *
 308  *      Note: when allocating from a particular point forwards space is never
 309  *      allocated behind that start point, and similarly when going backwards.
 310  */
 311 int32_t
 312 hammer_alist_alloc_from(hammer_alist_t bl, hammer_almeta_t *meta,
 313                         int32_t count, int32_t start, int flags)
 314
 315 {
 316 }
 317
 318 #endif
 319
 320 /*
 321  * alist_free()
 322  *
 323  *      Free up space in the block bitmap.  Return the base of a contiguous
 324  *      region.  Panic if an inconsistancy is found.
 325  *
 326  *      Unlike allocations, there are no alignment requirements for blkno or
 327  *      count when freeing blocks.
 328  */
 329
 330 void
 331 hammer_alist_free(hammer_alist_t bl, hammer_almeta_t *meta,
 332                   int32_t blkno, int32_t count)
 333 {
 334         if (bl) {
 335                 KKASSERT(blkno + count <= bl->bl_blocks);
 336                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX)
 337                         hammer_alst_leaf_free(meta, blkno, count);
 338                 else
 339                         hammer_alst_meta_free(meta, blkno, count,
 340                                               bl->bl_radix, bl->bl_skip, 0);
 341                 bl->bl_free += count;
 342         }
 343 }
 344
 345 #ifdef ALIST_DEBUG
 346
 347 /*
 348  * alist_print()    - dump radix tree
 349  */
 350
 351 void
 352 hammer_alist_print(hammer_alist_t bl, hammer_almeta_t *meta)
 353 {
 354         kprintf("ALIST {\n");
 355         hammer_alst_radix_print(meta, 0, bl->bl_radix, bl->bl_skip, 4);
 356         kprintf("}\n");
 357 }
 358
 359 #endif
 360
 361 /************************************************************************
 362  *                        ALLOCATION SUPPORT FUNCTIONS                  *
 363  ************************************************************************
 364  *
 365  *      These support functions do all the actual work.  They may seem
 366  *      rather longish, but that's because I've commented them up.  The
 367  *      actual code is straight forward.
 368  *
 369  */
 370
 371 /*
 372  * hammer_alist_leaf_alloc_fwd()
 373  *
 374  *      Allocate at a leaf in the radix tree (a bitmap).
 375  *
 376  *      This is the core of the allocator and is optimized for the 1 block
 377  *      and the HAMMER_ALIST_BMAP_RADIX block allocation cases.  Other cases
 378  *      are somewhat slower.  The 1 block allocation case is log2 and extremely
 379  *      quick.
 380  */
 381
 382 static int32_t
 383 hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int count)
 384 {
 385         u_int32_t orig = scan->bm_bitmap;
 386
 387         /*
 388          * Optimize bitmap all-allocated case.  Also, count = 1
 389          * case assumes at least 1 bit is free in the bitmap, so
 390          * we have to take care of this case here.
 391          */
 392         if (orig == 0) {
 393                 scan->bm_bighint = 0;
 394                 return(HAMMER_ALIST_BLOCK_NONE);
 395         }
 396
 397         /*
 398          * Optimized code to allocate one bit out of the bitmap
 399          */
 400         if (count == 1) {
 401                 u_int32_t mask;
 402                 int j = HAMMER_ALIST_BMAP_RADIX/2;
 403                 int r = 0;
 404
 405                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
 406
 407                 while (j) {
 408                         if ((orig & mask) == 0) {
 409                             r += j;
 410                             orig >>= j;
 411                         }
 412                         j >>= 1;
 413                         mask >>= j;
 414                 }
 415                 scan->bm_bitmap &= ~(1 << r);
 416                 return(blk + r);
 417         }
 418
 419         /*
 420          * non-optimized code to allocate N bits out of the bitmap.
 421          * The more bits, the faster the code runs.  It will run
 422          * the slowest allocating 2 bits, but since there aren't any
 423          * memory ops in the core loop (or shouldn't be, anyway),
 424          * you probably won't notice the difference.
 425          *
 426          * Similar to the blist case, the alist code also requires
 427          * allocations to be power-of-2 sized and aligned to the
 428          * size of the allocation, which simplifies the algorithm.
 429          */
 430         {
 431                 int j;
 432                 int n = HAMMER_ALIST_BMAP_RADIX - count;
 433                 u_int32_t mask;
 434
 435                 mask = (u_int32_t)-1 >> n;
 436
 437                 for (j = 0; j <= n; j += count) {
 438                         if ((orig & mask) == mask) {
 439                                 scan->bm_bitmap &= ~mask;
 440                                 return(blk + j);
 441                         }
 442                         mask = mask << count;
 443                 }
 444         }
 445
 446         /*
 447          * We couldn't allocate count in this subtree, update bighint.
 448          */
 449         scan->bm_bighint = count - 1;
 450         return(HAMMER_ALIST_BLOCK_NONE);
 451 }
 452
 453 /*
 454  * This version allocates blocks in the reverse direction.
 455  */
 456 static int32_t
 457 hammer_alst_leaf_alloc_rev(hammer_almeta_t *scan, int32_t blk, int count)
 458 {
 459         u_int32_t orig = scan->bm_bitmap;
 460
 461         /*
 462          * Optimize bitmap all-allocated case.  Also, count = 1
 463          * case assumes at least 1 bit is free in the bitmap, so
 464          * we have to take care of this case here.
 465          */
 466         if (orig == 0) {
 467                 scan->bm_bighint = 0;
 468                 return(HAMMER_ALIST_BLOCK_NONE);
 469         }
 470
 471         /*
 472          * Optimized code to allocate one bit out of the bitmap
 473          */
 474         if (count == 1) {
 475                 u_int32_t mask;
 476                 int j = HAMMER_ALIST_BMAP_RADIX/2;
 477                 int r = HAMMER_ALIST_BMAP_RADIX - 1;
 478
 479                 mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
 480
 481                 while (j) {
 482                         if ((orig & mask) == 0) {
 483                             r -= j;
 484                             orig <<= j;
 485                         }
 486                         j >>= 1;
 487                         mask <<= j;
 488                 }
 489                 scan->bm_bitmap &= ~(1 << r);
 490                 return(blk + r);
 491         }
 492
 493         /*
 494          * non-optimized code to allocate N bits out of the bitmap.
 495          * The more bits, the faster the code runs.  It will run
 496          * the slowest allocating 2 bits, but since there aren't any
 497          * memory ops in the core loop (or shouldn't be, anyway),
 498          * you probably won't notice the difference.
 499          *
 500          * Similar to the blist case, the alist code also requires
 501          * allocations to be power-of-2 sized and aligned to the
 502          * size of the allocation, which simplifies the algorithm.
 503          *
 504          * initial mask if count == 2:  1100....0000
 505          */
 506         {
 507                 int j;
 508                 int n = HAMMER_ALIST_BMAP_RADIX - count;
 509                 u_int32_t mask;
 510
 511                 mask = ((u_int32_t)-1 >> n) << n;
 512
 513                 for (j = n; j >= 0; j -= count) {
 514                         if ((orig & mask) == mask) {
 515                                 scan->bm_bitmap &= ~mask;
 516                                 return(blk + j);
 517                         }
 518                         mask = mask >> count;
 519                 }
 520         }
 521
 522         /*
 523          * We couldn't allocate count in this subtree, update bighint.
 524          */
 525         scan->bm_bighint = count - 1;
 526         return(HAMMER_ALIST_BLOCK_NONE);
 527 }
 528
 529 /*
 530  * hammer_alist_meta_alloc_fwd()
 531  *
 532  *      Allocate at a meta in the radix tree.
 533  *
 534  *      Attempt to allocate at a meta node.  If we can't, we update
 535  *      bighint and return a failure.  Updating bighint optimize future
 536  *      calls that hit this node.  We have to check for our collapse cases
 537  *      and we have a few optimizations strewn in as well.
 538  */
 539 static int32_t
 540 hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int32_t count,
 541                            int32_t radix, int skip
 542 ) {
 543         int i;
 544         u_int32_t mask;
 545         u_int32_t pmask;
 546         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
 547
 548         /*
 549          * ALL-ALLOCATED special case
 550          */
 551         if (scan->bm_bitmap == 0)  {
 552                 scan->bm_bighint = 0;
 553                 return(HAMMER_ALIST_BLOCK_NONE);
 554         }
 555
 556         radix /= HAMMER_ALIST_META_RADIX;
 557
 558         /*
 559          * Radix now represents each bitmap entry for this meta node.  If
 560          * the number of blocks being allocated can be fully represented,
 561          * we allocate directly out of this meta node.
 562          *
 563          * Meta node bitmaps use 2 bits per block.
 564          *
 565          *      00      ALL-ALLOCATED
 566          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
 567          *      10      (RESERVED)
 568          *      11      ALL-FREE
 569          */
 570         if (count >= radix) {
 571                 int n = count / radix * 2;      /* number of bits */
 572                 int j;
 573
 574                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
 575                 for (j = 0; j < HAMMER_ALIST_META_RADIX; j += n / 2) {
 576                         if ((scan->bm_bitmap & mask) == mask) {
 577                                 scan->bm_bitmap &= ~mask;
 578                                 return(blk + j * radix);
 579                         }
 580                         mask <<= n;
 581                 }
 582                 if (scan->bm_bighint >= count)
 583                         scan->bm_bighint = count >> 1;
 584                 return(HAMMER_ALIST_BLOCK_NONE);
 585         }
 586
 587         /*
 588          * If not we have to recurse.
 589          */
 590         mask = 0x00000003;
 591         pmask = 0x00000001;
 592         for (i = 1; i <= skip; i += next_skip) {
 593                 if (scan[i].bm_bighint == (int32_t)-1) {
 594                         /*
 595                          * Terminator
 596                          */
 597                         break;
 598                 }
 599                 if ((scan->bm_bitmap & mask) == mask) {
 600                         scan[i].bm_bitmap = (u_int32_t)-1;
 601                         scan[i].bm_bighint = radix;
 602                 }
 603
 604                 if (count <= scan[i].bm_bighint) {
 605                         /*
 606                          * count fits in object
 607                          */
 608                         int32_t r;
 609                         if (next_skip == 1) {
 610                                 r = hammer_alst_leaf_alloc_fwd(
 611                                         &scan[i], blk, count);
 612                         } else {
 613                                 r = hammer_alst_meta_alloc_fwd(
 614                                         &scan[i], blk, count,
 615                                         radix, next_skip - 1);
 616                         }
 617                         if (r != HAMMER_ALIST_BLOCK_NONE) {
 618                                 if (scan[i].bm_bitmap == 0) {
 619                                         scan->bm_bitmap &= ~mask;
 620                                 } else {
 621                                         scan->bm_bitmap &= ~mask;
 622                                         scan->bm_bitmap |= pmask;
 623                                 }
 624                                 return(r);
 625                         }
 626                 } else if (count > radix) {
 627                         /*
 628                          * count does not fit in object even if it were
 629                          * completely free.
 630                          */
 631                         break;
 632                 }
 633                 blk += radix;
 634                 mask <<= 2;
 635                 pmask <<= 2;
 636         }
 637
 638         /*
 639          * We couldn't allocate count in this subtree, update bighint.
 640          */
 641         if (scan->bm_bighint >= count)
 642                 scan->bm_bighint = count >> 1;
 643         return(HAMMER_ALIST_BLOCK_NONE);
 644 }
 645
 646 /*
 647  * This version allocates blocks in the reverse direction.
 648  */
 649 static int32_t
 650 hammer_alst_meta_alloc_rev(hammer_almeta_t *scan, int32_t blk, int32_t count,
 651                            int32_t radix, int skip
 652 ) {
 653         int i;
 654         int j;
 655         u_int32_t mask;
 656         u_int32_t pmask;
 657         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
 658
 659         /*
 660          * ALL-ALLOCATED special case
 661          */
 662         if (scan->bm_bitmap == 0)  {
 663                 scan->bm_bighint = 0;
 664                 return(HAMMER_ALIST_BLOCK_NONE);
 665         }
 666
 667         radix /= HAMMER_ALIST_META_RADIX;
 668
 669         /*
 670          * Radix now represents each bitmap entry for this meta node.  If
 671          * the number of blocks being allocated can be fully represented,
 672          * we allocate directly out of this meta node.
 673          *
 674          * Meta node bitmaps use 2 bits per block.
 675          *
 676          *      00      ALL-ALLOCATED
 677          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
 678          *      10      (RESERVED)
 679          *      11      ALL-FREE
 680          */
 681         if (count >= radix) {
 682                 int n = count / radix * 2;      /* number of bits */
 683                 int j;
 684
 685                 /*
 686                  * Initial mask if e.g. n == 2:  1100....0000
 687                  */
 688                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
 689                         (HAMMER_ALIST_BMAP_RADIX - n);
 690                 for (j = HAMMER_ALIST_META_RADIX - n / 2; j >= 0; j -= n / 2) {
 691                         if ((scan->bm_bitmap & mask) == mask) {
 692                                 scan->bm_bitmap &= ~mask;
 693                                 return(blk + j * radix);
 694                         }
 695                         mask >>= n;
 696                 }
 697                 if (scan->bm_bighint >= count)
 698                         scan->bm_bighint = count >> 1;
 699                 return(HAMMER_ALIST_BLOCK_NONE);
 700         }
 701
 702         /*
 703          * If not we have to recurse.  Since we are going in the reverse
 704          * direction we need an extra loop to determine if there is a
 705          * terminator, then run backwards.
 706          *
 707          * This is a little weird but we do not want to overflow the
 708          * mask/pmask in the loop.
 709          */
 710         j = 0;
 711         for (i = 1; i <= skip; i += next_skip) {
 712                 if (scan[i].bm_bighint == (int32_t)-1)
 713                         break;
 714                 blk += radix;
 715                 j += 2;
 716         }
 717         blk -= radix;
 718         j -= 2;
 719         mask = 0x00000003 << j;
 720         pmask = 0x00000001 << j;
 721         i -= next_skip;
 722
 723         while (i >= 1) {
 724                 /*
 725                  * Initialize the bitmap in the child if allocating from
 726                  * the all-free case.
 727                  */
 728                 if ((scan->bm_bitmap & mask) == mask) {
 729                         scan[i].bm_bitmap = (u_int32_t)-1;
 730                         scan[i].bm_bighint = radix;
 731                 }
 732
 733                 /*
 734                  * Handle various count cases.  Bighint may be too large but
 735                  * is never too small.
 736                  */
 737                 if (count <= scan[i].bm_bighint) {
 738                         /*
 739                          * count fits in object
 740                          */
 741                         int32_t r;
 742                         if (next_skip == 1) {
 743                                 r = hammer_alst_leaf_alloc_rev(
 744                                         &scan[i], blk, count);
 745                         } else {
 746                                 r = hammer_alst_meta_alloc_rev(
 747                                         &scan[i], blk, count,
 748                                         radix, next_skip - 1);
 749                         }
 750                         if (r != HAMMER_ALIST_BLOCK_NONE) {
 751                                 if (scan[i].bm_bitmap == 0) {
 752                                         scan->bm_bitmap &= ~mask;
 753                                 } else {
 754                                         scan->bm_bitmap &= ~mask;
 755                                         scan->bm_bitmap |= pmask;
 756                                 }
 757                                 return(r);
 758                         }
 759                 } else if (count > radix) {
 760                         /*
 761                          * count does not fit in object even if it were
 762                          * completely free.
 763                          */
 764                         break;
 765                 }
 766                 blk -= radix;
 767                 mask >>= 2;
 768                 pmask >>= 2;
 769                 i -= next_skip;
 770         }
 771
 772         /*
 773          * We couldn't allocate count in this subtree, update bighint.
 774          */
 775         if (scan->bm_bighint >= count)
 776                 scan->bm_bighint = count >> 1;
 777         return(HAMMER_ALIST_BLOCK_NONE);
 778 }
 779
 780 /*
 781  * BLST_LEAF_FREE()
 782  *
 783  *      Free allocated blocks from leaf bitmap.  The allocation code is
 784  *      restricted to powers of 2, the freeing code is not.
 785  */
 786 static void
 787 hammer_alst_leaf_free(
 788         hammer_almeta_t *scan,
 789         int32_t blk,
 790         int count
 791 ) {
 792         /*
 793          * free some data in this bitmap
 794          *
 795          * e.g.
 796          *      0000111111111110000
 797          *          \_________/\__/
 798          *              v        n
 799          */
 800         int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
 801         u_int32_t mask;
 802
 803         mask = ((u_int32_t)-1 << n) &
 804             ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
 805
 806         if (scan->bm_bitmap & mask)
 807                 panic("hammer_alst_radix_free: freeing free block");
 808         scan->bm_bitmap |= mask;
 809
 810         /*
 811          * We could probably do a better job here.  We are required to make
 812          * bighint at least as large as the biggest contiguous block of
 813          * data.  If we just shoehorn it, a little extra overhead will
 814          * be incured on the next allocation (but only that one typically).
 815          */
 816         scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
 817 }
 818
 819 /*
 820  * BLST_META_FREE()
 821  *
 822  *      Free allocated blocks from radix tree meta info.
 823  *
 824  *      This support routine frees a range of blocks from the bitmap.
 825  *      The range must be entirely enclosed by this radix node.  If a
 826  *      meta node, we break the range down recursively to free blocks
 827  *      in subnodes (which means that this code can free an arbitrary
 828  *      range whereas the allocation code cannot allocate an arbitrary
 829  *      range).
 830  */
 831
 832 static void
 833 hammer_alst_meta_free(
 834         hammer_almeta_t *scan,
 835         int32_t freeBlk,
 836         int32_t count,
 837         int32_t radix,
 838         int skip,
 839         int32_t blk
 840 ) {
 841         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
 842         u_int32_t mask;
 843         u_int32_t pmask;
 844         int i;
 845
 846         /*
 847          * Break the free down into its components.  Because it is so easy
 848          * to implement, frees are not limited to power-of-2 sizes.
 849          *
 850          * Each block in a meta-node bitmap takes two bits.
 851          */
 852         radix /= HAMMER_ALIST_META_RADIX;
 853
 854         i = (freeBlk - blk) / radix;
 855         blk += i * radix;
 856         mask = 0x00000003 << (i * 2);
 857         pmask = 0x00000001 << (i * 2);
 858
 859         i = i * next_skip + 1;
 860
 861         while (i <= skip && blk < freeBlk + count) {
 862                 int32_t v;
 863
 864                 v = blk + radix - freeBlk;
 865                 if (v > count)
 866                         v = count;
 867
 868                 if (scan->bm_bighint == (int32_t)-1)
 869                         panic("hammer_alst_meta_free: freeing unexpected range");
 870
 871                 if (freeBlk == blk && count >= radix) {
 872                         /*
 873                          * All-free case, no need to update sub-tree
 874                          */
 875                         scan->bm_bitmap |= mask;
 876                         scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
 877                         /*XXX*/
 878                 } else {
 879                         /*
 880                          * Recursion case
 881                          */
 882                         if (next_skip == 1)
 883                                 hammer_alst_leaf_free(&scan[i], freeBlk, v);
 884                         else
 885                                 hammer_alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
 886                         if (scan[i].bm_bitmap == (u_int32_t)-1)
 887                                 scan->bm_bitmap |= mask;
 888                         else
 889                                 scan->bm_bitmap |= pmask;
 890                         if (scan->bm_bighint < scan[i].bm_bighint)
 891                             scan->bm_bighint = scan[i].bm_bighint;
 892                 }
 893                 mask <<= 2;
 894                 pmask <<= 2;
 895                 count -= v;
 896                 freeBlk += v;
 897                 blk += radix;
 898                 i += next_skip;
 899         }
 900 }
 901
 902 /*
 903  * BLST_RADIX_INIT()
 904  *
 905  *      Initialize our meta structures and bitmaps and calculate the exact
 906  *      amount of space required to manage 'count' blocks - this space may
 907  *      be considerably less then the calculated radix due to the large
 908  *      RADIX values we use.
 909  */
 910
 911 static int32_t
 912 hammer_alst_radix_init(hammer_almeta_t *scan, int32_t radix,
 913                        int skip, int32_t count)
 914 {
 915         int i;
 916         int next_skip;
 917         int32_t memindex = 0;
 918         u_int32_t mask;
 919         u_int32_t pmask;
 920
 921         /*
 922          * Leaf node
 923          */
 924         if (radix == HAMMER_ALIST_BMAP_RADIX) {
 925                 if (scan) {
 926                         scan->bm_bighint = 0;
 927                         scan->bm_bitmap = 0;
 928                 }
 929                 return(memindex);
 930         }
 931
 932         /*
 933          * Meta node.  If allocating the entire object we can special
 934          * case it.  However, we need to figure out how much memory
 935          * is required to manage 'count' blocks, so we continue on anyway.
 936          */
 937
 938         if (scan) {
 939                 scan->bm_bighint = 0;
 940                 scan->bm_bitmap = 0;
 941         }
 942
 943         radix /= HAMMER_ALIST_META_RADIX;
 944         next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
 945         mask = 0x00000003;
 946         pmask = 0x00000001;
 947
 948         for (i = 1; i <= skip; i += next_skip) {
 949                 if (count >= radix) {
 950                         /*
 951                          * Allocate the entire object
 952                          */
 953                         memindex = i + hammer_alst_radix_init(
 954                             ((scan) ? &scan[i] : NULL),
 955                             radix,
 956                             next_skip - 1,
 957                             radix
 958                         );
 959                         count -= radix;
 960                         /* already marked as wholely allocated */
 961                 } else if (count > 0) {
 962                         /*
 963                          * Allocate a partial object
 964                          */
 965                         memindex = i + hammer_alst_radix_init(
 966                             ((scan) ? &scan[i] : NULL),
 967                             radix,
 968                             next_skip - 1,
 969                             count
 970                         );
 971                         count = 0;
 972
 973                         /*
 974                          * Mark as partially allocated
 975                          */
 976                         if (scan)
 977                                 scan->bm_bitmap |= pmask;
 978                 } else {
 979                         /*
 980                          * Add terminator and break out
 981                          */
 982                         if (scan)
 983                                 scan[i].bm_bighint = (int32_t)-1;
 984                         /* already marked as wholely allocated */
 985                         break;
 986                 }
 987                 mask <<= 2;
 988                 pmask <<= 2;
 989         }
 990         if (memindex < i)
 991                 memindex = i;
 992         return(memindex);
 993 }
 994
 995 #ifdef ALIST_DEBUG
 996
 997 static void
 998 hammer_alst_radix_print(hammer_almeta_t *scan, int32_t blk,
 999                         int32_t radix, int skip, int tab)
1000 {
1001         int i;
1002         int next_skip;
1003         int lastState = 0;
1004         u_int32_t mask;
1005
1006         if (radix == HAMMER_ALIST_BMAP_RADIX) {
1007                 kprintf(
1008                     "%*.*s(%04x,%d): bitmap %08x big=%d\n",
1009                     tab, tab, "",
1010                     blk, radix,
1011                     scan->bm_bitmap,
1012                     scan->bm_bighint
1013                 );
1014                 return;
1015         }
1016
1017         if (scan->bm_bitmap == 0) {
1018                 kprintf(
1019                     "%*.*s(%04x,%d) ALL ALLOCATED\n",
1020                     tab, tab, "",
1021                     blk,
1022                     radix
1023                 );
1024                 return;
1025         }
1026         if (scan->bm_bitmap == (u_int32_t)-1) {
1027                 kprintf(
1028                     "%*.*s(%04x,%d) ALL FREE\n",
1029                     tab, tab, "",
1030                     blk,
1031                     radix
1032                 );
1033                 return;
1034         }
1035
1036         kprintf(
1037             "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n",
1038             tab, tab, "",
1039             blk, radix,
1040             radix,
1041             scan->bm_bitmap,
1042             scan->bm_bighint
1043         );
1044
1045         radix /= HAMMER_ALIST_META_RADIX;
1046         next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
1047         tab += 4;
1048         mask = 0x00000003;
1049
1050         for (i = 1; i <= skip; i += next_skip) {
1051                 if (scan[i].bm_bighint == (int32_t)-1) {
1052                         kprintf(
1053                             "%*.*s(%04x,%d): Terminator\n",
1054                             tab, tab, "",
1055                             blk, radix
1056                         );
1057                         lastState = 0;
1058                         break;
1059                 }
1060                 if ((scan->bm_bitmap & mask) == mask) {
1061                         kprintf(
1062                             "%*.*s(%04x,%d): ALL FREE\n",
1063                             tab, tab, "",
1064                             blk, radix
1065                         );
1066                 } else if ((scan->bm_bitmap & mask) == 0) {
1067                         kprintf(
1068                             "%*.*s(%04x,%d): ALL ALLOCATED\n",
1069                             tab, tab, "",
1070                             blk, radix
1071                         );
1072                 } else {
1073                         hammer_alst_radix_print(
1074                             &scan[i],
1075                             blk,
1076                             radix,
1077                             next_skip - 1,
1078                             tab
1079                         );
1080                 }
1081                 blk += radix;
1082                 mask <<= 2;
1083         }
1084         tab -= 4;
1085
1086         kprintf(
1087             "%*.*s}\n",
1088             tab, tab, ""
1089         );
1090 }
1091
1092 #endif
1093
1094 #ifdef ALIST_DEBUG
1095
1096 int
1097 main(int ac, char **av)
1098 {
1099         int size = 1024;
1100         int i;
1101         hammer_alist_t bl;
1102         hammer_almeta_t *meta = NULL;
1103
1104         for (i = 1; i < ac; ++i) {
1105                 const char *ptr = av[i];
1106                 if (*ptr != '-') {
1107                         size = strtol(ptr, NULL, 0);
1108                         continue;
1109                 }
1110                 ptr += 2;
1111                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
1112                 exit(1);
1113         }
1114         bl = hammer_alist_create(size, NULL, &meta);
1115         hammer_alist_free(bl, meta, 0, size);
1116
1117         for (;;) {
1118                 char buf[1024];
1119                 int32_t da = 0;
1120                 int32_t count = 0;
1121                 int32_t blk;
1122
1123                 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
1124                 fflush(stdout);
1125                 if (fgets(buf, sizeof(buf), stdin) == NULL)
1126                         break;
1127                 switch(buf[0]) {
1128                 case 'p':
1129                         hammer_alist_print(bl, meta);
1130                         break;
1131                 case 'a':
1132                         if (sscanf(buf + 1, "%d", &count) == 1) {
1133                                 blk = hammer_alist_alloc(bl, meta, count);
1134                                 kprintf("    R=%04x\n", blk);
1135                         } else {
1136                                 kprintf("?\n");
1137                         }
1138                         break;
1139                 case 'r':
1140                         if (sscanf(buf + 1, "%d", &count) == 1) {
1141                                 blk = hammer_alist_alloc_rev(bl, meta, count);
1142                                 kprintf("    R=%04x\n", blk);
1143                         } else {
1144                                 kprintf("?\n");
1145                         }
1146                         break;
1147                 case 'f':
1148                         if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
1149                                 hammer_alist_free(bl, meta, da, count);
1150                         } else {
1151                                 kprintf("?\n");
1152                         }
1153                         break;
1154                 case '?':
1155                 case 'h':
1156                         puts(
1157                             "p          -print\n"
1158                             "a %d       -allocate\n"
1159                             "r %d       -allocate reverse\n"
1160                             "f %x %d    -free\n"
1161                             "h/?        -help"
1162                         );
1163                         break;
1164                 default:
1165                         kprintf("?\n");
1166                         break;
1167                 }
1168         }
1169         return(0);
1170 }
1171
1172 void
1173 panic(const char *ctl, ...)
1174 {
1175         __va_list va;
1176
1177         __va_start(va, ctl);
1178         vfprintf(stderr, ctl, va);
1179         fprintf(stderr, "\n");
1180         __va_end(va);
1181         exit(1);
1182 }
1183
1184 #endif
1185