[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(size_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(size_t size, int seed)
{
	struct fio_lfsr lfsr;
	struct axmap *map;
	size_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(size_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...");
	fflush(stdout);

	map = axmap_new(entries);

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

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

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

int main(int argc, char *argv[])
{
	size_t size = (1UL << 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
	1	#include <stdio.h>
	2	#include <stdlib.h>
	3	#include <inttypes.h>
	4
	5	#include "../lib/lfsr.h"
	6	#include "../lib/axmap.h"
	7
	8	static int test_regular(size_t size, int seed)
	9	{
	10	struct fio_lfsr lfsr;
	11	struct axmap *map;
	12	int err;
	13
	14	printf("Using %llu entries...", (unsigned long long) size);
	15	fflush(stdout);
	16
	17	lfsr_init(&lfsr, size, seed, seed & 0xF);
	18	map = axmap_new(size);
	19	err = 0;
	20
	21	while (size--) {
	22	uint64_t val;
	23
	24	if (lfsr_next(&lfsr, &val)) {
	25	printf("lfsr: short loop\n");
	26	err = 1;
	27	break;
	28	}
	29	if (axmap_isset(map, val)) {
	30	printf("bit already set\n");
	31	err = 1;
	32	break;
	33	}
	34	axmap_set(map, val);
	35	if (!axmap_isset(map, val)) {
	36	printf("bit not set\n");
	37	err = 1;
	38	break;
	39	}
	40	}
	41
	42	if (err)
	43	return err;
	44
	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);
	59	return 1;
	60	}
	61	return 0;
	62	}
	63
	64	static int test_next_free(size_t size, int seed)
	65	{
	66	struct fio_lfsr lfsr;
	67	struct axmap *map;
	68	size_t osize;
	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;
	193
	194	printf("pass!\n");
	195	axmap_free(map);
	196	return 0;
	197	}
	198
	199	static int test_multi(size_t size, unsigned int bit_off)
	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
	250	struct overlap_test {
	251	unsigned int start;
	252	unsigned int nr;
	253	unsigned int ret;
	254	};
	255
	256	static int test_overlap(void)
	257	{
	258	struct overlap_test tests[] = {
	259	{
	260	.start = 0,
	261	.nr = 0,
	262	.ret = 0,
	263	},
	264	{
	265	.start = 16,
	266	.nr = 16,
	267	.ret = 16,
	268	},
	269	{
	270	.start = 16,
	271	.nr = 0,
	272	.ret = 0,
	273	},
	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	},
	289	{
	290	.start = 79,
	291	.nr = 1,
	292	.ret = 0,
	293	},
	294	{
	295	.start = 80,
	296	.nr = 21,
	297	.ret = 21,
	298	},
	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	},
	334	{
	335	.start = 1100,
	336	.nr = 1,
	337	.ret = 1,
	338	},
	339	{
	340	.start = 1000,
	341	.nr = 256,
	342	.ret = 100,
	343	},
	344	{
	345	.start = 22684,
	346	.nr = 1,
	347	.ret = 1,
	348	},
	349	{
	350	.start = 22670,
	351	.nr = 60,
	352	.ret = 14,
	353	},
	354	{
	355	.start = 22670,
	356	.nr = 60,
	357	.ret = 0,
	358	},
	359	{
	360	.start = -1U,
	361	},
	362	};
	363	struct axmap *map;
	364	int entries, i, ret, err = 0;
	365
	366	entries = 0;
	367	for (i = 0; tests[i].start != -1U; i++) {
	368	unsigned int this = tests[i].start + tests[i].nr;
	369
	370	if (this > entries)
	371	entries = this;
	372	}
	373
	374	printf("Test overlaps...");
	375	fflush(stdout);
	376
	377	map = axmap_new(entries);
	378
	379	for (i = 0; tests[i].start != -1U; i++) {
	380	struct overlap_test *t = &tests[i];
	381
	382	ret = axmap_set_nr(map, t->start, t->nr);
	383	if (ret != t->ret) {
	384	printf("fail\n");
	385	printf("start=%u, nr=%d, ret=%d: %d\n", t->start, t->nr,
	386	t->ret, ret);
	387	err = 1;
	388	break;
	389	}
	390	}
	391
	392	if (!err)
	393	printf("pass!\n");
	394	axmap_free(map);
	395	return err;
	396	}
	397
	398	int main(int argc, char *argv[])
	399	{
	400	size_t size = (1UL << 23) - 200;
	401	int seed = 1;
	402
	403	if (argc > 1) {
	404	size = strtoul(argv[1], NULL, 10);
	405	if (argc > 2)
	406	seed = strtoul(argv[2], NULL, 10);
	407	}
	408
	409	if (test_regular(size, seed))
	410	return 1;
	411	if (test_multi(size, 0))
	412	return 2;
	413	if (test_multi(size, 17))
	414	return 3;
	415	if (test_overlap())
	416	return 4;
	417	if (test_next_free(size, seed))
	418	return 5;
	419
	420	/* Test 3 levels, all full: 646464 */
	421	if (test_next_free(646464, seed))
	422	return 6;
	423
	424	/* Test 4 levels, with 2 inner levels not full */
	425	if (test_next_free(((((6464)-63)64)-63)6412, seed))
	426	return 7;
	427
	428	return 0;
	429	}