HW6: System Calls and a User Process

This homework asks you to extend your "hello world" kernel with support for loading and executing a user process (as well as support for system calls). This assignments builds on top of your previous HW3, HW4, and HW5 submissions, i.e., you will extend the code of HW5. If you don't have a working HW5 submission talk to us.

Technically, you can do this assignment on any operating system that supports the Unix API and can run Qemu (CADE machines, your laptop that runs Linux or Linux VM, and even MacOS, etc.). You don't need to set up xv6 for this assignment, but if you're running on CADE you'll have to install QEMU, see QEMU setup instructions. Submit your programs and the shell through Gradescope (see instructions at the bottom of this page).

NOTE: YOU CANNOT PUBLICLY RELEASE SOLUTIONS TO THIS HOMEWORK. It's ok to show your work to your future employer as a private Git repo, however any public release is prohibited.

Part 1 - Syscall

User program

You will be extending your previous "hello world" kernel. Since we will be building a user process we will need a new Makefile. Download it here: Makefile and .gdbinit.tmpl. Note, if you run this on cade, change to correct grub command on line 75 of Makefile.

Download the following files: syscall.c , syscall.h , user.h , usys.asm , and user.c . Create user directory.

Add everything to your proj so it look like this:

- boot/
- Makefile
- syscall.c
- syscall.h
- ... other .c .h .asm files 
- user/
	  - user.c
	  - user.h
	  - usys.asm

The big picture of this project is to create our first process and be able to run a user program. Let us take the top down approach, and understand what a user program is. A user program are just a bunch of instructions that will be running in a special mode of CPU (ring 3). This means that

To be more specific, in order to run in user mode, we need to manage three data structures

In a typical OS, user program can enter the kernel through

You can implement or design any system call you want, but the main goal is to provide isolation for the user program for certain important functionalities. Image that you install a minesweeper on your computer, and it have unlimited access to your network card and disk. Not good.

In our toy kernel, we will only implement two system calls: print() and exit(). The print function will, as in its name, print to console. and exit function is another way to return from user to kernel permantly. Those syscall, by no way, is complete for a fully function kernel, but it will suffice for this homework.

