Linux路由缓存实现浅析

独孤九贱

最近闲赋在家，在家里做了一个双ADSL负载均衡的东东，不过遗憾的是，流量始终在一条线路上，本着解决问题的态度，把Linux的路由缓存子系统看了一下，现在把笔记发上来。
原来好像也发过一篇，不过是老版本内核的，本贴对应的版本是2.6.31。

不保证内容都正确，仅供讨论学习之用。

转载请注明作者和出处。

一、什么是路由缓存
路由查询IP层最重要的工作，同时，它也是一件很耗时的工作，为了提高路由查询的效率。Linux内核引用了路由缓存，用于减少对路由表的查询。呵呵，在计算机世界里，cache是无处不在的。Linux的路由缓存（下文中可能会简称为DST）是被设计来与协议无关的独立子系统。一个典型的路由缓存如下：

1. root@kendo-ThinkpadT410:~# route -Cn
   
2. 内核 IP 路由缓存
   
3. Source          Destination     Gateway         Flags Metric Ref    Use Iface
   
4. 10.1.1.199      74.125.53.102   10.1.1.254            0      0        3 eth0
   
5. 10.1.1.199      219.148.35.84   10.1.1.254            0      0        0 eth0
   
6. 10.1.1.199      118.123.3.237   10.1.1.254            0      0       21 eth0
   
7. 61.55.167.138   10.1.1.199      10.1.1.199      l     0      0       33 lo
   
8. 10.1.1.199      203.208.37.22   10.1.1.254            0      0        3 eth0
   
9. 10.1.1.183      10.1.1.255      10.1.1.255      ibl   0      0        1 lo
   
10. 10.1.1.199      72.14.213.101   10.1.1.254            0      0        1 eth0
    
11. 10.1.1.137      10.1.1.255      10.1.1.255      ibl   0      0        0 lo
    
12. 10.1.1.199      61.139.2.69     10.1.1.254            0      0       53 eth0
    
13. 10.1.1.199      8.8.8.8         10.1.1.254            0      0       45 eth0
    
14. 10.1.1.199      220.166.65.249  10.1.1.254            0      0       21 eth0
    
15. 10.1.1.199      207.46.193.178  10.1.1.254            0      0        3 eth0
    
16. 219.148.35.84   10.1.1.199      10.1.1.199      l     0      0        2 lo
    
17. 10.1.1.199      72.14.203.148   10.1.1.254            0      0        0 eth0
    
18. 8.8.8.8         10.1.1.199      10.1.1.199      l     0      0       22 lo
    
19. 10.1.1.199      207.46.193.178  10.1.1.254            0      0        1 eth0
    
20. 10.1.1.199      219.232.243.91  10.1.1.254            0      0        2 eth0
    
21. 10.1.1.199      118.123.3.236   10.1.1.254            0      0       21 eth0
    
22. ……
    

复制代码

二、路由缓存初始化
2.1 ip_rt_init
路由缓存使用hash表存储，初始化工作，最重要的就是分配hash表和表项所使用的SLAB，这个工作是在ip_rt_init中完成的：

1. int __init ip_rt_init(void)
   
