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

Cache object: 4b9a5d7c3c2547b47d0b2572f6d8b8f6


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