Programming Assignment 实验

https://github.com/GQBBBB/ics2018

[x] PA1
[x] PA2
[x] PA3
[x] PA4
[ ] PA5

PA0

搭建环境。注意:
[x] 虚拟机，双系统（包含GUI）
[ ] 云服务器（默认不包含GUI）

PA1

RTFSC

实现寄存器结构体 在这一部分,你需要在nemu/include/cpu/reg.h中正确实现寄存器才可以跑通NEMU. 手册已经给出了通用寄存器结构.

union {
    union {
    union {
        uint32_t _32;
        uint16_t _16;
        uint8_t _8[2];
    };
    uint32_t val;
    } gpr[8];
    struct { // do not change the order of the registers
      uint32_t eax, ecx, edx, ebx, esp, ebp, esi, edi;
    };
};

至于为什么这样实现,你还要参考该文件后半部分的check_reg_index, define和nemu/src/cpu/reg.c.

为什么在cmd_c()函数中, 调用cpu_exec()的时候传入了参数-1 我们可以看到nemu/src/monitor/cpu-exec.c中的void cpu_exec(uint64_t n). 在C99标准中定义了该数据类型typedef unsigned long int uint64_t;, -1可转化为无符号数2^64 - 1. 这几乎代表执行exec_wrapper()无数次. 然而exec_wrapper()函数就是执行并更新%eip的, cmd_c() 指令的的意图就在于执行所有指令.

基础设施

在nemu/src/monitor/debug/ui.c中实现各命令:

先在cmd_table中填写一下要实现的命令,格式可以模仿已存在的.

以函数的形式实现具体命令, 注意函数名以扫描内存为例:

// x N EXPR, 求出表达式EXPR的值, 将结果作为起始内存地址, 以十六进制形式输出连续的N个4字节
static int cmd_x(char *args) {
char *arg = strtok(args, " ");
if(arg == NULL){
    printf("请输入参数N！\n");
    return 0;
}
int  n = atoi(arg);
char *EXPR = strtok(NULL, " ");
if(EXPR == NULL){
    printf("请输入内存起始地址！\n");
    return 0;
}
bool success = true;
vaddr_t addr = expr(EXPR, &success);
    if (!success){
    printf("表达式出错！\n");
    return 0;
}
for(int i = 0; i < n; i++){
    uint32_t data = vaddr_read(addr + i * 4, 4);
    printf("0x%08x  ", addr + i * 4);
    for(int j = 0; j < 4; j++){
                printf("0x%02x  " , data & 0xff);
                data = data >> 8;
    }
    printf("\n");
}
printf("OK!\n");
return 0;
}

表达式求值

在nemu/src/monitor/debug/expr.c中实现表达式求值相关内容.

词法分析 -识别出每一个token
1. 在rule中编写规则(正则表达式), 识别出需要的符号, 如十进制数, 十六进制数, 加号, 减号等算数运算符和逻辑运算符.
2. 修改make_token, 此函数是用于具体识别token, 把识别出来的字符串copy到token.str里(注意末尾加'\0'), 把字符串类型放入token.type中(注意type为int类型,'+-*/'可以直接以符号(char 类型)代替, 例如空格类型为TK_NOTYPE, 需要你在enum中给它一个值,最好>256且不要重复).
递归求值 -对token数组进行分析求值.
1. check_parentheses检查左右括号是否符合规则:
  1. 维持一变量 x, 遇到左括号则加一, 遇到右括号则减一.
  2. 遍历时, 若 x < 0 则表达式括号一定不符合要求, 直接报错.
  3. 遍历时, 若 x = 0 并且遍历还没结束, 则flag = 0;
  4. 遍历结束, 若 x != 0 则表达式括号一定不符合要求, 直接报错.
  5. 遍历结束, 若 flag = 0 则返回false. 此时情况为 "(4 + 3) * (2 - 1)", 最外端没有括号包着, 会在eval中略过脱去最外层括号动作.
  6. 其他情况返回true. 此时情况为 "(4 + 3 * (2 - 1))", 会在eval中脱去最外层括号.
