###### tags: `CS162`

# Proj 1 Design Doc

## Group Members

* Richard Lin <[e-mail]>
* Siddharth Karia <[e-mail]>
* Lauren Go <[e-mail]>
* Leon Ming <[e-mail]>

## Task 1: Argument Passing

### Data Structures and Functions
1. Modify `process_execute()` and `start_process()` in `process.c` to pass only the first arg (filename) instead of entire command to `thread_create()` and `load()` respectively.
2. Modify `start_process()` in `process.c` to parse command line arguments and push appropriate data to the user stack.

### Algorithms
First, using `strtok_r()`, we will parse the string into its arguments separated by whitespace. We push each argument onto the stack in left-to-right order and determine argc in this process. The first argument will be used as the filename to the `load()` function.

Next, we will leave some amount of empty space on the stack to ensure the the stack pointer value is 16-byte aligned once all the pointers to the arguments have been pushed on. We will then push on a null pointer and the addresses of the arguments on the stack in right-to-left order. The addresses will be obtained by starting from the bottom of the arguments and iterating up string by string.

We then push the address of the leftmost argument (`argv[0]`) and `argc` onto the stack. At this point, the address should be 16-byte aligned. Then, we will push `0x0` to the stack as the return address of this function frame. Finally, we set the stack pointer to the address of `0x0` (return address).

### Synchronization
For this section, we do not have any shared resources.

### Rationale
We perform argument passing in the `start_process()` function because it simulates the return from an interrupt to start the process. It is easy for us to use the already created interrupt frame registers to know where on the stack to push our arguments.

In addition, `start_process()` calls `load()` on `file_name` which must be the name of an ELF executable. Since `file_name` also is the pointer for all arguments, including executable name, we have to parse `file_name` to get the executable name before calling `load()`.

## Task 2: Process Control Syscalls

### Data Structures and Functions
1. Create `check_uaddr()` function to validate user addresses before dereferencing, and to validate the first argument.
2. Create `wait_status` structure and `children` list structure in `thread.h` and add fields to PCB as appropriate.

From discussion section:

typedef struct wait_status
{
    struct list_elem elem; /* ‘children’ list element. */
    struct lock lock; /* Protects ref_cnt. */
    int ref_cnt; /* 2=child and parent both alive, 1=either child or parent alive, 0=child and parent both dead. */
    tid_t tid; /* Child thread id. */
    int exit_code; /* Child exit code, if dead. */
    struct semaphore dead; /* 0=child alive, 1=child dead. */
    struct semaphore loaded /* Initialized to 0. Enforces wait on child loading */
} wait_status;

In the thread struct, we add these members to the PCB section:

struct wait_status *wait_status;
struct list children;

3. Implement `process_wait()` and `process_exit()` functions in `process.c`.
4. Modify `syscall_handler()` function in `userprog/syscall.c` to enable syscalls `practice()`, `halt()`, `exit()`, `exec()`, and `wait()`.

### Algorithms

#### Validating User Addresses `check_uaddr()`
1. Check if `f->esp` is null. If null, exit.
2. Check if `*f->esp` is a valid user address (not kernel) (< `PHYS_BASE`) and does not point to unmapped memory (using `pagedir_get_page()` in `pagedir.c`)
3. To avoid the case of a n-byte memory region containg some bytes of valid memory and some bytes of invalid memory, check the beginning and end bytes of the arguments (`uint32_t* args`)

#### Create `wait_status` structure and `children` list structure in `thread.h` and add fields to PCB as appropriate
The `thread` struct will contain a list `wait_status` structures that represent children processes and a `wait_status` structure for its parent process. The `wait_status` is shared between a parent and child to communicate information and allow for synchronization. This is essential for wait and exec because they depend on a child process exiting or the child process to finish loading. The `wait_status` will contain locks and semaphores to ensure that members that are accessed by both parent and child do not encounter any race conditions.

#### Implement `process_wait()` and `process_exit()` functions in `process.c`
`process_wait()`: Iterating through the `children` list in the current process control block, find the child with the matching tid and call `sema_down()` on the `dead` semaphore for that child. If there is is no child found that matches the tid, return -1. The call to sema_down only returns after the child process exits. We can then decrement the `ref_cnt`, destroy the `wait_structure`, remove it from the `children `list, and return the `exit_code`.

`process_exit()`: This saves the exit code in `wait_structure`, call `sema_up()` on the `dead` semaphore, and decrements the `ref_cnt` member. If the `ref_cnt` is 0, then the `wait_structure` is freed. For each of the `wait_structure` in the `children` list, decrement `ref_cnt` and free the space if `ref_cnt` is 0 because the corresponding child is already dead. The thread is then terminated.

