Design Document for Project 1: User Programs
============================================

# Group Members

* Chuan-Jiun Yang <[e-mail]>
* Wei-Hsuan Hsu <[e-mail]>
* Benjamin Lamphere <[e-mail]>
* Yuxin Zhao <[e-mail]>

# Task 1: Argument Passing
## Data Structures and functions
> Write down any struct definitions, global (or static) variables, typedefs, or enumerations that you will be adding or modifying (if it already exists). These definitions should be written with the C programming language, not with pseudocode. Include a brief explanation the purpose of each modification. Your explanations should be as concise as possible. Leave the full explanation to the following sections.
1. To pass the command line arguments, we need to parse the input and create a struct to store the parsed arguments.

struct arguments{
    int argc;
    char *argv[];
};

3. While `strtok_r` can handle most use-cases, it has a flaw in that commands like `echo "de'f' ghi" '123"a"bc' a b c` would be split into too many arguments. We will create our own parser to support quoted arguments, with both single- and double- quotes. Edge cases include mixing quotes and unmatched quotes. Then we simply construct the `struct` and pass it into `process_execute(char *file_name)`.

3. We also need to modify the functions
`bool load (const char *file_name, void (**eip) (void), void **esp);` and
`static void start_process (void *file_name_);` to support the `struct arguments` structure.

## Algorithms
> This is where you tell us how your code will work. Your description should be at a level below the high level description of requirements given in the assignment. We have read the project spec too, so it is unnecessary to repeat or rephrase what is stated here. On the other hand, your description should be at a level above the code itself. Don't give a line-by-line run-down of what code you plan to write. Instead, you should try to convince us that your design satisfies all the requirements, including any uncommon edge cases. We expect you to read through the Pintos source code when preparing your design document, and your design document should refer to the Pintos source when necessary to clarify your implementation.

The command-line arguments will be passed in as `char*` from `process_execute(char *file_name)`, we first parse the input using parsing function `strtok_r()`. Then we need to implement our own argument parser to deal with single and double quotes, and solve the edge cases including mixed quotes, incomplete commands with `<`, `>`, or `|`. Next, we would construct the struct arguments and the input edge cases would be dealt with here.

In the function `bool load()`, we should allocate space for a minimal stack when setting up the register %esp in the function `static bool setup_stack (void **esp);`. Each argument should be pushed on the stack one by one following the 80x86 calling convention. And we need to push return address on the stack after pushing the arguments. And the stack pointer points to the return address.

## Synchronization
> This section should list all resources that are shared across threads. For each case, enumerate how the resources are accessed (e.g., from an interrupt context, etc), and describe the strategy you plan to use to ensure that these resources are shared and modified safely. For each resource, demonstrate that your design ensures correct behavior and avoids deadlock. In general, the best synchronization strategies are simple and easily verifiable. If your synchronization strategy is difficult to explain, this is a good indication that you should simplify your strategy. Please discuss the time/memory costs of your synchronization approach, and whether your strategy will significantly limit the concurrency of the kernel and/or user processes. When discussing the parallelism allowed by your approach, explain how frequently threads will contend on the shared resources, and any limits on the number of threads that can enter independent critical sections at a single time. You should aim to avoid locking strategies that are overly coarse.

For task 1, the arguments structure is not shared across threads. Synchronization strategy is not needed for task 1.

## Rationale
> Tell us why your design is better than the alternatives that you considered, or point out any shortcomings it may have. You should think about whether your design is easy to conceptualize, how much coding it will require, the time/space complexity of your algorithms, and how easy/difficult it would be to extend your design to accommodate additional features.

For the parsing part, a quote-parsing agorithm should be linear in both time and space. In practical terms, there should be very little overhead for the algorithm.

As for extending the design, there are two components: syntax and function. For syntax, we should after a certain point just define a formal grammar and use a compiler-generator like `antlr`, but it depends on how complex the desired additions are. Functional additions (such as the pipe operator) are more the domain of a shell than this interface, and it will be left to the user to develop such utilities if they desire.

# Task 2: Process Control Syscalls
>Pintos currently only supports one syscall: exit. You will add support for the following new syscalls: halt, exec, wait, and practice.
## Data Structures and functions

