Linux 核心專題: Skip List 及核心應用場景

執行人: Tonr01

提問清單

• ?

任務簡述

1. 重做第 8 週測驗題第二題，解釋程式碼運作原理，指出設計缺失並改進
2. 研讀〈A kernel skiplist implementation〉和〈Skiplists II: API and benchmarks〉，探討 Linux 核心引入的 skip list 的考量，找出現行 Linux 核心的應用案例
3. 分析 Concurrent-Skip-list 並以 C11 Atomics 重新實作，搭配閱讀〈Concurrent Skiplists〉，實作更高效的程式碼。

相關資訊

• 2019 年開發紀錄

解釋給定的 Skip List 實作

主要結構體

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 開頭。

struct sl_node {
    int key;
    void *val;
    struct sl_link link[0];
};

sl_node 為 skip list 的節點結構，其中 key 存放該節點的值，val 為存放該節點的位址，而 link 會指向其他層的該節點。

sl_node_alloc

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

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 都指向自己。

這裡的 set_random(); 的功用是什麼

注意其本質: "A skip list is a probabilistic data structure"

sl_delete

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

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

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 函式決定出該節點所佔的層數。

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 層節點機率為

${\displaystyle \frac{1}{2}}$，且有 2 層節點機率為

${\displaystyle \frac{1}{4}}$，僅有 3 層節點機率為

${\displaystyle \frac{1}{8}}$，以此類推。

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。

failed:
    free(new);
    return -EEXIST;

若是發現該節點已經在 skip list 中，則 goto failed; ，表示插入失敗。

sl_erase

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 連接。

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 後，防止程式碼因編譯器優化而造成問題。

if (list->head[i].next == &list->head[i])
    list->level--;

若是當刪除該節點後，該 list 為空時，則更新層數的資料，再繼續往下一層走訪，直到最後一層。

改進給定的 Skip List 實作

改進一

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

改善後程式碼

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 次做比較。

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

改進二

因為 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\mathrm{的}\mathrm{值}\mathrm{域})$，所以新增一個函式去對 key 值範圍取 log，藉此去限制整個 skiplist 的層數。

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 函式。

用 __builtin_clz 去改寫 log 函式

要對一個 32 bits 的值取

$log$ 只需要知道該值的 MSB 為 1 的位置即可，所以用 __builtin_clz 去取得 MSB 為 1 ，其左邊 0 的數量，在用 32 減去，就能知道 MSB 為 1 的位置。

commit 53f8e59。

32 bits integer:279
binary format = 100010111
                ^
                9
    
__builtin_clz(279) = 23
log(279) upper = 32 - 23 = 9

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 並改進效率