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,
  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->cb_create = cb_create;
  39         list->cb_match = cb_match;
  40         list->cb_remove = cb_remove;
  41         list->cb_clone = cb_clone;
  42         list->cb_clone_free = cb_clone_free;
  43         rte_rwlock_init(&list->lock);
  44         DRV_LOG(DEBUG, "mlx5 list %s initialized.", list->name);
  45         for (i = 0; i <= RTE_MAX_LCORE; i++)
  46                 LIST_INIT(&list->cache[i].h);
  47         return list;
  48 }
  49
  50 static struct mlx5_list_entry *
  51 __list_lookup(struct mlx5_list *list, int lcore_index, void *ctx, bool reuse)
  52 {
  53         struct mlx5_list_entry *entry = LIST_FIRST(&list->cache[lcore_index].h);
  54         uint32_t ret;
  55
  56         while (entry != NULL) {
  57                 if (list->cb_match(list, entry, ctx) == 0) {
  58                         if (reuse) {
  59                                 ret = __atomic_add_fetch(&entry->ref_cnt, 1,
  60                                                          __ATOMIC_RELAXED) - 1;
  61                                 DRV_LOG(DEBUG, "mlx5 list %s entry %p ref: %u.",
  62                                         list->name, (void *)entry,
  63                                         entry->ref_cnt);
  64                         } else if (lcore_index < RTE_MAX_LCORE) {
  65                                 ret = __atomic_load_n(&entry->ref_cnt,
  66                                                       __ATOMIC_RELAXED);
  67                         }
  68                         if (likely(ret != 0 || lcore_index == RTE_MAX_LCORE))
  69                                 return entry;
  70                         if (reuse && ret == 0)
  71                                 entry->ref_cnt--; /* Invalid entry. */
  72                 }
  73                 entry = LIST_NEXT(entry, next);
  74         }
  75         return NULL;
  76 }
  77
  78 struct mlx5_list_entry *
  79 mlx5_list_lookup(struct mlx5_list *list, void *ctx)
  80 {
  81         struct mlx5_list_entry *entry = NULL;
  82         int i;
  83
  84         rte_rwlock_read_lock(&list->lock);
  85         for (i = 0; i < RTE_MAX_LCORE; i++) {
  86                 entry = __list_lookup(list, i, ctx, false);
  87                 if (entry)
  88                         break;
  89         }
  90         rte_rwlock_read_unlock(&list->lock);
  91         return entry;
  92 }
  93
  94 static struct mlx5_list_entry *
  95 mlx5_list_cache_insert(struct mlx5_list *list, int lcore_index,
  96                        struct mlx5_list_entry *gentry, void *ctx)
  97 {
  98         struct mlx5_list_entry *lentry = list->cb_clone(list, gentry, ctx);
  99
 100         if (unlikely(!lentry))
 101                 return NULL;
 102         lentry->ref_cnt = 1u;
 103         lentry->gentry = gentry;
 104         lentry->lcore_idx = (uint32_t)lcore_index;
 105         LIST_INSERT_HEAD(&list->cache[lcore_index].h, lentry, next);
 106         return lentry;
 107 }
 108
 109 static void
 110 __list_cache_clean(struct mlx5_list *list, int lcore_index)
 111 {
 112         struct mlx5_list_cache *c = &list->cache[lcore_index];
 113         struct mlx5_list_entry *entry = LIST_FIRST(&c->h);
 114         uint32_t inv_cnt = __atomic_exchange_n(&c->inv_cnt, 0,
 115                                                __ATOMIC_RELAXED);
 116
 117         while (inv_cnt != 0 && entry != NULL) {
 118                 struct mlx5_list_entry *nentry = LIST_NEXT(entry, next);
 119
 120                 if (__atomic_load_n(&entry->ref_cnt, __ATOMIC_RELAXED) == 0) {
 121                         LIST_REMOVE(entry, next);
 122                         list->cb_clone_free(list, entry);
 123                         inv_cnt--;
 124                 }
 125                 entry = nentry;
 126         }
 127 }
 128
 129 struct mlx5_list_entry *
 130 mlx5_list_register(struct mlx5_list *list, void *ctx)
 131 {
 132         struct mlx5_list_entry *entry, *local_entry;
 133         volatile uint32_t prev_gen_cnt = 0;
 134         int lcore_index = rte_lcore_index(rte_lcore_id());
 135
 136         MLX5_ASSERT(list);
 137         MLX5_ASSERT(lcore_index < RTE_MAX_LCORE);
 138         if (unlikely(lcore_index == -1)) {
 139                 rte_errno = ENOTSUP;
 140                 return NULL;
 141         }
 142         /* 0. Free entries that was invalidated by other lcores. */
 143         __list_cache_clean(list, lcore_index);
 144         /* 1. Lookup in local cache. */
 145         local_entry = __list_lookup(list, lcore_index, ctx, true);
 146         if (local_entry)
 147                 return local_entry;
 148         /* 2. Lookup with read lock on global list, reuse if found. */
 149         rte_rwlock_read_lock(&list->lock);
 150         entry = __list_lookup(list, RTE_MAX_LCORE, ctx, true);
 151         if (likely(entry)) {
 152                 rte_rwlock_read_unlock(&list->lock);
 153                 return mlx5_list_cache_insert(list, lcore_index, entry, ctx);
 154         }
 155         prev_gen_cnt = list->gen_cnt;
 156         rte_rwlock_read_unlock(&list->lock);
 157         /* 3. Prepare new entry for global list and for cache. */
 158         entry = list->cb_create(list, entry, ctx);
 159         if (unlikely(!entry))
 160                 return NULL;
 161         local_entry = list->cb_clone(list, entry, ctx);
 162         if (unlikely(!local_entry)) {
 163                 list->cb_remove(list, entry);
 164                 return NULL;
 165         }
 166         entry->ref_cnt = 1u;
 167         local_entry->ref_cnt = 1u;
 168         local_entry->gentry = entry;
 169         local_entry->lcore_idx = (uint32_t)lcore_index;
 170         rte_rwlock_write_lock(&list->lock);
 171         /* 4. Make sure the same entry was not created before the write lock. */
 172         if (unlikely(prev_gen_cnt != list->gen_cnt)) {
 173                 struct mlx5_list_entry *oentry = __list_lookup(list,
 174                                                                RTE_MAX_LCORE,
 175                                                                ctx, true);
 176
 177                 if (unlikely(oentry)) {
 178                         /* 4.5. Found real race!!, reuse the old entry. */
 179                         rte_rwlock_write_unlock(&list->lock);
 180                         list->cb_remove(list, entry);
 181                         list->cb_clone_free(list, local_entry);
 182                         return mlx5_list_cache_insert(list, lcore_index, oentry,
 183                                                       ctx);
 184                 }
 185         }
 186         /* 5. Update lists. */
 187         LIST_INSERT_HEAD(&list->cache[RTE_MAX_LCORE].h, entry, next);
 188         list->gen_cnt++;
 189         rte_rwlock_write_unlock(&list->lock);
 190         LIST_INSERT_HEAD(&list->cache[lcore_index].h, local_entry, next);
 191         __atomic_add_fetch(&list->count, 1, __ATOMIC_RELAXED);
 192         DRV_LOG(DEBUG, "mlx5 list %s entry %p new: %u.", list->name,
 193                 (void *)entry, entry->ref_cnt);
 194         return local_entry;
 195 }
 196
 197 int
 198 mlx5_list_unregister(struct mlx5_list *list,
 199                       struct mlx5_list_entry *entry)
 200 {
 201         struct mlx5_list_entry *gentry = entry->gentry;
 202         int lcore_idx;
 203
 204         if (__atomic_sub_fetch(&entry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
 205                 return 1;
 206         lcore_idx = rte_lcore_index(rte_lcore_id());
 207         MLX5_ASSERT(lcore_idx < RTE_MAX_LCORE);
 208         if (entry->lcore_idx == (uint32_t)lcore_idx) {
 209                 LIST_REMOVE(entry, next);
 210                 list->cb_clone_free(list, entry);
 211         } else if (likely(lcore_idx != -1)) {
 212                 __atomic_add_fetch(&list->cache[entry->lcore_idx].inv_cnt, 1,
 213                                    __ATOMIC_RELAXED);
 214         } else {
 215                 return 0;
 216         }
 217         if (__atomic_sub_fetch(&gentry->ref_cnt, 1, __ATOMIC_RELAXED) != 0)
 218                 return 1;
 219         rte_rwlock_write_lock(&list->lock);
 220         if (likely(gentry->ref_cnt == 0)) {
 221                 LIST_REMOVE(gentry, next);
 222                 rte_rwlock_write_unlock(&list->lock);
 223                 list->cb_remove(list, gentry);
 224                 __atomic_sub_fetch(&list->count, 1, __ATOMIC_RELAXED);
 225                 DRV_LOG(DEBUG, "mlx5 list %s entry %p removed.",
 226                         list->name, (void *)gentry);
 227                 return 0;
 228         }
 229         rte_rwlock_write_unlock(&list->lock);
 230         return 1;
 231 }
 232
 233 void
 234 mlx5_list_destroy(struct mlx5_list *list)
 235 {
 236         struct mlx5_list_entry *entry;
 237         int i;
 238
 239         MLX5_ASSERT(list);
 240         for (i = 0; i <= RTE_MAX_LCORE; i++) {
 241                 while (!LIST_EMPTY(&list->cache[i].h)) {
 242                         entry = LIST_FIRST(&list->cache[i].h);
 243                         LIST_REMOVE(entry, next);
 244                         if (i == RTE_MAX_LCORE) {
 245                                 list->cb_remove(list, entry);
 246                                 DRV_LOG(DEBUG, "mlx5 list %s entry %p "
 247                                         "destroyed.", list->name,
 248                                         (void *)entry);
 249                         } else {
 250                                 list->cb_clone_free(list, entry);
 251                         }
 252                 }
 253         }
 254         mlx5_free(list);
 255 }
 256
 257 uint32_t
 258 mlx5_list_get_entry_num(struct mlx5_list *list)
 259 {
 260         MLX5_ASSERT(list);
 261         return __atomic_load_n(&list->count, __ATOMIC_RELAXED);
 262 }
 263
 264 /********************* Hash List **********************/
 265
 266 static struct mlx5_hlist_entry *
 267 mlx5_hlist_default_create_cb(struct mlx5_hlist *h, uint64_t key __rte_unused,
 268                              void *ctx __rte_unused)
 269 {
 270         return mlx5_malloc(MLX5_MEM_ZERO, h->entry_sz, 0, SOCKET_ID_ANY);
 271 }
 272
 273 static void
 274 mlx5_hlist_default_remove_cb(struct mlx5_hlist *h __rte_unused,
 275                              struct mlx5_hlist_entry *entry)
 276 {
 277         mlx5_free(entry);
 278 }
 279
 280 struct mlx5_hlist *
 281 mlx5_hlist_create(const char *name, uint32_t size, uint32_t entry_size,
 282                   uint32_t flags, mlx5_hlist_create_cb cb_create,
 283                   mlx5_hlist_match_cb cb_match, mlx5_hlist_remove_cb cb_remove)
 284 {
 285         struct mlx5_hlist *h;
 286         uint32_t act_size;
 287         uint32_t alloc_size;
 288         uint32_t i;
 289
 290         if (!size || !cb_match || (!cb_create ^ !cb_remove))
 291                 return NULL;
 292         /* Align to the next power of 2, 32bits integer is enough now. */
 293         if (!rte_is_power_of_2(size)) {
 294                 act_size = rte_align32pow2(size);
 295                 DRV_LOG(DEBUG, "Size 0x%" PRIX32 " is not power of 2, "
 296                         "will be aligned to 0x%" PRIX32 ".", size, act_size);
 297         } else {
 298                 act_size = size;
 299         }
 300         alloc_size = sizeof(struct mlx5_hlist) +
 301                      sizeof(struct mlx5_hlist_bucket) * act_size;
 302         /* Using zmalloc, then no need to initialize the heads. */
 303         h = mlx5_malloc(MLX5_MEM_ZERO, alloc_size, RTE_CACHE_LINE_SIZE,
 304                         SOCKET_ID_ANY);
 305         if (!h) {
 306                 DRV_LOG(ERR, "No memory for hash list %s creation",
 307                         name ? name : "None");
 308                 return NULL;
 309         }
 310         if (name)
 311                 snprintf(h->name, MLX5_HLIST_NAMESIZE, "%s", name);
 312         h->table_sz = act_size;
 313         h->mask = act_size - 1;
 314         h->entry_sz = entry_size;
 315         h->direct_key = !!(flags & MLX5_HLIST_DIRECT_KEY);
 316         h->write_most = !!(flags & MLX5_HLIST_WRITE_MOST);
 317         h->cb_create = cb_create ? cb_create : mlx5_hlist_default_create_cb;
 318         h->cb_match = cb_match;
 319         h->cb_remove = cb_remove ? cb_remove : mlx5_hlist_default_remove_cb;
 320         for (i = 0; i < act_size; i++)
 321                 rte_rwlock_init(&h->buckets[i].lock);
 322         DRV_LOG(DEBUG, "Hash list with %s size 0x%" PRIX32 " is created.",
 323                 h->name, act_size);
 324         return h;
 325 }
 326
 327 static struct mlx5_hlist_entry *
 328 __hlist_lookup(struct mlx5_hlist *h, uint64_t key, uint32_t idx,
 329                void *ctx, bool reuse)
 330 {
 331         struct mlx5_hlist_head *first;
 332         struct mlx5_hlist_entry *node;
 333
 334         MLX5_ASSERT(h);
 335         first = &h->buckets[idx].head;
 336         LIST_FOREACH(node, first, next) {
 337                 if (!h->cb_match(h, node, key, ctx)) {
 338                         if (reuse) {
 339                                 __atomic_add_fetch(&node->ref_cnt, 1,
 340                                                    __ATOMIC_RELAXED);
 341                                 DRV_LOG(DEBUG, "Hash list %s entry %p "
 342                                         "reuse: %u.",
 343                                         h->name, (void *)node, node->ref_cnt);
 344                         }
 345                         break;
 346                 }
 347         }
 348         return node;
 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_entry *node;
 356
 357         MLX5_ASSERT(h);
 358         rte_rwlock_read_lock(&h->buckets[idx].lock);
 359         node = __hlist_lookup(h, key, idx, ctx, reuse);
 360         rte_rwlock_read_unlock(&h->buckets[idx].lock);
 361         return node;
 362 }
 363
 364 struct mlx5_hlist_entry *
 365 mlx5_hlist_lookup(struct mlx5_hlist *h, uint64_t key, void *ctx)
 366 {
 367         uint32_t idx;
 368
 369         if (h->direct_key)
 370                 idx = (uint32_t)(key & h->mask);
 371         else
 372                 idx = rte_hash_crc_8byte(key, 0) & h->mask;
 373         return hlist_lookup(h, key, idx, ctx, false);
 374 }
 375
 376 struct mlx5_hlist_entry*
 377 mlx5_hlist_register(struct mlx5_hlist *h, uint64_t key, void *ctx)
 378 {
 379         uint32_t idx;
 380         struct mlx5_hlist_head *first;
 381         struct mlx5_hlist_bucket *b;
 382         struct mlx5_hlist_entry *entry;
 383         uint32_t prev_gen_cnt = 0;
 384
 385         if (h->direct_key)
 386                 idx = (uint32_t)(key & h->mask);
 387         else
 388                 idx = rte_hash_crc_8byte(key, 0) & h->mask;
 389         MLX5_ASSERT(h);
 390         b = &h->buckets[idx];
 391         /* Use write lock directly for write-most list. */
 392         if (!h->write_most) {
 393                 prev_gen_cnt = __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE);
 394                 entry = hlist_lookup(h, key, idx, ctx, true);
 395                 if (entry)
 396                         return entry;
 397         }
 398         rte_rwlock_write_lock(&b->lock);
 399         /* Check if the list changed by other threads. */
 400         if (h->write_most ||
 401             prev_gen_cnt != __atomic_load_n(&b->gen_cnt, __ATOMIC_ACQUIRE)) {
 402                 entry = __hlist_lookup(h, key, idx, ctx, true);
 403                 if (entry)
 404                         goto done;
 405         }
 406         first = &b->head;
 407         entry = h->cb_create(h, key, ctx);
 408         if (!entry) {
 409                 rte_errno = ENOMEM;
 410                 DRV_LOG(DEBUG, "Can't allocate hash list %s entry.", h->name);
 411                 goto done;
 412         }
 413         entry->idx = idx;
 414         entry->ref_cnt = 1;
 415         LIST_INSERT_HEAD(first, entry, next);
 416         __atomic_add_fetch(&b->gen_cnt, 1, __ATOMIC_ACQ_REL);
 417         DRV_LOG(DEBUG, "Hash list %s entry %p new: %u.",
 418                 h->name, (void *)entry, entry->ref_cnt);
 419 done:
 420         rte_rwlock_write_unlock(&b->lock);
 421         return entry;
 422 }
 423
 424 int
 425 mlx5_hlist_unregister(struct mlx5_hlist *h, struct mlx5_hlist_entry *entry)
 426 {
 427         uint32_t idx = entry->idx;
 428
 429         rte_rwlock_write_lock(&h->buckets[idx].lock);
 430         MLX5_ASSERT(entry && entry->ref_cnt && entry->next.le_prev);
 431         DRV_LOG(DEBUG, "Hash list %s entry %p deref: %u.",
 432                 h->name, (void *)entry, entry->ref_cnt);
 433         if (--entry->ref_cnt) {
 434                 rte_rwlock_write_unlock(&h->buckets[idx].lock);
 435                 return 1;
 436         }
 437         LIST_REMOVE(entry, next);
 438         /* Set to NULL to get rid of removing action for more than once. */
 439         entry->next.le_prev = NULL;
 440         h->cb_remove(h, entry);
 441         rte_rwlock_write_unlock(&h->buckets[idx].lock);
 442         DRV_LOG(DEBUG, "Hash list %s entry %p removed.",
 443                 h->name, (void *)entry);
 444         return 0;
 445 }
 446
 447 void
 448 mlx5_hlist_destroy(struct mlx5_hlist *h)
 449 {
 450         uint32_t idx;
 451         struct mlx5_hlist_entry *entry;
 452
 453         MLX5_ASSERT(h);
 454         for (idx = 0; idx < h->table_sz; ++idx) {
 455                 /* No LIST_FOREACH_SAFE, using while instead. */
 456                 while (!LIST_EMPTY(&h->buckets[idx].head)) {
 457                         entry = LIST_FIRST(&h->buckets[idx].head);
 458                         LIST_REMOVE(entry, next);
 459                         /*
 460                          * The owner of whole element which contains data entry
 461                          * is the user, so it's the user's duty to do the clean
 462                          * up and the free work because someone may not put the
 463                          * hlist entry at the beginning(suggested to locate at
 464                          * the beginning). Or else the default free function
 465                          * will be used.
 466                          */
 467                         h->cb_remove(h, entry);
 468                 }
 469         }
 470         mlx5_free(h);
 471 }