LC-trie 實現說明

節點型別

葉節點 (leaf)

帶有資料的終端節點。 它具有相關鍵的副本，以及“hlist”，其中包含按字首長度排序的路由表條目。 請參閱 struct leaf 和 struct leaf_info。

trie 節點或 tnode

內部節點，包含子節點（葉節點或 tnode）指標的陣列，透過鍵的子集進行索引。 請參閱 級別壓縮。

一些概念解釋

Bits (tnode)

用於索引到子陣列中的鍵段中的位數 - “子索引”。 請參閱 級別壓縮。

Pos (tnode)

用於索引到子陣列中的鍵段的位置（在鍵中）。 請參閱 路徑壓縮。

路徑壓縮 / 跳過的位

任何給定的 tnode 都透過其父節點的“pos”和“bits”指定的鍵段，從其父節點的子陣列連結。 在某些情況下，此 tnode 自身的“pos”不會與其父節點 (pos+bits) 立即相鄰，但鍵中會有一些位被跳過，因為它們表示沒有偏差的單條路徑。 這些“跳過的位”構成了路徑壓縮。 請注意，搜尋演算法在搜尋時會簡單地跳過這些位，因此有必要將鍵儲存在葉節點中，以驗證它們是否真的與我們正在搜尋的鍵匹配。

級別壓縮 / 子陣列

trie 保持級別平衡，在某些情況下，將已滿的子節點（請參閱“full_children”）的子節點向上移動一級，這樣每個內部節點 (“tnode”) 可能包含指向多個子節點的任意大小的連結陣列，而不是純粹的二叉樹。 相反，具有大部分為空的子陣列（請參閱 empty_children）的 tnode 可以被“對半”，將其某些子節點向下移動一級，以避免不斷增加的子陣列。

empty_children

給定 tnode 的子陣列中為 NULL 的位置數。

full_children

給定 tnode 中未進行路徑壓縮的子節點數。（換句話說，它們不是 NULL 或葉節點，並且它們的“pos”等於此 tnode 的“pos”+”bits”）。

(這裡的“full”一詞更多的是“完整”的意思，而不是“空”的反義詞，這可能會有點令人困惑。)

評論

我們已嘗試使程式碼結構儘可能接近 fib_hash，以便進行驗證並幫助進行審查。

fib_find_node()

瞭解此程式碼的一個好的開始。 此函式實現了一個簡單的 trie 查詢。

fib_insert_node()

在 trie 中插入一個新的葉節點。 這比 fib_find_node() 複雜一點。 插入一個新節點意味著我們可能必須在 trie 的一部分上執行級別壓縮演算法。

trie_leaf_remove()

查詢鍵，刪除它並執行級別壓縮演算法。

trie_rebalance()

動態 trie 的關鍵函式，在 trie 中進行任何更改後，它都會執行以進行最佳化和重組。 它將從給定的 tnode 向上遍歷 trie，朝著根節點方向，在每個步驟中執行 resize() 以實現級別壓縮。

resize()

分析 tnode 並透過重複膨脹或收縮子陣列大小來最佳化子陣列大小，直到它滿足最佳級別壓縮的標準。 這部分非常遵循原始論文，並且可能有一些實驗空間。

inflate()

將 tnode 中子陣列的大小加倍。 由 resize() 使用。

halve()

將 tnode 中子陣列的大小減半 - inflate() 的逆運算。 由 resize() 使用；

fn_trie_insert(), fn_trie_delete(), fn_trie_select_default()

路由操作函式。 應該非常符合 fib_hash 中的相應函式。

fn_trie_flush()

這會遍歷完整的 trie（使用 nextleaf()）並搜尋必須刪除的空葉節點。

fn_trie_dump()

轉儲按字首長度排序的路由表。 這比相應的 fib_hash 函式慢一些，因為我們必須為每個字首長度遍歷整個 trie。 相比之下，fib_hash 被組織為每個字首長度一個“區域”/雜湊。

鎖

fib_lock 用作 RW 鎖，方式與 fib_hash 中的方式相同。 但是，這些函式在某種程度上是分開的，以便用於其他可能的鎖定場景。 理論上，可以經由 RCU 執行 trie_rebalance，以避免在 fn_trie_lookup() 函式中進行 read_lock。

主要查詢機制

fn_trie_lookup() 是主要查詢函式。

最簡單的查詢形式就像 fib_find_node()。 我們逐個鍵段地向下遍歷 trie，直到找到一個葉節點。 check_leaf() 在葉節點的排序字首 hlist 中執行 fib_semantic_match。

如果找到匹配項，我們就完成了。

如果找不到匹配項，我們將進入字首匹配模式。 字首長度從與鍵長度相同開始，一次減少一個步驟，然後我們向上回溯遍歷 trie，嘗試找到最長匹配字首。 目標始終是到達葉節點並從 fib_semantic_match 機制中獲得肯定結果。

在每個 tnode 內部，搜尋最長匹配字首包括搜尋子陣列，砍掉（清零）子索引的最低有效“1”，直到找到匹配項或子索引只包含零。

此時，我們向上回溯（t->stats.backtrack++）遍歷 trie，繼續砍掉鍵的一部分，以便找到最長匹配字首。

此時，我們將重複向下遍歷子 trie 以查詢匹配項，並且有一些最佳化可用，可以為我們提供“快捷方式”以避免進入死衚衕。 在程式碼中尋找 “HL_OPTIMIZE” 部分。

為了減輕對路由選擇過程正確性的任何疑慮，添加了一個新的 netlink 操作。 尋找 NETLINK_FIB_LOOKUP，它為使用者空間提供對 fib_lookup() 的訪問。