OS161 Assignment 5

Assignment5

Implement fork, execv, waitpid, getpid and _exit.

Questions to think about

1. How to create a copy of an existing user process and make the new process return to user mode with a different return value than the original process. Code in runprogram.c and in the function it calls and in proc_create_runprogram will be very helpful in figuring that out.

fork system call is responsible for creating a copy of an existing user process and making the new(child) process return to user mode with a different return value than the original(parent) process.

To create a new user process, we first need to create a new kernel thread to provide to it. This newly-created kernel thread should change child's trapframe and return to user mode in a different manner than the parent.

2. How to replace the address space of a process created via fork with a completely new address space and executable.

When we want to create a process with a completely new address space and executable. we need to call execv after fork. In execv, we need to create the new address space, switch to and activate it. With the new address space set up, we can load the new executable and define the user stack.

3. How to copy in/out of the userspace the argument vector for the execv system call. This code requires lots of pointer arithmetic and handling various corner cases.

This is the most tricky part when we implement execv. We need to copy in/out not only the argument array, but also the pointers pointing to those arguments. First, we need to copy argument array and pointer array into the kernel from the old address space, then copy those out to the new address space.

4. How to manage the process IDs, so you don't run out as processes are created and retired.

We need to implement the PID system that dynamically allocates and reclaims PID.

5. How to synchronize the parent and child processes in waitpid() and _exit().

To synchronize parent and child processes, we need to implement the process wait and exit mechanism. For now, just need to understand that parent processes call waitpid to wait for their child processes to exit. When child processes exit, they need to signal their parents.

It's important to note that a process will not necessarily be cleaned up right after it exits. It strongly depends on how you design your process wait and cleanup mechanism.

6. How to manage the file table synchronization, given that starting from this assignment two or more processes might concurrently access the same file object (processes created via fork share the file objects).

In the last assignment, we already take this synchronization problem into account. As long as we hold the file handle lock right after we get the file handle, we are fine.

System calls to implement

Make sure to read the system calls man page carefully to understand every detail of these system calls:

getpid()

Main task: Implement pid allocation and reclamation

---

fork()

sys_fork is responsible for:

1. Copy address space(as_copy in dumbvm)

The forked process should have the exact same address space as the original process.

2. Copy the file table

When a process is forked, file descriptor entries of the new process point to the same file handles as in the parent process.

What kind of race conditions do you have to worry about?

Two processes simultaneously modifying the values of the offset.

Can you hold a spinlock while doing I/O?

Spinlocks turn off interrupts; I/O completion is signaled via an interrupt. If you turn off interrupts and then go do I/O, YOU WILL NEVER GET NOTIFIED!

Hold a regular lock? That will work. But do we have to hold the lock?

-- Not really. We can set up the uio struct with the right offset, release the lock, do the I/O, then acquire it again and update the offset if I/O was successful. Can’t update the offset prior to I/O completion – what if it fails?

3. Copy architectural state(Copy and tweak trapframe)

In the implementation of A5, you will have to make sure the right value is returned to the right process!

How will you need to modify the child's trapframe to make sure that the child correctly returns to user mode?

Set the correct return value (0), signal no error, and advance to next instruction in the trapframe.

When do you need to copy the parent's trapframe? Remember that as soon as the parent is returned from the system call, its trapframe will be destroyed or modified!

Copy the parent's trapframe to child_tf before creating the kernel thread for the child process.

4. Copy kernel thread(thread_fork)

When you fork a new process, you fork a new kernel thread to provide to the child process.

To fork that thread, you need to provide it a function to run. You’ll need to write that function.

As mentioned above, thread_fork is used to fork a new kernel thread for the newly-forked process. enter_forked_process is provided to the newly-created thread.

You need to implement the enter_forked_process to modify the child process's trapframe and return to user mode:

5. Return to user mode
6. Both the parent and child return to user mode

The parent just returns from exception(mips_trap).

The child returns via the mips_usermode function.

How does a thread enter user mode for the first time?

mips_usermode in trap.c. This function shouldn't used by threads returning from traps - they should just return from mips_trap.

---

execv()

It must replace the existing address space with a brand new one for the new executable (created by calling as_create in the current dumbvm system) and then run it.

While this is similar to starting a process straight out of the kernel (as runprogram() does), it's not quite that simple. Remember that this call is coming out of userspace, into the kernel, and then returning back to userspace. You must manage the memory that travels across these boundaries very carefully.