In user.c, add following code (this is a very small user program, it prints "hello user" on the screen and exits. But, hey, if you want to keep going, you can build anything you like (a realistic project is something like Tetris)

#include "user.h"

int main(void) 
{
	print("hello user\n"); 
	exit();
}

Now it is time to add definition for the two syscall we just add. In usys.asm, we already implemented print for you. Observe, this is incredly simple, as user's job is simply move a number into eax register, and then call interrupt at a specific number. The number T_SYSYCALL indicates the IRQ number. The main idea here is to interrupt to kernel at specific IRQ number, and have kernel to handle that as syscall.

global print
print:
	mov eax, SYS_print
	int T_SYSCALL
	ret

Your job here is to finish the implementation of usys.asm by implementing exit in similar manner. Once it is done, you can call make user to check if there is any compilation error.

Trap: Revisited

In order to supprot system calls in our minimal kernel, we need to add a couple of things. Let us first head to vectors.asm. You should already have some code in this file from previous homework. Now it is time to test your knowledge. In the user program, we wrote this line

int T_SYSCALL

Once you are modifying vectors.asm, now go to trap.c. You need to do two things

1. Add entry correspond to T_SYSCALL for IDT with DPL_USER permission and select KCODE segment
2. Handle tf->trapno for T_SYSCALL to invoke method syscall .

At last, comment out printk(".") in your timer interrupt handling code.

Syscall

Let us go take a look at the syscall function in syscall.c and you should see something like this

.... 

static int (*syscalls[])(void) = {
[SYS_print]    sys_print,
// TODO
};

void
syscall(struct trapframe *tf)
{
	uint num;

	current->tf = tf;

	num = current->tf->eax;
	if(num > 0 && num <= 2 && syscalls[num]) {

	// TODO: Invoke syscall correct syscall base on corresponding table entry
	// put the return result onto trap frame eax. 

	} else {
	current->tf->eax = -1;
	}
}

The syscall function will get current process (more on this later, now just see it as a global variable). The syscall table (variable named syscalls ) is a just an array of function pointers with its function signture

int func_name (void);

Recall that earlier in the user program, we wrote this line

mov eax, #SOME_NUMBER

Your job here is finish syscall function implementation and add sys_exit to the syscall table. This will complete the path of syscall from user to kernel.

Part 2 - Process

Download elf.h , proc.c , proc.h , and swtch.asm . Add everything to your code base.

We need to set up task state segment, add this to your mmu.h

// Task state segment format
struct taskstate {
	uint link;         // Old ts selector
	uint esp0;         // Stack pointers and segment selectors
	ushort ss0;        //   after an increase in privilege level
	ushort padding1;
	uint *esp1;
	ushort ss1;
	ushort padding2;
	uint *esp2;
	ushort ss2;
	ushort padding3;
	void *cr3;         // Page directory base
	uint *eip;         // Saved state from last task switch
	uint eflags;
	uint eax;          // More saved state (registers)
	uint ecx;
	uint edx;
	uint ebx;
	uint *esp;
	uint *ebp;
	uint esi;
	uint edi;
	ushort es;         // Even more saved state (segment selectors)
	ushort padding4;
	ushort cs;
	ushort padding5;
	ushort ss;
	ushort padding6;
	ushort ds;
	ushort padding7;
	ushort fs;
	ushort padding8;
	ushort gs;
	ushort padding9;
	ushort ldt;
	ushort padding10;
	ushort t;          // Trap on task switch
	ushort iomb;       // I/O map base address
};

#define SEG16(type, base, lim, dpl) (struct segdesc)  \
{ (lim) & 0xffff, (uint)(base) & 0xffff,              \
	((uint)(base) >> 16) & 0xff, type, 1, dpl, 1,       \
	(uint)(lim) >> 16, 0, 0, 1, 0, (uint)(base) >> 24 }

We also need to expand our GDT to set up user level abstraction. Go to your mmu.h. Replace and Add new

#define SEG_KCODE 1  // kernel code
#define SEG_KDATA 2  // kernel data+stack
#define SEG_UCODE 3  // user code
#define SEG_UDATA 4  // user data+stack
#define SEG_TSS   5  // this process's task state
#define NSEGS     6
#define DPL_USER  3 

Then, modify your GDT to be

struct segdesc gdt[NSEGS] = {
	[SEG_KCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, 0),
	[SEG_KDATA] = SEG(STA_W, 0, 0xffffffff, 0),
	[SEG_UCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, DPL_USER),
	[SEG_UDATA] = SEG(STA_W, 0, 0xffffffff, DPL_USER),
};

Main

Head to your main.c . Add two function userinit and run_current in main, then add paging set up like this:

#define K_MAX_ADDR 0x2000000
int main(void)
{
	int sum = 0;

	printk("Hello from main\n");

	// Free physical pages up to kernel for kernel to use
	for (uint page = PGROUNDUP((uint)end); page < K_MAX_ADDR; page += PGSIZE)
		page_free(page);

	uint flag = PTE_P + PTE_W;
	for (unsigned int va = 0; va < K_MAX_ADDR; va += PGSIZE)
		mmap(entry_pgdir, va, va, flag);

	// Map PIC
	mmap(entry_pgdir, DEFAULT_IOAPIC, DEFAULT_IOAPIC, flag);
	mmap(entry_pgdir, DEFAULT_LAPIC, DEFAULT_LAPIC, flag);

	write_cr3((uint)&entry_pgdir);
	
	int cr0 = read_cr0(); 
	cr0 |= CR0_PG;
	write_cr0(cr0);

	uartinit(); 
	initpics();
	tvinit();
	
	printk("init user\n"); 

	userinit(entry_pgdir);
	run_current(); 

	printk("current exited\n");

	while(1)
		halt(); 
	return sum; 
}
	

Both function definition are in proc.c file. userinit function will read the elf file to create a user process. and run_current function will context swtch to the only process. You don't need to touch run_current function. Your job will be understanding userinit and finish its implementation.

userinit is a long function, but it is mainly two part. The first part is elf loading. we first find the elf binary start address, which is a symbol that been added onto the kernel when we compile the user program by objcopy program. This will give us a elf struct, which we can use to load our simple user program like we did in hw2.

The second part of userinit is the focus of this assignment. This part will be responsible for set up the process data structure correctly.

void userinit(void)
{

	.... // Elf loading code

	p->pgdir = pgdir;
	p->kstack = (char *)page_alloc();
	memzero(p->kstack, PAGESIZE);
	
	char *sp;
	sp = p->kstack + PGSIZE;
	
	// TODO: Initilize kernel stack	
	// sp is your kernel stack pointer. 
	// put process trap frame and context on stack ( order matters !)
	
	// TODO: uncomment below to fill in ?s
	// p->tf->eip = ?
	// p->context->eip = ?
	
	p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
	p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
	p->tf->es = p->tf->ds;
	p->tf->ss = p->tf->ds;
	p->tf->eflags = FL_IF;


	..... // rest of code. 
}

The main idea of how to fill in the above code will be provided below, but you can also try reference xv6 for this part as alternative source.

Process

Let us first take a look at and the process definition (see proc.h):

struct proc
{
	uint sz;                 // Top address of this process
	char *kstack;            // Bottom of kernel stack for this process
	pde_t *pgdir;            // Page table
	enum procstate state;    // Process state
	struct context *context; // swtch() here to run process
	struct trapframe *tf;    // Trap frame for current syscall
};

Recall that, in order to execute the user program in ring 3, we need to do

In this homework, user process and kernel will share same pagetable, so this leaves us setting up segmentation register. we could manually write out this code, but xv6 does this in a interesting manner by using trapret to restore those register through trapret, but trapret to every process allocate. We will use this trick. so our process execution will look like this. (You can ignore low-level details of swtch function, But you need to know that swtch will return to p->context->eip )

swtch -> trapret -> usercode

In order to implement the above path of execution, we can do so by correctly set up process Kernel stack, we need to do following.

• Allocate memory for kernel stack
• Initialize Trap Frame and put on the kernel stack
• Initialize Process Context and put on the kernel stack

The visualization of kernel stack would be something like, note address are fake

0x1000 	------------ 
	TRAP FRAME
	-----------
	CONTEXT
0x0000  -----------

Once the above is done, run_current will switch to the process context, and start execute eip, which will be trapret that restore essentail registers for the process and start to execute its usercode.

Extra Credit (50%)

Implement a simple scheduler, a process table, and yield system call, so that process can be run concurrently. Note, you also need to create another user process to be loaded as part of your kernel. Your process should yield back to kernel scheduler whenever timer interrupt happens.

Submission

 make qemu-nox 

 make clean 

Note: Comment out printk(".") in your timer interrupt handling code in trap.c, so it doesn't mess with autograder.