arm64: ensure CPU clock retrieval issues isb()
[fio.git] / t / axmap.c
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(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
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(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
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
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
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 }