Linux内核连接跟踪锁的优化分析（1）

作者：[e-mail]

博客：linuxfocus.blog.chinaunix.net 
微博：weibo.com/glinuxer
QQ技术群：4367710

简介

很多网络设备都使用Linux作为自己的OS，但是由于Linux本身是一个通用的操作系统，因此各家厂商都会根据自己的技术水平和需求，对内核进行或多或少的改动。而Linux随着版本的迭代，也在不断的改善自己的代码，吸收各厂商的patch，如google提交的著名的RPS/RFS补丁。

本文将对最近内核提交的一个commit 93bb0ceb75be2fdfa9fc0dd1fb522d9ada515d9c 进行分析。该改动是用于改善多CPU环境下多全局的连接跟踪锁nfconntracklock的优化。优化的手段也是常见的方法，将锁的粒度变细，由一个全局的自旋锁，改为1024个自旋锁。其中还会涉及几个之前的内核优化。

优化分析

功能简介

连接跟踪是大多数网络设备的基础功能，其它高级功能如NAT，Firewall等都是建立在连接跟踪之上的。Linux内核要负责创建连接，匹配连接，过期连接，销毁连接等等工作。可以说，连接跟踪的性能要在相当大的程度上影响数据包的转发性能。

2.6内核代码分析

在Linux 2.6内核中，nf_conntrack_lock是一个全局的自旋锁，用于保护内核的连接跟踪表。但是，实际上连接跟踪表并不是简单的一个表。而老代码只是使用nf_conntrack_lock来保护，这样就相当于给一个锁赋予了太多太宽泛的职责。

内核的连接跟踪依赖于net命名空间struct netns_ct的成员变量。一个连接的完整生命过程要涉及多个表的操作，如下所示：

struct netns_ct {
    struct hlist_nulls_head *hash;
    struct hlist_head   *expect_hash;
    struct hlist_nulls_head unconfirmed;
    struct hlist_nulls_head dying; 

其中hash是真正的连接跟踪表，expect_hash用于expectation连接，unconfirmed用于未确定的连接，而dying用于即将销毁的连接。
在老的内核中对这四个表的访问，都依赖于这个全局的自旋锁nf_conntrack_lock的保护。很自然，这已经充分影响了多核的并行处理。

3.16 内核代码分析

内核虽然对连接跟踪锁一直在做优化，但是直到今年3月才彻底抛弃nf_conntrack_lock（说实话，我没想到内核这么晚才对这个锁动手。对于设备厂商来说，这样的锁早就给扔了）。下面我们就内核对于2.6中的各个连接表的优化进行分析。

后文的代码以最新稳定版本3.16的代码为准

expectation连接

内核引入了一个新的全局自旋锁nf_conntrack_expect_lock专门用于保护expectation连接。具体的代码在此就不罗列了。需要注意的是，为了避免死锁，这两个锁要么不能同时上锁，要么必须按照一定的顺序上锁。

unconfirmed和dying连接

这两种情况的表，在新代码中有了比较大的改动。struct netns_ct中的unconfirmed和dying被变更为动态per cpu变量struct ct_pcpu __percpu *pcpu_lists;。而struct ct_pcpu的结构如下：

struct ct_pcpu {
    spinlock_t      lock;
    struct hlist_nulls_head unconfirmed;
    struct hlist_nulls_head dying;
    struct hlist_nulls_head tmpl;
}; 

这里的ct_pcpu中的lock是用于用户空间与内核空间的同步。而多cpu间，即使仍然执行spinlock的上锁解锁动作，但实际上由于它们都是per cpu变量。因此并不会引起cpu之间的竞争。

一般的连接跟踪

真正的连接跟踪表netns_ct->hash实际上是一个hash表。之前的nf_conntrack_lock是对整个儿的hash表进行保护，那么我们可以减小锁的粒度来降低cpu之间的锁竞争。新内核去掉了独立的nf_conntrack_lock，取而代之的是1024个自旋锁。

-extern spinlock_t nf_conntrack_lock ;
+#ifdef CONFIG_LOCKDEP
+# define CONNTRACK_LOCKS 8
+#else
+# define CONNTRACK_LOCKS 1024
+#endif
+extern spinlock_t nf_conntrack_locks[CONNTRACK_LOCKS]; 

之所以在CONFIG_LOCKDEP下，将CONNTRACK_LOCKS的数量缩小为8，因为这种情况下spinlock占用内存过大。

1024个自旋锁依然小于连接hash表的桶的数量，但在cpu不多，且hash算法良好的情况下，依然可以取得相当不错的效果。如何确定使用哪个自旋锁呢？是根据original和reply两个方向的tuple计算hash值来确定使用哪个所。

由于同时需要两个锁，所以这时候引入了一个新问题。如何确定这两个锁的使用顺序呢？最直接的想法是，先上original方向的锁，再上reply方向的锁。然而这第一个念头，无疑是错误的。假设两个连接A和B，那么极有可能A的original方向的hash值和B的reply方向的hash值一样，并且A的reply方向的hash值与B的original方向的hash值也一样。这时，就出现了两个CPU需要使用两个锁a和b，结果CPU1已经拥有了b锁期望a锁，CPU2拥有了a锁期望b锁，因此出现了死锁。

内核采用一种小技巧。不考虑方向，只看hash值，永远让cpu先拥有hash值小的锁，再尝试另外一个。代码如下：

+/* return true if we need to recompute hashes (in case hash table was resized) */
+static bool nf_conntrack_double_lock(struct net *net, unsigned int h1,
+                                    unsigned int h2, unsigned int sequence)
+{
+       h1 %= CONNTRACK_LOCKS;
+       h2 %= CONNTRACK_LOCKS;
+       if (h1 <= h2) {
+               spin_lock(&nf_conntrack_locks[h1]);
+               if (h1 != h2)
+                       spin_lock_nested(&nf_conntrack_locks[h2],
+                                        SINGLE_DEPTH_NESTING);
+       } else {
+               spin_lock(&nf_conntrack_locks[h2]);
+               spin_lock_nested(&nf_conntrack_locks[h1],
+                                SINGLE_DEPTH_NESTING);
+       }
+       if (read_seqcount_retry(&net->ct.generation, sequence)) {
+               nf_conntrack_double_unlock(h1, h2);
+               return true;
+       }
+       return false;
+} 

这个函数通过比较h1和h2，先获得小hash值的锁，再尝试大hash值锁，最终同时拥有两个锁。

（最近由于工作太忙，已经大半年没有更新了。今天觉得实在是过意不去了，特意写了一篇，这是我最近两天看内核改动的所得。还没有写完，未完待续。貌似我又挖了一个坑）