# 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 ![](https://i.imgur.com/mNrPNRe.png) It allocate memory and end up zero, which means the program doesn't has memory leak. # Review : Dude, is my code constant time?