Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1440162 > unrolled thread

[PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency Nicolai Stange <nicstange@gmail.com> - 2016-07-10 21:40 +0200
    Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency Nicolai Stange <nicstange@gmail.com> - 2016-07-11 08:40 +0200
      Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic  clock's dynamic frequency Thomas Gleixner <tglx@linutronix.de> - 2016-07-11 10:40 +0200
        Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency Nicolai Stange <nicstange@gmail.com> - 2016-07-12 13:20 +0200
          Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic  clock's dynamic frequency Thomas Gleixner <tglx@linutronix.de> - 2016-07-12 17:10 +0200
            Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency Nicolai Stange <nicstange@gmail.com> - 2016-07-13 15:20 +0200

#1440162 — [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency

With NOHZ_FULL and one single well-isolated, CPU consumptive task, one
would expect approximately one clockevent interrupt per second. However, on
my Intel Haswell where the monotonic clock is the TSC monotonic clock and
the clockevent device is the TSC deadline device, it turns out that every
second, there are two such interrupts: the first one arrives always
approximately ~50us before the scheduled deadline as programmed by
tick_nohz_stop_sched_tick() through the hrtimer API. The
__hrtimer_run_queues() called in this interrupt detects that the queued
tick_sched_timer hasn't expired yet and simply does nothing except
reprogramming the clock event device to fire shortly after again.

These too early programmed deadlines are explained as follows:
clockevents_program_event() programs the clockevent device to fire
after
  f_event * delta_t_progr
clockevent device cycles where f_event is the clockevent device's hardware
frequency and delta_t_progr is the requested time interval. After that many
clockevent device cycles have elapsed, the device underlying the monotonic
clock, that is the monotonic raw clock has seen f_raw / f_event as many
cycles.
The ktime_get() called from __hrtimer_run_queues() interprets those
cycles to run at the frequency of the monotonic clock. Summarizing:
  delta_t_perc = 1/f_mono * f_raw/f_event * f_event * delta_t_progr
               = f_raw / f_mono * delta_t_progr
with f_mono being the monotonic clock's frequency and delta_t_perc being
the elapsed time interval as perceived by __hrtimer_run_queues().

Now, f_mono is not a constant, but is dynamically adjusted in
timekeeping_adjust() in order to compensate for the NTP error. With the
large values of delta_t_progr of 10^9ns with NOHZ_FULL, the error made
becomes significant and results in the double timer interrupts described
above.

Compensate for this error by multiplying delta_t_progr with f_mono / f_raw
in clockevents_program_event() before actually programming the clockevent
device.

Namely, introduce a helper, timekeeping_mono_interval_to_raw(), which
converts a given time interval from the monotonic clock's perception to
that of the raw monotonic clock by multiplying the value by f_mono / f_raw.
Call that helper from clockevents_program_event() in order to obtain a
suitable time interval to program the clockevent device with.

Signed-off-by: Nicolai Stange <nicstange@gmail.com>
---
 kernel/time/clockevents.c |  1 +
 kernel/time/timekeeping.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++
 kernel/time/timekeeping.h |  1 +
 3 files changed, 61 insertions(+)

diff --git a/kernel/time/clockevents.c b/kernel/time/clockevents.c
index a9b76a4..4bccf04 100644
--- a/kernel/time/clockevents.c
+++ b/kernel/time/clockevents.c
@@ -329,6 +329,7 @@ int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
 		return dev->set_next_ktime(expires, dev);
 
 	delta = ktime_to_ns(ktime_sub(expires, ktime_get()));
+	delta = timekeeping_mono_interval_to_raw(delta);
 	if (delta <= 0)
 		return force ? clockevents_program_min_delta(dev) : -ETIME;
 
diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index dcd5ce6..51dfbbb 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -23,6 +23,7 @@
 #include <linux/stop_machine.h>
 #include <linux/pvclock_gtod.h>
 #include <linux/compiler.h>
+#include <asm/div64.h>
 
 #include "tick-internal.h"
 #include "ntp_internal.h"
@@ -2133,6 +2134,64 @@ out:
 }
 
 /**
+ * timekeeper_mono_interval_to_raw - Convert mono interval to raw's perception.
+ * @interval: Time interval as measured by the mono clock.
+ *
+ * Converts the given time interval as measured by the monotonic clock to
+ * what would have been measured by the raw monotonic clock in the meanwhile.
+ * The monotonic clock's frequency gets dynamically adjusted every now and then
+ * in order to compensate for the differences to NTP. OTOH, the clockevents
+ * devices are not affected by this adjustment, i.e. they keep ticking at some
+ * fixed hardware frequency which may be assumed to have a constant ratio to
+ * the fixed raw monotonic clock's frequency. This function provides a means
+ * to convert time intervals from the dynamic frequency monotonic clock to
+ * the fixed frequency hardware world.
+ *
+ * If interval < 0, zero is returned. If an overflow happens during the
+ * calculation, KTIME_MAX is returned.
+ */
+s64 timekeeping_mono_interval_to_raw(s64 interval)
+{
+	struct timekeeper *tk = &tk_core.timekeeper;
+	u32 raw_mult = tk->tkr_raw.mult, mono_mult = tk->tkr_mono.mult;
+	u64 raw, tmp;
+
+	/* The overflow checks below can't deal with negative intervals. */
+	if (interval <= 0)
+		return 0;
+
+	/*
+	 * Calculate
+	 *   raw = f_mono / f_raw * interval
+	 *       = (raw_mult / 2^raw_shift) / (mono_mult / 2^mono_shift)
+	 *            * interval
+	 * where f_mono and f_raw denote the frequencies of the monotonic
+	 * and raw clock respectively.
+	 *
+	 * Note that the monotonic and raw clocks' shifts are equal and fixed,
+	 * that is they cancel.
+	 */
+
+	/* First, calculate interval * raw_mult while checking for overflow. */
+	raw = ((u64)interval >> 32) * raw_mult; /* Upper half of interval */
+	if (raw >> 32)
+		return KTIME_MAX;
+	raw <<= 32;
+	tmp = ((u64)interval & U32_MAX) * raw_mult; /* Lower half of interval */
+	if (U64_MAX - raw < tmp)
+		return KTIME_MAX;
+	raw += tmp;
+
+	/* Finally, do raw /= mono_mult with proper rounding. */
+	if (U64_MAX - raw < mono_mult / 2)
+		return KTIME_MAX;
+	raw += mono_mult / 2;
+	do_div(raw, mono_mult);
+
+	return (s64)raw;
+}
+
+/**
  * getboottime64 - Return the real time of system boot.
  * @ts:		pointer to the timespec64 to be set
  *
diff --git a/kernel/time/timekeeping.h b/kernel/time/timekeeping.h
index 704f595..40a0fa9 100644
--- a/kernel/time/timekeeping.h
+++ b/kernel/time/timekeeping.h
@@ -18,6 +18,7 @@ extern void timekeeping_resume(void);
 
 extern void do_timer(unsigned long ticks);
 extern void update_wall_time(void);
+extern s64 timekeeping_mono_interval_to_raw(s64 interval);
 
 extern seqlock_t jiffies_lock;
 
-- 
2.9.0

[toc] | [next] | [standalone]

#1440279

Nicolai Stange <nicstange@gmail.com> writes:

> With NOHZ_FULL and one single well-isolated, CPU consumptive task, one
> would expect approximately one clockevent interrupt per second. However, on
> my Intel Haswell where the monotonic clock is the TSC monotonic clock and
> the clockevent device is the TSC deadline device, it turns out that every
> second, there are two such interrupts: the first one arrives always
> approximately ~50us before the scheduled deadline as programmed by
> tick_nohz_stop_sched_tick() through the hrtimer API. The
> __hrtimer_run_queues() called in this interrupt detects that the queued
> tick_sched_timer hasn't expired yet and simply does nothing except
> reprogramming the clock event device to fire shortly after again.
>
> These too early programmed deadlines are explained as follows:
> clockevents_program_event() programs the clockevent device to fire
> after
>   f_event * delta_t_progr
> clockevent device cycles where f_event is the clockevent device's hardware
> frequency and delta_t_progr is the requested time interval. After that many
> clockevent device cycles have elapsed, the device underlying the monotonic
> clock, that is the monotonic raw clock has seen f_raw / f_event as many
> cycles.
> The ktime_get() called from __hrtimer_run_queues() interprets those
> cycles to run at the frequency of the monotonic clock. Summarizing:
>   delta_t_perc = 1/f_mono * f_raw/f_event * f_event * delta_t_progr
>                = f_raw / f_mono * delta_t_progr
> with f_mono being the monotonic clock's frequency and delta_t_perc being
> the elapsed time interval as perceived by __hrtimer_run_queues().
>
> Now, f_mono is not a constant, but is dynamically adjusted in
> timekeeping_adjust() in order to compensate for the NTP error. With the
> large values of delta_t_progr of 10^9ns with NOHZ_FULL, the error made
> becomes significant and results in the double timer interrupts described
> above.
>
> Compensate for this error by multiplying delta_t_progr with f_mono / f_raw
> in clockevents_program_event() before actually programming the clockevent
> device.
>
> Namely, introduce a helper, timekeeping_mono_interval_to_raw(), which
> converts a given time interval from the monotonic clock's perception to
> that of the raw monotonic clock by multiplying the value by f_mono / f_raw.
> Call that helper from clockevents_program_event() in order to obtain a
> suitable time interval to program the clockevent device with.
>
> Signed-off-by: Nicolai Stange <nicstange@gmail.com>
> ---
>  kernel/time/clockevents.c |  1 +
>  kernel/time/timekeeping.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++
>  kernel/time/timekeeping.h |  1 +
>  3 files changed, 61 insertions(+)
>
> diff --git a/kernel/time/clockevents.c b/kernel/time/clockevents.c
> index a9b76a4..4bccf04 100644
> --- a/kernel/time/clockevents.c
> +++ b/kernel/time/clockevents.c
> @@ -329,6 +329,7 @@ int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
>  		return dev->set_next_ktime(expires, dev);
>  
>  	delta = ktime_to_ns(ktime_sub(expires, ktime_get()));
> +	delta = timekeeping_mono_interval_to_raw(delta);
>  	if (delta <= 0)
>  		return force ? clockevents_program_min_delta(dev) : -ETIME;
>  
> diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> index dcd5ce6..51dfbbb 100644
> --- a/kernel/time/timekeeping.c
> +++ b/kernel/time/timekeeping.c
> @@ -23,6 +23,7 @@
>  #include <linux/stop_machine.h>
>  #include <linux/pvclock_gtod.h>
>  #include <linux/compiler.h>
> +#include <asm/div64.h>
>  
>  #include "tick-internal.h"
>  #include "ntp_internal.h"
> @@ -2133,6 +2134,64 @@ out:
>  }
>  
>  /**
> + * timekeeper_mono_interval_to_raw - Convert mono interval to raw's perception.
> + * @interval: Time interval as measured by the mono clock.
> + *
> + * Converts the given time interval as measured by the monotonic clock to
> + * what would have been measured by the raw monotonic clock in the meanwhile.
> + * The monotonic clock's frequency gets dynamically adjusted every now and then
> + * in order to compensate for the differences to NTP. OTOH, the clockevents
> + * devices are not affected by this adjustment, i.e. they keep ticking at some
> + * fixed hardware frequency which may be assumed to have a constant ratio to
> + * the fixed raw monotonic clock's frequency. This function provides a means
> + * to convert time intervals from the dynamic frequency monotonic clock to
> + * the fixed frequency hardware world.
> + *
> + * If interval < 0, zero is returned. If an overflow happens during the
> + * calculation, KTIME_MAX is returned.
> + */
> +s64 timekeeping_mono_interval_to_raw(s64 interval)
> +{
> +	struct timekeeper *tk = &tk_core.timekeeper;
> +	u32 raw_mult = tk->tkr_raw.mult, mono_mult = tk->tkr_mono.mult;
> +	u64 raw, tmp;
> +
> +	/* The overflow checks below can't deal with negative intervals. */
> +	if (interval <= 0)
> +		return 0;
> +
> +	/*
> +	 * Calculate
> +	 *   raw = f_mono / f_raw * interval
> +	 *       = (raw_mult / 2^raw_shift) / (mono_mult / 2^mono_shift)
> +	 *            * interval
> +	 * where f_mono and f_raw denote the frequencies of the monotonic
> +	 * and raw clock respectively.
> +	 *
> +	 * Note that the monotonic and raw clocks' shifts are equal and fixed,
> +	 * that is they cancel.
> +	 */
> +
> +	/* First, calculate interval * raw_mult while checking for overflow. */

After thinking further about this, I had to recognize that
  (raw_mult - mono_mult) * interval
is *much* less likely to overflow.

So, I'll send a v3 doing

  raw = interval + (((raw_mult - mono_mult) * interval) / mono_mult)

during the course of the day.



> +	raw = ((u64)interval >> 32) * raw_mult; /* Upper half of interval */
> +	if (raw >> 32)
> +		return KTIME_MAX;
> +	raw <<= 32;
> +	tmp = ((u64)interval & U32_MAX) * raw_mult; /* Lower half of interval */
> +	if (U64_MAX - raw < tmp)
> +		return KTIME_MAX;
> +	raw += tmp;
> +
> +	/* Finally, do raw /= mono_mult with proper rounding. */
> +	if (U64_MAX - raw < mono_mult / 2)
> +		return KTIME_MAX;
> +	raw += mono_mult / 2;
> +	do_div(raw, mono_mult);
> +
> +	return (s64)raw;
> +}
> +
> +/**
>   * getboottime64 - Return the real time of system boot.
>   * @ts:		pointer to the timespec64 to be set
>   *
> diff --git a/kernel/time/timekeeping.h b/kernel/time/timekeeping.h
> index 704f595..40a0fa9 100644
> --- a/kernel/time/timekeeping.h
> +++ b/kernel/time/timekeeping.h
> @@ -18,6 +18,7 @@ extern void timekeeping_resume(void);
>  
>  extern void do_timer(unsigned long ticks);
>  extern void update_wall_time(void);
> +extern s64 timekeeping_mono_interval_to_raw(s64 interval);
>  
>  extern seqlock_t jiffies_lock;

[toc] | [prev] | [next] | [standalone]

#1440359 — Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency

On Mon, 11 Jul 2016, Nicolai Stange wrote:
> > +	raw = ((u64)interval >> 32) * raw_mult; /* Upper half of interval */
> > +	if (raw >> 32)
> > +		return KTIME_MAX;
> > +	raw <<= 32;
> > +	tmp = ((u64)interval & U32_MAX) * raw_mult; /* Lower half of interval */
> > +	if (U64_MAX - raw < tmp)
> > +		return KTIME_MAX;
> > +	raw += tmp;
> > +
> > +	/* Finally, do raw /= mono_mult with proper rounding. */
> > +	if (U64_MAX - raw < mono_mult / 2)
> > +		return KTIME_MAX;
> > +	raw += mono_mult / 2;
> > +	do_div(raw, mono_mult);
> > +
> > +	return (s64)raw;

