[PATCH 00/17] IDR patches for 4.15

[PATCH 00/17] IDR patches for 4.15

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

The patches here are of three types:

 - Enhancing the test suite (fixing the build, adding a couple of new
   tests, fixing a bug in the test)
 - Replacing the 'extended' IDR API
 - Fixing some low-probability bugs 

As far as the 'extended' IDR API goes, this was added by Chris Mi to
permit a savvy user to use IDs up to ULONG_MAX in size (the traditional
IDR API only permits IDs to be INT_MAX).  It's harder to use, so we
wouldn't want to convert all users over to it.  But it can be made
easier to use than it currently is, which is what I've done here.  The
principal way that I've made it easier to use is by introducing
idr_alloc_u32(), which is what all but one of the existing users
actually want.

The last patch at the end I thought of just now -- what happens when
somebody adds an IDR entry with an ID > INT_MAX and then tries to
iterate over all entries in the IDR using an old interface that can't
return these large IDs?  It's not safe to return those IDs, so I've
settled for a dmesg warning and terminating the iteration.

Most of these patches have been sitting in my xarray tree in one form or
another for over a month.  I haven't seen anything from 0day to indicate
a problem here, but then there are as yet very few users and I'm not
sure 0day has covered any of them.

Matthew Wilcox (17):
  idr: Fix build
  radix tree test suite: Remove ARRAY_SIZE
  idr test suite: Fix ida_test_random()
  IDR test suite: Check handling negative end correctly
  idr: Delete idr_remove_ext function
  idr: Delete idr_replace_ext function
  idr: Delete idr_find_ext function
  idr: Add idr_alloc_u32 helper
  net sched actions: Convert to use idr_alloc_u32
  cls_basic: Convert to use idr_alloc_u32
  cls_bpf: Convert to use idr_alloc_u32
  cls_flower: Convert to idr_alloc_u32
  cls_u32: Reinstate cyclic allocation
  cls_u32: Convert to idr_alloc_u32
  idr: Rename idr_alloc_ext to idr_alloc_ul
  idr: Rename idr_for_each_entry_ext
  idr: Warn if old iterators see large IDs

 include/linux/idr.h                     | 109 ++++++++++--------------
 include/linux/radix-tree.h              |  17 +---
 lib/idr.c                               | 143 +++++++++++++++++++++++---------
 lib/radix-tree.c                        |   3 +-
 net/sched/act_api.c                     |  72 +++++++---------
 net/sched/cls_basic.c                   |  33 ++++----
 net/sched/cls_bpf.c                     |  32 ++++---
 net/sched/cls_flower.c                  |  34 ++++----
 net/sched/cls_u32.c                     |  51 +++++-------
 tools/testing/radix-tree/idr-test.c     |  22 ++++-
 tools/testing/radix-tree/linux/kernel.h |   2 -
 11 files changed, 267 insertions(+), 251 deletions(-)

-- 
2.15.0

[PATCH 01/17] idr: Fix build

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

The IDR calls WARN_ON without including <linux/bug.h>

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 7c3a365f7e12..dd048cf456b7 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -13,6 +13,7 @@
 #define __IDR_H__
 
 #include <linux/radix-tree.h>
+#include <linux/bug.h>
 #include <linux/gfp.h>
 #include <linux/percpu.h>
 
-- 
2.15.0

[PATCH 02/17] radix tree test suite: Remove ARRAY_SIZE

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

This is now defined in tools/include/linux/kernel.h, so our
definition generates a warning.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/linux/kernel.h | 2 --
 1 file changed, 2 deletions(-)

diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index c3bc3f364f68..426f32f28547 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -17,6 +17,4 @@
 #define pr_debug printk
 #define pr_cont printk
 
-#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
-
 #endif /* _KERNEL_H */
-- 
2.15.0

[PATCH 03/17] idr test suite: Fix ida_test_random()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

The test was checking the wrong errno; ida_get_new_above() returns
EAGAIN, not ENOMEM on memory allocation failure.  Double the number of
threads to increase the chance that we actually exercise this path
during the test suite (it was a bit sporadic before).

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/idr-test.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 30cd0b296f1a..193450b29bf0 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -380,7 +380,7 @@ void ida_check_random(void)
 			do {
 				ida_pre_get(&ida, GFP_KERNEL);
 				err = ida_get_new_above(&ida, bit, &id);
-			} while (err == -ENOMEM);
+			} while (err == -EAGAIN);
 			assert(!err);
 			assert(id == bit);
 		}
@@ -489,7 +489,7 @@ static void *ida_random_fn(void *arg)
 
 void ida_thread_tests(void)
 {
-	pthread_t threads[10];
+	pthread_t threads[20];
 	int i;
 
 	for (i = 0; i < ARRAY_SIZE(threads); i++)
-- 
2.15.0

[PATCH 04/17] IDR test suite: Check handling negative end correctly

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

One of the charming quirks of the idr_alloc() interface is that you
can pass a negative end and it will be interpreted as "maximum".  Ensure
we don't break that.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/idr-test.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 193450b29bf0..892ef8855b02 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -207,6 +207,7 @@ void idr_checks(void)
 		assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
 	}
 	assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
