SFQ qdisc crashes with limit of 2 packets

SFQ qdisc crashes with limit of 2 packets

[Chuck Ebbert]

Limit of 1 is forbidden, crashes with 2, works with 3:

https://bugzilla.redhat.com/show_bug.cgi?id=219895

=========

If the defect is produced at a console (as in ctrl-alt-f<0-6>) a kernel stack
trace can be seen the moment "ping" is invoked.  Since the stack trace is not
 written to the /var/log/messages here's part of it (manually copied):
  syscall_call(()
    sys_socketcall()
      sys_sendmsg()
        sock_sendmsg()
          inet_sendmsg()
            raw_sendmsg()      
              ip_push_pending_frames()
                ip_output()
                  neigh_resolve_output()
                    dev_queue_xmit()
                      __qdisc_run()
The location given in __qdisc_run() is 0x30/0x19b.  The value given for EIP is
sfq_dequeue+0xf6/0x179 in the sch_sfq module.

>From disassembling sch_sfq.ko it seems that it is on line 360 of sch_sfq.c:
    sch->qstats.backlog -= skb->len;
where "skb" is an invalid pointer:
    net/sched/sch_sfq.c:360
 194:   ff 4d 28                decl   0x28(%ebp)
 197:   8b 14 24                mov    (%esp),%edx
 19a:   8b 42 60                mov    0x60(%edx),%eax ** crash **
 19d:   29 45 58                sub    %eax,0x58(%ebp)

Re: SFQ qdisc crashes with limit of 2 packets

[Patrick McHardy]

Chuck Ebbert wrote:
> Limit of 1 is forbidden, crashes with 2, works with 3:
> 
>>From disassembling sch_sfq.ko it seems that it is on line 360 of sch_sfq.c:
>     sch->qstats.backlog -= skb->len;
> where "skb" is an invalid pointer:


Is it a NULL pointer or something random?

Re: SFQ qdisc crashes with limit of 2 packets

[Patrick McHardy]

Patrick McHardy wrote:
> Chuck Ebbert wrote:
> 
>>Limit of 1 is forbidden, crashes with 2, works with 3:
>>
>>>From disassembling sch_sfq.ko it seems that it is on line 360 of sch_sfq.c:
>>    sch->qstats.backlog -= skb->len;
>>where "skb" is an invalid pointer:
> 
> 
> 
> Is it a NULL pointer or something random?


Never mind, I found the reason. When enqueuing the packet, sfq_enqueue
contains an off-by-one in the limit check (which IIRC is there for a
reason, but I can't remember right now) and drops the packet again.
dev_queue_xmit() calls qdisc_run() anyway and the empty qdisc is
dequeued, which is not handled by SFQ.

I see three possibilities to fix this (in my preferred order):

1) figure out why the off-by-one is there, if not needed remove
2) don't dequeue qdiscs even once if empty
3) check for NULL in sfq_dequeue

So I'll try to remeber why the off-by-one is there ..

Re: SFQ qdisc crashes with limit of 2 packets

[Patrick McHardy]

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

Patrick McHardy wrote:
> Never mind, I found the reason. When enqueuing the packet, sfq_enqueue
> contains an off-by-one in the limit check (which IIRC is there for a
> reason, but I can't remember right now) and drops the packet again.
> dev_queue_xmit() calls qdisc_run() anyway and the empty qdisc is
> dequeued, which is not handled by SFQ.
> 
> I see three possibilities to fix this (in my preferred order):
> 
> 1) figure out why the off-by-one is there, if not needed remove
> 2) don't dequeue qdiscs even once if empty
> 3) check for NULL in sfq_dequeue
> 
> So I'll try to remeber why the off-by-one is there ..