1. We choose to use the provided `get_user` and `put_user` functions to check the segment fault by reading or writing a byte at the user address.
`static int get_user (const uint8_t *uaddr);`
`static bool put_user (uint8_t *udst, uint8_t byte);`
2. To implement the four syscalls, we need to realize their corresponding syscall handlers in `pintos/src/userprog/syscall.c`.
+ `void halt(void)`: This system call is used to terminate Pintos. We could use `power_off()` defined in `threads/init.h`
+ `pid_t exec(const char *file)`: The system call is to start executing a thread. We plan to use `process_execute()` defined in `process.c` to implement the exec handler.
+ `int wait(pid_t pid)`: This system call is used when a parent thread is waiting for a child thread to finish. We could use `process_wait()` defined in `process.c`
+ `int practice(int i)`: This system call is relatively simple. We don't use any functions to implement, instead we simply return the input param + 1

3. To implement wait() syscall, we create the `struct child_status` to keep track of the process's completion state. With `struct semaphore child_dead` in the struct, we'll delete `static struct semaphore temporary;`.

struct child_status{
    struct semaphore child_dead;
    int child_exit_code;
    struct list_elem elem;
    tid_t child_tid;
    int ref_cnt;
    struct lock lock;
};
struct child_status *wait_status;
struct list children;

## Algorithms
To realize safe memory read and write, we should first check whether the user address is below PHYS_BASE, and then dereference it. While dereferencing it, we plan to use `get_user()` and `put_user()` provided in the spec in `syscall.c`(refer to 4.1.4 in project 1 spec). If a value of -1 is returned, we need to handle this page fault in `page_fault()` in `execption.c` by copying `%eax` to `%eip` and then setting `%eax` as `0xffffffff`.

We will implement the four syscall functions seperately in `pintos/src/userprog/syscall.c`, and then call each function in `static void syscall_handler()` according to `args[0]`.

According to Section 2: Synchronization, Signals, Files, to implement `wait()`, we first need to find the child from the `struct list children`. Then we call `sema_down()` to wait for the child to die. In function `process_exit()`, `sema_up()` will be called to send signal to indicate the parent that the child exits. With the child's exit code, we can destroy the data structure and remove it from the list.

## Synchronization
1. The `semaphore child_dead` is shared between threads. The `child_dead` will be initialized to zero in `process_execute()`, and it's used for the parent to wait for its child process to exit. When there is a barrier needed, the parent will call `wait` which will lead to `process_wait()`, and inside the function, there will be a `sema_down()` to wait for the `child_dead` to become positive. When the child process exits, `process_exit()` will invoke `sema_up()` to signal its parent. If the `process_wait()` happens before the child exits, the parent process will wait until the `child_dead` is positive. On the other hand, if `process_wait()` is called after the child exits, then the `child_dead` will be positive already and the parent process wouldn't be blocked. Each `process_wait()` should be paired with a `process_exit()` so that there would be no deadlocks.

2. The `ref_cnt` would also be shared between threads. It will be accessed when `process_exit()` is invoked to keep track of the thread references. To maintain the atomicity of it in case of a race condition between parent and child process, we'll have the `lock` to lock and unlock `ref_cnt` before and after accessing it to provide mutual exclusion.

## Rationale
In order to complete this part, it is necessary to realize safe read and write to memory. We have adopted the approach of accessing memory first and handling fault in `page_fault()`. Another approach is to utilize the functions in `pagedir.c` and `vaddr.h` to check whether the address is valid before accessing it. Although the second approach sounds simpler and more intuitive, we have decided to use the first approach because it could be faster with the help of processor's MMU.

# Task 3: File Operation Syscalls
>In addition to the process control syscalls, you will also need to implement these file operation syscalls: create, remove, open, filesize, read, write, seek, tell, and close.
## Data Structures and functions
1. We need to realize the corresponding functions for these syscalls in `pintos/src/userprog/syscall.c`.

bool create (const char *file, unsigned initial_size);
bool remove (const char *file);
int open (const char *file);
int filesize (int fd);
int read (int fd, void *buffer, unsigned length);
int write (int fd, const void *buffer, unsigned length);
void seek (int fd, unsigned position);
unsigned tell (int fd);
void close (int fd);

2. We need to create a structure of file containing file descriptor, and maintain a list of such structure for one process. Because the interface of these syscalls uses `int fd`, and the interface of the functions that we plan to use in the file system library uses `struct file*`, we should connect file descriptor and file structure. Also, a list of file structure is useful to keep track of all files for one process. Considering the synchronization design for task 2 and that pintos processes are one to one mapped with threads, we can modify `struct thread` as following. The `struct list files` stores `struct file_info` for each of the threads.

struct file_info{
    int fd;
    struct file* file;
    struct list_elem elem;
};

