6.828 Lab4 PartA (Multiprocessor Support and Cooperative Multitasking) Writeup

Multiprocessor Support and Cooperative Multitasking

In this secion we will introduce the following concepts : mmio, vma, lma, elf, and apic.

PartA部分说明

前面的几个Lab只能支持单核，Lab4的PartA就是在之前的基础上，加上多核的扩展。主要工作是两方面 ：

• 多核怎么boot，怎么初始化多核的数据结构。
• 对于多核共享的数据结构，怎么处理data race。

Exercise 1

Something need to know

在JOS中，支持的是SMP（symmetric multiprocessing）：多个核在访问内存和IO和其他系统资源都是相互平等的关系，所有的CPU可以认为是一样的。

在boot阶段，CPU被分为两类：

• the bootstrap processor (BSP) : 负责初始化整个系统和操作系统的一些基本的数据结构（如 pages 等等）。
• the application processors (APs)：当JOS Boot起来之后，由BSP 发送STARTUP 指令，将其他CPU 激活。

在SMP系统中，每个CPU都有一个本地的APIC单元（Advanced Programmable Interrupt Controller），这个单元有两个作用：

• 负责在整个系统中控制和传递中断。
• 区别各个CPU。LAPIC提供给和它相连的CPU一个唯一的ID号，通过读APIC的 ID 就能够知道当前是哪个CPU在运行。

一个CPU通过MMIO访问对应的LAPIC。MMIO (Memory Mapped IO) : 将物理地址映射到一些IO设备的寄存器，这样通过对这些个物理地址的load/store操作，就相当于对这些寄存器进行了访问。(在之前的Lab里面，page_init()的时候，留出了IO hole，就是为了这里MMIO)。

Exercise 1

为 APIC 需要MMIO访问的地址分配空间。给出MMIO 的 pa 和 len，返回访问这个 pa 的 va。通过boot_map_region函数实现。注意对齐和检测地址溢出。因为这块内存不是普通的内存，所以安全起见，需要对这块内存不做缓存处理，所以PTE_PCD | PTE_PWT | PTE_W。 PTE_PCD 表示 page cache disabled, PTE_PWT 表示 page write through.

void *
mmio_map_region(physaddr_t pa, size_t size)
{
  void * ret = (void*)base;
  size = ROUNDUP(size, PGSIZE);
  if (base + size > MMIOLIM || base + size < base )
    panic("mmio_map_region : reservation overflow.\n");
  boot_map_region(kern_pgdir , base, size, pa, PTE_PCD | PTE_PWT | PTE_W);
  base += size;
  return ret;
}

Exercise 2

Something need to know

在BSP boot 之后， APs boot的简单过程：

