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_nomask 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 {
 370         struct rte_table_hash *t = (struct rte_table_hash *) table;
 371         uint64_t pkts_mask_out = 0;
 372
 373         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 374         RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(t, n_pkts_in);
 375
 376         for ( ; pkts_mask; ) {
 377                 struct bucket *bkt;
 378                 struct rte_mbuf *pkt;
 379                 uint8_t *key;
 380                 uint64_t pkt_mask, sig;
 381                 uint32_t pkt_index, bkt_index, i;
 382
 383                 pkt_index = __builtin_ctzll(pkts_mask);
 384                 pkt_mask = 1LLU << pkt_index;
 385                 pkts_mask &= ~pkt_mask;
 386
 387                 pkt = pkts[pkt_index];
 388                 key = RTE_MBUF_METADATA_UINT8_PTR(pkt, t->key_offset);
 389                 sig = (uint64_t) t->f_hash(key, t->key_size, t->seed);
 390
 391                 bkt_index = sig & t->bucket_mask;
 392                 bkt = &t->buckets[bkt_index];
 393                 sig = (sig >> 16) | 1LLU;
 394
 395                 /* Key is present in the bucket */
 396                 for (i = 0; i < KEYS_PER_BUCKET; i++) {
 397                         uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 398                         uint32_t bkt_key_index = bkt->key_pos[i];
 399                         uint8_t *bkt_key = &t->key_mem[bkt_key_index <<
 400                                 t->key_size_shl];
 401
 402                         if ((sig == bkt_sig) && (memcmp(key, bkt_key,
 403                                 t->key_size) == 0)) {
 404                                 uint8_t *data = &t->data_mem[bkt_key_index <<
 405                                         t->data_size_shl];
 406
 407                                 lru_update(bkt, i);
 408                                 pkts_mask_out |= pkt_mask;
 409                                 entries[pkt_index] = (void *) data;
 410                                 break;
 411                         }
 412                 }
 413         }
 414
 415         *lookup_hit_mask = pkts_mask_out;
 416         RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(t, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 417         return 0;
 418 }
 419
 420 /***
 421 *
 422 * mask = match bitmask
 423 * match = at least one match
 424 * match_many = more than one match
 425 * match_pos = position of first match
 426 *
 427 * ----------------------------------------
 428 * mask           match   match_many       match_pos
 429 * ----------------------------------------
 430 * 0000           0               0                        00
 431 * 0001           1               0                        00
 432 * 0010           1               0                        01
 433 * 0011           1               1                        00
 434 * ----------------------------------------
 435 * 0100           1               0                        10
 436 * 0101           1               1                        00
 437 * 0110           1               1                        01
 438 * 0111           1               1                        00
 439 * ----------------------------------------
 440 * 1000           1               0                        11
 441 * 1001           1               1                        00
 442 * 1010           1               1                        01
 443 * 1011           1               1                        00
 444 * ----------------------------------------
 445 * 1100           1               1                        10
 446 * 1101           1               1                        00
 447 * 1110           1               1                        01
 448 * 1111           1               1                        00
 449 * ----------------------------------------
 450 *
 451 * match = 1111_1111_1111_1110
 452 * match_many = 1111_1110_1110_1000
 453 * match_pos = 0001_0010_0001_0011__0001_0010_0001_0000
 454 *
 455 * match = 0xFFFELLU
 456 * match_many = 0xFEE8LLU
 457 * match_pos = 0x12131210LLU
 458 *
 459 ***/
 460
 461 #define LUT_MATCH                                               0xFFFELLU
 462 #define LUT_MATCH_MANY                                          0xFEE8LLU
 463 #define LUT_MATCH_POS                                           0x12131210LLU
 464
 465 #define lookup_cmp_sig(mbuf_sig, bucket, match, match_many, match_pos)\
 466 {                                                               \
 467         uint64_t bucket_sig[4], mask[4], mask_all;              \
 468                                                                 \
 469         bucket_sig[0] = bucket->sig[0];                         \
 470         bucket_sig[1] = bucket->sig[1];                         \
 471         bucket_sig[2] = bucket->sig[2];                         \
 472         bucket_sig[3] = bucket->sig[3];                         \
 473                                                                 \
 474         bucket_sig[0] ^= mbuf_sig;                              \
 475         bucket_sig[1] ^= mbuf_sig;                              \
 476         bucket_sig[2] ^= mbuf_sig;                              \
 477         bucket_sig[3] ^= mbuf_sig;                              \
 478                                                                 \
 479         mask[0] = 0;                                            \
 480         mask[1] = 0;                                            \
 481         mask[2] = 0;                                            \
 482         mask[3] = 0;                                            \
 483                                                                 \
 484         if (bucket_sig[0] == 0)                                 \
 485                 mask[0] = 1;                                    \
 486         if (bucket_sig[1] == 0)                                 \
 487                 mask[1] = 2;                                    \
 488         if (bucket_sig[2] == 0)                                 \
 489                 mask[2] = 4;                                    \
 490         if (bucket_sig[3] == 0)                                 \
 491                 mask[3] = 8;                                    \
 492                                                                 \
 493         mask_all = (mask[0] | mask[1]) | (mask[2] | mask[3]);   \
 494                                                                 \
 495         match = (LUT_MATCH >> mask_all) & 1;                    \
 496         match_many = (LUT_MATCH_MANY >> mask_all) & 1;          \
 497         match_pos = (LUT_MATCH_POS >> (mask_all << 1)) & 3;     \
 498 }
 499
 500 #define lookup_cmp_key(mbuf, key, match_key, f)                 \
 501 {                                                               \
 502         uint64_t *pkt_key = RTE_MBUF_METADATA_UINT64_PTR(mbuf, f->key_offset);\
 503         uint64_t *bkt_key = (uint64_t *) key;                   \
 504                                                                 \
 505         switch (f->key_size) {                                  \
 506         case 8:                                                 \
 507         {                                                       \
 508                 uint64_t xor = pkt_key[0] ^ bkt_key[0];         \
 509                 match_key = 0;                                  \
 510                 if (xor == 0)                                   \
 511                         match_key = 1;                          \
 512         }                                                       \
 513         break;                                                  \
 514                                                                 \
 515         case 16:                                                \
 516         {                                                       \
 517                 uint64_t xor[2], or;                            \
 518                                                                 \
 519                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 520                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 521                 or = xor[0] | xor[1];                           \
 522                 match_key = 0;                                  \
 523                 if (or == 0)                                    \
 524                         match_key = 1;                          \
 525         }                                                       \
 526         break;                                                  \
 527                                                                 \
 528         case 32:                                                \
 529         {                                                       \
 530                 uint64_t xor[4], or;                            \
 531                                                                 \
 532                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 533                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 534                 xor[2] = pkt_key[2] ^ bkt_key[2];               \
 535                 xor[3] = pkt_key[3] ^ bkt_key[3];               \
 536                 or = xor[0] | xor[1] | xor[2] | xor[3];         \
 537                 match_key = 0;                                  \
 538                 if (or == 0)                                    \
 539                         match_key = 1;                          \
 540         }                                                       \
 541         break;                                                  \
 542                                                                 \
 543         case 64:                                                \
 544         {                                                       \
 545                 uint64_t xor[8], or;                            \
 546                                                                 \
 547                 xor[0] = pkt_key[0] ^ bkt_key[0];               \
 548                 xor[1] = pkt_key[1] ^ bkt_key[1];               \
 549                 xor[2] = pkt_key[2] ^ bkt_key[2];               \
 550                 xor[3] = pkt_key[3] ^ bkt_key[3];               \
 551                 xor[4] = pkt_key[4] ^ bkt_key[4];               \
 552                 xor[5] = pkt_key[5] ^ bkt_key[5];               \
 553                 xor[6] = pkt_key[6] ^ bkt_key[6];               \
 554                 xor[7] = pkt_key[7] ^ bkt_key[7];               \
 555                 or = xor[0] | xor[1] | xor[2] | xor[3] |        \
 556                         xor[4] | xor[5] | xor[6] | xor[7];      \
 557                 match_key = 0;                                  \
 558                 if (or == 0)                                    \
 559                         match_key = 1;                          \
 560         }                                                       \
 561         break;                                                  \
 562                                                                 \
 563         default:                                                \
 564                 match_key = 0;                                  \
 565                 if (memcmp(pkt_key, bkt_key, f->key_size) == 0) \
 566                         match_key = 1;                          \
 567         }                                                       \
 568 }
 569
 570 #define lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index)\
 571 {                                                               \
 572         uint64_t pkt00_mask, pkt01_mask;                        \
 573         struct rte_mbuf *mbuf00, *mbuf01;                       \
 574         uint32_t key_offset = t->key_offset;            \
 575                                                                 \
 576         pkt00_index = __builtin_ctzll(pkts_mask);               \
 577         pkt00_mask = 1LLU << pkt00_index;                       \
 578         pkts_mask &= ~pkt00_mask;                               \
 579         mbuf00 = pkts[pkt00_index];                             \
 580                                                                 \
 581         pkt01_index = __builtin_ctzll(pkts_mask);               \
 582         pkt01_mask = 1LLU << pkt01_index;                       \
 583         pkts_mask &= ~pkt01_mask;                               \
 584         mbuf01 = pkts[pkt01_index];                             \
 585                                                                 \
 586         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
 587         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
 588 }
 589
 590 #define lookup2_stage0_with_odd_support(t, g, pkts, pkts_mask, pkt00_index, \
 591         pkt01_index)                                            \
 592 {                                                               \
 593         uint64_t pkt00_mask, pkt01_mask;                        \
 594         struct rte_mbuf *mbuf00, *mbuf01;                       \
 595         uint32_t key_offset = t->key_offset;            \
 596                                                                 \
 597         pkt00_index = __builtin_ctzll(pkts_mask);               \
 598         pkt00_mask = 1LLU << pkt00_index;                       \
 599         pkts_mask &= ~pkt00_mask;                               \
 600         mbuf00 = pkts[pkt00_index];                             \
 601                                                                 \
 602         pkt01_index = __builtin_ctzll(pkts_mask);               \
 603         if (pkts_mask == 0)                                     \
 604                 pkt01_index = pkt00_index;                      \
 605                                                                 \
 606         pkt01_mask = 1LLU << pkt01_index;                       \
 607         pkts_mask &= ~pkt01_mask;                               \
 608         mbuf01 = pkts[pkt01_index];                             \
 609                                                                 \
 610         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
 611         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
 612 }
 613
 614 #define lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index)\
 615 {                                                               \
 616         struct grinder *g10, *g11;                              \
 617         uint64_t sig10, sig11, bkt10_index, bkt11_index;        \
 618         struct rte_mbuf *mbuf10, *mbuf11;                       \
 619         struct bucket *bkt10, *bkt11, *buckets = t->buckets;    \
 620         uint8_t *key10, *key11;                                 \
 621         uint64_t bucket_mask = t->bucket_mask;                  \
 622         rte_table_hash_op_hash_nomask f_hash = t->f_hash;               \
 623         uint64_t seed = t->seed;                                \
 624         uint32_t key_size = t->key_size;                        \
 625         uint32_t key_offset = t->key_offset;                    \
 626                                                                 \
 627         mbuf10 = pkts[pkt10_index];                             \
 628         key10 = RTE_MBUF_METADATA_UINT8_PTR(mbuf10, key_offset);\
 629         sig10 = (uint64_t) f_hash(key10, key_size, seed);       \
 630         bkt10_index = sig10 & bucket_mask;                      \
 631         bkt10 = &buckets[bkt10_index];                          \
 632                                                                 \
 633         mbuf11 = pkts[pkt11_index];                             \
 634         key11 = RTE_MBUF_METADATA_UINT8_PTR(mbuf11, key_offset);\
 635         sig11 = (uint64_t) f_hash(key11, key_size, seed);       \
 636         bkt11_index = sig11 & bucket_mask;                      \
 637         bkt11 = &buckets[bkt11_index];                          \
 638                                                                 \
 639         rte_prefetch0(bkt10);                                   \
 640         rte_prefetch0(bkt11);                                   \
 641                                                                 \
 642         g10 = &g[pkt10_index];                                  \
 643         g10->sig = sig10;                                       \
 644         g10->bkt = bkt10;                                       \
 645                                                                 \
 646         g11 = &g[pkt11_index];                                  \
 647         g11->sig = sig11;                                       \
 648         g11->bkt = bkt11;                                       \
 649 }
 650
 651 #define lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many)\
 652 {                                                               \
 653         struct grinder *g20, *g21;                              \
 654         uint64_t sig20, sig21;                                  \
 655         struct bucket *bkt20, *bkt21;                           \
 656         uint8_t *key20, *key21, *key_mem = t->key_mem;          \
 657         uint64_t match20, match21, match_many20, match_many21;  \
 658         uint64_t match_pos20, match_pos21;                      \
 659         uint32_t key20_index, key21_index, key_size_shl = t->key_size_shl;\
 660                                                                 \
 661         g20 = &g[pkt20_index];                                  \
 662         sig20 = g20->sig;                                       \
 663         bkt20 = g20->bkt;                                       \
 664         sig20 = (sig20 >> 16) | 1LLU;                           \
 665         lookup_cmp_sig(sig20, bkt20, match20, match_many20, match_pos20);\
 666         match20 <<= pkt20_index;                                \
 667         match_many20 <<= pkt20_index;                           \
 668         key20_index = bkt20->key_pos[match_pos20];              \
 669         key20 = &key_mem[key20_index << key_size_shl];          \
 670                                                                 \
 671         g21 = &g[pkt21_index];                                  \
 672         sig21 = g21->sig;                                       \
 673         bkt21 = g21->bkt;                                       \
 674         sig21 = (sig21 >> 16) | 1LLU;                           \
 675         lookup_cmp_sig(sig21, bkt21, match21, match_many21, match_pos21);\
 676         match21 <<= pkt21_index;                                \
 677         match_many21 <<= pkt21_index;                           \
 678         key21_index = bkt21->key_pos[match_pos21];              \
 679         key21 = &key_mem[key21_index << key_size_shl];          \
 680                                                                 \
 681         rte_prefetch0(key20);                                   \
 682         rte_prefetch0(key21);                                   \
 683                                                                 \
 684         pkts_mask_match_many |= match_many20 | match_many21;    \
 685                                                                 \
 686         g20->match = match20;                                   \
 687         g20->match_pos = match_pos20;                           \
 688         g20->key_index = key20_index;                           \
 689                                                                 \
 690         g21->match = match21;                                   \
 691         g21->match_pos = match_pos21;                           \
 692         g21->key_index = key21_index;                           \
 693 }
 694
 695 #define lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out, \
 696         entries)                                                \
 697 {                                                               \
 698         struct grinder *g30, *g31;                              \
 699         struct rte_mbuf *mbuf30, *mbuf31;                       \
 700         struct bucket *bkt30, *bkt31;                           \
 701         uint8_t *key30, *key31, *key_mem = t->key_mem;          \
 702         uint8_t *data30, *data31, *data_mem = t->data_mem;      \
 703         uint64_t match30, match31, match_pos30, match_pos31;    \
 704         uint64_t match_key30, match_key31, match_keys;          \
 705         uint32_t key30_index, key31_index;                      \
 706         uint32_t key_size_shl = t->key_size_shl;                \
 707         uint32_t data_size_shl = t->data_size_shl;              \
 708                                                                 \
 709         mbuf30 = pkts[pkt30_index];                             \
 710         g30 = &g[pkt30_index];                                  \
 711         bkt30 = g30->bkt;                                       \
 712         match30 = g30->match;                                   \
 713         match_pos30 = g30->match_pos;                           \
 714         key30_index = g30->key_index;                           \
 715         key30 = &key_mem[key30_index << key_size_shl];          \
 716         lookup_cmp_key(mbuf30, key30, match_key30, t);          \
 717         match_key30 <<= pkt30_index;                            \
 718         match_key30 &= match30;                                 \
 719         data30 = &data_mem[key30_index << data_size_shl];       \
 720         entries[pkt30_index] = data30;                          \
 721                                                                 \
 722         mbuf31 = pkts[pkt31_index];                             \
 723         g31 = &g[pkt31_index];                                  \
 724         bkt31 = g31->bkt;                                       \
 725         match31 = g31->match;                                   \
 726         match_pos31 = g31->match_pos;                           \
 727         key31_index = g31->key_index;                           \
 728         key31 = &key_mem[key31_index << key_size_shl];          \
 729         lookup_cmp_key(mbuf31, key31, match_key31, t);          \
 730         match_key31 <<= pkt31_index;                            \
 731         match_key31 &= match31;                                 \
 732         data31 = &data_mem[key31_index << data_size_shl];       \
 733         entries[pkt31_index] = data31;                          \
 734                                                                 \
 735         rte_prefetch0(data30);                                  \
 736         rte_prefetch0(data31);                                  \
 737                                                                 \
 738         match_keys = match_key30 | match_key31;                 \
 739         pkts_mask_out |= match_keys;                            \
 740                                                                 \
 741         if (match_key30 == 0)                                   \
 742                 match_pos30 = 4;                                \
 743         lru_update(bkt30, match_pos30);                         \
 744                                                                 \
 745         if (match_key31 == 0)                                   \
 746                 match_pos31 = 4;                                \
 747         lru_update(bkt31, match_pos31);                         \
 748 }
 749
 750 /***
 751 * The lookup function implements a 4-stage pipeline, with each stage processing
 752 * two different packets. The purpose of pipelined implementation is to hide the
 753 * latency of prefetching the data structures and loosen the data dependency
 754 * between instructions.
 755 *
 756 *   p00  _______   p10  _______   p20  _______   p30  _______
 757 * ----->|       |----->|       |----->|       |----->|       |----->
 758 *       |   0   |      |   1   |      |   2   |      |   3   |
 759 * ----->|_______|----->|_______|----->|_______|----->|_______|----->
 760 *   p01            p11            p21            p31
 761 *
 762 * The naming convention is:
 763 *         pXY = packet Y of stage X, X = 0 .. 3, Y = 0 .. 1
 764 *
 765 ***/
 766 static int rte_table_hash_lru_lookup(
 767         void *table,
 768         struct rte_mbuf **pkts,
 769         uint64_t pkts_mask,
 770         uint64_t *lookup_hit_mask,
 771         void **entries)
 772 {
 773         struct rte_table_hash *t = (struct rte_table_hash *) table;
 774         struct grinder *g = t->grinders;
 775         uint64_t pkt00_index, pkt01_index, pkt10_index, pkt11_index;
 776         uint64_t pkt20_index, pkt21_index, pkt30_index, pkt31_index;
 777         uint64_t pkts_mask_out = 0, pkts_mask_match_many = 0;
 778         int status = 0;
 779
 780         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 781         RTE_TABLE_HASH_LRU_STATS_PKTS_IN_ADD(t, n_pkts_in);
 782
 783         /* Cannot run the pipeline with less than 7 packets */
 784         if (__builtin_popcountll(pkts_mask) < 7)
 785                 return rte_table_hash_lru_lookup_unoptimized(table, pkts,
 786                         pkts_mask, lookup_hit_mask, entries);
 787
 788         /* Pipeline stage 0 */
 789         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 790
 791         /* Pipeline feed */
 792         pkt10_index = pkt00_index;
 793         pkt11_index = pkt01_index;
 794
 795         /* Pipeline stage 0 */
 796         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 797
 798         /* Pipeline stage 1 */
 799         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 800
 801         /* Pipeline feed */
 802         pkt20_index = pkt10_index;
 803         pkt21_index = pkt11_index;
 804         pkt10_index = pkt00_index;
 805         pkt11_index = pkt01_index;
 806
 807         /* Pipeline stage 0 */
 808         lookup2_stage0(t, g, pkts, pkts_mask, pkt00_index, pkt01_index);
 809
 810         /* Pipeline stage 1 */
 811         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 812
 813         /* Pipeline stage 2 */
 814         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 815
 816         /*
 817         * Pipeline run
 818         *
 819         */
 820         for ( ; pkts_mask; ) {
 821                 /* Pipeline feed */
 822                 pkt30_index = pkt20_index;
 823                 pkt31_index = pkt21_index;
 824                 pkt20_index = pkt10_index;
 825                 pkt21_index = pkt11_index;
 826                 pkt10_index = pkt00_index;
 827                 pkt11_index = pkt01_index;
 828
 829                 /* Pipeline stage 0 */
 830                 lookup2_stage0_with_odd_support(t, g, pkts, pkts_mask,
 831                         pkt00_index, pkt01_index);
 832
 833                 /* Pipeline stage 1 */
 834                 lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 835
 836                 /* Pipeline stage 2 */
 837                 lookup2_stage2(t, g, pkt20_index, pkt21_index,
 838                         pkts_mask_match_many);
 839
 840                 /* Pipeline stage 3 */
 841                 lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index,
 842                         pkts_mask_out, entries);
 843         }
 844
 845         /* Pipeline feed */
 846         pkt30_index = pkt20_index;
 847         pkt31_index = pkt21_index;
 848         pkt20_index = pkt10_index;
 849         pkt21_index = pkt11_index;
 850         pkt10_index = pkt00_index;
 851         pkt11_index = pkt01_index;
 852
 853         /* Pipeline stage 1 */
 854         lookup2_stage1(t, g, pkts, pkt10_index, pkt11_index);
 855
 856         /* Pipeline stage 2 */
 857         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 858
 859         /* Pipeline stage 3 */
 860         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 861                 entries);
 862
 863         /* Pipeline feed */
 864         pkt30_index = pkt20_index;
 865         pkt31_index = pkt21_index;
 866         pkt20_index = pkt10_index;
 867         pkt21_index = pkt11_index;
 868
 869         /* Pipeline stage 2 */
 870         lookup2_stage2(t, g, pkt20_index, pkt21_index, pkts_mask_match_many);
 871
 872         /* Pipeline stage 3 */
 873         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 874                 entries);
 875
 876         /* Pipeline feed */
 877         pkt30_index = pkt20_index;
 878         pkt31_index = pkt21_index;
 879
 880         /* Pipeline stage 3 */
 881         lookup2_stage3(t, g, pkts, pkt30_index, pkt31_index, pkts_mask_out,
 882                 entries);
 883
 884         /* Slow path */
 885         pkts_mask_match_many &= ~pkts_mask_out;
 886         if (pkts_mask_match_many) {
 887                 uint64_t pkts_mask_out_slow = 0;
 888
 889                 status = rte_table_hash_lru_lookup_unoptimized(table, pkts,
 890                         pkts_mask_match_many, &pkts_mask_out_slow, entries);
 891                 pkts_mask_out |= pkts_mask_out_slow;
 892         }
 893
 894         *lookup_hit_mask = pkts_mask_out;
 895         RTE_TABLE_HASH_LRU_STATS_PKTS_LOOKUP_MISS(t, n_pkts_in - __builtin_popcountll(pkts_mask_out));
 896         return status;
 897 }
 898
 899 static int
 900 rte_table_hash_lru_stats_read(void *table, struct rte_table_stats *stats, int clear)
 901 {
 902         struct rte_table_hash *t = table;
 903
 904         if (stats != NULL)
 905                 memcpy(stats, &t->stats, sizeof(t->stats));
 906
 907         if (clear)
 908                 memset(&t->stats, 0, sizeof(t->stats));
 909
 910         return 0;
 911 }
 912
 913 struct rte_table_ops rte_table_hash_lru_ops = {
 914         .f_create = rte_table_hash_lru_create,
 915         .f_free = rte_table_hash_lru_free,
 916         .f_add = rte_table_hash_lru_entry_add,
 917         .f_delete = rte_table_hash_lru_entry_delete,
 918         .f_add_bulk = NULL,
 919         .f_delete_bulk = NULL,
 920         .f_lookup = rte_table_hash_lru_lookup,
 921         .f_stats = rte_table_hash_lru_stats_read,
 922 };