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