Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1645505
  • 博文数量: 1493
  • 博客积分: 38
  • 博客等级: 民兵
  • 技术积分: 5834
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-19 17:28
文章分类

全部博文(1493)

文章存档

2016年(11)

2015年(38)

2014年(137)

2013年(253)

2012年(1054)

2011年(1)

分类: LINUX

2014-10-21 09:39:08

Linux内核连接跟踪锁的优化分析(1)

作者:gfree.wind@gmail.com

博客: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值锁,最终同时拥有两个锁。


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

阅读(607) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~