[fio.git] / t / axmap.c

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#include "../lib/lfsr.h"
#include "../lib/axmap.h"

static int test_regular(uint64_t size, int seed)
{
	struct fio_lfsr lfsr;
	struct axmap *map;
	int err;

	printf("Using %llu entries...", (unsigned long long) size);
	fflush(stdout);

	lfsr_init(&lfsr, size, seed, seed & 0xF);
	map = axmap_new(size);
	err = 0;

	while (size--) {
		uint64_t val;

		if (lfsr_next(&lfsr, &val)) {
			printf("lfsr: short loop\n");
			err = 1;
			break;
		}
		if (axmap_isset(map, val)) {
			printf("bit already set\n");
			err = 1;
			break;
		}
		axmap_set(map, val);
		if (!axmap_isset(map, val)) {
			printf("bit not set\n");
			err = 1;
			break;
		}
	}

	if (err)
		return err;

	printf("pass!\n");
	axmap_free(map);
	return 0;
}

static int check_next_free(struct axmap *map, uint64_t start, uint64_t expected)
{

	uint64_t ff;

	ff = axmap_next_free(map, start);
	if (ff != expected) {
		printf("axmap_next_free broken: Expected %llu, got %llu\n",
				(unsigned long long)expected, (unsigned long long) ff);
		return 1;
	}
	return 0;
}

static int test_next_free(uint64_t size, int seed)
{
	struct fio_lfsr lfsr;
	struct axmap *map;
	uint64_t osize;
	uint64_t ff, lastfree;
	int err, i;

	printf("Test next_free %llu entries...", (unsigned long long) size);
	fflush(stdout);

	map = axmap_new(size);
	err = 0;


	/* Empty map.  Next free after 0 should be 1. */
	if (check_next_free(map, 0, 1))
		err = 1;

	/* Empty map.  Next free after 63 should be 64. */
	if (check_next_free(map, 63, 64))
		err = 1;

	/* Empty map.  Next free after size - 2 should be size - 1 */
	if (check_next_free(map, size - 2, size - 1))
		err = 1;

	/* Empty map.  Next free after size - 1 should be 0 */
	if (check_next_free(map, size - 1, 0))
		err = 1;

	/* Empty map.  Next free after 63 should be 64. */
	if (check_next_free(map, 63, 64))
		err = 1;


	/* Bit 63 set.  Next free after 62 should be 64. */
	axmap_set(map, 63);
	if (check_next_free(map, 62, 64))
		err = 1;

	/* Last bit set.  Next free after size - 2 should be 0. */
	axmap_set(map, size - 1);
	if (check_next_free(map, size - 2, 0))
		err = 1;

	/* Last bit set.  Next free after size - 1 should be 0. */
	if (check_next_free(map, size - 1, 0))
		err = 1;
	
	/* Last 64 bits set.  Next free after size - 66 or size - 65 should be 0. */
	for (i=size - 65; i < size; i++)
		axmap_set(map, i);
	if (check_next_free(map, size - 66, 0))
		err = 1;
	if (check_next_free(map, size - 65, 0))
		err = 1;
	
	/* Last 64 bits set.  Next free after size - 67 should be size - 66. */
	if (check_next_free(map, size - 67, size - 66))
		err = 1;

	axmap_free(map);
	
	/* Start with a fresh map and mostly fill it up */
	lfsr_init(&lfsr, size, seed, seed & 0xF);
	map = axmap_new(size);
	osize = size;

	/* Leave 1 entry free */
	size--;
	while (size--) {
		uint64_t val;

		if (lfsr_next(&lfsr, &val)) {
			printf("lfsr: short loop\n");
			err = 1;
			break;
		}
		if (axmap_isset(map, val)) {
			printf("bit already set\n");
			err = 1;
			break;
		}
		axmap_set(map, val);
		if (!axmap_isset(map, val)) {
			printf("bit not set\n");
			err = 1;
			break;
		}
	}

	/* Get last free bit */
	lastfree = axmap_next_free(map, 0);
	if (lastfree == -1ULL) {
		printf("axmap_next_free broken: Couldn't find last free bit\n");
		err = 1;
	}

	/* Start with last free bit and test wrap-around */
	ff = axmap_next_free(map, lastfree);
	if (ff != lastfree) {
		printf("axmap_next_free broken: wrap-around test #1 failed\n");
		err = 1;
	}

	/* Start with last bit and test wrap-around */
	ff = axmap_next_free(map, osize - 1);
	if (ff != lastfree) {
		printf("axmap_next_free broken: wrap-around test #2 failed\n");
		err = 1;
	}

	/* Set last free bit */
	axmap_set(map, lastfree);
	ff = axmap_next_free(map, 0);
	if (ff != -1ULL) {
		printf("axmap_next_free broken: Expected -1 from full map\n");
		err = 1;
	}

	ff = axmap_next_free(map, osize);
	if (ff != -1ULL) {
		printf("axmap_next_free broken: Expected -1 from out of bounds request\n");
		err = 1;
	}

	if (err)
		return err;

	printf("pass!\n");
	axmap_free(map);
	return 0;
}

