# 2020q1 Homework3 (quiz3)
contributed by < `OscarShiang` >
###### tags: `linux2020`

## 測試環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
ID=ubuntu

$ cat /proc/version
Linux version 5.3.0-40-generic (buildd@lcy01-amd64-024) 
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)) 

## 作業要求
- [x] 重新回答第 3 週測驗題
- [x] 解釋 XOR linked list 排序實作的原理，並指出其中可改進之處
- [x] 請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 XOR linked list 排序程式。過程中應該充分量化數據並進行視覺化處理。
- [x] 修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化，可設計頻繁的 test_malloc / test_free 呼叫交錯情境。
- [x] 解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制;
- [x] 在 Linux 核心找出運用類似的手法的程式碼並解說
* 提示: 可參見 [bfq_insert](https://elixir.bootlin.com/linux/v4.15/source/block/bfq-wf2q.c#L373) 和 [rb_link_node](https://elixir.bootlin.com/linux/v4.15/source/include/linux/rbtree.h#L105) 操作 [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 的手法

## 測驗題分析
在測驗 1 中，我們要實作的 XOR linked list 節點的結構如下

typedef struct __list list;
struct __list {
    int data;
    struct __list *addr;
};

而其中結構體內的 `addr` 指標並不是像原先在 lab0-c 中所出現的結構體一樣是採用 `next` 來實作下一個節點的指標，在這個結構中，因為使用 XOR 進行運算的緣故，我們可以將兩個位置，也就是 doubly-linked list 中常見的 `prev` 與 `next` 指標的值利用 XOR 疊在一起，達到將兩個位置利用一個指標表示的效果

在第一題中，我們要實作的是將 `left` 與 `right` 兩的 linked list 合併起來，所以在 `LL1` 中，我們所要做的事情是將 `merge` 指標現在所指向的元素與 `left` 連接起來，所以：
> `LL1` = `XOR(merge->addr, left)`

而在 `LL2` 的部分，因為我們是要將 `left` 連接在 `merge` 的後面，所以表示我們要捨棄原本的 `addr` 值，但是在排序的當下因為我們並不知道下一個要放哪個節點，所以其 `addr` 應該更改為 `merge` 也就是它的上一個節點的位址。因此：
> `LL2` = `merge`

而在 `RR1` 我們所做的事情與 `LL1` 類似，但根據 `LL1` 的情況判斷， `RR1` 的情況應該為 `right->data < left->data` ，就是將 `right` 的節點連接到合併的 list 中，所以 `RR1` 所做的應該為：
> `RR1` = `XOR(merge->addr, right)`

接著 `RR2` 就是更換 `right` 的 `addr` 指標，讓其能夠正確的連接在合併的 list 上，也就是：
> `RR2` = `merge`

在測驗 2 裡，我們要做的是將 singly-lined list 插入節點的寫法從

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

換成利用指標的指標所改寫的較簡潔的版本：

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && AA)
        BB;
    newt->next = *link;
    *link = newt;
}

因為兩者的用途是一樣的：將一個新的節點 `newt` 插入到一個遞增排列的 list 之中。而 while 迴圈的目的，就是在尋找插入 `newt` 的位置，且在 [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence) 中有列出 `->` 的優先度是高於 `*` 的 (`->` 的 precedence 為 1； `*` 的 precedence 為 2)，為了讓程式能夠正常運作，我們需要先取值後再取資料，因此答案應該為：
> `AA` = `(*link)->data < newt->data`

而因為在 while 迴圈的行為就是遊歷整個 list 的作用，並且考慮 `link` 本身的型態是指標的指標，所以在移動到下個節點的時候需要對該指標再進行取址的動作。而需要特別注意的是因為 `address of : &` 的 precedence 是 2 ，所以在使用 `&` 時，不用再加上一層括號，因此答案就會是：
> `BB` = `link = &(*link)->next`

## XOR linked list 排序的實作原理
在本次測驗中所實作的排序總共分兩個階段
1. 切割 list
2. 合併 list

在切割的實作上，所採用的做法是將最左的節點與剩下的節點切開，也就是以下程式碼所在的事情

list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);

首先我們將 `left` 與 `right` 指標分開賦值，且因為 start 是開頭的節點，所以其 `addr` 值就是其下一個節點的位址， `right` 就可以直接使用其 `addr` 當作下一個節點的位址使用。接著切斷 `left` 所指向節點的連結，接著利用 `XOR` 的特性將 `right->addr` 中 `left` 的位址刪除，完成節點的切割

接著利用遞迴的手法將剩下的元素進行切割，也就是下列程式碼所做的事情

left = sort(left);
right = sort(right);

當節點都已經切割完畢，接著就是將各個節點合併在一起，在實作上我們利用一個指標 `merge` 當作 iterator 並逐步進行合併的操作。

