# 2021q1 Homework1 (lab0)
###### tags: `linux2021`
contributed by <`Billy4195`>
## :penguin: Requirements
* [x] fork [lab0-c] on GitHub(https://github.com/sysprog21/lab0-c)
* [x] Reference: [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github)
* [x] Implementation
* [x] q_new
* [x] q_free
* [x] q_insert_head
* [x] q_insert_tail
* [x] q_remove_head
* [x] q_size
* [x] q_reverse
* [ ] q_sort
* [x] Fix address sanitizer
* [ ] Valgrind
* [ ] Check memory errors
* [ ] Use Massif to visualize the memory usage during the simulation(Need to design the experiment)
* [ ] Implement [coroutine](https://en.wikipedia.org/wiki/Coroutine) and provide new command `web`. Notice: `qtest` should be able to receive other commands when the web server is running.
* [ ] Try to integrate [tiny-web-server](https://github.com/7890/tiny-web-server), set the `FORK_COUNT` to 0 and use [coroutine](https://en.wikipedia.org/wiki/Coroutine) to replace the original system call.
* [ ] Explain the usage of [select](http://man7.org/linux/man-pages/man2/select.2.html) system call in this program.
* [ ] Analyze and explain the concern the implementation in [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) refer to CS:APP [RIO package](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf)
* [ ] Refer to [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward:, write an individual shell as `qtest` (Create an new GitHub repository)
* [ ] Explain how the [antirez/linenoise](https://github.com/antirez/linenoise) works and point out the usage of [termios](http://man7.org/linux/man-pages/man3/termios.3.html)
* [ ] Read the paper [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
* [ ] Explain how the "simuation" mode is implemented using the experiment to do the time complexity verfication instead of using theoretical analysis. Need to explain [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) and the implementation. (Notice: the implementation exists some defects, try to point out and give some solutions)
* [ ] Point out the defects(Hint: related to [RIO package](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf)) and send the pull request.
## Implementation
**[GitHub link](https://github.com/Billy4195/lab0-c)**
### Struct design for `queue_t`
For the extra attributes that I added is an pointer `tail` to point the tail element of the queue, and `size` to store the number of elements in queue.
These two attributes are needed for the constant execution time for `q_insert_tail` and `q_size`
```c=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Linked list of elements */
int size;
} queue_t;
```
### `q_new()`
Allocate the memory for `queue_t`, if the allocation fail then return NULL as SPEC required. If success, initialize the attributes
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (NULL == q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### `q_free()`
`q_free` is used to free all the allocated memory space inside the queue struct. It is better to free the allocated memory from the inner of struct to outer. Otherwise, if we free the outer struct without recording the inner allocated memory, then we may cause memory leak because doesn't free the inner one, or read from the freed outer memory is also an dangerous operation.
As a result, we just traverse every element inside of the queue and using `next` to store the next element. Firstly, free the value memory, then free the element itself. After freed all the elements in the queue, we could finally free the `queue_t` itself.
```c=
void q_free(queue_t *q)
{
list_ele_t *cur, *next;
if (q) {
cur = q->head;
while (cur) {
next = cur->next;
free(cur->value);
free(cur);
cur = next;
}
}
free(q);
}
```
### `q_insert_head()`
The point of this function is to allocate the space for new element. Because all the allocated memory by `malloc` will be tracked, we can't use `strdup` function to allocate memory for the given string.
The `tail` pointer should also be setup if it has not been set.
I should take carefully of `malloc` failure, as line 9 and line 14 are two check for the `malloc`. Especially for lineine 14, don't forget to freed the allcated space for element
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (NULL == q)
return false;
list_ele_t *newh;
int len = strlen(s);
newh = malloc(sizeof(list_ele_t));
if (NULL == newh)
goto fail_head;
newh->next = NULL;
newh->value = (char *) malloc(sizeof(char) * (len + 1));
if (NULL == newh->value)
goto fail_value;
memcpy(newh->value, s, len);
newh->value[len] = '\0';
newh->next = q->head;
q->head = newh;
if (NULL == q->tail)
q->tail = newh;
q->size++;
return true;
fail_value:
free(newh);
fail_head:
return false;
}
```
### `q_insert_tail`
The SPEC required us to implement an O(1) time complexity solution. As mentioned above, we have added a `tail` pointer to take care of this requirement. To achieve it, we just add element after the `tail` element and update the `tail` pointer.
The `head` pointer should also be check and set, if it has not been set.
I should also take care the `malloc` failure as we did in `q_insert_head`.
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (NULL == q)
return false;
int len = strlen(s);
list_ele_t *node = malloc(sizeof(list_ele_t));
if (NULL == node)
goto fail_head;
node->next = NULL;
node->value = malloc(sizeof(char) * (len + 1));
if (NULL == node->value)
goto fail_value;
memcpy(node->value, s, len);
node->value[len] = '\0';
if (q->tail)
q->tail->next = node;
q->tail = node;
if (NULL == q->head)
q->head = node;
q->size++;
return true;
fail_value:
free(node);
fail_head:
return false;
}
```
### `q_remove_head`
As the requirement, we store the string of the head element in given `sp` pointer in L8~L13. At line 14 check if the head is the only element in the queue, if yes then we reset the `tail` pointer, too.
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (NULL == q || NULL == q->head)
return false;
list_ele_t *node = q->head;
if (sp && bufsize > 0) {
int vlen = strlen(node->value);
int cpylen = vlen < bufsize ? vlen : bufsize - 1;
memcpy(sp, node->value, cpylen);
sp[cpylen] = '\0';
}
if (node == q->tail)
q->tail = NULL;
q->head = q->head->next;
free(node->value);
free(node);
q->size--;
return true;
}
```
### `q_size`
To achieve the O(1) time complexity, I use the added size attribute to record the size of the queue.
Check the corner case when the given queue is NULL.
```c=
int q_size(queue_t *q)
{
if (NULL == q)
return 0;
else
return q->size;
}
```
### `q_reverse`
I use to pointer `left` and `right` to traverse the queue and make the `next` pointer of each element point to the previous element to finish the reverse
```c=
void q_reverse(queue_t *q)
{
if (NULL == q || q->size <= 1)
return;
list_ele_t *left, *right;
list_ele_t *tmp, *prev;
prev = NULL;
left = q->head;
right = left->next;
tmp = right->next;
while (right) {
left->next = prev;
right->next = left;
prev = left;
left = right;
right = tmp;
tmp = tmp ? tmp->next : NULL;
}
left->next = prev;
tmp = q->head;
q->head = q->tail;
q->tail = tmp;
}
```
### `q_sort`
#### Recursive quick sort
I choose quick sort as the implementation of`q_sort`. However, the worse case for quick sort may cause O(N^2) time complexity.
```c=
void q_sort(queue_t *q)
{
if (NULL == q || q->size <= 1)
return;
list_ele_t *cur;
quick_sort(&(q->head));
cur = q->head;
while (cur->next) {
cur = cur->next;
}
q->tail = cur;
}
void list_add(list_ele_t **list, list_ele_t *node)
{
node->next = *list;
*list = node;
}
void list_concat(list_ele_t **left, list_ele_t *right)
{
while (*left) {
left = &((*left)->next);
}
*left = right;
}
void quick_sort(list_ele_t **list)
{
if (NULL == list || NULL == *list)
return;
list_ele_t *pivot;
list_ele_t *left = NULL, *right = NULL;
list_ele_t *ptr;
pivot = *list;
ptr = pivot->next;
pivot->next = NULL;
while (ptr) {
list_ele_t *node = ptr;
ptr = ptr->next;
if (strcmp(pivot->value, node->value) <= 0) {
list_add(&right, node);
} else {
list_add(&left, node);
}
}
quick_sort(&left);
quick_sort(&right);
*list = NULL;
list_concat(list, left);
list_concat(list, pivot);
list_concat(list, right);
}
```
#### Failure
After finish the `q_sort`, some related test passed, but some are still failed.
```shell=
--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-16-perf 0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 88/100
```
## Fix address sanitizer
As the SPEC mentioned, we need to fix the problem of address sanitizer, and and we can see the error message show at Line 15 that it is related to `echo` in `console.c`
```shell=
$ make SANITIZER=1
$ ./qtest
cmd> help
=================================================================
==103297==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5611d6d743c0 at pc 0x5611d6d5d7bd bp 0x7ffd209c6730 sp 0x7ffd209c6720
READ of size 4 at 0x5611d6d743c0 thread T0
#0 0x5611d6d5d7bc in do_help_cmd /home/su/repo/lab0-c/console.c:307
#1 0x5611d6d5d8d0 in interpret_cmda /home/su/repo/lab0-c/console.c:221
#2 0x5611d6d5e0b5 in interpret_cmd /home/su/repo/lab0-c/console.c:244
#3 0x5611d6d5f7f8 in run_console /home/su/repo/lab0-c/console.c:660
#4 0x5611d6d5c3e5 in main /home/su/repo/lab0-c/qtest.c:780
#5 0x7f2d76c260b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x5611d6d59b8d in _start (/home/su/repo/lab0-c/qtest+0x8b8d)
0x5611d6d743c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5611d6d743c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/su/repo/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac2bada6820: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ac2bada6830: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac2bada6840: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ac2bada6850: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac2bada6860: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac2bada6870: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ac2bada6880: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac2bada6890: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2bada68a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2bada68b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2bada68c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
```
Check console.c:307 in `do_help_cmd()`, we can see the problem happens at calling `report` function. While the error said that it's related to the global variable`echo` in console.c:59. So we could guess it has something to do with `param_ptr`.
```c=295
//console.c
static bool do_help_cmd(int argc, char *argv[])
{
cmd_ptr clist = cmd_list;
report(1, "Commands:", argv[0]);
while (clist) {
report(1, "\t%s\t%s", clist->name, clist->documentation);
clist = clist->next;
}
param_ptr plist = param_list;
report(1, "Options:");
while (plist) {
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
plist = plist->next;
}
return true;
}
```
Then we check the definition of `param_ptr` for `plist`and the call to add `echo` command in `console.c`.
```c=30
//console.h
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
```c=105
//console.c
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
We can see that the `echo` is declared as a bool type and in `add_param()` using an `int` pointer to store it in `param_ele` that is the cause for the address sanitizer error. To fix this problem we can just change the type from `bool` to `int` for the `echo` variable.
```c=58
// console.c
static int echo = 0;
```
# Problems
* Why the global variable `simulation` didn't cause the same error as `echo`, since it it also declared as `bool` type
> Notes: sorting without problem https://hackmd.io/@jasonmatobo/2021q1_homweork_lab0
> merge sort without error https://hackmd.io/@gyes00205/2021q1_lab0
Sign in with Wallet
Connect another wallet