Linux 时钟管理
Linux 中的定时器
在 Linux 内核中主要有两种类型的定时器。一类称为 timeout 类型，另一类称为 timer 类型。timeout 类型的定时器通常用于检测各种错误条件，例如用于检测网卡收发数据包是否会超时的定时器，IO 设备的读写是否会超时的定时器等等。通常情况下这些错误很少发生，因此，使用 timeout 类型的定时器一般在超时之前就会被移除，从而很少产生真正的函数调用和系统开销。总的来说，使用 timeout 类型的定时器产生的系统开销很小，它是下文提及的 timer wheel 通常使用的环境。此外，在使用 timeout 类型定时器的地方往往并不关心超时处理，因此超时精确与否，早 0.01 秒或者晚 0.01 秒并不十分重要，这在下文论述 deferrable timers 时会进一步介绍。timer 类型的定时器与 timeout 类型的定时器正相反，使用 timer 类型的定时器往往要求在精确的时钟条件下完成特定的事件，通常是周期性的并且依赖超时机制进行处理。例如设备驱动通常会定时读写设备来进行数据交互。如何高效的管理 timer 类型的定时器对提高系统的处理效率十分重要，下文在介绍 hrtimer 时会有更加详细的论述。
内核需要进行时钟管理，离不开底层的硬件支持。在早期是通过 8253 芯片提供的 PIT（Programmable Interval Timer）来提供时钟，但是 PIT 的频率很低，只能提供最高 1ms 的时钟精度，由于 PIT 触发的中断速度太慢，会导致很大的时延，对于像音视频这类对时间精度要求更高的应用并不足够，会极大的影响用户体验。随着硬件平台的不断发展变化，陆续出现了 TSC（Time Stamp Counter），HPET（High Precision Event Timer），ACPI PM Timer（ACPI Power Management Timer），CPU Local APIC Timer 等精度更高的时钟。这些时钟陆续被 Linux 的时钟子系统所采纳，从而不断的提高 Linux 时钟子系统的性能和灵活性。这些不同的时钟会在下文不同的章节中分别进行介绍。
Timer wheel
在 Linux 2.6.16 之前，内核一直使用一种称为 timer wheel 的机制来管理时钟。这就是熟知的 kernel 一直采用的基于 HZ 的 timer 机制。Timer wheel 的核心数据结构如清单 1 所示：
清单 1. Timer wheel 的核心数据结构
#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)#define TVN_SIZE (1 << TVN_BITS)#define TVR_SIZE (1 << TVR_BITS)#define TVN_MASK (TVN_SIZE - 1)#define TVR_MASK (TVR_SIZE - 1)struct tvec {struct list_head vec[TVN_SIZE];};struct tvec_root {struct list_head vec[TVR_SIZE];};struct tvec_base {spinlock_t lock;struct timer_list *running_timer;unsigned long timer_jiffies;unsigned long next_timer;struct tvec_root tv1;struct tvec tv2;struct tvec tv3;struct tvec tv4;struct tvec tv5;} ____cacheline_aligned; 以 CONFIG_BASE_SMALL 定义为 0 为例，TVR_SIZE ＝ 256，TVN_SIZE ＝ 64，这样
可以得到如图 1 所示的 timer wheel 的结构。
图 1. Timer wheel 的逻辑结构
在 timer wheel 的框架下，所有系统正在使用的 timer 并不是顺序存放在一个平坦的链表中，因为这样做会使得查找，插入，删除等操作效率低下。Timer wheel 提供了 5 个 timer 数组，数组之间存在着类似时分秒的进位关系。TV1 为第一个 timer 数组，其中存放着从 timer_jiffies（当前到期的 jiffies）到 timer_jiffies + 255 共 256 个 tick 对应的 timer list。因为在一个 tick 上可能同时有多个 timer 等待超时处理，timer wheel 使用 list_head 将所有 timer 串成一个链表，以便在超时时顺序处理。TV2 有 64 个单元，每个单元都对应着 256 个 tick，因此 TV2 所表示的超时时间范围从 timer_jiffies + 256 到 timer_jiffies + 256 * 64 – 1。依次类推 TV3，TV4，TV5。以 HZ=1000 为例，每 1ms 产生一次中断，TV1 就会被访问一次，但是 TV2 要每 256ms 才会被访问一次，TV3 要 16s，TV4 要 17 分钟，TV5 甚至要 19 小时才有机会检查一次。最终，timer wheel 可以管理的最大超时值为 2^32。一共使用了 512 个 list_head（256+64+64+64+64）。如果 CONFIG_BASE_SMALL 定义为 1，则最终使用的 list_head 个数为 128 个（64+16+16+16+16），占用的内存更少，更适合嵌入式系统使用。Timer wheel 的处理逻辑如清单 2 所示：
清单 2. timer wheel 的核心处理函数
static inline void __run_timers(struct tvec_base *base){struct timer_list *timer;spin_lock_irq(&base->lock);while (time_after_eq(jiffies, base->timer_jiffies)) {struct list_head work_list;struct list_head *head = &work_list;int index = base->timer_jiffies & TVR_MASK;/** Cascade timers:*/if (!index &&(!cascade(base, &base->tv2, INDEX(0))) &&(!cascade(base, &base->tv3, INDEX(1))) &&!cascade(base, &base->tv4, INDEX(2)))cascade(base, &base->tv5, INDEX(3));++base->timer_jiffies;list_replace_init(base->tv1.vec + index, &work_list);while (!list_empty(head)) {void (*fn)(unsigned long);unsigned long data;timer = list_first_entry(head, struct timer_list,entry);fn = timer->function;data = timer->data;. . . .fn(data);. . . .} base->timer_jiffies 用来记录在 TV1 中最接近超时的 tick 的位置。index 是用来遍历 TV1 的索引。每一次循环 index 会定位一个当前待处理的 tick，并处理这个 tick 下所有超时的 timer。base->timer_jiffies 会在每次循环后增加一个 jiffy，index 也会随之向前移动。当 index 变为 0 时表示 TV1 完成了一次完整的遍历，此时所有在 TV1 中的 timer 都被处理了，因此需要通过 cascade 将后面 TV2，TV3 等 timer list 中的 timer 向前移动，类似于进位。这种层叠的 timer list 实现机制可以大大降低每次检查超时 timer 的时间，每次中断只需要针对 TV1 进行检查，只有必要时才进行 cascade。即便如此，timer wheel 的实现机制仍然存在很大弊端。一个弊端就是 cascade 开销过大。在极端的条件下，同时会有多个 TV 需要进行 cascade 处理，会产生很大的时延。这也是为什么说 timeout 类型的定时器是 timer wheel 的主要应用环境，或者说 timer wheel 是为 timeout 类型的定时器优化的。因为 timeout 类型的定时器的应用场景多是错误条件的检测，这类错误发生的机率很小，通常不到超时就被删除了，因此不会产生 cascade 的开销。另一方面，由于 timer wheel 是建立在 HZ 的基础上的，因此其计时精度无法进一步提高。毕竟一味的通过提高 HZ 值来提高计时精度并无意义，结果只能是产生大量的定时中断，增加额外的系统开销。因此，有必要将高精度的 timer 与低精度的 timer 分开，这样既可以确保低精度的 timeout 类型的定时器应用，也便于高精度的 timer 类型定时器的应用。还有一个重要的因素是 timer wheel 的实现与 jiffies 的耦合性太强，非常不便于扩展。因此，自从 2.6.16 开始，一个新的 timer 子系统 hrtimer 被加入到内核中。
hrtimer (High-resolution Timer)
hrtimer 首先要实现的功能就是要克服 timer wheel 的缺点：低精度以及与内核其他模块的高耦合性。在正式介绍 hrtimer 之前，有必要先介绍几个常用的基本概念：
时钟源设备（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. 时钟源中 rating 的定义
时钟事件设备（clock-event device）
系统中可以触发 one-shot（单次）或者周期性中断的设备都可以作为时钟事件设备。如 HPET，CPU Local APIC Timer 等。HPET 比较特别，它既可以做时钟源设备也可以做时钟事件设备。时钟事件设备的类型分为全局和 per-CPU 两种类型。全局的时钟事件设备虽然附属于某一个特定的 CPU 上，但是完成的是系统相关的工作，例如完成系统的 tick 更新；per-CPU 的时钟事件设备主要完成 Local CPU 上的一些功能，例如对在当前 CPU 上运行进程的时间统计，profile，设置 Local CPU 上的下一次事件中断等。和时钟源设备的实现类似，时钟事件设备也通过 rating 来区分优先级关系。
tick device
Tick device 用来处理周期性的 tick event。Tick device 其实是时钟事件设备的一个 wrapper，因此 tick device 也有 one-shot 和周期性这两种中断触发模式。每注册一个时钟事件设备，这个设备会自动被注册为一个 tick device。全局的 tick device 用来更新诸如 jiffies 这样的全局信息，per-CPU 的 tick device 则用来更新每个 CPU 相关的特定信息。
broadcast
Broadcast 的出现是为了应对这样一种情况：假定 CPU 使用 Local APIC Timer 作为 per-CPU 的 tick device，但是某些特定的 CPU（如 Intel 的 Westmere 之前的 CPU）在进入 C3+ 的状态时 Local APIC Timer 也会同时停止工作，进入睡眠状态。在这种情形下 broadcast 可以替代 Local APIC Timer 继续完成统计进程的执行时间等有关操作。本质上 broadcast 是发送一个 IPI（Inter-processorinterrupt）中断给其他所有的 CPU，当目标 CPU 收到这个 IPI 中断后就会调用原先 Local APIC Timer 正常工作时的中断处理函数，从而实现了同样的功能。目前主要在 x86 以及 MIPS 下会用到 broadcast 功能。Timekeeping & GTOD (Generic Time-of-Day)
Timekeeping（可以理解为时间测量或者计时）是内核时间管理的一个核心组成部分。没有 Timekeeping，就无法更新系统时间，维持系统“心跳”。GTOD 是一个通用的框架，用来实现诸如设置系统时间 gettimeofday 或者修改系统时间 settimeofday 等工作。为了实现以上功能，Linux 实现了多种与时间相关但用于不同目的的数据结构。
struct timespec {__kernel_time_ttv_sec;/* seconds */longtv_nsec;/* nanoseconds */}; timespec 精度是纳秒。它用来保存从 00:00:00 GMT, 1 January 1970 开始经过的时间。内核使用全局变量 xtime 来记录这一信息，这就是通常所说的“Wall Time”或者“Real Time”。与此对应的是“System Time”。System Time 是一个单调递增的时间，每次系统启动时从 0 开始计时。
struct timeval {__kernel_time_ttv_sec;/* seconds */__kernel_suseconds_ttv_usec;/* microseconds */}; timeval 精度是微秒。timeval 主要用来指定一段时间间隔。
union ktime {s64tv64;#if BITS_PER_LONG != 64 && !defined(CONFIG_KTIME_SCALAR)struct {# ifdef __BIG_ENDIANs32sec, nsec;# elses32nsec, sec;# endif} tv;#endif}; ktime_t 是 hrtimer 主要使用的时间结构。无论使用哪种体系结构，ktime_t 始终保持 64bit 的精度，并且考虑了大小端的影响。
typedef u64 cycle_t;
cycle_t 是从时钟源设备中读取的时钟类型。
为了管理这些不同的时间结构，Linux 实现了一系列辅助函数来完成相互间的转换。
ktime_to_timespec，ktime_to_timeval，ktime_to_ns/ktime_to_us，反过来有诸如 ns_to_ktime 等类似的函数。
timeval_to_ns，timespec_to_ns，反过来有诸如 ns_to_timeval 等类似的函数。
timeval_to_jiffies，timespec_to_jiffies，msecs_to_jiffies, usecs_to_jiffies, clock_t_to_jiffies 反过来有诸如 ns_to_timeval 等类似的函数。
clocksource_cyc2ns / cyclecounter_cyc2ns
有了以上的介绍，通过图 3 可以更加清晰的看到这几者之间的关联。
图 2. 内核时钟子系统的结构关系
时钟源设备和时钟事件设备的引入，将原本放在各个体系结构中重复实现的冗余代码封装到各自的抽象层中，这样做不但消除了原来 timer wheel 与内核其他模块的紧耦合性，更重要的是系统可以在运行状态动态更换时钟源设备和时钟事件设备而不影响系统正常使用，譬如当 CPU 由于睡眠要关闭当前使用的时钟源设备或者时钟事件设备时系统可以平滑的切换到其他仍处于工作状态的设备上。Timekeeping/GTOD 在使用时钟源设备的基础上也采用类似的封装实现了体系结构的无关性和通用性。hrtimer 则可以通过 timekeeping 提供的接口完成定时器的更新，通过时钟事件设备提供的事件机制，完成对 timer 的管理。在图 3 中还有一个重要的模块就是 tick device 的抽象，尤其是 dynamic tick。Dynamic tick 的出现是为了能在系统空闲时通过停止 tick 的运行以达到降低 CPU 功耗的目的。使用 dynamic tick 的系统，只有在有实际工作时才会产生 tick，否则 tick 是处于停止状态。下文会有专门的章节进行论述。
hrtimer 的实现机制
hrtimer 是建立在 per-CPU 时钟事件设备上的，对于一个 SMP 系统，如果只有全局的时钟事件设备，hrtimer 无法工作。因为如果没有 per-CPU 时钟事件设备，时钟中断发生时系统必须产生必要的 IPI 中断来通知其他 CPU 完成相应的工作，而过多的 IPI 中断会带来很大的系统开销，这样会令使用 hrtimer 的代价太大，不如不用。为了支持 hrtimer，内核需要配置 CONFIG_HIGH_RES_TIMERS=y。hrtimer 有两种工作模式：低精度模式（low-resolution mode）与高精度模式（high-resolution mode）。虽然 hrtimer 子系统是为高精度的 timer 准备的，但是系统可能在运行过程中动态切换到不同精度的时钟源设备，因此，hrtimer 必须能够在低精度模式与高精度模式下自由切换。由于低精度模式是建立在高精度模式之上的，因此即便系统只支持低精度模式，部分支持高精度模式的代码仍然会编译到内核当中。
在低精度模式下，hrtimer 的核心处理函数是 hrtimer_run_queues，每一次 tick 中断都要执行一次。如清单 3 所示。这个函数的调用流程为：
update_process_timesrun_local_timershrtimer_run_queuesraise_softirq(TIMER_SOFTIRQ)
清单 3. 低精度模式下 hrtimer 的核心处理函数
void hrtimer_run_queues(void){struct rb_node *node;struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);struct hrtimer_clock_base *base;int index, gettime = 1;if (hrtimer_hres_active())return;for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) {base = &cpu_base->clock_base[index];if (!base->first)continue;if (gettime) {hrtimer_get_softirq_time(cpu_base);gettime = 0;}raw_spin_lock(&cpu_base->lock);while ((node = base->first)) {struct hrtimer *timer;timer = rb_entry(node, struct hrtimer, node);if (base->softirq_time.tv64 <=hrtimer_get_expires_tv64(timer))break;__run_hrtimer(timer, &base->softirq_time);}raw_spin_unlock(&cpu_base->lock);}} hrtimer_bases 是实现 hrtimer 的核心数据结构，通过 hrtimer_bases，hrtimer 可以管理挂在每一个 CPU 上的所有 timer。每个 CPU 上的 timer list 不再使用 timer wheel 中多级链表的实现方式，而是采用了红黑树（Red-Black Tree）来进行管理。hrtimer_bases 的定义如清单 4 所示：
清单 4. hrtimer_bases 的定义
DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) ={.clock_base ={{.index = CLOCK_REALTIME,.get_time = &ktime_get_real,.resolution = KTIME_LOW_RES,},{.index = CLOCK_MONOTONIC,.get_time = &ktime_get,.resolution = KTIME_LOW_RES,},}}; 图 4 展示了 hrtimer 如何通过 hrtimer_bases 来管理 timer。
图 3. hrtimer 的时钟管理
每个 hrtimer_bases 都包含两个 clock_base，一个是 CLOCK_REALTIME 类型的，另一个是 CLOCK_MONOTONIC 类型的。hrtimer 可以选择其中之一来设置 timer 的 expire time, 可以是实际的时间 , 也可以是相对系统运行的时间。
在 hrtimer_run_queues 的处理中，首先要通过 hrtimer_bases 找到正在执行当前中断的 CPU 相关联的 clock_base，然后逐个检查每个 clock_base 上挂的 timer 是否超时。由于 timer 在添加到 clock_base 上时使用了红黑树，最早超时的 timer 被放到树的最左侧，因此寻找超时 timer 的过程非常迅速，找到的所有超时 timer 会被逐一处理。超时的 timer 根据其类型分为 softIRQ / per-CPU / unlocked 几种。如果一个 timer 是 softIRQ 类型的，这个超时的 timer 需要被转移到 hrtimer_bases 的 cb_pending 的 list 上，待 IRQ0 的软中断被激活后，通过 run_hrtimer_pending 执行，另外两类则必须在 hardIRQ 中通过 __run_hrtimer 直接执行。不过在较新的 kernel（> 2.6.29）中，cb_pending 被取消，这样所有的超时 timers 都必须在 hardIRQ 的 context 中执行。这样修改的目的，一是为了简化代码逻辑，二是为了减少 2 次 context 的切换：一次从 hardIRQ 到 softIRQ，另一次从 softIRQ 到被超时 timer 唤醒的进程。
在 update_process_times 中，除了处理处于低精度模式的 hrtimer 外，还要唤醒 IRQ0 的 softIRQ（TIMER_SOFTIRQ（run_timer_softirq））以便执行 timer wheel 的代码。由于 hrtimer 子系统的加入，在 IRQ0 的 softIRQ 中，还需要通过 hrtimer_run_pending 检查是否可以将 hrtimer 切换到高精度模式，如清单 5 所示：
清单 5. hrtimer 进行精度切换的处理函数
void hrtimer_run_pending(void){if (hrtimer_hres_active())return;/** This _is_ ugly: We have to check in the softirq context,* whether we can switch to highres and / or nohz mode. The* clocksource switch happens in the timer interrupt with* xtime_lock held. Notification from there only sets the* check bit in the tick_oneshot code, otherwise we might* deadlock vs. xtime_lock.*/if (tick_check_oneshot_change(!hrtimer_is_hres_enabled()))hrtimer_switch_to_hres();} 正如这段代码的作者注释中所提到的，每一次触发 IRQ0 的 softIRQ 都需要检查一次是否可以将 hrtimer 切换到高精度，显然是十分低效的，希望将来有更好的方法不用每次都进行检查。
如果可以将 hrtimer 切换到高精度模式，则调用 hrtimer_switch_to_hres 函数进行切换。如清单 6 所示：
清单 6. hrtimer 切换到高精度模式的核心函数
/** Switch to high resolution mode*/static int hrtimer_switch_to_hres(void){int cpu = smp_processor_id();struct hrtimer_cpu_base *base = &per_cpu(hrtimer_bases, cpu);unsigned long flags;if (base->hres_active)return 1;local_irq_save(flags);if (tick_init_highres()) {local_irq_restore(flags);printk(KERN_WARNING "Could not switch to high resolution ""mode on CPU %dn", cpu);return 0;}base->hres_active = 1;base->clock_base[CLOCK_REALTIME].resolution = KTIME_HIGH_RES;base->clock_base[CLOCK_MONOTONIC].resolution = KTIME_HIGH_RES;tick_setup_sched_timer();/* "Retrigger" the interrupt to get things going */retrigger_next_event(NULL);local_irq_restore(flags);return 1;} hrtimer_interrupt的使用环境
hrtimer_interrupt 有 2 种常见的使用方式。一是作为 tick 的推动器在产生 tick 中断时被调用；另一种情况就是通过软中断 HRTIMER_SOFTIRQ（run_hrtimer_softirq）被调用，通常是被驱动程序或者间接的使用这些驱动程序的用户程序所调用
在这个函数中，首先使用 tick_init_highres 更新与原来的 tick device 绑定的时钟事件设备的 event handler，例如将在低精度模式下的工作函数 tick_handle_periodic / tick_handle_periodic_broadcast 换成 hrtimer_interrupt（它是 hrtimer 在高精度模式下的 timer 中断处理函数），同时将 tick device 的触发模式变为 one-shot，即单次触发模式，这是使用 dynamic tick 或者 hrtimer 时 tick device 的工作模式。由于 dynamic tick 可以随时停止和开始，以不规律的速度产生 tick，因此支持 one-shot 模式的时钟事件设备是必须的；对于 hrtimer，由于 hrtimer 采用事件机制驱动 timer 前进，因此使用 one-shot 的触发模式也是顺理成章的。不过这样一来，原本 tick device 每次执行中断时需要完成的周期性任务如更新 jiffies / wall time (do_timer) 以及更新 process 的使用时间（update_process_times）等工作在切换到高精度模式之后就没有了，因此在执行完 tick_init_highres 之后紧接着会调用 tick_setup_sched_timer 函数来完成这部分设置工作，如清单 7 所示：
清单 7. hrtimer 高精度模式下模拟周期运行的 tick device 的简化实现
void tick_setup_sched_timer(void){struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);ktime_t now = ktime_get();u64 offset;/** Emulate tick processing via per-CPU hrtimers:*/hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);ts->sched_timer.function = tick_sched_timer;. . . .for (;;) {hrtimer_forward(&ts->sched_timer, now, tick_period);hrtimer_start_expires(&ts->sched_timer,HRTIMER_MODE_ABS_PINNED);/* Check, if the timer was already in the past */if (hrtimer_active(&ts->sched_timer))break;now = ktime_get();}. . . .} 这个函数使用 tick_cpu_sched 这个 per-CPU 变量来模拟原来 tick device 的功能。tick_cpu_sched 本身绑定了一个 hrtimer，这个 hrtimer 的超时值为下一个 tick，回调函数为 tick_sched_timer。因此，每过一个 tick，tick_sched_timer 就会被调用一次，在这个回调函数中首先完成原来 tick device 的工作，然后设置下一次的超时值为再下一个 tick，从而达到了模拟周期运行的 tick device 的功能。如果所有的 CPU 在同一时间点被唤醒，并发执行 tick 时可能会出现 lock 竞争以及 cache-line 冲突，为此 Linux 内核做了特别处理：如果假设 CPU 的个数为 N，则所有的 CPU 都在 tick_period 前 1/2 的时间内执行 tick 工作，并且每个 CPU 的执行间隔是 tick_period / (2N)，见清单 8 所示：
清单 8. hrtimer 在高精度模式下 tick 执行周期的设置
void tick_setup_sched_timer(void){. . . ./* Get the next period (per cpu) */hrtimer_set_expires(&ts->sched_timer, tick_init_jiffy_update());offset = ktime_to_ns(tick_period) >> 1;do_div(offset, num_possible_cpus());offset *= smp_processor_id();hrtimer_add_expires_ns(&ts->sched_timer, offset);. . . .} 回到 hrtimer_switch_to_hres 函数中，在一切准备就绪后，调用 retrigger_next_event 激活下一次的 timer 就可以开始正常的运作了。
随着 hrtimer 子系统的发展，一些问题也逐渐暴露了出来。一个比较典型的问题就是 CPU 的功耗问题。现代 CPU 都实现了节能的特性，在没有工作时 CPU 会主动降低频率，关闭 CPU 内部一些非关键模块以达到节能的目的。由于 hrtimer 的精度很高，触发中断的频率也会很高，频繁的中断会极大的影响 CPU 的节能。在这方面 hrtimer 一直在不断的进行调整。以下几个例子都是针对这一问题所做的改进。
schedule_hrtimeout 函数
/*** schedule_hrtimeout - sleep until timeout* @expires:timeout value (ktime_t)* @mode:timer mode, HRTIMER_MODE_ABS or HRTIMER_MODE_REL*/int __sched schedule_hrtimeout(ktime_t *expires, const enum hrtimer_mode mode)
schedule_hrtimeout 用来产生一个高精度的调度超时，以 ns 为单位。这样可以更加细粒度的使用内核的调度器。在 Arjan van de Ven 的最初实现中，这个函数有一个很大的问题：由于其粒度很细，所以可能会更加频繁的唤醒内核，导致消耗更多的能源。为了实现既能节省能源，又能确保精确的调度超时，Arjan van de Ven 的办法是将一个超时点变成一个超时范围。设置 hrtimer A 的超时值有一个上限，称为 hard expire，在 hard expire 这个时间点上设置 hrtimer A 的超时中断；同时设置 hrtimer A 的超时值有一个下限，称为 soft expire。在 soft expire 到 hard expire 之间如果有一个 hrtimer B 的中断被触发，在 hrtimer B 的中断处理函数中，内核会检查是否有其他 hrtimer 的 soft expire 超时了，譬如 hrtimer A 的 soft expire 超时了，即使 hrtimer A 的 hard expire 没有到，也可以顺带被处理。换言之，将原来必须在 hard expire 超时才能执行的一个点变成一个范围后，可以尽量把 hrtimer 中断放在一起处理，这样 CPU 被重复唤醒的几率会变小，从而达到节能的效果，同时这个 hrtimer 也可以保证其执行精度。
Deferrable timers & round jiffies
在内核中使用的某些 legacy timer 对于精确的超时值并不敏感，早一点或者晚一点执行并不会产生多大的影响，因此，如果可以把这些对时间不敏感同时超时时间又比较接近的 timer 收集在一起执行，可以进一步减少 CPU 被唤醒的次数，从而达到节能的目地。这正是引入 Deferrable timers 的目地。如果一个 timer 可以被短暂延时，那么可以通过调用 init_timer_deferrable 设置 defer 标记，从而在执行时灵活选择处理方式。不过，如果这些 timers 都被延时到同一个时间点上也不是最优的选择，这样同样会产生 lock 竞争以及 cache-line 的问题。因此，即便将 defer timers 收集到一起，彼此之间也必须稍稍错开一些以防止上述问题。这正是引入 round_jiffies 函数的原因。虽然这样做会使得 CPU 被唤醒的次数稍多一些，但是由于间隔短，CPU 并不会进入很深的睡眠，这个代价还是可以接受的。由于 round_jiffies 需要在每次更新 timer 的超时值（mod_timer）时被调用，显得有些繁琐，因此又出现了更为便捷的 round jiffies 机制，称为 timer slack。Timer slack 修改了 timer_list 的结构定义，将需要偏移的 jiffies 值保存在 timer_list 内部，通过 apply_slack 在每次更新 timer 的过程中自动更新超时值。apply_slack 的实现如清单 9 所示：
清单 9. apply_slack 的实现
/** Decide where to put the timer while taking the slack into account** Algorithm:*1) calculate the maximum (absolute) time*2) calculate the highest bit where the expires and new max are different*3) use this bit to make a mask*4) use the bitmask to round down the maximum time, so that all last*bits are zeros*/static inlineunsigned long apply_slack(struct timer_list *timer, unsigned long expires){unsigned long expires_limit, mask;int bit;expires_limit = expires;if (timer->slack >= 0) {expires_limit = expires + timer->slack;} else {unsigned long now = jiffies; /* avoid reading jiffies twice *//* if already expired, no slack; otherwise slack 0.4% */if (time_after(expires, now))expires_limit = expires + (expires - now)/256;}mask = expires ^ expires_limit;if (mask == 0)return expires;bit = find_last_bit(&mask, BITS_PER_LONG);mask = (1 << bit) - 1;expires_limit = expires_limit & ~(mask);return expires_limit;} 随着现代计算机系统的发展，对节能的需求越来越高，尤其是在使用笔记本，手持设备等移动环境是对节能要求更高。Linux 当然也会更加关注这方面的需求。hrtimer 子系统的优化尽量确保在使用高精度的时钟的同时节约能源，如果系统在空闲时也可以尽量的节能，则 Linux 系统的节能优势可以进一步放大。这也是引入 dynamic tick 的根本原因。
Dynamic tick & tickless
在 dynamic tick 引入之前，内核一直使用周期性的基于 HZ 的 tick。传统的 tick 机制在系统进入空闲状态时仍然会产生周期性的中断，这种频繁的中断迫使 CPU 无法进入更深的睡眠。如果放开这个限制，在系统进入空闲时停止 tick，有工作时恢复 tick，实现完全自由的，根据需要产生 tick 的机制，可以使 CPU 获得更多的睡眠机会以及更深的睡眠，从而进一步节能。dynamic tick 的出现，就是为彻底替换掉周期性的 tick 机制而产生的。周期性运行的 tick 机制需要完成诸如进程时间片的计算，更新 profile，协助 CPU 进行负载均衡等诸多工作，这些工作 dynamic tick 都提供了相应的模拟机制来完成。由于 dynamic tick 的实现需要内核的很多模块的配合，包括了很多实现细节，这里只介绍 dynamic tick 的核心工作机制，以及如何启动和停止 dynamic tick。
Dynamic tick 的核心处理流程
从上文中可知内核时钟子系统支持低精度和高精度两种模式，因此 dynamic tick 也必须有两套对应的处理机制。从清单 5 中可以得知，如果系统支持 hrtimer 的高精度模式，hrtimer 可以在此从低精度模式切换到高精度模式。其实清单 5 还有另外一个重要功能：它也是低精度模式下从周期性 tick 到 dynamic tick 的切换点。如果当前系统不支持高精度模式，系统会尝试切换到 NOHZ 模式，也就是使用 dynamic tick 的模式，当然前提是内核使能了 NOHZ 模式。其核心处理函数如清单 10 所示。这个函数的调用流程如下：
tick_check_oneshot_changetick_nohz_switch_to_nohztick_switch_to_oneshot(tick_nohz_handler)
清单 10. 低精度模式下 dynamic tick 的核心处理函数
static void tick_nohz_handler(struct clock_event_device *dev){struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);struct pt_regs *regs = get_irq_regs();int cpu = smp_processor_id();ktime_t now = ktime_get();dev->next_event.tv64 = KTIME_MAX;if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE))tick_do_timer_cpu = cpu;/* Check, if the jiffies need an update */if (tick_do_timer_cpu == cpu)tick_do_update_jiffies64(now);/** When we are idle and the tick is stopped, we have to touch* the watchdog as we might not schedule for a really long* time. This happens on complete idle SMP systems while* waiting on the login prompt. We also increment the "start* of idle" jiffy stamp so the idle accounting adjustment we* do when we go busy again does not account too much ticks.*/if (ts->tick_stopped) {touch_softlockup_watchdog();ts->idle_jiffies++;}update_process_times(user_mode(regs));profile_tick(CPU_PROFILING);while (tick_nohz_reprogram(ts, now)) {now = ktime_get();tick_do_update_jiffies64(now);}} 在这个函数中，首先模拟周期性 tick device 完成类似的工作：如果当前 CPU 负责全局 tick device 的工作，则更新 jiffies，同时完成对本地 CPU 的进程时间统计等工作。如果当前 tick device 在此之前已经处于停止状态，为了防止 tick 停止时间过长造成 watchdog 超时，从而引发 soft-lockdep 的错误，需要通过调用 touch_softlockup_watchdog 复位软件看门狗防止其溢出。正如代码中注释所描述的，这种情况有可能出现在启动完毕，完全空闲等待登录的 SMP 系统上。最后需要设置下一次 tick 的超时时间。如果 tick_nohz_reprogram 执行时间超过了一个 jiffy，会导致设置的下一次超时时间已经过期，因此需要重新设置，相应的也需要再次更新 jiffies。这里虽然设置了下一次的超时事件，但是由于系统空闲时会停止 tick，因此下一次的超时事件可能发生，也可能不发生。这也正是 dynamic tick 根本特性。
从清单 7 中可以看到，在高精度模式下 tick_sched_timer 用来模拟周期性 tick device 的功能。dynamic tick 的实现也使用了这个函数。这是因为 hrtimer 在高精度模式时必须使用 one-shot 模式的 tick device，这也同时符合 dynamic tick 的要求。虽然使用同样的函数，表面上都会触发周期性的 tick 中断，但是使用 dynamic tick 的系统在空闲时会停止 tick 工作，因此 tick 中断不会是周期产生的。
Dynamic tick 的开始和停止
当 CPU 进入空闲时是最好的时机。此时可以启动 dynamic tick 机制，停止 tick；反之在 CPU 从空闲中恢复到工作状态时，则可以停止 dynamic tick。见清单 11 所示：
清单 11. CPU 在 idle 时 dynamic tick 的启动 / 停止设置
void cpu_idle(void){. . . .while (1) {tick_nohz_stop_sched_tick(1);while (!need_resched()) {. . . .}tick_nohz_restart_sched_tick();}. . . .} timer 子系统的初始化过程
在分别了解了内核时钟子系统各个模块后，现在可以系统的介绍内核时钟子系统的初始化过程。系统刚上电时，需要注册 IRQ0 时钟中断，完成时钟源设备，时钟事件设备，tick device 等初始化操作并选择合适的工作模式。由于刚启动时没有特别重要的任务要做，因此默认是进入低精度 + 周期 tick 的工作模式，之后会根据硬件的配置（如硬件上是否支持 HPET 等高精度 timer）和软件的配置（如是否通过命令行参数或者内核配置使能了高精度 timer 等特性）进行切换。在一个支持 hrtimer 高精度模式并使能了 dynamic tick 的系统中，第一次发生 IRQ0 的软中断时 hrtimer 就会进行从低精度到高精度的切换，然后再进一步切换到 NOHZ 模式。IRQ0 为系统的时钟中断，使用全局的时钟事件设备（global_clock_event）来处理的，其定义如下：
static struct irqaction irq0= {.handler = timer_interrupt,.flags = IRQF_DISABLED | IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER,.name = "timer" }; 它的中断处理函数 timer_interrupt 的简化实现如清单 12 所示：
清单 12. IRQ0 中断处理函数的简化实现
static irqreturn_t timer_interrupt(int irq, void *dev_id){. . . .global_clock_event->event_handler(global_clock_event); . . . .return IRQ_HANDLED;} 在 global_clock_event->event_handler 的处理中，除了更新 local CPU 上运行进程时间的统计，profile 等工作，更重要的是要完成更新 jiffies 等全局操作。这个全局的时钟事件设备的 event_handler 根据使用环境的不同，在低精度模式下可能是 tick_handle_periodic / tick_handle_periodic_broadcast，在高精度模式下是 hrtimer_interrupt。目前只有 HPET 或者 PIT 可以作为 global_clock_event 使用。其初始化流程清单 13 所示：
清单 13. timer 子系统的初始化流程
void __init time_init(void){late_time_init = x86_late_time_init;}static __init void x86_late_time_init(void){x86_init.timers.timer_init();tsc_init();}/* x86_init.timers.timer_init 是指向 hpet_time_init 的回调指针 */void __init hpet_time_init(void){if (!hpet_enable())setup_pit_timer();setup_default_timer_irq();} 由清单 13 可以看到，系统优先使用 HPET 作为 global_clock_event，只有在 HPET 没有使能时，PIT 才有机会成为 global_clock_event。在使能 HPET 的过程中，HPET 会同时被注册为时钟源设备和时钟事件设备。
hpet_enablehpet_clocksource_registerhpet_legacy_clockevent_registerclockevents_register_device(&hpet_clockevent);
clockevent_register_device 会触发 CLOCK_EVT_NOTIFY_ADD 事件，即创建对应的 tick device。然后在 tick_notify 这个事件处理函数中会添加新的 tick device。
clockevent_register_device trigger event CLOCK_EVT_NOTIFY_ADDtick_notify receives event CLOCK_EVT_NOTIFY_ADDtick_check_new_devicetick_setup_device
在 tick device 的设置过程中，会根据新加入的时钟事件设备是否使用 broadcast 来分别设置 event_handler。对于 tick device 的处理函数，可见图 5 所示：
表 2. tick device 在不同模式下的处理函数
另外，在系统运行的过程中，可以通过查看 /proc/timer_list 来显示系统当前配置的所有时钟的详细情况，譬如当前系统活动的时钟源设备，时钟事件设备，tick device 等。也可以通过查看 /proc/timer_stats 来查看当前系统中所有正在使用的 timer 的统计信息。包括所有正在使用 timer 的进程，启动 / 停止 timer 的函数，timer 使用的频率等信息。内核需要配置 CONFIG_TIMER_STATS=y，而且在系统启动时这个功能是关闭的，需要通过如下命令激活"echo 1 >/proc/timer_stats"。/proc/timer_stats 的显示格式如下所示：
<count>, <pid> <command> <start_func> (<expire_func>)
总结
随着应用环境的改变，使用需求的多样化，Linux 的时钟子系统也在不断的衍变。为了更好的支持音视频等对时间精度高的应用，Linux 提出了 hrtimer 这一高精度的时钟子系统，为了节约能源，Linux 改变了长久以来一直使用的基于 HZ 的 tick 机制，采用了 tickless 系统。即使是在对硬件平台的支持上，也是在不断改进。举例来说，由于 TSC 精度高，是首选的时钟源设备。但是现代 CPU 会在系统空闲时降低频率以节约能源，从而导致 TSC 的频率也会跟随发生改变。这样会导致 TSC 无法作为稳定的时钟源设备使用。随着新的 CPU 的出现，即使 CPU 的频率发生变化，TSC 也可以一直维持在固定频率上，从而确保其稳定性。在 Intel 的 Westmere 之前的 CPU 中，TSC 和 Local APIC Timer 类似，都会在 C3+ 状态时进入睡眠，从而导致系统需要切换到其他较低精度的时钟源设备上，但是在 Intel Westmere 之后的 CPU 中，TSC 可以一直保持运行状态，即使 CPU 进入了 C3+ 的睡眠状态，从而避免了时钟源设备的切换。在 SMP 的环境下，尤其是 16-COREs，32-COREs 这样的多 CPU 系统中，每个 CPU 之间的 TSC 很难保持同步，很容易出现“Out-of-Sync”。如果在这种环境下使用 TSC，会造成 CPU 之间的计时误差，然而在 Intel 最新的 Nehalem-EX CPU 中，已经可以确保 TSC 在多个 CPU 之间保持同步，从而可以使用 TSC 作为首选的时钟源设备。由此可见，无论是现在还是将来，只要有需要，内核的时钟子系统就会一直向前发展。
下载文档