+	assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i + 10, GFP_KERNEL) == -ENOSPC);
 
 	idr_for_each(&idr, item_idr_free, &idr);
 	idr_destroy(&idr);
-- 
2.15.0

[PATCH 05/17] idr: Delete idr_remove_ext function

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Simply changing idr_remove's 'id' argument to 'unsigned long' suffices
for all callers.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h    | 7 +------
 net/sched/act_api.c    | 2 +-
 net/sched/cls_basic.c  | 6 +++---
 net/sched/cls_bpf.c    | 6 +++---
 net/sched/cls_flower.c | 4 ++--
 net/sched/cls_u32.c    | 8 ++++----
 6 files changed, 14 insertions(+), 19 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index dd048cf456b7..9a4042489ec6 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -140,16 +140,11 @@ void *idr_replace(struct idr *, void *, int id);
 void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id);
 void idr_destroy(struct idr *);
 
-static inline void *idr_remove_ext(struct idr *idr, unsigned long id)
+static inline void *idr_remove(struct idr *idr, unsigned long id)
 {
 	return radix_tree_delete_item(&idr->idr_rt, id, NULL);
 }
 
-static inline void *idr_remove(struct idr *idr, int id)
-{
-	return idr_remove_ext(idr, id);
-}
-
 static inline void idr_init(struct idr *idr)
 {
 	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 4d33a50a8a6d..bab81574a420 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -78,7 +78,7 @@ static void free_tcf(struct tc_action *p)
 static void tcf_idr_remove(struct tcf_idrinfo *idrinfo, struct tc_action *p)
 {
 	spin_lock_bh(&idrinfo->lock);
-	idr_remove_ext(&idrinfo->action_idr, p->tcfa_index);
+	idr_remove(&idrinfo->action_idr, p->tcfa_index);
 	spin_unlock_bh(&idrinfo->lock);
 	gen_kill_estimator(&p->tcfa_rate_est);
 	free_tcf(p);
diff --git a/net/sched/cls_basic.c b/net/sched/cls_basic.c
index 5f169ded347e..d2193304bad0 100644
--- a/net/sched/cls_basic.c
+++ b/net/sched/cls_basic.c
@@ -120,7 +120,7 @@ static void basic_destroy(struct tcf_proto *tp)
 	list_for_each_entry_safe(f, n, &head->flist, link) {
 		list_del_rcu(&f->link);
 		tcf_unbind_filter(tp, &f->res);
-		idr_remove_ext(&head->handle_idr, f->handle);
+		idr_remove(&head->handle_idr, f->handle);
 		if (tcf_exts_get_net(&f->exts))
 			call_rcu(&f->rcu, basic_delete_filter);
 		else
@@ -137,7 +137,7 @@ static int basic_delete(struct tcf_proto *tp, void *arg, bool *last)
 
 	list_del_rcu(&f->link);
 	tcf_unbind_filter(tp, &f->res);
-	idr_remove_ext(&head->handle_idr, f->handle);
+	idr_remove(&head->handle_idr, f->handle);
 	tcf_exts_get_net(&f->exts);
 	call_rcu(&f->rcu, basic_delete_filter);
 	*last = list_empty(&head->flist);
@@ -224,7 +224,7 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 	err = basic_set_parms(net, tp, fnew, base, tb, tca[TCA_RATE], ovr);
 	if (err < 0) {
 		if (!fold)
-			idr_remove_ext(&head->handle_idr, fnew->handle);
+			idr_remove(&head->handle_idr, fnew->handle);
 		goto errout;
 	}
 
diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index a9f3e317055c..810c824eea81 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -294,7 +294,7 @@ static void __cls_bpf_delete(struct tcf_proto *tp, struct cls_bpf_prog *prog)
 {
 	struct cls_bpf_head *head = rtnl_dereference(tp->root);
 
-	idr_remove_ext(&head->handle_idr, prog->handle);
+	idr_remove(&head->handle_idr, prog->handle);
 	cls_bpf_stop_offload(tp, prog);
 	list_del_rcu(&prog->link);
 	tcf_unbind_filter(tp, &prog->res);
@@ -516,7 +516,7 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 	ret = cls_bpf_offload(tp, prog, oldprog);
 	if (ret) {
 		if (!oldprog)
-			idr_remove_ext(&head->handle_idr, prog->handle);
+			idr_remove(&head->handle_idr, prog->handle);
 		__cls_bpf_delete_prog(prog);
 		return ret;
 	}
@@ -539,7 +539,7 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 
 errout_idr:
 	if (!oldprog)
-		idr_remove_ext(&head->handle_idr, prog->handle);
+		idr_remove(&head->handle_idr, prog->handle);
 errout:
 	tcf_exts_destroy(&prog->exts);
 	kfree(prog);
diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 543a3e875d05..3e89b0be1706 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -283,7 +283,7 @@ static void __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f)
 {
 	struct cls_fl_head *head = rtnl_dereference(tp->root);
 
-	idr_remove_ext(&head->handle_idr, f->handle);
+	idr_remove(&head->handle_idr, f->handle);
 	list_del_rcu(&f->list);
 	if (!tc_skip_hw(f->flags))
 		fl_hw_destroy_filter(tp, f);
@@ -972,7 +972,7 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 
 errout_idr:
 	if (fnew->handle)
-		idr_remove_ext(&head->handle_idr, fnew->handle);
+		idr_remove(&head->handle_idr, fnew->handle);
 errout:
 	tcf_exts_destroy(&fnew->exts);
 	kfree(fnew);
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index ac152b4f4247..6fe4e3549ad3 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -591,7 +591,7 @@ static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
 					 rtnl_dereference(n->next));
 			tcf_unbind_filter(tp, &n->res);
 			u32_remove_hw_knode(tp, n->handle);
-			idr_remove_ext(&ht->handle_idr, n->handle);
+			idr_remove(&ht->handle_idr, n->handle);
 			if (tcf_exts_get_net(&n->exts))
 				call_rcu(&n->rcu, u32_delete_key_freepf_rcu);
 			else
@@ -617,7 +617,7 @@ static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
 		if (phn == ht) {
 			u32_clear_hw_hnode(tp, ht);
 			idr_destroy(&ht->handle_idr);
-			idr_remove_ext(&tp_c->handle_idr, ht->handle);
+			idr_remove(&tp_c->handle_idr, ht->handle);
 			RCU_INIT_POINTER(*hn, ht->next);
 			kfree_rcu(ht, rcu);
 			return 0;
@@ -992,7 +992,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 
 		err = u32_replace_hw_hnode(tp, ht, flags);
 		if (err) {
-			idr_remove_ext(&tp_c->handle_idr, handle);
+			idr_remove(&tp_c->handle_idr, handle);
 			kfree(ht);
 			return err;
 		}
@@ -1120,7 +1120,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 #endif
 	kfree(n);
 erridr:
-	idr_remove_ext(&ht->handle_idr, handle);
+	idr_remove(&ht->handle_idr, handle);
 	return err;
 }
 
-- 
2.15.0

[PATCH 06/17] idr: Delete idr_replace_ext function

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Changing idr_replace's 'id' argument to 'unsigned long' works for all
callers.  Callers which passed a negative ID now get -ENOENT instead of
-EINVAL.  No callers relied on this error value.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h    |  3 +--
 lib/idr.c              | 15 +++------------
 net/sched/act_api.c    |  2 +-
 net/sched/cls_basic.c  |  2 +-
 net/sched/cls_bpf.c    |  2 +-
 net/sched/cls_flower.c |  2 +-
 net/sched/cls_u32.c    |  2 +-
 7 files changed, 9 insertions(+), 19 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 9a4042489ec6..90dbe7a3735c 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -136,8 +136,7 @@ int idr_for_each(const struct idr *,
 		 int (*fn)(int id, void *p, void *data), void *data);
 void *idr_get_next(struct idr *, int *nextid);
 void *idr_get_next_ext(struct idr *idr, unsigned long *nextid);
-void *idr_replace(struct idr *, void *, int id);
-void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id);
+void *idr_replace(struct idr *, void *, unsigned long id);
 void idr_destroy(struct idr *);
 
 static inline void *idr_remove(struct idr *idr, unsigned long id)
diff --git a/lib/idr.c b/lib/idr.c
index 2593ce513a18..577bfd4fe5c2 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -147,18 +147,9 @@ EXPORT_SYMBOL(idr_get_next_ext);
  * the one being replaced!).
  *
  * Returns: the old value on success.  %-ENOENT indicates that @id was not
- * found.  %-EINVAL indicates that @id or @ptr were not valid.
+ * found.  %-EINVAL indicates that @ptr was not valid.
  */
-void *idr_replace(struct idr *idr, void *ptr, int id)
-{
-	if (id < 0)
-		return ERR_PTR(-EINVAL);
-
-	return idr_replace_ext(idr, ptr, id);
-}
-EXPORT_SYMBOL(idr_replace);
-
-void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id)
+void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 {
 	struct radix_tree_node *node;
 	void __rcu **slot = NULL;
@@ -175,7 +166,7 @@ void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id)
 
 	return entry;
 }
