[PATCH v3] net_sched: sch_sfq: fix allot handling

[Eric Dumazet <eric.dumazet@gmail.com>]

Le mercredi 15 décembre 2010 à 18:21 +0100, Patrick McHardy a écrit :
> On 15.12.2010 18:09, Eric Dumazet wrote:
> > Le mercredi 15 décembre 2010 à 18:03 +0100, Patrick McHardy a écrit :
> > 
> >> Right, that's odd. It shouldn't be necessary anymore though since
> >> now we initialize allot in sfq_enqueue() for all new flows and
> >> increase allotment for all active flows once per round in sfq_dequeue().
> >> The above code causes a second increase for the flow following a flow
> >> which went inactive.
> > 
> > Well, we do this in three places. Each time we 'select' a flow as the
> > next packet provider, we increase its allot by quantum.
> > 
> > We could change this, adding quantum to the current slot when its allot
> > becomes negative (and we select the next slot for next round)
> 
> Right, I again missed that 'a' refers to the next flow in the second
> condition in sfq_dequeue().
> 
> I have to run now, will have another look at this tommorrow.

Here is v3 : Now we add a quantum only when current flow consumed all
its allot, not "in advance for next slot". this should use less cpu too.

Thanks

[PATCH v3] net_sched: sch_sfq: fix allot handling

When deploying SFQ/IFB here at work, I found the allot management was
pretty wrong in sfq, even changing allot from short to int...

We should init allot for each new flow, not using a previous value found
in slot.

Before patch, I saw bursts of several packets per flow, apparently
denying the default "quantum 1514" limit I had on my SFQ class.

class sfq 11:1 parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 7p requeues 0 
 allot 11546 

class sfq 11:46 parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 1p requeues 0 
 allot -23873 

class sfq 11:78 parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 5p requeues 0 
 allot 11393 

After patch, better fairness among each flow, allot limit being
respected, allot is positive :

class sfq 11:e parent 11: 
 (dropped 0, overlimits 0 requeues 86) 
 backlog 0b 3p requeues 86 
 allot 596 

class sfq 11:94 parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 3p requeues 0 
 allot 1468 

class sfq 11:a4 parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 4p requeues 0 
 allot 650 

class sfq 11:bb parent 11: 
 (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 3p requeues 0 
 allot 596 

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
 net/sched/sch_sfq.c |   20 ++++++++------------
 1 files changed, 8 insertions(+), 12 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 3cf478d..7150705 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -270,7 +270,6 @@ static unsigned int sfq_drop(struct Qdisc *sch)
 		/* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
 		d = q->next[q->tail];
 		q->next[q->tail] = q->next[d];
-		q->allot[q->next[d]] += q->quantum;
 		skb = q->qs[d].prev;
 		len = qdisc_pkt_len(skb);
 		__skb_unlink(skb, &q->qs[d]);
@@ -321,14 +320,13 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 	sfq_inc(q, x);
 	if (q->qs[x].qlen == 1) {		/* The flow is new */
 		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
-			q->tail = x;
 			q->next[x] = x;
-			q->allot[x] = q->quantum;
 		} else {
 			q->next[x] = q->next[q->tail];
 			q->next[q->tail] = x;
-			q->tail = x;
 		}
+		q->tail = x;
+		q->allot[x] = q->quantum;
 	}
 	if (++sch->q.qlen <= q->limit) {
 		sch->bstats.bytes += qdisc_pkt_len(skb);
@@ -359,13 +357,13 @@ sfq_dequeue(struct Qdisc *sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
 	struct sk_buff *skb;
-	sfq_index a, old_a;
+	sfq_index a, next_a;
 
 	/* No active slots */
 	if (q->tail == SFQ_DEPTH)
 		return NULL;
 
-	a = old_a = q->next[q->tail];
+	a = q->next[q->tail];
 
 	/* Grab packet */
 	skb = __skb_dequeue(&q->qs[a]);
@@ -376,17 +374,15 @@ sfq_dequeue(struct Qdisc *sch)
 	/* Is the slot empty? */
 	if (q->qs[a].qlen == 0) {
 		q->ht[q->hash[a]] = SFQ_DEPTH;
-		a = q->next[a];
-		if (a == old_a) {
+		next_a = q->next[a];
+		if (a == next_a) {
 			q->tail = SFQ_DEPTH;
 			return skb;
 		}
-		q->next[q->tail] = a;
-		q->allot[a] += q->quantum;
+		q->next[q->tail] = next_a;
 	} else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
-		q->tail = a;
-		a = q->next[a];
 		q->allot[a] += q->quantum;
+		q->tail = a;
 	}
 	return skb;
 }