这篇文章 Timers and time management in the Linux kernel. Part 4. 是出自 linux-insides一书中 Timers and time management 章节 Introduction to timers

内核版本比对5.4-rc2 进行了相关调整, 增加相关备注

Linux内核中的定时器和时间管理.Part 4.

定时器

这是本章的第四部分，通过前一部分描述了Linux内核中与计时器和时间管理相关的内容，我们知道Linux内核中的tick broadcase框架和NO_HZ模式。我们将在这一部分继续研究与Linux内核中与时间管理相关的内容，并熟悉Linux内核中的另一个概念-timers。在研究Linux内核中的计时器之前，我们必须学习一些有关此概念的理论。请注意，我们将在本部分中考虑软件计时器。

Linux内核提供了软件计时器的概念，以允许将来可以调用内核功能。计时器在Linux内核中被广泛使用。例如，查看源代码文件 net/netfilter/ipset/ip_set_list_set.c。此源代码文件提供了用于管理IP地址组的框架的实现。

在 list_set 结构中包含了 time_list 变量 gc :

struct list_set {
    ...
    struct timer_list gc;
    ...
};

并非gc字段具有timer_list类型。 在include/linux/timer.h 头文件中定义的结构，该结构的要点是存储 Linux内核中的动态计时器。 实际上，Linux内核提供了两种类型的计时器，称为动态计时器和间隔计时器。 内核使用第一种计时器，用户模式使用第二种计时器。timer_list结构包含实际的dynamic定时器。 在我们的示例中，list_set包含gc计时器代表垃圾收集的计时器。 该计时器将在list_set_gc_init函数中初始化：

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深入研究此示例，因为本章与network部分的内容无关。但是我们看到计时器在Linux内核中得到了广泛使用，并且了解到它们代表了可以在将来调用功能的概念。

现在，让我们继续研究Linux内核的源代码，该代码与计时器和时间管理的内容有关，就像我们在前几章中所做的那样。

动态计数器介绍

正如我已经写过的，我们在之前的part中了解了tick broadcast框架和NO_HZ模式。 它们将通过调用tick_init函数在init/ main.c源代码文件中初始化。 如果我们查看此源代码文件，将看到下一次与管理相关的功能是：

init_timers();

init_timers函数定义在 kernel/time/timer.c源码文件中:

void __init init_timers(void)
{
    init_timer_cpus();
    open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
}

已按照新版本更新

让我们看一下每个函数的实现。 第一个函数 init_timer_cpus 同样定义在文件kernel/time/timer.c 源码文件中，处理系统每一个可能处理器:

static void __init init_timer_cpus(void)
{
    int cpu;

    for_each_possible_cpu(cpu)
        init_timer_cpu(cpu);
}

如果您不知道或不记得它是什么可能CPU，则可以阅读part其中描述了Linux内核中的 cpumask概念。 简而言之，可能处理器是可以在系统生命周期内随时插入的处理器。

init_timer_cpu函数为我们完成了主要工作，即它为每个处理器执行tvec_base结构的初始化。 在kernel/time/timer.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 时间系统分析，对新版本的结构说了说明.
timers: Give a few structs and members proper names 结构体调整记录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字段表示列表，该列表存储具有较大到期时间的动态计时器。

通过internal_add_timer:计算定时器与当前jiffies差值, cacade；迁移数组 tv5->tv4->tv3->tv2->tv1，由于jiffies在递增， tv5链表中的定时器会逐步迁移到tv1,并完成执行.

1. 现代时间轮

 * 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源代码文件中定义并执行初始化timer_base的：

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变量，该变量代表对于给定处理器指定动态计时器的主要数据结构。 per-cpu变量在同一源代码文件中定义：

static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);

首先，我们将给定处理器的timer_bases的地址获取到base变量，并在获取时，开始在init_timer_cpu函数中初始化一些timer_base字段。 在使用jiffies和可能的处理器编号初始化per-cpu动态计时器并中初始化timer_base的lockspinlock, 通过init_timer_cpus完成相关可能cpu的处理:

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处理器。

当处理器将在逻辑上脱机时，如何进行处理:

