ICS PA 4

多道程序

一个简单的想法就是，在系统一开始的时候加载多个程序，然后运行第一个；当第一个程序需要等待输入输出的时候，就切换到第二个程序来运行；当第二个程序也需要等待的时候，就继续切换到下一个程序来运行，如此类推。

要把批处理的 Nanos-lite 改造成一个多道程序操作系统，我们只需要实现以下两点就可以了：

在内存中可以同时存在多个进程
在满足某些条件的情况下，可以让执行流在这些进程之间切换

要实现第一点，目前有点困难。为了简单起见，我们可以在 Nanos-lite 中直接定义一些测试函数来作为程序，这里指 nanos-lite/src/proc.c 中的 hello_fun 函数。

下面先考量第二点。

上下文切换

在 PA3 中，我们已经提到了操作系统和用户进程之间的执行流切换。

上下文的本质就是进程的状态

我们现在需要考虑的是，如何在多个用户进程之间进行上下文切换。

基本原理

假设进程 A 运行的过程中触发了系统调用，陷入到内核。
根据 __am_asm_trap() 的代码，A 的上下文结构将会被保存到 A 的栈上。
系统调用处理完毕之后，__am_asm_trap() 会根据栈上保存的上下文结构来恢复 A 的上下文。
如果我们先不着急恢复 A 的上下文，而是先将栈顶指针切换到另一个进程 B 的栈上，由于 B 的栈上存放了之前 B 保存的上下文结构，接下来的操作就会根据这一结构来恢复 B 的上下文。
从 __am_asm_trap() 返回之后，我们已经在运行进程 B 了。

所以，上下文切换其实就是不同进程之间的栈切换。

进程控制块

我们需要一个 cp 指针来记录上下文结构的位置，当想要找到其它进程的上下文结构的时候，只要寻找这个进程相关的 cp 指针即可。

context pointer

Nanos-lite 的框架代码中已经定义了我们所需要使用的 PCB 结构，在 nanos-lite/include/proc.h 中定义：

typedef union {
  uint8_t stack[STACK_SIZE] PG_ALIGN;
  struct {
    Context *cp;
  };
} PCB;

内核线程

那么，对于刚刚加载完的进程，我们要怎么切换到它来让它运行起来呢？

答案很简单，我们只需要在进程的栈上人工创建一个上下文结构，使得将来切换的时候可以根据这个结构来正确地恢复上下文即可。

我们接下来的任务就是为 hello_fun 创建一个上下文，然后切换到它来执行。

这样的执行流有一个专门的名称，叫内核线程。

kernel thread

创建内核线程的上下文是通过 CTE 提供的 kcontext() 函数来实现的，在 abstract-machine/am/src/riscv/nemu/cte.c 中定义。

其原型为：

Context* kcontext(Area kstack, void (*entry)(void *), void *arg);

其中 kstack 是栈的范围，entry 是内核线程的入口，arg 则是内核线程的参数。

我们需要在 kstack 的底部创建一个以 entry 为返回地址的上下文结构，然后返回这一结构的指针：

Context *kcontext(Area kstack, void (*entry)(void *), void *arg) {
  uint32_t *ed = kstack.end;
  Context *base = (Context *) (ed - 36); // 36 = 32 + 3 + 1
  base->mepc = (uintptr_t) entry;
  return base;
}

注意指针的使用，对内存空间的不同解读

在 Nanos-lite 中，我们可以通过一个 context_kload() 函数来进行进一步的封装：它会调用 kcontext() 来创建上下文，并把返回的指针记录到 PCB 的 cp 中：

|               |
+---------------+ <---- kstack.end
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- kstack.start
|               |

其实现如下：

void context_kload(PCB *pcb, void (*entry)(void *), void *arg) {
  Area stack;
  stack.start = pcb->stack;
  stack.end = pcb->stack + STACK_SIZE;
  pcb->cp = kcontext(stack, entry, arg);
}

这里的关键是理解 PCB 是一个 union

线程 / 进程调度

上下文的创建和切换是 CTE 的工作，而具体切换到哪个上下文，则是由操作系统来决定的，这项任务叫做进程调度。

这其实体现了系统设计中的一种重要原则——机制和策略解耦

在 Project-N 中，这一解耦几乎做到了极致：机制和策略被分离到两个子项目中

AM 的另外一个好处是将底层硬件的行为抽象成系统级机制，AM 上的应用 (包括 OS) 只需要调用这些系统级机制，并实现相应的策略即可

进程调度是由 schedule() 函数来完成的，在 nanos-lite/src/proc.c 中定义：

Context* schedule(Context *prev) {
  // save the context pointer
  current->cp = prev;

  // always select pcb[0] as the new process
  current = &pcb[0];

  // then return the new context
  return current->cp;
}

它用于返回将要调度的进程上下文。

current 指针用于指向当前运行进程的 PCB。

剩余工作

为了实现上下文切换，还需要完成如下工作：

在 Nanos-lite 收到 EVENT_YIELD 事件后，我们需要调用 schedule() 并返回新的上下文：

