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