# Linux 核心設計 Homework2 (lab2)
contributed by < r34796Kevin >
[完整程式碼](https://github.com/r34796Kevin/Linux2021lab2/tree/ver2)
## 簡介
實作Jserv老師的[Linux 核心設計 (Linux Kernel Internals)](http://wiki.csie.ncku.edu.tw/linux/schedule)作業2,並且盡量完成作業的額外要求
## 測驗一
* 解釋仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作運作原理，指出改進空間並著手實作
* 研讀 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 原始程式碼，學習 [sysprog21/linux-list](https://github.com/sysprog21/linux-list)的手法，將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 最佳化手法
* 將你在 quiz1 提出的改進實作，和 Linux 核心的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark
### 解釋運作原理
首先來看`head(queue_t)`與`node(list_ele_t)`的結構
```c=
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
```
**list_ele_t**
**queue_t**
其實在**list_ele_t**與**queue_t**中已經存在**list_head**可以指向下一個節點，故我們可以做以下的精簡，也可以形成一個雙向鍊結串列。
```c=
typedef struct __element {
char *value;
//struct __element *next;
struct list_head list;
} list_ele_t;
```
**list_ele_t**
**queue_t**
**queue_t**直接使用**list_head**作為鏈結串列的開頭。
在測試程式碼中我們使用`cities.txt` 取自 [dict/cities.txt](https://github.com/sysprog21/dict/blob/master/cities.txt)，內含世界超過 9 萬個都市的名稱，會產生93827個節點。
```c=
int main(void)
{
FILE *fp = fopen("cities.txt", "r");
if (!fp) {
perror("failed to open cities.txt");
exit(EXIT_FAILURE);
}
struct list_head *q = q_new();
char buf[256];
while (fgets(buf, 256, fp)){
//printf("buf is %s",buf);
q_insert_head(q, buf);
}
fclose(fp);
//q_show(q);
list_merge_sort(q);
//q_show(q);
assert(validate(q));
q_free(q);
return 0;
}
```
修改之前
> valgrind --tool=memcheck --track-origins=yes ./test
==5737== Memcheck, a memory error detector
==5737== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5737== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5737== Command: ./test
==5737==
==5737==
==5737== HEAP SUMMARY:
==5737== in use at exit: 0 bytes in 0 blocks
==5737== ==total heap usage: 187,659 allocs, 187,659 frees, 5,280,126 bytes allocated==
==5737==
==5737== All heap blocks were freed -- no leaks are possible
==5737==
==5737== For lists of detected and suppressed errors, rerun with: -s
==5737== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
修改之後
> ==7255== Memcheck, a memory error detector
==7255== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7255== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==7255== Command: ./lab2
==7255==
==7255==
==7255== HEAP SUMMARY:
==7255== in use at exit: 0 bytes in 0 blocks
==7255== ==total heap usage: 187,659 allocs, 187,659 frees, 4,529,486 bytes allocated==
==7255==
==7255== All heap blocks were freed -- no leaks are possible
==7255==
==7255== For lists of detected and suppressed errors, rerun with: -s
==7255== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
因為每個節點的結構都精簡了，所以我們的記憶體空間從5,280,126 bytes下降為4,529,486 bytes。
原始的程式碼請參考[測驗一](https://hackmd.io/@sysprog/linux2021-quiz2)，
因為鍊結串列的結構改變了所以以下程式碼也要改寫。
### q_new
首先來看`struct list_head *q_new()`，配置一個list_head \*q，用`INIT_LIST_HEAD(q);`把\*prev跟\*next都指向自己。
```c=
static struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q) return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### q_insert_head
`bool q_insert_head(struct list_head *q, char *s)`傳入鍊結串列的開頭\*q，配置一個節點\*newh儲存char \*s並用`list_add_tail(&newh->list, q);`把newh加到鍊結串列的==最後==。
（函式的名稱是否改為q_insert_tail較為恰當？？）
```c=
bool q_insert_head(struct list_head *q, char *s)
{
if (!q) return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *new_value = strdup(s);
if (!new_value) {
free(newh);
return false;
}
newh->value = new_value;
list_add_tail(&newh->list, q);
return true;
}
```
```c=
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
用圖來解釋`list_add_tail(struct list_head *node, struct list_head *head)`
### get_middle
`list_head *get_middle(struct list_head *list)`
傳入一個環形鏈結串列的開頭\*list，回傳在正中間的節點slow。
因為每次fast走兩步slow走一步，當fast走出鍊結串列時（下一步為節點開頭list或下兩步為節點開頭list），slow會在鍊結串列的正中間。
```c=
static struct list_head *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (fast->next == list || fast->next->next == list)
break;
fast = fast->next->next;
}
return slow;
}
```
### list_merge_sort
`list_cut_position(&left, q, get_middle(q));`把開頭到中間的節點分給left，剩下的節點分給q。
遞迴呼叫`list_merge_sort`直到鍊結串列的每個節點都被分開，再使用`list_merge(&left, q, &sorted);`將節點排序好分給sorted。
```c=
void list_merge_sort(struct list_head *q)
{
if (list_is_singular(q))
return;
struct list_head left;
struct list_head sorted;
INIT_LIST_HEAD(&left);
list_cut_position(&left, q, get_middle(q));
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left, q, &sorted);
INIT_LIST_HEAD(q);
list_splice_tail(&sorted, q);
}
```
```c=
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
用圖來解釋`list_cut_position`
假設原本q後面有四個節點
呼叫`list_cut_position(&left, q, get_middle(q));`後鍊結串列將被分為兩個鍊結串列
### list_merge
`list_merge(list_head *lhs,list_head *rhs,list_head *head)`可以將兩個鍊結串列lhs跟rhs排序後，接到新的head上
```c=
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
```
以下是實現的細節
`char *lv跟char *rv`永遠指向各自鍊結串列的第一個節點，
`list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;`
用strcmp比大小後，把tmp指向value小的節點上。
`list_del(tmp);`實際上是把指定的節點移出鍊結串列中（但該節點仍存在記憶體中）
```c=
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
所以呼叫`list_del(tmp);`後會有以下結果
再用
`list_add_tail(tmp, head);`把tmp接到head後
執行完第一次迴圈後會有以下結果
跑完while迴圈後就可以得到一個排序過得鍊結串列。
### q_free
遍歷鍊結串列中的每個節點並釋放記憶體。
```c=
static void q_free(struct list_head *q)
{
struct list_head *current = q->next;
while (current != q) {
list_ele_t *tmp = list_entry(current, list_ele_t, list);
current = current->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
Sign in with Wallet
Connect another wallet