---
# System prepended metadata

title: 2022q1 Homework1 (lab0)
tags: [linux2022]

---

# 2022q1 Homework1 (lab0)
contributed by < [`Pepitaw`](https://github.com/Pepitaw/lab0-c) >
###### tags: `linux2022`

## 實驗環境
```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-9750H CPU @ 2.60GHz
Stepping:                        10
CPU MHz:                         2600.000
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11
```

## 開發紀錄
:::info
作業要求
- [x] q_new: 建立新的「空」佇列
- [x] q_free: 釋放佇列所佔用的記憶體
- [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] q_release_element: 釋放特定節點的記憶體空間
- [x] q_size: 計算目前佇列的節點總量
- [x] q_delete_mid: 移走佇列中間的節點
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x] q_swap: 交換佇列中鄰近的節點
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] q_sort: 以遞增順序來排序鏈結串列的節點
:::

### q_new
根據 `list.h` 參考函式 `INIT_LIST_HEAD` 初始化 q ，將 q 的 `next` 與 `prev` 指向自己。

:::spoiler 實際程式碼
```clike
struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}
```
:::

- 實作流程
  1. 使用 `malloc` 分配記憶體空間給指標 q 
  2. 如果 `malloc` 分配空間失敗，會回傳 `NULL`
  3. 使用 `INIT_LIST_HEAD` 初始化指標 q



### q_free
根據 `list.h` 參考函式 `list_for_each_entry_safe` ，藉由副本遍歷各個 `entry` ，不會受到移除 `entry` 的影響

:::spoiler 實際程式碼
```clike
void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *pos, *n;
    list_for_each_entry_safe (pos, n, l, list)
        q_release_element(pos);
    free(l);
}
```
:::

- 實作流程
  1. 若 `head` 指向 NULL 就 `return`
  2. 走訪整個 `linked list` ，對每個 `entry` 呼叫 `q_release_element` 釋放其空間
  3. 釋放 `head` 的記憶體空間

### q_insert_head
根據 `list.h` 參考函式 `list_add` ，將新增的 `element_t` 加到 `head` 的 `next`

:::spoiler 實際程式碼
```clike
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;
}

```
:::

- 實作流程
  1. 若 `head` 指向 NULL 就回傳 `false`
  2. 使用 `malloc()` 分配 `element_t` 大小的記憶體空間給 e ，若分配失敗則回傳 `false`
  3. 利用 `strdup` 會用 `malloc` 分配記憶體儲存字串的特性，直接指派給 e->value
  4. 若 `strdup` 分配記憶體失敗就清除 e 與回傳 `false`
  5. 加入新 `entry` 到list

:::spoiler 過去嘗試與心路歷程
1. 不知道在 queue.h 有定義 element_t ，自行定義 node
```clike
bool q_insert_head(struct list_head *head, char *s)
{
    struct node{
        char *str;
        struct list_head list;
    };
    struct node *n = malloc(sizeof(struct node));
    strcpy(n->str, s);
    list_add(&n->list, head);
    return true;
}
```
2. 遇到以下問題 Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
發現是 e->value 未配置記憶體，利用 strdup 配置記憶體與複製 *s (規格書中提到 Memory for the new string is obtained with malloc ，有malloc仍有配置失敗的時候)
```clike
element_t *e = malloc(sizeof(element_t));
if(!e)
    return false;
strcpy(e->value, s);
list_add(&e->list, head);
return true;
```
3. 去看 list_add 加入 node 的位置
```clike
struct list_head *tmp = head->next;
list_del(tmp);
list_add(tmp, head->next->next);
```
由以下結果得知，可以直接插入指定位置的下一個 `entry`
```shell
cmd> ih ant
l = [ant dolphin dolphin dolphin gerbil bear dolphin meerkat bear bear bear cat]
cmd> reverse
l = [dolphin dolphin ant dolphin gerbil bear dolphin meerkat bear bear bear cat]
```
:::

### q_insert_tail
根據 `list.h` 參考函式 `list_add_tail` ，將新增的 `element_t` 加到 `head` 的 `prev` ，其餘同 `q_insert_head`

:::spoiler 實際程式碼
```clike
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_remove_head
根據 `list.h` 參考函式 `list_first_entry` ，找到第一個 `entry` ，也參考函式 `list_del` 將目標 `entry` remove ，成為單一節點

:::spoiler 實際程式碼
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *e = list_first_entry(head, element_t, list);
    list_del(&e->list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}
```
:::

