[m-rev.] For review: Improvments to Stack Segments code.

[Zoltan Somogyi]

On 22-Feb-2011, Paul Bone <pbone at csse.unimelb.edu.au> wrote:
> Non-segmented stack (32MB)
>     asm_fast.gc                      average of 5 with ignore=1     18.16 (1.00)
> 
> With 512KB (normal) segments:
>     asm_fast.gc.stseg and NO caching average of 5 with ignore=1     19.20 (1.06)
>     asm_fast.gc.stseg WITH caching   average of 5 with ignore=1     19.16 (1.06)
> 
> With 4KB segments:
>     asm_fast.gc.stseg and NO caching average of 5 with ignore=1     20.66 (1.14)
>     asm_fast.gc.stseg WITH caching   average of 5 with ignore=1     19.66 (1.08)

>     Not all zones are added to the used list for the benefit of the memory
>     error handlers.

I don't understand what this means.

>     Updates to used_memory_zones now use a pthread mutex so that only one
>     thread may be updating the list at once.  This lock is shared with the
>     free_memory_zones structure.
> 
>     Updates to used_memory_zones now use memory barriers to guarantee that
>     concurrent reads always read a consistent, but possibly incomplete,
>     data-structure.  This is necessary because it is read from a signal handler
>     which cannot call pthread_mutex().

Do you mean that READS from used_memory_zones use barriers?

> runtime/mercury_stacks.c:
>     Use MR_GC_NEW rather than MR_GC_malloc_uncollectable for the list of
>     previous stack segments associated with a context.  The context is heap
>     allocated so the list need not be uncollectable.

But if you know that it is never garbage until explicitly released, then
you can spare unnecessary scanning.

> runtime/mercury_wrapper.h:
> runtime/mercury_wrapper.c:
>     Disable redzones when using stack segments.  The settings here apply to
>     the first segment on every stack.

What settings do you mean?

> runtime/mercury_context.h:
> runtime/mercury_context.c:
>     Small contexts are only used in stack segment grades.

But what is the change?

> runtime/mercury_memory.c:
>     Adjust the definition of MR_unit.  It is now guaranteed to be a multiple of
>     the page size which is required by it's use in mercury_memory_zones.c
> 
>     Conform to changes in mercury_wrapper.h.

s/it's/its/

> doc/user_guide.texi:
>     Corrected the default detstack size.

You should add comments linking from the definition to the documentation
and vice versa.

> +** This list contains used zones that need a signal handler, for example those
> +** that have redzones.  Other used zones may exist that are not on this list
> +** because:
> +**
> +**   1) They don't have a redzone.
> +**
> +**   2) Putting them on this list in a threadsafe grade requires extra
> +**      synchronisation.
> +*/

Document here where those zones go when they are no longer needed.

> -    /*
> -    ** XXX MR_construct_zone() does not yet reuse previously allocated memory
> -    ** zones properly and simply leaks memory when it tries to do so.  As a
> -    ** workaround, we never put memory zones on the free list and deallocate
> -    ** them immediately here.
> -    */

We should redo the paper's benchmarks once this is committed and installed.

