Skip to contentSkip to conversation

net: Sanitizing hrtimer usage in net/sched/sch_cbq.c

PATCH In review Thomas Gleixner 6 participants 25 messages Jul 9, 2009 – Jul 22, 2009

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover net: Sanitizing hrtimer usage in net/sched/sch_cbq.c

While looking at the "Soft-Lockup/Race in networking in 2.6.31-rc1+195 ( possibly caused by netem)" issue (http://lkml.org/lkml/2009/7/2/519)
I noticed some serious problems in the hrtimer related code of net/sched/sched/sch_cbq.c.

The following patch series addresses these.

I'm not entirely sure whether patch [1/3] covers all possible concurrent modifications, but it fixes the most obvious ones. The remaining details are left to the networking experts.

Patches [1/3] and [2/3] might be stable material as well.

Thanks,

tglx

#1 lore raw

PATCH 1/3 net: serialize hrtimer callback in sched_cbq

The hrtimer callback cbq_undelay() is not serialized against cbq_ovl_delay(). That affects at least q->pmask and q->delay_timer.

Lock it proper.

---
 net/sched/sch_cbq.c |    8 ++++++++
 1 file changed, 8 insertions(+)
net/sched/sch_cbq.c +8 -0
Index: linux-2.6/net/sched/sch_cbq.c
===================================================================
@@ -163,6 +163,7 @@ struct cbq_sched_data
 	psched_time_t		now_rt;		/* Cached real time */
 	unsigned		pmask;
 
+	spinlock_t		lock;
 	struct hrtimer		delay_timer;
 	struct qdisc_watchdog	watchdog;	/* Watchdog timer,
 						   started when CBQ has
@@ -503,6 +504,9 @@ static void cbq_ovl_delay(struct cbq_cla
 		cl->undertime = q->now + delay;
 
 		if (delay > 0) {
+			unsigned long flags;
+
+			spin_lock_irqsave(&q->lock, flags);
 			sched += delay + cl->penalty;
 			cl->penalized = sched;
 			cl->cpriority = TC_CBQ_MAXPRIO;
@@ -518,6 +522,7 @@ static void cbq_ovl_delay(struct cbq_cla
 			hrtimer_restart(&q->delay_timer);
 			cl->delayed = 1;
 			cl->xstats.overactions++;
+			spin_unlock_irqrestore(&q->lock, flags);
 			return;
 		}
 		delay = 1;
@@ -599,6 +604,7 @@ static enum hrtimer_restart cbq_undelay(
 
 	now = psched_get_time();
 
+	spin_lock(&q->lock);
 	pmask = q->pmask;
 	q->pmask = 0;
 
@@ -623,6 +629,7 @@ static enum hrtimer_restart cbq_undelay(
 		time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
 		hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
 	}
+	spin_unlock(&q->lock);
 
 	sch->flags &= ~TCQ_F_THROTTLED;
 	__netif_schedule(qdisc_root(sch));
@@ -1396,6 +1403,7 @@ static int cbq_init(struct Qdisc *sch, s
 	q->link.avpkt = q->link.allot/2;
 	q->link.minidle = -0x7FFFFFFF;
 
+	spin_lock_init(&q->lock);
 	qdisc_watchdog_init(&q->watchdog, sch);
 	hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
 	q->delay_timer.function = cbq_undelay;
maintainer
#2 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

From: Thomas Gleixner <[email protected]>
Date: Thu, 09 Jul 2009 21:59:22 -0000

Quoted 6 lines

The hrtimer callback cbq_undelay() is not serialized against cbq_ovl_delay(). That affects at least q->pmask and q->delay_timer.

Lock it proper.

The problems here are even much deeper than it appears.

First of all, I am to understand that hrtimers run from hardware interrupt context, right? If so, all of these datastructures are softirq safe only.

And it is not merely the immediate things you see being modified in this hrtimer, such as ->pmask etc., it is also the q->active[] pointers, the list state for the classes, just about everything in the qdisc state is referenced in this hrtimer code path.

I wonder how many queer unexplainable bugs we see because of this.

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

#3 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 21 lines · David Miller

From: Thomas Gleixner <[email protected]>
Date: Thu, 09 Jul 2009 21:59:22 -0000

Quoted 6 lines

The hrtimer callback cbq_undelay() is not serialized against cbq_ovl_delay(). That affects at least q->pmask and q->delay_timer.

Lock it proper.

The problems here are even much deeper than it appears.

First of all, I am to understand that hrtimers run from hardware interrupt context, right? If so, all of these datastructures are softirq safe only.

And it is not merely the immediate things you see being modified in this hrtimer, such as ->pmask etc., it is also the q->active[] pointers, the list state for the classes, just about everything in the qdisc state is referenced in this hrtimer code path.

Quoted 6 lines

I wonder how many queer unexplainable bugs we see because of this.

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

That's my understanding what HRTIMER_SOFTIRQ is used for. I think simply grabbing the root lock in cbq_undelay() should be fine.

Compile-tested only.

commit a790fb8873f1cbe8b9cb48cb368851e30d3ec172

Author: Patrick McHardy <[email protected]>
Date:   Tue Jul 14 10:19:47 2009 +0200

net-sched: sch_cbq: fix locking in cbq_undelay()

The hrtimer callback cbq_undelay() is not serialized against cbq_ovl_delay(). That affects at least q->pmask and q->delay_timer.

Lock it proper.

Based on patch by Thomas Gleixner <[email protected]>

net/sched/sch_cbq.c +5 -0
index 23a1676..7c659c6 100644
@@ -593,12 +593,16 @@ static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
 	struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
 						delay_timer);
 	struct Qdisc *sch = q->watchdog.qdisc;
+	spinlock_t *root_lock;
 	psched_time_t now;
 	psched_tdiff_t delay = 0;
 	unsigned pmask;
 
 	now = psched_get_time();
 
+	root_lock = qdisc_lock(qdisc_root(sch));
+	spin_lock(root_lock);
+
 	pmask = q->pmask;
 	q->pmask = 0;
 
@@ -615,6 +619,7 @@ static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
 				delay = tmp;
 		}
 	}
+	spin_unlock(root_lock);
 
 	if (delay) {
 		ktime_t time;
#4 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 3 lines · Patrick McHardy

That's my understanding what HRTIMER_SOFTIRQ is used for. I think simply grabbing the root lock in cbq_undelay() should be fine.

Its not, and its going away soon (again) :-)

The current use of HRTIMER_SOFTIRQ is for when we enqueue a hrtimer with an expiration time in the past. The current implementation tries to run the timer instantly, however we cannot do it from the context calling hrtimer_start(), since that might be holding locks the timer callback also wants to hold, resulting in deadlocks.

Instead we queue the timer to the softirq, and kick the softirq. Which leads to another problem in that we cannot always kick the softirq (esp from within the scheduler).

We're going to change hrtimer_start() to return -ETIME instead of trying to run the timer in-place, leaving the callers to figure it out.

The basic patch is done, but I still need to audit all the hrtimer users in the kernel.

maintainer
#5 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

In reply to Patrick McHardy

From: Patrick McHardy <[email protected]>
Date: Tue, 14 Jul 2009 10:22:02 +0200

Quoted 4 lines

That's my understanding what HRTIMER_SOFTIRQ is used for. I think simply grabbing the root lock in cbq_undelay() should be fine.

Compile-tested only.

Unfortunately, as Peter and Thomas explained, this is not the case.

#6 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

In reply to David Miller

David,

Quoted 12 lines · David Miller

From: Thomas Gleixner <[email protected]>
Date: Thu, 09 Jul 2009 21:59:22 -0000

Quoted 6 lines

The hrtimer callback cbq_undelay() is not serialized against cbq_ovl_delay(). That affects at least q->pmask and q->delay_timer.

Lock it proper.

The problems here are even much deeper than it appears.

Quoted 8 lines

First of all, I am to understand that hrtimers run from hardware interrupt context, right? If so, all of these datastructures are softirq safe only.

And it is not merely the immediate things you see being modified in this hrtimer, such as ->pmask etc., it is also the q->active[] pointers, the list state for the classes, just about everything in the qdisc state is referenced in this hrtimer code path.

That's what I was worried about.

Quoted 6 lines

I wonder how many queer unexplainable bugs we see because of this.

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

Sigh, I almost expected that the removal of the callback modes will fire back some day.

Thanks,

tglx

maintainer
#7 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

From: Thomas Gleixner <[email protected]>
Date: Tue, 14 Jul 2009 10:55:14 +0200 (CEST)

Quoted 11 lines

David,

Quoted 4 lines · David Miller

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

Sigh, I almost expected that the removal of the callback modes will fire back some day.

Well this makes hrtimers decidedly less useful for networking and we have a ton of bugs right now, basically in every hrtimer used by the networking currently.

The only way we can use them, as things currently stand, is as triggers for softirq work.

Is it really that troublesome to provide this kind of facility generically, rather than having various subsystems replicate such code where they want to use hrtimers and are restricted to softirqs?

#8 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 17 lines · David Miller

From: Thomas Gleixner <[email protected]>
Date: Tue, 14 Jul 2009 10:55:14 +0200 (CEST)

Quoted 9 lines · David Miller
Quoted 5 lines

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

Sigh, I almost expected that the removal of the callback modes will fire back some day.

Well this makes hrtimers decidedly less useful for networking and we have a ton of bugs right now, basically in every hrtimer used by the networking currently.

Quoted 6 lines

The only way we can use them, as things currently stand, is as triggers for softirq work.

Is it really that troublesome to provide this kind of facility generically, rather than having various subsystems replicate such code where they want to use hrtimers and are restricted to softirqs?

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

I can look into adding it back if we can agree on the interface and code impact, but looking at:

# git grep hrtimer_init net/ | sort -u
net/can/bcm.c:          hrtimer_init(&op->thrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
net/can/bcm.c:          hrtimer_init(&op->timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
net/sched/sch_api.c:    hrtimer_init(&wd->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
net/sched/sch_cbq.c:    hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);

I wonder if its worth the impact on the core kernel code, or whether its better for these few timers to kick off a tasklet or the like.

Further, I don't think a lot of subsystems would need this, as the general trend is away from softirqs/tasklets and towards threads/workqueues as most people want to schedule. And for those hardirq hrtimers are good enough as a wakeup source.

#9 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 7 lines · Peter Zijlstra

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

Yes. And I hated the bugs it had.

Don't make something as core as timers any more complicated. Don't take locks in timers and then complain about deadlocks. If your locking is broken, don't make the core timers be idiotically broken.

Because it was. The code was a total mess to follow, and had bugs.

Linus

#10 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 10 lines · Linus Torvalds
Quoted 7 lines · Peter Zijlstra

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

Quoted 7 lines

Yes. And I hated the bugs it had.

Don't make something as core as timers any more complicated. Don't take locks in timers and then complain about deadlocks. If your locking is broken, don't make the core timers be idiotically broken.

Because it was. The code was a total mess to follow, and had bugs.

How would something like the below work for people?

---
 include/linux/hrtimer.h |   22 ++++++++++++++++++++--
 kernel/hrtimer.c        |   23 ++++++++++++++++++++++-
 2 files changed, 42 insertions(+), 3 deletions(-)
include/linux/hrtimer.h +20 -2
index 4759917..e7559fe 100644
@@ -22,6 +22,7 @@
 #include <linux/wait.h>
 #include <linux/percpu.h>
 #include <linux/timer.h>
+#include <linux/interrupt.h>
 
 
 struct hrtimer_clock_base;
@@ -91,7 +92,6 @@ enum hrtimer_restart {
  * @function:	timer expiry callback function
  * @base:	pointer to the timer base (per cpu and per clock)
  * @state:	state information (See bit values above)
- * @cb_entry:	list head to enqueue an expired timer into the callback list
  * @start_site:	timer statistics field to store the site where the timer
  *		was started
  * @start_comm: timer statistics field to store the name of the process which
@@ -108,7 +108,6 @@ struct hrtimer {
 	enum hrtimer_restart		(*function)(struct hrtimer *);
 	struct hrtimer_clock_base	*base;
 	unsigned long			state;
-	struct list_head		cb_entry;
 #ifdef CONFIG_TIMER_STATS
 	int				start_pid;
 	void				*start_site;
@@ -116,6 +115,12 @@ struct hrtimer {
 #endif
 };
 
+struct hrtimer_softirq {
+	struct hrtimer		timer;
+	struct tasklet_struct	tasklet;
+	enum hrtimer_restart	(*function)(struct hrtimer *);
+};
+
 /**
  * struct hrtimer_sleeper - simple sleeper structure
  * @timer:	embedded timer structure
@@ -335,6 +340,19 @@ static inline void hrtimer_init_on_stack(struct hrtimer *timer,
 static inline void destroy_hrtimer_on_stack(struct hrtimer *timer) { }
 #endif
 
+enum hrtimer_restart __hrtimer_softirq_trampoline(struct hrtimer *timer);
+void __hrtimer_tasklet_trampoline(unsigned long data);
+
+static inline void hrtimer_softirq_init(struct hrtimer_softirq *stimer,
+		enum hrtimer_restart (*func)(struct hrtimer *),
+		clockid_t which_clock, enum hrtimer_mode mode)
+{
+	hrtimer_init(&stimer->timer, which_clock, mode);
+	stimer->timer.function = __hrtimer_softirq_trampoline;
+	tasklet_init(&stimer->tasklet, __hrtimer_tasklet_trampoline, stimer);
+	stimer->function = func;
+}
+
 /* Basic timer operations: */
 extern int hrtimer_start(struct hrtimer *timer, ktime_t tim,
 			 const enum hrtimer_mode mode);
kernel/hrtimer.c +22 -1
index ab5eb70..dae063c 100644
@@ -1098,7 +1098,6 @@ static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
 		clock_id = CLOCK_MONOTONIC;
 
 	timer->base = &cpu_base->clock_base[clock_id];
-	INIT_LIST_HEAD(&timer->cb_entry);
 	hrtimer_init_timer_hres(timer);
 
 #ifdef CONFIG_TIMER_STATS
@@ -1141,6 +1140,28 @@ int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp)
 }
 EXPORT_SYMBOL_GPL(hrtimer_get_res);
 
