4 * Copyright(c) 2016 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
35 * This file hold Cuckoo Hash private data structures to allows include from
36 * platform specific files like rte_cuckoo_hash_x86.h
39 #ifndef _RTE_CUCKOO_HASH_H_
40 #define _RTE_CUCKOO_HASH_H_
42 #if defined(RTE_ARCH_X86)
43 #include "rte_cmp_x86.h"
46 #if defined(RTE_ARCH_ARM64)
47 #include "rte_cmp_arm64.h"
50 /* Macro to enable/disable run-time checking of function parameters */
51 #if defined(RTE_LIBRTE_HASH_DEBUG)
52 #define RETURN_IF_TRUE(cond, retval) do { \
57 #define RETURN_IF_TRUE(cond, retval)
60 /* Hash function used if none is specified */
61 #if defined(RTE_MACHINE_CPUFLAG_SSE4_2) || defined(RTE_MACHINE_CPUFLAG_CRC32)
62 #include <rte_hash_crc.h>
63 #define DEFAULT_HASH_FUNC rte_hash_crc
65 #include <rte_jhash.h>
66 #define DEFAULT_HASH_FUNC rte_jhash
69 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
71 * All different options to select a key compare function,
72 * based on the key size and custom function.
74 enum cmp_jump_table_case
{
89 * Table storing all different key compare functions
90 * (multi-process supported)
92 const rte_hash_cmp_eq_t cmp_jump_table
[NUM_KEY_CMP_CASES
] = {
100 rte_hash_k112_cmp_eq
,
101 rte_hash_k128_cmp_eq
,
106 * All different options to select a key compare function,
107 * based on the key size and custom function.
109 enum cmp_jump_table_case
{
116 * Table storing all different key compare functions
117 * (multi-process supported)
119 const rte_hash_cmp_eq_t cmp_jump_table
[NUM_KEY_CMP_CASES
] = {
127 ADD_KEY_SINGLEWRITER
= 0,
129 ADD_KEY_MULTIWRITER_TM
,
132 /** Number of items per bucket. */
133 #define RTE_HASH_BUCKET_ENTRIES 8
135 #define NULL_SIGNATURE 0
139 #define KEY_ALIGNMENT 16
141 #define LCORE_CACHE_SIZE 64
143 #define RTE_HASH_MAX_PUSHES 100
145 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
147 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
149 #define RTE_HASH_TSX_MAX_RETRY 10
152 unsigned len
; /**< Cache len */
153 void *objs
[LCORE_CACHE_SIZE
]; /**< Cache objects */
154 } __rte_cache_aligned
;
156 /* Structure that stores key-value pair */
157 struct rte_hash_key
{
162 /* Variable key size */
164 } __attribute__((aligned(KEY_ALIGNMENT
)));
166 /* All different signature compare functions */
167 enum rte_hash_sig_compare_function
{
168 RTE_HASH_COMPARE_SCALAR
= 0,
169 RTE_HASH_COMPARE_SSE
,
170 RTE_HASH_COMPARE_AVX2
,
174 /** Bucket structure */
175 struct rte_hash_bucket
{
176 hash_sig_t sig_current
[RTE_HASH_BUCKET_ENTRIES
];
178 uint32_t key_idx
[RTE_HASH_BUCKET_ENTRIES
];
180 hash_sig_t sig_alt
[RTE_HASH_BUCKET_ENTRIES
];
182 uint8_t flag
[RTE_HASH_BUCKET_ENTRIES
];
183 } __rte_cache_aligned
;
185 /** A hash table structure. */
187 char name
[RTE_HASH_NAMESIZE
]; /**< Name of the hash. */
188 uint32_t entries
; /**< Total table entries. */
189 uint32_t num_buckets
; /**< Number of buckets in table. */
191 struct rte_ring
*free_slots
;
192 /**< Ring that stores all indexes of the free slots in the key table */
193 uint8_t hw_trans_mem_support
;
194 /**< Hardware transactional memory support */
195 struct lcore_cache
*local_free_slots
;
196 /**< Local cache per lcore, storing some indexes of the free slots */
197 enum add_key_case add_key
; /**< Multi-writer hash add behavior */
199 rte_spinlock_t
*multiwriter_lock
; /**< Multi-writer spinlock for w/o TM */
201 /* Fields used in lookup */
203 uint32_t key_len __rte_cache_aligned
;
204 /**< Length of hash key. */
205 rte_hash_function hash_func
; /**< Function used to calculate hash. */
206 uint32_t hash_func_init_val
; /**< Init value used by hash_func. */
207 rte_hash_cmp_eq_t rte_hash_custom_cmp_eq
;
208 /**< Custom function used to compare keys. */
209 enum cmp_jump_table_case cmp_jump_table_idx
;
210 /**< Indicates which compare function to use. */
211 enum rte_hash_sig_compare_function sig_cmp_fn
;
212 /**< Indicates which signature compare function to use. */
213 uint32_t bucket_bitmask
;
214 /**< Bitmask for getting bucket index from hash signature. */
215 uint32_t key_entry_size
; /**< Size of each key entry. */
217 void *key_store
; /**< Table storing all keys and data */
218 struct rte_hash_bucket
*buckets
;
219 /**< Table with buckets storing all the hash values and key indexes
222 } __rte_cache_aligned
;
225 struct rte_hash_bucket
*bkt
; /* Current bucket on the bfs search */
227 struct queue_node
*prev
; /* Parent(bucket) in search path */
228 int prev_slot
; /* Parent(slot) in search path */