1 /** 2 * BSD LICENSE 3 * 4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include <stdint.h> 35 #include <stdio.h> 36 #include <stdarg.h> 37 #include <string.h> 38 #include <errno.h> 39 40 #include <sys/queue.h> 41 #include <rte_memory.h> 42 #include <rte_eal.h> 43 #include <rte_eal_memconfig.h> 44 #include <rte_malloc.h> 45 #include <rte_common.h> 46 #include <rte_per_lcore.h> 47 #include <rte_errno.h> 48 #include <rte_string_fns.h> 49 #include <rte_cpuflags.h> 50 #include <rte_log.h> 51 #include <rte_spinlock.h> 52 53 #include "rte_fbk_hash.h" 54 55 TAILQ_HEAD(rte_fbk_hash_list, rte_tailq_entry); 56 57 static struct rte_tailq_elem rte_fbk_hash_tailq = { 58 .name = "RTE_FBK_HASH", 59 }; 60 EAL_REGISTER_TAILQ(rte_fbk_hash_tailq) 61 62 /** 63 * Performs a lookup for an existing hash table, and returns a pointer to 64 * the table if found. 65 * 66 * @param name 67 * Name of the hash table to find 68 * 69 * @return 70 * pointer to hash table structure or NULL on error. 71 */ 72 struct rte_fbk_hash_table * 73 rte_fbk_hash_find_existing(const char *name) 74 { 75 struct rte_fbk_hash_table *h = NULL; 76 struct rte_tailq_entry *te; 77 struct rte_fbk_hash_list *fbk_hash_list; 78 79 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head, 80 rte_fbk_hash_list); 81 82 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); 83 TAILQ_FOREACH(te, fbk_hash_list, next) { 84 h = (struct rte_fbk_hash_table *) te->data; 85 if (strncmp(name, h->name, RTE_FBK_HASH_NAMESIZE) == 0) 86 break; 87 } 88 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); 89 if (te == NULL) { 90 rte_errno = ENOENT; 91 return NULL; 92 } 93 return h; 94 } 95 96 /** 97 * Create a new hash table for use with four byte keys. 98 * 99 * @param params 100 * Parameters used in creation of hash table. 101 * 102 * @return 103 * Pointer to hash table structure that is used in future hash table 104 * operations, or NULL on error. 105 */ 106 struct rte_fbk_hash_table * 107 rte_fbk_hash_create(const struct rte_fbk_hash_params *params) 108 { 109 struct rte_fbk_hash_table *ht = NULL; 110 struct rte_tailq_entry *te; 111 char hash_name[RTE_FBK_HASH_NAMESIZE]; 112 const uint32_t mem_size = 113 sizeof(*ht) + (sizeof(ht->t[0]) * params->entries); 114 uint32_t i; 115 struct rte_fbk_hash_list *fbk_hash_list; 116 117 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head, 118 rte_fbk_hash_list); 119 120 /* Error checking of parameters. */ 121 if ((!rte_is_power_of_2(params->entries)) || 122 (!rte_is_power_of_2(params->entries_per_bucket)) || 123 (params->entries == 0) || 124 (params->entries_per_bucket == 0) || 125 (params->entries_per_bucket > params->entries) || 126 (params->entries > RTE_FBK_HASH_ENTRIES_MAX) || 127 (params->entries_per_bucket > RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX)){ 128 rte_errno = EINVAL; 129 return NULL; 130 } 131 132 snprintf(hash_name, sizeof(hash_name), "FBK_%s", params->name); 133 134 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); 135 136 /* guarantee there's no existing */ 137 TAILQ_FOREACH(te, fbk_hash_list, next) { 138 ht = (struct rte_fbk_hash_table *) te->data; 139 if (strncmp(params->name, ht->name, RTE_FBK_HASH_NAMESIZE) == 0) 140 break; 141 } 142 ht = NULL; 143 if (te != NULL) { 144 rte_errno = EEXIST; 145 goto exit; 146 } 147 148 te = rte_zmalloc("FBK_HASH_TAILQ_ENTRY", sizeof(*te), 0); 149 if (te == NULL) { 150 RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); 151 goto exit; 152 } 153 154 /* Allocate memory for table. */ 155 ht = (struct rte_fbk_hash_table *)rte_zmalloc_socket(hash_name, mem_size, 156 0, params->socket_id); 157 if (ht == NULL) { 158 RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n"); 159 rte_free(te); 160 goto exit; 161 } 162 163 /* Set up hash table context. */ 164 snprintf(ht->name, sizeof(ht->name), "%s", params->name); 165 ht->entries = params->entries; 166 ht->entries_per_bucket = params->entries_per_bucket; 167 ht->used_entries = 0; 168 ht->bucket_mask = (params->entries / params->entries_per_bucket) - 1; 169 for (ht->bucket_shift = 0, i = 1; 170 (params->entries_per_bucket & i) == 0; 171 ht->bucket_shift++, i <<= 1) 172 ; /* empty loop body */ 173 174 if (params->hash_func != NULL) { 175 ht->hash_func = params->hash_func; 176 ht->init_val = params->init_val; 177 } 178 else { 179 ht->hash_func = RTE_FBK_HASH_FUNC_DEFAULT; 180 ht->init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT; 181 } 182 183 te->data = (void *) ht; 184 185 TAILQ_INSERT_TAIL(fbk_hash_list, te, next); 186 187 exit: 188 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 189 190 return ht; 191 } 192 193 /** 194 * Free all memory used by a hash table. 195 * 196 * @param ht 197 * Hash table to deallocate. 198 */ 199 void 200 rte_fbk_hash_free(struct rte_fbk_hash_table *ht) 201 { 202 struct rte_tailq_entry *te; 203 struct rte_fbk_hash_list *fbk_hash_list; 204 205 if (ht == NULL) 206 return; 207 208 fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head, 209 rte_fbk_hash_list); 210 211 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); 212 213 /* find out tailq entry */ 214 TAILQ_FOREACH(te, fbk_hash_list, next) { 215 if (te->data == (void *) ht) 216 break; 217 } 218 219 if (te == NULL) { 220 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 221 return; 222 } 223 224 TAILQ_REMOVE(fbk_hash_list, te, next); 225 226 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 227 228 rte_free(ht); 229 rte_free(te); 230 } 231