2. dominant_operator求主操作符:
  1. 从左到右, 检测到左括号则开始向右移动, 略过括号内token.
  2. 检测到数值(包括寄存器)则略过.
  3. 检测到运算符则检测该运算符优先级是否最大, 最大则保存为主运算符.
  4. 返回主运算符(即括号外优先级最小(数值最大)的运算符).
3. eval函数递归求值:
  1. 符合递归结束条件:
    1. 左指针>右指针: 子表达式出错.
    2. 左指针=右指针: 获取指针所指token的数值, 若该token类型为运算符, 则直接终止报错.
  2. 求出主运算符.
  3. 在主运算符两侧分别递归求解表达式.
  4. 得到最小表达式, 根据主运算符进行运算返回.

实现本节时多打Log, 有助于排错.

监视点

监视点实现可以根据讲义要求实现即可, 主要就是对链表进行操作.

PA2

RTFSC

在开始此节之前建议先行完成基础设施(2) Differential Testing更有助于调试哟~_~

这一节主要分为四个部分: opcode_table数组, 解码函数make_DopHelper, 执行函数make_EHelper和RTL指令. make_DopHelper: 主要以i386手册附录A中的操作数表示记号来命名. make_EHelper: 它们的名字是指令操作本身. 执行函数通过RTL来描述指令真正的执行功能.

我们需要执行nexus-am/tests/cputest/tests/下的程序来查看都需要完成那些指令, 有的时候HIT GOOD TRAP并不代表指令完成正确, 程序出错可能是由累积的错误导致的, 总之这一部分非常耗时.

opcode_table 根据nemu/src/cpu/decode/decode.c的函数的注释和i386手册的Appendix A -- Opcode Map，在opcode_table中进行填写。填写形式大部分如下所示, opcode_table中的项基本都是IDEXW的变体, 分为id, ex, w三部分.

#define IDEXW(id, ex, w)   {concat(decode_, id), concat(exec_, ex), w}
#define IDEX(id, ex)       IDEXW(id, ex, 0)
#define EXW(ex, w)         {NULL, concat(exec_, ex), w}
#define EX(ex)             EXW(ex, 0)
#define EMPTY              EX(inv)

程序会根据id在nemu/src/cpu/decode/decode.c中找到译码函数, 译码函数已实现, 只需要填对id即可, 这部分实现要参照decode.c文件注释和手册. ex就是执行函数的名字, 执行函数分布在nemu/src/cpu/exec/文件夹下, 需要你自己实现(使用RTL指令), 实现后记得在all-instr.h中声明一下. 这部分实现要参照手册. w指操作数宽度, 可以看到默认情况下w=0, 当 w=0 时, set_width会根据decoding.is_operand_size_16自动判断操作数是两个字节还是四个. Opcode Map中的Ev中的v就是操作数的宽度。在i386的附录A会发现v指的是word or double word，也就是2或4字节。如果传进去的width是0，那么它会判断操作数是2字节还是4字节，如果不是0，那么就直接把width设为操作数宽度。所以，遇到v，那么第三个参数应该是0，如果遇到Eb，b的意思是byte，就是1。另外, 因为需要在执行函数中使用RTL, 应该在nemu/include/cpu/rtl.h中根据提示把RTL指令先行完成.

程序, 运行时环境与AM

实现nexus-am/libs/klib/src/string.c和nexus-am/libs/klib/src/stdio.c中列出的库函数, 可以参照c库的实现.

基础设施(2)

difftest是个很有用的工具, 不过如果不调试的话尽量不要开, 它有可能会导致一些莫名其妙的错误.

一键回归测试结果如下: 无标题

输入输出

in, out 在nemu/src/cpu/exec/system.c中 in: 通过判断目的操作数的宽度来选择pioread[l|w|b]()函数把从id_src中读取的值写入id_dest中的寄存器. out: 通过判断源操作数的宽度来从id_src的寄存器中读取值然后选择piowrite[l|w|b]()函数把值写入id_src.

时钟根据nexus-am/am/amdev.h中定义的数据结构, _DEVREG_TIMER_UPTIME需要把当前时间减去启动时间, 获取时间需要使用inl(nexus-am/am/arch/x86-nemu/include/x86.h)指令和RTC_PORT(nemu/src/device/timer.c). 我们可以在timer初始化时获取一次时间, 然后在_DEVREG_TIMER_UPTIME处获取一次时间, 用他们的差值来获得启动时间.

