blist.h revision 321459
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: 32178792Skmacy * blist = blist_create(blocks, flags) 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) 37178792Skmacy * (void) blist_resize(&blist, count, freeextra, flags) 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 47319965Salc * capable of managing up to (2^63) 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: stable/10/sys/sys/blist.h 321459 2017-07-25 04:13:43Z alc $ 53178792Skmacy 5442956Sdillon */ 5542956Sdillon 5642956Sdillon#ifndef _SYS_BLIST_H_ 5742956Sdillon#define _SYS_BLIST_H_ 5842956Sdillon 59319965Salctypedef uint64_t u_daddr_t; /* unsigned disk address */ 6096849Sphk 6142956Sdillon/* 62130049Salc * note: currently use SWAPBLK_NONE as an absolute value rather then 63130049Salc * a flag bit. 64130049Salc */ 65130049Salc 66130049Salc#define SWAPBLK_MASK ((daddr_t)((u_daddr_t)-1 >> 1)) /* mask */ 67130049Salc#define SWAPBLK_NONE ((daddr_t)((u_daddr_t)SWAPBLK_MASK + 1))/* flag */ 68130049Salc 69130049Salc/* 70321365Salc * Both blmeta and bmu_bitmap MUST be a power of 2 in size. 7142956Sdillon */ 7242956Sdillon 7342956Sdillontypedef struct blmeta { 7442956Sdillon union { 7542956Sdillon daddr_t bmu_avail; /* space available under us */ 7642956Sdillon u_daddr_t bmu_bitmap; /* bitmap if we are a leaf */ 7742956Sdillon } u; 7842956Sdillon daddr_t bm_bighint; /* biggest contiguous block hint*/ 7942956Sdillon} blmeta_t; 8042956Sdillon 8142956Sdillontypedef struct blist { 8242956Sdillon daddr_t bl_blocks; /* area of coverage */ 8342956Sdillon daddr_t bl_radix; /* coverage radix */ 8442956Sdillon daddr_t bl_skip; /* starting skip */ 85321459Salc daddr_t bl_cursor; /* next-fit search starts at */ 8642956Sdillon blmeta_t *bl_root; /* root of radix 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 94321365Salcdaddr_t blist_alloc(blist_t blist, daddr_t count); 95321375Salcdaddr_t blist_avail(blist_t blist); 96321365Salcblist_t blist_create(daddr_t blocks, int flags); 97321365Salcvoid blist_destroy(blist_t blist); 98321365Salcdaddr_t blist_fill(blist_t bl, daddr_t blkno, daddr_t count); 99321365Salcvoid blist_free(blist_t blist, daddr_t blkno, daddr_t count); 100321365Salcvoid blist_print(blist_t blist); 101321365Salcvoid blist_resize(blist_t *pblist, daddr_t count, int freenew, int flags); 10242956Sdillon 10342956Sdillon#endif /* _SYS_BLIST_H_ */ 10442956Sdillon 105