rte_cuckoo_hash_x86.h revision 8b25d1ad
1/*-
2 *   BSD LICENSE
3 *
4 *   Copyright(c) 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/* rte_cuckoo_hash_x86.h
35 * This file holds all x86 specific Cuckoo Hash functions
36 */
37
38/* Only tries to insert at one bucket (@prim_bkt) without trying to push
39 * buckets around
40 */
41static inline unsigned
42rte_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)
44{
45	unsigned i, status;
46	unsigned try = 0;
47
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
52			* bucket.
53			*/
54			for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
55				/* Check if slot is available */
56				if (likely(prim_bkt->signatures[i].sig ==
57						NULL_SIGNATURE)) {
58					prim_bkt->signatures[i].current = sig;
59					prim_bkt->signatures[i].alt = alt_hash;
60					prim_bkt->key_idx[i] = new_idx;
61					break;
62				}
63			}
64			rte_xend();
65
66			if (i != RTE_HASH_BUCKET_ENTRIES)
67				return 0;
68
69			break; /* break off try loop if transaction commits */
70		} else {
71			/* If we abort we give up this cuckoo path. */
72			try++;
73			rte_pause();
74		}
75	}
76
77	return -1;
78}
79
80/* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
81 * the path head with new entry (sig, alt_hash, new_idx)
82 */
83static inline int
84rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h,
85			struct queue_node *leaf, uint32_t leaf_slot,
86			hash_sig_t sig, hash_sig_t alt_hash, uint32_t new_idx)
87{
88	unsigned try = 0;
89	unsigned status;
90	uint32_t prev_alt_bkt_idx;
91
92	struct queue_node *prev_node, *curr_node = leaf;
93	struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
94	uint32_t prev_slot, curr_slot = leaf_slot;
95
96	while (try < RTE_HASH_TSX_MAX_RETRY) {
97		status = rte_xbegin();
98		if (likely(status == RTE_XBEGIN_STARTED)) {
99			while (likely(curr_node->prev != NULL)) {
100				prev_node = curr_node->prev;
101				prev_bkt = prev_node->bkt;
102				prev_slot = curr_node->prev_slot;
103
104				prev_alt_bkt_idx
105					= prev_bkt->signatures[prev_slot].alt
106					    & h->bucket_bitmask;
107
108				if (unlikely(&h->buckets[prev_alt_bkt_idx]
109					     != curr_bkt)) {
110					rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
111				}
112
113				/* Need to swap current/alt sig to allow later
114				 * Cuckoo insert to move elements back to its
115				 * primary bucket if available
116				 */
117				curr_bkt->signatures[curr_slot].alt =
118				    prev_bkt->signatures[prev_slot].current;
119				curr_bkt->signatures[curr_slot].current =
120				    prev_bkt->signatures[prev_slot].alt;
121				curr_bkt->key_idx[curr_slot]
122				    = prev_bkt->key_idx[prev_slot];
123
124				curr_slot = prev_slot;
125				curr_node = prev_node;
126				curr_bkt = curr_node->bkt;
127			}
128
129			curr_bkt->signatures[curr_slot].current = sig;
130			curr_bkt->signatures[curr_slot].alt = alt_hash;
131			curr_bkt->key_idx[curr_slot] = new_idx;
132
133			rte_xend();
134
135			return 0;
136		}
137
138		/* If we abort we give up this cuckoo path, since most likely it's
139		 * no longer valid as TSX detected data conflict
140		 */
141		try++;
142		rte_pause();
143	}
144
145	return -1;
146}
147
148/*
149 * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
150 * Cuckoo
151 */
152static inline int
153rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
154			struct rte_hash_bucket *bkt,
155			hash_sig_t sig, hash_sig_t alt_hash,
156			uint32_t new_idx)
157{
158	unsigned i;
159	struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
160	struct queue_node *tail, *head;
161	struct rte_hash_bucket *curr_bkt, *alt_bkt;
162
163	tail = queue;
164	head = queue + 1;
165	tail->bkt = bkt;
166	tail->prev = NULL;
167	tail->prev_slot = -1;
168
169	/* Cuckoo bfs Search */
170	while (likely(tail != head && head <
171					queue + RTE_HASH_BFS_QUEUE_MAX_LEN - 4)) {
172		curr_bkt = tail->bkt;
173		for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
174			if (curr_bkt->signatures[i].sig == NULL_SIGNATURE) {
175				if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
176						tail, i, sig,
177						alt_hash, new_idx) == 0))
178					return 0;
179			}
180
181			/* Enqueue new node and keep prev node info */
182			alt_bkt = &(h->buckets[curr_bkt->signatures[i].alt
183						    & h->bucket_bitmask]);
184			head->bkt = alt_bkt;
185			head->prev = tail;
186			head->prev_slot = i;
187			head++;
188		}
189		tail++;
190	}
191
192	return -ENOSPC;
193}
194