# 2019q1 Homework7 (skiplist)
contributed by < `bauuuu1021` >
* [作業要求](https://hackmd.io/s/rkl7BqCi4)
## 測驗及延伸
### 題目
給定一個 circular linked list 實作如下: (檔案 `list.h`)

#ifndef INTERNAL_LIST_H
#define INTERNAL_LIST_H

/* circular doubly-linked list */
typedef struct __list_t {
    struct __list_t *prev, *next;
} list_t;

/*
 * Initialize a list to empty. Because these are circular lists, an "empty"
 * list is an entry where both links point to itself. This makes insertion
 * and removal simpler because they do not need any branches.
 */
static inline void list_init(list_t *list) {
    list->prev = list;
    list->next = list;
}

/*
 * Append the provided entry to the end of the list. This assumes the entry
 * is not in a list already because it overwrites the linked list pointers.
 */
static inline void list_push(list_t *list, list_t *entry) {
    list_t *prev = list->prev;
    entry->prev = prev;
    entry->next = list;
    prev->next = entry;
    list->prev = entry;
}

/*
 * Remove the provided entry from whichever list it is currently in. This
 * assumes that the entry is in a list. You do not need to provide the list
 * because the lists are circular, so the list's pointers will automatically
 * be updated if the first or last entries are removed.
 */
static inline void list_remove(list_t *entry) {
    list_t *prev = entry->prev;
    list_t *next = entry->next;
    prev->next = next;
    next->prev = prev;
}

/*
 * Remove and return the first entry in the list or NULL if the list is empty.
 */
static inline list_t *list_pop(list_t *list) {
    list_t *foo = list->prev;
    if (foo == list)
        return NULL;
    LL1
}
#endif

請參照上方程式註解，補完對應程式碼。

### 作答區
根據 `list_pop()` 的註解

/*
 * Remove and return the first entry in the list or NULL if the list is empty.
 */

預期的行為是使用 `list_remove()` 移除並回傳該節點，或 list 為空時回傳 `NULL`，前半段程式碼就是在處理 list 為空的情況

list_t *foo = list->prev;
if (foo == list)
    return NULL;

而針對必須回傳節點的情況，可以發現選項中
* `(a)` return foo;
* `(b)` return foo->next;
* `(c)` return foo->prev;
* `(d)` list_remove(foo->prev); return foo;
* `(e)` list_remove(foo); return foo;
* `(f)` list_remove(foo->next); return foo->next;
* `(g)` list_remove(foo); return foo->next;

只有 (e) (f) 兩個選項有做到==移除並回傳==，但 `(f) list_remove(foo->next); return foo->next;` 中 `foo->next` 指向的是 `list`，其實是 list 的 head 而不是一個 entry

故答案應為 ==`(e)` list_remove(foo); return foo;==
### 延伸題目
:::success
延伸問題:
1. 研讀 2019q3 Week11 的 [cache-oblivious data structures](https://rcoh.me/posts/cache-oblivious-datastructures/) 參考資料，記錄所見所聞;
2. 依據之前給定的 Linux 核心 linked list 實作，開發 cache-oblivious 的版本，並證實其效益;
3. 實作 Skip list，並且比照之前的 unit test 提供對應的測試、效能分析，還有改善機制
:::
### 延伸問題 - 1
* 作者在 [Retrieve element from BST](https://github.com/rcoh/treelayout) 實驗中發現 cache-oblivious (綠線) 的效能隨著實驗大小變大而開始與另外兩個對照組有明顯差別
* 根據記憶體實際運作的情形來設計演算法
* 記憶體不是一次載入一個 Byte，而是一個 Block
* 因此在對較慢的記憶體做存取時，該考慮的其實不是讀一個 Byte 需要多少時間，而是為了此 Byte 所在的 Block 載入需要多少時間
* 故如果可以將演算法調整為針對某 Block 運算結束後再載入其他 Block ，可以大幅降低 I/O 成本
* 以下示意圖用同樣色線框在一起的代表在同一個 block
* leveled
* preorder

因此以上兩種資料結構，在從根節點開始尋找 BST 中特定節點都不是理想的，可能花大量時間載入一個 block 卻只用到其中的 1~少數個
* 但若修改儲存 BST 的記憶體方式，使每個 block 會被使用到的 element 數量提高，配置如下
(假設 B elements/block)<br>則不管搜尋目標在 BST 的何處，都固定會讀取路徑上每個 block 中 ${\log B}$ 個 element，因此會有差不多且不錯的效能表現
## skip list 在 Linux 之應用
>在 Linux 核心原始程式碼使用 skip list 的案例，介紹其原理，設計 Linux 核心模組的實驗
>* 需要涵蓋 kernel API 同步機制的運用
>* 執行時期的分析 (提示: 可善用 eBPF)
>

### 同步機制 API
根據 LWN 這篇 [文章](https://lwn.net/Articles/553047/)
>Insertion into the skiplist requires the programmer to get a "preload token" — skiplist_preload() ensures that the necessary memory is available and disables preemption. With the token in hand, it's possible to actually insert the item, then re-enable preemption.

可實作為類似下面 function 形式

int skiplist_preload(struct sl_list *list, gfp_t gfp_mask);

稍後完成 insertion 後必須根據上面 function 回傳的 `integer token` re-enable preemption
## 參考資料
* [Homework7 作業區](https://hackmd.io/s/S1xQB5RsV)
* [A kernel skiplist implementation - part 1](https://lwn.net/Articles/551896/)
* [A kernel skiplist implementation - part 2](https://lwn.net/Articles/553047/)
###### tags: `bauuuu1021` `linux2019` `2019spring`