static int test_multi(uint64_t size, unsigned int bit_off)
{
	unsigned int map_size = size;
	struct axmap *map;
	uint64_t val = bit_off;
	int i, err;

	printf("Test multi %llu entries %u offset...", (unsigned long long) size, bit_off);
	fflush(stdout);

	map = axmap_new(map_size);
	while (val + 128 <= map_size) {
		err = 0;
		for (i = val; i < val + 128; i++) {
			if (axmap_isset(map, val + i)) {
				printf("bit already set\n");
				err = 1;
				break;
			}
		}

		if (err)
			break;

		err = axmap_set_nr(map, val, 128);
		if (err != 128) {
			printf("only set %u bits\n", err);
			break;
		}

		err = 0;
		for (i = 0; i < 128; i++) {
			if (!axmap_isset(map, val + i)) {
				printf("bit not set: %llu\n", (unsigned long long) val + i);
				err = 1;
				break;
			}
		}

		val += 128;
		if (err)
			break;
	}

	if (!err)
		printf("pass!\n");

	axmap_free(map);
	return err;
}

struct overlap_test {
	unsigned int start;
	unsigned int nr;
	unsigned int ret;
};

static int test_overlap(void)
{
	struct overlap_test tests[] = {
		{
			.start	= 0,
			.nr	= 0,
			.ret	= 0,
		},
		{
			.start	= 16,
			.nr	= 16,
			.ret	= 16,
		},
		{
			.start	= 16,
			.nr	= 0,
			.ret	= 0,
		},
		{
			.start	= 0,
			.nr	= 32,
			.ret	= 16,
		},
		{
			.start	= 48,
			.nr	= 32,
			.ret	= 32,
		},
		{
			.start	= 32,
			.nr	= 32,
			.ret	= 16,
		},
		{
			.start	= 79,
			.nr	= 1,
			.ret	= 0,
		},
		{
			.start	= 80,
			.nr	= 21,
			.ret	= 21,
		},
		{
			.start	= 102,
			.nr	= 1,
			.ret	= 1,
		},
		{
			.start	= 101,
			.nr	= 3,
			.ret	= 1,
		},
		{
			.start	= 106,
			.nr	= 4,
			.ret	= 4,
		},
		{
			.start	= 105,
			.nr	= 3,
			.ret	= 1,
		},
		{
			.start	= 120,
			.nr	= 4,
			.ret	= 4,
		},
		{
			.start	= 118,
			.nr	= 2,
			.ret	= 2,
		},
		{
			.start	= 118,
			.nr	= 2,
			.ret	= 0,
		},
		{
			.start	= 1100,
			.nr	= 1,
			.ret	= 1,
		},
		{
			.start	= 1000,
			.nr	= 256,
			.ret	= 100,
		},
		{
			.start	= 22684,
			.nr	= 1,
			.ret	= 1,
		},
		{
			.start	= 22670,
			.nr	= 60,
			.ret	= 14,
		},
		{
			.start	= 22670,
			.nr	= 60,
			.ret	= 0,
		},
		{
			.start	= -1U,
		},
	};
	struct axmap *map;
	int entries, i, ret, err = 0;

	entries = 0;
	for (i = 0; tests[i].start != -1U; i++) {
		unsigned int this = tests[i].start + tests[i].nr;

		if (this > entries)
			entries = this;
	}

	printf("Test overlaps...\n");
	fflush(stdout);

	map = axmap_new(entries);

	for (i = 0; tests[i].start != -1U; i++) {
		struct overlap_test *t = &tests[i];

		printf("\tstart=%6u, nr=%3u: ", t->start, t->nr);
		ret = axmap_set_nr(map, t->start, t->nr);
		if (ret != t->ret) {
			printf("%3d (FAIL, wanted %d)\n", ret, t->ret);
			err = 1;
			break;
		}
		printf("%3d (PASS)\n", ret);
	}

	axmap_free(map);
	return err;
}