#### Modify `syscall_handler()` function in `userprog/syscall.c`
We start by adding multiple cases for each process control syscall in `syscall_handler()` inside `syscall.c`. This can be accomplished simply using a switch statement. All our logic for this part will go into the cases in this function.

For `practice()`, we get the integer argument using the `args` pointer, add one to it, and store the result in the eax register of our `intr_frame`. We'll then return the value.

`exit()` is already handled for us.

For `halt()`, we can just call `shutdown_power_off()`.

For `exec()`, we'll call `process_execute(cmd_line)`, which will create a new thread and process that runs the program specified by `cmd_line`. The `tid_t` from `process_execute` will be the same as the `pid_t` return from `exec` to keep a one-to-one mapping between threads and processes because processes are limited to single-threading in pintos. This also makes it easy to figure out which processes are running. If the thread fails to be created (-1 is returned from process_execute) or the executable cannot be loaded (the `ref_cnt` equals 1 after the parent finishes waiting for the child to load), we will return a `PID_ERROR` by storing it in the eax register. We will modify `init_thread()` to create a new `wait_status` struct, get the running thread i.e. the parent process using `thread_current`, and add the pointer to the new `wait_status` to the `children` list of the parent process. Once the `process_execute` function returns, the parent process can call `sema_down(&loaded)` on the child `wait_status` so that the syscall `exec` function only returns after the child calls `sema_up(&loaded)`, which occurs after it has attempted loading the executable.

For `wait`, we will call `process_wait(pid)`, which handles most of the functionality we want for `wait`. With the exit code as the return value from `process_wait`, we store it in eax and return.

### Synchronization
`wait_status` struct is shared across parent and child process in each of their `thread` structs.
`wait_status.lock` is used to prevent a race between the parent and child when either is trying to determine whether the other is still alive.
`wait_status.ref_cnt` specifies how many of the parent and child processes are still alive. This is protected by the `wait_status.lock` lock.
`wait_status.dead` is a semaphore that specifies whether the child process is dead, and it allows the parent to wait until the child is dead before proceeding.
`wait_status.loaded` is a semaphore that forces the parent process to wait until the child process has attempted to load its executable before proceeding.

#### Cases
1. **Parent calls wait before child exits**
Parent calls `sema_down(&wait_status.dead)`. The dead semaphore is 0 if the child has not exited, so the parent is waiting. Once the child exits, it will call `sema_up(&wait_status.dead)` and the parent call to `sema_down(&wait_status.dead)` will return. There is no race condition.
2. **Parent calls wait after child exits**
Child exits and calls `sema_up(&wait_status.dead)` and dead semaphore is now 1. When the parent calls wait, the function will return because the `sema_down(&wait_status.dead)` will return immediately. There is no race condition.
3. **Parent exits before child exits**
The parent will acquire the lock and decrement the `ref_cnt` before the child can, so `ref_cnt` is protected from race conditions.
4. **Parent exits after child exits**
The child will acquire the lock and decrement the `ref_cnt` before the parent can, so `ref_cnt` is protected from race conditions.

### Rationale

We validate user addresses before dereferencing because this seems to be simpler than utilizing the built in MMU page fault.

We decided to use a shared struct between the parent and each of its child processes because this protects other child processes from interacting with each other, which is the desired behavior. If we were to have a single structure for the parent that is shared with all children, this would become very complicated in terms of keeping track of which exit codes correspond to which pids and so on. We also decided to have three thread safety tools, one for altering the `wait_status` structure, one another for waiting for the child process to finish loading, and one for waiting for the child process to exit. Each of these allows for granular control for the specified task and minimize unnecessary waiting.

## Task 3: File Operation Syscalls

### Data Structures and Functions
1. Create a lock for the whole file system in `userprog/syscall.c` by adding `struct lock file_lock`
2. Create struct

struct file_folder {
    struct list_elem elem;
    struct file* f;
    int fd;
    char* name;
}

4. Add `struct list file_cabinet` to the process control block to keep track of files and file descriptors for each process
5. Add `file_count` variable to thread to return unique file descriptor every time a file is opened. `file_count` is initialized to 2 because 0 and 1 are reserved for standard input and standard output
6. Modify `syscall_handler()` function in `userprog/syscall.c` to enable syscalls `create()`, `remove()`, `open()`, `filesize()`, `read()`, `write()`, `seek()`, `tell()`, and `close()`.

