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

独孤九贱

回复 1# 独孤九贱

三、缓存的增加

当缓存查找没有命中，系统会进行路由表的查找，当查找命中后，会创建一个缓存项，将其插入到路由缓存hash表当中，这样，后续报文就不用再查路由表了。例如：

1. 
   
2.         /* 分配一个路由缓存项 */       
   
3.         rth = dst_alloc(&ipv4_dst_ops);
   
4.         if (!rth)
   
5.                 goto e_nobufs;
   
6.        
   
7.         /* 初始化rtable的各个成员 */
   
8.         rth->u.dst.output= ip_rt_bug;
   
9.         rth->rt_genid = rt_genid(net);
   
10. 
    
11.         atomic_set(&rth->u.dst.__refcnt, 1);
    
12.         rth->u.dst.flags= DST_HOST;
    
13.         if (IN_DEV_CONF_GET(in_dev, NOPOLICY))
    
14.                 rth->u.dst.flags |= DST_NOPOLICY;
    
15.         rth->fl.fl4_dst        = daddr;
    
16.         rth->rt_dst        = daddr;
    
17.         rth->fl.fl4_tos        = tos;
    
18.         rth->fl.mark    = skb->mark;
    
19.         rth->fl.fl4_src        = saddr;
    
20.         rth->rt_src        = saddr;
    
21. #ifdef CONFIG_NET_CLS_ROUTE
    
22.         rth->u.dst.tclassid = itag;
    
23. #endif
    
24.         rth->rt_iif        =
    
25.         rth->fl.iif        = dev->ifindex;
    
26.         rth->u.dst.dev        = net->loopback_dev;
    
27.         dev_hold(rth->u.dst.dev);
    
28.         rth->idev        = in_dev_get(rth->u.dst.dev);
    
29.         rth->rt_gateway        = daddr;
    
30.         rth->rt_spec_dst= spec_dst;
    
31.         rth->u.dst.input= ip_local_deliver;
    
32.         rth->rt_flags         = flags|RTCF_LOCAL;
    
33.         if (res.type == RTN_UNREACHABLE) {
    
34.                 rth->u.dst.input= ip_error;
    
35.                 rth->u.dst.error= -err;
    
36.                 rth->rt_flags         &= ~RTCF_LOCAL;
    
37.         }
    
38.         rth->rt_type        = res.type;
    
39.         /* 计算hash值 */
    
40.         hash = rt_hash(daddr, saddr, fl.iif, rt_genid(net));
    
41.         /* 将缓存插入hash表 */       
    
42.         err = rt_intern_hash(hash, rth, NULL, skb);

复制代码

在插入缓存项的时候，有四个动作：
1、调用dst_alloc分配一个缓存项；
2、初始化rth(struct rtable)各个成员，对rtable结构的理解，需要分析整个路由子系统，这里略过之；
3、计算缓存表的hash值，寻找入口；
4、调用rt_intern_hash插入路由表项；

3.1 缓存的分配
要将一个缓存增加入hash表，首先要调用dst_alloc分配一个路由缓存项，分配的实质就是在SLAB中分配一个高速缓存节点，每次分配的时候，都会尝试垃圾回收，关于垃圾回收，后面会有详述：

1. void * dst_alloc(struct dst_ops * ops)
   
2. {
   
3.         struct dst_entry * dst;
   
4. 
   
5.         /* 垃圾收集 */
   
6.         if (ops->gc && atomic_read(&ops->entries) > ops->gc_thresh) {
   
7.                 if (ops->gc(ops))
   
8.                         return NULL;
   
9.         }
   
10.         /* 在slab中分配缓存 */
    
11.         dst = kmem_cache_zalloc(ops->kmem_cachep, GFP_ATOMIC);
    
12.         if (!dst)
    
13.                 return NULL;
    
14.         /* 初始化各成员 */
    
15.         atomic_set(&dst->__refcnt, 0);
    
16.         dst->ops = ops;
    
17.         dst->lastuse = jiffies;
    
18.         dst->path = dst;
    
19.         dst->input = dst->output = dst_discard;
    
20. #if RT_CACHE_DEBUG >= 2
    
21.         atomic_inc(&dst_total);
    
22. #endif
    
23.         atomic_inc(&ops->entries);
    
24.         return dst;
    
25. }

复制代码

每个SLAB缓存的大小是sizeof(struct rtable)，所以dst_alloc分配的空间并不是dst，而是rtable，函数名称有点名不副实了。dst和rtable的指针可以相互转换，所以这并不是一个问题。不过函数的名称也并非完全不准确：它的初始化工作，仅是针对dst。而整个rtable的初始化，是留给调用者的。

3.2 缓存项的插入
缓存的插入是通过rt_intern_hash来完成的：

1. static int rt_intern_hash(unsigned hash, struct rtable *rt,
   
2.                           struct rtable **rp, struct sk_buff *skb)
   
