DPDK20.05 hash表4 – rte_hash_lookup
rte_hash_lookup() 函数在hash表中查找指定的key。
1、rte_hash_lookup()
1 2 3 4 5 | int32_t rte_hash_lookup(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL); } |
rte_hash_hash函数根据key计算得到对应的hash值。
2、__rte_hash_lookup_with_hash()
使用hash值及key进行查找。
1 2 3 4 5 6 7 8 | static inline int32_t __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig, void **data) { if (h->readwrite_concur_lf_support) /* 如果支持读写者并发,则调用该 xxx_lf 函数 */ return __rte_hash_lookup_with_hash_lf(h, key, sig, data); else /* 如果不支持读写者并发,则调用该 xxx_l 函数 */ return __rte_hash_lookup_with_hash_l(h, key, sig, data); } |
3、__rte_hash_lookup_with_hash_lf()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | static inline int32_t __rte_hash_lookup_with_hash_lf(const struct rte_hash *h, const void *key, hash_sig_t sig, void **data) { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *bkt, *cur_bkt; uint32_t cnt_b, cnt_a; int ret; uint16_t short_sig; short_sig = get_short_sig(sig); prim_bucket_idx = get_prim_bucket_index(h, sig); sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); do { /* 在查找开始之前获取 hash表修改的计数器。 * acquire语义可以确保search_one_bucket中的加载操作不会影响负载 */ cnt_b = __atomic_load_n(h->tbl_chng_cnt, __ATOMIC_ACQUIRE); /* 在主bucket中查找 */ bkt = &h->buckets[prim_bucket_idx]; ret = search_one_bucket_lf(h, key, short_sig, data, bkt); if (ret != -1) /* 如果找到就直接返回 */ return ret; /* 在次级bucket及关联的扩展bucket中查找 */ bkt = &h->buckets[sec_bucket_idx]; FOR_EACH_BUCKET(cur_bkt, bkt) { ret = search_one_bucket_lf(h, key, short_sig, data, cur_bkt); if (ret != -1) /* 如果找到就直接返回 */ return ret; } /* The loads of sig_current in search_one_bucket * should not move below the load from tbl_chng_cnt. */ __atomic_thread_fence(__ATOMIC_ACQUIRE); /* 再次读取 tbl_chng_cnt 变量,以检查在搜索期间hash表是否被修改。 * 如果被修改,则重新进行查找。该加载操作没有负载影响。 * 对于 cnt_b 的load acquire、主bucket中的key索引,以及次bucket * 中的key索引,可以确保其不会产生负载 */ cnt_a = __atomic_load_n(h->tbl_chng_cnt, __ATOMIC_ACQUIRE); } while (cnt_b != cnt_a); return -ENOENT; } |
4、__rte_hash_lookup_with_hash_l() 函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | static inline int32_t __rte_hash_lookup_with_hash_l(const struct rte_hash *h, const void *key, hash_sig_t sig, void **data) { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *bkt, *cur_bkt; int ret; uint16_t short_sig; short_sig = get_short_sig(sig); /* 获取 short sig */ prim_bucket_idx = get_prim_bucket_index(h, sig); sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); bkt = &h->buckets[prim_bucket_idx]; /* 得到主bucket */ __hash_rw_reader_lock(h); /* 在主bucket中查找 */ ret = search_one_bucket_l(h, key, short_sig, data, bkt); if (ret != -1) { /* 在主bucket中找到,直接返回 */ __hash_rw_reader_unlock(h); return ret; } bkt = &h->buckets[sec_bucket_idx]; /* 在次bucket及其每个扩展bucket中查找 */ FOR_EACH_BUCKET(cur_bkt, bkt) { ret = search_one_bucket_l(h, key, short_sig, data, cur_bkt); if (ret != -1) { /* 在次bucket或与其关联的扩展bucket中找到,直接返回 */ __hash_rw_reader_unlock(h); return ret; } } __hash_rw_reader_unlock(h); return -ENOENT; } |
————————————————————
原创文章,转载请注明: 转载自孙希栋的博客