[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));
	}

	axmap->first_free = 0;
}

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));

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