# CS333 – Introduction to Operating Systems
## Project 01 - Intro Xv6
### Member
* 21125020 - Dang Trung Nghia
* 21125029 - Tran Tuan Viet

### 1. Introduction
The following report is Lab: Systemcall Xv6 which is from course CS333 - Introduction to Operating Systems. This project aims to get familiar with xv6 and its system calls by solving the problems which are mentioned in detail in the second part of this report.

### 2. Detail Explanation
**a) Boot xv6 (easy)**

The main forcus of this problem is to set up xv6:
* Set up enviroment (Ubuntu, Debian, ...)
* Clone the resposition:

    git clone git://g.csail.mit.edu/xv6-labs-2023

* Build and run xv6:

    make qemu

**b) Sleep (easy)**

In this assignment, we need to implement **sleep** program for xv6, where the **sleep** should pause for a user-specified number of ticks.
With the support of **sleep** system call of xv6, we can easily complete this problem by 2 steps:
* Firstly check if the user forgets to pass an argument, sleep should print an error message.

    if (argc < 2)
    {
        fprintf(2, "Forget to pass argument\n");
        exit(1);
    }

* Secondly, with **atoi** (from *user/ulib.c*), then we can pause for a while.

    sleep(atoi(argv[1]));
    exit(0);

The output of our **sleep** program:

    xv6 kernel is booting

    hart 1 starting
    hart 2 starting
    init: starting sh
    $ sleep
    Forget to pass argument  # When user for get the pass argument
    $ sleep 10 # Pause program for 10 ticks
    $ 

**c) Pingpong (easy)**

The statement of this problem is to uses xv6 system calls to "ping-pong" a byte between two processes over a pair of pipes, one for each direction.
Our approach is to create a pipe by **pipe()** system call, then use **fork()** system call to create a child process which share the same pipe as its parent. After that, we can easily communicate between parent process and child process. Therefore, when we use read() and write(), the parent can get the content writed by its child.
* Create a pipe

    int p[2];
    pipe(p);

* Use **fork()** system call and exchange a byte between 2 processes

    if (fork() == 0)
    {
        char c;
        read(p[0], &c, 1);
        printf("%d: received ping\n", getpid());
        write(p[1], "y", 1);
    }
    else
    {
        write(p[1], "x", 1);
        char c;
        read(p[0], &c, 1);
        printf("%d: received pong\n", getpid());
    }
    exit(0);

The output of our program:

    xv6 kernel is booting

    hart 2 starting
    hart 1 starting
    init: starting sh
    $ pingpong
    4: received ping
    3: received pong
    $ pingpong
    exec pingpong failed
    $ pingpong
    7: received ping
    6: received pong
    $ pingpong
    9: received ping
    8: received pong
    $ pingpong
    11: received ping
    10: received pong

**d) Primes (moderate)/(hard)**

The statement of this assignment is to write a concurrent prime sieve program for xv6 using pipes.
The idea for this problem firstly is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, we will arrange to create one process that reads from its left neighbour over a pipe and writes to its right neighbour over another pipe based on [the Sieve of Eratosthenes](https://www.geeksforgeeks.org/sieve-of-eratosthenes/).
Loop from 2 to 35. Write them to pipe one by one. Read the first one from pipe buffer. Then record as **Num**. Create a new pipe, write everything not dividable by **Num**.
For example:
* The first process consists: 2, 3, ..., 35 (**2** is **Num**).
* The second process consists: 3, 5, 7, ..., (**3** is **Num**, get rid of numbers that are not diviable by previous Num).
* And so on until having all primes.

The first process is created by the following code:

    if (fork() == 0)
    {
        for (int i = 2; i <= 35; i++)
        {
            write(p[1], &i, sizeof(i));
        }
        close(p[1]);
        exit(0);
    }

The code for writing all numbers that is not dividable to **Num**:

    int i;
    while (read(p[0], &i, sizeof(i)) == sizeof(i))
    {
        if (i % n != 0)
        {
            write(q[1], &i, sizeof(i));
        }
    }
    close(p[0]);
    close(q[1]);
    wait((int *)0);

The output of our program:

    xv6 kernel is booting

    hart 2 starting
    hart 1 starting
    init: starting sh
    $ primes
    prime 2
    prime 3
    prime 5
    prime 7
    prime 11
    prime 13
    prime 17
    prime 19
    prime 23
    prime 29
    prime 31

**e) Find (moderate)**

In this problem, with a specific file's name, we use a recursive function to find all occurrence of the file.

We define the recursive function:

void find(char *path, char *name)

This function use to find the file `name` in the directory `path`. The function work with the following strategy:

* If the current `path` is a file:
* if the name of the current file is `name` then we found an occurrence of the target file, so we just print the `path` and `return`.
* Otherwise, just `return`.
* If the current `path` is a folder: loop through all the element `x` in the folder and call `find` funtion into that element `find("path/x", name)`.

switch(st.type) {
        case T_FILE:
            if(strcmp(name, fmtname(path)) == 0)
                fprintf(1, "%s\n", path);
            break;

        case T_DIR:
            if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
                fprintf(1, "find: path too long\n");
                break;
            }
            strcpy(buf, path);
            p = buf+strlen(buf);
            *p++ = '/';
            while(read(fd, &de, sizeof(de)) == sizeof(de)) {
                if(de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                    continue;
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                find(buf, name);
            }
            break;
    }

An example of the output of our program:

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ echo > b
$ mkdir a
$ echo > a/b
$ mkdir a/aa
$ echo > a/aa/b
$ find . b
./b
./a/b
./a/aa/b

**f) Xargs (moderate)**

In this problem, there are 2 main things we need to focus: the argument outside of the xarg executing and the argument of xarg executing. We will have a list of characters to to control the argument outside of the xarg executing. In detail, we will loop until the current character is '\n', then we will execute **xarg** program with **xarg** arguments, then continue executing others with list characters argument above.

In order to get argument from xargs and combine them with argument outside xargs program, we implement the following function:

    void getCmdArguments(char **preArgv, int preArgc, char *newArgv, char **argv)
    {
        int k = 0;
        for (int i = 0; i < preArgc; i++)
        {
            argv[k] = malloc(strlen(preArgv[i]) + 1);
            memcpy(argv[k++], preArgv[i], strlen(preArgv[i]) + 1);
        }
        argv[k] = malloc(strlen(newArgv) + 1);
        memcpy(argv[k++], newArgv, strlen(newArgv) + 1);
}

Then we execute the program to get the result:

    int curArgc = argc;
    char *curArgv[MAXARG];

    getCmdArguments(argv + 1, argc - 1, lstArg, curArgv);
    curArgv[curArgc] = 0;

    exec(curArgv[0], curArgv);

An example of the output of our program:

    xv6 kernel is booting

    hart 2 starting
    hart 1 starting
    init: starting sh
    $ echo hello too | xargs echo bye
    bye hello too