Recent changes (master)

[Jens Axboe <axboe@kernel.dk>]

The following changes since commit daa899130fdd40f5df720ee54980b00b07903dc4:

  io_u: residiual size should be unsigned long long (2018-08-21 09:16:09 -0600)

are available in the git repository at:

  git://git.kernel.dk/fio.git master

for you to fetch changes up to c08890d3a81cebb5b4bde14afb6c7778bb390ddf:

  Merge branch 'axmap' of https://github.com/bvanassche/fio (2018-08-22 20:13:45 -0600)

----------------------------------------------------------------
Bart Van Assche (5):
      lib/axmap: Add more documentation
      lib/axmap: Inline ulog64()
      lib/axmap: Make axmap_new() more robust
      lib/axmap: Simplify axmap_set_fn()
      lib/axmap: Optimize __axmap_set()

Jens Axboe (1):
      Merge branch 'axmap' of https://github.com/bvanassche/fio

 lib/axmap.c | 96 ++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 60 insertions(+), 36 deletions(-)

---

Diff of recent changes:

diff --git a/lib/axmap.c b/lib/axmap.c
index 923aae4..e194e80 100644
--- a/lib/axmap.c
+++ b/lib/axmap.c
@@ -57,26 +57,33 @@ static const unsigned long bit_masks[] = {
 #endif
 };
 
+/**
+ * struct axmap_level - a bitmap used to implement struct axmap
+ * @level: Level index. Each map has at least one level with index zero. The
+ *	higher the level index, the fewer bits a struct axmap_level contains.
+ * @map_size: Number of elements of the @map array.
+ * @map: A bitmap with @map_size elements.
+ */
 struct axmap_level {
 	int level;
 	unsigned long map_size;
 	unsigned long *map;
 };
 
+/**
+ * struct axmap - a set that can store numbers 0 .. @nr_bits - 1
+ * @nr_level: Number of elements of the @levels array.
+ * @levels: struct axmap_level array in which lower levels contain more bits
+ *	than higher levels.
+ * @nr_bits: One more than the highest value stored in the set.
+ */
 struct axmap {
 	unsigned int nr_levels;
 	struct axmap_level *levels;
 	uint64_t nr_bits;
 };
 
-static inline unsigned long ulog64(unsigned long val, unsigned int log)
-{
-	while (log-- && val)
-		val >>= UNIT_SHIFT;
-
-	return val;
-}
-
+/* Remove all elements from the @axmap set */
 void axmap_reset(struct axmap *axmap)
 {
 	int i;
@@ -102,6 +109,7 @@ void axmap_free(struct axmap *axmap)
 	free(axmap);
 }
 
+/* Allocate memory for a set that can store the numbers 0 .. @nr_bits - 1. */
 struct axmap *axmap_new(unsigned long nr_bits)
 {
 	struct axmap *axmap;
@@ -120,6 +128,8 @@ struct axmap *axmap_new(unsigned long nr_bits)
 
 	axmap->nr_levels = levels;
 	axmap->levels = calloc(axmap->nr_levels, sizeof(struct axmap_level));
+	if (!axmap->levels)
+		goto free_axmap;
 	axmap->nr_bits = nr_bits;
 
 	for (i = 0; i < axmap->nr_levels; i++) {
@@ -129,23 +139,30 @@ struct axmap *axmap_new(unsigned long nr_bits)
 		al->map_size = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 		al->map = malloc(al->map_size * sizeof(unsigned long));
 		if (!al->map)
-			goto err;
+			goto free_levels;
 
 		nr_bits = (nr_bits + BLOCKS_PER_UNIT - 1) >> UNIT_SHIFT;
 	}
 
 	axmap_reset(axmap);
 	return axmap;
-err:
+
+free_levels:
 	for (i = 0; i < axmap->nr_levels; i++)
-		if (axmap->levels[i].map)
-			free(axmap->levels[i].map);
+		free(axmap->levels[i].map);
 
 	free(axmap->levels);
+
+free_axmap:
 	free(axmap);
 	return NULL;
 }
 
+/*
+ * Call @func for each level, starting at level zero, until a level is found
+ * for which @func returns true. Return false if none of the @func calls
+ * returns true.
+ */
 static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr,
 			  bool (*func)(struct axmap_level *, unsigned long, unsigned int,
 			  void *), void *data)
