DPDK  18.11.10
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 #if defined(RTE_ARCH_MIPS_64)
23 #include "rte_cmp_mips.h"
24 #endif
25 
26 #if defined(RTE_ARCH_LOONGARCH_64)
27 #include "rte_cmp_lsx.h"
28 #endif
29 
30 /* Macro to enable/disable run-time checking of function parameters */
31 #if defined(RTE_LIBRTE_HASH_DEBUG)
32 #define RETURN_IF_TRUE(cond, retval) do { \
33  if (cond) \
34  return retval; \
35 } while (0)
36 #else
37 #define RETURN_IF_TRUE(cond, retval)
38 #endif
39 
40 #if defined(RTE_LIBRTE_HASH_DEBUG)
41 #define ERR_IF_TRUE(cond, fmt, args...) do { \
42  if (cond) { \
43  RTE_LOG(ERR, HASH, fmt, ##args); \
44  return; \
45  } \
46 } while (0)
47 #else
48 #define ERR_IF_TRUE(cond, fmt, args...)
49 #endif
50 
51 #include <rte_hash_crc.h>
52 #include <rte_jhash.h>
53 
54 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) || \
55  defined(RTE_ARCH_MIPS_64) || defined(RTE_ARCH_LOONGARCH_64)
56 /*
57  * All different options to select a key compare function,
58  * based on the key size and custom function.
59  */
60 enum cmp_jump_table_case {
61  KEY_CUSTOM = 0,
62  KEY_16_BYTES,
63  KEY_32_BYTES,
64  KEY_48_BYTES,
65  KEY_64_BYTES,
66  KEY_80_BYTES,
67  KEY_96_BYTES,
68  KEY_112_BYTES,
69  KEY_128_BYTES,
70  KEY_OTHER_BYTES,
71  NUM_KEY_CMP_CASES,
72 };
73 
74 /*
75  * Table storing all different key compare functions
76  * (multi-process supported)
77  */
78 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
79  NULL,
80  rte_hash_k16_cmp_eq,
81  rte_hash_k32_cmp_eq,
82  rte_hash_k48_cmp_eq,
83  rte_hash_k64_cmp_eq,
84  rte_hash_k80_cmp_eq,
85  rte_hash_k96_cmp_eq,
86  rte_hash_k112_cmp_eq,
87  rte_hash_k128_cmp_eq,
88  memcmp
89 };
90 #else
91 /*
92  * All different options to select a key compare function,
93  * based on the key size and custom function.
94  */
95 enum cmp_jump_table_case {
96  KEY_CUSTOM = 0,
97  KEY_OTHER_BYTES,
98  NUM_KEY_CMP_CASES,
99 };
100 
101 /*
102  * Table storing all different key compare functions
103  * (multi-process supported)
104  */
105 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
106  NULL,
107  memcmp
108 };
109 
110 #endif
111 
112 
114 #define RTE_HASH_BUCKET_ENTRIES 8
115 
116 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES)
117 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2
118 #endif
119 
120 #define NULL_SIGNATURE 0
121 
122 #define EMPTY_SLOT 0
123 
124 #define KEY_ALIGNMENT 16
125 
126 #define LCORE_CACHE_SIZE 64
127 
128 #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000
129 
130 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4
131 
132 #define RTE_HASH_TSX_MAX_RETRY 10
133 
134 struct lcore_cache {
135  unsigned len;
136  void *objs[LCORE_CACHE_SIZE];
138 
139 /* Structure that stores key-value pair */
140 struct rte_hash_key {
141  union {
142  uintptr_t idata;
143  void *pdata;
144  };
145  /* Variable key size */
146  char key[0];
147 };
148 
149 /* All different signature compare functions */
150 enum rte_hash_sig_compare_function {
151  RTE_HASH_COMPARE_SCALAR = 0,
152  RTE_HASH_COMPARE_SSE,
153  RTE_HASH_COMPARE_LSX,
154  RTE_HASH_COMPARE_NUM
155 };
156 
159  uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];
160 
161  uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES];
162 
163  uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
164 
165  void *next;
167 
169 struct rte_hash {
171  uint32_t entries;
172  uint32_t num_buckets;
177  struct lcore_cache *local_free_slots;
180  /* Fields used in lookup */
181 
182  uint32_t key_len __rte_cache_aligned;
193  uint8_t no_free_on_del;
207  enum cmp_jump_table_case cmp_jump_table_idx;
209  enum rte_hash_sig_compare_function sig_cmp_fn;
211  uint32_t bucket_bitmask;
213  uint32_t key_entry_size;
215  void *key_store;
223  uint32_t *tbl_chng_cnt;
226 
227 struct queue_node {
228  struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
229  uint32_t cur_bkt_idx;
230 
231  struct queue_node *prev; /* Parent(bucket) in search path */
232  int prev_slot; /* Parent(slot) in search path */
233 };
234 
235 #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:66
uint8_t use_local_cache
void * key_store
enum rte_hash_sig_compare_function sig_cmp_fn
uint32_t * tbl_chng_cnt
uint8_t readwrite_concur_support
uint32_t entries
uint32_t key_len __rte_cache_aligned
rte_hash_function hash_func
uint32_t num_buckets
#define RTE_HASH_NAMESIZE
Definition: rte_hash.h:27
uint8_t no_free_on_del
char name[RTE_HASH_NAMESIZE]
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:70
struct lcore_cache * local_free_slots
rte_rwlock_t * readwrite_lock
uint8_t hw_trans_mem_support
#define __rte_cache_aligned
Definition: rte_memory.h:67
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
enum cmp_jump_table_case cmp_jump_table_idx