3. {
   
4.         struct rtable        *rth, **rthp;
   
5.         unsigned long        now;
   
6.         struct rtable *cand, **candp;
   
7.         u32                 min_score;
   
8.         int                chain_length;
   
9.         int attempts = !in_softirq();
   
10. 
    
11. restart:
    
12.         chain_length = 0;
    
13.         min_score = ~(u32)0;
    
14.         cand = NULL;
    
15.         candp = NULL;
    
16.         now = jiffies;
    
17. 
    
18.         /* rt_intern_hash要做的第一件事情，就是检索要插入的缓存项在缓存hash表中是否存在。
    
19.          * 常理来讲，缓存的插入都是先查找但未命中后，再进行插入操作，所以这个检查好像是多余的。
    
20.          * 但是因为路由缓hash表可以在多个CPU上并行，缓存项可能在一个CPU上查找未命中的同时却被其它CPU插入……
    
21.          */
    
22.         /* 设备对应的网络子系统还没有缓存，当然也用不着检索了 */
    
23.         if (!rt_caching(dev_net(rt->u.dst.dev))) {
    
24.                 /*
    
25.                  * If we're not caching, just tell the caller we
    
26.                  * were successful and don't touch the route.  The
    
27.                  * caller hold the sole reference to the cache entry, and
    
28.                  * it will be released when the caller is done with it.
    
29.                  * If we drop it here, the callers have no way to resolve routes
    
30.                  * when we're not caching.  Instead, just point *rp at rt, so
    
31.                  * the caller gets a single use out of the route
    
32.                  * Note that we do rt_free on this new route entry, so that
    
33.                  * once its refcount hits zero, we are still able to reap it
    
34.                  * (Thanks Alexey)
    
35.                  * Note also the rt_free uses call_rcu.  We don't actually
    
36.                  * need rcu protection here, this is just our path to get
    
37.                  * on the route gc list.
    
38.                  */
    
39.                 /* 如果是单播中转或本地发送的报文，则尝试与arp绑定 */
    
40.                 if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
    
41.                         int err = arp_bind_neighbour(&rt->u.dst);
    
42.                         if (err) {
    
43.                                 /* 失败处理 */
    
44.                                 if (net_ratelimit())
    
45.                                         printk(KERN_WARNING
    
46.                                             "Neighbour table failure & not caching routes.\n");
    
47.                                 rt_drop(rt);
    
48.                                 return err;
    
49.                         }
    
50.                 }
    
51. 
    
52.                 rt_free(rt);
    
53.                 goto skip_hashing;
    
54.         }
    
55. 
    
56.         /* 取得hash链，这里与普通的链表稍有区别，因为rthp是指向指针的指针 */
    
57.         rthp = &rt_hash_table[hash].chain;
    
58. 
    
59.         /* 取得链锁 */
    
60.         spin_lock_bh(rt_hash_lock_addr(hash));
    
61.         /* 遍历链，寻找缓存是否已经存在
    
62.          * 这里一个值得注意的地方，是链表的删除操作：rthp被定义成一个指向指向的指针，这主要是为了高效地操作链表       
    
63.          * 每一次遍历，rthp指向的并不是缓存链中的下一个指点，而是指向“指向下一个节点的指针(dst.rt_next)的指针”:
    
64.          * rthp = &rth->u.dst.rt_next; 这样，在删除节点时，只需要修改这个指针指向的地址，让它指向待删除的节点的
    
65.          * 即可： *rthp = rth->u.dst.rt_next;这样，就不必再保留一个“前一节点的prev指针”。
    
66.          */
    
67.         while ((rth = *rthp) != NULL) {
    
68.                 /* 尝试超时过期清理 */
    
69.                 if (rt_is_expired(rth)) {
    
70.                         *rthp = rth->u.dst.rt_next;
    
71.                         rt_free(rth);
    
72.                         continue;
    
73.                 }
    
74.                 /* 关键字匹备，查看要插入的项是否存在 */
    
75.                 if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) {
    
76.                         /* 如果查找命中，则将它调到链首，这样做的理由是因为它是最近被使用，有可能会在接下来的查找中最先被使用 */
    
77.                         /* Put it first */
    
78.                         *rthp = rth->u.dst.rt_next;
    
79.                         /*
    
80.                          * Since lookup is lockfree, the deletion
    
81.                          * must be visible to another weakly ordered CPU before
    
82.                          * the insertion at the start of the hash chain.
    
83.                          */
    
84.                         rcu_assign_pointer(rth->u.dst.rt_next,
    
85.                                            rt_hash_table[hash].chain);
    
86.                         /*
    
87.                          * Since lookup is lockfree, the update writes
    
88.                          * must be ordered for consistency on SMP.
    
89.                          */
    
90.                         rcu_assign_pointer(rt_hash_table[hash].chain, rth);
    
91.                         /* 更新使用计数器(不是引用计数器)和时间戳 */
    
92.                         dst_use(&rth->u.dst, now);
    
93.                         /* 解锁*/
    
94.                         spin_unlock_bh(rt_hash_lock_addr(hash));
    
95.                         /* 因为存在，没有必要插入了，丢弃要插入的缓存项 */
    
96.                         rt_drop(rt);
    
97.                         /* 如果调用者指明了rp，则使用它返回查找到的缓存项，否则调用skb_dst_set设置skb的dst */
    
98.                         if (rp)
    
99.                                 *rp = rth;
    
100.                         else
     
101.                                 skb_dst_set(skb, &rth->u.dst);
     
102.                         return 0;
     
103.                 }
     
104. 
     
105.                 /* 如果对该缓存项没有引用，则尝试调用rt_score来计算应被删除的最佳候选人
     
106.                  * rt_score算计一个得分，拥有最小得分的缓存项则被记录至cand,同时使用了一个candp的理由与rthp作用类似，
     
107.                  * 在删除这个最佳删除项cand的时候，减少一个prev指针               
     
108.                  */
     
109.                 if (!atomic_read(&rth->u.dst.__refcnt)) {
     
110.                         u32 score = rt_score(rth);
     
111.                         /* min_socre初值是一个32位的最大值，如果计算出最小值，则不断地更新它，以期得到最大值 */
     
112.                         if (score <= min_score) {
     
113.                                 cand = rth;
     
114.                                 candp = rthp;
     
115.                                 min_score = score;
     
116.                         }
     
117.                 }
     
118.                 /* 统计链长，主要是用于以后判断是否超过垃圾回收的阀值 */
     
119.                 chain_length++;
     
