LinuxIPv4路由功能的分析.doc

IPv4路由设计与实现相关知识

文档编号：00-6201-100
当前版本：1.0.0.0
创建日期：2011-9-1
编写作者：ganjingwei

路由知识总结

前言 3
关于此文档 3
参考资料 3
第一章 路由的基本概念 4
1.1 路由的作用 4
1.2 路由的工作原理 4
第二章 数据结构 5
2.1 fib_table 5
2.2 fn_hash 5
2.3 fn_zone 5
2.4 fib_node 6
2.5 fib_alias 6
2.6 fib_info 7
2.7 fib_nh 7
第三章 路由表的创建 9
3.1 创建路由表 9
3.2 掩码长度分类级 10
3.3 网络地址分类级 12
3.4 路由信息分类级 13
3.5 具体创建过程 16
第四章 Linux路由功能实现 19
2.1 数据包流程 19
2.2 数据包路由过程 20
2.3 相关代码 22
2.3.1 ip_rcv_finish函数 22
2.3.2 ip_route_input函数 22
2.3.3 ip_route_input_slow函数 23
2.3.4 __mkroute_input函数 25
2.3.5 fib_lookup函数 26

前言
关于此文档
此文档是本人这段时间内学习Linux网络协议栈路由功能相关知识，总结并且整理出来的文档。供大家参考。
本文档描述Linux相关知识，各章节说明如下：
1 前言，即此章节；
2 路由理论知识；
3 相关数据结构；
4 路由表的创建；
5 Linux路由的实现及数据包流程。

参考资料
网络资源。
本文中的所有代码以broadcom4.12L.01为依据，内核代码为2.6。

第一章 路由的基本概念
1.1 路由的作用
路由器工作在ISO层次结构中的三层，根据三层协议的各种信息，完成数据包的选路和转发，最终达到目的地。

1.2 路由的工作原理
路由与网桥的区别，在于路由了解整个网络，而网桥只了解相连接的主机或网络。因此路由在选路的过程中，更具有目的性。
路由维持一张（多张）路由表来支持选路的功能。路由表与网桥表不同，路由表是人为配置的（这里说的人为配置，可能是用户通过接口进行配置，也可以是应用层本身对内核进行路由配置，比如动态更新路由自主学习等）。
每个路由表中记录的信息有：源地址（网络）、目的地址（网络）、目的网关、scope（距离）。查询根据这些来匹配。匹配过程中，先匹配一个路由缓存，再匹配路由表。路由缓存是由内核维持的，而路由表是人为配置的。缓存根据最近使用的表项来更新，目的是为了提高查询效率，和CPU的cache一样。在内核中，路由表由fib_table_hash[]表示，路由缓存由rt_hash_table[]表示。

第二章 数据结构
2.1 fib_table
这是一个路由表的最高级结构。
struct fib_table {
struct hlist_node tb_hlist;
u32 tb_id;
unsigned tb_stamp;
int tb_default;
int (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);
int (*tb_insert)(struct fib_table *, struct fib_config *);
int (*tb_delete)(struct fib_table *, struct fib_config *);
int (*tb_dump)(struct fib_table *table, struct sk_buff *skb,
struct netlink_callback *cb);
int (*tb_flush)(struct fib_table *table);
void (*tb_select_default)(struct fib_table *table,
const struct flowi *flp, struct fib_result *res);

unsigned char tb_data[0];
};

2.2 fn_hash
这是路由表一级查找（按掩码查找）的散列结构体，包含了散列表头和散列数组。
struct fn_hash {
struct fn_zone *fn_zones[33];
struct fn_zone *fn_zone_list;
};

2.3 fn_zone
这是路由表一级查找（按掩码查找）的具体信息保存的结构体。
struct fn_zone {
struct fn_zone *fz_next; /* Next not empty zone */
struct hlist_head *fz_hash; /* Hash table pointer */
int fz_nent; /* Number of entries */

int fz_divisor; /* Hash divisor */
u32 fz_hashmask; /* (fz_divisor - 1) */
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)