-EXPORT_SYMBOL(idr_replace_ext);
+EXPORT_SYMBOL(idr_replace);
 
 /**
  * DOC: IDA description
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index bab81574a420..7e901e855d68 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -348,7 +348,7 @@ void tcf_idr_insert(struct tc_action_net *tn, struct tc_action *a)
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 
 	spin_lock_bh(&idrinfo->lock);
-	idr_replace_ext(&idrinfo->action_idr, a, a->tcfa_index);
+	idr_replace(&idrinfo->action_idr, a, a->tcfa_index);
 	spin_unlock_bh(&idrinfo->lock);
 }
 EXPORT_SYMBOL(tcf_idr_insert);
diff --git a/net/sched/cls_basic.c b/net/sched/cls_basic.c
index d2193304bad0..147700afcf31 100644
--- a/net/sched/cls_basic.c
+++ b/net/sched/cls_basic.c
@@ -231,7 +231,7 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 	*arg = fnew;
 
 	if (fold) {
-		idr_replace_ext(&head->handle_idr, fnew, fnew->handle);
+		idr_replace(&head->handle_idr, fnew, fnew->handle);
 		list_replace_rcu(&fold->link, &fnew->link);
 		tcf_unbind_filter(tp, &fold->res);
 		tcf_exts_get_net(&fold->exts);
diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index 810c824eea81..b7c5c3150086 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -525,7 +525,7 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 		prog->gen_flags |= TCA_CLS_FLAGS_NOT_IN_HW;
 
 	if (oldprog) {
-		idr_replace_ext(&head->handle_idr, prog, handle);
+		idr_replace(&head->handle_idr, prog, handle);
 		list_replace_rcu(&oldprog->link, &prog->link);
 		tcf_unbind_filter(tp, &oldprog->res);
 		tcf_exts_get_net(&oldprog->exts);
diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index 3e89b0be1706..ca71823bee03 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -958,7 +958,7 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 
 	if (fold) {
 		fnew->handle = handle;
-		idr_replace_ext(&head->handle_idr, fnew, fnew->handle);
+		idr_replace(&head->handle_idr, fnew, fnew->handle);
 		list_replace_rcu(&fold->list, &fnew->list);
 		tcf_unbind_filter(tp, &fold->res);
 		tcf_exts_get_net(&fold->exts);
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 6fe4e3549ad3..9d48674a70e0 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -833,7 +833,7 @@ static void u32_replace_knode(struct tcf_proto *tp, struct tc_u_common *tp_c,
 		if (pins->handle == n->handle)
 			break;
 
-	idr_replace_ext(&ht->handle_idr, n, n->handle);
+	idr_replace(&ht->handle_idr, n, n->handle);
 	RCU_INIT_POINTER(n->next, pins->next);
 	rcu_assign_pointer(*ins, n);
 }
-- 
2.15.0

[PATCH 07/17] idr: Delete idr_find_ext function

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Simply changing idr_remove's 'id' argument to 'unsigned long' works
for all callers.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h    | 7 +------
 net/sched/act_api.c    | 2 +-
 net/sched/cls_flower.c | 2 +-
 3 files changed, 3 insertions(+), 8 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 90dbe7a3735c..12514ec0cd28 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -179,16 +179,11 @@ static inline void idr_preload_end(void)
  * This function can be called under rcu_read_lock(), given that the leaf
  * pointers lifetimes are correctly managed.
  */
