lib/table/rte_table_hash_key32.c

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