lib/table/rte_table_hash_cuckoo.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2017 Intel Corporation
   3  */
   4 #include <string.h>
   5 #include <stdio.h>
   6
   7 #include <rte_common.h>
   8 #include <rte_malloc.h>
   9 #include <rte_log.h>
  10
  11 #include "rte_table_hash_cuckoo.h"
  12
  13 #ifdef RTE_TABLE_STATS_COLLECT
  14
  15 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val) \
  16         (table->stats.n_pkts_in += val)
  17 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val) \
  18         (table->stats.n_pkts_lookup_miss += val)
  19
  20 #else
  21
  22 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val)
  23 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val)
  24
  25 #endif
  26
  27
  28 struct rte_table_hash {
  29         struct rte_table_stats stats;
  30
  31         /* Input parameters */
  32         uint32_t key_size;
  33         uint32_t entry_size;
  34         uint32_t n_keys;
  35         rte_hash_function f_hash;
  36         uint32_t seed;
  37         uint32_t key_offset;
  38
  39         /* cuckoo hash table object */
  40         struct rte_hash *h_table;
  41
  42         /* Lookup table */
  43         uint8_t memory[0] __rte_cache_aligned;
  44 };
  45
  46 static int
  47 check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params *params)
  48 {
  49         if (params == NULL) {
  50                 RTE_LOG(ERR, TABLE, "NULL Input Parameters.\n");
  51                 return -EINVAL;
  52         }
  53
  54         if (params->name == NULL) {
  55                 RTE_LOG(ERR, TABLE, "Table name is NULL.\n");
  56                 return -EINVAL;
  57         }
  58
  59         if (params->key_size == 0) {
  60                 RTE_LOG(ERR, TABLE, "Invalid key_size.\n");
  61                 return -EINVAL;
  62         }
  63
  64         if (params->n_keys == 0) {
  65                 RTE_LOG(ERR, TABLE, "Invalid n_keys.\n");
  66                 return -EINVAL;
  67         }
  68
  69         if (params->f_hash == NULL) {
  70                 RTE_LOG(ERR, TABLE, "f_hash is NULL.\n");
  71                 return -EINVAL;
  72         }
  73
  74         return 0;
  75 }
  76
  77 static void *
  78 rte_table_hash_cuckoo_create(void *params,
  79                         int socket_id,
  80                         uint32_t entry_size)
  81 {
  82         struct rte_table_hash_cuckoo_params *p = params;
  83         struct rte_hash *h_table;
  84         struct rte_table_hash *t;
  85         uint32_t total_size;
  86
  87         /* Check input parameters */
  88         if (check_params_create_hash_cuckoo(params))
  89                 return NULL;
  90
  91         /* Memory allocation */
  92         total_size = sizeof(struct rte_table_hash) +
  93                 RTE_CACHE_LINE_ROUNDUP(p->n_keys * entry_size);
  94
  95         t = rte_zmalloc_socket(p->name, total_size, RTE_CACHE_LINE_SIZE, socket_id);
  96         if (t == NULL) {
  97                 RTE_LOG(ERR, TABLE,
  98                         "%s: Cannot allocate %u bytes for cuckoo hash table %s\n",
  99                         __func__, total_size, p->name);
 100                 return NULL;
 101         }
 102
 103         /* Create cuckoo hash table */
 104         struct rte_hash_parameters hash_cuckoo_params = {
 105                 .entries = p->n_keys,
 106                 .key_len = p->key_size,
 107                 .hash_func = p->f_hash,
 108                 .hash_func_init_val = p->seed,
 109                 .socket_id = socket_id,
 110                 .name = p->name
 111         };
 112
 113         h_table = rte_hash_find_existing(p->name);
 114         if (h_table == NULL) {
 115                 h_table = rte_hash_create(&hash_cuckoo_params);
 116                 if (h_table == NULL) {
 117                         RTE_LOG(ERR, TABLE,
 118                                 "%s: failed to create cuckoo hash table %s\n",
 119                                 __func__, p->name);
 120                         rte_free(t);
 121                         return NULL;
 122                 }
 123         }
 124
 125         /* initialize the cuckoo hash parameters */
 126         t->key_size = p->key_size;
 127         t->entry_size = entry_size;
 128         t->n_keys = p->n_keys;
 129         t->f_hash = p->f_hash;
 130         t->seed = p->seed;
 131         t->key_offset = p->key_offset;
 132         t->h_table = h_table;
 133
 134         RTE_LOG(INFO, TABLE,
 135                 "%s: Cuckoo hash table %s memory footprint is %u bytes\n",
 136                 __func__, p->name, total_size);
 137         return t;
 138 }
 139
 140 static int
 141 rte_table_hash_cuckoo_free(void *table) {
 142         struct rte_table_hash *t = table;
 143
 144         if (table == NULL)
 145                 return -EINVAL;
 146
 147         rte_hash_free(t->h_table);
 148         rte_free(t);
 149
 150         return 0;
 151 }
 152
 153 static int
 154 rte_table_hash_cuckoo_entry_add(void *table, void *key, void *entry,
 155         int *key_found, void **entry_ptr)
 156 {
 157         struct rte_table_hash *t = table;
 158         int pos = 0;
 159
 160         /* Check input parameters */
 161         if ((table == NULL) ||
 162                 (key == NULL) ||
 163                 (entry == NULL) ||
 164                 (key_found == NULL) ||
 165                 (entry_ptr == NULL))
 166                 return -EINVAL;
 167
 168         /*  Find Existing entries */
 169         pos = rte_hash_lookup(t->h_table, key);
 170         if (pos >= 0) {
 171                 uint8_t *existing_entry;
 172
 173                 *key_found = 1;
 174                 existing_entry = &t->memory[pos * t->entry_size];
 175                 memcpy(existing_entry, entry, t->entry_size);
 176                 *entry_ptr = existing_entry;
 177
 178                 return 0;
 179         }
 180
 181         if (pos == -ENOENT) {
 182                 /* Entry not found. Adding new entry */
 183                 uint8_t *new_entry;
 184
 185                 pos = rte_hash_add_key(t->h_table, key);
 186                 if (pos < 0)
 187                         return pos;
 188
 189                 new_entry = &t->memory[pos * t->entry_size];
 190                 memcpy(new_entry, entry, t->entry_size);
 191
 192                 *key_found = 0;
 193                 *entry_ptr = new_entry;
 194                 return 0;
 195         }
 196
 197         return pos;
 198 }
 199
 200 static int
 201 rte_table_hash_cuckoo_entry_delete(void *table, void *key,
 202         int *key_found, void *entry)
 203 {
 204         struct rte_table_hash *t = table;
 205         int pos = 0;
 206
 207         /* Check input parameters */
 208         if ((table == NULL) ||
 209                 (key == NULL) ||
 210                 (key_found == NULL))
 211                 return -EINVAL;
 212
 213         pos = rte_hash_del_key(t->h_table, key);
 214         if (pos >= 0) {
 215                 *key_found = 1;
 216                 uint8_t *entry_ptr = &t->memory[pos * t->entry_size];
 217
 218                 if (entry)
 219                         memcpy(entry, entry_ptr, t->entry_size);
 220
 221                 memset(&t->memory[pos * t->entry_size], 0, t->entry_size);
 222                 return 0;
 223         }
 224
 225         *key_found = 0;
 226         return pos;
 227 }
 228
 229 static int
 230 rte_table_hash_cuckoo_lookup(void *table,
 231         struct rte_mbuf **pkts,
 232         uint64_t pkts_mask,
 233         uint64_t *lookup_hit_mask,
 234         void **entries)
 235 {
 236         struct rte_table_hash *t = table;
 237         uint64_t pkts_mask_out = 0;
 238         uint32_t i;
 239
 240         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
 241
 242         RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(t, n_pkts_in);
 243
 244         if ((pkts_mask & (pkts_mask + 1)) == 0) {
 245                 const uint8_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
 246                 int32_t positions[RTE_PORT_IN_BURST_SIZE_MAX], status;
 247
 248                 /* Keys for bulk lookup */
 249                 for (i = 0; i < n_pkts_in; i++)
 250                         keys[i] = RTE_MBUF_METADATA_UINT8_PTR(pkts[i],
 251                                 t->key_offset);
 252
 253                 /* Bulk Lookup */
 254                 status = rte_hash_lookup_bulk(t->h_table,
 255                                 (const void **) keys,
 256                                 n_pkts_in,
 257                                 positions);
 258                 if (status == 0) {
 259                         for (i = 0; i < n_pkts_in; i++) {
 260                                 if (likely(positions[i] >= 0)) {
 261                                         uint64_t pkt_mask = 1LLU << i;
 262
 263                                         entries[i] = &t->memory[positions[i]
 264                                                 * t->entry_size];
 265                                         pkts_mask_out |= pkt_mask;
 266                                 }
 267                         }
 268                 }
 269         } else
 270                 for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX
 271                                         - __builtin_clzll(pkts_mask)); i++) {
 272                         uint64_t pkt_mask = 1LLU << i;
 273
 274                         if (pkt_mask & pkts_mask) {
 275                                 struct rte_mbuf *pkt = pkts[i];
 276                                 uint8_t *key = RTE_MBUF_METADATA_UINT8_PTR(pkt,
 277                                                 t->key_offset);
 278                                 int pos;
 279
 280                                 pos = rte_hash_lookup(t->h_table, key);
 281                                 if (likely(pos >= 0)) {
 282                                         entries[i] = &t->memory[pos
 283                                                 * t->entry_size];
 284                                         pkts_mask_out |= pkt_mask;
 285                                 }
 286                         }
 287                 }
 288
 289         *lookup_hit_mask = pkts_mask_out;
 290         RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(t,
 291                         n_pkts_in - __builtin_popcountll(pkts_mask_out));
 292
 293         return 0;
 294
 295 }
 296
 297 static int
 298 rte_table_hash_cuckoo_stats_read(void *table, struct rte_table_stats *stats,
 299         int clear)
 300 {
 301         struct rte_table_hash *t = table;
 302
 303         if (stats != NULL)
 304                 memcpy(stats, &t->stats, sizeof(t->stats));
 305
 306         if (clear)
 307                 memset(&t->stats, 0, sizeof(t->stats));
 308
 309         return 0;
 310 }
 311
 312 struct rte_table_ops rte_table_hash_cuckoo_ops = {
 313         .f_create = rte_table_hash_cuckoo_create,
 314         .f_free = rte_table_hash_cuckoo_free,
 315         .f_add = rte_table_hash_cuckoo_entry_add,
 316         .f_delete = rte_table_hash_cuckoo_entry_delete,
 317         .f_add_bulk = NULL,
 318         .f_delete_bulk = NULL,
 319         .f_lookup = rte_table_hash_cuckoo_lookup,
 320         .f_stats = rte_table_hash_cuckoo_stats_read,
 321 };