1 实现虚拟机

计算机的内部工作原理

三个基本部件需要关注：CPU、寄存器及内存

代码（汇编指令）以二进制的形式保存在内存中
CPU 从中一条条地加载指令执行
程序运行的状态保存在寄存器中

内存

内存用于存储数据，这里的数据可以是代码，也可以是其它的数据

现代操作系统在操作内存时，并不是直接处理”物理内存“，而是操作”虚拟内存“。虚拟内存可以理解为一种映射，它的作用是屏蔽了物理的细节

例如 32 位的机器中，可以使用的内存地址为 2^32 = 4G，而电脑上的实际内存可能只有 256 M

操作系统将使用的虚拟地址映射到了到实际的内存上

进程的内存会被分成几个段：

代码段（text）用于存放代码（指令）
数据段（data）用于存放初始化了的数据，如int i = 10;，就需要存放到数据段中
未初始化数据段（bss）用于存放未初始化的数据，如 int i[1000];，因为不关心其中的真正数值，所以单独存放可以节省空间，减少程序的体积
栈（stack）用于处理函数调用相关的数据，如调用帧（calling frame）或是函数的局部变量等
堆（heap）用于为程序动态分配内存

在内存中的位置类似于下图：

+------------------+
|    stack   |     |      high address
|    ...     v     |
|                  |
|                  |
|                  |
|                  |
|    ...     ^     |
|    heap    |     |
+------------------+
| bss  segment     |
+------------------+
| data segment     |
+------------------+
| text segment     |      low address
+------------------+

在本设计中：

虚拟机并不打算模拟完整的计算机，因此简单起见，只关心三个内容：代码段、数据段以及栈
其中的数据段只用来存放字符串，因为编译器并不支持初始化变量，因此也不需要未初始化数据段

当用户的程序需要分配内存时，理论上虚拟机需要维护一个堆用于内存分配，但实际实现上较为复杂且与编译无关，故引入一个指令MSET，使得能直接使用编译器（解释器）中的内存

综上，需要首先在全局添加如下代码：

int *text,                    // text segment
    *old_text,                // for dump text segment
    *stack;                   // stack
char *data;                   // data segment

注意这里的类型

虽然是int型，但理解起来应该作为无符号的整型，因为会在代码段（text）中存放如指针/内存地址的数据，它们就是无符号的
其中数据段（data）由于只存放字符串，所以是 char * 型的

接着，在main函数中加入初始化代码，真正为其分配内存：

int main(int argc, char **argv) {

  // ...

  // allocate memory for virtual machine
  if (!(text = old_text = malloc(pool_size))) {
    printf("could not malloc(%d) for text area\n", pool_size);
    return -1;
  }
  if (!(data = malloc(pool_size))) {
    printf("could not malloc(%d) for data area\n", pool_size);
    return -1;
  }
  if (!(stack = malloc(pool_size))) {
    printf("could not malloc(%d) for stack area\n", pool_size);
    return -1;
  }

  // ...

  memset(text, 0, pool_size);
  memset(data, 0, pool_size);
  memset(stack, 0, pool_size);

  // ...

  program();

  return eval();
}

寄存器

计算机中的寄存器用于存放计算机的运行状态，真正的计算机中有许多不同种类的寄存器，但本设计的虚拟机中只使用 4 个寄存器，分别如下：

PC 程序计数器，它存放的是一个内存地址，该地址中存放着下一条要执行的计算机指令
SP 指针寄存器，永远指向当前的栈顶；注意的是由于栈是位于高地址并向低地址增长的，所以入栈时 SP 的值减小
BP 基址指针，也是用于指向栈的某些位置，在调用函数时会使用到它
AX 通用寄存器，虚拟机中，它用于存放一条指令执行后的结果

要理解这些寄存器的作用，需要去理解程序运行中会有哪些状态，而这些寄存器只是用于保存这些状态的

在全局中加入如下定义：

int *pc, *bp, *sp, ax, cycle; // virtual machine registers

在 main 函数中加入初始化代码，注意的是PC在初始应指向目标代码中的main函数，但还没有写任何编译相关的代码，因此先不处理。代码如下：

int main(int argc, char **argv) {

  // ...

  bp = sp = (int *)((int)stack + pool_size);
  ax = 0;

  // ...

  program();

  return eval();
}

指令集