首先我們要先判斷 `left` 與 `right` 是不是只有單一節點的 list ，如果不是的話，我們接著要判斷 `left` 與 `right` 之中，哪個節點的 `data` 較小，如果 `left` 的 `data` 較小，我們就執行 `if` 的動作，如果 `right` 的 `data` 較小，我們則執行 `else` 的動作。

接著則是判斷目前 list 與節點的狀況，首先如果我們要連接的 list 不是一個未連接的節點，我們需要將它與下一個節點切斷，如下列程式碼所示

list *next = left->addr;
if (next)
    next->addr = XOR(left, next->addr);

接著我們要將該節點與 `merge` 現在所指下的節點連接在一起，並考慮到可能這是我們連接的第一個節點，就會需要執行 `merge == NULL` 的情況，如果 `merge != NULL` 我們就將節點接上，重複這樣連接與合併的過程，我們就可以得到一個排序好的 list。

## 改進 XOR linked list 排序的實作
在上述的排序實作中，因為我們所使用的切割方式在每次遞迴呼叫的時候會切割出:
1. 該狀態的第一個節點
2. 除了第一個節點外的其他節點

所以在原本的實作中假設我們的 list 中有 $n$ 的節點，就會導致我們需要呼叫 $n$ 次才能完成 list 的切割。但是如果我們改為每次切割就是將整個 list 切割為一半，這樣我們只需要 $\log_2{n}$ 次的呼叫就能完成 list 的切割。

### 設計實驗驗證其改善的程度
我使用 `stdlib.h` 中所定義的 `rand()` 函式產生出介於 0 ~ 1000 的給定數量的資料，將其存入 `a`, `b` 兩個 list 中，並分別使用原先版本的排序與更改分割流程的版本進行排序。而執行時間則使用定義於 `time.h` 的 `strcut timespec` 進行計時。

將程式根據不同的節點個數（1 ~ 1000）執行 $100$ 次並取 $95\%$ 的信賴區間進行計算。

而最後的測試結果如下圖：

從本圖中可以發現，若使用將 list 分割為兩個個數相同的 list 再進行遞迴的話，執行效率可以得到大幅的提升

## 觀察硬體組態
根據我的電腦的訊息

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
Stepping:            9
CPU MHz:             1779.451
CPU max MHz:         3500.0000
CPU min MHz:         400.0000
BogoMIPS:            6199.99
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            4096K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp md_clear flush_l1d

可以看到我的 L1d cache 的大小為 32K

而 cacheline 的大小則被記錄在 `/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size` ，可以發現我的 cacheline 大小是 `64`

所以可以把 list 切割的最小單位改為 64 byte 的數量

因為一個節點的資料結構的空間大小為 16 byte ，所以我們最多可以把最小單位增加到 4 個節點，但因為考慮到還要使用其他的參數與指標來進行交換，所以我最後設定切割的最小單位為 2 個節點。

如果在最小單位的情況下，也就是在只有 2 個節點的 list 時，判斷第一個節點的數值是否比較大，如果比較小的話就回傳第二個節點的位址作為 `start` 回去，因為 XOR linked list 的結構在頭尾不需要額外作調整，所以可以直接將其回傳。

而測試的結果如下圖：

可以看到大多的情況下， cache version 都可以比切割至單一節點的情況還要好，在 list 長度為 1000 的情況下，兩種函式執行時間的差距可以到 10241 奈秒的差異。

## 更改 lab0-c / harness.c 結構
將 `harness.c` 中的 `struct BELE` 更改為下列結構

typedef struct BELE {
    struct BELE *addr;
    size_t payload_size;
    size_t magic_header;
    unsigned char payload[0];
} block_ele_t;

著手針對具節點間移動的操作進行修改：

將 `harness.c:find_header` 在使用 `cautious` 模式時尋找節點的操作改為下方之程式碼

    if (cautious_mode) {
        /* Make sure this is really an allocated block */
        block_ele_t *ab = allocated, *prev = NULL;
        bool found = false;
        while (ab && !found) {
            found = ab == b;
            // previous version
            // ab = ab->next;
            next_node(&ab, &prev);
        }
        if (!found) {
            report_event(MSG_ERROR,
                         "Attempted to free unallocated block.  Address = %p",
                         p);
            error_occurred = true;
        }
    }

補上 `next_node` 函式簡化移動指標的操作

static inline void next_node(block_ele_t **node, block_ele_t **prev)
{
    block_ele_t *next = XOR((*node)->addr, *prev);
    *prev = *node;
    *node = next;
}

將 `harness.c:test_malloc` 中連接節點的程式碼修改為下列：

    // cppcheck-suppress nullPointerRedundantCheck
    new_block->magic_header = MAGICHEADER;
    // cppcheck-suppress nullPointerRedundantCheck
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    // cppcheck-suppress nullPointerRedundantCheck
    new_block->addr = XOR(allocated, NULL);

    if (allocated)
        allocated->addr = XOR(new_block, allocated->addr);
    allocated = new_block;
    allocated_count++;

