1 /**
2 * \file
3 * Hazard pointer related code.
4 *
5 * (C) Copyright 2011 Novell, Inc
6 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
7 */
8
9 #include <config.h>
10
11 #include <string.h>
12
13 #include <mono/utils/hazard-pointer.h>
14 #include <mono/utils/mono-membar.h>
15 #include <mono/utils/mono-memory-model.h>
16 #include <mono/utils/monobitset.h>
17 #include <mono/utils/lock-free-array-queue.h>
18 #include <mono/utils/atomic.h>
19 #include <mono/utils/mono-os-mutex.h>
20 #ifdef SGEN_WITHOUT_MONO
21 #include <mono/sgen/sgen-gc.h>
22 #include <mono/sgen/sgen-client.h>
23 #else
24 #include <mono/utils/mono-mmap.h>
25 #include <mono/utils/mono-threads.h>
26 #include <mono/utils/mono-counters.h>
27 #endif
28
29 typedef struct {
30 gpointer p;
31 MonoHazardousFreeFunc free_func;
32 } DelayedFreeItem;
33
34 /* The hazard table */
35 #if MONO_SMALL_CONFIG
36 #define HAZARD_TABLE_MAX_SIZE 256
37 #define HAZARD_TABLE_OVERFLOW 4
38 #else
39 #define HAZARD_TABLE_MAX_SIZE 16384 /* There cannot be more threads than this number. */
40 #define HAZARD_TABLE_OVERFLOW 64
41 #endif
42
43 static volatile int hazard_table_size = 0;
44 static MonoThreadHazardPointers * volatile hazard_table = NULL;
45 static MonoHazardFreeQueueSizeCallback queue_size_cb;
46
47 /*
48 * Each entry is either 0 or 1, indicating whether that overflow small
49 * ID is busy.
50 */
51 static volatile gint32 overflow_busy [HAZARD_TABLE_OVERFLOW];
52
53 /* The table where we keep pointers to blocks to be freed but that
54 have to wait because they're guarded by a hazard pointer. */
55 static MonoLockFreeArrayQueue delayed_free_queue = MONO_LOCK_FREE_ARRAY_QUEUE_INIT (sizeof (DelayedFreeItem), MONO_MEM_ACCOUNT_HAZARD_POINTERS);
56
57 /* The table for small ID assignment */
58 static mono_mutex_t small_id_mutex;
59 static int small_id_next;
60 static int highest_small_id = -1;
61 static MonoBitSet *small_id_table;
62 static int hazardous_pointer_count;
63
64 /*
65 * Allocate a small thread id.
66 *
67 * FIXME: The biggest part of this function is very similar to
68 * domain_id_alloc() in domain.c and should be merged.
69 */
70 int
mono_thread_small_id_alloc(void)71 mono_thread_small_id_alloc (void)
72 {
73 int i, id = -1;
74
75 mono_os_mutex_lock (&small_id_mutex);
76
77 if (!small_id_table)
78 small_id_table = mono_bitset_new (1, 0);
79
80 id = mono_bitset_find_first_unset (small_id_table, small_id_next - 1);
81 if (id == -1)
82 id = mono_bitset_find_first_unset (small_id_table, -1);
83
84 if (id == -1) {
85 MonoBitSet *new_table;
86 if (small_id_table->size * 2 >= (1 << 16))
87 g_assert_not_reached ();
88 new_table = mono_bitset_clone (small_id_table, small_id_table->size * 2);
89 id = mono_bitset_find_first_unset (new_table, small_id_table->size - 1);
90
91 mono_bitset_free (small_id_table);
92 small_id_table = new_table;
93 }
94
95 g_assert (!mono_bitset_test_fast (small_id_table, id));
96 mono_bitset_set_fast (small_id_table, id);
97
98 small_id_next++;
99 if (small_id_next >= small_id_table->size)
100 small_id_next = 0;
101
102 g_assert (id < HAZARD_TABLE_MAX_SIZE);
103 if (id >= hazard_table_size) {
104 #if MONO_SMALL_CONFIG
105 hazard_table = g_malloc0 (sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE);
106 hazard_table_size = HAZARD_TABLE_MAX_SIZE;
107 #else
108 gpointer page_addr;
109 int pagesize = mono_pagesize ();
110 int num_pages = (hazard_table_size * sizeof (MonoThreadHazardPointers) + pagesize - 1) / pagesize;
111
112 if (hazard_table == NULL) {
113 hazard_table = (MonoThreadHazardPointers *volatile) mono_valloc (NULL,
114 sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE,
115 MONO_MMAP_NONE, MONO_MEM_ACCOUNT_HAZARD_POINTERS);
116 }
117
118 g_assert (hazard_table != NULL);
119 page_addr = (guint8*)hazard_table + num_pages * pagesize;
120
121 mono_mprotect (page_addr, pagesize, MONO_MMAP_READ | MONO_MMAP_WRITE);
122
123 ++num_pages;
124 hazard_table_size = num_pages * pagesize / sizeof (MonoThreadHazardPointers);
125
126 #endif
127 g_assert (id < hazard_table_size);
128 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
129 hazard_table [id].hazard_pointers [i] = NULL;
130 }
131
132 if (id > highest_small_id) {
133 highest_small_id = id;
134 mono_memory_write_barrier ();
135 }
136
137 mono_os_mutex_unlock (&small_id_mutex);
138
139 return id;
140 }
141
142 void
mono_thread_small_id_free(int id)143 mono_thread_small_id_free (int id)
144 {
145 /* MonoBitSet operations are not atomic. */
146 mono_os_mutex_lock (&small_id_mutex);
147
148 g_assert (id >= 0 && id < small_id_table->size);
149 g_assert (mono_bitset_test_fast (small_id_table, id));
150 mono_bitset_clear_fast (small_id_table, id);
151
152 mono_os_mutex_unlock (&small_id_mutex);
153 }
154
155 static gboolean
is_pointer_hazardous(gpointer p)156 is_pointer_hazardous (gpointer p)
157 {
158 int i, j;
159 int highest = highest_small_id;
160
161 g_assert (highest < hazard_table_size);
162
163 for (i = 0; i <= highest; ++i) {
164 for (j = 0; j < HAZARD_POINTER_COUNT; ++j) {
165 if (hazard_table [i].hazard_pointers [j] == p)
166 return TRUE;
167 LOAD_LOAD_FENCE;
168 }
169 }
170
171 return FALSE;
172 }
173
174 MonoThreadHazardPointers*
mono_hazard_pointer_get(void)175 mono_hazard_pointer_get (void)
176 {
177 int small_id = mono_thread_info_get_small_id ();
178
179 if (small_id < 0) {
180 static MonoThreadHazardPointers emerg_hazard_table;
181 g_warning ("Thread %p may have been prematurely finalized", (gpointer) (gsize) mono_native_thread_id_get ());
182 return &emerg_hazard_table;
183 }
184
185 return &hazard_table [small_id];
186 }
187
188 /* Can be called with hp==NULL, in which case it acts as an ordinary
189 pointer fetch. It's used that way indirectly from
190 mono_jit_info_table_add(), which doesn't have to care about hazards
191 because it holds the respective domain lock. */
192 gpointer
mono_get_hazardous_pointer(gpointer volatile * pp,MonoThreadHazardPointers * hp,int hazard_index)193 mono_get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
194 {
195 gpointer p;
196
197 for (;;) {
198 /* Get the pointer */
199 p = *pp;
200 /* If we don't have hazard pointers just return the
201 pointer. */
202 if (!hp)
203 return p;
204 /* Make it hazardous */
205 mono_hazard_pointer_set (hp, hazard_index, p);
206 /* Check that it's still the same. If not, try
207 again. */
208 if (*pp != p) {
209 mono_hazard_pointer_clear (hp, hazard_index);
210 continue;
211 }
212 break;
213 }
214
215 return p;
216 }
217
218 int
mono_hazard_pointer_save_for_signal_handler(void)219 mono_hazard_pointer_save_for_signal_handler (void)
220 {
221 int small_id, i;
222 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
223 MonoThreadHazardPointers *hp_overflow;
224
225 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
226 if (hp->hazard_pointers [i])
227 goto search;
228 return -1;
229
230 search:
231 for (small_id = 0; small_id < HAZARD_TABLE_OVERFLOW; ++small_id) {
232 if (!overflow_busy [small_id])
233 break;
234 }
235
236 /*
237 * If this assert fails we don't have enough overflow slots.
238 * We should contemplate adding them dynamically. If we can
239 * make mono_thread_small_id_alloc() lock-free we can just
240 * allocate them on-demand.
241 */
242 g_assert (small_id < HAZARD_TABLE_OVERFLOW);
243
244 if (mono_atomic_cas_i32 (&overflow_busy [small_id], 1, 0) != 0)
245 goto search;
246
247 hp_overflow = &hazard_table [small_id];
248
249 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
250 g_assert (!hp_overflow->hazard_pointers [i]);
251 *hp_overflow = *hp;
252
253 mono_memory_write_barrier ();
254
255 memset (hp, 0, sizeof (MonoThreadHazardPointers));
256
257 return small_id;
258 }
259
260 void
mono_hazard_pointer_restore_for_signal_handler(int small_id)261 mono_hazard_pointer_restore_for_signal_handler (int small_id)
262 {
263 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
264 MonoThreadHazardPointers *hp_overflow;
265 int i;
266
267 if (small_id < 0)
268 return;
269
270 g_assert (small_id < HAZARD_TABLE_OVERFLOW);
271 g_assert (overflow_busy [small_id]);
272
273 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
274 g_assert (!hp->hazard_pointers [i]);
275
276 hp_overflow = &hazard_table [small_id];
277
278 *hp = *hp_overflow;
279
280 mono_memory_write_barrier ();
281
282 memset (hp_overflow, 0, sizeof (MonoThreadHazardPointers));
283
284 mono_memory_write_barrier ();
285
286 overflow_busy [small_id] = 0;
287 }
288
289 /**
290 * mono_thread_hazardous_try_free:
291 * \param p the pointer to free
292 * \param free_func the function that can free the pointer
293 *
294 * If \p p is not a hazardous pointer it will be immediately freed by calling \p free_func.
295 * Otherwise it will be queued for later.
296 *
297 * Use this function if \p free_func can ALWAYS be called in the context where this function is being called.
298 *
299 * This function doesn't pump the free queue so try to accommodate a call at an appropriate time.
300 * See mono_thread_hazardous_try_free_some for when it's appropriate.
301 *
302 * \returns TRUE if \p p was free or FALSE if it was queued.
303 */
304 gboolean
mono_thread_hazardous_try_free(gpointer p,MonoHazardousFreeFunc free_func)305 mono_thread_hazardous_try_free (gpointer p, MonoHazardousFreeFunc free_func)
306 {
307 if (!is_pointer_hazardous (p)) {
308 free_func (p);
309 return TRUE;
310 } else {
311 mono_thread_hazardous_queue_free (p, free_func);
312 return FALSE;
313 }
314 }
315
316 /**
317 * mono_thread_hazardous_queue_free:
318 * \param p the pointer to free
319 * \param free_func the function that can free the pointer
320 * Queue \p p to be freed later. \p p will be freed once the hazard free queue is pumped.
321 *
322 * This function doesn't pump the free queue so try to accommodate a call at an appropriate time.
323 * See \c mono_thread_hazardous_try_free_some for when it's appropriate.
324 */
325 void
mono_thread_hazardous_queue_free(gpointer p,MonoHazardousFreeFunc free_func)326 mono_thread_hazardous_queue_free (gpointer p, MonoHazardousFreeFunc free_func)
327 {
328 DelayedFreeItem item = { p, free_func };
329
330 mono_atomic_inc_i32 (&hazardous_pointer_count);
331
332 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
333
334 guint32 queue_size = delayed_free_queue.num_used_entries;
335 if (queue_size && queue_size_cb)
336 queue_size_cb (queue_size);
337 }
338
339
340 void
mono_hazard_pointer_install_free_queue_size_callback(MonoHazardFreeQueueSizeCallback cb)341 mono_hazard_pointer_install_free_queue_size_callback (MonoHazardFreeQueueSizeCallback cb)
342 {
343 queue_size_cb = cb;
344 }
345
346 static void
try_free_delayed_free_items(guint32 limit)347 try_free_delayed_free_items (guint32 limit)
348 {
349 GArray *hazardous = NULL;
350 DelayedFreeItem item;
351 guint32 freed = 0;
352
353 // Free all the items we can and re-add the ones we can't to the queue.
354 while (mono_lock_free_array_queue_pop (&delayed_free_queue, &item)) {
355 if (is_pointer_hazardous (item.p)) {
356 if (!hazardous)
357 hazardous = g_array_sized_new (FALSE, FALSE, sizeof (DelayedFreeItem), delayed_free_queue.num_used_entries);
358
359 g_array_append_val (hazardous, item);
360 continue;
361 }
362
363 item.free_func (item.p);
364 freed++;
365
366 if (limit && freed == limit)
367 break;
368 }
369
370 if (hazardous) {
371 for (gint i = 0; i < hazardous->len; i++)
372 mono_lock_free_array_queue_push (&delayed_free_queue, &g_array_index (hazardous, DelayedFreeItem, i));
373
374 g_array_free (hazardous, TRUE);
375 }
376 }
377
378 void
mono_thread_hazardous_try_free_all(void)379 mono_thread_hazardous_try_free_all (void)
380 {
381 try_free_delayed_free_items (0);
382 }
383
384 void
mono_thread_hazardous_try_free_some(void)385 mono_thread_hazardous_try_free_some (void)
386 {
387 try_free_delayed_free_items (10);
388 }
389
390 void
mono_thread_smr_init(void)391 mono_thread_smr_init (void)
392 {
393 int i;
394
395 mono_os_mutex_init_recursive(&small_id_mutex);
396 mono_counters_register ("Hazardous pointers", MONO_COUNTER_JIT | MONO_COUNTER_INT, &hazardous_pointer_count);
397
398 for (i = 0; i < HAZARD_TABLE_OVERFLOW; ++i) {
399 int small_id = mono_thread_small_id_alloc ();
400 g_assert (small_id == i);
401 }
402 }
403
404 void
mono_thread_smr_cleanup(void)405 mono_thread_smr_cleanup (void)
406 {
407 mono_thread_hazardous_try_free_all ();
408
409 mono_lock_free_array_queue_cleanup (&delayed_free_queue);
410
411 /*FIXME, can't we release the small id table here?*/
412 }
413