泰晓科技 -- 聚焦 Linux - 追本溯源,见微知著!
网站地址:https://tinylab.org

儿童Linux系统,可打字编程学数理化
请稍侯

RISC-V jump_label 详解,第 2 部分:指令编码

Wu Zhangjin 创作于 2022/03/28

Author: Wu Zhangjin falcon@tinylab.org Date: 2022/03/28 Project: RISC-V Linux 内核剖析

背景简介

该系列有多篇文章,旨在分析 RISC-V 架构上的 jump_label 实现。

上一篇介绍了其技术原理,jump_label 能够基本消除 Tracepoint 禁用状态的开销,从而确保 Tracepoint 功能可直接编译进内核,并允许线上按需启用 Tracepoints。

从上一节我们已经知道,jump_label 的实现包含三部分:static_branch(foo), 指令编码以及运行时交换 nopgoto label(foo) 指令。

本节先来介绍指令编码部分,即带领大家阅读 RISC-V ISA 手册并把 nopgoto label(foo) 指令编码出来,继而分析 arch/riscv/kernel/jump_label.c 中的具体实现。

下载指令手册

上周的直播分享上,贾老师简单介绍了 RISC-V ISA 相关的内容,其中提到有两个重要的手册,一个是非特权 ISA,另外一个是特权 ISA。

这里 可以找到相应的手册,其中指令编码部分属于 非特权 ISA 手册

需要注意的是,这个 Spec 文档并不是一成不变的,所以本文提到的页面甚至章节等都可能变动,本文以 riscv-spec-20191213.pdf 为准。

参考手册编码目标指令

指令长度

在第 1 章中明确提到:

The base RISC-V ISA has fixed-length 32-bit instructions that must be naturally aligned on 32-bit boundaries.

但是:

However, the standard RISC-V encoding scheme is designed to support ISA extensions with variable-length instructions, where each instruction can be any number of 16-bit instruction parcels in length and parcels are naturally aligned on 16-bit boundaries. The standard compressed ISA extension described in Chapter 16 reduces code size by providing compressed 16-bit instructions and relaxes the alignment constraints to allow all instructions (16 bit and 32 bit) to be aligned on any 16-bit boundary to improve code densit

本文讨论正常情况,即所有的指令编码长度是 32 位无符号数。

NOP 指令编码

先来看简单一点的 nop 指令,这个在几乎所有架构上都有定义,但是编码却完全跟架构相关。

在非特权手册的 P20/38 页,即下述位置:

  • Chapter 2. RV32I Base Integer Instruction Set
    • 2.4 Integer Computational Instructions
      • Nop Instruction

很详细地介绍了:

The NOP instruction does not change any architecturally visible state, except for advancing the pc and incrementing any applicable performance counters. NOP is encoded as ADDI x0, x0, 0.

其编码如下:

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 | rd   | opcode  | Instruction
-----------|-----|--------|------|---------|------------
     12    | 5   |   3    | 5    |    7    | Bits Length
-----------|-----|--------|------|---------|------------
     0     | 0   |  ADDI  | 0    | OP-IMM  | Encoding

其中,x0 被编码为 0,而 ADDIOP-IMMfunct3 编码可以从 P130/148 页,即下述位置:

  • Chapter 24. RV32/64G Instruction Set Listings

直接找到:

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 |  rd  | opcode  | I-Type Instruction
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 |  000   |  rd  | 0010011 | ADDI

结合这两部分,确认了 funct3000,而 OP-IMM0010011,进而可以得到如下编码:

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 |  rd  | opcode  | Instruction
-----------|-----|--------|------|---------|------------
     12    | 5   |   3    |  5   |    7    | Bits Length
-----------|-----|--------|------|---------|------------
     0     | 0   |  000   |00000 | 0010011 | Encoding

所以,NOP 的最终编码是 00010011,即 0x13,考虑指令长度为 32 位,可以定义为:

#define RISCV_INSN_NOP 0x00000013U

JAL/J offset 指令编码

goto label(foo) 是一种无条件跳转需求,并且根据上一篇的分析,其跳转范围在一条 if 语句后面,不会涉及长跳转,所以可以对应 J offset 这样一种直接跳转指令,无需寄存器存放地址后再间接跳转(对应 JALR)。

在最新的 ISA 手册中,硬件 J 指令已经被删除,变成了伪指令,其实现合并进了 JAL 指令,对应 rd=x0,所以实际上我们需要查找的是 JAL offset 指令的编码。

Preface to Version 2.0:

The JAL instruction has now moved to the U-Type format with an explicit destination register, and the J instruction has been dropped being replaced by JAL with rd=x0. This removes the only instruction with an implicit destination register and removes the J-Type instruction format from the base ISA. There is an accompanying reduction in JAL reach, but a significant reduction in base ISA complexity

