# 2021q1 Homework1 (lab0)
contributed by < `nickchenchj` >
###### tags: `linux2021`
> [GitHub repository](https://github.com/nickchenchj/lab0-c).
## Prerequisite
* [J01: lab0](https://hackmd.io/@sysprog/linux2021-lab0)
* [C Programming Lab: Assessing Your C Programming Skills](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)
## Programming Task
Your task is to modify the code in queue.h and queue.c to fully implement the following functions.
* `q_new`: Create a new, empty queue.
* `q_free`: Free all storage used by a queue.
* `q_insert_head`: Attempt to insert a new element at the head of the queue (LIFO discipline).
* `q_insert_tail`: Attempt to insert a new element at the tail of the queue (FIFO discipline).
* `q_remove_head`: Attempt to remove the element at the head of the queue.
* `q_size`: Compute the number of elements in the queue.
* `q_reverse`: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
* `q_sort`: Sort elements in the queue in ascending order.
## Implementation
### queue.h
In order to speed up `q_size()` and `q_insert_tail()`, I made a few changes in `queue_t`. First, I added a pointer to `list_ele_t` that pointed to the last element in the queue. Also, with the aim of querying size of the queue in a constant time bound ($O(1)$), I added a variable `size`, which stored the number of elements in the queue, to `queue_t`.
```diff
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
+ list_ele_t *tail;
+ int size;
} queue_t;
```
:::warning
TODO: use `diff` rather than source code listing to emphasize on what you did.
:notes: jserv
:::
:::info
FIX: I modified my notes, please check it.
:cow: nickchenchj
:::
### queue.c
#### `q_new`
* Description: `q_new()` creates an empty queue using `malloc()`, initializes the queue, and returns the address of the queue. Note that `q_new()` returns `NULL` if `malloc()` fails to allocate memory to the queue.
* code snippet of `q_new()`:
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### `q_free`
* Description: `q_free()` takes a `queue_t` pointer as parameter and deallocates the memory region pointed to by that pointer (including the memory region pointed to by each element in the queue).
* code snippet of `q_free()`:
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
for (list_ele_t *curr = q->head, *next; curr != NULL; curr = next) {
next = curr->next;
free(curr->value);
free(curr);
}
free(q);
}
```
#### `q_insert_head`
* Description: `q_insert_head()` takes a `queue_t` pointer and a string as parameters and inserts an element, which points to the string, at the head of the queue. This function returns `true` if the `queue_t` pointer is a valid pointer and memory is allocated to the new element successfully. Otherwise, it returns `false`.
* code snippet of `q_insert_head()`:
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc((len + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size++;
return true;
}
```
#### `q_insert_tail`
* Description: `q_insert_tail()` is similar to `q_insert_head()`, it takes a `queue_t` pointer and a string as parameters. Also, it returns `true` if memory allocations are successful, and returns `false` otherwise. The difference between `q_insert_head()` and `q_insert_tail()` is that `q_insert_head()` inserts an element at the head of the queue, while `q_insert_tail()` inserts an element at the tail of the queue.
* code snippet of `q_insert_tail()`:
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc((len + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
newh->next = NULL;
if (q->size == 0)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
#### `q_remove_head`
* Description: `q_remove_head()` removes an element from the head of the queue and frees the memory regions allocated for the string and the element itself. It returns `true` if the removal of the element is successful, and returns `false` otherwise.
* Note that the string is copied to `sp` before the element is freed and removed. The copied string will be used to validate the correctness of `q_remove_head()`.
* code snippet of `q_remove_head()`:
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *target = q->head;
q->head = q->head->next;
/* Copies removed string to sp */
if (sp) {
int len = strlen(target->value);
int max_len = len > bufsize - 1 ? bufsize - 1 : len;
strncpy(sp, target->value, max_len);
sp[max_len] = '\0';
}
q->size--;
if (q->size == 0)
q->tail = NULL;
free(target->value);
free(target);
return true;
}
```
#### `q_size`
* Description: `q_size()` returns the number of elements in the queue, and returns `0` if the queue does not exist. Note that `q_size()` has a time complexity of $O(1)$, because the current size of the queue is stored in the queue itself. (see [queue.h](#queue.h))
* code snippet of `q_size()`:
```c=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
#### `q_reverse`
* Description: `q_reverse()` reverses the order of elements in the queue.
* code snippet of `q_reverse`:
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *prev = NULL, *curr = q->tail = q->head;
while (curr) {
list_ele_t *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->head = prev;
}
```
:::warning
TODO: Rewrite the function with a pointer to pointer.
:::
<!-- #### `q_sort` (selection sort)
* Function:
* Sort elements of queue in ascending order
* No effect if `q` is `NULL` or empty. In addition, if `q` has only one element, do nothing.
* code snippet of `q_sort`:
```c=
/* Selection Sort */
void q_sort(queue_t *q)
{
/* Assures there are more than one element in the queue */
if (!q || !q->head)
return;
for (list_ele_t **front = &q->head; (*front)->next != NULL;
front = &(*front)->next) {
list_ele_t **prev_of_min = front;
/* Finds the previous element of minimum element in the list */
for (list_ele_t **ele = &(*front)->next; *ele != NULL;
ele = &(*ele)->next) {
bool is_smaller = strcmp((*ele)->value, (*prev_of_min)->value) < 0;
if (is_smaller)
prev_of_min = ele;
}
if (prev_of_min != front) {
list_ele_t *min = *prev_of_min;
list_ele_t *next = min->next;
if (min->next == NULL)
q->tail = *front;
/* Adjacent elements */
if ((*front)->next == *prev_of_min) {
min->next = *front;
(*front)->next = next;
} else {
min->next = (*front)->next;
(*front)->next = next;
*prev_of_min = *front;
}
*front = min;
}
}
}
```
* **ERROR**: Not sorted in ascending order
* After the changes, however, new error occurred. This time, the system showed that I have reached the time limit, which means that my sorting method is too inefficient. Therefore, I decided to change the sorting method from `selection_sort` to `merge_sort`.
* `q_sort` succeeded in a small number of elements:
 -->
:::danger
Use text instead of screenshot! Be friendly to the visually impaired.
:notes: jserv
:::
<!-- * `q_sort` failed in a large number of elements (TLE):
 -->
#### `q_sort`
* Description: `q_sort()` sorts the elements in the queue in ascending order. The algorithm I used to sort the queue is [merge sort](https://www.geeksforgeeks.org/merge-sort/).
> ###### ref: [2020q3 Homework1 (lab0) - Sort](https://hackmd.io/@RinHizakura/ByuY_q6AU#Sort) (contributed by [RinHizakura](https://hackmd.io/@RinHizakura))
* function prototypes:
```c=
void q_sort(queue_t *q);
void merge_sort(list_ele_t **head);
void front_back_split(list_ele_t *head,
list_ele_t **front_ref,
list_ele_t **back_ref);
list_ele_t *merge_sorted_list(list_ele_t *a, list_ele_t *b);
void insert_tail(list_ele_t **destRef, list_ele_t **sourceRef);
```
* `q_sort()`: Sort the queue using merge sort and update the head and tail of the queue.
```c=
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
merge_sort(&q->head);
list_ele_t *tmp = q->head;
while (tmp->next != NULL)
tmp = tmp->next;
q->tail = tmp;
}
```
:::warning
:warning: The time complexity of `q_sort()` is $O(n)$, because it needs to update `head` and `tail` by iterating through the sorted queue.
:::
* `merge_sort()`:
```c=
void merge_sort(list_ele_t **head)
{
/* Returns if there are less than two elements */
if (*head == NULL || (*head)->next == NULL)
return;
list_ele_t *a;
list_ele_t *b;
front_back_split(*head, &a, &b);
merge_sort(&a); /* Merges the left part of the list starting from a */
merge_sort(&b); /* Merges the right part of the list starting from b */
*head = merge_sorted_list(a, b);
}
```
* `front_back_split()`: Split the list in half (`a` and `b`).
```c=
void front_back_split(list_ele_t *head,
list_ele_t **front_ref,
list_ele_t **back_ref)
{
list_ele_t *slow = head;
list_ele_t *fast = head->next;
/* Finds the middle element (slow) in the list */
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
/* Cuts the list in half */
*front_ref = head;
*back_ref = slow->next;
slow->next = NULL;
}
```
* `merge_sorted_list()`: Merge two sorted list and return the new `head`.
```c=
list_ele_t *merge_sorted_list(list_ele_t *a, list_ele_t *b)
{
list_ele_t dummy; /* dummy.next points to the first element in the
destination list */
list_ele_t *tail = &dummy;
dummy.next = NULL;
while (1) {
if (a == NULL) {
/* Appends the rest elements in b to the list */
tail->next = b;
break;
} else if (b == NULL) {
/* Appends the rest elements in a to the list */
tail->next = a;
break;
}
/* Inserts an element to the end of the list */
if (strcmp(a->value, b->value) < 0) {
insert_tail(&(tail->next), &a);
} else {
insert_tail(&(tail->next), &b);
}
tail = tail->next;
}
return dummy.next;
}
```
* `insert_tail()`: Insert an element to the end of a list.
```c=
void insert_tail(list_ele_t **dest_ref, list_ele_t **source_ref)
{
/* Points to the first element in the source list */
list_ele_t *new_node = *source_ref;
/* Advances the source pointer */
*source_ref = new_node->next;
/* Links new_node to the first element in the destination list */
new_node->next = *dest_ref;
/* Lets new_node become the first element in the destination list */
*dest_ref = new_node;
}
```
* result:
```bash
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/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
--- trace-16-perf 6/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 100/100
```
## AddressSanitizer error
>[AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) (aka ASan) is a memory error detector for C/C++ introduced by Google. It finds:
>
>- [Use after free](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleUseAfterFree) (dangling pointer dereference)
>- [Heap buffer overflow](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleHeapOutOfBounds)
>- [Stack buffer overflow](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleStackOutOfBounds)
>- [Global buffer overflow](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleGlobalOutOfBounds)
>- [Use after return](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleUseAfterReturn)
>- [Use after scope](https://github.com/google/sanitizers/wiki/AddressSanitizerExampleUseAfterScope)
>- [Initialization order bugs](https://github.com/google/sanitizers/wiki/AddressSanitizerInitializationOrderFiasco)
>- [Memory leaks](https://github.com/google/sanitizers/wiki/AddressSanitizerLeakSanitizer)
### Error: global-buffer-overflow
In this section, I solved an [global-buffer-overflow error](https://docs.microsoft.com/en-us/cpp/sanitizers/error-global-buffer-overflow?view=msvc-160) triggered by AddressSanitizer. AddressSanitizer generated the error message when I typed `help` after executing `qtest`. Note that the program was compiled using `make SANITIZER=1`. The error message was as follows:
```shell=
cmd> help
Commands:
# ... | Display comment
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
time cmd arg ... | Time command execution
Options:
=================================================================
==44882==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55f35c217400 at pc 0x55f35c20190f bp 0x7ffc3a2bbeb0 sp 0x7ffc3a2bbea0
READ of size 4 at 0x55f35c217400 thread T0
#0 0x55f35c20190e in do_help_cmd /home/nick/projects/lab0-c/console.c:307
#1 0x55f35c201a22 in interpret_cmda /home/nick/projects/lab0-c/console.c:221
#2 0x55f35c202207 in interpret_cmd /home/nick/projects/lab0-c/console.c:244
#3 0x55f35c20394a in run_console /home/nick/projects/lab0-c/console.c:660
#4 0x55f35c200531 in main /home/nick/projects/lab0-c/qtest.c:788
#5 0x7fc2a36f90b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55f35c1fdb8d in _start (/home/nick/projects/lab0-c/qtest+0x8b8d)
0x55f35c217401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55f35c217400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/nick/projects/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0abeeb83ae30: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0abeeb83ae40: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0abeeb83ae50: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9
0x0abeeb83ae60: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9
0x0abeeb83ae70: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0abeeb83ae80:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0abeeb83ae90: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0abeeb83aea0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abeeb83aeb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abeeb83aec0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0abeeb83aed0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==44882==ABORTING
```
AddressSanitizer triggered this error message because it read `4` bytes (line 23) while the size of the variable `echo` being read was only `1` byte (line 32). Also, according to the error message (line 22-24), it indicated that the global buffer overflowed on line 307 in `console.c`. The corresponding code snippet was shown below:
```cpp=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;
}
```
The global variable `echo` (`console.c`) and struct pointer `param_ptr` (`console.h`) were defined as follows:
```cpp=58
/* console.c */
static bool echo = 0;
```
```cpp=
/* console.h */
typedef struct PELE *param_ptr;
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
The following code snippet showed that `echo` was pointed to by an **integer** pointer and was added to the parameter list on line 22 in function `init_cmd()`:
```cpp=
/* console.c */
void init_cmd()
{
cmd_list = NULL;
param_list = NULL;
err_cnt = 0;
quit_flag = false;
add_cmd("help", do_help_cmd, " | Show documentation");
add_cmd("option", do_option_cmd,
" [name val] | Display or set options");
add_cmd("quit", do_quit_cmd, " | Exit program");
add_cmd("source", do_source_cmd,
" file | Read commands from source file");
add_cmd("log", do_log_cmd, " file | Copy output to file");
add_cmd("time", do_time_cmd, " cmd arg ... | Time command execution");
add_cmd("#", do_comment_cmd, " ... | Display comment");
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);
init_in();
init_time(&last_time);
first_time = last_time;
}
```
From line 307 in `console.c`, `report()` interpreted `*plist->valp`, or `echo`, as an integer (`4` bytes), whereas `echo`, which was a boolean variable, only took `1` byte. AddressSanitizer detected such incorrect interpretation and therefore triggered an global-buffer-overflow error.
### Solution
Since the error was resulting from incorrect interpretations of boolean variables, I changed the type of those variables from boolean to integer and the problem was solved. The changes are as follows:
`console.h`:
```diff
-extern bool simulation;
+extern int simulation;
```
`console.c`:
```diff
-bool simulation = false;
+int simulation = 0;
-static bool echo = 0;
+static int echo = 0;
```
:::warning
TODO:
1. Implement coroutine.
2. Explain how `select` and `console.c` works.
3. Explain how [antirez/linenoise](https://github.com/antirez/linenoise) works and look into the usage of [termios](https://man7.org/linux/man-pages/man3/termios.3.html).
4. Read [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) and explain how `simulation` verifies time complexity with experiments rather than theoretical analyses. Explain how [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) works and find solutions to this project.
5. Find flaws in this project and fix them.
:::
Sign in with Wallet
Connect another wallet