The timestamp counter and ordered reads

7.2 The clock: where a timestamp comes from

A timestamp is a reading of a counter, and a latency is the difference of two readings; whether that difference is a time depends on which counter was read, how it was read, and whether both readings came from the same counter. Each of the three can go wrong without any error, and each has a cost the measurement pays.

What a clock is to a CPU

To a program, a clock is a number that grows at a known rate. A PC has several. The platform’s chipset carries the HPET, the High Precision Event Timer, a counter ticking at 14–25 MHz that a core reads over the bus at 0.5–1 µs a read. And every core carries its own TSC, the time stamp counter: a 64-bit register, set to zero when the machine is powered on and incremented at a fixed rate from then on. The rdtsc instruction copies it into two 32-bit registers, which Rust’s intrinsic joins into one u64. It is an ordinary instruction that a user program may execute, with no call into the kernel, unless the kernel has forbidden it, which Linux does only for a process that asks. At 3.4 GHz the counter wraps after 2⁶⁴ ticks, about 170 years.

The kernel builds its own clocks on one of these counters, its clocksource, and prefers the TSC whenever it trusts it. Two of the clocks it offers matter here. CLOCK_REALTIME is the date and time of day, and it jumps whenever an administrator or the time daemon sets it: a step backward between two readings makes a latency negative. CLOCK_MONOTONIC never goes backward; the time daemon may only slew its rate, by at most 500 parts per million, 0.05%, to pull it towards true time. A latency is always taken from a monotonic counter, and the TSC, read directly, is one.

Invariant

The early TSCs ticked with the core’s own clock. When a core slowed down to save power the TSC slowed with it, and in the deepest idle states it stopped, so a difference of two readings was neither a time nor a reliable count of anything. Intel’s processors from 2008 on, and AMD’s from about the same years, made the TSC invariant: it ticks at one fixed rate whatever the core is doing, at turbo speed, throttled for power or heat, or asleep. The processor reports this in a CPUID bit, and Linux shows it as two flags in /proc/cpuinfo: constant_tsc, the rate does not follow the core’s frequency, and nonstop_tsc, the counter keeps counting in deep idle states. With both present the TSC is a clock.

Its fixed rate is the TSC frequency, a nominal figure close to the processor’s advertised base frequency: a part sold as 3.4 GHz that turbos to 5.0 GHz has a TSC ticking at or very near 3.4 GHz. The kernel finds the frequency at boot, from the processor where it says, otherwise by timing the TSC against another counter, and prints it: tsc: Detected 3400.000 MHz processor, and on many machines a later, finer line such as tsc: Refined TSC clocksource calibration: 3400.022 MHz. A difference of TSC readings divided by that frequency is a time and nothing else. It is the clock every timestamp in this chapter comes from.

Reading it

The hardware chapter’s out-of-order core runs each instruction when its inputs are ready, not in the order the program lists them, and only retires them in order. rdtsc is not serialising: nothing makes it wait for the instructions before it, so the core may read the counter while a slow load above it is still waiting on memory, or let instructions below it start first. A read placed after an operation can then happen before the operation is done, and the interval it closes is shorter than the work it claims to time.

The fix is a fence. lfence is an instruction that lets nothing after it begin until everything before it has completed; Intel defines it that way, and current AMD parts behave the same once the kernel enables it, which Linux does. lfence then rdtsc reads the counter after all earlier work has finished, at a cost of 10–20 ns more than the bare read, because the core must drain what it had in flight. rdtscp is the other form. It waits for all earlier instructions to execute before it reads, and it also returns the contents of a register called TSC_AUX, into which Linux writes, at boot, the number of each core in its low 12 bits and the core’s memory node above them. So every rdtscp reading carries the core it was taken on, and two readings with the same core number came from one core’s counter. Neither form stops later instructions from starting early, so a strict measurement also puts an lfence after its closing read. For intervals of hundreds of nanoseconds those few cycles of overlap at either edge do not matter; for an operation of 10–20 cycles they are all there is, which is why such operations are timed in bulk under perf stat and not one by one.

The capstone’s clock is three short functions, in src/lib.rs:

use core::arch::x86_64::{__rdtscp, _mm_lfence, _rdtsc};
use std::time::{Duration, Instant};

/// The TSC, read once every earlier instruction has finished.
#[inline(always)]
pub fn now() -> u64 {
    unsafe {
        _mm_lfence();   // wait for earlier instructions: do not read early
        _rdtsc()
    }
}

/// The TSC and the number of the core that read it.
#[inline(always)]
pub fn now_cpu() -> (u64, u32) {
    let mut aux = 0u32;
    let t = unsafe { __rdtscp(&mut aux) };  // aux: TSC_AUX, filled by the kernel at boot
    (t, aux & 0xfff)                        // low 12 bits: the CPU; above them, the node
}

/// TSC ticks per nanosecond, measured once at startup against CLOCK_MONOTONIC.
pub fn calibrate() -> f64 {
    let (i0, t0) = (Instant::now(), now());
    while i0.elapsed() < Duration::from_millis(200) {}  // spin for 200 ms
    let (i1, t1) = (Instant::now(), now());
    (t1 - t0) as f64 / (i1 - i0).as_nanos() as f64
}

now() is what the loop calls. now_cpu() is for checking, at the start and end of a run, that a thread is where it was pinned. calibrate() counts ticks across 200 ms of the kernel’s monotonic clock. Each pair of reads is uncertain by the 20–25 ns they take, so the error is about 50 ns in 200 ms, a quarter of a part per million; the time daemon’s slew, at most 0.05%, is below the 0.1% resolution of the histograms that use the result. Anything from 100 to 500 ms is enough. The loop stores raw ticks, a u64 that costs nothing to subtract, and converts to nanoseconds only when it records, outside the timed region.