---
tags: linux kernel
---
# 2022q1 Homework1 (lab0)
contributed by < `zoanana990` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 900.106
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/zoanana990/lab0-c)
- [x] 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [ ] 利用 `Valgrind` 分析 `q_test`
- [x] 在 `qtest` 提供新的命令 `shuffle` ，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 `web` 伺服器功能，注意: `web` 伺服器運作過程中，`qtest` 仍可接受其他命令
- [ ] 閱讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
## 作業 1. 修改`queue.[ch]`
### `q_new` 實作
- 一開始的想法，要先初始化一個佇列(queue)，再將佇列中的 `list_head` 初始化，寫下以下程式碼：
```c
struct list_head *q_new()
{
// make an element
element_t *q = malloc(sizeof(element_t));
// if not malloc memory
if (!q){
free(q);
return NULL;
}
// Initial the list node and value
q->value = NULL;
INIT_LIST_HEAD(&q->list);
return &q->list;
}
```
然而這個程式碼無法編譯成功，顯示錯誤為 `Attempted to free unallocated block` ，這給我兩個想法：
1. `element_t` 沒有分配成功，因此不需要為了它去free
```c
struct list_head *q_new()
{
// make an element
element_t *q = malloc(sizeof(element_t));
// if not malloc memory
if (!q){
return NULL;
}
q->value = malloc(sizeof(char));
if(!q->value){
free(q);
return NULL;
}
// Initial the list node and value
q->value = NULL;
INIT_LIST_HEAD(&q->list);
return &q->list;
}
```
這邊仍然會出現錯誤，因此我改變 `Makefile` 指定測試13，看一下出現結果，目前我沒有在對上面版本的程式碼繼續調整
```shell
WARNING: Malloc returning NULL
l = NULL
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
l = []
cmd> new
Freeing old queue
ERROR: Attempted to free unallocated block.
```
2. 函式回傳值要求為 `struct list_head` ，直接做一個 `struct list_head` 回傳就好， `element_t` 可以使用 `list_entry` 呼叫。
```c
struct list_head *q_new()
{
// make an element
struct list_head *l = malloc(sizeof(struct list_head));
// if not malloc memory
if (!l)
return NULL;
// Initial the list node
INIT_LIST_HEAD(l);
return l;
}
```
這個程式碼可以繼續成功運行
### `q_free` 實作
- 這個函式突顯了 `container_of` 的重要性，之前上課的時候完全不覺的 `container_of` 可以有什麼大的作用。在寫這個函式之後，完全沒有頭緒，因此回去重看了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)這時候才理解為什麼老師上課說 `container_of` 非常重要可以幫助程式變得很簡潔
- 一開始的程式碼：
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *curr;
list_for_each (curr, l)
q_release_element(list_entry(curr, element_t, list));
free(l);
}
```
- 這裡直接報錯，原因是 `curr` 指向的佇列被刪除後， `curr` 也會被刪除，會出現 `segmentation fault` 錯誤
- 因此需要調整成先創立一個節點，等現在的節點跑到下一個之後，再把之前的節點獨立出來，在刪掉
- 最終程式碼：
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *curr = l->next;
while(curr != l){
struct list_head *prev = curr;
curr = curr->next;
list_del(prev);
q_release_element(list_entry(prev, element_t, list));
}
free(l);
}
```
圖解說明：
- 一開始:
```graphviz
digraph{
rankdir = LR
l[color=red, fontcolor=red]
curr[color=blue, fontcolor=blue]
prev[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
curr -> bear
l -> {bear, meerkat}
bear -> {dophin, l}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {l, gerbil}
}
```
- 將 `prev` 紀錄 `curr` 及 `curr` 右移，程式碼對應如下：
```c
struct list_head *prev = curr;
curr = curr->next;
```
```graphviz
digraph{
rankdir = LR
l[color=red, fontcolor=red]
curr[color=blue, fontcolor=blue]
prev[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
curr -> dophin
l -> {bear, meerkat}
prev -> bear
bear -> {dophin, l}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {l, gerbil}
}
```
- 刪除 `bear` ，先將節點獨立出來，再將記憶體釋放，程式碼對應如下
```c
list_del(prev);
q_release_element(list_entry(prev, element_t, list));
```
```graphviz
digraph{
rankdir = LR
l[color=red, fontcolor=red]
curr[color=blue, fontcolor=blue]
prev[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
curr -> dophin
l -> {dophin, meerkat}
prev -> bear
dophin -> {gerbil, l}
gerbil -> {meerkat, dophin}
meerkat -> {l, gerbil}
}
```
- 利用 `container_of` 找到 `queue` 的位址進行刪除，經過n個迴圈後剩下原本的 `head`
```graphviz
digraph{
l[color=red, fontcolor=red]
}
```
- 將 `head` 釋放
- 結束
### `q_insert` 實作
- `q_insert_head` 和 `q_insert_tail` 很像，而重複的地方我寫成 `q_insert` ，這個函式主要是開 `element_t` 的空間及 `char*` 的空間，如果 `element_t *` 的空間沒有開成功則回傳false，如果 `char *` 的空間沒有開成功則須先釋放 `element_t` 的空間，再回傳false，否則會出現 `Allocated Blocks` 的錯誤
```c
/*
* Due to the repeated code in q_insert_head and q_insert_tail
* write a functionto replace them
*/
element_t *q_insert(char *s)
{
element_t *q = malloc(sizeof(element_t));
if (!q)
return NULL;
q->value = malloc(sizeof(char) * (strlen(s) + 1));
if(!q->value){
free(q);
return NULL;
}
strncpy(q->value, s, strlen(s));
q->value[strlen(s)] = '\0';
return q;
}
```
- 圖解說明：以插入頭為例
- 一開始
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
want_to_insert[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
head -> {dophin, meerkat}
want_to_insert -> bear
dophin -> {gerbil, head}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 先分配佇列空間並檢驗是否分配成功
- 在分配字串空間並檢驗是否分配成功，==若分配失敗須釋放佇列空間==，否則會出現 `allocated blocks` 的錯誤
- 利用 `linux API` 直接插入即可
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
dophin[shape = square]
bear[shape = square, color=blue, fontcolor=blue]
gerbil[shape = square]
meerkat[shape = square]
head -> {bear, meerkat}
bear -> {dophin, head}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 如此， `q_insert_head` 和 `q_insert_tail` 就可以寫出來：
- `q_insert_head`
```c
bool q_insert_head(struct list_head *head, char *s)
{
// Boundary Condition
if (!head)
return false;
// make a new element
element_t *q = q_insert(s);
if(!q)
return NULL;
// INIT_LIST_HEAD(&q_head->list);
list_add(&q->list, head);
return true;
}
```
- `q_insert_tail`
```c
bool q_insert_tail(struct list_head *head, char *s)
{
// Boundary Condition
if (!head)
return false;
// make a new element
element_t *q = q_insert(s);
if(!q)
return s;
list_add_tail(&q->list, head);
return true;
}
```
### `q_remove_head` 實作
- `q_remove_head` 是將佇列的開頭移出鏈結串列中，因此需要利用 `container_of` 找出佇列的位址：
```c
element_t *q_head = list_first_entry(head, element_t, list);
```
- 將節點斷開後，利用 `memset`, `memcpy` 或 `strncpy`等函式將字串複製到 `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 *q_head = list_first_entry(head, element_t, list);
list_del_init(&q_head->list);
sp = realloc(sp, sizeof(char) * bufsize);
if (sp) {
strncpy(sp, q_head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return q_head;
}
```
- 然後直接報錯，因為
```c
sp = realloc(sp, sizeof(char) * bufsize);
```
會出現 `copying of string in remove_head overflowed destination buffer`
如果把上面的程式碼換成：
```c
sp = calloc(bufsize, sizeof(char));
```
則會發生`Failed to store removed value`
如果都沒有寫的話，則會通過測試，這裡是因為記憶體分配的問題，這幾天會看你所不知道的C語言找答案
- 最終程式碼：
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *q_head = list_first_entry(head, element_t, list);
list_del_init(&q_head->list);
if (sp) {
strncpy(sp, q_head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return q_head;
}
```
- 圖解說明：
- 一開始
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
want_to_delete[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square, color=blue, fontcolor=blue]
gerbil[shape = square]
meerkat[shape = square]
want_to_delete ->bear
head -> {bear, meerkat}
bear -> {dophin, head}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 與 `q_free` 相同，先將 `bear` 獨立出來後利用 `container_of` 返回佇列
```c
element_t *q_head = list_first_entry(head, element_t, list);
list_del_init(&q_head->list);
```
```graphviz
digraph{
bear[shape=square, color=blue, fontcolor=blue]
}
```
### `q_remove_tail` 實作
- 可以直接使用 `q_remove_head` 的結果
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove_head(head->prev->prev, sp, bufsize);
}
```
### `q_delete_mid` 實作
- 這個函式老師在上課的時候有做範例，於是我也在 [leetcode 2095](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/submissions/) 寫一下草稿：
```c
struct ListNode* deleteMiddle(struct ListNode* head){
if(!head) return NULL;
struct ListNode *fast=head, **slow=&head;
while(fast && fast->next){
fast=fast->next->next;
slow=&(*slow)->next;
}
(*slow) = (*slow)->next;
return head;
}
```
- 將函式移植到作業時需要做一些調整：
```c
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 *fast=head->next, *slow = head->next;
for (;fast != head && fast->next!= head; fast = fast->next->next)
slow = slow->next;
q_release_element(list_entry(slow, element_t, list));
list_del(slow);
return true;
}
```
- 於是就順利的報錯了，錯誤內容 `Segmentation fault occurred. You dereferenced a NULL or invalid pointer` 也就是對空指標進行操作
這邊感謝 <`Risheng1128`> 的協助，問題出在下面這兩行：
```c
q_release_element(list_entry(slow, element_t, list));
list_del(slow);
```
我先把整的佇列刪除了，如果再把 `list_head` 刪掉會造成重複刪除，就會報上面那個錯誤，所以應該先把節點抓出來再將佇列刪除，這樣就部會造成上面那個錯誤
```c
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
```
- 最終程式碼：
```c
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 *fast=head->next, *slow = head->next;
for (;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;
}
```
- 圖解說明
- 一開始，`slow` 和 `fast` 設置在 `head->next` 。龜兔賽跑開始，設定迴圈終止條件為 `fast != head` 及`fast->next != head`
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
fast[color=blue, fontcolor=blue]
slow[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
fast -> bear
head -> {bear, meerkat}
slow -> bear
bear -> {dophin, head}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 第一次迴圈， `slow` 前進一格、 `fast` 前進兩格
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
fast[color=blue, fontcolor=blue]
slow[color=purple, fontcolor=purple]
slow -> dophin
fast -> gerbil
head -> {bear, meerkat}
bear -> {dophin, head}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 第二次迴圈，`slow`前進一格、`fast`前進兩格，達成終止條件
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
fast[color=blue, fontcolor=blue]
slow[color=purple, fontcolor=purple]
slow -> gerbil
fast -> head
head -> {bear, meerkat}
bear -> {dophin, head}
dophin -> {gerbil, bear}
gerbil -> {meerkat, dophin}
meerkat -> {head, gerbil}
}
```
- 將 `gerbil` 刪除，如前面做法相似
### `q_delete_dup` 實作
- 與前幾題相同，先利用[leetcode82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)打草稿，這邊我是使用間接指標(indirect pointer)，屬於疊代法
- 由於 `leetcode` 屬於單向鏈結串列，這邊需要因為 `linux kernel` 調整程式碼的
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
struct list_head *prev = NULL, *curr = head->next, *next = curr->next;
while (curr != head && next != head) {
element_t *q_curr = list_entry(curr, element_t, list);
element_t *q_next = list_entry(next, element_t, list);
while (next != head && !strcmp(q_curr->value, q_next->value)) {
prev = curr;
list_del(next);
q_release_element(list_entry(next, element_t, list));
next = curr->next;
q_next = list_entry(next, element_t, list);
}
if (prev) {
list_del(prev);
q_release_element(list_entry(prev, element_t, list));
prev = NULL;
}
curr = next;
next = curr->next;
}
return true;
}
```
### `q_swap` 實作
- 先利用 [leetcode 24](https://leetcode.com/problems/swap-nodes-in-pairs/) 打草稿：
```c
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode **indirect=&head, *future=NULL, *current=head;
while((*indirect) && (*indirect)->next){
current = *indirect;
future = current->next;
current->next = future->next;
future->next = current;
*indirect = future;
indirect = &(current)->next;
}
return head;
}
```
這邊需要對幾個地方做調整，
### `q_reverse` 實作
- 在寫這題之前，我先去 [leetcode 206](https://leetcode.com/problems/reverse-linked-list/submissions/) 打草稿，草稿寫完如下：
- 大致上思路是很簡單的，用個指標一個一個前進，然後改變所只的方向即可，當然也可以使用遞迴呼叫的方式，但是作業的回傳值是 `void` 所以我使用比較直觀的方式去寫，以這題leetcode來說，遞迴法是比較好的選擇
- 遞迴法：
```c
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL || head->next == NULL){
return head;
}
struct node* next = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return next;
}
```
- 疊代法：
```c
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *prev=NULL;
while(head){
struct ListNode* next=head->next;
head->next=prev;
prev=head;
head=next;
}
return prev;
}
```
- 作業是用疊帶法去寫的，但是仍然需要做一些調整：
1. `linux_kernel` 屬於doubly-circular linked list，因此 `while` 迴圈的中止條件及每個節點的連結需要調整
2. 作業中的函式回傳值為 `void` 因此避免改動 `head`
改動完如下所示：
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *curr = head, *prev = head->prev;
while (next != head) {
struct list_head *next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
- 於是就順利的報錯了，主要的原因出在 `struct list_head *next = curr->next;` 及 `curr->prev = next;` 的關聯，如果是單向鏈結串列，這個寫法沒有問題，但是他是雙向，因此我們必須保留每個節點的存在，調整方式很簡單，只要把 `next` 在外面宣告即可
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *curr = head, *prev = head->prev, *next = NULL;
while (next != head) {
next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
### `q_sort` 實作
- 本題我採用 `merge sort` 進行，在寫這題之前，我先對 [leetcode 21](), [leetcode 148](https://leetcode.com/problems/sort-list/) 進行練習，而本函式的撰寫即是這兩題的結合。
- 合併的程式碼有參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中的案例一 [leetcode 21](https://leetcode.com/problems/merge-two-sorted-lists/) 的解說，程式碼如下：
```c
struct ListNode* merge(struct ListNode* left, struct ListNode* right){
// leetcode 21
struct ListNode *head = NULL, **ptr = &head, **node;
for(node = NULL; left && right; *node = (*node)->next){
node = left->val > right->val ? &right : &left;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct ListNode *)((uintptr_t) left | (uintptr_t) right);
struct ListNode* h = head;
return head;
}
struct ListNode* sortList(struct ListNode* head){
// leetcode 148
if(!head || !head->next) return head;
struct ListNode *fast = head->next, *slow = head;
for(;fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct ListNode *next = slow->next;
slow->next = NULL;
return merge(sortList(head), sortList(next));
}
```
- 實際程式碼如下，這邊有參考<`Risheng1128`>的建議
```c
struct list_head *merge(struct list_head *left, struct list_head *right)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; left && right; *node = (*node)->next) {
element_t *q_left = list_entry(left, element_t, list);
element_t *q_right = list_entry(right, element_t, list);
node = strcmp(q_left->value, q_right->value) < 0 ? &left : &right;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
return head;
}
struct list_head *MergeSort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head->next, *slow = head;
for (; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *next = slow->next;
slow->next = NULL;
return merge(MergeSort(head), MergeSort(next));
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = MergeSort(head->next);
struct list_head *curr, *prev = head;
for (curr = head->next; curr; curr = curr->next) {
curr->prev = prev;
prev = curr;
}
prev->next = head;
head->prev = prev;
}
```
## 作業 2. 以 `Valgrind` 分析記憶體問題
目前使用 `valgrind`進行分析時發現程式碼有記憶體洩漏的問題
```shell
==27236== 8 bytes in 1 blocks are still reachable in loss record 1 of 33
==27236== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==27236== by 0x4A5250E: strdup (strdup.c:42)
==27236== by 0x110E1D: linenoiseHistoryAdd (linenoise.c:1236)
==27236== by 0x1119B0: linenoiseHistoryLoad (linenoise.c:1325)
==27236== by 0x10CC24: main (qtest.c:1175)
```
## 作業 3. Shuffle
參考[作業說明](https://hackmd.io/@sysprog/linux2022-lab0#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)將 `shuffle` 命令 (Command) 加入，寫下以下程式碼
```c
bool do_shuffle(int argc, char *argv[]){
...
}
...
add_cmd("shuffle", do_shuffle, " | Shuffle the list");
```
已經參閱 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，並且實作出來，程式碼如下
```c
void shuffle(struct list_head *l, size_t size){
if(size < 2) return;
for(size_t i=size; i>0; i--){
size_t index = rand()%i + 1;
struct list_head *node = l;
for(int j=0; j<index; j++)
node = node->next;
list_move_tail(node, l);
}
}
```
其原理如下：隨機選取一個數字，該數字小於目前鏈結串列的尺寸。
例如：打亂下面這個鍊結串列，首先說隨機有一個索引目標假設現在是3，就會將 `gerbil` 移到最後面
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
target[color=purple, fontcolor=purple]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
squirrel[shape = square]
vulture[shape = square]
head -> {bear, vulture}
bear -> {dophin, head}
dophin -> {gerbil, bear}
target -> gerbil
gerbil -> {meerkat, dophin}
meerkat -> {squirrel, gerbil}
squirrel -> {vulture, meerkat}
vulture -> {head, squirrel}
}
```
```graphviz
digraph{
rankdir = LR
head[color=red, fontcolor=red]
dophin[shape = square]
bear[shape = square]
gerbil[shape = square]
meerkat[shape = square]
squirrel[shape = square]
vulture[shape = square]
head -> {bear, gerbil}
bear -> {dophin, head}
dophin -> {meerkat, bear}
meerkat -> {squirrel, dophin}
squirrel -> {vulture, meerkat}
vulture -> {gerbil, squirrel}
gerbil -> {head, vulture}
}
```
如此就完成置換，重複這個動作，直到所有節點都被移動過為止
### 分析 Linux 核心原始程式碼的 `list_sort.c`
有了 `shuffle` 的功能，就可以分析 `linux kernel` 裡面的 `list_sort` 了，這邊使用老師提供的[連結](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)進行調整
說明效能如下表所示：
|| 10000 | 60000 |
| -------- | -------- | -----|
| My sort | 0.004068| 0.032433 |
| linux kernel | 0.003466| 0.017465 |
| linux kernel (消除檢查機制)| 0.004291| 0.039406 |
接下來讓我們探討速度落差在哪裡：
:::danger
注意書寫規範：中英文間用一個空白字元區隔
:notes: jserv
:::
## 作業 4. 加入 `Web` 命令
這邊有參考 <`laneser`> 的筆記進行實作，由於背景知識不足，這邊也先去閱讀 `CS:APP` 第11章
[CSAPP Chapter 11 筆記](https://hackmd.io/oG-aoiK3Trm_x0jxeCJCcg)
## 作業 5. 閱讀論文並實做
### 論文閱讀
### 程式實作
## 參考資料
- 作業要求 [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0)
Sign in with Wallet
Connect another wallet