int main(int argc, char *argv[])
{
	uint64_t size = (1ULL << 23) - 200;
	int seed = 1;

	if (argc > 1) {
		size = strtoul(argv[1], NULL, 10);
		if (argc > 2)
			seed = strtoul(argv[2], NULL, 10);
	}

	if (test_regular(size, seed))
		return 1;
	if (test_multi(size, 0))
		return 2;
	if (test_multi(size, 17))
		return 3;
	if (test_overlap())
		return 4;
	if (test_next_free(size, seed))
		return 5;

	/* Test 3 levels, all full:  64*64*64 */
	if (test_next_free(64*64*64, seed))
		return 6;

	/* Test 4 levels, with 2 inner levels not full */
	if (test_next_free(((((64*64)-63)*64)-63)*64*12, seed))
		return 7;

	return 0;
}
Commit	Line	Data
ad1f90aa JA	1	#include <stdio.h>
ad1f90aa JA	2	#include <stdlib.h>
ad1f90aa JA	3	#include <inttypes.h>
	4
	5	#include "../lib/lfsr.h"
32bbd3ab	6	#include "../lib/axmap.h"
ad1f90aa	7
39007445	8	static int test_regular(uint64_t size, int seed)
ad1f90aa JA	9	{
ad1f90aa JA	10	struct fio_lfsr lfsr;
ad1f90aa	11	struct axmap *map;
a7448122	12	int err;
ad1f90aa	13
a7448122 JA	14	printf("Using %llu entries...", (unsigned long long) size);
a7448122 JA	15	fflush(stdout);
ad1f90aa	16
d474cbc9	17	lfsr_init(&lfsr, size, seed, seed & 0xF);
ad1f90aa	18	map = axmap_new(size);
a7448122	19	err = 0;
ad1f90aa JA	20
	21	while (size--) {
	22	uint64_t val;
	23
dd9bd2b2	24	if (lfsr_next(&lfsr, &val)) {
32bbd3ab	25	printf("lfsr: short loop\n");
a7448122	26	err = 1;
32bbd3ab JA	27	break;
32bbd3ab JA	28	}
ab3379bc JA	29	if (axmap_isset(map, val)) {
ab3379bc JA	30	printf("bit already set\n");
a7448122	31	err = 1;
ab3379bc JA	32	break;
ab3379bc JA	33	}
ad1f90aa	34	axmap_set(map, val);
ab3379bc JA	35	if (!axmap_isset(map, val)) {
ab3379bc JA	36	printf("bit not set\n");
a7448122	37	err = 1;
ab3379bc JA	38	break;
ab3379bc JA	39	}
ad1f90aa JA	40	}
ad1f90aa JA	41
a7448122 JA	42	if (err)
	43	return err;
	44
54deacf4 MK	45	printf("pass!\n");
	46	axmap_free(map);
	47	return 0;
	48	}
	49
	50	static int check_next_free(struct axmap *map, uint64_t start, uint64_t expected)
	51	{
	52
	53	uint64_t ff;
	54
	55	ff = axmap_next_free(map, start);
	56	if (ff != expected) {
	57	printf("axmap_next_free broken: Expected %llu, got %llu\n",
	58	(unsigned long long)expected, (unsigned long long) ff);
32bbd3ab JA	59	return 1;
32bbd3ab JA	60	}
54deacf4 MK	61	return 0;
	62	}
	63
