路由表
在内核中存在路由表fib_table_hash和路由缓存表rt_hash_table。路由缓存表主要是为了加速路由的查找,每次路由查询都会先查找路由缓存,再查找路由表。这和cache是一个道理,缓存存储最近使用过的路由项,容量小,查找快速;路由表存储所有路由项,容量大,查找慢。
首先,应该先了解路由表的意义,下面是route命令查看到的路由表:
Destination |
Netmask |
Gateway |
Flags |
Interface |
Metric |
169.254.0.0 |
255.255.0.0 |
* |
U |
eth0 |
1 |
192.168.123.0 |
255.255.255.0 |
* |
U |
eth0 |
1 |
default |
0.0.0.0 |
192.168.123.254 |
UG |
eth0 |
1 |
一条路由其实就是告知主机要到达一个目的地址,下一跳应该走哪里。比如发往192.168.22.3报文通过查路由表,会得到下一跳为192.168.123.254,再将其发送出去。在路由表项中,还有一个很重要的属性-scope,它代表了到目的网络的距离。
路由scope可取值:RT_SCOPE_UNIVERSE,
RT_SCOPE_LINK, RT_SCOPE_HOST
在报文的转发过程中,显然是每次转发都要使到达目的网络的距离要越来越小或不变,否则根本到达不了目的网络。上面提到的scope很好的实现这个功能,在查找路由表中,表项的scope一定是更小或相等的scope(比如RT_SCOPE_LINK,则表项scope只能为RT_SCOPE_LINK或RT_SCOPE_HOST)。
路由缓存
路由缓存用于加速路由的查找,当收到报文或发送报文时,首先会查询路由缓存,在内核中被组织成hash表,就是rt_hash_table。
static struct rt_hash_bucket
*rt_hash_table __read_mostly;
[net/ipv4/route.c]
通过ip_route_input()进行查询,首先是缓存操作时,通过[src_ip,
dst_ip, iif,rt_genid]计算出hash值
hash = rt_hash(daddr, saddr, iif, rt_genid(net));
此时rt_hash_table[hash].chain就是要操作的缓存表项的链表,比如遍历该链表
for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.dst.rt_next)
因此,在缓存中查找一个表项,首先计算出hash值,取出这组表项,然后遍历链表,找出指定的表项,这里需要完全匹配[src_ip,
dst_ip, iif, tos, mark, net],实际上struct rtable中有专门的属性用于缓存的查找键值
– struct flowi。
/* Cache lookup keys */
struct flowi
fl;
当找到表项后会更新表项的最后访问时间,并取出dst
dst_use(&rth->u.dst, jiffies);
skb_dst_set(skb, &rth->u.dst);
路由缓存的创建
inet_init() -> ip_init() -> ip_rt_init()
rt_hash_table = (struct rt_hash_bucket *)
alloc_large_system_hash("IP route cache",
sizeof(struct rt_hash_bucket),
rhash_entries,
(totalram_pages >= 128 * 1024) ?
15 : 17,
0,
&rt_hash_log,
&rt_hash_mask,
rhash_entries ? 0 : 512 * 1024);
其中rt_hash_mask表示表的大小,rt_hash_log
= log(rt_hash_mask),创建后的结构如图所示:
路由缓存插入条目
函数rt_intern_hash()
要插入的条目是rt,相应散列值是hash,首先通过hash值找到对应的bucket
rthp = &rt_hash_table[hash].chain;
然后对bucket进行一遍查询,这次查询的目的有两个:如果是超时的条目,则直接删除;如果是与rt相同键值的条目,则删除并将rt插入头部返回。
while ((rth = *rthp) != NULL) {
if (rt_is_expired(rth)) { // 超时的条目
*rthp = rth->u.dst.rt_next;
rt_free(rth);
continue;
}
if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) { //重复的条目
*rthp = rth->u.dst.rt_next;
rcu_assign_pointer(rth->u.dst.rt_next, rt_hash_table[hash].chain);
rcu_assign_pointer(rt_hash_table[hash].chain, rth);
……
}
……
rthp = &rth->u.dst.rt_next;
}
在扫描一遍后,如rt还未存在,则将其插入头部
rt->u.dst.rt_next = rt_hash_table[hash].chain;
rcu_assign_pointer(rt_hash_table[hash].chain, rt);
如果新插入rt满足一定条件,还要与ARP邻居表进行绑定
Hint:缓存的每个bucket是没有头结点的,单向链表,它所使用的插入和删除操作是值得学习的,简单实用。
路由缓存删除条目
rt_del()
要删除的条目是rt,相应散列值是hash,首先通过hash值找到对应的bucket,然后遍历,如果条目超时,或找到rt,则删除它。
rthp = &rt_hash_table[hash].chain;
spin_lock_bh(rt_hash_lock_addr(hash));
ip_rt_put(rt);
while ((aux = *rthp) != NULL) {
if (aux == rt || rt_is_expired(aux)) {
*rthp = aux->u.dst.rt_next;
rt_free(aux);
continue;
}
rthp = &aux->u.dst.rt_next;
}
spin_unlock_bh(rt_hash_lock_addr(hash));
路由表的创建
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);
ip_fib_net_init() -> fib4_rules_init(),这里真正分配了路由表空间
local_table = fib_hash_table(RT_TABLE_LOCAL);
main_table
= fib_hash_table(RT_TABLE_MAIN);
然后将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]);
最终生成结构如图,LOCAL表位于fib_table_hash[0],MAIN表位于fib_table_hash[1];两张表通过结构tb_hlist链入链表,而tb_id则标识了功能,255是LOCAL表,254是MAIN表。
关于这里的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) {