Skip to main content

PA4

MallocSimenonsDecember 27, 2024About 11 minics 2nd roundPA

PA4

Overview

在 PA3 中，实现了中断机制，并借此实现了系统调用，完成了丰富的应用程序库。但是，直到目前为止，我们都是串行执行一个程序，能否并行执行呢？PA4 解决的正是这个问题，解决方法包括但不限于：进程切换、虚存管理。

Warning

前排提示：本 blog 既不是心得，也不是攻略，也不包含任何实现代码。如果你对 PA4 框架代码的设计方法感到好奇、对其中涉及到的概念缺乏清晰直观的认识，那么你可能会有所收获。

Comprehensions

栈

有哪些栈？

实际上存在三个栈的区域：

  • nanos 运行所使用的栈：这个栈是 am 定义的；nanos 是第一个被加载运行的“程序”，所以在一开始，使用的栈就是这个；
  • pcb 中的内核栈：这个栈是分配在静态内存区的，和 nanos 所使用的并不同，但讲义将前两个合称为静态内存区
  • 用户栈：在堆上分配的 32 KB 内存；一开始固定为从 heap.end 开始，后来改用 new_page 进行分配，以支持多用户进程

栈之间怎么切换？

在 trap.S 中，实际上并没有对栈指针 sp 进行保存、恢复。切换栈的过程，其实在 mv sp, a0 中。回忆进程调度的过程，schedule() 返回被调度进程的 pcb->cp ，也就是上下文指针，而上下文正是保存在栈上的，mv sp, a0 不仅是为了指向被调度进程的上下文，进而恢复，更是切换栈的过程。

pcb->cp 不是在内核栈空间吗？那怎么可能让用户进程使用我们约定的用户栈呢？

pcb->cp 虽然保存在内核栈里，但它是个指针，指向上一次保存上下文的栈地址，所以正常运行过程中，其实会指向用户栈

用户进程的初始化稍有不同。因为 trap.S 不会恢复上下文中的栈指针，只会单纯地将上下文指针赋给 sp，所以用户进程首次被调度时，其栈指针必定指向 pcb 中的内核栈。而在后续的过程中，进程的栈指针是不会切换的，所以我们需要一个另外的机制，来初始化栈指针。讲义通过上下文中的 GPRx 来完成。

另外值得注意的一点是，除了进程切换，否则栈指针都不会切换，哪怕是系统调用。这一点对后续分析 CTE 嵌套等较为重要。

nemu 的地址空间映射

  1. 内核恒等映射：PMEM (0x80000000-0x88000000) + 设备相关的地址空间；
  2. 用户程序可用的虚存范围 as.area：0x40000000-0x80000000 ，用户栈的虚存对应 [as.area.end - 32KB, as.area.end) 这段虚拟地址空间；
  3. 可用的物理内存：[heap.start, PMEM.end] ，通过 new_page 进行分配；

为什么要有内核恒等映射

首先，虽然是复制了整个一级页表，但是由于内核与用户地址刚好错开，所以这两者其实并不是覆盖关系。其次，在 loader 加载的时候，一直都在 nanos 的地址空间，也就是内核空间，问题只会出在调度用户程序运行之后。本来想的是会在使用到内核空间，例如进程切换的时候有问题，但测试发现，从 user_handler 返回，进入用户程序地址空间的下一行，准确说是 am_switch 的 ret 处，就挂了。设置完 satp，切换地址空间后，下一条指令立刻挂。

80001c98:	18079073          	csrw	satp,a5
80001c9c:	00008067          	ret

为什么呢？指令模块虽然在 nemu，但取值使用的是虚拟地址。

相应的，在监视器中，打印内存地址、监视点等，所使用的也应该是虚拟地址。毕竟总不能在 debug 用户程序时，先人肉转换到物理地址再调试吧（

从直观的角度来解释内核映射的作用：让本来就能够接触到物理地址 (0x80000000-0x88000000) 的代码能够不受虚存机制影响，照旧执行。有哪些代码是符合的呢？nanos 里的所有代码。这么做有什么好处呢？nanos 的定位是操作系统，应当能够越过虚存机制，自由地组织内存，例如在用户栈上准备参数时，可以不用转换地址。

pcb_boot 这个空 pcb 的作用？

考虑如下情形，执行 execve 的进程 A 的 pcb 被重写为 B 的 pcb，我们需要重新进入 B，这就必须有一个恢复 B 上下文的过程。首先是最直接的想法：能否在 A yield 之后直接恢复 B ？