static Context* do_event(Event e, Context* c) {
  switch (e.event) {
    case EVENT_YIELD:
        Log("EVENT_YIELD");
        c = schedule(c);
        break;
    ...

在 init_proc() 中单独创建一个以 hello_fun 为返回地址的上下文：

void init_proc() {
  context_kload(&pcb[0], hello_fun, NULL);
  switch_boot_pcb();
}

需要注释掉下面的 naive_uload，也可以加载 dummy 测试程序，直接触发 SYS_yield 系统调用

修改 CTE 中 __am_asm_trap() 的实现，使得从 __am_irq_handle() 返回后，先将栈顶指针切换到新进程的上下文结构，然后才恢复上下文，从而完成上下文切换的本质操作：

  jal __am_irq_handle

  # return context in a0 -> sp
  mv sp, a0

这里 __am_irq_handle() 函数返回了 cp 指针，也就是新进程的上下文结构

在 Nanos-lite 中识别出时钟中断事件

为了在 native 上进行上下文切换……

内核线程的参数

我们来创建两个内核线程，给它们传递不同的参数，然后在输出的信息中把参数也一同输出，这样我们就能看到执行流在两个内核线程之间来回切换了。

为此，我们需要修改 kcontext 函数，将参数放入上下文保存的寄存器 a0 中：

Context *kcontext(Area kstack, void (*entry)(void *), void *arg) {
  uint32_t *ed = kstack.end;
  Context *base = (Context *) (ed - 36); // 36 = 32 + 3 + 1
  base->mepc = (uintptr_t) entry;
  base->gpr[10] = (uintptr_t) arg;
  return base;
}

并修改 schedule，在两个内核线程之间来回切换：

Context* schedule(Context *prev) {
  // save the context pointer
  current->cp = prev;

  current = ((current == &pcb[0]) ? &pcb[1] : &pcb[0]);

  // then return the new context
  return current->cp;
}

最后我们在 init_proc 中创建两个内核线程：

void init_proc() {
  context_kload(&pcb[0], hello_fun, "A");
  context_kload(&pcb[1], hello_fun, "B");
  switch_boot_pcb();
  ...

让 hello_fun 以字符串的形式解析内核线程的参数：

void hello_fun(void *arg) {
  int j = 1;
  while (1) {
    Log("Hello World from Nanos-lite with arg '%s' for the %dth time!", (const char *)arg, j);
    j ++;
    yield();
  }
}

就可以了……

最后的效果大概是这样：

[/home/vgalaxy/ics2021/nanos-lite/src/irq.c,9,do_event] EVENT_YIELD
[/home/vgalaxy/ics2021/nanos-lite/src/proc.c,23,hello_fun] Hello World from Nanos-lite with arg 'A' for the 25285th time!
[/home/vgalaxy/ics2021/nanos-lite/src/irq.c,9,do_event] EVENT_YIELD
[/home/vgalaxy/ics2021/nanos-lite/src/proc.c,23,hello_fun] Hello World from Nanos-lite with arg 'B' for the 25285th time!
[/home/vgalaxy/ics2021/nanos-lite/src/irq.c,9,do_event] EVENT_YIELD
[/home/vgalaxy/ics2021/nanos-lite/src/proc.c,23,hello_fun] Hello World from Nanos-lite with arg 'A' for the 25286th time!
[/home/vgalaxy/ics2021/nanos-lite/src/irq.c,9,do_event] EVENT_YIELD
[/home/vgalaxy/ics2021/nanos-lite/src/proc.c,23,hello_fun] Hello World from Nanos-lite with arg 'B' for the 25286th time!
...

在真实的操作系统中，内核中的很多后台任务、守护服务和驱动程序都是以内核线程的形式存在的。如果你执行 ps aux，你就会看到系统中有很多 COMMAND 中带有中括号的内核线程，例如 [kthreadd]。

AM 在定义 kcontext() 的行为时，还要求 kcontext() 只能在栈上放置一个上下文结构，而不能放置更多的内容。这样的要求有两点好处：

kcontext() 对栈的写入只有一个上下文结构的内容，而不会产生其它的副作用
OS 可以预测调用 kcontext() 之后的返回值，并且利用这一确定的特性进行一些检查或者简化某些实现

然而 x86 是通过栈来传递参数，如果 kcontext() 需要支持 arg 的传递，它就需要往栈上放置更多的内容，这样就违反了上述确定性了……

可能的解决方案：引入一个辅助函数来将真正的参数传递从 kcontext() 推迟到内核线程的运行时刻……

用户进程

debug

麻了，不会……

先总结一下：

若内核线程在前，其 cp 会被覆写为零……
若内核线程在后，不考虑用户栈都可以执行……
_start 中对寄存器 sp 的赋值应为跳转的前一条语句

第二天了，准备使用各种 trace 工具进行诊断……

通过 mtrace 发现覆写的记录：

^[[1;34m[src/memory/paddr.c:54 paddr_write] address = 0x81b34000 write 0x00000000 at pc = 0x80001dd0^[[0m

通过 ftrace 进一步观察：

/home/vgalaxy/ics2021/nemu/build/riscv32-nemu-interpreter -b -l /home/vgalaxy/ics2021/nanos-lite/build/nemu-log.txt --elf=/home/vgalaxy/ics2021/nanos-lite/build/nanos-lite-riscv32-nemu.elf /home/vgalaxy/ics2021/nanos-lite/build/nanos-lite-riscv32-nemu.bin

在 paddr_write 中添加，将 Error 立即变为 Failure：

    ...
      if (addr == 0x81b34000 && data == 0) assert(0);
    ...

观察函数调用轨迹：

0x80001054: call   [do_syscall@0x800004a8]
0x800004e8: call   [do_syscall@0x800005d0]
0x800005dc: call   [fs_read@0x800009a8]
0x80000aa8: call   [dispinfo_read@0x80001374]
0x800013a4: call   [memset@0x80001dc0]
0x80001ddc: ret    [memset]
0x800013b0: call   [ioe_read@0x800018ac]
0x800018c4: call   [__am_gpu_config@0x80001958]
0x8000197c: ret    [__am_gpu_config]
0x800013c8: call   [sprintf@0x8000283c]
0x8000286c: call   [vsprintf@0x80002268]
0x800022b4: call   [memset@0x80001dc0]
riscv32-nemu-interpreter: src/memory/paddr.c:56: paddr_write: Assertion `0' failed.

定位错误源是 vsprintf 中的 memset：

    // memset(out,'\0',BUF_SIZE);

由于 out 为外部传入的参数，假定其至少有 BUF_SIZE 的大小显然有问题……

调试理论的一次实践……

context_uload

现在回到正题……

在 PA3 的批处理系统中，我们在 naive_uload() 中直接通过函数调用转移到用户进程的代码，那时候使用的还是内核区的栈。万一发生了栈溢出，就会出大问题。

内核线程使用的也是内核区的栈

内核线程的正确性可以由内核开发人员来保证

为了区别开来，我们把 PCB 中的栈称为内核栈，位于用户区的栈称为用户栈。

于是我们需要一个有别于 kcontext() 的方式来创建用户进程的上下文，那就是 ucontext()，在 abstract-machine/am/src/riscv/nemu/vme.c 中定义：

Context *ucontext(AddrSpace *as, Area kstack, void *entry) {
  uint32_t *ed = kstack.end;
  Context *base = (Context *) (ed - 36); // 36 = 32 + 3 + 1
  base->mepc = (uintptr_t) entry;
  return base;
}

其实现和 kcontext() 几乎一样。

用户栈相关的部分交给 Nanos-lite 来进行。

目前我们让 Nanos-lite 把 heap.end 作为用户进程的栈顶。

Nanos-lite 和 Navy 约定，Nanos-lite 把栈顶位置设置到 GPRx 中，然后由 Navy 里面的 _start 来把栈顶位置真正设置到栈指针寄存器中。

**请务必注意 __am_asm_trap 中恢复上下文的 POP 操作。**将栈顶位置存到 GPRx 后，恢复上下文时就可以保证 GPRx 中就是栈顶位置，紧接着就是用户进程的 _start：

.globl  _start
_start:
  move s0, zero

  # set heap.end to the stack pointer register
  mv sp, a0

  jal call_main

注意位置，必须为跳转的前一条语句

最后我们定义 context_uload，通过定义 context_uload_helper 获取入口地址：

void context_uload(PCB *pcb, const char *filename) {
  uintptr_t entry = context_uload_helper(pcb, filename);

//  Area stack;
//  stack.start = pcb->stack;
//  stack.end = pcb->stack + STACK_SIZE;

  Area stack;
  uint8_t *ed = heap.end;
  stack.end = ed;
  stack.start = ed - STACK_SIZE;

  Log("stack.start: %p, stack.end: %p", stack.start, stack.end);
  Log("entry: %p", entry);

  pcb->cp = ucontext(NULL, stack, (void(*)()) entry);

  pcb->cp->GPRx = (uintptr_t) heap.end;
}

后来发现 context_kload 和 context_uload 应该定义在 loader.c 中……

问题又来了，传入 ucontext 的参数为 heap 还是 pcb 中的 stack：

若为 heap，PCB 记录如下：

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87ffff70
Context switch: 0x81b8df70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87ffff70
Context switch: 0x87ffff70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87fffda0
Context switch: 0x81b8df70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87fffda0
Context switch: 0x87fffda0

...

对于内核线程：

|               |
+---------------+ <---- kstack.end
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- kstack.start
|               |

对于用户进程：

|               |
+---------------+ <---- heap.end
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
                     |
                     |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- kstack.start
|               |

注意下面的栈位于内核区，上面的栈位于用户区……

若为 pcb 中的 stack，PCB 记录如下：

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x81b95f70
Context switch: 0x81b8df70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x81b95f70
Context switch: 0x81b95f70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87fffda0
Context switch: 0x81b8df70

&pcb[0]: 0x81b86000, &pcb[0]->cp: 0x81b8df70
&pcb[1]: 0x81b8e000, &pcb[1]->cp: 0x87fffda0
Context switch: 0x87fffda0

...

用户进程的 Context 只在内核栈中创建了一次（用于第一次跳转），然后均在用户栈中保存……

经过简单的分析，应该选择第二种……

后面还有进一步的分析……

别忘了在 serial_write(), events_read() 和 fb_write() 的开头调用 yield() 来模拟设备访问缓慢的情况。添加之后，访问设备时就要进行上下文切换，从而实现多道程序系统的功能。

为了让 AM native 正确运行，需要在 navy-apps/libs/libos/src/crt0/start/am_native.S 中设置正确的栈指针。

观察 AM native 的 ucontext 实现，可知依赖于参数 as，然而目前传入 NULL，所以还行不通……
Context* ucontext(AddrSpace *as, Area kstack, void *entry) {
  Context *c = (Context*)kstack.end - 1;

  __am_get_example_uc(c);
  c->uc.uc_mcontext.gregs[REG_RIP] = (uintptr_t)entry;
  c->uc.uc_mcontext.gregs[REG_RSP] = (uintptr_t)USER_SPACE.end;

  int ret = sigemptyset(&(c->uc.uc_sigmask)); // enable interrupt
  assert(ret == 0);
  c->vm_head = as->ptr;

  c->ksp = (uintptr_t)kstack.end;

  return c;
}
另外，AM native 实现中断的机制与 riscv 并不同，找不到对应的 __am_asm_trap

用户进程的参数

loader

首先修改一下 loader，使其兼容 Nanos-lite native：

没仔细研究 ABI 的后果……

#ifdef __LP64__
# define Elf_Ehdr Elf64_Ehdr
# define Elf_Phdr Elf64_Phdr
char magic[16] = {0x7f, 0x45, 0x4c, 0x46, 0x02, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
#else
# define Elf_Ehdr Elf32_Ehdr
# define Elf_Phdr Elf32_Phdr
char magic[16] = {0x7f, 0x45, 0x4c, 0x46, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
#endif

// see /usr/include/elf.h to get the right type
// #define EM_RISCV        243 /* RISC-V */
// #define EM_X86_64       62  /* AMD x86-64 architecture */
// #define EM_386           3  /* Intel 80386 */
// #define EM_MIPS_RS3_LE  10  /* MIPS R3000 little-endian */


#if defined(__ISA_AM_NATIVE__) || defined(__ISA_X86_64__)
# define EXPECT_TYPE EM_X86_64
#elif defined(__ISA_X86__)
# define EXPECT_TYPE EM_386
#elif defined(__ISA_RISCV32__) || defined(__ISA_RISCV64__)
# define EXPECT_TYPE EM_RISCV
#elif defined(__ISA_MIPS32__)
# define EXPECT_TYPE EM_MIPS_RS3_LE  // TODO: need validation
#else
# error Unsupported ISA
#endif


static uintptr_t loader(PCB *pcb, const char *filename) {
    int fd = fs_open(filename, 0, 0);

    Elf_Ehdr elf_header;
    fs_read(fd, &elf_header, sizeof(elf_header));

    // check magic number
    for (int i = 0; i < 16; ++i) assert(magic[i] == elf_header.e_ident[i]);

    // check machine architecture
    assert(elf_header.e_machine == EXPECT_TYPE);

    // get entry point address
    uintptr_t entry_point_address = elf_header.e_entry;

    // get program header basic infos
    uint32_t program_header_index = elf_header.e_phoff;
    uint32_t program_header_length = elf_header.e_phentsize; // the size of one section
    uint32_t program_header_number = elf_header.e_phnum;

    // handle items of program header
    for (int i = 0; i < program_header_number; ++i) {
      Elf_Phdr ent;
      fs_lseek(fd, program_header_index + program_header_length * i, SEEK_SET);
      fs_read(fd, &ent, sizeof(Elf_Phdr));
      uint32_t type = ent.p_type;
      if (type == PT_LOAD) {
          uint32_t offset = ent.p_offset;
          uint32_t virtAddr = ent.p_vaddr;
          uint32_t fileSiz = ent.p_filesz;
          uint32_t memSiz = ent.p_memsz;

          char * buf_malloc = (char *)malloc(fileSiz * sizeof(char) + 1);
          assert(fs_lseek(fd, offset, SEEK_SET) >= 0);
          assert(fs_read(fd, buf_malloc, fileSiz) >= 0);
          memcpy((void *)(uintptr_t)virtAddr, buf_malloc, fileSiz);
          memset((void *)(uintptr_t)(virtAddr + fileSiz), 0, memSiz - fileSiz);
          free(buf_malloc);
      }
    }

    return entry_point_address;
}

argc / argv / envp

回到正题，操作系统在加载用户进程的时候，需要负责把 argc / argv / envp 以及相应的字符串放在用户栈中，并把它们的存放方式和位置作为和用户进程的约定之一，这样用户进程在 _start 中就可以根据约定访问它们了。

envp 指向的字符串数组里是形如 xxx=yyy 的字符串，表示有一个名为 xxx 的变量，它的值为 yyy。可以使用 getenv() 获取环境变量。

具体的约定如图所示：

|               |
+---------------+ <---- ustack.end
|  Unspecified  |
+---------------+
|               | <----------+
|    string     | <--------+ |
|     area      | <------+ | |
|               | <----+ | | |
|               | <--+ | | | |
+---------------+    | | | | |
|  Unspecified  |    | | | | |
+---------------+    | | | | |
|     NULL      |    | | | | |
+---------------+    | | | | |
|    ......     |    | | | | |
+---------------+    | | | | |
|    envp[1]    | ---+ | | | |
+---------------+      | | | |
|    envp[0]    | -----+ | | |
+---------------+        | | |
|     NULL      |        | | |
+---------------+        | | |
| argv[argc-1]  | -------+ | |
+---------------+          | |
|    ......     |          | |
+---------------+          | |
|    argv[1]    | ---------+ |
+---------------+            |
|    argv[0]    | -----------+
+---------------+
|      argc     |
+---------------+ <---- cp->GPRx
|               |

ABI: Process Initialization

Linux 上遵守的 ABI 是 System V ABI，它分为两部分：

一部分是和处理器无关的 generic ABI (gABI)，例如 ELF 格式，动态连接，文件系统结构等

一部分是和处理器相关的 processor specific ABI (psABI)，例如调用约定，操作系统接口，程序加载等

操作系统部分，我们需要修改 context_uload 的原型：

void context_uload(PCB *pcb, const char *filename, char *const argv[], char *const envp[]) {
  Log("filename: %s", filename);
  uintptr_t entry = loader(pcb, filename);

  Area stack;
  stack.start = pcb->stack;
  stack.end = pcb->stack + STACK_SIZE;

//  Area stack;
//  uint8_t *ed = heap.end;
//  stack.end = ed;
//  stack.start = ed - STACK_SIZE;

  Log("stack.start: %p, stack.end: %p", stack.start, stack.end);
  Log("entry: %p", entry);

  // prepare entry point
  pcb->cp = ucontext(NULL, stack, (void(*)()) entry);

  // prepare argv and envp
  void *ustack_end = new_page(8);
  int space_count = 0; // unit: the size of pointer
  // TODO: unspecified part

  int argc = 0;
  if (argv) while (argv[argc]) {
      // Log("argv[%d]: %s", argc, argv[argc]);
      argc++;
  }
  space_count += sizeof(uintptr_t); // for argc
  space_count += sizeof(uintptr_t) * (argc + 1); // for argv
  if (argv) for (int i = 0; i < argc; ++i) space_count += (strlen(argv[i]) + 1);

  int envpc = 0;
  if (envp) while (envp[envpc]) envpc++;
  space_count += sizeof(uintptr_t) * (envpc + 1); // for envp
  if (envp) for (int i = 0; i < envpc; ++i) space_count += (strlen(envp[i]) + 1);

  Log("argc: %d, envpc: %d, space_count: %d", argc, envpc, space_count);

  space_count += sizeof(uintptr_t); // for ROUNDUP
  Log("base before ROUNDUP: %p", ustack_end - space_count);
  uintptr_t *base = (uintptr_t *)ROUNDUP(ustack_end - space_count, sizeof(uintptr_t));
  uintptr_t *base_mem = base;
  Log("base after ROUNDUP: %p", base);

  *base = argc;
  base += 1;

  char *argv_temp[argc];
  char *envp_temp[envpc];
  base += (argc + 1) + (envpc + 1); // jump to string area
  char *string_area_curr = (char *)base;
  uintptr_t *string_area_curr_mem = (uintptr_t *)string_area_curr;

  for (int i = 0; i < argc; ++i) {
      strcpy(string_area_curr, argv[i]);
      argv_temp[i] = string_area_curr;
      string_area_curr += (strlen(argv[i]) + 1);
      Log("argv[%d]: %s, addr: %p", i, argv[i], argv_temp[i]);
  }

  for (int i = 0; i < envpc; ++i) {
      strcpy(string_area_curr, envp[i]);
      envp_temp[i] = string_area_curr;
      string_area_curr += (strlen(envp[i]) + 1);
      Log("envp[%d]: %s, addr: %p", i, envp[i], envp_temp[i]);
  }

  base -= (argc + 1) + (envpc + 1); // jump back

  for (int i = 0; i < argc; ++i) {
      *base = (uintptr_t)argv_temp[i];
      base += 1;
  }

  *base = (uintptr_t)NULL;
  base += 1;

  for (int i = 0; i < envpc; ++i) {
      *base = (uintptr_t)envp_temp[i];
      base += 1;
  }

  *base = (uintptr_t)NULL;
  base += 1;

  assert(string_area_curr_mem == base);

  pcb->cp->GPRx = (uintptr_t)base_mem;
}

需要注意的地方如下：

通过 new_page 获取 32KB 的内存作为用户栈，原因在下面解释
需要对 argv 和 envp 是否为 NULL 进行特判
先将字符串拷贝到用户栈中，再对 argv 和 envp 赋值
区分 const pointer 和 pointer to const
- char * const * -> a pointer to a const pointer to a char
- char const * * -> a pointer to pointer to a const char
- char * const [] -> an array of a const pointer to a char
- char const * [] -> an array of a pointer to a const char
- refer to http://c-faq.com/decl/spiral.anderson.html

用户程序部分，我们修改 call_main：

void call_main(uintptr_t *args) {
  uintptr_t *base = args;
  int argc = *base;
  base += 1;
  char **argv = (char **)base;
  // for (int i = 0; i < argc; ++i) printf("argv[%d]: %s\n", i, argv[i]);
  base += (argc + 1);
  char **envp = (char **)base;
  environ = envp;
  exit(main(argc, argv, envp));
  assert(0);
}

注意编写可移植的代码，因为 call_main() 是被各种 ISA 所共享的。

对可移植性没有信心……

对于测试，我们可以修改仙剑奇侠传的少量代码，如果它接收到一个 --skip 参数，就跳过片头动画：

   //
   // Show the trademark screen and splash screen
   //
   if (!(argc == 2 && (strcmp(argv[1], "--skip") == 0))) {
       PAL_TrademarkScreen();
       PAL_SplashScreen();
   }

我们可以这样创建用户进程：

  char *argv[] = {"/bin/pal", "--skip", NULL};
  char *envp[] = {NULL};
  context_uload(&pcb[1], "/bin/pal", argv, envp);

也可以这样：

  char *argv[] = {"/bin/pal", "--skip", NULL};
  context_uload(&pcb[1], "/bin/pal", argv, NULL);

别忘了第一个参数是程序名……

SYS_execve

观察 execve 的原型：

int execve(const char *filename, char *const argv[], char *const envp[]);

我们可以让用户来指定参数，并让操作系统来把指定的参数放到新进程的用户栈里面。

于是我们需要进一步优化系统调用 SYS_execve。

用户层：

int _execve(const char *fname, char * const argv[], char *const envp[]) {
  return _syscall_(SYS_execve, (intptr_t)fname, (intptr_t)argv, (intptr_t)envp);
}

操作系统部分，分派：

    case SYS_execve:
#ifdef CONFIG_STRACE
        Log("sys_execve(%s, %p, %p)", (const char *)c->GPR2, c->GPR3, c->GPR4);
#endif
        sys_execve((const char *)c->GPR2, (char * const*)c->GPR3, (char * const*)c->GPR4);
        while(1);

系统调用处理函数：

int sys_execve(const char *fname, char *const argv[], char *const envp[]) {
    // naive_uload(NULL, fname);
    context_uload(current, fname, argv, envp);
    switch_boot_pcb();
    yield();
    return -1;
}

通过强制修改当前进程块并立即触发 yield，进行上下文切换……

讲义中分析，B 可以安全使用 A 在 PCB 中的内核栈。然而在加载 B 时，Nanos-lite 使用的是 A 的用户栈，这意味着在 A 的执行流结束之前，A 的用户栈是不能被破坏的。

因此，我们应该申请一段新的内存作为 B 的用户栈，这就是上面 new_page 的用途。其简单的实现如下：

void* new_page(size_t nr_page) {
  pf += nr_page * PGSIZE;
  Log("ustack.end: %p", pf);
  return pf;
}

PGSIZE 为 4KB

我们有一个测试程序 navy-apps/tests/exec-test，它会以参数递增的方式不断地执行自身：

int main(int argc, char *argv[]) {
  int n = (argc >= 2 ? atoi(argv[1]) : 1);
  printf("%s: argv[1] = %d\n", argv[0], n);

  char buf[16];
  sprintf(buf, "%d", n + 1);
  execl(argv[0], argv[0], buf, NULL);
  return 0;
}

这里的 execl 使用了变长参数……

不过由于我们没有实现堆区内存的回收，exec-test 在运行一段时间之后，new_page() 就会把 0x3000000/0x83000000 附近的内存分配出去，导致用户进程的代码段被覆盖。

大概几百次调用……

另外，我们还可以完善 NTerm 的內建 Shell，使得它可以解析输入的参数，并传递给启动的程序：

#define buf_size 128
static char fname[buf_size];
static char arg_first[buf_size];

static void sh_handle_cmd(const char *cmd) {
    if (cmd == NULL) return;
    if (strncmp(cmd, "echo", 4) == 0) {
        if (strlen(cmd) == 5) sh_printf("\n");
        else sh_printf("%s", cmd + 5);
    } else {
        if (strlen(cmd) > buf_size) {
            sh_printf("command too long\n");
            return;
        }
        int arg_first_offset = 0;
        while (cmd[arg_first_offset] != ' ') {
            arg_first_offset++;
            if (cmd[arg_first_offset] == '\n') {
                arg_first_offset = -1;
                break;
            }
        }
        memset(fname, 0, buf_size);
        memset(arg_first, 0, buf_size);

        if (arg_first_offset > 0) {
            strncpy(fname, cmd, arg_first_offset);
            strncpy(arg_first, cmd + arg_first_offset + 1, strlen(cmd) - arg_first_offset);
            char *argv[] = {fname, arg_first, NULL};
            execve(fname, argv, NULL);
        } else {
            strncpy(fname, cmd, strlen(cmd) - 1);
            char *argv[] = {fname, NULL};
            execve(fname, argv, NULL);
        }
        // execvp(fname, argv);
    }
}

这里粗略的实现了对 argc ≤ 2 的识别。

另外，由于之前设置的环境变量似乎与上述实现不兼容：

argv[0]: �� V

我们需要完整敲入程序名……

大大增加了调试时间……

可以删去 fb_write() 的开头调用的 yield() ……

后来将 fname 和 arg_first 设为动态分配的数组就可以解决了……

Busybox

Busybox 会把其中的 Shell 工具链接成一个 ELF 可执行文件，而不是像 Ubuntu/Debian 等发行版中的 Shell 工具那样，每个工具都是独立的 ELF 可执行文件。

Busybox 的 main() 函数会根据传入的参数来调用相应工具的功能：

main -> run_applet_and_exit

感觉不太行……

程序行为汇总：

有环境变量

nterm -> cat -> ^
nterm -> menu -> nterm -> cat -> cat -> ^

发现大量的环境变量，且大部分都无权访问……

[base before] -> argv[0]: '�'D
[base before] -> argc: 1
[base before] -> envpc: 10593

所以就没法创建用户栈……

无环境变量

只要完整输入正确程序名，就不会报错，但是会出现：

[base before] -> argv[0]: $ �
[base before] -> argc: 1
[base before] -> envpc: 0

[before bb_basename] applet_name: $ �
[after bb_basename] applet_name: $ �
$ � : applet not found

无法解析 Busybox 中的程序名

或者可以研究一下 libc 中 execvp 和 setenv 的实现……

只能在 Navy native 中把玩 Busybox 了……

我们可以把 /usr/bin 也加入到 PATH 环境变量中……

虽然没啥意义，但这促使我们优雅的处理文件不存在的情况……

Nanos-lite 在处理 SYS_execve 系统调用的时候需要检查将要执行的程序是否存在，如果不存在，就需要返回一个错误码。

我们可以通过 fs_open() 来进行检查，如果需要打开的文件不存在，就返回一个错误的值，此时 SYS_execve 返回 -2。

另一方面，libos 中的 execve() 还需要检查系统调用的返回值：如果系统调用的返回值小于 0，则通常表示系统调用失败，此时需要将系统调用返回值取负，作为失败原因设置到一个全局的外部变量 errno 中，然后返回 -1。

navy-apps/libs/libc/src/posix/execvp.c

errno 是 C 标准定义的运行时环境中的一个全局变量，用于存放最近一次失败的系统调用或库函数调用的错误码。

$ errno -l
EPERM 1 Operation not permitted
ENOENT 2 No such file or directory
...

关于错误的处理，引入 errno_loader_flag，以 fs_open 为源点扩散调用轨迹：

fs_open (Log, return -1) <- loader (set flag) <- naive_uload (panic)

fs_open (Log, return -1) <- loader (set flag) <- context_uload <- init_proc (panic)

fs_open (Log, return -1) <- loader (set flag) <- context_uload <- sys_execve (return -2) <- do_syscall (set GPRx -2)

fs_open (Log, return -1) <- do_syscall (set GPRx -1)

括号中给出了处理方案……

基本思想是，系统启动前的错误直接 panic，系统运行中的错误可以容忍……

奇怪的是，引入了错误处理后，在无环境变量下，只要在执行 Busybox 中程序的命令前触发了错误，就可以正常运行了。而且执行后，NTerm 会被重新唤起……

操作 fsimg 中的文件似乎不太行……

原因是多了一个换行……

最后使用 strtok 优化 sh_handle_cmd：

static void sh_handle_cmd(const char *cmd) {
    if (cmd == NULL) return;
    if (strncmp(cmd, "echo", 4) == 0) { // built-in command
        if (strlen(cmd) == 5) sh_printf("\n");
        else sh_printf("%s", cmd + 5);
    } else {
        int argc = 0;

        char *cmd_without_newline = (char *)malloc(sizeof(char) * strlen(cmd));
        memset(cmd_without_newline, 0, strlen(cmd));
        strncpy(cmd_without_newline, cmd, strlen(cmd) - 1);

        char **argv = (char **)malloc(sizeof(char *) * argc_max);

        char *cur = strtok(cmd_without_newline, " ");
        assert(cur != NULL); // avoid cur is ""

        char *fname = (char *)malloc(sizeof(char) * (strlen(cur) + 1));
        memset(fname, 0, strlen(cur) + 1);
        strcpy(fname, cur);
        printf("[sh_handle_cmd] filename: %s at %p\n", fname, fname);

        while (cur) {
            printf("[sh_handle_cmd] argv[%d]: %s at %p\n", argc, cur, cur);
            argv[argc] = cur;
            cur = strtok(NULL, " ");
            argc++;
            if (argc == argc_max) {
                sh_printf("too many arguments\n");
                free(argv);
                free(fname);
                free(cmd_without_newline);
                return;
            }
        }
        argv[argc] = NULL;

        execve(fname, argv, NULL);

        fprintf(stderr, "\033[31m[ERROR]\033[0m Exec %s failed.\n\n", fname);
        free(argv);
        free(fname);
        free(cmd_without_newline);
        ...

来试试吧：

[before bb_basename] applet_name: /usr/bin/wc
[after bb_basename] applet_name: wc
     1000      1000      5000 /share/files/num

后来分析，在有环境变量的情况下，我们不用管那 10593 个怪怪的东西，直接在 context_uload 置 envpc 为零。然后行为就与无环境变量下一致了！

于是 built-in echo 覆盖了 /bin/echo ……

另外，在有环境变量的情况下，exec-test 需要输入完整的程序名，因为在自调用时没有环境变量……

唯一的缺憾，需要先触发一次错误……

现在我们可以理解，平时键入命令的时候计算机系统的各个抽象层都做了些什么：

终端如何读取用户的按键
Shell 如何进行命令的解析
库函数如何根据命令解析出的字符串搜索到可执行文件
操作系统如何加载执行一个可执行文件
……

麻了，cp 在长时间运行后会被覆写：

SDL_FreeSurface -> free -> _free_r

后面也触发了类似的 BUG

虚存管理

程序和内存位置

我们已经实现了一个多道程序的多任务系统，但却在尝试运行第二个用户进程的时候遇到了问题：我们在加载第二个用户进程的时候，就会覆盖第一个进程的内容。

因而，操作系统需要记录内存的分配情况，当需要运行一个新进程的时候，就给它分配一片空闲的内存位置，把它加载到这一内存位置上即可。

一般来说，根据程序的内存位置，可分类如下：

绝对代码：内存位置在链接时刻 (link time) 确定，使用绝对地址
可重定位代码：根据重定位的时间，又可以分为两种：
- 运行时 (run time) 重定位：在开始运行的时候，先把自己重定位到其它内存位置，然后再开始真正的运行。然而程序在运行时刻并不知道重定位的目标内存位置是否空闲
- 加载时 (load time) 重定位：让加载器来进行重定位，加载器会申请一个空闲的内存位置，然后将程序加载到这个内存位置，并把程序重定位到这个内存位置，之后才会执行这个程序
位置无关代码：程序中的所有寻址，都是针对程序位置来进行相对寻址操作，这样的程序就可以被加载到任意位置执行
- 如果一个可执行文件全部由 PIC 组成，那么它有一个新名字，叫 PIE (position-independent executable，位置无关可执行文件)
- PIE 还能在一定程度上对恶意的攻击程序造成了干扰，恶意程序也无法提前假设 PIE 运行的地址
- PIE 之所以能做到位置无关，其实是要依赖于程序中一个叫 GOT (global offset table，全局偏移量表) 的数据结构。要正确运行 PIE，加载器需要在加载程序的时候往 GOT 中填写正确的内容

另一种尝试是把程序看到的内存和它运行时候真正使用的内存解耦开来，这就是虚拟内存的思想。

我们需要在处理器和存储器之间添加一个新的硬件模块 MMU。

虚拟内存机制是一个软硬协同才能工作的机制：

操作系统负责进行物理内存的管理，加载进程的时候决定要把进程的虚拟地址映射到哪些物理地址
等到进程真正运行之前，还需要配置 MMU，把之前决定好的映射落实到硬件上

分段与分页

关于 MMU 具体如何进行地址映射，目前主要有两种主流的方式，即分段与分页。

分段

物理地址 = 虚拟地址 + 偏移量

分段机制在硬件上的实现可以非常简单，只需要在 MMU 中实现一个段基址寄存器就可以了。

操作系统在运行不同进程的时候，就在段基址寄存器中设置不同的值，MMU 会把进程使用的虚拟地址加上段基址，来生成真正用于访问内存的物理地址。

实际上，处理器中的分段机制有可能复杂得多。我们可以目睹一下 i386 分段机制的风采：

           15              0    31                                   0
  LOGICAL +----------------+   +-------------------------------------+
  ADDRESS |    SELECTOR    |   |                OFFSET               |
          +---+---------+--+   +-------------------+-----------------+
       +------+         V                          |
       | DESCRIPTOR TABLE                          |
       |  +------------+                           |
       |  |            |                           |
       |  |            |                           |
       |  |            |                           |
       |  |            |                           |
       |  |------------|                           |
       |  |  SEGMENT   | BASE          +---+       |
       +->| DESCRIPTOR |-------------->| + |<------+
          |------------| ADDRESS       +-+-+
          |            |                 |
          +------------+                 |
                                         V
              LINEAR  +------------+-----------+--------------+
              ADDRESS |    DIR     |   PAGE    |    OFFSET    |
                      +------------+-----------+--------------+

计组点名批评……

于是分段机制的各种概念不会加入到 NEMU 中来……

分页

事实上，我们需要一种按需分配的虚存管理机制。之所以分段机制不好实现按需分配，就是因为段的粒度太大了，为了实现这一目标，我们需要反其道而行之：把连续的存储空间分割成小片段，以这些小片段为单位进行组织，分配和管理。

分页机制引入了一个叫页表的结构，页表中的每一个表项记录了一个虚拟页到物理页的映射关系，来把不必连续的物理页面重新组织成连续的虚拟地址空间。

注：

PIC 可以将代码加载到任意内存位置执行，配合虚存管理，PIC 可以实现程序代码的共享……

重新考虑空指针，当程序对空指针解引用的时候，实际上是解引用一个无效的内存地址

实际上，空指针的实现取决于编译器的实现，访问空指针的后果取决于操作系统的实现。

在 Linux 中，每个进程空间的 0x0 虚拟地址开始的线性区都会被映射到一个用户态没有访问权限的页上。而编译器把空指针当做 0 对待。这就实现了检测空指针的错误

https://www.quora.com/What-actually-happens-when-dereferencing-a-NULL-pointer

我们可以把这分段和分页的过程分别抽象成两个数学函数：

  y = seg(x) = seg.base + x
  y = page(x)

不难理解，仅仅使用分段机制，虚拟地址是无法超过物理地址上限的。而分页机制就有可能超越容量的界限。

状态机视角下的虚存管理机制

为了描述虚存管理机制在状态机视角的行为，我们需要对状态机 S = <R, M> 的访存行为进行扩展。具体地，我们需要增加一个函数 fvm: M -> M，它就是我们上文讨论的地址转换的映射，然后把状态机中所有对 M 的访问 M[addr] 替换成 M[fvm(addr)]。

我们可以总结一下状态机视角下 AM 的状态转移：

注意其中的两个函数：

fex() 函数实际上并不属于状态机的一部分，因为抛出异常的判断方式是和状态机的具体状态无关的
fvm() 函数可以视为状态机的一部分，这是因为 fvm() 函数是可以通过程序进行修改的：操作系统可以决定如何建立虚拟地址和物理地址之间的映射。具体地，fvm() 函数可以认为是系统寄存器 SR 的一部分，操作系统通过修改 SR 来对虚存进行管理

TLB - 地址转换的加速

将 Cache 的思想用于地址转换中。

对于 x86 和 riscv32 来说，TLB 一般都是由硬件来负责管理的：当 TLB miss 时，硬件逻辑会自动进行 page table walk，并将地址转换结果填充到 TLB 中，软件不知道也无需知道这一过程的细节。

于是在 NEMU 中不必实现 TLB 了……

但 mips32 就不一样了，为了降低硬件设计的复杂度，mips32 规定，page table walk 和 TLB 填充都由软件来负责。

mips32 已经泪崩……

内存初探

物理内存

abstract-machine/am/src/riscv/nemu/vme.c

static Area segments[] = {      // Kernel memory mappings
  NEMU_PADDR_SPACE
};

abstract-machine/am/src/platform/nemu/include/nemu.h

#define NEMU_PADDR_SPACE \
  RANGE(&_pmem_start, PMEM_END), \
  RANGE(FB_ADDR, FB_ADDR + 0x200000), \
  RANGE(MMIO_BASE, MMIO_BASE + 0x1000) /* serial, rtc, screen, keyboard */

共分为三段：

0x80000000 ~ 0x88000000：内核区和用户区，在无 VME 下，用户程序被链接到内存位置 0x83000000 附近
0xa1000000 ~ 0xa1200000：显存
0xa0000000 ~ 0xa0001000：其余设备

虚拟内存

abstract-machine/am/src/riscv/nemu/vme.c

#define USER_SPACE RANGE(0x40000000, 0x80000000)

0x40000000 ~ 0x80000000

将虚存管理抽象成 VME

Virtual Memory Extension

本质上，虚存管理要做的事情，就是在维护物理内存到虚拟内存的映射。但这个映射应该是每个进程都各自维护一份，因此我们需要如下的两个 API：

// 创建一个默认的地址空间
void protect(AddrSpace *as) {
  PTE *updir = (PTE*)(pgalloc_usr(PGSIZE));
  as->ptr = updir;
  as->area = USER_SPACE;
  as->pgsize = PGSIZE;
  // map kernel space
  memcpy(updir, kas.ptr, PGSIZE);
}

// 销毁指定的地址空间
void unprotect(AddrSpace *as) {}

其中 AddrSpace 是一个结构体类型，定义了地址空间描述符的结构，在 abstract-machine/am/include/am.h 中定义：

typedef struct AddrSpace {
  int pgsize;
  Area area;
  void *ptr;
} AddrSpace;

其中 pgsize 用于指示页面的大小，area 表示虚拟地址空间中用户态的范围，ptr 是一个 ISA 相关的地址空间描述符指针，用于指示具体的映射。

有了地址空间，我们还需要有相应的 API 来维护它们：

void map(AddrSpace *as, void *va, void *pa, int prot);

它用于将地址空间 as 中虚拟地址 va 所在的虚拟页，以 prot 的权限映射到 pa 所在的物理页。

最后还有另外两个统一的 API：

bool vme_init(void *(*pgalloc_f)(int), void (*pgfree_f)(void *))

用于进行 VME 相关的初始化操作。其中它还接受两个来自操作系统的页面分配回调函数的指针，让 AM 在必要的时候通过这两个回调函数来申请 / 释放一页物理页。

Context* ucontext(AddrSpace *as, Area kstack, void *entry)

用于创建用户进程上下文。

在分页机制上运行 Nanos-lite

在 nanos-lite/include/common.h 中定义宏 HAS_VME，Nanos-lite 在初始化的时候就会调用 init_mm() 函数，在 nanos-lite/src/mm.c 中定义：

void init_mm() {
  Log("heap.start: %p, heap.end: %p", heap.start, heap.end);
  pf = (void *)ROUNDUP(heap.start, PGSIZE);
  Log("free physical pages starting from %p", pf);

#ifdef HAS_VME
  vme_init(pg_alloc, free_page);
#endif
}

vme_init 的定义在 abstract-machine/am/src/riscv/nemu/vme.c：

bool vme_init(void* (*pgalloc_f)(int), void (*pgfree_f)(void*)) {
  pgalloc_usr = pgalloc_f;
  pgfree_usr = pgfree_f;

  kas.ptr = pgalloc_f(PGSIZE);

  int i;
  for (i = 0; i < LENGTH(segments); i ++) {
    void *va = segments[i].start;
    for (; va < segments[i].end; va += PGSIZE) {
      map(&kas, va, va, 0);
    }
  }

  set_satp(kas.ptr);
  vme_enable = 1;

  return true;
}

注意这里内核虚拟地址空间的映射为恒等映射。

map() 是 VME 中的核心 API，它需要在虚拟地址空间 as 的页目录和页表中填写正确的内容，使得将来在分页模式下访问一个虚拟页时，硬件得到的物理页正是之前在调用 map() 时给出的目标物理页。

为了让 map() 填写的映射生效，我们还需要在 NEMU 中实现分页机制，为此我们需要相应的 API：

// 检查当前系统状态下对内存区间为 [vaddr, vaddr + len), 类型为 type 的访问是否需要经过地址转换。
int isa_mmu_check(vaddr_t vaddr, int len, int type);

// 对内存区间为 [vaddr, vaddr + len), 类型为 type 的内存访问进行地址转换
paddr_t isa_mmu_translate(vaddr_t vaddr, int len, int type);

可以参考这个页面。

Sv32 分页方案

Sv32 支持 4GiB 的虚址空间，这些空间被划分为 2^10 个 4MiB 大小的巨页。每个巨页被进一步划分为 2^10 个 4KiB 大小的基页（分页的基本单位）。因此，Sv32 的页表是基数为 2^10 的两级树结构。页表中每个项的大小是四个字节，因此页表本身的大小是 4KiB。页表的大小和每个页的大小完全相同，这样的设计简化了操作系统的内存分配。

然后是 satp 寄存器的结构：

MODE 域可以开启分页并选择页表级数，对于 RV32 而言只有 0 / 1 两个选项。

通常 M 模式的程序在第一次进入 S 模式之前会把零写入 satp 以禁用分页，然后 S 模式的程序在初始化页表以后会再次进行 satp 寄存器的写操作。

我们允许 M 模式的访存也进行地址转换

这对应了 vme_init 在映射后 set_satp：

static inline void set_satp(void *pdir) {
  uintptr_t mode = 1ul << (__riscv_xlen - 1);
  asm volatile("csrw satp, %0" : : "r"(mode | ((uintptr_t)pdir >> 12)));
}

static inline uintptr_t get_satp() {
  uintptr_t satp;
  asm volatile("csrr %0, satp" : "=r"(satp));
  return satp << 12;
}

注意这里移位的位数为 12 位，也就是说我们只使用了 PPN 的低 20 位。

接着是页表项结构：

V 位决定了该页表项的其余部分是否有效。

R / W / X 位分别表示此页是否可以读取、写入和执行。如果这三个位都是 0，那么这个页表项是指向下一级页表的指针，否则它是页表树的一个叶节点。

PPN 域包含物理页号，这是物理地址的一部分。若这个页表项是一个叶节点，那么 PPN 是转换后物理地址的一部分。否则 PPN 给出下一节页表的地址。

类似 satp，我们只使用 PPN 域的低 20 位。

最后是地址转换过程：

当在 satp 寄存器中启用了分页时，S 模式和 U 模式中的虚拟地址会以从根部遍历页表的方式转换为物理地址。其过程如下：

satp.PPN 给出了一级页表的基址，VA[31:22] 给出了一级页号，因此处理器会读取位于地址 (satp.PPN×4096+VA[31:22]×4) 的页表项。
该 PTE 包含二级页表的基址，VA[21:12] 给出了二级页号，因此处理器读取位于地址 (PTE.PPN×4096+VA[21:12]×4) 的叶节点页表项。
叶节点页表项的 PPN 字段和页内偏移组成了最终结果，物理地址就是 (LeafPTE.PPN×4096+VA[11:0])

处理器并没有表的概念，地址转换的过程只不过是一些访存和位操作而已……

实现

OS Layer

先打开 HAS_VME

实现 pg_alloc：

static void *pf = NULL;

void* new_page(size_t nr_page) { // 分配高地址，往低地址增长
  pf += nr_page * PGSIZE;
  Log("free physical pages starting from %p", pf);
  return pf;
}

#ifdef HAS_VME
static void* pg_alloc(int n) {
  int nr_page = n / PGSIZE;
  assert(nr_page * PGSIZE == n);
  void *end = new_page(nr_page);
  void *start = end - n;
  memset(start, 0, n);
  return start;
}
#endif

由于 new_page 返回的是高地址，pg_alloc 需要减去分配空间的字节数返回低地址。另外，我们保证 AM 通过回调函数调用 pg_alloc() 时申请的空间总是页面大小的整数倍，此外 pg_alloc() 还需要对分配的页面清零。

初始化时内存是随机的，所以要清零……

AM Layer

实现 map：

#define VA_OFFSET(addr) (addr & 0x00000FFF)
#define VA_VPN_0(addr)  ((addr >> 12) & 0x000003FF)
#define VA_VPN_1(addr)  ((addr >> 22) & 0x000003FF)

#define PA_OFFSET(addr) (addr & 0x00000FFF)
#define PA_PPN(addr)    ((addr >> 12) & 0x000FFFFF)

void map(AddrSpace *as, void *va, void *pa, int prot) {
  // printf("[map start]\n[VA]: %p, [PA]: %p\n", va, pa);

  uintptr_t va_trans = (uintptr_t) va;
  uintptr_t pa_trans = (uintptr_t) pa;

  assert(PA_OFFSET(pa_trans) == 0);
  assert(VA_OFFSET(va_trans) == 0);

  uint32_t ppn = PA_PPN(pa_trans);
  uint32_t vpn_1 = VA_VPN_1(va_trans);
  uint32_t vpn_0 = VA_VPN_0(va_trans);

  // printf("[PA_PPN]: 0x%x, [VA_VPN_1]: 0x%x, [VA_VPN_0]: 0x%x\n", ppn, vpn_1, vpn_0);

  PTE * page_dir_base = (PTE *) as->ptr;
  PTE * page_dir_target = page_dir_base + vpn_1;
  // printf("[DIR BASE]: %p, [DIR TARGET]: %p\n", page_dir_base, page_dir_target);

  if (*page_dir_target == 0) { // empty
    PTE * page_table_base = (PTE *) pgalloc_usr(PGSIZE);
    *page_dir_target = ((PTE) page_table_base) | PTE_V;

    PTE * page_table_target = page_table_base + vpn_0;
    *page_table_target = (ppn << 12) | PTE_V | PTE_R | PTE_W | PTE_X;

    // printf("[DIR TARGET ITEM]: 0x%x\n", *page_dir_target);
    // printf("[TABLE BASE]: %p, [TABLE TARGET]: %p\n", page_table_base, page_table_target);
    // printf("[TABLE TARGET ITEM]: 0x%x\n", *page_table_target);
  } else {
    PTE * page_table_base = (PTE *) ((*page_dir_target) & PTE_PPN);

    PTE * page_table_target = page_table_base + vpn_0;
    *page_table_target = (ppn << 12) | PTE_V | PTE_R | PTE_W | PTE_X;

    // printf("[DIR TARGET ITEM]: 0x%x\n", *page_dir_target);
    // printf("[TABLE BASE]: %p, [TABLE TARGET]: %p\n", page_table_base, page_table_target);
    // printf("[TABLE TARGET ITEM]: 0x%x\n", *page_table_target);
  }

  // printf("[map end]\n\n");
}

恒等映射简化了映射过程。

这里的思维难点是页表结构的组织，需要通过页表地址的转换过程反推。

通过 pgalloc_usr 获取二级页表的空间……

最初想使用结构体的 bits field 提取地址信息，但似乎行不通……

于是使用了 macro 进行提取……

此处 PTE 类型为 uintptr_t，使用指针方便读写……

请务必区分指针与指针所指向的对象，如：

*page_dir_target = ((PTE) page_table_base) | PTE_V;

提取了指针 page_table_base 的值……

另一个需要注意的地方在：

PTE * page_table_base = (PTE *) ((*page_dir_target) & PTE_PPN);

其中：

#define PTE_PPN 0xFFFFF000 // 31 ~ 12

我们仅提取了高 20 位，这是因为创建时分配的页是 4KB 对齐的，低 12 位为零……

NEMU Layer

添加 satp 寄存器，这一次我们直接在 riscv32_CPU_state 结构体中添加成员。

并修改 CSR_dispatch：

rtlreg_t* CSR_dispatch(uint32_t index) {
    switch (index) {
        case 0x300: return s0; // mstatus
        case 0x305: return t0; // mtvec
        case 0x341: return s1; // mepc
        case 0x342: return s2; // mcause
        case 0x180: return &cpu.satp; // satp
        default: panic("Unsupported CSR");
    }
}

指令的部分不变……

然后是 isa_mmu_check，检查 satp 寄存器的 MODE 域即可：

#define isa_mmu_check(vaddr, len, type) ((((cpu.satp & 0x80000000) >> 31) == 1) ? MMU_TRANSLATE : MMU_DIRECT)

接着是 isa_mmu_translate：

#define VA_OFFSET(addr) (addr & 0x00000FFF)
#define VA_VPN_0(addr)  ((addr >> 12) & 0x000003FF)
#define VA_VPN_1(addr)  ((addr >> 22) & 0x000003FF)

#define PTE_V(item)   (item & 0x1)
#define PTE_R(item)   ((item >> 1) & 0x1)
#define PTE_W(item)   ((item >> 2) & 0x1)
#define PTE_X(item)   ((item >> 3) & 0x1)
#define PTE_PPN(item) ((item >> 12) & 0xFFFFF)

typedef vaddr_t PTE;

paddr_t isa_mmu_translate(vaddr_t vaddr, int len, int type) {
  // Log("[VA]: 0x%x", vaddr);

  rtlreg_t satp = cpu.satp;
  PTE page_dir_base = satp << 12;

  uint32_t offset = VA_OFFSET(vaddr);
  uint32_t vpn_1 = VA_VPN_1(vaddr);
  uint32_t vpn_0 = VA_VPN_0(vaddr);

  PTE page_dir_target = page_dir_base + vpn_1 * 4;
  word_t page_dir_target_item = paddr_read(page_dir_target, 4);
  // Log("[ DIR TARGET ]: 0x%x, [ DIR TARGET ITEM ]: 0x%x", page_dir_target, page_dir_target_item);

  if (PTE_V(page_dir_target_item) == 0) assert(0);

  PTE page_table_base = PTE_PPN(page_dir_target_item) << 12;
  PTE page_table_target = page_table_base + vpn_0 * 4;
  word_t page_table_target_item = paddr_read(page_table_target, 4);
  // Log("[TABLE TARGET]: 0x%x, [TABLE TARGET ITEM]: 0x%x", page_table_target, page_table_target_item);

  if (PTE_V(page_table_target_item) == 0) assert(0);

  switch (type) {
    case MEM_TYPE_IFETCH: if (PTE_X(page_table_target_item) == 0) assert(0); break;
    case MEM_TYPE_READ:   if (PTE_R(page_table_target_item) == 0) assert(0); break;
    case MEM_TYPE_WRITE:  if (PTE_W(page_table_target_item) == 0) assert(0); break;
    default: assert(0); break;
  }

  paddr_t ppn = PTE_PPN(page_table_target_item) << 12;
  paddr_t paddr = ppn | offset;

  assert(paddr == vaddr);

  return paddr;
}

同样定义了一个宏提取地址和页表项的信息。

其过程在 Sv32 分页方案中已经阐述的十分清楚了……

这里的思维难点是对物理内存的读取是通过 paddr_read 进行，而非直接指针解引用。需要注意 NEMU 本质上是一个 64 位程序，其中模拟了一个 32 位的 CPU，内存从 0x80000000 开始……

别忘记乘 4，这里的 PTE 类型只是一个无符号整数，失去了指针的加成……

请务必使用 assertion 检查页目录项和页表项的 valid 位，还可以假装进行权限检查……

目前地址转换结果 pa 必定与 va 相同……

似乎没有完全遵循 NEMU ISA API 中的说明……

最后修改 vaddr.c：

word_t vaddr_ifetch_or_read(vaddr_t addr, int len, int type) {
  int flag = isa_mmu_check(addr, len, type);
  paddr_t paddr = addr;
  switch (flag) {
    case MMU_DIRECT:
        // do nothing
        break;
    case MMU_TRANSLATE:
        paddr = isa_mmu_translate(addr, len, type); // assert in isa_mmu_translate
        break;
    case MMU_FAIL:
        assert(0);
  }
  return paddr_read(paddr, len);
}

word_t vaddr_ifetch(vaddr_t addr, int len) {
  return vaddr_ifetch_or_read(addr, len, MEM_TYPE_IFETCH);
}

word_t vaddr_read(vaddr_t addr, int len) {
  return vaddr_ifetch_or_read(addr, len, MEM_TYPE_READ);
}

void vaddr_write(vaddr_t addr, int len, word_t data) {
  int flag = isa_mmu_check(addr, len, MEM_TYPE_WRITE);
  paddr_t paddr = addr;
  switch (flag) {
    case MMU_DIRECT:
        // do nothing
        break;
    case MMU_TRANSLATE:
        paddr = isa_mmu_translate(addr, len, MEM_TYPE_WRITE); // assert in isa_mmu_translate
        break;
    case MMU_FAIL:
        assert(0);
  }
  paddr_write(paddr, len, data);
}

利用上述两个 API，对虚拟地址访问的函数进行一些修改……

Debug

发现有函数在修改页表项，经过排查发现是 klib 中的 malloc，调用轨迹为 loader -> malloc：

static void init_addr() {
  addr = (void *)ROUNDUP(heap.start + 0x30000, 8); // for page
  is_init_addr = true;
}

void *malloc(size_t size) {
  if (!is_init_addr) init_addr();
  size = (size_t)ROUNDUP(size, 8);
  // printf("[malloc addr]: %p\n", addr);
  char *old = addr;
  addr += size;
  assert((uintptr_t)heap.start <= (uintptr_t)addr && (uintptr_t)addr < (uintptr_t)heap.end);
  for (uint64_t *p = (uint64_t *)old; p != (uint64_t *)addr; p ++) {
    *p = 0;
  }
  return old;
}

在修改前 malloc 是从 heap.start 开始分配内存的，也就是和页表在同一起跑线……

观察 map 过程中空闲页面的变化：

[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,34,init_mm] free physical pages starting from 0x805c0000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c1000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c2000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c3000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c4000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c5000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c6000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c7000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c8000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805c9000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805ca000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805cb000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805cc000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805cd000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805ce000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805cf000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d0000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d1000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d2000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d3000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d4000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d5000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d6000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d7000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d8000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805d9000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805da000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805db000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805dc000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805dd000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805de000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805df000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805e0000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805e1000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805e2000
[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,7,new_page] free physical pages starting from 0x805e3000

强行加了 0x30000 就可以弥补了……

后期应该需要进一步调整……

地址转换的踪迹 - vmtrace

在 isa_mmu_translate 中添加 Log，略……

注意区分下面的两种 trace：

观察访问内存地址转换：使用 vmtrace，重定向标准输出
观察创建页表地址转换：去掉 map 中 printf 的注释（或类似 strace 定义宏 ptetrace），重定向标准错误

在分页机制上运行用户进程

编译 Navy 应用程序的时候需要为 make 添加 VME=1 的参数，这样就可以将应用程序的链接地址改为 0x40000000。

make update VME=1

总结一下所需要修改的地方：

在加载用户进程之前为其创建地址空间，并在 __am_asm_trap 中切换地址空间
loader() 在获取用户程序的大小之后，以页为单位进行加载，并映射到用户进程的虚拟地址空间中
将 new_page() 申请得到的用户栈映射到用户进程的虚拟地址空间中
将 mm_brk() 中新申请的堆区映射到虚拟地址空间中

虽然看起来内容不多，但细节颇多，下面一一分析。

用户地址空间

由于地址空间是进程相关的，我们将 AddrSpace 结构体作为 PCB 的一部分。这样以后，我们只需要在 context_uload() 的开头调用 protect()，就可以实现地址空间的创建。

目前这个地址空间除了内核映射之外就没有其它内容了。

void protect(AddrSpace *as) {
  PTE *updir = (PTE*)(pgalloc_usr(PGSIZE));
  as->ptr = updir;
  as->area = USER_SPACE;
  as->pgsize = PGSIZE;
  // map kernel space
  memcpy(updir, kas.ptr, PGSIZE);
}

内核映射的作用是定位已有的页目录和页表项，因为页表对于内核和用户而言是共用的……

为了让这一地址空间生效，我们还需要将它落实到 MMU 中。具体地，我们希望在 CTE 恢复进程上下文的时候来切换地址空间。为此，我们需要将进程的地址空间描述符指针 as->ptr 加入到上下文中。

我们需要：

修改 ucontext() 的实现，在创建的用户进程上下文中设置地址空间描述符指针
在 __am_irq_handle() 的开头调用 __am_get_cur_as()，来将当前的地址空间描述符指针保存到上下文中
在 __am_irq_handle() 返回前调用 __am_switch() 来切换地址空间，将被调度进程的地址空间落实到 MMU 中

void __am_get_cur_as(Context *c) {
  c->pdir = (vme_enable ? (void *)get_satp() : NULL);
}

void __am_switch(Context *c) {
  if (vme_enable && c->pdir != NULL) {
    set_satp(c->pdir);
  }
}

这里需要注意 __am_get_cur_as 和 __am_switch 在 __am_irq_handle 的位置。具体的：

sp 减去 CONTEXT_SIZE，保存寄存器之后，调用 __am_get_cur_as

  addi sp, sp, -CONTEXT_SIZE

  MAP(REGS, PUSH)

  mv a0, sp
  jal __am_get_cur_as

恢复寄存器之前，调用 __am_switch

  mv a0, sp
  jal __am_switch

  MAP(REGS, POP)

  addi sp, sp, CONTEXT_SIZE

  mret

下面是 Debug 过程……

让 ftrace 同时追踪 Nanos-lite 和用户程序的函数调用……

用冒号分割参数中的两个 ELF 文件路径，使用 strtok 解析即可，其余部分几乎不变：
/home/vgalaxy/ics2021/nemu/build/riscv32-nemu-interpreter -b -l /home/vgalaxy/ics2021/nanos-lite/build/nemu-log.txt --elf=/home/vgalaxy/ics2021/nanos-lite/build/nanos-lite-riscv32-nemu.elf:/home/vgalaxy/ics2021/navy-apps/tests/dummy/build/dummy-riscv32 /home/vgalaxy/ics2021/nanos-lite/build/nanos-lite-riscv32-nemu.bin
发现是寄存器的保存和恢复位置有问题……

还有一处细节是地址空间描述符指针在上下文中的位置。PA3 中曾提到地址空间信息与 0 号寄存器共用存储空间，然而 Context 中 pdir 是单独的一个成员……

用户程序加载

以页为单位加载。这里需要考虑虚拟地址是否对齐：

#ifdef HAS_VME
    uintptr_t code_max_page_va_base = 0;
#endif
    for (int i = 0; i < program_header_number; ++i) {
      Elf_Phdr ent;
      fs_lseek(fd, program_header_index + program_header_length * i, SEEK_SET);
      fs_read(fd, &ent, sizeof(Elf_Phdr));

      uintptr_t type = ent.p_type;

      if (type == PT_LOAD) {
          uintptr_t offset = ent.p_offset;
          uintptr_t virtAddr = ent.p_vaddr;
          uintptr_t fileSiz = ent.p_filesz;
          uintptr_t memSiz = ent.p_memsz;
          uintptr_t flags = ent.p_flags;

          Log("offset: 0x%08x, virtAddr: 0x%08x, fileSiz: 0x%08x, memSiz: 0x%08x, flags: 0x%08x", offset, virtAddr, fileSiz, memSiz, flags);

#ifdef HAS_VME
          if (flags == (PF_R | PF_X)) { // code
              uintptr_t code_break = virtAddr + memSiz;
              if (code_break % PGSIZE == 0) code_max_page_va_base = code_break - PGSIZE;
              else code_max_page_va_base = (uintptr_t) ROUNDDOWN(code_break, PGSIZE);
          }

          if (flags == (PF_R | PF_W)) { // data
              load_file_break = virtAddr + memSiz; // for user heap page base
              assert(code_max_page_va_base != 0);
              assert(virtAddr > code_max_page_va_base); // assume code and data are not on the same page
              Log("code_max_page_va_base: %p, data_page_va_base: %p", code_max_page_va_base, virtAddr);
          }

          if (virtAddr % PGSIZE == 0) { // 4KB alignment
              unsigned int page_count = memSiz / PGSIZE; // page_count = ceil(memSiz / PGSIZE) - 1
              if (page_count * PGSIZE == memSiz) page_count--; // for ceil

              unsigned int page_count_file = fileSiz / PGSIZE;
              if (page_count_file * PGSIZE == fileSiz) page_count--; // for ceil

              for (unsigned int i = 0; i <= page_count_file; ++i) {
                  size_t read_bytes = PGSIZE;
                  if (i == page_count_file) read_bytes = (fileSiz % PGSIZE == 0) ? PGSIZE : (fileSiz % PGSIZE);

                  void * paddr = new_page(1);
                  paddr -= PGSIZE;
                  memset(paddr, 0, PGSIZE);

                  void * vaddr = (void *) (virtAddr + i * PGSIZE);

                  assert(fs_lseek(fd, offset + i * PGSIZE, SEEK_SET) >= 0);
                  assert(fs_read(fd, paddr, read_bytes) >= 0);

                  map(&pcb->as, vaddr, paddr, 0);
              }

              if (page_count > page_count_file) {
                  for (unsigned int i = page_count_file + 1; i <= page_count; ++i) {
                      void * paddr = new_page(1);
                      paddr -= PGSIZE;
                      memset(paddr, 0, PGSIZE);

                      void * vaddr = (void *) (virtAddr + i * PGSIZE);

                      map(&pcb->as, vaddr, paddr, 0);
                  }
              }
          } else {
              uintptr_t gap = virtAddr - (uintptr_t) ROUNDDOWN(virtAddr, PGSIZE);

              unsigned int page_count = (gap + memSiz) / PGSIZE;
              if (page_count * PGSIZE == (gap + memSiz)) page_count--; // for ceil

              unsigned int page_count_file = (gap + fileSiz) / PGSIZE;
              if (page_count_file * PGSIZE == (gap + fileSiz)) page_count--; // for ceil

              for (unsigned int i = 0; i <= page_count_file; ++i) {
                  if (i == 0) { // fill the gap
                      size_t read_bytes = PGSIZE - gap;

                      void * paddr = new_page(1);
                      paddr -= PGSIZE;
                      memset(paddr, 0, PGSIZE);

                      void * vaddr = (void *) (virtAddr - gap + i * PGSIZE);

                      assert(fs_lseek(fd, offset + i * PGSIZE, SEEK_SET) >= 0);
                      assert(fs_read(fd, paddr + gap, read_bytes) >= 0);

                      map(&pcb->as, vaddr, paddr, 0);
                  } else {
                      size_t read_bytes = PGSIZE;
                      if (i == page_count_file) read_bytes = ((gap + fileSiz) % PGSIZE == 0) ? PGSIZE : ((gap + fileSiz) % PGSIZE);

                      void * paddr = new_page(1);
                      paddr -= PGSIZE;
                      memset(paddr, 0, PGSIZE);

                      void * vaddr = (void *) (virtAddr - gap + i * PGSIZE);

                      assert(fs_lseek(fd, offset + (i - 1) * PGSIZE + (PGSIZE - gap), SEEK_SET) >= 0);
                      assert(fs_read(fd, paddr, read_bytes) >= 0);

                      map(&pcb->as, vaddr, paddr, 0);
                  }
              }

              if (page_count > page_count_file) {
                  for (unsigned int i = page_count_file + 1; i <= page_count; ++i) {
                      void * paddr = new_page(1);
                      paddr -= PGSIZE;
                      memset(paddr, 0, PGSIZE);

                      void * vaddr = (void *) (virtAddr - gap + i * PGSIZE);

                      map(&pcb->as, vaddr, paddr, 0);
                  }
              }
          }
#else
...

一般而言，代码段是对齐的，而数据段在代码段之后，可能是不对齐的，如仙剑奇侠传……

这里还假设代码段和数据段不在同一页面内……

使用局部变量 code_max_page_va_base 指示代码段最大页面的对应的虚拟内存的基址……

注意对页面数量的分析。

这里拆成了两个部分，前面是 fileSiz 对应的页面，后面是 memSiz 对应的页面。

若两个页面数相同，在 memset 的过程中已经为 memSiz 部分清零了。否则单独为 memSiz 对应的页面进行映射。

这里还定义了全局变量 code_break 指示数据段的末尾，在用户堆的部分需要用到……

另外，既然每一次读取的文件大小都是固定的，我们也就不需要在操作系统层调用 malloc 了，上面强行加 0x30000 的操作也就不需要了。换个角度来说，操作系统是不能调用 malloc 的，否则会与 VME 机制冲突。

请务必区分操作系统的动态内存分配 (AM 程序) 和用户程序的动态内存分配 (Navy 程序)

用户栈

我们把用户栈的虚拟地址安排在用户进程虚拟地址空间的末尾，可以通过 as.area.end 来得到末尾的位置，然后把用户栈的物理页映射到 [as.area.end - 32KB, as.area.end) 这段虚拟地址空间。

修改 context_uload 即可：

  // get the address of user stack
  void *ustack_end = new_page(8);
#ifdef HAS_VME
  void *ustack_start = ustack_end - 8 * PGSIZE;
  void *ustack_start_vaddr = pcb->as.area.end - 8 * PGSIZE;
  for (int i = 0; i < 8; ++i)
      map(&pcb->as, ustack_start_vaddr + i * PGSIZE, ustack_start + i * PGSIZE, 0);
#endif

用户堆

为了识别堆区中的哪些空间是新申请的，我们还需要记录堆区的位置。由于每个进程的堆区使用情况是独立的，我们需要为它们分别维护堆区的位置，因此我们在 PCB 中添加成员 max_brk，来记录 program break 曾经达到的最大位置。

引入 max_brk 是为了简化实现：我们可以不实现堆区的回收功能，而是只为当前新 program break 超过 max_brk 部分的虚拟地址空间分配物理页。

这里有一个非常隐蔽的问题，那就是 brk 用 _end 初始化堆区时，可能 _end 与数据段之间会有一段空隙。为此我们导出了之前定义的变量 code_break，并判断两者是否在同一页面内：

#ifdef HAS_VME
extern PCB *current;
extern uintptr_t load_file_break;
#endif

/* The brk() system call handler. */
int mm_brk(uintptr_t brk) {
#ifdef HAS_VME
  if (current->max_brk == 0) {
    Log("load_file_break: %p", (void *) load_file_break);
    void * va_base;

    if (load_file_break / PGSIZE == brk / PGSIZE) {
      Log("uheap_va before ROUNDUP: %p", (void *) brk);
      va_base = (void *) ROUNDUP(brk, PGSIZE);
      Log("uheap_va after ROUNDUP: %p", va_base);

      // do nothing
      current->max_brk = (uintptr_t) (va_base);
      Log("current->max_brk: %p", (void *) current->max_brk);

    } else {
      Log("uheap_va before ROUNDDOWN: %p", (void *) brk);
      va_base = (void *) ROUNDDOWN(brk, PGSIZE);
      Log("uheap_va after ROUNDDOWN: %p", va_base);

      void * pa_base = pg_alloc(PGSIZE);
      map(&current->as, va_base, pa_base, 0);

      current->max_brk = (uintptr_t) (va_base + PGSIZE);
      Log("current->max_brk: %p", (void *) current->max_brk);
    }

    return 0;
  }

  if (brk > current->max_brk) {
    unsigned int gap = brk - current->max_brk;
    unsigned int page_count = gap / PGSIZE;
    if (page_count * PGSIZE == gap) page_count--;
    for (int i = 0; i <= page_count; ++i) {
      void * va_base = (void *) (current->max_brk + i * PGSIZE);
      void * pa_base = pg_alloc(PGSIZE);
      map(&current->as, va_base, pa_base, 0);
    }
    current->max_brk += (page_count + 1) * PGSIZE;
    Log("current->max_brk: %p", (void *) current->max_brk);
  } else {
    Log("current->max_brk: %p", (void *) current->max_brk);
  }
  return 0;
#else
  return 0;
#endif
}

若在同一页面，就不需要再分配了……

下面是 Debug 的过程……

反复使用 vmtrace 和 ptetrace 观察地址转换的细节……

还发现在进行重定向的时候有些内容仍然会显示在屏幕上……

标准输出流和标准错误流中都有调试信息……

其余细节

不能在用户栈里面创建用户进程上下文

这是一道蓝框题，本来是想直接略过的……

之前曾提及，ucontext() 的行为是在内核栈 kstack 中创建用户进程上下文……

若要在用户栈里面创建，要考虑上下文的位置，栈顶存放了用户进程的参数，上下文若紧接着存放，可能会被覆写……

yield

在运行 PAL 的过程中发现，若在访问设备的过程不调用 yield，在某一时刻当前进程控制块会被覆写，从而导致访存错误：

[/home/vgalaxy/ics2021/nanos-lite/src/mm.c,37,mm_brk] current: 0x81bab000, current->cp: 0x6, &current->as: 0x81bab004, current->as.ptr: 0x6, current->max_brk: 0x0
...
[src/isa/riscv32/system/mmu.c:33 isa_mmu_translate] [WRONG]
[src/isa/riscv32/system/mmu.c:34 isa_mmu_translate] [VA]: 0x00000406
[src/isa/riscv32/system/mmu.c:35 isa_mmu_translate] [DIR TARGET]: 0x81c01000
[src/isa/riscv32/system/mmu.c:36 isa_mmu_translate] [DIR TARGET ITEM]: 0x00000000

在操作系统内陷后，上下文会切换到用户程序，即：

current: 0x81bab000, current->cp: 0x81bb2f70, &current->as: 0x81bab004, current->as.ptr: 0x81c01000, current->max_brk: 0x0
Context switch: 0x81bb2f70

由于在访问设备的过程不调用 yield，进程控制块的上下文所在的地址不再变化。

若在访问设备的过程调用 yield，其变化如下：

current: 0x81bab000, current->cp: 0x81bb2f70, &current->as: 0x81bab004, current->as.ptr: 0x81c01000, current->max_brk: 0x0
Context switch: 0x81bb2f70

current: 0x81bab000, current->cp: 0x81c72cd8, &current->as: 0x81bab004, current->as.ptr: 0x81c01000, current->max_brk: 0x40358000
Context switch: 0x81c72cd8

current: 0x81bab000, current->cp: 0x81c72cd8, &current->as: 0x81bab004, current->as.ptr: 0x81c01000, current->max_brk: 0x40358000
Context switch: 0x81c72cd8
...

注意到新的上下文所在的地址在用户栈中。

那为什么进程控制块就不会被覆写呢……

不调用 yield，多输出一些调试信息似乎也可以……

不支持执行其他程序

在 exit 的实现中调用 halt() 结束系统的运行，而非 sys_execve 其他程序……

也就是说目前不支持执行其他程序……

修改调度代码

always select pcb[0] as the new process

物理内存分析

从物理内存的堆区开始，依次存放了：

内核地址空间
物理地址恒等映射生成的页表和页表项
用户地址空间
用户程序
用户栈
用户堆

注意在映射 用户程序、用户栈、用户堆 的过程中可能产生新的的页表和页表项，所以之间会有一定间隙

native

EVENT_PAGEFAULT

give up DiffTest and AM native

可以研究一下其实现，位于 abstract-machine/am/src/native/vme.c

支持虚存管理的多道程序

用户进程和内核线程并发执行

我们首先让运行在分页机制上的用户进程和内核线程并发执行。

内核线程和用户进程最大的不同，就是它没有用户态的地址空间，内核线程的代码、数据和栈都是位于内核的地址空间。

由于 AM 创建的所有虚拟地址空间都会包含内核映射，所以我们只要在 kcontext() 中将上下文的地址空间描述符指针设置为 NULL，来进行特殊的标记，等到将来在 __am_irq_handle() 中调用 __am_switch() 时，如果发现地址空间描述符指针为 NULL，就不进行虚拟地址空间的切换。

在调试的时候发现上下文保存的内容（地址空间）会被修改，发现是因为在第一次切换到内核线程和用户进程时错误的将 PC 加上了 4，导致程序的第一条指令没有执行。对于内核线程而言，第一条指令为：

80001f68:       fe010113                addi    sp,sp,-32

这导致了内核栈中保存的上下文信息被修改……

于是我们只要在 ucontext 和 kcontext 中将入口地址减去 4 就可以了……

另外在调试的时候研究了一下进程控制块在物理内存中的存储：

1、初始化

&pcb[0]: 0x81bab000, (&pcb[0])->cp: 0x81bb2f70, (&pcb[0])->as: 0x81bddfa0, &((&pcb[0])->as): 0x81bab004, (&pcb[0])->as.ptr: 0x0, &((&pcb[0])->as.ptr): 0x81bab010, (&pcb[0])->max_brk: 0x0

&pcb[1]: 0x81bb3000, (&pcb[1])->cp: 0x81bbaf70, (&pcb[1])->as: 0x81bddfa0, &((&pcb[1])->as): 0x81bb3004, (&pcb[1])->as.ptr: 0x81c01000, &((&pcb[1])->as.ptr): 0x81bb3010, (&pcb[1])->max_brk: 0x0

2、第一次调度内核线程

&pcb[0]: 0x81bab000, (&pcb[0])->cp: 0x81bb2f70, (&pcb[0])->as: 0x81bddee0, &((&pcb[0])->as): 0x81bab004, (&pcb[0])->as.ptr: 0x0, &((&pcb[0])->as.ptr): 0x81bab010, (&pcb[0])->max_brk: 0x0
&pcb[1]: 0x81bb3000, (&pcb[1])->cp: 0x81bbaf70, (&pcb[1])->as: 0x81bddee0, &((&pcb[1])->as): 0x81bb3004, (&pcb[1])->as.ptr: 0x81c01000, &((&pcb[1])->as.ptr): 0x81bb3010, (&pcb[1])->max_brk: 0x0

发现 (&pcb[0])->as 和 (&pcb[1])->as 是一样的，并且发生了变化

3、第一次调度用户进程

&pcb[0]: 0x81bab000, (&pcb[0])->cp: 0x81bb2f50, (&pcb[0])->as: 0x81bb2ee0, &((&pcb[0])->as): 0x81bab004, (&pcb[0])->as.ptr: 0x0, &((&pcb[0])->as.ptr): 0x81bab010, (&pcb[0])->max_brk: 0x0
&pcb[1]: 0x81bb3000, (&pcb[1])->cp: 0x81bbaf70, (&pcb[1])->as: 0x81bb2ee0, &((&pcb[1])->as): 0x81bb3004, (&pcb[1])->as.ptr: 0x81c01000, &((&pcb[1])->as.ptr): 0x81bb3010, (&pcb[1])->max_brk: 0x0

变化同上

4、第二次调度内核线程

&pcb[0]: 0x81bab000, (&pcb[0])->cp: 0x81bb2f50, (&pcb[0])->as: 0x81c72c78, &((&pcb[0])->as): 0x81bab004, (&pcb[0])->as.ptr: 0x0, &((&pcb[0])->as.ptr): 0x81bab010, (&pcb[0])->max_brk: 0x0
&pcb[1]: 0x81bb3000, (&pcb[1])->cp: 0x81c72ce8, (&pcb[1])->as: 0x81c72c78, &((&pcb[1])->as): 0x81bb3004, (&pcb[1])->as.ptr: 0x81c01000, &((&pcb[1])->as.ptr): 0x81bb3010, (&pcb[1])->max_brk: 0x40358000

用户进程的上下文来到了用户栈中，并且有了 max_brk

总结来说，内核线程的地址空间总为 NULL

需要区分指针和指向指针的指针，

例如：

想观察 (&pcb[1])->as.ptr 是否被修改（本身为指针），就应该在外面再套一层取地址操作符

使用 %p printf 结构体并不是打印结构体变量的地址，若想打印，就应该在外面再套一层取地址操作符

并发执行多个用户进程

TODO

抢占多任务

记录一下 commit

c03ac8ac19d885e839703fb6abd9f61fe9d1916f

来自外部的声音

多道程序成功地实现了任务的并发执行，但这种并发不一定是公平的。如果一个进程长时间不触发 I/O 操作，多道程序系统并不会主动将控制权切换到其它进程，这样其它进程就得不到运行的机会。

如果要用于交互式场景，系统就要以一定的频率在所有进程之间来回切换，保证每个进程都能及时得到响应，这就是分时多任务。从触发上下文切换的角度看，分时多任务可以分成两类。

第一类是协同多任务，它的工作方式基于一个约定：用户进程周期性地主动让出 CPU 的控制权，从而让其它进程得到运行的机会。这件事需要操作系统提供一个特殊的系统调用，那就是我们在 PA3 中实现的 SYS_yield。在 PA3 中看似没什么用的 SYS_yield，其实是协同多任务操作系统中上下文切换的基石。
- 如果有一个恶意进程故意不遵守这个约定，不调用 SYS_yield，或者无意陷入了死循环，整个系统将会被这个进程独占。
第二类是抢占多任务，它基于硬件中断（通常是时钟中断）强行进行上下文切换，让系统中的所有进程公平地轮流运行。
- 中断控制器负责转发设备的中断请求
- CPU 每次执行完一条指令的时候，都会看看 INTR 引脚，看是否有设备的中断请求到来
  - 一个例外的情况就是 CPU 处于关中断状态，此时即使 INTR 引脚为高电平，CPU 也不会响应中断
  - 在 riscv32 中，如果 mstatus 中的 MIE 位为 0，则 CPU 处于关中断状态
嵌套中断需要使用堆栈保存中断上下文，我们在 PA 中暂不考虑这一点

NEMU Layer

在 NEMU 中，我们只需要添加时钟中断这一种中断就可以了。由于只有一种中断，我们也不需要通过中断控制器进行中断的管理，直接让时钟中断连接到 CPU 的 INTR 引脚即可。

时钟中断通过 nemu/src/device/timer.c 中的 timer_intr() 触发，每 10ms 触发一次。触发后，会调用 dev_raise_intr() 函数。

    timer_now = get_time();
    if (timer_now - timer_prev > 100000) { // 10 ms
      extern void dev_raise_intr();
      dev_raise_intr();
      timer_prev = get_time();
    }

这里在 for 循环前定义了两个变量 timer_now 和 timer_prev

注意时间单位为 us

还需要完成下述工作：

在 CPU 结构体中添加一个 bool 成员 INTR

略

在 dev_raise_intr() 中将 INTR 引脚设置为高电平

略

在 cpu_exec() 中 for 循环的末尾添加轮询 INTR 引脚的代码，每次执行完一条指令就查看是否有硬件中断到来

    word_t intr = isa_query_intr();
    if (intr != INTR_EMPTY) {
      cpu.pc = isa_raise_intr(intr, cpu.pc - 4); // attention for minus 4
    }

注意这里显式的减去 4，因为 AM 中的 __am_asm_trap 会将中断上下文中的 epc 加上 4

实现 isa_query_intr() 函数，在 nemu/src/isa/$ISA/system/intr.c 中定义：

#define IRQ_TIMER 0x80000007  // for riscv32
#define EVENT_IRQ_TIMER 5     // refer to am/include/am.h

word_t isa_query_intr() {
    if (cpu.INTR && get_mstatus_mie()) { // enable interrupt if MIE in mstatus is 1
        cpu.INTR = false;
        return IRQ_TIMER;
    }
    return INTR_EMPTY; // ((word_t) -1)
}

通过 RTFM 可知，MIE 为 mstatus 的第 3 位（从低到高，从 0 开始），而 MPIE 为 mstatus 的第 7 位，为此定义一些宏：

#define get_mstatus_field(offset)      ((*s0 >> offset) & 0x1)
#define set_mstatus_field(offset, val) ((val == 0) ? (*s0 &= (~(1 << offset))) : (*s0 |= (1 << offset)))
#define get_mstatus_mie()              get_mstatus_field(3)
#define set_mstatus_mie(val)           set_mstatus_field(3, val)
#define get_mstatus_mpie()             get_mstatus_field(7)
#define set_mstatus_mpie(val)          set_mstatus_field(7, val)

注意这里 set_mstatus_field 中的设置位和清空位

修改 isa_raise_intr() 中的代码，让处理器进入关中断状态

即将 mstatus.MIE 保存到 mstatus.MPIE 中，然后将 mstatus.MIE 位置为 0

#define IRQ_TIMER 0x80000007  // for riscv32
#define EVENT_IRQ_TIMER 5     // refer to am/include/am.h

word_t isa_raise_intr(word_t NO, vaddr_t epc) {
  *s1 = epc;
  *s2 = (NO == IRQ_TIMER) ? EVENT_IRQ_TIMER : NO;

  Log("[isa_raise_intr before] mie: %u, mpie: %u", get_mstatus_mie(), get_mstatus_mpie());

  set_mstatus_mpie(get_mstatus_mie());
  set_mstatus_mie(0);

  Log("[isa_raise_intr after] mie: %u, mpie: %u", get_mstatus_mie(), get_mstatus_mpie());

  return *t0;
}

只有 ecall 指令和轮询 INTR 引脚处会调用 isa_raise_intr

而 ecall 指令传递的 NO 已经与 am/include/am.h 相匹配了

// An event of type @event, caused by @cause of pointer @ref
typedef struct {
  enum {
    EVENT_NULL = 0,
    EVENT_YIELD, EVENT_SYSCALL, EVENT_PAGEFAULT, EVENT_ERROR,
    EVENT_IRQ_TIMER, EVENT_IRQ_IODEV,
  } event;
  uintptr_t cause, ref;
  const char *msg;
} Event;

所以这里需要额外对 IRQ_TIMER 进行转换

不理解 IRQ_TIMER 的设计

修改 mret 指令的实现

注意 __am_asm_trap 的最后一条指令便是 mret

将 mstatus.MPIE 还原到 mstatus.MIE 中，然后将 mstatus.MPIE 位置为 1

def_EHelper(mret) {
  rtl_li(s, &s->dnpc, *s1);

    Log("[mret before] mie: %u, mpie: %u", get_mstatus_mie(), get_mstatus_mpie());

    set_mstatus_mie(get_mstatus_mpie());
    set_mstatus_mpie(1);

    Log("[mret after] mie: %u, mpie: %u", get_mstatus_mie(), get_mstatus_mpie());

#ifdef CONFIG_ETRACE
    Log("mret at " FMT_WORD ", mstatus: " FMT_WORD ", mepc: " FMT_WORD ", mcause: " FMT_WORD, s->pc, *s0, *s1, *s2);
#endif
}

也就是说在 __am_asm_trap 的过程中 CPU 处于关中断状态

AM Layer

在 CTE 中添加时钟中断的支持，将时钟中断打包成 EVENT_IRQ_TIMER 事件

也就是修改 __am_irq_handle，添加一个分支：

      case EVENT_IRQ_TIMER: ev.event = EVENT_IRQ_TIMER; break;

修改 kcontext() 和 ucontext() 的代码

在构造上下文的时候，设置正确中断状态，使得将来恢复上下文之后 CPU 处于开中断状态

只需要设置 MPIE 即可，在切换到内核线程或用户进程时便会将 mstatus.MPIE 还原到 mstatus.MIE 中

  base->mstatus = 1 << 7; // set MPIE in mstatus

OS Layer

收到 EVENT_IRQ_TIMER 事件之后，调用 schedule() 来强制当前进程让出 CPU

修改 do_event，添加一个分支：

  case EVENT_IRQ_TIMER:
        Log("EVENT_IRQ_TIMER");
    c = schedule(c);
    Log("Context switch: %p", c);
    assert(c != NULL);
        break;

其事件的处理与 EVENT_YIELD 完全一致

同时也可以去掉我们之前在设备访问中插入的 yield() 了

测试

可能是性能受限，需要将中断时间从 10ms 提升到 100ms，否则处理不过来……

在 OS 陷入内核后触发 yield，从 boot 切换到内核线程：

[isa_raise_intr before] mie: 0, mpie: 0
[isa_raise_intr after] mie: 0, mpie: 0
...
[mret before] mie: 0, mpie: 1
[mret after] mie: 1, mpie: 1

可以发现 mpie 成功设置为 1

之后内核线程与用户进程的切换大抵如下：

[isa_raise_intr before] mie: 1, mpie: 1
[isa_raise_intr after] mie: 0, mpie: 1
...
[mret before] mie: 0, mpie: 1
[mret after] mie: 1, mpie: 1

注意有些 Log 记录是被 syscall 事件或 yield 事件触发，而非时钟中断事件

中断和用户进程初始化

我们知道，用户进程从 Navy 的 _start 开始运行，并且在 _start 中设置正确的栈指针。如果在用户进程设置正确的栈指针之前就到来了中断，我们的系统还能够正确地进行中断处理吗？

.globl  _start
_start:
  move s0, zero

  # set heap.end to the stack pointer register
  mv sp, a0

  jal call_main

理论上是可以正确处理的，第一次切换到用户进程，__am_asm_trap 恢复 mepc，mret 后开中断，执行 _start 第二条语句前时钟中断，此时栈指针仍然存放在 GPRx 中，一同保存在内核栈的用户进程上下文中，待到再次切换到用户进程，用户进程设置了正确的栈指针，此后用户进程上下文的信息便保存在用户栈中。

可以放心的是，用户进程上下文的保存和恢复不会破坏用户进程的参数，因为用户进程的参数存放在初始用户栈指针的高地址处。

基于时间片的进程调度

在抢占多任务操作系统中，由于时钟中断以固定的速率到来，时间被划分成长度均等的时间片，这样系统就可以进行基于时间片的进程调度了。

我们可以修改 schedule() 的代码，给仙剑奇侠传分配更多的时间片，使得仙剑奇侠传调度若干次，才让 hello 内核线程调度 1 次。

难以预测的状态机

为了对中断的行为进行建模，我们对 fex() 函数的定义进行扩展：除了判断当前状态是否需要抛出异常，如果当前处理器处于开中断状态，还需要判断是否有中断到来。

中断给计算机系统带来的不确定性可以说是一把双刃剑：

比如 GNU/Linux 内核会维护一个 entropy pool，用于收集系统中的熵。每当中断到来的时候，就会给这个 pool 添加一些熵。通过这些熵，我们就可以生成真正的随机数了，/dev/random 就是这样做的。
中断的存在也不得不让程序在一些问题的处理上需要付出额外的代价。如中断给并发的时域耦合提出了挑战：
- 用户进程之间可能会有共享变量
- 用户进程并发地执行系统调用
- 如果中断到来的时机不一样（你想调试它的时候），bug 却不被触发了，这种 bug 又叫 Heisenbug

ICS PA 4

TOC

ICS PA 4

多道程序

上下文切换

基本原理

进程控制块

内核线程

线程 / 进程调度

剩余工作

内核线程的参数

用户进程

debug

context_uload

用户进程的参数

loader

argc / argv / envp

SYS_execve

Busybox

虚存管理

程序和内存位置

分段与分页

分段

分页

状态机视角下的虚存管理机制

TLB - 地址转换的加速

内存初探

物理内存

虚拟内存

将虚存管理抽象成 VME

在分页机制上运行 Nanos-lite

Sv32 分页方案

实现

OS Layer

AM Layer

NEMU Layer

Debug

地址转换的踪迹 - vmtrace

在分页机制上运行用户进程

用户地址空间

用户程序加载

用户栈

用户堆

其余细节

支持虚存管理的多道程序

用户进程和内核线程并发执行

并发执行多个用户进程

抢占多任务

来自外部的声音

NEMU Layer

AM Layer

OS Layer

测试

中断和用户进程初始化

基于时间片的进程调度

难以预测的状态机