Add tests specifically for axmap_next_free()
authorMichael Kelley <mikelley@microsoft.com>
Fri, 17 Aug 2018 19:17:00 +0000 (12:17 -0700)
committerMichael Kelley <mikelley@microsoft.com>
Fri, 17 Aug 2018 19:17:00 +0000 (12:17 -0700)
Add tests for axmap_next_free() to ensure the new search algorithm
works correctly.  Since the new algorithm always looks forward for
the next free bit, it's possible to test for specific results given
a known condition of the map.  Test maps that are mostly empty and
mostly full. Test wrap-around. Test maps of particular sizes that
have unused bits in middle levels as well as in level 0.

t/axmap.c

index 1512737..1752439 100644 (file)
--- a/t/axmap.c
+++ b/t/axmap.c
@@ -9,8 +9,6 @@ static int test_regular(size_t size, int seed)
 {
        struct fio_lfsr lfsr;
        struct axmap *map;
-       size_t osize;
-       uint64_t ff;
        int err;
 
        printf("Using %llu entries...", (unsigned long long) size);
@@ -18,7 +16,6 @@ static int test_regular(size_t size, int seed)
 
        lfsr_init(&lfsr, size, seed, seed & 0xF);
        map = axmap_new(size);
-       osize = size;
        err = 0;
 
        while (size--) {
@@ -45,11 +42,154 @@ static int test_regular(size_t size, int seed)
        if (err)
                return err;
 
-       ff = axmap_next_free(map, osize);
-       if (ff != (uint64_t) -1ULL) {
-               printf("axmap_next_free broken: got %llu\n", (unsigned long long) ff);
+       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(size_t size, int seed)
+{
+       struct fio_lfsr lfsr;
+       struct axmap *map;
+       size_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);
@@ -269,6 +409,16 @@ int main(int argc, char *argv[])
                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;
 }