Next event time should consider jiffies used for recounting. Otherwise
qdisc_watchdog_schedule() triggers hrtimer immediately with the event
in the past, and may cause very high ksoftirqd cpu usage (if highres
is on). This patch charges jiffies globally, so we can skip this in
htb_do_events().

Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
---
 net/sched/sch_htb.c |   14 ++++++++++++--
 1 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index d6eb4a7..102866d 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -685,8 +685,11 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level)
 		if (cl->cmode != HTB_CAN_SEND)
 			htb_add_to_wait_tree(q, cl, diff);
 	}
-	/* too much load - let's continue on next jiffie (including above) */
-	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
+	/*
+	 * Too much load - let's continue on next jiffie.
+	 * (Used jiffies are charged later.)
+	 */
+	return q->now + 1;
 }
 
 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
@@ -845,6 +848,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 	struct htb_sched *q = qdisc_priv(sch);
 	int level;
 	psched_time_t next_event;
+	unsigned long start_at;
 
 	/* try to dequeue direct packets as high prio (!) to minimize cpu work */
 	skb = __skb_dequeue(&q->direct_queue);
@@ -857,6 +861,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 	if (!sch->q.qlen)
 		goto fin;
 	q->now = psched_get_time();
+	start_at = jiffies;
 
 	next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
 
@@ -889,6 +894,11 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 		}
 	}
 	sch->qstats.overlimits++;
+	/* charge used jiffies */
+	start_at = jiffies - start_at;
+	if (start_at > 0)
+		next_event += start_at * PSCHED_TICKS_PER_SEC / HZ;
+
 	qdisc_watchdog_schedule(&q->watchdog, next_event);
 fin:
 	return skb;
-- 
1.5.6.5

--

[ message continues ]

Currently htb_do_events() breaks events recounting for a level after 2
jiffies, but there is no reason to repeat this for next levels and
increase delays even more (with softirqs disabled). htb_dequeue_tree()
can add to this too, btw. In such a case q->now time is invalid anyway.

Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
---
 net/sched/sch_htb.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 102866d..b241ac6 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -661,12 +661,13 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
  * next pending event (0 for no event in pq).
  * Note: Applied are events whose have cl->pq_key <= q->now.
  */