39007445	64	static int test_next_free(uint64_t size, int seed)
54deacf4 MK	65	{
	66	struct fio_lfsr lfsr;
	67	struct axmap *map;
39007445	68	uint64_t osize;
54deacf4 MK	69	uint64_t ff, lastfree;
	70	int err, i;
	71
	72	printf("Test next_free %llu entries...", (unsigned long long) size);
	73	fflush(stdout);
	74
	75	map = axmap_new(size);
	76	err = 0;
	77
	78
	79	/* Empty map. Next free after 0 should be 1. */
	80	if (check_next_free(map, 0, 1))
	81	err = 1;
	82
	83	/* Empty map. Next free after 63 should be 64. */
	84	if (check_next_free(map, 63, 64))
	85	err = 1;
	86
	87	/* Empty map. Next free after size - 2 should be size - 1 */
	88	if (check_next_free(map, size - 2, size - 1))
	89	err = 1;
	90
	91	/* Empty map. Next free after size - 1 should be 0 */
	92	if (check_next_free(map, size - 1, 0))
	93	err = 1;
	94
	95	/* Empty map. Next free after 63 should be 64. */
	96	if (check_next_free(map, 63, 64))
	97	err = 1;
	98
	99
	100	/* Bit 63 set. Next free after 62 should be 64. */
	101	axmap_set(map, 63);
	102	if (check_next_free(map, 62, 64))
	103	err = 1;
	104
	105	/* Last bit set. Next free after size - 2 should be 0. */
	106	axmap_set(map, size - 1);
	107	if (check_next_free(map, size - 2, 0))
	108	err = 1;
	109
	110	/* Last bit set. Next free after size - 1 should be 0. */
	111	if (check_next_free(map, size - 1, 0))
	112	err = 1;
	113
	114	/* Last 64 bits set. Next free after size - 66 or size - 65 should be 0. */
	115	for (i=size - 65; i < size; i++)
	116	axmap_set(map, i);
	117	if (check_next_free(map, size - 66, 0))
	118	err = 1;
	119	if (check_next_free(map, size - 65, 0))
	120	err = 1;
	121
	122	/* Last 64 bits set. Next free after size - 67 should be size - 66. */
	123	if (check_next_free(map, size - 67, size - 66))
	124	err = 1;
	125
	126	axmap_free(map);
	127
	128	/* Start with a fresh map and mostly fill it up */
	129	lfsr_init(&lfsr, size, seed, seed & 0xF);
	130	map = axmap_new(size);
	131	osize = size;
	132
133	/* Leave 1 entry free */
134	size--;
135	while (size--) {
136	uint64_t val;
137
138	if (lfsr_next(&lfsr, &val)) {
139	printf("lfsr: short loop\n");
140	err = 1;
141	break;
142	}
143	if (axmap_isset(map, val)) {
144	printf("bit already set\n");
145	err = 1;
146	break;
147	}
148	axmap_set(map, val);
149	if (!axmap_isset(map, val)) {
150	printf("bit not set\n");
151	err = 1;
152	break;
153	}
154	}
155
156	/* Get last free bit */
157	lastfree = axmap_next_free(map, 0);
158	if (lastfree == -1ULL) {
159	printf("axmap_next_free broken: Couldn't find last free bit\n");
160	err = 1;
161	}
162
163	/* Start with last free bit and test wrap-around */
164	ff = axmap_next_free(map, lastfree);
165	if (ff != lastfree) {
166	printf("axmap_next_free broken: wrap-around test #1 failed\n");
167	err = 1;
168	}
169
170	/* Start with last bit and test wrap-around */
171	ff = axmap_next_free(map, osize - 1);
172	if (ff != lastfree) {
173	printf("axmap_next_free broken: wrap-around test #2 failed\n");
174	err = 1;
175	}
176
177	/* Set last free bit */
178	axmap_set(map, lastfree);
179	ff = axmap_next_free(map, 0);
180	if (ff != -1ULL) {
181	printf("axmap_next_free broken: Expected -1 from full map\n");
182	err = 1;
183	}
184
185	ff = axmap_next_free(map, osize);
186	if (ff != -1ULL) {
187	printf("axmap_next_free broken: Expected -1 from out of bounds request\n");
188	err = 1;
189	}
190
191	if (err)
192	return err;
32bbd3ab	193
a7448122 JA	194	printf("pass!\n");
	195	axmap_free(map);
	196	return 0;
	197	}
	198
