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 100