[RFC 0/1] New IDA API

[RFC 0/1] New IDA API

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

I have a tree locally with no more calls to ida_pre_get(),
ida_get_new_above(), ida_get_new() or ida_remove(), leaving us with only
calls to ida_simple_get() and ida_simple_remove().  With no 'complex'
versions, naming the functions ida_simple_* seems pointless.  I also
don't think that 'get' and 'remove' are antonyms.

The percpu_ida has the right names, in my opinion, 'alloc' and 'free'.
We're used to alloc and free from kmalloc/kfree and many other examples.
Looking through the existing users, ida_simple_get() is a little too
flexible for some users, so I included helper wrappers which allow
*most* users to just call ida_alloc(), while those that want a bounded
end can call ida_alloc_min() or ida_alloc_max().  ida_alloc_range() is
available for those who want to specify both ends of the range.

The most controversial thing is how to specify the upper bound on the
ID to allocate.  The current ida_simple_get() specifies an exclusive
bound (ie one higher than the maximum ID to return), while
ida_alloc_max() / ida_alloc_range() specify an inclusive bound (the
maximum ID to return).  Both styles of bound specification have their
adherents within the kernel, and current users seem about equally split
whether they would prefer 'end' or 'max':

drivers/block/virtio_blk.c:     err = ida_simple_get(&vd_index_ida, 0, minor_to_index(1 << MINORBITS),
drivers/dax/super.c:    minor = ida_simple_get(&dax_minor_ida, 0, MINORMASK+1, GFP_KERNEL);

Some have been confused by the current convention:

drivers/fsi/fsi-core.c: master->idx = ida_simple_get(&master_ida, 0, INT_MAX, GFP_KERNEL);
(pretty sure they'd be OK with returning INT_MAX)

One aspect I particularly like about specifying an inclusive rather than
exclusive bound is that this is not an uncommon pattern:
	id = ida_simple_get(&rtc_ida, of_id, of_id + 1, GFP_KERNEL);

and transforming that to
	id = ida_alloc_range(&rtc_ida, of_id, of_id, GFP_KERNEL);
makes more sense.  Also, there is a bug in the current implementation
of ida_simple_get where the above call would not just fail to allocate
an ID but actually BUG() if of_id happened to be INT_MAX.

I'm still musing whether the API should be expressed in terms of int,
or whether 64-bit systems might appreciate having the extra space of
'long'.  The underlying data structure supports 'unsigned long', but an
API that uses that is much harder to use and in the absence of any users,
I'm not going to add it.  Converting from int to long would hardly
change the interface, but it would lead to a situation where you could
allocate IDs on 64-bit systems that could never be allocated on 32-bit
systems.

Matthew Wilcox (1):
  ida: Add new API

 include/linux/idr.h | 59 +++++++++++++++++++++++++++++++++++++++++---
 lib/idr.c           | 70 ++++++++++++++++++++++++-----------------------------
 2 files changed, 87 insertions(+), 42 deletions(-)

-- 
2.16.2

[PATCH 1/1] ida: Add new API

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Add ida_alloc(), ida_alloc_min(), ida_alloc_max(), ida_alloc_range()
and ida_free().  The ida_alloc_max() and ida_alloc_range() functions
differ from ida_simple_get() in that they take an inclusive 'max'
parameter instead of an exclusive 'end' parameter.  Callers are about
evenly split whether they'd like inclusive or exclusive parameters and
'max' is easier to document than 'end'.

Change the IDA allocation to first attempt to allocate a bit using
existing memory, and only allocate memory afterwards.  Also change the
behaviour of 'min' > INT_MAX from being a BUG() to returning -ENOSPC.

Leave compatibility wrappers in place for ida_simple_get() and
ida_simple_remove() to avoid changing all callers.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h | 59 +++++++++++++++++++++++++++++++++++++++++---
 lib/idr.c           | 70 ++++++++++++++++++++++++-----------------------------
 2 files changed, 87 insertions(+), 42 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 7d6a6313f0ab..b80bc1ede636 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -228,15 +228,68 @@ 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(struct ida *ida, unsigned int start, unsigned int end,
-		   gfp_t gfp_mask);
-void ida_simple_remove(struct ida *ida, unsigned int id);
+int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
+void ida_free(struct ida *, unsigned int id);
+
+/**
+ * ida_alloc() - Allocate an unused ID.
+ * @ida: IDA handle.
+ * @gfp: Memory allocation flags.
+ *
+ * Allocate an ID between 0 and %INT_MAX, inclusive.
+ *
+ * Context: Any context.
+ * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free IDs.
+ */
+static inline int ida_alloc(struct ida *ida, gfp_t gfp)
+{
+	return ida_alloc_range(ida, 0, ~0, gfp);
+}
+
+/**
+ * ida_alloc_min() - Allocate an unused ID.
+ * @ida: IDA handle.
+ * @min: Lowest ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Allocate an ID between @min and %INT_MAX, inclusive.
+ *
+ * Context: Any context.
+ * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free IDs.
+ */
+static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)
+{
+	return ida_alloc_range(ida, min, ~0, gfp);
+}
+
+/**
+ * ida_alloc_max() - Allocate an unused ID.
+ * @ida: IDA handle.
+ * @max: Highest ID to allocate.
+ * @gfp: Memory allocation flags.
+ *
+ * Allocate an ID between 0 and @max, inclusive.
+ *
+ * Context: Any context.
+ * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free IDs.
+ */
+static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)
+{
+	return ida_alloc_range(ida, 0, max, gfp);
+}
 
 static inline void ida_init(struct ida *ida)
 {
 	INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT);
 }
 
