* [Patch net] net_sched: avoid generating same handle for u32 filters
@ 2014-07-18 0:34 Cong Wang
2014-07-19 22:07 ` Jamal Hadi Salim
2014-07-21 3:49 ` David Miller
0 siblings, 2 replies; 6+ messages in thread
From: Cong Wang @ 2014-07-18 0:34 UTC (permalink / raw)
To: netdev; +Cc: David S. Miller, Jamal Hadi Salim, Cong Wang, Cong Wang
From: Cong Wang <cwang@twopensource.com>
When kernel generates a handle for a u32 filter, it tries to start
from the max in the bucket. So when we have a filter with the max (fff)
handle, it will cause kernel always generates the same handle for new
filters. This can be shown by the following command:
tc qdisc add dev eth0 ingress
tc filter add dev eth0 parent ffff: protocol ip pref 770 handle 800::fff u32 match ip protocol 1 0xff
tc filter add dev eth0 parent ffff: protocol ip pref 770 u32 match ip protocol 1 0xff
...
we will get some u32 filters with same handle:
# tc filter show dev eth0 parent ffff:
filter protocol ip pref 770 u32
filter protocol ip pref 770 u32 fh 800: ht divisor 1
filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
match 00010000/00ff0000 at 8
filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
match 00010000/00ff0000 at 8
filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
match 00010000/00ff0000 at 8
filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
match 00010000/00ff0000 at 8
handles should be unique. This patch fixes it by looking up a bitmap,
so that can guarantee the handle is as unique as possible. For compatibility,
we still start from 0x800.
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Cong Wang <cwang@twopensource.com>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index c39b583..70c0be8 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -38,6 +38,7 @@
#include <linux/errno.h>
#include <linux/rtnetlink.h>
#include <linux/skbuff.h>
+#include <linux/bitmap.h>
#include <net/netlink.h>
#include <net/act_api.h>
#include <net/pkt_cls.h>
@@ -460,17 +461,25 @@ static int u32_delete(struct tcf_proto *tp, unsigned long arg)
return 0;
}
+#define NR_U32_NODE (1<<12)
static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
{
struct tc_u_knode *n;
- unsigned int i = 0x7FF;
+ unsigned long i;
+ unsigned long *bitmap = kzalloc(BITS_TO_LONGS(NR_U32_NODE) * sizeof(unsigned long),
+ GFP_KERNEL);
+ if (!bitmap)
+ return handle | 0xFFF;
for (n = ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
- if (i < TC_U32_NODE(n->handle))
- i = TC_U32_NODE(n->handle);
- i++;
+ set_bit(TC_U32_NODE(n->handle), bitmap);
- return handle | (i > 0xFFF ? 0xFFF : i);
+ i = find_next_zero_bit(bitmap, NR_U32_NODE, 0x800);
+ if (i >= NR_U32_NODE)
+ i = find_next_zero_bit(bitmap, NR_U32_NODE, 1);
+
+ kfree(bitmap);
+ return handle | (i >= NR_U32_NODE ? 0xFFF : i);
}
static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [Patch net] net_sched: avoid generating same handle for u32 filters
2014-07-18 0:34 [Patch net] net_sched: avoid generating same handle for u32 filters Cong Wang
@ 2014-07-19 22:07 ` Jamal Hadi Salim
2014-07-19 22:15 ` Cong Wang
2014-07-21 3:49 ` David Miller
1 sibling, 1 reply; 6+ messages in thread
From: Jamal Hadi Salim @ 2014-07-19 22:07 UTC (permalink / raw)
To: Cong Wang, netdev; +Cc: David S. Miller, Cong Wang
On 07/17/14 20:34, Cong Wang wrote:
> From: Cong Wang <cwang@twopensource.com>
>
> When kernel generates a handle for a u32 filter, it tries to start
> from the max in the bucket. So when we have a filter with the max (fff)
> handle, it will cause kernel always generates the same handle for new
> filters. This can be shown by the following command:
>
> tc qdisc add dev eth0 ingress
> tc filter add dev eth0 parent ffff: protocol ip pref 770 handle 800::fff u32 match ip protocol 1 0xff
> tc filter add dev eth0 parent ffff: protocol ip pref 770 u32 match ip protocol 1 0xff
> ...
>
> we will get some u32 filters with same handle:
>
> # tc filter show dev eth0 parent ffff:
> filter protocol ip pref 770 u32
> filter protocol ip pref 770 u32 fh 800: ht divisor 1
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
>
> handles should be unique. This patch fixes it by looking up a bitmap,
> so that can guarantee the handle is as unique as possible. For compatibility,
> we still start from 0x800.
>
No fundamental objection - question though: What happens if i was to
specify the handle when i provision the filter?
Side note: these handles + other info are used to "route" around
hash trees for filters.
I apologize in advance if i am slow in responding; i am on travel mode.
cheers,
jamal
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Patch net] net_sched: avoid generating same handle for u32 filters
2014-07-19 22:07 ` Jamal Hadi Salim
@ 2014-07-19 22:15 ` Cong Wang
2014-07-20 16:20 ` Jamal Hadi Salim
0 siblings, 1 reply; 6+ messages in thread
From: Cong Wang @ 2014-07-19 22:15 UTC (permalink / raw)
To: Jamal Hadi Salim
Cc: Linux Kernel Network Developers, David S. Miller, Cong Wang
On Sat, Jul 19, 2014 at 3:07 PM, Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> No fundamental objection - question though: What happens if i was to specify
> the handle when i provision the filter?
> Side note: these handles + other info are used to "route" around
> hash trees for filters.
>
gen_new_kid() is called only when handle is not specified by user.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Patch net] net_sched: avoid generating same handle for u32 filters
2014-07-19 22:15 ` Cong Wang
@ 2014-07-20 16:20 ` Jamal Hadi Salim
2014-07-21 3:49 ` David Miller
0 siblings, 1 reply; 6+ messages in thread
From: Jamal Hadi Salim @ 2014-07-20 16:20 UTC (permalink / raw)
To: Cong Wang; +Cc: Linux Kernel Network Developers, David S. Miller, Cong Wang
On 07/19/14 18:15, Cong Wang wrote:
> On Sat, Jul 19, 2014 at 3:07 PM, Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> gen_new_kid() is called only when handle is not specified by user.
>
Ok, thanks. Please add my sign-off.
cheers,
jamal
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Patch net] net_sched: avoid generating same handle for u32 filters
2014-07-20 16:20 ` Jamal Hadi Salim
@ 2014-07-21 3:49 ` David Miller
0 siblings, 0 replies; 6+ messages in thread
From: David Miller @ 2014-07-21 3:49 UTC (permalink / raw)
To: jhs; +Cc: xiyou.wangcong, netdev, cwang
From: Jamal Hadi Salim <jhs@mojatatu.com>
Date: Sun, 20 Jul 2014 12:20:29 -0400
> On 07/19/14 18:15, Cong Wang wrote:
>> On Sat, Jul 19, 2014 at 3:07 PM, Jamal Hadi Salim <jhs@mojatatu.com>
>> wrote:
>
>>
>> gen_new_kid() is called only when handle is not specified by user.
>>
>
> Ok, thanks. Please add my sign-off.
Jamal, please in the future just simply say:
Signed-off-by: Jamal ...
when you want your signoff to get added, it's more work for everyone
otherwise.
Thanks.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Patch net] net_sched: avoid generating same handle for u32 filters
2014-07-18 0:34 [Patch net] net_sched: avoid generating same handle for u32 filters Cong Wang
2014-07-19 22:07 ` Jamal Hadi Salim
@ 2014-07-21 3:49 ` David Miller
1 sibling, 0 replies; 6+ messages in thread
From: David Miller @ 2014-07-21 3:49 UTC (permalink / raw)
To: xiyou.wangcong; +Cc: netdev, jhs, cwang
From: Cong Wang <xiyou.wangcong@gmail.com>
Date: Thu, 17 Jul 2014 17:34:53 -0700
> From: Cong Wang <cwang@twopensource.com>
>
> When kernel generates a handle for a u32 filter, it tries to start
> from the max in the bucket. So when we have a filter with the max (fff)
> handle, it will cause kernel always generates the same handle for new
> filters. This can be shown by the following command:
>
> tc qdisc add dev eth0 ingress
> tc filter add dev eth0 parent ffff: protocol ip pref 770 handle 800::fff u32 match ip protocol 1 0xff
> tc filter add dev eth0 parent ffff: protocol ip pref 770 u32 match ip protocol 1 0xff
> ...
>
> we will get some u32 filters with same handle:
>
> # tc filter show dev eth0 parent ffff:
> filter protocol ip pref 770 u32
> filter protocol ip pref 770 u32 fh 800: ht divisor 1
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
> filter protocol ip pref 770 u32 fh 800::fff order 4095 key ht 800 bkt 0
> match 00010000/00ff0000 at 8
>
> handles should be unique. This patch fixes it by looking up a bitmap,
> so that can guarantee the handle is as unique as possible. For compatibility,
> we still start from 0x800.
>
> Cc: "David S. Miller" <davem@davemloft.net>
> Cc: Jamal Hadi Salim <jhs@mojatatu.com>
> Signed-off-by: Cong Wang <cwang@twopensource.com>
> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
Applied, thank you.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2014-07-21 3:49 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-07-18 0:34 [Patch net] net_sched: avoid generating same handle for u32 filters Cong Wang
2014-07-19 22:07 ` Jamal Hadi Salim
2014-07-19 22:15 ` Cong Wang
2014-07-20 16:20 ` Jamal Hadi Salim
2014-07-21 3:49 ` David Miller
2014-07-21 3:49 ` David Miller
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.