Commit | Line | Data |
---|---|---|
ad1f90aa JA |
1 | #include <stdio.h> |
2 | #include <stdlib.h> | |
ad1f90aa JA |
3 | #include <inttypes.h> |
4 | ||
5 | #include "../lib/lfsr.h" | |
32bbd3ab | 6 | #include "../lib/axmap.h" |
ad1f90aa | 7 | |
a7448122 | 8 | static int test_regular(size_t size, int seed) |
ad1f90aa JA |
9 | { |
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); |
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; |
28 | } | |
ab3379bc JA |
29 | if (axmap_isset(map, val)) { |
30 | printf("bit already set\n"); | |
a7448122 | 31 | err = 1; |
ab3379bc JA |
32 | break; |
33 | } | |
ad1f90aa | 34 | axmap_set(map, val); |
ab3379bc JA |
35 | if (!axmap_isset(map, val)) { |
36 | printf("bit not set\n"); | |
a7448122 | 37 | err = 1; |
ab3379bc JA |
38 | break; |
39 | } | |
ad1f90aa JA |
40 | } |
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; |
60 | } | |
54deacf4 MK |
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; | |
32bbd3ab | 193 | |
a7448122 JA |
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 | ||
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) |
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) |
371 | entries = this; | |
53bf886a JA |
372 | } |
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++) { |
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); |
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 | } |
391 | ||
9a5950bf | 392 | axmap_free(map); |
dc54a01f | 393 | return err; |
9a5950bf JA |
394 | } |
395 | ||
a7448122 JA |
396 | int main(int argc, char *argv[]) |
397 | { | |
398 | size_t size = (1UL << 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; | |
9a5950bf JA |
413 | if (test_overlap()) |
414 | return 4; | |
54deacf4 MK |
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; | |
a7448122 | 425 | |
ad1f90aa JA |
426 | return 0; |
427 | } |