From: Matthew Wilcox <mawil...@microsoft.com>
idr_alloc_ul fits better with other parts of the Linux kernel where we
need to name a function based on the types it operates on.
It uses a 'nextid' pointer argument instead of separate minimum ID and
output assigned ID, (like idr_get_next), reducing the number of arguments
by one. It also takes a 'max' argument rather than an 'end' argument
(unlike idr_alloc, but the semantics of 'end' don't work for unsigned long
arguments). And its return value is an errno, so mark it as __must_check.
Includes kernel-doc for idr_alloc_ul, which idr_alloc_ext didn't have,
and I realised we were missing a test-case where idr_alloc_cyclic wraps
around INT_MAX. Chris Mi <chr...@mellanox.com> has promised to contribute
test-cases for idr_alloc_ul.
Signed-off-by: Matthew Wilcox <mawil...@microsoft.com>
---
include/linux/idr.h | 55 ++-------------------
include/linux/radix-tree.h | 17 +------
lib/idr.c | 99 +++++++++++++++++++++++++++++--------
lib/radix-tree.c | 3 +-
net/sched/cls_u32.c | 20 ++++----
tools/testing/radix-tree/idr-test.c | 17 +++++++
6 files changed, 111 insertions(+), 100 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 9b2fd6f408b2..344380fd0887 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -13,7 +13,6 @@
#define __IDR_H__
#include <linux/radix-tree.h>
-#include <linux/bug.h>
#include <linux/gfp.h>
#include <linux/percpu.h>
@@ -82,55 +81,9 @@ static inline void idr_set_cursor(struct idr *idr, unsigned
int val)
void idr_preload(gfp_t gfp_mask);
-int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index,
- unsigned long start, unsigned long end, gfp_t gfp,
- bool ext);
-
-/**
- * idr_alloc - allocate an id
- * @idr: idr handle
- * @ptr: pointer to be associated with the new id
- * @start: the minimum id (inclusive)
- * @end: the maximum id (exclusive)
- * @gfp: memory allocation flags
- *
- * Allocates an unused ID in the range [start, end). Returns -ENOSPC
- * if there are no unused IDs in that range.
- *
- * Note that @end is treated as max when <= 0. This is to always allow
- * using @start + N as @end as long as N is inside integer range.
- *
- * Simultaneous modifications to the @idr are not allowed and should be
- * prevented by the user, usually with a lock. idr_alloc() may be called
- * concurrently with read-only accesses to the @idr, such as idr_find() and
- * idr_for_each_entry().
- */
-static inline int idr_alloc(struct idr *idr, void *ptr,
- int start, int end, gfp_t gfp)
-{
- unsigned long id;
- int ret;
-
- if (WARN_ON_ONCE(start < 0))
- return -EINVAL;
-
- ret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false);
-
- if (ret)
- return ret;
-
- return id;
-}
-
-static inline int idr_alloc_ext(struct idr *idr, void *ptr,
- unsigned long *index,
- unsigned long start,
- unsigned long end,
- gfp_t gfp)
-{
- return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true);
-}
-
+int idr_alloc(struct idr *, void *, int start, int end, gfp_t);
+int __must_check idr_alloc_ul(struct idr *, void *, unsigned long *nextid,
+ unsigned long max, gfp_t);
int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);
int idr_for_each(const struct idr *,
int (*fn)(int id, void *p, void *data), void *data);
@@ -163,7 +116,7 @@ static inline int __must_check idr_alloc_u32(struct idr
*idr, void *ptr,
u32 *nextid, unsigned long max, gfp_t gfp)
{
unsigned long tmp = *nextid;
- int ret = idr_alloc_ext(idr, ptr, &tmp, tmp, max + 1, gfp);
+ int ret = idr_alloc_ul(idr, ptr, &tmp, max, gfp);
*nextid = tmp;
return ret;
}
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 23a9c89c7ad9..fc55ff31eca7 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -356,24 +356,9 @@ int radix_tree_split(struct radix_tree_root *, unsigned
long index,
int radix_tree_join(struct radix_tree_root *, unsigned long index,
unsigned new_order, void *);
-void __rcu **idr_get_free_cmn(struct radix_tree_root *root,
+void __rcu **idr_get_free(struct radix_tree_root *root,
struct radix_tree_iter *iter, gfp_t gfp,
unsigned long max);
-static inline void __rcu **idr_get_free(struct radix_tree_root *root,
- struct radix_tree_iter *iter,
- gfp_t gfp,
- int end)
-{
- return idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX);
-}
-
-static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root,
- struct radix_tree_iter *iter,
- gfp_t gfp,
- unsigned long end)
-{
- return idr_get_free_cmn(root, iter, gfp, end - 1);
-}
enum {
RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */
diff --git a/lib/idr.c b/lib/idr.c
index 577bfd4fe5c2..103afb97b4bd 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1,4 +1,5 @@
#include <linux/bitmap.h>
+#include <linux/bug.h>
#include <linux/export.h>
#include <linux/idr.h>
#include <linux/slab.h>
@@ -7,32 +8,85 @@
DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap);
static DEFINE_SPINLOCK(simple_ida_lock);
-int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index,
- unsigned long start, unsigned long end, gfp_t gfp,
- bool ext)
+/**
+ * idr_alloc_ul() - Allocate a large ID.
+ * @idr: IDR handle.
+ * @ptr: Pointer to be associated with the new ID.
+ * @nextid: Pointer to minimum and new ID.
+ * @max: The maximum ID to allocate (inclusive).
+ * @gfp: Memory allocation flags.
+ *
+ * Allocates an unused ID in the range [*nextid, max] and updates the @nextid
+ * pointer with the newly assigned ID. Note that @max differs by 1 from the
+ * @end parameter to idr_alloc().
+ *
+ * The caller should provide their own locking to ensure that two concurrent
+ * modifications to the IDR are not possible. Read-only accesses to the
+ * IDR may be done under the RCU read lock or may exclude simultaneous
+ * writers.
+ *
+ * Return: 0 on success, -ENOMEM for memory allocation errors, -ENOSPC if
+ * there are no free IDs in the range.
+ */
+int idr_alloc_ul(struct idr *idr, void *ptr, unsigned long *nextid,
+ unsigned long max, gfp_t gfp)
{
struct radix_tree_iter iter;
void __rcu **slot;
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
return -EINVAL;
+ if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
+ idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
- radix_tree_iter_init(&iter, start);
- if (ext)
- slot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end);
- else
- slot = idr_get_free(&idr->idr_rt, &iter, gfp, end);
+ radix_tree_iter_init(&iter, *nextid);
+ slot = idr_get_free(&idr->idr_rt, &iter, gfp, max);
if (IS_ERR(slot))
return PTR_ERR(slot);
radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
- if (index)
- *index = iter.index;
+ *nextid = iter.index;
return 0;
}
-EXPORT_SYMBOL_GPL(idr_alloc_cmn);
+EXPORT_SYMBOL_GPL(idr_alloc_ul);
+
+/**
+ * idr_alloc - allocate an id
+ * @idr: idr handle
+ * @ptr: pointer to be associated with the new id
+ * @start: the minimum id (inclusive)
+ * @end: the maximum id (exclusive)
+ * @gfp: memory allocation flags
+ *
+ * Allocates an unused ID in the range [start, end). Returns -ENOSPC
+ * if there are no unused IDs in that range.
+ *
+ * Note that @end is treated as max when <= 0. This is to always allow
+ * using @start + N as @end as long as N is inside integer range.
+ *
+ * Simultaneous modifications to the @idr are not allowed and should be
+ * prevented by the user, usually with a lock. idr_alloc() may be called
+ * concurrently with read-only accesses to the @idr, such as idr_find() and
+ * idr_for_each_entry().
+ */
+int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
+{
+ unsigned long id = start;
+ int ret;
+
+ if (WARN_ON_ONCE(start < 0))
+ return -EINVAL;
+
+ ret = idr_alloc_ul(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);
+
+ if (ret)
+ return ret;
+
+ return id;
+}
+EXPORT_SYMBOL_GPL(idr_alloc);
/**
* idr_alloc_cyclic - allocate new idr entry in a cyclical fashion
@@ -48,18 +102,21 @@ EXPORT_SYMBOL_GPL(idr_alloc_cmn);
*/
int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
- int id, curr = idr->idr_next;
-
- if (curr < start)
- curr = start;
+ unsigned long id = idr->idr_next;
+ int err, max = end > 0 ? end - 1 : INT_MAX;
- id = idr_alloc(idr, ptr, curr, end, gfp);
- if ((id == -ENOSPC) && (curr > start))
- id = idr_alloc(idr, ptr, start, curr, gfp);
+ if ((int)id < start)
+ id = start;
- if (id >= 0)
- idr->idr_next = id + 1U;
+ err = idr_alloc_ul(idr, ptr, &id, max, gfp);
+ if ((err == -ENOSPC) && (id > start)) {
+ id = start;
+ err = idr_alloc_ul(idr, ptr, &id, max, gfp);
+ }
+ if (err)
+ return err;
+ idr->idr_next = id + 1;
return id;
}
EXPORT_SYMBOL(idr_alloc_cyclic);
@@ -226,7 +283,7 @@ EXPORT_SYMBOL(idr_replace);
* bitmap, which is excessive.
*/
-#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS)
+#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1)
/**
* ida_get_new_above - allocate new ID above or equal to a start id
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index c8d55565fafa..0a7ae3288a24 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -24,6 +24,7 @@
#include <linux/bitmap.h>
#include <linux/bitops.h>
+#include <linux/bug.h>
#include <linux/cpu.h>
#include <linux/errno.h>
#include <linux/export.h>
@@ -2135,7 +2136,7 @@ int ida_pre_get(struct ida *ida, gfp_t gfp)
}
EXPORT_SYMBOL(ida_pre_get);
-void __rcu **idr_get_free_cmn(struct radix_tree_root *root,
+void __rcu **idr_get_free(struct radix_tree_root *root,
struct radix_tree_iter *iter, gfp_t gfp,
unsigned long max)
{
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 2fede6a55d04..5c36e9c0df9a 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -730,19 +730,17 @@ static int u32_delete(struct tcf_proto *tp, void *arg,
bool *last)
static u32 gen_new_kid(struct tc_u_hnode *ht, u32 htid)
{
- unsigned long idr_index;
- u32 start = htid | 0x800;
- u32 max = htid | 0xFFF;
- u32 min = htid;
-
- if (idr_alloc_ext(&ht->handle_idr, NULL, &idr_index,
- start, max + 1, GFP_KERNEL)) {
- if (idr_alloc_ext(&ht->handle_idr, NULL, &idr_index,
- min + 1, max + 1, GFP_KERNEL))
- return max;
+ unsigned long index = htid | 0x800;
+ unsigned long max = htid | 0xFFF;
+
+ if (idr_alloc_ul(&ht->handle_idr, NULL, &index, max, GFP_KERNEL)) {
+ index = htid + 1;
+ if (idr_alloc_ul(&ht->handle_idr, NULL, &index, max,
+ GFP_KERNEL))
+ index = max;
}
- return (u32)idr_index;
+ return index;
}
static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
diff --git a/tools/testing/radix-tree/idr-test.c
b/tools/testing/radix-tree/idr-test.c
index 892ef8855b02..36437ade429c 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -215,6 +215,23 @@ void idr_checks(void)
assert(idr_is_empty(&idr));
+ idr_set_cursor(&idr, INT_MAX - 3UL);
+ for (i = INT_MAX - 3UL; i < INT_MAX + 3UL; i++) {
+ struct item *item;
+ unsigned int id;
+ if (i <= INT_MAX)
+ item = item_create(i, 0);
+ else
+ item = item_create(i - INT_MAX - 1, 0);
+
+ id = idr_alloc_cyclic(&idr, item, 0, 0, GFP_KERNEL);
+ assert(id == item->index);
+ }
+
+ idr_for_each(&idr, item_idr_free, &idr);
+ idr_destroy(&idr);
+ assert(idr_is_empty(&idr));
+
for (i = 1; i < 10000; i++) {
struct item *item = item_create(i, 0);
assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
--
2.15.0