1. 读取多核的配置信息。在BIOS 中存储着这个多核系统的基本信息，诸如：CPU的个数，对应的APIC的ID，和每个APIC对应的MMIO的地址。第一步要做的就是读取这些信息，通过kernel/mpconfig.c 中的mp_init()
2. BPS初始化自己的APIC，根据BIOS中的配置信息，初始化自己APIC对应的MMIO(通过调用mmio_map_region) 和其他APIC的信息。lapic_init()
3. BPS初始化对应的中断控制器。 pic_init()
4. boot CPU。和单个CPU的boot稍微有区别。初始化每个CPU的栈(当前使用的栈还是，同时将一段汇编代码mpentry.S装载到物理地址为MPENTRY_ADDR的内存中，lapic发送 START 指令，让每个CPU开始执行这段代码。 mpentry.S的作用就是把CPU boot起来，初始化页表，打开paging，把栈从临时boot的栈切换到最开始初始化的栈(KSTACKTOP下面区域)上。
5. 在mpentry.S的最后，跳到mp_main()执行，做以下操作：
   1. 切换页表到kern_pgdir.
   2. 初始化APs自己的APIC，lapic_init()
   3. 初始化APs自己的GDT 和 Segment Descriptor( ES, DS, SS, FS, GS, CS) env_init_percpu()
   4. 初始化APs自己的TSS 和 IDT trap_init_percpu()
   5. 更新CPU的状态信息

这个时候 APs 算是 boot 完成了。

Exercise 2

因为在boot APs的时候，需要将mpentry.S load到 MPENTRY_ADDR中，所以在page_init()的时候，需要把MPENTRY_ADDR 标记为占用。

for ( ; i < PGNUM(IOPHYSMEM); i ++) {
  // LAB 4 mark the physical page at MPENTRY_PADDR as in use.
  if ( i == PGNUM(MPENTRY_PADDR) ) {
    pages[i].pp_ref = 1;
    pages[i].pp_link = NULL;
  } else {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
  }
}

Qestion 1

MPBOOTPHYS的作用就是将VA(Virtual Address)转化为PA(Physical Address)，在boot/boot.S中，将ELF文件load到内存中，同时开始执行kern/entry.S的代码，entry.S的作用就load 临时的页表(kern/entry_pgdir， [0,4MB])，打开分页。 然而在boot APs的时候就不能这么做了，因为Intel 的 Multiprocessor Specificatoin B4.2 对 APIC 的 STARTUP 指令说明如下：

The STARTUP IPI causes the target processor to start executing in Real Mode from address 000VV000h, where VV is an 8-bit vector that is part of the IPI message. Startup vectors are limited to a 4-kilobyte page boundary in the first megabyte of the address space. Vectors A0-BF are reserved; do not use vectors in this range.

就是说在STARTUP 之后，运行在实模式下，只能用CS：IP寻址，并且CS：IP被限制在XY00:0000 (XY 为 8 bit)内，只能在4K范围内，所以boot_aps()把mpentry.S 复制到了MPENTRY_PADDR(0x7000)这个地址物理上，为了能够将虚拟地址转化到MPENTRY_PADDR起始的物理地址上，就需要MPBOOTPHYS这个宏。

另外关于 VMA 和 LMA的区别，GNU官方这样说的:

Every loadable or allocatable output section has two addresses. The first is the VMA, or virtual memory address. This is the address the section will have when the output file is run. The second is the LMA, or load memory address. This is the address at which the section will be loaded. In most cases the two addresses will be the same. An example of when they might be different is when a data section is loaded into ROM, and then copied into RAM when the program starts up (this technique is often used to initialize global variables in a ROM based system). In this case the ROM address would be the LMA, and the RAM address would be the VMA.

Exercise 3, 4

Something need to know

对于多核操作系统，需要注意对于每个CPU，哪些数据结构是私有的，哪些是共享的。在JOS中，对每个CPU都有struct CpuInfo:

// Per-CPU state
struct CpuInfo {
  uint8_t cpu_id;                 // Local APIC ID; index into cpus[] below
  volatile unsigned cpu_status;   // The status of the CPU
  struct Env *cpu_env;            // The currently-running environment.
  struct Taskstate cpu_ts;        // Used by x86 to find stack for interrupt
};

1. 栈. percpu_kstacks[NCPU][KSTKSIZE]
2. TSS 和 TSS 描述符
3. 当前运行的env
4. 寄存器上下文

Exercise 3

在BSP mem_init()的时候对所有CPU初始化栈的页表:

static void
mem_init_mp(void)
{
  int i = 0;
  uint32_t kstacktop_i;
  for ( ;i < NCPU ;i ++){
    kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
    boot_map_region(kern_pgdir, kstacktop_i - KSTKSIZE, KSTKSIZE, 
                    PADDR(&percpu_kstacks[i]), PTE_W);
  }

}

Exercise 4

在BSP 和 APs trap_init()的时候，初始化每个CPU的TSS和IDT

void
trap_init_percpu(void)
{
  thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - (thiscpu->cpu_id) * (KSTKSIZE + KSTKGAP);
  thiscpu->cpu_ts.ts_ss0 = GD_KD;

  // Initialize the TSS slot of the gdt.
  gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id] = SEG16(STS_T32A, (uint32_t) (&thiscpu->cpu_ts),
          sizeof(struct Taskstate), 0);
  gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id].sd_s = 0;

  // Load the TSS selector (like other segment selectors, the
  // bottom three bits are special; we leave them 0)
  ltr(GD_TSS0  + (thiscpu->cpu_id << 3) );

  // Load the IDT
  lidt(&idt_pd);
}

