lib/librte_table/rte_table_hash_lru.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
  34 #include <string.h>
  35 #include <stdio.h>
  36
  37 #include <rte_common.h>
  38 #include <rte_mbuf.h>
  39 #include <rte_memory.h>
  40 #include <rte_malloc.h>
  41 #include <rte_log.h>
  42
  43 #include "rte_table_hash.h"
  44 #include "rte_lru.h"
  45
  46 #define KEYS_PER_BUCKET 4
  47
  48 #ifdef RTE_TABLE_STATS_COLLECT
  49
  50 #define RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(table, val) \
  51         table->stats.n_pkts_in += val
  52 #define RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(table, val) \
  53         table->stats.n_pkts_lookup_miss += val
  54
  55 #else
  56
  57 #define RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(table, val)
  58 #define RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(table, val)
  59
  60 #endif
  61
  62 struct bucket {
  63         union {
  64                 struct bucket *next;
  65                 uint64_t lru_list;
  66         };
  67         uint16_t sig[KEYS_PER_BUCKET];
  68         uint32_t key_pos[KEYS_PER_BUCKET];
  69 };
  70
  71 struct grinder {
  72         struct bucket *bkt;
  73         uint64_t sig;
  74         uint64_t match;
  75         uint64_t match_pos;
  76         uint32_t key_index;
  77 };
  78
  79 struct rte_table_hash {
  80         struct rte_table_stats stats;
  81
  82         /* Input parameters */
  83         uint32_t key_size;
  84         uint32_t entry_size;
  85         uint32_t n_keys;
  86         uint32_t n_buckets;
  87         rte_table_hash_op_hash f_hash;
  88         uint64_t seed;
  89         uint32_t signature_offset;
  90         uint32_t key_offset;
  91
  92         /* Internal */
  93         uint64_t bucket_mask;
  94         uint32_t key_size_shl;
  95         uint32_t data_size_shl;
  96         uint32_t key_stack_tos;
  97
  98         /* Grinder */
  99         struct grinder grinders[RTE_PORT_IN_BURST_SIZE_MAX];
 100
 101         /* Tables */
 102         struct bucket *buckets;
 103         uint8_t *key_mem;
 104         uint8_t *data_mem;
 105         uint32_t *key_stack;
 106
 107         /* Table memory */
 108         uint8_t memory[0] __rte_cache_aligned;
 109 };
 110
 111 static int
 112 check_params_create(struct rte_table_hash_lru_params *params)
 113 {
 114         uint32_t n_buckets_min;
 115
 116         /* key_size */
 117         if ((params->key_size == 0) ||
 118                 (!rte_is_power_of_2(params->key_size))) {
 119                 RTE_LOG(ERR, TABLE, "%s: key_size invalid value\n", __func__);
 120                 return -EINVAL;
 121         }
 122
 123         /* n_keys */
 124         if ((params->n_keys == 0) ||
 125                 (!rte_is_power_of_2(params->n_keys))) {
 126                 RTE_LOG(ERR, TABLE, "%s: n_keys invalid value\n", __func__);
 127                 return -EINVAL;
 128         }
 129
 130         /* n_buckets */
 131         n_buckets_min = (params->n_keys + KEYS_PER_BUCKET - 1) / params->n_keys;
 132         if ((params->n_buckets == 0) ||
 133                 (!rte_is_power_of_2(params->n_keys)) ||
 134                 (params->n_buckets < n_buckets_min)) {
 135                 RTE_LOG(ERR, TABLE, "%s: n_buckets invalid value\n", __func__);
 136                 return -EINVAL;
 137         }
 138
 139         /* f_hash */
 140         if (params->f_hash == NULL) {
 141                 RTE_LOG(ERR, TABLE, "%s: f_hash invalid value\n", __func__);
 142                 return -EINVAL;
 143         }
 144
 145         return 0;
 146 }
 147
 148 static void *
 149 rte_table_hash_lru_create(void *params, int socket_id, uint32_t entry_size)
 150 {
 151         struct rte_table_hash_lru_params *p =
 152                 params;
 153         struct rte_table_hash *t;
 154         uint32_t total_size, table_meta_sz;
 155         uint32_t bucket_sz, key_sz, key_stack_sz, data_sz;
 156         uint32_t bucket_offset, key_offset, key_stack_offset, data_offset;
 157         uint32_t i;
 158
 159         /* Check input parameters */
 160         if ((check_params_create(p) != 0) ||
 161                 (!rte_is_power_of_2(entry_size)) ||
 162                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
 163                 (sizeof(struct bucket) != (RTE_CACHE_LINE_SIZE / 2))) {
 164                 return NULL;
 165         }
 166
 167         /* Memory allocation */
 168         table_meta_sz = RTE_CACHE_LINE_ROUNDUP(sizeof(struct rte_table_hash));
 169         bucket_sz = RTE_CACHE_LINE_ROUNDUP(p->n_buckets * sizeof(struct bucket));
 170         key_sz = RTE_CACHE_LINE_ROUNDUP(p->n_keys * p->key_size);
 171         key_stack_sz = RTE_CACHE_LINE_ROUNDUP(p->n_keys * sizeof(uint32_t));
 172         data_sz = RTE_CACHE_LINE_ROUNDUP(p->n_keys * entry_size);
 173         total_size = table_meta_sz + bucket_sz + key_sz + key_stack_sz +
 174                 data_sz;
 175
 176         t = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
 177         if (t == NULL) {
 178                 RTE_LOG(ERR, TABLE,
 179                         "%s: Cannot allocate %u bytes for hash table\n",
 180                         __func__, total_size);
 181                 return NULL;
 182         }
 183         RTE_LOG(INFO, TABLE, "%s (%u-byte key): Hash table memory footprint is "
 184                 "%u bytes\n", __func__, p->key_size, total_size);
 185
 186         /* Memory initialization */
 187         t->key_size = p->key_size;
 188         t->entry_size = entry_size;
 189         t->n_keys = p->n_keys;
 190         t->n_buckets = p->n_buckets;
 191         t->f_hash = p->f_hash;
 192         t->seed = p->seed;
 193         t->signature_offset = p->signature_offset;
 194         t->key_offset = p->key_offset;
 195
 196         /* Internal */
 197         t->bucket_mask = t->n_buckets - 1;
 198         t->key_size_shl = __builtin_ctzl(p->key_size);
 199         t->data_size_shl = __builtin_ctzl(entry_size);
 200
 201         /* Tables */
 202         bucket_offset = 0;
 203         key_offset = bucket_offset + bucket_sz;
 204         key_stack_offset = key_offset + key_sz;
 205         data_offset = key_stack_offset + key_stack_sz;
 206
 207         t->buckets = (struct bucket *) &t->memory[bucket_offset];
 208         t->key_mem = &t->memory[key_offset];
 209         t->key_stack = (uint32_t *) &t->memory[key_stack_offset];
 210         t->data_mem = &t->memory[data_offset];
 211
 212         /* Key stack */
 213         for (i = 0; i < t->n_keys; i++)
 214                 t->key_stack[i] = t->n_keys - 1 - i;
 215         t->key_stack_tos = t->n_keys;
 216
 217         /* LRU */
 218         for (i = 0; i < t->n_buckets; i++) {
 219                 struct bucket *bkt = &t->buckets[i];
 220
 221                 lru_init(bkt);
 222         }
 223
 224         return t;
 225 }
 226
 227 static int
 228 rte_table_hash_lru_free(void *table)
 229 {
 230         struct rte_table_hash *t = table;
 231
 232         /* Check input parameters */
 233         if (t == NULL)
 234                 return -EINVAL;
 235
 236         rte_free(t);
 237         return 0;
 238 }
 239
 240 static int
 241 rte_table_hash_lru_entry_add(void *table, void *key, void *entry,
 242         int *key_found, void **entry_ptr)
 243 {
 244         struct rte_table_hash *t = table;
 245         struct bucket *bkt;
 246         uint64_t sig;
 247         uint32_t bkt_index, i;
 248
 249         sig = t->f_hash(key, t->key_size, t->seed);
 250         bkt_index = sig & t->bucket_mask;
 251         bkt = &t->buckets[bkt_index];
 252         sig = (sig >> 16) | 1LLU;
 253
 254         /* Key is present in the bucket */
 255         for (i = 0; i < KEYS_PER_BUCKET; i++) {
 256                 uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 257                 uint32_t bkt_key_index = bkt->key_pos[i];
 258                 uint8_t *bkt_key = &t->key_mem[bkt_key_index <<
 259                         t->key_size_shl];
 260
 261                 if ((sig == bkt_sig) && (memcmp(key, bkt_key, t->key_size)
 262                         == 0)) {
 263                         uint8_t *data = &t->data_mem[bkt_key_index <<
 264                                 t->data_size_shl];
 265
 266                         memcpy(data, entry, t->entry_size);
 267                         lru_update(bkt, i);
 268                         *key_found = 1;
 269                         *entry_ptr = (void *) data;
 270                         return 0;
 271                 }
 272         }
 273
 274         /* Key is not present in the bucket */
 275         for (i = 0; i < KEYS_PER_BUCKET; i++) {
 276                 uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 277
 278                 if (bkt_sig == 0) {
 279                         uint32_t bkt_key_index;
 280                         uint8_t *bkt_key, *data;
 281
 282                         /* Allocate new key */
 283                         if (t->key_stack_tos == 0) {
 284                                 /* No keys available */
 285                                 return -ENOSPC;
 286                         }
 287                         bkt_key_index = t->key_stack[--t->key_stack_tos];
 288
 289                         /* Install new key */
 290                         bkt_key = &t->key_mem[bkt_key_index << t->key_size_shl];
 291                         data = &t->data_mem[bkt_key_index << t->data_size_shl];
 292
 293                         bkt->sig[i] = (uint16_t) sig;
 294                         bkt->key_pos[i] = bkt_key_index;
 295                         memcpy(bkt_key, key, t->key_size);
 296                         memcpy(data, entry, t->entry_size);
 297                         lru_update(bkt, i);
 298
 299                         *key_found = 0;
 300                         *entry_ptr = (void *) data;
 301                         return 0;
 302                 }
 303         }
 304
 305         /* Bucket full */
 306         {
 307                 uint64_t pos = lru_pos(bkt);
 308                 uint32_t bkt_key_index = bkt->key_pos[pos];
 309                 uint8_t *bkt_key = &t->key_mem[bkt_key_index <<
 310                         t->key_size_shl];
 311                 uint8_t *data = &t->data_mem[bkt_key_index << t->data_size_shl];
 312
 313                 bkt->sig[pos] = (uint16_t) sig;
 314                 memcpy(bkt_key, key, t->key_size);
 315                 memcpy(data, entry, t->entry_size);
 316                 lru_update(bkt, pos);
 317
 318                 *key_found = 0;
 319                 *entry_ptr = (void *) data;
 320                 return 0;
 321         }
 322 }
 323
 324 static int
 325 rte_table_hash_lru_entry_delete(void *table, void *key, int *key_found,
 326         void *entry)
 327 {
 328         struct rte_table_hash *t = table;
 329         struct bucket *bkt;
 330         uint64_t sig;
 331         uint32_t bkt_index, i;
 332
 333         sig = t->f_hash(key, t->key_size, t->seed);
 334         bkt_index = sig & t->bucket_mask;
 335         bkt = &t->buckets[bkt_index];
 336         sig = (sig >> 16) | 1LLU;
 337
 338         /* Key is present in the bucket */
 339         for (i = 0; i < KEYS_PER_BUCKET; i++) {
 340                 uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 341                 uint32_t bkt_key_index = bkt->key_pos[i];
 342                 uint8_t *bkt_key = &t->key_mem[bkt_key_index <<
 343                         t->key_size_shl];
 344
 345                 if ((sig == bkt_sig) &&
 346                         (memcmp(key, bkt_key, t->key_size) == 0)) {
 347                         uint8_t *data = &t->data_mem[bkt_key_index <<
 348                                 t->data_size_shl];
 349
 350                         bkt->sig[i] = 0;
 351                         t->key_stack[t->key_stack_tos++] = bkt_key_index;
 352                         *key_found = 1;
 353                         memcpy(entry, data, t->entry_size);
 354                         return 0;
 355                 }
 356         }
 357
 358         /* Key is not present in the bucket */
 359         *key_found = 0;
 360         return 0;
 361 }
 362
 363 static int rte_table_hash_lru_lookup_unoptimized(
 364         void *table,
 365         struct rte_mbuf **pkts,
 366         uint64_t pkts_mask,
 367         uint64_t *lookup_hit_mask,
 368         void **entries,
 369         int dosig)
 370 {
 371         struct rte_table_hash *t = (struct rte_table_hash *) table;
 372         uint64_t pkts_mask_out = 0;
 373
 374         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 375         RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(t, n_pkts_in);
 376
 377         for ( ; pkts_mask; ) {
 378                 struct bucket *bkt;
 379                 struct rte_mbuf *pkt;
 380                 uint8_t *key;
 381                 uint64_t pkt_mask, sig;
 382                 uint32_t pkt_index, bkt_index, i;
 383
 384                 pkt_index = __builtin_ctzll(pkts_mask);
 385                 pkt_mask = 1LLU << pkt_index;
 386                 pkts_mask &= ~pkt_mask;
 387
 388                 pkt = pkts[pkt_index];
 389                 key = RTE_MBUF_METADATA_UINT8_PTR(pkt, t->key_offset);
 390                 if (dosig)
 391                         sig = (uint64_t) t->f_hash(key, t->key_size, t->seed);
 392                 else
 393                         sig = RTE_MBUF_METADATA_UINT32(pkt,
 394                                 t->signature_offset);
 395
 396                 bkt_index = sig & t->bucket_mask;
 397                 bkt = &t->buckets[bkt_index];
 398                 sig = (sig >> 16) | 1LLU;
 399
 400                 /* Key is present in the bucket */
 401                 for (i = 0; i < KEYS_PER_BUCKET; i++) {
 402                         uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 403                         uint32_t bkt_key_index = bkt->key_pos[i];
 404                         uint8_t *bkt_key = &t->key_mem[bkt_key_index <<
 405                                 t->key_size_shl];
 406
 407                         if ((sig == bkt_sig) && (memcmp(key, bkt_key,
 408                                 t->key_size) == 0)) {
 409                                 uint8_t *data = &t->data_mem[bkt_key_index <<
 410                                         t->data_size_shl];
 411
 412                                 lru_update(bkt, i);
 413                                 pkts_mask_out |= pkt_mask;
 414                                 entries[pkt_index] = (void *) data;
 415                                 break;
 416                         }
 417                 }
 418         }
 419
 420         *lookup_hit_mask = pkts_mask_out;
 421         RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(t, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 422         return 0;
 423 }
 424
 425 /***
 426 *
 427 * mask = match bitmask
 428 * match = at least one match
 429 * match_many = more than one match
 430 * match_pos = position of first match
 431 *
 432 * ----------------------------------------
 433 * mask           match   match_many       match_pos
 434 * ----------------------------------------
 435 * 0000           0               0                        00
 436 * 0001           1               0                        00
 437 * 0010           1               0                        01
 438 * 0011           1               1                        00
 439 * ----------------------------------------
 440 * 0100           1               0                        10
 441 * 0101           1               1                        00
 442 * 0110           1               1                        01
 443 * 0111           1               1                        00
 444 * ----------------------------------------
 445 * 1000           1               0                        11
 446 * 1001           1               1                        00
 447 * 1010           1               1                        01
 448 * 1011           1               1                        00
 449 * ----------------------------------------
 450 * 1100           1               1                        10
 451 * 1101           1               1                        00
 452 * 1110           1               1                        01
 453 * 1111           1               1                        00
 454 * ----------------------------------------
 455 *
 456 * match = 1111_1111_1111_1110
 457 * match_many = 1111_1110_1110_1000
 458 * match_pos = 0001_0010_0001_0011__0001_0010_0001_0000
 459 *
 460 * match = 0xFFFELLU
 461 * match_many = 0xFEE8LLU
 462 * match_pos = 0x12131210LLU
 463 *
 464 ***/
 465
 466 #define LUT_MATCH                                               0xFFFELLU
 467 #define LUT_MATCH_MANY                                          0xFEE8LLU
 468 #define LUT_MATCH_POS                                           0x12131210LLU
 469
 470 #define lookup_cmp_sig(mbuf_sig, bucket, match, match_many, match_pos)\
 471 {                                                               \
 472         uint64_t bucket_sig[4], mask[4], mask_all;              \
 473                                                                 \
 474         bucket_sig[0] = bucket->sig[0];                         \
 475         bucket_sig[1] = bucket->sig[1];                         \
 476         bucket_sig[2] = bucket->sig[2];                         \
 477         bucket_sig[3] = bucket->sig[3];                         \
 478                                                                 \
 479         bucket_sig[0] ^= mbuf_sig;                              \
 480         bucket_sig[1] ^= mbuf_sig;                              \
 481         bucket_sig[2] ^= mbuf_sig;                              \
 482         bucket_sig[3] ^= mbuf_sig;                              \
 483                                                                 \
 484         mask[0] = 0;                                            \
 485         mask[1] = 0;                                            \
 486         mask[2] = 0;                                            \
 487         mask[3] = 0;                                            \
 488                                                                 \
 489         if (bucket_sig[0] == 0)                                 \
 490                 mask[0] = 1;                                    \
 491         if (bucket_sig[1] == 0)                                 \
 492                 mask[1] = 2;                                    \
 493         if (bucket_sig[2] == 0)                                 \
 494                 mask[2] = 4;                                    \
 495         if (bucket_sig[3] == 0)                                 \
 496                 mask[3] = 8;                                    \
 497                                                                 \
 498         mask_all = (mask[0] | mask[1]) | (mask[2] | mask[3]);   \
 499                                                                 \
 500         match = (LUT_MATCH >> mask_all) & 1;                    \
 501         match_many = (LUT_MATCH_MANY >> mask_all) & 1;          \
 502         match_pos = (LUT_MATCH_POS >> (mask_all << 1)) & 3;     \
 503 }
 504
 505 #define lookup_cmp_key(mbuf, key, match_key, f)                 \
 506 {                                                               \
 507         uint64_t *pkt_key = RTE_MBUF_METADATA_UINT64_PTR(mbuf, f->key_offset);\
 508         uint64_t *bkt_key = (uint64_t *) key;                   \
 509                                                                 \
 510         switch (f->key_size) {                                  \
 511         case 8:                                                 \
 512         {                                                       \
 513                 uint64_t xor = pkt_key[0] ^ bkt_key[0];         \
 514                 match_key = 0;                                  \
 515                 if (xor == 0)                                   \
 516                         match_key = 1;                          \
 517         }                                                       \
 518         break;                                                  \
 519                                                                 \
 520         case 16:                                                \
 521         {                                                       \
 522                 uint64_t xor[2], or;                            \
 523                                                                 \
 524                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 525                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 526                 or = xor[0] | xor[1];                           \
 527                 match_key = 0;                                  \
 528                 if (or == 0)                                    \
 529                         match_key = 1;                          \
 530         }                                                       \
 531         break;                                                  \
 532                                                                 \
 533         case 32:                                                \
 534         {                                                       \
 535                 uint64_t xor[4], or;                            \
 536                                                                 \
 537                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 538                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 539                 xor[2] = pkt_key[2] ^ bkt_key[2];               \
 540                 xor[3] = pkt_key[3] ^ bkt_key[3];               \
 541                 or = xor[0] | xor[1] | xor[2] | xor[3];         \
 542                 match_key = 0;                                  \
 543                 if (or == 0)                                    \
 544                         match_key = 1;                          \
 545         }                                                       \
 546         break;                                                  \
 547                                                                 \
 548         case 64:                                                \
 549         {                                                       \
 550                 uint64_t xor[8], or;                            \
 551                                                                 \
 552                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 553                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 554                 xor[2] = pkt_key[2] ^ bkt_key[2];               \
 555                 xor[3] = pkt_key[3] ^ bkt_key[3];               \
 556                 xor[4] = pkt_key[4] ^ bkt_key[4];               \
 557                 xor[5] = pkt_key[5] ^ bkt_key[5];               \
 558                 xor[6] = pkt_key[6] ^ bkt_key[6];               \
 559                 xor[7] = pkt_key[7] ^ bkt_key[7];               \
 560                 or = xor[0] | xor[1] | xor[2] | xor[3] |        \
 561                         xor[4] | xor[5] | xor[6] | xor[7];      \
 562                 match_key = 0;                                  \
 563                 if (or == 0)                                    \
 564                         match_key = 1;                          \
 565         }                                                       \
 566         break;                                                  \
 567                                                                 \
 568         default:                                                \
 569                 match_key = 0;                                  \
 570                 if (memcmp(pkt_key, bkt_key, f->key_size) == 0) \
 571                         match_key = 1;                          \
 572         }                                                       \
 573 }
 574
 575 #define lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index)\
 576 {                                                               \
 577         uint64_t pkt00_mask, pkt01_mask;                        \
 578         struct rte_mbuf *mbuf00, *mbuf01;                       \
 579         uint32_t key_offset = t->key_offset;            \
 580                                                                 \
 581         pkt00_index = __builtin_ctzll(pkts_mask);               \
 582         pkt00_mask = 1LLU << pkt00_index;                       \
 583         pkts_mask &= ~pkt00_mask;                               \
 584         mbuf00 = pkts[pkt00_index];                             \
 585                                                                 \
 586         pkt01_index = __builtin_ctzll(pkts_mask);               \
 587         pkt01_mask = 1LLU << pkt01_index;                       \
 588         pkts_mask &= ~pkt01_mask;                               \
 589         mbuf01 = pkts[pkt01_index];                             \
 590                                                                 \
 591         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
 592         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
 593 }
 594
 595 #define lookup2_stage0_with_odd_support(t, g, pkts, pkts_mask, pkt00_index, \
 596         pkt01_index)                                            \
 597 {                                                               \
 598         uint64_t pkt00_mask, pkt01_mask;                        \
 599         struct rte_mbuf *mbuf00, *mbuf01;                       \
 600         uint32_t key_offset = t->key_offset;            \
 601                                                                 \
 602         pkt00_index = __builtin_ctzll(pkts_mask);               \
 603         pkt00_mask = 1LLU << pkt00_index;                       \
 604         pkts_mask &= ~pkt00_mask;                               \
 605         mbuf00 = pkts[pkt00_index];                             \
 606                                                                 \
 607         pkt01_index = __builtin_ctzll(pkts_mask);               \
 608         if (pkts_mask == 0)                                     \
 609                 pkt01_index = pkt00_index;                      \
 610                                                                 \
 611         pkt01_mask = 1LLU << pkt01_index;                       \
 612         pkts_mask &= ~pkt01_mask;                               \
 613         mbuf01 = pkts[pkt01_index];                             \
 614                                                                 \
 615         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
 616         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
 617 }
 618
 619 #define lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index)    \
 620 {                                                               \
 621         struct grinder *g10, *g11;                              \
 622         uint64_t sig10, sig11, bkt10_index, bkt11_index;        \
 623         struct rte_mbuf *mbuf10, *mbuf11;                       \
 624         struct bucket *bkt10, *bkt11, *buckets = t->buckets;    \
 625         uint64_t bucket_mask = t->bucket_mask;                  \
 626         uint32_t signature_offset = t->signature_offset;        \
 627                                                                 \
 628         mbuf10 = pkts[pkt10_index];                             \
 629         sig10 = (uint64_t) RTE_MBUF_METADATA_UINT32(mbuf10, signature_offset);\
 630         bkt10_index = sig10 & bucket_mask;                      \
 631         bkt10 = &buckets[bkt10_index];                          \
 632                                                                 \
 633         mbuf11 = pkts[pkt11_index];                             \
 634         sig11 = (uint64_t) RTE_MBUF_METADATA_UINT32(mbuf11, signature_offset);\
 635         bkt11_index = sig11 & bucket_mask;                      \
 636         bkt11 = &buckets[bkt11_index];                          \
 637                                                                 \
 638         rte_prefetch0(bkt10);                                   \
 639         rte_prefetch0(bkt11);                                   \
 640                                                                 \
 641         g10 = &g[pkt10_index];                                  \
 642         g10->sig = sig10;                                       \
 643         g10->bkt = bkt10;                                       \
 644                                                                 \
 645         g11 = &g[pkt11_index];                                  \
 646         g11->sig = sig11;                                       \
 647         g11->bkt = bkt11;                                       \
 648 }
 649
 650 #define lookup2_stage1_dosig(t, g, pkts, pkt10_index, pkt11_index)\
 651 {                                                               \
 652         struct grinder *g10, *g11;                              \
 653         uint64_t sig10, sig11, bkt10_index, bkt11_index;        \
 654         struct rte_mbuf *mbuf10, *mbuf11;                       \
 655         struct bucket *bkt10, *bkt11, *buckets = t->buckets;    \
 656         uint8_t *key10, *key11;                                 \
 657         uint64_t bucket_mask = t->bucket_mask;                  \
 658         rte_table_hash_op_hash f_hash = t->f_hash;              \
 659         uint64_t seed = t->seed;                                \
 660         uint32_t key_size = t->key_size;                        \
 661         uint32_t key_offset = t->key_offset;                    \
 662                                                                 \
 663         mbuf10 = pkts[pkt10_index];                             \
 664         key10 = RTE_MBUF_METADATA_UINT8_PTR(mbuf10, key_offset);\
 665         sig10 = (uint64_t) f_hash(key10, key_size, seed);       \
 666         bkt10_index = sig10 & bucket_mask;                      \
 667         bkt10 = &buckets[bkt10_index];                          \
 668                                                                 \
 669         mbuf11 = pkts[pkt11_index];                             \
 670         key11 = RTE_MBUF_METADATA_UINT8_PTR(mbuf11, key_offset);\
 671         sig11 = (uint64_t) f_hash(key11, key_size, seed);       \
 672         bkt11_index = sig11 & bucket_mask;                      \
 673         bkt11 = &buckets[bkt11_index];                          \
 674                                                                 \
 675         rte_prefetch0(bkt10);                                   \
 676         rte_prefetch0(bkt11);                                   \
 677                                                                 \
 678         g10 = &g[pkt10_index];                                  \
 679         g10->sig = sig10;                                       \
 680         g10->bkt = bkt10;                                       \
 681                                                                 \
 682         g11 = &g[pkt11_index];                                  \
 683         g11->sig = sig11;                                       \
 684         g11->bkt = bkt11;                                       \
 685 }
 686
 687 #define lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many)\
 688 {                                                               \
 689         struct grinder *g20, *g21;                              \
 690         uint64_t sig20, sig21;                                  \
 691         struct bucket *bkt20, *bkt21;                           \
 692         uint8_t *key20, *key21, *key_mem = t->key_mem;          \
 693         uint64_t match20, match21, match_many20, match_many21;  \
 694         uint64_t match_pos20, match_pos21;                      \
 695         uint32_t key20_index, key21_index, key_size_shl = t->key_size_shl;\
 696                                                                 \
 697         g20 = &g[pkt20_index];                                  \
 698         sig20 = g20->sig;                                       \
 699         bkt20 = g20->bkt;                                       \
 700         sig20 = (sig20 >> 16) | 1LLU;                           \
 701         lookup_cmp_sig(sig20, bkt20, match20, match_many20, match_pos20);\
 702         match20 <<= pkt20_index;                                \
 703         match_many20 <<= pkt20_index;                           \
 704         key20_index = bkt20->key_pos[match_pos20];              \
 705         key20 = &key_mem[key20_index << key_size_shl];          \
 706                                                                 \
 707         g21 = &g[pkt21_index];                                  \
 708         sig21 = g21->sig;                                       \
 709         bkt21 = g21->bkt;                                       \
 710         sig21 = (sig21 >> 16) | 1LLU;                           \
 711         lookup_cmp_sig(sig21, bkt21, match21, match_many21, match_pos21);\
 712         match21 <<= pkt21_index;                                \
 713         match_many21 <<= pkt21_index;                           \
 714         key21_index = bkt21->key_pos[match_pos21];              \
 715         key21 = &key_mem[key21_index << key_size_shl];          \
 716                                                                 \
 717         rte_prefetch0(key20);                                   \
 718         rte_prefetch0(key21);                                   \
 719                                                                 \
 720         pkts_mask_match_many |= match_many20 | match_many21;    \
 721                                                                 \
 722         g20->match = match20;                                   \
 723         g20->match_pos = match_pos20;                           \
 724         g20->key_index = key20_index;                           \
 725                                                                 \
 726         g21->match = match21;                                   \
 727         g21->match_pos = match_pos21;                           \
 728         g21->key_index = key21_index;                           \
 729 }
 730
 731 #define lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out, \
 732         entries)                                                \
 733 {                                                               \
 734         struct grinder *g30, *g31;                              \
 735         struct rte_mbuf *mbuf30, *mbuf31;                       \
 736         struct bucket *bkt30, *bkt31;                           \
 737         uint8_t *key30, *key31, *key_mem = t->key_mem;          \
 738         uint8_t *data30, *data31, *data_mem = t->data_mem;      \
 739         uint64_t match30, match31, match_pos30, match_pos31;    \
 740         uint64_t match_key30, match_key31, match_keys;          \
 741         uint32_t key30_index, key31_index;                      \
 742         uint32_t key_size_shl = t->key_size_shl;                \
 743         uint32_t data_size_shl = t->data_size_shl;              \
 744                                                                 \
 745         mbuf30 = pkts[pkt30_index];                             \
 746         g30 = &g[pkt30_index];                                  \
 747         bkt30 = g30->bkt;                                       \
 748         match30 = g30->match;                                   \
 749         match_pos30 = g30->match_pos;                           \
 750         key30_index = g30->key_index;                           \
 751         key30 = &key_mem[key30_index << key_size_shl];          \
 752         lookup_cmp_key(mbuf30, key30, match_key30, t);          \
 753         match_key30 <<= pkt30_index;                            \
 754         match_key30 &= match30;                                 \
 755         data30 = &data_mem[key30_index << data_size_shl];       \
 756         entries[pkt30_index] = data30;                          \
 757                                                                 \
 758         mbuf31 = pkts[pkt31_index];                             \
 759         g31 = &g[pkt31_index];                                  \
 760         bkt31 = g31->bkt;                                       \
 761         match31 = g31->match;                                   \
 762         match_pos31 = g31->match_pos;                           \
 763         key31_index = g31->key_index;                           \
 764         key31 = &key_mem[key31_index << key_size_shl];          \
 765         lookup_cmp_key(mbuf31, key31, match_key31, t);          \
 766         match_key31 <<= pkt31_index;                            \
 767         match_key31 &= match31;                                 \
 768         data31 = &data_mem[key31_index << data_size_shl];       \
 769         entries[pkt31_index] = data31;                          \
 770                                                                 \
 771         rte_prefetch0(data30);                                  \
 772         rte_prefetch0(data31);                                  \
 773                                                                 \
 774         match_keys = match_key30 | match_key31;                 \
 775         pkts_mask_out |= match_keys;                            \
 776                                                                 \
 777         if (match_key30 == 0)                                   \
 778                 match_pos30 = 4;                                \
 779         lru_update(bkt30, match_pos30);                         \
 780                                                                 \
 781         if (match_key31 == 0)                                   \
 782                 match_pos31 = 4;                                \
 783         lru_update(bkt31, match_pos31);                         \
 784 }
 785
 786 /***
 787 * The lookup function implements a 4-stage pipeline, with each stage processing
 788 * two different packets. The purpose of pipelined implementation is to hide the
 789 * latency of prefetching the data structures and loosen the data dependency
 790 * between instructions.
 791 *
 792 *   p00  _______   p10  _______   p20  _______   p30  _______
 793 * ----->|       |----->|       |----->|       |----->|       |----->
 794 *       |   0   |      |   1   |      |   2   |      |   3   |
 795 * ----->|_______|----->|_______|----->|_______|----->|_______|----->
 796 *   p01            p11            p21            p31
 797 *
 798 * The naming convention is:
 799 *         pXY = packet Y of stage X, X = 0 .. 3, Y = 0 .. 1
 800 *
 801 ***/
 802 static int rte_table_hash_lru_lookup(
 803         void *table,
 804         struct rte_mbuf **pkts,
 805         uint64_t pkts_mask,
 806         uint64_t *lookup_hit_mask,
 807         void **entries)
 808 {
 809         struct rte_table_hash *t = (struct rte_table_hash *) table;
 810         struct grinder *g = t->grinders;
 811         uint64_t pkt00_index, pkt01_index, pkt10_index, pkt11_index;
 812         uint64_t pkt20_index, pkt21_index, pkt30_index, pkt31_index;
 813         uint64_t pkts_mask_out = 0, pkts_mask_match_many = 0;
 814         int status = 0;
 815
 816         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 817         RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(t, n_pkts_in);
 818
 819         /* Cannot run the pipeline with less than 7 packets */
 820         if (__builtin_popcountll(pkts_mask) < 7)
 821                 return rte_table_hash_lru_lookup_unoptimized(table, pkts,
 822                         pkts_mask, lookup_hit_mask, entries, 0);
 823
 824         /* Pipeline stage 0 */
 825         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 826
 827         /* Pipeline feed */
 828         pkt10_index = pkt00_index;
 829         pkt11_index = pkt01_index;
 830
 831         /* Pipeline stage 0 */
 832         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 833
 834         /* Pipeline stage 1 */
 835         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 836
 837         /* Pipeline feed */
 838         pkt20_index = pkt10_index;
 839         pkt21_index = pkt11_index;
 840         pkt10_index = pkt00_index;
 841         pkt11_index = pkt01_index;
 842
 843         /* Pipeline stage 0 */
 844         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 845
 846         /* Pipeline stage 1 */
 847         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 848
 849         /* Pipeline stage 2 */
 850         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 851
 852         /*
 853         * Pipeline run
 854         *
 855         */
 856         for ( ; pkts_mask; ) {
 857                 /* Pipeline feed */
 858                 pkt30_index = pkt20_index;
 859                 pkt31_index = pkt21_index;
 860                 pkt20_index = pkt10_index;
 861                 pkt21_index = pkt11_index;
 862                 pkt10_index = pkt00_index;
 863                 pkt11_index = pkt01_index;
 864
 865                 /* Pipeline stage 0 */
 866                 lookup2_stage0_with_odd_support(t, g, pkts, pkts_mask,
 867                         pkt00_index, pkt01_index);
 868
 869                 /* Pipeline stage 1 */
 870                 lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 871
 872                 /* Pipeline stage 2 */
 873                 lookup2_stage2(t, g, pkt20_index, pkt21_index,
 874                         pkts_mask_match_many);
 875
 876                 /* Pipeline stage 3 */
 877                 lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index,
 878                         pkts_mask_out, entries);
 879         }
 880
 881         /* Pipeline feed */
 882         pkt30_index = pkt20_index;
 883         pkt31_index = pkt21_index;
 884         pkt20_index = pkt10_index;
 885         pkt21_index = pkt11_index;
 886         pkt10_index = pkt00_index;
 887         pkt11_index = pkt01_index;
 888
 889         /* Pipeline stage 1 */
 890         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 891
 892         /* Pipeline stage 2 */
 893         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 894
 895         /* Pipeline stage 3 */
 896         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 897                 entries);
 898
 899         /* Pipeline feed */
 900         pkt30_index = pkt20_index;
 901         pkt31_index = pkt21_index;
 902         pkt20_index = pkt10_index;
 903         pkt21_index = pkt11_index;
 904
 905         /* Pipeline stage 2 */
 906         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 907
 908         /* Pipeline stage 3 */
 909         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 910                 entries);
 911
 912         /* Pipeline feed */
 913         pkt30_index = pkt20_index;
 914         pkt31_index = pkt21_index;
 915
 916         /* Pipeline stage 3 */
 917         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 918                 entries);
 919
 920         /* Slow path */
 921         pkts_mask_match_many &= ~pkts_mask_out;
 922         if (pkts_mask_match_many) {
 923                 uint64_t pkts_mask_out_slow = 0;
 924
 925                 status = rte_table_hash_lru_lookup_unoptimized(table, pkts,
 926                         pkts_mask_match_many, &pkts_mask_out_slow, entries, 0);
 927                 pkts_mask_out |= pkts_mask_out_slow;
 928         }
 929
 930         *lookup_hit_mask = pkts_mask_out;
 931         RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(t, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 932         return status;
 933 }
 934
 935 static int rte_table_hash_lru_lookup_dosig(
 936         void *table,
 937         struct rte_mbuf **pkts,
 938         uint64_t pkts_mask,
 939         uint64_t *lookup_hit_mask,
 940         void **entries)
 941 {
 942         struct rte_table_hash *t = (struct rte_table_hash *) table;
 943         struct grinder *g = t->grinders;
 944         uint64_t pkt00_index, pkt01_index, pkt10_index, pkt11_index;
 945         uint64_t pkt20_index, pkt21_index, pkt30_index, pkt31_index;
 946         uint64_t pkts_mask_out = 0, pkts_mask_match_many = 0;
 947         int status = 0;
 948
 949         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 950         RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(t, n_pkts_in);
 951
 952         /* Cannot run the pipeline with less than 7 packets */
 953         if (__builtin_popcountll(pkts_mask) < 7)
 954                 return rte_table_hash_lru_lookup_unoptimized(table, pkts,
 955                         pkts_mask, lookup_hit_mask, entries, 1);
 956
 957         /* Pipeline stage 0 */
 958         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 959
 960         /* Pipeline feed */
 961         pkt10_index = pkt00_index;
 962         pkt11_index = pkt01_index;
 963
 964         /* Pipeline stage 0 */
 965         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 966
 967         /* Pipeline stage 1 */
 968         lookup2_stage1_dosig(t, g, pkts, pkt10_index, pkt11_index);
 969
 970         /* Pipeline feed */
 971         pkt20_index = pkt10_index;
 972         pkt21_index = pkt11_index;
 973         pkt10_index = pkt00_index;
 974         pkt11_index = pkt01_index;
 975
 976         /* Pipeline stage 0 */
 977         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 978
 979         /* Pipeline stage 1 */
 980         lookup2_stage1_dosig(t, g, pkts, pkt10_index, pkt11_index);
 981
 982         /* Pipeline stage 2 */
 983         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 984
 985         /*
 986         * Pipeline run
 987         *
 988         */
 989         for ( ; pkts_mask; ) {
 990                 /* Pipeline feed */
 991                 pkt30_index = pkt20_index;
 992                 pkt31_index = pkt21_index;
 993                 pkt20_index = pkt10_index;
 994                 pkt21_index = pkt11_index;
 995                 pkt10_index = pkt00_index;
 996                 pkt11_index = pkt01_index;
 997
 998                 /* Pipeline stage 0 */
 999                 lookup2_stage0_with_odd_support(t, g, pkts, pkts_mask,
1000                         pkt00_index, pkt01_index);
1001
1002                 /* Pipeline stage 1 */
1003                 lookup2_stage1_dosig(t, g, pkts, pkt10_index, pkt11_index);
1004
1005                 /* Pipeline stage 2 */
1006                 lookup2_stage2(t, g, pkt20_index, pkt21_index,
1007                         pkts_mask_match_many);
1008
1009                 /* Pipeline stage 3 */
1010                 lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index,
1011                         pkts_mask_out, entries);
1012         }
1013
1014         /* Pipeline feed */
1015         pkt30_index = pkt20_index;
1016         pkt31_index = pkt21_index;
1017         pkt20_index = pkt10_index;
1018         pkt21_index = pkt11_index;
1019         pkt10_index = pkt00_index;
1020         pkt11_index = pkt01_index;
1021
1022         /* Pipeline stage 1 */
1023         lookup2_stage1_dosig(t, g, pkts, pkt10_index, pkt11_index);
1024
1025         /* Pipeline stage 2 */
1026         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
1027
1028         /* Pipeline stage 3 */
1029         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
1030                 entries);
1031
1032         /* Pipeline feed */
1033         pkt30_index = pkt20_index;
1034         pkt31_index = pkt21_index;
1035         pkt20_index = pkt10_index;
1036         pkt21_index = pkt11_index;
1037
1038         /* Pipeline stage 2 */
1039         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
1040
1041         /* Pipeline stage 3 */
1042         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
1043                 entries);
1044
1045         /* Pipeline feed */
1046         pkt30_index = pkt20_index;
1047         pkt31_index = pkt21_index;
1048
1049         /* Pipeline stage 3 */
1050         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
1051                 entries);
1052
1053         /* Slow path */
1054         pkts_mask_match_many &= ~pkts_mask_out;
1055         if (pkts_mask_match_many) {
1056                 uint64_t pkts_mask_out_slow = 0;
1057
1058                 status = rte_table_hash_lru_lookup_unoptimized(table, pkts,
1059                         pkts_mask_match_many, &pkts_mask_out_slow, entries, 1);
1060                 pkts_mask_out |= pkts_mask_out_slow;
1061         }
1062
1063         *lookup_hit_mask = pkts_mask_out;
1064         RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(t, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1065         return status;
1066 }
1067
1068 static int
1069 rte_table_hash_lru_stats_read(void *table, struct rte_table_stats *stats, int clear)
1070 {
1071         struct rte_table_hash *t = table;
1072
1073         if (stats != NULL)
1074                 memcpy(stats, &t->stats, sizeof(t->stats));
1075
1076         if (clear)
1077                 memset(&t->stats, 0, sizeof(t->stats));
1078
1079         return 0;
1080 }
1081
1082 struct rte_table_ops rte_table_hash_lru_ops = {
1083         .f_create = rte_table_hash_lru_create,
1084         .f_free = rte_table_hash_lru_free,
1085         .f_add = rte_table_hash_lru_entry_add,
1086         .f_delete = rte_table_hash_lru_entry_delete,
1087         .f_add_bulk = NULL,
1088         .f_delete_bulk = NULL,
1089         .f_lookup = rte_table_hash_lru_lookup,
1090         .f_stats = rte_table_hash_lru_stats_read,
1091 };
1092
1093 struct rte_table_ops rte_table_hash_lru_dosig_ops = {
1094         .f_create = rte_table_hash_lru_create,
1095         .f_free = rte_table_hash_lru_free,
1096         .f_add = rte_table_hash_lru_entry_add,
1097         .f_delete = rte_table_hash_lru_entry_delete,
1098         .f_add_bulk = NULL,
1099         .f_delete_bulk = NULL,
1100         .f_lookup = rte_table_hash_lru_lookup_dosig,
1101         .f_stats = rte_table_hash_lru_stats_read,
1102 };