[MLton] cvs commit: improved GC structure

Matthew Fluet fluet@mlton.org
Tue, 6 Apr 2004 17:47:48 -0700


fluet       04/04/06 17:47:48

  Modified:    include  c-main.h x86-main.h
               runtime  gc.c gc.h
               runtime/basis Thread.c
  Log:
  MAIL improved GC structure
  
  This implements the various GC improvements discussed over the last
  few days:
   - revise the mutator invariants to the following:
  
      static bool mutatorFrontierInvariant (GC_state s) {
              return (s->currentThread->bytesNeeded <=
                              s->limitPlusSlop - s->frontier);
      }
  
      static bool mutatorStackInvariant (GC_state s) {
              return (stackTop (s, s->currentThread->stack) <=
                              stackLimit (s, s->currentThread->stack) +
                              topFrameSize (s, s->currentThread->stack));
      }
  
     Note that these invariants are relative to the currentThread.
   - ensure the mutator invariants _after_ switching threads (possibly
      to the signal handler thread); note that the
      mutatorFrontierInvariant is only ensured after a runtime call that
      ensuresBytesFree.
   - for heap stacks, allow shrinking down to stack->used (modulo
      alignment).
   - both GC_copyCurrentThread and GC_copyThread create a minimal sized
      thread (i.e., stack->reserved == stack->used).
   - modified the stack growth algorithm to choose the maximum size of
      twice the current size and the size necessary to satisfy the
      mutator invariant.  (Because copied threads are copied with a
      minimal size, possibly with exactly one (small) stack frame on
      them, then doubling the size may not satisfy the mutator stack
      invariant.)
   - moved sending of GC signal to doGC.
   - folded Thread_switchTo into GC_threadSwitchTo.
  
  Some additional details:
   - I did not attempt to fold the growth of the current stack into
      forward; it's not clear to me how to do it properly -- note that
      it only applies when doing a major copying GC.  If we need to do a
      major mark compact GC, then we really need to copy the stack after
      the compaction.
   - I modified the stack shrinking policy:
      + for the current stacks, if stack->used <= stack->reserved / 4,
         then shrink to stack->reserved / 2 (subject to the mutator
         stack invariant).
      + for heap stacks, if stack->used <= stack->reserved / 4,
         then shrink to stack->reserved / 2,
         else if stack->used <= stack->reserved / 2,
         then shink to stack->used.
        This allows stacks to shrink down to the minimal size, if they
        live through multiple GCs.

Revision  Changes    Path
1.9       +2 -2      mlton/include/c-main.h

Index: c-main.h
===================================================================
RCS file: /cvsroot/mlton/mlton/include/c-main.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- c-main.h	2 Apr 2004 02:49:52 -0000	1.8
+++ c-main.h	7 Apr 2004 00:47:47 -0000	1.9
@@ -18,14 +18,14 @@
 	s->savedThread = s->currentThread;				\
 	s->canHandle += 3;						\
 	/* Switch to the C Handler thread. */				\
-	GC_switchToThread (s, s->callFromCHandler);			\
+	GC_switchToThread (s, s->callFromCHandler, 0);			\
 	nextFun = *(int*)(s->stackTop - WORD_SIZE);			\
 	cont.nextChunk = nextChunks[nextFun];				\
 	returnToC = FALSE;						\
 	do {								\
  		cont=(*(struct cont(*)(void))cont.nextChunk)();		\
 	} while (not returnToC);					\
-	GC_switchToThread (s, s->savedThread);				\
+	GC_switchToThread (s, s->savedThread, 0);      			\
  	s->savedThread = BOGUS_THREAD;					\
 	if (DEBUG_CCODEGEN)						\
 		fprintf (stderr, "MLton_callFromC done\n");		\



1.12      +2 -2      mlton/include/x86-main.h

