Skip to contentSkip to conversation

ktime: Fix ktime_divns to do signed division

RFC PATCH Superseded John Stultz 2 participants 3 messages May 6, 2015 High-resolution timers, timer wheel, clockevents

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

RFC PATCH v2 1/1 ktime: Fix ktime_divns to do signed division

It was noted that the 32bit implementation of ktime_divns() was doing unsigned division and didn't properly handle negative values.

This patch fixes the problem by checking and preserving the sign bit, and then reapplying it if appropriate after the division, it also changes the return type to a s64 to make it more obvious this is expected.

Nicolas also pointed out that negative dividers would cause infinite loops on 32bit systems, negative dividers is unlikely for users of this function, but out of caution this patch adds BUG_ON checks for negative dividers in both the 32 and 64bit versions to make sure no such use cases creep in.

Cc Nicolas Pitre <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Josh Boyer <[email protected]>
Cc One Thousand Gnomes <[email protected]>
Cc Trevor Cordes <[email protected]>
---
 include/linux/ktime.h | 27 +++++++++++++++++++++++----
 kernel/time/hrtimer.c | 11 ++++++++---
 2 files changed, 31 insertions(+), 7 deletions(-)
include/linux/ktime.h +23 -4
index 5fc3d10..ac9359e 100644
@@ -166,19 +166,38 @@ static inline bool ktime_before(const ktime_t cmp1, const ktime_t cmp2)
 }
 
 #if BITS_PER_LONG < 64
-extern u64 __ktime_divns(const ktime_t kt, s64 div);
-static inline u64 ktime_divns(const ktime_t kt, s64 div)
+extern s64 __ktime_divns(const ktime_t kt, s64 div);
+static inline s64 ktime_divns(const ktime_t kt, s64 div)
 {
+	/*
+	 * Negative divisors could cause an inf loop,
+	 * so bug out here.
+	 */
+	BUG_ON(div < 0);
 	if (__builtin_constant_p(div) && !(div >> 32)) {
-		u64 ns = kt.tv64;
+		s64 ns = kt.tv64;
+		int neg = (ns < 0);
+
+		if (neg)
+			ns = -ns;
 		do_div(ns, div);
+		if (neg)
+			ns = -ns;
 		return ns;
 	} else {
 		return __ktime_divns(kt, div);
 	}
 }
 #else /* BITS_PER_LONG < 64 */
-# define ktime_divns(kt, div)		(u64)((kt).tv64 / (div))
+static inline s64 ktime_divns(const ktime_t kt, s64 div)
+{
+	/*
+	 * 32-bit implementation cannot handle negative divisors,
+	 * so catch them on 64bit as well.
+	 */
+	BUG_ON(div < 0);
+	return (u64)((kt).tv64 / (div))
+}
 #endif
 
 static inline s64 ktime_to_us(const ktime_t kt)
kernel/time/hrtimer.c +8 -3
index 76d4bd9..c98ce4d 100644
@@ -266,12 +266,15 @@ lock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
 /*
  * Divide a ktime value by a nanosecond value
  */
-u64 __ktime_divns(const ktime_t kt, s64 div)
+s64 __ktime_divns(const ktime_t kt, s64 div)
 {
-	u64 dclc;
-	int sft = 0;
+	s64 dclc;
+	int neg, sft = 0;
 
 	dclc = ktime_to_ns(kt);
+	neg = (dclc < 0);
+	if (neg)
+		dclc = -dclc;
 	/* Make sure the divisor is less than 2^32: */
 	while (div >> 32) {
 		sft++;
@@ -279,6 +282,8 @@ u64 __ktime_divns(const ktime_t kt, s64 div)
 	}
 	dclc >>= sft;
 	do_div(dclc, (unsigned long) div);
+	if (neg)
+		dclc = -dclc;
 
 	return dclc;
 }
Signature · 1 line
1.9.1
#1 lore raw
Quoted 9 lines · John Stultz

It was noted that the 32bit implementation of ktime_divns() was doing unsigned division and didn't properly handle negative values.

This patch fixes the problem by checking and preserving the sign bit, and then reapplying it if appropriate after the division, it also changes the return type to a s64 to make it more obvious this is expected.

[...]

include/linux/ktime.h static inline bool ktime_before(const ktime_t cmp1, const ktime_t cmp2) · line 199

Quoted 10 lines
include/linux/ktime.h +8 -1
-# define ktime_divns(kt, div)          (u64)((kt).tv64 / (div))
+static inline s64 ktime_divns(const ktime_t kt, s64 div)
+{
+	/*
+	 * 32-bit implementation cannot handle negative divisors,
+	 * so catch them on 64bit as well.
+	 */
+	BUG_ON(div < 0);
+	return (u64)((kt).tv64 / (div))

You forgot to remove the u64 cast?

Is there a reason why it was there originally?

Nicolas

#2 lore raw
Quoted 13 lines · Nicolas Pitre
Quoted 9 lines · John Stultz

It was noted that the 32bit implementation of ktime_divns() was doing unsigned division and didn't properly handle negative values.

This patch fixes the problem by checking and preserving the sign bit, and then reapplying it if appropriate after the division, it also changes the return type to a s64 to make it more obvious this is expected.

[...]

Quoted 1 line
Quoted 11 lines

include/linux/ktime.h static inline bool ktime_before(const ktime_t cmp1, const ktime_t cmp2) · line 199

Quoted 9 lines
include/linux/ktime.h +8 -1
-# define ktime_divns(kt, div)          (u64)((kt).tv64 / (div))
+static inline s64 ktime_divns(const ktime_t kt, s64 div)
+{
+     /*
+      * 32-bit implementation cannot handle negative divisors,
+      * so catch them on 64bit as well.
+      */
+     BUG_ON(div < 0);
+     return (u64)((kt).tv64 / (div))

You forgot to remove the u64 cast?

Thanks for catching that!

Quoted 1 line

Is there a reason why it was there originally?

I assume because nanoseconds are usually though of as unsigned. It was introduced way back in the original hrtimer core code:
c0a3132963db68f1fbbd0e316b73de100fee3f08

thanks
-john