[Fwd: [patch] fix slot clash in sch_sfq.c]

[Fwd: [patch] fix slot clash in sch_sfq.c]

[Miguel Freitas]

[-- Attachment #1: Type: text/plain, Size: 110 bytes --]

I better send a copy of this one to the mailing list...

please cc me, i'm not subscribed.

regards,

Miguel


[-- Attachment #2: Forwarded message - [patch] fix slot clash in sch_sfq.c --]
[-- Type: message/rfc822, Size: 2032 bytes --]

[-- Attachment #2.1.1: Type: text/plain, Size: 1062 bytes --]

Hi Alexey, Hi David,

I've found a slot "leak" in sch_sfq.c that occurs with current 2.4 and
2.6 kernels. After dequeueing the last skb from a given slot, this slot
might be reused by a different hash (say new_hash). However the old hash
(q->ht[old_hash]) still points to the (now) reused slot. When new skb's
arrive with old_hash they will be enqueued at the same slot as new_hash
skb's (that is, q->ht[old_hash] == q->ht[new_hash]).

This produce a "slot clash" (opposed to a "hash clash"), severely
affecting the effectiveness of SFQ to provide fairness.

The attached one line patch fixes it, freeing the slot when last skb is
dequeued.

Note: I've noticed this problem while testing a fixed hash function of
the IP. the number of active slots didn't matched the number of active
IP clients. I have created a small standalone application, using
sch_sfq.c, to reproduce and debug this problem. I may provide this
application and a small data set (sequence of enqueues/dequeues) that
trigger the problem, let me know if you need it.

regards,

Miguel Freitas


[-- Attachment #2.1.2: sfq-slot-clash-fix.patch --]
[-- Type: text/x-patch, Size: 279 bytes --]

--- sch_sfq.orig	2004-02-09 11:10:43.000000000 -0200
+++ sch_sfq.c	2004-02-11 02:32:06.000000000 -0200
@@ -338,6 +338,7 @@
 
 	/* 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) {
 			q->tail = SFQ_DEPTH;

Re: [Fwd: [patch] fix slot clash in sch_sfq.c]

[David S. Miller]

On Wed, 11 Feb 2004 18:47:41 -0200
Miguel Freitas <miguel@cetuc.puc-rio.br> wrote:

> I better send a copy of this one to the mailing list...

Your patch is correct.  It is amusing that sfq_drop() was handling
this correctly yet sfq_dequeue() was not.  In fact, this breaks
pretty seriously the behavior of this scheduler as you've noted.