+#define ida_simple_get(ida, start, end, gfp)	\
+			ida_alloc_range(ida, start, (end) - 1, gfp)
+#define ida_simple_remove(ida, id)	ida_free(ida, id)
+
 /**
  * ida_get_new - allocate new ID
  * @ida:	idr handle
diff --git a/lib/idr.c b/lib/idr.c
index 823b813f08f8..fab3763e8c2a 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -317,7 +317,8 @@ EXPORT_SYMBOL(idr_replace);
  * bit per ID, and so is more space efficient than an IDR.  To use an IDA,
  * define it using DEFINE_IDA() (or embed a &struct ida in a data structure,
  * then initialise it using ida_init()).  To allocate a new ID, call
- * ida_simple_get().  To free an ID, call ida_simple_remove().
+ * ida_alloc(), ida_alloc_max() or ida_alloc_range().  To free an ID, call
+ * ida_free().
  *
  * If you have more complex locking requirements, use a loop around
  * ida_pre_get() and ida_get_new() to allocate a new ID.  Then use
@@ -378,7 +379,7 @@ EXPORT_SYMBOL(idr_replace);
  * Allocate new ID above or equal to @start.  It should be called
  * with any required locks to ensure that concurrent calls to
  * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed.
- * Consider using ida_simple_get() if you do not have complex locking
+ * Consider using ida_alloc_range() if you do not have complex locking
  * requirements.
  *
  * If memory is required, it will return %-EAGAIN, you should unlock
@@ -546,43 +547,34 @@ 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.
+ * ida_alloc_range() - Allocate an unused ID.
+ * @ida: IDA handle.
+ * @min: Lowest ID to allocate.
+ * @max: Highest ID to allocate.
+ * @gfp: Memory allocation flags.
  *
- * Compared to ida_get_new_above() this function does its own locking, and
- * should be used unless there are special requirements.
+ * Allocate an ID between @min and @max, inclusive.  The allocated ID will
+ * not exceed %INT_MAX, even if @max is larger.
  *
- * Use ida_simple_remove() to get rid of an id.
+ * Context: Any context.
+ * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
+ * or %-ENOSPC if there are no free IDs.
  */
-int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
-		   gfp_t gfp_mask)
+int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
+			gfp_t gfp)
 {
 	int ret, id;
-	unsigned int max;
 	unsigned long flags;
 
-	BUG_ON((int)start < 0);
-	BUG_ON((int)end < 0);
+	if ((int)min < 0)
+		return -ENOSPC;
 
-	if (end == 0)
-		max = 0x80000000;
-	else {
-		BUG_ON(end < start);
-		max = end - 1;
-	}
+	if ((int)max < 0)
+		max = INT_MAX;
 
 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);
+	ret = ida_get_new_above(ida, min, &id);
 	if (!ret) {
 		if (id > max) {
 			ida_remove(ida, id);
@@ -593,24 +585,24 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 	}
 	spin_unlock_irqrestore(&simple_ida_lock, flags);
 
-	if (unlikely(ret == -EAGAIN))
+	if (unlikely(ret == -EAGAIN)) {
+		if (!ida_pre_get(ida, gfp))
+			return -ENOMEM;
 		goto again;
+	}
 
 	return ret;
 }
-EXPORT_SYMBOL(ida_simple_get);
+EXPORT_SYMBOL(ida_alloc_range);
 
 /**
- * ida_simple_remove - remove an allocated id.
- * @ida: the (initialized) ida.
- * @id: the id returned by ida_simple_get.
- *
- * Use to release an id allocated with ida_simple_get().
+ * ida_free() - Release an allocated ID.
+ * @ida: IDA handle.
+ * @id: Previously allocated ID.
  *
- * Compared to ida_remove() this function does its own locking, and should be
- * used unless there are special requirements.
+ * Context: Any context.
  */
-void ida_simple_remove(struct ida *ida, unsigned int id)
+void ida_free(struct ida *ida, unsigned int id)
 {
 	unsigned long flags;
 
@@ -619,4 +611,4 @@ void ida_simple_remove(struct ida *ida, unsigned int id)
 	ida_remove(ida, id);
 	spin_unlock_irqrestore(&simple_ida_lock, flags);
 }
-EXPORT_SYMBOL(ida_simple_remove);
+EXPORT_SYMBOL(ida_free);
-- 
2.16.2