Index: x86-main.h
===================================================================
RCS file: /cvsroot/mlton/mlton/include/x86-main.h,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- x86-main.h	2 Apr 2004 02:49:52 -0000	1.11
+++ x86-main.h	7 Apr 2004 00:47:47 -0000	1.12
@@ -77,10 +77,10 @@
 	s->savedThread = s->currentThread;				\
 	s->canHandle += 3;						\
 	/* Return to the C Handler thread. */				\
-	GC_switchToThread (s, s->callFromCHandler);			\
+	GC_switchToThread (s, s->callFromCHandler, 0);			\
 	jump = *(pointer*)(s->stackTop - WORD_SIZE);			\
 	MLton_jumpToSML(jump);						\
-	GC_switchToThread (s, s->savedThread);				\
+	GC_switchToThread (s, s->savedThread, 0);      			\
 	s->savedThread = BOGUS_THREAD;					\
 	if (DEBUG_X86CODEGEN)						\
 		fprintf (stderr, "MLton_callFromC() done\n");		\



1.174     +147 -85   mlton/runtime/gc.c

Index: gc.c
===================================================================
RCS file: /cvsroot/mlton/mlton/runtime/gc.c,v
retrieving revision 1.173
retrieving revision 1.174
diff -u -r1.173 -r1.174
--- gc.c	4 Apr 2004 18:21:42 -0000	1.173
+++ gc.c	7 Apr 2004 00:47:47 -0000	1.174
@@ -746,9 +746,14 @@
 	return stackBottom (s, stack) + stack->used;
 }
 
+/* Pointer to the end of stack. */
+static inline pointer endOfStack (GC_state s, GC_stack stack) {
+	return stackBottom (s, stack) + stack->reserved;
+}
+
 /* The maximum value stackTop may take on. */
 static inline pointer stackLimit (GC_state s, GC_stack stack) {
-	return stackBottom (s, stack) + stack->reserved - stackSlop (s);
+	return endOfStack (s, stack) - stackSlop (s);
 }
 
 static inline bool stackIsEmpty (GC_stack stack) {
@@ -813,15 +818,6 @@
 	return stack->used + stackSlop (s) - topFrameSize (s, stack);
 }
 
