Netdev Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
@ 2019-06-19 21:09 Davide Caratti
  2019-06-19 22:04 ` Cong Wang
  0 siblings, 1 reply; 12+ messages in thread
From: Davide Caratti @ 2019-06-19 21:09 UTC (permalink / raw)
  To: Vlad Buslov, David S. Miller, netdev; +Cc: Cong Wang, Lucas Bates

on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
In this situation, the following script:

 # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
 # tc filter show dev eth0 ingress

results in an infinite loop. It happened also on other CPUs (e.g x86_64),
before commit 061775583e35 ("net: sched: flower: introduce reference
counting for filters"), because 'handle' + 1 made the u32 overflow before
it was assigned to 'cookie'; but that commit replaced the assignment with
a self-increment of 'cookie', so the problem was indirectly fixed.

Ensure not to call idr_get_next_ul() when 'cookie' contains an overflowed
value, and bail out of fl_walk() when its value is equal to ULONG_MAX.
While at it, add a TDC selftest that can be used to reproduce the problem.

 test results (on 5.2.0-0.rc5.git0.1.fc31.i686)

 unpatched (or affected) kernel:
 # ./tdc.py  -e 2ff3 -d dum0
 Test 2ff3: Add flower with max handle and then dump it
 All test results:
 1..1
 not ok 1 2ff3 - Add flower with max handle and then dump it
         Could not match regex pattern. Verify command output:
 Command "/sbin/tc filter show dev dum0 ingress" timed out

 patched (or unaffected) kernel:
 # ./tdc.py  -e 2ff3 -d dum0
 Test 2ff3: Add flower with max handle and then dump it
 All test results:
 1..1
 ok 1 2ff3 - Add flower with max handle and then dump it

Fixes: 01683a146999 ("net: sched: refactor flower walk to iterate over idr")
Reported-by: Li Shuang <shuali@redhat.com>
Signed-off-by: Davide Caratti <dcaratti@redhat.com>
---
 net/sched/cls_flower.c                        |  2 ++
 .../tc-testing/tc-tests/filters/tests.json    | 19 +++++++++++++++++++
 2 files changed, 21 insertions(+)

diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c
index eedd5786c084..acc86ae159f4 100644
--- a/net/sched/cls_flower.c
+++ b/net/sched/cls_flower.c
@@ -1702,6 +1702,8 @@ static void fl_walk(struct tcf_proto *tp, struct tcf_walker *arg,
 			break;
 		}
 		__fl_put(f);
+		if (arg->cookie == ULONG_MAX)
+			break;
 		arg->cookie++;
 		arg->count++;
 	}
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.20.1


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-19 21:09 [PATCH net] net/sched: flower: fix infinite loop in fl_walk() Davide Caratti
@ 2019-06-19 22:04 ` Cong Wang
  2019-06-20 12:52   ` Davide Caratti
  0 siblings, 1 reply; 12+ messages in thread
From: Cong Wang @ 2019-06-19 22:04 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Wed, Jun 19, 2019 at 2:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
>
> on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
> In this situation, the following script:
>
>  # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
>  # tc filter show dev eth0 ingress
>
> results in an infinite loop. It happened also on other CPUs (e.g x86_64),
> before commit 061775583e35 ("net: sched: flower: introduce reference
> counting for filters"), because 'handle' + 1 made the u32 overflow before
> it was assigned to 'cookie'; but that commit replaced the assignment with
> a self-increment of 'cookie', so the problem was indirectly fixed.

Interesting... Is this really specific to cls_flower? To me it looks like
a bug of idr_*_ul() API's, especially for idr_for_each_entry_ul().

Can you test if the following command has the same problem on i386?

tc actions add action ok index 4294967295

It is hard for me to find a 32bit CPU.


Thanks.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-19 22:04 ` Cong Wang
@ 2019-06-20 12:52   ` Davide Caratti
  2019-06-20 17:33     ` Cong Wang
  0 siblings, 1 reply; 12+ messages in thread