int fz_order; /* Zone order */
__be32 fz_mask;
#define FZ_MAS K(fz) ((fz)->fz_mask)
};

2.4 fib_node
这是路由表二级查找（网络地址查找）具体信息存放的结构体，其中fn_key就是网络地址，通过fn_key和掩码长度来计算散列定位。
struct fib_node {
struct hlist_node fn_hash;
struct list_head fn_alias;
__be32 fn_key;
struct fib_alias fn_embedded_alias;
};

2.5 fib_alias
这个结构体包含了路由的具体信息的结构体，但是它不对其进行描述，而是描述一些键值，用于标识和排序那些信息。真正的信息包含在fa_info中。
struct fib_alias {
struct list_head fa_list;
struct fib_info *fa_info;
u8 fa_tos;
u8 fa_type;
u8 fa_scope;
u8 fa_state;
#ifdef CONFIG_IP_FIB_TRIE
struct rcu_head rcu;
#endif
};

2.6 fib_info
这个才是真正的路由信息结构。
struct fib_info {
struct hlist_node fib_hash;
struct hlist_node fib_lhash;
struct net *fib_net;
int fib_treeref;
atomic_t fib_clntref;
int fib_dead;
unsigned fib_flags;
int fib_protocol;
__be32 fib_prefsrc;
u32 fib_priority;
u32 fib_metrics[RTAX_MAX];
#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 fib_nh fib_nh[0];
#define fib_dev fib_nh[0].nh_dev
};

2.7 fib_nh
这个结构被包含在fib_info中，是路由下一条的信息，一般来说只有一个，但是如果有多通路，也就是配置了CONFIG_IP_ROUTE_MULTIPATH，才会有多个。
struct fib_nh {
struct net_device *nh_dev;
struct hlist_node nh_hash;
struct fib_info *nh_parent;
unsigned nh_flags;
unsigned char nh_scope;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int nh_weight;
int nh_power;
#endif
#ifdef CONFIG_NET_CLS_ROUTE
__u32 nh_tclassid;
#endif
int nh_oif;
__be32 nh_gw;
};

第三章 路由表的创建
3.1 创建路由表
默认路由表由内核创建的函数调用流程为：
inet_init()
->ip_init()
->ip_fib_init()
->fib_net_init()
->ip_fib_net_init()[net/ipv4/fib_frontend.c]

在这个函数中，首先为路由表分配空间，这里的每个表项hlist_head实际都会链接一个单独的路由表，FIB_TABLE_HASHSZ表示了分配多少个路由表，一般情况下至少有两个——LOCAL和MAIN。注意这里仅仅是表头的空间分配，还没有真正分配路由表空间。
net->ipv4.fib_table_hash = kzalloc(
sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL);

接下来的err = fib4_rules_init(net); 真正分配了路由表空间
local_table = fib_hash_table(RT_TABLE_LOCAL);
if (local_table == NULL)
return -ENOMEM;
main_table = fib_hash_table(RT_TABLE_MAIN);
if (main_table == NULL)
goto fail;

然后将local和main表链入之前的fib_table_hash中
hlist_add_head_rcu(&local_table->tb_hlist,
&net->ipv4.fib_table_hash[TABLE_LOCAL_INDEX]);
hlist_add_head_rcu(&main_table->tb_hlist,
&net->ipv4.fib_table_hash[TABLE_MAIN_INDEX]);

最后生成的结构如图3-1，LOCAL表位于fib_table_hash[0]，MAIN表位于fib_table_hash[1]；两张表通过结构tb_hlist链入链表，而tb_id则标识了功能，255是LOCAL表，254是MAIN表。

图3-1 路由表内核内部结构
路由表的查找效率是第一位的，因此内核在实现时使用了多级索引来进行加速：
第一级：fn_zone，按不同掩码长度分类(如/5和/24)；
第二级：fib_node，按不同网络地址分类(如124.44.33.0/24)；
第三级：fib_info，按下一跳路由信息。
当然，我们创建路由表也要按照这个顺序。