(Also, notice that runprogram() doesn't take an argument vector -- but this must of course be handled correctly in execv())

As you are replacing an old address space with a new one, you must not leak memory used by the old address space.

Carefully read the man page for execv() to understand the trickery in passing the potentially very large argument vector to/from userspace.

int
execv(const char *program, char **args);

sys_execv is responsible for:

• Replace the old address space with a new one

• Copy the arguments into the new address space

• Return to user mode

The mechanics of exec():

To think before starting exec():

Where are the arguments located when the exec system call in invoked? In whose address space? How do you know their address?

How do we get them into the kernel? How do you figure out their total size?

Where do the arguments need to end up before we return to the user mode? Whose address space? Stack or heap?

How do we get them there? How do we organize them there.

What if the arguments array is huge and you cannot allocate enough kernel memory contiguously?

Passing arguments(copyin and copyout):

It's important to emphasize that we need to pass not only the arguments, but also the pointers to those arguments.

---

waitpid()

Require a fair bit of design.

If a parent process exits before one or more of its children, it can no longer be expected collect their exit status. There are several ways to handle this case in practice, of which the traditional Unix method is only one. This is something you should design.

---

_exit()

Closely connected to the implementation of waitpid().

Most of the time, the code for _exit() will be simple and the code for waitpid() relatively complicated.

Error handling

If there are conditions that can happen that are not listed in the man page, return the most appropriate error code from kern/include/kern/errno.h.

Note that if you add an error code to src/kern/include/kern/errno.h, you need to add a corresponding error message to the file src/kern/include/kern/errmsg.h.

kill_curthread

Feel free to write kill_curthread() in as simple a manner as possible.

kill_curthread is similar to _exit, except that in kill_curthread, we need to signal the parent process that current process is dead. We only need to change the p_exitcode.

Plan your work

Implement fork first.

You will be able to test it using /testbin/forktest (set no wait to 1 in forktest.c if you would like to run it before waitpid is implemented)

You may first implement fork() with a very simple pid assignment scheme, and improve on it later as you are designing the rest of the system calls.

Test your code

1. Testing using the shell

In user /bin/sh you will find a simple shell that will allow you to test your new system call interfaces.

You can exit the shell by typing "exit".

Before you run the shell, you need to put some synchronization code into common_prog()(in menu.c:114) to make sure that the menu thread is not trying to run concurrently with your shell and does not compete with it for the console input/output.

2. Error handling

Use the devious /testbin/badcall (which you should now be able to invoke from a shell). At this point your system should not crash no matter what the user program does.

Even /testbin/forkbomb should not crash your kernel.

3. Memory leaks

Your execv should properly dispose of the old address space (and any other old unneeded state) and returned the memory back to the system.

If a system call fails in the middle of execution (e.g., because of a bad pointer coming from user space) you must free up the resources allocated up to that point.

You can debug memory leaks by changing #undef LABELS to #define labels in vm/kmalloc.c and then invoking khdump from the kernel menu to examine the heap.

OS/161 kernel [? for menu]: khdump
Remaining allocations from generation 3:
  16 bytes at 0x80042e70, allocated at 0x80012d80
  64 bytes at 0x80040140, allocated at 0x80006080
  64 bytes at 0x800401c0, allocated at 0x8001162c
  64 bytes at 0x80040200, allocated at 0x80006080
  64 bytes at 0x80040340, allocated at 0x80006080
  64 bytes at 0x800403c0, allocated at 0x80006080
  64 bytes at 0x80040480, allocated at 0x80006080
  64 bytes at 0x80040540, allocated at 0x80006080
  64 bytes at 0x80040680, allocated at 0x80006080
 128 bytes at 0x8003f780, allocated at 0x80023cfc
 256 bytes at 0x80041b00, allocated at 0x8001162c
 512 bytes at 0x80043c00, allocated at 0x8001162c
Operation took 1.195788680 seconds

You see that this command outputs a bunch of virtual addresses that were allocated via kmalloc and the corresponding addresses of code locations, where those items were allocated. To find out what these code locations are, you can use os161-addr2line (the OS/161 version of this standard Unix tool). For example, using an address from the example above:

os161-addr2line -e ~/Work/os161/root/kernel 0x80023cfc
/Users/UBC-home/Work/os161/src/kern/compile/DUMBVM/../../thread/thread.c:132

4. How we will mark your code

We will run a subset of the following tests on your kernel (all from /testbin)

forktest
argtest
bigfile
crash
farm
faulter
forkbomb
multiexec
badcall
bigexec

Forktest and argtest are the simplest test programs, so first make sure that your kernel runs those. Badcall and bigexec are the most challenging.

My Solution

I have revealed enough tips(secrets) above, more than enough for you to implement this assignment correctly! Please do not look at my solution below until you have finished coding! Otherwise, you will lose the joy of coding!

Now, I will dive deep down into my design and implementation. SPOIL (CODE) ALERT!

This assignment has 4 major parts:

1. PID system
2. Process creation(fork)
3. Process wait and exit mechanism
4. Program replacement(execv)

PID system

First of all, we need to design our PID system that dynamically allocates and reclaims PID so that PID won't be used up as processes are created and destroyed.

Although the assignment handout suggest that we first implement a simple PID scheme before implementing fork and improve on it later when we try to implement more system calls, personally I prefer implementing the complete PID system before moving on.

My PID system design is rather simple. I maintain a global pid_table, with entries pid_entry. The index of the pid_table entry can be translated to pid. Since the index starts at 0 and the pid starts at PID_MIN(2), so index = pid - PID_MIN. I also use a next_pid variable to keep track of the next PID to try for allocation. Whenever we want to allocate a new PID, start trying from next_pid.

How do we know whether a pid is available? The pid_entry structure has a proc field. We simply examines whether pid_entry->proc == NULL. We free a pid by setting pid_entry->proc = NULL

I set kernel process's pid to PID_KERNEL(1) just for convenience sake, and user processes' pid begin at 2(PID_MIN).

/*
 * Create the process structure for the kernel.
 */
void
proc_bootstrap(void)
{
	kproc = proc_create("[kernel]");
	if (kproc == NULL) {
		panic("proc_create for kproc failed\n");
	}

	/* Allocate PID for kernel process */
	kproc->p_pid = PID_KERNEL;
}

proc_remove_pid is called only during process cleanup to free the pid. Therefore, in my implementation, pid freeing is always called in company with process destruction. It is important to emphasize that pid should not be freed until the process is destroyed (not exits!).

pid_bootstrap needs to be called during initial boot sequence(early initialization) to indicate that all PIDs are available to use.

Lastly, don't forget to call pid_allocate in proc_create_fork and proc_create_runprogram.

The complete code of pid.h and pid.c:

/*
 * Process ID management.
 */

#define PID_KERNEL    1

/* Number of PIDs available */
#define PID_COUNT   (PID_MAX - PID_MIN + 1)

/* Error value returned by pid_allocate */
#define ENOPID      (-1)    /* No PIDs available */

/* PID table entry structure */
struct pid_entry {
    pid_t pid;               /* Process ID */
    struct proc *proc;      /* Pointer to process structure */
};

/* Global PID management state */
struct pid_entry *pid_table;     /* PID allocation table */
struct spinlock pid_lock;        /* Lock for PID operations */
unsigned int pid_count;          /* Number of PIDs in use */
pid_t next_pid;                  /* Next PID to try for allocation */

/* 
 * Initialize the PID management system.
 * Called during system bootstrap.
 */
void pid_bootstrap(void);

/* 
 * Allocate a new PID and associate it with a process.
 * Returns allocated PID on success, ENOPID on failure.
 */
pid_t pid_allocate(struct proc *proc);

/* 
 * Convert PID to table index.
 */
int pid_to_index(pid_t pid);

/*
 * Get process structure associated with PID.
 * Returns NULL if PID is invalid or not in use.
 */
struct proc *pid_get_proc(pid_t pid);

/* 
 * Remove process from PID table. 
 */
void proc_remove_pid(struct proc *proc);

/*
 * Initialize the PID management system
 * Called during system bootstrap
 */
void 
pid_bootstrap(void) 
{
    size_t table_size = PID_COUNT * sizeof(struct pid_entry);
    
    /* Allocate PID table */
    pid_table = kmalloc(table_size);
    if (pid_table == NULL) {
        panic("pid_bootstrap: Unable to allocate PID table\n");
    }

    /* Initialize PID table entries */
    for (int i = 0; i < PID_COUNT; i++) {
        pid_table[i].pid = PID_MIN + i;
        pid_table[i].proc = NULL;
    }

    /* Initialize lock and state */
    spinlock_init(&pid_lock);
    pid_count = 0;
    next_pid = PID_MIN;
}

/*
 * Convert PID to table index
 */
int pid_to_index(pid_t pid) 
{
    KASSERT(pid >= PID_MIN && pid <= PID_MAX);
    return pid - PID_MIN;
}

/*
 * Check if a PID entry is available
 * Must be called with pid_lock held
 */
static inline int
is_pid_available(struct pid_entry *entry)
{
    return entry->proc == NULL;
}

/*
 * Find next available PID starting from next_pid
 * Must be called with pid_lock held
 */
static pid_t 
find_free_pid(void) 
{
    unsigned int start = pid_to_index(next_pid);
    unsigned int i = start;

    /* Search for a free PID */
    do {
        if (is_pid_available(&pid_table[i])) {
            return PID_MIN + i;
        }
        i = (i + 1) % PID_COUNT;
    } while (i != start);

    return ENOPID;
}

/*
 * Allocate a new PID and associate it with the given process
 * Returns allocated PID on success, ENOPID on failure
 */
pid_t 
pid_allocate(struct proc *proc) 
{
    pid_t pid;
    int index;

    KASSERT(proc != NULL);

    spinlock_acquire(&pid_lock);

    /* Check if we've reached maximum PIDs */
    if (pid_count >= PID_COUNT) {
        spinlock_release(&pid_lock);
        return ENOPID;
    }

    /* Find next available PID */
    pid = find_free_pid();
    if (pid == ENOPID) {
        spinlock_release(&pid_lock);
        return ENOPID;
    }

    /* Associate PID with process */
    index = pid_to_index(pid);
    KASSERT(pid_table[index].proc == NULL);
    pid_table[index].proc = proc;
    pid_count++;

    /* Update next_pid to start search from next position */
    next_pid = (pid < PID_MAX) ? (pid + 1) : PID_MIN;

    spinlock_release(&pid_lock);
    return pid;
}

/*
 * Get process structure associated with PID
 * Returns NULL if PID is invalid or not in use
 */
struct proc *
pid_get_proc(pid_t pid) 
{
    struct proc *p = NULL;
    
    /* Validate PID */
    if (pid < PID_MIN || pid > PID_MAX) {
        return NULL;
    }

    spinlock_acquire(&pid_lock);
    
    int index = pid_to_index(pid);
    p = pid_table[index].proc;
    
    spinlock_release(&pid_lock);
    return p;
}

/* 
 * Remove process from PID table 
 */
void proc_remove_pid(struct proc *proc) {
    spinlock_acquire(&pid_lock);
    pid_table[pid_to_index(proc->p_pid)].proc = NULL;
    pid_count--;
    spinlock_release(&pid_lock);
}

Process creation(fork)

Once we have our PID system ready, we can implement our fork logic: creating a new process, which is the exact same copy of the original process. Review the sys_fork's responsibility above and understand what it should do.

Now let's break it down:

1. Create a copy of the parent's trapframe to provide to the newly-created kernel thread for use.

// Create child trapframe copy
child_tf = kmalloc(sizeof(struct trapframe));
if (child_tf == NULL)
{
return ENOMEM;
}
*child_tf = *tf;

2. Create the child's proc structure child_proc

Remember that we need to create a new kernel thread to provide to the child process. Therefore, we first need to create the child's proc structure.

That's proc_create_fork's responsibility! In this function, we need to make the exact same copy of the parent process: copy the file table and allocate a new PID.

/* Create a fresh proc for use by fork. */
struct proc *
proc_create_fork(const char *name)
{
	struct proc *newproc;

	newproc = proc_create(name);
	if (newproc == NULL) {
		return NULL;
	}

    newproc->p_addrspace = NULL;
	
	/* Copy file table from parent process. */
    newproc->p_ft = filetable_copy(curproc->p_ft);
    if (newproc->p_ft == NULL)
    {
        proc_destroy(newproc);
        return NULL;
    }

	/* Allocate PID */
    newproc->p_pid = pid_allocate(newproc);
    if (newproc->p_pid == ENOPID) {
        proc_destroy(newproc);
        return NULL;
    }

	/* Set parent process for fork. */
	newproc->p_parent = curproc;

	/* Add to parent's child array */
	if (array_add(curproc->p_children, newproc, NULL)) {
		proc_destroy(newproc);
		return NULL;
	}

	/*
	 * Lock the current process to copy its current directory.
	 * (We don't need to lock the new process, though, as we have
	 * the only reference to it.)
	 */
	spinlock_acquire(&curproc->p_lock);
	if (curproc->p_cwd != NULL) {
		VOP_INCREF(curproc->p_cwd);
		newproc->p_cwd = curproc->p_cwd;
	}
	spinlock_release(&curproc->p_lock);

	return newproc;
}

You may be confused with the p_parent and p_children fields in the code above. Don't worry, I will explain why we need those fields in proc structure when I explain my process wait and exit mechanism.

In sys_fork, we call proc_create_fork to get the child proc:

// Create new process structure
child_proc = proc_create_fork("child");
if (child_proc == NULL)
{
    kfree(child_tf);
    return ENOMEM;
}

What's the difference between proc_create_fork and proc_create_runprogram?

proc_create_fork is called by sys_fork. In proc_create_fork, we create a new process that is the copy of the current process. Therefore, we need to copy the file table and add the new process to the current process's children array. proc_create_runprogram is called by the kernel to create a new process for use by runprogram. It will have no address space and will inherit the current process's (the kernel menu's) current directory.

3. Copy address space

Notice that in proc_create_fork, I didn't copy the parent's address space. I choose to do this in sys_fork after we get a child proc.

// Copy address space
result = as_copy(proc_getas(), &child_as);
if (result)
{
    proc_destroy(child_proc);
    kfree(child_tf);
    return result;
}

// Set up child process
child_proc->p_addrspace = child_as;

4. Create a new kernel thread

Remember that we need to create a new kernel thread to provide to the child process so that the child and the parent can return to user mode in their own way.

thread_fork is used to create a new thread to provide to the forked process. It needs to have an entrypoint where the new thread starts executing. Remember that the new thread needs to tweak trapframe to make sure the child has a different return value and return to user mode in a different manner than the parent. This function is performed by enter_forked_process.

// Create new thread for child process
result = thread_fork(
    curthread->t_name,
    child_proc,
    (void (*)(void *, unsigned long))enter_forked_process,    // New entry point function
    child_tf,           // Pass child trapframe as data1
    0                    // Unused data2
);

There we go! We find the entrypoint function for the new thread. Now it's time to implement enter_forked_process:

1. Copy the child's trapframe to our kernel stack from the heap.
2. Tweak the child's trapframe
3. Activate child process's address space
4. Enter user mode

/*
 * Enter user mode for a newly forked process.
 *
 * This function is provided as a reminder. You need to write
 * both it and the code that calls it.
 *
 * Thus, you can trash it and do things another way if you prefer.
 */
void enter_forked_process(struct trapframe *tf)
{
	(void)tf;
	struct trapframe child_tf; // create child's trapframe on the stack

	// Copy trapframe to our kernel stack
	child_tf = *tf;

	kfree(tf);

	// Child process returns 0 from fork()
	child_tf.tf_v0 = 0;

	/* signal no error */
	child_tf.tf_a3 = 0;

	// Advance to next instruction
	child_tf.tf_epc += 4;

	// Activate child's address space
	as_activate();

	// Enter user mode with child's trapframe
	mips_usermode(&child_tf);

	panic("enter_forked_process: mips_usermode returned\n");
}

Have you thought about why we need the trouble to first copy parent's trapframe onto the heap and then copy it to the kernel stack from the heap?

Because parent's trapframe is on its stack and will be destroyed as soon as it returns from trap. In the mean time, our newly-created kernel thread run concurrently and may lose the trapframe if the parent returns from trap too early. That's why we need to save a copy of the trapframe on the heap before the parent returns.

5. Parent returns from trap

While the child returns via the mips_usermode function in its own kernel thread. The parent just returns from trap(mips_trap) with the return value of its child's PID.

// Parent returns child's PID
*retval = child_proc->p_pid;

The complete code of sys_fork:

int sys_fork(struct trapframe *tf, pid_t *retval)
{
    struct trapframe *child_tf;  // Child's trapframe
    struct addrspace *child_as;  // Child's address space
    struct proc *child_proc;     // Child process
    int result;

    // Create child trapframe copy
    child_tf = kmalloc(sizeof(struct trapframe));
    if (child_tf == NULL)
    {
        return ENOMEM;
    }
    *child_tf = *tf;

    // Create new process structure
    child_proc = proc_create_fork("child");
    if (child_proc == NULL)
    {
        kfree(child_tf);
        return ENOMEM;
    }

    // Copy address space
    result = as_copy(proc_getas(), &child_as);
    if (result)
    {
        proc_destroy(child_proc);
        kfree(child_tf);
        return result;
    }

    // Set up child process
    child_proc->p_addrspace = child_as;

    // Create new thread for child process
    result = thread_fork(
        curthread->t_name,
        child_proc,
        (void (*)(void *, unsigned long))enter_forked_process,    // New entry point function
        child_tf,           // Pass child trapframe as data1
        0                    // Unused data2
    );

    if (result)
    {
        proc_destroy(child_proc);
        return result;
    }

    // Parent returns child's PID
    *retval = child_proc->p_pid;

    return 0;
}

Process wait and exit mechanism

This assignment gives us the freedom to design the process wait and exit mechanism. The assignment handout says:

Most of the time, the code for _exit() will be simple and the code for waitpid() relatively complicated.

However, my design requires a more complex _exit than waitpid. Maybe it is not the best design, but it is a working design!

Now let's break down my design:

The crux of the problem:

1. When should the process be cleaned up?
2. How to implement the mechanism for the parent process to wait for its child to exit?
3. How to kill a process when it encounters an error.

• Process cleanup mechanism

The main problem is that when a process exits, it should not be cleaned up right away. Instead, it should become zombie until its parent process call waitpid to collect its exit code.

Therefore, my first thought is to clean up the child process as soon as its parent collects its exit code.

However, that bring us a new problem:

What if the parent process never calls waitpid before it exits? Or the parent exits before its child exits? How to prevent its zombie child from hanging forever?

My solution to this problem is to delay the child process's cleanup until the parent process exits. That is to say, when a process exits, it should traverse all of its children, clean up zombie children( exit code already be collected) and make running children(haven't yet exited) become orphans. Those orphan processes would be cleaned up right away as soon as they exits(skip the process of becoming zombies).

After handling its children, the process should check if itself is orphaned. If so, just clean itself up(in thread_exit. If not, signal its parent and becomes zombie.

// In `thread_exit`

/* 
 * The code below is a bit more complex than it needs to be.
 * Actually, it only needs to check current process is orphaned
 * before clean it up. I add some additional check just for
 * robustness.
 */

...
/* 
 * Clean up process if:
 * 1. This is the last thread AND
 * 2. One of the following is true:
 *    - Process is marked DEAD (normal case) OR
 *    - Process has no parent (orphaned case)
 */
if (p != NULL) {
    lock_acquire(p->p_mutex);
    if (threadarray_num(&p->p_threads) == 0 && 
        (p->p_state == PROC_DEAD || p->p_parent == NULL)) {
        lock_release(p->p_mutex);

        /* Clean up process */
        proc_remove_pid(p);
        proc_destroy(p);
    } else {
        lock_release(p->p_mutex);
    }
}

Now this explains why I maintain a p_parent and p_children field in proc structure.

The flow chart below shows the normal life of a process:

PROC_RUNNING -> (PROC_ZOMBIE) -> PROC_DEAD & proc_destroy & proc_remove_pid -> PID is avaiable

The complete code of sys__exit:

/*
 * Exit system call.
 */
void sys__exit(int exitcode)
{
    KASSERT(curproc != NULL);
    KASSERT(curproc != kproc); /* Kernel process cannot exit */

    /* Get the lock */
    lock_acquire(curproc->p_mutex);

    /* Set exit code and change state to zombie */
    curproc->p_exitcode = _MKWAIT_EXIT(exitcode);
    curproc->p_state = PROC_ZOMBIE;

    /*
     * Handle children
     * - zombies and dead children get cleaned up immediately,
     * - running processes become orphans that clean themselves up
     */
    struct proc *child;
    while (array_num(curproc->p_children) > 0)
    {
        child = array_get(curproc->p_children, 0);

        if (child->p_state == PROC_ZOMBIE || child->p_state == PROC_DEAD)
        {
            KASSERT(array_num(child->p_children) == 0);

            child->p_state = PROC_DEAD;

            /* Remove from children array */
            array_remove(curproc->p_children, 0);

            /* Clean up the zombie/dead child */
            proc_remove_pid(child);
            proc_destroy(child);
        }
        else
        {
            /* Mark as orphaned - will self-cleanup when done */
            child->p_parent = NULL;

            /* Remove from children array */
            array_remove(curproc->p_children, 0);
        }
    }

    /* Signal parent if we have one, otherwise self-cleanup */
    if (curproc->p_parent != NULL)
    {
        cv_signal(curproc->p_cv, curproc->p_mutex); // Wake up waiting parent
    }
    else
    {
        /* Orphaned process cleans itself up */
        curproc->p_state = PROC_DEAD;
    }

    lock_release(curproc->p_mutex);

    thread_exit();

    /* Should never get here */
    panic("sys__exit: thread_exit returned\n");
}

• Process wait mechanism

waitpid is called by the parent process to wait for its child process to exit. When the child process exits, it signals its parent. My design is to let the parent process wait on its child's condition variable. When the child exits, it wakes up the parent.

// In `sys_waitpid`

...
/* Wait for child to exit */
while (child->p_state == PROC_RUNNING) {
    cv_wait(child->p_cv, child->p_mutex);
}

// In `sys__exit`

...
/* Signal parent if we have one, otherwise self-cleanup */
if (curproc->p_parent != NULL)
{
    cv_signal(curproc->p_cv, curproc->p_mutex); // Wake up waiting parent
}
else
{
    /* Orphaned process cleans itself up */
    curproc->p_state = PROC_DEAD;
}

Special case: recall that in my process cleanup mechanism, we clean up zombie children when the parent process exits. But if current process is the kernel process, it does not exit. Therefore, we need to clean up its child right after it collects its child's exit code in waitpid.

As in fact, the kernel does need to wait for its child to exit in OS/161 and we need to implement that logic:

In OS/161, the kernel thread, (or menu thread), after it gets command arguments from the command line, it goes into common_prog. In common_prog, it creates a new thread to provide to the new program. We need to make it wait for the subprogram to finish(exit) before allowing it to return to menu.

// In `common_prog`

...
/* Save the pid before we fork */
pid = proc->p_pid;

result = thread_fork(args[0] /* thread name */,
                     proc /* new process */,
                     cmd_progthread /* thread function */,
                     args /* thread arg */, nargs /* thread arg */);
if (result) {
    kprintf("thread_fork failed: %s\n", strerror(result));
    proc_destroy(proc);
    return result;
}

/*
	 * The new process will be destroyed when the program exits...
	 * once you write the code for handling that.
	 */
/* Wait for the subprogram to finish */
result = sys_waitpid(pid, NULL, 0, &result);
if (result) {
    kprintf("waitpid failed: %s\n", strerror(result));
    return result;
}

return 0;
// Return to menu

The complete code of sys_waitpid:

/*
 * Waitpid system call.
 */
int
sys_waitpid(pid_t pid, userptr_t status, int options, int *retval)
{
    struct proc *child;
    int exitcode;
    
    /* Check for invalid options */
    if (options != 0) {
        return EINVAL;
    }
    
    /* Get the child process */
    child = pid_get_proc(pid);
    if (child == NULL) {
        return ESRCH;  /* No such process */
    }
    
    /* Verify this is our child */
    lock_acquire(child->p_mutex);
    if (child->p_parent != curproc) {
        lock_release(child->p_mutex);
        return ECHILD;  /* Not a child of calling process */
    }

    /* Wait for child to exit */
    while (child->p_state == PROC_RUNNING) {
        cv_wait(child->p_cv, child->p_mutex);
    }

    /* Get exit status while holding the lock */
    exitcode = child->p_exitcode;
    child->p_state = PROC_DEAD;

    lock_release(child->p_mutex);

    if (curproc == kproc) {
        /* 
         * If we're the kernel, we do not exit, so we need to
         * clean up the child process here.
         */
        proc_remove_pid(child);
        proc_destroy(child);
    }

    /* Now copy out exit status if requested */
    if (status != NULL) {
        int result = copyout(&exitcode, status, sizeof(int));
        if (result) {
            return EFAULT;
        }
    }
    
    *retval = pid;
    return 0;
}

• Kill a process

When a user process hits a fatal fault, we need to kill it. But instead of crashing the entire kernel, we need to signal parent of its death and clean it up neatly.

This is very much like normal _exit, except that we need to set exit code to signal death.

/* Set exit code for signal death */
curproc->p_exitcode = _MKWAIT_SIG(sig);

The complete code of kill_curthread:

// In `kill_curthread`

...
/*
 * We have faced a fatal fault in user-level code, instead of
 * crashing the entire kernel. We need to clean up the process
 * and signal the parent if necessary.
 */

kprintf("Fatal user mode trap %u sig %d (%s, epc 0x%x, vaddr 0x%x)\n",
        code, sig, trapcodenames[code], epc, vaddr);

KASSERT(curproc != NULL);
KASSERT(curproc != kproc); /* Kernel process cannot be killed */

/* Get the lock */
lock_acquire(curproc->p_mutex);

/* Set exit code for signal death and change state to zombie */
curproc->p_exitcode = _MKWAIT_SIG(sig);
curproc->p_state = PROC_ZOMBIE;

/*
     * Handle children
     * - zombies and dead children get cleaned up immediately,
     * - running processes become orphans that clean themselves up
     */
struct proc *child;
while (array_num(curproc->p_children) > 0)
{
    child = array_get(curproc->p_children, 0);

    if (child->p_state == PROC_ZOMBIE || child->p_state == PROC_DEAD)
    {
        KASSERT(array_num(child->p_children) == 0);

        child->p_state = PROC_DEAD;

        /* Remove from children array */
        array_remove(curproc->p_children, 0);

        /* Clean up the zombie/dead child */
        proc_remove_pid(child);
        proc_destroy(child);
    }
    else
    {
        /* Mark as orphaned - will self-cleanup when done */
        child->p_parent = NULL;

        /* Remove from children array */
        array_remove(curproc->p_children, 0);
    }
}

/* Signal parent if we have one, otherwise self-cleanup */
if (curproc->p_parent != NULL)
{
    cv_signal(curproc->p_cv, curproc->p_mutex); // Wake up waiting parent
}
else
{
    /* Orphaned process cleans itself up */
    curproc->p_state = PROC_DEAD;
}

lock_release(curproc->p_mutex);

thread_exit();

/* Should never reach here */
panic("thread_exit returned in kill_curthread!\n");

Program replacement(execv)

We often needs to replace the currently executing program, (probably in a newly-forked process) with a newly-loaded program image(with completely new address space and executable).

That's the job of execv! This is also the most tricky system call we need to implement in the entire OS/161. Review the sys_execv's responsibility above and understand what it should do.

I break it down into 4 parts:

1. Copyin the arguments from the old address space
2. Load the new program image
3. Copyout the arguments into the new address space
4. Clean the old address space and return

Copyin and Copyout arguments are the most tricky parts, you can really mess up with those pointers! It is important to emphasize it again that we need to pass both the arguments(strings) and the pointers pointing to those arguments(strings).

• Copyin arguments from user space

It's important to emphasize that we need to pass not only the arguments, but also the pointers to those arguments.

First of all, I've defined two variables. kargbuf stores arguments(strings) in contiguous space(each individual string is stored in 4-bytes aligned address) and kargs stores the pointers array, pointing to individual strings in kargbuf.

char **kargs;    // Kernel buffer for args array
char *kargbuf;   // Kernel buffer for arg strings

Next, we need to know the number of arguments(strings) and the total bytes needed for strings, so that we can reserve space on the kernel heap to incept them.

1. Number of arguments(strings)

/* First, count the number of arguments */
while (true)
{
    userptr_t arg;
    result = copyin((const_userptr_t)&args[nargs], &arg, sizeof(userptr_t));
    if (result)
    {
        goto err1;
    }
    if (arg == NULL)
        break;
    nargs++;
}

/* Allocate kernel args array */
if (nargs > 0)
{
    kargs = kmalloc(nargs * sizeof(char *));
    if (kargs == NULL)
    {
        result = ENOMEM;
        goto err1;
    }
}

After we know the number of arguments(strings) and reserve the space for kargs, we copy the array of argument pointers from user space to kargs:

/* Copy the array of argument pointers from user space */
result = copyin((const_userptr_t)args, kargs, nargs * sizeof(char *));
if (result)
{
    goto err2;
}

Note that now the karg array store the pointers pointing to user address space. After we copy the arguments(strings) into the kernel, we need to make those pointers pointing to the arguments inside the kernel.

2. Total bytes for arguments(strings)

/* Calculate total bytes needed for strings */
total_bytes = 0;
for (int i = 0; i < nargs; i++)
{
    size_t len;
    char temp_buf;
    result = copyinstr((const_userptr_t)kargs[i], &temp_buf, ARG_MAX, &len);
    if (result)
    {
        goto err2;
    }
    total_bytes += ROUNDUP(len, 4); // Align to 4 bytes
}

/* Check if total size exceeds ARG_MAX */
if (total_bytes > ARG_MAX)
{
    result = E2BIG;
    goto err2;
}

/* Allocate buffer for argument strings */
kargbuf = kmalloc(total_bytes);
if (kargbuf == NULL)
{
    result = ENOMEM;
    goto err2;
}

After we know the total bytes needed for arguments(strings) and reserve space for kargbuf, we copy the arguments(strings) into kargbuf and make pointers in kargs pointing to the new locations(in kernel) of the arguments.

/* Copy strings to kernel buffer */
char *bufptr = kargbuf;
for (int i = 0; i < nargs; i++)
{
    size_t len;
    /* Copy string from user space */
    result = copyinstr((const_userptr_t)kargs[i], bufptr, ARG_MAX, &len);
    if (result)
    {
        goto err3;
    }
    kargs[i] = bufptr; /* Store pointer to string in kernel array */
    bufptr += ROUNDUP(len, 4);
}

• Load the new program image

1. Create and switch to the new address space

/* Create new address space */
new_as = as_create();
if (new_as == NULL)
{
    result = ENOMEM;
    vfs_close(v);
    goto err3;
}

/* Switch to new address space */
old_as = proc_setas(new_as);
as_activate();

2. Open and load the new executable

/* Copy the program path and verify it */
kprogram = kmalloc(PATH_MAX);
if (kprogram == NULL)
{
    result = ENOMEM;
    goto err1;
}
result = copyinstr(program, kprogram, PATH_MAX, &actual);
if (result)
{
    goto err1;
}

/* Open the executable */
result = vfs_open(kprogram, O_RDONLY, 0, &v);
if (result)
{
    goto err3;
}

/* Load the new executable */
result = load_elf(v, &entrypoint);
vfs_close(v);
if (result)
{
    proc_setas(old_as);
    as_activate();
    as_destroy(new_as);
    goto err3;
}

3. Define a new stack region

/* Define the user stack */
result = as_define_stack(new_as, &stackptr);
if (result)
{
    proc_setas(old_as);
    as_activate();
    as_destroy(new_as);
    goto err3;
}

• Copyout arguments to user stack

How to copy the arguments to the new address space?

We first obtain the initial stackptr via as_define_stack.

Next we calculate where the strings should begin:

/* Adjust stack pointer for strings */
stackptr -= total_bytes;
stackptr = ROUNDUP(stackptr - 7, 8);

/* Remember where strings start */
vaddr_t strings_start = stackptr;

Then copy the strings starting at stackptr(strings_start) and save the new user space address of the strings in kargs.

/* Copy strings and save their user-space addresses in kargs */
for (int i = 0; i < nargs; i++)
{
    size_t got;
    /* Copy string to user stack */
    result = copyoutstr((const char *)kargs[i], (userptr_t)stackptr, ARG_MAX, &got);
    if (result) { ... }
    /* Save user space address in kargs */
    kargs[i] = (char *)stackptr;
    /* Move to next aligned position */
    stackptr += ROUNDUP(got, 4);
}

Why do we need to save the strings' user space address?

After we copy the strings to user space address, we also need to copy the pointers to those strings.

We first calculate where the pointers should begin. Note that the pointers should store below the strings, as the stack grows in the direction of low address.

size_t ptrs_space = (nargs + 1) * sizeof(userptr_t); // +1 for NULL terminator

/* Adjust stack pointer for argv array */
stackptr = strings_start - ptrs_space;
stackptr = ROUNDUP(stackptr - 7, 8);

Then we copy the pointers (to the strings) starting at stackptr(This is also the final stackptr we need to pass to enter_new_process in order to enter user mode):

/* Copy out argv array */
for (int i = 0; i < nargs; i++)
{
    result = copyout((const_userptr_t)&kargs[i], (userptr_t)(stackptr + i * sizeof(userptr_t)), sizeof(userptr_t));
    if (result) { ... }
}

/* Set the last pointer to NULL */
void *null_val = NULL;
result = copyout(&null_val, (userptr_t)(stackptr + nargs * sizeof(userptr_t)), sizeof(userptr_t));
if (result) { ... }

This is the overview of user stack before we enter user mode:

• Clean the old address space and return to user mode

/* Clean up */
as_destroy(old_as);
if (kprogram)
    kfree(kprogram);
if (kargs)
    kfree(kargs);
if (kargbuf)
    kfree(kargbuf);

/* Enter user mode */
enter_new_process(nargs /*argc*/, (userptr_t)stackptr /*argv*/, NULL /*env*/, stackptr, entrypoint);

Finish!

Those are the files I have modified/created. Do not get here unless you are stuck in coding!

* kern/arch/mips/locore/trap.c
* kern/include/syscall.h
* kern/arch/mips/syscall/syscall.c
* kern/include/pid.h
* kern/proc/pid.c
* kern/include/proc.h
* kern/proc/proc.c
* kern/main/main.c
* kern/main/menu.c
* kern/syscall/_exit_syscalls.c
* kern/syscall/waitpid_syscalls.c
* kern/syscall/getpid_syscalls.c
* kern/syscall/execv_syscalls.c
* kern/syscall/fork_syscalls.c
* kern/thread/thread.c

We have passed all tests in Assignment5!

OS/161 kernel [? for menu]: p testbin/crash
[a] read from NULL
[b] read from invalid address
[c] read from kernel address
[d] write to NULL
[e] write to invalid address
[f] write to code segment
[g] write to kernel address
[h] jump to NULL
[i] jump to invalid address
[j] jump to kernel address
[k] alignment error
[l] illegal instruction
[m] divide by zero
[n] mod by zero
[o] Recurse infinitely
[*] Run everything (in subprocesses)
Note: [f] may not cause an exception on some platforms, in which
case it'll appear to fail.
Choose: Running: [a] read from NULL
Fatal user mode trap 2 sig 11 (TLB miss on load, epc 0x400310, vaddr 0x0)
Signal 11 (correct)
Running: [b] read from invalid address
Fatal user mode trap 2 sig 11 (TLB miss on load, epc 0x40032c, vaddr 0x40000000)
Signal 11 (correct)
Running: [c] read from kernel address
Fatal user mode trap 4 sig 10 (Address error on load, epc 0x400348, vaddr 0x80000000)
Signal 10 (correct)
Running: [d] write to NULL
Fatal user mode trap 3 sig 11 (TLB miss on store, epc 0x400364, vaddr 0x0)
Signal 11 (correct)
Running: [e] write to invalid address
Fatal user mode trap 3 sig 11 (TLB miss on store, epc 0x400374, vaddr 0x40000000)
Signal 11 (correct)
Running: [f] write to code segment
I wasn't killed - test fails!
Exit 1; expected signal 11
Running: [g] write to kernel address
Fatal user mode trap 5 sig 10 (Address error on store, epc 0x400394, vaddr 0x80000000)
Signal 10 (correct)
Running: [h] jump to NULL
Fatal user mode trap 2 sig 11 (TLB miss on load, epc 0x4003a0, vaddr 0x0)
Signal 11 (correct)
Running: [i] jump to invalid address
Fatal user mode trap 2 sig 11 (TLB miss on load, epc 0x4003ac, vaddr 0x40000000)
Signal 11 (correct)
Running: [j] jump to kernel address
Fatal user mode trap 4 sig 10 (Address error on load, epc 0x4003b8, vaddr 0x80000000)
Signal 10 (correct)
Running: [k] alignment error
Fatal user mode trap 4 sig 10 (Address error on load, epc 0x4003f0, vaddr 0x7fffffa9)
Signal 10 (correct)
Running: [l] illegal instruction
Fatal user mode trap 10 sig 4 (Illegal instruction, epc 0x4003c0, vaddr 0x0)
Signal 4 (correct)
Running: [m] divide by zero
Fatal user mode trap 9 sig 5 (Break instruction, epc 0x40042c, vaddr 0x0)
Signal 5 (correct)
Running: [n] mod by zero
Fatal user mode trap 9 sig 5 (Break instruction, epc 0x400468, vaddr 0x0)
Signal 5 (correct)
Running: [o] Recurse infinitely
Fatal user mode trap 3 sig 11 (TLB miss on store, epc 0x400488, vaddr 0x7ffedff0)
Signal 11 (correct)
Operation took 30.033709583 seconds

We have finished Assignment5!😊