[PATCH 0/5] rbd: improve how rbd ids are selected

[PATCH 0/5] rbd: improve how rbd ids are selected

[Alex Elder]

New rbd devices are granted a unique identifiers based on how many
devices are already in existence.  This series rearranges how that
is done, switching from using a spinlock to using an atomic variable
to select the next rbd id to use.  In the process a bit of the code
got a bit more isolated.

					-Alex

[PATCH 2/5] rbd: encapsulate new rbd id selection

[Alex Elder]

Move the loop that finds a new unique rbd id to use into
its own helper function.

Signed-off-by: Alex Elder <elder@dreamhost.com>
---
  drivers/block/rbd.c |   30 +++++++++++++++++++-----------
  1 files changed, 19 insertions(+), 11 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 25ed3c0..35290b1 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -2148,6 +2148,23 @@ static int rbd_init_watch_dev(struct rbd_device 
*rbd_dev)
  	return ret;
  }

+/* caller must hold ctl_mutex */
+static int rbd_id_get(void)
+{
+	struct list_head *tmp;
+	int new_id = 0;
+
+	list_for_each(tmp, &rbd_dev_list) {
+		struct rbd_device *rbd_dev;
+
+		rbd_dev = list_entry(tmp, struct rbd_device, node);
+		if (rbd_dev->id >= new_id)
+			new_id = rbd_dev->id + 1;
+	}
+
+	return new_id;
+}
+
  static ssize_t rbd_add(struct bus_type *bus,
  		       const char *buf,
  		       size_t count)
@@ -2155,8 +2172,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	struct ceph_osd_client *osdc;
  	struct rbd_device *rbd_dev;
  	ssize_t rc = -ENOMEM;
-	int irc, new_id = 0;
-	struct list_head *tmp;
+	int irc;
  	char *mon_dev_name;
  	char *options;

@@ -2184,15 +2200,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	/* generate unique id: find highest unique id, add one */
  	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);

-	list_for_each(tmp, &rbd_dev_list) {
-		struct rbd_device *rbd_dev;
-
-		rbd_dev = list_entry(tmp, struct rbd_device, node);
-		if (rbd_dev->id >= new_id)
-			new_id = rbd_dev->id + 1;
-	}
-
-	rbd_dev->id = new_id;
+	rbd_dev->id = rbd_id_get();

  	/* add to global list */
  	list_add_tail(&rbd_dev->node, &rbd_dev_list);
-- 
1.7.5.4

[PATCH 2/5] rbd: rework calculation of new rbd id's

[Alex Elder]

In order to select a new unique identifier for an added rbd device,
the list of all existing ones is searched and a value one greater
than the highest id is used.

The list search can be avoided by using an atomic variable that
keeps track of the current highest id.  Using a get/put model for
id's we can limit the boundless growth of id numbers a bit by
arranging to reuse the current highest id once it gets released.
Add these calls to "put" the id when an rbd is getting removed.

Note that this changes the pattern of device id's used--new values
will never be below the highest one seen so far (even if there
exists an unused lower one).  I assert this is OK because the key
property of an rbd id is its uniqueness, not its magnitude.

Regardless, a follow-on patch will restore the old way of doing
things, I just think this commit just makes the incremental change
to atomics a little easier to understand.

Signed-off-by: Alex Elder <elder@dreamhost.com>
---
  drivers/block/rbd.c |   35 +++++++++++++++++++++++------------
  1 files changed, 23 insertions(+), 12 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 35290b1..0c492e4 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -2148,21 +2148,29 @@ static int rbd_init_watch_dev(struct rbd_device 
*rbd_dev)
  	return ret;
  }

