由于我喜歡在較低級別（Low-level）的應用中（編譯器，解釋器，解析器，虛擬機等等）工作，所以我覺得寫一篇關于用C編程語言構建虛擬機的文章，是非常有必要的。我認為這篇文章除了能夠讓你了解到虛擬機的工作原理外，還可以讓你了解到較低級別的編程過程。

準備內容

• 使用的編譯器類型：我正在使用的是clang，它是輕量級編譯器，但你可以使用任何現代編譯器；
• 文本編輯器：我建議當編寫C語言時，通過IDE編輯文本編輯器，我將使用Emacs;
• 基本的編程知識：比如什么是變量，流量控制，函數，結構等；
• GNU Make：GNU Make主要用于自動化構建可執行程序（庫文件），這樣我們就不需要在終端中一遍又一遍地編寫相同的命令來編譯代碼。Make的功能包括:自動化構建和安裝；增量編譯及自動更新；適用于多語言，比如c/c++、java、php等；支持自定義功能擴展（只要有意義，都是可以放到makefile中）。

[[233734]]

為什么你應該寫一個虛擬機？

以下是你應該編寫虛擬機的一些原因：

1.你需要更深入地了解計算機的工作方式，本文將幫助你了解你的計算機在較低級別的環境中是如何運行工作的？而虛擬機則提供了一個非常簡單的抽象層；

2.順便了解一些虛擬機的知識；

3.深入了解一下編程語言的工作原理，現在的各種語言都針對虛擬機，比如JVM，Lua VM，FaceBook 的 Hip—Hop VM（PHP/Hack）等。

指令集

指令集會相對簡單，我將簡要介紹一下，例如如何從寄存器中移動值或跳轉到其他指令。

假設我們的虛擬機有一組寄存器：A，B，C，D，E和F，且這些都是通用寄存器，這意味著它們可以用于存儲任何東西。這與專用寄存器不同，例如在x86上，ip, flag, ds, …程序是只讀指令集。如果虛擬機是一個基于棧的虛擬機，這意味著它有一個我們可以壓棧和彈出值的棧，另外，該虛擬機還有一些我們也可以使用的寄存器。基于棧的虛擬機比基于寄存器的虛擬機實現起來要簡單得多。

下面是我將要實施的一個指令集的示例：

PSH 5       ; pushes 5 to the stack 
PSH 10      ; pushes 10 to the stack 
ADD         ; pops two values on top of the stack, adds them pushes to stack 
POP         ; pops the value on the stack, will also print it for debugging 
SET A 0     ; sets register A to 0 
HLT         ; stop the program 

以上就是我的指令集，請注意，POP指令將打印我們彈出的指令，其中很多是調試用的。ADD會將結果壓棧到棧，所以我們可以從棧中的彈出值來驗證它是否存在。我還在其中包含了一條SET指令，這樣你就可以了解如何訪問和寫入寄存器了。你也可以嘗試執行像MOV A，B（將值A移至B）的指令， HLT是顯示我已經完成程序執行的指令。

虛擬機如何工作？

其實虛擬機比你想象的要簡單，它的工作模式遵循一個簡單的規律，即“指令周期（instruction cycle）”，整個過程包括讀取、解碼、執行三大塊。首先，你要讀取指令集，然后才能解碼指令并執行解碼后的指令。

項目結構

在我開始編程之前，需要做一些準備工作。我需要一個文件夾來放置項目，我喜歡將項目放置于~/Dev下。另外，我需要一個C編譯器（我使用的是 clang 3.4）。以下是我在終端中設置我的項目的過程，假設你已經擁有一個?/ dev /目錄，不過你可以把它放到任何你想要的位置。

$ cd ~/dev/ 
$ mkdir mac 
$ cd mac 
$ mkdir src 

上面就是我把cd放到我的~/dev目錄的過程，首先，我會創建一個目錄（我稱之為VM“mac”）。然后，我進入該目錄并創建我的src目錄，這個目錄被用于存放代碼。

Makefile文件

我的makefile相對比較簡單，由于該文件不需要將任何東西分隔成多個文件，所以其中也不會包含任何東西，我只需要用一些標志來編譯文件即可。

SRC_FILES = main.c 
CC_FLAGS = -Wall -Wextra -g -std=c11 
CC = clang 
 
all: 
    ${CC} ${SRC_FILES} ${CC_FLAGS} -o mac 

