From patchwork Tue Jan 3 10:00:11 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Dumazet X-Patchwork-Id: 133991 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id A52F8B6F98 for ; Tue, 3 Jan 2012 21:00:22 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752202Ab2ACKAS (ORCPT ); Tue, 3 Jan 2012 05:00:18 -0500 Received: from mail-lpp01m010-f46.google.com ([209.85.215.46]:54843 "EHLO mail-lpp01m010-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751185Ab2ACKAQ (ORCPT ); Tue, 3 Jan 2012 05:00:16 -0500 Received: by lahd3 with SMTP id d3so3647112lah.19 for ; Tue, 03 Jan 2012 02:00:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=message-id:subject:from:to:cc:date:in-reply-to:references :content-type:x-mailer:content-transfer-encoding:mime-version; bh=0on2kaYW0lmNZveuFj73Znb8Ik5dJaiNqJxP1pcXDQ0=; b=SMv4USk7u5ShJg8aXWDGJNj3jB+6g8W5c820epqFQ7MpSK8udw0K38QDRxcTZWPo8j 7SmpvcRtQEzb4lHPjCf6NuB4SvO9lG5E21ezF4kNFUIt6JG5zlLzVZZs5ErDIVNBFB8V dE4ald9bmyXrnlWXaijqseaMCupKhZTE5amGE= Received: by 10.152.111.201 with SMTP id ik9mr36571324lab.8.1325584815041; Tue, 03 Jan 2012 02:00:15 -0800 (PST) Received: from [10.150.51.211] (gw0.net.jmsp.net. [212.23.165.14]) by mx.google.com with ESMTPS id sv10sm769302lab.14.2012.01.03.02.00.12 (version=SSLv3 cipher=OTHER); Tue, 03 Jan 2012 02:00:13 -0800 (PST) Message-ID: <1325584811.2320.11.camel@edumazet-HP-Compaq-6005-Pro-SFF-PC> Subject: [PATCH net-next v2] net_sched: qdisc_alloc_handle() can be too slow From: Eric Dumazet To: David Miller Cc: netdev , Dave Taht Date: Tue, 03 Jan 2012 11:00:11 +0100 In-Reply-To: <1325584697.2320.9.camel@edumazet-HP-Compaq-6005-Pro-SFF-PC> References: <1325584697.2320.9.camel@edumazet-HP-Compaq-6005-Pro-SFF-PC> X-Mailer: Evolution 3.2.1- Mime-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org 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 --- 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 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)