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