1118848Simp/*- 2118848Simp * Copyright (c) 1998 Matthew Dillon. All Rights Reserved. 3118848Simp * Redistribution and use in source and binary forms, with or without 4118848Simp * modification, are permitted provided that the following conditions 5118848Simp * are met: 6118848Simp * 1. Redistributions of source code must retain the above copyright 7118848Simp * notice, this list of conditions and the following disclaimer. 8118848Simp * 2. Redistributions in binary form must reproduce the above copyright 9118848Simp * notice, this list of conditions and the following disclaimer in the 10118848Simp * documentation and/or other materials provided with the distribution. 11118848Simp * 4. Neither the name of the University nor the names of its contributors 12118848Simp * may be used to endorse or promote products derived from this software 13118848Simp * without specific prior written permission. 14118848Simp * 15118848Simp * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 16118848Simp * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 17118848Simp * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18118848Simp * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 19118848Simp * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20118848Simp * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 21118848Simp * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 22118848Simp * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 23118848Simp * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 24118848Simp * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25118848Simp * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26118848Simp */ 2742956Sdillon/* 2842956Sdillon * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting 2942956Sdillon * 3042956Sdillon * This module implements a general bitmap allocator/deallocator. The 3142956Sdillon * allocator eats around 2 bits per 'block'. The module does not 32228233Seadler * try to interpret the meaning of a 'block' other than to return 3342956Sdillon * SWAPBLK_NONE on an allocation failure. 3442956Sdillon * 3542956Sdillon * A radix tree is used to maintain the bitmap. Two radix constants are 3642956Sdillon * involved: One for the bitmaps contained in the leaf nodes (typically 3742956Sdillon * 32), and one for the meta nodes (typically 16). Both meta and leaf 3842956Sdillon * nodes have a hint field. This field gives us a hint as to the largest 3942956Sdillon * free contiguous range of blocks under the node. It may contain a 4042956Sdillon * value that is too high, but will never contain a value that is too 4142956Sdillon * low. When the radix tree is searched, allocation failures in subtrees 4242956Sdillon * update the hint. 4342956Sdillon * 4442956Sdillon * The radix tree also implements two collapsed states for meta nodes: 4542956Sdillon * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is 4642956Sdillon * in either of these two states, all information contained underneath 4742956Sdillon * the node is considered stale. These states are used to optimize 4842956Sdillon * allocation and freeing operations. 4942956Sdillon * 5042956Sdillon * The hinting greatly increases code efficiency for allocations while 5142956Sdillon * the general radix structure optimizes both allocations and frees. The 5242956Sdillon * radix tree should be able to operate well no matter how much 5342956Sdillon * fragmentation there is and no matter how large a bitmap is used. 5442956Sdillon * 55246370Spluknet * The blist code wires all necessary memory at creation time. Neither 56246370Spluknet * allocations nor frees require interaction with the memory subsystem. 57246370Spluknet * The non-blocking features of the blist code are used in the swap code 58246370Spluknet * (vm/swap_pager.c). 5942956Sdillon * 60302234Sbdrewery * LAYOUT: The radix tree is laid out recursively using a 61302234Sbdrewery * linear array. Each meta node is immediately followed (laid out 6242956Sdillon * sequentially in memory) by BLIST_META_RADIX lower level nodes. This 6342956Sdillon * is a recursive structure but one that can be easily scanned through 6442956Sdillon * a very simple 'skip' calculation. In order to support large radixes, 6542956Sdillon * portions of the tree may reside outside our memory allocation. We 6642956Sdillon * handle this with an early-termination optimization (when bighint is 6742956Sdillon * set to -1) on the scan. The memory allocation is only large enough 6842956Sdillon * to cover the number of blocks requested at creation time even if it 6942956Sdillon * must be encompassed in larger root-node radix. 7042956Sdillon * 71228233Seadler * NOTE: the allocator cannot currently allocate more than 7242956Sdillon * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too 7342956Sdillon * large' if you try. This is an area that could use improvement. The 7442956Sdillon * radix is large enough that this restriction does not effect the swap 7542956Sdillon * system, though. Currently only the allocation code is effected by 7642956Sdillon * this algorithmic unfeature. The freeing code can handle arbitrary 7742956Sdillon * ranges. 7842956Sdillon * 7942956Sdillon * This code can be compiled stand-alone for debugging. 8042956Sdillon */ 8142956Sdillon 82116182Sobrien#include <sys/cdefs.h> 83116182Sobrien__FBSDID("$FreeBSD: stable/10/sys/kern/subr_blist.c 321459 2017-07-25 04:13:43Z alc $"); 84116182Sobrien 8555206Speter#ifdef _KERNEL 8642956Sdillon 8742956Sdillon#include <sys/param.h> 8842956Sdillon#include <sys/systm.h> 8942956Sdillon#include <sys/lock.h> 9042956Sdillon#include <sys/kernel.h> 9142956Sdillon#include <sys/blist.h> 9242956Sdillon#include <sys/malloc.h> 9379224Sdillon#include <sys/proc.h> 9476827Salfred#include <sys/mutex.h> 9542956Sdillon 9642956Sdillon#else 9742956Sdillon 9842956Sdillon#ifndef BLIST_NO_DEBUG 9942956Sdillon#define BLIST_DEBUG 10042956Sdillon#endif 10142956Sdillon 10242956Sdillon#include <sys/types.h> 103319965Salc#include <sys/malloc.h> 10442956Sdillon#include <stdio.h> 10542956Sdillon#include <string.h> 10642956Sdillon#include <stdlib.h> 10742956Sdillon#include <stdarg.h> 108321459Salc#include <stdbool.h> 10942956Sdillon 110321375Salc#define bitcount64(x) __bitcount64((uint64_t)(x)) 111107913Sdillon#define malloc(a,b,c) calloc(a, 1) 11242956Sdillon#define free(a,b) free(a) 11342956Sdillon 11442956Sdillon#include <sys/blist.h> 11542956Sdillon 11642956Sdillonvoid panic(const char *ctl, ...); 11742956Sdillon 11842956Sdillon#endif 11942956Sdillon 12042956Sdillon/* 12142956Sdillon * static support functions 12242956Sdillon */ 12342956Sdillon 124321459Salcstatic daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, 125321459Salc daddr_t cursor); 126321459Salcstatic daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, 127321459Salc daddr_t radix, daddr_t skip, daddr_t cursor); 12842956Sdillonstatic void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count); 12942956Sdillonstatic void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, 130321459Salc daddr_t radix, daddr_t skip, daddr_t blk); 13142956Sdillonstatic void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, 13242956Sdillon daddr_t skip, blist_t dest, daddr_t count); 133320622Salcstatic daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); 134320622Salcstatic daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, 135321459Salc daddr_t radix, daddr_t skip, daddr_t blk); 136321459Salcstatic daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, 137321459Salc daddr_t count); 13855206Speter#ifndef _KERNEL 139321459Salcstatic void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, 140321459Salc daddr_t skip, int tab); 14142956Sdillon#endif 14242956Sdillon 14355206Speter#ifdef _KERNEL 14442956Sdillonstatic MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); 14542956Sdillon#endif 14642956Sdillon 14742956Sdillon/* 14842956Sdillon * blist_create() - create a blist capable of handling up to the specified 14942956Sdillon * number of blocks 15042956Sdillon * 151228233Seadler * blocks - must be greater than 0 152178792Skmacy * flags - malloc flags 15342956Sdillon * 15442956Sdillon * The smallest blist consists of a single leaf node capable of 15542956Sdillon * managing BLIST_BMAP_RADIX blocks. 15642956Sdillon */ 15742956Sdillon 15842956Sdillonblist_t 159178792Skmacyblist_create(daddr_t blocks, int flags) 16042956Sdillon{ 16142956Sdillon blist_t bl; 162321459Salc daddr_t nodes, radix, skip; 16342956Sdillon 16442956Sdillon /* 16542956Sdillon * Calculate radix and skip field used for scanning. 16642956Sdillon */ 16742956Sdillon radix = BLIST_BMAP_RADIX; 168321459Salc skip = 0; 16942956Sdillon while (radix < blocks) { 170109086Sdillon radix *= BLIST_META_RADIX; 171109086Sdillon skip = (skip + 1) * BLIST_META_RADIX; 17242956Sdillon } 173321459Salc nodes = 1 + blst_radix_init(NULL, radix, skip, blocks); 17442956Sdillon 175321375Salc bl = malloc(sizeof(struct blist), M_SWAP, flags); 176320622Salc if (bl == NULL) 177320622Salc return (NULL); 17842956Sdillon 17942956Sdillon bl->bl_blocks = blocks; 18042956Sdillon bl->bl_radix = radix; 18142956Sdillon bl->bl_skip = skip; 182321459Salc bl->bl_cursor = 0; 183320622Salc bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags); 184320622Salc if (bl->bl_root == NULL) { 185320622Salc free(bl, M_SWAP); 186320622Salc return (NULL); 187320622Salc } 188321459Salc blst_radix_init(bl->bl_root, radix, skip, blocks); 18942956Sdillon 19042956Sdillon#if defined(BLIST_DEBUG) 19142956Sdillon printf( 192107913Sdillon "BLIST representing %lld blocks (%lld MB of swap)" 193107913Sdillon ", requiring %lldK of ram\n", 194107913Sdillon (long long)bl->bl_blocks, 195107913Sdillon (long long)bl->bl_blocks * 4 / 1024, 196320622Salc (long long)(nodes * sizeof(blmeta_t) + 1023) / 1024 19742956Sdillon ); 198107913Sdillon printf("BLIST raw radix tree contains %lld records\n", 199320622Salc (long long)nodes); 20042956Sdillon#endif 20142956Sdillon 202320622Salc return (bl); 20342956Sdillon} 20442956Sdillon 20542956Sdillonvoid 20642956Sdillonblist_destroy(blist_t bl) 20742956Sdillon{ 20842956Sdillon free(bl->bl_root, M_SWAP); 20942956Sdillon free(bl, M_SWAP); 21042956Sdillon} 21142956Sdillon 21242956Sdillon/* 213321375Salc * blist_alloc() - reserve space in the block bitmap. Return the base 21442956Sdillon * of a contiguous region or SWAPBLK_NONE if space could 21542956Sdillon * not be allocated. 21642956Sdillon */ 21742956Sdillon 21842956Sdillondaddr_t 21942956Sdillonblist_alloc(blist_t bl, daddr_t count) 22042956Sdillon{ 221321375Salc daddr_t blk; 22242956Sdillon 223321459Salc /* 224321459Salc * This loop iterates at most twice. An allocation failure in the 225321459Salc * first iteration leads to a second iteration only if the cursor was 226321459Salc * non-zero. When the cursor is zero, an allocation failure will 227321459Salc * reduce the hint, stopping further iterations. 228321459Salc */ 229321459Salc while (count <= bl->bl_root->bm_bighint) { 23042956Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 231321459Salc blk = blst_leaf_alloc(bl->bl_root, 0, count, 232321459Salc bl->bl_cursor); 23342956Sdillon else 234321375Salc blk = blst_meta_alloc(bl->bl_root, 0, count, 235321459Salc bl->bl_radix, bl->bl_skip, bl->bl_cursor); 236321459Salc if (blk != SWAPBLK_NONE) { 237321459Salc bl->bl_cursor = blk + count; 238321459Salc return (blk); 239321459Salc } else if (bl->bl_cursor != 0) 240321459Salc bl->bl_cursor = 0; 24142956Sdillon } 242321375Salc return (SWAPBLK_NONE); 24342956Sdillon} 24442956Sdillon 24542956Sdillon/* 246321375Salc * blist_avail() - return the number of free blocks. 247321375Salc */ 248321375Salc 249321375Salcdaddr_t 250321375Salcblist_avail(blist_t bl) 251321375Salc{ 252321375Salc 253321375Salc if (bl->bl_radix == BLIST_BMAP_RADIX) 254321375Salc return (bitcount64(bl->bl_root->u.bmu_bitmap)); 255321375Salc else 256321375Salc return (bl->bl_root->u.bmu_avail); 257321375Salc} 258321375Salc 259321375Salc/* 26042956Sdillon * blist_free() - free up space in the block bitmap. Return the base 26142956Sdillon * of a contiguous region. Panic if an inconsistancy is 26242956Sdillon * found. 26342956Sdillon */ 26442956Sdillon 26542956Sdillonvoid 26642956Sdillonblist_free(blist_t bl, daddr_t blkno, daddr_t count) 26742956Sdillon{ 26842956Sdillon if (bl) { 26942956Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 27042956Sdillon blst_leaf_free(bl->bl_root, blkno, count); 27142956Sdillon else 272321375Salc blst_meta_free(bl->bl_root, blkno, count, 273321375Salc bl->bl_radix, bl->bl_skip, 0); 27442956Sdillon } 27542956Sdillon} 27642956Sdillon 27742956Sdillon/* 278107913Sdillon * blist_fill() - mark a region in the block bitmap as off-limits 279107913Sdillon * to the allocator (i.e. allocate it), ignoring any 280107913Sdillon * existing allocations. Return the number of blocks 281107913Sdillon * actually filled that were free before the call. 282107913Sdillon */ 283107913Sdillon 284320622Salcdaddr_t 285107913Sdillonblist_fill(blist_t bl, daddr_t blkno, daddr_t count) 286107913Sdillon{ 287320622Salc daddr_t filled; 288107913Sdillon 289107913Sdillon if (bl) { 290107913Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 291107913Sdillon filled = blst_leaf_fill(bl->bl_root, blkno, count); 292107913Sdillon else 293107913Sdillon filled = blst_meta_fill(bl->bl_root, blkno, count, 294107913Sdillon bl->bl_radix, bl->bl_skip, 0); 295321375Salc return (filled); 296321375Salc } 297321375Salc return (0); 298107913Sdillon} 299107913Sdillon 300107913Sdillon/* 30142956Sdillon * blist_resize() - resize an existing radix tree to handle the 30242956Sdillon * specified number of blocks. This will reallocate 30342956Sdillon * the tree and transfer the previous bitmap to the new 30442956Sdillon * one. When extending the tree you can specify whether 30542956Sdillon * the new blocks are to left allocated or freed. 30642956Sdillon */ 30742956Sdillon 30842956Sdillonvoid 309178792Skmacyblist_resize(blist_t *pbl, daddr_t count, int freenew, int flags) 31042956Sdillon{ 311178792Skmacy blist_t newbl = blist_create(count, flags); 31242956Sdillon blist_t save = *pbl; 31342956Sdillon 31442956Sdillon *pbl = newbl; 31542956Sdillon if (count > save->bl_blocks) 31642956Sdillon count = save->bl_blocks; 31742956Sdillon blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 31842956Sdillon 31942956Sdillon /* 32042956Sdillon * If resizing upwards, should we free the new space or not? 32142956Sdillon */ 32242956Sdillon if (freenew && count < newbl->bl_blocks) { 32342956Sdillon blist_free(newbl, count, newbl->bl_blocks - count); 32442956Sdillon } 32542956Sdillon blist_destroy(save); 32642956Sdillon} 32742956Sdillon 32842956Sdillon#ifdef BLIST_DEBUG 32942956Sdillon 33042956Sdillon/* 33142956Sdillon * blist_print() - dump radix tree 33242956Sdillon */ 33342956Sdillon 33442956Sdillonvoid 33542956Sdillonblist_print(blist_t bl) 33642956Sdillon{ 33742956Sdillon printf("BLIST {\n"); 33842956Sdillon blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 33942956Sdillon printf("}\n"); 34042956Sdillon} 34142956Sdillon 34242956Sdillon#endif 34342956Sdillon 34442956Sdillon/************************************************************************ 34542956Sdillon * ALLOCATION SUPPORT FUNCTIONS * 34642956Sdillon ************************************************************************ 34742956Sdillon * 34842956Sdillon * These support functions do all the actual work. They may seem 34942956Sdillon * rather longish, but that's because I've commented them up. The 35042956Sdillon * actual code is straight forward. 35142956Sdillon * 35242956Sdillon */ 35342956Sdillon 35442956Sdillon/* 35542956Sdillon * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 35642956Sdillon * 357321459Salc * This is the core of the allocator and is optimized for the 358321459Salc * BLIST_BMAP_RADIX block allocation case. Otherwise, execution 359321459Salc * time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). 36042956Sdillon */ 36142956Sdillon 36242956Sdillonstatic daddr_t 363321459Salcblst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) 364321459Salc{ 365321459Salc u_daddr_t mask; 366321459Salc int count1, hi, lo, mid, num_shifts, range1, range_ext; 36742956Sdillon 368321459Salc if (count == BLIST_BMAP_RADIX) { 36942956Sdillon /* 370321459Salc * Optimize allocation of BLIST_BMAP_RADIX bits. If this wasn't 371321459Salc * a special case, then forming the final value of 'mask' below 372321459Salc * would require special handling to avoid an invalid left shift 373321459Salc * when count equals the number of bits in mask. 37442956Sdillon */ 375321459Salc if (~scan->u.bmu_bitmap != 0) { 376321459Salc scan->bm_bighint = BLIST_BMAP_RADIX - 1; 377321459Salc return (SWAPBLK_NONE); 378321459Salc } 379321459Salc if (cursor != blk) 380321459Salc return (SWAPBLK_NONE); 381321459Salc scan->u.bmu_bitmap = 0; 38242956Sdillon scan->bm_bighint = 0; 383321459Salc return (blk); 38442956Sdillon } 385321459Salc range1 = 0; 386321459Salc count1 = count - 1; 387321459Salc num_shifts = fls(count1); 388321459Salc mask = scan->u.bmu_bitmap; 389321459Salc while (mask != 0 && num_shifts > 0) { 39042956Sdillon /* 391321459Salc * If bit i is set in mask, then bits in [i, i+range1] are set 392321459Salc * in scan->u.bmu_bitmap. The value of range1 is equal to 393321459Salc * count1 >> num_shifts. Grow range and reduce num_shifts to 0, 394321459Salc * while preserving these invariants. The updates to mask leave 395321459Salc * fewer bits set, but each bit that remains set represents a 396321459Salc * longer string of consecutive bits set in scan->u.bmu_bitmap. 39742956Sdillon */ 398321459Salc num_shifts--; 399321459Salc range_ext = range1 + ((count1 >> num_shifts) & 1); 400321459Salc mask &= mask >> range_ext; 401321459Salc range1 += range_ext; 40242956Sdillon } 403321459Salc if (mask == 0) { 40442956Sdillon /* 405321459Salc * Update bighint. There is no allocation bigger than range1 406321459Salc * available in this leaf. 40742956Sdillon */ 408321459Salc scan->bm_bighint = range1; 409321459Salc return (SWAPBLK_NONE); 410321459Salc } 41142956Sdillon 412321459Salc /* 413321459Salc * Discard any candidates that appear before the cursor. 414321459Salc */ 415321459Salc lo = cursor - blk; 416321459Salc mask &= ~(u_daddr_t)0 << lo; 41742956Sdillon 418321459Salc if (mask == 0) 419321459Salc return (SWAPBLK_NONE); 420321459Salc 421321459Salc /* 422321459Salc * The least significant set bit in mask marks the start of the first 423321459Salc * available range of sufficient size. Clear all the bits but that one, 424321459Salc * and then perform a binary search to find its position. 425321459Salc */ 426321459Salc mask &= -mask; 427321459Salc hi = BLIST_BMAP_RADIX - count1; 428321459Salc while (lo + 1 < hi) { 429321459Salc mid = (lo + hi) >> 1; 430321459Salc if ((mask >> mid) != 0) 431321459Salc lo = mid; 432321459Salc else 433321459Salc hi = mid; 43442956Sdillon } 435321459Salc 43642956Sdillon /* 437321459Salc * Set in mask exactly the bits being allocated, and clear them from 438321459Salc * the set of available bits. 43942956Sdillon */ 440321459Salc mask = (mask << count) - mask; 441321459Salc scan->u.bmu_bitmap &= ~mask; 442321459Salc return (blk + lo); 44342956Sdillon} 44442956Sdillon 44542956Sdillon/* 44642956Sdillon * blist_meta_alloc() - allocate at a meta in the radix tree. 44742956Sdillon * 44842956Sdillon * Attempt to allocate at a meta node. If we can't, we update 44942956Sdillon * bighint and return a failure. Updating bighint optimize future 45042956Sdillon * calls that hit this node. We have to check for our collapse cases 45142956Sdillon * and we have a few optimizations strewn in as well. 45242956Sdillon */ 45342956Sdillon 45442956Sdillonstatic daddr_t 455321459Salcblst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix, 456321459Salc daddr_t skip, daddr_t cursor) 457321459Salc{ 458321459Salc daddr_t i, next_skip, r; 459321459Salc int child; 460321459Salc bool scan_from_start; 46142956Sdillon 462321375Salc if (scan->u.bmu_avail < count) { 46342956Sdillon /* 464321375Salc * The meta node's hint must be too large if the allocation 465321375Salc * exceeds the number of free blocks. Reduce the hint, and 466321375Salc * return failure. 46742956Sdillon */ 468321375Salc scan->bm_bighint = scan->u.bmu_avail; 469321375Salc return (SWAPBLK_NONE); 47042956Sdillon } 471321459Salc next_skip = skip / BLIST_META_RADIX; 47242956Sdillon 473321375Salc /* 474321375Salc * An ALL-FREE meta node requires special handling before allocating 475321375Salc * any of its blocks. 476321375Salc */ 47742956Sdillon if (scan->u.bmu_avail == radix) { 478109086Sdillon radix /= BLIST_META_RADIX; 47942956Sdillon 48042956Sdillon /* 481321375Salc * Reinitialize each of the meta node's children. An ALL-FREE 482321375Salc * meta node cannot have a terminator in any subtree. 48342956Sdillon */ 48442956Sdillon for (i = 1; i <= skip; i += next_skip) { 485321459Salc if (next_skip == 1) 48642956Sdillon scan[i].u.bmu_bitmap = (u_daddr_t)-1; 487321459Salc else 48842956Sdillon scan[i].u.bmu_avail = radix; 489321459Salc scan[i].bm_bighint = radix; 49042956Sdillon } 49142956Sdillon } else { 492109086Sdillon radix /= BLIST_META_RADIX; 49342956Sdillon } 49442956Sdillon 495321375Salc if (count > radix) { 496321375Salc /* 497321375Salc * The allocation exceeds the number of blocks that are 498321375Salc * managed by a subtree of this meta node. 499321375Salc */ 500321375Salc panic("allocation too large"); 501321375Salc } 502321459Salc scan_from_start = cursor == blk; 503321459Salc child = (cursor - blk) / radix; 504321459Salc blk += child * radix; 505321459Salc for (i = 1 + child * next_skip; i <= skip; i += next_skip) { 50642956Sdillon if (count <= scan[i].bm_bighint) { 50742956Sdillon /* 508321375Salc * The allocation might fit in the i'th subtree. 50942956Sdillon */ 51042956Sdillon if (next_skip == 1) { 511321459Salc r = blst_leaf_alloc(&scan[i], blk, count, 512321459Salc cursor > blk ? cursor : blk); 51342956Sdillon } else { 514321375Salc r = blst_meta_alloc(&scan[i], blk, count, 515321459Salc radix, next_skip - 1, cursor > blk ? 516321459Salc cursor : blk); 51742956Sdillon } 51842956Sdillon if (r != SWAPBLK_NONE) { 51942956Sdillon scan->u.bmu_avail -= count; 520321375Salc return (r); 52142956Sdillon } 52242956Sdillon } else if (scan[i].bm_bighint == (daddr_t)-1) { 52342956Sdillon /* 52442956Sdillon * Terminator 52542956Sdillon */ 52642956Sdillon break; 52742956Sdillon } 52842956Sdillon blk += radix; 52942956Sdillon } 53042956Sdillon 53142956Sdillon /* 53242956Sdillon * We couldn't allocate count in this subtree, update bighint. 53342956Sdillon */ 534321459Salc if (scan_from_start && scan->bm_bighint >= count) 53542956Sdillon scan->bm_bighint = count - 1; 536321459Salc 537321459Salc return (SWAPBLK_NONE); 53842956Sdillon} 53942956Sdillon 54042956Sdillon/* 54142956Sdillon * BLST_LEAF_FREE() - free allocated block from leaf bitmap 54242956Sdillon * 54342956Sdillon */ 54442956Sdillon 54542956Sdillonstatic void 54642956Sdillonblst_leaf_free( 54742956Sdillon blmeta_t *scan, 54842956Sdillon daddr_t blk, 54942956Sdillon int count 55042956Sdillon) { 55142956Sdillon /* 55242956Sdillon * free some data in this bitmap 55342956Sdillon * 55442956Sdillon * e.g. 55542956Sdillon * 0000111111111110000 55642956Sdillon * \_________/\__/ 55742956Sdillon * v n 55842956Sdillon */ 55942956Sdillon int n = blk & (BLIST_BMAP_RADIX - 1); 56042956Sdillon u_daddr_t mask; 56142956Sdillon 56242956Sdillon mask = ((u_daddr_t)-1 << n) & 56342956Sdillon ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 56442956Sdillon 56542956Sdillon if (scan->u.bmu_bitmap & mask) 56642956Sdillon panic("blst_radix_free: freeing free block"); 56742956Sdillon scan->u.bmu_bitmap |= mask; 56842956Sdillon 56942956Sdillon /* 57042956Sdillon * We could probably do a better job here. We are required to make 57142956Sdillon * bighint at least as large as the biggest contiguous block of 57242956Sdillon * data. If we just shoehorn it, a little extra overhead will 57342956Sdillon * be incured on the next allocation (but only that one typically). 57442956Sdillon */ 57542956Sdillon scan->bm_bighint = BLIST_BMAP_RADIX; 57642956Sdillon} 57742956Sdillon 57842956Sdillon/* 57942956Sdillon * BLST_META_FREE() - free allocated blocks from radix tree meta info 58042956Sdillon * 58142956Sdillon * This support routine frees a range of blocks from the bitmap. 58242956Sdillon * The range must be entirely enclosed by this radix node. If a 58342956Sdillon * meta node, we break the range down recursively to free blocks 58442956Sdillon * in subnodes (which means that this code can free an arbitrary 58542956Sdillon * range whereas the allocation code cannot allocate an arbitrary 58642956Sdillon * range). 58742956Sdillon */ 58842956Sdillon 58942956Sdillonstatic void 590321459Salcblst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix, 591321459Salc daddr_t skip, daddr_t blk) 592321459Salc{ 593321459Salc daddr_t i, next_skip, v; 594321459Salc int child; 59542956Sdillon 59642956Sdillon#if 0 597184205Sdes printf("free (%llx,%lld) FROM (%llx,%lld)\n", 598107913Sdillon (long long)freeBlk, (long long)count, 599107913Sdillon (long long)blk, (long long)radix 60042956Sdillon ); 60142956Sdillon#endif 602321459Salc next_skip = skip / BLIST_META_RADIX; 60342956Sdillon 60442956Sdillon if (scan->u.bmu_avail == 0) { 60542956Sdillon /* 60642956Sdillon * ALL-ALLOCATED special case, with possible 60742956Sdillon * shortcut to ALL-FREE special case. 60842956Sdillon */ 60942956Sdillon scan->u.bmu_avail = count; 61042956Sdillon scan->bm_bighint = count; 61142956Sdillon 61242956Sdillon if (count != radix) { 61342956Sdillon for (i = 1; i <= skip; i += next_skip) { 61442956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 61542956Sdillon break; 61642956Sdillon scan[i].bm_bighint = 0; 61742956Sdillon if (next_skip == 1) { 61842956Sdillon scan[i].u.bmu_bitmap = 0; 61942956Sdillon } else { 62042956Sdillon scan[i].u.bmu_avail = 0; 62142956Sdillon } 62242956Sdillon } 62342956Sdillon /* fall through */ 62442956Sdillon } 62542956Sdillon } else { 62642956Sdillon scan->u.bmu_avail += count; 62742956Sdillon /* scan->bm_bighint = radix; */ 62842956Sdillon } 62942956Sdillon 63042956Sdillon /* 63142956Sdillon * ALL-FREE special case. 63242956Sdillon */ 63342956Sdillon 63442956Sdillon if (scan->u.bmu_avail == radix) 63542956Sdillon return; 63642956Sdillon if (scan->u.bmu_avail > radix) 63796882Sjhb panic("blst_meta_free: freeing already free blocks (%lld) %lld/%lld", 63896882Sjhb (long long)count, (long long)scan->u.bmu_avail, 63996882Sjhb (long long)radix); 64042956Sdillon 64142956Sdillon /* 64242956Sdillon * Break the free down into its components 64342956Sdillon */ 64442956Sdillon 645109086Sdillon radix /= BLIST_META_RADIX; 64642956Sdillon 647321459Salc child = (freeBlk - blk) / radix; 648321459Salc blk += child * radix; 649321459Salc i = 1 + child * next_skip; 65042956Sdillon while (i <= skip && blk < freeBlk + count) { 65142956Sdillon v = blk + radix - freeBlk; 65242956Sdillon if (v > count) 65342956Sdillon v = count; 65442956Sdillon 65542956Sdillon if (scan->bm_bighint == (daddr_t)-1) 65642956Sdillon panic("blst_meta_free: freeing unexpected range"); 65742956Sdillon 65842956Sdillon if (next_skip == 1) { 65942956Sdillon blst_leaf_free(&scan[i], freeBlk, v); 66042956Sdillon } else { 66142956Sdillon blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 66242956Sdillon } 66342956Sdillon if (scan->bm_bighint < scan[i].bm_bighint) 66442956Sdillon scan->bm_bighint = scan[i].bm_bighint; 66542956Sdillon count -= v; 66642956Sdillon freeBlk += v; 66742956Sdillon blk += radix; 66842956Sdillon i += next_skip; 66942956Sdillon } 67042956Sdillon} 67142956Sdillon 67242956Sdillon/* 67342956Sdillon * BLIST_RADIX_COPY() - copy one radix tree to another 67442956Sdillon * 67542956Sdillon * Locates free space in the source tree and frees it in the destination 67642956Sdillon * tree. The space may not already be free in the destination. 67742956Sdillon */ 67842956Sdillon 67942956Sdillonstatic void blst_copy( 68042956Sdillon blmeta_t *scan, 68142956Sdillon daddr_t blk, 68242956Sdillon daddr_t radix, 68342956Sdillon daddr_t skip, 68442956Sdillon blist_t dest, 68542956Sdillon daddr_t count 68642956Sdillon) { 687321459Salc daddr_t i, next_skip; 68842956Sdillon 68942956Sdillon /* 69042956Sdillon * Leaf node 69142956Sdillon */ 69242956Sdillon 69342956Sdillon if (radix == BLIST_BMAP_RADIX) { 69442956Sdillon u_daddr_t v = scan->u.bmu_bitmap; 69542956Sdillon 69642956Sdillon if (v == (u_daddr_t)-1) { 69742956Sdillon blist_free(dest, blk, count); 69842956Sdillon } else if (v != 0) { 69942956Sdillon int i; 70042956Sdillon 70142956Sdillon for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { 702319965Salc if (v & ((u_daddr_t)1 << i)) 70342956Sdillon blist_free(dest, blk + i, 1); 70442956Sdillon } 70542956Sdillon } 70642956Sdillon return; 70742956Sdillon } 70842956Sdillon 70942956Sdillon /* 71042956Sdillon * Meta node 71142956Sdillon */ 71242956Sdillon 71342956Sdillon if (scan->u.bmu_avail == 0) { 71442956Sdillon /* 71542956Sdillon * Source all allocated, leave dest allocated 71642956Sdillon */ 71742956Sdillon return; 71842956Sdillon } 71942956Sdillon if (scan->u.bmu_avail == radix) { 72042956Sdillon /* 72142956Sdillon * Source all free, free entire dest 72242956Sdillon */ 72342956Sdillon if (count < radix) 72442956Sdillon blist_free(dest, blk, count); 72542956Sdillon else 72642956Sdillon blist_free(dest, blk, radix); 72742956Sdillon return; 72842956Sdillon } 72942956Sdillon 73042956Sdillon 731109086Sdillon radix /= BLIST_META_RADIX; 732321459Salc next_skip = skip / BLIST_META_RADIX; 73342956Sdillon 73442956Sdillon for (i = 1; count && i <= skip; i += next_skip) { 73542956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 73642956Sdillon break; 73742956Sdillon 73842956Sdillon if (count >= radix) { 73942956Sdillon blst_copy( 74042956Sdillon &scan[i], 74142956Sdillon blk, 74242956Sdillon radix, 74342956Sdillon next_skip - 1, 74442956Sdillon dest, 74542956Sdillon radix 74642956Sdillon ); 74742956Sdillon count -= radix; 74842956Sdillon } else { 74942956Sdillon if (count) { 75042956Sdillon blst_copy( 75142956Sdillon &scan[i], 75242956Sdillon blk, 75342956Sdillon radix, 75442956Sdillon next_skip - 1, 75542956Sdillon dest, 75642956Sdillon count 75742956Sdillon ); 75842956Sdillon } 75942956Sdillon count = 0; 76042956Sdillon } 76142956Sdillon blk += radix; 76242956Sdillon } 76342956Sdillon} 76442956Sdillon 76542956Sdillon/* 766107913Sdillon * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap 767107913Sdillon * 768107913Sdillon * This routine allocates all blocks in the specified range 769107913Sdillon * regardless of any existing allocations in that range. Returns 770107913Sdillon * the number of blocks allocated by the call. 771107913Sdillon */ 772107913Sdillon 773320622Salcstatic daddr_t 774107913Sdillonblst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) 775107913Sdillon{ 776107913Sdillon int n = blk & (BLIST_BMAP_RADIX - 1); 777320622Salc daddr_t nblks; 778321375Salc u_daddr_t mask; 779107913Sdillon 780107913Sdillon mask = ((u_daddr_t)-1 << n) & 781107913Sdillon ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 782107913Sdillon 783321375Salc /* Count the number of blocks that we are allocating. */ 784321375Salc nblks = bitcount64(scan->u.bmu_bitmap & mask); 785107913Sdillon 786107913Sdillon scan->u.bmu_bitmap &= ~mask; 787321375Salc return (nblks); 788107913Sdillon} 789107913Sdillon 790107913Sdillon/* 791107913Sdillon * BLIST_META_FILL() - allocate specific blocks at a meta node 792107913Sdillon * 793107913Sdillon * This routine allocates the specified range of blocks, 794107913Sdillon * regardless of any existing allocations in the range. The 795107913Sdillon * range must be within the extent of this node. Returns the 796107913Sdillon * number of blocks allocated by the call. 797107913Sdillon */ 798320622Salcstatic daddr_t 799321459Salcblst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, daddr_t radix, 800321459Salc daddr_t skip, daddr_t blk) 801321459Salc{ 802321459Salc daddr_t i, nblks, next_skip, v; 803321459Salc int child; 804107913Sdillon 805321375Salc if (count > radix) { 806321375Salc /* 807321375Salc * The allocation exceeds the number of blocks that are 808321375Salc * managed by this meta node. 809321375Salc */ 810321375Salc panic("allocation too large"); 811321375Salc } 812107913Sdillon if (count == radix || scan->u.bmu_avail == 0) { 813107913Sdillon /* 814107913Sdillon * ALL-ALLOCATED special case 815107913Sdillon */ 816107913Sdillon nblks = scan->u.bmu_avail; 817107913Sdillon scan->u.bmu_avail = 0; 818320622Salc scan->bm_bighint = 0; 819107913Sdillon return nblks; 820107913Sdillon } 821321459Salc next_skip = skip / BLIST_META_RADIX; 822107913Sdillon 823321375Salc /* 824321375Salc * An ALL-FREE meta node requires special handling before allocating 825321375Salc * any of its blocks. 826321375Salc */ 827107913Sdillon if (scan->u.bmu_avail == radix) { 828109086Sdillon radix /= BLIST_META_RADIX; 829107913Sdillon 830107913Sdillon /* 831321375Salc * Reinitialize each of the meta node's children. An ALL-FREE 832321375Salc * meta node cannot have a terminator in any subtree. 833107913Sdillon */ 834107913Sdillon for (i = 1; i <= skip; i += next_skip) { 835107913Sdillon if (next_skip == 1) { 836107913Sdillon scan[i].u.bmu_bitmap = (u_daddr_t)-1; 837107913Sdillon scan[i].bm_bighint = BLIST_BMAP_RADIX; 838107913Sdillon } else { 839107913Sdillon scan[i].bm_bighint = radix; 840107913Sdillon scan[i].u.bmu_avail = radix; 841107913Sdillon } 842107913Sdillon } 843107913Sdillon } else { 844109086Sdillon radix /= BLIST_META_RADIX; 845107913Sdillon } 846107913Sdillon 847321459Salc nblks = 0; 848321459Salc child = (allocBlk - blk) / radix; 849321459Salc blk += child * radix; 850321459Salc i = 1 + child * next_skip; 851107913Sdillon while (i <= skip && blk < allocBlk + count) { 852107913Sdillon v = blk + radix - allocBlk; 853107913Sdillon if (v > count) 854107913Sdillon v = count; 855107913Sdillon 856107913Sdillon if (scan->bm_bighint == (daddr_t)-1) 857107913Sdillon panic("blst_meta_fill: filling unexpected range"); 858107913Sdillon 859107913Sdillon if (next_skip == 1) { 860107913Sdillon nblks += blst_leaf_fill(&scan[i], allocBlk, v); 861107913Sdillon } else { 862107913Sdillon nblks += blst_meta_fill(&scan[i], allocBlk, v, 863107913Sdillon radix, next_skip - 1, blk); 864107913Sdillon } 865107913Sdillon count -= v; 866107913Sdillon allocBlk += v; 867107913Sdillon blk += radix; 868107913Sdillon i += next_skip; 869107913Sdillon } 870107913Sdillon scan->u.bmu_avail -= nblks; 871107913Sdillon return nblks; 872107913Sdillon} 873107913Sdillon 874107913Sdillon/* 87542956Sdillon * BLST_RADIX_INIT() - initialize radix tree 87642956Sdillon * 87742956Sdillon * Initialize our meta structures and bitmaps and calculate the exact 87842956Sdillon * amount of space required to manage 'count' blocks - this space may 879228233Seadler * be considerably less than the calculated radix due to the large 88042956Sdillon * RADIX values we use. 88142956Sdillon */ 88242956Sdillon 88342956Sdillonstatic daddr_t 884321459Salcblst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, daddr_t count) 88542956Sdillon{ 886321459Salc daddr_t i, memindex, next_skip; 88742956Sdillon 888321459Salc memindex = 0; 889321459Salc 89042956Sdillon /* 89142956Sdillon * Leaf node 89242956Sdillon */ 89342956Sdillon 89442956Sdillon if (radix == BLIST_BMAP_RADIX) { 89542956Sdillon if (scan) { 89642956Sdillon scan->bm_bighint = 0; 89742956Sdillon scan->u.bmu_bitmap = 0; 89842956Sdillon } 89942956Sdillon return(memindex); 90042956Sdillon } 90142956Sdillon 90242956Sdillon /* 90342956Sdillon * Meta node. If allocating the entire object we can special 90442956Sdillon * case it. However, we need to figure out how much memory 90542956Sdillon * is required to manage 'count' blocks, so we continue on anyway. 90642956Sdillon */ 90742956Sdillon 90842956Sdillon if (scan) { 90942956Sdillon scan->bm_bighint = 0; 91042956Sdillon scan->u.bmu_avail = 0; 91142956Sdillon } 91242956Sdillon 913109086Sdillon radix /= BLIST_META_RADIX; 914321459Salc next_skip = skip / BLIST_META_RADIX; 91542956Sdillon 91642956Sdillon for (i = 1; i <= skip; i += next_skip) { 91742956Sdillon if (count >= radix) { 91842956Sdillon /* 91942956Sdillon * Allocate the entire object 92042956Sdillon */ 92142956Sdillon memindex = i + blst_radix_init( 92242956Sdillon ((scan) ? &scan[i] : NULL), 92342956Sdillon radix, 92442956Sdillon next_skip - 1, 92542956Sdillon radix 92642956Sdillon ); 92742956Sdillon count -= radix; 92842956Sdillon } else if (count > 0) { 92942956Sdillon /* 93042956Sdillon * Allocate a partial object 93142956Sdillon */ 93242956Sdillon memindex = i + blst_radix_init( 93342956Sdillon ((scan) ? &scan[i] : NULL), 93442956Sdillon radix, 93542956Sdillon next_skip - 1, 93642956Sdillon count 93742956Sdillon ); 93842956Sdillon count = 0; 93942956Sdillon } else { 94042956Sdillon /* 94142956Sdillon * Add terminator and break out 94242956Sdillon */ 94342956Sdillon if (scan) 94442956Sdillon scan[i].bm_bighint = (daddr_t)-1; 94542956Sdillon break; 94642956Sdillon } 94742956Sdillon } 94842956Sdillon if (memindex < i) 94942956Sdillon memindex = i; 95042956Sdillon return(memindex); 95142956Sdillon} 95242956Sdillon 95342956Sdillon#ifdef BLIST_DEBUG 95442956Sdillon 95542956Sdillonstatic void 956321459Salcblst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, daddr_t skip, 957321459Salc int tab) 95842956Sdillon{ 959321459Salc daddr_t i, next_skip; 96042956Sdillon 96142956Sdillon if (radix == BLIST_BMAP_RADIX) { 96242956Sdillon printf( 963319965Salc "%*.*s(%08llx,%lld): bitmap %016llx big=%lld\n", 96442956Sdillon tab, tab, "", 965107913Sdillon (long long)blk, (long long)radix, 966107913Sdillon (long long)scan->u.bmu_bitmap, 967107913Sdillon (long long)scan->bm_bighint 96842956Sdillon ); 96942956Sdillon return; 97042956Sdillon } 97142956Sdillon 97242956Sdillon if (scan->u.bmu_avail == 0) { 97342956Sdillon printf( 974107913Sdillon "%*.*s(%08llx,%lld) ALL ALLOCATED\n", 97542956Sdillon tab, tab, "", 976107913Sdillon (long long)blk, 977107913Sdillon (long long)radix 97842956Sdillon ); 97942956Sdillon return; 98042956Sdillon } 98142956Sdillon if (scan->u.bmu_avail == radix) { 98242956Sdillon printf( 983107913Sdillon "%*.*s(%08llx,%lld) ALL FREE\n", 98442956Sdillon tab, tab, "", 985107913Sdillon (long long)blk, 986107913Sdillon (long long)radix 98742956Sdillon ); 98842956Sdillon return; 98942956Sdillon } 99042956Sdillon 99142956Sdillon printf( 992107913Sdillon "%*.*s(%08llx,%lld): subtree (%lld/%lld) big=%lld {\n", 99342956Sdillon tab, tab, "", 994107913Sdillon (long long)blk, (long long)radix, 995107913Sdillon (long long)scan->u.bmu_avail, 996107913Sdillon (long long)radix, 997107913Sdillon (long long)scan->bm_bighint 99842956Sdillon ); 99942956Sdillon 1000109086Sdillon radix /= BLIST_META_RADIX; 1001321459Salc next_skip = skip / BLIST_META_RADIX; 100242956Sdillon tab += 4; 100342956Sdillon 100442956Sdillon for (i = 1; i <= skip; i += next_skip) { 100542956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) { 100642956Sdillon printf( 1007107913Sdillon "%*.*s(%08llx,%lld): Terminator\n", 100842956Sdillon tab, tab, "", 1009107913Sdillon (long long)blk, (long long)radix 101042956Sdillon ); 101142956Sdillon break; 101242956Sdillon } 101342956Sdillon blst_radix_print( 101442956Sdillon &scan[i], 101542956Sdillon blk, 101642956Sdillon radix, 101742956Sdillon next_skip - 1, 101842956Sdillon tab 101942956Sdillon ); 102042956Sdillon blk += radix; 102142956Sdillon } 102242956Sdillon tab -= 4; 102342956Sdillon 102442956Sdillon printf( 102542956Sdillon "%*.*s}\n", 102642956Sdillon tab, tab, "" 102742956Sdillon ); 102842956Sdillon} 102942956Sdillon 103042956Sdillon#endif 103142956Sdillon 103242956Sdillon#ifdef BLIST_DEBUG 103342956Sdillon 103442956Sdillonint 103542956Sdillonmain(int ac, char **av) 103642956Sdillon{ 103742956Sdillon int size = 1024; 103842956Sdillon int i; 103942956Sdillon blist_t bl; 104042956Sdillon 104142956Sdillon for (i = 1; i < ac; ++i) { 104242956Sdillon const char *ptr = av[i]; 104342956Sdillon if (*ptr != '-') { 104442956Sdillon size = strtol(ptr, NULL, 0); 104542956Sdillon continue; 104642956Sdillon } 104742956Sdillon ptr += 2; 104842956Sdillon fprintf(stderr, "Bad option: %s\n", ptr - 2); 104942956Sdillon exit(1); 105042956Sdillon } 1051178792Skmacy bl = blist_create(size, M_WAITOK); 105242956Sdillon blist_free(bl, 0, size); 105342956Sdillon 105442956Sdillon for (;;) { 105542956Sdillon char buf[1024]; 1056319965Salc long long da = 0; 1057319965Salc long long count = 0; 105842956Sdillon 1059321375Salc printf("%lld/%lld/%lld> ", (long long)blist_avail(bl), 1060107913Sdillon (long long)size, (long long)bl->bl_radix); 106142956Sdillon fflush(stdout); 106242956Sdillon if (fgets(buf, sizeof(buf), stdin) == NULL) 106342956Sdillon break; 106442956Sdillon switch(buf[0]) { 106542956Sdillon case 'r': 1066107913Sdillon if (sscanf(buf + 1, "%lld", &count) == 1) { 1067319965Salc blist_resize(&bl, count, 1, M_WAITOK); 106842956Sdillon } else { 106942956Sdillon printf("?\n"); 107042956Sdillon } 107142956Sdillon case 'p': 107242956Sdillon blist_print(bl); 107342956Sdillon break; 107442956Sdillon case 'a': 1075107913Sdillon if (sscanf(buf + 1, "%lld", &count) == 1) { 107642956Sdillon daddr_t blk = blist_alloc(bl, count); 1077107913Sdillon printf(" R=%08llx\n", (long long)blk); 107842956Sdillon } else { 107942956Sdillon printf("?\n"); 108042956Sdillon } 108142956Sdillon break; 108242956Sdillon case 'f': 1083319965Salc if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { 108442956Sdillon blist_free(bl, da, count); 108542956Sdillon } else { 108642956Sdillon printf("?\n"); 108742956Sdillon } 108842956Sdillon break; 1089107913Sdillon case 'l': 1090319965Salc if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { 1091320622Salc printf(" n=%jd\n", 1092320622Salc (intmax_t)blist_fill(bl, da, count)); 1093107913Sdillon } else { 1094107913Sdillon printf("?\n"); 1095107913Sdillon } 1096107913Sdillon break; 109742956Sdillon case '?': 109842956Sdillon case 'h': 109942956Sdillon puts( 110042956Sdillon "p -print\n" 110142956Sdillon "a %d -allocate\n" 110242956Sdillon "f %x %d -free\n" 1103107913Sdillon "l %x %d -fill\n" 110442956Sdillon "r %d -resize\n" 110542956Sdillon "h/? -help" 110642956Sdillon ); 110742956Sdillon break; 110842956Sdillon default: 110942956Sdillon printf("?\n"); 111042956Sdillon break; 111142956Sdillon } 111242956Sdillon } 111342956Sdillon return(0); 111442956Sdillon} 111542956Sdillon 111642956Sdillonvoid 111742956Sdillonpanic(const char *ctl, ...) 111842956Sdillon{ 111942956Sdillon va_list va; 112042956Sdillon 112142956Sdillon va_start(va, ctl); 112242956Sdillon vfprintf(stderr, ctl, va); 112342956Sdillon fprintf(stderr, "\n"); 112442956Sdillon va_end(va); 112542956Sdillon exit(1); 112642956Sdillon} 112742956Sdillon 112842956Sdillon#endif 112942956Sdillon 1130