[RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

Greetings,

While rummaging around looking for HTH a gaggle of weird a$$ machines
can manage to timewarp back and forth by exactly 208 days, I stumbled
across $subject which looks like it may want to borrow Salman's fix.

clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
cycles * mult >> shift is overflow prone. so give it the same treatment.

Cc: Salman Qazi <sqazi@google.com>
Cc: John Stultz <johnstul@us.ibm.com>
Signed-off-by: Mike Galbraith <bitbucket@online.de>
---
 include/linux/clocksource.h |   11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

--- a/include/linux/clocksource.h
+++ b/include/linux/clocksource.h
@@ -77,13 +77,18 @@ struct timecounter {
  *
  * XXX - This could use some mult_lxl_ll() asm optimization. Same code
  * as in cyc2ns, but with unsigned result.
+ *
+ * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
+ * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
+ * to avoid a potential cycles * mult overflow.
  */
 static inline u64 cyclecounter_cyc2ns(const struct cyclecounter *cc,
 				      cycle_t cycles)
 {
-	u64 ret = (u64)cycles;
-	ret = (ret * cc->mult) >> cc->shift;
-	return ret;
+	u64 quot = (u64)cycles >> cc->shift;
+	u64 rem = (u64)cycles & ((1ULL << cc->shift) - 1);
+
+	return  quot * cc->mult + ((rem * cc->mult) >> cc->shift);
 }
 
 /**

[RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

(crap crap crap... M.A.I.N.T.A.I.N.E.R.S _dummy_)

clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
cycles * mult >> shift is overflow prone. so give it the same treatment.

Cc: Salman Qazi <sqazi@google.com>
Cc: John Stultz <john.stultz@linaro.org>,
Signed-off-by: Mike Galbraith <bitbucket@online.de>
---
 include/linux/clocksource.h |   11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

--- a/include/linux/clocksource.h
+++ b/include/linux/clocksource.h
@@ -77,13 +77,18 @@ struct timecounter {
  *
  * XXX - This could use some mult_lxl_ll() asm optimization. Same code
  * as in cyc2ns, but with unsigned result.
+ *
+ * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
+ * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
+ * to avoid a potential cycles * mult overflow.
  */
 static inline u64 cyclecounter_cyc2ns(const struct cyclecounter *cc,
 				      cycle_t cycles)
 {
-	u64 ret = (u64)cycles;
-	ret = (ret * cc->mult) >> cc->shift;
-	return ret;
+	u64 quot = (u64)cycles >> cc->shift;
+	u64 rem = (u64)cycles & ((1ULL << cc->shift) - 1);
+
+	return  quot * cc->mult + ((rem * cc->mult) >> cc->shift);
 }
 
 /**

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[John Stultz]

On Tue, Mar 4, 2014 at 1:38 PM, Mike Galbraith <bitbucket@online.de> wrote:
> (crap crap crap... M.A.I.N.T.A.I.N.E.R.S _dummy_)
>
> clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
>
> As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> cycles * mult >> shift is overflow prone. so give it the same treatment.
>
> Cc: Salman Qazi <sqazi@google.com>
> Cc: John Stultz <john.stultz@linaro.org>,
> Signed-off-by: Mike Galbraith <bitbucket@online.de>

Thanks for sending this in!  Curious exactly how the issue was being
triggered?  To some extent the cyclecounter/timecounter code never got
the adoption I expected, so I've sort of had it on my list to see
about killing that code off and merging its users w/ clocksources
(since the clocksource has been simplified since cyclecounters
landed). So curious to see what its actually being used for..
particularly since the timecounter code does have accumulation logic
which should avoid overflows (and deal with hardware counters that
wrap).

I'll put this in my 3.15 queue.

thanks
-john

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

On Tue, 2014-03-04 at 14:40 +0800, John Stultz wrote: 
> On Tue, Mar 4, 2014 at 1:38 PM, Mike Galbraith <bitbucket@online.de> wrote:
> > (crap crap crap... M.A.I.N.T.A.I.N.E.R.S _dummy_)
> >
> > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> >
> > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> > cycles * mult >> shift is overflow prone. so give it the same treatment.
> >
> > Cc: Salman Qazi <sqazi@google.com>
> > Cc: John Stultz <john.stultz@linaro.org>,
> > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> 
> Thanks for sending this in!  Curious exactly how the issue was being
> triggered?

Dunno that it is.  This is the result of me rummaging around, looking
for any excuse what-so-ever for a small and identical group of weird a$$
boxen running old 2.6.32 kernels (w. 208 day fix!) to manage to hop back
and forth in time by exactly 208 days.  Grep showed me that function, so
I scurried off and swiped the fix.

-Mike

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Henrik Austad]

On Tue, Mar 04, 2014 at 06:20:09AM +0100, Mike Galbraith wrote:
> Greetings,
> 
> While rummaging around looking for HTH a gaggle of weird a$$ machines
> can manage to timewarp back and forth by exactly 208 days, I stumbled
> across $subject which looks like it may want to borrow Salman's fix.
> 
> clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> 
> As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> cycles * mult >> shift is overflow prone. so give it the same treatment.
> 
> Cc: Salman Qazi <sqazi@google.com>
> Cc: John Stultz <johnstul@us.ibm.com>
> Signed-off-by: Mike Galbraith <bitbucket@online.de>
> ---
>  include/linux/clocksource.h |   11 ++++++++---
>  1 file changed, 8 insertions(+), 3 deletions(-)
> 
> --- a/include/linux/clocksource.h
> +++ b/include/linux/clocksource.h
> @@ -77,13 +77,18 @@ struct timecounter {
>   *
>   * XXX - This could use some mult_lxl_ll() asm optimization. Same code
>   * as in cyc2ns, but with unsigned result.
> + *
> + * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
> + * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
> + * to avoid a potential cycles * mult overflow.

Do we normally reference a particular commit in a comment? Why not just 
grab the same comment and add a "this is grabbed from arch/x86/... ?

>   */
>  static inline u64 cyclecounter_cyc2ns(const struct cyclecounter *cc,
>  				      cycle_t cycles)
>  {
> -	u64 ret = (u64)cycles;
> -	ret = (ret * cc->mult) >> cc->shift;
> -	return ret;
> +	u64 quot = (u64)cycles >> cc->shift;
> +	u64 rem = (u64)cycles & ((1ULL << cc->shift) - 1);
> +
> +	return  quot * cc->mult + ((rem * cc->mult) >> cc->shift);
>  }

Makes sense to me, for whatever that's worth :)

Also, tile could probably do with a similar approach for ns2cycles (not 
that I have observed any problems, but in the sense of being consistent and 
all). I'll send a patch in a separate email as not to clutter this thread 
too much :)

-- 
Henrik Austad

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

On Tue, 2014-03-04 at 08:20 +0100, Henrik Austad wrote: 
> On Tue, Mar 04, 2014 at 06:20:09AM +0100, Mike Galbraith wrote:
> > Greetings,
> > 
> > While rummaging around looking for HTH a gaggle of weird a$$ machines
> > can manage to timewarp back and forth by exactly 208 days, I stumbled
> > across $subject which looks like it may want to borrow Salman's fix.
> > 
> > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> > 
> > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> > cycles * mult >> shift is overflow prone. so give it the same treatment.
> > 
> > Cc: Salman Qazi <sqazi@google.com>
> > Cc: John Stultz <johnstul@us.ibm.com>
> > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> > ---
> >  include/linux/clocksource.h |   11 ++++++++---
> >  1 file changed, 8 insertions(+), 3 deletions(-)
> > 
> > --- a/include/linux/clocksource.h
> > +++ b/include/linux/clocksource.h
> > @@ -77,13 +77,18 @@ struct timecounter {
> >   *
> >   * XXX - This could use some mult_lxl_ll() asm optimization. Same code
> >   * as in cyc2ns, but with unsigned result.
> > + *
> > + * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
> > + * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
> > + * to avoid a potential cycles * mult overflow.
> 
> Do we normally reference a particular commit in a comment? Why not just 
> grab the same comment and add a "this is grabbed from arch/x86/... ?

Fewer '+' signs?  History doesn't go away, so seems fine to me.

-Mike

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

(boing boing boing... hell with it, today doesn't exist;)

On Tue, 2014-03-04 at 08:31 +0100, Mike Galbraith wrote: 
> On Tue, 2014-03-04 at 08:20 +0100, Henrik Austad wrote: 
> > On Tue, Mar 04, 2014 at 06:20:09AM +0100, Mike Galbraith wrote:
> > > Greetings,
> > > 
> > > While rummaging around looking for HTH a gaggle of weird a$$ machines
> > > can manage to timewarp back and forth by exactly 208 days, I stumbled
> > > across $subject which looks like it may want to borrow Salman's fix.
> > > 
> > > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> > > 
> > > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> > > cycles * mult >> shift is overflow prone. so give it the same treatment.
> > > 
> > > Cc: Salman Qazi <sqazi@google.com>
> > > Cc: John Stultz <johnstul@us.ibm.com>
> > > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> > > ---
> > >  include/linux/clocksource.h |   11 ++++++++---
> > >  1 file changed, 8 insertions(+), 3 deletions(-)
> > > 
> > > --- a/include/linux/clocksource.h
> > > +++ b/include/linux/clocksource.h
> > > @@ -77,13 +77,18 @@ struct timecounter {
> > >   *
> > >   * XXX - This could use some mult_lxl_ll() asm optimization. Same code
> > >   * as in cyc2ns, but with unsigned result.
> > > + *
> > > + * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
> > > + * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
> > > + * to avoid a potential cycles * mult overflow.
> > 
> > Do we normally reference a particular commit in a comment? Why not just 
> > grab the same comment and add a "this is grabbed from arch/x86/... ?
> 
> Fewer '+' signs?  History doesn't go away, so seems fine to me.
> 
> -Mike
> 
> --
> 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/

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Henrik Austad]

On Tue, Mar 04, 2014 at 08:36:28AM +0100, Mike Galbraith wrote:
> (boing boing boing... hell with it, today doesn't exist;)

you lost me at boing.. :)

> On Tue, 2014-03-04 at 08:31 +0100, Mike Galbraith wrote: 
> > On Tue, 2014-03-04 at 08:20 +0100, Henrik Austad wrote: 
> > > On Tue, Mar 04, 2014 at 06:20:09AM +0100, Mike Galbraith wrote:
> > > > Greetings,
> > > > 
> > > > While rummaging around looking for HTH a gaggle of weird a$$ machines
> > > > can manage to timewarp back and forth by exactly 208 days, I stumbled
> > > > across $subject which looks like it may want to borrow Salman's fix.
> > > > 
> > > > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> > > > 
> > > > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> > > > cycles * mult >> shift is overflow prone. so give it the same treatment.
> > > > 
> > > > Cc: Salman Qazi <sqazi@google.com>
> > > > Cc: John Stultz <johnstul@us.ibm.com>
> > > > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> > > > ---
> > > >  include/linux/clocksource.h |   11 ++++++++---
> > > >  1 file changed, 8 insertions(+), 3 deletions(-)
> > > > 
> > > > --- a/include/linux/clocksource.h
> > > > +++ b/include/linux/clocksource.h
> > > > @@ -77,13 +77,18 @@ struct timecounter {
> > > >   *
> > > >   * XXX - This could use some mult_lxl_ll() asm optimization. Same code
> > > >   * as in cyc2ns, but with unsigned result.
> > > > + *
> > > > + * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
> > > > + * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
> > > > + * to avoid a potential cycles * mult overflow.
> > > 
> > > Do we normally reference a particular commit in a comment? Why not just 
> > > grab the same comment and add a "this is grabbed from arch/x86/... ?
> > 
> > Fewer '+' signs?  History doesn't go away, so seems fine to me.

I wasn't thinking about the number of +'s in the code, but rather 
referencing other parts of the code from the code and particular commits in 
the commit-msg itself. It was the code<->commitmsg interface I was 
pondering.

Besides, it wasn't meant as "you shouldn't do that", but more "is it ok to 
do that?" :)

-- 
Henrik Austad

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

On Tue, 2014-03-04 at 09:02 +0100, Henrik Austad wrote: 
> On Tue, Mar 04, 2014 at 08:36:28AM +0100, Mike Galbraith wrote:
> > (boing boing boing... hell with it, today doesn't exist;)
> 
> you lost me at boing.. :)

Mail bounces due to dead addresses.  Bad hair day in progress.  Now my
shiny new address, which is the result of _every damn address_ I tried
at gmail saying "sorry, taken, try again endlessly", has escaped.

> > On Tue, 2014-03-04 at 08:31 +0100, Mike Galbraith wrote: 
> > > On Tue, 2014-03-04 at 08:20 +0100, Henrik Austad wrote: 
> > > > On Tue, Mar 04, 2014 at 06:20:09AM +0100, Mike Galbraith wrote:
> > > > > Greetings,
> > > > > 
> > > > > While rummaging around looking for HTH a gaggle of weird a$$ machines
> > > > > can manage to timewarp back and forth by exactly 208 days, I stumbled
> > > > > across $subject which looks like it may want to borrow Salman's fix.
> > > > > 
> > > > > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> > > > > 
> > > > > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> > > > > cycles * mult >> shift is overflow prone. so give it the same treatment.
> > > > > 
> > > > > Cc: Salman Qazi <sqazi@google.com>
> > > > > Cc: John Stultz <johnstul@us.ibm.com>
> > > > > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> > > > > ---
> > > > >  include/linux/clocksource.h |   11 ++++++++---
> > > > >  1 file changed, 8 insertions(+), 3 deletions(-)
> > > > > 
> > > > > --- a/include/linux/clocksource.h
> > > > > +++ b/include/linux/clocksource.h
> > > > > @@ -77,13 +77,18 @@ struct timecounter {
> > > > >   *
> > > > >   * XXX - This could use some mult_lxl_ll() asm optimization. Same code
> > > > >   * as in cyc2ns, but with unsigned result.
> > > > > + *
> > > > > + * Because it is the same as x86 __cycles_2_ns, give it the same treatment as
> > > > > + * commit 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock"
> > > > > + * to avoid a potential cycles * mult overflow.
> > > > 
> > > > Do we normally reference a particular commit in a comment? Why not just 
> > > > grab the same comment and add a "this is grabbed from arch/x86/... ?
> > > 
> > > Fewer '+' signs?  History doesn't go away, so seems fine to me.
> 
> I wasn't thinking about the number of +'s in the code, but rather 
> referencing other parts of the code from the code and particular commits in 
> the commit-msg itself. It was the code<->commitmsg interface I was 
> pondering.
> 
> Besides, it wasn't meant as "you shouldn't do that", but more "is it ok to 
> do that?" :)

It's perfectly fine until the maintainer says "NAK" :)  If he does, I'll
go generate '+' signs.. that he can then whack when he gets around to
what he said was likely to happen to that code.

-Mike

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[John Stultz]

On Tue, Mar 4, 2014 at 3:10 PM, Mike Galbraith <bitbucket@online.de> wrote:
> On Tue, 2014-03-04 at 14:40 +0800, John Stultz wrote:
>> On Tue, Mar 4, 2014 at 1:38 PM, Mike Galbraith <bitbucket@online.de> wrote:
>> > (crap crap crap... M.A.I.N.T.A.I.N.E.R.S _dummy_)
>> >
>> > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
>> >
>> > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
>> > cycles * mult >> shift is overflow prone. so give it the same treatment.
>> >
>> > Cc: Salman Qazi <sqazi@google.com>
>> > Cc: John Stultz <john.stultz@linaro.org>,
>> > Signed-off-by: Mike Galbraith <bitbucket@online.de>
>>
>> Thanks for sending this in!  Curious exactly how the issue was being
>> triggered?
>
> Dunno that it is.  This is the result of me rummaging around, looking
> for any excuse what-so-ever for a small and identical group of weird a$$
> boxen running old 2.6.32 kernels (w. 208 day fix!) to manage to hop back
> and forth in time by exactly 208 days.  Grep showed me that function, so
> I scurried off and swiped the fix.

So.. this makes me a bit more hesitant to really queue this,
particularly since the timecounter logic is supposed to periodically
accumulate cycles so you don't run into these overflow issues (the
earlier fix was for sched_clock which didn't do any accumulation).

So, if you're seeing time jump around, that's probably clocksource or
timekeping related, and not tied to the cyclecounter code. Do you have
any other info about these systems? What clocksource are they using,
etc?

thanks
-john

Re: [RFC][PATCH] clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()

[Mike Galbraith]

On Wed, 2014-03-05 at 08:58 +0800, John Stultz wrote: 
> On Tue, Mar 4, 2014 at 3:10 PM, Mike Galbraith <bitbucket@online.de> wrote:
> > On Tue, 2014-03-04 at 14:40 +0800, John Stultz wrote:
> >> On Tue, Mar 4, 2014 at 1:38 PM, Mike Galbraith <bitbucket@online.de> wrote:
> >> > (crap crap crap... M.A.I.N.T.A.I.N.E.R.S _dummy_)
> >> >
> >> > clocksource: avoid unnecessary overflow in cyclecounter_cyc2ns()
> >> >
> >> > As per 4cecf6d401a "sched, x86: Avoid unnecessary overflow in sched_clock",
> >> > cycles * mult >> shift is overflow prone. so give it the same treatment.
> >> >
> >> > Cc: Salman Qazi <sqazi@google.com>
> >> > Cc: John Stultz <john.stultz@linaro.org>,
> >> > Signed-off-by: Mike Galbraith <bitbucket@online.de>
> >>
> >> Thanks for sending this in!  Curious exactly how the issue was being
> >> triggered?
> >
> > Dunno that it is.  This is the result of me rummaging around, looking
> > for any excuse what-so-ever for a small and identical group of weird a$$
> > boxen running old 2.6.32 kernels (w. 208 day fix!) to manage to hop back
> > and forth in time by exactly 208 days.  Grep showed me that function, so
> > I scurried off and swiped the fix.
> 
> So.. this makes me a bit more hesitant to really queue this,
> particularly since the timecounter logic is supposed to periodically
> accumulate cycles so you don't run into these overflow issues (the
> earlier fix was for sched_clock which didn't do any accumulation).

Ok.

> So, if you're seeing time jump around, that's probably clocksource or
> timekeping related, and not tied to the cyclecounter code. Do you have
> any other info about these systems? What clocksource are they using,
> etc?

Not much, clocksource is TSC, with CPUs that should make it reliable.
They're interested now, so I'll be hearing more digging more.

-Mike