#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 源代码文件。

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中可以看到项目cpu状态及处理函数的定义:

这部分还不太了待更新

    [CPUHP_TIMERS_PREPARE] = {
        .name           = "timers:prepare",
        .startup.single     = timers_prepare_cpu,
        .teardown.single    = timers_dead_cpu,
    },

init_timers 最后一个步骤调用如下:

open_softirq(TIMER_SOFTIRQ, run_timer_softirq);

如果您已阅读有关中断的第九部分，则可能已经熟悉open_softirq函数。和Linux内核中的中断处理。简而言之，kernel/softirq.c源代码文件中定义的open_softirq函数会执行中断延迟处理程序。

在我们的例子中， 中断延迟函数(中断触发函数)是run_timer_softirq函数，它将在do_IRQ 函数,定义见arch/x86/kernel/irq.c。该功能的重点是处理软件动态计时器。在硬件计时器中断处理期间，Linux内核不会执行此操作，因为这是耗时的操作。

触发软中断时的回调函数

让我们看一下run_timer_softirq函数的实现：

// 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

/**
 * __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，, 这里的比较方法调用include/linux/jiffies.h中定义的time_after_eq宏:

#define time_after_eq(a,b)          \
    (typecheck(unsigned long, a) && \
     typecheck(unsigned long, b) && \
    ((long)((a) - (b)) >= 0))

如果jiffies小于定时器时间，那么返回，否则 调用collect_expired_timers

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的结构

static inline void __run_timers(struct timer_base *base)
{

...
    raw_spin_lock_irq(&base->lock);

...
    raw_spin_unlock_irq(&base->lock);
}

之后，它开始循环，而base->clk将不大于jiffies。

   while (time_after_eq(jiffies, base->clk)) {
   ...
   ...
   ...

我们可以在循环中找到许多不同的操作，但要点是找到过期的计时器并调用延迟的函数。 首先，我们需要计算列表的idx，该列表存储要使用以下表达式处理的i层计时器：

idx = (clk & LVL_MASK) + i * LVL_SIZE;

通过位图操作就能判断是否存在相关timer

    if (__test_and_clear_bit(idx, base->pending_map)) {

然后取下满足条件的timers放到heads中:

    vec = base->vectors + idx;
    hlist_move_list(vec, heads++);
    levels++;

之后增加base->clk++;

    base->clk++;

最后在 expire_timers中可以看到通过调用call_timer_fn调用了相关回调函数;

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 函数调用了指定的函数

static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long),
                          unsigned long data)
{
    ...
    ...
    ...
    fn(data);
    ...
    ...
    ...
}

就这样。 从现在开始，Linux内核就具有用于动态计时器的基础结构。 我们不会深入探讨这个有趣的主题。 正如我已经写过的，timers是Linux内核中的widely使用的这个概念, 但是没有介绍这些东西如何实现和如何工作。 但是现在我们知道了这个概念，为什么Linux内核需要它以及围绕它的一些数据结构。

现在让我们看看Linux内核中动态计时器的用法。

动态定时器的用法

如您已经注意到的，如果Linux内核提供了一个概念，那么它也提供了用于管理该概念的API，并且动态计时器概念在这里也不例外。要在Linux内核代码中使用计时器，我们必须定义一个带有timer_list类型的变量。我们可以通过两种方式初始化我们的timer_list结构。第一种是使用include/linux/timer.h头文件中定义的timer_setup宏。 ：

准备一个定时器使用timer_setup:

#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 是这个样子:

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);
}

另外一个方法是初始化:

#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结构

动态定时器被初始话成功了后， 可以用下面方法开始一个定时器：

void add_timer(struct timer_list * timer);
void add_timer_on(struct timer_list *timer, int cpu);

用下面的函数停止一个定时器:

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： //github.com/0xAX/linux-insides/issues/new）。

请注意，英语不是我的母语，对于给您带来的不便，我深表歉意。如果发现任何错误，请将PR发送给[linux-insides]（https://github.com/0xAX/linux-insides）。

相关链接

• IP
• netfilter
• network
• cpumask
• interrupt
• jiffies
• per-cpu
• spinlock
• procfs
• previous part