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 99