Skip to contentSkip to conversation

hrtimer updates

PATCH In review Thomas Gleixner 2 participants 26 messages Mar 12, 2006 – Mar 18, 2006

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

cover hrtimer updates

Andrew,

please take the following patchset into -mm.

It contains most of the yet unapplied patches of Romans earlier patchset. I reworked some bits and fixed SMP and userspace return value issues.

tglx
--

#1 lore raw

PATCH 1/8 hrtimer optimize softirq runqueues

The hrtimer softirq is called from the timer softirq every tick. Retrieve the current time from xtime and wall_to_monotonic instead of calling base->get_time() for each timer base. Store the time in the base structure and provide a hook once clock source abstractions are in place and to keep the code open for new base clocks.

Based on a patch from: Roman Zippel <[email protected]>

 include/linux/hrtimer.h |   20 ++++++++++++--------
 kernel/hrtimer.c        |   28 ++++++++++++++++++++++++++--
 2 files changed, 38 insertions(+), 10 deletions(-)
kernel/hrtimer.c +26 -2
Index: linux-2.6.16-updates/kernel/hrtimer.c
===================================================================
@@ -123,6 +123,26 @@ void ktime_get_ts(struct timespec *ts)
 EXPORT_SYMBOL_GPL(ktime_get_ts);
 
 /*
+ * Get the coarse grained time at the softirq based on xtime and
+ * wall_to_monotonic.
+ */
+static void hrtimer_get_softirq_time(struct hrtimer_base *base)
+{
+	ktime_t xtim, tomono;
+	unsigned long seq;
+
+	do {
+		seq = read_seqbegin(&xtime_lock);
+		xtim = timespec_to_ktime(xtime);
+		tomono = timespec_to_ktime(wall_to_monotonic);
+
+	} while (read_seqretry(&xtime_lock, seq));
+
+	base[CLOCK_REALTIME].softirq_time = xtim;
+	base[CLOCK_MONOTONIC].softirq_time = ktime_add(xtim, tomono);
+}
+
+/*
  * Functions and macros which are different for UP/SMP systems are kept in a
  * single place
  */
