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).
137 * Deal with concurrent stealers by verifying that there are no element
138 * in the list still pointing to the element stolen. (del_node)
140 void *ht_steal(struct rcu_ht
*ht
, void *key
)
142 struct rcu_ht_node
**prev
, *node
, *del_node
= NULL
;
149 hash
= ht
->hash_fct(key
, ht
->keylen
, ht
->hashseed
) % ht
->size
.lookup
;
151 prev
= &ht
->tbl
[hash
];
152 node
= rcu_dereference(*prev
);
158 data
= (void *)(unsigned long)-ENOENT
;
162 if (node
->key
== key
) {
166 node
= rcu_dereference(*prev
);
168 /* Found it ! pointer to object is in "prev" */
169 if (rcu_cmpxchg_pointer(prev
, node
, node
->next
) != node
)
175 * From that point, we own node. Note that there can still be concurrent
176 * RCU readers using it. We can free it outside of read lock after a GP.
181 call_rcu(free
, node
);
188 /* restart loop, release and re-take the read lock to be kind to GP */
194 int ht_delete(struct rcu_ht
*ht
, void *key
)
198 data
= ht_steal(ht
, key
);
199 if (data
&& data
!= (void *)(unsigned long)-ENOENT
) {
201 call_rcu(ht
->free_fct
, data
);
208 /* Delete all old elements. Allow concurrent writer accesses. */
209 int ht_delete_all(struct rcu_ht
*ht
)
212 struct rcu_ht_node
**prev
, *node
, *inext
;
215 for (i
= 0; i
< ht
->size
.lookup
; i
++) {
219 * Cut the head. After that, we own the first element.
221 node
= rcu_xchg_pointer(prev
, NULL
);
227 * We manage a list shared with concurrent writers and readers.
228 * Note that a concurrent add may or may not be deleted by us,
229 * depending if it arrives before or after the head is cut.
230 * "node" points to our first node. Remove first elements
237 inext
= rcu_xchg_pointer(prev
, NULL
);
239 * "node" is the first element of the list we have cut.
240 * We therefore own it, no concurrent writer may delete
241 * it. There can only be concurrent lookups. Concurrent
242 * add can only be done on a bucket head, but we've cut
243 * it already. inext is also owned by us, because we
244 * have exchanged it for "NULL". It will therefore be
245 * safe to use it after a G.P.
249 call_rcu(ht
->free_fct
, node
->data
);
250 call_rcu(free
, node
);
262 * Should only be called when no more concurrent readers nor writers can
263 * possibly access the table.
265 int ht_destroy(struct rcu_ht
*ht
)
269 ret
= ht_delete_all(ht
);
276 * Expects keys <= than pointer size to be encoded in the pointer itself.
278 uint32_t ht_jhash(void *key
, uint32_t length
, uint32_t initval
)
283 if (length
<= sizeof(void *))
287 ret
= jhash(vkey
, length
, initval
);
This page took 0.03948 seconds and 4 git commands to generate.