Skip to contentSkip to conversation

Dynamic Tick: Prevent clocksource wrapping during idle

PATCH In review Jon Hunter 4 participants 16 messages May 27, 2009 – Jun 25, 2009

Subsystems (2)
lore
Share & tools
lore

Jon Hunter

author
#0 lore raw

PATCH 1/2 Dynamic Tick: Prevent clocksource wrapping during idle

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a new function called "timekeeping_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource.

---
 include/linux/time.h      |    1 +
 kernel/time/tick-sched.c  |   36 +++++++++++++++++++++++----------
 kernel/time/timekeeping.c |   47 
+++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 73 insertions(+), 11 deletions(-)
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
 extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
 extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
 extern void update_wall_time(void);
 extern void update_xtime_cache(u64 nsec);
 
kernel/time/tick-sched.c +25 -11
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 	ktime_t last_update, expires, now;
 	struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
 	int cpu;
+	s64 time_delta, max_time_delta;
 
 	local_irq_save(flags);
 
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		seq = read_seqbegin(&xtime_lock);
 		last_update = last_jiffies_update;
 		last_jiffies = jiffies;
+		max_time_delta = timekeeping_max_deferment();
 	} while (read_seqretry(&xtime_lock, seq));
 
 	/* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
 	if ((long)delta_jiffies >= 1) {
 
 		/*
-		* calculate the expiry time for the next timer wheel
-		* timer
-		*/
-		expires = ktime_add_ns(last_update, tick_period.tv64 *
-				   delta_jiffies);
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;
+
+		if (time_delta > max_time_delta)
+			time_delta = max_time_delta;
+
+		/*
+		 * calculate the expiry time for the next timer wheel
+		 * timer
+		 */
+		expires = ktime_add_ns(last_update, time_delta);
 
 		/*
 		 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		if (cpu == tick_do_timer_cpu)
 			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-		if (delta_jiffies > 1)
+		if (time_delta > tick_period.tv64)
 			cpumask_set_cpu(cpu, nohz_cpu_mask);
 
 		/* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
 		ts->idle_sleeps++;
 
 		/*
-		 * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-		 * there is no timer pending or at least extremly far
-		 * into the future (12 days for HZ=1000). In this case
-		 * we simply stop the tick timer:
+		 * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+		 * signals that there is no timer pending or at least
+		 * extremely far into the future (12 days for HZ=1000).
+		 * In this case we simply stop the tick timer:
 		 */
