DPDK  17.11.10
rte_cuckoo_hash_x86.h
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  */
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)
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->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;
60  break;
61  }
62  }
63  rte_xend();
64 
65  if (i != RTE_HASH_BUCKET_ENTRIES)
66  return 0;
67 
68  break; /* break off try loop if transaction commits */
69  } else {
70  /* If we abort we give up this cuckoo path. */
71  try++;
72  rte_pause();
73  }
74  }
75 
76  return -1;
77 }
78 
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)
81  */
82 static inline int
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)
86 {
87  unsigned try = 0;
88  unsigned status;
89  uint32_t prev_alt_bkt_idx;
90 
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;
94 
95  while (try < RTE_HASH_TSX_MAX_RETRY) {
96  status = rte_xbegin();
97  if (likely(status == RTE_XBEGIN_STARTED)) {
98  /* In case empty slot was gone before entering TSX */
99  if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT)
100  rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
101  while (likely(curr_node->prev != NULL)) {
102  prev_node = curr_node->prev;
103  prev_bkt = prev_node->bkt;
104  prev_slot = curr_node->prev_slot;
105 
106  prev_alt_bkt_idx
107  = prev_bkt->sig_alt[prev_slot]
108  & h->bucket_bitmask;
109 
110  if (unlikely(&h->buckets[prev_alt_bkt_idx]
111  != curr_bkt)) {
112  rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
113  }
114 
115  /* Need to swap current/alt sig to allow later
116  * Cuckoo insert to move elements back to its
117  * primary bucket if available
118  */
119  curr_bkt->sig_alt[curr_slot] =
120  prev_bkt->sig_current[prev_slot];
121  curr_bkt->sig_current[curr_slot] =
122  prev_bkt->sig_alt[prev_slot];
123  curr_bkt->key_idx[curr_slot]
124  = prev_bkt->key_idx[prev_slot];
125 
126  curr_slot = prev_slot;
127  curr_node = prev_node;
128  curr_bkt = curr_node->bkt;
129  }
130 
131  curr_bkt->sig_current[curr_slot] = sig;
132  curr_bkt->sig_alt[curr_slot] = alt_hash;
133  curr_bkt->key_idx[curr_slot] = new_idx;
134 
135  rte_xend();
136 
137  return 0;
138  }
139 
140  /* If we abort we give up this cuckoo path, since most likely it's
141  * no longer valid as TSX detected data conflict
142  */
143  try++;
144  rte_pause();
145  }
146 
147  return -1;
148 }
149 
150 /*
151  * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
152  * Cuckoo
153  */
154 static inline int
155 rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
156  struct rte_hash_bucket *bkt,
157  hash_sig_t sig, hash_sig_t alt_hash,
158  uint32_t new_idx)
159 {
160  unsigned i;
161  struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
162  struct queue_node *tail, *head;
163  struct rte_hash_bucket *curr_bkt, *alt_bkt;
164 
165  tail = queue;
166  head = queue + 1;
167  tail->bkt = bkt;
168  tail->prev = NULL;
169  tail->prev_slot = -1;
170 
171  /* Cuckoo bfs Search */
172  while (likely(tail != head && head <
173  queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
174  RTE_HASH_BUCKET_ENTRIES)) {
175  curr_bkt = tail->bkt;
176  for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
177  if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
178  if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
179  tail, i, sig,
180  alt_hash, new_idx) == 0))
181  return 0;
182  }
183 
184  /* Enqueue new node and keep prev node info */
185  alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
186  & h->bucket_bitmask]);
187  head->bkt = alt_bkt;
188  head->prev = tail;
189  head->prev_slot = i;
190  head++;
191  }
192  tail++;
193  }
194 
195  return -ENOSPC;
196 }
#define likely(x)
#define unlikely(x)
uint32_t bucket_bitmask
static void rte_pause(void)
uint32_t hash_sig_t
Definition: rte_hash.h:67
struct rte_hash_bucket * buckets