* Re: [PATCH v3] ktime: Fix ktime_divns to do signed division
2015-05-08 20:47 [PATCH v3] ktime: Fix ktime_divns to do signed division John Stultz
@ 2015-05-08 21:18 ` Nicolas Pitre
2015-05-11 16:41 ` Trevor Cordes
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Nicolas Pitre @ 2015-05-08 21:18 UTC (permalink / raw)
To: John Stultz
Cc: lkml, Thomas Gleixner, Ingo Molnar, Josh Boyer,
One Thousand Gnomes, Trevor Cordes, stable
On Fri, 8 May 2015, John Stultz wrote:
> It was noted that the 32bit implementation of ktime_divns()
> was doing unsigned division and didn't properly handle
> negative values.
>
> And when a ktime helper was changed to utilize
> ktime_divns, it caused a regression on some IR blasters.
> See the following bugzilla for details:
> https://bugzilla.redhat.com/show_bug.cgi?id=1200353
>
> This patch fixes the problem in ktime_divns 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 checks for negative dividers for both
> 32-bit (BUG_ON) and 64-bit(WARN_ON) versions to make sure
> no such use cases creep in.
>
> Cc: Nicolas Pitre <nicolas.pitre@linaro.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Josh Boyer <jwboyer@redhat.com>
> Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
> Cc: Trevor Cordes <trevor@tecnopolis.ca>
> Cc: <stable@vger.kernel.org> # 3.17+ for regression
> Tested-by: Trevor Cordes <trevor@tecnopolis.ca>
> Reported-by: Trevor Cordes <trevor@tecnopolis.ca>
> Signed-off-by: John Stultz <john.stultz@linaro.org>
Acked-by: Nicolas Pitre <nico@linaro.org>
> ---
>
> New in v3:
> * Fix casting issue Nicolas pointed out
> * Use WARN_ON for 64bit case
>
> include/linux/ktime.h | 27 +++++++++++++++++++++++----
> kernel/time/hrtimer.c | 11 ++++++++---
> 2 files changed, 31 insertions(+), 7 deletions(-)
>
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index 5fc3d10..ab2de1c7 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -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.
> + */
> + WARN_ON(div < 0);
> + return kt.tv64 / div;
> +}
> #endif
>
> static inline s64 ktime_to_us(const ktime_t kt)
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index 76d4bd9..c98ce4d 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -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;
> }
> --
> 1.9.1
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v3] ktime: Fix ktime_divns to do signed division
2015-05-08 20:47 [PATCH v3] ktime: Fix ktime_divns to do signed division John Stultz
2015-05-08 21:18 ` Nicolas Pitre
@ 2015-05-11 16:41 ` Trevor Cordes
2015-05-12 14:14 ` Thomas Gleixner
2015-05-13 8:21 ` [tip:timers/urgent] " tip-bot for John Stultz
3 siblings, 0 replies; 6+ messages in thread
From: Trevor Cordes @ 2015-05-11 16:41 UTC (permalink / raw)
To: John Stultz
Cc: lkml, Nicolas Pitre, Thomas Gleixner, Ingo Molnar, Josh Boyer,
One Thousand Gnomes, stable
On 2015-05-08 John Stultz wrote:
> It was noted that the 32bit implementation of ktime_divns()
> was doing unsigned division and didn't properly handle
> negative values.
[...]
I have compiled, installed and tested (all weekend) the v3 of the patch
against 3.19.5-201.fc21.i686+PAE and it seems to work fine / stable,
and fixes my bug. I think it's a done deal! Thanks once again!
> Cc: Nicolas Pitre <nicolas.pitre@linaro.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Josh Boyer <jwboyer@redhat.com>
> Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
> Cc: Trevor Cordes <trevor@tecnopolis.ca>
> Cc: <stable@vger.kernel.org> # 3.17+ for regression
> Tested-by: Trevor Cordes <trevor@tecnopolis.ca>
> Reported-by: Trevor Cordes <trevor@tecnopolis.ca>
Tested-by: Trevor Cordes <trevor@tecnopolis.ca> [runtime test i686-PAE]
> Signed-off-by: John Stultz <john.stultz@linaro.org>
> ---
>
> New in v3:
> * Fix casting issue Nicolas pointed out
> * Use WARN_ON for 64bit case
>
> include/linux/ktime.h | 27 +++++++++++++++++++++++----
> kernel/time/hrtimer.c | 11 ++++++++---
> 2 files changed, 31 insertions(+), 7 deletions(-)
>
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index 5fc3d10..ab2de1c7 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -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.
> + */
> + WARN_ON(div < 0);
> + return kt.tv64 / div;
> +}
> #endif
>
> static inline s64 ktime_to_us(const ktime_t kt)
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index 76d4bd9..c98ce4d 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -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;
> }
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v3] ktime: Fix ktime_divns to do signed division
2015-05-08 20:47 [PATCH v3] ktime: Fix ktime_divns to do signed division John Stultz
2015-05-08 21:18 ` Nicolas Pitre
2015-05-11 16:41 ` Trevor Cordes
@ 2015-05-12 14:14 ` Thomas Gleixner
2015-05-12 15:14 ` John Stultz
2015-05-13 8:21 ` [tip:timers/urgent] " tip-bot for John Stultz
3 siblings, 1 reply; 6+ messages in thread
From: Thomas Gleixner @ 2015-05-12 14:14 UTC (permalink / raw)
To: John Stultz
Cc: lkml, Nicolas Pitre, Ingo Molnar, Josh Boyer, One Thousand Gnomes,
Trevor Cordes, stable
On Fri, 8 May 2015, John Stultz wrote:
> +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);
This triggers the typecheck for u64 in do_div(). The delta patch below
should do the trick.
Thanks,
tglx
diff --git a/include/linux/ktime.h b/include/linux/ktime.h
index ab2de1c7932c..b9620ebe356f 100644
--- a/include/linux/ktime.h
+++ b/include/linux/ktime.h
@@ -177,13 +177,13 @@ static inline s64 ktime_divns(const ktime_t kt, s64 div)
if (__builtin_constant_p(div) && !(div >> 32)) {
s64 ns = kt.tv64;
int neg = (ns < 0);
+ u64 tmp;
if (neg)
ns = -ns;
- do_div(ns, div);
- if (neg)
- ns = -ns;
- return ns;
+ tmp = ns;
+ do_div(tmp, div);
+ return neg ? -tmp : tmp;
} else {
return __ktime_divns(kt, div);
}
diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index c98ce4d9f613..bac65f810afd 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -268,8 +268,9 @@ lock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
*/
s64 __ktime_divns(const ktime_t kt, s64 div)
{
- s64 dclc;
int neg, sft = 0;
+ s64 dclc;
+ u64 tmp;
dclc = ktime_to_ns(kt);
neg = (dclc < 0);
@@ -280,12 +281,9 @@ s64 __ktime_divns(const ktime_t kt, s64 div)
sft++;
div >>= 1;
}
- dclc >>= sft;
- do_div(dclc, (unsigned long) div);
- if (neg)
- dclc = -dclc;
-
- return dclc;
+ tmp = dclc >> sft;
+ do_div(tmp, (unsigned long) div);
+ return neg ? -tmp : tmp;
}
EXPORT_SYMBOL_GPL(__ktime_divns);
#endif /* BITS_PER_LONG >= 64 */
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v3] ktime: Fix ktime_divns to do signed division
2015-05-12 14:14 ` Thomas Gleixner
@ 2015-05-12 15:14 ` John Stultz
0 siblings, 0 replies; 6+ messages in thread
From: John Stultz @ 2015-05-12 15:14 UTC (permalink / raw)
To: Thomas Gleixner
Cc: lkml, Nicolas Pitre, Ingo Molnar, Josh Boyer, One Thousand Gnomes,
Trevor Cordes, stable
On Tue, May 12, 2015 at 7:14 AM, Thomas Gleixner <tglx@linutronix.de> wrote:
> On Fri, 8 May 2015, John Stultz wrote:
>> +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);
>
> This triggers the typecheck for u64 in do_div(). The delta patch below
> should do the trick.
>
I started looking into this, and this landed in my inbox. Thanks Thomas! :)
I reproduced the issue w/ the kbuildbot instructions and the patch
below resolves it.
Acked-by: John Stultz <john.stultz@linaro.org>
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index ab2de1c7932c..b9620ebe356f 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -177,13 +177,13 @@ static inline s64 ktime_divns(const ktime_t kt, s64 div)
> if (__builtin_constant_p(div) && !(div >> 32)) {
> s64 ns = kt.tv64;
> int neg = (ns < 0);
> + u64 tmp;
>
> if (neg)
> ns = -ns;
> - do_div(ns, div);
> - if (neg)
> - ns = -ns;
> - return ns;
> + tmp = ns;
> + do_div(tmp, div);
> + return neg ? -tmp : tmp;
> } else {
> return __ktime_divns(kt, div);
> }
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index c98ce4d9f613..bac65f810afd 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -268,8 +268,9 @@ lock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags)
> */
> s64 __ktime_divns(const ktime_t kt, s64 div)
> {
> - s64 dclc;
> int neg, sft = 0;
> + s64 dclc;
> + u64 tmp;
>
> dclc = ktime_to_ns(kt);
> neg = (dclc < 0);
> @@ -280,12 +281,9 @@ s64 __ktime_divns(const ktime_t kt, s64 div)
> sft++;
> div >>= 1;
> }
> - dclc >>= sft;
> - do_div(dclc, (unsigned long) div);
> - if (neg)
> - dclc = -dclc;
> -
> - return dclc;
> + tmp = dclc >> sft;
> + do_div(tmp, (unsigned long) div);
> + return neg ? -tmp : tmp;
> }
> EXPORT_SYMBOL_GPL(__ktime_divns);
> #endif /* BITS_PER_LONG >= 64 */
^ permalink raw reply [flat|nested] 6+ messages in thread
* [tip:timers/urgent] ktime: Fix ktime_divns to do signed division
2015-05-08 20:47 [PATCH v3] ktime: Fix ktime_divns to do signed division John Stultz
` (2 preceding siblings ...)
2015-05-12 14:14 ` Thomas Gleixner
@ 2015-05-13 8:21 ` tip-bot for John Stultz
3 siblings, 0 replies; 6+ messages in thread
From: tip-bot for John Stultz @ 2015-05-13 8:21 UTC (permalink / raw)
To: linux-tip-commits
Cc: trevor, stable, gnomes, jwboyer, hpa, john.stultz, nicolas.pitre,
linux-kernel, tglx, mingo
Commit-ID: f7bcb70ebae0dcdb5a2d859b09e4465784d99029
Gitweb: http://git.kernel.org/tip/f7bcb70ebae0dcdb5a2d859b09e4465784d99029
Author: John Stultz <john.stultz@linaro.org>
AuthorDate: Fri, 8 May 2015 13:47:23 -0700
Committer: Thomas Gleixner <tglx@linutronix.de>
CommitDate: Wed, 13 May 2015 10:19:35 +0200
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.
And when a ktime helper was changed to utilize
ktime_divns, it caused a regression on some IR blasters.
See the following bugzilla for details:
https://bugzilla.redhat.com/show_bug.cgi?id=1200353
This patch fixes the problem in ktime_divns 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 checks for negative dividers for both
32-bit (BUG_ON) and 64-bit(WARN_ON) versions to make sure
no such use cases creep in.
[ tglx: Hand an u64 to do_div() to avoid the compiler warning ]
Fixes: 166afb64511e 'ktime: Sanitize ktime_to_us/ms conversion'
Reported-and-tested-by: Trevor Cordes <trevor@tecnopolis.ca>
Signed-off-by: John Stultz <john.stultz@linaro.org>
Acked-by: Nicolas Pitre <nicolas.pitre@linaro.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Josh Boyer <jwboyer@redhat.com>
Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
Cc: <stable@vger.kernel.org>
Link: http://lkml.kernel.org/r/1431118043-23452-1-git-send-email-john.stultz@linaro.org
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
include/linux/ktime.h | 27 +++++++++++++++++++++------
kernel/time/hrtimer.c | 14 ++++++++------
2 files changed, 29 insertions(+), 12 deletions(-)
diff --git a/include/linux/ktime.h b/include/linux/ktime.h
index 5fc3d10..2b6a204 100644
--- a/include/linux/ktime.h
+++ b/include/linux/ktime.h
@@ -166,19 +166,34 @@ 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;
- do_div(ns, div);
- return ns;
+ s64 ns = kt.tv64;
+ u64 tmp = ns < 0 ? -ns : ns;
+
+ do_div(tmp, div);
+ return ns < 0 ? -tmp : tmp;
} 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.
+ */
+ WARN_ON(div < 0);
+ return kt.tv64 / div;
+}
#endif
static inline s64 ktime_to_us(const ktime_t kt)
diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 76d4bd9..93ef7190 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -266,21 +266,23 @@ 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;
+ u64 tmp;
dclc = ktime_to_ns(kt);
+ tmp = dclc < 0 ? -dclc : dclc;
+
/* Make sure the divisor is less than 2^32: */
while (div >> 32) {
sft++;
div >>= 1;
}
- dclc >>= sft;
- do_div(dclc, (unsigned long) div);
-
- return dclc;
+ tmp >>= sft;
+ do_div(tmp, (unsigned long) div);
+ return dclc < 0 ? -tmp : tmp;
}
EXPORT_SYMBOL_GPL(__ktime_divns);
#endif /* BITS_PER_LONG >= 64 */
^ permalink raw reply related [flat|nested] 6+ messages in thread