39007445	199	static int test_multi(uint64_t size, unsigned int bit_off)
a7448122 JA	200	{
	201	unsigned int map_size = size;
	202	struct axmap *map;
	203	uint64_t val = bit_off;
	204	int i, err;
	205
	206	printf("Test multi %llu entries %u offset...", (unsigned long long) size, bit_off);
	207	fflush(stdout);
	208
	209	map = axmap_new(map_size);
	210	while (val + 128 <= map_size) {
	211	err = 0;
	212	for (i = val; i < val + 128; i++) {
	213	if (axmap_isset(map, val + i)) {
	214	printf("bit already set\n");
	215	err = 1;
	216	break;
	217	}
	218	}
	219
	220	if (err)
	221	break;
	222
	223	err = axmap_set_nr(map, val, 128);
	224	if (err != 128) {
	225	printf("only set %u bits\n", err);
	226	break;
	227	}
	228
	229	err = 0;
	230	for (i = 0; i < 128; i++) {
	231	if (!axmap_isset(map, val + i)) {
	232	printf("bit not set: %llu\n", (unsigned long long) val + i);
	233	err = 1;
	234	break;
	235	}
	236	}
	237
	238	val += 128;
	239	if (err)
	240	break;
	241	}
	242
	243	if (!err)
	244	printf("pass!\n");
	245
	246	axmap_free(map);
	247	return err;
	248	}
	249
dc54a01f JA	250	struct overlap_test {
	251	unsigned int start;
	252	unsigned int nr;
	253	unsigned int ret;
	254	};
	255
