1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright 2019 Mellanox Technologies, Ltd 3 */ 4 5 #include <rte_malloc.h> 6 #include <rte_hash_crc.h> 7 #include <rte_errno.h> 8 9 #include <mlx5_malloc.h> 10 11 #include "mlx5_common_utils.h" 12 #include "mlx5_common_log.h" 13 14 /********************* Hash List **********************/ 15 16 static struct mlx5_hlist_entry * 17 mlx5_hlist_default_create_cb(struct mlx5_hlist *h, uint64_t key __rte_unused, 18 void *ctx __rte_unused) 19 { 20 return mlx5_malloc(MLX5_MEM_ZERO, h->entry_sz, 0, SOCKET_ID_ANY); 21 } 22 23 static void 24 mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused, 25 struct mlx5_hlist_entry *entry) 26 { 27 mlx5_free(entry); 28 } 29 30 struct mlx5_hlist * 31 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size, 32 uint32_t flags, mlx5_hlist_create_cb cb_create, 33 mlx5_hlist_match_cb cb_match, mlx5_hlist_remove_cb cb_remove) 34 { 35 struct mlx5_hlist *h; 36 uint32_t act_size; 37 uint32_t alloc_size; 38 uint32_t i; 39 40 if (!size || !cb_match || (!cb_create ^ !cb_remove)) 41 return NULL; 42 /* Align to the next power of 2, 32bits integer is enough now. */ 43 if (!rte_is_power_of_2(size)) { 44 act_size = rte_align32pow2(size); 45 DRV_LOG(DEBUG, "Size 0x%" PRIX32 " is not power of 2, " 46 "will be aligned to 0x%" PRIX32 ".", size, act_size); 47 } else { 48 act_size = size; 49 } 50 alloc_size = sizeof(struct mlx5_hlist) + 51 sizeof(struct mlx5_hlist_bucket) * act_size; 52 /* Using zmalloc, then no need to initialize the heads. */ 53 h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE, 54 SOCKET_ID_ANY); 55 if (!h) { 56 DRV_LOG(ERR, "No memory for hash list %s creation", 57 name ? name : "None"); 58 return NULL; 59 } 60 if (name) 61 snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name); 62 h->table_sz = act_size; 63 h->mask = act_size - 1; 64 h->entry_sz = entry_size; 65 h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY); 66 h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST); 67 h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb; 68 h->cb_match = cb_match; 69 h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb; 70 for (i = 0; i < act_size; i++) 71 rte_rwlock_init(&h->buckets[i].lock); 72 DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.", 73 h->name, act_size); 74 return h; 75 } 76 77 static struct mlx5_hlist_entry * 78 __hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx, 79 void *ctx, bool reuse) 80 { 81 struct mlx5_hlist_head *first; 82 struct mlx5_hlist_entry *node; 83 84 MLX5_ASSERT(h); 85 first = &h->buckets[idx].head; 86 LIST_FOREACH(node, first, next) { 87 if (!h->cb_match(h, node, key, ctx)) { 88 if (reuse) { 89 __atomic_add_fetch(&node->ref_cnt, 1, 90 __ATOMIC_RELAXED); 91 DRV_LOG(DEBUG, "Hash list %s entry %p " 92 "reuse: %u.", 93 h->name, (void *)node, node->ref_cnt); 94 } 95 break; 96 } 97 } 98 return node; 99 } 100 101 static struct mlx5_hlist_entry * 102 hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx, 103 void *ctx, bool reuse) 104 { 105 struct mlx5_hlist_entry *node; 106 107 MLX5_ASSERT(h); 108 rte_rwlock_read_lock(&h->buckets[idx].lock); 109 node = __hlist_lookup(h, key, idx, ctx, reuse); 110 rte_rwlock_read_unlock(&h->buckets[idx].lock); 111 return node; 112 } 113 114 struct mlx5_hlist_entry * 115 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx) 116 { 117 uint32_t idx; 118 119 if (h->direct_key) 120 idx = (uint32_t)(key & h->mask); 121 else 122 idx = rte_hash_crc_8byte(key, 0) & h->mask; 123 return hlist_lookup(h, key, idx, ctx, false); 124 } 125 126 struct mlx5_hlist_entry* 127 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx) 128 { 129 uint32_t idx; 130 struct mlx5_hlist_head *first; 131 struct mlx5_hlist_bucket *b; 132 struct mlx5_hlist_entry *entry; 133 uint32_t prev_gen_cnt = 0; 134 135 if (h->direct_key) 136 idx = (uint32_t)(key & h->mask); 137 else 138 idx = rte_hash_crc_8byte(key, 0) & h->mask; 139 MLX5_ASSERT(h); 140 b = &h->buckets[idx]; 141 /* Use write lock directly for write-most list. */ 142 if (!h->write_most) { 143 prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE); 144 entry = hlist_lookup(h, key, idx, ctx, true); 145 if (entry) 146 return entry; 147 } 148 rte_rwlock_write_lock(&b->lock); 149 /* Check if the list changed by other threads. */ 150 if (h->write_most || 151 prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) { 152 entry = __hlist_lookup(h, key, idx, ctx, true); 153 if (entry) 154 goto done; 155 } 156 first = &b->head; 157 entry = h->cb_create(h, key, ctx); 158 if (!entry) { 159 rte_errno = ENOMEM; 160 DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name); 161 goto done; 162 } 163 entry->idx = idx; 164 entry->ref_cnt = 1; 165 LIST_INSERT_HEAD(first, entry, next); 166 __atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL); 167 DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.", 168 h->name, (void *)entry, entry->ref_cnt); 169 done: 170 rte_rwlock_write_unlock(&b->lock); 171 return entry; 172 } 173 174 int 175 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry) 176 { 177 uint32_t idx = entry->idx; 178 179 rte_rwlock_write_lock(&h->buckets[idx].lock); 180 MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev); 181 DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.", 182 h->name, (void *)entry, entry->ref_cnt); 183 if (--entry->ref_cnt) { 184 rte_rwlock_write_unlock(&h->buckets[idx].lock); 185 return 1; 186 } 187 LIST_REMOVE(entry, next); 188 /* Set to NULL to get rid of removing action for more than once. */ 189 entry->next.le_prev = NULL; 190 h->cb_remove(h, entry); 191 rte_rwlock_write_unlock(&h->buckets[idx].lock); 192 DRV_LOG(DEBUG, "Hash list %s entry %p removed.", 193 h->name, (void *)entry); 194 return 0; 195 } 196 197 void 198 mlx5_hlist_destroy(struct mlx5_hlist *h) 199 { 200 uint32_t idx; 201 struct mlx5_hlist_entry *entry; 202 203 MLX5_ASSERT(h); 204 for (idx = 0; idx < h->table_sz; ++idx) { 205 /* No LIST_FOREACH_SAFE, using while instead. */ 206 while (!LIST_EMPTY(&h->buckets[idx].head)) { 207 entry = LIST_FIRST(&h->buckets[idx].head); 208 LIST_REMOVE(entry, next); 209 /* 210 * The owner of whole element which contains data entry 211 * is the user, so it's the user's duty to do the clean 212 * up and the free work because someone may not put the 213 * hlist entry at the beginning(suggested to locate at 214 * the beginning). Or else the default free function 215 * will be used. 216 */ 217 h->cb_remove(h, entry); 218 } 219 } 220 mlx5_free(h); 221 } 222