Linux 路由子系统深度分析：框架、实现与代码路径

Linux 路由子系统深度分析：框架、实现与代码路径

一、路由子系统核心框架

+-----------------------+
|     用户空间工具       |
|   (iproute2, net-tools) |
+----------+------------+| Netlink (RTM)v
+-----------------------+
|     Netlink 接口      |<---------------------------------+
| (rtnetlink, fib_netns_ops) |                             |
+----------+------------+                             ||                                         || 路由配置管理                             |v                                         |
+----------------------+                              |
|  路由表管理子系统     |                              |
| (fib_frontend.c)     |--+                           |
| - fib_table_insert   |  |                           |
| - fib_table_delete   |  |                           |
+----------+-----------+  |                           ||              | 路由规则通知               || 路由规则操作   v                           |
+----------+-----------+  +----------------------+     |
|  路由策略数据库 (RPDB) |<->| FIB通知机制 (fib_notifier) |
| (fib_rules.c)        |  +----------------------+     |
| - fib_rules_lookup   |                             |
| - fib_default_rule_add|                             |
+----------+------------+                             || 策略匹配                                  |v                                         |
+----------------------+                              |
|  转发信息库 (FIB)    |<-----------------------------+
| (fib_trie.c)         |
| - fib_find_node      |
| - fib_table_lookup   |
+----------+-----------+| LPM查找v
+----------------------+
|  路由条目 (fib_info) |
| (fib_semantics.c)    |
| - fib_create_info    |
| - fib_release_info   |
+----------+-----------+| 下一跳信息v
+----------------------+    +----------------------+
|  下一跳 (fib_nh)     +--->|  目的地缓存 (dst_entry) |
| - nh_dev, nh_gw      |    | - input, output      |
+----------------------+    +----------+-----------+| 关联v+----------------------+|  邻居子系统 (neighbour) || - neigh_output       || - neigh_resolve_output|+----------------------+

好的，我们来对 Linux 网络子系统中极其关键的 路由子系统 进行一个详细深入的分析，涵盖其框架设计和核心实现机制。

路由子系统核心任务： 确定进入内核网络栈的数据包（无论是本地生成还是从网络接口接收）的下一跳（Next Hop），即决定数据包应该从哪个网络接口发出、发往哪个网关（或直接发给目标主机）以及使用哪个源 IP 地址。它是实现 IP 协议“无连接”、“尽力而为”转发的基础。

二、 路由子系统核心框架与组件

路由子系统采用了分层和模块化的设计，主要包含以下几个核心部分：

1. 路由缓存 (Route Cache) - 历史组件 (已移除)：

   • 历史作用： 早期内核（2.6 时代及之前）为了提高性能，会将最近成功查找的路由结果（struct rtable）缓存起来。缓存基于源/目的 IP、TOS、入接口等键值进行哈希查找，速度极快。
   • 问题与移除： 随着连接跟踪（Netfilter Conntrack）的成熟和广泛应用，以及路由查找算法本身的优化（如 LPC-trie），路由缓存的维护开销（失效、同步）超过了其带来的性能收益，且在 DoS 攻击下表现不佳。现代内核（3.6+）已完全移除了路由缓存。查找现在总是基于 Forwarding Information Base (FIB)。

2. 转发信息库 (FIB - Forwarding Information Base)：

   • 核心数据平面： FIB 是路由子系统的核心数据结构，它存储了内核当前使用的所有有效路由规则。它代表了内核的“路由表”。
   • 数据结构演进： 早期使用简单的哈希表。现代内核（2.6+）主要使用基于 LC-trie (Level Compressed trie) 算法的数据结构 struct fib_table。这是一种高度优化的前缀树（trie），专门为快速 最长前缀匹配 (Longest Prefix Match - LPM) 设计，这是 IP 路由查找的核心算法。
   • 多 FIB 表支持： Linux 支持多个路由表（默认最多 255 个）。每个表由唯一的数字 ID 标识。最常用的是：
     • RT_TABLE_LOCAL (255)： 本地接口地址和广播地址（内核自动管理）。
     • RT_TABLE_MAIN (254)： 默认表，用户通过 ip route 添加的路由通常放在这里。
     • RT_TABLE_DEFAULT (253)： 通常为空。
     • 其他表（0-252）可用于策略路由。
   • fib_lookup： 这是执行 LPM 查找的核心函数。给定目标 IP 地址，它在指定的 FIB 表中查找最具体的匹配路由条目。

