网络层路由系统（linux网络协议栈笔记）

查找出口

当要发送一个报文时，必定要查询发送接口，这个过程被Linux分为3个步骤：
第一个步骤是查询路由cache，
第二个步骤是查询FIB表，
第三步是将查询结果填入路由cache中以便将来查询。

现在来介绍一下路由cache。
路由cache
当确定了一条路由时，路由表项就被放入路由cache中，这意味着一旦知道路由并放入cache后，经过同样路由的报文能够立即找到出口。一个报文在本地机器上可以有一个目的地址，它最终的目的也许是本地可达的主机，也可能被发送到下一跳节点。因此，路由和目的cache被设计成报文目的地址对实际的IP发送过程是透明的，目的cache表项可以和路由cache表项互换。为了指向指向目的cache，同样的dst字段也指向路由表的表项。这让IP用有效的方法检查待发送报文的目的地址，而不用查找路由或显式的检查目的地址是否已经被解析到硬件地址。路由cache可以被看作FIB的子集，它是用来优化已知目的地址的已打开socket的快速路由的。路由cache的实现基于通用的目的地址cache架构，它由hash表组成，每一个表项包含路由表项。这个表可以用简单key完成快速搜索。hash表的实现允许冲突，因为每一个hash表位置可以包含多个路由。IP中的路由cache是一个hash桶（即rt_hash_bucket）的实例，叫rt_hase_table，在此数组中每一个单元包含一个指向路由表的链，每个匹配某目的地址的路由放在一个由链表指向的连接列表中。其基本结构如下：
rt_hash_table和rtable、dst_entry的关系如下图：

路由表是路由cache中存放每个路由的基本数据结构。本质上它是面向对象的。这是把路由cache看作是来源于通用的目的地址cache功能的原因。例如，sk_buff结构为外发报文包含一个指向目的cache表项的指针，这个dst表项为报文包含一个指向路由cache表项的指针。因此用相似的方法，这个rtable结构定义的首要的几个字段指向目的cache，dst_entry。

struct rtable
{
union
{
struct dst_entry dst;
} u;
struct flowi fl;//包含实际的hash 键
struct in_device *idev;
/*rt_flags能被提供应用程序接口的路由表使用。因为在单个hash桶内也许有多个路由，那么这些路由会冲突。当垃圾回收程序处理这些路由cache，如果和高价值的路由发生冲突时，低价值的路由倾向于被清除出去，路由控制flags决定这些路由的值。*/
unsigned rt_flags;
/*rt_type是这个路由的类型，它确定这些路由是否单播、组播或本地路由*/
__u16 rt_type;
/*rt_dst是IP目的地址，rt_src是IP源地址。Rt_iif是路由输入接口索引*/
__be32 rt_dst;
__be32 rt_src;
int rt_iif;
__be32 rt_gateway;//网关或邻居的IP地址
__be32 rt_spec_dst;
struct inet_peer *peer;
};

路由cache的搜索算法：先用一个简单的hash code定位hash桶里的一个slot，然后用一个key去匹配一个指定的路由，这必须遍历这个slot所有的路由列表直到rt_next等于NULL。第二级查找是把rtable表项中的fl字段和收到的报文中的信息进行精确匹配。fl结构包含了能确定某路由的所有信息。

flowi数据结构
这里我们碰到一个奇怪的结构就是flowi。从它的字面上来理解似乎是和“流”有关的一个东西，但源代码中没有对它进行详细解释。而且，BSD协议栈中也没有这么一个结构。那么它到底是什么呢？其实，它就是标识一个发送/接收流的结构，不同用户的业务流之间是如何被内核区别就依靠它。所以，flowi中的i可以理解成identifier。首先，它的结构如下：

struct flowi {
int oif;/*出口设备*/
int iif;/*入口设备*/
__u32 mark;/*mark值*/
/*三层相关的成员，对于ipv4有目的ip地址、源ip地址、tos、scope等*/
union {
struct {
__be32 daddr;
__be32 saddr;
__u8 tos;
__u8 scope;
} ip4_u;
struct {
struct in6_addr daddr;
struct in6_addr saddr;
__be32 flowlabel;
} ip6_u;
struct {
__le16 daddr;
__le16 saddr;
__u8 scope;
} dn_u;
} nl_u;
#define fld_dst nl_u.dn_u.daddr
#define fld_src nl_u.dn_u.saddr
#define fld_scope nl_u.dn_u.scope
#define fl6_dst nl_u.ip6_u.daddr
#define fl6_src nl_u.ip6_u.saddr
#define fl6_flowlabel nl_u.ip6_u.flowlabel
#define fl4_dst nl_u.ip4_u.daddr
#define fl4_src nl_u.ip4_u.saddr
#define fl4_tos nl_u.ip4_u.tos
#define fl4_scope nl_u.ip4_u.scope
__u8 proto;/*四层协议类型与四层协议相关的成员(源、目的端口)等*/
__u8 flags;
#define FLOWI_FLAG_MULTIPATHOLDROUTE 0x01
union {
struct {
__be16 sport;
__be16 dport;
} ports;
struct {
__u8 type;
__u8 code;
} icmpt;
struct {
__le16 sport;
__le16 dport;
} dnports;
__be32 spi;
#ifdef CONFIG_IPV6_MIP6
struct {
__u8 type;
} mht;
#endif
} uli_u;
#define fl_ip_sport uli_u.ports.sport
#define fl_ip_dport uli_u.ports.dport
#define fl_icmp_type uli_u.icmpt.type
#define fl_icmp_code uli_u.icmpt.code
#define fl_ipsec_spi uli_u.spi
#ifdef CONFIG_IPV6_MIP6
#define fl_mh_type uli_u.mht.type
#endif
__u32 secid; /* used by xfrm; see secid.txt */
} __attribute__((__aligned__(BITS_PER_LONG/8)));

