The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_blist.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 1998 Matthew Dillon.  All Rights Reserved.
    3  * Redistribution and use in source and binary forms, with or without
    4  * modification, are permitted provided that the following conditions
    5  * are met:
    6  * 1. Redistributions of source code must retain the above copyright
    7  *    notice, this list of conditions and the following disclaimer.
    8  * 2. Redistributions in binary form must reproduce the above copyright
    9  *    notice, this list of conditions and the following disclaimer in the
   10  *    documentation and/or other materials provided with the distribution.
   11  * 4. Neither the name of the University nor the names of its contributors
   12  *    may be used to endorse or promote products derived from this software
   13  *    without specific prior written permission.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
   16  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
   19  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
   21  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   22  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
   23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   24  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   26  */
   27 /*
   28  * BLIST.C -    Bitmap allocator/deallocator, using a radix tree with hinting
   29  *
   30  *      This module implements a general bitmap allocator/deallocator.  The
   31  *      allocator eats around 2 bits per 'block'.  The module does not
   32  *      try to interpret the meaning of a 'block' other than to return
   33  *      SWAPBLK_NONE on an allocation failure.
   34  *
   35  *      A radix tree controls access to pieces of the bitmap, and includes
   36  *      auxiliary information at each interior node about the availabilty of
   37  *      contiguous free blocks in the subtree rooted at that node.  Two radix
   38  *      constants are involved: one for the size of the bitmaps contained in the
   39  *      leaf nodes (BLIST_BMAP_RADIX), and one for the number of descendents of
   40  *      each of the meta (interior) nodes (BLIST_META_RADIX).  Each subtree is
   41  *      associated with a range of blocks.  The root of any subtree stores a
   42  *      hint field that defines an upper bound on the size of the largest
   43  *      allocation that can begin in the associated block range.  A hint is an
   44  *      upper bound on a potential allocation, but not necessarily a tight upper
   45  *      bound.
   46  *
   47  *      The radix tree also implements two collapsed states for meta nodes:
   48  *      the ALL-ALLOCATED state and the ALL-FREE state.  If a meta node is
   49  *      in either of these two states, all information contained underneath
   50  *      the node is considered stale.  These states are used to optimize
   51  *      allocation and freeing operations.
   52  *
   53  *      The hinting greatly increases code efficiency for allocations while
   54  *      the general radix structure optimizes both allocations and frees.  The
   55  *      radix tree should be able to operate well no matter how much
   56  *      fragmentation there is and no matter how large a bitmap is used.
   57  *
   58  *      The blist code wires all necessary memory at creation time.  Neither
   59  *      allocations nor frees require interaction with the memory subsystem.
   60  *      The non-blocking features of the blist code are used in the swap code
   61  *      (vm/swap_pager.c).
   62  *
   63  *      LAYOUT: The radix tree is laid out recursively using a
   64  *      linear array.  Each meta node is immediately followed (laid out
   65  *      sequentially in memory) by BLIST_META_RADIX lower level nodes.  This
   66  *      is a recursive structure but one that can be easily scanned through
   67  *      a very simple 'skip' calculation.  In order to support large radixes,
   68  *      portions of the tree may reside outside our memory allocation.  We
   69  *      handle this with an early-termination optimization (when bighint is
   70  *      set to -1) on the scan.  The memory allocation is only large enough
   71  *      to cover the number of blocks requested at creation time even if it
   72  *      must be encompassed in larger root-node radix.
   73  *
   74  *      NOTE: the allocator cannot currently allocate more than
   75  *      BLIST_BMAP_RADIX blocks per call.  It will panic with 'allocation too
   76  *      large' if you try.  This is an area that could use improvement.  The
   77  *      radix is large enough that this restriction does not effect the swap
   78  *      system, though.  Currently only the allocation code is affected by
   79  *      this algorithmic unfeature.  The freeing code can handle arbitrary
   80  *      ranges.
   81  *
   82  *      This code can be compiled stand-alone for debugging.
   83  */
   84 
   85 #include <sys/cdefs.h>
   86 __FBSDID("$FreeBSD: releng/11.2/sys/kern/subr_blist.c 331722 2018-03-29 02:50:57Z eadler $");
   87 
   88 #ifdef _KERNEL
   89 
   90 #include <sys/param.h>
   91 #include <sys/systm.h>
   92 #include <sys/lock.h>
   93 #include <sys/kernel.h>
   94 #include <sys/blist.h>
   95 #include <sys/malloc.h>
   96 #include <sys/sbuf.h>
   97 #include <sys/proc.h>
   98 #include <sys/mutex.h>
   99 
  100 #else
  101 
  102 #ifndef BLIST_NO_DEBUG
  103 #define BLIST_DEBUG
  104 #endif
  105 
  106 #include <sys/types.h>
  107 #include <sys/malloc.h>
  108 #include <sys/sbuf.h>
  109 #include <stdio.h>
  110 #include <string.h>
  111 #include <stdlib.h>
  112 #include <stdarg.h>
  113 #include <stdbool.h>
  114 
  115 #define bitcount64(x)   __bitcount64((uint64_t)(x))
  116 #define malloc(a,b,c)   calloc(a, 1)
  117 #define free(a,b)       free(a)
  118 static __inline int imax(int a, int b) { return (a > b ? a : b); }
  119 
  120 #include <sys/blist.h>
  121 
  122 void panic(const char *ctl, ...);
  123 
  124 #endif
  125 
  126 /*
  127  * static support functions
  128  */
  129 static daddr_t  blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
  130 static daddr_t  blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_t count,
  131                     u_daddr_t radix);
  132 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
  133 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
  134                     u_daddr_t radix);
  135 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
  136                     blist_t dest, daddr_t count);
  137 static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);
  138 static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count,
  139                     u_daddr_t radix);
  140 static daddr_t  blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count);
  141 #ifndef _KERNEL
  142 static void     blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
  143                     int tab);
  144 #endif
  145 
  146 #ifdef _KERNEL
  147 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
  148 #endif
  149 
  150 _Static_assert(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0,
  151     "radix divisibility error");
  152 #define BLIST_BMAP_MASK (BLIST_BMAP_RADIX - 1)
  153 #define BLIST_META_MASK (BLIST_META_RADIX - 1)
  154 
  155 /*
  156  * For a subtree that can represent the state of up to 'radix' blocks, the
  157  * number of leaf nodes of the subtree is L=radix/BLIST_BMAP_RADIX.  If 'm'
  158  * is short for BLIST_META_RADIX, then for a tree of height h with L=m**h
  159  * leaf nodes, the total number of tree nodes is 1 + m + m**2 + ... + m**h,
  160  * or, equivalently, (m**(h+1)-1)/(m-1).  This quantity is called 'skip'
  161  * in the 'meta' functions that process subtrees.  Since integer division
  162  * discards remainders, we can express this computation as
  163  * skip = (m * m**h) / (m - 1)
  164  * skip = (m * (radix / BLIST_BMAP_RADIX)) / (m - 1)
  165  * and since m divides BLIST_BMAP_RADIX, we can simplify further to
  166  * skip = (radix / (BLIST_BMAP_RADIX / m)) / (m - 1)
  167  * skip = radix / ((BLIST_BMAP_RADIX / m) * (m - 1))
  168  * so that simple integer division by a constant can safely be used for the
  169  * calculation.
  170  */
  171 static inline daddr_t
  172 radix_to_skip(daddr_t radix)
  173 {
  174 
  175         return (radix /
  176             ((BLIST_BMAP_RADIX / BLIST_META_RADIX) * BLIST_META_MASK));
  177 }
  178 
  179 /*
  180  * Use binary search, or a faster method, to find the 1 bit in a u_daddr_t.
  181  * Assumes that the argument has only one bit set.
  182  */
  183 static inline int
  184 bitpos(u_daddr_t mask)
  185 {
  186         int hi, lo, mid;
  187 
  188         switch (sizeof(mask)) {
  189 #ifdef HAVE_INLINE_FFSLL
  190         case sizeof(long long):
  191                 return (ffsll(mask) - 1);
  192 #endif
  193         default:
  194                 lo = 0;
  195                 hi = BLIST_BMAP_RADIX;
  196                 while (lo + 1 < hi) {
  197                         mid = (lo + hi) >> 1;
  198                         if ((mask >> mid) != 0)
  199                                 lo = mid;
  200                         else
  201                                 hi = mid;
  202                 }
  203                 return (lo);
  204         }
  205 }
  206 
  207 /*
  208  * blist_create() - create a blist capable of handling up to the specified
  209  *                  number of blocks
  210  *
  211  *      blocks - must be greater than 0
  212  *      flags  - malloc flags
  213  *
  214  *      The smallest blist consists of a single leaf node capable of
  215  *      managing BLIST_BMAP_RADIX blocks.
  216  */
  217 blist_t
  218 blist_create(daddr_t blocks, int flags)
  219 {
  220         blist_t bl;
  221         daddr_t nodes, radix;
  222 
  223         /*
  224          * Calculate the radix field used for scanning.
  225          */
  226         radix = BLIST_BMAP_RADIX;
  227         while (radix < blocks) {
  228                 radix *= BLIST_META_RADIX;
  229         }
  230         nodes = 1 + blst_radix_init(NULL, radix, blocks);
  231 
  232         bl = malloc(sizeof(struct blist), M_SWAP, flags);
  233         if (bl == NULL)
  234                 return (NULL);
  235 
  236         bl->bl_blocks = blocks;
  237         bl->bl_radix = radix;
  238         bl->bl_cursor = 0;
  239         bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags);
  240         if (bl->bl_root == NULL) {
  241                 free(bl, M_SWAP);
  242                 return (NULL);
  243         }
  244         blst_radix_init(bl->bl_root, radix, blocks);
  245 
  246 #if defined(BLIST_DEBUG)
  247         printf(
  248                 "BLIST representing %lld blocks (%lld MB of swap)"
  249                 ", requiring %lldK of ram\n",
  250                 (long long)bl->bl_blocks,
  251                 (long long)bl->bl_blocks * 4 / 1024,
  252                 (long long)(nodes * sizeof(blmeta_t) + 1023) / 1024
  253         );
  254         printf("BLIST raw radix tree contains %lld records\n",
  255             (long long)nodes);
  256 #endif
  257 
  258         return (bl);
  259 }
  260 
  261 void
  262 blist_destroy(blist_t bl)
  263 {
  264         free(bl->bl_root, M_SWAP);
  265         free(bl, M_SWAP);
  266 }
  267 
  268 /*
  269  * blist_alloc() -   reserve space in the block bitmap.  Return the base
  270  *                   of a contiguous region or SWAPBLK_NONE if space could
  271  *                   not be allocated.
  272  */
  273 daddr_t
  274 blist_alloc(blist_t bl, daddr_t count)
  275 {
  276         daddr_t blk;
  277 
  278         /*
  279          * This loop iterates at most twice.  An allocation failure in the
  280          * first iteration leads to a second iteration only if the cursor was
  281          * non-zero.  When the cursor is zero, an allocation failure will
  282          * reduce the hint, stopping further iterations.
  283          */
  284         while (count <= bl->bl_root->bm_bighint) {
  285                 blk = blst_meta_alloc(bl->bl_root, bl->bl_cursor, count,
  286                     bl->bl_radix);
  287                 if (blk != SWAPBLK_NONE) {
  288                         bl->bl_cursor = blk + count;
  289                         if (bl->bl_cursor == bl->bl_blocks)
  290                                 bl->bl_cursor = 0;
  291                         return (blk);
  292                 } else if (bl->bl_cursor != 0)
  293                         bl->bl_cursor = 0;
  294         }
  295         return (SWAPBLK_NONE);
  296 }
  297 
  298 /*
  299  * blist_avail() -      return the number of free blocks.
  300  */
  301 daddr_t
  302 blist_avail(blist_t bl)
  303 {
  304 
  305         if (bl->bl_radix == BLIST_BMAP_RADIX)
  306                 return (bitcount64(bl->bl_root->u.bmu_bitmap));
  307         else
  308                 return (bl->bl_root->u.bmu_avail);
  309 }
  310 
  311 /*
  312  * blist_free() -       free up space in the block bitmap.  Return the base
  313  *                      of a contiguous region.  Panic if an inconsistancy is
  314  *                      found.
  315  */
  316 void
  317 blist_free(blist_t bl, daddr_t blkno, daddr_t count)
  318 {
  319 
  320         blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix);
  321 }
  322 
  323 /*
  324  * blist_fill() -       mark a region in the block bitmap as off-limits
  325  *                      to the allocator (i.e. allocate it), ignoring any
  326  *                      existing allocations.  Return the number of blocks
  327  *                      actually filled that were free before the call.
  328  */
  329 daddr_t
  330 blist_fill(blist_t bl, daddr_t blkno, daddr_t count)
  331 {
  332 
  333         return (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix));
  334 }
  335 
  336 /*
  337  * blist_resize() -     resize an existing radix tree to handle the
  338  *                      specified number of blocks.  This will reallocate
  339  *                      the tree and transfer the previous bitmap to the new
  340  *                      one.  When extending the tree you can specify whether
  341  *                      the new blocks are to left allocated or freed.
  342  */
  343 void
  344 blist_resize(blist_t *pbl, daddr_t count, int freenew, int flags)
  345 {
  346     blist_t newbl = blist_create(count, flags);
  347     blist_t save = *pbl;
  348 
  349     *pbl = newbl;
  350     if (count > save->bl_blocks)
  351             count = save->bl_blocks;
  352     blst_copy(save->bl_root, 0, save->bl_radix, newbl, count);
  353 
  354     /*
  355      * If resizing upwards, should we free the new space or not?
  356      */
  357     if (freenew && count < newbl->bl_blocks) {
  358             blist_free(newbl, count, newbl->bl_blocks - count);
  359     }
  360     blist_destroy(save);
  361 }
  362 
  363 #ifdef BLIST_DEBUG
  364 
  365 /*
  366  * blist_print()    - dump radix tree
  367  */
  368 void
  369 blist_print(blist_t bl)
  370 {
  371         printf("BLIST cursor = %08jx {\n", (uintmax_t)bl->bl_cursor);
  372         blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4);
  373         printf("}\n");
  374 }
  375 
  376 #endif
  377 
  378 static const u_daddr_t fib[] = {
  379         1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
  380         4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811,
  381         514229, 832040, 1346269, 2178309, 3524578,
  382 };
  383 
  384 /*
  385  * Use 'gap' to describe a maximal range of unallocated blocks/bits.
  386  */
  387 struct gap_stats {
  388         daddr_t start;          /* current gap start, or SWAPBLK_NONE */
  389         daddr_t num;            /* number of gaps observed */
  390         daddr_t max;            /* largest gap size */
  391         daddr_t avg;            /* average gap size */
  392         daddr_t err;            /* sum - num * avg */
  393         daddr_t histo[nitems(fib)]; /* # gaps in each size range */
  394         int     max_bucket;     /* last histo elt with nonzero val */
  395 };
  396 
  397 /*
  398  * gap_stats_counting()    - is the state 'counting 1 bits'?
  399  *                           or 'skipping 0 bits'?
  400  */
  401 static inline bool
  402 gap_stats_counting(const struct gap_stats *stats)
  403 {
  404 
  405         return (stats->start != SWAPBLK_NONE);
  406 }
  407 
  408 /*
  409  * init_gap_stats()    - initialize stats on gap sizes
  410  */
  411 static inline void
  412 init_gap_stats(struct gap_stats *stats)
  413 {
  414 
  415         bzero(stats, sizeof(*stats));
  416         stats->start = SWAPBLK_NONE;
  417 }
  418 
  419 /*
  420  * update_gap_stats()    - update stats on gap sizes
  421  */
  422 static void
  423 update_gap_stats(struct gap_stats *stats, daddr_t posn)
  424 {
  425         daddr_t size;
  426         int hi, lo, mid;
  427 
  428         if (!gap_stats_counting(stats)) {
  429                 stats->start = posn;
  430                 return;
  431         }
  432         size = posn - stats->start;
  433         stats->start = SWAPBLK_NONE;
  434         if (size > stats->max)
  435                 stats->max = size;
  436 
  437         /*
  438          * Find the fibonacci range that contains size,
  439          * expecting to find it in an early range.
  440          */
  441         lo = 0;
  442         hi = 1;
  443         while (hi < nitems(fib) && fib[hi] <= size) {
  444                 lo = hi;
  445                 hi *= 2;
  446         }
  447         if (hi >= nitems(fib))
  448                 hi = nitems(fib);
  449         while (lo + 1 != hi) {
  450                 mid = (lo + hi) >> 1;
  451                 if (fib[mid] <= size)
  452                         lo = mid;
  453                 else
  454                         hi = mid;
  455         }
  456         stats->histo[lo]++;
  457         if (lo > stats->max_bucket)
  458                 stats->max_bucket = lo;
  459         stats->err += size - stats->avg;
  460         stats->num++;
  461         stats->avg += stats->err / stats->num;
  462         stats->err %= stats->num;
  463 }
  464 
  465 /*
  466  * dump_gap_stats()    - print stats on gap sizes
  467  */
  468 static inline void
  469 dump_gap_stats(const struct gap_stats *stats, struct sbuf *s)
  470 {
  471         int i;
  472 
  473         sbuf_printf(s, "number of maximal free ranges: %jd\n",
  474             (intmax_t)stats->num);
  475         sbuf_printf(s, "largest free range: %jd\n", (intmax_t)stats->max);
  476         sbuf_printf(s, "average maximal free range size: %jd\n",
  477             (intmax_t)stats->avg);
  478         sbuf_printf(s, "number of maximal free ranges of different sizes:\n");
  479         sbuf_printf(s, "               count  |  size range\n");
  480         sbuf_printf(s, "               -----  |  ----------\n");
  481         for (i = 0; i < stats->max_bucket; i++) {
  482                 if (stats->histo[i] != 0) {
  483                         sbuf_printf(s, "%20jd  |  ",
  484                             (intmax_t)stats->histo[i]);
  485                         if (fib[i] != fib[i + 1] - 1)
  486                                 sbuf_printf(s, "%jd to %jd\n", (intmax_t)fib[i],
  487                                     (intmax_t)fib[i + 1] - 1);
  488                         else
  489                                 sbuf_printf(s, "%jd\n", (intmax_t)fib[i]);
  490                 }
  491         }
  492         sbuf_printf(s, "%20jd  |  ", (intmax_t)stats->histo[i]);
  493         if (stats->histo[i] > 1)
  494                 sbuf_printf(s, "%jd to %jd\n", (intmax_t)fib[i],
  495                     (intmax_t)stats->max);
  496         else
  497                 sbuf_printf(s, "%jd\n", (intmax_t)stats->max);
  498 }
  499 
  500 /*
  501  * blist_stats()    - dump radix tree stats
  502  */
  503 void
  504 blist_stats(blist_t bl, struct sbuf *s)
  505 {
  506         struct gap_stats gstats;
  507         struct gap_stats *stats = &gstats;
  508         daddr_t i, nodes, radix;
  509         u_daddr_t bit, diff, mask;
  510 
  511         init_gap_stats(stats);
  512         nodes = 0;
  513         i = bl->bl_radix;
  514         while (i < bl->bl_radix + bl->bl_blocks) {
  515                 /*
  516                  * Find max size subtree starting at i.
  517                  */
  518                 radix = BLIST_BMAP_RADIX;
  519                 while (((i / radix) & BLIST_META_MASK) == 0)
  520                         radix *= BLIST_META_RADIX;
  521 
  522                 /*
  523                  * Check for skippable subtrees starting at i.
  524                  */
  525                 while (radix > BLIST_BMAP_RADIX) {
  526                         if (bl->bl_root[nodes].u.bmu_avail == 0) {
  527                                 if (gap_stats_counting(stats))
  528                                         update_gap_stats(stats, i);
  529                                 break;
  530                         }
  531                         if (bl->bl_root[nodes].u.bmu_avail == radix) {
  532                                 if (!gap_stats_counting(stats))
  533                                         update_gap_stats(stats, i);
  534                                 break;
  535                         }
  536 
  537                         /*
  538                          * Skip subtree root.
  539                          */
  540                         nodes++;
  541                         radix /= BLIST_META_RADIX;
  542                 }
  543                 if (radix == BLIST_BMAP_RADIX) {
  544                         /*
  545                          * Scan leaf.
  546                          */
  547                         mask = bl->bl_root[nodes].u.bmu_bitmap;
  548                         diff = mask ^ (mask << 1);
  549                         if (gap_stats_counting(stats))
  550                                 diff ^= 1;
  551                         while (diff != 0) {
  552                                 bit = diff & -diff;
  553                                 update_gap_stats(stats, i + bitpos(bit));
  554                                 diff ^= bit;
  555                         }
  556                 }
  557                 nodes += radix_to_skip(radix);
  558                 i += radix;
  559         }
  560         update_gap_stats(stats, i);
  561         dump_gap_stats(stats, s);
  562 }
  563 
  564 /************************************************************************
  565  *                        ALLOCATION SUPPORT FUNCTIONS                  *
  566  ************************************************************************
  567  *
  568  *      These support functions do all the actual work.  They may seem
  569  *      rather longish, but that's because I've commented them up.  The
  570  *      actual code is straight forward.
  571  *
  572  */
  573 
  574 /*
  575  * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
  576  *
  577  *      This is the core of the allocator and is optimized for the
  578  *      BLIST_BMAP_RADIX block allocation case.  Otherwise, execution
  579  *      time is proportional to log2(count) + bitpos time.
  580  */
  581 static daddr_t
  582 blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count)
  583 {
  584         u_daddr_t mask;
  585         int count1, hi, lo, num_shifts, range1, range_ext;
  586 
  587         range1 = 0;
  588         count1 = count - 1;
  589         num_shifts = fls(count1);
  590         mask = scan->u.bmu_bitmap;
  591         while ((-mask & ~mask) != 0 && num_shifts > 0) {
  592                 /*
  593                  * If bit i is set in mask, then bits in [i, i+range1] are set
  594                  * in scan->u.bmu_bitmap.  The value of range1 is equal to
  595                  * count1 >> num_shifts.  Grow range and reduce num_shifts to 0,
  596                  * while preserving these invariants.  The updates to mask leave
  597                  * fewer bits set, but each bit that remains set represents a
  598                  * longer string of consecutive bits set in scan->u.bmu_bitmap.
  599                  * If more updates to mask cannot clear more bits, because mask
  600                  * is partitioned with all 0 bits preceding all 1 bits, the loop
  601                  * terminates immediately.
  602                  */
  603                 num_shifts--;
  604                 range_ext = range1 + ((count1 >> num_shifts) & 1);
  605                 /*
  606                  * mask is a signed quantity for the shift because when it is
  607                  * shifted right, the sign bit should copied; when the last
  608                  * block of the leaf is free, pretend, for a while, that all the
  609                  * blocks that follow it are also free.
  610                  */
  611                 mask &= (daddr_t)mask >> range_ext;
  612                 range1 += range_ext;
  613         }
  614         if (mask == 0) {
  615                 /*
  616                  * Update bighint.  There is no allocation bigger than range1
  617                  * starting in this leaf.
  618                  */
  619                 scan->bm_bighint = range1;
  620                 return (SWAPBLK_NONE);
  621         }
  622 
  623         /* Discard any candidates that appear before blk. */
  624         mask &= (u_daddr_t)-1 << (blk & BLIST_BMAP_MASK);
  625         if (mask == 0)
  626                 return (SWAPBLK_NONE);
  627 
  628         /*
  629          * The least significant set bit in mask marks the start of the first
  630          * available range of sufficient size.  Clear all the bits but that one,
  631          * and then find its position.
  632          */
  633         mask &= -mask;
  634         lo = bitpos(mask);
  635 
  636         hi = lo + count;
  637         if (hi > BLIST_BMAP_RADIX) {
  638                 /*
  639                  * An allocation within this leaf is impossible, so a successful
  640                  * allocation depends on the next leaf providing some of the blocks.
  641                  */
  642                 if (((blk / BLIST_BMAP_RADIX + 1) & BLIST_META_MASK) == 0) {
  643                         /*
  644                          * The next leaf has a different meta-node parent, so it
  645                          * is not necessarily initialized.  Update bighint,
  646                          * comparing the range found at the end of mask to the
  647                          * largest earlier range that could have been made to
  648                          * vanish in the initial processing of mask.
  649                          */
  650                         scan->bm_bighint = imax(BLIST_BMAP_RADIX - lo, range1);
  651                         return (SWAPBLK_NONE);
  652                 }
  653                 hi -= BLIST_BMAP_RADIX;
  654                 if (((scan[1].u.bmu_bitmap + 1) & ~((u_daddr_t)-1 << hi)) != 0) {
  655                         /*
  656                          * The next leaf doesn't have enough free blocks at the
  657                          * beginning to complete the spanning allocation.  The
  658                          * hint cannot be updated, because the same allocation
  659                          * request could be satisfied later, by this leaf, if
  660                          * the state of the next leaf changes, and without any
  661                          * changes to this leaf.
  662                          */
  663                         return (SWAPBLK_NONE);
  664                 }
  665                 /* Clear the first 'hi' bits in the next leaf, allocating them. */
  666                 scan[1].u.bmu_bitmap &= (u_daddr_t)-1 << hi;
  667                 hi = BLIST_BMAP_RADIX;
  668         }
  669 
  670         /* Set the bits of mask at position 'lo' and higher. */
  671         mask = -mask;
  672         if (hi == BLIST_BMAP_RADIX) {
  673                 /*
  674                  * Update bighint.  There is no allocation bigger than range1
  675                  * available in this leaf after this allocation completes.
  676                  */
  677                 scan->bm_bighint = range1;
  678         } else {
  679                 /* Clear the bits of mask at position 'hi' and higher. */
  680                 mask &= (u_daddr_t)-1 >> (BLIST_BMAP_RADIX - hi);
  681                 /* If this allocation uses all the bits, clear the hint. */
  682                 if (mask == scan->u.bmu_bitmap)
  683                         scan->bm_bighint = 0;
  684         }
  685         /* Clear the allocated bits from this leaf. */
  686         scan->u.bmu_bitmap &= ~mask;
  687         return ((blk & ~BLIST_BMAP_MASK) + lo);
  688 }
  689 
  690 /*
  691  * blist_meta_alloc() - allocate at a meta in the radix tree.
  692  *
  693  *      Attempt to allocate at a meta node.  If we can't, we update
  694  *      bighint and return a failure.  Updating bighint optimize future
  695  *      calls that hit this node.  We have to check for our collapse cases
  696  *      and we have a few optimizations strewn in as well.
  697  */
  698 static daddr_t
  699 blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_t count, u_daddr_t radix)
  700 {
  701         daddr_t blk, i, next_skip, r, skip;
  702         int child;
  703         bool scan_from_start;
  704 
  705         if (radix == BLIST_BMAP_RADIX)
  706                 return (blst_leaf_alloc(scan, cursor, count));
  707         if (scan->u.bmu_avail < count) {
  708                 /*
  709                  * The meta node's hint must be too large if the allocation
  710                  * exceeds the number of free blocks.  Reduce the hint, and
  711                  * return failure.
  712                  */
  713                 scan->bm_bighint = scan->u.bmu_avail;
  714                 return (SWAPBLK_NONE);
  715         }
  716         blk = cursor & -radix;
  717         skip = radix_to_skip(radix);
  718         next_skip = skip / BLIST_META_RADIX;
  719 
  720         /*
  721          * An ALL-FREE meta node requires special handling before allocating
  722          * any of its blocks.
  723          */
  724         if (scan->u.bmu_avail == radix) {
  725                 radix /= BLIST_META_RADIX;
  726 
  727                 /*
  728                  * Reinitialize each of the meta node's children.  An ALL-FREE
  729                  * meta node cannot have a terminator in any subtree.
  730                  */
  731                 for (i = 1; i < skip; i += next_skip) {
  732                         if (next_skip == 1)
  733                                 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
  734                         else
  735                                 scan[i].u.bmu_avail = radix;
  736                         scan[i].bm_bighint = radix;
  737                 }
  738         } else {
  739                 radix /= BLIST_META_RADIX;
  740         }
  741 
  742         if (count > radix) {
  743                 /*
  744                  * The allocation exceeds the number of blocks that are
  745                  * managed by a subtree of this meta node.
  746                  */
  747                 panic("allocation too large");
  748         }
  749         scan_from_start = cursor == blk;
  750         child = (cursor - blk) / radix;
  751         blk += child * radix;
  752         for (i = 1 + child * next_skip; i < skip; i += next_skip) {
  753                 if (count <= scan[i].bm_bighint) {
  754                         /*
  755                          * The allocation might fit beginning in the i'th subtree.
  756                          */
  757                         r = blst_meta_alloc(&scan[i],
  758                             cursor > blk ? cursor : blk, count, radix);
  759                         if (r != SWAPBLK_NONE) {
  760                                 scan->u.bmu_avail -= count;
  761                                 return (r);
  762                         }
  763                 } else if (scan[i].bm_bighint == (daddr_t)-1) {
  764                         /*
  765                          * Terminator
  766                          */
  767                         break;
  768                 }
  769                 blk += radix;
  770         }
  771 
  772         /*
  773          * We couldn't allocate count in this subtree, update bighint.
  774          */
  775         if (scan_from_start && scan->bm_bighint >= count)
  776                 scan->bm_bighint = count - 1;
  777 
  778         return (SWAPBLK_NONE);
  779 }
  780 
  781 /*
  782  * BLST_LEAF_FREE() -   free allocated block from leaf bitmap
  783  *
  784  */
  785 static void
  786 blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
  787 {
  788         u_daddr_t mask;
  789         int n;
  790 
  791         /*
  792          * free some data in this bitmap
  793          * mask=0000111111111110000
  794          *          \_________/\__/
  795          *              count   n
  796          */
  797         n = blk & BLIST_BMAP_MASK;
  798         mask = ((u_daddr_t)-1 << n) &
  799             ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
  800         if (scan->u.bmu_bitmap & mask)
  801                 panic("freeing free block");
  802         scan->u.bmu_bitmap |= mask;
  803 
  804         /*
  805          * We could probably do a better job here.  We are required to make
  806          * bighint at least as large as the biggest contiguous block of
  807          * data.  If we just shoehorn it, a little extra overhead will
  808          * be incured on the next allocation (but only that one typically).
  809          */
  810         scan->bm_bighint = BLIST_BMAP_RADIX;
  811 }
  812 
  813 /*
  814  * BLST_META_FREE() - free allocated blocks from radix tree meta info
  815  *
  816  *      This support routine frees a range of blocks from the bitmap.
  817  *      The range must be entirely enclosed by this radix node.  If a
  818  *      meta node, we break the range down recursively to free blocks
  819  *      in subnodes (which means that this code can free an arbitrary
  820  *      range whereas the allocation code cannot allocate an arbitrary
  821  *      range).
  822  */
  823 static void
  824 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, u_daddr_t radix)
  825 {
  826         daddr_t blk, i, next_skip, skip, v;
  827         int child;
  828 
  829         if (scan->bm_bighint == (daddr_t)-1)
  830                 panic("freeing invalid range");
  831         if (radix == BLIST_BMAP_RADIX)
  832                 return (blst_leaf_free(scan, freeBlk, count));
  833         skip = radix_to_skip(radix);
  834         next_skip = skip / BLIST_META_RADIX;
  835 
  836         if (scan->u.bmu_avail == 0) {
  837                 /*
  838                  * ALL-ALLOCATED special case, with possible
  839                  * shortcut to ALL-FREE special case.
  840                  */
  841                 scan->u.bmu_avail = count;
  842                 scan->bm_bighint = count;
  843 
  844                 if (count != radix)  {
  845                         for (i = 1; i < skip; i += next_skip) {
  846                                 if (scan[i].bm_bighint == (daddr_t)-1)
  847                                         break;
  848                                 scan[i].bm_bighint = 0;
  849                                 if (next_skip == 1) {
  850                                         scan[i].u.bmu_bitmap = 0;
  851                                 } else {
  852                                         scan[i].u.bmu_avail = 0;
  853                                 }
  854                         }
  855                         /* fall through */
  856                 }
  857         } else {
  858                 scan->u.bmu_avail += count;
  859                 /* scan->bm_bighint = radix; */
  860         }
  861 
  862         /*
  863          * ALL-FREE special case.
  864          */
  865 
  866         if (scan->u.bmu_avail == radix)
  867                 return;
  868         if (scan->u.bmu_avail > radix)
  869                 panic("blst_meta_free: freeing already free blocks (%lld) %lld/%lld",
  870                     (long long)count, (long long)scan->u.bmu_avail,
  871                     (long long)radix);
  872 
  873         /*
  874          * Break the free down into its components
  875          */
  876 
  877         blk = freeBlk & -radix;
  878         radix /= BLIST_META_RADIX;
  879 
  880         child = (freeBlk - blk) / radix;
  881         blk += child * radix;
  882         i = 1 + child * next_skip;
  883         while (i < skip && blk < freeBlk + count) {
  884                 v = blk + radix - freeBlk;
  885                 if (v > count)
  886                         v = count;
  887                 blst_meta_free(&scan[i], freeBlk, v, radix);
  888                 if (scan->bm_bighint < scan[i].bm_bighint)
  889                         scan->bm_bighint = scan[i].bm_bighint;
  890                 count -= v;
  891                 freeBlk += v;
  892                 blk += radix;
  893                 i += next_skip;
  894         }
  895 }
  896 
  897 /*
  898  * BLIST_RADIX_COPY() - copy one radix tree to another
  899  *
  900  *      Locates free space in the source tree and frees it in the destination
  901  *      tree.  The space may not already be free in the destination.
  902  */
  903 static void
  904 blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest,
  905     daddr_t count)
  906 {
  907         daddr_t i, next_skip, skip;
  908 
  909         /*
  910          * Leaf node
  911          */
  912 
  913         if (radix == BLIST_BMAP_RADIX) {
  914                 u_daddr_t v = scan->u.bmu_bitmap;
  915 
  916                 if (v == (u_daddr_t)-1) {
  917                         blist_free(dest, blk, count);
  918                 } else if (v != 0) {
  919                         int i;
  920 
  921                         for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) {
  922                                 if (v & ((u_daddr_t)1 << i))
  923                                         blist_free(dest, blk + i, 1);
  924                         }
  925                 }
  926                 return;
  927         }
  928 
  929         /*
  930          * Meta node
  931          */
  932 
  933         if (scan->u.bmu_avail == 0) {
  934                 /*
  935                  * Source all allocated, leave dest allocated
  936                  */
  937                 return;
  938         }
  939         if (scan->u.bmu_avail == radix) {
  940                 /*
  941                  * Source all free, free entire dest
  942                  */
  943                 if (count < radix)
  944                         blist_free(dest, blk, count);
  945                 else
  946                         blist_free(dest, blk, radix);
  947                 return;
  948         }
  949 
  950 
  951         skip = radix_to_skip(radix);
  952         next_skip = skip / BLIST_META_RADIX;
  953         radix /= BLIST_META_RADIX;
  954 
  955         for (i = 1; count && i < skip; i += next_skip) {
  956                 if (scan[i].bm_bighint == (daddr_t)-1)
  957                         break;
  958 
  959                 if (count >= radix) {
  960                         blst_copy(&scan[i], blk, radix, dest, radix);
  961                         count -= radix;
  962                 } else {
  963                         if (count) {
  964                                 blst_copy(&scan[i], blk, radix, dest, count);
  965                         }
  966                         count = 0;
  967                 }
  968                 blk += radix;
  969         }
  970 }
  971 
  972 /*
  973  * BLST_LEAF_FILL() -   allocate specific blocks in leaf bitmap
  974  *
  975  *      This routine allocates all blocks in the specified range
  976  *      regardless of any existing allocations in that range.  Returns
  977  *      the number of blocks allocated by the call.
  978  */
  979 static daddr_t
  980 blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
  981 {
  982         daddr_t nblks;
  983         u_daddr_t mask;
  984         int n;
  985 
  986         n = blk & BLIST_BMAP_MASK;
  987         mask = ((u_daddr_t)-1 << n) &
  988             ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
  989 
  990         /* Count the number of blocks that we are allocating. */
  991         nblks = bitcount64(scan->u.bmu_bitmap & mask);
  992 
  993         scan->u.bmu_bitmap &= ~mask;
  994         return (nblks);
  995 }
  996 
  997 /*
  998  * BLIST_META_FILL() -  allocate specific blocks at a meta node
  999  *
 1000  *      This routine allocates the specified range of blocks,
 1001  *      regardless of any existing allocations in the range.  The
 1002  *      range must be within the extent of this node.  Returns the
 1003  *      number of blocks allocated by the call.
 1004  */
 1005 static daddr_t
 1006 blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, u_daddr_t radix)
 1007 {
 1008         daddr_t blk, i, nblks, next_skip, skip, v;
 1009         int child;
 1010 
 1011         if (scan->bm_bighint == (daddr_t)-1)
 1012                 panic("filling invalid range");
 1013         if (count > radix) {
 1014                 /*
 1015                  * The allocation exceeds the number of blocks that are
 1016                  * managed by this node.
 1017                  */
 1018                 panic("fill too large");
 1019         }
 1020         if (radix == BLIST_BMAP_RADIX)
 1021                 return (blst_leaf_fill(scan, allocBlk, count));
 1022         if (count == radix || scan->u.bmu_avail == 0)  {
 1023                 /*
 1024                  * ALL-ALLOCATED special case
 1025                  */
 1026                 nblks = scan->u.bmu_avail;
 1027                 scan->u.bmu_avail = 0;
 1028                 scan->bm_bighint = 0;
 1029                 return (nblks);
 1030         }
 1031         skip = radix_to_skip(radix);
 1032         next_skip = skip / BLIST_META_RADIX;
 1033         blk = allocBlk & -radix;
 1034 
 1035         /*
 1036          * An ALL-FREE meta node requires special handling before allocating
 1037          * any of its blocks.
 1038          */
 1039         if (scan->u.bmu_avail == radix) {
 1040                 radix /= BLIST_META_RADIX;
 1041 
 1042                 /*
 1043                  * Reinitialize each of the meta node's children.  An ALL-FREE
 1044                  * meta node cannot have a terminator in any subtree.
 1045                  */
 1046                 for (i = 1; i < skip; i += next_skip) {
 1047                         if (next_skip == 1)
 1048                                 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 1049                         else
 1050                                 scan[i].u.bmu_avail = radix;
 1051                         scan[i].bm_bighint = radix;
 1052                 }
 1053         } else {
 1054                 radix /= BLIST_META_RADIX;
 1055         }
 1056 
 1057         nblks = 0;
 1058         child = (allocBlk - blk) / radix;
 1059         blk += child * radix;
 1060         i = 1 + child * next_skip;
 1061         while (i < skip && blk < allocBlk + count) {
 1062                 v = blk + radix - allocBlk;
 1063                 if (v > count)
 1064                         v = count;
 1065                 nblks += blst_meta_fill(&scan[i], allocBlk, v, radix);
 1066                 count -= v;
 1067                 allocBlk += v;
 1068                 blk += radix;
 1069                 i += next_skip;
 1070         }
 1071         scan->u.bmu_avail -= nblks;
 1072         return (nblks);
 1073 }
 1074 
 1075 /*
 1076  * BLST_RADIX_INIT() - initialize radix tree
 1077  *
 1078  *      Initialize our meta structures and bitmaps and calculate the exact
 1079  *      amount of space required to manage 'count' blocks - this space may
 1080  *      be considerably less than the calculated radix due to the large
 1081  *      RADIX values we use.
 1082  */
 1083 static daddr_t
 1084 blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count)
 1085 {
 1086         daddr_t i, memindex, next_skip, skip;
 1087 
 1088         memindex = 0;
 1089 
 1090         /*
 1091          * Leaf node
 1092          */
 1093 
 1094         if (radix == BLIST_BMAP_RADIX) {
 1095                 if (scan) {
 1096                         scan->bm_bighint = 0;
 1097                         scan->u.bmu_bitmap = 0;
 1098                 }
 1099                 return (memindex);
 1100         }
 1101 
 1102         /*
 1103          * Meta node.  If allocating the entire object we can special
 1104          * case it.  However, we need to figure out how much memory
 1105          * is required to manage 'count' blocks, so we continue on anyway.
 1106          */
 1107 
 1108         if (scan) {
 1109                 scan->bm_bighint = 0;
 1110                 scan->u.bmu_avail = 0;
 1111         }
 1112 
 1113         skip = radix_to_skip(radix);
 1114         next_skip = skip / BLIST_META_RADIX;
 1115         radix /= BLIST_META_RADIX;
 1116 
 1117         for (i = 1; i < skip; i += next_skip) {
 1118                 if (count >= radix) {
 1119                         /*
 1120                          * Allocate the entire object
 1121                          */
 1122                         memindex = i +
 1123                             blst_radix_init(((scan) ? &scan[i] : NULL), radix,
 1124                             radix);
 1125                         count -= radix;
 1126                 } else if (count > 0) {
 1127                         /*
 1128                          * Allocate a partial object
 1129                          */
 1130                         memindex = i +
 1131                             blst_radix_init(((scan) ? &scan[i] : NULL), radix,
 1132                             count);
 1133                         count = 0;
 1134                 } else {
 1135                         /*
 1136                          * Add terminator and break out.  Make terminator bitmap
 1137                          * zero to avoid a spanning leaf allocation that
 1138                          * includes the terminator.
 1139                          */
 1140                         if (scan) {
 1141                                 scan[i].bm_bighint = (daddr_t)-1;
 1142                                 scan[i].u.bmu_bitmap = 0;
 1143                         }
 1144                         break;
 1145                 }
 1146         }
 1147         if (memindex < i)
 1148                 memindex = i;
 1149         return (memindex);
 1150 }
 1151 
 1152 #ifdef BLIST_DEBUG
 1153 
 1154 static void
 1155 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
 1156 {
 1157         daddr_t i, next_skip, skip;
 1158 
 1159         if (radix == BLIST_BMAP_RADIX) {
 1160                 printf(
 1161                     "%*.*s(%08llx,%lld): bitmap %016llx big=%lld\n",
 1162                     tab, tab, "",
 1163                     (long long)blk, (long long)radix,
 1164                     (long long)scan->u.bmu_bitmap,
 1165                     (long long)scan->bm_bighint
 1166                 );
 1167                 return;
 1168         }
 1169 
 1170         if (scan->u.bmu_avail == 0) {
 1171                 printf(
 1172                     "%*.*s(%08llx,%lld) ALL ALLOCATED\n",
 1173                     tab, tab, "",
 1174                     (long long)blk,
 1175                     (long long)radix
 1176                 );
 1177                 return;
 1178         }
 1179         if (scan->u.bmu_avail == radix) {
 1180                 printf(
 1181                     "%*.*s(%08llx,%lld) ALL FREE\n",
 1182                     tab, tab, "",
 1183                     (long long)blk,
 1184                     (long long)radix
 1185                 );
 1186                 return;
 1187         }
 1188 
 1189         printf(
 1190             "%*.*s(%08llx,%lld): subtree (%lld/%lld) big=%lld {\n",
 1191             tab, tab, "",
 1192             (long long)blk, (long long)radix,
 1193             (long long)scan->u.bmu_avail,
 1194             (long long)radix,
 1195             (long long)scan->bm_bighint
 1196         );
 1197 
 1198         skip = radix_to_skip(radix);
 1199         next_skip = skip / BLIST_META_RADIX;
 1200         radix /= BLIST_META_RADIX;
 1201         tab += 4;
 1202 
 1203         for (i = 1; i < skip; i += next_skip) {
 1204                 if (scan[i].bm_bighint == (daddr_t)-1) {
 1205                         printf(
 1206                             "%*.*s(%08llx,%lld): Terminator\n",
 1207                             tab, tab, "",
 1208                             (long long)blk, (long long)radix
 1209                         );
 1210                         break;
 1211                 }
 1212                 blst_radix_print(&scan[i], blk, radix, tab);
 1213                 blk += radix;
 1214         }
 1215         tab -= 4;
 1216 
 1217         printf(
 1218             "%*.*s}\n",
 1219             tab, tab, ""
 1220         );
 1221 }
 1222 
 1223 #endif
 1224 
 1225 #ifdef BLIST_DEBUG
 1226 
 1227 int
 1228 main(int ac, char **av)
 1229 {
 1230         int size = 1024;
 1231         int i;
 1232         blist_t bl;
 1233         struct sbuf *s;
 1234 
 1235         for (i = 1; i < ac; ++i) {
 1236                 const char *ptr = av[i];
 1237                 if (*ptr != '-') {
 1238                         size = strtol(ptr, NULL, 0);
 1239                         continue;
 1240                 }
 1241                 ptr += 2;
 1242                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
 1243                 exit(1);
 1244         }
 1245         bl = blist_create(size, M_WAITOK);
 1246         blist_free(bl, 0, size);
 1247 
 1248         for (;;) {
 1249                 char buf[1024];
 1250                 long long da = 0;
 1251                 long long count = 0;
 1252 
 1253                 printf("%lld/%lld/%lld> ", (long long)blist_avail(bl),
 1254                     (long long)size, (long long)bl->bl_radix);
 1255                 fflush(stdout);
 1256                 if (fgets(buf, sizeof(buf), stdin) == NULL)
 1257                         break;
 1258                 switch(buf[0]) {
 1259                 case 'r':
 1260                         if (sscanf(buf + 1, "%lld", &count) == 1) {
 1261                                 blist_resize(&bl, count, 1, M_WAITOK);
 1262                         } else {
 1263                                 printf("?\n");
 1264                         }
 1265                 case 'p':
 1266                         blist_print(bl);
 1267                         break;
 1268                 case 's':
 1269                         s = sbuf_new_auto();
 1270                         blist_stats(bl, s);
 1271                         sbuf_finish(s);
 1272                         printf("%s", sbuf_data(s));
 1273                         sbuf_delete(s);
 1274                         break;
 1275                 case 'a':
 1276                         if (sscanf(buf + 1, "%lld", &count) == 1) {
 1277                                 daddr_t blk = blist_alloc(bl, count);
 1278                                 printf("    R=%08llx\n", (long long)blk);
 1279                         } else {
 1280                                 printf("?\n");
 1281                         }
 1282                         break;
 1283                 case 'f':
 1284                         if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) {
 1285                                 blist_free(bl, da, count);
 1286                         } else {
 1287                                 printf("?\n");
 1288                         }
 1289                         break;
 1290                 case 'l':
 1291                         if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) {
 1292                                 printf("    n=%jd\n",
 1293                                     (intmax_t)blist_fill(bl, da, count));
 1294                         } else {
 1295                                 printf("?\n");
 1296                         }
 1297                         break;
 1298                 case '?':
 1299                 case 'h':
 1300                         puts(
 1301                             "p          -print\n"
 1302                             "s          -stats\n"
 1303                             "a %d       -allocate\n"
 1304                             "f %x %d    -free\n"
 1305                             "l %x %d    -fill\n"
 1306                             "r %d       -resize\n"
 1307                             "h/?        -help"
 1308                         );
 1309                         break;
 1310                 default:
 1311                         printf("?\n");
 1312                         break;
 1313                 }
 1314         }
 1315         return(0);
 1316 }
 1317 
 1318 void
 1319 panic(const char *ctl, ...)
 1320 {
 1321         va_list va;
 1322 
 1323         va_start(va, ctl);
 1324         vfprintf(stderr, ctl, va);
 1325         fprintf(stderr, "\n");
 1326         va_end(va);
 1327         exit(1);
 1328 }
 1329 
 1330 #endif

Cache object: 3fbcfcf81bd961062d97be9341081b34


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.