Implementing a virtual machine in C(虚拟机C语言实现)

页面导航:首页 > 软件编程 > C 语言 > Implementing a virtual machine in C(虚拟机C语言实现)

Implementing a virtual machine in C(虚拟机C语言实现)

来源: 作者: 时间:2016-01-25 09:50 【

介绍Github上展示了我们将要做的东西,你可以对比项目中的代码以防你遇到任何错误GitHub Repository 这是一篇关于使用C语言建造你自己的虚拟机的文章。我喜欢研究底层应用,例如编译器

介绍

Github上展示了我们将要做的东西,你可以对比项目中的代码以防你遇到任何错误
这是一篇关于使用C语言建造你自己的虚拟机的文章。我喜欢研究底层应用,例如编译器,解释器,编辑器,虚拟机等。

预备知识和提醒

在我们继续之前,有一些东西是你必须知道的:

一个编译器 — 我在使用clang3.4,但是你可以使用支持c99/c11的任何编译器 编辑器 — 我会建议你使用文本编辑器而不是IDE,我会使用Emacs 基本的编程知识 — 只是基本,例如变量,控制符,函数,结构体等 Make — 一个编译体系,让我们不必在控制台写重复的命令去编译我们的代码

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

1
这里有一些你应该写一个虚拟机的原因:

你希望对计算机的工作有更加深入的理解。这篇文章会帮助你去了解你的电脑是怎么在底层工作的,一个虚拟机提供了一个简单而优美的抽象。并且写一个虚拟机是你学习它的最好方式,不是吗? 你因为觉得它有趣而去学习一个虚拟机 你希望了解一些编程语言的工作方式。当今不同的语言有自己的虚拟机。例如JVM,Lua’s VM, Facebook’s Hip-Hop VM (PHP/Hack)等等。这些都是很大的概念,假设从C++程序转换到汇编给机器执行,当你思考它们的时候,你会理所当然地使用OOP编程方式,自动垃圾回收等所有的特性。

指令集

我们会实现自己的指令集,它非常的简单。
我将简单提及一些指令,例如从寄存器中移动值,或者跳转到其他指令,但是希望你在度过这篇文章以后弄清楚它们。

我们的虚拟机会有一系列的寄存器A,B, C, D, E, 和 F。这些都是目的寄存器,你可以使用来存储任何东西。一个程序是一个只读的指令序列。这是一个基于栈的虚拟机,也就是说我们拥有一个栈来进行进栈和出栈的操作,另外还有少量的寄存器供我们使用。基于栈的虚拟机比基于寄存器的虚拟机更加容易实现。

不再多说,这里是我们将会用到的指令集。分号后是对每一行作用的说明。

PSH 5 ; 将5进栈
PSH 10 ; 将10进栈
ADD ; 将栈顶的两个值相加,然后将结果进栈
POP ; 将栈顶元素出栈,将会用于调试
SET A 0 ; 将寄存器A置零
HLT ; 停止程序

这就是我们的指令集,注意POP指令会打印出栈的值,这样更加便于调试(ADD指令会将结果入栈,所以我们使用POP来判断是否操作正确)
你也可以自己尝试实现类似MOV A,B。HLT指令表示我们的程序结束。

怎么使虚拟机工作?

虚拟机比你想的要简单,它们遵循一个简单的模式:取指令,解析,执行。一些先进的虚拟机可能会有另外的步骤,但是核心就是这些。我们从代码或指令集做取得下一条指令,然后去解析指令和执行解析后的指令。为了简单起见,我们不会去解析指令,典型的虚拟机会打包一个指令到一个值,然后去解析它。

项目结构

在我们开始编程之前,我们虚拟创建工程。首先,你需要一个C编辑器。我们需要一个文件夹来放置你的工程,我喜欢将工程放置在~/Dev下。我们在目标文件夹中创建工程。这里假设你已经有了~/Dev/目录,但是你也可以在任何地方创建你工程。

$cd ~/Dev/
mkdir mac  
cd mac  
mkdir src 

