[Mono-dev] [PATCH]Add ephemeron support for sgen

[Paolo Molaro]

On 05/04/10 Rodrigo Kumpera wrote:
> Once this patch is accepted I'll move into finishing the managed side of it.
> Right now CWT is implemented doing linear search, but the idea is to switch
> to
> open addressing. To do that, the only change required to sgen is to store a
> tombstone instead of NULL when clearing unreachable keys.

The tombstone object needs to be known to both the managed and unmanaged
code: it may be a good idea to register it with the GC in the same icall
that registers the array (it would be per-domain, but storing it as an
additional field in EphemeronLinkNode should be fine).

> --- a/mono/metadata/sgen-gc.c
> +++ b/mono/metadata/sgen-gc.c
> +/* LOCKING: requires that the GC lock is held */
> +static void
> +clear_unreachable_ephemerons (CopyOrMarkObjectFunc copy_func, char *start, char *end)
> +{
> +	int was_in_nursery, was_promoted;
> +	EphemeronLinkNode *current = ephemeron_list, *prev = NULL;
> +	MonoArray *array;
> +	mword **ptr;
> +	uintptr_t i, length;
> +
> +	while (current) {
> +		char *object = current->array;
> +
> +		if (!object_is_reachable (object, start, end)) {
> +			EphemeronLinkNode *tmp = current;
> +
> +			DEBUG (5, fprintf (gc_debug_file, "Dead Ephemeron array at %p\n", object));
> +
> +			if (prev)
> +				prev->next = current->next;
> +			else
> +				ephemeron_list = current->next;
> +
> +			current = current->next;
> +			free_internal_mem (tmp, INTERNAL_MEM_EPHEMERON_LINK);
> +
> +			continue;
> +		}
> +
> +		was_in_nursery = ptr_in_nursery (object);
> +		copy_func ((void**)&object);
> +		current->array = object;
> +
> +		/*The array was promoted. Promote all elements of the array and add global remsets from the ones left behind in the nursery.
> +		 */
> +		was_promoted = was_in_nursery && !ptr_in_nursery (object);
> +
> +		DEBUG (5, fprintf (gc_debug_file, "Clearing unreachable entries for ephemeron array at %p\n", object));
> +
> +		array = (MonoArray*)object;
> +		ptr = (mword**)mono_array_addr_with_size (array, sizeof (mword) * 2, 0);
> +		length = mono_array_length (array);
> +
> +		for (i = 0; i < length; ++i) {
> +			char *key = (char*)ptr [0];
> +			char *value = (char*)ptr [1];

Using a:
typedef struct {
	void *key;
	void *value;
} Ephemeron;

instead of using ptr[0]/ptr[1] should make the code nicer here.

> +
> +			if (key)
> +				DEBUG (5, fprintf (gc_debug_file, "[%d] key %p (%s) value %p (%s)\n", i,
> +					key, key && object_is_reachable (key, start, end) ? "reachable" : "unreachable",
> +					value, value && object_is_reachable (value, start, end) ? "reachable" : "unreachable"));
> +
> +			if (key && !object_is_reachable (key, start, end)) {
> +				DEBUG (5, fprintf (gc_debug_file, "\tclearing index %d\n", i));
> +				ptr [0] = NULL;
> +				ptr [1] = NULL;
> +				key = NULL;
> +			}
> +
> +			if (key && was_promoted) {
> +				if (ptr_in_nursery (key)) {/*key was not promoted*/
> +					DEBUG (5, fprintf (gc_debug_file, "\tAdded remset to key %p\n", key));
> +					add_to_global_remset (ptr, FALSE);
> +				}
> +				if (ptr_in_nursery (value)) {/*value was not promoted*/
> +					DEBUG (5, fprintf (gc_debug_file, "\tAdded remset to value %p\n", value));
> +					add_to_global_remset (ptr + 1, FALSE);
> +				}
> +			}
> +			ptr += 2;
> +	   }

I would move the ptr += 2 together with the ++i (or use a single loop
indexer) and use the appropriate continue statements instead of the
multiple checks for a NULL key (it will also simplify the code when
tombstone support will be added).

> +/* LOCKING: requires that the GC lock is held */
> +static int
> +mark_ephemerons_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end)
> +{
> +	int nothing_marked = 1;
> +	EphemeronLinkNode *current = ephemeron_list;
> +	MonoArray *array;
> +	mword **ptr;
> +	uintptr_t i, length;
> +
> +	while (current) {

A for loop here is likely more appropriate, instead of the multiple
current = current->next statements.

> +		char *object = current->array, *old;
> +		DEBUG (5, fprintf (gc_debug_file, "Ephemeron array at %p\n", object));
> +		/*We ignore arrays in old gend during minor collections since all objects are promoted by the remset machinery.*/
> +
> +		if (object < start || object >= end) {
> +			current = current->next;
> +			continue;
> +		}
> +
> +		/*it has to be alive*/
> +		if (!object_is_reachable (object, start, end)) {
> +			DEBUG (5, fprintf (gc_debug_file, "Ephemeron array at %p is not reachable\n", object));
> +			current = current->next;
> +			continue;
> +		}
> +
> +		old = object;
> +		copy_func ((void**)&object);
> +
> +		array = (MonoArray*)object;
> +		ptr = (mword**)mono_array_addr_with_size (array, sizeof (mword) * 2, 0);
> +		length = mono_array_length (array);
> +
> +		DEBUG (5, fprintf (gc_debug_file, "Processing Ephemeron array at %p - %p\n", object, old));
> +		for (i = 0; i < mono_array_length (array); ++i) {
> +			char *key = (char*)ptr [0];
> +			char *value = (char*)ptr [1];

The Ephemeron struct would make the code nicer here, too.

> +/* LOCKING: assumes the GC lock is held */
> +static void
> +mono_gc_register_ephemeron_array (MonoObject *obj)
> +{
[...]
> +void
> +mono_gc_ephemeron_array_add (MonoObject *obj)
> +{
> +	LOCK_GC;
> +	mono_gc_register_ephemeron_array (obj);
> +	UNLOCK_GC;
> +}

Why two separate functions here? mono_gc_register_ephemeron_array has no
other callers.
Also, make the icall return the array or otherwise another value that
can be used to deal with an out of memory condition in the linked list
node allocation, for example (the exception would get thrown in managed
code).
If Mark doesn't have objections, with the above changes the code can go in.
Thanks!

lupus

-- 
-----------------------------------------------------------------
lupus at debian.org                                     debian/rules
lupus at ximian.com                             Monkeys do it better