内核初始化。第九部分。

RCU初始化

这是Linux内核初始化过程的第九部分，上一部分我们停在了调度器初始化。在这部分中，我们将继续深入了解Linux内核初始化过程，主要目的是了解RCU的初始化。我们可以看到，在init/main.c中，sched_init之后的下一步是调用preempt_disable。有两个宏：

• preempt_disable
• preempt_enable

用于禁用和启用抢占。首先让我们尝试理解在操作系统内核上下文中的preempt是什么。简单来说，抢占是操作系统内核提前当前任务以运行具有更高优先级任务的能力。在这里我们需要禁用抢占，因为我们在早期启动时只有一个init进程，我们在调用cpu_idle函数之前不需要停止它。preempt_disable宏定义在include/linux/preempt.h中，取决于CONFIG_PREEMPT_COUNT内核配置选项。这个宏实现为：

#define preempt_disable() \
do { \
        preempt_count_inc(); \
        barrier(); \
} while (0)

如果没有设置CONFIG_PREEMPT_COUNT，则为：

#define preempt_disable()                       barrier()

让我们看看它。首先我们可以看到这两种宏实现之间的一个区别。设置了CONFIG_PREEMPT_COUNT的preempt_disable包含了对preempt_count_inc的调用。有一个特殊的percpu变量存储持有的锁的数量和preempt_disable调用的次数：

DECLARE_PER_CPU(int, __preempt_count);

在preempt_disable的第一个实现中，我们增加了这个__preempt_count。有一个API用于返回__preempt_count的值，它是preempt_count函数。由于我们调用了preempt_disable，首先我们用preempt_count_inc宏增加抢占计数器，它展开为：

#define preempt_count_inc() preempt_count_add(1)
#define preempt_count_add(val)  __preempt_count_add(val)

其中preempt_count_add调用raw_cpu_add_4宏，它将1加到给定的percpu变量（我们的情况下是__preempt_count）上（关于percpu变量的更多信息可以在每个CPU变量部分阅读）。好的，我们增加了__preempt_count，接下来我们可以看到两个宏中都调用了barrier宏。barrier宏插入了一个优化屏障。在具有x86_64架构的处理器中，独立内存访问操作可以以任何顺序执行。这就是为什么我们需要机会指出编译器和处理器遵守顺序。这种机制是内存屏障。让我们考虑一个简单的例子：

preempt_disable();
foo();
preempt_enable();

编译器可以将其重新排列为：

preempt_disable();
preempt_enable();
foo();

在这种情况下，不可抢占的函数foo可以被抢占。由于我们在preempt_disable和preempt_enable宏中放置了barrier宏，它防止编译器交换preempt_count_inc与其他语句。关于屏障的更多信息可以在这里和这里阅读。

下一步我们可以看到以下语句：

if (WARN(!irqs_disabled(),
	 "Interrupts were enabled *very* early, fixing it\n"))
	local_irq_disable();

它检查IRQs状态，并在它们被启用时禁用（对于x86_64使用cli指令）。

就这样了。抢占被禁用了，我们可以继续前进。

整数ID管理初始化

下一步我们可以看到调用了定义在lib/idr.c中的idr_init_cache函数。idr库在Linux内核的多个地方用于管理为对象分配整数IDs和通过ID查找对象。

让我们看看idr_init_cache函数的实现：

