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 <string.h> 8 #include <errno.h> 9 #include <sys/queue.h> 10 11 #include <rte_cpuflags.h> 12 #include <rte_eal_memconfig.h> 13 #include <rte_malloc.h> 14 #include <rte_common.h> 15 #include <rte_errno.h> 16 #include <rte_string_fns.h> 17 #include <rte_log.h> 18 #include <rte_tailq.h> 19 20 #include "rte_fbk_hash.h" 21 22 RTE_LOG_REGISTER_SUFFIX(fbk_hash_logtype, fbk, INFO); 23 #define RTE_LOGTYPE_HASH fbk_hash_logtype 24 #define HASH_LOG(level, ...) \ 25 RTE_LOG_LINE(level, HASH, "" __VA_ARGS__) 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 HASH_LOG(ERR, "Failed to allocate tailq entry"); 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 HASH_LOG(ERR, "Failed to allocate fbk hash table"); 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 } 212