Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Thomas Gleixner]

> +#ifdef CONFIG_NO_IDLE_HZ
> +/**
> + * hrtimer_get_next - get next hrtimer to expire
> + *
> + * @bases:	ktimer base array
> + */
> +static inline struct hrtimer *hrtimer_get_next(struct hrtimer_base *bases)
> +{
> +	unsigned long flags;
> +	struct hrtimer *timer = NULL;
> +	int i;
> +
> +	for (i = 0; i < MAX_HRTIMER_BASES; i++) {
> +		struct hrtimer_base *base;
> +		struct hrtimer *cur;
> +
> +		base = &bases[i];
> +		spin_lock_irqsave(&base->lock, flags);
> +		cur = rb_entry(base->first, struct hrtimer, node);
> +		spin_unlock_irqrestore(&base->lock, flags);
> +
> +		if (cur == NULL)
> +			continue;
> +
> +		if (timer == NULL || cur->expires.tv64 < timer->expires.tv64)
> +			timer = cur;
> +	}
> +
> +	return timer;
> +}

This is racy on SMP. nanosleep hrtimers are on the stack and can go away
due to a signal. posix timers can be removed and destroyed on another
CPU.

Also the expires fields of CLOCK_MONOTONIC and CLOCK_REALTIME based
tiemrs can not really be compared. Expiry value is absolute time of the
respective base clock.

> +/**
> + * ktime_to_jiffies - converts ktime to jiffies
> + *
> + * @event:	ktime event to be converted to jiffies
> + *
> + * Caller must take care of xtime locking.
> + */
> +static inline unsigned long ktime_to_jiffies(const ktime_t event)
> +{
> +	ktime_t now, delta;
> +
> +	now = timespec_to_ktime(xtime);
> +	delta = ktime_sub(event, now);
> +
> +	return jiffies + (((delta.tv64 * NSEC_CONVERSION) >>
> +			(NSEC_JIFFIE_SC - SEC_JIFFIE_SC)) >> SEC_JIFFIE_SC);
> +}

Only CLOCK_REALTIME based timers are based on xtime. For CLOCK_MONOTONIC
based timers this calculation is off by wall_to_monotonic.

> +/**
> + * hrtimer_next_jiffie - get next hrtimer event in jiffies
> + *
> + * Called from next_timer_interrupt() to get the next hrtimer event.
> + * Eventually we should change next_timer_interrupt() to return
> + * results in nanoseconds instead of jiffies. Caller must host xtime_lock.

S390 does not hold xtime lock when calling next_timer_interrupt !

I look for a sane solution.

	tglx

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Tony Lindgren]

* Thomas Gleixner <tglx@linutronix.de> [060225 08:16]:
> > +#ifdef CONFIG_NO_IDLE_HZ
> > +/**
> > + * hrtimer_get_next - get next hrtimer to expire
> > + *
> > + * @bases:	ktimer base array
> > + */
> > +static inline struct hrtimer *hrtimer_get_next(struct hrtimer_base *bases)
> > +{
> > +	unsigned long flags;
> > +	struct hrtimer *timer = NULL;
> > +	int i;
> > +
> > +	for (i = 0; i < MAX_HRTIMER_BASES; i++) {
> > +		struct hrtimer_base *base;
> > +		struct hrtimer *cur;
> > +
> > +		base = &bases[i];
> > +		spin_lock_irqsave(&base->lock, flags);
> > +		cur = rb_entry(base->first, struct hrtimer, node);
> > +		spin_unlock_irqrestore(&base->lock, flags);
> > +
> > +		if (cur == NULL)
> > +			continue;
> > +
> > +		if (timer == NULL || cur->expires.tv64 < timer->expires.tv64)
> > +			timer = cur;
> > +	}
> > +
> > +	return timer;
> > +}
> 
> This is racy on SMP. nanosleep hrtimers are on the stack and can go away
> due to a signal. posix timers can be removed and destroyed on another
> CPU.

This should be fixed. But just as a note, we can tolerate some removed
timer values values as it would be just an extra timer interrupt.
 
> Also the expires fields of CLOCK_MONOTONIC and CLOCK_REALTIME based
> tiemrs can not really be compared. Expiry value is absolute time of the
> respective base clock.

