[fio.git] / lib / axmap.c

/*
 * Bitmap of bitmaps, where each layer is number-of-bits-per-word smaller than
 * the previous. Hence an 'axmap', since we axe each previous layer into a
 * much smaller piece. I swear, that is why it's named like that. It has
 * nothing to do with anything remotely narcissistic.
 *
 * A set bit at layer N indicates a full word at layer N-1, and so forth. As
 * the bitmap becomes progressively more full, checking for existance
 * becomes cheaper (since fewer layers are walked, making it a lot more
 * cache friendly) and locating the next free space likewise.
 *
 * Axmaps get pretty close to optimal (1 bit per block) space usage, since
 * layers quickly diminish in size. Doing the size math is straight forward,
 * since we have log64(blocks) layers of maps. For 20000 blocks, overhead
 * is roughly 1.9%, or 1.019 bits per block. The number quickly converges
 * towards 1.0158, or 1.58% of overhead.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "../arch/arch.h"
#include "axmap.h"
#include "../smalloc.h"
#include "../minmax.h"

#if BITS_PER_LONG == 64
#define UNIT_SHIFT		6
#elif BITS_PER_LONG == 32
#define UNIT_SHIFT		5
#else
#error "Number of arch bits unknown"
#endif

#define BLOCKS_PER_UNIT		(1UL << UNIT_SHIFT)
#define BLOCKS_PER_UNIT_MASK	(BLOCKS_PER_UNIT - 1)

#define firstfree_valid(b)	((b)->first_free != (uint64_t) -1)

struct axmap_level {
	int level;
	unsigned long map_size;
	unsigned long *map;
};

struct axmap {
	unsigned int nr_levels;
	struct axmap_level *levels;
	uint64_t first_free;
};

static unsigned long ulog64(unsigned long val, unsigned int log)
{
	while (log-- && val)
		val >>= UNIT_SHIFT;

	return val;
}

void axmap_reset(struct axmap *axmap)
{
	int i;

	for (i = 0; i < axmap->nr_levels; i++) {
		struct axmap_level *al = &axmap->levels[i];

		memset(al->map, 0, al->map_size * sizeof(unsigned long));
	}
}

void axmap_free(struct axmap *axmap)
{
	unsigned int i;

	if (!axmap)
		return;

	for (i = 0; i < axmap->nr_levels; i++)
		sfree(axmap->levels[i].map);

	sfree(axmap->levels);
	sfree(axmap);
}

struct axmap *axmap_new(unsigned long nr_bits)
{
	struct axmap *axmap;
	unsigned int i, levels;

	axmap = smalloc(sizeof(*axmap));
	if (!axmap)
		return NULL;

	levels = 1;
	i = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
	while (i > 1) {
		i = (i + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
		levels++;
	}

	axmap->nr_levels = levels;
	axmap->levels = smalloc(axmap->nr_levels * sizeof(struct axmap_level));
	axmap->first_free = 0;

	for (i = 0; i < axmap->nr_levels; i++) {
		struct axmap_level *al = &axmap->levels[i];

		al->level = i;
		al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
		al->map = smalloc(al->map_size * sizeof(unsigned long));
		if (!al->map)
			goto err;

		nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
	}

	axmap_reset(axmap);
	return axmap;
err:
	for (i = 0; i < axmap->nr_levels; i++)
		if (axmap->levels[i].map)
			sfree(axmap->levels[i].map);

	sfree(axmap->levels);
	return NULL;
}

static int axmap_handler(struct axmap *axmap, uint64_t bit_nr,
			  int (*func)(struct axmap_level *, unsigned long, unsigned int,
			  void *), void *data)
{
	struct axmap_level *al;
	int i;

	for (i = 0; i < axmap->nr_levels; i++) {
		unsigned long index = ulog64(bit_nr, i);
		unsigned long offset = index >> UNIT_SHIFT;
		unsigned int bit = index & BLOCKS_PER_UNIT_MASK;

		al = &axmap->levels[i];

		if (func(al, offset, bit, data))
			return 1;
	}

	return 0;
}

static int axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
	int (*func)(struct axmap_level *, unsigned long, unsigned int, void *),
	void *data)
{
	struct axmap_level *al;
	int i, level = axmap->nr_levels;

	for (i = axmap->nr_levels - 1; i >= 0; i--) {
		unsigned long index = ulog64(bit_nr, --level);
		unsigned long offset = index >> UNIT_SHIFT;
		unsigned int bit = index & BLOCKS_PER_UNIT_MASK;

		al = &axmap->levels[i];

		if (func(al, offset, bit, data))
			return 1;
	}

	return 0;
}

static int axmap_clear_fn(struct axmap_level *al, unsigned long offset,
			   unsigned int bit, void *unused)
{
	if (!(al->map[offset] & (1UL << bit)))
		return 1;

	al->map[offset] &= ~(1UL << bit);
	return 0;
}

void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
{
	axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
}

struct axmap_set_data {
	unsigned int nr_bits;
	unsigned int set_bits;
	unsigned int fail_ok;
};

static unsigned long bit_masks[] = {
	0x0000000000000000, 0x0000000000000001, 0x0000000000000003, 0x0000000000000007,
	0x000000000000000f, 0x000000000000001f, 0x000000000000003f, 0x000000000000007f,
	0x00000000000000ff, 0x00000000000001ff, 0x00000000000003ff, 0x00000000000007ff,
	0x0000000000000fff, 0x0000000000001fff, 0x0000000000003fff, 0x0000000000007fff,
	0x000000000000ffff, 0x000000000001ffff, 0x000000000003ffff, 0x000000000007ffff,
	0x00000000000fffff, 0x00000000001fffff, 0x00000000003fffff, 0x00000000007fffff,
	0x0000000000ffffff, 0x0000000001ffffff, 0x0000000003ffffff, 0x0000000007ffffff,
	0x000000000fffffff, 0x000000001fffffff, 0x000000003fffffff, 0x000000007fffffff,
	0x00000000ffffffff,
#if BITS_PER_LONG == 64
	0x00000001ffffffff, 0x00000003ffffffff, 0x00000007ffffffff, 0x0000000fffffffff,
	0x0000001fffffffff, 0x0000003fffffffff, 0x0000007fffffffff, 0x000000ffffffffff,
	0x000001ffffffffff, 0x000003ffffffffff, 0x000007ffffffffff, 0x00000fffffffffff,
	0x00001fffffffffff, 0x00003fffffffffff, 0x00007fffffffffff, 0x0000ffffffffffff,
	0x0001ffffffffffff, 0x0003ffffffffffff, 0x0007ffffffffffff, 0x000fffffffffffff,
	0x001fffffffffffff, 0x003fffffffffffff, 0x007fffffffffffff, 0x00ffffffffffffff,
	0x01ffffffffffffff, 0x03ffffffffffffff, 0x07ffffffffffffff, 0x0fffffffffffffff,
	0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff
#endif
};

static int axmap_set_fn(struct axmap_level *al, unsigned long offset,
			 unsigned int bit, void *__data)
{
	struct axmap_set_data *data = __data;
	unsigned long mask, overlap;
	unsigned int nr_bits;

	nr_bits = min(data->nr_bits, BLOCKS_PER_UNIT - bit);

	mask = bit_masks[nr_bits] << bit;

	/*
	 * Mask off any potential overlap, only sets contig regions
	 */
	overlap = al->map[offset] & mask;
	if (overlap == mask) {
		assert(data->fail_ok);
		return 1;
	}

	while (overlap) {
		unsigned long clear_mask = ~(1UL << ffz(~overlap));

		mask &= clear_mask;
		overlap &= clear_mask;
		nr_bits--;
	}

	assert(mask);
	assert(!(al->map[offset] & mask));
		
	al->map[offset] |= mask;

	if (!al->level)
		data->set_bits = nr_bits;

	data->nr_bits = 1;
	return al->map[offset] != -1UL;
}

