Part A: Multiprocessor Support and Cooperative Multitasking

这部分需要实现多处理器的支持，并且实现一些新的系统调用来支持合作的循环调度。

要让 JOS 支持 SMP（symmetric multiprocessing），但在 boot 几阶段 cpu 被分为两类：一类是 BSP（bootstrap processor），负责在系统 boot 过程中运行 boot 相关代码；另一类是 APs （application processors），在系统 boot 完成后由 BSP 唤醒，之后一直运行。

一个处理器和它对应的 LAPIC 之间通信使用的是 MMIO（memory mapped I/O），为了支持 MMIO，我们把 virtual memory 的最高 32MB 映射为 Memory mapped I/O。

JOS Memory Layout

• Exercise 1
  阅读文档发现 APs 的 entry code 位于物理地址的 0x7000 ，对应在物理地址的 BaseMemory 段。所以在 page_init 函数中，case2) 中加入判断语句，如果当前页是对应 entry code 的页，那么就标记为已用。（用的是 lab2 里的方法）

  // case 2)
  for(; i < npages_basemem; i++){
    if (i == MPENTRY_PADDR / PGSIZE) {
        pages[i].pp_ref = 1;
        pages[i].pp_link = NULL;
        continue;
    }
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }
  

• Question

  1. Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
     Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.

  注释云：

  This code is similar to boot/boot.S except that
  - it does not need to enable A20
  - it uses MPBOOTPHYS to calculate absolute addresses of its symbols, rather than relying on the linker to fill them

  因为在激活各个 APs 时，BSP 已经进入保护模式，而 APs 一开始是在实模式的，所以这里必须使用 absolute address （即物理地址）。

• 一些需要注意的 per-cpu 的状态

  per-cpu kernel stack：因为多个 cpu 可能同时 trap 进入 kernel，为了防止互相干扰，要为每个 cpu 预留 kernel stack 的空间。所有 kernel stack 从 KSTACKTOP 往下增长，每两个 kernel stack 之间用一段不可访问内存（guard pages）隔开。

  per-cpu TSS and TSS descriptor：每个 cpu 都要保存自己的 TSS 来记录自己的上下文信息。

  per-cpu system registors

  per-cpu idle env：对于闲置的 cpu ，JOS 的设计是让他们去跑一个 idle environment。默认 envs[cpunum()] 是每个 cpu 的 idle environment。

• Exercise 2
  这里要实现 kern/pmap.c 中的 mem_init_mp 函数去为每个 cpu 初始化 kernel stack 的空间。

  使用之前实现的 boot_map_region 函数在 NCPU 的循环中申请每段空间。

  这里踩了两个坑，一个是本 lab 一开始 merge 的时候手动修复冲突的时候在 mem_init 函数中把 mem_init_mp 和 boot_map_region 这一句前后弄反了；另一个是之前使用了大页 boot_map_region_large，改为小页之后就通过了。

• Exercise 3
  这里要实现在 kern/trap.c 中的 trap_init_percpu 函数，即在激活 APs 时为它们初始化对应的 TSS 和 TSS descriptor。

  // LAB 4: Your code here:
  
  int cur = thiscpu->cpu_id;
  thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - cur * (KSTKSIZE + KSTKGAP);
  thiscpu->cpu_ts.ts_ss0  = GD_KD;
  
  int GD_TSSi = GD_TSS0 + (cur << 3);
  gdt[GD_TSSi >> 3] = SEG16(STS_T32A, (uint32_t) (&(thiscpu->cpu_ts)),sizeof(struct Taskstate), 0);
  gdt[GD_TSSi >> 3].sd_s = 0;
  
  ltr(GD_TSSi);
  lidt(&idt_pd);
  

