1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2017 Intel Corporation
7 #include <rte_common.h>
9 #include <rte_memory.h>
10 #include <rte_malloc.h>
13 #include "rte_table_hash_cuckoo.h"
15 #ifdef RTE_TABLE_STATS_COLLECT
17 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val) \
18 (table->stats.n_pkts_in += val)
19 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val) \
20 (table->stats.n_pkts_lookup_miss += val)
24 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(table, val)
25 #define RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(table, val)
30 struct rte_table_hash
{
31 struct rte_table_stats stats
;
33 /* Input parameters */
37 rte_hash_function f_hash
;
41 /* cuckoo hash table object */
42 struct rte_hash
*h_table
;
45 uint8_t memory
[0] __rte_cache_aligned
;
49 check_params_create_hash_cuckoo(struct rte_table_hash_cuckoo_params
*params
)
52 RTE_LOG(ERR
, TABLE
, "NULL Input Parameters.\n");
56 if (params
->name
== NULL
) {
57 RTE_LOG(ERR
, TABLE
, "Table name is NULL.\n");
61 if (params
->key_size
== 0) {
62 RTE_LOG(ERR
, TABLE
, "Invalid key_size.\n");
66 if (params
->n_keys
== 0) {
67 RTE_LOG(ERR
, TABLE
, "Invalid n_keys.\n");
71 if (params
->f_hash
== NULL
) {
72 RTE_LOG(ERR
, TABLE
, "f_hash is NULL.\n");
80 rte_table_hash_cuckoo_create(void *params
,
84 struct rte_table_hash_cuckoo_params
*p
= params
;
85 struct rte_hash
*h_table
;
86 struct rte_table_hash
*t
;
89 /* Check input parameters */
90 if (check_params_create_hash_cuckoo(params
))
93 /* Memory allocation */
94 total_size
= sizeof(struct rte_table_hash
) +
95 RTE_CACHE_LINE_ROUNDUP(p
->n_keys
* entry_size
);
97 t
= rte_zmalloc_socket(p
->name
, total_size
, RTE_CACHE_LINE_SIZE
, socket_id
);
100 "%s: Cannot allocate %u bytes for cuckoo hash table %s\n",
101 __func__
, total_size
, p
->name
);
105 /* Create cuckoo hash table */
106 struct rte_hash_parameters hash_cuckoo_params
= {
107 .entries
= p
->n_keys
,
108 .key_len
= p
->key_size
,
109 .hash_func
= p
->f_hash
,
110 .hash_func_init_val
= p
->seed
,
111 .socket_id
= socket_id
,
115 h_table
= rte_hash_find_existing(p
->name
);
116 if (h_table
== NULL
) {
117 h_table
= rte_hash_create(&hash_cuckoo_params
);
118 if (h_table
== NULL
) {
120 "%s: failed to create cuckoo hash table %s\n",
127 /* initialize the cuckoo hash parameters */
128 t
->key_size
= p
->key_size
;
129 t
->entry_size
= entry_size
;
130 t
->n_keys
= p
->n_keys
;
131 t
->f_hash
= p
->f_hash
;
133 t
->key_offset
= p
->key_offset
;
134 t
->h_table
= h_table
;
137 "%s: Cuckoo hash table %s memory footprint is %u bytes\n",
138 __func__
, p
->name
, total_size
);
143 rte_table_hash_cuckoo_free(void *table
) {
144 struct rte_table_hash
*t
= table
;
149 rte_hash_free(t
->h_table
);
156 rte_table_hash_cuckoo_entry_add(void *table
, void *key
, void *entry
,
157 int *key_found
, void **entry_ptr
)
159 struct rte_table_hash
*t
= table
;
162 /* Check input parameters */
163 if ((table
== NULL
) ||
166 (key_found
== NULL
) ||
170 /* Find Existing entries */
171 pos
= rte_hash_lookup(t
->h_table
, key
);
173 uint8_t *existing_entry
;
176 existing_entry
= &t
->memory
[pos
* t
->entry_size
];
177 memcpy(existing_entry
, entry
, t
->entry_size
);
178 *entry_ptr
= existing_entry
;
183 if (pos
== -ENOENT
) {
184 /* Entry not found. Adding new entry */
187 pos
= rte_hash_add_key(t
->h_table
, key
);
191 new_entry
= &t
->memory
[pos
* t
->entry_size
];
192 memcpy(new_entry
, entry
, t
->entry_size
);
195 *entry_ptr
= new_entry
;
203 rte_table_hash_cuckoo_entry_delete(void *table
, void *key
,
204 int *key_found
, void *entry
)
206 struct rte_table_hash
*t
= table
;
209 /* Check input parameters */
210 if ((table
== NULL
) ||
215 pos
= rte_hash_del_key(t
->h_table
, key
);
218 uint8_t *entry_ptr
= &t
->memory
[pos
* t
->entry_size
];
221 memcpy(entry
, entry_ptr
, t
->entry_size
);
223 memset(&t
->memory
[pos
* t
->entry_size
], 0, t
->entry_size
);
232 rte_table_hash_cuckoo_lookup(void *table
,
233 struct rte_mbuf
**pkts
,
235 uint64_t *lookup_hit_mask
,
238 struct rte_table_hash
*t
= table
;
239 uint64_t pkts_mask_out
= 0;
242 __rte_unused
uint32_t n_pkts_in
= __builtin_popcountll(pkts_mask
);
244 RTE_TABLE_HASH_CUCKOO_STATS_PKTS_IN_ADD(t
, n_pkts_in
);
246 if ((pkts_mask
& (pkts_mask
+ 1)) == 0) {
247 const uint8_t *keys
[RTE_PORT_IN_BURST_SIZE_MAX
];
248 int32_t positions
[RTE_PORT_IN_BURST_SIZE_MAX
], status
;
250 /* Keys for bulk lookup */
251 for (i
= 0; i
< n_pkts_in
; i
++)
252 keys
[i
] = RTE_MBUF_METADATA_UINT8_PTR(pkts
[i
],
256 status
= rte_hash_lookup_bulk(t
->h_table
,
257 (const void **) keys
,
261 for (i
= 0; i
< n_pkts_in
; i
++) {
262 if (likely(positions
[i
] >= 0)) {
263 uint64_t pkt_mask
= 1LLU << i
;
265 entries
[i
] = &t
->memory
[positions
[i
]
267 pkts_mask_out
|= pkt_mask
;
272 for (i
= 0; i
< (uint32_t)(RTE_PORT_IN_BURST_SIZE_MAX
273 - __builtin_clzll(pkts_mask
)); i
++) {
274 uint64_t pkt_mask
= 1LLU << i
;
276 if (pkt_mask
& pkts_mask
) {
277 struct rte_mbuf
*pkt
= pkts
[i
];
278 uint8_t *key
= RTE_MBUF_METADATA_UINT8_PTR(pkt
,
282 pos
= rte_hash_lookup(t
->h_table
, key
);
283 if (likely(pos
>= 0)) {
284 entries
[i
] = &t
->memory
[pos
286 pkts_mask_out
|= pkt_mask
;
291 *lookup_hit_mask
= pkts_mask_out
;
292 RTE_TABLE_HASH_CUCKOO_STATS_PKTS_LOOKUP_MISS(t
,
293 n_pkts_in
- __builtin_popcountll(pkts_mask_out
));
300 rte_table_hash_cuckoo_stats_read(void *table
, struct rte_table_stats
*stats
,
303 struct rte_table_hash
*t
= table
;
306 memcpy(stats
, &t
->stats
, sizeof(t
->stats
));
309 memset(&t
->stats
, 0, sizeof(t
->stats
));
314 struct rte_table_ops rte_table_hash_cuckoo_ops
= {
315 .f_create
= rte_table_hash_cuckoo_create
,
316 .f_free
= rte_table_hash_cuckoo_free
,
317 .f_add
= rte_table_hash_cuckoo_entry_add
,
318 .f_delete
= rte_table_hash_cuckoo_entry_delete
,
320 .f_delete_bulk
= NULL
,
321 .f_lookup
= rte_table_hash_cuckoo_lookup
,
322 .f_stats
= rte_table_hash_cuckoo_stats_read
,