blist.h revision 139825
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. 1442956Sdillon * 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. 26139825Simp */ 27139825Simp 28139825Simp/* 2942956Sdillon * Implements bitmap resource lists. 3042956Sdillon * 3142956Sdillon * Usage: 3242956Sdillon * blist = blist_create(blocks) 3342956Sdillon * (void) blist_destroy(blist) 3442956Sdillon * blkno = blist_alloc(blist, count) 3542956Sdillon * (void) blist_free(blist, blkno, count) 36107913Sdillon * nblks = blist_fill(blist, blkno, count) 3742956Sdillon * (void) blist_resize(&blist, count, freeextra) 3842956Sdillon * 3942956Sdillon * 4042956Sdillon * Notes: 4142956Sdillon * on creation, the entire list is marked reserved. You should 4242956Sdillon * first blist_free() the sections you want to make available 4342956Sdillon * for allocation before doing general blist_alloc()/free() 4442956Sdillon * ops. 4542956Sdillon * 4642956Sdillon * SWAPBLK_NONE is returned on failure. This module is typically 4742956Sdillon * capable of managing up to (2^31) blocks per blist, though 4842956Sdillon * the memory utilization would be insane if you actually did 4942956Sdillon * that. Managing something like 512MB worth of 4K blocks 5042956Sdillon * eats around 32 KBytes of memory. 5142956Sdillon * 5250477Speter * $FreeBSD: head/sys/sys/blist.h 139825 2005-01-07 02:29:27Z imp $ 5342956Sdillon */ 5442956Sdillon 5542956Sdillon#ifndef _SYS_BLIST_H_ 5642956Sdillon#define _SYS_BLIST_H_ 5742956Sdillon 5896849Sphktypedef u_int32_t u_daddr_t; /* unsigned disk address */ 5996849Sphk 6042956Sdillon/* 61130049Salc * note: currently use SWAPBLK_NONE as an absolute value rather then 62130049Salc * a flag bit. 63130049Salc */ 64130049Salc 65130049Salc#define SWAPBLK_MASK ((daddr_t)((u_daddr_t)-1 >> 1)) /* mask */ 66130049Salc#define SWAPBLK_NONE ((daddr_t)((u_daddr_t)SWAPBLK_MASK + 1))/* flag */ 67130049Salc 68130049Salc/* 6942956Sdillon * blmeta and bl_bitmap_t MUST be a power of 2 in size. 7042956Sdillon */ 7142956Sdillon 7242956Sdillontypedef struct blmeta { 7342956Sdillon union { 7442956Sdillon daddr_t bmu_avail; /* space available under us */ 7542956Sdillon u_daddr_t bmu_bitmap; /* bitmap if we are a leaf */ 7642956Sdillon } u; 7742956Sdillon daddr_t bm_bighint; /* biggest contiguous block hint*/ 7842956Sdillon} blmeta_t; 7942956Sdillon 8042956Sdillontypedef struct blist { 8142956Sdillon daddr_t bl_blocks; /* area of coverage */ 8242956Sdillon daddr_t bl_radix; /* coverage radix */ 8342956Sdillon daddr_t bl_skip; /* starting skip */ 8442956Sdillon daddr_t bl_free; /* number of free blocks */ 8542956Sdillon blmeta_t *bl_root; /* root of radix tree */ 8642956Sdillon daddr_t bl_rootblks; /* daddr_t blks allocated for tree */ 8742956Sdillon} *blist_t; 8842956Sdillon 8942956Sdillon#define BLIST_META_RADIX 16 9042956Sdillon#define BLIST_BMAP_RADIX (sizeof(u_daddr_t)*8) 9142956Sdillon 9242956Sdillon#define BLIST_MAX_ALLOC BLIST_BMAP_RADIX 9342956Sdillon 9442956Sdillonextern blist_t blist_create(daddr_t blocks); 9542956Sdillonextern void blist_destroy(blist_t blist); 9642956Sdillonextern daddr_t blist_alloc(blist_t blist, daddr_t count); 9742956Sdillonextern void blist_free(blist_t blist, daddr_t blkno, daddr_t count); 98107913Sdillonextern int blist_fill(blist_t bl, daddr_t blkno, daddr_t count); 9942956Sdillonextern void blist_print(blist_t blist); 10042956Sdillonextern void blist_resize(blist_t *pblist, daddr_t count, int freenew); 10142956Sdillon 10242956Sdillon#endif /* _SYS_BLIST_H_ */ 10342956Sdillon 104