120. 
     
121.                 rthp = &rth->u.dst.rt_next;
     
122.         }
     
123. 
     
124.         /* 循环完hash链，没有找到匹备的缓存项，则将尝试插入，每次插入之前，都会尝试找到一个最佳的删除项cand，这样，以避免出现缓存容量的溢出 */
     
125.         if (cand) {
     
126.                 /* ip_rt_gc_elasticity used to be average length of chain
     
127.                  * length, when exceeded gc becomes really aggressive.
     
128.                  *
     
129.                  * The second limit is less certain. At the moment it allows
     
130.                  * only 2 entries per bucket. We will see.
     
131.                  */
     
132.                 /* 如果找到了cand，并且当前链的长度已经超过了定义的垃圾回收的阀值，则直接调用rt_free删除之 */
     
133.                 if (chain_length > ip_rt_gc_elasticity) {
     
134.                         *candp = cand->u.dst.rt_next;
     
135.                         rt_free(cand);
     
136.                 }
     
137.         } else {
     
138.                 /* 如果没有找到cand，但是当前链的长度已经超过了链的最大长度，则仍然在进行垃圾回收处理，这次出马的是rt_emergency_hash_rebuild */
     
139.                 if (chain_length > rt_chain_length_max) {
     
140.                         struct net *net = dev_net(rt->u.dst.dev);
     
141.                         int num = ++net->ipv4.current_rt_cache_rebuild_count;
     
142.                         if (!rt_caching(dev_net(rt->u.dst.dev))) {
     
143.                                 printk(KERN_WARNING "%s: %d rebuilds is over limit, route caching disabled\n",
     
144.                                         rt->u.dst.dev->name, num);
     
145.                         }
     
146.                         rt_emergency_hash_rebuild(dev_net(rt->u.dst.dev));
     
147.                 }
     
148.         }
     
149. 
     
150.         /* Try to bind route to arp only if it is output
     
151.            route or unicast forwarding path.
     
152.          */
     
153.         /* 如果是单播中转或本地发出的报文，尝试将路由缓存与arp绑定，需要绑定的理由在于加速，这样在数据发送的时候，可以很方便地封装二层帧首部 */
     
154.         if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
     
155.                 int err = arp_bind_neighbour(&rt->u.dst);
     
156.                 /* 绑定失败 */               
     
157.                 if (err) {
     
158.                         spin_unlock_bh(rt_hash_lock_addr(hash));
     
159.                         /* 内存不足，直接丢弃，并出错返回 */
     
160.                         if (err != -ENOBUFS) {
     
161.                                 rt_drop(rt);
     
162.                                 return err;
     
163.                         }
     
164. 
     
165.                         /* Neighbour tables are full and nothing
     
166.                            can be released. Try to shrink route cache,
     
167.                            it is most likely it holds some neighbour records.
     
168.                          */
     
169.                         /* 否则调整垃圾收回阀值，调用rt_garbage_collect进行主动垃圾清理，并尝试重试 */
     
170.                         if (attempts-- > 0) {
     
171.                                 int saved_elasticity = ip_rt_gc_elasticity;
     
172.                                 int saved_int = ip_rt_gc_min_interval;
     
173.                                 ip_rt_gc_elasticity        = 1;
     
174.                                 ip_rt_gc_min_interval        = 0;
     
175.                                 rt_garbage_collect(&ipv4_dst_ops);
     
176.                                 ip_rt_gc_min_interval        = saved_int;
     
177.                                 ip_rt_gc_elasticity        = saved_elasticity;
     
178.                                 goto restart;
     
179.                         }
     
180.                         /* 超过最大重试次数，仍旧失败 */
     
181.                         if (net_ratelimit())
     
182.                                 printk(KERN_WARNING "Neighbour table overflow.\n");
     
183.                         rt_drop(rt);
     
184.                         return -ENOBUFS;
     
185.                 }
     
186.         }
     
187. 
     
188.         rt->u.dst.rt_next = rt_hash_table[hash].chain;
     
189. 
     
190. #if RT_CACHE_DEBUG >= 2
     
191.         if (rt->u.dst.rt_next) {
     
192.                 struct rtable *trt;
     
193.                 printk(KERN_DEBUG "rt_cache @%02x: %pI4",
     
194.                        hash, &rt->rt_dst);
     
195.                 for (trt = rt->u.dst.rt_next; trt; trt = trt->u.dst.rt_next)
     
196.                         printk(" . %pI4", &trt->rt_dst);
     
197.                 printk("\n");
     
198.         }
     
199. #endif
     
200.         /*
     
201.          * Since lookup is lockfree, we must make sure
     
202.          * previous writes to rt are comitted to memory
     
203.          * before making rt visible to other CPUS.
     
204.          */
     
205.         /* 插入缓存项 */
     
206.         rcu_assign_pointer(rt_hash_table[hash].chain, rt);
     
207. 
     
208.         /* 解锁 */
     
209.         spin_unlock_bh(rt_hash_lock_addr(hash));
     
210. 
     
211. skip_hashing:
     
212.         if (rp)
     
213.                 *rp = rt;
     
214.         else
     
215.                 skb_dst_set(skb, &rt->u.dst);
     
216.         return 0;
     
217. }

复制代码

四、缓存的释放
在rt_intern_hash函数中，多次出现调用rt_free来释放或调用rt_drop来丢弃缓存的情况。
这两个函数非常相似：

1. static inline void rt_free(struct rtable *rt)
   
2. {
   
3.         call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
   
4. }

复制代码

1. static inline void rt_drop(struct rtable *rt)
   
2. {
   
3.         ip_rt_put(rt);
   
4.         call_rcu_bh(&rt->u.dst.rcu_head, dst_rcu_free);
   
5. }