• Exercise 4
  这里要实现对整个 kernel 加锁。此处实现的是 big kernel lock，即所有进程进入 kernel mode 时加锁，出 kernel mode 时放锁，任何时刻只能有一个进程处于 kernel mode。

  根据文档，在四个地方添加调用即可。

  需要注意的是，之前 lab3 中写的 sysenter 相关的四行代码必须在 trap_init_percpu 中。
  lab3中为：

  /*Lab3/4 code :*/
  // set MSR for sysenter
  extern void sysenter_handler();
  wrmsr(0x174, GD_KT, 0);       /* SYSENTER_CS_MSR */
  wrmsr(0x175, KSTACKTOP, 0);   /* SYSENTER_ESP_MSR */ //this line from lab3, changed below
  //wrmsr(0x175, thiscpu->cpu_ts.ts_esp0 , 0);    // specialized for per-cpu 
  wrmsr(0x176, (uint32_t)sysenter_handler, 0);          /* SYSENTER_EIP_MSR */
  

  这里改为：

  /*Lab3/4 code :*/
  // set MSR for sysenter
  extern void sysenter_handler();
  wrmsr(0x174, GD_KT, 0);       /* SYSENTER_CS_MSR */
  //wrmsr(0x175, KSTACKTOP, 0); /* SYSENTER_ESP_MSR */ this line from lab3, changed below
  wrmsr(0x175, thiscpu->cpu_ts.ts_esp0 , 0);    // specialized for per-cpu 
  wrmsr(0x176, (uint32_t)sysenter_handler, 0);          /* SYSENTER_EIP_MSR */
  

• Exercise 4.1

  这里需要实现 ticket spinlock。如果注释定义了 #USE_TICKET_SPIN_LOCK 那么 spinlock 中会多出两个属性 own，next。next 相当于挂号系统中的当前已经挂出的最大号数。所以当有进程申请拿锁的时候，需要将 next ++ ，并用这个值作为当前进程挂到的号。（这个动作要保证原子性）而 own 代表目前正在服务的号。所以当有进程放锁的时候，将 own ++。所有正在等待锁的进程等待 own 的值和自己的 next 值是否相等，相等说明叫到号，即可拿到锁。

  其中拿锁和放锁时，要保证对 next 的递增操作是原子操作

  // acquire the lock
  #else
    //LAB 4: Your code here
    unsigned ticket = atomic_return_and_add(&lk->next, 1);
    while (atomic_return_and_add(&lk->own, 0) != ticket)
        asm volatile ("pause");
  
  // release the lock
  #else
    //LAB 4: Your code here
    atomic_return_and_add(&lk->own, 1);
  

• Question

  2. It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock.

  因为我们实现的大内核锁只是保护住了进出 kernel mode 之间的动作，但其实在大内核锁起作用之前，trapentry.S 就已经在向内核栈上 push 各种数据了。这些动作并不能被大内核锁保护，所以在多个 CPU 交替发生 trap 的时候，如果是 shared kernel stack，一定会发生数据冲突。

I'm not brave enough

• Exercise 5

  这里要实现 rr 的调度。

  首先需要明确的设计：env 数组中前 NCPU 项都是 idle env。当某个 CPU 需要用到 idle env 时，只要访问 env[cpunum()] 即可拿到自己的 idle env。

  从 kern/init.c 中的 i386_init 函数中可以看出，先创建了 NCPU 个类型为 ENV_TYPE_IDLE 的空闲进程，之后剩下的从 NCPU 到 NENVS-1 的类型为 ENV_TYPE_USER 的用户进程。

• Question

  3. In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context--the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?

  具体原因与我们在 lab3 中实现的 env_setup_vm() 函数有关。每个 env 的 env_pgdir 的内核部分的映射都是以 kern_pgdir 为基础形成的，所以映射一致，且来切去都没差。

• Exercise 6

  这部分需要实现如同 Linux 系统里 fork 函数一样的函数。

  需要明确的设计：在 envid2env 的实现中，如果传入的 envid 为 0，则得到当前的 env，即 curenv。

  几个函数的实现不难，跟着注释走就 OK。

  实现完后，发现跑出了 protection fault （trap 13），之后 debug 修复的思路参考了之前学长攻略中的思路。

  第五个参数传入方式的设计：用 esi 保存（因为之前 push 过 esi），但是需要通过与 ebp 的相对位置 0x4(%ebp) 来取得。

