Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Krishna Kumar]

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.

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).

Thanks,

- KK

[PATCH v1] Speed-up pfifo_fast lookup using a public bitmap

[Krishna Kumar]

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;
 }

[PATCH v2] Speed-up pfifo_fast lookup using a private bitmap

[Krishna Kumar]

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,

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Jarek Poplawski]

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.

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[David Miller]

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 :-)

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Krishna Kumar2]

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 :-)

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Jarek Poplawski]

On Fri, Aug 14, 2009 at 01:49:07PM +0530, Krishna Kumar wrote:
> Jarek Poplawski <jarkao2@gmail.com> wrote on 08/13/2009 04:57:16 PM:
> 
> > > Sounds reasonable. To quantify that, I will test again for a longer
> > > run and report the difference.
> >
> > Yes, more numbers would be appreciated.
> 
> I did a longer 7-hour testing of original code, public bitmap (the
> code submitted earlier) and a private bitmap (patch below). Each
> result line is aggregate of 5 iterations of individual 1, 2, 4, 8,
> 32 netperf sessions, each running for 55 seconds:
> 
> -------------------------------------------------------
> IO Size     Org        Public          Private
> -------------------------------------------------------
> 4K          122571     126821          125913
> 16K         135715     135642          135530 
> 128K        131324     131862          131668
> 256K        130060     130107          130378
> -------------------------------------------------------
> Total:      519670     524433 (0.92%)  523491 (0.74%)
> -------------------------------------------------------
> 
> The difference between keeping the bitmap private and public is
> not much.

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.

> > > The tests are on the latest tree which contains CAN_BYPASS. So a
> > > single netperf process running this change will get no advantage
> > > since this enqueue/dequeue never happens unless the NIC is slow.
> > > But for multiple processes, it should help.
> > 
> > I mean: since the previous patch saved ~2% on omitting enqueue/dequeue,
> > and now enqueue/dequeue is ~2% faster, is it still worth to omit this?
> 
> I haven't tested the bitmap patch without the bypass code.
> Theoretically I assume that patch should help as we still save
> an enqueue/dequeue.
> 
> Thanks,
> 
> - KK
> 
> 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 new2/net/sched/sch_generic.c
> --- org/net/sched/sch_generic.c	2009-08-07 12:05:43.000000000 +0530
> +++ new2/net/sched/sch_generic.c	2009-08-14 12:48:37.000000000 +0530
> @@ -406,18 +406,38 @@ static const u8 prio2band[TC_PRIO_MAX+1]
...
> +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[0] + band;

	return priv->q + band;
seems more readable.

...
>  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),

checkpatch warns here, and it seems consistent with Documentation/
CodingStyle.

Thanks,
Jarek P.

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Krishna Kumar]

Jarek Poplawski <jarkao2@gmail.com> wrote on 08/13/2009 04:57:16 PM:

> > Sounds reasonable. To quantify that, I will test again for a longer
> > run and report the difference.
>
> Yes, more numbers would be appreciated.

I did a longer 7-hour testing of original code, public bitmap (the
code submitted earlier) and a private bitmap (patch below). Each
result line is aggregate of 5 iterations of individual 1, 2, 4, 8,
32 netperf sessions, each running for 55 seconds:

-------------------------------------------------------
IO Size     Org        Public          Private
-------------------------------------------------------
4K          122571     126821          125913
16K         135715     135642          135530 
128K        131324     131862          131668
256K        130060     130107          130378
-------------------------------------------------------
Total:      519670     524433 (0.92%)  523491 (0.74%)
-------------------------------------------------------

The difference between keeping the bitmap private and public is
not much.

> > The tests are on the latest tree which contains CAN_BYPASS. So a
> > single netperf process running this change will get no advantage
> > since this enqueue/dequeue never happens unless the NIC is slow.
> > But for multiple processes, it should help.
> 
> I mean: since the previous patch saved ~2% on omitting enqueue/dequeue,
> and now enqueue/dequeue is ~2% faster, is it still worth to omit this?

I haven't tested the bitmap patch without the bypass code.
Theoretically I assume that patch should help as we still save
an enqueue/dequeue.

Thanks,

- KK

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 new2/net/sched/sch_generic.c
--- org/net/sched/sch_generic.c	2009-08-07 12:05:43.000000000 +0530
+++ new2/net/sched/sch_generic.c	2009-08-14 12:48:37.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 bands.
+ * 	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[0] + 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,

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Jarek Poplawski]

On Thu, Aug 13, 2009 at 04:11:57PM +0530, Krishna Kumar2 wrote:
> > Jarek Poplawski <jarkao2@gmail.com>
> >
> > > but the test numbers came a little less, since it takes a few more
> > > memory references on enqueue/dequeue.
> >
> > If it's exactly "a little less" I'd consider keeping it private yet...
> 
> Sounds reasonable. To quantify that, I will test again for a longer
> run and report the difference.

Yes, more numbers would be appreciated.

> 
> > Btw, I wonder how much gain of your previous (_CAN_BYPASS) patch is
> > saved after this change...
> 
> The tests are on the latest tree which contains CAN_BYPASS. So a
> single netperf process running this change will get no advantage
> since this enqueue/dequeue never happens unless the NIC is slow.
> But for multiple processes, it should help.

I mean: since the previous patch saved ~2% on omitting enqueue/dequeue,
and now enqueue/dequeue is ~2% faster, is it still worth to omit this?

Regards,
Jarek P.

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Krishna Kumar2]

> Jarek Poplawski <jarkao2@gmail.com>
>
> > but the test numbers came a little less, since it takes a few more
> > memory references on enqueue/dequeue.
>
> If it's exactly "a little less" I'd consider keeping it private yet...

Sounds reasonable. To quantify that, I will test again for a longer
run and report the difference.