+enum hrtimer_restart __hrtimer_softirq_trampoline(struct hrtimer *timer)
+{
+	struct hrtimer_softirq *stimer =
+		container_of(timer, struct hrtimer_softirq, timer);
+
+	tasklet_hi_schedule(&timer->tasklet);
+
+	return HRTIMER_NORESTART;
+}
+EXPORT_SYMBOL_GPL(__hrtimer_softirq_trampoline);
+
+void __hrtimer_tasklet_trampoline(unsigned long data)
+{
+	struct hrtimer_softirq *stimer = (void *)data;
+	enum hrtimer_restart restart;
+
+	restart = stimer->function(&stimer->timer);
+	if (restart != HRTIMER_NORESTART)
+		hrtimer_restart(&stimer->timer);
+}
+EXPORT_SYMBOL_GPL(__hrtimer_tasklet_trampoline);
+
 static void __run_hrtimer(struct hrtimer *timer)
 {
 	struct hrtimer_clock_base *base = timer->base;
#11 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Linus Torvalds
Quoted 6 lines · Peter Zijlstra

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

Yes. And I hated the bugs it had.

Quoted 7 lines
Quoted 5 lines

Don't make something as core as timers any more complicated. Don't take locks in timers and then complain about deadlocks. If your locking is broken, don't make the core timers be idiotically broken.

Because it was. The code was a total mess to follow, and had bugs.

How would something like the below work for people?

Would be fine to me.

It reduces the duplicated code as well as private structs for hrtimers & tasklets. And finally your suggestion preserves the proper separation of the hrtimers and the tasklets that are used as underlying concepts.

Regards,
Oliver (who wrote net/can/bcm.c)

Quoted 113 lines
---
 include/linux/hrtimer.h |   22 ++++++++++++++++++++--
 kernel/hrtimer.c        |   23 ++++++++++++++++++++++-
 2 files changed, 42 insertions(+), 3 deletions(-)
include/linux/hrtimer.h +20 -2
index 4759917..e7559fe 100644
@@ -22,6 +22,7 @@
 #include <linux/wait.h>
 #include <linux/percpu.h>
 #include <linux/timer.h>
+#include <linux/interrupt.h>
 
 
 struct hrtimer_clock_base;
@@ -91,7 +92,6 @@ enum hrtimer_restart {
  * @function:	timer expiry callback function
  * @base:	pointer to the timer base (per cpu and per clock)
  * @state:	state information (See bit values above)
- * @cb_entry:	list head to enqueue an expired timer into the callback list
  * @start_site:	timer statistics field to store the site where the timer
  *		was started
  * @start_comm: timer statistics field to store the name of the process which
@@ -108,7 +108,6 @@ struct hrtimer {
 	enum hrtimer_restart		(*function)(struct hrtimer *);
 	struct hrtimer_clock_base	*base;
 	unsigned long			state;
-	struct list_head		cb_entry;
 #ifdef CONFIG_TIMER_STATS
 	int				start_pid;
 	void				*start_site;
@@ -116,6 +115,12 @@ struct hrtimer {
 #endif
 };
 
+struct hrtimer_softirq {
+	struct hrtimer		timer;
+	struct tasklet_struct	tasklet;
+	enum hrtimer_restart	(*function)(struct hrtimer *);
+};
+
 /**
  * struct hrtimer_sleeper - simple sleeper structure
  * @timer:	embedded timer structure
@@ -335,6 +340,19 @@ static inline void hrtimer_init_on_stack(struct hrtimer *timer,
 static inline void destroy_hrtimer_on_stack(struct hrtimer *timer) { }
 #endif
 
+enum hrtimer_restart __hrtimer_softirq_trampoline(struct hrtimer *timer);
+void __hrtimer_tasklet_trampoline(unsigned long data);
+
+static inline void hrtimer_softirq_init(struct hrtimer_softirq *stimer,
+		enum hrtimer_restart (*func)(struct hrtimer *),
+		clockid_t which_clock, enum hrtimer_mode mode)
+{
+	hrtimer_init(&stimer->timer, which_clock, mode);
+	stimer->timer.function = __hrtimer_softirq_trampoline;
+	tasklet_init(&stimer->tasklet, __hrtimer_tasklet_trampoline, stimer);
+	stimer->function = func;
+}
+
 /* Basic timer operations: */
 extern int hrtimer_start(struct hrtimer *timer, ktime_t tim,
 			 const enum hrtimer_mode mode);
kernel/hrtimer.c +22 -2
index ab5eb70..dae063c 100644
@@ -1098,7 +1098,6 @@ static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
 		clock_id = CLOCK_MONOTONIC;
 
 	timer->base = &cpu_base->clock_base[clock_id];
-	INIT_LIST_HEAD(&timer->cb_entry);
 	hrtimer_init_timer_hres(timer);
 
 #ifdef CONFIG_TIMER_STATS
@@ -1141,6 +1140,28 @@ int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp)
 }
 EXPORT_SYMBOL_GPL(hrtimer_get_res);
 
+enum hrtimer_restart __hrtimer_softirq_trampoline(struct hrtimer *timer)
+{
+	struct hrtimer_softirq *stimer =
+		container_of(timer, struct hrtimer_softirq, timer);
+
+	tasklet_hi_schedule(&timer->tasklet);
+
+	return HRTIMER_NORESTART;
+}
+EXPORT_SYMBOL_GPL(__hrtimer_softirq_trampoline);
+
+void __hrtimer_tasklet_trampoline(unsigned long data)
+{
+	struct hrtimer_softirq *stimer = (void *)data;
+	enum hrtimer_restart restart;
+
+	restart = stimer->function(&stimer->timer);
+	if (restart != HRTIMER_NORESTART)
+		hrtimer_restart(&stimer->timer);
+}
+EXPORT_SYMBOL_GPL(__hrtimer_tasklet_trampoline);
+
 static void __run_hrtimer(struct hrtimer *timer)
 {
 	struct hrtimer_clock_base *base = timer->base;
 
--

To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#12 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

In reply to Peter Zijlstra
Quoted 2 lines · Peter Zijlstra

How would something like the below work for people?

This looks saner.

It was the insanity of having the core timer code know about different modes that caused all the sily problems.

Having a separate abstraction layer for "I want to get a softirq timeout" sounds fine, as long as the timer code itself never cares.

That said, I don't think this shoud be a "hrtimer" issue (reflected in your naming and include file choice). I think this is a softirq or tasklet (or whatever) issue, and should be named that way.

Why should the timer code (and header files) care about how you can use tasklets with them? It shouldn't. The timers should be seen as the really low-level critical code, and the timer code should never need to know about softirq's or tasklets or whatever.

So I think you shouldmove it to kernel/softirq.c.

Linus

maintainer
#13 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

In reply to Peter Zijlstra

From: Peter Zijlstra <[email protected]>
Date: Fri, 17 Jul 2009 14:14:52 +0200

Quoted 13 lines · Linus Torvalds
Quoted 12 lines · Peter Zijlstra
Quoted 7 lines

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

Yes. And I hated the bugs it had.

Quoted 7 lines
Quoted 5 lines

Don't make something as core as timers any more complicated. Don't take locks in timers and then complain about deadlocks. If your locking is broken, don't make the core timers be idiotically broken.

Because it was. The code was a total mess to follow, and had bugs.

How would something like the below work for people?

I like it, but like Linus said it probably belongs in kernel/softirq.c

#14 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

Quoted 20 lines · David Miller

From: Peter Zijlstra <[email protected]>
Date: Fri, 17 Jul 2009 14:14:52 +0200

Quoted 17 lines · Linus Torvalds
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines

Linus really hated the softirq mode, which is what prompted me to change that.

Now, it might be he only hated the particular interface and the resulting code, but I think to remember he simply thought the whole thing daft.

Yes. And I hated the bugs it had.

Don't make something as core as timers any more complicated. Don't take locks in timers and then complain about deadlocks. If your locking is broken, don't make the core timers be idiotically broken.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

Because it was. The code was a total mess to follow, and had bugs.

How would something like the below work for people?

I like it, but like Linus said it probably belongs in kernel/softirq.c

Right, I meant to rework it, but stuff kept preempting me. I'll try and get around to it today :-)

#15 lore raw

PATCH 1/1 softirq: tasklet_hrtimer

In reply to David Miller

Thomas, will you take this?

---
Subject: softirq: tasklet_hrtimer
From: Peter Zijlstra <[email protected]>
Date: Wed Jul 22 14:18:35 CEST 2009

Stick tasklets and hrtimers together to provide an in-softirq hrtimer experience.

---
 include/linux/interrupt.h |   11 +++++++++++
 kernel/softirq.c          |   44 +++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 54 insertions(+), 1 deletion(-)
include/linux/interrupt.h +11 -0
Index: linux-2.6/include/linux/interrupt.h
===================================================================
@@ -14,6 +14,7 @@
 #include <linux/irqflags.h>
 #include <linux/smp.h>
 #include <linux/percpu.h>
+#include <linux/hrtimer.h>
 
 #include <asm/atomic.h>
 #include <asm/ptrace.h>
@@ -517,6 +518,16 @@ extern void tasklet_kill_immediate(struc
 extern void tasklet_init(struct tasklet_struct *t,
 			 void (*func)(unsigned long), unsigned long data);
 
+struct tasklet_hrtimer {
+	struct hrtimer 		timer;
+	struct tasklet_struct	tasklet;
+	enum hrtimer_restart	(*function)(struct hrtimer *);
+};
+
+void tasklet_hrtimer_init(struct tasklet_hrtimer *ttimer,
+			  enum hrtimer_restart (*function)(struct hrtimer *),
+			  clockid_t which_clock, enum hrtimer_mode mode);
+
 /*
  * Autoprobing for irqs:
  *
kernel/softirq.c +43 -1

56 lines not on this page · raw message

#16 lore raw

[tip:timers/urgent] softirq: introduce tasklet_hrtimer infrastructure

Commit-ID:  d34dc684eaad4e9561bbce423ac2581a48441fb0
Gitweb:     http://git.kernel.org/tip/d34dc684eaad4e9561bbce423ac2581a48441fb0
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Wed, 22 Jul 2009 14:18:35 +0200
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Wed, 22 Jul 2009 15:53:28 +0200

softirq: introduce tasklet_hrtimer infrastructure

commit ca109491f (hrtimer: removing all ur callback modes) moved all hrtimer callbacks into hard interrupt context when high resolution timers are active. That breaks code which relied on the assumption that the callback happens in softirq context.

Provide a generic infrastructure which combines tasklets and hrtimers together to provide an in-softirq hrtimer experience.

LKML-Reference: <1248265724.27058.1366.camel@twins>

---
 include/linux/interrupt.h |   26 ++++++++++++++++++
 kernel/softirq.c          |   64 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 89 insertions(+), 1 deletions(-)
include/linux/interrupt.h +26 -0
index 2721f07..fd4c9c6 100644
@@ -14,6 +14,7 @@
 #include <linux/irqflags.h>
 #include <linux/smp.h>
 #include <linux/percpu.h>
+#include <linux/hrtimer.h>
 
 #include <asm/atomic.h>
 #include <asm/ptrace.h>
@@ -517,6 +518,31 @@ extern void tasklet_kill_immediate(struct tasklet_struct *t, unsigned int cpu);
 extern void tasklet_init(struct tasklet_struct *t,
 			 void (*func)(unsigned long), unsigned long data);
 
+struct tasklet_hrtimer {
+	struct hrtimer		timer;
+	struct tasklet_struct	tasklet;
+	enum hrtimer_restart	(*function)(struct hrtimer *);
+};
+
+extern void
+tasklet_hrtimer_init(struct tasklet_hrtimer *ttimer,
+		     enum hrtimer_restart (*function)(struct hrtimer *),
+		     clockid_t which_clock, enum hrtimer_mode mode);
+
+static inline
+int tasklet_hrtimer_start(struct tasklet_hrtimer *ttimer, ktime_t time,
+			  const enum hrtimer_mode mode)
+{
+	return hrtimer_start(&ttimer->timer, time, mode);
+}
+
+static inline
+void tasklet_hrtimer_cancel(struct tasklet_hrtimer *ttimer)
+{
+	hrtimer_cancel(&ttimer->timer);
+	tasklet_kill(&ttimer->tasklet);
+}
+
 /*
  * Autoprobing for irqs:
  *
kernel/softirq.c +63 -1

76 lines not on this page · raw message

#17 lore raw

[tip:core/urgent] softirq: introduce tasklet_hrtimer infrastructure

In reply to Peter Zijlstra
Commit-ID:  9ba5f005c994ad28e266a0cd14ef29354be382c9
Gitweb:     http://git.kernel.org/tip/9ba5f005c994ad28e266a0cd14ef29354be382c9
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Wed, 22 Jul 2009 14:18:35 +0200
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Wed, 22 Jul 2009 17:01:17 +0200

softirq: introduce tasklet_hrtimer infrastructure

commit ca109491f (hrtimer: removing all ur callback modes) moved all hrtimer callbacks into hard interrupt context when high resolution timers are active. That breaks code which relied on the assumption that the callback happens in softirq context.

Provide a generic infrastructure which combines tasklets and hrtimers together to provide an in-softirq hrtimer experience.

LKML-Reference: <1248265724.27058.1366.camel@twins>

---
 include/linux/interrupt.h |   26 ++++++++++++++++++
 kernel/softirq.c          |   64 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 89 insertions(+), 1 deletions(-)
include/linux/interrupt.h +26 -0
index 2721f07..fd4c9c6 100644
@@ -14,6 +14,7 @@
 #include <linux/irqflags.h>
 #include <linux/smp.h>
 #include <linux/percpu.h>
+#include <linux/hrtimer.h>
 
 #include <asm/atomic.h>
 #include <asm/ptrace.h>
@@ -517,6 +518,31 @@ extern void tasklet_kill_immediate(struct tasklet_struct *t, unsigned int cpu);
 extern void tasklet_init(struct tasklet_struct *t,
 			 void (*func)(unsigned long), unsigned long data);
 
+struct tasklet_hrtimer {
+	struct hrtimer		timer;
+	struct tasklet_struct	tasklet;
+	enum hrtimer_restart	(*function)(struct hrtimer *);
+};
+
+extern void
+tasklet_hrtimer_init(struct tasklet_hrtimer *ttimer,
+		     enum hrtimer_restart (*function)(struct hrtimer *),
+		     clockid_t which_clock, enum hrtimer_mode mode);
+
+static inline
+int tasklet_hrtimer_start(struct tasklet_hrtimer *ttimer, ktime_t time,
+			  const enum hrtimer_mode mode)
+{
+	return hrtimer_start(&ttimer->timer, time, mode);
+}
+
+static inline
+void tasklet_hrtimer_cancel(struct tasklet_hrtimer *ttimer)
+{
+	hrtimer_cancel(&ttimer->timer);
+	tasklet_kill(&ttimer->tasklet);
+}
+
 /*
  * Autoprobing for irqs:
  *
kernel/softirq.c +63 -1

76 lines not on this page · raw message

maintainer Acked-by on v1 1/1
#18 lore raw

Re: [PATCH] softirq: tasklet_hrtimer

In reply to Peter Zijlstra

From: Peter Zijlstra <[email protected]>
Date: Wed, 22 Jul 2009 14:28:44 +0200

Quoted 11 lines

Thomas, will you take this?

---
Subject: softirq: tasklet_hrtimer
From: Peter Zijlstra <[email protected]>
Date: Wed Jul 22 14:18:35 CEST 2009

Stick tasklets and hrtimers together to provide an in-softirq hrtimer experience.

#20 lore raw

Re: [patch 1/3] net: serialize hrtimer callback in sched_cbq

In reply to David Miller
Quoted 11 lines · David Miller

From: Thomas Gleixner <[email protected]>
Date: Tue, 14 Jul 2009 10:55:14 +0200 (CEST)

Quoted 8 lines

David,

Quoted 4 lines · David Miller

What should probably happen is that the hrtimer merely fires off work at software interrupt context (perhaps a tasklet or similar), and that software interrupt code take the qdisc's root lock throughout it's execution.

Quoted 6 lines
Quoted 2 lines

Sigh, I almost expected that the removal of the callback modes will fire back some day.

Well this makes hrtimers decidedly less useful for networking and we have a ton of bugs right now, basically in every hrtimer used by the networking currently.

The CAN stuff is clean in this topic. See below.

Quoted 7 lines

The only way we can use them, as things currently stand, is as triggers for softirq work.

Is it really that troublesome to provide this kind of facility generically, rather than having various subsystems replicate such code where they want to use hrtimers and are restricted to softirqs?

Indeed this had been my concerns also, when i moved the hrtimer usage in a CAN protocol to use tasklets.

("can: update can-bcm for hrtimer hardirq callbacks")
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=6e5c172cf7ca1ab878cc6a6a4c1d52fef60f3ee0

due to

("hrtimer: removing all ur callback modes")
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=ca109491f612aab5c8152207631c0444f63da97f

I was not very amused that time and wanted to NACK that change, but Linus said:

"Quite frankly, your NAK doesn't matter.
We've had too many bugs in hrtimers. They _will_ get simplified."
(http://lkml.indiana.edu/hypermail/linux/kernel/0812.1/00218.html)

Thomas, is there chance to get this nice simple possibility back to invoke at least a hrtimer for SOFT_IRQ context additional to the current functionality??

I would expect this to save lot's of tasklet code that is - and will be - created due to the lack of the hrtimers softirq capability ...

FWIK there were really many callback modes before (per-cpu stuff and so), that were probably too much. But having a SOFT_IRQ callback mode again would really help.

Regards,
Oliver

#21 lore raw

PATCH 2/3 net: sanitize hrtimer usage in sched_cbq

In reply to Thomas Gleixner

The usage of hrtimer in cbq_ovl_delay() is less than obvious and in two aspects wrong.

The intention of the code is to arm an hrtimer with the expiry time X. If the timer is already armed the code needs to check whether the expiry time X is earlier than the expiry time of the armed timer and either keep the active timer or rearm it to X. If the timer is not armed it needs to schedule it to X. That's not what the code does.

It calls hrtimer_try_to_cancel() unconditionally and checks the return value. If the return value is non zero then it compares the expiry time of the timer with the new expiry time and picks the earlier one. The return value check does not take into account that the timer might run its callback (expressed by a return value of -1). In that case the expiry time of the timer is probably earlier than the new expiry time so it rearms the already expired timer with the expiry value in the past.

If the timer is not active (hrtimer_try_to_cancel() returns 0) it does not set the new expiry time X but instead restarts the timer with the expiry time which was active when the timer fired last. That's in the past as well.

Change the code to check whether the timer is enqueued. If it is enqueued then the expiry time of the timer is checked against the new expiry time and it only calls hrtimer_start when the new expiry time is earlier than the already armed timer. If the timer is not active then arm it unconditionally with the new expiry time.

---
 net/sched/sch_cbq.c |   21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)
net/sched/sch_cbq.c +14 -7
Index: linux-2.6/net/sched/sch_cbq.c
===================================================================
@@ -494,7 +494,6 @@ static void cbq_ovl_delay(struct cbq_cla
 
 	if (!cl->delayed) {
 		psched_time_t sched = q->now;
-		ktime_t expires;
 
 		delay += cl->offtime;
 		if (cl->avgidle < 0)
@@ -504,6 +503,7 @@ static void cbq_ovl_delay(struct cbq_cla
 		cl->undertime = q->now + delay;
 
 		if (delay > 0) {
+			ktime_t expires, actexp;
 			unsigned long flags;
 
 			spin_lock_irqsave(&q->lock, flags);
@@ -514,12 +514,19 @@ static void cbq_ovl_delay(struct cbq_cla
 
 			expires = ktime_set(0, 0);
 			expires = ktime_add_ns(expires, PSCHED_TICKS2NS(sched));
-			if (hrtimer_try_to_cancel(&q->delay_timer) &&
-			    ktime_to_ns(ktime_sub(
-					hrtimer_get_expires(&q->delay_timer),
-					expires)) > 0)
-				hrtimer_set_expires(&q->delay_timer, expires);
-			hrtimer_restart(&q->delay_timer);
+			/*
+			 * If the timer is queued check whether the
+			 * new expiry time is earlier than the current
+			 * one.
+			 */
+			if (hrtimer_is_queued(&q->delay_timer)) {
+				actexp = hrtimer_get_expires(&q->delay_timer);
+				if (expires.tv64 >= actexp.tv64)
+					expires.tv64 = 0;
+			}
+			if (expires.tv64)
+				hrtimer_start(&q->delay_timer, expires,
+					      HRTIMER_MODE_ABS);
 			cl->delayed = 1;
 			cl->xstats.overactions++;
 			spin_unlock_irqrestore(&q->lock, flags);
#22 lore raw

PATCH 3/3 net: use HRTIMER_RESTART in sched_cbq

In reply to Thomas Gleixner

Restarting a hrtimer from the callback function via hrtimer_start is inefficient. The canonical way is to modify the expiry value of the timer and return HRTIMER_RESTART to the hrtimer core code which takes care of the restart.

---
 net/sched/sch_cbq.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/sched/sch_cbq.c +4 -2
Index: linux-2.6/net/sched/sch_cbq.c
===================================================================
@@ -605,6 +605,7 @@ static enum hrtimer_restart cbq_undelay(
 	struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
 						delay_timer);
 	struct Qdisc *sch = q->watchdog.qdisc;
+	enum hrtimer_restart ret = HRTIMER_NORESTART;
 	psched_time_t now;
 	psched_tdiff_t delay = 0;
 	unsigned pmask;
@@ -634,13 +635,14 @@ static enum hrtimer_restart cbq_undelay(
 
 		time = ktime_set(0, 0);
 		time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
-		hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
+		hrtimer_set_expires(&q->delay_timer, time);
+		ret = HRTIMER_RESTART;
 	}
 	spin_unlock(&q->lock);
 
 	sch->flags &= ~TCQ_F_THROTTLED;
 	__netif_schedule(qdisc_root(sch));
-	return HRTIMER_NORESTART;
+	return ret;
 }
 
 #ifdef CONFIG_NET_CLS_ACT
maintainer
#23 lore raw
In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>
Date: Thu, 09 Jul 2009 21:59:18 -0000

Quoted 5 lines

While looking at the "Soft-Lockup/Race in networking in 2.6.31-rc1+195 ( possibly caused by netem)" issue (http://lkml.org/lkml/2009/7/2/519)
I noticed some serious problems in the hrtimer related code of net/sched/sched/sch_cbq.c.

Quoted 7 lines

The following patch series addresses these.

I'm not entirely sure whether patch [1/3] covers all possible concurrent modifications, but it fixes the most obvious ones. The remaining details are left to the networking experts.

Patches [1/3] and [2/3] might be stable material as well.

Thanks a lot for these paches Thomas, I'll look at them more closely.

maintainer
#24 lore raw
In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>
Date: Thu, 09 Jul 2009 21:59:18 -0000

Quoted 5 lines

While looking at the "Soft-Lockup/Race in networking in 2.6.31-rc1+195 ( possibly caused by netem)" issue (http://lkml.org/lkml/2009/7/2/519)
I noticed some serious problems in the hrtimer related code of net/sched/sched/sch_cbq.c.

Quoted 7 lines

The following patch series addresses these.

I'm not entirely sure whether patch [1/3] covers all possible concurrent modifications, but it fixes the most obvious ones. The remaining details are left to the networking experts.

Patches [1/3] and [2/3] might be stable material as well.

I'm holding off on this entire set until we figure out what to really do with the CBQ hrtimer situation. See my reply to patch #1, thanks.