-/* stackTopIsOk ensures that when this stack becomes current that 
- * the stackTop is less than the stackLimit.
- */
-static inline bool stackTopIsOk (GC_state s, GC_stack stack) {
-	return stackTop (s, stack) 
-		       	<= stackLimit (s, stack) 
-			+ (stackIsEmpty (stack) ? 0 : topFrameSize (s, stack));
-}
-
 #if ASSERT
 static bool hasBytesFree (GC_state s, W32 oldGen, W32 nursery) {
 	bool res;
@@ -1153,6 +1149,17 @@
 /*                            invariant                             */
 /* ---------------------------------------------------------------- */
 
+static bool mutatorFrontierInvariant (GC_state s) {
+	return (s->currentThread->bytesNeeded <= 
+			s->limitPlusSlop - s->frontier);
+}
+
+static bool mutatorStackInvariant (GC_state s) {
+	return (stackTop (s, s->currentThread->stack) <= 
+			stackLimit (s, s->currentThread->stack) + 
+			topFrameSize (s, s->currentThread->stack));
+}
+
 static bool ratiosOk (GC_state s) {
 	return 1.0 < s->growRatio
 			and 1.0 < s->nurseryRatio
@@ -1271,10 +1278,13 @@
 	return TRUE;
 }
 
-bool mutatorInvariant (GC_state s) {
+static bool mutatorInvariant (GC_state s, bool frontier, bool stack) {
 	if (DEBUG)
 		GC_display (s, stderr);
-	assert (stackTopIsOk (s, s->currentThread->stack));
+	if (frontier)
+		assert (mutatorFrontierInvariant(s));
+	if (stack)
+		assert (mutatorStackInvariant(s));
 	assert (invariant (s));
 	return TRUE;
 }
@@ -1335,8 +1345,11 @@
 void leave (GC_state s) {
 	if (DEBUG)
 		fprintf (stderr, "leave\n");
-	assert (mutatorInvariant (s));
-	if (s->signalIsPending and 0 == s->canHandle)
+	/* The mutator frontier invariant may not hold
+	 * for functions that don't ensureBytesFree.
+	 */
+	assert (mutatorInvariant (s, FALSE, TRUE));
+	if (s->canHandle == 0 and s->signalIsPending)
 		s->limit = 0;
 	unless (s->inSignalHandler)
 		unblockSignals (s);
@@ -1712,26 +1725,41 @@
 
 			assert (STACK_TAG == tag);
 			headerBytes = STACK_HEADER_SIZE;
-			/* Shrink stacks that don't use a lot of their reserved
-		 	 * space.
-			 */
 			stack = (GC_stack)p;
-			if (stack->used <= stack->reserved / 4) {
-				W32 new;
 
-				new = stackReserved
-					 (s, max (stack->reserved / 2, 
-							stackNeedsReserved (s, stack)));
-				/* It's possible that new > stack->reserved if
-				 * the stack is the current one and the stack
-				 * top isn't OK.  In that case, we want to leave
-				 * the stack alone, because some other part of
-				 * the gc will grow the stack.  We cannot do any
-				 * growing here because we may run out of to
-				 * space.
+			if (s->currentThread->stack == stack) {
+				/* Shrink stacks that don't use a lot 
+				 * of their reserved space;
+				 * but don't violate the stack invariant.
 				 */
-				if (new <= stack->reserved)
-					stack->reserved = new;
+				if (stack->used <= stack->reserved / 4) {
+					uint new = stackReserved (s, max (stack->reserved / 2,
+										stackNeedsReserved (s, stack)));
+					/* It's possible that new > stack->reserved if
+					 * the stack invariant is violated. In that case, 
+					 * we want to leave the stack alone, because some 
+					 * other part of the gc will grow the stack.  We 
+					 * cannot do any growing here because we may run 
+					 * out of to space.
+					 */
+					if (new <= stack->reserved) {
+						stack->reserved = new;
+						if (DEBUG_STACKS)
+							fprintf (stderr, "Shrinking stack to size %s.\n",
+									uintToCommaString (stack->reserved));
+					}
+				}
+			} else {
+				/* Shrink heap stacks that don't use a 
+				 * lot of their reserved space.
+				 */
+				if (stack->used <= stack->reserved / 4)
+					stack->reserved = stackReserved (s, stack->reserved / 2);
+				else if (stack->used <= stack->reserved / 2)
+					stack->reserved = stackReserved (s, stack->used);
+				if (DEBUG_STACKS)
+					fprintf (stderr, "Shrinking stack to size %s.\n",
+							uintToCommaString (stack->reserved));
 			}
 			objectBytes = sizeof (struct GC_stack) + stack->used;
 			skip = stack->reserved - stack->used;
@@ -2902,7 +2930,8 @@
 	uint size;
 	GC_stack stack;
 
-	size = 2 * s->currentThread->stack->reserved;
+	size = max(2 * s->currentThread->stack->reserved, 
+			stackNeedsReserved (s, s->currentThread->stack));
 	if (DEBUG_STACKS or s->messages)
 		fprintf (stderr, "Growing stack to size %s.\n",
 				uintToCommaString (stackBytes (s, size)));
@@ -2998,11 +3027,12 @@
 	if (needGCTime (s))
 		startTiming (&ru_start);
 	minorGC (s);
-	stackTopOk = stackTopIsOk (s, s->currentThread->stack);
+	stackTopOk = mutatorStackInvariant(s);
 	stackBytesRequested =
 		stackTopOk
 		? 0 
-		: stackBytes (s, 2 * s->currentThread->stack->reserved);
+		: stackBytes (s, max(2 * s->currentThread->stack->reserved, 
+					stackNeedsReserved (s, s->currentThread->stack)));
 	totalBytesRequested = 
 		(W64)oldGenBytesRequested 
 		+ stackBytesRequested
@@ -3030,6 +3060,14 @@
 				100.0 * ((double) s->oldGenSize) 
 					/ s->heap.size);
 	}
+	/* Send a GC signal. */
+	if (s->handleGCSignal and s->signalHandler != BOGUS_THREAD) {
+		if (DEBUG_SIGNALS)
+			fprintf (stderr, "GC Signal pending.\n");
+		s->gcSignalIsPending = TRUE;
+		unless (s->inSignalHandler) 
+			s->signalIsPending = TRUE;
+	}
 	if (DEBUG) 
 		GC_display (s, stderr);
 	assert (hasBytesFree (s, oldGenBytesRequested, nurseryBytesRequested));
@@ -3037,6 +3075,17 @@
 	leaveGC (s);
 }
 