复制代码

rt_drop多了一句ip_rt_put调用。ip_rt_put函数通过调用dst_release递减缓存的引用计数器：

1. static inline void ip_rt_put(struct rtable * rt)
   
2. {
   
3.         if (rt)
   
4.                 dst_release(&rt->u.dst);
   
5. }

复制代码

1. static inline void dst_rcu_free(struct rcu_head *head)
   
2. {
   
3.         struct dst_entry *dst = container_of(head, struct dst_entry, rcu_head);
   
4.         dst_free(dst);
   
5. }

复制代码

1. static inline void dst_free(struct dst_entry * dst)
   
2. {
   
3.         /* obsoolete > 1 时意思着缓存项已经被处理过了，直接返回 */       
   
4.         if (dst->obsolete > 1)
   
5.                 return;
   
6.         /* 如果dst的引用计数器为0，则直接调用dst_destory删除之，否则调用__dst_free进一步处理，
   
7.          * 特别地，如果删除失败，也会调用__dst_free
   
8.          */
   
9.         if (!atomic_read(&dst->__refcnt)) {
   
10.                 dst = dst_destroy(dst);
    
11.                 if (!dst)
    
12.                         return;
    
13.         }
    
14.         __dst_free(dst);
    
15. }

复制代码

1. void __dst_free(struct dst_entry * dst)
   
2. {
   
3.         spin_lock_bh(&dst_garbage.lock);
   
4.         ___dst_free(dst);
   
5.         dst->next = dst_garbage.list;
   
6.         dst_garbage.list = dst;
   
7.         if (dst_garbage.timer_inc > DST_GC_INC) {
   
8.                 dst_garbage.timer_inc = DST_GC_INC;
   
9.                 dst_garbage.timer_expires = DST_GC_MIN;
   
10.                 cancel_delayed_work(&dst_gc_work);
    
11.                 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires);
    
12.         }
    
13.         spin_unlock_bh(&dst_garbage.lock);
    
14. }

复制代码

__dst_free函数首先调用___dst_free将设备还没有处于运行或运行状态不是IFF_UP时，将dst的input/output函数指针设为dst_discard,并且设置obsolete=2，标识缓存项为DEAD状态，或者意味着它已经被_dst_free处理过了，与此相对就是在前文dst_free函数中，判断obsoolete > 1时就直接返回，因为它已经被处理过了：

1. static void ___dst_free(struct dst_entry * dst)
   
2. {
   
3.         /* The first case (dev==NULL) is required, when
   
4.            protocol module is unloaded.
   
5.          */
   
6.         if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) {
   
7.                 dst->input = dst->output = dst_discard;
   
8.         }
   
9.         dst->obsolete = 2;
   
10. }

复制代码

接下来的工作就是把dst放到一个dst_garbage_list全局链表中，这意味着缓存应该被释放，但是因为引用计数器非0，所以暂时放在这里，相当于
打入天牢，待秋后处决的意思:

1.         dst->next = dst_garbage.list;
   
2.         dst_garbage.list = dst;

复制代码

这个秋后处决的时间调度是使用一个延迟队列来实现的，如果队列的时间计数器inc大于 DST_GC_INC，则设置在最小
延迟时间DST_GC_MIN后处理dst_garbage_list：

1.         if (dst_garbage.timer_inc > DST_GC_INC) {
   
2.                 dst_garbage.timer_inc = DST_GC_INC;
   
3.                 dst_garbage.timer_expires = DST_GC_MIN;
   
4.                 cancel_delayed_work(&dst_gc_work);
   
5.                 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires);
   
6.         }

复制代码

缓存最终的内存释放，是通过dst_destroy来实现的，缓存释放的本质是向SLAB返还内存:

1. kmem_cache_free(dst->ops->kmem_cachep, dst);

复制代码

不过因为dst与其它子系统的相关性，实际的过程还要稍微麻烦一些：

1. struct dst_entry *dst_destroy(struct dst_entry * dst)
   
2. {
   
3.         struct dst_entry *child;
   
4.         struct neighbour *neigh;
   
5.         struct hh_cache *hh;
   
6. 
   
7.         smp_rmb();
   
8. 
   
9. again:
   
10.         neigh = dst->neighbour;
    
11.         hh = dst->hh;
    
12.         child = dst->child;
    
13.        
    
14.         /* 释放缓存对应的二层报头 */
    
15.         dst->hh = NULL;
    
16.         if (hh && atomic_dec_and_test(&hh->hh_refcnt))
    
17.                 kfree(hh);
    
18. 
    
19.         /* 释放对应的二层协议结构 */
    
20.         if (neigh) {
    
21.                 dst->neighbour = NULL;
    
22.                 neigh_release(neigh);
    
23.         }
    
24.        
    
25.         /* 减少总的缓存计数器 */
    
26.         atomic_dec(&dst->ops->entries);
    
27. 
    
28.         /* 如果协议定义了destroy，调用之 */
    
29.         if (dst->ops->destroy)
    
30.                 dst->ops->destroy(dst);
    
31.         /* 递减对应设备的引用计数器 */
    
32.         if (dst->dev)
    
33.                 dev_put(dst->dev);
    
34. #if RT_CACHE_DEBUG >= 2
    
35.         atomic_dec(&dst_total);
    
36. #endif
    
37.         /* 内存释放 */       
    
38.         kmem_cache_free(dst->ops->kmem_cachep, dst);
    
39.        
    
40.         /* dst的child指针被IPSEC模块使用，它可能是一个child链，在释放dst的时候，也会尝试去释放它，如果其
    
41.          * 设置了DST_NOHASH标识，并且没有被引用，则使用goto again反复地释放它们。否则，则将其做为返回值返回，
    
42.          * 前面在分析dst_free时指出，如果dst_free在调用dst_destroy时没有返回NULL，则调用__dst_free进一步处理。
    
43.          */
    
44.         dst = child;
    
45.         if (dst) {
    
46.                 int nohash = dst->flags & DST_NOHASH;
    
47. 
    
48.                 if (atomic_dec_and_test(&dst->__refcnt)) {
    
49.                         /* We were real parent of this dst, so kill child. */
    
50.                         if (nohash)
    
51.                                 goto again;
    
52.                 } else {
    
53.                         /* Child is still referenced, return it for freeing. */
    
54.                         if (nohash)
    
55.                                 return dst;
    
56.                         /* Child is still in his hash table */
    
57.                 }
    
58.         }
    
59.         return NULL;
    
60. }

