2 * Bitmap of bitmaps, where each layer is number-of-bits-per-word smaller than
3 * the previous. Hence an 'axmap', since we axe each previous layer into a
4 * much smaller piece. I swear, that is why it's named like that. It has
5 * nothing to do with anything remotely narcissistic.
7 * A set bit at layer N indicates a full word at layer N-1, and so forth. As
8 * the bitmap becomes progressively more full, checking for existance
9 * becomes cheaper (since fewer layers are walked, making it a lot more
10 * cache friendly) and locating the next free space likewise.
12 * Axmaps get pretty close to optimal (1 bit per block) space usage, since
13 * layers quickly diminish in size. Doing the size math is straight forward,
14 * since we have log64(blocks) layers of maps. For 20000 blocks, overhead
15 * is roughly 1.9%, or 1.019 bits per block. The number quickly converges
16 * towards 1.0158, or 1.58% of overhead.
23 #include "../arch/arch.h"
25 #include "../smalloc.h"
26 #include "../minmax.h"
28 #if BITS_PER_LONG == 64
30 #elif BITS_PER_LONG == 32
33 #error "Number of arch bits unknown"
36 #define BLOCKS_PER_UNIT (1UL << UNIT_SHIFT)
37 #define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1)
39 #define firstfree_valid(b) ((b)->first_free != (uint64_t) -1)
43 unsigned long map_size;
48 unsigned int nr_levels;
49 struct axmap_level *levels;
53 static unsigned long ulog64(unsigned long val, unsigned int log)
61 void axmap_reset(struct axmap *axmap)
65 for (i = 0; i < axmap->nr_levels; i++) {
66 struct axmap_level *al = &axmap->levels[i];
68 memset(al->map, 0, al->map_size * sizeof(unsigned long));
72 void axmap_free(struct axmap *axmap)
79 for (i = 0; i < axmap->nr_levels; i++)
80 sfree(axmap->levels[i].map);
86 struct axmap *axmap_new(unsigned long nr_bits)
89 unsigned int i, levels;
91 axmap = smalloc(sizeof(*axmap));
96 i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
98 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
102 axmap->nr_levels = levels;
103 axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
104 axmap->first_free = 0;
106 for (i = 0; i < axmap->nr_levels; i++) {
107 struct axmap_level *al = &axmap->levels[i];
110 al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
111 al->map = smalloc(al->map_size * sizeof(unsigned long));
115 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
121 for (i = 0; i < axmap->nr_levels; i++)
122 if (axmap->levels[i].map)
123 sfree(axmap->levels[i].map);
125 sfree(axmap->levels);
129 static int axmap_handler(struct axmap *axmap, uint64_t bit_nr,
130 int (*func)(struct axmap_level *, unsigned long, unsigned int,
133 struct axmap_level *al;
136 for (i = 0; i < axmap->nr_levels; i++) {
137 unsigned long index = ulog64(bit_nr, i);
138 unsigned long offset = index >> UNIT_SHIFT;
139 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
141 al = &axmap->levels[i];
143 if (func(al, offset, bit, data))
150 static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
151 int (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
154 struct axmap_level *al;
155 int i, level = axmap->nr_levels;
157 for (i = axmap->nr_levels - 1; i >= 0; i--) {
158 unsigned long index = ulog64(bit_nr, --level);
159 unsigned long offset = index >> UNIT_SHIFT;
160 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
162 al = &axmap->levels[i];
164 if (func(al, offset, bit, data))
171 static int axmap_clear_fn(struct axmap_level *al, unsigned long offset,
172 unsigned int bit, void *unused)
174 if (!(al->map[offset] & (1UL << bit)))
177 al->map[offset] &= ~(1UL << bit);
181 void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
183 axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
186 struct axmap_set_data {
187 unsigned int nr_bits;
188 unsigned int set_bits;
189 unsigned int fail_ok;
192 static unsigned long bit_masks[] = {
193 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
194 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
195 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
196 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
197 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
198 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
199 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
200 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
202 #if BITS_PER_LONG == 64
203 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
204 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
205 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
206 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
207 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
208 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
209 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
210 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
214 static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
215 unsigned int bit, void *__data)
217 struct axmap_set_data *data = __data;
218 unsigned long mask, overlap;
219 unsigned int nr_bits;
221 nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
223 mask = bit_masks[nr_bits] << bit;
226 * Mask off any potential overlap, only sets contig regions
228 overlap = al->map[offset] & mask;
229 if (overlap == mask) {
230 assert(data->fail_ok);
235 unsigned long clear_mask = ~(1UL << ffz(~overlap));
238 overlap &= clear_mask;
243 assert(!(al->map[offset] & mask));
245 al->map[offset] |= mask;
248 data->set_bits = nr_bits;
251 return al->map[offset] != -1UL;
254 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
255 struct axmap_set_data *data)
257 unsigned int set_bits, nr_bits = data->nr_bits;
259 if (axmap->first_free >= bit_nr &&
260 axmap->first_free < bit_nr + data->nr_bits)
261 axmap->first_free = -1ULL;
265 axmap_handler(axmap, bit_nr, axmap_set_fn, data);
266 set_bits += data->set_bits;
268 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
271 nr_bits -= data->set_bits;
272 bit_nr += data->set_bits;
274 data->nr_bits = nr_bits;
278 data->set_bits = set_bits;
281 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
283 struct axmap_set_data data = { .nr_bits = 1, };
285 __axmap_set(axmap, bit_nr, &data);
288 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
290 struct axmap_set_data data = { .nr_bits = nr_bits, };
292 __axmap_set(axmap, bit_nr, &data);
293 return data.set_bits;
296 static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
297 unsigned int bit, void *unused)
299 return (al->map[offset] & (1UL << bit)) != 0;
302 int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
304 return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
307 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
314 * Start at the bottom, then converge towards first free bit at the top
316 for (i = level; i >= 0; i--) {
317 struct axmap_level *al = &axmap->levels[i];
319 if (index >= al->map_size) {
324 for (j = index; j < al->map_size; j++) {
325 if (al->map[j] == -1UL)
329 * First free bit here is our index into the first
330 * free bit at the next higher level
332 index = (j << UNIT_SHIFT) + ffz(al->map[j]);
340 uint64_t axmap_first_free(struct axmap *axmap)
342 if (firstfree_valid(axmap))
343 return axmap->first_free;
345 axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
346 return axmap->first_free;
349 struct axmap_next_free_data {
351 unsigned long offset;
355 static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
356 unsigned int bit, void *__data)
358 struct axmap_next_free_data *data = __data;
359 uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);
361 if (!(mask & al->map[offset]))
364 if (al->map[offset] != -1UL) {
365 data->level = al->level;
366 data->offset = offset;
370 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
375 * 'bit_nr' is already set. Find the next free bit after this one.
377 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
379 struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
381 if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
382 return axmap->first_free;
384 if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
385 return axmap_first_free(axmap);
387 assert(data.level != -1U);
389 return axmap_find_first_free(axmap, data.level, data.offset);