用Rust實作Brainfuck的JIT編譯器

x64彙編簡介

Linux x64 彙編/Hello World

我們每天産出大量的垃圾代碼，我們每個人都可以像這樣簡單地編寫最簡單的代碼：

#include <stdio.h>

int main() {
  int x = 10;
  int y = 100;
  printf("x + y = %d\n"，x + y);
  return 0;
}

希望讀者們都可以了解上述 C 代碼的作用。但是，此代碼在底層如何工作？我認為并非所有人都能回答這個問題，我也是。我可以用Haskell，Erlang，Go 等進階程式設計語言編寫代碼，但是在它們編譯後我并不知道它在底層是如何工作的。是以，我決定采取一些更深入的步驟，進行記錄，并描述我對此的學習過程。希望這個過程不僅僅隻是對我來說很有趣。讓我們開始吧。

準備

開始之前，我們必須準備一些事情，如我所寫的那樣，我目前使用 Ubuntu 18.04，是以我的文章将針對該作業系統和體系結構。不同的 CPU 支援不同的指令集，目前我使用 Intel 的 64 位 CPU。同時我也将使用 NASM 文法。你可以使用以下方法安裝它：

$ apt install nasm

記住，Netwide Assembler（簡稱 NASM）是一款基于英特爾 x86 架構的彙編與反彙編工具。這就是我們目前需要的工具。

NASM 文法

在這裡，我将不介紹完整的彙編文法，我們僅提及其龐大文法的一小部分，也是那些我們将在本文中使用到的部分。通常， NASM 程式分為幾個段（section），在這篇文章中，我們将遇到以下兩個段：

資料段：data section
文本段：text section

資料段部分用于聲明常量，此資料在運作時不會更改。聲明資料部分的文法為：

section .data

文本段部分用于代碼。該部分必須以全局聲明

_start

開頭，該聲明告訴核心程式從何處開始執行。

section .text
global _start
_start:

注釋以符号

開頭。每條 NASM 源代碼行都包含以下四個字段的某種組合：

[label:] instruction [operands] [; comment]

方括号中的字段是可選的。基本的 NASM 指令由兩部分組成，第一部分是要執行的指令的名稱，第二部分是該指令的操作數。例如：

mov rax, 48 ; put value 48 in the rax register

Hello World!

讓我們用 NASM 編寫第一個程式。當然，這将是經典的 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

是的，它看起來一點都不像

printf("Hello World!\n")

。讓我們嘗試了解它是什麼以及它如何工作。首先看第一和第二行，我們定義了資料段部分，并将

msg

常量與 “Hello, World!” 值放在一起。現在，我們可以在代碼中使用此常量。接下來是聲明文本段部分和程式的入口。程式将從第 7 行開始執行。現在開始最有趣的部分，我們已經知道

mov

指令是什麼，它獲得 2 個操作數，并将第二個的值放在第一位。但是這些

rax, rdi

等是什麼？正如我們在 Wikipedia 中可以看到的：

中央處理器（CPU）是計算機中的硬體，它通過執行系統的基本算術，邏輯和輸入/輸出操作來執行計算機程式的指令。

好的，CPU 會執行一些運算。但是，在哪裡可以擷取該運算的資料，是記憶體嗎？從記憶體中讀取資料并将資料寫回到記憶體中會減慢處理器的速度，因為它涉及通過控制總線發送資料請求的複雜過程。是以，CPU 具有自己的内部存儲器，稱為寄存器。

是以，當我們編寫

mov rax, 1

時，意味着将 1 放入

rax

寄存器。現在我們知道

rax

，

rdi

，

rsi

等代表了什麼了，但是還需要知道什麼時候該使用

rax

，什麼時候使用

rdi

等。

rax ：臨時寄存器，當我們調用 syscall 時， rax 必須包含 syscall 号碼，是以後面的數字就是 syscall 的号碼
rdi ：用于将第 1 個參數傳遞給函數
rsi ：用于将第 2 個參數傳遞給函數
rdx ：用于将第 3 個參數傳遞給函數

換句話說，我們隻是在調用

sys_write

的 syscall。看看

sys_write

的定義：

size_t sys_write(unsigned int fd, const char * buf, size_t count);

它具有3個參數：

fd ：檔案描述符。對于 stdin，stdout 和 stderr 來說，其值分别為 0，1 和 2
buf ：指向字元數組
count ：指定要寫入的位元組數

我們将 1 寫入

rax

，這意味我們要調用

sys_write

。完整的

syscall

清單可以在 https://github.com/torvalds/linux/blob/master/arch/x86/entry/syscalls/syscall_64.tbl 找到。在完成該調用之後，将 60 寫入

rax

，這意味着我們要調用

