DPDK20.05 hash表3 – rte_hash_del_key
该函数用来删除hash表中的指定key。
1、rte_hash_del_key
1 2 3 4 5 | int32_t rte_hash_del_key(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); } |
rte_hash_hash() 函数用来根据 key 的值计算hash值，得到的值在DPDK中被称为 signature。在示例l3fwd中使用了自定义的函数ipv4_hash_crc()和ipv6_hash_crc()。
2、__rte_hash_del_key_with_hash
将指定key从hash表中删除。
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | static inline int32_t __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig) { uint32_t prim_bucket_idx, sec_bucket_idx; struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt; struct rte_hash_bucket *cur_bkt; int pos; int32_t ret, i; uint16_t short_sig; short_sig = get_short_sig(sig); /* 根据hash值得到 short sig */ /* 根据hash值得到主bucket中的索引 */ prim_bucket_idx = get_prim_bucket_index(h, sig); /* 根据short sig 得到次级bucket上的索引 */ sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig); prim_bkt = &h->buckets[prim_bucket_idx]; /* 得到主bucket */ __hash_rw_writer_lock(h); /* 从主bucket中查找并移除指定的key */ ret = search_and_remove(h, key, prim_bkt, short_sig, &pos); if (ret != -1) { /* 如果返回值不为-1，说明找到该key, pos即为该key在bucket中的位置 */ __rte_hash_compact_ll(h, prim_bkt, pos); last_bkt = prim_bkt->next; /* 得到主bucket 的第一个扩展bucket */ prev_bkt = prim_bkt; goto return_bkt; } /* 在主bucket中没有找到，继续查找次级bucket，以及次级bucket连接的每个扩展bucket */ sec_bkt = &h->buckets[sec_bucket_idx]; FOR_EACH_BUCKET(cur_bkt, sec_bkt) { ret = search_and_remove(h, key, cur_bkt, short_sig, &pos); if (ret != -1) { /* 如果返回值不为-1，说明找到找到该key */ __rte_hash_compact_ll(h, cur_bkt, pos); last_bkt = sec_bkt->next; prev_bkt = sec_bkt; goto return_bkt; } } __hash_rw_writer_unlock(h); /* 在主次两级bucket中都没有找到 */ return -ENOENT; /* 查看最后一个扩展bucket看其是否为空，如果为空就回收 */ return_bkt: if (!last_bkt) { /* 如果没有扩展bucket, 直接返回 */ __hash_rw_writer_unlock(h); return ret; } while (last_bkt->next) { /* 得到最后一个扩展bucket */ prev_bkt = last_bkt; last_bkt = last_bkt->next; } /* 找到最后一个扩展bucket中的第一个非空索引 */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (last_bkt->key_idx[i] != EMPTY_SLOT) break; } /* 当前 bucket 是空的 */ if (i == RTE_HASH_BUCKET_ENTRIES) { prev_bkt->next = NULL; /* 得到该bucket在hash表中所有扩展bucket中的索引 */ uint32_t index = last_bkt - h->buckets_ext + 1; /* 如果没有设置no_free_on_del，则回收该空bucket */ if (h->no_free_on_del) /* 如果设置了no_free_on_del，则将该索引保存到hash表 * 的ext_bkt_to_free[ret] 中，在调用rte_hash_del_xxx() * 函数时就会被回收。 * 如果启用了无锁读写并发，空的扩展bucket不能直接被插入回free list里 * （因为读者可能仍在使用它）。 * 因此对扩展bucket的释放就是对key的索引的释放 */ h->ext_bkt_to_free[ret] = index; else /* 如果没有设置no_free_on_del，则直接回收该空bucket的索引到h->free_ext_bkts */ rte_ring_sp_enqueue_elem(h->free_ext_bkts, &index, sizeof(uint32_t)); } __hash_rw_writer_unlock(h); return ret; } |
3、search_and_remove() 函数
该函数查找指定的bucket，并删除匹配的key结点。该函数并不是线程安全的，调用该函数的上层函数需要加锁。
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 | static inline int32_t search_and_remove(const struct rte_hash *h, const void *key, struct rte_hash_bucket *bkt, uint16_t sig, int *pos) { struct rte_hash_key *k, *keys = h->key_store; unsigned int i; uint32_t key_idx; /* 检查 key 是否在 bucket 中 */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { key_idx = __atomic_load_n(&bkt->key_idx[i], __ATOMIC_ACQUIRE); /* 得到其在key缓存中的索引 */ /* 如果hash值相同，且该索引不为空 */ if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { /* 得到对应的 key 所在的内存 */ k = (struct rte_hash_key *) ((char *)keys + key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { /* 如果key相同 */ bkt->sig_current[i] = NULL_SIGNATURE; /* 清除 hash 值 */ /* 如果没有设置该标记，则将其插入回h->free_slots中 */ if (!h->no_free_on_del) remove_entry(h, bkt, i); __atomic_store_n(&bkt->key_idx[i], EMPTY_SLOT, __ATOMIC_RELEASE); *pos = i; /* 得到其在 bucket中的位置 */ /* 返回key保存的位置。由于第 0 个位置是留空的，所以这里要减去1 */ return key_idx - 1; } } } return -1; } |
4、remove_entry() 函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | static inline void remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) { unsigned lcore_id, n_slots; struct lcore_cache *cached_free_slots; if (h->use_local_cache) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; /* Cache full, need to free it. */ if (cached_free_slots->len == LCORE_CACHE_SIZE) { /* Need to enqueue the free slots in global ring. */ n_slots = rte_ring_mp_enqueue_burst_elem(h->free_slots, cached_free_slots->objs, sizeof(uint32_t), LCORE_CACHE_SIZE, NULL); ERR_IF_TRUE((n_slots == 0), "%s: could not enqueue free slots in global ring\n", __func__); cached_free_slots->len -= n_slots; } /* Put index of new free slot in cache. */ cached_free_slots->objs[cached_free_slots->len] = bkt->key_idx[i]; cached_free_slots->len++; } else { /* 没有使用本地cache，直接将其入队回 h->free_slots */ rte_ring_sp_enqueue_elem(h->free_slots, &bkt->key_idx[i], sizeof(uint32_t)); } } |
————————————————————
原创文章，转载请注明： 转载自孙希栋的博客
相关文章
2020年7月24日 DPDK20.05 hash表4 – rte_hash_lookup
2020年7月24日 DPDK20.05 hash表2 – rte_hash_add_key
2020年7月24日 DPDK20.05 hash表1 – rte_hash_create 与 rte_hash_free
2020年7月17日 DPDK17.02内存池管理3 – rte_pktmbuf_pool_create
2020年7月17日 DPDK17.02内存池管理2 – rte_mempool_ops
2020年7月17日 DPDK17.02内存池管理1 – rte_mempool_create_empty