Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2017 Intel Corporation
3 : : */
4 : :
5 : : #include <rte_errno.h>
6 : : #include <rte_malloc.h>
7 : : #include <rte_prefetch.h>
8 : : #include <rte_random.h>
9 : : #include <rte_log.h>
10 : : #include <rte_vect.h>
11 : : #include <rte_cpuflags.h>
12 : :
13 : : #include "member.h"
14 : : #include "rte_member.h"
15 : : #include "rte_member_ht.h"
16 : :
17 : : #if defined(RTE_ARCH_X86)
18 : : #include "rte_member_x86.h"
19 : : #endif
20 : :
21 : : /* Search bucket for entry with tmp_sig and update set_id */
22 : : static inline int
23 : : update_entry_search(uint32_t bucket_id, member_sig_t tmp_sig,
24 : : struct member_ht_bucket *buckets,
25 : : member_set_t set_id)
26 : : {
27 : : uint32_t i;
28 : :
29 [ # # # # ]: 0 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
30 [ # # # # ]: 0 : if (buckets[bucket_id].sigs[i] == tmp_sig) {
31 : 0 : buckets[bucket_id].sets[i] = set_id;
32 : : return 1;
33 : : }
34 : : }
35 : : return 0;
36 : : }
37 : :
38 : : static inline int
39 : : search_bucket_single(uint32_t bucket_id, member_sig_t tmp_sig,
40 : : struct member_ht_bucket *buckets,
41 : : member_set_t *set_id)
42 : : {
43 : : uint32_t iter;
44 : :
45 [ # # # # : 0 : for (iter = 0; iter < RTE_MEMBER_BUCKET_ENTRIES; iter++) {
# # # # ]
46 [ # # # # : 0 : if (tmp_sig == buckets[bucket_id].sigs[iter] &&
# # # # ]
47 [ # # # # : 0 : buckets[bucket_id].sets[iter] !=
# # # # ]
48 : : RTE_MEMBER_NO_MATCH) {
49 : 0 : *set_id = buckets[bucket_id].sets[iter];
50 : : return 1;
51 : : }
52 : : }
53 : : return 0;
54 : : }
55 : :
56 : : static inline void
57 : : search_bucket_multi(uint32_t bucket_id, member_sig_t tmp_sig,
58 : : struct member_ht_bucket *buckets,
59 : : uint32_t *counter,
60 : : uint32_t matches_per_key,
61 : : member_set_t *set_id)
62 : : {
63 : : uint32_t iter;
64 : :
65 [ # # # # : 0 : for (iter = 0; iter < RTE_MEMBER_BUCKET_ENTRIES; iter++) {
# # # # ]
66 [ # # # # : 0 : if (tmp_sig == buckets[bucket_id].sigs[iter] &&
# # # # ]
67 [ # # # # : 0 : buckets[bucket_id].sets[iter] !=
# # # # ]
68 : : RTE_MEMBER_NO_MATCH) {
69 : 0 : set_id[*counter] = buckets[bucket_id].sets[iter];
70 : 0 : (*counter)++;
71 [ # # # # : 0 : if (*counter >= matches_per_key)
# # # # ]
72 : : return;
73 : : }
74 : : }
75 : : }
76 : :
77 : : int
78 : 8 : rte_member_create_ht(struct rte_member_setsum *ss,
79 : : const struct rte_member_parameters *params)
80 : : {
81 : : uint32_t i, j;
82 : : uint32_t size_bucket_t;
83 [ + + ]: 8 : uint32_t num_entries = rte_align32pow2(params->num_keys);
84 : :
85 [ + + ]: 8 : if ((num_entries > RTE_MEMBER_ENTRIES_MAX) ||
86 [ + + ]: 6 : !rte_is_power_of_2(RTE_MEMBER_BUCKET_ENTRIES) ||
87 : : num_entries < RTE_MEMBER_BUCKET_ENTRIES) {
88 : 3 : rte_errno = EINVAL;
89 : 3 : MEMBER_LOG(ERR,
90 : : "Membership HT create with invalid parameters");
91 : 3 : return -EINVAL;
92 : : }
93 : :
94 : 5 : uint32_t num_buckets = num_entries / RTE_MEMBER_BUCKET_ENTRIES;
95 : :
96 : : size_bucket_t = sizeof(struct member_ht_bucket);
97 : :
98 : 5 : struct member_ht_bucket *buckets = rte_zmalloc_socket(NULL,
99 : 5 : num_buckets * size_bucket_t,
100 : 5 : RTE_CACHE_LINE_SIZE, ss->socket_id);
101 : :
102 [ - + ]: 5 : if (buckets == NULL) {
103 : 0 : MEMBER_LOG(ERR, "memory allocation failed for HT "
104 : : "setsummary");
105 : 0 : return -ENOMEM;
106 : : }
107 : :
108 : 5 : ss->table = buckets;
109 : 5 : ss->bucket_cnt = num_buckets;
110 : 5 : ss->bucket_mask = num_buckets - 1;
111 : 5 : ss->cache = params->is_cache;
112 : :
113 [ + + ]: 20485 : for (i = 0; i < num_buckets; i++) {
114 [ + + ]: 348160 : for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++)
115 : 327680 : buckets[i].sets[j] = RTE_MEMBER_NO_MATCH;
116 : : }
117 : : #if defined(RTE_ARCH_X86)
118 [ + - ]: 5 : if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2) &&
119 [ + - ]: 5 : RTE_MEMBER_BUCKET_ENTRIES == 16 &&
120 : 5 : rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_256)
121 : 5 : ss->sig_cmp_fn = RTE_MEMBER_COMPARE_AVX2;
122 : : else
123 : : #endif
124 : 0 : ss->sig_cmp_fn = RTE_MEMBER_COMPARE_SCALAR;
125 : :
126 : 5 : MEMBER_LOG(DEBUG, "Hash table based filter created, "
127 : : "the table has %u entries, %u buckets",
128 : : num_entries, num_buckets);
129 : 5 : return 0;
130 : : }
131 : :
132 : : static inline void
133 : 307297 : get_buckets_index(const struct rte_member_setsum *ss, const void *key,
134 : : uint32_t *prim_bkt, uint32_t *sec_bkt, member_sig_t *sig)
135 : : {
136 : 614594 : uint32_t first_hash = MEMBER_HASH_FUNC(key, ss->key_len,
137 : 307297 : ss->prim_hash_seed);
138 : 307297 : uint32_t sec_hash = MEMBER_HASH_FUNC(&first_hash, sizeof(uint32_t),
139 : 307297 : ss->sec_hash_seed);
140 : : /*
141 : : * We use the first hash value for the signature, and the second hash
142 : : * value to derive the primary and secondary bucket locations.
143 : : *
144 : : * For non-cache mode, we use the lower bits for the primary bucket
145 : : * location. Then we xor primary bucket location and the signature
146 : : * to get the secondary bucket location. This is called "partial-key
147 : : * cuckoo hashing" proposed by B. Fan, et al's paper
148 : : * "Cuckoo Filter: Practically Better Than Bloom". The benefit to use
149 : : * xor is that one could derive the alternative bucket location
150 : : * by only using the current bucket location and the signature. This is
151 : : * generally required by non-cache mode's eviction and deletion
152 : : * process without the need to store alternative hash value nor the full
153 : : * key.
154 : : *
155 : : * For cache mode, we use the lower bits for the primary bucket
156 : : * location and the higher bits for the secondary bucket location. In
157 : : * cache mode, keys are simply overwritten if bucket is full. We do not
158 : : * use xor since lower/higher bits are more independent hash values thus
159 : : * should provide slightly better table load.
160 : : */
161 : 307297 : *sig = first_hash;
162 [ + + ]: 307297 : if (ss->cache) {
163 : 111401 : *prim_bkt = sec_hash & ss->bucket_mask;
164 : 111401 : *sec_bkt = (sec_hash >> 16) & ss->bucket_mask;
165 : : } else {
166 : 195896 : *prim_bkt = sec_hash & ss->bucket_mask;
167 : 195896 : *sec_bkt = (*prim_bkt ^ *sig) & ss->bucket_mask;
168 : : }
169 : 307297 : }
170 : :
171 : : int
172 : 20 : rte_member_lookup_ht(const struct rte_member_setsum *ss,
173 : : const void *key, member_set_t *set_id)
174 : : {
175 : : uint32_t prim_bucket, sec_bucket;
176 : : member_sig_t tmp_sig;
177 : 20 : struct member_ht_bucket *buckets = ss->table;
178 : :
179 : 20 : *set_id = RTE_MEMBER_NO_MATCH;
180 : 20 : get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
181 : :
182 [ + - ]: 20 : switch (ss->sig_cmp_fn) {
183 : : #if defined(RTE_ARCH_X86) && defined(__AVX2__)
184 : 20 : case RTE_MEMBER_COMPARE_AVX2:
185 : 20 : if (search_bucket_single_avx(prim_bucket, tmp_sig, buckets,
186 : : set_id) ||
187 : 10 : search_bucket_single_avx(sec_bucket, tmp_sig,
188 : : buckets, set_id))
189 : 10 : return 1;
190 : : break;
191 : : #endif
192 : 0 : default:
193 : 0 : if (search_bucket_single(prim_bucket, tmp_sig, buckets,
194 : : set_id) ||
195 : 0 : search_bucket_single(sec_bucket, tmp_sig,
196 : : buckets, set_id))
197 : 0 : return 1;
198 : : }
199 : :
200 : : return 0;
201 : : }
202 : :
203 : : uint32_t
204 : 4 : rte_member_lookup_bulk_ht(const struct rte_member_setsum *ss,
205 : : const void **keys, uint32_t num_keys, member_set_t *set_id)
206 : : {
207 : : uint32_t i;
208 : : uint32_t num_matches = 0;
209 : 4 : struct member_ht_bucket *buckets = ss->table;
210 : : member_sig_t tmp_sig[RTE_MEMBER_LOOKUP_BULK_MAX];
211 : : uint32_t prim_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
212 : : uint32_t sec_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
213 : :
214 [ + + ]: 24 : for (i = 0; i < num_keys; i++) {
215 : 20 : get_buckets_index(ss, keys[i], &prim_buckets[i],
216 : : &sec_buckets[i], &tmp_sig[i]);
217 : 20 : rte_prefetch0(&buckets[prim_buckets[i]]);
218 : 20 : rte_prefetch0(&buckets[sec_buckets[i]]);
219 : : }
220 : :
221 [ + + ]: 24 : for (i = 0; i < num_keys; i++) {
222 [ + - ]: 20 : switch (ss->sig_cmp_fn) {
223 : : #if defined(RTE_ARCH_X86) && defined(__AVX2__)
224 : 20 : case RTE_MEMBER_COMPARE_AVX2:
225 : 20 : if (search_bucket_single_avx(prim_buckets[i],
226 : 20 : tmp_sig[i], buckets, &set_id[i]) ||
227 : 4 : search_bucket_single_avx(sec_buckets[i],
228 : : tmp_sig[i], buckets, &set_id[i]))
229 : 16 : num_matches++;
230 : : else
231 : 4 : set_id[i] = RTE_MEMBER_NO_MATCH;
232 : : break;
233 : : #endif
234 : 0 : default:
235 : 0 : if (search_bucket_single(prim_buckets[i], tmp_sig[i],
236 : 0 : buckets, &set_id[i]) ||
237 : 0 : search_bucket_single(sec_buckets[i],
238 : : tmp_sig[i], buckets, &set_id[i]))
239 : 0 : num_matches++;
240 : : else
241 : 0 : set_id[i] = RTE_MEMBER_NO_MATCH;
242 : : }
243 : : }
244 : 4 : return num_matches;
245 : : }
246 : :
247 : : uint32_t
248 : 10 : rte_member_lookup_multi_ht(const struct rte_member_setsum *ss,
249 : : const void *key, uint32_t match_per_key,
250 : : member_set_t *set_id)
251 : : {
252 : 10 : uint32_t num_matches = 0;
253 : : uint32_t prim_bucket, sec_bucket;
254 : : member_sig_t tmp_sig;
255 : 10 : struct member_ht_bucket *buckets = ss->table;
256 : :
257 : 10 : get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
258 : :
259 [ + - ]: 10 : switch (ss->sig_cmp_fn) {
260 : : #if defined(RTE_ARCH_X86) && defined(__AVX2__)
261 : 10 : case RTE_MEMBER_COMPARE_AVX2:
262 : 10 : search_bucket_multi_avx(prim_bucket, tmp_sig, buckets,
263 : : &num_matches, match_per_key, set_id);
264 [ + - ]: 10 : if (num_matches < match_per_key)
265 : 10 : search_bucket_multi_avx(sec_bucket, tmp_sig,
266 : : buckets, &num_matches, match_per_key, set_id);
267 : 10 : return num_matches;
268 : : #endif
269 : 0 : default:
270 : 0 : search_bucket_multi(prim_bucket, tmp_sig, buckets, &num_matches,
271 : : match_per_key, set_id);
272 [ # # ]: 0 : if (num_matches < match_per_key)
273 : 0 : search_bucket_multi(sec_bucket, tmp_sig,
274 : : buckets, &num_matches, match_per_key, set_id);
275 : 0 : return num_matches;
276 : : }
277 : : }
278 : :
279 : : uint32_t
280 : 2 : rte_member_lookup_multi_bulk_ht(const struct rte_member_setsum *ss,
281 : : const void **keys, uint32_t num_keys, uint32_t match_per_key,
282 : : uint32_t *match_count,
283 : : member_set_t *set_ids)
284 : : {
285 : : uint32_t i;
286 : : uint32_t num_matches = 0;
287 : 2 : struct member_ht_bucket *buckets = ss->table;
288 : : uint32_t match_cnt_tmp;
289 : : member_sig_t tmp_sig[RTE_MEMBER_LOOKUP_BULK_MAX];
290 : : uint32_t prim_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
291 : : uint32_t sec_buckets[RTE_MEMBER_LOOKUP_BULK_MAX];
292 : :
293 [ + + ]: 12 : for (i = 0; i < num_keys; i++) {
294 : 10 : get_buckets_index(ss, keys[i], &prim_buckets[i],
295 : : &sec_buckets[i], &tmp_sig[i]);
296 : 10 : rte_prefetch0(&buckets[prim_buckets[i]]);
297 : 10 : rte_prefetch0(&buckets[sec_buckets[i]]);
298 : : }
299 [ + + ]: 12 : for (i = 0; i < num_keys; i++) {
300 : 10 : match_cnt_tmp = 0;
301 : :
302 [ + - ]: 10 : switch (ss->sig_cmp_fn) {
303 : : #if defined(RTE_ARCH_X86) && defined(__AVX2__)
304 : 10 : case RTE_MEMBER_COMPARE_AVX2:
305 : 10 : search_bucket_multi_avx(prim_buckets[i], tmp_sig[i],
306 : : buckets, &match_cnt_tmp, match_per_key,
307 : 10 : &set_ids[i*match_per_key]);
308 [ + - ]: 10 : if (match_cnt_tmp < match_per_key)
309 : 10 : search_bucket_multi_avx(sec_buckets[i],
310 : 10 : tmp_sig[i], buckets, &match_cnt_tmp,
311 : : match_per_key,
312 : : &set_ids[i*match_per_key]);
313 : 10 : match_count[i] = match_cnt_tmp;
314 [ + - ]: 10 : if (match_cnt_tmp != 0)
315 : 10 : num_matches++;
316 : : break;
317 : : #endif
318 : 0 : default:
319 : 0 : search_bucket_multi(prim_buckets[i], tmp_sig[i],
320 : : buckets, &match_cnt_tmp, match_per_key,
321 : 0 : &set_ids[i*match_per_key]);
322 [ # # ]: 0 : if (match_cnt_tmp < match_per_key)
323 : 0 : search_bucket_multi(sec_buckets[i], tmp_sig[i],
324 : : buckets, &match_cnt_tmp, match_per_key,
325 : : &set_ids[i*match_per_key]);
326 : 0 : match_count[i] = match_cnt_tmp;
327 [ # # ]: 0 : if (match_cnt_tmp != 0)
328 : 0 : num_matches++;
329 : : }
330 : : }
331 : 2 : return num_matches;
332 : : }
333 : :
334 : : static inline int
335 : 232970 : try_insert(struct member_ht_bucket *buckets, uint32_t prim, uint32_t sec,
336 : : member_sig_t sig, member_set_t set_id)
337 : : {
338 : : int i;
339 : : /* If not full then insert into one slot */
340 [ + + ]: 1965496 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
341 [ + + ]: 1938224 : if (buckets[prim].sets[i] == RTE_MEMBER_NO_MATCH) {
342 : 205698 : buckets[prim].sigs[i] = sig;
343 : 205698 : buckets[prim].sets[i] = set_id;
344 : 205698 : return 0;
345 : : }
346 : : }
347 : : /* If prim failed, we need to access second bucket */
348 [ + + ]: 408556 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
349 [ + + ]: 394096 : if (buckets[sec].sets[i] == RTE_MEMBER_NO_MATCH) {
350 : 12812 : buckets[sec].sigs[i] = sig;
351 : 12812 : buckets[sec].sets[i] = set_id;
352 : 12812 : return 0;
353 : : }
354 : : }
355 : : return -1;
356 : : }
357 : :
358 : : static inline int
359 : 111366 : try_update(struct member_ht_bucket *buckets, uint32_t prim, uint32_t sec,
360 : : member_sig_t sig, member_set_t set_id,
361 : : enum rte_member_sig_compare_function cmp_fn)
362 : : {
363 [ + - ]: 111366 : switch (cmp_fn) {
364 : : #if defined(RTE_ARCH_X86) && defined(__AVX2__)
365 [ + + ]: 111366 : case RTE_MEMBER_COMPARE_AVX2:
366 : : if (update_entry_search_avx(prim, sig, buckets, set_id) ||
367 : : update_entry_search_avx(sec, sig, buckets,
368 : : set_id))
369 : 74257 : return 0;
370 : : break;
371 : : #endif
372 : : default:
373 : : if (update_entry_search(prim, sig, buckets, set_id) ||
374 : : update_entry_search(sec, sig, buckets,
375 : : set_id))
376 : 0 : return 0;
377 : : }
378 : : return -1;
379 : : }
380 : :
381 : : static inline int
382 : : evict_from_bucket(void)
383 : : {
384 : : /* For now, we randomly pick one entry to evict */
385 : 3 : return rte_rand() & (RTE_MEMBER_BUCKET_ENTRIES - 1);
386 : : }
387 : :
388 : : /*
389 : : * This function is similar to the cuckoo hash make_space function in hash
390 : : * library
391 : : */
392 : : static inline int
393 : 20109 : make_space_bucket(const struct rte_member_setsum *ss, uint32_t bkt_idx,
394 : : unsigned int *nr_pushes)
395 : : {
396 : : unsigned int i, j;
397 : : int ret;
398 : 20109 : struct member_ht_bucket *buckets = ss->table;
399 : : uint32_t next_bucket_idx;
400 : : struct member_ht_bucket *next_bkt[RTE_MEMBER_BUCKET_ENTRIES];
401 : 20109 : struct member_ht_bucket *bkt = &buckets[bkt_idx];
402 : : /* MSB is set to indicate if an entry has been already pushed */
403 : : member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);
404 : :
405 : : /*
406 : : * Push existing item (search for bucket with space in
407 : : * alternative locations) to its alternative location
408 : : */
409 [ + + ]: 164856 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
410 : : /* Search for space in alternative locations */
411 : 159201 : next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
412 : 159201 : next_bkt[i] = &buckets[next_bucket_idx];
413 [ + + ]: 2660697 : for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++) {
414 [ + + ]: 2515950 : if (next_bkt[i]->sets[j] == RTE_MEMBER_NO_MATCH)
415 : : break;
416 : : }
417 : :
418 [ + + ]: 159201 : if (j != RTE_MEMBER_BUCKET_ENTRIES)
419 : : break;
420 : : }
421 : :
422 : : /* Alternative location has spare room (end of recursive function) */
423 [ + + ]: 20109 : if (i != RTE_MEMBER_BUCKET_ENTRIES) {
424 : 14454 : next_bkt[i]->sigs[j] = bkt->sigs[i];
425 : 14454 : next_bkt[i]->sets[j] = bkt->sets[i];
426 : 14454 : return i;
427 : : }
428 : :
429 : : /* Pick entry that has not been pushed yet */
430 [ + - ]: 5664 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++)
431 [ + + ]: 5664 : if ((bkt->sets[i] & flag_mask) == 0)
432 : : break;
433 : :
434 : : /* All entries have been pushed, so entry cannot be added */
435 [ + - ]: 5655 : if (i == RTE_MEMBER_BUCKET_ENTRIES ||
436 [ + + ]: 5655 : ++(*nr_pushes) > RTE_MEMBER_MAX_PUSHES)
437 : 3 : return -ENOSPC;
438 : :
439 : 5652 : next_bucket_idx = (bkt->sigs[i] ^ bkt_idx) & ss->bucket_mask;
440 : : /* Set flag to indicate that this entry is going to be pushed */
441 : 5652 : bkt->sets[i] |= flag_mask;
442 : :
443 : : /* Need room in alternative bucket to insert the pushed entry */
444 : 5652 : ret = make_space_bucket(ss, next_bucket_idx, nr_pushes);
445 : : /*
446 : : * After recursive function.
447 : : * Clear flags and insert the pushed entry
448 : : * in its alternative location if successful,
449 : : * or return error
450 : : */
451 : 5652 : bkt->sets[i] &= ~flag_mask;
452 [ + + ]: 5652 : if (ret >= 0) {
453 : 5502 : next_bkt[i]->sigs[ret] = bkt->sigs[i];
454 : 5502 : next_bkt[i]->sets[ret] = bkt->sets[i];
455 : 5502 : return i;
456 : : } else
457 : : return ret;
458 : : }
459 : :
460 : : int
461 : 307227 : rte_member_add_ht(const struct rte_member_setsum *ss,
462 : : const void *key, member_set_t set_id)
463 : : {
464 : : int ret;
465 : 307227 : unsigned int nr_pushes = 0;
466 : : uint32_t prim_bucket, sec_bucket;
467 : : member_sig_t tmp_sig;
468 : 307227 : struct member_ht_bucket *buckets = ss->table;
469 : : member_set_t flag_mask = 1U << (sizeof(member_set_t) * 8 - 1);
470 : :
471 [ + - + - ]: 307227 : if (set_id == RTE_MEMBER_NO_MATCH || (set_id & flag_mask) != 0)
472 : : return -EINVAL;
473 : :
474 : 307227 : get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
475 : :
476 : : /*
477 : : * If it is cache based setsummary, we try overwriting (updating)
478 : : * existing entry with the same signature first. In cache mode, we allow
479 : : * false negatives and only cache the most recent keys.
480 : : *
481 : : * For non-cache mode, we do not update existing entry with the same
482 : : * signature. This is because if two keys with same signature update
483 : : * each other, false negative may happen, which is not the expected
484 : : * behavior for non-cache setsummary.
485 : : */
486 [ + + ]: 307227 : if (ss->cache) {
487 : 111366 : ret = try_update(buckets, prim_bucket, sec_bucket, tmp_sig,
488 : 111366 : set_id, ss->sig_cmp_fn);
489 [ + + ]: 111366 : if (ret != -1)
490 : : return ret;
491 : : }
492 : : /* If not full then insert into one slot */
493 : 232970 : ret = try_insert(buckets, prim_bucket, sec_bucket, tmp_sig, set_id);
494 [ + + ]: 232970 : if (ret != -1)
495 : : return ret;
496 : :
497 : : /* Random pick prim or sec for recursive displacement */
498 [ + + ]: 14460 : uint32_t select_bucket = (tmp_sig & 1U) ? prim_bucket : sec_bucket;
499 [ + + ]: 14460 : if (ss->cache) {
500 : : ret = evict_from_bucket();
501 : 3 : buckets[select_bucket].sigs[ret] = tmp_sig;
502 : 3 : buckets[select_bucket].sets[ret] = set_id;
503 : 3 : return 1;
504 : : }
505 : :
506 : 14457 : ret = make_space_bucket(ss, select_bucket, &nr_pushes);
507 [ + + ]: 14457 : if (ret >= 0) {
508 : 14454 : buckets[select_bucket].sigs[ret] = tmp_sig;
509 : 14454 : buckets[select_bucket].sets[ret] = set_id;
510 : : ret = 1;
511 : : }
512 : :
513 : : return ret;
514 : : }
515 : :
516 : : void
517 : 5 : rte_member_free_ht(struct rte_member_setsum *ss)
518 : : {
519 : 5 : rte_free(ss->table);
520 : 5 : }
521 : :
522 : : int
523 : 10 : rte_member_delete_ht(const struct rte_member_setsum *ss, const void *key,
524 : : member_set_t set_id)
525 : : {
526 : : int i;
527 : : uint32_t prim_bucket, sec_bucket;
528 : : member_sig_t tmp_sig;
529 : 10 : struct member_ht_bucket *buckets = ss->table;
530 : :
531 : 10 : get_buckets_index(ss, key, &prim_bucket, &sec_bucket, &tmp_sig);
532 : :
533 [ + - ]: 10 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
534 [ + - ]: 10 : if (tmp_sig == buckets[prim_bucket].sigs[i] &&
535 [ + - ]: 10 : set_id == buckets[prim_bucket].sets[i]) {
536 : 10 : buckets[prim_bucket].sets[i] = RTE_MEMBER_NO_MATCH;
537 : 10 : return 0;
538 : : }
539 : : }
540 : :
541 [ # # ]: 0 : for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
542 [ # # ]: 0 : if (tmp_sig == buckets[sec_bucket].sigs[i] &&
543 [ # # ]: 0 : set_id == buckets[sec_bucket].sets[i]) {
544 : 0 : buckets[sec_bucket].sets[i] = RTE_MEMBER_NO_MATCH;
545 : 0 : return 0;
546 : : }
547 : : }
548 : : return -ENOENT;
549 : : }
550 : :
551 : : void
552 : 6 : rte_member_reset_ht(const struct rte_member_setsum *ss)
553 : : {
554 : : uint32_t i, j;
555 : 6 : struct member_ht_bucket *buckets = ss->table;
556 : :
557 [ + + ]: 24582 : for (i = 0; i < ss->bucket_cnt; i++) {
558 [ + + ]: 417792 : for (j = 0; j < RTE_MEMBER_BUCKET_ENTRIES; j++)
559 : 393216 : buckets[i].sets[j] = RTE_MEMBER_NO_MATCH;
560 : : }
561 : 6 : }
|