sys_exit

退出程式，且退出碼為 0。

最後，讓我們來建構這個程式，我們需要執行以下指令：

$ nasm -f elf64 -o main.o main.asm
$ ld -o main main.o

嘗試運作這個程式吧！

什麼是JIT

本文部分翻譯自：https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html.

“JIT” 一詞往往會喚起工程師内心最深處的恐懼和崇拜，通常這并沒有什麼錯，隻有最核心的編譯器團隊才能夢想建立這種東西。它會使你聯想到 JVM 或 .NET，這些家夥都是具有數十萬行代碼的超大型運作時。你永遠不會看到有人向你介紹 “Hello World!” 級别的 JIT 編譯器，但事實上隻需少量代碼即可完成一些有趣的工作。本文試圖改變這一點。

編寫一個 JIT 編譯器隻需要四步，就像把大象裝到冰箱裡一樣。

申請一段可寫和可執行的記憶體
将源碼翻譯為機器碼（通常經過彙編）
将機器碼寫入第一步申請的記憶體
執行這部分記憶體

Hello, JIT World: The Joy of Simple JITs

事不宜遲，讓我們跳進我們的第一個 JIT 程式。該代碼是特定于 64 位 Unix 的，因為它使用了

mmap()

。鑒于此讀者需要擁有支援該代碼的處理器和作業系統。

#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 行代碼是一個合法的 JIT。它動态生成一個函數，該函數傳回運作時指定的整數，然後運作該函數。讀者可以驗證其是否正常運作：

$ gcc -o jit jit.c
$ ./jit 42
$ echo $?
# 42

您會注意到，代碼中使用

mmap()

配置設定記憶體，而不是使用

malloc()

從堆中擷取記憶體的正常方法。這是必需的，因為我們需要記憶體是可執行的，是以我們可以跳轉到它而不會導緻程式崩潰。在大多數系統上，棧和堆都配置為不允許執行，因為如果你的代碼跳轉到了棧或堆，則意味着程式發生了很大的錯誤，這是由作業系統的記憶體結構決定的。更糟糕的是，利用緩沖區溢出的黑客可以使用可執行堆棧來更輕松地利用該漏洞。是以，通常我們希望避免映射任何可寫和可執行的記憶體，這也是在你自己的程式中遵循此規則的好習慣。我在上面打破了這個規則，但這隻是為了使我們的第一個程式盡可能簡單。

dynasm介紹

DynASM 是為 LuaJIT 編寫的 JIT 彙編預處理器和微型運作時庫。簡單來講，DynASM完成兩個工作，一個是預處理，把你寫的彙編指令（對，沒有Elixir，DynASM并不能直接把邏輯變成彙編，需要你手動把你的邏輯用彙編語言重寫一遍，是以性能也取決于你的彙編代碼寫的好壞）變成真正的二進制機器碼，另一個是提供一個微型運作時，來處理那些必須推遲到運作時才能執行的代碼。

而 Rust 生态中也有一個參照 DynASM 所開發的項目，也叫 dynasm：

https://crates.io/crates/dynasm

為了在 Rust 中編寫彙編代碼，我們将使用這個名為 dynasm-rs 的擴充庫。由于 dynasm-rs 是對著名 C/C++ 庫 dynasm 的模仿，後者則是 LuaJIT 項目的重要組成部分。是以，其作用與 Lua 的 DynASM 是一樣的，dynasm-rs 是一個彙編語言編譯器，它可以将彙編代碼編譯為機器碼。

在項目中的

Cargo.toml

檔案裡添加相應的依賴項：

[dependencies]
dynasm = "1.2.3"
dynasmrt = "1.2.3"

實作BrainfuckJIT

在生活中，如果有兩種合理但不同的方法時，你應該總是研究兩者的結合，看看能否找到兩全其美的方法。我們稱這種組合為雜合（hybrid）。例如，為什麼隻吃巧克力或簡單的堅果，而不是将兩者結合起來，成為一塊可愛的堅果巧克力呢？

在 1960 年約翰·麥卡錫偶然發現了此方法。在他的重要論文《符号表達式的遞歸函數及其在機器上的計算》（Recursive functions of symbolic expressions and their computation by machine, Part I）第一部分中，他提到了在運作時被轉換的函數，是以不需要編譯并執行系統。JIT 編譯是兩種傳統的機器代碼翻譯方法：提前編譯（AOT）和解釋（Interpreter）的結合，它結合了兩者的優點和缺點。

讓我們回憶一下第一篇文章的内容，是關于編寫 JIT 所需要的 4 個步驟：

申請一段可寫和可執行的記憶體
将源碼翻譯為機器碼（通常經過彙編）
将機器碼寫入第一步申請的記憶體
執行這部分記憶體

