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