現在這應該足夠了，你以后可以隨時改進它，但只要它能完成這項工作，我們應該沒問題。

指令編程

現在就可以開始編寫虛擬機的代碼了。首先，為了解釋指令編程，我必須用到一個枚舉，因為我們的指令基本上是從0到X的數字。事實上，匯編程序將獲取你的匯編文件，并將所有操作轉換為對應的數字。例如，如果你為mac編寫一個匯編程序，它將把所有MOV操作轉換為數字0。

typedef enum { 
    PSH, 
    ADD, 
    POP, 
    SET, 
    HLT 
} InstructionSet; 

現在我可以將測試程序存儲為一個數組，然后寫一個簡單的程序用于測試，比如將5和6相加，然后將它們用POP指令打印出來。如果你愿意，你可以定義一個指令將棧頂的值打印出來。

指令應該存儲成一個數組，我將在文檔的頂部定義它。但你可以把它放在一個頭文件中，以下是我的測試程序。

const int program[] = { 
    PSH, 5, 
    PSH, 6, 
    ADD, 
    POP, 
    HLT 
}; 

上面的程序會將5和6壓棧入棧，執行add指令，該指令將彈出棧中的兩個值，將它們加在一起并將結果壓棧回棧。然后會彈出結果，出于調試目的，我的彈出指令將打印這兩個值。

***，HLT指令意味著終止程序。如果我們要控制流程，可以隨時終止程序。不過，如果我們沒有任何指示，我們的虛擬機***也將自然終止。

現在我實現了虛擬機的讀取、解碼、執行的過程。但是要記住，我沒有解碼任何東西，因為我給出的是原始指令。

獲取當前指令

因為我已將程序存儲為一個數組，所以獲取當前指令很簡單。虛擬機有一個計數器，通常稱為程序計數器，不過有時也叫做指令指針等，通常它們分別縮寫為PC或IP。

現在，我只需在代碼頂部創建一個名為ip的變量，并將其設置為0。

int ip = 0; 

這個ip代表指令指針，由于我已經將程序本身存儲為一個整數數組，固ip變量作為數組中的索引，表示當前正在執行的指令。

int ip = 0; 
 
int main() { 
    int instr = program[ip]; 
    return 0; 
} 

如果打印變量instr，則PSH將顯示為0，因為變量instr是我們枚舉里的***個值。不過，我們也可以寫一個取回函數，如下所示：

int fetch() { 
    return program[ip]; 
} 

該函數在被調用時將返回當前指令。那么，如果我們想要下一條指令呢？我們只要增加指令指針即可。

int main() { 
    int x = fetch(); // PSH 
    ip++; // increment instruction pointer 
    int y = fetch(); // 5 
} 

那么我們該如何實現自動化呢？我們知道程序只有執行通過HLT指令時，才會停止，所以該程序本身就是一個***循環。

#include <stdbool.h>  
 
bool running = true; 
 
int main() { 
    while (running) { 
       int x = fetch(); 
       if (x == HLT) running = false; 
       ip++; 
    } 
} 

我目前要做的是循環遍歷每條指令，檢查指令的值是否為HLT，如果是，則停止循環，否則就不斷重復。

一條指令的評估

這是虛擬機的運行要點，其實虛擬機非常簡單，你可以編寫一個巨大的switch語句。而這么做就是為了加快運行速度，與之相對的是，對于所有指令和使用execute方法的某個抽象類或接口，都要使用HashMap。

switch語句中的每個case都是我們在枚舉中定義的指令，這個eval函數將使用一個簡單的指令參數來評估指令。除非你正在使用操作數，否則不要在此函數中執行任何指令指針增量。

void eval(int instr) { 
    switch (instr) { 
    case HLT: 
        running = false; 
        break; 
    } 
} 

我會將此函數添加回虛擬機的主循環中：

bool running = true; 
int ip = 0; 
 
// instruction enum 
// eval function 
// fetch function 
 
int main() { 
    while (running) { 
        eval(fetch()); 
        ip++; // increment the ip every iteration 
    } 
} 

棧

不過在添加其他指令之前，我們需要一個棧。棧是一個非常簡單的數據結構。我們將使用這個數組而不是一個鏈表。因為我的棧是固定大小的，所以不必擔心大小的調整。使用數組而不是鏈接列表，在緩存效率方面會更占優勢。

