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

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

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

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

	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
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
	42	struct axmap_level {
	43	int level;
	44	unsigned long map_size;
	45	unsigned long *map;
	46	};
	47
	48	struct 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
	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
12bde369 JA	68	fio_mutex_down(&axmap->lock);
12bde369 JA	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
17f0fd39 JA	76	axmap->first_free = 0;
12bde369	77	fio_mutex_up(&axmap->lock);
7ebd796f JA	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);
12bde369	91	__fio_mutex_remove(&axmap->lock);
7ebd796f JA	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
12bde369 JA	104	__fio_mutex_init(&axmap->lock, FIO_MUTEX_UNLOCKED);
12bde369 JA	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;
	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);
12bde369 JA	137	__fio_mutex_remove(&axmap->lock);
12bde369 JA	138	sfree(axmap);
7ebd796f JA	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;
7ebd796f JA	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;
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
	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
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 \|\|
0bfdf9f1 JA	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
	296	void 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
	305	unsigned 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
	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	{
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
47d94b0b JA	347	return 0;
7ebd796f JA	348	}
	349
	350	static 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	}
7ebd796f JA	389
d555a23d	390	static uint64_t axmap_first_free(struct axmap *axmap)
7ebd796f	391	{
12bde369 JA	392	uint64_t ret;
12bde369 JA	393
7ebd796f JA	394	if (firstfree_valid(axmap))
	395	return axmap->first_free;
	396
12bde369 JA	397	ret = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
12bde369 JA	398	axmap->first_free = ret;
12bde369 JA	399
12bde369 JA	400	return ret;
7ebd796f JA	401	}
	402
	403	struct axmap_next_free_data {
	404	unsigned int level;
	405	unsigned long offset;
	406	uint64_t bit;
	407	};
	408
	409	static int axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
	410	unsigned int bit, void *__data)
	411	{
	412	struct axmap_next_free_data *data = __data;
53737ae0	413	uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];
7ebd796f	414
53737ae0	415	if (!(mask & ~al->map[offset]))
7ebd796f JA	416	return 0;
	417
	418	if (al->map[offset] != -1UL) {
	419	data->level = al->level;
	420	data->offset = offset;
	421	return 1;
	422	}
	423
	424	data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
	425	return 0;
	426	}
	427
	428	/*
	429	* 'bit_nr' is already set. Find the next free bit after this one.
	430	*/
	431	uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
	432	{
	433	struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
53737ae0	434	uint64_t ret;
7ebd796f	435
12bde369	436	fio_mutex_down(&axmap->lock);
7ebd796f	437
12bde369 JA	438	if (firstfree_valid(axmap) && bit_nr < axmap->first_free) {
	439	ret = axmap->first_free;
	440	goto done;
	441	}
	442
	443	if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data)) {
	444	ret = axmap_first_free(axmap);
	445	goto done;
	446	}
7ebd796f JA	447
	448	assert(data.level != -1U);
	449
53737ae0 JA	450	/*
	451	* In the rare case that the map is unaligned, we might end up
	452	* finding an offset that's beyond the valid end. For that case,
	453	* find the first free one, the map is practically full.
	454	*/
	455	ret = axmap_find_first_free(axmap, data.level, data.offset);
12bde369 JA	456	if (ret != -1ULL) {
	457	done:
	458	fio_mutex_up(&axmap->lock);
53737ae0	459	return ret;
12bde369	460	}
53737ae0	461
12bde369 JA	462	ret = axmap_first_free(axmap);
12bde369 JA	463	goto done;
7ebd796f	464	}