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