/*
* Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
* Copyright (c) 1991,1992 by Xerox Corporation. All rights reserved.
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
*
* Permission is hereby granted to copy this garbage collector for any purpose,
* provided the above notices are retained on all copies.
*
* This file contains the functions:
* GC←mark() - Mark from the mark stack
* GC←mark←reliable() - as above, but fix things up after
* a mark stack overflow.
* GC←mark←all(b,t) - Mark from everything in a range
* GC←mark←all←stack(b,t) - Mark from everything in a range,
* consider interior pointers as valid
* GC←remark() - Mark from all marked objects. Used
* only if we had to drop something.
*/
# include <stdio.h>
# include "gc←private.h"
# define INITIAL←MARK←STACK←SIZE (1*HBLKSIZE)
/* INITIAL←MARK←STACK←SIZE * sizeof(mse) should be a */
/* multiple of HBLKSIZE. */
/*
* Limits of stack for GC←mark routine. Set by caller to GC←mark.
* All items between GC←mark←stack←top and GC←mark←stack←bottom-1 still need
* to be marked.
*/
mse * GC←mark←stack;
word GC←mark←stack←size = 0;
mse * GC←mark←stack←top;
static bool dropped←some = FALSE;
/* We ran out of space and were forced */
/* to drop some pointers during marking */
/* Mark procedure for objects that may contain arbitrary pointers. */
/* Msp is the current mark stack pointer. Msl limits the stack. */
/* We return the new stack pointer value. */
/* The object at addr has already been marked. Our job is to make */
/* sure that its descendents are marked. */
mse * GC←normal←mark←proc(addr, hhdr, msp, msl)
register word * addr;
register hdr * hhdr;
register mse * msp, * msl;
{
register word sz = hhdr -> hb←sz;
msp++;
/* Push the contents of the object on the mark stack. */
if (msp >= msl) {
dropped←some = TRUE;
return(msp-1);
}
msp -> mse←start = addr;
msp -> mse←end = addr + sz;
# ifdef GATHERSTATS
GC←composite←in←use += sz;
# endif
return(msp);
}
/* Mark procedure for objects that are known to contain no pointers. */
/*ARGSUSED*/
mse * GC←no←mark←proc(addr, hhdr, msp, msl)
register word * addr;
register hdr * hhdr;
register mse * msp, * msl;
{
# ifdef GATHERSTATS
GC←atomic←in←use += hhdr -> hb←sz;
# endif
return(msp);
}
/*
* Mark all objects pointed to by the regions described by
* mark stack entries between GC←mark←stack and GC←mark←stack←top,
* inclusive. Assumes the upper limit of a mark stack entry
* is never 0.
*/
void GC←mark()
{
mse * GC←mark←stack←reg = GC←mark←stack;
mse * GC←mark←stack←top←reg = GC←mark←stack←top;
mse * mark←stack←limit = &(GC←mark←stack[GC←mark←stack←size]);
register word * current←p; /* Pointer to current candidate ptr. */
register word current; /* Candidate pointer. */
register word * limit; /* (Incl) limit of current candidate */
/* range */
register ptr←t greatest←ha = GC←greatest←plausible←heap←addr;
register ptr←t least←ha = GC←least←plausible←heap←addr;
# define SPLIT←RANGE←WORDS 128
while (GC←mark←stack←top←reg >= GC←mark←stack←reg) {
register int displ; /* Displacement in block; first bytes, then words */
register hdr * hhdr;
register map←entry←type map←entry;
current←p = GC←mark←stack←top←reg -> mse←start;
limit = GC←mark←stack←top←reg -> mse←end;
if (limit - current←p > SPLIT←RANGE←WORDS) {
/* Process part of the range to avoid pushing too much on the */
/* stack. */
GC←mark←stack←top←reg -> mse←start =
limit = current←p + SPLIT←RANGE←WORDS;
/* Make sure that pointers overlapping the two ranges are */
/* considered. */
limit += sizeof(word) - ALIGNMENT;
} else {
GC←mark←stack←top←reg--;
}
limit -= 1;
while (current←p <= limit) {
current = *current←p;
current←p = (word *)((char *)current←p + ALIGNMENT);
if ((ptr←t)current < least←ha) continue;
if ((ptr←t)current >= greatest←ha) continue;
hhdr = HDR(current);
if (IS←FORWARDING←ADDR←OR←NIL(hhdr)) {
# ifdef ALL←INTERIOR←POINTERS
if (hhdr != 0) {
register word orig = current;
current = (word)HBLKPTR(current) + HDR←BYTES;
do {
current = current - HBLKSIZE*(int)hhdr;
hhdr = HDR(current);
} while(IS←FORWARDING←ADDR←OR←NIL(hhdr));
/* current points to the start of the large object */
if ((word *)orig - (word *)current
>= hhdr->hb←sz) {
/* Pointer past the end of the block */
GC←ADD←TO←BLACK←LIST←NORMAL(current);
continue;
}
} else {
GC←ADD←TO←BLACK←LIST←NORMAL(current);
continue;
}
# else
GC←ADD←TO←BLACK←LIST←NORMAL(current);
continue;
# endif
}
displ = HBLKDISPL(current);
map←entry = MAP←ENTRY((hhdr -> hb←map), displ);
if (map←entry == OBJ←INVALID) {
GC←ADD←TO←BLACK←LIST←NORMAL(current);
continue;
}
displ = BYTES←TO←WORDS(displ);
displ -= map←entry;
{
register word * mark←word←addr = hhdr -> hb←marks + divWORDSZ(displ);
register word mark←word = *mark←word←addr;
register word mark←bit = 1 << modWORDSZ(displ);
if (mark←word & mark←bit) {
/* Mark bit is already set */
continue;
}
*mark←word←addr = mark←word | mark←bit;
}
GC←mark←stack←top←reg =
(* (hhdr -> hb←mark←proc))((word *)(HBLKPTR(current)) + displ, hhdr,
GC←mark←stack←top←reg, mark←stack←limit);
}
}
GC←mark←stack←top = GC←mark←stack←top←reg;
}
/* Allocate or reallocate space for mark stack of size s words */
/* May silently fail. */
static void alloc←mark←stack(n)
word n;
{
mse * new←stack = (mse *)GET←MEM(n * sizeof(struct ms←entry));
if (GC←mark←stack←size != 0) {
if (new←stack != 0) {
/* Recycle old space */
GC←add←to←heap((struct hblk *)GC←mark←stack,
GC←mark←stack←size * sizeof(struct ms←entry));
GC←mark←stack = new←stack;
GC←mark←stack←size = n;
}
} else {
if (new←stack == 0) {
GC←err←printf0("No space for mark stack\n");
EXIT();
}
GC←mark←stack = new←stack;
GC←mark←stack←size = n;
}
GC←mark←stack←top = GC←mark←stack-1;
}
void GC←mark←init()
{
alloc←mark←stack(INITIAL←MARK←STACK←SIZE);
}
/* Identical to GC←mark, but guarantee that dropped←some is false */
/* when we finish. */
void GC←mark←reliable()
{
dropped←some = FALSE;
GC←mark();
while (dropped←some) {
dropped←some = FALSE;
# ifdef PRINTSTATS
GC←printf1("Mark stack overflow; current size = %lu entries\n",
GC←mark←stack←size);
# endif
alloc←mark←stack(2*GC←mark←stack←size);
GC←remark();
}
}
/*********************************************************************/
/* Mark all locations reachable via pointers located between b and t */
/* b is the first location to be checked. t is one past the last */
/* location to be checked. */
/*********************************************************************/
void GC←mark←all(bottom, top)
ptr←t bottom;
ptr←t top;
{
word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
if (GC←mark←stack←top != GC←mark←stack-1) {
ABORT("GC←mark←all: bad mark stack\n");
}
if (top == 0) return;
GC←mark←stack←top++;
GC←mark←stack←top -> mse←start = b;
GC←mark←stack←top -> mse←end = t;
GC←mark←reliable();
}
word * GC←buffer; /* Buffer for stack marking */
# define BUFSIZE 1024
/*
* A version of GC←mark←all that treats all interior pointers as valid
*/
void GC←mark←all←stack(bottom, top)
ptr←t bottom;
ptr←t top;
{
# ifdef ALL←INTERIOR←POINTERS
GC←mark←all(bottom, top);
# else
word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
register word *p;
register word q;
register word r;
register word *lim;
word * bufptr;
word * limit;
register ptr←t greatest←ha = GC←greatest←plausible←heap←addr;
register ptr←t least←ha = GC←least←plausible←heap←addr;
if (top == 0) return;
/* Allocate GC←buffer someplace where collector won't accidentally */
/* see old sections. */
if (GC←buffer == 0) {
GC←buffer = (word *)GC←scratch←alloc((word)(BUFSIZE * sizeof(word)));
}
bufptr = GC←buffer;
limit = GC←buffer+BUFSIZE;
/* check all pointers in range and put in buffer if they appear */
/* to be valid. */
lim = t - 1 /* longword */;
for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
q = *p;
if ((ptr←t)q < least←ha
|| (ptr←t)q >= greatest←ha) {
continue;
}
# ifdef ←←STDC←←
r = (word)GC←base((void *)q);
# else
r = (word)GC←base((char *)q);
# endif
if (r == 0) {
GC←add←to←black←list←stack(*p);
} else {
*(bufptr++) = r;
if (bufptr == limit) {
GC←mark←all((ptr←t)GC←buffer, (ptr←t)limit);
bufptr = GC←buffer;
}
}
}
if (bufptr != GC←buffer) GC←mark←all((ptr←t)GC←buffer, (ptr←t)bufptr);
# endif
}
/* Mark all objects reachable from marked objects in the given block */
/*ARGSUSED*/
static void remark←block(h, dummy)
struct hblk *h;
word dummy;
{
register hdr * hhdr = HDR(h);
register int sz = hhdr -> hb←sz;
register word * p;
register int word←no;
register word * lim;
register mse * GC←mark←stack←top←reg = GC←mark←stack←top;
if (hhdr -> hb←obj←kind == PTRFREE) return;
if (sz > MAXOBJSZ) {
lim = (word *)(h + 1);
} else {
lim = (word *)(h + 1) - sz;
}
for (p = (word *)h + HDR←WORDS, word←no = HDR←WORDS; p <= lim;
p += sz, word←no += sz) {
if (mark←bit←from←hdr(hhdr, word←no)) {
/* Mark from fields inside the object */
GC←mark←stack←top←reg++;
GC←mark←stack←top←reg -> mse←start = p;
GC←mark←stack←top←reg -> mse←end = p + sz;
}
}
GC←mark←stack←top = GC←mark←stack←top←reg;
GC←mark();
}
/*
* Traverse the heap. Mark all objects reachable from marked objects.
*/
void GC←remark()
{
GC←apply←to←all←blocks(remark←block, 0);
}