與我們如何擁有一個用于索引程序數組的ip類似，現在我們需要一個棧指針（sp）來顯示我們在棧數組中的位置。

下面是我的一個棧的數據結構的詳細列表：

[] // empty 
 
PSH 5 // put 5 on **top** of the stack 
[5] 
 
PSH 6 // 6 on top of the stack 
[5, 6] 
 
POP // pop the 6 off the top 
[5] 
 
POP // pop the 5 
[] // empty 
 
PSH 6 // push a 6... 
[6] 
 
PSH 5 // etc.. 
[6, 5] 

讓我們按照棧來分解我們的程序:：

PSH, 5, 
PSH, 6, 
ADD, 
POP, 
HLT 

首先我把5壓棧到棧上：

[5] 

然后把6壓棧到棧上：

[5, 6] 

然后add指令將彈出這些值并將它們加在一起，***將結果壓棧到棧上。

[5, 6] 
 
// pop the top value, store it in a variable called a 
a = pop; // a contains 6 
[5] // stack contents 
 
// pop the top value, store it in a variable called b 
b = pop; // b contains 5 
[] // stack contents 
 
// now we add b and a. Note we do it backwards, in addition 
// this doesn't matter, but in other potential instructions 
// for instance divide 5 / 6 is not the same as 6 / 5 
result = b + a; 
push result // push the result to the stack 
[11] // stack contents 

你看出來了嗎，我的棧指針在哪里起了作用？棧指針被設置為-1，這意味著它是空的。數組在C中為零索引，所以如果sp為0，它將被設置為C編譯器在其中引發的隨機數，因為數組的內存未被清零。

如果現在我壓棧3個值，則sp將為2.因此，這里是一個包含3個值的數組：

      -> sp -1 
   psh -> sp 0 
   psh -> sp 1 
   psh -> sp 3 
 
 sp points here (sp = 2) 
      | 
      V 
1, 5, 9] 
0  1  2 <- array indices or "addresses" 

現在我從棧上出棧一次，就需要減小棧頂指針。比如我接下來要把9出棧，那么棧頂將變為5。

sp points here (sp = 1) 
        | 
        V 
    [1, 5] 
     0  1 <- these are the array indices 

所以，當我想知道棧頂內容的時候，只需要查看sp的當前值，希望你現在應該知道棧是如何工作的。

現在我們用C語言實現它，用C語言實現一個棧是很簡單的，和ip一樣，我們也應該定義sp變量和數組，這個數組就是棧。

int ip = 0; 
int sp = -1; 
int stack[256]; 
 
... 

現在，如果我們想將壓棧一個值，就要增加棧指針，然后在當前sp中設置該值。

這個命令的順序是非常重要的，如果你先設置值，再增加sp，那你會得到一些不好的行為，因為我們在索引-1處寫入了內存。

// sp = -1 
sp++; // sp = 0 
stack[sp] = 5; // set value at stack[0] -> 5 
// top of stack is now [5] 

在我們的eval函數中，可以像以下這樣進行壓棧。

void eval(int instr) { 
    switch (instr) { 
        case HLT: { 
            running = false; 
            break; 
        } 
        case PSH: { 
            sp++; 
            stack[sp] = program[++ip]; 
            break; 
        } 
    } 
} 

可以很明顯看到，這與以前的eval函數有一些區別。首先，我們把每個case語句塊放到大括號里。你可能不理解這樣做的用意，它可以讓你在每條case的作用域里定義變量。雖然現在不需要定義變量，但將來會用到，并且這樣做可以很容易得讓所有的case語句塊保持一致的風格。

其次，是program[++ip] 表達式，該表達式是負責PSH指令所需的操作數。因為我們的程序存儲在一個數組里，PSH指令需要獲得一個操作數。操作數本質是一個參數，就像當你調用一個函數時，你可以給它傳遞一個參數。這種情況我們稱作壓棧數值5（PSH, 5）。我們可以通過增加指令指針ip來獲取操作數。當ip為0時，這意味著執行到了PSH指令，接下來我們希望取得壓棧的數值。這可以通過ip自增的方法實現，實現后，就需要跳到下一條指令否則會引發奇怪的錯誤。當然我們也可以把sp++簡化到stack[++sp]里。

program = [ PSH, 5, PSH, 6, ] 
            0    1  2    3 
 
