diff --git a/runtime/mercury_memory_zones.c b/runtime/mercury_memory_zones.c
index 47b3420..6b64b23 100644
--- a/runtime/mercury_memory_zones.c
+++ b/runtime/mercury_memory_zones.c
@@ -436,6 +436,10 @@ MR_unget_zone(MR_MemoryZone *zone)
     assert(res == 0);
   #endif
 
+    /* XXX for debugging */
+    memset(zone->MR_zone_bottom, 0xff,
+        ((char *) zone->MR_zone_top) - ((char *) zone->MR_zone_bottom));
+
     MR_dealloc_zone_memory(zone->MR_zone_bottom,
         ((char *) zone->MR_zone_top) - ((char *) zone->MR_zone_bottom));
 
@@ -489,6 +493,11 @@ MR_next_offset(void)
 {
     size_t offset;
 
+    /* XXX on really small stacks, an offset can cause us to start past the
+     * stack threshold so disable it while testing
+     */
+    return 0;
+
     MR_OBTAIN_GLOBAL_LOCK("MR_next_offset");
     offset = offset_vector[offset_counter];
     offset_counter = (offset_counter + 1) % (CACHE_SLICES - 1);
@@ -531,7 +540,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 +660,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 +671,15 @@ 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;
+    }
+    assert(zone->MR_zone_min < zone->MR_zone_redzone);
+
     res = MR_protect_pages((char *) zone->MR_zone_redzone, redsize + MR_unit,
         REDZONE_PROT);
     if (res < 0) {
@@ -697,6 +716,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_stacks.c b/runtime/mercury_stacks.c
index da11e2f..2277ad9 100644
--- a/runtime/mercury_stacks.c
+++ b/runtime/mercury_stacks.c
@@ -212,8 +212,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 +222,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,8 +245,8 @@ 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
 
@@ -259,10 +260,19 @@ MR_new_nondetstack_segment(MR_Word *maxfr, int n)
     MR_MemoryZones  *list;
     MR_MemoryZone   *new_zone;
 
+    {
+        static int first = 1;
+        if (first) {
+            printf("MR_new_nondetstack_segment called\n");
+            first = 0;
+        }
+    }
+
     old_maxfr = maxfr;
 
+    /* We perform explicit overflow checks so redzones just waste space. */
     new_zone = MR_create_zone("nondetstack_segment", 0, MR_nondetstack_size, 0,
-        MR_nondetstack_zone_size, MR_default_handler);
+        0, MR_default_handler);
 
     list = MR_GC_malloc_uncollectable(sizeof(MR_MemoryZones));
 
@@ -270,8 +280,8 @@ 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_printnondetstack(stdout, old_maxfr);
+    printf(", old succip: ");
     MR_printlabel(stdout, MR_succip);
 #endif
 
@@ -282,19 +292,26 @@ MR_new_nondetstack_segment(MR_Word *maxfr, int n)
     MR_CONTEXT(MR_ctxt_maxfr) =
         MR_CONTEXT(MR_ctxt_nondetstack_zone)->MR_zone_min;
 
+    /* Point maxfr at the base of the new stack segment. */
     MR_maxfr_word = (MR_Word) MR_CONTEXT(MR_ctxt_maxfr);
 
-    MR_mkframe("new_nondetstack_segment", 1, MR_ENTRY(MR_do_fail));
+    assert(MR_maxfr < (MR_Word *) MR_CONTEXT(MR_ctxt_nondetstack_zone)->
+        MR_zone_extend_threshold);
+
+    /* Create a stub frame. */
+    MR_mkframe("new_nondetstack_segment", 1, MR_ENTRY(MR_do_not_reached));
     MR_framevar(1) = (MR_Word) old_maxfr;
+    assert(MR_succip == MR_succip_slot(MR_maxfr));
 
-    MR_maxfr_word = (MR_Word) (MR_maxfr + (MR_NONDET_FIXED_SIZE + (n)));
+    /* Create the real frame. */
+    MR_maxfr_word = (MR_Word) (MR_maxfr + MR_NONDET_FIXED_SIZE + n);
 
 #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_printnondetstack(stdout, MR_maxfr);
