]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*- |
2 | * BSD LICENSE | |
3 | * | |
4 | * Copyright(c) 2016 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 | /* rte_cuckoo_hash.h | |
35 | * This file hold Cuckoo Hash private data structures to allows include from | |
36 | * platform specific files like rte_cuckoo_hash_x86.h | |
37 | */ | |
38 | ||
39 | #ifndef _RTE_CUCKOO_HASH_H_ | |
40 | #define _RTE_CUCKOO_HASH_H_ | |
41 | ||
42 | #if defined(RTE_ARCH_X86) | |
43 | #include "rte_cmp_x86.h" | |
44 | #endif | |
45 | ||
46 | #if defined(RTE_ARCH_ARM64) | |
47 | #include "rte_cmp_arm64.h" | |
48 | #endif | |
49 | ||
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 { \ | |
53 | if (cond) \ | |
54 | return retval; \ | |
55 | } while (0) | |
56 | #else | |
57 | #define RETURN_IF_TRUE(cond, retval) | |
58 | #endif | |
59 | ||
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 | |
64 | #else | |
65 | #include <rte_jhash.h> | |
66 | #define DEFAULT_HASH_FUNC rte_jhash | |
67 | #endif | |
68 | ||
69 | #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) | |
70 | /* | |
71 | * All different options to select a key compare function, | |
72 | * based on the key size and custom function. | |
73 | */ | |
74 | enum cmp_jump_table_case { | |
75 | KEY_CUSTOM = 0, | |
76 | KEY_16_BYTES, | |
77 | KEY_32_BYTES, | |
78 | KEY_48_BYTES, | |
79 | KEY_64_BYTES, | |
80 | KEY_80_BYTES, | |
81 | KEY_96_BYTES, | |
82 | KEY_112_BYTES, | |
83 | KEY_128_BYTES, | |
84 | KEY_OTHER_BYTES, | |
85 | NUM_KEY_CMP_CASES, | |
86 | }; | |
87 | ||
88 | /* | |
89 | * Table storing all different key compare functions | |
90 | * (multi-process supported) | |
91 | */ | |
92 | const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = { | |
93 | NULL, | |
94 | rte_hash_k16_cmp_eq, | |
95 | rte_hash_k32_cmp_eq, | |
96 | rte_hash_k48_cmp_eq, | |
97 | rte_hash_k64_cmp_eq, | |
98 | rte_hash_k80_cmp_eq, | |
99 | rte_hash_k96_cmp_eq, | |
100 | rte_hash_k112_cmp_eq, | |
101 | rte_hash_k128_cmp_eq, | |
102 | memcmp | |
103 | }; | |
104 | #else | |
105 | /* | |
106 | * All different options to select a key compare function, | |
107 | * based on the key size and custom function. | |
108 | */ | |
109 | enum cmp_jump_table_case { | |
110 | KEY_CUSTOM = 0, | |
111 | KEY_OTHER_BYTES, | |
112 | NUM_KEY_CMP_CASES, | |
113 | }; | |
114 | ||
115 | /* | |
116 | * Table storing all different key compare functions | |
117 | * (multi-process supported) | |
118 | */ | |
119 | const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = { | |
120 | NULL, | |
121 | memcmp | |
122 | }; | |
123 | ||
124 | #endif | |
125 | ||
126 | enum add_key_case { | |
127 | ADD_KEY_SINGLEWRITER = 0, | |
128 | ADD_KEY_MULTIWRITER, | |
129 | ADD_KEY_MULTIWRITER_TM, | |
130 | }; | |
131 | ||
132 | /** Number of items per bucket. */ | |
133 | #define RTE_HASH_BUCKET_ENTRIES 8 | |
134 | ||
135 | #define NULL_SIGNATURE 0 | |
136 | ||
137 | #define EMPTY_SLOT 0 | |
138 | ||
139 | #define KEY_ALIGNMENT 16 | |
140 | ||
141 | #define LCORE_CACHE_SIZE 64 | |
142 | ||
143 | #define RTE_HASH_MAX_PUSHES 100 | |
144 | ||
145 | #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000 | |
146 | ||
147 | #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4 | |
148 | ||
149 | #define RTE_HASH_TSX_MAX_RETRY 10 | |
150 | ||
151 | struct lcore_cache { | |
152 | unsigned len; /**< Cache len */ | |
153 | void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */ | |
154 | } __rte_cache_aligned; | |
155 | ||
156 | /* Structure that stores key-value pair */ | |
157 | struct rte_hash_key { | |
158 | union { | |
159 | uintptr_t idata; | |
160 | void *pdata; | |
161 | }; | |
162 | /* Variable key size */ | |
163 | char key[0]; | |
164 | } __attribute__((aligned(KEY_ALIGNMENT))); | |
165 | ||
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, | |
171 | RTE_HASH_COMPARE_NUM | |
172 | }; | |
173 | ||
174 | /** Bucket structure */ | |
175 | struct rte_hash_bucket { | |
176 | hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES]; | |
177 | ||
178 | uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES]; | |
179 | ||
180 | hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES]; | |
181 | ||
182 | uint8_t flag[RTE_HASH_BUCKET_ENTRIES]; | |
183 | } __rte_cache_aligned; | |
184 | ||
185 | /** A hash table structure. */ | |
186 | struct rte_hash { | |
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. */ | |
190 | ||
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 */ | |
198 | ||
199 | rte_spinlock_t *multiwriter_lock; /**< Multi-writer spinlock for w/o TM */ | |
200 | ||
201 | /* Fields used in lookup */ | |
202 | ||
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. */ | |
216 | ||
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 | |
220 | * to the key table. | |
221 | */ | |
222 | } __rte_cache_aligned; | |
223 | ||
224 | struct queue_node { | |
225 | struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */ | |
226 | ||
227 | struct queue_node *prev; /* Parent(bucket) in search path */ | |
228 | int prev_slot; /* Parent(slot) in search path */ | |
229 | }; | |
230 | ||
231 | #endif |