Commit | Line | Data |
---|---|---|
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 | |
14 | struct rcu_ht_node; | |
15 | ||
16 | struct rcu_ht_node { | |
17 | struct rcu_ht_node *next; | |
18 | void *key; | |
19 | void *data; | |
20 | }; | |
21 | ||
22 | struct 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 |
32 | struct 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 |
46 | void *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 | */ | |
77 | int 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. */ | |
96 | retry: | |
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; |
112 | end: | |
113 | rcu_read_unlock(); | |
114 | ||
115 | return ret; | |
116 | ||
117 | /* restart loop, release and re-take the read lock to be kind to GP */ | |
118 | restart: | |
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 | 127 | void *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 | |
135 | retry: | |
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; | |
154 | end: | |
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 */ | |
163 | restart: | |
164 | rcu_read_unlock(); | |
165 | goto retry; | |
166 | } | |
167 | ||
168 | int 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. */ |
183 | void 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(); | |
190 | cut_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 | */ | |
236 | void ht_destroy(struct rcu_ht *ht) | |
237 | { | |
238 | ht_delete_all(ht); | |
239 | free(ht->tbl); | |
240 | free(ht); | |
241 | } | |
242 | ||
243 | uint32_t ht_jhash(void *key, uint32_t length, uint32_t initval) | |
ab7d5fc6 | 244 | { |
674f7a69 | 245 | return jhash(key, length, initval); |
ab7d5fc6 | 246 | } |