3. 路由策略数据库 (RPDB - Routing Policy Database)：

   • 控制平面决策器： RPDB 定义了如何选择使用哪个路由表来进行查找。它提供了基于策略的路由功能。
   • struct fib_rule： 策略规则的核心结构。每条规则定义了：
     • 优先级 (r_priority)： 数字越小，优先级越高。
     • 选择器 (r_prefsrc, r_src, r_dst, r_tos, r_iif, r_oif, r_fwmark, r_table 等)： 基于源 IP、目的 IP、TOS、入接口、出接口、防火墙标记（fwmark）等条件匹配数据包。
     • 动作 (r_action)： 最常见的是 FR_ACT_TO_TBL，表示如果规则匹配，则使用规则指定的路由表（r_table）进行 FIB 查找。其他动作包括 FR_ACT_UNREACHABLE, FR_ACT_BLACKHOLE, FR_ACT_PROHIBIT 等。
     • r_src_len, r_dst_len： 源/目的地址的网络掩码长度。
   • 查找过程 (fib_rules_lookup)： 当需要进行路由决策时，内核按优先级顺序遍历 RPDB 中的所有规则。一旦找到第一条匹配当前数据包属性（源 IP、目的 IP、入接口、fwmark 等）的规则，就执行该规则指定的动作（通常是去指定的路由表中进行 FIB 查找）。如果没有任何规则匹配，通常使用 RT_TABLE_MAIN。

4. 路由条目 (struct fib_info)：

   • 这是 FIB 查找结果的具体表示。它包含了执行路由决策所需的所有关键信息：
     • 前缀 (fib_dst, fib_prefsrc)： 路由的目标网络和掩码长度，以及建议使用的源 IP 地址（通常用于多宿主主机）。
     • 类型 (fib_type)： 路由类型（RTN_UNICAST - 单播, RTN_LOCAL - 本地, RTN_BROADCAST, RTN_MULTICAST, RTN_BLACKHOLE, RTN_UNREACHABLE, RTN_PROHIBIT 等）。
     • 范围 (fib_scope)： 路由的有效范围（RT_SCOPE_UNIVERSE - 全局有效, RT_SCOPE_LINK - 仅在同一链路上有效, RT_SCOPE_HOST - 仅本机有效）。
     • 下一跳信息 (struct fib_nh)： 这是最关键的部分！ 一个 fib_info 可能包含多个 fib_nh（下一跳）结构，用于支持多路径路由 (ECMP)。每个 fib_nh 包含：
       • nh_dev： 指向输出网络设备 (struct net_device) 的指针。
       • nh_gw： 网关的 IP 地址（如果路由是间接的）。对于直连路由，这个字段为 0。
       • nh_weight： 权重（用于加权 ECMP）。
       • nh_flags： 标志位（如 RTNH_F_ONLINK - 网关在本地链路上）。
     • 关联的邻居条目 (nh_pcpu_rth_output)： 指向下一跳对应的邻居子系统条目（struct neighbour 或 struct dst_entry），该条目存储了网关（或目的主机）的链路层地址（MAC 地址）以及输出函数指针。这建立了路由子系统与邻居子系统之间的桥梁。
     • 引用计数 (fib_clntref)： 管理该结构生命周期的引用计数。
     • 度量值 (fib_priority)： 路由优先级（在相同前缀长度下，值越小优先级越高）。
   • struct fib_result： FIB 查找函数 (fib_lookup) 的返回值。它包含了指向匹配的 fib_info 的指针以及一些额外的查找信息（如路由表 ID、规则类型等）。

