2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sys/sys/alist.h,v 1.2 2007/10/09 17:18:09 dillon Exp $
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
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)
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.
54 * 01 Partially allocated
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.
67 #include <sys/types.h>
71 * blmeta and bl_bitmap_t MUST be a power of 2 in size.
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*/
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 */
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)
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
);
98 #endif /* _SYS_ALIST_H_ */