1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2019 Mellanox Technologies, Ltd
5 #include <rte_malloc.h>
6 #include <rte_hash_crc.h>
8 #include <mlx5_malloc.h>
10 #include "mlx5_utils.h"
13 mlx5_hlist_create(const char *name, uint32_t size)
21 /* Align to the next power of 2, 32bits integer is enough now. */
22 if (!rte_is_power_of_2(size)) {
23 act_size = rte_align32pow2(size);
24 DRV_LOG(WARNING, "Size 0x%" PRIX32 " is not power of 2, will "
25 "be aligned to 0x%" PRIX32 ".", size, act_size);
29 alloc_size = sizeof(struct mlx5_hlist) +
30 sizeof(struct mlx5_hlist_head) * act_size;
31 /* Using zmalloc, then no need to initialize the heads. */
32 h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
35 DRV_LOG(ERR, "No memory for hash list %s creation",
36 name ? name : "None");
40 snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name);
41 h->table_sz = act_size;
42 h->mask = act_size - 1;
43 DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
48 struct mlx5_hlist_entry *
49 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key)
52 struct mlx5_hlist_head *first;
53 struct mlx5_hlist_entry *node;
56 idx = rte_hash_crc_8byte(key, 0) & h->mask;
57 first = &h->heads[idx];
58 LIST_FOREACH(node, first, next) {
66 mlx5_hlist_insert(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
69 struct mlx5_hlist_head *first;
70 struct mlx5_hlist_entry *node;
72 MLX5_ASSERT(h && entry);
73 idx = rte_hash_crc_8byte(entry->key, 0) & h->mask;
74 first = &h->heads[idx];
75 /* No need to reuse the lookup function. */
76 LIST_FOREACH(node, first, next) {
77 if (node->key == entry->key)
80 LIST_INSERT_HEAD(first, entry, next);
85 mlx5_hlist_remove(struct mlx5_hlist *h __rte_unused,
86 struct mlx5_hlist_entry *entry)
88 MLX5_ASSERT(entry && entry->next.le_prev);
89 LIST_REMOVE(entry, next);
90 /* Set to NULL to get rid of removing action for more than once. */
91 entry->next.le_prev = NULL;
95 mlx5_hlist_destroy(struct mlx5_hlist *h,
96 mlx5_hlist_destroy_callback_fn cb, void *ctx)
99 struct mlx5_hlist_entry *entry;
102 for (idx = 0; idx < h->table_sz; ++idx) {
103 /* no LIST_FOREACH_SAFE, using while instead */
104 while (!LIST_EMPTY(&h->heads[idx])) {
105 entry = LIST_FIRST(&h->heads[idx]);
106 LIST_REMOVE(entry, next);
108 * The owner of whole element which contains data entry
109 * is the user, so it's the user's duty to do the clean
110 * up and the free work because someone may not put the
111 * hlist entry at the beginning(suggested to locate at
112 * the beginning). Or else the default free function
125 mlx5_ipool_lock(struct mlx5_indexed_pool *pool)
127 if (pool->cfg.need_lock)
128 rte_spinlock_lock(&pool->lock);
132 mlx5_ipool_unlock(struct mlx5_indexed_pool *pool)
134 if (pool->cfg.need_lock)
135 rte_spinlock_unlock(&pool->lock);
138 static inline uint32_t
139 mlx5_trunk_idx_get(struct mlx5_indexed_pool *pool, uint32_t entry_idx)
141 struct mlx5_indexed_pool_config *cfg = &pool->cfg;
142 uint32_t trunk_idx = 0;
145 if (!cfg->grow_trunk)
146 return entry_idx / cfg->trunk_size;
147 if (entry_idx >= pool->grow_tbl[cfg->grow_trunk - 1]) {
148 trunk_idx = (entry_idx - pool->grow_tbl[cfg->grow_trunk - 1]) /
149 (cfg->trunk_size << (cfg->grow_shift *
150 cfg->grow_trunk)) + cfg->grow_trunk;
152 for (i = 0; i < cfg->grow_trunk; i++) {
153 if (entry_idx < pool->grow_tbl[i])
161 static inline uint32_t
162 mlx5_trunk_size_get(struct mlx5_indexed_pool *pool, uint32_t trunk_idx)
164 struct mlx5_indexed_pool_config *cfg = &pool->cfg;
166 return cfg->trunk_size << (cfg->grow_shift *
167 (trunk_idx > cfg->grow_trunk ? cfg->grow_trunk : trunk_idx));
170 static inline uint32_t
171 mlx5_trunk_idx_offset_get(struct mlx5_indexed_pool *pool, uint32_t trunk_idx)
173 struct mlx5_indexed_pool_config *cfg = &pool->cfg;
178 if (!cfg->grow_trunk)
179 return cfg->trunk_size * trunk_idx;
180 if (trunk_idx < cfg->grow_trunk)
181 offset = pool->grow_tbl[trunk_idx - 1];
183 offset = pool->grow_tbl[cfg->grow_trunk - 1] +
184 (cfg->trunk_size << (cfg->grow_shift *
185 cfg->grow_trunk)) * (trunk_idx - cfg->grow_trunk);
189 struct mlx5_indexed_pool *
190 mlx5_ipool_create(struct mlx5_indexed_pool_config *cfg)
192 struct mlx5_indexed_pool *pool;
195 if (!cfg || !cfg->size || (!cfg->malloc ^ !cfg->free) ||
196 (cfg->trunk_size && ((cfg->trunk_size & (cfg->trunk_size - 1)) ||
197 ((__builtin_ffs(cfg->trunk_size) + TRUNK_IDX_BITS) > 32))))
199 pool = mlx5_malloc(MLX5_MEM_ZERO, sizeof(*pool) + cfg->grow_trunk *
200 sizeof(pool->grow_tbl[0]), RTE_CACHE_LINE_SIZE,
205 if (!pool->cfg.trunk_size)
206 pool->cfg.trunk_size = MLX5_IPOOL_DEFAULT_TRUNK_SIZE;
207 if (!cfg->malloc && !cfg->free) {
208 pool->cfg.malloc = mlx5_malloc;
209 pool->cfg.free = mlx5_free;
211 pool->free_list = TRUNK_INVALID;
212 if (pool->cfg.need_lock)
213 rte_spinlock_init(&pool->lock);
215 * Initialize the dynamic grow trunk size lookup table to have a quick
216 * lookup for the trunk entry index offset.
218 for (i = 0; i < cfg->grow_trunk; i++) {
219 pool->grow_tbl[i] = cfg->trunk_size << (cfg->grow_shift * i);
221 pool->grow_tbl[i] += pool->grow_tbl[i - 1];
227 mlx5_ipool_grow(struct mlx5_indexed_pool *pool)
229 struct mlx5_indexed_trunk *trunk;
230 struct mlx5_indexed_trunk **trunk_tmp;
231 struct mlx5_indexed_trunk **p;
232 size_t trunk_size = 0;
237 if (pool->n_trunk_valid == TRUNK_MAX_IDX)
239 if (pool->n_trunk_valid == pool->n_trunk) {
240 /* No free trunk flags, expand trunk list. */
241 int n_grow = pool->n_trunk_valid ? pool->n_trunk :
242 RTE_CACHE_LINE_SIZE / sizeof(void *);
244 p = pool->cfg.malloc(0, (pool->n_trunk_valid + n_grow) *
245 sizeof(struct mlx5_indexed_trunk *),
246 RTE_CACHE_LINE_SIZE, rte_socket_id());
250 memcpy(p, pool->trunks, pool->n_trunk_valid *
251 sizeof(struct mlx5_indexed_trunk *));
252 memset(RTE_PTR_ADD(p, pool->n_trunk_valid * sizeof(void *)), 0,
253 n_grow * sizeof(void *));
254 trunk_tmp = pool->trunks;
257 pool->cfg.free(trunk_tmp);
258 pool->n_trunk += n_grow;
260 if (!pool->cfg.release_mem_en) {
261 idx = pool->n_trunk_valid;
263 /* Find the first available slot in trunk list */
264 for (idx = 0; idx < pool->n_trunk; idx++)
265 if (pool->trunks[idx] == NULL)
268 trunk_size += sizeof(*trunk);
269 data_size = mlx5_trunk_size_get(pool, idx);
270 bmp_size = rte_bitmap_get_memory_footprint(data_size);
271 /* rte_bitmap requires memory cacheline aligned. */
272 trunk_size += RTE_CACHE_LINE_ROUNDUP(data_size * pool->cfg.size);
273 trunk_size += bmp_size;
274 trunk = pool->cfg.malloc(0, trunk_size,
275 RTE_CACHE_LINE_SIZE, rte_socket_id());
278 pool->trunks[idx] = trunk;
280 trunk->free = data_size;
281 trunk->prev = TRUNK_INVALID;
282 trunk->next = TRUNK_INVALID;
283 MLX5_ASSERT(pool->free_list == TRUNK_INVALID);
284 pool->free_list = idx;
285 /* Mark all entries as available. */
286 trunk->bmp = rte_bitmap_init_with_all_set(data_size, &trunk->data
287 [RTE_CACHE_LINE_ROUNDUP(data_size * pool->cfg.size)],
289 MLX5_ASSERT(trunk->bmp);
290 pool->n_trunk_valid++;
299 mlx5_ipool_malloc(struct mlx5_indexed_pool *pool, uint32_t *idx)
301 struct mlx5_indexed_trunk *trunk;
306 mlx5_ipool_lock(pool);
307 if (pool->free_list == TRUNK_INVALID) {
308 /* If no available trunks, grow new. */
309 if (mlx5_ipool_grow(pool)) {
310 mlx5_ipool_unlock(pool);
314 MLX5_ASSERT(pool->free_list != TRUNK_INVALID);
315 trunk = pool->trunks[pool->free_list];
316 MLX5_ASSERT(trunk->free);
317 if (!rte_bitmap_scan(trunk->bmp, &iidx, &slab)) {
318 mlx5_ipool_unlock(pool);
322 iidx += __builtin_ctzll(slab);
323 MLX5_ASSERT(iidx != UINT32_MAX);
324 MLX5_ASSERT(iidx < mlx5_trunk_size_get(pool, trunk->idx));
325 rte_bitmap_clear(trunk->bmp, iidx);
326 p = &trunk->data[iidx * pool->cfg.size];
327 iidx += mlx5_trunk_idx_offset_get(pool, trunk->idx);
328 iidx += 1; /* non-zero index. */
334 /* Full trunk will be removed from free list in imalloc. */
335 MLX5_ASSERT(pool->free_list == trunk->idx);
336 pool->free_list = trunk->next;
337 if (trunk->next != TRUNK_INVALID)
338 pool->trunks[trunk->next]->prev = TRUNK_INVALID;
339 trunk->prev = TRUNK_INVALID;
340 trunk->next = TRUNK_INVALID;
347 mlx5_ipool_unlock(pool);
352 mlx5_ipool_zmalloc(struct mlx5_indexed_pool *pool, uint32_t *idx)
354 void *entry = mlx5_ipool_malloc(pool, idx);
357 memset(entry, 0, pool->cfg.size);
362 mlx5_ipool_free(struct mlx5_indexed_pool *pool, uint32_t idx)
364 struct mlx5_indexed_trunk *trunk;
371 mlx5_ipool_lock(pool);
372 trunk_idx = mlx5_trunk_idx_get(pool, idx);
373 if ((!pool->cfg.release_mem_en && trunk_idx >= pool->n_trunk_valid) ||
374 (pool->cfg.release_mem_en && trunk_idx >= pool->n_trunk))
376 trunk = pool->trunks[trunk_idx];
379 entry_idx = idx - mlx5_trunk_idx_offset_get(pool, trunk->idx);
380 if (trunk_idx != trunk->idx ||
381 rte_bitmap_get(trunk->bmp, entry_idx))
383 rte_bitmap_set(trunk->bmp, entry_idx);
385 if (pool->cfg.release_mem_en && trunk->free == mlx5_trunk_size_get
386 (pool, trunk->idx)) {
387 if (pool->free_list == trunk->idx)
388 pool->free_list = trunk->next;
389 if (trunk->next != TRUNK_INVALID)
390 pool->trunks[trunk->next]->prev = trunk->prev;
391 if (trunk->prev != TRUNK_INVALID)
392 pool->trunks[trunk->prev]->next = trunk->next;
393 pool->cfg.free(trunk);
394 pool->trunks[trunk_idx] = NULL;
395 pool->n_trunk_valid--;
400 if (pool->n_trunk_valid == 0) {
401 pool->cfg.free(pool->trunks);
405 } else if (trunk->free == 1) {
406 /* Put into free trunk list head. */
407 MLX5_ASSERT(pool->free_list != trunk->idx);
408 trunk->next = pool->free_list;
409 trunk->prev = TRUNK_INVALID;
410 if (pool->free_list != TRUNK_INVALID)
411 pool->trunks[pool->free_list]->prev = trunk->idx;
412 pool->free_list = trunk->idx;
422 mlx5_ipool_unlock(pool);
426 mlx5_ipool_get(struct mlx5_indexed_pool *pool, uint32_t idx)
428 struct mlx5_indexed_trunk *trunk;
436 mlx5_ipool_lock(pool);
437 trunk_idx = mlx5_trunk_idx_get(pool, idx);
438 if ((!pool->cfg.release_mem_en && trunk_idx >= pool->n_trunk_valid) ||
439 (pool->cfg.release_mem_en && trunk_idx >= pool->n_trunk))
441 trunk = pool->trunks[trunk_idx];
444 entry_idx = idx - mlx5_trunk_idx_offset_get(pool, trunk->idx);
445 if (trunk_idx != trunk->idx ||
446 rte_bitmap_get(trunk->bmp, entry_idx))
448 p = &trunk->data[entry_idx * pool->cfg.size];
450 mlx5_ipool_unlock(pool);
455 mlx5_ipool_destroy(struct mlx5_indexed_pool *pool)
457 struct mlx5_indexed_trunk **trunks;
461 mlx5_ipool_lock(pool);
462 trunks = pool->trunks;
463 for (i = 0; i < pool->n_trunk; i++) {
465 pool->cfg.free(trunks[i]);
468 pool->cfg.free(pool->trunks);
469 mlx5_ipool_unlock(pool);
475 mlx5_ipool_dump(struct mlx5_indexed_pool *pool)
477 printf("Pool %s entry size %u, trunks %u, %d entry per trunk, "
479 pool->cfg.type, pool->cfg.size, pool->n_trunk_valid,
480 pool->cfg.trunk_size, pool->n_trunk_valid);
482 printf("Pool %s entry %u, trunk alloc %u, empty: %u, "
483 "available %u free %u\n",
484 pool->cfg.type, pool->n_entry, pool->trunk_new,
485 pool->trunk_empty, pool->trunk_avail, pool->trunk_free);
489 struct mlx5_l3t_tbl *
490 mlx5_l3t_create(enum mlx5_l3t_type type)
492 struct mlx5_l3t_tbl *tbl;
493 struct mlx5_indexed_pool_config l3t_ip_cfg = {
499 .malloc = mlx5_malloc,
503 if (type >= MLX5_L3T_TYPE_MAX) {
507 tbl = mlx5_malloc(MLX5_MEM_ZERO, sizeof(struct mlx5_l3t_tbl), 1,
515 case MLX5_L3T_TYPE_WORD:
516 l3t_ip_cfg.size = sizeof(struct mlx5_l3t_entry_word) +
517 sizeof(uint16_t) * MLX5_L3T_ET_SIZE;
518 l3t_ip_cfg.type = "mlx5_l3t_e_tbl_w";
520 case MLX5_L3T_TYPE_DWORD:
521 l3t_ip_cfg.size = sizeof(struct mlx5_l3t_entry_dword) +
522 sizeof(uint32_t) * MLX5_L3T_ET_SIZE;
523 l3t_ip_cfg.type = "mlx5_l3t_e_tbl_dw";
525 case MLX5_L3T_TYPE_QWORD:
526 l3t_ip_cfg.size = sizeof(struct mlx5_l3t_entry_qword) +
527 sizeof(uint64_t) * MLX5_L3T_ET_SIZE;
528 l3t_ip_cfg.type = "mlx5_l3t_e_tbl_qw";
531 l3t_ip_cfg.size = sizeof(struct mlx5_l3t_entry_ptr) +
532 sizeof(void *) * MLX5_L3T_ET_SIZE;
533 l3t_ip_cfg.type = "mlx5_l3t_e_tbl_tpr";
536 tbl->eip = mlx5_ipool_create(&l3t_ip_cfg);
546 mlx5_l3t_destroy(struct mlx5_l3t_tbl *tbl)
548 struct mlx5_l3t_level_tbl *g_tbl, *m_tbl;
555 for (i = 0; i < MLX5_L3T_GT_SIZE; i++) {
556 m_tbl = g_tbl->tbl[i];
559 for (j = 0; j < MLX5_L3T_MT_SIZE; j++) {
562 MLX5_ASSERT(!((struct mlx5_l3t_entry_word *)
563 m_tbl->tbl[j])->ref_cnt);
564 mlx5_ipool_free(tbl->eip,
565 ((struct mlx5_l3t_entry_word *)
566 m_tbl->tbl[j])->idx);
568 if (!(--m_tbl->ref_cnt))
571 MLX5_ASSERT(!m_tbl->ref_cnt);
572 mlx5_free(g_tbl->tbl[i]);
574 if (!(--g_tbl->ref_cnt))
577 MLX5_ASSERT(!g_tbl->ref_cnt);
581 mlx5_ipool_destroy(tbl->eip);
586 mlx5_l3t_get_entry(struct mlx5_l3t_tbl *tbl, uint32_t idx,
587 union mlx5_l3t_data *data)
589 struct mlx5_l3t_level_tbl *g_tbl, *m_tbl;
596 m_tbl = g_tbl->tbl[(idx >> MLX5_L3T_GT_OFFSET) & MLX5_L3T_GT_MASK];
599 e_tbl = m_tbl->tbl[(idx >> MLX5_L3T_MT_OFFSET) & MLX5_L3T_MT_MASK];
602 entry_idx = idx & MLX5_L3T_ET_MASK;
604 case MLX5_L3T_TYPE_WORD:
605 data->word = ((struct mlx5_l3t_entry_word *)e_tbl)->entry
608 case MLX5_L3T_TYPE_DWORD:
609 data->dword = ((struct mlx5_l3t_entry_dword *)e_tbl)->entry
612 case MLX5_L3T_TYPE_QWORD:
613 data->qword = ((struct mlx5_l3t_entry_qword *)e_tbl)->entry
617 data->ptr = ((struct mlx5_l3t_entry_ptr *)e_tbl)->entry
625 mlx5_l3t_clear_entry(struct mlx5_l3t_tbl *tbl, uint32_t idx)
627 struct mlx5_l3t_level_tbl *g_tbl, *m_tbl;
628 struct mlx5_l3t_entry_word *w_e_tbl;
629 struct mlx5_l3t_entry_dword *dw_e_tbl;
630 struct mlx5_l3t_entry_qword *qw_e_tbl;
631 struct mlx5_l3t_entry_ptr *ptr_e_tbl;
639 m_tbl = g_tbl->tbl[(idx >> MLX5_L3T_GT_OFFSET) & MLX5_L3T_GT_MASK];
642 e_tbl = m_tbl->tbl[(idx >> MLX5_L3T_MT_OFFSET) & MLX5_L3T_MT_MASK];
645 entry_idx = idx & MLX5_L3T_ET_MASK;
647 case MLX5_L3T_TYPE_WORD:
648 w_e_tbl = (struct mlx5_l3t_entry_word *)e_tbl;
649 w_e_tbl->entry[entry_idx] = 0;
650 ref_cnt = --w_e_tbl->ref_cnt;
652 case MLX5_L3T_TYPE_DWORD:
653 dw_e_tbl = (struct mlx5_l3t_entry_dword *)e_tbl;
654 dw_e_tbl->entry[entry_idx] = 0;
655 ref_cnt = --dw_e_tbl->ref_cnt;
657 case MLX5_L3T_TYPE_QWORD:
658 qw_e_tbl = (struct mlx5_l3t_entry_qword *)e_tbl;
659 qw_e_tbl->entry[entry_idx] = 0;
660 ref_cnt = --qw_e_tbl->ref_cnt;
663 ptr_e_tbl = (struct mlx5_l3t_entry_ptr *)e_tbl;
664 ptr_e_tbl->entry[entry_idx] = NULL;
665 ref_cnt = --ptr_e_tbl->ref_cnt;
669 mlx5_ipool_free(tbl->eip,
670 ((struct mlx5_l3t_entry_word *)e_tbl)->idx);
671 m_tbl->tbl[(idx >> MLX5_L3T_MT_OFFSET) & MLX5_L3T_MT_MASK] =
673 if (!(--m_tbl->ref_cnt)) {
676 [(idx >> MLX5_L3T_GT_OFFSET) & MLX5_L3T_GT_MASK] = NULL;
677 if (!(--g_tbl->ref_cnt)) {
686 mlx5_l3t_set_entry(struct mlx5_l3t_tbl *tbl, uint32_t idx,
687 union mlx5_l3t_data *data)
689 struct mlx5_l3t_level_tbl *g_tbl, *m_tbl;
690 struct mlx5_l3t_entry_word *w_e_tbl;
691 struct mlx5_l3t_entry_dword *dw_e_tbl;
692 struct mlx5_l3t_entry_qword *qw_e_tbl;
693 struct mlx5_l3t_entry_ptr *ptr_e_tbl;
695 uint32_t entry_idx, tbl_idx = 0;
697 /* Check the global table, create it if empty. */
700 g_tbl = mlx5_malloc(MLX5_MEM_ZERO,
701 sizeof(struct mlx5_l3t_level_tbl) +
702 sizeof(void *) * MLX5_L3T_GT_SIZE, 1,
711 * Check the middle table, create it if empty. Ref_cnt will be
712 * increased if new sub table created.
714 m_tbl = g_tbl->tbl[(idx >> MLX5_L3T_GT_OFFSET) & MLX5_L3T_GT_MASK];
716 m_tbl = mlx5_malloc(MLX5_MEM_ZERO,
717 sizeof(struct mlx5_l3t_level_tbl) +
718 sizeof(void *) * MLX5_L3T_MT_SIZE, 1,
724 g_tbl->tbl[(idx >> MLX5_L3T_GT_OFFSET) & MLX5_L3T_GT_MASK] =
729 * Check the entry table, create it if empty. Ref_cnt will be
730 * increased if new sub entry table created.
732 e_tbl = m_tbl->tbl[(idx >> MLX5_L3T_MT_OFFSET) & MLX5_L3T_MT_MASK];
734 e_tbl = mlx5_ipool_zmalloc(tbl->eip, &tbl_idx);
739 ((struct mlx5_l3t_entry_word *)e_tbl)->idx = tbl_idx;
740 m_tbl->tbl[(idx >> MLX5_L3T_MT_OFFSET) & MLX5_L3T_MT_MASK] =
744 entry_idx = idx & MLX5_L3T_ET_MASK;
746 case MLX5_L3T_TYPE_WORD:
747 w_e_tbl = (struct mlx5_l3t_entry_word *)e_tbl;
748 w_e_tbl->entry[entry_idx] = data->word;
751 case MLX5_L3T_TYPE_DWORD:
752 dw_e_tbl = (struct mlx5_l3t_entry_dword *)e_tbl;
753 dw_e_tbl->entry[entry_idx] = data->dword;
756 case MLX5_L3T_TYPE_QWORD:
757 qw_e_tbl = (struct mlx5_l3t_entry_qword *)e_tbl;
758 qw_e_tbl->entry[entry_idx] = data->qword;
762 ptr_e_tbl = (struct mlx5_l3t_entry_ptr *)e_tbl;
763 ptr_e_tbl->entry[entry_idx] = data->ptr;
764 ptr_e_tbl->ref_cnt++;