# 2019q1 Homework1 (lab0)
contributed by < `yiwei01` >
###### tags: `sysprog2019`
## Development environment
```shell
$ uname -a
Linux yiwei-X550JX 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc--version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
```
## lab0 requirement
* 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.
## How to achieve lab0 requirement step by step
### Data structure design
To meet the requirement that ```q_insert_tail``` and ```q_size``` operate in time O(1), I add **list_ele_t \*tail** and **int size** fields in queue_t structure in queue.h.
```clike=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### q_new
Allocate memory to new queue. If ```malloc``` dose not return NULL, then initialize the queue and return its starting address, else return NULL.
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
### q_size
By adding **int size** field in queue_t structure, ```q_size``` can operate in time O(1).
>Problems encountered and solved :
>I forget to check NULL pointer which result in NULL pointer dereference. Hence, I add a NULL pointer check when returning the value.
```clike=
int q_size(queue_t *q)
{
return !q ? 0 : q->size;
}
```
### q_insert_head
Before inserting new element, check if queue exists and can allocate enough space. In addition, I use additional variable **unsigned int len_s** to record the length of **s** in case that **s** is NULL but be taken as input of ```strlen```. When copying string, I use ```strncpy``` and assign '\0' to the last address of (newh->value). At the end, update **q->head** and **q->size** (and **q->tail** if needed).
>Problems encountered and solved :
>I misuse ```strcat(newh->value,"\0")``` to add terminating character after ```strncpy(newh->value, s, len_s);```. However, ```strcat``` overwrites the terminating null byte ('\0') at the end of ++dest++, so if there is not terminating character in ++dest++, it may has unexpected garbled message in it.
```clike=
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;
}
unsigned int len_s = !s ? 0 : strlen(s);
newh->value = malloc((len_s + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len_s);
(newh->value)[len_s] = '\0';
newh->next = q->head;
q->head = newh;
if (!q->tail) {
q->tail = newh;
}
q->size++;
return true;
}
```
### q_insert_tail
Almost as same as ```q_insert_head```, the subtle difference is that ```q_insert_tail``` has to check if **q->tail** exists. If **q->tail** exists, assign new list element to **q->tail->next**. At the end, update **q->tail** and **q->size** (and **q->head** if needed).
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q) {
return false;
}
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
unsigned int len_s = !s ? 0 : strlen(s);
newt->value = malloc((len_s + 1) * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, len_s);
(newt->value)[len_s] = '\0';
newt->next = NULL;
if (q->tail) {
q->tail->next = newt;
}
q->tail = newt;
if (!q->head) {
q->head = newt;
}
q->size++;
return true;
}
```
### q_remove_head
First, check if there are elements in **q** can be removed. Second, copying string from **q->head->value** to **sp**. Third, use additional variable **list_ele_t \*tmp** to record **q->head** then remove **tmp->value** and **tmp**. At the end, update **q->size**.
> After applying cppcheck, I'm reminded that "Unsigned variable 'bufsize' can't be negative so it is unnecessary to test it." So, I remove unnecessary assertion in Line 3.
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
assert(bufsize >= 0); /* This line is removed
after applying cppcheck */
if (!q || !q->head) {
return false;
}
if (sp && q->head->value) {
unsigned int copy_len = bufsize > 0 ? bufsize - 1 : 0;
strncpy(sp, q->head->value, copy_len);
sp[copy_len] = '\0';
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_free
Use **list_ele_t \*ptr** to record current **q->head** and an additional variable **list_ele_t \*tmp** to record **ptr->next**, after **ptr->value** and **ptr** are freed, assign **tmp** to **ptr** before go on next iteration. At the end, free **q**.
```clike=
void q_free(queue_t *q)
{
if (!q) {
return;
}
for (list_ele_t *ptr = q->head; ptr;) {
list_ele_t *tmp = ptr->next;
free(ptr->value);
free(ptr);
ptr = tmp;
}
free(q);
}
```
### q_reverse
If queue is not NULL, use **list_ele_t \*prev** to record the previous list elment and **list_ele_t \*next** to record the next element. Then reverse links by assigning **prev** to **curr->next**.
```clike=
void q_reverse(queue_t *q)
{
if (!q) {
return;
}
list_ele_t *prev = NULL, *next = NULL;
list_ele_t *curr = q->head;
q->tail = q->head;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->head = prev;
}
```
## Learning GNU/Linux development tools
### perf
>Problem encountered ( Installation ) :
```$ cat /proc/sys/kernel/perf_event_paranoid``` return 3
solved by :
```$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"```
or
```
sudo sysctl kernel.perf_event_paranoid=1
```
## How to improve performance
透過 perf ，我發現我的 ```q_reverse``` 算是整支程式的 bottleneck
Todo : 想改進方式
```
Samples: 3K of event 'cycles:ppp', Event count (approx.): 2894699324
Overhead Command Shared Object Symbol ◆
19.12% qtest libc-2.27.so [.] _int_malloc ▒
12.55% qtest qtest [.] q_reverse ▒
7.56% qtest qtest [.] test_free ▒
7.23% qtest libc-2.27.so [.] cfree@GLIBC_2.2.5 ▒
5.88% qtest libc-2.27.so [.] malloc ▒
5.13% qtest qtest [.] find_footer ▒
4.95% qtest qtest [.] test_malloc ▒
2.71% qtest libc-2.27.so [.] __memset_avx2_unaligned_erms ▒
2.71% qtest [kernel] [k] 0xffffffff86d8bf47 ▒
2.01% qtest qtest [.] find_header ▒
1.88% qtest qtest [.] q_insert_head ▒
1.86% qtest libc-2.27.so [.] __random_r
...
```
## How automatic scoring system works
## Behavior and skills in qtest
[0xff07](https://hackmd.io/s/SJnc7dtSN) 同學的筆記已紀錄的很完整，自己理解過後再整理一次重點：
1. programmer 呼叫的 malloc 已被替換成 test_malloc
2. programmer 呼叫的 free 已被替換成 test_free
3. programmer 呼叫的 strdup 已被替換成 test_strdup
資料結構圖示：
* block_ele_t :
* struct BELE *next : 指向 ```allocated```(doubly linked list) 的下一個 node
* struct BELE *prev : 指向 ```allocated```(doubly linked list) 的上一個 node
* size_t payload_size : 紀錄 programmer 呼叫 ```malloc``` 時要求的大小
* size_t magic_header : 用以驗證這塊 allocate 出去的 block 是否還合法
* unsigned char payload[0] : 真正能讓 programmer 使用的空間。
* 其為 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 的用法，其特徵為 : 當 zero-length array 是 **structure** 中的最後一個 member 時，則呼叫 malloc(sizeof( **structure** ) + <font color="red">指定大小</font>)時，該 **structure** 中的 zero-length array 得到的可用空間即為<font color="red">指定大小</font>。觀察 harness.c，可發現在 ```test_malloc``` 中便利用了此特性。
```clike=
block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
size : programmer 呼叫 malloc 時要求的大小( payload )
sizeof(size_t) : 額外給 magic_footer 的空間。
* 註 : block_ele_t 裡的 magic_header 與 magic_footer 皆是用來驗證這塊 block 是否還合法。在 ```test_malloc``` 中初始 magic_header 的值為 0xdeadbeef ， magic_footer 的值為 0xbeefdead，因此若該 block 的 magic_header 或 magic_footer 的值被更改，則代表此塊 block 曾被非法存取。
### find_header 與 find_footer
回傳 header 與 footer 的位址，其中 ```find_header``` 會檢查傳入的 block 是否真的是 allocated block，並檢查 magic_header 是否被更改過
### test_malloc
檢查現在是否為可分配的模式、此次分配是否成功、是否擁有足夠空間滿足使用者的要求，若成功則分配空間給使用者，並會在 block 紀錄分配多大的大小、初始 magic_header 與 magic_footer，最後加入 **allocated** 這個 doubly linked list
### test_free
檢查現在是否為可分配的模式、欲 free 的空間是否為 NULL、magic_footer 是否被更改過，若通過上述檢查，則將 payload 以 FILLCHAR 來覆蓋，並將 magic_header、 magic_footer assign 為 MAGICFREE，最後移出 doubly linked list
### test_strdup
將 ```strdup``` 會呼叫到的 ```malloc``` 替換為呼叫 ```test_malloc```.
Sign in with Wallet
Connect another wallet