2019q1 Homework1 (list)

tags: `sysprog` `2019` `2019spring`

contributed by <czvkcui>

自我檢查事項:

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

inline function釋出於C99標準^[1]，而linux kernel最早釋出時間是1991年^[2]，所以一開始的linux是不支援inline function的
function call相較直接使用macro會增加額外的呼叫成本(例如:function prologue)
compiler還是會自己決定是否要接受inline，所以若是要強制展開function，使用macro較佳^[3]
macro會增加code size，但是執行速度較佳(function 需要jump至function執行的地方)

做實驗：
矩陣乘法

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

程式碼：



















































































#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN 400

typedef struct __matrix_impl Matrix;
struct __matrix_impl {
    /* operations */
    Matrix (*mul)(const Matrix, const Matrix);
    int values[LEN][LEN];
};

static Matrix mul(const Matrix a, const Matrix b)
{
    Matrix matrix = { .values = { { 0 } } };

    for (int i = 0; i < LEN; i++)
        for (int j = 0; j < LEN; j++)
            for (int k = 0; k < LEN; k++)
                matrix.values[i][j] += a.values[i][k] * b.values[k][j];

    return matrix;
}

#define macro_mul(matrix, a, b)                                                          \
    for (int i = 0; i < LEN; i++)                                                        \
        for (int j = 0; j < LEN; j++)                                                    \
            for (int k = 0; k < LEN; k++)                                                \
                matrix.values[i][j] += a.values[i][k] * b.values[k][j];

static Matrix fit_number()
{

    Matrix c = { .values = { { 0 } } };
    srand(time(NULL));
    for (int i = 0; i < LEN; ++i) {
        for (int j = 0; j < LEN; j++) {
            c.values[i][j] = rand() % 5;
        }
    }
    return c;
}

int main(int argc, char* argv[])
{
    Matrix m =
    {
        .mul = mul,
        .values = {
            {0},
        },
    };

    Matrix n =
    {
        .mul = mul,
        .values = {
            {0},
        },
    };
    m = fit_number();
    n = fit_number();

    Matrix o = {
        .mul = mul,
    };
    clock_t begin = clock();
    o = o.mul(m, n);
    clock_t end = clock();
    printf("seq implement time taken:%lf\n", (double)(end - begin) / CLOCKS_PER_SEC);
    // print_matrix(o);

    begin = clock();
    macro_mul(o, m, n);
    end = clock();
    printf("macro implement time taken:%lf\n", (double)(end - begin) / CLOCKS_PER_SEC);

    return 0;
}

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

作用：推導型別
可以有兩種使用方法：

with expression
typename
































#include <stdlib.h>
#include <stdio.h>

struct vector
{
    int x;
    int y;
} *vec;

#define pointer(T) typeof(T *)
#define array(T,N) typeof(T [N])

int main()
{
    typeof(*vec) v; // with expression
    v.x = 10;
    v.y = 20;
    typeof(char*) str = "Hello world"; // with typename
    typeof(typeof(char*)[4]) string_array; // same as char* y[4];
    string_array[0] = str;

    array(pointer(struct vector), 4) vec_array; // same as vector* vec_array[4];
    vec_array[0] = &v; // same as vector* vec_array[4];

    printf("%d\n", v.x);
    printf("%d\n", v.y);
    printf("str:%s\n", str);
    printf("str:%s\n", string_array[0]);
    printf("vec_array[0]:%d\n", vec_array[0]->x);
    return 0;
}

result:

$ ./test 
10
20
str:Hello world
str:Hello world
vec_array[0]:10

解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

extension , typeof

根據^[4]，在使用-ansi或是-stdC標準規格中gnu的自己定義的keyword可能會引發問題(inline,asm,typeof)，所以加上底線來避免不同標準的相容問題。__extension__會告知編譯器使用的功能是gcc的擴充，而不會發出警告。在編譯時可以透過-pedantic來告知gcc檢查非標準也非gnu擴充的警告。

offsetof

man page 中有

NAME
       offsetof - offset of a structure member

SYNOPSIS
       #include <stddef.h>

       size_t offsetof(type, member);

DESCRIPTION
       The macro offsetof() returns the offset of the field member from the start of the structure type.

       This macro is useful because the sizes of the fields that compose a structure can vary across implementations, and compilers may insert different numbers of pad‐
       ding bytes between fields.  Consequently, an element's offset is not necessarily given by the sum of the sizes of the previous elements.

       A compiler error will result if member is not aligned to a byte boundary (i.e., it is a bit field).