> +    zone = MR_get_free_zone(size + redsize);
> +    if (zone) {

This should be

	if (zone != NULL)

On a few systems, NULL is not 0.

> +    if (redsize || (handler != MR_null_handler)) {

redsize > 0

s/redsize/redzone_size/g

> +        ** Any zone with a redzone or a non-default handler must be
> +        ** added the the used zones list.

added TO the used zones list.

> +    ** The redzone must be page aligned and it's size must be a multiple of

s/it's/its/

> -    zone->MR_zone_name = name;
> -    zone->MR_zone_id = id;
> -    zone->MR_zone_desired_size = size;
> -    zone->MR_zone_redzone_size = redsize;
> +    zone->MR_zone_name = NULL;

Why ignore the name?

>  #ifdef  MR_CHECK_OVERFLOW_VIA_MPROTECT
> -    zone->MR_zone_handler = handler;
> +    zone->MR_zone_handler = NULL;
>  #endif /* MR_CHECK_OVERFLOW_VIA_MPROTECT */

Why this change?

> +    /*
> +    ** XXX: Why use this value for new_total_size?
> +    */
>  #ifdef  MR_PROTECTPAGE
>      new_total_size = new_size + 2 * MR_unit;
>  #else

If you think it does not make sense, change it.

> +/****************************************************************************
> +**
> +** Cacheing of memory zones.
> +*/
> +#ifdef MR_DO_NOT_CACHE_FREE_MEMORY_ZONES

Mention that this is only for benchmarking.

> +** MR_should_gc_memory_zones() - True if either number and number of pages are
> +** above the high water mark.

I don't understand what this is trying to say. What numbers?

> +** MR_should_stop_gc_memory_zones() - True if both the number nad number of
> +** pages are below the low water mark.

Or this.

> +static void             MR_gc_zones(void);
> +static MR_bool          MR_should_gc_memory_zones(void);
> +static MR_bool          MR_should_stop_gc_memory_zones(void);
> +
> +/*
> +** Currently we use high and low water marks, collection begins if either the
> +** number of zones or total number of pages is above their respective high
> +** water marks and stops when both are below their low water marks.
> +**
> +** TODO: Test for optimal values of these settings, however there's probably
> +** not much to be gained here that can't be more easily gained somewhere else
> +** first.
> +*/

Now I understand. Put the two comments together.

> +/* 16 zones per thread */
> +#define MR_FREE_MEMORY_ZONES_NUM_HIGH   (16*MR_num_threads)
> +/* 4 zones per thread */
> +#define MR_FREE_MEMORY_ZONES_NUM_LOW    (4*MR_num_threads)
> +/* 16MB per thread */
> +#define MR_FREE_MEMORY_ZONES_PAGES_HIGH (((16*1024*1024)/MR_page_size)*MR_num_threads)
> +/* 4MB per thread */
> +#define MR_FREE_MEMORY_ZONES_PAGES_LOW  (((4*1024*1024)/MR_page_size)*MR_num_threads)

You may want to control these via MERCURY_OPTIONS, and doing that would be
simpler if the multiplication by MR_num_threads was done by the code using
these constants, not parts of the constants themselves.

> +static MR_MemoryZonesFree * MR_THREADSAFE_VOLATILE
> +free_memory_zones = NULL;

This is one definition, not two, so indent the second line.

> +/*
> +** A pointer into the list of free zones that always points to sub-list (when
> +** valid) with the least-recently-used zones.

I don't understand what this is trying to say.

Certain actions can invalidate
> +** this pointer, if this happens it is set to NULL.  Therefore this can be
> +** thought of as 'cached information'.

Cached from what?

> +/*
> +** The next token to be given to a memory zone as it's added to the free list.
> +** The tokens are used to detect the least recently used zones when freeing
> +** them.

That tells me what they are used for, but not what they MEAN. Also,
s/it's/it is/

> +static MR_THREADSAFE_VOLATILE MR_Unsigned lru_memory_zone_token = 0;
> +
> +static MR_MemoryZone *
> +MR_get_free_zone(size_t size)
> +{
> +    MR_MemoryZone       *zone;
> +    MR_MemoryZonesFree  *zones_list;
> +    MR_MemoryZonesFree  *zones_list_prev;
> +
> +    /*
> +    ** Unlink the first zone on the free-list, link it onto the used-list
> +    ** and return it.
> +    */
> +    MR_LOCK(&memory_zones_lock, "MR_get_free_zone");
> +
> +    zones_list = free_memory_zones;
> +    zones_list_prev = NULL;
> +    while (zones_list) {
> +        if (zones_list->MR_zonesfree_size <= size) {
> +            /*
> +             * A zone on this list will fit our needs.
> +             */

Comment style.

> +    if (zones_list) {

!= NULL

> +        zone = zones_list->MR_zonesfree_minor_head;
> +        if (zone->MR_zone_next) {

!= NULL

and more places below.

> +                ** This zone list had the least recently used zone on it,
> +                ** invalidate the lru_free_memory_zones pointer.

Why is that OK to do? Why can't you set it to point to the next least recently
used zone?

> +    if (cur_list == NULL) {
> +        MR_MemoryZonesFree *new_list, *prev_list;

Separate declarations are less error-prone.

> +            /*
> +            ** Because no lists currently exist, this new list must be the list
> +            ** with the lru zone on it.

According to a comment a couple of dozen or so lines ago, the assumption
here seems to be incorrect; some lists MAY currently exist.

> +
> +    zone->MR_zone_next = cur_list->MR_zonesfree_minor_head;
> +    cur_list->MR_zonesfree_minor_head = zone;
> +    if (!cur_list->MR_zonesfree_minor_tail) {
> +        /*
> +        ** This is the first zone on this list, so we set the tail to it to
> +        ** track it as the least-recently-used zone on the list
> +        */
> +        cur_list->MR_zonesfree_minor_tail = zone;

Don't you need the tail pointer set up correctly anyway? And end the sentence
with a period.

> +static MR_bool
> +MR_should_stop_gc_memory_zones(void)
> +{
> +    return (free_memory_zones_num < MR_FREE_MEMORY_ZONES_NUM_LOW) ||
> +        (free_memory_zones_pages < MR_FREE_MEMORY_ZONES_PAGES_LOW);
> +}

Didn't your comment above say this || should be &&?

> +static void
> +MR_gc_zones(void)
> +{
> +    do {
> +        MR_LOCK(&memory_zones_lock, "MR_gc_zones");
> +        MR_MemoryZonesFree  *cur_list;
> +        MR_Unsigned         oldest_lru_token, cur_lru_token;
> +
> +        if (!lru_free_memory_zones) {

lru_free_memory_zones == NULL, here and below.

> +            while(cur_list)
> +            {

Brace style.

> +            ** There's no memory to collect, perhaps there was a race before we
> +            ** locked mercury_zones_lock

End with period.

> +** lru_token	This field is filled with a token each time a zone is freed,
> +**		it's used to track the least-recently-used zones in the free
> +**		list so that they can be handed back to the garbage
> +**		collector/OS.

You need to say what the token MEANS.

> +/*
> +** Free memory zones are arranged in a list of lists, The outer list (below)
> +** associates a size of the zones in each inner list.  It is to be kept in
> +** sorted order from smallest to largest.  So that a traversal of this list
> +** returns the zones that are the 'best fit' as the 'first fit'.  The inner
> +** lists (using the MR_zone_next field of the zones contain zones of all the
> +** same size.
> +*/

Add closing ).

> +struct MR_MemoryZonesFree_Struct {
> +    size_t              MR_zonesfree_size;
> +    MR_MemoryZonesFree  *MR_zonesfree_major_next;
> +    MR_MemoryZonesFree 	*MR_zonesfree_major_prev;
> +    MR_MemoryZone       *MR_zonesfree_minor_head;
> +    MR_MemoryZone       *MR_zonesfree_minor_tail;

Align the fields' indentation.

> +    MR_release_zone(MR_CONTEXT(MR_ctxt_detstack_zone));
>  
>      list = MR_CONTEXT(MR_ctxt_prev_detstack_zones);
>      MR_CONTEXT(MR_ctxt_detstack_zone) = list->MR_zones_head;
>      MR_CONTEXT(MR_ctxt_prev_detstack_zones) = list->MR_zones_tail;
>      MR_CONTEXT(MR_ctxt_sp) = orig_sp;
> +    /* XXX: GC will get this */
>      MR_GC_free(list);

Yeah, so? Why the XXX?

Otherwise, the diff seems fine.

Zoltan.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------