TCP/IP协议栈-ipv4路由选择子系统

TCP/IP协议栈-ipv4路由选择子系统

本篇文章主要介绍以下内容:

  1. 路由选择表
  2. 转发信息库(Forwarding Information Base,FIB)
  3. FIB别名
  4. FIB TRIE

转发和FIB

linux网络协议栈最重要的目标之一就是转发流量,对于Internet骨干中的核心路由器来说更是如此。Linux IP栈层被称为路由选择子系统,负责转发数据包和维护转发数据库。路由选择就是根据路由表将接收到的数据包进行定向转发的的过程。在这个过程中,来到转发路由器的数据包经过网络协议栈的L2(数据链路层)到L3(网络层),无需将数据移到L4(传输层),而是直接转发,数据直接出栈或者丢弃。数据到达L4是需要性能开销的,所以进行路由选择和转发的机制,是可以有效提升网络性能。

默认网关和默认路由。在路由选择表中不与其他路由选择条目匹配的数据包都将转发到默认网关。在无类域间路由选择(CIDR)表示法时,默认路由用0.0.0.0/0表示。

设置默认网络命令如下:

ip route add default 192.168.1.1

设备和主机发送包的路由通过路由表和路由缓存来实现的。每个数据包,无论是接收还是发送,都需要在路由子系统中执行一次查找操作。根据路由子系统查找结果,决定是否应对数据包进行转发以及该从哪个接口发送出去。

在路由选择子系统中进行查找

我在上一篇介绍ipv4协议时,在谈到ip_rcv_finish时,有以下的注释:

当时并没有细讲这个ip_route_input_noref的函数,现在仔细追踪一下源码。

查找包含两个阶段:首先在路由选择缓存中查找;如果没找到,再在路由选择表中查找。查找方法由fib_lookup完成。
如果在路由选择子系统中找到了匹配的条目,方法fib_lookup将创建一个包含各种路由选择参数的fib_result对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static inline int fib_lookup(struct net *net, const struct flowi4 *flp,
struct fib_result *res)
{
struct fib_table *table;

table = fib_get_table(net, RT_TABLE_LOCAL);
if (!fib_table_lookup(table, flp, res, FIB_LOOKUP_NOREF))
return 0;

table = fib_get_table(net, RT_TABLE_MAIN);
if (!fib_table_lookup(table, flp, res, FIB_LOOKUP_NOREF))
return 0;
return -ENETUNREACH;
}

到了这个地方,我们先不往下继续追踪代码,先来分析下面几个数据结构:

rtable

flowi4

这两个数据结构的介绍见TCP/IP协议栈-ipv4

fib_result

1
2
3
4
5
6
7
8
9
10
struct fib_result {
unsigned char prefixlen;
unsigned char nh_sel;
unsigned char type;
unsigned char scope;
u32 tclassid;
struct fib_info *fi;
struct fib_table *table;
struct list_head *fa_head;
};
参数 解释
prefixlen 前缀长度,表示子网掩码,其值取0-32。使用默认路由,其值为0;使用命令ip route add 192.168.2.0/24 dev eth0 添加路由选择时,其值24,这是根据添加路由选择条目时指定的子网掩码决定的。在check_leaf中设置
nh_sel 下一跳数量。只有一个时为0;使用多径路由选择时,可能存在多个下一跳
type 最重要的一个参数,它决定处理数据包的方式。转发、接收、丢弃等。常见的type类型有RTN_BROADCAST和RTN_LOCAL。
fi 一个指向fib_info的指针,fib_info对象存储指向下一跳的引用
table 指针指向用于查找的FIB表
fa_head 指针质量fib_alias列表,旨在优化路由选择条目

fib_table

1
2
3
4
5
6
7
struct fib_table {
struct hlist_node tb_hlist;
u32 tb_id;
int tb_default;
int tb_num_default;
unsigned long tb_data[0];
};
  • tb_id:路由选择表标识符。对于主表,tb_id为254(RT_TABLE_MAIN);对于本地表,tb_id为255(RT_TABLE_LOCAL)。
  • the_num_default:表中包含的默认路由数。fib_trie_tablethe_num_default初始化为0。fib_table_insert将此值加1,fib_table_delete将此值减1。
  • tb_data[0]:路由选择条目占位符

    从本地地址中查找成功说明封包要提交给自己,系统表用于所有其他路由,可以由系统管理员配置或路由协议动态插入。当封包与表中的某条路由相匹配时,默认动作是从路由表得到该路由的转发信息,除此之外,还可以有动作:黑洞(Black hole)、不可到达(Unreachable)、禁止(Prohibit)、放弃(Throw).

fib_info

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct fib_info {
struct hlist_node fib_hash;
struct hlist_node fib_lhash;
struct net *fib_net; //网络命名空间
int fib_treeref;
atomic_t fib_clntref;
unsigned int fib_flags;
unsigned char fib_dead;
unsigned char fib_protocol; //路由的路由选择协议标识符
unsigned char fib_scope; //目标地址的范围
unsigned char fib_type; //路由的类型
__be32 fib_prefsrc;
u32 fib_priority; //路由优先级
u32 *fib_metrics;
#define fib_mtu fib_metrics[RTAX_MTU-1]
#define fib_window fib_metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics[RTAX_ADVMSS-1]
int fib_nhs;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int fib_power;
#endif
struct rcu_head rcu;
struct fib_nh fib_nh[0];
#define fib_dev fib_nh[0].nh_dev
};

