MIT 6.828 labs walkthroughs: Lab 4 Preemptive Multitasking

## Exercise 1

`lapic_init()` calls `mmio_map_region()` at first to map 4K memory at physical address `lapicaddr` to the MMIO area of virtual memory. So we need to use `boot_map_region()` to implement the `mmio_map_region()` in `kern/pmap.c`.

Although it is called only by `lapic_init()` and the size it passes equals to `PGSIZE`, we still need to round size up to a multiple of `PGSIZE`. But here rounding `base` or `pa` is not needed as they are always page-aligned. A temporary variable is needed as we are required to return the base of the reserved region. 

Follow the comment we can write some code like this:

```c
void *
mmio_map_region(physaddr_t pa, size_t size)
{
	size_t rounded_size = ROUNDUP(size, PGSIZE);
	
	if (base + rounded_size >= MMIOLIM) {
		panic("mmio_map_region: requested size overflow MMIOLIM");
	}
	boot_map_region(kern_pgdir, base, rounded_size, pa, PTE_PCD | PTE_PWT | PTE_W);

	uintptr_t curr_base = base;
	base += rounded_size;
	return (void *)curr_base;
}
```


## Exercise 2

The control flow transfer is, the bootstrap processor (BSP) executes `boot_aps()` to copy code in `kern/mpentry.S` to `MPENTRY_PADDR`, then send STARTUP IPIs to the APs. The APs run the entry code, then `mp_main()` will initialize it and notice the BSP they are up.

The code needs to be implemented here in `page_init()` is quite simple as we know that `MPENTRY_PADDR` is `0x7000`, it is above `PGSIZE` and below `IOPHYSMEM`. What we need to do here is to initialize the page at `MPENTRY_PADDR` as a special case in the corresponding position.

```diff
@@ -310,5 +310,10 @@ page_init(void)
        for (i = 1; i < npages_basemem; i++) {
-               pages[i].pp_ref = 0;
-               pages[i].pp_link = page_free_list;
-               page_free_list = &pages[i];
+               // mark the physical page at MPENTRY_PADDR as in use
+               if (i == MPENTRY_PADDR / PGSIZE) {
+                       pages[i].pp_ref = 1;
+               } else {
+                       pages[i].pp_ref = 0;
+                       pages[i].pp_link = page_free_list;
+                       page_free_list = &pages[i];
+               }
        }
```

Now QEMU should pass tests till `check_page_free_list()`.


## Question 1

`MPBOOTPHYS` is used to calculate the corresponding physical address of its symbols at `MPENTRY_PADDR` since APs are in real mode when starting and it can only run codes below 640K and `boot_aps()` has made a copy of the code at `MPENTRY_PADDR`, so the code can be accessed by the APs with the help of this macro.

The bootloader in `boot/boot.S` doesn't need such macro because it is an independent module linked to `0x7c00` which is addressable in real mode.

If it were omitted in `kern/mpentry.S`. The APs will try to load code at high address, which is unaddressable in real mode.


## Exercise 3

The comment provides all the information needed, even some of the code. It's very easy to implement.

```c
static void
mem_init_mp(void)
{
	int i;

	for (i = 0; i < NCPU; i++) {
		uint32_t kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);

		boot_map_region(kern_pgdir, kstacktop_i - KSTKSIZE, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W);
	}
}
```

Now QEMU should pass the `check_kern_pgdir()` test.


## Exercise 4

This one is also easy as the comment also gives lots of hints. What we need to do is to replace `ts` with `thiscpu->cpu_ts`, change `gdt[(GD_TSS0 >> 3)]` to `gdt[(GD_TSS0 >> 3) + i]`, set the esp point to the CPU's own kernel and load the TSS selector for each CPU. The TSS selector may be a little hard to find. Since its bottom 3 bits are 0 and GDT uses `(GD_TSS0 >> 3) + i` as its index, its value is `GD_TSS0 + (i << 3)` here.

```c
void
trap_init_percpu(void)
{
	int id = thiscpu->cpu_id;

	// Setup a TSS so that we get the right stack
	// when we trap to the kernel.
	thiscpu->cpu_ts.ts_esp0 = (uint32_t)percpu_kstacks[id] + KSTKSIZE;
	thiscpu->cpu_ts.ts_ss0 = GD_KD;
	thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

	// Initialize the TSS slot of the gdt.
	gdt[(GD_TSS0 >> 3) + id] = SEG16(STS_T32A, (uint32_t) (&thiscpu->cpu_ts),
					sizeof(struct Taskstate) - 1, 0);
	gdt[(GD_TSS0 >> 3) + 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 + (id << 3));

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


# Exercise 5

This is the easiest one so far. Simply add a call to `lock_kernel()` or `unlock_kernel()` to the location specified.

In `kern/init.c:i386_init()`:

```diff
@@ -44,2 +44,2 @@ i386_init(void)
        // Acquire the big kernel lock before waking up APs
