+ fix-next_timer_interrupt-for-hrtimer.patch added to -mm tree
Subsystems (2)
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 20 lines
(quoted diff) +20
-0+#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);
Review
Quoted 10 lines
(quoted diff) +10
-0+ + 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.
Quoted 7 lines
(quoted diff) +7
-0+/** + * ktime_to_jiffies - converts ktime to jiffies + * + * @event: ktime event to be converted to jiffies + * + * Caller must take care of xtime locking. + */
Review
Quoted 10 lines
(quoted diff) +10
-0+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.
Quoted 6 lines
+/**
+ *hrtimer_next_jiffie- get next hrtimer event in jiffies
+ *
+ * Called fromnext_timer_interrupt()to get the next hrtimer event.
+ * Eventually we should changenext_timer_interrupt()to return
+ * results in nanoseconds instead of jiffies. Caller must hostxtime_lock.
S390 does not hold xtime lock when calling next_timer_interrupt !
I look for a sane solution.
tglx
Quoted 26 lines · Thomas Gleixner
Quoted 26 lines
(quoted diff) +26
-0+#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;
Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +4
-0+ } + + 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.
Quoted 3 lines
Also the expires fields of
CLOCK_MONOTONICandCLOCK_REALTIMEbased 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?
Quoted 12 lines
Quoted 12 lines
(quoted diff) +12
-0+/** + * 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);
Quoted 8 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ delta = ktime_sub(event, now); + + return jiffies + (((delta.tv64 * NSEC_CONVERSION) >> + (NSEC_JIFFIE_SC - SEC_JIFFIE_SC)) >> SEC_JIFFIE_SC); +}Only
CLOCK_REALTIMEbased timers are based on xtime. ForCLOCK_MONOTONICbased timers this calculation is off bywall_to_monotonic.
Needs to be fixed then.
Quoted 8 lines
Quoted 6 lines
+/**
+ *hrtimer_next_jiffie- get next hrtimer event in jiffies
+ *
+ * Called fromnext_timer_interrupt()to get the next hrtimer event.
+ * Eventually we should changenext_timer_interrupt()to return
+ * results in nanoseconds instead of jiffies. Caller must hostxtime_lock.S390 does not hold xtime lock when calling
next_timer_interrupt!
Good point. Needs to be fixed.
Quoted 1 line
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
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
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().
kernel/hrtimer.c +100 -0
@@ -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 *
kernel/timer.c +10 -0
@@ -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
include/linux/hrtimer.h +1 -0
@@ -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) {
arch/arm/kernel/time.c +6 -4
@@ -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)); } }
Quoted 4 lines · Tony Lindgren
I've changed ARM
xtime_lockto read lock, but now there's a slight chance that an interrupt adds a timer afternext_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
arch/arm/kernel/time.c +6 -4
@@ -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)); } }
include/linux/hrtimer.h +4 -0
@@ -116,6 +116,10 @@ extern int hrtimer_try_to_cancel(structextern 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 ;
kernel/hrtimer.c +35 -0
@@ -505,6 +505,41 @@ ktime_t hrtimer_get_remaining(const strureturn 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 *
kernel/timer.c +16 -1
@@ -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
Quoted 8 lines · Thomas Gleixner
Quoted 4 lines · Tony Lindgren
I've changed ARM
xtime_lockto read lock, but now there's a slight chance that an interrupt adds a timer afternext_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
Tony,
Quoted 5 lines · Tony Lindgren
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
Quoted 8 lines · Thomas Gleixner
Tony,
Quoted 5 lines · Tony Lindgren
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.
Quoted 2 lines
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...
Quoted 5 lines
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
Quoted 6 lines · Tony Lindgren
Quoted 3 lines
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