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 /********************* mlx5 list ************************/ 15 16 static int 17 mlx5_list_init(struct mlx5_list_inconst *l_inconst, 18 struct mlx5_list_const *l_const, 19 struct mlx5_list_cache *gc) 20 { 21 rte_rwlock_init(&l_inconst->lock); 22 if (l_const->lcores_share) { 23 l_inconst->cache[MLX5_LIST_GLOBAL] = gc; 24 LIST_INIT(&l_inconst->cache[MLX5_LIST_GLOBAL]->h); 25 } 26 return 0; 27 } 28 29 struct mlx5_list * 30 mlx5_list_create(const char *name, void *ctx, bool lcores_share, 31 mlx5_list_create_cb cb_create, 32 mlx5_list_match_cb cb_match, 33 mlx5_list_remove_cb cb_remove, 34 mlx5_list_clone_cb cb_clone, 35 mlx5_list_clone_free_cb cb_clone_free) 36 { 37 struct mlx5_list *list; 38 struct mlx5_list_cache *gc = NULL; 39 40 if (!cb_match || !cb_create || !cb_remove || !cb_clone || 41 !cb_clone_free) { 42 rte_errno = EINVAL; 43 return NULL; 44 } 45 list = mlx5_malloc(MLX5_MEM_ZERO, 46 sizeof(*list) + (lcores_share ? sizeof(*gc) : 0), 47 0, SOCKET_ID_ANY); 48 49 if (!list) 50 return NULL; 51 if (name) 52 snprintf(list->l_const.name, 53 sizeof(list->l_const.name), "%s", name); 54 list->l_const.ctx = ctx; 55 list->l_const.lcores_share = lcores_share; 56 list->l_const.cb_create = cb_create; 57 list->l_const.cb_match = cb_match; 58 list->l_const.cb_remove = cb_remove; 59 list->l_const.cb_clone = cb_clone; 60 list->l_const.cb_clone_free = cb_clone_free; 61 rte_spinlock_init(&list->l_const.lcore_lock); 62 if (lcores_share) 63 gc = (struct mlx5_list_cache *)(list + 1); 64 if (mlx5_list_init(&list->l_inconst, &list->l_const, gc) != 0) { 65 mlx5_free(list); 66 return NULL; 67 } 68 DRV_LOG(DEBUG, "mlx5 list %s was created.", name); 69 return list; 70 } 71 72 static struct mlx5_list_entry * 73 __list_lookup(struct mlx5_list_inconst *l_inconst, 74 struct mlx5_list_const *l_const, 75 int lcore_index, void *ctx, bool reuse) 76 { 77 struct mlx5_list_entry *entry = 78 LIST_FIRST(&l_inconst->cache[lcore_index]->h); 79 uint32_t ret; 80 81 while (entry != NULL) { 82 if (l_const->cb_match(l_const->ctx, entry, ctx) == 0) { 83 if (reuse) { 84 ret = __atomic_add_fetch(&entry->ref_cnt, 1, 85 __ATOMIC_RELAXED) - 1; 86 DRV_LOG(DEBUG, "mlx5 list %s entry %p ref: %u.", 87 l_const->name, (void *)entry, 88 entry->ref_cnt); 89 } else if (lcore_index < MLX5_LIST_GLOBAL) { 90 ret = __atomic_load_n(&entry->ref_cnt, 91 __ATOMIC_RELAXED); 92 } 93 if (likely(ret != 0 || lcore_index == MLX5_LIST_GLOBAL)) 94 return entry; 95 if (reuse && ret == 0) 96 entry->ref_cnt--; /* Invalid entry. */ 97 } 98 entry = LIST_NEXT(entry, next); 99 } 100 return NULL; 101 } 102 103 static inline struct mlx5_list_entry * 104 _mlx5_list_lookup(struct mlx5_list_inconst *l_inconst, 105 struct mlx5_list_const *l_const, void *ctx) 106 { 107 struct mlx5_list_entry *entry = NULL; 108 int i; 109 110 rte_rwlock_read_lock(&l_inconst->lock); 111 for (i = 0; i < MLX5_LIST_GLOBAL; i++) { 112 if (!l_inconst->cache[i]) 113 continue; 114 entry = __list_lookup(l_inconst, l_const, i, 115 ctx, false); 116 if (entry) 117 break; 118 } 119 rte_rwlock_read_unlock(&l_inconst->lock); 120 return entry; 121 } 122 123 struct mlx5_list_entry * 124 mlx5_list_lookup(struct mlx5_list *list, void *ctx) 125 { 126 return _mlx5_list_lookup(&list->l_inconst, &list->l_const, ctx); 127 } 128 129 130 static struct mlx5_list_entry * 131 mlx5_list_cache_insert(struct mlx5_list_inconst *l_inconst, 132 struct mlx5_list_const *l_const, int lcore_index, 133 struct mlx5_list_entry *gentry, void *ctx) 134 { 135 struct mlx5_list_entry *lentry = 136 l_const->cb_clone(l_const->ctx, gentry, ctx); 137 138 if (unlikely(!lentry)) 139 return NULL; 140 lentry->ref_cnt = 1u; 141 lentry->gentry = gentry; 142 lentry->lcore_idx = (uint32_t)lcore_index; 143 LIST_INSERT_HEAD(&l_inconst->cache[lcore_index]->h, lentry, next); 144 return lentry; 145 } 146 147 static void 148 __list_cache_clean(struct mlx5_list_inconst *l_inconst, 149 struct mlx5_list_const *l_const, 150 int lcore_index) 151 { 152 struct mlx5_list_cache *c = l_inconst->cache[lcore_index]; 153 struct mlx5_list_entry *entry = LIST_FIRST(&c->h); 154 uint32_t inv_cnt = __atomic_exchange_n(&c->inv_cnt, 0, 155 __ATOMIC_RELAXED); 156 157 while (inv_cnt != 0 && entry != NULL) { 158 struct mlx5_list_entry *nentry = LIST_NEXT(entry, next); 159 160 if (__atomic_load_n(&entry->ref_cnt, __ATOMIC_RELAXED) == 0) { 161 LIST_REMOVE(entry, next); 162 if (l_const->lcores_share) 163 l_const->cb_clone_free(l_const->ctx, entry); 164 else 165 l_const->cb_remove(l_const->ctx, entry); 166 inv_cnt--; 167 } 168 entry = nentry; 169 } 170 } 171 172 static inline struct mlx5_list_entry * 173 _mlx5_list_register(struct mlx5_list_inconst *l_inconst, 174 struct mlx5_list_const *l_const, 175 void *ctx, int lcore_index) 176 { 177 struct mlx5_list_entry *entry = NULL, *local_entry; 178 volatile uint32_t prev_gen_cnt = 0; 179 MLX5_ASSERT(l_inconst); 180 if (unlikely(!l_inconst->cache[lcore_index])) { 181 l_inconst->cache[lcore_index] = mlx5_malloc(0, 182 sizeof(struct mlx5_list_cache), 183 RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY); 184 if (!l_inconst->cache[lcore_index]) { 185 rte_errno = ENOMEM; 186 return NULL; 187 } 188 l_inconst->cache[lcore_index]->inv_cnt = 0; 189 LIST_INIT(&l_inconst->cache[lcore_index]->h); 190 } 191 /* 0. Free entries that was invalidated by other lcores. */ 192 __list_cache_clean(l_inconst, l_const, lcore_index); 193 /* 1. Lookup in local cache. */ 194 local_entry = __list_lookup(l_inconst, l_const, lcore_index, ctx, true); 195 if (local_entry) 196 return local_entry; 197 if (l_const->lcores_share) { 198 /* 2. Lookup with read lock on global list, reuse if found. */ 199 rte_rwlock_read_lock(&l_inconst->lock); 200 entry = __list_lookup(l_inconst, l_const, MLX5_LIST_GLOBAL, 201 ctx, true); 202 if (likely(entry)) { 203 rte_rwlock_read_unlock(&l_inconst->lock); 204 return mlx5_list_cache_insert(l_inconst, l_const, 205 lcore_index, 206 entry, ctx); 207 } 208 prev_gen_cnt = l_inconst->gen_cnt; 209 rte_rwlock_read_unlock(&l_inconst->lock); 210 } 211 /* 3. Prepare new entry for global list and for cache. */ 212 entry = l_const->cb_create(l_const->ctx, ctx); 213 if (unlikely(!entry)) 214 return NULL; 215 entry->ref_cnt = 1u; 216 if (!l_const->lcores_share) { 217 entry->lcore_idx = (uint32_t)lcore_index; 218 LIST_INSERT_HEAD(&l_inconst->cache[lcore_index]->h, 219 entry, next); 220 __atomic_add_fetch(&l_inconst->count, 1, __ATOMIC_RELAXED); 221 DRV_LOG(DEBUG, "MLX5 list %s c%d entry %p new: %u.", 222 l_const->name, lcore_index, 223 (void *)entry, entry->ref_cnt); 224 return entry; 225 } 226 local_entry = l_const->cb_clone(l_const->ctx, entry, ctx); 227 if (unlikely(!local_entry)) { 228 l_const->cb_remove(l_const->ctx, entry); 229 return NULL; 230 } 231 local_entry->ref_cnt = 1u; 232 local_entry->gentry = entry; 233 local_entry->lcore_idx = (uint32_t)lcore_index; 234 rte_rwlock_write_lock(&l_inconst->lock); 235 /* 4. Make sure the same entry was not created before the write lock. */ 236 if (unlikely(prev_gen_cnt != l_inconst->gen_cnt)) { 237 struct mlx5_list_entry *oentry = __list_lookup(l_inconst, 238 l_const, 239 MLX5_LIST_GLOBAL, 240 ctx, true); 241 242 if (unlikely(oentry)) { 243 /* 4.5. Found real race!!, reuse the old entry. */ 244 rte_rwlock_write_unlock(&l_inconst->lock); 245 l_const->cb_remove(l_const->ctx, entry); 246 l_const->cb_clone_free(l_const->ctx, local_entry); 247 return mlx5_list_cache_insert(l_inconst, l_const, 248 lcore_index, 249 oentry, ctx); 250 } 251 } 252 /* 5. Update lists. */ 253 LIST_INSERT_HEAD(&l_inconst->cache[MLX5_LIST_GLOBAL]->h, entry, next); 254 l_inconst->gen_cnt++; 255 rte_rwlock_write_unlock(&l_inconst->lock); 256 LIST_INSERT_HEAD(&l_inconst->cache[lcore_index]->h, local_entry, next); 257 __atomic_add_fetch(&l_inconst->count, 1, __ATOMIC_RELAXED); 258 DRV_LOG(DEBUG, "mlx5 list %s entry %p new: %u.", l_const->name, 259 (void *)entry, entry->ref_cnt); 260 return local_entry; 261 } 262 263 struct mlx5_list_entry * 264 mlx5_list_register(struct mlx5_list *list, void *ctx) 265 { 266 struct mlx5_list_entry *entry; 267 int lcore_index = rte_lcore_index(rte_lcore_id()); 268 269 if (unlikely(lcore_index == -1)) { 270 lcore_index = MLX5_LIST_NLCORE; 271 rte_spinlock_lock(&list->l_const.lcore_lock); 272 } 273 entry = _mlx5_list_register(&list->l_inconst, &list->l_const, ctx, 274 lcore_index); 275 if (unlikely(lcore_index == MLX5_LIST_NLCORE)) 276 rte_spinlock_unlock(&list->l_const.lcore_lock); 277 return entry; 278 } 279 280 static inline int 281 _mlx5_list_unregister(struct mlx5_list_inconst *l_inconst, 282 struct mlx5_list_const *l_const, 283 struct mlx5_list_entry *entry, 284 int lcore_idx) 285 { 286 struct mlx5_list_entry *gentry = entry->gentry; 287 288 if (__atomic_sub_fetch(&entry->ref_cnt, 1, __ATOMIC_RELAXED) != 0) 289 return 1; 290 if (entry->lcore_idx == (uint32_t)lcore_idx) { 291 LIST_REMOVE(entry, next); 292 if (l_const->lcores_share) 293 l_const->cb_clone_free(l_const->ctx, entry); 294 else 295 l_const->cb_remove(l_const->ctx, entry); 296 } else { 297 __atomic_add_fetch(&l_inconst->cache[entry->lcore_idx]->inv_cnt, 298 1, __ATOMIC_RELAXED); 299 } 300 if (!l_const->lcores_share) { 301 __atomic_sub_fetch(&l_inconst->count, 1, __ATOMIC_RELAXED); 302 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.", 303 l_const->name, (void *)entry); 304 return 0; 305 } 306 if (__atomic_sub_fetch(&gentry->ref_cnt, 1, __ATOMIC_RELAXED) != 0) 307 return 1; 308 rte_rwlock_write_lock(&l_inconst->lock); 309 if (likely(gentry->ref_cnt == 0)) { 310 LIST_REMOVE(gentry, next); 311 rte_rwlock_write_unlock(&l_inconst->lock); 312 l_const->cb_remove(l_const->ctx, gentry); 313 __atomic_sub_fetch(&l_inconst->count, 1, __ATOMIC_RELAXED); 314 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.", 315 l_const->name, (void *)gentry); 316 return 0; 317 } 318 rte_rwlock_write_unlock(&l_inconst->lock); 319 return 1; 320 } 321 322 int 323 mlx5_list_unregister(struct mlx5_list *list, 324 struct mlx5_list_entry *entry) 325 { 326 int ret; 327 int lcore_index = rte_lcore_index(rte_lcore_id()); 328 329 if (unlikely(lcore_index == -1)) { 330 lcore_index = MLX5_LIST_NLCORE; 331 rte_spinlock_lock(&list->l_const.lcore_lock); 332 } 333 ret = _mlx5_list_unregister(&list->l_inconst, &list->l_const, entry, 334 lcore_index); 335 if (unlikely(lcore_index == MLX5_LIST_NLCORE)) 336 rte_spinlock_unlock(&list->l_const.lcore_lock); 337 return ret; 338 339 } 340 341 static void 342 mlx5_list_uninit(struct mlx5_list_inconst *l_inconst, 343 struct mlx5_list_const *l_const) 344 { 345 struct mlx5_list_entry *entry; 346 int i; 347 348 MLX5_ASSERT(l_inconst); 349 for (i = 0; i < MLX5_LIST_MAX; i++) { 350 if (!l_inconst->cache[i]) 351 continue; 352 while (!LIST_EMPTY(&l_inconst->cache[i]->h)) { 353 entry = LIST_FIRST(&l_inconst->cache[i]->h); 354 LIST_REMOVE(entry, next); 355 if (i == MLX5_LIST_GLOBAL) { 356 l_const->cb_remove(l_const->ctx, entry); 357 DRV_LOG(DEBUG, "mlx5 list %s entry %p " 358 "destroyed.", l_const->name, 359 (void *)entry); 360 } else { 361 l_const->cb_clone_free(l_const->ctx, entry); 362 } 363 } 364 if (i != MLX5_LIST_GLOBAL) 365 mlx5_free(l_inconst->cache[i]); 366 } 367 } 368 369 void 370 mlx5_list_destroy(struct mlx5_list *list) 371 { 372 mlx5_list_uninit(&list->l_inconst, &list->l_const); 373 mlx5_free(list); 374 } 375 376 uint32_t 377 mlx5_list_get_entry_num(struct mlx5_list *list) 378 { 379 MLX5_ASSERT(list); 380 return __atomic_load_n(&list->l_inconst.count, __ATOMIC_RELAXED); 381 } 382 383 /********************* Hash List **********************/ 384 385 struct mlx5_hlist * 386 mlx5_hlist_create(const char *name, uint32_t size, bool direct_key, 387 bool lcores_share, void *ctx, mlx5_list_create_cb cb_create, 388 mlx5_list_match_cb cb_match, 389 mlx5_list_remove_cb cb_remove, 390 mlx5_list_clone_cb cb_clone, 391 mlx5_list_clone_free_cb cb_clone_free) 392 { 393 struct mlx5_hlist *h; 394 struct mlx5_list_cache *gc; 395 uint32_t act_size; 396 uint32_t alloc_size; 397 uint32_t i; 398 399 if (!cb_match || !cb_create || !cb_remove || !cb_clone || 400 !cb_clone_free) { 401 rte_errno = EINVAL; 402 return NULL; 403 } 404 /* Align to the next power of 2, 32bits integer is enough now. */ 405 if (!rte_is_power_of_2(size)) { 406 act_size = rte_align32pow2(size); 407 DRV_LOG(WARNING, "Size 0x%" PRIX32 " is not power of 2, will " 408 "be aligned to 0x%" PRIX32 ".", size, act_size); 409 } else { 410 act_size = size; 411 } 412 alloc_size = sizeof(struct mlx5_hlist) + 413 sizeof(struct mlx5_hlist_bucket) * act_size; 414 if (lcores_share) 415 alloc_size += sizeof(struct mlx5_list_cache) * act_size; 416 /* Using zmalloc, then no need to initialize the heads. */ 417 h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE, 418 SOCKET_ID_ANY); 419 if (!h) { 420 DRV_LOG(ERR, "No memory for hash list %s creation", 421 name ? name : "None"); 422 return NULL; 423 } 424 if (name) 425 snprintf(h->l_const.name, sizeof(h->l_const.name), "%s", name); 426 h->l_const.ctx = ctx; 427 h->l_const.lcores_share = lcores_share; 428 h->l_const.cb_create = cb_create; 429 h->l_const.cb_match = cb_match; 430 h->l_const.cb_remove = cb_remove; 431 h->l_const.cb_clone = cb_clone; 432 h->l_const.cb_clone_free = cb_clone_free; 433 rte_spinlock_init(&h->l_const.lcore_lock); 434 h->mask = act_size - 1; 435 h->direct_key = direct_key; 436 gc = (struct mlx5_list_cache *)&h->buckets[act_size]; 437 for (i = 0; i < act_size; i++) { 438 if (mlx5_list_init(&h->buckets[i].l, &h->l_const, 439 lcores_share ? &gc[i] : NULL) != 0) { 440 mlx5_free(h); 441 return NULL; 442 } 443 } 444 DRV_LOG(DEBUG, "Hash list %s with size 0x%" PRIX32 " was created.", 445 name, act_size); 446 return h; 447 } 448 449 450 struct mlx5_list_entry * 451 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx) 452 { 453 uint32_t idx; 454 455 if (h->direct_key) 456 idx = (uint32_t)(key & h->mask); 457 else 458 idx = rte_hash_crc_8byte(key, 0) & h->mask; 459 return _mlx5_list_lookup(&h->buckets[idx].l, &h->l_const, ctx); 460 } 461 462 struct mlx5_list_entry* 463 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx) 464 { 465 uint32_t idx; 466 struct mlx5_list_entry *entry; 467 int lcore_index = rte_lcore_index(rte_lcore_id()); 468 469 if (h->direct_key) 470 idx = (uint32_t)(key & h->mask); 471 else 472 idx = rte_hash_crc_8byte(key, 0) & h->mask; 473 if (unlikely(lcore_index == -1)) { 474 lcore_index = MLX5_LIST_NLCORE; 475 rte_spinlock_lock(&h->l_const.lcore_lock); 476 } 477 entry = _mlx5_list_register(&h->buckets[idx].l, &h->l_const, ctx, 478 lcore_index); 479 if (likely(entry)) { 480 if (h->l_const.lcores_share) 481 entry->gentry->bucket_idx = idx; 482 else 483 entry->bucket_idx = idx; 484 } 485 if (unlikely(lcore_index == MLX5_LIST_NLCORE)) 486 rte_spinlock_unlock(&h->l_const.lcore_lock); 487 return entry; 488 } 489 490 int 491 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_list_entry *entry) 492 { 493 int lcore_index = rte_lcore_index(rte_lcore_id()); 494 int ret; 495 uint32_t idx = h->l_const.lcores_share ? entry->gentry->bucket_idx : 496 entry->bucket_idx; 497 if (unlikely(lcore_index == -1)) { 498 lcore_index = MLX5_LIST_NLCORE; 499 rte_spinlock_lock(&h->l_const.lcore_lock); 500 } 501 ret = _mlx5_list_unregister(&h->buckets[idx].l, &h->l_const, entry, 502 lcore_index); 503 if (unlikely(lcore_index == MLX5_LIST_NLCORE)) 504 rte_spinlock_unlock(&h->l_const.lcore_lock); 505 return ret; 506 } 507 508 void 509 mlx5_hlist_destroy(struct mlx5_hlist *h) 510 { 511 uint32_t i; 512 513 for (i = 0; i <= h->mask; i++) 514 mlx5_list_uninit(&h->buckets[i].l, &h->l_const); 515 mlx5_free(h); 516 } 517