3.2 掩码长度分类级
关于上一节说的struct fn_hash，它表示了不同子网掩码长度hash表（即fn_zone），对于ipv4，从0~32共33个。而fn_hash的实现则是fib_table的最后一个参数unsigned char tb_data[0]。
注意这里fn_zone还只是空指针，我们还只完成了路由表初始化的一部分。在启动阶段还会调用inet_rtm_newroute()->fib_table_insert()->fn_new_zone()[fib_hash.c]来创建fn_zone结构，前面已经讲过，fn_zone一共有33个，其中掩码长度为0[/0]表示为默认路由，fn_zone可以理解为相同掩码的地址集合。

首先为fn_zone分配空间
struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL);

传入参数z代表掩码长度，z=0的掩码用于默认路由，一般只有一个，所以fz_divisor只需设1；其它设为16；这里要提到fz_divisor的作用，fz->fz_hash并不是个单链表，而是一个哈希表，而哈希表的大小就是fz_divisor。
if (z) {
fz->fz_divisor = 16;
} else {
fz->fz_divisor = 1;
}

fz_hashmask实际是用于求余数的，当算出hash值，再hash & fz_hashmask就得出了在哈希表的位置；而fz_hash就是下一层的哈希表了，前面已经提过路由表被多组分层了，这里fz_hash就是根据fz_divisor大小来创建的；fz_order就是子网掩码长度；fz_mask就是子网掩码。
fz->fz_hashmask = (fz->fz_divisor - 1);
fz->fz_hash = fz_hash_alloc(fz->fz_divisor);
fz->fz_order = z;
fz->fz_mask = inet_make_mask(z);

从子网长度大于新添加fz的fn_zone中挑选一个不为空的fn_zones[i]，将新创建fz设成fn_zones[i].next；然后将fz根据掩码长度添加到fn_zones[]中相应位置；fn_zone_list始终指向掩码长度最长的fn_zone。
for (i=z+1; i<=32; i++)
if (table->fn_zones[i])
break;
if (i>32) {
fz->fz_next = table->fn_zone_list;
table->fn_zone_list = fz;
} else {
fz->fz_next = table->fn_zones[i]->fz_next;
table->fn_zones[i]->fz_next = fz;
}
table->fn_zones[z] = fz;

fn_hash包含33数组元素，每个元素存放一定掩码长度的fn_zone，其中fn_zone[i]存储掩码长度为i。而fn_zone通过内部属性fz_next又彼此串连起来，形成单向链表，其中fn_zone_list可以看作链表头，而这里链表的组织顺序是倒序的，即从掩码长到短。其中结构如图3-2所示。

图3-2 路由表一级查找结构

3.3 网络地址分类级
到上一节为止，fz_hash所分配的哈希表还没有插入内容，这部分为fib_insert_node()完成：
inet_rtm_newroute()->fib_table_insert()->fib_insert_node()[net/ipv4/fib_hash.c]。

这里f是fib_node，可以理解为具有相同网络地址的路由项集合。根据fn_key(网络地址)和fz(掩码长度)来计算hash值，决定将f插入fz_hash的哪个项。
struct hlist_head *head = &fz->fz_hash[fn_hash(f->fn_key, fz)];
hlist_add_head(&f->fn_hash, head);
}

如果fib_node不存在，则会创建它，这里的kmem_cache_zalloc()其实就是内存分配。
new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);
if (new_f == NULL)
goto out;
INIT_HLIST_NODE(&new_f->fn_hash);
INIT_LIST_HEAD(&new_f->fn_alias);
new_f->fn_key = key;
f = new_f;

