1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2016 Intel Corporation
5 /* rte_cuckoo_hash_x86.h
6 * This file holds all x86 specific Cuckoo Hash functions
9 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
12 static inline unsigned
13 rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt,
14 hash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx)
19 while (try < RTE_HASH_TSX_MAX_RETRY) {
20 status = rte_xbegin();
21 if (likely(status == RTE_XBEGIN_STARTED)) {
22 /* Insert new entry if there is room in the primary
25 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
26 /* Check if slot is available */
27 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
28 prim_bkt->sig_current[i] = sig;
29 prim_bkt->sig_alt[i] = alt_hash;
30 prim_bkt->key_idx[i] = new_idx;
36 if (i != RTE_HASH_BUCKET_ENTRIES)
39 break; /* break off try loop if transaction commits */
41 /* If we abort we give up this cuckoo path. */
50 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
51 * the path head with new entry (sig, alt_hash, new_idx)
54 rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
55 struct queue_node *leaf, uint32_t leaf_slot,
56 hash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx)
60 uint32_t prev_alt_bkt_idx;
62 struct queue_node *prev_node, *curr_node = leaf;
63 struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
64 uint32_t prev_slot, curr_slot = leaf_slot;
66 while (try < RTE_HASH_TSX_MAX_RETRY) {
67 status = rte_xbegin();
68 if (likely(status == RTE_XBEGIN_STARTED)) {
69 /* In case empty slot was gone before entering TSX */
70 if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT)
71 rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
72 while (likely(curr_node->prev != NULL)) {
73 prev_node = curr_node->prev;
74 prev_bkt = prev_node->bkt;
75 prev_slot = curr_node->prev_slot;
78 = prev_bkt->sig_alt[prev_slot]
81 if (unlikely(&h->buckets[prev_alt_bkt_idx]
83 rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
86 /* Need to swap current/alt sig to allow later
87 * Cuckoo insert to move elements back to its
88 * primary bucket if available
90 curr_bkt->sig_alt[curr_slot] =
91 prev_bkt->sig_current[prev_slot];
92 curr_bkt->sig_current[curr_slot] =
93 prev_bkt->sig_alt[prev_slot];
94 curr_bkt->key_idx[curr_slot]
95 = prev_bkt->key_idx[prev_slot];
97 curr_slot = prev_slot;
98 curr_node = prev_node;
99 curr_bkt = curr_node->bkt;
102 curr_bkt->sig_current[curr_slot] = sig;
103 curr_bkt->sig_alt[curr_slot] = alt_hash;
104 curr_bkt->key_idx[curr_slot] = new_idx;
111 /* If we abort we give up this cuckoo path, since most likely it's
112 * no longer valid as TSX detected data conflict
122 * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
126 rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
127 struct rte_hash_bucket *bkt,
128 hash_sig_t sig, hash_sig_t alt_hash,
132 struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
133 struct queue_node *tail, *head;
134 struct rte_hash_bucket *curr_bkt, *alt_bkt;
140 tail->prev_slot = -1;
142 /* Cuckoo bfs Search */
143 while (likely(tail != head && head <
144 queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
145 RTE_HASH_BUCKET_ENTRIES)) {
146 curr_bkt = tail->bkt;
147 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
148 if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
149 if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
151 alt_hash, new_idx) == 0))
155 /* Enqueue new node and keep prev node info */
156 alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
157 & h->bucket_bitmask]);