sch_sfq: fix queue limiting while enqueuing

[NET_SCHED] sch_sfq: fix queue limiting while enqueuing

Current way to use q->limit both as per flow and total queue limit doesn't make much sense. There would be no reason for sfq's limit parameter if the same could be done with ifconfig's txqueuelen, and it's too small for this anyway: with a number of flow queues around maximum (SFQ_DEPTH) each queue would be ~1 packet long, which means no queuing...

There is also changed a place for checking the total limit: let's do it at the beginning (like in pfifo_fast_enqueue()). IMHO current way is especially wrong during congestion: cpu & time costly classifying and enqueuing is done under queue_lock, to end with dropping of enqueued packets while adding newer ones. This means reordering and usually more resending. (I think, similar changes should be done in a few more qdiscs.)

---

 net/sched/sch_sfq.c |   29 +++++++++++++----------------
 1 files changed, 13 insertions(+), 16 deletions(-)

index a20e2ef..b4fd592 100644
@@ -283,6 +283,9 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 	sfq_index x;
 	int ret;
 
+	if (unlikely(sch->q.qlen >= max_t(__u32, sch->dev->tx_queue_len, 1)))
+		return qdisc_drop(skb, sch);
+
 	hash = sfq_classify(skb, sch, &ret);
 	if (hash == 0) {
 		if (ret == NET_XMIT_BYPASS)

@@ -319,14 +322,11 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 			q->tail = x;
 		}
 	}
-	if (++sch->q.qlen <= q->limit) {
-		sch->bstats.bytes += skb->len;
-		sch->bstats.packets++;
-		return 0;
-	}
 
-	sfq_drop(sch);
-	return NET_XMIT_CN;
+	sch->q.qlen++;
+	sch->bstats.bytes += skb->len;
+	sch->bstats.packets++;
+	return 0;
 }
 
 static int

@@ -337,6 +337,9 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc *sch)
 	sfq_index x;
 	int ret;
 
+	if (unlikely(sch->q.qlen >= max_t(__u32, sch->dev->tx_queue_len, 1)))
+		return qdisc_drop(skb, sch);
+
 	hash = sfq_classify(skb, sch, &ret);
 	if (hash == 0) {
 		if (ret == NET_XMIT_BYPASS)

@@ -381,14 +384,8 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc *sch)
 		}
 	}
 
-	if (++sch->q.qlen <= q->limit) {
-		sch->qstats.requeues++;
-		return 0;
-	}
-
-	sch->qstats.drops++;
-	sfq_drop(sch);
-	return NET_XMIT_CN;
+	sch->qstats.requeues++;
+	return 0;
 }
 
 

@@ -467,7 +464,7 @@ static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
 		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 
 	qlen = sch->q.qlen;
-	while (sch->q.qlen > q->limit)
+	while (q->max_depth > q->limit)
 		sfq_drop(sch);
 	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 

OK, you are right: it would break some scripts... But IMHO this way of treating tx_queue_len isn't right: it can be changed after initialization too, and looks like perfect way to control the queue size globally. Anyway, current use of "limit" parameter in sfq warps its idea. Another possibility would be like this:

sch->q.qlen >= max_t(__u32, sch->dev->tx_queue_len, q->limit)

or removing this global sch->q.qlen check at all. Or maybe we need to add one more tc parameter for sfq?

Thanks,
Jarek P.

I would go for a new parameter, tx_queue_len is not very well suited in my opinion since its global for the entire device, and most likely you don't want inner qdiscs to have the full tx_queue_length as limit but something smaller.

On Mon, Apr 28, 2008 at 04:02:01PM +0200, Patrick McHardy wrote:
...

Yes, a new parameter looks like the safest choice. I'll only have to re-think first the possible reason for this strange limit...

Thanks again,
Jarek P.

On Mon, Apr 28, 2008 at 04:58:37PM +0200, Jarek Poplawski wrote:
...