3.4 路由信息分类级
路由表最后一层是fib_info，具体的路由信息都存储在此，它由fib_create_info()创建。
首先为fib_info分配空间，由于fib_info的最后一个属性是struct fib_nh fib_nh[0]，因此大小是fib_info + nhs * fib_nh，这里的fib_nh代表了下一跳(next hop)的信息，nhs代表了下一跳的数目，一般情况下nhs=1，除非配置了支持多路径。
fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);

设置fi的相关属性
fi->fib_net = hold_net(net);
fi->fib_protocol = cfg->fc_protocol;
fi->fib_flags = cfg->fc_flags;
fi->fib_priority = cfg->fc_priority;
fi->fib_prefsrc = cfg->fc_prefsrc;
fi->fib_nhs = nhs;

使fi后面所有的nh->nh_parent指向fi，设置后如图3-3所示
change_nexthops(fi) {
nexthop_nh->nh_parent = fi;
} endfor_nexthops(fi)

图3-3 fib_info结构体
设置fib_nh的属性，这里仅展示了单一路径的情况：
struct fib_nh *nh = fi->fib_nh;
nh->nh_oif = cfg->fc_oif;
nh->nh_gw = cfg->fc_gw;
nh->nh_flags = cfg->fc_flags;

然后，再根据cfg->fc_scope值来设置nh的其余属性。如果scope是RT_SCOPE_HOST，则设置下一跳scope为RT_SCOPE_NOWHERE。
if (cfg->fc_scope == RT_SCOPE_HOST) {
struct fib_nh *nh = fi->fib_nh;
nh->nh_scope = RT_SCOPE_NOWHERE;
nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);
}

如果scope是RT_SCOPE_LINK或RT_SCOPE_UNIVERSE，则设置下跳：
change_nexthops(fi) {
if ((err = fib_check_nh(cfg, fi, nexthop_nh)) != 0)
goto failure;
} endfor_nexthops(fi)

最后，将fi链入链表中，这里要注意的是所有的fib_info(只要创建了的)都会加入fib_info_hash中，如果路由项使用了优先地址属性，还会加入fib_info_laddrhash中。
hlist_add_head(&fi->fib_hash,
&fib_info_hash[fib_info_hashfn(fi)]);
if (fi->fib_prefsrc) {
struct hlist_head *head;
head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)];
hlist_add_head(&fi->fib_lhash, head);
}

无论fib_info在路由表中位于哪个掩码、哪个网段结构下，都与fib_info_hash和fib_info_laddrhash无关，这两个哈希表与路由表独立，主要是用于加速路由信息fib_info的查找。哈希表的大小为fib_hash_size，当超过这个限制时，fib_hash_size * 2(如果哈希函数够好，每个bucket都有一个fib_info)。fib_info在哈希表如图3-4所示。

图3-4 fib_info结构与它的hash表

由于路由表信息也可能要以设备dev为键值搜索，因此还存在fib_info_devhash哈希表，用于存储nh的设置dev->ifindex。
change_nexthops(fi) {
hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);
head = &fib_info_devhash[hash];
hlist_add_head(&nexthop_nh->nh_hash, head);
} endfor_nexthops(fi)

3.5 具体创建过程
上面讲过了路由表各个部分的创建，现在来看下它们是如何一起工作的，在fib_table_insert()[net/ipv4/fib_hash.c]完成整个的路由表创建过程。下面来看下fib_table_insert()函数：

从fn_zones中取出掩码长度为fc_dst_len的项，如果该项不存在，则创建它（fn_zone的创建前面已经讲过）。
fz = table->fn_zones[cfg->fc_dst_len];
if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len)))
return -ENOBUFS;

然后创建fib_info结构，（前面已经讲过）
fi = fib_create_info(cfg);

然后在掩码长度相同项里查找指定网络地址key(如145.222.33.0/24)，查找的结果如图3-5所示.
f = fib_find_node(fz, key);

图3-5 查找网络地址key

