忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 4664 | 回复: 10

[内核同步] rculist_nulls使用详解:Netfilter会话表的锁保护 [复制链接]

论坛徽章:
0
发表于 2012-12-19 11:03 |显示全部楼层
本帖最后由 独孤九贱 于 2012-12-20 09:33 编辑

马上就要2012.12.21日了,在这个特殊的日子来临之际,发个灌水贴,以示纪念。

作者:独孤九贱
转载请注明出处。

1、概述
RCU锁相对于RWLOCK来讲,对于很少的写者,而多个读取并发的情况下,可以带来更好的并发性,关于原理及对比数据分析,这里就不再赘述了。内核也为链表使用RCU锁做了实现,即RCUList,事实上,这也是RCU锁一个最重要的应用之一。但是做为对RCULIst的扩展的RCUList_null,虽然引入有较长一段时间了,但是由于内核子系统使用较少,所以还不太知名,但是不巧的是网络栈的Netfilter的连接跟踪使用了它。内核对这个接口是这样描述的:
  1. Using hlist_nulls to protect read-mostly linked lists and objects using SLAB_DESTROY_BY_RCU allocations.
  2. Please read the basics in Documentation/RCU/listRCU.txt
复制代码
本文将结合Netfilter的conntrack表以及内核文档中对rculist_nulls的使用的介绍,从rculist_null、自旋锁、引用计数器、定时器的同步几个方面来详细分析其用法。所以阅读本文需要参考的nf_conntrack_core.c和Documentation/RCU/rculist_nulls.txt 两个文件。

2、数据结构
  1. struct nf_conn {
  2.         /* Usage count in here is 1 for hash table/destruct timer, 1 per skb,
  3.            plus 1 for any connection(s) we are `master' for */
  4.         struct nf_conntrack ct_general;

  5.         spinlock_t lock;
  6.        
  7.         /* XXX should I move this to the tail ? - Y.K */
  8.         /* These are my tuples; original and reply */
  9.         struct nf_conntrack_tuple_hash tuplehash[IP_CT_DIR_MAX];
  10.        
复制代码
ct_general中包含了引用计数器:
  1. #if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE)
  2. struct nf_conntrack {
  3.         atomic_t use;
  4. };
  5. #endif
复制代码
lock是用于整个结构的互斥锁

ct的两个方向的tuple都包含了hlist_nulls节点成员:
  1. /* Connections have two entries in the hash table: one for each way */
  2. struct nf_conntrack_tuple_hash {
  3.         struct hlist_nulls_node hnnode;
  4.         ……
  5. };
复制代码
另外,整个conntrack表,有一个全局锁
  1. spinlock_t nf_conntrack_lock ;
复制代码
它主要用于对表的添加、修改、遍历(不是查找)等操作。

conntrack使用了以上结构体成员或变量来实现相应的并发互斥。

3、节点分配与分初始化

整个高速缓存的创建,注意SLAB_DESTROY_BY_RCU的使用:
  1. static int nf_conntrack_init_net(struct net *net)
  2. {
  3.         //初始化节点总的计数器
  4.         atomic_set(&net->ct.count, 0);
  5.        
  6.         //分配高速缓存
  7.         net->ct.nf_conntrack_cachep = kmem_cache_create(net->ct.slabname,
  8.                                                         sizeof(struct nf_conn), 0,
  9.                                                         SLAB_DESTROY_BY_RCU, NULL);       
  10. }
复制代码
init_conntrack函数完成节点的分配与初始化:
  1.         //分配高速缓存
  2.         ct = kmem_cache_alloc(net->ct.nf_conntrack_cachep, gfp);

  3.         //初始化锁、引用计数器等成员       
  4.         spin_lock_init(&ct->lock);
  5.        
  6.         ct->tuplehash[IP_CT_DIR_ORIGINAL].hnnode.pprev = NULL;
  7.        
  8.         /*
  9.          * changes to lookup keys must be done before setting refcnt to 1
  10.          */
  11.         smp_wmb();
  12.         atomic_set(&ct->ct_general.use, 1);
复制代码
这与RCULIst_null.txt中介绍是相同的,当然,文档中同时讲了节点的插入操作,关于conntrack的插入,后文将会分析到:
  1. 2) Insert function :
  2. --------------------
  3. /*
  4. * Please note that new inserts are done at the head of list,
  5. * not in the middle or end.
  6. */ obj = kmem_cache_alloc(cachep); lock_chain(); // typically a spin_lock() obj->key = key; /*
  7. * changes to obj->key must be visible before refcnt one
  8. */ smp_wmb(); atomic_set(&obj->refcnt, 1); /*
  9. * insert obj in RCU way (readers might be traversing chain)
  10. */ hlist_nulls_add_head_rcu(&obj->obj_node, list); unlock_chain(); // typically a spin_unlock()