+static inline void ensureMutatorInvariant (GC_state s, bool force) {
+	if (force
+		or not (mutatorFrontierInvariant(s))
+		or not (mutatorStackInvariant(s))) {
+		/* This GC will grow the stack, if necessary. */
+		doGC (s, 0, s->currentThread->bytesNeeded, force, TRUE);
+	}
+	assert (mutatorFrontierInvariant(s));
+	assert (mutatorStackInvariant(s));
+}
+
 /* ensureFree (s, b) ensures that upon return
  *      b <= s->limitPlusSlop - s->frontier
  */
@@ -3051,12 +3100,8 @@
 	if (DEBUG_THREADS)
 		fprintf (stderr, "switchToThread (0x%08x)  used = %u  reserved = %u\n", 
 				(uint)t, t->stack->used, t->stack->reserved);
-	assert (stackTopIsOk (s, t->stack));
 	s->currentThread = t;
 	setStack (s);
-	ensureFree (s, t->bytesNeeded);
-	/* Can not refer to t, because ensureFree may have GC'ed. */
-	assert (s->currentThread->bytesNeeded <= s->limitPlusSlop - s->frontier);
 }
 
 static void startHandler (GC_state s) {
@@ -3065,7 +3110,7 @@
 		fprintf (stderr, "switching to signal handler\n");
 		GC_display (s, stderr);
 	}
-	assert (0 == s->canHandle);
+	assert (s->canHandle == 0);
 	assert (s->signalIsPending);
 	s->signalIsPending = FALSE;
 	s->inSignalHandler = TRUE;
@@ -3077,35 +3122,52 @@
 	s->canHandle = 1;
 }
 
