Skip to contentSkip to conversation

pkt_sched: add DRR scheduler

PATCH Superseded Patrick McHardy 3 participants 20 messages Nov 19, 2008 – Nov 25, 2008

Subsystems (3)
Networking Network drivers Traffic control (tc)
lore
Share & tools
lore

Patrick McHardy

author
#0 lore raw

commit 9a2114f922015699b3b8402941f9e444f4a84369

Author: Patrick McHardy <[email protected]>
Date:   Wed Nov 19 15:25:03 2008 +0100

pkt_sched: add DRR scheduler

Add classful DRR scheduler as a more flexible replacement for SFQ.

The main difference to the algorithm described in "Efficient Fair Queueing using Deficit Round Robin" is that this implementation doesn't drop packets from the longest queue on overrun because its classful and limits are handled by each individual child qdisc.

Signed-off-by Patrick McHardy <[email protected]>
include/linux/pkt_sched.h +16 -0
index 5d921fa..e3f133a 100644
@@ -500,4 +500,20 @@ struct tc_netem_corrupt
 
 #define NETEM_DIST_SCALE	8192
 
+/* DRR */
+
+enum
+{
+	TCA_DRR_UNSPEC,
+	TCA_DRR_QUANTUM,
+	__TCA_DRR_MAX
+};
+
+#define TCA_DRR_MAX	(__TCA_DRR_MAX - 1)
+
+struct tc_drr_stats
+{
+	u32	deficit;
+};
+
 #endif
net/sched/Kconfig +11 -0
index 36543b6..ba31fe3 100644
@@ -194,6 +194,17 @@ config NET_SCH_NETEM
 
 	  If unsure, say N.
 
+config NET_SCH_DRR
+	tristate "Deficit round robing scheduler (DRR)"
+	help
+	  Say Y here if you want to use the Deficit round robin (DRR) packet
+	  scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_drr.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
index 70b35f8..54d950c 100644
@@ -30,6 +30,7 @@ obj-$(CONFIG_NET_SCH_PRIO)	+= sch_prio.o
 obj-$(CONFIG_NET_SCH_MULTIQ)	+= sch_multiq.o
 obj-$(CONFIG_NET_SCH_ATM)	+= sch_atm.o
 obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem.o
+obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
 obj-$(CONFIG_NET_CLS_FW)	+= cls_fw.o
net/sched/sch_drr.c new file +505 -0

505 lines not on this page · raw message

#1 lore raw

On 19-11-2008 15:26, Patrick McHardy wrote:

...

net/sched/Kconfig config NET_SCH_NETEM · line 198

Quoted 10 lines
net/sched/Kconfig +2 -0
index 36543b6..ba31fe3 100644
@@ -194,6 +194,17 @@ config NET_SCH_NETEM
 
 	  If unsure, say N.
 
+config NET_SCH_DRR
+	tristate "Deficit round robing scheduler (DRR)"

- tristate "Deficit round robing scheduler (DRR)"
+ tristate "Deficit Round Robin scheduler (DRR)"

net/sched/Kconfig config NET_SCH_NETEM · line 200

Quoted 2 lines
net/sched/Kconfig +2 -0
+	help
+	  Say Y here if you want to use the Deficit round robin (DRR) packet

- Say Y here if you want to use the Deficit round robin (DRR) packet
+ Say Y here if you want to use the Deficit Round Robin (DRR) packet

net/sched/Kconfig config NET_SCH_NETEM · line 201

Quoted 1 line
net/sched/Kconfig +1 -0
+	  scheduling algorithm.

Looks OK to me except checkpatch and documentation/example (any... even at the beginning of the program).

Jarek P.

author
#2 lore raw
Quoted 10 lines · Jarek Poplawski

Review

Quoted 3 lines · Patrick McHardy
(quoted diff) +2 -0
+config NET_SCH_DRR
+	tristate "Deficit round robing scheduler (DRR)"

- tristate "Deficit round robing scheduler (DRR)"
+ tristate "Deficit Round Robin scheduler (DRR)"

Thanks, I've fixed the typos.

Quoted 2 lines

Looks OK to me except checkpatch and documentation/example (any... even at the beginning of the program).

And the checkpatch errors.

Documentation for this in the kernel tree seems pretty useless though.

