---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `HScallop` >
## 作業說明與要求
> [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Stepping: 10
CPU MHz: 800.218
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-11
```
## 開發過程
### q_new
* Create empty queue.
* Return NULL if could not allocate space.
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (q) {
INIT_LIST_HEAD(q);
}
return q;
}
```
一開始用 `LIST_HEAD` 宣告一個 list_head 後，用pointer指向他，但發現會有 scope 的問題，所以後來改成使用 malloc 配置記憶體。
### q_free
* Free all storage used by queue.
```c
void q_free(struct list_head *l)
{
if (!l) {
return;
}
element_t *entry = NULL, *next = NULL;
list_for_each_entry_safe (entry, next, l, list) {
free(entry->value);
free(entry);
}
free(l);
}
```
用 `list_for_each_entry_safe` 一個一個找到記憶體位址後，釋放記憶體。
### q_insert_head
* 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.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *e = malloc(sizeof(element_t));
if (!e) {
return false;
}
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add(&e->list, head);
return true;
}
```
照著註解的要求寫。查如何複製字串時，找到 `strdup` 。因為實作有使用 malloc ，使用上要手動 `free` ，避免 memory leak 。
### q_insert_tail
* 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.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *e = malloc(sizeof(element_t));
if (!e) {
return false;
}
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add_tail(&e->list, head);
return true;
}
```
與 `q_insert_head` 極其類似，只需要把後面改成 `list_add_tail` 。
### q_remove_head
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *e = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&e->list);
return e;
}
```
判斷是否為空後，使用 `list_first_entry` 找到第一個 element 的位址，照著註解的要求複製給 `*sp` ，最後 `list_del` remove list node 。
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
element_t *e = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&e->list);
return e;
}
```
基本上跟 `q_remove_head` 一樣，頭改尾。
### q_size
* Return number of elements in queue.
* Return 0 if q is NULL or empty.
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head)) {
return 0;
}
struct list_head *node;
int count = 0;
list_for_each (node, head) {
count++;
}
return count;
}
```
用 `list_for_each` 一個一個去數，看有幾個。
### q_delete_mid
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head)) {
return false;
}
struct list_head *fast, *slow;
fast = slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
參考 [leetcode discussion](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/discuss/1807699/2-pointer-method-in-C) 作法，使用兩個 pointer 用兩倍速差去跑，快的跑到底時，慢的就是中間。
### q_delete_dup
* Delete all nodes that have duplicate string, leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
```c
{
if (!head) {
return false;
}
if (list_empty(head) || list_is_singular(head)) {
return true;
}
element_t *node, *safe;
bool dup = false;
list_for_each_entry_safe (node, safe, head, list) {
if ((node->list.next != head) &&
(strcmp(node->value,
list_entry(node->list.next, element_t, list)->value) ==
0)) {
list_del(&node->list);
q_release_element(node);
dup = true;
} else if (dup) {
list_del(&node->list);
q_release_element(node);
dup = false;
}
}
return true;
}
```
一直做不出來，後來參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0) 的作法。
*改進方向：應該可以先找出所有重複的相同 element 一起拿掉。*
### q_swap
* Attempt to swap every two adjacent nodes.
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *node;
for (node = head->next; node != head && node->next != head;
node = node->next) {
struct list_head *tmp = node->next;
list_del(tmp);
list_add_tail(tmp, node);
}
}
```
先排除空、只有一個的情況，接著兩個兩個交換。
### q_reverse
* Reverse elements in queue.
* No effect if q is NULL or empty.
* This function should not allocate or free any list elements.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
```
先排除不用移動的情況後，一個一個慢慢移動。
### q_sort
* 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
#### mergeTwoLists
```c
struct list_head *mergeTwoLists(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; l1 && l2; *node = (*node)->next) {
node = (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0)
? &l1
: &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
return head;
}
```
使用 indirect pointer.
#### mergesort
```c
struct list_head *mergesort(struct list_head *head)
{
if (!head->next) {
return head;
}
struct list_head *fast = head, *slow = head, *mid;
while (true) {
if (!fast || !fast->next) {
break;
}
fast = fast->next->next;
slow = slow->next;
}
mid = slow;
slow->prev->next = NULL;
struct list_head *l1 = mergesort(head), *l2 = mergesort(mid);
return mergeTwoLists(l1, l2);
}
```
#### q_sort
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *node = head->next, *tmp;
head->prev->next = NULL;
head->next = NULL;
node = mergesort(node);
tmp = head;
tmp->next = node;
while (tmp->next) {
tmp->next->prev = tmp;
tmp = tmp->next;
}
tmp->next = head;
head->prev = tmp;
}
```
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 實作 (recursion method)。
*可以實作 iteration 部份*
## valgrind
用 MakeFile 裡面寫好的指令來測試
```shell
$ make valgrind
```
結果：
```shell
--- trace-17-complexity 0/5
--- TOTAL 95/100
make: *** [Makefile:68: valgrind] Error 1
```
回頭找 trace-17
```shell
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
ERROR: Probably not constant time
Probably constant time
ERROR: Probably not constant time
```
q_insert_head, q_remove_head 被 valgrind 認為可能不是 O(1)
>目前還沒想出原因
valgrind 沒有發現 memory leak
所有輸出皆為：
```shell
160 bytes in 1 blocks are still reachable in loss record 30 of 30
```
## 記憶體分析
valgrind tool [Massif: a heap profiler](https://valgrind.org/docs/manual/ms-manual.html)
> Massif is a heap profiler. It measures how much heap memory your program uses. This includes both the useful space, and the extra bytes allocated for book-keeping and alignment purposes. It can also measure the size of your program's stack(s), although it does not do so by default.
The topic of valgrind user manual says it's a heap profiler, but the manual itself shows it can also measure the size of stack actually.
A memory test trace is added. To observe heap, use the ih command. And use sort command to observe stack (currently implemented w/ recurrsive merge sort).
>trace-massif.cmd
```
new
ih RAND 1000
sort
free
quit
```
```shell
$ valgrind --tool=massif --stacks=yes ./qtest -f traces/trace-massif.cmd
$ massif-visualizer massif.out.<pid>
```
## signal
| signal | description | default action |
| ------- | --------------------- | -------------- |
| SIGABRT | Process abort signal. | |
| SIGFPE | | |
| SIGILL | | |
| SIGINT | | |
| SIGSEGV | | |
| SIGTERM | | |
## Why merge sort?
在 linux kernel 中， list_sort.c 為何使用 merge sort 實作，而不使用 quick sort ？
跟在教科書上用 array 的討論不同，在 list 不是連續記憶體，如果使用 merge sort 我們可以良好的運用 [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference) 的特性。
### 實驗
### 閱讀 [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
## [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
### 運作方式
以下敘述論文中提供的實作步驟
`step1 measure execution time`
用 t-test 來偵測是否在運行時是 constant time 的行為，造成可能的 leakage 。
#### TODO LIST
- [x] valgrind 測試
- [ ] valgrind 視覺化 (massif)
- [x] 開發歷程說明
- [ ] tiny-web
- [ ] 分析 console.c 研究 CS:APP RIO 套件
- [ ] 研究 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
- [ ] 解決 vscode `git push` 卡住問題
Sign in with Wallet
Connect another wallet