Context* schedule(Context *prev) {
  current->cp = prev;
  current = (current == &pcb[0] ? &pcb[1] : &pcb[0]);
  return current->cp;
}

这时的 prev 在 A 的用户栈里，而我们需要在 B 的内核栈里恢复上下文。因为 A、B 的 pcb 本质上是同一个，所以，第一行会直接将 B 的 cp 覆盖掉，返回的还是 A 的 用户栈中的上下文。

紧接着的一个实际的问题是，即使我们不想直接直接恢复 B，由于此时的 current 为 A、B 的 pcb，所以只要切换进程，在 schedule 的时候一定会首先复写掉 B 准备好的 pcb 的 cp。所以我们需要一个“替死鬼”，可以任意修改它的栈指针（同时也是上下文指针）。索性让它不需要栈、不需要上下文、不执行任何内容即可。这就是 pcb_boot。

我们可以为它 kload 一个空进程，更斩草除根的方法是：如第二行所做，在第一行覆盖之后，直接不再调度它（因为它既不是 pcb[0]，也不是 pcb[1]）

Debugging

栈覆盖

先说结论：trap.S 中的 CONTEXT_SIZE 忘记改了，导致 Context->pdir 会被覆盖，以及覆盖保存在栈上的运行环境。

现象：pdir 覆盖别人，会导致 pal 中 argc 值异常，并且这个值会随着栈结构的变化而正常/不正常；pdir 自己被覆盖，会导致程序运行崩溃。

调试过程

  1. 在 pal 开头打印 argc 没问题，在 SDL_Init 之后就会被覆盖，并且覆盖值一样：0x824da000。如果 argc 的值是用寄存器传的，那我根本没法 debug，寄存器的使用是编译器决定的；如果 argc 的值是通过栈传递的（0x824da000也确实很像是一个栈上有实际含义的值）

  2. 在栈上声明变量，打印地址，发现在0x824e2f68，这并不是用户栈的地址。

    1. 修改了 GPRx 的赋值，改到用户栈空间，还是没用，甚至值也还是 0x824da000。
    2. 这个值从未在 map 中出现过，但却是 s2 寄存器的值。
    3. 这个值是用户 map 最小地址 824db000 的前一页
    4. 这个值是用户的页表地址。

sdb debug

  1. 书接上文，在刚进 main，直到跳转到 SDL_Init 之前，s2 的值为 argc = 2（所以真的是从 s2 寄存器取的值？）

  2. s2 是一个调用者保存寄存器，所以按道理调用 SDL_Init 不应该修改它。（不一定每个函数开头都要保存一次，如果当前没用，则顺延到子函数保存）如果要保存的话，只能是保存在栈上。那么只能认为是栈被破坏了？ 经过监视点判断，发现第一次出现函数进入、返回时 s2 值不同的情况，是在 __gettimeofday_ 里

    Old value = 0x2
New value = 0x824d9000
[src/cpu/cpu-exec.c:47 trace_and_difftest] 0x80001d90

>>
80001d78 <__am_get_cur_as>:
80001d78:	024ab717          	auipc	a4,0x24ab
80001d7c:	2b472703          	lw	a4,692(a4) # 824ad02c <vme_enable>
80001d80:	00000793          	li	a5,0
80001d84:	00070663          	beqz	a4,80001d90 <__am_get_cur_as+0x18>
80001d88:	180027f3          	csrr	a5,satp
80001d8c:	00c79793          	slli	a5,a5,0xc
# a5 现在是 get_satp() 的返回值，也就是 pdir
80001d90:	08f52623          	sw	a5,140(a0) # 108c <_entry_offset+0x108c>
# 所以问题就在于，c->pdir 覆盖了 gettimeofday 栈上保存的 s2
80001d94:	00008067          	ret

总结：当确定 argc 的值是从 s2 中加载之后，debug 就很容易了（对应 sdb debug）。尝试替换位置、尝试理解错误值的过程，似乎并不能指导 debug 过程，只能隐约感觉到是栈的问题，但没法进一步 debug。

或许这里应该正向 debug。

Problems

问题之：execve时，用户栈能否复用

通过上述分析, 我们得出一个重要的结论: 在加载B时, Nanos-lite使用的是A的用户栈! 这意味着在A的执行流结束之前, A的用户栈是不能破坏的. 因此heap.end附近的用户栈是不能被B复用的, 我们应该申请一段新的内存作为B的用户栈, 来让Nanos-lite把B的参数放置到这个新分配的用户栈里面.