-static inline void *idr_find_ext(const struct idr *idr, unsigned long id)
+static inline void *idr_find(const struct idr *idr, unsigned long id)
 {
 	return radix_tree_lookup(&idr->idr_rt, id);
 }
 
-static inline void *idr_find(const struct idr *idr, int id)
-{
-	return idr_find_ext(idr, id);
-}
-
 /**
  * idr_for_each_entry - iterate over an idr's elements of a given type
  * @idr:     idr handle
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 7e901e855d68..efb90b8a3bf0 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -222,7 +222,7 @@ static struct tc_action *tcf_idr_lookup(u32 index, struct tcf_idrinfo *idrinfo)
 	struct tc_action *p = NULL;
 
 	spin_lock_bh(&idrinfo->lock);
-	p = idr_find_ext(&idrinfo->action_idr, index);
+	p = idr_find(&idrinfo->action_idr, index);
 	spin_unlock_bh(&idrinfo->lock);
 
 	return p;
diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index ca71823bee03..ec0dc92f6104 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -329,7 +329,7 @@ static void *fl_get(struct tcf_proto *tp, u32 handle)
 {
 	struct cls_fl_head *head = rtnl_dereference(tp->root);
 
-	return idr_find_ext(&head->handle_idr, handle);
+	return idr_find(&head->handle_idr, handle);
 }
 
 static const struct nla_policy fl_policy[TCA_FLOWER_MAX + 1] = {
-- 
2.15.0

[PATCH 08/17] idr: Add idr_alloc_u32 helper

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

All current users of idr_alloc_ext() actually want to allocate a u32 and
it's a little painful for them to use idr_alloc_ext().  This convenience
function makes it simple.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 12514ec0cd28..9b2fd6f408b2 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -139,6 +139,35 @@ void *idr_get_next_ext(struct idr *idr, unsigned long *nextid);
 void *idr_replace(struct idr *, void *, unsigned long id);
 void idr_destroy(struct idr *);
 
+/**
+ * idr_alloc_u32() - Allocate an ID.
+ * @idr: IDR handle.
+ * @ptr: Pointer to be associated with the new ID.
+ * @nextid: The 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.  Returns -ENOSPC and does not modify
+ * @nextid if there are no unused IDs in the range.
+ *
+ * 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.
+ */
+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);
+	*nextid = tmp;
+	return ret;
+}
+
 static inline void *idr_remove(struct idr *idr, unsigned long id)
 {
 	return radix_tree_delete_item(&idr->idr_rt, id, NULL);
-- 
2.15.0

[PATCH 09/17] net sched actions: Convert to use idr_alloc_u32

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Use the new helper.  Also untangle the error path, and in so doing
noticed that estimator generator failure would lead to us leaking an
ID.  Fix that bug.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/act_api.c | 60 ++++++++++++++++++++++-------------------------------
 1 file changed, 25 insertions(+), 35 deletions(-)

diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index efb90b8a3bf0..156302c110af 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -274,7 +274,6 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index, struct nlattr *est,
 	struct tcf_idrinfo *idrinfo = tn->idrinfo;
 	struct idr *idr = &idrinfo->action_idr;
 	int err = -ENOMEM;
-	unsigned long idr_index;
 
 	if (unlikely(!p))
 		return -ENOMEM;
@@ -284,45 +283,28 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index, struct nlattr *est,
 
 	if (cpustats) {
 		p->cpu_bstats = netdev_alloc_pcpu_stats(struct gnet_stats_basic_cpu);
-		if (!p->cpu_bstats) {
-err1:
-			kfree(p);
-			return err;
-		}
-		p->cpu_qstats = alloc_percpu(struct gnet_stats_queue);
-		if (!p->cpu_qstats) {
-err2:
-			free_percpu(p->cpu_bstats);
+		if (!p->cpu_bstats)
 			goto err1;
-		}
+		p->cpu_qstats = alloc_percpu(struct gnet_stats_queue);
+		if (!p->cpu_qstats)
+			goto err2;
 	}
 	spin_lock_init(&p->tcfa_lock);
+	idr_preload(GFP_KERNEL);
+	spin_lock_bh(&idrinfo->lock);
 	/* user doesn't specify an index */
 	if (!index) {
-		idr_preload(GFP_KERNEL);
-		spin_lock_bh(&idrinfo->lock);
-		err = idr_alloc_ext(idr, NULL, &idr_index, 1, 0,
-				    GFP_ATOMIC);
-		spin_unlock_bh(&idrinfo->lock);
-		idr_preload_end();
-		if (err) {
-err3:
-			free_percpu(p->cpu_qstats);
-			goto err2;
-		}
-		p->tcfa_index = idr_index;
+		index = 1;
+		err = idr_alloc_u32(idr, NULL, &index, UINT_MAX, GFP_ATOMIC);
 	} else {
-		idr_preload(GFP_KERNEL);
-		spin_lock_bh(&idrinfo->lock);
-		err = idr_alloc_ext(idr, NULL, NULL, index, index + 1,
-				    GFP_ATOMIC);
-		spin_unlock_bh(&idrinfo->lock);
-		idr_preload_end();
-		if (err)
-			goto err3;
-		p->tcfa_index = index;
+		err = idr_alloc_u32(idr, NULL, &index, index, GFP_ATOMIC);
 	}
+	spin_unlock_bh(&idrinfo->lock);
+	idr_preload_end();
+	if (err)
+		goto err3;
 
+	p->tcfa_index = index;
 	p->tcfa_tm.install = jiffies;
 	p->tcfa_tm.lastuse = jiffies;
 	p->tcfa_tm.firstuse = 0;
@@ -330,9 +312,8 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index, struct nlattr *est,
 		err = gen_new_estimator(&p->tcfa_bstats, p->cpu_bstats,
 					&p->tcfa_rate_est,
 					&p->tcfa_lock, NULL, est);
-		if (err) {
-			goto err3;
-		}
+		if (err)
+			goto err4;
 	}
 
 	p->idrinfo = idrinfo;