Exercise 5

Something need to know

多核中，时刻要记住，一行代码都是分成很多小的指令执行的，每个指令执行的时候，都可以被中断掉，并且每行代码都可能被多个CPU同时执行。

为了解决多个CPU访问同一段程序的时候的 race condition，JOS中使用了内核大锁(big kernel lock),其作用就是只能又一个env在kernel态运行，在任何时间，都只能又一个user 的 env 在kernel 执行，这样就防止出现多个CPU同时修改一个env的信息的情况了。所以在从user 进入kernel的时候和kernel跳到user的时候，需要lock_kernel和unlock_kernel。

Big kernel lock 采用的是spinlock，当要尝试获取锁的时候，如果没有拿到就spin在那里，直到拿到为止。

truct spinlock {
  unsigned locked;       // Is the lock held?

#ifdef DEBUG_SPINLOCK
  // For debugging:
  char *name;            // Name of lock.
  struct CpuInfo *cpu;   // The CPU holding the lock.
  uintptr_t pcs[10];     // The call stack (an array of program counters)
                         // that locked the lock.
#endif
};

在spin_lock的时候，采用了xchg ,xchg能够保证:

• 执行是原子的不可在划分的，在执行的时候是不可被中断掉的
• 执行是顺序的，不会被乱序优化执行。（有些处理器为了提高执行效率，一段指令可能会被乱序执行，

比如x86 xchg %eax, addr 指令，本质上是:

1. freeze other CPUs’ memory activity for address addr
2. temp := *addr
3. *addr := %eax
4. %eax = temp
5. un-freeze other memory activity

void
spin_lock(struct spinlock *lk)
{
#ifdef DEBUG_SPINLOCK
  if (holding(lk))
    panic("CPU %d cannot acquire %s: already holding", cpunum(), lk->name);
#endif

  // The xchg is atomic.
  // It also serializes, so that reads after acquire are not
  // reordered before it. 
  while (xchg(&lk->locked, 1) != 0)
    asm volatile ("pause");

  // Record info about lock acquisition for debugging.
#ifdef DEBUG_SPINLOCK
  lk->cpu = thiscpu;
  get_caller_pcs(lk->pcs);
#endif
}

static inline uint32_t
xchg(volatile uint32_t *addr, uint32_t newval)
{
  uint32_t result;

  // The + in "+m" denotes a read-modify-write operand.
  asm volatile("lock; xchgl %0, %1" :
      "+m" (*addr), "=a" (result) :
      "1" (newval) :
      "cc");
  return result;
}

lock按照提示添加就可以了，基本上都是在user 和 kernel的交界区。

• env_run : 从kernel到user，unlock
• trap : 从user到kernel, lock
• shed_yield : 调用env_run, lock，防止两个CPU同时跑一个env
• boot_aps : 在APs boot之前，lock住kernel

Question 2

如果是share 一个栈，那么每个CPU的栈相当于是穿插在这个share的栈上，CPU1 push，接着CPU2 push，再CPU1 pop的时候，就会出问题。

Exercise 6

Exercise 6

实现一个Round-Robin的调度算法，sched_yield() 函数的作用就是从envs中轮询挑选一个空闲的env来执行，如果没有，那么就继续执行之前的那个env，注意不能让两个CPU同时跑一个env。注意，轮询的时候，要从上次sched 的env的位置开始往下找，而不是从头，否则会有一些env始终无法调度到的情况。

void
sched_yield(void)
{
  struct Env *idle;
  size_t i = 0;
  size_t nxt = 0;
  idle = NULL;
  
  if (curenv) 
    nxt = ENVX(ENVX(curenv->env_id));

  for ( ;i < NENV;i ++) {
    nxt = (nxt + 1) & (NENV-1);
    if (envs[nxt].env_status == ENV_RUNNABLE) {
      idle = &envs[nxt];
      break;
    }
  }

  if (idle) 
    env_run(idle);
  else if (curenv && curenv->env_status == ENV_RUNNING)
    env_run(curenv);
   
  // sched_halt never returns
  sched_halt();
}

