[RFC,1/4] ida: add simple cyclic allocator support

Commit Message

Mike Christie June 23, 2017, 9:10 a.m. UTC

This patch modifies ida_get_simple to support cyclic allocation
similar to idr_alloc_cyclic. It will be used in the next
target layer patches to allocate IDs for info that is passed
to apps that were relying on the info's IDs to change after
device deletion then readdition sequences.

Signed-off-by: Mike Christie <[e-mail]>
---
 include/linux/idr.h |  3 ++
 lib/idr.c           | 79 +++++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 62 insertions(+), 20 deletions(-)

Patch

diff --git a/include/linux/idr.h b/include/linux/idr.h
index bf70b3e..cabf9fb 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -176,6 +176,7 @@  DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap);
 
 struct ida {
 	struct radix_tree_root	ida_rt;
+	unsigned int		ida_next;
 };
 
 #define IDA_INIT	{						\
@@ -188,6 +189,8 @@  int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
 void ida_remove(struct ida *ida, int id);
 void ida_destroy(struct ida *ida);
 
+int ida_simple_get_cyclic(struct ida *ida, unsigned int start, unsigned int end,
+			  gfp_t gfp_mask);
 int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 		   gfp_t gfp_mask);
 void ida_simple_remove(struct ida *ida, unsigned int id);
diff --git a/lib/idr.c b/lib/idr.c
index b13682b..bee57a6 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -407,25 +407,10 @@  void ida_destroy(struct ida *ida)
 }
 EXPORT_SYMBOL(ida_destroy);
 
-/**
- * ida_simple_get - get a new id.
- * @ida: the (initialized) ida.
- * @start: the minimum id (inclusive, < 0x8000000)
- * @end: the maximum id (exclusive, < 0x8000000 or 0)
- * @gfp_mask: memory allocation flags
- *
- * Allocates an id in the range start <= id < end, or returns -ENOSPC.
- * On memory allocation failure, returns -ENOMEM.
- *
- * Compared to ida_get_new_above() this function does its own locking, and
- * should be used unless there are special requirements.
- *
- * Use ida_simple_remove() to get rid of an id.
- */
-int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
-		   gfp_t gfp_mask)
+static int __ida_simple_get(struct ida *ida, unsigned int start,
+			    unsigned int end, bool cyclic, gfp_t gfp_mask)
 {
-	int ret, id;
+	int ret, id, curr;
 	unsigned int max;
 	unsigned long flags;
 
@@ -439,18 +424,28 @@  int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 		max = end - 1;
 	}
 
+	curr = start;
 again:
 	if (!ida_pre_get(ida, gfp_mask))
 		return -ENOMEM;
 
 	spin_lock_irqsave(&simple_ida_lock, flags);
-	ret = ida_get_new_above(ida, start, &id);
+	if (cyclic && ida->ida_next > curr)
+		curr = ida->ida_next;
+
+	ret = ida_get_new_above(ida, curr, &id);
 	if (!ret) {
 		if (id > max) {
 			ida_remove(ida, id);
-			ret = -ENOSPC;
+			if (cyclic && ida->ida_next > start) {
+				curr = ida->ida_next = start;
+				ret = -EAGAIN;
+			} else {
+				ret = -ENOSPC;
+			}
 		} else {
 			ret = id;
+			ida->ida_next = id + 1U;
 		}
 	}
 	spin_unlock_irqrestore(&simple_ida_lock, flags);
@@ -460,9 +455,53 @@  int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 
 	return ret;
 }
+
+/**
+ * ida_simple_get - get a new id.
+ * @ida: the (initialized) ida.
+ * @start: the minimum id (inclusive, < 0x8000000)
+ * @end: the maximum id (exclusive, < 0x8000000 or 0)
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range start <= id < end, or returns -ENOSPC.
+ * On memory allocation failure, returns -ENOMEM.
+ *
+ * Compared to ida_get_new_above() this function does its own locking, and
+ * should be used unless there are special requirements.
+ *
+ * Use ida_simple_remove() to get rid of an id.
+ */
+int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
+		   gfp_t gfp_mask)
+{
+	return __ida_simple_get(ida, start, end, false, gfp_mask);
+}
 EXPORT_SYMBOL(ida_simple_get);
 
 /**
+ * ida_simple_get_cyclic - get a new id.
+ * @ida: the (initialized) ida.
+ * @start: the minimum id (inclusive, < 0x8000000)
+ * @end: the maximum id (exclusive, < 0x8000000 or 0)
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an ID larger than the last ID allocated and less than @end.
+ * If @end is reached, it will attempt to allocate the smallest ID that is
+ * larger or equal to @start.
+ *
+ * If there are no available IDs returns -ENOSPC.
+ * On memory allocation failure, returns -ENOMEM.
+ *
+ * Use ida_simple_remove() to get rid of an id.
+ */
+int ida_simple_get_cyclic(struct ida *ida, unsigned int start, unsigned int end,
+			  gfp_t gfp_mask)
+{
+	return __ida_simple_get(ida, start, end, true, gfp_mask);
+}
+EXPORT_SYMBOL(ida_simple_get_cyclic);
+
+/**
  * ida_simple_remove - remove an allocated id.
  * @ida: the (initialized) ida.
  * @id: the id returned by ida_simple_get.