commit c6e712b1cf9446096159414cb9d7f8c58effe92f

Author: Patrick McHardy <[email protected]>
Date:   Thu Nov 20 12:39:18 2008 +0100

pkt_sched: add DRR scheduler

Add classful DRR scheduler as a more flexible replacement for SFQ.

The main difference to the algorithm described in "Efficient Fair Queueing using Deficit Round Robin" is that this implementation doesn't drop packets from the longest queue on overrun because its classful and limits are handled by each individual child qdisc.

Signed-off-by Patrick McHardy <[email protected]>
include/linux/pkt_sched.h +16 -0
index 5d921fa..e3f133a 100644
@@ -500,4 +500,20 @@ struct tc_netem_corrupt
 
 #define NETEM_DIST_SCALE	8192
 
+/* DRR */
+
+enum
+{
+	TCA_DRR_UNSPEC,
+	TCA_DRR_QUANTUM,
+	__TCA_DRR_MAX
+};
+
+#define TCA_DRR_MAX	(__TCA_DRR_MAX - 1)
+
+struct tc_drr_stats
+{
+	u32	deficit;
+};
+
 #endif
net/sched/Kconfig +11 -0
index 36543b6..4f7ef0d 100644
@@ -194,6 +194,17 @@ config NET_SCH_NETEM
 
 	  If unsure, say N.
 
+config NET_SCH_DRR
+	tristate "Deficit Round Robin scheduler (DRR)"
+	help
+	  Say Y here if you want to use the Deficit Round Robin (DRR) packet
+	  scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_drr.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
index 70b35f8..54d950c 100644
@@ -30,6 +30,7 @@ obj-$(CONFIG_NET_SCH_PRIO)	+= sch_prio.o
 obj-$(CONFIG_NET_SCH_MULTIQ)	+= sch_multiq.o
 obj-$(CONFIG_NET_SCH_ATM)	+= sch_atm.o
 obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem.o
+obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
 obj-$(CONFIG_NET_CLS_FW)	+= cls_fw.o
net/sched/sch_drr.c new file +505 -0

505 lines not on this page · raw message

#3 lore raw

On Thu, Nov 20, 2008 at 12:42:58PM +0100, Patrick McHardy wrote:
...

Quoted 1 line

Documentation for this in the kernel tree seems pretty useless though.

Right! What about iproute2 tree? (examples/?)

Jarek P.

author
#4 lore raw
Quoted 8 lines · Jarek Poplawski

On Thu, Nov 20, 2008 at 12:42:58PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

Documentation for this in the kernel tree seems pretty useless though.

Right! What about iproute2 tree? (examples/?)

Yes, I'll send something when I find some time (manpage probably).

Its trivial to use though, these is only a single optional parameter, the quantum.

#5 lore raw

On Thu, Nov 20, 2008 at 12:58:11PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

Its trivial to use though, these is only a single optional parameter, the quantum.

OK, but if you advertise this as a "flexible replacement for SFQ" sb. could be mislead, so I mean at least a simple example of such replacement.

Jarek P.

maintainer Applied
#6 lore raw
In reply to Patrick McHardy

From: Patrick McHardy <[email protected]>
Date: Thu, 20 Nov 2008 12:42:58 +0100

Quoted 6 lines

commit c6e712b1cf9446096159414cb9d7f8c58effe92f

Author: Patrick McHardy <[email protected]>
Date:   Thu Nov 20 12:39:18 2008 +0100

pkt_sched: add DRR scheduler

Quoted 8 lines

Add classful DRR scheduler as a more flexible replacement for SFQ.

The main difference to the algorithm described in "Efficient Fair Queueing using Deficit Round Robin" is that this implementation doesn't drop packets from the longest queue on overrun because its classful and limits are handled by each individual child qdisc.

Signed-off-by Patrick McHardy <[email protected]>

Applied, thanks Patrick.

#7 lore raw
In reply to Patrick McHardy

A small oversight:
----------------->
pkt_sched: sch_drr: Fix qlen in drr_drop()

Signed-off-by Jarek Poplawski <[email protected]>

---

 net/sched/sch_drr.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)
