VPPinfra---bihash简介

本文是对vpp源码中bihash的内存分布及结构体字段的简单介绍，由于时间有限，很多细节没有分析，后续有时间再进行详细补充。

Bihash简介

Bihash （Bounded-index Extensible Hashing） 边界索引可扩展的hash。VPP使用Bihash来解决一类键值（key/value）精确匹配查找问题。Bihash实现的优势包括： 1、哈希表容量可动态扩展，最高测试可达100M条记录数； bihash采用两级数据结构，一级是桶，二级是页；桶的大小是在初始化的时候确定的，不可以动态修改，这种结构的好处就是在哈希冲突时，可以通过扩页来解决，避免大量数据搬移带来的性能损耗。 2、查找性能不会随着表中记录数量的增加而剧烈下降； 在bihash初始化时，需要设置合理的bucket的数量及内存大小。根据经验来看，bucket的大小=用户总的计算量/4 （一页记录4个kv对，这个也是根据需要可调整的）；所设置的内存量应该可以轻松地包含所有的记录，并允许hash冲突。bihash哈希的内存和vpp主内存mainheap是分开的。 3、读操作不需要锁； 实际上在bihash 查询操作中存在自旋锁+内存屏障，但是这种概率也是非常低的（代码中有分支预测处理），是在查询到当前桶并且存在添加和删除的时候，才存在锁。 4、模板实现机制，可以容易扩展，以实现特定长度的键值应用；

bihash相关算法介绍

1、Bihash具有两级数据结构：

2、bihash典型的内存分布图如下：

bihash h->alloc_arena = mmap映射的基地址，默认是使用2M页大小对齐来映射内容的。并且起始地址和结束地址都是2M页大小对齐的（应该是为了后面使用2M大页）只是申请了连续的虚拟内存。 在申请h->buckets的地址是使用BV (alloc_aligned)函数中从基地址开始按照2M大页内存映射；如果系统没有设置大页，会再次按照系统页大小申请。

/*mmap flag是参数中MAP_HUGETLB 和 BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT
 *设置表示启用大页内存，可以mmap手册查询到
  */
  /* default is 2MB, use 30 for 1GB */
#ifndef BIHASH_LOG2_HUGEPAGE_SIZE
#define BIHASH_LOG2_HUGEPAGE_SIZE 21
#endif
int mmap_flags_huge = (mmap_flags | MAP_HUGETLB | MAP_LOCKED |
           BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT);
rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags_huge, -1, 0);

这里大页默认设置了2MB，如果环境内存充足，可以使用1G大页，会提升一部分性能。

bihash 还有一种分布方式，就是buckets[0]后面紧跟一个页大小。这种方式的只有一个模板clib_bihash_kv_16_8_t再使用。这种分布方式有什么好处？应该充分利用的cacheline的特性，桶和键值对内存大小不到一个cackeline大小。提高cacheline命中率。

#define BIHASH_KVP_AT_BUCKET_LEVEL 1  #为1表示按照当前的内存分布。
typedef struct
{
  u64 key[2];
  u64 value;
} clib_bihash_kv_16_8_t;

3、bihash值的使用

1、桶的索引：bucket_index = hash & (h->nbuckets - 1)； 2、桶内页的数量：(1 << log2_pages) 如果linear_search !=1时，通过hash >>= h->log2_nbuckets;hash &= (1 << log2_pages) - 1; 获取存储的页索引page_num = hash;即bucket、page的双层hash。 如果linear_search ==1时，表示线性存储，需要通过线性探测来查询数据，探测长度等于 (1 << log2_pages).

4、bihash参数h->freelist说明

h->freelist 是在主内存上申请的，也是vec结构。存储的是偏移量offset， 等于当前kvp的首地址到h->alloc_arena的距离. BVT (clib_bihash_value) 是个枚举类型，当存储到freelists区时，使用变量next_free_as_u64来存储偏移量offset，当成一个链表结构来使用。 下标对应的是buckets中的参数log2_pages，一般是在出现hash页冲突的时候进行2倍的扩充页存储区，先从freelists区对应的页大小来申请，如果没有空闲的，再从bihash的内存区进行申请；2倍扩充页存储区后，如果还是存在页冲突，再次进行4倍扩充页存储区（将2倍扩充的内存freelist[1]区）；如果4倍扩充还是存在页冲突，则转换成线性存储。从freelist区拿出2倍的页存储内存，将数据以遍历的方式复制到线性存储区。

5、working_copy区介绍

BVT (clib_bihash_value) ** working_copies /*工作区*/
int *working_copy_lengths；/*页数量*/
BVT (clib_bihash_bucket) saved_bucket;/*保存原始桶的内容*/

bihash是基于多线程的，再进行add操作时，首先会对桶进行加锁（这段时间时不允许读的），判断当前桶中页是否还有空闲区域存储kv对；如果有，直接添加到空闲区返回，如果没有则进行页扩充；页扩充前会进行bihash内存alloc锁，会在working_copies区上进行操作。

/*桶的锁，主要是为了对当前桶的读和写进行互斥*/
BV (clib_bihash_lock_bucket) (b);
/*bihash 内存alloc锁，主要是为了bihash 页内存kv数据存储区申请的互斥*/
BV (clib_bihash_alloc_lock) (h);

working_copies[thread_index]= 在bihash内存上申请b->log2_pages大小的页内存。 working_copy_lengths[thread_index] = b->log2_pages。

bihah相关结构体字段说明：

总结

bihash在vpp使用比较广，在NAT模块、路由模块、ip报文分片重组等一些大规格表项中都有使用。VPP也一直在对bihash进行性能的优化及模板的增加。上面提到的模板clib_bihash_kv_16_8_t的bihash内存分布方式就是性能优化很好的例子。最近在vpp-dev邮箱中对bihash线程安全性提出了质疑，感兴趣的可以去看一看。

参考资料

1、vpp开发文档。 https://fd.io/docs/vpp/master/gettingstarted/developers/bihash.html

另外推荐一个dpdk学习资料的github库，里面资料还是比较多的，值得去学习一下：https://github.com/0voice/dpdk_engineer_manual