1. 从tick到timer wheel内核定时器为什么要绕这么多弯很多人第一次看内核定时器相关代码时最大的困惑是timer_listmod_timerdel_timer这套接口明明用起来挺顺手为什么内核非要搞出一个叫timer wheel的东西从命名到数据结构都让人摸不着头脑。我在刚接触这部分源码时也有同样的疑问直到有一次用ftrace跟踪一个驱动程序的高频定时器超时分布才意识到这里头的复杂度远超直觉。先明确一个概念Linux内核里的定时器并不是到点自动执行一个函数这么简单。它的底层驱动来自硬件时钟中断而开发者见到的add_timer、mod_timer这类API都只是对内部timer wheel的封装。也就是说真正决定定时器性能、精度、扩展性的核心机制是timer wheel怎么保存、查找、触发这些定时器。而用户态的timerfd、epoll的超时、网络协议栈的TCP重传、块设备的I/O超时最终都会落到这一层。直接说结论timer wheel用的是多级哈希轮结构这也是名字里wheel轮的由来。内核默认是5级每一级是一个定长的数组每个数组元素挂一条定时器链表。低级轮负责近期的定时器粒度细高级轮负责远期定时器粒度粗。定时器到期后逐级降级到低级轮最终触发回调。这套做法本质上是在插入快和扫描快之间找了个工程平衡点——毕竟内核面对的定时器数量可能成千上万每个tick都从头到尾检查一遍所有定时器早就扛不住了。提示如果你只看过kernel/time/timer.c里add_timer的代码建议先从kernel/time/timer_list.c的输出对应着看这样对timer wheel的整体布局会更有画面感。这篇文章我不会把整份源码从头抄一遍而是挑几个真正重要的点逐一拆数据结构怎么组织、轮转的时机和逻辑是怎么衔接的、为什么会存在过期定时器延迟执行这种看起来违反直觉的现象以及在驱动开发里最容易踩哪些坑。最后再讲讲调试定时器相关问题时的经验和工具。2. timer wheel的数据结构与为什么是5级timer wheel的精髓全在kernel/time/timer.c里的struct timer_base以及tvec_base那套结构上。每个CPU都有一个独立的timer_base这样做的好处是定时器的添加、删除、触发都在本CPU上进行不需要加全局锁避免了多核竞争。这个设计在SMP普及的今天尤其重要因为定时器是内核里调用频率最高的机制之一任何一点锁竞争都会被放大。来看关键的层级定义#define TVN_BITS 6 #define TVR_BITS 8 #define TVN_SIZE (1 TVN_BITS) // 64 #define TVR_SIZE (1 TVR_BITS) // 256 #define TVN_MASK (TVN_SIZE - 1) #define TVR_MASK (TVR_SIZE - 1) struct timer_base { raw_spinlock_t lock; struct timer_list *running_timer; unsigned long clk; unsigned long next_expiry; ... struct hlist_head vectors[LVL_DEPTH][LVL_SIZE]; // 实际是5级数组 };第一个阵列level 0有256个桶每个桶对应1个jiffy的精度。后面每一级是64个桶分别对应256、16384、1048576、67108864个jiffy的范围。这里用LVL_DEPTH表示层级深度默认5LVL_SIZE表示每级的桶数量默认64。如果只算桶的总数是25664646464512个哈希桶看似不多但因为每级桶的跨度不同实际能覆盖的时间范围大得惊人一直到2^32个jiffy也就是大约497天假设HZ1000。也就是说mod_timer传一个很远很远的时间点也不会溢出这是老式的timer wheel按HZ范围硬编码所做不到的。层级间是怎么接上的呢关键在于LVL_START和LVL_SIZE的宏展开。内核通过lvls和level计算函数把一个expires值分解成层级数 偏移量static inline int calc_index(unsigned long expires, unsigned int lvl) { return (expires (LVL_SHIFT(lvl))) LVL_MASK; }LVL_SHIFT随层级线性增加第0级偏移是0第1级偏移是6因为第一级用6位索引64个桶第2级偏移是12依次类推。这个右移位与的过程本质上就是在做取模操作——只不过因为桶大小全是2的幂位运算比除法快得多。再仔细看这5级的有效时间范围分别是层级桶数量覆盖宽度时间表示范围HZ100002561 jiffy/桶0 ~ 255 ms164256 jiffy/桶256 ms ~ 16.384 s26416384 jiffy/桶16.384 s ~ 17.45 min3641048576 jiffy/桶17.45 min ~ 18.6 h46467108864 jiffy/桶18.6 h ~ 497 days有了这个表你再去看内核里__internal_add_timer的代码会发现它做的事情很简单从第0级开始找一旦发现expires能落在某一级桶的覆盖范围内就把它挂进那个桶。选级的依据不是看expires level算出来等于多少而是看它能不能在当前级内放下。这个规则保证了一个定时器始终被存放到能满足自身精度要求的最细粒度层级。但在实际阅读源码时我建议你留意timer_list结构体里还有两个容易被忽视的字段flags和idx。flags里除了用于RCU等场景的位标记还记录了定时器的CPU绑定信息TIMER_PINNED以及是否已经入队。idx则保存了当前所在桶的索引这个索引在删除定时器时非常关键——否则每次删除都要从第0级开始重新计算一次它应该在的位置。有了idxdetach_timer能在O(1)时间内把节点从链表上摘下来。这也是timer wheel性能好的另一个原因添加和删除都是O(1)或者O(level)而不是O(n)。如果你自己尝试画一下这个数据结构会发现它本质上是一个时间维度上的基数树——把expires这个32位值按位拆成5段每段作为哈希索引。这个设计的一个副作用是同一个桶里的定时器过期时间并不严格相等而是都落在桶所表示的时间跨度内。这也为后面到期但尚未执行的延迟现象埋下了伏笔。3. 轮转机制clk、vec和级间降级的完整流程搞清楚结构之后最核心的问题是定时器什么时候从高级别降落到低级别这背后的逻辑在__run_timers和run_timer_softirq里。过去在一个tick进来时内核会从第0级开始逐级检查但现在由于采用了级联设计逻辑可以简化很多。简化后的流程大概是这样的每次时钟tick触发run_timer_softirq软中断。把base-clk加1clk是长期维护的一个逻辑当前时间未必等于实时jiffies。检查当前clk在第0级对应的桶是否有定时器有则依次取出执行。当第0级的所有桶都走了一圈也就是256个tick轮子转了一整圈这时第1级会有一个桶被降级到第0级。降级的本质是把那一桶里的定时器全部重新计算索引分散挂到第0级对应的桶中。类似地第1级转完一圈第2级降级一个桶到第0级/第1级依此类推。这里面最容易被误解的是逐级降级到底发生在哪个时机。网上的文章说得含糊很容易让人误以为每次clk递增都要执行一次级联。实际上只有当某级的花名册roster指针走完一整圈时才会触发更高一级的级联操作。__run_timers里那个while (time_after_eq(jiffies, base-clk))的循环配合cascade逻辑保证了这种周期性。cascade这个函数名取得很形象水从高处往低处流定时器也像水一样从高级别桶流向低级别桶。它的源码实现是static int cascade(struct timer_base *base, struct timer_list *timer, unsigned int level) { struct hlist_head *tv base-vectors[level]; struct hlist_node *entry; struct timer_list *tmp; ... hlist_for_each_entry_safe(timer, tmp, tv index, entry) { hlist_del_init(timer-entry); internal_add_timer(base, timer); } ... }这里有个肉眼可见的性能成本当第1级的一个桶被降级到第0级时这个桶里的所有定时器都要重新internal_add_timer再计算一次哈希索引。如果某个桶里的定时器特别多cascade就会占用比较长的CPU时间。理论上一个恶意驱动可以创建大量短周期的定时器让它们都堆在同一桶里导致cascade时间显著拉长。不过正常驱动不会这么干因为定时器数量本身会受到系统内存和调用频率的限制。为了降低这种级联带来的延迟波动新版本内核引入了LVL_CLK_MASK等优化以及惰性降级不立刻把一个过期桶里的所有定时器级联到低级而是在collect_expired_timers阶段只摘取真正到期的那些定时器大部分情况下可以避免把整个桶重新散列。这个细节是看timer.c时最容易忽略的。另一个值得关注的是base-clk和jiffies之间的微妙关系。clk是内核定时器子系统的私有时钟通常等于jiffies但它的更新受软中断调度影响。也就是说软中断被延迟处理时clk会滞后于jiffies而__run_timers的while循环会尽量追赶在同一个软中断里处理多个tick的定时器。这时你观测到的现象就是明明定时器设的是10个jiffies后触发实际触发可能变成12个甚至20个jiffies之后。这引出了下一节要说的定时器精度话题。4. 定时器的延迟是feature不是bug为什么你等不到精准超时很多做驱动开发的人都碰到过这样的场景配置了一个1ms的周期定时器结果示波器量出来触发间隔是1.x毫秒甚至3毫秒于是怀疑是不是驱动写错了。其实内核定时器从来不做精确到点的保证。它承诺的只是至少不会比你要求的更早触发。这个语义叫deferrable可延迟对就是字面意思。原因有三层软中断的延迟定时器回调是在TIMER_SOFTIRQ上下文中执行的。如果当前CPU正忙或者软中断被硬中断屏蔽软中断的执行就会推迟。run_timer_softirq的调用时机由内核的irq_exit路径决定并不是tick中断一进来就立刻处理。没有到期即刻执行的硬性机制timer wheel在第0级桶的粒度是1个jiffy假设HZ1000。如果你在第10个jiffy挂一个定时器expires设为第11个jiffy它会在第11个jiffy的软中断中触发。但如果软中断在那一瞬间刚好被延迟表现就是晚到而非早到。内核保证它不会提前触发因为每次处理时都会检查time_before(expires, clk)这种时间比较。级联延迟高层的定时器降级时不是一个个算好精确时间散列到桶里而是带着一个桶的时间跨度整体下降。所以一个第3级的定时器在降级到第2级时它的精度就已经被抹平了——例如第3级一个桶跨度是1048576个jiffy约17分钟那这批定时器的实际触发时间可能相差很大。这就是为什么短周期定时器尽量别用大跨度的原因它们之间隔了几级精度被损耗掉了。在内核源码里专门为deferrable定时器做的处理是TIMER_DEFERRABLE标志位。这类定时器在CPU进入idle状态时不会触发从而避免把CPU从空闲唤醒。典型应用场景是网络栈中的TIME_WAIT清理等不那么紧急的任务。把这个标志理解成可以再等等你就明白了为什么timerfd在用户态设置超时时间时有时会比预期晚很多毫秒触发——这个时间差可能来自底层deferrable定时器。实际开发中我给出的建议是如果要求毫秒级以内的精度比如PWM波形控制、周期性数据采样不要用内核timer应该用hrtimer。用timer_list时把回调函数设计成幂等可重入的风格因为它可能重入比如在SMP上多个CPU同时调用同一个定时器回调如果该定时器设置了TIMER_PINNED则通常不会。不要在定时器回调里做耗时操作。定时器回调是在软中断上下文执行的同一个CPU上的所有定时器都共用这一个路径。一个回调耗时过长会导致后续所有定时器持续晚点。还有个小技巧如果你确实需要周期性任务不推荐用mod_timer在回调末尾重新挂载自己。看起来简单但它每次都得走一遍timer wheel的添加流程并且如果上一个实例还在运行mod_timer可能会被卡住。更稳的做法是用timer_reduce或者hrtimer的HRTIMER_MODE_REL模式从源头避免反复插入移除的开销。5. timer wheel的性能极限插入、删除、触发的最坏情况分析内核任何核心机制都逃不过最坏情况这三个字。timer wheel虽然平均时间复杂度低但有两个方面的性能需要特别关注哈希冲突和级联放大。先说哈希冲突。因为每个CPU的timer wheel是独立的不同CPU之间天然隔离冲突。但同一个CPU上如果大量定时器恰好落到同一个桶里比如你同时启动100个网络连接它们的超时时间都设为5秒在HZ250时第0级桶粒度是4ms第1级桶粒度是1秒5秒落在第1级桶的某个索引上这100个定时器会被串在一个链表上。触发时从链头走到链尾逐个执行回调。这不是灾难但会导致这批定时器互相拖慢。最坏情况发生在级联时的雪崩一个高层级桶里挂了几千个定时器降级瞬间把它们全部重新散列。cascade是串行完成的期间整个timer wheel的锁是持有的其他CPU访问不到这个timer_base考虑到每个CPU独立通常只有本CPU受影响。在内核里cascade函数体的循环对每个定时器都要调用一次internal_add_timer而internal_add_timer又要根据expires计算新索引。如果有一个驱动把几千个定时器设到完全相同的过期时间点级联那一瞬间的CPU开销会显著飙高。我做过一个测试在一块四核ARM平台上让一个驱动程序同时创建5000个timerexpires都指向同一个未来的tick。结果发现cascade阶段的软中断耗时能达到几百微秒虽然还不至于导致系统级卡顿但如果你正好在做声音采样或者低延迟控制这种尖峰是完全不可接受的。为了避免这个问题真实产品中往往会做定时器合并把多个相同过期时间的请求合并成一个定时器触发后统一处理。TCP协议栈就是这么干的——它维护一条early retransmit定时器而不是每个连接一个独立定时器。底层逻辑相同把大量短周期定时器变成少量中长周期定时器减少对timer wheel的压力。操作平均时间最坏时间备注添加定时器O(1)O(level)需级联时可能遍历层级删除定时器O(1)O(1)有idx时直接从链表摘除触发扫描每tick O(1)O(冲突桶大小)受同一桶链表长度影响级联O(桶内定时器数)O(桶内定时器数)可能成为延迟尖峰来源在工程上这些边的存在并不是bug而是投递快和执行准之间的权衡。如果你在意延迟峰值可以考虑把定时器分组管理关键业务用高精度定时器非关键业务合并到低频批量处理。这样可以把timer wheel的触发频率压低尖峰也会小得多。6. 实践排查用tracepoint和crash工具定位定时器问题光讲原理不给排查手段等于白讲。我在实际工作中确实遇到过几次和timer wheel相关的疑难杂症这里分享两个相对有价值的排查思路。第一个是用内建的tracepoint追踪定时器生命周期。内核在timer_start、timer_expire_entry、timer_expire_exit、timer_cancel等位置埋了tracepoint可以通过trace-cmd或者perf直接观测。比如你想知道某个驱动创建的定时器到底什么时候入队、什么时候触发、回调跑了多久可以这样perf record -e timer:timer_start -e timer:timer_expire_entry -e timer:timer_expire_exit -a sleep 5 perf script输出里能看到timer_list的地址、expires值、回调函数名以及回调开始和结束的时间戳。把时间戳相减就得到每次回调的实际执行时长。有一次我排查一个网卡驱动的收包超时问题就是通过这个tracepoint发现该驱动的定时器回调里居然做了mdio总线读写单次耗时都超过1毫秒导致整体收包延迟异常。定位后把mdio操作移到工作队列问题立刻消失。第二个排查手段是使用crash工具查看定时器的散落情况。如果系统出现了疑似定时器风暴的问题比如CPU soft lockupcrash进去后用timer命令列出所有定时器crash timer这个命令会把系统每个CPU上timer wheel里所有定时器按expires时间排序打出来。结合-t选项可以看到更详细的信息。如果发现某一个桶里的定时器数量上千就基本可以判定是哈希冲突严重或者某个驱动把大量定时器设到了同一个时间点。这类问题常见的根因有两类驱动程序用同一个timer_list结构体却连续多次mod_timer导致前一个回调还没执行新的又挂上去了最终在某次回调里出现数据竞争。回调函数内部调用del_timer_sync但该定时器又是在软中断里自删除自重新挂载的——del_timer_sync在中断上下文不能使用会触发BUG或者死锁。针对第二类我的建议是如果需要在定时器回调里重新调度用mod_timer就行如果需要在另一个上下文中取消定时器并等它跑完才用del_timer_sync。这两者的语义区分经常被忽略但恰恰是驱动稳定性的关键。7. 从5级到LVL新内核的timer wheel演进方向最后简单聊聊这个机制近几年的演进。老代码里tvec_base_s的写法是固定5级但后来为了支持更长的超时范围尤其是在休眠/挂起场景下内核改用了LVL_DEPTH宏把层级数做成可配置。你可以通过CONFIG_BASE_SMALL来压缩桶的数量这在高密度嵌入式环境里有用。CONFIG_BASE_SMALL这项在很多人眼里不起眼但我建议有极致性能需求的场景打开它做个基准测试。小于等于1的情况下第0级的桶数从256缩到32第1级及以上的桶数从64缩到16。带来的好处是cache footprint大幅降低但代价是哈希冲突变多。如果你的系统定时器数量不多打开它确实能减少内存占用和Cache Miss如果定时器成千上万就别开。另一个演进是timer_migration相关的优化。旧版内核里每CPU一个timer_base如果定时器在CPU A创建但到期时CPU A正在忙软中断的调度效率会受影响。新版本引入了TIMER_PINNED标志允许普通定时器在CPU之间迁移让负载均衡器把软中断搬到更空闲的CPU上处理。这也是为什么在新内核上perf观察到的软中断行为会和旧内核有明显差异。对于正在搭建嵌入式系统的开发者我的建议是别盲目追逐最新版。timer wheel这层如果没改好很容易引入回归。先摸清自己场景的定时器分布模型——是周期大量短定时器还是偶发少量长定时器——再决定要不要调整层级参数、要不要打开CONFIG_BASE_SMALL。内核的.config里关于timer的选项不多但每一个都值得认真评估。8. 我与timer wheel缠斗后的几点体会说起来timer wheel是我在内核源码里花时间最多、也最反直觉的模块之一。它说难不难——无非是一组哈希桶加若干级联规则但说简单也真不简单——任何一个小改动都可能牵动系统全局的定时精度和吞吐。我踩过最大的一个坑是在某个数据采集设备上为了让采样周期更精确我把驱动程序里所有定时器全部换成了hrtimer。结果虽然采样间隔稳定了系统整体负载却上升了十几个百分点原因就是hrtimer在每个tick之外还会额外触发大量高精度中断把这些中断累积起来反而拖垮了CPU。后来我又换回timer wheel只在最关键的一路采样上保留hrtimer两全其美。还有一次在产品调试时发现某个外设驱动的mod_timer调用频率特别高几乎每个数据包都触发一次。由于该驱动跑在中断上下文mod_timer本身要拿timer_base的锁同一CPU上其他定时器操作全被阻塞。那时还没意识到这是性能瓶颈后面看scheduling数据才恍然大悟——有些模块的性能事故不是算法本身慢而是锁竞争和Cache Miss造成的。如果你正打算深入读kernel/time/timer.c的源码我建议按这个顺序来先看timer_base和init_timer理清每个CPU的私有状态再看internal_add_timer确认层级计算和索引确定的逻辑接着看run_timer_softirq和__run_timers搞清楚软中断入口和过期处理流程最后再回头看cascade你会发现前面所有疑惑在这时全部串起来了。源码读起来确实有些绕但这套机制至今仍是Linux内核里最优雅、最高效的定时器实现之一。把它啃下来你对内核的时间感知能力会有质的提升也能在驱动开发时少走很多弯路。
Linux内核timer wheel机制详解：从数据结构到性能调优
1. 从tick到timer wheel内核定时器为什么要绕这么多弯很多人第一次看内核定时器相关代码时最大的困惑是timer_listmod_timerdel_timer这套接口明明用起来挺顺手为什么内核非要搞出一个叫timer wheel的东西从命名到数据结构都让人摸不着头脑。我在刚接触这部分源码时也有同样的疑问直到有一次用ftrace跟踪一个驱动程序的高频定时器超时分布才意识到这里头的复杂度远超直觉。先明确一个概念Linux内核里的定时器并不是到点自动执行一个函数这么简单。它的底层驱动来自硬件时钟中断而开发者见到的add_timer、mod_timer这类API都只是对内部timer wheel的封装。也就是说真正决定定时器性能、精度、扩展性的核心机制是timer wheel怎么保存、查找、触发这些定时器。而用户态的timerfd、epoll的超时、网络协议栈的TCP重传、块设备的I/O超时最终都会落到这一层。直接说结论timer wheel用的是多级哈希轮结构这也是名字里wheel轮的由来。内核默认是5级每一级是一个定长的数组每个数组元素挂一条定时器链表。低级轮负责近期的定时器粒度细高级轮负责远期定时器粒度粗。定时器到期后逐级降级到低级轮最终触发回调。这套做法本质上是在插入快和扫描快之间找了个工程平衡点——毕竟内核面对的定时器数量可能成千上万每个tick都从头到尾检查一遍所有定时器早就扛不住了。提示如果你只看过kernel/time/timer.c里add_timer的代码建议先从kernel/time/timer_list.c的输出对应着看这样对timer wheel的整体布局会更有画面感。这篇文章我不会把整份源码从头抄一遍而是挑几个真正重要的点逐一拆数据结构怎么组织、轮转的时机和逻辑是怎么衔接的、为什么会存在过期定时器延迟执行这种看起来违反直觉的现象以及在驱动开发里最容易踩哪些坑。最后再讲讲调试定时器相关问题时的经验和工具。2. timer wheel的数据结构与为什么是5级timer wheel的精髓全在kernel/time/timer.c里的struct timer_base以及tvec_base那套结构上。每个CPU都有一个独立的timer_base这样做的好处是定时器的添加、删除、触发都在本CPU上进行不需要加全局锁避免了多核竞争。这个设计在SMP普及的今天尤其重要因为定时器是内核里调用频率最高的机制之一任何一点锁竞争都会被放大。来看关键的层级定义#define TVN_BITS 6 #define TVR_BITS 8 #define TVN_SIZE (1 TVN_BITS) // 64 #define TVR_SIZE (1 TVR_BITS) // 256 #define TVN_MASK (TVN_SIZE - 1) #define TVR_MASK (TVR_SIZE - 1) struct timer_base { raw_spinlock_t lock; struct timer_list *running_timer; unsigned long clk; unsigned long next_expiry; ... struct hlist_head vectors[LVL_DEPTH][LVL_SIZE]; // 实际是5级数组 };第一个阵列level 0有256个桶每个桶对应1个jiffy的精度。后面每一级是64个桶分别对应256、16384、1048576、67108864个jiffy的范围。这里用LVL_DEPTH表示层级深度默认5LVL_SIZE表示每级的桶数量默认64。如果只算桶的总数是25664646464512个哈希桶看似不多但因为每级桶的跨度不同实际能覆盖的时间范围大得惊人一直到2^32个jiffy也就是大约497天假设HZ1000。也就是说mod_timer传一个很远很远的时间点也不会溢出这是老式的timer wheel按HZ范围硬编码所做不到的。层级间是怎么接上的呢关键在于LVL_START和LVL_SIZE的宏展开。内核通过lvls和level计算函数把一个expires值分解成层级数 偏移量static inline int calc_index(unsigned long expires, unsigned int lvl) { return (expires (LVL_SHIFT(lvl))) LVL_MASK; }LVL_SHIFT随层级线性增加第0级偏移是0第1级偏移是6因为第一级用6位索引64个桶第2级偏移是12依次类推。这个右移位与的过程本质上就是在做取模操作——只不过因为桶大小全是2的幂位运算比除法快得多。再仔细看这5级的有效时间范围分别是层级桶数量覆盖宽度时间表示范围HZ100002561 jiffy/桶0 ~ 255 ms164256 jiffy/桶256 ms ~ 16.384 s26416384 jiffy/桶16.384 s ~ 17.45 min3641048576 jiffy/桶17.45 min ~ 18.6 h46467108864 jiffy/桶18.6 h ~ 497 days有了这个表你再去看内核里__internal_add_timer的代码会发现它做的事情很简单从第0级开始找一旦发现expires能落在某一级桶的覆盖范围内就把它挂进那个桶。选级的依据不是看expires level算出来等于多少而是看它能不能在当前级内放下。这个规则保证了一个定时器始终被存放到能满足自身精度要求的最细粒度层级。但在实际阅读源码时我建议你留意timer_list结构体里还有两个容易被忽视的字段flags和idx。flags里除了用于RCU等场景的位标记还记录了定时器的CPU绑定信息TIMER_PINNED以及是否已经入队。idx则保存了当前所在桶的索引这个索引在删除定时器时非常关键——否则每次删除都要从第0级开始重新计算一次它应该在的位置。有了idxdetach_timer能在O(1)时间内把节点从链表上摘下来。这也是timer wheel性能好的另一个原因添加和删除都是O(1)或者O(level)而不是O(n)。如果你自己尝试画一下这个数据结构会发现它本质上是一个时间维度上的基数树——把expires这个32位值按位拆成5段每段作为哈希索引。这个设计的一个副作用是同一个桶里的定时器过期时间并不严格相等而是都落在桶所表示的时间跨度内。这也为后面到期但尚未执行的延迟现象埋下了伏笔。3. 轮转机制clk、vec和级间降级的完整流程搞清楚结构之后最核心的问题是定时器什么时候从高级别降落到低级别这背后的逻辑在__run_timers和run_timer_softirq里。过去在一个tick进来时内核会从第0级开始逐级检查但现在由于采用了级联设计逻辑可以简化很多。简化后的流程大概是这样的每次时钟tick触发run_timer_softirq软中断。把base-clk加1clk是长期维护的一个逻辑当前时间未必等于实时jiffies。检查当前clk在第0级对应的桶是否有定时器有则依次取出执行。当第0级的所有桶都走了一圈也就是256个tick轮子转了一整圈这时第1级会有一个桶被降级到第0级。降级的本质是把那一桶里的定时器全部重新计算索引分散挂到第0级对应的桶中。类似地第1级转完一圈第2级降级一个桶到第0级/第1级依此类推。这里面最容易被误解的是逐级降级到底发生在哪个时机。网上的文章说得含糊很容易让人误以为每次clk递增都要执行一次级联。实际上只有当某级的花名册roster指针走完一整圈时才会触发更高一级的级联操作。__run_timers里那个while (time_after_eq(jiffies, base-clk))的循环配合cascade逻辑保证了这种周期性。cascade这个函数名取得很形象水从高处往低处流定时器也像水一样从高级别桶流向低级别桶。它的源码实现是static int cascade(struct timer_base *base, struct timer_list *timer, unsigned int level) { struct hlist_head *tv base-vectors[level]; struct hlist_node *entry; struct timer_list *tmp; ... hlist_for_each_entry_safe(timer, tmp, tv index, entry) { hlist_del_init(timer-entry); internal_add_timer(base, timer); } ... }这里有个肉眼可见的性能成本当第1级的一个桶被降级到第0级时这个桶里的所有定时器都要重新internal_add_timer再计算一次哈希索引。如果某个桶里的定时器特别多cascade就会占用比较长的CPU时间。理论上一个恶意驱动可以创建大量短周期的定时器让它们都堆在同一桶里导致cascade时间显著拉长。不过正常驱动不会这么干因为定时器数量本身会受到系统内存和调用频率的限制。为了降低这种级联带来的延迟波动新版本内核引入了LVL_CLK_MASK等优化以及惰性降级不立刻把一个过期桶里的所有定时器级联到低级而是在collect_expired_timers阶段只摘取真正到期的那些定时器大部分情况下可以避免把整个桶重新散列。这个细节是看timer.c时最容易忽略的。另一个值得关注的是base-clk和jiffies之间的微妙关系。clk是内核定时器子系统的私有时钟通常等于jiffies但它的更新受软中断调度影响。也就是说软中断被延迟处理时clk会滞后于jiffies而__run_timers的while循环会尽量追赶在同一个软中断里处理多个tick的定时器。这时你观测到的现象就是明明定时器设的是10个jiffies后触发实际触发可能变成12个甚至20个jiffies之后。这引出了下一节要说的定时器精度话题。4. 定时器的延迟是feature不是bug为什么你等不到精准超时很多做驱动开发的人都碰到过这样的场景配置了一个1ms的周期定时器结果示波器量出来触发间隔是1.x毫秒甚至3毫秒于是怀疑是不是驱动写错了。其实内核定时器从来不做精确到点的保证。它承诺的只是至少不会比你要求的更早触发。这个语义叫deferrable可延迟对就是字面意思。原因有三层软中断的延迟定时器回调是在TIMER_SOFTIRQ上下文中执行的。如果当前CPU正忙或者软中断被硬中断屏蔽软中断的执行就会推迟。run_timer_softirq的调用时机由内核的irq_exit路径决定并不是tick中断一进来就立刻处理。没有到期即刻执行的硬性机制timer wheel在第0级桶的粒度是1个jiffy假设HZ1000。如果你在第10个jiffy挂一个定时器expires设为第11个jiffy它会在第11个jiffy的软中断中触发。但如果软中断在那一瞬间刚好被延迟表现就是晚到而非早到。内核保证它不会提前触发因为每次处理时都会检查time_before(expires, clk)这种时间比较。级联延迟高层的定时器降级时不是一个个算好精确时间散列到桶里而是带着一个桶的时间跨度整体下降。所以一个第3级的定时器在降级到第2级时它的精度就已经被抹平了——例如第3级一个桶跨度是1048576个jiffy约17分钟那这批定时器的实际触发时间可能相差很大。这就是为什么短周期定时器尽量别用大跨度的原因它们之间隔了几级精度被损耗掉了。在内核源码里专门为deferrable定时器做的处理是TIMER_DEFERRABLE标志位。这类定时器在CPU进入idle状态时不会触发从而避免把CPU从空闲唤醒。典型应用场景是网络栈中的TIME_WAIT清理等不那么紧急的任务。把这个标志理解成可以再等等你就明白了为什么timerfd在用户态设置超时时间时有时会比预期晚很多毫秒触发——这个时间差可能来自底层deferrable定时器。实际开发中我给出的建议是如果要求毫秒级以内的精度比如PWM波形控制、周期性数据采样不要用内核timer应该用hrtimer。用timer_list时把回调函数设计成幂等可重入的风格因为它可能重入比如在SMP上多个CPU同时调用同一个定时器回调如果该定时器设置了TIMER_PINNED则通常不会。不要在定时器回调里做耗时操作。定时器回调是在软中断上下文执行的同一个CPU上的所有定时器都共用这一个路径。一个回调耗时过长会导致后续所有定时器持续晚点。还有个小技巧如果你确实需要周期性任务不推荐用mod_timer在回调末尾重新挂载自己。看起来简单但它每次都得走一遍timer wheel的添加流程并且如果上一个实例还在运行mod_timer可能会被卡住。更稳的做法是用timer_reduce或者hrtimer的HRTIMER_MODE_REL模式从源头避免反复插入移除的开销。5. timer wheel的性能极限插入、删除、触发的最坏情况分析内核任何核心机制都逃不过最坏情况这三个字。timer wheel虽然平均时间复杂度低但有两个方面的性能需要特别关注哈希冲突和级联放大。先说哈希冲突。因为每个CPU的timer wheel是独立的不同CPU之间天然隔离冲突。但同一个CPU上如果大量定时器恰好落到同一个桶里比如你同时启动100个网络连接它们的超时时间都设为5秒在HZ250时第0级桶粒度是4ms第1级桶粒度是1秒5秒落在第1级桶的某个索引上这100个定时器会被串在一个链表上。触发时从链头走到链尾逐个执行回调。这不是灾难但会导致这批定时器互相拖慢。最坏情况发生在级联时的雪崩一个高层级桶里挂了几千个定时器降级瞬间把它们全部重新散列。cascade是串行完成的期间整个timer wheel的锁是持有的其他CPU访问不到这个timer_base考虑到每个CPU独立通常只有本CPU受影响。在内核里cascade函数体的循环对每个定时器都要调用一次internal_add_timer而internal_add_timer又要根据expires计算新索引。如果有一个驱动把几千个定时器设到完全相同的过期时间点级联那一瞬间的CPU开销会显著飙高。我做过一个测试在一块四核ARM平台上让一个驱动程序同时创建5000个timerexpires都指向同一个未来的tick。结果发现cascade阶段的软中断耗时能达到几百微秒虽然还不至于导致系统级卡顿但如果你正好在做声音采样或者低延迟控制这种尖峰是完全不可接受的。为了避免这个问题真实产品中往往会做定时器合并把多个相同过期时间的请求合并成一个定时器触发后统一处理。TCP协议栈就是这么干的——它维护一条early retransmit定时器而不是每个连接一个独立定时器。底层逻辑相同把大量短周期定时器变成少量中长周期定时器减少对timer wheel的压力。操作平均时间最坏时间备注添加定时器O(1)O(level)需级联时可能遍历层级删除定时器O(1)O(1)有idx时直接从链表摘除触发扫描每tick O(1)O(冲突桶大小)受同一桶链表长度影响级联O(桶内定时器数)O(桶内定时器数)可能成为延迟尖峰来源在工程上这些边的存在并不是bug而是投递快和执行准之间的权衡。如果你在意延迟峰值可以考虑把定时器分组管理关键业务用高精度定时器非关键业务合并到低频批量处理。这样可以把timer wheel的触发频率压低尖峰也会小得多。6. 实践排查用tracepoint和crash工具定位定时器问题光讲原理不给排查手段等于白讲。我在实际工作中确实遇到过几次和timer wheel相关的疑难杂症这里分享两个相对有价值的排查思路。第一个是用内建的tracepoint追踪定时器生命周期。内核在timer_start、timer_expire_entry、timer_expire_exit、timer_cancel等位置埋了tracepoint可以通过trace-cmd或者perf直接观测。比如你想知道某个驱动创建的定时器到底什么时候入队、什么时候触发、回调跑了多久可以这样perf record -e timer:timer_start -e timer:timer_expire_entry -e timer:timer_expire_exit -a sleep 5 perf script输出里能看到timer_list的地址、expires值、回调函数名以及回调开始和结束的时间戳。把时间戳相减就得到每次回调的实际执行时长。有一次我排查一个网卡驱动的收包超时问题就是通过这个tracepoint发现该驱动的定时器回调里居然做了mdio总线读写单次耗时都超过1毫秒导致整体收包延迟异常。定位后把mdio操作移到工作队列问题立刻消失。第二个排查手段是使用crash工具查看定时器的散落情况。如果系统出现了疑似定时器风暴的问题比如CPU soft lockupcrash进去后用timer命令列出所有定时器crash timer这个命令会把系统每个CPU上timer wheel里所有定时器按expires时间排序打出来。结合-t选项可以看到更详细的信息。如果发现某一个桶里的定时器数量上千就基本可以判定是哈希冲突严重或者某个驱动把大量定时器设到了同一个时间点。这类问题常见的根因有两类驱动程序用同一个timer_list结构体却连续多次mod_timer导致前一个回调还没执行新的又挂上去了最终在某次回调里出现数据竞争。回调函数内部调用del_timer_sync但该定时器又是在软中断里自删除自重新挂载的——del_timer_sync在中断上下文不能使用会触发BUG或者死锁。针对第二类我的建议是如果需要在定时器回调里重新调度用mod_timer就行如果需要在另一个上下文中取消定时器并等它跑完才用del_timer_sync。这两者的语义区分经常被忽略但恰恰是驱动稳定性的关键。7. 从5级到LVL新内核的timer wheel演进方向最后简单聊聊这个机制近几年的演进。老代码里tvec_base_s的写法是固定5级但后来为了支持更长的超时范围尤其是在休眠/挂起场景下内核改用了LVL_DEPTH宏把层级数做成可配置。你可以通过CONFIG_BASE_SMALL来压缩桶的数量这在高密度嵌入式环境里有用。CONFIG_BASE_SMALL这项在很多人眼里不起眼但我建议有极致性能需求的场景打开它做个基准测试。小于等于1的情况下第0级的桶数从256缩到32第1级及以上的桶数从64缩到16。带来的好处是cache footprint大幅降低但代价是哈希冲突变多。如果你的系统定时器数量不多打开它确实能减少内存占用和Cache Miss如果定时器成千上万就别开。另一个演进是timer_migration相关的优化。旧版内核里每CPU一个timer_base如果定时器在CPU A创建但到期时CPU A正在忙软中断的调度效率会受影响。新版本引入了TIMER_PINNED标志允许普通定时器在CPU之间迁移让负载均衡器把软中断搬到更空闲的CPU上处理。这也是为什么在新内核上perf观察到的软中断行为会和旧内核有明显差异。对于正在搭建嵌入式系统的开发者我的建议是别盲目追逐最新版。timer wheel这层如果没改好很容易引入回归。先摸清自己场景的定时器分布模型——是周期大量短定时器还是偶发少量长定时器——再决定要不要调整层级参数、要不要打开CONFIG_BASE_SMALL。内核的.config里关于timer的选项不多但每一个都值得认真评估。8. 我与timer wheel缠斗后的几点体会说起来timer wheel是我在内核源码里花时间最多、也最反直觉的模块之一。它说难不难——无非是一组哈希桶加若干级联规则但说简单也真不简单——任何一个小改动都可能牵动系统全局的定时精度和吞吐。我踩过最大的一个坑是在某个数据采集设备上为了让采样周期更精确我把驱动程序里所有定时器全部换成了hrtimer。结果虽然采样间隔稳定了系统整体负载却上升了十几个百分点原因就是hrtimer在每个tick之外还会额外触发大量高精度中断把这些中断累积起来反而拖垮了CPU。后来我又换回timer wheel只在最关键的一路采样上保留hrtimer两全其美。还有一次在产品调试时发现某个外设驱动的mod_timer调用频率特别高几乎每个数据包都触发一次。由于该驱动跑在中断上下文mod_timer本身要拿timer_base的锁同一CPU上其他定时器操作全被阻塞。那时还没意识到这是性能瓶颈后面看scheduling数据才恍然大悟——有些模块的性能事故不是算法本身慢而是锁竞争和Cache Miss造成的。如果你正打算深入读kernel/time/timer.c的源码我建议按这个顺序来先看timer_base和init_timer理清每个CPU的私有状态再看internal_add_timer确认层级计算和索引确定的逻辑接着看run_timer_softirq和__run_timers搞清楚软中断入口和过期处理流程最后再回头看cascade你会发现前面所有疑惑在这时全部串起来了。源码读起来确实有些绕但这套机制至今仍是Linux内核里最优雅、最高效的定时器实现之一。把它啃下来你对内核的时间感知能力会有质的提升也能在驱动开发时少走很多弯路。