找到手册的 P21/39 页,即如下位置:

  • Chapter 2. RV32I Base Integer Instruction Set
    • 2.5 Control Transfer Instructions
      • Unconditional Jumps

其说明如下:

Plain unconditional jumps (assembler pseudoinstruction J) are encoded as a JAL with rd=x0.

      31|30  -  21|  20    |19   -  12|11 - 7|6  -   0 | Bits
--------|---------|--------|----------|------|---------|------------
imm[20] |imm[10:1]|imm[11] |imm[19:12]|  rd  | opcode  | Instruction
--------|---------|--------|----------|------|---------|------------
    1   |   10    |   1    |    8     |  5   |   7     | Bits Length
--------------------------------------|------|---------|-----------
             offset[20:1]             | dest |   JAL   | Encoding

其中这里的直接跳转也是用到 x0 寄存器,dest 可以直接同 NOP 指令,直接编码为 0,而 JALOP-IMM 同样可以从 P130/148 页,即下述位置:

  • Chapter 24. RV32/64G Instruction Set Listings

直接找到:

31       -          12|11 - 7|6  -   0| Bits
----------------------|------|--------|--------------------
imm[20|10:1|11|19:12] |  rd  | opcode | J-type Instruction
----------------------|------|--------|---------------------
imm[20|10:1|11|19:12] |  rd  | 1101111| JAL Encoding

接下来先把 rd 替换为 x0 寄存器并编码为 0, 则 J offset 指令可以编码如下:

31       -          12|11 - 7|6  -   0| Bits
----------------------|------|--------|--------------------
imm[20|10:1|11|19:12] |  rd  | opcode | J-type Instruction
----------------------|------|--------|---------------------
imm[20|10:1|11|19:12] |  0   | 1101111| J offset Encoding

这里先把 J offsetrdopcode 编码定义出来:

#define RISCV_INSN_JAL 0x0000006fU

后面复杂的其实是 offset 的编码,这个并不是简单的把 offset 直接编码进目标指令,而是需要经过复杂的移位。

      31|30  -  21|  20    |19   -  12|11 - 7|6  -   0 | Bits
--------|---------|--------|----------|------|---------|------------
imm[20] |imm[10:1]|imm[11] |imm[19:12]|  rd  | opcode  | Instruction
--------|---------|--------|----------|------|---------|------------
    1   |   10    |   1    |    8     |  5   |   7     | Bits Length
--------------------------------------|------|---------|-----------
             offset[20:1]             |  0   | 1101111 | J offset Encoding

比如说 offset 的第 0 位直接是舍弃的(考虑到代码指令长度和对齐要求,所以这一位其实会一直是零),剩下的是复杂的移位:

  • offset[20] 放到目标指令的第 31 位
  • offset[10:1] 放到目标指令的第 21-30 位
  • offset[11] 放到目标指令的第 20 位
  • offset[12-19] 放到目标指令的第 12-19 位

需要先取出目标位再做相对移位,比如第 11 位要移到目标指令的第 20 位,相对移位 (20-11)。

好在 Linux 内核对于取出目标位提供了专门的宏,咱们先搬运一个试试:

((u32)offset & GENMASK(11, 11)) << (20 - 11)

其对应 “取目标位” 和 “相对移位” 两个操作,完整的 J offset 指令编码则如下:

insn = RISCV_INSN_JAL |
(((u32)offset & GENMASK(19, 12)) << (12 - 12)) |
(((u32)offset & GENMASK(11, 11)) << (20 - 11)) |
(((u32)offset & GENMASK(10,  1)) << (21 -  1)) |
(((u32)offset & GENMASK(20, 20)) << (31 - 20));

寄存器编码

上面介绍到的 NOPJAL/J offset 指令均只用到 x0 寄存器,其编码为 0。

由于其他指令可能会用到寄存器编码,这里做个补充介绍。

相关寄存器(x0-x31)的编码为对应的编号 0-31,验证如下。

先准备一段简单的汇编,保存为 test.s

# test.s
    .text
    .globl _start
_start:
    li x0, 0
    li x1, 0
    li x2, 0
    li x3, 0
    li x4, 0
    li x5, 0
    li x6, 0
    li x7, 0
    li x8, 0

    li a0, 0                     # return 0
    li a7, 93                    # __NR_exit
    scall

编译并反编译如下:

$ riscv64-linux-gnu-gcc -march=rv64im -mabi=lp64 -nostdlib -static -o test test.s
$ riscv64-linux-gnu-objdump -d -M no-aliases,numeric ./test

Disassembly of section .text:

0000000000010078 <_start>:
   10078:	00000013          	addi	x0,x0,0
   1007c:	00000093          	addi	x1,x0,0
   10080:	00000113          	addi	x2,x0,0
   10084:	00000193          	addi	x3,x0,0
   10088:	00000213          	addi	x4,x0,0
   1008c:	00000293          	addi	x5,x0,0
   10090:	00000313          	addi	x6,x0,0
   10094:	00000393          	addi	x7,x0,0
   10098:	00000413          	addi	x8,x0,0
   1009c:	00000513          	addi	x10,x0,0
   100a0:	05d00893          	addi	x17,x0,93
   100a4:	00000073          	ecall

可以看到 li 被实际编码为 addi 指令。ADDI 指令的编码方式已经在 NOP 指令编码 一节找到:

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 | rd   | opcode  | I-Type Instruction
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 |  000   | rd   | 0010011 | ADDI

x0-x8 的寄存器序号 0-8 的二进制编码代入可以依次得到如下编码:

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 | rd   | opcode  | I-Type Instruction
-----------|-----|--------|------|---------|------------
         0 | 0   |  000   |00000 | 0010011 | addi x0,x0,0
         0 | 0   |  000   |00001 | 0010011 | addi x1,x0,0
         0 | 0   |  000   |00010 | 0010011 | addi x2,x0,0
         0 | 0   |  000   |00011 | 0010011 | addi x3,x0,0
         0 | 0   |  000   |00100 | 0010011 | addi x4,x0,0
         0 | 0   |  000   |00101 | 0010011 | addi x5,x0,0
         0 | 0   |  000   |00110 | 0010011 | addi x6,x0,0
         0 | 0   |  000   |00111 | 0010011 | addi x7,x0,0
         0 | 0   |  000   |01000 | 0010011 | addi x8,x0,0

rdopcode 合并后,正好对应上面的反编译结果,请注意 opcode 只有 7 位,需要从 rd 编码取 1 位凑成后面 2 个十六进制编码,而两者一共 12 位,刚好构成 3 个十六进制数字。

31   -   20|19-15|14  - 12|11 - 7|6  -   0 | Bits
-----------|-----|--------|------|---------|------------
 imm[11:0] | rs1 | funct3 | rd   | opcode  | I-Type Instruction
-------------------------------------------|------------
               0x13:       0000 0001 0011  | addi x0,x0,0
               0x93:       0000 1001 0011  | addi x1,x0,0
              0x113:       0001 0001 0011  | addi x2,x0,0
              0x193:       0001 1001 0011  | addi x3,x0,0
              0x213:       0010 0001 0011  | addi x4,x0,0
              0x293:       0010 1001 0011  | addi x5,x0,0
              0x313:       0011 0001 0011  | addi x6,x0,0
              0x393:       0011 1001 0011  | addi x7,x0,0
              0x413:       0100 0001 0011  | addi x8,x0,0

这样调整一下,就很容易映射过去了。感兴趣的同学,也可以进一步阅读 riscv-gcc 的源代码:gcc/config/riscv

查看代码实现

接下来再去看代码就比较容易理解了,核心实现见 arch/riscv/kernel/jump_label.c

#define RISCV_INSN_NOP 0x00000013U
#define RISCV_INSN_JAL 0x0000006fU

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) {
		long offset = jump_entry_target(entry) - jump_entry_code(entry);

		if (WARN_ON(offset & 1 || offset < -524288 || offset >= 524288))
			return;

		insn = RISCV_INSN_JAL |     /* J offset 指令编码 */
			(((u32)offset & GENMASK(19, 12)) << (12 - 12)) |
			(((u32)offset & GENMASK(11, 11)) << (20 - 11)) |
			(((u32)offset & GENMASK(10,  1)) << (21 -  1)) |
			(((u32)offset & GENMASK(20, 20)) << (31 - 20));
	} else {
		insn = RISCV_INSN_NOP;     /* NOP 指令编码 */
	}

	mutex_lock(&text_mutex);
	patch_text_nosync(addr, &insn, sizeof(insn));
	mutex_unlock(&text_mutex);
}

本文只涉及 insn 编码部分,余下的部分包括如何获取和计算 offset,如何交换 nopJ offset(即 goto label(foo)),其中 offset 的获取和计算同 static_branch(foo) 的实现和 jump table 的设计密切相关。

小结

本文介绍了如何根据 RISC-V 的指令集手册来编码目标指令 nopgoto label(foo),该方法适合类似的指令编码需求,相关需求预期会出现在编译技术、内核汇编、性能优化等领域。

接下来我们将继续探讨剩下的两部分代码实现:static_branch(foo) 和运行时交换 nopgoto label(foo) 指令。



Read Album:

Read Related:

Read Latest: