Merge pull request #5714 from alexischr/update_bockbuild
[mono.git] / mono / sgen / sgen-workers.c
1 /**
2  * \file
3  * Worker threads for parallel and concurrent GC.
4  *
5  * Copyright 2001-2003 Ximian, Inc
6  * Copyright 2003-2010 Novell, Inc.
7  * Copyright (C) 2012 Xamarin Inc
8  *
9  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
10  */
11
12 #include "config.h"
13 #ifdef HAVE_SGEN_GC
14
15 #include <string.h>
16
17 #include "mono/sgen/sgen-gc.h"
18 #include "mono/sgen/sgen-workers.h"
19 #include "mono/sgen/sgen-thread-pool.h"
20 #include "mono/utils/mono-membar.h"
21 #include "mono/sgen/sgen-client.h"
22
23 static WorkerContext worker_contexts [GENERATION_MAX];
24
25 /*
26  * Allowed transitions:
27  *
28  * | from \ to          | NOT WORKING | WORKING | WORK ENQUEUED |
29  * |--------------------+-------------+---------+---------------+
30  * | NOT WORKING        | -           | -       | main / worker |
31  * | WORKING            | worker      | -       | main / worker |
32  * | WORK ENQUEUED      | -           | worker  | -             |
33  *
34  * The WORK ENQUEUED state guarantees that the worker thread will inspect the queue again at
35  * least once.  Only after looking at the queue will it go back to WORKING, and then,
36  * eventually, to NOT WORKING.  After enqueuing work the main thread transitions the state
37  * to WORK ENQUEUED.  Signalling the worker thread to wake up is only necessary if the old
38  * state was NOT WORKING.
39  */
40
41 enum {
42         STATE_NOT_WORKING,
43         STATE_WORKING,
44         STATE_WORK_ENQUEUED
45 };
46
47 #define SGEN_WORKER_MIN_SECTIONS_SIGNAL 4
48
49 static guint64 stat_workers_num_finished;
50
51 static gboolean
52 set_state (WorkerData *data, State old_state, State new_state)
53 {
54         SGEN_ASSERT (0, old_state != new_state, "Why are we transitioning to the same state?");
55         if (new_state == STATE_NOT_WORKING)
56                 SGEN_ASSERT (0, old_state == STATE_WORKING, "We can only transition to NOT WORKING from WORKING");
57         else if (new_state == STATE_WORKING)
58                 SGEN_ASSERT (0, old_state == STATE_WORK_ENQUEUED, "We can only transition to WORKING from WORK ENQUEUED");
59
60         return InterlockedCompareExchange (&data->state, new_state, old_state) == old_state;
61 }
62
63 static gboolean
64 state_is_working_or_enqueued (State state)
65 {
66         return state == STATE_WORKING || state == STATE_WORK_ENQUEUED;
67 }
68
69 static void
70 sgen_workers_ensure_awake (WorkerContext *context)
71 {
72         int i;
73         gboolean need_signal = FALSE;
74
75         /*
76          * All workers are awaken, make sure we reset the parallel context.
77          * We call this function only when starting the workers so nobody is running,
78          * or when the last worker is enqueuing preclean work. In both cases we can't
79          * have a worker working using a nopar context, which means it is safe.
80          */
81         context->idle_func_object_ops = (context->active_workers_num > 1) ? context->idle_func_object_ops_par : context->idle_func_object_ops_nopar;
82         context->workers_finished = FALSE;
83
84         for (i = 0; i < context->active_workers_num; i++) {
85                 State old_state;
86                 gboolean did_set_state;
87
88                 do {
89                         old_state = context->workers_data [i].state;
90
91                         if (old_state == STATE_WORK_ENQUEUED)
92                                 break;
93
94                         did_set_state = set_state (&context->workers_data [i], old_state, STATE_WORK_ENQUEUED);
95
96                         if (did_set_state && old_state == STATE_NOT_WORKING)
97                                 context->workers_data [i].last_start = sgen_timestamp ();
98                 } while (!did_set_state);
99
100                 if (!state_is_working_or_enqueued (old_state))
101                         need_signal = TRUE;
102         }
103
104         if (need_signal)
105                 sgen_thread_pool_idle_signal (context->thread_pool_context);
106 }
107
108 static void
109 worker_try_finish (WorkerData *data)
110 {
111         State old_state;
112         int i, working = 0;
113         WorkerContext *context = data->context;
114         gint64 last_start = data->last_start;
115
116         ++stat_workers_num_finished;
117
118         mono_os_mutex_lock (&context->finished_lock);
119
120         for (i = 0; i < context->active_workers_num; i++) {
121                 if (state_is_working_or_enqueued (context->workers_data [i].state))
122                         working++;
123         }
124
125         if (working == 1) {
126                 SgenWorkersFinishCallback callback = context->finish_callback;
127                 SGEN_ASSERT (0, context->idle_func_object_ops == context->idle_func_object_ops_nopar, "Why are we finishing with parallel context");
128                 /* We are the last one left. Enqueue preclean job if we have one and awake everybody */
129                 SGEN_ASSERT (0, data->state != STATE_NOT_WORKING, "How did we get from doing idle work to NOT WORKING without setting it ourselves?");
130                 if (callback) {
131                         context->finish_callback = NULL;
132                         callback ();
133                         context->worker_awakenings = 0;
134                         /* Make sure each worker has a chance of seeing the enqueued jobs */
135                         sgen_workers_ensure_awake (context);
136                         SGEN_ASSERT (0, data->state == STATE_WORK_ENQUEUED, "Why did we fail to set our own state to ENQUEUED");
137
138                         /*
139                          * Log to be able to get the duration of normal concurrent M&S phase.
140                          * Worker indexes are 1 based, since 0 is logically considered gc thread.
141                          */
142                         binary_protocol_worker_finish_stats (data - &context->workers_data [0] + 1, context->generation, context->forced_stop, data->major_scan_time, data->los_scan_time, data->total_time + sgen_timestamp () - last_start);
143                         goto work_available;
144                 }
145         }
146
147         do {
148                 old_state = data->state;
149
150                 SGEN_ASSERT (0, old_state != STATE_NOT_WORKING, "How did we get from doing idle work to NOT WORKING without setting it ourselves?");
151                 if (old_state == STATE_WORK_ENQUEUED)
152                         goto work_available;
153                 SGEN_ASSERT (0, old_state == STATE_WORKING, "What other possibility is there?");
154         } while (!set_state (data, old_state, STATE_NOT_WORKING));
155
156         /*
157          * If we are second to last to finish, we set the scan context to the non-parallel
158          * version so we can speed up the last worker. This helps us maintain same level
159          * of performance as non-parallel mode even if we fail to distribute work properly.
160          */
161         if (working == 2)
162                 context->idle_func_object_ops = context->idle_func_object_ops_nopar;
163
164         context->workers_finished = TRUE;
165         mono_os_mutex_unlock (&context->finished_lock);
166
167         data->total_time += (sgen_timestamp () - last_start);
168         binary_protocol_worker_finish_stats (data - &context->workers_data [0] + 1, context->generation, context->forced_stop, data->major_scan_time, data->los_scan_time, data->total_time);
169
170         sgen_gray_object_queue_trim_free_list (&data->private_gray_queue);
171         return;
172
173 work_available:
174         mono_os_mutex_unlock (&context->finished_lock);
175 }
176
177 void
178 sgen_workers_enqueue_job (int generation, SgenThreadPoolJob *job, gboolean enqueue)
179 {
180         if (!enqueue) {
181                 job->func (NULL, job);
182                 sgen_thread_pool_job_free (job);
183                 return;
184         }
185
186         sgen_thread_pool_job_enqueue (worker_contexts [generation].thread_pool_context, job);
187 }
188
189 static gboolean
190 workers_get_work (WorkerData *data)
191 {
192         SgenMajorCollector *major = sgen_get_major_collector ();
193         SgenMinorCollector *minor = sgen_get_minor_collector ();
194         GrayQueueSection *section;
195
196         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
197         g_assert (major->is_concurrent || minor->is_parallel);
198
199         section = sgen_section_gray_queue_dequeue (&data->context->workers_distribute_gray_queue);
200         if (section) {
201                 sgen_gray_object_enqueue_section (&data->private_gray_queue, section, major->is_parallel);
202                 return TRUE;
203         }
204
205         /* Nobody to steal from */
206         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
207         return FALSE;
208 }
209
210 static gboolean
211 workers_steal_work (WorkerData *data)
212 {
213         SgenMajorCollector *major = sgen_get_major_collector ();
214         SgenMinorCollector *minor = sgen_get_minor_collector ();
215         int generation = sgen_get_current_collection_generation ();
216         GrayQueueSection *section = NULL;
217         WorkerContext *context = data->context;
218         int i, current_worker;
219
220         if ((generation == GENERATION_OLD && !major->is_parallel) ||
221                         (generation == GENERATION_NURSERY && !minor->is_parallel))
222                 return FALSE;
223
224         /* If we're parallel, steal from other workers' private gray queues  */
225         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
226
227         current_worker = (int) (data - context->workers_data);
228
229         for (i = 1; i < context->active_workers_num && !section; i++) {
230                 int steal_worker = (current_worker + i) % context->active_workers_num;
231                 if (state_is_working_or_enqueued (context->workers_data [steal_worker].state))
232                         section = sgen_gray_object_steal_section (&context->workers_data [steal_worker].private_gray_queue);
233         }
234
235         if (section) {
236                 sgen_gray_object_enqueue_section (&data->private_gray_queue, section, TRUE);
237                 return TRUE;
238         }
239
240         /* Nobody to steal from */
241         g_assert (sgen_gray_object_queue_is_empty (&data->private_gray_queue));
242         return FALSE;
243 }
244
245 static void
246 concurrent_enqueue_check (GCObject *obj)
247 {
248         g_assert (sgen_concurrent_collection_in_progress ());
249         g_assert (!sgen_ptr_in_nursery (obj));
250         g_assert (SGEN_LOAD_VTABLE (obj));
251 }
252
253 static void
254 init_private_gray_queue (WorkerData *data)
255 {
256         sgen_gray_object_queue_init (&data->private_gray_queue,
257                         sgen_get_major_collector ()->is_concurrent ? concurrent_enqueue_check : NULL,
258                         FALSE);
259 }
260
261 static void
262 thread_pool_init_func (void *data_untyped)
263 {
264         WorkerData *data = (WorkerData *)data_untyped;
265         SgenMajorCollector *major = sgen_get_major_collector ();
266         SgenMinorCollector *minor = sgen_get_minor_collector ();
267
268         if (!major->is_concurrent && !minor->is_parallel)
269                 return;
270
271         init_private_gray_queue (data);
272
273         /* Separate WorkerData for same thread share free_block_lists */
274         if (major->is_parallel || minor->is_parallel)
275                 major->init_block_free_lists (&data->free_block_lists);
276 }
277
278 static gboolean
279 sgen_workers_are_working (WorkerContext *context)
280 {
281         int i;
282
283         for (i = 0; i < context->active_workers_num; i++) {
284                 if (state_is_working_or_enqueued (context->workers_data [i].state))
285                         return TRUE;
286         }
287         return FALSE;
288 }
289
290 static gboolean
291 continue_idle_func (void *data_untyped, int thread_pool_context)
292 {
293         if (data_untyped)
294                 return state_is_working_or_enqueued (((WorkerData*)data_untyped)->state);
295
296         /* Return if any of the threads is working in the context */
297         if (worker_contexts [GENERATION_NURSERY].workers_num && worker_contexts [GENERATION_NURSERY].thread_pool_context == thread_pool_context)
298                 return sgen_workers_are_working (&worker_contexts [GENERATION_NURSERY]);
299         if (worker_contexts [GENERATION_OLD].workers_num && worker_contexts [GENERATION_OLD].thread_pool_context == thread_pool_context)
300                 return sgen_workers_are_working (&worker_contexts [GENERATION_OLD]);
301
302         g_assert_not_reached ();
303         return FALSE;
304 }
305
306 static gboolean
307 should_work_func (void *data_untyped)
308 {
309         WorkerData *data = (WorkerData*)data_untyped;
310         WorkerContext *context = data->context;
311         int current_worker = (int) (data - context->workers_data);
312
313         return context->started && current_worker < context->active_workers_num && state_is_working_or_enqueued (data->state);
314 }
315
316 static void
317 marker_idle_func (void *data_untyped)
318 {
319         WorkerData *data = (WorkerData *)data_untyped;
320         WorkerContext *context = data->context;
321
322         SGEN_ASSERT (0, continue_idle_func (data_untyped, context->thread_pool_context), "Why are we called when we're not supposed to work?");
323
324         if (data->state == STATE_WORK_ENQUEUED) {
325                 set_state (data, STATE_WORK_ENQUEUED, STATE_WORKING);
326                 SGEN_ASSERT (0, data->state != STATE_NOT_WORKING, "How did we get from WORK ENQUEUED to NOT WORKING?");
327         }
328
329         if (!context->forced_stop && (!sgen_gray_object_queue_is_empty (&data->private_gray_queue) || workers_get_work (data) || workers_steal_work (data))) {
330                 ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (context->idle_func_object_ops, &data->private_gray_queue);
331
332                 SGEN_ASSERT (0, !sgen_gray_object_queue_is_empty (&data->private_gray_queue), "How is our gray queue empty if we just got work?");
333
334                 sgen_drain_gray_stack (ctx);
335
336                 if (data->private_gray_queue.num_sections >= SGEN_WORKER_MIN_SECTIONS_SIGNAL
337                                 && context->workers_finished && context->worker_awakenings < context->active_workers_num) {
338                         /* We bound the number of worker awakenings just to be sure */
339                         context->worker_awakenings++;
340                         mono_os_mutex_lock (&context->finished_lock);
341                         sgen_workers_ensure_awake (context);
342                         mono_os_mutex_unlock (&context->finished_lock);
343                 }
344         } else {
345                 worker_try_finish (data);
346         }
347 }
348
349 static void
350 init_distribute_gray_queue (WorkerContext *context)
351 {
352         sgen_section_gray_queue_init (&context->workers_distribute_gray_queue, TRUE,
353                         sgen_get_major_collector ()->is_concurrent ? concurrent_enqueue_check : NULL);
354 }
355
356 void
357 sgen_workers_create_context (int generation, int num_workers)
358 {
359         static gboolean stat_inited = FALSE;
360         int i;
361         WorkerData **workers_data_ptrs = (WorkerData**)sgen_alloc_internal_dynamic (num_workers * sizeof(WorkerData*), INTERNAL_MEM_WORKER_DATA, TRUE);
362         WorkerContext *context = &worker_contexts [generation];
363
364         SGEN_ASSERT (0, !context->workers_num, "We can't init the worker context for a generation twice");
365
366         mono_os_mutex_init (&context->finished_lock);
367
368         context->generation = generation;
369         context->workers_num = num_workers;
370         context->active_workers_num = num_workers;
371
372         context->workers_data = (WorkerData *)sgen_alloc_internal_dynamic (sizeof (WorkerData) * num_workers, INTERNAL_MEM_WORKER_DATA, TRUE);
373         memset (context->workers_data, 0, sizeof (WorkerData) * num_workers);
374
375         init_distribute_gray_queue (context);
376
377         for (i = 0; i < num_workers; ++i) {
378                 workers_data_ptrs [i] = &context->workers_data [i];
379                 context->workers_data [i].context = context;
380         }
381
382         context->thread_pool_context = sgen_thread_pool_create_context (num_workers, thread_pool_init_func, marker_idle_func, continue_idle_func, should_work_func, (void**)workers_data_ptrs);
383
384         if (!stat_inited) {
385                 mono_counters_register ("# workers finished", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_workers_num_finished);
386                 stat_inited = TRUE;
387         }
388 }
389
390 /* This is called with thread pool lock so no context switch can happen */
391 static gboolean
392 continue_idle_wait (int calling_context, int *threads_context)
393 {
394         WorkerContext *context;
395         int i;
396
397         if (worker_contexts [GENERATION_OLD].workers_num && calling_context == worker_contexts [GENERATION_OLD].thread_pool_context)
398                 context = &worker_contexts [GENERATION_OLD];
399         else if (worker_contexts [GENERATION_NURSERY].workers_num && calling_context == worker_contexts [GENERATION_NURSERY].thread_pool_context)
400                 context = &worker_contexts [GENERATION_NURSERY];
401         else
402                 g_assert_not_reached ();
403
404         /*
405          * We assume there are no pending jobs, since this is called only after
406          * we waited for all the jobs.
407          */
408         for (i = 0; i < context->active_workers_num; i++) {
409                 if (threads_context [i] == calling_context)
410                         return TRUE;
411         }
412
413         if (sgen_workers_have_idle_work (context->generation) && !context->forced_stop)
414                 return TRUE;
415
416         /*
417          * At this point there are no jobs to be done, and no objects to be scanned
418          * in the gray queues. We can simply asynchronously finish all the workers
419          * from the context that were not finished already (due to being stuck working
420          * in another context)
421          */
422
423         for (i = 0; i < context->active_workers_num; i++) {
424                 if (context->workers_data [i].state == STATE_WORK_ENQUEUED)
425                         set_state (&context->workers_data [i], STATE_WORK_ENQUEUED, STATE_WORKING);
426                 if (context->workers_data [i].state == STATE_WORKING)
427                         worker_try_finish (&context->workers_data [i]);
428         }
429
430         return FALSE;
431 }
432
433
434 void
435 sgen_workers_stop_all_workers (int generation)
436 {
437         WorkerContext *context = &worker_contexts [generation];
438
439         mono_os_mutex_lock (&context->finished_lock);
440         context->finish_callback = NULL;
441         mono_os_mutex_unlock (&context->finished_lock);
442
443         context->forced_stop = TRUE;
444
445         sgen_thread_pool_wait_for_all_jobs (context->thread_pool_context);
446         sgen_thread_pool_idle_wait (context->thread_pool_context, continue_idle_wait);
447         SGEN_ASSERT (0, !sgen_workers_are_working (context), "Can only signal enqueue work when in no work state");
448
449         context->started = FALSE;
450 }
451
452 void
453 sgen_workers_set_num_active_workers (int generation, int num_workers)
454 {
455         WorkerContext *context = &worker_contexts [generation];
456         if (num_workers) {
457                 SGEN_ASSERT (0, num_workers <= context->workers_num, "We can't start more workers than we initialized");
458                 context->active_workers_num = num_workers;
459         } else {
460                 context->active_workers_num = context->workers_num;
461         }
462 }
463
464 void
465 sgen_workers_start_all_workers (int generation, SgenObjectOperations *object_ops_nopar, SgenObjectOperations *object_ops_par, SgenWorkersFinishCallback callback)
466 {
467         WorkerContext *context = &worker_contexts [generation];
468         int i;
469         SGEN_ASSERT (0, !context->started, "Why are we starting to work without finishing previous cycle");
470
471         context->idle_func_object_ops_par = object_ops_par;
472         context->idle_func_object_ops_nopar = object_ops_nopar;
473         context->forced_stop = FALSE;
474         context->finish_callback = callback;
475         context->worker_awakenings = 0;
476         context->started = TRUE;
477
478         for (i = 0; i < context->active_workers_num; i++) {
479                 context->workers_data [i].major_scan_time = 0;
480                 context->workers_data [i].los_scan_time = 0;
481                 context->workers_data [i].total_time = 0;
482                 context->workers_data [i].last_start = 0;
483         }
484         mono_memory_write_barrier ();
485
486         /*
487          * We expect workers to start finishing only after all of them were awaken.
488          * Otherwise we might think that we have fewer workers and use wrong context.
489          */
490         mono_os_mutex_lock (&context->finished_lock);
491         sgen_workers_ensure_awake (context);
492         mono_os_mutex_unlock (&context->finished_lock);
493 }
494
495 void
496 sgen_workers_join (int generation)
497 {
498         WorkerContext *context = &worker_contexts [generation];
499         int i;
500
501         SGEN_ASSERT (0, !context->finish_callback, "Why are we joining concurrent mark early");
502
503         sgen_thread_pool_wait_for_all_jobs (context->thread_pool_context);
504         sgen_thread_pool_idle_wait (context->thread_pool_context, continue_idle_wait);
505         SGEN_ASSERT (0, !sgen_workers_are_working (context), "Can only signal enqueue work when in no work state");
506
507         /* At this point all the workers have stopped. */
508
509         SGEN_ASSERT (0, sgen_section_gray_queue_is_empty (&context->workers_distribute_gray_queue), "Why is there still work left to do?");
510         for (i = 0; i < context->active_workers_num; ++i)
511                 SGEN_ASSERT (0, sgen_gray_object_queue_is_empty (&context->workers_data [i].private_gray_queue), "Why is there still work left to do?");
512
513         context->started = FALSE;
514 }
515
516 /*
517  * Can only be called if the workers are not working in the
518  * context and there are no pending jobs.
519  */
520 gboolean
521 sgen_workers_have_idle_work (int generation)
522 {
523         WorkerContext *context = &worker_contexts [generation];
524         int i;
525
526         if (!sgen_section_gray_queue_is_empty (&context->workers_distribute_gray_queue))
527                 return TRUE;
528
529         for (i = 0; i < context->active_workers_num; ++i) {
530                 if (!sgen_gray_object_queue_is_empty (&context->workers_data [i].private_gray_queue))
531                         return TRUE;
532         }
533
534         return FALSE;
535 }
536
537 gboolean
538 sgen_workers_all_done (void)
539 {
540         if (worker_contexts [GENERATION_NURSERY].workers_num && sgen_workers_are_working (&worker_contexts [GENERATION_NURSERY]))
541                 return FALSE;
542         if (worker_contexts [GENERATION_OLD].workers_num && sgen_workers_are_working (&worker_contexts [GENERATION_OLD]))
543                 return FALSE;
544
545         return TRUE;
546 }
547
548 void
549 sgen_workers_assert_gray_queue_is_empty (int generation)
550 {
551         SGEN_ASSERT (0, sgen_section_gray_queue_is_empty (&worker_contexts [generation].workers_distribute_gray_queue), "Why is the workers gray queue not empty?");
552 }
553
554 void
555 sgen_workers_take_from_queue (int generation, SgenGrayQueue *queue)
556 {
557         WorkerContext *context = &worker_contexts [generation];
558
559         sgen_gray_object_spread (queue, sgen_workers_get_job_split_count (generation));
560
561         for (;;) {
562                 GrayQueueSection *section = sgen_gray_object_dequeue_section (queue);
563                 if (!section)
564                         break;
565                 sgen_section_gray_queue_enqueue (&context->workers_distribute_gray_queue, section);
566         }
567
568         SGEN_ASSERT (0, !sgen_workers_are_working (context), "We should fully populate the distribute gray queue before we start the workers");
569 }
570
571 SgenObjectOperations*
572 sgen_workers_get_idle_func_object_ops (WorkerData *worker)
573 {
574         g_assert (worker->context->idle_func_object_ops);
575         return worker->context->idle_func_object_ops;
576 }
577
578 /*
579  * If we have a single worker, splitting into multiple jobs makes no sense. With
580  * more than one worker, we split into a larger number of jobs so that, in case
581  * the work load is uneven, a worker that finished quickly can take up more jobs
582  * than another one.
583  *
584  * We also return 1 if there is no worker context for that generation.
585  */
586 int
587 sgen_workers_get_job_split_count (int generation)
588 {
589         return (worker_contexts [generation].active_workers_num > 1) ? worker_contexts [generation].active_workers_num * 4 : 1;
590 }
591
592 void
593 sgen_workers_foreach (int generation, SgenWorkerCallback callback)
594 {
595         WorkerContext *context = &worker_contexts [generation];
596         int i;
597
598         for (i = 0; i < context->workers_num; i++)
599                 callback (&context->workers_data [i]);
600 }
601
602 gboolean
603 sgen_workers_is_worker_thread (MonoNativeThreadId id)
604 {
605         return sgen_thread_pool_is_thread_pool_thread (id);
606 }
607
608 #endif