指令集是 CPU 能识别的命令的集合，也可以说是 CPU 能理解的语言

这里要为虚拟机构建自己的指令集，它们基于 x86 的指令集，但更为简单

首先在全局变量中加入一个枚举类型，这是要支持的全部指令：

// instructions
enum {
  LEA,
  IMM,
  JMP,
  CALL,
  JZ,
  JNZ,
  ENT,
  ADJ,
  LEV,
  LI,
  LC,
  SI,
  SC,
  PUSH,
  OR,
  XOR,
  AND,
  EQ,
  NE,
  LT,
  GT,
  LE,
  GE,
  SHL,
  SHR,
  ADD,
  SUB,
  MUL,
  DIV,
  MOD,
  OPEN,
  READ,
  CLOS,
  PRTF,
  MALC,
  MSET,
  MCMP,
  EXIT
};

这些指令的顺序带有参数的指令在前，没有参数的指令在后

这种顺序的唯一作用就是在打印调试信息时更加方便

MOV

MOV 是所有指令中最基础的一个，它用于将数据放进寄存器或内存地址，有点类似于 C 语言中的赋值语句

x86 的 MOV 指令有两个参数，分别是源地址和目标地址：MOV dest, source （Intel 风格），表示将 source 的内容放在 dest 中，它们可以是一个数、寄存器或是一个内存地址

一方面，我们的虚拟机只有一个寄存器，另一方面，识别这些参数的类型（是数据还是地址）是比较困难的，因此我们将 MOV 指令拆分成 5 个指令，这些指令只接受一个参数，如下：

IMM <num> 将 <num> 放入寄存器 ax 中
LC 将对应地址中的字符载入 ax 中，要求 ax 中存放地址
LI 将对应地址中的整数载入 ax 中，要求 ax 中存放地址
SC 将 ax 中的数据作为字符存放入地址中，要求栈顶存放地址
SI 将 ax 中的数据作为整数存放入地址中，要求栈顶存放地址

将一个指令变成了许多指令，整个系统就变得复杂了，但实际情况并非如此。首先是 x86 的 MOV 指令其实有许多变种，根据类型的不同有 MOVB, MOVW 等指令，这里的 LC/SC 和 LI/SI 就是对应字符型和整型的存取操作

但最为重要的是，通过将 MOV 指令拆分成这些指令，只有 IMM 需要有参数，且不需要判断类型，所以大大简化了实现的难度

在 eval() 函数中加入下列代码：

int eval() {
  int op, *tmp;
  while (1) {
    op = *pc++; // get next operation code

    if (op == IMM) {
      ax = *pc++;
    } // load immediate value to ax
    else if (op == LC) {
      ax = *(char *)ax;
    } // load character to ax, address in ax
    else if (op == LI) {
      ax = *(int *)ax;
    } // load integer to ax, address in ax
    else if (op == SC) {
      ax = *(char *)*sp++ = ax;
    } // save character to address, value in ax, address on stack
    else if (op == SI) {
      *(int *)*sp++ = ax;
    } // save integer to address, value in ax, address on stack

    // ... 

    } else {
      printf("unknown instruction:%d\n", op);
      return -1;
    }
  }
  return 0;
}

其中的 *sp++ 的作用是退栈，相当于 POP 操作

这里要解释的一点是，为什么 SI/SC 指令中，地址存放在栈中，而 LI/LC 中，地址存放在 ax 中？

原因是默认计算的结果是存放在 ax 中的，而地址通常是需要通过计算获得，所以执行 LI/LC 时直接从 ax 取值会更高效
另一点是 PUSH 指令只能将 ax 的值放到栈上，而不能以值作为参数

PUSH

在 x86 中，PUSH 的作用是将一个操作数推入栈中

而在虚拟机中，它的作用是将 ax 的值放入栈中，这样做的主要原因是为了简化虚拟机的实现，并且也只有一个寄存器 ax

代码如下：

int eval() {
  int op, *tmp;
  while (1) {
    op = *pc++; // get next operation code

    else if (op == PUSH) {
      *--sp = ax;
    } // push the value of ax onto the stack

    // ... 

    } else {
      printf("unknown instruction:%d\n", op);
      return -1;
    }
  }
  return 0;
}

JMP

JMP <addr> 是跳转指令，无条件地将当前的 PC 寄存器设置为指定的 <addr>

实现如下：