在目标文件夹中,我们创建一个文件夹(称为VM”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等指令转换成.\。例如,我们可以用0,5来代替PSH,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指令,将两者出栈,然后将相加的结果入栈。我们会将结果出栈然后打印它,但是你不需要自己去做这个事情。我们只是用它来测试。最后,HLT指令被调用表示程序结束。

现在我们有程序了。所以现在我们实现取值,解析,求值的虚拟机操作。但是记住,我们不解析任何东西,因为这里只是原始指令。这意味着我们只需要关心取值,和求值。我们简化出两个函数fetch和evaluate

取出当前指令

因为我们将程序存储到数组中了,取出指令就变得很简单。虚拟机有一个计数器,通常称为程序计算器,指令指针…这些名字都是一个意思,取决于你个人喜好。我将这些缩写成IP或PC,因为他们在VM代码中非常常见。

如果你还记得,我说过我们会将程序计数器当成一个寄存器..我们会这样做,但是还要等一下。现在,我们只是在程序的开头,创建一个变量,叫ip,将其值设置为0。

int ip = 0;

ip表示指令指针。因为我们将程序存储成数组,我们使用ip变量去指向当前的index。例如,如果我们创建了一个变量x,值为为ip指向的程序,它会存储我们程序的第一条指令(加上ip值为0)

int ip = 0;

int main() {  
    int instr = program[ip];
    return 0;
}

我们打印变量instr,它会给我们PSH,也就是0,因为这是我们enum的第一个值。我们可以将这个过程写出一个函数

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,如果是停止循环,否则执行指令,并继续。

执行指令

这里我们的目的是真正地执行指令,并且让它看起来更加清晰。由于这个虚拟机很简单,我们可以利用enum写一个巨大的switch结构。eval有一个参数,表示要执行的指令。我们不会增加指令指针,除非我们消耗掉操作数。

void eval(int instr) {  
    switch (instr) {
        case HLT:
            running = false;
            break;
    }
}

回到main函数,我们可以将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。它指向我们的栈数组的当前index。

为了更加形象,这是我们的栈(数组)

[] // 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]

然后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

所以我们栈指针在哪里呢?栈指针,或者说sp一般默认为-1,表示栈为空。数组从0开始,所以如果sp表示是0,那么C编译器会造成混乱。

现在如果我们将3个数入栈,sp会是2。

sp points here (sp = 2)
|
V
[1, 5, 9]
0 1 2 <- these are the array indices

当我们想看栈顶元素,我们只是看到sp指向的值。所以现在你应该明白栈是怎么工作的了。C语言实现也很简单。除了ip变量,我们还定义了一个sp变量,其默认值是-1!现在stack只是一个数组,我们有如下定义:

int ip = 0;  
int sp = -1;  
int stack[256]; // use a define or something here preferably

// other c code here...

现在如果我们想将元素入栈,我们自增栈指针,然后将值设置到sp指向的位置。注意,顺序非常重要!

// pushing 5

// sp = -1
sp++; // sp = 0  
stack[sp] = 5; // top of stack is now [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为零,这意味着它指向PSH,但是现在我们在PSH的指令,我们想获得下一个指示。要做到这一点就要增加指令。注意增量的位置是很重要的,我们得到的指令之前,我们要增加指令指针否则我们只会得到PSH,然后就跳过下一个指令造成一些奇怪的错误。我可以将sp++简写为stack[++sp]。

现在说POP指令,它很简单。我们只需要自减栈指针,但是我也想打印出我们出栈的那个值。我省略了其他的代码指令和switch语句,这里只包括POP指令的case部分:

// REMEMBER TO INCLUDE !

case POP: {  
    int val_popped = stack[sp--];
    printf("popped %d\n", val_popped);
    break;
}

所以我们所做的就是我们栈顶值保存到val_popped中,然后我们将栈指针自减。如果我们先将栈指针自减,你会得到一些垃圾值,因为sp可以是0,那么我们将栈指针自减并设置val_popped到stack[-1]基本上,这并不妙。

最后是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;
}

寄存器

对于虚拟机,寄存器是可选的。寄存器很容易实现,我们提到我们有寄存器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]; 

我们可以这样来使用寄存器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;

现在我们可以实际使用这些指令和堆栈指针。一个快捷的方法,是进行宏定义

#define sp (registers[SP])
#define ip (registers[IP])

应该是一个不错的解决方法,这样你不需要重写代码,并且保证功能正常。然而,这可能不便于扩展,可能会导致代码混淆,所以我建议不使用这种方法,但对于一个简单的玩具虚拟机它足够了。

当涉及到我们的代码中的分支,我给你一个提示。利用我们新的IP寄存器,我们可以给这个IP写入不同的值。试试下面这个示例,看它做什么:

PSH 10
SET IP 0

和人们熟悉的BASIC程序相似

10 PRINT “Hello, World”
20 GOTO 10

然而,因为我总是要将值入栈,所以最终会造成栈溢出。在你的VM中,这也是一个需要处理的边界情况。

; these are the instructions
PSH 10 ; 0 1
PSH 20 ; 2 3
SET IP 0 ; 4 5 6

如果你想调到第二条SET指令,我们会将IP寄存器设置为2而不是0。

最后

你可以在获得代码。如果你想要看到包含MOV,SET指令的版本,你可以bettervm.c。如果你遇到问题,你也可以将你的实现和上面的文件对比。如果你想要教程代码,你可以下载main.c。

你可以在项目文件夹下执行make命令,如果正确编译,你可以执行./mac文件。

如果你对这个话题感兴趣并且向扩展,网上有很多的资源。Notch写了DCPU-16,一个16位的。Github上也有很多的实现,你可以模仿它们。如果你写了一个类似的模拟器,检查它的语法规则,看看你是否能够执行指令和设置寄存器。

谢谢。

Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<