hash/rte_fbk_hash.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4
   5 #include <stdint.h>
   6 #include <stdio.h>
   7 #include <stdarg.h>
   8 #include <string.h>
   9 #include <errno.h>
  10
  11 #include <sys/queue.h>
  12 #include <rte_memory.h>
  13 #include <rte_eal.h>
  14 #include <rte_eal_memconfig.h>
  15 #include <rte_malloc.h>
  16 #include <rte_common.h>
  17 #include <rte_per_lcore.h>
  18 #include <rte_errno.h>
  19 #include <rte_string_fns.h>
  20 #include <rte_cpuflags.h>
  21 #include <rte_log.h>
  22 #include <rte_spinlock.h>
  23 #include <rte_tailq.h>
  24
  25 #include "rte_fbk_hash.h"
  26
  27 TAILQ_HEAD(rte_fbk_hash_list, rte_tailq_entry);
  28
  29 static struct rte_tailq_elem rte_fbk_hash_tailq = {
  30         .name = "RTE_FBK_HASH",
  31 };
  32 EAL_REGISTER_TAILQ(rte_fbk_hash_tailq)
  33
  34 /**
  35  * Performs a lookup for an existing hash table, and returns a pointer to
  36  * the table if found.
  37  *
  38  * @param name
  39  *   Name of the hash table to find
  40  *
  41  * @return
  42  *   pointer to hash table structure or NULL on error.
  43  */
  44 struct rte_fbk_hash_table *
  45 rte_fbk_hash_find_existing(const char *name)
  46 {
  47         struct rte_fbk_hash_table *h = NULL;
  48         struct rte_tailq_entry *te;
  49         struct rte_fbk_hash_list *fbk_hash_list;
  50
  51         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
  52                                        rte_fbk_hash_list);
  53
  54         rte_mcfg_tailq_read_lock();
  55         TAILQ_FOREACH(te, fbk_hash_list, next) {
  56                 h = (struct rte_fbk_hash_table *) te->data;
  57                 if (strncmp(name, h->name, RTE_FBK_HASH_NAMESIZE) == 0)
  58                         break;
  59         }
  60         rte_mcfg_tailq_read_unlock();
  61         if (te == NULL) {
  62                 rte_errno = ENOENT;
  63                 return NULL;
  64         }
  65         return h;
  66 }
  67
  68 /**
  69  * Create a new hash table for use with four byte keys.
  70  *
  71  * @param params
  72  *   Parameters used in creation of hash table.
  73  *
  74  * @return
  75  *   Pointer to hash table structure that is used in future hash table
  76  *   operations, or NULL on error.
  77  */
  78 struct rte_fbk_hash_table *
  79 rte_fbk_hash_create(const struct rte_fbk_hash_params *params)
  80 {
  81         struct rte_fbk_hash_table *ht = NULL;
  82         struct rte_tailq_entry *te;
  83         char hash_name[RTE_FBK_HASH_NAMESIZE];
  84         const uint32_t mem_size =
  85                         sizeof(*ht) + (sizeof(ht->t[0]) * params->entries);
  86         uint32_t i;
  87         struct rte_fbk_hash_list *fbk_hash_list;
  88         rte_fbk_hash_fn default_hash_func = (rte_fbk_hash_fn)rte_jhash_1word;
  89
  90         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
  91                                        rte_fbk_hash_list);
  92
  93         /* Error checking of parameters. */
  94         if ((!rte_is_power_of_2(params->entries)) ||
  95                         (!rte_is_power_of_2(params->entries_per_bucket)) ||
  96                         (params->entries == 0) ||
  97                         (params->entries_per_bucket == 0) ||
  98                         (params->entries_per_bucket > params->entries) ||
  99                         (params->entries > RTE_FBK_HASH_ENTRIES_MAX) ||
 100                         (params->entries_per_bucket > RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX)){
 101                 rte_errno = EINVAL;
 102                 return NULL;
 103         }
 104
 105         snprintf(hash_name, sizeof(hash_name), "FBK_%s", params->name);
 106
 107         rte_mcfg_tailq_write_lock();
 108
 109         /* guarantee there's no existing */
 110         TAILQ_FOREACH(te, fbk_hash_list, next) {
 111                 ht = (struct rte_fbk_hash_table *) te->data;
 112                 if (strncmp(params->name, ht->name, RTE_FBK_HASH_NAMESIZE) == 0)
 113                         break;
 114         }
 115         ht = NULL;
 116         if (te != NULL) {
 117                 rte_errno = EEXIST;
 118                 goto exit;
 119         }
 120
 121         te = rte_zmalloc("FBK_HASH_TAILQ_ENTRY", sizeof(*te), 0);
 122         if (te == NULL) {
 123                 RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n");
 124                 goto exit;
 125         }
 126
 127         /* Allocate memory for table. */
 128         ht = rte_zmalloc_socket(hash_name, mem_size,
 129                         0, params->socket_id);
 130         if (ht == NULL) {
 131                 RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n");
 132                 rte_free(te);
 133                 goto exit;
 134         }
 135
 136         /* Default hash function */
 137 #if defined(RTE_ARCH_X86)
 138         default_hash_func = (rte_fbk_hash_fn)rte_hash_crc_4byte;
 139 #elif defined(RTE_ARCH_ARM64)
 140         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
 141                 default_hash_func = (rte_fbk_hash_fn)rte_hash_crc_4byte;
 142 #endif
 143
 144         /* Set up hash table context. */
 145         strlcpy(ht->name, params->name, sizeof(ht->name));
 146         ht->entries = params->entries;
 147         ht->entries_per_bucket = params->entries_per_bucket;
 148         ht->used_entries = 0;
 149         ht->bucket_mask = (params->entries / params->entries_per_bucket) - 1;
 150         for (ht->bucket_shift = 0, i = 1;
 151             (params->entries_per_bucket & i) == 0;
 152             ht->bucket_shift++, i <<= 1)
 153                 ; /* empty loop body */
 154
 155         if (params->hash_func != NULL) {
 156                 ht->hash_func = params->hash_func;
 157                 ht->init_val = params->init_val;
 158         }
 159         else {
 160                 ht->hash_func = default_hash_func;
 161                 ht->init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT;
 162         }
 163
 164         te->data = (void *) ht;
 165
 166         TAILQ_INSERT_TAIL(fbk_hash_list, te, next);
 167
 168 exit:
 169         rte_mcfg_tailq_write_unlock();
 170
 171         return ht;
 172 }
 173
 174 /**
 175  * Free all memory used by a hash table.
 176  *
 177  * @param ht
 178  *   Hash table to deallocate.
 179  */
 180 void
 181 rte_fbk_hash_free(struct rte_fbk_hash_table *ht)
 182 {
 183         struct rte_tailq_entry *te;
 184         struct rte_fbk_hash_list *fbk_hash_list;
 185
 186         if (ht == NULL)
 187                 return;
 188
 189         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
 190                                        rte_fbk_hash_list);
 191
 192         rte_mcfg_tailq_write_lock();
 193
 194         /* find out tailq entry */
 195         TAILQ_FOREACH(te, fbk_hash_list, next) {
 196                 if (te->data == (void *) ht)
 197                         break;
 198         }
 199
 200         if (te == NULL) {
 201                 rte_mcfg_tailq_write_unlock();
 202                 return;
 203         }
 204
 205         TAILQ_REMOVE(fbk_hash_list, te, next);
 206
 207         rte_mcfg_tailq_write_unlock();
 208
 209         rte_free(ht);
 210         rte_free(te);
 211 }