如何用 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 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

发表评论
留言与评论(共有 0 条评论)
   
验证码:

相关文章

推荐文章

'); })();