从上面结构定义可以看到，一个数据报文有源、目的地址端口，有proto选项，有用户定义的类型，甚至有入接口和出接口，那么，通过这些标识，就可以唯一的确定某用户的业务流。然后你就可以对某一个指定的流查找其路由。好啦，可以这么说，路由是网络内不同业务流的标识，而flowi是操作系统内部不同业务流的标识。内核通过从TCP或IP报文头中抽取相应的信息填入到flowi结构中，然后路由查找模块根据这个信息为相应的流找到对应路由。所以说，flowi就是一个查找key。
路由的范围放在flowi结构的scope字段，我们可以想象这个“scope”是到目的地址的距离。它是用来确定如何路由报文和如何归类这些路由。上表的scope值用在fib_result里的scope字段和next_hop结构的fib_nhs里的nh_scope字段，用户创建的特定路由表应用程序可以定义scope的范围是0~199，当前，Linux Ipv4经常使用的是RT_SCOPE_UNIVERSE，RT_SCOPE_LINK或RT_SCOPE_HOST。较大的数暗示更接近目的地（除了RT_SCOPE_NOWHERE，表示目的地不存在）。每个路由表项即rtable的第一部分包含一个目的地址cache表项结构，叫dst_entry，它包扩用来指向管理cache表项的相应函数——dst_ops结构，对于IP Route Cache的dst_ops值如下（注意表中的路由表项指的是路由cache中的表项，不是FIB中的表项）：

在raw_sendmsg函数中调用了ip_route_output_flow，但它只是简单的调用了__ip_route_output_key，只是参数有所不同。这些比较重要的参数，要结合上面给出的代码仔细研究。首先，通过检查dst_entry的废除字段看是否该路由已被废除。如果是，就调用ip_rt_put函数把该路由归还到slab cache，否则，我们想删除到某目的地址所有的路由。。。
我们通过检查dst_entry的超时字段看该表项是否过期，或者看rt_flag标志是否已被打上RTCF_REDIRECTED标志来判断该路由已经被重路由，如果是，就重新计算32位hash值并调用rt_del删除匹配hash桶位置的所有路由。
一些路由cache函数被直接调用，其中一部分函数被定义成内联函数，比如ip_rt_put，它通过调用通用的dst_release函数删除一条路由。再如rt_bind_peer，它给某路由创建一条对端表项，从效果上看，它增加了关于到路由表中的目的地址的信息。
当一条新的路由为发送报文准备好后，ip_route_output调用rt_intern_hash函数，rt_inten_hash用hash作为索引到rt_hash_table的参数，这个索引只是定位到最匹配的位置，那个位置可以包含0个、1个或多个路由。然后该函数用rt中的flowi部分去匹配其中的一个路由。如果它找到一个精确匹配的，就把这个路由移到链表的前面，增加它的使用计数器，然后释放新的路由rt。如果没有匹配的项，那么新路由rt会放在链表的前面。如果邻居cache好像满了，我们就调用rt_garbage_collect函数删除路由，直到有足够的空间放置新路由。如果rt_intern_hash不能找到空间，就返回ENOBUFS错误代码。
一旦有一条指向非直连主机的外部地址的路由，那么两个主要的路由解析函数：ip_route_output_slow和ip_route_input_slow需要创建一些特别信息。例如，IP允许设定MTU，而且TCP可以与对端协商最大端长度的选项，那么就可以通过调用rt_set_nexthop去设定这些信息。具体流程就是下面的函数：