That's a complete insanity. No way that we are going to do all this math in
the CE programming path.

If you want to address the issue, then you need to find a way to adjust the
mult/shift factors of the clock event device occasionally.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1441257

Thomas Gleixner <tglx@linutronix.de> writes:

> On Mon, 11 Jul 2016, Nicolai Stange wrote:
>> > +	raw = ((u64)interval >> 32) * raw_mult; /* Upper half of interval */
>> > +	if (raw >> 32)
>> > +		return KTIME_MAX;
>> > +	raw <<= 32;
>> > +	tmp = ((u64)interval & U32_MAX) * raw_mult; /* Lower half of interval */
>> > +	if (U64_MAX - raw < tmp)
>> > +		return KTIME_MAX;
>> > +	raw += tmp;
>> > +
>> > +	/* Finally, do raw /= mono_mult with proper rounding. */
>> > +	if (U64_MAX - raw < mono_mult / 2)
>> > +		return KTIME_MAX;
>> > +	raw += mono_mult / 2;
>> > +	do_div(raw, mono_mult);
>> > +
>> > +	return (s64)raw;
>
> That's a complete insanity. No way that we are going to do all this math in
> the CE programming path.
>
> If you want to address the issue, then you need to find a way to adjust the
> mult/shift factors of the clock event device occasionally.

