Skip to content

timekeeping: Handle potential multiplication overflow

Adrian Hunter linux-s390 linuxppc-dev lkml 2 versions – Applied

Status from this message: The following commit has been merged into the timers/core branch of tip:

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v2 Latest19 patches 2 repliesApplied
  2. v119 patches 2 repliesSuperseded

Changes in v2 from the cover letter

vdso: Consolidate vdso_calc_delta()
Keep powerpc comment about mask
Move ifdef out of function
vdso: Consolidate nanoseconds calculation
Adjusted due to changes in "vdso: Consolidate vdso_calc_delta()"

Patches in v2 Applied

#Subject and filesSizeRepliesApplied
1/19vdso: Consolidate vdso_calc_delta()arch/powerpc/include/asm/vdso/gettimeofday.h arch/s390/include/asm/vdso/gettimeofday.h lib/vdso/gettimeofday.c+21 -210 replies
2/19vdso: Consolidate nanoseconds calculationarch/x86/include/asm/vdso/gettimeofday.h lib/vdso/gettimeofday.c+28 -340 replies
3/19vdso: Add CONFIG_GENERIC_VDSO_OVERFLOW_PROTECTlib/vdso/Kconfig+7 -00 replies
4/19math64: Tidy mul_u64_u32_shr()include/linux/math64.h+1 -51 reply
5/19vdso: math64: Provide mul_u64_u32_add_u64_shr()include/linux/math64.h include/vdso/math64.h+39 -10 replies
6/19vdso: Add vdso_data::max_cyclesinclude/vdso/datapage.h kernel/time/vsyscall.c+10 -00 replies
7/19vdso: Make delta calculation overflow safelib/vdso/gettimeofday.c+16 -10 replies
8/19x86/vdso: Make delta calculation overflow safearch/x86/Kconfig arch/x86/include/asm/vdso/gettimeofday.h+22 -80 replies
9/19timekeeping: Move timekeeping helper functionskernel/time/timekeeping.c+17 -170 replies
10/19timekeeping: Rename fast_tk_get_delta_ns() to __timekeeping_get_ns()kernel/time/timekeeping.c+3 -30 replies
11/19timekeeping: Tidy timekeeping_cycles_to_ns() slightlykernel/time/timekeeping.c+2 -30 replies
12/19timekeeping: Reuse timekeeping_cycles_to_ns()kernel/time/timekeeping.c+1 -40 replies
13/19timekeeping: Refactor timekeeping helperskernel/time/timekeeping.c+6 -140 replies
14/19timekeeping: Consolidate timekeeping helperskernel/time/timekeeping.c+8 -60 replies
15/19timekeeping: Fold in timekeeping_delta_to_ns()kernel/time/timekeeping.c+1 -120 replies
16/19timekeeping: Prepare timekeeping_cycles_to_ns() for overflow safetykernel/time/timekeeping.c+11 -10 replies
17/19timekeeping: Make delta calculation overflow safekernel/time/timekeeping.c+29 -110 replies
18/19timekeeping: Let timekeeping_cycles_to_ns() handle both under and overflowkernel/time/timekeeping.c+13 -180 replies
19/19clocksource: Make watchdog and suspend-timing multiplication overflow safekernel/time/clocksource.c+20 -220 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.

Read the v2 thread

Cover letter [PATCH V2 00/19] timekeeping: Handle potential multiplication overflow

Hi

Kernel timekeeping calculates a clock value by keeping a base value and adding the number of nanoseconds since that time. Those nanoseconds are calculated from the clocksource delta. Then periodically, the base value is moved forwards (refer timekeeping_advance()) which is done by the local timer interrupt handler. It is designed such that there will always be a timer interrupt before the delta becomes big enough to overflow the 64-bit multiplication used in the conversion of delta to nanoseconds (refer timekeeping_delta_to_ns()). Obviously if timer interrupts are stopped, then the multiplication does eventually overflow.

Timekeeping multiplication overflow results in a "time loop", typically cycling about every 15 minutes with x86 TSC, for example starting at 10:00:

10:00, 10:01, 10:02 ... 10:15, 10:00, 10:01, ... 10:15, 10:00, 10:01 ...

Because a VMM can deliberately stop timer interrupts for a guest, a virtual machine can be exposed to this issue.

TDX maintains a monotonically increasing virtual TSC for a TDX guest, so the overflow is allowing a backwards movement of timekeeping that would not happen otherwise.

It is considered this could break security of cryptographic protocols that rely on the timestamps for freshness / replay protection, and consequently the kernel should prevent such a time loop.

Handle multiplication overflows by falling back to higher precision calculation when the possibility of an overflow is detected.

Extend the facility also to VDSO, dependent on new config option GENERIC_VDSO_OVERFLOW_PROTECT which is selected by x86 only, so other architectures are not affected. The result is a calculation that has similar performance as before. Most machines showed performance benefit, except Skylake-based hardware such as Intel Kaby Lake which was seen <1% worse.

Changes in V2:
vdso: Consolidate vdso_calc_delta()
Keep powerpc comment about mask
Move ifdef out of function
vdso: Consolidate nanoseconds calculation
Adjusted due to changes in "vdso: Consolidate vdso_calc_delta()"

Adrian Hunter (19):
vdso: Consolidate vdso_calc_delta()
vdso: Consolidate nanoseconds calculation
vdso: Add CONFIG_GENERIC_VDSO_OVERFLOW_PROTECT
math64: Tidy mul_u64_u32_shr()
vdso: math64: Provide mul_u64_u32_add_u64_shr()
vdso: Add vdso_data::max_cycles
vdso: Make delta calculation overflow safe
x86/vdso: Make delta calculation overflow safe
timekeeping: Move timekeeping helper functions
timekeeping: Rename fast_tk_get_delta_ns() to __timekeeping_get_ns()
timekeeping: Tidy timekeeping_cycles_to_ns() slightly
timekeeping: Reuse timekeeping_cycles_to_ns()
timekeeping: Refactor timekeeping helpers
timekeeping: Consolidate timekeeping helpers
timekeeping: Fold in timekeeping_delta_to_ns()
timekeeping: Prepare timekeeping_cycles_to_ns() for overflow safety
timekeeping: Make delta calculation overflow safe
timekeeping: Let timekeeping_cycles_to_ns() handle both under and overflow
clocksource: Make watchdog and suspend-timing multiplication overflow safe

 arch/powerpc/include/asm/vdso/gettimeofday.h |  26 +++----
 arch/s390/include/asm/vdso/gettimeofday.h    |   7 +-
 arch/x86/Kconfig                             |   1 +
 arch/x86/include/asm/vdso/gettimeofday.h     |  42 +++++++----
 include/linux/math64.h                       |   8 +-
 include/vdso/datapage.h                      |   4 +
 include/vdso/math64.h                        |  38 ++++++++++
 kernel/time/clocksource.c                    |  42 +++++------
 kernel/time/timekeeping.c                    | 106 ++++++++++++++-------------
 kernel/time/vsyscall.c                       |   6 ++
 lib/vdso/Kconfig                             |   7 ++
 lib/vdso/gettimeofday.c                      |  55 +++++++++-----
 12 files changed, 208 insertions(+), 134 deletions(-)

Regards
Adrian