Merge branch 'master' of https://github.com/kelleymh/fio
authorJens Axboe <axboe@kernel.dk>
Fri, 17 Aug 2018 19:27:25 +0000 (13:27 -0600)
committerJens Axboe <axboe@kernel.dk>
Fri, 17 Aug 2018 19:27:25 +0000 (13:27 -0600)
* 'master' of https://github.com/kelleymh/fio:
  Add tests specifically for axmap_next_free()
  Reimplement axmap_next_free() to prevent distribution skew

lib/axmap.c
t/axmap.c

index 454af0b..8ffff9b 100644 (file)
@@ -336,99 +336,119 @@ bool axmap_isset(struct axmap *axmap, uint64_t bit_nr)
        return false;
 }
 
-static uint64_t axmap_find_first_free(struct axmap *axmap, unsigned int level,
-                                      uint64_t index)
+/*
+ * Find the first free bit that is at least as large as bit_nr.  Return
+ * -1 if no free bit is found before the end of the map.
+ */
+static uint64_t axmap_find_first_free(struct axmap *axmap, uint64_t bit_nr)
 {
-       uint64_t ret = -1ULL;
-       unsigned long j;
        int i;
+       unsigned long temp;
+       unsigned int bit;
+       uint64_t offset, base_index, index;
+       struct axmap_level *al;
 
-       /*
-        * Start at the bottom, then converge towards first free bit at the top
-        */
-       for (i = level; i >= 0; i--) {
-               struct axmap_level *al = &axmap->levels[i];
-
-               if (index >= al->map_size)
-                       goto err;
-
-               for (j = index; j < al->map_size; j++) {
-                       if (al->map[j] == -1UL)
-                               continue;
+       index = 0;
+       for (i = axmap->nr_levels - 1; i >= 0; i--) {
+               al = &axmap->levels[i];
 
-                       /*
-                        * First free bit here is our index into the first
-                        * free bit at the next higher level
-                        */
-                       ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
-                       break;
+               /* Shift previously calculated index for next level */
+               index <<= UNIT_SHIFT;
+
+               /*
+                * Start from an index that's at least as large as the
+                * originally passed in bit number.
+                */
+               base_index = bit_nr >> (UNIT_SHIFT * i);
+               if (index < base_index)
+                       index = base_index;
+
+               /* Get the offset and bit for this level */
+               offset = index >> UNIT_SHIFT;
+               bit = index & BLOCKS_PER_UNIT_MASK;
+
+               /*
+                * If the previous level had unused bits in its last
+                * word, the offset could be bigger than the map at
+                * this level. That means no free bits exist before the
+                * end of the map, so return -1.
+                */
+               if (offset >= al->map_size)
+                       return -1ULL;
+
+               /* Check the first word starting with the specific bit */
+               temp = ~bit_masks[bit] & ~al->map[offset];
+               if (temp)
+                       goto found;
+
+               /*
+                * No free bit in the first word, so iterate
+                * looking for a word with one or more free bits.
+                */
+               for (offset++; offset < al->map_size; offset++) {
+                       temp = ~al->map[offset];
+                       if (temp)
+                               goto found;
                }
-       }
-
-       if (ret < axmap->nr_bits)
-               return ret;
 
-err:
-       return (uint64_t) -1ULL;
-}
+               /* Did not find a free bit */
+               return -1ULL;
 
-static uint64_t axmap_first_free(struct axmap *axmap)
-{
-       if (!firstfree_valid(axmap))
-               axmap->first_free = axmap_find_first_free(axmap, axmap->nr_levels - 1, 0);
-
-       return axmap->first_free;
-}
-
-struct axmap_next_free_data {
-       unsigned int level;
-       unsigned long offset;
-       uint64_t bit;
-};
-
-static bool axmap_next_free_fn(struct axmap_level *al, unsigned long offset,
-                              unsigned int bit, void *__data)
-{
-       struct axmap_next_free_data *data = __data;
-       uint64_t mask = ~bit_masks[(data->bit + 1) & BLOCKS_PER_UNIT_MASK];
-
-       if (!(mask & ~al->map[offset]))
-               return false;
-
-       if (al->map[offset] != -1UL) {
-               data->level = al->level;
-               data->offset = offset;
-               return true;
+found:
+               /* Compute the index of the free bit just found */
+               index = (offset << UNIT_SHIFT) + ffz(~temp);
        }
 
-       data->bit = (data->bit + BLOCKS_PER_UNIT - 1) / BLOCKS_PER_UNIT;
-       return false;
+       /* If found an unused bit in the last word of level 0, return -1 */
+       if (index >= axmap->nr_bits)
+               return -1ULL;
+
+       return index;
 }
 
 /*
  * 'bit_nr' is already set. Find the next free bit after this one.
+ * Return -1 if no free bits found.
  */
 uint64_t axmap_next_free(struct axmap *axmap, uint64_t bit_nr)
 {
-       struct axmap_next_free_data data = { .level = -1U, .bit = bit_nr, };
        uint64_t ret;
+       uint64_t next_bit = bit_nr + 1;
+       unsigned long temp;
+       uint64_t offset;
+       unsigned int bit;
 
-       if (firstfree_valid(axmap) && bit_nr < axmap->first_free)
-               return axmap->first_free;
+       if (bit_nr >= axmap->nr_bits)
+               return -1ULL;
 
-       if (!axmap_handler(axmap, bit_nr, axmap_next_free_fn, &data))
-               return axmap_first_free(axmap);
+       /* If at the end of the map, wrap-around */
+       if (next_bit == axmap->nr_bits)
+               next_bit = 0;
 
-       assert(data.level != -1U);
+       offset = next_bit >> UNIT_SHIFT;
+       bit = next_bit & BLOCKS_PER_UNIT_MASK;
 
        /*
-        * In the rare case that the map is unaligned, we might end up
-        * finding an offset that's beyond the valid end. For that case,
-        * find the first free one, the map is practically full.
+        * As an optimization, do a quick check for a free bit
+        * in the current word at level 0. If not found, do
+        * a topdown search.
         */
-       ret = axmap_find_first_free(axmap, data.level, data.offset);
-       if (ret != -1ULL)
-               return ret;
+       temp = ~bit_masks[bit] & ~axmap->levels[0].map[offset];
+       if (temp) {
+               ret = (offset << UNIT_SHIFT) + ffz(~temp);
 
-       return axmap_first_free(axmap);
+               /* Might have found an unused bit at level 0 */
+               if (ret >= axmap->nr_bits)
+                       ret = -1ULL;
+       } else
+               ret = axmap_find_first_free(axmap, next_bit);
+
+       /*
+        * If there are no free bits starting at next_bit and going
+        * to the end of the map, wrap around by searching again
+        * starting at bit 0.
+        */
+       if (ret == -1ULL && next_bit != 0)
+               ret = axmap_find_first_free(axmap, 0);
+       return ret;
 }
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;
 }