# linux-sides-Timers and time management in the Linux kernel. Part 4. Date: 2019-10-25 这篇文章 [Timers and time management in the Linux kernel. Part 4.](https://0xax.gitbooks.io/linux-insides/Timers/linux-timers-4.html) 是出自 [linux-insides](https://0xax.gitbooks.io/linux-insides/content/)一书中 [Timers and time management](https://github.com/0xAX/linux-insides/tree/master/Timers) 章节 [Introduction to timers](https://github.com/0xAX/linux-insides/blob/master/Timers/linux-timers-4.md) > _内核版本比对5.4-rc2 进行了相关调整, 增加相关备注_ # Linux内核中的定时器和时间管理.Part 4. ## 定时器 这是[本章](https://0xax.gitbooks.io/linux-insides/content/Timers/index.html)的第四部分，通过[前一部分](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-3.html)描述了Linux内核中与计时器和时间管理相关的内容，我们知道Linux内核中的`tick broadcase`框架和`NO_HZ`模式。我们将在这一部分继续研究与Linux内核中与时间管理相关的内容，并熟悉Linux内核中的另一个概念-`timers`。在研究Linux内核中的计时器之前，我们必须学习一些有关此概念的理论。请注意，我们将在本部分中考虑软件计时器。 Linux内核提供了`软件计时器`的概念，以允许将来可以调用内核功能。计时器在Linux内核中被广泛使用。例如，查看源代码文件 [net/netfilter/ipset/ip\_set\_list\_set.c](https://github.com/torvalds/linux/blob/master/net/netfilter/ipset/ip_set_list_set.c)。此源代码文件提供了用于管理[IP](https://en.wikipedia.org/wiki/Internet_Protocol)地址组的框架的实现。 在 `list_set` 结构中包含了 `time_list` 变量 `gc` : ```C struct list_set { ... struct timer_list gc; ... }; ``` 并非gc字段具有timer\_list类型。 在[include/linux/timer.h](https://github.com/torvalds/linux/blob/master/include/linux/timer.h) 头文件中定义的结构，该结构的要点是存储 Linux内核中的`动态`计时器。 实际上，Linux内核提供了两种类型的计时器，称为动态计时器和间隔计时器。 内核使用第一种计时器，用户模式使用第二种计时器。`timer_list`结构包含实际的`dynamic`定时器。 在我们的示例中，`list_set`包含`gc`计时器代表垃圾收集的计时器。 该计时器将在`list_set_gc_init`函数中初始化： ```C static void list_set_gc_init(struct ip_set *set, void (*gc)(struct timer_list *t)) { struct list_set *map = set->data; timer_setup(&map->gc, gc, 0); mod_timer(&map->gc, jiffies + IPSET_GC_PERIOD(set->timeout) * HZ); } ``` > _按照现有版本进行调整_ 由gc指针指向的函数,将在超时时间等于map->gc.expires后被调用。 > `timer_setup`设置gc指向的函数， `mod_timer`设置超时时间 好的，我们不会使用[netfilter](https://en.wikipedia.org/wiki/Netfilter)深入研究此示例，因为本章与[network](https://en.wikipedia.org/wiki/Computer_network)部分的内容无关。但是我们看到计时器在Linux内核中得到了广泛使用，并且了解到它们代表了可以在将来调用功能的概念。 现在，让我们继续研究Linux内核的源代码，该代码与计时器和时间管理的内容有关，就像我们在前几章中所做的那样。 ## 动态计数器介绍 正如我已经写过的，我们在之前的[part](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-3.html)中了解了`tick broadcast`框架和`NO_HZ`模式。 它们将通过调用`tick_init`函数在[init/ main.c](https://github.com/torvalds/linux/blob/master/init/main.c)源代码文件中初始化。 如果我们查看此源代码文件，将看到下一次与管理相关的功能是： ```C init_timers(); ``` `init_timers`函数定义在 [kernel/time/timer.c](https://github.com/torvalds/linux/blob/master/kernel/time/timer.c)源码文件中: ```C void __init init_timers(void) { init_timer_cpus(); open_softirq(TIMER_SOFTIRQ, run_timer_softirq); } ``` > _已按照新版本更新_ 让我们看一下每个函数的实现。 第一个函数 `init_timer_cpus` 同样定义在文件[kernel/time/timer.c](https://github.com/torvalds/linux/blob/master/kernel/time/timer.c) 源码文件中，处理系统每一个`可能`处理器: ```C static void __init init_timer_cpus(void) { int cpu; for_each_possible_cpu(cpu) init_timer_cpu(cpu); } ``` 如果您不知道或不记得它是什么`可能`CPU，则可以阅读[part](https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-2.html)其中描述了Linux内核中的 `cpumask`概念。 简而言之，`可能`处理器是可以在系统生命周期内随时插入的处理器。 `init_timer_cpu`函数为我们完成了主要工作，即它为每个处理器执行`tvec_base`结构的初始化。 在[kernel/time/timer.c](https://github.com/torvalds/linux/blob/master/kernel/time/timer.c)源代码文件中定义的结构，存储与某个处理器的`动态`计时器相关的数据。 让我们看一下这个结构的定义： ```C struct timer_base { raw_spinlock_t lock; struct timer_list *running_timer; #ifdef CONFIG_PREEMPT_RT spinlock_t expiry_lock; atomic_t timer_waiters; #endif unsigned long clk; unsigned long next_expiry; unsigned int cpu; bool is_idle; bool must_forward_clk; DECLARE_BITMAP(pending_map, WHEEL_SIZE); struct hlist_head vectors[WHEEL_SIZE]; } ____cacheline_aligned; ``` `timer_base`结构包含以下字段： - `lock`: 用于保护`timer_base`; - `running_timer`: 指向特定处理器的当前运行计时器; - `clk`: 表示定时器经过jiffies, 判断时候已过期; - `next_ecpiry`: 最早的超时时间; - `cpu`: 该timer所属于的cpu; - `is_idle`: 是否处于空闲状态; - `DECLARE_BITMAP(pending_map, WHEEL_SIZE)`: 如果某个链表中有timer，则对应bit被设置为 1; - `vectors`: 维护所有的链表 > [Linux 时间系统分析](https://www.binss.me/blog/linux-time-system-analysis/)，对新版本的结构说了说明. [timers: Give a few structs and members proper names](https://github.com/torvalds/linux/commit/494af3ed7848de08640d98ee5aff57a45c137c3c#diff-38c4d856190bcc4ed0d9d56bc9026f9a) 结构体调整记录commits. * * * - 现代时间轮与经典时间轮 1. 经典时间轮 之前的版本tvec\_base,使用的是经典的时间轮, 存在tv1 tv2 tv3 tv4 tv5 5个时间轮\* tvec\_base结构的最后五个字段代表动态计时器列表。 第一个`tv1`字段具有： `tv1`是一个数组，可以包含64个或256个元素，其中每个元素代表一个动态计时器，该计时器将在下一个`255个`系统计时器中断(jiffies)中衰减。 接下来的三个字段：`tv2`,`tv3`和`tv4`也是具有动态计时器的列表，但是它们存储了动态计时器，这些动态计时器会衰减下一个`2 ^ 14-1`，`2 ^ 20-1`和`2 ^ 26`。 最后的`tv5`字段表示列表，该列表存储具有较大到期时间的动态计时器。 | tvec | jiffies | | --- | --- | | tv1 | 0-255(2^8) | | tv2 | 256--16383(2^14) | | tv3 | 16384--1048575(2^20) | | tv4 | 1048576--67108863(2^26) | | tv5 | 67108864--4294967295(2^32) | 通过`internal_add_timer`:计算定时器与当前jiffies差值, `cacade`；迁移数组 tv5->tv4->tv3->tv2->tv1，由于jiffies在递增， tv5链表中的定时器会逐步迁移到tv1,并完成执行. 1. 现代时间轮 ```C * HZ 1000 steps * Level Offset Granularity Range * 0 0 1 ms 0 ms - 63 ms * 1 64 8 ms 64 ms - 511 ms * 2 128 64 ms 512 ms - 4095 ms (512ms - ~4s) * 3 192 512 ms 4096 ms - 32767 ms (~4s - ~32s) * 4 256 4096 ms (~4s) 32768 ms - 262143 ms (~32s - ~4m) * 5 320 32768 ms (~32s) 262144 ms - 2097151 ms (~4m - ~34m) * 6 384 262144 ms (~4m) 2097152 ms - 16777215 ms (~34m - ~4h) * 7 448 2097152 ms (~34m) 16777216 ms - 134217727 ms (~4h - ~1d) * 8 512 16777216 ms (~4h) 134217728 ms - 1073741822 ms (~1d - ~12d) ``` 每层的固定的间隔时间offset， 每层的间隔时间不同, 定时进行扫描, 由于时间固定所以可以直接定位 `calc_index` * * * 因此，现在我们看到了`timer_base`结构及其字段说明，我们可以看一下`init_timer_cpu`函数的实现。 正如我已经写过的，此函数在 [kernel/time/timer.c](https://github.com/torvalds/linux/blob/master/kernel/time/timer.c)源代码文件中定义并执行初始化`timer_base`的： ```C static void __init init_timer_cpu(int cpu) { struct timer_base *base; int i; for (i = 0; i < NR_BASES; i++) { base = per_cpu_ptr(&timer_bases[i], cpu); base->cpu = cpu; raw_spin_lock_init(&base->lock); base->clk = jiffies; timer_base_init_expiry_lock(base); } } ``` `timer_bases`是一个 [per-cpu](https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-1.html)变量，该变量代表对于给定处理器指定动态计时器的主要数据结构。 `per-cpu`变量在同一源代码文件中定义： ```C static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]); ``` 首先，我们将给定处理器的`timer_bases`的地址获取到`base`变量，并在获取时，开始在init\_timer\_cpu函数中初始化一些`timer_base`字段。 在使用[jiffies](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-1.html)和`可能`的处理器编号初始化`per-cpu`动态计时器并中初始化`timer_base`的`lock`[spinlock](https://en.wikipedia.org/wiki/Spinlock), 通过`init_timer_cpus`完成相关`可能`cpu的处理: ```C static void __init init_timer_cpus(void) { int cpu; for_each_possible_cpu(cpu) init_timer_cpu(cpu); } ``` 初始化后的下一步是调用timer\_register\_cpu\_notifier函数。 此功能取决于`CONFIG_HOTPLUG_CPU`内核配置选项，该选项可支持Linux内核中的[hotplug](https://en.wikipedia.org/wiki/Hot_swapping)处理器。 当处理器将在逻辑上脱机时，如何进行处理: ```C #ifdef CONFIG_HOTPLUG_CPU int timers_prepare_cpu(unsigned int cpu) { struct timer_base *base; int b; for (b = 0; b < NR_BASES; b++) { base = per_cpu_ptr(&timer_bases[b], cpu); base->clk = jiffies; base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA; base->is_idle = false; base->must_forward_clk = true; } return 0; } int timers_dead_cpu(unsigned int cpu) { struct timer_base *old_base; struct timer_base *new_base; int b, i; BUG_ON(cpu_online(cpu)); for (b = 0; b < NR_BASES; b++) { old_base = per_cpu_ptr(&timer_bases[b], cpu); new_base = get_cpu_ptr(&timer_bases[b]); /* * The caller is globally serialized and nobody else * takes two locks at once, deadlock is not possible. */ raw_spin_lock_irq(&new_base->lock); raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING); /* * The current CPUs base clock might be stale. Update it * before moving the timers over. */ forward_timer_base(new_base); BUG_ON(old_base->running_timer); for (i = 0; i < WHEEL_SIZE; i++) migrate_timer_list(new_base, old_base->vectors + i); raw_spin_unlock(&old_base->lock); raw_spin_unlock_irq(&new_base->lock); put_cpu_ptr(&timer_bases); } return 0; } #endif ``` 本章将不会描述Linux内核源代码中与`hotplug`相关的事件，但是如果您对此事感兴趣可以在 [kernel/time/timer.c](https://github.com/torvalds/linux/blob/master/kernel/time/timer.c) 源代码文件。 ```C static void migrate_timer_list(struct timer_base *new_base, struct hlist_head *head) { struct timer_list *timer; int cpu = new_base->cpu; while (!hlist_empty(head)) { timer = hlist_entry(head->first, struct timer_list, entry); detach_timer(timer, false); timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu; internal_add_timer(new_base, timer); } } ``` 在[kernel/cpu.c](https://github.com/torvalds/linux/blob/master/kernel/cpu.c)中可以看到项目cpu状态及处理函数的定义: > _这部分还不太了待更新_ ```C [CPUHP_TIMERS_PREPARE] = { .name = "timers:prepare", .startup.single = timers_prepare_cpu, .teardown.single = timers_dead_cpu, }, ``` `init_timers` 最后一个步骤调用如下: ```C open_softirq(TIMER_SOFTIRQ, run_timer_softirq); ``` 如果您已阅读有关中断的第九部分，则可能已经熟悉open\_softirq函数。和Linux内核中的中断处理。简而言之，[kernel/softirq.c](https://github.com/torvalds/linux/blob/master/kernel/softirq.c)源代码文件中定义的`open_softirq`函数会执行`中断延迟处理`程序。 在我们的例子中， `中断延迟函数`(中断触发函数)是`run_timer_softirq`函数，它将在`do_IRQ` 函数,定义见[arch/x86/kernel/irq.c](https://github.com/torvalds/linux/blob/master/arch/x86/kernel/irq.c)。该功能的重点是处理软件动态计时器。在硬件计时器中断处理期间，Linux内核不会执行此操作，因为这是耗时的操作。 > _触发软中断时的回调函数_ 让我们看一下`run_timer_softirq`函数的实现： ```C // This function runs timers and the timer-tq in bottom half context. static __latent_entropy void run_timer_softirq(struct softirq_action *h) { struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]); __run_timers(base); if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && base->nohz_active) __run_timers(this_cpu_ptr(&timer_bases[BASE_DEF])); } ``` 可以看到`run_timer_softirq`对普通`base`和`nohz`的`base`调用了 `__run_timers` ```C /** * __run_timers - run all expired timers (if any) on this CPU. * @base: the timer vector to be processed. */ static inline void __run_timers(struct timer_base *base) { struct hlist_head heads[LVL_DEPTH]; int levels; if (!time_after_eq(jiffies, base->clk)) return; raw_spin_lock_irq(&base->lock); while (time_after_eq(jiffies, base->clk)) { levels = collect_expired_timers(base, heads); base->clk++; while (levels--) expire_timers(base, heads + levels); } base->running_timer = NULL; raw_spin_unlock_irq(&base->lock); } ``` 在\_\_run\_timers函数中，我们为当前处理器获取了一个动态定时器，并比较了[jiffies](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-1.html)，, 这里的比较方法调用[include/linux/jiffies.h](https://github.com//torvalds/linux/blob/master/include/linux/jiffies.h)中定义的`time_after_eq`宏: ```C #define time_after_eq(a,b) \ (typecheck(unsigned long, a) && \ typecheck(unsigned long, b) && \ ((long)((a) - (b)) >= 0)) ``` 如果`jiffies`小于定时器时间，那么返回，否则 调用`collect_expired_timers` ```C static int collect_expired_timers(struct timer_base *base, struct hlist_head *heads) { /* * NOHZ optimization. After a long idle sleep we need to forward the * base to current jiffies. Avoid a loop by searching the bitfield for * the next expiring timer. */ if ((long)(jiffies - base->clk) > 2) { unsigned long next = __next_timer_interrupt(base); /* * If the next timer is ahead of time forward to current * jiffies, otherwise forward to the next expiry time: */ if (time_after(next, jiffies)) { /* The call site will increment clock! */ base->clk = jiffies - 1; return 0; } base->clk = next; } return __collect_expired_timers(base, heads); } static int __collect_expired_timers(struct timer_base *base, struct hlist_head *heads) { unsigned long clk = base->clk; struct hlist_head *vec; int i, levels = 0; unsigned int idx; for (i = 0; i < LVL_DEPTH; i++) { idx = (clk & LVL_MASK) + i * LVL_SIZE; if (__test_and_clear_bit(idx, base->pending_map)) { vec = base->vectors + idx; hlist_move_list(vec, heads++); levels++; } /* Is it time to look at the next level? */ if (clk & LVL_CLK_MASK) break; /* Shift clock for the next level granularity */ clk >>= LVL_CLK_SHIFT; } return levels; } ``` 在各 level 中查找 base->clk 时刻时超时的 timer，将它们添加到 heads 的对应链表中。返回超时的最高 level, 由于位置固定使用位图方式快速的进行定位; 正如我刚才所写，`__run_timers`函数为给定处理器运行所有过期的计时器。 该功能从获取timer\_base的锁开始，以保护timer\_base的结构 ```C static inline void __run_timers(struct timer_base *base) { ... raw_spin_lock_irq(&base->lock); ... raw_spin_unlock_irq(&base->lock); } ``` 之后，它开始循环，而`base->clk`将不大于`jiffies`。 ```C while (time_after_eq(jiffies, base->clk)) { ... ... ... ``` 我们可以在循环中找到许多不同的操作，但要点是找到过期的计时器并调用延迟的函数。 首先，我们需要计算列表的`idx`，该列表存储要使用以下表达式处理的`i`层计时器： ```C idx = (clk & LVL_MASK) + i * LVL_SIZE; ``` 通过位图操作就能判断是否存在相关`timer` ```C if (__test_and_clear_bit(idx, base->pending_map)) { ``` 然后取下满足条件的timers放到heads中: ```C vec = base->vectors + idx; hlist_move_list(vec, heads++); levels++; ``` 之后增加`base->clk++;` ```C base->clk++; ``` 最后在 `expire_timers`中可以看到通过调用`call_timer_fn`调用了相关回调函数; ```C static void expire_timers(struct timer_base *base, struct hlist_head *head) { while (!hlist_empty(head)) { struct timer_list *timer; void (*fn)(unsigned long); unsigned long data; timer = hlist_entry(head->first, struct timer_list, entry); base->running_timer = timer; detach_timer(timer, true); fn = timer->function; data = timer->data; if (timer->flags & TIMER_IRQSAFE) { raw_spin_unlock(&base->lock); call_timer_fn(timer, fn, data); raw_spin_lock(&base->lock); } else { raw_spin_unlock_irq(&base->lock); call_timer_fn(timer, fn, data); raw_spin_lock_irq(&base->lock); } } } ``` `call_timer_fn` 函数调用了指定的函数 ```C static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long), unsigned long data) { ... ... ... fn(data); ... ... ... } ``` 就这样。 从现在开始，Linux内核就具有用于`动态计时器`的基础结构。 我们不会深入探讨这个有趣的主题。 正如我已经写过的，`timers`是Linux内核中的[widely](http://lxr.free-electrons.com/ident?i=timer_list)使用的这个概念, 但是没有介绍这些东西如何实现和如何工作。 但是现在我们知道了这个概念，为什么Linux内核需要它以及围绕它的一些数据结构。 现在让我们看看Linux内核中`动态计时器`的用法。 ## 动态定时器的用法 如您已经注意到的，如果Linux内核提供了一个概念，那么它也提供了用于管理该概念的API，并且`动态计时器`概念在这里也不例外。要在Linux内核代码中使用计时器，我们必须定义一个带有`timer_list`类型的变量。我们可以通过两种方式初始化我们的`timer_list`结构。第一种是使用[include/linux/timer.h](https://github.com/torvalds/linux/blob/master/include/linux/timer.h)头文件中定义的`timer_setup`宏。 ： 准备一个定时器使用`timer_setup`: ```C #define timer_setup(timer, callback, flags) \ __init_timer((timer), (callback), (flags)) #define __init_timer(_timer, _fn, _flags) \ init_timer_key((_timer), (_fn), (_flags), NULL, NULL) #define __init_timer_on_stack(_timer, _fn, _flags) \ init_timer_on_stack_key((_timer), (_fn), (_flags), NULL, NULL) ``` `init_timer_key` 是这个样子: ```C static void do_init_timer(struct timer_list *timer, void (*func)(struct timer_list *), unsigned int flags, const char *name, struct lock_class_key *key) { timer->entry.pprev = NULL; timer->function = func; timer->flags = flags | raw_smp_processor_id(); lockdep_init_map(&timer->lockdep_map, name, key, 0); } ``` 另外一个方法是初始化: ```C #define __TIMER_INITIALIZER(_function, _flags) { \ .entry = { .next = TIMER_ENTRY_STATIC }, \ .function = (_function), \ .flags = (_flags), \ __TIMER_LOCKDEP_MAP_INITIALIZER( \ __FILE__ ":" __stringify(__LINE__)) \ } #define DEFINE_TIMER(_name, _function) \ struct timer_list _name = \ __TIMER_INITIALIZER(_function, 0) ``` 宏定义初始化了`timer_list`结构 动态定时器被初始话成功了后， 可以用下面方法开始一个`定时器`： ```C void add_timer(struct timer_list * timer); void add_timer_on(struct timer_list *timer, int cpu); ``` 用下面的函数停止一个定时器: ```C int del_timer(struct timer_list * timer); ``` ## 小结 这是本章第四部分的结尾，它描述了Linux内核中与计时器和计时器管理相关的内容。在上一部分中，我们熟悉了两个新概念：`tick broadcast`框架和`NO_HZ`模式。在这一部分中，我们继续研究与时间管理相关的内容，并熟悉新概念-动态计时器或软件计时器。在本部分中，我们没有看到“动态计时器”管理代码的详细实现，但是看到了围绕此概念的数据结构和API。 在下一部分中，我们将继续研究Linux内核中与计时器管理相关的内容，并为我们看到新的概念-“计时器”。 如果您有任何疑问或建议，请随时在Twitter \[0xAX\]（[https://twitter.com/0xAX）上ping我，给我发电子邮件（anotherworldofworld@gmail.com）或直接创建\[issue\]（https](https://twitter.com/0xAX）上ping我，给我发电子邮件（anotherworldofworld@gmail.com）或直接创建[issue]（https)： //github.com/0xAX/linux-insides/issues/new）。 **请注意，英语不是我的母语，对于给您带来的不便，我深表歉意。如果发现任何错误，请将PR发送给\[linux-insides\]（[https://github.com/0xAX/linux-insides](https://github.com/0xAX/linux-insides)）。** ## 相关链接 - [IP](https://en.wikipedia.org/wiki/Internet_Protocol) - [netfilter](https://en.wikipedia.org/wiki/Netfilter) - [network](https://en.wikipedia.org/wiki/Computer_network) - [cpumask](https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-2.html) - [interrupt](https://en.wikipedia.org/wiki/Interrupt) - [jiffies](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-1.html) - [per-cpu](https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-1.html) - [spinlock](https://en.wikipedia.org/wiki/Spinlock) - [procfs](https://en.wikipedia.org/wiki/Procfs) - [previous part](https://0xax.gitbooks.io/linux-insides/content/Timers/linux-timers-3.html)