From: Davide Caratti @ 2019-06-20 12:52 UTC (permalink / raw)
  To: Cong Wang
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

hello Cong, thanks for reading.

On Wed, 2019-06-19 at 15:04 -0700, Cong Wang wrote:
> On Wed, Jun 19, 2019 at 2:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
> > on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
> > In this situation, the following script:
> > 
> >  # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
> >  # tc filter show dev eth0 ingress
> > 
> > results in an infinite loop. It happened also on other CPUs (e.g x86_64),
> > before commit 061775583e35 ("net: sched: flower: introduce reference
> > counting for filters"), because 'handle' + 1 made the u32 overflow before
> > it was assigned to 'cookie'; but that commit replaced the assignment with
> > a self-increment of 'cookie', so the problem was indirectly fixed.
> 
> Interesting... Is this really specific to cls_flower? To me it looks like
> a bug of idr_*_ul() API's, especially for idr_for_each_entry_ul().

good question, I have to investigate this better (idr_for_each_entry_ul()
expands in a iteration of idr_get_next_ul()). It surely got in cls_flower
when it was converted to use IDRs, but it's true that there might be other
points in TC where IDR are used and the same pattern is present (see
below).

> Can you test if the following command has the same problem on i386?
> 
> tc actions add action ok index 4294967295

the action is added, but then reading it back results in an infinite loop.
And again, the infinite loop happens on i686 and not on x86_64. I will try
to see where's the problem also here.

-- 
davide


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-20 12:52   ` Davide Caratti
@ 2019-06-20 17:33     ` Cong Wang
  2019-06-25 15:47       ` Davide Caratti
  0 siblings, 1 reply; 12+ messages in thread
From: Cong Wang @ 2019-06-20 17:33 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Thu, Jun 20, 2019 at 5:52 AM Davide Caratti <dcaratti@redhat.com> wrote:
>
> hello Cong, thanks for reading.
>
> On Wed, 2019-06-19 at 15:04 -0700, Cong Wang wrote:
> > On Wed, Jun 19, 2019 at 2:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
> > > on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
> > > In this situation, the following script:
> > >
> > >  # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
> > >  # tc filter show dev eth0 ingress
> > >
> > > results in an infinite loop. It happened also on other CPUs (e.g x86_64),
> > > before commit 061775583e35 ("net: sched: flower: introduce reference
> > > counting for filters"), because 'handle' + 1 made the u32 overflow before
> > > it was assigned to 'cookie'; but that commit replaced the assignment with
> > > a self-increment of 'cookie', so the problem was indirectly fixed.
> >
> > Interesting... Is this really specific to cls_flower? To me it looks like
> > a bug of idr_*_ul() API's, especially for idr_for_each_entry_ul().
>
> good question, I have to investigate this better (idr_for_each_entry_ul()
> expands in a iteration of idr_get_next_ul()). It surely got in cls_flower
> when it was converted to use IDRs, but it's true that there might be other
> points in TC where IDR are used and the same pattern is present (see
> below).


Yeah, this means we probably want to fix it in idr_get_next_ul() or its
callers like idr_for_each_entry_ul().

>
> > Can you test if the following command has the same problem on i386?
> >
> > tc actions add action ok index 4294967295
>
> the action is added, but then reading it back results in an infinite loop.
> And again, the infinite loop happens on i686 and not on x86_64. I will try
> to see where's the problem also here.

Right, this is what I expect, thanks for confirming it.

I am not sure it is better to handle this overflow inside idr_get_next_ul()
or just let its callers to handle it. According to the comments above
idr_get_next_ul() it sounds like it is not expected to overflow, so...

diff --git a/lib/idr.c b/lib/idr.c
index c34e256d2f01..a38f5e391cec 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -267,6 +267,9 @@ void *idr_get_next_ul(struct idr *idr, unsigned
long *nextid)
        if (!slot)
                return NULL;

+       /* overflow */
+       if (iter.index < id)
+               return NULL;
        *nextid = iter.index + base;
        return rcu_dereference_raw(*slot);
 }

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-20 17:33     ` Cong Wang
@ 2019-06-25 15:47       ` Davide Caratti
  2019-06-25 16:23         ` Davide Caratti
  2019-06-25 18:07         ` Cong Wang
  0 siblings, 2 replies; 12+ messages in thread
From: Davide Caratti @ 2019-06-25 15:47 UTC (permalink / raw)
  To: Cong Wang
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Thu, 2019-06-20 at 10:33 -0700, Cong Wang wrote:
> On Thu, Jun 20, 2019 at 5:52 AM Davide Caratti <dcaratti@redhat.com> wrote:
> > hello Cong, thanks for reading.
> > 
> > On Wed, 2019-06-19 at 15:04 -0700, Cong Wang wrote:
> > > On Wed, Jun 19, 2019 at 2:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
> > > > on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
> > > > In this situation, the following script:
> > > > 
> > > >  # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
> > > >  # tc filter show dev eth0 ingress
> > > > 
> > > > results in an infinite loop.

[...]

> I am not sure it is better to handle this overflow inside idr_get_next_ul()
> or just let its callers to handle it. According to the comments above
> idr_get_next_ul() it sounds like it is not expected to overflow, so...
> 
> diff --git a/lib/idr.c b/lib/idr.c
> index c34e256d2f01..a38f5e391cec 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -267,6 +267,9 @@ void *idr_get_next_ul(struct idr *idr, unsigned
> long *nextid)
>         if (!slot)
>                 return NULL;
> 
> +       /* overflow */
> +       if (iter.index < id)
> +               return NULL;
>         *nextid = iter.index + base;
>         return rcu_dereference_raw(*slot);
>  }

hello Cong,

I tested the above patch, but I still see the infinite loop on kernel
5.2.0-0.rc5.git0.1.fc31.i686 . 

idr_get_next_ul() returns the entry in the radix tree which is greater or 
equal to '*nextid' (which has the same value as 'id' in the above hunk). 
So, when the radix tree contains one slot with index equal to ULONG_MAX,
whatever can be the value of 'id', the condition in that if() will always 
be false (and the function will keep  returning non-NULL, hence the 
infinite loop).

I also tried this:

if (iter.index == id && id == ULONG_MAX) {
	return NULL;
}

it fixes the infinite loop, but it clearly breaks the function semantic
(and anyway, it's not sufficient to fix my test, at least with cls_flower
it still dumps the entry with id 0xffffffff several times).  I'm for
fixing the callers of idr_get_next_ul(), and in details:

- apply this patch for cls_flower
- change tcf_dump_walker() in act_api.c as follows, and add a TDC testcase
for 'gact'.

index 4e5d2e9ace5d..f34888c8a952 100644
--- a/net/sched/act_api.c
+++ b/net/sched/act_api.c
@@ -228,8 +228,11 @@ static int tcf_dump_walker(struct tcf_idrinfo
*idrinfo, struct sk_buff *skb,
 
        idr_for_each_entry_ul(idr, p, id) {
                index++;
-               if (index < s_i)
+               if (index < s_i) {
+                       if (id == ULONG_MAX)
+                               break;
                        continue;
+               }
 
                if (jiffy_since &&
                    time_after(jiffy_since,


WDYT?

thanks a lot,
-- 
davide


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-25 15:47       ` Davide Caratti
@ 2019-06-25 16:23         ` Davide Caratti
  2019-06-25 18:07         ` Cong Wang
  1 sibling, 0 replies; 12+ messages in thread
From: Davide Caratti @ 2019-06-25 16:23 UTC (permalink / raw)
  To: Cong Wang
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Tue, 2019-06-25 at 17:47 +0200, Davide Caratti wrote:
> On Thu, 2019-06-20 at 10:33 -0700, Cong Wang wrote:
> > On Thu, Jun 20, 2019 at 5:52 AM Davide Caratti <dcaratti@redhat.com> wrote:
> > > hello Cong, thanks for reading.
> > > 
> > > On Wed, 2019-06-19 at 15:04 -0700, Cong Wang wrote:
> > > > On Wed, Jun 19, 2019 at 2:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
> > > > > on some CPUs (e.g. i686), tcf_walker.cookie has the same size as the IDR.
> > > > > In this situation, the following script:
> > > > > 
> > > > >  # tc filter add dev eth0 ingress handle 0xffffffff flower action ok
> > > > >  # tc filter show dev eth0 ingress
> > > > > 
> > > > > results in an infinite loop.
> 
> So, when the radix tree contains one slot with index equal to ULONG_MAX,
> whatever can be the value of 'id',

oops, this phrase is of course wrong. the value of 'id' matters to
determine the condition of the if().

>  the condition in that if() will always 
> be false (and the function will keep  returning non-NULL, hence the 
> infinite loop).

what I wanted to say is, when the radix tree contains a single slot with
index equal to ULONG_MAX, whatever value I put in 'id' the function will
always return a pointer to that slot.

-- 
davide


^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-25 15:47       ` Davide Caratti
  2019-06-25 16:23         ` Davide Caratti
@ 2019-06-25 18:07         ` Cong Wang
  2019-06-25 19:29           ` Cong Wang
  1 sibling, 1 reply; 12+ messages in thread
From: Cong Wang @ 2019-06-25 18:07 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

Hello,

On Tue, Jun 25, 2019 at 8:47 AM Davide Caratti <dcaratti@redhat.com> wrote:
> hello Cong,
>
> I tested the above patch, but I still see the infinite loop on kernel
> 5.2.0-0.rc5.git0.1.fc31.i686 .
>
> idr_get_next_ul() returns the entry in the radix tree which is greater or
> equal to '*nextid' (which has the same value as 'id' in the above hunk).
> So, when the radix tree contains one slot with index equal to ULONG_MAX,
> whatever can be the value of 'id', the condition in that if() will always
> be false (and the function will keep  returning non-NULL, hence the
> infinite loop).
>
> I also tried this:
>
> if (iter.index == id && id == ULONG_MAX) {
>         return NULL;
> }
>
> it fixes the infinite loop, but it clearly breaks the function semantic
> (and anyway, it's not sufficient to fix my test, at least with cls_flower
> it still dumps the entry with id 0xffffffff several times).  I'm for
> fixing the callers of idr_get_next_ul(), and in details:

It now becomes more interesting.

On one hand, its callers should not need to worry about details
like overflow. On the other hand, in fact it does exactly what its
callers tell it to do, the problematic part is actually the
incremented id. On 64bit, it is fairly easy, we can just simply
know 'long' is longer than 32bit and leverage this to detect overflow,
but on 32bit this clearly doesn't work.

Let me think about it.

Thanks.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-25 18:07         ` Cong Wang
@ 2019-06-25 19:29           ` Cong Wang
  2019-06-26  0:05             ` Cong Wang
  2019-06-26 21:15             ` Cong Wang
  0 siblings, 2 replies; 12+ messages in thread
From: Cong Wang @ 2019-06-25 19:29 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

[-- Attachment #1: Type: text/plain, Size: 601 bytes --]

On Tue, Jun 25, 2019 at 11:07 AM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> On one hand, its callers should not need to worry about details
> like overflow. On the other hand, in fact it does exactly what its
> callers tell it to do, the problematic part is actually the
> incremented id. On 64bit, it is fairly easy, we can just simply
> know 'long' is longer than 32bit and leverage this to detect overflow,
> but on 32bit this clearly doesn't work.
>
> Let me think about it.

Davide, do you mind to try the attached patch?

It should handle this overflow case more gracefully, I hope.

Thanks.

[-- Attachment #2: idr_get_next_ul.diff --]
[-- Type: application/octet-stream, Size: 2903 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-25 19:29           ` Cong Wang
@ 2019-06-26  0:05             ` Cong Wang
  2019-06-26 21:15             ` Cong Wang
  1 sibling, 0 replies; 12+ messages in thread
From: Cong Wang @ 2019-06-26  0:05 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Tue, Jun 25, 2019 at 12:29 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
>
> On Tue, Jun 25, 2019 at 11:07 AM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > On one hand, its callers should not need to worry about details
> > like overflow. On the other hand, in fact it does exactly what its
> > callers tell it to do, the problematic part is actually the
> > incremented id. On 64bit, it is fairly easy, we can just simply
> > know 'long' is longer than 32bit and leverage this to detect overflow,
> > but on 32bit this clearly doesn't work.
> >
> > Let me think about it.
>
> Davide, do you mind to try the attached patch?
>
> It should handle this overflow case more gracefully, I hope.

Well, it looks like it would miss UINT_MAX... Let me see how this
can be fixed.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-25 19:29           ` Cong Wang
  2019-06-26  0:05             ` Cong Wang
@ 2019-06-26 21:15             ` Cong Wang
  2019-06-27 22:10               ` Davide Caratti
  1 sibling, 1 reply; 12+ messages in thread
From: Cong Wang @ 2019-06-26 21:15 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

[-- Attachment #1: Type: text/plain, Size: 253 bytes --]

Hi, Davide

On Tue, Jun 25, 2019 at 12:29 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> It should handle this overflow case more gracefully, I hope.
>

Please try this attached one and let me know if it works.
Hope I get it right this time.

Thanks!

[-- Attachment #2: idr_get_next_ul.patch --]
[-- Type: application/octet-stream, Size: 4956 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-26 21:15             ` Cong Wang
@ 2019-06-27 22:10               ` Davide Caratti
  2019-06-28  1:24                 ` Cong Wang
  0 siblings, 1 reply; 12+ messages in thread
From: Davide Caratti @ 2019-06-27 22:10 UTC (permalink / raw)
  To: Cong Wang
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Wed, 2019-06-26 at 14:15 -0700, Cong Wang wrote:
> Hi, Davide
> 
> On Tue, Jun 25, 2019 at 12:29 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > It should handle this overflow case more gracefully, I hope.
> > 
> 
> Please try this attached one and let me know if it works.
> Hope I get it right this time.
> 
> Thanks!

hello Cong, and thanks a lot for the patch!
I see it uses 

    (tmp <= id)

as the condition to detect the overflow, and at each iteration it does

    tmp = id, ++id

so that 'tmp' contains the last IDR found in the tree and 'id' is the next
tentative value to be searched for. When 'id' overflows, (tmp <= id)
becomes false, and the 'for' loop exits.
I tested it successfully with TC actions having the highest possible
index: 'tc actions show' doesn't loop anymore. But with cls_flower (that
uses idr_for_each_entry_continue_ul() ) I still see the infinite loop:
even when idr_for_each_entry_continue_ul() is used, fl_get_next_filter() 
never returns NULL, because 

    (tmp <= id) && (((entry) = idr_get_next_ul(idr, &(id))) != NULL)

calls idr_get_next_ul(idr, &(id)) at least once. So, even if
idr_for_each_entry_continue_ul() detected the overflow of 'id' after the
first iteration, and bailouts the for loop, fl_get_next_filter()
repeatedly returns a pointer to the idr slot with index equal to
0xffffffff. Because of that, the while() loop in fl_walk() keeps dumping
the same rule.
In my original patch I found easier to check for the overflow of
arg->cookie in fl_walk(), before the self-increment, so I was sure that 

    arg->fn(tp, f, arg)

was already called once when 'f' was the slot having the highest possible
IDR. Now, I didn't check it, but I guess 

    refcount_inc_not_zero(&f->refcnt))

in fl_get_next_filter() is always true during my test, so the inner
while() loop is not endless, even when the idr has a slot with id equal to
ULONG_MAX. Probably, to stay on the safe side, cls_flower needs both tests
to be in place, what do you think?  

-- 
davide




^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH net] net/sched: flower: fix infinite loop in fl_walk()
  2019-06-27 22:10               ` Davide Caratti
@ 2019-06-28  1:24                 ` Cong Wang
  0 siblings, 0 replies; 12+ messages in thread
From: Cong Wang @ 2019-06-28  1:24 UTC (permalink / raw)
  To: Davide Caratti
  Cc: Vlad Buslov, David S. Miller, Linux Kernel Network Developers,
	Lucas Bates

On Thu, Jun 27, 2019 at 3:10 PM Davide Caratti <dcaratti@redhat.com> wrote:
>
> On Wed, 2019-06-26 at 14:15 -0700, Cong Wang wrote:
> > Hi, Davide
> >
> > On Tue, Jun 25, 2019 at 12:29 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > > It should handle this overflow case more gracefully, I hope.
> > >
> >
> > Please try this attached one and let me know if it works.
> > Hope I get it right this time.
> >
> > Thanks!
>
> hello Cong, and thanks a lot for the patch!
> I see it uses
>
>     (tmp <= id)
>
> as the condition to detect the overflow, and at each iteration it does
>
>     tmp = id, ++id
>
> so that 'tmp' contains the last IDR found in the tree and 'id' is the next
> tentative value to be searched for. When 'id' overflows, (tmp <= id)
> becomes false, and the 'for' loop exits.

Yes, thanks for testing it with tc actions.


> I tested it successfully with TC actions having the highest possible
> index: 'tc actions show' doesn't loop anymore. But with cls_flower (that
> uses idr_for_each_entry_continue_ul() ) I still see the infinite loop:
> even when idr_for_each_entry_continue_ul() is used, fl_get_next_filter()
> never returns NULL, because
>
>     (tmp <= id) && (((entry) = idr_get_next_ul(idr, &(id))) != NULL)
>
> calls idr_get_next_ul(idr, &(id)) at least once. So, even if
> idr_for_each_entry_continue_ul() detected the overflow of 'id' after the
> first iteration, and bailouts the for loop, fl_get_next_filter()
> repeatedly returns a pointer to the idr slot with index equal to
> 0xffffffff. Because of that, the while() loop in fl_walk() keeps dumping
> the same rule.


