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[0]; 48 }; 49 50 static int 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 * 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 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 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 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 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 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