-		if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+		if (unlikely(time_delta >=
+				(tick_period.tv64 * NEXT_TIMER_MAX_DELTA))) {
 			ts->idle_expires.tv64 = KTIME_MAX;
 			if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
 				hrtimer_cancel(&ts->sched_timer);
kernel/time/timekeeping.c +47 -0

51 lines not on this page · raw message

clock.
*
* Weak dummy function for arches that do not yet support it.

Signature · 1 line
1.6.1
#1 lore raw
Quoted 5 lines · Jon Hunter

/**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Must be called with xtime_lock held!

No, that would mean that xtime_lock needs to be write locked. And we definitely do not want that.

The caller needs to observe xtime_lock via read_seqbegin / read_seqretry because clock might change.

Quoted 18 lines

+ */

kernel/time/timekeeping.c +17 -0
+s64 timekeeping_max_deferment(void)
+{
+	s64 max_nsecs;
+	u64 max_cycles;
+
+	/*
+	 * Calculate the maximum number of cycles that we can pass to the
+	 * cyc2ns function without overflowing a 64-bit signed result. The
+	 * maximum number of cycles is equal to ULLONG_MAX/clock->mult which
+	 * is equivalent to the below.
+	 * max_cycles < (2^63)/clock->mult
+	 * max_cycles < 2^(log2((2^63)/clock->mult))
+	 * max_cycles < 2^(log2(2^63) - log2(clock->mult))
+	 * max_cycles < 2^(63 - log2(clock->mult))
+	 * max_cycles < 1 << (63 - log2(clock->mult))
+	 * Please note that we add 1 to the result of the log2 to account for
+	 * any rounding errors, ensure the above inequality is satisfied and

kernel/time/timekeeping.c int timekeeping_valid_for_hres(void) · line 304

Quoted 10 lines
kernel/time/timekeeping.c +10 -0
+	 * no overflow will occur.
+	 */
+	max_cycles = 1ULL << (63 - (ilog2(clock->mult) + 1));
+
+	/*
+	 * The actual maximum number of cycles we can defer the clocksource is
+	 * determined by the minimum of max_cycles and clock->mask.
+	 */
+	max_cycles = min(max_cycles, clock->mask);
+	max_nsecs = cyc2ns(clock, max_cycles);

Why do you want to recalculate the whole stuff over and over ?

That computation can be done when the clock source is initialized or any fundamental change of the clock parameters happens.

Stick that value into the clocksource struct and just read it out.

kernel/time/timekeeping.c int timekeeping_valid_for_hres(void) · line 315

Quoted 10 lines
kernel/time/timekeeping.c +10 -0
+	/*
+	 * To ensure that the clocksource does not wrap whilst we are idle,
+	 * limit the time the clocksource can be deferred by 6.25%. Please
+	 * note a margin of 6.25% is used because this can be computed with
+	 * a shift, versus say 5% which would require division.
+	 */
+	max_nsecs = max_nsecs - (max_nsecs >> 4);
+
+	if (max_nsecs < 0)
+		max_nsecs = 0;

How does "max_nsecs = max_nsecs - (max_nsecs >> 4)" ever become negative ?

Thanks,

tglx

Acked-by on v1 1/2
#13 lore raw
In reply to Jon Hunter
Quoted 8 lines · Jon Hunter

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a new function called "timekeeping_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource.

Quoted 155 lines
---
  include/linux/time.h      |    1 +
  kernel/time/tick-sched.c  |   36 +++++++++++++++++++++++----------
  kernel/time/timekeeping.c |   47 
+++++++++++++++++++++++++++++++++++++++++++++
  3 files changed, 73 insertions(+), 11 deletions(-)
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
  extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
  extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
  extern void update_wall_time(void);
  extern void update_xtime_cache(u64 nsec);
 
kernel/time/tick-sched.c +25 -11
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  	ktime_t last_update, expires, now;
  	struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
  	int cpu;
+	s64 time_delta, max_time_delta;
 
  	local_irq_save(flags);
 
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  		seq = read_seqbegin(&xtime_lock);
  		last_update = last_jiffies_update;
  		last_jiffies = jiffies;
+		max_time_delta = timekeeping_max_deferment();
  	} while (read_seqretry(&xtime_lock, seq));
 
  	/* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
  	if ((long)delta_jiffies >= 1) {
 
  		/*
-		* calculate the expiry time for the next timer wheel
-		* timer
-		*/
-		expires = ktime_add_ns(last_update, tick_period.tv64 *
-				   delta_jiffies);
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;
+
+		if (time_delta > max_time_delta)
+			time_delta = max_time_delta;
+
+		/*
+		 * calculate the expiry time for the next timer wheel
+		 * timer
+		 */
+		expires = ktime_add_ns(last_update, time_delta);
 
  		/*
  		 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  		if (cpu == tick_do_timer_cpu)
  			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-		if (delta_jiffies > 1)
+		if (time_delta > tick_period.tv64)
  			cpumask_set_cpu(cpu, nohz_cpu_mask);
 
  		/* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
  		ts->idle_sleeps++;
 
  		/*
-		 * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-		 * there is no timer pending or at least extremly far
-		 * into the future (12 days for HZ=1000). In this case
-		 * we simply stop the tick timer:
+		 * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+		 * signals that there is no timer pending or at least
+		 * extremely far into the future (12 days for HZ=1000).
+		 * In this case we simply stop the tick timer:
  		 */
-		if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+		if (unlikely(time_delta >=
+				(tick_period.tv64 * NEXT_TIMER_MAX_DELTA))) {
  			ts->idle_expires.tv64 = KTIME_MAX;
  			if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
  				hrtimer_cancel(&ts->sched_timer);
kernel/time/timekeeping.c +1 -0
index 687dff4..608fc6f 100644
@@ -271,6 +271,53 @@ int timekeeping_valid_for_hres(void)
  }
 
  /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be 

deferred
+ *
+ * IMPORTANT: Must be called with xtime_lock held!
+ */

kernel/time/timekeeping.c +43 -0
+s64 timekeeping_max_deferment(void)
+{
+	s64 max_nsecs;
+	u64 max_cycles;
+
+	/*
+	 * Calculate the maximum number of cycles that we can pass to the
+	 * cyc2ns function without overflowing a 64-bit signed result. The
+	 * maximum number of cycles is equal to ULLONG_MAX/clock->mult which
+	 * is equivalent to the below.
+	 * max_cycles < (2^63)/clock->mult
+	 * max_cycles < 2^(log2((2^63)/clock->mult))
+	 * max_cycles < 2^(log2(2^63) - log2(clock->mult))
+	 * max_cycles < 2^(63 - log2(clock->mult))
+	 * max_cycles < 1 << (63 - log2(clock->mult))
+	 * Please note that we add 1 to the result of the log2 to account for
+	 * any rounding errors, ensure the above inequality is satisfied and
+	 * no overflow will occur.
+	 */
+	max_cycles = 1ULL << (63 - (ilog2(clock->mult) + 1));
+
+	/*
+	 * The actual maximum number of cycles we can defer the clocksource is
+	 * determined by the minimum of max_cycles and clock->mask.
+	 */
+	max_cycles = min(max_cycles, clock->mask);
+	max_nsecs = cyc2ns(clock, max_cycles);
+
+	/*
+	 * To ensure that the clocksource does not wrap whilst we are idle,
+	 * limit the time the clocksource can be deferred by 6.25%. Please
+	 * note a margin of 6.25% is used because this can be computed with
+	 * a shift, versus say 5% which would require division.
+	 */
+	max_nsecs = max_nsecs - (max_nsecs >> 4);
+
+	if (max_nsecs < 0)
+		max_nsecs = 0;
+
+	return max_nsecs;
+}
+
+/**
   * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

#2 lore raw
In reply to Thomas Gleixner
Quoted 32 lines · Thomas Gleixner
Quoted 18 lines · Jon Hunter

+ */

kernel/time/timekeeping.c +17 -0
+s64 timekeeping_max_deferment(void)
+{
+	s64 max_nsecs;
+	u64 max_cycles;
+
+	/*
+	 * Calculate the maximum number of cycles that we can pass to the
+	 * cyc2ns function without overflowing a 64-bit signed result. The
+	 * maximum number of cycles is equal to ULLONG_MAX/clock->mult which
+	 * is equivalent to the below.
+	 * max_cycles < (2^63)/clock->mult
+	 * max_cycles < 2^(log2((2^63)/clock->mult))
+	 * max_cycles < 2^(log2(2^63) - log2(clock->mult))
+	 * max_cycles < 2^(63 - log2(clock->mult))
+	 * max_cycles < 1 << (63 - log2(clock->mult))
+	 * Please note that we add 1 to the result of the log2 to account for
+	 * any rounding errors, ensure the above inequality is satisfied and

kernel/time/timekeeping.c int timekeeping_valid_for_hres(void) · line 304

Quoted 10 lines
kernel/time/timekeeping.c +10 -0
+	 * no overflow will occur.
+	 */
+	max_cycles = 1ULL << (63 - (ilog2(clock->mult) + 1));
+
+	/*
+	 * The actual maximum number of cycles we can defer the clocksource is
+	 * determined by the minimum of max_cycles and clock->mask.
+	 */
+	max_cycles = min(max_cycles, clock->mask);
+	max_nsecs = cyc2ns(clock, max_cycles);

Why do you want to recalculate the whole stuff over and over ?

Quoted 4 lines

That computation can be done when the clock source is initialized or any fundamental change of the clock parameters happens.

Stick that value into the clocksource struct and just read it out.

Sigh.

I was hoping to avoid hanging another bit of junk off of the clocksource struct.

But I guess we could compute that value on registration and keep it around. Changes to mult could effect things, but should be well within the 6% safety net we give ourselves.

Quoted 5 lines
Quoted 5 lines
kernel/time/timekeeping.c +5 -0
+	/*
+	 * To ensure that the clocksource does not wrap whilst we are idle,
+	 * limit the time the clocksource can be deferred by 6.25%. Please
+	 * note a margin of 6.25% is used because this can be computed with
+	 * a shift, versus say 5% which would require division.
Quoted 8 lines

kernel/time/timekeeping.c int timekeeping_valid_for_hres(void) · line 315

Quoted 5 lines
kernel/time/timekeeping.c +5 -0
+	 */
+	max_nsecs = max_nsecs - (max_nsecs >> 4);
+
+	if (max_nsecs < 0)
+		max_nsecs = 0;

How does "max_nsecs = max_nsecs - (max_nsecs >> 4)" ever become negative ?

Fair point. Now we've limited the overflow case, we shouldn't trip negative values.

thanks
-john

#3 lore raw
Quoted 11 lines · john stultz
Quoted 6 lines

Why do you want to recalculate the whole stuff over and over ?

That computation can be done when the clock source is initialized or any fundamental change of the clock parameters happens.

Stick that value into the clocksource struct and just read it out.

Sigh.

I was hoping to avoid hanging another bit of junk off of the clocksource struct.

Sure, but buying that 8 bytes with Einsteinian insanity is nuts.

Quoted 3 lines

But I guess we could compute that value on registration and keep it around. Changes to mult could effect things, but should be well within the 6% safety net we give ourselves.

That was my thought as well, but even if we have to go to 12% it's way better than doing repeated nonsense on the way to idle.

Thanks,

tglx

#14 lore raw
In reply to Jon Hunter
Quoted 10 lines · Jon Hunter

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a new function called "timekeeping_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource.

From the patch description I understand that this will avoid wrapping

around for only the *current* clocksource. What happens if, say, TSC is the clocksource and ACPI_PM is being used as the watchdog_clocksource, in that case the timekeeping_max_deferement will give TSC' max allowed sleep value (which is greater than ACPI_PMs). i.e. We could still sleep beyond ACPI_PM's wrap around threshold which may result in us marking TSC as unsuable as a clocksource. That could still result in incorrect timekeeping right ?

Thanks,
Alok

Quoted 168 lines

---
 include/linux/time.h      |    1 + kernel/time/tick-sched.c  |   36 +++++++++++++++++++++++---------- kernel/time/timekeeping.c |   47
+++++++++++++++++++++++++++++++++++++++++++++

 3 files changed, 73 insertions(+), 11 deletions(-)
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
  extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
  extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
  extern void update_wall_time(void);
  extern void update_xtime_cache(u64 nsec);
 
kernel/time/tick-sched.c +0 -0
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
        ktime_t last_update, expires, now;

       struct clock_event_device *dev =
__get_cpu_var(tick_cpu_device).evtdev;
       int cpu;
+       s64 time_delta, max_time_delta;

       local_irq_save(flags);

kernel/time/tick-sched.c +24 -11
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
                seq = read_seqbegin(&xtime_lock);
                last_update = last_jiffies_update;
                last_jiffies = jiffies;
+               max_time_delta = timekeeping_max_deferment();
        } while (read_seqretry(&xtime_lock, seq));
 
        /* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
        if ((long)delta_jiffies >= 1) {
 
                /*
-               * calculate the expiry time for the next timer wheel
-               * timer
-               */
-               expires = ktime_add_ns(last_update, tick_period.tv64 *
-                                  delta_jiffies);
+                * Calculate the time delta for the next timer event.
+                * If the time delta exceeds the maximum time delta
+                * permitted by the current clocksource then adjust
+                * the time delta accordingly to ensure the
+                * clocksource does not wrap.
+                */
+               time_delta = tick_period.tv64 * delta_jiffies;
+
+               if (time_delta > max_time_delta)
+                       time_delta = max_time_delta;
+
+               /*
+                * calculate the expiry time for the next timer wheel
+                * timer
+                */
+               expires = ktime_add_ns(last_update, time_delta);
 
                /*
                 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
                if (cpu == tick_do_timer_cpu)
                        tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-               if (delta_jiffies > 1)
+               if (time_delta > tick_period.tv64)
                        cpumask_set_cpu(cpu, nohz_cpu_mask);
 
                /* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
                ts->idle_sleeps++;
 
                /*
-                * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-                * there is no timer pending or at least extremly far
-                * into the future (12 days for HZ=1000). In this case
-                * we simply stop the tick timer:
+                * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+                * signals that there is no timer pending or at least
+                * extremely far into the future (12 days for HZ=1000).
+                * In this case we simply stop the tick timer:
                 */
-               if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+               if (unlikely(time_delta >=
+                               (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)))
 {
                        ts->idle_expires.tv64 = KTIME_MAX;
                        if (ts->nohz_mode == NOHZ_MODE_HIGHRES)

                               hrtimer_cancel(&ts->sched_timer);

kernel/time/timekeeping.c +1 -0
index 687dff4..608fc6f 100644
@@ -271,6 +271,53 @@ int timekeeping_valid_for_hres(void)
  }
 
  /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be

deferred
+ *
+ * IMPORTANT: Must be called with xtime_lock held!
+ */

kernel/time/timekeeping.c +16 -0
+s64 timekeeping_max_deferment(void)
+{
+       s64 max_nsecs;
+       u64 max_cycles;
+
+       /*
+        * Calculate the maximum number of cycles that we can pass to the
+        * cyc2ns function without overflowing a 64-bit signed result. The
+        * maximum number of cycles is equal to ULLONG_MAX/clock->mult which
+        * is equivalent to the below.
+        * max_cycles < (2^63)/clock->mult
+        * max_cycles < 2^(log2((2^63)/clock->mult))
+        * max_cycles < 2^(log2(2^63) - log2(clock->mult))
+        * max_cycles < 2^(63 - log2(clock->mult))
+        * max_cycles < 1 << (63 - log2(clock->mult))
+        * Please note that we add 1 to the result of the log2 to account

for
+        * any rounding errors, ensure the above inequality is satisfied and
+        * no overflow will occur.
+        */
+       max_cycles = 1ULL << (63 - (ilog2(clock->mult) + 1));
+
+       /*
+        * The actual maximum number of cycles we can defer the clocksource is
+        * determined by the minimum of max_cycles and clock->mask.
+        */
+       max_cycles = min(max_cycles, clock->mask);
+       max_nsecs = cyc2ns(clock, max_cycles);

kernel/time/timekeeping.c +16 -0
+
+       /*
+        * To ensure that the clocksource does not wrap whilst we are idle,
+        * limit the time the clocksource can be deferred by 6.25%. Please
+        * note a margin of 6.25% is used because this can be computed with
+        * a shift, versus say 5% which would require division.
+        */
+       max_nsecs = max_nsecs - (max_nsecs >> 4);
+
+       if (max_nsecs < 0)
+               max_nsecs = 0;
+
+       return max_nsecs;
+}
+
+/**

 * read_persistent_clock -  Return time in seconds from the persistent clock.
 *
 * Weak dummy function for arches that do not yet support it. --
1.6.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

#15 lore raw
Quoted 10 lines · Alok Kataria
Quoted 8 lines · Jon Hunter

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a new function called "timekeeping_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource.

Quoted 8 lines
Quoted 1 line

From the patch description I understand that this will avoid wrapping

around for only the *current* clocksource. What happens if, say, TSC is the clocksource and ACPI_PM is being used as the watchdog_clocksource, in that case the timekeeping_max_deferement will give TSC' max allowed sleep value (which is greater than ACPI_PMs). i.e. We could still sleep beyond ACPI_PM's wrap around threshold which may result in us marking TSC as unsuable as a clocksource. That could still result in incorrect timekeeping right ?

No, because the watchdog timer takes care of that. It wakes up at time.

Thanks,

tglx

author
#4 lore raw
In reply to Thomas Gleixner
Quoted 6 lines · Thomas Gleixner
Quoted 5 lines · john stultz
Quoted 5 lines

Why do you want to recalculate the whole stuff over and over ?

That computation can be done when the clock source is initialized or any fundamental change of the clock parameters happens.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

Stick that value into the clocksource struct and just read it out.

Sigh.

I was hoping to avoid hanging another bit of junk off of the clocksource struct.

Sure, but buying that 8 bytes with Einsteinian insanity is nuts.

Ok, I have re-worked the patch to avoid computing the value over and over and just use the original mult value to calculate the max deferment. This patch calculates the value on registering the clocksource and stores the value in the clocksource struct.

Quoted 6 lines
Quoted 3 lines

But I guess we could compute that value on registration and keep it around. Changes to mult could effect things, but should be well within the 6% safety net we give ourselves.

That was my thought as well, but even if we have to go to 12% it's way better than doing repeated nonsense on the way to idle.

For now I have modified the patch to go to 12.5% margin to be on the safe side.

Let me know your thoughts on the below.

Cheers
Jon

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a function called "clocksource_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource and function called "timekeeping_max_deferment()" that returns maximum time the kernel can sleep for the current clocksource.

---
 include/linux/clocksource.h |   46 
+++++++++++++++++++++++++++++++++++++++++++
 include/linux/time.h        |    1 +
 kernel/time/clocksource.c   |    3 ++
 kernel/time/tick-sched.c    |   36 +++++++++++++++++++++++----------
 kernel/time/timekeeping.c   |   11 ++++++++++
 5 files changed, 86 insertions(+), 11 deletions(-)
include/linux/clocksource.h +46 -0
index 5a40d14..b0d676e 100644
@@ -151,6 +151,7 @@ extern u64 timecounter_cyc2time(struct timecounter *tc,
  * @mult:		cycle to nanosecond multiplier (adjusted by NTP)
  * @mult_orig:		cycle to nanosecond multiplier (unadjusted by NTP)
  * @shift:		cycle to nanosecond divisor (power of two)
+ * @max_idle_ns:	max idle time permitted by the clocksource (nsecs)
  * @flags:		flags describing special properties
  * @vread:		vsyscall based read
  * @resume:		resume function for the clocksource, if necessary
@@ -171,6 +172,7 @@ struct clocksource {
 	u32 mult;
 	u32 mult_orig;
 	u32 shift;
+	s64 max_idle_ns;
 	unsigned long flags;
 	cycle_t (*vread)(void);
 	void (*resume)(void);
@@ -322,6 +324,50 @@ static inline s64 cyc2ns(struct clocksource *cs, cycle_t cycles)
 }
 
 /**
+ * clocksource_max_deferment - Returns max time the clocksource can be deferred
+ * @cs:		Pointer to clocksource
+ *
+ */
+static inline s64 clocksource_max_deferment(struct clocksource *cs)
+{
+	s64 max_nsecs;
+	u64 max_cycles;
+
+	/*
+	 * Calculate the maximum number of cycles that we can pass to the
+	 * cyc2ns function without overflowing a 64-bit signed result. The
+	 * maximum number of cycles is equal to ULLONG_MAX/cs->mult which
+	 * is equivalent to the below.
+	 * max_cycles < (2^63)/cs->mult
+	 * max_cycles < 2^(log2((2^63)/cs->mult))
+	 * max_cycles < 2^(log2(2^63) - log2(cs->mult))
+	 * max_cycles < 2^(63 - log2(cs->mult))
+	 * max_cycles < 1 << (63 - log2(cs->mult))
+	 * Please note that we add 1 to the result of the log2 to account for
+	 * any rounding errors, ensure the above inequality is satisfied and
+	 * no overflow will occur.
+	 */
+	max_cycles = 1ULL << (63 - (ilog2(cs->mult) + 1));
+
+	/*
+	 * The actual maximum number of cycles we can defer the clocksource is
+	 * determined by the minimum of max_cycles and cs->mask.
+	 */
+	max_cycles = min(max_cycles, cs->mask);
+	max_nsecs = cyc2ns(cs, max_cycles);
+
+	/*
+	 * To ensure that the clocksource does not wrap whilst we are idle,
+	 * limit the time the clocksource can be deferred by 12.5%. Please
+	 * note a margin of 12.5% is used because this can be computed with
+	 * a shift, versus say 10% which would require division.
+	 */
+	max_nsecs = max_nsecs - (max_nsecs >> 5);
+
+	return max_nsecs;
+}
+
+/**
  * clocksource_calculate_interval - Calculates a clocksource interval 

struct
*
* @c: Pointer to clocksource.

include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
 extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
 extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
 extern void update_wall_time(void);
 extern void update_xtime_cache(u64 nsec);
 
kernel/time/clocksource.c +3 -0
index ecfd7b5..0d98dc2 100644
@@ -405,6 +405,9 @@ int clocksource_register(struct clocksource *c)
 	/* save mult_orig on registration */
 	c->mult_orig = c->mult;
 
+	/* calculate max idle time permitted for this clocksource */
+	c->max_idle_ns = clocksource_max_deferment(c);
+
 	spin_lock_irqsave(&clocksource_lock, flags);
 	ret = clocksource_enqueue(c);
 	if (!ret)
kernel/time/tick-sched.c +25 -11
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 	ktime_t last_update, expires, now;
 	struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
 	int cpu;
+	s64 time_delta, max_time_delta;
 
 	local_irq_save(flags);
 
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		seq = read_seqbegin(&xtime_lock);
 		last_update = last_jiffies_update;
 		last_jiffies = jiffies;
+		max_time_delta = timekeeping_max_deferment();
 	} while (read_seqretry(&xtime_lock, seq));
 
 	/* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
 	if ((long)delta_jiffies >= 1) {
 
 		/*
-		* calculate the expiry time for the next timer wheel
-		* timer
-		*/
-		expires = ktime_add_ns(last_update, tick_period.tv64 *
-				   delta_jiffies);
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;
+
+		if (time_delta > max_time_delta)
+			time_delta = max_time_delta;
+
+		/*
+		 * calculate the expiry time for the next timer wheel
+		 * timer
+		 */
+		expires = ktime_add_ns(last_update, time_delta);
 
 		/*
 		 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		if (cpu == tick_do_timer_cpu)
 			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-		if (delta_jiffies > 1)
+		if (time_delta > tick_period.tv64)
 			cpumask_set_cpu(cpu, nohz_cpu_mask);
 
 		/* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
 		ts->idle_sleeps++;
 
 		/*
-		 * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-		 * there is no timer pending or at least extremly far
-		 * into the future (12 days for HZ=1000). In this case
-		 * we simply stop the tick timer:
+		 * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+		 * signals that there is no timer pending or at least
+		 * extremely far into the future (12 days for HZ=1000).
+		 * In this case we simply stop the tick timer:
 		 */
