lib/librte_table/rte_table_hash_key16.c

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