复制代码

独孤九贱

回复 1# 独孤九贱


五、缓存的垃圾回收
要进行垃圾回收的原因很多，例如，缓存项巨大，点用过多内存。前面在插入缓存项的时候已经看到在插入新缓存项的时候，总是会尝试去删除一个合适的旧的缓存项。
这就是缓存垃圾回收的一个例子。

缓存子系统使用了两种垃圾回收机集：
同步回收
        当分配新的缓存项，但是发现缓存总数已经超过阀值gc_thresh时。
        当一条新的缓存项需要插入到缓存hash表，而对应的表的链中有合适应该被删除的项，这在之前已经看到过。
        当邻居子系统缓存需要内存时，因为dst与2层协议缓存之前存在相互用用关系，这在dst_destroy中已经看到。如果二层缓存协议无法分配到内存时，那么
        进入同步回收，间接地释放2层缓存协议所占的内存。
异步回收
        系统使用一个定时器，来定时地触发定期的垃圾回收操作，以使缓存的容量始终在一个合理的范围内。   

5.1 同步回收
dst_alloc在分配新的缓存项，但是发现缓存总数已经超过阀值gc_thresh时

1.         /* 垃圾收集 */
   
2.         if (ops->gc && atomic_read(&ops->entries) > ops->gc_thresh) {
   
3.                 if (ops->gc(ops))
   
4.                         return NULL;
   
5.         }

复制代码

ops->gc在初始化的时候，指向的函数是gc_garbage_collect：

1. static struct dst_ops ipv4_dst_ops = {
   
2.         .family =                AF_INET,
   
3.         .protocol =                cpu_to_be16(ETH_P_IP),
   
4.         .gc =                        rt_garbage_collect,
   
5.         .check =                ipv4_dst_check,
   
6.         .destroy =                ipv4_dst_destroy,
   
7.         .ifdown =                ipv4_dst_ifdown,
   
8.         .negative_advice =        ipv4_negative_advice,
   
9.         .link_failure =                ipv4_link_failure,
   
10.         .update_pmtu =                ip_rt_update_pmtu,
    
11.         .local_out =                __ip_local_out,
    
12.         .entries =                ATOMIC_INIT(0),
    
13. };

复制代码

rt_garbage_collect是垃圾同步回收的核心函数，这个函数长而复杂，分段来分析它：

1. /*
   
2.    Short description of GC goals.
   
3. 
   
4.    We want to build algorithm, which will keep routing cache
   
5.    at some equilibrium point, when number of aged off entries
   
6.    is kept approximately equal to newly generated ones.
   
7. 
   
8.    Current expiration strength is variable "expire".
   
9.    We try to adjust it dynamically, so that if networking
   
10.    is idle expires is large enough to keep enough of warm entries,
    
11.    and when load increases it reduces to limit cache size.
    
12. */
    
13. 
    
14. static int rt_garbage_collect(struct dst_ops *ops)
    