static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)

{
	sfq_index p, n;
	int d = q->qs[x].qlen + SFQ_DEPTH;

-------------------->^^^^^^^^

	p = d;
	n = q->dep[d].next;

...

So it's really by design! (I don't know why I missed this, and why it didn't break my lame test...)

Thanks again for stopping this disaster,
Jarek P.

On Tue, Apr 29, 2008 at 10:53:41PM +0200, Jarek Poplawski wrote:
...

...Hmm..., actually this is the place:

sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch) {
...

	x = q->ht[hash];
	if (x == SFQ_DEPTH) {
		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;

...

sfq counts on free slot always available here.

Regards,
Jarek P.

IIRC thats why the limit is capped at SFQ_DEPTH - 1.

David, as Patrick noticed this patch was wrong and I withdraw it.

I still can't see why sfq should have such a low limit, but I think, there is at least something to improve in the way it's imposed. BTW, my previous idea to check this before classifying was wrong too. But, IMHO, this could be done better than now like in this patch.

Regards,
Jarek P.

------------------------->

[NET_SCHED] sch_sfq: prevent unnecessary reordering

Current check of queue limit in sfq_enqueue() isn't optimal: there is really not much more needed to prevent unnecessary dropping and possible reordering.

---

 net/sched/sch_sfq.c |   17 ++++++++++++-----
 1 files changed, 12 insertions(+), 5 deletions(-)

index a20e2ef..9afef88 100644
@@ -298,12 +298,19 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 		q->hash[x] = hash;
 	}
 
-	/* If selected queue has length q->limit, this means that
-	 * all another queues are empty and that we do simple tail drop,
-	 * i.e. drop _this_ packet.
+	/*
+	 * If the queue is full some dropping is necessary. Let's check
+	 * whether this slot is to be selected to avoid reordering at
+	 * least. If max_depth == 1 (very unprobable) another slot could
+	 * be chosen to drop, but there is no reason to do this (and if
+	 * it were this slot yet the reordering would happen.)
 	 */
-	if (q->qs[x].qlen >= q->limit)
-		return qdisc_drop(skb, sch);
+	if (sch->q.qlen >= q->limit) {
+		sfq_index d = q->max_depth;
+
+		if ((d > 1 && x == q->dep[d + SFQ_DEPTH].next) || d == 1)
+			return qdisc_drop(skb, sch);
+	}
 
 	sch->qstats.backlog += skb->len;
 	__skb_queue_tail(&q->qs[x], skb);

From: Jarek Poplawski <[email protected]>
Date: Mon, 28 Apr 2008 09:04:53 +0000

Yes, I was following the discussion. But thanks for the confirmation :-)

...

I'll let Patrick review this one first, too.

David Miller wrote, On 04/28/2008 11:03 AM:
...

Very wise decision! (As usual.)

But, after rethinking, I've to withdraw this patch too. Sorry!

It looks like the patch could be quite right and should save sometimes a few cpu cycles, but the subject and the comment are wrong: it doesn't prevent reordering, but simply adding and later dropping the same packet. So, the gain is less than planned. (Anyway, if somebody thinks it's useful, I could resend it after changing...)

Thanks,
Jarek P.

It's a useful param which I use - on slow egress I can't see the point of queuing many seconds worth of traffic. It may also help keep stronger connections in check.

When shaping ingress it's essential to drop early to get out of slowstart before the far buffer gets too full.

Maybe it makes no difference in the long run, but if you drop and then enqueue a later packet the sender will get to know sooner so congestion control can do it's stuff.

Andy.

Andy Furniss wrote, On 04/28/2008 01:37 PM:

I agree the param is useful, but I can't see any technical reason why sfq can't do a bit more queuing sometimes - especially when we expect more flows/users per qdisc (probably another param would be necessary for this).

Happilly(?) it looks like my patch will not change here a lot...

Thanks for comments,
Jarek P.