如何用C語(yǔ)言實(shí)現(xiàn)一個(gè)虛擬機(jī)？
由于我喜歡在較低級(jí)別（Low-level）的應(yīng)用中（編譯器，解釋器，解析器，虛擬機(jī)等等）工作，所以我覺得寫一篇關(guān)于用C編程語(yǔ)言構(gòu)建虛擬機(jī)的文章，是非常有必要的。我認(rèn)為這篇文章除了能夠讓你了解到虛擬機(jī)的工作原理外，還可以讓你了解到較低級(jí)別的編程過(guò)程。
準(zhǔn)備內(nèi)容
- 使用的編譯器類型：我正在使用的是clang，它是輕量級(jí)編譯器，但你可以使用任何現(xiàn)代編譯器；
- 文本編輯器：我建議當(dāng)編寫C語(yǔ)言時(shí)，通過(guò)IDE編輯文本編輯器，我將使用Emacs;
- 基本的編程知識(shí)：比如什么是變量，流量控制，函數(shù)，結(jié)構(gòu)等；
- GNU Make：GNU Make主要用于自動(dòng)化構(gòu)建可執(zhí)行程序（庫(kù)文件），這樣我們就不需要在終端中一遍又一遍地編寫相同的命令來(lái)編譯代碼。Make的功能包括:自動(dòng)化構(gòu)建和安裝；增量編譯及自動(dòng)更新；適用于多語(yǔ)言，比如c/c++、java、php等；支持自定義功能擴(kuò)展（只要有意義，都是可以放到makefile中）。
為什么你應(yīng)該寫一個(gè)虛擬機(jī)？
以下是你應(yīng)該編寫虛擬機(jī)的一些原因：
1.你需要更深入地了解計(jì)算機(jī)的工作方式，本文將幫助你了解你的計(jì)算機(jī)在較低級(jí)別的環(huán)境中是如何運(yùn)行工作的？而虛擬機(jī)則提供了一個(gè)非常簡(jiǎn)單的抽象層；
2.順便了解一些虛擬機(jī)的知識(shí)；
3.深入了解一下編程語(yǔ)言的工作原理，現(xiàn)在的各種語(yǔ)言都針對(duì)虛擬機(jī)，比如JVM，Lua VM，F(xiàn)aceBook 的 Hip—Hop VM（PHP/Hack）等。
指令集
指令集會(huì)相對(duì)簡(jiǎn)單，我將簡(jiǎn)要介紹一下，例如如何從寄存器中移動(dòng)值或跳轉(zhuǎn)到其他指令。
假設(shè)我們的虛擬機(jī)有一組寄存器：A，B，C，D，E和F，且這些都是通用寄存器，這意味著它們可以用于存儲(chǔ)任何東西。這與專用寄存器不同，例如在x86上，ip, flag, ds, …程序是只讀指令集。如果虛擬機(jī)是一個(gè)基于棧的虛擬機(jī)，這意味著它有一個(gè)我們可以壓棧和彈出值的棧，另外，該虛擬機(jī)還有一些我們也可以使用的寄存器。基于棧的虛擬機(jī)比基于寄存器的虛擬機(jī)實(shí)現(xiàn)起來(lái)要簡(jiǎn)單得多。
下面是我將要實(shí)施的一個(gè)指令集的示例：
- 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
以上就是我的指令集，請(qǐng)注意，POP指令將打印我們彈出的指令，其中很多是調(diào)試用的。ADD會(huì)將結(jié)果壓棧到棧，所以我們可以從棧中的彈出值來(lái)驗(yàn)證它是否存在。我還在其中包含了一條SET指令，這樣你就可以了解如何訪問和寫入寄存器了。你也可以嘗試執(zhí)行像MOV A，B（將值A(chǔ)移至B）的指令， HLT是顯示我已經(jīng)完成程序執(zhí)行的指令。
虛擬機(jī)如何工作？
其實(shí)虛擬機(jī)比你想象的要簡(jiǎn)單，它的工作模式遵循一個(gè)簡(jiǎn)單的規(guī)律，即“指令周期（instruction cycle）”，整個(gè)過(guò)程包括讀取、解碼、執(zhí)行三大塊。首先，你要讀取指令集，然后才能解碼指令并執(zhí)行解碼后的指令。
項(xiàng)目結(jié)構(gòu)
在我開始編程之前，需要做一些準(zhǔn)備工作。我需要一個(gè)文件夾來(lái)放置項(xiàng)目，我喜歡將項(xiàng)目放置于~/Dev下。另外，我需要一個(gè)C編譯器（我使用的是 clang 3.4）。以下是我在終端中設(shè)置我的項(xiàng)目的過(guò)程，假設(shè)你已經(jīng)擁有一個(gè)?/ dev /目錄，不過(guò)你可以把它放到任何你想要的位置。
- $ cd ~/dev/
- $ mkdir mac
- $ cd mac
- $ mkdir src
上面就是我把cd放到我的~/dev目錄的過(guò)程，首先，我會(huì)創(chuàng)建一個(gè)目錄（我稱之為VM“mac”）。然后，我進(jìn)入該目錄并創(chuàng)建我的src目錄，這個(gè)目錄被用于存放代碼。
Makefile文件
我的makefile相對(duì)比較簡(jiǎn)單，由于該文件不需要將任何東西分隔成多個(gè)文件，所以其中也不會(huì)包含任何東西，我只需要用一些標(biāo)志來(lái)編譯文件即可。
- SRC_FILES = main.c
- CC_FLAGS = -Wall -Wextra -g -std=c11
- CC = clang
- all:
- ${CC} ${SRC_FILES} ${CC_FLAGS} -o mac
現(xiàn)在這應(yīng)該足夠了，你以后可以隨時(shí)改進(jìn)它，但只要它能完成這項(xiàng)工作，我們應(yīng)該沒問題。
指令編程
現(xiàn)在就可以開始編寫虛擬機(jī)的代碼了。首先，為了解釋指令編程，我必須用到一個(gè)枚舉，因?yàn)槲覀兊闹噶罨旧鲜菑?到X的數(shù)字。事實(shí)上，匯編程序?qū)@取你的匯編文件，并將所有操作轉(zhuǎn)換為對(duì)應(yīng)的數(shù)字。例如，如果你為mac編寫一個(gè)匯編程序，它將把所有MOV操作轉(zhuǎn)換為數(shù)字0。
- typedef enum {
- PSH,
- ADD,
- POP,
- SET,
- HLT
- } InstructionSet;
現(xiàn)在我可以將測(cè)試程序存儲(chǔ)為一個(gè)數(shù)組，然后寫一個(gè)簡(jiǎn)單的程序用于測(cè)試，比如將5和6相加，然后將它們用POP指令打印出來(lái)。如果你愿意，你可以定義一個(gè)指令將棧頂?shù)闹荡蛴〕鰜?lái)。
指令應(yīng)該存儲(chǔ)成一個(gè)數(shù)組，我將在文檔的頂部定義它。但你可以把它放在一個(gè)頭文件中，以下是我的測(cè)試程序。
- const int program[] = {
- PSH, 5,
- PSH, 6,
- ADD,
- POP,
- HLT
- };
上面的程序會(huì)將5和6壓棧入棧，執(zhí)行add指令，該指令將彈出棧中的兩個(gè)值，將它們加在一起并將結(jié)果壓棧回棧。然后會(huì)彈出結(jié)果，出于調(diào)試目的，我的彈出指令將打印這兩個(gè)值。
***，HLT指令意味著終止程序。如果我們要控制流程，可以隨時(shí)終止程序。不過(guò)，如果我們沒有任何指示，我們的虛擬機(jī)***也將自然終止。
現(xiàn)在我實(shí)現(xiàn)了虛擬機(jī)的讀取、解碼、執(zhí)行的過(guò)程。但是要記住，我沒有解碼任何東西，因?yàn)槲医o出的是原始指令。
獲取當(dāng)前指令
因?yàn)槲乙褜⒊绦虼鎯?chǔ)為一個(gè)數(shù)組，所以獲取當(dāng)前指令很簡(jiǎn)單。虛擬機(jī)有一個(gè)計(jì)數(shù)器，通常稱為程序計(jì)數(shù)器，不過(guò)有時(shí)也叫做指令指針等，通常它們分別縮寫為PC或IP。
現(xiàn)在，我只需在代碼頂部創(chuàng)建一個(gè)名為ip的變量，并將其設(shè)置為0。
- int ip = 0;
這個(gè)ip代表指令指針，由于我已經(jīng)將程序本身存儲(chǔ)為一個(gè)整數(shù)數(shù)組，固ip變量作為數(shù)組中的索引，表示當(dāng)前正在執(zhí)行的指令。
- int ip = 0;
- int main() {
- int instr = program[ip];
- return 0;
- }
如果打印變量instr，則PSH將顯示為0，因?yàn)樽兞縤nstr是我們枚舉里的***個(gè)值。不過(guò)，我們也可以寫一個(gè)取回函數(shù)，如下所示：
- int fetch() {
- return program[ip];
- }
該函數(shù)在被調(diào)用時(shí)將返回當(dāng)前指令。那么，如果我們想要下一條指令呢？我們只要增加指令指針即可。
- int main() {
- int x = fetch(); // PSH
- ip++; // increment instruction pointer
- int y = fetch(); // 5
- }
那么我們?cè)撊绾螌?shí)現(xiàn)自動(dòng)化呢？我們知道程序只有執(zhí)行通過(guò)HLT指令時(shí)，才會(huì)停止，所以該程序本身就是一個(gè)***循環(huán)。
- #include <stdbool.h>
- bool running = true;
- int main() {
- while (running) {
- int x = fetch();
- if (x == HLT) running = false;
- ip++;
- }
- }
我目前要做的是循環(huán)遍歷每條指令，檢查指令的值是否為HLT，如果是，則停止循環(huán)，否則就不斷重復(fù)。
一條指令的評(píng)估
這是虛擬機(jī)的運(yùn)行要點(diǎn)，其實(shí)虛擬機(jī)非常簡(jiǎn)單，你可以編寫一個(gè)巨大的switch語(yǔ)句。而這么做就是為了加快運(yùn)行速度，與之相對(duì)的是，對(duì)于所有指令和使用execute方法的某個(gè)抽象類或接口，都要使用HashMap。
switch語(yǔ)句中的每個(gè)case都是我們?cè)诿杜e中定義的指令，這個(gè)eval函數(shù)將使用一個(gè)簡(jiǎn)單的指令參數(shù)來(lái)評(píng)估指令。除非你正在使用操作數(shù)，否則不要在此函數(shù)中執(zhí)行任何指令指針增量。
- void eval(int instr) {
- switch (instr) {
- case HLT:
- running = false;
- break;
- }
- }
我會(huì)將此函數(shù)添加回虛擬機(jī)的主循環(huán)中：
- bool running = true;
- int ip = 0;
- // instruction enum
- // eval function
- // fetch function
- int main() {
- while (running) {
- eval(fetch());
- ip++; // increment the ip every iteration
- }
- }
棧
不過(guò)在添加其他指令之前，我們需要一個(gè)棧。棧是一個(gè)非常簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。我們將使用這個(gè)數(shù)組而不是一個(gè)鏈表。因?yàn)槲业臈Ｊ枪潭ù笮〉模圆槐負(fù)?dān)心大小的調(diào)整。使用數(shù)組而不是鏈接列表，在緩存效率方面會(huì)更占優(yōu)勢(shì)。
與我們?nèi)绾螕碛幸粋€(gè)用于索引程序數(shù)組的ip類似，現(xiàn)在我們需要一個(gè)棧指針（sp）來(lái)顯示我們?cè)跅?shù)組中的位置。
下面是我的一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)的詳細(xì)列表：
- [] // 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]
讓我們按照棧來(lái)分解我們的程序:：
- PSH, 5,
- PSH, 6,
- ADD,
- POP,
- HLT
首先我把5壓棧到棧上：
- [5]
然后把6壓棧到棧上：
- [5, 6]
然后add指令將彈出這些值并將它們加在一起，***將結(jié)果壓棧到棧上。
- [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
你看出來(lái)了嗎，我的棧指針在哪里起了作用？棧指針被設(shè)置為-1，這意味著它是空的。數(shù)組在C中為零索引，所以如果sp為0，它將被設(shè)置為C編譯器在其中引發(fā)的隨機(jī)數(shù)，因?yàn)閿?shù)組的內(nèi)存未被清零。
如果現(xiàn)在我壓棧3個(gè)值，則sp將為2.因此，這里是一個(gè)包含3個(gè)值的數(shù)組：
- -> 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"
現(xiàn)在我從棧上出棧一次，就需要減小棧頂指針。比如我接下來(lái)要把9出棧，那么棧頂將變?yōu)?。
- sp points here (sp = 1)
- |
- V
- [1, 5]
- 0 1 <- these are the array indices
所以，當(dāng)我想知道棧頂內(nèi)容的時(shí)候，只需要查看sp的當(dāng)前值，希望你現(xiàn)在應(yīng)該知道棧是如何工作的。
現(xiàn)在我們用C語(yǔ)言實(shí)現(xiàn)它，用C語(yǔ)言實(shí)現(xiàn)一個(gè)棧是很簡(jiǎn)單的，和ip一樣，我們也應(yīng)該定義sp變量和數(shù)組，這個(gè)數(shù)組就是棧。
- int ip = 0;
- int sp = -1;
- int stack[256];
- ...
現(xiàn)在，如果我們想將壓棧一個(gè)值，就要增加棧指針，然后在當(dāng)前sp中設(shè)置該值。
這個(gè)命令的順序是非常重要的，如果你先設(shè)置值，再增加sp，那你會(huì)得到一些不好的行為，因?yàn)槲覀冊(cè)谒饕?1處寫入了內(nèi)存。
- // sp = -1
- sp++; // sp = 0
- stack[sp] = 5; // set value at stack[0] -> 5
- // top of stack is now [5]
在我們的eval函數(shù)中，可以像以下這樣進(jìn)行壓棧。
- void eval(int instr) {
- switch (instr) {
- case HLT: {
- running = false;
- break;
- }
- case PSH: {
- sp++;
- stack[sp] = program[++ip];
- break;
- }
- }
- }
可以很明顯看到，這與以前的eval函數(shù)有一些區(qū)別。首先，我們把每個(gè)case語(yǔ)句塊放到大括號(hào)里。你可能不理解這樣做的用意，它可以讓你在每條case的作用域里定義變量。雖然現(xiàn)在不需要定義變量，但將來(lái)會(huì)用到，并且這樣做可以很容易得讓所有的case語(yǔ)句塊保持一致的風(fēng)格。
其次，是program[++ip] 表達(dá)式，該表達(dá)式是負(fù)責(zé)PSH指令所需的操作數(shù)。因?yàn)槲覀兊某绦虼鎯?chǔ)在一個(gè)數(shù)組里，PSH指令需要獲得一個(gè)操作數(shù)。操作數(shù)本質(zhì)是一個(gè)參數(shù)，就像當(dāng)你調(diào)用一個(gè)函數(shù)時(shí)，你可以給它傳遞一個(gè)參數(shù)。這種情況我們稱作壓棧數(shù)值5（PSH, 5）。我們可以通過(guò)增加指令指針ip來(lái)獲取操作數(shù)。當(dāng)ip為0時(shí)，這意味著執(zhí)行到了PSH指令，接下來(lái)我們希望取得壓棧的數(shù)值。這可以通過(guò)ip自增的方法實(shí)現(xiàn)，實(shí)現(xiàn)后，就需要跳到下一條指令否則會(huì)引發(fā)奇怪的錯(cuò)誤。當(dāng)然我們也可以把sp++簡(jiǎn)化到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指令非常簡(jiǎn)單，只需對(duì)堆棧指針進(jìn)行遞減操作即可。但是，如果你想讓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指令,是一種計(jì)算機(jī)指令,含義為兩數(shù)相加(不帶進(jìn)位)。這可能會(huì)讓你覺得有點(diǎn)棘手，而這正是case語(yǔ)句塊放到大括號(hào)里的技巧所在，因?yàn)槲覀儸F(xiàn)在要引入了一些變量了。
- 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;
- }
在具體操作之前，請(qǐng)注意，這里的某些操作的順序很重要！
- 5 / 4 != 4 / 5
棧是LIFO，全稱First in, First out，先進(jìn)先出。也就是說(shuō)，如果先進(jìn)棧5再進(jìn)棧4，就會(huì)先出棧4，然后出棧5。如果我們確實(shí)執(zhí)行了pop() / pop()，那么這將會(huì)給我們錯(cuò)誤的表達(dá)式，因此，確保順序正確是至關(guān)重要的。
寄存器
寄存器是虛擬機(jī)中的選配件，很容易實(shí)現(xiàn)。之前提到過(guò)我們可能需要六個(gè)寄存器：A，B，C，D，E和F。和實(shí)現(xiàn)指令集一樣，我們也用一個(gè)枚舉來(lái)實(shí)現(xiàn)它們。
- typedef enum {
- A, B, C, D, E, F,
- NUM_OF_REGISTERS
- } Registers;
不過(guò)這里有一個(gè)小技巧，枚舉的***會(huì)出現(xiàn)NUM_OF_REGISTERS。通過(guò)這個(gè)函數(shù)可以獲取寄存器的大小，即便你又添加了其它的寄存器，也可以獲得他們的大小。
我會(huì)將我的寄存器存儲(chǔ)在一個(gè)數(shù)組中，這是因?yàn)槲乙褂妹杜e，A = 0，B = 1，C = 2等。所以當(dāng)我想設(shè)置寄存器A時(shí)，就像說(shuō)register [A] = some_value一樣簡(jiǎn)單。
- int registers[NUM_OF_REGISTERS];
打印寄存器A中的值：
- printf("%d\n", registers[A]); // prints the value at the register A
指令指針
記住有一條分支指令的指針是要指向當(dāng)前指令的，由于現(xiàn)在是虛擬機(jī)源代碼，所以***的辦法是將指令指針作為一個(gè)寄存器，這樣你就可以從虛擬機(jī)程序中進(jìn)行讀取和各種操作。
- typedef enum {
- A, B, C, D, E, F, PC, SP,
- NUM_OF_REGISTERS
- } Registers;
現(xiàn)在我需要移植代碼來(lái)實(shí)際使用這些指令和堆棧指針，最快的方法是刪除棧頂?shù)膕p和ip變量，并用以下的定義替換它們。
- #define sp (registers[SP])
- #define ip (registers[IP])
這樣你就不必重寫很多代碼了，就能***地運(yùn)行了。不過(guò)缺點(diǎn)是，不能很好地?cái)U(kuò)展，并且它會(huì)混淆一些代碼，所以我建議不要使用這種方法，但對(duì)于一個(gè)簡(jiǎn)單的虛擬機(jī)來(lái)說(shuō)，用一下也無(wú)妨。
當(dāng)涉及到分支代碼時(shí)，我會(huì)給你一個(gè)提示。有了新的IP寄存器后，我們可以通過(guò)向這個(gè)IP寫入不同的值來(lái)進(jìn)行分支。試試下面這個(gè)例子，看看它能做什么。
- PSH 10
- SET IP 0
這類似于很多人都熟悉的基本程序:
- 10 PRINT "Hello, World"
- 20 GOTO 10
但是，由于我們不斷地進(jìn)行進(jìn)棧，所以一旦進(jìn)棧的量超過(guò)空間量，就將發(fā)生棧溢出。
請(qǐng)注意，每個(gè) ‘word’是一個(gè)指令，所以程序以下所示。
- ; these are the instructions
- PSH 10 ; 0 1
- PSH 20 ; 2 3
- SET IP 0 ; 4 5 6
如果我們想跳到第二組指令，我們將IP寄存器設(shè)置為2而不是0。
總結(jié)
閱讀完本文后，如果你在項(xiàng)目根目錄中運(yùn)行make，則可以執(zhí)行虛擬機(jī)：./mac。
你可以在這里查看github上的源代碼，如果你想用MOV和SET指令來(lái)看虛擬機(jī)的更新版本，那么檢查一下mac-improved目錄，我們?cè)诒疚闹袑?shí)現(xiàn)的虛擬機(jī)的源代碼位于mac.c中
