PA_record.log

| 0 | 总字数 4.8k | 期望阅读时间 18 min
  1. 1. PA1
  2. 2. PA2
  3. 3. PA3

从指令集实现到操作系统
nju-ics-pa 工程记录

那就让我来认真对待这个质量高的夸张的PA。NJU牛逼!

我就是精神南大人(不)

PA1

调用顺序:

main.c 调用 init_monitor()

  • parse-args 中的 getopt_long 函数的文档查看通过 man 3 getopt 进行。这个在 Arch 下有坑。(会显示 locale 未定义)只需要 RTFM(archwiki) 安装 man-pages 等两个包即可。而 man 后的第一个参数:

    • 1: Executable programs
    • 2: System calls3: Library calls

最常见的就是这三个了。我们要查看 getopt.h 中的,选择第三个。找到 getopt_long() 的定义与使用方法。初始化 struct option 后… 详细的就不说了,下次用到的时候再看文档(x

  • init_log 中也无什么可以说的。包括 init_mem()

  • 接下来是一个比较关键的 init_isa()init_isa 中(我选择 riscv32 来学习)。

    init_isa 函数中会将 image 复制到 IMAGE_START 中(为 pmem 所代表的地址,由 guest_to_host 函数进行映射,而 guest_to_host 函数的意思为

    /* convert the guest physical address in the guest program to host virtual address in NEMU */

NEMU 的执行会在$n$次循环后结束,而这个$n$由 ~0 (-1) 得到。还算比较简单吧。

  • 踩了个坑,使用 uint 的时候,不能拿来判长度。不信你试试看,绝对挂。

  • 在 +4 那里又挂了一次。一个 word 是两个字节 xxx

  • inline 那个是咋回事?应该是定义函数的时候并不需要加上更多的qulifier?我也记不清了。

需要注意的是,在编写获取寄存器内容的时候,需要特别处理 pc,因为 pc 并未出现在 regsl 中。

PA1 写完了,来个总结。(至于必答题… 我就偷懒惹

各类 #include<> 的写法, 我果然还得再努力学习一下。写完代码不能什么都不学到,至少得学到点工程的知识对吧,那就是 Think twice, code once,同一个道理。

补充。实际上我的 debugger 有不少的 bug,但是鉴于此项目整体比较简单,而且启动 debugger 比较麻烦,我后来也没怎么用过这个 debugger。这部分的基础设施我就懒得再 fix bugs 了。

PA2

一条指令在 NEMU 中的一生

程序运行顺序:

main.c 开始运行后进入 init_monitor,其中 load_img 会加载其 ~.bin

接下来在 engine_start 中,ui_mainloop 会识别其为 batchmode 并且进行 cmd_c进入 cpu_exec。该指令的一生从这里开始。

说错了点,其实是从循环里的 isa_exec_once() 开始,其在 nemu/isa/riscv32/exec/exec.c 中定义。

首先来看这个 DecodeExecState,在 decode.h 中定义,

typedef struct {
  uint32_t opcode;
  vaddr_t seq_pc;  // sequential pc
  uint32_t is_jmp;
  vaddr_t jmp_pc;
  Operand src1, dest, src2;
  int width;
  rtlreg_t tmp_reg[4];
  ISADecodeInfo isa;
} DecodeExecState;

注意其中的几个关键点。我们按照isa_exec_once() 中的顺序介绍。首先默认不是 jmp 的类型(所以关于 pc 的操作可以暂时忽略)。并将 seq_pc 置为 cpu.pc(之后再管这部分)

其中的 ISADecodeInfo 是跟着 ISA 的,isa.h 中进行了宏定义将具体的 ISA 定义为了该 ISADecodeInfo。我们的 riscv32_ISADecodeInfo 大致内容如下

typedef struct {
  union {
    struct {
      uint32_t opcode1_0 : 2;
      ...
    } i;
    struct {
      uint32_t opcode1_0 : 2;
      ...
    } s;
    struct {
      uint32_t opcode1_0 : 2;
      ...
    } u;
     ...
    uint32_t val;
  } instr;
} riscv32_ISADecodeInfo;

定义了 opcode 的几种形态,至于这几种形态的具体内容,refer to riscv-spec.pdf 的 page 16。后面带了一个 val,用来存储指令原有的样子。那个加冒号的写法实际上是位段的处理,保证 i/s/u 的二进制位和和标准的 instruction format 对应吧。这里非标准使用 union 的骚操作保证 val 里的每一位都直接被赋值…实在精彩。如果需要自己写这段,大小端的问题需要注意,算了今天就不处理了。

于是,这条指令进入了 fetch_decode_exec() 函数中。这个函数将带领这个指针走完其一生。

我们实现的CPU执行一条指令有四个步骤,IF | ID | EX | PC。

IF 比较简单,阅读 instr_fetch 可以发现,只是一次访问 vaddr 的询问,取其地址内容即可。


开始 ID 并保证 opcode1_0 == 0x3 。(至于为什么,看文档去)

接下来是对 opcode6_2 进行 switch。其中 IDEX 是一份宏定义,在 exec.h 中。共进行了三步。确定 instruction 的宽度,通过宏定义 decode 到具体函数,通过宏定义执行具体函数。嘛,由于 switch 是使用跳表,所以会快一些。

我们在 switch 中使用的都是 IDEX,即默认将 width 置为 0。

mips32和riscv32的访存指令会有不同操作数宽度的版本, 包括32位, 16位和8位, 因此我们还需要把宽度信息记录到s中提供后续过程使用.

然后,设置完宽度后,我们花大篇幅来修改一下译码(ID)操作。给宏提供的参数为具体的 I/S/U,及会被解析为 decode_load_I 函数。依次类推。

然后是操作数(Operand)的控制,这要求我们进行进一步 Decode,由 Decode Helper Function 完成。 DHF 的宏定义在 include/cpu/decode.h ,而 Decode Operand Helper Function 的宏定义在 local_include/decode.h 中,目前只有两种操作,即 decode_op_idecode_op_r,对应立即数和寄存器。在被宏定义的 decode_op_r 中,有一个 op->preg,是一个指向对应寄存器的指针。这样做避免了每次都访问 reg_l(val)

被 DHF 定义的一系列函数基本都是重复的工程操作,查 specification 即可。照着这个类型,再多实现些指令类型也可。


译码部分就这样,我们可爱的指令终于可以开始执行了。

执行部分的函数定义由 def_EHelper 进行。

需要执行的指令可能有多种情况,即 isa.{}.funct3 就可以区分不同指令,与 funct3/funct7 同时需要以区分指令。但是 EX 系列的宏并不允许我们在指令中进行 switch(你明明就可以不用它!),但是为了与 load, store 代码的整体性,我还是选择用 EX 宏 + 新添加一个函数来处理。

在操作寄存器的过程中,我们使用 rtlrtl pseudortl pseudo 存在的意义是方便我们使用 rtl

总而言之,经过了大半周摸摸搞搞的修改(这部分没有写 pa-record),终于实现了 RV32IRV32M 系列的指令,实现了部分 klib 后,离项目的完成又尽了一步(躺)


接下来就是 I/O 的部分了,即设备的输入输出。

设备的输入输出有集中常见方式。端口 I/O 和内存映射 I/O。

前者的对寄存器操作设备的方案依赖于 in/out 指令。这两个指令能够负责向某个端口的寄存器写入某些值,设备读取这些值并且进行对应操作。

MMIO 则更加先进,在物理内存空间上分配一段空间给设备,然后 CPU 在操作某段内存的时候,不知不觉就操作了对应的设备。


mainargs 传入的过程:在 nemu.mk 的 line 19

CFLAGS += -DMAINARGS=\"$(mainargs)\"

在编译时这个会被传入到 mainargs[] 变量中,再在 _trm_inirt() 中被传入到 main 函数中去。神秘。


接下来让我尝试理清楚 NEMU 和 AM 在软硬件上配合的关系。

首先从硬件层的 NEMU 说起吧。NEMU 在每条指令运行的时候都会尝试观测 device_update_flag 的情况。如果为 true,则会在指令执行结束之后运行 device.c 中的 device_update 函数,这个函数目前(主要)负责:

  1. 进行 vga_update,将会调用 vga.c 中的 vga_update_screen 函数,该函数会观测寄存器 sync 的情况,如果其值为 1 则真正意义上进行同步。
  2. 进行 key_down 的观测,这个是基于 SDL 的 API,就不深究了。

既然现在要写显卡,我们来看一看 VGA 的部分。update_screen 函数会操作 SDL 读取 vmem 中的内容显示图像,我们姑且不管这一部分,回到软件层面来看一看。

既然 AM 是 NEMU 的抽象,我们就不能简单从“这俩会通信”来入手。

最基础的最基础的问题是,NEMU 是编译在 x86-64 上的,而 AM 是跑在 riscv32 上的。而事实上,NEMU 当然能获取自己的寄存器(及内存)信息,AM 也能修改其寄存器(及内存)信息。所以这俩就建立了通信。我们的目的是让自己写的 C 能跑在 riscv32 上。 AM 给用户程序提供了几个常规的 API,比如说 io_readio_write。这两个函数能操作 AM 让 AM 让 AM 修改寄存器信息。


声卡,虽然会很砖,但是必须实现。仙剑奇侠传怎么能没声音呢?

/* * * * * * * * * * AUDIO PART * * * * * * * * * * *
 * AURIO_CTRL   : Audio control, to change freq/channel/samples
 * AUDIO_STATUS : Used buffer size
 * AUDIO_PLAY   : Write [buf.start, buf.end) to buffer, wait until there's space
 * */
AM_DEVREG(14, AUDIO_CONFIG, RD, bool present; int bufsize);
AM_DEVREG(15, AUDIO_CTRL,   WR, int freq, channels, samples);
AM_DEVREG(16, AUDIO_STATUS, RD, int count);
AM_DEVREG(17, AUDIO_PLAY,   WR, Area buf);
// * * * * * * * * * AUDIO PART * * * * * * * * * * *

首先我们来分析一下 am-tests 中的 audio.c。这是一段播放小星星的代码。

audio.c 最开始是检测 AM_AUDIO_CONFIGpresent 是否为 true,当然,我们需要将其设为 true

接下来是初始化 freq 等基本信息,略过。

AUDIO_PLAY 需要一段 Area,用于存即将写入 buffer 的内容…

我靠,从昨天晚上写到刚才,终于能跑了,来检讨一下笨死了的自己。

我实现的是一个由 AM 上的 push 和 nemu 里的 pop 维护的一个 queue,这个 queue 装在对应内存里。内存的前 8 个字节用于装 headend,是队列所对应的循环数组的首尾。

由程序调用 AM 中的 __am_audio_play,其会等待直到 buffer 中有空余空间后进行写入。这里其实有不少问题,是依赖于主机的 context switch 的,所以我采用一种比较保守的实现,但是实际上好像… 额,性能比较弱。即在 pushpop 函数内部对 queue 的 size 通过 MMIO 进行维护。 之后可以在这里多想想,然后尝试实现一些以一个 segment 为单位的队列?性能应该会高不少。

SDL 的回调函数每次会取 2048 个元素(有可能),性能还算不错。但是 push 那边的话因为需要等待空间,性能就比较弱。

不过第一次写是为了正确实现,抽象的比较高。现在的实现应该是没有问题的,如果仙剑那边跑的实在太卡的话我就用 mem 系列指令重写一下。(虽然 mem 系列我也没优化就是了,肯定要优化一下的,比如给 mem 系列实现一个硬件层的接口让宿主来进行 memset ???x)

之后有心情的话可以去读一下 LiteNES 的代码,这次就算了。居然还能学优化x 之后再说。


PA3

PA3 这部分比较难懂,有一些 undoc feature

我们来做那个必答题,yield() 调用之后发生了什么。

进入了 yield 函数,将 a7 作为参数(即 sstatus)传给了 ecallecall 执行对应操作,并调用 raise_instr 执行了设置 sepc 和设置 scause 等操作。需要注意,在 cte_init 中,我们将 __am_asm_trap函数指针传入了 stvec,所以其会 jmp__am_asm_trap 里。__am_asm_trap 的操作相对比较迷惑,大概意思就是在栈里初始化了 Context*,于是在接下来的函数就能访问之前的内容。大概是,这样吧。我是有点没读懂的。


我一直不太熟悉 ELF 的格式,今天再来 review 一下。

ELF 有面向链接的 section 视角,提供了可重定位信息。第二个是面向执行的 segment 视角,这个视角提供了加载可执行文件的信息。 通过 readelf 我们能看到 sectionsegment 的映射关系。

ELF 采用 program header table 来管理 segment。通过 ehdr 来管理 section。其中 ehdr 包含了所有 segment 放置的位置(通过一个数组)

所以我们的 loader 需要负责加载所有的 segment

ELF 还有很多我不太熟悉的操作,还是以后遇到问题 man 5 elf 吧。(上面的东西是前几天写的了,懒得补充了)


今天我们再来梳理一下从 hello.c 到最后程序运行的过程。

hello.c 由其 Makefile 管理。这里再让我吐槽一下 CLion 的逻辑,Makefile 在 CLion 里完全不可用(躺)。我也不想一点一点做移植,就这样将就了。

然后我们将 hello.c mvramdisk.img,其为一个已经并未链接的 elf。它会在 nanos-lite 链接的时候由 resource.S 链接到其 .data 段中。(???感觉这操作好神秘)

.section .data
.global ramdisk_start, ramdisk_end
ramdisk_start:
.incbin "build/ramdisk.img"
ramdisk_end:
// ...

关于上述步骤,用 readelf 查看 nanos-lite 的编译结果可以看到,.symtab 里有 ramdisk_startramdisk_end 的痕迹。ramdisk 的一系列 API 能够让读取该段内存的内容。而我们的 loader() 则负责将该段内存读取到其应该存在的地方。(即其自身 ELF header 设置的 entry 及其之后的内容)

既然 loader 返回了 entrynaive_uloadpc 切换到 loaderentry,即开始运行 ramdisk 的内容了。

关于 ecall 的部分我再给自己哆嗦两句。ecall 的类型参数存放在 a7 中,我们规定 a7 = [0..20) 是系统调用。其编号的具体内容在 navy_apps 的 syscall.h 中存放着。syscall.c 中实现了一些系统调用(说来我咋觉得这些东西该放在 nanos-lite 中呢,不过放在 navy-apps 中也有一定道理倒是x)


终于写完虚拟文件系统了… 写了一周多。这套文件系统里有不少的坑,我们慢慢道来。

虚拟文件系统又是一层抽象(尽管会略微降低性能?),我们实现了一份比较简单的文件系统,支持基础的读写操作。虚拟文件系统实现的核心是,为特殊文件实现特殊的读写函数,而这个读写函数不一定是针对储存空间操作的,可能是针对某一些特殊的数据流操作的。当然,通用的读写函数也是必须被实现的,这些读写函数将操作真正的一块处于硬盘(?)中的一块被抽象的,称作文件的空间。关于文件的格式已经研究过了,在这里就不再赘述。

我们在此处只需考虑那些特殊的,“被抽象”出来的文件。比如:

 typedef struct {
  char *name;
  size_t size;
  size_t disk_offset;
  ReadFn read;
  WriteFn write;
} Finfo;

// ...
{"/dev/events", 0, 0, events_read, invalid_write},
{"/proc/dispinfo", 0, 0, dispinfo_read, invalid_write},
{"/dev/fb", 0, 0, invalid_read, fb_write},

这三者是被抽象出的文件,抽象出的文件的核心在于那个 ReadFn 函数,这个函数是可以被自行定义的,比如 dispinfo_read 就会调用 AM 中实现的一系列接口,返回一段字符。这段字符并没有放在硬盘上。

在对文件读写时,首先尝试调用 ReadFn 以及 WriteFn,若失败,才会跌落至常规的对文件的读写。

在此基础上实现了 device.c 中的一系列函数,包括:

  • serial_write: 串口输入输出,抽象为 stdout/stderr
  • events_read: 从 AM_INPUT_KEYBRD 获取键盘输入信息,抽象为 /dev/events
  • dispinfo_read: 已经提到了
  • fb_write: 是显存的抽象,实现不太友好(还有不少瑕疵),不想提了。

总而言之,经过了一段时间,已经解决了这部分的内容,该进入 PA3 的最后一部分啦!


Fixed-point arithmetic

神秘的,可以避开 FPU 实现的方法。

定点算数实现的核心是避开 IEEE 标准,自己实现一套更加简便的,和当前 ALU 同构的规范。浮点数和定点数的运算本身没有过大的区别,都是数字和数字的碰撞,IEEE 标准徒增功耗(不)

于是我们定义一套新的标准,对于一个实数 $a$,我们将其表示为 $A = a \cdot 2^8$,在内存中存储为

31  30                           8          0
+----+---------------------------+----------+
|sign|          integer          | fraction |
+----+---------------------------+----------+

(书里的图,我就嫖来了)

鉴于小数的最低位是在 $2^{-8}$,我们乘上 $2^8$ 之后可以建立一套双射。

回答这个问题:

阅读fixedpt_rconst()的代码, 从表面上看, 它带有非常明显的浮点操作, 但从编译结果来看却没有任何浮点指令. 你知道其中的原因吗?

确实啊(沉思),先总结一下,fixedpt 让编译器来负责大部分的浮点处理。

我们用 godbolt 来测试一下,int a = (int)1.333;,得出的指令并没有浮点运算。fixedpt_rconst 也同理

#define fixedpt_rconst(R) ((fixedpt)((R) * FIXEDPT_ONE + ((R) >= 0 ? 0.5 : -0.5)))
#define FIXEDPT_ONE    ((fixedpt)((fixedpt)1 << FIXEDPT_FBITS))

FIXEDPT_ONE 则是之前提到的 $2^8$,这部分预处理会在编译器完成。而例如,$-1.2$,会出现 $-1.2 \cdot 2^8 - 0.5 \rightarrow -307.7 \rightarrow -307$ 的情况,这个 $\pm0.5$ 估计是拿来修正整数值的吧。晕乎乎,不管了。


TODO: PA3


我们还是先开始 PA4 好了,毕竟 PA3 的后面部分有点砖。我简单修了一下批处理系统那套,应该能够基本运行了。不过我还是对分时多任务感兴趣一点,于是就先做 PA4 了。

PA4 难度不低,我们先解决基本的 Context Switch 的问题。分为几步比较神秘的。

首先把 ContextPCB 的定义扔在这里。

typedef union {
  uint8_t stack[STACK_SIZE] PG_ALIGN;
  struct {
    Context *cp;
    AddrSpace as;
    // we do not free memory, so use `max_brk' to determine when to call _map()
    uintptr_t max_brk;
  };
} PCB;

struct Context {
  uintptr_t gpr[32];
  uintptr_t cause, status, epc;
  void *pdir;
};

其定义比较清晰,PCB 的意思是进程控制块,用户保存内核栈和 cpContext pointer,指向保存的用于 Context switch 的“虚假的上下文”。而这个虚假的上下文是虚假给 trap.S 看的,trap.S 会还原这个偷梁换柱的上下文中的信息,并且通过 sret 跳转到其 epc 的位置。偷梁换柱进行的位置是 trap.S 中的 jal __am_irq_handle,这个函数会产生返回值并且放在 a0。我们只需 mv sp, a0 即可漂漂亮亮地替换被还原的上下文。

init_irq 的时候调用了 cte_initdo_event 被作为全局变量user_handler 放入到了 cte.c 中,这个函数指针今后会在 __am_irq_handle 调用,并且会返回 c,在 trap.S 中的 a0 寄存器被接收,先不谈这里。

kcontext 会创建一个上下文,将其放在 kstack 的最底部。然后 PCBunion 会将 cp 指向 context 的顶部。sret 会将这玩意儿倒回 Context 设定的位置,开始 Context 部分的运行。

为了清晰地解释,画一张图。

image.png

为了节约空间(懒)我没有画3一些细节的部分。

[实在太久没有阶段性的成就感了,先把这玩意儿丢到博客里好了]