4 * Copyright(c) 2016 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
34 /* rte_cuckoo_hash_x86.h
35 * This file holds all x86 specific Cuckoo Hash functions
38 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
41 static inline unsigned
42 rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt,
43 hash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx)
48 while (try < RTE_HASH_TSX_MAX_RETRY) {
49 status = rte_xbegin();
50 if (likely(status == RTE_XBEGIN_STARTED)) {
51 /* Insert new entry if there is room in the primary
54 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
55 /* Check if slot is available */
56 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
57 prim_bkt->sig_current[i] = sig;
58 prim_bkt->sig_alt[i] = alt_hash;
59 prim_bkt->key_idx[i] = new_idx;
65 if (i != RTE_HASH_BUCKET_ENTRIES)
68 break; /* break off try loop if transaction commits */
70 /* If we abort we give up this cuckoo path. */
79 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
80 * the path head with new entry (sig, alt_hash, new_idx)
83 rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
84 struct queue_node *leaf, uint32_t leaf_slot,
85 hash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx)
89 uint32_t prev_alt_bkt_idx;
91 struct queue_node *prev_node, *curr_node = leaf;
92 struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
93 uint32_t prev_slot, curr_slot = leaf_slot;
95 while (try < RTE_HASH_TSX_MAX_RETRY) {
96 status = rte_xbegin();
97 if (likely(status == RTE_XBEGIN_STARTED)) {
98 while (likely(curr_node->prev != NULL)) {
99 prev_node = curr_node->prev;
100 prev_bkt = prev_node->bkt;
101 prev_slot = curr_node->prev_slot;
104 = prev_bkt->sig_alt[prev_slot]
107 if (unlikely(&h->buckets[prev_alt_bkt_idx]
109 rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
112 /* Need to swap current/alt sig to allow later
113 * Cuckoo insert to move elements back to its
114 * primary bucket if available
116 curr_bkt->sig_alt[curr_slot] =
117 prev_bkt->sig_current[prev_slot];
118 curr_bkt->sig_current[curr_slot] =
119 prev_bkt->sig_alt[prev_slot];
120 curr_bkt->key_idx[curr_slot]
121 = prev_bkt->key_idx[prev_slot];
123 curr_slot = prev_slot;
124 curr_node = prev_node;
125 curr_bkt = curr_node->bkt;
128 curr_bkt->sig_current[curr_slot] = sig;
129 curr_bkt->sig_alt[curr_slot] = alt_hash;
130 curr_bkt->key_idx[curr_slot] = new_idx;
137 /* If we abort we give up this cuckoo path, since most likely it's
138 * no longer valid as TSX detected data conflict
148 * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
152 rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
153 struct rte_hash_bucket *bkt,
154 hash_sig_t sig, hash_sig_t alt_hash,
158 struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
159 struct queue_node *tail, *head;
160 struct rte_hash_bucket *curr_bkt, *alt_bkt;
166 tail->prev_slot = -1;
168 /* Cuckoo bfs Search */
169 while (likely(tail != head && head <
170 queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) {
171 curr_bkt = tail->bkt;
172 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
173 if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
174 if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
176 alt_hash, new_idx) == 0))
180 /* Enqueue new node and keep prev node info */
181 alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
182 & h->bucket_bitmask]);