5. 目的地缓存 (struct dst_entry)：

   • 路由结果的封装与输出接口： 这是路由查找的最终产物，也是网络栈后续处理（特别是输出路径）的关键对象。
   • 关键成员：
     • __refcnt： 引用计数。
     • dev： 输出网络设备。
     • _metrics： 路由度量值（如 MTU、RTT 等）。
     • flags： 标志位。
     • lastuse： 上次使用时间戳。
     • input, output： 关键函数指针！ 定义了如何处理指向该目的地的数据包。
       • input： 通常用于输入路径，指向处理本地投递或转发的函数（如 ip_local_deliver 或 ip_forward）。
       • output： 用于输出路径，指向实际执行数据包发送的函数。这个函数通常是通过邻居子系统解析链路层地址后设置的（如 neigh_output）。在路由查找刚完成时，它可能指向一个通用的输出函数（如 ip_output），该函数会触发邻居子系统的处理。
     • neighbour： 指向对应的邻居条目 (struct neighbour)。这是路由子系统与邻居子系统紧密协作的关键点。output 函数最终会调用 neighbour->output（例如 neigh_resolve_output 或 dev_queue_xmit）来发送数据包。
   • struct rtable： 这是 IPv4 特定的 dst_entry 子类型，包含了 IPv4 特有的信息，如源/目的 IP 地址、TOS、路由标记等。

6. 邻居子系统 (Neighbour Subsystem - ARP/ND)：

   • 紧密集成： 路由子系统确定了下一跳的 IP 地址（网关或目标主机）和输出接口。邻居子系统负责将该 IP 地址解析为对应的链路层地址（如以太网 MAC 地址）。
   • struct neighbour： 代表一个邻居（同一链路上的主机或路由器）。它存储了链路层地址、状态（NUD_NONE, NUD_INCOMPLETE, NUD_REACHABLE, NUD_STALE 等）以及输出函数指针 (output)。
   • 交互流程：
     1. 路由查找得到 dst_entry (如 rtable)。
     2. 内核通过 dst->output (初始可能是 ip_output 或 ip6_output) 尝试发送数据包。
     3. ip_output 会调用 dst_neigh_output。
     4. dst_neigh_output 会获取或创建与 dst_entry 关联的 neighbour 条目。
     5. 根据 neighbour 的状态，调用其 output 方法：
        • 如果状态是 NUD_REACHABLE，直接调用 neigh->ops->queue_xmit（最终通常是 dev_queue_xmit 将包放入设备队列）。
        • 如果状态是 NUD_NONE 或 NUD_STALE，则调用 neigh_resolve_output。该函数会检查是否需要发送 ARP 请求（IPv4）或 Neighbor Solicitation（IPv6）。如果需要，它会缓存数据包（到 neigh->arp_queue）并启动地址解析过程。解析成功后，状态变为 NUD_REACHABLE，缓存的包会被发送。
        • 如果状态是 NUD_FAILED，通常会导致发送失败。

三、 路由查找流程详解（以 IPv4 接收转发为例）

1. 数据包接收： 网卡驱动通过 NAPI 将数据包放入接收队列，软中断 NET_RX_SOFTIRQ 触发 net_rx_action。
2. 协议处理 (ip_rcv)： 网络层处理函数 ip_rcv 被调用，进行基本的 IP 头校验。
3. 路由决策入口 (ip_route_input_noref / ip_route_input_rcu):
   • 这是输入路径路由查找的入口函数。主要任务：确定包是发给本机的 (INPUT)、需要转发的 (FORWARD)、还是广播/组播的。
   • 关键步骤：
     • 检查目的地址是否是本地地址？ 查 local 表 (RT_TABLE_LOCAL)。如果找到类型为 RTN_LOCAL 的路由，则包是发给本机的。
     • 检查是否开启转发 (net->ipv4.ip_forward)? 如果没开启，且包不是发给本机的，则丢弃并回复 ICMP 目的不可达。
     • 执行 RPDB 查找 (fib_rules_lookup)： 使用数据包的属性（源 IP、目的 IP、入接口、TOS、fwmark 等）遍历路由策略规则。
     • FIB 查找 (fib_lookup): 根据 RPDB 规则选定的路由表（通常是 main 表）进行最长前缀匹配查找，得到 fib_result。
     • 构建 dst_entry (rt_dst_alloc)： 基于 fib_result 创建一个 struct rtable (IPv4 的 dst_entry)。设置关键字段：
       • rtable->dst.input： 设置为 ip_forward（用于转发）或 ip_local_deliver（用于本机，但这一步通常在查 local 表时已确定）。
       • rtable->dst.output： 初始通常设置为 ip_output（对于本机生成或转发的包，后续邻居子系统会替换它）。
       • rtable->rt_gateway： 下一跳 IP（网关地址或目的地址）。
       • rtable->rt_dev： 输出设备（来自 fib_nh）。
       • rtable->rt_route_iif： 输入设备。
     • 关联邻居： 隐含地为这个 rtable 初始化了邻居关联（后续输出时具体解析）。
