Linux fib_table_lookup TRIE路由查找前缀匹配

Linux fib_table_lookup TRIE路由查找前缀匹配

fib_table_lookup 是Linux IPv4路由表查找的核心函数，使用LC-Trie（Level-Compressed Trie）数据结构实现最长前缀匹配。该函数位于 net/ipv4/fib_trie.c，负责在路由表中查找与目标IP地址最匹配的条目。

一、 TRIE数据结构的组织

Linux路由表的Trie实现将IPv4地址（32位）组织为两级压缩trie。每个节点对应一个前缀长度范围内的key空间。核心数据结构：

struct key_vector {
t_key key; /* 节点键值 */
t_key pos; /* 当前位的偏移 */
t_key bits; /* 当前节点覆盖的位数 */
struct key_vector *tnode; /* 子节点数组 */
struct leaf *leaf; /* 叶子节点，关联fib_info */
};

struct leaf {
struct key_vector kv;
struct hlist_head list; /* 相同前缀的fib别名链表 */
struct rcu_head rcu;
};

每个内部节点（tnode）的子节点数量由 bits 决定。子节点数组大小为 2^bits。查找时，根据目标地址的 pos 位之后的 bits 位索引子节点。

二、 fib_table_lookup的函数签名

fib_table_lookup 接受流信息（flowi4）作为查询条件，返回最匹配的 fib_result：

int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
struct fib_result *res, int fib_flags)
{
struct trie *t = (struct trie *)tb->tb_data;
struct key_vector *kv;
struct leaf *leaf;
int ret;

/* RCU读锁保护TRIE结构 */
rcu_read_lock();

/* 从根节点开始trie查找 */
kv = rcu_dereference(t->kv);
leaf = fib_find_node(t, &kv, flp->daddr, flp->flowi4_scope);
if (!leaf) {
ret = 1; /* 未找到 */
goto out;
}

/* 在leaf的别名链表中查找匹配的fib_alias */
ret = fib_find_alias(leaf, flp, res, fib_flags);

out:
rcu_read_unlock();
return ret;
}

三、 fib_find_node的Trie遍历

fib_find_node 实现trie的逐级下降查找：

static struct leaf *fib_find_node(struct trie *t, struct key_vector **kv,
__be32 key, u8 scope)
{
struct key_vector *tn, *kvn;
unsigned long bits;

tn = *kv;

/* 从根节点开始遍历 */
while (IS_TNODE(tn)) {
/* 计算在当前节点中的索引 */
bits = (key >> tn->pos) & ((1ul << tn->bits) - 1);

/* 通过索引获取子节点 */
kvn = rcu_dereference(tn->tnode[bits]);
if (!kvn) {
/* 未匹配：回溯到最接近的祖先 */
goto backtrace;
}

tn = kvn;
}

/* 到达叶子节点 */
return (struct leaf *)tn;

backtrace:
/* 回溯查找更短前缀的匹配 */
while (tn && IS_TNODE(tn)) {
/* 检查当前节点是否持有匹配 */
if (tn->leaf) {
*kv = tn;
return tn->leaf;
}
tn = node_parent_rcu(tn);
}
return NULL;
}

在Trie下降过程中，key右移 pos 位后取低 bits 位作为子节点数组索引。如果中间缺失子节点，通过回溯到父节点检查是否有默认路由或更短前缀的匹配。

四、 最长前缀匹配的核心算法

fib_find_alias 在leaf的别名链表中执行最长前缀匹配：

static int fib_find_alias(struct leaf *leaf, const struct flowi4 *flp,
struct fib_result *res, int fib_flags)
{
struct fib_alias *fa, *fa_match = NULL;
u8 plen, tos = flp->flowi4_tos;

/* 遍历该前缀下的所有fib_alias */
hlist_for_each_entry_rcu(fa, &leaf->list, fa_list) {
plen = fa->fa_slen;
tos_match = fa->fa_tos;

/* TOS匹配检查 */
if (tos_match != tos) {
if (fa->fa_info->fib_metrics->metrics[RTAX_INITCWND - 1])
continue;
}

/* scope匹配 */
if (fa->fa_scope != flp->flowi4_scope)
continue;

/* type匹配（RTN_UNICAST, RTN_LOCAL等） */
if (fa->fa_type == RTN_UNREACHABLE ||
fa->fa_type == RTN_BLACKHOLE) {
continue;
}

/* 选择最长前缀 */
if (!fa_match || plen > fa_match->fa_slen)
fa_match = fa;
}

if (fa_match) {
res->prefixlen = fa_match->fa_slen;
res->fi = fa_match->fa_info;
res->type = fa_match->fa_type;
res->scope = fa_match->fa_scope;
return 0;
}
return 1;
}

