contributed by < tinyynoob
>
本題主要是在闡述 Linux kernel 當中 hash table 的實作,觀察
可知 table 結構大致如下
每格都連接著一條 linked list (或 NULL ),以 heads[2]
為例
每個 hlist_node 上的 entry 結構定義為:
其中不同節點的 key 應不同,即 key 的唯一性需要被保證,否則後續在 find_key() 可能會出問題。
table size (圖中的數字 4 ) 是由 MAP_HASH_SIZE()
macro 來取得,其值為輸入乘以 2 ,並會紀錄於 map_t
的 bits
成員。
為何 bits
不使用 size_t
型別?
此外,為何會選用 bits
做為變數名稱?是否有什麼特殊意涵?
取名
bits
主要是搭配 capacity 的計算,無論是size_t
或ssize_t
都不影響理解。
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
該函式的功能為動態配置出 table 結構,並依序將每個 hlist_head 的 first
成員都初始化為 NULL 。
函式的第 2 行使用 hash function 快速前往資料所在的 hlist ,接著 3 到 7 行走訪該 hlist ,一個一個比對是否為我們要尋找的節點,若找不到則回傳 NULL 。
以上功能正確運作的一個必要條件是 key 的唯一性,否則可能會找到 key 值相同的另一個節點,使得後續取出的 data 不如預期。
這裡頭所使用的 hash function 定義為
目前不太清楚為何選用 golden ratio 為乘數。
這裡使用了 Fibonacci hashing ,根據 wikipedia ,這樣的 hash 方法可以使結果均勻分配在 table space 中。
或許可以用程式測看看它的分佈
至於前面的 macro define 怎麼來呢?首先, golden ratio 在數學上為 ,我們可以計算出其倒數 恰好是原本的小數部份。
linux/hash.h 的註解中引註了一篇文章 Linux Kernel Hash Table Behavior: Analysis and Improvements ,在其 5.1 節給出
這個 4294967296 顯然是 32 位無號數的最大值加 1 ,也就是 。
這代表我們將輸入的 val
乘上 幾乎等同於乘上 2654435761 並右移 32 ,然後我們需要左移 bits
位以充分利用 hashtable 的 size 。
然而 hash.h 裡定義的 golden_ratio_32 是 0x61C88647 也就是 1640531527 ,並不是文章中的 2654435761 ,由於 0x61C88647 的二進制最高位是 0 ,所以我以為這個差異不是來自有無號轉換。
查詢了網路上的討論,得到答案說這其實還是跟有號數、無號數有關,我整理如下
signed | unsigned | binary | hex |
---|---|---|---|
1640531527 | 1640531527 | 01100001110010001000011001000111 | 0x61C88647 |
-1640531527 | 2654435769 | 10011110001101110111100110111001 | 0x9E3779B9 |
所以兩種相乘的答案雖然會以截然不同的面貌存在記憶體中,但就二補數的電腦數值系統而言,它們所表達的數「值」是相同,只差了 sign ,也因此並不影響 hash 的 distribution 。
另外雖然 2654435769 並不是文章中給出的 2654435761 ,但是它更接近於我們期望的 0.618033989 :
該函式去 map
中尋找是否有符合 key
值的 entry ,若有便將該 entry 的 data
讀出來。
首先 3 至 7 行直接到 map
當中查找,若已存在該 key 則不增添新節點,反之進入新增節點的程序。
以下舉例說明新增節點的過程:
Suppose
假設 [1]
原為
現在我們希望將 kn
所指到的節點放進這條 list ,最便利的方法是直接塞在最前方
圖中黑色的連線已由程式碼第 14 及 15 行完成,因此另外兩條藍色的連線即為我們在 AAA
和 BBB
需要達成的功能。
map_deinit()
的功能為刪除掉整個 hash table ,其運作流程大致如下圖
接著圖解內層迴圈的行為,假設程式在某個時候執行到第 8 行
在程式執行到第 21 行時會變成
百思不解什麼情況下會出現第 13 行的 condition ,或許與多執行緒有關?
看 Linux 核心原始程式碼
list.h
對於hlist_unhashed
的註解:然後再翻閱核心文件關於 RCU 對於 reader 的行為
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
程式運作邏輯可大致理解如下:
成功配對出 target
值則達成目標,否則將現值加入 hash table 再繼續往下尋找。
此處使用 hashtable 帶來的主要好處是加快搜尋舊資料的速度,避免一一確認帶來的 低效。
本題範例與 Linux kernel 中所使用的 hash 結構相同,最大的區別在於 kernel 中有為了多使用者並行讀寫的情境設計了另一組 API ,同時在此種情境下的 hashtable 被稱為 rcu enabled hashtable 。
RCU 的主要概念是將 更新 動作拆分成 移除 與 再生 ,原因在於在並行的情境下,若更新在 reader 使用資料時發生,則可能會導致 reader 讀到更新一半的資料,發生非預期的後果; RCU 機制使用 read-side critical section , reader 只可能讀到完全舊的資料抑或是完全新的資料,如此便不致發生讀取錯誤。
在遞迴的實作中,程式先確認 head
與 head->next
是否 duplicate ,若有則進入 while 迴圈刪除這組 duplicate ,此外就繼續遞迴下去。
例如:
經過 while 後會變成
由於第 10 行的遞迴參數是 head->next
,因此它會對 b 呼叫遞迴,如此一來便移除了所有重複的 a 。
COND1 及 COND2 都是 duplicate 的判斷式
這支程式主要是用 linked list 來實現 cache 的運作,並使用 mod 運算來映射對應的 cache 位置。
cache 的本體結構宣告為
cache 的 creation 如下
大致上就是配置空間和初始化,唯一需要留意的是第 3 行的語法可以依據 capacity
的值動態配置 hheads[]
的大小。
每個載有資料的節點有結構:
比較特別的是節點有 hlink
與 dlink
兩個用於 linked list 的成員,稍後會解釋為何如此。
第 4 行由輸入 key
值對應 cache 的位置。
第 5 行開始明顯是個用來尋找 node 的迴圈,觀察參數的數量與型別,可以推測 MM2
應為 list_for_each_entry()
。
程式在 obj->hheads[hash]
list 中尋找,找到之後的行為是回傳 value
並將 dlink
移到 obj->dhead
前方,如果找不到則回傳 -1 。我們可以發現 obj->hheads[hash]
這條 list 都沒有被改變。
得知 obj->hheads[]
結構是 array of struct list_head ,每一個 element 拖著一條 list ,其中的 node 藉由 hlink
成員與對應的 list 互動。所有被放到 cache 的資料都會以節點形式存在 obj->hheads[]
的某處,且可以用近乎 的速度快速被找到。
For some variable ,
這裡用的都是 list.h 裡一般的 list
,所以 prev
全部是 direct pointer 。
除了 hheads[]
以外,我們的 cache 額外 maintain 了一條 list dhead
。由於 obj->dhead
這條 list 在每次節點被 access 時都會更動,我們可以猜想它就是用來指示 recently used 的標的。因為資料每次被 access 就會被移到最前方,所以節點位置越靠後表示越久沒被 access 。而每個節點是用 dlink
來與 obj->dhead
串列互動, hlink
與 dlink
各自獨立、互不干擾。這就像是一筆資料有兩個分身,一個在 hheads[]
中,另一個在 dhead
中。
Example for obj->capacity=3 :
此外值得注意的是第 7 行,藉由 lru->dlink
的方式快速找到目標節點在 dhead
中的分身,我們就不必再於 dhead
走訪一次。
以上圖為例,當又有一筆資料要放進 cache 的時候,節點 a
的兩個分身都會被踢出,因為它在 dhead
這條串列的尾巴,如此功能便是在 CachePut()
實現。
此函式概略運作邏輯如圖:
第 5 行依據 key
尋找節點是否已存在,因此 MM3
顯然也是 list_for_each_entry()
。
根據流程圖可以分成 3 個分支討論
如果有找到的話就更新 dlink
(recently used) ,並修改節點的 value
值。
使用 obj->count
來計數是否已達 cache 容量上限 。
在空間已滿的情況下,我們的 policy 是移除 least recently used 的節點,也就是 dhead
的尾節點。
為了避免 free()
之後又馬上 malloc()
,我們可以回收利用舊節點空間。首先我們得要找到舊節點,取得尾節點可以使用 API list_last_entry()
,於是我們解出了 MM4
。
接著得將節點從對應的 hhead[]
和 dhead
中移出,填入新資料之後依據新的 key
重新串入 hheads[hash]
並移到 dhead
最前方。
這個分支也相對簡單,就是為資料建構新節點,並更新 hheads[hash]
, dhead
及 count
。
將 obj
清空的函式, MM1
為 list_for_each_entry_safe()
,此 API 有註解
注意到因為所有進到 cache 節點必定有在 dhead
的分身,所以我們不需要去走訪 hheads[]
陣列,只要清空 dhead
串列就可以釋放完所有的 LRUNode
。
且因 hheads[]
是隨著 obj
動態配置而來,所以我們不應該執行
只要呼叫
便能一勞永逸。
在 hlink
所屬的串列上,我們會進行的操作就是
並沒有特別需要 access 尾節點的需求,所以我認為我們沒有必要使用環狀串列,取而代之可以使用 kernel 中 hlist
風格 (如測驗 1 ) 的串列,它更便利於從 list 中移除節點。
而 dlink
所屬的串列則因頭尾操作的需要,維持 kernel list
風格。
對應本題,我找到了 linux/lru_cache.h 。
其中定義了兩個資料結構
這裡的 colision
成員相當於我們的 hlink
,使用了 hlist
的結構,與我的想法相符; list
成員相當於 dlink
。
lc
應是 lru_cache
的縮寫。
不確定 element 是怎麼存放資料的,是用內嵌結構或是用 unsigned 儲存指標訊息
在 lru_cache.h 中,節點通常不會真的被刪除,而是不斷被移到 lru_cache
裡的各個不同串列,見這段註解
藉此可以推測 refcnt
的功能是紀錄該 element 的 user 數量,原意可能是 reference counter 。若沒有 user 使用則會被移到 lru
或 free
。
為了了解這些函式,得再前往 lru_cache.c
lc_get
的實作函式