[PATCH] netem: account for packets in delayed queue in qlen

[PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

Netem has a private queue for delayed packets, and currently, packets
in this queue are not accounted for in the qdisc qlen statistics.
This is a problem if netem is used inside another qdisc doing rate
control that peeks at the qlen.

This patch changes the statistics to include the packets held but
not ready to send.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2005-03-29 13:54:37 -08:00
+++ b/net/sched/sch_netem.c	2005-03-29 13:54:37 -08:00
@@ -152,9 +152,6 @@
 	/* Always queue at tail to keep packets in order */
 	if (likely(q->delayed.qlen < q->limit)) {
 		__skb_queue_tail(&q->delayed, skb);
-		sch->bstats.bytes += skb->len;
-		sch->bstats.packets++;
-
 		if (!timer_pending(&q->timer)) {
 			q->timer.expires = jiffies + PSCHED_US2JIFFIE(td);
 			add_timer(&q->timer);
@@ -162,7 +159,6 @@
 		return NET_XMIT_SUCCESS;
 	}
 
-	sch->qstats.drops++;
 	kfree_skb(skb);
 	return NET_XMIT_DROP;
 }
@@ -170,6 +166,8 @@
 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
+	struct sk_buff *skb2;
+	int ret;
 
 	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
 
@@ -182,12 +180,16 @@
 	}
 
 	/* Random duplication */
-	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) {
-		struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
-
+	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)
+	    && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
 		pr_debug("netem_enqueue: dup %p\n", skb2);
-		if (skb2)
-			delay_skb(sch, skb2);
+
+		if (delay_skb(sch, skb2)) {
+			sch->q.qlen++;
+			sch->bstats.bytes += skb2->len;
+			sch->bstats.packets++;
+		} else
+			sch->qstats.drops++;
 	}
 
 	/* If doing simple delay then gap == 0 so all packets
@@ -196,22 +198,21 @@
 	 * packets will be delayed.
 	 */
 	if (q->counter < q->gap) {
-		int ret;
-
 		++q->counter;
 		ret = q->qdisc->enqueue(skb, q->qdisc);
-		if (likely(ret == NET_XMIT_SUCCESS)) {
-			sch->q.qlen++;
-			sch->bstats.bytes += skb->len;
-			sch->bstats.packets++;
-		} else
-			sch->qstats.drops++;
-		return ret;
+	} else {
+		q->counter = 0;
+		ret = delay_skb(sch, skb);
 	}
-	
-	q->counter = 0;
 
-	return delay_skb(sch, skb);
+	if (likely(ret == NET_XMIT_SUCCESS)) {
+		sch->q.qlen++;
+		sch->bstats.bytes += skb->len;
+		sch->bstats.packets++;
+	} else
+		sch->qstats.drops++;
+
+	return ret;
 }
 
 /* Requeue packets but don't change time stamp */
@@ -283,10 +284,10 @@
 		}
 		__skb_unlink(skb, &q->delayed);
 
-		if (q->qdisc->enqueue(skb, q->qdisc))
+		if (q->qdisc->enqueue(skb, q->qdisc)) {
+			sch->q.qlen--;
 			sch->qstats.drops++;
-		else
-			sch->q.qlen++;
+		}
 	}
 	qdisc_run(dev);
 	spin_unlock_bh(&dev->queue_lock);

Re: [PATCH] netem: account for packets in delayed queue in qlen

[David S. Miller]

On Tue, 29 Mar 2005 15:21:10 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> Netem has a private queue for delayed packets, and currently, packets
> in this queue are not accounted for in the qdisc qlen statistics.
> This is a problem if netem is used inside another qdisc doing rate
> control that peeks at the qlen.
> 
> This patch changes the statistics to include the packets held but
> not ready to send.
> 
> Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

Both 2.4.x and 2.6.x variants applied, thanks Stephen.

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

Stephen Hemminger wrote:
> Netem has a private queue for delayed packets, and currently, packets
> in this queue are not accounted for in the qdisc qlen statistics.
> This is a problem if netem is used inside another qdisc doing rate
> control that peeks at the qlen.
> 
> This patch changes the statistics to include the packets held but
> not ready to send.

