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