[Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[Cong Wang]

idr_get_next_ul() is problematic by design, it can't handle
the following overflow case well on 32-bit CPU:

u32 id = UINT_MAX;
idr_alloc_u32(&id);
while (idr_get_next_ul(&id) != NULL)
 id++;

when 'id' overflows and becomes 0 after UINT_MAX, the loop
goes infinite.

Fix this by eliminating external users of idr_get_next_ul()
and migrating them to idr_for_each_entry_continue_ul(). And
add an additional parameter for these iteration macros to detect
overflow properly.

Please merge this through networking tree, as all the users
are in networking subsystem.

Cong Wang (2):
  idr: fix overflow case for idr_for_each_entry_ul()
  idr: introduce idr_for_each_entry_continue_ul()

Davide Caratti (1):
  selftests: add a test case for cls_lower handle overflow

---
 .../ethernet/mellanox/mlx5/core/fs_counters.c | 10 ++++---
 include/linux/idr.h                           | 21 +++++++++++++--
 net/sched/act_api.c                           |  9 ++++---
 net/sched/cls_flower.c                        | 27 +++++--------------
 .../tc-testing/tc-tests/filters/tests.json    | 19 +++++++++++++
 5 files changed, 57 insertions(+), 29 deletions(-)

-- 
2.21.0

[Patch net 1/3] idr: fix overflow case for idr_for_each_entry_ul()

[Cong Wang]

idr_for_each_entry_ul() is buggy as it can't handle overflow
case correctly. When we have an ID == UINT_MAX, it becomes an
infinite loop. This happens when running on 32-bit CPU where
unsigned long has the same size with unsigned int.

There is no better way to fix this than casting it to a larger
integer, but we can't just 64 bit integer on 32 bit CPU. Instead
we could just use an additional integer to help us to detect this
overflow case, that is, adding a new parameter to this macro.
Fortunately tc action is its only user right now.

Fixes: 65a206c01e8e ("net/sched: Change act_api and act_xxx modules to use IDR")
Reported-by: Li Shuang <shuali@redhat.com>
Tested-by: Davide Caratti <dcaratti@redhat.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Chris Mi <chrism@mellanox.com>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 include/linux/idr.h | 7 +++++--
 net/sched/act_api.c | 9 ++++++---
 2 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index ee7abae143d3..68528a72d10d 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -191,14 +191,17 @@ static inline void idr_preload_end(void)
  * 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.
+ * @tmp: A temporary placeholder for ID.
  * @id: Entry ID.
  *
  * @entry and @id do not need to be initialized before the loop, and
  * after normal termination @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)