- 實作流程
  1. 如果 `head` 指向 NULL 或只有 `head` 就回傳 `NULL`
  2. 利用 `list_first_entry` 找到第一個 `entry`
  3. 再用`list_del` 將目標 `entry` remove ，成為單一節點
  4. 若 sp 存在，複製 e->value 到 sp 並補結尾 `\0`

:::spoiler 過去嘗試與心路歷程（有問題待解）
1. 想說用 strdup 修改 sp 不但有配置記憶體，還會自動補 `\0` ，但卻報錯還不知道原因。
```clike
if(sp){
    sp = strndup(e->value, bufsize - 1);
}
```
ERROR: Failed to store removed value
:::

### q_remove_tail
根據 `list.h` 參考函式 `list_last_entry` ，找到最後一個 `entry` ，其餘與 `q_remove_head` 相同

:::spoiler 實際程式碼
```clike
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;
    element_t *e = list_last_entry(head, element_t, list);
    list_del(&e->list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}
```
:::

### q_size
根據 `list.h` 參考函式 `list_for_each()` 遍歷各個 `entry`

:::spoiler 實際程式碼
```clike
int q_size(struct list_head *head)
{
    if (!head)
        return false;
    int i = 0;
    struct list_head *lh;
    list_for_each (lh, head)
        i++;
    return i;
}
```
:::

- 實作流程
  1. 若傳入的 `head` 指向 NULL 就回傳 `false`
  2. 每經過一個 `entry` i 就加一，最後即為size

### q_delete_mid
依據「龜兔賽跑」[Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)，當 `rabbit` 跑完 list 時， `turtle` 跑到一半的特性，來尋找中間的節點
:::spoiler 實際程式碼
```clike
bool q_delete_mid(struct list_head *head)
{
    struct list_head *fast = head->next, *slow = head->next;
    for (; fast != head->prev && fast->next != head->prev;
         fast = fast->next->next, slow = slow->next)
        ;
    /*while(fast != NULL && fast->next != NULL){
        fast = fast->next->next;
    slow = slow->next;
    }*/
    slow->prev->next = slow->next;
    slow->next->prev = slow->prev;
    q_release_element(list_entry(slow, element_t, list));
    return true;
}
```
:::

- 實作流程
  1. 設置兩個 pointer ， fast 一次跑一個 `entry` ， slow 跑兩個 `entry`
  2. 兩 pointer 開始遍歷 list ，當其中一個 pointer 跑完 list 時結束
  3. 利用 q_release_element 對 slow 做 delete

:::spoiler 過去嘗試與心路歷程
1. 實做龜兔賽跑找中間節點，遇到以下問題
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
因為迴圈結束方式是判斷是否為 NULL ，但 circular linked list 是頭尾相接不會 NULL
```clike
for(struct list_head *fast = head, *slow = head; fast && fast->next; \
    fast = fast->next->next, slow = slow->next);
```
:::

### q_delete_dup

:::spoiler 實際程式碼
```clike
bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *pos, *n;
    bool used = false;
    list_for_each_entry_safe (pos, n, head, list) {
        if (pos->list.next != head &&
            !strcmp(pos->value,
                    list_entry(pos->list.next, element_t, list)->value)) {
            list_del(&pos->list);
            q_release_element(pos);
            used = true;
        } else if (used) {
            list_del(&pos->list);
            q_release_element(pos);
            used = false;
        }
    }
    return true;
}
```
:::

- 實作流程
  1. 如果 `head` 指向 NULL 就回傳 `false`
  2. 利用 `list_for_each_entry_safe` 遍歷各個 `entry` 
  3. 利用 `strcmp` 比較 pos 跟下一個 `entry` 的 value 是否相同
  4. 若 value 相同且 pos 不是結尾，就將 pos delete
  5. 用 use 去紀錄該 `entry` 是否跟以刪除 `entry` 有相同的 value

### q_swap
根據 `list.h` 參考函式 `list_move_tail` 將 `entry` 放到 `head->prev`

:::spoiler 實際程式碼
```clike
void q_swap(struct list_head *head)
{
    bool odd = q_size(head) & 0x01;
    for (int i = q_size(head) >> 1; i > 0; i--) {
        list_move_tail(head->next->next, head);
        list_move_tail(head->next, head);
    }
    if (odd)
        list_move_tail(head->next, head);
}
```
:::