同时在syscall中添加sys_yield()系统调用。sys_yield通过调用 sche_yield 实现。

Question 3

因为所有user 的env的页表的初始化都是通过 memmove(e->env_pgdir, kern_pgdir, PGSIZE); 实现的，kern_pgdir中包含了UENVS的地址空间，envs数组都是存储在UENVS这个地址上的，UENVS对user是RO，对kernel是RW，所以，即使更换为被调度的env的pgdir，也是可以访问这个虚拟地址的。

Question 4

old env 的registers包含了old env的运行的状态，运行到哪个eip，使用的是哪个ss，ssp等等，当这个old env被调度，继续执行的时候，需要知道之前执行到哪里了，所以是需要保存old env的registers的。

old env 的 reigsters 是在 trap(trapframe)中，把参数 trapframe，拷贝到 curenv->env_tf，上的，这样就保存了trap之前，env 的状态了，curenv 是在 UENV 虚拟地址上的。

// Copy trap frame (which is currently on the stack)
// into 'curenv->env_tf', so that running the environment
// will restart at the trap point.
// now, the code is running in kernel mode, but curenv is not 
// kernel, curenv is the env just before the trap occured.
// so, the trap fram copy is needed, for saving the trapped 
// env's registers.
// tf is on the kernel stack.
curenv->env_tf = *tf;
// The trapframe on the stack should be ignored from here on.
tf = &curenv->env_tf;

Exercise 7

实现关于 fork 的系统调用。因为是系统调用，所以对于 user 系统调用的参数的处理要谨慎，进行各种corner case 的检查，来保证在某些特殊述如下 user 不能hack kernel。

记住这句话：大道理谁都懂，魔鬼在细节！ 在写kernel的代码的时候，要考到到各种输入的corner case。

sys_exofork 的实现

sys_exofork 的作用就是alloc 一个新的env，这个env 调用系统调用的孩子(curenv 就是调用这个系统调用的env)。同时将son env的寄存器的值初始化为parent env的值，这样相当于son env 也是执行到这里的，只不过son env的status 是 ENV_NOT_RUNNABLE，因为还没有初始化页表什么的，所以还是不能运行的。对于函数的返回值，如果是parent env，那么返回son env 的id，如果是son env，那么返回0。如何区分这个呢？想到系统调用的返回值是记录在trapframe 的eax寄存器中，所以，注意对son env的寄存器初始化的时候，要将son env 的eax寄存器初始化为0。

static envid_t
sys_exofork(void)
{
  struct Env *newenv;
  int ret;

  // alloc 
  if ((ret = env_alloc(&newenv, curenv->env_id)) < 0)
    return -E_NO_FREE_ENV;

  // set trapframe , note that son_env 's eax should be zero because 
  // son env's fork will return zero.
  memmove(&newenv->env_tf, &curenv->env_tf, sizeof(struct Trapframe));
  newenv->env_tf.tf_regs.reg_eax = 0;
 
  // set status 
  newenv->env_status = ENV_NOT_RUNNABLE;
  return newenv->env_id;
}

sys_env_set_status 的实现

sys_env_set_status的功能就如名字一样，但是需要做如下的检查：

• envid 需要是curenv 的son。通过envid2env检查。
• status 只能是 ENV_RUNNABLE 或者 ENV_NOT_RUNNABLE，因为这个系统调用是配合sys_exofork的。

static int
sys_env_set_status(envid_t envid, int status)
{
  int ret;
  struct Env * son_env;

  // check validation of the envid
  if((ret = envid2env(envid, &son_env, 1)) < 0 ) 
    return -E_BAD_ENV;

  // check status 
  if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) 
    return -E_INVAL;

  // set son_env status 
  son_env->env_status = status;
  return 0;
}

sys_page_alloc 的实现

sys_page_alloc的作用是初始化一个page，映射到va这个虚拟地址，对应的权限是perm。注意envid必须是son env 的id。这个是配合sys_exofork使用的，注意到sys_exofork没有初始化虚拟地址。注意：