void __init idr_init_cache(void)
{
        idr_layer_cache = kmem_cache_create("idr_layer_cache",
                                sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
}

在这里我们可以看到调用了kmem_cache_create。我们已经在init/main.c中调用了kmem_cache_init。这个函数再次使用kmem_cache_alloc创建通用缓存（关于缓存的更多信息我们将在Linux内核内存管理章节中看到）。在我们的情况下，我们使用kmem_cache_t，它将被slab分配器使用，kmem_cache_create创建它。如你所见，我们向kmem_cache_create传递了五个参数：

• 缓存的名称；
• 缓存中存储的对象的大小；
• 页面中第一个对象的偏移量；
• 标志；
• 对象的构造函数。

它将为整数ID创建kmem_cache。整数IDs是通常用于将一组整数ID映射到一组指针的常用模式。我们可以看到在i2c驱动子系统的使用整数ID的例子。例如，代表i2c子系统核心的drivers/i2c/i2c-core-base.c定义了i2c适配器的ID，使用DEFINE_IDR宏：

static DEFINE_IDR(i2c_adapter_idr);

然后它用于声明i2c适配器：

static int __i2c_add_numbered_adapter(struct i2c_adapter *adap)
{
  int     id;
  ...
  ...
  ...
  id = idr_alloc(&i2c_adapter_idr, adap, adap->nr, adap->nr + 1, GFP_KERNEL);
  ...
  ...
  ...
}

id2_adapter_idr表示动态计算的总线号。

关于整数ID管理的更多信息，你可以在这里阅读。

RCU初始化

下一步是RCU初始化，通过rcu_init函数，其实现取决于两个内核配置选项：

• CONFIG_TINY_RCU
• CONFIG_TREE_RCU

在第一种情况下，rcu_init将在kernel/rcu/tiny.c中，而在第二种情况下，它将在kernel/rcu/tree.c中定义。我们将看到tree rcu的实现，但首先关于RCU的概述。

RCU或读-复制-更新是Linux内核中实现的可扩展的高性能同步机制。在早期，Linux内核提供了支持并发运行应用程序的环境，但所有执行都在内核中使用单个全局锁进行序列化。在今天，Linux内核没有单个全局锁，但提供了不同的机制，包括无锁数据结构、每个CPU的数据结构等。其中一种机制是-读-复制-更新。RCU技术是为很少修改的数据结构设计的。RCU的思想很简单。例如，我们有一个很少修改的数据结构。如果有人想改变这个数据结构，我们制作这个数据结构的副本，并在副本中进行所有更改。与此同时，所有其他数据结构的用户都使用它的旧版本。接下来，我们需要选择一个安全的时刻，当原始版本的数据结构没有用户时，用修改后的副本更新它。

当然，这个RCU的描述非常简化。为了理解一些关于RCU的细节，我们首先需要学习一些术语。RCU中的数据读取器在关键部分中执行。每当数据读取器进入关键部分时，它会调用rcu_read_lock，并在退出关键部分时调用rcu_read_unlock。如果线程不在关键部分，它将处于称为-静默状态的状态。当每个线程都处于静默状态的时刻称为-宽限期。如果一个线程想要从数据结构中移除一个元素，这发生在两个步骤中。第一步是移除 - 从数据结构中原子地移除元素，但并不释放物理内存。之后，线程-写入者宣布并等待直到它完成。从这一刻起，被移除的元素对线程-读取者可用。在宽限期结束后，元素移除的第二步将开始，它只是从物理内存中移除元素。

RCU有几个实现。旧的RCU称为经典，新实现称为tree RCU。正如你可能已经理解的，CONFIG_TREE_RCU内核配置选项启用了树RCU。另一个是tiny RCU，它取决于CONFIG_TINY_RCU和CONFIG_SMP=n。我们将在关于同步原语的单独章节中看到更多关于RCU的详细信息，但现在让我们看看kernel/rcu/tree.c中的rcu_init实现：

void __init rcu_init(void)
{
    int cpu;

    rcu_bootup_announce();
    rcu_init_geometry();
    rcu_init_one(&rcu_bh_state, &rcu_bh_data);
    rcu_init_one(&rcu_sched_state, &rcu_sched_data);
    __rcu_init_preempt();
    open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);

    /*
     * We don't need protection against CPU-hotplug here because
     * this is called early in boot, before either interrupts
     * or the scheduler are operational.
     */
    cpu_notifier(rcu_cpu_notify, 0);
    pm_notifier(rcu_pm_notify, 0);
    for_each_online_cpu(cpu)
        rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);

    rcu_early_boot_tests();
}

在rcu_init函数的开始，我们定义了cpu变量并调用rcu_bootup_announce。rcu_bootup_announce函数非常简单：

static void __init rcu_bootup_announce(void)
{
    pr_info("Hierarchical RCU implementation.\n");
    rcu_bootup_announce_oddness();
}