struct thread{
    /* Owned by thread.c. */
    struct list files;                  /*list of files*/
    struct list children;               /*list of all wait status struct for the children*/
    struct children_status *wait_status;
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    uint8_t *stack;                     /* Saved stack pointer. */
    int priority;                       /* Priority. */
    struct list_elem allelem;           /* List element for all threads list. */

    /* Shared between thread.c and synch.c. */
    struct list_elem elem;              /* List element. */

#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint32_t *pagedir;                  /* Page directory. */
#endif

    /* Owned by thread.c. */
    unsigned magic;                     /* Detects stack overflow. */
  };

3. To find the file according to the file descriptor, we need to implement the function `struct file* fd_to_file(int fd)` where we search through the list of files of the current process to find the file descriptor according to the input and return the file structure.

4. Create a `struct lock file_sys_lock` in `filesys.h` to lock files naively.

## Algorithms

For these syscalls functions:
* `create()`: it can be implemented by `bool
filesys_create (const char *name, off_t initial_size)` defined in `filesys.c`, which can creates a file named `NAME` with the given `SIZE`.
* `remove()`: it can be implemented by `bool
filesys_remove (const char *name)` defined in `filesys.c`
* `open()`: it can open the file given the pathname and return the file descriptor. It can be implemened by `struct file * filesys_open (const char *name)` defined in `filesys.c` and `struct file * file_open (struct inode *inode)` defined in `file.c`. In the mean time, we need to consider the uniqueness and existence of the file descriptor returned from `open()`. Two distinct files cannot have the same file descirptor. Hence we need to generate different fds when opening the file.
* `filesize()`: it can be implemented by `off_t
file_length (struct file *file)` defined in `file.c`.
* `read()`: it can be implemented by `off_t
file_read (struct file *file, void *buffer, off_t size)` defined in `file.c`.
* `write()`: it can be implemented by `off_t
file_write (struct file *file, const void *buffer, off_t size)` defined in `file.c`.
* `seek()` : it can be implemented by `void
file_seek (struct file *file, off_t new_pos)` defined in `file.c`.
* `tell()`: it can be implemented by `off_t
file_tell (struct file *file)` defined in `file.c`
* `close()`: we need to search through the list to find the file with the file descriptor same as the input by the function `struct file* fd_to_file(int fd)`, and then call `void file_close (struct file *file)` defined in `file.c`.

We will call each function in `static void syscall_handler()` according to the value of `args[0]`.

If the file descriptor does not exist for the current process, we need to return an error code.

## Synchronization
1. The whole file system is shared by the processes. With all these syscalls, the files in ths file system can be modified concurrently. To simplify synchronization, the file system now can be considered as a critical region. We will use a global lock `struct lock file_sys_lock` to lock files whenever there is a call to file system system call. We can acquire lock at the begining of each file operation and release lock after completing the function.

2. The executable file can be shared among two or more processes, and thus the executable file risks being modified by `write()` operation when it's currently running. To deny write to the executable file of the current process, in the function `load()` when reading the executable file, we can use `file_deny_write()`, which is defined in `file.c`. We can call `file_deny_write(file)` after opening the executable file by `file = filesys_open (file_name);` and before reading and verifying executable header. After the file is no longer running, for example, the process that executes the file exits, we need to call `file_allow_write(file)` to re-enable write operations to the file.

## Rationale
Instead of implementing these syscall functions by ourselves, we directly use the existing operations in the file library and get the file structure required by these existing operations from file descriptor. It's much faster and easier to implement it based on these existing functions. And as mentioned in multiple places, we do not need to deal with sophoticated file system synchronization now, and thus we choose to use a global lock as a simple solution.

# Additional Questions
1. The test is called `sc-bad-sp`. At line 18, the program invokes a system call with the stack pointer (`%esp`) set to a bad address `$.-(64*1024*1024)`. The address assigned to the stack pointer is 64MB below the code segment. Hence the stack pointer is invalid and the process must be terminated.

2. The test is `sc-bad-arg`. At line 14, `%esp` is set to `$0xbffffffc`, which is one word away from `PHYS_BASE`, so only one argument can be pushed to the stack, and according to the code, `%0`(the input `SYS_EXIT`) is pushed on the stack. A system call has many parameters, e.g. argc, argv, word alighments... etc. A system call is invoked at line 14, yet the system call params are stored in kernel address space because `%esp` is set incorrectly. As a result, the program wouldn't be able to safely access them.

3. The test `/pintos/src/tests/userprog/write-zero.c` does not fully test what happens when writing zero-length data to a file. While it does check that the return value of `write(...)` is correct, it does not check the file to ensure that no data was written.