# 2023q1 Homework1(lab0)
contributed by < `vax-r` >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
Stepping: 11
CPU MHz: 1800.000
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Not affected
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Retbleed: Mitigation; IBRS
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled v
ia prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user
pointer sanitization
Vulnerability Spectre v2: Mitigation; IBRS, IBPB conditional, RSB filling
, PBRSB-eIBRS Not affected
Vulnerability Srbds: Mitigation; Microcode
Vulnerability Tsx async abort: Not affected
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtr
r pge mca cmov pat pse36 clflush dts acpi mmx f
xsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rd
tscp lm constant_tsc art arch_perfmon pebs bts
rep_good nopl xtopology nonstop_tsc cpuid aperf
mperf pni pclmulqdq dtes64 monitor ds_cpl vmx e
st tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_
1 sse4_2 x2apic movbe popcnt tsc_deadline_timer
aes xsave avx f16c rdrand lahf_lm abm 3dnowpre
fetch cpuid_fault epb invpcid_single ssbd ibrs
ibpb stibp tpr_shadow vnmi flexpriority ept vpi
d ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi
2 erms invpcid mpx rdseed adx smap clflushopt i
ntel_pt xsaveopt xsavec xgetbv1 xsaves dtherm i
da arat pln pts hwp hwp_notify hwp_act_window h
wp_epp md_clear flush_l1d arch_capabilities
```
## 開發過程
### q_free
本來的做法是直接 `free(l)`
但在make check的時候會碰到error
發現應該要將每個element逐個釋放, 並且value和list也該分開釋放
於是我使用 `list_for_each()`此api將queue中的element逐個走訪並釋放
但後來參閱其他學員的作業發現他人使用的是`list_for_each_safe()`
我在閱讀linux kernel api時有看到數種不同api都是用來iterate over the list
但不確定每種api各自的使用時機
於是我研究了每個api和他們的使用時機
https://stackoverflow.com/questions/9207850/why-do-we-need-list-for-each-safe-in-for-deleting-nodes-in-kernel-linked-list
make之後發現不能使用list_for_each_safe() 應該使用的是list_for_each_entry_safe()
因為我們的queue當中其實每個node都是一個element_t, 在其中使用struct list_head來串起每個node, 使用list_for_each_entry_safe()才能iterate over我們定義的型別
最後的問題是本來在此函式的最後, 我使用list_del(l)來將此queue的head給釋放, 但在check的時候會遇到error告訴我還有一個block沒被釋放
將其改成free(l)
原來list_del並不會釋放該空間, 只會將該node從list當中移除
```clike
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *cur, *tmp;
list_for_each_entry_safe (cur, tmp, l, list)
q_release_element(cur);
free(l);
}
```
### q_insert_head
剛完成的程式碼如下
```clike
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
INIT_LIST_HEAD(&(new_element->list));
new_element->value = s;
list_add(&(new_element->list), head);
return true;
}
```
進行make check之後會得到以下error
```bash
ERROR: Need to allocate and copy string for new queue element
```
透過gdb檢查記憶體配置出現什麼錯誤
值得注意的是若直接使用gdb開始分析function
應該每次都會跳進一個叫做exception_setup()的function
原來在harness.c當中有定義此函式
經過分析後 在執行q_insert_head之前 是先呼叫queue_insert這個function
而command line輸入的字串則是透過`argv[1]` 來取得
若沒有為`new_element->value` 配置新的空間再把輸入的字串放入
則有可能因為`argv[1]`位置的內容被改寫而影響到結果
把程式碼改寫成以下後 結果看似正確
```clike
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_element = malloc(sizeof(element_t));
INIT_LIST_HEAD(&(new_element->list));
new_element->value = malloc(sizeof(char) * (strlen(s) + 1));
strcpy(new_element->value, s);
new_element->value = strdup(s);
list_add(&(new_element->list), head);
return true;
}
```
進行make check檢查後q_insert_head結果正確
於是我嘗試提交git commit
結果它回覆我
```bash
Dangerous function detected in /home/yi-shin-cheng/linux-internals/lab0-c/queue.c
39: strcpy(new_element->value, s);
```
同時叫我去查看 https://security.web.cern.ch/recommendations/en/codetools/c.shtml
原來`strcpy, strcmp, strcat`等functions都不會檢查buffer length所以很容易把超過destination能容納的範圍寫入destination
最好能使用`strlcpy`
但必須事先知道source的大小否則很難配置空間
每次都配置很大的記憶體空間又很浪費
改為使用memcpy就通過了
### q_remove_head
實做此部份沒有遇到太大的困難
主要是在把字串複製進入sp的部份, 因為需要保證sp當中的字串是NULL terminated
本來想使用strscpy_pad 但本次作業所使用的library不包含此API
所以使用strncpy, 但strncpy不保證destination為NULL terminated
所以我先計算出destination的長度, 並在sp的結尾塞入`\0`
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *removed_element = list_first_entry(head, element_t, list);
list_del(&removed_element->list);
int len = strlen(removed_element->value) < bufsize
? strlen(removed_element->value) + 1
: bufsize;
if (sp) {
strncpy(sp, removed_element->value, len);
*(sp + len - 1) = '\0';
}
return removed_element;
}
```
### q_delete_mid
此題為刪除queue中位於中間的結點
假設有n個element, 則刪除第$\lfloor n/2 \rfloor$個element
本來想說要用fast, slow pointer, 但想到這是一個circular linked list
若用fast, slow pointer不僅要先計算queue的size, 還得把整個queue繞一圈
想到若一個pointer往前走, 一個往後走, 則兩個pointer相撞的位置剛好會在中間
```clike
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *forward, *backward;
forward = head;
backward = head;
do {
forward = forward->next;
backward = backward->prev;
} while (forward != backward &&
(forward->next != backward && backward->prev != forward));
list_del(forward);
return true;
}
```
以上的程式碼依然存在問題, 在進行trace-02-ops.cmd裡面的測試時, 全部執行結果都正確不過最後free queue的時候會跳出error告訴你還有4個blocks沒有被free
原來問題出在我沒有正確的將整個entry給delete掉, list_del僅僅是將queue的node裡面用來串接相鄰的node的struct list_head給刪掉，整個element_t並沒有被刪除
使用list_entry來找到forward被哪個element_t給包住並將它們正確的移除並刪除
```diff
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *forward, *backward;
forward = head;
backward = head;
do {
forward = forward->next;
backward = backward->prev;
} while (forward != backward &&
(forward->next != backward && backward->prev != forward));
+ element_t *entry = list_entry(forward, element_t, list);
list_del(forward);
+ q_release_element(entry);
return true;
}
```
### q_delete_dup
此函式要求刪除在queue當中所有含有重複字串的node
leetcode的範例中對於重複字串的node會留下一個
但此作業中要求全部刪除, 因此需要額外紀錄目前走訪的node是否是之前重複過的
```clike
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
element_t *current = NULL, *tmp1 = NULL;
struct list_head *cursor;
int dup = 0;
list_for_each_entry_safe (current, tmp1, head, list) {
cursor = current->list.next;
if (cursor != head && !strcmp(current->value, list_entry(cursor, element_t, list)->value)) {
list_del(&(current->list));
q_release_element(current);
dup = 1;
}
else if (dup) {
list_del(&(current->list));
q_release_element(current);
dup = 0;
}
}
return true;
}
```
### q_swap
本來想利用linux kernel api當中的list_swap來實做, 但library中沒有此function, 所以我參考其他學長的作法, 利用list_move的方式, 換個思維方式也能達到swap的效果
值得注意的是, 當我使用list_for_each_safe來做iterate的時候，會出現無窮迴圈的現象, 使用list_for_each就不會, 這是為什麼呢？
```clike
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *cursor;
list_for_each(cursor, head) {
if ( cursor->next == head )
break;
list_move(cursor, cursor->next);
}
}
```
### q_reverse
瀏覽kernel api後沒有注意到適合實做此function的api, 於是我利用以下方法將整個queue給反轉, iterate整個list的時候保存當下節點的next, 並變更current->next和current->prev
```clike
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *current, *next;
current = head;
do {
next = current->next;
current->next = current->prev;
current->prev = next;
current = next;
} while (current != head);
}
```
### q_reverseK
解題耗時較長, 不能另外增開空間所以作法必須是in-place的
我的作法是將k個node先做成一個list, 接著將此list丟入q_reverse進行反轉後再和原本的list接起來
```clike
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
int times = q_size(head) / k;
int i, j, remain = 0;
if (times*k != q_size(head))
remain = q_size(head) - times*k;
struct list_head *cur_h, *next_h, *tmp;
next_h = head->next;
head->next = head;
head->prev = head;
for ( i=0; i<times; i++ ) {
cur_h = next_h;
for (j=0;j<k;j++)//find the next head
next_h = next_h->next;
//make a sub-list
cur_h->prev = next_h->prev;
next_h->prev->next = cur_h;
q_reverse(cur_h);
cur_h = cur_h->next;
head->prev->next = cur_h;
cur_h->prev->next = head;
tmp = head->prev;
head->prev = cur_h->prev;
cur_h->prev = tmp;
}
if (remain) {
cur_h = next_h;
for (j=0;j<remain-1;j++)
next_h = next_h->next;
cur_h->prev = next_h;
next_h->next = cur_h;
head->prev->next = cur_h;
cur_h->prev->next = head;
tmp = head->prev;
head->prev = cur_h->prev;
cur_h->prev = tmp;
}
}
```
### q_sort
我參考 ＠alanjian85 的作法並改寫成自己的風格
使用遞迴版本merge sort的作法
未來可以改進成非遞迴版本以避免stack overflow
```clike
void q_merge_two(struct list_head *list1, struct list_head *list2, bool descend)
{
//assume to be merge in descending order
if (!list1 || !list2)
return;
struct list_head temp_head;
INIT_LIST_HEAD(&temp_head);
element_t *entry1, *entry2, *entry_selected;
while (!list_empty(list1) && !list_empty(list2)) {
entry1 = list_first_entry(list1, element_t, list);
entry2 = list_first_entry(list2, element_t, list);
bool cond;
if (descend)
cond = strcmp(entry1->value, entry2->value) > 0;
else
cond = strcmp(entry1->value, entry2->value) < 0;
entry_selected = cond ? entry1 : entry2;
list_move_tail(&entry_selected->list, &temp_head);
}
list_splice_tail_init(list1, &temp_head);
list_splice_tail_init(list2, &temp_head);
list_splice(&temp_head, list1);
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *forward, *backward;
forward = head;
backward = head;
do {
forward = forward->next;
backward = backward->prev;
} while (forward != backward &&
(forward->next != backward && backward->prev != forward));
struct list_head left;
list_cut_position(&left, head, forward);
q_sort(&left, descend);
q_sort(head, descend);
q_merge_two(head, &left, descend);
}
```
### q_ascend / q_descend
本來我的想法是利用雙層迴圈順向走訪, 並將外層迴圈走到的node和內層迴圈比較, 想法很直觀, 但這樣實做出來的程式碼可讀性跟效率都較差
調整過後利用反向走訪, 同樣是雙層迴圈但外層迴圈走訪的node不是一個一個走訪, 而是只走訪比當前所在之node->value還小（還大）之節點
內層迴圈用來拜訪當前node所有左邊的節點並與node->value比較
此處若能用list_for_each_entry_reverse來改寫會更好, 但library中沒有此api
```clike
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || q_size(head) == 1)
return q_size(head);
struct list_head *rr, *r_cursor = head->prev, *safe;
element_t *pivot_entry, *tmp_entry;
while (r_cursor != head) {
pivot_entry = list_entry(r_cursor, element_t, list);
for(rr=r_cursor->prev, safe = rr->prev; rr!=head; rr=safe, safe = safe->prev) {
tmp_entry = list_entry(rr, element_t, list);
if (strcmp(pivot_entry->value, tmp_entry->value) >= 0)
break;
list_del(rr);
q_release_element(tmp_entry);
}
r_cursor = rr;
}
return q_size(head);
}
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || q_size(head) == 1)
return q_size(head);
struct list_head *rr, *r_cursor = head->prev, *safe;
element_t *pivot_entry, *tmp_entry;
while (r_cursor != head) {
pivot_entry = list_entry(r_cursor, element_t, list);
for(rr=r_cursor->prev, safe = rr->prev; rr!=head; rr=safe, safe = safe->prev) {
tmp_entry = list_entry(rr, element_t, list);
if (strcmp(pivot_entry->value, tmp_entry->value) <= 0)
break;
list_del(rr);
q_release_element(tmp_entry);
}
r_cursor = rr;
}
return q_size(head);
}
```
### q_merge
此處為參考學長們作法的實做, 未來應作為改進的項目
```clike
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
int size = q_size(first->q);
if (list_is_singular(head))
return size;
queue_contex_t *second =
list_entry(first->chain.next, queue_contex_t, chain);
queue_contex_t *end = NULL;
while (second != end) {
size += q_size(second->q);
q_merge_two(first->q, second->q, descend);
if (!end)
end = second;
list_move_tail(&second->chain, head);
second = list_entry(first->chain.next, queue_contex_t, chain);
}
return size;
}
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
int i = q_size(head) - 1;
struct list_head *node;
for (node = head->prev; node != head; node = node->prev, i--) {
struct list_head *other = head->next;
for (int j = rand() % (i + 1); j > 0; j--)
other = other->next;
if (node == other)
continue;
struct list_head *temp = other->prev;
list_move(other, node);
list_move(node, temp);
node = other;
}
}
```
## q_insert_head, q_insert_tail, q_remove_head, q_remove_tail time complexity testing
第17個測驗檔案是用來測試以上四個函式的時間複雜度是否是constant time
目前提交無法通過
還找不到原因, 每個function都各自通過測試過
Google Drive
Gist
Clipboard
Sign in with Wallet