Part B: Copy-on-Write Fork

这个 lab 的第二部分需要实现 COW（写时拷贝）。

• User level Page Fault
  因为触发 COW 的第一步就是触发一个 PageFault，所以我们需要先实现 User level Page Fault。

• Exercise 7
  这里需要实现 sys_env_set_pgfault_upcall 函数。这个函数为指定的 env 绑定一个 pagefalut 处理函数。实现如下：

  // LAB 4: Your code here.
  //panic("sys_env_set_pgfault_upcall not implemented");
  struct Env *e;
  int r;
  r = envid2env(envid, &e, 1);
  if(r < 0)
      return r;
  e->env_pgfault_upcall = func;
  return 0;
  

• User stack and exception stack
  正常情况下，在用户栈上执行。当 page fault 发生的时候，内核会重启用户进程并在一个指定的位置（user exception stack）执行 pagefault handler。

  JOS 的 user exception stack 大小为 PGSIZE，位置在 [UXSTACKTOP-PGSIZE,UXSTACKTOP-1]。

• Exercise 8
  这里需要实现调用 Pagefault Handler。

  当 pagefault 发生的时候，如果当前没有注册 handler，那么内核就会摧毁当前 env（和原来一样）。如果发现了 handler，那么内核会在当前 env 的 exception stack 上记录一个特殊的 TF，叫做 struct UTrapframe。

  UTrapframe 结构图

之后 kernel 会调度当前的 user env（就是触发 pgfault 的同一个）在 exception stack 上执行 pgfault handler。

如果发生 pagefault 的时候，已经在 user exception stack 上了，说明在执行 pagefault handler 的时候又出发了 pagefault（嵌套）。这时候需要把新的 UTrapframe push 在老的 UTrapframe 下方，而不是覆盖。具体判断方法，检查当前的 tf->tf_esp 是否在范围 [UXSTACKTOP-PGSIZE, UXSTACKTOP-1] 之内。

• Exercise 10
  这里要实现一个用户环境的方法 set_pgfault_handler。首先在 syscall 里分发

  case SYS_env_set_pgfault_upcall:
  return sys_env_set_pgfault_upcall((envid_t)a1, (void *)a2);
  

  需要明确的变量：

  1.handler 是传入的用户自定义页错误处理函数指针。
  2._pgfault_upcall 是一个全局变量，在 lib/pfentry.S 中完成的初始化。它是页错误处理的总入口，页错误除了运行 page fault handler，还需要切换回正常栈。
  3._pgfault_handler 被赋值为handler，会在 _pgfault_upcall 中被调用，是页错误处理的一部分。

  然后完成 set_pgfault_handler 函数：如果是第一次调用，需要先分配一个页面作为 user exception stack，并将该 env 的 upcall 设置为上一个 exercise 写好的汇编程序。之后再调用的时候直接改 _pgfault_handler 即可。实现如下：

  int r;
  
  if (_pgfault_handler == 0) {
      // First time through!
      // LAB 4: Your code here.
      //panic("set_pgfault_handler not implemented");
      if((r = sys_page_alloc((envid_t) 0, (void*)(UXSTACKTOP-PGSIZE), PTE_U | PTE_P | PTE_W)) < 0 )
          panic("error in set_pgfault_handler %e\n",r);
      if((r = sys_env_set_pgfault_upcall((envid_t)0, _pgfault_upcall)) < 0)
          panic("error in set_pgfault_handler: sys_env_set_pgfault_upcall: %e\n", r);
  }
  
  // Save handler pointer for assembly to call.
  _pgfault_handler = handler;
  

