lib/librte_table/rte_table_hash_key32.c

   1 /*-
   2  *       BSD LICENSE
   3  *
   4  *       Copyright(c) 2010-2014 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 #include <string.h>
  34 #include <stdio.h>
  35
  36 #include <rte_common.h>
  37 #include <rte_mbuf.h>
  38 #include <rte_memory.h>
  39 #include <rte_malloc.h>
  40 #include <rte_log.h>
  41
  42 #include "rte_table_hash.h"
  43 #include "rte_lru.h"
  44
  45 #define RTE_TABLE_HASH_KEY_SIZE                                         32
  46
  47 #define RTE_BUCKET_ENTRY_VALID                                          0x1LLU
  48
  49 #ifdef RTE_TABLE_STATS_COLLECT
  50
  51 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(table, val) \
  52         table->stats.n_pkts_in += val
  53 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(table, val) \
  54         table->stats.n_pkts_lookup_miss += val
  55
  56 #else
  57
  58 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(table, val)
  59 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(table, val)
  60
  61 #endif
  62
  63 struct rte_bucket_4_32 {
  64         /* Cache line 0 */
  65         uint64_t signature[4 + 1];
  66         uint64_t lru_list;
  67         struct rte_bucket_4_32 *next;
  68         uint64_t next_valid;
  69
  70         /* Cache lines 1 and 2 */
  71         uint64_t key[4][4];
  72
  73         /* Cache line 3 */
  74         uint8_t data[0];
  75 };
  76
  77 struct rte_table_hash {
  78         struct rte_table_stats stats;
  79
  80         /* Input parameters */
  81         uint32_t n_buckets;
  82         uint32_t n_entries_per_bucket;
  83         uint32_t key_size;
  84         uint32_t entry_size;
  85         uint32_t bucket_size;
  86         uint32_t signature_offset;
  87         uint32_t key_offset;
  88         rte_table_hash_op_hash f_hash;
  89         uint64_t seed;
  90
  91         /* Extendible buckets */
  92         uint32_t n_buckets_ext;
  93         uint32_t stack_pos;
  94         uint32_t *stack;
  95
  96         /* Lookup table */
  97         uint8_t memory[0] __rte_cache_aligned;
  98 };
  99
 100 static int
 101 check_params_create_lru(struct rte_table_hash_key32_lru_params *params) {
 102         /* n_entries */
 103         if (params->n_entries == 0) {
 104                 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
 105                 return -EINVAL;
 106         }
 107
 108         /* f_hash */
 109         if (params->f_hash == NULL) {
 110                 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
 111                         __func__);
 112                 return -EINVAL;
 113         }
 114
 115         return 0;
 116 }
 117
 118 static void *
 119 rte_table_hash_create_key32_lru(void *params,
 120                 int socket_id,
 121                 uint32_t entry_size)
 122 {
 123         struct rte_table_hash_key32_lru_params *p =
 124                 (struct rte_table_hash_key32_lru_params *) params;
 125         struct rte_table_hash *f;
 126         uint32_t n_buckets, n_entries_per_bucket, key_size, bucket_size_cl;
 127         uint32_t total_size, i;
 128
 129         /* Check input parameters */
 130         if ((check_params_create_lru(p) != 0) ||
 131                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
 132                 ((sizeof(struct rte_bucket_4_32) % RTE_CACHE_LINE_SIZE) != 0)) {
 133                 return NULL;
 134         }
 135         n_entries_per_bucket = 4;
 136         key_size = 32;
 137
 138         /* Memory allocation */
 139         n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
 140                 n_entries_per_bucket);
 141         bucket_size_cl = (sizeof(struct rte_bucket_4_32) + n_entries_per_bucket
 142                 * entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
 143         total_size = sizeof(struct rte_table_hash) + n_buckets *
 144                 bucket_size_cl * RTE_CACHE_LINE_SIZE;
 145
 146         f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
 147         if (f == NULL) {
 148                 RTE_LOG(ERR, TABLE,
 149                         "%s: Cannot allocate %u bytes for hash table\n",
 150                         __func__, total_size);
 151                 return NULL;
 152         }
 153         RTE_LOG(INFO, TABLE,
 154                 "%s: Hash table memory footprint is %u bytes\n", __func__,
 155                 total_size);
 156
 157         /* Memory initialization */
 158         f->n_buckets = n_buckets;
 159         f->n_entries_per_bucket = n_entries_per_bucket;
 160         f->key_size = key_size;
 161         f->entry_size = entry_size;
 162         f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
 163         f->signature_offset = p->signature_offset;
 164         f->key_offset = p->key_offset;
 165         f->f_hash = p->f_hash;
 166         f->seed = p->seed;
 167
 168         for (i = 0; i < n_buckets; i++) {
 169                 struct rte_bucket_4_32 *bucket;
 170
 171                 bucket = (struct rte_bucket_4_32 *) &f->memory[i *
 172                         f->bucket_size];
 173                 bucket->lru_list = 0x0000000100020003LLU;
 174         }
 175
 176         return f;
 177 }
 178
 179 static int
 180 rte_table_hash_free_key32_lru(void *table)
 181 {
 182         struct rte_table_hash *f = (struct rte_table_hash *) table;
 183
 184         /* Check input parameters */
 185         if (f == NULL) {
 186                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 187                 return -EINVAL;
 188         }
 189
 190         rte_free(f);
 191         return 0;
 192 }
 193
 194 static int
 195 rte_table_hash_entry_add_key32_lru(
 196         void *table,
 197         void *key,
 198         void *entry,
 199         int *key_found,
 200         void **entry_ptr)
 201 {
 202         struct rte_table_hash *f = (struct rte_table_hash *) table;
 203         struct rte_bucket_4_32 *bucket;
 204         uint64_t signature, pos;
 205         uint32_t bucket_index, i;
 206
 207         signature = f->f_hash(key, f->key_size, f->seed);
 208         bucket_index = signature & (f->n_buckets - 1);
 209         bucket = (struct rte_bucket_4_32 *)
 210                 &f->memory[bucket_index * f->bucket_size];
 211         signature |= RTE_BUCKET_ENTRY_VALID;
 212
 213         /* Key is present in the bucket */
 214         for (i = 0; i < 4; i++) {
 215                 uint64_t bucket_signature = bucket->signature[i];
 216                 uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 217
 218                 if ((bucket_signature == signature) &&
 219                         (memcmp(key, bucket_key, f->key_size) == 0)) {
 220                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 221
 222                         memcpy(bucket_data, entry, f->entry_size);
 223                         lru_update(bucket, i);
 224                         *key_found = 1;
 225                         *entry_ptr = (void *) bucket_data;
 226                         return 0;
 227                 }
 228         }
 229
 230         /* Key is not present in the bucket */
 231         for (i = 0; i < 4; i++) {
 232                 uint64_t bucket_signature = bucket->signature[i];
 233                 uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 234
 235                 if (bucket_signature == 0) {
 236                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 237
 238                         bucket->signature[i] = signature;
 239                         memcpy(bucket_key, key, f->key_size);
 240                         memcpy(bucket_data, entry, f->entry_size);
 241                         lru_update(bucket, i);
 242                         *key_found = 0;
 243                         *entry_ptr = (void *) bucket_data;
 244
 245                         return 0;
 246                 }
 247         }
 248
 249         /* Bucket full: replace LRU entry */
 250         pos = lru_pos(bucket);
 251         bucket->signature[pos] = signature;
 252         memcpy(bucket->key[pos], key, f->key_size);
 253         memcpy(&bucket->data[pos * f->entry_size], entry, f->entry_size);
 254         lru_update(bucket, pos);
 255         *key_found      = 0;
 256         *entry_ptr = (void *) &bucket->data[pos * f->entry_size];
 257
 258         return 0;
 259 }
 260
 261 static int
 262 rte_table_hash_entry_delete_key32_lru(
 263         void *table,
 264         void *key,
 265         int *key_found,
 266         void *entry)
 267 {
 268         struct rte_table_hash *f = (struct rte_table_hash *) table;
 269         struct rte_bucket_4_32 *bucket;
 270         uint64_t signature;
 271         uint32_t bucket_index, i;
 272
 273         signature = f->f_hash(key, f->key_size, f->seed);
 274         bucket_index = signature & (f->n_buckets - 1);
 275         bucket = (struct rte_bucket_4_32 *)
 276                 &f->memory[bucket_index * f->bucket_size];
 277         signature |= RTE_BUCKET_ENTRY_VALID;
 278
 279         /* Key is present in the bucket */
 280         for (i = 0; i < 4; i++) {
 281                 uint64_t bucket_signature = bucket->signature[i];
 282                 uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 283
 284                 if ((bucket_signature == signature) &&
 285                         (memcmp(key, bucket_key, f->key_size) == 0)) {
 286                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 287
 288                         bucket->signature[i] = 0;
 289                         *key_found = 1;
 290                         if (entry)
 291                                 memcpy(entry, bucket_data, f->entry_size);
 292
 293                         return 0;
 294                 }
 295         }
 296
 297         /* Key is not present in the bucket */
 298         *key_found = 0;
 299         return 0;
 300 }
 301
 302 static int
 303 check_params_create_ext(struct rte_table_hash_key32_ext_params *params) {
 304         /* n_entries */
 305         if (params->n_entries == 0) {
 306                 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
 307                 return -EINVAL;
 308         }
 309
 310         /* n_entries_ext */
 311         if (params->n_entries_ext == 0) {
 312                 RTE_LOG(ERR, TABLE, "%s: n_entries_ext is zero\n", __func__);
 313                 return -EINVAL;
 314         }
 315
 316         /* f_hash */
 317         if (params->f_hash == NULL) {
 318                 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
 319                         __func__);
 320                 return -EINVAL;
 321         }
 322
 323         return 0;
 324 }
 325
 326 static void *
 327 rte_table_hash_create_key32_ext(void *params,
 328         int socket_id,
 329         uint32_t entry_size)
 330 {
 331         struct rte_table_hash_key32_ext_params *p =
 332                         (struct rte_table_hash_key32_ext_params *) params;
 333         struct rte_table_hash *f;
 334         uint32_t n_buckets, n_buckets_ext, n_entries_per_bucket;
 335         uint32_t key_size, bucket_size_cl, stack_size_cl, total_size, i;
 336
 337         /* Check input parameters */
 338         if ((check_params_create_ext(p) != 0) ||
 339                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
 340                 ((sizeof(struct rte_bucket_4_32) % RTE_CACHE_LINE_SIZE) != 0))
 341                 return NULL;
 342
 343         n_entries_per_bucket = 4;
 344         key_size = 32;
 345
 346         /* Memory allocation */
 347         n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
 348                 n_entries_per_bucket);
 349         n_buckets_ext = (p->n_entries_ext + n_entries_per_bucket - 1) /
 350                 n_entries_per_bucket;
 351         bucket_size_cl = (sizeof(struct rte_bucket_4_32) + n_entries_per_bucket
 352                 * entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
 353         stack_size_cl = (n_buckets_ext * sizeof(uint32_t) + RTE_CACHE_LINE_SIZE - 1)
 354                 / RTE_CACHE_LINE_SIZE;
 355         total_size = sizeof(struct rte_table_hash) +
 356                 ((n_buckets + n_buckets_ext) * bucket_size_cl + stack_size_cl) *
 357                 RTE_CACHE_LINE_SIZE;
 358
 359         f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
 360         if (f == NULL) {
 361                 RTE_LOG(ERR, TABLE,
 362                         "%s: Cannot allocate %u bytes for hash table\n",
 363                         __func__, total_size);
 364                 return NULL;
 365         }
 366         RTE_LOG(INFO, TABLE,
 367                 "%s: Hash table memory footprint is %u bytes\n", __func__,
 368                 total_size);
 369
 370         /* Memory initialization */
 371         f->n_buckets = n_buckets;
 372         f->n_entries_per_bucket = n_entries_per_bucket;
 373         f->key_size = key_size;
 374         f->entry_size = entry_size;
 375         f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
 376         f->signature_offset = p->signature_offset;
 377         f->key_offset = p->key_offset;
 378         f->f_hash = p->f_hash;
 379         f->seed = p->seed;
 380
 381         f->n_buckets_ext = n_buckets_ext;
 382         f->stack_pos = n_buckets_ext;
 383         f->stack = (uint32_t *)
 384                 &f->memory[(n_buckets + n_buckets_ext) * f->bucket_size];
 385
 386         for (i = 0; i < n_buckets_ext; i++)
 387                 f->stack[i] = i;
 388
 389         return f;
 390 }
 391
 392 static int
 393 rte_table_hash_free_key32_ext(void *table)
 394 {
 395         struct rte_table_hash *f = (struct rte_table_hash *) table;
 396
 397         /* Check input parameters */
 398         if (f == NULL) {
 399                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 400                 return -EINVAL;
 401         }
 402
 403         rte_free(f);
 404         return 0;
 405 }
 406
 407 static int
 408 rte_table_hash_entry_add_key32_ext(
 409         void *table,
 410         void *key,
 411         void *entry,
 412         int *key_found,
 413         void **entry_ptr)
 414 {
 415         struct rte_table_hash *f = (struct rte_table_hash *) table;
 416         struct rte_bucket_4_32 *bucket0, *bucket, *bucket_prev;
 417         uint64_t signature;
 418         uint32_t bucket_index, i;
 419
 420         signature = f->f_hash(key, f->key_size, f->seed);
 421         bucket_index = signature & (f->n_buckets - 1);
 422         bucket0 = (struct rte_bucket_4_32 *)
 423                         &f->memory[bucket_index * f->bucket_size];
 424         signature |= RTE_BUCKET_ENTRY_VALID;
 425
 426         /* Key is present in the bucket */
 427         for (bucket = bucket0; bucket != NULL; bucket = bucket->next) {
 428                 for (i = 0; i < 4; i++) {
 429                         uint64_t bucket_signature = bucket->signature[i];
 430                         uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 431
 432                         if ((bucket_signature == signature) &&
 433                                 (memcmp(key, bucket_key, f->key_size) == 0)) {
 434                                 uint8_t *bucket_data = &bucket->data[i *
 435                                         f->entry_size];
 436
 437                                 memcpy(bucket_data, entry, f->entry_size);
 438                                 *key_found = 1;
 439                                 *entry_ptr = (void *) bucket_data;
 440
 441                                 return 0;
 442                         }
 443                 }
 444         }
 445
 446         /* Key is not present in the bucket */
 447         for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
 448                 bucket_prev = bucket, bucket = bucket->next)
 449                 for (i = 0; i < 4; i++) {
 450                         uint64_t bucket_signature = bucket->signature[i];
 451                         uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 452
 453                         if (bucket_signature == 0) {
 454                                 uint8_t *bucket_data = &bucket->data[i *
 455                                         f->entry_size];
 456
 457                                 bucket->signature[i] = signature;
 458                                 memcpy(bucket_key, key, f->key_size);
 459                                 memcpy(bucket_data, entry, f->entry_size);
 460                                 *key_found = 0;
 461                                 *entry_ptr = (void *) bucket_data;
 462
 463                                 return 0;
 464                         }
 465                 }
 466
 467         /* Bucket full: extend bucket */
 468         if (f->stack_pos > 0) {
 469                 bucket_index = f->stack[--f->stack_pos];
 470
 471                 bucket = (struct rte_bucket_4_32 *)
 472                         &f->memory[(f->n_buckets + bucket_index) *
 473                         f->bucket_size];
 474                 bucket_prev->next = bucket;
 475                 bucket_prev->next_valid = 1;
 476
 477                 bucket->signature[0] = signature;
 478                 memcpy(bucket->key[0], key, f->key_size);
 479                 memcpy(&bucket->data[0], entry, f->entry_size);
 480                 *key_found = 0;
 481                 *entry_ptr = (void *) &bucket->data[0];
 482                 return 0;
 483         }
 484
 485         return -ENOSPC;
 486 }
 487
 488 static int
 489 rte_table_hash_entry_delete_key32_ext(
 490         void *table,
 491         void *key,
 492         int *key_found,
 493         void *entry)
 494 {
 495         struct rte_table_hash *f = (struct rte_table_hash *) table;
 496         struct rte_bucket_4_32 *bucket0, *bucket, *bucket_prev;
 497         uint64_t signature;
 498         uint32_t bucket_index, i;
 499
 500         signature = f->f_hash(key, f->key_size, f->seed);
 501         bucket_index = signature & (f->n_buckets - 1);
 502         bucket0 = (struct rte_bucket_4_32 *)
 503                 &f->memory[bucket_index * f->bucket_size];
 504         signature |= RTE_BUCKET_ENTRY_VALID;
 505
 506         /* Key is present in the bucket */
 507         for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
 508                 bucket_prev = bucket, bucket = bucket->next)
 509                 for (i = 0; i < 4; i++) {
 510                         uint64_t bucket_signature = bucket->signature[i];
 511                         uint8_t *bucket_key = (uint8_t *) bucket->key[i];
 512
 513                         if ((bucket_signature == signature) &&
 514                                 (memcmp(key, bucket_key, f->key_size) == 0)) {
 515                                 uint8_t *bucket_data = &bucket->data[i *
 516                                         f->entry_size];
 517
 518                                 bucket->signature[i] = 0;
 519                                 *key_found = 1;
 520                                 if (entry)
 521                                         memcpy(entry, bucket_data,
 522                                                 f->entry_size);
 523
 524                                 if ((bucket->signature[0] == 0) &&
 525                                                 (bucket->signature[1] == 0) &&
 526                                                 (bucket->signature[2] == 0) &&
 527                                                 (bucket->signature[3] == 0) &&
 528                                                 (bucket_prev != NULL)) {
 529                                         bucket_prev->next = bucket->next;
 530                                         bucket_prev->next_valid =
 531                                                 bucket->next_valid;
 532
 533                                         memset(bucket, 0,
 534                                                 sizeof(struct rte_bucket_4_32));
 535                                         bucket_index = (((uint8_t *)bucket -
 536                                                 (uint8_t *)f->memory)/f->bucket_size) - f->n_buckets;
 537                                         f->stack[f->stack_pos++] = bucket_index;
 538                                 }
 539
 540                                 return 0;
 541                         }
 542                 }
 543
 544         /* Key is not present in the bucket */
 545         *key_found = 0;
 546         return 0;
 547 }
 548
 549 #define lookup_key32_cmp(key_in, bucket, pos)                   \
 550 {                                                               \
 551         uint64_t xor[4][4], or[4], signature[4];                \
 552                                                                 \
 553         signature[0] = ((~bucket->signature[0]) & 1);           \
 554         signature[1] = ((~bucket->signature[1]) & 1);           \
 555         signature[2] = ((~bucket->signature[2]) & 1);           \
 556         signature[3] = ((~bucket->signature[3]) & 1);           \
 557                                                                 \
 558         xor[0][0] = key_in[0] ^  bucket->key[0][0];             \
 559         xor[0][1] = key_in[1] ^  bucket->key[0][1];             \
 560         xor[0][2] = key_in[2] ^  bucket->key[0][2];             \
 561         xor[0][3] = key_in[3] ^  bucket->key[0][3];             \
 562                                                                 \
 563         xor[1][0] = key_in[0] ^  bucket->key[1][0];             \
 564         xor[1][1] = key_in[1] ^  bucket->key[1][1];             \
 565         xor[1][2] = key_in[2] ^  bucket->key[1][2];             \
 566         xor[1][3] = key_in[3] ^  bucket->key[1][3];             \
 567                                                                 \
 568         xor[2][0] = key_in[0] ^  bucket->key[2][0];             \
 569         xor[2][1] = key_in[1] ^  bucket->key[2][1];             \
 570         xor[2][2] = key_in[2] ^  bucket->key[2][2];             \
 571         xor[2][3] = key_in[3] ^  bucket->key[2][3];             \
 572                                                                 \
 573         xor[3][0] = key_in[0] ^  bucket->key[3][0];             \
 574         xor[3][1] = key_in[1] ^  bucket->key[3][1];             \
 575         xor[3][2] = key_in[2] ^  bucket->key[3][2];             \
 576         xor[3][3] = key_in[3] ^  bucket->key[3][3];             \
 577                                                                 \
 578         or[0] = xor[0][0] | xor[0][1] | xor[0][2] | xor[0][3] | signature[0];\
 579         or[1] = xor[1][0] | xor[1][1] | xor[1][2] | xor[1][3] | signature[1];\
 580         or[2] = xor[2][0] | xor[2][1] | xor[2][2] | xor[2][3] | signature[2];\
 581         or[3] = xor[3][0] | xor[3][1] | xor[3][2] | xor[3][3] | signature[3];\
 582                                                                 \
 583         pos = 4;                                                \
 584         if (or[0] == 0)                                         \
 585                 pos = 0;                                        \
 586         if (or[1] == 0)                                         \
 587                 pos = 1;                                        \
 588         if (or[2] == 0)                                         \
 589                 pos = 2;                                        \
 590         if (or[3] == 0)                                         \
 591                 pos = 3;                                        \
 592 }
 593
 594 #define lookup1_stage0(pkt0_index, mbuf0, pkts, pkts_mask, f)   \
 595 {                                                               \
 596         uint64_t pkt_mask;                                      \
 597         uint32_t key_offset = f->key_offset;    \
 598                                                                 \
 599         pkt0_index = __builtin_ctzll(pkts_mask);                \
 600         pkt_mask = 1LLU << pkt0_index;                          \
 601         pkts_mask &= ~pkt_mask;                                 \
 602                                                                 \
 603         mbuf0 = pkts[pkt0_index];                               \
 604         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf0, key_offset));\
 605 }
 606
 607 #define lookup1_stage1(mbuf1, bucket1, f)                       \
 608 {                                                               \
 609         uint64_t signature;                                     \
 610         uint32_t bucket_index;                                  \
 611                                                                 \
 612         signature = RTE_MBUF_METADATA_UINT32(mbuf1, f->signature_offset);\
 613         bucket_index = signature & (f->n_buckets - 1);          \
 614         bucket1 = (struct rte_bucket_4_32 *)                    \
 615                 &f->memory[bucket_index * f->bucket_size];      \
 616         rte_prefetch0(bucket1);                                 \
 617         rte_prefetch0((void *)(((uintptr_t) bucket1) + RTE_CACHE_LINE_SIZE));\
 618         rte_prefetch0((void *)(((uintptr_t) bucket1) + 2 * RTE_CACHE_LINE_SIZE));\
 619 }
 620
 621 #define lookup1_stage2_lru(pkt2_index, mbuf2, bucket2,          \
 622         pkts_mask_out, entries, f)                              \
 623 {                                                               \
 624         void *a;                                                \
 625         uint64_t pkt_mask;                                      \
 626         uint64_t *key;                                          \
 627         uint32_t pos;                                           \
 628                                                                 \
 629         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 630                                                                 \
 631         lookup_key32_cmp(key, bucket2, pos);                    \
 632                                                                 \
 633         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
 634         pkts_mask_out |= pkt_mask;                              \
 635                                                                 \
 636         a = (void *) &bucket2->data[pos * f->entry_size];       \
 637         rte_prefetch0(a);                                       \
 638         entries[pkt2_index] = a;                                \
 639         lru_update(bucket2, pos);                               \
 640 }
 641
 642 #define lookup1_stage2_ext(pkt2_index, mbuf2, bucket2, pkts_mask_out,\
 643         entries, buckets_mask, buckets, keys, f)                \
 644 {                                                               \
 645         struct rte_bucket_4_32 *bucket_next;                    \
 646         void *a;                                                \
 647         uint64_t pkt_mask, bucket_mask;                         \
 648         uint64_t *key;                                          \
 649         uint32_t pos;                                           \
 650                                                                 \
 651         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 652                                                                 \
 653         lookup_key32_cmp(key, bucket2, pos);                    \
 654                                                                 \
 655         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
 656         pkts_mask_out |= pkt_mask;                              \
 657                                                                 \
 658         a = (void *) &bucket2->data[pos * f->entry_size];       \
 659         rte_prefetch0(a);                                       \
 660         entries[pkt2_index] = a;                                \
 661                                                                 \
 662         bucket_mask = (~pkt_mask) & (bucket2->next_valid << pkt2_index);\
 663         buckets_mask |= bucket_mask;                            \
 664         bucket_next = bucket2->next;                            \
 665         buckets[pkt2_index] = bucket_next;                      \
 666         keys[pkt2_index] = key;                                 \
 667 }
 668
 669 #define lookup_grinder(pkt_index, buckets, keys, pkts_mask_out, \
 670         entries, buckets_mask, f)                               \
 671 {                                                               \
 672         struct rte_bucket_4_32 *bucket, *bucket_next;           \
 673         void *a;                                                \
 674         uint64_t pkt_mask, bucket_mask;                         \
 675         uint64_t *key;                                          \
 676         uint32_t pos;                                           \
 677                                                                 \
 678         bucket = buckets[pkt_index];                            \
 679         key = keys[pkt_index];                                  \
 680                                                                 \
 681         lookup_key32_cmp(key, bucket, pos);                     \
 682                                                                 \
 683         pkt_mask = (bucket->signature[pos] & 1LLU) << pkt_index;\
 684         pkts_mask_out |= pkt_mask;                              \
 685                                                                 \
 686         a = (void *) &bucket->data[pos * f->entry_size];        \
 687         rte_prefetch0(a);                                       \
 688         entries[pkt_index] = a;                                 \
 689                                                                 \
 690         bucket_mask = (~pkt_mask) & (bucket->next_valid << pkt_index);\
 691         buckets_mask |= bucket_mask;                            \
 692         bucket_next = bucket->next;                             \
 693         rte_prefetch0(bucket_next);                             \
 694         rte_prefetch0((void *)(((uintptr_t) bucket_next) + RTE_CACHE_LINE_SIZE));\
 695         rte_prefetch0((void *)(((uintptr_t) bucket_next) +      \
 696                 2 * RTE_CACHE_LINE_SIZE));                              \
 697         buckets[pkt_index] = bucket_next;                       \
 698         keys[pkt_index] = key;                                  \
 699 }
 700
 701 #define lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01,\
 702         pkts, pkts_mask, f)                                     \
 703 {                                                               \
 704         uint64_t pkt00_mask, pkt01_mask;                        \
 705         uint32_t key_offset = f->key_offset;            \
 706                                                                 \
 707         pkt00_index = __builtin_ctzll(pkts_mask);               \
 708         pkt00_mask = 1LLU << pkt00_index;                       \
 709         pkts_mask &= ~pkt00_mask;                               \
 710                                                                 \
 711         mbuf00 = pkts[pkt00_index];                             \
 712         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
 713                                                                 \
 714         pkt01_index = __builtin_ctzll(pkts_mask);               \
 715         pkt01_mask = 1LLU << pkt01_index;                       \
 716         pkts_mask &= ~pkt01_mask;                               \
 717                                                                 \
 718         mbuf01 = pkts[pkt01_index];                             \
 719         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
 720 }
 721
 722 #define lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,\
 723         mbuf00, mbuf01, pkts, pkts_mask, f)                     \
 724 {                                                               \
 725         uint64_t pkt00_mask, pkt01_mask;                        \
 726         uint32_t key_offset = f->key_offset;            \
 727                                                                 \
 728         pkt00_index = __builtin_ctzll(pkts_mask);               \
 729         pkt00_mask = 1LLU << pkt00_index;                       \
 730         pkts_mask &= ~pkt00_mask;                               \
 731                                                                 \
 732         mbuf00 = pkts[pkt00_index];                             \
 733         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset)); \
 734                                                                 \
 735         pkt01_index = __builtin_ctzll(pkts_mask);               \
 736         if (pkts_mask == 0)                                     \
 737                 pkt01_index = pkt00_index;                      \
 738                                                                 \
 739         pkt01_mask = 1LLU << pkt01_index;                       \
 740         pkts_mask &= ~pkt01_mask;                               \
 741                                                                 \
 742         mbuf01 = pkts[pkt01_index];                             \
 743         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset)); \
 744 }
 745
 746 #define lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f)   \
 747 {                                                               \
 748         uint64_t signature10, signature11;                      \
 749         uint32_t bucket10_index, bucket11_index;                \
 750                                                                 \
 751         signature10 = RTE_MBUF_METADATA_UINT32(mbuf10, f->signature_offset);\
 752         bucket10_index = signature10 & (f->n_buckets - 1);      \
 753         bucket10 = (struct rte_bucket_4_32 *)                   \
 754                 &f->memory[bucket10_index * f->bucket_size];    \
 755         rte_prefetch0(bucket10);                                \
 756         rte_prefetch0((void *)(((uintptr_t) bucket10) + RTE_CACHE_LINE_SIZE));\
 757         rte_prefetch0((void *)(((uintptr_t) bucket10) + 2 * RTE_CACHE_LINE_SIZE));\
 758                                                                 \
 759         signature11 = RTE_MBUF_METADATA_UINT32(mbuf11, f->signature_offset);\
 760         bucket11_index = signature11 & (f->n_buckets - 1);      \
 761         bucket11 = (struct rte_bucket_4_32 *)                   \
 762                 &f->memory[bucket11_index * f->bucket_size];    \
 763         rte_prefetch0(bucket11);                                \
 764         rte_prefetch0((void *)(((uintptr_t) bucket11) + RTE_CACHE_LINE_SIZE));\
 765         rte_prefetch0((void *)(((uintptr_t) bucket11) + 2 * RTE_CACHE_LINE_SIZE));\
 766 }
 767
 768 #define lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,\
 769         bucket20, bucket21, pkts_mask_out, entries, f)          \
 770 {                                                               \
 771         void *a20, *a21;                                        \
 772         uint64_t pkt20_mask, pkt21_mask;                        \
 773         uint64_t *key20, *key21;                                \
 774         uint32_t pos20, pos21;                                  \
 775                                                                 \
 776         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 777         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 778                                                                 \
 779         lookup_key32_cmp(key20, bucket20, pos20);               \
 780         lookup_key32_cmp(key21, bucket21, pos21);               \
 781                                                                 \
 782         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
 783         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
 784         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 785                                                                 \
 786         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 787         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 788         rte_prefetch0(a20);                                     \
 789         rte_prefetch0(a21);                                     \
 790         entries[pkt20_index] = a20;                             \
 791         entries[pkt21_index] = a21;                             \
 792         lru_update(bucket20, pos20);                            \
 793         lru_update(bucket21, pos21);                            \
 794 }
 795
 796 #define lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21, bucket20, \
 797         bucket21, pkts_mask_out, entries, buckets_mask, buckets, keys, f)\
 798 {                                                               \
 799         struct rte_bucket_4_32 *bucket20_next, *bucket21_next;  \
 800         void *a20, *a21;                                        \
 801         uint64_t pkt20_mask, pkt21_mask, bucket20_mask, bucket21_mask;\
 802         uint64_t *key20, *key21;                                \
 803         uint32_t pos20, pos21;                                  \
 804                                                                 \
 805         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 806         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 807                                                                 \
 808         lookup_key32_cmp(key20, bucket20, pos20);               \
 809         lookup_key32_cmp(key21, bucket21, pos21);               \
 810                                                                 \
 811         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
 812         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
 813         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 814                                                                 \
 815         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 816         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 817         rte_prefetch0(a20);                                     \
 818         rte_prefetch0(a21);                                     \
 819         entries[pkt20_index] = a20;                             \
 820         entries[pkt21_index] = a21;                             \
 821                                                                 \
 822         bucket20_mask = (~pkt20_mask) & (bucket20->next_valid << pkt20_index);\
 823         bucket21_mask = (~pkt21_mask) & (bucket21->next_valid << pkt21_index);\
 824         buckets_mask |= bucket20_mask | bucket21_mask;          \
 825         bucket20_next = bucket20->next;                         \
 826         bucket21_next = bucket21->next;                         \
 827         buckets[pkt20_index] = bucket20_next;                   \
 828         buckets[pkt21_index] = bucket21_next;                   \
 829         keys[pkt20_index] = key20;                              \
 830         keys[pkt21_index] = key21;                              \
 831 }
 832
 833 static int
 834 rte_table_hash_lookup_key32_lru(
 835         void *table,
 836         struct rte_mbuf **pkts,
 837         uint64_t pkts_mask,
 838         uint64_t *lookup_hit_mask,
 839         void **entries)
 840 {
 841         struct rte_table_hash *f = (struct rte_table_hash *) table;
 842         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
 843         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 844         uint32_t pkt00_index, pkt01_index, pkt10_index;
 845         uint32_t pkt11_index, pkt20_index, pkt21_index;
 846         uint64_t pkts_mask_out = 0;
 847
 848         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 849         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
 850
 851         /* Cannot run the pipeline with less than 5 packets */
 852         if (__builtin_popcountll(pkts_mask) < 5) {
 853                 for ( ; pkts_mask; ) {
 854                         struct rte_bucket_4_32 *bucket;
 855                         struct rte_mbuf *mbuf;
 856                         uint32_t pkt_index;
 857
 858                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask, f);
 859                         lookup1_stage1(mbuf, bucket, f);
 860                         lookup1_stage2_lru(pkt_index, mbuf, bucket,
 861                                         pkts_mask_out, entries, f);
 862                 }
 863
 864                 *lookup_hit_mask = pkts_mask_out;
 865                 RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 866                 return 0;
 867         }
 868
 869         /*
 870          * Pipeline fill
 871          *
 872          */
 873         /* Pipeline stage 0 */
 874         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 875                 pkts_mask, f);
 876
 877         /* Pipeline feed */
 878         mbuf10 = mbuf00;
 879         mbuf11 = mbuf01;
 880         pkt10_index = pkt00_index;
 881         pkt11_index = pkt01_index;
 882
 883         /* Pipeline stage 0 */
 884         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 885                 pkts_mask, f);
 886
 887         /* Pipeline stage 1 */
 888         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 889
 890         /*
 891          * Pipeline run
 892          *
 893          */
 894         for ( ; pkts_mask; ) {
 895                 /* Pipeline feed */
 896                 bucket20 = bucket10;
 897                 bucket21 = bucket11;
 898                 mbuf20 = mbuf10;
 899                 mbuf21 = mbuf11;
 900                 mbuf10 = mbuf00;
 901                 mbuf11 = mbuf01;
 902                 pkt20_index = pkt10_index;
 903                 pkt21_index = pkt11_index;
 904                 pkt10_index = pkt00_index;
 905                 pkt11_index = pkt01_index;
 906
 907                 /* Pipeline stage 0 */
 908                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
 909                         mbuf00, mbuf01, pkts, pkts_mask, f);
 910
 911                 /* Pipeline stage 1 */
 912                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 913
 914                 /* Pipeline stage 2 */
 915                 lookup2_stage2_lru(pkt20_index, pkt21_index,
 916                         mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out,
 917                         entries, f);
 918         }
 919
 920         /*
 921          * Pipeline flush
 922          *
 923          */
 924         /* Pipeline feed */
 925         bucket20 = bucket10;
 926         bucket21 = bucket11;
 927         mbuf20 = mbuf10;
 928         mbuf21 = mbuf11;
 929         mbuf10 = mbuf00;
 930         mbuf11 = mbuf01;
 931         pkt20_index = pkt10_index;
 932         pkt21_index = pkt11_index;
 933         pkt10_index = pkt00_index;
 934         pkt11_index = pkt01_index;
 935
 936         /* Pipeline stage 1 */
 937         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 938
 939         /* Pipeline stage 2 */
 940         lookup2_stage2_lru(pkt20_index, pkt21_index,
 941                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
 942
 943         /* Pipeline feed */
 944         bucket20 = bucket10;
 945         bucket21 = bucket11;
 946         mbuf20 = mbuf10;
 947         mbuf21 = mbuf11;
 948         pkt20_index = pkt10_index;
 949         pkt21_index = pkt11_index;
 950
 951         /* Pipeline stage 2 */
 952         lookup2_stage2_lru(pkt20_index, pkt21_index,
 953                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
 954
 955         *lookup_hit_mask = pkts_mask_out;
 956         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 957         return 0;
 958 } /* rte_table_hash_lookup_key32_lru() */
 959
 960 static int
 961 rte_table_hash_lookup_key32_ext(
 962         void *table,
 963         struct rte_mbuf **pkts,
 964         uint64_t pkts_mask,
 965         uint64_t *lookup_hit_mask,
 966         void **entries)
 967 {
 968         struct rte_table_hash *f = (struct rte_table_hash *) table;
 969         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
 970         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 971         uint32_t pkt00_index, pkt01_index, pkt10_index;
 972         uint32_t pkt11_index, pkt20_index, pkt21_index;
 973         uint64_t pkts_mask_out = 0, buckets_mask = 0;
 974         struct rte_bucket_4_32 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
 975         uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
 976
 977         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 978         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
 979
 980         /* Cannot run the pipeline with less than 5 packets */
 981         if (__builtin_popcountll(pkts_mask) < 5) {
 982                 for ( ; pkts_mask; ) {
 983                         struct rte_bucket_4_32 *bucket;
 984                         struct rte_mbuf *mbuf;
 985                         uint32_t pkt_index;
 986
 987                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask, f);
 988                         lookup1_stage1(mbuf, bucket, f);
 989                         lookup1_stage2_ext(pkt_index, mbuf, bucket,
 990                                 pkts_mask_out, entries, buckets_mask, buckets,
 991                                 keys, f);
 992                 }
 993
 994                 goto grind_next_buckets;
 995         }
 996
 997         /*
 998          * Pipeline fill
 999          *
1000          */
1001         /* Pipeline stage 0 */
1002         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1003                 pkts_mask, f);
1004
1005         /* Pipeline feed */
1006         mbuf10 = mbuf00;
1007         mbuf11 = mbuf01;
1008         pkt10_index = pkt00_index;
1009         pkt11_index = pkt01_index;
1010
1011         /* Pipeline stage 0 */
1012         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1013                 pkts_mask, f);
1014
1015         /* Pipeline stage 1 */
1016         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1017
1018         /*
1019          * Pipeline run
1020          *
1021          */
1022         for ( ; pkts_mask; ) {
1023                 /* Pipeline feed */
1024                 bucket20 = bucket10;
1025                 bucket21 = bucket11;
1026                 mbuf20 = mbuf10;
1027                 mbuf21 = mbuf11;
1028                 mbuf10 = mbuf00;
1029                 mbuf11 = mbuf01;
1030                 pkt20_index = pkt10_index;
1031                 pkt21_index = pkt11_index;
1032                 pkt10_index = pkt00_index;
1033                 pkt11_index = pkt01_index;
1034
1035                 /* Pipeline stage 0 */
1036                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1037                         mbuf00, mbuf01, pkts, pkts_mask, f);
1038
1039                 /* Pipeline stage 1 */
1040                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1041
1042                 /* Pipeline stage 2 */
1043                 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1044                         bucket20, bucket21, pkts_mask_out, entries,
1045                         buckets_mask, buckets, keys, f);
1046         }
1047
1048         /*
1049          * Pipeline flush
1050          *
1051          */
1052         /* Pipeline feed */
1053         bucket20 = bucket10;
1054         bucket21 = bucket11;
1055         mbuf20 = mbuf10;
1056         mbuf21 = mbuf11;
1057         mbuf10 = mbuf00;
1058         mbuf11 = mbuf01;
1059         pkt20_index = pkt10_index;
1060         pkt21_index = pkt11_index;
1061         pkt10_index = pkt00_index;
1062         pkt11_index = pkt01_index;
1063
1064         /* Pipeline stage 1 */
1065         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1066
1067         /* Pipeline stage 2 */
1068         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1069                 bucket20, bucket21, pkts_mask_out, entries,
1070                 buckets_mask, buckets, keys, f);
1071
1072         /* Pipeline feed */
1073         bucket20 = bucket10;
1074         bucket21 = bucket11;
1075         mbuf20 = mbuf10;
1076         mbuf21 = mbuf11;
1077         pkt20_index = pkt10_index;
1078         pkt21_index = pkt11_index;
1079
1080         /* Pipeline stage 2 */
1081         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1082                 bucket20, bucket21, pkts_mask_out, entries,
1083                 buckets_mask, buckets, keys, f);
1084
1085 grind_next_buckets:
1086         /* Grind next buckets */
1087         for ( ; buckets_mask; ) {
1088                 uint64_t buckets_mask_next = 0;
1089
1090                 for ( ; buckets_mask; ) {
1091                         uint64_t pkt_mask;
1092                         uint32_t pkt_index;
1093
1094                         pkt_index = __builtin_ctzll(buckets_mask);
1095                         pkt_mask = 1LLU << pkt_index;
1096                         buckets_mask &= ~pkt_mask;
1097
1098                         lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1099                                 entries, buckets_mask_next, f);
1100                 }
1101
1102                 buckets_mask = buckets_mask_next;
1103         }
1104
1105         *lookup_hit_mask = pkts_mask_out;
1106         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1107         return 0;
1108 } /* rte_table_hash_lookup_key32_ext() */
1109
1110 static int
1111 rte_table_hash_key32_stats_read(void *table, struct rte_table_stats *stats, int clear)
1112 {
1113         struct rte_table_hash *t = (struct rte_table_hash *) table;
1114
1115         if (stats != NULL)
1116                 memcpy(stats, &t->stats, sizeof(t->stats));
1117
1118         if (clear)
1119                 memset(&t->stats, 0, sizeof(t->stats));
1120
1121         return 0;
1122 }
1123
1124 struct rte_table_ops rte_table_hash_key32_lru_ops = {
1125         .f_create = rte_table_hash_create_key32_lru,
1126         .f_free = rte_table_hash_free_key32_lru,
1127         .f_add = rte_table_hash_entry_add_key32_lru,
1128         .f_delete = rte_table_hash_entry_delete_key32_lru,
1129         .f_add_bulk = NULL,
1130         .f_delete_bulk = NULL,
1131         .f_lookup = rte_table_hash_lookup_key32_lru,
1132         .f_stats = rte_table_hash_key32_stats_read,
1133 };
1134
1135 struct rte_table_ops rte_table_hash_key32_ext_ops = {
1136         .f_create = rte_table_hash_create_key32_ext,
1137         .f_free = rte_table_hash_free_key32_ext,
1138         .f_add = rte_table_hash_entry_add_key32_ext,
1139         .f_delete = rte_table_hash_entry_delete_key32_ext,
1140         .f_add_bulk = NULL,
1141         .f_delete_bulk = NULL,
1142         .f_lookup = rte_table_hash_lookup_key32_ext,
1143         .f_stats = rte_table_hash_key32_stats_read,
1144 };