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         /*
 129          * At this point the GC might not be running anymore.  We
 130          * could have been woken up by a job that was then taken by
 131          * another thread, after which the collection finished, so we
 132          * first have to successfully dequeue a job before doing
 133          * anything assuming that the collection is still ongoing.
 134          */
 135
 136         if (!workers_job_queue_num_entries)
 137                 return FALSE;
 138
 139         mono_mutex_lock (&workers_job_queue_mutex);
 140         entry = (JobQueueEntry*)workers_job_queue;
 141         if (entry) {
 142                 workers_job_queue = entry->next;
 143                 --workers_job_queue_num_entries;
 144         }
 145         mono_mutex_unlock (&workers_job_queue_mutex);
 146
 147         if (!entry)
 148                 return FALSE;
 149
 150         g_assert (sgen_collection_is_parallel ());
 151
 152         entry->func (data, entry->data);
 153         sgen_free_internal (entry, INTERNAL_MEM_JOB_QUEUE_ENTRY);
 154         return TRUE;
 155 }
 156
 157 static gboolean
 158 workers_steal (WorkerData *data, WorkerData *victim_data, gboolean lock)
 159 {
 160         SgenGrayQueue *queue = &data->private_gray_queue;
 161         int num, n;
 162
 163         g_assert (!queue->first);
 164
 165         if (!victim_data->stealable_stack_fill)
 166                 return FALSE;
 167
 168         if (lock && mono_mutex_trylock (&victim_data->stealable_stack_mutex))
 169                 return FALSE;
 170
 171         n = num = (victim_data->stealable_stack_fill + 1) / 2;
 172         /* We're stealing num entries. */
 173
 174         while (n > 0) {
 175                 int m = MIN (SGEN_GRAY_QUEUE_SECTION_SIZE, n);
 176                 n -= m;
 177
 178                 sgen_gray_object_alloc_queue_section (queue);
 179                 memcpy (queue->first->objects,
 180                                 victim_data->stealable_stack + victim_data->stealable_stack_fill - num + n,
 181                                 sizeof (char*) * m);
 182                 queue->first->end = m;
 183         }
 184
 185         victim_data->stealable_stack_fill -= num;
 186
 187         if (lock)
 188                 mono_mutex_unlock (&victim_data->stealable_stack_mutex);
 189
 190         if (data == victim_data) {
 191                 if (lock)
 192                         stat_workers_stolen_from_self_lock += num;
 193                 else
 194                         stat_workers_stolen_from_self_no_lock += num;
 195         } else {
 196                 stat_workers_stolen_from_others += num;
 197         }
 198
 199         return num != 0;
 200 }
 201
 202 static gboolean
 203 workers_get_work (WorkerData *data)
 204 {
 205         int i;
 206
 207         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 208
 209         /* Try to steal from our own stack. */
 210         if (workers_steal (data, data, TRUE))
 211                 return TRUE;
 212
 213         /* Then from the GC thread's stack. */
 214         if (workers_steal (data, &workers_gc_thread_data, TRUE))
 215                 return TRUE;
 216
 217         /* Finally, from another worker. */
 218         for (i = 0; i < workers_num; ++i) {
 219                 WorkerData *victim_data = &workers_data [i];
 220                 if (data == victim_data)
 221                         continue;
 222                 if (workers_steal (data, victim_data, TRUE))
 223                         return TRUE;
 224         }
 225
 226         /* Nobody to steal from */
 227         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 228         return FALSE;
 229 }
 230
 231 static void
 232 workers_gray_queue_share_redirect (SgenGrayQueue *queue)
 233 {
 234         GrayQueueSection *section;
 235         WorkerData *data = queue->alloc_prepare_data;
 236
 237         if (data->stealable_stack_fill) {
 238                 /*
 239                  * There are still objects in the stealable stack, so
 240                  * wake up any workers that might be sleeping
 241                  */
 242                 if (workers_gc_in_progress)
 243                         workers_wake_up_all ();
 244                 return;
 245         }
 246
 247         /* The stealable stack is empty, so fill it. */
 248         mono_mutex_lock (&data->stealable_stack_mutex);
 249
 250         while (data->stealable_stack_fill < STEALABLE_STACK_SIZE &&
 251                         (section = sgen_gray_object_dequeue_section (queue))) {
 252                 int num = MIN (section->end, STEALABLE_STACK_SIZE - data->stealable_stack_fill);
 253
 254                 memcpy (data->stealable_stack + data->stealable_stack_fill,
 255                                 section->objects + section->end - num,
 256                                 sizeof (char*) * num);
 257
 258                 section->end -= num;
 259                 data->stealable_stack_fill += num;
 260
 261                 if (section->end)
 262                         sgen_gray_object_enqueue_section (queue, section);
 263                 else
 264                         sgen_gray_object_free_queue_section (section);
 265         }
 266
 267         if (data != &workers_gc_thread_data && sgen_gray_object_queue_is_empty (queue))
 268                 workers_steal (data, data, FALSE);
 269
 270         mono_mutex_unlock (&data->stealable_stack_mutex);
 271
 272         if (workers_gc_in_progress)
 273                 workers_wake_up_all ();
 274 }
 275
 276 static mono_native_thread_return_t
 277 workers_thread_func (void *data_untyped)
 278 {
 279         WorkerData *data = data_untyped;
 280
 281         mono_thread_info_register_small_id ();
 282
 283         if (sgen_get_major_collector ()->init_worker_thread)
 284                 sgen_get_major_collector ()->init_worker_thread (data->major_collector_data);
 285
 286         sgen_gray_object_queue_init_with_alloc_prepare (&data->private_gray_queue,
 287                         workers_gray_queue_share_redirect, data);
 288
 289         for (;;) {
 290                 gboolean did_work = FALSE;
 291
 292                 while (workers_dequeue_and_do_job (data)) {
 293                         did_work = TRUE;
 294                         /* FIXME: maybe distribute the gray queue here? */
 295                 }
 296
 297                 if (workers_marking && (!sgen_gray_object_queue_is_empty (&data->private_gray_queue) || workers_get_work (data))) {
 298                         g_assert (!sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 299
 300                         while (!sgen_drain_gray_stack (&data->private_gray_queue, 32))
 301                                 workers_gray_queue_share_redirect (&data->private_gray_queue);
 302                         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
 303
 304                         sgen_gray_object_queue_init (&data->private_gray_queue);
 305
 306                         did_work = TRUE;
 307                 }
 308
 309                 if (!did_work)
 310                         workers_wait ();
 311         }
 312
 313         /* dummy return to make compilers happy */
 314         return NULL;
 315 }
 316
 317 void
 318 sgen_workers_distribute_gray_queue_sections (void)
 319 {
 320         if (!sgen_collection_is_parallel ())
 321                 return;
 322
 323         workers_gray_queue_share_redirect (&workers_distribute_gray_queue);
 324 }
 325
 326 void
 327 sgen_workers_init_distribute_gray_queue (void)
 328 {
 329         if (!sgen_collection_is_parallel ())
 330                 return;
 331
 332         sgen_gray_object_queue_init (&workers_distribute_gray_queue);
 333 }
 334
 335 void
 336 sgen_workers_init (int num_workers)
 337 {
 338         int i;
 339
 340         if (!sgen_get_major_collector ()->is_parallel)
 341                 return;
 342
 343         //g_print ("initing %d workers\n", num_workers);
 344
 345         workers_num = num_workers;
 346
 347         workers_data = sgen_alloc_internal_dynamic (sizeof (WorkerData) * num_workers, INTERNAL_MEM_WORKER_DATA);
 348         memset (workers_data, 0, sizeof (WorkerData) * num_workers);
 349
 350         MONO_SEM_INIT (&workers_waiting_sem, 0);
 351         MONO_SEM_INIT (&workers_done_sem, 0);
 352
 353         sgen_gray_object_queue_init_with_alloc_prepare (&workers_distribute_gray_queue,
 354                         workers_gray_queue_share_redirect, &workers_gc_thread_data);
 355         mono_mutex_init (&workers_gc_thread_data.stealable_stack_mutex, NULL);
 356         workers_gc_thread_data.stealable_stack_fill = 0;
 357
 358         if (sgen_get_major_collector ()->alloc_worker_data)
 359                 workers_gc_thread_data.major_collector_data = sgen_get_major_collector ()->alloc_worker_data ();
 360
 361         for (i = 0; i < workers_num; ++i) {
 362                 /* private gray queue is inited by the thread itself */
 363                 mono_mutex_init (&workers_data [i].stealable_stack_mutex, NULL);
 364                 workers_data [i].stealable_stack_fill = 0;
 365
 366                 if (sgen_get_major_collector ()->alloc_worker_data)
 367                         workers_data [i].major_collector_data = sgen_get_major_collector ()->alloc_worker_data ();
 368         }
 369
 370         LOCK_INIT (workers_job_queue_mutex);
 371
 372         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_JOB_QUEUE_ENTRY, sizeof (JobQueueEntry));
 373
 374         mono_counters_register ("Stolen from self lock", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_self_lock);
 375         mono_counters_register ("Stolen from self no lock", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_self_no_lock);
 376         mono_counters_register ("Stolen from others", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_stolen_from_others);
 377         mono_counters_register ("# workers waited", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_workers_num_waited);
 378 }
 379
 380 /* only the GC thread is allowed to start and join workers */
 381
 382 static void
 383 workers_start_worker (int index)
 384 {
 385         g_assert (index >= 0 && index < workers_num);
 386
 387         g_assert (!workers_data [index].thread);
 388         mono_native_thread_create (&workers_data [index].thread, workers_thread_func, &workers_data [index]);
 389 }
 390
 391 void
 392 sgen_workers_start_all_workers (void)
 393 {
 394         int i;
 395
 396         if (!sgen_collection_is_parallel ())
 397                 return;
 398
 399         if (sgen_get_major_collector ()->init_worker_thread)
 400                 sgen_get_major_collector ()->init_worker_thread (workers_gc_thread_data.major_collector_data);
 401
 402         g_assert (!workers_gc_in_progress);
 403         workers_gc_in_progress = TRUE;
 404         workers_marking = FALSE;
 405         workers_done_posted = 0;
 406
 407         if (workers_started) {
 408                 if (workers_num_waiting != workers_num)
 409                         g_error ("Expecting all %d sgen workers to be parked, but only %d are", workers_num, workers_num_waiting);
 410                 workers_wake_up_all ();
 411                 return;
 412         }
 413
 414         for (i = 0; i < workers_num; ++i)
 415                 workers_start_worker (i);
 416
 417         workers_started = TRUE;
 418 }
 419
 420 void
 421 sgen_workers_start_marking (void)
 422 {
 423         if (!sgen_collection_is_parallel ())
 424                 return;
 425
 426         g_assert (workers_started && workers_gc_in_progress);
 427         g_assert (!workers_marking);
 428
 429         workers_marking = TRUE;
 430
 431         workers_wake_up_all ();
 432 }
 433
 434 void
 435 sgen_workers_join (void)
 436 {
 437         int i;
 438
 439         if (!sgen_collection_is_parallel ())
 440                 return;
 441
 442         g_assert (sgen_gray_object_queue_is_empty (&workers_gc_thread_data.private_gray_queue));
 443         g_assert (sgen_gray_object_queue_is_empty (&workers_distribute_gray_queue));
 444
 445         g_assert (workers_gc_in_progress);
 446         workers_gc_in_progress = FALSE;
 447         if (workers_num_waiting == workers_num) {
 448                 /*
 449                  * All the workers might have shut down at this point
 450                  * and posted the done semaphore but we don't know it
 451                  * yet.  It's not a big deal to wake them up again -
 452                  * they'll just do one iteration of their loop trying to
 453                  * find something to do and then go back to waiting
 454                  * again.
 455                  */
 456                 workers_wake_up_all ();
 457         }
 458         MONO_SEM_WAIT (&workers_done_sem);
 459         workers_marking = FALSE;
 460
 461         if (sgen_get_major_collector ()->reset_worker_data) {
 462                 for (i = 0; i < workers_num; ++i)
 463                         sgen_get_major_collector ()->reset_worker_data (workers_data [i].major_collector_data);
 464         }
 465
 466         g_assert (workers_done_posted);
 467
 468         g_assert (!workers_gc_thread_data.stealable_stack_fill);
 469         g_assert (sgen_gray_object_queue_is_empty (&workers_gc_thread_data.private_gray_queue));
 470         for (i = 0; i < workers_num; ++i) {
 471                 g_assert (!workers_data [i].stealable_stack_fill);
 472                 g_assert (sgen_gray_object_queue_is_empty (&workers_data [i].private_gray_queue));
 473         }
 474 }
 475
 476 gboolean
 477 sgen_is_worker_thread (MonoNativeThreadId thread)
 478 {
 479         int i;
 480
 481         if (sgen_get_major_collector ()->is_worker_thread && sgen_get_major_collector ()->is_worker_thread (thread))
 482                 return TRUE;
 483
 484         for (i = 0; i < workers_num; ++i) {
 485                 if (workers_data [i].thread == thread)
 486                         return TRUE;
 487         }
 488         return FALSE;
 489 }
 490
 491 gboolean
 492 sgen_workers_is_distributed_queue (SgenGrayQueue *queue)
 493 {
 494         return queue == &workers_distribute_gray_queue;
 495 }
 496
 497 SgenGrayQueue*
 498 sgen_workers_get_distribute_gray_queue (void)
 499 {
 500         return &workers_distribute_gray_queue;
 501 }
 502
 503 void
 504 sgen_workers_reset_data (void)
 505 {
 506         if (sgen_get_major_collector ()->reset_worker_data)
 507                 sgen_get_major_collector ()->reset_worker_data (workers_gc_thread_data.major_collector_data);
 508
 509 }
 510 #endif