键盘按键键盘发送该键的通码(make code); 释放一个键时键盘会发送该键的断码(break code). 通码 = 断码 | 0x8000, 通码和断码的区别在于通码第20位为一, 断码第20位为零. keydown = 1为按下按键, keydown = 0为释放按键. keycode为按键的断码, 没有按键时, keycode为_KEY_NONE. 同样用inl指令从I8042_DATA_PORT(nemu/src/device/keyboard.c)处获取通码/断码.

VGA 用inl指令从SCREEN_PORT(nemu/src/device/vga.c)处获取屏幕大小(高16位为宽, 低16位为高). 内存映射I/O需要通过is_mmio()函数判断一个物理地址是否被映射到I/O空间, 如果是则调用mmio_read()或mmio_write(), 调用时需要提供映射号(is_mmio()返回). 如果不是内存映射I/O的访问, 就访问pmem. 实现_DEVREG_VIDEO_FBCTL:

      //fb                 w
      //  +------------------------------ x
      //  |           ^ctl->x
      //  |           |
      //  |           |
      //  |ctl->y     |
      //  |<----------+------------------+
      //h |           |                  |
      //  |           |                  |
      //  |           +------------------+
      //  |
      //  y
      // 每次绘制一行，每个像素包含RGBA共四个字节 
for(int i = 0; i < ctl->h; i++)
      memcpy(fb + (ctl->y + i) * screen_width() + ctl->x, ctl->pixels + i * ctl->w, ctl->w * 4);

PA3

自陷指令 `int`

nemu 程序使用自陷指令int进行执行流的切换, 程序执行自陷指令之后, 就会陷入到操作系统预先设置好的跳转目标, 而跳转目标是通过门描述符(GateDesc)来指示的.

触发异常后后按要求在nemu中的system.c中实现int的执行函数, 它调用了intr.c中的raise_intr函数, 并传入int指令的dest操作数和当前eip. 按照以下要求完成raise_intr函数:

依次将EFLAGS, CS(代码段寄存器), EIP寄存器的值压栈
从IDTR中读出IDT的首地址,根据异常号NO(=dest)在IDT中进行索引, 找到一个门描述符(base + NO * sizeof(GateDesc))
将门描述符中的offset域组合成目标地址, 并判断P位来用确定这一个门描述符是否有效
跳转到目标地址

CTE(ConText Extension)

nexus-am 注意这两个API:

int _cte_init(_Context* (*handler)(_Event ev, _Context *ctx))用于进行CTE相关的初始化操作. 其中它还接受一个来自操作系统的事件处理回调函数的指针, 当发生事件时, CTE将会把事件和相关的上下文作为参数, 来调用这个回调函数, 交由操作系统进行后续处理. 它具体会做两件事:
- 初始化IDT
- 注册一个事件处理回调函数, 这个回调函数由Nanos-lite提供
void _yield()用于进行自陷操作, 会触发一个编号为_EVENT_YIELD事件. 在x86-nemu中, 我们约定自陷操作通过int $0x81触发.

保存上下文

nexus-am 成功跳转到自陷入口函数vectrap()(trap.S)之后, 需要用pusha指令把通用寄存器的值压栈. vectrap()会压入错误码和异常号#irq, 然后跳转到asm_trap(). 这些内容连同之前保存的错误码, #irq, 以及硬件保存的EFLAGS, CS, EIP, 形成了完整的上下文. 接下来代码将会把当前的%esp压栈, 并调用irq_handle()函数(cte.c).

irq_handle()会把执行流切换的原因打包成编号为_EVENT_xxx的事件 case 0x81: ev.event = _EVENT_YIELD; break;, 然后调用在_cte_init()(目前只有vertrap, 其他的还需要自己添加)idt[0x81] = GATE(STS_TG32, KSEL(SEG_KCODE), vectrap, DPL_KERN);中注册的事件处理回调函数, 将事件交给Nanos-lite来处理. 在Nanos-lite中, 这一回调函数是nanos-lite/src/irq.c中的do_event()函数case _EVENT_YIELD: Log("receive _EVENT_YIELD event"); break;.

系统调用

用户程序通过自陷指令int $0x80指令触发系统调用.