when pushing: 
ip starts at 0 (PSH) 
ip++, so ip is now 1 (5) 
sp++, allocate some space on the stack 
stack[sp] = program[ip], put the value 5 on the stack 

POP指令非常簡單，只需對堆棧指針進行遞減操作即可。但是，如果你想讓pop指令打印剛剛彈出的值即出棧值,還要做很多工作。

case POP: { 
    // store the value at the stack in val_popped THEN decrement the stack ptr 
    int val_popped = stack[sp--]; 
 
    // print it out! 
    printf("popped %d\n", val_popped); 
    break; 
} 

***是添加ADD指令，ADD指令,是一種計算機指令,含義為兩數相加(不帶進位)。這可能會讓你覺得有點棘手，而這正是case語句塊放到大括號里的技巧所在，因為我們現在要引入了一些變量了。

case ADD: { 
    // first we pop the stack and store it as 'a' 
    int a = stack[sp--]; 
 
    // then we pop the top of the stack and store it as 'b' 
    int b = stack[sp--]; 
 
    // we then add the result and push it to the stack 
    int result = b + a; 
    sp++; // increment stack pointer **before** 
    stack[sp] = result; // set the value to the top of the stack 
 
    // all done! 
    break; 
} 

在具體操作之前，請注意，這里的某些操作的順序很重要！ 

5 / 4 != 4 / 5 

棧是LIFO，全稱First in, First out，先進先出。也就是說，如果先進棧5再進棧4，就會先出棧4，然后出棧5。如果我們確實執行了pop() / pop()，那么這將會給我們錯誤的表達式，因此，確保順序正確是至關重要的。

寄存器

寄存器是虛擬機中的選配件，很容易實現。之前提到過我們可能需要六個寄存器：A，B，C，D，E和F。和實現指令集一樣，我們也用一個枚舉來實現它們。

typedef enum { 
   A, B, C, D, E, F, 
   NUM_OF_REGISTERS 
} Registers; 

不過這里有一個小技巧，枚舉的***會出現NUM_OF_REGISTERS。通過這個函數可以獲取寄存器的大小，即便你又添加了其它的寄存器，也可以獲得他們的大小。

我會將我的寄存器存儲在一個數組中，這是因為我要使用枚舉，A = 0，B = 1，C = 2等。所以當我想設置寄存器A時，就像說register [A] = some_value一樣簡單。

int registers[NUM_OF_REGISTERS]; 

打印寄存器A中的值：

printf("%d\n", registers[A]); // prints the value at the register A 

指令指針

記住有一條分支指令的指針是要指向當前指令的，由于現在是虛擬機源代碼，所以***的辦法是將指令指針作為一個寄存器，這樣你就可以從虛擬機程序中進行讀取和各種操作。

typedef enum { 
    A, B, C, D, E, F, PC, SP, 
    NUM_OF_REGISTERS 
} Registers; 

現在我需要移植代碼來實際使用這些指令和堆棧指針，最快的方法是刪除棧頂的sp和ip變量，并用以下的定義替換它們。

#define sp (registers[SP]) 
#define ip (registers[IP]) 

這樣你就不必重寫很多代碼了，就能***地運行了。不過缺點是，不能很好地擴展，并且它會混淆一些代碼，所以我建議不要使用這種方法，但對于一個簡單的虛擬機來說，用一下也無妨。

當涉及到分支代碼時，我會給你一個提示。有了新的IP寄存器后，我們可以通過向這個IP寫入不同的值來進行分支。試試下面這個例子，看看它能做什么。

PSH 10 
SET IP 0 

這類似于很多人都熟悉的基本程序:

10 PRINT "Hello, World" 
20 GOTO 10 

但是，由于我們不斷地進行進棧，所以一旦進棧的量超過空間量，就將發生棧溢出。

請注意，每個 ‘word’是一個指令，所以程序以下所示。

              ;  these are the instructions 
PSH 10        ;  0 1 
PSH 20        ;  2 3 
SET IP 0      ;  4 5 6 

如果我們想跳到第二組指令，我們將IP寄存器設置為2而不是0。

總結

閱讀完本文后，如果你在項目根目錄中運行make，則可以執行虛擬機：./mac。

你可以在這里查看github上的源代碼，如果你想用MOV和SET指令來看虛擬機的更新版本，那么檢查一下mac-improved目錄，我們在本文中實現的虛擬機的源代碼位于mac.c中