LC-trie 实现说明

节点类型

叶节点 (leaf)

带有数据的末端节点。它具有相关键的副本，以及按前缀长度排序的路由表条目的“hlist”。请参阅结构体 leaf 和 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”)。

(这里的“满”这个词更多地用作“完整”的意义，而不是“空”的反义词，这可能会有点令人困惑。)

注释

我们已尽力使代码结构尽可能接近 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() 的访问权限。