lib/librte_table/rte_table_hash_key8.c

   1 /*-
   2  *       BSD LICENSE
   3  *
   4  *       Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
   5  *       All rights reserved.
   6  *
   7  *       Redistribution and use in source and binary forms, with or without
   8  *       modification, are permitted provided that the following conditions
   9  *       are met:
  10  *
  11  *      * Redistributions of source code must retain the above copyright
  12  *               notice, this list of conditions and the following disclaimer.
  13  *      * Redistributions in binary form must reproduce the above copyright
  14  *               notice, this list of conditions and the following disclaimer in
  15  *               the documentation and/or other materials provided with the
  16  *               distribution.
  17  *      * Neither the name of Intel Corporation nor the names of its
  18  *               contributors may be used to endorse or promote products derived
  19  *               from this software without specific prior written permission.
  20  *
  21  *       THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *       "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *       LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *       A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *       OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *       SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *       LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *       DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *       THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *       (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *       OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33 #include <string.h>
  34 #include <stdio.h>
  35
  36 #include <rte_common.h>
  37 #include <rte_mbuf.h>
  38 #include <rte_memory.h>
  39 #include <rte_malloc.h>
  40 #include <rte_log.h>
  41
  42 #include "rte_table_hash.h"
  43 #include "rte_lru.h"
  44
  45 #define RTE_TABLE_HASH_KEY_SIZE                                         8
  46
  47 #ifdef RTE_TABLE_STATS_COLLECT
  48
  49 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(table, val) \
  50         table->stats.n_pkts_in += val
  51 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(table, val) \
  52         table->stats.n_pkts_lookup_miss += val
  53
  54 #else
  55
  56 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(table, val)
  57 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(table, val)
  58
  59 #endif
  60
  61 struct rte_bucket_4_8 {
  62         /* Cache line 0 */
  63         uint64_t signature;
  64         uint64_t lru_list;
  65         struct rte_bucket_4_8 *next;
  66         uint64_t next_valid;
  67
  68         uint64_t key[4];
  69
  70         /* Cache line 1 */
  71         uint8_t data[0];
  72 };
  73
  74 struct rte_table_hash {
  75         struct rte_table_stats stats;
  76
  77         /* Input parameters */
  78         uint32_t n_buckets;
  79         uint32_t n_entries_per_bucket;
  80         uint32_t key_size;
  81         uint32_t entry_size;
  82         uint32_t bucket_size;
  83         uint32_t signature_offset;
  84         uint32_t key_offset;
  85         rte_table_hash_op_hash f_hash;
  86         uint64_t seed;
  87
  88         /* Extendible buckets */
  89         uint32_t n_buckets_ext;
  90         uint32_t stack_pos;
  91         uint32_t *stack;
  92
  93         /* Lookup table */
  94         uint8_t memory[0] __rte_cache_aligned;
  95 };
  96
  97 static int
  98 check_params_create_lru(struct rte_table_hash_key8_lru_params *params) {
  99         /* n_entries */
 100         if (params->n_entries == 0) {
 101                 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
 102                 return -EINVAL;
 103         }
 104
 105         /* f_hash */
 106         if (params->f_hash == NULL) {
 107                 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
 108                         __func__);
 109                 return -EINVAL;
 110         }
 111
 112         return 0;
 113 }
 114
 115 static void *
 116 rte_table_hash_create_key8_lru(void *params, int socket_id, uint32_t entry_size)
 117 {
 118         struct rte_table_hash_key8_lru_params *p =
 119                 (struct rte_table_hash_key8_lru_params *) params;
 120         struct rte_table_hash *f;
 121         uint32_t n_buckets, n_entries_per_bucket, key_size, bucket_size_cl;
 122         uint32_t total_size, i;
 123
 124         /* Check input parameters */
 125         if ((check_params_create_lru(p) != 0) ||
 126                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
 127                 ((sizeof(struct rte_bucket_4_8) % RTE_CACHE_LINE_SIZE) != 0)) {
 128                 return NULL;
 129         }
 130         n_entries_per_bucket = 4;
 131         key_size = 8;
 132
 133         /* Memory allocation */
 134         n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
 135                 n_entries_per_bucket);
 136         bucket_size_cl = (sizeof(struct rte_bucket_4_8) + n_entries_per_bucket *
 137                 entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
 138         total_size = sizeof(struct rte_table_hash) + n_buckets *
 139                 bucket_size_cl * RTE_CACHE_LINE_SIZE;
 140
 141         f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
 142         if (f == NULL) {
 143                 RTE_LOG(ERR, TABLE,
 144                         "%s: Cannot allocate %u bytes for hash table\n",
 145                         __func__, total_size);
 146                 return NULL;
 147         }
 148         RTE_LOG(INFO, TABLE,
 149                 "%s: Hash table memory footprint is %u bytes\n",
 150                 __func__, total_size);
 151
 152         /* Memory initialization */
 153         f->n_buckets = n_buckets;
 154         f->n_entries_per_bucket = n_entries_per_bucket;
 155         f->key_size = key_size;
 156         f->entry_size = entry_size;
 157         f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
 158         f->signature_offset = p->signature_offset;
 159         f->key_offset = p->key_offset;
 160         f->f_hash = p->f_hash;
 161         f->seed = p->seed;
 162
 163         for (i = 0; i < n_buckets; i++) {
 164                 struct rte_bucket_4_8 *bucket;
 165
 166                 bucket = (struct rte_bucket_4_8 *) &f->memory[i *
 167                         f->bucket_size];
 168                 bucket->lru_list = 0x0000000100020003LLU;
 169         }
 170
 171         return f;
 172 }
 173
 174 static int
 175 rte_table_hash_free_key8_lru(void *table)
 176 {
 177         struct rte_table_hash *f = (struct rte_table_hash *) table;
 178
 179         /* Check input parameters */
 180         if (f == NULL) {
 181                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 182                 return -EINVAL;
 183         }
 184
 185         rte_free(f);
 186         return 0;
 187 }
 188
 189 static int
 190 rte_table_hash_entry_add_key8_lru(
 191         void *table,
 192         void *key,
 193         void *entry,
 194         int *key_found,
 195         void **entry_ptr)
 196 {
 197         struct rte_table_hash *f = (struct rte_table_hash *) table;
 198         struct rte_bucket_4_8 *bucket;
 199         uint64_t signature, mask, pos;
 200         uint32_t bucket_index, i;
 201
 202         signature = f->f_hash(key, f->key_size, f->seed);
 203         bucket_index = signature & (f->n_buckets - 1);
 204         bucket = (struct rte_bucket_4_8 *)
 205                 &f->memory[bucket_index * f->bucket_size];
 206
 207         /* Key is present in the bucket */
 208         for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 209                 uint64_t bucket_signature = bucket->signature;
 210                 uint64_t bucket_key = bucket->key[i];
 211
 212                 if ((bucket_signature & mask) &&
 213                     (*((uint64_t *) key) == bucket_key)) {
 214                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 215
 216                         memcpy(bucket_data, entry, f->entry_size);
 217                         lru_update(bucket, i);
 218                         *key_found = 1;
 219                         *entry_ptr = (void *) bucket_data;
 220                         return 0;
 221                 }
 222         }
 223
 224         /* Key is not present in the bucket */
 225         for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 226                 uint64_t bucket_signature = bucket->signature;
 227
 228                 if ((bucket_signature & mask) == 0) {
 229                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 230
 231                         bucket->signature |= mask;
 232                         bucket->key[i] = *((uint64_t *) key);
 233                         memcpy(bucket_data, entry, f->entry_size);
 234                         lru_update(bucket, i);
 235                         *key_found = 0;
 236                         *entry_ptr = (void *) bucket_data;
 237
 238                         return 0;
 239                 }
 240         }
 241
 242         /* Bucket full: replace LRU entry */
 243         pos = lru_pos(bucket);
 244         bucket->key[pos] = *((uint64_t *) key);
 245         memcpy(&bucket->data[pos * f->entry_size], entry, f->entry_size);
 246         lru_update(bucket, pos);
 247         *key_found      = 0;
 248         *entry_ptr = (void *) &bucket->data[pos * f->entry_size];
 249
 250         return 0;
 251 }
 252
 253 static int
 254 rte_table_hash_entry_delete_key8_lru(
 255         void *table,
 256         void *key,
 257         int *key_found,
 258         void *entry)
 259 {
 260         struct rte_table_hash *f = (struct rte_table_hash *) table;
 261         struct rte_bucket_4_8 *bucket;
 262         uint64_t signature, mask;
 263         uint32_t bucket_index, i;
 264
 265         signature = f->f_hash(key, f->key_size, f->seed);
 266         bucket_index = signature & (f->n_buckets - 1);
 267         bucket = (struct rte_bucket_4_8 *)
 268                 &f->memory[bucket_index * f->bucket_size];
 269
 270         /* Key is present in the bucket */
 271         for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 272                 uint64_t bucket_signature = bucket->signature;
 273                 uint64_t bucket_key = bucket->key[i];
 274
 275                 if ((bucket_signature & mask) &&
 276                     (*((uint64_t *) key) == bucket_key)) {
 277                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
 278
 279                         bucket->signature &= ~mask;
 280                         *key_found = 1;
 281                         if (entry)
 282                                 memcpy(entry, bucket_data, f->entry_size);
 283
 284                         return 0;
 285                 }
 286         }
 287
 288         /* Key is not present in the bucket */
 289         *key_found = 0;
 290         return 0;
 291 }
 292
 293 static int
 294 check_params_create_ext(struct rte_table_hash_key8_ext_params *params) {
 295         /* n_entries */
 296         if (params->n_entries == 0) {
 297                 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
 298                 return -EINVAL;
 299         }
 300
 301         /* n_entries_ext */
 302         if (params->n_entries_ext == 0) {
 303                 RTE_LOG(ERR, TABLE, "%s: n_entries_ext is zero\n", __func__);
 304                 return -EINVAL;
 305         }
 306
 307         /* f_hash */
 308         if (params->f_hash == NULL) {
 309                 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
 310                         __func__);
 311                 return -EINVAL;
 312         }
 313
 314         return 0;
 315 }
 316
 317 static void *
 318 rte_table_hash_create_key8_ext(void *params, int socket_id, uint32_t entry_size)
 319 {
 320         struct rte_table_hash_key8_ext_params *p =
 321                 (struct rte_table_hash_key8_ext_params *) params;
 322         struct rte_table_hash *f;
 323         uint32_t n_buckets, n_buckets_ext, n_entries_per_bucket, key_size;
 324         uint32_t bucket_size_cl, stack_size_cl, total_size, i;
 325
 326         /* Check input parameters */
 327         if ((check_params_create_ext(p) != 0) ||
 328                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
 329                 ((sizeof(struct rte_bucket_4_8) % RTE_CACHE_LINE_SIZE) != 0))
 330                 return NULL;
 331
 332         n_entries_per_bucket = 4;
 333         key_size = 8;
 334
 335         /* Memory allocation */
 336         n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
 337                 n_entries_per_bucket);
 338         n_buckets_ext = (p->n_entries_ext + n_entries_per_bucket - 1) /
 339                 n_entries_per_bucket;
 340         bucket_size_cl = (sizeof(struct rte_bucket_4_8) + n_entries_per_bucket *
 341                 entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
 342         stack_size_cl = (n_buckets_ext * sizeof(uint32_t) + RTE_CACHE_LINE_SIZE - 1)
 343                 / RTE_CACHE_LINE_SIZE;
 344         total_size = sizeof(struct rte_table_hash) + ((n_buckets +
 345                 n_buckets_ext) * bucket_size_cl + stack_size_cl) *
 346                 RTE_CACHE_LINE_SIZE;
 347
 348         f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
 349         if (f == NULL) {
 350                 RTE_LOG(ERR, TABLE,
 351                         "%s: Cannot allocate %u bytes for hash table\n",
 352                         __func__, total_size);
 353                 return NULL;
 354         }
 355         RTE_LOG(INFO, TABLE,
 356                 "%s: Hash table memory footprint is %u bytes\n",
 357                 __func__, total_size);
 358
 359         /* Memory initialization */
 360         f->n_buckets = n_buckets;
 361         f->n_entries_per_bucket = n_entries_per_bucket;
 362         f->key_size = key_size;
 363         f->entry_size = entry_size;
 364         f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
 365         f->signature_offset = p->signature_offset;
 366         f->key_offset = p->key_offset;
 367         f->f_hash = p->f_hash;
 368         f->seed = p->seed;
 369
 370         f->n_buckets_ext = n_buckets_ext;
 371         f->stack_pos = n_buckets_ext;
 372         f->stack = (uint32_t *)
 373                 &f->memory[(n_buckets + n_buckets_ext) * f->bucket_size];
 374
 375         for (i = 0; i < n_buckets_ext; i++)
 376                 f->stack[i] = i;
 377
 378         return f;
 379 }
 380
 381 static int
 382 rte_table_hash_free_key8_ext(void *table)
 383 {
 384         struct rte_table_hash *f = (struct rte_table_hash *) table;
 385
 386         /* Check input parameters */
 387         if (f == NULL) {
 388                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
 389                 return -EINVAL;
 390         }
 391
 392         rte_free(f);
 393         return 0;
 394 }
 395
 396 static int
 397 rte_table_hash_entry_add_key8_ext(
 398         void *table,
 399         void *key,
 400         void *entry,
 401         int *key_found,
 402         void **entry_ptr)
 403 {
 404         struct rte_table_hash *f = (struct rte_table_hash *) table;
 405         struct rte_bucket_4_8 *bucket0, *bucket, *bucket_prev;
 406         uint64_t signature;
 407         uint32_t bucket_index, i;
 408
 409         signature = f->f_hash(key, f->key_size, f->seed);
 410         bucket_index = signature & (f->n_buckets - 1);
 411         bucket0 = (struct rte_bucket_4_8 *)
 412                 &f->memory[bucket_index * f->bucket_size];
 413
 414         /* Key is present in the bucket */
 415         for (bucket = bucket0; bucket != NULL; bucket = bucket->next) {
 416                 uint64_t mask;
 417
 418                 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 419                         uint64_t bucket_signature = bucket->signature;
 420                         uint64_t bucket_key = bucket->key[i];
 421
 422                         if ((bucket_signature & mask) &&
 423                                         (*((uint64_t *) key) == bucket_key)) {
 424                                 uint8_t *bucket_data = &bucket->data[i *
 425                                         f->entry_size];
 426
 427                                 memcpy(bucket_data, entry, f->entry_size);
 428                                 *key_found = 1;
 429                                 *entry_ptr = (void *) bucket_data;
 430                                 return 0;
 431                         }
 432                 }
 433         }
 434
 435         /* Key is not present in the bucket */
 436         for (bucket_prev = NULL, bucket = bucket0;
 437                 bucket != NULL; bucket_prev = bucket, bucket = bucket->next) {
 438                 uint64_t mask;
 439
 440                 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 441                         uint64_t bucket_signature = bucket->signature;
 442
 443                         if ((bucket_signature & mask) == 0) {
 444                                 uint8_t *bucket_data = &bucket->data[i *
 445                                         f->entry_size];
 446
 447                                 bucket->signature |= mask;
 448                                 bucket->key[i] = *((uint64_t *) key);
 449                                 memcpy(bucket_data, entry, f->entry_size);
 450                                 *key_found = 0;
 451                                 *entry_ptr = (void *) bucket_data;
 452
 453                                 return 0;
 454                         }
 455                 }
 456         }
 457
 458         /* Bucket full: extend bucket */
 459         if (f->stack_pos > 0) {
 460                 bucket_index = f->stack[--f->stack_pos];
 461
 462                 bucket = (struct rte_bucket_4_8 *) &f->memory[(f->n_buckets +
 463                         bucket_index) * f->bucket_size];
 464                 bucket_prev->next = bucket;
 465                 bucket_prev->next_valid = 1;
 466
 467                 bucket->signature = 1;
 468                 bucket->key[0] = *((uint64_t *) key);
 469                 memcpy(&bucket->data[0], entry, f->entry_size);
 470                 *key_found = 0;
 471                 *entry_ptr = (void *) &bucket->data[0];
 472                 return 0;
 473         }
 474
 475         return -ENOSPC;
 476 }
 477
 478 static int
 479 rte_table_hash_entry_delete_key8_ext(
 480         void *table,
 481         void *key,
 482         int *key_found,
 483         void *entry)
 484 {
 485         struct rte_table_hash *f = (struct rte_table_hash *) table;
 486         struct rte_bucket_4_8 *bucket0, *bucket, *bucket_prev;
 487         uint64_t signature;
 488         uint32_t bucket_index, i;
 489
 490         signature = f->f_hash(key, f->key_size, f->seed);
 491         bucket_index = signature & (f->n_buckets - 1);
 492         bucket0 = (struct rte_bucket_4_8 *)
 493                 &f->memory[bucket_index * f->bucket_size];
 494
 495         /* Key is present in the bucket */
 496         for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
 497                 bucket_prev = bucket, bucket = bucket->next) {
 498                 uint64_t mask;
 499
 500                 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 501                         uint64_t bucket_signature = bucket->signature;
 502                         uint64_t bucket_key = bucket->key[i];
 503
 504                         if ((bucket_signature & mask) &&
 505                                 (*((uint64_t *) key) == bucket_key)) {
 506                                 uint8_t *bucket_data = &bucket->data[i *
 507                                         f->entry_size];
 508
 509                                 bucket->signature &= ~mask;
 510                                 *key_found = 1;
 511                                 if (entry)
 512                                         memcpy(entry, bucket_data,
 513                                                 f->entry_size);
 514
 515                                 if ((bucket->signature == 0) &&
 516                                     (bucket_prev != NULL)) {
 517                                         bucket_prev->next = bucket->next;
 518                                         bucket_prev->next_valid =
 519                                                 bucket->next_valid;
 520
 521                                         memset(bucket, 0,
 522                                                 sizeof(struct rte_bucket_4_8));
 523                                         bucket_index = (((uint8_t *)bucket -
 524                                                 (uint8_t *)f->memory)/f->bucket_size) - f->n_buckets;
 525                                         f->stack[f->stack_pos++] = bucket_index;
 526                                 }
 527
 528                                 return 0;
 529                         }
 530                 }
 531         }
 532
 533         /* Key is not present in the bucket */
 534         *key_found = 0;
 535         return 0;
 536 }
 537
 538 #define lookup_key8_cmp(key_in, bucket, pos)                    \
 539 {                                                               \
 540         uint64_t xor[4], signature;                             \
 541                                                                 \
 542         signature = ~bucket->signature;                         \
 543                                                                 \
 544         xor[0] = (key_in[0] ^    bucket->key[0]) | (signature & 1);\
 545         xor[1] = (key_in[0] ^    bucket->key[1]) | (signature & 2);\
 546         xor[2] = (key_in[0] ^    bucket->key[2]) | (signature & 4);\
 547         xor[3] = (key_in[0] ^    bucket->key[3]) | (signature & 8);\
 548                                                                 \
 549         pos = 4;                                                \
 550         if (xor[0] == 0)                                        \
 551                 pos = 0;                                        \
 552         if (xor[1] == 0)                                        \
 553                 pos = 1;                                        \
 554         if (xor[2] == 0)                                        \
 555                 pos = 2;                                        \
 556         if (xor[3] == 0)                                        \
 557                 pos = 3;                                        \
 558 }
 559
 560 #define lookup1_stage0(pkt0_index, mbuf0, pkts, pkts_mask)      \
 561 {                                                               \
 562         uint64_t pkt_mask;                                      \
 563                                                                 \
 564         pkt0_index = __builtin_ctzll(pkts_mask);                \
 565         pkt_mask = 1LLU << pkt0_index;                          \
 566         pkts_mask &= ~pkt_mask;                                 \
 567                                                                 \
 568         mbuf0 = pkts[pkt0_index];                               \
 569         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf0, 0));   \
 570 }
 571
 572 #define lookup1_stage1(mbuf1, bucket1, f)                       \
 573 {                                                               \
 574         uint64_t signature;                                     \
 575         uint32_t bucket_index;                                  \
 576                                                                 \
 577         signature = RTE_MBUF_METADATA_UINT32(mbuf1, f->signature_offset);\
 578         bucket_index = signature & (f->n_buckets - 1);          \
 579         bucket1 = (struct rte_bucket_4_8 *)                     \
 580                 &f->memory[bucket_index * f->bucket_size];      \
 581         rte_prefetch0(bucket1);                                 \
 582 }
 583
 584 #define lookup1_stage1_dosig(mbuf1, bucket1, f)                 \
 585 {                                                               \
 586         uint64_t *key;                                          \
 587         uint64_t signature;                                     \
 588         uint32_t bucket_index;                                  \
 589                                                                 \
 590         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf1, f->key_offset);\
 591         signature = f->f_hash(key, RTE_TABLE_HASH_KEY_SIZE, f->seed);\
 592         bucket_index = signature & (f->n_buckets - 1);          \
 593         bucket1 = (struct rte_bucket_4_8 *)                     \
 594                 &f->memory[bucket_index * f->bucket_size];      \
 595         rte_prefetch0(bucket1);                                 \
 596 }
 597
 598 #define lookup1_stage2_lru(pkt2_index, mbuf2, bucket2,          \
 599         pkts_mask_out, entries, f)                              \
 600 {                                                               \
 601         void *a;                                                \
 602         uint64_t pkt_mask;                                      \
 603         uint64_t *key;                                          \
 604         uint32_t pos;                                           \
 605                                                                 \
 606         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 607                                                                 \
 608         lookup_key8_cmp(key, bucket2, pos);                     \
 609                                                                 \
 610         pkt_mask = ((bucket2->signature >> pos) & 1LLU) << pkt2_index;\
 611         pkts_mask_out |= pkt_mask;                              \
 612                                                                 \
 613         a = (void *) &bucket2->data[pos * f->entry_size];       \
 614         rte_prefetch0(a);                                       \
 615         entries[pkt2_index] = a;                                \
 616         lru_update(bucket2, pos);                               \
 617 }
 618
 619 #define lookup1_stage2_ext(pkt2_index, mbuf2, bucket2, pkts_mask_out,\
 620         entries, buckets_mask, buckets, keys, f)                \
 621 {                                                               \
 622         struct rte_bucket_4_8 *bucket_next;                     \
 623         void *a;                                                \
 624         uint64_t pkt_mask, bucket_mask;                         \
 625         uint64_t *key;                                          \
 626         uint32_t pos;                                           \
 627                                                                 \
 628         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
 629                                                                 \
 630         lookup_key8_cmp(key, bucket2, pos);                     \
 631                                                                 \
 632         pkt_mask = ((bucket2->signature >> pos) & 1LLU) << pkt2_index;\
 633         pkts_mask_out |= pkt_mask;                              \
 634                                                                 \
 635         a = (void *) &bucket2->data[pos * f->entry_size];       \
 636         rte_prefetch0(a);                                       \
 637         entries[pkt2_index] = a;                                \
 638                                                                 \
 639         bucket_mask = (~pkt_mask) & (bucket2->next_valid << pkt2_index);\
 640         buckets_mask |= bucket_mask;                            \
 641         bucket_next = bucket2->next;                            \
 642         buckets[pkt2_index] = bucket_next;                      \
 643         keys[pkt2_index] = key;                                 \
 644 }
 645
 646 #define lookup_grinder(pkt_index, buckets, keys, pkts_mask_out, entries,\
 647         buckets_mask, f)                                        \
 648 {                                                               \
 649         struct rte_bucket_4_8 *bucket, *bucket_next;            \
 650         void *a;                                                \
 651         uint64_t pkt_mask, bucket_mask;                         \
 652         uint64_t *key;                                          \
 653         uint32_t pos;                                           \
 654                                                                 \
 655         bucket = buckets[pkt_index];                            \
 656         key = keys[pkt_index];                                  \
 657                                                                 \
 658         lookup_key8_cmp(key, bucket, pos);                      \
 659                                                                 \
 660         pkt_mask = ((bucket->signature >> pos) & 1LLU) << pkt_index;\
 661         pkts_mask_out |= pkt_mask;                              \
 662                                                                 \
 663         a = (void *) &bucket->data[pos * f->entry_size];        \
 664         rte_prefetch0(a);                                       \
 665         entries[pkt_index] = a;                                 \
 666                                                                 \
 667         bucket_mask = (~pkt_mask) & (bucket->next_valid << pkt_index);\
 668         buckets_mask |= bucket_mask;                            \
 669         bucket_next = bucket->next;                             \
 670         rte_prefetch0(bucket_next);                             \
 671         buckets[pkt_index] = bucket_next;                       \
 672         keys[pkt_index] = key;                                  \
 673 }
 674
 675 #define lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01,\
 676         pkts, pkts_mask)                                        \
 677 {                                                               \
 678         uint64_t pkt00_mask, pkt01_mask;                        \
 679                                                                 \
 680         pkt00_index = __builtin_ctzll(pkts_mask);               \
 681         pkt00_mask = 1LLU << pkt00_index;                       \
 682         pkts_mask &= ~pkt00_mask;                               \
 683                                                                 \
 684         mbuf00 = pkts[pkt00_index];                             \
 685         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0));  \
 686                                                                 \
 687         pkt01_index = __builtin_ctzll(pkts_mask);               \
 688         pkt01_mask = 1LLU << pkt01_index;                       \
 689         pkts_mask &= ~pkt01_mask;                               \
 690                                                                 \
 691         mbuf01 = pkts[pkt01_index];                             \
 692         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0));  \
 693 }
 694
 695 #define lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,\
 696         mbuf00, mbuf01, pkts, pkts_mask)                        \
 697 {                                                               \
 698         uint64_t pkt00_mask, pkt01_mask;                        \
 699                                                                 \
 700         pkt00_index = __builtin_ctzll(pkts_mask);               \
 701         pkt00_mask = 1LLU << pkt00_index;                       \
 702         pkts_mask &= ~pkt00_mask;                               \
 703                                                                 \
 704         mbuf00 = pkts[pkt00_index];                             \
 705         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0));  \
 706                                                                 \
 707         pkt01_index = __builtin_ctzll(pkts_mask);               \
 708         if (pkts_mask == 0)                                     \
 709                 pkt01_index = pkt00_index;                      \
 710                                                                 \
 711         pkt01_mask = 1LLU << pkt01_index;                       \
 712         pkts_mask &= ~pkt01_mask;                               \
 713                                                                 \
 714         mbuf01 = pkts[pkt01_index];                             \
 715         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0));  \
 716 }
 717
 718 #define lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f)   \
 719 {                                                               \
 720         uint64_t signature10, signature11;                      \
 721         uint32_t bucket10_index, bucket11_index;                \
 722                                                                 \
 723         signature10 = RTE_MBUF_METADATA_UINT32(mbuf10, f->signature_offset);\
 724         bucket10_index = signature10 & (f->n_buckets - 1);      \
 725         bucket10 = (struct rte_bucket_4_8 *)                    \
 726                 &f->memory[bucket10_index * f->bucket_size];    \
 727         rte_prefetch0(bucket10);                                \
 728                                                                 \
 729         signature11 = RTE_MBUF_METADATA_UINT32(mbuf11, f->signature_offset);\
 730         bucket11_index = signature11 & (f->n_buckets - 1);      \
 731         bucket11 = (struct rte_bucket_4_8 *)                    \
 732                 &f->memory[bucket11_index * f->bucket_size];    \
 733         rte_prefetch0(bucket11);                                \
 734 }
 735
 736 #define lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f)\
 737 {                                                               \
 738         uint64_t *key10, *key11;                                \
 739         uint64_t signature10, signature11;                      \
 740         uint32_t bucket10_index, bucket11_index;                \
 741         rte_table_hash_op_hash f_hash = f->f_hash;              \
 742         uint64_t seed = f->seed;                                \
 743         uint32_t key_offset = f->key_offset;                    \
 744                                                                 \
 745         key10 = RTE_MBUF_METADATA_UINT64_PTR(mbuf10, key_offset);\
 746         key11 = RTE_MBUF_METADATA_UINT64_PTR(mbuf11, key_offset);\
 747                                                                 \
 748         signature10 = f_hash(key10, RTE_TABLE_HASH_KEY_SIZE, seed);\
 749         bucket10_index = signature10 & (f->n_buckets - 1);      \
 750         bucket10 = (struct rte_bucket_4_8 *)                    \
 751                 &f->memory[bucket10_index * f->bucket_size];    \
 752         rte_prefetch0(bucket10);                                \
 753                                                                 \
 754         signature11 = f_hash(key11, RTE_TABLE_HASH_KEY_SIZE, seed);\
 755         bucket11_index = signature11 & (f->n_buckets - 1);      \
 756         bucket11 = (struct rte_bucket_4_8 *)                    \
 757                 &f->memory[bucket11_index * f->bucket_size];    \
 758         rte_prefetch0(bucket11);                                \
 759 }
 760
 761 #define lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,\
 762         bucket20, bucket21, pkts_mask_out, entries, f)          \
 763 {                                                               \
 764         void *a20, *a21;                                        \
 765         uint64_t pkt20_mask, pkt21_mask;                        \
 766         uint64_t *key20, *key21;                                \
 767         uint32_t pos20, pos21;                                  \
 768                                                                 \
 769         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 770         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 771                                                                 \
 772         lookup_key8_cmp(key20, bucket20, pos20);                \
 773         lookup_key8_cmp(key21, bucket21, pos21);                \
 774                                                                 \
 775         pkt20_mask = ((bucket20->signature >> pos20) & 1LLU) << pkt20_index;\
 776         pkt21_mask = ((bucket21->signature >> pos21) & 1LLU) << pkt21_index;\
 777         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 778                                                                 \
 779         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 780         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 781         rte_prefetch0(a20);                                     \
 782         rte_prefetch0(a21);                                     \
 783         entries[pkt20_index] = a20;                             \
 784         entries[pkt21_index] = a21;                             \
 785         lru_update(bucket20, pos20);                            \
 786         lru_update(bucket21, pos21);                            \
 787 }
 788
 789 #define lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21, bucket20, \
 790         bucket21, pkts_mask_out, entries, buckets_mask, buckets, keys, f)\
 791 {                                                               \
 792         struct rte_bucket_4_8 *bucket20_next, *bucket21_next;   \
 793         void *a20, *a21;                                        \
 794         uint64_t pkt20_mask, pkt21_mask, bucket20_mask, bucket21_mask;\
 795         uint64_t *key20, *key21;                                \
 796         uint32_t pos20, pos21;                                  \
 797                                                                 \
 798         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
 799         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
 800                                                                 \
 801         lookup_key8_cmp(key20, bucket20, pos20);                \
 802         lookup_key8_cmp(key21, bucket21, pos21);                \
 803                                                                 \
 804         pkt20_mask = ((bucket20->signature >> pos20) & 1LLU) << pkt20_index;\
 805         pkt21_mask = ((bucket21->signature >> pos21) & 1LLU) << pkt21_index;\
 806         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
 807                                                                 \
 808         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
 809         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
 810         rte_prefetch0(a20);                                     \
 811         rte_prefetch0(a21);                                     \
 812         entries[pkt20_index] = a20;                             \
 813         entries[pkt21_index] = a21;                             \
 814                                                                 \
 815         bucket20_mask = (~pkt20_mask) & (bucket20->next_valid << pkt20_index);\
 816         bucket21_mask = (~pkt21_mask) & (bucket21->next_valid << pkt21_index);\
 817         buckets_mask |= bucket20_mask | bucket21_mask;          \
 818         bucket20_next = bucket20->next;                         \
 819         bucket21_next = bucket21->next;                         \
 820         buckets[pkt20_index] = bucket20_next;                   \
 821         buckets[pkt21_index] = bucket21_next;                   \
 822         keys[pkt20_index] = key20;                              \
 823         keys[pkt21_index] = key21;                              \
 824 }
 825
 826 static int
 827 rte_table_hash_lookup_key8_lru(
 828         void *table,
 829         struct rte_mbuf **pkts,
 830         uint64_t pkts_mask,
 831         uint64_t *lookup_hit_mask,
 832         void **entries)
 833 {
 834         struct rte_table_hash *f = (struct rte_table_hash *) table;
 835         struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
 836         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 837         uint32_t pkt00_index, pkt01_index, pkt10_index,
 838                         pkt11_index, pkt20_index, pkt21_index;
 839         uint64_t pkts_mask_out = 0;
 840
 841         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 842         RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
 843
 844         /* Cannot run the pipeline with less than 5 packets */
 845         if (__builtin_popcountll(pkts_mask) < 5) {
 846                 for ( ; pkts_mask; ) {
 847                         struct rte_bucket_4_8 *bucket;
 848                         struct rte_mbuf *mbuf;
 849                         uint32_t pkt_index;
 850
 851                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
 852                         lookup1_stage1(mbuf, bucket, f);
 853                         lookup1_stage2_lru(pkt_index, mbuf, bucket,
 854                                         pkts_mask_out, entries, f);
 855                 }
 856
 857                 *lookup_hit_mask = pkts_mask_out;
 858                 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 859                 return 0;
 860         }
 861
 862         /*
 863          * Pipeline fill
 864          *
 865          */
 866         /* Pipeline stage 0 */
 867         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 868                 pkts_mask);
 869
 870         /* Pipeline feed */
 871         mbuf10 = mbuf00;
 872         mbuf11 = mbuf01;
 873         pkt10_index = pkt00_index;
 874         pkt11_index = pkt01_index;
 875
 876         /* Pipeline stage 0 */
 877         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 878                 pkts_mask);
 879
 880         /* Pipeline stage 1 */
 881         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 882
 883         /*
 884          * Pipeline run
 885          *
 886          */
 887         for ( ; pkts_mask; ) {
 888                 /* Pipeline feed */
 889                 bucket20 = bucket10;
 890                 bucket21 = bucket11;
 891                 mbuf20 = mbuf10;
 892                 mbuf21 = mbuf11;
 893                 mbuf10 = mbuf00;
 894                 mbuf11 = mbuf01;
 895                 pkt20_index = pkt10_index;
 896                 pkt21_index = pkt11_index;
 897                 pkt10_index = pkt00_index;
 898                 pkt11_index = pkt01_index;
 899
 900                 /* Pipeline stage 0 */
 901                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
 902                         mbuf00, mbuf01, pkts, pkts_mask);
 903
 904                 /* Pipeline stage 1 */
 905                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 906
 907                 /* Pipeline stage 2 */
 908                 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
 909                         bucket20, bucket21, pkts_mask_out, entries, f);
 910         }
 911
 912         /*
 913          * Pipeline flush
 914          *
 915          */
 916         /* Pipeline feed */
 917         bucket20 = bucket10;
 918         bucket21 = bucket11;
 919         mbuf20 = mbuf10;
 920         mbuf21 = mbuf11;
 921         mbuf10 = mbuf00;
 922         mbuf11 = mbuf01;
 923         pkt20_index = pkt10_index;
 924         pkt21_index = pkt11_index;
 925         pkt10_index = pkt00_index;
 926         pkt11_index = pkt01_index;
 927
 928         /* Pipeline stage 1 */
 929         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
 930
 931         /* Pipeline stage 2 */
 932         lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
 933                 bucket20, bucket21, pkts_mask_out, entries, f);
 934
 935         /* Pipeline feed */
 936         bucket20 = bucket10;
 937         bucket21 = bucket11;
 938         mbuf20 = mbuf10;
 939         mbuf21 = mbuf11;
 940         pkt20_index = pkt10_index;
 941         pkt21_index = pkt11_index;
 942
 943         /* Pipeline stage 2 */
 944         lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
 945                 bucket20, bucket21, pkts_mask_out, entries, f);
 946
 947         *lookup_hit_mask = pkts_mask_out;
 948         RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 949         return 0;
 950 } /* rte_table_hash_lookup_key8_lru() */
 951
 952 static int
 953 rte_table_hash_lookup_key8_lru_dosig(
 954         void *table,
 955         struct rte_mbuf **pkts,
 956         uint64_t pkts_mask,
 957         uint64_t *lookup_hit_mask,
 958         void **entries)
 959 {
 960         struct rte_table_hash *f = (struct rte_table_hash *) table;
 961         struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
 962         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
 963         uint32_t pkt00_index, pkt01_index, pkt10_index;
 964         uint32_t pkt11_index, pkt20_index, pkt21_index;
 965         uint64_t pkts_mask_out = 0;
 966
 967         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 968         RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
 969
 970         /* Cannot run the pipeline with less than 5 packets */
 971         if (__builtin_popcountll(pkts_mask) < 5) {
 972                 for ( ; pkts_mask; ) {
 973                         struct rte_bucket_4_8 *bucket;
 974                         struct rte_mbuf *mbuf;
 975                         uint32_t pkt_index;
 976
 977                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
 978                         lookup1_stage1_dosig(mbuf, bucket, f);
 979                         lookup1_stage2_lru(pkt_index, mbuf, bucket,
 980                                 pkts_mask_out, entries, f);
 981                 }
 982
 983                 *lookup_hit_mask = pkts_mask_out;
 984                 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 985                 return 0;
 986         }
 987
 988         /*
 989          * Pipeline fill
 990          *
 991          */
 992         /* Pipeline stage 0 */
 993         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
 994                 pkts_mask);
 995
 996         /* Pipeline feed */
 997         mbuf10 = mbuf00;
 998         mbuf11 = mbuf01;
 999         pkt10_index = pkt00_index;