-       // Your code here:
+       lock_kernel();
```

In `kern/init.c:i386_init()`:

```diff
@@ -107,5 +107,5 @@ mp_main(void)
        // Now that we have finished some basic setup, call sched_yield()
        // to start running processes on this CPU.  But make sure that
        // only one CPU can enter the scheduler at a time!
-       //
-       // Your code here:
+       lock_kernel();
+       sched_yield();
```

In `kern/trap.c:trap()`:

```diff
@@ -276,5 +275,5 @@ trap(struct Trapframe *tf)
                // Trapped from user mode.
                // Acquire the big kernel lock before doing any
                // serious kernel work.
-               // LAB 4: Your code here.
+               lock_kernel();
                assert(curenv);
```

In `kern/env.c:env_run()`:

```diff
@@ -547,5 +547,6 @@ env_run(struct Env *e)
        curenv = e;
        e->env_status = ENV_RUNNING;
        e->env_runs++;
+       unlock_kernel();
        lcr3(PADDR(e->env_pgdir));
        env_pop_tf(&e->env_tf);
```


## Question 2

When an exception or interrupt is triggered, the kernel will push some information onto the stack (here it is TrapFrame), before the trap handler acquires the big kernel lock. So other CPUs can push a TrapFrame when one CPU is in kernel mode. If all CPUs share one kernel stack, something like this may happen. CPU0 is handling a trap, at this time, a trap on CPU1 is triggered and it pushes its TrapFrame onto the stack. When CPU0 has done the job, it will pop the stack pushed by CPU1 instead of its own. In this situation, the kernel stack will be corrupted, and the control flow will not be transferred as expected.


## Exercise 6

Implement round-robin scheduling in `sched_yield()` in `kern/sched.c` is not hard, we need to find the first runnable environment after `curenv` in `envs[]`, if not found, search from 0 to `curenv`, as the comment indicates. Notice that the `curenv` may be null. Since `env_run()` does not return, a flag variable is not needed here.

```c
void
sched_yield(void)
{
	struct Env *idle = curenv;
	int idle_envid = (idle == NULL) ? -1 : ENVX(idle->env_id);
	int i;

	// search envs after idle
	for (i = idle_envid + 1; i < NENV; i++) {
		if (envs[i].env_status == ENV_RUNNABLE) {
			env_run(&envs[i]);
		}
	}

	// find from 1st env if not found
	for (i = 0; i < idle_envid; i++) {;
		if (envs[i].env_status == ENV_RUNNABLE) {
			env_run(&envs[i]);
		}
	}

	// if still not found, try idle
	if(idle != NULL && idle->env_status == ENV_RUNNING) {
		env_run(idle);
	}

	// sched_halt never returns
	sched_halt();
}
```

Then modify `syscall()` in `kern/syscall.c` to dispatch `sys_yield()`. Simply add a case will do this.

```c
case SYS_yield:
	sys_yield();
	return 0;
```

And don't forget to remove this in `kern/init.c:mp_main()`, though it won't cause any trouble if it is not removed.

```c
// Remove this after you finish Exercise 6
for (;;);
```

To test this, we are asked to create three environments that all run the program `user/yield.c`. So this code should be added to `kern/init.c:i386_init()`. Remember to comment out the `user_primes` test as `fork()` is not implemented so far.

```c
#if defined(TEST)
	// Don't touch -- used by grading script!
	ENV_CREATE(TEST, ENV_TYPE_USER);
#else
	// Touch all you want.
	ENV_CREATE(user_yield, ENV_TYPE_USER);
	ENV_CREATE(user_yield, ENV_TYPE_USER);
	ENV_CREATE(user_yield, ENV_TYPE_USER);
	// ENV_CREATE(user_primes, ENV_TYPE_USER);