复制代码
4、节点的插入
__nf_conntrack_confirm函数完成相应的插入操作:

  1. /* Confirm a connection given skb; places it in hash table */
  2. int
  3. __nf_conntrack_confirm(struct sk_buff *skb)
  4. {
  5.         ……
  6.         //加全局锁
  7.         spin_lock_bh(&nf_conntrack_lock);

  8.         //加引用计数器
  9.         atomic_inc(&ct->ct_general.use);

  10.         /* Since the lookup is lockless, hash insertion must be done after
  11.          * starting the timer and setting the CONFIRMED bit. The RCU barriers
  12.          * guarantee that no other CPU can find the conntrack before the above
  13.          * stores are visible.
  14.          */
  15.         __nf_conntrack_hash_insert(ct, hash, repl_hash);
  16.        
  17.         spin_unlock_bh(&nf_conntrack_lock);
  18.         ……
  19. }
复制代码
分配节点和插入的时候,引用计数器都加了1.这与netfilter的语义有关,分配的时候,将其设置为1,
与查找的时候,增加引用计数器原因相同:它们都是为skb使用conntrack准备的。而这里加1,则是为hash
表准备的:表明hash表已经在使用它了。
  1. //具体的插入函数       
  2. static void __nf_conntrack_hash_insert(struct nf_conn *ct,
  3.                                        unsigned int hash,
  4.                                        unsigned int repl_hash)
  5. {
  6.         struct net *net = nf_ct_net(ct);

  7.         hlist_nulls_add_head_rcu(&ct->tuplehash[IP_CT_DIR_ORIGINAL].hnnode,
  8.                            &net->ct.hash[hash]);
  9.         hlist_nulls_add_head_rcu(&ct->tuplehash[IP_CT_DIR_REPLY].hnnode,
  10.                            &net->ct.hash[repl_hash]);
  11. }
复制代码
可以看到,这里的分配、插入操作,都是rculist_nulls.txt中代码的翻版。
未完,待续……

评分

参与人数 1可用积分 +8 收起 理由
Godbach + 8 赞一个!

查看全部评分

论坛徽章:
0
发表于 2012-12-19 11:04 |显示全部楼层
本帖最后由 独孤九贱 于 2012-12-19 11:12 编辑

5、查找
查找是rculist_null最为重要的应用,可以说所有的准备都是为它而来,
____nf_conntrack_find完成hash表的查找工作,它返回要查找的节点,
该函数的结构为标准的hlist_nulls的查找,但是这个函数没有RCU锁的保护,
作者将其一分为二,锁放在上层了调用函数了:

  1. /*
  2. * Warning :
  3. * - Caller must take a reference on returned object
  4. *   and recheck nf_ct_tuple_equal(tuple, &h->tuple)
  5. * OR
  6. * - Caller must lock nf_conntrack_lock before calling this function
  7. */
  8. static struct nf_conntrack_tuple_hash *
  9. ____nf_conntrack_find(struct net *net, u16 zone,
  10.                       const struct nf_conntrack_tuple *tuple, u32 hash)
  11. {
  12.         struct nf_conntrack_tuple_hash *h;
  13.         struct hlist_nulls_node *n;
  14.         unsigned int bucket = hash_bucket(hash, net);

  15.         /* Disable BHs the entire time since we normally need to disable them
  16.          * at least once for the stats anyway.
  17.          */
  18.         local_bh_disable();
  19. begin:
  20.         hlist_nulls_for_each_entry_rcu(h, n, &net->ct.hash[bucket], hnnode) {
  21.                 if (nf_ct_tuple_equal(tuple, &h->tuple) &&
  22.                     nf_ct_zone(nf_ct_tuplehash_to_ctrack(h)) == zone) {
  23.                         NF_CT_STAT_INC(net, found);
  24.                         local_bh_enable();
  25.                         return h;
  26.                 }
  27.                 NF_CT_STAT_INC(net, searched);
  28.         }
  29.         /*
  30.          * if the nulls value we got at the end of this lookup is
  31.          * not the expected one, we must restart lookup.
  32.          * We probably met an item that was moved to another chain.
  33.          */
  34.         if (get_nulls_value(n) != bucket) {
  35.                 NF_CT_STAT_INC(net, search_restart);
  36.                 goto begin;
  37.         }
  38.         local_bh_enable();

  39.         return NULL;
  40. }
