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)      \
 595 {                                                               \
 596         uint64_t pkt_mask;                                      \
 597                                                                 \
 598         pkt0_index = __builtin_ctzll(pkts_mask);                \
 599         pkt_mask = 1LLU << pkt0_index;                          \
 600         pkts_mask &= ~pkt_mask;                                 \
 601                                                                 \
 602         mbuf0 = pkts[pkt0_index];                               \
 603         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf0, 0));   \
 604 }
 605
 606 #define lookup1_stage1(mbuf1, bucket1, f)                       \
 607 {                                                               \
 608         uint64_t signature;                                     \
 609         uint32_t bucket_index;                                  \
 610                                                                 \
 611         signature = RTE_MBUF_METADATA_UINT32(mbuf1, f->signature_offset);\
 612         bucket_index = signature & (f->n_buckets - 1);          \
 613         bucket1 = (struct rte_bucket_4_32 *)                    \
 614                 &f->memory[bucket_index * f->bucket_size];      \
 615         rte_prefetch0(bucket1);                                 \
 616         rte_prefetch0((void *)(((uintptr_t) bucket1) + RTE_CACHE_LINE_SIZE));\
 617         rte_prefetch0((void *)(((uintptr_t) bucket1) + 2 * RTE_CACHE_LINE_SIZE));\
 618 }
 619
 620 #define lookup1_stage2_lru(pkt2_index, mbuf2, bucket2,          \
 621         pkts_mask_out, entries, f)                              \
 622 {                                                               \
 623         void *a;                                                \
 624         uint64_t pkt_mask;                                      \
 625         uint64_t *key;                                          \
 626         uint32_t pos;                                           \
 627                                                                 \
 628         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 629                                                                 \
 630         lookup_key32_cmp(key, bucket2, pos);                    \
 631                                                                 \
 632         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
 633         pkts_mask_out |= pkt_mask;                              \
 634                                                                 \
 635         a = (void *) &bucket2->data[pos * f->entry_size];       \
 636         rte_prefetch0(a);                                       \
 637         entries[pkt2_index] = a;                                \
 638         lru_update(bucket2, pos);                               \
 639 }
 640
 641 #define lookup1_stage2_ext(pkt2_index, mbuf2, bucket2, pkts_mask_out,\
 642         entries, buckets_mask, buckets, keys, f)                \
 643 {                                                               \
 644         struct rte_bucket_4_32 *bucket_next;                    \
 645         void *a;                                                \
 646         uint64_t pkt_mask, bucket_mask;                         \
 647         uint64_t *key;                                          \
 648         uint32_t pos;                                           \
 649                                                                 \
 650         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 651                                                                 \
 652         lookup_key32_cmp(key, bucket2, pos);                    \
 653                                                                 \
 654         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
 655         pkts_mask_out |= pkt_mask;                              \
 656                                                                 \
 657         a = (void *) &bucket2->data[pos * f->entry_size];       \
 658         rte_prefetch0(a);                                       \
 659         entries[pkt2_index] = a;                                \
 660                                                                 \
 661         bucket_mask = (~pkt_mask) & (bucket2->next_valid << pkt2_index);\
 662         buckets_mask |= bucket_mask;                            \
 663         bucket_next = bucket2->next;                            \
 664         buckets[pkt2_index] = bucket_next;                      \
 665         keys[pkt2_index] = key;                                 \
 666 }
 667
 668 #define lookup_grinder(pkt_index, buckets, keys, pkts_mask_out, \
 669         entries, buckets_mask, f)                               \
 670 {                                                               \
 671         struct rte_bucket_4_32 *bucket, *bucket_next;           \
 672         void *a;                                                \
 673         uint64_t pkt_mask, bucket_mask;                         \
 674         uint64_t *key;                                          \
 675         uint32_t pos;                                           \
 676                                                                 \
 677         bucket = buckets[pkt_index];                            \
 678         key = keys[pkt_index];                                  \
 679                                                                 \
 680         lookup_key32_cmp(key, bucket, pos);                     \
 681                                                                 \
 682         pkt_mask = (bucket->signature[pos] & 1LLU) << pkt_index;\
 683         pkts_mask_out |= pkt_mask;                              \
 684                                                                 \
 685         a = (void *) &bucket->data[pos * f->entry_size];        \
 686         rte_prefetch0(a);                                       \
 687         entries[pkt_index] = a;                                 \
 688                                                                 \
 689         bucket_mask = (~pkt_mask) & (bucket->next_valid << pkt_index);\
 690         buckets_mask |= bucket_mask;                            \
 691         bucket_next = bucket->next;                             \
 692         rte_prefetch0(bucket_next);                             \
 693         rte_prefetch0((void *)(((uintptr_t) bucket_next) + RTE_CACHE_LINE_SIZE));\
 694         rte_prefetch0((void *)(((uintptr_t) bucket_next) +      \
 695                 2 * RTE_CACHE_LINE_SIZE));                              \
 696         buckets[pkt_index] = bucket_next;                       \
 697         keys[pkt_index] = key;                                  \
 698 }
 699
 700 #define lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01,\
 701         pkts, pkts_mask)                                        \
 702 {                                                               \
 703         uint64_t pkt00_mask, pkt01_mask;                        \
 704                                                                 \
 705         pkt00_index = __builtin_ctzll(pkts_mask);               \
 706         pkt00_mask = 1LLU << pkt00_index;                       \
 707         pkts_mask &= ~pkt00_mask;                               \
 708                                                                 \
 709         mbuf00 = pkts[pkt00_index];                             \
 710         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0));  \
 711                                                                 \
 712         pkt01_index = __builtin_ctzll(pkts_mask);               \
 713         pkt01_mask = 1LLU << pkt01_index;                       \
 714         pkts_mask &= ~pkt01_mask;                               \
 715                                                                 \
 716         mbuf01 = pkts[pkt01_index];                             \
 717         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0));  \
 718 }
 719
 720 #define lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,\
 721         mbuf00, mbuf01, pkts, pkts_mask)                        \
 722 {                                                               \
 723         uint64_t pkt00_mask, pkt01_mask;                        \
 724                                                                 \
 725         pkt00_index = __builtin_ctzll(pkts_mask);               \
 726         pkt00_mask = 1LLU << pkt00_index;                       \
 727         pkts_mask &= ~pkt00_mask;                               \
 728                                                                 \
 729         mbuf00 = pkts[pkt00_index];                             \
 730         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0));  \
 731                                                                 \
 732         pkt01_index = __builtin_ctzll(pkts_mask);               \
 733         if (pkts_mask == 0)                                     \
 734                 pkt01_index = pkt00_index;                      \
 735                                                                 \
 736         pkt01_mask = 1LLU << pkt01_index;                       \
 737         pkts_mask &= ~pkt01_mask;                               \
 738                                                                 \
 739         mbuf01 = pkts[pkt01_index];                             \
 740         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0));  \
 741 }
 742
 743 #define lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f)   \
 744 {                                                               \
 745         uint64_t signature10, signature11;                      \
 746         uint32_t bucket10_index, bucket11_index;                \
 747                                                                 \
 748         signature10 = RTE_MBUF_METADATA_UINT32(mbuf10, f->signature_offset);\
 749         bucket10_index = signature10 & (f->n_buckets - 1);      \
 750         bucket10 = (struct rte_bucket_4_32 *)                   \
 751                 &f->memory[bucket10_index * f->bucket_size];    \
 752         rte_prefetch0(bucket10);                                \
 753         rte_prefetch0((void *)(((uintptr_t) bucket10) + RTE_CACHE_LINE_SIZE));\
 754         rte_prefetch0((void *)(((uintptr_t) bucket10) + 2 * RTE_CACHE_LINE_SIZE));\
 755                                                                 \
 756         signature11 = RTE_MBUF_METADATA_UINT32(mbuf11, f->signature_offset);\
 757         bucket11_index = signature11 & (f->n_buckets - 1);      \
 758         bucket11 = (struct rte_bucket_4_32 *)                   \
 759                 &f->memory[bucket11_index * f->bucket_size];    \
 760         rte_prefetch0(bucket11);                                \
 761         rte_prefetch0((void *)(((uintptr_t) bucket11) + RTE_CACHE_LINE_SIZE));\
 762         rte_prefetch0((void *)(((uintptr_t) bucket11) + 2 * RTE_CACHE_LINE_SIZE));\
 763 }
 764
 765 #define lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,\
 766         bucket20, bucket21, pkts_mask_out, entries, f)          \
 767 {                                                               \
 768         void *a20, *a21;                                        \
 769         uint64_t pkt20_mask, pkt21_mask;                        \
 770         uint64_t *key20, *key21;                                \
 771         uint32_t pos20, pos21;                                  \
 772                                                                 \
 773         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 774         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 775                                                                 \
 776         lookup_key32_cmp(key20, bucket20, pos20);               \
 777         lookup_key32_cmp(key21, bucket21, pos21);               \
 778                                                                 \
 779         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
 780         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
 781         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 782                                                                 \
 783         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 784         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 785         rte_prefetch0(a20);                                     \
 786         rte_prefetch0(a21);                                     \
 787         entries[pkt20_index] = a20;                             \
 788         entries[pkt21_index] = a21;                             \
 789         lru_update(bucket20, pos20);                            \
 790         lru_update(bucket21, pos21);                            \
 791 }
 792
 793 #define lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21, bucket20, \
 794         bucket21, pkts_mask_out, entries, buckets_mask, buckets, keys, f)\
 795 {                                                               \
 796         struct rte_bucket_4_32 *bucket20_next, *bucket21_next;  \
 797         void *a20, *a21;                                        \
 798         uint64_t pkt20_mask, pkt21_mask, bucket20_mask, bucket21_mask;\
 799         uint64_t *key20, *key21;                                \
 800         uint32_t pos20, pos21;                                  \
 801                                                                 \
 802         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 803         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 804                                                                 \
 805         lookup_key32_cmp(key20, bucket20, pos20);               \
 806         lookup_key32_cmp(key21, bucket21, pos21);               \
 807                                                                 \
 808         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
 809         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
 810         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 811                                                                 \
 812         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 813         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 814         rte_prefetch0(a20);                                     \
 815         rte_prefetch0(a21);                                     \
 816         entries[pkt20_index] = a20;                             \
 817         entries[pkt21_index] = a21;                             \
 818                                                                 \
 819         bucket20_mask = (~pkt20_mask) & (bucket20->next_valid << pkt20_index);\
 820         bucket21_mask = (~pkt21_mask) & (bucket21->next_valid << pkt21_index);\
 821         buckets_mask |= bucket20_mask | bucket21_mask;          \
 822         bucket20_next = bucket20->next;                         \
 823         bucket21_next = bucket21->next;                         \
 824         buckets[pkt20_index] = bucket20_next;                   \
 825         buckets[pkt21_index] = bucket21_next;                   \
 826         keys[pkt20_index] = key20;                              \
 827         keys[pkt21_index] = key21;                              \
 828 }
 829
 830 static int
 831 rte_table_hash_lookup_key32_lru(
 832         void *table,
 833         struct rte_mbuf **pkts,
 834         uint64_t pkts_mask,
 835         uint64_t *lookup_hit_mask,
 836         void **entries)
 837 {
 838         struct rte_table_hash *f = (struct rte_table_hash *) table;
 839         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
 840         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 841         uint32_t pkt00_index, pkt01_index, pkt10_index;
 842         uint32_t pkt11_index, pkt20_index, pkt21_index;
 843         uint64_t pkts_mask_out = 0;
 844
 845         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 846         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
 847
 848         /* Cannot run the pipeline with less than 5 packets */
 849         if (__builtin_popcountll(pkts_mask) < 5) {
 850                 for ( ; pkts_mask; ) {
 851                         struct rte_bucket_4_32 *bucket;
 852                         struct rte_mbuf *mbuf;
 853                         uint32_t pkt_index;
 854
 855                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
 856                         lookup1_stage1(mbuf, bucket, f);
 857                         lookup1_stage2_lru(pkt_index, mbuf, bucket,
 858                                         pkts_mask_out, entries, f);
 859                 }
 860
 861                 *lookup_hit_mask = pkts_mask_out;
 862                 RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 863                 return 0;
 864         }
 865
 866         /*
 867          * Pipeline fill
 868          *
 869          */
 870         /* Pipeline stage 0 */
 871         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 872                 pkts_mask);
 873
 874         /* Pipeline feed */
 875         mbuf10 = mbuf00;
 876         mbuf11 = mbuf01;
 877         pkt10_index = pkt00_index;
 878         pkt11_index = pkt01_index;
 879
 880         /* Pipeline stage 0 */
 881         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 882                 pkts_mask);
 883
 884         /* Pipeline stage 1 */
 885         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 886
 887         /*
 888          * Pipeline run
 889          *
 890          */
 891         for ( ; pkts_mask; ) {
 892                 /* Pipeline feed */
 893                 bucket20 = bucket10;
 894                 bucket21 = bucket11;
 895                 mbuf20 = mbuf10;
 896                 mbuf21 = mbuf11;
 897                 mbuf10 = mbuf00;
 898                 mbuf11 = mbuf01;
 899                 pkt20_index = pkt10_index;
 900                 pkt21_index = pkt11_index;
 901                 pkt10_index = pkt00_index;
 902                 pkt11_index = pkt01_index;
 903
 904                 /* Pipeline stage 0 */
 905                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
 906                         mbuf00, mbuf01, pkts, pkts_mask);
 907
 908                 /* Pipeline stage 1 */
 909                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 910
 911                 /* Pipeline stage 2 */
 912                 lookup2_stage2_lru(pkt20_index, pkt21_index,
 913                         mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out,
 914                         entries, f);
 915         }
 916
 917         /*
 918          * Pipeline flush
 919          *
 920          */
 921         /* Pipeline feed */
 922         bucket20 = bucket10;
 923         bucket21 = bucket11;
 924         mbuf20 = mbuf10;
 925         mbuf21 = mbuf11;
 926         mbuf10 = mbuf00;
 927         mbuf11 = mbuf01;
 928         pkt20_index = pkt10_index;
 929         pkt21_index = pkt11_index;
 930         pkt10_index = pkt00_index;
 931         pkt11_index = pkt01_index;
 932
 933         /* Pipeline stage 1 */
 934         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 935
 936         /* Pipeline stage 2 */
 937         lookup2_stage2_lru(pkt20_index, pkt21_index,
 938                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
 939
 940         /* Pipeline feed */
 941         bucket20 = bucket10;
 942         bucket21 = bucket11;
 943         mbuf20 = mbuf10;
 944         mbuf21 = mbuf11;
 945         pkt20_index = pkt10_index;
 946         pkt21_index = pkt11_index;
 947
 948         /* Pipeline stage 2 */
 949         lookup2_stage2_lru(pkt20_index, pkt21_index,
 950                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
 951
 952         *lookup_hit_mask = pkts_mask_out;
 953         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 954         return 0;
 955 } /* rte_table_hash_lookup_key32_lru() */
 956
 957 static int
 958 rte_table_hash_lookup_key32_ext(
 959         void *table,
 960         struct rte_mbuf **pkts,
 961         uint64_t pkts_mask,
 962         uint64_t *lookup_hit_mask,
 963         void **entries)
 964 {
 965         struct rte_table_hash *f = (struct rte_table_hash *) table;
 966         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
 967         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 968         uint32_t pkt00_index, pkt01_index, pkt10_index;
 969         uint32_t pkt11_index, pkt20_index, pkt21_index;
 970         uint64_t pkts_mask_out = 0, buckets_mask = 0;
 971         struct rte_bucket_4_32 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
 972         uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
 973
 974         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 975         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
 976
 977         /* Cannot run the pipeline with less than 5 packets */
 978         if (__builtin_popcountll(pkts_mask) < 5) {
 979                 for ( ; pkts_mask; ) {
 980                         struct rte_bucket_4_32 *bucket;
 981                         struct rte_mbuf *mbuf;
 982                         uint32_t pkt_index;
 983
 984                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
 985                         lookup1_stage1(mbuf, bucket, f);
 986                         lookup1_stage2_ext(pkt_index, mbuf, bucket,
 987                                 pkts_mask_out, entries, buckets_mask, buckets,
 988                                 keys, f);
 989                 }
 990
 991                 goto grind_next_buckets;
 992         }
 993
 994         /*
 995          * Pipeline fill
 996          *
 997          */
 998         /* Pipeline stage 0 */
 999         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1000                 pkts_mask);
1001
1002         /* Pipeline feed */
1003         mbuf10 = mbuf00;
1004         mbuf11 = mbuf01;
1005         pkt10_index = pkt00_index;
1006         pkt11_index = pkt01_index;
1007
1008         /* Pipeline stage 0 */
1009         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1010                 pkts_mask);
1011
1012         /* Pipeline stage 1 */
1013         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1014
1015         /*
1016          * Pipeline run
1017          *
1018          */
1019         for ( ; pkts_mask; ) {
1020                 /* Pipeline feed */
1021                 bucket20 = bucket10;
1022                 bucket21 = bucket11;
1023                 mbuf20 = mbuf10;
1024                 mbuf21 = mbuf11;
1025                 mbuf10 = mbuf00;
1026                 mbuf11 = mbuf01;
1027                 pkt20_index = pkt10_index;
1028                 pkt21_index = pkt11_index;
1029                 pkt10_index = pkt00_index;
1030                 pkt11_index = pkt01_index;
1031
1032                 /* Pipeline stage 0 */
1033                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1034                         mbuf00, mbuf01, pkts, pkts_mask);
1035
1036                 /* Pipeline stage 1 */
1037                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1038
1039                 /* Pipeline stage 2 */
1040                 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1041                         bucket20, bucket21, pkts_mask_out, entries,
1042                         buckets_mask, buckets, keys, f);
1043         }
1044
1045         /*
1046          * Pipeline flush
1047          *
1048          */
1049         /* Pipeline feed */
1050         bucket20 = bucket10;
1051         bucket21 = bucket11;
1052         mbuf20 = mbuf10;
1053         mbuf21 = mbuf11;
1054         mbuf10 = mbuf00;
1055         mbuf11 = mbuf01;
1056         pkt20_index = pkt10_index;
1057         pkt21_index = pkt11_index;
1058         pkt10_index = pkt00_index;
1059         pkt11_index = pkt01_index;
1060
1061         /* Pipeline stage 1 */
1062         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1063
1064         /* Pipeline stage 2 */
1065         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1066                 bucket20, bucket21, pkts_mask_out, entries,
1067                 buckets_mask, buckets, keys, f);
1068
1069         /* Pipeline feed */
1070         bucket20 = bucket10;
1071         bucket21 = bucket11;
1072         mbuf20 = mbuf10;
1073         mbuf21 = mbuf11;
1074         pkt20_index = pkt10_index;
1075         pkt21_index = pkt11_index;
1076
1077         /* Pipeline stage 2 */
1078         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1079                 bucket20, bucket21, pkts_mask_out, entries,
1080                 buckets_mask, buckets, keys, f);
1081
1082 grind_next_buckets:
1083         /* Grind next buckets */
1084         for ( ; buckets_mask; ) {
1085                 uint64_t buckets_mask_next = 0;
1086
1087                 for ( ; buckets_mask; ) {
1088                         uint64_t pkt_mask;
1089                         uint32_t pkt_index;
1090
1091                         pkt_index = __builtin_ctzll(buckets_mask);
1092                         pkt_mask = 1LLU << pkt_index;
1093                         buckets_mask &= ~pkt_mask;
1094
1095                         lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1096                                 entries, buckets_mask_next, f);
1097                 }
1098
1099                 buckets_mask = buckets_mask_next;
1100         }
1101
1102         *lookup_hit_mask = pkts_mask_out;
1103         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1104         return 0;
1105 } /* rte_table_hash_lookup_key32_ext() */
1106
1107 static int
1108 rte_table_hash_key32_stats_read(void *table, struct rte_table_stats *stats, int clear)
1109 {
1110         struct rte_table_hash *t = (struct rte_table_hash *) table;
1111
1112         if (stats != NULL)
1113                 memcpy(stats, &t->stats, sizeof(t->stats));
1114
1115         if (clear)
1116                 memset(&t->stats, 0, sizeof(t->stats));
1117
1118         return 0;
1119 }
1120
1121 struct rte_table_ops rte_table_hash_key32_lru_ops = {
1122         .f_create = rte_table_hash_create_key32_lru,
1123         .f_free = rte_table_hash_free_key32_lru,
1124         .f_add = rte_table_hash_entry_add_key32_lru,
1125         .f_delete = rte_table_hash_entry_delete_key32_lru,
1126         .f_lookup = rte_table_hash_lookup_key32_lru,
1127         .f_stats = rte_table_hash_key32_stats_read,
1128 };
1129
1130 struct rte_table_ops rte_table_hash_key32_ext_ops = {
1131         .f_create = rte_table_hash_create_key32_ext,
1132         .f_free = rte_table_hash_free_key32_ext,
1133         .f_add = rte_table_hash_entry_add_key32_ext,
1134         .f_delete = rte_table_hash_entry_delete_key32_ext,
1135         .f_lookup = rte_table_hash_lookup_key32_ext,
1136         .f_stats = rte_table_hash_key32_stats_read,
1137 };