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 #ifndef _RTE_FBK_HASH_H_ 35 #define _RTE_FBK_HASH_H_ 36 37 /** 38 * @file 39 * 40 * This is a hash table implementation for four byte keys (fbk). 41 * 42 * Note that the return value of the add function should always be checked as, 43 * if a bucket is full, the key is not added even if there is space in other 44 * buckets. This keeps the lookup function very simple and therefore fast. 45 */ 46 47 #include <stdint.h> 48 #include <errno.h> 49 #include <sys/queue.h> 50 51 #ifdef __cplusplus 52 extern "C" { 53 #endif 54 55 #include <string.h> 56 57 #include <rte_config.h> 58 #ifndef RTE_FBK_HASH_FUNC_DEFAULT 59 #if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32) 60 #include <rte_hash_crc.h> 61 /** Default four-byte key hash function if none is specified. */ 62 #define RTE_FBK_HASH_FUNC_DEFAULT rte_hash_crc_4byte 63 #else 64 #include <rte_jhash.h> 65 #define RTE_FBK_HASH_FUNC_DEFAULT rte_jhash_1word 66 #endif 67 #endif 68 69 #ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT 70 /** Initialising value used when calculating hash. */ 71 #define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF 72 #endif 73 74 /** The maximum number of entries in the hash table that is supported. */ 75 #define RTE_FBK_HASH_ENTRIES_MAX (1 << 20) 76 77 /** The maximum number of entries in each bucket that is supported. */ 78 #define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256 79 80 /** Maximum size of string for naming the hash. */ 81 #define RTE_FBK_HASH_NAMESIZE 32 82 83 /** Type of function that can be used for calculating the hash value. */ 84 typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val); 85 86 /** Parameters used when creating four-byte key hash table. */ 87 struct rte_fbk_hash_params { 88 const char *name; /**< Name of the hash table. */ 89 uint32_t entries; /**< Total number of entries. */ 90 uint32_t entries_per_bucket; /**< Number of entries in a bucket. */ 91 int socket_id; /**< Socket to allocate memory on. */ 92 rte_fbk_hash_fn hash_func; /**< The hash function. */ 93 uint32_t init_val; /**< For initialising hash function. */ 94 }; 95 96 /** Individual entry in the four-byte key hash table. */ 97 union rte_fbk_hash_entry { 98 uint64_t whole_entry; /**< For accessing entire entry. */ 99 struct { 100 uint16_t is_entry; /**< Non-zero if entry is active. */ 101 uint16_t value; /**< Value returned by lookup. */ 102 uint32_t key; /**< Key used to find value. */ 103 } entry; /**< For accessing each entry part. */ 104 }; 105 106 107 /** The four-byte key hash table structure. */ 108 struct rte_fbk_hash_table { 109 char name[RTE_FBK_HASH_NAMESIZE]; /**< Name of the hash. */ 110 uint32_t entries; /**< Total number of entries. */ 111 uint32_t entries_per_bucket; /**< Number of entries in a bucket. */ 112 uint32_t used_entries; /**< How many entries are used. */ 113 uint32_t bucket_mask; /**< To find which bucket the key is in. */ 114 uint32_t bucket_shift; /**< Convert bucket to table offset. */ 115 rte_fbk_hash_fn hash_func; /**< The hash function. */ 116 uint32_t init_val; /**< For initialising hash function. */ 117 118 /** A flat table of all buckets. */ 119 union rte_fbk_hash_entry t[]; 120 }; 121 122 /** 123 * Find the offset into hash table of the bucket containing a particular key. 124 * 125 * @param ht 126 * Pointer to hash table. 127 * @param key 128 * Key to calculate bucket for. 129 * @return 130 * Offset into hash table. 131 */ 132 static inline uint32_t 133 rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key) 134 { 135 return (ht->hash_func(key, ht->init_val) & ht->bucket_mask) << 136 ht->bucket_shift; 137 } 138 139 /** 140 * Add a key to an existing hash table with bucket id. 141 * This operation is not multi-thread safe 142 * and should only be called from one thread. 143 * 144 * @param ht 145 * Hash table to add the key to. 146 * @param key 147 * Key to add to the hash table. 148 * @param value 149 * Value to associate with key. 150 * @param bucket 151 * Bucket to associate with key. 152 * @return 153 * 0 if ok, or negative value on error. 154 */ 155 static inline int 156 rte_fbk_hash_add_key_with_bucket(struct rte_fbk_hash_table *ht, 157 uint32_t key, uint16_t value, uint32_t bucket) 158 { 159 /* 160 * The writing of a new value to the hash table is done as a single 161 * 64bit operation. This should help prevent individual entries being 162 * corrupted due to race conditions, but it's still possible to 163 * overwrite entries that have just been made valid. 164 */ 165 const uint64_t new_entry = ((uint64_t)(key) << 32) | 166 ((uint64_t)(value) << 16) | 167 1; /* 1 = is_entry bit. */ 168 uint32_t i; 169 170 for (i = 0; i < ht->entries_per_bucket; i++) { 171 /* Set entry if unused. */ 172 if (! ht->t[bucket + i].entry.is_entry) { 173 ht->t[bucket + i].whole_entry = new_entry; 174 ht->used_entries++; 175 return 0; 176 } 177 /* Change value if key already exists. */ 178 if (ht->t[bucket + i].entry.key == key) { 179 ht->t[bucket + i].entry.value = value; 180 return 0; 181 } 182 } 183 184 return -ENOSPC; /* No space in bucket. */ 185 } 186 187 /** 188 * Add a key to an existing hash table. This operation is not multi-thread safe 189 * and should only be called from one thread. 190 * 191 * @param ht 192 * Hash table to add the key to. 193 * @param key 194 * Key to add to the hash table. 195 * @param value 196 * Value to associate with key. 197 * @return 198 * 0 if ok, or negative value on error. 199 */ 200 static inline int 201 rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, 202 uint32_t key, uint16_t value) 203 { 204 return rte_fbk_hash_add_key_with_bucket(ht, 205 key, value, rte_fbk_hash_get_bucket(ht, key)); 206 } 207 208 /** 209 * Remove a key with a given bucket id from an existing hash table. 210 * This operation is not multi-thread 211 * safe and should only be called from one thread. 212 * 213 * @param ht 214 * Hash table to remove the key from. 215 * @param key 216 * Key to remove from the hash table. 217 * @param bucket 218 * Bucket id associate with key. 219 * @return 220 * 0 if ok, or negative value on error. 221 */ 222 static inline int 223 rte_fbk_hash_delete_key_with_bucket(struct rte_fbk_hash_table *ht, 224 uint32_t key, uint32_t bucket) 225 { 226 uint32_t last_entry = ht->entries_per_bucket - 1; 227 uint32_t i, j; 228 229 for (i = 0; i < ht->entries_per_bucket; i++) { 230 if (ht->t[bucket + i].entry.key == key) { 231 /* Find last key in bucket. */ 232 for (j = ht->entries_per_bucket - 1; j > i; j-- ) { 233 if (! ht->t[bucket + j].entry.is_entry) { 234 last_entry = j - 1; 235 } 236 } 237 /* 238 * Move the last key to the deleted key's position, and 239 * delete the last key. lastEntry and i may be same but 240 * it doesn't matter. 241 */ 242 ht->t[bucket + i].whole_entry = 243 ht->t[bucket + last_entry].whole_entry; 244 ht->t[bucket + last_entry].whole_entry = 0; 245 246 ht->used_entries--; 247 return 0; 248 } 249 } 250 251 return -ENOENT; /* Key didn't exist. */ 252 } 253 254 /** 255 * Remove a key from an existing hash table. This operation is not multi-thread 256 * safe and should only be called from one thread. 257 * 258 * @param ht 259 * Hash table to remove the key from. 260 * @param key 261 * Key to remove from the hash table. 262 * @return 263 * 0 if ok, or negative value on error. 264 */ 265 static inline int 266 rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) 267 { 268 return rte_fbk_hash_delete_key_with_bucket(ht, 269 key, rte_fbk_hash_get_bucket(ht, key)); 270 } 271 272 /** 273 * Find a key in the hash table with a given bucketid. 274 * This operation is multi-thread safe. 275 * 276 * @param ht 277 * Hash table to look in. 278 * @param key 279 * Key to find. 280 * @param bucket 281 * Bucket associate to the key. 282 * @return 283 * The value that was associated with the key, or negative value on error. 284 */ 285 static inline int 286 rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, 287 uint32_t key, uint32_t bucket) 288 { 289 union rte_fbk_hash_entry current_entry; 290 uint32_t i; 291 292 for (i = 0; i < ht->entries_per_bucket; i++) { 293 /* Single read of entry, which should be atomic. */ 294 current_entry.whole_entry = ht->t[bucket + i].whole_entry; 295 if (! current_entry.entry.is_entry) { 296 return -ENOENT; /* Error once we hit an empty field. */ 297 } 298 if (current_entry.entry.key == key) { 299 return current_entry.entry.value; 300 } 301 } 302 return -ENOENT; /* Key didn't exist. */ 303 } 304 305 /** 306 * Find a key in the hash table. This operation is multi-thread safe. 307 * 308 * @param ht 309 * Hash table to look in. 310 * @param key 311 * Key to find. 312 * @return 313 * The value that was associated with the key, or negative value on error. 314 */ 315 static inline int 316 rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) 317 { 318 return rte_fbk_hash_lookup_with_bucket(ht, 319 key, rte_fbk_hash_get_bucket(ht, key)); 320 } 321 322 /** 323 * Delete all entries in a hash table. This operation is not multi-thread 324 * safe and should only be called from one thread. 325 * 326 * @param ht 327 * Hash table to delete entries in. 328 */ 329 static inline void 330 rte_fbk_hash_clear_all(struct rte_fbk_hash_table *ht) 331 { 332 memset(ht->t, 0, sizeof(ht->t[0]) * ht->entries); 333 ht->used_entries = 0; 334 } 335 336 /** 337 * Find what fraction of entries are being used. 338 * 339 * @param ht 340 * Hash table to find how many entries are being used in. 341 * @return 342 * Load factor of the hash table, or negative value on error. 343 */ 344 static inline double 345 rte_fbk_hash_get_load_factor(struct rte_fbk_hash_table *ht) 346 { 347 return (double)ht->used_entries / (double)ht->entries; 348 } 349 350 /** 351 * Performs a lookup for an existing hash table, and returns a pointer to 352 * the table if found. 353 * 354 * @param name 355 * Name of the hash table to find 356 * 357 * @return 358 * pointer to hash table structure or NULL on error with rte_errno 359 * set appropriately. Possible rte_errno values include: 360 * - ENOENT - required entry not available to return. 361 */ 362 struct rte_fbk_hash_table *rte_fbk_hash_find_existing(const char *name); 363 364 /** 365 * Create a new hash table for use with four byte keys. 366 * 367 * @param params 368 * Parameters used in creation of hash table. 369 * 370 * @return 371 * Pointer to hash table structure that is used in future hash table 372 * operations, or NULL on error with rte_errno set appropriately. 373 * Possible rte_errno error values include: 374 * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure 375 * - E_RTE_SECONDARY - function was called from a secondary process instance 376 * - EINVAL - invalid parameter value passed to function 377 * - ENOSPC - the maximum number of memzones has already been allocated 378 * - EEXIST - a memzone with the same name already exists 379 * - ENOMEM - no appropriate memory area found in which to create memzone 380 */ 381 struct rte_fbk_hash_table * \ 382 rte_fbk_hash_create(const struct rte_fbk_hash_params *params); 383 384 /** 385 * Free all memory used by a hash table. 386 * Has no effect on hash tables allocated in memory zones 387 * 388 * @param ht 389 * Hash table to deallocate. 390 */ 391 void rte_fbk_hash_free(struct rte_fbk_hash_table *ht); 392 393 #ifdef __cplusplus 394 } 395 #endif 396 397 #endif /* _RTE_FBK_HASH_H_ */ 398