urcu-ht: add correct hash, implement delete_all
[urcu.git] / urcu-ht.c
CommitLineData
2ed95849
MD
1
2#define _LGPL_SOURCE
3#include <stdlib.h>
4#include <urcu.h>
5#include <arch.h>
6#include <arch_atomic.h>
7#include <assert.h>
8#include <compiler.h>
9#include <urcu-defer.h>
10#include <errno.h>
ab7d5fc6 11#include <urcu-ht.h>
674f7a69 12#include <urcu/jhash.h>
2ed95849
MD
13
14struct rcu_ht_node;
15
16struct rcu_ht_node {
17 struct rcu_ht_node *next;
18 void *key;
19 void *data;
20};
21
22struct rcu_ht {
674f7a69 23 struct rcu_ht_node **tbl;
2ed95849
MD
24 ht_hash_fct hash_fct;
25 void (*free_fct)(void *data); /* fct to free data */
674f7a69
MD
26 struct ht_size {
27 unsigned long add;
28 unsigned long lookup;
29 } size;
2ed95849
MD
30};
31
674f7a69
MD
32struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*free_fct)(void *data),
33 unsigned long init_size)
2ed95849
MD
34{
35 struct rcu_ht *ht;
36
37 ht = calloc(1, sizeof(struct rcu_ht));
38 ht->hash_fct = hash_fct;
39 ht->free_fct = free_fct;
674f7a69
MD
40 ht->size.add = init_size;
41 ht->size.lookup = init_size;
42 ht->tbl = calloc(init_size, sizeof(struct rcu_ht_node *));
ab7d5fc6 43 return ht;
2ed95849
MD
44}
45
2ed95849
MD
46void *ht_lookup(struct rcu_ht *ht, void *key)
47{
48 unsigned long hash;
49 struct rcu_ht_node *node;
50 void *ret;
51
674f7a69 52 hash = ht->hash_fct(key) % ht->size.lookup;
2ed95849
MD
53
54 rcu_read_lock();
674f7a69 55 node = rcu_dereference(*ht->tbl[hash]);
2ed95849
MD
56 for (;;) {
57 if (likely(!node)) {
58 ret = NULL;
59 break;
60 }
61 if (node->key == key) {
62 ret = node->data;
63 break;
64 }
65 node = rcu_dereference(node->next);
66 }
67 rcu_read_unlock();
ab7d5fc6
MD
68
69 return ret;
2ed95849
MD
70}
71
72/*
73 * Will re-try until either:
74 * - The key is already there (-EEXIST)
75 * - We successfully add the key at the head of a table bucket.
76 */
77int ht_add(struct rcu_ht *ht, void *key, void *data)
78{
79 struct rcu_ht_node *node, *old_head, *new_head;
80 unsigned long hash;
81 int ret = 0;
82
83 new_head = calloc(1, sizeof(struct rcu_ht_node));
84 new_head->key = key;
85 new_head->data = data;
674f7a69 86 hash = ht->hash_fct(key) % ht->size.add;
2ed95849
MD
87
88 /* here comes the fun and tricky part.
89 * Add at the beginning with a cmpxchg.
90 * Hold a read lock between the moment the first element is read
91 * and the nodes traversal (to find duplicates). This ensures
92 * the head pointer has not been reclaimed when cmpxchg is done.
93 * Always adding at the head ensures that we would have to
94 * re-try if a new item has been added concurrently. So we ensure that
95 * we never add duplicates. */
96retry:
97 rcu_read_lock();
98
674f7a69 99 old_head = node = rcu_dereference(*ht->tbl[hash]);
2ed95849
MD
100 for (;;) {
101 if (likely(!node)) {
102 break;
103 }
104 if (node->key == key) {
105 ret = -EEXIST;
106 goto end;
107 }
108 node = rcu_dereference(node->next);
109 }
674f7a69 110 if (rcu_cmpxchg_pointer(ht->tbl[hash], old_head, new_head) != old_head)
2ed95849
MD
111 goto restart;
112end:
113 rcu_read_unlock();
114
115 return ret;
116
117 /* restart loop, release and re-take the read lock to be kind to GP */
118restart:
119 rcu_read_unlock();
120 goto retry;
121}
122
123/*
124 * Restart until we successfully remove the entry, or no entry is left
125 * ((void *)(unsigned long)-ENOENT).
126 */
ab7d5fc6 127void *ht_steal(struct rcu_ht *ht, void *key)
2ed95849
MD
128{
129 struct rcu_ht_node **prev, *node;
130 unsigned long hash;
ab7d5fc6 131 void *data;
2ed95849 132
674f7a69 133 hash = ht->hash_fct(key) % ht->size.lookup;
2ed95849
MD
134
135retry:
136 rcu_read_lock();
137
674f7a69 138 prev = ht->tbl[hash];
2ed95849
MD
139 node = rcu_dereference(*prev);
140 for (;;) {
141 if (likely(!node)) {
ab7d5fc6 142 data = (void *)(unsigned long)-ENOENT;
2ed95849
MD
143 goto end;
144 }
145 if (node->key == key) {
146 break;
147 }
148 prev = &node->next;
149 node = rcu_dereference(*prev);
150 }
151 /* Found it ! pointer to object is in "prev" */
152 if (rcu_cmpxchg_pointer(prev, node, node->next) != node)
153 goto restart;
154end:
155 rcu_read_unlock();
156
ab7d5fc6
MD
157 data = node->data;
158 call_rcu(free, node);
159
160 return data;
2ed95849
MD
161
162 /* restart loop, release and re-take the read lock to be kind to GP */
163restart:
164 rcu_read_unlock();
165 goto retry;
166}
167
168int ht_delete(struct rcu_ht *ht, void *key)
169{
ab7d5fc6 170 void *data;
2ed95849 171
ab7d5fc6
MD
172 data = ht_steal(ht, key);
173 if (data) {
174 if (ht->free_fct && data)
175 call_rcu(ht->free_fct, data);
2ed95849
MD
176 return 0;
177 } else {
178 return -ENOENT;
179 }
180}
ab7d5fc6 181
674f7a69
MD
182/* Delete all old elements. Allow concurrent writer accesses. */
183void ht_delete_all(struct rcu_ht *ht)
184{
185 unsigned long i;
186 struct rcu_ht_node **prev, *node, *inext;
187
188 for (i = 0; i < ht->size.lookup; i++) {
189 rcu_read_lock();
190cut_head:
191 prev = ht->tbl[i];
192 if (prev) {
193 /*
194 * Cut the head. After that, we own the first element.
195 */
196 node = rcu_xchg_pointer(prev, NULL);
197 } else {
198 rcu_read_unlock();
199 continue;
200 }
201 /*
202 * We manage a list shared with concurrent writers and readers.
203 * Note that a concurrent add may or may not be deleted by us,
204 * depending if it arrives before or after the head is cut.
205 * "node" points to our first node. Remove first elements
206 * iteratively.
207 */
208 for (;;) {
209 prev = &node->next;
210 inext = rcu_xchg_pointer(prev, NULL);
211 /*
212 * "node" is the first element of the list we have cut.
213 * We therefore own it, no concurrent writer may delete
214 * it. There can only be concurrent lookups. Concurrent
215 * add can only be done on a bucket head, but we've cut
216 * it already. inext is also owned by us, because we
217 * have exchanged it for "NULL". It will therefore be
218 * safe to use it after a G.P.
219 */
220 rcu_read_unlock();
221 if (node->data)
222 call_rcu(ht->free_fct, node->data);
223 call_rcu(free, node);
224 if (likely(!inext))
225 break;
226 rcu_read_lock();
227 node = inext;
228 }
229 }
230}
231
232/*
233 * Should only be called when no more concurrent readers nor writers can
234 * possibly access the table.
235 */
236void ht_destroy(struct rcu_ht *ht)
237{
238 ht_delete_all(ht);
239 free(ht->tbl);
240 free(ht);
241}
242
243uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval)
ab7d5fc6 244{
674f7a69 245 return jhash(key, length, initval);
ab7d5fc6 246}
This page took 0.048278 seconds and 4 git commands to generate.