-/*
- * sgen-marksweep.c: The Mark & Sweep major collector.
+/**
+ * \file
+ * The Mark & Sweep major collector.
*
* Author:
* Mark Probst <mark.probst@gmail.com>
#define MS_MARK_BIT(bl,w,b) ((bl)->mark_words [(w)] & (ONE_P << (b)))
#define MS_SET_MARK_BIT(bl,w,b) ((bl)->mark_words [(w)] |= (ONE_P << (b)))
+#define MS_SET_MARK_BIT_PAR(bl,w,b,first) do { \
+ guint32 tmp_mark_word = (bl)->mark_words [(w)]; \
+ guint32 old_mark_word; \
+ first = FALSE; \
+ while (!(tmp_mark_word & (ONE_P << (b)))) { \
+ old_mark_word = tmp_mark_word; \
+ tmp_mark_word = InterlockedCompareExchange ((volatile gint32*)&(bl)->mark_words [w], old_mark_word | (ONE_P << (b)), old_mark_word); \
+ if (tmp_mark_word == old_mark_word) { \
+ first = TRUE; \
+ break; \
+ } \
+ } \
+ } while (0)
+
#define MS_OBJ_ALLOCED(o,b) (*(void**)(o) && (*(char**)(o) < MS_BLOCK_FOR_BLOCK_INFO (b) || *(char**)(o) >= MS_BLOCK_FOR_BLOCK_INFO (b) + MS_BLOCK_SIZE))
static gboolean concurrent_mark;
static gboolean concurrent_sweep = TRUE;
+SgenThreadPool sweep_pool_inst;
+SgenThreadPool *sweep_pool;
+
#define BLOCK_IS_TAGGED_HAS_REFERENCES(bl) SGEN_POINTER_IS_TAGGED_1 ((bl))
#define BLOCK_TAG_HAS_REFERENCES(bl) SGEN_POINTER_TAG_1 ((bl))
* thread only ever adds blocks to the free list, so the ABA problem can't occur.
*/
static MSBlockInfo * volatile *free_block_lists [MS_BLOCK_TYPE_MAX];
+static MonoNativeTlsKey worker_block_free_list_key;
static guint64 stat_major_blocks_alloced = 0;
static guint64 stat_major_blocks_freed = 0;
#define FREE_BLOCKS_FROM(lists,p,r) (lists [((p) ? MS_BLOCK_FLAG_PINNED : 0) | ((r) ? MS_BLOCK_FLAG_REFS : 0)])
#define FREE_BLOCKS(p,r) (FREE_BLOCKS_FROM (free_block_lists, (p), (r)))
+#define FREE_BLOCKS_LOCAL(p,r) (FREE_BLOCKS_FROM (((MSBlockInfo***)mono_native_tls_get_value (worker_block_free_list_key)), (p), (r)))
#define MS_BLOCK_OBJ_SIZE_INDEX(s) \
(((s)+7)>>3 < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES ? \
ms_find_block_obj_size_index ((s)))
static void*
-major_alloc_heap (mword nursery_size, mword nursery_align, int the_nursery_bits)
+major_alloc_heap (mword nursery_size, mword nursery_align)
{
char *start;
if (nursery_align)
return alloc_obj (vtable, size, FALSE, has_references);
}
+/*
+ * This can only be called by sgen workers. While this is called we assume
+ * that no other thread is accessing the block free lists. The world should
+ * be stopped and the gc thread should be waiting for workers to finish.
+ */
+static GCObject*
+major_alloc_object_par (GCVTable vtable, size_t size, gboolean has_references)
+{
+ int size_index = MS_BLOCK_OBJ_SIZE_INDEX (size);
+ MSBlockInfo * volatile * free_blocks = FREE_BLOCKS (FALSE, has_references);
+ MSBlockInfo **free_blocks_local = FREE_BLOCKS_LOCAL (FALSE, has_references);
+ void *obj;
+
+ if (free_blocks_local [size_index]) {
+get_slot:
+ obj = unlink_slot_from_free_list_uncontested (free_blocks_local, size_index);
+ } else {
+ MSBlockInfo *block;
+get_block:
+ block = free_blocks [size_index];
+ if (!block) {
+ if (G_UNLIKELY (!ms_alloc_block (size_index, FALSE, has_references)))
+ return NULL;
+ goto get_block;
+ } else {
+ MSBlockInfo *next_free = block->next_free;
+ /*
+ * Once a block is removed from the main list, it cannot return on the list until
+ * all the workers are finished and sweep is starting. This means we don't need
+ * to account for ABA problems.
+ */
+ if (SGEN_CAS_PTR ((volatile gpointer *)&free_blocks [size_index], next_free, block) != block)
+ goto get_block;
+ block->next_free = free_blocks_local [size_index];
+ free_blocks_local [size_index] = block;
+
+ goto get_slot;
+ }
+ }
+
+ /* FIXME: assumes object layout */
+ *(GCVTable*)obj = vtable;
+
+ /* FIXME is it worth CAS-ing here */
+ total_allocated_major += block_obj_sizes [size_index];
+
+ return (GCObject *)obj;
+}
+
/*
* We're not freeing the block if it's empty. We leave that work for
* the next major collection.
wait:
job = sweep_job;
if (job)
- sgen_thread_pool_job_wait (job);
+ sgen_thread_pool_job_wait (sweep_pool, job);
SGEN_ASSERT (0, !sweep_job, "Why did the sweep job not null itself?");
SGEN_ASSERT (0, sweep_state == SWEEP_STATE_SWEPT, "How is the sweep job done but we're not swept?");
}
if (!MS_MARK_BIT ((block), __word, __bit)) { \
MS_SET_MARK_BIT ((block), __word, __bit); \
if (sgen_gc_descr_has_references (desc)) \
- GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
+ GRAY_OBJECT_ENQUEUE_SERIAL ((queue), (obj), (desc)); \
+ binary_protocol_mark ((obj), (gpointer)SGEN_LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((obj))); \
+ INC_NUM_MAJOR_OBJECTS_MARKED (); \
+ } \
+ } while (0)
+#define MS_MARK_OBJECT_AND_ENQUEUE_PAR(obj,desc,block,queue) do { \
+ int __word, __bit; \
+ gboolean first; \
+ MS_CALC_MARK_BIT (__word, __bit, (obj)); \
+ SGEN_ASSERT (9, MS_OBJ_ALLOCED ((obj), (block)), "object %p not allocated", obj); \
+ MS_SET_MARK_BIT_PAR ((block), __word, __bit, first); \
+ if (first) { \
+ if (sgen_gc_descr_has_references (desc)) \
+ GRAY_OBJECT_ENQUEUE_PARALLEL ((queue), (obj), (desc)); \
binary_protocol_mark ((obj), (gpointer)SGEN_LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((obj))); \
INC_NUM_MAJOR_OBJECTS_MARKED (); \
} \
} while (0)
+
+
static void
pin_major_object (GCObject *obj, SgenGrayQueue *queue)
{
MS_MARK_OBJECT_AND_ENQUEUE (obj, sgen_obj_get_descriptor (obj), block, queue);
}
+#define COPY_OR_MARK_PARALLEL
#include "sgen-major-copy-object.h"
static long long
#define DRAIN_GRAY_STACK_FUNCTION_NAME drain_gray_stack_no_evacuation
#include "sgen-marksweep-drain-gray-stack.h"
+#define COPY_OR_MARK_PARALLEL
+#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_par_no_evacuation
+#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_par_no_evacuation
+#define DRAIN_GRAY_STACK_FUNCTION_NAME drain_gray_stack_par_no_evacuation
+#include "sgen-marksweep-drain-gray-stack.h"
+
#define COPY_OR_MARK_WITH_EVACUATION
#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_with_evacuation
#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_with_evacuation
#define SCAN_PTR_FIELD_FUNCTION_NAME major_scan_ptr_field_with_evacuation
#include "sgen-marksweep-drain-gray-stack.h"
+#define COPY_OR_MARK_PARALLEL
+#define COPY_OR_MARK_WITH_EVACUATION
+#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_par_with_evacuation
+#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_par_with_evacuation
+#define SCAN_VTYPE_FUNCTION_NAME major_scan_vtype_par_with_evacuation
+#define DRAIN_GRAY_STACK_FUNCTION_NAME drain_gray_stack_par_with_evacuation
+#define SCAN_PTR_FIELD_FUNCTION_NAME major_scan_ptr_field_par_with_evacuation
+#include "sgen-marksweep-drain-gray-stack.h"
+
#define COPY_OR_MARK_CONCURRENT
#define COPY_OR_MARK_FUNCTION_NAME major_copy_or_mark_object_concurrent_no_evacuation
#define SCAN_OBJECT_FUNCTION_NAME major_scan_object_concurrent_no_evacuation
return drain_gray_stack_no_evacuation (queue);
}
+static gboolean
+drain_gray_stack_par (SgenGrayQueue *queue)
+{
+ if (major_is_evacuating ())
+ return drain_gray_stack_par_with_evacuation (queue);
+ else
+ return drain_gray_stack_par_no_evacuation (queue);
+}
+
static gboolean
drain_gray_stack_concurrent (SgenGrayQueue *queue)
{
major_copy_or_mark_object_with_evacuation (ptr, *ptr, queue);
}
+static void
+major_copy_or_mark_object_concurrent_par_finish_canonical (GCObject **ptr, SgenGrayQueue *queue)
+{
+ major_copy_or_mark_object_par_with_evacuation (ptr, *ptr, queue);
+}
+
static void
mark_pinned_objects_in_block (MSBlockInfo *block, size_t first_entry, size_t last_entry, SgenGrayQueue *queue)
{
static volatile size_t num_major_sections_before_sweep;
static volatile size_t num_major_sections_freed_in_sweep;
+static void
+sgen_worker_clear_free_block_lists (WorkerData *worker)
+{
+ int i, j;
+
+ if (!worker->free_block_lists)
+ return;
+
+ for (i = 0; i < MS_BLOCK_TYPE_MAX; i++) {
+ for (j = 0; j < num_block_obj_sizes; j++) {
+ ((MSBlockInfo***) worker->free_block_lists) [i][j] = NULL;
+ }
+ }
+}
+
+static void
+sgen_worker_clear_free_block_lists_evac (WorkerData *worker)
+{
+ int i, j;
+
+ if (!worker->free_block_lists)
+ return;
+
+ for (i = 0; i < MS_BLOCK_TYPE_MAX; i++) {
+ for (j = 0; j < num_block_obj_sizes; j++) {
+ if (((MSBlockInfo***) worker->free_block_lists) [i][j])
+ SGEN_ASSERT (0, !((MSBlockInfo***) worker->free_block_lists) [i][j]->next_free, "Why do we have linked free blocks on the workers");
+
+ if (evacuate_block_obj_sizes [j])
+ ((MSBlockInfo***) worker->free_block_lists) [i][j] = NULL;
+ }
+ }
+}
+
static void
sweep_start (void)
{
for (j = 0; j < num_block_obj_sizes; ++j)
free_blocks [j] = NULL;
}
+
+ sgen_workers_foreach (sgen_worker_clear_free_block_lists);
}
static void sweep_finish (void);
*/
if (concurrent_sweep && lazy_sweep) {
sweep_blocks_job = sgen_thread_pool_job_alloc ("sweep_blocks", sweep_blocks_job_func, sizeof (SgenThreadPoolJob));
- sgen_thread_pool_job_enqueue (sweep_blocks_job);
+ sgen_thread_pool_job_enqueue (sweep_pool, sweep_blocks_job);
}
sweep_finish ();
SGEN_ASSERT (0, !sweep_job, "We haven't finished the last sweep?");
if (concurrent_sweep) {
sweep_job = sgen_thread_pool_job_alloc ("sweep", sweep_job_func, sizeof (SgenThreadPoolJob));
- sgen_thread_pool_job_enqueue (sweep_job);
+ sgen_thread_pool_job_enqueue (sweep_pool, sweep_job);
} else {
sweep_job_func (NULL, NULL);
}
sgen_evacuation_freelist_blocks (&free_block_lists [MS_BLOCK_FLAG_REFS][i], i);
}
+ /* We expect workers to have very few blocks on the freelist, just evacuate them */
+ sgen_workers_foreach (sgen_worker_clear_free_block_lists_evac);
+
if (lazy_sweep && concurrent_sweep) {
/*
* sweep_blocks_job is created before sweep_finish, which we wait for above
*/
SgenThreadPoolJob *job = sweep_blocks_job;
if (job)
- sgen_thread_pool_job_wait (job);
+ sgen_thread_pool_job_wait (sweep_pool, job);
}
if (lazy_sweep && !concurrent_sweep)
#endif
}
+static SgenThreadPool*
+major_get_sweep_pool (void)
+{
+ return sweep_pool;
+}
+
static int
compare_pointers (const void *va, const void *vb) {
char *a = *(char**)va, *b = *(char**)vb;
}
static void
-major_scan_card_table (CardTableScanType scan_type, ScanCopyContext ctx)
+major_scan_card_table (CardTableScanType scan_type, ScanCopyContext ctx, int job_index, int job_split_count)
{
MSBlockInfo *block;
gboolean has_references, was_sweeping, skip_scan;
binary_protocol_major_card_table_scan_start (sgen_timestamp (), scan_type & CARDTABLE_SCAN_MOD_UNION);
FOREACH_BLOCK_HAS_REFERENCES_NO_LOCK (block, has_references) {
+ if (__index % job_split_count != job_index)
+ continue;
#ifdef PREFETCH_CARDS
- int prefetch_index = __index + 6;
+ int prefetch_index = __index + 6 * job_split_count;
if (prefetch_index < allocated_blocks.next_slot) {
MSBlockInfo *prefetch_block = BLOCK_UNTAG (*sgen_array_list_get_slot (&allocated_blocks, prefetch_index));
PREFETCH_READ (prefetch_block);
post_param_init (SgenMajorCollector *collector)
{
collector->sweeps_lazily = lazy_sweep;
- collector->needs_thread_pool = concurrent_mark || concurrent_sweep;
+}
+
+/* We are guaranteed to be called by the worker in question */
+static void
+sgen_worker_init_callback (gpointer worker_untyped)
+{
+ int i;
+ WorkerData *worker = (WorkerData*) worker_untyped;
+ MSBlockInfo ***worker_free_blocks = (MSBlockInfo ***) sgen_alloc_internal_dynamic (sizeof (MSBlockInfo**) * MS_BLOCK_TYPE_MAX, INTERNAL_MEM_MS_TABLES, TRUE);
+
+ for (i = 0; i < MS_BLOCK_TYPE_MAX; i++)
+ worker_free_blocks [i] = (MSBlockInfo **) sgen_alloc_internal_dynamic (sizeof (MSBlockInfo*) * num_block_obj_sizes, INTERNAL_MEM_MS_TABLES, TRUE);
+
+ worker->free_block_lists = worker_free_blocks;
+
+ mono_native_tls_set_value (worker_block_free_list_key, worker_free_blocks);
+}
+
+static void
+thread_pool_init_func (void *data_untyped)
+{
+ sgen_client_thread_register_worker ();
}
static void
for (i = 0; i < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES * 8; ++i)
g_assert (MS_BLOCK_OBJ_SIZE_INDEX (i) == ms_find_block_obj_size_index (i));
+ /* We can do this because we always init the minor before the major */
+ if (is_parallel || sgen_get_minor_collector ()->is_parallel) {
+ mono_native_tls_alloc (&worker_block_free_list_key, NULL);
+ collector->worker_init_cb = sgen_worker_init_callback;
+ }
+
mono_counters_register ("# major blocks allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_major_blocks_alloced);
mono_counters_register ("# major blocks freed", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_major_blocks_freed);
mono_counters_register ("# major blocks lazy swept", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_major_blocks_lazy_swept);
concurrent_mark = is_concurrent;
collector->is_concurrent = is_concurrent;
collector->is_parallel = is_parallel;
- collector->needs_thread_pool = is_concurrent || concurrent_sweep;
collector->get_and_reset_num_major_objects_marked = major_get_and_reset_num_major_objects_marked;
collector->supports_cardtable = TRUE;
collector->alloc_degraded = major_alloc_degraded;
collector->alloc_object = major_alloc_object;
+ collector->alloc_object_par = major_alloc_object_par;
collector->free_pinned_object = free_pinned_object;
collector->iterate_objects = major_iterate_objects;
collector->free_non_pinned_object = major_free_non_pinned_object;
collector->is_valid_object = major_is_valid_object;
collector->describe_pointer = major_describe_pointer;
collector->count_cards = major_count_cards;
+ collector->get_sweep_pool = major_get_sweep_pool;
collector->major_ops_serial.copy_or_mark_object = major_copy_or_mark_object_canonical;
collector->major_ops_serial.scan_object = major_scan_object_with_evacuation;
+ collector->major_ops_serial.scan_ptr_field = major_scan_ptr_field_with_evacuation;
collector->major_ops_serial.drain_gray_stack = drain_gray_stack;
if (is_concurrent) {
collector->major_ops_concurrent_start.copy_or_mark_object = major_copy_or_mark_object_concurrent_canonical;
collector->major_ops_conc_par_start.scan_ptr_field = major_scan_ptr_field_concurrent_par_with_evacuation;
collector->major_ops_conc_par_start.drain_gray_stack = drain_gray_stack_concurrent_par;
- /* FIXME use parallel obj ops */
- collector->major_ops_conc_par_finish = collector->major_ops_concurrent_finish;
+ collector->major_ops_conc_par_finish.copy_or_mark_object = major_copy_or_mark_object_concurrent_par_finish_canonical;
+ collector->major_ops_conc_par_finish.scan_object = major_scan_object_par_with_evacuation;
+ collector->major_ops_conc_par_finish.scan_vtype = major_scan_vtype_par_with_evacuation;
+ collector->major_ops_conc_par_finish.scan_ptr_field = major_scan_ptr_field_par_with_evacuation;
+ collector->major_ops_conc_par_finish.drain_gray_stack = drain_gray_stack_par;
}
}
/*cardtable requires major pages to be 8 cards aligned*/
g_assert ((MS_BLOCK_SIZE % (8 * CARD_SIZE_IN_BYTES)) == 0);
+
+ if (concurrent_sweep) {
+ SgenThreadPool **thread_datas = &sweep_pool;
+ sweep_pool = &sweep_pool_inst;
+ sgen_thread_pool_init (sweep_pool, 1, thread_pool_init_func, NULL, NULL, NULL, (SgenThreadPoolData**)&thread_datas);
+ }
}
void