blist.h revision 319965
193020Snsouch/*- 293020Snsouch * Copyright (c) 1998 Matthew Dillon. All Rights Reserved. 393020Snsouch * Redistribution and use in source and binary forms, with or without 493020Snsouch * modification, are permitted provided that the following conditions 593020Snsouch * are met: 693020Snsouch * 1. Redistributions of source code must retain the above copyright 793020Snsouch * notice, this list of conditions and the following disclaimer. 893020Snsouch * 2. Redistributions in binary form must reproduce the above copyright 993020Snsouch * notice, this list of conditions and the following disclaimer in the 1093020Snsouch * documentation and/or other materials provided with the distribution. 1193020Snsouch * 4. Neither the name of the University nor the names of its contributors 1293020Snsouch * may be used to endorse or promote products derived from this software 1393020Snsouch * without specific prior written permission. 1493020Snsouch * 1593020Snsouch * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 1693020Snsouch * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 1793020Snsouch * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1893020Snsouch * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 1993020Snsouch * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2093020Snsouch * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 2193020Snsouch * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2293020Snsouch * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 2393020Snsouch * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 2493020Snsouch * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 2593020Snsouch * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2693020Snsouch */ 2795118Snsouch 28203692Sgavin/* 2993020Snsouch * Implements bitmap resource lists. 3093020Snsouch * 3193020Snsouch * Usage: 3293020Snsouch * blist = blist_create(blocks, flags) 3393020Snsouch * (void) blist_destroy(blist) 3493020Snsouch * blkno = blist_alloc(blist, count) 3593020Snsouch * (void) blist_free(blist, blkno, count) 3693020Snsouch * nblks = blist_fill(blist, blkno, count) 3793020Snsouch * (void) blist_resize(&blist, count, freeextra, flags) 3893020Snsouch * 3993020Snsouch * 4093020Snsouch * Notes: 4193020Snsouch * on creation, the entire list is marked reserved. You should 4297589Sru * first blist_free() the sections you want to make available 4397589Sru * for allocation before doing general blist_alloc()/free() 4497589Sru * ops. 4595118Snsouch * 4693020Snsouch * SWAPBLK_NONE is returned on failure. This module is typically 4793020Snsouch * capable of managing up to (2^63) blocks per blist, though 4893020Snsouch * the memory utilization would be insane if you actually did 4993020Snsouch * that. Managing something like 512MB worth of 4K blocks 5095118Snsouch * eats around 32 KBytes of memory. 51103356Sceri * 5293020Snsouch * $FreeBSD: stable/10/sys/sys/blist.h 319965 2017-06-15 03:58:23Z alc $ 5393020Snsouch 5493020Snsouch */ 5593020Snsouch 5693020Snsouch#ifndef _SYS_BLIST_H_ 5797589Sru#define _SYS_BLIST_H_ 5895118Snsouch 5995118Snsouchtypedef uint64_t u_daddr_t; /* unsigned disk address */ 6097589Sru 6197589Sru/* 6293020Snsouch * note: currently use SWAPBLK_NONE as an absolute value rather then 6393020Snsouch * a flag bit. 6493020Snsouch */ 6595118Snsouch 6695118Snsouch#define SWAPBLK_MASK ((daddr_t)((u_daddr_t)-1 >> 1)) /* mask */ 6793020Snsouch#define SWAPBLK_NONE ((daddr_t)((u_daddr_t)SWAPBLK_MASK + 1))/* flag */ 6893020Snsouch 6993020Snsouch/* 7097589Sru * blmeta and bl_bitmap_t MUST be a power of 2 in size. 7193020Snsouch */ 7293020Snsouch 73typedef struct blmeta { 74 union { 75 daddr_t bmu_avail; /* space available under us */ 76 u_daddr_t bmu_bitmap; /* bitmap if we are a leaf */ 77 } u; 78 daddr_t bm_bighint; /* biggest contiguous block hint*/ 79} blmeta_t; 80 81typedef struct blist { 82 daddr_t bl_blocks; /* area of coverage */ 83 daddr_t bl_radix; /* coverage radix */ 84 daddr_t bl_skip; /* starting skip */ 85 daddr_t bl_free; /* number of free blocks */ 86 blmeta_t *bl_root; /* root of radix tree */ 87 daddr_t bl_rootblks; /* daddr_t blks allocated for tree */ 88} *blist_t; 89 90#define BLIST_META_RADIX 16 91#define BLIST_BMAP_RADIX (sizeof(u_daddr_t)*8) 92 93#define BLIST_MAX_ALLOC BLIST_BMAP_RADIX 94 95extern blist_t blist_create(daddr_t blocks, int flags); 96extern void blist_destroy(blist_t blist); 97extern daddr_t blist_alloc(blist_t blist, daddr_t count); 98extern void blist_free(blist_t blist, daddr_t blkno, daddr_t count); 99extern int blist_fill(blist_t bl, daddr_t blkno, daddr_t count); 100extern void blist_print(blist_t blist); 101extern void blist_resize(blist_t *pblist, daddr_t count, int freenew, int flags); 102 103#endif /* _SYS_BLIST_H_ */ 104 105