Skip to contentSkip to conversation

ktime: Fix ktime_divns to do signed division

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

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

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

It was noted that the 32bit implementation of ktime_divns was doing unsgined division adn 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.

Unfortunately there is some duplication since we have the optimized version for constant 32bit divider. I was considering reworkign the __ktime_divns helper to simplify the sign-handling logic, but then it would likely just be a s64/s64 divide, and probably should be more generic.

Thoughts?

Nicolas also notes that the ktime_divns() function breaks if someone passes in a negative divisor as well. This patch doesn't yet address that issue.

Cc Nicolas Pitre <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Josh Boyer <[email protected]>
Cc One Thousand Gnomes <[email protected]>
---
 include/linux/ktime.h | 12 ++++++++++--
 kernel/time/hrtimer.c | 11 +++++++++--
 2 files changed, 19 insertions(+), 4 deletions(-)
include/linux/ktime.h +10 -2
index 5fc3d10..d947263 100644
@@ -166,12 +166,20 @@ 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);
+extern s64 __ktime_divns(const ktime_t kt, s64 div);
 static inline u64 ktime_divns(const ktime_t kt, s64 div)
 {
 	if (__builtin_constant_p(div) && !(div >> 32)) {
-		u64 ns = kt.tv64;
+		s64 ns = kt.tv64;
+		int neg = 0;
+
+		if (ns < 0) {
+			neg = 1;
+			ns = -ns;
+		}
 		do_div(ns, div);
+		if (neg)
+			ns = -ns;
 		return ns;
 	} else {
 		return __ktime_divns(kt, div);
kernel/time/hrtimer.c +9 -2
index 76d4bd9..4c1b294 100644
@@ -266,12 +266,17 @@ 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;
+	s64 dclc;
 	int sft = 0;
+	int neg = 0;
 
 	dclc = ktime_to_ns(kt);
+	if (dclc < 0) {
+		neg = 1;
+		dclc = -dclc;
+	}
 	/* Make sure the divisor is less than 2^32: */
 	while (div >> 32) {
 		sft++;
@@ -279,6 +284,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

Bah. I forgot to add [RFC] to the subject. This patch isn't yet ready for submission, I just wanted to get some initial feedback on it.

thanks
-john

Quoted 95 lines · John Stultz

It was noted that the 32bit implementation of ktime_divns was doing unsgined division adn 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.

Unfortunately there is some duplication since we have the optimized version for constant 32bit divider. I was considering reworkign the __ktime_divns helper to simplify the sign-handling logic, but then it would likely just be a s64/s64 divide, and probably should be more generic.

Thoughts?

Nicolas also notes that the ktime_divns() function breaks if someone passes in a negative divisor as well. This patch doesn't yet address that issue.

Cc Nicolas Pitre <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Josh Boyer <[email protected]>
Cc One Thousand Gnomes <[email protected]>
---
 include/linux/ktime.h | 12 ++++++++++--
 kernel/time/hrtimer.c | 11 +++++++++--
 2 files changed, 19 insertions(+), 4 deletions(-)
include/linux/ktime.h +10 -2
index 5fc3d10..d947263 100644
@@ -166,12 +166,20 @@ 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);
+extern s64 __ktime_divns(const ktime_t kt, s64 div);
 static inline u64 ktime_divns(const ktime_t kt, s64 div)
 {
        if (__builtin_constant_p(div) && !(div >> 32)) {
-               u64 ns = kt.tv64;
+               s64 ns = kt.tv64;
+               int neg = 0;
+
+               if (ns < 0) {
+                       neg = 1;
+                       ns = -ns;
+               }
                do_div(ns, div);
+               if (neg)
+                       ns = -ns;
                return ns;
        } else {
                return __ktime_divns(kt, div);
kernel/time/hrtimer.c +9 -3
index 76d4bd9..4c1b294 100644
@@ -266,12 +266,17 @@ 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;
+       s64 dclc;
        int sft = 0;
+       int neg = 0;
 
        dclc = ktime_to_ns(kt);
+       if (dclc < 0) {
+               neg = 1;
+               dclc = -dclc;
+       }
        /* Make sure the divisor is less than 2^32: */
        while (div >> 32) {
                sft++;
@@ -279,6 +284,8 @@ u64 __ktime_divns(const ktime_t kt, s64 div)
        }
        dclc >>= sft;
        do_div(dclc, (unsigned long) div);
+       if (neg)
+               dclc = -dclc;
 
        return dclc;
 }
--

1.9.1

#2 lore raw
In reply to John Stultz
Quoted 8 lines · John Stultz

It was noted that the 32bit implementation of ktime_divns was doing unsgined division adn 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.

Quoted 8 lines

Unfortunately there is some duplication since we have the optimized version for constant 32bit divider. I was considering reworkign the __ktime_divns helper to simplify the sign-handling logic, but then it would likely just be a s64/s64 divide, and probably should be more generic.

Thoughts?

Wouldn't it be better to simply forbid negative time altogether? Given it's been broken for quite a while, there must not be that many instances of such usage and fixing them would avoid the useless sign handling overhead to 99.9% of the cases.

Quoted 3 lines

Nicolas also notes that the ktime_divns() function breaks if someone passes in a negative divisor as well. This patch doesn't yet address that issue.

GRanted, a negative divisor here would be even weirder and should definitely be rejected. Maybe the infinite loop is a good thing in that case, probably better than producing wrong numbers.

Quoted 81 lines
Cc Nicolas Pitre <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Josh Boyer <[email protected]>
Cc One Thousand Gnomes <[email protected]>
---
 include/linux/ktime.h | 12 ++++++++++--
 kernel/time/hrtimer.c | 11 +++++++++--
 2 files changed, 19 insertions(+), 4 deletions(-)
include/linux/ktime.h +10 -2
index 5fc3d10..d947263 100644
@@ -166,12 +166,20 @@ 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);
+extern s64 __ktime_divns(const ktime_t kt, s64 div);
 static inline u64 ktime_divns(const ktime_t kt, s64 div)
 {
 	if (__builtin_constant_p(div) && !(div >> 32)) {
-		u64 ns = kt.tv64;
+		s64 ns = kt.tv64;
+		int neg = 0;
+
+		if (ns < 0) {
+			neg = 1;
+			ns = -ns;
+		}
 		do_div(ns, div);
+		if (neg)
+			ns = -ns;
 		return ns;
 	} else {
 		return __ktime_divns(kt, div);
kernel/time/hrtimer.c +9 -2
index 76d4bd9..4c1b294 100644
@@ -266,12 +266,17 @@ 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;
+	s64 dclc;
 	int sft = 0;
+	int neg = 0;
 
 	dclc = ktime_to_ns(kt);
+	if (dclc < 0) {
+		neg = 1;
+		dclc = -dclc;
+	}
 	/* Make sure the divisor is less than 2^32: */
 	while (div >> 32) {
 		sft++;
@@ -279,6 +284,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 · 7 lines
1.9.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
#3 lore raw
Quoted 17 lines · Nicolas Pitre
Quoted 15 lines · John Stultz

It was noted that the 32bit implementation of ktime_divns was doing unsgined division adn 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.

Unfortunately there is some duplication since we have the optimized version for constant 32bit divider. I was considering reworkign the __ktime_divns helper to simplify the sign-handling logic, but then it would likely just be a s64/s64 divide, and probably should be more generic.

Quoted 6 lines
Quoted 1 line

Thoughts?

Wouldn't it be better to simply forbid negative time altogether? Given it's been broken for quite a while, there must not be that many instances of such usage and fixing them would avoid the useless sign handling overhead to 99.9% of the cases.

Well, ktime is basically an s64 and timespecs can be negative as well. So I'm not sure its reasonable to disqualify negative time intervals from using this function. Especially since on 64bit systems, ktime_divns handles negative intervals just fine.

Quoted 7 lines
Quoted 3 lines

Nicolas also notes that the ktime_divns() function breaks if someone passes in a negative divisor as well. This patch doesn't yet address that issue.

GRanted, a negative divisor here would be even weirder and should definitely be rejected. Maybe the infinite loop is a good thing in that case, probably better than producing wrong numbers.

Yea. I'm thinking a WARN_ON or a BUG would be good to have in both 32bit and 64bit cases so we avoid folks testing on 64bit and thinking it works generally.

thanks
-john

#4 lore raw
In reply to John Stultz

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

Quoted 11 lines · John Stultz

static inline u64 ktime_divns(const ktime_t kt, s64 div) {

include/linux/ktime.h +7 -1
 	if (__builtin_constant_p(div) && !(div >> 32)) {
-		u64 ns = kt.tv64;
+		s64 ns = kt.tv64;
+		int neg = 0;
+
+		if (ns < 0) {
+			neg = 1;
+			ns = -ns;
+		}

Minor comment: you could save some realestate with:

		s64 ns = kt.tv64;
		bool neg = (ns < 0);

		if (neg)
			ns = -ns;

Nicolas

Tested-by on v1 1/1
#5 lore raw
In reply to John Stultz
Quoted 7 lines · On 2015-05-01 John Stultz wrote:

It was noted that the 32bit implementation of ktime_divns was doing unsgined division adn 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.

I worked your new patch into my test system into Fedora 21's latest 3.19.5-200.fc21 (they haven't switched to 4.0 yet). I had to add in Nicolas' 8b618628 commit as well to get this new patch to go into 3.19.5.

After rebuild and reboot I can confirm this patch fixes my bug: irsend doesn't hang lircd. I'll report if anything else weird goes on, but this all seems pretty straightforward so I doubt I'll have any problems.

Quoted 2 lines

I'll send it out here shortly. If you could give it a spin at your leisure, and if it works give me a Tested-by: tag I'd appreciate it!

I'm not quite sure how to give a Tested-by, but from the minimal docs I found on the net, I am trying below (after your Signed-off-by tag). If I need to do something else, please point me in the general direction of instructions.

Quoted 2 lines

Great work again on chasing this down, and thanks for helping with debugging and validating the fix!

Thanks! I'm really glad this is getting worked out and am happy to help. It's a big step forward for me to move past simple bugzilla onto kernel bisects. I plan on giving a presentation about all this at my local Linux user group. It'll be nice to report the happy ending! You guys have been great. I guess kernel bugzilla isn't the place to get
help: it's here on the LKML.

P.S. Here's the kernel bz link, we/I can close it with the results once this is all done:
https://bugzilla.kernel.org/show_bug.cgi?id=95431

Quoted 6 lines
Cc Nicolas Pitre <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Josh Boyer <[email protected]>
Cc One Thousand Gnomes <[email protected]>
Quoted 65 lines
---
 include/linux/ktime.h | 12 ++++++++++--
 kernel/time/hrtimer.c | 11 +++++++++--
 2 files changed, 19 insertions(+), 4 deletions(-)
include/linux/ktime.h +10 -2
index 5fc3d10..d947263 100644
@@ -166,12 +166,20 @@ 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);
+extern s64 __ktime_divns(const ktime_t kt, s64 div);
 static inline u64 ktime_divns(const ktime_t kt, s64 div)
 {
 	if (__builtin_constant_p(div) && !(div >> 32)) {
-		u64 ns = kt.tv64;
+		s64 ns = kt.tv64;
+		int neg = 0;
+
+		if (ns < 0) {
+			neg = 1;
+			ns = -ns;
+		}
 		do_div(ns, div);
+		if (neg)
+			ns = -ns;
 		return ns;
 	} else {
 		return __ktime_divns(kt, div);
kernel/time/hrtimer.c +0 -0
index 76d4bd9..4c1b294 100644
@@ -266,12 +266,17 @@ lock_hrtimer_base(const struct hrtimer *timer,

unsigned long *flags) /*
* Divide a ktime value by a nanosecond value
*/

kernel/time/hrtimer.c +9 -2
-u64 __ktime_divns(const ktime_t kt, s64 div)
+s64 __ktime_divns(const ktime_t kt, s64 div)
 {
-	u64 dclc;
+	s64 dclc;
 	int sft = 0;
+	int neg = 0;
 
 	dclc = ktime_to_ns(kt);
+	if (dclc < 0) {
+		neg = 1;
+		dclc = -dclc;
+	}
 	/* Make sure the divisor is less than 2^32: */
 	while (div >> 32) {
 		sft++;
@@ -279,6 +284,8 @@ u64 __ktime_divns(const ktime_t kt, s64 div)
 	}
 	dclc >>= sft;
 	do_div(dclc, (unsigned long) div);
+	if (neg)
+		dclc = -dclc;
 
 	return dclc;
 }