[PATCH 0/2] rbd: clear EXISTS flag for disappearing snapshot

[PATCH 0/2] rbd: clear EXISTS flag for disappearing snapshot

[Alex Elder]

The first patch in this series puts back some functionality
that was deleted inadvertently by the previous commit.  Josh
pointed out it had disappeared.  The second one replaces a
linear search of snapshot ids with a binary search for
efficiency.

					-Alex

[PATCH 1/2] rbd: clear EXISTS flag if mapped snapshot disappears
[PATCH 2/2] rbd: use binary search for snapshot lookup

[PATCH 1/2] rbd: clear EXISTS flag if mapped snapshot disappears

[Alex Elder]

This functionality inadvertently disappeared in the last patch.

Image snapshots can get removed at just about any time.  In
particular it can disappear even if it is in use by an rbd
client as a mapped image.

The rbd client deals with such a disappearance by responding to new
requests with ENXIO.  This is implemented by each rbd device
maintaining an EXISTS flag, which is normally set but cleared if a
snapshot disappears.

This patch (re-)implements the clearing of that flag.

Whenever mapped image header information is refreshed, if the
mapping is for a snapshot, verify the mapped snapshot is still
present in the updated snapshot context.  If it is not, clear the
flag.

It is not necessary to check this in the initial probe, because the
probe will not succeed if the snapshot doesn't exist.

This resolves:
    http://tracker.ceph.com/issues/4880

Signed-off-by: Alex Elder <elder@inktank.com>
---
 drivers/block/rbd.c |   23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 0ca959f..3f58aba 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -3114,6 +3114,25 @@ static int rbd_dev_v1_refresh(struct rbd_device
*rbd_dev)
 	return ret;
 }

+/*
+ * Clear the rbd device's EXISTS flag if the snapshot it's mapped to
+ * has disappeared from the (just updated) snapshot context.
+ */
+static void rbd_exists_validate(struct rbd_device *rbd_dev)
+{
+	u64 snap_id;
+
+	if (!test_bit(RBD_DEV_FLAG_EXISTS, &rbd_dev->flags))
+		return;
+
+	snap_id = rbd_dev->spec->snap_id;
+	if (snap_id == CEPH_NOSNAP)
+		return;
+
+	if (rbd_dev_snap_index(rbd_dev, snap_id) == BAD_SNAP_INDEX)
+		clear_bit(RBD_DEV_FLAG_EXISTS, &rbd_dev->flags);
+}
+
 static int rbd_dev_refresh(struct rbd_device *rbd_dev)
 {
 	u64 image_size;
@@ -3126,6 +3145,10 @@ static int rbd_dev_refresh(struct rbd_device
*rbd_dev)
 		ret = rbd_dev_v1_refresh(rbd_dev);
 	else
 		ret = rbd_dev_v2_refresh(rbd_dev);
+
+	/* If it's a mapped snapshot, validate its EXISTS flag */
+
+	rbd_exists_validate(rbd_dev);
 	mutex_unlock(&ctl_mutex);
 	if (ret)
 		rbd_warn(rbd_dev, "got notification but failed to "
-- 
1.7.9.5

[PATCH 2/2] rbd: use binary search for snapshot lookup

[Alex Elder]

Use bsearch(3) to make snapshot lookup by id more efficient.  (There
could be thousands of snapshots, and conceivably many more.)

Signed-off-by: Alex Elder <elder@inktank.com>
---
 drivers/block/rbd.c |   34 +++++++++++++++++++++++++++++-----
 1 file changed, 29 insertions(+), 5 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 3f58aba..a6e5fe3 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -33,6 +33,7 @@
 #include <linux/ceph/mon_client.h>
 #include <linux/ceph/decode.h>
 #include <linux/parser.h>
+#include <linux/bsearch.h>

 #include <linux/kernel.h>
 #include <linux/device.h>
@@ -819,16 +820,39 @@ static const char *_rbd_dev_v1_snap_name(struct
rbd_device *rbd_dev, u32 which)
 	return kstrdup(snap_name, GFP_KERNEL);
 }

+/*
+ * Snapshot id comparison function for use with qsort()/bsearch().
+ * Note that result is for snapshots in *descending* order.
+ */
+static int snapid_compare_reverse(const void *s1, const void *s2)
+{
+	u64 snap_id1 = *(u64 *)s1;
+	u64 snap_id2 = *(u64 *)s2;
+
+	if (snap_id1 < snap_id2)
+		return 1;
+	return snap_id1 == snap_id2 ? 0 : 1;
+}
+
+/*
+ * Search a snapshot context to see if the given snapshot id is
+ * present.
+ *
+ * Returns the position of the snapshot id in the array if it's found,
+ * or BAD_SNAP_INDEX otherwise.
+ *
+ * Note: The snapshot array is in kept sorted (by the osd) in
+ * reverse order, highest snapshot id first.
+ */
 static u32 rbd_dev_snap_index(struct rbd_device *rbd_dev, u64 snap_id)
 {
 	struct ceph_snap_context *snapc = rbd_dev->header.snapc;
-	u32 which;
+	u64 *found;

-	for (which = 0; which < snapc->num_snaps; which++)
-		if (snapc->snaps[which] == snap_id)
-			return which;
+	found = bsearch(&snap_id, &snapc->snaps, snapc->num_snaps,
+				sizeof (snap_id), snapid_compare_reverse);

-	return BAD_SNAP_INDEX;
+	return found ? (u32)(found - &snapc->snaps[0]) : BAD_SNAP_INDEX;
 }

 static const char *rbd_dev_v1_snap_name(struct rbd_device *rbd_dev,
-- 
1.7.9.5

Re: [PATCH 0/2] rbd: clear EXISTS flag for disappearing snapshot

[Alex Elder]

On 05/01/2013 04:29 PM, Alex Elder wrote:
> The first patch in this series puts back some functionality
> that was deleted inadvertently by the previous commit.  Josh
> pointed out it had disappeared.  The second one replaces a
> linear search of snapshot ids with a binary search for
> efficiency.
> 
> 					-Alex

These patches are available in the "review/wip-slabs" branch of
the ceph-client git repository.  The patches in these other two
series are there as well:

[PATCH 0/4] rbd: use slab caches for frequently allocated structures
[PATCH 0/3] libceph: use slab caches in messenger and osd osd client

					-Alex

> [PATCH 1/2] rbd: clear EXISTS flag if mapped snapshot disappears
> [PATCH 2/2] rbd: use binary search for snapshot lookup
> 

Re: [PATCH 1/2] rbd: clear EXISTS flag if mapped snapshot disappears

[Josh Durgin]

Reviewed-by: Josh Durgin <josh.durgin@inktank.com>

On 05/01/2013 02:32 PM, Alex Elder wrote:
> This functionality inadvertently disappeared in the last patch.
>
> Image snapshots can get removed at just about any time.  In
> particular it can disappear even if it is in use by an rbd
> client as a mapped image.
>
> The rbd client deals with such a disappearance by responding to new
> requests with ENXIO.  This is implemented by each rbd device
> maintaining an EXISTS flag, which is normally set but cleared if a
> snapshot disappears.
>
> This patch (re-)implements the clearing of that flag.
>
> Whenever mapped image header information is refreshed, if the
> mapping is for a snapshot, verify the mapped snapshot is still
> present in the updated snapshot context.  If it is not, clear the
> flag.
>
> It is not necessary to check this in the initial probe, because the
> probe will not succeed if the snapshot doesn't exist.
>
> This resolves:
>      http://tracker.ceph.com/issues/4880
>
> Signed-off-by: Alex Elder <elder@inktank.com>
> ---
>   drivers/block/rbd.c |   23 +++++++++++++++++++++++
>   1 file changed, 23 insertions(+)
>
> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
> index 0ca959f..3f58aba 100644
> --- a/drivers/block/rbd.c
> +++ b/drivers/block/rbd.c
> @@ -3114,6 +3114,25 @@ static int rbd_dev_v1_refresh(struct rbd_device
> *rbd_dev)
>   	return ret;
>   }
>
> +/*
> + * Clear the rbd device's EXISTS flag if the snapshot it's mapped to
> + * has disappeared from the (just updated) snapshot context.
> + */
> +static void rbd_exists_validate(struct rbd_device *rbd_dev)
> +{
> +	u64 snap_id;
> +
> +	if (!test_bit(RBD_DEV_FLAG_EXISTS, &rbd_dev->flags))
> +		return;
> +
> +	snap_id = rbd_dev->spec->snap_id;
> +	if (snap_id == CEPH_NOSNAP)
> +		return;
> +
> +	if (rbd_dev_snap_index(rbd_dev, snap_id) == BAD_SNAP_INDEX)
> +		clear_bit(RBD_DEV_FLAG_EXISTS, &rbd_dev->flags);
> +}
> +
>   static int rbd_dev_refresh(struct rbd_device *rbd_dev)
>   {
>   	u64 image_size;
> @@ -3126,6 +3145,10 @@ static int rbd_dev_refresh(struct rbd_device
> *rbd_dev)
>   		ret = rbd_dev_v1_refresh(rbd_dev);
>   	else
>   		ret = rbd_dev_v2_refresh(rbd_dev);
> +
> +	/* If it's a mapped snapshot, validate its EXISTS flag */
> +
> +	rbd_exists_validate(rbd_dev);
>   	mutex_unlock(&ctl_mutex);
>   	if (ret)
>   		rbd_warn(rbd_dev, "got notification but failed to "
>

Re: [PATCH 2/2] rbd: use binary search for snapshot lookup

[Josh Durgin]

On 05/01/2013 02:32 PM, Alex Elder wrote:
> Use bsearch(3) to make snapshot lookup by id more efficient.  (There
> could be thousands of snapshots, and conceivably many more.)
>
> Signed-off-by: Alex Elder <elder@inktank.com>
> ---
>   drivers/block/rbd.c |   34 +++++++++++++++++++++++++++++-----
>   1 file changed, 29 insertions(+), 5 deletions(-)
>
> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
> index 3f58aba..a6e5fe3 100644
> --- a/drivers/block/rbd.c
> +++ b/drivers/block/rbd.c
> @@ -33,6 +33,7 @@
>   #include <linux/ceph/mon_client.h>
>   #include <linux/ceph/decode.h>
>   #include <linux/parser.h>
> +#include <linux/bsearch.h>
>
>   #include <linux/kernel.h>
>   #include <linux/device.h>
> @@ -819,16 +820,39 @@ static const char *_rbd_dev_v1_snap_name(struct
> rbd_device *rbd_dev, u32 which)
>   	return kstrdup(snap_name, GFP_KERNEL);
>   }
>
> +/*
> + * Snapshot id comparison function for use with qsort()/bsearch().
> + * Note that result is for snapshots in *descending* order.
> + */
> +static int snapid_compare_reverse(const void *s1, const void *s2)
> +{
> +	u64 snap_id1 = *(u64 *)s1;
> +	u64 snap_id2 = *(u64 *)s2;
> +
> +	if (snap_id1 < snap_id2)
> +		return 1;

I think this 1 should be -1. Looks good otherwise.

Reviewed-by: Josh Durgin <josh.durgin@inktank.com>

> +	return snap_id1 == snap_id2 ? 0 : 1;
> +}
> +
> +/*
> + * Search a snapshot context to see if the given snapshot id is
> + * present.
> + *
> + * Returns the position of the snapshot id in the array if it's found,
> + * or BAD_SNAP_INDEX otherwise.
> + *
> + * Note: The snapshot array is in kept sorted (by the osd) in
> + * reverse order, highest snapshot id first.
> + */
>   static u32 rbd_dev_snap_index(struct rbd_device *rbd_dev, u64 snap_id)
>   {
>   	struct ceph_snap_context *snapc = rbd_dev->header.snapc;
> -	u32 which;
> +	u64 *found;
>
> -	for (which = 0; which < snapc->num_snaps; which++)
> -		if (snapc->snaps[which] == snap_id)
> -			return which;
> +	found = bsearch(&snap_id, &snapc->snaps, snapc->num_snaps,
> +				sizeof (snap_id), snapid_compare_reverse);
>
> -	return BAD_SNAP_INDEX;
> +	return found ? (u32)(found - &snapc->snaps[0]) : BAD_SNAP_INDEX;
>   }
>
>   static const char *rbd_dev_v1_snap_name(struct rbd_device *rbd_dev,
>

Re: [PATCH 2/2] rbd: use binary search for snapshot lookup

[Alex Elder]

On 05/02/2013 11:47 AM, Josh Durgin wrote:
> On 05/01/2013 02:32 PM, Alex Elder wrote:
>> Use bsearch(3) to make snapshot lookup by id more efficient.  (There
>> could be thousands of snapshots, and conceivably many more.)
>>
>> Signed-off-by: Alex Elder <elder@inktank.com>
>> ---
>>   drivers/block/rbd.c |   34 +++++++++++++++++++++++++++++-----
>>   1 file changed, 29 insertions(+), 5 deletions(-)
>>
>> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
>> index 3f58aba..a6e5fe3 100644
>> --- a/drivers/block/rbd.c
>> +++ b/drivers/block/rbd.c
>> @@ -33,6 +33,7 @@
>>   #include <linux/ceph/mon_client.h>
>>   #include <linux/ceph/decode.h>
>>   #include <linux/parser.h>
>> +#include <linux/bsearch.h>
>>
>>   #include <linux/kernel.h>
>>   #include <linux/device.h>
>> @@ -819,16 +820,39 @@ static const char *_rbd_dev_v1_snap_name(struct
>> rbd_device *rbd_dev, u32 which)
>>       return kstrdup(snap_name, GFP_KERNEL);
>>   }
>>
>> +/*
>> + * Snapshot id comparison function for use with qsort()/bsearch().
>> + * Note that result is for snapshots in *descending* order.
>> + */
>> +static int snapid_compare_reverse(const void *s1, const void *s2)
>> +{
>> +    u64 snap_id1 = *(u64 *)s1;
>> +    u64 snap_id2 = *(u64 *)s2;
>> +
>> +    if (snap_id1 < snap_id2)
>> +        return 1;
> 
> I think this 1 should be -1. Looks good otherwise.

No, this one should be one (for reverse sort).
But the other one--below--should be -1.

I tested this with a little user space program
and I did in fact have it right at one time,
but somehow I screwed it up when transferring
it over.

Very good eye on these, as usual.  Thanks a lot.

					-Alex
> 
> Reviewed-by: Josh Durgin <josh.durgin@inktank.com>
> 
>> +    return snap_id1 == snap_id2 ? 0 : 1;
>> +}
>> +
>> +/*
>> + * Search a snapshot context to see if the given snapshot id is
>> + * present.
>> + *
>> + * Returns the position of the snapshot id in the array if it's found,
>> + * or BAD_SNAP_INDEX otherwise.
>> + *
>> + * Note: The snapshot array is in kept sorted (by the osd) in
>> + * reverse order, highest snapshot id first.
>> + */
>>   static u32 rbd_dev_snap_index(struct rbd_device *rbd_dev, u64 snap_id)
>>   {
>>       struct ceph_snap_context *snapc = rbd_dev->header.snapc;
>> -    u32 which;
>> +    u64 *found;
>>
>> -    for (which = 0; which < snapc->num_snaps; which++)
>> -        if (snapc->snaps[which] == snap_id)
>> -            return which;
>> +    found = bsearch(&snap_id, &snapc->snaps, snapc->num_snaps,
>> +                sizeof (snap_id), snapid_compare_reverse);
>>
>> -    return BAD_SNAP_INDEX;
>> +    return found ? (u32)(found - &snapc->snaps[0]) : BAD_SNAP_INDEX;
>>   }
>>
>>   static const char *rbd_dev_v1_snap_name(struct rbd_device *rbd_dev,
>>
>