lib/librte_table/rte_table_hash_key8.c

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