[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 existence
 * 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 "../mutex.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		(1U << 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 {
	struct fio_mutex lock;
	unsigned int nr_levels;
	struct axmap_level *levels;
	uint64_t first_free;
	uint64_t nr_bits;
};

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;

	fio_mutex_down(&axmap->lock);

	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;
	fio_mutex_up(&axmap->lock);
}

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);
	__fio_mutex_remove(&axmap->lock);
	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;

	__fio_mutex_init(&axmap->lock, FIO_MUTEX_UNLOCKED);

	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->nr_bits = nr_bits;

	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);
	__fio_mutex_remove(&axmap->lock);
	sfree(axmap);
	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;
};

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

	if (bit_nr > axmap->nr_bits)
		return;
	else if (bit_nr + nr_bits > axmap->nr_bits)
		nr_bits = axmap->nr_bits - bit_nr;

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

		if (!data->set_bits ||
		    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->set_bits = set_bits;
}

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

	fio_mutex_down(&axmap->lock);
	__axmap_set(axmap, bit_nr, &data);
	fio_mutex_up(&axmap->lock);
}

unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
{
	unsigned int set_bits = 0;

	do {
		struct axmap_set_data data = { .nr_bits = nr_bits, };
		unsigned int max_bits, this_set;

		max_bits = BLOCKS_PER_UNIT - (bit_nr & BLOCKS_PER_UNIT_MASK);
		if (max_bits < nr_bits)
			data.nr_bits = max_bits;

		this_set = data.nr_bits;
		__axmap_set(axmap, bit_nr, &data);
		set_bits += data.set_bits;
		if (data.set_bits != this_set)
			break;

		nr_bits -= data.set_bits;
		bit_nr += data.set_bits;
	} while (nr_bits);

	return 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)
{
	if (bit_nr <= axmap->nr_bits) {
		int ret;

		fio_mutex_down(&axmap->lock);
		ret = axmap_handler_topdown(axmap, bit_nr, axmap_isset_fn, NULL);
		fio_mutex_up(&axmap->lock);
		return ret;
	}

	return 0;
}

static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
				       uint64_t index)
{
	uint64_t ret = -1ULL;
	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];

		/*
		 * Clear 'ret', this is a bug condition.
		 */
		if (index >= al->map_size) {
			ret = -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
			 */
			ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
			break;
		}
	}

	if (ret < axmap->nr_bits)
		return ret;

	return (uint64_t) -1ULL;
}

