[PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[Chris Metcalf]

This bugfix was originally made in commit 35a4933a8959 ("time:
Avoid signed overflow in timekeeping_get_ns()").  When the code was
refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
translation") the signed overflow fix was lost.  Re-introduce it.

Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
---
I happened to be looking for an unrelated fix, found this code,
realized the tip code didn't match the fixed code, and
backtracked to where it had gone away.

 kernel/time/timekeeping.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index 37dec7e3db43..57926bc7b7f3 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
 {
 	s64 nsec;
 
-	nsec = delta * tkr->mult + tkr->xtime_nsec;
-	nsec >>= tkr->shift;
+	nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
 
 	/* If arch requires, add in get_arch_timeoffset() */
 	return nsec + arch_gettimeoffset();
-- 
2.7.2

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[John Stultz]

On Mon, Nov 14, 2016 at 11:42 AM, Chris Metcalf <cmetcalf@mellanox.com> wrote:
> This bugfix was originally made in commit 35a4933a8959 ("time:
> Avoid signed overflow in timekeeping_get_ns()").  When the code was
> refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
> translation") the signed overflow fix was lost.  Re-introduce it.
>
> Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
> ---
> I happened to be looking for an unrelated fix, found this code,
> realized the tip code didn't match the fixed code, and
> backtracked to where it had gone away.
>
>  kernel/time/timekeeping.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> index 37dec7e3db43..57926bc7b7f3 100644
> --- a/kernel/time/timekeeping.c
> +++ b/kernel/time/timekeeping.c
> @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
>  {
>         s64 nsec;
>
> -       nsec = delta * tkr->mult + tkr->xtime_nsec;
> -       nsec >>= tkr->shift;
> +       nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;

Ugh.

So... I think this proves the original fix was *far* too subtle to
maintain. So I think reintroducing it as-is doesn't protect us from
undoing it.  If the problem is really using the signed intermediate
nsec value, we should get rid of that.

thanks
-john

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 1473 bytes --]

On Mon, Nov 14, 2016 at 02:42:49PM -0500, Chris Metcalf wrote:
> This bugfix was originally made in commit 35a4933a8959 ("time:
> Avoid signed overflow in timekeeping_get_ns()").  When the code was
> refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
> translation") the signed overflow fix was lost.  Re-introduce it.
> 
> Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>

Reviewed-by: David Gibson <david@gibson.dropbear.id.au>

> ---
> I happened to be looking for an unrelated fix, found this code,
> realized the tip code didn't match the fixed code, and
> backtracked to where it had gone away.
> 
>  kernel/time/timekeeping.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> index 37dec7e3db43..57926bc7b7f3 100644
> --- a/kernel/time/timekeeping.c
> +++ b/kernel/time/timekeeping.c
> @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
>  {
>  	s64 nsec;
>  
> -	nsec = delta * tkr->mult + tkr->xtime_nsec;
> -	nsec >>= tkr->shift;
> +	nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
>  
>  	/* If arch requires, add in get_arch_timeoffset() */
>  	return nsec + arch_gettimeoffset();

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[Laurent Vivier]

On 14/11/2016 20:42, Chris Metcalf wrote:
> This bugfix was originally made in commit 35a4933a8959 ("time:
> Avoid signed overflow in timekeeping_get_ns()").  When the code was
> refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
> translation") the signed overflow fix was lost.  Re-introduce it.
> 
> Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
> ---
> I happened to be looking for an unrelated fix, found this code,
> realized the tip code didn't match the fixed code, and
> backtracked to where it had gone away.
> 
>  kernel/time/timekeeping.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> index 37dec7e3db43..57926bc7b7f3 100644
> --- a/kernel/time/timekeeping.c
> +++ b/kernel/time/timekeeping.c
> @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
>  {
>  	s64 nsec;
>  
> -	nsec = delta * tkr->mult + tkr->xtime_nsec;
> -	nsec >>= tkr->shift;
> +	nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
>  
>  	/* If arch requires, add in get_arch_timeoffset() */
>  	return nsec + arch_gettimeoffset();
> 
Reviewed-by: Laurent Vivier <lvivier@redhat.com>

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[Thomas Gleixner]

On Mon, 14 Nov 2016, John Stultz wrote:

> On Mon, Nov 14, 2016 at 11:42 AM, Chris Metcalf <cmetcalf@mellanox.com> wrote:
> > This bugfix was originally made in commit 35a4933a8959 ("time:
> > Avoid signed overflow in timekeeping_get_ns()").  When the code was
> > refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
> > translation") the signed overflow fix was lost.  Re-introduce it.
> >
> > Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
> > ---
> > I happened to be looking for an unrelated fix, found this code,
> > realized the tip code didn't match the fixed code, and
> > backtracked to where it had gone away.
> >
> >  kernel/time/timekeeping.c | 3 +--
> >  1 file changed, 1 insertion(+), 2 deletions(-)
> >
> > diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
> > index 37dec7e3db43..57926bc7b7f3 100644
> > --- a/kernel/time/timekeeping.c
> > +++ b/kernel/time/timekeeping.c
> > @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
> >  {
> >         s64 nsec;
> >
> > -       nsec = delta * tkr->mult + tkr->xtime_nsec;
> > -       nsec >>= tkr->shift;
> > +       nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
> 
> Ugh.
> 
> So... I think this proves the original fix was *far* too subtle to
> maintain. So I think reintroducing it as-is doesn't protect us from
> undoing it.  If the problem is really using the signed intermediate
> nsec value, we should get rid of that.

As I told the other guy who submitted something similar: This is not really
helpful. It merily drags the overflow case out by a factor of 2.

So we really need to figure out under which circumstances this can happen
and fixup either the callsites or detect the condition right there, which
I'd like to avoid for the hotpath.

Thanks,

	tglx

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[John Stultz]

On Tue, Nov 15, 2016 at 1:53 PM, Thomas Gleixner <tglx@linutronix.de> wrote:
> On Mon, 14 Nov 2016, John Stultz wrote:
>
>> On Mon, Nov 14, 2016 at 11:42 AM, Chris Metcalf <cmetcalf@mellanox.com> wrote:
>> > This bugfix was originally made in commit 35a4933a8959 ("time:
>> > Avoid signed overflow in timekeeping_get_ns()").  When the code was
>> > refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
>> > translation") the signed overflow fix was lost.  Re-introduce it.
>> >
>> > Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
>> > ---
>> > I happened to be looking for an unrelated fix, found this code,
>> > realized the tip code didn't match the fixed code, and
>> > backtracked to where it had gone away.
>> >
>> >  kernel/time/timekeeping.c | 3 +--
>> >  1 file changed, 1 insertion(+), 2 deletions(-)
>> >
>> > diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
>> > index 37dec7e3db43..57926bc7b7f3 100644
>> > --- a/kernel/time/timekeeping.c
>> > +++ b/kernel/time/timekeeping.c
>> > @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
>> >  {
>> >         s64 nsec;
>> >
>> > -       nsec = delta * tkr->mult + tkr->xtime_nsec;
>> > -       nsec >>= tkr->shift;
>> > +       nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
>>
>> Ugh.
>>
>> So... I think this proves the original fix was *far* too subtle to
>> maintain. So I think reintroducing it as-is doesn't protect us from
>> undoing it.  If the problem is really using the signed intermediate
>> nsec value, we should get rid of that.
>
> As I told the other guy who submitted something similar: This is not really
> helpful. It merily drags the overflow case out by a factor of 2.

Well... So lost time (where a VM/gdb caused stall runs past the
clocksource or causes an mult overflow) is a bit less problematic then
getting a huge negative nsec value.

> So we really need to figure out under which circumstances this can happen
> and fixup either the callsites or detect the condition right there, which
> I'd like to avoid for the hotpath.

I get that catching the (delta > TOOBIG) case, but even then I'm not
sure how we deal that condition in a way that results in anything
meaningfully different from the less-problematic unsigned overflow
(ie, capping it).

thanks
-john

Re: [PATCH] time: Avoid signed overflow in timekeeping_delta_to_ns()

[John Stultz]

On Tue, Nov 15, 2016 at 2:03 PM, John Stultz <john.stultz@linaro.org> wrote:
> On Tue, Nov 15, 2016 at 1:53 PM, Thomas Gleixner <tglx@linutronix.de> wrote:
>> On Mon, 14 Nov 2016, John Stultz wrote:
>>
>>> On Mon, Nov 14, 2016 at 11:42 AM, Chris Metcalf <cmetcalf@mellanox.com> wrote:
>>> > This bugfix was originally made in commit 35a4933a8959 ("time:
>>> > Avoid signed overflow in timekeeping_get_ns()").  When the code was
>>> > refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
>>> > translation") the signed overflow fix was lost.  Re-introduce it.
>>> >
>>> > Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
>>> > ---
>>> > I happened to be looking for an unrelated fix, found this code,
>>> > realized the tip code didn't match the fixed code, and
>>> > backtracked to where it had gone away.
>>> >
>>> >  kernel/time/timekeeping.c | 3 +--
>>> >  1 file changed, 1 insertion(+), 2 deletions(-)
>>> >
>>> > diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
>>> > index 37dec7e3db43..57926bc7b7f3 100644
>>> > --- a/kernel/time/timekeeping.c
>>> > +++ b/kernel/time/timekeeping.c
>>> > @@ -304,8 +304,7 @@ static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
>>> >  {
>>> >         s64 nsec;
>>> >
>>> > -       nsec = delta * tkr->mult + tkr->xtime_nsec;
>>> > -       nsec >>= tkr->shift;
>>> > +       nsec = (delta * tkr->mult + tkr->xtime_nsec) >> tkr->shift;
>>>
>>> Ugh.
>>>
>>> So... I think this proves the original fix was *far* too subtle to
>>> maintain. So I think reintroducing it as-is doesn't protect us from
>>> undoing it.  If the problem is really using the signed intermediate
>>> nsec value, we should get rid of that.
>>
>> As I told the other guy who submitted something similar: This is not really
>> helpful. It merily drags the overflow case out by a factor of 2.
>
> Well... So lost time (where a VM/gdb caused stall runs past the
> clocksource or causes an mult overflow) is a bit less problematic then
> getting a huge negative nsec value.
>
>> So we really need to figure out under which circumstances this can happen
>> and fixup either the callsites or detect the condition right there, which
>> I'd like to avoid for the hotpath.
>
> I get that catching the (delta > TOOBIG) case, but even then I'm not
> sure how we deal that condition in a way that results in anything
> meaningfully different from the less-problematic unsigned overflow
> (ie, capping it).

So I think I'm going to queue up Liav's fix here, as it has been in my
TOQUEUE folder for a bit longer.

Thomas: I know you didn't like it when it was originally submitted,
preferring to catch the case when it happens, but the signed shift is
more problematic. Additionally, the CONFIG_DEBUG_TIMEKEEPING checks
should already warn on the next tick when this case triggers (when the
offset is larger then max_cycles).

Sound ok?

thanks
-john

[PATCH v2] time: Avoid signed overflow in timekeeping_delta_to_ns()

[Chris Metcalf]

This bug was originally fixed in commit 35a4933a8959 ("time:
Avoid signed overflow in timekeeping_get_ns()").  When the code was
refactored in commit 6bd58f09e1d8 ("time: Add cycles to nanoseconds
translation") the signed overflow fix was lost.  Re-introduce it
in a less subtle way by changing the type of "nsec" to unsigned
and adding a comment explaining why.

Signed-off-by: Chris Metcalf <cmetcalf@mellanox.com>
---
v2: just use "u64 nsec" to fix the signed shift problem

 kernel/time/timekeeping.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index 37dec7e3db43..8c06a2aa9b5f 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -302,7 +302,7 @@ static inline u32 arch_gettimeoffset(void) { return 0; }
 static inline s64 timekeeping_delta_to_ns(struct tk_read_base *tkr,
 					  cycle_t delta)
 {
-	s64 nsec;
+	u64 nsec;   /* Avoid possibility of a negative right shift. */
 
 	nsec = delta * tkr->mult + tkr->xtime_nsec;
 	nsec >>= tkr->shift;
-- 
2.7.2