1 /**
2 * \file
3 * A mostly concurrent hashtable
4 *
5 * Author:
6 * Rodrigo Kumpera (kumpera@gmail.com)
7 *
8 * (C) 2014 Xamarin
9 */
10
11 #include "mono-conc-hashtable.h"
12 #include <mono/utils/hazard-pointer.h>
13
14 /* Configuration knobs. */
15
16 #define INITIAL_SIZE 32
17 #define LOAD_FACTOR 0.75f
18 #define TOMBSTONE ((gpointer)(ssize_t)-1)
19
20 typedef struct {
21 gpointer key;
22 gpointer value;
23 } key_value_pair;
24
25 typedef struct {
26 int table_size;
27 key_value_pair *kvs;
28 } conc_table;
29
30 struct _MonoConcurrentHashTable {
31 volatile conc_table *table; /* goes to HP0 */
32 GHashFunc hash_func;
33 GEqualFunc equal_func;
34 int element_count;
35 int overflow_count;
36 GDestroyNotify key_destroy_func;
37 GDestroyNotify value_destroy_func;
38 };
39
40 static conc_table*
conc_table_new(int size)41 conc_table_new (int size)
42 {
43 conc_table *res = g_new (conc_table, 1);
44 res->table_size = size;
45 res->kvs = g_new0 (key_value_pair, size);
46 return res;
47 }
48
49 static void
conc_table_free(gpointer ptr)50 conc_table_free (gpointer ptr)
51 {
52 conc_table *table = (conc_table *)ptr;
53 g_free (table->kvs);
54 g_free (table);
55 }
56
57 static void
conc_table_lf_free(conc_table * table)58 conc_table_lf_free (conc_table *table)
59 {
60 mono_thread_hazardous_try_free (table, conc_table_free);
61 }
62
63
64 /*
65 A common problem with power of two hashtables is that it leads of bad clustering when dealing
66 with aligned numbers.
67
68 The solution here is to mix the bits from two primes plus the hash itself, it produces a better spread
69 than just the numbers.
70 */
71
72 static MONO_ALWAYS_INLINE int
mix_hash(int hash)73 mix_hash (int hash)
74 {
75 return ((hash * 215497) >> 16) ^ (hash * 1823231 + hash);
76 }
77
78 static MONO_ALWAYS_INLINE void
insert_one_local(conc_table * table,GHashFunc hash_func,gpointer key,gpointer value)79 insert_one_local (conc_table *table, GHashFunc hash_func, gpointer key, gpointer value)
80 {
81 key_value_pair *kvs = table->kvs;
82 int table_mask = table->table_size - 1;
83 int hash = mix_hash (hash_func (key));
84 int i = hash & table_mask;
85
86 while (table->kvs [i].key)
87 i = (i + 1) & table_mask;
88
89 kvs [i].key = key;
90 kvs [i].value = value;
91 }
92
93 /* LOCKING: Must be called holding hash_table->mutex */
94 static void
expand_table(MonoConcurrentHashTable * hash_table)95 expand_table (MonoConcurrentHashTable *hash_table)
96 {
97 conc_table *old_table = (conc_table*)hash_table->table;
98 conc_table *new_table = conc_table_new (old_table->table_size * 2);
99 key_value_pair *kvs = old_table->kvs;
100 int i;
101
102 for (i = 0; i < old_table->table_size; ++i) {
103 if (kvs [i].key && kvs [i].key != TOMBSTONE)
104 insert_one_local (new_table, hash_table->hash_func, kvs [i].key, kvs [i].value);
105 }
106 mono_memory_barrier ();
107 hash_table->table = new_table;
108 hash_table->overflow_count = (int)(new_table->table_size * LOAD_FACTOR);
109 conc_table_lf_free (old_table);
110 }
111
112
113 MonoConcurrentHashTable*
mono_conc_hashtable_new(GHashFunc hash_func,GEqualFunc key_equal_func)114 mono_conc_hashtable_new (GHashFunc hash_func, GEqualFunc key_equal_func)
115 {
116 MonoConcurrentHashTable *res = g_new0 (MonoConcurrentHashTable, 1);
117 res->hash_func = hash_func ? hash_func : g_direct_hash;
118 res->equal_func = key_equal_func;
119 // res->equal_func = g_direct_equal;
120 res->table = conc_table_new (INITIAL_SIZE);
121 res->element_count = 0;
122 res->overflow_count = (int)(INITIAL_SIZE * LOAD_FACTOR);
123 return res;
124 }
125
126 MonoConcurrentHashTable*
mono_conc_hashtable_new_full(GHashFunc hash_func,GEqualFunc key_equal_func,GDestroyNotify key_destroy_func,GDestroyNotify value_destroy_func)127 mono_conc_hashtable_new_full (GHashFunc hash_func, GEqualFunc key_equal_func, GDestroyNotify key_destroy_func, GDestroyNotify value_destroy_func)
128 {
129 MonoConcurrentHashTable *res = mono_conc_hashtable_new (hash_func, key_equal_func);
130 res->key_destroy_func = key_destroy_func;
131 res->value_destroy_func = value_destroy_func;
132 return res;
133 }
134
135
136 void
mono_conc_hashtable_destroy(MonoConcurrentHashTable * hash_table)137 mono_conc_hashtable_destroy (MonoConcurrentHashTable *hash_table)
138 {
139 if (hash_table->key_destroy_func || hash_table->value_destroy_func) {
140 int i;
141 conc_table *table = (conc_table*)hash_table->table;
142 key_value_pair *kvs = table->kvs;
143
144 for (i = 0; i < table->table_size; ++i) {
145 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
146 if (hash_table->key_destroy_func)
147 (hash_table->key_destroy_func) (kvs [i].key);
148 if (hash_table->value_destroy_func)
149 (hash_table->value_destroy_func) (kvs [i].value);
150 }
151 }
152 }
153 conc_table_free ((gpointer)hash_table->table);
154 g_free (hash_table);
155 }
156
157 gpointer
mono_conc_hashtable_lookup(MonoConcurrentHashTable * hash_table,gpointer key)158 mono_conc_hashtable_lookup (MonoConcurrentHashTable *hash_table, gpointer key)
159 {
160 MonoThreadHazardPointers* hp;
161 conc_table *table;
162 int hash, i, table_mask;
163 key_value_pair *kvs;
164 hash = mix_hash (hash_table->hash_func (key));
165 hp = mono_hazard_pointer_get ();
166
167 retry:
168 table = (conc_table *)mono_get_hazardous_pointer ((gpointer volatile*)&hash_table->table, hp, 0);
169 table_mask = table->table_size - 1;
170 kvs = table->kvs;
171 i = hash & table_mask;
172
173 if (G_LIKELY (!hash_table->equal_func)) {
174 while (kvs [i].key) {
175 if (key == kvs [i].key) {
176 gpointer value;
177 /* The read of keys must happen before the read of values */
178 mono_memory_barrier ();
179 value = kvs [i].value;
180 /* FIXME check for NULL if we add suppport for removal */
181 mono_hazard_pointer_clear (hp, 0);
182 return value;
183 }
184 i = (i + 1) & table_mask;
185 }
186 } else {
187 GEqualFunc equal = hash_table->equal_func;
188
189 while (kvs [i].key) {
190 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
191 gpointer value;
192 /* The read of keys must happen before the read of values */
193 mono_memory_barrier ();
194 value = kvs [i].value;
195
196 /* We just read a value been deleted, try again. */
197 if (G_UNLIKELY (!value))
198 goto retry;
199
200 mono_hazard_pointer_clear (hp, 0);
201 return value;
202 }
203 i = (i + 1) & table_mask;
204 }
205 }
206
207 /* The table might have expanded and the value is now on the newer table */
208 mono_memory_barrier ();
209 if (hash_table->table != table)
210 goto retry;
211
212 mono_hazard_pointer_clear (hp, 0);
213 return NULL;
214 }
215
216 /**
217 * mono_conc_hashtable_remove:
218 * Remove a value from the hashtable. Requires external locking
219 * \returns the old value if \p key is already present or NULL
220 */
221 gpointer
mono_conc_hashtable_remove(MonoConcurrentHashTable * hash_table,gpointer key)222 mono_conc_hashtable_remove (MonoConcurrentHashTable *hash_table, gpointer key)
223 {
224 conc_table *table;
225 key_value_pair *kvs;
226 int hash, i, table_mask;
227
228 g_assert (key != NULL && key != TOMBSTONE);
229
230 hash = mix_hash (hash_table->hash_func (key));
231
232 table = (conc_table*)hash_table->table;
233 kvs = table->kvs;
234 table_mask = table->table_size - 1;
235 i = hash & table_mask;
236
237 if (!hash_table->equal_func) {
238 for (;;) {
239 if (!kvs [i].key) {
240 return NULL; /*key not found*/
241 }
242
243 if (key == kvs [i].key) {
244 gpointer value = kvs [i].value;
245 kvs [i].value = NULL;
246 mono_memory_barrier ();
247 kvs [i].key = TOMBSTONE;
248 --hash_table->element_count;
249
250 if (hash_table->key_destroy_func != NULL)
251 (*hash_table->key_destroy_func) (key);
252 if (hash_table->value_destroy_func != NULL)
253 (*hash_table->value_destroy_func) (value);
254
255 return value;
256 }
257 i = (i + 1) & table_mask;
258 }
259 } else {
260 GEqualFunc equal = hash_table->equal_func;
261 for (;;) {
262 if (!kvs [i].key) {
263 return NULL; /*key not found*/
264 }
265
266 if (kvs [i].key != TOMBSTONE && equal (key, kvs [i].key)) {
267 gpointer old_key = kvs [i].key;
268 gpointer value = kvs [i].value;
269 kvs [i].value = NULL;
270 mono_memory_barrier ();
271 kvs [i].key = TOMBSTONE;
272
273 if (hash_table->key_destroy_func != NULL)
274 (*hash_table->key_destroy_func) (old_key);
275 if (hash_table->value_destroy_func != NULL)
276 (*hash_table->value_destroy_func) (value);
277 return value;
278 }
279
280 i = (i + 1) & table_mask;
281 }
282 }
283 }
284 /**
285 * mono_conc_hashtable_insert:
286 * Insert a value into the hashtable. Requires external locking.
287 * \returns the old value if \p key is already present or NULL
288 */
289 gpointer
mono_conc_hashtable_insert(MonoConcurrentHashTable * hash_table,gpointer key,gpointer value)290 mono_conc_hashtable_insert (MonoConcurrentHashTable *hash_table, gpointer key, gpointer value)
291 {
292 conc_table *table;
293 key_value_pair *kvs;
294 int hash, i, table_mask;
295
296 g_assert (key != NULL && key != TOMBSTONE);
297 g_assert (value != NULL);
298
299 hash = mix_hash (hash_table->hash_func (key));
300
301 if (hash_table->element_count >= hash_table->overflow_count)
302 expand_table (hash_table);
303
304 table = (conc_table*)hash_table->table;
305 kvs = table->kvs;
306 table_mask = table->table_size - 1;
307 i = hash & table_mask;
308
309 if (!hash_table->equal_func) {
310 for (;;) {
311 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
312 kvs [i].value = value;
313 /* The write to values must happen after the write to keys */
314 mono_memory_barrier ();
315 kvs [i].key = key;
316 ++hash_table->element_count;
317 return NULL;
318 }
319 if (key == kvs [i].key) {
320 gpointer value = kvs [i].value;
321 return value;
322 }
323 i = (i + 1) & table_mask;
324 }
325 } else {
326 GEqualFunc equal = hash_table->equal_func;
327 for (;;) {
328 if (!kvs [i].key || kvs [i].key == TOMBSTONE) {
329 kvs [i].value = value;
330 /* The write to values must happen after the write to keys */
331 mono_memory_barrier ();
332 kvs [i].key = key;
333 ++hash_table->element_count;
334 return NULL;
335 }
336 if (equal (key, kvs [i].key)) {
337 gpointer value = kvs [i].value;
338 return value;
339 }
340 i = (i + 1) & table_mask;
341 }
342 }
343 }
344
345 /**
346 * mono_conc_hashtable_foreach:
347 * Calls \p func for each value in the hashtable. Requires external locking.
348 */
349 void
mono_conc_hashtable_foreach(MonoConcurrentHashTable * hash_table,GHFunc func,gpointer userdata)350 mono_conc_hashtable_foreach (MonoConcurrentHashTable *hash_table, GHFunc func, gpointer userdata)
351 {
352 int i;
353 conc_table *table = (conc_table*)hash_table->table;
354 key_value_pair *kvs = table->kvs;
355
356 for (i = 0; i < table->table_size; ++i) {
357 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
358 func (kvs [i].key, kvs [i].value, userdata);
359 }
360 }
361 }
362
363 /**
364 * mono_conc_hashtable_foreach_steal:
365 *
366 * Calls @func for each entry in the hashtable, if @func returns true, remove from the hashtable. Requires external locking.
367 * Same semantics as g_hash_table_foreach_steal.
368 */
369 void
mono_conc_hashtable_foreach_steal(MonoConcurrentHashTable * hash_table,GHRFunc func,gpointer userdata)370 mono_conc_hashtable_foreach_steal (MonoConcurrentHashTable *hash_table, GHRFunc func, gpointer userdata)
371 {
372 int i;
373 conc_table *table = (conc_table*)hash_table->table;
374 key_value_pair *kvs = table->kvs;
375
376 for (i = 0; i < table->table_size; ++i) {
377 if (kvs [i].key && kvs [i].key != TOMBSTONE) {
378 if (func (kvs [i].key, kvs [i].value, userdata)) {
379 kvs [i].value = NULL;
380 mono_memory_barrier ();
381 kvs [i].key = TOMBSTONE;
382 --hash_table->element_count;
383 }
384 }
385 }
386 }
387