@@ -340,6 +321,15 @@ int tcf_idr_create(struct tc_action_net *tn, u32 index, struct nlattr *est,
 	INIT_LIST_HEAD(&p->list);
 	*a = p;
 	return 0;
+err4:
+	idr_remove(idr, index);
+err3:
+	free_percpu(p->cpu_qstats);
+err2:
+	free_percpu(p->cpu_bstats);
+err1:
+	kfree(p);
+	return err;
 }
 EXPORT_SYMBOL(tcf_idr_create);
 
-- 
2.15.0

[PATCH 10/17] cls_basic: Convert to use idr_alloc_u32

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Use the new helper which saves a temporary variable and a few lines of
code.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/cls_basic.c | 25 ++++++++++---------------
 1 file changed, 10 insertions(+), 15 deletions(-)

diff --git a/net/sched/cls_basic.c b/net/sched/cls_basic.c
index 147700afcf31..529597c8c28c 100644
--- a/net/sched/cls_basic.c
+++ b/net/sched/cls_basic.c
@@ -182,7 +182,6 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 	struct nlattr *tb[TCA_BASIC_MAX + 1];
 	struct basic_filter *fold = (struct basic_filter *) *arg;
 	struct basic_filter *fnew;
-	unsigned long idr_index;
 
 	if (tca[TCA_OPTIONS] == NULL)
 		return -EINVAL;
@@ -205,21 +204,17 @@ static int basic_change(struct net *net, struct sk_buff *in_skb,
 	if (err < 0)
 		goto errout;
 
-	if (handle) {
-		fnew->handle = handle;
-		if (!fold) {
-			err = idr_alloc_ext(&head->handle_idr, fnew, &idr_index,
-					    handle, handle + 1, GFP_KERNEL);
-			if (err)
-				goto errout;
-		}
-	} else {
-		err = idr_alloc_ext(&head->handle_idr, fnew, &idr_index,
-				    1, 0x7FFFFFFF, GFP_KERNEL);
-		if (err)
-			goto errout;
-		fnew->handle = idr_index;
+	if (!handle) {
+		handle = 1;
+		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
+					INT_MAX, GFP_KERNEL);
+	} else if (!fold) {
+		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
+					handle, GFP_KERNEL);
 	}
