0bbdb5d4e8284d28e8de006cb0ea5476eb9dc7f4
3 * TODO: keys are currently assumed <= sizeof(void *). Key target never freed.
10 #include <arch_atomic.h>
13 #include <urcu-defer.h>
16 #include <urcu/jhash.h>
22 struct rcu_ht_node
*next
;
28 struct rcu_ht_node
**tbl
;
30 void (*free_fct
)(void *data
); /* fct to free data */
39 struct rcu_ht
*ht_new(ht_hash_fct hash_fct
, void (*free_fct
)(void *data
),
40 unsigned long init_size
, uint32_t keylen
,
45 ht
= calloc(1, sizeof(struct rcu_ht
));
46 ht
->hash_fct
= hash_fct
;
47 ht
->free_fct
= free_fct
;
48 ht
->size
.add
= init_size
;
49 ht
->size
.lookup
= init_size
;
51 ht
->hashseed
= hashseed
;
52 ht
->tbl
= calloc(init_size
, sizeof(struct rcu_ht_node
*));
56 void *ht_lookup(struct rcu_ht
*ht
, void *key
)
59 struct rcu_ht_node
*node
;
62 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.lookup
;
65 node
= rcu_dereference(ht
->tbl
[hash
]);
71 if (node
->key
== key
) {
75 node
= rcu_dereference(node
->next
);
83 * Will re-try until either:
84 * - The key is already there (-EEXIST)
85 * - We successfully add the key at the head of a table bucket.
87 int ht_add(struct rcu_ht
*ht
, void *key
, void *data
)
89 struct rcu_ht_node
*node
, *old_head
, *new_head
;
93 new_head
= calloc(1, sizeof(struct rcu_ht_node
));
95 new_head
->data
= data
;
96 /* here comes the fun and tricky part.
97 * Add at the beginning with a cmpxchg.
98 * Hold a read lock between the moment the first element is read
99 * and the nodes traversal (to find duplicates). This ensures
100 * the head pointer has not been reclaimed when cmpxchg is done.
101 * Always adding at the head ensures that we would have to
102 * re-try if a new item has been added concurrently. So we ensure that
103 * we never add duplicates. */
107 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.add
;
109 old_head
= node
= rcu_dereference(ht
->tbl
[hash
]);
114 if (node
->key
== key
) {
118 node
= rcu_dereference(node
->next
);
120 new_head
->next
= old_head
;
121 if (rcu_cmpxchg_pointer(&ht
->tbl
[hash
], old_head
, new_head
) != old_head
)
128 /* restart loop, release and re-take the read lock to be kind to GP */
135 * Restart until we successfully remove the entry, or no entry is left
136 * ((void *)(unsigned long)-ENOENT).
138 void *ht_steal(struct rcu_ht
*ht
, void *key
)
140 struct rcu_ht_node
**prev
, *node
;
147 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.lookup
;
149 prev
= &ht
->tbl
[hash
];
150 node
= rcu_dereference(*prev
);
153 data
= (void *)(unsigned long)-ENOENT
;
156 if (node
->key
== key
) {
160 node
= rcu_dereference(*prev
);
162 /* Found it ! pointer to object is in "prev" */
163 if (rcu_cmpxchg_pointer(prev
, node
, node
->next
) != node
)
166 /* From that point, we own node. We can free it outside of read lock */
170 call_rcu(free
, node
);
177 /* restart loop, release and re-take the read lock to be kind to GP */
183 int ht_delete(struct rcu_ht
*ht
, void *key
)
187 data
= ht_steal(ht
, key
);
188 if (data
&& data
!= (void *)(unsigned long)-ENOENT
) {
190 call_rcu(ht
->free_fct
, data
);
197 /* Delete all old elements. Allow concurrent writer accesses. */
198 int ht_delete_all(struct rcu_ht
*ht
)
201 struct rcu_ht_node
**prev
, *node
, *inext
;
204 for (i
= 0; i
< ht
->size
.lookup
; i
++) {
208 * Cut the head. After that, we own the first element.
210 node
= rcu_xchg_pointer(prev
, NULL
);
216 * We manage a list shared with concurrent writers and readers.
217 * Note that a concurrent add may or may not be deleted by us,
218 * depending if it arrives before or after the head is cut.
219 * "node" points to our first node. Remove first elements
226 inext
= rcu_xchg_pointer(prev
, NULL
);
228 * "node" is the first element of the list we have cut.
229 * We therefore own it, no concurrent writer may delete
230 * it. There can only be concurrent lookups. Concurrent
231 * add can only be done on a bucket head, but we've cut
232 * it already. inext is also owned by us, because we
233 * have exchanged it for "NULL". It will therefore be
234 * safe to use it after a G.P.
238 call_rcu(ht
->free_fct
, node
->data
);
239 call_rcu(free
, node
);
251 * Should only be called when no more concurrent readers nor writers can
252 * possibly access the table.
254 int ht_destroy(struct rcu_ht
*ht
)
258 ret
= ht_delete_all(ht
);
265 * Expects keys <= than pointer size to be encoded in the pointer itself.
267 uint32_t ht_jhash(void *key
, uint32_t length
, uint32_t initval
)
272 if (length
<= sizeof(void *))
276 ret
= jhash(vkey
, length
, initval
);
This page took 0.03574 seconds and 3 git commands to generate.