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
-
171 RTE_HASH_BUCKET_ENTRIES
)) {
172 curr_bkt
= tail
->bkt
;
173 for (i
= 0; i
< RTE_HASH_BUCKET_ENTRIES
; i
++) {
174 if (curr_bkt
->key_idx
[i
] == EMPTY_SLOT
) {
175 if (likely(rte_hash_cuckoo_move_insert_mw_tm(h
,
177 alt_hash
, new_idx
) == 0))
181 /* Enqueue new node and keep prev node info */
182 alt_bkt
= &(h
->buckets
[curr_bkt
->sig_alt
[i
]
183 & h
->bucket_bitmask
]);