南京大学 ICS-PA 总结

https://nju-projectn.github.io/ics-pa-gitbook/ics2021/index.html

这个课程我是在微博上看到包云岗老师转发进来的,之前也没有搞过这方面的实验所以就想试试。个人感觉是对于已经相对熟悉计算系体系结构的同学来说,也不是特别简单。许多地方需要理解代码为什么这么写,你还需要假设自己是在某一个抽象层次上,是看不到其他层次抽象的东西的。感觉Makefile写的非常好,另外就是一些链接脚本也值得学习下。我觉得整个项目是个宝藏,时不时可以拿出来翻翻作为参考。

整个项目大概分为这么几个部分:

最后跑起来的可执行程序只有NEMU, AM + nanos-lite + navy-apps 都交叉编译(我使用的是riscv64)被打包成为二进制镜像被加载NEMU里面,二进制被加载到特定的内存位置上开始被解释执行。在没有VME的时候,交叉编译的二进制都是从类似0x8000000开始执行的,使用的是物理地址;有了VME之后交叉编译的二进制就可以放在任意地址上了。

整个PA有些东西我也没有搞:各种trace(ftrace,iotrace etc), 声卡,移植SDL,跑各种应用程序。对于不是课程学生来说,最重要的是选择自己感兴趣并且稍微有点挑战的内容来完成。我的实现在这里 https://github.com/dirtysalt/ics-pa


PA1 主要工作是在NEMU里面增加watchpoint, watchpoint就涉及到表达式的求值。

NEMU里面一个很有意思的工作就是允许使用图形化界面进行配置 `make menuconfig`. 按照PA说明给出的原理就是有个很简单的语言kconfig, 然后可以使用图形化来读取kconfig并且生成对应的头文件autoconf.h以及auto.conf。autoconfig.h里面都是类似 `#define CONFIG_XXX` 这样的选项给C语言使用的,auto.conf则是可以被include到Makefile中。


PA2 主要工作有下面几个:

实现CPU指令最好是按照test cases需要一个个去实现,每条指令都可以使用RTL(register transfer language)来实现,因为每个指令实现起来可能还会使用的到中间状态,而这些中间状态则需要使用临时寄存器。某些指令是伪指令需要找到具体指令,对于某些指令则还需要看看汇编代码里面的hex格式进行对照。最终大约需要实现下面这些

#define INSTR_LIST(f) f(auipc) f(ld) f(sd) f(inv) f(nemu_trap) f(addi) f(jal) f(jalr) \
f(add) f(sub) f(sltiu) f(beq) f(bne) f(addiw) f(slli) f(lw) f(addw) f(sh) f(srai) \
f(lbu) f(sllw) f(andi) f(and) f(or) f(sltu) f(xori) f(ori) f(sb) f(sraiw) f(sw) \
f(mul) f(div) f(divu) f(mulw) f(divw) f(divuw) f(remw) f(remuw) f(rem) f(remu) \
f(srli) f(bge) f(bgeu) f(blt) f(bltu) \
f(slti) f(slt) f(lh) f(lhu) f(subw) f(srlw) f(sraw) f(slliw) f(srliw) f(lui) \
f(sll) f(lb) f(xor) \
f(csrrw) f(csrrs) f(ecall) f(mret)

好像JAL和BRANCH里面还会将指令中各个部分的内容进行bit mix, 这个实现起来需要非常小心。

// offset[20|10:1|11|19:12]
// offset[19|9:0|10|18:11]
#define JAL_SHUFFLE(imm) \
    (((imm >> 19) & 0x1) << 19) | ((imm & 0xff) << 11) | (((imm >> 8) & 0x1) << 10) | ((imm >> 9) & 0x3ff)

// offset[12|10:5|4:1|11]
// offset[11|9:4|3:0|10]
#define BRANCH_SHUFFLE(imm) \
    (((imm >> 11) & 0x1) << 11) | ((imm & 0x1) << 10) | (((imm >> 5) & 0x3f) << 4) | ((imm >> 1) & 0x0f)

