This solves the issue where jiffies can be stale and inaccurate.

Putting some prints, I see that basemono can be quite stale:
tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000

Since we have 'now' in ts->idle_entrytime, we can just use that. It is
more accurate, cleaner, reduces lines of code and reduces any lock
contention with the seq locks.

I was also concerned about issue where jiffies is not updated for a long
time, and then we receive a non-tick interrupt in the future. Relying on
stale jiffies value and using that as base can be inaccurate to determine
whether next event occurs within next tick. Fix that.

XXX: Need to fix issue in idle accounting which does 'jiffies -
idle_entrytime'. If idle_entrytime is more current than jiffies, it
could cause negative values. I could replace jiffies with idle_exittime
in this computation potentially to fix that.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 kernel/time/tick-sched.c | 27 +++++++--------------------
 1 file changed, 7 insertions(+), 20 deletions(-)

diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 4aa64266f2b0..22a4f96d9585 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -860,24 +860,6 @@ static inline bool local_timer_softirq_pending(void)
 	return local_softirq_pending() & BIT(TIMER_SOFTIRQ);
 }
 
-/*
- * Read jiffies and the time when jiffies were updated last
- */
-u64 get_jiffies_update(unsigned long *basej)
-{
-	unsigned long basejiff;
-	unsigned int seq;
-	u64 basemono;
-
-	do {
-		seq = read_seqcount_begin(&jiffies_seq);
-		basemono = last_jiffies_update;
-		basejiff = jiffies;
-	} while (read_seqcount_retry(&jiffies_seq, seq));
-	*basej = basejiff;
-	return basemono;
-}
-
 /**
  * tick_nohz_next_event() - return the clock monotonic based next event
  * @ts:		pointer to tick_sched struct
@@ -887,14 +869,19 @@ u64 get_jiffies_update(unsigned long *basej)
  * *%0		- When the next event is a maximum of TICK_NSEC in the future
  *		  and the tick is not stopped yet
  * *%next_event	- Next event based on clock monotonic
+ *
+ * Note: ts->idle_entrytime is updated with 'now' via tick_nohz_idle_enter().
  */
 static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
 {
-	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo;
+	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo, boot_ticks;
 	unsigned long basejiff;
 	int tick_cpu;
 
-	basemono = get_jiffies_update(&basejiff);
+	boot_ticks = DIV_ROUND_DOWN_ULL(ts->idle_entrytime, TICK_NSEC);
+	basejiff = boot_ticks + INITIAL_JIFFIES;
+	basemono = boot_ticks * TICK_NSEC;
+
 	ts->last_jiffies = basejiff;
 	ts->timer_expires_base = basemono;
 
-- 
2.47.0.277.g8800431eea-goog

On Fri, Nov 08 2024 at 17:48, Joel Fernandes wrote:
> This solves the issue where jiffies can be stale and inaccurate.

Which issue?

> Putting some prints, I see that basemono can be quite stale:
> tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000

What is your definition of stale? 3ms on a system with HZ < 1000 is
completely correct and within the margin of the next tick, no?

> Since we have 'now' in ts->idle_entrytime, we can just use that. It is
> more accurate, cleaner, reduces lines of code and reduces any lock
> contention with the seq locks.

What's more accurate and what is the actual problem you are trying to
solve. This handwaving about cleaner, less lines of code and contention
on a non existing lock is just not helpful.

> I was also concerned about issue where jiffies is not updated for a long
> time, and then we receive a non-tick interrupt in the future. Relying on
> stale jiffies value and using that as base can be inaccurate to determine
> whether next event occurs within next tick. Fix that.

I'm failing to decode this word salad.

> XXX: Need to fix issue in idle accounting which does 'jiffies -
> idle_entrytime'. If idle_entrytime is more current than jiffies, it
> could cause negative values. I could replace jiffies with idle_exittime
> in this computation potentially to fix that.

So you "fix" some yet to be correctly described issue by breaking stuff?

>  static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
>  {
> -	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo;
> +	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo, boot_ticks;
>  	unsigned long basejiff;
>  	int tick_cpu;
>  
> -	basemono = get_jiffies_update(&basejiff);
> +	boot_ticks = DIV_ROUND_DOWN_ULL(ts->idle_entrytime, TICK_NSEC);

Again this div/mult is more expensive than the sequence count on 32bit.

> -/*
> - * Read jiffies and the time when jiffies were updated last
> - */
> -u64 get_jiffies_update(unsigned long *basej)

How does this even compile? This function is global for a reason.

Thanks,

        tglx

On Tue, Nov 12, 2024 at 03:30:24PM +0100, Thomas Gleixner wrote:
> On Fri, Nov 08 2024 at 17:48, Joel Fernandes wrote:
> > This solves the issue where jiffies can be stale and inaccurate.
> 
> Which issue?

I will describe below.

> > Putting some prints, I see that basemono can be quite stale:
> > tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000
> 
> What is your definition of stale? 3ms on a system with HZ < 1000 is
> completely correct and within the margin of the next tick, no?

I am on HZ=1000. So 3ms is not within margin of the next tick for me.

> > Since we have 'now' in ts->idle_entrytime, we can just use that. It is
> > more accurate, cleaner, reduces lines of code and reduces any lock
> > contention with the seq locks.
> 
> What's more accurate and what is the actual problem you are trying to
> solve. This handwaving about cleaner, less lines of code and contention
> on a non existing lock is just not helpful.

Oh sure. the concern I have is that jiffies might be quite out of date for
whatever reason as I shared above with comparing the jiffies with
idle_entrytrime. I am not sure exactly why this happens, maybe because
interrupts were disabled on the do-timer CPU? But in any case I was concerned
about this code in tick_nohz_next_event():


	if (rcu_needs_cpu() || arch_needs_cpu() ||
	    irq_work_needs_cpu() || local_timer_softirq_pending()) {
		next_tick = basemono + TICK_NSEC;
	}

If we are using a stale basemono, that just seems wrong to me. If basemono
is stale, then next_tick could even be in the past?

> > I was also concerned about issue where jiffies is not updated for a long
> > time, and then we receive a non-tick interrupt in the future. Relying on
> > stale jiffies value and using that as base can be inaccurate to determine
> > whether next event occurs within next tick. Fix that.
> 
> I'm failing to decode this word salad.

I think I came up with an incorrect explanation of why basemono is lagging -
I have to look deeper into when basemono can be out-of-date - I certainly saw
it being lagging sometimes as I showed in the traces.

Anyway my broken word salad was something like: Say jiffies update did not
happen for a long time (can the tick be turned off on a do-timer CPU?). Then
say if a non-tick interrupt, like a device interrupt bring the CPU out of
idle, and then on the way back to idle, it tries to stop the tick. 'basemono'
would be quite out of date.

I am just speculating, I don't know exactly why I see basemono lagging. I
thought maybe we can fix that and avoid issues in the future that might show
up because of such inaccuracy.

Other theories?

I wonder if you're going to mention that this code works even if basemono is
out-of-date. But I am concerned that in 'low resolution mode', if we have an
hrtimer that is about to expire within the next tick, and if basemono is
lagging by several ticks, then could this code accidentally not keep the tick
alive thinking that the hrtimer is several ticks away?

> > XXX: Need to fix issue in idle accounting which does 'jiffies -
> > idle_entrytime'. If idle_entrytime is more current than jiffies, it
> > could cause negative values. I could replace jiffies with idle_exittime
> > in this computation potentially to fix that.
> 
> So you "fix" some yet to be correctly described issue by breaking stuff?

Its a side-effect of this patch, more adjustments are needed. This is just an
RFC, Thomas :-)

> >  static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
> >  {
> > -	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo;
> > +	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo, boot_ticks;
> >  	unsigned long basejiff;
> >  	int tick_cpu;
> >  
> > -	basemono = get_jiffies_update(&basejiff);
> > +	boot_ticks = DIV_ROUND_DOWN_ULL(ts->idle_entrytime, TICK_NSEC);
> 
> Again this div/mult is more expensive than the sequence count on 32bit.

Got it, I was hoping that there was a better way to calculate the number of
ticks without expensive div/mult, let me know if you had any ideas on that?
But it seems to me there isn't an alternative. So we may have to table this
idea. Also I think it suffers from the same tick-skew issue you mentioned I
think.

> > -/*
> > - * Read jiffies and the time when jiffies were updated last
> > - */
> > -u64 get_jiffies_update(unsigned long *basej)
> 
> How does this even compile? This function is global for a reason.

Yeah, sorry I had fixed the issue in my next revision when I adjusted the
timer migration code:

https://git.kernel.org/pub/scm/linux/kernel/git/jfern/linux.git/commit/?h=timers/tick-sched&id=1cf33bddf50341cf9802ed19374dc42d8466868b

thanks,

 - Joel

Le Fri, Nov 08, 2024 at 05:48:36PM +0000, Joel Fernandes (Google) a écrit :
> This solves the issue where jiffies can be stale and inaccurate.
> 
> Putting some prints, I see that basemono can be quite stale:
> tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000

That's 3 ms. If HZ < 1000 that's to be expected. But even with HZ = 1000 it can
happen.

> 
> Since we have 'now' in ts->idle_entrytime, we can just use that. It is
> more accurate, cleaner, reduces lines of code and reduces any lock
> contention with the seq locks.

Do we need such accuracy? The timers rely on jiffies anyway.
Also it's a seqcount read. Basically just a pair of smp_rmb().
Not sure a division would be cheaper.

> 
> I was also concerned about issue where jiffies is not updated for a long
> time, and then we receive a non-tick interrupt in the future. Relying on
> stale jiffies value and using that as base can be inaccurate to determine
> whether next event occurs within next tick. Fix that.
> 
> XXX: Need to fix issue in idle accounting which does 'jiffies -
> idle_entrytime'. If idle_entrytime is more current than jiffies, it
> could cause negative values. I could replace jiffies with idle_exittime
> in this computation potentially to fix that.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  kernel/time/tick-sched.c | 27 +++++++--------------------
>  1 file changed, 7 insertions(+), 20 deletions(-)
> 
> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> index 4aa64266f2b0..22a4f96d9585 100644
> --- a/kernel/time/tick-sched.c
> +++ b/kernel/time/tick-sched.c
> @@ -860,24 +860,6 @@ static inline bool local_timer_softirq_pending(void)
>  	return local_softirq_pending() & BIT(TIMER_SOFTIRQ);
>  }
>  
> -/*
> - * Read jiffies and the time when jiffies were updated last
> - */
> -u64 get_jiffies_update(unsigned long *basej)
> -{
> -	unsigned long basejiff;
> -	unsigned int seq;
> -	u64 basemono;
> -
> -	do {
> -		seq = read_seqcount_begin(&jiffies_seq);
> -		basemono = last_jiffies_update;
> -		basejiff = jiffies;
> -	} while (read_seqcount_retry(&jiffies_seq, seq));
> -	*basej = basejiff;
> -	return basemono;
> -}

This is used in tmigr as well.

Thanks.

On Mon, Nov 11, 2024 at 11:25:15PM +0100, Frederic Weisbecker wrote:
> Le Fri, Nov 08, 2024 at 05:48:36PM +0000, Joel Fernandes (Google) a écrit :
> > This solves the issue where jiffies can be stale and inaccurate.
> > 
> > Putting some prints, I see that basemono can be quite stale:
> > tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000
> 
> That's 3 ms. If HZ < 1000 that's to be expected. But even with HZ = 1000 it can
> happen.

For me HZ=1000 though.

> > Since we have 'now' in ts->idle_entrytime, we can just use that. It is
> > more accurate, cleaner, reduces lines of code and reduces any lock
> > contention with the seq locks.
> 
> Do we need such accuracy? The timers rely on jiffies anyway.
> Also it's a seqcount read. Basically just a pair of smp_rmb().
> Not sure a division would be cheaper.

In low resolution mode, hrtimers are also expired by the tick. It seems to
me, because of the error in jiffies, the clockevent programming for the tick
will also have errors which reflect in hrtimer expiry (granted if one does
not want errors in hrtimer, they shouldn't be using low-res mode, but
still a bounded error is better than an unpredictable unbounded one..).

I agree on the division issue though, I couldn't find an alternative.

Expanding on the previous paragraph, it seems to me that we will end up
programming the clockevent with incorrect values that are subject to the
error. Like if basemono is lagging by several ticks, then 'expires' value in
clock event may also be lagging.  Then after the clock event is programmed
with the erroneous value, the clockevent will wake up the CPU too soon I
think causing power wastage. If the jifies was accurate, the clockevent would
wake up the system more into the future..

Or do you see this scenario not playing out?

> > I was also concerned about issue where jiffies is not updated for a long
> > time, and then we receive a non-tick interrupt in the future. Relying on
> > stale jiffies value and using that as base can be inaccurate to determine
> > whether next event occurs within next tick. Fix that.
> > 
> > XXX: Need to fix issue in idle accounting which does 'jiffies -
> > idle_entrytime'. If idle_entrytime is more current than jiffies, it
> > could cause negative values. I could replace jiffies with idle_exittime
> > in this computation potentially to fix that.
> > 
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >  kernel/time/tick-sched.c | 27 +++++++--------------------
> >  1 file changed, 7 insertions(+), 20 deletions(-)
> > 
> > diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> > index 4aa64266f2b0..22a4f96d9585 100644
> > --- a/kernel/time/tick-sched.c
> > +++ b/kernel/time/tick-sched.c
> > @@ -860,24 +860,6 @@ static inline bool local_timer_softirq_pending(void)
> >  	return local_softirq_pending() & BIT(TIMER_SOFTIRQ);
> >  }
> >  
> > -/*
> > - * Read jiffies and the time when jiffies were updated last
> > - */
> > -u64 get_jiffies_update(unsigned long *basej)
> > -{
> > -	unsigned long basejiff;
> > -	unsigned int seq;
> > -	u64 basemono;
> > -
> > -	do {
> > -		seq = read_seqcount_begin(&jiffies_seq);
> > -		basemono = last_jiffies_update;
> > -		basejiff = jiffies;
> > -	} while (read_seqcount_retry(&jiffies_seq, seq));
> > -	*basej = basejiff;
> > -	return basemono;
> > -}
> 
> This is used in tmigr as well.