OK. How can we get the first event in nanoseconds easily?
 
> > +/**
> > + * ktime_to_jiffies - converts ktime to jiffies
> > + *
> > + * @event:	ktime event to be converted to jiffies
> > + *
> > + * Caller must take care of xtime locking.
> > + */
> > +static inline unsigned long ktime_to_jiffies(const ktime_t event)
> > +{
> > +	ktime_t now, delta;
> > +
> > +	now = timespec_to_ktime(xtime);
> > +	delta = ktime_sub(event, now);
> > +
> > +	return jiffies + (((delta.tv64 * NSEC_CONVERSION) >>
> > +			(NSEC_JIFFIE_SC - SEC_JIFFIE_SC)) >> SEC_JIFFIE_SC);
> > +}
> 
> Only CLOCK_REALTIME based timers are based on xtime. For CLOCK_MONOTONIC
> based timers this calculation is off by wall_to_monotonic.

Needs to be fixed then.
 
> > +/**
> > + * hrtimer_next_jiffie - get next hrtimer event in jiffies
> > + *
> > + * Called from next_timer_interrupt() to get the next hrtimer event.
> > + * Eventually we should change next_timer_interrupt() to return
> > + * results in nanoseconds instead of jiffies. Caller must host xtime_lock.
> 
> S390 does not hold xtime lock when calling next_timer_interrupt !

Good point. Needs to be fixed.
 
> I look for a sane solution.

We really should fix this for 2.6.16. Then maybe after 2.6.16 we can
convert next_timer_interrupt() to return nanosecond instead of jiffies.
And then we can get rid of jiffies again in the hrtimer code :)

Tony

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Tony Lindgren]

[-- Attachment #1: Type: text/plain, Size: 337 bytes --]

Hi all,

Here's take 3 for comments and testing. It should fix the issues
mentioned by Thomas Gleixner.

I've changed ARM xtime_lock to read lock, but now there's a slight
chance that an interrupt adds a timer after next_timer_interrupt() is
called and before timer is reprogrammed. I believe s390 also has this
problem.

Regards,

Tony

[-- Attachment #2: patch-hrtimer-dyntick --]
[-- Type: text/plain, Size: 4938 bytes --]

This patch adds support for hrtimer to next_timer_interrupt()
and fixes current breakage.

Function next_timer_interrupt() got broken with a recent patch
6ba1b91213e81aa92b5cf7539f7d2a94ff54947c as sys_nanosleep() was
moved to hrtimer. This broke things as next_timer_interrupt()
did not check hrtimer tree for next event.

Function next_timer_interrupt() is needed with dyntick
(CONFIG_NO_IDLE_HZ, VST) implementations, as the system can
be in idle when next hrtimer event was supposed to happen.
At least ARM and S390 currently use next_timer_interrupt(). 

Signed-off-by: Tony Lindgren <tony@atomide.com>

--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -505,6 +505,106 @@
 	return rem;
 }
 
+#ifdef CONFIG_NO_IDLE_HZ
+
+/**
+ * hrtimer_get_next_offset - get next hrtimer to expire in ktime_t from now
+ *
+ * @offset:	pointer for next event offset
+ *
+ * Note that the timer event may get removed, so the result is not guaranteed
+ * to be correct. Nanosleep hrtimers are on the stack and can go away due to
+ * a signal, and posix timers can be removed and destroyed on another CPU.
+ * For next_timer_interrupt() this should be OK, as it causes just an extra
+ * timer interrupt.
+ */
+static inline int hrtimer_get_next_offset(ktime_t *offset)
+{
+	struct hrtimer_base *bases = __get_cpu_var(hrtimer_bases);
+	unsigned long flags;
+	int i, ret = -EAGAIN;
+
+	if (bases == NULL)
+		return ret;
+
+	offset->tv64 = KTIME_MAX;
+
+	for (i = 0; i < MAX_HRTIMER_BASES; i++) {
+		struct hrtimer_base *base;
+		struct rb_node *node;
+		struct hrtimer *timer;
+		ktime_t delta, now;
+
+		base = &bases[i];
+		now = base->get_time();
+		spin_lock_irqsave(&base->lock, flags);
+		if ((node = base->first) != NULL) {
+			timer = rb_entry(node, struct hrtimer, node);
+			delta = ktime_sub(timer->expires, now);
+
+			if (delta.tv64 <= 0) {
+				spin_unlock_irqrestore(&base->lock, flags);
+				continue;
+			}
+
+			if (delta.tv64 <= offset->tv64) {
+				offset->tv64 = delta.tv64;
+				ret = 0;
+			}
+		}
+		spin_unlock_irqrestore(&base->lock, flags);
+	}
+
+	return ret;
+}
+
+/**
+ * ktime_offset_to_jiffies - converts ktime to jiffies
+ *
+ * @offset:	ktime event offset to be converted to jiffies
+ *
+ * Note that this function should not be needed once next_timer_interrupt()
+ * is converted to return nsecs instead of jiffies.
+ */
+static inline unsigned long ktime_offset_to_jiffies(const ktime_t offset)
+{
+	unsigned long timer_jiffies;
+
+	if (offset.tv64 <= 0)
+		return jiffies + 1;
+
+	timer_jiffies = (unsigned long)(((offset.tv64 * NSEC_CONVERSION) >>
+				(NSEC_JIFFIE_SC - SEC_JIFFIE_SC)) >> SEC_JIFFIE_SC);
+
+	if (timer_jiffies < 1)
+		timer_jiffies = 1;
+
+	return jiffies + timer_jiffies;
+}
+
+/**
+ * hrtimer_next_jiffie - translates next hrtimer event into jiffies
+ *
+ * Called from next_timer_interrupt() to get the next hrtimer event.
+ * Eventually we should change next_timer_interrupt() to return
+ * results in nanoseconds instead of jiffies.
+ */
+int hrtimer_next_jiffie(unsigned long *next_jiffie)
+{
+	ktime_t offset;
+	int ret;
+
+	ret = hrtimer_get_next_offset(&offset);
+	if (ret != 0)
+		return ret;
+
+	*next_jiffie = ktime_offset_to_jiffies(offset);
+
+	return 0;
+}
+
+#endif
+
 /**
  * hrtimer_init - initialize a timer to the given clock
  *
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -489,9 +489,15 @@
 	struct list_head *list;
 	struct timer_list *nte;
 	unsigned long expires;
+	unsigned long hr_expires = jiffies + 10 * HZ;	/* Anything far ahead */
 	tvec_t *varray[4];
 	int i, j;
 