9a5950bf JA	256	static int test_overlap(void)
9a5950bf JA	257	{
dc54a01f	258	struct overlap_test tests[] = {
5031b5cf JA	259	{
	260	.start = 0,
	261	.nr = 0,
	262	.ret = 0,
	263	},
dc54a01f JA	264	{
	265	.start = 16,
	266	.nr = 16,
	267	.ret = 16,
	268	},
5031b5cf JA	269	{
	270	.start = 16,
	271	.nr = 0,
	272	.ret = 0,
	273	},
dc54a01f JA	274	{
	275	.start = 0,
	276	.nr = 32,
	277	.ret = 16,
	278	},
	279	{
	280	.start = 48,
	281	.nr = 32,
	282	.ret = 32,
	283	},
	284	{
	285	.start = 32,
	286	.nr = 32,
	287	.ret = 16,
	288	},
64e6d4e6 JA	289	{
	290	.start = 79,
	291	.nr = 1,
	292	.ret = 0,
	293	},
	294	{
	295	.start = 80,
	296	.nr = 21,
	297	.ret = 21,
	298	},
dc54a01f JA	299	{
	300	.start = 102,
	301	.nr = 1,
	302	.ret = 1,
	303	},
	304	{
	305	.start = 101,
	306	.nr = 3,
	307	.ret = 1,
	308	},
	309	{
	310	.start = 106,
	311	.nr = 4,
	312	.ret = 4,
	313	},
	314	{
	315	.start = 105,
	316	.nr = 3,
	317	.ret = 1,
	318	},
	319	{
	320	.start = 120,
	321	.nr = 4,
	322	.ret = 4,
	323	},
	324	{
	325	.start = 118,
	326	.nr = 2,
	327	.ret = 2,
	328	},
	329	{
	330	.start = 118,
	331	.nr = 2,
	332	.ret = 0,
	333	},
b8c79239 JA	334	{
	335	.start = 1100,
	336	.nr = 1,
	337	.ret = 1,
	338	},
	339	{
	340	.start = 1000,
	341	.nr = 256,
	342	.ret = 100,
	343	},
c7b42e0a JA	344	{
	345	.start = 22684,
	346	.nr = 1,
	347	.ret = 1,
	348	},
	349	{
	350	.start = 22670,
	351	.nr = 60,
	352	.ret = 14,
	353	},
8b813b1d JA	354	{
	355	.start = 22670,
	356	.nr = 60,
	357	.ret = 0,
	358	},
dc54a01f JA	359	{
	360	.start = -1U,
	361	},
	362	};
9a5950bf	363	struct axmap *map;
dc54a01f	364	int entries, i, ret, err = 0;
9a5950bf	365
dc54a01f	366	entries = 0;
b8c79239	367	for (i = 0; tests[i].start != -1U; i++) {
dc54a01f	368	unsigned int this = tests[i].start + tests[i].nr;
53bf886a	369
dc54a01f JA	370	if (this > entries)
dc54a01f JA	371	entries = this;
53bf886a JA	372	}
53bf886a JA	373
e7ff953f	374	printf("Test overlaps...\n");
dc54a01f	375	fflush(stdout);
9a5950bf	376
dc54a01f	377	map = axmap_new(entries);
9a5950bf	378
dc54a01f JA	379	for (i = 0; tests[i].start != -1U; i++) {
dc54a01f JA	380	struct overlap_test *t = &tests[i];
9a5950bf	381
e7ff953f	382	printf("\tstart=%6u, nr=%3u: ", t->start, t->nr);
dc54a01f JA	383	ret = axmap_set_nr(map, t->start, t->nr);
dc54a01f JA	384	if (ret != t->ret) {
e7ff953f	385	printf("%3d (FAIL, wanted %d)\n", ret, t->ret);
dc54a01f JA	386	err = 1;
	387	break;
	388	}
e7ff953f	389	printf("%3d (PASS)\n", ret);
9a5950bf JA	390	}
9a5950bf JA	391
9a5950bf	392	axmap_free(map);
dc54a01f	393	return err;
9a5950bf JA	394	}
9a5950bf JA	395
a7448122 JA	396	int main(int argc, char *argv[])
a7448122 JA	397	{
39007445	398	uint64_t size = (1ULL << 23) - 200;
a7448122 JA	399	int seed = 1;
	400
	401	if (argc > 1) {
	402	size = strtoul(argv[1], NULL, 10);
	403	if (argc > 2)
	404	seed = strtoul(argv[2], NULL, 10);
	405	}
	406
	407	if (test_regular(size, seed))
	408	return 1;
	409	if (test_multi(size, 0))
	410	return 2;
	411	if (test_multi(size, 17))
	412	return 3;
9a5950bf JA	413	if (test_overlap())
9a5950bf JA	414	return 4;
54deacf4 MK	415	if (test_next_free(size, seed))
	416	return 5;
	417
	418	/* Test 3 levels, all full: 646464 */
	419	if (test_next_free(646464, seed))
	420	return 6;
	421
	422	/* Test 4 levels, with 2 inner levels not full */
	423	if (test_next_free(((((6464)-63)64)-63)6412, seed))
	424	return 7;
a7448122	425
ad1f90aa JA	426	return 0;
ad1f90aa JA	427	}