如何用C语言实现一个虚拟机？

由于我喜欢在较低级别（Low-level）的应用中（编译器，解释器，解析器，虚拟机等等）工作，所以我觉得写一篇关于用C编程语言构建虚拟机的文章，是非常有必要的。我认为这篇文章除了能够让你了解到虚拟机的工作原理外，还可以让你了解到较低级别的编程过程。

准备内容

· 使用的编译器类型：我正在使用的是clang，它是轻量级编译器，但你可以使用任何现代编译器；

· 文本编辑器：我建议当编写C语言时，通过IDE编辑文本编辑器，我将使用Emacs;

· 基本的编程知识：比如什么是变量，流量控制，函数，结构等；

· GNU Make：GNU Make主要用于自动化构建可执行程序（库文件），这样我们就不需要在终端中一遍又一遍地编写相同的命令来编译代码。Make的功能包括:自动化构建和安装；增量编译及自动更新；适用于多语言，比如c/c++、java、php等；支持自定义功能扩展（只要有意义，都是可以放到makefile中）。

为什么你应该写一个虚拟机？

以下是你应该编写虚拟机的一些原因：

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中