用於計算member在struct中與起始位址的差異。
offsetof也可以使用下列macro實做：

#define offsetof(type, member) ((size_t)&((type *)0)->member)

(type*)會得到該type的pointer型態，((type*)0)會將該type的起始位置得到0,((type*)0)->member則會得到member的address，但這是在type 起始地址為 0 的情況下的地址，也就是這個 member 的 offset。

Statements and Declarations in Expressions^[5]

gne允許自己定義extension，在({...})的範圍內可以使用statment來撰寫expression。最後一行的expression需要使用;結尾來作為回傳值。
example：

 #define maxint(a,b) \
       ({int _a = (a), _b = (b); _a > _b ? _a : _b; })

more gnu extension:gnu extension cheetsheet

結論^[6]

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define container_of(ptr, type, member)                                                  \
    __extension__({                                                                      \
        const __typeof__(((type*)0)->member)* __pmember = (ptr);                         \
        printf("__pmember address:%p\n", __pmember);                                     \
        (type*)((char*)__pmember - offsetof(type, member));                              \
    })

typedef struct student_info {
    int id;
    char name[32];
    int age;
} student_info;

int main()
{
    size_t off_set = 0;
    off_set = offsetof(student_info, id);
    printf("id offset: %lu\n", off_set);

    off_set = offsetof(student_info, name);
    printf("name offset: %lu\n", off_set);

    off_set = offsetof(student_info, age);
    printf("age offset: %lu\n\n", off_set);

    student_info* stu = (student_info*)malloc(sizeof(student_info));
    printf("stu->age address:%p\n", &(stu->age));

    student_info* ptr = container_of(&(stu->age), student_info, age);
    printf("\n");

    printf("stu address:%p\n", stu);
    printf("ptr address:%p\n", ptr);
    return 0;
}

result:

id offset: 0
name offset: 4
age offset: 36

stu->age address:0x5623e6885694
__pmember address:0x5623e6885694

stu address:0x5623e6885670
ptr address:0x5623e6885670

const __typeof__(((type*)0)->member)* __pmember = (ptr)：定義一個指向ptr的__pmember指標，該指標的型態是type結構的member的型態，對照offsetof，typeof(((type*)0)->member)便能到該member的型態，(type*)((char*)__pmember - offsetof(type, member));該member在object中的address和該member在struct中的offset相減，便能夠得到該object的address，我們舊能夠對整個object進行操作。

除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？

可以保持對list操作的一致
封裝運算子
將常用操作抽象化

`LIST_POISONING` 這樣的設計有何意義？

因為list刪除節點後，不會釋放list node，因此當重新使用這塊list node時可能會操作到不合法的區域。

`list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？






#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)
         
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

list_for_each_safe相較於list_for_each，多了一個safe的pointer，這個pointer的指標會指向目前list node的下個list node，這麼做的好處是若我們在expression刪除list node，list仍然可以完成迭代。java和python中的list或是hash map，在使用for each語法時也會禁止使用者刪除list 或是hash map中的element。

for_each 風格的開發方式對程式開發者的影響為何？

提示：對照其他程式語言，如 Perl 和 Python

可以使用較簡潔的方式遍歷資料結構中的element

程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？

提示: 對照看 Doxygen

Doxygen可以從程式碼的註解中直接生成說明文件，這樣修改程式碼時只要修改註解就能夠生成修改後的文件，保持程式碼和說明文件的一致。

Creating a configuration file

doxygen 在使用之前必須加入設定檔

doxygen -g <config-file>

Running doxygen

doxygen 會根據config-file 的內容選擇輸出的格式和目的地
支援的格式有HTML, RTF,

LaTeX

, XML, Unix-Man page, DocBook
預設輸出是在doxygen 的config-file的位置

doxygen <config-file>

生成list的說明文件

先用doxygen -g 產生Doxyfile
修改Doxfile的設定檔
- PROJECT_NAME
- OUTPUT_DIRECTORY
- JAVADOC_AUTOBRIEF = yes(list.h的註解格式是java doc)
- EXTRACT_ALL = YES
- INPUT = include/
- INLINE_SOURCES
- EXTRACT_STATIC
修改Makefile

doc:
    @doxygen

make doc便可以在doc目錄下得到文件
commit

`tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

unit test^[7]:

測試function的操作是否符合預期
出現bugs時，可以排除是這些function所造成

`tests/` 目錄的 unit test 可如何持續精進和改善呢？

linked list 採用環狀是基於哪些考量？