15. {
    
16.         static unsigned long expire = RT_GC_TIMEOUT;
    
17.         static unsigned long last_gc;
    
18.         static int rover;
    
19.         static int equilibrium;
    
20.         struct rtable *rth, **rthp;
    
21.         unsigned long now = jiffies;
    
22.         int goal;
    
23. 
    
24.         /*
    
25.          * Garbage collection is pretty expensive,
    
26.          * do not make it too frequently.
    
27.          */
    
28.         /* 累计收集计数器 */
    
29.         RT_CACHE_STAT_INC(gc_total);
    
30. 
    
31.         /* 垃圾同步收集需要占用大量的CPU资源，所以不能太过频繁，如果两次收集的时间小于ip_rt_gc_min_interval，
    
32.          * 并且当前的缓存总数小于ip_rt_max_size，则累计忽略收集的计数器，退出。
    
33.          */
    
34.         if (now - last_gc < ip_rt_gc_min_interval &&
    
35.             atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
    
36.                 RT_CACHE_STAT_INC(gc_ignored);
    
37.                 goto out;
    
38.         }
    
39. 
    
40.         /* Calculate number of entries, which we want to expire now. */
    
41.          /* rt_garbage_colloect首先计算出一个goal(垃圾收集的目标数量)，当hash表总数超过
    
42.           * ip_rt_gc_elasticity * 2^ rt_hash_log时，系统认为缓存容量太大，存在风险
    
43.           * goal的初始值即设为该值，求得该值后，则存在两种情况，goal <= 0，意味着负载还不是很大，而
    
44.           * 反之，则意味着hash表负载较重，需要更严格的收集方式。
    
45.           */
    
46.         goal = atomic_read(&ipv4_dst_ops.entries) -
    
47.                 (ip_rt_gc_elasticity << rt_hash_log);
    
48.         if (goal <= 0) {
    
49.                 /* gc_thresh是垃圾回收的阀值，也可以看成，小于这个值的数目的缓存数目，用不着回收，如果equilibrium
    
50.                  * 的值小于gc_thresh，则让它等于这个——这可以看做，整个缓存数目中，除了要回收的goal，剩下的就是equilibrium */
    
51.                 if (equilibrium < ipv4_dst_ops.gc_thresh)
    
52.                         equilibrium = ipv4_dst_ops.gc_thresh;
    
53.                 /* 重新计算要回收的goal */
    
54.                 goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
    
55.                 //
    
56.                 if (goal > 0) {
    
57.                         equilibrium += min_t(unsigned int, goal >> 1, rt_hash_mask + 1);
    
58.                         goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
    
59.                 }
    
60.         } else {
    
61.                 /* We are in dangerous area. Try to reduce cache really
    
62.                  * aggressively.
    
63.                  */
    
64.                 /* hash表负载过重，需要一种更为严格的方式 */
    
65.                 goal = max_t(unsigned int, goal >> 1, rt_hash_mask + 1);
    
66.                 equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
    
67.         }
    
68.        
    
69.         /* 更新最后一次垃圾回收的时间戳 */
    
70.         if (now - last_gc >= ip_rt_gc_min_interval)
    
71.                 last_gc = now;
    
72.        
    
73.         /* 用不着进行回收处理 */
    
74.         if (goal <= 0) {
    
75.                 equilibrium += goal;
    
76.                 goto work_done;
    
77.         }

复制代码

接下来的工作，就是回收goal个缓存项，函数使用了一个复杂的三层循环来完成这一工作。先来看最深层的循环：

1.                         rthp = &rt_hash_table[k].chain;
   
2.                         spin_lock_bh(rt_hash_lock_addr(k));
   
3.                         while ((rth = *rthp) != NULL) {
   
4.                                 if (!rt_is_expired(rth) &&
   
5.                                         !rt_may_expire(rth, tmo, expire)) {
   
6.                                         tmo >>= 1;
   
7.                                         rthp = &rth->u.dst.rt_next;
   
8.                                         continue;
   
9.                                 }
   
10.                                 *rthp = rth->u.dst.rt_next;
    
11.                                 rt_free(rth);
    
12.                                 goal--;
    
13.                         }
    
14.                         spin_unlock_bh(rt_hash_lock_addr(k));
    
15.                         if (goal <= 0)
    
16.                                 break;

复制代码

这层循环是遍历第k个hash链(这个k是第二层循环的循环变量)，它使用rt_is_expired和rt_may_expire判断缓存项是否应该被删除，
删除缓存项的代码，在之前已经分析过了，这里不同的是递减goal值，以期让它小于或等于0，以达到回收的要求。如果不满足删除条件，
则减半tmo(rt_may_expire的第一个参数)，这个值越低，在第二个参数expire不变的情况下，缓存项被删除的可能性就越大。这是循环
过程中的一个重点。

1.                 for (i = rt_hash_mask, k = rover; i >= 0; i--) {
   
2.                         /* 将tmo初始赋为expire，而expire在第三层循环中也会减半，所以，越是循环（老是没有达到goal的数目），回收的
   
3.                         条件越严格 */
   
4.                         unsigned long tmo = expire;
   
5. 
   
6.                         k = (k + 1) & rt_hash_mask;
   
7.                         ……
   
8.                         spin_unlock_bh(rt_hash_lock_addr(k));
   
9.                         /* 在二层循环中，如果回收数目到达了goal，则退出该层循环之，这里并没有使用goto的直接跳出三层循环的目的在于，还没有设
   
10.                          * 置合适的rover值，结束循环的动作留给外层循环来完成。                         
    
11.                         */
    
12.                         if (goal <= 0)
    
13.                                 break;
    
14.                 }
    
15.                 /* 更新rover */
    
16.                 rover = k;

复制代码

这个循环中，除了tmo是一个重点之外，rover是另一个需要注意的地方。首先rover是一个静态变量，引入它的理由在于：
假设一个很大的缓存表，第一次从最开始处遍历回收，进行了一部份就满足了goal。退出循环。第二次回收，又重头开始，这意味着后面的缓存项则可能永远
没有机会被发现。
为了公平和效率，使用rover值记住上一次到达的hash链的位置，下一次就接着开始就行了。所以，for中，k值的初始就是rover。而在for循环结束后，需要
更新rover值。

理解了内层两层的循环，最外层就显示相对简单了：

1. do {
   
2.         ……
   
3.                 rover = k;
   
4. 
   
5.                 if (goal <= 0)
   
6.                         goto work_done;
   
7. 
   
8.                 /* Goal is not achieved. We stop process if:
   
9. 
   
10.                    - if expire reduced to zero. Otherwise, expire is halfed.
    
11.                    - if table is not full.
    
12.                    - if we are called from interrupt.
    
13.                    - jiffies check is just fallback/debug loop breaker.
    
14.                      We will not spin here for long time in any case.
    
15.                  */
    
16. 
    
17.                 RT_CACHE_STAT_INC(gc_goal_miss);
    
18. 
    
19.                 if (expire == 0)
    
20.                         break;
    
21. 
    
22.                 expire >>= 1;
    
23. #if RT_CACHE_DEBUG >= 2
    
24.                 printk(KERN_DEBUG "expire>> %u %d %d %d\n", expire,
    
25.                                 atomic_read(&ipv4_dst_ops.entries), goal, i);
    
26. #endif
    
27. 
    
28.                 if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
    
29.                         goto out;
    
30. }while (!in_softirq() && time_before_eq(jiffies, now));

复制代码

进入到最外层循环，如果goal已经达到条件，则结束循环，反之，则意味着回收工作并没有如期地完成，这需要设置更严格的回收策略来完成（hash表需要被再次扫描，My God!），
需这个更为严格，是通过将expire减半（因为for循环中，tmo的初始为expire），所以最内层的rt_may_expire就变得更加严厉，循环，遍历，直至回收到goal个缓存项，
当然，这样的结果就是有可能CPU被长期占用，所以，do...while中有也一些条件来提前结束这个工作：
1、expire到达0，不能一直地减半吧……
2、缓存项总数ipv4_dst_ops.entries小于ip_rt_max_size，这意味着hash表虽然负载很重，但是还没有满，还处理可以勉强接受的范围。
3、如果rt_garbage_collect是在软件断上下文中，或者扫描的时间已经超过1个jiffies，则应该让出CPU。

接下来就是一些收尾的工作：

1. 
   
2.         if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
   
3.                 goto out;
   
4.         /* 已经尽最大努力了，但是还是没有达到回收的目标，输出缓存溢出信息 */
   
5.         if (net_ratelimit())
   
6.                 printk(KERN_WARNING "dst cache overflow\n");
   
7.         RT_CACHE_STAT_INC(gc_dst_overflow);
   
8.         return 1;
   
9. 
   
10. work_done:
    
11.         /* 重新设置expire */
    
12.         expire += ip_rt_gc_min_interval;
    
13.         if (expire > ip_rt_gc_timeout ||
    
14.             atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
    
15.                 expire = ip_rt_gc_timeout;
    
16. #if RT_CACHE_DEBUG >= 2
    
17.         printk(KERN_DEBUG "expire++ %u %d %d %d\n", expire,
    
18.                         atomic_read(&ipv4_dst_ops.entries), goal, rover);
    
19. #endif
    
20. out:        return 0;
    
21. }

复制代码

5.2 异步回收
从以上分析可以看到，在极端的情况下，同步回收可能会非常占用资源，为了避免这种情况的出现，系统同时使用了另一个异步回收方式。所谓异步，就是通过一个
定时器，周期性地做回收工作。
在路由子系统的初始化中，定义了一个定时器expires_work：

1.         /* All the timers, started at system startup tend
   
2.            to synchronize. Perturb it a bit.
   
3.          */
   
4.         INIT_DELAYED_WORK_DEFERRABLE(&expires_work, rt_worker_func);
   
5. 
   
6. /*
   
7. * rt_worker_func() is run in process context.
   
8. * we call rt_check_expire() to scan part of the hash table
   
9. */
   
10. static void rt_worker_func(struct work_struct *work)
    
11. {
    
12.         rt_check_expire();
    
13.         schedule_delayed_work(&expires_work, ip_rt_gc_interval);
    
14. }

复制代码

异步回收的核心函数是rt_check_expire，然后调用schedule_delayed_word重新激活异步回收：

1. 
   
2. static void rt_check_expire(void)
   
3. {
   
4.         static unsigned int rover;
   
5.         unsigned int i = rover, goal;
   
6.         struct rtable *rth, *aux, **rthp;
   
7.         unsigned long samples = 0;
   
8.         unsigned long sum = 0, sum2 = 0;
   
9.         unsigned long delta;
   
10.         u64 mult;
    
11. 
    
12.         delta = jiffies - expires_ljiffies;
    
13.         expires_ljiffies = jiffies;
    
14.         mult = ((u64)delta) << rt_hash_log;
    
15.         if (ip_rt_gc_timeout > 1)
    
16.                 do_div(mult, ip_rt_gc_timeout);
    
17.         goal = (unsigned int)mult;
    
18.         if (goal > rt_hash_mask)
    
19.                 goal = rt_hash_mask + 1;
    
20.         for (; goal > 0; goal--) {
    
21.                 unsigned long tmo = ip_rt_gc_timeout;
    
22.                 unsigned long length;
    
23. 
    
24.                 i = (i + 1) & rt_hash_mask;
    
25.                 rthp = &rt_hash_table[i].chain;
    
26. 
    
27.                 if (need_resched())
    
28.                         cond_resched();
    
29. 
    
30.                 samples++;
    
31. 
    
32.                 if (*rthp == NULL)
    
33.                         continue;
    
34.                 length = 0;
    
35.                 spin_lock_bh(rt_hash_lock_addr(i));
    
36.                 while ((rth = *rthp) != NULL) {
    
37.                         prefetch(rth->u.dst.rt_next);
    
38.                         if (rt_is_expired(rth)) {
    
39.                                 *rthp = rth->u.dst.rt_next;
    
40.                                 rt_free(rth);
    
41.                                 continue;
    
42.                         }
    
43.                         if (rth->u.dst.expires) {
    
44.                                 /* Entry is expired even if it is in use */
    
45.                                 if (time_before_eq(jiffies, rth->u.dst.expires)) {
    
46. nofree:
    
47.                                         tmo >>= 1;
    
48.                                         rthp = &rth->u.dst.rt_next;
    
49.                                         /*
    
50.                                          * We only count entries on
    
51.                                          * a chain with equal hash inputs once
    
52.                                          * so that entries for different QOS
    
53.                                          * levels, and other non-hash input
    
54.                                          * attributes don't unfairly skew
    
55.                                          * the length computation
    
56.                                          */
    
57.                                         for (aux = rt_hash_table[i].chain;;) {
    
58.                                                 if (aux == rth) {
    
59.                                                         length += ONE;
    
60.                                                         break;
    
61.                                                 }
    
62.                                                 if (compare_hash_inputs(&aux->fl, &rth->fl))
    
63.                                                         break;
    
64.                                                 aux = aux->u.dst.rt_next;
    
65.                                         }
    
66.                                         continue;
    
67.                                 }
    
68.                         } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout))
    
69.                                 goto nofree;
    
70. 
    
71.                         /* Cleanup aged off entries. */
    
72.                         *rthp = rth->u.dst.rt_next;
    
73.                         rt_free(rth);
    
74.                 }
    
75.                 spin_unlock_bh(rt_hash_lock_addr(i));
    
76.                 sum += length;
    
77.                 sum2 += length*length;
    
78.         }
    
