mono/utils/hazard-pointer.c

   1 /*
   2  * hazard-pointer.c: Hazard pointer related code.
   3  *
   4  * (C) Copyright 2011 Novell, Inc
   5  */
   6
   7 #include <config.h>
   8
   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>
  19
  20 typedef struct {
  21         gpointer p;
  22         MonoHazardousFreeFunc free_func;
  23         gboolean might_lock;
  24 } DelayedFreeItem;
  25
  26 /* The hazard table */
  27 #if MONO_SMALL_CONFIG
  28 #define HAZARD_TABLE_MAX_SIZE   256
  29 #define HAZARD_TABLE_OVERFLOW   4
  30 #else
  31 #define HAZARD_TABLE_MAX_SIZE   16384 /* There cannot be more threads than this number. */
  32 #define HAZARD_TABLE_OVERFLOW   64
  33 #endif
  34
  35 static volatile int hazard_table_size = 0;
  36 static MonoThreadHazardPointers * volatile hazard_table = NULL;
  37
  38 /*
  39  * Each entry is either 0 or 1, indicating whether that overflow small
  40  * ID is busy.
  41  */
  42 static volatile gint32 overflow_busy [HAZARD_TABLE_OVERFLOW];
  43
  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));
  47
  48 /* The table for small ID assignment */
  49 static mono_mutex_t 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;
  54
  55 /*
  56  * Allocate a small thread id.
  57  *
  58  * FIXME: The biggest part of this function is very similar to
  59  * domain_id_alloc() in domain.c and should be merged.
  60  */
  61 int
  62 mono_thread_small_id_alloc (void)
  63 {
  64         int i, id = -1;
  65
  66         mono_mutex_lock (&small_id_mutex);
  67
  68         if (!small_id_table)
  69                 small_id_table = mono_bitset_new (1, 0);
  70
  71         id = mono_bitset_find_first_unset (small_id_table, small_id_next - 1);
  72         if (id == -1)
  73                 id = mono_bitset_find_first_unset (small_id_table, -1);
  74
  75         if (id == -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);
  81
  82                 mono_bitset_free (small_id_table);
  83                 small_id_table = new_table;
  84         }
  85
  86         g_assert (!mono_bitset_test_fast (small_id_table, id));
  87         mono_bitset_set_fast (small_id_table, id);
  88
  89         small_id_next++;
  90         if (small_id_next >= small_id_table->size)
  91                 small_id_next = 0;
  92
  93         g_assert (id < HAZARD_TABLE_MAX_SIZE);
  94         if (id >= hazard_table_size) {
  95 #if MONO_SMALL_CONFIG
  96                 hazard_table = g_malloc0 (sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE);
  97                 hazard_table_size = HAZARD_TABLE_MAX_SIZE;
  98 #else
  99                 gpointer page_addr;
 100                 int pagesize = mono_pagesize ();
 101                 int num_pages = (hazard_table_size * sizeof (MonoThreadHazardPointers) + pagesize - 1) / pagesize;
 102
 103                 if (hazard_table == NULL) {
 104                         hazard_table = mono_valloc (NULL,
 105                                 sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE,
 106                                 MONO_MMAP_NONE);
 107                 }
 108
 109                 g_assert (hazard_table != NULL);
 110                 page_addr = (guint8*)hazard_table + num_pages * pagesize;
 111
 112                 mono_mprotect (page_addr, pagesize, MONO_MMAP_READ | MONO_MMAP_WRITE);
 113
 114                 ++num_pages;
 115                 hazard_table_size = num_pages * pagesize / sizeof (MonoThreadHazardPointers);
 116
 117 #endif
 118                 g_assert (id < hazard_table_size);
 119                 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 120                         hazard_table [id].hazard_pointers [i] = NULL;
 121         }
 122
 123         if (id > highest_small_id) {
 124                 highest_small_id = id;
 125                 mono_memory_write_barrier ();
 126         }
 127
 128         mono_mutex_unlock (&small_id_mutex);
 129
 130         return id;
 131 }
 132
 133 void
 134 mono_thread_small_id_free (int id)
 135 {
 136         /* MonoBitSet operations are not atomic. */
 137         mono_mutex_lock (&small_id_mutex);
 138
 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);
 142
 143         mono_mutex_unlock (&small_id_mutex);
 144 }
 145
 146 static gboolean
 147 is_pointer_hazardous (gpointer p)
 148 {
 149         int i, j;
 150         int highest = highest_small_id;
 151
 152         g_assert (highest < hazard_table_size);
 153
 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)
 157                                 return TRUE;
 158                         LOAD_LOAD_FENCE;
 159                 }
 160         }
 161
 162         return FALSE;
 163 }
 164
 165 MonoThreadHazardPointers*
 166 mono_hazard_pointer_get (void)
 167 {
 168         int small_id = mono_thread_info_get_small_id ();
 169
 170         if (small_id < 0) {
 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;
 174         }
 175
 176         return &hazard_table [small_id];
 177 }
 178
 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. */
 183 gpointer
 184 get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
 185 {
 186         gpointer p;
 187
 188         for (;;) {
 189                 /* Get the pointer */
 190                 p = *pp;
 191                 /* If we don't have hazard pointers just return the
 192                    pointer. */
 193                 if (!hp)
 194                         return p;
 195                 /* Make it hazardous */
 196                 mono_hazard_pointer_set (hp, hazard_index, p);
 197                 /* Check that it's still the same.  If not, try
 198                    again. */
 199                 if (*pp != p) {
 200                         mono_hazard_pointer_clear (hp, hazard_index);
 201                         continue;
 202                 }
 203                 break;
 204         }
 205
 206         return p;
 207 }
 208
 209 int
 210 mono_hazard_pointer_save_for_signal_handler (void)
 211 {
 212         int small_id, i;
 213         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 214         MonoThreadHazardPointers *hp_overflow;
 215
 216         for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 217                 if (hp->hazard_pointers [i])
 218                         goto search;
 219         return -1;
 220
 221  search:
 222         for (small_id = 0; small_id < HAZARD_TABLE_OVERFLOW; ++small_id) {
 223                 if (!overflow_busy [small_id])
 224                         break;
 225         }
 226
 227         /*
 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.
 232          */
 233         g_assert (small_id < HAZARD_TABLE_OVERFLOW);
 234
 235         if (InterlockedCompareExchange (&overflow_busy [small_id], 1, 0) != 0)
 236                 goto search;
 237
 238         hp_overflow = &hazard_table [small_id];
 239
 240         for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 241                 g_assert (!hp_overflow->hazard_pointers [i]);
 242         *hp_overflow = *hp;
 243
 244         mono_memory_write_barrier ();
 245
 246         memset (hp, 0, sizeof (MonoThreadHazardPointers));
 247
 248         return small_id;
 249 }
 250
 251 void
 252 mono_hazard_pointer_restore_for_signal_handler (int small_id)
 253 {
 254         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 255         MonoThreadHazardPointers *hp_overflow;
 256         int i;
 257
 258         if (small_id < 0)
 259                 return;
 260
 261         g_assert (small_id < HAZARD_TABLE_OVERFLOW);
 262         g_assert (overflow_busy [small_id]);
 263
 264         for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 265                 g_assert (!hp->hazard_pointers [i]);
 266
 267         hp_overflow = &hazard_table [small_id];
 268
 269         *hp = *hp_overflow;
 270
 271         mono_memory_write_barrier ();
 272
 273         memset (hp_overflow, 0, sizeof (MonoThreadHazardPointers));
 274
 275         mono_memory_write_barrier ();
 276
 277         overflow_busy [small_id] = 0;
 278 }
 279
 280 static gboolean
 281 try_free_delayed_free_item (gboolean lock_free_context)
 282 {
 283         DelayedFreeItem item;
 284         gboolean popped = mono_lock_free_array_queue_pop (&delayed_free_queue, &item);
 285
 286         if (!popped)
 287                 return FALSE;
 288
 289         if ((lock_free_context && item.might_lock) || (is_pointer_hazardous (item.p))) {
 290                 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
 291                 return FALSE;
 292         }
 293
 294         item.free_func (item.p);
 295
 296         return TRUE;
 297 }
 298
 299 void
 300 mono_thread_hazardous_free_or_queue (gpointer p, MonoHazardousFreeFunc free_func,
 301                 gboolean free_func_might_lock, gboolean lock_free_context)
 302 {
 303         int i;
 304
 305         if (lock_free_context)
 306                 g_assert (!free_func_might_lock);
 307         if (free_func_might_lock)
 308                 g_assert (!lock_free_context);
 309
 310         /* First try to free a few entries in the delayed free
 311            table. */
 312         for (i = 0; i < 3; ++i)
 313                 try_free_delayed_free_item (lock_free_context);
 314
 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 };
 319
 320                 ++hazardous_pointer_count;
 321
 322                 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
 323         } else {
 324                 free_func (p);
 325         }
 326 }
 327
 328 void
 329 mono_thread_hazardous_try_free_all (void)
 330 {
 331         while (try_free_delayed_free_item (FALSE))
 332                 ;
 333 }
 334
 335 void
 336 mono_thread_hazardous_try_free_some (void)
 337 {
 338         int i;
 339         for (i = 0; i < 10; ++i)
 340                 try_free_delayed_free_item (FALSE);
 341 }
 342
 343 void
 344 mono_thread_smr_init (void)
 345 {
 346         int i;
 347
 348         mono_mutex_init_recursive(&small_id_mutex);
 349         mono_counters_register ("Hazardous pointers", MONO_COUNTER_JIT | MONO_COUNTER_INT, &hazardous_pointer_count);
 350
 351         for (i = 0; i < HAZARD_TABLE_OVERFLOW; ++i) {
 352                 int small_id = mono_thread_small_id_alloc ();
 353                 g_assert (small_id == i);
 354         }
 355 }
 356
 357 void
 358 mono_thread_smr_cleanup (void)
 359 {
 360         mono_thread_hazardous_try_free_all ();
 361
 362         mono_lock_free_array_queue_cleanup (&delayed_free_queue);
 363
 364         /*FIXME, can't we release the small id table here?*/
 365 }