Merge branch 's3_crypto' of github.com:hualongfeng/fio
[fio.git] / t / axmap.c
CommitLineData
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
39007445 8static int test_regular(uint64_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
50static 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
39007445 64static 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 199static 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
250struct overlap_test {
251 unsigned int start;
252 unsigned int nr;
253 unsigned int ret;
254};
255
9a5950bf
JA
256static 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
396int main(int argc, char *argv[])
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())
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}