Runtime bug? and other questions
Stephen Weeks
sweeks@intertrust.com
Wed, 26 Jan 2000 12:15:45 -0800 (PST)
> Hmm looks like the bug is still there.... but only manifests itself when I
> *don't* compile with -DGC_EVERY_CHECK
Found the bug. I've appended the fixed gc.c to the end of this
message. The problem was due to the stack resizing code in forward.
When the stack was grown, the entire new stack size bytes were copied
from fromSpace instead of just copying the part of the stack that was
used. The new code only copies the used part of the stack and bumps
the back of the queue in toSpace by a "skip" amount (which is only
nonzero for stacks). Your example now works. Lemme know if there are
more problems. Doubtless this are, since this runtime is so
untested.
--------------------------------------------------------------------------------
/* Copyright (C) 1997-1999 NEC Research Institute.
* Please see the file LICENSE for license information.
*/
#include "gc.h"
#include <sys/mman.h>
#include <sys/resource.h>
#include <fcntl.h>
#include <string.h>
#include <values.h>
enum {
BOGUS_EXN_STACK = 0xFFFFFFFF,
BOGUS_POINTER = 0x1,
DEBUG = FALSE,
FORWARDED = 0xFFFFFFFF,
STACK_HEADER_SIZE = WORD_SIZE,
HEADER_SIZE = WORD_SIZE,
STACK_HEADER = 0x3FFFFFFF,
};
#define BOGUS_THREAD (GC_thread)BOGUS_POINTER
#define STRING_HEADER GC_arrayHeader(1, 0)
#define WORD8_VECTOR_HEADER GC_arrayHeader(1, 0)
#define THREAD_HEADER GC_objectHeader(1, 1)
static void doGC(GC_state s, uint bytesRequested, uint stackBytesRequested);
static void enter(GC_state s);
static void leave(GC_state s);
static inline void splitHeader(word header, uint *numPointers,
uint *numNonPointers) {
*numPointers = header & ONES(POINTER_BITS);
*numNonPointers =
(header >> NON_POINTERS_SHIFT) & ONES(NON_POINTER_BITS);
}
static inline bool isNormal(word header) {
return header & HIGH_BIT;
}
/* Return a pointer to the header for the object pointed to by p. */
static inline word* getHeaderp(pointer p) {
return (word*)(p - WORD_SIZE);
}
/* Return the header for the object pointed to by p. */
static inline word getHeader(pointer p) {
return *(getHeaderp(p));
}
static inline uint toBytes(uint n) {
return n << 2;
}
static inline bool isWordAligned(uint x) {
return 0 == (x & 0x3);
}
typedef void (*pointerFun)(GC_state s, pointer *p);
static inline uint min(uint x, uint y) {
return ((x < y) ? x : y);
}
static inline uint max(uint x, uint y) {
return ((x > y) ? x : y);
}
/* ------------------------------------------------- */
/* Safe mmap and munmap */
/* ------------------------------------------------- */
static void *smmap(size_t length) {
void *result;
result = mmap(NULL, length, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANON, -1, 0);
if (result == (void*)-1)
die("mmap failed");
return result;
}
static void smunmap(pointer base, size_t length) {
if (0 == length)
return;
if (0 != munmap(base, length))
die("munmap failed");
}
/* ------------------------------------------------- */
/* roundPage */
/* ------------------------------------------------- */
/*
* Round size up to a multiple of the size of a page.
*/
static size_t roundPage(size_t size)
{
static size_t psize;
psize = getpagesize();
size += psize - 1;
size -= size % psize;
return (size);
}
/* ------------------------------------------------- */
/* allocate */
/* ------------------------------------------------- */
static void ensureFree(GC_state s, uint bytesRequested) {
if (s->frontier + bytesRequested > s-> limit) {
doGC(s, bytesRequested, 0);
}
}
static pointer allocate(GC_state s, uint header, uint bytesRequested) {
pointer result;
bytesRequested = wordAlign(bytesRequested);
ensureFree(s, HEADER_SIZE + bytesRequested);
*(uint*)s->frontier = header;
result = s->frontier + HEADER_SIZE;
s->frontier = result + bytesRequested;
assert(isWordAligned((uint)s->frontier));
return result;
}
/* ------------------------------------------------- */
/* Stacks */
/* ------------------------------------------------- */
/* stackSlop returns the amount of "slop" space needed between the top of
* the stack and the end of the stack space.
*/
static inline uint stackSlop(GC_state s) {
return 2 * s->maxFrameSize;
}
static pointer stackBottom(GC_stack stack) {
return ((pointer)stack) + sizeof(struct GC_stack);
}
/* Pointer to the topmost word in use on the stack. */
static pointer stackTop(GC_stack stack) {
return stackBottom(stack) + stack->used - WORD_SIZE;
}
/* The maximum value stackTop may take on. */
static pointer stackLimit(GC_state s, GC_stack stack) {
return stackBottom(stack) + stack->reserved - stackSlop(s);
}
/* Number of bytes used by the stack. */
static uint currentStackUsed(GC_state s) {
return s->stackTop + WORD_SIZE - s->stackBottom;
}
static uint topFrameSize(GC_state s, GC_stack stack) {
return s->frameLayouts[*(uint*)stackTop(stack)].numBytes;
}
/* stackTopIsOk ensures that when this stack becomes current that
* the stackTop is less than the stackLimit.
*/
static bool stackTopIsOk(GC_state s, GC_stack stack) {
return stackTop(stack) <= stackLimit(s, stack) + topFrameSize(s, stack);
}
static GC_stack newStack(GC_state s, uint size) {
GC_stack stack;
stack = (GC_stack)allocate(s, STACK_HEADER,
size + sizeof(struct GC_stack));
stack->reserved = size;
stack->used = 0;
return stack;
}
static void setStack(GC_state s) {
GC_stack stack;
/* Why was this test here? */
/* if (s->currentThread != BOGUS_THREAD) { */
stack = s->currentThread->stack;
s->stackBottom = stackBottom(stack);
s->stackTop = stackTop(stack);
s->stackLimit = stackLimit(s, stack);
}
static void stackCopy(GC_stack from, GC_stack to) {
to->used = from->used;
memmove(stackBottom(to), stackBottom(from), from->used);
}
/* ------------------------------------------------- */
/* Threads */
/* ------------------------------------------------- */
static uint initialStackBytes(GC_state s) {
return stackSlop(s);
}
static uint initialThreadBytes(GC_state s) {
return HEADER_SIZE
+ sizeof(struct GC_thread)
+ HEADER_SIZE
+ sizeof(struct GC_stack)
+ initialStackBytes(s);
}
static GC_thread newThreadOfSize(GC_state s, uint stackSize) {
GC_stack stack;
GC_thread t;
stack = newStack(s, stackSize);
t = (GC_thread)allocate(s, THREAD_HEADER, sizeof(struct GC_thread));
t->exnStack = BOGUS_EXN_STACK;
t->stack = stack;
return t;
}
static void switchToThread(GC_state s, GC_thread t) {
/* s->savedThread = s->currentThread; */
s->currentThread = t;
setStack(s);
}
void GC_switchToThread(GC_state s, GC_thread t) {
enter(s);
switchToThread(s, t);
leave(s);
}
static void copyThread(GC_state s, GC_thread from, uint size) {
GC_thread to;
/* newThreadOfSize may do a GC, which invalidates from.
* Hence we need to stash from where the GC can find it.
*/
s->savedThread = from;
to = newThreadOfSize(s, size);
from = s->savedThread;
stackCopy(from->stack, to->stack);
to->exnStack = from->exnStack;
s->savedThread = to;
}
void GC_copyThreadShrink(GC_state s, GC_thread t) {
enter(s);
copyThread(s, t, t->stack->used);
leave(s);
}
uint stackNeedsReserved(GC_state s, GC_stack stack) {
return stack->used + stackSlop(s) - topFrameSize(s, stack);
}
void GC_copyThread(GC_state s, GC_thread t) {
enter(s);
assert(t->stack->reserved == t->stack->used);
copyThread(s, t, stackNeedsReserved(s, t->stack));
leave(s);
}
/* ------------------------------------------------- */
/* fromSpace, toSpace */
/* ------------------------------------------------- */
static inline void setLimit(GC_state s) {
s->limit = s->base + s->fromSize;
}
static void fromSpace(GC_state s) {
s->base = smmap(s->fromSize);
if (s->fromSize > s->maxHeapSizeSeen)
s->maxHeapSizeSeen = s->fromSize;
setLimit(s);
}
static void toSpace(GC_state s) {
s->toBase = smmap(s->toSize);
if (s->toSize > s->maxHeapSizeSeen)
s->maxHeapSizeSeen = s->toSize;
}
/* ------------------------------------------------- */
/* currentTime */
/* ------------------------------------------------- */
/* return time as number of milliseconds */
static uint currentTime() {
uint result;
struct rusage ru;
getrusage(RUSAGE_SELF, &ru);
result = 0;
result += 1000 * ru.ru_utime.tv_sec;
result += 1000 * ru.ru_stime.tv_sec;
result += ru.ru_utime.tv_usec / 1000;
result += ru.ru_stime.tv_usec / 1000;
return result;
}
/* ------------------------------------------------- */
/* display */
/* ------------------------------------------------- */
/* static void display(GC_state s, FILE *stream) { */
/* fprintf(stream, "frontier - base = %d limit - base = %d\n", */
/* (int)(s->frontier - s->base), */
/* (int)(s->limit - s->base)); */
/* } */
/* ------------------------------------------------- */
/* computeHeapSize */
/* ------------------------------------------------- */
/* returns min(s->maxHeapSize, live * ratio).
* It is careful not to overflow when doing the multiply.
* It should only be called when not s->useFixedHeap, since s->maxHeapSize is
* only set in that case.
*/
static uint computeHeapSize(GC_state s, uint live, uint ratio) {
ullong needed;
assert(not s->useFixedHeap);
needed = ((ullong)live) * ratio;
return ((needed > s->maxHeapSize)
? s->maxHeapSize
: roundPage(needed));
}
/* ------------------------------------------------- */
/* extractArrayNumBytes */
/* ------------------------------------------------- */
/* The number of bytes in an array, not including the header. */
static inline uint extractArrayNumBytes(pointer p,
uint numPointers,
uint numNonPointers) {
uint numElements, bytesPerElement, result;
numElements = GC_arrayNumElements(p);
bytesPerElement = numNonPointers + toBytes(numPointers);
result = wordAlign(numElements * bytesPerElement);
return result;
}
static inline void maybeCall(pointerFun f, GC_state s, pointer *pp) {
if (GC_isPointer(*pp))
f(s, pp);
}
/* ------------------------------------------------- */
/* foreachGlobal */
/* ------------------------------------------------- */
/* Apply f to each global pointer into the heap. */
static void foreachGlobal(GC_state s, pointerFun f) {
int i;
for (i = 0; i < s->numGlobals; ++i)
maybeCall(f, s, &s->globals[i]);
maybeCall(f, s, (pointer*)&s->currentThread);
maybeCall(f, s, (pointer*)&s->savedThread);
maybeCall(f, s, (pointer*)&s->signalHandler);
}
/* ------------------------------------------------- */
/* foreachPointerInObject */
/* ------------------------------------------------- */
/*
* Apply f to each pointer in the object p, where p points at the first
* data word in the object.
* Returns pointer to the end of object, i.e. just past object.
*/
static pointer foreachPointerInObject(GC_state s, pointerFun f, pointer p) {
word header;
uint numPointers;
uint numNonPointers;
header = getHeader(p);
if (isNormal(header)) { /* It's a normal object. */
pointer max;
splitHeader(header, &numPointers, &numNonPointers);
p += toBytes(numNonPointers);
max = p + toBytes(numPointers);
/* Apply f to all internal pointers. */
for ( ; p < max; p += POINTER_SIZE)
maybeCall(f, s, (pointer*)p);
} else if (STACK_HEADER == header) {
GC_stack stack;
pointer top, bottom;
int i;
uint frameIndex;
GC_frameLayout *layout;
GC_offsets frameOffsets;
stack = (GC_stack)p;
bottom = stackBottom(stack);
top = stackTop(stack);
assert(stack->used <= stack->reserved);
while (top >= bottom) {
/* Invariant: top points at a frame index. */
frameIndex = *(uint*) top;
#if DEBUG
fprintf(stderr, " frame index %d.\n", frameIndex);
#endif
assert(frameIndex < s->maxFrameIndex);
layout = &(s->frameLayouts[frameIndex]);
frameOffsets = layout->offsets;
top -= layout->numBytes;
for (i = 0 ; i < frameOffsets[0] ; ++i) {
#if DEBUG
fprintf(stderr, " offset %d address %x\n",
frameOffsets[i + 1],
*(pointer*)(top + frameOffsets[i + 1]));
#endif
maybeCall(f, s, (pointer*)(top + frameOffsets[i + 1]));
}
}
assert(top == bottom - WORD_SIZE);
p += sizeof(struct GC_stack) + stack->reserved;
} else { /* It's an array. */
uint numBytes;
splitHeader(header, &numPointers, &numNonPointers);
numBytes = extractArrayNumBytes(p, numPointers, numNonPointers);
if (numBytes == 0)
/* An empty array -- skip the POINTER_SIZE bytes
* for the forwarding pointer.
*/
p += POINTER_SIZE;
else {
pointer max;
max = p + numBytes;
if (numPointers == 0) {
/* There are no pointers, just update p. */
p = max;
} else if (numNonPointers == 0) {
/* It's an array with only pointers. */
for (; p < max; p += POINTER_SIZE)
maybeCall(f, s, (pointer*)p);
} else {
uint numBytesPointers;
numBytesPointers = toBytes(numPointers);
/* For each array element. */
while (p < max) {
pointer max2;
p += numNonPointers;
max2 = p + numBytesPointers;
/* For each internal pointer. */
for ( ; p < max2; p += POINTER_SIZE)
maybeCall(f, s, (pointer*)p);
}
}
assert(p == max);
}
}
return p;
}
/* ------------------------------------------------- */
/* toData */
/* ------------------------------------------------- */
/* p should point at the beginning of an object (i.e. the header).
* Returns a pointer to the start of the object data.
*/
static inline pointer toData(pointer p) {
word header;
header = *(word*)p;
return ((isNormal(header) or (STACK_HEADER == header))
? p + WORD_SIZE
: p + 2 * WORD_SIZE);
}
/* ------------------------------------------------- */
/* foreachPointerInRange */
/* ------------------------------------------------- */
/* Apply f to each pointer between front and *back, which should be a
* contiguous sequence of objects, where front points at the beginning of
* the first object and *back points just past the end of the last object.
* f may increase *back (for example, this is done by forward).
*/
static void foreachPointerInRange(GC_state s, pointer front, pointer *back,
pointerFun f) {
assert(front <= *back);
while (front < *back) {
assert(isWordAligned((uint)front));
front = foreachPointerInObject(s, f, toData(front));
}
assert(front == *back);
}
/* ------------------------------------------------- */
/* invariant */
/* ------------------------------------------------- */
#ifndef NODEBUG
static bool isInFromSpace(GC_state s, pointer p) {
return (s->base <= p and p < s->frontier);
}
static void assertIsInFromSpace(GC_state s, pointer *p) {
assert(isInFromSpace(s, *p));
}
static bool isInToSpace(GC_state s, pointer p) {
return (not(GC_isPointer(p))
or (s->toBase <= p and p < s->toBase + s->toSize));
}
static bool invariant(GC_state s) {
/* would be nice to add divisiblity by pagesize of various things */
/* Frame layouts */
{
int i;
for (i = 0; i < s->maxFrameIndex; ++i) {
GC_frameLayout *layout;
layout = &(s->frameLayouts[i]);
if (layout->numBytes > 0) {
GC_offsets offsets;
int j;
assert(layout->numBytes <= s->maxFrameSize);
offsets = layout->offsets;
for (j = 0; j < offsets[0]; ++j)
assert(offsets[j + 1] < layout->numBytes);
}
}
}
/* Heap */
assert(isWordAligned((uint)s->frontier));
assert(s->base <= s->frontier);
assert(0 == s->fromSize
or (s->frontier <= s->limit
and s->limit == s->base + s->fromSize));
assert(s->useFixedHeap or (s->fromSize <= s->maxHeapSize
and s->toSize <= s->maxHeapSize));
assert(s->toBase == NULL or s->toSize == s->fromSize);
/* Check that all pointers are into from space. */
foreachGlobal(s, assertIsInFromSpace);
foreachPointerInRange(s, s->base, &s->frontier, assertIsInFromSpace);
/* Current thread. */
{
uint offset;
GC_stack stack;
stack = s->currentThread->stack;
assert(isWordAligned(stack->reserved));
assert(s->stackBottom == stackBottom(stack));
assert(s->stackTop == stackTop(stack));
assert(s->stackLimit == stackLimit(s, stack));
assert(stack->used == currentStackUsed(s));
assert(s->stackBottom <= s->stackTop + WORD_SIZE);
for (offset = s->currentThread->exnStack;
offset != BOGUS_EXN_STACK; ) {
assert(s->stackBottom + offset
<= s->stackTop + WORD_SIZE);
offset = *(uint*)(s->stackBottom + offset + WORD_SIZE);
}
}
return TRUE;
}
#endif /* #ifndef NODEBUG */
/* ------------------------------------------------- */
/* initCounters */
/* ------------------------------------------------- */
static void initCounters(GC_state s) {
s->bytesAllocated = 0;
s->bytesCopied = 0;
s->canHandle = TRUE;
s->currentThread = BOGUS_THREAD;
s->gcTime = 0;
s->inSignalHandler = FALSE;
s->maxPause = 0;
s->maxHeapSizeSeen = 0;
s->maxBytesLive = 0;
s->numGCs = 0;
s->savedThread = BOGUS_THREAD;
s->signalHandler = BOGUS_THREAD;
sigemptyset(&s->signalsHandled);
s->signalIsPending = FALSE;
sigemptyset(&s->signalsPending);
s->startTime = currentTime();
/* The next 3 are for heap resizing */
s->minLive = 20;
s->maxLive = 3;
/* set liveRatio (close) to the geometric mean of minLive and maxLive */
{
uint i;
for (i = s->maxLive; i * i <= s->minLive * s->maxLive; ++i);
s->liveRatio = i;
}
}
/* ------------------------------------------------- */
/* getRAMsize */
/* ------------------------------------------------- */
/* RAM size is multiplied by this so that we don't use up all the memory */
static const double RAMslop = 0.95;
/* Get RAM size from /proc/meminfo. Very Linux specific.
*
* /proc/meminfo looks like the following.
*
* total: used: free: shared: buffers: cached:
* Mem: 263462912 251154432 12308480 19861504 52588544 122769408
* Swap: 131567616 53248 131514368
* MemTotal: 257288 kB
*/
static uint getRAMsize() {
FILE *file;
char c;
char buf[80];
uint n;
file = sopen("/proc/meminfo", "r");
while ((c = fgetc(file)) != '\n');
fgets(buf, sizeof("Mem:"), file);
while ((c = fgetc(file)) == ' ') ;
n = 0;
do
n = n * 10 + (int)(c - '0');
while ((c = fgetc(file)) != ' ');
fclose(file);
return roundPage((uint)((double)n * RAMslop));
}
/* ------------------------------------------------- */
/* setHeapParams */
/* ------------------------------------------------- */
/* set fromSize and maybe maxHeapSize, depending on whether useFixedHeap.
* size must not be an approximation, because setHeapParams will die if it
* can't set fromSize big enough.
*/
static void setHeapParams(GC_state s, uint size) {
if (s->useFixedHeap) {
if (0 == s->fromSize)
s->fromSize = getRAMsize();
s->fromSize = roundPage(s->fromSize / 2);
} else {
if (0 == s->maxHeapSize)
s->maxHeapSize = getRAMsize();
s->maxHeapSize = roundPage(s->maxHeapSize / 2);
s->fromSize = computeHeapSize(s, size, s->liveRatio);
}
if (size > s->fromSize)
die("Out of memory.");
}
/* ------------------------------------------------- */
/* GC_init */
/* ------------------------------------------------- */
void GC_init(GC_state s) {
int i;
assert(isWordAligned(sizeof(struct GC_thread)));
initCounters(s);
setHeapParams(s, s->bytesLive);
for (i = 0; i < s->numGlobals; ++i)
s->globals[i] = (pointer)BOGUS_POINTER;
/* This sets s->fromSize so that there is enough space for the
* initial thread.
*/
s->fromSize = roundPage(s->fromSize + initialThreadBytes(s));
fromSpace(s);
s->frontier = s->base;
s->toSize = s->fromSize;
toSpace(s); /* FIXME: Why does toSpace need to be allocated? */
switchToThread(s, newThreadOfSize(s, initialStackBytes(s)));
assert(invariant(s));
}
/* ------------------------------------------------- */
/* forward */
/* ------------------------------------------------- */
/*
* Forward the object pointed to by *pp.
* Update *pp to point to the new object.
*/
static void forward(GC_state s, pointer *pp) {
pointer p;
word header;
assert(isInFromSpace(s, *pp));
p = *pp;
header = getHeader(p);
if (header != FORWARDED) { /* forward the object */
uint headerBytes, objectBytes, size, skip;
uint numPointers, numNonPointers;
/* Compute the space taken by the header and object body. */
header = getHeader(p);
splitHeader(header, &numPointers, &numNonPointers);
if (isNormal(header)) { /* Fixed size object. */
headerBytes = GC_OBJECT_HEADER_SIZE;
objectBytes = toBytes(numPointers + numNonPointers);
skip = 0;
} else if (STACK_HEADER == header) { /* Stack. */
GC_stack stack;
headerBytes = STACK_HEADER_SIZE;
/* Resize stacks not being used as continuations. */
stack = (GC_stack)p;
if (stack->reserved != stack->used) {
if (4 * stack->used <= stack->reserved)
stack->reserved = stack->reserved / 2;
else if (4 * stack->used > 3 * stack->reserved)
stack->reserved = stack->reserved * 2;
stack->reserved =
wordAlign(max(stack->reserved,
stackNeedsReserved(s, stack)));
assert(stackTopIsOk(s, stack));
}
objectBytes = sizeof(struct GC_stack) + stack->used;
skip = stack->reserved - stack->used;
} else { /* Array. */
headerBytes = GC_ARRAY_HEADER_SIZE;
objectBytes = extractArrayNumBytes(p, numPointers,
numNonPointers);
skip = 0;
/* Empty arrays have POINTER_SIZE bytes for the
* forwarding pointer.
*/
if (0 == objectBytes) objectBytes = POINTER_SIZE;
}
size = headerBytes + objectBytes;
if (s->back + size + skip > s->toLimit)
die("Out of memory.");
/* Copy the object. */
memmove(s->back, p - headerBytes, size);
/* Store the forwarding pointer in the old object. */
*(word*)(p - WORD_SIZE) = FORWARDED;
*(pointer*)p = s->back + headerBytes;
/* Update the back of the queue. */
s->back += size + skip;
assert(isWordAligned((uint)s->back));
}
*pp = *(pointer*)p;
assert(isInToSpace(s, *pp));
}
/* ------------------------------------------------- */
/* doGC */
/* ------------------------------------------------- */
static void doGC(GC_state s, uint bytesRequested, uint stackBytesRequested) {
uint gcTime;
uint size;
pointer front;
assert(invariant(s));
if (DEBUG or s->messages)
fprintf(stderr, "Starting gc.\n");
s->recentStart = currentTime();
unless (s->useFixedHeap) { /* Get toSpace ready. */
uint needed;
needed = computeHeapSize
(s, s->bytesLive + bytesRequested + stackBytesRequested,
s->liveRatio);
/* toSpace must be at least as big as fromSpace */
if (needed < s->fromSize)
needed = s->fromSize;
/* Massage toSpace so that it is of needed size. */
if (s->toBase != NULL) {
if (s->toSize < needed) {
if (DEBUG or s->messages)
fprintf(stderr, "Unmapping toSpace\n");
smunmap(s->toBase, s->toSize);
s->toBase = NULL;
} else if (s->toSize > needed) {
uint delete;
delete = s->toSize - needed;
if (DEBUG or s->messages)
fprintf(stderr, "Shrinking toSpace by %u\n", delete);
smunmap(s->toBase + needed, delete);
}
}
s->toSize = needed;
if (NULL == s->toBase)
toSpace(s);
}
s->numGCs++;
s->bytesAllocated += s->frontier - s->base - s->bytesLive;
s->back = s->toBase;
if (DEBUG or s->messages)
fprintf(stderr,
"toSpace is %s bytes.\n",
uintToCommaString(s->toSize));
s->toLimit = s->toBase + s->toSize;
/* The actual GC. */
front = s->back;
foreachGlobal(s, forward);
foreachPointerInRange(s, front, &s->back, forward);
size = s->fromSize;
/* Swap fromSpace and toSpace. */
{
pointer tmp;
tmp = s->base;
s->base = s->toBase;
s->toBase = tmp;
}
{
uint tmp;
tmp = s->fromSize;
s->fromSize = s->toSize;
s->toSize = tmp;
}
setStack(s);
s->frontier = s->back;
s->bytesLive = s->frontier - s->base;
if (s->bytesLive > s->maxBytesLive)
s->maxBytesLive = s->bytesLive;
/* Resize heap, if necessary. */
unless (s->useFixedHeap) {
uint needed;
needed = s->bytesLive + bytesRequested;
if (computeHeapSize(s, needed, s->minLive) < s->fromSize) {
/* shrink heap */
uint keep;
keep = computeHeapSize(s, needed, s->liveRatio);
if (DEBUG or s->messages)
fprintf(stderr, "Shrinking heap to %u bytes.\n", keep);
assert(keep <= s->fromSize);
smunmap(s->base + keep, s->fromSize - keep);
s->fromSize = keep;
}
if ((s->toSize < s->fromSize)
or (computeHeapSize(s, needed, s->maxLive) > s->fromSize)) {
/* prepare to allocate new toSpace at next GC */
smunmap(s->toBase, s->toSize);
s->toBase = NULL;
} else {
/* shrink toSpace so that s->toSize == s->fromSize */
smunmap(s->toBase + s->fromSize, s->toSize - s->fromSize);
s->toSize = s->fromSize;
}
}
setLimit(s);
s->bytesCopied += s->bytesLive;
gcTime = currentTime() - s->recentStart;
s->gcTime += gcTime;
s->maxPause = max(s->maxPause, gcTime);
if (DEBUG or s->messages) {
fprintf(stderr, "Finished gc.\n");
fprintf(stderr, "time(ms): %s\n", intToCommaString(gcTime));
fprintf(stderr, "live(bytes): %s (%.1f%%)\n",
intToCommaString(s->bytesLive),
100.0 * ((double) s->bytesLive) / size);
}
if (bytesRequested > s->limit - s->frontier) {
if (s->useFixedHeap or s->fromSize == s->maxHeapSize) {
die("Out of memory.");
} else doGC(s, bytesRequested, 0);
}
assert(bytesRequested <= s->limit - s->frontier);
assert(invariant(s));
}
/* ------------------------------------------------- */
/* GC_gc */
/* ------------------------------------------------- */
void GC_gc(GC_state s, uint bytesRequested, bool force) {
uint stackBytesRequested;
enter(s);
stackBytesRequested =
(stackTopIsOk(s, s->currentThread->stack))
? 0
: (HEADER_SIZE
+ sizeof(struct GC_stack)
+ 2 * s->currentThread->stack->reserved);
if (force or (s->frontier + bytesRequested + stackBytesRequested
> s->limit)) {
/* This GC will grow the stack, if necessary. */
doGC(s, bytesRequested, s->currentThread->stack->reserved);
assert(bytesRequested <= s->limit - s->frontier);
} else if (not(stackTopIsOk(s, s->currentThread->stack))) {
uint size;
GC_stack stack;
size = 2 * s->currentThread->stack->reserved;
if (DEBUG or s->messages)
fprintf(stderr, "Growing stack to size %u.\n", size);
/* The newStack can't cause a GC, because we checked above to
* make sure there was enough space.
*/
stack = newStack(s, size);
stackCopy(s->currentThread->stack, stack);
s->currentThread->stack = stack;
setStack(s);
assert(bytesRequested <= s->limit - s->frontier);
} else if (s->signalIsPending and s->canHandle) {
/* Switch to the signal handler thread. */
s->signalIsPending = FALSE;
s->inSignalHandler = TRUE;
s->savedThread = s->currentThread;
switchToThread(s, s->signalHandler);
}
assert(stackTopIsOk(s, s->currentThread->stack));
leave(s);
}
/* ------------------------------------------------- */
/* GC_createStrings */
/* ------------------------------------------------- */
void GC_createStrings(GC_state s, struct GC_stringInit inits[]) {
pointer frontier;
int i;
assert(invariant(s));
frontier = s->frontier;
for(i = 0; inits[i].str != NULL; ++i) {
uint numElements, numBytes;
numElements = inits[i].size;
numBytes = GC_ARRAY_HEADER_SIZE
+ ((0 == numElements)
? POINTER_SIZE
: wordAlign(numElements));
if (frontier + numBytes > s->limit)
die("Unable to allocate string constant \"%s\".",
inits[i].str);
*(word*)frontier = numElements;
*(word*)(frontier + WORD_SIZE) = STRING_HEADER;
s->globals[inits[i].globalIndex] =
frontier + GC_ARRAY_HEADER_SIZE;
{
int j;
for (j = 0; j < numElements; ++j)
*(frontier + GC_ARRAY_HEADER_SIZE + j)
= inits[i].str[j];
}
frontier += numBytes;
}
s->frontier = frontier;
assert(invariant(s));
}
/* ------------------------------------------------- */
/* GC_done */
/* ------------------------------------------------- */
static void displayUint(string name, uint n) {
fprintf(stderr, "%s: %s\n", name, uintToCommaString(n));
}
static void displayUllong(string name, ullong n) {
fprintf(stderr, "%s: %s\n", name, ullongToCommaString(n));
}
void GC_done(GC_state s) {
enter(s);
smunmap(s->base, s->fromSize);
if (s->toBase != NULL) smunmap(s->toBase, s->toSize);
if (s->summary) {
double time;
displayUint("max semispace size(bytes)", s->maxHeapSizeSeen);
time = (double)(currentTime() - s->startTime);
fprintf(stderr, "GC time(ms): %s (%.1f%%)\n",
intToCommaString(s->gcTime),
(0.0 == time) ? 0.0
: 100.0 * ((double) s->gcTime) / time);
displayUint("maxPause(ms)", s->maxPause);
displayUint("number of GCs", s->numGCs);
displayUllong("bytes allocated",
s->bytesAllocated
+ (s->frontier - s->base - s->bytesLive));
displayUllong("bytes copied", s->bytesCopied);
displayUint("max bytes live", s->maxBytesLive);
}
}
/* ------------------------------------------------- */
/* GC_saveWorld */
/* ------------------------------------------------- */
/* TERMINATOR is used to separate the human readable messages at the beginning
* of the world file from the machine readable data.
*/
static const char TERMINATOR = '\000';
void GC_saveWorld(GC_state s,
pointer fileName,
void (*saveGlobals)(FILE *file)) {
FILE *file;
enter(s);
/* The sopen must happen before the GC, because the GC will invalidate
* the fileName pointer.
*/
file = sopen((char*)fileName, "w");
/* Compact the heap into fromSpace */
doGC(s, 0, 0);
fprintf(file, "Heap file created by MLton.\nbase = %x\nfrontier = %x\nmaxHeapSize = %u\n",
(uint)s->base,
(uint)s->frontier,
s->maxHeapSize);
fputc(TERMINATOR, file);
swriteUint(s->magic, file);
swriteUint((uint)s->base, file);
swriteUint((uint)s->frontier, file);
swriteUint((uint)s->currentThread, file);
swriteUint((uint)s->signalHandler, file);
swriteUint((uint)s->useFixedHeap, file);
swriteUint(s->fromSize, file);
swriteUint(s->maxHeapSize, file);
swrite(s->base, 1, s->frontier - s->base, file);
(*saveGlobals)(file);
fclose(file);
leave(s);
}
/* ------------------------------------------------- */
/* translateHeap */
/* ------------------------------------------------- */
static void translatePointer(GC_state s, pointer *p) {
if (1 == s->translateDirection)
*p += s->translateDiff;
else
*p -= s->translateDiff;
}
/* Translate all pointers to the heap from within the stack and the heap for
* a heap that has moved from s->base == old to s->base.
*/
static void translateHeap(GC_state s, pointer old) {
if (s->base == old)
return;
else if (s->base > old) {
s->translateDiff = s->base - old;
s->translateDirection = 1;
} else {
s->translateDiff = old - s->base;
s->translateDirection = -1;
}
/* Translate globals and heap. */
foreachGlobal(s, translatePointer);
foreachPointerInRange(s, s->base, &s->frontier, translatePointer);
}
/* ------------------------------------------------- */
/* GC_loadWorld */
/* ------------------------------------------------- */
void GC_loadWorld(GC_state s,
char *fileName,
bool heapSizeCommandLine,
void (*loadGlobals)(FILE *file)) {
FILE *file;
uint heapSize, fromSize, maxHeapSize, magic;
pointer base, frontier;
bool useFixedHeap;
char c;
initCounters(s);
file = sopen((char*)fileName, "r");
until ((c = fgetc(file)) == TERMINATOR or EOF == c);
if (EOF == c) die("Invalid world.");
magic = sreadUint(file);
unless (s->magic == magic)
die("Invalid world: wrong magic number.");
base = (pointer)sreadUint(file);
frontier = (pointer)sreadUint(file);
heapSize = frontier - base;
s->bytesLive = heapSize;
s->currentThread = (GC_thread)sreadUint(file);
s->signalHandler = (GC_thread)sreadUint(file);
useFixedHeap = (bool)sreadUint(file);
fromSize = sreadUint(file);
maxHeapSize = sreadUint(file);
/* set s->useFixedHeap, s->maxHeapSize, s->fromSize */
if (heapSizeCommandLine)
setHeapParams(s, heapSize);
else {
s->useFixedHeap = useFixedHeap;
if (useFixedHeap)
s->fromSize = fromSize;
else {
s->maxHeapSize = maxHeapSize;
s->fromSize = computeHeapSize(s, heapSize, s->liveRatio);
}
}
/* Allocate fromSpace. */
unless (heapSize <= s->fromSize)
die("Not enough space to load world.");
fromSpace(s);
sread(s->base, 1, heapSize, file);
s->frontier = s->base + heapSize;
(*loadGlobals)(file);
unless (EOF == fgetc(file))
die("Invalid world: junk at end of file.");
fclose(file);
/* This must occur after loading the heap and globals, since it
* changes pointers in all of them.
*/
translateHeap(s, base);
setStack(s);
/* Allocate toSpace. We at least must do this if s->useFixedHeap. */
s->toSize = s->fromSize;
toSpace(s);
assert(invariant(s));
}
/* ------------------------------------------------- */
/* Signals */
/* ------------------------------------------------- */
static void blockSignals(GC_state s) {
sigprocmask(SIG_BLOCK, &s->signalsHandled, NULL);
}
static void unblockSignals(GC_state s) {
sigprocmask(SIG_UNBLOCK, &s->signalsHandled, NULL);
}
/* enter and leave should be called at the start and end of every GC function
* that is exported to the outside world. They make sure that signals are
* blocked for the duration of the function and check the GC invariant
* They are a bit tricky because of the case when the runtime system is invoked
* from within an ML signal handler.
*/
static void enter(GC_state s) {
/* used needs to be set because the mutator has changed s->stackTop. */
s->currentThread->stack->used = currentStackUsed(s);
unless (s->inSignalHandler) {
blockSignals(s);
if (s->limit == s->base)
setLimit(s);
}
assert(invariant(s));
}
static void leave(GC_state s) {
assert(invariant(s));
if (s->signalIsPending)
s->limit = s->base;
unless (s->inSignalHandler)
unblockSignals(s);
}
/* GC_handler sets s->limit = s->base so that the next limit check will fail.
* Signals need to be blocked during the handler (i.e. it should run atomically)
* because sigaddset does both a read and a write of s->signalsPending.
* The signals are blocked by MLTON_Signal_handle (see mlton-lib.c).
*/
void GC_handler(GC_state s, int signum) {
s->limit = s->base;
sigaddset(&s->signalsPending, signum);
s->signalIsPending = TRUE;
}
void GC_finishHandler(GC_state s, GC_thread t) {
enter(s);
assert(t != BOGUS_THREAD);
s->inSignalHandler = FALSE;
sigemptyset(&s->signalsPending);
switchToThread(s, t);
leave(s);
}