首先申請一段記憶體作為 Brainfuck 解釋器的紙帶，并取得該段紙帶在記憶體中的起始位址和終止位址：

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()) };

我們将整個 Brainfuck 程式看作一個函數，它接收兩個參數：紙帶起始位址和終止位址。根據 nasm 規範，函數的第一個參數被存在

rdi

寄存器中，第二個參數被存在

rsi

寄存器中。我們将它們複制到

r12

和

r13

這兩個寄存器内持久化存儲。同時

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

函數，使之後的彙編代碼中可以調用這兩個函數。

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();
}

之後, 将每個 IR 翻譯為語義等價的彙編代碼如下。首先

SHL(x)

，

SHR(x)

，

ADD(x)

和

SUB(x)

4 個操作符最為簡單，它們均隻使用一行彙編代碼即可完成翻譯。之後是

PUTCHAR

與

GETCHAR

，們遵循彙編中函數調用的邏輯，的參數與位址按照規則寫入指定寄存器，然後，用

call

指令調用該函數。最後是

JIZ(x)

與

JNZ(x)

，它們，流程控制，其對應，編代碼通過組合使用标簽，比較運算，

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
            )
        }
    }
}

同時不要忘記為該函數寫上

return

：

dynasm!(ops
    ; ret
);

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);

#![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>> {
        // 将源檔案中的内容轉換為 Opcode 數組
        let opcode_code = opcode::Code::from(data)?;
        // 将 opcode 轉換為 ir code
        let code = ir_code::Code::from(opcode_code.instrs)?;
        // 用來當比對到 [ 和 ] 時執行跳轉的
        let mut loops = vec![];

        // 通過此對象配置設定可寫、可執行的記憶體，并且需要将代碼都寫入到此記憶體中
        let mut ops = dynasmrt::x64::Assembler::new()?;
        // 代碼的入口點
        let entry_point = ops.offset();

        dynasm!(ops
            // 聲明要使用的彙編文法
            ; .arch x64
            // 将記憶體的起始位址放到 rcx，rdi存儲的是我們生成的函數的第一個參數
            ; 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));
                    // 如果指針指向的單元值為零，向後跳轉到對應的 ] 指令的次一指令處
                    dynasm!(ops
                        ; cmp BYTE [rcx], 0
                        ; jz => r
                        ; => l
                    )
                }
                IR::JNZ(_) => {
                    let (l, r) = loops.pop().unwrap();
                    // 如果指針指向的單元值不為零，向前跳轉到對應的 [ 指令的次一指令處
                    dynasm!(ops
                        ; cmp BYTE [rcx], 0
                        ; jnz => l
                        ; => r
                    )
                }
            }
        }
        dynasm!(ops
            ; ret
        );

        // 對 ops 對象調用 finalize 後才會實際配置設定記憶體
        let exec_buffer = ops.finalize().unwrap();
        // 給 Brainfuck 源碼執行時所使用的記憶體
        let mut memory: Box<[u8]> = vec![0; 65536].into_boxed_slice();
        // 記憶體起始位址
        let memory_addr_from = memory.as_mut_ptr();
        // 記憶體結束位址
        let memory_addr_to = unsafe { memory_addr_from.add(memory.len()) };
        // 将 exec_buffer 這塊可寫、可執行的記憶體轉換成一個函數
        let fun: fn(memory_addr_from: *mut u8, memory_addr_to: *mut u8) =
            unsafe { std::mem::transmute(exec_buffer.ptr(entry_point)) };
        // 執行該函數
        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)
}

用Rust實作Brainfuck的JIT編譯器

x64彙編簡介

Linux x64 彙編/Hello World

準備

NASM 文法

Hello World!

什麼是JIT

Hello, JIT World: The Joy of Simple JITs

dynasm介紹

實作BrainfuckJIT

繼續閱讀

Rust Actix Web 中關于 HttpServer 的一點思考

第一個Rust程式報錯

MStar 方案屏參配置

【屏類型結構體定義PanelType】文檔位置：《apiPNL.h》

rust中slice panicked at 'byte index 5 is not a char boundary' 問題解決辦法

作業系統學習筆記——輸入輸出（I/O）管理

淺談面向對象前言面向對象？來說說繼承結論

[單片機][N76E003][MCP4017][MCP4018][MCP4019] 數字電位器使用方法例子代碼

程式小白學Rust-----day01

12-陷阱門

電子工程師名片——SPI Flash

單片機複習題

rust hello-world項目建立與編譯運作

rust學習（二）mio和socketpair及多線程

如何使用Python編寫一個Lisp解釋器

C# IL代碼、JIT編譯器、MSIL、Ildasm.exe