0xAX 发布的文章

Linux 内核中的位数组和位操作

除了不同的基于链式的数据结构以外,Linux 内核也为位数组(或称为 位图 bitmap )提供了 API。位数组在 Linux 内核里被广泛使用,并且在以下的源代码文件中包含了与这样的结构搭配使用的通用 API

除了这两个文件之外,还有体系结构特定的头文件,它们为特定的体系结构提供优化的位操作。我们将探讨 x86\_64 体系结构,因此在我们的例子里,它会是

头文件。正如我上面所写的,位图在 Linux 内核中被广泛地使用。例如,位数组常常用于保存一组在线/离线处理器,以便系统支持热插拔的 CPU(你可以在 cpumasks 部分阅读更多相关知识 ),一个 位数组 bit array 可以在 Linux 内核初始化等期间保存一组已分配的中断处理

因此,本部分的主要目的是了解 位数组 bit array 是如何在 Linux 内核中实现的。让我们现在开始吧。

位数组声明

在我们开始查看位图操作的 API 之前,我们必须知道如何在 Linux 内核中声明它。有两种声明位数组的通用方法。第一种简单的声明一个位数组的方法是,定义一个 unsigned long 的数组,例如:

unsigned long my_bitmap[8]

第二种方法,是使用 DECLARE_BITMAP 宏,它定义于 include/linux/types.h 头文件:

#define DECLARE_BITMAP(name,bits) \
    unsigned long name[BITS_TO_LONGS(bits)]

我们可以看到 DECLARE_BITMAP 宏使用两个参数:

  • name - 位图名称;
  • bits - 位图中位数;

并且只是使用 BITS_TO_LONGS(bits) 元素展开 unsigned long 数组的定义。 BITS_TO_LONGS 宏将一个给定的位数转换为 long 的个数,换言之,就是计算 bits 中有多少个 8 字节元素:

#define BITS_PER_BYTE           8
#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

因此,例如 DECLARE_BITMAP(my_bitmap, 64) 将产生:

>>> (((64) + (64) - 1) / (64))
1

与:

unsigned long my_bitmap[1];

在能够声明一个位数组之后,我们便可以使用它了。

体系结构特定的位操作

我们已经看了上面提及的一对源文件和头文件,它们提供了位数组操作的 API。其中重要且广泛使用的位数组 API 是体系结构特定的且位于已提及的头文件中 arch/x86/include/asm/bitops.h

首先让我们查看两个最重要的函数:

  • set_bit;
  • clear_bit.

我认为没有必要解释这些函数的作用。从它们的名字来看,这已经很清楚了。让我们直接查看它们的实现。如果你浏览 arch/x86/include/asm/bitops.h 头文件,你将会注意到这些函数中的每一个都有原子性和非原子性两种变体。在我们开始深入这些函数的实现之前,首先,我们必须了解一些有关 原子 atomic 操作的知识。

简而言之,原子操作保证两个或以上的操作不会并发地执行同一数据。x86 体系结构提供了一系列原子指令,例如, xchgcmpxchg 等指令。除了原子指令,一些非原子指令可以在 lock 指令的帮助下具有原子性。现在你已经对原子操作有了足够的了解,我们可以接着探讨 set_bitclear_bit 函数的实现。

我们先考虑函数的 非原子性 non-atomic 变体。非原子性的 set_bitclear_bit 的名字以双下划线开始。正如我们所知道的,所有这些函数都定义于 arch/x86/include/asm/bitops.h 头文件,并且第一个函数就是 __set_bit:

static inline void __set_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
}

正如我们所看到的,它使用了两个参数:

  • nr - 位数组中的位号(LCTT 译注:从 0 开始)
  • addr - 我们需要置位的位数组地址

注意,addr 参数使用 volatile 关键字定义,以告诉编译器给定地址指向的变量可能会被修改。 __set_bit 的实现相当简单。正如我们所看到的,它仅包含一行内联汇编代码。在我们的例子中,我们使用 bts 指令,从位数组中选出一个第一操作数(我们的例子中的 nr)所指定的位,存储选出的位的值到 CF 标志寄存器并设置该位(LCTT 译注:即 nr 指定的位置为 1)。

注意,我们了解了 nr 的用法,但这里还有一个参数 addr 呢!你或许已经猜到秘密就在 ADDRADDR 是一个定义在同一个头文件中的宏,它展开为一个包含给定地址和 +m 约束的字符串:

#define ADDR                BITOP_ADDR(addr)
#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))

除了 +m 之外,在 __set_bit 函数中我们可以看到其他约束。让我们查看并试着理解它们所表示的意义:

  • +m - 表示内存操作数,这里的 + 表明给定的操作数为输入输出操作数;
  • I - 表示整型常量;
  • r - 表示寄存器操作数

除了这些约束之外,我们也能看到 memory 关键字,其告诉编译器这段代码会修改内存中的变量。到此为止,现在我们看看相同的 原子性 atomic 变体函数。它看起来比 非原子性 non-atomic 变体更加复杂:

static __always_inline void
set_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "orb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)CONST_MASK(nr))
            : "memory");
    } else {
        asm volatile(LOCK_PREFIX "bts %1,%0"
            : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
    }
}

(LCTT 译注:BITOP\_ADDR 的定义为:#define BITOP_ADDR(x) "=m" (*(volatile long *) (x)),ORB 为字节按位或。)

首先注意,这个函数使用了与 __set_bit 相同的参数集合,但额外地使用了 __always_inline 属性标记。 __always_inline 是一个定义于 include/linux/compiler-gcc.h 的宏,并且只是展开为 always_inline 属性:

#define __always_inline inline __attribute__((always_inline))

其意味着这个函数总是内联的,以减少 Linux 内核映像的大小。现在让我们试着了解下 set_bit 函数的实现。首先我们在 set_bit 函数的开头检查给定的位的数量。IS_IMMEDIATE 宏定义于相同的头文件,并展开为 gcc 内置函数的调用:

#define IS_IMMEDIATE(nr)        (__builtin_constant_p(nr))

如果给定的参数是编译期已知的常量,__builtin_constant_p 内置函数则返回 1,其他情况返回 0。假若给定的位数是编译期已知的常量,我们便无须使用效率低下的 bts 指令去设置位。我们可以只需在给定地址指向的字节上执行 按位或 操作,其字节包含给定的位,掩码位数表示高位为 1,其他位为 0 的掩码。在其他情况下,如果给定的位号不是编译期已知常量,我们便做和 __set_bit 函数一样的事。CONST_MASK_ADDR 宏:

#define CONST_MASK_ADDR(nr, addr)   BITOP_ADDR((void *)(addr) + ((nr)>>3))

展开为带有到包含给定位的字节偏移的给定地址,例如,我们拥有地址 0x1000 和位号 0x9。因为 0x9 代表 一个字节 + 一位,所以我们的地址是 addr + 1:

>>> hex(0x1000 + (0x9 >> 3))
'0x1001'

CONST_MASK 宏将我们给定的位号表示为字节,位号对应位为高位 1,其他位为 0

#define CONST_MASK(nr)          (1 << ((nr) & 7))
>>> bin(1 << (0x9 & 7))
'0b10'

最后,我们应用 按位或 运算到这些变量上面,因此,假如我们的地址是 0x4097 ,并且我们需要置位号为 9 的位为 1:

>>> bin(0x4097)
'0b100000010010111'
>>> bin((0x4097 >> 0x9) | (1 << (0x9 & 7)))
'0b100010'

第 9 位 将会被置位。(LCTT 译注:这里的 9 是从 0 开始计数的,比如0010,按照作者的意思,其中的 1 是第 1 位)

注意,所有这些操作使用 LOCK_PREFIX 标记,其展开为 lock 指令,保证该操作的原子性。

正如我们所知,除了 set_bit__set_bit 操作之外,Linux 内核还提供了两个功能相反的函数,在原子性和非原子性的上下文中清位。它们是 clear_bit__clear_bit。这两个函数都定义于同一个头文件 并且使用相同的参数集合。不仅参数相似,一般而言,这些函数与 set_bit__set_bit 也非常相似。让我们查看非原子性 __clear_bit 的实现吧:

static inline void __clear_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
}