+	/* Look for timer events in hrtimer. */
+	if ((hrtimer_next_jiffie(&hr_expires) == 0)
+		&& (time_before(hr_expires, jiffies + 2)))
+			return hr_expires;
+
 	base = &__get_cpu_var(tvec_bases);
 	spin_lock(&base->t_base.lock);
 	expires = base->timer_jiffies + (LONG_MAX >> 1);
@@ -542,6 +548,10 @@
 		}
 	}
 	spin_unlock(&base->t_base.lock);
+
+	if (time_before(hr_expires, expires))
+		expires = hr_expires;
+
 	return expires;
 }
 #endif
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -115,6 +115,7 @@
 /* Query timers: */
 extern ktime_t hrtimer_get_remaining(const struct hrtimer *timer);
 extern int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp);
+extern int hrtimer_next_jiffie(unsigned long *next_jiffie);
 
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
--- a/arch/arm/kernel/time.c
+++ b/arch/arm/kernel/time.c
@@ -422,12 +422,14 @@
 void timer_dyn_reprogram(void)
 {
 	struct dyn_tick_timer *dyn_tick = system_timer->dyn_tick;
+	unsigned long next, seq;
 
-	if (dyn_tick) {
-		write_seqlock(&xtime_lock);
-		if (dyn_tick->state & DYN_TICK_ENABLED)
+	if (dyn_tick && (dyn_tick->state & DYN_TICK_ENABLED)) {
+		next = next_timer_interrupt();
+		do {
+			seq = read_seqbegin(&xtime_lock);
 			dyn_tick->reprogram(next_timer_interrupt() - jiffies);
-		write_sequnlock(&xtime_lock);
+		} while (read_seqretry(&xtime_lock, seq));
 	}
 }
 

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Thomas Gleixner]

