使用 C 語言實現一個虛擬機
使用 C 語言實現一個虛擬機
介紹
GitHub 展示了我們將會構建的東西, 你也可以在發生錯誤的時候拿你的代碼同這個資源庫進行對比. GitHub 資源庫
我考慮過會寫一篇有關使用C語言構建專屬虛擬機的文章. 我喜歡研究“底層”的應用程序，比方說編譯器、解釋器以及虛擬機。我也愛談論到它們。我也有另外一個系列的有關使用Go來編寫一個解釋器的文章（目前正在準備中）。我也在開發自己的編程語言 Alloy.
必要的準備工作及注意事項：
在開始之前需要做以下工作：
-
一個C編譯器——我使用了 clang 3.4，也可以用其它支持 c99/c11 的編譯器；
-
文本編輯器——我建議使用基于IDE的文本編輯器，我使用 Emacs;
-
基礎編程知識——最基本的變量，流程控制，函數，數據結構等；
-
Make 腳本——能使程序更快一點。
為什么要寫個虛擬機？
有以下原因：
-
想深入了解計算機工作原理。本文將幫助你了解計算機底層如何工作，虛擬機提供簡潔的抽象層，這不就是一個最好的學習它們原理的方法嗎？
-
更深入了解一些編程語言是如何工作。例如，當下多種經常使用那些語言的虛擬機。包括JVM，Lua VM，非死book 的 Hip—Hop VM（PHP/Hack） 等。
-
只是因為有興趣學習虛擬機。
指令集
我們將要實現一種非常簡單的自定義的指令集。我不會講一些高級的如位移寄存器等，希望在讀過這篇文章后掌握這些。
我們的虛擬機具有一組寄存器，A,B,C,D,E, 和F。這些是通用寄存器，也就是說，它們可以用于存儲任何東西。一個程序將會是一個只讀指令序列。這個虛擬機是一個基于堆棧的虛擬機，也就是說它有一個可以讓我們壓入和彈出值的堆棧，同時還有少量可用的寄存器。這要比實現一個基于寄存器的虛擬機簡單的多。
言歸正傳，下面是我們將要實現的指令集：
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）這樣的指令。HTL 指令是為了告訴我們程序已經運行結束。
虛擬機是如何工作的呢？
現在我們已經到了本文最關鍵的部分，虛擬機比你想象的簡單，它們遵循一個簡單的模式：讀取；解碼；執行。首先，我們從指令集合或代碼中讀取下一條指令，然后將指令解碼并執行解碼后的指令。為簡單起見，我們忽略了虛擬機的編碼部分，典型的虛擬機將會把一個指令（操作碼和它的操作數）打包成一個數字，然后再解碼這個指令。
項目結構
開始編程之前，我們需要設置好我們的項目。第一，你需要一個C編譯器（我使用 clang 3.4）。還需要一個文件夾來放置我們的項目，我喜歡將我的項目放置于~/Dev：
$cd ~/Dev/ mkdir mac cd mac mkdir src
如上，我們先 cd 進入~/Dev 目錄，或者任何你想放置的位置，然后新建一個目錄（我稱這個虛擬機為"mac"）。然后再 cd 進這個目錄并新建我們 src 目錄，這個目錄用于放置代碼。
Makefile
makefile 相對直接，我們不需要將什么東西分成多個文件，也不用包含任何東西，所以我們只需要用一些標志來編譯文件：
SRC_FILES = main.c
CC_FLAGS = -Wall -Wextra -g -std=c11
CC = clang
all:
${CC} ${SRC_FILES} ${CC_FLAGS} -o mac 這對目前來說已經足夠了，你以后還可以改進它，但是只要它能完成這個工作，我們應該滿足了。
指令編程（代碼）
現在開始寫虛擬機的代碼了。第一，我們需要定義程序的指令。為此，我們可以使用一個枚舉類型enum，因為我們的指令基本上是從0到X的數字。事實上，可以說你是在組裝一個匯編文件，它會使用像 mov 這樣的詞，然后翻譯成聲明的指令。
我們可以只寫一個指令文件，例如 PSH, 5 是0, 5，但是這樣并不易讀，所以我們使用枚舉器！
typedef enum {
PSH,
ADD,
POP,
SET,
HLT
} InstructionSet; 現在我們可以將一個測試程序存儲為一個數組。我們寫一個簡單的程序用于測試：將5和6相加，然后將他們打印出來（用POP指令）。如果你愿意，你可以定義一個指令將棧頂的值打印出來。
指令應該存儲成一個數組，我將在文檔的頂部定義它；但你或許會將它放在一個頭文件中，下面是我們的測試程序：
const int program[] = {
PSH, 5,
PSH, 6,
ADD,
POP,
HLT
}; 上面的程序將會把5和6壓入棧，調用 ADD 指令，這將會把棧頂的兩個值彈出，相加后將結果壓回棧中，接下來我們彈出結果，因為 POP 指令將會打印這個值，但是你不必自己再做了，我已經做好并測試過了。最后，HLT 指令結束程序。
很好，這樣我們有了自己的程序。現在我們實現了虛擬機的讀取，解碼，求值的模式。但是要記住，我們沒有解碼任何東西，因為我們給出的是原始指令。也就是說我們只需要關注讀取和求值！我們可以將它們簡化成兩個函數 fetch 和 evaluate。
取得當前指令
因為我們已經將我們的程序存成了一個數組，所以很簡單的就可以取得當前指令。一個虛擬機有一個計數器，一般來說叫做程序計數器，指令指針等等，這些名字是一個意思取決于你的個人喜好。在虛擬機的代碼庫里，IP 或 PC 這樣的簡寫形式也隨處可見。
如果你之前有記得，我說過我們要把程序計數器以寄存器的形式存儲...我們將那么做——在以后。現在，我們只是在我們代碼的最頂端創建一個叫 ip 的變量，并且設置為 0。
int ip = 0;
ip 變量代表指令指針。因為我們已經將程序存成了一個數組，所以使用 ip 變量去指明程序數組中當前索引。例如，如果創建了一個被賦值了程序 ip 索引的變量 x，它將存儲我們程序的第一條指令。
[假設ip為0]
int ip = 0;
int main() {
int instr = program[ip];
return 0; 如果我們打印變量 instr，本來應是 PSH 的它將顯示為0，因為在他是我們枚舉里的第一個值。我們也可以寫一個取回函數像這樣：
int fetch() {
return program[ip];
} 這個函數將會返回當前被調用指令。太棒了，那么如果我們想要下一條指令呢？很容易，我們只要增加指令指針就好了：
int main() {
int x = fetch(); // PSH
ip++; // increment instruction pointer
int y = fetch(); // 5
} 那么怎樣讓它自己動起來呢？我們知道一個程序直到它執行 HLT 指令才會停止。因此我們使用一個無限的循環持續直到當前指令為HLT。
// INCLUDE <stdbool.h>!
bool running = true;
int main() {
while (running) {
int x = fetch();
if (x == HLT) running = false;
ip++;
}
} 這工作的很好，但是有點凌亂。我們正在循環每一條指令，檢查是否 HLT，如果是就停止循環，否則“吃掉”指令接著循環。
判斷一條指令
因此這就是我們虛擬機的主體，然而我們想要確實的評判每一條指令，并且使它更簡潔一些。好的，這個簡單的虛擬機，你可以寫一個“巨大”的 switch 聲明。讓 switch 中的每一個 case 對應一條我們定義在枚舉中的指令。這個 eval 函數將使用一個簡單的指令的參數來判斷。我們在函數中不會使用任何指令指針遞增除非我們想操作數浪費操作數。
void eval(int instr) {
switch (instr) {
case HLT:
running = false;
break;
}
} 因此如果我們在回到主函數，就可以像這樣使用我們的 eval 函數工作：
bool running = true;
int ip = 0;
// instruction enum here
// eval function here
// fetch function here
int main() {
while (running) {
eval(fetch());
ip++; // increment the ip every iteration
}
} 棧！
很好，那會很完美的完成這個工作。現在，在我們加入其他指令之前，我們需要一個棧。幸運的是，棧是很容易實現的，我們僅僅需要使用一個數組而已。數組會被設置為合適的大小，這樣它就能包含256個值了。我們也需要一個棧指針（常被縮寫為sp）。這個指針會指向棧數組。
為了讓我們對它有一個更加形象化的印象，讓我們來看看這個用數組實現的棧吧：
[] // empty PSH 5 // put 5 on **top** of the stack [5] PSH 6 [5, 6] POP [5] POP [] // empty PSH 6 [6] PSH 5 [6, 5]
那么，在我們的程序里發生了什么呢？
PSH, 5, PSH, 6, ADD, POP, HLT
我們首先把5壓入了棧
[5]
然后壓入6：
[5, 6]
接著添加指令，取出這些值，把它們加在一起并把結果壓入棧中：
[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
那么我們的棧指針在哪起作用呢？棧指針（或者說sp）一般是被設置為-1，這意味著這個指針是空的。請記住一個數組是從0開始的，如果沒有初始化sp的值，那么他會被設置為C編譯器放在那的一個隨機值。
如果我們將3個值壓棧，那么sp將變成2。所以這個數組保存了三個值：
sp指向這里（sp = 2） | V [1, 5, 9] 0 1 2 <- 數組下標
現在我們從棧上出棧一次，我們僅需要減小棧頂指針。比如我們接下來把9出棧，那么棧頂將變為5：
sp指向這里（sp = 1） | V [1, 5] 0 1 <- 數組下標
所以，當我們想知道棧頂內容的時候，只需要查看sp的當前值。OK，你可能想知道棧是如何工作的，現在我們用C語言實現它。很簡單，和ip一樣，我們也應該定義一個sp變量，記得把它賦為-1！再定義一個名為stack的數組，代碼如下：
int ip = 0; int sp = -1; int stack[256]; // 用數組或適合此處的其它結構 // 其它C代碼
現在如果我們想入棧一個值，我們先增加棧頂指針，接著設置當前sp處的值（我們剛剛增加的）。注意：這兩步的順序很重要！
// 壓棧5 // sp = -1 sp++; // sp = 0 stack[sp] = 5; // 棧頂現在變為5
所以，在我們的執行函數eval()里，可以像這樣實現push出棧指令：
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指令需要獲得一個操作數。操作數本質是一個參數，就像當你調用一個函數時，你可以給它傳遞一個參數。這種情況我們稱作壓棧數值5。我們可以通過增加指令指針（譯者注：一般也叫做程序計數器）ip來獲取操作數。當ip為0時，這意味著執行到了PSH指令，接下來我們希望取得下一條指令——即壓棧的數值。這可以通過ip自增的方法實現（注意：增加ip的位置十分重要，我們希望在取得指令前自增，否則我們只是拿到了PSH指令），接下來需要跳到下一條指令否則會引發奇怪的錯誤。當然我們也可以把sp++簡化到stack[++sp]里。
對于POP指令，實現非常簡單。只需要減小棧頂指針，但是我一般希望能夠在出棧的時候打印出棧值。
我省略了實現其它指令的代碼和swtich語句，僅列出POP指令的實現：
// 記得#include <stdio.h>!
case POP: {
int val_popped = stack[sp--];
printf("popped %d\n", val_popped);
break;
} 現在，POP指令能夠工作了！我們剛剛做的只是把棧頂放到變量val_popped里，接著棧頂指針減一。如果我們首先棧頂減一，那么將得到一些無效值，因為sp可能取值為0，那么我們可能把stack[-1]賦給val_popped，通常這不是一個好主意。
最后是ADD指令。這條指令可能要花費你一些腦細胞，同時這也是我們需要用大括號{}實現case語句內作用域的原因。
case ADD: {
// 首先我們出棧，把數值存入變量a
int a = stack[sp--];
// 接著我們出棧，把數值存入變量b
// 接著兩個變量相加，再把結果入棧
int result = a + b;
sp++; // 棧頂加1 **放在賦值之前**
stack[sp] = result; // 設置棧頂值
// 完成！
break;
} 寄存器
寄存器是虛擬機中的選配件，很容易實現。之前提到過我們可能需要六個寄存器：A，B，C，D，E和F。和實現指令集一樣，我們也用一個枚舉來實現它們。
typedef enum {
A, B, C, D, E, F,
NUM_OF_REGISTERS
} Registers; 小技巧：枚舉的最后放置了一個數 NUM_OF_REGISTERS。通過這個數可以獲取寄存器的個數，即便你又添加了其它的寄存器。現在我們需要一個數組為寄存器存放數值：
int registers[NUM_OF_REGISTERS];
接下來你可以讀取寄存器內的值：
printf("%d\n", registers[A]); // 打印寄存器A的值 修訂
我沒有在寄存器花太多心思，但你應該能夠寫出一些操作寄存器的指令。比如，如果你想實現任何分支跳轉，可以通過把指令指針（譯者注：或叫程序計數器）和/或棧頂指針存到寄存器里，或者通過實現分支指令。
前者實現起來相對快捷、簡單。我們可以這樣做，增加代表IP和SP的寄存器：
typedef enum {
A, B, C, D, E, F, PC, SP,
NUM_OF_REGISTERS
} Registers; 現在我們需要實現代碼來使用指令指針和棧頂指針。一個簡單的辦法——刪掉上面定義的sp和ip變量，用宏定義實現它們：
#define sp (registers[SP]) #define ip (registers[IP]) 譯者注：此處應同Registers枚舉中保持一致，IP應改為PC
這個修改恰到好處，你不需要重寫很多代碼，同時它工作的很好。
一些習題
如何實現分支指令？
我把問題留給你！記住指令指針（程序計數器）指向當前指令，并且其數值存儲在一個寄存器里。所以你需要寫一條指令設置寄存器的值，例如：SET REG value。接下來可以通過設置IP寄存器為某條指令的位置，進而跳轉到這條指令。如果你想看一個更復雜的例子，請訪問我的github代碼庫，那里有一個遞減某個值直到其為0的例子。
這里有幾道題目，實現MOV指令：MOV REG_A, REG_B。換句話說，MOV指令把數值從REG_A移到REG_B。同樣SET REG_A VALUE，會設置REG_A內容為VALUE。
你可以從github此處訪問源碼。如果你想更“高級”虛擬機是如何實現MOV和SET指令的，請瀏覽bettervm.c文件。你可以拿自己的實現和它作比較。如果你只想大體了解一下代碼結構，請先瀏覽main.c。
好了！現在你拿到代碼了。在根目錄下運行make，它會自動編譯，接下來運行./mac。
多謝閱讀本文！