1 /* 2 * Copyright (c) 2007,2011 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 /* 35 * Implements a power-of-2 aligned and sized resource bitmap. The 36 * number of blocks need not be a power-of-2, but any allocation which is 37 * not a power of 2 will first allocate the nearest higher power of 2 38 * and then free the remainder. Frees have no alignment requirements 39 * and piecemeal frees are allowed. 40 * 41 * alist = alist_create(blocks, malloctype) 42 * (void) alist_init(alist, blocks, records, nrecords) 43 * (void) alist_destroy(alist, malloctype) 44 * blkno = alist_alloc(alist, start, 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 typedef u_int32_t alist_bmap_t; 71 typedef u_int32_t alist_blk_t; 72 73 /* 74 * almeta and alist_bmap_t MUST be a power of 2 in size. 75 */ 76 typedef struct almeta { 77 alist_bmap_t bm_bitmap; /* bitmap if we are a leaf */ 78 alist_blk_t bm_bighint; /* biggest contiguous block hint*/ 79 } almeta_t; 80 81 typedef struct alist { 82 alist_blk_t bl_blocks; /* area of coverage */ 83 alist_blk_t bl_radix; /* coverage radix */ 84 alist_blk_t bl_skip; /* starting skip */ 85 alist_blk_t bl_free; /* number of free blocks */ 86 almeta_t *bl_root; /* root of radix tree */ 87 alist_blk_t bl_rootblks; /* #blocks handled by tree */ 88 } *alist_t; 89 90 #define ALIST_META_RADIX (sizeof(alist_bmap_t)*4) /* 16 */ 91 #define ALIST_BMAP_RADIX (sizeof(alist_bmap_t)*8) /* 32 */ 92 #define ALIST_BLOCK_NONE ((alist_blk_t)-1) 93 94 /* 95 * When alist_init() is used the caller can pre-allocate the records 96 * array. 97 */ 98 #define ALIST_RECORDS_65536 2193 99 #define ALIST_RECORDS_1048576 34961 100 101 extern alist_t alist_create(alist_blk_t blocks, struct malloc_type *mtype); 102 extern void alist_init(alist_t alist, alist_blk_t blocks, 103 almeta_t *records, alist_blk_t nrecords); 104 extern void alist_destroy(alist_t alist, struct malloc_type *mtype); 105 extern alist_blk_t alist_alloc(alist_t alist, alist_blk_t start, 106 alist_blk_t count); 107 extern void alist_free(alist_t alist, alist_blk_t blkno, alist_blk_t count); 108 extern alist_blk_t alist_free_info(alist_t bl, alist_blk_t *startp, 109 alist_blk_t *countp); 110 extern void alist_print(alist_t alist); 111 112 #endif /* _SYS_ALIST_H_ */ 113 114