许多现代体系结构处理外设上都采用MMIO(memory mapped io), 相当于给IO设备分配某个特定的地址空间,访问地址空间需要使用volatile关键字不然编译器是不知道存在副作用的。另外一种设备管理方式则是使用端口IO(port io). 为了能够兼容不同CPU/体系结构(NEMU/QEMU), AM需要在这层进行封装,将这些IO读写包装成为一种形式,这个就是IOE的用途。我记得后来在file和VGA映射上做了个hack, 我没有将write(fd, buf)内容写入,而是直接将buf指针传到下面了。

这节我记得实现了一个ftrace, 大致就是可以根据指令结合ELF找到当前属于什么函数。对于riscv来说没有什么call/ret, 都是jmp, 所以需要在其他地方判断是call/ret. 我们可以通过跳转地址属于func start addr来判断:如果是函数首地址,那么认为是call, 否则就是ret. 函数栈可能会出现不匹配,我猜想原因可能是因为尾递归造成的:如果我在尾递归做个简单操作比如+1就可以匹配上了。

这节有个NEMU benchmark跑分,我的实现可以说是非常的差,好像只有4分左右,惨不忍睹的那种。


PA3 两个部分:CTE(context extension, 上下文切换)以及unix-like file映射。unix-like file映射没有什么新鲜东西,所以主要还是上下文切换,以及包括如何简单地加载ELF文件。

当前阶段的实现,都是将ELF直接加载到某个物理地址上,所以如果ELF都是相同的start address的话那么就只能加载一个ELF。主要就是下面这段代码(nanos-lite/src/loader.c):


PA4 三个部分:进程切换,虚拟内存,以及用户态和内核态栈切换(我没太看懂为什么需要它,因为每个用户进程都可以访问内核栈)。

如果大学学过x86汇编啥的,大约CTE对应的就是里面的中断:触发中断会有个专门的中断例程,并且带上中断号。这个例程地址存放在某个固定的寄存器上,对于这类内存地址的虚拟内存映射都是在内核初始化阶段搞好的,这个在PA4的VME里面可以看到。这个上下文切换非常有意思,需要结合栈结构+ABI协同工作。

riscv64里面的中断例程大约就是这样的 (abstract-machine/am/src/riscv/nemu/trap.S), 分为几个部分:

// abstract-machine/am/include/arch/riscv64-nemu.h

struct Context {
    // TODO: fix the order of these members to match trap.S
    uintptr_t gpr[32], mcause, mstatus, mepc;
    // TODO(yan): I don't know what's that for? what's dir?
    // page table directory?
    void* pdir;
};

#define concat_temp(x, y) x ## y
#define concat(x, y) concat_temp(x, y)
#define MAP(c, f) c(f)

#if __riscv_xlen == 32
#define LOAD  lw
#define STORE sw
#define XLEN  4
#else
#define LOAD  ld
#define STORE sd
#define XLEN  8
#endif

#define REGS(f) \
      f( 1)       f( 3) f( 4) f( 5) f( 6) f( 7) f( 8) f( 9) \
f(10) f(11) f(12) f(13) f(14) f(15) f(16) f(17) f(18) f(19) \
f(20) f(21) f(22) f(23) f(24) f(25) f(26) f(27) f(28) f(29) \
f(30) f(31)

#define PUSH(n) STORE concat(x, n), (n * XLEN)(sp);
#define POP(n)  LOAD  concat(x, n), (n * XLEN)(sp);

#define CONTEXT_SIZE  ((32 + 3 + 1) * XLEN)
#define OFFSET_SP     ( 2 * XLEN)
#define OFFSET_CAUSE  (32 * XLEN)
#define OFFSET_STATUS (33 * XLEN)
#define OFFSET_EPC    (34 * XLEN)

.align 3
.globl __am_asm_trap
__am_asm_trap:
  addi sp, sp, -CONTEXT_SIZE

  MAP(REGS, PUSH)

  csrr t0, mcause
  csrr t1, mstatus
  csrr t2, mepc

  STORE t0, OFFSET_CAUSE(sp)
  STORE t1, OFFSET_STATUS(sp)
  STORE t2, OFFSET_EPC(sp)

  # set mstatus.MPRV to pass difftest
  li a0, (1 << 17)
  or t1, t1, a0
  csrw mstatus, t1

  # first argument as ctx pointer.
  mv a0, sp
  jal __am_irq_handle

  # TODO(yan): we ignore return ctx?
  # a0 is address of Context*
  mv sp, a0

  LOAD t1, OFFSET_STATUS(sp)
  LOAD t2, OFFSET_EPC(sp)
  csrw mstatus, t1
  csrw mepc, t2

  MAP(REGS, POP)

  addi sp, sp, CONTEXT_SIZE

  mret

