lib/librte_hash/rte_cuckoo_hash.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2016 Intel Corporation
   3  */
   4
   5 /* rte_cuckoo_hash.h
   6  * This file hold Cuckoo Hash private data structures to allows include from
   7  * platform specific files like rte_cuckoo_hash_x86.h
   8  */
   9
  10 #ifndef _RTE_CUCKOO_HASH_H_
  11 #define _RTE_CUCKOO_HASH_H_
  12
  13 #if defined(RTE_ARCH_X86)
  14 #include "rte_cmp_x86.h"
  15 #endif
  16
  17 #if defined(RTE_ARCH_ARM64)
  18 #include "rte_cmp_arm64.h"
  19 #endif
  20
  21 /* Macro to enable/disable run-time checking of function parameters */
  22 #if defined(RTE_LIBRTE_HASH_DEBUG)
  23 #define RETURN_IF_TRUE(cond, retval) do { \
  24         if (cond) \
  25                 return retval; \
  26 } while (0)
  27 #else
  28 #define RETURN_IF_TRUE(cond, retval)
  29 #endif
  30
  31 /* Hash function used if none is specified */
  32 #if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32)
  33 #include <rte_hash_crc.h>
  34 #define DEFAULT_HASH_FUNC       rte_hash_crc
  35 #else
  36 #include <rte_jhash.h>
  37 #define DEFAULT_HASH_FUNC       rte_jhash
  38 #endif
  39
  40 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
  41 /*
  42  * All different options to select a key compare function,
  43  * based on the key size and custom function.
  44  */
  45 enum cmp_jump_table_case {
  46         KEY_CUSTOM = 0,
  47         KEY_16_BYTES,
  48         KEY_32_BYTES,
  49         KEY_48_BYTES,
  50         KEY_64_BYTES,
  51         KEY_80_BYTES,
  52         KEY_96_BYTES,
  53         KEY_112_BYTES,
  54         KEY_128_BYTES,
  55         KEY_OTHER_BYTES,
  56         NUM_KEY_CMP_CASES,
  57 };
  58
  59 /*
  60  * Table storing all different key compare functions
  61  * (multi-process supported)
  62  */
  63 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
  64         NULL,
  65         rte_hash_k16_cmp_eq,
  66         rte_hash_k32_cmp_eq,
  67         rte_hash_k48_cmp_eq,
  68         rte_hash_k64_cmp_eq,
  69         rte_hash_k80_cmp_eq,
  70         rte_hash_k96_cmp_eq,
  71         rte_hash_k112_cmp_eq,
  72         rte_hash_k128_cmp_eq,
  73         memcmp
  74 };
  75 #else
  76 /*
  77  * All different options to select a key compare function,
  78  * based on the key size and custom function.
  79  */
  80 enum cmp_jump_table_case {
  81         KEY_CUSTOM = 0,
  82         KEY_OTHER_BYTES,
  83         NUM_KEY_CMP_CASES,
  84 };
  85
  86 /*
  87  * Table storing all different key compare functions
  88  * (multi-process supported)
  89  */
  90 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
  91         NULL,
  92         memcmp
  93 };
  94
  95 #endif
  96
  97 enum add_key_case {
  98         ADD_KEY_SINGLEWRITER = 0,
  99         ADD_KEY_MULTIWRITER,
 100         ADD_KEY_MULTIWRITER_TM,
 101 };
 102
 103 /** Number of items per bucket. */
 104 #define RTE_HASH_BUCKET_ENTRIES         8
 105
 106 #define NULL_SIGNATURE                  0
 107
 108 #define EMPTY_SLOT                      0
 109
 110 #define KEY_ALIGNMENT                   16
 111
 112 #define LCORE_CACHE_SIZE                64
 113
 114 #define RTE_HASH_MAX_PUSHES             100
 115
 116 #define RTE_HASH_BFS_QUEUE_MAX_LEN       1000
 117
 118 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
 119
 120 #define RTE_HASH_TSX_MAX_RETRY  10
 121
 122 struct lcore_cache {
 123         unsigned len; /**< Cache len */
 124         void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */
 125 } __rte_cache_aligned;
 126
 127 /* Structure that stores key-value pair */
 128 struct rte_hash_key {
 129         union {
 130                 uintptr_t idata;
 131                 void *pdata;
 132         };
 133         /* Variable key size */
 134         char key[0];
 135 } __attribute__((aligned(KEY_ALIGNMENT)));
 136
 137 /* All different signature compare functions */
 138 enum rte_hash_sig_compare_function {
 139         RTE_HASH_COMPARE_SCALAR = 0,
 140         RTE_HASH_COMPARE_SSE,
 141         RTE_HASH_COMPARE_AVX2,
 142         RTE_HASH_COMPARE_NUM
 143 };
 144
 145 /** Bucket structure */
 146 struct rte_hash_bucket {
 147         hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES];
 148
 149         uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
 150
 151         hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];
 152
 153         uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
 154 } __rte_cache_aligned;
 155
 156 /** A hash table structure. */
 157 struct rte_hash {
 158         char name[RTE_HASH_NAMESIZE];   /**< Name of the hash. */
 159         uint32_t entries;               /**< Total table entries. */
 160         uint32_t num_buckets;           /**< Number of buckets in table. */
 161
 162         struct rte_ring *free_slots;
 163         /**< Ring that stores all indexes of the free slots in the key table */
 164         uint8_t hw_trans_mem_support;
 165         /**< Hardware transactional memory support */
 166         struct lcore_cache *local_free_slots;
 167         /**< Local cache per lcore, storing some indexes of the free slots */
 168         enum add_key_case add_key; /**< Multi-writer hash add behavior */
 169
 170         rte_spinlock_t *multiwriter_lock; /**< Multi-writer spinlock for w/o TM */
 171
 172         /* Fields used in lookup */
 173
 174         uint32_t key_len __rte_cache_aligned;
 175         /**< Length of hash key. */
 176         rte_hash_function hash_func;    /**< Function used to calculate hash. */
 177         uint32_t hash_func_init_val;    /**< Init value used by hash_func. */
 178         rte_hash_cmp_eq_t rte_hash_custom_cmp_eq;
 179         /**< Custom function used to compare keys. */
 180         enum cmp_jump_table_case cmp_jump_table_idx;
 181         /**< Indicates which compare function to use. */
 182         enum rte_hash_sig_compare_function sig_cmp_fn;
 183         /**< Indicates which signature compare function to use. */
 184         uint32_t bucket_bitmask;
 185         /**< Bitmask for getting bucket index from hash signature. */
 186         uint32_t key_entry_size;         /**< Size of each key entry. */
 187
 188         void *key_store;                /**< Table storing all keys and data */
 189         struct rte_hash_bucket *buckets;
 190         /**< Table with buckets storing all the hash values and key indexes
 191          * to the key table.
 192          */
 193 } __rte_cache_aligned;
 194
 195 struct queue_node {
 196         struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
 197
 198         struct queue_node *prev;     /* Parent(bucket) in search path */
 199         int prev_slot;               /* Parent(slot) in search path */
 200 };
 201
 202 #endif