1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2016 Intel Corporation 3 * Copyright(c) 2018 Arm Limited 4 */ 5 6 /* rte_cuckoo_hash.h 7 * This file hold Cuckoo Hash private data structures to allows include from 8 * platform specific files like rte_cuckoo_hash_x86.h 9 */ 10 11 #ifndef _RTE_CUCKOO_HASH_H_ 12 #define _RTE_CUCKOO_HASH_H_ 13 14 #include <stdalign.h> 15 16 #if defined(RTE_ARCH_X86) 17 #include "rte_cmp_x86.h" 18 #endif 19 20 #if defined(RTE_ARCH_ARM64) 21 #include "rte_cmp_arm64.h" 22 #endif 23 24 /* Macro to enable/disable run-time checking of function parameters */ 25 #if defined(RTE_LIBRTE_HASH_DEBUG) 26 #define RETURN_IF_TRUE(cond, retval) do { \ 27 if (cond) \ 28 return retval; \ 29 } while (0) 30 #else 31 #define RETURN_IF_TRUE(cond, retval) 32 #endif 33 34 #include <rte_hash_crc.h> 35 #include <rte_jhash.h> 36 37 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) 38 /* 39 * All different options to select a key compare function, 40 * based on the key size and custom function. 41 */ 42 enum cmp_jump_table_case { 43 KEY_CUSTOM = 0, 44 KEY_16_BYTES, 45 KEY_32_BYTES, 46 KEY_48_BYTES, 47 KEY_64_BYTES, 48 KEY_80_BYTES, 49 KEY_96_BYTES, 50 KEY_112_BYTES, 51 KEY_128_BYTES, 52 KEY_OTHER_BYTES, 53 NUM_KEY_CMP_CASES, 54 }; 55 56 /* 57 * Table storing all different key compare functions 58 * (multi-process supported) 59 */ 60 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = { 61 NULL, 62 rte_hash_k16_cmp_eq, 63 rte_hash_k32_cmp_eq, 64 rte_hash_k48_cmp_eq, 65 rte_hash_k64_cmp_eq, 66 rte_hash_k80_cmp_eq, 67 rte_hash_k96_cmp_eq, 68 rte_hash_k112_cmp_eq, 69 rte_hash_k128_cmp_eq, 70 memcmp 71 }; 72 #else 73 /* 74 * All different options to select a key compare function, 75 * based on the key size and custom function. 76 */ 77 enum cmp_jump_table_case { 78 KEY_CUSTOM = 0, 79 KEY_OTHER_BYTES, 80 NUM_KEY_CMP_CASES, 81 }; 82 83 /* 84 * Table storing all different key compare functions 85 * (multi-process supported) 86 */ 87 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = { 88 NULL, 89 memcmp 90 }; 91 92 #endif 93 94 95 /** 96 * Number of items per bucket. 97 * 8 is a tradeoff between performance and memory consumption. 98 * When it is equal to 8, multiple 'struct rte_hash_bucket' can be fit 99 * on a single cache line (64 or 128 bytes long) without any gaps 100 * in memory between them due to alignment. 101 */ 102 #define RTE_HASH_BUCKET_ENTRIES 8 103 104 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES) 105 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2 106 #endif 107 108 #define NULL_SIGNATURE 0 109 110 #define EMPTY_SLOT 0 111 112 #define KEY_ALIGNMENT 16 113 114 #define LCORE_CACHE_SIZE 64 115 116 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000 117 118 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4 119 120 #define RTE_HASH_TSX_MAX_RETRY 10 121 122 struct __rte_cache_aligned lcore_cache { 123 unsigned len; /**< Cache len */ 124 uint32_t objs[LCORE_CACHE_SIZE]; /**< Cache objects */ 125 }; 126 127 /* Structure that stores key-value pair */ 128 struct rte_hash_key { 129 union { 130 uintptr_t idata; 131 RTE_ATOMIC(void *) pdata; 132 }; 133 /* Variable key size */ 134 char key[0]; 135 }; 136 137 /** Bucket structure */ 138 struct __rte_cache_aligned rte_hash_bucket { 139 uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES]; 140 141 RTE_ATOMIC(uint32_t) key_idx[RTE_HASH_BUCKET_ENTRIES]; 142 143 uint8_t flag[RTE_HASH_BUCKET_ENTRIES]; 144 145 void *next; 146 }; 147 148 /** A hash table structure. */ 149 struct __rte_cache_aligned rte_hash { 150 char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ 151 uint32_t entries; /**< Total table entries. */ 152 uint32_t num_buckets; /**< Number of buckets in table. */ 153 154 struct rte_ring *free_slots; 155 /**< Ring that stores all indexes of the free slots in the key table */ 156 157 struct lcore_cache *local_free_slots; 158 /**< Local cache per lcore, storing some indexes of the free slots */ 159 160 /* RCU config */ 161 struct rte_hash_rcu_config *hash_rcu_cfg; 162 /**< HASH RCU QSBR configuration structure */ 163 struct rte_rcu_qsbr_dq *dq; /**< RCU QSBR defer queue. */ 164 165 /* Fields used in lookup */ 166 167 alignas(RTE_CACHE_LINE_SIZE) uint32_t key_len; 168 /**< Length of hash key. */ 169 uint8_t hw_trans_mem_support; 170 /**< If hardware transactional memory is used. */ 171 uint8_t use_local_cache; 172 /**< If multi-writer support is enabled, use local cache 173 * to allocate key-store slots. 174 */ 175 uint8_t readwrite_concur_support; 176 /**< If read-write concurrency support is enabled */ 177 uint8_t ext_table_support; /**< Enable extendable bucket table */ 178 uint8_t no_free_on_del; 179 /**< If key index should be freed on calling rte_hash_del_xxx APIs. 180 * If this is set, rte_hash_free_key_with_position must be called to 181 * free the key index associated with the deleted entry. 182 * This flag is enabled by default. 183 */ 184 uint8_t readwrite_concur_lf_support; 185 /**< If read-write concurrency lock free support is enabled */ 186 uint8_t writer_takes_lock; 187 /**< Indicates if the writer threads need to take lock */ 188 rte_hash_function hash_func; /**< Function used to calculate hash. */ 189 uint32_t hash_func_init_val; /**< Init value used by hash_func. */ 190 rte_hash_cmp_eq_t rte_hash_custom_cmp_eq; 191 /**< Custom function used to compare keys. */ 192 enum cmp_jump_table_case cmp_jump_table_idx; 193 /**< Indicates which compare function to use. */ 194 unsigned int sig_cmp_fn; 195 /**< Indicates which signature compare function to use. */ 196 uint32_t bucket_bitmask; 197 /**< Bitmask for getting bucket index from hash signature. */ 198 uint32_t key_entry_size; /**< Size of each key entry. */ 199 200 void *key_store; /**< Table storing all keys and data */ 201 struct rte_hash_bucket *buckets; 202 /**< Table with buckets storing all the hash values and key indexes 203 * to the key table. 204 */ 205 rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */ 206 struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */ 207 struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */ 208 /* Stores index of an empty ext bkt to be recycled on calling 209 * rte_hash_del_xxx APIs. When lock free read-write concurrency is 210 * enabled, an empty ext bkt cannot be put into free list immediately 211 * (as readers might be using it still). Hence freeing of the ext bkt 212 * is piggy-backed to freeing of the key index. 213 */ 214 uint32_t *ext_bkt_to_free; 215 RTE_ATOMIC(uint32_t) *tbl_chng_cnt; 216 /**< Indicates if the hash table changed from last read. */ 217 }; 218 219 struct queue_node { 220 struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */ 221 uint32_t cur_bkt_idx; 222 223 struct queue_node *prev; /* Parent(bucket) in search path */ 224 int prev_slot; /* Parent(slot) in search path */ 225 }; 226 227 /** @internal Default RCU defer queue entries to reclaim in one go. */ 228 #define RTE_HASH_RCU_DQ_RECLAIM_MAX 16 229 230 #endif 231