-/* caller must hold ctl_mutex */
+static atomic_t rbd_id_max = ATOMIC_INIT(0);
+
+/*
+ * Get a unique rbd identifier.  The minimum rbd id is 1.
+ */
  static int rbd_id_get(void)
  {
-	struct list_head *tmp;
-	int new_id = 0;
-
-	list_for_each(tmp, &rbd_dev_list) {
-		struct rbd_device *rbd_dev;
+	return atomic_inc_return(&rbd_id_max);
+}

-		rbd_dev = list_entry(tmp, struct rbd_device, node);
-		if (rbd_dev->id >= new_id)
-			new_id = rbd_dev->id + 1;
-	}
+/*
+ * Record that an rbd identifier is no longer in use.
+ */
+static void rbd_id_put(int rbd_id)
+{
+	BUG_ON(rbd_id < 1);

-	return new_id;
+	/*
+	 * New id's are always one more than the current maximum.
+	 * If the id being "put" *is* that maximum, decrement the
+	 * maximum so the next one requested just reuses this one.
+	 */
+	atomic_cmpxchg(&rbd_id_max, rbd_id, rbd_id - 1);
  }

  static ssize_t rbd_add(struct bus_type *bus,
@@ -2197,7 +2205,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	INIT_LIST_HEAD(&rbd_dev->node);
  	INIT_LIST_HEAD(&rbd_dev->snaps);

-	/* generate unique id: find highest unique id, add one */
+	/* generate unique id: one more than highest used so far */
  	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);

  	rbd_dev->id = rbd_id_get();
@@ -2267,6 +2275,7 @@ err_out_bus:
  	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
  	list_del_init(&rbd_dev->node);
  	mutex_unlock(&ctl_mutex);
+	rbd_id_put(target_id);

  	/* this will also clean up rest of rbd_dev stuff */

@@ -2283,6 +2292,7 @@ err_out_client:
  err_out_slot:
  	list_del_init(&rbd_dev->node);
  	mutex_unlock(&ctl_mutex);
+	rbd_id_put(target_id);

  	kfree(rbd_dev);
  err_out_opt:
@@ -2360,6 +2370,7 @@ static ssize_t rbd_remove(struct bus_type *bus,
  	}

  	list_del_init(&rbd_dev->node);
+	rbd_id_put(target_id);

  	__rbd_remove_all_snaps(rbd_dev);
  	rbd_bus_del_dev(rbd_dev);
-- 
1.7.5.4

Re: [PATCH 2/5] rbd: rework calculation of new rbd id's

[Yehuda Sadeh Weinraub]