不論從那一個list node開始搜尋，必定能搜尋到所有的list node

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

什麼情境會需要需要找到第 k 大/小元素呢？又，你打算如何實作？

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

作業要求

讓qtest支援link list

新增list_sort.h到linux-list用於排序:commit
list.h中有以下function:
- enum { QUICK_SORT, MERGE_SORT, INSERT_SORT };
  - 選擇排序方法
- void list_sort(struct list_head *, int);
  - 透過int選擇排序方法
- 排序方法
  - list_insertsort
  - list_qsort
  - list_mergesort
- list sort實做
```
static void (*list_sort_table[])(struct list_head *head) = { list_qsort, list_mergesort, list_insertsort };

void list_sort(struct list_head *head, int sort)
{
    list_sort_table[sort](head);
}
```
int sort透過 enum傳入時list_sort_table就會執行指定的排序方法
加入list的支援:commit
修改Makefile引入list repository
```
LISTDIR = ../linux-list
CFLAGS = -O0 -g -Wall -Werror -I$(LISTDIR)/include -    I$(LISTDIR)/private
```
- 修改BIG_QUEUE避免queue的限制影響到list
- 新指令支援
  - do_generate_shuffle
    - 產生亂數陣列
  - do_new_list
    - 產生新的link list
  - do_list_insert_elements
    - 把亂數陣列的所有element新增到link list
  - do_list_free
    - 釋放link list
  - do_list_sort
    - link list 排序
  - do_show_list
    - 印出link list
  - do_show_array
    - 印出亂數陣列

讓qtest支援效能測試:commit
Makefile加入繪圖命令

benchmark:
    ./qtest -f traces/trace-list.cmd
plot:
    gnuplot plot.gp

flurt(flush out result)將結果輸出到指定的txt file














bool do_output_result(int argc, char *argv[])
{
    if (argc < 1) {
        report(1, "%s need output file name", argv[0]);
        return false;
    }

    FILE *file = fopen(argv[1], "a");
    init_files(stdout, file);
    bool ok = interpret_cmda(argc - 2, argv + 2);
    init_files(stdout, stdin);
    fclose(file);
    return ok;
}

benchmark.txt結果:

Delta time = 0.004140
Delta time = 0.006029
Delta time = 0.285116
Delta time = 0.007655
Delta time = 0.010094
Delta time = 1.526486
Delta time = 0.012552
Delta time = 0.015353
Delta time = 4.293411
Delta time = 0.020902
Delta time = 0.020826
Delta time = 11.036341
Delta time = 0.026997
Delta time = 0.025958
Delta time = 17.795828

還是需要透過手動修改成指定格式:

10000 0.004140 0.006029 0.285116
20000 0.007655 0.010094 1.526486
30000 0.012552 0.015353 4.293411
40000 0.020902 0.020826 11.036341
50000 0.026997 0.025958 17.795828

繪圖plot.gp：

reset
set term png enhanced font 'Verdana,10'
set ylabel "time (sec)"
set xlabel "size"
set xtics 10000
set title "Time Comparison (random input)"
set output "normal.png"

plot [:][-1:]'benchmark.txt' \
    using 1:2 with linespoints linewidth 2 title 'merge', \
''  using 1:3 with linespoints linewidth 2 title 'quick', \
''  using 1:4 with linespoints linewidth 2 title 'insert'

set output "qm.png"

plot 'benchmark.txt' \
    using 1:2 with linespoints linewidth 2 title 'merge', \
''  using 1:3 with linespoints linewidth 2 title 'quick', \

效能分析

排序方法	最佳	平均	最差
insert sort^[8]	$O (n)$	$O (n^{2})$	$O (n^{2})$
quick sort^[9]	$O (n l o g n)$	$O (n l o g n)$	$O (n^{2})$
merge sort^[10]	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$

比較三者在list的排序時間(random input):

比較quick sort和merge sort

from 2019社群

在 Linux 核心中，建議採用 heap sort 或 merge sort，有個重要的考量是，許多要排序的原始序列，已是幾乎排序好的 (例如個別 process 佔用 CPU 的比例，原本已排序好，只是新增新的 process 後，又需要重排序)，或是期望順序剛好相反，這對於 quick sort 都是很大的衝擊。

參考from bauuuu1021筆記：

insert sort即使在best case下(以排序陣列,sequential input)，仍然較quick sort和merge sort花費更多的時間
quick sort時間會大幅增加
merge sort影響較小

參考資料

gnuplot教學