6 #include "../arch/arch.h"
8 #include "../smalloc.h"
11 #if BITS_PER_LONG == 64
14 #elif BITS_PER_LONG == 32
18 #error "Number of arch bits unknown"
21 #define BLOCKS_PER_UNIT (1UL << UNIT_SHIFT)
22 #define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1)
24 #define firstfree_valid(b) ((b)->first_free != (uint64_t) -1)
28 unsigned long map_size;
33 unsigned int nr_levels;
34 struct bitmap_level *levels;
38 static unsigned long ulog64(unsigned long val, unsigned int log)
46 void bitmap_reset(struct bitmap *bitmap)
50 for (i = 0; i < bitmap->nr_levels; i++) {
51 struct bitmap_level *bl = &bitmap->levels[i];
53 memset(bl->map, 0, bl->map_size * UNIT_SIZE);
57 void bitmap_free(struct bitmap *bitmap)
64 for (i = 0; i < bitmap->nr_levels; i++) {
68 for (j = 0; j < bitmap->levels[i].map_size; j++) {
69 if (bitmap->levels[i].map[j] != ~0UL)
70 printf("L%d: %.5ld=%.16lx\n", i, j, bitmap->levels[i].map[j]);
74 sfree(bitmap->levels[i].map);
77 sfree(bitmap->levels);
81 struct bitmap *bitmap_new(unsigned long nr_bits)
83 struct bitmap *bitmap;
84 unsigned int i, levels;
86 bitmap = smalloc(sizeof(*bitmap));
91 i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
93 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
97 bitmap->nr_levels = levels;
98 bitmap->levels = smalloc(bitmap->nr_levels * sizeof(struct bitmap_level));
99 bitmap->first_free = 0;
101 for (i = 0; i < bitmap->nr_levels; i++) {
102 struct bitmap_level *bl = &bitmap->levels[i];
105 bl->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
106 bl->map = smalloc(bl->map_size << UNIT_SHIFT);
110 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
113 bitmap_reset(bitmap);
116 for (i = 0; i < bitmap->nr_levels; i++)
117 if (bitmap->levels[i].map)
118 sfree(bitmap->levels[i].map);
120 sfree(bitmap->levels);
124 static int bitmap_handler(struct bitmap *bitmap, uint64_t bit_nr,
125 int (*func)(struct bitmap_level *, unsigned long, unsigned int,
128 struct bitmap_level *bl;
131 for (i = 0; i < bitmap->nr_levels; i++) {
132 unsigned long index = ulog64(bit_nr, i);
133 unsigned long offset = index >> UNIT_SHIFT;
134 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
136 bl = &bitmap->levels[i];
138 if (func(bl, offset, bit, data))
145 static int bitmap_handler_topdown(struct bitmap *bitmap, uint64_t bit_nr,
146 int (*func)(struct bitmap_level *, unsigned long, unsigned int, void *),
149 struct bitmap_level *bl;
150 int i, level = bitmap->nr_levels;
152 for (i = bitmap->nr_levels - 1; i >= 0; i--) {
153 unsigned long index = ulog64(bit_nr, --level);
154 unsigned long offset = index >> UNIT_SHIFT;
155 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
157 bl = &bitmap->levels[i];
159 if (func(bl, offset, bit, data))
166 static int bitmap_clear_fn(struct bitmap_level *bl, unsigned long offset,
167 unsigned int bit, void *unused)
169 if (!(bl->map[offset] & (1UL << bit)))
172 bl->map[offset] &= ~(1UL << bit);
176 void bitmap_clear(struct bitmap *bitmap, uint64_t bit_nr)
178 bitmap_handler(bitmap, bit_nr, bitmap_clear_fn, NULL);
181 struct bitmap_set_data {
182 unsigned int nr_bits;
183 unsigned int set_bits;
184 unsigned int fail_ok;
187 static unsigned long bit_masks[] = {
188 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
189 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
190 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
191 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
192 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
193 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
194 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
195 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
197 #if BITS_PER_LONG == 64
198 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff,
199 0x0000000fffffffff, 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff,
200 0x000000ffffffffff, 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff,
201 0x00000fffffffffff, 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff,
202 0x0000ffffffffffff, 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff,
203 0x000fffffffffffff, 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff,
204 0x00ffffffffffffff, 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff,
205 0x0fffffffffffffff, 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff,
210 static int bitmap_set_fn(struct bitmap_level *bl, unsigned long offset,
211 unsigned int bit, void *__data)
213 struct bitmap_set_data *data = __data;
214 unsigned long mask, overlap;
215 unsigned int nr_bits;
217 nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
219 mask = bit_masks[nr_bits] << bit;
222 * Mask off any potential overlap, only sets contig regions
224 overlap = bl->map[offset] & mask;
225 if (overlap == mask) {
226 assert(data->fail_ok);
231 unsigned long clear_mask = ~(1UL << ffz(~overlap));
234 overlap &= clear_mask;
239 assert(!(bl->map[offset] & mask));
241 bl->map[offset] |= mask;
244 data->set_bits = nr_bits;
247 return bl->map[offset] != -1UL;
250 static void __bitmap_set(struct bitmap *bitmap, uint64_t bit_nr,
251 struct bitmap_set_data *data)
253 unsigned int set_bits, nr_bits = data->nr_bits;
255 if (bitmap->first_free >= bit_nr &&
256 bitmap->first_free < bit_nr + data->nr_bits)
257 bitmap->first_free = -1ULL;
261 bitmap_handler(bitmap, bit_nr, bitmap_set_fn, data);
262 set_bits += data->set_bits;
264 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
267 nr_bits -= data->set_bits;
268 bit_nr += data->set_bits;
270 data->nr_bits = nr_bits;
274 data->set_bits = set_bits;
277 void bitmap_set(struct bitmap *bitmap, uint64_t bit_nr)
279 struct bitmap_set_data data = { .nr_bits = 1, };
281 __bitmap_set(bitmap, bit_nr, &data);
284 unsigned int bitmap_set_nr(struct bitmap *bitmap, uint64_t bit_nr, unsigned int nr_bits)
286 struct bitmap_set_data data = { .nr_bits = nr_bits, };
288 __bitmap_set(bitmap, bit_nr, &data);
289 return data.set_bits;
292 static int bitmap_isset_fn(struct bitmap_level *bl, unsigned long offset,
293 unsigned int bit, void *unused)
295 return (bl->map[offset] & (1UL << bit)) != 0;
298 int bitmap_isset(struct bitmap *bitmap, uint64_t bit_nr)
300 return bitmap_handler_topdown(bitmap, bit_nr, bitmap_isset_fn, NULL);
303 static uint64_t bitmap_find_first_free(struct bitmap *bitmap, unsigned int level,
310 * Start at the bottom, then converge towards first free bit at the top
312 for (i = level; i >= 0; i--) {
313 struct bitmap_level *bl = &bitmap->levels[i];
315 if (index >= bl->map_size) {
320 for (j = index; j < bl->map_size; j++) {
321 if (bl->map[j] == -1UL)
325 * First free bit here is our index into the first
326 * free bit at the next higher level
328 index = (j << UNIT_SHIFT) + ffz(bl->map[j]);
336 uint64_t bitmap_first_free(struct bitmap *bitmap)
338 if (firstfree_valid(bitmap))
339 return bitmap->first_free;
341 bitmap->first_free = bitmap_find_first_free(bitmap, bitmap->nr_levels - 1, 0);
342 return bitmap->first_free;
345 struct bitmap_next_free_data {
347 unsigned long offset;
351 static int bitmap_next_free_fn(struct bitmap_level *bl, unsigned long offset,
352 unsigned int bit, void *__data)
354 struct bitmap_next_free_data *data = __data;
355 uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);
357 if (!(mask & bl->map[offset]))
360 if (bl->map[offset] != -1UL) {
361 data->level = bl->level;
362 data->offset = offset;
366 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
371 * 'bit_nr' is already set. Find the next free bit after this one.
373 uint64_t bitmap_next_free(struct bitmap *bitmap, uint64_t bit_nr)
375 struct bitmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
377 if (firstfree_valid(bitmap) && bit_nr < bitmap->first_free)
378 return bitmap->first_free;
380 if (!bitmap_handler(bitmap, bit_nr, bitmap_next_free_fn, &data))
381 return bitmap_first_free(bitmap);
383 assert(data.level != -1U);
385 return bitmap_find_first_free(bitmap, data.level, data.offset);