-		if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+		if (unlikely(time_delta >=
+				(tick_period.tv64 * NEXT_TIMER_MAX_DELTA))) {
 			ts->idle_expires.tv64 = KTIME_MAX;
 			if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
 				hrtimer_cancel(&ts->sched_timer);
kernel/time/timekeeping.c +11 -0
index 687dff4..659cae3 100644
@@ -271,6 +271,17 @@ int timekeeping_valid_for_hres(void)
 }
 
 /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+
+/**
  * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

Signature · 1 line
1.6.1
#5 lore raw
Quoted 7 lines · Jon Hunter

/**
+ * clocksource_max_deferment - Returns max time the clocksource can be deferred
+ * @cs: Pointer to clocksource
+ *
+ */
+static inline s64 clocksource_max_deferment(struct clocksource *cs)

Please make this a real function. There is no reason to stick this into a header file. The only user is clocksource.c anyway, so please put it there as a static function and let the compiler decide what to do with it.

Otherwise, I'm happy with it.

Thanks,

tglx

author
#6 lore raw
Quoted 4 lines · Thomas Gleixner

Please make this a real function. There is no reason to stick this into a header file. The only user is clocksource.c anyway, so please put it there as a static function and let the compiler decide what to do with it.

No problem. Please see below. Let me know if this is ok and there is anything else.

