[m-rev.] for review: fix nondet stack segments

Peter Wang novalazy at gmail.com
Wed Aug 6 17:06:48 AEST 2008


For review by Zoltan.

Branches: main

Nondet stack segments didn't work properly using the placeholder frame trick
at the base of nondet stack segments. i.e. when we jump to special procedure
(MR_pop_nondetstack_segment) stored in the succip slot of the base frame, it
should free the top stack segment, set maxfr to the correct value and jump to
the real succip.  However, we were reading values of maxfr and succip from
the *det* stack which is clearly wrong.  After fixing that, it still didn't
work properly.  Nondet execution seems to be too haphazard for the trick to
work.  MR_pop_nondetstack_segment() can be entered not only when the top
stack segment can be deallocated, which complicates things.

Instead, switch to a simpler method to deallocate nondet stack frames.  When
creating a nondet frame, we know that all stack segments above that which
`maxfr' points into can be freed.  In the common case, `maxfr' *will* point
into the top stack segment and that can be checked with just one additional
test.  After deallocating excess stack segments, the new frame can be created
as before.

See also Mantis bug #65.

runtime/mercury_stacks.h:
	Make `MR_nondetstack_extend_and_check' check that `maxfr' still lives
	on the top nondet stack segment.  If not, or if a new segment is
	required, call `MR_nondetstack_segment_extend_slow_path'.

runtime/mercury_stacks.c:
	Rename `MR_new_detstack_segment' to
	`MR_nondetstack_segment_extend_slow_path'.  Make it free excess
	nondet stack segments.

	Fix a bug where `MR_NONDET_FIXED_SIZE' was added twice to the number of
	slots required for a new frame.

	Delete `MR_pop_nondetstack_segment' which is no longer used.

	Don't use red zones for new det and nondet stack segments.

	Add missing parameters to some debugging code.

runtime/mercury_stack_trace.c:
	Delete reference to `MR_pop_nondetstack_segment'.

runtime/mercury_memory_zones.c:
	Add sanity checks for small memory zone sizes, e.g. they may be too
	small to fit all of the usable zone area, red zone and cache offset.

NEWS:
	Announce stack segment support as it should be stable now.

diff --git a/NEWS b/NEWS
index b55d40a..82a6215 100644
--- a/NEWS
+++ b/NEWS
@@ -236,6 +236,9 @@ Changes to the Mercury compiler:
 
 * We have added support for simultaneous execution of jobs with `mmc --make'.
 
+* We have added support for stack segments, which allows programs to grow
+  stacks on demand.
+
 * We have made it easier to use single-precision floats, which do not need
   to be boxed on 32-bit machines.
 
@@ -425,6 +428,12 @@ Changes to the Mercury compiler:
 * Simultaneous execution of jobs with `mmc --make' can be enabled with
   the `--jobs <n>' option.
 
+* The option `--stack-segments', or grade component `.stseg', causes
+  programs to execute using stack segments, where segments can be allocated
+  at runtime, instead of using fixed sized stacks.  The program won't run out
+  of stack space and stack sizes can be much smaller, but execution time will
+  be increased.
+
 * Single-precision floats can now be selected for the C backends by using the
   `.spf' grade component, or passing the `--single-prec-float' option to the
   compiler.
