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 32229832Seadler * 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 * 55246708Spluknet * The blist code wires all necessary memory at creation time. Neither 56246708Spluknet * allocations nor frees require interaction with the memory subsystem. 57246708Spluknet * The non-blocking features of the blist code are used in the swap code 58246708Spluknet * (vm/swap_pager.c). 5942956Sdillon * 6042956Sdillon * LAYOUT: The radix tree is layed out recursively using a 6142956Sdillon * linear array. Each meta node is immediately followed (layed 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 * 71229832Seadler * 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$"); 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#define SWAPBLK_NONE ((daddr_t)-1) 10342956Sdillon 10442956Sdillon#include <sys/types.h> 10542956Sdillon#include <stdio.h> 10642956Sdillon#include <string.h> 10742956Sdillon#include <stdlib.h> 10842956Sdillon#include <stdarg.h> 10942956Sdillon 110107913Sdillon#define malloc(a,b,c) calloc(a, 1) 11142956Sdillon#define free(a,b) free(a) 11242956Sdillon 11342956Sdillontypedef unsigned int u_daddr_t; 11442956Sdillon 11542956Sdillon#include <sys/blist.h> 11642956Sdillon 11742956Sdillonvoid panic(const char *ctl, ...); 11842956Sdillon 11942956Sdillon#endif 12042956Sdillon 12142956Sdillon/* 12242956Sdillon * static support functions 12342956Sdillon */ 12442956Sdillon 12542956Sdillonstatic daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count); 12642956Sdillonstatic daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, 12742956Sdillon daddr_t count, daddr_t radix, int skip); 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, 13042956Sdillon daddr_t radix, int 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); 133107913Sdillonstatic int blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); 134107913Sdillonstatic int blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, 135107913Sdillon daddr_t radix, int skip, daddr_t blk); 13642956Sdillonstatic daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, 13742956Sdillon int skip, daddr_t count); 13855206Speter#ifndef _KERNEL 13942956Sdillonstatic void blst_radix_print(blmeta_t *scan, daddr_t blk, 14042956Sdillon daddr_t radix, int 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 * 151229832Seadler * 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; 16242956Sdillon int radix; 16342956Sdillon int skip = 0; 16442956Sdillon 16542956Sdillon /* 16642956Sdillon * Calculate radix and skip field used for scanning. 16742956Sdillon */ 16842956Sdillon radix = BLIST_BMAP_RADIX; 16942956Sdillon 17042956Sdillon while (radix < blocks) { 171109086Sdillon radix *= BLIST_META_RADIX; 172109086Sdillon skip = (skip + 1) * BLIST_META_RADIX; 17342956Sdillon } 17442956Sdillon 175178792Skmacy bl = malloc(sizeof(struct blist), M_SWAP, flags | M_ZERO); 17642956Sdillon 17742956Sdillon bl->bl_blocks = blocks; 17842956Sdillon bl->bl_radix = radix; 17942956Sdillon bl->bl_skip = skip; 18042956Sdillon bl->bl_rootblks = 1 + 18142956Sdillon blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); 182178792Skmacy bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, flags); 18342956Sdillon 18442956Sdillon#if defined(BLIST_DEBUG) 18542956Sdillon printf( 186107913Sdillon "BLIST representing %lld blocks (%lld MB of swap)" 187107913Sdillon ", requiring %lldK of ram\n", 188107913Sdillon (long long)bl->bl_blocks, 189107913Sdillon (long long)bl->bl_blocks * 4 / 1024, 190107913Sdillon (long long)(bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 19142956Sdillon ); 192107913Sdillon printf("BLIST raw radix tree contains %lld records\n", 193107913Sdillon (long long)bl->bl_rootblks); 19442956Sdillon#endif 19542956Sdillon blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); 19642956Sdillon 19742956Sdillon return(bl); 19842956Sdillon} 19942956Sdillon 20042956Sdillonvoid 20142956Sdillonblist_destroy(blist_t bl) 20242956Sdillon{ 20342956Sdillon free(bl->bl_root, M_SWAP); 20442956Sdillon free(bl, M_SWAP); 20542956Sdillon} 20642956Sdillon 20742956Sdillon/* 20842956Sdillon * blist_alloc() - reserve space in the block bitmap. Return the base 20942956Sdillon * of a contiguous region or SWAPBLK_NONE if space could 21042956Sdillon * not be allocated. 21142956Sdillon */ 21242956Sdillon 21342956Sdillondaddr_t 21442956Sdillonblist_alloc(blist_t bl, daddr_t count) 21542956Sdillon{ 21642956Sdillon daddr_t blk = SWAPBLK_NONE; 21742956Sdillon 21842956Sdillon if (bl) { 21942956Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 22042956Sdillon blk = blst_leaf_alloc(bl->bl_root, 0, count); 22142956Sdillon else 22242956Sdillon blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); 22342956Sdillon if (blk != SWAPBLK_NONE) 22442956Sdillon bl->bl_free -= count; 22542956Sdillon } 22642956Sdillon return(blk); 22742956Sdillon} 22842956Sdillon 22942956Sdillon/* 23042956Sdillon * blist_free() - free up space in the block bitmap. Return the base 23142956Sdillon * of a contiguous region. Panic if an inconsistancy is 23242956Sdillon * found. 23342956Sdillon */ 23442956Sdillon 23542956Sdillonvoid 23642956Sdillonblist_free(blist_t bl, daddr_t blkno, daddr_t count) 23742956Sdillon{ 23842956Sdillon if (bl) { 23942956Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 24042956Sdillon blst_leaf_free(bl->bl_root, blkno, count); 24142956Sdillon else 24242956Sdillon blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); 24342956Sdillon bl->bl_free += count; 24442956Sdillon } 24542956Sdillon} 24642956Sdillon 24742956Sdillon/* 248107913Sdillon * blist_fill() - mark a region in the block bitmap as off-limits 249107913Sdillon * to the allocator (i.e. allocate it), ignoring any 250107913Sdillon * existing allocations. Return the number of blocks 251107913Sdillon * actually filled that were free before the call. 252107913Sdillon */ 253107913Sdillon 254107913Sdillonint 255107913Sdillonblist_fill(blist_t bl, daddr_t blkno, daddr_t count) 256107913Sdillon{ 257107913Sdillon int filled; 258107913Sdillon 259107913Sdillon if (bl) { 260107913Sdillon if (bl->bl_radix == BLIST_BMAP_RADIX) 261107913Sdillon filled = blst_leaf_fill(bl->bl_root, blkno, count); 262107913Sdillon else 263107913Sdillon filled = blst_meta_fill(bl->bl_root, blkno, count, 264107913Sdillon bl->bl_radix, bl->bl_skip, 0); 265107913Sdillon bl->bl_free -= filled; 266107913Sdillon return filled; 267107913Sdillon } else 268107913Sdillon return 0; 269107913Sdillon} 270107913Sdillon 271107913Sdillon/* 27242956Sdillon * blist_resize() - resize an existing radix tree to handle the 27342956Sdillon * specified number of blocks. This will reallocate 27442956Sdillon * the tree and transfer the previous bitmap to the new 27542956Sdillon * one. When extending the tree you can specify whether 27642956Sdillon * the new blocks are to left allocated or freed. 27742956Sdillon */ 27842956Sdillon 27942956Sdillonvoid 280178792Skmacyblist_resize(blist_t *pbl, daddr_t count, int freenew, int flags) 28142956Sdillon{ 282178792Skmacy blist_t newbl = blist_create(count, flags); 28342956Sdillon blist_t save = *pbl; 28442956Sdillon 28542956Sdillon *pbl = newbl; 28642956Sdillon if (count > save->bl_blocks) 28742956Sdillon count = save->bl_blocks; 28842956Sdillon blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); 28942956Sdillon 29042956Sdillon /* 29142956Sdillon * If resizing upwards, should we free the new space or not? 29242956Sdillon */ 29342956Sdillon if (freenew && count < newbl->bl_blocks) { 29442956Sdillon blist_free(newbl, count, newbl->bl_blocks - count); 29542956Sdillon } 29642956Sdillon blist_destroy(save); 29742956Sdillon} 29842956Sdillon 29942956Sdillon#ifdef BLIST_DEBUG 30042956Sdillon 30142956Sdillon/* 30242956Sdillon * blist_print() - dump radix tree 30342956Sdillon */ 30442956Sdillon 30542956Sdillonvoid 30642956Sdillonblist_print(blist_t bl) 30742956Sdillon{ 30842956Sdillon printf("BLIST {\n"); 30942956Sdillon blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); 31042956Sdillon printf("}\n"); 31142956Sdillon} 31242956Sdillon 31342956Sdillon#endif 31442956Sdillon 31542956Sdillon/************************************************************************ 31642956Sdillon * ALLOCATION SUPPORT FUNCTIONS * 31742956Sdillon ************************************************************************ 31842956Sdillon * 31942956Sdillon * These support functions do all the actual work. They may seem 32042956Sdillon * rather longish, but that's because I've commented them up. The 32142956Sdillon * actual code is straight forward. 32242956Sdillon * 32342956Sdillon */ 32442956Sdillon 32542956Sdillon/* 32642956Sdillon * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). 32742956Sdillon * 32842956Sdillon * This is the core of the allocator and is optimized for the 1 block 32942956Sdillon * and the BLIST_BMAP_RADIX block allocation cases. Other cases are 33042956Sdillon * somewhat slower. The 1 block allocation case is log2 and extremely 33142956Sdillon * quick. 33242956Sdillon */ 33342956Sdillon 33442956Sdillonstatic daddr_t 33542956Sdillonblst_leaf_alloc( 33642956Sdillon blmeta_t *scan, 33742956Sdillon daddr_t blk, 33842956Sdillon int count 33942956Sdillon) { 34042956Sdillon u_daddr_t orig = scan->u.bmu_bitmap; 34142956Sdillon 34242956Sdillon if (orig == 0) { 34342956Sdillon /* 34442956Sdillon * Optimize bitmap all-allocated case. Also, count = 1 34542956Sdillon * case assumes at least 1 bit is free in the bitmap, so 34642956Sdillon * we have to take care of this case here. 34742956Sdillon */ 34842956Sdillon scan->bm_bighint = 0; 34942956Sdillon return(SWAPBLK_NONE); 35042956Sdillon } 35142956Sdillon if (count == 1) { 35242956Sdillon /* 35342956Sdillon * Optimized code to allocate one bit out of the bitmap 35442956Sdillon */ 35542956Sdillon u_daddr_t mask; 35642956Sdillon int j = BLIST_BMAP_RADIX/2; 35742956Sdillon int r = 0; 35842956Sdillon 35942956Sdillon mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX/2); 36042956Sdillon 36142956Sdillon while (j) { 36242956Sdillon if ((orig & mask) == 0) { 36342956Sdillon r += j; 36442956Sdillon orig >>= j; 36542956Sdillon } 36642956Sdillon j >>= 1; 36742956Sdillon mask >>= j; 36842956Sdillon } 36942956Sdillon scan->u.bmu_bitmap &= ~(1 << r); 37042956Sdillon return(blk + r); 37142956Sdillon } 37242956Sdillon if (count <= BLIST_BMAP_RADIX) { 37342956Sdillon /* 37442956Sdillon * non-optimized code to allocate N bits out of the bitmap. 37542956Sdillon * The more bits, the faster the code runs. It will run 37642956Sdillon * the slowest allocating 2 bits, but since there aren't any 37742956Sdillon * memory ops in the core loop (or shouldn't be, anyway), 37842956Sdillon * you probably won't notice the difference. 37942956Sdillon */ 38042956Sdillon int j; 38142956Sdillon int n = BLIST_BMAP_RADIX - count; 38242956Sdillon u_daddr_t mask; 38342956Sdillon 38442956Sdillon mask = (u_daddr_t)-1 >> n; 38542956Sdillon 38642956Sdillon for (j = 0; j <= n; ++j) { 38742956Sdillon if ((orig & mask) == mask) { 38842956Sdillon scan->u.bmu_bitmap &= ~mask; 38942956Sdillon return(blk + j); 39042956Sdillon } 39142956Sdillon mask = (mask << 1); 39242956Sdillon } 39342956Sdillon } 39442956Sdillon /* 39542956Sdillon * We couldn't allocate count in this subtree, update bighint. 39642956Sdillon */ 39742956Sdillon scan->bm_bighint = count - 1; 39842956Sdillon return(SWAPBLK_NONE); 39942956Sdillon} 40042956Sdillon 40142956Sdillon/* 40242956Sdillon * blist_meta_alloc() - allocate at a meta in the radix tree. 40342956Sdillon * 40442956Sdillon * Attempt to allocate at a meta node. If we can't, we update 40542956Sdillon * bighint and return a failure. Updating bighint optimize future 40642956Sdillon * calls that hit this node. We have to check for our collapse cases 40742956Sdillon * and we have a few optimizations strewn in as well. 40842956Sdillon */ 40942956Sdillon 41042956Sdillonstatic daddr_t 41142956Sdillonblst_meta_alloc( 41242956Sdillon blmeta_t *scan, 41342956Sdillon daddr_t blk, 41442956Sdillon daddr_t count, 41542956Sdillon daddr_t radix, 41642956Sdillon int skip 41742956Sdillon) { 41842956Sdillon int i; 419109086Sdillon int next_skip = ((u_int)skip / BLIST_META_RADIX); 42042956Sdillon 42142956Sdillon if (scan->u.bmu_avail == 0) { 42242956Sdillon /* 42342956Sdillon * ALL-ALLOCATED special case 42442956Sdillon */ 42542956Sdillon scan->bm_bighint = count; 42642956Sdillon return(SWAPBLK_NONE); 42742956Sdillon } 42842956Sdillon 42942956Sdillon if (scan->u.bmu_avail == radix) { 430109086Sdillon radix /= BLIST_META_RADIX; 43142956Sdillon 43242956Sdillon /* 43342956Sdillon * ALL-FREE special case, initialize uninitialize 43442956Sdillon * sublevel. 43542956Sdillon */ 43642956Sdillon for (i = 1; i <= skip; i += next_skip) { 43742956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 43842956Sdillon break; 43942956Sdillon if (next_skip == 1) { 44042956Sdillon scan[i].u.bmu_bitmap = (u_daddr_t)-1; 44142956Sdillon scan[i].bm_bighint = BLIST_BMAP_RADIX; 44242956Sdillon } else { 44342956Sdillon scan[i].bm_bighint = radix; 44442956Sdillon scan[i].u.bmu_avail = radix; 44542956Sdillon } 44642956Sdillon } 44742956Sdillon } else { 448109086Sdillon radix /= BLIST_META_RADIX; 44942956Sdillon } 45042956Sdillon 45142956Sdillon for (i = 1; i <= skip; i += next_skip) { 45242956Sdillon if (count <= scan[i].bm_bighint) { 45342956Sdillon /* 45442956Sdillon * count fits in object 45542956Sdillon */ 45642956Sdillon daddr_t r; 45742956Sdillon if (next_skip == 1) { 45842956Sdillon r = blst_leaf_alloc(&scan[i], blk, count); 45942956Sdillon } else { 46042956Sdillon r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); 46142956Sdillon } 46242956Sdillon if (r != SWAPBLK_NONE) { 46342956Sdillon scan->u.bmu_avail -= count; 46442956Sdillon if (scan->bm_bighint > scan->u.bmu_avail) 46542956Sdillon scan->bm_bighint = scan->u.bmu_avail; 46642956Sdillon return(r); 46742956Sdillon } 46842956Sdillon } else if (scan[i].bm_bighint == (daddr_t)-1) { 46942956Sdillon /* 47042956Sdillon * Terminator 47142956Sdillon */ 47242956Sdillon break; 47342956Sdillon } else if (count > radix) { 47442956Sdillon /* 47542956Sdillon * count does not fit in object even if it were 47642956Sdillon * complete free. 47742956Sdillon */ 47842956Sdillon panic("blist_meta_alloc: allocation too large"); 47942956Sdillon } 48042956Sdillon blk += radix; 48142956Sdillon } 48242956Sdillon 48342956Sdillon /* 48442956Sdillon * We couldn't allocate count in this subtree, update bighint. 48542956Sdillon */ 48642956Sdillon if (scan->bm_bighint >= count) 48742956Sdillon scan->bm_bighint = count - 1; 48842956Sdillon return(SWAPBLK_NONE); 48942956Sdillon} 49042956Sdillon 49142956Sdillon/* 49242956Sdillon * BLST_LEAF_FREE() - free allocated block from leaf bitmap 49342956Sdillon * 49442956Sdillon */ 49542956Sdillon 49642956Sdillonstatic void 49742956Sdillonblst_leaf_free( 49842956Sdillon blmeta_t *scan, 49942956Sdillon daddr_t blk, 50042956Sdillon int count 50142956Sdillon) { 50242956Sdillon /* 50342956Sdillon * free some data in this bitmap 50442956Sdillon * 50542956Sdillon * e.g. 50642956Sdillon * 0000111111111110000 50742956Sdillon * \_________/\__/ 50842956Sdillon * v n 50942956Sdillon */ 51042956Sdillon int n = blk & (BLIST_BMAP_RADIX - 1); 51142956Sdillon u_daddr_t mask; 51242956Sdillon 51342956Sdillon mask = ((u_daddr_t)-1 << n) & 51442956Sdillon ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 51542956Sdillon 51642956Sdillon if (scan->u.bmu_bitmap & mask) 51742956Sdillon panic("blst_radix_free: freeing free block"); 51842956Sdillon scan->u.bmu_bitmap |= mask; 51942956Sdillon 52042956Sdillon /* 52142956Sdillon * We could probably do a better job here. We are required to make 52242956Sdillon * bighint at least as large as the biggest contiguous block of 52342956Sdillon * data. If we just shoehorn it, a little extra overhead will 52442956Sdillon * be incured on the next allocation (but only that one typically). 52542956Sdillon */ 52642956Sdillon scan->bm_bighint = BLIST_BMAP_RADIX; 52742956Sdillon} 52842956Sdillon 52942956Sdillon/* 53042956Sdillon * BLST_META_FREE() - free allocated blocks from radix tree meta info 53142956Sdillon * 53242956Sdillon * This support routine frees a range of blocks from the bitmap. 53342956Sdillon * The range must be entirely enclosed by this radix node. If a 53442956Sdillon * meta node, we break the range down recursively to free blocks 53542956Sdillon * in subnodes (which means that this code can free an arbitrary 53642956Sdillon * range whereas the allocation code cannot allocate an arbitrary 53742956Sdillon * range). 53842956Sdillon */ 53942956Sdillon 54042956Sdillonstatic void 54142956Sdillonblst_meta_free( 54242956Sdillon blmeta_t *scan, 54342956Sdillon daddr_t freeBlk, 54442956Sdillon daddr_t count, 54542956Sdillon daddr_t radix, 54642956Sdillon int skip, 54742956Sdillon daddr_t blk 54842956Sdillon) { 54942956Sdillon int i; 550109086Sdillon int next_skip = ((u_int)skip / BLIST_META_RADIX); 55142956Sdillon 55242956Sdillon#if 0 553184205Sdes printf("free (%llx,%lld) FROM (%llx,%lld)\n", 554107913Sdillon (long long)freeBlk, (long long)count, 555107913Sdillon (long long)blk, (long long)radix 55642956Sdillon ); 55742956Sdillon#endif 55842956Sdillon 55942956Sdillon if (scan->u.bmu_avail == 0) { 56042956Sdillon /* 56142956Sdillon * ALL-ALLOCATED special case, with possible 56242956Sdillon * shortcut to ALL-FREE special case. 56342956Sdillon */ 56442956Sdillon scan->u.bmu_avail = count; 56542956Sdillon scan->bm_bighint = count; 56642956Sdillon 56742956Sdillon if (count != radix) { 56842956Sdillon for (i = 1; i <= skip; i += next_skip) { 56942956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 57042956Sdillon break; 57142956Sdillon scan[i].bm_bighint = 0; 57242956Sdillon if (next_skip == 1) { 57342956Sdillon scan[i].u.bmu_bitmap = 0; 57442956Sdillon } else { 57542956Sdillon scan[i].u.bmu_avail = 0; 57642956Sdillon } 57742956Sdillon } 57842956Sdillon /* fall through */ 57942956Sdillon } 58042956Sdillon } else { 58142956Sdillon scan->u.bmu_avail += count; 58242956Sdillon /* scan->bm_bighint = radix; */ 58342956Sdillon } 58442956Sdillon 58542956Sdillon /* 58642956Sdillon * ALL-FREE special case. 58742956Sdillon */ 58842956Sdillon 58942956Sdillon if (scan->u.bmu_avail == radix) 59042956Sdillon return; 59142956Sdillon if (scan->u.bmu_avail > radix) 59296882Sjhb panic("blst_meta_free: freeing already free blocks (%lld) %lld/%lld", 59396882Sjhb (long long)count, (long long)scan->u.bmu_avail, 59496882Sjhb (long long)radix); 59542956Sdillon 59642956Sdillon /* 59742956Sdillon * Break the free down into its components 59842956Sdillon */ 59942956Sdillon 600109086Sdillon radix /= BLIST_META_RADIX; 60142956Sdillon 60242956Sdillon i = (freeBlk - blk) / radix; 60342956Sdillon blk += i * radix; 60442956Sdillon i = i * next_skip + 1; 60542956Sdillon 60642956Sdillon while (i <= skip && blk < freeBlk + count) { 60742956Sdillon daddr_t v; 60842956Sdillon 60942956Sdillon v = blk + radix - freeBlk; 61042956Sdillon if (v > count) 61142956Sdillon v = count; 61242956Sdillon 61342956Sdillon if (scan->bm_bighint == (daddr_t)-1) 61442956Sdillon panic("blst_meta_free: freeing unexpected range"); 61542956Sdillon 61642956Sdillon if (next_skip == 1) { 61742956Sdillon blst_leaf_free(&scan[i], freeBlk, v); 61842956Sdillon } else { 61942956Sdillon blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); 62042956Sdillon } 62142956Sdillon if (scan->bm_bighint < scan[i].bm_bighint) 62242956Sdillon scan->bm_bighint = scan[i].bm_bighint; 62342956Sdillon count -= v; 62442956Sdillon freeBlk += v; 62542956Sdillon blk += radix; 62642956Sdillon i += next_skip; 62742956Sdillon } 62842956Sdillon} 62942956Sdillon 63042956Sdillon/* 63142956Sdillon * BLIST_RADIX_COPY() - copy one radix tree to another 63242956Sdillon * 63342956Sdillon * Locates free space in the source tree and frees it in the destination 63442956Sdillon * tree. The space may not already be free in the destination. 63542956Sdillon */ 63642956Sdillon 63742956Sdillonstatic void blst_copy( 63842956Sdillon blmeta_t *scan, 63942956Sdillon daddr_t blk, 64042956Sdillon daddr_t radix, 64142956Sdillon daddr_t skip, 64242956Sdillon blist_t dest, 64342956Sdillon daddr_t count 64442956Sdillon) { 64542956Sdillon int next_skip; 64642956Sdillon int i; 64742956Sdillon 64842956Sdillon /* 64942956Sdillon * Leaf node 65042956Sdillon */ 65142956Sdillon 65242956Sdillon if (radix == BLIST_BMAP_RADIX) { 65342956Sdillon u_daddr_t v = scan->u.bmu_bitmap; 65442956Sdillon 65542956Sdillon if (v == (u_daddr_t)-1) { 65642956Sdillon blist_free(dest, blk, count); 65742956Sdillon } else if (v != 0) { 65842956Sdillon int i; 65942956Sdillon 66042956Sdillon for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { 66142956Sdillon if (v & (1 << i)) 66242956Sdillon blist_free(dest, blk + i, 1); 66342956Sdillon } 66442956Sdillon } 66542956Sdillon return; 66642956Sdillon } 66742956Sdillon 66842956Sdillon /* 66942956Sdillon * Meta node 67042956Sdillon */ 67142956Sdillon 67242956Sdillon if (scan->u.bmu_avail == 0) { 67342956Sdillon /* 67442956Sdillon * Source all allocated, leave dest allocated 67542956Sdillon */ 67642956Sdillon return; 67742956Sdillon } 67842956Sdillon if (scan->u.bmu_avail == radix) { 67942956Sdillon /* 68042956Sdillon * Source all free, free entire dest 68142956Sdillon */ 68242956Sdillon if (count < radix) 68342956Sdillon blist_free(dest, blk, count); 68442956Sdillon else 68542956Sdillon blist_free(dest, blk, radix); 68642956Sdillon return; 68742956Sdillon } 68842956Sdillon 68942956Sdillon 690109086Sdillon radix /= BLIST_META_RADIX; 691109086Sdillon next_skip = ((u_int)skip / BLIST_META_RADIX); 69242956Sdillon 69342956Sdillon for (i = 1; count && i <= skip; i += next_skip) { 69442956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 69542956Sdillon break; 69642956Sdillon 69742956Sdillon if (count >= radix) { 69842956Sdillon blst_copy( 69942956Sdillon &scan[i], 70042956Sdillon blk, 70142956Sdillon radix, 70242956Sdillon next_skip - 1, 70342956Sdillon dest, 70442956Sdillon radix 70542956Sdillon ); 70642956Sdillon count -= radix; 70742956Sdillon } else { 70842956Sdillon if (count) { 70942956Sdillon blst_copy( 71042956Sdillon &scan[i], 71142956Sdillon blk, 71242956Sdillon radix, 71342956Sdillon next_skip - 1, 71442956Sdillon dest, 71542956Sdillon count 71642956Sdillon ); 71742956Sdillon } 71842956Sdillon count = 0; 71942956Sdillon } 72042956Sdillon blk += radix; 72142956Sdillon } 72242956Sdillon} 72342956Sdillon 72442956Sdillon/* 725107913Sdillon * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap 726107913Sdillon * 727107913Sdillon * This routine allocates all blocks in the specified range 728107913Sdillon * regardless of any existing allocations in that range. Returns 729107913Sdillon * the number of blocks allocated by the call. 730107913Sdillon */ 731107913Sdillon 732107913Sdillonstatic int 733107913Sdillonblst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) 734107913Sdillon{ 735107913Sdillon int n = blk & (BLIST_BMAP_RADIX - 1); 736107913Sdillon int nblks; 737107913Sdillon u_daddr_t mask, bitmap; 738107913Sdillon 739107913Sdillon mask = ((u_daddr_t)-1 << n) & 740107913Sdillon ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); 741107913Sdillon 742107913Sdillon /* Count the number of blocks we're about to allocate */ 743107913Sdillon bitmap = scan->u.bmu_bitmap & mask; 744107913Sdillon for (nblks = 0; bitmap != 0; nblks++) 745107913Sdillon bitmap &= bitmap - 1; 746107913Sdillon 747107913Sdillon scan->u.bmu_bitmap &= ~mask; 748107913Sdillon return nblks; 749107913Sdillon} 750107913Sdillon 751107913Sdillon/* 752107913Sdillon * BLIST_META_FILL() - allocate specific blocks at a meta node 753107913Sdillon * 754107913Sdillon * This routine allocates the specified range of blocks, 755107913Sdillon * regardless of any existing allocations in the range. The 756107913Sdillon * range must be within the extent of this node. Returns the 757107913Sdillon * number of blocks allocated by the call. 758107913Sdillon */ 759107913Sdillonstatic int 760107913Sdillonblst_meta_fill( 761107913Sdillon blmeta_t *scan, 762107913Sdillon daddr_t allocBlk, 763107913Sdillon daddr_t count, 764107913Sdillon daddr_t radix, 765107913Sdillon int skip, 766107913Sdillon daddr_t blk 767107913Sdillon) { 768107913Sdillon int i; 769109086Sdillon int next_skip = ((u_int)skip / BLIST_META_RADIX); 770107913Sdillon int nblks = 0; 771107913Sdillon 772107913Sdillon if (count == radix || scan->u.bmu_avail == 0) { 773107913Sdillon /* 774107913Sdillon * ALL-ALLOCATED special case 775107913Sdillon */ 776107913Sdillon nblks = scan->u.bmu_avail; 777107913Sdillon scan->u.bmu_avail = 0; 778107913Sdillon scan->bm_bighint = count; 779107913Sdillon return nblks; 780107913Sdillon } 781107913Sdillon 782107913Sdillon if (scan->u.bmu_avail == radix) { 783109086Sdillon radix /= BLIST_META_RADIX; 784107913Sdillon 785107913Sdillon /* 786107913Sdillon * ALL-FREE special case, initialize sublevel 787107913Sdillon */ 788107913Sdillon for (i = 1; i <= skip; i += next_skip) { 789107913Sdillon if (scan[i].bm_bighint == (daddr_t)-1) 790107913Sdillon break; 791107913Sdillon if (next_skip == 1) { 792107913Sdillon scan[i].u.bmu_bitmap = (u_daddr_t)-1; 793107913Sdillon scan[i].bm_bighint = BLIST_BMAP_RADIX; 794107913Sdillon } else { 795107913Sdillon scan[i].bm_bighint = radix; 796107913Sdillon scan[i].u.bmu_avail = radix; 797107913Sdillon } 798107913Sdillon } 799107913Sdillon } else { 800109086Sdillon radix /= BLIST_META_RADIX; 801107913Sdillon } 802107913Sdillon 803107913Sdillon if (count > radix) 804107913Sdillon panic("blist_meta_fill: allocation too large"); 805107913Sdillon 806107913Sdillon i = (allocBlk - blk) / radix; 807107913Sdillon blk += i * radix; 808107913Sdillon i = i * next_skip + 1; 809107913Sdillon 810107913Sdillon while (i <= skip && blk < allocBlk + count) { 811107913Sdillon daddr_t v; 812107913Sdillon 813107913Sdillon v = blk + radix - allocBlk; 814107913Sdillon if (v > count) 815107913Sdillon v = count; 816107913Sdillon 817107913Sdillon if (scan->bm_bighint == (daddr_t)-1) 818107913Sdillon panic("blst_meta_fill: filling unexpected range"); 819107913Sdillon 820107913Sdillon if (next_skip == 1) { 821107913Sdillon nblks += blst_leaf_fill(&scan[i], allocBlk, v); 822107913Sdillon } else { 823107913Sdillon nblks += blst_meta_fill(&scan[i], allocBlk, v, 824107913Sdillon radix, next_skip - 1, blk); 825107913Sdillon } 826107913Sdillon count -= v; 827107913Sdillon allocBlk += v; 828107913Sdillon blk += radix; 829107913Sdillon i += next_skip; 830107913Sdillon } 831107913Sdillon scan->u.bmu_avail -= nblks; 832107913Sdillon return nblks; 833107913Sdillon} 834107913Sdillon 835107913Sdillon/* 83642956Sdillon * BLST_RADIX_INIT() - initialize radix tree 83742956Sdillon * 83842956Sdillon * Initialize our meta structures and bitmaps and calculate the exact 83942956Sdillon * amount of space required to manage 'count' blocks - this space may 840229832Seadler * be considerably less than the calculated radix due to the large 84142956Sdillon * RADIX values we use. 84242956Sdillon */ 84342956Sdillon 84442956Sdillonstatic daddr_t 84542956Sdillonblst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) 84642956Sdillon{ 84742956Sdillon int i; 84842956Sdillon int next_skip; 84942956Sdillon daddr_t memindex = 0; 85042956Sdillon 85142956Sdillon /* 85242956Sdillon * Leaf node 85342956Sdillon */ 85442956Sdillon 85542956Sdillon if (radix == BLIST_BMAP_RADIX) { 85642956Sdillon if (scan) { 85742956Sdillon scan->bm_bighint = 0; 85842956Sdillon scan->u.bmu_bitmap = 0; 85942956Sdillon } 86042956Sdillon return(memindex); 86142956Sdillon } 86242956Sdillon 86342956Sdillon /* 86442956Sdillon * Meta node. If allocating the entire object we can special 86542956Sdillon * case it. However, we need to figure out how much memory 86642956Sdillon * is required to manage 'count' blocks, so we continue on anyway. 86742956Sdillon */ 86842956Sdillon 86942956Sdillon if (scan) { 87042956Sdillon scan->bm_bighint = 0; 87142956Sdillon scan->u.bmu_avail = 0; 87242956Sdillon } 87342956Sdillon 874109086Sdillon radix /= BLIST_META_RADIX; 875109086Sdillon next_skip = ((u_int)skip / BLIST_META_RADIX); 87642956Sdillon 87742956Sdillon for (i = 1; i <= skip; i += next_skip) { 87842956Sdillon if (count >= radix) { 87942956Sdillon /* 88042956Sdillon * Allocate the entire object 88142956Sdillon */ 88242956Sdillon memindex = i + blst_radix_init( 88342956Sdillon ((scan) ? &scan[i] : NULL), 88442956Sdillon radix, 88542956Sdillon next_skip - 1, 88642956Sdillon radix 88742956Sdillon ); 88842956Sdillon count -= radix; 88942956Sdillon } else if (count > 0) { 89042956Sdillon /* 89142956Sdillon * Allocate a partial object 89242956Sdillon */ 89342956Sdillon memindex = i + blst_radix_init( 89442956Sdillon ((scan) ? &scan[i] : NULL), 89542956Sdillon radix, 89642956Sdillon next_skip - 1, 89742956Sdillon count 89842956Sdillon ); 89942956Sdillon count = 0; 90042956Sdillon } else { 90142956Sdillon /* 90242956Sdillon * Add terminator and break out 90342956Sdillon */ 90442956Sdillon if (scan) 90542956Sdillon scan[i].bm_bighint = (daddr_t)-1; 90642956Sdillon break; 90742956Sdillon } 90842956Sdillon } 90942956Sdillon if (memindex < i) 91042956Sdillon memindex = i; 91142956Sdillon return(memindex); 91242956Sdillon} 91342956Sdillon 91442956Sdillon#ifdef BLIST_DEBUG 91542956Sdillon 91642956Sdillonstatic void 91742956Sdillonblst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) 91842956Sdillon{ 91942956Sdillon int i; 92042956Sdillon int next_skip; 92142956Sdillon int lastState = 0; 92242956Sdillon 92342956Sdillon if (radix == BLIST_BMAP_RADIX) { 92442956Sdillon printf( 925107913Sdillon "%*.*s(%08llx,%lld): bitmap %08llx big=%lld\n", 92642956Sdillon tab, tab, "", 927107913Sdillon (long long)blk, (long long)radix, 928107913Sdillon (long long)scan->u.bmu_bitmap, 929107913Sdillon (long long)scan->bm_bighint 93042956Sdillon ); 93142956Sdillon return; 93242956Sdillon } 93342956Sdillon 93442956Sdillon if (scan->u.bmu_avail == 0) { 93542956Sdillon printf( 936107913Sdillon "%*.*s(%08llx,%lld) ALL ALLOCATED\n", 93742956Sdillon tab, tab, "", 938107913Sdillon (long long)blk, 939107913Sdillon (long long)radix 94042956Sdillon ); 94142956Sdillon return; 94242956Sdillon } 94342956Sdillon if (scan->u.bmu_avail == radix) { 94442956Sdillon printf( 945107913Sdillon "%*.*s(%08llx,%lld) ALL FREE\n", 94642956Sdillon tab, tab, "", 947107913Sdillon (long long)blk, 948107913Sdillon (long long)radix 94942956Sdillon ); 95042956Sdillon return; 95142956Sdillon } 95242956Sdillon 95342956Sdillon printf( 954107913Sdillon "%*.*s(%08llx,%lld): subtree (%lld/%lld) big=%lld {\n", 95542956Sdillon tab, tab, "", 956107913Sdillon (long long)blk, (long long)radix, 957107913Sdillon (long long)scan->u.bmu_avail, 958107913Sdillon (long long)radix, 959107913Sdillon (long long)scan->bm_bighint 96042956Sdillon ); 96142956Sdillon 962109086Sdillon radix /= BLIST_META_RADIX; 963109086Sdillon next_skip = ((u_int)skip / BLIST_META_RADIX); 96442956Sdillon tab += 4; 96542956Sdillon 96642956Sdillon for (i = 1; i <= skip; i += next_skip) { 96742956Sdillon if (scan[i].bm_bighint == (daddr_t)-1) { 96842956Sdillon printf( 969107913Sdillon "%*.*s(%08llx,%lld): Terminator\n", 97042956Sdillon tab, tab, "", 971107913Sdillon (long long)blk, (long long)radix 97242956Sdillon ); 97342956Sdillon lastState = 0; 97442956Sdillon break; 97542956Sdillon } 97642956Sdillon blst_radix_print( 97742956Sdillon &scan[i], 97842956Sdillon blk, 97942956Sdillon radix, 98042956Sdillon next_skip - 1, 98142956Sdillon tab 98242956Sdillon ); 98342956Sdillon blk += radix; 98442956Sdillon } 98542956Sdillon tab -= 4; 98642956Sdillon 98742956Sdillon printf( 98842956Sdillon "%*.*s}\n", 98942956Sdillon tab, tab, "" 99042956Sdillon ); 99142956Sdillon} 99242956Sdillon 99342956Sdillon#endif 99442956Sdillon 99542956Sdillon#ifdef BLIST_DEBUG 99642956Sdillon 99742956Sdillonint 99842956Sdillonmain(int ac, char **av) 99942956Sdillon{ 100042956Sdillon int size = 1024; 100142956Sdillon int i; 100242956Sdillon blist_t bl; 100342956Sdillon 100442956Sdillon for (i = 1; i < ac; ++i) { 100542956Sdillon const char *ptr = av[i]; 100642956Sdillon if (*ptr != '-') { 100742956Sdillon size = strtol(ptr, NULL, 0); 100842956Sdillon continue; 100942956Sdillon } 101042956Sdillon ptr += 2; 101142956Sdillon fprintf(stderr, "Bad option: %s\n", ptr - 2); 101242956Sdillon exit(1); 101342956Sdillon } 1014178792Skmacy bl = blist_create(size, M_WAITOK); 101542956Sdillon blist_free(bl, 0, size); 101642956Sdillon 101742956Sdillon for (;;) { 101842956Sdillon char buf[1024]; 101942956Sdillon daddr_t da = 0; 102042956Sdillon daddr_t count = 0; 102142956Sdillon 102242956Sdillon 1023107913Sdillon printf("%lld/%lld/%lld> ", (long long)bl->bl_free, 1024107913Sdillon (long long)size, (long long)bl->bl_radix); 102542956Sdillon fflush(stdout); 102642956Sdillon if (fgets(buf, sizeof(buf), stdin) == NULL) 102742956Sdillon break; 102842956Sdillon switch(buf[0]) { 102942956Sdillon case 'r': 1030107913Sdillon if (sscanf(buf + 1, "%lld", &count) == 1) { 103142956Sdillon blist_resize(&bl, count, 1); 103242956Sdillon } else { 103342956Sdillon printf("?\n"); 103442956Sdillon } 103542956Sdillon case 'p': 103642956Sdillon blist_print(bl); 103742956Sdillon break; 103842956Sdillon case 'a': 1039107913Sdillon if (sscanf(buf + 1, "%lld", &count) == 1) { 104042956Sdillon daddr_t blk = blist_alloc(bl, count); 1041107913Sdillon printf(" R=%08llx\n", (long long)blk); 104242956Sdillon } else { 104342956Sdillon printf("?\n"); 104442956Sdillon } 104542956Sdillon break; 104642956Sdillon case 'f': 1047107913Sdillon if (sscanf(buf + 1, "%llx %lld", 1048107913Sdillon (long long *)&da, (long long *)&count) == 2) { 104942956Sdillon blist_free(bl, da, count); 105042956Sdillon } else { 105142956Sdillon printf("?\n"); 105242956Sdillon } 105342956Sdillon break; 1054107913Sdillon case 'l': 1055107913Sdillon if (sscanf(buf + 1, "%llx %lld", 1056107913Sdillon (long long *)&da, (long long *)&count) == 2) { 1057107913Sdillon printf(" n=%d\n", 1058107913Sdillon blist_fill(bl, da, count)); 1059107913Sdillon } else { 1060107913Sdillon printf("?\n"); 1061107913Sdillon } 1062107913Sdillon break; 106342956Sdillon case '?': 106442956Sdillon case 'h': 106542956Sdillon puts( 106642956Sdillon "p -print\n" 106742956Sdillon "a %d -allocate\n" 106842956Sdillon "f %x %d -free\n" 1069107913Sdillon "l %x %d -fill\n" 107042956Sdillon "r %d -resize\n" 107142956Sdillon "h/? -help" 107242956Sdillon ); 107342956Sdillon break; 107442956Sdillon default: 107542956Sdillon printf("?\n"); 107642956Sdillon break; 107742956Sdillon } 107842956Sdillon } 107942956Sdillon return(0); 108042956Sdillon} 108142956Sdillon 108242956Sdillonvoid 108342956Sdillonpanic(const char *ctl, ...) 108442956Sdillon{ 108542956Sdillon va_list va; 108642956Sdillon 108742956Sdillon va_start(va, ctl); 108842956Sdillon vfprintf(stderr, ctl, va); 108942956Sdillon fprintf(stderr, "\n"); 109042956Sdillon va_end(va); 109142956Sdillon exit(1); 109242956Sdillon} 109342956Sdillon 109442956Sdillon#endif 109542956Sdillon 1096