1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <inttypes.h>
4 
5 #include "../lib/lfsr.h"
6 #include "../lib/axmap.h"
7 
test_regular(uint64_t size,int seed)8 static int test_regular(uint64_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 
check_next_free(struct axmap * map,uint64_t start,uint64_t expected)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 
test_next_free(uint64_t size,int seed)64 static int test_next_free(uint64_t size, int seed)
65 {
66 	struct fio_lfsr lfsr;
67 	struct axmap *map;
68 	uint64_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 
test_multi(uint64_t size,unsigned int bit_off)199 static int test_multi(uint64_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 
test_overlap(void)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...\n");
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 		printf("\tstart=%6u, nr=%3u: ", t->start, t->nr);
383 		ret = axmap_set_nr(map, t->start, t->nr);
384 		if (ret != t->ret) {
385 			printf("%3d (FAIL, wanted %d)\n", ret, t->ret);
386 			err = 1;
387 			break;
388 		}
389 		printf("%3d (PASS)\n", ret);
390 	}
391 
392 	axmap_free(map);
393 	return err;
394 }
395 
main(int argc,char * argv[])396 int main(int argc, char *argv[])
397 {
398 	uint64_t size = (1ULL << 23) - 200;
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;
413 	if (test_overlap())
414 		return 4;
415 	if (test_next_free(size, seed))
416 		return 5;
417 
418 	/* Test 3 levels, all full:  64*64*64 */
419 	if (test_next_free(64*64*64, seed))
420 		return 6;
421 
422 	/* Test 4 levels, with 2 inner levels not full */
423 	if (test_next_free(((((64*64)-63)*64)-63)*64*12, seed))
424 		return 7;
425 
426 	return 0;
427 }
428