pa2-1 指令解码与执行

前言

经历了基本没有学习的十一假期后，pa2-1 来了，它的说明文档有 30 多页，老师的 PPT 课件有 100 多页……足以见得这次的实验都多重要。 经过了 pa2-1 的磨炼，我已经充分认识到这门课的强大，老师提供给你的一个完整的模拟计算机的代码框架，你要做的只是给这身躯体变得有血有肉，但能够完成任务的前提是：你差不得懂得整个代码框架的运作机制，或者是每一个实现部分的框架运行机制，在此基础上，你才能少犯错，少出 bug。

必备材料

• NJUics 2019 PA 实验手册
• Intel 的 i386 手册
• i386 手册的勘误表
• pa 整个工程代码

原理说明

pa2-1 要实现==所有==汇编指令的翻译和实现，也就是说，给你一行十六进制的汇编操作指令，你需要根据它的 opcode 判断出这是 i386 手册中的哪一个汇编指令，并且你要用 c 语言实现这个操作。

比如下面这行指令：

8b 94 83 00 11 00 00 8b 45 f4

• 读取 8b，这就是 opcode。
• 去 i386 手册查一查，这个 0x8b 对应的汇编操作是 MOV Gv,Ev。
• 根据 i386 的规则能够知道意思是把 Ev 这个源操作数 MOV 到 Gv 这个目的操作数里。
• 自己用 C 语言编写一个 mov_E2G 的函数。
• Gv、Ev 具体是什么呢？这就要去看 0x8b 后面的 94、83、00……了

总之就是，读取一个 opcode 之后，根据这个 opcode 对应的汇编指令，去它后面读取相应长度的数，获取源操作数、目的操作数的具体信息，然后实现这个操作。

最终目标是：实现==所有==汇编指令，大概至多 256 个。

开始

函数命名规则：

• i：立即数
• r：寄存器地址
• rm：寄存器地址或内存地址
• m：内存地址
• b：8 位
• w：16 位
• l：32 位
• v：16 或 32 位
• bv：源操作数 8 位，目的操作数 16 或 32 位

第一个 mov 函数

//把一个i（立即数）传给一个r（寄存器），b表示i和r都是8位。
int mov_i2r_b(uint32_t eip, uint8_t opcode)
{
        OPERAND imm, r;// 创建源操作数和目的操作数局部变量
      //OPERAND是一个结构体，里面有val、type、addr、data_size成员，可以进行读、写操作

        imm.type = OPR_IMM; // 配置源操作数类型
      imm.addr = eip + 1; // 配置源操作数地址
      imm.data_size = 8;// 配置源操作数长度

        r.data_size = 8;// 配置目的操作数类型
        r.type = OPR_REG; // 配置目的操作数类型
      r.addr = opcode & 0x7;// 配置目的操作数类型

        operand_read(&imm); // 读源操作数的值
      r.val = imm.val; // 将源操作数的值赋给目的操作数
      operand_write(&r);// 写入目的操作数，完成 mov 动作

        return 2;    // 返回指令长度
}

这是我们写的第一个函数的例子。

思路就是，获取源操作数、目的操作数的信息（是寄存器就获取它的名字，是内存地址就获取它的地址，是立即数就获取它的值），然后通过不断地读、写内存地址的方式实现这个函数。

以后的每一个函数都要这样（至少最终是这样。下面讲如何偷懒）

简化

由于这 256 个指令中有大量的指令是==具有相同功能但操作数类型不同==的函数，

比如：

mov_i2r_b();
mov_i2r_w();
mov_i2r_v();
mov_i2r_bv();

mov_rm2r_b();
mov_rm2r_w();
mov_rm2r_v();
mov_rm2r_bv();

mov_r2rm_b();
mov_r2rm_w();
mov_r2rm_v();
mov_r2rm_bv();

这些指令只是源操作数、目的操作数不同，功能相同，最终的代码一定是极度相似的，所以老师给我们提供了==宏定义展开==的偷懒方法，实际上就是把重复的没必要多次写的部分代码用宏定义的方式提前写好，最终只需要完成最后的“功能”即可，不用再考虑怎么获取源操作数、目的操作数的信息了。

方法很强，具体实现有点麻烦，不讨论了。

总之，只需要写下面的代码可以了：

static void instr_execute_2op()
{
        operand_read(&opr_src);
        opr_dest.val = opr_src.val;
        operand_write(&opr_dest);
}

结束

这一节就是很麻烦，但不难。

绝大多数指令都能够用老师的偷懒宏定义的方式解决，写一个函数体，相当于写出七八个函数了。

有个别的汇编指令无法用这种方式，比如 push、pop、ret、call。

这四个指令是最容易出 bug 的，来来回回改了好几处 bug，一定要好好看 i386 手册上面每一个指令的伪代码。

还有还有，i386 上关于 jcc 的部分内容有错误，老师给了勘误手册。

写这篇文章的时候已经是 pa2-3 结束的时候，2-1 的好多内容都记不太清楚了……不多说了。

pa2-2

前言

这一节实验只需要两步。

• 修改 Makefile 文件中的一行，把程序执行时指令存放的实际地址从 30000 改为 100000。
• 补充完成程序的装载过程（只需添加两行代码）

原理

pa 实验中的一个程序的可执行文件（ELF 文件），它的存储空间是从 0x0 到 MAX_SIZE。

