sys/sys/alist.h

   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