79.         if (samples) {
    
80.                 unsigned long avg = sum / samples;
    
81.                 unsigned long sd = int_sqrt(sum2 / samples - avg*avg);
    
82.                 rt_chain_length_max = max_t(unsigned long,
    
83.                                         ip_rt_gc_elasticity,
    
84.                                         (avg + 4*sd) >> FRACT_BITS);
    
85.         }
    
86.         rover = i;
    
87. }

复制代码

与同步回收类似，函数首先计算出一个goal，做为回收的标的外层循环的依据。内层循环也与同步回收非常相似，也是从上一次的rover标记处的hash链开始遍历，以示公平和效率：

1.                 unsigned int i = rover
   
2.                
   
3.                 i = (i + 1) & rt_hash_mask;
   
4.                 rthp = &rt_hash_table[i].chain;
   
5. 
   
6.                 while ((rth = *rthp) != NULL) {
   
7.                         /* 内存预取，用于优先目的 */
   
8.                         prefetch(rth->u.dst.rt_next);
   
9.                         /* 判断是否过期，如果过期释放之 */
   
10.                         if (rt_is_expired(rth)) {
    
11.                                 *rthp = rth->u.dst.rt_next;
    
12.                                 rt_free(rth);
    
13.                                 continue;
    
14.                         }
    
15.                         /*这个if...else if判断，表示如果缓存项的时间已经过期，或者通过rt_may_expire判断出符合删除条件，则视做已经老化(aged)的项，删除之
    
16.                          * 否则扫行nofree标签处，tmo减半，继续循环。                         
    
17.                         */
    
18.                         if (rth->u.dst.expires) {
    
19.                                 /* Entry is expired even if it is in use */
    
20.                                 if (time_before_eq(jiffies, rth->u.dst.expires)) {
    
21. nofree:
    
22.                                         tmo >>= 1;
    
23.                                         rthp = &rth->u.dst.rt_next;
    
24.                                         /*
    
25.                                          * We only count entries on
    
26.                                          * a chain with equal hash inputs once
    
27.                                          * so that entries for different QOS
    
28.                                          * levels, and other non-hash input
    
29.                                          * attributes don't unfairly skew
    
30.                                          * the length computation
    
31.                                          */
    
32.                                         for (aux = rt_hash_table[i].chain;;) {
    
33.                                                 if (aux == rth) {
    
34.                                                         length += ONE;
    
35.                                                         break;
    
36.                                                 }
    
37.                                                 if (compare_hash_inputs(&aux->fl, &rth->fl))
    
38.                                                         break;
    
39.                                                 aux = aux->u.dst.rt_next;
    
40.                                         }
    
41.                                         continue;
    
42.                                 }
    
43.                         } else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout))
    