从 0x0 到 0x30000 是 testcase 的 ELF File 数据，从 0x30000 开始之后是 kernel 模拟的装载指令的部分，从 0x100000 开始之后是 pa2-2 编写的装载 load 函数生成的数据存放的位置。

也就是说，从 0x30000 开始运行程序，用的是系统的 load 函数；换到 0x100000 后，用的是我们自己编写的 load 函数。

load 函数的作用

读取并分析 ELF 文件，根据 ELF 文件的内容运行程序。

具体是：

读入位于 ELF 文件最开始位置(偏移量为 0)处的 ELF 头，并根据其中的值 e_phoff 定位程序头表在 ELF 文件中的位置。

顺序扫描程序头表中的每一个表项，遇到需要装载的表项时，根据表项描述的内容将相应的数据拷贝 到内存相应位置。

pa2-3 完善调试器(选)

前言

整个 pa 项目的 nemu 有一个控制器 monitor，平时测试程序都在用它，它有一些指令：

• si：单步执行
• ni：单步执行（这两个区别是一个进入函数，另一个直接跳下一步）
• info r：显示所有寄存器+eip 里面存的值
• p：计算一个表达式
• ……

总之和 gdb 有点类似，只不过这个调试器是编写框架的人自己写的简易版。

pa2-3 的目的就是为了给这个 monitor 增加 p 指令的功能。

即实现==计算表达式==的功能。

##原理

随便一个表达式：

-0xc0100000 && 5 +  ($eax +5)*4 - *(  $ebp +8)+ number +main

这个表达式里面出现了以下类型的字符串：

• 十六进制数
• 不限制长度的空格
• 逻辑运算符号：&& || != ==
• +-*/
• 十进制数字 number
• 左右括号()
• 符号 main（函数名、变量名）

还有一点，这里面开头的“-”并不是减号，而是负号，第二个*也不是乘号，而是指针解引用的标志。

如何求出这个表达式的值呢？

词法分析-正则表达式

首先，用正则表达式去匹配不同类型的字符串，它们之前有优先级，匹配完成后存储在一个 tokens 数组里面，每一个 token 有一个 type 变量和一个 str 变量。

比如说 4+7*(3-1)，它的词法分析结果就是：

数字、4；
加号、略；
数字、7；
乘号、略；
左括号、略；
数字、3；
减号、略；
数字、1；
右括号、略。

略的意思是 type 的类型已经可以确定这是什么数据了，没必要再存一个 str 了。

匹配完成之后，我们要考虑乘号、减号的特殊用法：指针解引用、负号。

你会发现，当乘号、减号意指乘法、减法时，它前面只能是数字、十六进制数、寄存器、符号。

由此可以遍历一遍 token 表，把乘号、减号的特殊含义找出来。

递归的方法求解表达式

之前学过的处理表达式的思路是，把中缀表达式改为后缀，然后按顺序用栈去计算。

这里老师给了一种新的思路。

solve(expr)
{
        //把expr拆解成expr1、op、expr2
        val1=solve(expr1);
        val2=solve(expr2);
        return val1 op val2；
}
//比如
solve(6+(9-5)+7*8)
  =solve(6+(9-5))+solve(7*8)
    =solve(6)+solve((9-5))+solve(7*8)
  =……;

大概的代码如下：

eval(p, q)
{
      if(p > q)
    {
                /* Bad expression */
    }
        else if(p == q)
    {//p==q，说明这个字符串只剩下一个token了，根据它的类型很好处理。
      //数字就返回它的数值，寄存器就返回寄存器的值，符号名就去找到ELF文件里面对应的符号地址
                /* Single token.
                * For now this token should be a number.
                * Return the value of the number.
                */
        }
        else if(check_parentheses(p, q) == true)
    {//如何字符串被括号包围，那么扔掉括号
                /* The expression is surrounded by a matched pair of parentheses.
                * If that is the case, just throw away the parentheses.
                */
                return eval(p + 1, q - 1);
    }
        else
    {//基本操作，遍历一遍token，找到符合要求的那个op，然后两边裂开，递归求值
                op = the position of dominant operator in the token expression;
          val1 = eval(p, op - 1);
                val2 = eval(op + 1, q);
                switch(op_type)
        {
                case '+': return val1 + val2; case '-': /* ... */
                case '*': /* ... */
                case '/': /* ... */
                default: assert(0);
        }
        }
}

重点是这个字符串中哪一个符号才是我们要找的 op？

op 有几个要求：

• op 一定不在括号里面
• op 的运算符优先级最低
• 如果多个运算符优先级相同，取最右侧的为 op
• 如果开头是负号、指针解引用，那么它就是 op

之后要做的，就是不断往上加操作了，从加减乘除开始，加入指针解引用，加入逻辑运算符，到最后加入负号名。

最后

pa2-1 写了大量的指令，真真正正的让你理解每一条汇编指令的具体功能。

pa2-2 步骤很少，为了让你理解程序的装载过程。

pa2-3 督促你学习正则表达式，同时讲了一种求表达式结果的递归方法。

到这里，几乎可以说明白了 pa 实验的目的。

从整体看，有一台完好的操作系统，pa 不断地拆下一块，拼上自己制作的那一块，一步步地朝着完全自主制造发展。

从细节看，每一个步骤都被老师简化了，实际要写的代码并不多，只是为了让你真正理解每一个过程。

这门实验是计算机系统基础的配套实验，理论课上听的迷迷糊糊，做完实验才仿佛有醍醐灌顶的感觉。