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