ktime: Fix ktime_divns to do signed division

Message ID 1430520085-24535-1-git-send-email-john.stultz@linaro.org
State New
Headers show

Commit Message

John Stultz May 1, 2015, 10:41 p.m.
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 <nicolas.pitre@linaro.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Josh Boyer <jwboyer@redhat.com>
Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
Reported-by: Trevor Cordes <trevor@tecnopolis.ca>
Signed-off-by: John Stultz <john.stultz@linaro.org>
---
 include/linux/ktime.h | 12 ++++++++++--
 kernel/time/hrtimer.c | 11 +++++++++--
 2 files changed, 19 insertions(+), 4 deletions(-)

Comments

John Stultz May 1, 2015, 10:43 p.m. | #1
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

On Fri, May 1, 2015 at 3:41 PM, John Stultz <john.stultz@linaro.org> 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.
>
> 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 <nicolas.pitre@linaro.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Josh Boyer <jwboyer@redhat.com>
> Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
> Reported-by: Trevor Cordes <trevor@tecnopolis.ca>
> Signed-off-by: John Stultz <john.stultz@linaro.org>
> ---
>  include/linux/ktime.h | 12 ++++++++++--
>  kernel/time/hrtimer.c | 11 +++++++++--
>  2 files changed, 19 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index 5fc3d10..d947263 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -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);
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index 76d4bd9..4c1b294 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -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
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Nicolas Pitre May 1, 2015, 11:54 p.m. | #2
On Fri, 1 May 2015, 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.
> 
> 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.

> 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.

> Cc: Nicolas Pitre <nicolas.pitre@linaro.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Josh Boyer <jwboyer@redhat.com>
> Cc: One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>
> Reported-by: Trevor Cordes <trevor@tecnopolis.ca>
> Signed-off-by: John Stultz <john.stultz@linaro.org>
> ---
>  include/linux/ktime.h | 12 ++++++++++--
>  kernel/time/hrtimer.c | 11 +++++++++--
>  2 files changed, 19 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/ktime.h b/include/linux/ktime.h
> index 5fc3d10..d947263 100644
> --- a/include/linux/ktime.h
> +++ b/include/linux/ktime.h
> @@ -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);
> diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
> index 76d4bd9..4c1b294 100644
> --- a/kernel/time/hrtimer.c
> +++ b/kernel/time/hrtimer.c
> @@ -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
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
John Stultz May 2, 2015, midnight | #3
On Fri, May 1, 2015 at 4:54 PM, Nicolas Pitre <nicolas.pitre@linaro.org> wrote:
> On Fri, 1 May 2015, 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.
>>
>> 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.

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.


>> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Nicolas Pitre May 2, 2015, 12:14 a.m. | #4
On Fri, 1 May 2015, John Stultz wrote:

>  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;
> +		}

Minor comment: you could save some realestate with:

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

		if (neg)
			ns = -ns;


Nicolas
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Patch hide | download patch | download mbox

diff --git a/include/linux/ktime.h b/include/linux/ktime.h
index 5fc3d10..d947263 100644
--- a/include/linux/ktime.h
+++ b/include/linux/ktime.h
@@ -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);
diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 76d4bd9..4c1b294 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -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;
 }