Deep Dive into Linux Timekeeping Architecture: System Time, Timers, and Hardware Oscillators

1. Linux Timing Architecture

The Linux kernel separates time management into two concepts: a system time point (wall‑clock) and time intervals (timers). The core data structure is struct timespec defined in linux/v3.10/source/include/uapi/linux/time.h#L9 :

struct timespec {
  __kernel_time_t tv_sec;
  long tv_nsec;
};

The global xtime object stores the current seconds ( tv_sec ) and nanoseconds ( tv_nsec ) since the Unix epoch.

During kernel boot, timekeeping_init() (called from init/main.c ) reads the persistent hardware clock via read_persistent_clock() :

void read_persistent_clock(struct timespec *ts) {
  unsigned long retval;
  retval = x86_platform.get_wallclock();
  ts->tv_sec = retval;
  ts->tv_nsec = 0;
}

The low‑level get_wallclock() function ultimately calls mach_get_cmos_time() , which reads the RTC registers (seconds, minutes, hours, day, month, year) and converts them with mktime() :

unsigned long mktime(const unsigned int year0, const unsigned int mon0,
                     const unsigned int day, const unsigned int hour,
                     const unsigned int min, const unsigned int sec) {
  /* conversion algorithm omitted for brevity */
  return ((((unsigned long)(year/4 - year/100 + year/400 + 367*mon/12 + day) +
           year*365 - 719499) * 24 + hour) * 60 + min) * 60 + sec;
}

After initialization, the kernel provides fast user‑space access to the current time via __getnstimeofday() , which uses a sequence lock to avoid costly user‑kernel switches:

int __getnstimeofday(struct timespec *ts) {
  struct timekeeper *tk = &timekeeper
  unsigned long seq;
  s64 nsecs = 0;
  do {
    seq = read_seqcount_begin(&timekeeper_seq);
    ts->tv_sec = tk->xtime_sec;
    nsecs = timekeeping_get_ns(tk);
  } while (read_seqcount_retry(&timekeeper_seq, seq));
  ts->tv_nsec = 0;
  timespec_add_ns(ts, nsecs);
  return 0;
}

When the system clock is set, do_settimeofday() acquires a write lock, updates xtime , and propagates the change to the monotonic clock.

int do_settimeofday(const struct timespec *tv) {
  struct timekeeper *tk = &timekeeper
  struct timespec ts_delta, xt;
  unsigned long flags;
  raw_spin_lock_irqsave(&timekeeper_lock, flags);
  write_seqcount_begin(&timekeeper_seq);
  timekeeping_forward_now(tk);
  xt = tk_xtime(tk);
  ts_delta.tv_sec = tv->tv_sec - xt.tv_sec;
  ts_delta.tv_nsec = tv->tv_nsec - xt.tv_nsec;
  tk_set_wall_to_mono(tk, timespec_sub(tk->wall_to_monotonic, ts_delta));
  tk_set_xtime(tk, tv);
  timekeeping_update(tk, true, true);
  write_seqcount_end(&timekeeper_seq);
  raw_spin_unlock_irqrestore(&timekeeper_lock, flags);
  return 0;
}

2. Timer Infrastructure

Linux tracks the number of timer ticks since boot with the jiffies counter, whose frequency is defined by HZ (typically 100). The 32‑bit jiffies wraps roughly every 50 days; to expose early wrap‑around bugs the kernel starts it at -300*HZ .

extern u64 __jiffy_data jiffies_64;
extern unsigned long volatile __jiffy_data jiffies;
#define INITIAL_JIFFIES ((unsigned long)(unsigned int)(-300*HZ))

Dynamic timers are represented by struct timer_list :

struct timer_list {
  struct list_head entry;
  unsigned long expires;
  struct tvec_base *base;
  void (*function)(unsigned long);
  unsigned long data;
};

The kernel has evolved several algorithms to manage these timers:

Raw list algorithm : O(1) add, O(n) delete and expiry scan.

Sorted list algorithm : O(n) add, O(1) delete and expiry.

Min‑heap algorithm : O(log n) add, O(1) delete and expiry.

Timing‑wheel algorithm : O(1) for all operations but requires a large array for fine granularity.

Hierarchical timing wheel : multiple wheels with different granularities, reducing memory while keeping O(1) operations; incurs “cascade” work when a higher‑level wheel rolls over.

Red‑black tree (hrtimer) : stores high‑resolution timers; add/delete are O(log n) and the next expiry is always at the tree’s leftmost node, allowing the kernel to program the hardware timer for the earliest deadline.

For very short delays the kernel bypasses the timer subsystem and uses busy‑wait functions udelay() or ndelay() , which either read the TSC/HPET or execute calibrated loops.

3. Hardware Clock Source

The ultimate time source is a quartz crystal oscillator. The crystal exhibits the piezoelectric effect: an applied electric field causes mechanical deformation, and conversely, mechanical stress generates an electric field. When driven at its resonant frequency, the crystal oscillates stably, providing the precise clock ticks that the kernel ultimately counts.

4. Summary

The article walks from the Linux kernel’s high‑level time APIs down to the hardware oscillator that generates the tick signal. It explains how the system time is initialized, read, and updated, describes the data structures and algorithms behind timers, and highlights the trade‑offs between simplicity, memory usage, and latency in different timer implementations.