+#define idr_for_each_entry_ul(idr, entry, tmp, id)			\
+	for (tmp = 0, id = 0;						\
+	     tmp <= id && ((entry) = idr_get_next_ul(idr, &(id))) != NULL; \
+	     tmp = id, ++id)
 
 /**
  * idr_for_each_entry_continue() - Continue iteration over an IDR's elements of a given type
diff --git a/net/sched/act_api.c b/net/sched/act_api.c
index 5567af5d7cb5..835adde28a7e 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -221,12 +221,13 @@ static int tcf_dump_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 	struct idr *idr = &idrinfo->action_idr;
 	struct tc_action *p;
 	unsigned long id = 1;
+	unsigned long tmp;
 
 	mutex_lock(&idrinfo->lock);
 
 	s_i = cb->args[0];
 
-	idr_for_each_entry_ul(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, tmp, id) {
 		index++;
 		if (index < s_i)
 			continue;
@@ -292,6 +293,7 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 	struct idr *idr = &idrinfo->action_idr;
 	struct tc_action *p;
 	unsigned long id = 1;
+	unsigned long tmp;
 
 	nest = nla_nest_start_noflag(skb, 0);
 	if (nest == NULL)
@@ -300,7 +302,7 @@ static int tcf_del_walker(struct tcf_idrinfo *idrinfo, struct sk_buff *skb,
 		goto nla_put_failure;
 
 	mutex_lock(&idrinfo->lock);
-	idr_for_each_entry_ul(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, tmp, id) {
 		ret = tcf_idr_release_unsafe(p);
 		if (ret == ACT_P_DELETED) {
 			module_put(ops->owner);
@@ -533,8 +535,9 @@ void tcf_idrinfo_destroy(const struct tc_action_ops *ops,
 	struct tc_action *p;
 	int ret;
 	unsigned long id = 1;
+	unsigned long tmp;
 
-	idr_for_each_entry_ul(idr, p, id) {
+	idr_for_each_entry_ul(idr, p, tmp, id) {
 		ret = __tcf_idr_release(p, false, true);
 		if (ret == ACT_P_DELETED)
 			module_put(ops->owner);
-- 
2.21.0

[Patch net 2/3] idr: introduce idr_for_each_entry_continue_ul()

[Cong Wang]

Similarly, other callers of idr_get_next_ul() suffer the same
overflow bug as they don't handle it properly either.

Introduce idr_for_each_entry_continue_ul() to help these callers
iterate from a given ID.

cls_flower needs more care here because it still has overflow when
does arg->cookie++, we have to fold its nested loops into one
and remove the arg->cookie++.

Fixes: 01683a146999 ("net: sched: refactor flower walk to iterate over idr")
Fixes: 12d6066c3b29 ("net/mlx5: Add flow counters idr")
Reported-by: Li Shuang <shuali@redhat.com>
Cc: Davide Caratti <dcaratti@redhat.com>
Cc: Vlad Buslov <vladbu@mellanox.com>
Cc: Chris Mi <chrism@mellanox.com>
Cc: Matthew Wilcox <willy@infradead.org>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 .../ethernet/mellanox/mlx5/core/fs_counters.c | 10 ++++---
 include/linux/idr.h                           | 14 ++++++++++
 net/sched/cls_flower.c                        | 27 +++++--------------
 3 files changed, 27 insertions(+), 24 deletions(-)

diff --git a/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c b/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
index c6c28f56aa29..b3762123a69c 100644
--- a/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
+++ b/drivers/net/ethernet/mellanox/mlx5/core/fs_counters.c
@@ -102,13 +102,15 @@ static struct list_head *mlx5_fc_counters_lookup_next(struct mlx5_core_dev *dev,
 	struct mlx5_fc_stats *fc_stats = &dev->priv.fc_stats;
 	unsigned long next_id = (unsigned long)id + 1;
 	struct mlx5_fc *counter;
+	unsigned long tmp;
 
 	rcu_read_lock();
 	/* skip counters that are in idr, but not yet in counters list */
-	while ((counter = idr_get_next_ul(&fc_stats->counters_idr,
-					  &next_id)) != NULL &&
-	       list_empty(&counter->list))
-		next_id++;
+	idr_for_each_entry_continue_ul(&fc_stats->counters_idr,
+				       counter, tmp, next_id) {
+		if (!list_empty(&counter->list))
+			break;
+	}
 	rcu_read_unlock();
 
 	return counter ? &counter->list : &fc_stats->counters;
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 68528a72d10d..4ec8986e5dfb 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -216,6 +216,20 @@ static inline void idr_preload_end(void)
 	     entry;							\
 	     ++id, (entry) = idr_get_next((idr), &(id)))
 
+/**
+ * idr_for_each_entry_continue_ul() - Continue iteration over an IDR's elements of a given type
+ * @idr: IDR handle.
+ * @entry: The type * to use as a cursor.
+ * @tmp: A temporary placeholder for ID.
+ * @id: Entry ID.
+ *
+ * Continue to iterate over entries, continuing after the current position.
+ */
+#define idr_for_each_entry_continue_ul(idr, entry, tmp, id)		\
+	for (tmp = id;							\
+	     tmp <= id && ((entry) = idr_get_next_ul(idr, &(id))) != NULL; \
+	     tmp = id, ++id)
+
 /*
  * IDA - ID Allocator, use when translation from id to pointer isn't necessary.
  */
diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index eedd5786c084..fdeede3af72e 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -524,24 +524,6 @@ static struct cls_fl_filter *__fl_get(struct cls_fl_head *head, u32 handle)
 	return f;
 }
 
-static struct cls_fl_filter *fl_get_next_filter(struct tcf_proto *tp,
-						unsigned long *handle)
-{
-	struct cls_fl_head *head = fl_head_dereference(tp);
-	struct cls_fl_filter *f;
-
-	rcu_read_lock();
-	while ((f = idr_get_next_ul(&head->handle_idr, handle))) {
-		/* don't return filters that are being deleted */
-		if (refcount_inc_not_zero(&f->refcnt))
-			break;
-		++(*handle);
-	}
-	rcu_read_unlock();
-
-	return f;
-}
-
 static int __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f,
 		       bool *last, bool rtnl_held,
 		       struct netlink_ext_ack *extack)