OK the off-by-one prevents an out-of-bounds array access, which
would cause a crash itself. Despite what I said above, sfq does
try to handle dequeues while empty, but forgets to update q->tail
when dropping the last packet from the only active queue, probably
because it wasn't expected that the queue length is too small to
queue even a single packet (and that really doesn't make much sense).

So one possibility for fixing this is to update q->tail in sfq_drop
when dropping the last packet, but that would still leave the qdisc
non-functional because of the off-by-one. I chose a different way:
cap the limit at SFQ_DEPTH-1 and remove the off-by-one, which should
have no effect on the max (still 127), but prevents the crash since
we can now queue at least a single packet and q->tail is properly
updated in sfq_dequeue().

CCed Alexey just to be safe, but I think the patch should be fine.

Signed-off-by: Patrick McHardy <kaber@trash.net>

[-- Attachment #2: y --]
[-- Type: text/plain, Size: 1347 bytes --]

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 9579573..cbf8089 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -270,7 +270,7 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 			q->tail = x;
 		}
 	}
-	if (++sch->q.qlen < q->limit-1) {
+	if (++sch->q.qlen < q->limit) {
 		sch->bstats.bytes += skb->len;
 		sch->bstats.packets++;
 		return 0;
@@ -306,7 +306,7 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 			q->tail = x;
 		}
 	}
-	if (++sch->q.qlen < q->limit - 1) {
+	if (++sch->q.qlen < q->limit) {
 		sch->qstats.requeues++;
 		return 0;
 	}
@@ -391,10 +391,10 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 	q->perturb_period = ctl->perturb_period*HZ;
 	if (ctl->limit)
-		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
+		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 
 	qlen = sch->q.qlen;
-	while (sch->q.qlen >= q->limit-1)
+	while (sch->q.qlen >= q->limit)
 		sfq_drop(sch);
 	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 
@@ -423,7 +423,7 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 	}
-	q->limit = SFQ_DEPTH;
+	q->limit = SFQ_DEPTH - 1;
 	q->max_depth = 0;
 	q->tail = SFQ_DEPTH;
 	if (opt == NULL) {

Re: SFQ qdisc crashes with limit of 2 packets

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Tue, 18 Sep 2007 21:15:28 +0200

> OK the off-by-one prevents an out-of-bounds array access, which
> would cause a crash itself. Despite what I said above, sfq does
> try to handle dequeues while empty, but forgets to update q->tail
> when dropping the last packet from the only active queue, probably
> because it wasn't expected that the queue length is too small to
> queue even a single packet (and that really doesn't make much sense).
> 
> So one possibility for fixing this is to update q->tail in sfq_drop
> when dropping the last packet, but that would still leave the qdisc
> non-functional because of the off-by-one. I chose a different way:
> cap the limit at SFQ_DEPTH-1 and remove the off-by-one, which should
> have no effect on the max (still 127), but prevents the crash since
> we can now queue at least a single packet and q->tail is properly
> updated in sfq_dequeue().
> 
> CCed Alexey just to be safe, but I think the patch should be fine.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

I've applied this to net-2.6, thanks Patrick.

I'll hold off merging this to Linus until later today so
that if some issue is found we can address it.

Thanks.

Re: SFQ qdisc crashes with limit of 2 packets

[Alexey Kuznetsov]

Hello!

> OK the off-by-one prevents an out-of-bounds array access,

Yes, this is not off-by-one (off-by-two, to be more exact :-)).

Maximal queue length is really limited by SFQ_DEPTH-2, because:

1. SFQ keeps list of queue lengths in array of length SFQ_DEPTH.
   This means length of queue must be in range 0..SFQ_DEPTH-1.

2. SFQ enqueues incoming packet first, and drops something after this.
   This means it always needs a free slot in queue. So, SFQ_DEPTH-2.


> CCed Alexey just to be safe, but I think the patch should be fine.

Yes. But what'a about limit == 1? tc prohibits this case, but it is still
not nice to have the bug in kernel. Plus, code remains creepy, the check

+	if (++sch->q.qlen < q->limit) {

still looks as a scary off-by-one. I would go all the way: replace this
with natural:

	if (++sch->q.qlen <= q->limit) {

and maxed q->limit at SFQ_DEPTH-2. Patch enclosed.


Seems, it is easy to relax the limit to SFQ_DEPTH-1, item #2 is an artificial
limitation. If current queue already has SFQ_DEPTH-1 packets, we can
drop from tail of this queue and skip update of all the state. It is even
an optimization for the case when we have single flow. I am not 100% sure
about this, I'll try and report.



diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 9579573..cbf8089 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -270,7 +270,7 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 			q->tail = x;
 		}
 	}
-	if (++sch->q.qlen < q->limit-1) {
+	if (++sch->q.qlen <= q->limit) {
 		sch->bstats.bytes += skb->len;
 		sch->bstats.packets++;
 		return 0;
@@ -306,7 +306,7 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 			q->tail = x;
 		}
 	}
-	if (++sch->q.qlen < q->limit - 1) {
+	if (++sch->q.qlen <= q->limit) {
 		sch->qstats.requeues++;
 		return 0;
 	}
@@ -391,10 +391,10 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 	q->perturb_period = ctl->perturb_period*HZ;
 	if (ctl->limit)
-		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH);
+		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 2);
 
 	qlen = sch->q.qlen;
