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.11 2008/01/24 02:14:45 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  * The radix tree supports allocator layering. By supplying a base_radix > 1
  64  * the allocator will issue callbacks to recurse into lower layers once
  65  * higher layers have been exhausted.
  66  *
  67  * ALLOCATIONS IN MULTIPLES OF base_radix WILL BE ENTIRELY RETAINED IN THE
  68  * HIGHER LEVEL ALLOCATOR AND NEVER RECURSE.  This means the init function
  69  * will never be called and the A-list will consider the underlying zone
  70  * as being uninitialized.  If you then do a partial free, the A-list will
  71  * call the init function before freeing.  Most users of this API, including
  72  * HAMMER, only allocate and free whole zones, or only allocate and free
  73  * partial zones, and never mix their metaphors.
  74  *
  75  * This code can be compiled stand-alone for debugging.
  76  */
  77
  78 #ifdef _KERNEL
  79
  80 #include <sys/param.h>
  81 #include <sys/systm.h>
  82 #include <sys/lock.h>
  83 #include <sys/kernel.h>
  84 #include <sys/malloc.h>
  85 #include <vm/vm.h>
  86 #include <vm/vm_object.h>
  87 #include <vm/vm_kern.h>
  88 #include <vm/vm_extern.h>
  89 #include <vm/vm_page.h>
  90
  91 #include "hammer_alist.h"
  92 #include "hammer_disk.h"
  93
  94 #else
  95
  96 #ifndef ALIST_NO_DEBUG
  97 #define ALIST_DEBUG
  98 #endif
  99
 100 #include <sys/types.h>
 101 #include <sys/errno.h>
 102 #include <stdio.h>
 103 #include <assert.h>
 104 #include <string.h>
 105 #include <stdlib.h>
 106 #include <stdarg.h>
 107
 108 #define kmalloc(a,b,c)  malloc(a)
 109 #define kfree(a,b)      free(a)
 110 #define kprintf         printf
 111 #define KKASSERT(exp)   assert(exp)
 112 struct malloc_type;
 113
 114 #include "hammer_alist.h"
 115
 116 void panic(const char *ctl, ...);
 117
 118 #endif
 119
 120 /*
 121  * static support functions
 122  */
 123 static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan,
 124                                         int32_t blk, int count, int32_t atblk);
 125 static int32_t hammer_alst_meta_alloc_fwd(hammer_alist_t live,
 126                                         hammer_almeta_t scan,
 127                                         int32_t blk, int32_t count,
 128                                         int32_t radix, int skip, int32_t atblk);
 129 static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t scan,
 130                                         int32_t blk, int count, int32_t atblk);
 131 static int32_t hammer_alst_meta_alloc_rev(hammer_alist_t live,
 132                                         hammer_almeta_t scan,
 133                                         int32_t blk, int32_t count,
 134                                         int32_t radix, int skip, int32_t atblk);
 135 static int32_t hammer_alst_find(hammer_alist_t live, hammer_almeta_t scan,
 136                                         int32_t blk, int32_t radix,
 137                                         int32_t skip, int32_t atblk, int flags);
 138 static void hammer_alst_leaf_free(hammer_almeta_t scan, int32_t relblk,
 139                                         int count);
 140 static void hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
 141                                         int32_t freeBlk, int32_t count,
 142                                         int32_t radix, int skip, int32_t blk);
 143 static int32_t  hammer_alst_radix_init(hammer_almeta_t scan,
 144                                         int32_t radix, int skip, int32_t count);
 145 static void     hammer_alst_radix_recover(hammer_alist_recover_t info,
 146                                         hammer_almeta_t scan, int32_t blk,
 147                                         int32_t radix, int skip, int32_t count,
 148                                         int32_t a_beg, int32_t a_end);
 149 #ifdef ALIST_DEBUG
 150 static void     hammer_alst_radix_print(hammer_alist_t live,
 151                                         hammer_almeta_t scan, int32_t blk,
 152                                         int32_t radix, int skip, int tab);
 153 #endif
 154
 155 /*
 156  * Initialize an a-list config structure for use.  The config structure
 157  * describes the basic structure of an a-list's topology and may be
 158  * shared by any number of a-lists which have the same topology.
 159  *
 160  * blocks is the total number of blocks, that is the number of blocks
 161  * handled at this layer multiplied by the base radix.
 162  *
 163  * When base_radix != 1 the A-list has only meta elements and does not have
 164  * any leaves, in order to be able to track partial allocations.
 165  */
 166 void
 167 hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
 168                       int32_t base_radix, int32_t maxmeta, int inverted)
 169 {
 170         int radix;
 171         int skip;
 172
 173         /*
 174          * Calculate radix and skip field used for scanning.  The leaf nodes
 175          * in our tree are either BMAP or META nodes depending on whether
 176          * we chain to a lower level allocation layer or not.
 177          */
 178         if (base_radix == 1)
 179                 radix = HAMMER_ALIST_BMAP_RADIX;
 180         else
 181                 radix = HAMMER_ALIST_META_RADIX;
 182         skip = 1;
 183
 184         while (radix < blocks / base_radix) {
 185                 radix *= HAMMER_ALIST_META_RADIX;
 186                 skip = skip * HAMMER_ALIST_META_RADIX + 1;
 187         }
 188
 189         /*
 190          * Increase the radix based on the number of blocks a lower level
 191          * allocator is able to handle at the 'base' of our allocator.
 192          * If base_radix != 1 the caller will have to initialize the callback
 193          * fields to implement the lower level allocator.
 194          */
 195         KKASSERT((int64_t)radix * (int64_t)base_radix < 0x80000000LL);
 196         radix *= base_radix;
 197
 198         bzero(bl, sizeof(*bl));
 199
 200         bl->bl_blocks = blocks;
 201         bl->bl_base_radix = base_radix;
 202         bl->bl_radix = radix;
 203         bl->bl_skip = skip;
 204         bl->bl_rootblks = hammer_alst_radix_init(NULL, bl->bl_radix,
 205                                                  bl->bl_skip, blocks);
 206         bl->bl_inverted = inverted;
 207         ++bl->bl_rootblks;      /* one more for freeblks header */
 208         if (base_radix == 1)
 209                 bl->bl_terminal = 1;
 210         KKASSERT(maxmeta == 0 || bl->bl_rootblks <= maxmeta);
 211
 212 #if defined(ALIST_DEBUG)
 213         kprintf(
 214                 "PRIMARY ALIST LAYER manages %d blocks"
 215                 ", requiring %dK (%d bytes) of ram\n",
 216                 bl->bl_blocks / bl->bl_base_radix,
 217                 (bl->bl_rootblks * sizeof(struct hammer_almeta) + 1023) / 1024,
 218                 (bl->bl_rootblks * sizeof(struct hammer_almeta))
 219         );
 220         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
 221 #endif
 222 }
 223
 224 /*
 225  * Initialize a new A-list
 226  */
 227 void
 228 hammer_alist_init(hammer_alist_t live, int32_t start, int32_t count,
 229                   enum hammer_alloc_state state)
 230 {
 231         hammer_alist_config_t bl = live->config;
 232
 233         /*
 234          * Note: base_freeblks is a count, not a block number limit.
 235          */
 236         live->meta->bm_alist_freeblks = 0;
 237         live->meta->bm_alist_base_freeblks = count;
 238         hammer_alst_radix_init(live->meta + 1, bl->bl_radix,
 239                                bl->bl_skip, bl->bl_blocks);
 240         if (count && state == HAMMER_ASTATE_FREE)
 241                 hammer_alist_free(live, start, count);
 242 }
 243
 244 #if !defined(_KERNEL) && defined(ALIST_DEBUG)
 245
 246 /*
 247  * hammer_alist_create()        (userland only)
 248  *
 249  *      create a alist capable of handling up to the specified number of
 250  *      blocks.  blocks must be greater then 0
 251  *
 252  *      The smallest alist consists of a single leaf node capable of
 253  *      managing HAMMER_ALIST_BMAP_RADIX blocks, or (if base_radix != 1)
 254  *      a single meta node capable of managing HAMMER_ALIST_META_RADIX
 255  *      blocks which recurses into other storage layers for a total
 256  *      handling capability of (HAMMER_ALIST_META_RADIX * base_radix) blocks.
 257  *
 258  *      Larger a-list's increase their capability exponentially by
 259  *      HAMMER_ALIST_META_RADIX.
 260  *
 261  *      The block count is the total number of blocks inclusive of any
 262  *      layering.  blocks can be less then base_radix and will result in
 263  *      a radix tree with a single leaf node which then chains down.
 264  */
 265
 266 hammer_alist_t
 267 hammer_alist_create(int32_t blocks, int32_t base_radix,
 268                     struct malloc_type *mtype, enum hammer_alloc_state state)
 269 {
 270         hammer_alist_t live;
 271         hammer_alist_config_t bl;
 272         size_t metasize;
 273
 274         live = kmalloc(sizeof(*live), mtype, M_WAITOK);
 275         live->config = bl = kmalloc(sizeof(*bl), mtype, M_WAITOK);
 276         hammer_alist_template(bl, blocks, base_radix, 0, 0);
 277
 278         metasize = sizeof(*live->meta) * bl->bl_rootblks;
 279         live->meta = kmalloc(metasize, mtype, M_WAITOK);
 280         bzero(live->meta, metasize);
 281
 282 #if defined(ALIST_DEBUG)
 283         kprintf(
 284                 "ALIST representing %d blocks (%d MB of swap)"
 285                 ", requiring %dK (%d bytes) of ram\n",
 286                 bl->bl_blocks,
 287                 bl->bl_blocks * 4 / 1024,
 288                 (bl->bl_rootblks * sizeof(*live->meta) + 1023) / 1024,
 289                 (bl->bl_rootblks * sizeof(*live->meta))
 290         );
 291         if (base_radix != 1) {
 292                 kprintf("ALIST recurses when it reaches a base_radix of %d\n",
 293                         base_radix);
 294         }
 295         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
 296 #endif
 297         hammer_alist_init(live, 0, blocks, state);
 298         return(live);
 299 }
 300
 301 void
 302 hammer_alist_destroy(hammer_alist_t live, struct malloc_type *mtype)
 303 {
 304         kfree(live->config, mtype);
 305         kfree(live->meta, mtype);
 306         live->config = NULL;
 307         live->meta = NULL;
 308         kfree(live, mtype);
 309 }
 310
 311 #endif
 312
 313 /*
 314  * hammer_alist_alloc()
 315  *
 316  *      Reserve space in the block bitmap.  Return the base of a contiguous
 317  *      region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
 318  */
 319
 320 int32_t
 321 hammer_alist_alloc(hammer_alist_t live, int32_t count)
 322 {
 323         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
 324         hammer_alist_config_t bl = live->config;
 325
 326         KKASSERT((count | (count - 1)) == (count << 1) - 1);
 327
 328         if (bl && count <= bl->bl_radix) {
 329                 /*
 330                  * When skip is 1 we are at a leaf.  If we are the terminal
 331                  * allocator we use our native leaf functions and radix will
 332                  * be HAMMER_ALIST_BMAP_RADIX.  Otherwise we are a meta node
 333                  * which will chain to another allocator.
 334                  */
 335                 if (bl->bl_skip == 1 && bl->bl_terminal) {
 336 #ifndef _KERNEL
 337                         KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 338 #endif
 339                         blk = hammer_alst_leaf_alloc_fwd(
 340                                     live->meta + 1, 0, count, 0);
 341                 } else {
 342                         blk = hammer_alst_meta_alloc_fwd(
 343                                     live, live->meta + 1,
 344                                     0, count, bl->bl_radix, bl->bl_skip, 0);
 345                 }
 346                 if (blk != HAMMER_ALIST_BLOCK_NONE)
 347                         live->meta->bm_alist_freeblks -= count;
 348         }
 349         return(blk);
 350 }
 351
 352 int32_t
 353 hammer_alist_alloc_fwd(hammer_alist_t live, int32_t count, int32_t atblk)
 354 {
 355         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
 356         hammer_alist_config_t bl = live->config;
 357
 358         KKASSERT((count | (count - 1)) == (count << 1) - 1);
 359
 360         if (bl && count <= bl->bl_radix) {
 361                 /*
 362                  * When skip is 1 we are at a leaf.  If we are the terminal
 363                  * allocator we use our native leaf functions and radix will
 364                  * be HAMMER_ALIST_BMAP_RADIX.  Otherwise we are a meta node
 365                  * which will chain to another allocator.
 366                  */
 367                 if (bl->bl_skip == 1 && bl->bl_terminal) {
 368 #ifndef _KERNEL
 369                         KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 370 #endif
 371                         blk = hammer_alst_leaf_alloc_fwd(
 372                                     live->meta + 1, 0, count, atblk);
 373                 } else {
 374                         blk = hammer_alst_meta_alloc_fwd(
 375                                     live, live->meta + 1,
 376                                     0, count, bl->bl_radix, bl->bl_skip, atblk);
 377                 }
 378                 if (blk != HAMMER_ALIST_BLOCK_NONE)
 379                         live->meta->bm_alist_freeblks -= count;
 380         }
 381         return(blk);
 382 }
 383
 384 int32_t
 385 hammer_alist_alloc_rev(hammer_alist_t live, int32_t count, int32_t atblk)
 386 {
 387         hammer_alist_config_t bl = live->config;
 388         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
 389
 390         KKASSERT((count | (count - 1)) == (count << 1) - 1);
 391
 392         if (bl && count < bl->bl_radix) {
 393                 if (bl->bl_skip == 1 && bl->bl_terminal) {
 394 #ifndef _KERNEL
 395                         KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 396 #endif
 397                         blk = hammer_alst_leaf_alloc_rev(
 398                                     live->meta + 1, 0, count, atblk);
 399                 } else {
 400                         blk = hammer_alst_meta_alloc_rev(
 401                                     live, live->meta + 1,
 402                                     0, count, bl->bl_radix, bl->bl_skip, atblk);
 403                 }
 404                 if (blk != HAMMER_ALIST_BLOCK_NONE)
 405                         live->meta->bm_alist_freeblks -= count;
 406         }
 407         return(blk);
 408 }
 409
 410 /*
 411  * hammer_alist_find()
 412  *
 413  *      Locate the first block >= atblk and < maxblk marked as allocated
 414  *      in the A-list and return it.  Return HAMMER_ALIST_BLOCK_NONE if
 415  *      no block could be found.
 416  *
 417  *      HAMMER_ALIST_FIND_NOSTACK  - A special search mode which returns
 418  *      all initialized blocks (whether allocated or free) on bl_base_radix
 419  *      boundaries.  The all-free (11) state is treated as initialized only
 420  *      if bl_inverted is set.
 421  *
 422  *      HAMMER_ALIST_FIND_INITONLY - only initialized blocks are returned.
 423  *      Blocks belonging to the all-allocated/uninitialized state are not
 424  *      returned.
 425  */
 426 int32_t
 427 hammer_alist_find(hammer_alist_t live, int32_t atblk, int32_t maxblk, int flags)
 428 {
 429         hammer_alist_config_t bl = live->config;
 430         KKASSERT(live->config != NULL);
 431         KKASSERT(atblk >= 0);
 432         atblk = hammer_alst_find(live, live->meta + 1, 0, bl->bl_radix,
 433                                  bl->bl_skip, atblk, flags);
 434         if (atblk >= maxblk)
 435                 atblk = HAMMER_ALIST_BLOCK_NONE;
 436         return(atblk);
 437 }
 438
 439 /*
 440  * hammer_alist_free()
 441  *
 442  *      Free up space in the block bitmap.  Return the base of a contiguous
 443  *      region.  Panic if an inconsistancy is found.
 444  *
 445  *      Unlike allocations, there are no alignment requirements for blkno or
 446  *      count when freeing blocks.
 447  */
 448
 449 void
 450 hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count)
 451 {
 452         hammer_alist_config_t bl = live->config;
 453
 454         KKASSERT(blkno + count <= bl->bl_blocks);
 455         if (bl->bl_skip == 1 && bl->bl_terminal) {
 456 #ifndef _KERNEL
 457                 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
 458 #endif
 459                 hammer_alst_leaf_free(live->meta + 1, blkno, count);
 460         } else {
 461                 hammer_alst_meta_free(live, live->meta + 1,
 462                                       blkno, count,
 463                                       bl->bl_radix, bl->bl_skip, 0);
 464         }
 465         live->meta->bm_alist_freeblks += count;
 466 }
 467
 468 /*
 469  * Recover an A-list.  This will dive down to the leaves and regenerate
 470  * the hints and the freeblks count.  This function will also recurse
 471  * through any stacked A-lists.  > 0 is returned on success, a negative
 472  * error code on failure.
 473  *
 474  * Since A-lists have no pointers the only thing that can prevent recovery
 475  * is an I/O error in e.g. a stacked A-list.  This doesn't mean the recovered
 476  * map will be meaningful, however.
 477  *
 478  * blk is usually passed as 0 at the top level and is adjusted as the recovery
 479  * code scans the A-list.  It is only used when recursing down a stacked
 480  * A-list.
 481  *
 482  * (start,count) describes the region of the A-list which is allowed to contain
 483  * free blocks.  Any region to the left or right will be marked as allocated.
 484  */
 485 int
 486 hammer_alist_recover(hammer_alist_t live, int32_t blk, int32_t start,
 487                      int32_t count)
 488 {
 489         hammer_alist_config_t bl = live->config;
 490         struct hammer_alist_recover info;
 491
 492         info.live = live;
 493         info.error = 0;
 494
 495         live->meta->bm_alist_freeblks = 0;
 496         live->meta->bm_alist_base_freeblks = count;
 497         hammer_alst_radix_recover(&info, live->meta + 1, blk, bl->bl_radix,
 498                                   bl->bl_skip, bl->bl_blocks,
 499                                   start, start + count);
 500         if (info.error)
 501                 return(info.error);
 502         return(live->meta->bm_alist_freeblks);
 503 }
 504
 505 int
 506 hammer_alist_isfull(hammer_alist_t live)
 507 {
 508         return(live->meta->bm_alist_freeblks == 0);
 509 }
 510
 511 int
 512 hammer_alist_isempty(hammer_alist_t live)
 513 {
 514         return((int)live->meta->bm_alist_freeblks ==
 515                live->meta->bm_alist_base_freeblks);
 516 }
 517
 518 #ifdef ALIST_DEBUG
 519
 520 /*
 521  * alist_print()    - dump radix tree
 522  */
 523
 524 void
 525 hammer_alist_print(hammer_alist_t live, int tab)
 526 {
 527         hammer_alist_config_t bl = live->config;
 528
 529         kprintf("%*.*sALIST (%d/%d free blocks) {\n",
 530                 tab, tab, "",
 531                 live->meta->bm_alist_freeblks,
 532                 live->meta->bm_alist_base_freeblks);
 533         hammer_alst_radix_print(live, live->meta + 1, 0,
 534                                 bl->bl_radix, bl->bl_skip, tab + 4);
 535         kprintf("%*.*s}\n", tab, tab, "");
 536 }
 537
 538 #endif
 539
 540 /************************************************************************
 541  *                        ALLOCATION SUPPORT FUNCTIONS                  *
 542  ************************************************************************
 543  *
 544  *      These support functions do all the actual work.  They may seem
 545  *      rather longish, but that's because I've commented them up.  The
 546  *      actual code is straight forward.
 547  *
 548  */
 549
 550 /*
 551  * hammer_alist_leaf_alloc_fwd()
 552  *
 553  *      Allocate at a leaf in the radix tree (a bitmap).
 554  *
 555  *      This is the core of the allocator and is optimized for the 1 block
 556  *      and the HAMMER_ALIST_BMAP_RADIX block allocation cases.  Other cases
 557  *      are somewhat slower.  The 1 block allocation case is log2 and extremely
 558  *      quick.
 559  */
 560
 561 static int32_t
 562 hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk,
 563                            int count, int32_t atblk)
 564 {
 565         u_int32_t orig = scan->bm_bitmap;
 566         int32_t saveblk = blk;
 567
 568         /*
 569          * Optimize bitmap all-allocated case.  Also, count = 1
 570          * case assumes at least 1 bit is free in the bitmap, so
 571          * we have to take care of this case here.
 572          */
 573         if (orig == 0) {
 574                 scan->bm_bighint = 0;
 575                 return(HAMMER_ALIST_BLOCK_NONE);
 576         }
 577
 578 #if 0
 579         /*
 580          * Optimized code to allocate one bit out of the bitmap
 581          *
 582          * mask iterates e.g. 00001111 00000011 00000001
 583          *
 584          * mask starts at 00001111
 585          */
 586         if (count == 1) {
 587                 u_int32_t mask;
 588                 int j = HAMMER_ALIST_BMAP_RADIX/2;
 589                 int r = 0;
 590
 591                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
 592
 593                 while (j) {
 594                         if ((orig & mask) == 0) {
 595                             r += j;
 596                             orig >>= j;
 597                         }
 598                         j >>= 1;
 599                         mask >>= j;
 600                 }
 601                 scan->bm_bitmap &= ~(1 << r);
 602                 return(blk + r);
 603         }
 604 #endif
 605
 606         /*
 607          * non-optimized code to allocate N bits out of the bitmap.
 608          * The more bits, the faster the code runs.  It will run
 609          * the slowest allocating 2 bits, but since there aren't any
 610          * memory ops in the core loop (or shouldn't be, anyway),
 611          * you probably won't notice the difference.
 612          *
 613          * Similar to the blist case, the alist code also requires
 614          * allocations to be power-of-2 sized and aligned to the
 615          * size of the allocation, which simplifies the algorithm.
 616          */
 617         {
 618                 int j;
 619                 int n = HAMMER_ALIST_BMAP_RADIX - count;
 620                 u_int32_t mask;
 621
 622                 mask = (u_int32_t)-1 >> n;
 623
 624                 for (j = 0; j <= n; j += count) {
 625                         if ((orig & mask) == mask && blk >= atblk) {
 626                                 scan->bm_bitmap &= ~mask;
 627                                 return(blk);
 628                         }
 629                         mask = mask << count;
 630                         blk += count;
 631                 }
 632         }
 633
 634         /*
 635          * We couldn't allocate count in this subtree, update bighint if
 636          * atblk didn't interfere with the hinting mechanism.
 637          */
 638         if (saveblk >= atblk)
 639                 scan->bm_bighint = count - 1;
 640         return(HAMMER_ALIST_BLOCK_NONE);
 641 }
 642
 643 /*
 644  * This version allocates blocks in the reverse direction.
 645  */
 646 static int32_t
 647 hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk,
 648                            int count, int32_t atblk)
 649 {
 650         u_int32_t orig = scan->bm_bitmap;
 651         int32_t saveblk;
 652
 653         /*
 654          * Optimize bitmap all-allocated case.  Also, count = 1
 655          * case assumes at least 1 bit is free in the bitmap, so
 656          * we have to take care of this case here.
 657          */
 658         if (orig == 0) {
 659                 scan->bm_bighint = 0;
 660                 return(HAMMER_ALIST_BLOCK_NONE);
 661         }
 662
 663 #if 0
 664         /*
 665          * Optimized code to allocate one bit out of the bitmap
 666          */
 667         if (count == 1) {
 668                 u_int32_t mask;
 669                 int j = HAMMER_ALIST_BMAP_RADIX/2;
 670                 int r = HAMMER_ALIST_BMAP_RADIX - 1;
 671
 672                 mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
 673
 674                 while (j) {
 675                         if ((orig & mask) == 0) {
 676                             r -= j;
 677                             orig <<= j;
 678                         }
 679                         j >>= 1;
 680                         mask <<= j;
 681                 }
 682                 scan->bm_bitmap &= ~(1 << r);
 683                 return(blk + r);
 684         }
 685 #endif
 686
 687         /*
 688          * non-optimized code to allocate N bits out of the bitmap.
 689          * The more bits, the faster the code runs.  It will run
 690          * the slowest allocating 2 bits, but since there aren't any
 691          * memory ops in the core loop (or shouldn't be, anyway),
 692          * you probably won't notice the difference.
 693          *
 694          * Similar to the blist case, the alist code also requires
 695          * allocations to be power-of-2 sized and aligned to the
 696          * size of the allocation, which simplifies the algorithm.
 697          *
 698          * initial mask if count == 2:  1100....0000
 699          */
 700         {
 701                 int j;
 702                 int n = HAMMER_ALIST_BMAP_RADIX - count;
 703                 u_int32_t mask;
 704
 705                 mask = ((u_int32_t)-1 >> n) << n;
 706                 blk += n;
 707                 saveblk = blk;
 708
 709                 for (j = n; j >= 0; j -= count) {
 710                         if ((orig & mask) == mask && blk <= atblk) {
 711                                 scan->bm_bitmap &= ~mask;
 712                                 return(blk);
 713                         }
 714                         mask = mask >> count;
 715                         blk -= count;
 716                 }
 717         }
 718
 719         /*
 720          * We couldn't allocate count in this subtree, update bighint if
 721          * atblk didn't interfere with it.
 722          */
 723         if (saveblk <= atblk)
 724                 scan->bm_bighint = count - 1;
 725         return(HAMMER_ALIST_BLOCK_NONE);
 726 }
 727
 728 /*
 729  * hammer_alist_meta_alloc_fwd()
 730  *
 731  *      Allocate at a meta in the radix tree.
 732  *
 733  *      Attempt to allocate at a meta node.  If we can't, we update
 734  *      bighint and return a failure.  Updating bighint optimize future
 735  *      calls that hit this node.  We have to check for our collapse cases
 736  *      and we have a few optimizations strewn in as well.
 737  */
 738 static int32_t
 739 hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
 740                            int32_t blk, int32_t count,
 741                            int32_t radix, int skip, int32_t atblk
 742 ) {
 743         hammer_alist_config_t bl;
 744         u_int32_t mask;
 745         u_int32_t pmask;
 746         int32_t saveblk;
 747         int next_skip;
 748         int i;
 749
 750         /*
 751          * ALL-ALLOCATED special case
 752          */
 753         if (scan->bm_bitmap == 0 || scan->bm_bitmap == 0xAAAAAAAAU)  {
 754                 scan->bm_bighint = 0;
 755                 return(HAMMER_ALIST_BLOCK_NONE);
 756         }
 757
 758         radix /= HAMMER_ALIST_META_RADIX;
 759         bl = live->config;
 760
 761         /*
 762          * Radix now represents each bitmap entry for this meta node.  If
 763          * the number of blocks being allocated can be fully represented,
 764          * we allocate directly out of this meta node.
 765          *
 766          * Meta node bitmaps use 2 bits per block.
 767          *
 768          *      00      ALL-ALLOCATED - UNINITIALIZED
 769          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
 770          *      10      ALL-ALLOCATED - INITIALIZED
 771          *      11      ALL-FREE      - UNINITIALIZED
 772          */
 773         if (count >= radix) {
 774                 int n = count / radix * 2;      /* number of bits */
 775                 int nd2 = n / 2;
 776                 int j;
 777
 778                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
 779                 saveblk = blk;
 780                 for (j = 0; j < (int)HAMMER_ALIST_META_RADIX; j += nd2) {
 781                         if ((scan->bm_bitmap & mask) == mask && blk >= atblk) {
 782                                 /*
 783                                  * NOTE: Marked all-allocate/uninitialized
 784                                  * rather then all-allocated/initialized.
 785                                  * See the warning at the top of the file.
 786                                  */
 787                                 scan->bm_bitmap &= ~mask;
 788                                 return(blk);
 789                         }
 790                         mask <<= n;
 791                         blk += radix * nd2;
 792                 }
 793                 if (scan->bm_bighint >= count && saveblk >= atblk)
 794                         scan->bm_bighint = count >> 1;
 795                 return(HAMMER_ALIST_BLOCK_NONE);
 796         }
 797
 798         /*
 799          * If the count is too big we couldn't allocate anything from a
 800          * recursion even if the sub-tree were entirely free.
 801          */
 802         saveblk = blk;
 803         if (count > radix)
 804                 goto failed;
 805
 806         /*
 807          * If not we have to recurse.
 808          */
 809         mask = 0x00000003;
 810         pmask = 0x00000001;
 811
 812         if (skip == 1) {
 813                 /*
 814                  * If skip is 1 we are a meta leaf node, which means there
 815                  * is another allocation layer we have to dive down into.
 816                  */
 817                 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
 818                         /*
 819                          * If the next layer is completely free then call
 820                          * its init function to initialize it.
 821                          */
 822                         if ((scan->bm_bitmap & mask) == mask &&
 823                             blk + radix > atblk) {
 824                                 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
 825                                         /*
 826                                          * NOTE: Marked all-allocate/uninit-
 827                                          * ialized rather then all-allocated/
 828                                          * initialized.  See the warning at
 829                                          * the top of the file.
 830                                          */
 831                                         scan->bm_bitmap &= ~mask;
 832                                         scan->bm_bitmap |= pmask;
 833                                 }
 834                         }
 835
 836                         /*
 837                          * If there may be some free blocks try to allocate
 838                          * out of the layer.  If the layer indicates that
 839                          * it is completely full then clear both bits to
 840                          * propogate the condition.
 841                          */
 842                         if ((scan->bm_bitmap & mask) == pmask &&
 843                             blk + radix > atblk) {
 844                                 int32_t r;
 845                                 int32_t full;
 846
 847                                 r = bl->bl_radix_alloc_fwd(live->info, blk,
 848                                                            radix, count,
 849                                                            atblk, &full);
 850                                 if (full) {
 851                                         scan->bm_bitmap &= ~mask;
 852                                         scan->bm_bitmap |= pmask << 1;
 853                                 }
 854                                 if (r != HAMMER_ALIST_BLOCK_NONE)
 855                                         return(r);
 856                         }
 857                         blk += radix;
 858                         mask <<= 2;
 859                         pmask <<= 2;
 860                 }
 861         } else {
 862                 /*
 863                  * Otherwise there are sub-records in the current a-list
 864                  * layer.  We can also peek into the sub-layers to get
 865                  * more accurate size hints.
 866                  */
 867                 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
 868                 for (i = 1; i < skip; i += next_skip) {
 869                         if (scan[i].bm_bighint == (int32_t)-1) {
 870                                 /*
 871                                  * Terminator
 872                                  */
 873                                 break;
 874                         }
 875
 876                         /*
 877                          * Initialize bitmap if allocating from the all-free
 878                          * case.
 879                          */
 880                         if ((scan->bm_bitmap & mask) == mask) {
 881                                 scan[i].bm_bitmap = (u_int32_t)-1;
 882                                 scan[i].bm_bighint = radix;
 883                         }
 884
 885                         if (count <= scan[i].bm_bighint &&
 886                             blk + radix > atblk) {
 887                                 /*
 888                                  * count fits in object, recurse into the
 889                                  * next layer.  If the next_skip is 1 it
 890                                  * will be either a normal leaf or a meta
 891                                  * leaf.
 892                                  */
 893                                 int32_t r;
 894
 895                                 if (next_skip == 1 && bl->bl_terminal) {
 896                                         r = hammer_alst_leaf_alloc_fwd(
 897                                                 &scan[i], blk, count, atblk);
 898                                 } else {
 899                                         r = hammer_alst_meta_alloc_fwd(
 900                                                 live, &scan[i],
 901                                                 blk, count,
 902                                                 radix, next_skip, atblk);
 903                                 }
 904                                 if (r != HAMMER_ALIST_BLOCK_NONE) {
 905                                         if (scan[i].bm_bitmap == 0) {
 906                                                 scan->bm_bitmap &= ~mask;
 907                                         } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
 908                                                 scan->bm_bitmap &= ~mask;
 909                                                 scan->bm_bitmap |= pmask << 1;
 910                                         } else {
 911                                                 scan->bm_bitmap &= ~mask;
 912                                                 scan->bm_bitmap |= pmask;
 913                                         }
 914                                         return(r);
 915                                 }
 916                         }
 917                         blk += radix;
 918                         mask <<= 2;
 919                         pmask <<= 2;
 920                 }
 921         }
 922
 923 failed:
 924         /*
 925          * We couldn't allocate count in this subtree, update bighint.
 926          */
 927         if (scan->bm_bighint >= count && saveblk >= atblk)
 928                 scan->bm_bighint = count >> 1;
 929         return(HAMMER_ALIST_BLOCK_NONE);
 930 }
 931
 932 /*
 933  * This version allocates blocks in the reverse direction.
 934  *
 935  * This is really nasty code
 936  */
 937 static int32_t
 938 hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
 939                            int32_t blk, int32_t count,
 940                            int32_t radix, int skip, int32_t atblk
 941 ) {
 942         hammer_alist_config_t bl;
 943         int i;
 944         int j;
 945         u_int32_t mask;
 946         u_int32_t pmask;
 947         int32_t saveblk;
 948         int next_skip;
 949
 950         /*
 951          * ALL-ALLOCATED special case
 952          */
 953         if (scan->bm_bitmap == 0 || scan->bm_bitmap == 0xAAAAAAAAU)  {
 954                 scan->bm_bighint = 0;
 955                 return(HAMMER_ALIST_BLOCK_NONE);
 956         }
 957
 958         radix /= HAMMER_ALIST_META_RADIX;
 959         bl = live->config;
 960
 961         /*
 962          * Radix now represents each bitmap entry for this meta node.  If
 963          * the number of blocks being allocated can be fully represented,
 964          * we allocate directly out of this meta node.
 965          *
 966          * Meta node bitmaps use 2 bits per block.
 967          *
 968          *      00      ALL-ALLOCATED (uninitialized)
 969          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
 970          *      10      ALL-ALLOCATED (initialized)
 971          *      11      ALL-FREE
 972          */
 973         if (count >= radix) {
 974                 int n = count / radix * 2;      /* number of bits */
 975                 int nd2 = n / 2;                /* number of radi */
 976
 977                 /*
 978                  * Initial mask if e.g. n == 2:  1100....0000
 979                  */
 980                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
 981                         (HAMMER_ALIST_BMAP_RADIX - n);
 982                 blk += (HAMMER_ALIST_META_RADIX - nd2) * radix;
 983                 saveblk = blk;
 984                 for (j = HAMMER_ALIST_META_RADIX - nd2; j >= 0; j -= nd2) {
 985                         if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
 986                                 scan->bm_bitmap &= ~mask;
 987                                 return(blk);
 988                         }
 989                         mask >>= n;
 990                         blk -= nd2 * radix;
 991                 }
 992                 if (scan->bm_bighint >= count && saveblk <= atblk)
 993                         scan->bm_bighint = count >> 1;
 994                 return(HAMMER_ALIST_BLOCK_NONE);
 995         }
 996
 997         /*
 998          * NOTE: saveblk must represent the entire layer, not the base blk
 999          * of the last element.  Otherwise an atblk that is inside the
1000          * last element can cause bighint to be updated for a failed
1001          * allocation when we didn't actually test all available blocks.
1002          */
1003
1004         if (skip == 1) {
1005                 /*
1006                  * We need the recurse but we are at a meta node leaf, which
1007                  * means there is another layer under us.
1008                  */
1009                 mask = 0xC0000000;
1010                 pmask = 0x40000000;
1011                 blk += radix * HAMMER_ALIST_META_RADIX;
1012
1013                 saveblk = blk;
1014                 blk -= radix;
1015
1016                 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
1017                         /*
1018                          * If the next layer is completely free then call
1019                          * its init function to initialize it.  The init
1020                          * function is responsible for the initial freeing.
1021                          */
1022                         if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
1023                                 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
1024                                         scan->bm_bitmap &= ~mask;
1025                                         scan->bm_bitmap |= pmask;
1026                                 }
1027                         }
1028
1029                         /*
1030                          * If there may be some free blocks try to allocate
1031                          * out of the layer.  If the layer indicates that
1032                          * it is completely full then clear both bits to
1033                          * propogate the condition.
1034                          */
1035                         if ((scan->bm_bitmap & mask) == pmask && blk <= atblk) {
1036                                 int32_t r;
1037                                 int32_t full;
1038
1039                                 r = bl->bl_radix_alloc_rev(live->info, blk,
1040                                                            radix, count,
1041                                                            atblk, &full);
1042                                 if (full) {
1043                                         scan->bm_bitmap &= ~mask;
1044                                         scan->bm_bitmap |= pmask << 1;
1045                                 }
1046                                 if (r != HAMMER_ALIST_BLOCK_NONE)
1047                                         return(r);
1048                         }
1049                         mask >>= 2;
1050                         pmask >>= 2;
1051                         blk -= radix;
1052                 }
1053         } else {
1054                 /*
1055                  * Since we are going in the reverse direction we need an
1056                  * extra loop to determine if there is a terminator, then
1057                  * run backwards.
1058                  *
1059                  * This is a little weird but we do not want to overflow the
1060                  * mask/pmask in the loop.
1061                  */
1062                 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1063                 j = 0;
1064                 for (i = 1; i < skip; i += next_skip) {
1065                         if (scan[i].bm_bighint == (int32_t)-1) {
1066                                 KKASSERT(j != 0);
1067                                 break;
1068                         }
1069                         blk += radix;
1070                         j += 2;
1071                 }
1072
1073                 saveblk = blk;
1074                 blk -= radix;
1075                 j -= 2;
1076                 mask = 0x00000003 << j;
1077                 pmask = 0x00000001 << j;
1078                 i -= next_skip;
1079
1080                 while (i >= 1) {
1081                         /*
1082                          * Initialize the bitmap in the child if allocating
1083                          * from the all-free case.
1084                          */
1085                         if ((scan->bm_bitmap & mask) == mask) {
1086                                 scan[i].bm_bitmap = (u_int32_t)-1;
1087                                 scan[i].bm_bighint = radix;
1088                         }
1089
1090                         /*
1091                          * Handle various count cases.  Bighint may be too
1092                          * large but is never too small.
1093                          */
1094                         if (count <= scan[i].bm_bighint && blk <= atblk) {
1095                                 /*
1096                                  * count fits in object
1097                                  */
1098                                 int32_t r;
1099                                 if (next_skip == 1 && bl->bl_terminal) {
1100                                         r = hammer_alst_leaf_alloc_rev(
1101                                                 &scan[i], blk, count, atblk);
1102                                 } else {
1103                                         r = hammer_alst_meta_alloc_rev(
1104                                                 live, &scan[i],
1105                                                 blk, count,
1106                                                 radix, next_skip, atblk);
1107                                 }
1108                                 if (r != HAMMER_ALIST_BLOCK_NONE) {
1109                                         if (scan[i].bm_bitmap == 0) {
1110                                                 scan->bm_bitmap &= ~mask;
1111                                         } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1112                                                 scan->bm_bitmap &= ~mask;
1113                                                 scan->bm_bitmap |= pmask << 1;
1114                                         } else {
1115                                                 scan->bm_bitmap &= ~mask;
1116                                                 scan->bm_bitmap |= pmask;
1117                                         }
1118                                         return(r);
1119                                 }
1120                         }
1121                         blk -= radix;
1122                         mask >>= 2;
1123                         pmask >>= 2;
1124                         i -= next_skip;
1125                 }
1126         }
1127
1128         /*
1129          * We couldn't allocate count in this subtree, update bighint.
1130          * Since we are restricted to powers of 2, the next highest count
1131          * we might be able to allocate is (count >> 1).
1132          */
1133         if (scan->bm_bighint >= count && saveblk <= atblk)
1134                 scan->bm_bighint = count >> 1;
1135         return(HAMMER_ALIST_BLOCK_NONE);
1136 }
1137
1138 /*
1139  * HAMMER_ALST_FIND()
1140  *
1141  * Locate the first allocated block greater or equal to atblk.
1142  */
1143 static int32_t
1144 hammer_alst_find(hammer_alist_t live, hammer_almeta_t scan, int32_t blk,
1145                  int32_t radix, int32_t skip, int32_t atblk, int flags)
1146 {
1147         u_int32_t mask;
1148         u_int32_t pmask;
1149         int32_t next_skip;
1150         int32_t tmpblk;
1151         int nostack = flags & HAMMER_ALIST_FIND_NOSTACK;
1152         int initonly = flags & HAMMER_ALIST_FIND_INITONLY;
1153         int i;
1154         int j;
1155
1156         /*
1157          * Leaf node (currently hammer_alist_find() only works on terminal
1158          * a-list's and the case is asserted in hammer_alist_find()).
1159          */
1160         if (skip == 1 && live->config->bl_terminal) {
1161                 if (scan->bm_bitmap == (u_int32_t)-1)
1162                         return(HAMMER_ALIST_BLOCK_NONE);
1163                 for (i = 0; i < (int)HAMMER_ALIST_BMAP_RADIX; ++i) {
1164                         if (blk + i < atblk)
1165                                 continue;
1166                         if ((scan->bm_bitmap & (1 << i)) == 0)
1167                                 return(blk + i);
1168                 }
1169                 return(HAMMER_ALIST_BLOCK_NONE);
1170         }
1171
1172         /*
1173          * Meta
1174          */
1175         radix /= HAMMER_ALIST_META_RADIX;
1176         next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1177         mask = 0x00000003;
1178         pmask = 0x00000001;
1179         for (j = 0, i = 1; j < (int)HAMMER_ALIST_META_RADIX;
1180              (i += next_skip), ++j) {
1181                 /*
1182                  * Check Terminator
1183                  */
1184                 if (scan[i].bm_bighint == (int32_t)-1) {
1185                         break;
1186                 }
1187
1188                 /*
1189                  * Recurse if this meta might contain a desired block.
1190                  */
1191                 if (blk + radix > atblk) {
1192                         if (next_skip == 0 && nostack) {
1193                                 /*
1194                                  * At base_radix and nostack was specified.
1195                                  */
1196                                 if ((scan->bm_bitmap & mask) == 0) {
1197                                         /*
1198                                          * 00 - all-allocated, uninitalized
1199                                          */
1200                                         if (initonly == 0) {
1201                                                 if (atblk <= blk)
1202                                                         return(blk);
1203                                         }
1204                                 } else if ((scan->bm_bitmap & mask) != mask) {
1205                                         /*
1206                                          * 01 or 10 - partially allocated
1207                                          * or all-allocated/initialized.
1208                                          */
1209                                         if (atblk <= blk)
1210                                                 return(blk);
1211                                 } else if ((scan->bm_bitmap & mask) == mask) {
1212                                         /*
1213                                          * 11 - all free.  If inverted it is
1214                                          * initialized, however, and must be
1215                                          * returned for the no-stack case.
1216                                          */
1217                                         if (live->config->bl_inverted) {
1218                                                 if (atblk <= blk)
1219                                                         return(blk);
1220                                         }
1221                                 }
1222                         } else if ((scan->bm_bitmap & mask) == 0) {
1223                                 /*
1224                                  * 00 - all-allocated, uninitialized
1225                                  */
1226                                 if (initonly == 0) {
1227                                         goto return_all_meta;
1228                                 }
1229                                 /* else skip */
1230                         } else if ((scan->bm_bitmap & mask) == (pmask << 1)) {
1231                                 /*
1232                                  * 10 - all-allocated, initialized
1233                                  */
1234                                 goto return_all_meta;
1235                         } else if ((scan->bm_bitmap & mask) == mask) {
1236                                 /*
1237                                  * 11 - all-free (skip if not inverted)
1238                                  *
1239                                  * If nostack and inverted we must return
1240                                  * blocks on the base radix boundary.
1241                                  */
1242                                 if (nostack && live->config->bl_inverted) {
1243                                         int32_t bradix;
1244
1245 return_all_meta:
1246                                         bradix = live->config->bl_base_radix;
1247                                         if (atblk <= blk)
1248                                                 return(blk);
1249                                         atblk = (atblk + bradix - 1) &
1250                                                 ~(bradix - 1);
1251                                         if (atblk < blk + radix)
1252                                                 return(atblk);
1253                                 }
1254                         } else if (next_skip == 0) {
1255                                 /*
1256                                  * Partially allocated but we have to recurse
1257                                  * into a stacked A-list.
1258                                  *
1259                                  * If no-stack is set the caller just wants
1260                                  * to know if the
1261                                  */
1262                                 if (atblk < blk)
1263                                         atblk = blk;
1264                                 tmpblk = live->config->bl_radix_find(
1265                                                 live->info, blk, radix,
1266                                                 atblk, flags);
1267                                 if (tmpblk != HAMMER_ALIST_BLOCK_NONE)
1268                                         return(tmpblk);
1269                                 /* else skip */
1270                         } else if ((scan->bm_bitmap & mask) == pmask) {
1271                                 /*
1272                                  * 01 - partially-allocated
1273                                  */
1274                                 if (atblk < blk)
1275                                         atblk = blk;
1276                                 tmpblk = hammer_alst_find(live, &scan[i],
1277                                                           blk, radix,
1278                                                           next_skip, atblk,
1279                                                           flags);
1280                                 if (tmpblk != HAMMER_ALIST_BLOCK_NONE)
1281                                         return(tmpblk);
1282                         }
1283                 }
1284                 mask <<= 2;
1285                 pmask <<= 2;
1286                 blk += radix;
1287         }
1288         return(HAMMER_ALIST_BLOCK_NONE);
1289 }
1290
1291 /*
1292  * HAMMER_ALST_LEAF_FREE()
1293  *
1294  *      Free allocated blocks from leaf bitmap.  The allocation code is
1295  *      restricted to powers of 2, the freeing code is not.
1296  */
1297 static void
1298 hammer_alst_leaf_free(hammer_almeta_t scan, int32_t blk, int count) {
1299         /*
1300          * free some data in this bitmap
1301          *
1302          * e.g.
1303          *      0000111111111110000
1304          *          \_________/\__/
1305          *              v        n
1306          */
1307         int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
1308         u_int32_t mask;
1309
1310         mask = ((u_int32_t)-1 << n) &
1311             ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
1312
1313         if (scan->bm_bitmap & mask)
1314                 panic("hammer_alst_radix_free: freeing free block");
1315         scan->bm_bitmap |= mask;
1316
1317         /*
1318          * We could probably do a better job here.  We are required to make
1319          * bighint at least as large as the biggest contiguous block of
1320          * data.  If we just shoehorn it, a little extra overhead will
1321          * be incured on the next allocation (but only that one typically).
1322          */
1323         scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
1324 }
1325
1326 /*
1327  * BLST_META_FREE()
1328  *
1329  *      Free allocated blocks from radix tree meta info.
1330  *
1331  *      This support routine frees a range of blocks from the bitmap.
1332  *      The range must be entirely enclosed by this radix node.  If a
1333  *      meta node, we break the range down recursively to free blocks
1334  *      in subnodes (which means that this code can free an arbitrary
1335  *      range whereas the allocation code cannot allocate an arbitrary
1336  *      range).
1337  */
1338
1339 static void
1340 hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
1341                       int32_t freeBlk, int32_t count,
1342                       int32_t radix, int skip, int32_t blk
1343 ) {
1344         hammer_alist_config_t bl;
1345         int next_skip;
1346         u_int32_t mask;
1347         u_int32_t pmask;
1348         int i;
1349
1350         /*
1351          * Break the free down into its components.  Because it is so easy
1352          * to implement, frees are not limited to power-of-2 sizes.
1353          *
1354          * Each block in a meta-node bitmap takes two bits.
1355          */
1356         radix /= HAMMER_ALIST_META_RADIX;
1357         bl = live->config;
1358
1359         i = (freeBlk - blk) / radix;
1360         blk += i * radix;
1361         mask = 0x00000003 << (i * 2);
1362         pmask = 0x00000001 << (i * 2);
1363
1364         if (skip == 1) {
1365                 /*
1366                  * Our meta node is a leaf node, which means it must recurse
1367                  * into another allocator.
1368                  */
1369                 while (i < (int)HAMMER_ALIST_META_RADIX &&
1370                        blk < freeBlk + count) {
1371                         int32_t v;
1372
1373                         v = blk + radix - freeBlk;
1374                         if (v > count)
1375                                 v = count;
1376
1377                         if (scan->bm_bighint == (int32_t)-1)
1378                                 panic("hammer_alst_meta_free: freeing unexpected range");
1379                         KKASSERT((scan->bm_bitmap & mask) != mask);
1380
1381                         if (freeBlk == blk && count >= radix) {
1382                                 /*
1383                                  * Freeing an entire zone.  Only recurse if
1384                                  * the zone was initialized.  A 00 state means
1385                                  * that the zone is marked all-allocated,
1386                                  * but was never initialized.
1387                                  *
1388                                  * Then set the zone to the all-free state (11).
1389                                  */
1390                                 int32_t empty;
1391
1392                                 if (scan->bm_bitmap & mask) {
1393                                         bl->bl_radix_free(live->info, blk, radix,
1394                                                           freeBlk - blk, v, &empty);
1395                                         KKASSERT(empty);
1396                                         bl->bl_radix_destroy(live->info, blk, radix);
1397                                 }
1398                                 scan->bm_bitmap |= mask;
1399                                 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1400                                 /* XXX bighint not being set properly */
1401                         } else {
1402                                 /*
1403                                  * Recursion case, partial free.  If 00 the
1404                                  * zone is marked all allocated but has never
1405                                  * been initialized, so we init it.
1406                                  */
1407                                 int32_t empty;
1408
1409                                 if ((scan->bm_bitmap & mask) == 0)
1410                                         bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_ALLOC);
1411                                 bl->bl_radix_free(live->info, blk, radix,
1412                                                   freeBlk - blk, v, &empty);
1413                                 if (empty) {
1414                                         if (scan->bm_bitmap & mask)
1415                                                 bl->bl_radix_destroy(live->info, blk, radix);
1416                                         scan->bm_bitmap |= mask;
1417                                         scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1418                                         /* XXX bighint not being set properly */
1419                                 } else {
1420                                         scan->bm_bitmap &= ~mask;
1421                                         scan->bm_bitmap |= pmask;
1422                                         if (scan->bm_bighint < radix / 2)
1423                                                 scan->bm_bighint = radix / 2;
1424                                         /* XXX bighint not being set properly */
1425                                 }
1426                         }
1427                         ++i;
1428                         mask <<= 2;
1429                         pmask <<= 2;
1430                         count -= v;
1431                         freeBlk += v;
1432                         blk += radix;
1433                 }
1434         } else {
1435                 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1436                 i = 1 + i * next_skip;
1437
1438                 while (i <= skip && blk < freeBlk + count) {
1439                         int32_t v;
1440
1441                         KKASSERT(mask != 0);
1442                         KKASSERT(count != 0);
1443
1444                         v = blk + radix - freeBlk;
1445                         if (v > count)
1446                                 v = count;
1447
1448                         if (scan->bm_bighint == (int32_t)-1)
1449                                 panic("hammer_alst_meta_free: freeing unexpected range");
1450
1451                         if (freeBlk == blk && count >= radix) {
1452                                 /*
1453                                  * All-free case, no need to update sub-tree
1454                                  */
1455                                 scan->bm_bitmap |= mask;
1456                                 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1457                                 /* XXX bighint not being set properly */
1458                         } else {
1459                                 /*
1460                                  * Recursion case
1461                                  */
1462                                 if (next_skip == 1 && bl->bl_terminal) {
1463                                         hammer_alst_leaf_free(&scan[i], freeBlk, v);
1464                                 } else {
1465                                         hammer_alst_meta_free(live, &scan[i],
1466                                                               freeBlk, v,
1467                                                               radix, next_skip,
1468                                                               blk);
1469                                 }
1470                                 if (scan[i].bm_bitmap == (u_int32_t)-1) {
1471                                         scan->bm_bitmap |= mask;
1472                                         /* XXX bighint not set properly */
1473                                         scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1474                                 } else {
1475                                         scan->bm_bitmap &= ~mask;
1476                                         scan->bm_bitmap |= pmask;
1477                                         /* XXX bighint not set properly */
1478                                         if (scan->bm_bighint < scan[i].bm_bighint)
1479                                                 scan->bm_bighint = scan[i].bm_bighint;
1480                                 }
1481                         }
1482                         mask <<= 2;
1483                         pmask <<= 2;
1484                         count -= v;
1485                         freeBlk += v;
1486                         blk += radix;
1487                         i += next_skip;
1488                 }
1489         }
1490 }
1491
1492 /*
1493  * hammer_alst_radix_init()
1494  *
1495  *      Initialize our meta structures and bitmaps and calculate the exact
1496  *      number of meta-nodes required to manage 'count' blocks.
1497  *
1498  *      The required space may be truncated due to early termination records.
1499  */
1500 static int32_t
1501 hammer_alst_radix_init(hammer_almeta_t scan, int32_t radix,
1502                        int skip, int32_t count)
1503 {
1504         int i;
1505         int next_skip;
1506         int32_t memindex = 1;
1507         u_int32_t mask;
1508         u_int32_t pmask;
1509
1510         /*
1511          * Basic initialization of the almeta for meta or leaf nodes.  This
1512          * marks the element as all-allocated.
1513          */
1514         if (scan) {
1515                 scan->bm_bighint = 0;
1516                 scan->bm_bitmap = 0;
1517         }
1518
1519         /*
1520          * We are at a terminal node, we only eat one meta element.   If
1521          * live->config->bl_terminal is set this is a leaf node, otherwise
1522          * it is a meta node for a stacked A-list.  We do NOT recurse into
1523          * stacked A-lists but simply mark the entire stack as all-free using
1524          * code 00 (meaning all-free & uninitialized).
1525          */
1526         if (skip == 1)
1527                 return(memindex);
1528
1529         /*
1530          * Meta node.  If allocating the entire object we can special
1531          * case it.  However, we need to figure out how much memory
1532          * is required to manage 'count' blocks, so we continue on anyway.
1533          */
1534         radix /= HAMMER_ALIST_META_RADIX;
1535         next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1536         mask = 0x00000003;
1537         pmask = 0x00000001;
1538
1539         for (i = 1; i < skip; i += next_skip) {
1540                 /*
1541                  * We eat up to this record
1542                  */
1543                 memindex = i;
1544
1545                 KKASSERT(mask != 0);
1546
1547                 if (count >= radix) {
1548                         /*
1549                          * Allocate the entire object
1550                          */
1551                         memindex += hammer_alst_radix_init(
1552                             ((scan) ? &scan[i] : NULL),
1553                             radix,
1554                             next_skip,
1555                             radix
1556                         );
1557                         count -= radix;
1558                         /* already marked as wholely allocated */
1559                 } else if (count > 0) {
1560                         /*
1561                          * Allocate a partial object
1562                          */
1563                         memindex += hammer_alst_radix_init(
1564                             ((scan) ? &scan[i] : NULL),
1565                             radix,
1566                             next_skip,
1567                             count
1568                         );
1569                         count = 0;
1570
1571                         /*
1572                          * Mark as partially allocated
1573                          */
1574                         if (scan) {
1575                                 scan->bm_bitmap &= ~mask;
1576                                 scan->bm_bitmap |= pmask;
1577                         }
1578                 } else {
1579                         /*
1580                          * Add terminator and break out.  The terminal
1581                          * eats the meta node at scan[i].
1582                          */
1583                         ++memindex;
1584                         if (scan)
1585                                 scan[i].bm_bighint = (int32_t)-1;
1586                         /* already marked as wholely allocated */
1587                         break;
1588                 }
1589                 mask <<= 2;
1590                 pmask <<= 2;
1591         }
1592         return(memindex);
1593 }
1594
1595 /*
1596  * hammer_alst_radix_recover()
1597  *
1598  *      This code is basically a duplicate of hammer_alst_radix_init()
1599  *      except it recovers the a-list instead of initializes it.
1600  *
1601  *      (a_beg,a_end) specifies the global allocatable range within
1602  *      the radix tree.  The recovery code guarentees that blocks
1603  *      within the tree but outside this range are marked as being
1604  *      allocated to prevent them from being allocated.
1605  *
1606  *
1607  */
1608 static void
1609 hammer_alst_radix_recover(hammer_alist_recover_t info, hammer_almeta_t scan,
1610                           int32_t blk, int32_t radix, int skip, int32_t count,
1611                           int32_t a_beg, int32_t a_end)
1612 {
1613         hammer_alist_t live = info->live;
1614         u_int32_t mask;
1615         u_int32_t pmask;
1616         int next_skip;
1617         int i;
1618         int j;
1619         int n;
1620
1621         /*
1622          * Don't try to recover bighint, just set it to its maximum
1623          * value and let the A-list allocations reoptimize it.  XXX
1624          */
1625         scan->bm_bighint = radix;
1626
1627         /*
1628          * If we are at a terminal node (i.e. not stacked on top of another
1629          * A-list), just count the free blocks.
1630          */
1631         if (skip == 1 && live->config->bl_terminal) {
1632                 for (i = 0; i < (int)HAMMER_ALIST_BMAP_RADIX; ++i) {
1633                         if (blk + i < a_beg || blk + i >= a_end)
1634                                 scan->bm_bitmap &= ~(1 << i);
1635                         if (scan->bm_bitmap & (1 << i))
1636                                 ++info->live->meta->bm_alist_freeblks;
1637                 }
1638                 return;
1639         }
1640
1641         /*
1642          * Recursive meta node (next_skip != 0) or terminal meta
1643          * node (next_skip == 0).
1644          */
1645         radix /= HAMMER_ALIST_META_RADIX;
1646         next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1647         mask = 0x00000003;
1648         pmask = 0x00000001;
1649
1650         for (i = 1, j = 0; j < (int)HAMMER_ALIST_META_RADIX;
1651               ++j, (i += next_skip)) {
1652                 /*
1653                  * Check mask:
1654                  *
1655                  *      00      ALL-ALLOCATED - UNINITIALIZED
1656                  *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
1657                  *      10      ALL-ALLOCATED - INITIALIZED
1658                  *      11      ALL-FREE      - UNINITIALIZED (INITIALIZED
1659                  *                              IF CONFIG SAYS INVERTED)
1660                  */
1661                 KKASSERT(mask);
1662
1663                 /*
1664                  * Adjust the bitmap for out of bounds or partially out of
1665                  * bounds elements.  If we are completely out of bounds
1666                  * mark as all-allocated.  If we are partially out of
1667                  * bounds do not allow the area to be marked all-free.
1668                  */
1669                 if (blk + radix <= a_beg || blk >= a_end) {
1670                         scan->bm_bitmap &= ~mask;
1671                 } else if (blk < a_beg || blk + radix > a_end) {
1672                         if ((scan->bm_bitmap & mask) == mask) {
1673                                 scan->bm_bitmap &= ~mask;
1674                                 scan->bm_bitmap |= pmask;
1675                         }
1676                 }
1677
1678                 if (count >= radix) {
1679                         /*
1680                          * Recover the entire object
1681                          */
1682                         if ((scan->bm_bitmap & mask) == 0) {
1683                                 /*
1684                                  * All-allocated (uninited), do nothing
1685                                  */
1686                         } else if ((scan->bm_bitmap & mask) == mask &&
1687                                    live->config->bl_inverted == 0) {
1688                                 /*
1689                                  * All-free (uninited), do nothing.
1690                                  *
1691                                  * (if inverted all-free is initialized and
1692                                  * must be recovered).
1693                                  */
1694                                 live->meta->bm_alist_freeblks += radix;
1695                         } else if (next_skip) {
1696                                 if ((scan->bm_bitmap & mask) == mask) {
1697                                         /*
1698                                          * This is a special case.  If we
1699                                          * are inverted but in an all-free
1700                                          * state, it's actually initialized
1701                                          * (sorta) and we still have to dive
1702                                          * through to any stacked nodes so
1703                                          * we can call bl_radix_recover().
1704                                          */
1705                                         scan[i].bm_bitmap = (u_int32_t)-1;
1706                                 }
1707                                 /*
1708                                  * Normal meta node, initialized.  Recover and
1709                                  * adjust to the proper state.
1710                                  */
1711                                 hammer_alst_radix_recover(
1712                                     info,
1713                                     &scan[i],
1714                                     blk, radix,
1715                                     next_skip, radix,
1716                                     a_beg, a_end
1717                                 );
1718                                 if (scan[i].bm_bitmap == 0) {
1719                                         scan->bm_bitmap &= ~mask;
1720                                 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1721                                         scan->bm_bitmap &= ~mask;
1722                                         scan->bm_bitmap |= pmask << 1;
1723                                 } else if (scan[i].bm_bitmap == (u_int32_t)-1) {
1724                                         scan->bm_bitmap |= mask;
1725                                 } else {
1726                                         scan->bm_bitmap &= ~mask;
1727                                         scan->bm_bitmap |= pmask;
1728                                 }
1729                         } else {
1730                                 /*
1731                                  * Stacked meta node, recurse.
1732                                  *
1733                                  * If no free blocks are present mark the
1734                                  * meta node as all-allocated/initialized.
1735                                  * A return code of -EDOM will mark the
1736                                  * meta node as all-allocated/uninitialized.
1737                                  *
1738                                  * This can be really confusing. bl_inverted
1739                                  * has no function here because we are
1740                                  * ALREADY known to be in an initialized
1741                                  * state.
1742                                  */
1743                                 n = live->config->bl_radix_recover(
1744                                             live->info,
1745                                             blk, radix, radix);
1746                                 if (n == -EDOM) {
1747                                         scan->bm_bitmap &= ~mask;
1748                                 } else if (n >= 0) {
1749                                         live->meta->bm_alist_freeblks += n;
1750                                         if (n == 0) {
1751                                                 scan->bm_bitmap =
1752                                                     (scan->bm_bitmap & ~mask) |
1753                                                     (pmask << 1);
1754                                         } else if (n == radix) {
1755                                                 scan->bm_bitmap |= mask;
1756                                         } else {
1757                                                 scan->bm_bitmap =
1758                                                     (scan->bm_bitmap & ~mask) |
1759                                                     pmask;
1760                                         }
1761                                 } else {
1762                                         info->error = n;
1763                                 }
1764                         }
1765                         count -= radix;
1766                 } else if (count > 0) {
1767                         /*
1768                          * Recover a partial object.  The object can become
1769                          * wholely allocated but never wholely free.
1770                          */
1771                         if (next_skip) {
1772                                 hammer_alst_radix_recover(
1773                                     info,
1774                                     &scan[i],
1775                                     blk, radix,
1776                                     next_skip, count,
1777                                     a_beg, a_end
1778                                 );
1779                                 if (scan[i].bm_bitmap == 0) {
1780                                         scan->bm_bitmap &= ~mask;
1781                                 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1782                                         scan->bm_bitmap &= ~mask;
1783                                         scan->bm_bitmap |= pmask << 1;
1784                                 } else {
1785                                         scan->bm_bitmap &= ~mask;
1786                                         scan->bm_bitmap |= pmask;
1787                                 }
1788                         } else {
1789                                 /*
1790                                  * If no free blocks are present mark the
1791                                  * meta node as all-allocated/initialized.
1792                                  * A return code of -EDOM will mark the
1793                                  * meta node as all-allocated/uninitialized.
1794                                  *
1795                                  * This can be really confusing. bl_inverted
1796                                  * has no function here because we are
1797                                  * ALREADY known to be in an initialized
1798                                  */
1799                                 n = live->config->bl_radix_recover(
1800                                             live->info,
1801                                             blk, radix, count);
1802                                 if (n == -EDOM) {
1803                                         scan->bm_bitmap &= ~mask;
1804                                 } else if (n >= 0) {
1805                                         live->meta->bm_alist_freeblks += n;
1806                                         if (n == 0) {
1807                                                 scan->bm_bitmap &= ~mask;
1808                                                 scan->bm_bitmap |= pmask << 1;
1809                                         } else {
1810                                                 scan->bm_bitmap &= ~mask;
1811                                                 scan->bm_bitmap |= pmask;
1812                                         }
1813                                 } else {
1814                                         info->error = n;
1815                                 }
1816                         }
1817                         count = 0;
1818                 } else if (next_skip) {
1819                         /*
1820                          * Add terminator.  The terminator eats the meta
1821                          * node at scan[i].  There is only ONE terminator,
1822                          * make sure we don't write out any more (set count to
1823                          * -1) or we may overflow our allocation.
1824                          */
1825                         if (count == 0) {
1826                                 scan[i].bm_bighint = (int32_t)-1;
1827                                 count = -1;
1828                         }
1829                         scan->bm_bitmap &= ~mask;       /* all-allocated/uni */
1830                 } else {
1831                         scan->bm_bitmap &= ~mask;       /* all-allocated/uni */
1832                 }
1833                 mask <<= 2;
1834                 pmask <<= 2;
1835                 blk += radix;
1836         }
1837 }
1838
1839 #ifdef ALIST_DEBUG
1840
1841 static void
1842 hammer_alst_radix_print(hammer_alist_t live, hammer_almeta_t scan,
1843                         int32_t blk, int32_t radix, int skip, int tab)
1844 {
1845         int i;
1846         int next_skip;
1847         int lastState = 0;
1848         u_int32_t mask;
1849
1850         if (skip == 1 && live->config->bl_terminal) {
1851                 kprintf(
1852                     "%*.*s(%04x,%d): bitmap %08x big=%d\n",
1853                     tab, tab, "",
1854                     blk, radix,
1855                     scan->bm_bitmap,
1856                     scan->bm_bighint
1857                 );
1858                 return;
1859         }
1860
1861         if (scan->bm_bitmap == 0) {
1862                 kprintf(
1863                     "%*.*s(%04x,%d) ALL ALLOCATED\n",
1864                     tab, tab, "",
1865                     blk,
1866                     radix
1867                 );
1868                 return;
1869         }
1870         if (scan->bm_bitmap == (u_int32_t)-1) {
1871                 kprintf(
1872                     "%*.*s(%04x,%d) ALL FREE\n",
1873                     tab, tab, "",
1874                     blk,
1875                     radix
1876                 );
1877                 return;
1878         }
1879
1880         kprintf(
1881             "%*.*s(%04x,%d): %s (%d) bitmap=%08x big=%d {\n",
1882             tab, tab, "",
1883             blk, radix,
1884             (skip == 1 ? "LAYER" : "subtree"),
1885             radix,
1886             scan->bm_bitmap,
1887             scan->bm_bighint
1888         );
1889
1890         radix /= HAMMER_ALIST_META_RADIX;
1891         tab += 4;
1892         mask = 0x00000003;
1893
1894         if (skip == 1) {
1895                 for (i = 0; i < HAMMER_ALIST_META_RADIX; ++i) {
1896                         if ((scan->bm_bitmap & mask) == mask) {
1897                                 kprintf(
1898                                     "%*.*s(%04x,%d): ALL FREE\n",
1899                                     tab, tab, "",
1900                                     blk, radix
1901                                 );
1902                         } else if ((scan->bm_bitmap & mask) == 0) {
1903                                 kprintf(
1904                                     "%*.*s(%04x,%d): ALL ALLOCATED\n",
1905                                     tab, tab, "",
1906                                     blk, radix
1907                                 );
1908                         } else {
1909                                 live->config->bl_radix_print(
1910                                                 live->info, blk, radix, tab);
1911                         }
1912                         blk += radix;
1913                         mask <<= 2;
1914                 }
1915         } else {
1916                 next_skip = ((u_int)(skip - 1) / HAMMER_ALIST_META_RADIX);
1917
1918                 for (i = 1; i < skip; i += next_skip) {
1919                         KKASSERT(mask != 0);
1920                         if (scan[i].bm_bighint == (int32_t)-1) {
1921                                 kprintf(
1922                                     "%*.*s(%04x,%d): Terminator\n",
1923                                     tab, tab, "",
1924                                     blk, radix
1925                                 );
1926                                 lastState = 0;
1927                                 break;
1928                         }
1929                         if ((scan->bm_bitmap & mask) == mask) {
1930                                 kprintf(
1931                                     "%*.*s(%04x,%d): ALL FREE\n",
1932                                     tab, tab, "",
1933                                     blk, radix
1934                                 );
1935                         } else if ((scan->bm_bitmap & mask) == 0) {
1936                                 kprintf(
1937                                     "%*.*s(%04x,%d): ALL ALLOCATED\n",
1938                                     tab, tab, "",
1939                                     blk, radix
1940                                 );
1941                         } else {
1942                                 hammer_alst_radix_print(
1943                                     live,
1944                                     &scan[i],
1945                                     blk,
1946                                     radix,
1947                                     next_skip,
1948                                     tab
1949                                 );
1950                         }
1951                         blk += radix;
1952                         mask <<= 2;
1953                 }
1954         }
1955         tab -= 4;
1956
1957         kprintf(
1958             "%*.*s}\n",
1959             tab, tab, ""
1960         );
1961 }
1962
1963 #endif
1964
1965 #ifdef ALIST_DEBUG
1966
1967 static struct hammer_alist_live **layers;       /* initialized by main */
1968 static int32_t layer_radix = -1;
1969
1970 /*
1971  * Initialize a zone.
1972  *
1973  * If allocating is non-zero this init is being called when transitioning out
1974  * of an all-free state.  Allocate the zone and mark the whole mess as being
1975  * free so the caller can then allocate out of this zone.
1976  *
1977  * If freeing this init is being called when transitioning out of an
1978  * initial all-allocated (00) state.  Allocate the zone but leave the whole
1979  * mess left all-allocated.  The caller will then free the appropriate range.
1980  */
1981 static
1982 int
1983 debug_radix_init(void *info, int32_t blk, int32_t radix,
1984                  enum hammer_alloc_state state)
1985 {
1986         hammer_alist_t layer;
1987         int layer_no = blk / layer_radix;
1988
1989         printf("lower layer: init (%04x,%d) layer_radix=%d\n",
1990                blk, radix, layer_radix);
1991         KKASSERT(layer_radix == radix);
1992         KKASSERT(layers[layer_no] == NULL);
1993         layer = layers[layer_no] = hammer_alist_create(radix, 1, NULL, state);
1994         return(0);
1995 }
1996
1997 static
1998 int32_t
1999 debug_radix_recover(void *info, int32_t blk, int32_t radix, int32_t count)
2000 {
2001         hammer_alist_t layer;
2002         int layer_no = blk / layer_radix;
2003         int32_t n;
2004
2005         KKASSERT(layer_radix == radix);
2006         KKASSERT(layers[layer_no] != NULL);
2007         layer = layers[layer_no];
2008         n = hammer_alist_recover(layer, blk, 0, count);
2009         printf("Recover layer %d blk %d result %d/%d\n",
2010                 layer_no, blk, n, count);
2011         return(n);
2012 }
2013
2014 static
2015 int32_t
2016 debug_radix_find(void *info, int32_t blk, int32_t radix, int32_t atblk,
2017                  int flags)
2018 {
2019         hammer_alist_t layer;
2020         int layer_no = blk / layer_radix;
2021         int32_t res;
2022
2023         KKASSERT(layer_radix == radix);
2024         KKASSERT(layers[layer_no] != NULL);
2025         layer = layers[layer_no];
2026         res = hammer_alist_find(layer, atblk - blk, radix, flags);
2027         if (res != HAMMER_ALIST_BLOCK_NONE)
2028                 res += blk;
2029         return(res);
2030 }
2031
2032 /*
2033  * This is called when a zone becomes entirely free, typically after a
2034  * call to debug_radix_free() has indicated that the entire zone is now
2035  * free.
2036  */
2037 static
2038 int
2039 debug_radix_destroy(void *info, int32_t blk, int32_t radix)
2040 {
2041         hammer_alist_t layer;
2042         int layer_no = blk / layer_radix;
2043
2044         printf("lower layer: destroy (%04x,%d)\n", blk, radix);
2045         layer = layers[layer_no];
2046         KKASSERT(layer != NULL);
2047         hammer_alist_destroy(layer, NULL);
2048         layers[layer_no] = NULL;
2049         return(0);
2050 }
2051
2052
2053 static
2054 int32_t
2055 debug_radix_alloc_fwd(void *info, int32_t blk, int32_t radix,
2056                       int32_t count, int32_t atblk, int32_t *fullp)
2057 {
2058         hammer_alist_t layer = layers[blk / layer_radix];
2059         int32_t r;
2060
2061         r = hammer_alist_alloc_fwd(layer, count, atblk - blk);
2062         *fullp = hammer_alist_isfull(layer);
2063         if (r != HAMMER_ALIST_BLOCK_NONE)
2064                 r += blk;
2065         return(r);
2066 }
2067
2068 static
2069 int32_t
2070 debug_radix_alloc_rev(void *info, int32_t blk, int32_t radix,
2071                       int32_t count, int32_t atblk, int32_t *fullp)
2072 {
2073         hammer_alist_t layer = layers[blk / layer_radix];
2074         int32_t r;
2075
2076         r = hammer_alist_alloc_rev(layer, count, atblk - blk);
2077         *fullp = hammer_alist_isfull(layer);
2078         if (r != HAMMER_ALIST_BLOCK_NONE)
2079                 r += blk;
2080         return(r);
2081 }
2082
2083 static
2084 void
2085 debug_radix_free(void *info, int32_t blk, int32_t radix,
2086                  int32_t base_blk, int32_t count, int32_t *emptyp)
2087 {
2088         int layer_no = blk / layer_radix;
2089         hammer_alist_t layer = layers[layer_no];
2090
2091         KKASSERT(layer);
2092         hammer_alist_free(layer, base_blk, count);
2093         *emptyp = hammer_alist_isempty(layer);
2094 }
2095
2096 static
2097 void
2098 debug_radix_print(void *info, int32_t blk, int32_t radix, int tab)
2099 {
2100         hammer_alist_t layer = layers[blk / layer_radix];
2101
2102         hammer_alist_print(layer, tab);
2103 }
2104
2105 int
2106 main(int ac, char **av)
2107 {
2108         int32_t size = -1;
2109         int i;
2110         hammer_alist_t live;
2111         hammer_almeta_t meta = NULL;
2112
2113         for (i = 1; i < ac; ++i) {
2114                 const char *ptr = av[i];
2115                 if (*ptr != '-') {
2116                         if (size == -1)
2117                                 size = strtol(ptr, NULL, 0);
2118                         else if (layer_radix == -1)
2119                                 layer_radix = strtol(ptr, NULL, 0);
2120                         else
2121                                 ;
2122                         continue;
2123                 }
2124                 ptr += 2;
2125                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
2126                 exit(1);
2127         }
2128         if (size == -1)
2129                 size = 1024;
2130         if (layer_radix == -1)
2131                 layer_radix = 1;        /* no second storage layer */
2132         if ((size ^ (size - 1)) != (size << 1) - 1) {
2133                 fprintf(stderr, "size must be a power of 2\n");
2134                 exit(1);
2135         }
2136         if ((layer_radix ^ (layer_radix - 1)) != (layer_radix << 1) - 1) {
2137                 fprintf(stderr, "the second layer radix must be a power of 2\n");
2138                 exit(1);
2139         }
2140
2141         live = hammer_alist_create(size, layer_radix, NULL,
2142                                    HAMMER_ASTATE_ALLOC);
2143         layers = calloc(size, sizeof(hammer_alist_t));
2144
2145         printf("A-LIST TEST %d blocks, first-layer radix %d, "
2146                "second-layer radix %d\n",
2147                 size, live->config->bl_radix / layer_radix, layer_radix);
2148
2149         live->config->bl_radix_init = debug_radix_init;
2150         live->config->bl_radix_recover = debug_radix_recover;
2151         live->config->bl_radix_find = debug_radix_find;
2152         live->config->bl_radix_destroy = debug_radix_destroy;
2153         live->config->bl_radix_alloc_fwd = debug_radix_alloc_fwd;
2154         live->config->bl_radix_alloc_rev = debug_radix_alloc_rev;
2155         live->config->bl_radix_free = debug_radix_free;
2156         live->config->bl_radix_print = debug_radix_print;
2157
2158         hammer_alist_free(live, 0, size);
2159
2160         for (;;) {
2161                 char buf[1024];
2162                 int32_t da = 0;
2163                 int32_t count = 0;
2164                 int32_t atblk;
2165                 int32_t blk;
2166                 int flags;
2167
2168                 kprintf("%d/%d> ",
2169                         live->meta->bm_alist_freeblks, size);
2170                 fflush(stdout);
2171                 if (fgets(buf, sizeof(buf), stdin) == NULL)
2172                         break;
2173                 switch(buf[0]) {
2174                 case 'p':
2175                         hammer_alist_print(live, 0);
2176
2177                         flags = 0;
2178                         if (buf[1] == 'i' || (buf[1] && buf[2] == 'i'))
2179                                 flags |= HAMMER_ALIST_FIND_INITONLY;
2180                         if (buf[1] == 'm' || (buf[1] && buf[2] == 'm'))
2181                                 flags |= HAMMER_ALIST_FIND_NOSTACK;
2182                         atblk = 0;
2183                         kprintf("allocated: ");
2184                         while ((atblk = hammer_alist_find(live, atblk, size, flags)) != HAMMER_ALIST_BLOCK_NONE) {
2185                                 kprintf(" %d", atblk);
2186                                 ++atblk;
2187                         }
2188                         kprintf("\n");
2189                         break;
2190                 case 'a':
2191                         atblk = 0;
2192                         if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
2193                                 blk = hammer_alist_alloc_fwd(live, count, atblk);
2194                                 kprintf("    R=%04x\n", blk);
2195                         } else {
2196                                 kprintf("?\n");
2197                         }
2198                         break;
2199                 case 'r':
2200                         atblk = HAMMER_ALIST_BLOCK_MAX;
2201                         if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
2202                                 blk = hammer_alist_alloc_rev(live, count, atblk);
2203                                 kprintf("    R=%04x\n", blk);
2204                         } else {
2205                                 kprintf("?\n");
2206                         }
2207                         break;
2208                 case 'f':
2209                         if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
2210                                 hammer_alist_free(live, da, count);
2211                                 if (hammer_alist_isempty(live))
2212                                         kprintf("a-list is now 100%% empty\n");
2213                         } else {
2214                                 kprintf("?\n");
2215                         }
2216                         break;
2217                 case 'R':
2218                         {
2219                                 int n;
2220
2221                                 n = hammer_alist_recover(live, 0, 0,
2222                                            live->meta->bm_alist_base_freeblks);
2223                                 if (n < 0)
2224                                         kprintf("recover: error %d\n", -n);
2225                                 else
2226                                         kprintf("recover: %d free\n", n);
2227                         }
2228                         break;
2229                 case '?':
2230                 case 'h':
2231                         puts(
2232                             "p[i][m]    -print (initialized only) (meta-only)\n"
2233                             "a %d       -allocate\n"
2234                             "r %d       -allocate reverse\n"
2235                             "f %x %d    -free\n"
2236                             "R          -recovery a-list\n"
2237                             "h/?        -help"
2238                         );
2239                         break;
2240                 default:
2241                         kprintf("?\n");
2242                         break;
2243                 }
2244         }
2245         return(0);
2246 }
2247
2248 void
2249 panic(const char *ctl, ...)
2250 {
2251         __va_list va;
2252
2253         __va_start(va, ctl);
2254         vfprintf(stderr, ctl, va);
2255         fprintf(stderr, "\n");
2256         __va_end(va);
2257         exit(1);
2258 }
2259
2260 #endif
2261