drivers/common/mlx5/mlx5_common_utils.c

   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 struct 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)
  23 {
  24         struct mlx5_list *list;
  25         int i;
  26
  27         if (!cb_match || !cb_create || !cb_remove || !cb_clone ||
  28             !cb_clone_free) {
  29                 rte_errno = EINVAL;
  30                 return NULL;
  31         }
  32         list = mlx5_malloc(MLX5_MEM_ZERO, sizeof(*list), 0, SOCKET_ID_ANY);
  33         if (!list)
  34                 return NULL;
  35         if (name)
  36                 snprintf(list->name, sizeof(list->name), "%s", name);
  37         list->ctx = ctx;
  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);
  48         return list;
  49 }
  50
  51 static struct mlx5_list_entry *
  52 __list_lookup(struct mlx5_list *list, int lcore_index, void *ctx, bool reuse)
  53 {
  54         struct mlx5_list_entry *entry = LIST_FIRST(&list->cache[lcore_index].h);
  55         uint32_t ret;
  56
  57         while (entry != NULL) {
  58                 if (list->cb_match(list->ctx, entry, ctx) == 0) {
  59                         if (reuse) {
  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,
  64                                         entry->ref_cnt);
  65                         } else if (lcore_index < RTE_MAX_LCORE) {
  66                                 ret = __atomic_load_n(&entry->ref_cnt,
  67                                                       __ATOMIC_RELAXED);
  68                         }
  69                         if (likely(ret != 0 || lcore_index == RTE_MAX_LCORE))
  70                                 return entry;
  71                         if (reuse && ret == 0)
  72                                 entry->ref_cnt--; /* Invalid entry. */
  73                 }
  74                 entry = LIST_NEXT(entry, next);
  75         }
  76         return NULL;
  77 }
  78
  79 struct mlx5_list_entry *
  80 mlx5_list_lookup(struct mlx5_list *list, void *ctx)
  81 {
  82         struct mlx5_list_entry *entry = NULL;
  83         int i;
  84
  85         rte_rwlock_read_lock(&list->lock);
  86         for (i = 0; i < RTE_MAX_LCORE; i++) {
  87                 entry = __list_lookup(list, i, ctx, false);
  88                 if (entry)
  89                         break;
  90         }
  91         rte_rwlock_read_unlock(&list->lock);
  92         return entry;
  93 }
  94
  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)
  98 {
  99         struct mlx5_list_entry *lentry = list->cb_clone(list->ctx, gentry, ctx);
 100
 101         if (unlikely(!lentry))
 102                 return NULL;
 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);
 107         return lentry;
 108 }
 109
 110 static void
 111 __list_cache_clean(struct mlx5_list *list, int lcore_index)
 112 {
 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,
 116                                                __ATOMIC_RELAXED);
 117
 118         while (inv_cnt != 0 && entry != NULL) {
 119                 struct mlx5_list_entry *nentry = LIST_NEXT(entry, next);
 120
 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->ctx, entry);
 125                         else
 126                                 list->cb_remove(list->ctx, entry);
 127                         inv_cnt--;
 128                 }
 129                 entry = nentry;
 130         }
 131 }
 132
 133 struct mlx5_list_entry *
 134 mlx5_list_register(struct mlx5_list *list, void *ctx)
 135 {
 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());
 139
 140         MLX5_ASSERT(list);
 141         MLX5_ASSERT(lcore_index < RTE_MAX_LCORE);
 142         if (unlikely(lcore_index == -1)) {
 143                 rte_errno = ENOTSUP;
 144                 return NULL;
 145         }
 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);
 150         if (local_entry)
 151                 return local_entry;
 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);
 156                 if (likely(entry)) {
 157                         rte_rwlock_read_unlock(&list->lock);
 158                         return mlx5_list_cache_insert(list, lcore_index, entry,
 159                                                       ctx);
 160                 }
 161                 prev_gen_cnt = list->gen_cnt;
 162                 rte_rwlock_read_unlock(&list->lock);
 163         }
 164         /* 3. Prepare new entry for global list and for cache. */
 165         entry = list->cb_create(list->ctx, ctx);
 166         if (unlikely(!entry))
 167                 return NULL;
 168         entry->ref_cnt = 1u;
 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);
 175                 return entry;
 176         }
 177         local_entry = list->cb_clone(list->ctx, entry, ctx);
 178         if (unlikely(!local_entry)) {
 179                 list->cb_remove(list->ctx, entry);
 180                 return NULL;
 181         }
 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,
 189                                                                RTE_MAX_LCORE,
 190                                                                ctx, true);
 191
 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->ctx, entry);
 196                         list->cb_clone_free(list->ctx, local_entry);
 197                         return mlx5_list_cache_insert(list, lcore_index, oentry,
 198                                                       ctx);
 199                 }
 200         }
 201         /* 5. Update lists. */
 202         LIST_INSERT_HEAD(&list->cache[RTE_MAX_LCORE].h, entry, next);
 203         list->gen_cnt++;
 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);
 209         return local_entry;
 210 }
 211
 212 int
 213 mlx5_list_unregister(struct mlx5_list *list,
 214                       struct mlx5_list_entry *entry)
 215 {
 216         struct mlx5_list_entry *gentry = entry->gentry;
 217         int lcore_idx;
 218
 219         if (__atomic_sub_fetch(&entry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
 220                 return 1;
 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->ctx, entry);
 227                 else
 228                         list->cb_remove(list->ctx, entry);
 229         } else if (likely(lcore_idx != -1)) {
 230                 __atomic_add_fetch(&list->cache[entry->lcore_idx].inv_cnt, 1,
 231                                    __ATOMIC_RELAXED);
 232         } else {
 233                 return 0;
 234         }
 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);
 239                 return 0;
 240         }
 241         if (__atomic_sub_fetch(&gentry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
 242                 return 1;
 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->ctx, 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);
 251                 return 0;
 252         }
 253         rte_rwlock_write_unlock(&list->lock);
 254         return 1;
 255 }
 256
 257 void
 258 mlx5_list_destroy(struct mlx5_list *list)
 259 {
 260         struct mlx5_list_entry *entry;
 261         int i;
 262
 263         MLX5_ASSERT(list);
 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,
 272                                         (void *)entry);
 273                         } else {
 274                                 list->cb_clone_free(list, entry);
 275                         }
 276                 }
 277         }
 278         mlx5_free(list);
 279 }
 280
 281 uint32_t
 282 mlx5_list_get_entry_num(struct mlx5_list *list)
 283 {
 284         MLX5_ASSERT(list);
 285         return __atomic_load_n(&list->count, __ATOMIC_RELAXED);
 286 }
 287
 288 /********************* Hash List **********************/
 289
 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)
 293 {
 294         return mlx5_malloc(MLX5_MEM_ZERO, h->entry_sz, 0, SOCKET_ID_ANY);
 295 }
 296
 297 static void
 298 mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused,
 299                              struct mlx5_hlist_entry *entry)
 300 {
 301         mlx5_free(entry);
 302 }
 303
 304 struct mlx5_hlist *
 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)
 308 {
 309         struct mlx5_hlist *h;
 310         uint32_t act_size;
 311         uint32_t alloc_size;
 312         uint32_t i;
 313
 314         if (!size || !cb_match || (!cb_create ^ !cb_remove))
 315                 return NULL;
 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);
 321         } else {
 322                 act_size = size;
 323         }
 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,
 328                         SOCKET_ID_ANY);
 329         if (!h) {
 330                 DRV_LOG(ERR, "No memory for hash list %s creation",
 331                         name ? name : "None");
 332                 return NULL;
 333         }
 334         if (name)
 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.",
 347                 h->name, act_size);
 348         return h;
 349 }
 350
 351 static struct mlx5_hlist_entry *
 352 __hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
 353                void *ctx, bool reuse)
 354 {
 355         struct mlx5_hlist_head *first;
 356         struct mlx5_hlist_entry *node;
 357
 358         MLX5_ASSERT(h);
 359         first = &h->buckets[idx].head;
 360         LIST_FOREACH(node, first, next) {
 361                 if (!h->cb_match(h, node, key, ctx)) {
 362                         if (reuse) {
 363                                 __atomic_add_fetch(&node->ref_cnt, 1,
 364                                                    __ATOMIC_RELAXED);
 365                                 DRV_LOG(DEBUG, "Hash list %s entry %p "
 366                                         "reuse: %u.",
 367                                         h->name, (void *)node, node->ref_cnt);
 368                         }
 369                         break;
 370                 }
 371         }
 372         return node;
 373 }
 374
 375 static struct mlx5_hlist_entry *
 376 hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
 377              void *ctx, bool reuse)
 378 {
 379         struct mlx5_hlist_entry *node;
 380
 381         MLX5_ASSERT(h);
 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);
 385         return node;
 386 }
 387
 388 struct mlx5_hlist_entry *
 389 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
 390 {
 391         uint32_t idx;
 392
 393         if (h->direct_key)
 394                 idx = (uint32_t)(key & h->mask);
 395         else
 396                 idx = rte_hash_crc_8byte(key, 0) & h->mask;
 397         return hlist_lookup(h, key, idx, ctx, false);
 398 }
 399
 400 struct mlx5_hlist_entry*
 401 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 402 {
 403         uint32_t idx;
 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;
 408
 409         if (h->direct_key)
 410                 idx = (uint32_t)(key & h->mask);
 411         else
 412                 idx = rte_hash_crc_8byte(key, 0) & h->mask;
 413         MLX5_ASSERT(h);
 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);
 419                 if (entry)
 420                         return entry;
 421         }
 422         rte_rwlock_write_lock(&b->lock);
 423         /* Check if the list changed by other threads. */
 424         if (h->write_most ||
 425             prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
 426                 entry = __hlist_lookup(h, key, idx, ctx, true);
 427                 if (entry)
 428                         goto done;
 429         }
 430         first = &b->head;
 431         entry = h->cb_create(h, key, ctx);
 432         if (!entry) {
 433                 rte_errno = ENOMEM;
 434                 DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
 435                 goto done;
 436         }
 437         entry->idx = idx;
 438         entry->ref_cnt = 1;
 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);
 443 done:
 444         rte_rwlock_write_unlock(&b->lock);
 445         return entry;
 446 }
 447
 448 int
 449 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 450 {
 451         uint32_t idx = entry->idx;
 452
 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);
 459                 return 1;
 460         }
 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);
 468         return 0;
 469 }
 470
 471 void
 472 mlx5_hlist_destroy(struct mlx5_hlist *h)
 473 {
 474         uint32_t idx;
 475         struct mlx5_hlist_entry *entry;
 476
 477         MLX5_ASSERT(h);
 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);
 483                         /*
 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
 489                          * will be used.
 490                          */
 491                         h->cb_remove(h, entry);
 492                 }
 493         }
 494         mlx5_free(h);
 495 }