| #include <stdio.h> |
| #include <stdlib.h> |
| #include <inttypes.h> |
| |
| #include "../lib/lfsr.h" |
| #include "../lib/axmap.h" |
| |
| static int test_regular(uint64_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(uint64_t size, int seed) |
| { |
| struct fio_lfsr lfsr; |
| struct axmap *map; |
| uint64_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(uint64_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...\n"); |
| fflush(stdout); |
| |
| map = axmap_new(entries); |
| |
| for (i = 0; tests[i].start != -1U; i++) { |
| struct overlap_test *t = &tests[i]; |
| |
| printf("\tstart=%6u, nr=%3u: ", t->start, t->nr); |
| ret = axmap_set_nr(map, t->start, t->nr); |
| if (ret != t->ret) { |
| printf("%3d (FAIL, wanted %d)\n", ret, t->ret); |
| err = 1; |
| break; |
| } |
| printf("%3d (PASS)\n", ret); |
| } |
| |
| axmap_free(map); |
| return err; |
| } |
| |
| int main(int argc, char *argv[]) |
| { |
| uint64_t size = (1ULL << 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; |
| } |