2 * hazard-pointer.c: Hazard pointer related code.
4 * (C) Copyright 2011 Novell, Inc
9 #include <mono/utils/hazard-pointer.h>
10 #include <mono/utils/mono-membar.h>
11 #include <mono/utils/mono-memory-model.h>
12 #include <mono/utils/mono-mmap.h>
13 #include <mono/utils/monobitset.h>
14 #include <mono/utils/mono-threads.h>
15 #include <mono/utils/lock-free-array-queue.h>
16 #include <mono/utils/mono-counters.h>
17 #include <mono/utils/atomic.h>
18 #include <mono/io-layer/io-layer.h>
22 MonoHazardousFreeFunc free_func;
26 /* The hazard table */
28 #define HAZARD_TABLE_MAX_SIZE 256
29 #define HAZARD_TABLE_OVERFLOW 4
31 #define HAZARD_TABLE_MAX_SIZE 16384 /* There cannot be more threads than this number. */
32 #define HAZARD_TABLE_OVERFLOW 64
35 static volatile int hazard_table_size = 0;
36 static MonoThreadHazardPointers * volatile hazard_table = NULL;
39 * Each entry is either 0 or 1, indicating whether that overflow small
42 static volatile gint32 overflow_busy [HAZARD_TABLE_OVERFLOW];
44 /* The table where we keep pointers to blocks to be freed but that
45 have to wait because they're guarded by a hazard pointer. */
46 static MonoLockFreeArrayQueue delayed_free_queue = MONO_LOCK_FREE_ARRAY_QUEUE_INIT (sizeof (DelayedFreeItem));
48 /* The table for small ID assignment */
49 static CRITICAL_SECTION small_id_mutex;
50 static int small_id_next;
51 static int highest_small_id = -1;
52 static MonoBitSet *small_id_table;
53 static int hazardous_pointer_count;
56 * Allocate a small thread id.
58 * FIXME: The biggest part of this function is very similar to
59 * domain_id_alloc() in domain.c and should be merged.
62 mono_thread_small_id_alloc (void)
66 EnterCriticalSection (&small_id_mutex);
69 small_id_table = mono_bitset_new (1, 0);
71 id = mono_bitset_find_first_unset (small_id_table, small_id_next - 1);
73 id = mono_bitset_find_first_unset (small_id_table, -1);
76 MonoBitSet *new_table;
77 if (small_id_table->size * 2 >= (1 << 16))
78 g_assert_not_reached ();
79 new_table = mono_bitset_clone (small_id_table, small_id_table->size * 2);
80 id = mono_bitset_find_first_unset (new_table, small_id_table->size - 1);
82 mono_bitset_free (small_id_table);
83 small_id_table = new_table;
86 g_assert (!mono_bitset_test_fast (small_id_table, id));
87 mono_bitset_set_fast (small_id_table, id);
90 if (small_id_next >= small_id_table->size)
93 g_assert (id < HAZARD_TABLE_MAX_SIZE);
94 if (id >= hazard_table_size) {
96 hazard_table = g_malloc0 (sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE);
97 hazard_table_size = HAZARD_TABLE_MAX_SIZE;
100 int pagesize = mono_pagesize ();
101 int num_pages = (hazard_table_size * sizeof (MonoThreadHazardPointers) + pagesize - 1) / pagesize;
103 if (hazard_table == NULL) {
104 hazard_table = mono_valloc (NULL,
105 sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE,
109 g_assert (hazard_table != NULL);
110 page_addr = (guint8*)hazard_table + num_pages * pagesize;
112 mono_mprotect (page_addr, pagesize, MONO_MMAP_READ | MONO_MMAP_WRITE);
115 hazard_table_size = num_pages * pagesize / sizeof (MonoThreadHazardPointers);
118 g_assert (id < hazard_table_size);
119 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
120 hazard_table [id].hazard_pointers [i] = NULL;
123 if (id > highest_small_id) {
124 highest_small_id = id;
125 mono_memory_write_barrier ();
128 LeaveCriticalSection (&small_id_mutex);
134 mono_thread_small_id_free (int id)
136 /* MonoBitSet operations are not atomic. */
137 EnterCriticalSection (&small_id_mutex);
139 g_assert (id >= 0 && id < small_id_table->size);
140 g_assert (mono_bitset_test_fast (small_id_table, id));
141 mono_bitset_clear_fast (small_id_table, id);
143 LeaveCriticalSection (&small_id_mutex);
147 is_pointer_hazardous (gpointer p)
150 int highest = highest_small_id;
152 g_assert (highest < hazard_table_size);
154 for (i = 0; i <= highest; ++i) {
155 for (j = 0; j < HAZARD_POINTER_COUNT; ++j) {
156 if (hazard_table [i].hazard_pointers [j] == p)
165 MonoThreadHazardPointers*
166 mono_hazard_pointer_get (void)
168 int small_id = mono_thread_info_get_small_id ();
171 static MonoThreadHazardPointers emerg_hazard_table;
172 g_warning ("Thread %p may have been prematurely finalized", (gpointer)mono_native_thread_id_get ());
173 return &emerg_hazard_table;
176 return &hazard_table [small_id];
179 /* Can be called with hp==NULL, in which case it acts as an ordinary
180 pointer fetch. It's used that way indirectly from
181 mono_jit_info_table_add(), which doesn't have to care about hazards
182 because it holds the respective domain lock. */
184 get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
189 /* Get the pointer */
191 /* If we don't have hazard pointers just return the
195 /* Make it hazardous */
196 mono_hazard_pointer_set (hp, hazard_index, p);
197 /* Check that it's still the same. If not, try
200 mono_hazard_pointer_clear (hp, hazard_index);
210 mono_hazard_pointer_save_for_signal_handler (void)
213 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
214 MonoThreadHazardPointers *hp_overflow;
216 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
217 if (hp->hazard_pointers [i])
222 for (small_id = 0; small_id < HAZARD_TABLE_OVERFLOW; ++small_id) {
223 if (!overflow_busy [small_id])
228 * If this assert fails we don't have enough overflow slots.
229 * We should contemplate adding them dynamically. If we can
230 * make mono_thread_small_id_alloc() lock-free we can just
231 * allocate them on-demand.
233 g_assert (small_id < HAZARD_TABLE_OVERFLOW);
235 if (InterlockedCompareExchange (&overflow_busy [small_id], 1, 0) != 0)
238 hp_overflow = &hazard_table [small_id];
240 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
241 g_assert (!hp_overflow->hazard_pointers [i]);
244 mono_memory_write_barrier ();
246 memset (hp, 0, sizeof (MonoThreadHazardPointers));
252 mono_hazard_pointer_restore_for_signal_handler (int small_id)
254 MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
255 MonoThreadHazardPointers *hp_overflow;
261 g_assert (small_id < HAZARD_TABLE_OVERFLOW);
262 g_assert (overflow_busy [small_id]);
264 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
265 g_assert (!hp->hazard_pointers [i]);
267 hp_overflow = &hazard_table [small_id];
271 mono_memory_write_barrier ();
273 memset (hp_overflow, 0, sizeof (MonoThreadHazardPointers));
275 mono_memory_write_barrier ();
277 overflow_busy [small_id] = 0;
281 try_free_delayed_free_item (gboolean lock_free_context)
283 DelayedFreeItem item;
284 gboolean popped = mono_lock_free_array_queue_pop (&delayed_free_queue, &item);
289 if ((lock_free_context && item.might_lock) || (is_pointer_hazardous (item.p))) {
290 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
294 item.free_func (item.p);
300 mono_thread_hazardous_free_or_queue (gpointer p, MonoHazardousFreeFunc free_func,
301 gboolean free_func_might_lock, gboolean lock_free_context)
305 if (lock_free_context)
306 g_assert (!free_func_might_lock);
307 if (free_func_might_lock)
308 g_assert (!lock_free_context);
310 /* First try to free a few entries in the delayed free
312 for (i = 0; i < 3; ++i)
313 try_free_delayed_free_item (lock_free_context);
315 /* Now see if the pointer we're freeing is hazardous. If it
316 isn't, free it. Otherwise put it in the delay list. */
317 if (is_pointer_hazardous (p)) {
318 DelayedFreeItem item = { p, free_func, free_func_might_lock };
320 ++hazardous_pointer_count;
322 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
329 mono_thread_hazardous_try_free_all (void)
331 while (try_free_delayed_free_item (FALSE))
336 mono_thread_hazardous_try_free_some (void)
339 for (i = 0; i < 10; ++i)
340 try_free_delayed_free_item (FALSE);
344 mono_thread_smr_init (void)
348 InitializeCriticalSection(&small_id_mutex);
349 mono_counters_register ("Hazardous pointers", MONO_COUNTER_JIT | MONO_COUNTER_INT, &hazardous_pointer_count);
351 for (i = 0; i < HAZARD_TABLE_OVERFLOW; ++i) {
352 int small_id = mono_thread_small_id_alloc ();
353 g_assert (small_id == i);
358 mono_thread_smr_cleanup (void)
360 mono_thread_hazardous_try_free_all ();
362 mono_lock_free_array_queue_cleanup (&delayed_free_queue);
364 /*FIXME, can't we release the small id table here?*/