同一前缀长度下可能有多个fib_alias，区别在tos和scope字段。查找过程优先匹配tos，如果tos不匹配再按最长前缀选择。

五、 插入与删除操作

Trie插入操作维护前缀的层次结构。当插入/24路由时，trie可能分裂内部节点：

static int fib_insert_node(struct trie *t, struct key_vector *tp,
struct fib_alias *new, __be32 key)
{
struct key_vector *n, *l;
int pos, bits;

/* 找到插入位置 */
l = fib_find_node(t, &tp, key, new->fa_scope);
if (l) {
/* 已有对应leaf，直接添加到别名链表 */
hlist_add_head_rcu(&new->fa_list, &l->list);
return 0;
}

/* 需要创建新leaf */
n = leaf_new(key);
if (!n)
return -ENOMEM;

/* 将新leaf插入到trie中 */
if (tp) {
bits = key >> tp->pos & ((1ul << tp->bits) - 1);
rcu_assign_pointer(tp->tnode[bits], n);
} else {
rcu_assign_pointer(t->kv, n); /* 新根节点 */
}

hlist_add_head_rcu(&new->fa_list, &n->leaf->list);
return 0;
}

当Trie中某个内部节点的子节点数量少于阈值时，触发节点合并（collapse）以减少空间占用。

六、 多路径路由与nexthop

当路由表使用多路径（multipath）时，fib_info包含多个nexthop。fib_table_lookup 不直接处理多路径选择，由调用方（如 fib_select_multipath）完成：

int fib_select_multipath(struct fib_result *res, int hash)
{
struct fib_info *fi = res->fi;
int nh_sel;

if (!fib_info_num_path(fi))
return 0;

/* 基于hash选择nexthop */
nh_sel = hash % fib_info_num_path(fi);
change_nexthops(fi) {
if (nh_sel == nh->nh_sel)
break;
} endfor_nexthops(fi);

res->nh_sel = nh_sel;
res->fi = fi;
return 0;
}

哈希值通常由源地址、目的地址和协议端口计算得到，保证同一流始终走同一路径。

七、 sysctl与路由缓存控制

Trie查找的行为可以通过内核参数控制：

net.ipv4.fib_multipath_hash_policy = 0
0: Layer 3 (源/目的IP)
1: Layer 4 (源/目的IP + 源/目的端口)
2: Layer 3+inner (用于隧道场景)

net.ipv4.fib_notify_on_flag_change = 0

sysctl_fib_sync_mem 控制FIB同步内存消耗。

八、 批量路由查找的优化

在路由表中存在大量条目时，fib_table_lookup 使用RCU加速并发读取。当进行 bulk delete 操作时，使用 synchronize_rcu 确保所有读者完成后再释放旧节点：

void fib_trie_delete(struct fib_table *tb, struct fib_config *cfg)
{
/* 逻辑删除：先从leaf链表移除fa */
hlist_del_rcu(&fa->fa_list);

/* 物理删除：等待RCU grace period */
call_rcu(&fa->rcu, fib_alias_destroy);

/* 如果leaf为空，从trie中移除leaf节点 */
if (hlist_empty(&l->list))
fib_leaf_delete(t, l);
}

这种RCU保护下的无锁读取使Linux路由查找在大型路由表（数十万条）下仍能保持高性能。

fib_table_lookup 的实现代表了路由查找从哈希表到Trie的演进。LC-Trie以每个内部节点2^bits的子节点数组换取O(1)的查找复杂度，同时通过节点压缩合并控制内存开销。最长前缀匹配在leaf的别名链表中以线性扫描完成，但由于同一前缀下的别名数量很少，性能开销可控。