sys/sys/alist.h

   1 /*
   2  * Copyright (c) 2007 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  * $DragonFly: src/sys/sys/alist.h,v 1.1 2007/04/09 17:09:58 dillon Exp $
  35  */
  36 /*
  37  * Implements a power-of-2 aligned and sized resource bitmap.  The
  38  * number of blocks need not be a power-of-2, but all allocations must
  39  * be a power of 2 and will be aligned on return.
  40  *
  41  * alist = alist_create(blocks, malloctype)
  42  * (void)  alist_destroy(alist, malloctype)
  43  * blkno = alist_alloc(alist, count)
  44  * (void)  alist_free(alist, blkno, count)
  45  *
  46  * A radix tree is constructed using radix 16 for the meta nodes and radix 32
  47  * for the leaf nodes.  Each meta node has a 32 bit bitmap using 2 bits
  48  * per radix (32 bits), and each leaf node has a 32 bit bitmap using 1 bit
  49  * per radix.  The 2-bit bit patterns in the meta-node indicate how the
  50  * sub-tree is allocated.
  51  *
  52  *      00      All-allocated
  53  *      01      Partially allocated
  54  *      10      (reserved)
  55  *      11      All-free
  56  *
  57  * Each meta-node and leaf has a biggest-hint field indicating the largest
  58  * possible allocation that can be made in that sub-tree.  The value in
  59  * this field may be too large but will never be too small.
  60  */
  61
  62 #ifndef _SYS_ALIST_H_
  63 #define _SYS_ALIST_H_
  64
  65 #ifndef _SYS_TYPES_H_
  66 #include <sys/types.h>
  67 #endif
  68
  69 /*
  70  * blmeta and bl_bitmap_t MUST be a power of 2 in size.
  71  */
  72
  73 typedef struct almeta {
  74         u_daddr_t       bm_bitmap;      /* bitmap if we are a leaf      */
  75         daddr_t         bm_bighint;     /* biggest contiguous block hint*/
  76 } almeta_t;
  77
  78 typedef struct alist {
  79         daddr_t         bl_blocks;      /* area of coverage             */
  80         int             bl_radix;       /* coverage radix               */
  81         daddr_t         bl_skip;        /* starting skip                */
  82         daddr_t         bl_free;        /* number of free blocks        */
  83         almeta_t        *bl_root;       /* root of radix tree           */
  84         daddr_t         bl_rootblks;    /* daddr_t blks allocated for tree */
  85 } *alist_t;
  86
  87 #define ALIST_META_RADIX        (sizeof(u_daddr_t)*4)   /* 16 */
  88 #define ALIST_BMAP_RADIX        (sizeof(u_daddr_t)*8)   /* 32 */
  89 #define ALIST_BLOCK_NONE        ((daddr_t)-1)
  90
  91 extern alist_t alist_create(daddr_t blocks, struct malloc_type *mtype);
  92 extern void alist_destroy(alist_t blist, struct malloc_type *mtype);
  93 extern daddr_t alist_alloc(alist_t blist, daddr_t count);
  94 extern void alist_free(alist_t blist, daddr_t blkno, daddr_t count);
  95 extern void alist_print(alist_t blist);
  96
  97 #endif  /* _SYS_ALIST_H_ */
  98