#endif // TEST*
```

Now run `make qemu CPUS=x` (x is the number of CPUs) will create 3 environments, each one will be switched 5 times, and finally invokes the kernel monitor.


## Question 3

In `env_setup_vm()`, the comment says the virtual address space of all environments is identical from `UTOP` to `UVPT`, as well as the address space of the kernel. The virtual address of `e` is always the same whatever the address space it is, so it can be dereferenced both before and after the addressing switch.


## Question 4

The context switch needs to ensure the environment can resume the execution at exactly where it stops as the switch has never happened. So all the registers need to be saved. They are pushed onto the stack when it triggers `sys_yield()` syscall, and then the trap handler (here it is `kern/trap.c:trap()`) will save them in `env_tf`. And they are restored by `env_pop_tf()` when `env_run()` is executed.


## Exercise 7

This exercise requires us to implement several functions. The codes are long but not very difficult since most of them are for handling errors.

Let's start with `sys_exofork()`, possibly the most difficult one here because this syscall is called once but returns twice and it should be tweaked to return 0 to the child.

To figure out how this syscall is used, we need to take a look at `user/dumbfork.c`. This parent will call `sys_exofork`, the kernel will make a copy of the `Env` structure of itself for the child, and set the child's status to `ENV_NOT_RUNNABLE`. Now the child is created and stopped. `sys_exofork` will put the child's envid in the `eax` register according to the calling convention for return value. Then the parent will make a full copy of its memory to the child and set the child to be runnable. After that, the round-robin scheduling will run the child using `env_run()` at some time. When the child process is resumed, it will try to read the return value from `eax`, and `eax` is saved in its `Env` structure. So to return 0 to the child, we need to modify the value of saved `eax` register of the child.

With the analysis above and the comment, it's not hard to implement this function.

```c
static envid_t
sys_exofork(void)
{
	struct Env *e;
	int r;

	if ((r = env_alloc(&e, curenv->env_id)) != 0) {
		return r;
	}
	e->env_status = ENV_NOT_RUNNABLE;
	e->env_tf = curenv->env_tf;
	e->env_tf.tf_regs.reg_eax = 0;  // return 0 to child
	return e->env_id;
}
```

`sys_env_set_status()` is a easy one. What need to do is to check the parameters and simply alter the status.

```c
static int
sys_env_set_status(envid_t envid, int status)
{
	struct Env *e;
	int r;

	if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) {
		return -E_INVAL;
	}
	if ((r = envid2env(envid, &e, 1)) != 0) {
		return r;
	}
	e->env_status = status;
	return 0;
}
```

`sys_page_alloc()` is also easy. Here we need to use `page_alloc()` and `page_insert()` implemented in Lab 2 to allocate a page for the env, and we need to check the parameters first, as the comment says.

```c
static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
	struct Env *e;
	struct PageInfo *pp;
	int r;

	if ((uint32_t)va >= UTOP || PGOFF(va) != 0) {
		return -E_INVAL;
	}
	if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P)) {
		return -E_INVAL;
	}
	if ((perm & ~(PTE_SYSCALL)) != 0) {
		return -E_INVAL;
	}
	if ((r = envid2env(envid, &e, 1)) != 0) {
		return r;
	}
	if((pp = page_alloc(perm)) == NULL) {
		return -E_NO_MEM;
	}
	if((r = page_insert(e->env_pgdir, pp, va, perm)) != 0) {
		page_free(pp);
		return -E_NO_MEM;
	}
	return 0;
}
```

`sys_page_map()` is a little long, but not difficult. Here we need to use `page_lookup()` and `page_insert()` to map a page to another position. Follow the comment and make sure you have checked all the errors provided.

```c
static int
sys_page_map(envid_t srcenvid, void *srcva,
	     envid_t dstenvid, void *dstva, int perm)
{
	struct Env *srcenv, *dstenv;
	struct PageInfo *pp;
	pte_t *pte;
	int r;

	if ((uint32_t)srcva >= UTOP || PGOFF(srcva) != 0) {
		return -E_INVAL;
	}
	if ((uint32_t)dstva >= UTOP || PGOFF(dstva) != 0) {
		return -E_INVAL;
	}
	if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P)) {
		return -E_INVAL;
	}
	if ((perm & ~(PTE_SYSCALL)) != 0) {
		return -E_INVAL;
	}
	if ((r = envid2env(srcenvid, &srcenv, 1)) != 0) {
		return r;
	}
	if ((r = envid2env(dstenvid, &dstenv, 1)) != 0) {
		return r;
	}
	if ((pp = page_lookup(srcenv->env_pgdir, srcva, &pte)) == NULL) {
		return -E_INVAL;
	}
	if ((*pte & PTE_W) == 0 && (perm & PTE_W) == PTE_W) {
		return -E_INVAL;
	}
	if ((r = page_insert(dstenv->env_pgdir, pp, dstva, perm)) != 0) {
		return r;
	}
	return 0;
}
```

The last one `sys_page_unmap()` is another easy one, just write follow the comment.

```c
static int
sys_page_unmap(envid_t envid, void *va)
{
	struct Env *e;
	int r;

	if ((uint32_t)va >= UTOP || PGOFF(va) != 0) {
		return -E_INVAL;
	}
	if ((r = envid2env(envid, &e, 1)) != 0) {
		return r;
	}
	page_remove(e->env_pgdir, va);
	return 0;
}
```

At last, don't forget to modify `syscall()` in `kern/syscall.c` to dispatch the syscalls above.

```c
case SYS_exofork:
	return sys_exofork();
