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