From fa0f5aa74316c636427ac92dad0bc5714c34ca17 Mon Sep 17 00:00:00 2001 From: Eric Dumazet Date: Tue, 3 Jan 2012 00:00:11 +0000 Subject: net_sched: qdisc_alloc_handle() can be too slow 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 CC: Dave Taht Signed-off-by: David S. Miller --- 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 dca6c1a576f7..3d8981fde301 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) -- cgit v1.2.3-59-g8ed1b