navy-apps/libs/libos/src/nanos.c中系统调用接口syscall(), 其中的内联汇编会先把系统调用的参数依次放入%eax, %ebx, %ecx, %edx四个寄存器中, 然后执行自陷指令int $0x80. x86-nemu的CTE会将这个自陷操作打包成一个系统调用事件_EVENT_SYSCALL, 并交由Nanos-lite继续处理. Nanos-lite收到系统调用事件之后, 就会调出系统调用处理函数do_syscall()(syscall.c)进行处理. do_syscall()首先通过宏GPR1从上下文c中获取用户进程之前设置好的系统调用参数, 通过第一个参数系统调用号进行分发.

void sys_yield(_Context *c) {
  _yield();
  c->GPR1 = 0;
}

void sys_exit(_Context *c) {
  _halt(0);
  c->GPR1 = 0;
}

_Context* do_syscall(_Context *c) {
  uintptr_t a[4];
  a[0] = c->GPR1; // 系统调用号
  switch (a[0]) {
      case SYS_yield: sys_yield(c); break; // 1
      case SYS_exit: sys_exit(c); break; // 0
      default: panic("Unhandled syscall ID = %d", a[0]);
  }

  return NULL;
}

经过CTE, 执行流会从do_syscall()一路返回到用户程序的上述内联汇编中. 内联汇编最后从%eax寄存器中取出系统调用的返回值, 并返回给_syscall()的调用者, 告知其系统调用执行的情况.

GPR?宏有5个,其中GPR1一定是对应%eax, 按照上文所述的依次放入,对应关系如下:

#define GPR1 eax
#define GPR2 ebx
#define GPR3 ecx
#define GPR4 edx
#define GPRx eip

PS. 到此完成所有步骤后一直出现如下错误:

# diff_test
qemu eax:0x00000001, nemu eax:0x00000001
qemu ecx:0x00000000, nemu ecx:0x00000000
qemu edx:0x00000000, nemu edx:0x00000000
qemu ebx:0x00000000, nemu ebx:0x00000000
qemu esp:0x00007b30, nemu esp:0x00007b34
qemu ebp:0x00007b48, nemu ebp:0x00007b48
qemu esi:0x0347ae1f, nemu esi:0x0347ae1f
qemu edi:0x33ce1790, nemu edi:0x33ce1790
qemu eip:0x00100e8b, nemu eip:0x00100e73

nemu: ABORT at eip = 0x00100e73

查看0x00100e73处指令为:

00100e71 <vecsys>:
    100e71: 6a 00                   push   $0x0
    100e73: 68 80 00 00 00          push   $0x80
    100e78: eb 15                   jmp    100e8f <asm_trap>

非常纳闷, 竟然在trap.S中出错了, 简直没道理. 发现qemu和nemu的eip不同, 并且push指令明明早已经实现了. 后来把diff_test关掉以后果然HIT GOOD TRAP了......

总结一下自陷指令int的流程:

最开始位于nemu
程序陷入自陷指令后(system.c中的make_EHelper(int))调用raise_intr()函数, 传入int的dest操作数和当前eip
在raise_intr中将eflags, cs寄存器和eip压栈. 并索引中断描述符表IDT,使用dest和idtr寄存器的base地址找到对应门描述符. 取出门描述符中地址并跳跃
接下来是nexus-am
成功跳转到自陷入口函数(trap.S中)之后, 压入通用寄存器的值,错误码和异常号#irq, 然后跳转到asm_trap(). 这些内容连同之前保存的错误码, #irq, 以及硬件保存的EFLAGS, CS, EIP, 形成了完整的上下文. 接下来代码将会把当前的%esp压栈, 并调用irq_handle()函数(cte.c)
irq_handle()的代码会根据irq把执行流切换的原因打包成事件, 然后调用在_cte_init()中注册的事件处理回调函数, 将事件交给Nanos-lite来处理
接下来是nanos-lite
do_event()函数(irq.c)要根据事件ID对事件进行分发, 可以调用do_syscall()(位于syscall.c)在其中执行不同系统调用
over

标准输出

按照说明实现sys_write即可, 需要注意的是要在navy-apps/libs/libos/src/nanos.c的_write()中调用系统调用接口函数.