Cheers
Jon

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a function called "clocksource_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource and function called "timekeeping_max_deferment()" that returns maximum time the kernel can sleep for the current clocksource.

---
 include/linux/clocksource.h |    2 +
 include/linux/time.h        |    1 +
 kernel/time/clocksource.c   |   47 
+++++++++++++++++++++++++++++++++++++++++++
 kernel/time/tick-sched.c    |   36 ++++++++++++++++++++++----------
 kernel/time/timekeeping.c   |   11 ++++++++++
 5 files changed, 86 insertions(+), 11 deletions(-)
include/linux/clocksource.h +2 -0
index 5a40d14..465af22 100644
@@ -151,6 +151,7 @@ extern u64 timecounter_cyc2time(struct timecounter *tc,
  * @mult:		cycle to nanosecond multiplier (adjusted by NTP)
  * @mult_orig:		cycle to nanosecond multiplier (unadjusted by NTP)
  * @shift:		cycle to nanosecond divisor (power of two)
+ * @max_idle_ns:	max idle time permitted by the clocksource (nsecs)
  * @flags:		flags describing special properties
  * @vread:		vsyscall based read
  * @resume:		resume function for the clocksource, if necessary
@@ -171,6 +172,7 @@ struct clocksource {
 	u32 mult;
 	u32 mult_orig;
 	u32 shift;
+	s64 max_idle_ns;
 	unsigned long flags;
 	cycle_t (*vread)(void);
 	void (*resume)(void);
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
 extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
 extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
 extern void update_wall_time(void);
 extern void update_xtime_cache(u64 nsec);
 
kernel/time/clocksource.c +47 -0

59 lines not on this page · raw message

kernel/time/tick-sched.c +25 -11
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 	ktime_t last_update, expires, now;
 	struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
 	int cpu;
+	s64 time_delta, max_time_delta;
 
 	local_irq_save(flags);
 
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		seq = read_seqbegin(&xtime_lock);
 		last_update = last_jiffies_update;
 		last_jiffies = jiffies;
+		max_time_delta = timekeeping_max_deferment();
 	} while (read_seqretry(&xtime_lock, seq));
 
 	/* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
 	if ((long)delta_jiffies >= 1) {
 
 		/*
-		* calculate the expiry time for the next timer wheel
-		* timer
-		*/
-		expires = ktime_add_ns(last_update, tick_period.tv64 *
-				   delta_jiffies);
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;
+
+		if (time_delta > max_time_delta)
+			time_delta = max_time_delta;
+
+		/*
+		 * calculate the expiry time for the next timer wheel
+		 * timer
+		 */
+		expires = ktime_add_ns(last_update, time_delta);
 
 		/*
 		 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
 		if (cpu == tick_do_timer_cpu)
 			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-		if (delta_jiffies > 1)
+		if (time_delta > tick_period.tv64)
 			cpumask_set_cpu(cpu, nohz_cpu_mask);
 
 		/* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
 		ts->idle_sleeps++;
 
 		/*
-		 * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-		 * there is no timer pending or at least extremly far
-		 * into the future (12 days for HZ=1000). In this case
-		 * we simply stop the tick timer:
+		 * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+		 * signals that there is no timer pending or at least
+		 * extremely far into the future (12 days for HZ=1000).
+		 * In this case we simply stop the tick timer:
 		 */
-		if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+		if (unlikely(time_delta >=
+				(tick_period.tv64 * NEXT_TIMER_MAX_DELTA))) {
 			ts->idle_expires.tv64 = KTIME_MAX;
 			if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
 				hrtimer_cancel(&ts->sched_timer);
kernel/time/timekeeping.c +11 -0
index 687dff4..659cae3 100644
@@ -271,6 +271,17 @@ int timekeeping_valid_for_hres(void)
 }
 
 /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+
+/**
  * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

Signature · 1 line
1.6.1
Acked-by
#7 lore raw
Quoted 22 lines · Jon Hunter
Quoted 4 lines · Thomas Gleixner

Please make this a real function. There is no reason to stick this into a header file. The only user is clocksource.c anyway, so please put it there as a static function and let the compiler decide what to do with it.

No problem. Please see below. Let me know if this is ok and there is anything else.

Cheers
Jon

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a function called "clocksource_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource and function called "timekeeping_max_deferment()" that returns maximum time the kernel can sleep for the current clocksource.

Quoted 1 line

Thanks for putting up with my apparent misdirections and going around and around on this. :)

Quoted 208 lines
---
  include/linux/clocksource.h |    2 +
  include/linux/time.h        |    1 +
  kernel/time/clocksource.c   |   47 
+++++++++++++++++++++++++++++++++++++++++++
  kernel/time/tick-sched.c    |   36 ++++++++++++++++++++++----------
  kernel/time/timekeeping.c   |   11 ++++++++++
  5 files changed, 86 insertions(+), 11 deletions(-)
include/linux/clocksource.h +2 -0
index 5a40d14..465af22 100644
@@ -151,6 +151,7 @@ extern u64 timecounter_cyc2time(struct timecounter *tc,
   * @mult:		cycle to nanosecond multiplier (adjusted by NTP)
   * @mult_orig:		cycle to nanosecond multiplier (unadjusted by NTP)
   * @shift:		cycle to nanosecond divisor (power of two)
+ * @max_idle_ns:	max idle time permitted by the clocksource (nsecs)
   * @flags:		flags describing special properties
   * @vread:		vsyscall based read
   * @resume:		resume function for the clocksource, if necessary
@@ -171,6 +172,7 @@ struct clocksource {
  	u32 mult;
  	u32 mult_orig;
  	u32 shift;
+	s64 max_idle_ns;
  	unsigned long flags;
  	cycle_t (*vread)(void);
  	void (*resume)(void);
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
  extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
  extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
  extern void update_wall_time(void);
  extern void update_xtime_cache(u64 nsec);
 
kernel/time/clocksource.c +1 -0
index ecfd7b5..18d2b9f 100644
@@ -321,6 +321,50 @@ void clocksource_touch_watchdog(void)
  }
 
  /**
+ * clocksource_max_deferment - Returns max time the clocksource can be 

deferred
+ * @cs: Pointer to clocksource
+ *
+ */

kernel/time/clocksource.c +43 -0
+static s64 clocksource_max_deferment(struct clocksource *cs)
+{
+	s64 max_nsecs;
+	u64 max_cycles;
+
+	/*
+	 * Calculate the maximum number of cycles that we can pass to the
+	 * cyc2ns function without overflowing a 64-bit signed result. The
+	 * maximum number of cycles is equal to ULLONG_MAX/cs->mult which
+	 * is equivalent to the below.
+	 * max_cycles < (2^63)/cs->mult
+	 * max_cycles < 2^(log2((2^63)/cs->mult))
+	 * max_cycles < 2^(log2(2^63) - log2(cs->mult))
+	 * max_cycles < 2^(63 - log2(cs->mult))
+	 * max_cycles < 1 << (63 - log2(cs->mult))
+	 * Please note that we add 1 to the result of the log2 to account for
+	 * any rounding errors, ensure the above inequality is satisfied and
+	 * no overflow will occur.
+	 */
+	max_cycles = 1ULL << (63 - (ilog2(cs->mult) + 1));
+
+	/*
+	 * The actual maximum number of cycles we can defer the clocksource is
+	 * determined by the minimum of max_cycles and cs->mask.
+	 */
+	max_cycles = min(max_cycles, cs->mask);
+	max_nsecs = cyc2ns(cs, max_cycles);
+
+	/*
+	 * To ensure that the clocksource does not wrap whilst we are idle,
+	 * limit the time the clocksource can be deferred by 12.5%. Please
+	 * note a margin of 12.5% is used because this can be computed with
+	 * a shift, versus say 10% which would require division.
+	 */
+	max_nsecs = max_nsecs - (max_nsecs >> 5);
+
+	return max_nsecs;
+}
+
+/**
   * clocksource_get_next - Returns the selected clocksource
   *
   */
@@ -405,6 +449,9 @@ int clocksource_register(struct clocksource *c)
  	/* save mult_orig on registration */
  	c->mult_orig = c->mult;
 
+	/* calculate max idle time permitted for this clocksource */
+	c->max_idle_ns = clocksource_max_deferment(c);
+
  	spin_lock_irqsave(&clocksource_lock, flags);
  	ret = clocksource_enqueue(c);
  	if (!ret)
kernel/time/tick-sched.c +25 -11
index d3f1ef4..f0155ae 100644
@@ -217,6 +217,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  	ktime_t last_update, expires, now;
  	struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev;
  	int cpu;
+	s64 time_delta, max_time_delta;
 
  	local_irq_save(flags);
 
@@ -264,6 +265,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  		seq = read_seqbegin(&xtime_lock);
  		last_update = last_jiffies_update;
  		last_jiffies = jiffies;
+		max_time_delta = timekeeping_max_deferment();
  	} while (read_seqretry(&xtime_lock, seq));
 
  	/* Get the next timer wheel timer */
