1 /*- 2 * BSD LICENSE 3 * 4 * Copyright(c) 2010-2016 Intel Corporation. All rights reserved. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include <string.h> 35 #include <stdint.h> 36 #include <errno.h> 37 #include <stdio.h> 38 #include <stdarg.h> 39 #include <sys/queue.h> 40 41 #include <rte_common.h> 42 #include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */ 43 #include <rte_log.h> 44 #include <rte_memcpy.h> 45 #include <rte_prefetch.h> 46 #include <rte_branch_prediction.h> 47 #include <rte_malloc.h> 48 #include <rte_eal.h> 49 #include <rte_eal_memconfig.h> 50 #include <rte_per_lcore.h> 51 #include <rte_errno.h> 52 #include <rte_string_fns.h> 53 #include <rte_cpuflags.h> 54 #include <rte_rwlock.h> 55 #include <rte_spinlock.h> 56 #include <rte_ring.h> 57 #include <rte_compat.h> 58 #include <rte_pause.h> 59 60 #include "rte_hash.h" 61 #include "rte_cuckoo_hash.h" 62 63 #if defined(RTE_ARCH_X86) 64 #include "rte_cuckoo_hash_x86.h" 65 #endif 66 67 TAILQ_HEAD(rte_hash_list, rte_tailq_entry); 68 69 static struct rte_tailq_elem rte_hash_tailq = { 70 .name = "RTE_HASH", 71 }; 72 EAL_REGISTER_TAILQ(rte_hash_tailq) 73 74 struct rte_hash * 75 rte_hash_find_existing(const char *name) 76 { 77 struct rte_hash *h = NULL; 78 struct rte_tailq_entry *te; 79 struct rte_hash_list *hash_list; 80 81 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); 82 83 rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); 84 TAILQ_FOREACH(te, hash_list, next) { 85 h = (struct rte_hash *) te->data; 86 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0) 87 break; 88 } 89 rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); 90 91 if (te == NULL) { 92 rte_errno = ENOENT; 93 return NULL; 94 } 95 return h; 96 } 97 98 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func) 99 { 100 h->cmp_jump_table_idx = KEY_CUSTOM; 101 h->rte_hash_custom_cmp_eq = func; 102 } 103 104 static inline int 105 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h) 106 { 107 if (h->cmp_jump_table_idx == KEY_CUSTOM) 108 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len); 109 else 110 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len); 111 } 112 113 struct rte_hash * 114 rte_hash_create(const struct rte_hash_parameters *params) 115 { 116 struct rte_hash *h = NULL; 117 struct rte_tailq_entry *te = NULL; 118 struct rte_hash_list *hash_list; 119 struct rte_ring *r = NULL; 120 char hash_name[RTE_HASH_NAMESIZE]; 121 void *k = NULL; 122 void *buckets = NULL; 123 char ring_name[RTE_RING_NAMESIZE]; 124 unsigned num_key_slots; 125 unsigned hw_trans_mem_support = 0; 126 unsigned i; 127 128 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); 129 130 if (params == NULL) { 131 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n"); 132 return NULL; 133 } 134 135 /* Check for valid parameters */ 136 if ((params->entries > RTE_HASH_ENTRIES_MAX) || 137 (params->entries < RTE_HASH_BUCKET_ENTRIES) || 138 !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) || 139 (params->key_len == 0)) { 140 rte_errno = EINVAL; 141 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n"); 142 return NULL; 143 } 144 145 /* Check extra flags field to check extra options. */ 146 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT) 147 hw_trans_mem_support = 1; 148 149 /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ 150 if (hw_trans_mem_support) 151 /* 152 * Increase number of slots by total number of indices 153 * that can be stored in the lcore caches 154 * except for the first cache 155 */ 156 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) * 157 (LCORE_CACHE_SIZE - 1) + 1; 158 else 159 num_key_slots = params->entries + 1; 160 161 snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name); 162 /* Create ring (Dummy slot index is not enqueued) */ 163 r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots), 164 params->socket_id, 0); 165 if (r == NULL) { 166 RTE_LOG(ERR, HASH, "memory allocation failed\n"); 167 goto err; 168 } 169 170 snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); 171 172 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); 173 174 /* guarantee there's no existing: this is normally already checked 175 * by ring creation above */ 176 TAILQ_FOREACH(te, hash_list, next) { 177 h = (struct rte_hash *) te->data; 178 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0) 179 break; 180 } 181 h = NULL; 182 if (te != NULL) { 183 rte_errno = EEXIST; 184 te = NULL; 185 goto err_unlock; 186 } 187 188 te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); 189 if (te == NULL) { 190 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n"); 191 goto err_unlock; 192 } 193 194 h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash), 195 RTE_CACHE_LINE_SIZE, params->socket_id); 196 197 if (h == NULL) { 198 RTE_LOG(ERR, HASH, "memory allocation failed\n"); 199 goto err_unlock; 200 } 201 202 const uint32_t num_buckets = rte_align32pow2(params->entries) 203 / RTE_HASH_BUCKET_ENTRIES; 204 205 buckets = rte_zmalloc_socket(NULL, 206 num_buckets * sizeof(struct rte_hash_bucket), 207 RTE_CACHE_LINE_SIZE, params->socket_id); 208 209 if (buckets == NULL) { 210 RTE_LOG(ERR, HASH, "memory allocation failed\n"); 211 goto err_unlock; 212 } 213 214 const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len; 215 const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots; 216 217 k = rte_zmalloc_socket(NULL, key_tbl_size, 218 RTE_CACHE_LINE_SIZE, params->socket_id); 219 220 if (k == NULL) { 221 RTE_LOG(ERR, HASH, "memory allocation failed\n"); 222 goto err_unlock; 223 } 224 225 /* 226 * If x86 architecture is used, select appropriate compare function, 227 * which may use x86 intrinsics, otherwise use memcmp 228 */ 229 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) 230 /* Select function to compare keys */ 231 switch (params->key_len) { 232 case 16: 233 h->cmp_jump_table_idx = KEY_16_BYTES; 234 break; 235 case 32: 236 h->cmp_jump_table_idx = KEY_32_BYTES; 237 break; 238 case 48: 239 h->cmp_jump_table_idx = KEY_48_BYTES; 240 break; 241 case 64: 242 h->cmp_jump_table_idx = KEY_64_BYTES; 243 break; 244 case 80: 245 h->cmp_jump_table_idx = KEY_80_BYTES; 246 break; 247 case 96: 248 h->cmp_jump_table_idx = KEY_96_BYTES; 249 break; 250 case 112: 251 h->cmp_jump_table_idx = KEY_112_BYTES; 252 break; 253 case 128: 254 h->cmp_jump_table_idx = KEY_128_BYTES; 255 break; 256 default: 257 /* If key is not multiple of 16, use generic memcmp */ 258 h->cmp_jump_table_idx = KEY_OTHER_BYTES; 259 } 260 #else 261 h->cmp_jump_table_idx = KEY_OTHER_BYTES; 262 #endif 263 264 if (hw_trans_mem_support) { 265 h->local_free_slots = rte_zmalloc_socket(NULL, 266 sizeof(struct lcore_cache) * RTE_MAX_LCORE, 267 RTE_CACHE_LINE_SIZE, params->socket_id); 268 } 269 270 /* Setup hash context */ 271 snprintf(h->name, sizeof(h->name), "%s", params->name); 272 h->entries = params->entries; 273 h->key_len = params->key_len; 274 h->key_entry_size = key_entry_size; 275 h->hash_func_init_val = params->hash_func_init_val; 276 277 h->num_buckets = num_buckets; 278 h->bucket_bitmask = h->num_buckets - 1; 279 h->buckets = buckets; 280 h->hash_func = (params->hash_func == NULL) ? 281 DEFAULT_HASH_FUNC : params->hash_func; 282 h->key_store = k; 283 h->free_slots = r; 284 h->hw_trans_mem_support = hw_trans_mem_support; 285 286 #if defined(RTE_ARCH_X86) 287 if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)) 288 h->sig_cmp_fn = RTE_HASH_COMPARE_AVX2; 289 else if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) 290 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE; 291 else 292 #endif 293 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR; 294 295 /* Turn on multi-writer only with explicit flat from user and TM 296 * support. 297 */ 298 if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) { 299 if (h->hw_trans_mem_support) { 300 h->add_key = ADD_KEY_MULTIWRITER_TM; 301 } else { 302 h->add_key = ADD_KEY_MULTIWRITER; 303 h->multiwriter_lock = rte_malloc(NULL, 304 sizeof(rte_spinlock_t), 305 RTE_CACHE_LINE_SIZE); 306 if (h->multiwriter_lock == NULL) 307 goto err_unlock; 308 309 rte_spinlock_init(h->multiwriter_lock); 310 } 311 } else 312 h->add_key = ADD_KEY_SINGLEWRITER; 313 314 /* Populate free slots ring. Entry zero is reserved for key misses. */ 315 for (i = 1; i < num_key_slots; i++) 316 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); 317 318 te->data = (void *) h; 319 TAILQ_INSERT_TAIL(hash_list, te, next); 320 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 321 322 return h; 323 err_unlock: 324 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 325 err: 326 rte_ring_free(r); 327 rte_free(te); 328 rte_free(h); 329 rte_free(buckets); 330 rte_free(k); 331 return NULL; 332 } 333 334 void 335 rte_hash_free(struct rte_hash *h) 336 { 337 struct rte_tailq_entry *te; 338 struct rte_hash_list *hash_list; 339 340 if (h == NULL) 341 return; 342 343 hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); 344 345 rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); 346 347 /* find out tailq entry */ 348 TAILQ_FOREACH(te, hash_list, next) { 349 if (te->data == (void *) h) 350 break; 351 } 352 353 if (te == NULL) { 354 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 355 return; 356 } 357 358 TAILQ_REMOVE(hash_list, te, next); 359 360 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); 361 362 if (h->hw_trans_mem_support) 363 rte_free(h->local_free_slots); 364 365 if (h->add_key == ADD_KEY_MULTIWRITER) 366 rte_free(h->multiwriter_lock); 367 rte_ring_free(h->free_slots); 368 rte_free(h->key_store); 369 rte_free(h->buckets); 370 rte_free(h); 371 rte_free(te); 372 } 373 374 hash_sig_t 375 rte_hash_hash(const struct rte_hash *h, const void *key) 376 { 377 /* calc hash result by key */ 378 return h->hash_func(key, h->key_len, h->hash_func_init_val); 379 } 380 381 /* Calc the secondary hash value from the primary hash value of a given key */ 382 static inline hash_sig_t 383 rte_hash_secondary_hash(const hash_sig_t primary_hash) 384 { 385 static const unsigned all_bits_shift = 12; 386 static const unsigned alt_bits_xor = 0x5bd1e995; 387 388 uint32_t tag = primary_hash >> all_bits_shift; 389 390 return primary_hash ^ ((tag + 1) * alt_bits_xor); 391 } 392 393 void 394 rte_hash_reset(struct rte_hash *h) 395 { 396 void *ptr; 397 uint32_t tot_ring_cnt, i; 398 399 if (h == NULL) 400 return; 401 402 memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket)); 403 memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); 404 405 /* clear the free ring */ 406 while (rte_ring_dequeue(h->free_slots, &ptr) == 0) 407 rte_pause(); 408 409 /* Repopulate the free slots ring. Entry zero is reserved for key misses */ 410 if (h->hw_trans_mem_support) 411 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) * 412 (LCORE_CACHE_SIZE - 1); 413 else 414 tot_ring_cnt = h->entries; 415 416 for (i = 1; i < tot_ring_cnt + 1; i++) 417 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i)); 418 419 if (h->hw_trans_mem_support) { 420 /* Reset local caches per lcore */ 421 for (i = 0; i < RTE_MAX_LCORE; i++) 422 h->local_free_slots[i].len = 0; 423 } 424 } 425 426 /* Search for an entry that can be pushed to its alternative location */ 427 static inline int 428 make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt, 429 unsigned int *nr_pushes) 430 { 431 unsigned i, j; 432 int ret; 433 uint32_t next_bucket_idx; 434 struct rte_hash_bucket *next_bkt[RTE_HASH_BUCKET_ENTRIES]; 435 436 /* 437 * Push existing item (search for bucket with space in 438 * alternative locations) to its alternative location 439 */ 440 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 441 /* Search for space in alternative locations */ 442 next_bucket_idx = bkt->sig_alt[i] & h->bucket_bitmask; 443 next_bkt[i] = &h->buckets[next_bucket_idx]; 444 for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { 445 if (next_bkt[i]->key_idx[j] == EMPTY_SLOT) 446 break; 447 } 448 449 if (j != RTE_HASH_BUCKET_ENTRIES) 450 break; 451 } 452 453 /* Alternative location has spare room (end of recursive function) */ 454 if (i != RTE_HASH_BUCKET_ENTRIES) { 455 next_bkt[i]->sig_alt[j] = bkt->sig_current[i]; 456 next_bkt[i]->sig_current[j] = bkt->sig_alt[i]; 457 next_bkt[i]->key_idx[j] = bkt->key_idx[i]; 458 return i; 459 } 460 461 /* Pick entry that has not been pushed yet */ 462 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) 463 if (bkt->flag[i] == 0) 464 break; 465 466 /* All entries have been pushed, so entry cannot be added */ 467 if (i == RTE_HASH_BUCKET_ENTRIES || ++(*nr_pushes) > RTE_HASH_MAX_PUSHES) 468 return -ENOSPC; 469 470 /* Set flag to indicate that this entry is going to be pushed */ 471 bkt->flag[i] = 1; 472 473 /* Need room in alternative bucket to insert the pushed entry */ 474 ret = make_space_bucket(h, next_bkt[i], nr_pushes); 475 /* 476 * After recursive function. 477 * Clear flags and insert the pushed entry 478 * in its alternative location if successful, 479 * or return error 480 */ 481 bkt->flag[i] = 0; 482 if (ret >= 0) { 483 next_bkt[i]->sig_alt[ret] = bkt->sig_current[i]; 484 next_bkt[i]->sig_current[ret] = bkt->sig_alt[i]; 485 next_bkt[i]->key_idx[ret] = bkt->key_idx[i]; 486 return i; 487 } else 488 return ret; 489 490 } 491 492 /* 493 * Function called to enqueue back an index in the cache/ring, 494 * as slot has not being used and it can be used in the 495 * next addition attempt. 496 */ 497 static inline void 498 enqueue_slot_back(const struct rte_hash *h, 499 struct lcore_cache *cached_free_slots, 500 void *slot_id) 501 { 502 if (h->hw_trans_mem_support) { 503 cached_free_slots->objs[cached_free_slots->len] = slot_id; 504 cached_free_slots->len++; 505 } else 506 rte_ring_sp_enqueue(h->free_slots, slot_id); 507 } 508 509 static inline int32_t 510 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, 511 hash_sig_t sig, void *data) 512 { 513 hash_sig_t alt_hash; 514 uint32_t prim_bucket_idx, sec_bucket_idx; 515 unsigned i; 516 struct rte_hash_bucket *prim_bkt, *sec_bkt; 517 struct rte_hash_key *new_k, *k, *keys = h->key_store; 518 void *slot_id = NULL; 519 uint32_t new_idx; 520 int ret; 521 unsigned n_slots; 522 unsigned lcore_id; 523 struct lcore_cache *cached_free_slots = NULL; 524 unsigned int nr_pushes = 0; 525 526 if (h->add_key == ADD_KEY_MULTIWRITER) 527 rte_spinlock_lock(h->multiwriter_lock); 528 529 prim_bucket_idx = sig & h->bucket_bitmask; 530 prim_bkt = &h->buckets[prim_bucket_idx]; 531 rte_prefetch0(prim_bkt); 532 533 alt_hash = rte_hash_secondary_hash(sig); 534 sec_bucket_idx = alt_hash & h->bucket_bitmask; 535 sec_bkt = &h->buckets[sec_bucket_idx]; 536 rte_prefetch0(sec_bkt); 537 538 /* Get a new slot for storing the new key */ 539 if (h->hw_trans_mem_support) { 540 lcore_id = rte_lcore_id(); 541 cached_free_slots = &h->local_free_slots[lcore_id]; 542 /* Try to get a free slot from the local cache */ 543 if (cached_free_slots->len == 0) { 544 /* Need to get another burst of free slots from global ring */ 545 n_slots = rte_ring_mc_dequeue_burst(h->free_slots, 546 cached_free_slots->objs, 547 LCORE_CACHE_SIZE, NULL); 548 if (n_slots == 0) { 549 ret = -ENOSPC; 550 goto failure; 551 } 552 553 cached_free_slots->len += n_slots; 554 } 555 556 /* Get a free slot from the local cache */ 557 cached_free_slots->len--; 558 slot_id = cached_free_slots->objs[cached_free_slots->len]; 559 } else { 560 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) { 561 ret = -ENOSPC; 562 goto failure; 563 } 564 } 565 566 new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size); 567 rte_prefetch0(new_k); 568 new_idx = (uint32_t)((uintptr_t) slot_id); 569 570 /* Check if key is already inserted in primary location */ 571 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 572 if (prim_bkt->sig_current[i] == sig && 573 prim_bkt->sig_alt[i] == alt_hash) { 574 k = (struct rte_hash_key *) ((char *)keys + 575 prim_bkt->key_idx[i] * h->key_entry_size); 576 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 577 /* Enqueue index of free slot back in the ring. */ 578 enqueue_slot_back(h, cached_free_slots, slot_id); 579 /* Update data */ 580 k->pdata = data; 581 /* 582 * Return index where key is stored, 583 * subtracting the first dummy index 584 */ 585 ret = prim_bkt->key_idx[i] - 1; 586 goto failure; 587 } 588 } 589 } 590 591 /* Check if key is already inserted in secondary location */ 592 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 593 if (sec_bkt->sig_alt[i] == sig && 594 sec_bkt->sig_current[i] == alt_hash) { 595 k = (struct rte_hash_key *) ((char *)keys + 596 sec_bkt->key_idx[i] * h->key_entry_size); 597 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 598 /* Enqueue index of free slot back in the ring. */ 599 enqueue_slot_back(h, cached_free_slots, slot_id); 600 /* Update data */ 601 k->pdata = data; 602 /* 603 * Return index where key is stored, 604 * subtracting the first dummy index 605 */ 606 ret = sec_bkt->key_idx[i] - 1; 607 goto failure; 608 } 609 } 610 } 611 612 /* Copy key */ 613 rte_memcpy(new_k->key, key, h->key_len); 614 new_k->pdata = data; 615 616 #if defined(RTE_ARCH_X86) /* currently only x86 support HTM */ 617 if (h->add_key == ADD_KEY_MULTIWRITER_TM) { 618 ret = rte_hash_cuckoo_insert_mw_tm(prim_bkt, 619 sig, alt_hash, new_idx); 620 if (ret >= 0) 621 return new_idx - 1; 622 623 /* Primary bucket full, need to make space for new entry */ 624 ret = rte_hash_cuckoo_make_space_mw_tm(h, prim_bkt, sig, 625 alt_hash, new_idx); 626 627 if (ret >= 0) 628 return new_idx - 1; 629 630 /* Also search secondary bucket to get better occupancy */ 631 ret = rte_hash_cuckoo_make_space_mw_tm(h, sec_bkt, sig, 632 alt_hash, new_idx); 633 634 if (ret >= 0) 635 return new_idx - 1; 636 } else { 637 #endif 638 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 639 /* Check if slot is available */ 640 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) { 641 prim_bkt->sig_current[i] = sig; 642 prim_bkt->sig_alt[i] = alt_hash; 643 prim_bkt->key_idx[i] = new_idx; 644 break; 645 } 646 } 647 648 if (i != RTE_HASH_BUCKET_ENTRIES) { 649 if (h->add_key == ADD_KEY_MULTIWRITER) 650 rte_spinlock_unlock(h->multiwriter_lock); 651 return new_idx - 1; 652 } 653 654 /* Primary bucket full, need to make space for new entry 655 * After recursive function. 656 * Insert the new entry in the position of the pushed entry 657 * if successful or return error and 658 * store the new slot back in the ring 659 */ 660 ret = make_space_bucket(h, prim_bkt, &nr_pushes); 661 if (ret >= 0) { 662 prim_bkt->sig_current[ret] = sig; 663 prim_bkt->sig_alt[ret] = alt_hash; 664 prim_bkt->key_idx[ret] = new_idx; 665 if (h->add_key == ADD_KEY_MULTIWRITER) 666 rte_spinlock_unlock(h->multiwriter_lock); 667 return new_idx - 1; 668 } 669 #if defined(RTE_ARCH_X86) 670 } 671 #endif 672 /* Error in addition, store new slot back in the ring and return error */ 673 enqueue_slot_back(h, cached_free_slots, (void *)((uintptr_t) new_idx)); 674 675 failure: 676 if (h->add_key == ADD_KEY_MULTIWRITER) 677 rte_spinlock_unlock(h->multiwriter_lock); 678 return ret; 679 } 680 681 int32_t 682 rte_hash_add_key_with_hash(const struct rte_hash *h, 683 const void *key, hash_sig_t sig) 684 { 685 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 686 return __rte_hash_add_key_with_hash(h, key, sig, 0); 687 } 688 689 int32_t 690 rte_hash_add_key(const struct rte_hash *h, const void *key) 691 { 692 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 693 return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0); 694 } 695 696 int 697 rte_hash_add_key_with_hash_data(const struct rte_hash *h, 698 const void *key, hash_sig_t sig, void *data) 699 { 700 int ret; 701 702 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 703 ret = __rte_hash_add_key_with_hash(h, key, sig, data); 704 if (ret >= 0) 705 return 0; 706 else 707 return ret; 708 } 709 710 int 711 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data) 712 { 713 int ret; 714 715 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 716 717 ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data); 718 if (ret >= 0) 719 return 0; 720 else 721 return ret; 722 } 723 static inline int32_t 724 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, 725 hash_sig_t sig, void **data) 726 { 727 uint32_t bucket_idx; 728 hash_sig_t alt_hash; 729 unsigned i; 730 struct rte_hash_bucket *bkt; 731 struct rte_hash_key *k, *keys = h->key_store; 732 733 bucket_idx = sig & h->bucket_bitmask; 734 bkt = &h->buckets[bucket_idx]; 735 736 /* Check if key is in primary location */ 737 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 738 if (bkt->sig_current[i] == sig && 739 bkt->key_idx[i] != EMPTY_SLOT) { 740 k = (struct rte_hash_key *) ((char *)keys + 741 bkt->key_idx[i] * h->key_entry_size); 742 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 743 if (data != NULL) 744 *data = k->pdata; 745 /* 746 * Return index where key is stored, 747 * subtracting the first dummy index 748 */ 749 return bkt->key_idx[i] - 1; 750 } 751 } 752 } 753 754 /* Calculate secondary hash */ 755 alt_hash = rte_hash_secondary_hash(sig); 756 bucket_idx = alt_hash & h->bucket_bitmask; 757 bkt = &h->buckets[bucket_idx]; 758 759 /* Check if key is in secondary location */ 760 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 761 if (bkt->sig_current[i] == alt_hash && 762 bkt->sig_alt[i] == sig) { 763 k = (struct rte_hash_key *) ((char *)keys + 764 bkt->key_idx[i] * h->key_entry_size); 765 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 766 if (data != NULL) 767 *data = k->pdata; 768 /* 769 * Return index where key is stored, 770 * subtracting the first dummy index 771 */ 772 return bkt->key_idx[i] - 1; 773 } 774 } 775 } 776 777 return -ENOENT; 778 } 779 780 int32_t 781 rte_hash_lookup_with_hash(const struct rte_hash *h, 782 const void *key, hash_sig_t sig) 783 { 784 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 785 return __rte_hash_lookup_with_hash(h, key, sig, NULL); 786 } 787 788 int32_t 789 rte_hash_lookup(const struct rte_hash *h, const void *key) 790 { 791 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 792 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL); 793 } 794 795 int 796 rte_hash_lookup_with_hash_data(const struct rte_hash *h, 797 const void *key, hash_sig_t sig, void **data) 798 { 799 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 800 return __rte_hash_lookup_with_hash(h, key, sig, data); 801 } 802 803 int 804 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data) 805 { 806 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 807 return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data); 808 } 809 810 static inline void 811 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) 812 { 813 unsigned lcore_id, n_slots; 814 struct lcore_cache *cached_free_slots; 815 816 bkt->sig_current[i] = NULL_SIGNATURE; 817 bkt->sig_alt[i] = NULL_SIGNATURE; 818 if (h->hw_trans_mem_support) { 819 lcore_id = rte_lcore_id(); 820 cached_free_slots = &h->local_free_slots[lcore_id]; 821 /* Cache full, need to free it. */ 822 if (cached_free_slots->len == LCORE_CACHE_SIZE) { 823 /* Need to enqueue the free slots in global ring. */ 824 n_slots = rte_ring_mp_enqueue_burst(h->free_slots, 825 cached_free_slots->objs, 826 LCORE_CACHE_SIZE, NULL); 827 cached_free_slots->len -= n_slots; 828 } 829 /* Put index of new free slot in cache. */ 830 cached_free_slots->objs[cached_free_slots->len] = 831 (void *)((uintptr_t)bkt->key_idx[i]); 832 cached_free_slots->len++; 833 } else { 834 rte_ring_sp_enqueue(h->free_slots, 835 (void *)((uintptr_t)bkt->key_idx[i])); 836 } 837 } 838 839 static inline int32_t 840 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, 841 hash_sig_t sig) 842 { 843 uint32_t bucket_idx; 844 hash_sig_t alt_hash; 845 unsigned i; 846 struct rte_hash_bucket *bkt; 847 struct rte_hash_key *k, *keys = h->key_store; 848 int32_t ret; 849 850 bucket_idx = sig & h->bucket_bitmask; 851 bkt = &h->buckets[bucket_idx]; 852 853 /* Check if key is in primary location */ 854 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 855 if (bkt->sig_current[i] == sig && 856 bkt->key_idx[i] != EMPTY_SLOT) { 857 k = (struct rte_hash_key *) ((char *)keys + 858 bkt->key_idx[i] * h->key_entry_size); 859 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 860 remove_entry(h, bkt, i); 861 862 /* 863 * Return index where key is stored, 864 * subtracting the first dummy index 865 */ 866 ret = bkt->key_idx[i] - 1; 867 bkt->key_idx[i] = EMPTY_SLOT; 868 return ret; 869 } 870 } 871 } 872 873 /* Calculate secondary hash */ 874 alt_hash = rte_hash_secondary_hash(sig); 875 bucket_idx = alt_hash & h->bucket_bitmask; 876 bkt = &h->buckets[bucket_idx]; 877 878 /* Check if key is in secondary location */ 879 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 880 if (bkt->sig_current[i] == alt_hash && 881 bkt->key_idx[i] != EMPTY_SLOT) { 882 k = (struct rte_hash_key *) ((char *)keys + 883 bkt->key_idx[i] * h->key_entry_size); 884 if (rte_hash_cmp_eq(key, k->key, h) == 0) { 885 remove_entry(h, bkt, i); 886 887 /* 888 * Return index where key is stored, 889 * subtracting the first dummy index 890 */ 891 ret = bkt->key_idx[i] - 1; 892 bkt->key_idx[i] = EMPTY_SLOT; 893 return ret; 894 } 895 } 896 } 897 898 return -ENOENT; 899 } 900 901 int32_t 902 rte_hash_del_key_with_hash(const struct rte_hash *h, 903 const void *key, hash_sig_t sig) 904 { 905 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 906 return __rte_hash_del_key_with_hash(h, key, sig); 907 } 908 909 int32_t 910 rte_hash_del_key(const struct rte_hash *h, const void *key) 911 { 912 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 913 return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); 914 } 915 916 int 917 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, 918 void **key) 919 { 920 RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); 921 922 struct rte_hash_key *k, *keys = h->key_store; 923 k = (struct rte_hash_key *) ((char *) keys + (position + 1) * 924 h->key_entry_size); 925 *key = k->key; 926 927 if (position != 928 __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key), 929 NULL)) { 930 return -ENOENT; 931 } 932 933 return 0; 934 } 935 936 static inline void 937 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches, 938 const struct rte_hash_bucket *prim_bkt, 939 const struct rte_hash_bucket *sec_bkt, 940 hash_sig_t prim_hash, hash_sig_t sec_hash, 941 enum rte_hash_sig_compare_function sig_cmp_fn) 942 { 943 unsigned int i; 944 945 switch (sig_cmp_fn) { 946 #ifdef RTE_MACHINE_CPUFLAG_AVX2 947 case RTE_HASH_COMPARE_AVX2: 948 *prim_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32( 949 _mm256_load_si256( 950 (__m256i const *)prim_bkt->sig_current), 951 _mm256_set1_epi32(prim_hash))); 952 *sec_hash_matches = _mm256_movemask_ps((__m256)_mm256_cmpeq_epi32( 953 _mm256_load_si256( 954 (__m256i const *)sec_bkt->sig_current), 955 _mm256_set1_epi32(sec_hash))); 956 break; 957 #endif 958 #ifdef RTE_MACHINE_CPUFLAG_SSE2 959 case RTE_HASH_COMPARE_SSE: 960 /* Compare the first 4 signatures in the bucket */ 961 *prim_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16( 962 _mm_load_si128( 963 (__m128i const *)prim_bkt->sig_current), 964 _mm_set1_epi32(prim_hash))); 965 *prim_hash_matches |= (_mm_movemask_ps((__m128)_mm_cmpeq_epi16( 966 _mm_load_si128( 967 (__m128i const *)&prim_bkt->sig_current[4]), 968 _mm_set1_epi32(prim_hash)))) << 4; 969 /* Compare the first 4 signatures in the bucket */ 970 *sec_hash_matches = _mm_movemask_ps((__m128)_mm_cmpeq_epi16( 971 _mm_load_si128( 972 (__m128i const *)sec_bkt->sig_current), 973 _mm_set1_epi32(sec_hash))); 974 *sec_hash_matches |= (_mm_movemask_ps((__m128)_mm_cmpeq_epi16( 975 _mm_load_si128( 976 (__m128i const *)&sec_bkt->sig_current[4]), 977 _mm_set1_epi32(sec_hash)))) << 4; 978 break; 979 #endif 980 default: 981 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { 982 *prim_hash_matches |= 983 ((prim_hash == prim_bkt->sig_current[i]) << i); 984 *sec_hash_matches |= 985 ((sec_hash == sec_bkt->sig_current[i]) << i); 986 } 987 } 988 989 } 990 991 #define PREFETCH_OFFSET 4 992 static inline void 993 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 994 int32_t num_keys, int32_t *positions, 995 uint64_t *hit_mask, void *data[]) 996 { 997 uint64_t hits = 0; 998 int32_t i; 999 uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX]; 1000 uint32_t sec_hash[RTE_HASH_LOOKUP_BULK_MAX]; 1001 const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; 1002 const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; 1003 uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; 1004 uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0}; 1005 1006 /* Prefetch first keys */ 1007 for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++) 1008 rte_prefetch0(keys[i]); 1009 1010 /* 1011 * Prefetch rest of the keys, calculate primary and 1012 * secondary bucket and prefetch them 1013 */ 1014 for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) { 1015 rte_prefetch0(keys[i + PREFETCH_OFFSET]); 1016 1017 prim_hash[i] = rte_hash_hash(h, keys[i]); 1018 sec_hash[i] = rte_hash_secondary_hash(prim_hash[i]); 1019 1020 primary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask]; 1021 secondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask]; 1022 1023 rte_prefetch0(primary_bkt[i]); 1024 rte_prefetch0(secondary_bkt[i]); 1025 } 1026 1027 /* Calculate and prefetch rest of the buckets */ 1028 for (; i < num_keys; i++) { 1029 prim_hash[i] = rte_hash_hash(h, keys[i]); 1030 sec_hash[i] = rte_hash_secondary_hash(prim_hash[i]); 1031 1032 primary_bkt[i] = &h->buckets[prim_hash[i] & h->bucket_bitmask]; 1033 secondary_bkt[i] = &h->buckets[sec_hash[i] & h->bucket_bitmask]; 1034 1035 rte_prefetch0(primary_bkt[i]); 1036 rte_prefetch0(secondary_bkt[i]); 1037 } 1038 1039 /* Compare signatures and prefetch key slot of first hit */ 1040 for (i = 0; i < num_keys; i++) { 1041 compare_signatures(&prim_hitmask[i], &sec_hitmask[i], 1042 primary_bkt[i], secondary_bkt[i], 1043 prim_hash[i], sec_hash[i], h->sig_cmp_fn); 1044 1045 if (prim_hitmask[i]) { 1046 uint32_t first_hit = __builtin_ctzl(prim_hitmask[i]); 1047 uint32_t key_idx = primary_bkt[i]->key_idx[first_hit]; 1048 const struct rte_hash_key *key_slot = 1049 (const struct rte_hash_key *)( 1050 (const char *)h->key_store + 1051 key_idx * h->key_entry_size); 1052 rte_prefetch0(key_slot); 1053 continue; 1054 } 1055 1056 if (sec_hitmask[i]) { 1057 uint32_t first_hit = __builtin_ctzl(sec_hitmask[i]); 1058 uint32_t key_idx = secondary_bkt[i]->key_idx[first_hit]; 1059 const struct rte_hash_key *key_slot = 1060 (const struct rte_hash_key *)( 1061 (const char *)h->key_store + 1062 key_idx * h->key_entry_size); 1063 rte_prefetch0(key_slot); 1064 } 1065 } 1066 1067 /* Compare keys, first hits in primary first */ 1068 for (i = 0; i < num_keys; i++) { 1069 positions[i] = -ENOENT; 1070 while (prim_hitmask[i]) { 1071 uint32_t hit_index = __builtin_ctzl(prim_hitmask[i]); 1072 1073 uint32_t key_idx = primary_bkt[i]->key_idx[hit_index]; 1074 const struct rte_hash_key *key_slot = 1075 (const struct rte_hash_key *)( 1076 (const char *)h->key_store + 1077 key_idx * h->key_entry_size); 1078 /* 1079 * If key index is 0, do not compare key, 1080 * as it is checking the dummy slot 1081 */ 1082 if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { 1083 if (data != NULL) 1084 data[i] = key_slot->pdata; 1085 1086 hits |= 1ULL << i; 1087 positions[i] = key_idx - 1; 1088 goto next_key; 1089 } 1090 prim_hitmask[i] &= ~(1 << (hit_index)); 1091 } 1092 1093 while (sec_hitmask[i]) { 1094 uint32_t hit_index = __builtin_ctzl(sec_hitmask[i]); 1095 1096 uint32_t key_idx = secondary_bkt[i]->key_idx[hit_index]; 1097 const struct rte_hash_key *key_slot = 1098 (const struct rte_hash_key *)( 1099 (const char *)h->key_store + 1100 key_idx * h->key_entry_size); 1101 /* 1102 * If key index is 0, do not compare key, 1103 * as it is checking the dummy slot 1104 */ 1105 1106 if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) { 1107 if (data != NULL) 1108 data[i] = key_slot->pdata; 1109 1110 hits |= 1ULL << i; 1111 positions[i] = key_idx - 1; 1112 goto next_key; 1113 } 1114 sec_hitmask[i] &= ~(1 << (hit_index)); 1115 } 1116 1117 next_key: 1118 continue; 1119 } 1120 1121 if (hit_mask != NULL) 1122 *hit_mask = hits; 1123 } 1124 1125 int 1126 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 1127 uint32_t num_keys, int32_t *positions) 1128 { 1129 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || 1130 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || 1131 (positions == NULL)), -EINVAL); 1132 1133 __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL); 1134 return 0; 1135 } 1136 1137 int 1138 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, 1139 uint32_t num_keys, uint64_t *hit_mask, void *data[]) 1140 { 1141 RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || 1142 (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || 1143 (hit_mask == NULL)), -EINVAL); 1144 1145 int32_t positions[num_keys]; 1146 1147 __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data); 1148 1149 /* Return number of hits */ 1150 return __builtin_popcountl(*hit_mask); 1151 } 1152 1153 int32_t 1154 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next) 1155 { 1156 uint32_t bucket_idx, idx, position; 1157 struct rte_hash_key *next_key; 1158 1159 RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL); 1160 1161 const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; 1162 /* Out of bounds */ 1163 if (*next >= total_entries) 1164 return -ENOENT; 1165 1166 /* Calculate bucket and index of current iterator */ 1167 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; 1168 idx = *next % RTE_HASH_BUCKET_ENTRIES; 1169 1170 /* If current position is empty, go to the next one */ 1171 while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) { 1172 (*next)++; 1173 /* End of table */ 1174 if (*next == total_entries) 1175 return -ENOENT; 1176 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; 1177 idx = *next % RTE_HASH_BUCKET_ENTRIES; 1178 } 1179 1180 /* Get position of entry in key table */ 1181 position = h->buckets[bucket_idx].key_idx[idx]; 1182 next_key = (struct rte_hash_key *) ((char *)h->key_store + 1183 position * h->key_entry_size); 1184 /* Return key and data */ 1185 *key = next_key->key; 1186 *data = next_key->pdata; 1187 1188 /* Increment iterator */ 1189 (*next)++; 1190 1191 return position - 1; 1192 } 1193