linux-kernel - Re: [PATCH] sched, x86: fix overflow in cyc2ns

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAKUOC8W--JcA1YfWgSuK3f=dexiJS=-N6ro_3b1W=FnhdYxOrw@mail.gmail.com>
Date:	Fri, 9 Mar 2012 16:29:15 -0800
From:	Salman Qazi <sqazi@...gle.com>
To:	Paul Turner <pjt@...gle.com>
Cc:	john stultz <johnstul@...ibm.com>, Ingo Molnar <mingo@...e.hu>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] sched, x86: fix overflow in cyc2ns_offset

On Fri, Mar 9, 2012 at 4:22 PM, Paul Turner <pjt@...gle.com> wrote:
> On Fri, Mar 9, 2012 at 4:00 PM, Salman Qazi <sqazi@...gle.com> 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.
>>
>> Signed-off-by: Salman Qazi <sqazi@...gle.com>
>> ---
>>  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)); \
>> +}                                                      \
>> +)
>
> Any reason not to make this a static inline so that we get saner typing?

Only re-usability.  I put it in include/linux/kernel.h with a lot of
other #defines like min , max, clamp, that are generally
applicable.

>
>> +
>> +
>>  #define _RET_IP_               (unsigned long)__builtin_return_address(0)
>>  #define _THIS_IP_  ({ __label__ __here; __here: (unsigned long)&&__here; })
>>
>>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/