### Algorithms

#### Acquiring a Lock
Before performing any operation involving file operation syscalls, we must acquire the global lock in `syscall.c`

#### Modify `syscall_handler()` function in `userprog/syscall.c`
For `create()`, we first acquire the file operation lock, then call `filesys_create (const char *name, off_t initial_size)` in `filesys/filesys.c` with the same parameters, and get the boolean returned. We then release the file lock, store the boolean in the eax register, and return it.

For `remove()`, we first acquire the file operation lock, then call `filesys_remove (const char *name)` in `filesys.c` by passing in the name, and get the boolean returned. We then release the file lock, store the boolean in the eax register, and return it. The boolean may be false even if the file name does not exist.

For `open()`, we acquire the file operation lock, then we call `filesys_open()` in `filesys.c` and get a `struct file*`. If the file is `NULL`, return -1. Increment the `file_count` variable of the current thread, and use that as the new file descriptor value. We create and add a new `file_folder` to the current thread's `file_cabinet` using the new fd value and the file pointer and the name of the file. Finally, increase `file_count` in the thread if it's successful. Store the file descriptor in the eax register, release the file lock, and return the file descriptor.

For the following functions, we check to make sure that the `fd` argument is valid.

For `filesize()`, we acquire the file operation lock, get the current thread, find the `struct file*` pointer by looking through `file_cabinet` for that thread, then call `file_length()` in `file.c` and save the number of bytes actually read (returned by `file_read()`) in the eax register. We then release the file lock.

For `read()`, we acquire the file operation lock; get the file pointer from the current thread's `file_cabinet`; call `file_read()` in `file.c` with the file pointer, buffer pointer, and size; and save the number of bytes actually read (returned by `file_read()`) in the eax register. We then release the file lock.
If file descriptor is 0, then we use `input_getc()` to read from stdin.
If file descriptor is 1, exit(-1) after releasing the file lock.

For `write()`, we acquire the file operation lock; get the file pointer from the current thread's `file_cabinet`; call `file_write (struct file *file, const void *buffer, off_t size)` in `file.c` with the file pointer, buffer pointer, and size; and save the number of bytes actually written (returned by `file_write()`) in the eax register. We then release the file lock.
In order to handle the case that we might be writing to a currently running executable, for every write we check that the file name is not the same as a thread in `all_list`. If it is running, skip the write.

For `seek()`, we acquire the file operation lock, then get the current thread, find the `struct file*` of the file by iterating through `file_cabinet` for the current thread, then call `file_seek()` from `file.c` on the file. We write the return value to the eax register and release the file lock.

For `tell()`, we acquire the file operation lock, get the current thread, find the `struct file*` pointer by looking through `file_cabinet` for that thread, then call `file_tell()` in `file.c` on the file pointer and write the return value to the eax register. We then release the file lock.

For `close()`, we acquire the file operation lock, get the current thread, find the `struct file*` pointer by looking through `file_cabinet` for that thread, then call `file_close()` in `file.c` on the file pointer and write the return value to the eax register. Next, we remove the `struct file_folder` entry from the `file_cabinet` list using linked list functions. We then release the file lock.

### Synchronization

We use the file operation lock on the entire set of filesys functions in order to maintain thread safety. We also have to make sure that we release the lock before we exit with code -1.

Because file operations are very common for user processes of all kinds, so it is likely that the global file operation lock will cause a measurable decrease in system concurrency.

We hope to design a finer system for synchronization during the filesystem project.

### Rationale

There is a lot of similarity among the file operations: obtaining the file lock, getting the current thread, getting the `file*` pointer using the file descriptor, storing a return value in the eax register, and releasing the file lock. This could be abstracted away through higher-order or helper functions.

We mandate that each thread maintains a list of files it opened to facilitate easy lookup of the struct file pointer via the file descriptor.

## Additional Questions

1. `child-bad.c` uses an invalid stack pointer. On line 12, `%esp` is set to`$0x20101234`, and an interrupt for a syscall is initiated. Since the stack pointer is invalid, the syscall should exit.
2. `sc-boundary-3.c` uses `p` as a pointer into memory. `p` is decremented by 1 byte into valid memory (line 14), while `%esp` is purposely left unchanged for the syscall (line 18). With everything but the first byte of `p` in invalid memory, the process should be killed.
3. In Task 1, passing arguments, we are supposed to allocate space on the stack for arguments passed into a function. However, the current tests do not test the case when the arguments are longer than a page. To test this, we need to write a command line argument that is longer than 4KiB.