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  *  version: DPDK.L.1.2.3-3
  34  */
  35
  36 #include <stdio.h>
  37 #include <stdint.h>
  38 #include <string.h>
  39 #include <stdlib.h>
  40 #include <stdarg.h>
  41 #include <errno.h>
  42 #include <sys/queue.h>
  43
  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>
  50 #include <rte_hash.h>
  51 #include <rte_hash_crc.h>
  52 #include <rte_jhash.h>
  53 #include <rte_tailq.h>
  54 #include <rte_eal.h>
  55 #include <rte_fbk_hash.h>
  56 #include <rte_ip.h>
  57 #include <rte_string_fns.h>
  58
  59 #include <cmdline_parse.h>
  60
  61 #include "test.h"
  62
  63 #ifdef RTE_LIBRTE_HASH
  64
  65 /* Types of hash table performance test that can be performed */
  66 enum hash_test_t {
  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 */
  73 };
  74
  75 /* Function type for hash table operations. */
  76 typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key);
  77
  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;
  82         uint32_t entries;
  83         uint32_t bucket_entries;
  84         uint32_t key_len;
  85         rte_hash_function hash_func;
  86         uint32_t hash_func_init_val;
  87 };
  88
  89 #define ITERATIONS 10000
  90 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
  91
  92 /*******************************************************************************
  93  * Hash table performance test configuration section.
  94  */
  95 struct tbl_perf_test_params tbl_perf_params[] =
  96 {
  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},
 163 /* Big table, add */
 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},
 229
 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},
 296 /* Big table, add */
 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},
 362 };
 363
 364 /******************************************************************************/
 365
 366 /*******************************************************************************
 367  * Hash function performance test configuration section. Each performance test
 368  * will be performed HASHTEST_ITERATIONS times.
 369  *
 370  * The five arrays below control what tests are performed. Every combination
 371  * from the array entries is tested.
 372  */
 373 #define HASHTEST_ITERATIONS 1000000
 374
 375 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
 376 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
 377 #else
 378 static rte_hash_function hashtest_funcs[] = {rte_jhash};
 379 #endif
 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 /******************************************************************************/
 383
 384 /*
 385  * Check condition and return an error if true. Assumes that "handle" is the
 386  * name of the hash structure pointer to be freed.
 387  */
 388 #define RETURN_IF_ERROR(cond, str, ...) do {                            \
 389         if (cond) {                                                     \
 390                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
 391                 if (handle) rte_hash_free(handle);                      \
 392                 return -1;                                              \
 393         }                                                               \
 394 } while(0)
 395
 396 #define RETURN_IF_ERROR_FBK(cond, str, ...) do {                                \
 397         if (cond) {                                                     \
 398                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
 399                 if (handle) rte_fbk_hash_free(handle);                  \
 400                 return -1;                                              \
 401         }                                                               \
 402 } while(0)
 403
 404 /* 5-tuple key type */
 405 struct flow_key {
 406         uint32_t ip_src;
 407         uint32_t ip_dst;
 408         uint16_t port_src;
 409         uint16_t port_dst;
 410         uint8_t proto;
 411 } __attribute__((packed));
 412
 413 /*
 414  * Hash function that always returns the same value, to easily test what
 415  * happens when a bucket is full.
 416  */
 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)
 420 {
 421         return 3;
 422 }
 423
 424 /*
 425  * Print out result of unit test hash operation.
 426  */
 427 #if defined(UNIT_TEST_HASH_VERBOSE)
 428 static void print_key_info(const char *msg, const struct flow_key *key,
 429                                                                 int32_t pos)
 430 {
 431         uint8_t *p = (uint8_t *)key;
 432         unsigned i;
 433
 434         printf("%s key:0x", msg);
 435         for (i = 0; i < sizeof(struct flow_key); i++) {
 436                 printf("%02X", p[i]);
 437         }
 438         printf(" @ pos %d\n", pos);
 439 }
 440 #else
 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)
 444 {
 445 }
 446 #endif
 447
 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),
 452         .port_src = 0x0908,
 453         .port_dst = 0x0b0a,
 454         .proto = 0x0c,
 455 }, {
 456         .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
 457         .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
 458         .port_src = 0x1918,
 459         .port_dst = 0x1b1a,
 460         .proto = 0x1c,
 461 }, {
 462         .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
 463         .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
 464         .port_src = 0x2928,
 465         .port_dst = 0x2b2a,
 466         .proto = 0x2c,
 467 }, {
 468         .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
 469         .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
 470         .port_src = 0x3938,
 471         .port_dst = 0x3b3a,
 472         .proto = 0x3c,
 473 }, {
 474         .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
 475         .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
 476         .port_src = 0x4948,
 477         .port_dst = 0x4b4a,
 478         .proto = 0x4c,
 479 } };
 480
 481 /* Parameters used for hash table in unit test functions. Name set later. */
 482 static struct rte_hash_parameters ut_params = {
 483         .entries = 64,
 484         .bucket_entries = 4,
 485         .key_len = sizeof(struct flow_key), /* 13 */
 486         .hash_func = rte_jhash,
 487         .hash_func_init_val = 0,
 488         .socket_id = 0,
 489 };
 490
 491 /*
 492  * Basic sequence of operations for a single key:
 493  *      - add
 494  *      - lookup (hit)
 495  *      - delete
 496  *      - lookup (miss)
 497  */
 498 static int test_add_delete(void)
 499 {
 500         struct rte_hash *handle;
 501         int pos0, expectedPos0;
 502
 503         ut_params.name = "test1";
 504         handle = rte_hash_create(&ut_params);
 505         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 506
 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);
 510         expectedPos0 = pos0;
 511
 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);
 516
 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);
 521
 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);
 526
 527         rte_hash_free(handle);
 528         return 0;
 529 }
 530
 531 /*
 532  * Sequence of operations for a single key:
 533  *      - delete: miss
 534  *      - add
 535  *      - lookup: hit
 536  *      - add: update
 537  *      - lookup: hit (updated data)
 538  *      - delete: hit
 539  *      - delete: miss
 540  *      - lookup: miss
 541  */
 542 static int test_add_update_delete(void)
 543 {
 544         struct rte_hash *handle;
 545         int pos0, expectedPos0;
 546
 547         ut_params.name = "test2";
 548         handle = rte_hash_create(&ut_params);
 549         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 550
 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);
 555
 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);
 559         expectedPos0 = pos0;
 560
 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);
 565
 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);
 570
 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);
 575
 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);
 580
 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);
 585
 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);
 590
 591         rte_hash_free(handle);
 592         return 0;
 593 }
 594
 595 /*
 596  * Sequence of operations for find existing hash table
 597  *
 598  *  - create table
 599  *  - find existing table: hit
 600  *  - find non-existing table: miss
 601  *
 602  */
 603 static int test_hash_find_existing(void)
 604 {
 605         struct rte_hash *handle = NULL, *result = NULL;
 606
 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");
 611
 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");
 615
 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");
 619
 620         /* Cleanup. */
 621         rte_hash_free(handle);
 622
 623         return 0;
 624 }
 625
 626 /*
 627  * Sequence of operations for 5 keys
 628  *      - add keys
 629  *      - lookup keys: hit
 630  *      - add keys (update)
 631  *      - lookup keys: hit (updated data)
 632  *      - delete keys : hit
 633  *      - lookup keys: miss
 634  */
 635 static int test_five_keys(void)
 636 {
 637         struct rte_hash *handle;
 638         const void *key_array[5] = {0};
 639         int pos[5];
 640         int expected_pos[5];
 641         unsigned i;
 642         int ret;
 643
 644         ut_params.name = "test3";
 645         handle = rte_hash_create(&ut_params);
 646         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 647
 648         /* Add */
 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];
 655         }
 656
 657         /* Lookup */
 658         for(i = 0; i < 5; i++)
 659                 key_array[i] = &keys[i];
 660
 661         ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
 662         if(ret == 0)
 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]);
 667                 }
 668
 669         /* Add - update */
 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]);
 675         }
 676
 677         /* Lookup */
 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]);
 683         }
 684
 685         /* Delete */
 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]);
 691         }
 692
 693         /* Lookup */
 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]);
 699         }
 700
 701         rte_hash_free(handle);
 702
 703         return 0;
 704 }
 705
 706 /*
 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
 717  */
 718 static int test_full_bucket(void)
 719 {
 720         struct rte_hash_parameters params_pseudo_hash = {
 721                 .name = "test4",
 722                 .entries = 64,
 723                 .bucket_entries = 4,
 724                 .key_len = sizeof(struct flow_key), /* 13 */
 725                 .hash_func = pseudo_hash,
 726                 .hash_func_init_val = 0,
 727                 .socket_id = 0,
 728         };
 729         struct rte_hash *handle;
 730         int pos[5];
 731         int expected_pos[5];
 732         unsigned i;
 733
 734         handle = rte_hash_create(&params_pseudo_hash);
 735         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 736
 737         /* Fill bucket*/
 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];
 744         }
 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]);
 750
 751         /* Lookup */
 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]);
 757         }
 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]);
 762
 763         /* Add - update */
 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]);
 769         }
 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]);
 774
 775         /* Lookup */
 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]);
 781         }
 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]);
 786
 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]);
 797
 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]);
 803
 804         /* Delete */
 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]);
 810         }
 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]);
 815
 816         /* Lookup */
 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]);
 822         }
 823
 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]);
 833
 834         rte_hash_free(handle);
 835
 836         /* Cover the NULL case. */
 837         rte_hash_free(0);
 838         return 0;
 839 }
 840
 841 /*
 842  * To help print out name of hash functions.
 843  */
 844 static const char *get_hash_name(rte_hash_function f)
 845 {
 846         if (f == rte_jhash)
 847                 return "jhash";
 848
 849         if (f == rte_hash_crc)
 850                 return "rte_hash_crc";
 851
 852         return "UnknownHash";
 853 }
 854
 855 /*
 856  * Find average of array of numbers.
 857  */
 858 static double
 859 get_avg(const uint32_t *array, uint32_t size)
 860 {
 861         double sum = 0;
 862         unsigned i;
 863         for (i = 0; i < size; i++)
 864                 sum += array[i];
 865         return sum / (double)size;
 866 }
 867
 868 /*
 869  * Do a single performance test, of one type of operation.
 870  *
 871  * @param h
 872  *   hash table to run test on
 873  * @param func
 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).
 879  * @return
 880  *   The average number of ticks per hash function call. A negative number
 881  *   signifies failure.
 882  */
 883 static double
 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)
 887 {
 888         uint64_t begin, end, ticks = 0;
 889         uint8_t *key = NULL;
 890         uint32_t *bucket_occupancies = NULL;
 891         uint32_t num_buckets, i, j;
 892         int32_t pos;
 893
 894         /* Initialise */
 895         num_buckets = params->entries / params->bucket_entries;
 896         key = (uint8_t *) rte_zmalloc("hash key",
 897                         params->key_len * sizeof(uint8_t), 16);
 898         if (key == NULL)
 899                 return -1;
 900
 901         bucket_occupancies = (uint32_t *) rte_zmalloc("bucket occupancies",
 902                         num_buckets * sizeof(uint32_t), 16);
 903         if (bucket_occupancies == NULL) {
 904                 rte_free(key);
 905                 return -1;
 906         }
 907
 908         ticks = 0;
 909         *invalid_pos_count = 0;
 910
 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();
 915
 916                 /* Perform operation, and measure time it takes */
 917                 begin = rte_rdtsc();
 918                 pos = func(h, key);
 919                 end = rte_rdtsc();
 920                 ticks += end - begin;
 921
 922                 /* Other work per iteration */
 923                 if (pos < 0)
 924                         *invalid_pos_count += 1;
 925                 else
 926                         bucket_occupancies[pos / params->bucket_entries]++;
 927         }
 928         *avg_occupancy = get_avg(bucket_occupancies, num_buckets);
 929
 930         rte_free(bucket_occupancies);
 931         rte_free(key);
 932
 933         return (double)ticks / params->num_iterations;
 934 }
 935
 936 /*
 937  * To help print out what tests are being done.
 938  */
 939 static const char *
 940 get_tbl_perf_test_desc(enum hash_test_t type)
 941 {
 942         switch (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";
 950         }
 951 }
 952
 953 /*
 954  * Run a hash table performance test based on params.
 955  */
 956 static int
 957 run_tbl_perf_test(struct tbl_perf_test_params *params)
 958 {
 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,
 966                 .socket_id = 0,
 967         };
 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];
 973
 974         rte_snprintf(name, 32, "test%u", calledCount++);
 975         hash_params.name = name;
 976
 977         handle = rte_hash_create(&hash_params);
 978         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 979
 980         switch (params->test_type){
 981         case ADD_ON_EMPTY:
 982                 ticks = run_single_tbl_perf_test(handle, rte_hash_add_key,
 983                                 params, &avg_occupancy, &invalid_pos);
 984                 break;
 985         case DELETE_ON_EMPTY:
 986                 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
 987                                 params, &avg_occupancy, &invalid_pos);
 988                 break;
 989         case LOOKUP_ON_EMPTY:
 990                 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
 991                                 params, &avg_occupancy, &invalid_pos);
 992                 break;
 993         case ADD_UPDATE:
 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);
