Skip to contentSkip to conversation

SFQ qdisc crashes with limit of 2 packets

DISCUSSION Applied Chuck Ebbert 4 participants 10 messages Sep 18, 2007 – Oct 1, 2007

Subsystems (3)
Networking Network drivers Traffic control (tc)
lore
Share & tools
lore

Chuck Ebbert

author
#0 lore raw

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.

Quoted 1 line

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)
#1 lore raw
Quoted 5 lines · Chuck Ebbert

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

Quoted 1 line

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?

#2 lore raw
Quoted 11 lines · Patrick McHardy
Quoted 5 lines · Chuck Ebbert

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

Quoted 1 line

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

#3 lore raw
Quoted 6 lines · Patrick McHardy

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.

Quoted 7 lines

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 <[email protected]>
net/sched/sch_sfq.c +5 -5
index 9579573..cbf8089 100644
@@ -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) {
maintainer Applied
#4 lore raw

From: Patrick McHardy <[email protected]>
Date: Tue, 18 Sep 2007 21:15:28 +0200

Quoted 15 lines

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

Quoted 3 lines

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

Signed-off-by Patrick McHardy <[email protected]>

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.

#5 lore raw
In reply to Patrick McHardy

Hello!

Quoted 1 line

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.

Quoted 1 line

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.

net/sched/sch_sfq.c +5 -5
index 9579573..cbf8089 100644
@@ -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) {
#6 lore raw
Quoted 10 lines · Alexey Kuznetsov

Hello!

Quoted 1 line

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

(quoted diff) +1 -0
+	if (++sch->q.qlen < q->limit) {
Quoted 6 lines

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

maintainer
#7 lore raw

From: Patrick McHardy <[email protected]>
Date: Wed, 19 Sep 2007 15:08:22 +0200

Quoted 11 lines
Quoted 10 lines · Alexey Kuznetsov

Hello!

Quoted 1 line

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

(quoted diff) +1 -0
+	if (++sch->q.qlen < q->limit) {
Quoted 8 lines
Quoted 6 lines

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.

#8 lore raw
In reply to Patrick McHardy

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 <[email protected]>
net/sched/sch_sfq.c +31 -16
index 3a23e30..b542c87 100644
@@ -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)
maintainer Applied
#9 lore raw

From: Alexey Kuznetsov <[email protected]>
Date: Fri, 21 Sep 2007 19:55:22 +0400

Quoted 7 lines

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.

Quoted 6 lines

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 <[email protected]>

Applied, thanks Alexey.