本文是对vpp源码中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 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;
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).
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倍的页存储内存,将数据以遍历的方式复制到线性存储区。
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。
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
本文分享自 DPDK VPP源码分析 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!