case SYS_env_set_status:
	return sys_env_set_status(a1, a2);
case SYS_page_alloc:
	return sys_page_alloc(a1, (void *)a2, a3);
case SYS_page_map:
	return sys_page_map(a1, (void *)a2, a3, (void *)a4, a5);
case SYS_page_unmap:
	return sys_page_unmap(a1, (void *)a2);
```

Now `dumbfork` test in `make grade` will be passed.


## Exercise 8

Now it comes to Part B, the hardest part of this lab, also the hardest part so far. But this exercise is as simple as the previous one. Read the comment thoroughly will give you all you need.

```c
static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
	struct Env *e;
	int r;

	if ((r = envid2env(envid, &e, 1)) != 0) {
		return r;
	}
	e->env_pgfault_upcall = func;
	return 0;
}
```

Also, don't forget to add a case in `syscall()`.

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


## Exercise 9

Now we need to set up the `UTrapframe` structure and save the trap-time state in it for the copy-on-write page fault handler. Though the comment in `page_fault_handler()` is very long, it worth reading as such a long comment contains almost everything we need. You should also read the lab page thoroughly. What we need to do can be concluded into the 5 steps following:

1. Check whether the environment's page fault upcall exists. If not, destroy the environment.

2. Find where the page fault stack frame `UTrapframe` should be located. If it is not caused by another page fault, it is right below `UXSTACKTOP`. Or it is below the previous stack frame, a 32-bit should be pushed first. To test whether `tf->tf_esp` is already on the user exception stack, check whether it is in the range between `UXSTACKTOP-PGSIZE` and `UXSTACKTOP-1`, inclusive.

3. Check whether the environment allocated a page for its exception stack, the permission to write it and whether the exception stack overflows. If one of these situations occurs, destroy the environment. This can be done with calling `user_mem_assert()` as the hint says.

4. Set up the `UTrapframe`, copy the register values, error code and `fault_va` into it. Most of these values are in the `TrapFrame` and `fault_va` is provided.

5. Run the page fault handler with `UTrapframe` in user mode. So we need to modify the `esp` and `eip` of `TrapFrame` and call `env_run()` to give control back to the user environment and run the page fault handler.

Here is my code:

```c
void
page_fault_handler(struct Trapframe *tf)
{
	uint32_t fault_va;

	// Read processor's CR2 register to find the faulting address
	fault_va = rcr2();

	// Handle kernel-mode page faults.
	if ((tf->tf_cs & 0x3) == 0) {
		panic("page_fault_handler: page fault in kernel mode");
	}

	// We've already handled kernel-mode exceptions, so if we get here,
	// the page fault happened in user mode.
	if (curenv->env_pgfault_upcall) {
		struct UTrapframe *utf;

		// Determine the location
		if (tf->tf_esp >= UXSTACKTOP - PGSIZE && tf->tf_esp < UXSTACKTOP) {
			*(uint32_t *)(tf->tf_esp - 4) = 0;  // push an empty 32-bit word
			utf = (struct UTrapframe *)(tf->tf_esp - 4 - sizeof(struct UTrapframe));
		} else {
			utf = (struct UTrapframe *)(UXSTACKTOP - sizeof(struct UTrapframe));
		}

		// Check permission
		user_mem_assert(curenv, (void *)utf, sizeof(struct UTrapframe), PTE_W | PTE_U);

		// Set up the user trap frame
		utf->utf_esp = tf->tf_esp;
		utf->utf_eflags = tf->tf_eflags;
		utf->utf_eip = tf->tf_eip;
		utf->utf_regs = tf->tf_regs;
		utf->utf_err = tf->tf_err;
		utf->utf_fault_va = fault_va;

		// Switch the environment
		tf->tf_esp = (uint32_t)utf;
		tf->tf_eip = (uint32_t)curenv->env_pgfault_upcall;
		env_run(curenv);
	}

	// Destroy the environment that caused the fault.
	cprintf("[%08x] user fault va %08x ip %08x\n",
		curenv->env_id, fault_va, tf->tf_eip);
	print_trapframe(tf);
	env_destroy(curenv);
}