• Exercise 11
  这里要实现 COW fork 了。

  现在我们已经具备了在用户空间实现 copy-on-write fork() 的条件。
  如同 dumbfork() 一样，fork() 也要创建一个新进程，并且在新进程中建立与父进程同样的内存映射。关键的不同点是，dumbfork() 拷贝了物理页的内容，而 fork() 仅拷贝了映射关系，仅在某个进程需要改写某一页的内容时，才拷贝这一页的内容。其基本流程如下：
  1.父进程使用 set_pgfault_handler将 pgfault() 设为 page fault handler
  2.父进程使用 sys_exofork() 建立一个子进程
  3.对每个在 UTOP 之下可写页面以及 COW 页面（用 PTE_COW 标识），父进程调用 duppage 将其“映射”到子进程，同时将其权限改为只读，并用 PTE_COW 位来与一般只读页面区别
  异常栈的分配方式与此不同，需要在子进程中分配一个新页面。因为 page fault handler 会实实在在地向异常栈写入内容，并在异常栈上运行。如果异常栈页面都用 COW 机制，那就没有能够执行拷贝这个过程的载体了
  4.父进程会为子进程设置 user page fault entrypoint
  5.子进程已经就绪，父进程将其设为 runnable
  进程第一次往一个 COW page 写入内容时，会发生 page fault，其流程为：
  1.内核将 page fault 传递至 _pgfault_upcall，它会调用 pgfault() handler
  2.pgfault() 检查错误类型，以及页面是否标记为PTE_COW
  3.pgfault() 分配一个新的页面并将 fault page 的内容拷贝进去，然后将旧的映射覆盖，使其映射到该新页面。

  fork 函数的实现如下：

  envid_t
  fork(void)
  {
      // LAB 4: Your code here.
      //panic("fork not implemented");
      set_pgfault_handler(pgfault);
      envid_t e_id = sys_exofork();
      if (e_id < 0) panic("fork: %e", e_id);
      if (e_id == 0) {
          // child
          thisenv = &envs[ENVX(sys_getenvid())];
          return 0;
      }
  
  
      for (uintptr_t addr = UTEXT; addr < USTACKTOP; addr += PGSIZE) {
          if ((vpd[PDX(addr)] & PTE_P) && (vpt[PGNUM(addr)] & (PTE_P | PTE_U)) == (PTE_P | PTE_U))
              duppage(e_id, PGNUM(addr));
      }
      // alloc page for exception stack
      int r = sys_page_alloc(e_id, (void *)(UXSTACKTOP-PGSIZE), PTE_U | PTE_W | PTE_P);
      if (r < 0) panic("fork: %e",r);
  
      extern void _pgfault_upcall();
      r = sys_env_set_pgfault_upcall(e_id, _pgfault_upcall);
      if (r < 0) panic("fork: set upcall for child fail, %e", r);
  
      if ((r = sys_env_set_status(e_id, ENV_RUNNABLE)) < 0)
          panic("sys_env_set_status: %e", r);
  
      return e_id;
  }
  

  接下来实现 duppage 函数。主要负责检查 pn 指向的页的 perm 是否是 PTE_W 和 PTE_COW。如果是就将当前 env 中的这一页在 envid 指向的 env 中形成新的映射。

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

• Exercise 12
  扩展内核功能，能够接受硬件时钟的外部中断。这里需要做的是修改 trapentry.S 和 trap.c/trap_init() 来初始化 IRQ 的 IDT 表。

  在上述两处添加一些硬编码的东西，之后跑不过测试。后来发现忘记 trapentry.S 中忘记添加 sti 这一语句。

  You will have to ensure that the FL_IF flag is set in user environments when they run so that when an interrupt arrives, it gets passed through to the processor and handled by your interrupt code. Otherwise, interrupts are masked, or ignored until interrupts are re-enabled. We masked interrupts with the very first instruction of the bootloader, and so far we have never gotten around to re-enabling them.

• Exercise 13

  在 trap_dispatch() 中的注释处添加时钟中断的处理分支。

  // Handle clock interrupts. Don't forget to acknowledge the
  // interrupt using lapic_eoi() before calling the scheduler!
  // LAB 4: Your code here.
  if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
      lapic_eoi();
      sched_yield();
      return;
  }
  

未实现 challenge