I tried adjusting the clock event device's ->mult, triggered by
timekeeping_apply_adjustment() and it works well.

I think that in order to avoid error accumulation, it is best not to do
any incremental updates to ->mult, but introduce a new ->mult_mono and
recalculate the latter from the former.

Now, the ->mult_mono needs to get updated when the driver updates
->mult. Certainly, hooking into clockevents_register_device() and
clockevents_update_freq() is the method of choice here. However,
there are a handful of drivers which set ->mult from
->set_state_oneshot() either by direct assignment or through
clockevents_config():
  drivers/clocksource/sh_cmt.c
  drivers/clocksource/sh_tmu.c
  drivers/clocksource/em_sti.c
  drivers/clocksource/h8300_timer8.c
Converting these to clockevents_update_freq() seems straightforward
though.


Another issue is that ->min_delta_ns and ->max_delta_ns are measured in
raw clock time while the delta in clockevents_program_event() would now
be interpreted as being in monotonic clock time:
  clc = ((unsigned long long) delta * dev->mult_mono) >> dev->shift;

Ideally, I'd like to get rid of ->min_delta_ns and ->max_delta_ns
alltogether and consistently use the ->min_delta_ticks and
->max_delta_ticks instead. AFAICS, ->min_delta_ns is really needed only
for setting dev->next_event in clockevents_program_min_delta().
dev->next_event is read only from __clockevents_update_freq() for
reprogramming purposes and thus, assuming 0 for ->delta_min_ns in
clockevents_program_min_delta() would probably work: a reprogramming
would invoke clockevents_program_min_delta() once again.

