DPDK  18.02.2
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  while (likely(curr_node->prev != NULL)) {
70  prev_node = curr_node->prev;
71  prev_bkt = prev_node->bkt;
72  prev_slot = curr_node->prev_slot;
73 
74  prev_alt_bkt_idx
75  = prev_bkt->sig_alt[prev_slot]
76  & h->bucket_bitmask;
77 
78  if (unlikely(&h->buckets[prev_alt_bkt_idx]
79  != curr_bkt)) {
80  rte_xabort(RTE_XABORT_CUCKOO_PATH_INVALIDED);
81  }
82 
83  /* Need to swap current/alt sig to allow later
84  * Cuckoo insert to move elements back to its
85  * primary bucket if available
86  */
87  curr_bkt->sig_alt[curr_slot] =
88  prev_bkt->sig_current[prev_slot];
89  curr_bkt->sig_current[curr_slot] =
90  prev_bkt->sig_alt[prev_slot];
91  curr_bkt->key_idx[curr_slot]
92  = prev_bkt->key_idx[prev_slot];
93 
94  curr_slot = prev_slot;
95  curr_node = prev_node;
96  curr_bkt = curr_node->bkt;
97  }
98 
99  curr_bkt->sig_current[curr_slot] = sig;
100  curr_bkt->sig_alt[curr_slot] = alt_hash;
101  curr_bkt->key_idx[curr_slot] = new_idx;
102 
103  rte_xend();
104 
105  return 0;
106  }
107 
108  /* If we abort we give up this cuckoo path, since most likely it's
109  * no longer valid as TSX detected data conflict
110  */
111  try++;
112  rte_pause();
113  }
114 
115  return -1;
116 }
117 
118 /*
119  * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
120  * Cuckoo
121  */
122 static inline int
123 rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h,
124  struct rte_hash_bucket *bkt,
125  hash_sig_t sig, hash_sig_t alt_hash,
126  uint32_t new_idx)
127 {
128  unsigned i;
129  struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
130  struct queue_node *tail, *head;
131  struct rte_hash_bucket *curr_bkt, *alt_bkt;
132 
133  tail = queue;
134  head = queue + 1;
135  tail->bkt = bkt;
136  tail->prev = NULL;
137  tail->prev_slot = -1;
138 
139  /* Cuckoo bfs Search */
140  while (likely(tail != head && head <
141  queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
142  RTE_HASH_BUCKET_ENTRIES)) {
143  curr_bkt = tail->bkt;
144  for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
145  if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
146  if (likely(rte_hash_cuckoo_move_insert_mw_tm(h,
147  tail, i, sig,
148  alt_hash, new_idx) == 0))
149  return 0;
150  }
151 
152  /* Enqueue new node and keep prev node info */
153  alt_bkt = &(h->buckets[curr_bkt->sig_alt[i]
154  & h->bucket_bitmask]);
155  head->bkt = alt_bkt;
156  head->prev = tail;
157  head->prev_slot = i;
158  head++;
159  }
160  tail++;
161  }
162 
163  return -ENOSPC;
164 }
Generated by   doxygen 1.8.1.2