-	while (sch->q.qlen >= q->limit-1)
+	while (sch->q.qlen > q->limit)
 		sfq_drop(sch);
 	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 
@@ -423,7 +423,7 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 	}
-	q->limit = SFQ_DEPTH;
+	q->limit = SFQ_DEPTH - 2;
 	q->max_depth = 0;
 	q->tail = SFQ_DEPTH;
 	if (opt == NULL) {

Re: SFQ qdisc crashes with limit of 2 packets

[Patrick McHardy]

Alexey Kuznetsov wrote:
> Hello!
> 
>>CCed Alexey just to be safe, but I think the patch should be fine.
> 
> 
> Yes. But what'a about limit == 1? tc prohibits this case, but it is still
> not nice to have the bug in kernel. Plus, code remains creepy, the check
> 
> +	if (++sch->q.qlen < q->limit) {
> 
> still looks as a scary off-by-one. I would go all the way: replace this
> with natural:
> 
> 	if (++sch->q.qlen <= q->limit) {
> 
> and maxed q->limit at SFQ_DEPTH-2. Patch enclosed.


Thats even better, thanks :)

Re: SFQ qdisc crashes with limit of 2 packets

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Wed, 19 Sep 2007 15:08:22 +0200

> Alexey Kuznetsov wrote:
> > Hello!
> > 
> >>CCed Alexey just to be safe, but I think the patch should be fine.
> > 
> > 
> > Yes. But what'a about limit == 1? tc prohibits this case, but it is still
> > not nice to have the bug in kernel. Plus, code remains creepy, the check
> > 
> > +	if (++sch->q.qlen < q->limit) {
> > 
> > still looks as a scary off-by-one. I would go all the way: replace this
> > with natural:
> > 
> > 	if (++sch->q.qlen <= q->limit) {
> > 
> > and maxed q->limit at SFQ_DEPTH-2. Patch enclosed.
> 
> Thats even better, thanks :)

I'll put this into my tree and wait while Alexey does his tests.

Thanks.

Re: SFQ qdisc crashes with limit of 2 packets

[Alexey Kuznetsov]

Hello!

Remove artificial limitation for sfq queue limit.

This is followup to Patrick's patch. A little optimization to enqueue
routine allows to remove artificial limitation on queue length.

Plus, testing showed that hash function used by SFQ is too bad or even worse.
It does not even sweep the whole range of hash values.
Switched to Jenkins' hash.


Signed-off-by: Alexey Kuznetsov <kaber@ms2.inr.ac.ru>


diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 3a23e30..b542c87 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -19,6 +19,7 @@
 #include <linux/init.h>
 #include <linux/ipv6.h>
 #include <linux/skbuff.h>
+#include <linux/jhash.h>
 #include <net/ip.h>
 #include <net/netlink.h>
 #include <net/pkt_sched.h>
@@ -95,7 +96,7 @@ struct sfq_sched_data
 
 /* Variables */
 	struct timer_list perturb_timer;
-	int		perturbation;
+	u32		perturbation;
 	sfq_index	tail;		/* Index of current slot in round */
 	sfq_index	max_depth;	/* Maximal depth */
 
@@ -109,12 +110,7 @@ struct sfq_sched_data
 
 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
 {
-	int pert = q->perturbation;
-
-	/* Have we any rotation primitives? If not, WHY? */
-	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
-	h ^= h>>10;
-	return h & 0x3FF;
+	return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
 }
 
 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
@@ -256,6 +252,13 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 		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 (q->qs[x].qlen >= q->limit)
+		return qdisc_drop(skb, sch);
+
 	sch->qstats.backlog += skb->len;
 	__skb_queue_tail(&q->qs[x], skb);
 	sfq_inc(q, x);
@@ -294,6 +297,19 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 	}
 	sch->qstats.backlog += skb->len;
 	__skb_queue_head(&q->qs[x], skb);
+	/* If selected queue has length q->limit+1, this means that
+	 * all another queues are empty and we do simple tail drop.
+	 * This packet is still requeued at head of queue, tail packet
+	 * is dropped.
+	 */
+	if (q->qs[x].qlen > q->limit) {
+		skb = q->qs[x].prev;
+		__skb_unlink(skb, &q->qs[x]);
+		sch->qstats.drops++;
+		sch->qstats.backlog -= skb->len;
+		kfree_skb(skb);
+		return NET_XMIT_CN;
+	}
 	sfq_inc(q, x);
 	if (q->qs[x].qlen == 1) {		/* The flow is new */
 		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
@@ -370,12 +386,10 @@ static void sfq_perturbation(unsigned long arg)
 	struct Qdisc *sch = (struct Qdisc*)arg;
 	struct sfq_sched_data *q = qdisc_priv(sch);
 
-	q->perturbation = net_random()&0x1F;
+	get_random_bytes(&q->perturbation, 4);
 
-	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
-		add_timer(&q->perturb_timer);
-	}
+	if (q->perturb_period)
+		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
 }
 
 static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
@@ -391,7 +405,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
 	q->perturb_period = ctl->perturb_period*HZ;
 	if (ctl->limit)
-		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 2);
+		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
 
 	qlen = sch->q.qlen;
 	while (sch->q.qlen > q->limit)