2. {
   
3.         ……
   
4.         /* 初始化DST SLAB分配缓存器 */
   
5.         ipv4_dst_ops.kmem_cachep =
   
6.                 kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
   
7.                                   SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
   
8. 
   
9.         ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
   
10. 
    
11.         /* 根据系统内存容量，分配路由缓存hash表 */
    
12.         rt_hash_table = (struct rt_hash_bucket *)
    
13.                 alloc_large_system_hash("IP route cache",
    
14.                                         sizeof(struct rt_hash_bucket),
    
15.                                         rhash_entries,
    
16.                                         (totalram_pages >= 128 * 1024) ?
    
17.                                         15 : 17,
    
18.                                         0,
    
19.                                         &rt_hash_log,
    
20.                                         &rt_hash_mask,
    
21.                                         rhash_entries ? 0 : 512 * 1024);
    
22.         /* 初始化hash表 */                                       
    
23.         memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
    
24.         rt_hash_lock_init();
    
25. 
    
26.         /* gc_thresh和ip_rt_max_size用于垃圾回收 */
    
27.         ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
    
28.         ip_rt_max_size = (rt_hash_mask + 1) * 16;
    
29.         ……

复制代码

指针rt_hash_table指向缓存hash表，表的每一个桶是结构struct rt_hash_bucket，桶下的链表的结构是struct rtable。

1. /*
   
2. * Route cache.
   
3. */
   
4. 
   
5. /* The locking scheme is rather straight forward:
   
6. *
   
7. * 1) Read-Copy Update protects the buckets of the central route hash.
   
8. * 2) Only writers remove entries, and they hold the lock
   
9. *    as they look at rtable reference counts.
   
10. * 3) Only readers acquire references to rtable entries,
    
11. *    they do so with atomic increments and with the
    
12. *    lock held.
    
13. */
    
14. 
    
15. struct rt_hash_bucket {
    
16.         struct rtable        *chain;
    
17. };

复制代码

rt_hash_bucket只有一个struct rtable结构的成员，rtable用于描于一个缓存项（准确地讲，它是包括但不仅限于）：

1. struct fib_nh;
   
2. struct inet_peer;
   
3. struct rtable
   
4. {
   
5.         union
   
6.         {
   
7.                 struct dst_entry        dst;
   
8.         } u;
   
9. 
   
10.         /* Cache lookup keys */
    
11.         struct flowi                fl;
    
12. 
    
13.         struct in_device        *idev;
    
14.        
    
15.         int                        rt_genid;
    
16.         unsigned                rt_flags;
    
17.         __u16                        rt_type;
    
18. 
    
19.         __be32                        rt_dst;        /* Path destination        */
    
20.         __be32                        rt_src;        /* Path source                */
    
21.         int                        rt_iif;
    
22. 
    
23.         /* Info on neighbour */
    
24.         __be32                        rt_gateway;
    
25. 
    
26.         /* Miscellaneous cached information */
    
27.         __be32                        rt_spec_dst; /* RFC1122 specific destination */
    
28.         struct inet_peer        *peer; /* long-living peer info */
    
29. };

复制代码

rtable包含一些具体的协议有关的项和一个与协议无关、类型为struct dst_entry的成员。路由缓存中，最为精华的部份就是DST的单独抽像，设计者将它设计成一个无协议无关的结构，无协议无关，意味着不论是IPV4，还是V6，亦或其它网络层协议，都可以使用它。值得注意的是，dst成员被设计成union，结构dst_entry与rtable有相同的地址，同一个指针可以方便地在两者之前进行强制类型转换。整个hash表如下图所示：

2.2 hash表的分配
DST缓存的hash表的分配，是通过调用系统API alloc_large_system_hash实现的：

1.         rt_hash_table = (struct rt_hash_bucket *)
   
2.                 alloc_large_system_hash("IP route cache",
   
3.                                         sizeof(struct rt_hash_bucket),
   
4.                                         rhash_entries,
   
5.                                         (totalram_pages >= 128 * 1024) ?
   
6.                                         15 : 17,
   
7.                                         0,
   
8.                                         &rt_hash_log,
   
9.                                         &rt_hash_mask,
   
10.                                         rhash_entries ? 0 : 512 * 1024);

复制代码

对照以上代码，来分析alloc_large_system_hash的实现：

1. /*
   
2. * allocate a large system hash table from bootmem
   
3. * - it is assumed that the hash table must contain an exact power-of-2
   
4. *   quantity of entries
   
5. * - limit is the number of hash buckets, not the total allocation size
   
6. */
   
7. void *__init alloc_large_system_hash(const char *tablename,                /* hash表名称 */
   
8.                                      unsigned long bucketsize,                                        /* hash表的每个桶的大小 */
   
9.                                      unsigned long numentries,                                        /* hash表的总的元素数目 */
   
10.                                      int scale,
    
11.                                      int flags,
    
12.                                      unsigned int *_hash_shift,
    
13.                                      unsigned int *_hash_mask,
    
14.                                      unsigned long limit)
    
15. {

复制代码

函数前三个参数很清晰，后面几个参数在代码中逐步了解，一个有意思的是，实始分配的时候，并不需要指
明hash表的桶的数目。而这个数目，对于hash表来讲，是至关重要的。

1.         unsigned long long max = limit;
   
2.         unsigned long log2qty, size;
   
3.         void *table = NULL;

复制代码

如果没有手动指定hash表的大小，则根据系统内存大小自动计算hash表的元素总数。对于DST子系统而言，其值是一个
内核名命行参数rhash_entries，用户可以在内核引导时指定其大小:

1.         /* allow the kernel cmdline to have a say */
   
2.         if (!numentries) {
   
3.                 /* round applicable memory size up to nearest megabyte */
   
4.                 /**
   
5.                  * numentries的计算基数是nr_kernel_pages，它表示内存的dma和normal页区的实际页数
   
6.                  */
   
7.                 numentries = nr_kernel_pages;
   
8.                
   
9.                 /**
   
10.                  * 这部份的计算是让numentries的值自动校正为其对应的最接近以MB字节单位的页面数的值，
    
11.                  * 以x86，32位的情况，一个1MB包含的页面数为1UL << 20 - PAGE_SHIFT，后面直接以256来行文了。
    
12.                  * 例如，如果 numentries为100，则会自动调整为256，如果为257，则会调整为512，如果为1000，则
    
13.                  * 会调整为1024……(假定)
    
14.                  */
    
15.                
    
16.                 /**
    
17.                  * 这里 "+= 1MB包含的页面数" 意味着向上对齐，即如果原始是2，则会变成257(当然，通过后面的位移运算，会把它变成256)，
    
18.                  * 而不是变成0(向下对齐)，而-1则是一个调整阀值，对于一些边界值，如0，会保证它还是0，256还是256（而不是向上靠成512了）
    
19.                  */
    
20.                 numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
    
21.                 /* 右移左移移得人头晕，其实就是以256为边界对齐 */               
    
22.                 numentries >>= 20 - PAGE_SHIFT;
    
23.                 numentries <<= 20 - PAGE_SHIFT;
    
24. 
    
25.                 /* limit to 1 bucket per 2^scale bytes of low memory */
    
26.                 /* scale只是一个当numentries为0时，计算numentries的滚动标尺 */
    
27.                 if (scale > PAGE_SHIFT)
    
28.                         numentries >>= (scale - PAGE_SHIFT);
    
29.                 else
    
30.                         numentries <<= (PAGE_SHIFT - scale);
    
31. 
    
32.                 /* Make sure we've got at least a 0-order allocation.. */
    
33.                 if (unlikely((numentries * bucketsize) < PAGE_SIZE))
    
34.                         numentries = PAGE_SIZE / bucketsize;
    
35.         }
    
36.         /* 变为最接近的2的幂 */
    
37.         numentries = roundup_pow_of_two(numentries);

复制代码

最后一个参数limit为hash表元素的总大小，如果没有指定，则自动计算一个，默认情况下，使用总共路由的1/16（右移四位），：

1.         /* limit allocation size to 1/16 total memory by default */
   
2.         if (max == 0) {
   
3.                 max = ((unsigned long long)nr_all_pages << PAGE_SHIFT) >> 4;
   
4.                 do_div(max, bucketsize);
   
5.         }

复制代码

如果numentries超限，调整它：

1.         if (numentries > max)
   
2.                 numentries = max;

复制代码

对numentries对对数：ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value，即
hash表的总元素是2^log2qty。可以很方便地使用1 << log2qty来表示之。

1.         log2qty = ilog2(numentries);

复制代码

另一方面，hash表的分配，采用了三种方式，其值主要是根据参数flags和另一个全局变量hashdist来决定的：

1.         do {
   
2.                 size = bucketsize << log2qty;
   
3.                 /**
   
4.                  * 这里可以看到其第5个参数的作用，如果标志位设置有HASH_EARLY,表明在启动时分配,
   
5.                  * 在bootmem中分配，否则使用其它方式来分配。
   
6.                  */
   
7.                 if (flags & HASH_EARLY)
   
8.                         table = alloc_bootmem_nopanic(size);
   
9.                 else if (hashdist)
   
10.                         table = __vmalloc(size, GFP_ATOMIC, PAGE_KERNEL);
    
11.                 else {
    
12.                         /*
    
13.                          * If bucketsize is not a power-of-two, we may free
    
14.                          * some pages at the end of hash table which
    
15.                          * alloc_pages_exact() automatically does
    
16.                          */
    
17.                         if (get_order(size) < MAX_ORDER) {
    
18.                                 table = alloc_pages_exact(size, GFP_ATOMIC);
    
19.                                 kmemleak_alloc(table, size, 1, GFP_ATOMIC);
    
20.                         }
    
21.                 }
    
22.         } while (!table && size > PAGE_SIZE && --log2qty);

复制代码

/* 分配失败 */

1.         if (!table)
   
2.                 panic("Failed to allocate %s hash table\n", tablename);

复制代码

/* 从成功分配的信息当中，可以了解一些重要的计算参数的含义，也可以在dmesg中，对照计算 */

1.         printk(KERN_INFO "%s hash table entries: %d (order: %d, %lu bytes)\n",
   
2.                tablename,
   
3.                (1U << log2qty),
   
4.                ilog2(size) - PAGE_SHIFT,
   
5.                size);

复制代码

/**
         * 第6个参数向用户返回log2qty的值，这个值的含义前文已有分析。
         */

1.         if (_hash_shift)
   
2.                 *_hash_shift = log2qty;

复制代码

/**
         * 1U << log2qty是hash表桶的大小，第7个参数*_hash_mask是向调用者返回桶的大小，即桶大小为*_hash_mask + 1
         * 之所以在做减1的调整，应该是因为C语言的数组是从0开始的。
         */

1.         if (_hash_mask)
   
2.                 *_hash_mask = (1 << log2qty) - 1;
   
3. 
   
4.         return table;
   
5. }

复制代码

hashdist的dist，意指distribution：

1. #define HASH_EARLY        0x00000001        /* Allocating during early boot? */
   
2. 
   
3. /* Only NUMA needs hash distribution. 64bit NUMA architectures have
   
4. * sufficient vmalloc space.
   
5. */
   
6. #if defined(CONFIG_NUMA) && defined(CONFIG_64BIT)
   
7. #define HASHDIST_DEFAULT 1
   
8. #else
   
9. #define HASHDIST_DEFAULT 0
   
10. #endif
    
11. extern int hashdist;                /* Distribute hashes across NUMA nodes? */
    
12. 
    
13. int hashdist = HASHDIST_DEFAULT;
    
14. 
    
15. #ifdef CONFIG_NUMA
    
16. static int __init set_hashdist(char *str)
    
17. {
    
18.         if (!str)
    
19.                 return 0;
    
20.         hashdist = simple_strtoul(str, &str, 0);
    
21.         return 1;
    
22. }
    
23. __setup("hashdist=", set_hashdist);
    
24. #endif

复制代码

可见，hashdist主要是为了支持NUMA，而这个distribution，应该就是对应vmalloc的特性吧：物理上非连续。

了解了alloc_large_system_hash函数的各个参数的作用，就可以完全理解DST的hash表的分配了。

三、缓存的查询
IP层收到数据报文的时候，ip_rcv_finish会调用 ip_route_input进行路由查询工作：

1. static int ip_rcv_finish(struct sk_buff *skb)
   
2. {
   
3.         const struct iphdr *iph = ip_hdr(skb);
   
4.         struct rtable *rt;
   
5. 
   
6.         /*
   
7.          *        Initialise the virtual path cache for the packet. It describes
   
8.          *        how the packet travels inside Linux networking.
   
9.          */
   
10.         if (skb_dst(skb) == NULL) {
    
11.                 int err = ip_route_input(skb, iph->daddr, iph->saddr, iph->tos,
    
12.                                          skb->dev);
    
13.                 if (unlikely(err)) {
    
14.                         if (err == -EHOSTUNREACH)
    
15.                                 IP_INC_STATS_BH(dev_net(skb->dev),
    
16.                                                 IPSTATS_MIB_INADDRERRORS);
    
17.                         else if (err == -ENETUNREACH)
    
18.                                 IP_INC_STATS_BH(dev_net(skb->dev),
    
19.                                                 IPSTATS_MIB_INNOROUTES);
    
20.                         goto drop;
    
21.                 }
    
22.         }

复制代码

ip_route_input会首先尝试进行缓存的查找，如果找不到，再查询路由表，这里仅分析缓存的查找：

1. int ip_route_input(struct sk_buff *skb, __be32 daddr, __be32 saddr,
   
2.                    u8 tos, struct net_device *dev)
   
3. {
   
4.         struct rtable * rth;
   
5.         unsigned        hash;
   
6.         int iif = dev->ifindex;
   
7.         struct net *net;
   
8. 
   
9.         net = dev_net(dev);
   
10. 
    
11.         if (!rt_caching(net))
    
12.                 goto skip_cache;
    
13. 
    
14.         tos &= IPTOS_RT_MASK;
    
15.         hash = rt_hash(daddr, saddr, iif, rt_genid(net));
    
16. 
    
17.         rcu_read_lock();
    
18.         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
    
19.              rth = rcu_dereference(rth->u.dst.rt_next)) {
    
20.                 if (((rth->fl.fl4_dst ^ daddr) |
    
21.                      (rth->fl.fl4_src ^ saddr) |
    
22.                      (rth->fl.iif ^ iif) |
    
23.                      rth->fl.oif |
    
24.                      (rth->fl.fl4_tos ^ tos)) == 0 &&
    
25.                     rth->fl.mark == skb->mark &&
    
26.                     net_eq(dev_net(rth->u.dst.dev), net) &&
    
27.                     !rt_is_expired(rth)) {
    
28.                         dst_use(&rth->u.dst, jiffies);
    
29.                         RT_CACHE_STAT_INC(in_hit);
    
30.                         rcu_read_unlock();
    
31.                         skb_dst_set(skb, &rth->u.dst);
    
32.                         return 0;
    
33.                 }
    
34.                 RT_CACHE_STAT_INC(in_hlist_search);
    
35.         }
    
36.         rcu_read_unlock();

复制代码

ip_route_input首先调用rt_hash_code函数计算hash值，以取得在rt_hash_table中的入口，然后使用for循环，遍历hash链中的每一个桶，进行缓存的匹备，匹备的要素包括：
目的地址
来源地址
输入接口
输出接口或ToS
netfilter mark
缓存设备
缓存是否过期

如果缓存查找命中，则使用dst_use更新使用计数器和时间戳:

1. static inline void dst_use(struct dst_entry *dst, unsigned long time)
   
2. {
   
3.         dst_hold(dst);
   
4.         dst->__use++;
   
5.         dst->lastuse = time;
   
6. }

复制代码

RT_CACHE_STAT_INC宏用于累加查找命中计数器，skb_dst_set设置当前skb的dst：

1. static inline void skb_dst_set(struct sk_buff *skb, struct dst_entry *dst)
   
2. {
   
3.         skb->_skb_dst = (unsigned long)dst;
   
4. }

复制代码

有一个重要的问题是，在缓存创建的时候，封装了缓存下一步的发送函数output，这里设置了skb的dst，就意味着它可以继续处理和转发了，例如：

1.         rth->u.dst.input = ip_forward;
   
2.         rth->u.dst.output = ip_output;

复制代码

一点小改变：值得注意的是，查找匹备与老版本相比较，已经有了明显的变化：

1.         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
   
2.              rth = rcu_dereference(rth->u.rt_next)) {
   
3.                 if (rth->fl.fl4_dst == daddr &&
   
4.                     rth->fl.fl4_src == saddr &&
   
5.                     rth->fl.iif == iif &&
   
6.                     rth->fl.oif == 0 &&
   
7. #ifdef CONFIG_IP_ROUTE_FWMARK
   
8.                     rth->fl.fl4_fwmark == skb->nfmark &&
   
9. #endif
   
10.                     rth->fl.fl4_tos == tos) {

复制代码

上面代码取自2.6.12，新版本中多增加了两项比较：

1. net_eq(dev_net(rth->u.dst.dev), net) &&
   
2.                     !rt_is_expired(rth)

复制代码

因为缓存是独立于协议的，所以net_eq比较当前缓存对应的协议是否匹备，例如是否都是ipv4。rt_is_expired用于检查缓存是否过期。
另一个变化是把(XX == XX) && (YY == YY)比较，变成了(XX ^ XX) | (YY ^ YY)，这样变的理由在于：
如果A == B, 则A ^ B = 0

匿名者7

好帖！
问个问题：假如在路由器下有多个wan口(eth0 eth1 eth 2 eth3).
那我在调用ip_route_input时会设置哪一个为dst呢？
有没有什么办法可以手动去设定具体的路由呢？

wavespider

回复 1# 独孤九贱


    "dst成员被设计成union，结构dst_entry与rtable有相同的地址"
    struct rtable
{
        union
        {
                struct dst_entry        dst;
        } u;
        /* Cache lookup keys */
        struct flowi                fl;
        .....
}

问题是，如果dst不是一个union的话，地址也一样吧？！

chanwai1219

understanding internals的笔记,很好,多谢

fei265274

很不错的文章，受教了

20040925

回复 39# tuibo


    我测试了一下，删除路由的时候好像不会强制清缓存

蓝色神话

楼主用心了，感谢分享！！！

tuibo

每次添加修改删除配置路由，路由cache应该要被强制刷新掉。    每次包流过应该，应该要修改cache定时器的超时时间。

finalfantasy000

回复 10# Godbach


    我同意你的看法

becomefish

Hi , lz , do you like to work in ChengDu ? Plz contact [ chenyu105 at gmail dot com ]

: D

边边赚

不错，楼主的分享，十分感谢