文章目录
前言
内核中有很多判断条件在正常情况下的结果都是固定的,除非极其罕见的场景才会改变,通常单个的这种判断的代价很低可以忽略,但是如果这种判断数量巨大且被频繁执行,那就会带来性能损失了。
对于这种情况内核提供了likely/unlikely来优化这种情况,内核中这两个宏用于帮助编译器和CPU进行分支预测:likely()和unlikely()。从它们的名称可以看出,它们用于对代码中的条件进行注释,表示它们评估为真的可能性。但是,如果错误地标记为likely()的条件实际上是unlikely(),或者反之,会影响性能,因为CPU可能会预取错误的指令。
likely/unlikely是给编译器的提示,让它生成的指令能够使分支预测更有利于"likely"(可能性高)分支。如果预测正确,那么跳转指令基本上是免费的,不需要花费任何周期。然而,如果预测错误,就意味着处理器流水线需要被清空,可能会花费多个周期。只要预测大部分时间是正确的,这对性能来说通常是有益的。
likely/unlikely是程序员在代码植入提示信息,提高分支预测的准确性,但还是会分支预测失败。
在内核代码中,有很多分支判断条件,它们在绝大多数情形下,都是不成立的,比如:
if (unlikely(condition)) { /* condition 在极少数情况下才会成立 */
do unlikely code
}else{
do likely code
}
现代cpu都有预测功能,变量的判断有可能会造成硬件预测失败,影响流水线性能。虽然有likely和unlikely,但还是会有小概率的预测失败。
尽管我们已经加上unlikely修饰来进行优化,但是,读取 condition 仍然要访问内存,仍然需要用到cache;另外,也会CPU分支预测失败。虽然少数这样的代码影响不大,但当这样的条件判断代码(如内核中大量的tracepoint)增多的时候,将对cache会造成很大压力,所有这些代码导致的cache miss,以及CPU分支预测失败,所造成的性能损失,就变得可观起来。因此,内核需要一种方案来取消分支预测,来解决这样的问题。
如果某个判断分支在大多数情况下都是只走一个特定路径,除了加上likely和unlikely告诉编译器进行优化,是否还有其他方法?
内核开发者就开发了这样一种新的方法:通过动态替换内存中的代码段,去掉分支的判断条件,让代码根据动态设置要么直接执行a分支,要么直接执行b分支。
这种技术在底层是通过将汇编中的nop指令替换成jmp,或者将jmp指令替换成nop实现的。具体的实现和体系相关。
去掉分支的判断条件,取消分支预测的方案 :
Static keys + jump label
修改分支处的代码来消除条件分支,取消分支预测,提高系统性能。
依靠运行时修改代码而不是依靠状态数据来控制执行流。
Static keys通过使用GCC特性和代码补丁技术,允许在性能敏感的快速路径内核代码中包含不常用的功能。以下是一个快速示例:
struct static_key key = STATIC_KEY_INIT_FALSE;
...
if (static_key_false(&key)) //动态的将二进制代码修改掉,将if代码段去掉,这样一个分支预测就不存在了
do unlikely code //nop 指令
else
do likely code
...
static_key_slow_inc(); //enable nop->jmp
...
static_key_slow_dec(); //disable jmp->nop
...
运行时直接修改代码,当enable的时候把代码nop修改为jmp,当disable的时候把代码jmp修改为nop。
static_key_false()分支将以对可能代码路径的影响尽可能小的方式生成到代码中。
内核的static-key机制就是为了优化这种场景,其优化的结果是:对于大多数情况,对应的判断被优化为一个NOP指令,在非常有场景的时候就变成jump XXX一类的指令,使得对应的代码段得到执行。
只有在我们确定不经常变化的变量的判断上才能用这种方式取消分支预测。
tracepoint就是我们确定不经常变化的变量,它大部分情况下都是disable的,基本只有我们调试跟踪的时候才会开启tracepoint。
比如tracepoints,大部分情况下都是disable的,如果对于tracepoints我们每次都用if条件判断是否开启,那会有分支预测的开销,即使加上likely/unlikely修饰,仍然会有分支预测的开销。对于这种情况使用Static keys机制,动态的将二进制代码修改掉,将if代码段去掉,这样一个分支预测就不存在了,tracepoints disable的时候是 nop 指令,tracepoints enable的时候是 jmp 指令。
一、asm goto
目前,跟踪点(tracepoints)是使用条件分支实现的。条件检查需要针对每个跟踪点检查一个全局变量。尽管此检查的开销很小,但在内存缓存面临压力时(这些全局变量的内存缓存行可能与其他内存访问共享),它会增加。随着内核中跟踪点数量的增加,这种开销可能变得更加严重。此外,跟踪点通常处于休眠状态(禁用),并不直接提供内核功能。因此,尽可能减少它们的影响是非常可取的。虽然跟踪点是这项工作的最初动机,但其他内核代码路径也应该能够利用静态键机制。
gcc(v4.5)引入了一个新的’asm goto’语句,允许跳转到一个标签:
这种形式的asm语句存在一个重要限制,即我们无法支持跳转指令的输出重装载,因此无法支持来自跳转asm的输出。
不过,内核开发人员的使用情况实际上并不需要输出。他们希望进行一些代码修补,以实现几乎零成本的跟踪。他们的使用情况看起来类似于:
+#define TRACE1(NUM) \
+ do { \
+ asm goto ("0: nop;" \
+ ".pushsection trace_table;" \
+ ".long 0b, %l0;" \
+ ".popsection" \
+ : : : : trace#NUM); \
+ if (0) { trace#NUM: trace(); } \
+ } while (0)
gcc编译器提供了asm goto的机制,使得可以在asm goto的基础上构建出jump label。
在内核中使用TRACE宏的实例会被散布开来。预期编译器会重新排列这些块,使得直线代码路径通常只包含nop指令。但我们在trace_table部分记录了足够的信息,允许将nop指令修补为直接跳转到trace#NUM标签,该标签调用trace函数,然后再跳回直线代码。
使用’asm goto’,我们可以创建默认情况下要么被执行要么不被执行的分支,而无需检查内存。然后,在运行时,我们可以对分支位置进行修补以改变分支方向。
例如,如果我们有一个默认情况下被禁用的简单分支:
if (static_key_false(&key))
printk("I am the true branch\n");
因此,默认情况下不会发出’printk’。生成的代码将由一个原子的’no-op’指令(在x86上为5个字节)组成,位于直线代码路径中。当分支被“翻转”时,我们将在直线代码路径中的’no-op’处用一个’jump’指令修补,以跳转到分支外的真分支。因此,改变分支方向是昂贵的,但分支选择基本上是“免费”的。这是这种优化的基本权衡。
这种低级修补机制称为“跳转标签修补”,为静态键机制提供了基础。
二、API使用
2.1 低版本API
为了利用这种优化,首先必须定义一个键:
struct static_key key;
初始化键的方式如下:
struct static_key key = STATIC_KEY_INIT_TRUE;
或者:
struct static_key key = STATIC_KEY_INIT_FALSE;
如果键没有初始化,它默认为false。‘struct static_key’必须是一个’global’,也就是说,它不能在堆栈上分配或在运行时动态分配。
然后在代码中使用该键:
if (static_key_false(&key))
do unlikely code
else
do likely code
Or:
if (static_key_true(&key))
do likely code
else
do unlikely code
通过’STATIC_KEY_INIT_FALSE’初始化的键必须在’static_key_false()'结构中使用。同样,通过’STATIC_KEY_INIT_TRUE’初始化的键必须在’static_key_true()'结构中使用。一个键可以在多个分支中使用,但所有分支的使用方式必须与键的初始化方式匹配。
然后可以通过以下方式切换分支:
static_key_slow_inc(&key); // branch = true nop->jmp
...
static_key_slow_dec(&key); // brach = false jmp->nop
因此,'static_key_slow_inc()'表示“将分支变为true”,'static_key_slow_dec()'表示“将分支变为false”,并进行适当的引用计数。例如,如果键初始化为true,调用static_key_slow_dec()将将分支切换为false。随后的static_key_slow_inc()将再次将分支更改为true。同样,如果键初始化为false,static_key_slow_inc()将将分支更改为true。然后,static_key_slow_dec()将再次将分支变为false。
内核中的一个示例用法是实现跟踪点:
static inline void trace_##name(proto) \
{ \
if (static_key_false(&__tracepoint_##name.key)) \
__DO_TRACE(&__tracepoint_##name, \
TP_PROTO(data_proto), \
TP_ARGS(data_args), \
TP_CONDITION(cond)); \
}
跟踪点默认情况下是禁用的,并且可以放置在内核的性能关键部分。因此,通过使用静态键,当未使用时,跟踪点几乎没有任何影响。
2.2 高版本API
已弃用的API:
直接使用struct static_key现在已被弃用。此外,static_key_{true,false}()也已被弃用。请不要使用以下内容:
struct static_key false = STATIC_KEY_INIT_FALSE;
struct static_key true = STATIC_KEY_INIT_TRUE;
static_key_true()
static_key_false()
更新后的API替代方案如下:
DEFINE_STATIC_KEY_TRUE(key);
DEFINE_STATIC_KEY_FALSE(key);
DEFINE_STATIC_KEY_ARRAY_TRUE(keys, count);
DEFINE_STATIC_KEY_ARRAY_FALSE(keys, count);
static_branch_likely()
static_branch_unlikely()
静态键(Static keys)通过GCC特性和代码修补技术,在性能敏感的快速路径内核代码中实现了包含不常用功能的方式。以下是一个快速示例:
DEFINE_STATIC_KEY_FALSE(key);
...
if (static_branch_unlikely(&key))
do unlikely code
else
do likely code
...
static_branch_enable(&key);
...
static_branch_disable(&key);
...
static_branch_unlikely()分支将以对可能代码路径的最小影响生成到代码中。
三、jump label
jump_lable屏蔽不同体系更改机器代码的不同,向上提供一个统一接口。不同体系会提供给jump_lable一个体系相关的实现。
jump_lable的实现原理很简单,就是通过替换内存中机器代码的nop空指令为jmp指令,或者替换机器代码的jmp指令为nop空指令,实现分支的切换。
config JUMP_LABEL
bool "Optimize very unlikely/likely branches"
depends on HAVE_ARCH_JUMP_LABEL
该选项启用了一种透明的分支优化,使得内核中某些几乎总是为真或几乎总是为假的分支条件执行起来更加廉价。
某些对性能敏感的内核代码,例如跟踪点、调度功能、网络代码和KVM,具有此类分支并包含对此优化技术的支持。
如果检测到编译器支持 “asm goto”,内核将仅使用无操作(nop)指令编译这样的分支。当条件标志切换为真时,nop 指令将被转换为跳转指令,以执行条件块中的指令。
这种技术降低了处理器分支预测的开销和压力,通常使内核更快。条件的更新速度较慢,但这些情况非常罕见。
内核中充斥着几乎从不改变结果的测试。一个经典的例子是跟踪点(tracepoint),在运行中的系统上几乎从不禁用它们,只有非常罕见的例外。长期以来一直有兴趣优化这些地方的测试;从2.6.37开始,“跳转标签”(jump label)功能将完全消除这些测试。
考虑一个典型跟踪点的定义,尽管其中有一些预处理器的混乱,但大致如下所示:
static inline trace_foo(args)
{
if (unlikely(trace_foo_enabled))
goto do_trace;
return;
do_trace:
/* Actually do tracing stuff */
}
即使有了unlikey优化,既然有if判断,cpu的分支预测就有可能失败,再者do_trace在代码上离if这么近,即使编译器再聪明,二进制代码的do_trace也不会离前面的代码太远的,这样由于局部性原理和cpu的预取机制,do_trace的代码很有可能就被预取入了cpu的cache,就算我们从来不打算trace代码也是如此。
我们需要的是如果不开启trace,那么do_trace永远不被欲取或者被预测,唯一的办法就是去掉if判断,永远不调用goto语句,像下面这样:
static inline trace_foo(args)
{
return;
do_trace:
/* Actually do tracing stuff */
}
单个跟踪点的测试成本基本上为零。内核中的跟踪点数量正在增加,每个跟踪点都会增加一个新的测试。每个测试都必须从内存中获取一个值,增加了对缓存的压力,降低了性能。鉴于该值几乎从不改变,找到一种优化"跟踪点禁用"情况的方法将是不错的。
好处是JUMP_LABEL()不必像那样实现。相反,它可以在一个特殊的表中记录测试的位置和键值,以及简单地插入一个空操作指令。这将把测试(和跟踪点)在常见的"未启用"情况下的成本降低到零。大部分时间,跟踪点将永远不会被启用,并且省略的测试也不会被注意到。
棘手的部分出现在某人想要启用跟踪点时。现在,改变其状态需要调用一对特殊函数之一:
void enable_jump_label(void *key);
void disable_jump_label(void *key);
调用enable_jump_label()将在跳转标签表中查找键,然后用"goto label"的汇编等价物替换特殊的空操作指令,从而启用跟踪点。禁用跳转标签将导致空操作指令被恢复。
使用jump label后:
enum jump_label_type {
JUMP_LABEL_DISABLE = 0,
JUMP_LABEL_ENABLE,
};
()如果对于某一个函数不需要trace(JUMP_LABEL_DISABLE ),内核只需要执行一个操作将asm goto附近的代码改掉即可,比如改称下面这样:
static inline trace_foo(args)
{
jmp 0;
0:
nop;
return;
do_trace:
/* Actually do tracing stuff */
}
(2)如果需要trace(JUMP_LABEL_ENABLE),那么就改成:
static inline trace_foo(args)
{
jmp do_trace;
0:
nop;
return;
do_trace:
/* Actually do tracing stuff */
}
最终结果是显著减少了禁用跟踪点的开销。
四、源码分析
4.1 数据结构
静态键(static_key)由一个名为struct static_key的结构体定义:
#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)
struct static_key {
atomic_t enabled;
/* Set lsb bit to 1 if branch is default true, 0 ot */
struct jump_entry *entries;
#ifdef CONFIG_MODULES
struct static_key_mod *next;
#endif
};
其中,enabled字段表示静态键的状态,0表示false,1表示true。entries字段包含了跳转标签(jump label)的修补信息,其定义如下:
#ifdef CONFIG_X86_64
typedef u64 jump_label_t;
struct jump_entry {
jump_label_t code;
jump_label_t target;
jump_label_t key;
};
在这里,code是进行修补的地址,target是我们需要跳转的目标地址,而key则是静态键的地址。
其关系如下图所示:
4.2 static_key_false
// linux-3.10/include/linux/jump_label.h
#if defined(CC_HAVE_ASM_GOTO) && defined(CONFIG_JUMP_LABEL)
struct static_key {
atomic_t enabled;
/* Set lsb bit to 1 if branch is default true, 0 ot */
struct jump_entry *entries;
#ifdef CONFIG_MODULES
struct static_key_mod *next;
#endif
};
# include <asm/jump_label.h>
# define HAVE_JUMP_LABEL
#endif /* CC_HAVE_ASM_GOTO && CONFIG_JUMP_LABEL */
static __always_inline bool static_key_false(struct static_key *key)
{
return arch_static_branch(key);
}
// linux-3.10/arch/x86/include/asm/jump_label.h
#define JUMP_LABEL_NOP_SIZE 5
#define STATIC_KEY_INITIAL_NOP ".byte 0xe9 \n\t .long 0\n\t"
static __always_inline bool arch_static_branch(struct static_key *key)
{
asm goto("1:"
STATIC_KEY_INITIAL_NOP
".pushsection __jump_table, \"aw\" \n\t"
_ASM_ALIGN "\n\t"
_ASM_PTR "1b, %l[l_yes], %c0 \n\t"
".popsection \n\t"
: : "i" (key) : : l_yes);
return false;
l_yes:
return true;
}
该函数使用了一个asm goto语句,这是GCC的扩展,允许汇编代码跳转到C语言标签。这个结构用于根据静态键实现分支指令。
下面是asm goto语句内部汇编代码的解析:
(1)“1:” 是一个本地标签,表示代码中的当前位置。
(2)STATIC_KEY_INITIAL_NOP 是之前定义的宏,它展开为静态键分支的初始指令。它由一个nop指令后跟一个32位的零值组成。
(3)“.pushsection __jump_table, “aw” \n\t” 推入一个名为__jump_table的新节,具有属性"aw"(分配和可写)。
(4)_ASM_ALIGN 和 _ASM_PTR 是宏,可能会展开为特定于体系结构的汇编指令,用于对齐和定义指针。
(5)“_ASM_PTR “1b, %l[l_yes], %c0 \n\t” 在__jump_table节中定义一个指针。它指向标签"1b”(当前位置),C语言标签%l[l_yes](如果静态键为true时的目标标签),以及常量%c0(表示key参数的值)。
往段“__jump_table”中写入label “1b”、C label “l_yes”和输入参数struct static_key *key的地址,这些信息对应于struct jump_entry 中的code、target、key成员。
#ifdef CONFIG_X86_64
typedef u64 jump_label_t;
struct jump_entry {
jump_label_t code;
jump_label_t target;
jump_label_t key;
};
(6)“.popsection \n\t” 弹出当前节从节栈中。
asm goto语句具有输入操作数"i" (key),表示key参数在汇编代码中被使用为输入。
在asm goto语句之后,有一个返回语句return false;,表示默认的返回值是false。
最后,有一个C语言标签l_yes,后面跟着一个返回语句return true;。这个标签表示如果静态键为true时的跳转目标。如果控制流程到达这个标签,函数返回true。
可见,以上代码的作用就是:执行NOP指令后返回false,同时把NOP指令的地址、代码”return true”对应地址、struct static_key *key的地址写入到段“__jump_table”。由于固定返回为false且为always inline,编译器会把
if (static_key_false((&static_key)))
do the unlikely work;
else
do likely work
优化为:
1:
nop
do likely work
retq
l_yes:
do the unlikely work;
如果启用了就会优化为:
1:
jmp l_yes
do likely work
retq
l_yes:
do the unlikely work;
4.3 jump_label_init
/* .data section */
#define DATA_DATA
......
. = ALIGN(8); \
VMLINUX_SYMBOL(__start___jump_table) = .; \
*(__jump_table) \
VMLINUX_SYMBOL(__stop___jump_table) = .; \
. = ALIGN(8);
extern struct jump_entry __start___jump_table[];
extern struct jump_entry __stop___jump_table[];
void __init jump_label_init(void)
{
struct jump_entry *iter_start = __start___jump_table;
struct jump_entry *iter_stop = __stop___jump_table;
struct static_key *key = NULL;
struct jump_entry *iter;
jump_label_lock();
jump_label_sort_entries(iter_start, iter_stop);
for (iter = iter_start; iter < iter_stop; iter++) {
struct static_key *iterk;
iterk = (struct static_key *)(unsigned long)iter->key;
arch_jump_label_transform_static(iter, jump_label_type(iterk));
if (iterk == key)
continue;
key = iterk;
/*
* Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH.
*/
*((unsigned long *)&key->entries) += (unsigned long)iter;
#ifdef CONFIG_MODULES
key->next = NULL;
#endif
}
jump_label_unlock();
}
jump_label_init()函数用于初始化跳转标签。
通过迭代遍历跳转表的每个条目,对每个条目进行处理。首先,将条目的键转换为struct static_key类型,并调用arch_jump_label_transform_static()函数进行体系结构特定的转换操作。
// kernel/jump_label.c
jump_label_init()
// arch/x86/kernel/jump_label.c
-->arch_jump_label_transform_static()
-->__jump_label_transform()
4.4 __jump_label_transform
#ifdef HAVE_JUMP_LABEL
union jump_code_union {
char code[JUMP_LABEL_NOP_SIZE];
struct {
char jump;
int offset;
} __attribute__((packed));
};
static void __jump_label_transform(struct jump_entry *entry,
enum jump_label_type type,
void *(*poker)(void *, const void *, size_t))
{
union jump_code_union code;
if (type == JUMP_LABEL_ENABLE) {
code.jump = 0xe9;
code.offset = entry->target -
(entry->code + JUMP_LABEL_NOP_SIZE);
} else
memcpy(&code, ideal_nops[NOP_ATOMIC5], JUMP_LABEL_NOP_SIZE);
(*poker)((void *)entry->code, &code, JUMP_LABEL_NOP_SIZE);
}
这是一个名为__jump_label_transform()的静态函数。它接受一个jump_entry结构体指针,一个jump_label_type类型的枚举值,以及一个函数指针poker作为参数。
函数内部首先声明了一个union jump_code_union类型的变量code,用于存储跳转指令的代码。
然后,根据传入的jump_label_type值,进行不同的操作。如果类型为JUMP_LABEL_ENABLE,则设置code变量的跳转指令为0xe9(表示无条件跳转指令),并计算跳转目标的偏移量,使得跳转目标的地址减去当前指令的地址和JUMP_LABEL_NOP_SIZE(指令长度)的结果作为偏移量。
如果类型不是JUMP_LABEL_ENABLE,则从ideal_nops[NOP_ATOMIC5]复制指定长度的指令到code变量。
最后,通过调用poker函数指针,将code变量的内容写入到entry->code指向的内存地址中,长度为JUMP_LABEL_NOP_SIZE。
这个函数的作用是根据提供的跳转标签类型,使用相应的跳转指令或者指定的空操作(nop)指令来转换跳转标签的代码。
enum jump_label_type {
JUMP_LABEL_DISABLE = 0,
JUMP_LABEL_ENABLE,
};
JUMP_LABEL_DISABLE : 复制 nop 指令到code地址处。
JUMP_LABEL_ENABLE:复制 jmp 指令到code地址处。
4.5 static_key_slow_inc/dec
static_key_slow_dec/static_key_slow_inc,这两个函数的做法原理类似,其关键在于当计数(key->enabled)达到需要修改代码段中的代码的时候,通过jump_label_update来完成代码的修改。把struct static_key::target指向的位置(就是使用该static_key的arch_static_branch中的那些”1b标号指向的nop指令”),替换为jump指令,从而jump到不常用的段;或者从jump指令改回nop指令。
(1)
void static_key_slow_inc(struct static_key *key)
{
if (atomic_inc_not_zero(&key->enabled))
return;
jump_label_lock();
if (atomic_read(&key->enabled) == 0) {
if (!jump_label_get_branch_default(key))
jump_label_update(key, JUMP_LABEL_ENABLE);
else
jump_label_update(key, JUMP_LABEL_DISABLE);
}
atomic_inc(&key->enabled);
jump_label_unlock();
}
EXPORT_SYMBOL_GPL(static_key_slow_inc);
static_key_slow_inc函数调用了jump_label_update来修补代码,并将static_key的enabled设置为1。
static void jump_label_update(struct static_key *key, int enable)
{
struct jump_entry *stop = __stop___jump_table;
struct jump_entry *entry = jump_label_get_entries(key);
#ifdef CONFIG_MODULES
struct module *mod = __module_address((unsigned long)key);
__jump_label_mod_update(key, enable);
if (mod)
stop = mod->jump_entries + mod->num_jump_entries;
#endif
/* if there are no users, entry can be NULL */
if (entry)
__jump_label_update(key, entry, stop, enable);
}
jump_label_update函数从static_key的entries字段获取jump_entry。stop参数可以是stop_jump_table或者static_key所属模块的跳转条目末尾。然后调用__jump_label_update函数。
jump_label_update()
-->__jump_label_update()
-->arch_jump_label_transform()
-->__jump_label_transform()
static_key_slow_inc将nop指令替换为jmp指令。
(2)
void static_key_slow_dec(struct static_key *key)
{
__static_key_slow_dec(key, 0, NULL);
}
EXPORT_SYMBOL_GPL(static_key_slow_dec);
static void __static_key_slow_dec(struct static_key *key,
unsigned long rate_limit, struct delayed_work *work)
{
if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex)) {
WARN(atomic_read(&key->enabled) < 0,
"jump label: negative count!\n");
return;
}
if (rate_limit) {
atomic_inc(&key->enabled);
schedule_delayed_work(work, rate_limit);
} else {
if (!jump_label_get_branch_default(key))
jump_label_update(key, JUMP_LABEL_DISABLE);
else
jump_label_update(key, JUMP_LABEL_ENABLE);
}
jump_label_unlock();
}
static_key_slow_dec将jmp指令替换为nop指令。
五、__jump_table节
静态键(static_key)和跳转标签(jump label)允许我们在需要进行检查的地址处进行代码修补,以确定要执行的代码流。在某些情况下,开关的取值几乎相同(true或false),因此检查可能会影响性能。使用静态键,我们可以实现无需检查而直接执行平坦的代码流。
静态键主要涉及以下三个方面:
(1)ELF文件中的__jump_table节:静态键的信息需要在编译时保存在ELF文件中。这些信息存储在特定的__jump_table节中,其中包含了静态键的状态以及与之关联的跳转代码。
(2)内核解析__jump_table信息:当内核加载ELF文件时,它会解析__jump_table节中的静态键信息。内核通过读取这些信息,了解静态键的状态以及相关的跳转代码位置。
(3)更新修补代码:当需要更改静态键的状态时,内核会根据静态键的值选择执行相应的代码路径。如果需要修改静态键的状态,内核会更新相应的修补代码,将跳转指令或空操作(nop)指令写入到相应的代码位置,以实现正确的代码流。
5.1 内核
对于内核镜像,跳转标签(jump label)保存在__start___jump_table和__stop___jump_table两个全局变量之间:
// linux-3.10/include/asm-generic/vmlinux.lds.h
/* .data section */
#define DATA_DATA \
......
*(__tracepoints) \
/* implement dynamic printk debug */ \
. = ALIGN(8); \
VMLINUX_SYMBOL(__start___jump_table) = .; \
*(__jump_table) \
VMLINUX_SYMBOL(__stop___jump_table) = .; \
. = ALIGN(8); \
......
// linux-3.10/include/linux/jump_label.h
extern struct jump_entry __start___jump_table[];
extern struct jump_entry __stop___jump_table[];
# uname -r
3.10.0-693.el7.x86_64
# cat /proc/kallsyms | grep __start___jump_table
ffffffff81af7378 D __start___jump_table
# cat /proc/kallsyms | grep __stop___jump_table
ffffffff81afc598 D __stop___jump_table
其初始化过程:
start_kernel()
-->jump_label_init()
在start_kernel函数中,会调用jump_label_init函数来解析__jump_table。
5.2 内核模块
跳转标签(jump label)保存内核模块ELF文件中的__jump_table节:
# readelf -S xfs.ko | grep __jump_table
[39] __jump_table PROGBITS 0000000000000000 0013f8f8
[40] .rela__jump_table RELA 0000000000000000 00142280
struct module
{
......
#ifdef HAVE_JUMP_LABEL
struct jump_entry *jump_entries;
unsigned int num_jump_entries;
#endif
......
}
初始化模块的jump_entry条目:
load_module()
-->find_module_sections()
static void find_module_sections(struct module *mod, struct load_info *info)
{
......
#ifdef HAVE_JUMP_LABEL
mod->jump_entries = section_objs(info, "__jump_table",
sizeof(*mod->jump_entries),
&mod->num_jump_entries);
#endif
}
......
对于模块(modules),在jump_label_init_module函数中,会注册一个名为jump_label_module_nb的模块通知器(module notifier)。当加载一个模块时,它会调用jump_label_add_module函数来解析该模块的__jump_table。
static int
jump_label_module_notify(struct notifier_block *self, unsigned long val,
void *data)
{
struct module *mod = data;
int ret = 0;
switch (val) {
case MODULE_STATE_COMING:
jump_label_lock();
ret = jump_label_add_module(mod);
if (ret)
jump_label_del_module(mod);
jump_label_unlock();
break;
case MODULE_STATE_GOING:
jump_label_lock();
jump_label_del_module(mod);
jump_label_unlock();
break;
case MODULE_STATE_LIVE:
jump_label_lock();
jump_label_invalidate_module_init(mod);
jump_label_unlock();
break;
}
return notifier_from_errno(ret);
}
struct notifier_block jump_label_module_nb = {
.notifier_call = jump_label_module_notify,
.priority = 1, /* higher than tracepoints */
};
static __init int jump_label_init_module(void)
{
return register_module_notifier(&jump_label_module_nb);
}
early_initcall(jump_label_init_module);
static int jump_label_add_module(struct module *mod)
{
struct jump_entry *iter_start = mod->jump_entries;
struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
struct jump_entry *iter;
struct static_key *key = NULL;
struct static_key_mod *jlm;
/* if the module doesn't have jump label entries, just return */
if (iter_start == iter_stop)
return 0;
jump_label_sort_entries(iter_start, iter_stop);
for (iter = iter_start; iter < iter_stop; iter++) {
struct static_key *iterk;
iterk = (struct static_key *)(unsigned long)iter->key;
if (iterk == key)
continue;
key = iterk;
if (__module_address(iter->key) == mod) {
/*
* Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH.
*/
*((unsigned long *)&key->entries) += (unsigned long)iter;
key->next = NULL;
continue;
}
jlm = kzalloc(sizeof(struct static_key_mod), GFP_KERNEL);
if (!jlm)
return -ENOMEM;
jlm->mod = mod;
jlm->entries = iter;
jlm->next = key->next;
key->next = jlm;
if (jump_label_type(key) == JUMP_LABEL_ENABLE)
__jump_label_update(key, iter, iter_stop, JUMP_LABEL_ENABLE);
}
return 0;
}
static void __jump_label_update(struct static_key *key,
struct jump_entry *entry,
struct jump_entry *stop, int enable)
{
for (; (entry < stop) &&
(entry->key == (jump_label_t)(unsigned long)key);
entry++) {
/*
* entry->code set to 0 invalidates module init text sections
* kernel_text_address() verifies we are not in core kernel
* init code, see jump_label_invalidate_module_init().
*/
if (entry->code && kernel_text_address(entry->code))
arch_jump_label_transform(entry, enable);
}
}
函数__jump_label_update用于更新静态键和跳转标签的状态。这个函数的作用是在给定的范围内遍历跳转标签数组(entry到stop之间),并根据静态键的状态更新相应的跳转标签。
在每次循环迭代中,函数会检查当前跳转标签的key字段是否与传入的静态键的地址匹配。如果匹配,则执行以下操作:
(1)检查跳转标签的code字段是否为非零值,并且该地址属于内核文本段(通过kernel_text_address函数进行验证)。这是为了确保只对有效的跳转标签进行操作,并排除了模块的初始化文本段。
int kernel_text_address(unsigned long addr)
{
if (core_kernel_text(addr))
return 1;
return is_module_text_address(addr);
}
(2)调用arch_jump_label_transform函数,根据传入的enable参数对跳转标签进行转换。具体的转换操作将由特定体系结构的代码实现。
arch_jump_label_transform()
-->__jump_label_transform()
static void __jump_label_transform(struct jump_entry *entry,
enum jump_label_type type,
void *(*poker)(void *, const void *, size_t))
{
union jump_code_union code;
if (type == JUMP_LABEL_ENABLE) {
code.jump = 0xe9;
code.offset = entry->target -
(entry->code + JUMP_LABEL_NOP_SIZE);
} else
memcpy(&code, ideal_nops[NOP_ATOMIC5], JUMP_LABEL_NOP_SIZE);
(*poker)((void *)entry->code, &code, JUMP_LABEL_NOP_SIZE);
}
六、修改内存代码
6.1 x86架构
参考代码3.10
(1)初始化
jump_label_init()
-->arch_jump_label_transform_static()
__init_or_module void arch_jump_label_transform_static(struct jump_entry *entry,
enum jump_label_type type)
{
__jump_label_transform(entry, type, text_poke_early);
}
调用的是text_poke_early函数。
(2)运行时
static_key_slow_inc/dec()
-->jump_label_update()
-->__jump_label_update()
-->arch_jump_label_transform()
void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)
{
get_online_cpus();
mutex_lock(&text_mutex);
__jump_label_transform(entry, type, text_poke_smp);
mutex_unlock(&text_mutex);
put_online_cpus();
}
调用的是text_poke_smp函数。
6.2 ARM64架构
参考的代码5.15
(1)初始化
jump_label_init()
-->arch_jump_label_transform_static()
-->arch_jump_label_transform()
void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)
{
void *addr = (void *)jump_entry_code(entry);
u32 insn;
if (type == JUMP_LABEL_JMP) {
insn = aarch64_insn_gen_branch_imm(jump_entry_code(entry),
jump_entry_target(entry),
AARCH64_INSN_BRANCH_NOLINK);
} else {
insn = aarch64_insn_gen_nop();
}
aarch64_insn_patch_text_nosync(addr, insn);
}
int __kprobes aarch64_insn_patch_text_nosync(void *addr, u32 insn)
{
u32 *tp = addr;
int ret;
/* A64 instructions must be word aligned */
if ((uintptr_t)tp & 0x3)
return -EINVAL;
ret = aarch64_insn_write(tp, insn);
if (ret == 0)
caches_clean_inval_pou((uintptr_t)tp,
(uintptr_t)tp + AARCH64_INSN_SIZE);
return ret;
}
调用的是aarch64_insn_write函数。
(2)运行时
static_key_enable()
-->static_key_enable_cpuslocked()
-->jump_label_update()
-->__jump_label_update()
-->arch_jump_label_transform()
和上述相同,也是调用aarch64_insn_write函数。
参考资料
Linux 3.10.0
Linux 5.15.0
https://blog.csdn.net/dog250/article/details/106715700
https://terenceli.github.io/%E6%8A%80%E6%9C%AF/2019/07/20/linux-static-key-internals
https://tinylab.org/riscv-jump-label-part4/
https://www.zhihu.com/question/471637144
https://blog.csdn.net/weixin_43512663/article/details/123344672
https://blog.csdn.net/wdjjwb/article/details/80845627
https://blog.csdn.net/JiMoKuangXiangQu/article/details/128239338
https://rtoax.blog.csdn.net/article/details/115279591