4 * Copyright(c) 2010-2012 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.
33 * version: DPDK.L.1.2.3-3
42 #include <sys/queue.h>
44 #include <rte_common.h>
45 #include <rte_malloc.h>
46 #include <rte_cycles.h>
47 #include <rte_random.h>
48 #include <rte_memory.h>
49 #include <rte_memzone.h>
51 #include <rte_hash_crc.h>
52 #include <rte_jhash.h>
53 #include <rte_tailq.h>
55 #include <rte_fbk_hash.h>
57 #include <rte_string_fns.h>
59 #include <cmdline_parse.h>
63 #ifdef RTE_LIBRTE_HASH
65 /* Types of hash table performance test that can be performed */
67 ADD_ON_EMPTY, /*< Add keys to empty table */
68 DELETE_ON_EMPTY, /*< Attempt to delete keys from empty table */
69 LOOKUP_ON_EMPTY, /*< Attempt to find keys in an empty table */
70 ADD_UPDATE, /*< Add/update keys in a full table */
71 DELETE, /*< Delete keys from a full table */
72 LOOKUP /*< Find keys in a full table */
75 /* Function type for hash table operations. */
76 typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key);
78 /* Structure to hold parameters used to run a hash table performance test */
79 struct tbl_perf_test_params {
80 enum hash_test_t test_type;
81 uint32_t num_iterations;
83 uint32_t bucket_entries;
85 rte_hash_function hash_func;
86 uint32_t hash_func_init_val;
89 #define ITERATIONS 10000
90 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
92 /*******************************************************************************
93 * Hash table performance test configuration section.
95 struct tbl_perf_test_params tbl_perf_params[] =
97 /* Small table, add */
98 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
99 { ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0},
100 { ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0},
101 { ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0},
102 { ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0},
103 { ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0},
104 { ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0},
105 { ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0},
106 { ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0},
107 { ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0},
108 { ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0},
109 { ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0},
110 { ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0},
111 { ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0},
112 { ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0},
113 { ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0},
114 { ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0},
115 { ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0},
116 { ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0},
117 { ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0},
118 { ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0},
119 /* Small table, update */
120 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
121 { ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0},
122 { ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0},
123 { ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0},
124 { ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0},
125 { ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0},
126 { ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0},
127 { ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0},
128 { ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0},
129 { ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0},
130 { ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0},
131 { ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0},
132 { ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0},
133 { ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0},
134 { ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0},
135 { ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0},
136 { ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0},
137 { ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0},
138 { ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0},
139 { ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0},
140 { ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0},
141 /* Small table, lookup */
142 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
143 { LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0},
144 { LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0},
145 { LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0},
146 { LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0},
147 { LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0},
148 { LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0},
149 { LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0},
150 { LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0},
151 { LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0},
152 { LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0},
153 { LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0},
154 { LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0},
155 { LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0},
156 { LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0},
157 { LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0},
158 { LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0},
159 { LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0},
160 { LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0},
161 { LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0},
162 { LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0},
164 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
165 { ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0},
166 { ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0},
167 { ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0},
168 { ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0},
169 { ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0},
170 { ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0},
171 { ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0},
172 { ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0},
173 { ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0},
174 { ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0},
175 { ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0},
176 { ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0},
177 { ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0},
178 { ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0},
179 { ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0},
180 { ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0},
181 { ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0},
182 { ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0},
183 { ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0},
184 { ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0},
185 /* Big table, update */
186 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
187 { ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0},
188 { ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0},
189 { ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0},
190 { ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0},
191 { ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0},
192 { ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0},
193 { ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0},
194 { ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0},
195 { ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0},
196 { ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0},
197 { ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0},
198 { ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0},
199 { ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0},
200 { ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0},
201 { ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0},
202 { ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0},
203 { ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0},
204 { ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0},
205 { ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0},
206 { ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0},
207 /* Big table, lookup */
208 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
209 { LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0},
210 { LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0},
211 { LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0},
212 { LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0},
213 { LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0},
214 { LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0},
215 { LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0},
216 { LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0},
217 { LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0},
218 { LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0},
219 { LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0},
220 { LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0},
221 { LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0},
222 { LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0},
223 { LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0},
224 { LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0},
225 { LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0},
226 { LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0},
227 { LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0},
228 { LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0},
230 /* Small table, add */
231 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
232 { ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0},
233 { ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0},
234 { ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0},
235 { ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0},
236 { ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0},
237 { ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0},
238 { ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0},
239 { ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0},
240 { ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0},
241 { ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0},
242 { ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0},
243 { ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0},
244 { ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0},
245 { ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0},
246 { ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0},
247 { ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0},
248 { ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0},
249 { ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0},
250 { ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0},
251 { ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0},
252 /* Small table, update */
253 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
254 { ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0},
255 { ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0},
256 { ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0},
257 { ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0},
258 { ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0},
259 { ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0},
260 { ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0},
261 { ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0},
262 { ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0},
263 { ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0},
264 { ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0},
265 { ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0},
266 { ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0},
267 { ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0},
268 { ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0},
269 { ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0},
270 { ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0},
271 { ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0},
272 { ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0},
273 { ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0},
274 /* Small table, lookup */
275 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
276 { LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0},
277 { LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0},
278 { LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0},
279 { LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0},
280 { LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0},
281 { LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0},
282 { LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0},
283 { LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0},
284 { LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0},
285 { LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0},
286 { LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0},
287 { LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0},
288 { LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0},
289 { LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0},
290 { LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0},
291 { LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0},
292 { LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0},
293 { LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0},
294 { LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0},
295 { LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0},
297 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
298 { ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0},
299 { ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0},
300 { ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0},
301 { ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0},
302 { ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0},
303 { ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0},
304 { ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0},
305 { ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0},
306 { ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0},
307 { ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0},
308 { ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0},
309 { ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0},
310 { ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0},
311 { ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0},
312 { ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0},
313 { ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0},
314 { ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0},
315 { ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0},
316 { ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0},
317 { ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0},
318 /* Big table, update */
319 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
320 { ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0},
321 { ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0},
322 { ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0},
323 { ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0},
324 { ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0},
325 { ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0},
326 { ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0},
327 { ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0},
328 { ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0},
329 { ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0},
330 { ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0},
331 { ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0},
332 { ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0},
333 { ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0},
334 { ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0},
335 { ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0},
336 { ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0},
337 { ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0},
338 { ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0},
339 { ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0},
340 /* Big table, lookup */
341 /* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
342 { LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0},
343 { LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0},
344 { LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0},
345 { LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0},
346 { LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0},
347 { LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0},
348 { LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0},
349 { LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0},
350 { LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0},
351 { LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0},
352 { LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0},
353 { LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0},
354 { LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0},
355 { LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0},
356 { LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0},
357 { LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0},
358 { LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0},
359 { LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0},
360 { LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0},
361 { LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0},
364 /******************************************************************************/
366 /*******************************************************************************
367 * Hash function performance test configuration section. Each performance test
368 * will be performed HASHTEST_ITERATIONS times.
370 * The five arrays below control what tests are performed. Every combination
371 * from the array entries is tested.
373 #define HASHTEST_ITERATIONS 1000000
375 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
376 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
378 static rte_hash_function hashtest_funcs[] = {rte_jhash};
380 static uint32_t hashtest_initvals[] = {0};
381 static uint32_t hashtest_key_lens[] = {2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
382 /******************************************************************************/
385 * Check condition and return an error if true. Assumes that "handle" is the
386 * name of the hash structure pointer to be freed.
388 #define RETURN_IF_ERROR(cond, str, ...) do { \
390 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
391 if (handle) rte_hash_free(handle); \
396 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
398 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
399 if (handle) rte_fbk_hash_free(handle); \
404 /* 5-tuple key type */
411 } __attribute__((packed));
414 * Hash function that always returns the same value, to easily test what
415 * happens when a bucket is full.
417 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
418 __attribute__((unused)) uint32_t key_len,
419 __attribute__((unused)) uint32_t init_val)
425 * Print out result of unit test hash operation.
427 #if defined(UNIT_TEST_HASH_VERBOSE)
428 static void print_key_info(const char *msg, const struct flow_key *key,
431 uint8_t *p = (uint8_t *)key;
434 printf("%s key:0x", msg);
435 for (i = 0; i < sizeof(struct flow_key); i++) {
436 printf("%02X", p[i]);
438 printf(" @ pos %d\n", pos);
441 static void print_key_info(__attribute__((unused)) const char *msg,
442 __attribute__((unused)) const struct flow_key *key,
443 __attribute__((unused)) int32_t pos)
448 /* Keys used by unit test functions */
449 static struct flow_key keys[5] = { {
450 .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
451 .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
456 .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
457 .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
462 .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
463 .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
468 .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
469 .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
474 .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
475 .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
481 /* Parameters used for hash table in unit test functions. Name set later. */
482 static struct rte_hash_parameters ut_params = {
485 .key_len = sizeof(struct flow_key), /* 13 */
486 .hash_func = rte_jhash,
487 .hash_func_init_val = 0,
492 * Basic sequence of operations for a single key:
498 static int test_add_delete(void)
500 struct rte_hash *handle;
501 int pos0, expectedPos0;
503 ut_params.name = "test1";
504 handle = rte_hash_create(&ut_params);
505 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
507 pos0 = rte_hash_add_key(handle, &keys[0]);
508 print_key_info("Add", &keys[0], pos0);
509 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
512 pos0 = rte_hash_lookup(handle, &keys[0]);
513 print_key_info("Lkp", &keys[0], pos0);
514 RETURN_IF_ERROR(pos0 != expectedPos0,
515 "failed to find key (pos0=%d)", pos0);
517 pos0 = rte_hash_del_key(handle, &keys[0]);
518 print_key_info("Del", &keys[0], pos0);
519 RETURN_IF_ERROR(pos0 != expectedPos0,
520 "failed to delete key (pos0=%d)", pos0);
522 pos0 = rte_hash_lookup(handle, &keys[0]);
523 print_key_info("Lkp", &keys[0], pos0);
524 RETURN_IF_ERROR(pos0 != -ENOENT,
525 "fail: found key after deleting! (pos0=%d)", pos0);
527 rte_hash_free(handle);
532 * Sequence of operations for a single key:
537 * - lookup: hit (updated data)
542 static int test_add_update_delete(void)
544 struct rte_hash *handle;
545 int pos0, expectedPos0;
547 ut_params.name = "test2";
548 handle = rte_hash_create(&ut_params);
549 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
551 pos0 = rte_hash_del_key(handle, &keys[0]);
552 print_key_info("Del", &keys[0], pos0);
553 RETURN_IF_ERROR(pos0 != -ENOENT,
554 "fail: found non-existent key (pos0=%d)", pos0);
556 pos0 = rte_hash_add_key(handle, &keys[0]);
557 print_key_info("Add", &keys[0], pos0);
558 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
561 pos0 = rte_hash_lookup(handle, &keys[0]);
562 print_key_info("Lkp", &keys[0], pos0);
563 RETURN_IF_ERROR(pos0 != expectedPos0,
564 "failed to find key (pos0=%d)", pos0);
566 pos0 = rte_hash_add_key(handle, &keys[0]);
567 print_key_info("Add", &keys[0], pos0);
568 RETURN_IF_ERROR(pos0 != expectedPos0,
569 "failed to re-add key (pos0=%d)", pos0);
571 pos0 = rte_hash_lookup(handle, &keys[0]);
572 print_key_info("Lkp", &keys[0], pos0);
573 RETURN_IF_ERROR(pos0 != expectedPos0,
574 "failed to find key (pos0=%d)", pos0);
576 pos0 = rte_hash_del_key(handle, &keys[0]);
577 print_key_info("Del", &keys[0], pos0);
578 RETURN_IF_ERROR(pos0 != expectedPos0,
579 "failed to delete key (pos0=%d)", pos0);
581 pos0 = rte_hash_del_key(handle, &keys[0]);
582 print_key_info("Del", &keys[0], pos0);
583 RETURN_IF_ERROR(pos0 != -ENOENT,
584 "fail: deleted already deleted key (pos0=%d)", pos0);
586 pos0 = rte_hash_lookup(handle, &keys[0]);
587 print_key_info("Lkp", &keys[0], pos0);
588 RETURN_IF_ERROR(pos0 != -ENOENT,
589 "fail: found key after deleting! (pos0=%d)", pos0);
591 rte_hash_free(handle);
596 * Sequence of operations for find existing hash table
599 * - find existing table: hit
600 * - find non-existing table: miss
603 static int test_hash_find_existing(void)
605 struct rte_hash *handle = NULL, *result = NULL;
607 /* Create hash table. */
608 ut_params.name = "hash_find_existing";
609 handle = rte_hash_create(&ut_params);
610 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
612 /* Try to find existing hash table */
613 result = rte_hash_find_existing("hash_find_existing");
614 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
616 /* Try to find non-existing hash table */
617 result = rte_hash_find_existing("hash_find_non_existing");
618 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
621 rte_hash_free(handle);
627 * Sequence of operations for 5 keys
630 * - add keys (update)
631 * - lookup keys: hit (updated data)
632 * - delete keys : hit
633 * - lookup keys: miss
635 static int test_five_keys(void)
637 struct rte_hash *handle;
638 const void *key_array[5] = {0};
644 ut_params.name = "test3";
645 handle = rte_hash_create(&ut_params);
646 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
649 for (i = 0; i < 5; i++) {
650 pos[i] = rte_hash_add_key(handle, &keys[i]);
651 print_key_info("Add", &keys[i], pos[i]);
652 RETURN_IF_ERROR(pos[i] < 0,
653 "failed to add key (pos[%u]=%d)", i, pos[i]);
654 expected_pos[i] = pos[i];
658 for(i = 0; i < 5; i++)
659 key_array[i] = &keys[i];
661 ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
663 for(i = 0; i < 5; i++) {
664 print_key_info("Lkp", key_array[i], pos[i]);
665 RETURN_IF_ERROR(pos[i] != expected_pos[i],
666 "failed to find key (pos[%u]=%d)", i, pos[i]);
670 for (i = 0; i < 5; i++) {
671 pos[i] = rte_hash_add_key(handle, &keys[i]);
672 print_key_info("Add", &keys[i], pos[i]);
673 RETURN_IF_ERROR(pos[i] != expected_pos[i],
674 "failed to add key (pos[%u]=%d)", i, pos[i]);
678 for (i = 0; i < 5; i++) {
679 pos[i] = rte_hash_lookup(handle, &keys[i]);
680 print_key_info("Lkp", &keys[i], pos[i]);
681 RETURN_IF_ERROR(pos[i] != expected_pos[i],
682 "failed to find key (pos[%u]=%d)", i, pos[i]);
686 for (i = 0; i < 5; i++) {
687 pos[i] = rte_hash_del_key(handle, &keys[i]);
688 print_key_info("Del", &keys[i], pos[i]);
689 RETURN_IF_ERROR(pos[i] != expected_pos[i],
690 "failed to delete key (pos[%u]=%d)", i, pos[i]);
694 for (i = 0; i < 5; i++) {
695 pos[i] = rte_hash_lookup(handle, &keys[i]);
696 print_key_info("Lkp", &keys[i], pos[i]);
697 RETURN_IF_ERROR(pos[i] != -ENOENT,
698 "failed to find key (pos[%u]=%d)", i, pos[i]);
701 rte_hash_free(handle);
707 * Add keys to the same bucket until bucket full.
708 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
709 * first 4 successful, 5th unsuccessful
710 * - lookup the 5 keys: 4 hits, 1 miss
711 * - add the 5 keys again: 4 OK, one error as bucket is full
712 * - lookup the 5 keys: 4 hits (updated data), 1 miss
713 * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
714 * - lookup the 5 keys: 5 misses
715 * - add the 5th key: OK
716 * - lookup the 5th key: hit
718 static int test_full_bucket(void)
720 struct rte_hash_parameters params_pseudo_hash = {
724 .key_len = sizeof(struct flow_key), /* 13 */
725 .hash_func = pseudo_hash,
726 .hash_func_init_val = 0,
729 struct rte_hash *handle;
734 handle = rte_hash_create(¶ms_pseudo_hash);
735 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
738 for (i = 0; i < 4; i++) {
739 pos[i] = rte_hash_add_key(handle, &keys[i]);
740 print_key_info("Add", &keys[i], pos[i]);
741 RETURN_IF_ERROR(pos[i] < 0,
742 "failed to add key (pos[%u]=%d)", i, pos[i]);
743 expected_pos[i] = pos[i];
745 /* This shouldn't work because the bucket is full */
746 pos[4] = rte_hash_add_key(handle, &keys[4]);
747 print_key_info("Add", &keys[4], pos[4]);
748 RETURN_IF_ERROR(pos[4] != -ENOSPC,
749 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
752 for (i = 0; i < 4; i++) {
753 pos[i] = rte_hash_lookup(handle, &keys[i]);
754 print_key_info("Lkp", &keys[i], pos[i]);
755 RETURN_IF_ERROR(pos[i] != expected_pos[i],
756 "failed to find key (pos[%u]=%d)", i, pos[i]);
758 pos[4] = rte_hash_lookup(handle, &keys[4]);
759 print_key_info("Lkp", &keys[4], pos[4]);
760 RETURN_IF_ERROR(pos[4] != -ENOENT,
761 "fail: found non-existent key (pos[4]=%d)", pos[4]);
764 for (i = 0; i < 4; i++) {
765 pos[i] = rte_hash_add_key(handle, &keys[i]);
766 print_key_info("Add", &keys[i], pos[i]);
767 RETURN_IF_ERROR(pos[i] != expected_pos[i],
768 "failed to add key (pos[%u]=%d)", i, pos[i]);
770 pos[4] = rte_hash_add_key(handle, &keys[4]);
771 print_key_info("Add", &keys[4], pos[4]);
772 RETURN_IF_ERROR(pos[4] != -ENOSPC,
773 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
776 for (i = 0; i < 4; i++) {
777 pos[i] = rte_hash_lookup(handle, &keys[i]);
778 print_key_info("Lkp", &keys[i], pos[i]);
779 RETURN_IF_ERROR(pos[i] != expected_pos[i],
780 "failed to find key (pos[%u]=%d)", i, pos[i]);
782 pos[4] = rte_hash_lookup(handle, &keys[4]);
783 print_key_info("Lkp", &keys[4], pos[4]);
784 RETURN_IF_ERROR(pos[4] != -ENOENT,
785 "fail: found non-existent key (pos[4]=%d)", pos[4]);
787 /* Delete 1 key, check other keys are still found */
788 pos[1] = rte_hash_del_key(handle, &keys[1]);
789 print_key_info("Del", &keys[1], pos[1]);
790 RETURN_IF_ERROR(pos[1] != expected_pos[1],
791 "failed to delete key (pos[1]=%d)", pos[1]);
792 pos[3] = rte_hash_lookup(handle, &keys[3]);
793 print_key_info("Lkp", &keys[3], pos[3]);
794 RETURN_IF_ERROR(pos[3] != expected_pos[3],
795 "failed lookup after deleting key from same bucket "
796 "(pos[3]=%d)", pos[3]);
798 /* Go back to previous state */
799 pos[1] = rte_hash_add_key(handle, &keys[1]);
800 print_key_info("Add", &keys[1], pos[1]);
801 expected_pos[1] = pos[1];
802 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
805 for (i = 0; i < 4; i++) {
806 pos[i] = rte_hash_del_key(handle, &keys[i]);
807 print_key_info("Del", &keys[i], pos[i]);
808 RETURN_IF_ERROR(pos[i] != expected_pos[i],
809 "failed to delete key (pos[%u]=%d)", i, pos[i]);
811 pos[4] = rte_hash_del_key(handle, &keys[4]);
812 print_key_info("Del", &keys[4], pos[4]);
813 RETURN_IF_ERROR(pos[4] != -ENOENT,
814 "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
817 for (i = 0; i < 4; i++) {
818 pos[i] = rte_hash_lookup(handle, &keys[i]);
819 print_key_info("Lkp", &keys[i], pos[i]);
820 RETURN_IF_ERROR(pos[i] != -ENOENT,
821 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
824 /* Add and lookup the 5th key */
825 pos[4] = rte_hash_add_key(handle, &keys[4]);
826 print_key_info("Add", &keys[4], pos[4]);
827 RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
828 expected_pos[4] = pos[4];
829 pos[4] = rte_hash_lookup(handle, &keys[4]);
830 print_key_info("Lkp", &keys[4], pos[4]);
831 RETURN_IF_ERROR(pos[4] != expected_pos[4],
832 "failed to find key (pos[4]=%d)", pos[4]);
834 rte_hash_free(handle);
836 /* Cover the NULL case. */
842 * To help print out name of hash functions.
844 static const char *get_hash_name(rte_hash_function f)
849 if (f == rte_hash_crc)
850 return "rte_hash_crc";
852 return "UnknownHash";
856 * Find average of array of numbers.
859 get_avg(const uint32_t *array, uint32_t size)
863 for (i = 0; i < size; i++)
865 return sum / (double)size;
869 * Do a single performance test, of one type of operation.
872 * hash table to run test on
874 * function to call (add, delete or lookup function)
875 * @param avg_occupancy
876 * The average number of entries in each bucket of the hash table
877 * @param invalid_pos_count
878 * The amount of errors (e.g. due to a full bucket).
880 * The average number of ticks per hash function call. A negative number
884 run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func,
885 const struct tbl_perf_test_params *params, double *avg_occupancy,
886 uint32_t *invalid_pos_count)
888 uint64_t begin, end, ticks = 0;
890 uint32_t *bucket_occupancies = NULL;
891 uint32_t num_buckets, i, j;
895 num_buckets = params->entries / params->bucket_entries;
896 key = (uint8_t *) rte_zmalloc("hash key",
897 params->key_len * sizeof(uint8_t), 16);
901 bucket_occupancies = (uint32_t *) rte_zmalloc("bucket occupancies",
902 num_buckets * sizeof(uint32_t), 16);
903 if (bucket_occupancies == NULL) {
909 *invalid_pos_count = 0;
911 for (i = 0; i < params->num_iterations; i++) {
912 /* Prepare inputs for the current iteration */
913 for (j = 0; j < params->key_len; j++)
914 key[j] = (uint8_t) rte_rand();
916 /* Perform operation, and measure time it takes */
920 ticks += end - begin;
922 /* Other work per iteration */
924 *invalid_pos_count += 1;
926 bucket_occupancies[pos / params->bucket_entries]++;
928 *avg_occupancy = get_avg(bucket_occupancies, num_buckets);
930 rte_free(bucket_occupancies);
933 return (double)ticks / params->num_iterations;
937 * To help print out what tests are being done.
940 get_tbl_perf_test_desc(enum hash_test_t type)
943 case ADD_ON_EMPTY: return "Add on Empty";
944 case DELETE_ON_EMPTY: return "Delete on Empty";
945 case LOOKUP_ON_EMPTY: return "Lookup on Empty";
946 case ADD_UPDATE: return "Add Update";
947 case DELETE: return "Delete";
948 case LOOKUP: return "Lookup";
949 default: return "UNKNOWN";
954 * Run a hash table performance test based on params.
957 run_tbl_perf_test(struct tbl_perf_test_params *params)
959 static unsigned calledCount = 5;
960 struct rte_hash_parameters hash_params = {
961 .entries = params->entries,
962 .bucket_entries = params->bucket_entries,
963 .key_len = params->key_len,
964 .hash_func = params->hash_func,
965 .hash_func_init_val = params->hash_func_init_val,
968 struct rte_hash *handle;
969 double avg_occupancy = 0, ticks = 0;
970 uint32_t num_iterations, invalid_pos;
971 char name[RTE_HASH_NAMESIZE];
972 char hashname[RTE_HASH_NAMESIZE];
974 rte_snprintf(name, 32, "test%u", calledCount++);
975 hash_params.name = name;
977 handle = rte_hash_create(&hash_params);
978 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
980 switch (params->test_type){
982 ticks = run_single_tbl_perf_test(handle, rte_hash_add_key,
983 params, &avg_occupancy, &invalid_pos);
985 case DELETE_ON_EMPTY:
986 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
987 params, &avg_occupancy, &invalid_pos);
989 case LOOKUP_ON_EMPTY:
990 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
991 params, &avg_occupancy, &invalid_pos);
994 num_iterations = params->num_iterations;
995 params->num_iterations = params->entries;
996 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
997 &avg_occupancy, &invalid_pos);
998 params->num_iterations = num_iterations;
999 ticks = run_single_tbl_perf_test(handle, rte_hash_add_key,
1000 params, &avg_occupancy, &invalid_pos);
1003 num_iterations = params->num_iterations;
1004 params->num_iterations = params->entries;
1005 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
1006 &avg_occupancy, &invalid_pos);
1008 params->num_iterations = num_iterations;
1009 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
1010 params, &avg_occupancy, &invalid_pos);
1013 num_iterations = params->num_iterations;
1014 params->num_iterations = params->entries;
1015 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
1016 &avg_occupancy, &invalid_pos);
1018 params->num_iterations = num_iterations;
1019 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
1020 params, &avg_occupancy, &invalid_pos);
1025 rte_snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func));
1027 printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n",
1029 get_tbl_perf_test_desc(params->test_type),
1030 (unsigned) params->key_len,
1031 (unsigned) params->entries,
1032 (unsigned) params->bucket_entries,
1033 (unsigned) invalid_pos,
1039 rte_hash_free(handle);
1044 * Run all hash table performance tests.
1046 static int run_all_tbl_perf_tests(void)
1050 printf(" *** Hash table performance test results ***\n");
1051 printf("Hash Func. , Operation , Key size (bytes), Entries, "
1052 "Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\n");
1054 /* Loop through every combination of test parameters */
1056 i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params);
1060 if (run_tbl_perf_test(&tbl_perf_params[i]) < 0)
1067 * Test a hash function.
1069 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
1072 static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
1073 uint64_t ticks = 0, start, end;
1076 for (i = 0; i < HASHTEST_ITERATIONS; i++) {
1078 for (j = 0; j < key_len; j++)
1079 key[j] = (uint8_t) rte_rand();
1081 start = rte_rdtsc();
1082 f(key, key_len, init_val);
1084 ticks += end - start;
1087 printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
1088 (unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
1092 * Test all hash functions.
1094 static void run_hash_func_tests(void)
1098 printf("\n\n *** Hash function performance test results ***\n");
1099 printf(" Number of iterations for each test = %d\n",
1100 HASHTEST_ITERATIONS);
1101 printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
1104 i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
1107 j < sizeof(hashtest_initvals) / sizeof(uint32_t);
1110 k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
1112 run_hash_func_test(hashtest_funcs[i],
1113 hashtest_initvals[j],
1114 hashtest_key_lens[k]);
1120 /******************************************************************************/
1122 fbk_hash_unit_test(void)
1124 struct rte_fbk_hash_params params = {
1125 .name = "fbk_hash_test",
1126 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1127 .entries_per_bucket = 4,
1131 struct rte_fbk_hash_params invalid_params_1 = {
1132 .name = "invalid_1",
1133 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
1134 .entries_per_bucket = 4,
1138 struct rte_fbk_hash_params invalid_params_2 = {
1139 .name = "invalid_4",
1141 .entries_per_bucket = 3, /* Not power of 2 */
1145 struct rte_fbk_hash_params invalid_params_3 = {
1146 .name = "invalid_2",
1147 .entries = 0, /* Entries is 0 */
1148 .entries_per_bucket = 4,
1152 struct rte_fbk_hash_params invalid_params_4 = {
1153 .name = "invalid_3",
1154 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1155 .entries_per_bucket = 0, /* Entries per bucket is 0 */
1159 struct rte_fbk_hash_params invalid_params_5 = {
1160 .name = "invalid_4",
1162 .entries_per_bucket = 8, /* Entries per bucket > entries */
1166 struct rte_fbk_hash_params invalid_params_6 = {
1167 .name = "invalid_5",
1168 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
1169 .entries_per_bucket = 4,
1173 struct rte_fbk_hash_params params_jhash = {
1175 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1176 .entries_per_bucket = 4,
1178 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
1179 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1182 struct rte_fbk_hash_params params_nohash = {
1183 .name = "valid nohash",
1184 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1185 .entries_per_bucket = 4,
1187 .hash_func = 0, /* Tests for null hash_func */
1188 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1191 struct rte_fbk_hash_table *handle;
1193 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1194 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
1197 double used_entries;
1199 /* Try creating hashes with invalid parameters */
1200 handle = rte_fbk_hash_create(&invalid_params_1);
1201 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1203 handle = rte_fbk_hash_create(&invalid_params_2);
1204 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1206 handle = rte_fbk_hash_create(&invalid_params_3);
1207 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1209 handle = rte_fbk_hash_create(&invalid_params_4);
1210 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1212 handle = rte_fbk_hash_create(&invalid_params_5);
1213 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1215 handle = rte_fbk_hash_create(&invalid_params_6);
1216 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1218 /* Create empty jhash hash. */
1219 handle = rte_fbk_hash_create(¶ms_jhash);
1220 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
1223 rte_fbk_hash_free(handle);
1225 /* Create empty jhash hash. */
1226 handle = rte_fbk_hash_create(¶ms_nohash);
1227 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
1230 rte_fbk_hash_free(handle);
1232 /* Create empty hash. */
1233 handle = rte_fbk_hash_create(¶ms);
1234 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1236 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1237 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1238 "load factor right after creation is not zero but it should be");
1240 for (i = 0; i < 5; i++) {
1241 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1242 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1245 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1246 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
1247 "load factor now is not as expected");
1248 /* Find value of added keys. */
1249 for (i = 0; i < 5; i++) {
1250 status = rte_fbk_hash_lookup(handle, keys[i]);
1251 RETURN_IF_ERROR_FBK(status != vals[i],
1252 "fbk hash lookup failed");
1255 /* Change value of added keys. */
1256 for (i = 0; i < 5; i++) {
1257 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
1258 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
1261 /* Find new values. */
1262 for (i = 0; i < 5; i++) {
1263 status = rte_fbk_hash_lookup(handle, keys[i]);
1264 RETURN_IF_ERROR_FBK(status != vals[4-i],
1265 "fbk hash lookup failed");
1268 /* Delete keys individually. */
1269 for (i = 0; i < 5; i++) {
1270 status = rte_fbk_hash_delete_key(handle, keys[i]);
1271 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
1274 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1275 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1276 "load factor right after deletion is not zero but it should be");
1277 /* Lookup should now fail. */
1278 for (i = 0; i < 5; i++) {
1279 status = rte_fbk_hash_lookup(handle, keys[i]);
1280 RETURN_IF_ERROR_FBK(status == 0,
1281 "fbk hash lookup should have failed");
1284 /* Add keys again. */
1285 for (i = 0; i < 5; i++) {
1286 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1287 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1290 /* Make sure they were added. */
1291 for (i = 0; i < 5; i++) {
1292 status = rte_fbk_hash_lookup(handle, keys[i]);
1293 RETURN_IF_ERROR_FBK(status != vals[i],
1294 "fbk hash lookup failed");
1297 /* Clear all entries. */
1298 rte_fbk_hash_clear_all(handle);
1300 /* Lookup should fail. */
1301 for (i = 0; i < 5; i++) {
1302 status = rte_fbk_hash_lookup(handle, keys[i]);
1303 RETURN_IF_ERROR_FBK(status == 0,
1304 "fbk hash lookup should have failed");
1308 rte_fbk_hash_free(handle);
1310 /* Cover the NULL case. */
1311 rte_fbk_hash_free(0);
1316 /* Control operation of performance testing of fbk hash. */
1317 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
1318 #define TEST_SIZE 1000000 /* How many operations to time. */
1319 #define TEST_ITERATIONS 30 /* How many measurements to take. */
1320 #define ENTRIES (1 << 15) /* How many entries. */
1323 fbk_hash_perf_test(void)
1325 struct rte_fbk_hash_params params = {
1326 .name = "fbk_hash_test",
1328 .entries_per_bucket = 4,
1331 struct rte_fbk_hash_table *handle;
1332 uint32_t keys[ENTRIES] = {0};
1333 unsigned indexes[TEST_SIZE];
1334 uint64_t lookup_time = 0;
1339 handle = rte_fbk_hash_create(¶ms);
1340 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1342 /* Generate random keys and values. */
1343 for (i = 0; i < ENTRIES; i++) {
1344 uint32_t key = (uint32_t)rte_rand();
1345 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
1346 uint16_t val = (uint16_t)rte_rand();
1348 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
1352 if (added > (LOAD_FACTOR * ENTRIES)) {
1357 for (i = 0; i < TEST_ITERATIONS; i++) {
1361 /* Generate random indexes into keys[] array. */
1362 for (j = 0; j < TEST_SIZE; j++) {
1363 indexes[j] = rte_rand() % added;
1366 begin = rte_rdtsc();
1368 for (j = 0; j < TEST_SIZE; j++) {
1369 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
1372 lookup_time += (double)(end - begin);
1375 printf("\n\n *** FBK Hash function performance test results ***\n");
1377 * The use of the 'value' variable ensures that the hash lookup is not
1378 * being optimised out by the compiler.
1381 printf("Number of ticks per lookup = %g\n",
1382 (double)lookup_time /
1383 ((double)TEST_ITERATIONS * (double)TEST_SIZE));
1385 rte_fbk_hash_free(handle);
1391 * Sequence of operations for find existing fbk hash table
1394 * - find existing table: hit
1395 * - find non-existing table: miss
1398 static int test_fbk_hash_find_existing(void)
1400 struct rte_fbk_hash_params params = {
1401 .name = "fbk_hash_find_existing",
1402 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1403 .entries_per_bucket = 4,
1406 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1408 /* Create hash table. */
1409 handle = rte_fbk_hash_create(¶ms);
1410 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1412 /* Try to find existing fbk hash table */
1413 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
1414 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
1416 /* Try to find non-existing fbk hash table */
1417 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1418 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
1421 rte_fbk_hash_free(handle);
1427 * Do tests for hash creation with bad parameters.
1429 static int test_hash_creation_with_bad_parameters(void)
1431 struct rte_hash *handle;
1432 struct rte_hash_parameters params;
1434 handle = rte_hash_create(NULL);
1435 if (handle != NULL) {
1436 rte_hash_free(handle);
1437 printf("Impossible creating hash sucessfully without any parameter\n");
1441 memcpy(¶ms, &ut_params, sizeof(params));
1442 params.name = "creation_with_bad_parameters_0";
1443 params.entries = RTE_HASH_ENTRIES_MAX + 1;
1444 handle = rte_hash_create(¶ms);
1445 if (handle != NULL) {
1446 rte_hash_free(handle);
1447 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
1451 memcpy(¶ms, &ut_params, sizeof(params));
1452 params.name = "creation_with_bad_parameters_1";
1453 params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
1454 handle = rte_hash_create(¶ms);
1455 if (handle != NULL) {
1456 rte_hash_free(handle);
1457 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
1461 memcpy(¶ms, &ut_params, sizeof(params));
1462 params.name = "creation_with_bad_parameters_2";
1463 params.entries = params.bucket_entries - 1;
1464 handle = rte_hash_create(¶ms);
1465 if (handle != NULL) {
1466 rte_hash_free(handle);
1467 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
1471 memcpy(¶ms, &ut_params, sizeof(params));
1472 params.name = "creation_with_bad_parameters_3";
1473 params.entries = params.entries - 1;
1474 handle = rte_hash_create(¶ms);
1475 if (handle != NULL) {
1476 rte_hash_free(handle);
1477 printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
1481 memcpy(¶ms, &ut_params, sizeof(params));
1482 params.name = "creation_with_bad_parameters_4";
1483 params.bucket_entries = params.bucket_entries - 1;
1484 handle = rte_hash_create(¶ms);
1485 if (handle != NULL) {
1486 rte_hash_free(handle);
1487 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
1491 memcpy(¶ms, &ut_params, sizeof(params));
1492 params.name = "creation_with_bad_parameters_5";
1494 handle = rte_hash_create(¶ms);
1495 if (handle != NULL) {
1496 rte_hash_free(handle);
1497 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1501 memcpy(¶ms, &ut_params, sizeof(params));
1502 params.name = "creation_with_bad_parameters_6";
1503 params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
1504 handle = rte_hash_create(¶ms);
1505 if (handle != NULL) {
1506 rte_hash_free(handle);
1507 printf("Impossible creating hash sucessfully if key_len is greater than the maximun\n");
1514 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1515 0x04, 0x05, 0x06, 0x07,
1516 0x08, 0x09, 0x0a, 0x0b,
1517 0x0c, 0x0d, 0x0e, 0x0f};
1518 static struct rte_hash_parameters hash_params_ex = {
1521 .bucket_entries = 4,
1524 .hash_func_init_val = 0,
1529 * add/delete key with jhash2
1532 test_hash_add_delete_jhash2(void)
1535 struct rte_hash *handle;
1538 hash_params_ex.name = "hash_test_jhash2";
1539 hash_params_ex.key_len = 4;
1540 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1542 handle = rte_hash_create(&hash_params_ex);
1543 if (handle == NULL) {
1544 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1547 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1549 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1553 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1554 if (pos2 < 0 || pos1 != pos2) {
1555 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1562 rte_hash_free(handle);
1568 * add/delete (2) key with jhash2
1571 test_hash_add_delete_2_jhash2(void)
1574 struct rte_hash *handle;
1577 hash_params_ex.name = "hash_test_2_jhash2";
1578 hash_params_ex.key_len = 8;
1579 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1581 handle = rte_hash_create(&hash_params_ex);
1585 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1589 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1590 if (pos2 < 0 || pos1 != pos2)
1597 rte_hash_free(handle);
1603 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1605 const uint32_t *k = key;
1609 return rte_jhash_1word(k[0], initval);
1613 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1615 const uint32_t *k = key;
1619 return rte_jhash_2words(k[0], k[1], initval);
1623 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1625 const uint32_t *k = key;
1629 return rte_jhash_3words(k[0], k[1], k[2], initval);
1633 * add/delete key with jhash 1word
1636 test_hash_add_delete_jhash_1word(void)
1639 struct rte_hash *handle;
1642 hash_params_ex.name = "hash_test_jhash_1word";
1643 hash_params_ex.key_len = 4;
1644 hash_params_ex.hash_func = test_hash_jhash_1word;
1646 handle = rte_hash_create(&hash_params_ex);
1648 goto fail_jhash_1word;
1650 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1652 goto fail_jhash_1word;
1654 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1655 if (pos2 < 0 || pos1 != pos2)
1656 goto fail_jhash_1word;
1662 rte_hash_free(handle);
1668 * add/delete key with jhash 2word
1671 test_hash_add_delete_jhash_2word(void)
1674 struct rte_hash *handle;
1677 hash_params_ex.name = "hash_test_jhash_2word";
1678 hash_params_ex.key_len = 8;
1679 hash_params_ex.hash_func = test_hash_jhash_2word;
1681 handle = rte_hash_create(&hash_params_ex);
1683 goto fail_jhash_2word;
1685 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1687 goto fail_jhash_2word;
1689 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1690 if (pos2 < 0 || pos1 != pos2)
1691 goto fail_jhash_2word;
1697 rte_hash_free(handle);
1703 * add/delete key with jhash 3word
1706 test_hash_add_delete_jhash_3word(void)
1709 struct rte_hash *handle;
1712 hash_params_ex.name = "hash_test_jhash_3word";
1713 hash_params_ex.key_len = 12;
1714 hash_params_ex.hash_func = test_hash_jhash_3word;
1716 handle = rte_hash_create(&hash_params_ex);
1718 goto fail_jhash_3word;
1720 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1722 goto fail_jhash_3word;
1724 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1725 if (pos2 < 0 || pos1 != pos2)
1726 goto fail_jhash_3word;
1732 rte_hash_free(handle);
1738 * Do all unit and performance tests.
1742 if (test_add_delete() < 0)
1744 if (test_hash_add_delete_jhash2() < 0)
1746 if (test_hash_add_delete_2_jhash2() < 0)
1748 if (test_hash_add_delete_jhash_1word() < 0)
1750 if (test_hash_add_delete_jhash_2word() < 0)
1752 if (test_hash_add_delete_jhash_3word() < 0)
1754 if (test_hash_find_existing() < 0)
1756 if (test_add_update_delete() < 0)
1758 if (test_five_keys() < 0)
1760 if (test_full_bucket() < 0)
1762 if (run_all_tbl_perf_tests() < 0)
1764 run_hash_func_tests();
1766 if (test_fbk_hash_find_existing() < 0)
1768 if (fbk_hash_unit_test() < 0)
1770 if (fbk_hash_perf_test() < 0)
1772 if (test_hash_creation_with_bad_parameters() < 0)
1781 printf("The Hash library is not included in this build\n");