七叶笔记 » golang编程 » Linux内核中链表list_head……的并发性

Linux内核中链表list_head……的并发性

我们被灌输过各种高效复杂的数据结构,比如rb tree,skip list等等,但现实中,我们经常用各种List管理我们的数据,因为它的操作非常简单。

  • 如果数据量小或者不太在乎时间,选择list_head。
  • 如果数据量大且对查找性能要求很高,读多写少的情况下,选择hlist。
  • 如果数据量大且对查找性能要求很高,写操作相对多的情况下,选择hlist_nulls。

在涉及并发操作的环境中,对list的add,delete肯定需要某种并发保护,因为:

  • 无论是add还是delete操作本身均不是原子操作。

但在具体的使用中,很多人搞不清该使用哪种类型的锁,于是就出现了以下的范式:

  • 懒省事者,无论是add,delete还是list_for_each,均用一把spinlock搞定。
  • 想优化性能却不想做太多的,直接把spinlock换成rwlock,一切看起来OK。
  • 如果写操作非常多且不能忍受性能损失,rculock搞定,同时保留add,delete的spinlock。

但是事情真的有这么复杂吗?我看未必。

事实上, 只要我们自己控制好写并发,读写是可以无锁并行的,只要保证我们的读操作中遍历 链表 的顺序是从前到后即可。

我们看看这是为什么,先看add list:

我们看到,之所以add操作对遍历不影响,是因为:

  • 第一,遍历是始终单向向前的。
  • 第二,先将新节点的next接入链表,使从new节点可继续遍历。
  • 第三,再将链表节点的next指向新节点,使new节点可被遍历到。

同时,我们知道在x86_64体系,对齐的指针操作是原子操作,所以,上面第三步就是原子操作,这保证了链表add操作和遍历操作是无冲突的:

  1. 遍历进程要么到达new。
  2. 遍历进程要么越过到达N2。
  3. 不会存在除1和2之外的其它情况。

然而,如何保证上图中的顺序不会被编译器或者CPU给reorder呢?这很容易保证:

  • 增加一个屏障即可!

长话短说, 几乎 可以认为,x86_64体系,只有write-read序列存在CPU乱序的情况,所以乱序的情况并不会发生在链表操作中, “几乎” 以外的情况,此处不谈。

需要C/C++ Linux 服务器架构师学习资料私信“资料”(资料包括C/C++,Linux,golang技术,Nginx,ZeroMQ, MySQL ,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK,ffmpeg等),免费分享

在Linux内核的链表操作接口中,上述的顺序以及原子保证是通过 _rcu 后缀来修饰的接口保证的,比如:

  • list_add_rcu/list_del_rcu
  • hlist_add_after_rcu/hlist_del_rcu
  • hlist_nulls_add_head_rcu/hlist_nulls_del_rcu

以上的这些接口可以同时和同版本的for_each遍历同时进行而不会出现并发问题!也就是说,在保证不会同时add和del的前提下,可以实现无锁遍历。

有了上面的理解,我们再看看del操作的流程:

和add操作一样,这也是个实实在在的RCU操作,其核心在于 最后更新

关于rcu,我们必须清楚一件事,那就是遍历操作本身要通过rcu readlock保护,保证delete的节点在rcu readlock释放后再回收。

最后,我们看一个关于hlist_nulls的遍历算法和其Insert/add, Remove /delete算法,来自内核文档Documents/RCU/rculist_nulls.txt:

  • Lookup算法:
 1) Lookup algo
--------------
rcu_read_lock()
begin:
obj = lockless_lookup(key);
if (obj) {
  if (!try_get_ref(obj)) // might fail for free objects
    goto begin;
  /*
   * Because a writer could delete object, and a writer could
   * reuse these object before the RCU grace period, we
   * must check key after getting the reference on object
   */  if (obj->key != key) { // not the object we expected
     put_ref(obj);
     goto begin;
   }
}
rcu_read_unlock();  
  • Insert/add算法:
 2) Insert algo :
----------------
/*
 * Please note that new inserts are done at the head of list,
 * not in the middle or end.
 */obj = kmem_cache_alloc(...);
lock_chain(); // typically a spin_lock()
obj->key = key;
/*
 * we need to make sure obj->key is updated before obj->next
 * or obj->refcnt
 */smp_wmb();
atomic_set(&obj->refcnt, 1);
hlist_add_head_rcu(&obj->obj_node, list);
unlock_chain(); // typically a spin_unlock()  
  • Remove/delete算法:
 3) Remove algo
--------------

if (put_last_reference_on(obj) {
   lock_chain(); // typically a spin_lock()
   hlist_del_init_rcu(&obj->obj_node);
   unlock_chain(); // typically a spin_unlock()
   kmem_cache_free(cachep, obj);
}  

在Linux内核的socket系统中,我们可以看到上述算法的具体实现,这是一个标准的算法,但是在特殊的环境下真的有必要这么复杂吗?lock_chain真的有必要吗?

以socket系统为例,我们知道,socket是可以在内核中的软中断上下文被创建和销毁的,这里就会存在并发问题,因此Insert/Insert,Remove/Remove,Insert/Remove之间就会存在并发,所以必须lock_chain。

但是如果我们保证节点的Insert和Remove均是在进程上下文的受控环境中进行的,比方说配置下发,那么我们只需要控制下发过程本身的并发即可,我们只要保证不会同时有Insert/Insert,Remove/Remove,Insert/Remove之间的并发即可,而这可以通过mutex来实现:

 int write_config(...)
{
mutext_lock(&global_mutex);
insert_or_remove_some_nodes(...);
mutex_unlock(&global_mutex);
}  

这样我们就可以省掉更多的spin开销,而我们知道mutex是可以re-schedule的,这便节省了CPU资源。

你也不要怼我说re-schedule切换进程也是有开销的,这个开销可能比spinlock的开销更大,我承认这个点,但是我并非站在这个谁的开销大的立场上说这件事的,我的立场是:

  • 受控的环境比争抢的环境更好,我一向崇尚仲裁。

至于怎么定义 “好” ,这便是形而上学的范畴了。

举个例子,Linux内核的路由rule就是这么实现的。

相关文章