[PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Jarek Poplawski]

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


Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

---

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

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index a20e2ef..b4fd592 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -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);
 

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Patrick McHardy]

Jarek Poplawski wrote:
> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
>
> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index a20e2ef..b4fd592 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -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);
> +
>   

I don't think we should do this. The tx_queue_len is only used for
initialization in case no parameter is specified by other qdiscs.

Besides this *will* break for example my configuration, I use SFQ
as inner qdisc on virtual devices with either tx_queue_len == 0
or 3 in case of ppp.

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Jarek Poplawski]

On Sun, Apr 27, 2008 at 08:29:44PM +0200, Patrick McHardy wrote:
> Jarek Poplawski wrote:
>> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
>>
>> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
>> index a20e2ef..b4fd592 100644
>> --- a/net/sched/sch_sfq.c
>> +++ b/net/sched/sch_sfq.c
>> @@ -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);
>> +
>>   
>
> I don't think we should do this. The tx_queue_len is only used for
> initialization in case no parameter is specified by other qdiscs.
>
> Besides this *will* break for example my configuration, I use SFQ
> as inner qdisc on virtual devices with either tx_queue_len == 0
> or 3 in case of ppp.

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.

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Patrick McHardy]

Jarek Poplawski wrote:
> On Sun, Apr 27, 2008 at 08:29:44PM +0200, Patrick McHardy wrote:
>> Jarek Poplawski wrote:
>>> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
>>>
>> Besides this *will* break for example my configuration, I use SFQ
>> as inner qdisc on virtual devices with either tx_queue_len == 0
>> or 3 in case of ppp.
> 
> 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?


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.

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Jarek Poplawski]

On Mon, Apr 28, 2008 at 04:02:01PM +0200, Patrick McHardy wrote:
...
> 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.

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. 

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Jarek Poplawski]

On Mon, Apr 28, 2008 at 04:58:37PM +0200, Jarek Poplawski 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...

  
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. 

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Jarek Poplawski]

On Tue, Apr 29, 2008 at 10:53:41PM +0200, Jarek Poplawski wrote:
...
> So it's really by design! (I don't know why I missed this, and why

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

Re: [PATCH][NET_SCHED] sch_sfq: fix queue limiting while enqueuing

[Patrick McHardy]

Jarek Poplawski wrote:
> On Tue, Apr 29, 2008 at 10:53:41PM +0200, Jarek Poplawski wrote:
> ...
>> So it's really by design! (I don't know why I missed this, and why
> 
> ...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.


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

[PATCH][NET_SCHED] sch_sfq: prevent unnecessary reordering

[Jarek Poplawski]

On 27-04-2008 16:22, Jarek Poplawski wrote:
> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
> 

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.


Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

---

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

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index a20e2ef..9afef88 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -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);

Re: [PATCH][NET_SCHED] sch_sfq: prevent unnecessary reordering

[David Miller]

From: Jarek Poplawski <jarkao2@gmail.com>
Date: Mon, 28 Apr 2008 09:04:53 +0000

> On 27-04-2008 16:22, Jarek Poplawski wrote:
> > [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
> > 
> 
> David, as Patrick noticed this patch was wrong and I withdraw it.

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

> 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.
 ...
> [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.
> 
> 
> Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>

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

Re: [PATCH][NET_SCHED] sch_sfq: prevent unnecessary reordering

[Jarek Poplawski]

David Miller wrote, On 04/28/2008 11:03 AM:
...
>> [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.
>>
>>
>> Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
> 
> I'll let Patrick review this one first, too.

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.

Re: [PATCH][NET_SCHED] sch_sfq: prevent unnecessary reordering

[Andy Furniss]

Jarek Poplawski wrote:
> On 27-04-2008 16:22, Jarek Poplawski wrote:
>> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
>>
> 
> 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,

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.


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

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.

Re: [PATCH][NET_SCHED] sch_sfq: prevent unnecessary reordering

[Jarek Poplawski]

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

> Jarek Poplawski wrote:
>> On 27-04-2008 16:22, Jarek Poplawski wrote:
>>> [NET_SCHED] sch_sfq: fix queue limiting while enqueuing
>>>
>> 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,
> 
> 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.

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

> When shaping ingress it's essential to drop early to get out of 
> slowstart before the far buffer gets too full.
> 
> 
>> [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.
> 
> 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.

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

Thanks for comments,
Jarek P.