- 實作流程
  1. 先將第二個的 `entry` 放到尾巴
  2. 再將第一個的 `entry` 放到尾巴
  3. 總共做"總數的一半"次
  4. 若總數為奇數，就要再做一次流程二

:::spoiler 過去嘗試與心路歷程 （有問題待解）
1. 想使用 `list.h` 函式 `list_swap` ，但發現未定義
我是在 linux kernel 版本 5.13.0 查到的函式，與我的 linux kernel 5.13.0-30-generic 相符，但還是找不到原因
```clike
void q_shuffle(struct list_head *head)
{
    srand( time(NULL) );
    for (int i = q_size(head); i > 0; i--) {
        struct list_head *tmp = head->next;
        for (int x = rand()%i; x > 0; x--){
            tmp = tmp->next;
        }
        list_swap(tmp, head->prev);
        //list_move_tail(tmp, head);
    }
}
```
```shell
queue.c: In function ‘q_shuffle’:
queue.c:347:2: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
  347 |  list_swap(tmp, head->prev);
      |  ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1
```

:::

### q_reverse

:::spoiler 實際程式碼
```clike
void q_reverse(struct list_head *head)
{
    if (!head || head->next->next == head)
        return;
    struct list_head *pos = head->prev;
    for (int i = q_size(head); i > 1; i--)
        list_move_tail(pos->prev, head);
}
```
:::

- 實作流程
  1. 若 `head` 指向 NULL 或 list 只有一個 `entry` 就回傳 NULL
  2. 從尾巴開始反向遍歷，將 `entry` 依序放到尾巴

### q_sort

:::spoiler 實際程式碼
```clike
struct list_head *mergesort(struct list_head *node)
{
    if (!node || !node->next)
        return node;
    struct list_head *fast = node, *slow = node;
    for (; fast->next && fast->next->next;
         fast = fast->next->next, slow = slow->next)
        ;
    fast = slow->next;
    slow->next = NULL;

    struct list_head *l1 = mergesort(node);
    struct list_head *l2 = mergesort(fast);

    struct list_head t_head, *tmp = &t_head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) > 0) {
            tmp->next = l2;
            l2 = l2->next;
        } else {
            tmp->next = l1;
            l1 = l1->next;
        }
        tmp = tmp->next;
    }
    if (l1)
        tmp->next = l1;
    else
        tmp->next = l2;
    return t_head.next;
}

void q_sort(struct list_head *head)
{
    if (!head || !head->next)
        return;
    head->prev->next = NULL;
    struct list_head *list = head->next;
    list = mergesort(list);
    head->next = list;

    struct list_head *i = head;
    while (i->next != NULL) {
        i->next->prev = i;
        i = i->next;
    }
    head->prev = i;
    i->next = head;
}
```
:::
- 實作流程
  1. 若 `head` 指向 NULL 或 list 沒有 `entry` 就 return
  2. 將尾巴的 next 指向 NULL，切斷 next 方向的 circular
  3. 將去除 `head` 的 list 進行 mergesort
  - 以下為 mergesort
  4. 利用「龜兔賽跑」將 list 從中間一分為二
  5. 再用 `strcmp` 比較大小，依小到大排列
  6. 將 `head` 指向 排序好的 list
  7. 最後利用 `list` 的 `next->prev` 將所有  `prev` 重新排列

## 理解 [Linux 核心中的排序實作](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)

:::spoiler merge (pointer to pointer version)
```clike
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b)
{
	struct list_head *head, **tail = &head;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			*tail = a;
			tail = &a->next;
			a = a->next;
			if (!a) {
				*tail = b;
				break;
			}
		} else {
			*tail = b;
			tail = &b->next;
			b = b->next;
			if (!b) {
				*tail = a;
				break;
			}
		}
	}
	return head;
}
```
:::

- 程式碼理解
  1. 用 pointer to pointer 指向 a 與 b 之間較小的
  2. 但沒有處理 prev 的部份

