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-memory-model.h>
  13 #include <mono/utils/mono-mmap.h>
  14 #include <mono/utils/monobitset.h>
  15 #include <mono/utils/mono-threads.h>
  16 #include <mono/utils/lock-free-array-queue.h>
  17 #include <mono/io-layer/io-layer.h>
  18
  19 typedef struct {
  20         gpointer p;
  21         MonoHazardousFreeFunc free_func;
  22 } DelayedFreeItem;
  23
  24 /* The hazard table */
  25 #if MONO_SMALL_CONFIG
  26 #define HAZARD_TABLE_MAX_SIZE   256
  27 #else
  28 #define HAZARD_TABLE_MAX_SIZE   16384 /* There cannot be more threads than this number. */
  29 #endif
  30
  31 static volatile int hazard_table_size = 0;
  32 static MonoThreadHazardPointers * volatile hazard_table = NULL;
  33
  34 /* The table where we keep pointers to blocks to be freed but that
  35    have to wait because they're guarded by a hazard pointer. */
  36 static MonoLockFreeArrayQueue delayed_free_queue = MONO_LOCK_FREE_ARRAY_QUEUE_INIT (sizeof (DelayedFreeItem));
  37
  38 /* The table for small ID assignment */
  39 static CRITICAL_SECTION small_id_mutex;
  40 static int small_id_next;
  41 static int highest_small_id = -1;
  42 static MonoBitSet *small_id_table;
  43
  44 /*
  45  * Allocate a small thread id.
  46  *
  47  * FIXME: The biggest part of this function is very similar to
  48  * domain_id_alloc() in domain.c and should be merged.
  49  */
  50 int
  51 mono_thread_small_id_alloc (void)
  52 {
  53         int i, id = -1;
  54
  55         EnterCriticalSection (&small_id_mutex);
  56
  57         if (!small_id_table)
  58                 small_id_table = mono_bitset_new (1, 0);
  59
  60         id = mono_bitset_find_first_unset (small_id_table, small_id_next);
  61         if (id == -1)
  62                 id = mono_bitset_find_first_unset (small_id_table, -1);
  63
  64         if (id == -1) {
  65                 MonoBitSet *new_table;
  66                 if (small_id_table->size * 2 >= (1 << 16))
  67                         g_assert_not_reached ();
  68                 new_table = mono_bitset_clone (small_id_table, small_id_table->size * 2);
  69                 id = mono_bitset_find_first_unset (new_table, small_id_table->size - 1);
  70
  71                 mono_bitset_free (small_id_table);
  72                 small_id_table = new_table;
  73         }
  74
  75         g_assert (!mono_bitset_test_fast (small_id_table, id));
  76         mono_bitset_set_fast (small_id_table, id);
  77
  78         small_id_next++;
  79         if (small_id_next >= small_id_table->size)
  80                 small_id_next = 0;
  81
  82         g_assert (id < HAZARD_TABLE_MAX_SIZE);
  83         if (id >= hazard_table_size) {
  84 #if MONO_SMALL_CONFIG
  85                 hazard_table = g_malloc0 (sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE);
  86                 hazard_table_size = HAZARD_TABLE_MAX_SIZE;
  87 #else
  88                 gpointer page_addr;
  89                 int pagesize = mono_pagesize ();
  90                 int num_pages = (hazard_table_size * sizeof (MonoThreadHazardPointers) + pagesize - 1) / pagesize;
  91
  92                 if (hazard_table == NULL) {
  93                         hazard_table = mono_valloc (NULL,
  94                                 sizeof (MonoThreadHazardPointers) * HAZARD_TABLE_MAX_SIZE,
  95                                 MONO_MMAP_NONE);
  96                 }
  97
  98                 g_assert (hazard_table != NULL);
  99                 page_addr = (guint8*)hazard_table + num_pages * pagesize;
 100
 101                 mono_mprotect (page_addr, pagesize, MONO_MMAP_READ | MONO_MMAP_WRITE);
 102
 103                 ++num_pages;
 104                 hazard_table_size = num_pages * pagesize / sizeof (MonoThreadHazardPointers);
 105
 106 #endif
 107                 g_assert (id < hazard_table_size);
 108                 for (i = 0; i < HAZARD_POINTER_COUNT; ++i)
 109                         hazard_table [id].hazard_pointers [i] = NULL;
 110         }
 111
 112         if (id > highest_small_id) {
 113                 highest_small_id = id;
 114                 mono_memory_write_barrier ();
 115         }
 116
 117         LeaveCriticalSection (&small_id_mutex);
 118
 119         return id;
 120 }
 121
 122 void
 123 mono_thread_small_id_free (int id)
 124 {
 125         /* MonoBitSet operations are not atomic. */
 126         EnterCriticalSection (&small_id_mutex);
 127
 128         g_assert (id >= 0 && id < small_id_table->size);
 129         g_assert (mono_bitset_test_fast (small_id_table, id));
 130         mono_bitset_clear_fast (small_id_table, id);
 131
 132         LeaveCriticalSection (&small_id_mutex);
 133 }
 134
 135 static gboolean
 136 is_pointer_hazardous (gpointer p)
 137 {
 138         int i, j;
 139         int highest = highest_small_id;
 140
 141         g_assert (highest < hazard_table_size);
 142
 143         for (i = 0; i <= highest; ++i) {
 144                 for (j = 0; j < HAZARD_POINTER_COUNT; ++j) {
 145                         if (hazard_table [i].hazard_pointers [j] == p)
 146                                 return TRUE;
 147                         LOAD_LOAD_FENCE;
 148                 }
 149         }
 150
 151         return FALSE;
 152 }
 153
 154 MonoThreadHazardPointers*
 155 mono_hazard_pointer_get (void)
 156 {
 157         int small_id = mono_thread_info_get_small_id ();
 158
 159         if (small_id < 0) {
 160                 static MonoThreadHazardPointers emerg_hazard_table;
 161                 g_warning ("Thread %p may have been prematurely finalized", (gpointer)mono_native_thread_id_get ());
 162                 return &emerg_hazard_table;
 163         }
 164
 165         return &hazard_table [small_id];
 166 }
 167
 168 /* Can be called with hp==NULL, in which case it acts as an ordinary
 169    pointer fetch.  It's used that way indirectly from
 170    mono_jit_info_table_add(), which doesn't have to care about hazards
 171    because it holds the respective domain lock. */
 172 gpointer
 173 get_hazardous_pointer (gpointer volatile *pp, MonoThreadHazardPointers *hp, int hazard_index)
 174 {
 175         gpointer p;
 176
 177         for (;;) {
 178                 /* Get the pointer */
 179                 p = *pp;
 180                 /* If we don't have hazard pointers just return the
 181                    pointer. */
 182                 if (!hp)
 183                         return p;
 184                 /* Make it hazardous */
 185                 mono_hazard_pointer_set (hp, hazard_index, p);
 186                 /* Check that it's still the same.  If not, try
 187                    again. */
 188                 if (*pp != p) {
 189                         mono_hazard_pointer_clear (hp, hazard_index);
 190                         continue;
 191                 }
 192                 break;
 193         }
 194
 195         return p;
 196 }
 197
 198 static gboolean
 199 try_free_delayed_free_item (void)
 200 {
 201         DelayedFreeItem item;
 202         gboolean popped = mono_lock_free_array_queue_pop (&delayed_free_queue, &item);
 203
 204         if (!popped)
 205                 return FALSE;
 206
 207         if (is_pointer_hazardous (item.p)) {
 208                 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
 209                 return FALSE;
 210         }
 211
 212         item.free_func (item.p);
 213
 214         return TRUE;
 215 }
 216
 217 void
 218 mono_thread_hazardous_free_or_queue (gpointer p, MonoHazardousFreeFunc free_func)
 219 {
 220         int i;
 221
 222         /* First try to free a few entries in the delayed free
 223            table. */
 224         for (i = 0; i < 3; ++i)
 225                 try_free_delayed_free_item ();
 226
 227         /* Now see if the pointer we're freeing is hazardous.  If it
 228            isn't, free it.  Otherwise put it in the delay list. */
 229         if (is_pointer_hazardous (p)) {
 230                 DelayedFreeItem item = { p, free_func };
 231
 232                 ++mono_stats.hazardous_pointer_count;
 233
 234                 mono_lock_free_array_queue_push (&delayed_free_queue, &item);
 235         } else {
 236                 free_func (p);
 237         }
 238 }
 239
 240 void
 241 mono_thread_hazardous_try_free_all (void)
 242 {
 243         while (try_free_delayed_free_item ())
 244                 ;
 245 }
 246
 247 void
 248 mono_thread_smr_init (void)
 249 {
 250         InitializeCriticalSection(&small_id_mutex);
 251 }
 252
 253 void
 254 mono_thread_smr_cleanup (void)
 255 {
 256         mono_thread_hazardous_try_free_all ();
 257
 258         mono_lock_free_array_queue_cleanup (&delayed_free_queue);
 259
 260         /*FIXME, can't we release the small id table here?*/
 261 }