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