+	if (err)
+		goto errout;
+	fnew->handle = handle;
 
 	err = basic_set_parms(net, tp, fnew, base, tb, tca[TCA_RATE], ovr);
 	if (err < 0) {
-- 
2.15.0

[PATCH 11/17] cls_bpf: Convert to use idr_alloc_u32

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Use the new helper.  This has a modest reduction in both lines of code
and compiled code size.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/cls_bpf.c | 24 ++++++++++--------------
 1 file changed, 10 insertions(+), 14 deletions(-)

diff --git a/net/sched/cls_bpf.c b/net/sched/cls_bpf.c
index b7c5c3150086..82050b240842 100644
--- a/net/sched/cls_bpf.c
+++ b/net/sched/cls_bpf.c
@@ -467,7 +467,6 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 	struct cls_bpf_prog *oldprog = *arg;
 	struct nlattr *tb[TCA_BPF_MAX + 1];
 	struct cls_bpf_prog *prog;
-	unsigned long idr_index;
 	int ret;
 
 	if (tca[TCA_OPTIONS] == NULL)
@@ -494,21 +493,18 @@ static int cls_bpf_change(struct net *net, struct sk_buff *in_skb,
 	}
 
 	if (handle == 0) {
-		ret = idr_alloc_ext(&head->handle_idr, prog, &idr_index,
-				    1, 0x7FFFFFFF, GFP_KERNEL);
-		if (ret)
-			goto errout;
-		prog->handle = idr_index;
-	} else {
-		if (!oldprog) {
-			ret = idr_alloc_ext(&head->handle_idr, prog, &idr_index,
-					    handle, handle + 1, GFP_KERNEL);
-			if (ret)
-				goto errout;
-		}
-		prog->handle = handle;
+		handle = 1;
+		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
+						INT_MAX, GFP_KERNEL);
+	} else if (!oldprog) {
+		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
+						handle, GFP_KERNEL);
 	}
 
+	if (ret)
+		goto errout;
+	prog->handle = handle;
+
 	ret = cls_bpf_set_parms(net, tp, prog, base, tb, tca[TCA_RATE], ovr);
 	if (ret < 0)
 		goto errout_idr;
-- 
2.15.0

[PATCH 12/17] cls_flower: Convert to idr_alloc_u32

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Use the new helper which saves a temporary variable and a few lines
of code.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/cls_flower.c | 26 ++++++++++----------------
 1 file changed, 10 insertions(+), 16 deletions(-)

diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index ec0dc92f6104..77a7a3c883b7 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -858,7 +858,6 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 	struct cls_fl_filter *fnew;
 	struct nlattr **tb;
 	struct fl_flow_mask mask = {};
-	unsigned long idr_index;
 	int err;
 
 	if (!tca[TCA_OPTIONS])
@@ -889,21 +888,17 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 		goto errout;
 
 	if (!handle) {
-		err = idr_alloc_ext(&head->handle_idr, fnew, &idr_index,
-				    1, 0x80000000, GFP_KERNEL);
-		if (err)
-			goto errout;
-		fnew->handle = idr_index;
-	}
-
-	/* user specifies a handle and it doesn't exist */
-	if (handle && !fold) {
-		err = idr_alloc_ext(&head->handle_idr, fnew, &idr_index,
-				    handle, handle + 1, GFP_KERNEL);
-		if (err)
-			goto errout;
-		fnew->handle = idr_index;
+		handle = 1;
+		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
+					INT_MAX, GFP_KERNEL);
+	} else if (!fold) {
+		/* user specifies a handle and it doesn't exist */
+		err = idr_alloc_u32(&head->handle_idr, fnew, &handle,
+					handle, GFP_KERNEL);
 	}