复制代码
上层调用函数使用RCU锁保护,来调用该查找函数,并且如果查找命中,增加引用计数器:

  1. /* Find a connection corresponding to a tuple. */
  2. static struct nf_conntrack_tuple_hash *
  3. __nf_conntrack_find_get(struct net *net, u16 zone,
  4.                         const struct nf_conntrack_tuple *tuple, u32 hash)
  5. {
  6.         struct nf_conntrack_tuple_hash *h;
  7.         struct nf_conn *ct;

  8.         rcu_read_lock();
  9. begin:
  10.         h = ____nf_conntrack_find(net, zone, tuple, hash);
  11.         if (h) {
  12.                 ct = nf_ct_tuplehash_to_ctrack(h);
  13.                 if (unlikely(nf_ct_is_dying(ct) ||
  14.                              !atomic_inc_not_zero(&ct->ct_general.use)))
  15.                         h = NULL;
  16.                 else {
  17.                         if (unlikely(!nf_ct_tuple_equal(tuple, &h->tuple) ||
  18.                                      nf_ct_zone(ct) != zone)) {
  19.                                 nf_ct_put(ct);
  20.                                 goto begin;
  21.                         }
  22.                 }
  23.         }
  24.         rcu_read_unlock();

  25.         return h;
  26. }
复制代码
这同样与rculist_nulls.txt中描述是完全相同的,只是实现的时候切割开了:
  1. 1) lookup algo
  2. head = &table[slot];
  3. rcu_read_lock(); begin: hlist_nulls_for_each_entry_rcu(obj, node, head, member) { if (obj->key == key) { if (!try_get_ref(obj)) // might fail for free objects goto begin; if (obj->key != key) { // not the object we expected put_ref(obj);
  4.          goto begin; } goto out; } /*
  5. * if the nulls value we got at the end of this lookup is
  6. * not the expected one, we must restart lookup.
  7. * We probably met an item that was moved to another chain.
  8. */
  9. if (get_nulls_value(node) != slot) goto begin; obj = NULL;
  10. out: rcu_read_unlock();
复制代码
6、更新
当查找到的节点需要对其成员进行操作时,需要加节点锁,如下所示:
  1. static int tcp_packet(struct nf_conn *ct,
  2.                       const struct sk_buff *skb,
  3.                       unsigned int dataoff,
  4.                       enum ip_conntrack_info ctinfo,
  5.                       u_int8_t pf,
  6.                       unsigned int hooknum)
  7. {
  8.         spin_lock_bh(&ct->lock);
  9.        
  10.         //对ct成员的若干操作
  11.         ……
  12.        
  13.         spin_unlock_bh(&ct->lock);
  14. }
复制代码
这里,最重要的理解查找操作不需要更多的自旋锁保护,只需rcu_read_lock即可。这涉及到RCU锁的原理与实现,本文侧重于rculist_null的使用接口介绍与分析,不再RCU相关东东了。
未完,待续……


   

1人打赏

论坛徽章:
0
发表于 2012-12-19 11:05 |显示全部楼层
7、删除
7.1 超时释放

节点的定时器超时,会调用death_by_timeout函数:

  1. static void death_by_timeout(unsigned long ul_conntrack)
  2. {
  3.         ……
  4.         nf_ct_delete_from_lists(ct);
  5.         nf_ct_put(ct);
  6. }
复制代码
nf_ct_delete_from_lists完成从链表中释放
  1. void nf_ct_delete_from_lists(struct nf_conn *ct)
  2. {
  3.         ……
  4.         //全局锁
  5.         spin_lock_bh(&nf_conntrack_lock);
  6.         /* Inside lock so preempt is disabled on module removal path.
  7.          * Otherwise we can get spurious warnings. */
  8.         ……
  9.         clean_from_lists(ct);
  10.         spin_unlock_bh(&nf_conntrack_lock);
  11. }
复制代码
对于添加和删除链表的操作,是需要一个链表的自旋锁保护,这里是nf的全局锁nf_conntrack_lock。
  1. static void
  2. clean_from_lists(struct nf_conn *ct)
  3. {
  4.         pr_debug("clean_from_lists(%p)\n", ct);
  5.         hlist_nulls_del_rcu(&ct->tuplehash[IP_CT_DIR_ORIGINAL].hnnode);
  6.         hlist_nulls_del_rcu(&ct->tuplehash[IP_CT_DIR_REPLY].hnnode);

  7.         /* Destroy all pending expectations */
  8.         nf_ct_remove_expectations(ct);
  9. }
