mono/metadata/sgen-workers.c

   1 /*
   2  * Copyright 2001-2003 Ximian, Inc
   3  * Copyright 2003-2010 Novell, Inc.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining
   6  * a copy of this software and associated documentation files (the
   7  * "Software"), to deal in the Software without restriction, including
   8  * without limitation the rights to use, copy, modify, merge, publish,
   9  * distribute, sublicense, and/or sell copies of the Software, and to
  10  * permit persons to whom the Software is furnished to do so, subject to
  11  * the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be
  14  * included in all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  20  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  21  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  22  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  */
  24
  25 #include "config.h"
  26 #ifdef HAVE_SGEN_GC
  27
  28 #include "metadata/sgen-gc.h"
  29 #include "metadata/sgen-workers.h"
  30 #include "utils/mono-counters.h"
  31
  32 static int workers_num;
  33 static WorkerData *workers_data;
  34 static WorkerData workers_gc_thread_data;
  35
  36 static SgenGrayQueue workers_distribute_gray_queue;
  37
  38 static volatile gboolean workers_gc_in_progress = FALSE;
  39 static volatile gboolean workers_marking = FALSE;
  40 static gboolean workers_started = FALSE;
  41 static volatile int workers_num_waiting = 0;
  42 static MonoSemType workers_waiting_sem;
  43 static MonoSemType workers_done_sem;
  44 static volatile int workers_done_posted = 0;
  45
  46 static volatile int workers_job_queue_num_entries = 0;
  47 static volatile JobQueueEntry *workers_job_queue = NULL;
  48 static LOCK_DECLARE (workers_job_queue_mutex);
  49
  50 static long long stat_workers_stolen_from_self_lock;
  51 static long long stat_workers_stolen_from_self_no_lock;
  52 static long long stat_workers_stolen_from_others;
  53 static long long stat_workers_num_waited;
  54
  55 static void
  56 workers_wake_up (int max)
  57 {
  58         int i;
  59
  60         for (i = 0; i < max; ++i) {
  61                 int num;
  62                 do {
  63                         num = workers_num_waiting;
  64                         if (num == 0)
  65                                 return;
  66                 } while (InterlockedCompareExchange (&workers_num_waiting, num - 1, num) != num);
  67                 MONO_SEM_POST (&workers_waiting_sem);
  68         }
  69 }
  70
  71 static void
  72 workers_wake_up_all (void)
  73 {
  74         workers_wake_up (workers_num);
  75 }
  76
  77 static void
  78 workers_wait (void)
  79 {
  80         int num;
  81         ++stat_workers_num_waited;
  82         do {
  83                 num = workers_num_waiting;
  84         } while (InterlockedCompareExchange (&workers_num_waiting, num + 1, num) != num);
  85         if (num + 1 == workers_num && !workers_gc_in_progress) {
  86                 /* Make sure the done semaphore is only posted once. */
  87                 int posted;
  88                 do {
  89                         posted = workers_done_posted;
  90                         if (posted)
  91                                 break;
  92                 } while (InterlockedCompareExchange (&workers_done_posted, 1, 0) != 0);
  93                 if (!posted)
  94                         MONO_SEM_POST (&workers_done_sem);
  95         }
  96         MONO_SEM_WAIT (&workers_waiting_sem);
  97 }
  98
  99 void
 100 sgen_workers_enqueue_job (JobFunc func, void *data)
 101 {
 102         int num_entries;
 103         JobQueueEntry *entry;
 104
 105         if (!sgen_collection_is_parallel ()) {
 106                 func (NULL, data);
 107                 return;
 108         }
 109
 110         entry = sgen_alloc_internal (INTERNAL_MEM_JOB_QUEUE_ENTRY);
 111         entry->func = func;
 112         entry->data = data;
 113
 114         mono_mutex_lock (&workers_job_queue_mutex);
 115         entry->next = workers_job_queue;
 116         workers_job_queue = entry;
 117         num_entries = ++workers_job_queue_num_entries;
 118         mono_mutex_unlock (&workers_job_queue_mutex);
 119
 120         workers_wake_up (num_entries);
 121 }
 122
 123 static gboolean
 124 workers_dequeue_and_do_job (WorkerData *data)
 125 {
 126         JobQueueEntry *entry;
 127
 128         g_assert (sgen_collection_is_parallel ());
 129
 130         if (!workers_job_queue_num_entries)
 131                 return FALSE;
 132
 133         mono_mutex_lock (&workers_job_queue_mutex);
 134         entry = (JobQueueEntry*)workers_job_queue;
 135         if (entry) {
 136                 workers_job_queue = entry->next;
 137                 --workers_job_queue_num_entries;
 138         }
 139         mono_mutex_unlock (&workers_job_queue_mutex);
 140
 141         if (!entry)
 142                 return FALSE;
 143
 144         entry->func (data, entry->data);
 145         sgen_free_internal (entry, INTERNAL_MEM_JOB_QUEUE_ENTRY);
 146         return TRUE;
 147 }
 148
 149 static gboolean
 150 workers_steal (WorkerData *data, WorkerData *victim_data, gboolean lock)
 151 {
 152         SgenGrayQueue *queue = &data->private_gray_queue;
 153         int num, n;
 154
 155         g_assert (!queue->first);
 156
 157         if (!victim_data->stealable_stack_fill)
 158                 return FALSE;
 159
 160         if (lock && mono_mutex_trylock (&victim_data->stealable_stack_mutex))
 161                 return FALSE;
 162
 163         n = num = (victim_data->stealable_stack_fill + 1) / 2;
 164         /* We're stealing num entries. */
 165
 166         while (n > 0) {
 167                 int m = MIN (SGEN_GRAY_QUEUE_SECTION_SIZE, n);
 168                 n -= m;
 169
 170                 sgen_gray_object_alloc_queue_section (queue);
 171                 memcpy (queue->first->objects,
 172                                 victim_data->stealable_stack + victim_data->stealable_stack_fill - num + n,
 173                                 sizeof (char*) * m);
 174                 queue->first->end = m;
 175         }
 176
 177         victim_data->stealable_stack_fill -= num;
 178
 179         if (lock)
 180                 mono_mutex_unlock (&victim_data->stealable_stack_mutex);
 181
 182         if (data == victim_data) {
 183                 if (lock)
 184                         stat_workers_stolen_from_self_lock += num;
 185                 else
 186                         stat_workers_stolen_from_self_no_lock += num;
 187         } else {
 188                 stat_workers_stolen_from_others += num;
 189         }
 190
 191         return num != 0;
 192 }
 193
 194 static gboolean
 195 workers_get_work (WorkerData *data)
 196 {
 197         int i;
 198
 199         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 200
 201         /* Try to steal from our own stack. */
 202         if (workers_steal (data, data, TRUE))
 203                 return TRUE;
 204
 205         /* Then from the GC thread's stack. */
 206         if (workers_steal (data, &workers_gc_thread_data, TRUE))
 207                 return TRUE;
 208
 209         /* Finally, from another worker. */
 210         for (i = 0; i < workers_num; ++i) {
 211                 WorkerData *victim_data = &workers_data [i];
 212                 if (data == victim_data)
 213                         continue;
 214                 if (workers_steal (data, victim_data, TRUE))
 215                         return TRUE;
 216         }
 217
 218         /* Nobody to steal from */
 219         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 220         return FALSE;
 221 }
 222
 223 static void
 224 workers_gray_queue_share_redirect (SgenGrayQueue *queue)
 225 {
 226         GrayQueueSection *section;
 227         WorkerData *data = queue->alloc_prepare_data;
 228
 229         if (data->stealable_stack_fill) {
 230                 /*
 231                  * There are still objects in the stealable stack, so
 232                  * wake up any workers that might be sleeping
 233                  */
 234                 if (workers_gc_in_progress)
 235                         workers_wake_up_all ();
 236                 return;
 237         }
 238
 239         /* The stealable stack is empty, so fill it. */
 240         mono_mutex_lock (&data->stealable_stack_mutex);
 241
 242         while (data->stealable_stack_fill < STEALABLE_STACK_SIZE &&
 243                         (section = sgen_gray_object_dequeue_section (queue))) {
 244                 int num = MIN (section->end, STEALABLE_STACK_SIZE - data->stealable_stack_fill);
 245
 246                 memcpy (data->stealable_stack + data->stealable_stack_fill,
 247                                 section->objects + section->end - num,
 248                                 sizeof (char*) * num);
 249
 250                 section->end -= num;
 251                 data->stealable_stack_fill += num;
 252
 253                 if (section->end)
 254                         sgen_gray_object_enqueue_section (queue, section);
 255                 else
 256                         sgen_gray_object_free_queue_section (section);
 257         }
 258
 259         if (data != &workers_gc_thread_data && sgen_gray_object_queue_is_empty (queue))
 260                 workers_steal (data, data, FALSE);
 261
 262         mono_mutex_unlock (&data->stealable_stack_mutex);
 263
 264         if (workers_gc_in_progress)
 265                 workers_wake_up_all ();
 266 }
 267
 268 static mono_native_thread_return_t
 269 workers_thread_func (void *data_untyped)
 270 {
 271         WorkerData *data = data_untyped;
 272
 273         mono_thread_info_register_small_id ();
 274
 275         if (sgen_get_major_collector ()->init_worker_thread)
 276                 sgen_get_major_collector ()->init_worker_thread (data->major_collector_data);
 277
 278         sgen_gray_object_queue_init_with_alloc_prepare (&data->private_gray_queue,
 279                         workers_gray_queue_share_redirect, data);
 280
 281         for (;;) {
 282                 gboolean did_work = FALSE;
 283
 284                 while (workers_dequeue_and_do_job (data)) {
 285                         did_work = TRUE;
 286                         /* FIXME: maybe distribute the gray queue here? */
 287                 }
 288
 289                 if (workers_marking && (!sgen_gray_object_queue_is_empty (&data->private_gray_queue) || workers_get_work (data))) {
 290                         g_assert (!sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 291
 292                         while (!sgen_drain_gray_stack (&data->private_gray_queue, 32))
 293                                 workers_gray_queue_share_redirect (&data->private_gray_queue);
 294                         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 295
 296                         sgen_gray_object_queue_init (&data->private_gray_queue);
 297
 298                         did_work = TRUE;
 299                 }
 300
 301                 if (!did_work)
 302                         workers_wait ();
 303         }
 304
 305         /* dummy return to make compilers happy */
 306         return NULL;
 307 }
 308
 309 void
 310 sgen_workers_distribute_gray_queue_sections (void)
 311 {
 312         if (!sgen_collection_is_parallel ())
 313                 return;
 314
 315         workers_gray_queue_share_redirect (&workers_distribute_gray_queue);
 316 }
 317
 318 void
 319 sgen_workers_init_distribute_gray_queue (void)
 320 {
 321         if (!sgen_collection_is_parallel ())
 322                 return;
 323
 324         sgen_gray_object_queue_init (&workers_distribute_gray_queue);
 325 }
 326
 327 void
 328 sgen_workers_init (int num_workers)
 329 {
 330         int i;
 331
 332         if (!sgen_get_major_collector ()->is_parallel)
 333                 return;
 334
 335         //g_print ("initing %d workers\n", num_workers);
 336
 337         workers_num = num_workers;
 338
 339         workers_data = sgen_alloc_internal_dynamic (sizeof (WorkerData) * num_workers, INTERNAL_MEM_WORKER_DATA);
 340         memset (workers_data, 0, sizeof (WorkerData) * num_workers);
 341
 342         MONO_SEM_INIT (&workers_waiting_sem, 0);
 343         MONO_SEM_INIT (&workers_done_sem, 0);
 344
 345         sgen_gray_object_queue_init_with_alloc_prepare (&workers_distribute_gray_queue,
 346                         workers_gray_queue_share_redirect, &workers_gc_thread_data);
 347         mono_mutex_init (&workers_gc_thread_data.stealable_stack_mutex, NULL);
 348         workers_gc_thread_data.stealable_stack_fill = 0;
 349
 350         if (sgen_get_major_collector ()->alloc_worker_data)
 351                 workers_gc_thread_data.major_collector_data = sgen_get_major_collector ()->alloc_worker_data ();
 352
 353         for (i = 0; i < workers_num; ++i) {
 354                 /* private gray queue is inited by the thread itself */
 355                 mono_mutex_init (&workers_data [i].stealable_stack_mutex, NULL);
 356                 workers_data [i].stealable_stack_fill = 0;
 357
 358                 if (sgen_get_major_collector ()->alloc_worker_data)
 359                         workers_data [i].major_collector_data = sgen_get_major_collector ()->alloc_worker_data ();
 360         }
 361
 362         LOCK_INIT (workers_job_queue_mutex);
 363
 364         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_JOB_QUEUE_ENTRY, sizeof (JobQueueEntry));
 365
 366         mono_counters_register ("Stolen from self lock", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_self_lock);
 367         mono_counters_register ("Stolen from self no lock", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_self_no_lock);
 368         mono_counters_register ("Stolen from others", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_others);
 369         mono_counters_register ("# workers waited", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_num_waited);
 370 }
 371
 372 /* only the GC thread is allowed to start and join workers */
 373
 374 static void
 375 workers_start_worker (int index)
 376 {
 377         g_assert (index >= 0 && index < workers_num);
 378
 379         g_assert (!workers_data [index].thread);
 380         mono_native_thread_create (&workers_data [index].thread, workers_thread_func, &workers_data [index]);
 381 }
 382
 383 void
 384 sgen_workers_start_all_workers (void)
 385 {
 386         int i;
 387
 388         if (!sgen_collection_is_parallel ())
 389                 return;
 390
 391         if (sgen_get_major_collector ()->init_worker_thread)
 392                 sgen_get_major_collector ()->init_worker_thread (workers_gc_thread_data.major_collector_data);
 393
 394         g_assert (!workers_gc_in_progress);
 395         workers_gc_in_progress = TRUE;
 396         workers_marking = FALSE;
 397         workers_done_posted = 0;
 398
 399         if (workers_started) {
 400                 g_assert (workers_num_waiting == workers_num);
 401                 workers_wake_up_all ();
 402                 return;
 403         }
 404
 405         for (i = 0; i < workers_num; ++i)
 406                 workers_start_worker (i);
 407
 408         workers_started = TRUE;
 409 }
 410
 411 void
 412 sgen_workers_start_marking (void)
 413 {
 414         if (!sgen_collection_is_parallel ())
 415                 return;
 416
 417         g_assert (workers_started && workers_gc_in_progress);
 418         g_assert (!workers_marking);
 419
 420         workers_marking = TRUE;
 421
 422         workers_wake_up_all ();
 423 }
 424
 425 void
 426 sgen_workers_join (void)
 427 {
 428         int i;
 429
 430         if (!sgen_collection_is_parallel ())
 431                 return;
 432
 433         g_assert (sgen_gray_object_queue_is_empty (&workers_gc_thread_data.private_gray_queue));
 434         g_assert (sgen_gray_object_queue_is_empty (&workers_distribute_gray_queue));
 435
 436         g_assert (workers_gc_in_progress);
 437         workers_gc_in_progress = FALSE;
 438         if (workers_num_waiting == workers_num) {
 439                 /*
 440                  * All the workers might have shut down at this point
 441                  * and posted the done semaphore but we don't know it
 442                  * yet.  It's not a big deal to wake them up again -
 443                  * they'll just do one iteration of their loop trying to
 444                  * find something to do and then go back to waiting
 445                  * again.
 446                  */
 447                 workers_wake_up_all ();
 448         }
 449         MONO_SEM_WAIT (&workers_done_sem);
 450         workers_marking = FALSE;
 451
 452         if (sgen_get_major_collector ()->reset_worker_data) {
 453                 for (i = 0; i < workers_num; ++i)
 454                         sgen_get_major_collector ()->reset_worker_data (workers_data [i].major_collector_data);
 455         }
 456
 457         g_assert (workers_done_posted);
 458
 459         g_assert (!workers_gc_thread_data.stealable_stack_fill);
 460         g_assert (sgen_gray_object_queue_is_empty (&workers_gc_thread_data.private_gray_queue));
 461         for (i = 0; i < workers_num; ++i) {
 462                 g_assert (!workers_data [i].stealable_stack_fill);
 463                 g_assert (sgen_gray_object_queue_is_empty (&workers_data [i].private_gray_queue));
 464         }
 465 }
 466
 467 gboolean
 468 sgen_is_worker_thread (MonoNativeThreadId thread)
 469 {
 470         int i;
 471
 472         if (sgen_get_major_collector ()->is_worker_thread && sgen_get_major_collector ()->is_worker_thread (thread))
 473                 return TRUE;
 474
 475         for (i = 0; i < workers_num; ++i) {
 476                 if (workers_data [i].thread == thread)
 477                         return TRUE;
 478         }
 479         return FALSE;
 480 }
 481
 482 gboolean
 483 sgen_workers_is_distributed_queue (SgenGrayQueue *queue)
 484 {
 485         return queue == &workers_distribute_gray_queue;
 486 }
 487
 488 SgenGrayQueue*
 489 sgen_workers_get_distribute_gray_queue (void)
 490 {
 491         return &workers_distribute_gray_queue;
 492 }
 493
 494 void
 495 sgen_workers_reset_data (void)
 496 {
 497         if (sgen_get_major_collector ()->reset_worker_data)
 498                 sgen_get_major_collector ()->reset_worker_data (workers_gc_thread_data.major_collector_data);
 499
 500 }
 501 #endif