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() 的访问。