The downside of this approach is that a quick grep reveals 40 clockevent
device drivers whose initialization code would need to get touched in
order to convert them from min_delta_ns/max_delta_ns to
min_delta_ticks/max_delta_ticks.


So, the question is whether I should do all of this or whether the
doubled timer interrupts aren't annoying enough to justify such a big
change?


Thanks,

Nicolai

[toc] | [prev] | [next] | [standalone]

#1441484 — Re: [PATCH v2 4/4] kernel/time/clockevents: compensate for monotonic clock's dynamic frequency

On Tue, 12 Jul 2016, Nicolai Stange wrote:
> I tried adjusting the clock event device's ->mult, triggered by
> timekeeping_apply_adjustment() and it works well.
> 
> I think that in order to avoid error accumulation, it is best not to do
> any incremental updates to ->mult, but introduce a new ->mult_mono and
> recalculate the latter from the former.
> 
> Now, the ->mult_mono needs to get updated when the driver updates
> ->mult. Certainly, hooking into clockevents_register_device() and
> clockevents_update_freq() is the method of choice here. However,
> there are a handful of drivers which set ->mult from
> ->set_state_oneshot() either by direct assignment or through
> clockevents_config():
>   drivers/clocksource/sh_cmt.c
>   drivers/clocksource/sh_tmu.c
>   drivers/clocksource/em_sti.c
>   drivers/clocksource/h8300_timer8.c
> Converting these to clockevents_update_freq() seems straightforward
> though.

