# 2020q3 Homework1 (lab0)
contributed by < [stonelin](https://github.com/StoneLin0708) >
###### tags: `sysprog2020`
## Outline
* [Outline](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Outline)
* [Environment](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Environment)
* [Implement](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Implement)
* [X] queue_t
* [X] q_new
* [X] q_free
* [X] q_insert_head
* [X] q_insert_tail
* [X] q_remove_head
* [X] q_size
* [X] q_reverse
* [X] q_sort
* [The bug of qtest](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g?view#The-bug-of-qtest)
* [Valgrind](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g?both#Valgrind-amp-Massif)
## Environment
```bash
➜ uname -a
Linux stonelin-ncku 5.4.0-7642-generic #46~1598628707~20.04~040157c-Ubuntu SMP Fri Aug 28 18:02:16 UTC x86_64 x86_64 x86_64 GNU/Linux
➜ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## Implement
### queue_t
```c
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
} queue_t;
```
Add a pointer to tail element and a size cache to provide
$O(1)$ q_insert_tail and $O(1)$ q_size.
### q_new
```c
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;
}
```
$O(1)$
### q_free
```c
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
free(q->head->value);
list_ele_t *next = q->head->next;
free(q->head);
q->head = next;
}
free(q);
}
```
$O(N)$
Free the value, element and finilly queue it self.
### q_insert_\[head, tail\]
```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) {
const size_t l = strlen(s) + 1;
newh->value = malloc(l);
if (newh->value) {
strncpy(newh->value, s, l); // copy string
```
head:
```c
newh->next = q->head;
q->head = newh;
if (!q->tail) // first element
q->tail = newh;
++(q->size);
```
tail:
```c
newh->next = NULL;
if (q->tail)
q->tail->next = newh;
q->tail = newh;
if (!q->head) // first element
q->head = newh;
```
```c
return true;
}
free(newh);
}
return false;
}
```
$O(1)$
Create a new element and insert to head or tail, insert logic is a little bit different, both need to take care fore the first insert.
#### To do
* I use strlen combine with strncpy, but is should be same as only strcpy, need to find out if there is a safer way to do it. (the only solution I can figure out is not use null terminated string)
[stackoverflow](https://stackoverflow.com/questions/52207214/how-to-use-strncpy-correctly)
### q_remove_head
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q)
return false;
if (!q->head)
return false;
list_ele_t *node = q->head;
q->head = node->next;
if (q->tail == node)
q->tail = NULL;
size_t len = strlen(node->value);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
if (len > (bufsize - 1)) {
sp[bufsize - 1] = 0;
}
}
free(node->value);
free(node);
--(q->size);
return true;
}
```
$O(1)$
Remove did provide buffer size, but the strcpy issue still unsolved at insert.
### q_size
```c
int q_size(queue_t *q)
{
return !q ? 0 : q->size;
}
```
$O(1)$
Cuz implelmention of insert and remove both keep track of queue size, so it could just return cached size.
### q_reverse
```c
void q_reverse(queue_t *q)
{
if (!q)
return;
list_ele_t *cur = NULL;
q->tail = q->head;
while (q->head) {
list_ele_t *next = q->head->next;
q->head->next = cur;
cur = q->head;
q->head = next;
}
q->head = cur;
}
```
$O(N)$
### q_sort
sort is more tricky one, before read anything online I have implement this
```c
int cmp(const void *a, const void *b)
{
const list_ele_t *aa = *(list_ele_t **) a;
const list_ele_t *bb = *(list_ele_t **) b;
return strcmp(aa->value, bb->value);
}
void q_sort(queue_t *q){
const size_t s = q_size(q);
if (!s)
return;
list_ele_t *l[s];
{
list_ele_t *h = q->head;
for (int i = 0; i < s; ++i, h = h->next) {
l[i] = h;
}
}
qsort(l, s, sizeof(list_ele_t *), cmp);
q->head = l[0];
for (int i = 0; i < (s - 1); ++i) {
l[i]->next = l[i + 1];
}
q->tail = l[s - 1];
q->tail->next = NULL;
}
```
Speed: $O(NlogN)$
Space: $O(N)$
By using qsort at stdlib, extract all element from queue to a array, and re-link elements after sorting.
Queue to array and re-link should both take $O(N)$, qsort is [most likely](https://en.cppreference.com/w/c/algorithm/qsort) $O(NlogN)$. The array take $O(N)$ extra space.
**It overload the stack by creating large array in test.**
And head allocate is not allowed.
I find out on internet I should do merge sort instead using qsort, but I still didn't figure out how to doing it efficiently (since it take mulitiple split and neither do I want to cache all midpoint *which I can't without overloading stak* nor do I feel like to implement recursive version).
So I combine merge and qsort in this way
```c
list_ele_t *merge(list_ele_t *l, list_ele_t *r)
{
list_ele_t *h;
if (strcmp(l->value, r->value) < 0) {
h = l;
l = l->next;
} else {
h = r;
r = r->next;
}
list_ele_t *c = h;
while (l && r) {
if (strcmp(l->value, r->value) < 0) {
c->next = l;
l = l->next;
} else {
c->next = r;
r = r->next;
}
c = c->next;
}
c->next = l ? l : r;
return h;
}
int comp(const void *a, const void *b)
{
return strcmp((*(list_ele_t **) a)->value, (*(list_ele_t **) b)->value);
}
list_ele_t *quick_sort_sub(list_ele_t **l)
{
list_ele_t *arr[512]; // create array of elements
list_ele_t **end = &arr[512]; // set maximum
list_ele_t **begin;
// put list of elements into array, also find last element
for (begin = arr; (begin != end) && *l; *l = (*l)->next, ++begin)
*begin = *l;
end = begin;
qsort(arr, end - arr, sizeof(list_ele_t *), comp); // sort
for (begin = arr; (begin != end - 1);
++begin) // put array of elements back to list
(*begin)->next = *(begin + 1);
(*begin)->next = NULL; // cut last
return *arr;
}
void q_sort(queue_t *q)
{
const size_t s = q_size(q);
if (!s)
return;
list_ele_t *head = q->head;
list_ele_t *sorted = NULL;
while (head) { // terminate when no element left
// quick sort sub-list and modify head to next element after sorted list
list_ele_t *newh = quick_sort_sub(&head);
// merge two list if exist
sorted = sorted ? merge(sorted, newh) : newh;
}
q->head = sorted;
}
```
Speed: $O(NlogN)$
Space: $O(K)$ which K is number of element to be sort at once, 512 in my case.
Sort only $K$ element at once, and merge it after. it is not a clean solution, and I don't really know if it is faster than plain merge sort, to address that I sould do some perormance and memory test.
#### To do
* do performance test on each sorting algorithm
# The bug of qtest
After run
```bash
make SANITIZER=1
make test
```
I got this.
```bash
0x55838d6059a1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55838d6059a0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/stonelin/project/sysprog/lab0-c/console.c:368 in do_option_cmd
```
The error message cleary point out the line couse the buffer overflow, but I didn't read it carefully and just want to find what does 'simulation' do.
And I accidentally found another bug cause by 'echo' when running qtest and run help command.
```bash
==992535==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e4ece2c780 at pc 0x55e4ece1c4b5 bp 0x7ffd6672b230 sp 0x7ffd6672b220
READ of size 4 at 0x55e4ece2c780 thread T0
#0 0x55e4ece1c4b4 in do_help_cmd /home/stonelin/project/sysprog/lab0-c/console.c:306
#1 0x55e4ece1c5c8 in interpret_cmda /home/stonelin/project/sysprog/lab0-c/console.c:220
#2 0x55e4ece1d00f in interpret_cmd /home/stonelin/project/sysprog/lab0-c/console.c:243
#3 0x55e4ece1dee5 in cmd_select /home/stonelin/project/sysprog/lab0-c/console.c:607
#4 0x55e4ece1e088 in run_console /home/stonelin/project/sysprog/lab0-c/console.c:628
#5 0x55e4ece1b103 in main /home/stonelin/project/sysprog/lab0-c/qtest.c:772
#6 0x7f84ee6700b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x55e4ece188ed in _start (/home/stonelin/project/sysprog/lab0-c/qtest+0x78ed)
0x55e4ece2c781 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:58:13' (0x55e4ece2c780) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/stonelin/project/sysprog/lab0-c/console.c:306 in do_help_cmd
Shadow bytes around the buggy address
```
I notice those two variable are both type bool, and both reference once at console.c:init_cmd(), and cast to type (int*). after some trace and varification, I fix bug by change type of those two global variable from bool to int.
# Valgrind & Massif
```bash
make valgrind
valgrind --tool=massif /tmp/qtest.wj8opq -f traces/trace-12-malloc.cmd
massif-visualizer massif.out.994298
```
### Test result of trace-12-malloc.cmd
It allocate memory and end up zero, which means the program doesn't has memory leak.
# Review : Dude, is my code constant time?
Sign in with Wallet
Connect another wallet