mono/utils/hazard-pointer.c

   1 /*
   2  * hazard-pointer.c: Hazard pointer related code.
   3  *
   4  * (C) Copyright 2011 Novell, Inc
   5  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   6  */
   7
   8 #include <config.h>
   9
  10 #include <string.h>
  11
  12 #include <mono/utils/hazard-pointer.h>
  13 #include <mono/utils/mono-membar.h>
  14 #include <mono/utils/mono-memory-model.h>
  15 #include <mono/utils/monobitset.h>
  16 #include <mono/utils/lock-free-array-queue.h>
  17 #include <mono/utils/atomic.h>
  18 #include <mono/utils/mono-os-mutex.h>
  19 #ifdef SGEN_WITHOUT_MONO
  20 #include <mono/sgen/sgen-gc.h>
  21 #include <mono/sgen/sgen-client.h>
  22 #else
  23 #include <mono/utils/mono-mmap.h>
  24 #include <mono/utils/mono-threads.h>
  25 #include <mono/utils/mono-counters.h>
  26 #include <mono/io-layer/io-layer.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
  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
 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
 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*
 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
 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
 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 (InterlockedCompareExchange (&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
 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  * @p: the pointer to free
 292  * @free_func: the function that can free the pointer
 293  *
 294  * If @p is not a hazardous pointer it will be immediately freed by calling @free_func.
 295  * Otherwise it will be queued for later.
 296  *
 297  * Use this function if @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  * Return: TRUE if @p was free or FALSE if it was queued.
 303  */
 304 gboolean
 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  * @p: the pointer to free
 319  * @free_func: the function that can free the pointer
 320  *
 321  * Queue @p to be freed later. @p will be freed once the hazard free queue is pumped.
 322  *
 323  * This function doesn't pump the free queue so try to accommodate a call at an appropriate time.
 324  * See mono_thread_hazardous_try_free_some for when it's appropriate.
 325  *
 326  */
 327 void
 328 mono_thread_hazardous_queue_free (gpointer p, MonoHazardousFreeFunc free_func)
 329 {
 330         DelayedFreeItem item = { p, free_func };
 331
 332         InterlockedIncrement (&hazardous_pointer_count);
 333
 334         mono_lock_free_array_queue_push (&delayed_free_queue, &item);
 335
 336         guint32 queue_size = delayed_free_queue.num_used_entries;
 337         if (queue_size && queue_size_cb)
 338                 queue_size_cb (queue_size);
 339 }
 340
 341
 342 void
 343 mono_hazard_pointer_install_free_queue_size_callback (MonoHazardFreeQueueSizeCallback cb)
 344 {
 345         queue_size_cb = cb;
 346 }
 347
 348 static void
 349 try_free_delayed_free_items (guint32 limit)
 350 {
 351         GArray *hazardous = NULL;
 352         DelayedFreeItem item;
 353         guint32 freed = 0;
 354
 355         // Free all the items we can and re-add the ones we can't to the queue.
 356         while (mono_lock_free_array_queue_pop (&delayed_free_queue, &item)) {
 357                 if (is_pointer_hazardous (item.p)) {
 358                         if (!hazardous)
 359                                 hazardous = g_array_sized_new (FALSE, FALSE, sizeof (DelayedFreeItem), delayed_free_queue.num_used_entries);
 360
 361                         g_array_append_val (hazardous, item);
 362                         continue;
 363                 }
 364
 365                 item.free_func (item.p);
 366                 freed++;
 367
 368                 if (limit && freed == limit)
 369                         break;
 370         }
 371
 372         if (hazardous) {
 373                 for (gint i = 0; i < hazardous->len; i++)
 374                         mono_lock_free_array_queue_push (&delayed_free_queue, &g_array_index (hazardous, DelayedFreeItem, i));
 375
 376                 g_array_free (hazardous, TRUE);
 377         }
 378 }
 379
 380 void
 381 mono_thread_hazardous_try_free_all (void)
 382 {
 383         try_free_delayed_free_items (0);
 384 }
 385
 386 void
 387 mono_thread_hazardous_try_free_some (void)
 388 {
 389         try_free_delayed_free_items (10);
 390 }
 391
 392 void
 393 mono_thread_smr_init (void)
 394 {
 395         int i;
 396
 397         mono_os_mutex_init_recursive(&small_id_mutex);
 398         mono_counters_register ("Hazardous pointers", MONO_COUNTER_JIT | MONO_COUNTER_INT, &hazardous_pointer_count);
 399
 400         for (i = 0; i < HAZARD_TABLE_OVERFLOW; ++i) {
 401                 int small_id = mono_thread_small_id_alloc ();
 402                 g_assert (small_id == i);
 403         }
 404 }
 405
 406 void
 407 mono_thread_smr_cleanup (void)
 408 {
 409         mono_thread_hazardous_try_free_all ();
 410
 411         mono_lock_free_array_queue_cleanup (&delayed_free_queue);
 412
 413         /*FIXME, can't we release the small id table here?*/
 414 }