[TOC]
使用Rust實(shí)現(xiàn)Brainfuck的JIT編譯器
x64匯編簡(jiǎn)介
Linux x64 匯編/Hello World
我們每天產(chǎn)出大量的垃圾代碼郑原，我們每個(gè)人都可以像這樣簡(jiǎn)單地編寫最簡(jiǎn)單的代碼：
#include <stdio.h>
int main() {
int x = 10;
int y = 100;
printf("x + y = %d\n"艾少，x + y);
return 0;
}
希望讀者們都可以理解上述 C 代碼的作用传于。但是渔欢，此代碼在底層如何工作？我認(rèn)為并非所有人都能回答這個(gè)問題，我也是讼撒。我可以用Haskell燎窘，Erlang摹闽，Go 等高級(jí)編程語(yǔ)言編寫代碼，但是在它們編譯后我并不知道它在底層是如何工作的褐健。因此付鹿，我決定采取一些更深入的步驟，進(jìn)行記錄蚜迅，并描述我對(duì)此的學(xué)習(xí)過(guò)程舵匾。希望這個(gè)過(guò)程不僅僅只是對(duì)我來(lái)說(shuō)很有趣。讓我們開始吧谁不。
準(zhǔn)備
開始之前坐梯，我們必須準(zhǔn)備一些事情，如我所寫的那樣刹帕，我目前使用 Ubuntu 18.04吵血，因此我的文章將針對(duì)該操作系統(tǒng)和體系結(jié)構(gòu)。不同的 CPU 支持不同的指令集偷溺，目前我使用 Intel 的 64 位 CPU践瓷。同時(shí)我也將使用 NASM 語(yǔ)法。你可以使用以下方法安裝它：
$ apt install nasm
記住亡蓉，Netwide Assembler（簡(jiǎn)稱 NASM）是一款基于英特爾 x86 架構(gòu)的匯編與反匯編工具晕翠。這就是我們目前需要的工具。
NASM 語(yǔ)法
在這里砍濒，我將不介紹完整的匯編語(yǔ)法淋肾，我們僅提及其龐大語(yǔ)法的一小部分，也是那些我們將在本文中使用到的部分爸邢。通常樊卓， NASM 程序分為幾個(gè)段（section），在這篇文章中杠河，我們將遇到以下兩個(gè)段：
- 數(shù)據(jù)段：data section
- 文本段：text section
數(shù)據(jù)段部分用于聲明常量碌尔，此數(shù)據(jù)在運(yùn)行時(shí)不會(huì)更改浇辜。聲明數(shù)據(jù)部分的語(yǔ)法為：
section .data
文本段部分用于代碼。該部分必須以全局聲明 _start 開頭唾戚，該聲明告訴內(nèi)核程序從何處開始執(zhí)行柳洋。
section .text
global _start
_start:
注釋以符號(hào) ; 開頭。每條 NASM 源代碼行都包含以下四個(gè)字段的某種組合：
[label:] instruction [operands] [; comment]
方括號(hào)中的字段是可選的叹坦⌒芰停基本的 NASM 指令由兩部分組成，第一部分是要執(zhí)行的指令的名稱募书，第二部分是該命令的操作數(shù)绪囱。例如：
mov rax, 48 ; put value 48 in the rax register
Hello World!
讓我們用 NASM 編寫第一個(gè)程序。當(dāng)然莹捡，這將是經(jīng)典的 Hello World! 程序鬼吵。這是它的代碼：
section .data
msg db "Hello World!", 0x0A
section .text
global _start
_start:
mov rax, 1
mov rdi, 1
mov rsi, msg
mov rdx, 13
syscall
mov rax, 60
mov rdi, 0
syscall
是的，它看起來(lái)一點(diǎn)都不像 printf("Hello World!\n")篮赢。讓我們嘗試了解它是什么以及它如何工作而柑。首先看第一和第二行，我們定義了數(shù)據(jù)段部分荷逞，并將 msg 常量與 “Hello, World!” 值放在一起。現(xiàn)在粹排，我們可以在代碼中使用此常量种远。接下來(lái)是聲明文本段部分和程序的入口。程序?qū)牡?7 行開始執(zhí)行⊥缍現(xiàn)在開始最有趣的部分坠敷，我們已經(jīng)知道 mov 指令是什么，它獲得 2 個(gè)操作數(shù)射富，并將第二個(gè)的值放在第一位膝迎。但是這些 rax, rdi 等是什么？正如我們?cè)?Wikipedia 中可以看到的：
中央處理器（CPU）是計(jì)算機(jī)中的硬件胰耗，它通過(guò)執(zhí)行系統(tǒng)的基本算術(shù)限次，邏輯和輸入/輸出操作來(lái)執(zhí)行計(jì)算機(jī)程序的指令。
好的柴灯，CPU 會(huì)執(zhí)行一些運(yùn)算卖漫。但是，在哪里可以獲取該運(yùn)算的數(shù)據(jù)赠群，是內(nèi)存嗎羊始？從內(nèi)存中讀取數(shù)據(jù)并將數(shù)據(jù)寫回到內(nèi)存中會(huì)減慢處理器的速度，因?yàn)樗婕巴ㄟ^(guò)控制總線發(fā)送數(shù)據(jù)請(qǐng)求的復(fù)雜過(guò)程查描。因此突委，CPU 具有自己的內(nèi)部存儲(chǔ)器柏卤，稱為寄存器。
因此匀油，當(dāng)我們編寫 mov rax, 1 時(shí)缘缚，意味著將 1 放入 rax 寄存器。現(xiàn)在我們知道 rax钧唐，rdi忙灼，rsi 等代表了什么了，但是還需要知道什么時(shí)候該使用 rax 钝侠，什么時(shí)候使用 rdi 等该园。
-
rax：臨時(shí)寄存器，當(dāng)我們調(diào)用syscall時(shí)帅韧，rax必須包含syscall號(hào)碼里初，所以后面的數(shù)字就是syscall的號(hào)碼 -
rdi：用于將第 1 個(gè)參數(shù)傳遞給函數(shù) -
rsi：用于將第 2 個(gè)參數(shù)傳遞給函數(shù) -
rdx：用于將第 3 個(gè)參數(shù)傳遞給函數(shù)
換句話說(shuō)，我們只是在調(diào)用 sys_write 的 syscall忽舟∷粒看看 sys_write 的定義：
size_t sys_write(unsigned int fd, const char * buf, size_t count);
它具有3個(gè)參數(shù)：
-
fd：文件描述符。對(duì)于 stdin叮阅，stdout 和 stderr 來(lái)說(shuō)刁品，其值分別為 0，1 和 2 -
buf：指向字符數(shù)組 -
count：指定要寫入的字節(jié)數(shù)
我們將 1 寫入 rax浩姥，這意味我們要調(diào)用 sys_write挑随。完整的 syscall 列表可以在 https://github.com/torvalds/linux/blob/master/arch/x86/entry/syscalls/syscall_64.tbl 找到。在完成該調(diào)用之后勒叠，將 60 寫入 rax兜挨，這意味著我們要調(diào)用 sys_exit 退出程序，且退出碼為 0眯分。
最后拌汇，讓我們來(lái)構(gòu)建這個(gè)程序，我們需要執(zhí)行以下命令：
$ nasm -f elf64 -o main.o main.asm
$ ld -o main main.o
嘗試運(yùn)行這個(gè)程序吧弊决！
什么是JIT
本文部分翻譯自：https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html.
“JIT” 一詞往往會(huì)喚起工程師內(nèi)心最深處的恐懼和崇拜噪舀，通常這并沒有什么錯(cuò)，只有最核心的編譯器團(tuán)隊(duì)才能夢(mèng)想創(chuàng)建這種東西飘诗。它會(huì)使你聯(lián)想到 JVM 或 .NET傅联，這些家伙都是具有數(shù)十萬(wàn)行代碼的超大型運(yùn)行時(shí)。你永遠(yuǎn)不會(huì)看到有人向你介紹 “Hello World!” 級(jí)別的 JIT 編譯器疚察，但事實(shí)上只需少量代碼即可完成一些有趣的工作蒸走。本文試圖改變這一點(diǎn)。
編寫一個(gè) JIT 編譯器只需要四步貌嫡，就像把大象裝到冰箱里一樣比驻。
- 申請(qǐng)一段可寫和可執(zhí)行的內(nèi)存
- 將源碼翻譯為機(jī)器碼（通常經(jīng)過(guò)匯編）
- 將機(jī)器碼寫入第一步申請(qǐng)的內(nèi)存
- 執(zhí)行這部分內(nèi)存
Hello, JIT World: The Joy of Simple JITs
事不宜遲该溯，讓我們跳進(jìn)我們的第一個(gè) JIT 程序。該代碼是特定于 64 位 Unix 的别惦，因?yàn)樗褂昧?mmap()狈茉。鑒于此讀者需要擁有支持該代碼的處理器和操作系統(tǒng)。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
int main(int argc, char *argv[]) {
// Machine code for:
// mov eax, 0
// ret
unsigned char code[] = {0xb8, 0x00, 0x00, 0x00, 0x00, 0xc3};
if (argc < 2) {
fprintf(stderr, "Usage: jit1 <integer>\n");
return 1;
}
// Overwrite immediate value "0" in the instruction
// with the user's value. This will make our code:
// mov eax, <user's value>
// ret
int num = atoi(argv[1]);
memcpy(&code[1], &num, 4);
// Allocate writable/executable memory.
// Note: real programs should not map memory both writable
// and executable because it is a security risk.
void *mem = mmap(NULL, sizeof(code), PROT_WRITE | PROT_EXEC,
MAP_ANON | MAP_PRIVATE, -1, 0);
memcpy(mem, code, sizeof(code));
// The function will return the user's value.
int (*func)() = mem;
return func();
}
似乎很難相信上面的 33 行代碼是一個(gè)合法的 JIT掸掸。它動(dòng)態(tài)生成一個(gè)函數(shù)氯庆，該函數(shù)返回運(yùn)行時(shí)指定的整數(shù)，然后運(yùn)行該函數(shù)扰付。讀者可以驗(yàn)證其是否正常運(yùn)行：
$ gcc -o jit jit.c
$ ./jit 42
$ echo $?
# 42
您會(huì)注意到堤撵，代碼中使用 mmap() 分配內(nèi)存，而不是使用 malloc() 從堆中獲取內(nèi)存的常規(guī)方法羽莺。這是必需的实昨，因?yàn)槲覀冃枰獌?nèi)存是可執(zhí)行的，因此我們可以跳轉(zhuǎn)到它而不會(huì)導(dǎo)致程序崩潰盐固。在大多數(shù)系統(tǒng)上荒给，棧和堆都配置為不允許執(zhí)行，因?yàn)槿绻愕拇a跳轉(zhuǎn)到了椀蟛罚或堆志电，則意味著程序發(fā)生了很大的錯(cuò)誤，這是由操作系統(tǒng)的內(nèi)存結(jié)構(gòu)決定的蛔趴。更糟糕的是挑辆，利用緩沖區(qū)溢出的黑客可以使用可執(zhí)行堆棧來(lái)更輕松地利用該漏洞。因此夺脾，通常我們希望避免映射任何可寫和可執(zhí)行的內(nèi)存，這也是在你自己的程序中遵循此規(guī)則的好習(xí)慣茉继。我在上面打破了這個(gè)規(guī)則咧叭，但這只是為了使我們的第一個(gè)程序盡可能簡(jiǎn)單。
dynasm介紹
DynASM 是為 LuaJIT 編寫的 JIT 匯編預(yù)處理器和微型運(yùn)行時(shí)庫(kù)烁竭。簡(jiǎn)單來(lái)講菲茬，DynASM完成兩個(gè)工作，一個(gè)是預(yù)處理派撕，把你寫的匯編指令（對(duì)婉弹，沒有Elixir，DynASM并不能直接把邏輯變成匯編终吼，需要你手動(dòng)把你的邏輯用匯編語(yǔ)言重寫一遍镀赌，因此性能也取決于你的匯編代碼寫的好壞）變成真正的二進(jìn)制機(jī)器碼，另一個(gè)是提供一個(gè)微型運(yùn)行時(shí)际跪，來(lái)處理那些必須推遲到運(yùn)行時(shí)才能執(zhí)行的代碼商佛。
而 Rust 生態(tài)中也有一個(gè)參照 DynASM 所開發(fā)的項(xiàng)目喉钢，也叫 dynasm：
為了在 Rust 中編寫匯編代碼，我們將使用這個(gè)名為 dynasm-rs 的擴(kuò)展庫(kù)良姆。由于 dynasm-rs 是對(duì)著名 C/C++ 庫(kù) dynasm 的模仿肠虽，后者則是 LuaJIT 項(xiàng)目的重要組成部分。因此玛追，其作用與 Lua 的 DynASM 是一樣的税课，dynasm-rs 是一個(gè)匯編語(yǔ)言編譯器，它可以將匯編代碼編譯為機(jī)器碼痊剖。
在項(xiàng)目中的 Cargo.toml 文件里添加相應(yīng)的依賴項(xiàng)：
[dependencies]
dynasm = "1.2.3"
dynasmrt = "1.2.3"
實(shí)現(xiàn)BrainfuckJIT
在生活中韩玩，如果有兩種合理但不同的方法時(shí)，你應(yīng)該總是研究?jī)烧叩慕Y(jié)合邢笙，看看能否找到兩全其美的方法啸如。我們稱這種組合為雜合（hybrid）。例如氮惯，為什么只吃巧克力或簡(jiǎn)單的堅(jiān)果叮雳，而不是將兩者結(jié)合起來(lái)，成為一塊可愛的堅(jiān)果巧克力呢妇汗？
在 1960 年約翰·麥卡錫偶然發(fā)現(xiàn)了此方法帘不。在他的重要論文《符號(hào)表達(dá)式的遞歸函數(shù)及其在機(jī)器上的計(jì)算》（Recursive functions of symbolic expressions and their computation by machine, Part I）第一部分中，他提到了在運(yùn)行時(shí)被轉(zhuǎn)換的函數(shù)杨箭，因此不需要編譯并執(zhí)行系統(tǒng)寞焙。JIT 編譯是兩種傳統(tǒng)的機(jī)器代碼翻譯方法：提前編譯（AOT）和解釋（Interpreter）的結(jié)合，它結(jié)合了兩者的優(yōu)點(diǎn)和缺點(diǎn)互婿。
讓我們回憶一下第一篇文章的內(nèi)容捣郊，是關(guān)于編寫 JIT 所需要的 4 個(gè)步驟：
- 申請(qǐng)一段可寫和可執(zhí)行的內(nèi)存
- 將源碼翻譯為機(jī)器碼（通常經(jīng)過(guò)匯編）
- 將機(jī)器碼寫入第一步申請(qǐng)的內(nèi)存
- 執(zhí)行這部分內(nèi)存
首先申請(qǐng)一段內(nèi)存作為 Brainfuck 解釋器的紙帶，并取得該段紙帶在內(nèi)存中的起始地址和終止地址：
let mut tape: Box<[u8]> = vec![0; 65536].into_boxed_slice();
let tape_addr_from = tape.as_mut_ptr();
let tape_addr_to = unsafe { tape_addr_from.add(tape.len()) };
我們將整個(gè) Brainfuck 程序看作一個(gè)函數(shù)慈参，它接收兩個(gè)參數(shù)：紙帶起始地址和終止地址呛牲。根據(jù) nasm 規(guī)范，函數(shù)的第一個(gè)參數(shù)被存在 rdi 寄存器中驮配，第二個(gè)參數(shù)被存在 rsi 寄存器中娘扩。我們將它們復(fù)制到 r12 和 r13 這兩個(gè)寄存器內(nèi)持久化存儲(chǔ)。同時(shí) rcx 寄存器被用作為紙帶的指針 SP壮锻，賦予其初始值為紙帶起始地址琐旁。
let mut ops = dynasmrt::x64::Assembler::new()?;
let entry_point = ops.offset();
dynasm!(ops
; .arch x64
; mov r12, rdi // arg tape_addr_from
; mov r13, rsi // arg tape_addr_to
; mov rcx, rdi // stack pointer
);
編寫 sysv64 格式的 getchar/putchar 函數(shù)，使之后的匯編代碼中可以調(diào)用這兩個(gè)函數(shù)猜绣。
unsafe extern "sysv64" fn putchar(char: *mut u8) {
std::io::stdout()
.write_all(std::slice::from_raw_parts(char, 1))
.unwrap();
}
unsafe extern "sysv64" fn getchar(char: *mut u8) {
std::io::stdout().flush().unwrap();
std::io::stdin()
.read_exact(std::slice::from_raw_parts_mut(char, 1))
.unwrap();
}
之后, 將每個(gè) IR 翻譯為語(yǔ)義等價(jià)的匯編代碼如下灰殴。首先 SHL(x)，SHR(x)掰邢，ADD(x) 和 SUB(x) 4 個(gè)操作符最為簡(jiǎn)單验懊，它們均只使用一行匯編代碼即可完成翻譯擅羞。之后是 PUTCHAR 與 GETCHAR，們遵循匯編中函數(shù)調(diào)用的邏輯义图，的參數(shù)與地址按照規(guī)則寫入指定寄存器减俏，然后，用 call 指令調(diào)用該函數(shù)碱工。最后是 JIZ(x) 與 JNZ(x)娃承，它們，流程控制怕篷，其對(duì)應(yīng)历筝，編代碼通過(guò)組合使用標(biāo)簽，比較運(yùn)算廊谓，jump 指令完成梳猪。
for ir in code.instrs {
match ir {
ir::IR::SHL(x) => dynasm!(ops
; sub rcx, x as i32 // sp -= x
),
ir::IR::SHR(x) => dynasm!(ops
; add rcx, x as i32 // sp += x
),
ir::IR::ADD(x) => dynasm!(ops
; add BYTE [rcx], x as i8 // *sp += x
),
ir::IR::SUB(x) => dynasm!(ops
; sub BYTE [rcx], x as i8 // *sp -= x
),
ir::IR::PUTCHAR => dynasm!(ops
; mov r15, rcx
; mov rdi, rcx
; mov rax, QWORD putchar as _
; sub rsp, BYTE 0x28
; call rax
; add rsp, BYTE 0x28
; mov rcx, r15
),
ir::IR::GETCHAR => dynasm!(ops
; mov r15, rcx
; mov rdi, rcx
; mov rax, QWORD getchar as _
; sub rsp, BYTE 0x28
; call rax
; add rsp, BYTE 0x28
; mov rcx, r15
),
ir::IR::JIZ(_) => {
let l = ops.new_dynamic_label();
let r = ops.new_dynamic_label();
loops.push((l, r));
dynasm!(ops
; cmp BYTE [rcx], 0
; jz => r
; => l
)
}
ir::IR::JNZ(_) => {
let (l, r) = loops.pop().unwrap();
dynasm!(ops
; cmp BYTE [rcx], 0
; jnz => l
; => r
)
}
}
}
同時(shí)不要忘記為該函數(shù)寫上 return：
dynasm!(ops
; ret
);
最后，通過(guò)強(qiáng)制類型換將這段內(nèi)存標(biāo)記為一個(gè)合法的 rust 函數(shù)的函數(shù)體蒸痹，這可以通過(guò) std::mem::transmute 函數(shù)實(shí)現(xiàn)春弥。
let exec_buffer = ops.finalize().unwrap(); // compile the asm
let fun: extern "sysv64" fn(tape_addr_from: *mut u8, tape_addr_to: *mut u8) =
unsafe { std::mem::transmute(exec_buffer.ptr(entry_point)) };
fun(tape_addr_from, tape_addr_to);
至此，我們成功將一個(gè) Brainfuck 程序動(dòng)態(tài)編譯為一個(gè)函數(shù)叠荠。上面的匯編代碼中沒有進(jìn)行包括 I/O匿沛，出等方面的錯(cuò)誤處理，一項(xiàng)復(fù)雜的工程榛鼎，并且特意不被加入到代碼中以便讀者只關(guān)心其核心邏輯逃呼。你可以嘗試自己去實(shí)現(xiàn)。
完整代碼如下：
#![feature(proc_macro_hygiene)]
use std::io::prelude::*;
use dynasm::dynasm;
use dynasmrt::{DynasmApi, DynasmLabelApi};
mod opcode;
mod ir_code;
use ir_code::IR;
unsafe extern "sysv64" fn putchar(char: u8) {
std::io::stdout().write_all(&[char]).unwrap()
}
#[derive(Default)]
struct Interpreter {}
impl Interpreter {
fn run(&mut self, data: Vec<u8>) -> Result<(), Box<dyn std::error::Error>> {
// 將源文件中的內(nèi)容轉(zhuǎn)換為 Opcode 數(shù)組
let opcode_code = opcode::Code::from(data)?;
// 將 opcode 轉(zhuǎn)換為 ir code
let code = ir_code::Code::from(opcode_code.instrs)?;
// 用來(lái)當(dāng)匹配到 [ 和 ] 時(shí)執(zhí)行跳轉(zhuǎn)的
let mut loops = vec![];
// 通過(guò)此對(duì)象分配可寫者娱、可執(zhí)行的內(nèi)存抡笼，并且需要將代碼都寫入到此內(nèi)存中
let mut ops = dynasmrt::x64::Assembler::new()?;
// 代碼的入口點(diǎn)
let entry_point = ops.offset();
dynasm!(ops
// 聲明要使用的匯編語(yǔ)法
; .arch x64
// 將內(nèi)存的起始地址放到 rcx，rdi存儲(chǔ)的是我們生成的函數(shù)的第一個(gè)參數(shù)
; mov rcx, rdi
);
for ir in code.instrs {
match ir {
IR::SHL(x) => dynasm!(ops
; sub rcx, x as i32 // sp -= x
),
IR::SHR(x) => dynasm!(ops
; add rcx, x as i32 // sp += x
),
IR::ADD(x) => dynasm!(ops
; add BYTE [rcx], x as i8 // sp* += x
),
IR::SUB(x) => dynasm!(ops
; sub BYTE [rcx], x as i8 // sp* -= x
),
IR::PUTCHAR => dynasm!(ops
; mov r12, rcx
; mov rdi, [rcx]
; mov rax, QWORD putchar as _
; sub rsp, BYTE 0x28 // Make stack 16 byte aligned
; call rax
; add rsp, BYTE 0x28
; mov rcx, r12
),
IR::GETCHAR => {
// 用的少黄鳍，省略
}
IR::JIZ(_) => {
let l = ops.new_dynamic_label();
let r = ops.new_dynamic_label();
loops.push((l, r));
// 如果指針指向的單元值為零推姻，向后跳轉(zhuǎn)到對(duì)應(yīng)的 ] 指令的次一指令處
dynasm!(ops
; cmp BYTE [rcx], 0
; jz => r
; => l
)
}
IR::JNZ(_) => {
let (l, r) = loops.pop().unwrap();
// 如果指針指向的單元值不為零，向前跳轉(zhuǎn)到對(duì)應(yīng)的 [ 指令的次一指令處
dynasm!(ops
; cmp BYTE [rcx], 0
; jnz => l
; => r
)
}
}
}
dynasm!(ops
; ret
);
// 對(duì) ops 對(duì)象調(diào)用 finalize 后才會(huì)實(shí)際分配內(nèi)存
let exec_buffer = ops.finalize().unwrap();
// 給 Brainfuck 源碼執(zhí)行時(shí)所使用的內(nèi)存
let mut memory: Box<[u8]> = vec![0; 65536].into_boxed_slice();
// 內(nèi)存起始地址
let memory_addr_from = memory.as_mut_ptr();
// 內(nèi)存結(jié)束地址
let memory_addr_to = unsafe { memory_addr_from.add(memory.len()) };
// 將 exec_buffer 這塊可寫际起、可執(zhí)行的內(nèi)存轉(zhuǎn)換成一個(gè)函數(shù)
let fun: fn(memory_addr_from: *mut u8, memory_addr_to: *mut u8) =
unsafe { std::mem::transmute(exec_buffer.ptr(entry_point)) };
// 執(zhí)行該函數(shù)
fun(memory_addr_from, memory_addr_to);
Ok(())
}
}
fn main() -> Result<(), Box<dyn std::error::Error>> {
let args: Vec<String> = std::env::args().collect();
assert!(args.len() >= 2);
let mut f = std::fs::File::open(&args[1])?;
let mut c: Vec<u8> = Vec::new();
f.read_to_end(&mut c)?;
let mut i = Interpreter::default();
i.run(c)
}
