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++)
65 sfree(bitmap->levels[i].map);
67 sfree(bitmap->levels);
71 struct bitmap *bitmap_new(unsigned long nr_bits)
73 struct bitmap *bitmap;
74 unsigned int i, levels;
76 bitmap = smalloc(sizeof(*bitmap));
81 i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
83 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
87 bitmap->nr_levels = levels;
88 bitmap->levels = smalloc(bitmap->nr_levels * sizeof(struct bitmap_level));
89 bitmap->first_free = 0;
91 for (i = 0; i < bitmap->nr_levels; i++) {
92 struct bitmap_level *bl = &bitmap->levels[i];
95 bl->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
96 bl->map = smalloc(bl->map_size << UNIT_SHIFT);
100 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
103 bitmap_reset(bitmap);
106 for (i = 0; i < bitmap->nr_levels; i++)
107 if (bitmap->levels[i].map)
108 sfree(bitmap->levels[i].map);
110 sfree(bitmap->levels);
114 static int bitmap_handler(struct bitmap *bitmap, uint64_t bit_nr,
115 int (*func)(struct bitmap_level *, unsigned long, unsigned int,
118 struct bitmap_level *bl;
121 for (i = 0; i < bitmap->nr_levels; i++) {
122 unsigned long index = ulog64(bit_nr, i);
123 unsigned long offset = index >> UNIT_SHIFT;
124 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
126 bl = &bitmap->levels[i];
128 if (func(bl, offset, bit, data))
135 static int bitmap_handler_topdown(struct bitmap *bitmap, uint64_t bit_nr,
136 int (*func)(struct bitmap_level *, unsigned long, unsigned int, void *),
139 struct bitmap_level *bl;
140 int i, level = bitmap->nr_levels;
142 for (i = bitmap->nr_levels - 1; i >= 0; i--) {
143 unsigned long index = ulog64(bit_nr, --level);
144 unsigned long offset = index >> UNIT_SHIFT;
145 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
147 bl = &bitmap->levels[i];
149 if (func(bl, offset, bit, data))
156 static int bitmap_clear_fn(struct bitmap_level *bl, unsigned long offset,
157 unsigned int bit, void *unused)
159 if (!(bl->map[offset] & (1UL << bit)))
162 bl->map[offset] &= ~(1UL << bit);
166 void bitmap_clear(struct bitmap *bitmap, uint64_t bit_nr)
168 bitmap_handler(bitmap, bit_nr, bitmap_clear_fn, NULL);
171 struct bitmap_set_data {
172 unsigned int nr_bits;
173 unsigned int set_bits;
174 unsigned int fail_ok;
177 static unsigned long bit_masks[] = {
178 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
179 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
180 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
181 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
182 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
183 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
184 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
185 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
187 #if BITS_PER_LONG == 64
188 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
189 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
190 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
191 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
192 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
193 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
194 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
195 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
199 static int bitmap_set_fn(struct bitmap_level *bl, unsigned long offset,
200 unsigned int bit, void *__data)
202 struct bitmap_set_data *data = __data;
203 unsigned long mask, overlap;
204 unsigned int nr_bits;
206 nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
208 mask = bit_masks[nr_bits] << bit;
211 * Mask off any potential overlap, only sets contig regions
213 overlap = bl->map[offset] & mask;
214 if (overlap == mask) {
215 assert(data->fail_ok);
220 unsigned long clear_mask = ~(1UL << ffz(~overlap));
223 overlap &= clear_mask;
228 assert(!(bl->map[offset] & mask));
230 bl->map[offset] |= mask;
233 data->set_bits = nr_bits;
236 return bl->map[offset] != -1UL;
239 static void __bitmap_set(struct bitmap *bitmap, uint64_t bit_nr,
240 struct bitmap_set_data *data)
242 unsigned int set_bits, nr_bits = data->nr_bits;
244 if (bitmap->first_free >= bit_nr &&
245 bitmap->first_free < bit_nr + data->nr_bits)
246 bitmap->first_free = -1ULL;
250 bitmap_handler(bitmap, bit_nr, bitmap_set_fn, data);
251 set_bits += data->set_bits;
253 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
256 nr_bits -= data->set_bits;
257 bit_nr += data->set_bits;
259 data->nr_bits = nr_bits;
263 data->set_bits = set_bits;
266 void bitmap_set(struct bitmap *bitmap, uint64_t bit_nr)
268 struct bitmap_set_data data = { .nr_bits = 1, };
270 __bitmap_set(bitmap, bit_nr, &data);
273 unsigned int bitmap_set_nr(struct bitmap *bitmap, uint64_t bit_nr, unsigned int nr_bits)
275 struct bitmap_set_data data = { .nr_bits = nr_bits, };
277 __bitmap_set(bitmap, bit_nr, &data);
278 return data.set_bits;
281 static int bitmap_isset_fn(struct bitmap_level *bl, unsigned long offset,
282 unsigned int bit, void *unused)
284 return (bl->map[offset] & (1UL << bit)) != 0;
287 int bitmap_isset(struct bitmap *bitmap, uint64_t bit_nr)
289 return bitmap_handler_topdown(bitmap, bit_nr, bitmap_isset_fn, NULL);
292 static uint64_t bitmap_find_first_free(struct bitmap *bitmap, unsigned int level,
299 * Start at the bottom, then converge towards first free bit at the top
301 for (i = level; i >= 0; i--) {
302 struct bitmap_level *bl = &bitmap->levels[i];
304 if (index >= bl->map_size) {
309 for (j = index; j < bl->map_size; j++) {
310 if (bl->map[j] == -1UL)
314 * First free bit here is our index into the first
315 * free bit at the next higher level
317 index = (j << UNIT_SHIFT) + ffz(bl->map[j]);
325 uint64_t bitmap_first_free(struct bitmap *bitmap)
327 if (firstfree_valid(bitmap))
328 return bitmap->first_free;
330 bitmap->first_free = bitmap_find_first_free(bitmap, bitmap->nr_levels - 1, 0);
331 return bitmap->first_free;
334 struct bitmap_next_free_data {
336 unsigned long offset;
340 static int bitmap_next_free_fn(struct bitmap_level *bl, unsigned long offset,
341 unsigned int bit, void *__data)
343 struct bitmap_next_free_data *data = __data;
344 uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);
346 if (!(mask & bl->map[offset]))
349 if (bl->map[offset] != -1UL) {
350 data->level = bl->level;
351 data->offset = offset;
355 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
360 * 'bit_nr' is already set. Find the next free bit after this one.
362 uint64_t bitmap_next_free(struct bitmap *bitmap, uint64_t bit_nr)
364 struct bitmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
366 if (firstfree_valid(bitmap) && bit_nr < bitmap->first_free)
367 return bitmap->first_free;
369 if (!bitmap_handler(bitmap, bit_nr, bitmap_next_free_fn, &data))
370 return bitmap_first_free(bitmap);
372 assert(data.level != -1U);
374 return bitmap_find_first_free(bitmap, data.level, data.offset);