int __ip_route_output_key(struct net *net, struct rtable **rp,
const struct flowi *flp)
{
unsigned hash;
struct rtable *rth;
if (!rt_caching(net))
goto slow_output;
/*类似于ip_route_input,先在cache中查找路由， 找到就返回*/
hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
rcu_read_lock_bh();
for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.dst.rt_next)) {
if (rth->fl.fl4_dst == flp->fl4_dst &&
rth->fl.fl4_src == flp->fl4_src &&
rth->fl.iif == 0 &&
rth->fl.oif == flp->oif &&
rth->fl.mark == flp->mark &&
!((rth->fl.fl4_tos ^ flp->fl4_tos) &
(IPTOS_RT_MASK | RTO_ONLINK)) &&
net_eq(dev_net(rth->u.dst.dev), net) &&
!rt_is_expired(rth)) {
dst_use(&rth->u.dst, jiffies);
RT_CACHE_STAT_INC(out_hit);
rcu_read_unlock_bh();
*rp = rth;
return 0;
}
RT_CACHE_STAT_INC(out_hlist_search);
}
rcu_read_unlock_bh();
/*不支持cache 或在cache中没找到相应的路由信息，在路由表中查找*/
slow_output:
/*如果没有找到相应表项，表明还没有为该流找到一条路由，于是，将进行路由解析过程*/
return ip_route_output_slow(net, rp, flp);
}

再分析ip_route_output_slow的代码：

