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