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/sys/alist.h

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) 2007,2011 The DragonFly Project.  All rights reserved.
    3  * 
    4  * This code is derived from software contributed to The DragonFly Project
    5  * by Matthew Dillon <dillon@backplane.com>
    6  * 
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 
   11  * 1. Redistributions of source code must retain the above copyright
   12  *    notice, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in
   15  *    the documentation and/or other materials provided with the
   16  *    distribution.
   17  * 3. Neither the name of The DragonFly Project nor the names of its
   18  *    contributors may be used to endorse or promote products derived
   19  *    from this software without specific, prior written permission.
   20  * 
   21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
   25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
   29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32  * SUCH DAMAGE.
   33  */
   34 /*
   35  * Implements a power-of-2 aligned and sized resource bitmap.  The
   36  * number of blocks need not be a power-of-2, but any allocation which is
   37  * not a power of 2 will first allocate the nearest higher power of 2
   38  * and then free the remainder.  Frees have no alignment requirements
   39  * and piecemeal frees are allowed.
   40  *
   41  * alist = alist_create(blocks, malloctype)
   42  * (void)  alist_init(alist, blocks, records, nrecords)
   43  * (void)  alist_destroy(alist, malloctype)
   44  * blkno = alist_alloc(alist, start, count)
   45  * (void)  alist_free(alist, blkno, count)
   46  *
   47  * A radix tree is constructed using radix 16 for the meta nodes and radix 32
   48  * for the leaf nodes.  Each meta node has a 32 bit bitmap using 2 bits
   49  * per radix (32 bits), and each leaf node has a 32 bit bitmap using 1 bit
   50  * per radix.  The 2-bit bit patterns in the meta-node indicate how the
   51  * sub-tree is allocated.
   52  *
   53  *      00      All-allocated
   54  *      01      Partially allocated
   55  *      10      (reserved)
   56  *      11      All-free
   57  *
   58  * Each meta-node and leaf has a biggest-hint field indicating the largest
   59  * possible allocation that can be made in that sub-tree.  The value in
   60  * this field may be too large but will never be too small.
   61  */
   62 
   63 #ifndef _SYS_ALIST_H_
   64 #define _SYS_ALIST_H_
   65 
   66 #ifndef _SYS_TYPES_H_ 
   67 #include <sys/types.h>
   68 #endif
   69 
   70 typedef u_int32_t       alist_bmap_t;
   71 typedef u_int32_t       alist_blk_t;
   72 
   73 /*
   74  * almeta and alist_bmap_t MUST be a power of 2 in size.
   75  */
   76 typedef struct almeta {
   77         alist_bmap_t    bm_bitmap;      /* bitmap if we are a leaf      */
   78         alist_blk_t     bm_bighint;     /* biggest contiguous block hint*/
   79 } almeta_t;
   80 
   81 typedef struct alist {
   82         alist_blk_t     bl_blocks;      /* area of coverage             */
   83         alist_blk_t     bl_radix;       /* coverage radix               */
   84         alist_blk_t     bl_skip;        /* starting skip                */
   85         alist_blk_t     bl_free;        /* number of free blocks        */
   86         almeta_t        *bl_root;       /* root of radix tree           */
   87         alist_blk_t     bl_rootblks;    /* #blocks handled by tree      */
   88 } *alist_t;
   89 
   90 #define ALIST_META_RADIX        (sizeof(alist_bmap_t)*4)        /* 16 */
   91 #define ALIST_BMAP_RADIX        (sizeof(alist_bmap_t)*8)        /* 32 */
   92 #define ALIST_BLOCK_NONE        ((alist_blk_t)-1)
   93 
   94 /*
   95  * When alist_init() is used the caller can pre-allocate the records
   96  * array.
   97  */
   98 #define ALIST_RECORDS_65536     2193
   99 #define ALIST_RECORDS_1048576   34961
  100 
  101 extern alist_t alist_create(alist_blk_t blocks, struct malloc_type *mtype);
  102 extern void alist_init(alist_t alist, alist_blk_t blocks,
  103                                 almeta_t *records, alist_blk_t nrecords);
  104 extern void alist_destroy(alist_t alist, struct malloc_type *mtype);
  105 extern alist_blk_t alist_alloc(alist_t alist, alist_blk_t start,
  106                                 alist_blk_t count);
  107 extern void alist_free(alist_t alist, alist_blk_t blkno, alist_blk_t count);
  108 extern alist_blk_t alist_free_info(alist_t bl, alist_blk_t *startp,
  109                                 alist_blk_t *countp);
  110 extern void alist_print(alist_t alist);
  111 
  112 #endif  /* _SYS_ALIST_H_ */
  113 

Cache object: 622edfa553cc083b0e517e355a72f7f7


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