rbd: improve how rbd ids are selected

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 <[email protected]>

---
 drivers/block/rbd.c |   35 +++++++++++++++++++++++------------

 1 files changed, 23 insertions(+), 12 deletions(-)

drivers/block/rbd.c +7 -6

index 35290b1..0c492e4 100644
@@ -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);
+}
 

drivers/block/rbd.c +8 -2

-       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:

drivers/block/rbd.c +1 -1

@@ -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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 <[email protected]>

---
 drivers/block/rbd.c |   40 ++++++++++++++++++++++++++++++++++------

 1 files changed, 34 insertions(+), 6 deletions(-)

drivers/block/rbd.c +19 -1

index 042377b..4c5bb39 100644
@@ -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.

drivers/block/rbd.c +6 -6

        /*
-        * 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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 7 lines · 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.

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..

Quoted 37 lines

Signed-off-by Alex Elder<[email protected]>

---
  drivers/block/rbd.c |   40 ++++++++++++++++++++++++++++++++++------
  1 files changed, 34 insertions(+), 6 deletions(-)

drivers/block/rbd.c +19 -1

index 042377b..4c5bb39 100644
@@ -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.

drivers/block/rbd.c static void rbd_id_get(struct rbd_device *rbd_dev) · line 2205

Quoted 10 lines

drivers/block/rbd.c +9 -0

+        */
+       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?

Quoted 31 lines

drivers/block/rbd.c +6 -6

        /*
-        * 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html