static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
			 struct axmap_set_data *data)
{
	unsigned int set_bits, nr_bits = data->nr_bits;

	if (axmap->first_free >= bit_nr &&
	    axmap->first_free < bit_nr + data->nr_bits)
		axmap->first_free = -1ULL;

	set_bits = 0;
	while (nr_bits) {
		axmap_handler(axmap, bit_nr, axmap_set_fn, data);
		set_bits += data->set_bits;

		if (data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
			break;

		nr_bits -= data->set_bits;
		bit_nr += data->set_bits;

		data->nr_bits = nr_bits;
		data->fail_ok = 1;
	}

	data->set_bits = set_bits;
}

void axmap_set(struct axmap *axmap, uint64_t bit_nr)
{
	struct axmap_set_data data = { .nr_bits = 1, };

	__axmap_set(axmap, bit_nr, &data);
}

unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
{
	struct axmap_set_data data = { .nr_bits = nr_bits, };

	__axmap_set(axmap, bit_nr, &data);
	return data.set_bits;
}

static int axmap_isset_fn(struct axmap_level *al, unsigned long offset,
			    unsigned int bit, void *unused)
{
	return (al->map[offset] & (1UL << bit)) != 0;
}

int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
{
	return axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
}

static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
				       uint64_t index)
{
	unsigned long j;
	int i;

	/*
	 * Start at the bottom, then converge towards first free bit at the top
	 */
	for (i = level; i >= 0; i--) {
		struct axmap_level *al = &axmap->levels[i];

		if (index >= al->map_size) {
			index = -1ULL;
			break;
		}

		for (j = index; j < al->map_size; j++) {
			if (al->map[j] == -1UL)
				continue;

			/*
			 * First free bit here is our index into the first
			 * free bit at the next higher level
			 */
			index = (j << UNIT_SHIFT) + ffz(al->map[j]);
			break;
		}
	}

	return index;
}

uint64_t axmap_first_free(struct axmap *axmap)
{
	if (firstfree_valid(axmap))
		return axmap->first_free;

	axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
	return axmap->first_free;
}

struct axmap_next_free_data {
	unsigned int level;
	unsigned long offset;
	uint64_t bit;
};

static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
			       unsigned int bit, void *__data)
{
	struct axmap_next_free_data *data = __data;
	uint64_t mask = ~((1UL << ((data->bit & BLOCKS_PER_UNIT_MASK) + 1)) - 1);

	if (!(mask & al->map[offset]))
		return 0;

	if (al->map[offset] != -1UL) {
		data->level = al->level;
		data->offset = offset;
		return 1;
	}

	data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
	return 0;
}

/*
 * 'bit_nr' is already set. Find the next free bit after this one.
 */
uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
{
	struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };

	if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
		return axmap->first_free;

	if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
		return axmap_first_free(axmap);

	assert(data.level != -1U);

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