[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);
}