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/metadata/class-internals.h>
  10 #include <mono/utils/hazard-pointer.h>
  11 #include <mono/utils/mono-membar.h>
  12 #include <mono/utils/mono-mmap.h>
  13 #include <mono/utils/monobitset.h>
  14 #include <mono/utils/mono-threads.h>
  15 #include <mono/io-layer/io-layer.h>
  16
  17 typedef struct {
  18         gpointer p;
  19         MonoHazardousFreeFunc free_func;
  20 } DelayedFreeItem;
  21
  22 enum {
  23         DFE_STATE_FREE,
  24         DFE_STATE_USED,
  25         DFE_STATE_BUSY
  26 };
  27
  28 typedef struct {
  29         gint32 state;
  30         DelayedFreeItem item;
  31 } DelayedFreeEntry;
  32
  33 typedef struct _DelayedFreeChunk DelayedFreeChunk;
  34 struct _DelayedFreeChunk {
  35         DelayedFreeChunk *next;
  36         gint32 num_entries;
  37         DelayedFreeEntry entries [MONO_ZERO_LEN_ARRAY];
  38 };
  39
  40 /* The hazard table */
  41 #if MONO_SMALL_CONFIG
  42 #define HAZARD_TABLE_MAX_SIZE   256
  43 #else
  44 #define HAZARD_TABLE_MAX_SIZE   16384 /* There cannot be more threads than this number. */
  45 #endif
  46
  47 static volatile int hazard_table_size = 0;
  48 static MonoThreadHazardPointers * volatile hazard_table = NULL;
  49
  50 /* The table where we keep pointers to blocks to be freed but that
  51    have to wait because they're guarded by a hazard pointer. */
  52 static volatile gint32 num_used_delayed_free_entries;
  53 static DelayedFreeChunk *delayed_free_chunk_list;
  54
  55 /* The table for small ID assignment */
  56 static CRITICAL_SECTION small_id_mutex;
  57 static int small_id_next;
  58 static int highest_small_id = -1;
  59 static MonoBitSet *small_id_table;
  60
  61 /*
  62  * Delayed free table
  63  *
  64  * The table is a linked list of arrays (chunks).  Chunks are never
  65  * removed from the list, only added to the end, in a lock-free manner.
  66  *
  67  * Adding or removing an entry in the table is only possible at the end.
  68  * To do so, the thread first has to increment or decrement
  69  * num_used_delayed_free_entries.  The entry thus added or removed now
  70  * "belongs" to that thread.  It first CASes the state to BUSY,
  71  * writes/reads the entry, and then sets the state to USED or FREE.
  72  *
  73  * Note that it's possible that there is contention.  Some thread will
  74  * always make progress, though.
  75  *
  76  * The simplest case of contention is one thread pushing and another
  77  * thread popping the same entry.  The state is FREE at first, so the
  78  * pushing thread succeeds in setting it to BUSY.  The popping thread
  79  * will only succeed with its CAS once the state is USED, which is the
  80  * case after the pushing thread has finished pushing.
  81  */
  82
  83 static DelayedFreeChunk*
  84 alloc_delayed_free_chunk (void)
  85 {
  86         int size = mono_pagesize ();
  87         int num_entries = (size - (sizeof (DelayedFreeChunk) - sizeof (DelayedFreeEntry) * MONO_ZERO_LEN_ARRAY)) / sizeof (DelayedFreeEntry);
  88         DelayedFreeChunk *chunk = mono_valloc (0, size, MONO_MMAP_READ | MONO_MMAP_WRITE);
  89         chunk->num_entries = num_entries;
  90         return chunk;
  91 }
  92
  93 static void
  94 free_delayed_free_chunk (DelayedFreeChunk *chunk)
  95 {
  96         mono_vfree (chunk, mono_pagesize ());
  97 }
  98
  99 static DelayedFreeEntry*
 100 get_delayed_free_entry (int index)
 101 {
 102         DelayedFreeChunk *chunk;
 103
 104         g_assert (index >= 0);
 105
 106         if (!delayed_free_chunk_list) {
 107                 chunk = alloc_delayed_free_chunk ();
 108                 mono_memory_write_barrier ();
 109                 if (InterlockedCompareExchangePointer ((volatile gpointer *)&delayed_free_chunk_list, chunk, NULL) != NULL)
 110                         free_delayed_free_chunk (chunk);
 111         }
 112
 113         chunk = delayed_free_chunk_list;
 114         g_assert (chunk);
 115
 116         while (index >= chunk->num_entries) {
 117                 DelayedFreeChunk *next = chunk->next;
 118                 if (!next) {
 119                         next = alloc_delayed_free_chunk ();
 120                         mono_memory_write_barrier ();
 121                         if (InterlockedCompareExchangePointer ((volatile gpointer *) &chunk->next, next, NULL) != NULL) {
 122                                 free_delayed_free_chunk (next);
 123                                 next = chunk->next;
 124                                 g_assert (next);
 125                         }
 126                 }
 127                 index -= chunk->num_entries;
 128                 chunk = next;
 129         }
 130
 131         return &chunk->entries [index];
 132 }
 133
 134 static void
 135 delayed_free_push (DelayedFreeItem item)
 136 {
 137         int index, num_used;
 138         DelayedFreeEntry *entry;
 139
 140         do {
 141                 index = InterlockedIncrement (&num_used_delayed_free_entries) - 1;
 142                 entry = get_delayed_free_entry (index);
 143         } while (InterlockedCompareExchange (&entry->state, DFE_STATE_BUSY, DFE_STATE_FREE) != DFE_STATE_FREE);
 144
 145         mono_memory_write_barrier ();
 146
 147         entry->item = item;
 148
 149         mono_memory_write_barrier ();
 150
 151         entry->state = DFE_STATE_USED;
 152
 153         mono_memory_write_barrier ();
 154
 155         do {
 156                 num_used = num_used_delayed_free_entries;
 157                 if (num_used > index)
 158                         break;
 159         } while (InterlockedCompareExchange (&num_used_delayed_free_entries, index + 1, num_used) != num_used);
 160 }
 161
 162 static gboolean
 163 delayed_free_pop (DelayedFreeItem *item)
 164 {
 165         int index;
 166         DelayedFreeEntry *entry;
 167
 168         do {
 169                 do {
 170                         index = num_used_delayed_free_entries;
 171                         if (index == 0)
 172                                 return FALSE;
 173                 } while (InterlockedCompareExchange (&num_used_delayed_free_entries, index - 1, index) != index);
 174
 175                 entry = get_delayed_free_entry (index - 1);
 176         } while (InterlockedCompareExchange (&entry->state, DFE_STATE_BUSY, DFE_STATE_USED) != DFE_STATE_USED);
 177
 178         mono_memory_barrier ();
 179
 180         *item = entry->item;
 181
 182         mono_memory_barrier ();
 183
 184         entry->state = DFE_STATE_FREE;
 185
 186         return TRUE;
 187 }
 188
 189 /*
 190  * Allocate a small thread id.
 191  *
 192  * FIXME: The biggest part of this function is very similar to
 193  * domain_id_alloc() in domain.c and should be merged.
 194  */
 195 int
 196 mono_thread_small_id_alloc (void)
 197 {
 198         int i, id = -1;
 199
 200         EnterCriticalSection (&small_id_mutex);
 201
 202         if (!small_id_table)
 203                 small_id_table = mono_bitset_new (1, 0);
 204
 205         id = mono_bitset_find_first_unset (small_id_table, small_id_next);
 206         if (id == -1)
 207                 id = mono_bitset_find_first_unset (small_id_table, -1);
 208
 209         if (id == -1) {
 210                 MonoBitSet *new_table;
 211                 if (small_id_table->size * 2 >= (1 << 16))
 212                         g_assert_not_reached ();
 213                 new_table = mono_bitset_clone (small_id_table, small_id_table->size * 2);
 214                 id = mono_bitset_find_first_unset (new_table, small_id_table->size - 1);
 215
 216                 mono_bitset_free (small_id_table);
 217                 small_id_table = new_table;
 218         }
 219
 220         g_assert (!mono_bitset_test_fast (small_id_table, id));
 221         mono_bitset_set_fast (small_id_table, id);
 222
 223         small_id_next++;
 224         if (small_id_next >= small_id_table->size)
 225                 small_id_next = 0;
 226
 227         g_assert (id < HAZARD_TABLE_MAX_SIZE);
 228         if (id >= hazard_table_size) {
 229 #if MONO_SMALL_CONFIG
 230                 hazard_table = g_malloc0 (sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE);
 231                 hazard_table_size = HAZARD_TABLE_MAX_SIZE;
 232 #else
 233                 gpointer page_addr;
 234                 int pagesize = mono_pagesize ();
 235                 int num_pages = (hazard_table_size * sizeof (MonoThreadHazardPointers) + pagesize - 1) / pagesize;
 236
 237                 if (hazard_table == NULL) {
 238                         hazard_table = mono_valloc (NULL,
 239                                 sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE,
 240                                 MONO_MMAP_NONE);
 241                 }
 242
 243                 g_assert (hazard_table != NULL);
 244                 page_addr = (guint8*)hazard_table + num_pages * pagesize;
 245
 246                 mono_mprotect (page_addr, pagesize, MONO_MMAP_READ | MONO_MMAP_WRITE);
 247
 248                 ++num_pages;
 249                 hazard_table_size = num_pages * pagesize / sizeof (MonoThreadHazardPointers);
 250
 251 #endif
 252                 g_assert (id < hazard_table_size);
 253                 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 254                         hazard_table [id].hazard_pointers [i] = NULL;
 255         }
 256
 257         if (id > highest_small_id) {
 258                 highest_small_id = id;
 259                 mono_memory_write_barrier ();
 260         }
 261
 262         LeaveCriticalSection (&small_id_mutex);
 263
 264         return id;
 265 }
 266
 267 void
 268 mono_thread_small_id_free (int id)
 269 {
 270         /* MonoBitSet operations are not atomic. */
 271         EnterCriticalSection (&small_id_mutex);
 272
 273         g_assert (id >= 0 && id < small_id_table->size);
 274         g_assert (mono_bitset_test_fast (small_id_table, id));
 275         mono_bitset_clear_fast (small_id_table, id);
 276
 277         LeaveCriticalSection (&small_id_mutex);
 278 }
 279
 280 static gboolean
 281 is_pointer_hazardous (gpointer p)
 282 {
 283         int i;
 284         int highest = highest_small_id;
 285
 286         g_assert (highest < hazard_table_size);
 287
 288         for (i = 0; i <= highest; ++i) {
 289                 if (hazard_table [i].hazard_pointers [0] == p
 290                                 || hazard_table [i].hazard_pointers [1] == p)
 291                         return TRUE;
 292         }
 293
 294         return FALSE;
 295 }
 296
 297 MonoThreadHazardPointers*
 298 mono_hazard_pointer_get (void)
 299 {
 300         int small_id = mono_thread_info_get_small_id ();
 301
 302         if (small_id < 0) {
 303                 static MonoThreadHazardPointers emerg_hazard_table;
 304                 g_warning ("Thread %p may have been prematurely finalized", (gpointer)mono_native_thread_id_get ());
 305                 return &emerg_hazard_table;
 306         }
 307
 308         return &hazard_table [small_id];
 309 }
 310
 311 /* Can be called with hp==NULL, in which case it acts as an ordinary
 312    pointer fetch.  It's used that way indirectly from
 313    mono_jit_info_table_add(), which doesn't have to care about hazards
 314    because it holds the respective domain lock. */
 315 gpointer
 316 get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
 317 {
 318         gpointer p;
 319
 320         for (;;) {
 321                 /* Get the pointer */
 322                 p = *pp;
 323                 /* If we don't have hazard pointers just return the
 324                    pointer. */
 325                 if (!hp)
 326                         return p;
 327                 /* Make it hazardous */
 328                 mono_hazard_pointer_set (hp, hazard_index, p);
 329                 /* Check that it's still the same.  If not, try
 330                    again. */
 331                 if (*pp != p) {
 332                         mono_hazard_pointer_clear (hp, hazard_index);
 333                         continue;
 334                 }
 335                 break;
 336         }
 337
 338         return p;
 339 }
 340
 341 static gboolean
 342 try_free_delayed_free_item (void)
 343 {
 344         DelayedFreeItem item;
 345         gboolean popped = delayed_free_pop (&item);
 346
 347         if (!popped)
 348                 return FALSE;
 349
 350         if (is_pointer_hazardous (item.p)) {
 351                 delayed_free_push (item);
 352                 return FALSE;
 353         }
 354
 355         item.free_func (item.p);
 356
 357         return TRUE;
 358 }
 359
 360 void
 361 mono_thread_hazardous_free_or_queue (gpointer p, MonoHazardousFreeFunc free_func)
 362 {
 363         int i;
 364
 365         /* First try to free a few entries in the delayed free
 366            table. */
 367         for (i = 0; i < 3; ++i)
 368                 try_free_delayed_free_item ();
 369
 370         /* Now see if the pointer we're freeing is hazardous.  If it
 371            isn't, free it.  Otherwise put it in the delay list. */
 372         if (is_pointer_hazardous (p)) {
 373                 DelayedFreeItem item = { p, free_func };
 374
 375                 ++mono_stats.hazardous_pointer_count;
 376
 377                 delayed_free_push (item);
 378         } else {
 379                 free_func (p);
 380         }
 381 }
 382
 383 void
 384 mono_thread_hazardous_try_free_all (void)
 385 {
 386         while (try_free_delayed_free_item ())
 387                 ;
 388 }
 389
 390 void
 391 mono_thread_smr_init (void)
 392 {
 393         InitializeCriticalSection(&small_id_mutex);
 394 }
 395
 396 void
 397 mono_thread_smr_cleanup (void)
 398 {
 399         DelayedFreeChunk *chunk;
 400
 401         mono_thread_hazardous_try_free_all ();
 402
 403         chunk = delayed_free_chunk_list;
 404         delayed_free_chunk_list = NULL;
 405         while (chunk) {
 406                 DelayedFreeChunk *next = chunk->next;
 407                 free_delayed_free_chunk (chunk);
 408                 chunk = next;
 409         }
 410
 411         /*FIXME, can't we release the small id table here?*/
 412 }