Commit | Line | Data |
---|---|---|
984263bc | 1 | /* |
8c10bfcf MD |
2 | * Copyright (c) 2003,2004 The DragonFly Project. All rights reserved. |
3 | * | |
4 | * This code is derived from software contributed to The DragonFly Project | |
5 | * by Matthew Dillon <dillon@backplane.com> | |
6 | * | |
7 | * Redistribution and use in source and binary forms, with or without | |
8 | * modification, are permitted provided that the following conditions | |
9 | * are met: | |
10 | * | |
11 | * 1. Redistributions of source code must retain the above copyright | |
12 | * notice, this list of conditions and the following disclaimer. | |
13 | * 2. Redistributions in binary form must reproduce the above copyright | |
14 | * notice, this list of conditions and the following disclaimer in | |
15 | * the documentation and/or other materials provided with the | |
16 | * distribution. | |
17 | * 3. Neither the name of The DragonFly Project nor the names of its | |
18 | * contributors may be used to endorse or promote products derived | |
19 | * from this software without specific, prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
22 | * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
23 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |
24 | * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |
25 | * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | |
26 | * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, | |
27 | * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
28 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | |
29 | * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, | |
30 | * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT | |
31 | * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
32 | * SUCH DAMAGE. | |
33 | * | |
984263bc MD |
34 | * Implements bitmap resource lists. |
35 | * | |
36 | * Usage: | |
37 | * blist = blist_create(blocks) | |
38 | * (void) blist_destroy(blist) | |
39 | * blkno = blist_alloc(blist, count) | |
40 | * (void) blist_free(blist, blkno, count) | |
9f3543c6 | 41 | * nblks = blist_fill(blist, blkno, count) |
984263bc MD |
42 | * (void) blist_resize(&blist, count, freeextra) |
43 | * | |
44 | * | |
45 | * Notes: | |
46 | * on creation, the entire list is marked reserved. You should | |
47 | * first blist_free() the sections you want to make available | |
48 | * for allocation before doing general blist_alloc()/free() | |
49 | * ops. | |
50 | * | |
51 | * SWAPBLK_NONE is returned on failure. This module is typically | |
52 | * capable of managing up to (2^31) blocks per blist, though | |
53 | * the memory utilization would be insane if you actually did | |
54 | * that. Managing something like 512MB worth of 4K blocks | |
55 | * eats around 32 KBytes of memory. | |
56 | * | |
57 | * $FreeBSD: src/sys/sys/blist.h,v 1.2.2.1 2003/01/12 09:23:12 dillon Exp $ | |
58 | */ | |
59 | ||
60 | #ifndef _SYS_BLIST_H_ | |
61 | #define _SYS_BLIST_H_ | |
62 | ||
1bd40720 MD |
63 | #ifndef _SYS_TYPES_H_ |
64 | #include <sys/types.h> | |
65 | #endif | |
66 | ||
534ee349 MD |
67 | #define SWBLK_BITS 64 |
68 | typedef int64_t swblk_t; | |
69 | typedef u_int64_t u_swblk_t; | |
35d5bbd3 | 70 | |
651d8e75 MD |
71 | /* |
72 | * note: currently use SWAPBLK_NONE as an absolute value rather then | |
73 | * a flag bit. | |
74 | */ | |
75 | #define SWAPBLK_MASK ((swblk_t)((u_swblk_t)-1 >> 1)) /* mask */ | |
76 | #define SWAPBLK_NONE ((swblk_t)((u_swblk_t)SWAPBLK_MASK + 1))/* flag */ | |
77 | ||
984263bc MD |
78 | /* |
79 | * blmeta and bl_bitmap_t MUST be a power of 2 in size. | |
80 | */ | |
81 | ||
82 | typedef struct blmeta { | |
83 | union { | |
35d5bbd3 MD |
84 | swblk_t bmu_avail; /* space available under us */ |
85 | u_swblk_t bmu_bitmap; /* bitmap if we are a leaf */ | |
984263bc | 86 | } u; |
35d5bbd3 | 87 | swblk_t bm_bighint; /* biggest contiguous block hint*/ |
984263bc MD |
88 | } blmeta_t; |
89 | ||
90 | typedef struct blist { | |
35d5bbd3 | 91 | swblk_t bl_blocks; /* area of coverage */ |
79634a66 | 92 | int64_t bl_radix; /* coverage radix */ |
35d5bbd3 MD |
93 | swblk_t bl_skip; /* starting skip */ |
94 | swblk_t bl_free; /* number of free blocks */ | |
984263bc | 95 | blmeta_t *bl_root; /* root of radix tree */ |
35d5bbd3 | 96 | swblk_t bl_rootblks; /* swblk_t blks allocated for tree */ |
984263bc MD |
97 | } *blist_t; |
98 | ||
534ee349 MD |
99 | #define BLIST_META_RADIX (sizeof(u_swblk_t)*8/2) /* 2 bits per */ |
100 | #define BLIST_BMAP_RADIX (sizeof(u_swblk_t)*8) /* 1 bit per */ | |
984263bc | 101 | |
79634a66 | 102 | /* |
534ee349 MD |
103 | * The radix may exceed the size of a 64 bit signed (or unsigned) int |
104 | * when the maximal number of blocks is allocated. With a 32-bit swblk_t | |
105 | * this corresponds to ~1G x PAGE_SIZE = 4096GB. The swap code usually | |
106 | * divides this by 4, leaving us with a capability of up to four 1TB swap | |
107 | * devices. | |
79634a66 | 108 | * |
534ee349 MD |
109 | * With a 64-bit swblk_t the limitation is some insane number. |
110 | * | |
111 | * NOTE: For now I don't trust that we overflow-detect properly so we divide | |
112 | * out to ensure that no overflow occurs. | |
79634a66 | 113 | */ |
534ee349 MD |
114 | |
115 | #if SWBLK_BITS == 64 | |
116 | #define BLIST_MAXBLKS (0x4000000000000000LL / \ | |
117 | (BLIST_BMAP_RADIX / BLIST_META_RADIX)) | |
118 | #else | |
79634a66 MD |
119 | #define BLIST_MAXBLKS (0x40000000 / \ |
120 | (BLIST_BMAP_RADIX / BLIST_META_RADIX)) | |
534ee349 | 121 | #endif |
79634a66 | 122 | |
984263bc MD |
123 | #define BLIST_MAX_ALLOC BLIST_BMAP_RADIX |
124 | ||
b5516a55 SW |
125 | blist_t blist_create(swblk_t); |
126 | void blist_destroy(blist_t); | |
127 | swblk_t blist_alloc(blist_t, swblk_t); | |
128 | swblk_t blist_allocat(blist_t, swblk_t, swblk_t); | |
129 | void blist_free(blist_t, swblk_t, swblk_t); | |
130 | swblk_t blist_fill(blist_t, swblk_t, swblk_t); | |
131 | void blist_print(blist_t); | |
132 | void blist_resize(blist_t *, swblk_t, int); | |
984263bc MD |
133 | |
134 | #endif /* _SYS_BLIST_H_ */ |