• 只有envid 对应的env 是 curenv 或者是curenv 的 son 才可以。
• va 不能超过 UTOP，并且必须是PAGE对齐的。
• perm 的权限是又限制的，比如说不能使用PTE_D。PTE_SYSCALL宏给出了可以使用的PTE的FLAG。
• 物理page初始化为zero。
• 如果插入pte失败，记得把分配的物理页回收。

因为这个系统调用实现的时候，先page_alloc，分配一个新的PageInfo，然后将这个PageInfo page_insert到va上，一个副作用就是如果va对应的PageInfo存在，那么之前的PageInfo就会被unmap掉。

static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
  int ret;
  struct Env * env;
  struct PageInfo * pp;

  // check envid
  if ((ret = envid2env(envid, &env, 1)) < 0)
    return -E_BAD_ENV;

  // check va
  if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) 
    return -E_INVAL;

  // check perm 
  if (((perm | PTE_SYSCALL) != PTE_SYSCALL) || ((perm | PTE_U | PTE_P) != perm)) 
    return -E_INVAL;

  // alloc page and memset to ZERO
  pp = page_alloc(ALLOC_ZERO);
  if (!pp) 
    return -E_NO_MEM;

  // insert to page table
  if ((ret = page_insert(env->env_pgdir, pp, va, perm)) < 0){
    page_free(pp);
    return -E_NO_MEM;
  }

  return 0;
}

sys_page_map 的实现

sys_page_map 的作用是将 srcenvid 中的 srcva 对应的内容 复制到 dstenvid 中的 dstva 中，同时将权限更新为perm。注意：

• 凡是涉及到envid，就要检查envid 的有效性，只有curenv 的 id 是这个envid 或者 curenv 的直接相连的 son env 的 id 是这个 envid 的时候才能够访问。
• 系统调用中凡是涉及到虚拟地址空间，都要检查这个user是否有访问这个虚拟地址空间的权限。比如va不能够超过 UTOP。
• 凡是涉及到虚拟地址空间的，创建这个va的page的时候，注意这个va是否已经被占用了。
• 凡是涉及到页表权限FLAG的，都要检查user是否有这个权限设置这个FLAG。

static int
sys_page_map(envid_t srcenvid, void *srcva,
       envid_t dstenvid, void *dstva, int perm)
{
  struct Env *srcenv, *dstenv;
  int ret;
  struct PageInfo * pp;
  pte_t * src_pte;

  // check srcenvid and dstenvid
  if ((ret = envid2env(srcenvid, &srcenv, 1)) < 0)
    return ret;
  if ((ret = envid2env(dstenvid, &dstenv, 1)) < 0)
    return ret;

  // check srcva and dstva
  if ((uintptr_t)srcva >= UTOP || (uintptr_t)dstva >= UTOP || PGOFF(srcva) != 0 || PGOFF(dstva) != 0)
    return -E_INVAL;

  // check srcva is mapped in srcenv or not
  pp = page_lookup(srcenv->env_pgdir, srcva, &src_pte);
  if (!pp) 
    return -E_INVAL;

  // check perm 
  if (((perm | PTE_SYSCALL) != PTE_SYSCALL) || (!(*src_pte & PTE_W) && (perm & PTE_W)))
    return -E_INVAL;

  // do page map
  if ((ret = page_insert(dstenv->env_pgdir, pp, dstva, perm)) < 0)
    return -E_NO_MEM;

  return 0;
}

sys_page_unmap 的实现

sys_page_unmap的功能就是释放envid对应的虚拟地址空间va。注意检查参数。

static int
sys_page_unmap(envid_t envid, void *va)
{
  int ret;
  struct Env *env;

  // check envid 
  if ((ret = envid2env(envid, &env, 1)) < 0)
    return -E_BAD_ENV;

  // check va
  if ((uintptr_t)va >= UTOP || (PGOFF(va) != 0))
    return -E_INVAL;

  // do page unmap
  page_remove(env->env_pgdir, va);
  return 0;
}

利用刚刚完成的系统调用在用户态实现简单的 fork