这个Context是如何和进程关联起来的呢?下面是进程结构体PCB定义(nanos-lite/include/proc.h)

typedef union {
    uint8_t stack[STACK_SIZE] PG_ALIGN;
    struct {
        Context* cp;
        // TODO(yan): to record user space stack end.
        // so we can reuse user space stack.
        void* user_stack_end;
        AddrSpace as;
        // we do not free memory, so use `max_brk' to determine when to call _map()
        uintptr_t max_brk;
    };
} PCB;

我花了一些时间整理了一下Context以及PCB还有kernel stack/user stack之间的关系,大约是下面这样的:

nju-ics-pa-pcb.jpg

虚拟内存有几件事情比较重要:


关于PIC/PIE, TLB设计,以及页表转换的坑(取指令的时候可能会跨越两个页表),我觉得也挺有启发的,所以粘贴在这里。

这就是PIC(position-independent code, 位置无关代码)的基本思想. 今天的动态库都是PIC, 这样它们就可以被加载到任意的内存位置了. 此外, 如果一个可执行文件全部由PIC组成, 那么它有一个新名字, 叫PIE(position-independent executable, 位置无关可执行文件). 编译器可以通过特定的选项编译出PIE. 和一般的程序不同, PIE还能在一定程度上对恶意的攻击程序造成了干扰: 恶意程序也无法提前假设PIE运行的地址. 也正是因为这一安全相关的特性, 最近的不少GNU/Linux的发行版上配套的gcc都默认生成PIE. 不过, 使用相对寻址会使得程序的代码量增大, 性能也会受到一些影响, 但对于早期的计算机来说, 内存是一种非常珍贵的资源, 降低性能也是大家不愿意看到的, 因此对于PIC和PIE, 大家也会慎重考虑.

对于x86和riscv32来说, TLB一般都是由硬件来负责管理的: 当TLB miss时, 硬件逻辑会自动进行page table walk, 并将地址转换结果填充到TLB中, 软件不知道也无需知道这一过程的细节. 对PA来说, 这是一个好消息: 既然对软件透明, 那么就可以简化了. 因此如果你选择了x86或者riscv32, 你不必在NEMU中实现TLB. 但mips32就不一样了, 为了降低硬件设计的复杂度, mips32规定, page table walk和TLB填充都由软件来负责. 很自然地, 在mips32中, TLB miss被设计成一种异常: 当TLB miss时, CPU将会抛出异常, 由软件来进行page table walk和TLB填充.

TLB管理是一个考量软硬件tradeoff的典型例子, mips32把这件事交给软件来做, 毫无疑问会引入额外的性能开销. 在一些性能不太重要的嵌入式场景中, 这并不会有什么大问题; 但如果是在一些面向高性能的场景中, 这种表面上简单的机制就成为了性能瓶颈的来源: 例如在数据中心场景中, 程序需要访问的数据非常多, 局部性也很差, TLB miss是非常常见的现象, 这种情况下, 软件管理TLB的性能开销就会被进一步放大.

最后提醒一下x86页级地址转换时出现的一种特殊情况. 由于x86并没有严格要求数据对齐, 因此可能会出现数据跨越虚拟页边界的情况, 例如一条很长的指令的首字节在一个虚拟页的最后, 剩下的字节在另一个虚拟页的开头. 如果这两个虚拟页被映射到两个不连续的物理页, 就需要进行两次页级地址转换, 分别读出这两个物理页中需要的字节, 然后拼接起来组成一个完成的数据返回. 不过根据KISS法则, 你现在可以暂时不实现这种特殊情况的处理, 在判断出数据跨越虚拟页边界的情况之后, 先使用assert(0)终止NEMU, 等到真的出现这种情况的时候再进行处理. 而mips32和riscv32作为RISC架构, 指令和数据都严格按照4字节对齐, 因此不会发生这样的情况, 否则CPU将会抛出异常, 可见软件灵活性和硬件复杂度是计算机系统中又一对tradeoff.