Message ID | 1325584811.2320.11.camel@edumazet-HP-Compaq-6005-Pro-SFF-PC |
---|---|
State | Accepted, archived |
Delegated to: | David Miller |
Headers | show |
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.
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 :) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 ] -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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)
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(-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html