On Tue, Feb 28, 2012 at 7:40 PM, Alex Elder <elder@dreamhost.com> wrote:
> In order to select a new unique identifier for an added rbd device,
> the list of all existing ones is searched and a value one greater
> than the highest id is used.
>
> The list search can be avoided by using an atomic variable that
> keeps track of the current highest id.  Using a get/put model for
> id's we can limit the boundless growth of id numbers a bit by
> arranging to reuse the current highest id once it gets released.
> Add these calls to "put" the id when an rbd is getting removed.
>
> Note that this changes the pattern of device id's used--new values
> will never be below the highest one seen so far (even if there
> exists an unused lower one).  I assert this is OK because the key
> property of an rbd id is its uniqueness, not its magnitude.
>
> Regardless, a follow-on patch will restore the old way of doing
> things, I just think this commit just makes the incremental change
> to atomics a little easier to understand.
>
> Signed-off-by: Alex Elder <elder@dreamhost.com>
> ---
>  drivers/block/rbd.c |   35 +++++++++++++++++++++++------------
>  1 files changed, 23 insertions(+), 12 deletions(-)
>
> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
> index 35290b1..0c492e4 100644
> --- a/drivers/block/rbd.c
> +++ b/drivers/block/rbd.c
> @@ -2148,21 +2148,29 @@ static int rbd_init_watch_dev(struct rbd_device
> *rbd_dev)
>        return ret;
>  }
>
> -/* caller must hold ctl_mutex */
> +static atomic_t rbd_id_max = ATOMIC_INIT(0);
> +
> +/*
> + * Get a unique rbd identifier.  The minimum rbd id is 1.
> + */
>  static int rbd_id_get(void)
>  {
> -       struct list_head *tmp;
> -       int new_id = 0;
> -
> -       list_for_each(tmp, &rbd_dev_list) {
> -               struct rbd_device *rbd_dev;
> +       return atomic_inc_return(&rbd_id_max);
> +}
>
> -               rbd_dev = list_entry(tmp, struct rbd_device, node);
> -               if (rbd_dev->id >= new_id)
> -                       new_id = rbd_dev->id + 1;
> -       }
> +/*
> + * Record that an rbd identifier is no longer in use.
> + */
> +static void rbd_id_put(int rbd_id)
> +{
> +       BUG_ON(rbd_id < 1);

A scenario where you have a few devices that keep being added/removed
in order (e.g., for backup purposes) may exhaust the 31 bits used for
this purpose. Can we use a 64 bit counter (is atomic64_t a good idea?)

>
> -       return new_id;
> +       /*
> +        * New id's are always one more than the current maximum.
> +        * If the id being "put" *is* that maximum, decrement the
> +        * maximum so the next one requested just reuses this one.
> +        */
> +       atomic_cmpxchg(&rbd_id_max, rbd_id, rbd_id - 1);
>  }
>
>  static ssize_t rbd_add(struct bus_type *bus,
> @@ -2197,7 +2205,7 @@ static ssize_t rbd_add(struct bus_type *bus,
>        INIT_LIST_HEAD(&rbd_dev->node);
>        INIT_LIST_HEAD(&rbd_dev->snaps);
>
> -       /* generate unique id: find highest unique id, add one */
> +       /* generate unique id: one more than highest used so far */
>        mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
>
>        rbd_dev->id = rbd_id_get();
> @@ -2267,6 +2275,7 @@ err_out_bus:
>        mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
>        list_del_init(&rbd_dev->node);
>        mutex_unlock(&ctl_mutex);
> +       rbd_id_put(target_id);
>
>        /* this will also clean up rest of rbd_dev stuff */
>
> @@ -2283,6 +2292,7 @@ err_out_client:
>  err_out_slot:
>        list_del_init(&rbd_dev->node);
>        mutex_unlock(&ctl_mutex);
> +       rbd_id_put(target_id);
>
>        kfree(rbd_dev);
>  err_out_opt:
> @@ -2360,6 +2370,7 @@ static ssize_t rbd_remove(struct bus_type *bus,
>        }
>
>        list_del_init(&rbd_dev->node);
> +       rbd_id_put(target_id);
>
>        __rbd_remove_all_snaps(rbd_dev);
>        rbd_bus_del_dev(rbd_dev);
> --
> 1.7.5.4
>
> --
> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 3/5] rbd: protect the rbd_dev_list with a spinlock

[Alex Elder]

The rbd_dev_list is just a simple list of all the current
rbd_devices.  Using the ctl_mutex as a concurrency guard is
overkill.  Instead, use a spinlock for that specific purpose.

This also reduces the window that the ctl_mutex needs to be held in
rbd_add().

Signed-off-by: Alex Elder <elder@dreamhost.com>
---
  drivers/block/rbd.c |   33 ++++++++++++++++++++++-----------
  1 files changed, 22 insertions(+), 11 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 0c492e4..e839289 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -174,11 +174,13 @@ static struct bus_type rbd_bus_type = {
  	.name		= "rbd",
  };

-static DEFINE_SPINLOCK(node_lock);      /* protects client get/put */
-
  static DEFINE_MUTEX(ctl_mutex);	  /* Serialize 
open/close/setup/teardown */
+
  static LIST_HEAD(rbd_dev_list);    /* devices */
+static DEFINE_SPINLOCK(rbd_dev_list_lock);
+
  static LIST_HEAD(rbd_client_list);      /* clients */
+static DEFINE_SPINLOCK(node_lock);      /* protects client get/put */

  static int __rbd_init_snaps_header(struct rbd_device *rbd_dev);
  static void rbd_dev_release(struct device *dev);
@@ -2206,12 +2208,12 @@ static ssize_t rbd_add(struct bus_type *bus,
  	INIT_LIST_HEAD(&rbd_dev->snaps);

  	/* generate unique id: one more than highest used so far */
-	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
-
  	rbd_dev->id = rbd_id_get();

  	/* add to global list */
+	spin_lock(&rbd_dev_list_lock);
  	list_add_tail(&rbd_dev->node, &rbd_dev_list);
+	spin_unlock(&rbd_dev_list_lock);

  	/* parse add command */
  	if (sscanf(buf, "%" __stringify(RBD_MAX_OPT_LEN) "s "
@@ -2235,12 +2237,14 @@ static ssize_t rbd_add(struct bus_type *bus,

  	/* initialize rest of new object */
  	snprintf(rbd_dev->name, DEV_NAME_LEN, DRV_NAME "%d", rbd_dev->id);
+
+	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
  	rc = rbd_get_client(rbd_dev, mon_dev_name, options);
+	mutex_unlock(&ctl_mutex);
+
  	if (rc < 0)
  		goto err_out_slot;

-	mutex_unlock(&ctl_mutex);
-
  	/* pick the pool */
  	osdc = &rbd_dev->rbd_client->client->osdc;
  	rc = ceph_pg_poolid_by_name(osdc->osdmap, rbd_dev->pool_name);
@@ -2272,9 +2276,9 @@ static ssize_t rbd_add(struct bus_type *bus,
  	return count;

  err_out_bus:
-	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
+	spin_lock(&rbd_dev_list_lock);
  	list_del_init(&rbd_dev->node);
-	mutex_unlock(&ctl_mutex);
+	spin_unlock(&rbd_dev_list_lock);
  	rbd_id_put(target_id);

  	/* this will also clean up rest of rbd_dev stuff */
@@ -2288,10 +2292,10 @@ err_out_blkdev:
  	unregister_blkdev(rbd_dev->major, rbd_dev->name);
  err_out_client:
  	rbd_put_client(rbd_dev);
-	mutex_lock_nested(&ctl_mutex, SINGLE_DEPTH_NESTING);
  err_out_slot:
+	spin_lock(&rbd_dev_list_lock);
  	list_del_init(&rbd_dev->node);
-	mutex_unlock(&ctl_mutex);
+	spin_unlock(&rbd_dev_list_lock);
  	rbd_id_put(target_id);

  	kfree(rbd_dev);
@@ -2310,11 +2314,15 @@ static struct rbd_device *__rbd_get_dev(unsigned 
long id)
  	struct list_head *tmp;
  	struct rbd_device *rbd_dev;

+	spin_lock(&rbd_dev_list_lock);
  	list_for_each(tmp, &rbd_dev_list) {
  		rbd_dev = list_entry(tmp, struct rbd_device, node);
-		if (rbd_dev->id == id)
+		if (rbd_dev->id == id) {
+			spin_unlock(&rbd_dev_list_lock);
  			return rbd_dev;
+		}
  	}
+	spin_unlock(&rbd_dev_list_lock);
  	return NULL;
  }

@@ -2369,7 +2377,10 @@ static ssize_t rbd_remove(struct bus_type *bus,
  		goto done;
  	}

+	spin_lock(&rbd_dev_list_lock);
  	list_del_init(&rbd_dev->node);
+	spin_unlock(&rbd_dev_list_lock);
+
  	rbd_id_put(target_id);

  	__rbd_remove_all_snaps(rbd_dev);
-- 
1.7.5.4

[PATCH 4/5] rbd: tie rbd_dev_list changes to rbd_id operations

[Alex Elder]

The only time entries are added to or removed from the global
rbd_dev_list is exactly when a "put" or "get" operation is being
performed on a rbd_dev's id.  So just move the list management code
into get/put routines.

Signed-off-by: Alex Elder <elder@dreamhost.com>
---
  drivers/block/rbd.c |   47 +++++++++++++++++++++--------------------------
  1 files changed, 21 insertions(+), 26 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index e839289..042377b 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -2153,26 +2153,36 @@ static int rbd_init_watch_dev(struct rbd_device 
*rbd_dev)
  static atomic_t rbd_id_max = ATOMIC_INIT(0);

  /*
- * Get a unique rbd identifier.  The minimum rbd id is 1.
+ * Get a unique rbd identifier for the given new rbd_dev, and add
+ * the rbd_dev to the global list.  The minimum rbd id is 1.
   */
-static int rbd_id_get(void)
+static void rbd_id_get(struct rbd_device *rbd_dev)
  {
-	return atomic_inc_return(&rbd_id_max);
+	rbd_dev->id = atomic_inc_return(&rbd_id_max);
+
+	spin_lock(&rbd_dev_list_lock);
+	list_add_tail(&rbd_dev->node, &rbd_dev_list);
+	spin_unlock(&rbd_dev_list_lock);
  }

  /*
- * Record that an rbd identifier is no longer in use.
+ * Remove an rbd_dev from the global list, and record that its
+ * identifier is no longer in use.
   */
-static void rbd_id_put(int rbd_id)
+static void rbd_id_put(struct rbd_device *rbd_dev)
  {
-	BUG_ON(rbd_id < 1);
+	BUG_ON(rbd_dev->id < 1);
+
+	spin_lock(&rbd_dev_list_lock);
+	list_del_init(&rbd_dev->node);
+	spin_unlock(&rbd_dev_list_lock);

  	/*
  	 * New id's are always one more than the current maximum.
  	 * If the id being "put" *is* that maximum, decrement the
  	 * maximum so the next one requested just reuses this one.
  	 */
-	atomic_cmpxchg(&rbd_id_max, rbd_id, rbd_id - 1);
+	atomic_cmpxchg(&rbd_id_max, rbd_dev->id, rbd_dev->id - 1);
  }

  static ssize_t rbd_add(struct bus_type *bus,
@@ -2208,12 +2218,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	INIT_LIST_HEAD(&rbd_dev->snaps);

  	/* generate unique id: one more than highest used so far */
-	rbd_dev->id = rbd_id_get();
-
-	/* add to global list */
-	spin_lock(&rbd_dev_list_lock);
-	list_add_tail(&rbd_dev->node, &rbd_dev_list);
-	spin_unlock(&rbd_dev_list_lock);
+	rbd_id_get(rbd_dev);

  	/* parse add command */
  	if (sscanf(buf, "%" __stringify(RBD_MAX_OPT_LEN) "s "
@@ -2276,10 +2281,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	return count;

  err_out_bus:
-	spin_lock(&rbd_dev_list_lock);
-	list_del_init(&rbd_dev->node);
-	spin_unlock(&rbd_dev_list_lock);
-	rbd_id_put(target_id);
+	rbd_id_put(rbd_dev);

  	/* this will also clean up rest of rbd_dev stuff */

@@ -2293,10 +2295,7 @@ err_out_blkdev:
  err_out_client:
  	rbd_put_client(rbd_dev);
  err_out_slot:
-	spin_lock(&rbd_dev_list_lock);
-	list_del_init(&rbd_dev->node);
-	spin_unlock(&rbd_dev_list_lock);
-	rbd_id_put(target_id);
+	rbd_id_put(rbd_dev);

  	kfree(rbd_dev);
  err_out_opt:
@@ -2377,11 +2376,7 @@ static ssize_t rbd_remove(struct bus_type *bus,
  		goto done;
  	}

-	spin_lock(&rbd_dev_list_lock);
-	list_del_init(&rbd_dev->node);
-	spin_unlock(&rbd_dev_list_lock);
-
-	rbd_id_put(target_id);
+	rbd_id_put(rbd_dev);

  	__rbd_remove_all_snaps(rbd_dev);
  	rbd_bus_del_dev(rbd_dev);
-- 
1.7.5.4

[PATCH 5/5] rbd: restore previous rbd id sequence behavior

[Alex Elder]

It used to be that selecting a new unique identifier for an added
rbd device required searching all existing ones to find the highest
id is used.  A recent change made that unnecessary, but made it
so that id's used were monotonically non-decreasing.  It's a bit
more pleasant to have smaller rbd id's though, and this change
makes ids get allocated as they were before--each new id is one more
than the maximum currently in use.

Signed-off-by: Alex Elder <elder@dreamhost.com>
---
  drivers/block/rbd.c |   40 ++++++++++++++++++++++++++++++++++------
  1 files changed, 34 insertions(+), 6 deletions(-)

diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
index 042377b..4c5bb39 100644
--- a/drivers/block/rbd.c
+++ b/drivers/block/rbd.c
@@ -2171,18 +2171,46 @@ static void rbd_id_get(struct rbd_device *rbd_dev)
   */
  static void rbd_id_put(struct rbd_device *rbd_dev)
  {
-	BUG_ON(rbd_dev->id < 1);
+	struct list_head *tmp;
+	int rbd_id = rbd_dev->id;
+	int max_id;
+
+	BUG_ON(rbd_id < 1);

  	spin_lock(&rbd_dev_list_lock);
  	list_del_init(&rbd_dev->node);
+
+	/*
+	 * If the id being "put" is not the current maximum, there
+	 * is nothing special we need to do.
+	 */
+	if (rbd_id != atomic_read(&rbd_id_max)) {
+		spin_unlock(&rbd_dev_list_lock);
+		return;
+	}
+
+	/*
+	 * We need to update the current maximum id.  Search the
+	 * list to find out what it is.  We're more likely to find
+	 * the maximum at the end, so search the list backward.
+	 */
+	max_id = 0;
+	list_for_each_prev(tmp, &rbd_dev_list) {
+		struct rbd_device *rbd_dev;
+
+		rbd_dev = list_entry(tmp, struct rbd_device, node);
+		if (rbd_id > max_id)
+			max_id = rbd_id;
+	}
  	spin_unlock(&rbd_dev_list_lock);

  	/*
-	 * New id's are always one more than the current maximum.
-	 * If the id being "put" *is* that maximum, decrement the
-	 * maximum so the next one requested just reuses this one.
+	 * The max id could have been updated by rbd_id_get(), in
+	 * which case it now accurately reflects the new maximum.
+	 * Be careful not to overwrite the maximum value in that
+	 * case.
  	 */
-	atomic_cmpxchg(&rbd_id_max, rbd_dev->id, rbd_dev->id - 1);
+	atomic_cmpxchg(&rbd_id_max, rbd_id, max_id);
  }

  static ssize_t rbd_add(struct bus_type *bus,
@@ -2217,7 +2245,7 @@ static ssize_t rbd_add(struct bus_type *bus,
  	INIT_LIST_HEAD(&rbd_dev->node);
  	INIT_LIST_HEAD(&rbd_dev->snaps);

-	/* generate unique id: one more than highest used so far */
+	/* generate unique id: find highest unique id, add one */
  	rbd_id_get(rbd_dev);

  	/* parse add command */
-- 
1.7.5.4

Re: [PATCH 5/5] rbd: restore previous rbd id sequence behavior

[Yehuda Sadeh Weinraub]

On Tue, Feb 28, 2012 at 7:40 PM, Alex Elder <elder@dreamhost.com> wrote:
> It used to be that selecting a new unique identifier for an added
> rbd device required searching all existing ones to find the highest
> id is used.  A recent change made that unnecessary, but made it
> so that id's used were monotonically non-decreasing.  It's a bit
> more pleasant to have smaller rbd id's though, and this change
> makes ids get allocated as they were before--each new id is one more
> than the maximum currently in use.

Oh, so ignore my previous comment, though in any case we can still
exhaust the 31 bits:

loop through:

add A
add B
remove A
add C
remove B
add A
remove C
add B


etc..

>
> Signed-off-by: Alex Elder <elder@dreamhost.com>
> ---
>  drivers/block/rbd.c |   40 ++++++++++++++++++++++++++++++++++------
>  1 files changed, 34 insertions(+), 6 deletions(-)
>
> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
> index 042377b..4c5bb39 100644
> --- a/drivers/block/rbd.c
> +++ b/drivers/block/rbd.c
> @@ -2171,18 +2171,46 @@ static void rbd_id_get(struct rbd_device *rbd_dev)
>  */
>  static void rbd_id_put(struct rbd_device *rbd_dev)
>  {
> -       BUG_ON(rbd_dev->id < 1);
> +       struct list_head *tmp;
> +       int rbd_id = rbd_dev->id;
> +       int max_id;
> +
> +       BUG_ON(rbd_id < 1);
>
>        spin_lock(&rbd_dev_list_lock);
>        list_del_init(&rbd_dev->node);
> +
> +       /*
> +        * If the id being "put" is not the current maximum, there
> +        * is nothing special we need to do.
> +        */
> +       if (rbd_id != atomic_read(&rbd_id_max)) {
> +               spin_unlock(&rbd_dev_list_lock);
> +               return;
> +       }
> +
> +       /*
> +        * We need to update the current maximum id.  Search the
> +        * list to find out what it is.  We're more likely to find
> +        * the maximum at the end, so search the list backward.
> +        */
> +       max_id = 0;
> +       list_for_each_prev(tmp, &rbd_dev_list) {
> +               struct rbd_device *rbd_dev;
> +
> +               rbd_dev = list_entry(tmp, struct rbd_device, node);
> +               if (rbd_id > max_id)
> +                       max_id = rbd_id;
> +       }
>        spin_unlock(&rbd_dev_list_lock);

So we still need to either use 64 bit counter, or think of a better
scheme to allocate ids. Maybe using some sorted data structure here?
>
>        /*
> -        * New id's are always one more than the current maximum.
> -        * If the id being "put" *is* that maximum, decrement the
> -        * maximum so the next one requested just reuses this one.
> +        * The max id could have been updated by rbd_id_get(), in
> +        * which case it now accurately reflects the new maximum.
> +        * Be careful not to overwrite the maximum value in that
> +        * case.
>         */
> -       atomic_cmpxchg(&rbd_id_max, rbd_dev->id, rbd_dev->id - 1);
> +       atomic_cmpxchg(&rbd_id_max, rbd_id, max_id);
>  }
>
>  static ssize_t rbd_add(struct bus_type *bus,
> @@ -2217,7 +2245,7 @@ static ssize_t rbd_add(struct bus_type *bus,
>        INIT_LIST_HEAD(&rbd_dev->node);
>        INIT_LIST_HEAD(&rbd_dev->snaps);
>
> -       /* generate unique id: one more than highest used so far */
> +       /* generate unique id: find highest unique id, add one */
>        rbd_id_get(rbd_dev);
>
>        /* parse add command */
> --
> 1.7.5.4
>
> --
> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 5/5] rbd: restore previous rbd id sequence behavior

[Alex Elder]

On 02/29/2012 12:53 PM, Yehuda Sadeh Weinraub wrote:
> On Tue, Feb 28, 2012 at 7:40 PM, Alex Elder<elder@dreamhost.com>  wrote:
>> It used to be that selecting a new unique identifier for an added
>> rbd device required searching all existing ones to find the highest
>> id is used.  A recent change made that unnecessary, but made it
>> so that id's used were monotonically non-decreasing.  It's a bit
>> more pleasant to have smaller rbd id's though, and this change
>> makes ids get allocated as they were before--each new id is one more
>> than the maximum currently in use.
>
> Oh, so ignore my previous comment, though in any case we can still
> exhaust the 31 bits:
>
> loop through:
>
> add A
> add B
> remove A
> add C
> remove B
> add A
> remove C
> add B

OK with me.  I didn't change the previous behavior.
But I'm fine with making it 64 bits.  I will implement
that and post an update.

					-Alex

>
> etc..
>
>>
>> Signed-off-by: Alex Elder<elder@dreamhost.com>
>> ---
>>   drivers/block/rbd.c |   40 ++++++++++++++++++++++++++++++++++------
>>   1 files changed, 34 insertions(+), 6 deletions(-)
>>
>> diff --git a/drivers/block/rbd.c b/drivers/block/rbd.c
>> index 042377b..4c5bb39 100644
>> --- a/drivers/block/rbd.c
>> +++ b/drivers/block/rbd.c
>> @@ -2171,18 +2171,46 @@ static void rbd_id_get(struct rbd_device *rbd_dev)
>>   */
>>   static void rbd_id_put(struct rbd_device *rbd_dev)
>>   {
>> -       BUG_ON(rbd_dev->id<  1);
>> +       struct list_head *tmp;
>> +       int rbd_id = rbd_dev->id;
>> +       int max_id;
>> +
>> +       BUG_ON(rbd_id<  1);
>>
>>         spin_lock(&rbd_dev_list_lock);
>>         list_del_init(&rbd_dev->node);
>> +
>> +       /*
>> +        * If the id being "put" is not the current maximum, there
>> +        * is nothing special we need to do.
>> +        */
>> +       if (rbd_id != atomic_read(&rbd_id_max)) {
>> +               spin_unlock(&rbd_dev_list_lock);
>> +               return;
>> +       }
>> +
>> +       /*
>> +        * We need to update the current maximum id.  Search the
>> +        * list to find out what it is.  We're more likely to find
>> +        * the maximum at the end, so search the list backward.
>> +        */
>> +       max_id = 0;
>> +       list_for_each_prev(tmp,&rbd_dev_list) {
>> +               struct rbd_device *rbd_dev;
>> +
>> +               rbd_dev = list_entry(tmp, struct rbd_device, node);
>> +               if (rbd_id>  max_id)
>> +                       max_id = rbd_id;
>> +       }
>>         spin_unlock(&rbd_dev_list_lock);
>
> So we still need to either use 64 bit counter, or think of a better
> scheme to allocate ids. Maybe using some sorted data structure here?
>>
>>         /*
>> -        * New id's are always one more than the current maximum.
>> -        * If the id being "put" *is* that maximum, decrement the
>> -        * maximum so the next one requested just reuses this one.
>> +        * The max id could have been updated by rbd_id_get(), in
>> +        * which case it now accurately reflects the new maximum.
>> +        * Be careful not to overwrite the maximum value in that
>> +        * case.
>>          */
>> -       atomic_cmpxchg(&rbd_id_max, rbd_dev->id, rbd_dev->id - 1);
>> +       atomic_cmpxchg(&rbd_id_max, rbd_id, max_id);
>>   }
>>
>>   static ssize_t rbd_add(struct bus_type *bus,
>> @@ -2217,7 +2245,7 @@ static ssize_t rbd_add(struct bus_type *bus,
>>         INIT_LIST_HEAD(&rbd_dev->node);
>>         INIT_LIST_HEAD(&rbd_dev->snaps);
>>
>> -       /* generate unique id: one more than highest used so far */
>> +       /* generate unique id: find highest unique id, add one */
>>         rbd_id_get(rbd_dev);
>>
>>         /* parse add command */
>> --
>> 1.7.5.4
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 0/5] rbd: improve how rbd ids are selected

[Sage Weil]

This series looks good.

Reviewed-by: Sage Weil <sage@newdream.net>

On Tue, 28 Feb 2012, Alex Elder wrote:

> New rbd devices are granted a unique identifiers based on how many
> devices are already in existence.  This series rearranges how that
> is done, switching from using a spinlock to using an atomic variable
> to select the next rbd id to use.  In the process a bit of the code
> got a bit more isolated.
> 
> 					-Alex
> --
> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
>