diff --git a/runtime/mercury_memory_zones.c b/runtime/mercury_memory_zones.c
index 47b3420..ac2e418 100644
--- a/runtime/mercury_memory_zones.c
+++ b/runtime/mercury_memory_zones.c
@@ -531,7 +531,6 @@ MR_construct_zone(const char *name, int id, MR_Word *base,
 {
     MR_MemoryZone   *zone;
     size_t          total_size;
-    int             res;
 
     if (base == NULL) {
         MR_fatal_error("MR_construct_zone called with NULL pointer");
@@ -652,6 +651,8 @@ MR_setup_redzones(MR_MemoryZone *zone)
     size = zone->MR_zone_desired_size;
     redsize = zone->MR_zone_redzone_size;
 
+    assert(size > redsize);
+
     /*
     ** setup the redzone
     */
@@ -661,6 +662,14 @@ MR_setup_redzones(MR_MemoryZone *zone)
             MR_unit);
     zone->MR_zone_redzone_base = zone->MR_zone_redzone;
 
+    /*
+    ** When using small memory zones, the offset given by MR_next_offset()
+    ** might have us starting in the middle of the redzone.  Don't do that.
+    */
+    if (zone->MR_zone_min >= zone->MR_zone_redzone) {
+        zone->MR_zone_min = zone->MR_zone_bottom;
+    }
+
     res = MR_protect_pages((char *) zone->MR_zone_redzone, redsize + MR_unit,
         REDZONE_PROT);
     if (res < 0) {
@@ -697,6 +706,9 @@ MR_setup_redzones(MR_MemoryZone *zone)
 #if defined(MR_STACK_SEGMENTS) && !defined(MR_HIGHLEVEL_CODE)
     zone->MR_zone_extend_threshold = (char *) zone->MR_zone_end
         - MR_stack_margin_size;
+
+    assert((MR_Word *) zone->MR_zone_extend_threshold > zone->MR_zone_min);
+    assert((MR_Word *) zone->MR_zone_extend_threshold < zone->MR_zone_redzone);
 #endif
 }
 
diff --git a/runtime/mercury_stack_trace.c b/runtime/mercury_stack_trace.c
index afd50b1..a12a550 100644
--- a/runtime/mercury_stack_trace.c
+++ b/runtime/mercury_stack_trace.c
@@ -321,10 +321,6 @@ MR_stack_walk_succip_layout(MR_Code *success,
         success = (MR_Code *) MR_based_stackvar(*stack_trace_sp_ptr, 2);
         *stack_trace_sp_ptr = (MR_Word *)
             MR_based_stackvar(*stack_trace_sp_ptr, 1);
-    } else if (success == MR_ENTRY(MR_pop_nondetstack_segment)) {
-        success = MR_succip_slot(*stack_trace_curfr_ptr);
-        *stack_trace_curfr_ptr = (MR_Word *)
-            MR_based_framevar(*stack_trace_curfr_ptr, 1);
     }
 #endif /* !MR_HIGHLEVEL_CODE && MR_STACK_SEGMENTS */
 
diff --git a/runtime/mercury_stacks.c b/runtime/mercury_stacks.c
index da11e2f..cbb8aa8 100644
--- a/runtime/mercury_stacks.c
+++ b/runtime/mercury_stacks.c
@@ -202,7 +202,6 @@ MR_debug_zone_extend(FILE *fp, const char *when, const char *stackname,
 #ifdef  MR_STACK_SEGMENTS
 
 MR_declare_entry(MR_pop_detstack_segment);
-MR_declare_entry(MR_pop_nondetstack_segment);
 
 MR_Word *MR_new_detstack_segment(MR_Word *sp, int n)
 {
@@ -212,8 +211,9 @@ MR_Word *MR_new_detstack_segment(MR_Word *sp, int n)
 
     old_sp = sp;
 
+    /* We perform explicit overflow checks so redzones just waste space. */
     new_zone = MR_create_zone("detstack_segment", 0, MR_detstack_size, 0,
-        MR_detstack_zone_size, MR_default_handler);
+        0, MR_default_handler);
 
     list = MR_GC_malloc_uncollectable(sizeof(MR_MemoryZones));
 
@@ -221,8 +221,8 @@ MR_Word *MR_new_detstack_segment(MR_Word *sp, int n)
     printf("create new det segment: old zone: %p, old sp %p\n",
         MR_CONTEXT(MR_ctxt_detstack_zone), old_sp);
     printf("old sp: ");
-    MR_printdetstack(old_sp);
-    printf("old succip: ");
+    MR_printdetstack(stdout, old_sp);
+    printf(", old succip: ");
     MR_printlabel(stdout, MR_succip);
 #endif
 
@@ -244,25 +244,43 @@ MR_Word *MR_new_detstack_segment(MR_Word *sp, int n)
     printf("create new det segment: new zone: %p, new sp %p\n",
         MR_CONTEXT(MR_ctxt_detstack_zone), MR_sp);
     printf("new sp: ");
-    MR_printdetstack(MR_sp);
-    printf("new succip: ");
+    MR_printdetstack(stdout, MR_sp);
+    printf(", new succip: ");
     MR_printlabel(stdout, MR_ENTRY(MR_pop_detstack_segment));
 #endif
 
     return MR_sp;
 }
 
-MR_Word *
-MR_new_nondetstack_segment(MR_Word *maxfr, int n)
+static  void     MR_rewind_nondetstack_segments(MR_Word *maxfr);
+
+void
+MR_nondetstack_segment_extend_slow_path(MR_Word *old_maxfr, int incr)
 {
-    MR_Word         *old_maxfr;
+    MR_Word         *new_maxfr;
     MR_MemoryZones  *list;
     MR_MemoryZone   *new_zone;
 
-    old_maxfr = maxfr;
+    /*
+    ** Pop off the nondet stack segments until maxfr is within the bounds of
+    ** the top segment.
+    ** XXX we could avoid rewinding all the way if we'll be needing to create a
+    ** new segment anyway
+    */
+    MR_rewind_nondetstack_segments(old_maxfr);
+
+    /* Try to make a frame on the top segment. */
+    new_maxfr = old_maxfr + incr;
+    if (new_maxfr < (MR_Word *) MR_CONTEXT(MR_ctxt_nondetstack_zone)->
+        MR_zone_extend_threshold)
+    {
+        MR_maxfr_word = (MR_Word) new_maxfr;
+        return;
+    }
 
-    new_zone = MR_create_zone("nondetstack_segment", 0, MR_nondetstack_size, 0,
-        MR_nondetstack_zone_size, MR_default_handler);
+    /* We perform explicit overflow checks so redzones just waste space. */
+    new_zone = MR_create_zone("nondetstack_segment", 0,
+        MR_nondetstack_size, 0, 0, MR_default_handler);
 
     list = MR_GC_malloc_uncollectable(sizeof(MR_MemoryZones));
 
@@ -270,9 +288,7 @@ MR_new_nondetstack_segment(MR_Word *maxfr, int n)
     printf("create new nondet segment: old zone: %p, old maxfr %p\n",
         MR_CONTEXT(MR_ctxt_nondetstack_zone), old_maxfr);
     printf("old maxfr: ");
-    MR_printnondetstack(old_maxfr);
-    printf("old succip: ");
-    MR_printlabel(stdout, MR_succip);
+    MR_printnondetstack(stdout, old_maxfr);
 #endif
 
     list->MR_zones_head = MR_CONTEXT(MR_ctxt_nondetstack_zone);
@@ -282,33 +298,50 @@ MR_new_nondetstack_segment(MR_Word *maxfr, int n)
     MR_CONTEXT(MR_ctxt_maxfr) =
         MR_CONTEXT(MR_ctxt_nondetstack_zone)->MR_zone_min;
 
-    MR_maxfr_word = (MR_Word) MR_CONTEXT(MR_ctxt_maxfr);
-
-    MR_mkframe("new_nondetstack_segment", 1, MR_ENTRY(MR_do_fail));
-    MR_framevar(1) = (MR_Word) old_maxfr;
-
-    MR_maxfr_word = (MR_Word) (MR_maxfr + (MR_NONDET_FIXED_SIZE + (n)));
+    MR_maxfr_word = (MR_Word) (MR_CONTEXT(MR_ctxt_maxfr) + incr);
 
 #ifdef  MR_DEBUG_STACK_SEGMENTS
     printf("create new nondet segment: new zone: %p, new maxfr %p\n",
         MR_CONTEXT(MR_ctxt_nondetstack_zone), MR_maxfr);
     printf("new maxfr: ");
-    MR_printnondetstack(MR_maxfr);
-    printf("new succip: ");
-    MR_printlabel(stdout, MR_ENTRY(MR_pop_nondetstack_segment));
+    MR_printnondetstack(stdout, MR_maxfr);
 #endif
+}
 
-    return MR_maxfr;
+static void
+MR_rewind_nondetstack_segments(MR_Word *maxfr)
+{
+    MR_MemoryZone   *zone;
+    MR_MemoryZones  *list;
+
+    for (;;) {
+        zone = MR_CONTEXT(MR_ctxt_nondetstack_zone);
+        /*
+        ** XXX why is maxfr sometimes slightly past MR_zone_extend_threshold?
+        ** That's why we test against MR_zone_redzone.
+        */
+        if (maxfr >= zone->MR_zone_min &&
+            maxfr < (MR_Word *) zone->MR_zone_redzone)
+        {
+            break;
+        }
+
+        MR_unget_zone(zone);
+
+        list = MR_CONTEXT(MR_ctxt_prev_nondetstack_zones);
+        assert(list);
+        MR_CONTEXT(MR_ctxt_nondetstack_zone) = list->MR_zones_head;
+        MR_CONTEXT(MR_ctxt_prev_nondetstack_zones) = list->MR_zones_tail;
+        MR_GC_free(list);
+    }
 }
 
 #endif  /* MR_STACK_SEGMENTS */
 
 MR_define_extern_entry(MR_pop_detstack_segment);
-MR_define_extern_entry(MR_pop_nondetstack_segment);
 
 MR_BEGIN_MODULE(stack_segment_module)
     MR_init_entry_an(MR_pop_detstack_segment);
-    MR_init_entry_an(MR_pop_nondetstack_segment);
 MR_BEGIN_CODE
 
 MR_define_entry(MR_pop_detstack_segment);
@@ -325,8 +358,8 @@ MR_define_entry(MR_pop_detstack_segment);
     printf("restore old det segment: old zone %p, old sp %p\n",
         MR_CONTEXT(MR_ctxt_detstack_zone), MR_sp);
     printf("old sp: ");
-    MR_printdetstack(MR_sp);
-    printf("old succip: ");
+    MR_printdetstack(stdout, MR_sp);
+    printf(", old succip: ");
     MR_printlabel(stdout, MR_succip);
 #endif
 
@@ -342,8 +375,8 @@ MR_define_entry(MR_pop_detstack_segment);
     printf("restore old det segment: new zone %p, new sp %p\n",
         MR_CONTEXT(MR_ctxt_detstack_zone), orig_sp);
     printf("new sp: ");
-    MR_printdetstack(orig_sp);
-    printf("new succip: ");
+    MR_printdetstack(stdout, orig_sp);
+    printf(", new succip: ");
     MR_printlabel(stdout, orig_succip);
 #endif
 
@@ -354,49 +387,6 @@ MR_define_entry(MR_pop_detstack_segment);
     MR_fatal_error("MR_pop_detstack_segment reached\n");
 #endif  /* MR_STACK_SEGMENTS */
 
-MR_define_entry(MR_pop_nondetstack_segment);
-#ifdef MR_STACK_SEGMENTS
-{
-    MR_MemoryZones  *list;
-    MR_Word         *orig_maxfr;
-    MR_Code         *orig_succip;
-
-    orig_maxfr = (MR_Word *) MR_stackvar(1);
-    orig_succip = (MR_Code *) MR_stackvar(2);
-
-#ifdef  MR_DEBUG_STACK_SEGMENTS
-    printf("restore old nondet segment: old zone %p, old maxfr %p\n",
-        MR_CONTEXT(MR_ctxt_nondetstack_zone), MR_maxfr);
-    printf("old maxfr: ");
-    MR_printnondetstack(MR_maxfr);
-    printf("old succip: ");
-    MR_printlabel(stdout, MR_succip);
-#endif
-
-    MR_unget_zone(MR_CONTEXT(MR_ctxt_nondetstack_zone));
-
-    list = MR_CONTEXT(MR_ctxt_prev_nondetstack_zones);
-    MR_CONTEXT(MR_ctxt_nondetstack_zone) = list->MR_zones_head;
-    MR_CONTEXT(MR_ctxt_prev_nondetstack_zones) = list->MR_zones_tail;
-    MR_CONTEXT(MR_ctxt_maxfr) = orig_maxfr;
-    MR_GC_free(list);
-
-#ifdef  MR_DEBUG_STACK_SEGMENTS
-    printf("restore old nondet segment: new zone %p, new maxfr %p\n",
-        MR_CONTEXT(MR_ctxt_nondetstack_zone), orig_maxfr);
-    printf("new maxfr: ");
-    MR_printnondetstack(orig_maxfr);
-    printf("new succip: ");
-    MR_printlabel(stdout, orig_succip);
-#endif
-
-    MR_maxfr_word = (MR_Word) orig_maxfr;
-    MR_GOTO(orig_succip);
-}
-#else   /* ! MR_STACK_SEGMENTS */
-    MR_fatal_error("MR_pop_nondetstack_segment reached\n");
-#endif  /* MR_STACK_SEGMENTS */
-
 MR_END_MODULE
 
 #endif /* !MR_HIGHLEVEL_CODE */
diff --git a/runtime/mercury_stacks.h b/runtime/mercury_stacks.h
index 52c3a7a..220b643 100644
--- a/runtime/mercury_stacks.h
+++ b/runtime/mercury_stacks.h
@@ -106,18 +106,20 @@
                 MR_zone_extend_threshold;                                     \
             incr = MR_NONDET_FIXED_SIZE + (n);                                \
             new_maxfr = MR_maxfr + incr;                                      \
-            if (new_maxfr > threshold) {                                      \
+            if (MR_maxfr < MR_CONTEXT(MR_ctxt_nondetstack_zone->MR_zone_min)  \
+                || new_maxfr > threshold)                                     \
+            {                                                                 \
                 MR_save_registers();                                          \
-                new_maxfr = MR_new_nondetstack_segment(MR_maxfr, incr);       \
+                MR_nondetstack_segment_extend_slow_path(MR_maxfr, incr);      \
                 MR_restore_registers();                                       \
-                MR_succip_word =                                              \
-                    (MR_Word) MR_ENTRY(MR_pop_nondetstack_segment);           \
+            } else {                                                          \
+                MR_maxfr_word = (MR_Word) new_maxfr;                          \
             }                                                                 \
-            MR_maxfr_word = (MR_Word) new_maxfr;                              \
         } while (0)
 
-  extern    MR_Word         *MR_new_detstack_segment(MR_Word *sp, int n);
-  extern    MR_Word         *MR_new_nondetstack_segment(MR_Word *maxfr, int n);
+  extern    MR_Word     *MR_new_detstack_segment(MR_Word *sp, int n);
+  extern    void        MR_nondetstack_segment_extend_slow_path(
+                            MR_Word *old_maxfr, int n);
 
 #else   /* !MR_STACK_SEGMENTS */
 


--------------------------------------------------------------------------
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
--------------------------------------------------------------------------



More information about the reviews mailing list