@@ -170,13 +187,18 @@ static bool axmap_handler(struct axmap *axmap, uint64_t bit_nr,
 	return false;
 }
 
+/*
+ * Call @func for each level, starting at the highest level, until a level is
+ * found for which @func returns true. Return false if none of the @func calls
+ * returns true.
+ */
 static bool axmap_handler_topdown(struct axmap *axmap, uint64_t bit_nr,
 	bool (*func)(struct axmap_level *, unsigned long, unsigned int, void *))
 {
 	int i;
 
 	for (i = axmap->nr_levels - 1; i >= 0; i--) {
-		unsigned long index = ulog64(bit_nr, i);
+		unsigned long index = bit_nr >> (UNIT_SHIFT * i);
 		unsigned long offset = index >> UNIT_SHIFT;
 		unsigned int bit = index & BLOCKS_PER_UNIT_MASK;
 
@@ -192,6 +214,11 @@ struct axmap_set_data {
 	unsigned int set_bits;
 };
 
+/*
+ * Set at most @__data->nr_bits bits in @al at offset @offset. Do not exceed
+ * the boundary of the element at offset @offset. Return the number of bits
+ * that have been set in @__data->set_bits if @al->level == 0.
+ */
 static bool axmap_set_fn(struct axmap_level *al, unsigned long offset,
 			 unsigned int bit, void *__data)
 {
@@ -208,18 +235,12 @@ static bool axmap_set_fn(struct axmap_level *al, unsigned long offset,
 	 */
 	overlap = al->map[offset] & mask;
 	if (overlap == mask) {
-done:
 		data->set_bits = 0;
 		return true;
 	}
 
 	if (overlap) {
-		const int __bit = ffz(~overlap);
-
-		nr_bits = __bit - bit;
-		if (!nr_bits)
-			goto done;
-
+		nr_bits = ffz(~overlap) - bit;
 		mask = bit_masks[nr_bits] << bit;
 	}
 
@@ -230,36 +251,33 @@ done:
 	if (!al->level)
 		data->set_bits = nr_bits;
 
+	/* For the next level */
 	data->nr_bits = 1;
+
 	return al->map[offset] != -1UL;
 }
 
+/*
+ * Set up to @data->nr_bits starting from @bit_nr in @axmap. Start at
+ * @bit_nr. If that bit has not yet been set then set it and continue until
+ * either @data->nr_bits have been set or a 1 bit is found. Store the number
+ * of bits that have been set in @data->set_bits. It is guaranteed that all
+ * bits that have been requested to set fit in the same unsigned long word of
+ * level 0 of @axmap.
+ */
 static void __axmap_set(struct axmap *axmap, uint64_t bit_nr,
 			 struct axmap_set_data *data)
 {
-	unsigned int set_bits, nr_bits = data->nr_bits;
+	unsigned int nr_bits = data->nr_bits;
 
 	if (bit_nr > axmap->nr_bits)
 		return;
 	else if (bit_nr + nr_bits > axmap->nr_bits)
 		nr_bits = axmap->nr_bits - bit_nr;
 
-	set_bits = 0;
-	while (nr_bits) {
-		axmap_handler(axmap, bit_nr, axmap_set_fn, data);
-		set_bits += data->set_bits;
+	assert(nr_bits <= BLOCKS_PER_UNIT);
 
-		if (!data->set_bits ||
-		    data->set_bits != (BLOCKS_PER_UNIT - nr_bits))
-			break;
-
-		nr_bits -= data->set_bits;
-		bit_nr += data->set_bits;
-
-		data->nr_bits = nr_bits;
-	}
-
-	data->set_bits = set_bits;
+	axmap_handler(axmap, bit_nr, axmap_set_fn, data);
 }
 
 void axmap_set(struct axmap *axmap, uint64_t bit_nr)
@@ -269,6 +287,12 @@ void axmap_set(struct axmap *axmap, uint64_t bit_nr)
 	__axmap_set(axmap, bit_nr, &data);
 }
 
+/*
+ * Set up to @nr_bits starting from @bit in @axmap. Start at @bit. If that
+ * bit has not yet been set then set it and continue until either @nr_bits
+ * have been set or a 1 bit is found. Return the number of bits that have been
+ * set.
+ */
 unsigned int axmap_set_nr(struct axmap *axmap, uint64_t bit_nr,
 			  unsigned int nr_bits)
 {