Good catch, it is actually the arg->cookie++ which causes the trouble
here.


> In my original patch I found easier to check for the overflow of
> arg->cookie in fl_walk(), before the self-increment, so I was sure that
>
>     arg->fn(tp, f, arg)
>
> was already called once when 'f' was the slot having the highest possible
> IDR. Now, I didn't check it, but I guess
>
>     refcount_inc_not_zero(&f->refcnt))
>
> in fl_get_next_filter() is always true during my test, so the inner
> while() loop is not endless, even when the idr has a slot with id equal to
> ULONG_MAX. Probably, to stay on the safe side, cls_flower needs both tests
> to be in place, what do you think?

I think we can just fold the nested loops into one for cls_flower and remove
the arg->cookie++.

What's more, arg->cookie could overflow too,seems we have to switch back to
arg->skip. I am not sure, if this is really a problem we can fix it separately.

Thanks.

^ permalink raw reply	[flat|nested] 12+ messages in thread

end of thread, back to index

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-19 21:09 [PATCH net] net/sched: flower: fix infinite loop in fl_walk() Davide Caratti
2019-06-19 22:04 ` Cong Wang
2019-06-20 12:52   ` Davide Caratti
2019-06-20 17:33     ` Cong Wang
2019-06-25 15:47       ` Davide Caratti
2019-06-25 16:23         ` Davide Caratti
2019-06-25 18:07         ` Cong Wang
2019-06-25 19:29           ` Cong Wang
2019-06-26  0:05             ` Cong Wang
2019-06-26 21:15             ` Cong Wang
2019-06-27 22:10               ` Davide Caratti
2019-06-28  1:24                 ` Cong Wang

Netdev Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/netdev/0 netdev/git/0.git
	git clone --mirror https://lore.kernel.org/netdev/1 netdev/git/1.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 netdev netdev/ https://lore.kernel.org/netdev \
		netdev@vger.kernel.org netdev@archiver.kernel.org
	public-inbox-index netdev


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.netdev


AGPL code for this site: git clone https://public-inbox.org/ public-inbox