# Linux 核心專題: Skip List 及核心應用場景
> 執行人: Tonr01
:::success
:question: 提問清單
* ?
:::
## 任務簡述
1. 重做[第 8 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz8)第二題，解釋程式碼運作原理，指出設計缺失並改進
2. 研讀〈[A kernel skiplist implementation](https://lwn.net/Articles/551896/)〉和〈[Skiplists II: API and benchmarks](https://lwn.net/Articles/553047/)〉，探討 Linux 核心引入的 skip list 的考量，找出現行 Linux 核心的應用案例
3. 分析 [Concurrent-Skip-list](https://github.com/shreyas-gopalakrishna/Concurrent-Skip-list) 並以 C11 Atomics 重新實作，搭配閱讀〈[Concurrent Skiplists](https://spcl.inf.ethz.ch/Teaching/2013-dphpc/final/4.pdf)〉，實作更高效的程式碼。
相關資訊
* [2019 年開發紀錄](https://hackmd.io/@Vy_ZuZdnSo-Wv4jSWgNmLw/B1OZFDL1H)
## 解釋給定的 Skip List 實作
### 主要結構體
```c
struct sl_link {
struct sl_link *prev, *next;
};
struct sl_list {
int size;
int level;
struct sl_link head[SL_MAXLEVEL];
};
```
`sl_list` 為 skip list 的結構體，其中 `size` 存放整個 skip list 的元素個數，`level` 存放 skip list 的層級數，而 `head` 會指向每層的 list 開頭。
```c
struct sl_node {
int key;
void *val;
struct sl_link link[0];
};
```
`sl_node` 為 skip list 的節點結構，其中 `key` 存放該節點的值，`val` 為存放該節點的位址，而 `link` 會指向其他層的該節點。
### `sl_node_alloc`
```c
static struct sl_node *sl_node_alloc(int key, void *val, int level)
{
struct sl_node *node =
malloc(sizeof(struct sl_node) + (level + 1) * sizeof(struct sl_link));
if (!node)
return NULL;
node->key = key, node->val = val;
return node;
}
```
`sl_node_alloc` 為配置記憶體空間給節點，因為每個元素所佔有的層數是隨機的，若是宣告成大小一致的 `link`，會造成記憶體的浪費，於是在 `sl_node` 中宣告 `struct sl_link link[0];`，將其宣告成一個可以擴充的陣列，所以在配置記憶體時就能視該元素所佔有的層數去動態的配置記憶體，一個節點所佔用的空間大小為節點本身的結構大小加上每一層連接的 link。
### `sl_list_alloc`
```c
struct sl_list *sl_list_alloc(void)
{
struct sl_list *list = malloc(sizeof(struct sl_list));
if (!list)
return NULL;
list->level = 0;
list->size = 0;
set_random();
for (int i = 0; i < SL_MAXLEVEL; i++)
list_init(&list->head[i]);
return list;
}
```
`sl_list_alloc` 為初始化 skip list，會將所有的 list head 初始化，將它的 `prev`, `next` link 都指向自己。
:::warning
這裡的 `set_random();` 的功用是什麼
> 注意其本質: "A skip list is a probabilistic data structure"
:::
### `sl_delete`
```c
void sl_delete(struct sl_list *list)
{
struct sl_link *n, *pos = list->head[0].next;
list_for_each_safe_from (pos, n, &list->head[0]) {
struct sl_node *node = list_entry(pos, 0);
free(node);
}
free(list);
}
```
`sl_delete` 是用來釋放整條 skip list，`head[0]` 為第一層的 list，也就是包含所有元素的 list，所以將每個節點都釋放，最後再將 list 釋放。
### `sl_search`
```c
void *sl_search(struct sl_list *list, int key)
{
int i = list->level;
struct sl_link *pos = &list->head[i];
struct sl_link *head = &list->head[i];
for (; i >= 0; i--) {
pos = pos->next;
list_for_each_from (pos, head) {
struct sl_node *node = list_entry(pos, i);
if (node->key > key)
break;
else if (node->key == key)
return node->val;
}
pos = pos->prev;
pos--;
head--;
}
return NULL;
}
```
`sl_search` 是用來搜尋節點是否存在於 skip list，首先會從 skip list 的最上層開始找起，若是找到 `key` 值一樣的節點就回傳該節點的位址，若是目前走訪的節點的 `key` 值大於要搜尋的節點的 `key` 值，則表示搜尋的節點可能會在下一層，所以先回到前一個節點，再往下一層去走訪，直到每一層都走訪完。
### `sl_insert`
```c
int sl_insert(struct sl_list *list, int key, void *val)
{
int i, level = random_level();
struct sl_link *pos = &list->head[level];
struct sl_link *head = &list->head[level];
struct sl_node *new = sl_node_alloc(key, val, level);
if (!new)
return -ENOMEM;
if (level > list->level)
list->level = level;
for (i = level; i >= 0; i--) {
pos = pos->next;
list_for_each_from (pos, head) {
struct sl_node *tmp = list_entry(pos, i);
if (tmp->key > key) {
break;
} else if (tmp->key == key)
goto failed;
}
pos = pos->prev;
list_add(&new->link[i], pos);
pos--;
head--;
}
list->size++;
return 0;
failed:
free(new);
return -EEXIST;
}
```
`sl_insert` 是用來插入新節點到 skip list，並回傳 skip list 大小，一開始先用 `random_level` 函式決定出該節點所佔的層數。
```c
static inline int random_level(void)
{
int level = 0;
uint32_t random_seed = (uint32_t) random();
while (random_seed && (random_seed & 1)) {
random_seed >>= 1;
level++;
}
return level >= SL_MAXLEVEL ? SL_MAXLEVEL - 1 : level;
}
```
因為節點所佔的層數是隨機產生的，所以這裡使用隨機方法 (稱作 "coin flip"，也就是「擲硬幣看正反面結果」) 決定這個元素有幾層節點。詳細的實作方法為先用 `random()` 去得到一個隨機數，`random_seed & 1` 的用意是視 `random_seed` last bit 是 1 或 0 去決定是否增加層數，也就是決定該元素僅有 1 層節點機率為 $\dfrac{1}{2}$，且有 2 層節點機率為 $\dfrac{1}{4}$，僅有 3 層節點機率為 $\dfrac{1}{8}$，以此類推。
```c
for (i = level; i >= 0; i--) {
pos = pos->next;
list_for_each_from (pos, head) {
struct sl_node *tmp = list_entry(pos, i);
if (tmp->key > key) {
break;
} else if (tmp->key == key)
goto failed;
}
pos = pos->prev;
list_add(&new->link[i], pos);
pos--;
head--;
}
```
走訪節點的方式與 `list_search` 相同，會先從該節點所佔的最高層數開始走訪，去比較每個節點的 `key` 值，找到插入的地方，再用 `list_add` 插入節點到每層 list，直到走訪完全部的 skip list。
```c
failed:
free(new);
return -EEXIST;
```
若是發現該節點已經在 skip list 中，則 `goto failed;` ，表示插入失敗。
### `sl_erase`
```c
int sl_erase(struct sl_list *list, int key)
{
int i = list->level;
struct sl_link *pos = &list->head[i];
struct sl_link *n, *head = &list->head[i];
for (; i >= 0; i--) {
pos = pos->next;
list_for_each_safe_from(pos, n, head) {
struct sl_node *tmp = list_entry(pos, i);
if (tmp->key == key) {
for (; i >= 0; i--) {
list_del(pos--);
if (list->head[i].next == &list->head[i])
list->level--;
}
free(tmp);
list->size--;
return 0;
} else if (tmp->key > key)
break;
}
pos = pos->prev;
pos--;
head--;
}
return -EINVAL;
}
```
`sl_erase` 是用來刪除指定節點，一樣從最高層數開始，先去找目前層數是否有該節點，若沒有，則往下一層找，若有，則使用 `list_del` 函式將該節點從 list 分離出來，並將前後的 link 連接。
```c
static inline void __list_del(struct sl_link *prev, struct sl_link *next)
{
next->prev = prev;
compiler_barrier();
prev->next = next;
}
```
`compiler_barrier()` 的目的在於告訴編譯器，在 barrier() 前後必須明確區隔，barrier 之前的操作不可跑到 barrier 後，防止程式碼因編譯器優化而造成問題。
```c
if (list->head[i].next == &list->head[i])
list->level--;
```
若是當刪除該節點後，該 list 為空時，則更新層數的資料，再繼續往下一層走訪，直到最後一層。
## 改進給定的 Skip List 實作
### 改進一
```c
static inline int random_level(void)
{
int level = 0;
uint32_t random_seed = (uint32_t) random();
while (random_seed && (random_seed & 1)) {
random_seed >>= 1;
level++;
}
return level >= SL_MAXLEVEL ? SL_MAXLEVEL - 1 : level;
}
```
在 `random_level` 函式中，須從最低位元開始檢查，直到該 bit 為 0 時才停止，所以最壞情況會是 $O(\log{n})$ ，也就是最差須做 32 次檢查。
```
random_seed =
01101011100010110100010101100111
^
check
last bit == 1
level = level + 1 = 1
random_seed >>= 1
00110101110001011010001010110011
^
check
last bit == 1
level = level + 1 = 2
random_seed >>= 1
00011010111000101101000101011001
^
check
last bit == 1
level = level + 1 = 3
random_seed >>= 1
00001101011100010110100010101100
^
check
last bit == 0
level = 3
done
```
可以看出只需要知道從最低位元到高位元第一個為 0 的 bit 位置，就可以得到 `level` 的值，所以這裡使用 `__builtin_ffs` 來改善。
* `int __builtin_ffs (unsigned int x) 會回傳 1 + LSB 為 1 的 index`
主要的想法是先將 `random_seed` 的值與 `-1` 做 $XOR$ ，可以得到與 `random_seed` 0, 1 相反的值，再去用 `__builtin_ffs` 去得到 LSB 為 1 的 index ，此時 LSB 為 1 的 index 就是原本從最低位元到高位元第一個為 0 的 bit 位置。
```
random_seed =
01101011100010110100010101100111
random_seed ^ -1 =
10010100011101001011101010011000
^
4
__builtin_ffs(random_seed ^ -1) = 4
level = 4 - 1 = 3
```
#### 改善後程式碼
```c
static inline int random_level(void)
{
uint32_t random_seed = (uint32_t) random();
int level = __builtin_ffs(random_seed ^ -1) - 1;
return level >= SL_MAXLEVEL ? SL_MAXLEVEL - 1 : level;
}
```
#### 以 Linux 效能分析工具: 運用 perf
這裡分別用改善前與改善後的 `random_level` 函式產生 1000000 筆資料，並執行 5 次做比較。
```shell
$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./random
choose 1 or 2:1
1: random_level_origin
2: random_level_update
```
#### `random_level_origin`
```
Performance counter stats for './random' (5 runs):
10,745 cache-misses # 37.749 % of all cache refs ( +- 5.14% )
28,087 cache-references ( +- 1.58% )
87,840,933 instructions # 1.22 insn per cycle ( +- 0.01% )
72,349,681 cycles ( +- 0.73% )
0.591 +- 0.223 seconds time elapsed ( +- 37.75% )
```
#### `random_level_enhance1`
```
Performance counter stats for './random' (5 runs):
10,910 cache-misses # 37.399 % of all cache refs ( +- 6.62% )
27,999 cache-references ( +- 2.91% )
79,842,405 instructions # 1.34 insn per cycle ( +- 0.02% )
59,620,192 cycles ( +- 0.10% )
0.423 +- 0.101 seconds time elapsed ( +- 23.95% )
```
#### 效能比較
|event data | origin | enhance1 |
| :- | -: | -: |
| cache-misses | 10,745 | 10,910 |
| cache-references | 28,087 | 27,999 |
| instructions | 87,840,933 | 79,842,405 |
| cycles | 72,349,681 | 59,620,192 |
可以看出 cache-misses 與 cache-references 是差不多的，減少了大約 10％ 的 instructions，並減少約 18％ 的 cycles。
> [commit e725145](https://github.com/Tonr01/skiplist/commit/e72514555cf2d917a641aaeb90b999d4c784e887)。
### 改進二
因為 skiplist 是一種 probabilistic data structure，所以在決定 skiplist 的層數時，最壞情況可能會增長很多不需要的層數，因為決定層數主要是用 flip-coin 的方法，多餘的層數會造成不必要的走訪。
```
level 11 = 36 ->tail, num of node = 1
level 10 = 36 ->tail, num of node = 1
level 9 = 36 ->tail, num of node = 1
level 8 = 36 ->tail, num of node = 1
level 7 = 27 ->36 ->tail, num of node = 2
level 6 = 27 ->36 ->tail, num of node = 2
level 5 = 27 ->36 ->tail, num of node = 2
level 4 = 10 ->27 ->32 ->36 ->40 ->50 ->tail, num of node = 6
level 3 = 10 ->17 ->27 ->32 ->36 ->40 ->50 ->tail, num of node = 7
level 2 = 10 ->17 ->27 ->28 ->29 ->32 ->36 ->40 ->50 ->tail, num of node = 9
level 1 = 2 ->5 ->7 ->10 ->12 ->17 ->20 ->23 ->25 ->27 ->28 ->29 ->32 ->35 ->36 ->40 ->47 ->48 ->49 ->50 ->tail, num of node = 20
level 0 = 0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9 ->10 ->11 ->12 ->13 ->14 ->15 ->16 ->17 ->18 ->19 ->20 ->21 ->22 ->23 ->24 ->25 ->26 ->27 ->28 ->29 ->30 ->31 ->32 ->33 ->34 ->35 ->36 ->37 ->38 ->39 ->40 ->41 ->42 ->43 ->44 ->45 ->46 ->47 ->48 ->49 ->50 ->tail, num of node = 51
```
可以看出 level 8~11 重複 4 層，當走訪的值不是 36 時，則必須多走這些重複的層，會造成些許效能上的浪費，balanced skip list 的第 Level i+1 通道包含 Level i 通道的每 1/p 個元素，所以最佳的層數為 $\log(key 的值域)$，所以新增一個函式去對 key 值範圍取 log，藉此去限制整個 skiplist 的層數。
```c
int log2_32(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x >> 1) + 1;
}
```
這個取 log 的函式是先前在測驗裡的方法，這裡剛好能使用到，詳細方法在 [log 函式](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-4)。
#### 用 `__builtin_clz` 去改寫 log 函式
要對一個 32 bits 的值取 $log$ 只需要知道該值的 MSB 為 1 的位置即可，所以用 `__builtin_clz` 去取得 MSB 為 1 ，其左邊 0 的數量，在用 32 減去，就能知道 MSB 為 1 的位置。
> [commit 53f8e59](https://github.com/Tonr01/skiplist/commit/53f8e5910f8f532199f4eb66c1ae95ba85515e2d)。
```
32 bits integer:279
binary format = 100010111
^
9
__builtin_clz(279) = 23
log(279) upper = 32 - 23 = 9
```
```c
static inline int log2_32(uint32_t x)
{
return 32 - __builtin_clz(x);
}
```
#### 改善後的結果
以 key 值範圍為 50 為例，$log(50)$ 取上限為 6 ，所以可以將層數限制在 6 層內，可以省下些許不必要的空間。
```
level 6 = 22 ->46 ->tail, num of node = 2
level 5 = 16 ->18 ->22 ->46 ->49 ->tail, num of node = 5
level 4 = 1 ->16 ->18 ->22 ->31 ->46 ->49 ->tail, num of node = 7
level 3 = 1 ->16 ->18 ->20 ->22 ->31 ->35 ->46 ->49 ->tail, num of node = 9
level 2 = 1 ->9 ->16 ->18 ->20 ->22 ->24 ->31 ->32 ->35 ->46 ->49 ->tail, num of node = 12
level 1 = 0 ->1 ->3 ->5 ->6 ->7 ->9 ->10 ->14 ->15 ->16 ->18 ->20 ->21 ->22 ->24 ->31 ->32 ->34 ->35 ->36 ->38 ->46 ->47 ->49 ->50 ->tail, num of node = 26
level 0 = 0 ->1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9 ->10 ->11 ->12 ->13 ->14 ->15 ->16 ->17 ->18 ->19 ->20 ->21 ->22 ->23 ->24 ->25 ->26 ->27 ->28 ->29 ->30 ->31 ->32 ->33 ->34 ->35 ->36 ->37 ->38 ->39 ->40 ->41 ->42 ->43 ->44 ->45 ->46 ->47 ->48 ->49 ->50 ->tail, num of node = 51
```
## 研讀給定的 LWN 文章，討論 Linux 核心程式碼的應用
參見 `mm/memory-tiers.c`
### Linux 引入 skiplist 的考量
#### Average case
| Data sturcture | Access | Search | Insertion | Deletion |
| :- | -: | -: | -: | -: |
| Linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$ |
| Red-black tree | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ |
| Skip list | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ |
一般的鏈結串列在資料數目龐大時，其 access, search 會有效能上的瓶頸，而 red-black tree 雖然在平均的時間複雜度上跟 skiplist 一樣，而且可以藉由 read-copy-update (RCU) 去達到 concurrent reads，但卻無法達到 concurrent writes，而 skiplist 可以達到 concurrent writes 與 reads。
## TODO: 以 C11 Atomics 改寫 [Concurrent-Skip-list](https://github.com/shreyas-gopalakrishna/Concurrent-Skip-list) 並改進效率
Sign in with Wallet
Connect another wallet