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));
71 axmap->first_free = 0;
74 void axmap_free(struct axmap *axmap)
81 for (i = 0; i < axmap->nr_levels; i++)
82 sfree(axmap->levels[i].map);
88 struct axmap *axmap_new(unsigned long nr_bits)
91 unsigned int i, levels;
93 axmap = smalloc(sizeof(*axmap));
98 i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
100 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
104 axmap->nr_levels = levels;
105 axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
107 for (i = 0; i < axmap->nr_levels; i++) {
108 struct axmap_level *al = &axmap->levels[i];
111 al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
112 al->map = smalloc(al->map_size * sizeof(unsigned long));
116 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
122 for (i = 0; i < axmap->nr_levels; i++)
123 if (axmap->levels[i].map)
124 sfree(axmap->levels[i].map);
126 sfree(axmap->levels);
130 static int axmap_handler(struct axmap *axmap, uint64_t bit_nr,
131 int (*func)(struct axmap_level *, unsigned long, unsigned int,
134 struct axmap_level *al;
137 for (i = 0; i < axmap->nr_levels; i++) {
138 unsigned long index = ulog64(bit_nr, i);
139 unsigned long offset = index >> UNIT_SHIFT;
140 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
142 al = &axmap->levels[i];
144 if (func(al, offset, bit, data))
151 static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
152 int (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
155 struct axmap_level *al;
156 int i, level = axmap->nr_levels;
158 for (i = axmap->nr_levels - 1; i >= 0; i--) {
159 unsigned long index = ulog64(bit_nr, --level);
160 unsigned long offset = index >> UNIT_SHIFT;
161 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
163 al = &axmap->levels[i];
165 if (func(al, offset, bit, data))
172 static int axmap_clear_fn(struct axmap_level *al, unsigned long offset,
173 unsigned int bit, void *unused)
175 if (!(al->map[offset] & (1UL << bit)))
178 al->map[offset] &= ~(1UL << bit);
182 void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
184 axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
187 struct axmap_set_data {
188 unsigned int nr_bits;
189 unsigned int set_bits;
190 unsigned int fail_ok;
193 static unsigned long bit_masks[] = {
194 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
195 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
196 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
197 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
198 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
199 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
200 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
201 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
203 #if BITS_PER_LONG == 64
204 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
205 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
206 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
207 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
208 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
209 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
210 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
211 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
215 static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
216 unsigned int bit, void *__data)
218 struct axmap_set_data *data = __data;
219 unsigned long mask, overlap;
220 unsigned int nr_bits;
222 nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
224 mask = bit_masks[nr_bits] << bit;
227 * Mask off any potential overlap, only sets contig regions
229 overlap = al->map[offset] & mask;
230 if (overlap == mask) {
231 assert(data->fail_ok);
236 unsigned long clear_mask = ~(1UL << ffz(~overlap));
239 overlap &= clear_mask;
244 assert(!(al->map[offset] & mask));
246 al->map[offset] |= mask;
249 data->set_bits = nr_bits;
252 return al->map[offset] != -1UL;
255 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
256 struct axmap_set_data *data)
258 unsigned int set_bits, nr_bits = data->nr_bits;
260 if (axmap->first_free >= bit_nr &&
261 axmap->first_free < bit_nr + data->nr_bits)
262 axmap->first_free = -1ULL;
266 axmap_handler(axmap, bit_nr, axmap_set_fn, data);
267 set_bits += data->set_bits;
269 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
272 nr_bits -= data->set_bits;
273 bit_nr += data->set_bits;
275 data->nr_bits = nr_bits;
279 data->set_bits = set_bits;
282 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
284 struct axmap_set_data data = { .nr_bits = 1, };
286 __axmap_set(axmap, bit_nr, &data);
289 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
291 struct axmap_set_data data = { .nr_bits = nr_bits, };
293 __axmap_set(axmap, bit_nr, &data);
294 return data.set_bits;
297 static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
298 unsigned int bit, void *unused)
300 return (al->map[offset] & (1UL << bit)) != 0;
303 int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
305 return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
308 static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
315 * Start at the bottom, then converge towards first free bit at the top
317 for (i = level; i >= 0; i--) {
318 struct axmap_level *al = &axmap->levels[i];
320 if (index >= al->map_size) {
325 for (j = index; j < al->map_size; j++) {
326 if (al->map[j] == -1UL)
330 * First free bit here is our index into the first
331 * free bit at the next higher level
333 index = (j << UNIT_SHIFT) + ffz(al->map[j]);
341 uint64_t axmap_first_free(struct axmap *axmap)
343 if (firstfree_valid(axmap))
344 return axmap->first_free;
346 axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
347 return axmap->first_free;
350 struct axmap_next_free_data {
352 unsigned long offset;
356 static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
357 unsigned int bit, void *__data)
359 struct axmap_next_free_data *data = __data;
360 uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);
362 if (!(mask & al->map[offset]))
365 if (al->map[offset] != -1UL) {
366 data->level = al->level;
367 data->offset = offset;
371 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
376 * 'bit_nr' is already set. Find the next free bit after this one.
378 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
380 struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
382 if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
383 return axmap->first_free;
385 if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
386 return axmap_first_free(axmap);
388 assert(data.level != -1U);
390 return axmap_find_first_free(axmap, data.level, data.offset);