+    printf(", new succip: ");
     MR_printlabel(stdout, MR_ENTRY(MR_pop_nondetstack_segment));
 #endif
 
@@ -325,8 +342,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 +359,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
 
@@ -358,18 +375,50 @@ MR_define_entry(MR_pop_nondetstack_segment);
 #ifdef MR_STACK_SEGMENTS
 {
     MR_MemoryZones  *list;
+    MR_Word         *stub_fr;
     MR_Word         *orig_maxfr;
     MR_Code         *orig_succip;
 
-    orig_maxfr = (MR_Word *) MR_stackvar(1);
-    orig_succip = (MR_Code *) MR_stackvar(2);
+    /*
+    ** MR_curfr points at the frame that it would be pointing at,
+    ** had the stub frame not been present.
+    */
+
+    stub_fr = MR_CONTEXT(MR_ctxt_nondetstack_zone)->MR_zone_min
+        + MR_NONDET_FIXED_SIZE + 1;
+
+#if 0
+    if (MR_maxfr != stub_fr) {
+        MR_Word *fr;
+
+        /* stub_fr seems to give the right succip */
+        fr = stub_fr;
+
+        printf("not popping, jumping to %p instead, curfr = %p\n",
+            MR_succip_slot(fr), MR_curfr);
+        MR_GOTO(MR_succip_slot(fr));
+    }
+#endif
+
+    orig_maxfr = (MR_Word *) MR_based_framevar(stub_fr, 1);
+    /* XXX shouldn't this be true? */
+    /* orig_maxfr = MR_prevfr_slot(stub_fr); */
+    orig_succip = (MR_Code *) MR_succip_slot(stub_fr);
+    assert(MR_curfr == MR_succfr_slot(stub_fr));
+
+    assert(
+        orig_maxfr < (MR_Word *) MR_CONTEXT(MR_ctxt_nondetstack_zone)->
+            MR_zone_min ||
+        orig_maxfr > (MR_Word *) MR_CONTEXT(MR_ctxt_nondetstack_zone)->
+            MR_zone_extend_threshold
+    );
 
 #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_printnondetstack(stdout, MR_maxfr);
+    printf(", old succip: ");
     MR_printlabel(stdout, MR_succip);
 #endif
 
@@ -378,6 +427,7 @@ MR_define_entry(MR_pop_nondetstack_segment);
     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;
+    /* XXX do we need this? */
     MR_CONTEXT(MR_ctxt_maxfr) = orig_maxfr;
     MR_GC_free(list);
 
@@ -385,8 +435,8 @@ MR_define_entry(MR_pop_nondetstack_segment);
     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_printnondetstack(stdout, orig_maxfr);
+    printf(", new succip: ");
     MR_printlabel(stdout, orig_succip);
 #endif
 
diff --git a/runtime/mercury_stacks.h b/runtime/mercury_stacks.h
index 52c3a7a..546813e 100644
--- a/runtime/mercury_stacks.h
+++ b/runtime/mercury_stacks.h
@@ -98,17 +98,16 @@
 
   #define MR_nondetstack_extend_and_check(n)                                  \
         do {                                                                  \
+            const int extend_n = (n);                                         \
             MR_Word *new_maxfr;                                               \
             MR_Word *threshold;                                               \
-            int     incr;                                                     \
                                                                               \
             threshold = (MR_Word *) MR_CONTEXT(MR_ctxt_nondetstack_zone)->    \
                 MR_zone_extend_threshold;                                     \
-            incr = MR_NONDET_FIXED_SIZE + (n);                                \
-            new_maxfr = MR_maxfr + incr;                                      \
+            new_maxfr = MR_maxfr + MR_NONDET_FIXED_SIZE + extend_n;           \
             if (new_maxfr > threshold) {                                      \
                 MR_save_registers();                                          \
-                new_maxfr = MR_new_nondetstack_segment(MR_maxfr, incr);       \
+                new_maxfr = MR_new_nondetstack_segment(MR_maxfr, extend_n);   \
                 MR_restore_registers();                                       \
                 MR_succip_word =                                              \
                     (MR_Word) MR_ENTRY(MR_pop_nondetstack_segment);           \
@@ -349,16 +348,19 @@ MR_declare_entry(MR_pop_nondetstack_segment);
     do {                                                                      \
         MR_Word *prevfr;                                                      \
         MR_Word *succfr;                                                      \
+        MR_Code *save_succip;                                                 \
                                                                               \
         prevfr = MR_maxfr;                                                    \
         succfr = MR_curfr;                                                    \
-        MR_nondetstack_extend_and_check(numslots);                            \
+        save_succip = MR_succip;                                              \
+        MR_nondetstack_extend_and_check(numslots); /* can change succip */    \
         MR_nondetstack_post_extend_check();                                   \
         MR_curfr_word = MR_maxfr_word;                                        \
         MR_prevfr_slot_word(MR_curfr) = (MR_Word) prevfr;                     \
         MR_succip_slot_word(MR_curfr) = (MR_Word) MR_succip;                  \
         MR_succfr_slot_word(MR_curfr) = (MR_Word) succfr;                     \
         MR_redofr_slot_word(MR_curfr) = MR_curfr_word;                        \
+        MR_succip_word = (MR_Word) save_succip;                               \
         MR_maybe_fill_table_detfr_slot();                                     \
         MR_debugmkframe(predname);                                            \
         MR_nondetstack_overflow_check();                                      \
diff --git a/t/nondet_stseg.m b/t/nondet_stseg.m
new file mode 100644
index 0000000..70331a9
--- /dev/null
+++ b/t/nondet_stseg.m
@@ -0,0 +1,92 @@
+%-----------------------------------------------------------------------------%
+% Test nondet stack segments.
+
+% MERCURY_OPTIONS='--nondetstack-size 8 --nondetstack-redzone-size 1 -C1' ./nondet_stseg
+
+:- module nondet_stseg.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module int.
+:- import_module list.
+
+%-----------------------------------------------------------------------------%
+
+main(!IO) :-
+    % Do a lot of nondet stuff.
+    A = [1, 2],
+    B = [10, 20, 30],
+    (
+        l_perm(A, As),
+        trace [io(!IO)] (
+            io.write_string("As = ", !IO),
+            io.write(As, !IO),
+            io.nl(!IO)
+        ),
+        l_perm(B, Bs),
+        trace [io(!IO)] (
+            io.write_string("Bs = ", !IO),
+            io.write(Bs, !IO),
+            io.nl(!IO)
+        ),
+        l_perm(Bs, Cs),
+        l_perm(Cs, Ds),
+        l_perm(Ds, Es),     % 2592
+        l_perm(Es, Fs),     % 15552
+        l_perm(Fs, Gs),     % 93312
+        l_perm(Gs, Hs),     % should be 559872, got 559205
+        trace [io(!IO)] (
+            io.write_string("\tHs = ", !IO),
+            io.write(Hs, !IO),
+            io.nl(!IO),
+            incr(!IO)
+        ),
+        As = Hs
+    ->
+        io.write_string("equal lists\n", !IO)
+    ;
+        io.write_string("not equal lists\n", !IO)
+    ),
+
+    get_n(N, !IO),
+    io.write_int(N, !IO),
+    io.write_string(" should equal 559872\n", !IO).
+
+:- mutable(n, int, 0, ground, [untrailed, attach_to_io_state]).
+
+:- pred incr(io::di, io::uo) is det.
+
+incr(!IO) :-
+    get_n(N, !IO),
+    set_n(N + 1, !IO).
+
+% Reproduce list.m procedures for easier debugging.
+
+:- pred l_perm(list(T)::in, list(T)::out) is multi.
+
+l_perm([], []).
+l_perm([X | Xs], Ys) :-
+    l_perm(Xs, Ys0),
+    l_insert(X, Ys0, Ys).
+
+:- pred l_insert(T::in, list(T)::in, list(T)::out) is multi.
+
+l_insert(Elem, List0, List) :-
+    l_delete(List, Elem, List0).
+
+:- pred l_delete(list(T)::out, T::in, list(T)::in) is multi.
+
+l_delete([X | L], X, L).
+l_delete([X | Xs], Y, [X | L]) :-
+    l_delete(Xs, Y, L).
+
+%-----------------------------------------------------------------------------%
+% vi: ft=mercury ts=8 sts=4 sw=4 et