@@ -283,11 +285,22 @@ void tick_nohz_stop_sched_tick(int inidle)
  	if ((long)delta_jiffies >= 1) {
 
  		/*
-		* calculate the expiry time for the next timer wheel
-		* timer
-		*/
-		expires = ktime_add_ns(last_update, tick_period.tv64 *
-				   delta_jiffies);
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;
+
+		if (time_delta > max_time_delta)
+			time_delta = max_time_delta;
+
+		/*
+		 * calculate the expiry time for the next timer wheel
+		 * timer
+		 */
+		expires = ktime_add_ns(last_update, time_delta);
 
  		/*
  		 * If this cpu is the one which updates jiffies, then
@@ -300,7 +313,7 @@ void tick_nohz_stop_sched_tick(int inidle)
  		if (cpu == tick_do_timer_cpu)
  			tick_do_timer_cpu = TICK_DO_TIMER_NONE;
 
-		if (delta_jiffies > 1)
+		if (time_delta > tick_period.tv64)
  			cpumask_set_cpu(cpu, nohz_cpu_mask);
 
  		/* Skip reprogram of event if its not changed */
@@ -332,12 +345,13 @@ void tick_nohz_stop_sched_tick(int inidle)
  		ts->idle_sleeps++;
 
  		/*
-		 * delta_jiffies >= NEXT_TIMER_MAX_DELTA signals that
-		 * there is no timer pending or at least extremly far
-		 * into the future (12 days for HZ=1000). In this case
-		 * we simply stop the tick timer:
+		 * time_delta >= (tick_period.tv64 * NEXT_TIMER_MAX_DELTA)
+		 * signals that there is no timer pending or at least
+		 * extremely far into the future (12 days for HZ=1000).
+		 * In this case we simply stop the tick timer:
  		 */
-		if (unlikely(delta_jiffies >= NEXT_TIMER_MAX_DELTA)) {
+		if (unlikely(time_delta >=
+				(tick_period.tv64 * NEXT_TIMER_MAX_DELTA))) {
  			ts->idle_expires.tv64 = KTIME_MAX;
  			if (ts->nohz_mode == NOHZ_MODE_HIGHRES)
  				hrtimer_cancel(&ts->sched_timer);
kernel/time/timekeeping.c +1 -0
index 687dff4..659cae3 100644
@@ -271,6 +271,17 @@ int timekeeping_valid_for_hres(void)
  }
 
  /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be 

deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */

kernel/time/timekeeping.c +6 -0
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+
+/**
   * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

#8 lore raw
In reply to Jon Hunter
Quoted 8 lines · Jon Hunter
Quoted 4 lines · Thomas Gleixner

Please make this a real function. There is no reason to stick this into a header file. The only user is clocksource.c anyway, so please put it there as a static function and let the compiler decide what to do with it.

No problem. Please see below. Let me know if this is ok and there is anything else.

Looks good now.

Quoted 7 lines

/**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */

Just nitpicking here. For the intended use case this is irrelevant.

On UP this is called from an irq disabled section, so nothing is going to change the clock source.

On SMP it does not matter if CPU A goes to sleep with the old clock source and CPU B changes the clock source while A is idle. When B goes idle it will take the change into account.

But that leads me to an interesting observation:

On SMP we really should only care for the CPU which has the do_timer duty assigned. All other CPUs can sleep as long as they want. When that CPU goes idle and drops the do_timer duty it needs to look at max_deferement, but the others can sleep as long as they want.

So the rule would be:

  if (cpu == tick_do_timer_cpu || tick_do_timer_cpu == TICK_DO_TIMER_NONE)
     check_max_deferment();
  else
     sleep_as_long_as_you_want;

Could you add that perhaps ?

kernel/time/timekeeping.c int timekeeping_valid_for_hres(void) · line 283

Quoted 5 lines
kernel/time/timekeeping.c +5 -0
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+

Thanks for your patience,

tglx

author
#9 lore raw
Quoted 9 lines · Thomas Gleixner
Quoted 7 lines · Jon Hunter

/**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */

Quoted 8 lines

Just nitpicking here. For the intended use case this is irrelevant.

On UP this is called from an irq disabled section, so nothing is going to change the clock source.

On SMP it does not matter if CPU A goes to sleep with the old clock source and CPU B changes the clock source while A is idle. When B goes idle it will take the change into account.

Ok, understood. Let me know if you would like me to remove the comment above. I wanted to make sure that if someone was to use this function else where (can't think of why right now) that they would not over look this.

Quoted 7 lines

But that leads me to an interesting observation:

On SMP we really should only care for the CPU which has the do_timer duty assigned. All other CPUs can sleep as long as they want. When that CPU goes idle and drops the do_timer duty it needs to look at max_deferement, but the others can sleep as long as they want.

Quoted 8 lines

So the rule would be:

  if (cpu == tick_do_timer_cpu || tick_do_timer_cpu == TICK_DO_TIMER_NONE)
     check_max_deferment();
  else
     sleep_as_long_as_you_want;

Could you add that perhaps ?

Absolutely. Please see below and let me know if this is ok.

Quoted 1 line

Thanks for your patience,

No problem. Thanks for the feedback.

Cheers
Jon

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a function called "clocksource_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource and function called "timekeeping_max_deferment()" that returns maximum time the kernel can sleep for the current clocksource.

---
 include/linux/clocksource.h |    2 +
 include/linux/time.h        |    1 +
 kernel/time/clocksource.c   |   47 
+++++++++++++++++++++++++++++++++++++++++++
 kernel/time/tick-sched.c    |   47 
++++++++++++++++++++++++++++++++----------
 kernel/time/timekeeping.c   |   11 ++++++++++
 5 files changed, 97 insertions(+), 11 deletions(-)
include/linux/clocksource.h +2 -0
index 5a40d14..465af22 100644
@@ -151,6 +151,7 @@ extern u64 timecounter_cyc2time(struct timecounter *tc,
  * @mult:		cycle to nanosecond multiplier (adjusted by NTP)
  * @mult_orig:		cycle to nanosecond multiplier (unadjusted by NTP)
  * @shift:		cycle to nanosecond divisor (power of two)
+ * @max_idle_ns:	max idle time permitted by the clocksource (nsecs)
  * @flags:		flags describing special properties
  * @vread:		vsyscall based read
  * @resume:		resume function for the clocksource, if necessary
@@ -171,6 +172,7 @@ struct clocksource {
 	u32 mult;
 	u32 mult_orig;
 	u32 shift;
+	s64 max_idle_ns;
 	unsigned long flags;
 	cycle_t (*vread)(void);
 	void (*resume)(void);
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
 extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
 extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
 extern void update_wall_time(void);
 extern void update_xtime_cache(u64 nsec);
 
kernel/time/clocksource.c +47 -0

59 lines not on this page · raw message

kernel/time/tick-sched.c +36 -11

78 lines not on this page · raw message

kernel/time/timekeeping.c +11 -0
index 687dff4..659cae3 100644
@@ -271,6 +271,17 @@ int timekeeping_valid_for_hres(void)
 }
 
 /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+
+/**
  * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

Signature · 1 line
1.6.1
author
#10 lore raw
In reply to Jon Hunter

kernel/time/tick-sched.c void tick_nohz_stop_sched_tick(int inidle) · line 294

Quoted 7 lines · Jon Hunter
kernel/time/tick-sched.c +7 -0
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;

Thinking about this more, although it is very unlikely, for 64-bit machines there is a chance that the above multiply could overflow if delta_jiffies is very large.

tick_period.tv64 should always be less than NSEC_PER_SEC and so you would need delta_jiffies to be greater than 2^32 to cause overflow. On a 32-bit machine an unsigned long will not be greater than 2^32 as it is only 32-bits but this would be possible on a 64-bit machines.

So to be safe we should make sure that delta_jiffies is not greater than
NEXT_TIMER_MAX_DELTA (2^30 - 1) before doing the multiply. If you
think that this is a valid concern, then I can re-work and re-post. Sorry for not catching this before.

Jon

author
#11 lore raw
Quoted 11 lines · Jon Hunter

Review

Quoted 7 lines · Jon Hunter
(quoted diff) +7 -0
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;

Thinking about this more, although it is very unlikely, for 64-bit machines there is a chance that the above multiply could overflow if delta_jiffies is very large.

Quoted 5 lines

tick_period.tv64 should always be less than NSEC_PER_SEC and so you would need delta_jiffies to be greater than 2^32 to cause overflow. On a 32-bit machine an unsigned long will not be greater than 2^32 as it is only 32-bits but this would be possible on a 64-bit machines.

So to be safe we should make sure that delta_jiffies is not greater than
NEXT_TIMER_MAX_DELTA (2^30 - 1) before doing the multiply. If you
think that this is a valid concern, then I can re-work and re-post. Sorry for not catching this before.

With regard to the above, to ensure that there are no overflows with the above calculation, I re-worked this patch a little. The below should be equivalent to the current code, just re-organised a little. Let me know if this would be acceptable or not.

Cheers
Jon

The dynamic tick allows the kernel to sleep for periods longer than a single tick. This patch prevents that the kernel from sleeping for a period longer than the maximum time that the current clocksource can count. This ensures that the kernel will not lose track of time. This patch adds a function called "clocksource_max_deferment()" that calculates the maximum time the kernel can sleep for a given clocksource and function called "timekeeping_max_deferment()" that returns maximum time the kernel can sleep for the current clocksource.

---
 include/linux/clocksource.h |    2 +
 include/linux/time.h        |    1 +
 kernel/time/clocksource.c   |   47 +++++++++++++++++++++++++++++++++++
 kernel/time/tick-sched.c    |   57 
++++++++++++++++++++++++++++++++----------
 kernel/time/timekeeping.c   |   11 ++++++++
 5 files changed, 104 insertions(+), 14 deletions(-)
include/linux/clocksource.h +2 -0
index 5a40d14..465af22 100644
@@ -151,6 +151,7 @@ extern u64 timecounter_cyc2time(struct timecounter *tc,
  * @mult:		cycle to nanosecond multiplier (adjusted by NTP)
  * @mult_orig:		cycle to nanosecond multiplier (unadjusted by NTP)
  * @shift:		cycle to nanosecond divisor (power of two)
+ * @max_idle_ns:	max idle time permitted by the clocksource (nsecs)
  * @flags:		flags describing special properties
  * @vread:		vsyscall based read
  * @resume:		resume function for the clocksource, if necessary
@@ -171,6 +172,7 @@ struct clocksource {
 	u32 mult;
 	u32 mult_orig;
 	u32 shift;
+	s64 max_idle_ns;
 	unsigned long flags;
 	cycle_t (*vread)(void);
 	void (*resume)(void);
include/linux/time.h +1 -0
index 242f624..090be07 100644
@@ -130,6 +130,7 @@ extern void monotonic_to_bootbased(struct timespec *ts);
 
 extern struct timespec timespec_trunc(struct timespec t, unsigned gran);
 extern int timekeeping_valid_for_hres(void);
+extern s64 timekeeping_max_deferment(void);
 extern void update_wall_time(void);
 extern void update_xtime_cache(u64 nsec);
 
kernel/time/clocksource.c +47 -0

59 lines not on this page · raw message

kernel/time/tick-sched.c +43 -14

88 lines not on this page · raw message

kernel/time/timekeeping.c +11 -0
index 687dff4..659cae3 100644
@@ -271,6 +271,17 @@ int timekeeping_valid_for_hres(void)
 }
 
 /**
+ * timekeeping_max_deferment - Returns max time the clocksource can be deferred
+ *
+ * IMPORTANT: Caller must observe xtime_lock via read_seqbegin/read_seqretry
+ * to ensure that the clocksource does not change!
+ */
+s64 timekeeping_max_deferment(void)
+{
+	return clock->max_idle_ns;
+}
+
+/**
  * read_persistent_clock -  Return time in seconds from the persistent 

clock.
*
* Weak dummy function for arches that do not yet support it.

Signature · 1 line
1.6.1
author
#12 lore raw
Quoted 11 lines · Jon Hunter
Quoted 10 lines · Jon Hunter

kernel/time/tick-sched.c void tick_nohz_stop_sched_tick(int inidle) · line 314

Quoted 7 lines · Jon Hunter
kernel/time/tick-sched.c +7 -0
+		 * Calculate the time delta for the next timer event.
+		 * If the time delta exceeds the maximum time delta
+		 * permitted by the current clocksource then adjust
+		 * the time delta accordingly to ensure the
+		 * clocksource does not wrap.
+		 */
+		time_delta = tick_period.tv64 * delta_jiffies;

Thinking about this more, although it is very unlikely, for 64-bit machines there is a chance that the above multiply could overflow if delta_jiffies is very large.

Quoted 7 lines
Quoted 5 lines

tick_period.tv64 should always be less than NSEC_PER_SEC and so you would need delta_jiffies to be greater than 2^32 to cause overflow. On a 32-bit machine an unsigned long will not be greater than 2^32 as it is only 32-bits but this would be possible on a 64-bit machines.

So to be safe we should make sure that delta_jiffies is not greater than
NEXT_TIMER_MAX_DELTA (2^30 - 1) before doing the multiply. If you
think that this is a valid concern, then I can re-work and re-post. Sorry for not catching this before.

With regard to the above, to ensure that there are no overflows with the above calculation, I re-worked this patch a little. The below should be equivalent to the current code, just re-organised a little. Let me know if this would be acceptable or not.

Hi Thomas, John,

Did you guys have chance to review this? Let me know if you have any further comments/feedback.

Cheers
Jon