net/sched/sch_drr.c +1 -0
index 8d523d9..37e6ab9 100644
@@ -406,6 +406,7 @@ static unsigned int drr_drop(struct Qdisc *sch)
 		if (cl->qdisc->ops->drop) {
 			len = cl->qdisc->ops->drop(cl->qdisc);
 			if (len > 0) {
+				sch->q.qlen--;
 				if (cl->qdisc->q.qlen == 0)
 					list_del(&cl->alist);
 				return len;
#10 lore raw

PATCH 1/1 pkt_sched: sch_drr: Fix drr_dequeue() loop

In reply to Patrick McHardy

pkt_sched: sch_drr: Fix loop in drr_dequeue

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true exept the first time.

Signed-off-by Jarek Poplawski <[email protected]>

---

 net/sched/sch_drr.c |   24 +++++++++++++++++++++---
 1 files changed, 21 insertions(+), 3 deletions(-)
net/sched/sch_drr.c +21 -3
index 37e6ab9..ab75461 100644
@@ -369,12 +369,17 @@ static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 {
 	struct drr_sched *q = qdisc_priv(sch);
-	struct drr_class *cl;
+	struct drr_class *cl, *cl_first;
 	struct sk_buff *skb;
 	unsigned int len;
+	bool skb_waiting = false;
 
-	while (!list_empty(&q->active)) {
-		cl = list_first_entry(&q->active, struct drr_class, alist);
+	if (list_empty(&q->active))
+		return NULL;
+
+	cl_first = cl = list_first_entry(&q->active, struct drr_class, alist);
+
+	while (1) {
 		skb = cl->qdisc->ops->peek(cl->qdisc);
 		if (skb == NULL)
 			goto skip;

@@ -390,9 +395,22 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 		}
 
 		cl->deficit += cl->quantum;
+		skb_waiting = true;
 skip:
 		list_move_tail(&cl->alist, &q->active);
+		cl = list_first_entry(&q->active, struct drr_class, alist);
+
+		if (cl == cl_first) {
+			if (skb_waiting) {
+				/* next round of deficit refilling */
+				skb_waiting = false;
+			} else {
+				/* all qdiscs are non-work-conserving! */
+				break;
+			}
+		}
 	}
+
 	return NULL;
 }
#11 lore raw

PATCH v2 1/1 pkt_sched: sch_drr: Fix drr_dequeue() loop

In reply to Patrick McHardy

(Changelog fixed only)

pkt_sched: sch_drr: Fix drr_dequeue() loop

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true except the first time.

Signed-off-by Jarek Poplawski <[email protected]>

---

 net/sched/sch_drr.c |   24 +++++++++++++++++++++---
 1 files changed, 21 insertions(+), 3 deletions(-)
net/sched/sch_drr.c +21 -3
index 37e6ab9..ab75461 100644
@@ -369,12 +369,17 @@ static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 {
 	struct drr_sched *q = qdisc_priv(sch);
-	struct drr_class *cl;
+	struct drr_class *cl, *cl_first;
 	struct sk_buff *skb;
 	unsigned int len;
+	bool skb_waiting = false;
 
-	while (!list_empty(&q->active)) {
-		cl = list_first_entry(&q->active, struct drr_class, alist);
+	if (list_empty(&q->active))
+		return NULL;
+
+	cl_first = cl = list_first_entry(&q->active, struct drr_class, alist);
+
+	while (1) {
 		skb = cl->qdisc->ops->peek(cl->qdisc);
 		if (skb == NULL)
 			goto skip;

@@ -390,9 +395,22 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 		}
 
 		cl->deficit += cl->quantum;
+		skb_waiting = true;
 skip:
 		list_move_tail(&cl->alist, &q->active);
+		cl = list_first_entry(&q->active, struct drr_class, alist);
+
+		if (cl == cl_first) {
+			if (skb_waiting) {
+				/* next round of deficit refilling */
+				skb_waiting = false;
+			} else {
+				/* all qdiscs are non-work-conserving! */
+				break;
+			}
+		}
 	}
+
 	return NULL;
 }
author
#12 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 8 lines · Jarek Poplawski

(Changelog fixed only)

pkt_sched: sch_drr: Fix drr_dequeue() loop

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true except the first time.

Thanks for the report. I don't like to overcomplicate treatment of this broken configuration though, so this patch simply returns NULL when the inner qdiscs is non-work-conserving.

commit f995e708c778d5c3201d769ffae636f6941654ed

Author: Patrick McHardy <[email protected]>
Date:   Mon Nov 24 13:13:16 2008 +0100

pkt_sched: sch_drr: fix drr_dequeue loop()

Jarek Poplawski points out:

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true except the first time.

Using non-work-conserving qdiscs as children of DRR makes no sense, simply bail out in that case.

Reported-by Jarek Poplawski <[email protected]>
Signed-off-by Patrick McHardy <[email protected]>
net/sched/sch_drr.c +5 -3
index 37e6ab9..e7a7e87 100644
@@ -373,11 +373,13 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 	struct sk_buff *skb;
 	unsigned int len;
 
-	while (!list_empty(&q->active)) {
+	if (list_empty(&q->active))
+		goto out;
+	while (1) {
 		cl = list_first_entry(&q->active, struct drr_class, alist);
 		skb = cl->qdisc->ops->peek(cl->qdisc);
 		if (skb == NULL)
-			goto skip;
+			goto out;
 
 		len = qdisc_pkt_len(skb);
 		if (len <= cl->deficit) {

@@ -390,9 +392,9 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 		}
 
 		cl->deficit += cl->quantum;
-skip:
 		list_move_tail(&cl->alist, &q->active);
 	}
+out:
 	return NULL;
 }
#13 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 5 lines · Patrick McHardy
Quoted 4 lines · Jarek Poplawski

(Changelog fixed only)

pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 8 lines
Quoted 4 lines

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true except the first time.

Thanks for the report. I don't like to overcomplicate treatment of this broken configuration though, so this patch simply returns NULL when the inner qdiscs is non-work-conserving.

Hmm... I don't agree with treating this as broken (IIRC Denys Fedoryshchenko wrote about some case when he prefers TBF over HTB, and with DRR this could be an interesting alternative), but of course you are the author and I respect your decision.

Thanks,
Jarek P.

author
#14 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 10 lines · Jarek Poplawski
Quoted 9 lines · Patrick McHardy
Quoted 8 lines · Jarek Poplawski

(Changelog fixed only)

pkt_sched: sch_drr: Fix drr_dequeue() loop

If all child qdiscs of sch_drr are non-work-conserving (e.g. sch_tbf) drr_dequeue() will busy-loop waiting for skbs instead of leaving the job for a watchdog. Checking for list_empty() in each loop isn't necessary either, because this can never be true except the first time.

Quoted 8 lines
Quoted 3 lines

Thanks for the report. I don't like to overcomplicate treatment of this broken configuration though, so this patch simply returns NULL when the inner qdiscs is non-work-conserving.

Hmm... I don't agree with treating this as broken (IIRC Denys Fedoryshchenko wrote about some case when he prefers TBF over HTB, and with DRR this could be an interesting alternative), but of course you are the author and I respect your decision.

TBF with an inner DRR is fine. The other way around is broken in the sense that the behaviour is undefined.

#15 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

On Mon, Nov 24, 2008 at 01:38:48PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

TBF with an inner DRR is fine. The other way around is broken in the sense that the behaviour is undefined.

IMHO, this other way (e.g. a class with TBF per user), should work too.

BTW, since this "broken" config isn't very apparent, maybe you should add some warning?

Jarek P.

author
#16 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 6 lines · Jarek Poplawski

On Mon, Nov 24, 2008 at 01:38:48PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

TBF with an inner DRR is fine. The other way around is broken in the sense that the behaviour is undefined.

IMHO, this other way (e.g. a class with TBF per user), should work too.

The behaviour undefined, so what does "work too" mean in this context?

The main question is: what should be done with the class when it throttles?

You suggest moving it to the end of the active list. Should its deficit be recharged in that case? Possible no because it didn't send packets - but then again it might have handed out *some* packets (less than the deficit) before it started throttling. Both ways would introduce unfairness.

What could be done without harming the algorithm is to treat throttled classes as inactive until they become unthrottled again, meaning they would be added to the end of the active list with a full deficit. But we have no indication for specific classes, unthrottling simply triggers another dequeue of the root, so the implementation would get quite complicated, leaving alone the fact that each TBF would potentially start its own watchdog, causing excessive wakeups.

And I don't see much use for this, what is the advantage over using HTB or HFSC?

Quoted 2 lines

BTW, since this "broken" config isn't very apparent, maybe you should add some warning?

Yes, but I don't want to add this to the ->dequeue() path. It belongs in the ->init() path and we currently don't have enough information in there.

#17 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 27 lines · Patrick McHardy
Quoted 6 lines · Jarek Poplawski

On Mon, Nov 24, 2008 at 01:38:48PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

TBF with an inner DRR is fine. The other way around is broken in the sense that the behaviour is undefined.

IMHO, this other way (e.g. a class with TBF per user), should work too.

The behaviour undefined, so what does "work too" mean in this context?

The main question is: what should be done with the class when it throttles?

You suggest moving it to the end of the active list. Should its deficit be recharged in that case? Possible no because it didn't send packets - but then again it might have handed out *some* packets (less than the deficit) before it started throttling. Both ways would introduce unfairness.

What could be done without harming the algorithm is to treat throttled classes as inactive until they become unthrottled again, meaning they would be added to the end of the active list with a full deficit. But we have no indication for specific classes, unthrottling simply triggers another dequeue of the root, so the implementation would get quite complicated, leaving alone the fact that each TBF would potentially start its own watchdog, causing excessive wakeups.

Quoted 2 lines

And I don't see much use for this, what is the advantage over using HTB or HFSC?

Probably no advantage, if you now these things... or for testing. But I like to give users a choice, at least if it's not obviously wrong. Of course, if you think this harms the proper configs with too much overhead, then there is no question we should forget about this.

Jarek P.

maintainer
#18 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

From: Jarek Poplawski <[email protected]>
Date: Mon, 24 Nov 2008 13:45:16 +0000

Quoted 28 lines · Patrick McHardy
Quoted 27 lines
Quoted 6 lines · Jarek Poplawski

On Mon, Nov 24, 2008 at 01:38:48PM +0100, Patrick McHardy wrote:
...

Quoted 2 lines

TBF with an inner DRR is fine. The other way around is broken in the sense that the behaviour is undefined.

IMHO, this other way (e.g. a class with TBF per user), should work too.

The behaviour undefined, so what does "work too" mean in this context?

The main question is: what should be done with the class when it throttles?

You suggest moving it to the end of the active list. Should its deficit be recharged in that case? Possible no because it didn't send packets - but then again it might have handed out *some* packets (less than the deficit) before it started throttling. Both ways would introduce unfairness.

What could be done without harming the algorithm is to treat throttled classes as inactive until they become unthrottled again, meaning they would be added to the end of the active list with a full deficit. But we have no indication for specific classes, unthrottling simply triggers another dequeue of the root, so the implementation would get quite complicated, leaving alone the fact that each TBF would potentially start its own watchdog, causing excessive wakeups.

Quoted 7 lines
Quoted 2 lines

And I don't see much use for this, what is the advantage over using HTB or HFSC?

Probably no advantage, if you now these things... or for testing. But I like to give users a choice, at least if it's not obviously wrong. Of course, if you think this harms the proper configs with too much overhead, then there is no question we should forget about this.

Things seem to have settled, thus I have applied Patrick's version of the fix.

But I encourage people to add the necessary framework such that such unwanted configurations can be in fact detected at ->init() time and thus properly warned about.

Silent packet dropping really upsets users.

author
#19 lore raw

Re: [PATCH v2] pkt_sched: sch_drr: Fix drr_dequeue() loop

Quoted 2 lines · David Miller

Things seem to have settled, thus I have applied Patrick's version of the fix.

Thanks.

Quoted 5 lines

But I encourage people to add the necessary framework such that such unwanted configurations can be in fact detected at ->init() time and thus properly warned about.

Silent packet dropping really upsets users.

The packets won't be dropped, the qdisc will simply wait until the throttled inner qdisc becomes active again.

Refusing incorrect changes in ->init() is not easy because at least HFSC can switch between work-conserving and non-work-conserving through ->change(), so the upper qdisc would have to be able to perform validation before the change is made. This is additionally complicated by the fact that (in case of HFSC) it can't be determined by looking only at the class that is currently changed, the use of a upper-limit curve on any class makes it non-work-conserving.

Perhaps its best to ignore this special case and always treat HFSC as non-work-conserving, I haven't seen a configuration which uses a hierarchical qdisc as inner qdisc so far.