如果不存在该网络地址项，则创建相应的fib_node，并加入到链表fz_hash中。
if (!f) {
new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);
if (new_f == NULL)
goto out;
INIT_HLIST_NODE(&new_f->fn_hash);
INIT_LIST_HEAD(&new_f->fn_alias);
new_f->fn_key = key;
f = new_f;
}
……
fib_insert_node(fz, new_f);

如果存在该网络地址项，则在fib_node的属性fn_alias中以tos和fi->fib_priority作为键值查找。一个fib_node可以有多个fib_alias相对应，这些fib_alias以链表形式存在，并按tos并从大到小的顺序排列。因此，fib_find_alias查找到的是第一个fib_alias->tos不大于tos的fib_alias项。
fa = fib_find_alias(&f->fn_alias, tos, fi->fib_priority);

如果查找到的fa与与要插入的路由项完全相同，则按照设置的标置位进行操作，NLM_F_REPLACE则替换掉旧的，NLM_F_APPEND添加在后面。

设置要插入的fib_alias的属性，包括最重要的fib_alias->fa_info设置为fi。
new_fa->fa_info = fi;
new_fa->fa_tos = tos;
new_fa->fa_type = cfg->fc_type;
new_fa->fa_scope = cfg->fc_scope;
new_fa->fa_state = 0;

如果没有要插入路由的网络地址项fib_node，则之前已经创建了新的，现在将它插入到路由表中fib_insert_node()；然后将new_fa链入到fib_node->fn_alias中。
if (new_f)
fib_insert_node(fz, new_f);
list_add_tail(&new_fa->fa_list,
(fa ? &fa->fa_list : &f->fn_alias));

最后，由于新插入的路由表项，会发出通告，告知所以加入RTNLGRP_IPV4_ROUTE组的成员，这个功能可以在linux中使用”ip route monitor”来测试。最终的路由表如图3-6所示。
rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, &cfg->fc_nlinfo, 0);

图3-6 路由表总体结构
第四章 Linux路由功能实现
2.1 数据包流程

图4-1 Linux网络层的数据包函数调用流程
如图4-1所示，ip_rcv是IPv4数据包的基本接收函数，由下层调用。这个函数完成一系列的校验、协议处理等等，然后进入第一个HOOK点，这是在本机路由前的点。
在ip_rcv_finish函数中，会调用ip_route_input函数来进行本机路由，判断是发送给本机的，还是需要转发的，由此来知道下一处理函数是ip_local_deliver，还是ip_forward。至于ip_route_input是如何进行路由的，将在下一节进行讲解。
ip_local_deliver以上，是本机数据包流程，这与路由无关，这里不做赘述。
ip_forward进行一些路由的处理，比如设置网关、MTU，TTL减1等等。然后进入ip_forward_finish，根据之前设置的skb->dst->output函数来确定去处。这个output也是在之前的路由过程中确定的，具体是单播、多播、还是广播等等，视之前的路由和协议而定。
2.2 数据包路由过程
之前说了ip_rcv_finish函数中，调用ip_route_input函数来进行本机路由。具体流程如图4-2所示。

图4-2 路由过程
ip_route_input函数中，首先去路由缓存rt_ hash_table中查找，如果找到则直接返回。如果没有找到，则调用ip_route_input_slow来查找路由表。
ip_route_input_slow函数中调用fib_lookup来查找。fib_lookup有两种定义，根据不同的功能编译开关。一种是只查找main表和local表，这是低级路由。另一种则会遍历rule表，先匹配应该查找哪一张路由表（可能是高级路由配置的），然后再对该表进行查询。
如果查询结果是本机的数据包，则会在ip_route_input_slow函数的后面部分进行数据包路由信息的更改，最重要的是入口函数改成ip_local_deliver。然后调用rt_intern_hash函数来更新路由缓存。
如果结果是需要转发的，则调用ip_mkroute_input->__mkroute_input来做进一步的处理（ip_mkroute_input中有一个分支，多路路由，这里不作介绍）。也就是把查找到的路由信息加入路由缓存，并把路由结果传递给数据包。
2.3 相关代码
2.3.1 ip_rcv_finish函数
……………………………………
if (skb->dst == NULL) {
int err = ip_route_input(skb, READ32_ALIGNED(iph->daddr),
READ32_ALIGNED(iph->saddr), iph->tos, skb->dev);
if (unlikely(err)) {
if (err == -EHOSTUNREACH)
IP_INC_STATS_BH(dev_net(skb->dev),
IPSTATS_MIB_INADDRERRORS);
else if (err == -ENETUNREACH)
IP_INC_STATS_BH(dev_net(skb->dev),
IPSTATS_MIB_INNOROUTES);
goto drop;
}
}
……………………………………