堆区管理

根据讲义使SYS_brk系统调用总是返回0即可, 表示堆区大小的调整总是成功. _sbrk()则通过以下步骤编写:

获取当前program break位置(end)
根据当前program break位置和参数increment, 计算出新program break
通过SYS_brk系统调用来让操作系统设置新program break(总是成功,返回0)
更新之前记录的program break的位置, 并将旧program break的位置作为_sbrk()的返回值返回. 若该系统调用失败, _sbrk()会返回-1

当没有实现SYS_brk和_sbrk()时, 运行hello程序, 除了第一条使用write输出的Hello World可以完整输出外, 其余使用printf的输出均只输出首字母H. 实现堆区管理后printf函数可以完整输出语句了.

文件系统

实现open, close, read, write, lseek等系统调用, 流程和上面差不多. 需要注意的是write系统调用, 由于在上面实现I/O时简单的实现了一下write(直接由_putc()输出),所以现在需要对它进行改造:

void sys_write(_Context *c) {
  int fd = c->GPR2; 
  void *buf = (void *) c->GPR3;
  size_t len = c->GPR4; 
  c->GPR1 = fs_write(fd, buf, len);
}

size_t fs_write(int fd, const void *buf, size_t len){
  Finfo *file = &file_table[fd];

  // 针对stdout和stderr
  if (fd == 1 || fd == 2){
    // file->write 调用_put()输出buf中内容
    size_t std_len = file->write(buf, file->open_offset, len);
    file->open_offset += std_len;
    return std_len;
  }

  if (file->open_offset + len > file->size)
    len = file->size - file->open_offset;  

  size_t return_len = ramdisk_write(buf, file->disk_offset + file->open_offset, len);
  file->open_offset += return_len;

  return return_len;
}

在做到后面时发现这一段话

不过在Nanos-lite中, 由于特殊文件的数量很少, 我们约定, 当上述的函数指针为NULL时, 表示相应文件是一个普通文件, 通过ramdisk的API来进行文件的读写, 这样我们就不需要为大多数的普通文件显式指定ramdisk的读写函数了.

因此我们可以把上述fs_write代码中的if (fd == 1 || fd == 2)替换为if (fd->write).

当你在VFS中只完成/dev/fb和/proc/dispinfo时, 让Nanos-lite加载/bin/bmptest, 并不能输出看到屏幕上显示ProjectN的Logo:

[src/fs.c,53,fs_open] open /dev/events fail!
[src/fs.c,54,fs_open] system panic: Assertion failed: 0
nemu: HIT BAD TRAP at eip = 0x00100032

还要继续往下完成/bin/events:

size_t events_read(void *buf, size_t offset, size_t len) {
  // read_key()是nexus-am/libs/klib/src/io.c中的方法,返回keycode(因为keyname数组最大为256,所以只用到了第0~8位)和keydown(在第15位)
  int key = read_key();
  int return_len = 0;

  if ((key & 0x1ff) == _KEY_NONE) {
    return_len = sprintf(buf, "t %d\n", uptime());
  } else {
    // 判断是否keydown
    if (key & 0x8000){
      return_len = sprintf(buf, "kd %s\n", keyname[key & 0x1ff]);
    } else {
      return_len = sprintf(buf, "ku %s\n", keyname[key & 0x1ff]);
    }
  }

  return return_len;
}

仙剑运行成功，肉眼可见的刷新，那一群鸭子从右边飞到左边飞了十几分钟 : ) “仙剑奇侠传”这个界面可能要停留几十分钟才能继续加载，开始新故事后（也就是李逍遥和李大娘的那个场景）会直接退出，目测是触发了SYS_exit系统调用。

PA4

多道程序

当一个程序触发系统调用时, 陷入到内核. 根据asm_trap()的代码, A的上下文结构(_Context)将会被保存到A的栈上. 本来系统调用处理完毕之后, asm_trap()会根据栈上保存的上下文结构来恢复A的上下文

我们要做的就是恢复该进程上下文之前, 把栈顶指针切到另一个进程栈上,指向另一个进程的上下文结构从而偷梁换柱.

我们需要根据一个叫进程控制块(PCB)的结构(确切的说是其中的_Context *cp)来保存上下文的位置, 从而能找到其他程序上下文.