@@ -400,8 +414,8 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 
 	del_timer(&q->perturb_timer);
 	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
-		add_timer(&q->perturb_timer);
+		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
+		get_random_bytes(&q->perturbation, 4);
 	}
 	sch_tree_unlock(sch);
 	return 0;
@@ -423,12 +437,13 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 	}
-	q->limit = SFQ_DEPTH - 2;
+	q->limit = SFQ_DEPTH - 1;
 	q->max_depth = 0;
 	q->tail = SFQ_DEPTH;
 	if (opt == NULL) {
 		q->quantum = psched_mtu(sch->dev);
 		q->perturb_period = 0;
+		get_random_bytes(&q->perturbation, 4);
 	} else {
 		int err = sfq_change(sch, opt);
 		if (err)

Re: SFQ qdisc crashes with limit of 2 packets

[David Miller]

From: Alexey Kuznetsov <kuznet@ms2.inr.ac.ru>
Date: Fri, 21 Sep 2007 19:55:22 +0400

> Hello!
> 
> Remove artificial limitation for sfq queue limit.
> 
> This is followup to Patrick's patch. A little optimization to enqueue
> routine allows to remove artificial limitation on queue length.
> 
> Plus, testing showed that hash function used by SFQ is too bad or even worse.
> It does not even sweep the whole range of hash values.
> Switched to Jenkins' hash.
> 
> 
> Signed-off-by: Alexey Kuznetsov <kaber@ms2.inr.ac.ru>

Applied, thanks Alexey.