> Btw, I wonder how much gain of your previous (_CAN_BYPASS) patch is
> saved after this change...

The tests are on the latest tree which contains CAN_BYPASS. So a
single netperf process running this change will get no advantage
since this enqueue/dequeue never happens unless the NIC is slow.
But for multiple processes, it should help.

>  - * Convert a bitmap to the first band number where an skb is queue'd,
where:
>  + * Convert a bitmap to the first band number where an skb is queued,
where:
>
> > + *    bitmap=0 means there are no skbs for any bands
> > + *    bitmap=1 means there is a skb on band 0
>
>  - *    bitmap=1 means there is a skb on band 0
>  + *    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};
>
> Why wrapped?

cut-n-paste of prio2band, I will fix this and the above comments.

>
> ...
>  ... pfifo_fast_reset(...)
>  {
>    ...
> +   qdisc->bitmap = 0; ?
>  }

Correct. Thanks for pointing this out.

Regards,

- KK

Re: [PATCH] Speed-up pfifo_fast lookup using a bitmap

[Jarek Poplawski]

On Thu, Aug 13, 2009 at 12:58:18PM +0530, Krishna Kumar wrote:
> Maintain a per-qdisc bitmap indicating availability of skbs for
> each band. This helps in faster lookup for a skb when there are
> no high priority skbs. Also, it helps in (rare) cases where there
> are no skbs on the list where an immediate lookup helps rather
> than iterating through the three bands.
> 
> Another option I considered was to create a private qdisc pointer
> and avoid touching Qdisc structure:
> 	struct pfifo_fast_priv {
> 		unsigned long bitmap;
> 		struct sk_buff_head q[PFIFO_FAST_BANDS];
> 	};
> but the test numbers came a little less, since it takes a few more
> memory references on enqueue/dequeue.

If it's exactly "a little less" I'd consider keeping it private yet...

> 
> By keeping the bitmap in Qdisc, it is possible to implement the
> lookup for other schedulers, maybe sch_prio which goes through 16
> bands?
> 
> The BW numbers are average across 5 iterations for multiple
> netperf sessions (1-12 on x86_64, and 1-32 on P6) tested with
> Chelsio 10 gbps cards over a 2 hour run:
> 
> -------------------------------------------------------------------------
>      |         x86_64 (Mb/s)          |               P6 (Mb/s)
> --------------------------------------|----------------------------------
> Size |  ORG BW          NEW BW        |    ORG BW          NEW BW       
> -----|--------------------------------|----------------------------------
> 16K  |  157700          158237        |    153876          156696
> 64K  |  155916          157882        |    154176          155987
> 128K |  155122          155628        |    154983          155904
> 256K |  154808          158913        |    153898          155164
> -------------------------------------------------------------------------

Btw, I wonder how much gain of your previous (_CAN_BYPASS) patch is
saved after this change...

> 
> Thanks,
> 
> - KK
> 
> 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-07 19:35:16.000000000 +0530
> @@ -72,6 +72,7 @@ struct Qdisc
>  	 * For performance sake on SMP, we put highly modified fields at the end
>  	 */
>  	unsigned long		state;
> +	unsigned long		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-13 11:57:54.000000000 +0530
> @@ -406,18 +406,29 @@ 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 queue'd, where:

 - * Convert a bitmap to the first band number where an skb is queue'd, where:
 + * Convert a bitmap to the first band number where an skb is queued, where:

> + * 	bitmap=0 means there are no skbs for any bands
> + * 	bitmap=1 means there is a skb on band 0

 - * 	bitmap=1 means there is a skb on band 0
 + * 	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};

Why wrapped?

...
 ... pfifo_fast_reset(...)
 {
	...
+	qdisc->bitmap = 0; ?
 }

Thanks,
Jarek P.

[PATCH] Speed-up pfifo_fast lookup using a bitmap

[Krishna Kumar]

Maintain a per-qdisc bitmap indicating availability of skbs for
each band. This helps in faster lookup for a skb when there are
no high priority skbs. Also, it helps in (rare) cases where there
are no skbs on the list where an immediate lookup helps rather
than iterating through the three bands.

Another option I considered was to create a private qdisc pointer
and avoid touching Qdisc structure:
	struct pfifo_fast_priv {
		unsigned long bitmap;
		struct sk_buff_head q[PFIFO_FAST_BANDS];
	};
but the test numbers came a little less, since it takes a few more
memory references on enqueue/dequeue.

By keeping the bitmap in Qdisc, it is possible to implement the
lookup for other schedulers, maybe sch_prio which goes through 16
bands?

The BW numbers are average across 5 iterations for multiple
netperf sessions (1-12 on x86_64, and 1-32 on P6) tested with
Chelsio 10 gbps cards over a 2 hour run:

-------------------------------------------------------------------------
     |         x86_64 (Mb/s)          |               P6 (Mb/s)
--------------------------------------|----------------------------------
Size |  ORG BW          NEW BW        |    ORG BW          NEW BW       
-----|--------------------------------|----------------------------------
16K  |  157700          158237        |    153876          156696
64K  |  155916          157882        |    154176          155987
128K |  155122          155628        |    154983          155904
256K |  154808          158913        |    153898          155164
-------------------------------------------------------------------------

Thanks,

- KK

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-07 19:35:16.000000000 +0530
@@ -72,6 +72,7 @@ struct Qdisc
 	 * For performance sake on SMP, we put highly modified fields at the end
 	 */
 	unsigned long		state;
+	unsigned long		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-13 11:57:54.000000000 +0530
@@ -406,18 +406,29 @@ 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 queue'd, where:
+ * 	bitmap=0 means there are no skbs for any bands
+ * 	bitmap=1 means there is a 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 +438,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 +456,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;