app/test/test_hash.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2012 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
  35 #include <stdio.h>
  36 #include <stdint.h>
  37 #include <string.h>
  38 #include <stdlib.h>
  39 #include <stdarg.h>
  40 #include <errno.h>
  41 #include <sys/queue.h>
  42
  43 #include <rte_common.h>
  44 #include <rte_malloc.h>
  45 #include <rte_cycles.h>
  46 #include <rte_random.h>
  47 #include <rte_memory.h>
  48 #include <rte_memzone.h>
  49 #include <rte_tailq.h>
  50 #include <rte_eal.h>
  51 #include <rte_ip.h>
  52 #include <rte_string_fns.h>
  53
  54 #include <rte_hash.h>
  55 #include <rte_fbk_hash.h>
  56 #include <rte_jhash.h>
  57
  58 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
  59 #include <rte_hash_crc.h>
  60 #endif
  61 #include <cmdline_parse.h>
  62
  63 #include "test.h"
  64
  65 #ifdef RTE_LIBRTE_HASH
  66
  67 /* Types of hash table performance test that can be performed */
  68 enum hash_test_t {
  69         ADD_ON_EMPTY,           /*< Add keys to empty table */
  70         DELETE_ON_EMPTY,        /*< Attempt to delete keys from empty table */
  71         LOOKUP_ON_EMPTY,        /*< Attempt to find keys in an empty table */
  72         ADD_UPDATE,             /*< Add/update keys in a full table */
  73         DELETE,                 /*< Delete keys from a full table */
  74         LOOKUP                  /*< Find keys in a full table */
  75 };
  76
  77 /* Function type for hash table operations. */
  78 typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key);
  79
  80 /* Structure to hold parameters used to run a hash table performance test */
  81 struct tbl_perf_test_params {
  82         enum hash_test_t test_type;
  83         uint32_t num_iterations;
  84         uint32_t entries;
  85         uint32_t bucket_entries;
  86         uint32_t key_len;
  87         rte_hash_function hash_func;
  88         uint32_t hash_func_init_val;
  89 };
  90
  91 #define ITERATIONS 10000
  92 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
  93
  94 /*******************************************************************************
  95  * Hash table performance test configuration section.
  96  */
  97 struct tbl_perf_test_params tbl_perf_params[] =
  98 {
  99 /* Small table, add */
 100 /*  Test type | Iterations | Entries | BucketSize | KeyLen |     HashFunc | InitVal */
 101 { ADD_ON_EMPTY,        1024,     1024,           1,      16,     rte_jhash,  0},
 102 { ADD_ON_EMPTY,        1024,     1024,           2,      16,     rte_jhash,  0},
 103 { ADD_ON_EMPTY,        1024,     1024,           4,      16,     rte_jhash,  0},
 104 { ADD_ON_EMPTY,        1024,     1024,           8,      16,     rte_jhash,  0},
 105 { ADD_ON_EMPTY,        1024,     1024,          16,      16,     rte_jhash,  0},
 106 { ADD_ON_EMPTY,        1024,     1024,           1,      32,     rte_jhash,  0},
 107 { ADD_ON_EMPTY,        1024,     1024,           2,      32,     rte_jhash,  0},
 108 { ADD_ON_EMPTY,        1024,     1024,           4,      32,     rte_jhash,  0},
 109 { ADD_ON_EMPTY,        1024,     1024,           8,      32,     rte_jhash,  0},
 110 { ADD_ON_EMPTY,        1024,     1024,          16,      32,     rte_jhash,  0},
 111 { ADD_ON_EMPTY,        1024,     1024,           1,      48,     rte_jhash,  0},
 112 { ADD_ON_EMPTY,        1024,     1024,           2,      48,     rte_jhash,  0},
 113 { ADD_ON_EMPTY,        1024,     1024,           4,      48,     rte_jhash,  0},
 114 { ADD_ON_EMPTY,        1024,     1024,           8,      48,     rte_jhash,  0},
 115 { ADD_ON_EMPTY,        1024,     1024,          16,      48,     rte_jhash,  0},
 116 { ADD_ON_EMPTY,        1024,     1024,           1,      64,     rte_jhash,  0},
 117 { ADD_ON_EMPTY,        1024,     1024,           2,      64,     rte_jhash,  0},
 118 { ADD_ON_EMPTY,        1024,     1024,           4,      64,     rte_jhash,  0},
 119 { ADD_ON_EMPTY,        1024,     1024,           8,      64,     rte_jhash,  0},
 120 { ADD_ON_EMPTY,        1024,     1024,          16,      64,     rte_jhash,  0},
 121 /* Small table, update */
 122 /*  Test type | Iterations | Entries | BucketSize | KeyLen |     HashFunc | InitVal */
 123 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      16,     rte_jhash,  0},
 124 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      16,     rte_jhash,  0},
 125 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      16,     rte_jhash,  0},
 126 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      16,     rte_jhash,  0},
 127 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      16,     rte_jhash,  0},
 128 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      32,     rte_jhash,  0},
 129 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      32,     rte_jhash,  0},
 130 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      32,     rte_jhash,  0},
 131 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      32,     rte_jhash,  0},
 132 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      32,     rte_jhash,  0},
 133 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      48,     rte_jhash,  0},
 134 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      48,     rte_jhash,  0},
 135 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      48,     rte_jhash,  0},
 136 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      48,     rte_jhash,  0},
 137 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      48,     rte_jhash,  0},
 138 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      64,     rte_jhash,  0},
 139 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      64,     rte_jhash,  0},
 140 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      64,     rte_jhash,  0},
 141 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      64,     rte_jhash,  0},
 142 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      64,     rte_jhash,  0},
 143 /* Small table, lookup */
 144 /*  Test type | Iterations | Entries | BucketSize | KeyLen |     HashFunc | InitVal */
 145 {       LOOKUP,  ITERATIONS,     1024,           1,      16,     rte_jhash,  0},
 146 {       LOOKUP,  ITERATIONS,     1024,           2,      16,     rte_jhash,  0},
 147 {       LOOKUP,  ITERATIONS,     1024,           4,      16,     rte_jhash,  0},
 148 {       LOOKUP,  ITERATIONS,     1024,           8,      16,     rte_jhash,  0},
 149 {       LOOKUP,  ITERATIONS,     1024,          16,      16,     rte_jhash,  0},
 150 {       LOOKUP,  ITERATIONS,     1024,           1,      32,     rte_jhash,  0},
 151 {       LOOKUP,  ITERATIONS,     1024,           2,      32,     rte_jhash,  0},
 152 {       LOOKUP,  ITERATIONS,     1024,           4,      32,     rte_jhash,  0},
 153 {       LOOKUP,  ITERATIONS,     1024,           8,      32,     rte_jhash,  0},
 154 {       LOOKUP,  ITERATIONS,     1024,          16,      32,     rte_jhash,  0},
 155 {       LOOKUP,  ITERATIONS,     1024,           1,      48,     rte_jhash,  0},
 156 {       LOOKUP,  ITERATIONS,     1024,           2,      48,     rte_jhash,  0},
 157 {       LOOKUP,  ITERATIONS,     1024,           4,      48,     rte_jhash,  0},
 158 {       LOOKUP,  ITERATIONS,     1024,           8,      48,     rte_jhash,  0},
 159 {       LOOKUP,  ITERATIONS,     1024,          16,      48,     rte_jhash,  0},
 160 {       LOOKUP,  ITERATIONS,     1024,           1,      64,     rte_jhash,  0},
 161 {       LOOKUP,  ITERATIONS,     1024,           2,      64,     rte_jhash,  0},
 162 {       LOOKUP,  ITERATIONS,     1024,           4,      64,     rte_jhash,  0},
 163 {       LOOKUP,  ITERATIONS,     1024,           8,      64,     rte_jhash,  0},
 164 {       LOOKUP,  ITERATIONS,     1024,          16,      64,     rte_jhash,  0},
 165 /* Big table, add */
 166 /* Test type  | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 167 { ADD_ON_EMPTY,     1048576,  1048576,           1,      16,    rte_jhash,   0},
 168 { ADD_ON_EMPTY,     1048576,  1048576,           2,      16,    rte_jhash,   0},
 169 { ADD_ON_EMPTY,     1048576,  1048576,           4,      16,    rte_jhash,   0},
 170 { ADD_ON_EMPTY,     1048576,  1048576,           8,      16,    rte_jhash,   0},
 171 { ADD_ON_EMPTY,     1048576,  1048576,          16,      16,    rte_jhash,   0},
 172 { ADD_ON_EMPTY,     1048576,  1048576,           1,      32,    rte_jhash,   0},
 173 { ADD_ON_EMPTY,     1048576,  1048576,           2,      32,    rte_jhash,   0},
 174 { ADD_ON_EMPTY,     1048576,  1048576,           4,      32,    rte_jhash,   0},
 175 { ADD_ON_EMPTY,     1048576,  1048576,           8,      32,    rte_jhash,   0},
 176 { ADD_ON_EMPTY,     1048576,  1048576,          16,      32,    rte_jhash,   0},
 177 { ADD_ON_EMPTY,     1048576,  1048576,           1,      48,    rte_jhash,   0},
 178 { ADD_ON_EMPTY,     1048576,  1048576,           2,      48,    rte_jhash,   0},
 179 { ADD_ON_EMPTY,     1048576,  1048576,           4,      48,    rte_jhash,   0},
 180 { ADD_ON_EMPTY,     1048576,  1048576,           8,      48,    rte_jhash,   0},
 181 { ADD_ON_EMPTY,     1048576,  1048576,          16,      48,    rte_jhash,   0},
 182 { ADD_ON_EMPTY,     1048576,  1048576,           1,      64,    rte_jhash,   0},
 183 { ADD_ON_EMPTY,     1048576,  1048576,           2,      64,    rte_jhash,   0},
 184 { ADD_ON_EMPTY,     1048576,  1048576,           4,      64,    rte_jhash,   0},
 185 { ADD_ON_EMPTY,     1048576,  1048576,           8,      64,    rte_jhash,   0},
 186 { ADD_ON_EMPTY,     1048576,  1048576,          16,      64,    rte_jhash,   0},
 187 /* Big table, update */
 188 /* Test type  | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 189 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      16,    rte_jhash,   0},
 190 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      16,    rte_jhash,   0},
 191 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      16,    rte_jhash,   0},
 192 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      16,    rte_jhash,   0},
 193 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      16,    rte_jhash,   0},
 194 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      32,    rte_jhash,   0},
 195 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      32,    rte_jhash,   0},
 196 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      32,    rte_jhash,   0},
 197 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      32,    rte_jhash,   0},
 198 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      32,    rte_jhash,   0},
 199 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      48,    rte_jhash,   0},
 200 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      48,    rte_jhash,   0},
 201 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      48,    rte_jhash,   0},
 202 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      48,    rte_jhash,   0},
 203 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      48,    rte_jhash,   0},
 204 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      64,    rte_jhash,   0},
 205 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      64,    rte_jhash,   0},
 206 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      64,    rte_jhash,   0},
 207 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      64,    rte_jhash,   0},
 208 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      64,    rte_jhash,   0},
 209 /* Big table, lookup */
 210 /* Test type  | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 211 {       LOOKUP,  ITERATIONS,  1048576,           1,      16,    rte_jhash,   0},
 212 {       LOOKUP,  ITERATIONS,  1048576,           2,      16,    rte_jhash,   0},
 213 {       LOOKUP,  ITERATIONS,  1048576,           4,      16,    rte_jhash,   0},
 214 {       LOOKUP,  ITERATIONS,  1048576,           8,      16,    rte_jhash,   0},
 215 {       LOOKUP,  ITERATIONS,  1048576,          16,      16,    rte_jhash,   0},
 216 {       LOOKUP,  ITERATIONS,  1048576,           1,      32,    rte_jhash,   0},
 217 {       LOOKUP,  ITERATIONS,  1048576,           2,      32,    rte_jhash,   0},
 218 {       LOOKUP,  ITERATIONS,  1048576,           4,      32,    rte_jhash,   0},
 219 {       LOOKUP,  ITERATIONS,  1048576,           8,      32,    rte_jhash,   0},
 220 {       LOOKUP,  ITERATIONS,  1048576,          16,      32,    rte_jhash,   0},
 221 {       LOOKUP,  ITERATIONS,  1048576,           1,      48,    rte_jhash,   0},
 222 {       LOOKUP,  ITERATIONS,  1048576,           2,      48,    rte_jhash,   0},
 223 {       LOOKUP,  ITERATIONS,  1048576,           4,      48,    rte_jhash,   0},
 224 {       LOOKUP,  ITERATIONS,  1048576,           8,      48,    rte_jhash,   0},
 225 {       LOOKUP,  ITERATIONS,  1048576,          16,      48,    rte_jhash,   0},
 226 {       LOOKUP,  ITERATIONS,  1048576,           1,      64,    rte_jhash,   0},
 227 {       LOOKUP,  ITERATIONS,  1048576,           2,      64,    rte_jhash,   0},
 228 {       LOOKUP,  ITERATIONS,  1048576,           4,      64,    rte_jhash,   0},
 229 {       LOOKUP,  ITERATIONS,  1048576,           8,      64,    rte_jhash,   0},
 230 {       LOOKUP,  ITERATIONS,  1048576,          16,      64,    rte_jhash,   0},
 231
 232 /* Small table, add */
 233 /*  Test type | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 234 { ADD_ON_EMPTY,        1024,     1024,           1,      16, rte_hash_crc,   0},
 235 { ADD_ON_EMPTY,        1024,     1024,           2,      16, rte_hash_crc,   0},
 236 { ADD_ON_EMPTY,        1024,     1024,           4,      16, rte_hash_crc,   0},
 237 { ADD_ON_EMPTY,        1024,     1024,           8,      16, rte_hash_crc,   0},
 238 { ADD_ON_EMPTY,        1024,     1024,          16,      16, rte_hash_crc,   0},
 239 { ADD_ON_EMPTY,        1024,     1024,           1,      32, rte_hash_crc,   0},
 240 { ADD_ON_EMPTY,        1024,     1024,           2,      32, rte_hash_crc,   0},
 241 { ADD_ON_EMPTY,        1024,     1024,           4,      32, rte_hash_crc,   0},
 242 { ADD_ON_EMPTY,        1024,     1024,           8,      32, rte_hash_crc,   0},
 243 { ADD_ON_EMPTY,        1024,     1024,          16,      32, rte_hash_crc,   0},
 244 { ADD_ON_EMPTY,        1024,     1024,           1,      48, rte_hash_crc,   0},
 245 { ADD_ON_EMPTY,        1024,     1024,           2,      48, rte_hash_crc,   0},
 246 { ADD_ON_EMPTY,        1024,     1024,           4,      48, rte_hash_crc,   0},
 247 { ADD_ON_EMPTY,        1024,     1024,           8,      48, rte_hash_crc,   0},
 248 { ADD_ON_EMPTY,        1024,     1024,          16,      48, rte_hash_crc,   0},
 249 { ADD_ON_EMPTY,        1024,     1024,           1,      64, rte_hash_crc,   0},
 250 { ADD_ON_EMPTY,        1024,     1024,           2,      64, rte_hash_crc,   0},
 251 { ADD_ON_EMPTY,        1024,     1024,           4,      64, rte_hash_crc,   0},
 252 { ADD_ON_EMPTY,        1024,     1024,           8,      64, rte_hash_crc,   0},
 253 { ADD_ON_EMPTY,        1024,     1024,          16,      64, rte_hash_crc,   0},
 254 /* Small table, update */
 255 /*  Test type | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 256 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      16, rte_hash_crc,   0},
 257 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      16, rte_hash_crc,   0},
 258 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      16, rte_hash_crc,   0},
 259 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      16, rte_hash_crc,   0},
 260 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      16, rte_hash_crc,   0},
 261 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      32, rte_hash_crc,   0},
 262 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      32, rte_hash_crc,   0},
 263 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      32, rte_hash_crc,   0},
 264 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      32, rte_hash_crc,   0},
 265 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      32, rte_hash_crc,   0},
 266 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      48, rte_hash_crc,   0},
 267 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      48, rte_hash_crc,   0},
 268 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      48, rte_hash_crc,   0},
 269 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      48, rte_hash_crc,   0},
 270 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      48, rte_hash_crc,   0},
 271 {   ADD_UPDATE,  ITERATIONS,     1024,           1,      64, rte_hash_crc,   0},
 272 {   ADD_UPDATE,  ITERATIONS,     1024,           2,      64, rte_hash_crc,   0},
 273 {   ADD_UPDATE,  ITERATIONS,     1024,           4,      64, rte_hash_crc,   0},
 274 {   ADD_UPDATE,  ITERATIONS,     1024,           8,      64, rte_hash_crc,   0},
 275 {   ADD_UPDATE,  ITERATIONS,     1024,          16,      64, rte_hash_crc,   0},
 276 /* Small table, lookup */
 277 /*  Test type | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 278 {       LOOKUP,  ITERATIONS,     1024,           1,      16, rte_hash_crc,   0},
 279 {       LOOKUP,  ITERATIONS,     1024,           2,      16, rte_hash_crc,   0},
 280 {       LOOKUP,  ITERATIONS,     1024,           4,      16, rte_hash_crc,   0},
 281 {       LOOKUP,  ITERATIONS,     1024,           8,      16, rte_hash_crc,   0},
 282 {       LOOKUP,  ITERATIONS,     1024,          16,      16, rte_hash_crc,   0},
 283 {       LOOKUP,  ITERATIONS,     1024,           1,      32, rte_hash_crc,   0},
 284 {       LOOKUP,  ITERATIONS,     1024,           2,      32, rte_hash_crc,   0},
 285 {       LOOKUP,  ITERATIONS,     1024,           4,      32, rte_hash_crc,   0},
 286 {       LOOKUP,  ITERATIONS,     1024,           8,      32, rte_hash_crc,   0},
 287 {       LOOKUP,  ITERATIONS,     1024,          16,      32, rte_hash_crc,   0},
 288 {       LOOKUP,  ITERATIONS,     1024,           1,      48, rte_hash_crc,   0},
 289 {       LOOKUP,  ITERATIONS,     1024,           2,      48, rte_hash_crc,   0},
 290 {       LOOKUP,  ITERATIONS,     1024,           4,      48, rte_hash_crc,   0},
 291 {       LOOKUP,  ITERATIONS,     1024,           8,      48, rte_hash_crc,   0},
 292 {       LOOKUP,  ITERATIONS,     1024,          16,      48, rte_hash_crc,   0},
 293 {       LOOKUP,  ITERATIONS,     1024,           1,      64, rte_hash_crc,   0},
 294 {       LOOKUP,  ITERATIONS,     1024,           2,      64, rte_hash_crc,   0},
 295 {       LOOKUP,  ITERATIONS,     1024,           4,      64, rte_hash_crc,   0},
 296 {       LOOKUP,  ITERATIONS,     1024,           8,      64, rte_hash_crc,   0},
 297 {       LOOKUP,  ITERATIONS,     1024,          16,      64, rte_hash_crc,   0},
 298 /* Big table, add */
 299 /* Test type  | Iterations | Entries | BucketSize | KeyLen |    HashFunc | InitVal */
 300 { ADD_ON_EMPTY,     1048576,  1048576,           1,      16, rte_hash_crc,   0},
 301 { ADD_ON_EMPTY,     1048576,  1048576,           2,      16, rte_hash_crc,   0},
 302 { ADD_ON_EMPTY,     1048576,  1048576,           4,      16, rte_hash_crc,   0},
 303 { ADD_ON_EMPTY,     1048576,  1048576,           8,      16, rte_hash_crc,   0},
 304 { ADD_ON_EMPTY,     1048576,  1048576,          16,      16, rte_hash_crc,   0},
 305 { ADD_ON_EMPTY,     1048576,  1048576,           1,      32, rte_hash_crc,   0},
 306 { ADD_ON_EMPTY,     1048576,  1048576,           2,      32, rte_hash_crc,   0},
 307 { ADD_ON_EMPTY,     1048576,  1048576,           4,      32, rte_hash_crc,   0},
 308 { ADD_ON_EMPTY,     1048576,  1048576,           8,      32, rte_hash_crc,   0},
 309 { ADD_ON_EMPTY,     1048576,  1048576,          16,      32, rte_hash_crc,   0},
 310 { ADD_ON_EMPTY,     1048576,  1048576,           1,      48, rte_hash_crc,   0},
 311 { ADD_ON_EMPTY,     1048576,  1048576,           2,      48, rte_hash_crc,   0},
 312 { ADD_ON_EMPTY,     1048576,  1048576,           4,      48, rte_hash_crc,   0},
 313 { ADD_ON_EMPTY,     1048576,  1048576,           8,      48, rte_hash_crc,   0},
 314 { ADD_ON_EMPTY,     1048576,  1048576,          16,      48, rte_hash_crc,   0},
 315 { ADD_ON_EMPTY,     1048576,  1048576,           1,      64, rte_hash_crc,   0},
 316 { ADD_ON_EMPTY,     1048576,  1048576,           2,      64, rte_hash_crc,   0},
 317 { ADD_ON_EMPTY,     1048576,  1048576,           4,      64, rte_hash_crc,   0},
 318 { ADD_ON_EMPTY,     1048576,  1048576,           8,      64, rte_hash_crc,   0},
 319 { ADD_ON_EMPTY,     1048576,  1048576,          16,      64, rte_hash_crc,   0},
 320 /* Big table, update */
 321 /* Test type  | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
 322 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      16, rte_hash_crc,   0},
 323 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      16, rte_hash_crc,   0},
 324 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      16, rte_hash_crc,   0},
 325 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      16, rte_hash_crc,   0},
 326 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      16, rte_hash_crc,   0},
 327 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      32, rte_hash_crc,   0},
 328 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      32, rte_hash_crc,   0},
 329 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      32, rte_hash_crc,   0},
 330 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      32, rte_hash_crc,   0},
 331 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      32, rte_hash_crc,   0},
 332 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      48, rte_hash_crc,   0},
 333 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      48, rte_hash_crc,   0},
 334 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      48, rte_hash_crc,   0},
 335 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      48, rte_hash_crc,   0},
 336 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      48, rte_hash_crc,   0},
 337 {   ADD_UPDATE,  ITERATIONS,  1048576,           1,      64, rte_hash_crc,   0},
 338 {   ADD_UPDATE,  ITERATIONS,  1048576,           2,      64, rte_hash_crc,   0},
 339 {   ADD_UPDATE,  ITERATIONS,  1048576,           4,      64, rte_hash_crc,   0},
 340 {   ADD_UPDATE,  ITERATIONS,  1048576,           8,      64, rte_hash_crc,   0},
 341 {   ADD_UPDATE,  ITERATIONS,  1048576,          16,      64, rte_hash_crc,   0},
 342 /* Big table, lookup */
 343 /* Test type  | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */
 344 {       LOOKUP,  ITERATIONS,  1048576,           1,      16, rte_hash_crc,   0},
 345 {       LOOKUP,  ITERATIONS,  1048576,           2,      16, rte_hash_crc,   0},
 346 {       LOOKUP,  ITERATIONS,  1048576,           4,      16, rte_hash_crc,   0},
 347 {       LOOKUP,  ITERATIONS,  1048576,           8,      16, rte_hash_crc,   0},
 348 {       LOOKUP,  ITERATIONS,  1048576,          16,      16, rte_hash_crc,   0},
 349 {       LOOKUP,  ITERATIONS,  1048576,           1,      32, rte_hash_crc,   0},
 350 {       LOOKUP,  ITERATIONS,  1048576,           2,      32, rte_hash_crc,   0},
 351 {       LOOKUP,  ITERATIONS,  1048576,           4,      32, rte_hash_crc,   0},
 352 {       LOOKUP,  ITERATIONS,  1048576,           8,      32, rte_hash_crc,   0},
 353 {       LOOKUP,  ITERATIONS,  1048576,          16,      32, rte_hash_crc,   0},
 354 {       LOOKUP,  ITERATIONS,  1048576,           1,      48, rte_hash_crc,   0},
 355 {       LOOKUP,  ITERATIONS,  1048576,           2,      48, rte_hash_crc,   0},
 356 {       LOOKUP,  ITERATIONS,  1048576,           4,      48, rte_hash_crc,   0},
 357 {       LOOKUP,  ITERATIONS,  1048576,           8,      48, rte_hash_crc,   0},
 358 {       LOOKUP,  ITERATIONS,  1048576,          16,      48, rte_hash_crc,   0},
 359 {       LOOKUP,  ITERATIONS,  1048576,           1,      64, rte_hash_crc,   0},
 360 {       LOOKUP,  ITERATIONS,  1048576,           2,      64, rte_hash_crc,   0},
 361 {       LOOKUP,  ITERATIONS,  1048576,           4,      64, rte_hash_crc,   0},
 362 {       LOOKUP,  ITERATIONS,  1048576,           8,      64, rte_hash_crc,   0},
 363 {       LOOKUP,  ITERATIONS,  1048576,          16,      64, rte_hash_crc,   0},
 364 };
 365
 366 /******************************************************************************/
 367
 368 /*******************************************************************************
 369  * Hash function performance test configuration section. Each performance test
 370  * will be performed HASHTEST_ITERATIONS times.
 371  *
 372  * The five arrays below control what tests are performed. Every combination
 373  * from the array entries is tested.
 374  */
 375 #define HASHTEST_ITERATIONS 1000000
 376
 377 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
 378 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
 379 #else
 380 static rte_hash_function hashtest_funcs[] = {rte_jhash};
 381 #endif
 382 static uint32_t hashtest_initvals[] = {0};
 383 static uint32_t hashtest_key_lens[] = {2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
 384 /******************************************************************************/
 385
 386 /*
 387  * Check condition and return an error if true. Assumes that "handle" is the
 388  * name of the hash structure pointer to be freed.
 389  */
 390 #define RETURN_IF_ERROR(cond, str, ...) do {                            \
 391         if (cond) {                                                     \
 392                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
 393                 if (handle) rte_hash_free(handle);                      \
 394                 return -1;                                              \
 395         }                                                               \
 396 } while(0)
 397
 398 #define RETURN_IF_ERROR_FBK(cond, str, ...) do {                                \
 399         if (cond) {                                                     \
 400                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
 401                 if (handle) rte_fbk_hash_free(handle);                  \
 402                 return -1;                                              \
 403         }                                                               \
 404 } while(0)
 405
 406 /* 5-tuple key type */
 407 struct flow_key {
 408         uint32_t ip_src;
 409         uint32_t ip_dst;
 410         uint16_t port_src;
 411         uint16_t port_dst;
 412         uint8_t proto;
 413 } __attribute__((packed));
 414
 415 /*
 416  * Hash function that always returns the same value, to easily test what
 417  * happens when a bucket is full.
 418  */
 419 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
 420                             __attribute__((unused)) uint32_t key_len,
 421                             __attribute__((unused)) uint32_t init_val)
 422 {
 423         return 3;
 424 }
 425
 426 /*
 427  * Print out result of unit test hash operation.
 428  */
 429 #if defined(UNIT_TEST_HASH_VERBOSE)
 430 static void print_key_info(const char *msg, const struct flow_key *key,
 431                                                                 int32_t pos)
 432 {
 433         uint8_t *p = (uint8_t *)key;
 434         unsigned i;
 435
 436         printf("%s key:0x", msg);
 437         for (i = 0; i < sizeof(struct flow_key); i++) {
 438                 printf("%02X", p[i]);
 439         }
 440         printf(" @ pos %d\n", pos);
 441 }
 442 #else
 443 static void print_key_info(__attribute__((unused)) const char *msg,
 444                 __attribute__((unused)) const struct flow_key *key,
 445                 __attribute__((unused)) int32_t pos)
 446 {
 447 }
 448 #endif
 449
 450 /* Keys used by unit test functions */
 451 static struct flow_key keys[5] = { {
 452         .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
 453         .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
 454         .port_src = 0x0908,
 455         .port_dst = 0x0b0a,
 456         .proto = 0x0c,
 457 }, {
 458         .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
 459         .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
 460         .port_src = 0x1918,
 461         .port_dst = 0x1b1a,
 462         .proto = 0x1c,
 463 }, {
 464         .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
 465         .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
 466         .port_src = 0x2928,
 467         .port_dst = 0x2b2a,
 468         .proto = 0x2c,
 469 }, {
 470         .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
 471         .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
 472         .port_src = 0x3938,
 473         .port_dst = 0x3b3a,
 474         .proto = 0x3c,
 475 }, {
 476         .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
 477         .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
 478         .port_src = 0x4948,
 479         .port_dst = 0x4b4a,
 480         .proto = 0x4c,
 481 } };
 482
 483 /* Parameters used for hash table in unit test functions. Name set later. */
 484 static struct rte_hash_parameters ut_params = {
 485         .entries = 64,
 486         .bucket_entries = 4,
 487         .key_len = sizeof(struct flow_key), /* 13 */
 488         .hash_func = rte_jhash,
 489         .hash_func_init_val = 0,
 490         .socket_id = 0,
 491 };
 492
 493 /*
 494  * Basic sequence of operations for a single key:
 495  *      - add
 496  *      - lookup (hit)
 497  *      - delete
 498  *      - lookup (miss)
 499  */
 500 static int test_add_delete(void)
 501 {
 502         struct rte_hash *handle;
 503         int pos0, expectedPos0;
 504
 505         ut_params.name = "test1";
 506         handle = rte_hash_create(&ut_params);
 507         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 508
 509         pos0 = rte_hash_add_key(handle, &keys[0]);
 510         print_key_info("Add", &keys[0], pos0);
 511         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 512         expectedPos0 = pos0;
 513
 514         pos0 = rte_hash_lookup(handle, &keys[0]);
 515         print_key_info("Lkp", &keys[0], pos0);
 516         RETURN_IF_ERROR(pos0 != expectedPos0,
 517                         "failed to find key (pos0=%d)", pos0);
 518
 519         pos0 = rte_hash_del_key(handle, &keys[0]);
 520         print_key_info("Del", &keys[0], pos0);
 521         RETURN_IF_ERROR(pos0 != expectedPos0,
 522                         "failed to delete key (pos0=%d)", pos0);
 523
 524         pos0 = rte_hash_lookup(handle, &keys[0]);
 525         print_key_info("Lkp", &keys[0], pos0);
 526         RETURN_IF_ERROR(pos0 != -ENOENT,
 527                         "fail: found key after deleting! (pos0=%d)", pos0);
 528
 529         rte_hash_free(handle);
 530         return 0;
 531 }
 532
 533 /*
 534  * Sequence of operations for a single key:
 535  *      - delete: miss
 536  *      - add
 537  *      - lookup: hit
 538  *      - add: update
 539  *      - lookup: hit (updated data)
 540  *      - delete: hit
 541  *      - delete: miss
 542  *      - lookup: miss
 543  */
 544 static int test_add_update_delete(void)
 545 {
 546         struct rte_hash *handle;
 547         int pos0, expectedPos0;
 548
 549         ut_params.name = "test2";
 550         handle = rte_hash_create(&ut_params);
 551         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 552
 553         pos0 = rte_hash_del_key(handle, &keys[0]);
 554         print_key_info("Del", &keys[0], pos0);
 555         RETURN_IF_ERROR(pos0 != -ENOENT,
 556                         "fail: found non-existent key (pos0=%d)", pos0);
 557
 558         pos0 = rte_hash_add_key(handle, &keys[0]);
 559         print_key_info("Add", &keys[0], pos0);
 560         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 561         expectedPos0 = pos0;
 562
 563         pos0 = rte_hash_lookup(handle, &keys[0]);
 564         print_key_info("Lkp", &keys[0], pos0);
 565         RETURN_IF_ERROR(pos0 != expectedPos0,
 566                         "failed to find key (pos0=%d)", pos0);
 567
 568         pos0 = rte_hash_add_key(handle, &keys[0]);
 569         print_key_info("Add", &keys[0], pos0);
 570         RETURN_IF_ERROR(pos0 != expectedPos0,
 571                         "failed to re-add key (pos0=%d)", pos0);
 572
 573         pos0 = rte_hash_lookup(handle, &keys[0]);
 574         print_key_info("Lkp", &keys[0], pos0);
 575         RETURN_IF_ERROR(pos0 != expectedPos0,
 576                         "failed to find key (pos0=%d)", pos0);
 577
 578         pos0 = rte_hash_del_key(handle, &keys[0]);
 579         print_key_info("Del", &keys[0], pos0);
 580         RETURN_IF_ERROR(pos0 != expectedPos0,
 581                         "failed to delete key (pos0=%d)", pos0);
 582
 583         pos0 = rte_hash_del_key(handle, &keys[0]);
 584         print_key_info("Del", &keys[0], pos0);
 585         RETURN_IF_ERROR(pos0 != -ENOENT,
 586                         "fail: deleted already deleted key (pos0=%d)", pos0);
 587
 588         pos0 = rte_hash_lookup(handle, &keys[0]);
 589         print_key_info("Lkp", &keys[0], pos0);
 590         RETURN_IF_ERROR(pos0 != -ENOENT,
 591                         "fail: found key after deleting! (pos0=%d)", pos0);
 592
 593         rte_hash_free(handle);
 594         return 0;
 595 }
 596
 597 /*
 598  * Sequence of operations for find existing hash table
 599  *
 600  *  - create table
 601  *  - find existing table: hit
 602  *  - find non-existing table: miss
 603  *
 604  */
 605 static int test_hash_find_existing(void)
 606 {
 607         struct rte_hash *handle = NULL, *result = NULL;
 608
 609         /* Create hash table. */
 610         ut_params.name = "hash_find_existing";
 611         handle = rte_hash_create(&ut_params);
 612         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 613
 614         /* Try to find existing hash table */
 615         result = rte_hash_find_existing("hash_find_existing");
 616         RETURN_IF_ERROR(result != handle, "could not find existing hash table");
 617
 618         /* Try to find non-existing hash table */
 619         result = rte_hash_find_existing("hash_find_non_existing");
 620         RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
 621
 622         /* Cleanup. */
 623         rte_hash_free(handle);
 624
 625         return 0;
 626 }
 627
 628 /*
 629  * Sequence of operations for 5 keys
 630  *      - add keys
 631  *      - lookup keys: hit
 632  *      - add keys (update)
 633  *      - lookup keys: hit (updated data)
 634  *      - delete keys : hit
 635  *      - lookup keys: miss
 636  */
 637 static int test_five_keys(void)
 638 {
 639         struct rte_hash *handle;
 640         const void *key_array[5] = {0};
 641         int pos[5];
 642         int expected_pos[5];
 643         unsigned i;
 644         int ret;
 645
 646         ut_params.name = "test3";
 647         handle = rte_hash_create(&ut_params);
 648         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 649
 650         /* Add */
 651         for (i = 0; i < 5; i++) {
 652                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 653                 print_key_info("Add", &keys[i], pos[i]);
 654                 RETURN_IF_ERROR(pos[i] < 0,
 655                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 656                 expected_pos[i] = pos[i];
 657         }
 658
 659         /* Lookup */
 660         for(i = 0; i < 5; i++)
 661                 key_array[i] = &keys[i];
 662
 663         ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
 664         if(ret == 0)
 665                 for(i = 0; i < 5; i++) {
 666                         print_key_info("Lkp", key_array[i], pos[i]);
 667                         RETURN_IF_ERROR(pos[i] != expected_pos[i],
 668                                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 669                 }
 670
 671         /* Add - update */
 672         for (i = 0; i < 5; i++) {
 673                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 674                 print_key_info("Add", &keys[i], pos[i]);
 675                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 676                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 677         }
 678
 679         /* Lookup */
 680         for (i = 0; i < 5; i++) {
 681                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 682                 print_key_info("Lkp", &keys[i], pos[i]);
 683                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 684                                 "failed to find key (pos[%u]=%d)", i, pos[i]);
 685         }
 686
 687         /* Delete */
 688         for (i = 0; i < 5; i++) {
 689                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 690                 print_key_info("Del", &keys[i], pos[i]);
 691                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 692                                 "failed to delete key (pos[%u]=%d)", i, pos[i]);
 693         }
 694
 695         /* Lookup */
 696         for (i = 0; i < 5; i++) {
 697                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 698                 print_key_info("Lkp", &keys[i], pos[i]);
 699                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 700                                 "failed to find key (pos[%u]=%d)", i, pos[i]);
 701         }
 702
 703         rte_hash_free(handle);
 704
 705         return 0;
 706 }
 707
 708 /*
 709  * Add keys to the same bucket until bucket full.
 710  *      - add 5 keys to the same bucket (hash created with 4 keys per bucket):
 711  *              first 4 successful, 5th unsuccessful
 712  *      - lookup the 5 keys: 4 hits, 1 miss
 713  *      - add the 5 keys again: 4 OK, one error as bucket is full
 714  *      - lookup the 5 keys: 4 hits (updated data), 1 miss
 715  *      - delete the 5 keys: 5 OK (even if the 5th is not in the table)
 716  *      - lookup the 5 keys: 5 misses
 717  *      - add the 5th key: OK
 718  *      - lookup the 5th key: hit
 719  */
 720 static int test_full_bucket(void)
 721 {
 722         struct rte_hash_parameters params_pseudo_hash = {
 723                 .name = "test4",
 724                 .entries = 64,
 725                 .bucket_entries = 4,
 726                 .key_len = sizeof(struct flow_key), /* 13 */
 727                 .hash_func = pseudo_hash,
 728                 .hash_func_init_val = 0,
 729                 .socket_id = 0,
 730         };
 731         struct rte_hash *handle;
 732         int pos[5];
 733         int expected_pos[5];
 734         unsigned i;
 735
 736         handle = rte_hash_create(&params_pseudo_hash);
 737         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 738
 739         /* Fill bucket*/
 740         for (i = 0; i < 4; i++) {
 741                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 742                 print_key_info("Add", &keys[i], pos[i]);
 743                 RETURN_IF_ERROR(pos[i] < 0,
 744                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 745                 expected_pos[i] = pos[i];
 746         }
 747         /* This shouldn't work because the bucket is full */
 748         pos[4] = rte_hash_add_key(handle, &keys[4]);
 749         print_key_info("Add", &keys[4], pos[4]);
 750         RETURN_IF_ERROR(pos[4] != -ENOSPC,
 751                         "fail: added key to full bucket (pos[4]=%d)", pos[4]);
 752
 753         /* Lookup */
 754         for (i = 0; i < 4; i++) {
 755                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 756                 print_key_info("Lkp", &keys[i], pos[i]);
 757                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 758                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 759         }
 760         pos[4] = rte_hash_lookup(handle, &keys[4]);
 761         print_key_info("Lkp", &keys[4], pos[4]);
 762         RETURN_IF_ERROR(pos[4] != -ENOENT,
 763                         "fail: found non-existent key (pos[4]=%d)", pos[4]);
 764
 765         /* Add - update */
 766         for (i = 0; i < 4; i++) {
 767                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 768                 print_key_info("Add", &keys[i], pos[i]);
 769                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 770                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 771         }
 772         pos[4] = rte_hash_add_key(handle, &keys[4]);
 773         print_key_info("Add", &keys[4], pos[4]);
 774         RETURN_IF_ERROR(pos[4] != -ENOSPC,
 775                         "fail: added key to full bucket (pos[4]=%d)", pos[4]);
 776
 777         /* Lookup */
 778         for (i = 0; i < 4; i++) {
 779                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 780                 print_key_info("Lkp", &keys[i], pos[i]);
 781                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 782                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 783         }
 784         pos[4] = rte_hash_lookup(handle, &keys[4]);
 785         print_key_info("Lkp", &keys[4], pos[4]);
 786         RETURN_IF_ERROR(pos[4] != -ENOENT,
 787                         "fail: found non-existent key (pos[4]=%d)", pos[4]);
 788
 789         /* Delete 1 key, check other keys are still found */
 790         pos[1] = rte_hash_del_key(handle, &keys[1]);
 791         print_key_info("Del", &keys[1], pos[1]);
 792         RETURN_IF_ERROR(pos[1] != expected_pos[1],
 793                         "failed to delete key (pos[1]=%d)", pos[1]);
 794         pos[3] = rte_hash_lookup(handle, &keys[3]);
 795         print_key_info("Lkp", &keys[3], pos[3]);
 796         RETURN_IF_ERROR(pos[3] != expected_pos[3],
 797                         "failed lookup after deleting key from same bucket "
 798                         "(pos[3]=%d)", pos[3]);
 799
 800         /* Go back to previous state */
 801         pos[1] = rte_hash_add_key(handle, &keys[1]);
 802         print_key_info("Add", &keys[1], pos[1]);
 803         expected_pos[1] = pos[1];
 804         RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
 805
 806         /* Delete */
 807         for (i = 0; i < 4; i++) {
 808                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 809                 print_key_info("Del", &keys[i], pos[i]);
 810                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 811                         "failed to delete key (pos[%u]=%d)", i, pos[i]);
 812         }
 813         pos[4] = rte_hash_del_key(handle, &keys[4]);
 814         print_key_info("Del", &keys[4], pos[4]);
 815         RETURN_IF_ERROR(pos[4] != -ENOENT,
 816                         "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
 817
 818         /* Lookup */
 819         for (i = 0; i < 4; i++) {
 820                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 821                 print_key_info("Lkp", &keys[i], pos[i]);
 822                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 823                         "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
 824         }
 825
 826         /* Add and lookup the 5th key */
 827         pos[4] = rte_hash_add_key(handle, &keys[4]);
 828         print_key_info("Add", &keys[4], pos[4]);
 829         RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
 830         expected_pos[4] = pos[4];
 831         pos[4] = rte_hash_lookup(handle, &keys[4]);
 832         print_key_info("Lkp", &keys[4], pos[4]);
 833         RETURN_IF_ERROR(pos[4] != expected_pos[4],
 834                         "failed to find key (pos[4]=%d)", pos[4]);
 835
 836         rte_hash_free(handle);
 837
 838         /* Cover the NULL case. */
 839         rte_hash_free(0);
 840         return 0;
 841 }
 842
 843 /*
 844  * To help print out name of hash functions.
 845  */
 846 static const char *get_hash_name(rte_hash_function f)
 847 {
 848         if (f == rte_jhash)
 849                 return "jhash";
 850
 851         if (f == rte_hash_crc)
 852                 return "rte_hash_crc";
 853
 854         return "UnknownHash";
 855 }
 856
 857 /*
 858  * Find average of array of numbers.
 859  */
 860 static double
 861 get_avg(const uint32_t *array, uint32_t size)
 862 {
 863         double sum = 0;
 864         unsigned i;
 865         for (i = 0; i < size; i++)
 866                 sum += array[i];
 867         return sum / (double)size;
 868 }
 869
 870 /*
 871  * Do a single performance test, of one type of operation.
 872  *
 873  * @param h
 874  *   hash table to run test on
 875  * @param func
 876  *   function to call (add, delete or lookup function)
 877  * @param avg_occupancy
 878  *   The average number of entries in each bucket of the hash table
 879  * @param invalid_pos_count
 880  *   The amount of errors (e.g. due to a full bucket).
 881  * @return
 882  *   The average number of ticks per hash function call. A negative number
 883  *   signifies failure.
 884  */
 885 static double
 886 run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func,
 887                 const struct tbl_perf_test_params *params, double *avg_occupancy,
 888                 uint32_t *invalid_pos_count)
 889 {
 890         uint64_t begin, end, ticks = 0;
 891         uint8_t *key = NULL;
 892         uint32_t *bucket_occupancies = NULL;
 893         uint32_t num_buckets, i, j;
 894         int32_t pos;
 895
 896         /* Initialise */
 897         num_buckets = params->entries / params->bucket_entries;
 898         key = (uint8_t *) rte_zmalloc("hash key",
 899                         params->key_len * sizeof(uint8_t), 16);
 900         if (key == NULL)
 901                 return -1;
 902
 903         bucket_occupancies = (uint32_t *) rte_zmalloc("bucket occupancies",
 904                         num_buckets * sizeof(uint32_t), 16);
 905         if (bucket_occupancies == NULL) {
 906                 rte_free(key);
 907                 return -1;
 908         }
 909
 910         ticks = 0;
 911         *invalid_pos_count = 0;
 912
 913         for (i = 0; i < params->num_iterations; i++) {
 914                 /* Prepare inputs for the current iteration */
 915                 for (j = 0; j < params->key_len; j++)
 916                         key[j] = (uint8_t) rte_rand();
 917
 918                 /* Perform operation, and measure time it takes */
 919                 begin = rte_rdtsc();
 920                 pos = func(h, key);
 921                 end = rte_rdtsc();
 922                 ticks += end - begin;
 923
 924                 /* Other work per iteration */
 925                 if (pos < 0)
 926                         *invalid_pos_count += 1;
 927                 else
 928                         bucket_occupancies[pos / params->bucket_entries]++;
 929         }
 930         *avg_occupancy = get_avg(bucket_occupancies, num_buckets);
 931
 932         rte_free(bucket_occupancies);
 933         rte_free(key);
 934
 935         return (double)ticks / params->num_iterations;
 936 }
 937
 938 /*
 939  * To help print out what tests are being done.
 940  */
 941 static const char *
 942 get_tbl_perf_test_desc(enum hash_test_t type)
 943 {
 944         switch (type){
 945         case ADD_ON_EMPTY: return "Add on Empty";
 946         case DELETE_ON_EMPTY: return "Delete on Empty";
 947         case LOOKUP_ON_EMPTY: return "Lookup on Empty";
 948         case ADD_UPDATE: return "Add Update";
 949         case DELETE: return "Delete";
 950         case LOOKUP: return "Lookup";
 951         default: return "UNKNOWN";
 952         }
 953 }
 954
 955 /*
 956  * Run a hash table performance test based on params.
 957  */
 958 static int
 959 run_tbl_perf_test(struct tbl_perf_test_params *params)
 960 {
 961         static unsigned calledCount = 5;
 962         struct rte_hash_parameters hash_params = {
 963                 .entries = params->entries,
 964                 .bucket_entries = params->bucket_entries,
 965                 .key_len = params->key_len,
 966                 .hash_func = params->hash_func,
 967                 .hash_func_init_val = params->hash_func_init_val,
 968                 .socket_id = 0,
 969         };
 970         struct rte_hash *handle;
 971         double avg_occupancy = 0, ticks = 0;
 972         uint32_t num_iterations, invalid_pos;
 973         char name[RTE_HASH_NAMESIZE];
 974         char hashname[RTE_HASH_NAMESIZE];
 975
 976         rte_snprintf(name, 32, "test%u", calledCount++);
 977         hash_params.name = name;
 978
 979         handle = rte_hash_create(&hash_params);
 980         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 981
 982         switch (params->test_type){
 983         case ADD_ON_EMPTY:
 984                 ticks = run_single_tbl_perf_test(handle, rte_hash_add_key,
 985                                 params, &avg_occupancy, &invalid_pos);
 986                 break;
 987         case DELETE_ON_EMPTY:
 988                 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
 989                                 params, &avg_occupancy, &invalid_pos);
 990                 break;
 991         case LOOKUP_ON_EMPTY:
 992                 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
 993                                 params, &avg_occupancy, &invalid_pos);
 994                 break;
 995         case ADD_UPDATE:
 996                 num_iterations = params->num_iterations;
 997                 params->num_iterations = params->entries;
 998                 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
 999                                 &avg_occupancy, &invalid_pos);
