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.2 2007/10/09 17:18:09 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.  Frees do not have to
  40  * be aligned.
  41  *
  42  * alist = alist_create(blocks, malloctype)
  43  * (void)  alist_destroy(alist, malloctype)
  44  * blkno = alist_alloc(alist, 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 /*
  71  * blmeta and bl_bitmap_t MUST be a power of 2 in size.
  72  */
  73
  74 typedef struct almeta {
  75         u_daddr_t       bm_bitmap;      /* bitmap if we are a leaf      */
  76         daddr_t         bm_bighint;     /* biggest contiguous block hint*/
  77 } almeta_t;
  78
  79 typedef struct alist {
  80         daddr_t         bl_blocks;      /* area of coverage             */
  81         int             bl_radix;       /* coverage radix               */
  82         daddr_t         bl_skip;        /* starting skip                */
  83         daddr_t         bl_free;        /* number of free blocks        */
  84         almeta_t        *bl_root;       /* root of radix tree           */
  85         daddr_t         bl_rootblks;    /* daddr_t blks allocated for tree */
  86 } *alist_t;
  87
  88 #define ALIST_META_RADIX        (sizeof(u_daddr_t)*4)   /* 16 */
  89 #define ALIST_BMAP_RADIX        (sizeof(u_daddr_t)*8)   /* 32 */
  90 #define ALIST_BLOCK_NONE        ((daddr_t)-1)
  91
  92 extern alist_t alist_create(daddr_t blocks, struct malloc_type *mtype);
  93 extern void alist_destroy(alist_t blist, struct malloc_type *mtype);
  94 extern daddr_t alist_alloc(alist_t blist, daddr_t count);
  95 extern void alist_free(alist_t blist, daddr_t blkno, daddr_t count);
  96 extern void alist_print(alist_t blist);
  97
  98 #endif  /* _SYS_ALIST_H_ */
  99