```

There is also a simple question to answer, "What happens if the user environment runs out of space on the exception stack?". The comment of `page_fault_handler()` has already given us the answer. If it runs out of space, it cannot pass the `user_mem_assert()` and the function will destroy the environment that caused the fault.


## Exercise 10

This is really a hard one since what we need to write here is all x86 assembly code here. The `_pgfault_upcall` routine in `lib/pfentry.S` has already implemented the procedure to call the page fault handler. What we need to write here is the procedure to return to the original point in the user code that caused the page fault, so we must have a clear view of how a control transfer is performed at the machine level.

The following figure from [Figure 3.26 of CS:APP3e](http://csapp.cs.cmu.edu/3e/figures.html) shows how a usual call-return procedure is performed on x86-64. x86 is very similar to this, except for the register name.

![call-ret.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/427908/7060b32f-dc70-3032-b9ac-18fd97e0565d.jpeg)

The `call` instruction will push the next instruction of the caller to be executed in `eip` onto the stack, then create a new stack frame for the callee. The callee will push registers to save like `ebp` onto the stack. After the callee has done its job, it will pop these saved registers back, and use a `ret` instruction to give control back to the caller. The `ret` works the same as `pop %eip`.

Here since it is not a usual call-return. We need to modify the caller's stack frame to "push" the `eip` onto the stack frame of the caller. That is to say, we need to enlarge the stack of the caller for 4 bytes to put the saved `eip`. And that's why we need the empty 32-bit word for nested page faults. Then we need to manually pop back the saved registers in a user exception stack frame, and finally, give control back to where the page fault is encountered.

So what we need to adjust the stack like this:

```
Before:
   Previous Frame                 User Trap Frame
+------------------+            +------------------+
| stack data       |      +---- | trap-time esp    |
| ...              |      |     | trap-time eflags |
+------------------+ <----+     | trap-time eip    |
                                | trap-time eax    |  
                                | ...              |
                                | trap-time esi    |
                                | trap-time edi    |  
                                | tf_err           |
                                | fault_va         |
                                +------------------+  <-- %esp
After:
   Previous Frame                 User Trap Frame
+------------------+            +------------------+
| stack data       |      +---- | trap-time esp-4  |
| ...              |      |     | trap-time eflags |
| trap-time eip    |      |     | trap-time eip    |
+------------------+ <----+     | trap-time eax    |  
                                | ...              |
                                | trap-time esi    |
                                | trap-time edi    |  
                                | tf_err           |
                                | fault_va         |
                                +------------------+  <-- %esp
```

Beware that previous stack frame can either a normal user stack frame or an exception stack frame. So we cannot use move the trap-time eip directly to `0x34(%esp)`.

And this is my implementation.

```asm
// Save trap-time eip next to previous stack (that's why we need the empty dword)
movl 0x30(%esp), %ecx    // save trap-time esp in ecx
subl $4, %ecx            // enlarge the previous stack for 4 bytes
movl %ecx, 0x30(%esp)    // write the modified esp back
movl 0x28(%esp), %edx    // save trap-time eip in edx
movl %edx, (%ecx)        // save eip at new esp for return

// Restore the trap-time registers.  After you do this, you
// can no longer modify any general-purpose registers.
addl $8, %esp            // skip fault_va and tf_err
popal                    // pop PushRegs

// Restore eflags from the stack.  After you do this, you can
// no longer use arithmetic operations or anything else that
// modifies eflags.
addl $4, %esp            // skip eip
popfl                    // pop eflags

// Switch back to the adjusted trap-time stack.
pop %esp

// Return to re-execute the instruction that faulted.
ret
```

## Exercise 11

This exercise is not difficult. Since it is in user mode, we need to use the syscalls implemented in Exercise 7 & 8 to implement this. Also remember to handle errors.

```c
void
set_pgfault_handler(void (*handler)(struct UTrapframe *utf))
{
	int r;

	if (_pgfault_handler == 0) {
		// First time through!
		if ((r = sys_page_alloc(thisenv->env_id, (void *)(UXSTACKTOP - PGSIZE), PTE_W | PTE_U | PTE_P)) != 0) {
			panic("set_pgfault_handler: %e", r);
		}
		if ((r = sys_env_set_pgfault_upcall(thisenv->env_id, _pgfault_upcall)) != 0) {
			panic("set_pgfault_handler: %e", r);
		}
	}

	// Save handler pointer for assembly to call.
	_pgfault_handler = handler;
}
```

Now run `make grade` we shall pass all tests in Part B except for `forktree`.


## Exercise 12

After doing so much prepare work, now we are going to implement the copy-on-write fork.

Before coding, it is suggested to take a look at the `uvpt[]` and `uvpd[]` we will use later here. Here, JOS uses a [clever mapping trick](https://pdos.csail.mit.edu/6.828/2018/labs/lab4/uvpt.html) which maps the page table to `UVPT` so that user code can read the PTE and PDE contents. x86 processors will read the 2 level page table to access a virtual memory address. If we access the address at `UVPT+i`, it will return us the PTE, and the offset `i` is the page number. For example, if we access `0xef410100`, the processor will first read the PDE, the `0x3bd` entry of page directory, then the PTE, the `0x10` entry of page table, then the content, the `0x100` entry of the page. Here the PDE points to the page table, so the PTE being read is the same as PDE, and the content is the PTE of `0x04040000~0x04040fff`. The offset is the DIR and the PAGE part of the virtual address, so it is the page number. In the example, `uvpt[0x10100]` is the PTE for `0x04040000~0x04040fff`. Specially, if we access `uvpt + UVPT >> 10`, it will return the PDE since the content is still the PDE, and the offset here is the page directory index.

Below shows what is at `UVPT`:

```
     0                 4                 8                                ...
     +-----------------+-----------------+-----+----------------------+-----+
