中财网微信软文写手:Linux TCP/IP协议栈笔记（二）路由缓存 - Linux内核探索 - SecPow...
来源：百度文库 编辑：中财网 时间：2024/04/29 06:07:59
Linux TCP/IP协议栈笔记（二）路由缓存
路由缓存
作者：kendo
出处：www.skynet.org.cn
内核版本：2.6.12
2007-4-2
版权所有，转载请注明出处。
1、什么是路由缓存
当数据包进入网络层后，需要做的第一件事情，就是进行路由查找，也即根据数据包的目标地址，查找需要转发的目的网关，当然，实际情况比这个要复杂，查找条件并不仅限于目的地址。
为了提高路由查找的效率，路由子系统引入了路由缓存的概念，用于某个目的地址在路由表中查找到匹配路由项后，就把目的地址对应的路由项缓存起来，可以通过route –C看到路由缓存表：
这样，下一次路由查找时，就先查缓存，没有在缓存中，再去搜索路由表。
不论进入或者是发出的数据，都要在网络层进行路由查找，查找首先在路由缓存中进行，如果命中，则查找完成，如果没有命中，则进入路由表中的查找，如果在表中查找命中，则创建相应的路由缓存项。
2、路由缓存表的组织
如前所述，整个缓存表由一条条地缓存项组成，整个表采用了hash表来组织，如下图。
从这张图中，我们可以看到许多重要的信息：
哈希桶的类型是rt_hash_bucket，该结构只包含指向缓存元素链表的一个指针和一个锁:
[Copy to clipboard] [ - ] CODE: struct rt_hash_bucket {
struct rtable *chain;
spinlock_t lock;
} __attribute__((__aligned__(8)));
chain成员指针自然指向下一个路由缓存项，用于链表的维护，另外，它还包含了一个自旋锁。关于锁的使用，这在后面代码分析中，可以看到。
Chain是一个struct rtable类型的指针，struct rtable用于描述一条完整的路由缓存项，它是路由子系统中，最重要的数据结构之一：
[Copy to clipboard] [ - ] CODE: struct rtable
{
/*
* 第一个成员u，被定义为一个联合体，这非常的重要，因为struct rtable被定义为每一项路由缓存，所以不可避免地在hash表中，存在冲撞的情况，rt_next指针就用来组织冲撞的链表。而另一方面，struct dst_entry结构的第一个成员struct dst_entry *next;也指向了下一个冲撞节点struct rtable中的struct dst_entry，虽然这两个指针rt_next和dst.next的类型不同，但是它们却指向了同一内存位置(因为dst是struct rtable的第一个成员)，这样，巧妙的设计，使得其很容易其享一些数据。一个指向rtable结构的指针可以安全地映射（typecast）为一个指向dst_entry的指针，反之亦然。前面分析哈希表时，说同时用到rt_next和next两个成员指针来维护链表，就是这个道理。
*/
union
{
struct dst_entry dst;
struct rtable *rt_next;
} u;
/*该指针指向egress设备的IP配置块。注意对送往本地的ingress报文的路由，设置的egress设备为loopback设备。*/
struct in_device *idev;
unsigned rt_flags; /*路由标志*/
__u16 rt_type; /*路由类型*/
__u16 rt_multipath_alg; /*多路径缓存算法。该字段是根据相关路由项上配置的算法来初始化*/
__u32 rt_dst; /* 目的IP */
__u32 rt_src; /* 源IP */
/*
Ingress设备标识。这个值是从ingress设备的net_device数据结构中得到。对本地生
成的流量（因此不是从任何接口上接收到的），该字段被设置为出设备的ifindex
字段。不要将该字段与本章后面描述的flowi数据结构fl中的iif字段混淆，对本地生
成的流量，fl中的iif字段被设置为零（loopback_dev）。
*/
int rt_iif;
/*
* 当目的主机为直连时（即在同一链路上），rt_gateway表示目的地址。当需要通过一个网关到达目的地时，
* rt_gateway被设置为由路由项中的下一跳网关。
*/
__u32 rt_gateway;
/* 用于缓存查找的搜索key */
struct flowi fl;
/* Miscellaneous cached information */
__u32 rt_spec_dst; /* RFC1122 specific destination */
/*
inet_peer结构存储有关IP peer的long-living信息，IP peer是该缓存
路由项的目的IP地址对应的主机。与本地主机在最近一段时间通信的每个远端IP
地址都有一个inet_peer结构。
*/
struct inet_peer *peer; /* long-living peer info */
};
第一个成员dst是struct dst_entry类型，它用于存储缓存路由项中独立于协议的信息，因为协议栈中除了IPV4，还有其它网络层协议，如IPV6，还要使用路由子系统。一般是在网络层协议的缓存结构中，包含此结构，以用于存储私有信息，这里我们看到的在struct rtable中包含struct dst_entry就是一个典型的例子：
[Copy to clipboard] [ - ] CODE: struct dst_entry
{
/*用于将分布在同一个哈希桶内的dst_entry实例链接在一起*/
struct dst_entry *next;
/*引用计数*/
atomic_t __refcnt; /* client references */
int __use; /*该表项已经被使用的次数（即缓存查找返回该表项的次数）*/
struct dst_entry *child;
struct net_device *dev; /*Egress设备（即将报文送达目的地的发送设备）*/
/*
当fib_lookup API（只被IPv4使用）失败时，错误值被保存在error（用一个正值）
中，在后面的ip_error中使用该值来决定如何处理本次路由查找失败（即决定生成
哪一类ICMP消息）。
*/
short error;
/*
* 用于定义该dst_entry实例的可用状态：0（缺省值）表示该结构有效而且可以被使
用，2表示该结构将被删除因而不能被使用，-1被IPsec和IPv6使用但不被IPv4使
用。
*/
short obsolete;
/*
* 标志集合（Set of flags）。DST_HOST被TCP使用，表示主机路由（即它不是到网
络或到一个广播/多播地址的路由）。DST_NOXFRM，DST_NOPOLICY和
DST_NOHASH只用于IPsec。
*/
int flags;
#define DST_HOST 1
#define DST_NOXFRM 2
#define DST_NOPOLICY 4
#define DST_NOHASH 8
#define DST_BALANCED 0x10
/*
用于记录该表项上次被使用的时间戳。当缓存查找成功时更新该时间戳，垃圾回
收程序使用该时间戳来选择最合适的应当被释放的结构。
*/
unsigned long lastuse;
unsigned long expires; /*表示该表项将过期的时间戳。*/
unsigned short header_len; /* more space at head required */
unsigned short trailer_len; /* space to reserve at tail */
u32 metrics[RTAX_MAX];
struct dst_entry *path;
unsigned long rate_last; /* 这两个字段被用于对两种类型的ICMP消息限速。 */
unsigned long rate_tokens;
struct neighbour *neighbour; /*neighbour是包含下一跳三层地址到二层地址映射的结构，hh是缓存的二层头。*/
struct hh_cache *hh;
struct xfrm_state *xfrm;
/*分别表示处理ingress报文和处理egress报文的函数。参见第33章“缓存查找”小节。*/
int (*input)(struct sk_buff*);
int (*output)(struct sk_buff*);
#ifdef CONFIG_NET_CLS_ROUTE
__u32 tclassid; /*基于路由表的classifier的标签。*/
#endif
struct dst_ops *ops; /*该结构内的虚函数表（VFT）用于处理dst_entry结构。*/
struct rcu_head rcu_head;
char info[0];
};
当然，结构是复杂的，可以暂时跳过其成员的含义，大约知道这个结构是拿来做什么的就可以了，我们在代码分析中，再回过头来分析其成员变量的含义。
左牵黄，右擎苍，老夫聊发少年狂
kendo (九贱)
管理员
UID 1
精华 1
积分 10
帖子 86
阅读权限 200
注册 2006-11-27
来自 中国重庆
状态 离线 #2 使用道具 发表于 2007-4-2 11:24 资料 个人空间 主页 短消息 加为好友
2、缓存的初始化
明白了缓存hash表，现在来看这个表是如何被组织起来的：
net/ipv4/route.c
int __init ip_rt_init(void)
{
……
ipv4_dst_ops.kmem_cachep = kmem_cache_create("ip_dst_cache",
sizeof(struct rtable),
0, SLAB_HWCACHE_ALIGN,
NULL, NULL);
if (!ipv4_dst_ops.kmem_cachep)
panic("IP: failed to allocate ip_dst_cache\n");
//计算出最大可需要的内存空间
goal = num_physpages >> (26 - PAGE_SHIFT);
if (rhash_entries)
goal = (rhash_entries * sizeof(struct rt_hash_bucket)) >> PAGE_SHIFT;
//该循环计算出此内存空间，需要的最大的order数
for (order = 0; (1UL << order) < goal; order++)
/* NOTHING */;
do {
//1UL << order，计算出分配的页面，再乘上页面大小，除以桶大小，计算出共可以有多少个hash桶
rt_hash_mask = (1UL << order) * PAGE_SIZE /
sizeof(struct rt_hash_bucket);
while (rt_hash_mask & (rt_hash_mask - 1))
rt_hash_mask--;
//分配hash表空间，它共有rt_hash_mask个桶
rt_hash_table = (struct rt_hash_bucket *)
__get_free_pages(GFP_ATOMIC, order);
} while (rt_hash_table == NULL && --order > 0);
//上面这个while循环在分配失败后，一直尝试递减order，再尝试分配，直至分配分功或者order为0
if (!rt_hash_table)
panic("Failed to allocate IP route cache hash table\n");
……
}
初始化工作中，主要完成内存的计算，hash桶的空间的分配工作，这样，所有链表的链表首部就被建立起来了。整个hash表的框架就被建立起来了。当一个缓存项需要被加入至这个表中，就根据相应的hash算法计算出hash值，然后使用rt_hash_table[hash]定位到链表的入口，利用前文所述的struct rt_hash_bucket结构的chain成员组织链表，将其加入即可。因为我这里主要分析数据流的转发，重点是查找工作，缓存表的插入／删除／垃圾回收等工作，就不在这里一一详细分析了。
左牵黄，右擎苍，老夫聊发少年狂 kendo (九贱)
管理员
UID 1
精华 1
积分 10
帖子 86
阅读权限 200
注册 2006-11-27
来自 中国重庆
状态 离线 #3 使用道具 发表于 2007-4-2 11:31 资料 个人空间 主页 短消息 加为好友 3、缓存的查找
当数据包进入网络层后，第一个被调用的函数是ip_rcv函数：
[Copy to clipboard] [ - ] CODE: /* Main IP Receive routine. */
int ip_rcv(struct sk_buff *skb, struct net_device *dev, struct packet_type *pt)
{
struct iphdr *iph;
/* 混杂模式下，数据将被丢弃 */
if (skb->pkt_type == PACKET_OTHERHOST)
goto drop;
/*更新SNMP统计修筑*/
IP_INC_STATS_BH(IPSTATS_MIB_INRECEIVES);
/*skb_share_check用于skb的共享检查，如果有别人已经在使用了，则克隆一份给自己使用*/
if ((skb = skb_share_check(skb, GFP_ATOMIC)) == NULL) {
IP_INC_STATS_BH(IPSTATS_MIB_INDISCARDS);
goto out;
}
/*一个正确的IP包，包长度应该大于或等于包首部长度*/
if (!pskb_may_pull(skb, sizeof(struct iphdr)))
goto inhdr_error;
/*取得IP首部*/
iph = skb->nh.iph;
/*
* RFC1122: 3.1.2.2 MUST silently discard any IP frame that fails the checksum.
*
* Is the datagram acceptable?
*
* 1. Length at least the size of an ip header
* 2. Version of 4
* 3. Checksums correctly. [Speed optimisation for later, skip loopback checksums]
* 4. Doesn't have a bogus length
*/
/*长度和版本检查*/
if (iph->ihl < 5 || iph->version != 4)
goto inhdr_error;
if (!pskb_may_pull(skb, iph->ihl*4))
goto inhdr_error;
/*因为如果运行不好，上边pskb_may_pull函数会进一步去调用__pskb_pull_tail函数，去以完成补全数据包的页外数据的工作，把碎片部分
的数据线性重组，所以，有必要重置iph指针，以指向正确的ip 首部*/
iph = skb->nh.iph;
/*校验和检查*/
if (ip_fast_csum((u8 *)iph, iph->ihl) != 0)
goto inhdr_error;
{
__u32 len = ntohs(iph->tot_len);
if (skb->len < len || len < (iph->ihl<<2))
goto inhdr_error;
/* Our transport medium may have padded the buffer out. Now we know it
* is IP we can trim to the true length of the frame.
* Note this now means skb->len holds ntohs(iph->tot_len).
*/
if (pskb_trim_rcsum(skb, len)) {
IP_INC_STATS_BH(IPSTATS_MIB_INDISCARDS);
goto drop;
}
}
/*进入Netfilter钩子，处理完后，继续执行ip_rcv_finish */
return NF_HOOK(PF_INET, NF_IP_PRE_ROUTING, skb, dev, NULL,
ip_rcv_finish);
inhdr_error:
IP_INC_STATS_BH(IPSTATS_MIB_INHDRERRORS);
drop:
kfree_skb(skb);
out:
return NET_RX_DROP;
}
这一部份代码，简而言之，就是取得IP首部，进行合法性检查，然后调用ip_rcv_finish函数，关于Netfilter的更多内容，请参考九贱的《Linux防火墙设计与Nefilter源码分析》。
ip_rcv_finish 要做的第一件事情，就是调用ip_route_input函数进行缓存查找：
[Copy to clipboard] [ - ] CODE: static inline int ip_rcv_finish(struct sk_buff *skb)
{
struct net_device *dev = skb->dev;
struct iphdr *iph = skb->nh.iph;
/*
* Initialise the virtual path cache for the packet. It describes
* how the packet travels inside Linux networking.
*/
if (skb->dst == NULL) {
if (ip_route_input(skb, iph->daddr, iph->saddr, iph->tos, dev))
goto drop;
}
……
这就进入我们本章的主题了，接下来看看ip_route_input是如何进行缓存查找的。
[Copy to clipboard] [ - ] CODE: int ip_route_input(struct sk_buff *skb, //数据包
u32 daddr, u32 saddr, //目的地址和源地址
u8 tos, //TOS
struct net_device *dev) //输入设备
{
struct rtable * rth;
unsigned hash;
int iif = dev->ifindex;
tos &= IPTOS_RT_MASK;
hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
rcu_read_lock();
for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.rt_next)) {
if (rth->fl.fl4_dst == daddr &&
rth->fl.fl4_src == saddr &&
rth->fl.iif == iif &&
rth->fl.oif == 0 &&
#ifdef CONFIG_IP_ROUTE_FWMARK
rth->fl.fl4_fwmark == skb->nfmark &&
#endif
rth->fl.fl4_tos == tos) {
rth->u.dst.lastuse = jiffies;
dst_hold(&rth->u.dst);
rth->u.dst.__use++;
RT_CACHE_STAT_INC(in_hit);
rcu_read_unlock();
skb->dst = (struct dst_entry*)rth;
return 0;
}
RT_CACHE_STAT_INC(in_hlist_search);
}
rcu_read_unlock();
if (MULTICAST(daddr)) {
struct in_device *in_dev;
rcu_read_lock();
if ((in_dev = __in_dev_get(dev)) != NULL) {
int our = ip_check_mc(in_dev, daddr, saddr,
skb->nh.iph->protocol);
if (our
#ifdef CONFIG_IP_MROUTE
|| (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
#endif
) {
rcu_read_unlock();
return ip_route_input_mc(skb, daddr, saddr,
tos, dev, our);
}
}
rcu_read_unlock();
return -EINVAL;
}
return ip_route_input_slow(skb, daddr, saddr, tos, dev);
}
函数的第一个工作，就是根据目的地址、源地址、接口索引和TOS值计算hash值
[Copy to clipboard] [ - ] CODE: hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
这里用到了rcu锁，关于这个锁的更多内容，可以参考其它相关资料。宏rcu_dereference在RCU读临界部份中取出一个RCU保护的指针。在需要内存屏障的体系中进行内存屏障：
[Copy to clipboard] [ - ] CODE: #define rcu_dereference(p) ({ \
typeof(p) _________p1 = p; \
smp_read_barrier_depends(); \
(_________p1); \
})
于是，我们有了hash值后，就可以在hash桶中直接找到链表入口：
[Copy to clipboard] [ - ] CODE: struct rtable * rth;
rth = rcu_dereference(rt_hash_table[hash].chain);
如果要遍历该链表中的所有路由缓存项，就可以使用如下循环：
[Copy to clipboard] [ - ] CODE: for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.rt_next)) {
……
}
遍历每一个缓存项就简单，重要的是如何将缓存中的路由特征同数据包的特征值进行匹配。
struct rtable中的fl成员，用于存储相关的路由特征值，也就是路由缓存查找匹配的关键字，它是一个struct flowi结构类型：
[Copy to clipboard] [ - ] CODE: struct flowi {
/*Egress设备ID和ingress设备ID*/
int oif;
int iif;
/*该联合的各个字段是可用于指定L3参数取值的结构。目前支持的协议为IPv4，IPv6和DECnet。*/
union {
struct {
__u32 daddr;
__u32 saddr;
__u32 fwmark;
__u8 tos;
__u8 scope;
} ip4_u;
struct {
struct in6_addr daddr;
struct in6_addr saddr;
__u32 flowlabel;
} ip6_u;
struct {
__u16 daddr;
__u16 saddr;
__u32 fwmark;
__u8 scope;
} dn_u;
} nl_u;
#define fld_dst nl_u.dn_u.daddr
#define fld_src nl_u.dn_u.saddr
#define fld_fwmark nl_u.dn_u.fwmark
#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_fwmark nl_u.ip4_u.fwmark
#define fl4_tos nl_u.ip4_u.tos
#define fl4_scope nl_u.ip4_u.scope
/*L4协议*/
__u8 proto;
/*该变量只定义了一个标志，FLOWI_FLAG_MULTIPATHOLDROUTE，它最初用于多路径代码，但已不再被使用。*/
__u8 flags;
#define FLOWI_FLAG_MULTIPATHOLDROUTE 0x01
/*该联合的各个字段是可用于指定L4参数取值的主要结构。目前支持的协议为TCP,UDP，ICMP，DECnet和IPsec协议套件（suite）*/
union {
struct {
__u16 sport;
__u16 dport;
} ports;
struct {
__u8 type;
__u8 code;
} icmpt;
struct {
__u16 sport;
__u16 dport;
__u8 objnum;
__u8 objnamel; /* Not 16 bits since max val is 16 */
__u8 objname[16]; /* Not zero terminated */
} dnports;
__u32 spi;
} 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
} __attribute__((__aligned__(BITS_PER_LONG/8)));
抛开其它协议和成员，联合体成员ip4_u就是IPV4协议关心的东东了：
[Copy to clipboard] [ - ] CODE: struct {
__u32 daddr;
__u32 saddr;
__u32 fwmark;
__u8 tos;
__u8 scope;
} ip4_u;
于是，在遍历路由缓存项时，就可以使用如下语句来匹配路由缓存：
[Copy to clipboard] [ - ] CODE: if (rth->fl.fl4_dst == daddr &&
rth->fl.fl4_src == saddr &&
rth->fl.iif == iif &&
rth->fl.oif == 0 &&
#ifdef CONFIG_IP_ROUTE_FWMARK
rth->fl.fl4_fwmark == skb->nfmark &&
#endif
rth->fl.fl4_tos == tos)
分别对来源/目的地址，输入/输出设备，Netfilter防火墙的标记值和TOS值进行匹配。如果手气好，查找命中了：
[Copy to clipboard] [ - ] CODE: rth->u.dst.lastuse = jiffies; //更新最近使用时间标记
dst_hold(&rth->u.dst);
rth->u.dst.__use++; //更新缓存使用记数器
RT_CACHE_STAT_INC(in_hit);
rcu_read_unlock();
[b]skb->dst = (struct dst_entry*)rth; //设置skb的dst指针指向路由缓存项[/b]
return 0;
如果没有查到，怎么办？
当然，不是次次都能糊清一色的，如果没有命中的话，就要去查到路由表了。可以推想，网络栈在缓存查找没有命中后，会去搜索路由表，如果路由表匹配，会将由于产生的路由缓存项插入缓存表，以待下一次使用。关于路由表查找的相关内容，我会在下一章中分析。
路由缓存
作者：kendo
出处：www.skynet.org.cn
内核版本：2.6.12
2007-4-2
版权所有，转载请注明出处。
1、什么是路由缓存
当数据包进入网络层后，需要做的第一件事情，就是进行路由查找，也即根据数据包的目标地址，查找需要转发的目的网关，当然，实际情况比这个要复杂，查找条件并不仅限于目的地址。
为了提高路由查找的效率，路由子系统引入了路由缓存的概念，用于某个目的地址在路由表中查找到匹配路由项后，就把目的地址对应的路由项缓存起来，可以通过route –C看到路由缓存表：
这样，下一次路由查找时，就先查缓存，没有在缓存中，再去搜索路由表。
不论进入或者是发出的数据，都要在网络层进行路由查找，查找首先在路由缓存中进行，如果命中，则查找完成，如果没有命中，则进入路由表中的查找，如果在表中查找命中，则创建相应的路由缓存项。
2、路由缓存表的组织
如前所述，整个缓存表由一条条地缓存项组成，整个表采用了hash表来组织，如下图。
从这张图中，我们可以看到许多重要的信息：
- hash桶的大小由变量rt_hash_mask决定，它是决定路由缓存大小的重要因素；
- 每一个hash桶的项，是由结构struct rt_hash_bucket；
- 每一个路由缓存项，是由结构struct rtable结构描述的，它的rt_next/next成员来组织链表的；为什么是两个成员指针而不仅仅是一个next，这在后面来分析；
- struct rtable缓存项中，还包含了一个struct dst_entry结构；
哈希桶的类型是rt_hash_bucket，该结构只包含指向缓存元素链表的一个指针和一个锁:
[Copy to clipboard] [ - ] CODE: struct rt_hash_bucket {
struct rtable *chain;
spinlock_t lock;
} __attribute__((__aligned__(8)));
chain成员指针自然指向下一个路由缓存项，用于链表的维护，另外，它还包含了一个自旋锁。关于锁的使用，这在后面代码分析中，可以看到。
Chain是一个struct rtable类型的指针，struct rtable用于描述一条完整的路由缓存项，它是路由子系统中，最重要的数据结构之一：
[Copy to clipboard] [ - ] CODE: struct rtable
{
/*
* 第一个成员u，被定义为一个联合体，这非常的重要，因为struct rtable被定义为每一项路由缓存，所以不可避免地在hash表中，存在冲撞的情况，rt_next指针就用来组织冲撞的链表。而另一方面，struct dst_entry结构的第一个成员struct dst_entry *next;也指向了下一个冲撞节点struct rtable中的struct dst_entry，虽然这两个指针rt_next和dst.next的类型不同，但是它们却指向了同一内存位置(因为dst是struct rtable的第一个成员)，这样，巧妙的设计，使得其很容易其享一些数据。一个指向rtable结构的指针可以安全地映射（typecast）为一个指向dst_entry的指针，反之亦然。前面分析哈希表时，说同时用到rt_next和next两个成员指针来维护链表，就是这个道理。
*/
union
{
struct dst_entry dst;
struct rtable *rt_next;
} u;
/*该指针指向egress设备的IP配置块。注意对送往本地的ingress报文的路由，设置的egress设备为loopback设备。*/
struct in_device *idev;
unsigned rt_flags; /*路由标志*/
__u16 rt_type; /*路由类型*/
__u16 rt_multipath_alg; /*多路径缓存算法。该字段是根据相关路由项上配置的算法来初始化*/
__u32 rt_dst; /* 目的IP */
__u32 rt_src; /* 源IP */
/*
Ingress设备标识。这个值是从ingress设备的net_device数据结构中得到。对本地生
成的流量（因此不是从任何接口上接收到的），该字段被设置为出设备的ifindex
字段。不要将该字段与本章后面描述的flowi数据结构fl中的iif字段混淆，对本地生
成的流量，fl中的iif字段被设置为零（loopback_dev）。
*/
int rt_iif;
/*
* 当目的主机为直连时（即在同一链路上），rt_gateway表示目的地址。当需要通过一个网关到达目的地时，
* rt_gateway被设置为由路由项中的下一跳网关。
*/
__u32 rt_gateway;
/* 用于缓存查找的搜索key */
struct flowi fl;
/* Miscellaneous cached information */
__u32 rt_spec_dst; /* RFC1122 specific destination */
/*
inet_peer结构存储有关IP peer的long-living信息，IP peer是该缓存
路由项的目的IP地址对应的主机。与本地主机在最近一段时间通信的每个远端IP
地址都有一个inet_peer结构。
*/
struct inet_peer *peer; /* long-living peer info */
};
第一个成员dst是struct dst_entry类型，它用于存储缓存路由项中独立于协议的信息，因为协议栈中除了IPV4，还有其它网络层协议，如IPV6，还要使用路由子系统。一般是在网络层协议的缓存结构中，包含此结构，以用于存储私有信息，这里我们看到的在struct rtable中包含struct dst_entry就是一个典型的例子：
[Copy to clipboard] [ - ] CODE: struct dst_entry
{
/*用于将分布在同一个哈希桶内的dst_entry实例链接在一起*/
struct dst_entry *next;
/*引用计数*/
atomic_t __refcnt; /* client references */
int __use; /*该表项已经被使用的次数（即缓存查找返回该表项的次数）*/
struct dst_entry *child;
struct net_device *dev; /*Egress设备（即将报文送达目的地的发送设备）*/
/*
当fib_lookup API（只被IPv4使用）失败时，错误值被保存在error（用一个正值）
中，在后面的ip_error中使用该值来决定如何处理本次路由查找失败（即决定生成
哪一类ICMP消息）。
*/
short error;
/*
* 用于定义该dst_entry实例的可用状态：0（缺省值）表示该结构有效而且可以被使
用，2表示该结构将被删除因而不能被使用，-1被IPsec和IPv6使用但不被IPv4使
用。
*/
short obsolete;
/*
* 标志集合（Set of flags）。DST_HOST被TCP使用，表示主机路由（即它不是到网
络或到一个广播/多播地址的路由）。DST_NOXFRM，DST_NOPOLICY和
DST_NOHASH只用于IPsec。
*/
int flags;
#define DST_HOST 1
#define DST_NOXFRM 2
#define DST_NOPOLICY 4
#define DST_NOHASH 8
#define DST_BALANCED 0x10
/*
用于记录该表项上次被使用的时间戳。当缓存查找成功时更新该时间戳，垃圾回
收程序使用该时间戳来选择最合适的应当被释放的结构。
*/
unsigned long lastuse;
unsigned long expires; /*表示该表项将过期的时间戳。*/
unsigned short header_len; /* more space at head required */
unsigned short trailer_len; /* space to reserve at tail */
u32 metrics[RTAX_MAX];
struct dst_entry *path;
unsigned long rate_last; /* 这两个字段被用于对两种类型的ICMP消息限速。 */
unsigned long rate_tokens;
struct neighbour *neighbour; /*neighbour是包含下一跳三层地址到二层地址映射的结构，hh是缓存的二层头。*/
struct hh_cache *hh;
struct xfrm_state *xfrm;
/*分别表示处理ingress报文和处理egress报文的函数。参见第33章“缓存查找”小节。*/
int (*input)(struct sk_buff*);
int (*output)(struct sk_buff*);
#ifdef CONFIG_NET_CLS_ROUTE
__u32 tclassid; /*基于路由表的classifier的标签。*/
#endif
struct dst_ops *ops; /*该结构内的虚函数表（VFT）用于处理dst_entry结构。*/
struct rcu_head rcu_head;
char info[0];
};
当然，结构是复杂的，可以暂时跳过其成员的含义，大约知道这个结构是拿来做什么的就可以了，我们在代码分析中，再回过头来分析其成员变量的含义。
左牵黄，右擎苍，老夫聊发少年狂
kendo (九贱) 管理员
UID 1
精华 1
积分 10
帖子 86
阅读权限 200
注册 2006-11-27
来自 中国重庆
状态 离线 #2 使用道具 发表于 2007-4-2 11:24 资料 个人空间 主页 短消息 加为好友
2、缓存的初始化明白了缓存hash表，现在来看这个表是如何被组织起来的：
net/ipv4/route.c
int __init ip_rt_init(void)
{
……
ipv4_dst_ops.kmem_cachep = kmem_cache_create("ip_dst_cache",
sizeof(struct rtable),
0, SLAB_HWCACHE_ALIGN,
NULL, NULL);
if (!ipv4_dst_ops.kmem_cachep)
panic("IP: failed to allocate ip_dst_cache\n");
//计算出最大可需要的内存空间
goal = num_physpages >> (26 - PAGE_SHIFT);
if (rhash_entries)
goal = (rhash_entries * sizeof(struct rt_hash_bucket)) >> PAGE_SHIFT;
//该循环计算出此内存空间，需要的最大的order数
for (order = 0; (1UL << order) < goal; order++)
/* NOTHING */;
do {
//1UL << order，计算出分配的页面，再乘上页面大小，除以桶大小，计算出共可以有多少个hash桶
rt_hash_mask = (1UL << order) * PAGE_SIZE /
sizeof(struct rt_hash_bucket);
while (rt_hash_mask & (rt_hash_mask - 1))
rt_hash_mask--;
//分配hash表空间，它共有rt_hash_mask个桶
rt_hash_table = (struct rt_hash_bucket *)
__get_free_pages(GFP_ATOMIC, order);
} while (rt_hash_table == NULL && --order > 0);
//上面这个while循环在分配失败后，一直尝试递减order，再尝试分配，直至分配分功或者order为0
if (!rt_hash_table)
panic("Failed to allocate IP route cache hash table\n");
……
}
初始化工作中，主要完成内存的计算，hash桶的空间的分配工作，这样，所有链表的链表首部就被建立起来了。整个hash表的框架就被建立起来了。当一个缓存项需要被加入至这个表中，就根据相应的hash算法计算出hash值，然后使用rt_hash_table[hash]定位到链表的入口，利用前文所述的struct rt_hash_bucket结构的chain成员组织链表，将其加入即可。因为我这里主要分析数据流的转发，重点是查找工作，缓存表的插入／删除／垃圾回收等工作，就不在这里一一详细分析了。
左牵黄，右擎苍，老夫聊发少年狂
kendo (九贱) 管理员
UID 1
精华 1
积分 10
帖子 86
阅读权限 200
注册 2006-11-27
来自 中国重庆
状态 离线 #3 使用道具 发表于 2007-4-2 11:31 资料 个人空间 主页 短消息 加为好友
3、缓存的查找当数据包进入网络层后，第一个被调用的函数是ip_rcv函数：
[Copy to clipboard] [ - ] CODE: /* Main IP Receive routine. */
int ip_rcv(struct sk_buff *skb, struct net_device *dev, struct packet_type *pt)
{
struct iphdr *iph;
/* 混杂模式下，数据将被丢弃 */
if (skb->pkt_type == PACKET_OTHERHOST)
goto drop;
/*更新SNMP统计修筑*/
IP_INC_STATS_BH(IPSTATS_MIB_INRECEIVES);
/*skb_share_check用于skb的共享检查，如果有别人已经在使用了，则克隆一份给自己使用*/
if ((skb = skb_share_check(skb, GFP_ATOMIC)) == NULL) {
IP_INC_STATS_BH(IPSTATS_MIB_INDISCARDS);
goto out;
}
/*一个正确的IP包，包长度应该大于或等于包首部长度*/
if (!pskb_may_pull(skb, sizeof(struct iphdr)))
goto inhdr_error;
/*取得IP首部*/
iph = skb->nh.iph;
/*
* RFC1122: 3.1.2.2 MUST silently discard any IP frame that fails the checksum.
*
* Is the datagram acceptable?
*
* 1. Length at least the size of an ip header
* 2. Version of 4
* 3. Checksums correctly. [Speed optimisation for later, skip loopback checksums]
* 4. Doesn't have a bogus length
*/
/*长度和版本检查*/
if (iph->ihl < 5 || iph->version != 4)
goto inhdr_error;
if (!pskb_may_pull(skb, iph->ihl*4))
goto inhdr_error;
/*因为如果运行不好，上边pskb_may_pull函数会进一步去调用__pskb_pull_tail函数，去以完成补全数据包的页外数据的工作，把碎片部分
的数据线性重组，所以，有必要重置iph指针，以指向正确的ip 首部*/
iph = skb->nh.iph;
/*校验和检查*/
if (ip_fast_csum((u8 *)iph, iph->ihl) != 0)
goto inhdr_error;
{
__u32 len = ntohs(iph->tot_len);
if (skb->len < len || len < (iph->ihl<<2))
goto inhdr_error;
/* Our transport medium may have padded the buffer out. Now we know it
* is IP we can trim to the true length of the frame.
* Note this now means skb->len holds ntohs(iph->tot_len).
*/
if (pskb_trim_rcsum(skb, len)) {
IP_INC_STATS_BH(IPSTATS_MIB_INDISCARDS);
goto drop;
}
}
/*进入Netfilter钩子，处理完后，继续执行ip_rcv_finish */
return NF_HOOK(PF_INET, NF_IP_PRE_ROUTING, skb, dev, NULL,
ip_rcv_finish);
inhdr_error:
IP_INC_STATS_BH(IPSTATS_MIB_INHDRERRORS);
drop:
kfree_skb(skb);
out:
return NET_RX_DROP;
}
这一部份代码，简而言之，就是取得IP首部，进行合法性检查，然后调用ip_rcv_finish函数，关于Netfilter的更多内容，请参考九贱的《Linux防火墙设计与Nefilter源码分析》。
ip_rcv_finish 要做的第一件事情，就是调用ip_route_input函数进行缓存查找：
[Copy to clipboard] [ - ] CODE: static inline int ip_rcv_finish(struct sk_buff *skb)
{
struct net_device *dev = skb->dev;
struct iphdr *iph = skb->nh.iph;
/*
* Initialise the virtual path cache for the packet. It describes
* how the packet travels inside Linux networking.
*/
if (skb->dst == NULL) {
if (ip_route_input(skb, iph->daddr, iph->saddr, iph->tos, dev))
goto drop;
}
……
这就进入我们本章的主题了，接下来看看ip_route_input是如何进行缓存查找的。
[Copy to clipboard] [ - ] CODE: int ip_route_input(struct sk_buff *skb, //数据包
u32 daddr, u32 saddr, //目的地址和源地址
u8 tos, //TOS
struct net_device *dev) //输入设备
{
struct rtable * rth;
unsigned hash;
int iif = dev->ifindex;
tos &= IPTOS_RT_MASK;
hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
rcu_read_lock();
for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.rt_next)) {
if (rth->fl.fl4_dst == daddr &&
rth->fl.fl4_src == saddr &&
rth->fl.iif == iif &&
rth->fl.oif == 0 &&
#ifdef CONFIG_IP_ROUTE_FWMARK
rth->fl.fl4_fwmark == skb->nfmark &&
#endif
rth->fl.fl4_tos == tos) {
rth->u.dst.lastuse = jiffies;
dst_hold(&rth->u.dst);
rth->u.dst.__use++;
RT_CACHE_STAT_INC(in_hit);
rcu_read_unlock();
skb->dst = (struct dst_entry*)rth;
return 0;
}
RT_CACHE_STAT_INC(in_hlist_search);
}
rcu_read_unlock();
if (MULTICAST(daddr)) {
struct in_device *in_dev;
rcu_read_lock();
if ((in_dev = __in_dev_get(dev)) != NULL) {
int our = ip_check_mc(in_dev, daddr, saddr,
skb->nh.iph->protocol);
if (our
#ifdef CONFIG_IP_MROUTE
|| (!LOCAL_MCAST(daddr) && IN_DEV_MFORWARD(in_dev))
#endif
) {
rcu_read_unlock();
return ip_route_input_mc(skb, daddr, saddr,
tos, dev, our);
}
}
rcu_read_unlock();
return -EINVAL;
}
return ip_route_input_slow(skb, daddr, saddr, tos, dev);
}
函数的第一个工作，就是根据目的地址、源地址、接口索引和TOS值计算hash值
[Copy to clipboard] [ - ] CODE: hash = rt_hash_code(daddr, saddr ^ (iif << 5), tos);
这里用到了rcu锁，关于这个锁的更多内容，可以参考其它相关资料。宏rcu_dereference在RCU读临界部份中取出一个RCU保护的指针。在需要内存屏障的体系中进行内存屏障：
[Copy to clipboard] [ - ] CODE: #define rcu_dereference(p) ({ \
typeof(p) _________p1 = p; \
smp_read_barrier_depends(); \
(_________p1); \
})
于是，我们有了hash值后，就可以在hash桶中直接找到链表入口：
[Copy to clipboard] [ - ] CODE: struct rtable * rth;
rth = rcu_dereference(rt_hash_table[hash].chain);
如果要遍历该链表中的所有路由缓存项，就可以使用如下循环：
[Copy to clipboard] [ - ] CODE: for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
rth = rcu_dereference(rth->u.rt_next)) {
……
}
遍历每一个缓存项就简单，重要的是如何将缓存中的路由特征同数据包的特征值进行匹配。
struct rtable中的fl成员，用于存储相关的路由特征值，也就是路由缓存查找匹配的关键字，它是一个struct flowi结构类型：
[Copy to clipboard] [ - ] CODE: struct flowi {
/*Egress设备ID和ingress设备ID*/
int oif;
int iif;
/*该联合的各个字段是可用于指定L3参数取值的结构。目前支持的协议为IPv4，IPv6和DECnet。*/
union {
struct {
__u32 daddr;
__u32 saddr;
__u32 fwmark;
__u8 tos;
__u8 scope;
} ip4_u;
struct {
struct in6_addr daddr;
struct in6_addr saddr;
__u32 flowlabel;
} ip6_u;
struct {
__u16 daddr;
__u16 saddr;
__u32 fwmark;
__u8 scope;
} dn_u;
} nl_u;
#define fld_dst nl_u.dn_u.daddr
#define fld_src nl_u.dn_u.saddr
#define fld_fwmark nl_u.dn_u.fwmark
#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_fwmark nl_u.ip4_u.fwmark
#define fl4_tos nl_u.ip4_u.tos
#define fl4_scope nl_u.ip4_u.scope
/*L4协议*/
__u8 proto;
/*该变量只定义了一个标志，FLOWI_FLAG_MULTIPATHOLDROUTE，它最初用于多路径代码，但已不再被使用。*/
__u8 flags;
#define FLOWI_FLAG_MULTIPATHOLDROUTE 0x01
/*该联合的各个字段是可用于指定L4参数取值的主要结构。目前支持的协议为TCP,UDP，ICMP，DECnet和IPsec协议套件（suite）*/
union {
struct {
__u16 sport;
__u16 dport;
} ports;
struct {
__u8 type;
__u8 code;
} icmpt;
struct {
__u16 sport;
__u16 dport;
__u8 objnum;
__u8 objnamel; /* Not 16 bits since max val is 16 */
__u8 objname[16]; /* Not zero terminated */
} dnports;
__u32 spi;
} 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
} __attribute__((__aligned__(BITS_PER_LONG/8)));
抛开其它协议和成员，联合体成员ip4_u就是IPV4协议关心的东东了：
[Copy to clipboard] [ - ] CODE: struct {
__u32 daddr;
__u32 saddr;
__u32 fwmark;
__u8 tos;
__u8 scope;
} ip4_u;
于是，在遍历路由缓存项时，就可以使用如下语句来匹配路由缓存：
[Copy to clipboard] [ - ] CODE: if (rth->fl.fl4_dst == daddr &&
rth->fl.fl4_src == saddr &&
rth->fl.iif == iif &&
rth->fl.oif == 0 &&
#ifdef CONFIG_IP_ROUTE_FWMARK
rth->fl.fl4_fwmark == skb->nfmark &&
#endif
rth->fl.fl4_tos == tos)
分别对来源/目的地址，输入/输出设备，Netfilter防火墙的标记值和TOS值进行匹配。如果手气好，查找命中了：
[Copy to clipboard] [ - ] CODE: rth->u.dst.lastuse = jiffies; //更新最近使用时间标记
dst_hold(&rth->u.dst);
rth->u.dst.__use++; //更新缓存使用记数器
RT_CACHE_STAT_INC(in_hit);
rcu_read_unlock();
[b]skb->dst = (struct dst_entry*)rth; //设置skb的dst指针指向路由缓存项[/b]
return 0;
如果没有查到，怎么办？
当然，不是次次都能糊清一色的，如果没有命中的话，就要去查到路由表了。可以推想，网络栈在缓存查找没有命中后，会去搜索路由表，如果路由表匹配，会将由于产生的路由缓存项插入缓存表，以待下一次使用。关于路由表查找的相关内容，我会在下一章中分析。