[sheepdog] [PATCH v3 1/3] sheep: handle VID overflow correctly

[Hitoshi Mitake]

Current sheep cannot handle a case like this:
1. iterate snapshot creation and let latest working VDI have VID 0xffffff
2. create one more snapshot

This problem comes from invalid usage of find_next_zero_bit() of sheep.
Current sheep checks its VID bitmap with find_next_zero_bit(). But the
function has a subtle point we must care about. If we check a bitmap
and whose right most bit is 1, it returns a number of the bit though
the bit is not 0. It means
    /* the right most bit of sys->vdi_inuse is 1*/
    find_next_zero_bit(sys->vdi_inuse, SD_NR_VDIS, 0);
will return SD_NR_VDIS - 1 (not SD_NR_VDIS, of course). So it is not
possible to check the right most bit is used or not by simply calling
find_next_zero_bit(). So the existing code cannot handle the case of
overflow.

This patch solves the problem by let 0xffffff be an invalid VID (and
as I describe later, 0x000000 will also be invalid). With this
modification, we can simply ignore the return value 0xffffff of
find_next_zero_bit() and the right most bit vdi_inuse is already used.

And this patch also let 0x000000 be an invalid VID. It is for VID
recycling. In some places of sheepdog, parent_vid is used as a
value which indicates that the VDI has a parent (clone or snapshot) or
not (working VDI). So this patch lets the first VID 0x000001 and
prevent this sort of confusion.

Signed-off-by: Hitoshi Mitake <mitake.hitoshi at lab.ntt.co.jp>
---
 sheep/vdi.c | 34 ++++++++++++++++++++++++++++------
 1 file changed, 28 insertions(+), 6 deletions(-)

v3:
 - handle a case of 0xffffff and 0x000000 VID

diff --git a/sheep/vdi.c b/sheep/vdi.c
index 8114fb5..fbb4534 100644
--- a/sheep/vdi.c
+++ b/sheep/vdi.c
@@ -1345,7 +1345,7 @@ out:
 /*
  * Return SUCCESS (range of bits set):
  * Iff we get a bitmap range [left, right) that VDI might be set between. if
- * right < start, this means a wrap around case where we should examine the
+ * right < left, this means a wrap around case where we should examine the
  * two split ranges, [left, SD_NR_VDIS - 1] and [0, right). 'Right' is the free
  * bit that might be used by newly created VDI.
  *
@@ -1356,14 +1356,18 @@ static int get_vdi_bitmap_range(const char *name, unsigned long *left,
 				unsigned long *right)
 {
 	*left = sd_hash_vdi(name);
+
+	if (unlikely(*left == SD_NR_VDIS - 1 || !*left))
+		*left = 1;	/* 0xffffff and 0x000000 should be skipeed */
+
 	*right = find_next_zero_bit(sys->vdi_inuse, SD_NR_VDIS, *left);
 	if (*left == *right)
 		return SD_RES_NO_VDI;
 
-	if (*right == SD_NR_VDIS) {
+	if (*right == SD_NR_VDIS - 1) {
 		/* Wrap around */
-		*right = find_next_zero_bit(sys->vdi_inuse, SD_NR_VDIS, 0);
-		if (*right == SD_NR_VDIS)
+		*right = find_next_zero_bit(sys->vdi_inuse, SD_NR_VDIS, 1);
+		if (*right == SD_NR_VDIS - 1)
 			return SD_RES_FULL_VDI;
 	}
 	return SD_RES_SUCCESS;
@@ -1404,7 +1408,15 @@ static int fill_vdi_info_range(uint32_t left, uint32_t right,
 		ret = SD_RES_NO_MEM;
 		goto out;
 	}
-	for (i = right - 1; i >= left; i--) {
+	for (i = right - 1; i >= left && i; i--) {
+		/*
+		 * below bitmap checking is an optimization for
+		 * vdi_lookup_for_creation()
+		 */
+		if (!test_bit(i, sys->vdi_inuse) &&
+		    !test_bit(i, sys->vdi_deleted))
+			continue;
+
 		ret = sd_read_object(vid_to_vdi_oid(i), (char *)inode,
 				     SD_INODE_HEADER_SIZE, 0);
 		if (ret != SD_RES_SUCCESS)
@@ -1448,10 +1460,20 @@ static int fill_vdi_info(unsigned long left, unsigned long right,
 {
 	int ret;
 
+	assert(left != right);
+	/*
+	 * If left == right, fill_vdi_info() shouldn't called by vdi_lookup().
+	 * vdi_lookup() must return SD_RES_NO_VDI to its caller.
+	 */
+
 	if (left < right)
 		return fill_vdi_info_range(left, right, iocb, info);
 
-	ret = fill_vdi_info_range(0, right, iocb, info);
+	if (likely(1 < right))
+		ret = fill_vdi_info_range(1, right, iocb, info);
+	else
+		ret = SD_RES_NO_VDI;
+
 	switch (ret) {
 	case SD_RES_NO_VDI:
 	case SD_RES_NO_TAG:
-- 
1.9.1