它只是用pr_info函数打印有关RCU的信息，并使用rcu_bootup_announce_oddness，它也使用pr_info打印有关当前RCU配置的不同信息，这取决于不同的内核配置选项，如CONFIG_RCU_TRACE、CONFIG_PROVE_RCU、CONFIG_RCU_FANOUT_EXACT等。下一步，我们可以看到调用了rcu_init_geometry函数。这个函数定义在同一个源代码文件中，并根据CPU的数量计算节点树的几何形状。实际上RCU提供了可扩展性，内部RCU锁争用极低。如果数据结构将从不同的CPU读取怎么办？RCU API提供了rcu_state结构，它呈现了RCU的全局状态，包括节点层次结构。层次结构由以下呈现：

struct rcu_node node[NUM_RCU_NODES];

数组结构。正如我们在上面定义的注释中读到的：

The root (first level) of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]), and the third level
in ->node[m+1] and following (->node[m+1] referenced by ->level[2]).  The number of levels is
determined by the number of CPUs and by CONFIG_RCU_FANOUT.

Small systems will have a "hierarchy" consisting of a single rcu_node.

rcu_node结构在kernel/rcu/tree.h中定义，包含有关当前宽限期的信息，宽限期是否已完成，需要切换的CPU或组以使当前宽限期继续，等等。每个rcu_node包含一对CPU的锁。这些rcu_node结构嵌入到rcu_state结构的线性数组中，并以树的形式呈现，根是第一个元素，并覆盖所有CPU。如你所见，rcu节点的数量由NUM_RCU_NODES决定，这取决于可用CPU的数量：

#define NUM_RCU_NODES (RCU_SUM - NR_CPUS)
#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)

其中级别值取决于CONFIG_RCU_FANOUT_LEAF配置选项。例如，在最简单的情况下，一台有八个CPU的机器上的一个rcu_node将覆盖两个CPU：

+-----------------------------------------------------------------+
|  rcu_state                                                      |
|                 +----------------------+                        |
|                 |         root         |                        |
|                 |       rcu_node       |                        |
|                 +----------------------+                        |
|                    |                |                           |
|               +----v-----+       +--v-------+                   |
|               |          |       |          |                   |
|               | rcu_node |       | rcu_node |                   |
|               |          |       |          |                   |
|         +------------------+     +----------------+             |
|         |                  |        |             |             |
|         |                  |        |             |             |
|    +----v-----+    +-------v--+   +-v--------+  +-v--------+    |
|    |          |    |          |   |          |  |          |    |
|    | rcu_node |    | rcu_node |   | rcu_node |  | rcu_node |    |
|    |          |    |          |   |          |  |          |    |
|    +----------+    +----------+   +----------+  +----------+    |
|         |                 |             |               |       |
|         |                 |             |               |       |
|         |                 |             |               |       |
|         |                 |             |               |       |
+---------|-----------------|-------------|---------------|-------+
          |                 |             |               |
+---------v-----------------v-------------v---------------v--------+
|                 |                |               |               |
|     CPU1        |      CPU3      |      CPU5     |     CPU7      |
|                 |                |               |               |
|     CPU2        |      CPU4      |      CPU6     |     CPU8      |
|                 |                |               |               |
+------------------------------------------------------------------+

所以，在rcu_init_geometry函数中，我们只需要计算rcu_node结构的总数。我们从计算第一个和下一个fqs（force-quiescent-state）（关于它的更多信息请参见上面的内容）的jiffies开始：

d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
if (jiffies_till_first_fqs == ULONG_MAX)
    jiffies_till_first_fqs = d;
if (jiffies_till_next_fqs == ULONG_MAX)
    jiffies_till_next_fqs = d;

其中：

#define RCU_JIFFIES_TILL_FORCE_QS (1 + (HZ > 250) + (HZ > 500))
#define RCU_JIFFIES_FQS_DIV     256

由于我们计算了这些jiffies，我们检查之前定义的jiffies_till_first_fqs和jiffies_till_next_fqs变量是否等于ULONG_MAX（它们的默认值）并将它们设置为计算值。由于我们之前没有触及这些变量，它们等于ULONG_MAX：