:::spoiler merge_final (pointer version)
```clike
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b)
{
	struct list_head *tail = head;
	u8 count = 0;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			tail->next = a;
			a->prev = tail;
			tail = a;
			a = a->next;
			if (!a)
				break;
		} else {
			tail->next = b;
			b->prev = tail;
			tail = b;
			b = b->next;
			if (!b) {
				b = a;
				break;
			}
		}
	}

	/* Finish linking remainder of list b on to tail */
	tail->next = b;
	do {
		/*
		 * If the merge is highly unbalanced (e.g. the input is
		 * already sorted), this loop may run many iterations.
		 * Continue callbacks to the client even though no
		 * element comparison is needed, so the client's cmp()
		 * routine can invoke cond_resched() periodically.
		 */
		if (unlikely(!++count))
			cmp(priv, b, b);
		b->prev = tail;
		tail = b;
		b = b->next;
	} while (b);

	/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;
}
```
:::
- 程式碼理解
  1. 比較 a 跟 b 的大小，用 tail 的 next 指向比較小的 entry
  2. 一路遍歷兩個 linked list 直到其中一個 linked list 結束(a 或 b 指向 NULL)
  3. 用 b 指向還未走到尾巴的 linked list (未經過的 entry)
  4. 用 tail 的 next 指向剩下的 entry
  5. 遍歷完剩下的 entry ，並用 count 紀錄剩下的 entry 數量
  6. 利用 unlikely 將 count 轉成 bool
  7. 頭尾相接成為 circular
- 程式碼差異
  1. 在每次 merge 時就處理好 prev 與 next 的 link 
     我則是只看 next ，將 linked list 用 next 排列完後，再一次將所有的 prev 處理好
  2. 計算兩個 linked list 的 merge 是否 entry 數量相近，我則沒有考慮

:::spoiler list_sort
```clike
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	struct list_head *list = head->next, *pending = NULL;
	size_t count = 0;	/* Count of pending */

	if (list == head->prev)	/* Zero or one elements */
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

	/* End of input; merge together all the pending lists. */
	list = pending;
	pending = pending->prev;
	for (;;) {
		struct list_head *next = pending->prev;

		if (!next)
			break;
		list = merge(priv, cmp, pending, list);
		pending = next;
	}
	/* The final merge, rebuilding prev links */
	merge_final(priv, cmp, head, pending, list);
}
```
:::
- 程式碼理解
  1. 用 head->next == head->prev 去判斷是否只有一個 entry 或沒有 entry
  2. 將 circular 的 next 部份斷開
- 程式碼差異

## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
:::info 
作業目標
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
:::
==更新中==
:::spoiler
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd

==2951== 5 bytes in 1 blocks are still reachable in loss record 1 of 2
==2951==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951==    by 0x4A5250E: strdup (strdup.c:42)
==2951==    by 0x1108BE: linenoiseHistoryAdd (linenoise.c:1236)
==2951==    by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951==    by 0x10C6B0: main (qtest.c:951)
==2951== 
==2951== 160 bytes in 1 blocks are still reachable in loss record 2 of 2
==2951==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2951==    by 0x11087E: linenoiseHistoryAdd (linenoise.c:1224)
==2951==    by 0x111451: linenoiseHistoryLoad (linenoise.c:1325)
==2951==    by 0x10C6B0: main (qtest.c:951)
```
```clike
linecopy = strdup(line);
```
:::

## 在 qtest 提供新的命令 shuffle
:::info
作業目標
- [x] 在 `qtest` 提供新的命令 `shuffle` ，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 解釋 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP [RIO](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 套件 的原理和考量點。可對照參考 CS:APP [第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
:::

:::spoiler 程式碼
```clike
void q_shuffle(struct list_head *head)
{
    srand(time(NULL));
    for (int i = q_size(head); i > 0; i--) {
        struct list_head *tmp = head->next, *tail = head->prev;
        for (int x = rand() % i; x > 0; x--)
            tmp = tmp->next;
        list_del(tail);
        list_add(tail, tmp->prev);
        list_move_tail(tmp, head);
    }
}
```
:::
- 實作流程
  1. 將 `linked list` 的 size 不斷減一，作為隨機變數的範圍
  2. 遍歷去找隨機變數所指定的 `entry`
  3. 用 `list_del` 將尾巴成為獨立的 `entry` ，將尾巴用 `list_add` 加到目標 `entry` 的下一個 `entry` ，再將目標 `entry` 移動到尾巴，作為交換

## 在 qtest 提供新的命令 web

## 參考資料
- HackMD 模板參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view)
- Mergesort 分割部分 參考 [`Risheng1128`](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view)
- [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0)
- [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
- [Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)
- [quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c)