创建上下文 根据讲义图示设置cp指针, 设置eip为要执行的函数entry, 设置cs为0x8即可.

进程调度 在nanos-lite/src/proc.c中完成调度函数schedule(), 在nanos-lite/src/irq.c中收到_EVENT_YIELD事件后, 调用schedule()并返回其现场. 在nexus-am/am/arch/x86-nemu/src/trap.S中的asm_trap()添加movl %eax, %esp, 先将栈顶指针切换到新进程的上下文结构, 然后才恢复上下文, 从而完成上下文切换的本质操作.

创建用户进程上下文 与_kcontext()相比, 除了在栈上创建必要的上下文信息之外, _ucontext()还需要在栈上准备一个栈帧, 用于存放main()函数的参数信息(设置为0或NULL). 这个栈帧将来会被navy-apps/libs/libc/src/platform/crt0.c中的_start()函数使用.

超越容量的界限

在分页机制上运行Nanos-lite 在这里我们需要在vaddr_read()和vaddr_write()中检测CR0的PG是否为1来确认是否需要经过分页地址转换. 需要分页地址转换的调用page_translate()函数进行转换. 该页表为二级页表, 我们需要先从CR3中获取页目录表基地址, 加上偏移位后获得页表基地址所在页目录项, 页表基地址再加上偏移位之后获得对应页表项, 读取页表项的值加上偏移地址可以得到物理地址.

在分页机制上运行用户进程 在context_uload()(nanos-lite/src/loader.c)的开头调用_protect(), 并且把pcb->as的地址传给它.

在nexus-am/am/arch/x86-nemu/src/vme.c中实现_map()函数:

通过p->ptr获得页目录基地址.
根据页目录基地址获取va对应页目录项.
判断页目录项对应物理页是否可用, 若不可用则申请新的物理页并更新该页目录项.
根据页目录项获取va对应页表项
判断页表项对应物理页是否可用, 若不可用则申请新的物理页并更新该页表项.

修改loader()实现: 计算要加载程序有多少页, 然后对于每一页, 申请一页物理页, 建立虚拟地址到物理地址的映射, 最后再把文件内容拷贝至物理页. 记得在加载所有内容至物理页后(for或while循环结束后),更新pcb的cur_brk 和max_brk 为文件末尾地址. 否则未来运行app时会出现以下错误:

nemu: src/memory/memory.c:73: page_translate: Assertion `paddr_read(pg + sizeof(paddr_t) * PTX(vaddr), sizeof(paddr_t)) & PTE_P' failed.

实现nanos-lite/src/mm.c中的mm_brk()函数, 该函数作用就是通过一个循环将从current->max_brk到new_brk为止的部分，以页为单位分别申请一页空闲页并建立映射.

还有一些其他改动按照讲义要求实现即可.

时钟中断

抢占多任务 大部分没什么要说的, 在修改_ucontext()的代码构造上下文的时候, 把eflags寄存器的IF位设置为开中断(1)以保证上下文恢复后能正常响应中断即可.

最后

稍微修改一下events_read(), init_proc()和schedule()函数以支持使用F1, F2, F3切换三个pal.

PA实验必做部分到此结束~

GQBBBB / GQBBBB.github.io

PA实验（ICS2018 NJU） #6

Programming Assignment 实验

[ ] PA5

PA0

PA1

RTFSC

基础设施

表达式求值

监视点

PA2

RTFSC

程序, 运行时环境与AM

基础设施(2)

输入输出

PA3

自陷指令 `int`

CTE(ConText Extension)

保存上下文

系统调用

标准输出

堆区管理

文件系统

PA4

多道程序

超越容量的界限

时钟中断

最后

GQBBBB / GQBBBB.github.io

PA实验（ICS2018 NJU） #6

Programming Assignment 实验

[ ] PA5

PA0

PA1

RTFSC

基础设施

表达式求值

监视点

PA2

RTFSC

程序, 运行时环境与AM

基础设施(2)

输入输出

PA3

自陷指令 int

CTE(ConText Extension)

保存上下文

系统调用

标准输出

堆区管理

文件系统

PA4

多道程序

超越容量的界限

时钟中断

最后

自陷指令 `int`