第二章·第一节转发信息库 (FIB)

⚠️ 注意

如果您发现了错误，欢迎参与贡献。

📖 本节目录

💡 摘要 (Powered by OpenAI)

本文深入介绍了 BIRD 的转发信息库 (FIB) —— 一种基于两级哈希的路由前缀索引结构，支持 CIDR 查找和在线异步读取。

什么是 FIB

FIB (Forwarding Information Base) 是 BIRD 中一种专为按网络前缀索引存储路由而设计的数据结构。它支持：

插入 (Insertion) 和 删除 (Deletion)
按前缀搜索 (Search by prefix)
CIDR 路由查找 (Routing)：最长前缀匹配，即 CIDR 路由器用于转发数据包的查找方式
异步读取 (Asynchronous reading)：在其他模块同时添加、修改或删除条目时遍历 FIB 内容 —— 这也是实现中最棘手的部分

💡 译者注

FIB 的概念来源于路由器硬件中的"转发信息库"。在软件路由器（如运行 BIRD 的 Linux 服务器）中，FIB 实际上对应 Linux 内核路由表。BIRD 在自己的用户空间进程中维护一份独立的 FIB，然后通过 Kernel 协议与内核同步。这种"双表"架构使得 BIRD 可以在不影响内核转发的前提下灵活操作路由。

两级哈希机制

在内部，每个 FIB 被表示为一系列 fib_node 类型节点的集合，使用精心设计的两级哈希机制进行索引：

第一级：计算一个与哈希表大小无关的 16 位主哈希键
第二级：将主键对表大小取模，得出用于确定节点所在桶的真实哈希键

每个桶中的节点链表按主哈希键排序。这意味着如果将桶总数保持为 2 的幂，在重哈希 (re-hash) 时能保持节点的相对顺序，避免大规模数据迁移。

💡 译者注

两级哈希设计是 BIRD 的一个精巧优化。第一级主哈希键独立于表大小，意味着当哈希表扩容（桶数量翻倍）时，只需将节点按主键重新分配到新桶，而每个桶内部的排序关系不变。这种设计避免了传统哈希表扩容时需要重新计算所有哈希值的开销。

异步读取一致性

FIB 最棘手的特性是允许在线修改的同时进行读取遍历。实现方式：

每个节点维护一个读取者链表 (list of readers)
当节点被删除时，其所有读取者自动转移到表中的下一个节点
这样遍历操作永远不会丢失进度或访问已释放的内存

迭代方式

简单迭代 (FIB_WALK 宏)：

FIB_WALK(f, node) {
    // 只能修改节点内部数据
    // 不能添加或删除节点
}
FIB_WALK_END;

异步迭代 (FIB_ITERATE 系列宏)：

struct fib_iterator it;
FIB_ITERATE_INIT(&it, f);

// 开始迭代
FIB_ITERATE_START(f, &it, node) {
    FIB_ITERATE_PUT(&it);  // 暂停迭代
    // 此时可以安全修改 FIB、退出函数等
    // 稍后重新进入循环即可恢复迭代
}
FIB_ITERATE_END;
FIB_ITERATE_UNLINK(&it);  // 提前结束

⚠️ 重要约束

迭代器在暂停状态时绝对不能销毁，否则 FIB 中将包含指向无效内存的指针。每次 FIB_ITERATE_INIT() 或 FIB_ITERATE_PUT() 后，在迭代器销毁前必须调用 FIB_ITERATE_START() 或 FIB_ITERATE_UNLINK()。

核心 API

函数	签名	说明
`fib_init`	`(f, p, addr_type, node_size, node_offset, hash_order, init)`	初始化新 FIB 结构
`fib_find`	`(f, a) → void*`	按前缀搜索节点，未找到返回 `NULL`
`fib_get`	`(f, a) → void*`	查找或自动创建节点
`fib_route`	`(f, n) → void*`	CIDR 路由查找：最长前缀匹配
`fib_delete`	`(f, E)`	删除节点并转移所有异步读取者
`fib_free`	`(f)`	释放整个 FIB 及其所有节点
`fib_check`	`(f)`	审计内部一致性（仅调试用）

本文译者及原文信息

Hat

译者

展开原文属性

原文作者： <Ondrej Filip>, <Martin Mares>, <Maria Matejka>, <Ondrej Zajicek>

原文链接： https://bird.network.cz/?get_doc&v=20&f=prog-2.html#ss2.1

原文标题： 2.1 Forwarding Information Base

展开译文属性

遵循协议： CC BY-NC-SA 4.0

译者： hat

翻译时间： 2026-05-01

更新时间： 2026-05-01

本文链接： https://bird.xmsl.dev/docs/developer-guide/2-1-fib.html

第二章·第一节 转发信息库 (FIB) ​

什么是 FIB ​

两级哈希机制 ​

异步读取一致性 ​

迭代方式 ​

核心 API ​

本文译者及原文信息 ​

Hat