static ulong jiffies_till_first_fqs = ULONG_MAX;
static ulong jiffies_till_next_fqs = ULONG_MAX;

在rcu_init_geometry的下一步中，我们检查rcu_fanout_leaf是否未改变（它与编译时的CONFIG_RCU_FANOUT_LEAF具有相同的值），并且等于CONFIG_RCU_FANOUT_LEAF配置选项的值，我们只返回：

if (rcu_fanout_leaf == CONFIG_RCU_FANOUT_LEAF &&
    nr_cpu_ids == NR_CPUS)
    return;

在此之后，我们需要计算给定级别数量的rcu_node树可以处理的节点数：

rcu_capacity[0] = 1;
rcu_capacity[1] = rcu_fanout_leaf;
for (i = 2; i <= MAX_RCU_LVLS; i++)
    rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;

最后一步我们在循环中计算树的每个级别的rcu节点数。

由于我们已经计算了rcu_node树的几何形状，我们需要回到rcu_init函数，下一步我们需要使用rcu_init_one函数初始化两个rcu_state结构：

rcu_init_one(&rcu_bh_state, &rcu_bh_data);
rcu_init_one(&rcu_sched_state, &rcu_sched_data);

rcu_init_one函数接受两个参数：

• 全局RCU状态；
• RCU的每个CPU数据。

这两个变量在kernel/rcu/tree.h中定义，以及其percpu数据：

extern struct rcu_state rcu_bh_state;
DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);

关于这些状态，你可以在这里阅读。正如我上面写的，我们需要初始化rcu_state结构，rcu_init_one函数将帮助我们。在rcu_state初始化之后，我们可以看到调用了__rcu_init_preempt，它取决于CONFIG_PREEMPT_RCU内核配置选项。它与之前的函数执行相同的操作 - 使用rcu_init_one函数初始化rcu_preempt_state结构，它具有rcu_state类型。在此之后，在rcu_init中，我们可以看到调用了：

open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);

这个函数。这个函数注册了一个待处理中断的处理程序。待处理中断或softirq假设部分操作可以延迟到系统负载较轻时执行。待处理中断由以下结构表示：

struct softirq_action
{
    void    (*action)(struct softirq_action *);
};

它定义在include/linux/interrupt.h中，只包含一个字段 - 中断的处理程序。你可以用以下命令检查系统中的softirqs：

$ cat /proc/softirqs
                    CPU0       CPU1       CPU2       CPU3       CPU4       CPU5       CPU6       CPU7
          HI:          2          0          0          1          0          2          0          0
       TIMER:     137779     108110     139573     107647     107408     114972      99653      98665
      NET_TX:       1127          0          4          0          1          1          0          0
      NET_RX:        334        221     132939       3076        451        361        292        303
       BLOCK:       5253       5596          8        779       2016      37442         28       2855
BLOCK_IOPOLL:          0          0          0          0          0          0          0          0
     TASKLET:         66          0       2916        113          0         24      26708          0
       SCHED:     102350      75950      91705      75356      75323      82627      69279      69914
     HRTIMER:        510        302        368        260        219        255        248        246
         RCU:      81290      68062      82979      69015      68390      69385      63304      63473

open_softirq函数接受两个参数：

• 中断的索引；
• 中断处理程序。

并将中断处理程序添加到待处理中断的数组中：

void open_softirq(int nr, void (*action)(struct softirq_action *))
{
    softirq_vec[nr].action = action;
}

在我们的情况下，中断处理程序是rcu_process_callbacks，它定义在kernel/rcu/tree.c中，它执行当前CPU的RCU核心处理。注册了RCU的softirq中断后，我们可以看到以下代码：

cpu_notifier(rcu_cpu_notify, 0);
pm_notifier(rcu_pm_notify, 0);
for_each_online_cpu(cpu)
    rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);

在这里我们可以看到注册了cpu通知器，这在支持CPU热插拔的系统中是需要的，我们将不会深入了解这个主题的细节。rcu_init中的最后一个函数是rcu_early_boot_tests：