没错,正如我们所见,__clear_bit 使用相同的参数集合,并包含极其相似的内联汇编代码块。它只是使用 btr 指令替换了 bts。正如我们从函数名所理解的一样,通过给定地址,它清除了给定的位。btr 指令表现得像 bts(LCTT 译注:原文这里为 btr,可能为笔误,修正为 bts)。该指令选出第一操作数所指定的位,存储它的值到 CF 标志寄存器,并且清除第二操作数指定的位数组中的对应位。

__clear_bit 的原子性变体为 clear_bit

static __always_inline void
clear_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "andb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)~CONST_MASK(nr)));
    } else {
        asm volatile(LOCK_PREFIX "btr %1,%0"
            : BITOP_ADDR(addr)
            : "Ir" (nr));
    }
}

并且正如我们所看到的,它与 set_bit 非常相似,只有两处不同。第一处差异为 clear_bit 使用 btr 指令来清位,而 set_bit 使用 bts 指令来置位。第二处差异为 clear_bit 使用否定的位掩码和 按位与 在给定的字节上置位,而 set_bit 使用 按位或 指令。

到此为止,我们可以在任意位数组置位和清位了,我们将看看位掩码上的其他操作。

在 Linux 内核中对位数组最广泛使用的操作是设置和清除位,但是除了这两个操作外,位数组上其他操作也是非常有用的。Linux 内核里另一种广泛使用的操作是知晓位数组中一个给定的位是否被置位。我们能够通过 test_bit 宏的帮助实现这一功能。这个宏定义于 arch/x86/include/asm/bitops.h 头文件,并根据位号分别展开为 constant_test_bitvariable_test_bit 调用。

#define test_bit(nr, addr)          \
    (__builtin_constant_p((nr))                 \
     ? constant_test_bit((nr), (addr))          \
     : variable_test_bit((nr), (addr)))

因此,如果 nr 是编译期已知常量,test_bit 将展开为 constant_test_bit 函数的调用,而其他情况则为 variable_test_bit。现在让我们看看这些函数的实现,让我们从 variable_test_bit 开始看起:

static inline int variable_test_bit(long nr, volatile const unsigned long *addr)
{
    int oldbit;

    asm volatile("bt %2,%1\n\t"
             "sbb %0,%0"
             : "=r" (oldbit)
             : "m" (*(unsigned long *)addr), "Ir" (nr));

    return oldbit;
}

variable_test_bit 函数使用了与 set_bit 及其他函数使用的相似的参数集合。我们也可以看到执行 btsbb 指令的内联汇编代码。bt (或称 bit test)指令从第二操作数指定的位数组选出第一操作数指定的一个指定位,并且将该位的值存进标志寄存器的 CF 位。第二个指令 sbb 从第二操作数中减去第一操作数,再减去 CF 的值。因此,这里将一个从给定位数组中的给定位号的值写进标志寄存器的 CF 位,并且执行 sbb 指令计算: 00000000 - CF,并将结果写进 oldbit 变量。

constant_test_bit 函数做了和我们在 set_bit 所看到的一样的事:

