From: Adrian Hunter <adrian.hunter@intel.com> To: Thomas Gleixner <tglx@linutronix.de> Cc: Peter Zijlstra <peterz@infradead.org>, Dave Hansen <dave.hansen@linux.intel.com>, John Stultz <jstultz@google.com>, "H. Peter Anvin" <hpa@zytor.com>, Alexander Gordeev <agordeev@linux.ibm.com>, Vincenzo Frascino <vincenzo.frascino@arm.com>, linux-s390@vger.kernel.org, Arnd Bergmann <arnd@arndb.de>, x86@kernel.org, "Aneesh Kumar K.V" <aneesh.kumar@kernel.org>, Ingo Molnar <mingo@redhat.com>, "Naveen N. Rao" <naveen.n.rao@linux.ibm.com>, Christian Borntraeger <borntraeger@linux.ibm.com>, Vasily Gorbik <gor@linux.ibm.com>, Heiko Carstens <hca@linux.ibm.com>, Nicholas Piggin <npiggin@gmail.com>, Borislav Petkov <bp@alien8.de>, Andy Lutomirski <luto@kernel.org>, Bjorn Helgaas <bhelgaas@google.com>, Anna-Maria Behnsen <anna-maria@linutronix.de>, Stephen Boyd <sboyd@kernel.org>, Randy Dunlap <rdunlap@infradead.org>, linux-kernel@vger.kernel.org, Sven Schnelle <svens@linux.ibm.com>, linuxppc-dev@lists.ozlabs.org Subject: [PATCH V2 17/19] timekeeping: Make delta calculation overflow safe Date: Mon, 25 Mar 2024 08:40:21 +0200 [thread overview] Message-ID: <20240325064023.2997-18-adrian.hunter@intel.com> (raw) In-Reply-To: <20240325064023.2997-1-adrian.hunter@intel.com> Kernel timekeeping is designed to keep the change in cycles (since the last timer interrupt) below max_cycles, which prevents multiplication overflow when converting cycles to nanoseconds. However, if timer interrupts stop, the calculation will eventually overflow. Add protection against that. In timekeeping_cycles_to_ns() calculation, check against max_cycles, falling back to a slower higher precision calculation. In timekeeping_forward_now(), process delta in chunks of at most max_cycles. Suggested-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Adrian Hunter <adrian.hunter@intel.com> --- kernel/time/timekeeping.c | 40 ++++++++++++++++++++++++++++----------- 1 file changed, 29 insertions(+), 11 deletions(-) diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c index d17484082e2c..111dfdbd488f 100644 --- a/kernel/time/timekeeping.c +++ b/kernel/time/timekeeping.c @@ -364,19 +364,32 @@ static void tk_setup_internals(struct timekeeper *tk, struct clocksource *clock) } /* Timekeeper helper functions. */ +static noinline u64 delta_to_ns_safe(const struct tk_read_base *tkr, u64 delta) +{ + return mul_u64_u32_add_u64_shr(delta, tkr->mult, tkr->xtime_nsec, tkr->shift); +} + static inline u64 timekeeping_cycles_to_ns(const struct tk_read_base *tkr, u64 cycles) { /* Calculate the delta since the last update_wall_time() */ u64 mask = tkr->mask, delta = (cycles - tkr->cycle_last) & mask; - if (IS_ENABLED(CONFIG_CLOCKSOURCE_VALIDATE_LAST_CYCLE)) { - /* - * Handle clocksource inconsistency between CPUs to prevent - * time from going backwards by checking for the MSB of the - * mask being set in the delta. - */ - if (unlikely(delta & ~(mask >> 1))) - return tkr->xtime_nsec >> tkr->shift; + /* + * This detects the case where the delta overflows the multiplication + * with tkr->mult. + */ + if (unlikely(delta > tkr->clock->max_cycles)) { + if (IS_ENABLED(CONFIG_CLOCKSOURCE_VALIDATE_LAST_CYCLE)) { + /* + * Handle clocksource inconsistency between CPUs to prevent + * time from going backwards by checking for the MSB of the + * mask being set in the delta. + */ + if (unlikely(delta & ~(mask >> 1))) + return tkr->xtime_nsec >> tkr->shift; + } + + return delta_to_ns_safe(tkr, delta); } return ((delta * tkr->mult) + tkr->xtime_nsec) >> tkr->shift; @@ -789,10 +802,15 @@ static void timekeeping_forward_now(struct timekeeper *tk) tk->tkr_mono.cycle_last = cycle_now; tk->tkr_raw.cycle_last = cycle_now; - tk->tkr_mono.xtime_nsec += delta * tk->tkr_mono.mult; - tk->tkr_raw.xtime_nsec += delta * tk->tkr_raw.mult; + while (delta > 0) { + u64 max = tk->tkr_mono.clock->max_cycles; + u64 incr = delta < max ? delta : max; - tk_normalize_xtime(tk); + tk->tkr_mono.xtime_nsec += incr * tk->tkr_mono.mult; + tk->tkr_raw.xtime_nsec += incr * tk->tkr_raw.mult; + tk_normalize_xtime(tk); + delta -= incr; + } } /** -- 2.34.1
WARNING: multiple messages have this Message-ID (diff)
From: Adrian Hunter <adrian.hunter@intel.com> To: Thomas Gleixner <tglx@linutronix.de> Cc: Michael Ellerman <mpe@ellerman.id.au>, Nicholas Piggin <npiggin@gmail.com>, Christophe Leroy <christophe.leroy@csgroup.eu>, "Aneesh Kumar K.V" <aneesh.kumar@kernel.org>, "Naveen N. Rao" <naveen.n.rao@linux.ibm.com>, Heiko Carstens <hca@linux.ibm.com>, Vasily Gorbik <gor@linux.ibm.com>, Alexander Gordeev <agordeev@linux.ibm.com>, Christian Borntraeger <borntraeger@linux.ibm.com>, Sven Schnelle <svens@linux.ibm.com>, Ingo Molnar <mingo@redhat.com>, Borislav Petkov <bp@alien8.de>, Dave Hansen <dave.hansen@linux.intel.com>, x86@kernel.org, "H. Peter Anvin" <hpa@zytor.com>, Andy Lutomirski <luto@kernel.org>, Vincenzo Frascino <vincenzo.frascino@arm.com>, John Stultz <jstultz@google.com>, Stephen Boyd <sboyd@kernel.org>, Peter Zijlstra <peterz@infradead.org>, Randy Dunlap <rdunlap@infradead.org>, Bjorn Helgaas <bhelgaas@google.com>, Arnd Bergmann <arnd@arndb.de>, Anna-Maria Behnsen <anna-maria@linutronix.de>, linuxppc-dev@lists.ozlabs.org, linux-kernel@vger.kernel.org, linux-s390@vger.kernel.org Subject: [PATCH V2 17/19] timekeeping: Make delta calculation overflow safe Date: Mon, 25 Mar 2024 08:40:21 +0200 [thread overview] Message-ID: <20240325064023.2997-18-adrian.hunter@intel.com> (raw) In-Reply-To: <20240325064023.2997-1-adrian.hunter@intel.com> Kernel timekeeping is designed to keep the change in cycles (since the last timer interrupt) below max_cycles, which prevents multiplication overflow when converting cycles to nanoseconds. However, if timer interrupts stop, the calculation will eventually overflow. Add protection against that. In timekeeping_cycles_to_ns() calculation, check against max_cycles, falling back to a slower higher precision calculation. In timekeeping_forward_now(), process delta in chunks of at most max_cycles. Suggested-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Adrian Hunter <adrian.hunter@intel.com> --- kernel/time/timekeeping.c | 40 ++++++++++++++++++++++++++++----------- 1 file changed, 29 insertions(+), 11 deletions(-) diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c index d17484082e2c..111dfdbd488f 100644 --- a/kernel/time/timekeeping.c +++ b/kernel/time/timekeeping.c @@ -364,19 +364,32 @@ static void tk_setup_internals(struct timekeeper *tk, struct clocksource *clock) } /* Timekeeper helper functions. */ +static noinline u64 delta_to_ns_safe(const struct tk_read_base *tkr, u64 delta) +{ + return mul_u64_u32_add_u64_shr(delta, tkr->mult, tkr->xtime_nsec, tkr->shift); +} + static inline u64 timekeeping_cycles_to_ns(const struct tk_read_base *tkr, u64 cycles) { /* Calculate the delta since the last update_wall_time() */ u64 mask = tkr->mask, delta = (cycles - tkr->cycle_last) & mask; - if (IS_ENABLED(CONFIG_CLOCKSOURCE_VALIDATE_LAST_CYCLE)) { - /* - * Handle clocksource inconsistency between CPUs to prevent - * time from going backwards by checking for the MSB of the - * mask being set in the delta. - */ - if (unlikely(delta & ~(mask >> 1))) - return tkr->xtime_nsec >> tkr->shift; + /* + * This detects the case where the delta overflows the multiplication + * with tkr->mult. + */ + if (unlikely(delta > tkr->clock->max_cycles)) { + if (IS_ENABLED(CONFIG_CLOCKSOURCE_VALIDATE_LAST_CYCLE)) { + /* + * Handle clocksource inconsistency between CPUs to prevent + * time from going backwards by checking for the MSB of the + * mask being set in the delta. + */ + if (unlikely(delta & ~(mask >> 1))) + return tkr->xtime_nsec >> tkr->shift; + } + + return delta_to_ns_safe(tkr, delta); } return ((delta * tkr->mult) + tkr->xtime_nsec) >> tkr->shift; @@ -789,10 +802,15 @@ static void timekeeping_forward_now(struct timekeeper *tk) tk->tkr_mono.cycle_last = cycle_now; tk->tkr_raw.cycle_last = cycle_now; - tk->tkr_mono.xtime_nsec += delta * tk->tkr_mono.mult; - tk->tkr_raw.xtime_nsec += delta * tk->tkr_raw.mult; + while (delta > 0) { + u64 max = tk->tkr_mono.clock->max_cycles; + u64 incr = delta < max ? delta : max; - tk_normalize_xtime(tk); + tk->tkr_mono.xtime_nsec += incr * tk->tkr_mono.mult; + tk->tkr_raw.xtime_nsec += incr * tk->tkr_raw.mult; + tk_normalize_xtime(tk); + delta -= incr; + } } /** -- 2.34.1
next prev parent reply other threads:[~2024-03-25 6:53 UTC|newest] Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top 2024-03-25 6:40 [PATCH V2 00/19] timekeeping: Handle potential multiplication overflow Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 01/19] vdso: Consolidate vdso_calc_delta() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 02/19] vdso: Consolidate nanoseconds calculation Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 03/19] vdso: Add CONFIG_GENERIC_VDSO_OVERFLOW_PROTECT Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 04/19] math64: Tidy mul_u64_u32_shr() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] math64: Tidy up mul_u64_u32_shr() tip-bot2 for Adrian Hunter 2024-04-24 15:11 ` [PATCH V2 04/19] math64: Tidy mul_u64_u32_shr() Peter Zijlstra 2024-04-24 15:11 ` Peter Zijlstra 2024-03-25 6:40 ` [PATCH V2 05/19] vdso: math64: Provide mul_u64_u32_add_u64_shr() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] vdso, " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 06/19] vdso: Add vdso_data::max_cycles Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] vdso: Add vdso_data:: Max_cycles tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 07/19] vdso: Make delta calculation overflow safe Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 08/19] x86/vdso: " Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 09/19] timekeeping: Move timekeeping helper functions Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 10/19] timekeeping: Rename fast_tk_get_delta_ns() to __timekeeping_get_ns() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 11/19] timekeeping: Tidy timekeeping_cycles_to_ns() slightly Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 12/19] timekeeping: Reuse timekeeping_cycles_to_ns() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 13/19] timekeeping: Refactor timekeeping helpers Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 14/19] timekeeping: Consolidate " Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 15/19] timekeeping: Fold in timekeeping_delta_to_ns() Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 16/19] timekeeping: Prepare timekeeping_cycles_to_ns() for overflow safety Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter [this message] 2024-03-25 6:40 ` [PATCH V2 17/19] timekeeping: Make delta calculation overflow safe Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 18/19] timekeeping: Let timekeeping_cycles_to_ns() handle both under and overflow Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 6:40 ` [PATCH V2 19/19] clocksource: Make watchdog and suspend-timing multiplication overflow safe Adrian Hunter 2024-03-25 6:40 ` Adrian Hunter 2024-04-08 13:10 ` [tip: timers/core] " tip-bot2 for Adrian Hunter 2024-03-25 18:11 ` [PATCH V2 00/19] timekeeping: Handle potential multiplication overflow Arnd Bergmann
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20240325064023.2997-18-adrian.hunter@intel.com \ --to=adrian.hunter@intel.com \ --cc=agordeev@linux.ibm.com \ --cc=aneesh.kumar@kernel.org \ --cc=anna-maria@linutronix.de \ --cc=arnd@arndb.de \ --cc=bhelgaas@google.com \ --cc=borntraeger@linux.ibm.com \ --cc=bp@alien8.de \ --cc=dave.hansen@linux.intel.com \ --cc=gor@linux.ibm.com \ --cc=hca@linux.ibm.com \ --cc=hpa@zytor.com \ --cc=jstultz@google.com \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-s390@vger.kernel.org \ --cc=linuxppc-dev@lists.ozlabs.org \ --cc=luto@kernel.org \ --cc=mingo@redhat.com \ --cc=naveen.n.rao@linux.ibm.com \ --cc=npiggin@gmail.com \ --cc=peterz@infradead.org \ --cc=rdunlap@infradead.org \ --cc=sboyd@kernel.org \ --cc=svens@linux.ibm.com \ --cc=tglx@linutronix.de \ --cc=vincenzo.frascino@arm.com \ --cc=x86@kernel.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.