IT技术网www.itjs.cn

当前位置:首页 > 编程语言 > C/C++ > 入门教程 > 告诉你如何使用 C 语言实现一个虚拟机

告诉你如何使用 C 语言实现一个虚拟机

发布时间:2015-05-13 00:00 来源:oschina

介绍

GitHub 展示了我们将会构建的东西, 你也可以在发生错误的时候拿你的代码同这个资源库进行对比. GitHub 资源库

我考虑过会写一篇有关使用C语言构建专属虚拟机的文章. 我喜欢研究“底层”的应用程序,比方说编译器、解释器以及虚拟机。我也爱谈论到它们。我也有另外一个系列的有关使用Go来编写一个解释器的文章(目前正在准备中)。我也在开发自己的编程语言 Alloy.

必要的准备工作及注意事项:

在开始之前需要做以下工作:

一个C编译器——我使用了 clang 3.4,也可以用其它支持 c99/c11 的编译器; 文本编辑器——我建议使用基于IDE的文本编辑器,我使用 Emacs; 基础编程知识——最基本的变量,流程控制,函数,数据结构等; Make 脚本——能使程序更快一点。

为什么要写个虚拟机?

有以下原因:

想深入了解计算机工作原理。本文将帮助你了解计算机底层如何工作,虚拟机提供简洁的抽象层,这不就是一个最好的学习它们原理的方法吗? 更深入了解一些编程语言是如何工作。例如,当下多种经常使用那些语言的虚拟机。包括JVM,Lua VM,FaceBook 的 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是0,在没有初始化为零的情况下它将被设置成C编译器给出的随机数。

如果我们压入(push)3个值,那么sp将编程2。所以这是一个有个3个值的数组:

sp指向这里(sp = 2)
       |
       V
[1, 5, 9]
 0  1  2 <- 数组下标

现在我们从栈上弹出(pop)一个值,我们仅需要减小栈顶指针。比如我们接下来弹出9,那么栈顶将变为5:

sp指向这里(sp = 1)
    |
    V
[1, 5]
 0  1 <- 数组下标

所以,当我们想知道栈顶内容的时候,我们只需要查看sp的当前值。OK,你可能想知道栈是如何工作的,现在我们用C语言实现它,那时相当easy。和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。换句话说,这条指令把数值从REG_A移到REG_B。同样SET REG_A VALUE,会设置REG_A内容为VALUE。

你可以从github此处check out源码。如果你想看实现了MOV和SET指令的、更“高级”的虚拟机,请check out bettervm.c文件。你可以拿自己的实现和它作比较。如果你指向大体浏览一下代码,请先check out main.c。

好了!现在你拿到代码了。在根目录下运行make,它会自动编译,接下来运行./mac。

多谢阅读本文!