On Mon, 2006-02-27 at 19:29 -0800, Tony Lindgren wrote:
> I've changed ARM xtime_lock to read lock, but now there's a slight
> chance that an interrupt adds a timer after next_timer_interrupt() is
> called and before timer is reprogrammed. I believe s390 also has this
> problem.

This needs a more generalized solution later, but I picked up your ARM
change and simplified the hrtimer related bits.

	tglx


Index: 2.6.16-rc4-git/arch/arm/kernel/time.c
===================================================================
--- 2.6.16-rc4-git.orig/arch/arm/kernel/time.c
+++ 2.6.16-rc4-git/arch/arm/kernel/time.c
@@ -422,12 +422,14 @@ static int timer_dyn_tick_disable(void)
 void timer_dyn_reprogram(void)
 {
 	struct dyn_tick_timer *dyn_tick = system_timer->dyn_tick;
+	unsigned long next, seq;
 
-	if (dyn_tick) {
-		write_seqlock(&xtime_lock);
-		if (dyn_tick->state & DYN_TICK_ENABLED)
+	if (dyn_tick && (dyn_tick->state & DYN_TICK_ENABLED)) {
+		next = next_timer_interrupt();
+		do {
+			seq = read_seqbegin(&xtime_lock);
 			dyn_tick->reprogram(next_timer_interrupt() - jiffies);
-		write_sequnlock(&xtime_lock);
+		} while (read_seqretry(&xtime_lock, seq));
 	}
 }
 
Index: 2.6.16-rc4-git/include/linux/hrtimer.h
===================================================================
--- 2.6.16-rc4-git.orig/include/linux/hrtimer.h
+++ 2.6.16-rc4-git/include/linux/hrtimer.h
@@ -116,6 +116,10 @@ extern int hrtimer_try_to_cancel(struct 
 extern ktime_t hrtimer_get_remaining(const struct hrtimer *timer);
 extern int hrtimer_get_res(const clockid_t which_clock, struct timespec *tp);
 
+#ifdef CONFIG_NO_IDLE_HZ
+extern ktime_t hrtimer_get_next_event(void);
+#endif
+
 static inline int hrtimer_active(const struct hrtimer *timer)
 {
 	return timer->state == HRTIMER_PENDING;
Index: 2.6.16-rc4-git/kernel/hrtimer.c
===================================================================
--- 2.6.16-rc4-git.orig/kernel/hrtimer.c
+++ 2.6.16-rc4-git/kernel/hrtimer.c
@@ -505,6 +505,41 @@ ktime_t hrtimer_get_remaining(const stru
 	return rem;
 }
 
+#ifdef CONFIG_NO_IDLE_HZ
+/**
+ * hrtimer_get_next_event - get the time until next expiry event
+ *
+ * Returns the delta to the next expiry event or KTIME_MAX if no timer
+ * is pending.
+ */
+ktime_t hrtimer_get_next_event(void)
+{
+	struct hrtimer_base *base = __get_cpu_var(hrtimer_bases);
+	ktime_t delta, mindelta = { .tv64 = KTIME_MAX };
+	unsigned long flags;
+	int i;
+
+	for (i = 0; i < MAX_HRTIMER_BASES; i++, base++) {
+		struct hrtimer *timer;
+
+		spin_lock_irqsave(&base->lock, flags);
+		if (!base->first) {
+			spin_unlock_irqrestore(&base->lock, flags);
+			continue;
+		}
+		timer = rb_entry(base->first, struct hrtimer, node);
+		delta.tv64 = timer->expires.tv64;
+		spin_unlock_irqrestore(&base->lock, flags);
+		delta = ktime_sub(delta, base->get_time());
+		if (delta.tv64 < mindelta.tv64)
+			mindelta.tv64 = delta.tv64;
+	}
+	if (mindelta.tv64 < 0)
+		mindelta.tv64 = 0;
+	return mindelta;
+}
+#endif
+
 /**
  * hrtimer_init - initialize a timer to the given clock
  *
Index: 2.6.16-rc4-git/kernel/timer.c
===================================================================
--- 2.6.16-rc4-git.orig/kernel/timer.c
+++ 2.6.16-rc4-git/kernel/timer.c
@@ -488,10 +488,21 @@ unsigned long next_timer_interrupt(void)
 	tvec_base_t *base;
 	struct list_head *list;
 	struct timer_list *nte;
-	unsigned long expires;
+	unsigned long expires, hr_expires = MAX_JIFFY_OFFSET;
+	ktime_t hr_delta;
 	tvec_t *varray[4];
 	int i, j;
 
+	hr_delta = hrtimer_get_next_event();
+	if (hr_delta.tv64 != KTIME_MAX) {
+		struct timespec tsdelta;
+		tsdelta = ktime_to_timespec(hr_delta);
+		hr_expires = timespec_to_jiffies(&tsdelta);
+		if (hr_expires < 3)
+			return hr_expires + jiffies;
+	}
+	hr_expires += jiffies;
+
 	base = &__get_cpu_var(tvec_bases);
 	spin_lock(&base->t_base.lock);
 	expires = base->timer_jiffies + (LONG_MAX >> 1);
@@ -542,6 +553,10 @@ found:
 		}
 	}
 	spin_unlock(&base->t_base.lock);
+
+	if (time_before(hr_expires, expires))
+		return hr_expires;
+
 	return expires;
 }
 #endif

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Tony Lindgren]

* Thomas Gleixner <tglx@linutronix.de> [060228 01:03]:
> On Mon, 2006-02-27 at 19:29 -0800, Tony Lindgren wrote:
> > I've changed ARM xtime_lock to read lock, but now there's a slight
> > chance that an interrupt adds a timer after next_timer_interrupt() is
> > called and before timer is reprogrammed. I believe s390 also has this
> > problem.
> 
> This needs a more generalized solution later, but I picked up your ARM
> change and simplified the hrtimer related bits.

Cool, after a quick test seems to work OK here. Any ideas how to fix the
locking problem above?

Maybe one option would be to just reprogram the hardware timer when a
new hrtimer is added. That would then allow subjiffie timers too.

Regards,

Tony

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Thomas Gleixner]

Tony,

On Tue, 2006-02-28 at 01:51 -0800, Tony Lindgren wrote:
> Cool, after a quick test seems to work OK here. Any ideas how to fix the
> locking problem above?
> 
> Maybe one option would be to just reprogram the hardware timer when a
> new hrtimer is added. That would then allow subjiffie timers too.

You might have a look into the high resolution timer patches on top of
hrtimers at http://www.tglx.de/projects/hrtimers

The clockevents abstraction layer is a quick attempt to generalize the
problem around event generation. I'm stuck in some other work right now,
but I'm going to rework this layer soon. IMO John Stultz GTOD patches
and the generalization of clock events will be a sane base for high
resolution timers and dynamic ticks.

	tglx

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Tony Lindgren]

* Thomas Gleixner <tglx@linutronix.de> [060228 02:05]:
> Tony,
> 
> On Tue, 2006-02-28 at 01:51 -0800, Tony Lindgren wrote:
> > Cool, after a quick test seems to work OK here. Any ideas how to fix the
> > locking problem above?
> > 
> > Maybe one option would be to just reprogram the hardware timer when a
> > new hrtimer is added. That would then allow subjiffie timers too.

Actually to me it looks like the read lock should do just fine on ARM,
as timer_dyn_reprogram() is called from idle loop with interrupts
disabled.
 
> You might have a look into the high resolution timer patches on top of
> hrtimers at http://www.tglx.de/projects/hrtimers

I'll take a look at those once I have some more time...
 
> The clockevents abstraction layer is a quick attempt to generalize the
> problem around event generation. I'm stuck in some other work right now,
> but I'm going to rework this layer soon. IMO John Stultz GTOD patches
> and the generalization of clock events will be a sane base for high
> resolution timers and dynamic ticks.

Yeah. And then we also need to change next_timer_interrupt() return
nanoseconds.

Regards,

Tony

Re: + fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree

[Thomas Gleixner]

On Sat, 2006-02-25 at 10:57 -0800, Tony Lindgren wrote:
> > This is racy on SMP. nanosleep hrtimers are on the stack and can go away
> > due to a signal. posix timers can be removed and destroyed on another
> > CPU.
> 
> This should be fixed. But just as a note, we can tolerate some removed
> timer values values as it would be just an extra timer interrupt.

The problem is not the removed timer. Its the reference to a destroyed
object you hold.
 
	tglx