There is one troublesome spot left, netem_watchdog() decreases q.qlen
when the packet couldn't be enqueued. I don't think it is possible
to make netem useable as leaf-qdisc, it will always have to touch
q.qlen from timer context and classful qdiscs can't deal with this
since they all maintain their own q.qlen counters and expect changes
only in the +-1 range in enqueue/dequeue/requeue/drop. Best thing IMO
would be to refuse to work as anything but root qdisc.

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

On Tue, 05 Apr 2005 21:48:45 +0200
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> > Netem has a private queue for delayed packets, and currently, packets
> > in this queue are not accounted for in the qdisc qlen statistics.
> > This is a problem if netem is used inside another qdisc doing rate
> > control that peeks at the qlen.
> > 
> > This patch changes the statistics to include the packets held but
> > not ready to send.
> 
> There is one troublesome spot left, netem_watchdog() decreases q.qlen
> when the packet couldn't be enqueued. I don't think it is possible
> to make netem useable as leaf-qdisc, it will always have to touch
> q.qlen from timer context and classful qdiscs can't deal with this
> since they all maintain their own q.qlen counters and expect changes
> only in the +-1 range in enqueue/dequeue/requeue/drop. Best thing IMO
> would be to refuse to work as anything but root qdisc.

But then it won't work as a leaf off of prio to handle a single flow.

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

On Tue, 05 Apr 2005 21:48:45 +0200
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> > Netem has a private queue for delayed packets, and currently, packets
> > in this queue are not accounted for in the qdisc qlen statistics.
> > This is a problem if netem is used inside another qdisc doing rate
> > control that peeks at the qlen.
> > 
> > This patch changes the statistics to include the packets held but
> > not ready to send.
> 
> There is one troublesome spot left, netem_watchdog() decreases q.qlen
> when the packet couldn't be enqueued. I don't think it is possible
> to make netem useable as leaf-qdisc, it will always have to touch
> q.qlen from timer context and classful qdiscs can't deal with this
> since they all maintain their own q.qlen counters and expect changes
> only in the +-1 range in enqueue/dequeue/requeue/drop. Best thing IMO
> would be to refuse to work as anything but root qdisc.
> 

Would this work better.? It just increases qlen by +/- 1 on enqueue, dequeue.
It also allows < 1ms delays if there is enough traffic going through.

--- linux-2.6.12-rc2/net/sched/sch_netem.c	2005-04-04 09:39:41.000000000 -0700
+++ netem-2.6.12-rc2/net/sched/sch_netem.c	2005-04-06 15:39:16.000000000 -0700
@@ -138,38 +138,78 @@ static long tabledist(unsigned long mu, 
 }
 
 /* Put skb in the private delayed queue. */
-static int delay_skb(struct Qdisc *sch, struct sk_buff *skb)
+static int netem_delay(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
-	struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
 	psched_tdiff_t td;
 	psched_time_t now;
 	
 	PSCHED_GET_TIME(now);
 	td = tabledist(q->latency, q->jitter, &q->delay_cor, q->delay_dist);
-	PSCHED_TADD2(now, td, cb->time_to_send);
 	
 	/* Always queue at tail to keep packets in order */
 	if (likely(q->delayed.qlen < q->limit)) {
+		struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
+	
+		PSCHED_TADD2(now, td, cb->time_to_send);
+
+		pr_debug("netem_delay: skb=%p now=%llu tosend=%llu\n", skb, 
+			 now, cb->time_to_send);
+	
 		__skb_queue_tail(&q->delayed, skb);
-		if (!timer_pending(&q->timer)) {
-			q->timer.expires = jiffies + PSCHED_US2JIFFIE(td);
-			add_timer(&q->timer);
-		}
 		return NET_XMIT_SUCCESS;
 	}
 
+	pr_debug("netem_delay: queue over limit %d\n", q->limit);
+	sch->qstats.overlimits++;
 	kfree_skb(skb);
 	return NET_XMIT_DROP;
 }
 