在修改 `harness.c:test_free` 函式之前，因為在函式中有涉及到節點刪除，所以我們需要先找出其前一個節點，當它的前一個節點被找出後，就可以利用 `XOR` 找出其後一個節點，所以設計 `find_prev` 函式來達到利用遍尋找出其前一個節點的目的

static block_ele_t *find_prev(block_ele_t *node)
{
    block_ele_t *curr = allocated, *prev = NULL;
    while (curr != node)
        next_node(&curr, &prev);
    return prev;
}

接著處理 `test_free` 中處理節點連接的實作

void test_free(void *p)
{
    ...
    
    /* Unlink from list */
    block_ele_t *bp = find_prev(b);
    block_ele_t *bn = XOR(b->addr, bp);
    if (bp) {
        // bp->next = bn;
        bp->addr = XOR(bp->addr, b);
        bp->addr = XOR(bp->addr, bn);
    } else {
        // allocated = bn;
        allocated = bn;
    }
    if (bn) {
        // bn->prev = bp;
        bn->addr = XOR(bn->addr, b);
        bn->addr = XOR(bn->addr, bp);
    }

    free(b);
    allocated_count--;
}

## 實作的限制
### 無法從單一節點的結構中取得前後節點的位址
在一般的 doubly-linked list 中，因為每個節點都存有前一個與後一個節點的位址，所以在實作像是刪除節點的時候，我們可以從 `node->prev` 直接取得前一個節點的位址。

在修改 `lab0-c/harness.c` 時，我發現因為 XOR linked list 無法從單一節點的結構中取得前後節點的位置，所以導致我需要多花時間從第一個節點開始往後找其對應的節點。而有可能因為尋找前一個節點所耗費的時間而被 Timeout。

## 解釋 insert 程式碼運作與實作原理
該程式的 `insert` 在做的事情就是將一個新的節點插入在一個遞增的 list 中，所以在插入節點時必須考慮其在 list 中的位置應該放在哪裡，而使用的方式就是從第一個節點開始比較每個節點的數值，當比較到節點的數值剛好大於被比較的節點的數值時，我們就把節點插入在其後面

所以在實作上，我們就會使用 while 迴圈，從 head 所指向的第一個節點開始尋找節點插入的位置，如下列所示

while (node != NULL && node->data < newt->data) {
    prev = node;
    node = node->next;
}

## 比較原始版本與 pointer to pointer 版本執行時間差異

利用 `isolcpus` 與 `taskset` 避免誤差產生，並使用 $95\%$ 的信賴區間剔除偏差值，測試使用原始版本以及 pointer to pointer 的執行時間比較，結果如下圖

可以看到 pointer to pointer 版本因為在 `insert` 的插入階段不需要判斷是否有前一個節點的情況，所以得以減少分支的數量，在執行時間上得到了小幅度的改進

## 在 Linux 核心中尋找類似手法並解說
在 Linux 核心中對於 bfq 的實作中就有使用到 pointer to pointer 的方法

首先我們可以先了解 bfq 的概念，根據 [The Linux Kernel Documentation](https://www.kernel.org/doc/html/latest/block/bfq-iosched.html) 的描述：
> BFQ is a proportional-share I/O scheduler, with some extra low-latency capabilities. In addition to cgroups support (blkio or io controllers), BFQ’s main features are:
> - BFQ guarantees a high system and application responsiveness, and a low latency for time-sensitive applications, such as audio or video players;
> - BFQ distributes bandwidth, and not just time, among processes or groups (switching back to time distribution when needed to keep throughput high).

可以知道 bfq 是用於分配 I/O 使用的排程器，而其實作就是以紅黑樹的結構來進行實作，因為紅黑樹在進行節點插入、刪除、查找的時間複雜度可以達到 $O(log\ {n})$，讓排程器可以快速的選擇程序進行操作。

而其 `bfq_insert` 的實作如下：

static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
{
    struct bfq_entity *entry;
    struct rb_node **node = &root->rb_node;
    struct rb_node *parent = NULL;

    while (*node) {
        parent = *node;
        entry = rb_entry(parent, struct bfq_entity, rb_node);

        if (bfq_gt(entry->finish, entity->finish))
            node = &parent->rb_left;
        else
            node = &parent->rb_right;
    }

    rb_link_node(&entity->rb_node, parent, node);
    rb_insert_color(&entity->rb_node, root);

    entity->tree = root;
}

可以看到實作中 `node` 就是一個 `struct rb_node` 的 pointer to pointer，作用就是在使用 `node` 進行遊歷的時候利用 pointer to pointer 的特性一更新 `node` 所指向的節點的連接，而不需要額外在宣告變數來處理這些操作

## 參考資料
1. [2020q1 第 3 週測驗題](https://hackmd.io/tciwz4l1Tiyb1JOzP94YpA?view)
2. [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence)
3. [BFQ (Budget Fair Queueing) - The Linux Kernel Documentation](https://www.kernel.org/doc/html/latest/block/bfq-iosched.html)