1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2017 Intel Corporation
3 */
4
5 #include <stdalign.h>
6 #include <stdio.h>
7 #include <string.h>
8
9 #include <rte_common.h>
10 #include <rte_malloc.h>
11 #include <rte_log.h>
12
13 #include "rte_table_hash_cuckoo.h"
14
15 #include "table_log.h"
16
17 #ifdef RTE_TABLE_STATS_COLLECT
18
19 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val) \
20 (table->stats.n_pkts_in += val)
21 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val) \
22 (table->stats.n_pkts_lookup_miss += val)
23
24 #else
25
26 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val)
27 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val)
28
29 #endif
30
31
32 struct rte_table_hash {
33 struct rte_table_stats stats;
34
35 /* Input parameters */
36 uint32_t key_size;
37 uint32_t entry_size;
38 uint32_t n_keys;
39 rte_hash_function f_hash;
40 uint32_t seed;
41 uint32_t key_offset;
42
43 /* cuckoo hash table object */
44 struct rte_hash *h_table;
45
46 /* Lookup table */
47 alignas(RTE_CACHE_LINE_SIZE) uint8_t memory[];
48 };
49
50 static int
check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params * params)51 check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params *params)
52 {
53 if (params == NULL) {
54 TABLE_LOG(ERR, "NULL Input Parameters.");
55 return -EINVAL;
56 }
57
58 if (params->name == NULL) {
59 TABLE_LOG(ERR, "Table name is NULL.");
60 return -EINVAL;
61 }
62
63 if (params->key_size == 0) {
64 TABLE_LOG(ERR, "Invalid key_size.");
65 return -EINVAL;
66 }
67
68 if (params->n_keys == 0) {
69 TABLE_LOG(ERR, "Invalid n_keys.");
70 return -EINVAL;
71 }
72
73 if (params->f_hash == NULL) {
74 TABLE_LOG(ERR, "f_hash is NULL.");
75 return -EINVAL;
76 }
77
78 return 0;
79 }
80
81 static void *
rte_table_hash_cuckoo_create(void * params,int socket_id,uint32_t entry_size)82 rte_table_hash_cuckoo_create(void *params,
83 int socket_id,
84 uint32_t entry_size)
85 {
86 struct rte_table_hash_cuckoo_params *p = params;
87 struct rte_hash *h_table;
88 struct rte_table_hash *t;
89 uint32_t total_size;
90
91 /* Check input parameters */
92 if (check_params_create_hash_cuckoo(params))
93 return NULL;
94
95 /* Memory allocation */
96 total_size = sizeof(struct rte_table_hash) +
97 RTE_CACHE_LINE_ROUNDUP(p->n_keys * entry_size);
98
99 t = rte_zmalloc_socket(p->name, total_size, RTE_CACHE_LINE_SIZE, socket_id);
100 if (t == NULL) {
101 TABLE_LOG(ERR,
102 "%s: Cannot allocate %u bytes for cuckoo hash table %s",
103 __func__, total_size, p->name);
104 return NULL;
105 }
106
107 /* Create cuckoo hash table */
108 struct rte_hash_parameters hash_cuckoo_params = {
109 .entries = p->n_keys,
110 .key_len = p->key_size,
111 .hash_func = p->f_hash,
112 .hash_func_init_val = p->seed,
113 .socket_id = socket_id,
114 .name = p->name
115 };
116
117 h_table = rte_hash_find_existing(p->name);
118 if (h_table == NULL) {
119 h_table = rte_hash_create(&hash_cuckoo_params);
120 if (h_table == NULL) {
121 TABLE_LOG(ERR,
122 "%s: failed to create cuckoo hash table %s",
123 __func__, p->name);
124 rte_free(t);
125 return NULL;
126 }
127 }
128
129 /* initialize the cuckoo hash parameters */
130 t->key_size = p->key_size;
131 t->entry_size = entry_size;
132 t->n_keys = p->n_keys;
133 t->f_hash = p->f_hash;
134 t->seed = p->seed;
135 t->key_offset = p->key_offset;
136 t->h_table = h_table;
137
138 TABLE_LOG(INFO,
139 "%s: Cuckoo hash table %s memory footprint is %u bytes",
140 __func__, p->name, total_size);
141 return t;
142 }
143
144 static int
rte_table_hash_cuckoo_free(void * table)145 rte_table_hash_cuckoo_free(void *table) {
146 struct rte_table_hash *t = table;
147
148 if (table == NULL)
149 return -EINVAL;
150
151 rte_hash_free(t->h_table);
152 rte_free(t);
153
154 return 0;
155 }
156
157 static int
rte_table_hash_cuckoo_entry_add(void * table,void * key,void * entry,int * key_found,void ** entry_ptr)158 rte_table_hash_cuckoo_entry_add(void *table, void *key, void *entry,
159 int *key_found, void **entry_ptr)
160 {
161 struct rte_table_hash *t = table;
162 int pos = 0;
163
164 /* Check input parameters */
165 if ((table == NULL) ||
166 (key == NULL) ||
167 (entry == NULL) ||
168 (key_found == NULL) ||
169 (entry_ptr == NULL))
170 return -EINVAL;
171
172 /* Find Existing entries */
173 pos = rte_hash_lookup(t->h_table, key);
174 if (pos >= 0) {
175 uint8_t *existing_entry;
176
177 *key_found = 1;
178 existing_entry = &t->memory[pos * t->entry_size];
179 memcpy(existing_entry, entry, t->entry_size);
180 *entry_ptr = existing_entry;
181
182 return 0;
183 }
184
185 if (pos == -ENOENT) {
186 /* Entry not found. Adding new entry */
187 uint8_t *new_entry;
188
189 pos = rte_hash_add_key(t->h_table, key);
190 if (pos < 0)
191 return pos;
192
193 new_entry = &t->memory[pos * t->entry_size];
194 memcpy(new_entry, entry, t->entry_size);
195
196 *key_found = 0;
197 *entry_ptr = new_entry;
198 return 0;
199 }
200
201 return pos;
202 }
203
204 static int
rte_table_hash_cuckoo_entry_delete(void * table,void * key,int * key_found,void * entry)205 rte_table_hash_cuckoo_entry_delete(void *table, void *key,
206 int *key_found, void *entry)
207 {
208 struct rte_table_hash *t = table;
209 int pos = 0;
210
211 /* Check input parameters */
212 if ((table == NULL) ||
213 (key == NULL) ||
214 (key_found == NULL))
215 return -EINVAL;
216
217 pos = rte_hash_del_key(t->h_table, key);
218 if (pos >= 0) {
219 *key_found = 1;
220 uint8_t *entry_ptr = &t->memory[pos * t->entry_size];
221
222 if (entry)
223 memcpy(entry, entry_ptr, t->entry_size);
224
225 memset(&t->memory[pos * t->entry_size], 0, t->entry_size);
226 return 0;
227 }
228
229 *key_found = 0;
230 return pos;
231 }
232
233 static int
rte_table_hash_cuckoo_lookup(void * table,struct rte_mbuf ** pkts,uint64_t pkts_mask,uint64_t * lookup_hit_mask,void ** entries)234 rte_table_hash_cuckoo_lookup(void *table,
235 struct rte_mbuf **pkts,
236 uint64_t pkts_mask,
237 uint64_t *lookup_hit_mask,
238 void **entries)
239 {
240 struct rte_table_hash *t = table;
241 uint64_t pkts_mask_out = 0;
242 uint32_t i;
243
244 __rte_unused uint32_t n_pkts_in = rte_popcount64(pkts_mask);
245
246 RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(t, n_pkts_in);
247
248 if ((pkts_mask & (pkts_mask + 1)) == 0) {
249 const uint8_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
250 int32_t positions[RTE_PORT_IN_BURST_SIZE_MAX], status;
251
252 /* Keys for bulk lookup */
253 for (i = 0; i < n_pkts_in; i++)
254 keys[i] = RTE_MBUF_METADATA_UINT8_PTR(pkts[i],
255 t->key_offset);
256
257 /* Bulk Lookup */
258 status = rte_hash_lookup_bulk(t->h_table,
259 (const void **) keys,
260 n_pkts_in,
261 positions);
262 if (status == 0) {
263 for (i = 0; i < n_pkts_in; i++) {
264 if (likely(positions[i] >= 0)) {
265 uint64_t pkt_mask = 1LLU << i;
266
267 entries[i] = &t->memory[positions[i]
268 * t->entry_size];
269 pkts_mask_out |= pkt_mask;
270 }
271 }
272 }
273 } else
274 for (i = 0; i < (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX
275 - rte_clz64(pkts_mask)); i++) {
276 uint64_t pkt_mask = 1LLU << i;
277
278 if (pkt_mask & pkts_mask) {
279 struct rte_mbuf *pkt = pkts[i];
280 uint8_t *key = RTE_MBUF_METADATA_UINT8_PTR(pkt,
281 t->key_offset);
282 int pos;
283
284 pos = rte_hash_lookup(t->h_table, key);
285 if (likely(pos >= 0)) {
286 entries[i] = &t->memory[pos
287 * t->entry_size];
288 pkts_mask_out |= pkt_mask;
289 }
290 }
291 }
292
293 *lookup_hit_mask = pkts_mask_out;
294 RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(t,
295 n_pkts_in - rte_popcount64(pkts_mask_out));
296
297 return 0;
298
299 }
300
301 static int
rte_table_hash_cuckoo_stats_read(void * table,struct rte_table_stats * stats,int clear)302 rte_table_hash_cuckoo_stats_read(void *table, struct rte_table_stats *stats,
303 int clear)
304 {
305 struct rte_table_hash *t = table;
306
307 if (stats != NULL)
308 memcpy(stats, &t->stats, sizeof(t->stats));
309
310 if (clear)
311 memset(&t->stats, 0, sizeof(t->stats));
312
313 return 0;
314 }
315
316 struct rte_table_ops rte_table_hash_cuckoo_ops = {
317 .f_create = rte_table_hash_cuckoo_create,
318 .f_free = rte_table_hash_cuckoo_free,
319 .f_add = rte_table_hash_cuckoo_entry_add,
320 .f_delete = rte_table_hash_cuckoo_entry_delete,
321 .f_add_bulk = NULL,
322 .f_delete_bulk = NULL,
323 .f_lookup = rte_table_hash_cuckoo_lookup,
324 .f_stats = rte_table_hash_cuckoo_stats_read,
325 };
326