# 2021q1 Homework1 (lab0)
contributed by < `hallblazzar` >
###### tags: `linux-kernel-internals-2021q1`
## Target 1: [CMU](https://www.cmu.edu) [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)
Finish the item below：
- [x] q_new: Create a new, empty queue.
- [x] q_free: Free all storage used by a queue.
- [x] q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
- [x] q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
- [x] q_remove_head: Attempt to remove the element at the head of the queue.
- [x] q_size: Compute the number of elements in the queue.
- [x] q_sort: Added by the class, Linux Kernel Internals. Sort elements in queue in ascending order according to methods in [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/).
### Requirements
- OS - [Ubuntu 20.04 (Focal Fossa)](https://releases.ubuntu.com/20.04/)
### Setup
- Install package below:
`$ sudo apt install build-essential git-core valgrind cppcheck clang-format aspell colordiff`
- Pull the [forked GitHub repository](https://github.com/HallBlazzar/lab0-c):
`git clone https://github.com/HallBlazzar/lab0-c.git`
- Build:
`make clean`
`make `
### Implementation
#### `queue_t` structure
- Add 2 extra fields, `tail` and `size`, to easier implement `q_size` and `q_insert_tail` in O(1).
#### `q_new`
- Perform NULL checking before initializing `q`.
#### `q_free`
* Iteratly free value and queue element.
#### `q_insert_head`
- Check queue not NULL and new queue element allocation before performing insertion.
- If `tail` is NULL, it means the element is the first element in the queue. So both `tail` and `heal` should point to the element.
#### `q_insert_tail`
- Element creation logic is the same as `q_insert_head`.
- Make the element be both `head` and `tail` if it is the first element, also decided by `tail` is NULL or not.
#### new_element
- Move element creation logic to isolated internal function to reuse it in `q_insert_head` and `q_insert_tail`.
- Check `malloc()` result before performing any operations.
- Allocate memory string by `strlen(s)+1`. The reason is `strlen()` won't take `\0`(NULL charactor) into account while counting string length. Additional add 1 as boundary size is required for placing `\0`.
- `strncpy()` is memory safe if memory size of destiniation is sufficient to copy charactors from source. Otherwise the fllowing issue might be caused:
- [Segmentation fault](https://en.wikipedia.org/wiki/Segmentation_fault) - Try to access inaccessible memory.
- Write to memory which should't be accessed. In my experience, I did write to [`magic_footer`](https://en.wikipedia.org/wiki/Segmentation_fault) and break `free()` funciton.`
#### `q_remove_head`
- Make sure queue and `head` exist before performing any operations.
- Check `sp` before copying `head->value`. This variable is used to show which element is removed on the `qtest` console.
- If the element is the only element in the queue, make sure both `head` and `tail` are set as NULL after removing the element.
- Free memory of string and element.
#### `q_size`
- Perform NULL queue check to decide what value to return.
#### `q_reverse`
- Use 3 variable to contorl queue reversing proccess.
:::success
todo: explain how reverse work
:::
#### `q_sort`
- Use merge sort(`merge()`, `merge_sort()`) and `strcmp()` as sorting algorithm.
- The `head` and `tail` pointers need to be re-assigened after sorting. Otherwise, they will still point to the original element.
- An interesting thing is, if write the queue dividing code as below, the whole merge sort algorithm will be slowed down:
```c
while (fast && fast = fast->next) {
slow = slow->next;
fast = fast->next;
}
```
It looks splitting queue with more element could significantly improve the algorithm's performance.
## Target 2: [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)
Compile the CMU C Programming Lab with with Address Sanitizer(ASan) enabled (`$ make SANITIZER=1`) to detect possible runtime memory corruption issues in `qtest` and fix them.
### Reproduce
There are 2 approaches to trigger memory corruption detection when ASan enable :
- `help`: Execute `help` comand in `./qtest`.
- `scoring`: Execute `make test`.
### Investigate
Both approaches could trigger `global buffer overflow` error. It looks the codes in both errors mentions will probably access content of global variables.
- `help`
```
==93918==ERROR: AddressSanitizer: global-buffer-overflow on address 0x562bfff5d3c0 at pc 0x562bfff467bd bp 0x7ffd78fc2090 sp 0x7ffd78fc2080
READ of size 4 at 0x562bfff5d3c0 thread T0
#0 0x562bfff467bc in do_help_cmd /home/hallblazzar/jserv/lab0-c/console.c:307
#1 0x562bfff468d0 in interpret_cmda /home/hallblazzar/jserv/lab0-c/console.c:221
#2 0x562bfff470b5 in interpret_cmd /home/hallblazzar/jserv/lab0-c/console.c:244
#3 0x562bfff487f8 in run_console /home/hallblazzar/jserv/lab0-c/console.c:660
#4 0x562bfff453e5 in main /home/hallblazzar/jserv/lab0-c/qtest.c:780
#5 0x7f9321bfa0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x562bfff42b8d in _start (/home/hallblazzar/jserv/lab0-c/qtest+0x8b8d)
0x562bfff5d3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x562bfff5d3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/hallblazzar/jserv/lab0-c/console.c:307 in do_help_cmd
```
- `scoring`
```
==93973==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b746e2b5e0 at pc 0x55b746e13ae8 bp 0x7fffc47edcc0 sp 0x7fffc47edcb0
READ of size 4 at 0x55b746e2b5e0 thread T0
#0 0x55b746e13ae7 in do_option_cmd /home/hallblazzar/jserv/lab0-c/console.c:369
#1 0x55b746e128d0 in interpret_cmda /home/hallblazzar/jserv/lab0-c/console.c:221
#2 0x55b746e130b5 in interpret_cmd /home/hallblazzar/jserv/lab0-c/console.c:244
#3 0x55b746e142e1 in cmd_select /home/hallblazzar/jserv/lab0-c/console.c:594
#4 0x55b746e1485b in run_console /home/hallblazzar/jserv/lab0-c/console.c:667
#5 0x55b746e113e5 in main /home/hallblazzar/jserv/lab0-c/qtest.c:780
#6 0x7f762be270b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55b746e0eb8d in _start (/home/hallblazzar/jserv/lab0-c/qtest+0x8b8d)
0x55b746e2b5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55b746e2b5e0) of size 1
```
Check the codes trigger the error, I could confirm that both of them do highly relate to a global varialbe, `param_list`.
- `help`
```c=307
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,plist->documentation);
```
- `scoring`
```c=369
int oldval = *plist->valp;
```
Therefore, I try do some test in the `console.c`, and I cound confirm that the pointer dereferencing of the `int` point, `plist->valp`, is the cause.
But the question is, why? For a integer pointer, these statement shouldn't cause it read more than 4 bytes.
After testing and tracing behaviors for a day, I could confirm the root cause is the boolean variables, `echo` and `simulation`. But to understand the reason, we need to know where are the `plist->valp` referened.
There are 2 functions use the filed:
- `do_help_cmd()`
- `do_option_cmd()`
In the beginning, I just focused on analyzing what `do_help_cmd` and the function refer to it, `add_cmd`, but nothing was found. I was unable to verify what cause pointer deferencing being broken. By contrast, when I traced `do_option_cmd`, I found something interesting:
```c=104
add_param("simulation", (int *) &simulation,"Start/Stop simulation mode", NULL);
add_param("verbose", &verblevel, "Verbosity level", NULL);
add_param("error", &err_limit, "Number of errors until exit", NULL);
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
In my understanding, the `add_param()` is used to add parameter for the `option` command in `./qtest` which changes runtime behavior while executing cother commands. If check codes in `qtest.c`, I could confirm that it actually refers to the following global variables to change each function's behavior:
- `bool simulation`
- `int verblevel`
- `int err_limit`
- `bool echo`
And the structure, `PELE` (`plist`'s data type) is used to refer to these global variables and modify their value in `add_param()` runtime. But why do `simulation` and `echo` need to additionally be converted?
The `add_param()` provides the answer. As the `add_param()` is called, these global variables are stored in the `plist->valp` field, so there are 2 different tyep of variables will be store in the field. Therefore, the cause seems be clear:
:::warning
When dereferencing, it looks 4 bytes(integer size) will be read from address stored in the pointer. But if what the address actually store is smaller than 4 bytes(e.g.,boolean), then reading 4 bytes will be overfolw. In addition, these variables are global variable, so the global-buffer-overflow error is thrown.
:::
As a result, I modify the data type of `simulation` and `echo` from `bool` to `integer`, and I could see both `help` and `scoring`(actually, `opion`) work properly now.
## Target 3: [Valgrind](https://valgrind.org/)
Use the Valgrind to solve memory issue for the `qtest`, and use the Massif to visualize memory usage during executing the `simulation` command.
### Issue 1: Read commands from file
#### Reproduce
Executing valgrind with `make valgrind`, and the following error will be reported for each test case:
```
==102682== 8 bytes in 1 blocks are still reachable in loss record 1 of 3
==102682== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==102682== by 0x4A5050E: strdup (strdup.c:42)
==102682== by 0x110081: linenoiseHistoryAdd (linenoise.c:1236)
==102682== by 0x110C14: linenoiseHistoryLoad (linenoise.c:1325)
==102682== by 0x10C24A: main (qtest.c:772)
==102682==
==102682== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==102682== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==102682== by 0x110041: linenoiseHistoryAdd (linenoise.c:1224)
==102682== by 0x110C14: linenoiseHistoryLoad (linenoise.c:1325)
==102682== by 0x10C24A: main (qtest.c:772)
==102682==
==102682== 195 bytes in 19 blocks are still reachable in loss record 3 of 3
==102682== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==102682== by 0x4A5050E: strdup (strdup.c:42)
==102682== by 0x10FFF5: linenoiseHistoryAdd (linenoise.c:1236)
==102682== by 0x110C14: linenoiseHistoryLoad (linenoise.c:1325)
==102682== by 0x10C24A: main (qtest.c:772)
==102682==
```
#### Investigate
Basically, the issue is caused by executing `qtest` via `-f` option, which means reading commands from file. As what `make test` do, `make valgrind` also read commands from test cases under `traces` directory. But the same issue doesn't occur if directly execute commands by manullay typing them. So the problem is, what's the difference between executing commands from files and manually typing?
First of all, from the error, `still reachable in loss`, it looks the problem does highly relate to unfreed memory after `qtest` exist. And after tracing codes from error obove, I could confirm that the issue should be caused by the memory allocated for the global variable, `history`.
Code trigger the issue is as below shows(`main()`):
```c
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE);
```
And the error shows in `linenoiseHistoryAdd()`(which is called by `linenoiseHIstoryLoad()`) , memory of `hisotyr` allocated in the following code are left unreleased:
```c=1236
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
```
To further understanding how does the problem be triggered, having more under standing to the difference between how commands being executing when they're read from file and manually typed. After verifying, I could confirm that the following part is important(`run_console()`):
```c=
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
```
While executing commands, if command file is passed, the varialbe, `has_infile`, will be `true`. So:
- Manually typed commands will be recorded in `history` variable.
- Commands read from command file will be executed but won't be recorded. Besides, no `linenoise`-related operations performed in `cmd_select()`.
As a result, to fix the issue, the most straightforward way is preventing initializing `history` in command file reading mode. Adding the following condition to check is command file passed could solve the problem:
```c
if (!infile_name)
{
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
```
:::success
>Not sure about why does the following code doesn't cause the same memory issue. The reason is the code looks doesn't free `history` but not cause the error. Further verifying `linenoise`' behavior is required.
>```
>linenoiseHistoryAdd(cmdline); /* Add to >the history. */
>linenoiseHistorySave(HISTORY_FILE); /* Save >the history on disk. */
>linenoiseFree(cmdline);
>```
:::
### Issue 2: Failed executed comands
#### Reproduce
To simply trigger the issue:
- Execute `valgrind -q --leak-check=full ./qtest`.
- Under interactive mode, type a invalid command(e.g., "`notexist`").
Then the error as following will be thrown:
{%gist HallBlazzar/f501d5bec75a7b3a678e2f80b275e4a0 %}
The issue also applies to other approaches could trigger error report while executing `qtest`. For instance, executing test case 17 when valgrind is enabled, which causes execution time increased and raises `ERROR: Probably not constant time`.
#### Investigate
Though the report is long, but it could still be summarized as below:
1. `32 bytes in 1 blocks are still reachable ...` error for memories allocated to `cmd_ptr` in `add_cmd()`. The time the error repeates, 17, also equals to the time the `add_cmd()` is called.
2. `40 bytes in 1 blocks are still reachable ...` error for memories allocated to `param_ptr` in `add_param()`. The time the error repeates, 7, also equals to the time the `add_param()` is called.
3. `8,216 bytes in 1 blocks are still reachable ...` error memories allocated to `buf_stack` for command file(!).
Therefore, the issue looks caused by resource are remained unreleased when eror occur during executing commands. But the problem is, what's the differece between error occur and normal execute?
In the beginning, the global variable, `err_cnt` looks provides a great answer to the question. When each `cmd` callback function, the `err_cnt` will be plus 1. However, it doesn't change behavior for the `finish_cmd()` function which is always be called no matter error occur or not. It means, resource cleanning up logic for `cmd_prt`/`param_ptr`/`buf_stack` in `do_quit_cmd()` should always be executed, which cannnot explain the phenomenon.
After adding a `report()` function(before that, I tried add many report functions to clarify which code is currently executed) in `finish_cmd()` function, and I could confirm that the function is never executed when error occur:
```c=
ok = ok && run_console(infile_name);
report(1, "here");
ok = ok && finish_cmd();
```
I realized that the issue should be the operation, "`&&`". In addition to `err_cnt`, when erro occur, `run_console()` command will also return `false`. Under the situation, the `ok` varialbe will be `false`, and the `finish_cmd()` will never be executed because the `ok` has already been `false`.
As a result, to make sure the `finish_cmd()` function could always be executed, and execution status of it could still used to decide `ok`, I fix the code as below, which resolve the issue:
```c=
ok = ok && run_console(infile_name);
bool finish_clean_up = finish_cmd();
ok = ok && finish_clean_up;
```
## Target 4: [Massif](https://www.valgrind.org/docs/manual/ms-manual.html)
Todo
## Target 5: Web server coroutine
Use [coroutine](https://en.wikipedia.org/wiki/Coroutine) and [tiny-web-server](https://github.com/7890/tiny-web-server) to implement a new command, `web`, to run a web server. In addition, during the execution of the web server, the `qtest` should still allow to accpt commands.
### Problem
Not sure about how to implement.
Though Coroutine could switch between different contexts to execute statements in them, once a statement in a context executes for long time, another context will be blocked.
For instance, to accept new commands, the `linenoise()` API call will stay accepting new charactors unless the user press `Enter`. If place user request checking statements for web server in another coroutine, they won't be executed when `linenoise()` is called. Besides, they'll also be blocked when other commands are executing.
### Solution
Approach 1 - We could place context switching API calls(`setjum()/longjmp()`) everywhere, but the code will looks ugly. Besides, it still cannot always ensure the coroutine won't be blocked.
Approach 2 - We could create a new thread/subprocess to run web server, but I'm not sure that satisfies the requirement.
### Update
### Implement
Implement command based on [tiny-web-server](https://github.com/7890/tiny-web-server):
- Divide `main()` to 2 functions:
- `run_server()` - Create web server socket.
- `handle_request()` - Accept connection and handle request.
- The web server execution process will be:
1. Run `web` command to create create socket.
2. In `run_console()`, polls connection each time accpting commands or "Enter" by `handle_request()`.
It provide a simple context switch function for web server.
## Target 6: How does select work
Explain:
1. How is select system call used in `qtest`.
2. Analyze `console.c`, and explain the considerations about using [`RIO` package in Ch10. in CS:APP ](csapp.cs.cmu.edu/2e/ch10-preview.pdf).
3. Implement a command interpreter terminal like `qtest` in new GitHub repository.
### 1. How is `select` system call used in `qtest` ###
After tracing, the only place use the system call in the `qtest` is in the `cmd_select()` in `console.c`. In `qtest`, the `cmd_select()` is used to read and execute commands from command files. But it looks the system call is not really useful in the `qtest`.
As the [`man page`](https://man7.org/linux/man-pages/man2/select.2.html) mentions, the system call:
- monitors multiple file descriptors.
- waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible).
However, reading lines from file doesn't require to perform checking for file descriptor. Those logic should be helpful when the input is from STDIN/network socket instead of file. I think this is also the way `cmd_select()` is designed, i.e., accepting different kind of source as input. Under the situation, `select()` system call is necessary.
### 2. Considerations about using [`RIO` package in Ch10. in CS:APP ](csapp.cs.cmu.edu/2e/ch10-preview.pdf)
For my understanding, I think the package is used to save kernel overhead.
From [Ch10. in CS:APP](csapp.cs.cmu.edu/2e/ch10-preview.pdf), we could know that to use data from a file, it will follow the procedure below:
```flow
file=>operation: Disk
memory=>operation: File Mapping Memory
app_memory=>operation: Application Memory
file->memory->app_memory
```
Each arrow represents overhead to kernel. Therefore, while loading data, if we could make basic exception handling in file mapping memory instead of in application memory, some overhead could be saved.
For instance, consider getting the following response or charactors while performing `read()`:
- `EINTR` while readon bytes from socket
- `EOF` charactor
- `EOL` charactor
If we filter out and handle these cases in file mapping memory, then we don't have to handle them after loading them into application memory, which save the kernel overhead from the file mapping memory to application memory.
### 3. Implement a command interpreter terminal like `qtest` in new GitHub repository.
Todo
## Target 7: Linenoise
Anylize how [antirez/linenoise](https://github.com/antirez/linenoise) works, especially the use of the [termios](https://man7.org/linux/man-pages/man3/termios.3.html).
Todo
## Target 8: Constant time
Read the thesis, [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf), and analyze how `simulation` mode validate time complexity. Besides, explain [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) and how `simulation` mode implement analyzing.
Note that there are some defects for the implement. Try to discuss them and provide workarounds/solutions.
Todo
## Target 9: Defect of RIO
Figure out implement defect of RIO in `qtest`, and make pull request.
Todo
Sign in with Wallet
Connect another wallet