# CS162 Final Report Group 54

## New Changes

## Task 1

bool setup_args_on_stack(char* file_name, void** esp); 

Instead of having the stack arguments being pushed in `setup_stack` we decided to have a seperate function `setup_args_on_stack` after calling load() to ensure that load actually runs properly before pushing arguments onto the stack. This ensures that if load fails, we won't have to worry about the arguments being pushed even if the load fails.

We also decided to have `setup_args_on_stack` return a boolean so that if the arguments that we pushed on was too large and moved the esp into invalid

We also had to change the call to `load` to only include the first token seen in `file_name` so that we execute corectly.

## Task 2
### 2.1 Data Structure/Functions

typedef struct thread_history {
  tid_t child_tid;
  enum thread_status status; //copy status from childs thread to thread_history
                             //used to ensure use of elem to only one process at a time
  struct semaphore semaphore;
  //just to keep track of ref_cnt
  struct lock lock;
  int ref_cnt; // should be initialized to two when execing
  struct list_elem elem;
} shared_data_t;

struct file_map {
  int fd; 
  struct file* fp;
  char* file_name;
  struct list_elem elem;
};

struct thread {
  /* Owned by thread.c. */
  struct list children;  // list of thread histories
  struct thread_history* myself; //info of child, written by child, null for parent  
  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;
  int last_fd;
  struct list file_map_list;
  /* Priority. */
  struct list_elem allelem; /* List element for all threads list. */
  struct file* my_file;
  /* Shared between thread.c and synch.c. */ 
  struct list_elem elem; /* List element. */

### 2.2 Algorithms
We realized for `exec()` we needed to call `process_execute` instead of load to make sure we create a thread properly.

We also needed to make sure for the `process_exit` call we are freeing appropriately, making sure to cleanup any thread_history structures whose reference count was 0 and any open file descriptors and any `file_map` structures we used for task 3.

int process_wait(tid_t child_tid) {
    -Waits for thread TID to die and returns its exit status
    -If it was terminated by the kernel (i.e. killed due to an
   exception), returns -1
   -If it was terminated by the kernel (i.e. killed due to an
   exception), returns -1 immediately, without waiting.
}

//changes to process_execute
tid_t process_execute(const char* file_name){
    -aquire thread history structure of newly created thread 
    by calling thread_findchild(tid)
    -down semaphore of thread history structure to wait until process
    has loaded
}

//changes to start_process
static void start_process(void* file_name_) {
    -up semaphore in thread history struct of current thread when either:
        -process fails to load OR
        -calling load fails OR
        -when it successfully loads
}

struct thread_history* thread_findchild(tid_t child) {
    -iterates through parents children list to find the thread_history
    struct corresponding to tid_t = child
    -if found returns the struct, else returns NULL
}

static struct thread* findbytid(tid_t tid)  {
    -find thread struct corresponding to tid
    -return if it exists, else return NULL
}

static void addchild(struct thread* t) {
    -set myself thread history structs status to t's status
    -aquire lock to increase ref_cnt by 1
    -release lock
    -add t's thread history struct to the current thread's children list
}

int thread_status(tid_t tid) {
    -returns the status of the thread corresponding to tid if it exists
}

bool valid_user_pointer(const void* user_pointer) {
    -takes in a pointer to memory as user_pointer
    -casts to unint8_t, stores as copy
    -calls check_valid on all 4 bytes of copy
    -returns false if any of the bytes invalid, true otherwise
}

static bool check_valid(uint8_t* ptr) [
    -returns false if ptr is NULL or pointer is not a user address
        or if pointer is not in threads page directory
]

bool validate_buffer(const void* string_buffer, int size) {
   -validates the memory address of string_buffer up to size 
}

bool validate_char(const void* string_buffer) {
    -checks if memory address is valid of everything until a '\0' is found
    -returns true if everything valid, false otherwise
}

### 2.3 Synchronization

We also realized that when we call `exec()` we need to wait for `start_process` to complete to get the status of the newly created thread. To implement, we used our method `thread_findchild` to retrieve the `thread_history` of the newly created child. With the childs `thread_history`, we call `sema_down` on the semaphore in the child's`thread_history` to wait until `start_process` has either sucessfully completed which we then call `sema_up` on said semaphore or the call to `load` failed which we set the `thread_history` status equal to `thread_error` then call `sema_up`.

## Task 3
### Data Structures/Functions and Algorithms
To ensure that a processes executable does not get modified by any other processes we did the following:

- Add a `FILE * my_file` field in `thread.h` to keep track of a thread's executable file
- assign my_file to be the thread's executable file in `load`
- call `file_deny_write` on 'my_file' in `load` within `process_execute`
- call `file_allow_write` on `my_file` in `process_exit`

## Student Testing report

### First Test Case: syn-tell

This test goes over the implementation of the `syscall_tell` function since it's not tested in the tests given to use.

For our test, we re used the syn-write test and create 10 children and write into 'stuff' for each of the children in seperate chunks. Then we check after we right if tell points to the right location and the end of the chunk the child thread is supposed to write.

The result of `userprog/build/tests/ilesys/base/syn-tell.output` is:

Copying tests/filesys/base/syn-tell to scratch partition...
Copying tests/filesys/base/child-syn-tell to scratch partition...
qemu-system-i386 -device isa-debug-exit -hda /tmp/EazpAIjbRl.dsk -m 4 -net none -nographic -monitor null
PiLo hda1
Loading...........
Kernel command line: -q -f extract run syn-tell
Pintos booting with 3,968 kB RAM...
367 pages available in kernel pool.
367 pages available in user pool.
Calibrating timer...  523,468,800 loops/s.
hda: 5,040 sectors (2 MB), model "QM00001", serial "QEMU HARDDISK"
hda1: 183 sectors (91 kB), Pintos OS kernel (20)
hda2: 4,096 sectors (2 MB), Pintos file system (21)
hda3: 226 sectors (113 kB), Pintos scratch (22)
filesys: using hda2
scratch: using hda3
Formatting file system...done.
Boot complete.
Extracting ustar archive from scratch device into file system...
Putting 'syn-tell' into the file system...
Putting 'child-syn-tell' into the file system...
Erasing ustar archive...
Executing 'syn-tell':
(syn-tell) begin
(syn-tell) create "stuff"
(syn-tell) exec child 1 of 10: "child-syn-tell 0"
(syn-tell) exec child 2 of 10: "child-syn-tell 1"
child-syn-tell: exit(0)
(syn-tell) exec child 3 of 10: "child-syn-tell 2"
child-syn-tell: exit(1)
(syn-tell) exec child 4 of 10: "child-syn-tell 3"
child-syn-tell: exit(2)
(syn-tell) exec child 5 of 10: "child-syn-tell 4"
child-syn-tell: exit(3)
(syn-tell) exec child 6 of 10: "child-syn-tell 5"
child-syn-tell: exit(4)
(syn-tell) exec child 7 of 10: "child-syn-tell 6"
child-syn-tell: exit(5)
(syn-tell) exec child 8 of 10: "child-syn-tell 7"
child-syn-tell: exit(6)
(syn-tell) exec child 9 of 10: "child-syn-tell 8"
child-syn-tell: exit(7)
(syn-tell) exec child 10 of 10: "child-syn-tell 9"
child-syn-tell: exit(8)
(syn-tell) wait for child 1 of 10 returned 0 (expected 0)
(syn-tell) wait for child 2 of 10 returned 1 (expected 1)
(syn-tell) wait for child 3 of 10 returned 2 (expected 2)
(syn-tell) wait for child 4 of 10 returned 3 (expected 3)
(syn-tell) wait for child 5 of 10 returned 4 (expected 4)
(syn-tell) wait for child 6 of 10 returned 5 (expected 5)
(syn-tell) wait for child 7 of 10 returned 6 (expected 6)
(syn-tell) wait for child 8 of 10 returned 7 (expected 7)
(syn-tell) wait for child 9 of 10 returned 8 (expected 8)
child-syn-tell: exit(9)
(syn-tell) wait for child 10 of 10 returned 9 (expected 9)
(syn-tell) open "stuff"
(syn-tell) read "stuff"
(syn-tell) end
syn-tell: exit(0)
Execution of 'syn-tell' complete.
Timer: 94 ticks
Thread: 29 idle ticks, 58 kernel ticks, 7 user ticks
hda2 (filesys): 576 reads, 482 writes
hda3 (scratch): 225 reads, 2 writes
Console: 2326 characters output
Keyboard: 0 keys pressed
Exception: 0 page faults
Powering off...

The result of `userprog/build/tests/filesys/base/seek_tell.result` is just:

PASS

One non trivial potential kernel bugs is that locking is not implemented in the kernel which makes `tell` not thread safe. This means that in the case of multiple threads, if we had created two seperate threads to `write` into the file and to get the result of `tell` from the file we could have executed `tell` before `write` and `tell` would return the wrong byte offset.

Another non trivial kernel bug is that file fds are not implemented properly. If fds were shared across processes we wouldn't be able to write into files across different threads as when one thread closes the file we wouldn't be able to write in other threads.

## Second Test Case: open_multiple
In this test case we try overloading the file descriptor table for a process to ensure we don't have any memory leaks.
We open a file 129 times and check if the 129th call to open fails since the limit for file descriptors should be 128.

The result of `userprog/build/tests/userprof/open_multiple.output` is:

Copying tests/userprog/open_multiple to scratch partition...
Copying ../../tests/userprog/sample.txt to scratch partition...
qemu-system-i386 -device isa-debug-exit -hda /tmp/Q5JCPlI0N4.dsk -m 4 -net none -nographic -monitor null
PiLo hda1
Loading...........
Kernel command line: -q -f extract run open_multiple
Pintos booting with 3,968 kB RAM...
367 pages available in kernel pool.
367 pages available in user pool.
Calibrating timer...  549,683,200 loops/s.
hda: 5,040 sectors (2 MB), model "QM00001", serial "QEMU HARDDISK"
hda1: 183 sectors (91 kB), Pintos OS kernel (20)
hda2: 4,096 sectors (2 MB), Pintos file system (21)
hda3: 106 sectors (53 kB), Pintos scratch (22)
filesys: using hda2
scratch: using hda3
Formatting file system...done.
Boot complete.
Extracting ustar archive from scratch device into file system...
Putting 'open_multiple' into the file system...
Putting 'sample.txt' into the file system...
Erasing ustar archive...
Executing 'open_multiple':
(open_multiple) begin
(open_multiple) create "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) open "test.txt"
(open_multiple) end
open_multiple: exit(0)
Execution of 'open_multiple' complete.
Timer: 106 ticks
Thread: 20 idle ticks, 60 kernel ticks, 27 user ticks
hda2 (filesys): 624 reads, 223 writes
hda3 (scratch): 105 reads, 2 writes
Console: 5124 characters output
Keyboard: 0 keys pressed
Exception: 0 page faults
Powering off...

The result of `userprog/build/tests/userprof/open_multiple.result` is:

PASS

One non trivial bug is that the kernel does not provide a limit for the number of file descriptors opened. This could lead to a potential memory overload issue where the user fills up all their memory with file descriptors and prevents them from running any further tasks that require memory.

Another non trivial bug is that the kernel fails to implement different file descriptors for seperate openings of the same file. This would allow the last write to work because there is only one file descriptor opened which is not the proper implementation for file descriptors in PintOS.

### Tell us about your experience writing tests for Pintos.

In order to come up with two thorough tests, we had to go through all existing tests and check which functions they called or didn't call to see what was and what wasn't tested. Through our searching we found that tell wasn't tested, so we made sure that syscall-tell behaved correctly. Looking through the project 1 spec we also found out an interesting test case about overloading the file descriptor table for a process, so we decided to test for it to ensure we don’t have any memory leaks in the case that the user was opening many files for a process.

### What can be improved about the Pintos testing system? (There’s a lot of room for improvement.)

Overall we wished there was a little more documentation about how to write test cases, because for the `syn-tell` function we were a little confused about how child threads/processes were called. The `Make.tests` file could have also been easier to use as a lot of the syntax was really messy and hard to understand.

### What did you learn from writing test cases?

By writing test cases, we made sure all our functions working correctly. Also, we spent more time thinking about edge cases we needed to cover. This helped us understand some of the existing tests more thouroghly instead of mindlessly just running the autograder.

# Reflection

Overall, this project was a lot of work. We did fairly well on helping each other to work out the details of how to implement complex tasks in the project. We could improve our time management skills by budgeting specific times to work. We could also strive to have shorter bursts of more productive work meetings rather than longer meetings with lower productivity. We tried to split up the work and pair program between with groups of two. This worked fairly well to implement small, less complex tasks. However, our system failed when working on complex tasks. We could improve our ability to tackle complex tasks by working together in contrast to having fragmented ideas on what to do about the complex tasks. Initially, Cole and Max revised the design doc while Connie and Khang worked out the code for Task 1. Cole and Max then worked on implementing the logic for certain syscalls such as halt, wait, and exec. Connie and Khang worked on implementing file system calls such as read, filesize, open, write, and seek, in addition to implementing a way to keep track of files. Khang spent a lot of time debugging in office hours while Cole spent a lot of time waiting in office hours, only to not be seen by anyone. In the last days, we got together and helped each other to debug some failed test cases, also we brainstormed about possible non trivial bugs we could write for two of our own test cases.