Yeah, sorry I had fixed the issue in my next revision when I adjusted the
timer migration code:

https://git.kernel.org/pub/scm/linux/kernel/git/jfern/linux.git/commit/?h=timers/tick-sched&id=1cf33bddf50341cf9802ed19374dc42d8466868b

I am on work travel this week, apologies for slow replies and thanks so much
for your replies and your discussions!

thanks,

 - Joel

On Fri, Nov 08, 2024 at 05:48:36PM +0000, Joel Fernandes (Google) wrote:
> This solves the issue where jiffies can be stale and inaccurate.
> 
> Putting some prints, I see that basemono can be quite stale:
> tick_nohz_next_event: basemono=18692000000 basemono_from_idle_entrytime=18695000000
> 
> Since we have 'now' in ts->idle_entrytime, we can just use that. It is
> more accurate, cleaner, reduces lines of code and reduces any lock
> contention with the seq locks.
> 
> I was also concerned about issue where jiffies is not updated for a long
> time, and then we receive a non-tick interrupt in the future. Relying on
> stale jiffies value and using that as base can be inaccurate to determine
> whether next event occurs within next tick. Fix that.
> 
> XXX: Need to fix issue in idle accounting which does 'jiffies -
> idle_entrytime'. If idle_entrytime is more current than jiffies, it
> could cause negative values. I could replace jiffies with idle_exittime
> in this computation potentially to fix that.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  kernel/time/tick-sched.c | 27 +++++++--------------------
>  1 file changed, 7 insertions(+), 20 deletions(-)
> 
> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> index 4aa64266f2b0..22a4f96d9585 100644
> --- a/kernel/time/tick-sched.c
> +++ b/kernel/time/tick-sched.c
> @@ -860,24 +860,6 @@ static inline bool local_timer_softirq_pending(void)
>  	return local_softirq_pending() & BIT(TIMER_SOFTIRQ);
>  }
>  
> -/*
> - * Read jiffies and the time when jiffies were updated last
> - */
> -u64 get_jiffies_update(unsigned long *basej)
> -{
> -	unsigned long basejiff;
> -	unsigned int seq;
> -	u64 basemono;
> -
> -	do {
> -		seq = read_seqcount_begin(&jiffies_seq);
> -		basemono = last_jiffies_update;
> -		basejiff = jiffies;
> -	} while (read_seqcount_retry(&jiffies_seq, seq));
> -	*basej = basejiff;
> -	return basemono;
> -}
> -
>  /**
>   * tick_nohz_next_event() - return the clock monotonic based next event
>   * @ts:		pointer to tick_sched struct
> @@ -887,14 +869,19 @@ u64 get_jiffies_update(unsigned long *basej)
>   * *%0		- When the next event is a maximum of TICK_NSEC in the future
>   *		  and the tick is not stopped yet
>   * *%next_event	- Next event based on clock monotonic
> + *
> + * Note: ts->idle_entrytime is updated with 'now' via tick_nohz_idle_enter().
>   */
>  static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
>  {
> -	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo;
> +	u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo, boot_ticks;
>  	unsigned long basejiff;
>  	int tick_cpu;
>  
> -	basemono = get_jiffies_update(&basejiff);
> +	boot_ticks = DIV_ROUND_DOWN_ULL(ts->idle_entrytime, TICK_NSEC);
> +	basejiff = boot_ticks + INITIAL_JIFFIES;
> +	basemono = boot_ticks * TICK_NSEC;
> +

There is a bug here, I end up overcounting basejiff. I did something like
this and it now makes basejiff equivalent to the previous code so should be
good. I'll work more on it this week...

                                                                                       ─╯
diff --git a/kernel/time/tick-common.c b/kernel/time/tick-common.c
index d88b13076b79..5387c67eea7a 100644
--- a/kernel/time/tick-common.c
+++ b/kernel/time/tick-common.c
@@ -34,6 +34,8 @@ DEFINE_PER_CPU(struct tick_device, tick_cpu_device);
  */
 ktime_t tick_next_period;

+ktime_t tick_first_period;
+
 /*
  * tick_do_timer_cpu is a timer core internal variable which holds the CPU NR
  * which is responsible for calling do_timer(), i.e. the timekeeping stuff. This
@@ -219,6 +221,7 @@ static void tick_setup_device(struct tick_device *td,
                if (READ_ONCE(tick_do_timer_cpu) == TICK_DO_TIMER_BOOT) {
                        WRITE_ONCE(tick_do_timer_cpu, cpu);
                        tick_next_period = ktime_get();
+                       tick_first_period = tick_next_period;
 #ifdef CONFIG_NO_HZ_FULL
                        /*
                         * The boot CPU may be nohz_full, in which case set
diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 5f2105e637bd..a15721516a85 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -20,6 +20,7 @@ struct timer_events {

 DECLARE_PER_CPU(struct tick_device, tick_cpu_device);
 extern ktime_t tick_next_period;
+extern ktime_t tick_first_period;
 extern int tick_do_timer_cpu __read_mostly;

 extern void tick_setup_periodic(struct clock_event_device *dev, int broadcast);
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 8a245f8ceb56..8fdfda4b8af3 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -895,11 +896,23 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
        u64 basemono, next_tick, delta, expires, delta_hr, next_hr_wo, boot_ticks;
        unsigned long basejiff;
        int tick_cpu;

        boot_ticks = DIV_ROUND_DOWN_ULL(ts->idle_entrytime, TICK_NSEC);
        basejiff = boot_ticks + INITIAL_JIFFIES;
        basemono = boot_ticks * TICK_NSEC;

+       /*
+        * There is some time that passes between when clocksource starts and the
+        * first time tick device is setup. Offset basejiff by that.
+       */
+       basejiff -= DIV_ROUND_DOWN_ULL(tick_first_period, TICK_NSEC);
+
        ts->last_jiffies = basejiff;
        ts->timer_expires_base = basemono;

On Sun, Nov 10 2024 at 22:55, Joel Fernandes wrote:
>
> +       /*
> +        * There is some time that passes between when clocksource starts and the
> +        * first time tick device is setup. Offset basejiff by that.
> +       */
> +       basejiff -= DIV_ROUND_DOWN_ULL(tick_first_period, TICK_NSEC);

We clearly need yet another division here. Especially as that division
results in the exactly same value every time.

On Tue, Nov 12, 2024 at 03:48:43PM +0100, Thomas Gleixner wrote:
> On Sun, Nov 10 2024 at 22:55, Joel Fernandes wrote:
> >
> > +       /*
> > +        * There is some time that passes between when clocksource starts and the
> > +        * first time tick device is setup. Offset basejiff by that.
> > +       */
> > +       basejiff -= DIV_ROUND_DOWN_ULL(tick_first_period, TICK_NSEC);
> 
> We clearly need yet another division here. Especially as that division
> results in the exactly same value every time.

Yeah I fixed it in my v2 but did not post it yet:

https://git.kernel.org/pub/scm/linux/kernel/git/jfern/linux.git/commit/?h=timers/tick-sched&id=60707e27418e3bca026be0bd9b1eacfe2a6ce72a

I will hold back on posting till we finish discussing on this RFC.

thanks,

 - Joel