@@ -1691,20 +1673,25 @@ static int fl_delete(struct tcf_proto *tp, void *arg, bool *last,
 static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 		    bool rtnl_held)
 {
+	struct cls_fl_head *head = fl_head_dereference(tp);
+	unsigned long id = arg->cookie, tmp;
 	struct cls_fl_filter *f;
 
 	arg->count = arg->skip;
 
-	while ((f = fl_get_next_filter(tp, &arg->cookie)) != NULL) {
+	idr_for_each_entry_continue_ul(&head->handle_idr, f, tmp, id) {
+		/* don't return filters that are being deleted */
+		if (!refcount_inc_not_zero(&f->refcnt))
+			continue;
 		if (arg->fn(tp, f, arg) < 0) {
 			__fl_put(f);
 			arg->stop = 1;
 			break;
 		}
 		__fl_put(f);
-		arg->cookie++;
 		arg->count++;
 	}
+	arg->cookie = id;
 }
 
 static struct cls_fl_filter *
-- 
2.21.0

[Patch net 3/3] selftests: add a test case for cls_lower handle overflow

[Cong Wang]

From: Davide Caratti <dcaratti@redhat.com>

Reported-by: Li Shuang <shuali@redhat.com>
Signed-off-by: Davide Caratti <dcaratti@redhat.com>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 .../tc-testing/tc-tests/filters/tests.json    | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/tools/testing/selftests/tc-testing/tc-tests/filters/tests.json b/tools/testing/selftests/tc-testing/tc-tests/filters/tests.json
index e2f92cefb8d5..16559c436f21 100644
--- a/tools/testing/selftests/tc-testing/tc-tests/filters/tests.json
+++ b/tools/testing/selftests/tc-testing/tc-tests/filters/tests.json
@@ -38,6 +38,25 @@
             "$TC qdisc del dev $DEV1 clsact"
         ]
     },