UVPT | PTEs for 0x0000 | PTEs for 0x1000 | ... | PTEs for UVPT / PDEs | ... | UVPT+PGSIZE
     +-----------------+-----------------+-----+----------------------+-----+
     ^ uvpt[]                                  ^ uvpd[]
```

It is very confusing and hard to understand. The following figure may help you understand it.'

![vpt.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/427908/404a1909-a034-1ebd-9bda-f0fad23bee78.png)

In this figure, the circular arrow is followed once for uvpt[] and twice for uvpd[].

Now we can proceed to coding. The first one to implement is `fork()`. It is very similar to `dumbfork()`, except how the copy is performed. As the comment says we also need to set up page fault handler, create a child and allocate a new page for the child's user exception stack. A page fault upcall also needs to be set, and that's we will easily neglect here, including me. And here is my implemention.

```c
envid_t
fork(void)
{
	envid_t envid;
	uint32_t addr;
	int r;

	set_pgfault_handler(pgfault);
	envid = sys_exofork();
	if (envid < 0) {
		panic("sys_exofork: %e", envid);
	}
	if (envid == 0) {
		// fix thisenv in child
		thisenv = &envs[ENVX(sys_getenvid())];
		return 0;
	}

	// copy the address space mappings to child
	for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
		if ((uvpd[PDX(addr)] & PTE_P) == PTE_P && (uvpt[PGNUM(addr)] & PTE_P) == PTE_P) {
			duppage(envid, PGNUM(addr));
		}
	}

	// allocate new page for child's user exception stack
	void _pgfault_upcall();

	if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP - PGSIZE), PTE_W | PTE_U | PTE_P)) != 0) {
		panic("fork: %e", r);
	}
	if ((r = sys_env_set_pgfault_upcall(envid, _pgfault_upcall)) != 0) {
		panic("fork: %e", r);
	}

	// mark the child as runnable
	if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) != 0)
		panic("fork: %e", r);

	return envid;
}
```

`duppage()` is not difficult. Here we map the page for the child environment. If the page is writable, we need to map it in both environments as a COW page so that they won't interfere with each other, and if it is read-only, simply map it in the child. Here we should use the syscalls we implemented in Exercise 8.

```c
static int
duppage(envid_t envid, unsigned pn)
{
	envid_t parent_envid = sys_getenvid();
	void *va = (void *)(pn * PGSIZE);
	int r;

	if ((uvpt[pn] & PTE_W) == PTE_W || (uvpt[pn] & PTE_COW) == PTE_COW) {
		if ((r = sys_page_map(parent_envid, va, envid, va, PTE_COW | PTE_U | PTE_P)) != 0) {
			panic("duppage: %e", r);
		}
		if ((r = sys_page_map(parent_envid, va, parent_envid, va, PTE_COW | PTE_U | PTE_P)) != 0) {
			panic("duppage: %e", r);
		}
	} else {
		if ((r = sys_page_map(parent_envid, va, envid, va, PTE_U | PTE_P)) != 0) {
			panic("duppage: %e", r);
		}
	}

	return 0;
}
```

The last one `pgfault()` uses syscalls to copy the page on page faults. The comment provides many hints so it is easy to implement.

```c
static void
pgfault(struct UTrapframe *utf)
{
	void *addr = (void *) utf->utf_fault_va;
	uint32_t err = utf->utf_err;
	pte_t pte = uvpt[PGNUM(addr)];
	envid_t envid = sys_getenvid();
	int r;

	if ((err & FEC_WR) == 0 || (pte & PTE_COW) == 0) {
		panic("pgfault: bad faulting access\n");
	}
	if ((r = sys_page_alloc(envid, PFTEMP, PTE_W | PTE_U | PTE_P)) != 0) {
		panic("pgfault: %e", r);
	}
	memcpy(PFTEMP, ROUNDDOWN(addr, PGSIZE), PGSIZE);
	if ((r = sys_page_map(envid, PFTEMP, envid, ROUNDDOWN(addr, PGSIZE), PTE_W | PTE_U | PTE_P)) != 0) {
		panic("pgfault: %e", r);
	}
	if ((r = sys_page_unmap(envid, PFTEMP)) != 0) {
		panic("pgfault: %e", r);
	}
}
```

Now `forktree` test in `make grade` will be passed.


## Exercise 13

This part is much simpler than Part B. This exercise requires to add more interrupt handler in `kern/trapentry.S` and `kern/trap.c:trap()`. Adding a handler is very simple. If you forget how to do this, see [Exercise 4 of Lab 3](https://qiita.com/kagurazakakotori/items/334ab87a6eeb76711936#exercise-4).

[Section 6.15 of Intel® 64 and IA-32 Architectures Software Developer's Manual: Volume 3](https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-system-programming-manual-325384.html) indicates that user-defined interrupts don't contain an error code.

In `kern/trapentry.S`:

```diff
@@ -66,3 +66,9 @@ TRAPHANDLER(th_align, T_ALIGN)
 TRAPHANDLER_NOEC(th_mchk, T_MCHK)
 TRAPHANDLER_NOEC(th_simderr, T_SIMDERR)
 TRAPHANDLER_NOEC(th_syscall, T_SYSCALL)