@@ -586,9 +606,11 @@ int hrtimer_get_res(const clockid_t whic
  */
 static inline void run_hrtimer_queue(struct hrtimer_base *base)
 {
-	ktime_t now = base->get_time();
 	struct rb_node *node;
 
+	if (base->get_softirq_time)
+		base->softirq_time = base->get_softirq_time();
+
 	spin_lock_irq(&base->lock);
 
 	while ((node = base->first)) {
@@ -598,7 +620,7 @@ static inline void run_hrtimer_queue(str
 		void *data;
 
 		timer = rb_entry(node, struct hrtimer, node);
-		if (now.tv64 <= timer->expires.tv64)
+		if (base->softirq_time.tv64 <= timer->expires.tv64)
 			break;
 
 		fn = timer->function;
@@ -641,6 +663,8 @@ void hrtimer_run_queues(void)
 	struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
 	int i;
 
+	hrtimer_get_softirq_time(base);
+
 	for (i = 0; i < MAX_HRTIMER_BASES; i++)
 		run_hrtimer_queue(&base[i]);
 }
include/linux/hrtimer.h +12 -8
Index: linux-2.6.16-updates/include/linux/hrtimer.h
===================================================================
@@ -72,14 +72,16 @@ struct hrtimer {
 /**
  * struct hrtimer_base - the timer base for a specific clock
  *
- * @index:	clock type index for per_cpu support when moving a timer
- *		to a base on another cpu.
- * @lock:	lock protecting the base and associated timers
- * @active:	red black tree root node for the active timers
- * @first:	pointer to the timer node which expires first
- * @resolution:	the resolution of the clock, in nanoseconds
- * @get_time:	function to retrieve the current time of the clock
- * @curr_timer:	the timer which is executing a callback right now
+ * @index:		clock type index for per_cpu support when moving a timer
+ *			to a base on another cpu.
+ * @lock:		lock protecting the base and associated timers
+ * @active:		red black tree root node for the active timers
+ * @first:		pointer to the timer node which expires first
+ * @resolution:		the resolution of the clock, in nanoseconds
+ * @get_time:		function to retrieve the current time of the clock
+ * @get_sofirq_time:	function to retrieve the current time from the softirq
+ * @curr_timer:		the timer which is executing a callback right now
+ * @softirq_time:	the time when running the hrtimer queue in the softirq
  */
 struct hrtimer_base {
 	clockid_t		index;
@@ -88,7 +90,9 @@ struct hrtimer_base {
 	struct rb_node		*first;
 	ktime_t			resolution;
 	ktime_t			(*get_time)(void);
+	ktime_t			(*get_softirq_time)(void);
 	struct hrtimer		*curr_timer;
+	ktime_t			softirq_time;
 };
 
 /*

--

#2 lore raw

PATCH 2/8 Pass current time to hrtimer_forward()

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

Pass current time to hrtimer_forward(). This allows to use the softirq time in the timer base when the forward function is called from the timer callback. Other places pass current time with a call to timer->base->get_time().

 include/linux/hrtimer.h |    3 ++-
 kernel/hrtimer.c        |    7 +++----
 kernel/itimer.c         |    3 ++-
 kernel/posix-timers.c   |   14 ++++++++++----
 4 files changed, 17 insertions(+), 10 deletions(-)
include/linux/hrtimer.h +2 -1
Index: linux-2.6.16-updates/include/linux/hrtimer.h
===================================================================
@@ -130,7 +130,8 @@ static inline int hrtimer_active(const s
 }
 
 /* Forward a hrtimer so it expires after now: */
-extern unsigned long hrtimer_forward(struct hrtimer *timer, ktime_t interval);
+extern unsigned long
+hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval);
 
 /* Precise sleep: */
 extern long hrtimer_nanosleep(struct timespec *rqtp,
kernel/hrtimer.c +3 -4
Index: linux-2.6.16-updates/kernel/hrtimer.c
===================================================================
@@ -301,18 +301,17 @@ void unlock_hrtimer_base(const struct hr
  * hrtimer_forward - forward the timer expiry
  *
  * @timer:	hrtimer to forward
+ * @now:	forward past this time
  * @interval:	the interval to forward
  *
  * Forward the timer expiry so it will expire in the future.
  * Returns the number of overruns.
  */
 unsigned long
-hrtimer_forward(struct hrtimer *timer, ktime_t interval)
+hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval)
 {
 	unsigned long orun = 1;
-	ktime_t delta, now;
-
-	now = timer->base->get_time();
+	ktime_t delta;
 
 	delta = ktime_sub(now, timer->expires);
 
kernel/itimer.c +2 -1
Index: linux-2.6.16-updates/kernel/itimer.c
===================================================================
@@ -136,7 +136,8 @@ int it_real_fn(void *data)
 
 	if (tsk->signal->it_real_incr.tv64 != 0) {
 		hrtimer_forward(&tsk->signal->real_timer,
-			       tsk->signal->it_real_incr);
+				tsk->signal->real_timer.base->softirq_time,
+				tsk->signal->it_real_incr);
 
 		return HRTIMER_RESTART;
 	}
kernel/posix-timers.c +10 -4
Index: linux-2.6.16-updates/kernel/posix-timers.c
===================================================================
@@ -250,15 +250,18 @@ __initcall(init_posix_timers);
 
 static void schedule_next_timer(struct k_itimer *timr)
 {
+	struct hrtimer *timer = &timr->it.real.timer;
+
 	if (timr->it.real.interval.tv64 == 0)
 		return;
 
-	timr->it_overrun += hrtimer_forward(&timr->it.real.timer,
+	timr->it_overrun += hrtimer_forward(timer, timer->base->get_time(),
 					    timr->it.real.interval);
+
 	timr->it_overrun_last = timr->it_overrun;
 	timr->it_overrun = -1;
 	++timr->it_requeue_pending;
-	hrtimer_restart(&timr->it.real.timer);
+	hrtimer_restart(timer);
 }
 
 /*
@@ -333,6 +336,7 @@ EXPORT_SYMBOL_GPL(posix_timer_event);
 static int posix_timer_fn(void *data)
 {
 	struct k_itimer *timr = data;
+	struct hrtimer *timer = &timr->it.real.timer;
 	unsigned long flags;
 	int si_private = 0;
 	int ret = HRTIMER_NORESTART;
@@ -350,7 +354,8 @@ static int posix_timer_fn(void *data)
 		 */
 		if (timr->it.real.interval.tv64 != 0) {
 			timr->it_overrun +=
-				hrtimer_forward(&timr->it.real.timer,
+				hrtimer_forward(timer,
+						timer->base->softirq_time,
 						timr->it.real.interval);
 			ret = HRTIMER_RESTART;
 		}
@@ -621,7 +626,8 @@ common_timer_get(struct k_itimer *timr, 
 	if (timr->it_requeue_pending & REQUEUE_PENDING ||
 	    (timr->it_sigev_notify & ~SIGEV_THREAD_ID) == SIGEV_NONE) {
 		timr->it_overrun +=
-			hrtimer_forward(timer, timr->it.real.interval);
+			hrtimer_forward(timer, timer->base->get_time(),
+					timr->it.real.interval);
 		remaining = hrtimer_get_remaining(timer);
 	}
  calci:

--

#3 lore raw

PATCH 3/8 posix-timer cleanup common_timer_get()

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

Cleanup common_timer_get() a little.

 kernel/posix-timers.c |   27 ++++++++++++---------------
 1 file changed, 12 insertions(+), 15 deletions(-)
kernel/posix-timers.c +12 -15
Index: linux-2.6.16-updates/kernel/posix-timers.c
===================================================================
@@ -606,18 +606,20 @@ static struct k_itimer * lock_timer(time
 static void
 common_timer_get(struct k_itimer *timr, struct itimerspec *cur_setting)
 {
-	ktime_t remaining;
+	ktime_t now, remaining;
 	struct hrtimer *timer = &timr->it.real.timer;
 
 	memset(cur_setting, 0, sizeof(struct itimerspec));
-	remaining = hrtimer_get_remaining(timer);
 
-	/* Time left ? or timer pending */
-	if (remaining.tv64 > 0 || hrtimer_active(timer))
-		goto calci;
 	/* interval timer ? */
-	if (timr->it.real.interval.tv64 == 0)
+	if (timr->it.real.interval.tv64 == 0) {
+		cur_setting->it_interval =
+			ktime_to_timespec(timr->it.real.interval);
+	} else if (!hrtimer_active(timer))
 		return;
+
+	now = timer->base->get_time();
+
 	/*
 	 * When a requeue is pending or this is a SIGEV_NONE timer
 	 * move the expiry time forward by intervals, so expiry is >
@@ -625,16 +627,11 @@ common_timer_get(struct k_itimer *timr, 
 	 */
 	if (timr->it_requeue_pending & REQUEUE_PENDING ||
 	    (timr->it_sigev_notify & ~SIGEV_THREAD_ID) == SIGEV_NONE) {
-		timr->it_overrun +=
-			hrtimer_forward(timer, timer->base->get_time(),
-					timr->it.real.interval);
-		remaining = hrtimer_get_remaining(timer);
+		timr->it_overrun += hrtimer_forward(timer, now,
+						    timr->it.real.interval);
 	}
- calci:
-	/* interval timer ? */
-	if (timr->it.real.interval.tv64 != 0)
-		cur_setting->it_interval =
-			ktime_to_timespec(timr->it.real.interval);
+
+	remaining = ktime_sub(timer->expires, now);
 	/* Return 0 only, when the timer is expired and not pending */
 	if (remaining.tv64 <= 0)
 		cur_setting->it_value.tv_nsec = 1;

--

#4 lore raw

PATCH 4/8 hrtimer simplify nanosleep

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

nanosleep is the only user of the expired state, so let it manage this itself, which makes the hrtimer code a bit simpler. The remaining time is also only calculated if requested.

 include/linux/hrtimer.h |    4 -
 kernel/hrtimer.c        |  142 ++++++++++++++++++++----------------------------
 2 files changed, 63 insertions(+), 83 deletions(-)
include/linux/hrtimer.h +1 -3
Index: linux-2.6.16-updates/include/linux/hrtimer.h
===================================================================
@@ -38,9 +38,7 @@ enum hrtimer_restart {
  * Timer states:
  */
 enum hrtimer_state {
-	HRTIMER_INACTIVE,	/* Timer is inactive */
-	HRTIMER_EXPIRED,		/* Timer is expired */
-	HRTIMER_RUNNING,		/* Timer is running the callback function */
+	HRTIMER_INACTIVE,		/* Timer is inactive */
 	HRTIMER_PENDING,		/* Timer is pending */
 };
 
kernel/hrtimer.c +62 -80

204 lines not on this page · raw message

--

#5 lore raw

PATCH 5/8 hrtimer remove state field

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

Remove the state field and encode this information in the rb_node similiar to normal timer.

 include/linux/hrtimer.h |   11 ++---------
 kernel/hrtimer.c        |   13 ++++---------
 2 files changed, 6 insertions(+), 18 deletions(-)
include/linux/hrtimer.h +2 -9
Index: linux-2.6.16-updates/include/linux/hrtimer.h
===================================================================
@@ -34,13 +34,7 @@ enum hrtimer_restart {
 	HRTIMER_RESTART,
 };
 
-/*
- * Timer states:
- */
-enum hrtimer_state {
-	HRTIMER_INACTIVE,		/* Timer is inactive */
-	HRTIMER_PENDING,		/* Timer is pending */
-};
+#define HRTIMER_INACTIVE	((void *)1UL)
 
 struct hrtimer_base;
 
@@ -61,7 +55,6 @@ struct hrtimer_base;
 struct hrtimer {
 	struct rb_node		node;
 	ktime_t			expires;
-	enum hrtimer_state	state;
 	int			(*function)(void *);
 	void			*data;
 	struct hrtimer_base	*base;
@@ -124,7 +117,7 @@ extern ktime_t hrtimer_get_next_event(vo
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
-	return timer->state == HRTIMER_PENDING;
+	return timer->node.rb_parent != HRTIMER_INACTIVE;
 }
 
 /* Forward a hrtimer so it expires after now: */
kernel/hrtimer.c +4 -9
Index: linux-2.6.16-updates/kernel/hrtimer.c
===================================================================
@@ -374,8 +374,6 @@ static void enqueue_hrtimer(struct hrtim
 	rb_link_node(&timer->node, parent, link);
 	rb_insert_color(&timer->node, &base->active);
 
-	timer->state = HRTIMER_PENDING;
-
 	if (!base->first || timer->expires.tv64 <
 	    rb_entry(base->first, struct hrtimer, node)->expires.tv64)
 		base->first = &timer->node;
@@ -395,6 +393,7 @@ static void __remove_hrtimer(struct hrti
 	if (base->first == &timer->node)
 		base->first = rb_next(&timer->node);
 	rb_erase(&timer->node, &base->active);
+	timer->node.rb_parent = HRTIMER_INACTIVE;
 }
 
 /*
@@ -405,7 +404,6 @@ remove_hrtimer(struct hrtimer *timer, st
 {
 	if (hrtimer_active(timer)) {
 		__remove_hrtimer(timer, base);
-		timer->state = HRTIMER_INACTIVE;
 		return 1;
 	}
 	return 0;
@@ -579,6 +577,7 @@ void hrtimer_init(struct hrtimer *timer,
 		clock_id = CLOCK_MONOTONIC;
 
 	timer->base = &bases[clock_id];
+	timer->node.rb_parent = HRTIMER_INACTIVE;
 }
 
 /**
@@ -625,7 +624,6 @@ static inline void run_hrtimer_queue(str
 		fn = timer->function;
 		data = timer->data;
 		set_curr_timer(base, timer);
-		timer->state = HRTIMER_INACTIVE;
 		__remove_hrtimer(timer, base);
 		spin_unlock_irq(&base->lock);
 
@@ -633,11 +631,8 @@ static inline void run_hrtimer_queue(str
 
 		spin_lock_irq(&base->lock);
 
-		/* Another CPU has added back the timer */
-		if (timer->state != HRTIMER_INACTIVE)
-			continue;
-
-		if (restart != HRTIMER_NORESTART)
+		if (restart != HRTIMER_NORESTART &&
+		    !hrtimer_active(timer))
 			enqueue_hrtimer(timer, base);
 	}
 	set_curr_timer(base, NULL);

--

#6 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 4 lines · Thomas Gleixner
kernel/hrtimer.c +0 -0
@@ -633,11 +631,8 @@ static inline void run_hrtimer_queue(str
 
 		spin_lock_irq(&base->lock);
 

kernel/hrtimer.c static inline void run_hrtimer_queue(str · line 638

Quoted 10 lines
kernel/hrtimer.c +2 -5
-		/* Another CPU has added back the timer */
-		if (timer->state != HRTIMER_INACTIVE)
-			continue;
-
-		if (restart != HRTIMER_NORESTART)
+		if (restart != HRTIMER_NORESTART &&
+		    !hrtimer_active(timer))
 			enqueue_hrtimer(timer, base);
 	}
 	set_curr_timer(base, NULL);

BTW the active check can be removed again, as it was added for a state machine problem, I only didn't want to remove it for 2.6.16.

bye, Roman

#7 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 15 lines · Roman Zippel

kernel/hrtimer.c static inline void run_hrtimer_queue(str · line 638

Quoted 12 lines
kernel/hrtimer.c +2 -5
 		spin_lock_irq(&base->lock);
 
-		/* Another CPU has added back the timer */
-		if (timer->state != HRTIMER_INACTIVE)
-			continue;
-
-		if (restart != HRTIMER_NORESTART)
+		if (restart != HRTIMER_NORESTART &&
+		    !hrtimer_active(timer))
 			enqueue_hrtimer(timer, base);
 	}
 	set_curr_timer(base, NULL);

BTW the active check can be removed again, as it was added for a state machine problem, I only didn't want to remove it for 2.6.16.

The check can not be removed. The reason why it was added is still the same.

It has nothing to do with a state machine. It's a simple SMP locking issue.

softirq runs on CPU0
base->lock()

remove_timer(timer);

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.
requeue = timer->fn();

base->lock()

if (requeue)
enqueue_timer(timer)

--> OOPS

We can not wait in the signal delivery path until the callback has been executed, as we hold the posix-timer->lock and this would deadlock timer->fn().

tglx

#8 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 21 lines · Thomas Gleixner
Quoted 2 lines

BTW the active check can be removed again, as it was added for a state machine problem, I only didn't want to remove it for 2.6.16.

The check can not be removed. The reason why it was added is still the same.

It has nothing to do with a state machine. It's a simple SMP locking issue.

softirq runs on CPU0
base->lock()

remove_timer(timer);

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.
requeue = timer->fn();

base->lock()

Quoted 8 lines

if (requeue)
enqueue_timer(timer)

--> OOPS

We can not wait in the signal delivery path until the callback has been executed, as we hold the posix-timer->lock and this would deadlock timer->fn().

posix_timer either restarts the timer directly or via signal delivery, but never both, so this case can't happen (unless there is a bug in the posix_timer).

bye, Roman

#9 lore raw

Re: [patch 5/8] hrtimer remove state field

Roman,

I looked up the exact problem again.

Quoted 8 lines · Roman Zippel
Quoted 8 lines

softirq runs on CPU0
base->lock()

remove_timer(timer);

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.

		------->  sig_ignore is set
Quoted 9 lines
Quoted 9 lines

requeue = timer->fn();

base->lock()

if (requeue)
enqueue_timer(timer)

--> OOPS

Quoted 7 lines
Quoted 3 lines

We can not wait in the signal delivery path until the callback has been executed, as we hold the posix-timer->lock and this would deadlock timer->fn().

posix_timer either restarts the timer directly or via signal delivery, but never both, so this case can't happen (unless there is a bug in the posix_timer).

It took quite a time to track this down. Its unlikely, but it _CAN_ happen !

tglx

#10 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 11 lines · Thomas Gleixner
Quoted 8 lines · Roman Zippel
Quoted 8 lines

softirq runs on CPU0
base->lock()

remove_timer(timer);

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.

		------->  sig_ignore is set

??? I can't find any symbol 'sig_ignore'.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

requeue = timer->fn();

base->lock()

if (requeue)
enqueue_timer(timer)

What actually happened is that requeue is false and in the meantime the timer was restarted on another cpu via signal delivery and run_hrtimer_queue would set the state to expired, while the timer was still active -> OOPS.

bye, Roman

#11 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 10 lines · Roman Zippel

Hi,

Quoted 6 lines · Thomas Gleixner
Quoted 5 lines · Roman Zippel
Quoted 5 lines

softirq runs on CPU0
base->lock()

remove_timer(timer);

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.

		------->  sig_ignore is set

??? I can't find any symbol 'sig_ignore'.

Oh well. The application sets SIG_IGN for the signal in question, so send_sigqueue() returns 1 because sig_ignored() returns 1.

Sorry for being imprecise.

tglx

#12 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 10 lines · Thomas Gleixner
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.

		------->  sig_ignore is set

??? I can't find any symbol 'sig_ignore'.

Oh well. The application sets SIG_IGN for the signal in question, so send_sigqueue() returns 1 because sig_ignored() returns 1.

In this case no signal is queued and the timer won't be restarted via signal delivery.

bye, Roman

#13 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 10 lines · Roman Zippel

Hi,

Quoted 6 lines · Thomas Gleixner
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines

base->unlock()
signal of previous expiry is delivered on CPU1 timer is reqeued.

		------->  sig_ignore is set
Quoted 7 lines
Quoted 4 lines
Quoted 1 line

??? I can't find any symbol 'sig_ignore'.

Oh well. The application sets SIG_IGN for the signal in question, so send_sigqueue() returns 1 because sig_ignored() returns 1.

In this case no signal is queued and the timer won't be restarted via signal delivery.

Roman,

Interrupts are enable before fn() is called, so an interrupt can actually delay it long enough that userspace on CPU1 can set SIG_IGN

CPU 0
spin_unlock_irq(base->lock)
CPU1
signal is dequeued
timer is requeued
user space code is executed user space code sets SIG_IGN
restart = fn();

Now fn() calls send_sigqeue() which returns 1, resulting in ret = HRTIMER_RESTART which leads to requeueing of an enqueued timer.

tglx

#14 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 17 lines · Thomas Gleixner
Quoted 2 lines

In this case no signal is queued and the timer won't be restarted via signal delivery.

Roman,

Interrupts are enable before fn() is called, so an interrupt can actually delay it long enough that userspace on CPU1 can set SIG_IGN

CPU 0
spin_unlock_irq(base->lock)
CPU1
signal is dequeued
timer is requeued
user space code is executed user space code sets SIG_IGN
restart = fn();

Quoted 2 lines

Now fn() calls send_sigqeue() which returns 1, resulting in ret = HRTIMER_RESTART which leads to requeueing of an enqueued timer.

I'm not quite sure I follow, when the timer is running no signal should be queued, so nothing can be dequeued and no new timer can be requeued. If that somehow is possible (although I don't see how), you'd found a bug in the signal/posix timer code, which should not be worked around in the hrtimer run queue.

bye, Roman

#15 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 10 lines · Roman Zippel
Quoted 10 lines

CPU 0
spin_unlock_irq(base->lock)
CPU1
signal is dequeued
timer is requeued
user space code is executed user space code sets SIG_IGN
restart = fn();

Quoted 8 lines
Quoted 2 lines

Now fn() calls send_sigqeue() which returns 1, resulting in ret = HRTIMER_RESTART which leads to requeueing of an enqueued timer.

I'm not quite sure I follow, when the timer is running no signal should be queued, so nothing can be dequeued and no new timer can be requeued. If that somehow is possible (although I don't see how), you'd found a bug in the signal/posix timer code, which should not be worked around in the hrtimer run queue.

How do you want to prevent that a signal is dequeued on one CPU while the softirq expires the timer on another CPU ? This can not be prevented.

Of course we can check hrtimer_active() in posix_timer_fn(), but I have to check if there is a problem the other way round. I cook up a patch.

tglx

#16 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 3 lines · Thomas Gleixner

How do you want to prevent that a signal is dequeued on one CPU while the softirq expires the timer on another CPU ? This can not be prevented.

This should not be possible in first place, otherwise it's a bug. The original problem was a broken state machine, is that so hard to believe? If there is another problem, please provide more details.

bye, Roman

#17 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 11 lines · Roman Zippel

Hi,

Quoted 3 lines · Thomas Gleixner

How do you want to prevent that a signal is dequeued on one CPU while the softirq expires the timer on another CPU ? This can not be prevented.

This should not be possible in first place, otherwise it's a bug. The original problem was a broken state machine, is that so hard to believe? If there is another problem, please provide more details.

Roman,

there was a state machine problem caused by something similar.

But the problem I described now happened with the current patch queue - without the hrtimer_active() check. I have no direct access to the machine which lets this surface and I just tried to reconstruct the scenario from the sparse information which was provided by the customer. All I can tell, that it is related to something similar and a requeue happens where none should happen.

I agree, that it should not be handled in the hrtimer code. It has to be fixed in the posix-timer code.

I make the check a BUG_ON(!hrtimer_active(timer) so it might show up in -mm again. Ok ?

tglx

#18 lore raw

PATCH 1/1 hrtimer remove replace state check by BUG_ON

The rework of the hrtimer code showed a hard to track sporadic problem on a testers machine. The !hrtimer_active check in the return path of the timer callback function prevents requeueing of an enqueued timer. Replace the check by a BUG_ON to get more info about this not yet verified problem instead of hiding it away.

kernel/hrtimer.c +3 -2
Index: linux-2.6.16-updates/kernel/hrtimer.c
===================================================================
@@ -631,9 +631,10 @@ static inline void run_hrtimer_queue(str
 
 		spin_lock_irq(&base->lock);
 
-		if (restart != HRTIMER_NORESTART &&
-		    !hrtimer_active(timer))
+		if (restart != HRTIMER_NORESTART) {
+			BUG_ON(hrtimer_active(timer));
 			enqueue_hrtimer(timer, base);
+		}
 	}
 	set_curr_timer(base, NULL);
 	spin_unlock_irq(&base->lock);
#19 lore raw

Re: [patch 5/8] hrtimer remove state field

In reply to Thomas Gleixner

Hi,

Quoted 6 lines · Thomas Gleixner

But the problem I described now happened with the current patch queue - without the hrtimer_active() check. I have no direct access to the machine which lets this surface and I just tried to reconstruct the scenario from the sparse information which was provided by the customer. All I can tell, that it is related to something similar and a requeue happens where none should happen.

I have an idea what might have happened. You don't advance the pending state, if the signal isn't queued, so that the pending state is screwed up afterwards. Although I don't see how it could crash the kernel (it has only the potential to mess up the timer queue via hrtimer_forward() a bit), but I don't know what other patches were applied.

Quoted 2 lines

I make the check a BUG_ON(!hrtimer_active(timer) so it might show up in -mm again. Ok ?

That's fine.
The point is that it's currently not needed to allow the user this behaviour. It's a bit unfortunate that such API details were not discussed before it got merged - users have a tendency to (ab)use a system in the least expected way (especially if they somehow gotten the idea it's much better than the old stuff in every way).
For example no current user restarts an active timer, which could be used to simplify the locking. If we tightened a bit what a user is allowed to do, we could gain flexibility on the other side, e.g. allow drivers to create timer sources or how to integrate cpu timer.

bye, Roman

kernel/posix-timers.c +1 -0
Index: linux-2.6-git/kernel/posix-timers.c
===================================================================
@@ -353,6 +353,7 @@
 				hrtimer_forward(&timr->it.real.timer,
 						timr->it.real.interval);
 			ret = HRTIMER_RESTART;
+			++timr->it_requeue_pending;
 		}
 	}
 
#20 lore raw

Re: [patch 5/8] hrtimer remove state field

Roman,

Quoted 5 lines

I have an idea what might have happened. You don't advance the pending state, if the signal isn't queued, so that the pending state is screwed up afterwards. Although I don't see how it could crash the kernel (it has only the potential to mess up the timer queue via hrtimer_forward() a bit), but I don't know what other patches were applied.

Good catch, but I dont see how it would trigger the bug.

Quoted 2 lines

For example no current user restarts an active timer, which could be used to simplify the locking.

How does this simplify the locking ? It just removes the hrtimer_cancel() call in hrtimer_start() and makes the switch_hrtimer_base() code a bit simpler.

The general locking rules would be still the same and I dont see increased flexibility at all.

Quoted 3 lines

If we tightened a bit what a user is allowed to
do, we could gain flexibility on the other side, e.g. allow drivers to create timer sources or how to integrate cpu timer.

-ENOPARSE. Can you please explain what "allow drivers to create timer sources" means and why the above locking is in the way ?

tglx

#21 lore raw

Re: [patch 5/8] hrtimer remove state field

Hi,

Quoted 9 lines · Thomas Gleixner
Quoted 2 lines

For example no current user restarts an active timer, which could be used to simplify the locking.

How does this simplify the locking ? It just removes the hrtimer_cancel() call in hrtimer_start() and makes the switch_hrtimer_base() code a bit simpler.

The general locking rules would be still the same and I dont see increased flexibility at all.

Current users already do the serialize the calls into hrtimer themselves (stopping and restarting), which can make the locking even simpler.

Quoted 6 lines
Quoted 3 lines

If we tightened a bit what a user is allowed to
do, we could gain flexibility on the other side, e.g. allow drivers to create timer sources or how to integrate cpu timer.

-ENOPARSE. Can you please explain what "allow drivers to create timer sources" means and why the above locking is in the way ?

For example dynamically attaching a timer_base to a clock source (e.g. to create a monotonic timer independent of NTP adjustments). Right now as soon as any timer_base is active it cannot be deconfigured again due to pointers to it from timers, so this would require different locking.

bye, Roman

#22 lore raw

Re: [patch 5/8] hrtimer remove state field

Quoted 5 lines · Roman Zippel
Quoted 2 lines

The general locking rules would be still the same and I dont see increased flexibility at all.

Current users already do the serialize the calls into hrtimer themselves (stopping and restarting), which can make the locking even simpler.

Serialization of the users does not help for protecting the timer queues especially not on SMP.

Can you please give a real example how to simplify this. Nobody has any objections to simplify locking when possible. But unproven claims in repeated form do not help. After a while they just get annoying.

Quoted 11 lines
Quoted 6 lines
Quoted 3 lines

If we tightened a bit what a user is allowed to
do, we could gain flexibility on the other side, e.g. allow drivers to create timer sources or how to integrate cpu timer.

-ENOPARSE. Can you please explain what "allow drivers to create timer sources" means and why the above locking is in the way ?

For example dynamically attaching a timer_base to a clock source (e.g. to create a monotonic timer independent of NTP adjustments). Right now as soon as any timer_base is active it cannot be deconfigured again due to pointers to it from timers, so this would require different locking.

I do not really understand what you want to achieve.

Timer bases are related to clock sources. You can switch the clock source of the CLOCK_MONOTONIC timer base at any given time to a different one which is not NTP adjusted. Where is the problem?

The timer base does not care about the underlying clock source at all. All it knows of it is the function which reads the current time related to this clock. When the underlying clock changes the way it generates current time then the timer base does not care at all.

This is not a problem of hrtimers. Its a problem of the clock source abstraction layer like John Stultz GTOD framework.

If you want to have timer bases with dynamic clock sources which can go away then you have to take care of much more than locking. But I really do not see a need for this.

tglx

#23 lore raw

PATCH 6/8 Remove it_real_value calculation from proc/*/stat

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

Remove the it_real_value from /proc/*/stat, during 1.2.x was the last time it returned useful data (as it was directly maintained by the scheduler), now it's only a waste of time to calculate it. Return 0 instead.

 fs/proc/array.c |    5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
fs/proc/array.c +1 -4
Index: linux-2.6.16-updates/fs/proc/array.c
===================================================================
@@ -330,7 +330,6 @@ static int do_task_stat(struct task_stru
 	unsigned long  min_flt = 0,  maj_flt = 0;
 	cputime_t cutime, cstime, utime, stime;
 	unsigned long rsslim = 0;
-	DEFINE_KTIME(it_real_value);
 	struct task_struct *t;
 	char tcomm[sizeof(task->comm)];
 
@@ -386,7 +385,6 @@ static int do_task_stat(struct task_stru
 			utime = cputime_add(utime, task->signal->utime);
 			stime = cputime_add(stime, task->signal->stime);
 		}
-		it_real_value = task->signal->real_timer.expires;
 	}
 	ppid = pid_alive(task) ? task->group_leader->real_parent->tgid : 0;
 	read_unlock(&tasklist_lock);
@@ -413,7 +411,7 @@ static int do_task_stat(struct task_stru
 	start_time = nsec_to_clock_t(start_time);
 
 	res = sprintf(buffer,"%d (%s) %c %d %d %d %d %d %lu %lu \
-%lu %lu %lu %lu %lu %ld %ld %ld %ld %d %ld %llu %lu %ld %lu %lu %lu %lu %lu \
+%lu %lu %lu %lu %lu %ld %ld %ld %ld %d 0 %llu %lu %ld %lu %lu %lu %lu %lu \
 %lu %lu %lu %lu %lu %lu %lu %lu %d %d %lu %lu\n",
 		task->pid,
 		tcomm,
@@ -435,7 +433,6 @@ static int do_task_stat(struct task_stru
 		priority,
 		nice,
 		num_threads,
-		(long) ktime_to_clock_t(it_real_value),
 		start_time,
 		vsize,
 		mm ? get_mm_rss(mm) : 0,

--

#24 lore raw

PATCH 7/8 Remove DEFINE_KTIME and ktime_to_clock_t()

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

Now that it_real_value is gone, the last user of DEFINE_KTIME and ktime_to_clock_t are also gone, so remove it before someone starts using it again.

 include/linux/ktime.h |   20 --------------------
 1 file changed, 20 deletions(-)
include/linux/ktime.h +0 -20
Index: linux-2.6.16-updates/include/linux/ktime.h
===================================================================
@@ -64,9 +64,6 @@ typedef union {
 
 #if (BITS_PER_LONG == 64) || defined(CONFIG_KTIME_SCALAR)
 
-/* Define a ktime_t variable and initialize it to zero: */
-#define DEFINE_KTIME(kt)		ktime_t kt = { .tv64 = 0 }
-
 /**
  * ktime_set - Set a ktime_t variable from a seconds/nanoseconds value
  *
@@ -113,9 +110,6 @@ static inline ktime_t timeval_to_ktime(s
 /* Map the ktime_t to timeval conversion to ns_to_timeval function */
 #define ktime_to_timeval(kt)		ns_to_timeval((kt).tv64)
 
-/* Map the ktime_t to clock_t conversion to the inline in jiffies.h: */
-#define ktime_to_clock_t(kt)		nsec_to_clock_t((kt).tv64)
-
 /* Convert ktime_t to nanoseconds - NOP in the scalar storage format: */
 #define ktime_to_ns(kt)			((kt).tv64)
 
@@ -136,9 +130,6 @@ static inline ktime_t timeval_to_ktime(s
  *   tv.sec < 0 and 0 >= tv.nsec < NSEC_PER_SEC
  */
 
-/* Define a ktime_t variable and initialize it to zero: */
-#define DEFINE_KTIME(kt)		ktime_t kt = { .tv64 = 0 }
-
 /* Set a ktime_t variable to a value in sec/nsec representation: */
 static inline ktime_t ktime_set(const long secs, const unsigned long nsecs)
 {
@@ -255,17 +246,6 @@ static inline struct timeval ktime_to_ti
 }
 
 /**
- * ktime_to_clock_t - convert a ktime_t variable to clock_t format
- * @kt:		the ktime_t variable to convert
- *
- * Returns a clock_t variable with the converted value
- */
-static inline clock_t ktime_to_clock_t(const ktime_t kt)
-{
-	return nsec_to_clock_t( (u64) kt.tv.sec * NSEC_PER_SEC + kt.tv.nsec);
-}
-
-/**
  * ktime_to_ns - convert a ktime_t variable to scalar nanoseconds
  * @kt:		the ktime_t variable to convert
  *

--

#25 lore raw

PATCH 8/8 Remove nsec_t typedef

In reply to Thomas Gleixner

From: Roman Zippel <[email protected]>

nsec_t predates ktime_t and has mostly been superseded by it. In the few places that are left it's better to make it explicit that we're dealing with 64 bit values here.

 include/linux/time.h |   18 ++++++------------
 kernel/time.c        |    4 ++--
 2 files changed, 8 insertions(+), 14 deletions(-)
include/linux/time.h +6 -12
Index: linux-2.6.16-updates/include/linux/time.h
===================================================================
@@ -73,12 +73,6 @@ extern void set_normalized_timespec(stru
 #define timespec_valid(ts) \
 	(((ts)->tv_sec >= 0) && (((unsigned long) (ts)->tv_nsec) < NSEC_PER_SEC))
 
-/*
- * 64-bit nanosec type. Large enough to span 292+ years in nanosecond
- * resolution. Ought to be enough for a while.
- */
-typedef s64 nsec_t;
-
 extern struct timespec xtime;
 extern struct timespec wall_to_monotonic;
 extern seqlock_t xtime_lock;
@@ -113,9 +107,9 @@ extern struct timespec timespec_trunc(st
  * Returns the scalar nanosecond representation of the timespec
  * parameter.
  */
-static inline nsec_t timespec_to_ns(const struct timespec *ts)
+static inline s64 timespec_to_ns(const struct timespec *ts)
 {
-	return ((nsec_t) ts->tv_sec * NSEC_PER_SEC) + ts->tv_nsec;
+	return ((s64) ts->tv_sec * NSEC_PER_SEC) + ts->tv_nsec;
 }
 
 /**
@@ -125,9 +119,9 @@ static inline nsec_t timespec_to_ns(cons
  * Returns the scalar nanosecond representation of the timeval
  * parameter.
  */
-static inline nsec_t timeval_to_ns(const struct timeval *tv)
+static inline s64 timeval_to_ns(const struct timeval *tv)
 {
-	return ((nsec_t) tv->tv_sec * NSEC_PER_SEC) +
+	return ((s64) tv->tv_sec * NSEC_PER_SEC) +
 		tv->tv_usec * NSEC_PER_USEC;
 }
 
@@ -137,7 +131,7 @@ static inline nsec_t timeval_to_ns(const
  *
  * Returns the timespec representation of the nsec parameter.
  */
-extern struct timespec ns_to_timespec(const nsec_t nsec);
+extern struct timespec ns_to_timespec(const s64 nsec);
 
 /**
  * ns_to_timeval - Convert nanoseconds to timeval
@@ -145,7 +139,7 @@ extern struct timespec ns_to_timespec(co
  *
  * Returns the timeval representation of the nsec parameter.
  */
-extern struct timeval ns_to_timeval(const nsec_t nsec);
+extern struct timeval ns_to_timeval(const s64 nsec);
 
 #endif /* __KERNEL__ */
 
kernel/time.c +2 -2
Index: linux-2.6.16-updates/kernel/time.c
===================================================================
@@ -637,7 +637,7 @@ void set_normalized_timespec(struct time
  *
  * Returns the timespec representation of the nsec parameter.
  */
-struct timespec ns_to_timespec(const nsec_t nsec)
+struct timespec ns_to_timespec(const s64 nsec)
 {
 	struct timespec ts;
 
@@ -657,7 +657,7 @@ struct timespec ns_to_timespec(const nse
  *
  * Returns the timeval representation of the nsec parameter.
  */
-struct timeval ns_to_timeval(const nsec_t nsec)
+struct timeval ns_to_timeval(const s64 nsec)
 {
 	struct timespec ts = ns_to_timespec(nsec);
 	struct timeval tv;
kernel/hrtimer.c +2 -2
Index: linux-2.6.16-updates/kernel/hrtimer.c
===================================================================
@@ -266,7 +266,7 @@ ktime_t ktime_add_ns(const ktime_t kt, u
 /*
  * Divide a ktime value by a nanosecond value
  */
-static unsigned long ktime_divns(const ktime_t kt, nsec_t div)
+static unsigned long ktime_divns(const ktime_t kt, s64 div)
 {
 	u64 dclc, inc, dns;
 	int sft = 0;
@@ -322,7 +322,7 @@ hrtimer_forward(struct hrtimer *timer, k
 		interval.tv64 = timer->base->resolution.tv64;
 
 	if (unlikely(delta.tv64 >= interval.tv64)) {
-		nsec_t incr = ktime_to_ns(interval);
+		s64 incr = ktime_to_ns(interval);
 
 		orun = ktime_divns(delta, incr);
 		timer->expires = ktime_add_ns(timer->expires, incr * orun);

--