1001                 break;
1002         case DELETE:
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);
1007
1008                 params->num_iterations = num_iterations;
1009                 ticks = run_single_tbl_perf_test(handle, rte_hash_del_key,
1010                                 params, &avg_occupancy, &invalid_pos);
1011                 break;
1012         case LOOKUP:
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);
1017
1018                 params->num_iterations = num_iterations;
1019                 ticks = run_single_tbl_perf_test(handle, rte_hash_lookup,
1020                                 params, &avg_occupancy, &invalid_pos);
1021                 break;
1022         default: return -1;
1023         }
1024
1025         rte_snprintf(hashname, RTE_HASH_NAMESIZE, "%s", get_hash_name(params->hash_func));
1026
1027         printf("%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\n",
1028                 hashname,
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,
1034                 avg_occupancy,
1035                 ticks
1036         );
1037
1038         /* Free */
1039         rte_hash_free(handle);
1040         return 0;
1041 }
1042
1043 /*
1044  * Run all hash table performance tests.
1045  */
1046 static int run_all_tbl_perf_tests(void)
1047 {
1048         unsigned i;
1049
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");
1053
1054         /* Loop through every combination of test parameters */
1055         for (i = 0;
1056              i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params);
1057              i++) {
1058
1059                 /* Perform test */
1060                 if (run_tbl_perf_test(&tbl_perf_params[i]) < 0)
1061                         return -1;
1062         }
1063         return 0;
1064 }
1065
1066 /*
1067  * Test a hash function.
1068  */
1069 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
1070                 uint32_t key_len)
1071 {
1072         static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
1073         uint64_t ticks = 0, start, end;
1074         unsigned i, j;
1075
1076         for (i = 0; i < HASHTEST_ITERATIONS; i++) {
1077
1078                 for (j = 0; j < key_len; j++)
1079                         key[j] = (uint8_t) rte_rand();
1080
1081                 start = rte_rdtsc();
1082                 f(key, key_len, init_val);
1083                 end = rte_rdtsc();
1084                 ticks += end - start;
1085         }
1086
1087         printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
1088                         (unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
1089 }
1090
1091 /*
1092  * Test all hash functions.
1093  */
1094 static void run_hash_func_tests(void)
1095 {
1096         unsigned i, j, k;
1097
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");
1102
1103         for (i = 0;
1104              i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
1105              i++) {
1106                 for (j = 0;
1107                      j < sizeof(hashtest_initvals) / sizeof(uint32_t);
1108                      j++) {
1109                         for (k = 0;
1110                              k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
1111                              k++) {
1112                                 run_hash_func_test(hashtest_funcs[i],
1113                                                 hashtest_initvals[j],
1114                                                 hashtest_key_lens[k]);
1115                         }
1116                 }
1117         }
1118 }
1119
1120 /******************************************************************************/
1121 static int
1122 fbk_hash_unit_test(void)
1123 {
1124         struct rte_fbk_hash_params params = {
1125                 .name = "fbk_hash_test",
1126                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1127                 .entries_per_bucket = 4,
1128                 .socket_id = 0,
1129         };
1130
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,
1135                 .socket_id = 0,
1136         };
1137
1138         struct rte_fbk_hash_params invalid_params_2 = {
1139                 .name = "invalid_4",
1140                 .entries = 4,
1141                 .entries_per_bucket = 3,         /* Not power of 2 */
1142                 .socket_id = 0,
1143         };
1144
1145         struct rte_fbk_hash_params invalid_params_3 = {
1146                 .name = "invalid_2",
1147                 .entries = 0,                    /* Entries is 0 */
1148                 .entries_per_bucket = 4,
1149                 .socket_id = 0,
1150         };
1151
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 */
1156                 .socket_id = 0,
1157         };
1158
1159         struct rte_fbk_hash_params invalid_params_5 = {
1160                 .name = "invalid_4",
1161                 .entries = 4,
1162                 .entries_per_bucket = 8,         /* Entries per bucket > entries */
1163                 .socket_id = 0,
1164         };
1165
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,
1170                 .socket_id = 0,
1171         };
1172
1173         struct rte_fbk_hash_params params_jhash = {
1174                 .name = "valid",
1175                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1176                 .entries_per_bucket = 4,
1177                 .socket_id = 0,
1178                 .hash_func = rte_jhash_1word,              /* Tests for different hash_func */
1179                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1180         };
1181
1182         struct rte_fbk_hash_params params_nohash = {
1183                 .name = "valid nohash",
1184                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1185                 .entries_per_bucket = 4,
1186                 .socket_id = 0,
1187                 .hash_func = 0,                            /* Tests for null hash_func */
1188                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1189         };
1190
1191         struct rte_fbk_hash_table *handle;
1192         uint32_t keys[5] =
1193                 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1194         uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
1195         int status;
1196         unsigned i;
1197         double used_entries;
1198
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");
1202
1203         handle = rte_fbk_hash_create(&invalid_params_2);
1204         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1205
1206         handle = rte_fbk_hash_create(&invalid_params_3);
1207         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1208
1209         handle = rte_fbk_hash_create(&invalid_params_4);
1210         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1211
1212         handle = rte_fbk_hash_create(&invalid_params_5);
1213         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1214
1215         handle = rte_fbk_hash_create(&invalid_params_6);
1216         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1217
1218         /* Create empty jhash hash. */
1219         handle = rte_fbk_hash_create(&params_jhash);
1220         RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
1221
1222         /* Cleanup. */
1223         rte_fbk_hash_free(handle);
1224
1225         /* Create empty jhash hash. */
1226         handle = rte_fbk_hash_create(&params_nohash);
1227         RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
1228
1229         /* Cleanup. */
1230         rte_fbk_hash_free(handle);
1231
1232         /* Create empty hash. */
1233         handle = rte_fbk_hash_create(&params);
1234         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1235
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");
1239         /* Add keys. */
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");
1243         }
1244
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");
1253         }
1254
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");
1259         }
1260
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");
1266         }
1267
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");
1272         }
1273
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");
1282         }
1283
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");
1288         }
1289
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");
1295         }
1296
1297         /* Clear all entries. */
1298         rte_fbk_hash_clear_all(handle);
1299
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");
1305         }
1306
1307         /* Cleanup. */
1308         rte_fbk_hash_free(handle);
1309
1310         /* Cover the NULL case. */
1311         rte_fbk_hash_free(0);
1312
1313         return 0;
1314 }
1315
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. */
1321
1322 static int
1323 fbk_hash_perf_test(void)
1324 {
1325         struct rte_fbk_hash_params params = {
1326                 .name = "fbk_hash_test",
1327                 .entries = ENTRIES,
1328                 .entries_per_bucket = 4,
1329                 .socket_id = 0,
1330         };
1331         struct rte_fbk_hash_table *handle;
1332         uint32_t keys[ENTRIES] = {0};
1333         unsigned indexes[TEST_SIZE];
1334         uint64_t lookup_time = 0;
1335         unsigned added = 0;
1336         unsigned value = 0;
1337         unsigned i, j;
1338
1339         handle = rte_fbk_hash_create(&params);
1340         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1341
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();
1347
1348                 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
1349                         keys[added] = key;
1350                         added++;
1351                 }
1352                 if (added > (LOAD_FACTOR * ENTRIES)) {
1353                         break;
1354                 }
1355         }
1356
1357         for (i = 0; i < TEST_ITERATIONS; i++) {
1358                 uint64_t begin;
1359                 uint64_t end;
1360
1361                 /* Generate random indexes into keys[] array. */
1362                 for (j = 0; j < TEST_SIZE; j++) {
1363                         indexes[j] = rte_rand() % added;
1364                 }
1365
1366                 begin = rte_rdtsc();
1367                 /* Do lookups */
1368                 for (j = 0; j < TEST_SIZE; j++) {
1369                         value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
1370                 }
1371                 end = rte_rdtsc();
1372                 lookup_time += (double)(end - begin);
1373         }
1374
1375         printf("\n\n *** FBK Hash function performance test results ***\n");
1376         /*
1377          * The use of the 'value' variable ensures that the hash lookup is not
1378          * being optimised out by the compiler.
1379          */
1380         if (value != 0)
1381                 printf("Number of ticks per lookup = %g\n",
1382                         (double)lookup_time /
1383                         ((double)TEST_ITERATIONS * (double)TEST_SIZE));
1384
1385         rte_fbk_hash_free(handle);
1386
1387         return 0;
1388 }
1389
1390 /*
1391  * Sequence of operations for find existing fbk hash table
1392  *
1393  *  - create table
1394  *  - find existing table: hit
1395  *  - find non-existing table: miss
1396  *
1397  */
1398 static int test_fbk_hash_find_existing(void)
1399 {
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,
1404                         .socket_id = 0,
1405         };
1406         struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1407
1408         /* Create hash table. */
1409         handle = rte_fbk_hash_create(&params);
1410         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1411
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");
1415
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");
1419
1420         /* Cleanup. */
1421         rte_fbk_hash_free(handle);
1422
1423         return 0;
1424 }
1425
1426 /*
1427  * Do tests for hash creation with bad parameters.
1428  */
1429 static int test_hash_creation_with_bad_parameters(void)
1430 {
1431         struct rte_hash *handle;
1432         struct rte_hash_parameters params;
1433
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");
1438                 return -1;
1439         }
1440
1441         memcpy(&params, &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(&params);
1445         if (handle != NULL) {
1446                 rte_hash_free(handle);
1447                 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
1448                 return -1;
1449         }
1450
1451         memcpy(&params, &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(&params);
1455         if (handle != NULL) {
1456                 rte_hash_free(handle);
1457                 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
1458                 return -1;
1459         }
1460
1461         memcpy(&params, &ut_params, sizeof(params));
1462         params.name = "creation_with_bad_parameters_2";
1463         params.entries = params.bucket_entries - 1;
1464         handle = rte_hash_create(&params);
1465         if (handle != NULL) {
1466                 rte_hash_free(handle);
1467                 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
1468                 return -1;
1469         }
1470
1471         memcpy(&params, &ut_params, sizeof(params));
1472         params.name = "creation_with_bad_parameters_3";
1473         params.entries = params.entries - 1;
1474         handle = rte_hash_create(&params);
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");
1478                 return -1;
1479         }
1480
1481         memcpy(&params, &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(&params);
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");
1488                 return -1;
1489         }
1490
1491         memcpy(&params, &ut_params, sizeof(params));
1492         params.name = "creation_with_bad_parameters_5";
1493         params.key_len = 0;
1494         handle = rte_hash_create(&params);
1495         if (handle != NULL) {
1496                 rte_hash_free(handle);
1497                 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1498                 return -1;
1499         }
1500
1501         memcpy(&params, &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(&params);
1505         if (handle != NULL) {
1506                 rte_hash_free(handle);
1507                 printf("Impossible creating hash sucessfully if key_len is greater than the maximun\n");
1508                 return -1;
1509         }
1510
1511         return 0;
1512 }
1513
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 = {
1519         .name = NULL,
1520         .entries = 64,
1521         .bucket_entries = 4,
1522         .key_len = 0,
1523         .hash_func = NULL,
1524         .hash_func_init_val = 0,
1525         .socket_id = 0,
1526 };
1527
1528 /*
1529  * add/delete key with jhash2
1530  */
1531 static int
1532 test_hash_add_delete_jhash2(void)
1533 {
1534         int ret = -1;
1535         struct rte_hash *handle;
1536         int32_t pos1, pos2;
1537
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;
1541
1542         handle = rte_hash_create(&hash_params_ex);
1543         if (handle == NULL) {
1544                 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1545                 goto fail_jhash2;
1546         }
1547         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1548         if (pos1 < 0) {
1549                 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1550                 goto fail_jhash2;
1551         }
1552
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");
1556                 goto fail_jhash2;
1557         }
1558         ret = 0;
1559
1560 fail_jhash2:
1561         if (handle != NULL)
1562                 rte_hash_free(handle);
1563
1564         return ret;
1565 }
1566
1567 /*
1568  * add/delete (2) key with jhash2
1569  */
1570 static int
1571 test_hash_add_delete_2_jhash2(void)
1572 {
1573         int ret = -1;
1574         struct rte_hash *handle;
1575         int32_t pos1, pos2;
1576
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;
1580
1581         handle = rte_hash_create(&hash_params_ex);
1582         if (handle == NULL)
1583                 goto fail_2_jhash2;
1584
1585         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1586         if (pos1 < 0)
1587                 goto fail_2_jhash2;
1588
1589         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1590         if (pos2 < 0 || pos1 != pos2)
1591                 goto fail_2_jhash2;
1592
1593         ret = 0;
1594
1595 fail_2_jhash2:
1596         if (handle != NULL)
1597                 rte_hash_free(handle);
1598
1599         return ret;
1600 }
1601
1602 static uint32_t
1603 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1604 {
1605         const uint32_t *k = key;
1606
1607         length =length;
1608
1609         return rte_jhash_1word(k[0], initval);
1610 }
1611
1612 static uint32_t
1613 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1614 {
1615         const uint32_t *k = key;
1616
1617         length =length;
1618
1619         return rte_jhash_2words(k[0], k[1], initval);
1620 }
1621
1622 static uint32_t
1623 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1624 {
1625         const uint32_t *k = key;
1626
1627         length =length;
1628
1629         return rte_jhash_3words(k[0], k[1], k[2], initval);
1630 }
1631
1632 /*
1633  * add/delete key with jhash 1word
1634  */
1635 static int
1636 test_hash_add_delete_jhash_1word(void)
1637 {
1638         int ret = -1;
1639         struct rte_hash *handle;
1640         int32_t pos1, pos2;
1641
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;
1645
1646         handle = rte_hash_create(&hash_params_ex);
1647         if (handle == NULL)
1648                 goto fail_jhash_1word;
1649
1650         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1651         if (pos1 < 0)
1652                 goto fail_jhash_1word;
1653
1654         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1655         if (pos2 < 0 || pos1 != pos2)
1656                 goto fail_jhash_1word;
1657
1658         ret = 0;
1659
1660 fail_jhash_1word:
1661         if (handle != NULL)
1662                 rte_hash_free(handle);
1663
1664         return ret;
1665 }
1666
1667 /*
1668  * add/delete key with jhash 2word
1669  */
1670 static int
1671 test_hash_add_delete_jhash_2word(void)
1672 {
1673         int ret = -1;
1674         struct rte_hash *handle;
1675         int32_t pos1, pos2;
1676
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;
1680
1681         handle = rte_hash_create(&hash_params_ex);
1682         if (handle == NULL)
1683                 goto fail_jhash_2word;
1684
1685         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1686         if (pos1 < 0)
1687                 goto fail_jhash_2word;
1688
1689         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1690         if (pos2 < 0 || pos1 != pos2)
1691                 goto fail_jhash_2word;
1692
1693         ret = 0;
1694
1695 fail_jhash_2word:
1696         if (handle != NULL)
1697                 rte_hash_free(handle);
1698
1699         return ret;
1700 }
1701
1702 /*
1703  * add/delete key with jhash 3word
1704  */
1705 static int
1706 test_hash_add_delete_jhash_3word(void)
1707 {
1708         int ret = -1;
1709         struct rte_hash *handle;
1710         int32_t pos1, pos2;
1711
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;
1715
1716         handle = rte_hash_create(&hash_params_ex);
1717         if (handle == NULL)
1718                 goto fail_jhash_3word;
1719
1720         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1721         if (pos1 < 0)
1722                 goto fail_jhash_3word;
1723
1724         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1725         if (pos2 < 0 || pos1 != pos2)
1726                 goto fail_jhash_3word;
1727
1728         ret = 0;
1729
1730 fail_jhash_3word:
1731         if (handle != NULL)
1732                 rte_hash_free(handle);
1733
1734         return ret;
1735 }
1736
1737 /*
1738  * Do all unit and performance tests.
1739  */
1740 int test_hash(void)
1741 {
1742         if (test_add_delete() < 0)
1743                 return -1;
1744         if (test_hash_add_delete_jhash2() < 0)
1745                 return -1;
1746         if (test_hash_add_delete_2_jhash2() < 0)
1747                 return -1;
1748         if (test_hash_add_delete_jhash_1word() < 0)
1749                 return -1;
1750         if (test_hash_add_delete_jhash_2word() < 0)
1751                 return -1;
1752         if (test_hash_add_delete_jhash_3word() < 0)
1753                 return -1;
1754         if (test_hash_find_existing() < 0)
1755                 return -1;
1756         if (test_add_update_delete() < 0)
1757                 return -1;
1758         if (test_five_keys() < 0)
1759                 return -1;
1760         if (test_full_bucket() < 0)
1761                 return -1;
1762         if (run_all_tbl_perf_tests() < 0)
1763                 return -1;
1764         run_hash_func_tests();
1765
1766         if (test_fbk_hash_find_existing() < 0)
1767                 return -1;
1768         if (fbk_hash_unit_test() < 0)
1769                 return -1;
1770         if (fbk_hash_perf_test() < 0)
1771                 return -1;
1772         if (test_hash_creation_with_bad_parameters() < 0)
1773                 return -1;
1774         return 0;
1775 }
1776 #else
1777
1778 int
1779 test_hash(void)
1780 {
1781         printf("The Hash library is not included in this build\n");
1782         return 0;
1783 }
1784
1785 #endif