+TRAPHANDLER_NOEC(th_irq_timer, IRQ_OFFSET + IRQ_TIMER)
+TRAPHANDLER_NOEC(th_irq_kbd, IRQ_OFFSET + IRQ_KBD)
+TRAPHANDLER_NOEC(th_irq_serial, IRQ_OFFSET + IRQ_SERIAL)
+TRAPHANDLER_NOEC(th_irq_spurious, IRQ_OFFSET + IRQ_SPURIOUS)
+TRAPHANDLER_NOEC(th_irq_ide, IRQ_OFFSET + IRQ_IDE)
+TRAPHANDLER_NOEC(th_irq_error, IRQ_OFFSET + IRQ_ERROR)
```

In `kern/trap.c`

```diff
@@ -90,3 +90,9 @@ trap_init(void)
        void th_mchk();
        void th_simderr();
        void th_syscall();
+       void th_irq_timer();
+       void th_irq_kbd();
+       void th_irq_serial();
+       void th_irq_spurious();
+       void th_irq_ide();
+       void th_irq_error();
@@ -110,3 +116,9 @@ trap_init(void)
        SETGATE(idt[T_MCHK], 0, GD_KT, &th_mchk, 0);
        SETGATE(idt[T_SIMDERR], 0, GD_KT, &th_simderr, 0);
        SETGATE(idt[T_SYSCALL], 0, GD_KT, &th_syscall, 3);
+       SETGATE(idt[IRQ_OFFSET + IRQ_TIMER], 0, GD_KT, &th_irq_timer, 0);
+       SETGATE(idt[IRQ_OFFSET + IRQ_KBD], 0, GD_KT, &th_irq_kbd, 0);
+       SETGATE(idt[IRQ_OFFSET + IRQ_SERIAL], 0, GD_KT, &th_irq_serial, 0);
+       SETGATE(idt[IRQ_OFFSET + IRQ_SPURIOUS], 0, GD_KT, &th_irq_spurious, 0);
+       SETGATE(idt[IRQ_OFFSET + IRQ_IDE], 0, GD_KT, &th_irq_ide, 0);
+       SETGATE(idt[IRQ_OFFSET + IRQ_ERROR], 0, GD_KT, &th_irq_error, 0);
```

We also need to enable interrupts in user mode. This can be done by adding this to `kern/env.c:env_alloc()`.

```diff
@@ -256,2 +256,2 @@ env_alloc(struct Env **newenv_store, envid_t parent_id)
        // Enable interrupts while in user mode.
-       // LAB 4: Your code here.
+       e->env_tf.tf_eflags |= FL_IF;
```

And don't forget to uncomment the `sti` instruction in `kern/sched.c:sched_halt()` so that idle CPUs unmask interrupts.


## Exercise 14

Now we are asked to modify `kern/trap.c:trap_dispatch()` to call `sched_yield()` to handle a clock interrupt. Simply add a case would do this. Remember to call `lapic_eoi()` as the comment says.

```c
case IRQ_OFFSET + IRQ_TIMER:
	lapic_eoi();
	sched_yield();
	return;