在user/dumbfork.c 中实现的dumbfork，没有实现COW，过程如下:

// 这段代码是user的代码，在user态执行。
envid_t
dumbfork(void)
{
  envid_t envid;
  uint8_t *addr;
  int r;
  extern unsigned char end[];

  // Allocate a new child environment.
  // The kernel will initialize it with a copy of our register state,
  // so that the child will appear to have called sys_exofork() too -
  // except that in the child, this "fake" call to sys_exofork()
  // will return 0 instead of the envid of the child.
  envid = sys_exofork();
  if (envid < 0)
    panic("sys_exofork: %e", envid);
  if (envid == 0) {
    // We're the child.
    // The copied value of the global variable 'thisenv'
    // is no longer valid (it refers to the parent!).
    // Fix it and return 0.
    // 这里的thisenv不是 kernel 中的每个CPU的thisenv，每个 CPU 中的
    // thisenv一定是正在运行的env，因为在调度的时候会更新curenv的值。
    // 这里的thisenv是 lib 中记录的当前的env。
    thisenv = &envs[ENVX(sys_getenvid())];
    return 0;
  }

  // We're the parent.
  // Eagerly copy our entire address space into the child.
  // This is NOT what you should do in your fork implementation.
  for (addr = (uint8_t*) UTEXT; addr < end; addr += PGSIZE)
    duppage(envid, addr);

  // Also copy the stack we are currently running on.
  duppage(envid, ROUNDDOWN(&addr, PGSIZE));

  // Start the child environment running
  if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
    panic("sys_env_set_status: %e", r);

  return envid;
}

如何通过这些系统调用实现duppage？

通过 sys_page_map， sys_page_unmap， memmove 把当前env上的va上的内容，复制到son env上对应的va上？ parent env 是无法直接访问son env的地址空间的。

在这里首先不得不感叹一下JOS的设计哲学，这些系统调用的函数实现功能的粒度恰到好处。没有一个系统调用的实现是有重复的。如果让我来解决这个问题，可能直接就是简单粗暴的加一个系统调用，能够将一个env的va上的内容复制到另一个env的va上，但是这两个env是要有检查parent关系的。但是这样显然就和前面的系统调用有重复实现的部分了。说几点细节：

• sys_page_alloc : parent env 可以通过这个系统调用来给son env分配一个虚拟地址和对应的物理页。
• sys_page_map : parent env 可以在 son 的 env 中 set 一个映射：son env 的一个va 对应到 将自己的va对应的物理页上。注意：parent env的物理页被两个va映射了。
• sys_page_unmap : parent env可以通过这个系统调用，将son env的一个 PTE 从PageTable中删除掉，同时decref对应的物理页。

方法如下：

1. parent env 是可以通过调用 sys_page_alloc 来给son env 分配一个虚拟地址和这个虚拟地址对应的物理页的。所以首先在 son env 上分配这样一个虚拟地址。
2. 在parent env中设置一个临时的虚拟地址tmpva，将son env的va 通过 sys_page_map，映射到parent tmpva 对应的物理页上。tmpva对应的物理页refcount = 2.
3. 通过memmove，将parent env 中的va对应的内容复制到 tmpva上。
4. 在parent env中sys_page_unmap 自己的tmpva。这样tmpva对应的物理页的refcount 就是1了，是son va引用的。

// 这段代码是user的，在user态执行。
// dup当前env的 addr 到 destenv的addr 上。
void
duppage(envid_t dstenv, void *addr)
{
  int r;

  // This is NOT what you should do in your fork.
  if ((r = sys_page_alloc(dstenv, addr, PTE_P|PTE_U|PTE_W)) < 0)
    panic("sys_page_alloc: %e", r);
  if ((r = sys_page_map(dstenv, addr, 0, UTEMP, PTE_P|PTE_U|PTE_W)) < 0)
    panic("sys_page_map: %e", r);
  memmove(UTEMP, addr, PGSIZE);
  if ((r = sys_page_unmap(0, UTEMP)) < 0)
    panic("sys_page_unmap: %e", r);
}

– EOF –