DPDK  18.05.1
rte_cuckoo_hash_x86.h
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2016 Intel Corporation
3  */
4 
5 /* rte_cuckoo_hash_x86.h
6  * This file holds all x86 specific Cuckoo Hash functions
7  */
8 
9 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
10  * buckets around
11  */
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)
15 {
16  unsigned i, status;
17  unsigned try = 0;
18 
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
23  * bucket.
24  */
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;
31  break;
32  }
33  }
34  rte_xend();
35 
36  if (i != RTE_HASH_BUCKET_ENTRIES)
37  return 0;
38 
39  break; /* break off try loop if transaction commits */
40  } else {
41  /* If we abort we give up this cuckoo path. */
42  try++;
43  rte_pause();
44  }
45  }
46 
47  return -1;
48 }
49 
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)
52  */
53 static inline int
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)
57 {
58  unsigned try = 0;
59  unsigned status;
60  uint32_t prev_alt_bkt_idx;
61 
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;
65 
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;
76 
77  prev_alt_bkt_idx
78  = prev_bkt->sig_alt[prev_slot]
79  & h->bucket_bitmask;
80 
81  if (unlikely(&h->buckets[prev_alt_bkt_idx]
82  != curr_bkt)) {
83  rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
84  }
85 
86  /* Need to swap current/alt sig to allow later
87  * Cuckoo insert to move elements back to its
88  * primary bucket if available
89  */
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];
96 
97  curr_slot = prev_slot;
98  curr_node = prev_node;
99  curr_bkt = curr_node->bkt;
100  }
101 
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;
105 
106  rte_xend();
107 
108  return 0;
109  }
110 
111  /* If we abort we give up this cuckoo path, since most likely it's
112  * no longer valid as TSX detected data conflict
113  */
114  try++;
115  rte_pause();
116  }
117 
118  return -1;
119 }
120 
121 /*
122  * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
123  * Cuckoo
124  */
125 static inline int
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,
129  uint32_t new_idx)
130 {
131  unsigned i;
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;
135 
136  tail = queue;
137  head = queue + 1;
138  tail->bkt = bkt;
139  tail->prev = NULL;
140  tail->prev_slot = -1;
141 
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,
150  tail, i, sig,
151  alt_hash, new_idx) == 0))
152  return 0;
153  }
154 
155  /* Enqueue new node and keep prev node info */
156  alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
157  & h->bucket_bitmask]);
158  head->bkt = alt_bkt;
159  head->prev = tail;
160  head->prev_slot = i;
161  head++;
162  }
163  tail++;
164  }
165 
166  return -ENOSPC;
167 }
Generated by   doxygen 1.8.1.2