2.3.2 ip_route_input函数
……………………………………
for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.dst.rt_next)) {
if (((rth->fl.fl4_dst ^ daddr) |
(rth->fl.fl4_src ^ saddr) |
(rth->fl.iif ^ iif) |
rth->fl.oif |
(rth->fl.fl4_tos ^ tos)) == 0 &&
rth->fl.mark == skb->mark &&
net_eq(dev_net(rth->u.dst.dev), net) &&
!rt_is_expired(rth)) {
dst_use(&rth->u.dst, jiffies);
RT_CACHE_STAT_INC(in_hit);
rcu_read_unlock();
skb->rtable = rth;
return 0;
}
……………………………………
return ip_route_input_slow(skb, daddr, saddr, tos, dev);

2.3.3 ip_route_input_slow函数
……………………………………
if ((err = fib_lookup(net, &fl, &res)) != 0) {
if (!IN_DEV_FORWARD(in_dev))
goto e_hostunreach;
goto no_route;
}
……………………………………
if (res.type == RTN_LOCAL) {
int result;
result = fib_validate_source(saddr, daddr, tos,
net->loopback_dev->ifindex,
dev, &spec_dst, &itag);
if (result < 0)
goto martian_source;
if (result)
flags |= RTCF_DIRECTSRC;
spec_dst = daddr;
goto local_input;
}
……………………………………
err = ip_mkroute_input(skb, &res, &fl, in_dev, daddr, saddr, tos);
……………………………………
local_input:
rth = dst_alloc(&ipv4_dst_ops);
if (!rth)
goto e_nobufs;
rth->u.dst.output= ip_rt_bug;
rth->rt_genid = rt_genid(net);
atomic_set(&rth->u.dst.__refcnt, 1);
rth->u.dst.flags= DST_HOST;
if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
rth->u.dst.flags |= DST_NOPOLICY;
rth->fl.fl4_dst = daddr;
rth->rt_dst = daddr;
rth->fl.fl4_tos = tos;
rth->fl.mark = skb->mark;
rth->fl.fl4_src = saddr;
rth->rt_src = saddr;
rth->rt_iif =
rth->fl.iif = dev->ifindex;
rth->u.dst.dev = net->loopback_dev;
dev_hold(rth->u.dst.dev);
rth->idev = in_dev_get(rth->u.dst.dev);
rth->rt_gateway = daddr;
rth->rt_spec_dst= spec_dst;
rth->u.dst.input= ip_local_deliver;
rth->rt_flags = flags|RTCF_LOCAL;
if (res.type == RTN_UNREACHABLE) {
rth->u.dst.input= ip_error;
rth->u.dst.error= -err;
rth->rt_flags &= ~RTCF_LOCAL;
}
rth->rt_type = res.type;
hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net));
err = rt_intern_hash(hash, rth, &skb->rtable);
……………………………………

2.3.4 __mkroute_input函数
……………………………………
rth->u.dst.flags= DST_HOST;
if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
rth->u.dst.flags |= DST_NOPOLICY;
if (IN_DEV_CONF_GET(out_dev, NOXFRM))
rth->u.dst.flags |= DST_NOXFRM;
rth->fl.fl4_dst = daddr;
rth->rt_dst