4. 设置 skb 目的地 (skb_dst_set)： 将创建的 rtable（作为 dst_entry）关联到 sk_buff (skb->dst)。
5. 后续处理： 根据 dst->input 函数指针调用相应的处理函数：
   • 如果是 ip_local_deliver： 数据包进入本机上层协议栈（TCP/UDP/ICMP 等）。
   • 如果是 ip_forward： 执行转发逻辑（TTL 减 1，处理选项，分片等），然后调用 dst_output(skb)。
6. 输出路径 (dst_output -> skb_dst(skb)->output(skb)):
   • 这会调用 rtable->dst.output，通常是 ip_output。
   • ip_output 处理可能的 IP 选项，然后调用 ip_finish_output。
   • ip_finish_output 处理可能的分片，然后调用 ip_finish_output2。
   • ip_finish_output2 调用 dst_neigh_output。
   • dst_neigh_output 获取或创建与 rtable->rt_gateway 对应的邻居条目 (struct neighbour)，并调用 neigh_output。
   • neigh_output 根据邻居条目的状态 (neigh->nud_state) 调用其 output 方法：
     • NUD_CONNECTED/NUD_REACHABLE： 直接调用 neigh->ops->queue_xmit (最终调用 dev_queue_xmit 将包放入网卡发送队列)。
     • 其他状态 (NUD_INCOMPLETE, NUD_STALE, NUD_DELAY, NUD_PROBE): 调用 neigh_resolve_output，该函数负责处理 ARP/ND 解析（可能发送请求并缓存数据包），解析成功后发送包。

四、核心组件实现机制

1. 路由策略数据库 (RPDB)

数据结构：

// 策略规则定义
struct fib_rule {u32             priority;      // 优先级（值越小优先级越高）u32             table;         // 目标路由表IDu8              action;        // 动作类型u8              l3mdev;        // L3主设备标志u32             flags;         // 规则标志u32             fwmark;        // 防火墙标记u32             fwmask;        // 防火墙掩码__be32          src;           // 源地址__be32          dst;           // 目的地址u8              src_len;       // 源地址长度u8              dst_len;       // 目的地址长度
};

策略匹配流程：

