syscall::_exit(social_life);

Wednesday. December 23, 2020 - 13 mins

Introduction

This is a project in my CPEN 331 Operating System course, and here is the course website. The objective of the course is to gain a deeper understanding of an operating system (or a kernel, pretty much?), but more importantly, implement the pivotal parts of the kernel infrastructure. We used a partially implemented operating system developed by Harvard University called OS161.

Basic Tools and Languages

We started off by learning how to navigate large C/assembly codebase using cscope and cflow, and debugging using gdb debugger. Version controlling using git is the standard for this project. I also started to use vim and emac as the default text editor for this project. Since OS161 is built and compiled using gcc, I also deepened my knowledge of gcc compilers and how to build/make huge C programs with low level assembly code.

cscope interface

Locks and Condition Variables

After learning all the necessary tools, we learned more about lower level instructions, e.g. how the hardware implements atomic instructions and their impact on software. We also implemented our own blocking locks and condition variables using mutexes and semaphores. The functions I implemented were crucial to running multi-cored computers (or even multi-threaded programs), including:

create/destroy lock
acquire/release lock
create/destroy condition variables (CVs)
wait for condition variables
signal/broadcast condition variables

The condition variables is required to be implemented with Mesa semantics in OS161, and the implementation of the locks needs to have the following features:

Comply to the interface: Using the OS161 API only.
Mutual exclusion: only one thread can hold a lock at any given time.
No busy-waiting: No use of spinlocks, because spinlocks spin, or busy-wait, hogging the CPU and checking if the lock became available.

struct lock *
lock_create(const char *name)
{
        struct lock *lock;

        lock = kmalloc(sizeof(struct lock));
        if (lock == NULL) {
                return NULL;
        }

        lock->lk_name = kstrdup(name);
        if (lock->lk_name == NULL) {
                kfree(lock);
                return NULL;
        }
        
        /* Creates the wait channel. If NULL after creating, free its memory. */
        lock->lk_wchan = wchan_create(lock->lk_name);
        if (lock->lk_wchan == NULL) {
                kfree(lock->lk_name);
                kfree(lock);
                return NULL;
        }

        lock->lk_availability = true;
        spinlock_init(&lock->lk_splk);
        // No thread has this lock at this point
        lock->cur_cpu = NULL;
        lock->cur_thread = NULL;

        return lock;
}

One of the functions: Creating the Lock

We will use the synchronization primitives (locks and condition variables) we implemented and learn how to enforce mutual exclusion and thread-to-thread signaling in the remaining project.

System Calls

We also implemented all of the system calls required for the operating system, including:

open()
read()
write()
close()
lseek()
chdir()
dup2()
__getcwd()
getpid()
fork()
execv()
waitpid()
_exit()

To make the syscalls work, we implemented new data structures in the kernel to support the new file-related system calls. We also learn about the process abstraction of Unix, mechanisms of new process creation, and enforcing protection/safety in a multiprocess operating system. In general, not only did I gained deeper knowledge about file descriptors, synchronization, memory allocation, exception handling, and C programming/debugging, I also learned a lot about how kernels (operating systems) work.

int
sys_fork(struct trapframe *tf, pid_t *retval)
{
	struct trapframe *ntf;
	int result;
	struct proc *newproc;

	ntf = kmalloc(sizeof(struct trapframe));
	if (ntf==NULL) {
		return ENOMEM;
	}
	*ntf = *tf;

	result = proc_fork(&newproc);
	if (result) {
		kfree(ntf);
		return result;
	}
	*retval = newproc->p_pid;

	result = thread_fork(curthread->t_name, newproc,
			     fork_newthread, ntf, 0);
	if (result) {
		proc_unfork(newproc);
		kfree(ntf);
		return result;
	}

	return 0;
}

fork() syscall snippet

Virtual Memory

In this section, we had to implement our own virtual memory for OS161, that is our own paging algorithm - the mechanism by which memory pages of an active process can be sent to disk when memory is needed, and restored to memory when required by the program. There were a lot of memory leaks during the debugging process so we got proficient in using valgrind and gdb tools. We also added another system call sbrk() so that you can use malloc() when dealing with virtual memory. I also learned more about memory-management unit (MMU) and the translation lookaside buffer (TLB) when implementing the virtual memory.

Thoughts

This course is definitely the hardest course I have ever taken, but I learned a lot and got confident with C programming! Really proud of myself for completing the course and understanding most/all of the concepts :)