static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr)
{
    return ((1UL << (nr & (BITS_PER_LONG-1))) &
        (addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
}

它生成了一个位号对应位为高位 1,而其他位为 0 的字节(正如我们在 CONST_MASK 所看到的),并将 按位与 应用于包含给定位号的字节。

下一个被广泛使用的位数组相关操作是改变一个位数组中的位。为此,Linux 内核提供了两个辅助函数:

  • __change_bit;
  • change_bit.

你可能已经猜测到,就拿 set_bit__set_bit 例子说,这两个变体分别是原子和非原子版本。首先,让我们看看 __change_bit 函数的实现:

static inline void __change_bit(long nr, volatile unsigned long *addr)
{
    asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
}

相当简单,不是吗? __change_bit 的实现和 __set_bit 一样,只是我们使用 btc 替换 bts 指令而已。 该指令从一个给定位数组中选出一个给定位,将该为位的值存进 CF 并使用求反操作改变它的值,因此值为 1 的位将变为 0,反之亦然:

>>> int(not 1)
0
>>> int(not 0)
1

__change_bit 的原子版本为 change_bit 函数:

static inline void change_bit(long nr, volatile unsigned long *addr)
{
    if (IS_IMMEDIATE(nr)) {
        asm volatile(LOCK_PREFIX "xorb %1,%0"
            : CONST_MASK_ADDR(nr, addr)
            : "iq" ((u8)CONST_MASK(nr)));
    } else {
        asm volatile(LOCK_PREFIX "btc %1,%0"
            : BITOP_ADDR(addr)
            : "Ir" (nr));
    }
}

它和 set_bit 函数很相似,但也存在两点不同。第一处差异为 xor 操作而不是 or。第二处差异为 btc( LCTT 译注:原文为 bts,为作者笔误) 而不是 bts

目前,我们了解了最重要的体系特定的位数组操作,是时候看看一般的位图 API 了。

通用位操作

除了 arch/x86/include/asm/bitops.h 中体系特定的 API 外,Linux 内核提供了操作位数组的通用 API。正如我们本部分开头所了解的一样,我们可以在 include/linux/bitmap.h 头文件和 lib/bitmap.c 源文件中找到它。但在查看这些源文件之前,我们先看看 include/linux/bitops.h 头文件,其提供了一系列有用的宏,让我们看看它们当中一部分。

首先我们看看以下 4 个 宏:

  • for_each_set_bit
  • for_each_set_bit_from
  • for_each_clear_bit
  • for_each_clear_bit_from

所有这些宏都提供了遍历位数组中某些位集合的迭代器。第一个宏迭代那些被置位的位。第二个宏也是一样,但它是从某一个确定的位开始。最后两个宏做的一样,但是迭代那些被清位的位。让我们看看 for_each_set_bit 宏:

#define for_each_set_bit(bit, addr, size) \
    for ((bit) = find_first_bit((addr), (size));        \
         (bit) < (size);                    \
         (bit) = find_next_bit((addr), (size), (bit) + 1))

正如我们所看到的,它使用了三个参数,并展开为一个循环,该循环从作为 find_first_bit 函数返回结果的第一个置位开始,到小于给定大小的最后一个置位为止。

除了这四个宏, arch/x86/include/asm/bitops.h 也提供了 64-bit32-bit 变量循环的 API 等等。

下一个 头文件 提供了操作位数组的 API。例如,它提供了以下两个函数:

  • bitmap_zero;
  • bitmap_fill.

它们分别可以清除一个位数组和用 1 填充位数组。让我们看看 bitmap_zero 函数的实现:

static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
{
    if (small_const_nbits(nbits))
        *dst = 0UL;
    else {
        unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
        memset(dst, 0, len);
    }
}

首先我们可以看到对 nbits 的检查。 small_const_nbits 是一个定义在同一个头文件 的宏:

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

正如我们可以看到的,它检查 nbits 是否为编译期已知常量,并且其值不超过 BITS_PER_LONG64。如果位数目没有超过一个 long 变量的位数,我们可以仅仅设置为 0。在其他情况,我们需要计算有多少个需要填充位数组的 long 变量并且使用 memset 进行填充。

bitmap_fill 函数的实现和 biramp_zero 函数很相似,除了我们需要在给定的位数组中填写 0xff0b11111111

static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
{
    unsigned int nlongs = BITS_TO_LONGS(nbits);
    if (!small_const_nbits(nbits)) {
        unsigned int len = (nlongs - 1) * sizeof(unsigned long);
        memset(dst, 0xff,  len);
    }
    dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

除了 bitmap_fillbitmap_zeroinclude/linux/bitmap.h 头文件也提供了和 bitmap_zero 很相似的 bitmap_copy,只是仅仅使用 memcpy 而不是 memset 这点差异而已。它也提供了位数组的按位操作,像 bitmap_and, bitmap_or, bitamp_xor等等。我们不会探讨这些函数的实现了,因为如果你理解了本部分的所有内容,这些函数的实现是很容易理解的。无论如何,如果你对这些函数是如何实现的感兴趣,你可以打开并研究 include/linux/bitmap.h 头文件。

本部分到此为止。

链接


via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/bitmap.md

作者:0xAX 译者:cposture 校对:wxy

本文由 LCTT 原创翻译,Linux中国 荣誉推出

基数树 Radix tree

Trie

正如你所知道的,Linux内核提供了许多不同的库和函数,它们实现了不同的数据结构和算法。在这部分,我们将研究其中一种数据结构—— 基数树 Radix tree 。在 Linux 内核中,有两个文件与基数树的实现和API相关:

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 compressed trie ,而字典树是实现了关联数组接口并允许以 键值对 方式存储值的一种数据结构。这里的键通常是字符串,但可以使用任意数据类型。字典树因为它的节点而与 n叉树 不同。字典树的节点不存储键,而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子:

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

因此在这个例子中,我们可以看到一个有着两个键 gocat字典树 。压缩的字典树也叫做 基数树 ,它和 字典树 的不同之处在于,所有只有一个子节点的中间节点都被删除。

Linux 内核中的基数树是把值映射到整形键的一种数据结构。include/linux/radix-tree.h文件中的以下结构体描述了基数树:

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

这个结构体描述了一个基数树的根,它包含了3个域成员:

  • height - 树的高度;
  • gfp_mask - 告知如何执行动态内存分配;
  • rnode - 孩子节点指针.

我们第一个要讨论的字段是 gfp_mask

底层内核的内存动态分配函数以一组标志作为 gfp_mask ,用于描述如何执行动态内存分配。这些控制分配进程的 GFP_ 标志拥有以下值:( GF_NOIO 标志)意味着睡眠以及等待内存,( __GFP_HIGHMEM 标志)意味着高端内存能够被使用,( GFP_ATOMIC 标志)意味着分配进程拥有高优先级并不能睡眠等等。

  • GFP_NOIO - 睡眠等待内存
  • __GFP_HIGHMEM - 高端内存能够被使用;
  • GFP_ATOMIC - 分配进程拥有高优先级并且不能睡眠;

等等。

下一个字段是rnode

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

这个结构体包含的信息有父节点中的偏移以及到底端(叶节点)的高度、子节点的个数以及用于访问和释放节点的字段成员。这些字段成员描述如下:

  • path - 父节点中的偏移和到底端(叶节点)的高度
  • count - 子节点的个数;
  • parent - 父节点指针;
  • private_data - 由树的用户使用;
  • rcu_head - 用于释放节点;
  • private_list - 由树的用户使用;

radix_tree_node 的最后两个成员—— tagsslots 非常重要且令人关注。Linux 内核基数树的每个节点都包含了一组 指针槽 slots ,槽里存储着指向数据的指针。在Linux内核基数树的实现中,空槽存储的是 NULL 。Linux内核中的基数树也支持 标签 tags ,它与 radix_tree_node 结构体的 tags 字段相关联。有了标签,我们就可以对基数树中存储的记录以单个 比特位 bit 进行设置。

既然我们了解了基数树的结构,那么该是时候看一下它的API了。

Linux内核基数树API

我们从结构体的初始化开始。有两种方法初始化一个新的基数树。第一种是使用 RADIX_TREE 宏:

RADIX_TREE(name, gfp_mask);

正如你所看到的,我们传递了 name 参数,所以通过 RADIX_TREE 宏,我们能够定义和初始化基数树为给定的名字。RADIX_TREE 的实现很简单:

#define RADIX_TREE(name, mask) \
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { \
        .height = 0,              \
        .gfp_mask = (mask),       \
        .rnode = NULL,            \
}

RADIX_TREE 宏的开始,我们使用给定的名字定义 radix_tree_root 结构体实例,并使用给定的 mask 调用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏则是使用默认值和给定的mask对 radix_tree_root 结构体进行了初始化。

第二种方法是手动定义radix_tree_root结构体,并且将它和mask传给 INIT_RADIX_TREE 宏:

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏的定义如下:

#define INIT_RADIX_TREE(root, mask)  \
do {                                 \
        (root)->height = 0;          \
        (root)->gfp_mask = (mask);   \
        (root)->rnode = NULL;        \
} while (0)

RADIX_TREE_INIT宏所做的初始化工作一样,INIT_RADIX_TREE 宏使用默认值和给定的 mask 完成初始化工作。

接下来是用于向基数树插入和删除数据的两个函数:

  • radix_tree_insert;
  • radix_tree_delete;

第一个函数 radix_tree_insert 需要3个参数:

  • 基数树的根;
  • 索引键;
  • 插入的数据;

radix_tree_delete 函数需要和 radix_tree_insert 一样的一组参数,但是不需要传入要删除的数据。

基数树的搜索以两种方法实现:

  • radix_tree_lookup;
  • radix_tree_gang_lookup;
  • radix_tree_lookup_slot.

第一个函数radix_tree_lookup需要两个参数:

  • 基数树的根;
  • 索引键;

这个函数尝试在树中查找给定的键,并返回和该键相关联的记录。第二个函数 radix_tree_gang_lookup 有以下的函数签名:

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

它返回的是记录的个数。 results 中的结果,按键排序,并从第一个索引开始。返回的记录个数将不会超过 max_items 的值。

最后一个函数radix_tree_lookup_slot将会返回包含数据的指针槽。

链接


via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md

作者:[0xAX] 译者:cposture 校对:Mr小眼儿

本文由 LCTT 原创翻译,Linux中国 荣誉推出

Linux 内核中自己实现了双向链表,可以在 include/linux/list.h 找到定义。我们将会首先从双向链表数据结构开始介绍内核里的数据结构。为什么?因为它在内核里使用的很广泛,你只需要在 free-electrons.com 检索一下就知道了。

首先让我们看一下在 include/linux/types.h 里的主结构体:

struct list_head {
    struct list_head *next, *prev;
};

你可能注意到这和你以前见过的双向链表的实现方法是不同的。举个例子来说,在 glib 库里是这样实现的:

struct GList {
  gpointer data;
  GList *next;
  GList *prev;
};

通常来说一个链表结构会包含一个指向某个项目的指针。但是 Linux 内核中的链表实现并没有这样做。所以问题来了:链表在哪里保存数据呢?。实际上,内核里实现的链表是侵入式链表(Intrusive list)。侵入式链表并不在节点内保存数据-它的节点仅仅包含指向前后节点的指针,以及指向链表节点数据部分的指针——数据就是这样附加在链表上的。这就使得这个数据结构是通用的,使用起来就不需要考虑节点数据的类型了。

比如:

struct nmi_desc {
    spinlock_t lock;
    struct list_head head;
};

让我们看几个例子来理解一下在内核里是如何使用 list_head 的。如上所述,在内核里有很多很多不同的地方都用到了链表。我们来看一个在杂项字符驱动里面的使用的例子。在 drivers/char/misc.c 的杂项字符驱动 API 被用来编写处理小型硬件或虚拟设备的小驱动。这些驱动共享相同的主设备号:

#define MISC_MAJOR              10

但是都有各自不同的次设备号。比如:

ls -l /dev |  grep 10
crw-------   1 root root     10, 235 Mar 21 12:01 autofs
drwxr-xr-x  10 root root         200 Mar 21 12:01 cpu
crw-------   1 root root     10,  62 Mar 21 12:01 cpu_dma_latency
crw-------   1 root root     10, 203 Mar 21 12:01 cuse
drwxr-xr-x   2 root root         100 Mar 21 12:01 dri
crw-rw-rw-   1 root root     10, 229 Mar 21 12:01 fuse
crw-------   1 root root     10, 228 Mar 21 12:01 hpet
crw-------   1 root root     10, 183 Mar 21 12:01 hwrng
crw-rw----+  1 root kvm      10, 232 Mar 21 12:01 kvm
crw-rw----   1 root disk     10, 237 Mar 21 12:01 loop-control
crw-------   1 root root     10, 227 Mar 21 12:01 mcelog
crw-------   1 root root     10,  59 Mar 21 12:01 memory_bandwidth
crw-------   1 root root     10,  61 Mar 21 12:01 network_latency
crw-------   1 root root     10,  60 Mar 21 12:01 network_throughput
crw-r-----   1 root kmem     10, 144 Mar 21 12:01 nvram
brw-rw----   1 root disk      1,  10 Mar 21 12:01 ram10
crw--w----   1 root tty       4,  10 Mar 21 12:01 tty10
crw-rw----   1 root dialout   4,  74 Mar 21 12:01 ttyS10
crw-------   1 root root     10,  63 Mar 21 12:01 vga_arbiter
crw-------   1 root root     10, 137 Mar 21 12:01 vhci

现在让我们看看它是如何使用链表的。首先看一下结构体 miscdevice

struct miscdevice
{
      int minor;
      const char *name;
      const struct file_operations *fops;
      struct list_head list;
      struct device *parent;
      struct device *this_device;
      const char *nodename;
      mode_t mode;
};

可以看到结构体miscdevice的第四个变量list 是所有注册过的设备的链表。在源代码文件的开始可以看到这个链表的定义:

static LIST_HEAD(misc_list);

它实际上是对用list_head 类型定义的变量的扩展。

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

然后使用宏 LIST_HEAD_INIT 进行初始化,这会使用变量name 的地址来填充prevnext 结构体的两个变量。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

现在来看看注册杂项设备的函数misc_register。它在一开始就用函数 INIT_LIST_HEAD 初始化了miscdevice->list

INIT_LIST_HEAD(&misc->list);

作用和宏LIST_HEAD_INIT一样。

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

接下来,在函数device_create 创建了设备后,我们就用下面的语句将设备添加到设备链表:

list_add(&misc->list, &misc_list);

内核文件list.h 提供了向链表添加新项的 API 接口。我们来看看它的实现:

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

实际上就是使用3个指定的参数来调用了内部函数__list_add

  • new - 新项。
  • head - 新项将会插在head的后面
  • head->next - 插入前,head 后面的项。

__list_add的实现非常简单:

static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

这里,我们在prevnext 之间添加了一个新项。所以我们开始时用宏LIST_HEAD_INIT定义的misc 链表会包含指向miscdevice->list 的向前指针和向后指针。

这儿还有一个问题:如何得到列表的内容呢?这里有一个特殊的宏:

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

使用了三个参数:

  • ptr - 指向结构 list_head 的指针;
  • type - 结构体类型;
  • member - 在结构体内类型为list_head 的变量的名字;

比如说:

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

然后我们就可以使用p->minor 或者 p->name来访问miscdevice。让我们来看看list_entry 的实现:

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

如我们所见,它仅仅使用相同的参数调用了宏container_of。初看这个宏挺奇怪的:

#define container_of(ptr, type, member) ({                      \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

首先你可以注意到花括号内包含两个表达式。编译器会执行花括号内的全部语句,然后返回最后的表达式的值。

举个例子来说:

#include <stdio.h>

int main() {
    int i = 0;
    printf("i = %d\n", ({++i; ++i;}));
    return 0;
}

最终会打印出2

下一点就是typeof,它也很简单。就如你从名字所理解的,它仅仅返回了给定变量的类型。当我第一次看到宏container_of的实现时,让我觉得最奇怪的就是表达式((type *)0)中的0。实际上这个指针巧妙的计算了从结构体特定变量的偏移,这里的0刚好就是位宽里的零偏移。让我们看一个简单的例子:

#include <stdio.h>

struct s {
        int field1;
        char field2;
     char field3;
};

int main() {
    printf("%p\n", &((struct s*)0)->field3);
    return 0;
}

结果显示0x5

下一个宏offsetof会计算从结构体起始地址到某个给定结构字段的偏移。它的实现和上面类似:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

现在我们来总结一下宏container_of。只需给定结构体中list_head类型 字段的地址、名字和结构体容器的类型,它就可以返回结构体的起始地址。在宏定义的第一行,声明了一个指向结构体成员变量ptr的指针__mptr,并且把ptr 的地址赋给它。现在ptr__mptr 指向了同一个地址。从技术上讲我们并不需要这一行,但是它可以方便地进行类型检查。第一行保证了特定的结构体(参数type)包含成员变量member。第二行代码会用宏offsetof计算成员变量相对于结构体起始地址的偏移,然后从结构体的地址减去这个偏移,最后就得到了结构体。

当然了list_addlist_entry不是<linux/list.h>提供的唯一功能。双向链表的实现还提供了如下API:

  • list\_add
  • list\_add\_tail
  • list\_del
  • list\_replace
  • list\_move
  • list\_is\_last
  • list\_empty
  • list\_cut\_position
  • list\_splice
  • list\_for\_each
  • list\_for\_each\_entry

等等很多其它API。


via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/dlist.md

译者:Ezio 校对:Mr小眼儿

本文由 LCTT 原创编译,Linux中国 荣誉推出

介绍

我不会告诉你怎么在自己的电脑上去构建、安装一个定制化的 Linux 内核,这样的资料太多了,它们会对你有帮助。本文会告诉你当你在内核源码路径里敲下make 时会发生什么。

当我刚刚开始学习内核代码时,Makefile 是我打开的第一个文件,这个文件看起来真令人害怕 :)。那时候这个 Makefile 还只包含了1591 行代码,当我开始写本文时,内核已经是4.2.0的第三个候选版本 了。

这个 makefile 是 Linux 内核代码的根 makefile ,内核构建就始于此处。是的,它的内容很多,但是如果你已经读过内核源代码,你就会发现每个包含代码的目录都有一个自己的 makefile。当然了,我们不会去描述每个代码文件是怎么编译链接的,所以我们将只会挑选一些通用的例子来说明问题。而你不会在这里找到构建内核的文档、如何整洁内核代码、tags 的生成和交叉编译 相关的说明,等等。我们将从make 开始,使用标准的内核配置文件,到生成了内核镜像 bzImage 结束。

如果你已经很了解 make 工具那是最好,但是我也会描述本文出现的相关代码。

让我们开始吧!

(题图来自:adafruit.com)

编译内核前的准备

在开始编译前要进行很多准备工作。最主要的就是找到并配置好配置文件,make 命令要使用到的参数都需要从这些配置文件获取。现在就让我们深入内核的根 makefile

内核的根 Makefile 负责构建两个主要的文件:vmlinux (内核镜像可执行文件)和模块文件。内核的 Makefile 从定义如下变量开始:

VERSION = 4
PATCHLEVEL = 2
SUBLEVEL = 0
EXTRAVERSION = -rc3
NAME = Hurr durr I'ma sheep

这些变量决定了当前内核的版本,并且被使用在很多不同的地方,比如同一个 Makefile 中的 KERNELVERSION

KERNELVERSION = $(VERSION)$(if $(PATCHLEVEL),.$(PATCHLEVEL)$(if $(SUBLEVEL),.$(SUBLEVEL)))$(EXTRAVERSION)

接下来我们会看到很多ifeq 条件判断语句,它们负责检查传递给 make 的参数。内核的 Makefile 提供了一个特殊的编译选项 make help ,这个选项可以生成所有的可用目标和一些能传给 make 的有效的命令行参数。举个例子,make V=1 会在构建过程中输出详细的编译信息,第一个 ifeq 就是检查传递给 make 的 V=n 选项。

ifeq ("$(origin V)", "command line")
  KBUILD_VERBOSE = $(V)
endif
ifndef KBUILD_VERBOSE
  KBUILD_VERBOSE = 0
endif

ifeq ($(KBUILD_VERBOSE),1)
  quiet =
  Q =
else
  quiet=quiet_
  Q = @
endif

export quiet Q KBUILD_VERBOSE

如果 V=n 这个选项传给了 make ,系统就会给变量 KBUILD_VERBOSE 选项附上 V 的值,否则的话KBUILD_VERBOSE 就会为 0。然后系统会检查 KBUILD_VERBOSE 的值,以此来决定 quietQ 的值。符号 @ 控制命令的输出,如果它被放在一个命令之前,这条命令的输出将会是 CC scripts/mod/empty.o,而不是Compiling .... scripts/mod/empty.o(LCTT 译注:CC 在 makefile 中一般都是编译命令)。在这段最后,系统导出了所有的变量。

下一个 ifeq 语句检查的是传递给 make 的选项 O=/dir,这个选项允许在指定的目录 dir 输出所有的结果文件:

ifeq ($(KBUILD_SRC),)

ifeq ("$(origin O)", "command line")
  KBUILD_OUTPUT := $(O)
endif

ifneq ($(KBUILD_OUTPUT),)
saved-output := $(KBUILD_OUTPUT)
KBUILD_OUTPUT := $(shell mkdir -p $(KBUILD_OUTPUT) && cd $(KBUILD_OUTPUT) \
                                && /bin/pwd)
$(if $(KBUILD_OUTPUT),, \
     $(error failed to create output directory "$(saved-output)"))

sub-make: FORCE
    $(Q)$(MAKE) -C $(KBUILD_OUTPUT) KBUILD_SRC=$(CURDIR) \
    -f $(CURDIR)/Makefile $(filter-out _all sub-make,$(MAKECMDGOALS))

skip-makefile := 1
endif # ifneq ($(KBUILD_OUTPUT),)
endif # ifeq ($(KBUILD_SRC),)

系统会检查变量 KBUILD_SRC,它代表内核代码的顶层目录,如果它是空的(第一次执行 makefile 时总是空的),我们会设置变量 KBUILD_OUTPUT 为传递给选项 O 的值(如果这个选项被传进来了)。下一步会检查变量 KBUILD_OUTPUT ,如果已经设置好,那么接下来会做以下几件事:

  • 将变量 KBUILD_OUTPUT 的值保存到临时变量 saved-output
  • 尝试创建给定的输出目录;
  • 检查创建的输出目录,如果失败了就打印错误;
  • 如果成功创建了输出目录,那么就在新目录重新执行 make 命令(参见选项-C)。

下一个 ifeq 语句会检查传递给 make 的选项 CM

ifeq ("$(origin C)", "command line")
  KBUILD_CHECKSRC = $(C)
endif
ifndef KBUILD_CHECKSRC
  KBUILD_CHECKSRC = 0
endif

ifeq ("$(origin M)", "command line")
  KBUILD_EXTMOD := $(M)
endif

第一个选项 C 会告诉 makefile 需要使用环境变量 $CHECK 提供的工具来检查全部 c 代码,默认情况下会使用sparse。第二个选项 M 会用来编译外部模块(本文不做讨论)。

系统还会检查变量 KBUILD_SRC,如果 KBUILD_SRC 没有被设置,系统会设置变量 srctree.

ifeq ($(KBUILD_SRC),)
        srctree := .
endif

objtree := .
src     := $(srctree)
obj     := $(objtree)

export srctree objtree VPATH

这将会告诉 Makefile 内核的源码树就在执行 make 命令的目录,然后要设置 objtree 和其他变量为这个目录,并且将这些变量导出。接着就是要获取 SUBARCH 的值,这个变量代表了当前的系统架构(LCTT 译注:一般都指CPU 架构):

SUBARCH := $(shell uname -m | sed -e s/i.86/x86/ -e s/x86_64/x86/ \
                  -e s/sun4u/sparc64/ \
                  -e s/arm.*/arm/ -e s/sa110/arm/ \
                  -e s/s390x/s390/ -e s/parisc64/parisc/ \
                  -e s/ppc.*/powerpc/ -e s/mips.*/mips/ \
                  -e s/sh[234].*/sh/ -e s/aarch64.*/arm64/ )

如你所见,系统执行 uname 得到机器、操作系统和架构的信息。因为我们得到的是 uname 的输出,所以我们需要做一些处理再赋给变量 SUBARCH 。获得 SUBARCH 之后就要设置SRCARCHhfr-archSRCARCH 提供了硬件架构相关代码的目录,hfr-arch 提供了相关头文件的目录:

ifeq ($(ARCH),i386)
        SRCARCH := x86
endif
ifeq ($(ARCH),x86_64)
        SRCARCH := x86
endif

hdr-arch  := $(SRCARCH)

注意:ARCHSUBARCH 的别名。如果没有设置过代表内核配置文件路径的变量 KCONFIG_CONFIG,下一步系统会设置它,默认情况下就是 .config

KCONFIG_CONFIG  ?= .config
export KCONFIG_CONFIG

以及编译内核过程中要用到的 shell

CONFIG_SHELL := $(shell if [ -x "$$BASH" ]; then echo $$BASH; \
      else if [ -x /bin/bash ]; then echo /bin/bash; \
      else echo sh; fi ; fi)

接下来就要设置一组和编译内核的编译器相关的变量。我们会设置主机的 CC++ 的编译器及相关配置项:

HOSTCC       = gcc
HOSTCXX      = g++
HOSTCFLAGS   = -Wall -Wmissing-prototypes -Wstrict-prototypes -O2 -fomit-frame-pointer -std=gnu89
HOSTCXXFLAGS = -O2

接下来会去适配代表编译器的变量 CC,那为什么还要 HOST* 这些变量呢?这是因为 CC 是编译内核过程中要使用的目标架构的编译器,但是 HOSTCC 是要被用来编译一组 host 程序的(下面我们就会看到)。

然后我们就看到变量 KBUILD_MODULESKBUILD_BUILTIN 的定义,这两个变量决定了我们要编译什么东西(内核、模块或者两者):

KBUILD_MODULES :=
KBUILD_BUILTIN := 1

ifeq ($(MAKECMDGOALS),modules)
  KBUILD_BUILTIN := $(if $(CONFIG_MODVERSIONS),1)
endif

在这我们可以看到这些变量的定义,并且,如果们仅仅传递了 modulesmake,变量 KBUILD_BUILTIN 会依赖于内核配置选项 CONFIG_MODVERSIONS

下一步操作是引入下面的文件:

include scripts/Kbuild.include

文件 Kbuild 或者又叫做 Kernel Build System 是一个用来管理构建内核及其模块的特殊框架。kbuild 文件的语法与 makefile 一样。文件scripts/Kbuild.includekbuild 系统提供了一些常规的定义。因为我们包含了这个 kbuild 文件,我们可以看到和不同工具关联的这些变量的定义,这些工具会在内核和模块编译过程中被使用(比如链接器、编译器、来自 binutils 的二进制工具包 ,等等):

AS      = $(CROSS_COMPILE)as
LD      = $(CROSS_COMPILE)ld
CC      = $(CROSS_COMPILE)gcc
CPP     = $(CC) -E
AR      = $(CROSS_COMPILE)ar
NM      = $(CROSS_COMPILE)nm
STRIP       = $(CROSS_COMPILE)strip
OBJCOPY     = $(CROSS_COMPILE)objcopy
OBJDUMP     = $(CROSS_COMPILE)objdump
AWK     = awk
...
...
...

在这些定义好的变量后面,我们又定义了两个变量:USERINCLUDELINUXINCLUDE。他们包含了头文件的路径(第一个是给用户用的,第二个是给内核用的):

USERINCLUDE    := \
        -I$(srctree)/arch/$(hdr-arch)/include/uapi \
        -Iarch/$(hdr-arch)/include/generated/uapi \
        -I$(srctree)/include/uapi \
        -Iinclude/generated/uapi \
        -include $(srctree)/include/linux/kconfig.h

LINUXINCLUDE    := \
        -I$(srctree)/arch/$(hdr-arch)/include \
        ...

以及给 C 编译器的标准标志:

KBUILD_CFLAGS   := -Wall -Wundef -Wstrict-prototypes -Wno-trigraphs \
           -fno-strict-aliasing -fno-common \
           -Werror-implicit-function-declaration \
           -Wno-format-security \
           -std=gnu89

这并不是最终确定的编译器标志,它们还可以在其他 makefile 里面更新(比如 arch/ 里面的 kbuild)。变量定义完之后,全部会被导出供其他 makefile 使用。

下面的两个变量 RCS_FIND_IGNORERCS_TAR_IGNORE 包含了被版本控制系统忽略的文件:

export RCS_FIND_IGNORE := \( -name SCCS -o -name BitKeeper -o -name .svn -o    \
              -name CVS -o -name .pc -o -name .hg -o -name .git \) \
              -prune -o
export RCS_TAR_IGNORE := --exclude SCCS --exclude BitKeeper --exclude .svn \
             --exclude CVS --exclude .pc --exclude .hg --exclude .git

这就是全部了,我们已经完成了所有的准备工作,下一个点就是如果构建vmlinux

直面内核构建

现在我们已经完成了所有的准备工作,根 makefile(注:内核根目录下的 makefile)的下一步工作就是和编译内核相关的了。在这之前,我们不会在终端看到 make 命令输出的任何东西。但是现在编译的第一步开始了,这里我们需要从内核根 makefile 的 598 行开始,这里可以看到目标vmlinux

all: vmlinux
    include arch/$(SRCARCH)/Makefile

不要操心我们略过的从 export RCS_FIND_IGNORE.....all: vmlinux..... 这一部分 makefile 代码,他们只是负责根据各种配置文件(make *.config)生成不同目标内核的,因为之前我就说了这一部分我们只讨论构建内核的通用途径。

目标 all: 是在命令行如果不指定具体目标时默认使用的目标。你可以看到这里包含了架构相关的 makefile(在这里就指的是 arch/x86/Makefile)。从这一时刻起,我们会从这个 makefile 继续进行下去。如我们所见,目标 all 依赖于根 makefile 后面声明的 vmlinux

vmlinux: scripts/link-vmlinux.sh $(vmlinux-deps) FORCE

vmlinux 是 linux 内核的静态链接可执行文件格式。脚本 scripts/link-vmlinux.sh 把不同的编译好的子模块链接到一起形成了 vmlinux。

第二个目标是 vmlinux-deps,它的定义如下:

vmlinux-deps := $(KBUILD_LDS) $(KBUILD_VMLINUX_INIT) $(KBUILD_VMLINUX_MAIN)

它是由内核代码下的每个顶级目录的 built-in.o 组成的。之后我们还会检查内核所有的目录,kbuild 会编译各个目录下所有的对应 $(obj-y) 的源文件。接着调用 $(LD) -r 把这些文件合并到一个 build-in.o 文件里。此时我们还没有vmlinux-deps,所以目标 vmlinux 现在还不会被构建。对我而言 vmlinux-deps 包含下面的文件:

arch/x86/kernel/vmlinux.lds arch/x86/kernel/head_64.o
arch/x86/kernel/head64.o    arch/x86/kernel/head.o
init/built-in.o             usr/built-in.o
arch/x86/built-in.o         kernel/built-in.o
mm/built-in.o               fs/built-in.o
ipc/built-in.o              security/built-in.o
crypto/built-in.o           block/built-in.o
lib/lib.a                   arch/x86/lib/lib.a
lib/built-in.o              arch/x86/lib/built-in.o
drivers/built-in.o          sound/built-in.o
firmware/built-in.o         arch/x86/pci/built-in.o
arch/x86/power/built-in.o   arch/x86/video/built-in.o
net/built-in.o

下一个可以被执行的目标如下:

$(sort $(vmlinux-deps)): $(vmlinux-dirs) ;
$(vmlinux-dirs): prepare scripts
    $(Q)$(MAKE) $(build)=$@

就像我们看到的,vmlinux-dir 依赖于两部分:preparescripts。第一个 prepare 定义在内核的根 makefile 中,准备工作分成三个阶段:

prepare: prepare0
prepare0: archprepare FORCE
    $(Q)$(MAKE) $(build)=.
archprepare: archheaders archscripts prepare1 scripts_basic

prepare1: prepare2 $(version_h) include/generated/utsrelease.h \
                   include/config/auto.conf
    $(cmd_crmodverdir)
prepare2: prepare3 outputmakefile asm-generic

第一个 prepare0 展开到 archprepare ,后者又展开到 archheaderarchscripts,这两个变量定义在 x86_64 相关的 Makefile。让我们看看这个文件。x86_64 特定的 makefile 从变量定义开始,这些变量都是和特定架构的配置文件 (defconfig,等等)有关联。在定义了编译 16-bit 代码的编译选项之后,根据变量 BITS 的值,如果是 32, 汇编代码、链接器、以及其它很多东西(全部的定义都可以在arch/x86/Makefile找到)对应的参数就是 i386,而 64 就对应的是 x86_84

第一个目标是 makefile 生成的系统调用列表(syscall table)中的 archheaders

archheaders:
    $(Q)$(MAKE) $(build)=arch/x86/entry/syscalls all

第二个目标是 makefile 里的 archscripts

archscripts: scripts_basic
    $(Q)$(MAKE) $(build)=arch/x86/tools relocs

我们可以看到 archscripts 是依赖于根 Makefile里的scripts_basic 。首先我们可以看出 scripts_basic 是按照 scripts/basic 的 makefile 执行 make 的:

scripts_basic:
    $(Q)$(MAKE) $(build)=scripts/basic

scripts/basic/Makefile 包含了编译两个主机程序 fixdepbin2 的目标:

hostprogs-y := fixdep
hostprogs-$(CONFIG_BUILD_BIN2C)     += bin2c
always      := $(hostprogs-y)

$(addprefix $(obj)/,$(filter-out fixdep,$(always))): $(obj)/fixdep

第一个工具是 fixdep:用来优化 gcc 生成的依赖列表,然后在重新编译源文件的时候告诉make。第二个工具是 bin2c,它依赖于内核配置选项 CONFIG_BUILD_BIN2C,并且它是一个用来将标准输入接口(LCTT 译注:即 stdin)收到的二进制流通过标准输出接口(即:stdout)转换成 C 头文件的非常小的 C 程序。你可能注意到这里有些奇怪的标志,如 hostprogs-y 等。这个标志用于所有的 kbuild 文件,更多的信息你可以从documentation 获得。在我们这里, hostprogs-y 告诉 kbuild 这里有个名为 fixed 的程序,这个程序会通过和 Makefile 相同目录的 fixdep.c 编译而来。

执行 make 之后,终端的第一个输出就是 kbuild 的结果:

$ make
  HOSTCC  scripts/basic/fixdep

当目标 script_basic 被执行,目标 archscripts 就会 make arch/x86/tools 下的 makefile 和目标 relocs:

$(Q)$(MAKE) $(build)=arch/x86/tools relocs

包含了重定位 的信息的代码 relocs_32.crelocs_64.c 将会被编译,这可以在make 的输出中看到:

  HOSTCC  arch/x86/tools/relocs_32.o
  HOSTCC  arch/x86/tools/relocs_64.o
  HOSTCC  arch/x86/tools/relocs_common.o
  HOSTLD  arch/x86/tools/relocs

在编译完 relocs.c 之后会检查 version.h:

$(version_h): $(srctree)/Makefile FORCE
    $(call filechk,version.h)
    $(Q)rm -f $(old_version_h)

我们可以在输出看到它:

CHK     include/config/kernel.release

以及在内核的根 Makefiel 使用 arch/x86/include/generated/asm 的目标 asm-generic 来构建 generic 汇编头文件。在目标 asm-generic 之后,archprepare 就完成了,所以目标 prepare0 会接着被执行,如我上面所写:

prepare0: archprepare FORCE
    $(Q)$(MAKE) $(build)=.

注意 build,它是定义在文件 scripts/Kbuild.include,内容是这样的:

build := -f $(srctree)/scripts/Makefile.build obj

或者在我们的例子中,它就是当前源码目录路径:.

$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.build obj=.

脚本 scripts/Makefile.build 通过参数 obj 给定的目录找到 Kbuild 文件,然后引入 kbuild 文件:

include $(kbuild-file)

并根据这个构建目标。我们这里 . 包含了生成 kernel/bounds.sarch/x86/kernel/asm-offsets.sKbuild 文件。在此之后,目标 prepare 就完成了它的工作。 vmlinux-dirs 也依赖于第二个目标 scripts ,它会编译接下来的几个程序:filealiasmk_elfconfigmodpost 等等。之后,scripts/host-programs 就可以开始编译我们的目标 vmlinux-dirs 了。

首先,我们先来理解一下 vmlinux-dirs 都包含了那些东西。在我们的例子中它包含了下列内核目录的路径:

init usr arch/x86 kernel mm fs ipc security crypto block
drivers sound firmware arch/x86/pci arch/x86/power
arch/x86/video net lib arch/x86/lib

我们可以在内核的根 Makefile 里找到 vmlinux-dirs 的定义:

vmlinux-dirs    := $(patsubst %/,%,$(filter %/, $(init-y) $(init-m) \
             $(core-y) $(core-m) $(drivers-y) $(drivers-m) \
             $(net-y) $(net-m) $(libs-y) $(libs-m)))

init-y      := init/
drivers-y   := drivers/ sound/ firmware/
net-y       := net/
libs-y      := lib/
...
...
...

这里我们借助函数 patsubstfilter去掉了每个目录路径里的符号 /,并且把结果放到 vmlinux-dirs 里。所以我们就有了 vmlinux-dirs 里的目录列表,以及下面的代码:

$(vmlinux-dirs): prepare scripts
    $(Q)$(MAKE) $(build)=$@

符号 $@ 在这里代表了 vmlinux-dirs,这就表明程序会递归遍历从 vmlinux-dirs 以及它内部的全部目录(依赖于配置),并且在对应的目录下执行 make 命令。我们可以在输出看到结果:

  CC      init/main.o
  CHK     include/generated/compile.h
  CC      init/version.o
  CC      init/do_mounts.o
  ...
  CC      arch/x86/crypto/glue_helper.o
  AS      arch/x86/crypto/aes-x86_64-asm_64.o
  CC      arch/x86/crypto/aes_glue.o
  ...
  AS      arch/x86/entry/entry_64.o
  AS      arch/x86/entry/thunk_64.o
  CC      arch/x86/entry/syscall_64.o

每个目录下的源代码将会被编译并且链接到 built-io.o 里:

$ find . -name built-in.o
./arch/x86/crypto/built-in.o
./arch/x86/crypto/sha-mb/built-in.o
./arch/x86/net/built-in.o
./init/built-in.o
./usr/built-in.o
...
...

好了,所有的 built-in.o 都构建完了,现在我们回到目标 vmlinux 上。你应该还记得,目标 vmlinux 是在内核的根makefile 里。在链接 vmlinux 之前,系统会构建 samples, Documentation 等等,但是如上文所述,我不会在本文描述这些。

vmlinux: scripts/link-vmlinux.sh $(vmlinux-deps) FORCE
    ...
    ...
    +$(call if_changed,link-vmlinux)

你可以看到,调用脚本 scripts/link-vmlinux.sh 的主要目的是把所有的 built-in.o 链接成一个静态可执行文件,和生成 System.map。 最后我们来看看下面的输出:

  LINK    vmlinux
  LD      vmlinux.o
  MODPOST vmlinux.o
  GEN     .version
  CHK     include/generated/compile.h
  UPD     include/generated/compile.h
  CC      init/version.o
  LD      init/built-in.o
  KSYM    .tmp_kallsyms1.o
  KSYM    .tmp_kallsyms2.o
  LD      vmlinux
  SORTEX  vmlinux
  SYSMAP  System.map

vmlinuxSystem.map 生成在内核源码树根目录下。

$ ls vmlinux System.map 
System.map  vmlinux

这就是全部了,vmlinux 构建好了,下一步就是创建 bzImage.

制作bzImage

bzImage 就是压缩了的 linux 内核镜像。我们可以在构建了 vmlinux 之后通过执行 make bzImage 获得bzImage。同时我们可以仅仅执行 make 而不带任何参数也可以生成 bzImage ,因为它是在 arch/x86/kernel/Makefile 里预定义的、默认生成的镜像:

all: bzImage

让我们看看这个目标,它能帮助我们理解这个镜像是怎么构建的。我已经说过了 bzImage 是被定义在 arch/x86/kernel/Makefile,定义如下:

bzImage: vmlinux
    $(Q)$(MAKE) $(build)=$(boot) $(KBUILD_IMAGE)
    $(Q)mkdir -p $(objtree)/arch/$(UTS_MACHINE)/boot
    $(Q)ln -fsn ../../x86/boot/bzImage $(objtree)/arch/$(UTS_MACHINE)/boot/$@

在这里我们可以看到第一次为 boot 目录执行 make,在我们的例子里是这样的:

boot := arch/x86/boot

现在的主要目标是编译目录 arch/x86/bootarch/x86/boot/compressed 的代码,构建 setup.binvmlinux.bin,最后用这两个文件生成 bzImage。第一个目标是定义在 arch/x86/boot/Makefile$(obj)/setup.elf:

$(obj)/setup.elf: $(src)/setup.ld $(SETUP_OBJS) FORCE
    $(call if_changed,ld)

我们已经在目录 arch/x86/boot 有了链接脚本 setup.ld,和扩展到 boot 目录下全部源代码的变量 SETUP_OBJS 。我们可以看看第一个输出:

  AS      arch/x86/boot/bioscall.o
  CC      arch/x86/boot/cmdline.o
  AS      arch/x86/boot/copy.o
  HOSTCC  arch/x86/boot/mkcpustr
  CPUSTR  arch/x86/boot/cpustr.h
  CC      arch/x86/boot/cpu.o
  CC      arch/x86/boot/cpuflags.o
  CC      arch/x86/boot/cpucheck.o
  CC      arch/x86/boot/early_serial_console.o
  CC      arch/x86/boot/edd.o

下一个源码文件是 arch/x86/boot/header.S,但是我们不能现在就编译它,因为这个目标依赖于下面两个头文件:

$(obj)/header.o: $(obj)/voffset.h $(obj)/zoffset.h

第一个头文件 voffset.h 是使用 sed 脚本生成的,包含用 nm 工具从 vmlinux 获取的两个地址:

#define VO__end 0xffffffff82ab0000
#define VO__text 0xffffffff81000000

这两个地址是内核的起始和结束地址。第二个头文件 zoffset.harch/x86/boot/compressed/Makefile 可以看出是依赖于目标 vmlinux的:

$(obj)/zoffset.h: $(obj)/compressed/vmlinux FORCE
    $(call if_changed,zoffset)

目标 $(obj)/compressed/vmlinux 依赖于 vmlinux-objs-y —— 说明需要编译目录 arch/x86/boot/compressed 下的源代码,然后生成 vmlinux.binvmlinux.bin.bz2,和编译工具 mkpiggy。我们可以在下面的输出看出来:

  LDS     arch/x86/boot/compressed/vmlinux.lds
  AS      arch/x86/boot/compressed/head_64.o
  CC      arch/x86/boot/compressed/misc.o
  CC      arch/x86/boot/compressed/string.o
  CC      arch/x86/boot/compressed/cmdline.o
  OBJCOPY arch/x86/boot/compressed/vmlinux.bin
  BZIP2   arch/x86/boot/compressed/vmlinux.bin.bz2
  HOSTCC  arch/x86/boot/compressed/mkpiggy

vmlinux.bin 是去掉了调试信息和注释的 vmlinux 二进制文件,加上了占用了 u32 (LCTT 译注:即4-Byte)的长度信息的 vmlinux.bin.all 压缩后就是 vmlinux.bin.bz2。其中 vmlinux.bin.all 包含了 vmlinux.binvmlinux.relocs(LCTT 译注:vmlinux 的重定位信息),其中 vmlinux.relocsvmlinux 经过程序 relocs 处理之后的 vmlinux 镜像(见上文所述)。我们现在已经获取到了这些文件,汇编文件 piggy.S 将会被 mkpiggy 生成、然后编译:

  MKPIGGY arch/x86/boot/compressed/piggy.S
  AS      arch/x86/boot/compressed/piggy.o

这个汇编文件会包含经过计算得来的、压缩内核的偏移信息。处理完这个汇编文件,我们就可以看到 zoffset 生成了:

  ZOFFSET arch/x86/boot/zoffset.h

现在 zoffset.hvoffset.h 已经生成了,arch/x86/boot 里的源文件可以继续编译:

  AS      arch/x86/boot/header.o
  CC      arch/x86/boot/main.o
  CC      arch/x86/boot/mca.o
  CC      arch/x86/boot/memory.o
  CC      arch/x86/boot/pm.o
  AS      arch/x86/boot/pmjump.o
  CC      arch/x86/boot/printf.o
  CC      arch/x86/boot/regs.o
  CC      arch/x86/boot/string.o
  CC      arch/x86/boot/tty.o
  CC      arch/x86/boot/video.o
  CC      arch/x86/boot/video-mode.o
  CC      arch/x86/boot/video-vga.o
  CC      arch/x86/boot/video-vesa.o
  CC      arch/x86/boot/video-bios.o

所有的源代码会被编译,他们最终会被链接到 setup.elf

  LD      arch/x86/boot/setup.elf

或者:

ld -m elf_x86_64   -T arch/x86/boot/setup.ld arch/x86/boot/a20.o arch/x86/boot/bioscall.o arch/x86/boot/cmdline.o arch/x86/boot/copy.o arch/x86/boot/cpu.o arch/x86/boot/cpuflags.o arch/x86/boot/cpucheck.o arch/x86/boot/early_serial_console.o arch/x86/boot/edd.o arch/x86/boot/header.o arch/x86/boot/main.o arch/x86/boot/mca.o arch/x86/boot/memory.o arch/x86/boot/pm.o arch/x86/boot/pmjump.o arch/x86/boot/printf.o arch/x86/boot/regs.o arch/x86/boot/string.o arch/x86/boot/tty.o arch/x86/boot/video.o arch/x86/boot/video-mode.o arch/x86/boot/version.o arch/x86/boot/video-vga.o arch/x86/boot/video-vesa.o arch/x86/boot/video-bios.o -o arch/x86/boot/setup.elf

最后的两件事是创建包含目录 arch/x86/boot/* 下的编译过的代码的 setup.bin

objcopy  -O binary arch/x86/boot/setup.elf arch/x86/boot/setup.bin

以及从 vmlinux 生成 vmlinux.bin :

objcopy  -O binary -R .note -R .comment -S arch/x86/boot/compressed/vmlinux arch/x86/boot/vmlinux.bin

最最后,我们编译主机程序 arch/x86/boot/tools/build.c,它将会用来把 setup.binvmlinux.bin 打包成 bzImage:

arch/x86/boot/tools/build arch/x86/boot/setup.bin arch/x86/boot/vmlinux.bin arch/x86/boot/zoffset.h arch/x86/boot/bzImage

实际上 bzImage 就是把 setup.binvmlinux.bin 连接到一起。最终我们会看到输出结果,就和那些用源码编译过内核的同行的结果一样:

Setup is 16268 bytes (padded to 16384 bytes).
System is 4704 kB
CRC 94a88f9a
Kernel: arch/x86/boot/bzImage is ready  (#5)

全部结束。

结论

这就是本文的结尾部分。本文我们了解了编译内核的全部步骤:从执行 make 命令开始,到最后生成 bzImage。我知道,linux 内核的 makefile 和构建 linux 的过程第一眼看起来可能比较迷惑,但是这并不是很难。希望本文可以帮助你理解构建 linux 内核的整个流程。

链接


via: https://github.com/0xAX/linux-insides/blob/master/Misc/how_kernel_compiled.md

译者:oska874 校对:wxy

本文由 LCTT 原创翻译,Linux中国 荣誉推出