contributed by < Jings1017
>
linux2021
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="20.04.2 LTS (Focal Fossa)"
$ cat /proc/version
Linux version 5.8.0-44-generic (buildd@lgw01-amd64-054)
(gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0,
GNU ld (GNU Binutils for Ubuntu) 2.34)
#50~20.04.1-Ubuntu SMP Wed Feb 10 21:07:30 UTC 2021
為了達到作業要求 - 需在 \(O(1)\) 時間內完成,
故需要兩個指標分別指向 queue 的頭尾
另外需得知 queue size 多大,存放在 size 中
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
因為 malloc() 在取長度為0或是記憶體發生錯誤時會回傳NULL,所以可利用其回傳值來判斷是否有成功取得 queue_t 之空間
若成功取得,便將 head , tail 初始化成 NULL,而 size 初始化成 0,否則回傳 NULL
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
可利用 while 走訪整個 queue 結構,先將 value的 空間釋放,再釋放該元素的空間,最後釋放出 q 的空間,避免造成 memory leak
{
if (!q)
return;
list_ele_t *node = q->head;
while (node) {
list_ele_t *tmp = node->next;
free(node->value);
free(node);
node = tmp;
q->size--;
}
free(q);
}
首先,判斷 queue 是否存在,否則回傳 false
再配置一個新的 node 的空間,存放欲插入之 node,
並配置該 node->value 所需之空間,並將 s 複製到其中
最後再連接到 queue 上,並更新 q->size 之值
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
if (!q->tail)
q->tail = newh;
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
在配置記憶體空間的部分與 q_insert_head
雷同,
相異之處在於下方程式碼 line 10 ,須明確設定 newh->next=NULL
因為插入在尾端,須確保後面沒有接其他節點
最後則是判斷此次插入是否為該 queue 之第一個元素,是的話則須更新 q->head 的值為 newh,確保執行其他操作不會導致有 q->head==NULL
的狀況發生
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
newh->next = NULL;
newh->value = malloc(strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
if (!q->head)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
再作業要求中有提到,須對欲刪除之字串進行處理,處理方式為將此字串複製到 sp 中存放,但為了避免 bufsize 小於原字串之長度,故統一在 sp 最後一個字元放入 '\0'
{
if (!q || !q->head)
return false;
list_ele_t *node = q->head;
q->head = q->head->next;
if (sp) {
strncpy(sp, node->value, bufsize);
sp[bufsize - 1] = '\0';
}
free(node->value);
free(node);
if (!q->head)
q->tail = NULL;
q->size--;
return true;
}
根據作業要求,直接回傳 q->size 能確保此函式能在 \(O(1)\) 內完成
若 q 或 q->head 未取得記憶體位置,則回傳 0
{
if (!q || !q->head)
return 0;
return q->size;
}
可以利用 while 從頭走訪每個元素,逐一反轉接到 rev_list,走訪完即可得到反轉之queue
{
if (!q || !q->head || q->size <= 1)
return;
list_ele_t *rev_list = q->head;
list_ele_t *aux_list = q->head->next;
q->tail = rev_list;
rev_list->next = NULL;
while (aux_list) {
list_ele_t *tmp = aux_list;
aux_list = aux_list->next;
tmp->next = rev_list;
rev_list = tmp;
}
q->head = rev_list;
}
在排序的部份,因作業要求須再 \(O(nlgn)\) 內完成,
所以採用 merge sort 的方式實作,可確保在 worst case 中也是在 \(O(nlgn)\) 的範圍內完成
{
if (!q || !q->head || q->size <= 1)
return;
q->head = mergeSort(q->head);
list_ele_t *tail = q->head;
while (tail->next) {
tail = tail->next;
}
q->tail = tail;
}
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *curr, *head;
/* choose head */
if (strcmp(l1->value, l2->value) < 0) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
curr = head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1)
curr->next = l1;
if (l2)
curr->next = l2;
return head;
}
{
if (!head || !head->next)
return head;
/* divide two parts */
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSort(head);
list_ele_t *l2 = mergeSort(fast);
return merge(l1, l2);
}
$ sudo apt instal massif-visualizer
$ make valgrind
先執行以下指令,可得到ㄧ輸出檔 massif.out file
valgrind --tool=massif ./qtest -f <test-data>
再將此輸出檔,利用以下指令開啟,會得到視覺化的分析圖表
massif-visualizer <massif.out file>
正常的記憶體用量應該回到 0 KB 之使用量,
表示所有動態產生的記憶體空間皆有被歸還,
即 Total Memory Heap Consumption 最後會回到 0
若 Total Memory Heap Consumption 沒有回到 0 ,
則表示有記憶體空間未被歸還
故可由此工具容易判斷是否有 memory leak 的現象產生
$ make valgrind
$ valgrind --tool=massif ./qtest -f ./traces/trace-16-perf.cmd
$ massif-visualizer massif.out.5708
$ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd
$ massif-visualizer massif.out.5733
$ make clean
$ make SANITIZER=1
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
$ ./qtest -v 3 -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
=================================================================
==3798==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5591927ca5e0 at pc 0x5591927b2ae8 bp 0x7ffdc3ee4940 sp 0x7ffdc3ee4930
READ of size 4 at 0x5591927ca5e0 thread T0
#0 0x5591927b2ae7 in do_option_cmd /home/jingsian/linux2021/lab0-c/console.c:369
#1 0x5591927b18d0 in interpret_cmda /home/jingsian/linux2021/lab0-c/console.c:221
#2 0x5591927b20b5 in interpret_cmd /home/jingsian/linux2021/lab0-c/console.c:244
#3 0x5591927b32e1 in cmd_select /home/jingsian/linux2021/lab0-c/console.c:594
#4 0x5591927b385b in run_console /home/jingsian/linux2021/lab0-c/console.c:667
#5 0x5591927b03e5 in main /home/jingsian/linux2021/lab0-c/qtest.c:780
#6 0x7f43416d20b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x5591927adb8d in _start (/home/jingsian/linux2021/lab0-c/qtest+0x8b8d)
0x5591927ca5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x5591927ca5e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/jingsian/linux2021/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
0x0ab2b24f1460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2b24f1470: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2b24f1480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2b24f1490: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab2b24f14a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ab2b24f14b0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9
0x0ab2b24f14c0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
0x0ab2b24f14d0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab2b24f14e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab2b24f14f0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
0x0ab2b24f1500: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
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
==3798==ABORTING
SUMMARY: AddressSanitizer: global-buffer-overflow /home/jingsian/linux2021/lab0-c/console.c:369 in do_option_cmd
故可得知,須檢查 console.c ,針對 do_option_cmd 進行分析
/* line 340 in console.c */
static bool do_option_cmd(int argc, char *argv[])
{
if (argc == 1) {
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;
}
for (int i = 1; i < argc; i++) {
char *name = argv[i];
int value = 0;
bool found = false;
/* Get value from next argument */
if (i + 1 >= argc) {
report(1, "No value given for parameter %s", name);
return false;
} else if (!get_int(argv[++i], &value)) {
report(1, "Cannot parse '%s' as integer", argv[i]);
return false;
}
/* Find parameter in list */
param_ptr plist = param_list;
while (!found && plist) {
if (strcmp(plist->name, name) == 0) {
int oldval = *plist->valp; // here
*plist->valp = value;
if (plist->setter)
plist->setter(oldval);
found = true;
} else
plist = plist->next;
}
/* Didn't find parameter */
if (!found) {
report(1, "Unknown parameter '%s'", name);
return false;
}
}
return true;
}
並檢查 report function
/* line 91 in report.c */
void report(int level, char *fmt, ...)
{
if (!verbfile)
init_files(stdout, stdout);
if (level <= verblevel) {
va_list ap;
va_start(ap, fmt);
vfprintf(verbfile, fmt, ap);
fprintf(verbfile, "\n");
fflush(verbfile);
va_end(ap);
if (logfile) {
va_start(ap, fmt);
vfprintf(logfile, fmt, ap);
fprintf(logfile, "\n");
fflush(logfile);
va_end(ap);
}
}
}
主要原因是因為這邊讀取時 type 是 int (4 byte)
但在 simulation 宣告時 type 為 bool (1 byte),所以會出錯
bool simulation = false; -> 改成 -> int simulation = false;
extern bool simulation; -> 改成 -> extern int simulation;
static bool echo = 0; -> 改成 -> static int echo = 0;
$ make clean
$ make SANITIZER=1
$ ./qtest -v 3 -f traces/trace-17-complexity.cmd
cmd> # Test if q_insert_tail and q_size is constant time complexity
cmd> option simulation 1
cmd> it
Probably constant time
cmd> size
Probably constant time
cmd> option simulation 0
Freeing queue