-static psched_time_t htb_do_events(struct htb_sched *q, int level)
+static psched_time_t htb_do_events(struct htb_sched *q, int level,
+				   unsigned long start)
 {
 	/* don't run for longer than 2 jiffies; 2 is used instead of
 	   1 to simplify things when jiffy is going to be incremented
 	   too soon */
-	unsigned long stop_at = jiffies + 2;
+	unsigned long stop_at = start + 2;
 	while (time_before(jiffies, stop_at)) {
 		struct htb_class *cl;
 		long diff;
@@ -871,7 +872,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 		psched_time_t event;
 
 		if (q->now >= q->near_ev_cache[level]) {
-			event = htb_do_events(q, level);
+			event = htb_do_events(q, level, start_at);
 			if (!event)
 				event = q->now + PSCHED_TICKS_PER_SEC;
 			q->near_ev_cache[level] = event;
-- 
1.5.6.5

--

[ message continues ]

This (including the last patch) is really confusing - q->now doesn't
contain HZ values but psched ticks. Could you describe the overall
algorithm you're trying to implement please?

--

[ message continues ]

The algorithm is we want to "continue on the next jiffie". We know
we've lost here a lot of time (~2 jiffies), and this will be added
later. Since these jiffies are not precise enough wrt. psched ticks
or ktime, and we will add around 2000 (for HZ 1000) psched ticks
anyway this +1 here simply doesn't matter and can mean "a bit after
q->now".

We can try to do this more precisely with additional psched_get_time(),
instead of jiffies, but my "tests" didn't show any advantage. What
matters is to avoid longer scheduling with the past time.

This case can probably happen only with very low rate limits for a
large number of classes, and I guess they simply need some spare time,
not necessarily at psched tick precision.

Jarek P.
--

[ message continues ]

This might as well return q->now, no? The elapsed time is added
on top later anyways. But anyways, I think both the approach and
the patch are wrong.

	/* charge used jiffies */
	start_at = jiffies - start_at;
	if (start_at > 0)
		next_event += start_at * PSCHED_TICKS_PER_SEC / HZ;

What relationship does the duration it ran for has to the time it
should run at again?

The focus on jiffies is wrong IMO, the reason why we get high
load is because the CPU can't keep up, delaying things even
longer is not going to help get the work done. The only reason to
look at jiffies is because its a cheap indication that it has
ran for too long and we should give other tasks a change to run
as well, but it should continue immediately after it did that.
So all it should do is make sure that the watchdog is scheduled
with a very small positive delay.

As for the implementation: the increase in delay (the snippet
above) is also done in the case that no packets were available
for other reasons (throttling), in which case we might needlessly
delay for an extra jiffie if jiffies wrapped while it tried to
dequeue.
--

[ message continues ]

Yes, but IMHO it looks worse, considering the problem here (we want to

The scheduling times won't be in the past mostly and hrtimers won't
trigger too soon, but approximately around we really need and can

This needs additional psched_get_time(), and as I've written before
there is no apparent advantage in problematic cases, but this would

But in another similar cases there could be no change in jiffies, but
almost a jiffie used for counting, so wrong schedule time as well.
Approximatly this all should be fine, and it still can be tuned later.
IMHO, this all should not affect "common" cases, which are expected to
use less then jiffie here.

Jarek P.
--

[ message continues ]

Sure. But it also won't be in the past if we simply add .. lets say
the current uptime in ms. My point was that there's absolutely no
relationship between those two times and combining them just to
get a value thats not in the past is wrong. Especially considering
*why* we want a value in the future and what we'll get from that

htb_do_events() exceeding two jiffies is fortunately not a common
case. You (incorrectly) made the calculation somewhat of a common
case by also adding to the delay if the inner classes simply throttled
and already returned the exact delay they want.

Much better (again considering what we want to achieve here) would
be to not use the hrtimer watchdog at all. We want to give lower
priority tasks a chance to run, so ideally we'd use a low priority

Its not "wrong". We don't want to delay. Its a courtesy to the

Jiffies might wrap even if it only took only a few nanoseconds.
And its not fine, in the case of throttled classes there's no
reason to add extra delay *at all*.
--

[ message continues ]

To David Miller: David don't apply yet - this patch needs change.

Patrick, read below:




I'm not sure I get ot right: for precise scheduling hrtimers look

In this case it's probably self-courtesy too: this ksoftirqd takes

Yes, you are right with this. I can try too fix this tomorrow, unless
you prefer to send your version of this patch.

Thanks,
Jarek P.
--

[ message continues ]

I meant "at all" for the wakeup after we've decided HTB has too much
work to do at once. A work queue seems better suited since that makes
sure we allow other processes to run, but don't wait unnecessarily

Well, it calls back to HTB, which continues to do real work. But
leaving HTB, scheduling a timer just to be called immediately again

I don't have a version of my own, so please go ahead :)
--

[ message continues ]

On Tue, Dec 09, 2008 at 03:56:09PM +0100, Patrick McHardy wrote:

Maybe I miss your point, but IMHO the too much work case isn't a
problem here: there is a lot of time wasted in this case, so e.g.
additional psched_get_time() and "safe" rescheduling is possible -
no need to complicate it with workqueues etc. (but current patch 7
should be enough). I'm concerned with e.g. a config doing often
htb_do_events() and htb_dequeue_tree() in ~1 jiffie and
rescheduling for 1/2 jiffie (or 1/2 vs. 1/4 etc.), so mainly in

Alas I haven't found how we can fix it generally without any such costs,
so I think I've to leave this problem for now. Then only this "over 2
jiffies" case should be fixed here (current patch 7), plus I propose the
patch below to additionally skip doing events generally after 2 jiffies.

Thanks,
Jarek P.

-------------> (redone old patch 3 - to apply on top of patch 7)

pkt_sched: sch_htb: Break all htb_do_events() after 2 jiffies

Currently htb_do_events() breaks events recounting for a level after 2
jiffies, but there is no reason to repeat this for next levels and
increase delays even more (with softirqs disabled). htb_dequeue_tree()
can add to this too, btw. In such a case q->now time is invalid anyway.

Thanks to Patrick McHardy for spotting an error around earlier version
of this patch.

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

 net/sched/sch_htb.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 9ca8a26..2f0f0b0 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -661,12 +661,13 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
  * next pending event (0 for no event in pq).
  * Note: Applied are events whose have cl->pq_key <= q->now.
  */
-static psched_time_t htb_do_events(struct htb_sched *q, int level)
+static psched_time_t htb_do_events(struct htb_sched *q, int level,
+				   unsigned long start)
 {
 	/* don't run ...
[ message continues ]

(resend)

pkt_sched: sch_htb: Break all htb_do_events() after 2 jiffies

Currently htb_do_events() breaks events recounting for a level after 2
jiffies, but there is no reason to repeat this for next levels and
increase delays even more (with softirqs disabled). htb_dequeue_tree()
can add to this too, btw. In such a case q->now time is invalid anyway.

Thanks to Patrick McHardy for spotting an error around earlier version
of this patch.

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

 net/sched/sch_htb.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 9ca8a26..2f0f0b0 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -661,12 +661,13 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
  * next pending event (0 for no event in pq).
  * Note: Applied are events whose have cl->pq_key <= q->now.
  */
-static psched_time_t htb_do_events(struct htb_sched *q, int level)
+static psched_time_t htb_do_events(struct htb_sched *q, int level,
+				   unsigned long start)
 {
 	/* don't run for longer than 2 jiffies; 2 is used instead of
 	   1 to simplify things when jiffy is going to be incremented
 	   too soon */
-	unsigned long stop_at = jiffies + 2;
+	unsigned long stop_at = start + 2;
 	while (time_before(jiffies, stop_at)) {
 		struct htb_class *cl;
 		long diff;
@@ -845,6 +846,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 	struct htb_sched *q = qdisc_priv(sch);
 	int level;
 	psched_time_t next_event;
+	unsigned long start_at;
 
 	/* try to dequeue direct packets as high prio (!) to minimize cpu work */
 	skb = __skb_dequeue(&q->direct_queue);
@@ -857,6 +859,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 	if (!sch->q.qlen)
 		goto fin;
 	q->now = psched_get_time();
+	start_at = jiffies;
 
 	next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
 
@@ -866,7 +869,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 ...
[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Also applied, thanks Jarek.
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

What I've done is apply patches 5 and 6 since those are
fine and independent of these timer issues.

So once you work this stuff out please resubmit the rest.

Thanks!
--

[ message continues ]

Very nice of you, but IMHO patches 1 and 4 are OK too.

I'm withdrawing patches 2 and 3, and will try to discuss this with

Of course, I can resubmit 1 and 4 if you think it's really needed.

Thanks,
Jarek P.
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Please do, there were dependencies.  In fact patch 2 changes
the very change you made in patch 1.

I understand it's logical steps, but you could just do 1 and
2 in the same patch and it'd be OK.
--

[ message continues ]

OK, so I withdraw 1 and 4 too, and let's say this is No 7 (2in1).

Sorry for this mess,
Jarek P.

------------->
pkt_sched: sch_htb: Consider used jiffies in htb_do_events()

Next event time should consider jiffies used for recounting. Otherwise
qdisc_watchdog_schedule() triggers hrtimer immediately with the event
in the past, and may cause very high ksoftirqd cpu usage (if highres
is on).

There is also removed checking "event" for zero in htb_dequeue(): it's
always true in this place.

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

 net/sched/sch_htb.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 5070643..9ca8a26 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -685,8 +685,8 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level)
 		if (cl->cmode != HTB_CAN_SEND)
 			htb_add_to_wait_tree(q, cl, diff);
 	}
-	/* too much load - let's continue on next jiffie */
-	return q->now + PSCHED_TICKS_PER_SEC / HZ;
+	/* too much load - let's continue on next jiffie (including above) */
+	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
 }
 
 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
@@ -873,7 +873,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 		} else
 			event = q->near_ev_cache[level];
 
-		if (event && next_event > event)
+		if (next_event > event)
 			next_event = event;
 
 		m = ~q->row_mask[level];
--

[ message continues ]

Just FYI, I'm travelling today, so I'll need until tommorrow to
review this.

--

[ message continues ]

Patrick, I know you said you were travelling and very busy,
but Jarek has been waiting patiently for you to review
these two newly respun patches.

These are just rotting in my patch queue and I'd like to
do something with them.

Thanks.
--

[ message continues ]

I guess Patrick has some doubts, but since these patches are not
critical, let's say I'll resend them within a few weeks.

Thanks,
Jarek P.
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Fair enough, I'll mark them deferred on patchwork
--

[ message continues ]

Sorry, I dropped the ball on this one. I still think scheduling
a work-queue or something else running in process context to
kick the queue once the scheduler had a chance to run would
be a better solution. But Jarek's patches are an improvement
to the current situation, so no objections from me.


--

[ message continues ]

Thanks for the review Patrick. As I wrote before, I'm not against
using a workqueue here: it's logically better, but I still think
this place is rather exception, so I'm not convinced we should
care so much adding better solution, but also some overhead when
cancelling this workqueue. But if it really bothers you, please
confirm, and I'll do it. BTW, I wonder if adding the old "too many
events" warning back wouldn't be more useful here.

David, I'm not sure you can still track these patches, so I'll
soon resend them (2 patches: #7/6 and 8/6).

Thanks,
Jarek P.
--

[ message continues ]

It doesn't bother me :) I just think its the technical better
and also most likely code-wise cleaner solution to this problem.
Cancellation wouldn't be necessary since an unnecessary
netif_schedule() doesn't really matter.

It you don't mind adding the workqueue, I certainly would prefer
it, but I'm also fine with this patch. I don't have a HTB setup
or a testcase for this specific case, otherwise I'd simply do it

It would be good to notify the user and also have some indication
for this case when looking into bug reports. A counter or a (single)
printk would both be fine.

--

[ message continues ]

On Mon, Jan 12, 2009 at 11:22:47AM +0100, Patrick McHardy wrote:

Hmm... Do you mean during destroying... It's probably not very long,
but deleting and creating qdiscs especially for some virtual devices
can take longer I guess.

Jarek P.
--

[ message continues ]

I was referring to your statement "but also some overhead when
cancelling this workqueue" and assumed you meant during packet
processing. In the destruction path it really doesn't matter at
all.
--

[ message continues ]

Here is my proposal. (I assume single "work conserving" warn should be
enough too - if somebody doesn't fix it for one class, they probably
know what they are doing, and don't need more.)

Jarek P.
-------------->
pkt_sched: sch_htb: Warn on too many events.

Let's get some info on possible config problems. This patch brings
back an old warning, but it's printed only once now. BTW a "class
isn't work conserving" warning is also limited to once per qdisc
instead of per class.

With feedback from Patrick McHardy <kaber@trash.net>

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

 net/sched/sch_htb.c |   14 ++++++++++----
 1 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 2f0f0b0..6fbb3e3 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -114,8 +114,6 @@ struct htb_class {
 	struct tcf_proto *filter_list;
 	int filter_cnt;
 
-	int warned;		/* only one warning about non work conserving .. */
-
 	/* token bucket parameters */
 	struct qdisc_rate_table *rate;	/* rate table of the class itself */
 	struct qdisc_rate_table *ceil;	/* ceiling rate (limits borrows too) */
@@ -155,6 +153,10 @@ struct htb_sched {
 	int direct_qlen;	/* max qlen of above */
 
 	long direct_pkts;
+
+#define HTB_WARN_NONCONSERVING	0x1
+#define HTB_WARN_TOOMANYEVENTS	0x2
+	int warned;	/* only one warning about non work conserving etc. */
 };
 
 /* find class in global hash table using given handle */
@@ -687,6 +689,10 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level,
 			htb_add_to_wait_tree(q, cl, diff);
 	}
 	/* too much load - let's continue on next jiffie (including above) */
+	if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
+		printk(KERN_WARNING "htb: too many events!\n");
+		q->warned |= HTB_WARN_TOOMANYEVENTS;
+	}
 	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
 }
 
@@ -809,11 +815,11 @@ next:
 		skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
 		if (likely(skb != NULL))
 ...
[ message continues ]

How about making this flag and the warning message (in a out-of-line
function) globally available? Other qdiscs (f.i. HFSC) can't deal with
inner non-work-conserving qdiscs as well.
--

[ message continues ]

OK, thanks,
Jarek P.
------------------> take 2: PATCH 1/3
pkt_sched: sch_hfsc: sch_htb: Add non-work-conserving warning handler.


This patch uses qdisc->flags field of "suspected" child qdisc.

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

diff -Nurp a/include/net/pkt_sched.h b/include/net/pkt_sched.h
--- a/include/net/pkt_sched.h	2009-01-02 21:21:37.000000000 +0100
+++ b/include/net/pkt_sched.h	2009-01-29 22:57:55.000000000 +0100
@@ -85,6 +85,7 @@ extern struct qdisc_rate_table *qdisc_ge
 		struct nlattr *tab);
 extern void qdisc_put_rtab(struct qdisc_rate_table *tab);
 extern void qdisc_put_stab(struct qdisc_size_table *tab);
+extern void qdisc_warn_nonwc(char *txt, struct Qdisc *qdisc);
 
 extern void __qdisc_run(struct Qdisc *q);
 
diff -Nurp a/include/net/sch_generic.h b/include/net/sch_generic.h
--- a/include/net/sch_generic.h	2009-01-20 18:43:03.000000000 +0100
+++ b/include/net/sch_generic.h	2009-01-29 22:36:33.000000000 +0100
@@ -42,9 +42,10 @@ struct Qdisc
 	int 			(*enqueue)(struct sk_buff *skb, struct Qdisc *dev);
 	struct sk_buff *	(*dequeue)(struct Qdisc *dev);
 	unsigned		flags;
-#define TCQ_F_BUILTIN	1
-#define TCQ_F_THROTTLED	2
-#define TCQ_F_INGRESS	4
+#define TCQ_F_BUILTIN		1
+#define TCQ_F_THROTTLED		2
+#define TCQ_F_INGRESS		4
+#define TCQ_F_WARN_NONWC	(1 << 16)
 	int			padded;
 	struct Qdisc_ops	*ops;
 	struct qdisc_size_table	*stab;
diff -Nurp a/net/sched/sch_api.c b/net/sched/sch_api.c
--- a/net/sched/sch_api.c	2009-01-20 18:43:10.000000000 +0100
+++ b/net/sched/sch_api.c	2009-01-30 00:35:19.000000000 +0100
@@ -444,6 +444,17 @@ out:
 }
 EXPORT_SYMBOL(qdisc_calculate_pkt_len);
 
+void qdisc_warn_nonwc(char *txt, struct Qdisc *qdisc)
+{
+	if (!(qdisc->flags & TCQ_F_WARN_NONWC)) {
+		printk(KERN_WARNING
+		       "%s: %s qdisc %X: is non-work-conserving?\n",
+		       txt, qdisc->ops->id, qdisc->handle >> 16);
+		qdisc->flags |= TCQ_F_WARN_NONWC;
+	}
+}
+EXPORT_SYMBOL(qdisc_warn_nonwc);
+
 static enum hrtimer_restart ...
[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Applied.
--

[ message continues ]

------------------> PATCH 2/3
pkt_sched: sch_htb: Warn on too many events.

Let's get some info on possible config problems. This patch brings
back an old warning, but is printed only once now.

With feedback from Patrick McHardy <kaber@trash.net>

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

diff -Nurp b/net/sched/sch_htb.c c/net/sched/sch_htb.c
--- b/net/sched/sch_htb.c	2009-01-29 22:07:42.000000000 +0000
+++ c/net/sched/sch_htb.c	2009-01-30 08:48:41.000000000 +0000
@@ -153,6 +153,9 @@ struct htb_sched {
 	int direct_qlen;	/* max qlen of above */
 
 	long direct_pkts;
+
+#define HTB_WARN_TOOMANYEVENTS	0x1
+	unsigned int warned;	/* only one warning */
 };
 
 /* find class in global hash table using given handle */
@@ -685,6 +688,10 @@ static psched_time_t htb_do_events(struc
 			htb_add_to_wait_tree(q, cl, diff);
 	}
 	/* too much load - let's continue on next jiffie (including above) */
+	if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
+		printk(KERN_WARNING "htb: too many events!\n");
+		q->warned |= HTB_WARN_TOOMANYEVENTS;
+	}
 	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
 }
 
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Applied.
--

[ message continues ]

(Changed In-Reply-To)

OK, thanks,
Jarek P.
-------------> PATCH 3/3
pkt_sched: sch_htb: Use workqueue to schedule after too many events.

Patrick McHardy <kaber@trash.net> suggested using a workqueue instead
of hrtimers to trigger netif_schedule() when there is a problem with
setting exact time of this event: 'The differnce - yeah, it shouldn't
make much, mainly wake up the qdisc earlier (but not too early) after
"too many events" occured _and_ no further enqueue events wake up the
qdisc anyways.'

Signed-off-by: Jarek Poplawski <jarkao2@gmail.com>
---
diff -Nurp c/net/sched/sch_htb.c d/net/sched/sch_htb.c
--- c/net/sched/sch_htb.c	2009-01-30 08:48:41.000000000 +0000
+++ d/net/sched/sch_htb.c	2009-01-30 09:00:06.000000000 +0000
@@ -35,6 +35,7 @@
 #include <linux/list.h>
 #include <linux/compiler.h>
 #include <linux/rbtree.h>
+#include <linux/workqueue.h>
 #include <net/netlink.h>
 #include <net/pkt_sched.h>
 
@@ -156,6 +157,7 @@ struct htb_sched {
 
 #define HTB_WARN_TOOMANYEVENTS	0x1
 	unsigned int warned;	/* only one warning */
+	struct work_struct work;
 };
 
 /* find class in global hash table using given handle */
@@ -659,7 +661,7 @@ static void htb_charge_class(struct htb_
  * htb_do_events - make mode changes to classes at the level
  *
  * Scans event queue for pending events and applies them. Returns time of
- * next pending event (0 for no event in pq).
+ * next pending event (0 for no event in pq, q->now for too many events).
  * Note: Applied are events whose have cl->pq_key <= q->now.
  */
 static psched_time_t htb_do_events(struct htb_sched *q, int level,
@@ -687,12 +689,14 @@ static psched_time_t htb_do_events(struc
 		if (cl->cmode != HTB_CAN_SEND)
 			htb_add_to_wait_tree(q, cl, diff);
 	}
-	/* too much load - let's continue on next jiffie (including above) */
+
+	/* too much load - let's continue after a break for scheduling */
 	if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
 		printk(KERN_WARNING "htb: too many events!\n");
 		q->warned ...
[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Applied.
--

[ message continues ]

Here is an example of this workqueue. I hope I didn't miss your point,
but since I didn't find much difference in testing, I'd prefer not to
sign-off/merge this yet, at least until there are many reports on
"too many events" problem, and somebody finds it useful.

Thanks,
Jarek P.

--- (for example only)

diff -Nurp b/net/sched/sch_htb.c c/net/sched/sch_htb.c
--- b/net/sched/sch_htb.c	2009-01-13 20:20:47.000000000 +0100
+++ c/net/sched/sch_htb.c	2009-01-13 21:32:17.000000000 +0100
@@ -35,6 +35,7 @@
 #include <linux/list.h>
 #include <linux/compiler.h>
 #include <linux/rbtree.h>
+#include <linux/workqueue.h>
 #include <net/netlink.h>
 #include <net/pkt_sched.h>
 
@@ -157,6 +158,7 @@ struct htb_sched {
 #define HTB_WARN_NONCONSERVING	0x1
 #define HTB_WARN_TOOMANYEVENTS	0x2
 	int warned;	/* only one warning about non work conserving etc. */
+	struct work_struct work;
 };
 
 /* find class in global hash table using given handle */
@@ -660,7 +662,7 @@ static void htb_charge_class(struct htb_
  * htb_do_events - make mode changes to classes at the level
  *
  * Scans event queue for pending events and applies them. Returns time of
- * next pending event (0 for no event in pq).
+ * next pending event (0 for no event in pq, q->now for too many events).
  * Note: Applied are events whose have cl->pq_key <= q->now.
  */
 static psched_time_t htb_do_events(struct htb_sched *q, int level,
@@ -688,12 +690,14 @@ static psched_time_t htb_do_events(struc
 		if (cl->cmode != HTB_CAN_SEND)
 			htb_add_to_wait_tree(q, cl, diff);
 	}
-	/* too much load - let's continue on next jiffie (including above) */
+
+	/* too much load - let's continue after a break for scheduling */
 	if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
 		printk(KERN_WARNING "htb: too many events!\n");
 		q->warned |= HTB_WARN_TOOMANYEVENTS;
 	}
-	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
+
+	return q->now;
 }
 
 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
@@ -898,7 ...
[ message continues ]

No, this seems to be exactly what I meant. The differnce - yeah, it
shouldn't make much, mainly wake up the qdisc earlier (but not too
early) after "too many events" occured _and_ no further enqueue
events wake up the qdisc anyways.
--

[ message continues ]

On Mon, Jan 12, 2009 at 10:10:47AM +0000, Jarek Poplawski wrote:

Maybe I should have mention this: there is nothing more except these 2
patches to merge from this thread.

Jarek P.
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Thanks, please do that.
--

[ message continues ]

I hope you've received them.

Thanks,
Jarek P.
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

I did, thanks.
--

[ message continues ]

(resend)

pkt_sched: sch_htb: Consider used jiffies in htb_do_events()

Next event time should consider jiffies used for recounting. Otherwise
qdisc_watchdog_schedule() triggers hrtimer immediately with the event
in the past, and may cause very high ksoftirqd cpu usage (if highres
is on).

There is also removed checking "event" for zero in htb_dequeue(): it's
always true in this place.

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

 net/sched/sch_htb.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_htb.c b/net/sched/sch_htb.c
index 5070643..9ca8a26 100644
--- a/net/sched/sch_htb.c
+++ b/net/sched/sch_htb.c
@@ -685,8 +685,8 @@ static psched_time_t htb_do_events(struct htb_sched *q, int level)
 		if (cl->cmode != HTB_CAN_SEND)
 			htb_add_to_wait_tree(q, cl, diff);
 	}
-	/* too much load - let's continue on next jiffie */
-	return q->now + PSCHED_TICKS_PER_SEC / HZ;
+	/* too much load - let's continue on next jiffie (including above) */
+	return q->now + 2 * PSCHED_TICKS_PER_SEC / HZ;
 }
 
 /* Returns class->node+prio from id-tree where classe's id is >= id. NULL
@@ -873,7 +873,7 @@ static struct sk_buff *htb_dequeue(struct Qdisc *sch)
 		} else
 			event = q->near_ev_cache[level];
 
-		if (event && next_event > event)
+		if (next_event > event)
 			next_event = event;
 
 		m = ~q->row_mask[level];
--

[ message continues ]

From: Jarek Poplawski <jarkao2@gmail.com>

Applied.
--

[ message continues ]