3 * TODO: keys are currently assumed <= sizeof(void *). Key target never freed.
13 #include <urcu-defer.h>
15 #include <arch_atomic.h>
17 #include <urcu/jhash.h>
23 struct rcu_ht_node
*next
;
30 struct rcu_ht_node
**tbl
;
32 void (*free_fct
)(void *data
); /* fct to free data */
41 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
, void (*free_fct
)(void *data
),
42 unsigned long init_size
, uint32_t keylen
,
47 ht
= calloc(1, sizeof(struct rcu_ht
));
48 ht
->hash_fct
= hash_fct
;
49 ht
->free_fct
= free_fct
;
50 ht
->size
.add
= init_size
;
51 ht
->size
.lookup
= init_size
;
53 ht
->hashseed
= hashseed
;
54 ht
->tbl
= calloc(init_size
, sizeof(struct rcu_ht_node
*));
58 void *ht_lookup(struct rcu_ht
*ht
, void *key
)
61 struct rcu_ht_node
*node
;
64 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.lookup
;
67 node
= rcu_dereference(ht
->tbl
[hash
]);
73 if (node
->key
== key
) {
77 node
= rcu_dereference(node
->next
);
85 * Will re-try until either:
86 * - The key is already there (-EEXIST)
87 * - We successfully add the key at the head of a table bucket.
89 int ht_add(struct rcu_ht
*ht
, void *key
, void *data
)
91 struct rcu_ht_node
*node
, *old_head
, *new_head
;
95 new_head
= calloc(1, sizeof(struct rcu_ht_node
));
97 new_head
->data
= data
;
99 /* here comes the fun and tricky part.
100 * Add at the beginning with a cmpxchg.
101 * Hold a read lock between the moment the first element is read
102 * and the nodes traversal (to find duplicates). This ensures
103 * the head pointer has not been reclaimed when cmpxchg is done.
104 * Always adding at the head ensures that we would have to
105 * re-try if a new item has been added concurrently. So we ensure that
106 * we never add duplicates. */
110 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.add
;
112 old_head
= node
= rcu_dereference(ht
->tbl
[hash
]);
117 if (node
->key
== key
) {
121 node
= rcu_dereference(node
->next
);
123 new_head
->next
= old_head
;
124 if (rcu_cmpxchg_pointer(&ht
->tbl
[hash
], old_head
, new_head
) != old_head
)
131 /* restart loop, release and re-take the read lock to be kind to GP */
138 * Restart until we successfully remove the entry, or no entry is left
139 * ((void *)(unsigned long)-ENOENT).
140 * Deal with concurrent stealers by doing an extra verification pass to check
141 * that no element in the list are still pointing to the element stolen.
142 * This could happen if two concurrent steal for consecutive objects are
143 * executed. A pointer to an object being stolen could be saved by the
144 * concurrent stealer for the previous object.
145 * Also, given that in this precise scenario, another stealer can also want to
146 * delete the doubly-referenced object; use a "stolen" flag to let only one
147 * stealer delete the object.
149 void *ht_steal(struct rcu_ht
*ht
, void *key
)
151 struct rcu_ht_node
**prev
, *node
, *del_node
= NULL
;
158 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.lookup
;
160 prev
= &ht
->tbl
[hash
];
161 node
= rcu_dereference(*prev
);
170 if (node
->key
== key
) {
174 node
= rcu_dereference(*prev
);
179 * Another concurrent thread stole it ? If so, let it deal with
182 if (cmpxchg(&node
->stolen
, 0, 1) != 0)
186 /* Found it ! pointer to object is in "prev" */
187 if (rcu_cmpxchg_pointer(prev
, node
, node
->next
) == node
)
193 * From that point, we own node. Note that there can still be concurrent
194 * RCU readers using it. We can free it outside of read lock after a GP.
198 data
= del_node
->data
;
199 call_rcu(free
, del_node
);
203 data
= (void *)(unsigned long)-ENOENT
;
207 /* restart loop, release and re-take the read lock to be kind to GP */
213 int ht_delete(struct rcu_ht
*ht
, void *key
)
217 data
= ht_steal(ht
, key
);
218 if (data
&& data
!= (void *)(unsigned long)-ENOENT
) {
220 call_rcu(ht
->free_fct
, data
);
227 /* Delete all old elements. Allow concurrent writer accesses. */
228 int ht_delete_all(struct rcu_ht
*ht
)
231 struct rcu_ht_node
**prev
, *node
, *inext
;
234 for (i
= 0; i
< ht
->size
.lookup
; i
++) {
238 * Cut the head. After that, we own the first element.
240 node
= rcu_xchg_pointer(prev
, NULL
);
246 * We manage a list shared with concurrent writers and readers.
247 * Note that a concurrent add may or may not be deleted by us,
248 * depending if it arrives before or after the head is cut.
249 * "node" points to our first node. Remove first elements
256 inext
= rcu_xchg_pointer(prev
, NULL
);
258 * "node" is the first element of the list we have cut.
259 * We therefore own it, no concurrent writer may delete
260 * it. There can only be concurrent lookups. Concurrent
261 * add can only be done on a bucket head, but we've cut
262 * it already. inext is also owned by us, because we
263 * have exchanged it for "NULL". It will therefore be
264 * safe to use it after a G.P.
268 call_rcu(ht
->free_fct
, node
->data
);
269 call_rcu(free
, node
);
281 * Should only be called when no more concurrent readers nor writers can
282 * possibly access the table.
284 int ht_destroy(struct rcu_ht
*ht
)
288 ret
= ht_delete_all(ht
);
295 * Expects keys <= than pointer size to be encoded in the pointer itself.
297 uint32_t ht_jhash(void *key
, uint32_t length
, uint32_t initval
)
302 if (length
<= sizeof(void *))
306 ret
= jhash(vkey
, length
, initval
);
This page took 0.052579 seconds and 5 git commands to generate.