From 83dc78394f43f2ee0451af483a410c8cdb2088f0 Mon Sep 17 00:00:00 2001 From: cheloha Date: Sat, 23 Jul 2022 22:58:51 +0000 Subject: [PATCH] timecounting: use full 96-bit product when computing elapsed time The timecounting subsystem computes elapsed time by scaling (64 bits) the difference between two counter values (32 bits at most) up into a struct bintime (128 bits). Under normal circumstances it is sufficient to do this with 64-bit multiplication, like this: struct bintime bt; bt.sec = 0; bt.frac = th->tc_scale * tc_delta(th); However, if tc_delta() exceeds 1 second's worth of counter ticks, that multiplication overflows. The result is that the monotonic clock appears to jump backwards. When can this happen? In practice, I have seen it when trying to compile LLVM on an EdgeRouter Lite when using an SD card as the backing disk. The box gets stuck in swap, the hardclock(9) is delayed, and we appear to "lose time". To avoid this overflow we need to compute the full 96-bit product of the delta and the scale. This commit adds TIMECOUNT_TO_BINTIME(), a function for computing that full product, to sys/time.h. The patch puts the new function to use in lib/libc/sys/microtime.c and sys/kern/kern_tc.c. (The commit also reorganizes some of our high resolution bintime code so that we always read the timecounter first.) Doing the full 96-bit multiplication is between 0% and 15% slower than doing the cheaper 64-bit multiplication on amd64. Measuring a precise difference is extremely difficult because the computation is already quite fast. I would guess that the cost is slightly higher than that on 32-bit platforms. Nobody ever volunteered to test, so this remains a guess. Thread: https://marc.info/?l=openbsd-tech&m=163424607918042&w=2 6 month bump: https://marc.info/?l=openbsd-tech&m=165124251401342&w=2 Committed after 9 months without review. --- lib/libc/sys/microtime.c | 13 +++++++------ sys/kern/kern_tc.c | 16 +++++++++------- sys/sys/time.h | 13 ++++++++++++- 3 files changed, 28 insertions(+), 14 deletions(-) diff --git a/lib/libc/sys/microtime.c b/lib/libc/sys/microtime.c index e85a86a78de..9084e5813cf 100644 --- a/lib/libc/sys/microtime.c +++ b/lib/libc/sys/microtime.c @@ -1,4 +1,4 @@ -/* $OpenBSD: microtime.c,v 1.1 2020/07/06 13:33:06 pirofti Exp $ */ +/* $OpenBSD: microtime.c,v 1.2 2022/07/23 22:58:51 cheloha Exp $ */ /* * Copyright (c) 2000 Poul-Henning Kamp * Copyright (c) 2020 Paul Irofti @@ -45,10 +45,10 @@ binuptime(struct bintime *bt, struct timekeep *tk) do { gen = tk->tk_generation; membar_consumer(); - *bt = tk->tk_offset; if (tc_delta(tk, &delta)) return -1; - bintimeaddfrac(bt, tk->tk_scale * delta, bt); + TIMECOUNT_TO_BINTIME(delta, tk->tk_scale, bt); + bintimeadd(bt, &tk->tk_offset, bt); membar_consumer(); } while (gen == 0 || gen != tk->tk_generation); @@ -65,7 +65,8 @@ binruntime(struct bintime *bt, struct timekeep *tk) membar_consumer(); if (tc_delta(tk, &delta)) return -1; - bintimeaddfrac(&tk->tk_offset, tk->tk_scale * delta, bt); + TIMECOUNT_TO_BINTIME(delta, tk->tk_scale, bt); + bintimeadd(bt, &tk->tk_offset, bt); bintimesub(bt, &tk->tk_naptime, bt); membar_consumer(); } while (gen == 0 || gen != tk->tk_generation); @@ -81,10 +82,10 @@ bintime(struct bintime *bt, struct timekeep *tk) do { gen = tk->tk_generation; membar_consumer(); - *bt = tk->tk_offset; if (tc_delta(tk, &delta)) return -1; - bintimeaddfrac(bt, tk->tk_scale * delta, bt); + TIMECOUNT_TO_BINTIME(delta, tk->tk_scale, bt); + bintimeadd(bt, &tk->tk_offset, bt); bintimeadd(bt, &tk->tk_boottime, bt); membar_consumer(); } while (gen == 0 || gen != tk->tk_generation); diff --git a/sys/kern/kern_tc.c b/sys/kern/kern_tc.c index 3d35064ece1..58204d0ea9f 100644 --- a/sys/kern/kern_tc.c +++ b/sys/kern/kern_tc.c @@ -1,4 +1,4 @@ -/* $OpenBSD: kern_tc.c,v 1.75 2021/10/24 00:02:25 jsg Exp $ */ +/* $OpenBSD: kern_tc.c,v 1.76 2022/07/23 22:58:51 cheloha Exp $ */ /* * Copyright (c) 2000 Poul-Henning Kamp @@ -189,8 +189,8 @@ binuptime(struct bintime *bt) th = timehands; gen = th->th_generation; membar_consumer(); - *bt = th->th_offset; - bintimeaddfrac(bt, th->th_scale * tc_delta(th), bt); + TIMECOUNT_TO_BINTIME(tc_delta(th), th->th_scale, bt); + bintimeadd(bt, &th->th_offset, bt); membar_consumer(); } while (gen == 0 || gen != th->th_generation); } @@ -278,7 +278,8 @@ binruntime(struct bintime *bt) th = timehands; gen = th->th_generation; membar_consumer(); - bintimeaddfrac(&th->th_offset, th->th_scale * tc_delta(th), bt); + TIMECOUNT_TO_BINTIME(tc_delta(th), th->th_scale, bt); + bintimeadd(bt, &th->th_offset, bt); bintimesub(bt, &th->th_naptime, bt); membar_consumer(); } while (gen == 0 || gen != th->th_generation); @@ -303,8 +304,8 @@ bintime(struct bintime *bt) th = timehands; gen = th->th_generation; membar_consumer(); - *bt = th->th_offset; - bintimeaddfrac(bt, th->th_scale * tc_delta(th), bt); + TIMECOUNT_TO_BINTIME(tc_delta(th), th->th_scale, bt); + bintimeadd(bt, &th->th_offset, bt); bintimeadd(bt, &th->th_boottime, bt); membar_consumer(); } while (gen == 0 || gen != th->th_generation); @@ -641,7 +642,8 @@ tc_windup(struct bintime *new_boottime, struct bintime *new_offset, ncount = 0; th->th_offset_count += delta; th->th_offset_count &= th->th_counter->tc_counter_mask; - bintimeaddfrac(&th->th_offset, th->th_scale * delta, &th->th_offset); + TIMECOUNT_TO_BINTIME(delta, th->th_scale, &bt); + bintimeadd(&th->th_offset, &bt, &th->th_offset); /* * Ignore new offsets that predate the current offset. diff --git a/sys/sys/time.h b/sys/sys/time.h index ac0eb2f35f7..d4736c97cb6 100644 --- a/sys/sys/time.h +++ b/sys/sys/time.h @@ -1,4 +1,4 @@ -/* $OpenBSD: time.h,v 1.61 2021/06/19 13:49:39 cheloha Exp $ */ +/* $OpenBSD: time.h,v 1.62 2022/07/23 22:58:51 cheloha Exp $ */ /* $NetBSD: time.h,v 1.18 1996/04/23 10:29:33 mycroft Exp $ */ /* @@ -208,6 +208,17 @@ bintimesub(const struct bintime *bt, const struct bintime *ct, dt->frac = bt->frac - ct->frac; } +static inline void +TIMECOUNT_TO_BINTIME(u_int count, uint64_t scale, struct bintime *bt) +{ + uint64_t hi64; + + hi64 = count * (scale >> 32); + bt->sec = hi64 >> 32; + bt->frac = hi64 << 32; + bintimeaddfrac(bt, count * (scale & 0xffffffff), bt); +} + /*- * Background information: * -- 2.20.1