复制代码
nf_ct_put释放节点高速缓存:

  1. /* decrement reference count on a conntrack */
  2. static inline void nf_ct_put(struct nf_conn *ct)
  3. {
  4.         NF_CT_ASSERT(ct);
  5.         nf_conntrack_put(&ct->ct_general);
  6. }

  7. static inline void nf_conntrack_put(struct nf_conntrack *nfct)
  8. {
  9.         if (nfct && atomic_dec_and_test(&nfct->use))
  10.                 nf_conntrack_destroy(nfct);
  11. }
复制代码
nf_conntrack_destroy事实上会调用destroy_conntrack->nf_conntrack_free函数,
最终释放高速缓存:

  1. void nf_conntrack_free(struct nf_conn *ct)
  2. {
  3.         ……
  4.         //递减计数器
  5.         atomic_dec(&net->ct.count);
  6.         //释放高速缓存
  7.         kmem_cache_free(net->ct.nf_conntrack_cachep, ct);
  8. }
复制代码
这段代码示例很好地展示了全局锁与单个节点的引用计数器的配合使用,完整全部的释放工作。

7.2 使用者释放
conntrack查找命中后,会将找到的ct节点指针赋给skb
  1. skb->nfct = &ct->ct_general;                        //resolve_normal_ct函数
复制代码
当skb被释放时,会调用上述nf_conntrack_put函数尝试释放引用:
  1. static void skb_release_head_state(struct sk_buff *skb)
  2. {
  3. #if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE)
  4.         nf_conntrack_put(skb->nfct);
  5. #endif
  6. }
复制代码
这里有意思是的skb释放是直接释放高速缓存,并不涉及链表操作,有两种场景:
a、超时函数并没有触发,那么只里仅是增加、减少引用计数器而已,不涉及其它;
b、超时函数被调用,节点被从hash表中删除并减少引用计数器,而释放则放到这里;