+	if (err)
+		goto errout;
+	fnew->handle = handle;
 
 	if (tb[TCA_FLOWER_FLAGS]) {
 		fnew->flags = nla_get_u32(tb[TCA_FLOWER_FLAGS]);
@@ -957,7 +952,6 @@ static int fl_change(struct net *net, struct sk_buff *in_skb,
 	*arg = fnew;
 
 	if (fold) {
-		fnew->handle = handle;
 		idr_replace(&head->handle_idr, fnew, fnew->handle);
 		list_replace_rcu(&fold->list, &fnew->list);
 		tcf_unbind_filter(tp, &fold->res);
-- 
2.15.0

[PATCH 13/17] cls_u32: Reinstate cyclic allocation

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Commit e7614370d6f0 ("net_sched: use idr to allocate u32 filter handles)
converted htid allocation to use the IDR.  The ID allocated by this
scheme changes; it used to be cyclic, but now always allocates the
lowest available.  The IDR supports cyclic allocation, so just use
the right function.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/cls_u32.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 9d48674a70e0..e65b47483dc0 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -316,19 +316,13 @@ static void *u32_get(struct tcf_proto *tp, u32 handle)
 	return u32_lookup_key(ht, handle);
 }
 
+/* Protected by rtnl lock */
 static u32 gen_new_htid(struct tc_u_common *tp_c, struct tc_u_hnode *ptr)
 {
-	unsigned long idr_index;
-	int err;
-
-	/* This is only used inside rtnl lock it is safe to increment
-	 * without read _copy_ update semantics
-	 */
-	err = idr_alloc_ext(&tp_c->handle_idr, ptr, &idr_index,
-			    1, 0x7FF, GFP_KERNEL);
-	if (err)
+	int id = idr_alloc_cyclic(&tp_c->handle_idr, ptr, 1, 0x7FF, GFP_KERNEL);
+	if (id < 0)
 		return 0;
-	return (u32)(idr_index | 0x800) << 20;
+	return (id | 0x800U) << 20;
 }
 
 static struct hlist_head *tc_u_common_hash;
-- 
2.15.0

[PATCH 14/17] cls_u32: Convert to idr_alloc_u32

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

No real benefit to this classifier, but since we're allocating a u32
anyway, we should use this function.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 net/sched/cls_u32.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index e65b47483dc0..2fede6a55d04 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -970,8 +970,8 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 				return -ENOMEM;
 			}
 		} else {
-			err = idr_alloc_ext(&tp_c->handle_idr, ht, NULL,
-					    handle, handle + 1, GFP_KERNEL);
+			err = idr_alloc_u32(&tp_c->handle_idr, ht, &handle,
+						handle, GFP_KERNEL);
 			if (err) {
 				kfree(ht);
 				return err;
@@ -1020,8 +1020,7 @@ static int u32_change(struct net *net, struct sk_buff *in_skb,
 		if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
 			return -EINVAL;
 		handle = htid | TC_U32_NODE(handle);
-		err = idr_alloc_ext(&ht->handle_idr, NULL, NULL,
-				    handle, handle + 1,
+		err = idr_alloc_u32(&ht->handle_idr, NULL, &handle, handle,
 				    GFP_KERNEL);
 		if (err)
 			return err;
-- 
2.15.0

[PATCH 15/17] idr: Rename idr_alloc_ext to idr_alloc_ul

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@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 <chrism@mellanox.com> has promised to contribute
test-cases for idr_alloc_ul.

Signed-off-by: Matthew Wilcox <mawilcox@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

[PATCH 16/17] idr: Rename idr_for_each_entry_ext

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Match idr_alloc_ul with idr_get_next_ul and idr_for_each_entry_ul.
Also add kernel-doc.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/idr.h | 17 ++++++++++++++---
 lib/idr.c           | 20 +++++++++++++++-----
 net/sched/act_api.c |  6 +++---
 3 files changed, 32 insertions(+), 11 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 344380fd0887..91d27a9bcdf4 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -88,7 +88,7 @@ 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);
 void *idr_get_next(struct idr *, int *nextid);
-void *idr_get_next_ext(struct idr *idr, unsigned long *nextid);
+void *idr_get_next_ul(struct idr *, unsigned long *nextid);
 void *idr_replace(struct idr *, void *, unsigned long id);
 void idr_destroy(struct idr *);
 
@@ -178,8 +178,19 @@ static inline void *idr_find(const struct idr *idr, unsigned long id)
  */
 #define idr_for_each_entry(idr, entry, id)			\
 	for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id)
-#define idr_for_each_entry_ext(idr, entry, id)			\
-	for (id = 0; ((entry) = idr_get_next_ext(idr, &(id))) != NULL; ++id)
+
+/**
+ * idr_for_each_entry_ul() - iterate over an IDR's elements of a given type.
+ * @idr: IDR handle.
+ * @entry: The type * to use as cursor.
+ * @id: Entry ID.
+ *
+ * @entry and @id do not need to be initialized before the loop, and
+ * after normal terminatinon @entry is left with the value NULL.  This
+ * is convenient for a "not found" value.
+ */
+#define idr_for_each_entry_ul(idr, entry, id)			\
+	for (id = 0; ((entry) = idr_get_next_ul(idr, &(id))) != NULL; ++id)
 
 /**
  * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type
diff --git a/lib/idr.c b/lib/idr.c
index 103afb97b4bd..772a24513d1e 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -155,9 +155,9 @@ int idr_for_each(const struct idr *idr,
 EXPORT_SYMBOL(idr_for_each);
 
 /**
- * idr_get_next - Find next populated entry
- * @idr: idr handle
- * @nextid: Pointer to lowest possible ID to return
+ * idr_get_next() - Find next populated entry.
+ * @idr: IDR handle.
+ * @nextid: Pointer to lowest possible ID to return.
  *
  * Returns the next populated entry in the tree with an ID greater than
  * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
@@ -178,7 +178,17 @@ void *idr_get_next(struct idr *idr, int *nextid)
 }
 EXPORT_SYMBOL(idr_get_next);
 
-void *idr_get_next_ext(struct idr *idr, unsigned long *nextid)
+/**
+ * idr_get_next_ul() - Find next populated entry.
+ * @idr: IDR handle.
+ * @nextid: Pointer to lowest possible ID to return.
+ *
+ * Returns the next populated entry in the tree with an ID greater than
+ * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
+ * to the ID of the found value.  To use in a loop, the value pointed to by
+ * nextid must be incremented by the user.
+ */
+void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;
@@ -190,7 +200,7 @@ void *idr_get_next_ext(struct idr *idr, unsigned long *nextid)
 	*nextid = iter.index;
 	return rcu_dereference_raw(*slot);
 }
-EXPORT_SYMBOL(idr_get_next_ext);
+EXPORT_SYMBOL(idr_get_next_ul);
 
 /**
  * idr_replace - replace pointer for given id
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 156302c110af..4133d91b7029 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -124,7 +124,7 @@ static int tcf_dump_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 
 	s_i = cb->args[0];
 
-	idr_for_each_entry_ext(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, id) {
 		index++;
 		if (index < s_i)
 			continue;
@@ -181,7 +181,7 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 	if (nla_put_string(skb, TCA_KIND, ops->kind))
 		goto nla_put_failure;
 
-	idr_for_each_entry_ext(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, id) {
 		ret = __tcf_idr_release(p, false, true);
 		if (ret == ACT_P_DELETED) {
 			module_put(ops->owner);
@@ -351,7 +351,7 @@ void tcf_idrinfo_destroy(const struct tc_action_ops *ops,
 	int ret;
 	unsigned long id = 1;
 
-	idr_for_each_entry_ext(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, id) {
 		ret = __tcf_idr_release(p, false, true);
 		if (ret == ACT_P_DELETED)
 			module_put(ops->owner);
-- 
2.15.0

[PATCH 17/17] idr: Warn if old iterators see large IDs

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Now that the IDR can be used to store large IDs, it is possible somebody
might only partially convert their old code and use the iterators which
can only handle IDs up to INT_MAX.  It's probably unwise to show them a
truncated ID, so settle for spewing warnings to dmesg, and terminating
the iteration.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 lib/idr.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/lib/idr.c b/lib/idr.c
index 772a24513d1e..f56133a600bb 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -145,7 +145,11 @@ int idr_for_each(const struct idr *idr,
 	void __rcu **slot;
 
 	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
-		int ret = fn(iter.index, rcu_dereference_raw(*slot), data);
+		int ret;
+
+		if (WARN_ON(iter.index > INT_MAX))
+			break;
+		ret = fn(iter.index, rcu_dereference_raw(*slot), data);
 		if (ret)
 			return ret;
 	}
@@ -173,6 +177,9 @@ void *idr_get_next(struct idr *idr, int *nextid)
 	if (!slot)
 		return NULL;
 
+	if (WARN_ON_ONCE(iter.index > INT_MAX))
+		return NULL;
+
 	*nextid = iter.index;
 	return rcu_dereference_raw(*slot);
 }
-- 
2.15.0

Re: [PATCH 11/17] cls_bpf: Convert to use idr_alloc_u32

[Jakub Kicinski]

On Tue, 28 Nov 2017 13:33:06 -0800, Matthew Wilcox wrote:
> +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
> +						INT_MAX, GFP_KERNEL);
> +	} else if (!oldprog) {
> +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
> +						handle, GFP_KERNEL);

nit: in many places you seem to not align the second line with opening
parenthesis.  Is that intentional?

FWIW there may be a small merge conflict with net on cls_bpf in patch
5, some of the code has been removed.

Re: [PATCH 11/17] cls_bpf: Convert to use idr_alloc_u32

[Matthew Wilcox]

On Tue, Nov 28, 2017 at 05:08:40PM -0800, Jakub Kicinski wrote:
> On Tue, 28 Nov 2017 13:33:06 -0800, Matthew Wilcox wrote:
> > +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
> > +						INT_MAX, GFP_KERNEL);
> > +	} else if (!oldprog) {
> > +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
> > +						handle, GFP_KERNEL);
> 
> nit: in many places you seem to not align the second line with opening
> parenthesis.  Is that intentional?

It's more that I don't care.  I press 'enter', which indents the arguments
by a certain amount, then press the 'tab' key until it looks aesthetically
pleasing.

> FWIW there may be a small merge conflict with net on cls_bpf in patch
> 5, some of the code has been removed.

Thanks.  Dave, do you want to take the IDR patches through your tree to
save conflict resolution?

Re: [PATCH 11/17] cls_bpf: Convert to use idr_alloc_u32

[David Miller]

From: Matthew Wilcox <willy@infradead.org>
Date: Wed, 29 Nov 2017 08:29:16 -0800

> On Tue, Nov 28, 2017 at 05:08:40PM -0800, Jakub Kicinski wrote:
>> On Tue, 28 Nov 2017 13:33:06 -0800, Matthew Wilcox wrote:
>> > +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
>> > +						INT_MAX, GFP_KERNEL);
>> > +	} else if (!oldprog) {
>> > +		ret = idr_alloc_u32(&head->handle_idr, prog, &handle,
>> > +						handle, GFP_KERNEL);
>> 
>> nit: in many places you seem to not align the second line with opening
>> parenthesis.  Is that intentional?
> 
> It's more that I don't care.  I press 'enter', which indents the arguments
> by a certain amount, then press the 'tab' key until it looks aesthetically
> pleasing.
> 
>> FWIW there may be a small merge conflict with net on cls_bpf in patch
>> 5, some of the code has been removed.
> 
> Thanks.  Dave, do you want to take the IDR patches through your tree to
> save conflict resolution?

Sure, after you fix the indentation problems Jakub pointed out please
resubmit them separately to netdev.