1000                 params->num_iterations = num_iterations;
1001                 ticks = run_single_tbl_perf_test(handle, rte_hash_add_key,
1002                                 params, &avg_occupancy, &invalid_pos);
1003                 break;
1004         case DELETE:
1005                 num_iterations = params->num_iterations;
1006                 params->num_iterations = params->entries;
1007                 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
1008                                 &avg_occupancy, &invalid_pos);
1009
1010                 params->num_iterations = num_iterations;
1011                 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
1012                                 params, &avg_occupancy, &invalid_pos);
1013                 break;
1014         case LOOKUP:
1015                 num_iterations = params->num_iterations;
1016                 params->num_iterations = params->entries;
1017                 run_single_tbl_perf_test(handle, rte_hash_add_key, params,
1018                                 &avg_occupancy, &invalid_pos);
1019
1020                 params->num_iterations = num_iterations;
1021                 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
1022                                 params, &avg_occupancy, &invalid_pos);
1023                 break;
1024         default: return -1;
1025         }
1026
1027         rte_snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func));
1028
1029         printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n",
1030                 hashname,
1031                 get_tbl_perf_test_desc(params->test_type),
1032                 (unsigned) params->key_len,
1033                 (unsigned) params->entries,
1034                 (unsigned) params->bucket_entries,
1035                 (unsigned) invalid_pos,
1036                 avg_occupancy,
1037                 ticks
1038         );
1039
1040         /* Free */
1041         rte_hash_free(handle);
1042         return 0;
1043 }
1044
1045 /*
1046  * Run all hash table performance tests.
1047  */
1048 static int run_all_tbl_perf_tests(void)
1049 {
1050         unsigned i;
1051
1052         printf(" *** Hash table performance test results ***\n");
1053         printf("Hash Func.  , Operation      , Key size (bytes), Entries, "
1054                "Entries per bucket, Errors  , Avg. bucket entries, Ticks/Op.\n");
1055
1056         /* Loop through every combination of test parameters */
1057         for (i = 0;
1058              i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params);
1059              i++) {
1060
1061                 /* Perform test */
1062                 if (run_tbl_perf_test(&tbl_perf_params[i]) < 0)
1063                         return -1;
1064         }
1065         return 0;
1066 }
1067
1068 /*
1069  * Test a hash function.
1070  */
1071 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
1072                 uint32_t key_len)
1073 {
1074         static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
1075         uint64_t ticks = 0, start, end;
1076         unsigned i, j;
1077
1078         for (i = 0; i < HASHTEST_ITERATIONS; i++) {
1079
1080                 for (j = 0; j < key_len; j++)
1081                         key[j] = (uint8_t) rte_rand();
1082
1083                 start = rte_rdtsc();
1084                 f(key, key_len, init_val);
1085                 end = rte_rdtsc();
1086                 ticks += end - start;
1087         }
1088
1089         printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
1090                         (unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
1091 }
1092
1093 /*
1094  * Test all hash functions.
1095  */
1096 static void run_hash_func_tests(void)
1097 {
1098         unsigned i, j, k;
1099
1100         printf("\n\n *** Hash function performance test results ***\n");
1101         printf(" Number of iterations for each test = %d\n",
1102                         HASHTEST_ITERATIONS);
1103         printf("Hash Func.  , Key Length (bytes), Initial value, Ticks/Op.\n");
1104
1105         for (i = 0;
1106              i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
1107              i++) {
1108                 for (j = 0;
1109                      j < sizeof(hashtest_initvals) / sizeof(uint32_t);
1110                      j++) {
1111                         for (k = 0;
1112                              k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
1113                              k++) {
1114                                 run_hash_func_test(hashtest_funcs[i],
1115                                                 hashtest_initvals[j],
1116                                                 hashtest_key_lens[k]);
1117                         }
1118                 }
1119         }
1120 }
1121
1122 /******************************************************************************/
1123 static int
1124 fbk_hash_unit_test(void)
1125 {
1126         struct rte_fbk_hash_params params = {
1127                 .name = "fbk_hash_test",
1128                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1129                 .entries_per_bucket = 4,
1130                 .socket_id = 0,
1131         };
1132
1133         struct rte_fbk_hash_params invalid_params_1 = {
1134                 .name = "invalid_1",
1135                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
1136                 .entries_per_bucket = 4,
1137                 .socket_id = 0,
1138         };
1139
1140         struct rte_fbk_hash_params invalid_params_2 = {
1141                 .name = "invalid_4",
1142                 .entries = 4,
1143                 .entries_per_bucket = 3,         /* Not power of 2 */
1144                 .socket_id = 0,
1145         };
1146
1147         struct rte_fbk_hash_params invalid_params_3 = {
1148                 .name = "invalid_2",
1149                 .entries = 0,                    /* Entries is 0 */
1150                 .entries_per_bucket = 4,
1151                 .socket_id = 0,
1152         };
1153
1154         struct rte_fbk_hash_params invalid_params_4 = {
1155                 .name = "invalid_3",
1156                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1157                 .entries_per_bucket = 0,         /* Entries per bucket is 0 */
1158                 .socket_id = 0,
1159         };
1160
1161         struct rte_fbk_hash_params invalid_params_5 = {
1162                 .name = "invalid_4",
1163                 .entries = 4,
1164                 .entries_per_bucket = 8,         /* Entries per bucket > entries */
1165                 .socket_id = 0,
1166         };
1167
1168         struct rte_fbk_hash_params invalid_params_6 = {
1169                 .name = "invalid_5",
1170                 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2,   /* Entries > max allowed */
1171                 .entries_per_bucket = 4,
1172                 .socket_id = 0,
1173         };
1174
1175         struct rte_fbk_hash_params params_jhash = {
1176                 .name = "valid",
1177                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1178                 .entries_per_bucket = 4,
1179                 .socket_id = 0,
1180                 .hash_func = rte_jhash_1word,              /* Tests for different hash_func */
1181                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1182         };
1183
1184         struct rte_fbk_hash_params params_nohash = {
1185                 .name = "valid nohash",
1186                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1187                 .entries_per_bucket = 4,
1188                 .socket_id = 0,
1189                 .hash_func = 0,                            /* Tests for null hash_func */
1190                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1191         };
1192
1193         struct rte_fbk_hash_table *handle;
1194         uint32_t keys[5] =
1195                 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1196         uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
1197         int status;
1198         unsigned i;
1199         double used_entries;
1200
1201         /* Try creating hashes with invalid parameters */
1202         handle = rte_fbk_hash_create(&invalid_params_1);
1203         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1204
1205         handle = rte_fbk_hash_create(&invalid_params_2);
1206         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1207
1208         handle = rte_fbk_hash_create(&invalid_params_3);
1209         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1210
1211         handle = rte_fbk_hash_create(&invalid_params_4);
1212         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1213
1214         handle = rte_fbk_hash_create(&invalid_params_5);
1215         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1216
1217         handle = rte_fbk_hash_create(&invalid_params_6);
1218         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1219
1220         /* Create empty jhash hash. */
1221         handle = rte_fbk_hash_create(&params_jhash);
1222         RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
1223
1224         /* Cleanup. */
1225         rte_fbk_hash_free(handle);
1226
1227         /* Create empty jhash hash. */
1228         handle = rte_fbk_hash_create(&params_nohash);
1229         RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
1230
1231         /* Cleanup. */
1232         rte_fbk_hash_free(handle);
1233
1234         /* Create empty hash. */
1235         handle = rte_fbk_hash_create(&params);
1236         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1237
1238         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1239         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1240                                 "load factor right after creation is not zero but it should be");
1241         /* Add keys. */
1242         for (i = 0; i < 5; i++) {
1243                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1244                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1245         }
1246
1247         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1248         RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
1249                                 "load factor now is not as expected");
1250         /* Find value of added keys. */
1251         for (i = 0; i < 5; i++) {
1252                 status = rte_fbk_hash_lookup(handle, keys[i]);
1253                 RETURN_IF_ERROR_FBK(status != vals[i],
1254                                 "fbk hash lookup failed");
1255         }
1256
1257         /* Change value of added keys. */
1258         for (i = 0; i < 5; i++) {
1259                 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
1260                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
1261         }
1262
1263         /* Find new values. */
1264         for (i = 0; i < 5; i++) {
1265                 status = rte_fbk_hash_lookup(handle, keys[i]);
1266                 RETURN_IF_ERROR_FBK(status != vals[4-i],
1267                                 "fbk hash lookup failed");
1268         }
1269
1270         /* Delete keys individually. */
1271         for (i = 0; i < 5; i++) {
1272                 status = rte_fbk_hash_delete_key(handle, keys[i]);
1273                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
1274         }
1275
1276         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1277         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1278                                 "load factor right after deletion is not zero but it should be");
1279         /* Lookup should now fail. */
1280         for (i = 0; i < 5; i++) {
1281                 status = rte_fbk_hash_lookup(handle, keys[i]);
1282                 RETURN_IF_ERROR_FBK(status == 0,
1283                                 "fbk hash lookup should have failed");
1284         }
1285
1286         /* Add keys again. */
1287         for (i = 0; i < 5; i++) {
1288                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1289                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1290         }
1291
1292         /* Make sure they were added. */
1293         for (i = 0; i < 5; i++) {
1294                 status = rte_fbk_hash_lookup(handle, keys[i]);
1295                 RETURN_IF_ERROR_FBK(status != vals[i],
1296                                 "fbk hash lookup failed");
1297         }
1298
1299         /* Clear all entries. */
1300         rte_fbk_hash_clear_all(handle);
1301
1302         /* Lookup should fail. */
1303         for (i = 0; i < 5; i++) {
1304                 status = rte_fbk_hash_lookup(handle, keys[i]);
1305                 RETURN_IF_ERROR_FBK(status == 0,
1306                                 "fbk hash lookup should have failed");
1307         }
1308
1309         /* Cleanup. */
1310         rte_fbk_hash_free(handle);
1311
1312         /* Cover the NULL case. */
1313         rte_fbk_hash_free(0);
1314
1315         return 0;
1316 }
1317
1318 /* Control operation of performance testing of fbk hash. */
1319 #define LOAD_FACTOR 0.667       /* How full to make the hash table. */
1320 #define TEST_SIZE 1000000       /* How many operations to time. */
1321 #define TEST_ITERATIONS 30      /* How many measurements to take. */
1322 #define ENTRIES (1 << 15)       /* How many entries. */
1323
1324 static int
1325 fbk_hash_perf_test(void)
1326 {
1327         struct rte_fbk_hash_params params = {
1328                 .name = "fbk_hash_test",
1329                 .entries = ENTRIES,
1330                 .entries_per_bucket = 4,
1331                 .socket_id = 0,
1332         };
1333         struct rte_fbk_hash_table *handle;
1334         uint32_t keys[ENTRIES] = {0};
1335         unsigned indexes[TEST_SIZE];
1336         uint64_t lookup_time = 0;
1337         unsigned added = 0;
1338         unsigned value = 0;
1339         unsigned i, j;
1340
1341         handle = rte_fbk_hash_create(&params);
1342         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1343
1344         /* Generate random keys and values. */
1345         for (i = 0; i < ENTRIES; i++) {
1346                 uint32_t key = (uint32_t)rte_rand();
1347                 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
1348                 uint16_t val = (uint16_t)rte_rand();
1349
1350                 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
1351                         keys[added] = key;
1352                         added++;
1353                 }
1354                 if (added > (LOAD_FACTOR * ENTRIES)) {
1355                         break;
1356                 }
1357         }
1358
1359         for (i = 0; i < TEST_ITERATIONS; i++) {
1360                 uint64_t begin;
1361                 uint64_t end;
1362
1363                 /* Generate random indexes into keys[] array. */
1364                 for (j = 0; j < TEST_SIZE; j++) {
1365                         indexes[j] = rte_rand() % added;
1366                 }
1367
1368                 begin = rte_rdtsc();
1369                 /* Do lookups */
1370                 for (j = 0; j < TEST_SIZE; j++) {
1371                         value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
1372                 }
1373                 end = rte_rdtsc();
1374                 lookup_time += (double)(end - begin);
1375         }
1376
1377         printf("\n\n *** FBK Hash function performance test results ***\n");
1378         /*
1379          * The use of the 'value' variable ensures that the hash lookup is not
1380          * being optimised out by the compiler.
1381          */
1382         if (value != 0)
1383                 printf("Number of ticks per lookup = %g\n",
1384                         (double)lookup_time /
1385                         ((double)TEST_ITERATIONS * (double)TEST_SIZE));
1386
1387         rte_fbk_hash_free(handle);
1388
1389         return 0;
1390 }
1391
1392 /*
1393  * Sequence of operations for find existing fbk hash table
1394  *
1395  *  - create table
1396  *  - find existing table: hit
1397  *  - find non-existing table: miss
1398  *
1399  */
1400 static int test_fbk_hash_find_existing(void)
1401 {
1402         struct rte_fbk_hash_params params = {
1403                         .name = "fbk_hash_find_existing",
1404                         .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1405                         .entries_per_bucket = 4,
1406                         .socket_id = 0,
1407         };
1408         struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1409
1410         /* Create hash table. */
1411         handle = rte_fbk_hash_create(&params);
1412         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1413
1414         /* Try to find existing fbk hash table */
1415         result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
1416         RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
1417
1418         /* Try to find non-existing fbk hash table */
1419         result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1420         RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
1421
1422         /* Cleanup. */
1423         rte_fbk_hash_free(handle);
1424
1425         return 0;
1426 }
1427
1428 /*
1429  * Do tests for hash creation with bad parameters.
1430  */
1431 static int test_hash_creation_with_bad_parameters(void)
1432 {
1433         struct rte_hash *handle;
1434         struct rte_hash_parameters params;
1435
1436         handle = rte_hash_create(NULL);
1437         if (handle != NULL) {
1438                 rte_hash_free(handle);
1439                 printf("Impossible creating hash sucessfully without any parameter\n");
1440                 return -1;
1441         }
1442
1443         memcpy(&params, &ut_params, sizeof(params));
1444         params.name = "creation_with_bad_parameters_0";
1445         params.entries = RTE_HASH_ENTRIES_MAX + 1;
1446         handle = rte_hash_create(&params);
1447         if (handle != NULL) {
1448                 rte_hash_free(handle);
1449                 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
1450                 return -1;
1451         }
1452
1453         memcpy(&params, &ut_params, sizeof(params));
1454         params.name = "creation_with_bad_parameters_1";
1455         params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
1456         handle = rte_hash_create(&params);
1457         if (handle != NULL) {
1458                 rte_hash_free(handle);
1459                 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
1460                 return -1;
1461         }
1462
1463         memcpy(&params, &ut_params, sizeof(params));
1464         params.name = "creation_with_bad_parameters_2";
1465         params.entries = params.bucket_entries - 1;
1466         handle = rte_hash_create(&params);
1467         if (handle != NULL) {
1468                 rte_hash_free(handle);
1469                 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
1470                 return -1;
1471         }
1472
1473         memcpy(&params, &ut_params, sizeof(params));
1474         params.name = "creation_with_bad_parameters_3";
1475         params.entries = params.entries - 1;
1476         handle = rte_hash_create(&params);
1477         if (handle != NULL) {
1478                 rte_hash_free(handle);
1479                 printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
1480                 return -1;
1481         }
1482
1483         memcpy(&params, &ut_params, sizeof(params));
1484         params.name = "creation_with_bad_parameters_4";
1485         params.bucket_entries = params.bucket_entries - 1;
1486         handle = rte_hash_create(&params);
1487         if (handle != NULL) {
1488                 rte_hash_free(handle);
1489                 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
1490                 return -1;
1491         }
1492
1493         memcpy(&params, &ut_params, sizeof(params));
1494         params.name = "creation_with_bad_parameters_5";
1495         params.key_len = 0;
1496         handle = rte_hash_create(&params);
1497         if (handle != NULL) {
1498                 rte_hash_free(handle);
1499                 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1500                 return -1;
1501         }
1502
1503         memcpy(&params, &ut_params, sizeof(params));
1504         params.name = "creation_with_bad_parameters_6";
1505         params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
1506         handle = rte_hash_create(&params);
1507         if (handle != NULL) {
1508                 rte_hash_free(handle);
1509                 printf("Impossible creating hash sucessfully if key_len is greater than the maximun\n");
1510                 return -1;
1511         }
1512
1513         return 0;
1514 }
1515
1516 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1517                         0x04, 0x05, 0x06, 0x07,
1518                         0x08, 0x09, 0x0a, 0x0b,
1519                         0x0c, 0x0d, 0x0e, 0x0f};
1520 static struct rte_hash_parameters hash_params_ex = {
1521         .name = NULL,
1522         .entries = 64,
1523         .bucket_entries = 4,
1524         .key_len = 0,
1525         .hash_func = NULL,
1526         .hash_func_init_val = 0,
1527         .socket_id = 0,
1528 };
1529
1530 /*
1531  * add/delete key with jhash2
1532  */
1533 static int
1534 test_hash_add_delete_jhash2(void)
1535 {
1536         int ret = -1;
1537         struct rte_hash *handle;
1538         int32_t pos1, pos2;
1539
1540         hash_params_ex.name = "hash_test_jhash2";
1541         hash_params_ex.key_len = 4;
1542         hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1543
1544         handle = rte_hash_create(&hash_params_ex);
1545         if (handle == NULL) {
1546                 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1547                 goto fail_jhash2;
1548         }
1549         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1550         if (pos1 < 0) {
1551                 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1552                 goto fail_jhash2;
1553         }
1554
1555         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1556         if (pos2 < 0 || pos1 != pos2) {
1557                 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1558                 goto fail_jhash2;
1559         }
1560         ret = 0;
1561
1562 fail_jhash2:
1563         if (handle != NULL)
1564                 rte_hash_free(handle);
1565
1566         return ret;
1567 }
1568
1569 /*
1570  * add/delete (2) key with jhash2
1571  */
1572 static int
1573 test_hash_add_delete_2_jhash2(void)
1574 {
1575         int ret = -1;
1576         struct rte_hash *handle;
1577         int32_t pos1, pos2;
1578
1579         hash_params_ex.name = "hash_test_2_jhash2";
1580         hash_params_ex.key_len = 8;
1581         hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1582
1583         handle = rte_hash_create(&hash_params_ex);
1584         if (handle == NULL)
1585                 goto fail_2_jhash2;
1586
1587         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1588         if (pos1 < 0)
1589                 goto fail_2_jhash2;
1590
1591         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1592         if (pos2 < 0 || pos1 != pos2)
1593                 goto fail_2_jhash2;
1594
1595         ret = 0;
1596
1597 fail_2_jhash2:
1598         if (handle != NULL)
1599                 rte_hash_free(handle);
1600
1601         return ret;
1602 }
1603
1604 static uint32_t
1605 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1606 {
1607         const uint32_t *k = key;
1608
1609         length =length;
1610
1611         return rte_jhash_1word(k[0], initval);
1612 }
1613
1614 static uint32_t
1615 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1616 {
1617         const uint32_t *k = key;
1618
1619         length =length;
1620
1621         return rte_jhash_2words(k[0], k[1], initval);
1622 }
1623
1624 static uint32_t
1625 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1626 {
1627         const uint32_t *k = key;
1628
1629         length =length;
1630
1631         return rte_jhash_3words(k[0], k[1], k[2], initval);
1632 }
1633
1634 /*
1635  * add/delete key with jhash 1word
1636  */
1637 static int
1638 test_hash_add_delete_jhash_1word(void)
1639 {
1640         int ret = -1;
1641         struct rte_hash *handle;
1642         int32_t pos1, pos2;
1643
1644         hash_params_ex.name = "hash_test_jhash_1word";
1645         hash_params_ex.key_len = 4;
1646         hash_params_ex.hash_func = test_hash_jhash_1word;
1647
1648         handle = rte_hash_create(&hash_params_ex);
1649         if (handle == NULL)
1650                 goto fail_jhash_1word;
1651
1652         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1653         if (pos1 < 0)
1654                 goto fail_jhash_1word;
1655
1656         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1657         if (pos2 < 0 || pos1 != pos2)
1658                 goto fail_jhash_1word;
1659
1660         ret = 0;
1661
1662 fail_jhash_1word:
1663         if (handle != NULL)
1664                 rte_hash_free(handle);
1665
1666         return ret;
1667 }
1668
1669 /*
1670  * add/delete key with jhash 2word
1671  */
1672 static int
1673 test_hash_add_delete_jhash_2word(void)
1674 {
1675         int ret = -1;
1676         struct rte_hash *handle;
1677         int32_t pos1, pos2;
1678
1679         hash_params_ex.name = "hash_test_jhash_2word";
1680         hash_params_ex.key_len = 8;
1681         hash_params_ex.hash_func = test_hash_jhash_2word;
1682
1683         handle = rte_hash_create(&hash_params_ex);
1684         if (handle == NULL)
1685                 goto fail_jhash_2word;
1686
1687         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1688         if (pos1 < 0)
1689                 goto fail_jhash_2word;
1690
1691         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1692         if (pos2 < 0 || pos1 != pos2)
1693                 goto fail_jhash_2word;
1694
1695         ret = 0;
1696
1697 fail_jhash_2word:
1698         if (handle != NULL)
1699                 rte_hash_free(handle);
1700
1701         return ret;
1702 }
1703
1704 /*
1705  * add/delete key with jhash 3word
1706  */
1707 static int
1708 test_hash_add_delete_jhash_3word(void)
1709 {
1710         int ret = -1;
1711         struct rte_hash *handle;
1712         int32_t pos1, pos2;
1713
1714         hash_params_ex.name = "hash_test_jhash_3word";
1715         hash_params_ex.key_len = 12;
1716         hash_params_ex.hash_func = test_hash_jhash_3word;
1717
1718         handle = rte_hash_create(&hash_params_ex);
1719         if (handle == NULL)
1720                 goto fail_jhash_3word;
1721
1722         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1723         if (pos1 < 0)
1724                 goto fail_jhash_3word;
1725
1726         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1727         if (pos2 < 0 || pos1 != pos2)
1728                 goto fail_jhash_3word;
1729
1730         ret = 0;
1731
1732 fail_jhash_3word:
1733         if (handle != NULL)
1734                 rte_hash_free(handle);
1735
1736         return ret;
1737 }
1738
1739 /*
1740  * Do all unit and performance tests.
1741  */
1742 int test_hash(void)
1743 {
1744         if (test_add_delete() < 0)
1745                 return -1;
1746         if (test_hash_add_delete_jhash2() < 0)
1747                 return -1;
1748         if (test_hash_add_delete_2_jhash2() < 0)
1749                 return -1;
1750         if (test_hash_add_delete_jhash_1word() < 0)
1751                 return -1;
1752         if (test_hash_add_delete_jhash_2word() < 0)
1753                 return -1;
1754         if (test_hash_add_delete_jhash_3word() < 0)
1755                 return -1;
1756         if (test_hash_find_existing() < 0)
1757                 return -1;
1758         if (test_add_update_delete() < 0)
1759                 return -1;
1760         if (test_five_keys() < 0)
1761                 return -1;
1762         if (test_full_bucket() < 0)
1763                 return -1;
1764         if (run_all_tbl_perf_tests() < 0)
1765                 return -1;
1766         run_hash_func_tests();
1767
1768         if (test_fbk_hash_find_existing() < 0)
1769                 return -1;
1770         if (fbk_hash_unit_test() < 0)
1771                 return -1;
1772         if (fbk_hash_perf_test() < 0)
1773                 return -1;
1774         if (test_hash_creation_with_bad_parameters() < 0)
1775                 return -1;
1776         return 0;
1777 }
1778 #else
1779
1780 int
1781 test_hash(void)
1782 {
1783         printf("The Hash library is not included in this build\n");
1784         return 0;
1785 }
1786
1787 #endif