uint64_t axmap_first_free(struct axmap *axmap)
{
	uint64_t ret;

	if (firstfree_valid(axmap))
		return axmap->first_free;

	fio_mutex_down(&axmap->lock);
	ret = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
	axmap->first_free = ret;
	fio_mutex_up(&axmap->lock);

	return ret;
}

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 = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];

	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, };
	uint64_t ret;

	fio_mutex_down(&axmap->lock);

	if (firstfree_valid(axmap) && bit_nr < axmap->first_free) {
		ret = axmap->first_free;
		goto done;
	}

	if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data)) {
		ret = axmap_first_free(axmap);
		goto done;
	}

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

	/*
	 * In the rare case that the map is unaligned, we might end up
	 * finding an offset that's beyond the valid end. For that case,
	 * find the first free one, the map is practically full.
	 */
	ret = axmap_find_first_free(axmap, data.level, data.offset);
	if (ret != -1ULL) {
done:
		fio_mutex_up(&axmap->lock);
		return ret;
	}

	ret = axmap_first_free(axmap);
	goto done;
}
Commit	Line	Data
	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 existence
	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 "../mutex.h"
	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
	37	#define BLOCKS_PER_UNIT (1U << UNIT_SHIFT)
	38	#define BLOCKS_PER_UNIT_MASK (BLOCKS_PER_UNIT - 1)
	39
	40	#define firstfree_valid(b) ((b)->first_free != (uint64_t) -1)
	41
	42	struct axmap_level {
	43	int level;
	44	unsigned long map_size;
	45	unsigned long *map;
	46	};
	47
	48	struct axmap {
	49	struct fio_mutex lock;
	50	unsigned int nr_levels;
	51	struct axmap_level *levels;
	52	uint64_t first_free;
	53	uint64_t nr_bits;
	54	};
	55
	56	static unsigned long ulog64(unsigned long val, unsigned int log)
	57	{
	58	while (log-- && val)
	59	val >>= UNIT_SHIFT;
	60
	61	return val;
	62	}
	63
	64	void axmap_reset(struct axmap *axmap)
	65	{
	66	int i;
	67
	68	fio_mutex_down(&axmap->lock);
	69
	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	}
	75
	76	axmap->first_free = 0;
	77	fio_mutex_up(&axmap->lock);
	78	}
	79
	80	void 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);
	91	__fio_mutex_remove(&axmap->lock);
	92	sfree(axmap);
	93	}
	94
	95	struct 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
	104	__fio_mutex_init(&axmap->lock, FIO_MUTEX_UNLOCKED);
	105
	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));
	115	axmap->nr_bits = nr_bits;
	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;
	131	err:
	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);
	137	__fio_mutex_remove(&axmap->lock);
	138	sfree(axmap);
	139	return NULL;
	140	}
	141
	142	static 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
	163	static 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
	184	static 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
	194	void axmap_clear(struct axmap *axmap, uint64_t bit_nr)
	195	{
	196	axmap_handler(axmap, bit_nr, axmap_clear_fn, NULL);
	197	}
	198
	199	struct axmap_set_data {
	200	unsigned int nr_bits;
	201	unsigned int set_bits;
	202	};
	203
	204	static 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
	226	static 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;
	241	if (overlap == mask)
	242	return 1;
	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
	264	static 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
	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
	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
	283	if (!data->set_bits \|\|
	284	data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
	285	break;
	286
	287	nr_bits -= data->set_bits;
	288	bit_nr += data->set_bits;
	289
	290	data->nr_bits = nr_bits;
	291	}
	292
	293	data->set_bits = set_bits;
	294	}
	295
	296	void axmap_set(struct axmap *axmap, uint64_t bit_nr)
	297	{
	298	struct axmap_set_data data = { .nr_bits = 1, };
	299
	300	fio_mutex_down(&axmap->lock);
	301	__axmap_set(axmap, bit_nr, &data);
	302	fio_mutex_up(&axmap->lock);
	303	}
	304
	305	unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr, unsigned int nr_bits)
	306	{
	307	unsigned int set_bits = 0;
	308
	309	do {
	310	struct axmap_set_data data = { .nr_bits = nr_bits, };
	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;
	322
	323	nr_bits -= data.set_bits;
	324	bit_nr += data.set_bits;
	325	} while (nr_bits);
	326
	327	return set_bits;
	328	}
	329
	330	static 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
	336	int axmap_isset(struct axmap *axmap, uint64_t bit_nr)
	337	{
	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	}
	346
	347	return 0;
	348	}
	349
	350	static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
	351	uint64_t index)
	352	{
	353	uint64_t ret = -1ULL;
	354	unsigned long j;
	355	int i;
	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
	363	/*
	364	* Clear 'ret', this is a bug condition.
	365	*/
	366	if (index >= al->map_size) {
	367	ret = -1ULL;
	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	*/
	379	ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
	380	break;
	381	}
	382	}
	383
	384	if (ret < axmap->nr_bits)
	385	return ret;
	386
	387	return (uint64_t) -1ULL;
	388	}
	389
	390	uint64_t axmap_first_free(struct axmap *axmap)
	391	{
	392	uint64_t ret;
	393
	394	if (firstfree_valid(axmap))
	395	return axmap->first_free;
	396
	397	fio_mutex_down(&axmap->lock);
	398	ret = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
	399	axmap->first_free = ret;
	400	fio_mutex_up(&axmap->lock);
	401
	402	return ret;
	403	}
	404
	405	struct axmap_next_free_data {
	406	unsigned int level;
	407	unsigned long offset;
	408	uint64_t bit;
	409	};
	410
	411	static 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;
	415	uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];
	416
	417	if (!(mask & ~al->map[offset]))
	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	*/
	433	uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
	434	{
	435	struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
	436	uint64_t ret;
	437
	438	fio_mutex_down(&axmap->lock);
	439
	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	}
	449
	450	assert(data.level != -1U);
	451
	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);
	458	if (ret != -1ULL) {
	459	done:
	460	fio_mutex_up(&axmap->lock);
	461	return ret;
	462	}
	463
	464	ret = axmap_first_free(axmap);
	465	goto done;
	466	}