Ok.
 
> Another issue is that ->min_delta_ns and ->max_delta_ns are measured in
> raw clock time while the delta in clockevents_program_event() would now
> be interpreted as being in monotonic clock time:
>   clc = ((unsigned long long) delta * dev->mult_mono) >> dev->shift;

Does that really matter much?

> Ideally, I'd like to get rid of ->min_delta_ns and ->max_delta_ns
> alltogether and consistently use the ->min_delta_ticks and
> ->max_delta_ticks instead. AFAICS, ->min_delta_ns is really needed only
> for setting dev->next_event in clockevents_program_min_delta().
> dev->next_event is read only from __clockevents_update_freq() for
> reprogramming purposes and thus, assuming 0 for ->delta_min_ns in
> clockevents_program_min_delta() would probably work: a reprogramming
> would invoke clockevents_program_min_delta() once again.

I completely fail to parse the above paragraph. 
 
> The downside of this approach is that a quick grep reveals 40 clockevent
> device drivers whose initialization code would need to get touched in
> order to convert them from min_delta_ns/max_delta_ns to
> min_delta_ticks/max_delta_ticks.
> 
> So, the question is whether I should do all of this or whether the
> doubled timer interrupts aren't annoying enough to justify such a big
> change?

Can you provide an initial patch which does the adjustment w/o all the related
churn so we can see how intrusive that gets?

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1442449

Thomas Gleixner <tglx@linutronix.de> writes:

> On Tue, 12 Jul 2016, Nicolai Stange wrote:
>> Another issue is that ->min_delta_ns and ->max_delta_ns are measured in
>> raw clock time while the delta in clockevents_program_event() would now
>> be interpreted as being in monotonic clock time:
>>   clc = ((unsigned long long) delta * dev->mult_mono) >> dev->shift;
>
> Does that really matter much?
>
>> Ideally, I'd like to get rid of ->min_delta_ns and ->max_delta_ns
>> alltogether and consistently use the ->min_delta_ticks and
>> ->max_delta_ticks instead. AFAICS, ->min_delta_ns is really needed only
>> for setting dev->next_event in clockevents_program_min_delta().
>> dev->next_event is read only from __clockevents_update_freq() for
>> reprogramming purposes and thus, assuming 0 for ->delta_min_ns in
>> clockevents_program_min_delta() would probably work: a reprogramming
>> would invoke clockevents_program_min_delta() once again.
>
> I completely fail to parse the above paragraph. 
>  
>> The downside of this approach is that a quick grep reveals 40 clockevent
>> device drivers whose initialization code would need to get touched in
>> order to convert them from min_delta_ns/max_delta_ns to
>> min_delta_ticks/max_delta_ticks.
>> 
>> So, the question is whether I should do all of this or whether the
>> doubled timer interrupts aren't annoying enough to justify such a big
>> change?
>
> Can you provide an initial patch which does the adjustment w/o all the related
> churn so we can see how intrusive that gets?

Please see the RFC tagged series at
  http://lkml.kernel.org/g/20160713130017.8202-1-nicstange@gmail.com
I tried to answer/address your above questions in the cover letter.

Note that I split the x86 TSC related patches off:
  http://lkml.kernel.org/g/20160713130344.8319-1-nicstange@gmail.com

Thanks,

Nicolai

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web