```

Now it will pass `spin` and `stresssched` test if we run `make grade`.


## Exercise 15

Implementing `sys_ipc_recv()` in `kern/syscall.c` is relativly easy. Althogh the comment says we need to give up the CPU, we do not need to explicitly call `sched_yield()` to do this since marking the environment not runnable will do this implicitly, and if we call it, the return value of syscall cannot be passed to the user environment.

```c
static int
sys_ipc_recv(void *dstva)
{
	if ((uint32_t)dstva < UTOP && PGOFF(dstva) != 0) {
		return -E_INVAL;
	}
	curenv->env_ipc_recving = 1;
	curenv->env_ipc_dstva = dstva;
	curenv->env_status = ENV_NOT_RUNNABLE;
	return 0;
}
```

`sys_ipc_try_send()` is very simlar to `sys_page_alloc()` and `sys_page_map()` we implemented in Exercise 7. And we should carefully check all the situations as the comment says. Here it should not panic if `srcva >= UTOP`.

One error was not clearly described in the comment. `-E_INVAL` should be returned if `(perm & PTE_W)` *and `srcva < UTOP`*, but `srcva` is read-only in the current environment's address space. Though here it won't make any trouble, it will lead to a bug in Exercise 6 of Lab 5, and it is not easy to find this bug. (Luckily, I found it :)
 
```c
static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
	struct Env *e;
	struct PageInfo *pp;
	pte_t *pte;
	int r;

	if ((r = envid2env(envid, &e, 0)) != 0) {
		return r;
	}
	if (e->env_ipc_recving == 0) {
		return -E_IPC_NOT_RECV;
	}
	if ((uint32_t)srcva < UTOP) {
		if (PGOFF(srcva) != 0) {
			return -E_INVAL;
		}
		if ((perm & (PTE_U | PTE_P)) != (PTE_U | PTE_P)) {
			return -E_INVAL;
		}
		if ((perm & ~(PTE_SYSCALL)) != 0) {
			return -E_INVAL;
		}
		if ((pp = page_lookup(curenv->env_pgdir, srcva, &pte)) == NULL) {
			return -E_INVAL;
		}
		if ((*pte & PTE_W) == 0 && (perm & PTE_W) == PTE_W) {
			return -E_INVAL;
		}
		if ((r = page_insert(e->env_pgdir, pp, e->env_ipc_dstva, perm)) != 0) {
			return r;
		}
		e->env_ipc_perm = perm;
	} else {
		e->env_ipc_perm = 0;
	}
	e->env_ipc_recving = 0;
	e->env_ipc_from = curenv->env_id;
	e->env_ipc_value = value;
	e->env_status = ENV_RUNNABLE;
	return 0;
}
```

Then add some dispatchers in `syscall()`.

```c
case SYS_ipc_recv:
	return sys_ipc_recv((void *)a1);
case SYS_ipc_try_send:
	return sys_ipc_try_send(a1, a2, (void *)a3, a4);
```

Now we are going to implement the APIs for user programs in `lib/ipc.c`. `ipc_recv()` is the wrapper function for `sys_ipc_recv()`. The comment provides the detailed procedure. And if `pg` is null, we should pass `UTOP` as `pg` since the syscalls will just ignore the address and it will not panic the kernel.

```c
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
	int r;

	if (pg == NULL) {
		pg = (void *)UTOP;
	}
	if ((r = sys_ipc_recv(pg)) < 0) {
		if (from_env_store != NULL) {
			*from_env_store = 0;
		}
		if (perm_store != NULL) {
			*perm_store = 0;
		}
		return r;
	}
	if (from_env_store != NULL) {
		*from_env_store = thisenv->env_ipc_from;
	}
	if (perm_store != NULL) {
		*perm_store = thisenv->env_ipc_perm;
	}
	return thisenv->env_ipc_value;
}
```

`ipc_send()` is very similar to `ipc_recv()`. Because it keeps trying until it succeeds and it should try at least once, a do-while loop is perfectly suitable here, though do-while loops are seldom used in most cases.

```c
void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
	int r;

	if (pg == NULL) {
		pg = (void *)UTOP;
	}
	do {
		r = sys_ipc_try_send(to_env, val, pg, perm);
		if (r < 0 && r != -E_IPC_NOT_RECV) {
			panic("ipc_send: %e", r);
		}
		sys_yield();
	} while(r != 0);
}
```

Now run `make grade` we shall pass all the tests and get 80 points like this:

```
dumbfork: OK (3.0s) 
Part A score: 5/5

faultread: OK (2.1s) 
faultwrite: OK (2.1s) 
faultdie: OK (2.1s) 
faultregs: OK (2.1s) 
faultalloc: OK (2.0s) 
faultallocbad: OK (2.9s) 
faultnostack: OK (3.1s) 
faultbadhandler: OK (3.0s) 
faultevilhandler: OK (3.1s) 
forktree: OK (2.2s) 
Part B score: 50/50

spin: OK (2.9s) 
stresssched: OK (3.6s) 
sendpage: OK (3.1s) 
pingpong: OK (3.2s) 
primes: OK (6.9s) 
Part C score: 25/25

Score: 80/80
```