lib/librte_table/rte_table_hash_cuckoo.c

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