DPDK  22.11.0
rte_cuckoo_hash.h
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2016 Intel Corporation
3  * Copyright(c) 2018 Arm Limited
4  */
5 
6 /* rte_cuckoo_hash.h
7  * This file hold Cuckoo Hash private data structures to allows include from
8  * platform specific files like rte_cuckoo_hash_x86.h
9  */
10 
11 #ifndef _RTE_CUCKOO_HASH_H_
12 #define _RTE_CUCKOO_HASH_H_
13 
14 #if defined(RTE_ARCH_X86)
15 #include "rte_cmp_x86.h"
16 #endif
17 
18 #if defined(RTE_ARCH_ARM64)
19 #include "rte_cmp_arm64.h"
20 #endif
21 
22 /* Macro to enable/disable run-time checking of function parameters */
23 #if defined(RTE_LIBRTE_HASH_DEBUG)
24 #define RETURN_IF_TRUE(cond, retval) do { \
25  if (cond) \
26  return retval; \
27 } while (0)
28 #else
29 #define RETURN_IF_TRUE(cond, retval)
30 #endif
31 
32 #if defined(RTE_LIBRTE_HASH_DEBUG)
33 #define ERR_IF_TRUE(cond, fmt, args...) do { \
34  if (cond) { \
35  RTE_LOG(ERR, HASH, fmt, ##args); \
36  return; \
37  } \
38 } while (0)
39 #else
40 #define ERR_IF_TRUE(cond, fmt, args...)
41 #endif
42 
43 #include <rte_hash_crc.h>
44 #include <rte_jhash.h>
45 
46 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
47 /*
48  * All different options to select a key compare function,
49  * based on the key size and custom function.
50  */
51 enum cmp_jump_table_case {
52  KEY_CUSTOM = 0,
53  KEY_16_BYTES,
54  KEY_32_BYTES,
55  KEY_48_BYTES,
56  KEY_64_BYTES,
57  KEY_80_BYTES,
58  KEY_96_BYTES,
59  KEY_112_BYTES,
60  KEY_128_BYTES,
61  KEY_OTHER_BYTES,
62  NUM_KEY_CMP_CASES,
63 };
64 
65 /*
66  * Table storing all different key compare functions
67  * (multi-process supported)
68  */
69 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
70  NULL,
71  rte_hash_k16_cmp_eq,
72  rte_hash_k32_cmp_eq,
73  rte_hash_k48_cmp_eq,
74  rte_hash_k64_cmp_eq,
75  rte_hash_k80_cmp_eq,
76  rte_hash_k96_cmp_eq,
77  rte_hash_k112_cmp_eq,
78  rte_hash_k128_cmp_eq,
79  memcmp
80 };
81 #else
82 /*
83  * All different options to select a key compare function,
84  * based on the key size and custom function.
85  */
86 enum cmp_jump_table_case {
87  KEY_CUSTOM = 0,
88  KEY_OTHER_BYTES,
89  NUM_KEY_CMP_CASES,
90 };
91 
92 /*
93  * Table storing all different key compare functions
94  * (multi-process supported)
95  */
96 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
97  NULL,
98  memcmp
99 };
100 
101 #endif
102 
103 
111 #define RTE_HASH_BUCKET_ENTRIES 8
112 
113 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES)
114 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2
115 #endif
116 
117 #define NULL_SIGNATURE 0
118 
119 #define EMPTY_SLOT 0
120 
121 #define KEY_ALIGNMENT 16
122 
123 #define LCORE_CACHE_SIZE 64
124 
125 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
126 
127 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
128 
129 #define RTE_HASH_TSX_MAX_RETRY 10
130 
131 struct lcore_cache {
132  unsigned len;
133  uint32_t objs[LCORE_CACHE_SIZE];
135 
136 /* Structure that stores key-value pair */
137 struct rte_hash_key {
138  union {
139  uintptr_t idata;
140  void *pdata;
141  };
142  /* Variable key size */
143  char key[0];
144 };
145 
146 /* All different signature compare functions */
147 enum rte_hash_sig_compare_function {
148  RTE_HASH_COMPARE_SCALAR = 0,
149  RTE_HASH_COMPARE_SSE,
150  RTE_HASH_COMPARE_NEON,
151  RTE_HASH_COMPARE_NUM
152 };
153 
156  uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];
157 
158  uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
159 
160  uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
161 
162  void *next;
164 
166 struct rte_hash {
167  char name[RTE_HASH_NAMESIZE];
168  uint32_t entries;
169  uint32_t num_buckets;
174  struct lcore_cache *local_free_slots;
177  /* RCU config */
180  struct rte_rcu_qsbr_dq *dq;
182  /* Fields used in lookup */
183 
184  uint32_t key_len __rte_cache_aligned;
195  uint8_t no_free_on_del;
209  enum cmp_jump_table_case cmp_jump_table_idx;
211  enum rte_hash_sig_compare_function sig_cmp_fn;
213  uint32_t bucket_bitmask;
215  uint32_t key_entry_size;
217  void *key_store;
222  rte_rwlock_t *readwrite_lock;
225  /* Stores index of an empty ext bkt to be recycled on calling
226  * rte_hash_del_xxx APIs. When lock free read-write concurrency is
227  * enabled, an empty ext bkt cannot be put into free list immediately
228  * (as readers might be using it still). Hence freeing of the ext bkt
229  * is piggy-backed to freeing of the key index.
230  */
231  uint32_t *ext_bkt_to_free;
232  uint32_t *tbl_chng_cnt;
235 
236 struct queue_node {
237  struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
238  uint32_t cur_bkt_idx;
239 
240  struct queue_node *prev; /* Parent(bucket) in search path */
241  int prev_slot; /* Parent(slot) in search path */
242 };
243 
245 #define RTE_HASH_RCU_DQ_RECLAIM_MAX 16
246 
247 #endif
uint8_t readwrite_concur_lf_support
uint32_t(* rte_hash_function)(const void *key, uint32_t key_len, uint32_t init_val)
Definition: rte_hash.h:65
uint8_t use_local_cache
void * key_store
uint32_t * tbl_chng_cnt
uint8_t readwrite_concur_support
uint32_t entries
uint32_t key_len __rte_cache_aligned
struct rte_rcu_qsbr_dq * dq
rte_hash_function hash_func
uint32_t num_buckets
#define RTE_HASH_NAMESIZE
Definition: rte_hash.h:27
uint8_t no_free_on_del
struct rte_ring * free_slots
uint32_t key_entry_size
uint32_t bucket_bitmask
struct rte_ring * free_ext_bkts
int(* rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len)
Definition: rte_hash.h:69
struct lcore_cache * local_free_slots
rte_rwlock_t * readwrite_lock
#define __rte_cache_aligned
Definition: rte_common.h:440
uint8_t hw_trans_mem_support
struct rte_hash_rcu_config * hash_rcu_cfg
struct rte_hash_bucket * buckets_ext
rte_hash_cmp_eq_t rte_hash_custom_cmp_eq
uint8_t writer_takes_lock
uint8_t ext_table_support
uint32_t hash_func_init_val
struct rte_hash_bucket * buckets