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