---
# System prepended metadata

title: Linux 核心設計 Homework2 (lab2)

---

# 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;
```
![](https://i.imgur.com/zQAqLhf.png)
　　　　　　**list_ele_t**
![](https://i.imgur.com/P8XGIuk.png)
　　　　　　**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;

```
![](https://i.imgur.com/gJr9zSx.png)
　　　　　　**list_ele_t**
![](https://i.imgur.com/edFQuQe.png)
　　　　**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)`
![](https://i.imgur.com/AUG6xQK.png)


### 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後面有四個節點
![](https://i.imgur.com/RMStwyN.png)

呼叫`list_cut_position(&left, q, get_middle(q));`後鍊結串列將被分為兩個鍊結串列
![](https://i.imgur.com/qkfVgD6.png)



### 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`永遠指向各自鍊結串列的第一個節點，
![](https://i.imgur.com/qvFg7gw.png)
`list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;`
用strcmp比大小後，把tmp指向value小的節點上。
![](https://i.imgur.com/CI8BlCx.png)
`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);`後會有以下結果
![](https://i.imgur.com/rwwtgno.png)
再用
`list_add_tail(tmp, head);`把tmp接到head後
執行完第一次迴圈後會有以下結果
![](https://i.imgur.com/cT3k3tI.png)
跑完while迴圈後就可以得到一個排序過得鍊結串列。
![](https://i.imgur.com/2ZXVJ68.png)
### 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);
}

```