1000         pkt11_index = pkt01_index;
1001
1002         /* Pipeline stage 0 */
1003         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1004                 pkts_mask);
1005
1006         /* Pipeline stage 1 */
1007         lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1008
1009         /*
1010          * Pipeline run
1011          *
1012          */
1013         for ( ; pkts_mask; ) {
1014                 /* Pipeline feed */
1015                 bucket20 = bucket10;
1016                 bucket21 = bucket11;
1017                 mbuf20 = mbuf10;
1018                 mbuf21 = mbuf11;
1019                 mbuf10 = mbuf00;
1020                 mbuf11 = mbuf01;
1021                 pkt20_index = pkt10_index;
1022                 pkt21_index = pkt11_index;
1023                 pkt10_index = pkt00_index;
1024                 pkt11_index = pkt01_index;
1025
1026                 /* Pipeline stage 0 */
1027                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1028                         mbuf00, mbuf01, pkts, pkts_mask);
1029
1030                 /* Pipeline stage 1 */
1031                 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1032
1033                 /* Pipeline stage 2 */
1034                 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1035                         bucket20, bucket21, pkts_mask_out, entries, f);
1036         }
1037
1038         /*
1039          * Pipeline flush
1040          *
1041          */
1042         /* Pipeline feed */
1043         bucket20 = bucket10;
1044         bucket21 = bucket11;
1045         mbuf20 = mbuf10;
1046         mbuf21 = mbuf11;
1047         mbuf10 = mbuf00;
1048         mbuf11 = mbuf01;
1049         pkt20_index = pkt10_index;
1050         pkt21_index = pkt11_index;
1051         pkt10_index = pkt00_index;
1052         pkt11_index = pkt01_index;
1053
1054         /* Pipeline stage 1 */
1055         lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1056
1057         /* Pipeline stage 2 */
1058         lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1059                 bucket20, bucket21, pkts_mask_out, entries, f);
1060
1061         /* Pipeline feed */
1062         bucket20 = bucket10;
1063         bucket21 = bucket11;
1064         mbuf20 = mbuf10;
1065         mbuf21 = mbuf11;
1066         pkt20_index = pkt10_index;
1067         pkt21_index = pkt11_index;
1068
1069         /* Pipeline stage 2 */
1070         lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1071                 bucket20, bucket21, pkts_mask_out, entries, f);
1072
1073         *lookup_hit_mask = pkts_mask_out;
1074         RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1075         return 0;
1076 } /* rte_table_hash_lookup_key8_lru_dosig() */
1077
1078 static int
1079 rte_table_hash_lookup_key8_ext(
1080         void *table,
1081         struct rte_mbuf **pkts,
1082         uint64_t pkts_mask,
1083         uint64_t *lookup_hit_mask,
1084         void **entries)
1085 {
1086         struct rte_table_hash *f = (struct rte_table_hash *) table;
1087         struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
1088         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
1089         uint32_t pkt00_index, pkt01_index, pkt10_index;
1090         uint32_t pkt11_index, pkt20_index, pkt21_index;
1091         uint64_t pkts_mask_out = 0, buckets_mask = 0;
1092         struct rte_bucket_4_8 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
1093         uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
1094
1095         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
1096         RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
1097
1098         /* Cannot run the pipeline with less than 5 packets */
1099         if (__builtin_popcountll(pkts_mask) < 5) {
1100                 for ( ; pkts_mask; ) {
1101                         struct rte_bucket_4_8 *bucket;
1102                         struct rte_mbuf *mbuf;
1103                         uint32_t pkt_index;
1104
1105                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
1106                         lookup1_stage1(mbuf, bucket, f);
1107                         lookup1_stage2_ext(pkt_index, mbuf, bucket,
1108                                 pkts_mask_out, entries, buckets_mask, buckets,
1109                                 keys, f);
1110                 }
1111
1112                 goto grind_next_buckets;
1113         }
1114
1115         /*
1116          * Pipeline fill
1117          *
1118          */
1119         /* Pipeline stage 0 */
1120         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1121                 pkts_mask);
1122
1123         /* Pipeline feed */
1124         mbuf10 = mbuf00;
1125         mbuf11 = mbuf01;
1126         pkt10_index = pkt00_index;
1127         pkt11_index = pkt01_index;
1128
1129         /* Pipeline stage 0 */
1130         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1131                 pkts_mask);
1132
1133         /* Pipeline stage 1 */
1134         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1135
1136         /*
1137          * Pipeline run
1138          *
1139          */
1140         for ( ; pkts_mask; ) {
1141                 /* Pipeline feed */
1142                 bucket20 = bucket10;
1143                 bucket21 = bucket11;
1144                 mbuf20 = mbuf10;
1145                 mbuf21 = mbuf11;
1146                 mbuf10 = mbuf00;
1147                 mbuf11 = mbuf01;
1148                 pkt20_index = pkt10_index;
1149                 pkt21_index = pkt11_index;
1150                 pkt10_index = pkt00_index;
1151                 pkt11_index = pkt01_index;
1152
1153                 /* Pipeline stage 0 */
1154                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1155                         mbuf00, mbuf01, pkts, pkts_mask);
1156
1157                 /* Pipeline stage 1 */
1158                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1159
1160                 /* Pipeline stage 2 */
1161                 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1162                         bucket20, bucket21, pkts_mask_out, entries,
1163                         buckets_mask, buckets, keys, f);
1164         }
1165
1166         /*
1167          * Pipeline flush
1168          *
1169          */
1170         /* Pipeline feed */
1171         bucket20 = bucket10;
1172         bucket21 = bucket11;
1173         mbuf20 = mbuf10;
1174         mbuf21 = mbuf11;
1175         mbuf10 = mbuf00;
1176         mbuf11 = mbuf01;
1177         pkt20_index = pkt10_index;
1178         pkt21_index = pkt11_index;
1179         pkt10_index = pkt00_index;
1180         pkt11_index = pkt01_index;
1181
1182         /* Pipeline stage 1 */
1183         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1184
1185         /* Pipeline stage 2 */
1186         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1187                 bucket20, bucket21, pkts_mask_out, entries,
1188                 buckets_mask, buckets, keys, f);
1189
1190         /* Pipeline feed */
1191         bucket20 = bucket10;
1192         bucket21 = bucket11;
1193         mbuf20 = mbuf10;
1194         mbuf21 = mbuf11;
1195         pkt20_index = pkt10_index;
1196         pkt21_index = pkt11_index;
1197
1198         /* Pipeline stage 2 */
1199         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1200                 bucket20, bucket21, pkts_mask_out, entries,
1201                 buckets_mask, buckets, keys, f);
1202
1203 grind_next_buckets:
1204         /* Grind next buckets */
1205         for ( ; buckets_mask; ) {
1206                 uint64_t buckets_mask_next = 0;
1207
1208                 for ( ; buckets_mask; ) {
1209                         uint64_t pkt_mask;
1210                         uint32_t pkt_index;
1211
1212                         pkt_index = __builtin_ctzll(buckets_mask);
1213                         pkt_mask = 1LLU << pkt_index;
1214                         buckets_mask &= ~pkt_mask;
1215
1216                         lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1217                                 entries, buckets_mask_next, f);
1218                 }
1219
1220                 buckets_mask = buckets_mask_next;
1221         }
1222
1223         *lookup_hit_mask = pkts_mask_out;
1224         RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1225         return 0;
1226 } /* rte_table_hash_lookup_key8_ext() */
1227
1228 static int
1229 rte_table_hash_lookup_key8_ext_dosig(
1230         void *table,
1231         struct rte_mbuf **pkts,
1232         uint64_t pkts_mask,
1233         uint64_t *lookup_hit_mask,
1234         void **entries)
1235 {
1236         struct rte_table_hash *f = (struct rte_table_hash *) table;
1237         struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
1238         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
1239         uint32_t pkt00_index, pkt01_index, pkt10_index;
1240         uint32_t pkt11_index, pkt20_index, pkt21_index;
1241         uint64_t pkts_mask_out = 0, buckets_mask = 0;
1242         struct rte_bucket_4_8 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
1243         uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
1244
1245         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
1246         RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
1247
1248         /* Cannot run the pipeline with less than 5 packets */
1249         if (__builtin_popcountll(pkts_mask) < 5) {
1250                 for ( ; pkts_mask; ) {
1251                         struct rte_bucket_4_8 *bucket;
1252                         struct rte_mbuf *mbuf;
1253                         uint32_t pkt_index;
1254
1255                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
1256                         lookup1_stage1_dosig(mbuf, bucket, f);
1257                         lookup1_stage2_ext(pkt_index, mbuf, bucket,
1258                                 pkts_mask_out, entries, buckets_mask,
1259                                 buckets, keys, f);
1260                 }
1261
1262                 goto grind_next_buckets;
1263         }
1264
1265         /*
1266          * Pipeline fill
1267          *
1268          */
1269         /* Pipeline stage 0 */
1270         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1271                 pkts_mask);
1272
1273         /* Pipeline feed */
1274         mbuf10 = mbuf00;
1275         mbuf11 = mbuf01;
1276         pkt10_index = pkt00_index;
1277         pkt11_index = pkt01_index;
1278
1279         /* Pipeline stage 0 */
1280         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1281                 pkts_mask);
1282
1283         /* Pipeline stage 1 */
1284         lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1285
1286         /*
1287          * Pipeline run
1288          *
1289          */
1290         for ( ; pkts_mask; ) {
1291                 /* Pipeline feed */
1292                 bucket20 = bucket10;
1293                 bucket21 = bucket11;
1294                 mbuf20 = mbuf10;
1295                 mbuf21 = mbuf11;
1296                 mbuf10 = mbuf00;
1297                 mbuf11 = mbuf01;
1298                 pkt20_index = pkt10_index;
1299                 pkt21_index = pkt11_index;
1300                 pkt10_index = pkt00_index;
1301                 pkt11_index = pkt01_index;
1302
1303                 /* Pipeline stage 0 */
1304                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1305                         mbuf00, mbuf01, pkts, pkts_mask);
1306
1307                 /* Pipeline stage 1 */
1308                 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1309
1310                 /* Pipeline stage 2 */
1311                 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1312                         bucket20, bucket21, pkts_mask_out, entries,
1313                         buckets_mask, buckets, keys, f);
1314         }
1315
1316         /*
1317          * Pipeline flush
1318          *
1319          */
1320         /* Pipeline feed */
1321         bucket20 = bucket10;
1322         bucket21 = bucket11;
1323         mbuf20 = mbuf10;
1324         mbuf21 = mbuf11;
1325         mbuf10 = mbuf00;
1326         mbuf11 = mbuf01;
1327         pkt20_index = pkt10_index;
1328         pkt21_index = pkt11_index;
1329         pkt10_index = pkt00_index;
1330         pkt11_index = pkt01_index;
1331
1332         /* Pipeline stage 1 */
1333         lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1334
1335         /* Pipeline stage 2 */
1336         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1337                 bucket20, bucket21, pkts_mask_out, entries,
1338                 buckets_mask, buckets, keys, f);
1339
1340         /* Pipeline feed */
1341         bucket20 = bucket10;
1342         bucket21 = bucket11;
1343         mbuf20 = mbuf10;
1344         mbuf21 = mbuf11;
1345         pkt20_index = pkt10_index;
1346         pkt21_index = pkt11_index;
1347
1348         /* Pipeline stage 2 */
1349         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1350                 bucket20, bucket21, pkts_mask_out, entries,
1351                 buckets_mask, buckets, keys, f);
1352
1353 grind_next_buckets:
1354         /* Grind next buckets */
1355         for ( ; buckets_mask; ) {
1356                 uint64_t buckets_mask_next = 0;
1357
1358                 for ( ; buckets_mask; ) {
1359                         uint64_t pkt_mask;
1360                         uint32_t pkt_index;
1361
1362                         pkt_index = __builtin_ctzll(buckets_mask);
1363                         pkt_mask = 1LLU << pkt_index;
1364                         buckets_mask &= ~pkt_mask;
1365
1366                         lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1367                                 entries, buckets_mask_next, f);
1368                 }
1369
1370                 buckets_mask = buckets_mask_next;
1371         }
1372
1373         *lookup_hit_mask = pkts_mask_out;
1374         RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1375         return 0;
1376 } /* rte_table_hash_lookup_key8_dosig_ext() */
1377
1378 static int
1379 rte_table_hash_key8_stats_read(void *table, struct rte_table_stats *stats, int clear)
1380 {
1381         struct rte_table_hash *t = (struct rte_table_hash *) table;
1382
1383         if (stats != NULL)
1384                 memcpy(stats, &t->stats, sizeof(t->stats));
1385
1386         if (clear)
1387                 memset(&t->stats, 0, sizeof(t->stats));
1388
1389         return 0;
1390 }
1391
1392 struct rte_table_ops rte_table_hash_key8_lru_ops = {
1393         .f_create = rte_table_hash_create_key8_lru,
1394         .f_free = rte_table_hash_free_key8_lru,
1395         .f_add = rte_table_hash_entry_add_key8_lru,
1396         .f_delete = rte_table_hash_entry_delete_key8_lru,
1397         .f_lookup = rte_table_hash_lookup_key8_lru,
1398         .f_stats = rte_table_hash_key8_stats_read,
1399 };
1400
1401 struct rte_table_ops rte_table_hash_key8_lru_dosig_ops = {
1402         .f_create = rte_table_hash_create_key8_lru,
1403         .f_free = rte_table_hash_free_key8_lru,
1404         .f_add = rte_table_hash_entry_add_key8_lru,
1405         .f_delete = rte_table_hash_entry_delete_key8_lru,
1406         .f_lookup = rte_table_hash_lookup_key8_lru_dosig,
1407         .f_stats = rte_table_hash_key8_stats_read,
1408 };
1409
1410 struct rte_table_ops rte_table_hash_key8_ext_ops = {
1411         .f_create = rte_table_hash_create_key8_ext,
1412         .f_free = rte_table_hash_free_key8_ext,
1413         .f_add = rte_table_hash_entry_add_key8_ext,
1414         .f_delete = rte_table_hash_entry_delete_key8_ext,
1415         .f_lookup = rte_table_hash_lookup_key8_ext,
1416         .f_stats = rte_table_hash_key8_stats_read,
1417 };
1418
1419 struct rte_table_ops rte_table_hash_key8_ext_dosig_ops = {
1420         .f_create = rte_table_hash_create_key8_ext,
1421         .f_free = rte_table_hash_free_key8_ext,
1422         .f_add = rte_table_hash_entry_add_key8_ext,
1423         .f_delete = rte_table_hash_entry_delete_key8_ext,
1424         .f_lookup = rte_table_hash_lookup_key8_ext_dosig,
1425         .f_stats = rte_table_hash_key8_stats_read,
1426 };