void rcu_early_boot_tests(void)
{
    pr_info("Running RCU self tests\n");

    if (rcu_self_test)
         early_boot_test_call_rcu();
    if (rcu_self_test_bh)
        early_boot_test_call_rcu_bh();
    if (rcu_self_test_sched)
       early_boot_test_call_rcu_sched();
}

它运行RCU的自测试。

就这样了。我们看到了RCU子系统的初始化过程。如我上面所写，更多关于RCU的内容将在关于同步原语的单独章节中介绍。

初始化过程的其余部分

好的，我们已经通过了这部分的主要主题，即RCU初始化，但这不是Linux内核初始化过程的结束。在这部分的最后一个段落中，我们将看到一些函数在初始化时工作，但我们不会深入了解这些函数的实现细节，原因多种多样。不深入细节的一些原因如下：

• 它们对通用内核初始化过程并不重要，并且取决于不同的内核配置；
• 它们具有调试性质，现在并不重要；
• 我们将在其他部分/章节中看到这些内容的许多细节。

在我们初始化了RCU之后，下一步在init/main.c中可以看到的是trace_init函数。从它的名字可以理解，这个函数初始化跟踪子系统。你可以在这里阅读更多关于Linux内核跟踪系统的信息。

在trace_init之后，我们可以看到调用radix_tree_init。如果你熟悉不同的数据结构，你可以理解这个函数的名称，它初始化内核实现的Radix树。这个函数定义在lib/radix-tree.c中，你可以在关于Radix树的部分阅读更多关于它的信息。

接下来的几个函数与中断处理子系统有关，它们是：

• early_irq_init
• init_IRQ
• softirq_init

我们将在关于中断和异常处理的特别部分中看到这些函数的解释和它们的实现。在此之后是许多与不同计时和计时器相关函数（如init_timers、hrtimers_init、time_init等）。我们将在关于计时器的章节中看到这些函数的更多内容。

接下来的几个函数与perf事件相关 - perf_event_init（将有专门关于perf的章节），用profile_init初始化分析。在此之后，我们通过调用：

local_irq_enable();

启用irq，它展开为sti指令，并进行SLAB的后续初始化，调用kmem_cache_init_late函数（如我上面所写，我们将在Linux内存管理章节中了解SLAB）。

在SLAB的后续初始化之后，下一步是用console_init函数初始化控制台，该函数来自drivers/tty/tty_io.c。

在控制台初始化之后，我们可以看到lockdep_info函数，它打印有关锁依赖验证器的信息。在此之后，我们可以看到用debug_objects_mem_init初始化动态分配的debug objects，用kmemleak_init初始化内核内存泄漏检测器，用setup_per_cpu_pageset设置percpu页面集，用numa_policy_init设置 NUMA策略，用sched_clock_init为调度器设置时间，用pidmap_init调用初始化初始PID命名空间的pidmap，用anon_vma_init为私有虚拟内存区域创建缓存，并用acpi_early_init提前初始化ACPI。

这是Linux内核初始化过程的第九部分的结尾，在这里我们看到了RCU的初始化。在这部分的最后一个段落（Rest of the initialization process）中，我们将浏览许多函数，但不会深入了解它们的实现细节。如果你不了解这些内容，或者你了解但不理解这些内容，请不用担心。正如我已经多次写过的，我们将在其他部分或其他章节中看到实现的细节。

结论

这是关于Linux内核初始化过程的第九部分的结尾。在这部分中，我们看到了RCU子系统的初始化过程。在下一部分中，我们将继续深入了解Linux内核初始化过程，我希望我们将完成start_kernel函数，并从同一个init/main.c源代码文件中转到rest_init函数，并看到第一个进程的启动。

如果你有任何问题或建议，请在评论中告诉我，或者在twitter上联系我。

请注意，英语不是我的第一语言，我对任何不便表示歉意。如果你发现任何错误，请向我发送PR到linux-insides。

链接

• 无锁数据结构
• kmemleak
• ACPI
• IRQs
• RCU
• RCU文档
• 整数ID管理
• Documentation/memory-barriers.txt
• 运行时锁定正确性验证器
• 每个CPU变量
• Linux内核内存管理
• slab
• i2c
• 上一部分