+/*
+ *  Move a packet that is ready to send from the delay holding
+ *  list to the underlying qdisc.
+ */
+static int netem_run(struct Qdisc *sch)
+{
+	struct netem_sched_data *q = qdisc_priv(sch);
+	struct sk_buff *skb;
+	psched_time_t now;
+
+	PSCHED_GET_TIME(now);
+
+	skb = skb_peek(&q->delayed);
+	if (skb) {
+		const struct netem_skb_cb *cb
+			= (const struct netem_skb_cb *)skb->cb;
+		long delay 
+			= PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
+		pr_debug("netem_run: skb=%p delay=%ld\n", skb, delay);
+
+		/* if more time remaining? */
+		if (delay > 0) {
+			mod_timer(&q->timer, jiffies + delay);
+			return 1;
+		}
+
+		__skb_unlink(skb, &q->delayed);
+		
+		if (q->qdisc->enqueue(skb, q->qdisc)) {
+			sch->q.qlen--;
+			sch->qstats.drops++;
+		} 
+	}
+
+	return 0;
+}
+
 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
 	struct sk_buff *skb2;
 	int ret;
 
-	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
+	pr_debug("netem_enqueue skb=%p\n", skb);
 
 	/* Random packet drop 0 => none, ~0 => all */
 	if (q->loss && q->loss >= get_crandom(&q->loss_cor)) {
@@ -184,7 +224,7 @@ static int netem_enqueue(struct sk_buff 
 	    && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
 		pr_debug("netem_enqueue: dup %p\n", skb2);
 
-		if (delay_skb(sch, skb2)) {
+		if (netem_delay(sch, skb2)) {
 			sch->q.qlen++;
 			sch->bstats.bytes += skb2->len;
 			sch->bstats.packets++;
@@ -202,7 +242,8 @@ static int netem_enqueue(struct sk_buff 
 		ret = q->qdisc->enqueue(skb, q->qdisc);
 	} else {
 		q->counter = 0;
-		ret = delay_skb(sch, skb);
+		ret = netem_delay(sch, skb);
+		netem_run(sch);
 	}
 
 	if (likely(ret == NET_XMIT_SUCCESS)) {
@@ -241,56 +282,35 @@ static unsigned int netem_drop(struct Qd
 	return len;
 }
 
-/* Dequeue packet.
- *  Move all packets that are ready to send from the delay holding
- *  list to the underlying qdisc, then just call dequeue
- */
 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
 	struct sk_buff *skb;
+	int pending;
+
+	pending = netem_run(sch);
 
 	skb = q->qdisc->dequeue(q->qdisc);
-	if (skb) 
+	if (skb) {
+		pr_debug("netem_dequeue: return skb=%p\n", skb);
 		sch->q.qlen--;
+		sch->flags &= ~TCQ_F_THROTTLED;
+	}
+	else if (pending) {
+		pr_debug("netem_dequeue: throttling\n");
+		sch->flags |= TCQ_F_THROTTLED;
+	} 
+
 	return skb;
 }
 
 static void netem_watchdog(unsigned long arg)
 {
 	struct Qdisc *sch = (struct Qdisc *)arg;
-	struct netem_sched_data *q = qdisc_priv(sch);
-	struct net_device *dev = sch->dev;
-	struct sk_buff *skb;
-	psched_time_t now;
 
-	pr_debug("netem_watchdog: fired @%lu\n", jiffies);
-
-	spin_lock_bh(&dev->queue_lock);
-	PSCHED_GET_TIME(now);
-
-	while ((skb = skb_peek(&q->delayed)) != NULL) {
-		const struct netem_skb_cb *cb
-			= (const struct netem_skb_cb *)skb->cb;
-		long delay 
-			= PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
-		pr_debug("netem_watchdog: skb %p@%lu %ld\n",
-			 skb, jiffies, delay);
-
-		/* if more time remaining? */
-		if (delay > 0) {
-			mod_timer(&q->timer, jiffies + delay);
-			break;
-		}
-		__skb_unlink(skb, &q->delayed);
-
-		if (q->qdisc->enqueue(skb, q->qdisc)) {
-			sch->q.qlen--;
-			sch->qstats.drops++;
-		}
-	}
-	qdisc_run(dev);
-	spin_unlock_bh(&dev->queue_lock);
+	pr_debug("netem_watchdog qlen=%d\n", sch->q.qlen);
+	sch->flags &= ~TCQ_F_THROTTLED;
+	netif_schedule(sch->dev);
 }
 
 static void netem_reset(struct Qdisc *sch)
@@ -301,6 +321,7 @@ static void netem_reset(struct Qdisc *sc
 	skb_queue_purge(&q->delayed);
 
 	sch->q.qlen = 0;
+	sch->flags &= ~TCQ_F_THROTTLED;
 	del_timer_sync(&q->timer);
 }
 

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

Stephen Hemminger wrote:
> Would this work better.? It just increases qlen by +/- 1 on enqueue, dequeue.
> It also allows < 1ms delays if there is enough traffic going through.

It looks better, but with duplication there can still be an increment
of 2 in netem_enqueue().

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

On Sun, 17 Apr 2005 17:38:40 +0200
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> > Would this work better.? It just increases qlen by +/- 1 on enqueue, dequeue.
> > It also allows < 1ms delays if there is enough traffic going through.
> 
> It looks better, but with duplication there can still be an increment
> of 2 in netem_enqueue().

There may be no sane way to do duplication without that. Other ways like injecting
packets again at top of queue with a thread/tasklet seem rather gross

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

Stephen Hemminger wrote:
> There may be no sane way to do duplication without that.

This way doesn't work properly either. The classful qdiscs don't care
about their own q.qlen and just try to dequeue, if successful they
decrement q.qlen. When duplicating packets in an inner qdisc the
top-level qdisc's q.qlen will turn negative at some point (it's
unsigned, but returned as int from qdisc_restart) and will cause
qdisc_run() to spin forever.

> Other ways like injecting
> packets again at top of queue with a thread/tasklet seem rather gross

Injecting at the top is also problematic because it needs to
follow the same classification-path as the first packet, which
can only be guarenteed with stateless classification.

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

On Wed, 20 Apr 2005 16:00:56 +0200
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> > There may be no sane way to do duplication without that.
> 
> This way doesn't work properly either. The classful qdiscs don't care
> about their own q.qlen and just try to dequeue, if successful they
> decrement q.qlen. When duplicating packets in an inner qdisc the
> top-level qdisc's q.qlen will turn negative at some point (it's
> unsigned, but returned as int from qdisc_restart) and will cause
> qdisc_run() to spin forever.

So duplication is a no go...
Unless there is a different way of accounting for qlen (like a callback).

> > Other ways like injecting
> > packets again at top of queue with a thread/tasklet seem rather gross
> 
> Injecting at the top is also problematic because it needs to
> follow the same classification-path as the first packet, which
> can only be guarenteed with stateless classification.
> 
> Regards
> Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

Stephen Hemminger wrote:
> So duplication is a no go...
> Unless there is a different way of accounting for qlen (like a callback).

Instead of a callback you could store parent pointers in struct Qdisc
and walk up the tree. One place that would need additional changes to
cope with qlen changes of more than 1 is HFSC. It uses q.qlen == 1 as
indication that a leaf qdisc was activated by the last enqueue
operation. An increment of 2 when q.qlen was 0 before would cause HFSC
to forget to activate a class.

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Stephen Hemminger]

On Fri, 22 Apr 2005 01:10:25 +0200
Patrick McHardy <kaber@trash.net> wrote:

> Stephen Hemminger wrote:
> > So duplication is a no go...
> > Unless there is a different way of accounting for qlen (like a callback).
> 
> Instead of a callback you could store parent pointers in struct Qdisc
> and walk up the tree. One place that would need additional changes to
> cope with qlen changes of more than 1 is HFSC. It uses q.qlen == 1 as
> indication that a leaf qdisc was activated by the last enqueue
> operation. An increment of 2 when q.qlen was 0 before would cause HFSC
> to forget to activate a class.

I'm thinking of changing enqueue (and maybe later dequeue) API to decouple
the qlen assumption.

Either:
	rc = qdisc->enqueue(skb, qdisc, &my->qlen)
or add NET_XMIT_DUPPED
	rc = qdisc->enqueue(skb, qdisc);
	if (rc < NET_XMIT_SUCCESS) {
		++my->dropped;
	} else {
		my->qlen++;
		if (rc == NET_XMIT_DUPPED)
			my->qlen++;
}

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

Stephen Hemminger wrote:
> I'm thinking of changing enqueue (and maybe later dequeue) API to decouple
> the qlen assumption.
> 
> Either:
> 	rc = qdisc->enqueue(skb, qdisc, &my->qlen)
> or add NET_XMIT_DUPPED
> 	rc = qdisc->enqueue(skb, qdisc);
> 	if (rc < NET_XMIT_SUCCESS) {
> 		++my->dropped;
> 	} else {
> 		my->qlen++;
> 		if (rc == NET_XMIT_DUPPED)
> 			my->qlen++;
> }

To be frank, I don't like either one. Both have the same problem
wrt. HFSC, the first solution requires changes all over the place,
the second one is unflexible and also requires lots of changes. I
don't see what could benefit from this API change besides netem,
so I'd vote to go with my proposed solution: store the parent
pointers in struct Qdisc, add code to walk up the tree and adjust
the qlen to netem, and fix up HFSC.

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[jamal]

On Fri, 2005-22-04 at 01:39 +0200, Patrick McHardy wrote:
> Stephen Hemminger wrote:
> > I'm thinking of changing enqueue (and maybe later dequeue) API to decouple
> > the qlen assumption.
> > 
> > Either:
> > 	rc = qdisc->enqueue(skb, qdisc, &my->qlen)
> > or add NET_XMIT_DUPPED
> > 	rc = qdisc->enqueue(skb, qdisc);
> > 	if (rc < NET_XMIT_SUCCESS) {
> > 		++my->dropped;
> > 	} else {
> > 		my->qlen++;
> > 		if (rc == NET_XMIT_DUPPED)
> > 			my->qlen++;
> > }
> 
> To be frank, I don't like either one. Both have the same problem
> wrt. HFSC, the first solution requires changes all over the place,
> the second one is unflexible and also requires lots of changes. I
> don't see what could benefit from this API change besides netem,
> so I'd vote to go with my proposed solution: store the parent
> pointers in struct Qdisc, add code to walk up the tree and adjust
> the qlen to netem, and fix up HFSC.

Duplication of packets would be trivial to do with mirred mirror option
attached to the qdisc. Something along the lines of:

on device ethx \
match all packets (or whatever filter you want) \
action mirred mirror to device ethx

To duplicate packet more than once:
on device ethx \
match all packets (or whatever filter you want) \
action mirred mirror to device ethx \
action mirred mirror to device ethx

repeat for as many dups as you want

more funky?
randomly duplicate one or two packets

on device ethx \
match all packets (or whatever filter you want) \
action gact random stop here \
action mirred mirror to device ethx \
action gact random stop here \
action mirred mirror to device ethx

cheers,
jamal

Re: [PATCH] netem: account for packets in delayed queue in qlen

[Patrick McHardy]

jamal wrote:
> Duplication of packets would be trivial to do with mirred mirror option
> attached to the qdisc.

The problem with duplication and queueing to the device is that
the packet needs to take the same classification-path as the
original packet to end up in the same leaf-queue. This can only
be guaranteed by restricting which classifiers can be used.

Regards
Patrick

Re: [PATCH] netem: account for packets in delayed queue in qlen

[jamal]

On Fri, 2005-22-04 at 02:10 +0200, Patrick McHardy wrote:
> jamal wrote:
> > Duplication of packets would be trivial to do with mirred mirror option
> > attached to the qdisc.
> 
> The problem with duplication and queueing to the device is that
> the packet needs to take the same classification-path as the
> original packet to end up in the same leaf-queue. This can only
> be guaranteed by restricting which classifiers can be used.

What i described happens before the queueing. So packets should end up
in the same leaf queue because the same classifier rule is used to
select the dup action. I should actually try to make sure it works;

cheers,
jamal

Re: [PATCH] netem: account for packets in delayed queue in qlen

[jamal]

On Thu, 2005-21-04 at 20:32 -0400, jamal wrote:
>  I should actually try to make sure it works;
> 

Never mind - it wont work at the moment ;->
A missing feature described at the top should get it to work though ;->

cheers,
jamal