Linux 核心設計 Homework2 (lab2)

contributed by < r34796Kevin >
完整程式碼

簡介

實作Jserv老師的Linux 核心設計 (Linux Kernel Internals)作業2,並且盡量完成作業的額外要求

測驗一

• 解釋仿效 Linux 核心 include/linux/list.h 的精簡實作運作原理，指出改進空間並著手實作
• 研讀 Linux 核心的 lib/list_sort.c 原始程式碼，學習 sysprog21/linux-list的手法，將 lib/list_sort.c 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 lib/list_sort.c 最佳化手法
• 將你在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark

解釋運作原理

首先來看head(queue_t)與node(list_ele_t)的結構

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可以指向下一個節點，故我們可以做以下的精簡，也可以形成一個雙向鍊結串列。

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，內含世界超過 9 萬個都市的名稱，會產生93827個節點。

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 © 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 © 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。

原始的程式碼請參考測驗一，
因為鍊結串列的結構改變了所以以下程式碼也要改寫。

q_new

首先來看struct list_head *q_new()，配置一個list_head *q，用INIT_LIST_HEAD(q);把*prev跟*next都指向自己。

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較為恰當？？）

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;
}

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會在鍊結串列的正中間。

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。

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);
}

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上

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);實際上是把指定的節點移出鍊結串列中（但該節點仍存在記憶體中）

/**
 * 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

遍歷鍊結串列中的每個節點並釋放記憶體。

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);
}