DPDK  24.11.0-rc1
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 #include <stdalign.h>
15 
16 #if defined(RTE_ARCH_X86)
17 #include "rte_cmp_x86.h"
18 #endif
19 
20 #if defined(RTE_ARCH_ARM64)
21 #include "rte_cmp_arm64.h"
22 #endif
23 
24 /* Macro to enable/disable run-time checking of function parameters */
25 #if defined(RTE_LIBRTE_HASH_DEBUG)
26 #define RETURN_IF_TRUE(cond, retval) do { \
27  if (cond) \
28  return retval; \
29 } while (0)
30 #else
31 #define RETURN_IF_TRUE(cond, retval)
32 #endif
33 
34 #include <rte_hash_crc.h>
35 #include <rte_jhash.h>
36 
37 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
38 /*
39  * All different options to select a key compare function,
40  * based on the key size and custom function.
41  */
42 enum cmp_jump_table_case {
43  KEY_CUSTOM = 0,
44  KEY_16_BYTES,
45  KEY_32_BYTES,
46  KEY_48_BYTES,
47  KEY_64_BYTES,
48  KEY_80_BYTES,
49  KEY_96_BYTES,
50  KEY_112_BYTES,
51  KEY_128_BYTES,
52  KEY_OTHER_BYTES,
53  NUM_KEY_CMP_CASES,
54 };
55 
56 /*
57  * Table storing all different key compare functions
58  * (multi-process supported)
59  */
60 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
61  NULL,
62  rte_hash_k16_cmp_eq,
63  rte_hash_k32_cmp_eq,
64  rte_hash_k48_cmp_eq,
65  rte_hash_k64_cmp_eq,
66  rte_hash_k80_cmp_eq,
67  rte_hash_k96_cmp_eq,
68  rte_hash_k112_cmp_eq,
69  rte_hash_k128_cmp_eq,
70  memcmp
71 };
72 #else
73 /*
74  * All different options to select a key compare function,
75  * based on the key size and custom function.
76  */
77 enum cmp_jump_table_case {
78  KEY_CUSTOM = 0,
79  KEY_OTHER_BYTES,
80  NUM_KEY_CMP_CASES,
81 };
82 
83 /*
84  * Table storing all different key compare functions
85  * (multi-process supported)
86  */
87 const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
88  NULL,
89  memcmp
90 };
91 
92 #endif
93 
94 
102 #define RTE_HASH_BUCKET_ENTRIES 8
103 
104 #if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES)
105 #error RTE_HASH_BUCKET_ENTRIES must be a power of 2
106 #endif
107 
108 #define NULL_SIGNATURE 0
109 
110 #define EMPTY_SLOT 0
111 
112 #define KEY_ALIGNMENT 16
113 
114 #define LCORE_CACHE_SIZE 64
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 __rte_cache_aligned lcore_cache {
123  unsigned len;
124  uint32_t objs[LCORE_CACHE_SIZE];
125 };
126 
127 /* Structure that stores key-value pair */
128 struct rte_hash_key {
129  union {
130  uintptr_t idata;
131  RTE_ATOMIC(void *) pdata;
132  };
133  /* Variable key size */
134  char key[0];
135 };
136 
139  uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES];
140 
141  RTE_ATOMIC(uint32_t) key_idx[RTE_HASH_BUCKET_ENTRIES];
142 
143  uint8_t flag[RTE_HASH_BUCKET_ENTRIES];
144 
145  void *next;
146 };
147 
150  char name[RTE_HASH_NAMESIZE];
151  uint32_t entries;
152  uint32_t num_buckets;
157  struct lcore_cache *local_free_slots;
160  /* RCU config */
163  struct rte_rcu_qsbr_dq *dq;
165  /* Fields used in lookup */
166 
167  alignas(RTE_CACHE_LINE_SIZE) uint32_t key_len;
178  uint8_t no_free_on_del;
192  enum cmp_jump_table_case cmp_jump_table_idx;
194  unsigned int sig_cmp_fn;
196  uint32_t bucket_bitmask;
198  uint32_t key_entry_size;
200  void *key_store;
205  rte_rwlock_t *readwrite_lock;
208  /* Stores index of an empty ext bkt to be recycled on calling
209  * rte_hash_del_xxx APIs. When lock free read-write concurrency is
210  * enabled, an empty ext bkt cannot be put into free list immediately
211  * (as readers might be using it still). Hence freeing of the ext bkt
212  * is piggy-backed to freeing of the key index.
213  */
214  uint32_t *ext_bkt_to_free;
215  RTE_ATOMIC(uint32_t) *tbl_chng_cnt;
217 };
218 
219 struct queue_node {
220  struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */
221  uint32_t cur_bkt_idx;
222 
223  struct queue_node *prev; /* Parent(bucket) in search path */
224  int prev_slot; /* Parent(slot) in search path */
225 };
226 
228 #define RTE_HASH_RCU_DQ_RECLAIM_MAX 16
229 
230 #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
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
#define __rte_cache_aligned
Definition: rte_common.h:602
unsigned int sig_cmp_fn
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
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