缓存

缓存路由选择查找结果是一种优化技术,可以用于改善路由选择子系统的性能。路由选择查找结果缓存在下一跳对象fib_nh中。是缓存寻找结果。查找的结果缓存在下一跳对象fib_nh中。在接收和传输路径中,缓存fib_result工作都由方法rt_cache_route完成。不同于路由选择缓存,路由选择已在3.6中从协议栈删除了。

在接收路径和传输路径中进行缓存的过程如下:

  • 在接收路径中,通过设置下一跳对象(fib_nh)的nh_rth_input字段,将fib_result对象缓存到下一跳对象(fib_nh)中
  • 在传输路径中,通过设置下一跳对象(fib_nh)的nh_pcpu_rth_output字段,将fib_result对象缓存到下一跳对象(fib_nh)中
  • nh_rth_inputnh_pcpu_rth_output都是结构体rtable的实例
  • 在传输和接收路径中,缓存fib_result的工作是由方法rt_cache_route完成的
  • 缓存路径MTUICMPv4重定向的工作是使用FIB例外实现的

下一跳

当目的网络和本地主机不是直连时,需要通过其他路由器进行转发。选择下一跳的算法有:随机算法,加权随机算法,循环法,设备循环算法。结构体fib_nh表示下一跳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct fib_nh {
struct net_device *nh_dev; //外出网络设备
struct hlist_node nh_hash;
struct fib_info *nh_parent;
unsigned int nh_flags;
unsigned char nh_scope; //范围
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int nh_weight;
int nh_power;
#endif
#ifdef CONFIG_IP_ROUTE_CLASSID
__u32 nh_tclassid;
#endif
int nh_oif; //外出接口索引
__be32 nh_gw;
__be32 nh_saddr;
int nh_saddr_genid;
struct rtable __rcu * __percpu *nh_pcpu_rth_output;
struct rtable __rcu *nh_rth_input;
struct fnhe_hash_bucket *nh_exceptions;
};

ICMPv4重定向消息

有时候路由选择条目可能是次优的,在这种情况下,需要发送ICMPv4重定向消息。

有四种重定向消息代码:

1
2
3
4
5
/* Codes for REDIRECT. */
#define ICMP_REDIR_NET 0 /* Redirect Net */
#define ICMP_REDIR_HOST 1 /* Redirect Host */
#define ICMP_REDIR_NETTOS 2 /* Redirect Net for TOS */
#define ICMP_REDIR_HOSTTOS 3 /* Redirect Host for TOS */

在方法ip_forward中,通过调用方法ip_rt_send_redirect来发送ICMPv4重定向消息。

路由协议守护进程

可以根据三种方式将路由插入到内核的路由表:

  • 通过用户命令静态配置,如ip route,route
  • 通过路由协议,如边界网管协议BGP,外部网管协议RGP,开放式最短路径有限OSPF协议等。协议的用户空间路由守护进程。
  • 内核接收和处理的ICMP重定向消息

路由协议和内核之间的通信是双向的。

路由子系统初始化

路由子系统初始化始于ip_rt_init函数,位于文件net/ipv4/route.c。该函数通过ip_init调用。

ip_rt_init会调用ip_fib_init来初始化fib表。因为路由子系统关心网络设备状态的变化和网络设备上IP配置的变化,所以在ip_fib_init中订阅了两个事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int __init ip_rt_init(void)
{
int rc = 0;

#ifdef CONFIG_IP_ROUTE_CLASSID
ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct), __alignof__(struct ip_rt_acct));
if (!ip_rt_acct)
panic("IP: failed to allocate ip_rt_acct\n");
#endif

ipv4_dst_ops.kmem_cachep =
kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);

ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;

if (dst_entries_init(&ipv4_dst_ops) < 0)
panic("IP: failed to allocate ipv4_dst_ops counter\n");

if (dst_entries_init(&ipv4_dst_blackhole_ops) < 0)
panic("IP: failed to allocate ipv4_dst_blackhole_ops counter\n");

ipv4_dst_ops.gc_thresh = ~0;
ip_rt_max_size = INT_MAX;

devinet_init();
ip_fib_init();

if (ip_rt_proc_init())
pr_err("Unable to create route proc files\n");
#ifdef CONFIG_XFRM
xfrm_init();
xfrm4_init();
#endif
rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL, NULL);

#ifdef CONFIG_SYSCTL
register_pernet_subsys(&sysctl_route_ops);
#endif
register_pernet_subsys(&rt_genid_ops);
register_pernet_subsys(&ipv4_inetpeer_ops);
return rc;
}

void __init ip_fib_init(void)
{
//创建了3张路由表
rtnl_register(PF_INET, RTM_NEWROUTE, inet_rtm_newroute, NULL, NULL);
rtnl_register(PF_INET, RTM_DELROUTE, inet_rtm_delroute, NULL, NULL);
rtnl_register(PF_INET, RTM_GETROUTE, NULL, inet_dump_fib, NULL);

register_pernet_subsys(&fib_net_ops);
//订阅了两个事件
register_netdevice_notifier(&fib_netdev_notifier);
register_inetaddr_notifier(&fib_inetaddr_notifier);

fib_trie_init();
}

注:之后会专门写一篇关于路由的源码追踪文章,本篇简单介绍。