/*
* Major route resolver routine.
*/
static int ip_route_output_slow(struct net *net, struct rtable **rp,
const struct flowi *oldflp)
{
u32 tos = RT_FL_TOS(oldflp); /*获取tos和当前的RTO_ONLINK（？）标志*/
struct flowi fl = { .nl_u = { .ip4_u =
{ .daddr = oldflp->fl4_dst,
.saddr = oldflp->fl4_src,
.tos = tos & IPTOS_RT_MASK,
/*如果设置了MSG_DONTROUTE，那么tos=RTO_ONLINK，于是scope＝SCOPE_LINK*/
.scope = ((tos & RTO_ONLINK) ? /*根据这个标志，得出路由的scope*/
RT_SCOPE_LINK :
RT_SCOPE_UNIVERSE),
} },
.mark = oldflp->mark,
.iif = net->loopback_dev->ifindex, /*设备号为lo的设备号?*/
.oif = oldflp->oif };
struct fib_result res;
unsigned flags = 0;
struct net_device *dev_out = NULL;
int free_res = 0;
int err;
res.fi = NULL;
#ifdef CONFIG_IP_MULTIPLE_TABLES
res.r = NULL;
#endif
/*先是对源地址， 发包接口号和目的地址进行判断分类处理。下面的每一个红色跳转就是一种情况*/
if (oldflp->fl4_src) { /*源*/
err = -EINVAL;
if (ipv4_is_multicast(oldflp->fl4_src) ||
ipv4_is_lbcast(oldflp->fl4_src) ||
ipv4_is_zeronet(oldflp->fl4_src))
goto out;
/*上面是对报文源地址的合理性检查，源地址是多播，广播或0地址时，返回错误*/
/* I removed check for oif == dev_out->oif here.
It was wrong for two reasons:
我在这里删去检查oif == dev_out->oif是否成立，因为有两个原因说明这个检查时错误的：
1. ip_dev_find(net, saddr) can return wrong iface, if saddr
is assigned to multiple interfaces
如果源地址是一个多播接口的地址，函数ip_dev_find(net, saddr)可能返回错误的设备接口。
2. Moreover, we are allowed to send packets with saddr
of another iface. --ANK
而且可以用另外设备接口的源地址发送报文
*/
if (oldflp->oif == 0
&& (ipv4_is_multicast(oldflp->fl4_dst) ||
oldflp->fl4_dst == htonl(0xFFFFFFFF))) { /*发包接口为lo，目的地址是广播或多播时查找发包设备，ip_dev_find返回与所给定的源地址相等的第一个设备*/
/* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
dev_out = ip_dev_find(net, oldflp->fl4_src);
if (dev_out == NULL)
goto out;
/* Special hack: user can direct multicasts
and limited broadcast via necessary interface
without fiddling with IP_MULTICAST_IF or IP_PKTINFO.
This hack is not just for fun, it allows
vic,vat and friends to work.
They bind socket to loopback, set ttl to zero
and expect that it will work.
From the viewpoint of routing cache they are broken,
because we are not allowed to build multicast path
with loopback source addr (look, routing cache
cannot know, that ttl is zero, so that packet
will not leave this host and route is valid).
Luckily, this hack is good workaround.
*/
/*当报文初始化的出接口为lo接口源地址不为空目的地址是多播或广播地址时，找到源地址所对应的接口重新为出接口赋值， 然后创建cache路由项*/
fl.oif = dev_out->ifindex;
goto make_route;
}
if (!(oldflp->flags & FLOWI_FLAG_ANYSRC)) {
/* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
dev_out = ip_dev_find(net, oldflp->fl4_src);
if (dev_out == NULL)
goto out;
dev_put(dev_out);
dev_out = NULL;
}
}
if (oldflp->oif) {/*发包设备不为空*/
/*检测出接口是否存在*/
dev_out = dev_get_by_index(net, oldflp->oif);
err = -ENODEV;
if (dev_out == NULL)
goto out;
/* RACE: Check return value of inet_select_addr instead. */
/*看设备是否是多地址*/
if (__in_dev_get_rtnl(dev_out) == NULL) {
dev_put(dev_out);
goto out; /* Wrong error code */
}
/*当目的地址是本地多播地址或广播地址，并且报文源地址为空时，找出出接口设备上IP地址scope小于RT_SCOPE_LINK的地址，并赋值，然后往cache中添加路由表项*/
if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
oldflp->fl4_dst == htonl(0xFFFFFFFF)) {
if (!fl.fl4_src)
fl.fl4_src = inet_select_addr(dev_out, 0,
RT_SCOPE_LINK);
goto make_route;
}
/*目的地址是单播地址或空，源地址为空，那就选一个小于特定scope的IP地址*/
if (!fl.fl4_src) {
if (ipv4_is_multicast(oldflp->fl4_dst))
fl.fl4_src = inet_select_addr(dev_out, 0,
fl.fl4_scope);
else if (!oldflp->fl4_dst)
fl.fl4_src = inet_select_addr(dev_out, 0,
RT_SCOPE_HOST);
}
}
if (!fl.fl4_dst) {/*目的地址为空*/
fl.fl4_dst = fl.fl4_src;
if (!fl.fl4_dst)
fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);/*目的和源地址都是空，则赋值为lo接口地址*/
if (dev_out)
dev_put(dev_out);
dev_out = net->loopback_dev;
dev_hold(dev_out);
fl.oif = net->loopback_dev->ifindex;
res.type = RTN_LOCAL;
flags |= RTCF_LOCAL;
/*为发给本机的报文添加cache路由*/
goto make_route;
}
/*一种情况是源地址目的地址不为空，目的地址为空，出接口为lo*/
/*还有其他几种情况，就是目的地址和出接口必须对应*/
if (fib_lookup(net, &fl, &res)) {
res.fi = NULL;
if (oldflp->oif) {
/* Apparently, routing tables are wrong. Assume,
that the destination is on link.
WHY? DW.
Because we are allowed to send to iface
even if it has NO routes and NO assigned
addresses. When oif is specified, routing
tables are looked up with only one purpose:
to catch if destination is gatewayed, rather than
direct. Moreover, if MSG_DONTROUTE is set,
we send packet, ignoring both routing tables
and ifaddr state. --ANK
We could make it even if oif is unknown,
likely IPv6, but we do not.
*/
if (fl.fl4_src == 0)
fl.fl4_src = inet_select_addr(dev_out, 0,
RT_SCOPE_LINK);
res.type = RTN_UNICAST;
/*没有查到路由，并且出接口不为lo*/
goto make_route;
}
if (dev_out)
dev_put(dev_out);
err = -ENETUNREACH;
goto out;
}
/*找到路由*/
free_res = 1;
/*路由指向本地*/
if (res.type == RTN_LOCAL) {
if (!fl.fl4_src)
fl.fl4_src = fl.fl4_dst;
if (dev_out)
dev_put(dev_out);
dev_out = net->loopback_dev;
dev_hold(dev_out);
fl.oif = dev_out->ifindex;
if (res.fi)
fib_info_put(res.fi);
res.fi = NULL;
flags |= RTCF_LOCAL;
goto make_route;
}
/*是否支持多路径路由*/
#ifdef CONFIG_IP_ROUTE_MULTIPATH
if (res.fi->fib_nhs > 1 && fl.oif == 0)
fib_select_multipath(&fl, &res);
else
#endif
if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
fib_select_default(net, &fl, &res);
if (!fl.fl4_src)
fl.fl4_src = FIB_RES_PREFSRC(res);
if (dev_out)
dev_put(dev_out);
dev_out = FIB_RES_DEV(res);
dev_hold(dev_out);
fl.oif = dev_out->ifindex;
/*往cache中添加相应的路由项*/
make_route:
err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
if (free_res)
fib_res_put(&res);
if (dev_out)
dev_put(dev_out);
out: return err;
}

第一次查找ip_dev_find，它比较简单，只是调用ip_fib_local_table -> tb_lookup (ip_fib_local_table, &fl, &res)；它和之后要研究的fib_lookup函数类似，只是不查找ip_fib_main_table：

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;
}

fib_lookup是FIB中做路由搜索的主要的前端函数。首先调用local表的查找函数，然后再调用本地网的查找函数，如果没有找到就返回ENETUNREACH，要注意的是2个表都必须查找。

未完待续。。。