同样地,这也与文档中描述相同:
  1. 3) Remove algo
  2. -------------- Nothing special here, we can use a standard RCU hlist deletion. But thanks to SLAB_DESTROY_BY_RCU, beware a deleted object can be reused very very fast (before the end of RCU grace period)
  3. if (put_last_reference_on(obj) { lock_chain(); // typically a spin_lock()
  4.    hlist_del_init_rcu(&obj->obj_node);
  5.    unlock_chain(); // typically a spin_unlock()
  6.    kmem_cache_free(cachep, obj); }
复制代码
8、全清       

下面来看对整个hash表的节点的清空操作:

  1. static void nf_conntrack_cleanup_net(struct net *net)
  2. {
  3. i_see_dead_people:
  4.         nf_ct_iterate_cleanup(net, kill_all, NULL);

  5.         //ct.count为整个hash表的节点计数器,这里循环直至所有节点被释放,
  6.         //这是因为此时模块移除时,Netfilter Hook函数或网络软中断函数可能拥有conntrack节点。
  7.         if (atomic_read(&net->ct.count) != 0) {
  8.                 schedule();
  9.                 goto i_see_dead_people;
  10.         }

  11.         ……
  12.         //释放高速缓存       
  13.         kmem_cache_destroy(net->ct.nf_conntrack_cachep);
  14.         ……
  15. }
复制代码
nf_ct_iterate_cleanup遍历整个hash表,释放节点:

  1. void nf_ct_iterate_cleanup(struct net *net,
  2.                            int (*iter)(struct nf_conn *i, void *data),
  3.                            void *data)
  4. {
  5.         struct nf_conn *ct;
  6.         unsigned int bucket = 0;

  7.         while ((ct = get_next_corpse(net, iter, data, &bucket)) != NULL) {
  8.                 /* Time to push up daises... */
  9.                 if (del_timer(&ct->timeout))
  10.                         death_by_timeout((unsigned long)ct);
  11.                 /* ... else the timer will get him soon. */

  12.                 nf_ct_put(ct);
  13.         }
  14. }
复制代码
这里需要注意的是定时器的删除操作,即del_timer函数的调用:
1、当定时器已经被调度执行,其将直接返回0,nf_ct_put将被执行,
这意味着后续的nf_ct_put函数可与在其它CPU上执行的定时器超时函数death_by_timeout并行执行,
它们的互斥显然由引用计数器来实现。而不需要再调用del_timer_sync等待同步;

2、另一种情况,定时器并没有被调度,则直接删除定时器,并且直接调用death_by_timeout来实现删除操作;

get_next_corpse在遍历hash表时,查找节点的时候,会增加引用计数器,所以,循环内部最后调用nf_ct_put(ct)释放之,而不是:

  1.                 if (del_timer(&ct->timeout)){
  2.                         death_by_timeout((unsigned long)ct);
  3.                         continue;
  4.                 }
复制代码
get_next_corpsehash表的遍历,逐个返回节点:

  1. /* Bring out ya dead! */
  2. static struct nf_conn *
  3. get_next_corpse(struct net *net, int (*iter)(struct nf_conn *i, void *data),
  4.                 void *data, unsigned int *bucket)
  5. {
  6.         struct nf_conntrack_tuple_hash *h;
  7.         struct nf_conn *ct;
  8.         struct hlist_nulls_node *n;

  9.         spin_lock_bh(&nf_conntrack_lock);
  10.         for (; *bucket < net->ct.htable_size; (*bucket)++) {
  11.                 hlist_nulls_for_each_entry(h, n, &net->ct.hash[*bucket], hnnode) {
  12.                         ct = nf_ct_tuplehash_to_ctrack(h);
  13.                         if (iter(ct, data))
  14.                                 goto found;
  15.                 }
  16.         }
  17.         hlist_nulls_for_each_entry(h, n, &net->ct.unconfirmed, hnnode) {
  18.                 ct = nf_ct_tuplehash_to_ctrack(h);
  19.                 if (iter(ct, data))
  20.                         set_bit(IPS_DYING_BIT, &ct->status);
  21.         }
  22.         spin_unlock_bh(&nf_conntrack_lock);
  23.         return NULL;
  24. found:
  25.         atomic_inc(&ct->ct_general.use);
  26.         spin_unlock_bh(&nf_conntrack_lock);
  27.         return ct;
  28. }
复制代码
可以看到,遍历的时候,同样需要全局锁的保护,而单个节点的使用,依靠的是引用计数器。

全局终!!!

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2012-12-19 11:45 |显示全部楼层
回复 2# 独孤九贱
九贱兄又有大作问世,好好拜读先。


   

论坛徽章:
0
发表于 2012-12-19 11:50 |显示全部楼层
Godbach 发表于 2012-12-19 11:45
回复 2# 独孤九贱
九贱兄又有大作问世,好好拜读先。

客气,我也是因为工作需要,看一下,然后把笔记放上来了,大家共同学习嘛

论坛徽章:
10
戌狗
日期:2013-10-17 09:43:0215-16赛季CBA联赛之广东
日期:2018-02-05 11:22:1215-16赛季CBA联赛之八一
日期:2016-07-04 12:26:1815-16赛季CBA联赛之青岛
日期:2016-06-08 11:15:4115-16赛季CBA联赛之辽宁
日期:2016-04-05 10:10:1415-16赛季CBA联赛之辽宁
日期:2016-03-11 11:11:48酉鸡
日期:2014-12-18 14:35:48狮子座
日期:2014-02-20 10:14:07寅虎
日期:2013-12-02 13:48:2915-16赛季CBA联赛之广夏
日期:2018-03-21 08:51:10
发表于 2012-12-19 15:15 |显示全部楼层
支持楼主大作!学习下~

论坛徽章:
6
金牛座
日期:2013-10-08 10:19:10技术图书徽章
日期:2013-10-14 16:24:09CU十二周年纪念徽章
日期:2013-10-24 15:41:34狮子座
日期:2013-11-24 19:26:19未羊
日期:2014-01-23 15:50:002015年亚洲杯之阿联酋
日期:2015-05-09 14:36:15
发表于 2012-12-19 18:07 |显示全部楼层
回复 1# 独孤九贱
一到年底九贱兄就有干货啊

   

论坛徽章:
4
天秤座
日期:2013-10-18 13:58:33金牛座
日期:2013-11-28 16:17:01辰龙
日期:2014-01-14 09:54:32戌狗
日期:2014-01-24 09:23:27
发表于 2012-12-19 18:13 |显示全部楼层
马克一下,回头要研究。

论坛徽章:
0
发表于 2018-03-07 15:42 |显示全部楼层
你好,独孤老师。
我也在看Linux内核连接跟踪这一块的代码,大部分函数明白了。有个问题, 为什么要增加ct->ct_general.use的引用计数,既然是要清楚这个连接跟踪,增加引用计数有什么意义?
  1.         atomic_inc(&ct->ct_general.use);
复制代码

论坛徽章:
0
发表于 2018-03-07 21:06 |显示全部楼层
不明白为什么get_next_corpse要增加计数
get_next_corpse在遍历hash表时,查找节点的时候,会增加引用计数器,所以,循环内部最后调用nf_ct_put(ct)释放之
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:wangnan@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP