bihash并不是线程安全的

近期在vpp-dev订阅邮箱中有一个关于bihash的在查询过程中返回的value数值为-1，导致在后续使用中产生崩溃。所以认为bihash并不是线程安全的。下面就一起来看一下邮件的内容。

邮件中提到在2020年2月8号的一封邮件中也提出bihash的在查询过程中返回value数值为-1的情况。

邮件链接：https://lists.fd.io/g/vpp-dev/message/15606,部分内容如下：当作为bihash的用户执行bihash操作时，不需要任何额外的加锁，bihash的api会在幕后为做这件事。 我只看到过一个暂时的情况：在高强度的添加/删除工作负载下，其他线程的执行查询操作时可能存在查找成功，但返回值是~0的情况，这种场景还是很容易存在的。

最近发生了看似相关的崩溃，当时在snat_main.flow_hash中的查找产生了一个value=-1，随后返回值作为目的索引在使用中产生了崩溃。为此详细研究了bihash并提出了自己的解决方案：

bihash线程不安全的原因

bihash表中的桶数永远不会改变。每个桶都有一个锁位。添加或删除时通过api接口 clib_bihash_add_del_inline_with_hash。该函数尽早获取桶锁并在持有锁的同时执行添加/删除/更新动作。显然这是安全的，我们需要关注读者。 通过clib_bihash_search_inline_with_hash和clib_bihash_search_inline_2_with_hash 进行查找。该函数定位桶并等待，直到锁定位被清除。

  /*查询到bihash桶*/
  b = BV (clib_bihash_get_bucket) (h, hash);
  /*如果桶为空，则直接返回*/
  if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
    return -1;
  /*判断桶是否已经加锁，持续等待直到锁释放*/
  if (PREDICT_FALSE (b->lock))
  {
      volatile BVT (clib_bihash_bucket) * bv = b;
      while (bv->lock)
    CLIB_PAUSE ();
  }

从上面代码开始之后，函数会进行key比对，而不需要进行bihash桶加锁。没有什么可以阻止更新程序更改读者当前正在查看的数据，甚至可以立即删除hash数据。此处是否可以正确工作的判定方法是我们是否可以对查找和更新操作的相对性能进行假设。在查找的早期检查锁定可确保当前没有正在进行的更新。如果查找比更新快，那么可能存在一种情况就是bihash数据被清空掉。事实上，我们在 clib_bihash_add_del_inline_with_hash 中有以下注释：

因为读取线程正在查看实时数据，所以我们必须格外小心。查询时不持有桶锁。我们需要比查询慢，超过查询检查桶锁的时刻。

不幸的是，这个假设不成立。任何线程都可能在任意时间被抢占。即使我们排除了抢占，也有微体系结构的怪癖（例如缓存、分支错误预测）可能会减慢查找到内存读取和更新将重叠的程度。 查找的核心是以下循环。请注意，检查键和获取值不是原子的，因此如果我们在中间被抢占，结果可能是假的。

 for (i = 0; i < limit; i++)
    {
      if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
    {
          /*此处并不是原子操作，可能bihash数值被删除，清空为全FF*/
      *valuep = v->kvp[i];
      return 0;
    }
    }

更新键值对的不同方式： (1) 添加动作：

clib_memcpy_fast (&(v->kvp[i].value),
                 &add_v->value, sizeof(add_v->value));
CLIB_MEMORY_STORE_BARRIER (); /* 确保值已经确定 内存屏障动作*/
clib_memcpy_fast (&(v->kvp[i]), &add_v->key,
                                sizeof (add_v->key));

密钥更新不是原子的，读者可以在中途观察到密钥更新。

(2) 更新动作：

clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));

再次不是原子的。读者可以见证 (old_k, new_v) 或 (new_k, old_v) 甚至来自旧密钥和新密钥的块的任意交错。 (3)删除动作：

clib_memset_u8(&(v->kvp[i]), 0xff, sizeof(*(add_v)));

同样也不是原子的。

修复

值得注意的是，bihash 永远不会崩溃。不过，它偶尔会产生虚假的结果。虽然 -1 很容易检查，但分析表明其他虚假结果也是可能的。分析可能存在的情况

1. 值半途中更新，可能与bihash_8_16。
2. 观察一个由于键部分更新而不存在的键。概率很低，因为哈希应该将它映射到相同的桶。 3.旧键与新值匹配。概率很低，因为查找应该在特定的位置被抢占以使查找发生。 尽管这些异常情况不太可能发生，但它们仍然是可能的并且可以被利用。 提议是为桶引入读锁。有利于读者的实现如下： 扩展 clib_bihash wirh "u64 rlocks[MAX_THREADS]"。根据线程索引，每个读取器在各自的数组项中发布其当前正在检查的桶号。引入填充以避免错误共享。 写入者锁定序列将是：1) 锁定桶；2）等到bucket号不在rlocks中。 读者锁序列：1）在rlocks中发布bucket号；2) 如果桶没有锁定，则完成；3) 否则从 rlocks 清除桶号，等待桶锁被释放并重新启动。

你好，感谢有见地的讨论！ 我明白高性能是 vpp 最重要的目标之一，因此某些解决方案可能不会成功。从我的 POV 来看，版本计数器会有所改进。它肯定会降低触发错误的可能性。 关于 isolcpus，目前这是作为优化而不是先决条件提出的。如果没有 isolcpus，线程可能会被抢占任意长的时间。这意味着无论我们为版本字段分配多少位，有时它们都不够。 无论线程如何安排，我都希望拥有强大的功能。是否可以使用 vpp 基准测试实验室来评估所提议解决方案的性能影响？ 最后，我想重新讨论读者锁定提案。我们的想法是我们不会在读取器路径中引入任何原子操作。阅读器发布它要在 int rlock[MAX_THREADS] 数组中检查的桶号。每个线程在 rlock 中使用一个不同的单元（由线程 id 确定），因此它可以是一个常规写入，然后是一个屏障。使用填充消除错误共享。 Writer 锁定当前实现的存储桶 (CAS)，然后等待存储桶编号从 rlock[] 中消失。 Reader 发布桶号，然后检查桶是否被锁定（常规写入、屏障、常规读取）。如果没有锁定就可以了，否则从 rlock 中删除桶号，等待锁定被释放，重新启动。 该提案没有引入任何新的原子操作。由于 rlock 阵列中的缓存行乒乓操作，仍然可能会出现减速。在最坏的情况下，读取器会花费我们 1 次额外的缓存未命中。可以与存储桶预取合并，使其基本上免费（如果有的话，bihash 用户预取存储桶的数量很少）。 最好的事物，

邮件回复中也提交了另外一种解决方案，增加一个原子操作计数，感兴趣的可以阅读以下patch：https://gerrit.fd.io/r/c/vpp/+/34326

不知道大家有没有遇到过上面的问题，有没有更好的解决方案，可以参与方案的讨论：https://lists.fd.io/g/vpp-dev/topic/86744671#20427