Re: [PATCH] sched, x86: fix overflow in cyc2ns_offset

[Salman Qazi]

On Fri, Mar 9, 2012 at 4:25 PM, john stultz <johnstul@xxxxxxxxxx> wrote:
>
> On Fri, 2012-03-09 at 16:00 -0800, Salman Qazi wrote:
> > When a machine boots up, the TSC generally gets reset.  However, when
> > kexec is used to boot into a kernel, the TSC value would be carried
> > over from the previous kernel.  The computation of cycns_offset in
> > set_cyc2ns_scale is prone to an overflow, if the machine has been up
> > more than 208 days prior to the kexec.  The overflow happens when
> > we multiply *scale, even though there is enough room to store the
> > final answer.  We fix this issue by decomposing tsc_now into the
> > quotient and remainder of division by CYC2NS_SCALE_FACTOR and then
> > performing the multiplication separately on the two components.
> >
> > Refactor code to share the calculation with the previous
> > fix in __cycles_2_ns.
>
> Thanks so much for making it more generic and reusable! But one question
> below.
>
> > Signed-off-by: Salman Qazi <sqazi@xxxxxxxxxx>
> > ---
> >  arch/x86/include/asm/timer.h |    8 ++------
> >  arch/x86/kernel/tsc.c        |    3 ++-
> >  include/linux/kernel.h       |   13 +++++++++++++
> >  3 files changed, 17 insertions(+), 7 deletions(-)
> >
> > diff --git a/arch/x86/include/asm/timer.h b/arch/x86/include/asm/timer.h
> > index 431793e..34baa0e 100644
> > --- a/arch/x86/include/asm/timer.h
> > +++ b/arch/x86/include/asm/timer.h
> > @@ -57,14 +57,10 @@ DECLARE_PER_CPU(unsigned long long, cyc2ns_offset);
> >
> >  static inline unsigned long long __cycles_2_ns(unsigned long long cyc)
> >  {
> > -     unsigned long long quot;
> > -     unsigned long long rem;
> >       int cpu = smp_processor_id();
> >       unsigned long long ns = per_cpu(cyc2ns_offset, cpu);
> > -     quot = (cyc >> CYC2NS_SCALE_FACTOR);
> > -     rem = cyc & ((1ULL << CYC2NS_SCALE_FACTOR) - 1);
> > -     ns += quot * per_cpu(cyc2ns, cpu) +
> > -             ((rem * per_cpu(cyc2ns, cpu)) >> CYC2NS_SCALE_FACTOR);
> > +     ns += mult_frac(cyc, per_cpu(cyc2ns, cpu),
> > +                     (1UL << CYC2NS_SCALE_FACTOR));
> >       return ns;
> >  }
> >
> > diff --git a/arch/x86/kernel/tsc.c b/arch/x86/kernel/tsc.c
> > index a62c201..183c592 100644
> > --- a/arch/x86/kernel/tsc.c
> > +++ b/arch/x86/kernel/tsc.c
> > @@ -620,7 +620,8 @@ static void set_cyc2ns_scale(unsigned long cpu_khz,
> > int cpu)
> >
> >       if (cpu_khz) {
> >               *scale = (NSEC_PER_MSEC << CYC2NS_SCALE_FACTOR)/cpu_khz;
> > -             *offset = ns_now - (tsc_now * *scale >>
> > CYC2NS_SCALE_FACTOR);
> > +             *offset = ns_now - mult_frac(tsc_now, *scale,
> > +                                          (1UL <<
> > CYC2NS_SCALE_FACTOR));
> >       }
> >
> >       sched_clock_idle_wakeup_event(0);
> > diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> > index e834342..d801acb 100644
> > --- a/include/linux/kernel.h
> > +++ b/include/linux/kernel.h
> > @@ -85,6 +85,19 @@
> >  }                                                    \
> >  )
> >
> > +/*
> > + * Multiplies an integer by a fraction, while avoiding unnecessary
> > + * overflow or loss of precision.
> > + */
> > +#define mult_frac(x, numer, denom)(                  \
> > +{                                                    \
> > +     typeof(x) quot = (x) / (denom);                 \
> > +     typeof(x) rem  = (x) % (denom);                 \
> > +     (quot * (numer)) + ((rem * (numer)) / (denom)); \
> > +}                                                    \
> > +)
> > +
> > +
>
> So... Sorry, why did you change it from the shifted logic?
>

It's more generally applicable.  The compiler is smart enough to do
the right thing in the power-of-two
constant case.


> I was thinking more like:
> mult_shifted_fract(x, mult, shift)
> {
>        quot = x >> shift;
>        rem = x & ((1ULL << shift)-1);
>        return quot * mult + (rem * mult) >> shift;
> }
>
> Is the compiler really smart enough to avoid the divides?

Yes, it is.  I verified that.

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