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