* [PATCH net-next] net_sched: qdisc_alloc_handle() can be too slow @ 2012-01-03 9:58 Eric Dumazet 2012-01-03 10:00 ` [PATCH net-next v2] " Eric Dumazet 0 siblings, 1 reply; 5+ messages in thread From: Eric Dumazet @ 2012-01-03 9:58 UTC (permalink / raw) To: David Miller; +Cc: netdev, Dave Taht When trying to allocate ~32768 qdiscs using autohandle mechanism, we can fill the space managed by kernel (handles in [8000-FFFF]:0000 range) But O(N^2) qdisc_alloc_handle() loops 0x10000 times instead of 0x8000 time tc add qdisc add dev eth0 parent 10:7fff pfifo limit 10 RTNETLINK answers: Cannot allocate memory real 1m54.826s user 0m0.000s sys 0m0.004s INFO: rcu_sched_state detected stall on CPU 0 (t=60000 jiffies) Half number of loops, and add a cond_resched() call. We hold rtnl at this point. Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> CC: Dave Taht <dave.taht@gmail.com> --- Next move is using rb-tree instead of a linked list, to speedup qdisc_lookup(). A complex qdisc setup is way too slow. net/sched/sch_api.c | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) ^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH net-next v2] net_sched: qdisc_alloc_handle() can be too slow 2012-01-03 9:58 [PATCH net-next] net_sched: qdisc_alloc_handle() can be too slow Eric Dumazet @ 2012-01-03 10:00 ` Eric Dumazet 2012-01-03 10:23 ` Dave Taht 2012-01-03 18:03 ` David Miller 0 siblings, 2 replies; 5+ messages in thread From: Eric Dumazet @ 2012-01-03 10:00 UTC (permalink / raw) To: David Miller; +Cc: netdev, Dave Taht When trying to allocate ~32768 qdiscs using autohandle mechanism, we can fill the space managed by kernel (handles in [8000-FFFF]:0000 range) But O(N^2) qdisc_alloc_handle() loops 0x10000 times instead of 0x8000 time tc add qdisc add dev eth0 parent 10:7fff pfifo limit 10 RTNETLINK answers: Cannot allocate memory real 1m54.826s user 0m0.000s sys 0m0.004s INFO: rcu_sched_state detected stall on CPU 0 (t=60000 jiffies) Half number of loops, and add a cond_resched() call. We hold rtnl at this point. Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> CC: Dave Taht <dave.taht@gmail.com> --- v2: With the patch itself :) Next move is using rb-tree instead of a linked list, to speedup qdisc_lookup(). A complex qdisc setup is way too slow. net/sched/sch_api.c | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c index dca6c1a..3d8981f 100644 --- a/net/sched/sch_api.c +++ b/net/sched/sch_api.c @@ -618,20 +618,24 @@ void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash, } EXPORT_SYMBOL(qdisc_class_hash_remove); -/* Allocate an unique handle from space managed by kernel */ - +/* Allocate an unique handle from space managed by kernel + * Possible range is [8000-FFFF]:0000 (0x8000 values) + */ static u32 qdisc_alloc_handle(struct net_device *dev) { - int i = 0x10000; + int i = 0x8000; static u32 autohandle = TC_H_MAKE(0x80000000U, 0); do { autohandle += TC_H_MAKE(0x10000U, 0); if (autohandle == TC_H_MAKE(TC_H_ROOT, 0)) autohandle = TC_H_MAKE(0x80000000U, 0); - } while (qdisc_lookup(dev, autohandle) && --i > 0); + if (!qdisc_lookup(dev, autohandle)) + return autohandle; + cond_resched(); + } while (--i > 0); - return i > 0 ? autohandle : 0; + return 0; } void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n) ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH net-next v2] net_sched: qdisc_alloc_handle() can be too slow 2012-01-03 10:00 ` [PATCH net-next v2] " Eric Dumazet @ 2012-01-03 10:23 ` Dave Taht 2012-01-03 18:03 ` David Miller 1 sibling, 0 replies; 5+ messages in thread From: Dave Taht @ 2012-01-03 10:23 UTC (permalink / raw) To: Eric Dumazet; +Cc: David Miller, netdev On Tue, Jan 3, 2012 at 11:00 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > When trying to allocate ~32768 qdiscs using autohandle mechanism, we can > fill the space managed by kernel (handles in [8000-FFFF]:0000 range) > > But O(N^2) qdisc_alloc_handle() loops 0x10000 times instead of 0x8000 > > time tc add qdisc add dev eth0 parent 10:7fff pfifo limit 10 > RTNETLINK answers: Cannot allocate memory > real 1m54.826s > user 0m0.000s > sys 0m0.004s > > INFO: rcu_sched_state detected stall on CPU 0 (t=60000 jiffies) > > Half number of loops, and add a cond_resched() call. > We hold rtnl at this point. > > Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> > CC: Dave Taht <dave.taht@gmail.com> > --- > v2: With the patch itself :) > > Next move is using rb-tree instead of a linked list, to speedup > qdisc_lookup(). A complex qdisc setup is way too slow. > > net/sched/sch_api.c | 14 +++++++++----- > 1 file changed, 9 insertions(+), 5 deletions(-) > > diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c > index dca6c1a..3d8981f 100644 > --- a/net/sched/sch_api.c > +++ b/net/sched/sch_api.c > @@ -618,20 +618,24 @@ void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash, > } > EXPORT_SYMBOL(qdisc_class_hash_remove); > > -/* Allocate an unique handle from space managed by kernel */ > - > +/* Allocate an unique handle from space managed by kernel > + * Possible range is [8000-FFFF]:0000 (0x8000 values) > + */ > static u32 qdisc_alloc_handle(struct net_device *dev) > { > - int i = 0x10000; > + int i = 0x8000; > static u32 autohandle = TC_H_MAKE(0x80000000U, 0); > > do { > autohandle += TC_H_MAKE(0x10000U, 0); > if (autohandle == TC_H_MAKE(TC_H_ROOT, 0)) > autohandle = TC_H_MAKE(0x80000000U, 0); > - } while (qdisc_lookup(dev, autohandle) && --i > 0); > + if (!qdisc_lookup(dev, autohandle)) > + return autohandle; > + cond_resched(); > + } while (--i > 0); > > - return i > 0 ? autohandle : 0; > + return 0; > } > > void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n) > > I take it this is from you trying to allocate XXk bins in staqfq.lua and watching it go boom? I'll gladly go and try to break more stuff if you like. :) I ran yesterday's patches for sfq, and qfq on net-next all night on an x86 box, successfully, on e1000e to ag71xx. I'm not willing to declare victory on QFQ yet, it was a really hard problem to trigger... give me a day on it... I'm testing the backport of those two patches to 3.1.6 (no porting needed, they just apply) on cerowrt now, then I'm going to setup a fairly complex scenario (wireless,wired, 7-8 machines) in bloatlab #2 The wireless data I got a couple days back is rather noisy but the median is promising. http://www.teklibre.com/~d/bloat/wireless.qfqvspfifofast10iperfs.png I'll get a lot more over the next few days and smooth it out. -- Dave Täht SKYPE: davetaht US Tel: 1-239-829-5608 FR Tel: 0638645374 http://www.bufferbloat.net ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH net-next v2] net_sched: qdisc_alloc_handle() can be too slow 2012-01-03 10:00 ` [PATCH net-next v2] " Eric Dumazet 2012-01-03 10:23 ` Dave Taht @ 2012-01-03 18:03 ` David Miller 2012-01-03 20:34 ` Eric Dumazet 1 sibling, 1 reply; 5+ messages in thread From: David Miller @ 2012-01-03 18:03 UTC (permalink / raw) To: eric.dumazet; +Cc: netdev, dave.taht From: Eric Dumazet <eric.dumazet@gmail.com> Date: Tue, 03 Jan 2012 11:00:11 +0100 > When trying to allocate ~32768 qdiscs using autohandle mechanism, we can > fill the space managed by kernel (handles in [8000-FFFF]:0000 range) > > But O(N^2) qdisc_alloc_handle() loops 0x10000 times instead of 0x8000 > > time tc add qdisc add dev eth0 parent 10:7fff pfifo limit 10 > RTNETLINK answers: Cannot allocate memory > real 1m54.826s > user 0m0.000s > sys 0m0.004s > > INFO: rcu_sched_state detected stall on CPU 0 (t=60000 jiffies) > > Half number of loops, and add a cond_resched() call. > We hold rtnl at this point. > > Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> > CC: Dave Taht <dave.taht@gmail.com> Applied, thanks Eric. I always cringed when I looked at this function :) ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH net-next v2] net_sched: qdisc_alloc_handle() can be too slow 2012-01-03 18:03 ` David Miller @ 2012-01-03 20:34 ` Eric Dumazet 0 siblings, 0 replies; 5+ messages in thread From: Eric Dumazet @ 2012-01-03 20:34 UTC (permalink / raw) To: David Miller; +Cc: netdev, dave.taht Le mardi 03 janvier 2012 à 13:03 -0500, David Miller a écrit : > Applied, thanks Eric. I always cringed when I looked at this function :) > Yep :( I'll add an IDR (and not a btree as I stated earlier) to get O(1) allocations and qdisc_lookup(), it should help to optimize qdisc_tree_decrease_qlen() [ Slow as hell for complex qdisc setups ] ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2012-01-03 20:34 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2012-01-03 9:58 [PATCH net-next] net_sched: qdisc_alloc_handle() can be too slow Eric Dumazet 2012-01-03 10:00 ` [PATCH net-next v2] " Eric Dumazet 2012-01-03 10:23 ` Dave Taht 2012-01-03 18:03 ` David Miller 2012-01-03 20:34 ` Eric Dumazet
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox
