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

Cache object: 9587ee248736fd7a4b90c2ddaa51646a


[ 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.