# 2021q1 Homework1 (lab0)
contributed by < `yellow-hank` >
###### tags: `LinuxKernel`
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
## Queue 實作
### Structure
### queue
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* End of list */
size_t size; /* list size */
} queue_t;
```
#### linked list
```cpp
typedef struct ELE {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct ELE *next;
} list_ele_t;
```
### functions
#### q_new
:::spoiler code
```cpp
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
// check malloc whether allocating space sucess or not
if (!q) {
return q;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
:::
- 產生一個新的 queue 的資料結構，若是配置記憶體失敗，則回傳 NULL ，餅切初始化 queue 的變數
#### q_free
:::spoiler code
```cpp
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q) {
return;
}
/* go through each list node to release value's space.
* After release value's space, release list node
*/
for (; q->head != NULL;) {
free(q->head->value);
list_ele_t *delete_node = q->head;
q->head = q->head->next;
free(delete_node);
}
free(q);
}
```
:::
**釋放一個 queue ，裡面有兩個節點的示意圖**
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> delete_node"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct3;
struct3:f1 -> struct4;
}
```
更改第一個 next 指向方式，並且讓 head 指向下一個節點
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> delete_node"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
}
```
釋放 delete_node 指向的空間，並且讓 delete_node 指向下一個節點
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> delete_node"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct3;
}
```
#### q_insert_head
:::spoiler code
```cpp
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
char *s_new;
// check malloc whether allocating space sucess or not
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
// allocate space for string
s_new = malloc(sizeof(char) * (strlen(s) + 1));
if (!s_new) {
free(newh);
return false;
}
// deal with the first time inserting node
if (!q->head) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
newh->value = s_new;
/*using memcpy because strcpy may cause source string won't
* have a teminating character and it may crash program.
*/
memcpy(s_new, s, strlen(s) + 1);
q->size++;
return true;
}
```
:::
- 這裡使用 memcpy ，是因為 strcpy 會導致 '\0' 有機會不會被放入，可能會使程式存取到非法的空間，使程式終止。
- 在進行除錯時，發現如果在第二次配置記體失敗時，要記得將先前配置的空間釋放掉，第一次撰寫未注意到導致測試未通過。
**示意圖**
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> newh"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> newh"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct3:f1 -> struct4:f0;
struct2:f1 -> struct4;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> newh"];
struct2 [label="<f0> head"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct3:f1 -> struct4:f0;
struct2:f1 -> struct3;
}
```
#### q_insert_tail
:::spoiler code
```cpp
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
char *s_new;
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
s_new = malloc(sizeof(char) * (strlen(s) + 1));
if (!s_new) {
free(newh);
return false;
}
newh->next = NULL;
if (q->tail) {
q->tail->next = newh;
} else {
q->head = newh;
}
q->tail = newh;
newh->value = s_new;
/*using memcpy because strcpy may cause source string won't
* have a teminating character and it may crash program.
*/
memcpy(s_new, s, strlen(s) + 1);
q->size++;
return true;
}
```
:::
- 這裡使用 memcpy ，是因為 strcpy 會導致 '\0' 有機會不會被放入，可能會使程式存取到非法的空間，使程式終止。
- 為了實現時間複雜度為 O(1) ，在 queue 的結構中加入一個變數紀錄 list 的末端，如此一來，可以在常數時間內加入資料在末端。
**示意圖**
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> tail"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
struct3:f1 -> struct4:f0;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> tail"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="<f0> newh"];
struct6 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
struct3:f1 -> struct4:f0;
struct5:f1 -> struct6;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> tail"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="<f0> newh"];
struct6 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
struct3:f1 -> struct4:f0;
struct5:f1 -> struct6;
struct4:f1 -> struct6:f0;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> tail"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="<f0> newh"];
struct6 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct6;
struct3:f1 -> struct4:f0;
struct5:f1 -> struct6;
struct4:f1 -> struct6:f0;
}
```
#### q_remove_head
:::spoiler code
```cpp
/*
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
* The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *delete_ptr;
if (!q) {
return false;
}
if (!q->head) {
return false;
}
if (sp) {
memcpy(sp, q->head->value, bufsize);
sp[bufsize - 1] = '\0';
}
free(q->head->value);
delete_ptr = q->head;
q->head = q->head->next;
free(delete_ptr);
q->size--;
return true;
}
```
:::
- 這裡需要注意的是節點中的 value 需要被釋放，因為先前是透過 malloc 配置，若不進行釋放記憶體使用量會隨時間增加，可能會導致記憶體不足的情況
- 先釋放 value 空間，而後釋放整個節點。
**示意圖**
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> delete_ptr"];
struct3 [label="<f0> tail"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct4;
struct2:f1 -> struct4;
struct3:f1 -> struct5:f0;
struct4:f1 -> struct5:f0;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct2 [label="<f0> delete_ptr"];
struct3 [label="<f0> tail"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct5;
struct2:f1 -> struct4;
struct3:f1 -> struct5:f0;
}
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> head"];
struct3 [label="<f0> tail"];
struct5 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct5;
struct3:f1 -> struct5:f0;
}
```
#### q_size
:::spoiler code
```cpp
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
/* using a variable in queue_t to store size.After insert or remove
* operation increase or decrease size.With this implement, to reach time
* complexity O(1)
*/
if (!q) {
return 0;
}
return q->size;
}
```
:::
- 為了實現時間複雜度為 O(1) ，在 queue 的結構中加入一個變數紀錄節點的個數，而個數的增加或減少則是在新增函示或是移除函示中進行變動。
- 注意的是 queue 為空時，個數為零。
#### q_reverse
:::spoiler code
```cpp
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(queue_t *q)
{
list_ele_t *prev = NULL, *current, *next, *swap;
if (!q) {
return;
}
for (current = q->head; current != NULL;) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
swap = q->head;
q->head = q->tail;
q->tail = swap;
}
```
:::
**示意圖**
用三個指標個別指向三個個別節點
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> prev"];
struct2 [label="<f0> current"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="<f0> next"];
struct6 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
struct3:f1 -> struct4:f0;
struct5:f1 -> struct6;
struct4:f1 -> struct6:f0;
}
```
把個別指向的節點中的 next 指向反向， current 指向 prev ， next 指向 current
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<f0> prev"];
struct2 [label="<f0> current"];
struct3 [label="{<f0> value|<f1> next\n}"];
struct4 [label="{<f0> value|<f1> next\n}"];
struct5 [label="<f0> next"];
struct6 [label="{<f0> value|<f1> next\n}"];
struct1:f1 -> struct3;
struct2:f1 -> struct4;
struct4:f1 -> struct3:f0;
struct5:f1 -> struct6;
struct6:f1 -> struct4:f0;
}
```
#### q_sort
:::spoiler code
```cpp
/* insert node at list tail and change head and tail pointer*/
void list_insert_tail(list_ele_t **head, list_ele_t **tail, list_ele_t *node)
{
if (*tail == NULL) {
*tail = node;
*head = node;
} else {
(*tail)->next = node;
(*tail) = node;
}
}
list_ele_t *merge(list_ele_t *first, list_ele_t *second)
{
list_ele_t *result_head = NULL, *result_tail = NULL;
while (first && second) {
// compare and put the smaller one in result
if (strcmp(first->value, second->value) <= 0) {
list_insert_tail(&result_head, &result_tail, first);
first = first->next;
} else {
list_insert_tail(&result_head, &result_tail, second);
second = second->next;
}
}
// Find the list that still have data, and add it in result
if (first) {
list_insert_tail(&result_head, &result_tail, first);
}
if (second) {
list_insert_tail(&result_head, &result_tail, second);
}
return result_head;
}
list_ele_t *mergesort(list_ele_t *list)
{
if (!list->next) {
return list;
}
list_ele_t *slow = list, *fast = list->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
list_ele_t *tmp = slow->next;
slow->next = NULL;
return merge(mergesort(list), mergesort(tmp));
}
/*
* 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.
*/
void q_sort(queue_t *q)
{
if (!q || !q->head || !q->head->next) {
return;
}
list_ele_t *i;
q->head = mergesort(q->head);
// update tail's information
for (i = q->head; i->next != NULL; i = i->next)
;
q->tail = i;
}
```
:::
- 第一次實作時使用 Quick Sort ， 尚未注意到測試中有考慮到時間複雜度需要達到 O(nlgn) ， Quick Sort 最差的時間複雜度會是 O(n^2^) 。為了達成目標，我去尋找較為接近的演算法，後來選擇 Merge Sort ， 平均時間複雜度為 O(nlgn) ，在實作中遇到的問題是很容易發生 segmentation fault ，需要了解出錯的地點，很容易在這邊打轉。
- 第一次將 Merge Sort 實作出來，但是因為在加入節點的設計使用到重頭開始移動到尾巴再將其加入，這樣耗費許多時間，雖然結果是正確的。後來，我新增一個變數紀錄尾巴，如同上述 q_insert_tail 的做法，減少許多時間。
## 修正 qtest
使用 Adress Sanitizer 分析 qtest 執行 help 指令發生的錯誤
```
==234967==ERROR: AddressSanitizer: global-buffer-overflow on address 0x557eaae33400 at pc 0x557eaae1c90f bp 0x7ffcc876bad0 sp 0x7ffcc876bac0
READ of size 4 at 0x557eaae33400 thread T0
#0 0x557eaae1c90e in do_help_cmd /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:307
#1 0x557eaae1ca22 in interpret_cmda /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:221
#2 0x557eaae1d207 in interpret_cmd /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:244
#3 0x557eaae1e951 in run_console /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:660
#4 0x557eaae1b531 in main /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/qtest.c:788
#5 0x7f19f18b10b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x557eaae18b8d in _start (/home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/qtest+0x8b8d)
0x557eaae33401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x557eaae33400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/yellowhank/Desktop/linux_kernel/hw0/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ab0555be630: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab0555be640: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab0555be650: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9
0x0ab0555be660: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9
0x0ab0555be670: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ab0555be680:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ab0555be690: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab0555be6a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab0555be6b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab0555be6c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab0555be6d0: 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
==234967==ABORTING
```
這裡發現在存取 echo 變數時，會發生 global-buffer-overflow 。查詢 C99 規格書發現 bool 的空間是足夠放 0 和 1 。
- C99 [6.2.5] **Types**
> An object declared as type _Bool is large enough to store the values 0 and 1.
下列程式碼使用 plist->valp 整數指標去指向 echo 空間，會導致指標直接存取 4bytes 的空間，但是實際上 echo 的空間不足 4bytes ，會導致 global-buffer-overflow
```cpp
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
```
也實測 bool 和 int 的空間大小，得到 bool 1bytes, int 4 bytes
```cpp
printf("%ld %ld\n",sizeof(bool), sizeof(int))
// 1 4
```
### 嘗試解決方式
- 可以將 echo 變數的宣告型態提升至 int ，但是接下來 simulation 會遇到相同的問題， simulation 是外部的變數，不一定能夠更動型態。
- 把 plist->valp 轉型成 bool* ，但是需注意到原本是 int* ，這是非常危險的方式，有機會導致資訊量減少，得到錯誤的結果，這個方式需要評估原本的 int 有沒有超過 1bytes 的空間，在這裡因為 option length 使用數字 1024 ，所以不適用。
### 解決方式
- 在結構 PELE 中加入一個變數紀錄是布林值還是整數值
```cpp
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
bool checkboolint;
};
```
- 在加入參數時，設定此值是布林值還是整數值
```cpp
void add_param(char *name,
int *valp,
char *doccumentation,
setter_function setter);
setter_function setter,
bool setbool);
```
- 在 report 的地方分為布林值解決方式或是整數值解決方式
```cpp
if (plist->checkboolint)
report(1, "\t%s\t%d\t%s", plist->name, *(bool *) plist->valp,
plist->documentation);
else
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
```
## 使用 valgrind 排除 queue 實作時記憶體錯誤
使用 make valgrind 針對記憶體進行除錯
- 錯誤結果 (擷取第一個測試錯誤)
```
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==288083== Invalid read of size 8
==288083== at 0x4842C30: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8ff8 is 8 bytes before a block of size 2,049 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10B3B4: do_remove_head (qtest.c:334)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842C3B: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8ff0 is 16 bytes before a block of size 2,049 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10B3B4: do_remove_head (qtest.c:334)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842C1C: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8fe8 is 24 bytes before a block of size 2,049 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10B3B4: do_remove_head (qtest.c:334)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842C28: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8fe0 is 32 bytes before a block of size 2,064 in arena "client"
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842A8F: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8c50 is 3 bytes after a block of size 45 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10DEDF: test_malloc (harness.c:138)
==288083== by 0x10E399: q_insert_head (queue.c:64)
==288083== by 0x10BC57: do_insert_head (qtest.c:216)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842A97: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8c58 is 11 bytes after a block of size 45 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10DEDF: test_malloc (harness.c:138)
==288083== by 0x10E399: q_insert_head (queue.c:64)
==288083== by 0x10BC57: do_insert_head (qtest.c:216)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842A7C: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8c60 is 19 bytes after a block of size 45 alloc'd
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10DEDF: test_malloc (harness.c:138)
==288083== by 0x10E399: q_insert_head (queue.c:64)
==288083== by 0x10BC57: do_insert_head (qtest.c:216)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
==288083== Invalid read of size 8
==288083== at 0x4842A87: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba8c68 is 24 bytes after a block of size 48 in arena "client"
==288083==
==288083== Invalid read of size 1
==288083== at 0x4842B60: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10E4DF: memcpy (string_fortified.h:34)
==288083== by 0x10E4DF: q_remove_head (queue.c:144)
==288083== by 0x10B57A: do_remove_head (qtest.c:368)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Address 0x4ba9040 is 64 bytes inside a block of size 2,049 free'd
==288083== at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10B68D: do_remove_head (qtest.c:413)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083== Block was alloc'd at
==288083== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==288083== by 0x10B3B4: do_remove_head (qtest.c:334)
==288083== by 0x10CEA1: interpret_cmda (console.c:224)
==288083== by 0x10D338: interpret_cmd (console.c:247)
==288083== by 0x10DBA0: cmd_select (console.c:601)
==288083== by 0x10DE6D: run_console (console.c:674)
==288083== by 0x10C2D1: main (qtest.c:789)
==288083==
--- trace-01-ops 0/6
```
- 問題分析
- 發現在 q_remove_head 中的 memmove 有發生 invalid read 的情況
### 嘗試解決方式
- 閱讀資料針對 memcpy 可能發生的問題進行解決，在規格書中發現 memcpy 和 memmove 雖然都是複製字串，但是 memcpy 針對 [overlapping](https://cs50.stackexchange.com/questions/14615/memory-overlap-in-c) 的問題， memcpy 會發生未定義行為。
- C99 [7.21.2.1] **The memcpy function**
> The memcpy function copies n characters from the object pointed to by s2 into the
object pointed to by s1. If copying takes place between objects that overlap, the behavior
is undefined.
- 相對 memmove 可以針對 overlapping 進行處置，是透過複製到一個暫存的陣列來解決
- C99 [7.21.2.2] **The memmove function**
> The memmove function copies n characters from the object pointed to by s2 into the
object pointed to by s1. Copying takes place as if the n characters from the object
pointed to by s2 are first copied into a temporary array of n characters that does not
overlap the objects pointed to by s1 and s2, and then the n characters from the
temporary array are copied into the object pointed to by s1.
- memcpy 的好處是效率快速，前提是沒有 overlapping
- 所以將 memcpy 替換成 memmove
### 解決方式
- 發現到 memcpy 中的 size 都是使用 buffersize 並沒有針對
q->head->value 做適度的調整導致 sp 的大小都是 bufsize。
```cpp
memcpy(sp, q->head->value, bufsize);
sp[bufsize - 1] = '\0';
```
- 去檢查原本字串的長度，如果超過 bufsize 則另行處理
```cpp
if (bufsize < string_len + 1) {
memmove(sp, q->head->value, bufsize);
sp[bufsize - 1] = '\0';
} else {
memmove(sp, q->head->value, string_len + 1);
sp[string_len] = '\0';
}
```
### 視覺化 simulation 的記憶體使用量
- 使用 valgrind 中的 massif 進行分析
```bash
valgrind --tool=massif ./qtest -v 3 -f ./traces/trace-17-complexity.cmd
#印出結果
ms_print massif.out.258408
```
- 結果 (直接執行上述實做的 queue)
```
--------------------------------------------------------------------------------
Command: ./qtest -v 3 -f ./traces/trace-17-complexity.cmd
Massif arguments: (none)
ms_print arguments: massif.out.258408
--------------------------------------------------------------------------------
MB
1.231^ #
| #
| #
| # : :
| # : : :
| # : : :: : : @
| # : : :: : : @
| # : : :: : : @ :
| # :: : : : :: : : @ : :
| # : : : :::: : : : @ : :
| #: : : : :::: : : : @: : ::
| #: : ::: : :::: : : : @: : : ::
| #: : ::: : @::::: : : : @::: : : : ::@
| #: : ::: : @ :::: : : : @:: : : : ::@
| #: :: : ::: : : @ :::: : ::: : @:: ::: : : ::@
| #: : : ::: : : @ :::: : :: : @:: :::@: : ::@
| #::: : : :::@: : @ :::: : :: : : : @:: :::@: : ::@
| #:: : : : :::@:::@ : @ ::::::: : :: : : : @:: :::@: ::::@
| #:: : : : :::@:::@ : @ ::::: : : :: ::: ::@:: :::@: ::::@
| #:: : : : :::@:::@:: @ : @ ::::: : ::::: :::@@::@:: :: :::@::::::@
0 +----------------------------------------------------------------------->Gi
0 26.97
Number of snapshots: 65
Detailed snapshots: [1, 2 (peak), 14, 18, 21, 25, 41, 44, 54, 64]
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
0 0 0 0 0 0
1 451,350,369 304,816 250,300 54,516 0
82.12% (250,300B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->76.75% (233,955B) 0x10DEDF: test_malloc (harness.c:138)
| ->41.34% (126,000B) 0x10E375: q_insert_head (queue.c:59)
| | ->41.34% (126,000B) 0x10E9FE: measure (constant.c:65)
| | ->41.34% (126,000B) 0x10EB7E: doit (fixture.c:136)
| | ->41.34% (126,000B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->41.34% (126,000B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->41.34% (126,000B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->41.34% (126,000B) 0x10D338: interpret_cmd (console.c:247)
| | ->41.34% (126,000B) 0x10DBA0: cmd_select (console.c:601)
| | ->41.34% (126,000B) 0x10DE6D: run_console (console.c:674)
| | ->41.34% (126,000B) 0x10C2D1: main (qtest.c:789)
| |
| ->35.36% (107,787B) 0x10E399: q_insert_head (queue.c:64)
| | ->35.36% (107,787B) 0x10E9FE: measure (constant.c:65)
| | ->35.36% (107,787B) 0x10EB7E: doit (fixture.c:136)
| | ->35.36% (107,787B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->35.36% (107,787B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->35.36% (107,787B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->35.36% (107,787B) 0x10D338: interpret_cmd (console.c:247)
| | ->35.36% (107,787B) 0x10DBA0: cmd_select (console.c:601)
| | ->35.36% (107,787B) 0x10DE6D: run_console (console.c:674)
| | ->35.36% (107,787B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.06% (168B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.98% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->02.70% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->02.70% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->02.70% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.29% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.38% (7,249B) in 10 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
2 744,872,031 1,290,600 1,051,284 239,316 0
81.46% (1,051,284B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->80.19% (1,034,939B) 0x10DEDF: test_malloc (harness.c:138)
| ->43.18% (557,256B) 0x10E375: q_insert_head (queue.c:59)
| | ->43.18% (557,256B) 0x10E9FE: measure (constant.c:65)
| | ->43.18% (557,256B) 0x10EB7E: doit (fixture.c:136)
| | ->43.18% (557,256B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->43.18% (557,256B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->43.18% (557,256B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->43.18% (557,256B) 0x10D338: interpret_cmd (console.c:247)
| | ->43.18% (557,256B) 0x10DBA0: cmd_select (console.c:601)
| | ->43.18% (557,256B) 0x10DE6D: run_console (console.c:674)
| | ->43.18% (557,256B) 0x10C2D1: main (qtest.c:789)
| |
| ->37.00% (477,515B) 0x10E399: q_insert_head (queue.c:64)
| | ->37.00% (477,515B) 0x10E9FE: measure (constant.c:65)
| | ->37.00% (477,515B) 0x10EB7E: doit (fixture.c:136)
| | ->37.00% (477,515B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->37.00% (477,515B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->37.00% (477,515B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->37.00% (477,515B) 0x10D338: interpret_cmd (console.c:247)
| | ->37.00% (477,515B) 0x10DBA0: cmd_select (console.c:601)
| | ->37.00% (477,515B) 0x10DE6D: run_console (console.c:674)
| | ->37.00% (477,515B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.01% (168B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.27% (16,345B) in 11 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
3 1,196,716,406 705,968 575,645 130,323 0
4 1,525,314,876 273,712 224,842 48,870 0
5 2,195,497,317 49,640 43,108 6,532 0
6 2,590,737,257 28,976 26,331 2,645 0
7 3,086,439,722 445,488 364,123 81,365 0
8 3,814,260,269 201,520 166,510 35,010 0
9 4,121,127,632 34,864 31,125 3,739 0
10 4,581,428,795 787,120 641,617 145,503 0
11 5,246,308,143 629,680 514,129 115,551 0
12 5,757,754,359 600,040 490,065 109,975 0
13 6,249,528,173 1,058,480 861,461 197,019 0
14 6,579,996,777 274,864 226,034 48,830 0
82.23% (226,034B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->76.29% (209,689B) 0x10DEDF: test_malloc (harness.c:138)
| ->41.09% (112,952B) 0x10E375: q_insert_head (queue.c:59)
| | ->41.09% (112,952B) 0x10E9FE: measure (constant.c:65)
| | ->41.09% (112,952B) 0x10EB7E: doit (fixture.c:136)
| | ->41.09% (112,952B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->41.09% (112,952B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->41.09% (112,952B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->41.09% (112,952B) 0x10D338: interpret_cmd (console.c:247)
| | ->41.09% (112,952B) 0x10DBA0: cmd_select (console.c:601)
| | ->41.09% (112,952B) 0x10DE6D: run_console (console.c:674)
| | ->41.09% (112,952B) 0x10C2D1: main (qtest.c:789)
| |
| ->35.17% (96,673B) 0x10E399: q_insert_head (queue.c:64)
| | ->35.17% (96,673B) 0x10E9FE: measure (constant.c:65)
| | ->35.17% (96,673B) 0x10EB7E: doit (fixture.c:136)
| | ->35.17% (96,673B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->35.17% (96,673B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->35.17% (96,673B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->35.17% (96,673B) 0x10D338: interpret_cmd (console.c:247)
| | ->35.17% (96,673B) 0x10DBA0: cmd_select (console.c:601)
| | ->35.17% (96,673B) 0x10DE6D: run_console (console.c:674)
| | ->35.17% (96,673B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.02% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->03.31% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->02.99% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->02.99% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->02.99% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.32% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.64% (7,249B) in 10 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
15 7,075,699,585 394,544 322,629 71,915 0
16 7,488,785,369 200,112 164,754 35,358 0
17 7,819,253,909 837,352 682,465 154,887 0
18 8,232,339,793 211,304 174,359 36,945 0
82.52% (174,359B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->74.78% (158,014B) 0x10DEDF: test_malloc (harness.c:138)
| ->40.28% (85,120B) 0x10E375: q_insert_head (queue.c:59)
| | ->40.28% (85,120B) 0x10E9FE: measure (constant.c:65)
| | ->40.28% (85,120B) 0x10EB7E: doit (fixture.c:136)
| | ->40.28% (85,120B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->40.28% (85,120B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->40.28% (85,120B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->40.28% (85,120B) 0x10D338: interpret_cmd (console.c:247)
| | ->40.28% (85,120B) 0x10DBA0: cmd_select (console.c:601)
| | ->40.28% (85,120B) 0x10DE6D: run_console (console.c:674)
| | ->40.28% (85,120B) 0x10C2D1: main (qtest.c:789)
| |
| ->34.47% (72,830B) 0x10E399: q_insert_head (queue.c:64)
| | ->34.47% (72,830B) 0x10E9FE: measure (constant.c:65)
| | ->34.47% (72,830B) 0x10EB7E: doit (fixture.c:136)
| | ->34.47% (72,830B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->34.47% (72,830B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->34.47% (72,830B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->34.47% (72,830B) 0x10D338: interpret_cmd (console.c:247)
| | ->34.47% (72,830B) 0x10DBA0: cmd_select (console.c:601)
| | ->34.47% (72,830B) 0x10DE6D: run_console (console.c:674)
| | ->34.47% (72,830B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.03% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->04.30% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->03.89% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->03.89% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->03.89% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.42% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.29% (4,849B) in 9 places, all below massif's threshold (1.00%)
|
->01.14% (2,400B) 0x10EB30: doit (fixture.c:127)
->01.14% (2,400B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
->01.14% (2,400B) 0x10B7F2: do_insert_tail (qtest.c:263)
->01.14% (2,400B) 0x10CEA1: interpret_cmda (console.c:224)
->01.14% (2,400B) 0x10D338: interpret_cmd (console.c:247)
->01.14% (2,400B) 0x10DBA0: cmd_select (console.c:601)
->01.14% (2,400B) 0x10DE6D: run_console (console.c:674)
->01.14% (2,400B) 0x10C2D1: main (qtest.c:789)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
19 8,810,659,780 65,512 56,001 9,511 0
20 9,471,596,719 48,688 42,333 6,355 0
21 9,884,682,472 91,880 77,400 14,480 0
84.24% (77,400B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->66.45% (61,055B) 0x10DEDF: test_malloc (harness.c:138)
| ->35.72% (32,816B) 0x10E375: q_insert_head (queue.c:59)
| | ->35.72% (32,816B) 0x10E9FE: measure (constant.c:65)
| | ->35.72% (32,816B) 0x10EB7E: doit (fixture.c:136)
| | ->35.72% (32,816B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->35.72% (32,816B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->35.72% (32,816B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->35.72% (32,816B) 0x10D338: interpret_cmd (console.c:247)
| | ->35.72% (32,816B) 0x10DBA0: cmd_select (console.c:601)
| | ->35.72% (32,816B) 0x10DE6D: run_console (console.c:674)
| | ->35.72% (32,816B) 0x10C2D1: main (qtest.c:789)
| |
| ->30.55% (28,071B) 0x10E399: q_insert_head (queue.c:64)
| | ->30.55% (28,071B) 0x10E9FE: measure (constant.c:65)
| | ->30.55% (28,071B) 0x10EB7E: doit (fixture.c:136)
| | ->30.55% (28,071B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->30.55% (28,071B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->30.55% (28,071B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->30.55% (28,071B) 0x10D338: interpret_cmd (console.c:247)
| | ->30.55% (28,071B) 0x10DBA0: cmd_select (console.c:601)
| | ->30.55% (28,071B) 0x10DE6D: run_console (console.c:674)
| | ->30.55% (28,071B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.18% (168B) in 1+ places, all below ms_print's threshold (01.00%)
|
->09.90% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->08.94% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->08.94% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->08.94% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.96% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.61% (2,400B) 0x10EB30: doit (fixture.c:127)
| ->02.61% (2,400B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| ->02.61% (2,400B) 0x10B7F2: do_insert_tail (qtest.c:263)
| ->02.61% (2,400B) 0x10CEA1: interpret_cmda (console.c:224)
| ->02.61% (2,400B) 0x10D338: interpret_cmd (console.c:247)
| ->02.61% (2,400B) 0x10DBA0: cmd_select (console.c:601)
| ->02.61% (2,400B) 0x10DE6D: run_console (console.c:674)
| ->02.61% (2,400B) 0x10C2D1: main (qtest.c:789)
|
->01.31% (1,208B) 0x10EAE8: doit (fixture.c:122)
| ->01.31% (1,208B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| ->01.31% (1,208B) 0x10B7F2: do_insert_tail (qtest.c:263)
| ->01.31% (1,208B) 0x10CEA1: interpret_cmda (console.c:224)
| ->01.31% (1,208B) 0x10D338: interpret_cmd (console.c:247)
| ->01.31% (1,208B) 0x10DBA0: cmd_select (console.c:601)
| ->01.31% (1,208B) 0x10DE6D: run_console (console.c:674)
| ->01.31% (1,208B) 0x10C2D1: main (qtest.c:789)
|
->01.31% (1,208B) 0x10EAF8: doit (fixture.c:123)
| ->01.31% (1,208B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| ->01.31% (1,208B) 0x10B7F2: do_insert_tail (qtest.c:263)
| ->01.31% (1,208B) 0x10CEA1: interpret_cmda (console.c:224)
| ->01.31% (1,208B) 0x10D338: interpret_cmd (console.c:247)
| ->01.31% (1,208B) 0x10DBA0: cmd_select (console.c:601)
| ->01.31% (1,208B) 0x10DE6D: run_console (console.c:674)
| ->01.31% (1,208B) 0x10C2D1: main (qtest.c:789)
|
->01.31% (1,200B) 0x10EB08: doit (fixture.c:124)
| ->01.31% (1,200B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| ->01.31% (1,200B) 0x10B7F2: do_insert_tail (qtest.c:263)
| ->01.31% (1,200B) 0x10CEA1: interpret_cmda (console.c:224)
| ->01.31% (1,200B) 0x10D338: interpret_cmd (console.c:247)
| ->01.31% (1,200B) 0x10DBA0: cmd_select (console.c:601)
| ->01.31% (1,200B) 0x10DE6D: run_console (console.c:674)
| ->01.31% (1,200B) 0x10C2D1: main (qtest.c:789)
|
->01.11% (1,024B) 0x4A2AE83: _IO_file_doallocate (filedoalloc.c:101)
| ->01.11% (1,024B) 0x4A3B04F: _IO_doallocbuf (genops.c:347)
| ->01.11% (1,024B) 0x4A3A0AF: _IO_file_overflow@@GLIBC_2.2.5 (fileops.c:745)
| | ->01.11% (1,024B) 0x4A38834: _IO_new_file_xsputn (fileops.c:1244)
| | ->01.11% (1,024B) 0x4A38834: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1197)
| | ->01.11% (1,024B) 0x4A1FAF1: __vfprintf_internal (vfprintf-internal.c:1373)
| | ->01.11% (1,024B) 0x10C8C9: vfprintf (stdio2.h:130)
| | ->01.11% (1,024B) 0x10C8C9: report_noreturn (report.c:122)
| | ->01.11% (1,024B) 0x10DB5E: readline (console.c:534)
| | ->01.11% (1,024B) 0x10DB5E: cmd_select (console.c:599)
| | ->01.11% (1,024B) 0x10DE6D: run_console (console.c:674)
| | ->01.11% (1,024B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
|
->00.23% (209B) in 1+ places, all below ms_print's threshold (01.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
22 10,417,751,127 23,984 22,279 1,705 0
23 11,017,665,208 222,640 183,631 39,009 0
24 11,497,596,509 47,792 41,589 6,203 0
25 12,097,510,777 518,248 423,278 94,970 0
81.67% (423,278B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->78.52% (406,933B) 0x10DEDF: test_malloc (harness.c:138)
| ->42.34% (219,408B) 0x10E375: q_insert_head (queue.c:59)
| | ->42.34% (219,408B) 0x10E9FE: measure (constant.c:65)
| | ->42.34% (219,408B) 0x10EB7E: doit (fixture.c:136)
| | ->42.34% (219,408B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->42.34% (219,408B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->42.34% (219,408B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->42.34% (219,408B) 0x10D338: interpret_cmd (console.c:247)
| | ->42.34% (219,408B) 0x10DBA0: cmd_select (console.c:601)
| | ->42.34% (219,408B) 0x10DE6D: run_console (console.c:674)
| | ->42.34% (219,408B) 0x10C2D1: main (qtest.c:789)
| |
| ->36.17% (187,461B) 0x10E399: q_insert_head (queue.c:64)
| | ->36.17% (187,461B) 0x10E9FE: measure (constant.c:65)
| | ->36.17% (187,461B) 0x10EB7E: doit (fixture.c:136)
| | ->36.17% (187,461B) 0x10EDD6: is_insert_tail_const (fixture.c:168)
| | ->36.17% (187,461B) 0x10B7F2: do_insert_tail (qtest.c:263)
| | ->36.17% (187,461B) 0x10CEA1: interpret_cmda (console.c:224)
| | ->36.17% (187,461B) 0x10D338: interpret_cmd (console.c:247)
| | ->36.17% (187,461B) 0x10DBA0: cmd_select (console.c:601)
| | ->36.17% (187,461B) 0x10DE6D: run_console (console.c:674)
| | ->36.17% (187,461B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.76% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->01.59% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->01.59% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->01.59% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.17% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.40% (7,249B) in 10 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
26 12,457,459,255 580,072 473,733 106,339 0
27 13,057,373,388 970,088 790,451 179,637 0
28 13,417,321,965 764,976 623,253 141,723 0
29 14,017,235,984 1,125,296 916,184 209,112 0
30 14,377,184,366 993,072 809,010 184,062 0
31 14,857,115,714 215,272 177,607 37,665 0
32 15,577,012,612 1,144,552 931,820 212,732 0
33 16,056,943,800 23,656 22,024 1,632 0
34 16,627,378,405 257,840 212,026 45,814 0
35 17,288,316,182 93,104 78,407 14,697 0
36 17,949,253,519 1,027,888 837,327 190,561 0
37 18,279,722,221 388,656 318,568 70,088 0
38 18,940,659,559 261,864 215,480 46,384 0
39 19,601,597,277 134,576 112,087 22,489 0
40 20,097,300,581 725,864 592,461 133,403 0
41 20,427,769,452 125,104 104,329 20,775 0
83.39% (104,329B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->70.33% (87,982B) 0x10DEDF: test_malloc (harness.c:138)
| ->37.91% (47,432B) 0x10E375: q_insert_head (queue.c:59)
| | ->37.91% (47,432B) 0x10EAA3: measure (constant.c:76)
| | | ->37.91% (47,432B) 0x10EB7E: doit (fixture.c:136)
| | | ->37.91% (47,432B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->37.91% (47,432B) 0x10AE1A: do_size (qtest.c:482)
| | | ->37.91% (47,432B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->37.91% (47,432B) 0x10D338: interpret_cmd (console.c:247)
| | | ->37.91% (47,432B) 0x10DBA0: cmd_select (console.c:601)
| | | ->37.91% (47,432B) 0x10DE6D: run_console (console.c:674)
| | | ->37.91% (47,432B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->32.36% (40,486B) 0x10E399: q_insert_head (queue.c:64)
| | ->32.36% (40,486B) 0x10EAA3: measure (constant.c:76)
| | | ->32.36% (40,486B) 0x10EB7E: doit (fixture.c:136)
| | | ->32.36% (40,486B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->32.36% (40,486B) 0x10AE1A: do_size (qtest.c:482)
| | | ->32.36% (40,486B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->32.36% (40,486B) 0x10D338: interpret_cmd (console.c:247)
| | | ->32.36% (40,486B) 0x10DBA0: cmd_select (console.c:601)
| | | ->32.36% (40,486B) 0x10DE6D: run_console (console.c:674)
| | | ->32.36% (40,486B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.05% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->07.27% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->06.57% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->06.57% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->06.57% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.70% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->03.88% (4,851B) in 10 places, all below massif's threshold (1.00%)
|
->01.92% (2,400B) 0x10EB30: doit (fixture.c:127)
->01.92% (2,400B) 0x10EEB7: is_size_const (fixture.c:188)
| ->01.92% (2,400B) 0x10AE1A: do_size (qtest.c:482)
| ->01.92% (2,400B) 0x10CEA1: interpret_cmda (console.c:224)
| ->01.92% (2,400B) 0x10D338: interpret_cmd (console.c:247)
| ->01.92% (2,400B) 0x10DBA0: cmd_select (console.c:601)
| ->01.92% (2,400B) 0x10DE6D: run_console (console.c:674)
| ->01.92% (2,400B) 0x10C2D1: main (qtest.c:789)
|
->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
42 21,088,706,911 311,472 255,648 55,824 0
43 21,584,410,151 179,760 148,603 31,157 0
44 22,080,113,397 979,816 797,457 182,359 0
81.39% (797,457B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->79.72% (781,110B) 0x10DEDF: test_malloc (harness.c:138)
| ->43.00% (421,344B) 0x10E375: q_insert_head (queue.c:59)
| | ->43.00% (421,344B) 0x10EAA3: measure (constant.c:76)
| | | ->43.00% (421,344B) 0x10EB7E: doit (fixture.c:136)
| | | ->43.00% (421,344B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->43.00% (421,344B) 0x10AE1A: do_size (qtest.c:482)
| | | ->43.00% (421,344B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->43.00% (421,344B) 0x10D338: interpret_cmd (console.c:247)
| | | ->43.00% (421,344B) 0x10DBA0: cmd_select (console.c:601)
| | | ->43.00% (421,344B) 0x10DE6D: run_console (console.c:674)
| | | ->43.00% (421,344B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->36.71% (359,702B) 0x10E399: q_insert_head (queue.c:64)
| | ->36.71% (359,702B) 0x10EAA3: measure (constant.c:76)
| | | ->36.71% (359,702B) 0x10EB7E: doit (fixture.c:136)
| | | ->36.71% (359,702B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->36.71% (359,702B) 0x10AE1A: do_size (qtest.c:482)
| | | ->36.71% (359,702B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->36.71% (359,702B) 0x10D338: interpret_cmd (console.c:247)
| | | ->36.71% (359,702B) 0x10DBA0: cmd_select (console.c:601)
| | | ->36.71% (359,702B) 0x10DE6D: run_console (console.c:674)
| | | ->36.71% (359,702B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.67% (16,347B) in 12 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
45 22,410,582,233 691,504 564,228 127,276 0
46 22,906,285,509 575,408 470,207 105,201 0
47 23,567,223,065 102,120 85,737 16,383 0
48 24,228,160,705 47,848 41,635 6,213 0
49 24,558,629,618 413,360 338,365 74,995 0
50 24,852,151,295 309,352 253,855 55,497 0
51 25,145,673,018 803,944 655,724 148,220 0
52 25,439,194,714 441,576 361,213 80,363 0
53 25,732,716,420 338,920 277,857 61,063 0
54 26,026,238,269 375,984 308,165 67,819 0
81.96% (308,165B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->77.61% (291,818B) 0x10DEDF: test_malloc (harness.c:138)
| ->41.81% (157,192B) 0x10E375: q_insert_head (queue.c:59)
| | ->41.81% (157,192B) 0x10EAA3: measure (constant.c:76)
| | | ->41.81% (157,192B) 0x10EB7E: doit (fixture.c:136)
| | | ->41.81% (157,192B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->41.81% (157,192B) 0x10AE1A: do_size (qtest.c:482)
| | | ->41.81% (157,192B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->41.81% (157,192B) 0x10D338: interpret_cmd (console.c:247)
| | | ->41.81% (157,192B) 0x10DBA0: cmd_select (console.c:601)
| | | ->41.81% (157,192B) 0x10DE6D: run_console (console.c:674)
| | | ->41.81% (157,192B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->35.79% (134,562B) 0x10E399: q_insert_head (queue.c:64)
| | ->35.79% (134,562B) 0x10EAA3: measure (constant.c:76)
| | | ->35.79% (134,562B) 0x10EB7E: doit (fixture.c:136)
| | | ->35.79% (134,562B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->35.79% (134,562B) 0x10AE1A: do_size (qtest.c:482)
| | | ->35.79% (134,562B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->35.79% (134,562B) 0x10D338: interpret_cmd (console.c:247)
| | | ->35.79% (134,562B) 0x10DBA0: cmd_select (console.c:601)
| | | ->35.79% (134,562B) 0x10DE6D: run_console (console.c:674)
| | | ->35.79% (134,562B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.02% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->02.42% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->02.19% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->02.19% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->02.19% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.23% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.93% (7,251B) in 11 places, all below massif's threshold (1.00%)
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
55 26,319,760,052 627,304 512,013 115,291 0
56 26,613,281,750 87,728 74,028 13,700 0
57 26,906,803,465 106,856 89,523 17,333 0
58 27,200,325,223 553,392 452,071 101,321 0
59 27,493,846,934 201,704 166,547 35,157 0
60 27,787,368,701 697,960 569,144 128,816 0
61 28,080,890,458 595,944 486,374 109,570 0
62 28,374,412,178 895,280 729,489 165,791 0
63 28,667,933,895 219,368 180,804 38,564 0
64 28,961,455,583 521,904 426,399 95,505 0
81.70% (426,399B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->78.57% (410,052B) 0x10DEDF: test_malloc (harness.c:138)
| ->42.35% (221,032B) 0x10E375: q_insert_head (queue.c:59)
| | ->42.35% (221,032B) 0x10EAA3: measure (constant.c:76)
| | | ->42.35% (221,032B) 0x10EB7E: doit (fixture.c:136)
| | | ->42.35% (221,032B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->42.35% (221,032B) 0x10AE1A: do_size (qtest.c:482)
| | | ->42.35% (221,032B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->42.35% (221,032B) 0x10D338: interpret_cmd (console.c:247)
| | | ->42.35% (221,032B) 0x10DBA0: cmd_select (console.c:601)
| | | ->42.35% (221,032B) 0x10DE6D: run_console (console.c:674)
| | | ->42.35% (221,032B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->36.21% (188,956B) 0x10E399: q_insert_head (queue.c:64)
| | ->36.21% (188,956B) 0x10EAA3: measure (constant.c:76)
| | | ->36.21% (188,956B) 0x10EB7E: doit (fixture.c:136)
| | | ->36.21% (188,956B) 0x10EEB7: is_size_const (fixture.c:188)
| | | ->36.21% (188,956B) 0x10AE1A: do_size (qtest.c:482)
| | | ->36.21% (188,956B) 0x10CEA1: interpret_cmda (console.c:224)
| | | ->36.21% (188,956B) 0x10D338: interpret_cmd (console.c:247)
| | | ->36.21% (188,956B) 0x10DBA0: cmd_select (console.c:601)
| | | ->36.21% (188,956B) 0x10DE6D: run_console (console.c:674)
| | | ->36.21% (188,956B) 0x10C2D1: main (qtest.c:789)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.01% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.74% (9,096B) 0x10C946: malloc_or_fail (report.c:189)
| ->01.57% (8,216B) 0x10CFF9: push_file (console.c:457)
| | ->01.57% (8,216B) 0x10DDDE: run_console (console.c:659)
| | ->01.57% (8,216B) 0x10C2D1: main (qtest.c:789)
| |
| ->00.17% (880B) in 1+ places, all below ms_print's threshold (01.00%)
|
->01.39% (7,251B) in 11 places, all below massif's threshold (1.00%)
```
## web server 實作
- web-server 引用自 [tiny-web_server](https://github.com/7890/tiny-web-server)
- 修正裡面使用 sprintf 的實作，改用 snprintf ，對於長度過長不會發生溢位。
- 修正 local variable 的 scope ，不需要宣告在較大的 scope 中。
- 新增 web 指令在 qtest 中，可以開啟 web server
```cpp
add_cmd("web", do_open_web, " | run a webserver");
```
- 新增 closeweb 指令在 qtest 中，可以關閉 web-server
```cpp
add_cmd("closeweb", do_close_web, " | close webserver");
```
- 若沒手動關閉 web server ，程式也會在 quit 後，自動關閉 web server
- 目前為了讓 web server 可以在 qtest 的背景執行，使用 fork 實作，之後會改成 coroutine
Sign in with Wallet
Connect another wallet