blist.h revision 42956
142956Sdillon/* 242956Sdillon * Copyright (c) 1998 Matthew Dillon. Terms of use and redistribution in all 342956Sdillon * forms are covered by the BSD copyright in the file "/usr/src/COPYRIGHT". 442956Sdillon * 542956Sdillon * Implements bitmap resource lists. 642956Sdillon * 742956Sdillon * Usage: 842956Sdillon * blist = blist_create(blocks) 942956Sdillon * (void) blist_destroy(blist) 1042956Sdillon * blkno = blist_alloc(blist, count) 1142956Sdillon * (void) blist_free(blist, blkno, count) 1242956Sdillon * (void) blist_resize(&blist, count, freeextra) 1342956Sdillon * 1442956Sdillon * 1542956Sdillon * Notes: 1642956Sdillon * on creation, the entire list is marked reserved. You should 1742956Sdillon * first blist_free() the sections you want to make available 1842956Sdillon * for allocation before doing general blist_alloc()/free() 1942956Sdillon * ops. 2042956Sdillon * 2142956Sdillon * SWAPBLK_NONE is returned on failure. This module is typically 2242956Sdillon * capable of managing up to (2^31) blocks per blist, though 2342956Sdillon * the memory utilization would be insane if you actually did 2442956Sdillon * that. Managing something like 512MB worth of 4K blocks 2542956Sdillon * eats around 32 KBytes of memory. 2642956Sdillon * 2742956Sdillon * $Id: blist.h,v Exp $ 2842956Sdillon */ 2942956Sdillon 3042956Sdillon#ifndef _SYS_BLIST_H_ 3142956Sdillon#define _SYS_BLIST_H_ 3242956Sdillon 3342956Sdillon#define LOG2(v) (((u_daddr_t)(v) >= 0x80000000U) ? 31 : \ 3442956Sdillon ((u_daddr_t)(v) >= 0x40000000U) ? 30 : \ 3542956Sdillon ((u_daddr_t)(v) >= 0x20000000U) ? 29 : \ 3642956Sdillon ((u_daddr_t)(v) >= 0x10000000U) ? 28 : \ 3742956Sdillon ((u_daddr_t)(v) >= 0x08000000U) ? 27 : \ 3842956Sdillon ((u_daddr_t)(v) >= 0x04000000U) ? 26 : \ 3942956Sdillon ((u_daddr_t)(v) >= 0x02000000U) ? 25 : \ 4042956Sdillon ((u_daddr_t)(v) >= 0x01000000U) ? 24 : \ 4142956Sdillon ((u_daddr_t)(v) >= 0x00800000U) ? 23 : \ 4242956Sdillon ((u_daddr_t)(v) >= 0x00400000U) ? 22 : \ 4342956Sdillon ((u_daddr_t)(v) >= 0x00200000U) ? 21 : \ 4442956Sdillon ((u_daddr_t)(v) >= 0x00100000U) ? 20 : \ 4542956Sdillon ((u_daddr_t)(v) >= 0x00080000U) ? 19 : \ 4642956Sdillon ((u_daddr_t)(v) >= 0x00040000U) ? 18 : \ 4742956Sdillon ((u_daddr_t)(v) >= 0x00020000U) ? 17 : \ 4842956Sdillon ((u_daddr_t)(v) >= 0x00010000U) ? 16 : \ 4942956Sdillon ((u_daddr_t)(v) >= 0x00008000U) ? 15 : \ 5042956Sdillon ((u_daddr_t)(v) >= 0x00004000U) ? 14 : \ 5142956Sdillon ((u_daddr_t)(v) >= 0x00002000U) ? 13 : \ 5242956Sdillon ((u_daddr_t)(v) >= 0x00001000U) ? 12 : \ 5342956Sdillon ((u_daddr_t)(v) >= 0x00000800U) ? 11 : \ 5442956Sdillon ((u_daddr_t)(v) >= 0x00000400U) ? 10 : \ 5542956Sdillon ((u_daddr_t)(v) >= 0x00000200U) ? 9 : \ 5642956Sdillon ((u_daddr_t)(v) >= 0x00000100U) ? 8 : \ 5742956Sdillon ((u_daddr_t)(v) >= 0x00000080U) ? 7 : \ 5842956Sdillon ((u_daddr_t)(v) >= 0x00000040U) ? 6 : \ 5942956Sdillon ((u_daddr_t)(v) >= 0x00000020U) ? 5 : \ 6042956Sdillon ((u_daddr_t)(v) >= 0x00000010U) ? 4 : \ 6142956Sdillon ((u_daddr_t)(v) >= 0x00000008U) ? 3 : \ 6242956Sdillon ((u_daddr_t)(v) >= 0x00000004U) ? 2 : \ 6342956Sdillon ((u_daddr_t)(v) >= 0x00000002U) ? 1 : 0) 6442956Sdillon 6542956Sdillon/* 6642956Sdillon * blmeta and bl_bitmap_t MUST be a power of 2 in size. 6742956Sdillon */ 6842956Sdillon 6942956Sdillontypedef struct blmeta { 7042956Sdillon union { 7142956Sdillon daddr_t bmu_avail; /* space available under us */ 7242956Sdillon u_daddr_t bmu_bitmap; /* bitmap if we are a leaf */ 7342956Sdillon } u; 7442956Sdillon daddr_t bm_bighint; /* biggest contiguous block hint*/ 7542956Sdillon} blmeta_t; 7642956Sdillon 7742956Sdillontypedef struct blist { 7842956Sdillon daddr_t bl_blocks; /* area of coverage */ 7942956Sdillon daddr_t bl_radix; /* coverage radix */ 8042956Sdillon daddr_t bl_skip; /* starting skip */ 8142956Sdillon daddr_t bl_free; /* number of free blocks */ 8242956Sdillon blmeta_t *bl_root; /* root of radix tree */ 8342956Sdillon daddr_t bl_rootblks; /* daddr_t blks allocated for tree */ 8442956Sdillon} *blist_t; 8542956Sdillon 8642956Sdillon#define BLIST_META_RADIX 16 8742956Sdillon#define BLIST_META_RADIX_SHIFT LOG2(BLIST_META_RADIX) 8842956Sdillon#define BLIST_BMAP_RADIX (sizeof(u_daddr_t)*8) 8942956Sdillon#define BLIST_BMAP_RADIX_SHIFT LOG2(BLIST_BMAP_RADIX) 9042956Sdillon 9142956Sdillon#define BLIST_MAX_ALLOC BLIST_BMAP_RADIX 9242956Sdillon 9342956Sdillonextern blist_t blist_create(daddr_t blocks); 9442956Sdillonextern void blist_destroy(blist_t blist); 9542956Sdillonextern daddr_t blist_alloc(blist_t blist, daddr_t count); 9642956Sdillonextern void blist_free(blist_t blist, daddr_t blkno, daddr_t count); 9742956Sdillonextern void blist_print(blist_t blist); 9842956Sdillonextern void blist_resize(blist_t *pblist, daddr_t count, int freenew); 9942956Sdillon 10042956Sdillon#endif /* _SYS_BLIST_H_ */ 10142956Sdillon 102