// net/ipv4/fib_rules.c
int fib_rules_lookup(struct fib_rules_ops *ops, struct flowi *fl, int flags,struct fib_lookup_arg *arg)
{struct fib_rule *rule;list_for_each_entry(rule, &ops->rules_list, list) {if (!fib_rule_match(rule, ops, fl, flags))continue;if (rule->action == FR_ACT_GOTO) {// 跳转到其他规则链} else if (rule->action == FR_ACT_TO_TBL) {// 使用指定路由表err = ops->action(rule, fl, flags, arg);if (err != -EAGAIN)return err;}}return -ESRCH; // 未匹配
}

2. 转发信息库 (FIB)

数据结构：

// 路由表结构
struct fib_table {struct hlist_node   tb_hlist;   // 哈希链表u32                 tb_id;      // 表IDunsigned            tb_num_default; // 默认路由数量struct rcu_head     rcu;        // RCU保护struct trie         __rcu *tb_trie; // LC-trie树根
};// LC-trie节点结构
struct tnode {t_key key;                      // 键值unsigned long pos;              // 位位置struct tnode __rcu *parent;     // 父节点struct tnode __rcu *child[0];   // 子节点
};

LPM查找算法：

// net/ipv4/fib_trie.c
static struct key_vector *fib_find_node(struct trie *t, struct key_vector **tp,u32 key)
{struct key_vector *n, *pn;unsigned long index;pn = t->kv;n = get_child(pn, 1);while (n) {if (index >= n->key && index <= n->key + n->pos) {*tp = pn;return n;}pn = n;n = get_child_rcu(n, get_index(key, n));}return NULL;
}

3. 目的地缓存 (dst_entry)

核心结构：

struct dst_entry {struct net_device       *dev;     // 输出设备unsigned long           _metrics; // 路由度量unsigned long           expires;  // 过期时间struct neighbour __rcu  *neighbour; // 邻居条目int               (*input)(struct sk_buff *);  // 输入处理函数int               (*output)(struct net *, struct sock *, struct sk_buff *); // 输出处理函数
};// IPv4专用路由缓存
struct rtable {struct dst_entry    dst;__be32              rt_key_dst;   // 目的地址__be32              rt_key_src;   // 源地址__be32              rt_gateway;   // 网关地址u8                  rt_type;      // 路由类型
};

4. 邻居子系统集成

路由到邻居的转换：

// net/ipv4/ip_output.c
static int ip_finish_output2(struct net *net, struct sock *sk, struct sk_buff *skb)
{struct dst_entry *dst = skb_dst(skb);struct rtable *rt = (struct rtable *)dst;struct neighbour *neigh;// 获取邻居条目neigh = __ipv4_neigh_lookup_noref(dst->dev, rt->rt_gateway);if (unlikely(!neigh))neigh = __neigh_create(&arp_tbl, &rt->rt_gateway, dst->dev, false);// 通过邻居子系统发送return neigh_output(neigh, skb);
}

五、核心路径代码分析

1. 输入路径路由 (ip_route_input)

// net/ipv4/route.c
int ip_route_input_noref(struct sk_buff *skb, __be32 daddr, __be32 saddr,u8 tos, struct net_device *dev)
{struct fib_result res;struct flowi4 fl4;// 初始化流信息memset(&fl4, 0, sizeof(fl4));fl4.flowi4_iif = dev->ifindex;fl4.daddr = daddr;fl4.saddr = saddr;fl4.flowi4_tos = tos;// 策略路由查找if (fib_rules_lookup(net->ipv4.rules_ops, flowi4_to_flowi(&fl4), 0, &res))goto no_route;// 创建路由缓存rth = rt_dst_alloc(dev_net(dev), flags);if (!rth)goto e_nobufs;// 设置路由属性rth->dst.input = ip_forward;rth->dst.output = ip_output;rth->rt_key_dst = daddr;rth->rt_gateway = res.fi->fib_nh[0].nh_gw;// 关联到skbskb_dst_set(skb, &rth->dst);return 0;
}

2. 输出路径路由 (__ip_route_output_key)

// net/ipv4/route.c
struct rtable *__ip_route_output_key(struct net *net, struct flowi4 *fl4)
{struct fib_result res;// 策略路由查找if (fib_rules_lookup(net->ipv4.rules_ops, flowi4_to_flowi(fl4), 0, &res))return ERR_PTR(-ENETUNREACH);// 创建路由缓存rth = rt_dst_alloc(out_dev, flags);rth->rt_key_dst = fl4->daddr;rth->rt_key_src = fl4->saddr;// 设置输出函数rth->dst.output = ip_output;// 多路径路由处理if (res.fi->fib_nhs > 1 && fl4->flowi4_oif == 0)fib_select_multipath(&res, hash);return rth;
}

3. FIB更新操作 (fib_table_insert)

// net/ipv4/fib_trie.c
int fib_table_insert(struct net *net, struct fib_table *tb,struct fib_config *cfg, struct netlink_ext_ack *extack)
{struct trie *t = (struct trie *)tb->tb_data;struct fib_alias *fa, *new_fa;// 查找插入位置l = fib_find_node(t, &tp, key);// 创建新条目new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);new_fa->fa_info = fi;new_fa->fa_tos = cfg->fc_tos;new_fa->fa_type = cfg->fc_type;// 插入到trie树if (!l) {// 创建新叶子节点l = leaf_new(key);insert_leaf(t, tp, l);}// 添加到别名列表hlist_add_head_rcu(&new_fa->fa_list, &l->leaf);// 通知路由变更rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, cfg, NLM_F_CREATE);
}

六、关键机制实现细节

1. 多路径路由 (ECMP)

// net/ipv4/fib_semantics.c
void fib_select_multipath(struct fib_result *res, int hash)
{struct fib_info *fi = res->fi;u32 w;for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {struct fib_nh *nh = &fi->fib_nh[nhsel];// 计算权重w = nh->nh_weight;if (w == 0)continue;// 哈希选择路径if (hash <= atomic_read(&nh->nh_upper_bound)) {res->nh_sel = nhsel;return;}hash -= atomic_read(&nh->nh_upper_bound);}
}

2. 邻居子系统集成

// net/core/neighbour.c
int neigh_output(struct neighbour *n, struct sk_buff *skb)
{// 根据邻居状态选择输出函数if (n->nud_state & NUD_CONNECTED)return n->output(n, skb);  // 直接发送elsereturn neigh_resolve_output(n, skb); // 需要解析
}int neigh_resolve_output(struct neighbour *neigh, struct sk_buff *skb)
{// 发送ARP请求if (!(neigh->nud_state & (NUD_STALE | NUD_INCOMPLETE))) {neigh->ops->solicit(neigh, skb);__skb_queue_tail(&neigh->arp_queue, skb);return 0;}// 已解析，直接发送return neigh->ops->output(neigh, skb);
}

七 、性能优化机制

1. RCU锁优化

// FIB查找使用RCU保护
static struct key_vector *fib_find_node(struct trie *t, struct key_vector **tp, u32 key)
{struct key_vector *pn, *n;rcu_read_lock();pn = t->kv;n = rcu_dereference(pn->tnode[0]);...rcu_read_unlock();
}

2. 路由缓存优化（历史）

// 旧版路由缓存（3.6之前）
struct rt_hash_bucket {struct rtable    *chain;
};// 缓存查找（已移除）
static inline struct rtable *rt_hash_result(u32 saddr, u32 daddr, int iif)
{unsigned int hash = rt_hash_code(saddr, daddr, iif);struct rtable *rth = rt_hash_table[hash].chain;while (rth) {if (rth->fl.fl4_src == saddr &&rth->fl.fl4_dst == daddr &&rth->fl.iif == iif)return rth;rth = rth->u.dst.rt_next;}return NULL;
}

八、诊断工具与调试接口

1. /proc 文件系统接口

# 查看路由表
cat /proc/net/route# 查看FIB统计
cat /proc/net/stat/rt_cache# 查看路由策略
cat /proc/net/rt_acct

2. ftrace 跟踪点

# 启用路由跟踪点
echo 1 > /sys/kernel/debug/tracing/events/fib/enable
echo 1 > /sys/kernel/debug/tracing/events/neigh/enable# 查看跟踪结果
cat /sys/kernel/debug/tracing/trace_pipe

九、总结架构图

+-------------------+     +-------------------+     +-------------------+
|  用户空间配置工具   |     |   网络协议栈        |     |    网络设备驱动     |
| (ip route add/del) |     | (TCP/UDP/ICMP)    |     | (驱动收发包队列)     |
+---------+---------+     +---------+---------+     +---------+---------+| Netlink                 |                        |v                         v                        v
+-------------------+     +-------------------+     +-------------------+
|  Netlink 子系统    |     |   IP 路由入口      |     |  邻居子系统ARP/ND   |
| (处理RTM_NEWROUTE) |     | (ip_route_input)  |     | (MAC地址解析)       |
+---------+---------+     +---------+---------+     +---------+---------+|                         |                        |v                         v                        |
+-------------------+     +-------------------+              |
|  路由策略数据库 RPDB |     |  路由缓存 dst_entry |<----------+
| (策略路由选择)       |     | (输入/输出函数指针)  |
+---------+---------+     +---------+---------+|                         |v                         v
+-------------------+     +-------------------+
|  转发信息库 FIB     |     |  多路径路由ECMP    |
| (LC-trie实现LPM)    |     | (流量负载均衡)      |
+-------------------+     +-------------------+

关键实现要点：

1. 分层架构：用户空间→Netlink→RPDB→FIB→dst_entry→邻居子系统
2. 高性能查找：LC-trie实现O(log n)复杂度LPM查找
3. 策略路由：RPDB支持基于源/目的地址、防火墙标记等多维路由
4. 无缝集成：dst_entry通过input/output函数指针连接网络栈各层
5. 动态更新：RCU保护实现路由表无锁更新
6. 多路径支持：ECMP实现流量负载均衡和高可用

路由子系统通过高度模块化的设计和精密的算法实现，在保证功能灵活性的同时，提供了接近线速的转发性能，是现代Linux网络栈的核心基础设施。