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