1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2019 Mellanox Technologies, Ltd
5 #include <rte_malloc.h>
6 #include <rte_hash_crc.h>
9 #include <mlx5_malloc.h>
11 #include "mlx5_common_utils.h"
12 #include "mlx5_common_log.h"
14 /********************* mlx5 list ************************/
17 mlx5_list_create(const char *name, void *ctx,
18 mlx5_list_create_cb cb_create,
19 mlx5_list_match_cb cb_match,
20 mlx5_list_remove_cb cb_remove,
21 mlx5_list_clone_cb cb_clone,
22 mlx5_list_clone_free_cb cb_clone_free)
24 struct mlx5_list *list;
27 if (!cb_match || !cb_create || !cb_remove || !cb_clone ||
32 list = mlx5_malloc(MLX5_MEM_ZERO, sizeof(*list), 0, SOCKET_ID_ANY);
36 snprintf(list->name, sizeof(list->name), "%s", name);
38 list->cb_create = cb_create;
39 list->cb_match = cb_match;
40 list->cb_remove = cb_remove;
41 list->cb_clone = cb_clone;
42 list->cb_clone_free = cb_clone_free;
43 rte_rwlock_init(&list->lock);
44 DRV_LOG(DEBUG, "mlx5 list %s initialized.", list->name);
45 for (i = 0; i <= RTE_MAX_LCORE; i++)
46 LIST_INIT(&list->cache[i].h);
50 static struct mlx5_list_entry *
51 __list_lookup(struct mlx5_list *list, int lcore_index, void *ctx, bool reuse)
53 struct mlx5_list_entry *entry = LIST_FIRST(&list->cache[lcore_index].h);
56 while (entry != NULL) {
57 if (list->cb_match(list, entry, ctx) == 0) {
59 ret = __atomic_add_fetch(&entry->ref_cnt, 1,
60 __ATOMIC_RELAXED) - 1;
61 DRV_LOG(DEBUG, "mlx5 list %s entry %p ref: %u.",
62 list->name, (void *)entry,
64 } else if (lcore_index < RTE_MAX_LCORE) {
65 ret = __atomic_load_n(&entry->ref_cnt,
68 if (likely(ret != 0 || lcore_index == RTE_MAX_LCORE))
70 if (reuse && ret == 0)
71 entry->ref_cnt--; /* Invalid entry. */
73 entry = LIST_NEXT(entry, next);
78 struct mlx5_list_entry *
79 mlx5_list_lookup(struct mlx5_list *list, void *ctx)
81 struct mlx5_list_entry *entry = NULL;
84 rte_rwlock_read_lock(&list->lock);
85 for (i = 0; i < RTE_MAX_LCORE; i++) {
86 entry = __list_lookup(list, i, ctx, false);
90 rte_rwlock_read_unlock(&list->lock);
94 static struct mlx5_list_entry *
95 mlx5_list_cache_insert(struct mlx5_list *list, int lcore_index,
96 struct mlx5_list_entry *gentry, void *ctx)
98 struct mlx5_list_entry *lentry = list->cb_clone(list, gentry, ctx);
100 if (unlikely(!lentry))
102 lentry->ref_cnt = 1u;
103 lentry->gentry = gentry;
104 lentry->lcore_idx = (uint32_t)lcore_index;
105 LIST_INSERT_HEAD(&list->cache[lcore_index].h, lentry, next);
110 __list_cache_clean(struct mlx5_list *list, int lcore_index)
112 struct mlx5_list_cache *c = &list->cache[lcore_index];
113 struct mlx5_list_entry *entry = LIST_FIRST(&c->h);
114 uint32_t inv_cnt = __atomic_exchange_n(&c->inv_cnt, 0,
117 while (inv_cnt != 0 && entry != NULL) {
118 struct mlx5_list_entry *nentry = LIST_NEXT(entry, next);
120 if (__atomic_load_n(&entry->ref_cnt, __ATOMIC_RELAXED) == 0) {
121 LIST_REMOVE(entry, next);
122 list->cb_clone_free(list, entry);
129 struct mlx5_list_entry *
130 mlx5_list_register(struct mlx5_list *list, void *ctx)
132 struct mlx5_list_entry *entry, *local_entry;
133 volatile uint32_t prev_gen_cnt = 0;
134 int lcore_index = rte_lcore_index(rte_lcore_id());
137 MLX5_ASSERT(lcore_index < RTE_MAX_LCORE);
138 if (unlikely(lcore_index == -1)) {
142 /* 0. Free entries that was invalidated by other lcores. */
143 __list_cache_clean(list, lcore_index);
144 /* 1. Lookup in local cache. */
145 local_entry = __list_lookup(list, lcore_index, ctx, true);
148 /* 2. Lookup with read lock on global list, reuse if found. */
149 rte_rwlock_read_lock(&list->lock);
150 entry = __list_lookup(list, RTE_MAX_LCORE, ctx, true);
152 rte_rwlock_read_unlock(&list->lock);
153 return mlx5_list_cache_insert(list, lcore_index, entry, ctx);
155 prev_gen_cnt = list->gen_cnt;
156 rte_rwlock_read_unlock(&list->lock);
157 /* 3. Prepare new entry for global list and for cache. */
158 entry = list->cb_create(list, entry, ctx);
159 if (unlikely(!entry))
161 local_entry = list->cb_clone(list, entry, ctx);
162 if (unlikely(!local_entry)) {
163 list->cb_remove(list, entry);
167 local_entry->ref_cnt = 1u;
168 local_entry->gentry = entry;
169 local_entry->lcore_idx = (uint32_t)lcore_index;
170 rte_rwlock_write_lock(&list->lock);
171 /* 4. Make sure the same entry was not created before the write lock. */
172 if (unlikely(prev_gen_cnt != list->gen_cnt)) {
173 struct mlx5_list_entry *oentry = __list_lookup(list,
177 if (unlikely(oentry)) {
178 /* 4.5. Found real race!!, reuse the old entry. */
179 rte_rwlock_write_unlock(&list->lock);
180 list->cb_remove(list, entry);
181 list->cb_clone_free(list, local_entry);
182 return mlx5_list_cache_insert(list, lcore_index, oentry,
186 /* 5. Update lists. */
187 LIST_INSERT_HEAD(&list->cache[RTE_MAX_LCORE].h, entry, next);
189 rte_rwlock_write_unlock(&list->lock);
190 LIST_INSERT_HEAD(&list->cache[lcore_index].h, local_entry, next);
191 __atomic_add_fetch(&list->count, 1, __ATOMIC_RELAXED);
192 DRV_LOG(DEBUG, "mlx5 list %s entry %p new: %u.", list->name,
193 (void *)entry, entry->ref_cnt);
198 mlx5_list_unregister(struct mlx5_list *list,
199 struct mlx5_list_entry *entry)
201 struct mlx5_list_entry *gentry = entry->gentry;
204 if (__atomic_sub_fetch(&entry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
206 lcore_idx = rte_lcore_index(rte_lcore_id());
207 MLX5_ASSERT(lcore_idx < RTE_MAX_LCORE);
208 if (entry->lcore_idx == (uint32_t)lcore_idx) {
209 LIST_REMOVE(entry, next);
210 list->cb_clone_free(list, entry);
211 } else if (likely(lcore_idx != -1)) {
212 __atomic_add_fetch(&list->cache[entry->lcore_idx].inv_cnt, 1,
217 if (__atomic_sub_fetch(&gentry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
219 rte_rwlock_write_lock(&list->lock);
220 if (likely(gentry->ref_cnt == 0)) {
221 LIST_REMOVE(gentry, next);
222 rte_rwlock_write_unlock(&list->lock);
223 list->cb_remove(list, gentry);
224 __atomic_sub_fetch(&list->count, 1, __ATOMIC_RELAXED);
225 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.",
226 list->name, (void *)gentry);
229 rte_rwlock_write_unlock(&list->lock);
234 mlx5_list_destroy(struct mlx5_list *list)
236 struct mlx5_list_entry *entry;
240 for (i = 0; i <= RTE_MAX_LCORE; i++) {
241 while (!LIST_EMPTY(&list->cache[i].h)) {
242 entry = LIST_FIRST(&list->cache[i].h);
243 LIST_REMOVE(entry, next);
244 if (i == RTE_MAX_LCORE) {
245 list->cb_remove(list, entry);
246 DRV_LOG(DEBUG, "mlx5 list %s entry %p "
247 "destroyed.", list->name,
250 list->cb_clone_free(list, entry);
258 mlx5_list_get_entry_num(struct mlx5_list *list)
261 return __atomic_load_n(&list->count, __ATOMIC_RELAXED);
264 /********************* Hash List **********************/
266 static struct mlx5_hlist_entry *
267 mlx5_hlist_default_create_cb(struct mlx5_hlist *h, uint64_t key __rte_unused,
268 void *ctx __rte_unused)
270 return mlx5_malloc(MLX5_MEM_ZERO, h->entry_sz, 0, SOCKET_ID_ANY);
274 mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused,
275 struct mlx5_hlist_entry *entry)
281 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
282 uint32_t flags, mlx5_hlist_create_cb cb_create,
283 mlx5_hlist_match_cb cb_match, mlx5_hlist_remove_cb cb_remove)
285 struct mlx5_hlist *h;
290 if (!size || !cb_match || (!cb_create ^ !cb_remove))
292 /* Align to the next power of 2, 32bits integer is enough now. */
293 if (!rte_is_power_of_2(size)) {
294 act_size = rte_align32pow2(size);
295 DRV_LOG(DEBUG, "Size 0x%" PRIX32 " is not power of 2, "
296 "will be aligned to 0x%" PRIX32 ".", size, act_size);
300 alloc_size = sizeof(struct mlx5_hlist) +
301 sizeof(struct mlx5_hlist_bucket) * act_size;
302 /* Using zmalloc, then no need to initialize the heads. */
303 h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
306 DRV_LOG(ERR, "No memory for hash list %s creation",
307 name ? name : "None");
311 snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name);
312 h->table_sz = act_size;
313 h->mask = act_size - 1;
314 h->entry_sz = entry_size;
315 h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY);
316 h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST);
317 h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
318 h->cb_match = cb_match;
319 h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
320 for (i = 0; i < act_size; i++)
321 rte_rwlock_init(&h->buckets[i].lock);
322 DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
327 static struct mlx5_hlist_entry *
328 __hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
329 void *ctx, bool reuse)
331 struct mlx5_hlist_head *first;
332 struct mlx5_hlist_entry *node;
335 first = &h->buckets[idx].head;
336 LIST_FOREACH(node, first, next) {
337 if (!h->cb_match(h, node, key, ctx)) {
339 __atomic_add_fetch(&node->ref_cnt, 1,
341 DRV_LOG(DEBUG, "Hash list %s entry %p "
343 h->name, (void *)node, node->ref_cnt);
351 static struct mlx5_hlist_entry *
352 hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
353 void *ctx, bool reuse)
355 struct mlx5_hlist_entry *node;
358 rte_rwlock_read_lock(&h->buckets[idx].lock);
359 node = __hlist_lookup(h, key, idx, ctx, reuse);
360 rte_rwlock_read_unlock(&h->buckets[idx].lock);
364 struct mlx5_hlist_entry *
365 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
370 idx = (uint32_t)(key & h->mask);
372 idx = rte_hash_crc_8byte(key, 0) & h->mask;
373 return hlist_lookup(h, key, idx, ctx, false);
376 struct mlx5_hlist_entry*
377 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
380 struct mlx5_hlist_head *first;
381 struct mlx5_hlist_bucket *b;
382 struct mlx5_hlist_entry *entry;
383 uint32_t prev_gen_cnt = 0;
386 idx = (uint32_t)(key & h->mask);
388 idx = rte_hash_crc_8byte(key, 0) & h->mask;
390 b = &h->buckets[idx];
391 /* Use write lock directly for write-most list. */
392 if (!h->write_most) {
393 prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE);
394 entry = hlist_lookup(h, key, idx, ctx, true);
398 rte_rwlock_write_lock(&b->lock);
399 /* Check if the list changed by other threads. */
401 prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
402 entry = __hlist_lookup(h, key, idx, ctx, true);
407 entry = h->cb_create(h, key, ctx);
410 DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
415 LIST_INSERT_HEAD(first, entry, next);
416 __atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
417 DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.",
418 h->name, (void *)entry, entry->ref_cnt);
420 rte_rwlock_write_unlock(&b->lock);
425 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
427 uint32_t idx = entry->idx;
429 rte_rwlock_write_lock(&h->buckets[idx].lock);
430 MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
431 DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.",
432 h->name, (void *)entry, entry->ref_cnt);
433 if (--entry->ref_cnt) {
434 rte_rwlock_write_unlock(&h->buckets[idx].lock);
437 LIST_REMOVE(entry, next);
438 /* Set to NULL to get rid of removing action for more than once. */
439 entry->next.le_prev = NULL;
440 h->cb_remove(h, entry);
441 rte_rwlock_write_unlock(&h->buckets[idx].lock);
442 DRV_LOG(DEBUG, "Hash list %s entry %p removed.",
443 h->name, (void *)entry);
448 mlx5_hlist_destroy(struct mlx5_hlist *h)
451 struct mlx5_hlist_entry *entry;
454 for (idx = 0; idx < h->table_sz; ++idx) {
455 /* No LIST_FOREACH_SAFE, using while instead. */
456 while (!LIST_EMPTY(&h->buckets[idx].head)) {
457 entry = LIST_FIRST(&h->buckets[idx].head);
458 LIST_REMOVE(entry, next);
460 * The owner of whole element which contains data entry
461 * is the user, so it's the user's duty to do the clean
462 * up and the free work because someone may not put the
463 * hlist entry at the beginning(suggested to locate at
464 * the beginning). Or else the default free function
467 h->cb_remove(h, entry);