* [PATCH v1] Speed-up pfifo_fast lookup using a public bitmap
2009-08-14 13:24 [PATCH] Speed-up pfifo_fast lookup using a bitmap Krishna Kumar
@ 2009-08-14 13:25 ` Krishna Kumar
2009-08-14 13:25 ` [PATCH v2] Speed-up pfifo_fast lookup using a private bitmap Krishna Kumar
2009-08-14 21:36 ` [PATCH] Speed-up pfifo_fast lookup using a bitmap Jarek Poplawski
2 siblings, 0 replies; 6+ messages in thread
From: Krishna Kumar @ 2009-08-14 13:25 UTC (permalink / raw)
To: Jarek Poplawski; +Cc: netdev, herbert, kaber, Krishna Kumar, davem
Signed-off-by: Krishna Kumar <krkumar2@in.ibm.com>
---
include/net/sch_generic.h | 1
net/sched/sch_generic.c | 46 +++++++++++++++++++++++-------------
2 files changed, 31 insertions(+), 16 deletions(-)
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;
}
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH v2] Speed-up pfifo_fast lookup using a private bitmap
2009-08-14 13:24 [PATCH] Speed-up pfifo_fast lookup using a bitmap Krishna Kumar
2009-08-14 13:25 ` [PATCH v1] Speed-up pfifo_fast lookup using a public bitmap Krishna Kumar
@ 2009-08-14 13:25 ` Krishna Kumar
2009-08-14 21:36 ` [PATCH] Speed-up pfifo_fast lookup using a bitmap Jarek Poplawski
2 siblings, 0 replies; 6+ messages in thread
From: Krishna Kumar @ 2009-08-14 13:25 UTC (permalink / raw)
To: Jarek Poplawski; +Cc: netdev, davem, herbert, Krishna Kumar, kaber
Signed-off-by: Krishna Kumar <krkumar2@in.ibm.com>
---
net/sched/sch_generic.c | 70 ++++++++++++++++++++++++++------------
1 file changed, 48 insertions(+), 22 deletions(-)
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:16.000000000 +0530
@@ -406,18 +406,38 @@ 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)
+/*
+ * Private data for a pfifo_fast scheduler containing:
+ * - the three band queues
+ * - bitmap indicating which of the bands contain skbs.
+ */
+struct pfifo_fast_priv {
+ u32 bitmap;
+ struct sk_buff_head q[PFIFO_FAST_BANDS];
+};
+
+/*
+ * 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 pfifo_fast_priv *priv,
+ int band)
{
- struct sk_buff_head *list = qdisc_priv(qdisc);
- return list + prio2band[skb->priority & TC_PRIO_MAX];
+ return priv->q + 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 pfifo_fast_priv *priv = qdisc_priv(qdisc);
+ struct sk_buff_head *list = band2list(priv, band);
if (skb_queue_len(list) < qdisc_dev(qdisc)->tx_queue_len) {
+ priv->bitmap |= (1 << band);
qdisc->q.qlen++;
return __qdisc_enqueue_tail(skb, qdisc, list);
}
@@ -427,14 +447,18 @@ 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);
+ struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
+ int band = bitmap2band[priv->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 = band2list(priv, band);
+ struct sk_buff *skb = __qdisc_dequeue_head(qdisc, list);
+
+ qdisc->q.qlen--;
+ if (skb_queue_empty(list))
+ priv->bitmap &= ~(1 << band);
+
+ return skb;
}
return NULL;
@@ -442,12 +466,13 @@ 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);
+ struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
+ int band = bitmap2band[priv->bitmap];
+
+ if (band >= 0) {
+ struct sk_buff_head *list = band2list(priv, band);
- for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
- if (!skb_queue_empty(list + prio))
- return skb_peek(list + prio);
+ return skb_peek(list);
}
return NULL;
@@ -456,11 +481,12 @@ static struct sk_buff *pfifo_fast_peek(s
static void pfifo_fast_reset(struct Qdisc* qdisc)
{
int prio;
- struct sk_buff_head *list = qdisc_priv(qdisc);
+ struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
- __qdisc_reset_queue(qdisc, list + prio);
+ __qdisc_reset_queue(qdisc, band2list(priv, prio));
+ priv->bitmap = 0;
qdisc->qstats.backlog = 0;
qdisc->q.qlen = 0;
}
@@ -480,17 +506,17 @@ nla_put_failure:
static int pfifo_fast_init(struct Qdisc *qdisc, struct nlattr *opt)
{
int prio;
- struct sk_buff_head *list = qdisc_priv(qdisc);
+ struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
- skb_queue_head_init(list + prio);
+ skb_queue_head_init(band2list(priv, prio));
return 0;
}
static struct Qdisc_ops pfifo_fast_ops __read_mostly = {
.id = "pfifo_fast",
- .priv_size = PFIFO_FAST_BANDS * sizeof(struct sk_buff_head),
+ .priv_size = sizeof(struct pfifo_fast_priv),
.enqueue = pfifo_fast_enqueue,
.dequeue = pfifo_fast_dequeue,
.peek = pfifo_fast_peek,
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap
2009-08-14 13:24 [PATCH] Speed-up pfifo_fast lookup using a bitmap Krishna Kumar
2009-08-14 13:25 ` [PATCH v1] Speed-up pfifo_fast lookup using a public bitmap Krishna Kumar
2009-08-14 13:25 ` [PATCH v2] Speed-up pfifo_fast lookup using a private bitmap Krishna Kumar
@ 2009-08-14 21:36 ` Jarek Poplawski
2009-08-18 2:03 ` David Miller
2 siblings, 1 reply; 6+ messages in thread
From: Jarek Poplawski @ 2009-08-14 21:36 UTC (permalink / raw)
To: Krishna Kumar; +Cc: kaber, netdev, davem, herbert
On Fri, Aug 14, 2009 at 06:54:58PM +0530, Krishna Kumar wrote:
> ďťżHi Jarek,
>
> Jarek Poplawski <jarkao2@gmail.com> wrote on 08/14/2009 04:31:27 PM:
>
> > Alas, private or public, these values are lower on average than
> > before, so I'm not sure the complexity (especially in reading) added
> > by this patch is worth it. So, I can only say it looks formally OK,
> > except the changelog and maybe 2 cosmetical suggestions below.
>
> Maybe the different test parameters result in smaller improvements.
> I agree with you - the first approach is very readable and probably
> preferable, while the second introduces a new structure and more
> complexity.
Actually, I meant the complexity added by any of these versions. If
you declare: "This helps in faster lookup for a skb when there are no
high priority skbs.", there is a question if less than 1% is enough.
> I am sending both these versions a last time, after fixing your
> comments in case someone can help decide if one or the other is
> better (sorry I forgot to run checkpatch couple of times, will try
> to remember next time).
I definitely can't see a reason to make this variable public, and
prefer the private (v2) version (which still lacks a changelog, btw).
Thanks,
Jarek P.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap
2009-08-14 21:36 ` [PATCH] Speed-up pfifo_fast lookup using a bitmap Jarek Poplawski
@ 2009-08-18 2:03 ` David Miller
2009-08-18 16:46 ` Krishna Kumar2
0 siblings, 1 reply; 6+ messages in thread
From: David Miller @ 2009-08-18 2:03 UTC (permalink / raw)
To: jarkao2; +Cc: krkumar2, kaber, netdev, herbert
From: Jarek Poplawski <jarkao2@gmail.com>
Date: Fri, 14 Aug 2009 23:36:43 +0200
> I definitely can't see a reason to make this variable public, and
> prefer the private (v2) version (which still lacks a changelog, btw).
I'm fine with patch v2, but yes it needs to be properly submitted
with a real changelog before I can apply it :-)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap
2009-08-18 2:03 ` David Miller
@ 2009-08-18 16:46 ` Krishna Kumar2
0 siblings, 0 replies; 6+ messages in thread
From: Krishna Kumar2 @ 2009-08-18 16:46 UTC (permalink / raw)
To: netdev
Sorry about the delay, I am sick with the flu for the last few days.
I will send the patch tomorrow.
thanks,
- KK
David Miller <davem@davemloft.net> wrote on 08/18/2009 07:33:43 AM:
> David Miller <davem@davemloft.net>
> 08/18/2009 07:33 AM
>
> To
>
> jarkao2@gmail.com
>
> cc
>
> Krishna Kumar2/India/IBM@IBMIN, kaber@trash.net, netdev@vger.kernel.org,
> herbert@gondor.apana.org.au
>
> Subject
>
> Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap
>
> From: Jarek Poplawski <jarkao2@gmail.com>
> Date: Fri, 14 Aug 2009 23:36:43 +0200
>
> > I definitely can't see a reason to make this variable public, and
> > prefer the private (v2) version (which still lacks a changelog, btw).
>
> I'm fine with patch v2, but yes it needs to be properly submitted
> with a real changelog before I can apply it :-)
^ permalink raw reply [flat|nested] 6+ messages in thread