2019-03-06 15:31:24

by Hongbo Yao

[permalink] [raw]
Subject: [RFC PATCH 0/2] add ktime_sub_safe() to avoid undefined behaviour

When I ran Syzkaller testsuite, I got some UBSAN warnings with
ktime_sub().

Instead of putting overflow checks into each place, add a function
which does the sanity checking and convert all affected callers to use
it.

Hongbo Yao (2):
ktime: add ktime_sub_safe() to avoid undefined behaviour
hrtimer: Prevent overflow for relative refrences

include/linux/ktime.h | 8 ++++++++
kernel/time/hrtimer.c | 21 +++++++++++++++++++--
2 files changed, 27 insertions(+), 2 deletions(-)

--
2.20.1



2019-03-06 15:32:09

by Hongbo Yao

[permalink] [raw]
Subject: [RFC PATCH 2/2] hrtimer: Prevent overflow for relative refrences

I ran Syzkaller testsuite, and got the following call trace.

===============================================================
UBSAN: Undefined behaviour in ../kernel/time/hrtimer.c:514:11
signed integer overflow:
9223372036854775807 - -240652746 cannot be represented in type 'long
long int'
CPU: 1 PID: 9308 Comm: trinity-c5 Not tainted 4.19.25-dirty #4
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS
rel-1.12.0-0-ga698c8995f-prebuilt.qemu.org 04/01/2014
Call Trace:
<IRQ>
dump_stack+0xdd/0x12a
ubsan_epilogue+0x10/0x65
handle_overflow+0x1a8/0x212
? val_to_string.constprop.2+0x137/0x137
? print_lock_contention_bug+0x190/0x190
? __next_base+0x2b/0xc0
? __hrtimer_run_queues+0xca/0x830
__ubsan_handle_sub_overflow+0x11/0x19
__hrtimer_next_event_base+0x1a9/0x1b0
__hrtimer_get_next_event+0x96/0x140
hrtimer_interrupt+0x391/0x610
smp_apic_timer_interrupt+0x137/0x3d0
apic_timer_interrupt+0xf/0x20

===============================================================

Use ktime_sub_safe() which has the necessary sanity checks in place and
limits the result to the valid range.

Signed-off-by: Hongbo Yao <[email protected]>
---
kernel/time/hrtimer.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index cadc5bcbfc9e..2195b35af085 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -527,7 +527,8 @@ static ktime_t __hrtimer_next_event_base(struct hrtimer_cpu_base *cpu_base,

timer = container_of(next, struct hrtimer, node);
}
- expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
+ expires = ktime_sub_safe(hrtimer_get_expires(timer),
+ base->offset);
if (expires < expires_next) {
expires_next = expires;

@@ -781,7 +782,8 @@ static void hrtimer_reprogram(struct hrtimer *timer, bool reprogram)
{
struct hrtimer_cpu_base *cpu_base = this_cpu_ptr(&hrtimer_bases);
struct hrtimer_clock_base *base = timer->base;
- ktime_t expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
+ ktime_t expires = ktime_sub_safe(hrtimer_get_expires(timer),
+ base->offset);

WARN_ON_ONCE(hrtimer_get_expires_tv64(timer) < 0);

--
2.20.1


2019-03-06 16:56:12

by Hongbo Yao

[permalink] [raw]
Subject: [RFC PATCH 1/2] ktime: add ktime_sub_safe() to avoid undefined behaviour

This patch add a new ktime_sub_unsafe() helper which won't throw a
UBSAN warning when it does overflows, and then it add ktime_sub_safe()
which will check if the result of ktime_sub_unsafe overflows.This patch
modify the above functions to use ktime_sub_safe instead of ktime_sub();

Signed-off-by: Xiongfeng Wang <[email protected]>
Signed-off-by: Hongbo Yao <[email protected]>
---
include/linux/ktime.h | 8 ++++++++
kernel/time/hrtimer.c | 16 ++++++++++++++++
2 files changed, 24 insertions(+)

diff --git a/include/linux/ktime.h b/include/linux/ktime.h
index b2bb44f87f5a..325e794b0dd1 100644
--- a/include/linux/ktime.h
+++ b/include/linux/ktime.h
@@ -45,6 +45,12 @@ static inline ktime_t ktime_set(const s64 secs, const unsigned long nsecs)
/* Subtract two ktime_t variables. rem = lhs -rhs: */
#define ktime_sub(lhs, rhs) ((lhs) - (rhs))

+/*
+ * Same as ktime_sub(), but avoids undefined behaviour on overflow; however,
+ * this means that you must check the result for overflow yourself.
+ */
+#define ktime_sub_unsafe(lhs, rhs) ((u64) (lhs) - (rhs))
+
/* Add two ktime_t variables. res = lhs + rhs: */
#define ktime_add(lhs, rhs) ((lhs) + (rhs))

@@ -215,6 +221,8 @@ static inline ktime_t ktime_sub_ms(const ktime_t kt, const u64 msec)

extern ktime_t ktime_add_safe(const ktime_t lhs, const ktime_t rhs);

+extern ktime_t ktime_sub_safe(const ktime_t lhs, const ktime_t rhs);
+
/**
* ktime_to_timespec_cond - convert a ktime_t variable to timespec
* format only if the variable contains data
diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index e1a549c9e399..cadc5bcbfc9e 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -317,6 +317,22 @@ s64 __ktime_divns(const ktime_t kt, s64 div)
EXPORT_SYMBOL_GPL(__ktime_divns);
#endif /* BITS_PER_LONG >= 64 */

+/*
+ * sub two ktime values and do a safety check for overflow:
+ */
+ktime_t ktime_sub_safe(const ktime_t lhs, const ktime_t rhs)
+{
+ ktime_t res = ktime_sub_unsafe(lhs, rhs);
+
+ if (lhs > 0 && rhs < 0 && res < 0)
+ res = ktime_set(KTIME_SEC_MAX, 0);
+ else if (lhs < 0 && rhs > 0 && res > 0)
+ res = ktime_set(-KTIME_SEC_MAX, 0);
+
+ return res;
+}
+EXPORT_SYMBOL_GPL(ktime_sub_safe);
+
/*
* Add two ktime values and do a safety check for overflow:
*/
--
2.20.1