+    {
+        "id": "2ff3",
+        "name": "Add flower with max handle and then dump it",
+        "category": [
+            "filter",
+            "flower"
+        ],
+        "setup": [
+            "$TC qdisc add dev $DEV2 ingress"
+        ],
+        "cmdUnderTest": "$TC filter add dev $DEV2 protocol ip pref 1 parent ffff: handle 0xffffffff flower action ok",
+        "expExitCode": "0",
+        "verifyCmd": "$TC filter show dev $DEV2 ingress",
+        "matchPattern": "filter protocol ip pref 1 flower.*handle 0xffffffff",
+        "matchCount": "1",
+        "teardown": [
+            "$TC qdisc del dev $DEV2 ingress"
+        ]
+    },
     {
         "id": "d052",
         "name": "Add 1M filters with the same action",
-- 
2.21.0

Re: [Patch net 2/3] idr: introduce idr_for_each_entry_continue_ul()

[Davide Caratti]

On Fri, 2019-06-28 at 11:03 -0700, Cong Wang wrote:
> Similarly, other callers of idr_get_next_ul() suffer the same
> overflow bug as they don't handle it properly either.
> 
> Introduce idr_for_each_entry_continue_ul() to help these callers
> iterate from a given ID.
> 
> cls_flower needs more care here because it still has overflow when
> does arg->cookie++, we have to fold its nested loops into one
> and remove the arg->cookie++.

hello Cong,

I confirm that this patch fixes the infinite loop when dumping TC flower
rule with handle 0xffffffff on kernel 5.2.0-0.rc5.git0.1.fc31.i686.

Tested-by: Davide Caratti <dcaratti@redhat.com>

thanks!
-- 
davide

Re: [Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[David Miller]

From: Cong Wang <xiyou.wangcong@gmail.com>
Date: Fri, 28 Jun 2019 11:03:40 -0700

> idr_get_next_ul() is problematic by design, it can't handle
> the following overflow case well on 32-bit CPU:
> 
> u32 id = UINT_MAX;
> idr_alloc_u32(&id);
> while (idr_get_next_ul(&id) != NULL)
>  id++;
> 
> when 'id' overflows and becomes 0 after UINT_MAX, the loop
> goes infinite.
> 
> Fix this by eliminating external users of idr_get_next_ul()
> and migrating them to idr_for_each_entry_continue_ul(). And
> add an additional parameter for these iteration macros to detect
> overflow properly.
> 
> Please merge this through networking tree, as all the users
> are in networking subsystem.

Series applied, thanks Cong.

Re: [Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[Matthew Wilcox]

On Mon, Jul 01, 2019 at 07:16:00PM -0700, David Miller wrote:
> From: Cong Wang <xiyou.wangcong@gmail.com>
> Date: Fri, 28 Jun 2019 11:03:40 -0700
> 
> > idr_get_next_ul() is problematic by design, it can't handle
> > the following overflow case well on 32-bit CPU:
> > 
> > u32 id = UINT_MAX;
> > idr_alloc_u32(&id);
> > while (idr_get_next_ul(&id) != NULL)
> >  id++;
> > 
> > when 'id' overflows and becomes 0 after UINT_MAX, the loop
> > goes infinite.
> > 
> > Fix this by eliminating external users of idr_get_next_ul()
> > and migrating them to idr_for_each_entry_continue_ul(). And
> > add an additional parameter for these iteration macros to detect
> > overflow properly.
> > 
> > Please merge this through networking tree, as all the users
> > are in networking subsystem.
> 
> Series applied, thanks Cong.

Ugh, I don't even get the weekend to reply?

I think this is just a bad idea.  It'd be better to apply the conversion
patches to use XArray than fix up this crappy interface.  I didn't
reply before because I wanted to check those patches still apply and
post them as part of the response.  Now they're definitely broken and
need to be redone.

Re: [Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[David Miller]

From: Matthew Wilcox <willy@infradead.org>
Date: Mon, 1 Jul 2019 19:37:30 -0700

> On Mon, Jul 01, 2019 at 07:16:00PM -0700, David Miller wrote:
>> From: Cong Wang <xiyou.wangcong@gmail.com>
>> Date: Fri, 28 Jun 2019 11:03:40 -0700
>> 
>> > idr_get_next_ul() is problematic by design, it can't handle
>> > the following overflow case well on 32-bit CPU:
>> > 
>> > u32 id = UINT_MAX;
>> > idr_alloc_u32(&id);
>> > while (idr_get_next_ul(&id) != NULL)
>> >  id++;
>> > 
>> > when 'id' overflows and becomes 0 after UINT_MAX, the loop
>> > goes infinite.
>> > 
>> > Fix this by eliminating external users of idr_get_next_ul()
>> > and migrating them to idr_for_each_entry_continue_ul(). And
>> > add an additional parameter for these iteration macros to detect
>> > overflow properly.
>> > 
>> > Please merge this through networking tree, as all the users
>> > are in networking subsystem.
>> 
>> Series applied, thanks Cong.
> 
> Ugh, I don't even get the weekend to reply?
> 
> I think this is just a bad idea.  It'd be better to apply the conversion
> patches to use XArray than fix up this crappy interface.  I didn't
> reply before because I wanted to check those patches still apply and
> post them as part of the response.  Now they're definitely broken and
> need to be redone.

Please work this out with Cong.

I think his approach is safe for net and thus -stable than an xarray
conversion.

Re: [Patch net 0/3] idr: fix overflow cases on 32-bit CPU

[Cong Wang]

On Mon, Jul 1, 2019 at 7:37 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Mon, Jul 01, 2019 at 07:16:00PM -0700, David Miller wrote:
> > From: Cong Wang <xiyou.wangcong@gmail.com>
> > Date: Fri, 28 Jun 2019 11:03:40 -0700
> >
> > > idr_get_next_ul() is problematic by design, it can't handle
> > > the following overflow case well on 32-bit CPU:
> > >
> > > u32 id = UINT_MAX;
> > > idr_alloc_u32(&id);
> > > while (idr_get_next_ul(&id) != NULL)
> > >  id++;
> > >
> > > when 'id' overflows and becomes 0 after UINT_MAX, the loop
> > > goes infinite.
> > >
> > > Fix this by eliminating external users of idr_get_next_ul()
> > > and migrating them to idr_for_each_entry_continue_ul(). And
> > > add an additional parameter for these iteration macros to detect
> > > overflow properly.
> > >
> > > Please merge this through networking tree, as all the users
> > > are in networking subsystem.
> >
> > Series applied, thanks Cong.
>
> Ugh, I don't even get the weekend to reply?
>
> I think this is just a bad idea.  It'd be better to apply the conversion
> patches to use XArray than fix up this crappy interface.  I didn't
> reply before because I wanted to check those patches still apply and
> post them as part of the response.  Now they're definitely broken and
> need to be redone.

You can always do refactoring for net-next/linux-next. It is never late
for it.

Thanks.