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