但是：即使 heap.end 被 B 复用，也不会在 A 执行流结束之前，破坏 A 的用户栈。加载 B 的时候，只是将 GPRx 设置为 heap.end，同时 A 的 pcb 被覆盖，此时 A 的执行流就已经结束了。经过测试（exec-test）也确实是这样，覆盖 stack 的做法，可以摆脱堆区内存耗尽的问题，一直运行下去。

问题之：理解、实现错误，但能正常运行

  • bug 没有暴露 ：例如旧版实现中 vsprintf 在目标字符串开头写入 \0 的错误，因为没有使用该函数的缘故，居然在一周目中没有暴露。这次是在运行 native 时，构造哈希表查询 key 时，发现的异常。

  • 理解错误，但是无用之举： 例如在旧版实现中，在 PA4.1 中设置上下文中 sp 指针。很显然，当时就没注意到 trap.S 中没有保存、恢复栈指针，进一步，也就更不可能理解用户栈、内核栈切换的过程

  • 殊途同归 ：例如在旧版实现中，用户栈指针初始化在 nanos 的地址空间：

// pcb->cp->GPRx = (uintptr_t)ptr;
  pcb->cp->GPRx = (uintptr_t)ptr + (pcb->as.area.end - ustack_end);

虽然 nanos 地址空间中的 ptr 和 用户地址空间中的 ptr + (pcb->as.area.end - ustack_end) 其实指向的是同一片内存，但原理上不正确。

问题之：同学的用户、内核栈切换为什么能运行

要干什么： 在 __am_irq_handle 中取出 ksp 的逻辑值，进行判断，并赋值到 c->np 中。

栈切换伪代码
void __am_asm_trap() {
  c->sp = $sp;
  if (ksp != 0) {   // ksp is global
    $sp = ksp;
  }
  c->np = (ksp == 0 ? KERNEL : USER);  // np should be in Context

  ksp = 0;          // support re-entry of CTE

  // save context

  __am_irq_handle(c);

  // restore context

  if (c->np == USER) {
    ksp = $sp;
  }
  $sp = c->sp;

  return_from_trap();
}

ksp 的逻辑值存在 mscratch 中，而根据讲义内容：

__am_asm_trap:
  csrrw sp, mscratch, sp   // (1) atomically exchange sp and mscratch
  bnez sp, save_context    // (2) take the branch if we trapped from user
  csrr sp, mscratch        // (3) if we trapped from kernel, restore the original sp

save_context:

我们可以知道：在 save_context 之后，sp 的值是内核栈的指针，而 mscratch 中的值始终为 sp 旧值，也就是说，如果单纯的在 __am_irq_handle 中取出 mscratch 的值，则并不是 ksp 的值（通过 assert(ksp != 0) 也可以证实）。怎么改，这里就不赘述了，我们来思考一下，为什么这个错误的做法能够正确执行。

因为 ksp 始终不为 0，所以 c->np 恒为 USER，这会导致什么？对于从用户进程陷入的 CTE，完全正确；而对于从内核态陷入的 CTE （包括系统调用产生的内核态重入），在他们从 trap 返回时，会额外产生一次 ksp = $sp 。事实上，在 PA 中，这种情况（只用考虑 trap.S 的下半段，即返回内核态）是有限的，考虑 __am_irq_handle 的返回值，其实只有两种情况 schedule 和 do_syscall。后者原样返回原来的 context，而内核态不可能有 syscall，所以只有一种情况：schedule 返回 nanos 内核线程的上下文。此时 mscratch 中错误的为非0，而内核线程太简单了：每次 printf 之后直接 yield，导致运行之后的 sp 仍然等于 ksp，进入 yield 之后，会把 sp 设置为 mscratch 的值，等于没变。

因此，归根结底还是复杂性不够的原因。

感想

快速过完了 PA4 二周目，给我的最深印象是，一周目遗漏、错误理解了许多内容，尤其是关于地址空间那一部分。一周目中对于“堆”、“内核栈”、“用户栈”这些名词的理解，大多只停留在抽象概念的层次，并不能与实际的地址，以及相应的执行内容关联起来。相比较而言，虚存机制理解的就较为透彻，因为虚存机制的实现涉及大量的地址解析，需要对 pagewalk 过程完全了解。

这就引发了第二个感想：PA 的评测，哪怕是助教手动评测，也没有办法检查关键部分实现的正确性。犹记与 syq 互相帮助，完成 PA4 的经历，更多的是 difftest，关于原理的讨论（例如前文用户栈、内核栈切换的部分），则往往不了了之，直到二周目才能给出正确的分析，才能给“错误的正确实现”一个合理的解释。

You have reached the end :)
Copyright © 2025 MallocSimenons