subr_blist.c revision 1.6.2.2
1 1.6.2.2 kent /* $NetBSD: subr_blist.c,v 1.6.2.2 2005/04/29 11:29:24 kent Exp $ */ 2 1.6.2.2 kent 3 1.6.2.2 kent /*- 4 1.6.2.2 kent * Copyright (c) 1998 Matthew Dillon. All Rights Reserved. 5 1.6.2.2 kent * Redistribution and use in source and binary forms, with or without 6 1.6.2.2 kent * modification, are permitted provided that the following conditions 7 1.6.2.2 kent * are met: 8 1.6.2.2 kent * 1. Redistributions of source code must retain the above copyright 9 1.6.2.2 kent * notice, this list of conditions and the following disclaimer. 10 1.6.2.2 kent * 2. Redistributions in binary form must reproduce the above copyright 11 1.6.2.2 kent * notice, this list of conditions and the following disclaimer in the 12 1.6.2.2 kent * documentation and/or other materials provided with the distribution. 13 1.6.2.2 kent * 4. Neither the name of the University nor the names of its contributors 14 1.6.2.2 kent * may be used to endorse or promote products derived from this software 15 1.6.2.2 kent * without specific prior written permission. 16 1.6.2.2 kent * 17 1.6.2.2 kent * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 18 1.6.2.2 kent * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 19 1.6.2.2 kent * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 1.6.2.2 kent * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 21 1.6.2.2 kent * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 1.6.2.2 kent * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 23 1.6.2.2 kent * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 1.6.2.2 kent * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 25 1.6.2.2 kent * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 26 1.6.2.2 kent * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 27 1.6.2.2 kent * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 1.6.2.2 kent */ 29 1.6.2.2 kent /* 30 1.6.2.2 kent * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting 31 1.6.2.2 kent * 32 1.6.2.2 kent * This module implements a general bitmap allocator/deallocator. The 33 1.6.2.2 kent * allocator eats around 2 bits per 'block'. The module does not 34 1.6.2.2 kent * try to interpret the meaning of a 'block' other then to return 35 1.6.2.2 kent * BLIST_NONE on an allocation failure. 36 1.6.2.2 kent * 37 1.6.2.2 kent * A radix tree is used to maintain the bitmap. Two radix constants are 38 1.6.2.2 kent * involved: One for the bitmaps contained in the leaf nodes (typically 39 1.6.2.2 kent * 32), and one for the meta nodes (typically 16). Both meta and leaf 40 1.6.2.2 kent * nodes have a hint field. This field gives us a hint as to the largest 41 1.6.2.2 kent * free contiguous range of blocks under the node. It may contain a 42 1.6.2.2 kent * value that is too high, but will never contain a value that is too 43 1.6.2.2 kent * low. When the radix tree is searched, allocation failures in subtrees 44 1.6.2.2 kent * update the hint. 45 1.6.2.2 kent * 46 1.6.2.2 kent * The radix tree also implements two collapsed states for meta nodes: 47 1.6.2.2 kent * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is 48 1.6.2.2 kent * in either of these two states, all information contained underneath 49 1.6.2.2 kent * the node is considered stale. These states are used to optimize 50 1.6.2.2 kent * allocation and freeing operations. 51 1.6.2.2 kent * 52 1.6.2.2 kent * The hinting greatly increases code efficiency for allocations while 53 1.6.2.2 kent * the general radix structure optimizes both allocations and frees. The 54 1.6.2.2 kent * radix tree should be able to operate well no matter how much 55 1.6.2.2 kent * fragmentation there is and no matter how large a bitmap is used. 56 1.6.2.2 kent * 57 1.6.2.2 kent * Unlike the rlist code, the blist code wires all necessary memory at 58 1.6.2.2 kent * creation time. Neither allocations nor frees require interaction with 59 1.6.2.2 kent * the memory subsystem. In contrast, the rlist code may allocate memory 60 1.6.2.2 kent * on an rlist_free() call. The non-blocking features of the blist code 61 1.6.2.2 kent * are used to great advantage in the swap code (vm/nswap_pager.c). The 62 1.6.2.2 kent * rlist code uses a little less overall memory then the blist code (but 63 1.6.2.2 kent * due to swap interleaving not all that much less), but the blist code 64 1.6.2.2 kent * scales much, much better. 65 1.6.2.2 kent * 66 1.6.2.2 kent * LAYOUT: The radix tree is layed out recursively using a 67 1.6.2.2 kent * linear array. Each meta node is immediately followed (layed out 68 1.6.2.2 kent * sequentially in memory) by BLIST_META_RADIX lower level nodes. This 69 1.6.2.2 kent * is a recursive structure but one that can be easily scanned through 70 1.6.2.2 kent * a very simple 'skip' calculation. In order to support large radixes, 71 1.6.2.2 kent * portions of the tree may reside outside our memory allocation. We 72 1.6.2.2 kent * handle this with an early-termination optimization (when bighint is 73 1.6.2.2 kent * set to -1) on the scan. The memory allocation is only large enough 74 1.6.2.2 kent * to cover the number of blocks requested at creation time even if it 75 1.6.2.2 kent * must be encompassed in larger root-node radix. 76 1.6.2.2 kent * 77 1.6.2.2 kent * NOTE: the allocator cannot currently allocate more then 78 1.6.2.2 kent * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too 79 1.6.2.2 kent * large' if you try. This is an area that could use improvement. The 80 1.6.2.2 kent * radix is large enough that this restriction does not effect the swap 81 1.6.2.2 kent * system, though. Currently only the allocation code is effected by 82 1.6.2.2 kent * this algorithmic unfeature. The freeing code can handle arbitrary 83 1.6.2.2 kent * ranges. 84 1.6.2.2 kent * 85 1.6.2.2 kent * This code can be compiled stand-alone for debugging. 86 1.6.2.2 kent */ 87 1.6.2.2 kent 88 1.6.2.2 kent #include <sys/cdefs.h> 89 1.6.2.2 kent __KERNEL_RCSID(0, "$NetBSD: subr_blist.c,v 1.6.2.2 2005/04/29 11:29:24 kent Exp $"); 90 1.6.2.2 kent #if 0 91 1.6.2.2 kent __FBSDID("$FreeBSD: src/sys/kern/subr_blist.c,v 1.17 2004/06/04 04:03:25 alc Exp $"); 92 1.6.2.2 kent #endif 93 1.6.2.2 kent 94 1.6.2.2 kent #ifdef _KERNEL 95 1.6.2.2 kent 96 1.6.2.2 kent #include <sys/param.h> 97 1.6.2.2 kent #include <sys/systm.h> 98 1.6.2.2 kent #include <sys/blist.h> 99 1.6.2.2 kent #include <sys/malloc.h> 100 1.6.2.2 kent 101 1.6.2.2 kent #else 102 1.6.2.2 kent 103 1.6.2.2 kent #ifndef BLIST_NO_DEBUG 104 1.6.2.2 kent #define BLIST_DEBUG 105 1.6.2.2 kent #endif 106 1.6.2.2 kent 107 1.6.2.2 kent #include <sys/types.h> 108 1.6.2.2 kent #include <stdio.h> 109 1.6.2.2 kent #include <string.h> 110 1.6.2.2 kent #include <stdlib.h> 111 1.6.2.2 kent #include <stdarg.h> 112 1.6.2.2 kent #include <inttypes.h> 113 1.6.2.2 kent 114 1.6.2.2 kent #define malloc(a,b,c) calloc(a, 1) 115 1.6.2.2 kent #define free(a,b) free(a) 116 1.6.2.2 kent 117 1.6.2.2 kent #include "../sys/blist.h" 118 1.6.2.2 kent 119 1.6.2.2 kent void panic(const char *ctl, ...); 120 1.6.2.2 kent 121 1.6.2.2 kent #endif 122 1.6.2.2 kent 123 1.6.2.2 kent /* 124 1.6.2.2 kent * blmeta and bl_bitmap_t MUST be a power of 2 in size. 125 1.6.2.2 kent */ 126 1.6.2.2 kent 127 1.6.2.2 kent typedef struct blmeta { 128 1.6.2.2 kent union { 129 1.6.2.2 kent blist_blkno_t bmu_avail; /* space available under us */ 130 1.6.2.2 kent blist_bitmap_t bmu_bitmap; /* bitmap if we are a leaf */ 131 1.6.2.2 kent } u; 132 1.6.2.2 kent blist_blkno_t bm_bighint; /* biggest contiguous block hint*/ 133 1.6.2.2 kent } blmeta_t; 134 1.6.2.2 kent 135 1.6.2.2 kent struct blist { 136 1.6.2.2 kent blist_blkno_t bl_blocks; /* area of coverage */ 137 1.6.2.2 kent blist_blkno_t bl_radix; /* coverage radix */ 138 1.6.2.2 kent blist_blkno_t bl_skip; /* starting skip */ 139 1.6.2.2 kent blist_blkno_t bl_free; /* number of free blocks */ 140 1.6.2.2 kent blmeta_t *bl_root; /* root of radix tree */ 141 1.6.2.2 kent blist_blkno_t bl_rootblks; /* blks allocated for tree */ 142 1.6.2.2 kent }; 143 1.6.2.2 kent 144 1.6.2.2 kent #define BLIST_META_RADIX 16 145 1.6.2.2 kent 146 1.6.2.2 kent /* 147 1.6.2.2 kent * static support functions 148 1.6.2.2 kent */ 149 1.6.2.2 kent 150 1.6.2.2 kent static blist_blkno_t blst_leaf_alloc(blmeta_t *scan, blist_blkno_t blk, 151 1.6.2.2 kent int count); 152 1.6.2.2 kent static blist_blkno_t blst_meta_alloc(blmeta_t *scan, blist_blkno_t blk, 153 1.6.2.2 kent blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip); 154 1.6.2.2 kent static void blst_leaf_free(blmeta_t *scan, blist_blkno_t relblk, int count); 155 1.6.2.2 kent static void blst_meta_free(blmeta_t *scan, blist_blkno_t freeBlk, 156 1.6.2.2 kent blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip, 157 1.6.2.2 kent blist_blkno_t blk); 158 1.6.2.2 kent static void blst_copy(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix, 159 1.6.2.2 kent blist_blkno_t skip, blist_t dest, blist_blkno_t count); 160 1.6.2.2 kent static int blst_leaf_fill(blmeta_t *scan, blist_blkno_t blk, int count); 161 1.6.2.2 kent static blist_blkno_t blst_meta_fill(blmeta_t *scan, blist_blkno_t allocBlk, 162 1.6.2.2 kent blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip, 163 1.6.2.2 kent blist_blkno_t blk); 164 1.6.2.2 kent static blist_blkno_t blst_radix_init(blmeta_t *scan, blist_blkno_t radix, 165 1.6.2.2 kent blist_blkno_t skip, blist_blkno_t count); 166 1.6.2.2 kent #ifndef _KERNEL 167 1.6.2.2 kent static void blst_radix_print(blmeta_t *scan, blist_blkno_t blk, 168 1.6.2.2 kent blist_blkno_t radix, blist_blkno_t skip, int tab); 169 1.6.2.2 kent #endif 170 1.6.2.2 kent 171 1.6.2.2 kent #ifdef _KERNEL 172 1.6.2.2 kent static MALLOC_DEFINE(M_BLIST, "blist", "Bitmap allocator"); 173 1.6.2.2 kent #endif 174 1.6.2.2 kent 175 1.6.2.2 kent /* 176 1.6.2.2 kent * blist_create() - create a blist capable of handling up to the specified 177 1.6.2.2 kent * number of blocks 178 1.6.2.2 kent * 179 1.6.2.2 kent * blocks must be greater then 0 180 1.6.2.2 kent * 181 1.6.2.2 kent * The smallest blist consists of a single leaf node capable of 182 1.6.2.2 kent * managing BLIST_BMAP_RADIX blocks. 183 1.6.2.2 kent */ 184 1.6.2.2 kent 185 1.6.2.2 kent blist_t 186 1.6.2.2 kent blist_create(blist_blkno_t blocks) 187 1.6.2.2 kent { 188 1.6.2.2 kent blist_t bl; 189 1.6.2.2 kent blist_blkno_t radix; 190 1.6.2.2 kent blist_blkno_t skip = 0; 191 1.6.2.2 kent 192 1.6.2.2 kent /* 193 1.6.2.2 kent * Calculate radix and skip field used for scanning. 194 1.6.2.2 kent * 195 1.6.2.2 kent * XXX check overflow 196 1.6.2.2 kent */ 197 1.6.2.2 kent radix = BLIST_BMAP_RADIX; 198 1.6.2.2 kent 199 1.6.2.2 kent while (radix < blocks) { 200 1.6.2.2 kent radix *= BLIST_META_RADIX; 201 1.6.2.2 kent skip = (skip + 1) * BLIST_META_RADIX; 202 1.6.2.2 kent } 203 1.6.2.2 kent 204 1.6.2.2 kent bl = malloc(sizeof(struct blist), M_BLIST, M_WAITOK | M_ZERO); 205 1.6.2.2 kent 206 1.6.2.2 kent bl->bl_blocks = blocks; 207 1.6.2.2 kent bl->bl_radix = radix; 208 1.6.2.2 kent bl->bl_skip = skip; 209 1.6.2.2 kent bl->bl_rootblks = 1 + 210 1.6.2.2 kent blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 211 1.6.2.2 kent bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_BLIST, M_WAITOK); 212 1.6.2.2 kent 213 1.6.2.2 kent #if defined(BLIST_DEBUG) 214 1.6.2.2 kent printf( 215 1.6.2.2 kent "BLIST representing %" PRIu64 " blocks (%" PRIu64 " MB of swap)" 216 1.6.2.2 kent ", requiring %" PRIu64 "K of ram\n", 217 1.6.2.2 kent (uint64_t)bl->bl_blocks, 218 1.6.2.2 kent (uint64_t)bl->bl_blocks * 4 / 1024, 219 1.6.2.2 kent ((uint64_t)bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 220 1.6.2.2 kent ); 221 1.6.2.2 kent printf("BLIST raw radix tree contains %" PRIu64 " records\n", 222 1.6.2.2 kent (uint64_t)bl->bl_rootblks); 223 1.6.2.2 kent #endif 224 1.6.2.2 kent blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 225 1.6.2.2 kent 226 1.6.2.2 kent return(bl); 227 1.6.2.2 kent } 228 1.6.2.2 kent 229 1.6.2.2 kent void 230 1.6.2.2 kent blist_destroy(blist_t bl) 231 1.6.2.2 kent { 232 1.6.2.2 kent free(bl->bl_root, M_BLIST); 233 1.6.2.2 kent free(bl, M_BLIST); 234 1.6.2.2 kent } 235 1.6.2.2 kent 236 1.6.2.2 kent /* 237 1.6.2.2 kent * blist_alloc() - reserve space in the block bitmap. Return the base 238 1.6.2.2 kent * of a contiguous region or BLIST_NONE if space could 239 1.6.2.2 kent * not be allocated. 240 1.6.2.2 kent */ 241 1.6.2.2 kent 242 1.6.2.2 kent blist_blkno_t 243 1.6.2.2 kent blist_alloc(blist_t bl, blist_blkno_t count) 244 1.6.2.2 kent { 245 1.6.2.2 kent blist_blkno_t blk = BLIST_NONE; 246 1.6.2.2 kent 247 1.6.2.2 kent if (bl) { 248 1.6.2.2 kent if (bl->bl_radix == BLIST_BMAP_RADIX) 249 1.6.2.2 kent blk = blst_leaf_alloc(bl->bl_root, 0, count); 250 1.6.2.2 kent else 251 1.6.2.2 kent blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 252 1.6.2.2 kent if (blk != BLIST_NONE) 253 1.6.2.2 kent bl->bl_free -= count; 254 1.6.2.2 kent } 255 1.6.2.2 kent return(blk); 256 1.6.2.2 kent } 257 1.6.2.2 kent 258 1.6.2.2 kent /* 259 1.6.2.2 kent * blist_free() - free up space in the block bitmap. Return the base 260 1.6.2.2 kent * of a contiguous region. Panic if an inconsistancy is 261 1.6.2.2 kent * found. 262 1.6.2.2 kent */ 263 1.6.2.2 kent 264 1.6.2.2 kent void 265 1.6.2.2 kent blist_free(blist_t bl, blist_blkno_t blkno, blist_blkno_t count) 266 1.6.2.2 kent { 267 1.6.2.2 kent if (bl) { 268 1.6.2.2 kent if (bl->bl_radix == BLIST_BMAP_RADIX) 269 1.6.2.2 kent blst_leaf_free(bl->bl_root, blkno, count); 270 1.6.2.2 kent else 271 1.6.2.2 kent blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 272 1.6.2.2 kent bl->bl_free += count; 273 1.6.2.2 kent } 274 1.6.2.2 kent } 275 1.6.2.2 kent 276 1.6.2.2 kent /* 277 1.6.2.2 kent * blist_fill() - mark a region in the block bitmap as off-limits 278 1.6.2.2 kent * to the allocator (i.e. allocate it), ignoring any 279 1.6.2.2 kent * existing allocations. Return the number of blocks 280 1.6.2.2 kent * actually filled that were free before the call. 281 1.6.2.2 kent */ 282 1.6.2.2 kent 283 1.6.2.2 kent blist_blkno_t 284 1.6.2.2 kent blist_fill(blist_t bl, blist_blkno_t blkno, blist_blkno_t count) 285 1.6.2.2 kent { 286 1.6.2.2 kent blist_blkno_t filled; 287 1.6.2.2 kent 288 1.6.2.2 kent if (bl) { 289 1.6.2.2 kent if (bl->bl_radix == BLIST_BMAP_RADIX) 290 1.6.2.2 kent filled = blst_leaf_fill(bl->bl_root, blkno, count); 291 1.6.2.2 kent else 292 1.6.2.2 kent filled = blst_meta_fill(bl->bl_root, blkno, count, 293 1.6.2.2 kent bl->bl_radix, bl->bl_skip, 0); 294 1.6.2.2 kent bl->bl_free -= filled; 295 1.6.2.2 kent return filled; 296 1.6.2.2 kent } else 297 1.6.2.2 kent return 0; 298 1.6.2.2 kent } 299 1.6.2.2 kent 300 1.6.2.2 kent /* 301 1.6.2.2 kent * blist_resize() - resize an existing radix tree to handle the 302 1.6.2.2 kent * specified number of blocks. This will reallocate 303 1.6.2.2 kent * the tree and transfer the previous bitmap to the new 304 1.6.2.2 kent * one. When extending the tree you can specify whether 305 1.6.2.2 kent * the new blocks are to left allocated or freed. 306 1.6.2.2 kent */ 307 1.6.2.2 kent 308 1.6.2.2 kent void 309 1.6.2.2 kent blist_resize(blist_t *pbl, blist_blkno_t count, int freenew) 310 1.6.2.2 kent { 311 1.6.2.2 kent blist_t newbl = blist_create(count); 312 1.6.2.2 kent blist_t save = *pbl; 313 1.6.2.2 kent 314 1.6.2.2 kent *pbl = newbl; 315 1.6.2.2 kent if (count > save->bl_blocks) 316 1.6.2.2 kent count = save->bl_blocks; 317 1.6.2.2 kent blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 318 1.6.2.2 kent 319 1.6.2.2 kent /* 320 1.6.2.2 kent * If resizing upwards, should we free the new space or not? 321 1.6.2.2 kent */ 322 1.6.2.2 kent if (freenew && count < newbl->bl_blocks) { 323 1.6.2.2 kent blist_free(newbl, count, newbl->bl_blocks - count); 324 1.6.2.2 kent } 325 1.6.2.2 kent blist_destroy(save); 326 1.6.2.2 kent } 327 1.6.2.2 kent 328 1.6.2.2 kent #ifdef BLIST_DEBUG 329 1.6.2.2 kent 330 1.6.2.2 kent /* 331 1.6.2.2 kent * blist_print() - dump radix tree 332 1.6.2.2 kent */ 333 1.6.2.2 kent 334 1.6.2.2 kent void 335 1.6.2.2 kent blist_print(blist_t bl) 336 1.6.2.2 kent { 337 1.6.2.2 kent printf("BLIST {\n"); 338 1.6.2.2 kent blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 339 1.6.2.2 kent printf("}\n"); 340 1.6.2.2 kent } 341 1.6.2.2 kent 342 1.6.2.2 kent #endif 343 1.6.2.2 kent 344 1.6.2.2 kent /************************************************************************ 345 1.6.2.2 kent * ALLOCATION SUPPORT FUNCTIONS * 346 1.6.2.2 kent ************************************************************************ 347 1.6.2.2 kent * 348 1.6.2.2 kent * These support functions do all the actual work. They may seem 349 1.6.2.2 kent * rather longish, but that's because I've commented them up. The 350 1.6.2.2 kent * actual code is straight forward. 351 1.6.2.2 kent * 352 1.6.2.2 kent */ 353 1.6.2.2 kent 354 1.6.2.2 kent /* 355 1.6.2.2 kent * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 356 1.6.2.2 kent * 357 1.6.2.2 kent * This is the core of the allocator and is optimized for the 1 block 358 1.6.2.2 kent * and the BLIST_BMAP_RADIX block allocation cases. Other cases are 359 1.6.2.2 kent * somewhat slower. The 1 block allocation case is log2 and extremely 360 1.6.2.2 kent * quick. 361 1.6.2.2 kent */ 362 1.6.2.2 kent 363 1.6.2.2 kent static blist_blkno_t 364 1.6.2.2 kent blst_leaf_alloc( 365 1.6.2.2 kent blmeta_t *scan, 366 1.6.2.2 kent blist_blkno_t blk, 367 1.6.2.2 kent int count 368 1.6.2.2 kent ) { 369 1.6.2.2 kent blist_bitmap_t orig = scan->u.bmu_bitmap; 370 1.6.2.2 kent 371 1.6.2.2 kent if (orig == 0) { 372 1.6.2.2 kent /* 373 1.6.2.2 kent * Optimize bitmap all-allocated case. Also, count = 1 374 1.6.2.2 kent * case assumes at least 1 bit is free in the bitmap, so 375 1.6.2.2 kent * we have to take care of this case here. 376 1.6.2.2 kent */ 377 1.6.2.2 kent scan->bm_bighint = 0; 378 1.6.2.2 kent return(BLIST_NONE); 379 1.6.2.2 kent } 380 1.6.2.2 kent if (count == 1) { 381 1.6.2.2 kent /* 382 1.6.2.2 kent * Optimized code to allocate one bit out of the bitmap 383 1.6.2.2 kent */ 384 1.6.2.2 kent blist_bitmap_t mask; 385 1.6.2.2 kent int j = BLIST_BMAP_RADIX/2; 386 1.6.2.2 kent int r = 0; 387 1.6.2.2 kent 388 1.6.2.2 kent mask = (blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX/2); 389 1.6.2.2 kent 390 1.6.2.2 kent while (j) { 391 1.6.2.2 kent if ((orig & mask) == 0) { 392 1.6.2.2 kent r += j; 393 1.6.2.2 kent orig >>= j; 394 1.6.2.2 kent } 395 1.6.2.2 kent j >>= 1; 396 1.6.2.2 kent mask >>= j; 397 1.6.2.2 kent } 398 1.6.2.2 kent scan->u.bmu_bitmap &= ~((blist_bitmap_t)1 << r); 399 1.6.2.2 kent return(blk + r); 400 1.6.2.2 kent } 401 1.6.2.2 kent if (count <= BLIST_BMAP_RADIX) { 402 1.6.2.2 kent /* 403 1.6.2.2 kent * non-optimized code to allocate N bits out of the bitmap. 404 1.6.2.2 kent * The more bits, the faster the code runs. It will run 405 1.6.2.2 kent * the slowest allocating 2 bits, but since there aren't any 406 1.6.2.2 kent * memory ops in the core loop (or shouldn't be, anyway), 407 1.6.2.2 kent * you probably won't notice the difference. 408 1.6.2.2 kent */ 409 1.6.2.2 kent int j; 410 1.6.2.2 kent int n = BLIST_BMAP_RADIX - count; 411 1.6.2.2 kent blist_bitmap_t mask; 412 1.6.2.2 kent 413 1.6.2.2 kent mask = (blist_bitmap_t)-1 >> n; 414 1.6.2.2 kent 415 1.6.2.2 kent for (j = 0; j <= n; ++j) { 416 1.6.2.2 kent if ((orig & mask) == mask) { 417 1.6.2.2 kent scan->u.bmu_bitmap &= ~mask; 418 1.6.2.2 kent return(blk + j); 419 1.6.2.2 kent } 420 1.6.2.2 kent mask = (mask << 1); 421 1.6.2.2 kent } 422 1.6.2.2 kent } 423 1.6.2.2 kent /* 424 1.6.2.2 kent * We couldn't allocate count in this subtree, update bighint. 425 1.6.2.2 kent */ 426 1.6.2.2 kent scan->bm_bighint = count - 1; 427 1.6.2.2 kent return(BLIST_NONE); 428 1.6.2.2 kent } 429 1.6.2.2 kent 430 1.6.2.2 kent /* 431 1.6.2.2 kent * blist_meta_alloc() - allocate at a meta in the radix tree. 432 1.6.2.2 kent * 433 1.6.2.2 kent * Attempt to allocate at a meta node. If we can't, we update 434 1.6.2.2 kent * bighint and return a failure. Updating bighint optimize future 435 1.6.2.2 kent * calls that hit this node. We have to check for our collapse cases 436 1.6.2.2 kent * and we have a few optimizations strewn in as well. 437 1.6.2.2 kent */ 438 1.6.2.2 kent 439 1.6.2.2 kent static blist_blkno_t 440 1.6.2.2 kent blst_meta_alloc( 441 1.6.2.2 kent blmeta_t *scan, 442 1.6.2.2 kent blist_blkno_t blk, 443 1.6.2.2 kent blist_blkno_t count, 444 1.6.2.2 kent blist_blkno_t radix, 445 1.6.2.2 kent blist_blkno_t skip 446 1.6.2.2 kent ) { 447 1.6.2.2 kent blist_blkno_t i; 448 1.6.2.2 kent blist_blkno_t next_skip = (skip / BLIST_META_RADIX); 449 1.6.2.2 kent 450 1.6.2.2 kent if (scan->u.bmu_avail == 0) { 451 1.6.2.2 kent /* 452 1.6.2.2 kent * ALL-ALLOCATED special case 453 1.6.2.2 kent */ 454 1.6.2.2 kent scan->bm_bighint = count; 455 1.6.2.2 kent return(BLIST_NONE); 456 1.6.2.2 kent } 457 1.6.2.2 kent 458 1.6.2.2 kent if (scan->u.bmu_avail == radix) { 459 1.6.2.2 kent radix /= BLIST_META_RADIX; 460 1.6.2.2 kent 461 1.6.2.2 kent /* 462 1.6.2.2 kent * ALL-FREE special case, initialize uninitialize 463 1.6.2.2 kent * sublevel. 464 1.6.2.2 kent */ 465 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 466 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) 467 1.6.2.2 kent break; 468 1.6.2.2 kent if (next_skip == 1) { 469 1.6.2.2 kent scan[i].u.bmu_bitmap = (blist_bitmap_t)-1; 470 1.6.2.2 kent scan[i].bm_bighint = BLIST_BMAP_RADIX; 471 1.6.2.2 kent } else { 472 1.6.2.2 kent scan[i].bm_bighint = radix; 473 1.6.2.2 kent scan[i].u.bmu_avail = radix; 474 1.6.2.2 kent } 475 1.6.2.2 kent } 476 1.6.2.2 kent } else { 477 1.6.2.2 kent radix /= BLIST_META_RADIX; 478 1.6.2.2 kent } 479 1.6.2.2 kent 480 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 481 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) { 482 1.6.2.2 kent /* 483 1.6.2.2 kent * Terminator 484 1.6.2.2 kent */ 485 1.6.2.2 kent break; 486 1.6.2.2 kent } else if (count <= scan[i].bm_bighint) { 487 1.6.2.2 kent /* 488 1.6.2.2 kent * count fits in object 489 1.6.2.2 kent */ 490 1.6.2.2 kent blist_blkno_t r; 491 1.6.2.2 kent if (next_skip == 1) { 492 1.6.2.2 kent r = blst_leaf_alloc(&scan[i], blk, count); 493 1.6.2.2 kent } else { 494 1.6.2.2 kent r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 495 1.6.2.2 kent } 496 1.6.2.2 kent if (r != BLIST_NONE) { 497 1.6.2.2 kent scan->u.bmu_avail -= count; 498 1.6.2.2 kent if (scan->bm_bighint > scan->u.bmu_avail) 499 1.6.2.2 kent scan->bm_bighint = scan->u.bmu_avail; 500 1.6.2.2 kent return(r); 501 1.6.2.2 kent } 502 1.6.2.2 kent } else if (count > radix) { 503 1.6.2.2 kent /* 504 1.6.2.2 kent * count does not fit in object even if it were 505 1.6.2.2 kent * complete free. 506 1.6.2.2 kent */ 507 1.6.2.2 kent panic("blist_meta_alloc: allocation too large"); 508 1.6.2.2 kent } 509 1.6.2.2 kent blk += radix; 510 1.6.2.2 kent } 511 1.6.2.2 kent 512 1.6.2.2 kent /* 513 1.6.2.2 kent * We couldn't allocate count in this subtree, update bighint. 514 1.6.2.2 kent */ 515 1.6.2.2 kent if (scan->bm_bighint >= count) 516 1.6.2.2 kent scan->bm_bighint = count - 1; 517 1.6.2.2 kent return(BLIST_NONE); 518 1.6.2.2 kent } 519 1.6.2.2 kent 520 1.6.2.2 kent /* 521 1.6.2.2 kent * BLST_LEAF_FREE() - free allocated block from leaf bitmap 522 1.6.2.2 kent * 523 1.6.2.2 kent */ 524 1.6.2.2 kent 525 1.6.2.2 kent static void 526 1.6.2.2 kent blst_leaf_free( 527 1.6.2.2 kent blmeta_t *scan, 528 1.6.2.2 kent blist_blkno_t blk, 529 1.6.2.2 kent int count 530 1.6.2.2 kent ) { 531 1.6.2.2 kent /* 532 1.6.2.2 kent * free some data in this bitmap 533 1.6.2.2 kent * 534 1.6.2.2 kent * e.g. 535 1.6.2.2 kent * 0000111111111110000 536 1.6.2.2 kent * \_________/\__/ 537 1.6.2.2 kent * v n 538 1.6.2.2 kent */ 539 1.6.2.2 kent int n = blk & (BLIST_BMAP_RADIX - 1); 540 1.6.2.2 kent blist_bitmap_t mask; 541 1.6.2.2 kent 542 1.6.2.2 kent mask = ((blist_bitmap_t)-1 << n) & 543 1.6.2.2 kent ((blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 544 1.6.2.2 kent 545 1.6.2.2 kent if (scan->u.bmu_bitmap & mask) 546 1.6.2.2 kent panic("blst_radix_free: freeing free block"); 547 1.6.2.2 kent scan->u.bmu_bitmap |= mask; 548 1.6.2.2 kent 549 1.6.2.2 kent /* 550 1.6.2.2 kent * We could probably do a better job here. We are required to make 551 1.6.2.2 kent * bighint at least as large as the biggest contiguous block of 552 1.6.2.2 kent * data. If we just shoehorn it, a little extra overhead will 553 1.6.2.2 kent * be incured on the next allocation (but only that one typically). 554 1.6.2.2 kent */ 555 1.6.2.2 kent scan->bm_bighint = BLIST_BMAP_RADIX; 556 1.6.2.2 kent } 557 1.6.2.2 kent 558 1.6.2.2 kent /* 559 1.6.2.2 kent * BLST_META_FREE() - free allocated blocks from radix tree meta info 560 1.6.2.2 kent * 561 1.6.2.2 kent * This support routine frees a range of blocks from the bitmap. 562 1.6.2.2 kent * The range must be entirely enclosed by this radix node. If a 563 1.6.2.2 kent * meta node, we break the range down recursively to free blocks 564 1.6.2.2 kent * in subnodes (which means that this code can free an arbitrary 565 1.6.2.2 kent * range whereas the allocation code cannot allocate an arbitrary 566 1.6.2.2 kent * range). 567 1.6.2.2 kent */ 568 1.6.2.2 kent 569 1.6.2.2 kent static void 570 1.6.2.2 kent blst_meta_free( 571 1.6.2.2 kent blmeta_t *scan, 572 1.6.2.2 kent blist_blkno_t freeBlk, 573 1.6.2.2 kent blist_blkno_t count, 574 1.6.2.2 kent blist_blkno_t radix, 575 1.6.2.2 kent blist_blkno_t skip, 576 1.6.2.2 kent blist_blkno_t blk 577 1.6.2.2 kent ) { 578 1.6.2.2 kent blist_blkno_t i; 579 1.6.2.2 kent blist_blkno_t next_skip = (skip / BLIST_META_RADIX); 580 1.6.2.2 kent 581 1.6.2.2 kent #if 0 582 1.6.2.2 kent printf("FREE (%" PRIx64 ",%" PRIu64 583 1.6.2.2 kent ") FROM (%" PRIx64 ",%" PRIu64 ")\n", 584 1.6.2.2 kent (uint64_t)freeBlk, (uint64_t)count, 585 1.6.2.2 kent (uint64_t)blk, (uint64_t)radix 586 1.6.2.2 kent ); 587 1.6.2.2 kent #endif 588 1.6.2.2 kent 589 1.6.2.2 kent if (scan->u.bmu_avail == 0) { 590 1.6.2.2 kent /* 591 1.6.2.2 kent * ALL-ALLOCATED special case, with possible 592 1.6.2.2 kent * shortcut to ALL-FREE special case. 593 1.6.2.2 kent */ 594 1.6.2.2 kent scan->u.bmu_avail = count; 595 1.6.2.2 kent scan->bm_bighint = count; 596 1.6.2.2 kent 597 1.6.2.2 kent if (count != radix) { 598 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 599 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) 600 1.6.2.2 kent break; 601 1.6.2.2 kent scan[i].bm_bighint = 0; 602 1.6.2.2 kent if (next_skip == 1) { 603 1.6.2.2 kent scan[i].u.bmu_bitmap = 0; 604 1.6.2.2 kent } else { 605 1.6.2.2 kent scan[i].u.bmu_avail = 0; 606 1.6.2.2 kent } 607 1.6.2.2 kent } 608 1.6.2.2 kent /* fall through */ 609 1.6.2.2 kent } 610 1.6.2.2 kent } else { 611 1.6.2.2 kent scan->u.bmu_avail += count; 612 1.6.2.2 kent /* scan->bm_bighint = radix; */ 613 1.6.2.2 kent } 614 1.6.2.2 kent 615 1.6.2.2 kent /* 616 1.6.2.2 kent * ALL-FREE special case. 617 1.6.2.2 kent */ 618 1.6.2.2 kent 619 1.6.2.2 kent if (scan->u.bmu_avail == radix) 620 1.6.2.2 kent return; 621 1.6.2.2 kent if (scan->u.bmu_avail > radix) 622 1.6.2.2 kent panic("blst_meta_free: freeing already free blocks (%" 623 1.6.2.2 kent PRIu64 ") %" PRIu64 "/%" PRIu64, 624 1.6.2.2 kent (uint64_t)count, 625 1.6.2.2 kent (uint64_t)scan->u.bmu_avail, 626 1.6.2.2 kent (uint64_t)radix); 627 1.6.2.2 kent 628 1.6.2.2 kent /* 629 1.6.2.2 kent * Break the free down into its components 630 1.6.2.2 kent */ 631 1.6.2.2 kent 632 1.6.2.2 kent radix /= BLIST_META_RADIX; 633 1.6.2.2 kent 634 1.6.2.2 kent i = (freeBlk - blk) / radix; 635 1.6.2.2 kent blk += i * radix; 636 1.6.2.2 kent i = i * next_skip + 1; 637 1.6.2.2 kent 638 1.6.2.2 kent while (i <= skip && blk < freeBlk + count) { 639 1.6.2.2 kent blist_blkno_t v; 640 1.6.2.2 kent 641 1.6.2.2 kent v = blk + radix - freeBlk; 642 1.6.2.2 kent if (v > count) 643 1.6.2.2 kent v = count; 644 1.6.2.2 kent 645 1.6.2.2 kent if (scan->bm_bighint == (blist_blkno_t)-1) 646 1.6.2.2 kent panic("blst_meta_free: freeing unexpected range"); 647 1.6.2.2 kent 648 1.6.2.2 kent if (next_skip == 1) { 649 1.6.2.2 kent blst_leaf_free(&scan[i], freeBlk, v); 650 1.6.2.2 kent } else { 651 1.6.2.2 kent blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 652 1.6.2.2 kent } 653 1.6.2.2 kent if (scan->bm_bighint < scan[i].bm_bighint) 654 1.6.2.2 kent scan->bm_bighint = scan[i].bm_bighint; 655 1.6.2.2 kent count -= v; 656 1.6.2.2 kent freeBlk += v; 657 1.6.2.2 kent blk += radix; 658 1.6.2.2 kent i += next_skip; 659 1.6.2.2 kent } 660 1.6.2.2 kent } 661 1.6.2.2 kent 662 1.6.2.2 kent /* 663 1.6.2.2 kent * BLIST_RADIX_COPY() - copy one radix tree to another 664 1.6.2.2 kent * 665 1.6.2.2 kent * Locates free space in the source tree and frees it in the destination 666 1.6.2.2 kent * tree. The space may not already be free in the destination. 667 1.6.2.2 kent */ 668 1.6.2.2 kent 669 1.6.2.2 kent static void blst_copy( 670 1.6.2.2 kent blmeta_t *scan, 671 1.6.2.2 kent blist_blkno_t blk, 672 1.6.2.2 kent blist_blkno_t radix, 673 1.6.2.2 kent blist_blkno_t skip, 674 1.6.2.2 kent blist_t dest, 675 1.6.2.2 kent blist_blkno_t count 676 1.6.2.2 kent ) { 677 1.6.2.2 kent blist_blkno_t next_skip; 678 1.6.2.2 kent blist_blkno_t i; 679 1.6.2.2 kent 680 1.6.2.2 kent /* 681 1.6.2.2 kent * Leaf node 682 1.6.2.2 kent */ 683 1.6.2.2 kent 684 1.6.2.2 kent if (radix == BLIST_BMAP_RADIX) { 685 1.6.2.2 kent blist_bitmap_t v = scan->u.bmu_bitmap; 686 1.6.2.2 kent 687 1.6.2.2 kent if (v == (blist_bitmap_t)-1) { 688 1.6.2.2 kent blist_free(dest, blk, count); 689 1.6.2.2 kent } else if (v != 0) { 690 1.6.2.2 kent int i; 691 1.6.2.2 kent 692 1.6.2.2 kent for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { 693 1.6.2.2 kent if (v & (1 << i)) 694 1.6.2.2 kent blist_free(dest, blk + i, 1); 695 1.6.2.2 kent } 696 1.6.2.2 kent } 697 1.6.2.2 kent return; 698 1.6.2.2 kent } 699 1.6.2.2 kent 700 1.6.2.2 kent /* 701 1.6.2.2 kent * Meta node 702 1.6.2.2 kent */ 703 1.6.2.2 kent 704 1.6.2.2 kent if (scan->u.bmu_avail == 0) { 705 1.6.2.2 kent /* 706 1.6.2.2 kent * Source all allocated, leave dest allocated 707 1.6.2.2 kent */ 708 1.6.2.2 kent return; 709 1.6.2.2 kent } 710 1.6.2.2 kent if (scan->u.bmu_avail == radix) { 711 1.6.2.2 kent /* 712 1.6.2.2 kent * Source all free, free entire dest 713 1.6.2.2 kent */ 714 1.6.2.2 kent if (count < radix) 715 1.6.2.2 kent blist_free(dest, blk, count); 716 1.6.2.2 kent else 717 1.6.2.2 kent blist_free(dest, blk, radix); 718 1.6.2.2 kent return; 719 1.6.2.2 kent } 720 1.6.2.2 kent 721 1.6.2.2 kent 722 1.6.2.2 kent radix /= BLIST_META_RADIX; 723 1.6.2.2 kent next_skip = (skip / BLIST_META_RADIX); 724 1.6.2.2 kent 725 1.6.2.2 kent for (i = 1; count && i <= skip; i += next_skip) { 726 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) 727 1.6.2.2 kent break; 728 1.6.2.2 kent 729 1.6.2.2 kent if (count >= radix) { 730 1.6.2.2 kent blst_copy( 731 1.6.2.2 kent &scan[i], 732 1.6.2.2 kent blk, 733 1.6.2.2 kent radix, 734 1.6.2.2 kent next_skip - 1, 735 1.6.2.2 kent dest, 736 1.6.2.2 kent radix 737 1.6.2.2 kent ); 738 1.6.2.2 kent count -= radix; 739 1.6.2.2 kent } else { 740 1.6.2.2 kent if (count) { 741 1.6.2.2 kent blst_copy( 742 1.6.2.2 kent &scan[i], 743 1.6.2.2 kent blk, 744 1.6.2.2 kent radix, 745 1.6.2.2 kent next_skip - 1, 746 1.6.2.2 kent dest, 747 1.6.2.2 kent count 748 1.6.2.2 kent ); 749 1.6.2.2 kent } 750 1.6.2.2 kent count = 0; 751 1.6.2.2 kent } 752 1.6.2.2 kent blk += radix; 753 1.6.2.2 kent } 754 1.6.2.2 kent } 755 1.6.2.2 kent 756 1.6.2.2 kent /* 757 1.6.2.2 kent * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap 758 1.6.2.2 kent * 759 1.6.2.2 kent * This routine allocates all blocks in the specified range 760 1.6.2.2 kent * regardless of any existing allocations in that range. Returns 761 1.6.2.2 kent * the number of blocks allocated by the call. 762 1.6.2.2 kent */ 763 1.6.2.2 kent 764 1.6.2.2 kent static int 765 1.6.2.2 kent blst_leaf_fill(blmeta_t *scan, blist_blkno_t blk, int count) 766 1.6.2.2 kent { 767 1.6.2.2 kent int n = blk & (BLIST_BMAP_RADIX - 1); 768 1.6.2.2 kent int nblks; 769 1.6.2.2 kent blist_bitmap_t mask, bitmap; 770 1.6.2.2 kent 771 1.6.2.2 kent mask = ((blist_bitmap_t)-1 << n) & 772 1.6.2.2 kent ((blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 773 1.6.2.2 kent 774 1.6.2.2 kent /* Count the number of blocks we're about to allocate */ 775 1.6.2.2 kent bitmap = scan->u.bmu_bitmap & mask; 776 1.6.2.2 kent for (nblks = 0; bitmap != 0; nblks++) 777 1.6.2.2 kent bitmap &= bitmap - 1; 778 1.6.2.2 kent 779 1.6.2.2 kent scan->u.bmu_bitmap &= ~mask; 780 1.6.2.2 kent return nblks; 781 1.6.2.2 kent } 782 1.6.2.2 kent 783 1.6.2.2 kent /* 784 1.6.2.2 kent * BLIST_META_FILL() - allocate specific blocks at a meta node 785 1.6.2.2 kent * 786 1.6.2.2 kent * This routine allocates the specified range of blocks, 787 1.6.2.2 kent * regardless of any existing allocations in the range. The 788 1.6.2.2 kent * range must be within the extent of this node. Returns the 789 1.6.2.2 kent * number of blocks allocated by the call. 790 1.6.2.2 kent */ 791 1.6.2.2 kent static blist_blkno_t 792 1.6.2.2 kent blst_meta_fill( 793 1.6.2.2 kent blmeta_t *scan, 794 1.6.2.2 kent blist_blkno_t allocBlk, 795 1.6.2.2 kent blist_blkno_t count, 796 1.6.2.2 kent blist_blkno_t radix, 797 1.6.2.2 kent blist_blkno_t skip, 798 1.6.2.2 kent blist_blkno_t blk 799 1.6.2.2 kent ) { 800 1.6.2.2 kent blist_blkno_t i; 801 1.6.2.2 kent blist_blkno_t next_skip = (skip / BLIST_META_RADIX); 802 1.6.2.2 kent blist_blkno_t nblks = 0; 803 1.6.2.2 kent 804 1.6.2.2 kent if (count == radix || scan->u.bmu_avail == 0) { 805 1.6.2.2 kent /* 806 1.6.2.2 kent * ALL-ALLOCATED special case 807 1.6.2.2 kent */ 808 1.6.2.2 kent nblks = scan->u.bmu_avail; 809 1.6.2.2 kent scan->u.bmu_avail = 0; 810 1.6.2.2 kent scan->bm_bighint = count; 811 1.6.2.2 kent return nblks; 812 1.6.2.2 kent } 813 1.6.2.2 kent 814 1.6.2.2 kent if (scan->u.bmu_avail == radix) { 815 1.6.2.2 kent radix /= BLIST_META_RADIX; 816 1.6.2.2 kent 817 1.6.2.2 kent /* 818 1.6.2.2 kent * ALL-FREE special case, initialize sublevel 819 1.6.2.2 kent */ 820 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 821 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) 822 1.6.2.2 kent break; 823 1.6.2.2 kent if (next_skip == 1) { 824 1.6.2.2 kent scan[i].u.bmu_bitmap = (blist_bitmap_t)-1; 825 1.6.2.2 kent scan[i].bm_bighint = BLIST_BMAP_RADIX; 826 1.6.2.2 kent } else { 827 1.6.2.2 kent scan[i].bm_bighint = radix; 828 1.6.2.2 kent scan[i].u.bmu_avail = radix; 829 1.6.2.2 kent } 830 1.6.2.2 kent } 831 1.6.2.2 kent } else { 832 1.6.2.2 kent radix /= BLIST_META_RADIX; 833 1.6.2.2 kent } 834 1.6.2.2 kent 835 1.6.2.2 kent if (count > radix) 836 1.6.2.2 kent panic("blist_meta_fill: allocation too large"); 837 1.6.2.2 kent 838 1.6.2.2 kent i = (allocBlk - blk) / radix; 839 1.6.2.2 kent blk += i * radix; 840 1.6.2.2 kent i = i * next_skip + 1; 841 1.6.2.2 kent 842 1.6.2.2 kent while (i <= skip && blk < allocBlk + count) { 843 1.6.2.2 kent blist_blkno_t v; 844 1.6.2.2 kent 845 1.6.2.2 kent v = blk + radix - allocBlk; 846 1.6.2.2 kent if (v > count) 847 1.6.2.2 kent v = count; 848 1.6.2.2 kent 849 1.6.2.2 kent if (scan->bm_bighint == (blist_blkno_t)-1) 850 1.6.2.2 kent panic("blst_meta_fill: filling unexpected range"); 851 1.6.2.2 kent 852 1.6.2.2 kent if (next_skip == 1) { 853 1.6.2.2 kent nblks += blst_leaf_fill(&scan[i], allocBlk, v); 854 1.6.2.2 kent } else { 855 1.6.2.2 kent nblks += blst_meta_fill(&scan[i], allocBlk, v, 856 1.6.2.2 kent radix, next_skip - 1, blk); 857 1.6.2.2 kent } 858 1.6.2.2 kent count -= v; 859 1.6.2.2 kent allocBlk += v; 860 1.6.2.2 kent blk += radix; 861 1.6.2.2 kent i += next_skip; 862 1.6.2.2 kent } 863 1.6.2.2 kent scan->u.bmu_avail -= nblks; 864 1.6.2.2 kent return nblks; 865 1.6.2.2 kent } 866 1.6.2.2 kent 867 1.6.2.2 kent /* 868 1.6.2.2 kent * BLST_RADIX_INIT() - initialize radix tree 869 1.6.2.2 kent * 870 1.6.2.2 kent * Initialize our meta structures and bitmaps and calculate the exact 871 1.6.2.2 kent * amount of space required to manage 'count' blocks - this space may 872 1.6.2.2 kent * be considerably less then the calculated radix due to the large 873 1.6.2.2 kent * RADIX values we use. 874 1.6.2.2 kent */ 875 1.6.2.2 kent 876 1.6.2.2 kent static blist_blkno_t 877 1.6.2.2 kent blst_radix_init(blmeta_t *scan, blist_blkno_t radix, blist_blkno_t skip, 878 1.6.2.2 kent blist_blkno_t count) 879 1.6.2.2 kent { 880 1.6.2.2 kent blist_blkno_t i; 881 1.6.2.2 kent blist_blkno_t next_skip; 882 1.6.2.2 kent blist_blkno_t memindex = 0; 883 1.6.2.2 kent 884 1.6.2.2 kent /* 885 1.6.2.2 kent * Leaf node 886 1.6.2.2 kent */ 887 1.6.2.2 kent 888 1.6.2.2 kent if (radix == BLIST_BMAP_RADIX) { 889 1.6.2.2 kent if (scan) { 890 1.6.2.2 kent scan->bm_bighint = 0; 891 1.6.2.2 kent scan->u.bmu_bitmap = 0; 892 1.6.2.2 kent } 893 1.6.2.2 kent return(memindex); 894 1.6.2.2 kent } 895 1.6.2.2 kent 896 1.6.2.2 kent /* 897 1.6.2.2 kent * Meta node. If allocating the entire object we can special 898 1.6.2.2 kent * case it. However, we need to figure out how much memory 899 1.6.2.2 kent * is required to manage 'count' blocks, so we continue on anyway. 900 1.6.2.2 kent */ 901 1.6.2.2 kent 902 1.6.2.2 kent if (scan) { 903 1.6.2.2 kent scan->bm_bighint = 0; 904 1.6.2.2 kent scan->u.bmu_avail = 0; 905 1.6.2.2 kent } 906 1.6.2.2 kent 907 1.6.2.2 kent radix /= BLIST_META_RADIX; 908 1.6.2.2 kent next_skip = (skip / BLIST_META_RADIX); 909 1.6.2.2 kent 910 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 911 1.6.2.2 kent if (count >= radix) { 912 1.6.2.2 kent /* 913 1.6.2.2 kent * Allocate the entire object 914 1.6.2.2 kent */ 915 1.6.2.2 kent memindex = i + blst_radix_init( 916 1.6.2.2 kent ((scan) ? &scan[i] : NULL), 917 1.6.2.2 kent radix, 918 1.6.2.2 kent next_skip - 1, 919 1.6.2.2 kent radix 920 1.6.2.2 kent ); 921 1.6.2.2 kent count -= radix; 922 1.6.2.2 kent } else if (count > 0) { 923 1.6.2.2 kent /* 924 1.6.2.2 kent * Allocate a partial object 925 1.6.2.2 kent */ 926 1.6.2.2 kent memindex = i + blst_radix_init( 927 1.6.2.2 kent ((scan) ? &scan[i] : NULL), 928 1.6.2.2 kent radix, 929 1.6.2.2 kent next_skip - 1, 930 1.6.2.2 kent count 931 1.6.2.2 kent ); 932 1.6.2.2 kent count = 0; 933 1.6.2.2 kent } else { 934 1.6.2.2 kent /* 935 1.6.2.2 kent * Add terminator and break out 936 1.6.2.2 kent */ 937 1.6.2.2 kent if (scan) 938 1.6.2.2 kent scan[i].bm_bighint = (blist_blkno_t)-1; 939 1.6.2.2 kent break; 940 1.6.2.2 kent } 941 1.6.2.2 kent } 942 1.6.2.2 kent if (memindex < i) 943 1.6.2.2 kent memindex = i; 944 1.6.2.2 kent return(memindex); 945 1.6.2.2 kent } 946 1.6.2.2 kent 947 1.6.2.2 kent #ifdef BLIST_DEBUG 948 1.6.2.2 kent 949 1.6.2.2 kent static void 950 1.6.2.2 kent blst_radix_print(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix, 951 1.6.2.2 kent blist_blkno_t skip, int tab) 952 1.6.2.2 kent { 953 1.6.2.2 kent blist_blkno_t i; 954 1.6.2.2 kent blist_blkno_t next_skip; 955 1.6.2.2 kent int lastState = 0; 956 1.6.2.2 kent 957 1.6.2.2 kent if (radix == BLIST_BMAP_RADIX) { 958 1.6.2.2 kent printf( 959 1.6.2.2 kent "%*.*s(%0*" PRIx64 ",%" PRIu64 960 1.6.2.2 kent "): bitmap %0*" PRIx64 " big=%" PRIu64 "\n", 961 1.6.2.2 kent tab, tab, "", 962 1.6.2.2 kent sizeof(blk) * 2, 963 1.6.2.2 kent (uint64_t)blk, 964 1.6.2.2 kent (uint64_t)radix, 965 1.6.2.2 kent sizeof(scan->u.bmu_bitmap) * 2, 966 1.6.2.2 kent (uint64_t)scan->u.bmu_bitmap, 967 1.6.2.2 kent (uint64_t)scan->bm_bighint 968 1.6.2.2 kent ); 969 1.6.2.2 kent return; 970 1.6.2.2 kent } 971 1.6.2.2 kent 972 1.6.2.2 kent if (scan->u.bmu_avail == 0) { 973 1.6.2.2 kent printf( 974 1.6.2.2 kent "%*.*s(%0*" PRIx64 ",%" PRIu64") ALL ALLOCATED\n", 975 1.6.2.2 kent tab, tab, "", 976 1.6.2.2 kent sizeof(blk) * 2, 977 1.6.2.2 kent (uint64_t)blk, 978 1.6.2.2 kent (uint64_t)radix 979 1.6.2.2 kent ); 980 1.6.2.2 kent return; 981 1.6.2.2 kent } 982 1.6.2.2 kent if (scan->u.bmu_avail == radix) { 983 1.6.2.2 kent printf( 984 1.6.2.2 kent "%*.*s(%0*" PRIx64 ",%" PRIu64 ") ALL FREE\n", 985 1.6.2.2 kent tab, tab, "", 986 1.6.2.2 kent sizeof(blk) * 2, 987 1.6.2.2 kent (uint64_t)blk, 988 1.6.2.2 kent (uint64_t)radix 989 1.6.2.2 kent ); 990 1.6.2.2 kent return; 991 1.6.2.2 kent } 992 1.6.2.2 kent 993 1.6.2.2 kent printf( 994 1.6.2.2 kent "%*.*s(%0*" PRIx64 ",%" PRIu64 "): subtree (%" PRIu64 "/%" 995 1.6.2.2 kent PRIu64 ") big=%" PRIu64 " {\n", 996 1.6.2.2 kent tab, tab, "", 997 1.6.2.2 kent sizeof(blk) * 2, 998 1.6.2.2 kent (uint64_t)blk, 999 1.6.2.2 kent (uint64_t)radix, 1000 1.6.2.2 kent (uint64_t)scan->u.bmu_avail, 1001 1.6.2.2 kent (uint64_t)radix, 1002 1.6.2.2 kent (uint64_t)scan->bm_bighint 1003 1.6.2.2 kent ); 1004 1.6.2.2 kent 1005 1.6.2.2 kent radix /= BLIST_META_RADIX; 1006 1.6.2.2 kent next_skip = (skip / BLIST_META_RADIX); 1007 1.6.2.2 kent tab += 4; 1008 1.6.2.2 kent 1009 1.6.2.2 kent for (i = 1; i <= skip; i += next_skip) { 1010 1.6.2.2 kent if (scan[i].bm_bighint == (blist_blkno_t)-1) { 1011 1.6.2.2 kent printf( 1012 1.6.2.2 kent "%*.*s(%0*" PRIx64 ",%" PRIu64 "): Terminator\n", 1013 1.6.2.2 kent tab, tab, "", 1014 1.6.2.2 kent sizeof(blk) * 2, 1015 1.6.2.2 kent (uint64_t)blk, 1016 1.6.2.2 kent (uint64_t)radix 1017 1.6.2.2 kent ); 1018 1.6.2.2 kent lastState = 0; 1019 1.6.2.2 kent break; 1020 1.6.2.2 kent } 1021 1.6.2.2 kent blst_radix_print( 1022 1.6.2.2 kent &scan[i], 1023 1.6.2.2 kent blk, 1024 1.6.2.2 kent radix, 1025 1.6.2.2 kent next_skip - 1, 1026 1.6.2.2 kent tab 1027 1.6.2.2 kent ); 1028 1.6.2.2 kent blk += radix; 1029 1.6.2.2 kent } 1030 1.6.2.2 kent tab -= 4; 1031 1.6.2.2 kent 1032 1.6.2.2 kent printf( 1033 1.6.2.2 kent "%*.*s}\n", 1034 1.6.2.2 kent tab, tab, "" 1035 1.6.2.2 kent ); 1036 1.6.2.2 kent } 1037 1.6.2.2 kent 1038 1.6.2.2 kent #endif 1039 1.6.2.2 kent 1040 1.6.2.2 kent #ifdef BLIST_DEBUG 1041 1.6.2.2 kent 1042 1.6.2.2 kent int 1043 1.6.2.2 kent main(int ac, char **av) 1044 1.6.2.2 kent { 1045 1.6.2.2 kent blist_blkno_t size = 1024; 1046 1.6.2.2 kent int i; 1047 1.6.2.2 kent blist_t bl; 1048 1.6.2.2 kent 1049 1.6.2.2 kent for (i = 1; i < ac; ++i) { 1050 1.6.2.2 kent const char *ptr = av[i]; 1051 1.6.2.2 kent if (*ptr != '-') { 1052 1.6.2.2 kent size = strtol(ptr, NULL, 0); 1053 1.6.2.2 kent continue; 1054 1.6.2.2 kent } 1055 1.6.2.2 kent ptr += 2; 1056 1.6.2.2 kent fprintf(stderr, "Bad option: %s\n", ptr - 2); 1057 1.6.2.2 kent exit(1); 1058 1.6.2.2 kent } 1059 1.6.2.2 kent bl = blist_create(size); 1060 1.6.2.2 kent blist_free(bl, 0, size); 1061 1.6.2.2 kent 1062 1.6.2.2 kent for (;;) { 1063 1.6.2.2 kent char buf[1024]; 1064 1.6.2.2 kent uint64_t da = 0; 1065 1.6.2.2 kent uint64_t count = 0; 1066 1.6.2.2 kent 1067 1.6.2.2 kent printf("%" PRIu64 "/%" PRIu64 "/%" PRIu64 "> ", 1068 1.6.2.2 kent (uint64_t)bl->bl_free, 1069 1.6.2.2 kent (uint64_t)size, 1070 1.6.2.2 kent (uint64_t)bl->bl_radix); 1071 1.6.2.2 kent fflush(stdout); 1072 1.6.2.2 kent if (fgets(buf, sizeof(buf), stdin) == NULL) 1073 1.6.2.2 kent break; 1074 1.6.2.2 kent switch(buf[0]) { 1075 1.6.2.2 kent case 'r': 1076 1.6.2.2 kent if (sscanf(buf + 1, "%" SCNu64, &count) == 1) { 1077 1.6.2.2 kent blist_resize(&bl, count, 1); 1078 1.6.2.2 kent } else { 1079 1.6.2.2 kent printf("?\n"); 1080 1.6.2.2 kent } 1081 1.6.2.2 kent case 'p': 1082 1.6.2.2 kent blist_print(bl); 1083 1.6.2.2 kent break; 1084 1.6.2.2 kent case 'a': 1085 1.6.2.2 kent if (sscanf(buf + 1, "%" SCNu64, &count) == 1) { 1086 1.6.2.2 kent blist_blkno_t blk = blist_alloc(bl, count); 1087 1.6.2.2 kent printf(" R=%0*" PRIx64 "\n", 1088 1.6.2.2 kent sizeof(blk) * 2, 1089 1.6.2.2 kent (uint64_t)blk); 1090 1.6.2.2 kent } else { 1091 1.6.2.2 kent printf("?\n"); 1092 1.6.2.2 kent } 1093 1.6.2.2 kent break; 1094 1.6.2.2 kent case 'f': 1095 1.6.2.2 kent if (sscanf(buf + 1, "%" SCNx64 " %" SCNu64, 1096 1.6.2.2 kent &da, &count) == 2) { 1097 1.6.2.2 kent blist_free(bl, da, count); 1098 1.6.2.2 kent } else { 1099 1.6.2.2 kent printf("?\n"); 1100 1.6.2.2 kent } 1101 1.6.2.2 kent break; 1102 1.6.2.2 kent case 'l': 1103 1.6.2.2 kent if (sscanf(buf + 1, "%" SCNx64 " %" SCNu64, 1104 1.6.2.2 kent &da, &count) == 2) { 1105 1.6.2.2 kent printf(" n=%" PRIu64 "\n", 1106 1.6.2.2 kent (uint64_t)blist_fill(bl, da, count)); 1107 1.6.2.2 kent } else { 1108 1.6.2.2 kent printf("?\n"); 1109 1.6.2.2 kent } 1110 1.6.2.2 kent break; 1111 1.6.2.2 kent case '?': 1112 1.6.2.2 kent case 'h': 1113 1.6.2.2 kent puts( 1114 1.6.2.2 kent "p -print\n" 1115 1.6.2.2 kent "a %d -allocate\n" 1116 1.6.2.2 kent "f %x %d -free\n" 1117 1.6.2.2 kent "l %x %d -fill\n" 1118 1.6.2.2 kent "r %d -resize\n" 1119 1.6.2.2 kent "h/? -help" 1120 1.6.2.2 kent ); 1121 1.6.2.2 kent break; 1122 1.6.2.2 kent default: 1123 1.6.2.2 kent printf("?\n"); 1124 1.6.2.2 kent break; 1125 1.6.2.2 kent } 1126 1.6.2.2 kent } 1127 1.6.2.2 kent return(0); 1128 1.6.2.2 kent } 1129 1.6.2.2 kent 1130 1.6.2.2 kent void 1131 1.6.2.2 kent panic(const char *ctl, ...) 1132 1.6.2.2 kent { 1133 1.6.2.2 kent va_list va; 1134 1.6.2.2 kent 1135 1.6.2.2 kent va_start(va, ctl); 1136 1.6.2.2 kent vfprintf(stderr, ctl, va); 1137 1.6.2.2 kent fprintf(stderr, "\n"); 1138 1.6.2.2 kent va_end(va); 1139 1.6.2.2 kent exit(1); 1140 1.6.2.2 kent } 1141 1.6.2.2 kent 1142 1.6.2.2 kent #endif 1143 1.6.2.2 kent 1144
Indexes created Tue Sep 30 20:09:53 GMT 2025