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, bool lcores_share,
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->lcores_share = lcores_share;
39 list->cb_create = cb_create;
40 list->cb_match = cb_match;
41 list->cb_remove = cb_remove;
42 list->cb_clone = cb_clone;
43 list->cb_clone_free = cb_clone_free;
44 rte_rwlock_init(&list->lock);
45 DRV_LOG(DEBUG, "mlx5 list %s initialized.", list->name);
46 for (i = 0; i <= RTE_MAX_LCORE; i++)
47 LIST_INIT(&list->cache[i].h);
51 static struct mlx5_list_entry *
52 __list_lookup(struct mlx5_list *list, int lcore_index, void *ctx, bool reuse)
54 struct mlx5_list_entry *entry = LIST_FIRST(&list->cache[lcore_index].h);
57 while (entry != NULL) {
58 if (list->cb_match(list, entry, ctx) == 0) {
60 ret = __atomic_add_fetch(&entry->ref_cnt, 1,
61 __ATOMIC_RELAXED) - 1;
62 DRV_LOG(DEBUG, "mlx5 list %s entry %p ref: %u.",
63 list->name, (void *)entry,
65 } else if (lcore_index < RTE_MAX_LCORE) {
66 ret = __atomic_load_n(&entry->ref_cnt,
69 if (likely(ret != 0 || lcore_index == RTE_MAX_LCORE))
71 if (reuse && ret == 0)
72 entry->ref_cnt--; /* Invalid entry. */
74 entry = LIST_NEXT(entry, next);
79 struct mlx5_list_entry *
80 mlx5_list_lookup(struct mlx5_list *list, void *ctx)
82 struct mlx5_list_entry *entry = NULL;
85 rte_rwlock_read_lock(&list->lock);
86 for (i = 0; i < RTE_MAX_LCORE; i++) {
87 entry = __list_lookup(list, i, ctx, false);
91 rte_rwlock_read_unlock(&list->lock);
95 static struct mlx5_list_entry *
96 mlx5_list_cache_insert(struct mlx5_list *list, int lcore_index,
97 struct mlx5_list_entry *gentry, void *ctx)
99 struct mlx5_list_entry *lentry = list->cb_clone(list, gentry, ctx);
101 if (unlikely(!lentry))
103 lentry->ref_cnt = 1u;
104 lentry->gentry = gentry;
105 lentry->lcore_idx = (uint32_t)lcore_index;
106 LIST_INSERT_HEAD(&list->cache[lcore_index].h, lentry, next);
111 __list_cache_clean(struct mlx5_list *list, int lcore_index)
113 struct mlx5_list_cache *c = &list->cache[lcore_index];
114 struct mlx5_list_entry *entry = LIST_FIRST(&c->h);
115 uint32_t inv_cnt = __atomic_exchange_n(&c->inv_cnt, 0,
118 while (inv_cnt != 0 && entry != NULL) {
119 struct mlx5_list_entry *nentry = LIST_NEXT(entry, next);
121 if (__atomic_load_n(&entry->ref_cnt, __ATOMIC_RELAXED) == 0) {
122 LIST_REMOVE(entry, next);
123 if (list->lcores_share)
124 list->cb_clone_free(list, entry);
126 list->cb_remove(list, entry);
133 struct mlx5_list_entry *
134 mlx5_list_register(struct mlx5_list *list, void *ctx)
136 struct mlx5_list_entry *entry = NULL, *local_entry;
137 volatile uint32_t prev_gen_cnt = 0;
138 int lcore_index = rte_lcore_index(rte_lcore_id());
141 MLX5_ASSERT(lcore_index < RTE_MAX_LCORE);
142 if (unlikely(lcore_index == -1)) {
146 /* 0. Free entries that was invalidated by other lcores. */
147 __list_cache_clean(list, lcore_index);
148 /* 1. Lookup in local cache. */
149 local_entry = __list_lookup(list, lcore_index, ctx, true);
152 if (list->lcores_share) {
153 /* 2. Lookup with read lock on global list, reuse if found. */
154 rte_rwlock_read_lock(&list->lock);
155 entry = __list_lookup(list, RTE_MAX_LCORE, ctx, true);
157 rte_rwlock_read_unlock(&list->lock);
158 return mlx5_list_cache_insert(list, lcore_index, entry,
161 prev_gen_cnt = list->gen_cnt;
162 rte_rwlock_read_unlock(&list->lock);
164 /* 3. Prepare new entry for global list and for cache. */
165 entry = list->cb_create(list, entry, ctx);
166 if (unlikely(!entry))
169 if (!list->lcores_share) {
170 entry->lcore_idx = (uint32_t)lcore_index;
171 LIST_INSERT_HEAD(&list->cache[lcore_index].h, entry, next);
172 __atomic_add_fetch(&list->count, 1, __ATOMIC_RELAXED);
173 DRV_LOG(DEBUG, "MLX5 list %s c%d entry %p new: %u.",
174 list->name, lcore_index, (void *)entry, entry->ref_cnt);
177 local_entry = list->cb_clone(list, entry, ctx);
178 if (unlikely(!local_entry)) {
179 list->cb_remove(list, entry);
182 local_entry->ref_cnt = 1u;
183 local_entry->gentry = entry;
184 local_entry->lcore_idx = (uint32_t)lcore_index;
185 rte_rwlock_write_lock(&list->lock);
186 /* 4. Make sure the same entry was not created before the write lock. */
187 if (unlikely(prev_gen_cnt != list->gen_cnt)) {
188 struct mlx5_list_entry *oentry = __list_lookup(list,
192 if (unlikely(oentry)) {
193 /* 4.5. Found real race!!, reuse the old entry. */
194 rte_rwlock_write_unlock(&list->lock);
195 list->cb_remove(list, entry);
196 list->cb_clone_free(list, local_entry);
197 return mlx5_list_cache_insert(list, lcore_index, oentry,
201 /* 5. Update lists. */
202 LIST_INSERT_HEAD(&list->cache[RTE_MAX_LCORE].h, entry, next);
204 rte_rwlock_write_unlock(&list->lock);
205 LIST_INSERT_HEAD(&list->cache[lcore_index].h, local_entry, next);
206 __atomic_add_fetch(&list->count, 1, __ATOMIC_RELAXED);
207 DRV_LOG(DEBUG, "mlx5 list %s entry %p new: %u.", list->name,
208 (void *)entry, entry->ref_cnt);
213 mlx5_list_unregister(struct mlx5_list *list,
214 struct mlx5_list_entry *entry)
216 struct mlx5_list_entry *gentry = entry->gentry;
219 if (__atomic_sub_fetch(&entry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
221 lcore_idx = rte_lcore_index(rte_lcore_id());
222 MLX5_ASSERT(lcore_idx < RTE_MAX_LCORE);
223 if (entry->lcore_idx == (uint32_t)lcore_idx) {
224 LIST_REMOVE(entry, next);
225 if (list->lcores_share)
226 list->cb_clone_free(list, entry);
228 list->cb_remove(list, entry);
229 } else if (likely(lcore_idx != -1)) {
230 __atomic_add_fetch(&list->cache[entry->lcore_idx].inv_cnt, 1,
235 if (!list->lcores_share) {
236 __atomic_sub_fetch(&list->count, 1, __ATOMIC_RELAXED);
237 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.",
238 list->name, (void *)entry);
241 if (__atomic_sub_fetch(&gentry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
243 rte_rwlock_write_lock(&list->lock);
244 if (likely(gentry->ref_cnt == 0)) {
245 LIST_REMOVE(gentry, next);
246 rte_rwlock_write_unlock(&list->lock);
247 list->cb_remove(list, gentry);
248 __atomic_sub_fetch(&list->count, 1, __ATOMIC_RELAXED);
249 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.",
250 list->name, (void *)gentry);
253 rte_rwlock_write_unlock(&list->lock);
258 mlx5_list_destroy(struct mlx5_list *list)
260 struct mlx5_list_entry *entry;
264 for (i = 0; i <= RTE_MAX_LCORE; i++) {
265 while (!LIST_EMPTY(&list->cache[i].h)) {
266 entry = LIST_FIRST(&list->cache[i].h);
267 LIST_REMOVE(entry, next);
268 if (i == RTE_MAX_LCORE) {
269 list->cb_remove(list, entry);
270 DRV_LOG(DEBUG, "mlx5 list %s entry %p "
271 "destroyed.", list->name,
274 list->cb_clone_free(list, entry);
282 mlx5_list_get_entry_num(struct mlx5_list *list)
285 return __atomic_load_n(&list->count, __ATOMIC_RELAXED);
288 /********************* Hash List **********************/
290 static struct mlx5_hlist_entry *
291 mlx5_hlist_default_create_cb(struct mlx5_hlist *h, uint64_t key __rte_unused,
292 void *ctx __rte_unused)
294 return mlx5_malloc(MLX5_MEM_ZERO, h->entry_sz, 0, SOCKET_ID_ANY);
298 mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused,
299 struct mlx5_hlist_entry *entry)
305 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
306 uint32_t flags, mlx5_hlist_create_cb cb_create,
307 mlx5_hlist_match_cb cb_match, mlx5_hlist_remove_cb cb_remove)
309 struct mlx5_hlist *h;
314 if (!size || !cb_match || (!cb_create ^ !cb_remove))
316 /* Align to the next power of 2, 32bits integer is enough now. */
317 if (!rte_is_power_of_2(size)) {
318 act_size = rte_align32pow2(size);
319 DRV_LOG(DEBUG, "Size 0x%" PRIX32 " is not power of 2, "
320 "will be aligned to 0x%" PRIX32 ".", size, act_size);
324 alloc_size = sizeof(struct mlx5_hlist) +
325 sizeof(struct mlx5_hlist_bucket) * act_size;
326 /* Using zmalloc, then no need to initialize the heads. */
327 h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
330 DRV_LOG(ERR, "No memory for hash list %s creation",
331 name ? name : "None");
335 snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name);
336 h->table_sz = act_size;
337 h->mask = act_size - 1;
338 h->entry_sz = entry_size;
339 h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY);
340 h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST);
341 h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
342 h->cb_match = cb_match;
343 h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
344 for (i = 0; i < act_size; i++)
345 rte_rwlock_init(&h->buckets[i].lock);
346 DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
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_head *first;
356 struct mlx5_hlist_entry *node;
359 first = &h->buckets[idx].head;
360 LIST_FOREACH(node, first, next) {
361 if (!h->cb_match(h, node, key, ctx)) {
363 __atomic_add_fetch(&node->ref_cnt, 1,
365 DRV_LOG(DEBUG, "Hash list %s entry %p "
367 h->name, (void *)node, node->ref_cnt);
375 static struct mlx5_hlist_entry *
376 hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
377 void *ctx, bool reuse)
379 struct mlx5_hlist_entry *node;
382 rte_rwlock_read_lock(&h->buckets[idx].lock);
383 node = __hlist_lookup(h, key, idx, ctx, reuse);
384 rte_rwlock_read_unlock(&h->buckets[idx].lock);
388 struct mlx5_hlist_entry *
389 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
394 idx = (uint32_t)(key & h->mask);
396 idx = rte_hash_crc_8byte(key, 0) & h->mask;
397 return hlist_lookup(h, key, idx, ctx, false);
400 struct mlx5_hlist_entry*
401 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
404 struct mlx5_hlist_head *first;
405 struct mlx5_hlist_bucket *b;
406 struct mlx5_hlist_entry *entry;
407 uint32_t prev_gen_cnt = 0;
410 idx = (uint32_t)(key & h->mask);
412 idx = rte_hash_crc_8byte(key, 0) & h->mask;
414 b = &h->buckets[idx];
415 /* Use write lock directly for write-most list. */
416 if (!h->write_most) {
417 prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE);
418 entry = hlist_lookup(h, key, idx, ctx, true);
422 rte_rwlock_write_lock(&b->lock);
423 /* Check if the list changed by other threads. */
425 prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
426 entry = __hlist_lookup(h, key, idx, ctx, true);
431 entry = h->cb_create(h, key, ctx);
434 DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
439 LIST_INSERT_HEAD(first, entry, next);
440 __atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
441 DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.",
442 h->name, (void *)entry, entry->ref_cnt);
444 rte_rwlock_write_unlock(&b->lock);
449 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
451 uint32_t idx = entry->idx;
453 rte_rwlock_write_lock(&h->buckets[idx].lock);
454 MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
455 DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.",
456 h->name, (void *)entry, entry->ref_cnt);
457 if (--entry->ref_cnt) {
458 rte_rwlock_write_unlock(&h->buckets[idx].lock);
461 LIST_REMOVE(entry, next);
462 /* Set to NULL to get rid of removing action for more than once. */
463 entry->next.le_prev = NULL;
464 h->cb_remove(h, entry);
465 rte_rwlock_write_unlock(&h->buckets[idx].lock);
466 DRV_LOG(DEBUG, "Hash list %s entry %p removed.",
467 h->name, (void *)entry);
472 mlx5_hlist_destroy(struct mlx5_hlist *h)
475 struct mlx5_hlist_entry *entry;
478 for (idx = 0; idx < h->table_sz; ++idx) {
479 /* No LIST_FOREACH_SAFE, using while instead. */
480 while (!LIST_EMPTY(&h->buckets[idx].head)) {
481 entry = LIST_FIRST(&h->buckets[idx].head);
482 LIST_REMOVE(entry, next);
484 * The owner of whole element which contains data entry
485 * is the user, so it's the user's duty to do the clean
486 * up and the free work because someone may not put the
487 * hlist entry at the beginning(suggested to locate at
488 * the beginning). Or else the default free function
491 h->cb_remove(h, entry);