-void GC_switchToThread (GC_state s, GC_thread t) {
+void GC_switchToThread (GC_state s, GC_thread t, uint ensureBytesFree) {
 	if (DEBUG_THREADS)
-		fprintf (stderr, "GC_switchToThread (0x%08x)\n", (uint)t);
-	if (TRUE) {
+		fprintf (stderr, "GC_switchToThread (0x%08x, %u)\n", (uint)t, ensureBytesFree);
+	if (FALSE) {
 		/* This branch is slower than the else branch, especially 
 		 * when debugging is turned on, because it does an invariant
 		 * check on every thread switch.
 		 * So, we'll stick with the else branch for now.
 		 */
 	 	enter (s);
-	  	switchToThread (s, t);
+		s->currentThread->bytesNeeded = ensureBytesFree;
+		switchToThread (s, t);
 		s->canHandle--;
-		if (0 == s->canHandle and s->signalIsPending) {
-			startHandler(s);
-			switchToThread(s, s->signalHandler);
-		}
+		if (s->canHandle == 0 and s->signalIsPending) {
+			startHandler (s);
+			switchToThread (s, s->signalHandler);
+		}
+		ensureMutatorInvariant (s, FALSE);
+		assert (mutatorFrontierInvariant(s));
+		assert (mutatorStackInvariant(s));
 	 	leave (s);
 	} else {
+		/* BEGIN: enter(s); */
 		s->currentThread->stack->used = currentStackUsed (s);
-		s->currentThread = t;
-		setStack (s);
-		if (t->bytesNeeded > s->limitPlusSlop - s->frontier)  {
-			enter (s);
-			doGC (s, 0, t->bytesNeeded, FALSE, TRUE);
-			leave (s);
-		}
+		s->currentThread->exnStack = s->exnStack;
+		/* END: enter(s); */
+		switchToThread (s, t);
+		s->canHandle--;
+		if (s->canHandle == 0 and s->signalIsPending) {
+			startHandler (s);
+			switchToThread (s, s->signalHandler);
+		}
+		/* BEGIN: ensureMutatorInvariant */
+		if (not (mutatorFrontierInvariant(s))
+			or not (mutatorStackInvariant(s))) {
+			enter(s);
+			/* This GC will grow the stack, if necessary. */
+			doGC (s, 0, s->currentThread->bytesNeeded, FALSE, TRUE);
+			leave(s);
+		}
+		/* END: ensureMutatorInvariant */
+		/* BEGIN: leave(s); */
+		/* END: leave(s); */
 	}
-	/* Can not refer to t, because we may have GC'ed. */
-	assert (s->currentThread->bytesNeeded <= s->limitPlusSlop - s->frontier);
+	assert (mutatorFrontierInvariant(s));
+	assert (mutatorStackInvariant(s));
 }
 
 /* GC_startHandler does not do an enter()/leave(), even though it is exported.
@@ -3133,24 +3195,13 @@
 	if (0 == bytesRequested)
 		bytesRequested = LIMIT_SLOP;
 	s->currentThread->bytesNeeded = bytesRequested;
-	if (force 
-		or bytesRequested > s->limitPlusSlop - s->frontier
-		or not (stackTopIsOk (s, s->currentThread->stack))) {
-		/* This GC will grow the stack, if necessary. */
-		doGC (s, 0, bytesRequested, force, TRUE);	
-		/* Send a GC signal. */
-		if (s->handleGCSignal and BOGUS_THREAD != s->signalHandler) {
-			if (DEBUG_SIGNALS)
-				fprintf (stderr, "GC Signal pending\n");
-			s->gcSignalIsPending = TRUE;
-			unless (s->inSignalHandler)
-				s->signalIsPending = TRUE;
-		}
-	} else {
-		startHandler (s);
+	if (s->canHandle == 0 and s->signalIsPending) {
+		startHandler(s);
 		switchToThread (s, s->signalHandler);
 	}
-	assert (s->currentThread->bytesNeeded <= s->limitPlusSlop - s->frontier);
+	ensureMutatorInvariant (s, force);
+	assert (mutatorFrontierInvariant(s));
+	assert (mutatorStackInvariant(s));
 	leave (s);
 }
 
@@ -3251,10 +3302,6 @@
 	return res;
 }
 
-static inline uint initialThreadBytes (GC_state s) {
-	return threadBytes (s) + stackBytes (s, initialStackSize (s));
-}
-
 static GC_thread newThreadOfSize (GC_state s, uint stackSize) {
 	GC_stack stack;
 	GC_thread t;
@@ -3295,8 +3342,8 @@
 }
 
 void GC_copyCurrentThread (GC_state s) {
-	GC_thread t;
 	GC_thread res;
+	GC_thread t;
 	
 	if (DEBUG_THREADS)
 		fprintf (stderr, "GC_copyCurrentThread\n");
@@ -3307,6 +3354,7 @@
  * the reserved to be slightly larger than the used.
  */
 /*	assert (res->stack->reserved == res->stack->used); */
+	assert (res->stack->reserved >= res->stack->used);
 	leave (s);
 	if (DEBUG_THREADS)
 		fprintf (stderr, "0x%08x = GC_copyCurrentThread\n", (uint)res);
@@ -3317,14 +3365,24 @@
 	GC_thread res;
 	GC_thread t;
 
-	t = (GC_thread)thread;
 	if (DEBUG_THREADS)
-		fprintf (stderr, "GC_copyThread (0x%08x)\n", (uint)t);
+		fprintf (stderr, "GC_copyThread (0x%08x)\n", (uint)thread);
 	enter (s);
+	t = (GC_thread)thread;
+/* The following assert is no longer true, since alignment restrictions can force
+ * the reserved to be slightly larger than the used.
+ */
 /*	assert (t->stack->reserved == t->stack->used); */
-	res = copyThread (s, t, stackNeedsReserved (s, t->stack));
-	assert (stackTopIsOk (s, res->stack));
+	assert (t->stack->reserved >= t->stack->used);
+	res = copyThread (s, t, t->stack->used);
+/* The following assert is no longer true, since alignment restrictions can force
+ * the reserved to be slightly larger than the used.
+ */
+/*	assert (res->stack->reserved == res->stack->used); */
+	assert (res->stack->reserved >= res->stack->used);
 	leave (s);
+	if (DEBUG_THREADS)
+		fprintf (stderr, "0x%08x = GC_copyThread (0x%08x)\n", (uint)res, (uint)thread);
 	return (pointer)res;
 }
 
