Skip to contentSkip to conversation

Speed-up pfifo_fast lookup using a bitmap

PATCH Superseded Krishna Kumar 3 participants 6 messages Aug 14, 2009 – Aug 18, 2009

Subsystems (3)
Networking Network drivers Traffic control (tc)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Krishna Kumar

author
#0 lore raw

Hi Jarek,

Jarek Poplawski <[email protected]> wrote on 08/14/2009 04:31:27 PM:

Quoted 4 lines

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

author
#1 lore raw

PATCH 1/1 Speed-up pfifo_fast lookup using a public bitmap

Signed-off-by Krishna Kumar <[email protected]>

---

 include/net/sch_generic.h |    1 
 net/sched/sch_generic.c   |   46 +++++++++++++++++++++++-------------
 2 files changed, 31 insertions(+), 16 deletions(-)
include/net/sch_generic.h +1 -0
diff -ruNp org/include/net/sch_generic.h new/include/net/sch_generic.h
@@ -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;
net/sched/sch_generic.c +30 -16

80 lines not on this page · raw message

author
#2 lore raw

PATCH v2 1/1 Speed-up pfifo_fast lookup using a private bitmap

In reply to Krishna Kumar
Signed-off-by Krishna Kumar <[email protected]>

---

 net/sched/sch_generic.c |   70 ++++++++++++++++++++++++++------------
 1 file changed, 48 insertions(+), 22 deletions(-)
net/sched/sch_generic.c +48 -22
diff -ruNp org/net/sched/sch_generic.c new/net/sched/sch_generic.c
@@ -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,
#3 lore raw
In reply to Krishna Kumar
Quoted 9 lines · Krishna Kumar

ďťżHi Jarek,

Jarek Poplawski <[email protected]> wrote on 08/14/2009 04:31:27 PM:

Quoted 4 lines

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.

Quoted 4 lines

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.

Quoted 4 lines

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.

maintainer
#4 lore raw

From: Jarek Poplawski <[email protected]>
Date: Fri, 14 Aug 2009 23:36:43 +0200

Quoted 2 lines

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

author
#5 lore raw

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 <[email protected]> wrote on 08/18/2009 07:33:43 AM:

Quoted 24 lines

David Miller <[email protected]>
08/18/2009 07:33 AM

To

[email protected]

cc

Krishna Kumar2/India/IBM@IBMIN, [email protected], [email protected], [email protected]

Subject

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

From: Jarek Poplawski <[email protected]>
Date: Fri, 14 Aug 2009 23:36:43 +0200

Quoted 2 lines

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