From patchwork Fri Aug 14 13:25:20 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Krishna Kumar X-Patchwork-Id: 31402 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@bilbo.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from ozlabs.org (ozlabs.org [203.10.76.45]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "mx.ozlabs.org", Issuer "CA Cert Signing Authority" (verified OK)) by bilbo.ozlabs.org (Postfix) with ESMTPS id C51E1B6F1E for ; Fri, 14 Aug 2009 23:25:30 +1000 (EST) Received: by ozlabs.org (Postfix) id B16ABDDD1B; Fri, 14 Aug 2009 23:25:30 +1000 (EST) Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 23D10DDD0B for ; Fri, 14 Aug 2009 23:25:30 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755741AbZHNNZV (ORCPT ); Fri, 14 Aug 2009 09:25:21 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1755672AbZHNNZU (ORCPT ); Fri, 14 Aug 2009 09:25:20 -0400 Received: from e23smtp09.au.ibm.com ([202.81.31.142]:43844 "EHLO e23smtp09.au.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754913AbZHNNZT (ORCPT ); Fri, 14 Aug 2009 09:25:19 -0400 Received: from d23relay02.au.ibm.com (d23relay02.au.ibm.com [202.81.31.244]) by e23smtp09.au.ibm.com (8.14.3/8.13.1) with ESMTP id n7EDMhVs026810 for ; Fri, 14 Aug 2009 23:22:43 +1000 Received: from d23av03.au.ibm.com (d23av03.au.ibm.com [9.190.234.97]) by d23relay02.au.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id n7EDPKi61187946 for ; Fri, 14 Aug 2009 23:25:20 +1000 Received: from d23av03.au.ibm.com (loopback [127.0.0.1]) by d23av03.au.ibm.com (8.12.11.20060308/8.13.3) with ESMTP id n7EDPJt7018031 for ; Fri, 14 Aug 2009 23:25:20 +1000 Received: from localhost.localdomain ([9.77.71.9]) by d23av03.au.ibm.com (8.12.11.20060308/8.12.11) with ESMTP id n7EDPCJS017929; Fri, 14 Aug 2009 23:25:15 +1000 From: Krishna Kumar To: Jarek Poplawski Cc: netdev@vger.kernel.org, herbert@gondor.apana.org.au, kaber@trash.net, Krishna Kumar , davem@davemloft.net Date: Fri, 14 Aug 2009 18:55:20 +0530 Message-Id: <20090814132520.27518.3049.sendpatchset@localhost.localdomain> In-Reply-To: <20090814132458.27518.65144.sendpatchset@localhost.localdomain> References: <20090814132458.27518.65144.sendpatchset@localhost.localdomain> Subject: [PATCH v1] Speed-up pfifo_fast lookup using a public bitmap Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Signed-off-by: Krishna Kumar --- include/net/sch_generic.h | 1 net/sched/sch_generic.c | 46 +++++++++++++++++++++++------------- 2 files changed, 31 insertions(+), 16 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 -ruNp org/include/net/sch_generic.h new/include/net/sch_generic.h --- org/include/net/sch_generic.h 2009-08-07 12:05:43.000000000 +0530 +++ new/include/net/sch_generic.h 2009-08-13 16:55:32.000000000 +0530 @@ -72,6 +72,7 @@ struct Qdisc * For performance sake on SMP, we put highly modified fields at the end */ unsigned long state; + u32 bitmap; struct sk_buff_head q; struct gnet_stats_basic bstats; struct gnet_stats_queue qstats; diff -ruNp org/net/sched/sch_generic.c new/net/sched/sch_generic.c --- org/net/sched/sch_generic.c 2009-08-07 12:05:43.000000000 +0530 +++ new/net/sched/sch_generic.c 2009-08-14 18:23:01.000000000 +0530 @@ -406,18 +406,28 @@ static const u8 prio2band[TC_PRIO_MAX+1] #define PFIFO_FAST_BANDS 3 -static inline struct sk_buff_head *prio2list(struct sk_buff *skb, - struct Qdisc *qdisc) +/* + * Convert a bitmap to the first band number where an skb is queued, where: + * bitmap=0 means there are no skbs on any band. + * bitmap=1 means there is an skb on band 0. + * bitmap=7 means there are skbs on all 3 bands, etc. + */ +static const int bitmap2band[] = {-1, 0, 1, 0, 2, 0, 1, 0}; + +static inline struct sk_buff_head *band2list(struct Qdisc *qdisc, int band) { struct sk_buff_head *list = qdisc_priv(qdisc); - return list + prio2band[skb->priority & TC_PRIO_MAX]; + + return list + band; } static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc) { - struct sk_buff_head *list = prio2list(skb, qdisc); + int band = prio2band[skb->priority & TC_PRIO_MAX]; + struct sk_buff_head *list = band2list(qdisc, band); if (skb_queue_len(list) < qdisc_dev(qdisc)->tx_queue_len) { + qdisc->bitmap |= (1 << band); qdisc->q.qlen++; return __qdisc_enqueue_tail(skb, qdisc, list); } @@ -427,14 +437,17 @@ static int pfifo_fast_enqueue(struct sk_ static struct sk_buff *pfifo_fast_dequeue(struct Qdisc* qdisc) { - int prio; - struct sk_buff_head *list = qdisc_priv(qdisc); + int band = bitmap2band[qdisc->bitmap]; - for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) { - if (!skb_queue_empty(list + prio)) { - qdisc->q.qlen--; - return __qdisc_dequeue_head(qdisc, list + prio); - } + if (likely(band >= 0)) { + struct sk_buff_head *list = qdisc_priv(qdisc); + struct sk_buff *skb = __qdisc_dequeue_head(qdisc, list + band); + + qdisc->q.qlen--; + if (skb_queue_empty(list + band)) + qdisc->bitmap &= ~(1 << band); + + return skb; } return NULL; @@ -442,12 +455,12 @@ static struct sk_buff *pfifo_fast_dequeu static struct sk_buff *pfifo_fast_peek(struct Qdisc* qdisc) { - int prio; - struct sk_buff_head *list = qdisc_priv(qdisc); + int band = bitmap2band[qdisc->bitmap]; + + if (band >= 0) { + struct sk_buff_head *list = qdisc_priv(qdisc); - for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) { - if (!skb_queue_empty(list + prio)) - return skb_peek(list + prio); + return skb_peek(list + band); } return NULL; @@ -461,6 +474,7 @@ static void pfifo_fast_reset(struct Qdis for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) __qdisc_reset_queue(qdisc, list + prio); + qdisc->bitmap = 0; qdisc->qstats.backlog = 0; qdisc->q.qlen = 0; }