linux的TSC计算原理mult和shift－clocksource_cyc2ns

TSC即（Time Stamp Counter或Time Source Cycles）
1 用法
/**
 * cyc2ns - converts clocksource cycles to nanoseconds
 * @cs:        Pointer to clocksource
 * @cycles:    Cycles
 *
 * Uses the clocksource and ntp ajdustment to convert cycle_ts to nanoseconds.
 *
 * XXX - This could use some mult_lxl_ll() asm optimization
 */
static inline s64 cyc2ns(struct clocksource *cs, cycle_t cycles)
{
    u64 ret = (u64)cycles;
    ret = (ret * cs->mult) >> cs->shift;
    return ret;
}

2 动机

为什么不 cycles *NSEC_PER_SEC / freq?



1. convert the clock cycles to ns

ns = cyc * NSEC_PER_SEC / freq (freq is clock freq of the counter)
= use the scaling math. (please refer to arch/x86/kernel/tsc.c)
= (cyc * mult) >> shift (refer to clocksource_calc_mult_shift() )

另2.6.34
arch/x86/kernel/tsc.c
/* Accelerators for sched_clock()
 * convert from cycles(64bits) => nanoseconds (64bits)
 *  basic equation:
 *              ns = cycles / (freq / ns_per_sec)
 *              ns = cycles * (ns_per_sec / freq)
 *              ns = cycles * (10^9 / (cpu_khz * 10^3))
 *              ns = cycles * (10^6 / cpu_khz)
 *
 *      Then we use scaling math (suggested by [e-mail]) to get:
 *              ns = cycles * (10^6 * SC / cpu_khz) / SC
因为SC为2^order倍数,所以也就等效于[luther.gliethttp]
mult = (10^6 << shift) / cpu_khz
即
mult = (10^9 << shift) / cpu_hz
 *              ns = (cycles * mult) >> shift
 *              ns = cycles * cyc2ns_scale / SC
 *
 *      And since SC is a constant power of two, we can convert the div
 *  into a shift.
 *
 *  We can use khz divisor instead of mhz to keep a better precision, since
 *  cyc2ns_scale is limited to 10^6 * 2^10, which fits in 32 bits.
 *  ([e-mail])
 *
 *                      [e-mail] "math is hard, lets go shopping!"
 */
3 shift value和mult的选取

/**
+ * clocksource_hz2shift - calculates shift from hz and # of bits
+ * @bits: Number of bits this clocksource uses
+ * @hz: Clocksource frequency in Hz
+ *
+ * Helper functions that calculates the best shift value
+ * based on the hz and # of bits of any given clock.
+ */
+static inline u32 clocksource_hz2shift(u32 bits, u32 hz)
+{
+ u64 temp;
+
+ for (; bits > 0; bits--) {
+ temp = (u64) NSEC_PER_SEC << bits;
+ do_div(temp, hz);
+ if ((temp >> 32) == 0)
+ break;
+ }
+ return bits;
+}
结 合下面的解释,可以看到要保证shift足够大, 同时又要保证temp(即以后的mult) 必须 2^32-1 范围内

时钟源设备（clock-source device）

系统中可以提供一定精度的计时设备都可以作为时钟源设备。如 TSC，HPET，ACPI PM-Timer，PIT 等。但是不同的时钟源提供的时钟精度是不一样的。像 TSC，HPET 等时钟源既支持高精度模式（high-resolution mode）也支持低精度模式（low-resolution mode），而 PIT 只能支持低精度模式。此外，时钟源的计时都是单调递增的（monotonically），如果时钟源的计时出现翻转（即返回到 0 值），很容易造成计时错误， 内核的一个 patch（commit id: ff69f2）就是处理这类问题的一个很好示例。时钟源作为系统时钟的提供者，在可靠并且可用的前提下精度越高越好。在 Linux 中不同的时钟源有不同的 rating，具有更高 rating 的时钟源会优先被系统使用。如图 2 所示：

1 ~ 99	100 ~ 199	200 ~ 299	300 ~ 399	400 ~ 499
非常差的时钟源，只能作为最后的选择。如 jiffies	基本可以使用但并非理想的时钟源。如 PIT	正确可用的时钟源。如 ACPI PM Timer，HPET	快速并且精确的时钟源。如 TSC	理想时钟源。如 kvm_clock，xen_clock

[patch 0/3] Provide generic function to calc mult/shift factors for clocks

The mult and shift factors of clock events differ in their data type
from those of clock sources for no reason. u32 is sufficient for
both. shift is always <= 32 and mult is limited to 2^32-1 to avoid
64bit multiplication overflows in the conversion.

2.6.34 有clocksource_calc_mult_shift函数
/**
 * clocksource_hz2mult - calculates mult from hz and shift
 * @hz:            Clocksource frequency in Hz
 * @shift_constant:    Clocksource shift factor
 *
 * Helper functions that converts a hz counter
 * frequency to a timsource multiplier, given the
 * clocksource shift value
 */
static inline u32 clocksource_hz2mult(u32 hz, u32 shift_constant)
{
    /*  hz = cyc/(Billion ns)
     *  mult/2^shift  = ns/cyc
     *  mult = ns/cyc * 2^shift
     *  mult = 1Billion/hz * 2^shift
     *  mult = 1000000000 * 2^shift / hz
     *  mult = (1000000000<     */
    u64 tmp = ((u64)1000000000) << shift_constant;

    tmp += hz/2; /* round for do_div */
    do_div(tmp, hz);

    return (u32)tmp;
}
/**
 * clocksource_khz2mult - calculates mult from khz and shift
 * @khz:        Clocksource frequency in KHz
 * @shift_constant:    Clocksource shift factor
 *
 * Helper functions that converts a khz counter frequency to a timsource
 * multiplier, given the clocksource shift value
 */
static inline u32 clocksource_khz2mult(u32 khz, u32 shift_constant)
{
    /*  khz = cyc/(Million ns)
     *  mult/2^shift  = ns/cyc
     *  mult = ns/cyc * 2^shift
     *  mult = 1Million/khz * 2^shift
     *  mult = 1000000 * 2^shift / khz
     *  mult = (1000000<     */
    u64 tmp = ((u64)1000000) << shift_constant;

    tmp += khz/2; /* round for do_div */
    do_div(tmp, khz);

    return (u32)tmp;
}

/**
 * clocksource_hz2mult - calculates mult from hz and shift
 * @hz:            Clocksource frequency in Hz
 * @shift_constant:    Clocksource shift factor
 *
 * Helper functions that converts a hz counter
 * frequency to a timsource multiplier, given the
 * clocksource shift value
 */
static inline u32 clocksource_hz2mult(u32 hz, u32 shift_constant)
{
    /*  hz = cyc/(Billion ns)
     *  mult/2^shift  = ns/cyc
     *  mult = ns/cyc * 2^shift
     *  mult = 1Billion/hz * 2^shift
     *  mult = 1000000000 * 2^shift / hz
     *  mult = (1000000000<     */
    u64 tmp = ((u64)1000000000) << shift_constant;

    tmp += hz/2; /* round for do_div */
    do_div(tmp, hz);

    return (u32)tmp;
}

/**
 * clocksource_cyc2ns - converts clocksource cycles to nanoseconds
 *
 * Converts cycles to nanoseconds, using the given mult and shift.
 *
 * XXX - This could use some mult_lxl_ll() asm optimization
 */
static inline s64 clocksource_cyc2ns(cycle_t cycles, u32 mult, u32 shift)
{
    return ((u64) cycles * mult) >> shift;
}

转：http://blog.chinaunix.net/space.php?uid=1858380&do=blog&cuid=2231638