CommitLineData
7ebd796f
JA
1/*
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.
6 *
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.
11 *
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.
17 */
18#include <stdio.h>
19#include <stdlib.h>
20#include <string.h>
21#include <assert.h>
22
23#include "../arch/arch.h"
24#include "axmap.h"
25#include "../smalloc.h"
26#include "../minmax.h"
27
28#if BITS_PER_LONG == 64
29#define UNIT_SHIFT 6
30#elif BITS_PER_LONG == 32
31#define UNIT_SHIFT 5
32#else
33#error "Number of arch bits unknown"
34#endif
35
36#define BLOCKS_PER_UNIT (1UL << UNIT_SHIFT)
38
39#define firstfree_valid(b) ((b)->first_free != (uint64_t) -1)
40
41struct axmap_level {
42 int level;
43 unsigned long map_size;
44 unsigned long *map;
45};
46
47struct axmap {
48 unsigned int nr_levels;
49 struct axmap_level *levels;
50 uint64_t first_free;
47d94b0b 51 uint64_t nr_bits;
7ebd796f
JA
52};
53
54static unsigned long ulog64(unsigned long val, unsigned int log)
55{
56 while (log-- && val)
57 val >>= UNIT_SHIFT;
58
59 return val;
60}
61
62void axmap_reset(struct axmap *axmap)
63{
64 int i;
65
66 for (i = 0; i < axmap->nr_levels; i++) {
67 struct axmap_level *al = &axmap->levels[i];
68
69 memset(al->map, 0, al->map_size * sizeof(unsigned long));
70 }
17f0fd39
JA
71
72 axmap->first_free = 0;
7ebd796f
JA
73}
74
75void axmap_free(struct axmap *axmap)
76{
77 unsigned int i;
78
79 if (!axmap)
80 return;
81
82 for (i = 0; i < axmap->nr_levels; i++)
83 sfree(axmap->levels[i].map);
84
85 sfree(axmap->levels);
86 sfree(axmap);
87}
88
89struct axmap *axmap_new(unsigned long nr_bits)
90{
91 struct axmap *axmap;
92 unsigned int i, levels;
93
94 axmap = smalloc(sizeof(*axmap));
95 if (!axmap)
96 return NULL;
97
98 levels = 1;
99 i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
100 while (i > 1) {
101 i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
102 levels++;
103 }
104
105 axmap->nr_levels = levels;
106 axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
47d94b0b 107 axmap->nr_bits = nr_bits;
7ebd796f
JA
108
109 for (i = 0; i < axmap->nr_levels; i++) {
110 struct axmap_level *al = &axmap->levels[i];
111
112 al->level = i;
113 al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
114 al->map = smalloc(al->map_size * sizeof(unsigned long));
115 if (!al->map)
116 goto err;
117
118 nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
119 }
120
121 axmap_reset(axmap);
122 return axmap;
123err:
124 for (i = 0; i < axmap->nr_levels; i++)
125 if (axmap->levels[i].map)
126 sfree(axmap->levels[i].map);
127
128 sfree(axmap->levels);
129 return NULL;
130}
131
132static int axmap_handler(struct axmap *axmap, uint64_t bit_nr,
133 int (*func)(struct axmap_level *, unsigned long, unsigned int,
134 void *), void *data)
135{
136 struct axmap_level *al;
137 int i;
138
139 for (i = 0; i < axmap->nr_levels; i++) {
140 unsigned long index = ulog64(bit_nr, i);
141 unsigned long offset = index >> UNIT_SHIFT;
142 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
143
144 al = &axmap->levels[i];
145
146 if (func(al, offset, bit, data))
147 return 1;
148 }
149
150 return 0;
151}
152
153static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
154 int (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
155 void *data)
156{
157 struct axmap_level *al;
158 int i, level = axmap->nr_levels;
159
160 for (i = axmap->nr_levels - 1; i >= 0; i--) {
161 unsigned long index = ulog64(bit_nr, --level);
162 unsigned long offset = index >> UNIT_SHIFT;
163 unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
164
165 al = &axmap->levels[i];
166
167 if (func(al, offset, bit, data))
168 return 1;
169 }
170
171 return 0;
172}
173
174static int axmap_clear_fn(struct axmap_level *al, unsigned long offset,
175 unsigned int bit, void *unused)
176{
177 if (!(al->map[offset] & (1UL << bit)))
178 return 1;
179
180 al->map[offset] &= ~(1UL << bit);
181 return 0;
182}
183
184void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
185{
186 axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
187}
188
189struct axmap_set_data {
190 unsigned int nr_bits;
191 unsigned int set_bits;
192 unsigned int fail_ok;
193};
194
195static unsigned long bit_masks[] = {
196 0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
197 0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
198 0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
199 0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
200 0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
201 0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
202 0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
203 0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
204 0x00000000ffffffff,
205#if BITS_PER_LONG == 64
206 0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
207 0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
208 0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
209 0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
210 0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
211 0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
212 0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
213 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
214#endif
215};
216
217static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
218 unsigned int bit, void *__data)
219{
220 struct axmap_set_data *data = __data;
222 unsigned int nr_bits;
223
224 nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);
225
227
228 /*
229 * Mask off any potential overlap, only sets contig regions
230 */
231 overlap = al->map[offset] & mask;
232 if (overlap == mask) {
233 assert(data->fail_ok);
234 return 1;
235 }
236
237 while (overlap) {
238 unsigned long clear_mask = ~(1UL << ffz(~overlap));
239
242 nr_bits--;
243 }
244
247
249
250 if (!al->level)
251 data->set_bits = nr_bits;
252
253 data->nr_bits = 1;
254 return al->map[offset] != -1UL;
255}
256
257static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
258 struct axmap_set_data *data)
259{
260 unsigned int set_bits, nr_bits = data->nr_bits;
261
262 if (axmap->first_free >= bit_nr &&
263 axmap->first_free < bit_nr + data->nr_bits)
264 axmap->first_free = -1ULL;
265
47d94b0b
JA
266 if (bit_nr > axmap->nr_bits)
267 return;
268 else if (bit_nr + nr_bits > axmap->nr_bits)
269 nr_bits = axmap->nr_bits - bit_nr;
270
7ebd796f
JA
271 set_bits = 0;
272 while (nr_bits) {
273 axmap_handler(axmap, bit_nr, axmap_set_fn, data);
274 set_bits += data->set_bits;
275
276 if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
277 break;
278
279 nr_bits -= data->set_bits;
280 bit_nr += data->set_bits;
281
282 data->nr_bits = nr_bits;
283 data->fail_ok = 1;
284 }
285
286 data->set_bits = set_bits;
287}
288
289void axmap_set(struct axmap *axmap, uint64_t bit_nr)
290{
291 struct axmap_set_data data = { .nr_bits = 1, };
292
293 __axmap_set(axmap, bit_nr, &data);
294}
295
296unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
297{
298 struct axmap_set_data data = { .nr_bits = nr_bits, };
299
300 __axmap_set(axmap, bit_nr, &data);
301 return data.set_bits;
302}
303
304static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
305 unsigned int bit, void *unused)
306{
307 return (al->map[offset] & (1UL << bit)) != 0;
308}
309
310int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
311{
47d94b0b
JA
312 if (bit_nr <= axmap->nr_bits)
313 return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
314
315 return 0;
7ebd796f
JA
316}
317
318static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
319 uint64_t index)
320{
731ef4c7 321 uint64_t ret = -1ULL;
7ebd796f 322 unsigned long j;
731ef4c7 323 int i;
7ebd796f
JA
324
325 /*
326 * Start at the bottom, then converge towards first free bit at the top
327 */
328 for (i = level; i >= 0; i--) {
329 struct axmap_level *al = &axmap->levels[i];
330
731ef4c7
JA
331 /*
332 * Clear 'ret', this is a bug condition.
333 */
7ebd796f 334 if (index >= al->map_size) {
731ef4c7 335 ret = -1ULL;
7ebd796f
JA
336 break;
337 }
338
339 for (j = index; j < al->map_size; j++) {
340 if (al->map[j] == -1UL)
341 continue;
342
343 /*
344 * First free bit here is our index into the first
345 * free bit at the next higher level
346 */
731ef4c7 347 ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
7ebd796f
JA
348 break;
349 }
350 }
351
47d94b0b
JA
352 if (ret < axmap->nr_bits)
353 return ret;
354
355 return (uint64_t) -1ULL;
7ebd796f
JA
356}
357
358uint64_t axmap_first_free(struct axmap *axmap)
359{
360 if (firstfree_valid(axmap))
361 return axmap->first_free;
362
363 axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
364 return axmap->first_free;
365}
366
367struct axmap_next_free_data {
368 unsigned int level;
369 unsigned long offset;
370 uint64_t bit;
371};
372
373static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
374 unsigned int bit, void *__data)
375{
376 struct axmap_next_free_data *data = __data;
7ebd796f 378
53737ae0 379 if (!(mask & ~al->map[offset]))
7ebd796f
JA
380 return 0;
381
382 if (al->map[offset] != -1UL) {
383 data->level = al->level;
384 data->offset = offset;
385 return 1;
386 }
387
388 data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
389 return 0;
390}
391
392/*
393 * 'bit_nr' is already set. Find the next free bit after this one.
394 */
395uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
396{
397 struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
53737ae0 398 uint64_t ret;
7ebd796f
JA
399
400 if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
401 return axmap->first_free;
402
403 if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
404 return axmap_first_free(axmap);
405
406 assert(data.level != -1U);
407
53737ae0
JA
408 /*
409 * In the rare case that the map is unaligned, we might end up
410 * finding an offset that's beyond the valid end. For that case,
411 * find the first free one, the map is practically full.
412 */
413 ret = axmap_find_first_free(axmap, data.level, data.offset);
414 if (ret != -1ULL)
415 return ret;
416
417 return axmap_first_free(axmap);
7ebd796f 418}