@@ -4432,14 +4490,18 @@
 		atexit (profileEnd);
 	} else
 		s->profilingIsOn = FALSE;
-	if (s->isOriginal)
+	if (s->isOriginal) {
 		newWorld (s);
-	else {
+		/* The mutator stack invariant doesn't hold,
+		 * because the mutator has yet to run.
+		 */
+		assert (mutatorInvariant(s, TRUE, FALSE));
+	} else {
 		loadWorld (s, worldFile);
 		if (s->profilingIsOn and s->profileStack)
 			GC_foreachStackFrame (s, enterFrame);
+		assert (mutatorInvariant(s, TRUE, TRUE));
 	}
-	assert (mutatorInvariant (s));
 	s->amInGC = FALSE;
 	return i;
 }
@@ -4542,7 +4604,7 @@
 	if (DEBUG_SIGNALS)
 		fprintf (stderr, "GC_handler signum = %d\n", signum);
 	assert (sigismember (&s->signalsHandled, signum));
-	if (0 == s->canHandle)
+	if (s->canHandle == 0)
 		s->limit = 0;
 	s->signalIsPending = TRUE;
 	sigaddset (&s->signalsPending, signum);



1.73      +1 -1      mlton/runtime/gc.h

Index: gc.h
===================================================================
RCS file: /cvsroot/mlton/mlton/runtime/gc.h,v
retrieving revision 1.72
retrieving revision 1.73
diff -u -r1.72 -r1.73
--- gc.h	4 Apr 2004 18:21:42 -0000	1.72
+++ gc.h	7 Apr 2004 00:47:47 -0000	1.73
@@ -676,7 +676,7 @@
  */
 void GC_startHandler (GC_state s);
 
-void GC_switchToThread (GC_state s, GC_thread t);
+void GC_switchToThread (GC_state s, GC_thread t, uint ensureBytesFree);
 
 void GC_unpack (GC_state s);
 



1.13      +1 -6      mlton/runtime/basis/Thread.c

Index: Thread.c
===================================================================
RCS file: /cvsroot/mlton/mlton/runtime/basis/Thread.c,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -r1.12 -r1.13
--- Thread.c	2 Apr 2004 02:49:52 -0000	1.12
+++ Thread.c	7 Apr 2004 00:47:48 -0000	1.13
@@ -50,13 +50,8 @@
 }
 
 void Thread_switchTo (Thread thread, Word ensureBytesFree) {
-	GC_state s;
-
 	if (DEBUG_THREAD)
 		fprintf (stderr, "Thread_switchTo (0x%08x, %u)\n",
 				(uint)thread, (uint)ensureBytesFree);
-	s = &gcState;
-	s->currentThread->stack->used = s->stackTop - s->stackBottom;
-	s->currentThread->bytesNeeded = ensureBytesFree;
-	GC_switchToThread (s, (GC_thread)thread);
+	GC_switchToThread (&gcState, (GC_thread)thread, ensureBytesFree);
 }