44.                                 goto nofree;
    
45. 
    
46.                         /* Cleanup aged off entries. */
    
47.                         *rthp = rth->u.dst.rt_next;
    
48.                         rt_free(rth);
    
49.                 }

复制代码

独孤九贱

回复 4# 独孤九贱

后记

缓存的分析并没有解决我的问题。因为这涉及到对路由表查询的处理。但是从ip_route_input查询路由缓存的过程来看，它并没有对多路径做明显的支持。从对路由表的查询和处理结果来看，对于多路径缓存的处理分为两种情况：
1、如果内核编译支持多路径缓存，则同时为每个路径生成一个缓存项，但是因为ip_route_input并没有做支持，所以，始终查询命中到第一个缓存上面。我就是属于这种情况，数据仅走一边了。

2、如果内核编译不支持，则使用一个随机公平的算法生成缓存项，这样就可以做到流量分担了。不过它是基于流，而非单个报文的。

Godbach

非常感谢九贱兄的分享，为大家奉献这么多精华文章啊。

Godbach

回复  独孤九贱
MARK一下，哪天详细看看。
瀚海书香 发表于 2010-12-09 10:02

为了保持九贱兄文章的连续性。就把你的回帖删除了，因为你的后面还有两贴是九贱兄的，见谅。

瀚海书香

回复 6# Godbach
看来得重新MARK一下了。。。
多谢九贱兄分享这么好的分析。

Godbach

最近正在看《Linux网络技术内幕》，应该很快就看到路由部分了。这块还是很重要的，九贱兄的文章应该对于理解路由有很大的帮助。

瀚海书香

回复 4# 独孤九贱
有幸拜读这篇分析路由缓存的文章，感觉分析的很不错。
以前也曾经粗略的看了一下linux对多路路由的支持。当时曾发现一个问题，就是linux的路由缓存会在超过一定时间后自己清除掉，导致重新路由。这样一来对于长时间的链接来说就可能会出现再次路由后的路由与之前使用的路由不是同一个路由，导致链接断开。
不知九贱兄是否解决过这个问题？

Godbach

当时曾发现一个问题，就是linux的路由缓存会在超过一定时间后自己清除掉，导致重新路由。这样一来对于长时间的链接来说就可能会出现再次路由后的路由与之前使用的路由不是同一个路由，导致链接断开。

我还没深入看Linux的路由。但是我觉得你说的这种情况不应该出现啊，既然是一个长连接，那么要么它对路由的访问比较频繁，要么对路由有引用计数。不管是哪一种情况，按理说Linux都不应该清除吧。