Linux链表list_head/hlist_head/hlist_nulls_head的并发性

缺乏、安全感 2023-07-25 12:53 48阅读 0赞

我们被灌输过各种高效复杂的数据结构，比如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：

![å¨è¿éæå¥å¾çæè¿°][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70]

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

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

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

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

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

*  增加一个屏障即可！

长话短说，几乎 可以认为，x86\_64体系，只有write-read序列存在CPU乱序的情况，所以乱序的情况并不会发生在链表操作中， “几乎” 以外的情况，参见：  
https://blog.csdn.net/dog250/article/details/103911008

在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操作的流程：

![å¨è¿éæå¥å¾çæè¿°][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 1]

和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就是这么实现的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70]: /images/20230528/b7cf816959bc45fcb2703e1d6f9f720d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 1]: /images/20230528/cee96ac207ff412b8dc08022f54a6db4.png