/*
* Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
* Copyright (c) 1991 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:
* static void clear←marks()
* bool GC←gcollect←inner(force)
* void GC←gcollect()
* bool GC←expand←hp(n)
* ptr←t GC←allocobj(sz, kind)
*/
# include <stdio.h>
# include <signal.h>
# include <sys/types.h>
# include "gc←private.h"
/*
* This is a garbage collecting storage allocator
* that should run on most UNIX systems. The garbage
* collector is overly conservative in that it may fail to GC←reclaim
* inaccessible storage. On the other hand, it does not assume
* any runtime tag information.
* We make the following assumptions:
* 1. We are running under something that looks like Berkeley UNIX,
* on one of the supported architectures.
* 2. For every accessible object, a pointer to it is stored in
* a) the stack segment, or
* b) the data or bss segment, or
* c) the registers, or
* d) an accessible block.
*
*/
/*
* Separate free lists are maintained for different sized objects
* up to MAXOBJSZ.
* The call GC←allocobj(i,k) ensures that the freelist for
* kind k objects of size i points to a non-empty
* free list. It returns a pointer to the first entry on the free list.
* In a single-threaded world, GC←allocobj may be called to allocate
* an object of (small) size i as follows:
*
* opp = &(GC←objfreelist[i]);
* if (*opp == 0) GC←allocobj(i, NORMAL);
* ptr = *opp;
* *opp = ptr->next;
*
* Note that this is very fast if the free list is non-empty; it should
* only involve the execution of 4 or 5 simple instructions.
* All composite objects on freelists are cleared, except for
* their first word.
*/
/*
* The allocator uses GC←allochblk to allocate large chunks of objects.
* These chunks all start on addresses which are multiples of
* HBLKSZ. Each allocated chunk has an associated header,
* which can be located quickly based on the address of the chunk.
* (See headers.c for details.)
* This makes it possible to check quickly whether an
* arbitrary address corresponds to an object administered by the
* allocator.
*/
word GC←non←gc←bytes = 0; /* Number of bytes not intended to be collected */
word GC←gc←no = 0;
char * GC←copyright[] =
{"Copyright 1988,1989 Hans-J. Boehm and 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."};
/* some more variables */
extern signed←word GC←mem←found; /* Number of reclaimed longwords */
/* after garbage collection */
/* clear all mark bits in the header */
void GC←clear←hdr←marks(hhdr)
register hdr * hhdr;
{
bzero((char *)hhdr -> hb←marks, (int)(MARK←BITS←SZ*sizeof(word)));
}
/*
* Clear all mark bits associated with block h.
*/
/*ARGSUSED*/
static void clear←marks←for←block(h, dummy)
struct hblk *h;
word dummy;
{
register hdr * hhdr = HDR(h);
GC←clear←hdr←marks(hhdr);
}
/*
* Clear mark bits in all allocated heap blocks
*/
static void clear←marks()
{
GC←apply←to←all←blocks(clear←marks←for←block, (word)0);
}
bool GC←dont←expand = 0;
word GC←free←space←divisor = 4;
/* Return the minimum number of words that must be allocated between */
/* collections to amortize the collection cost. */
static word min←words←allocd()
{
int dummy;
# ifdef THREADS
/* We punt, for now. */
register signed←word stack←size = 10000;
# else
register signed←word stack←size = (ptr←t)(&dummy) - GC←stackbottom;
# endif
register word total←root←size; /* includes double stack size, */
/* since the stack is expensive */
/* to scan. */
if (stack←size < 0) stack←size = -stack←size;
total←root←size = 2 * stack←size + GC←root←size;
return(BYTES←TO←WORDS(GC←heapsize + total←root←size)/GC←free←space←divisor);
}
/* Return the number of words allocated, adjusted for explicit storage */
/* management. This number can be used in deciding when to trigger */
/* collections. */
word GC←adj←words←allocd()
{
register signed←word result;
register signed←word expl←managed =
BYTES←TO←WORDS((long)GC←non←gc←bytes
- (long)GC←non←gc←bytes←at←gc);
/* Don't count what was explicitly freed, or newly allocated for */
/* explicit management. Note that deallocating an explicitly */
/* managed object should not alter result, assuming the client */
/* is playing by the rules. */
result = (signed←word)GC←words←allocd
- (signed←word)GC←mem←freed - expl←managed;
if (result > (signed←word)GC←words←allocd) result = GC←words←allocd;
/* probably client bug or unfortunate scheduling */
if (result < (signed←word)(GC←words←allocd >> 2)) {
/* Always count at least 1/8 of the allocations. We don't want */
/* to collect too infrequently, since that would inhibit */
/* coalescing of free storage blocks. */
/* This also makes us partially robust against client bugs. */
return(GC←words←allocd >> 3);
} else {
return(result);
}
}
/* Clear up a few frames worth og garbage left at the top of the stack. */
/* This is used to prevent us from accidentally treating garbade left */
/* on the stack by other parts of the collector as roots. This */
/* differs from the code in misc.c, which actually tries to keep the */
/* stack clear of long-lived, client-generated garbage. */
void GC←clear←a←few←frames()
{
# define NWORDS 64
word frames[NWORDS];
register int i;
for (i = 0; i < NWORDS; i++) frames[i] = 0;
}
/*
* Restore inaccessible objects to the free list
* update GC←mem←found (number of reclaimed longwords after
* garbage collection)
* We assume we hold the allocation lock, and are not interruptable by
* signals, if that matters.
* If force is FALSE and we didn't do anything, return FALSE.
* Otherwise return TRUE
*/
bool GC←gcollect←inner(force)
bool force; /* Collect even if only a small amount of allocation */
/* has taken place. Otherwise we refuse, allowing the */
/* heap to grow. */
{
# ifdef PRINTTIMES
CLOCK←TYPE start←time;
CLOCK←TYPE mark←time;
CLOCK←TYPE done←time;
# endif
if (!force && !GC←dont←expand
&& GC←adj←words←allocd() < min←words←allocd()) return(FALSE);
# ifdef PRINTTIMES
GET←TIME(start←time);
# endif
# ifdef PRINTSTATS
GC←printf2("Collection %lu reclaimed %ld bytes\n",
(unsigned long) GC←gc←no,
(long)WORDS←TO←BYTES(GC←mem←found));
# endif
GC←gc←no++;
# ifdef GATHERSTATS
GC←mem←found = 0;
GC←composite←in←use = 0;
GC←atomic←in←use = 0;
# endif
# ifdef PRINTSTATS
GC←printf2("Collection number %lu after %lu allocated bytes ",
(unsigned long) GC←gc←no,
(unsigned long) WORDS←TO←BYTES(GC←words←allocd));
GC←printf1("(heapsize = %lu bytes)\n",
(unsigned long) GC←heapsize);
/* Printf arguments may be pushed in funny places. Clear the */
/* space. */
GC←printf0("");
# endif
clear←marks();
STOP←WORLD();
/* Mark from all roots. */
/* Minimize junk left in my registers and on the stack */
GC←clear←a←few←frames();
GC←noop(0,0,0,0,0,0);
GC←mark←roots();
GC←promote←black←lists();
/* Check all debugged objects for consistency */
if (GC←debugging←started) {
GC←check←heap();
}
START←WORLD();
# ifdef PRINTTIMES
GET←TIME(mark←time);
# endif
# ifdef FIND←LEAK
/* Mark all objects on the free list. All objects should be */
/* marked when we're done. */
{
register word size; /* current object size */
register ptr←t p; /* pointer to current object */
register struct hblk * h; /* pointer to block containing *p */
register hdr * hhdr;
register int word←no; /* "index" of *p in *q */
int kind;
for (kind = 0; kind < GC←n←kinds; kind++) {
for (size = 1; size <= MAXOBJSZ; size++) {
for (p= GC←obj←kinds[kind].ok←freelist[size];
p != 0; p=obj←link(p)){
h = HBLKPTR(p);
hhdr = HDR(h);
word←no = (((word *)p) - ((word *)h));
set←mark←bit←from←hdr(hhdr, word←no);
}
}
}
}
/* Check that everything is marked */
GC←start←reclaim(TRUE);
# else
GC←finalize();
/* Clear free list mark bits, in case they got accidentally marked */
/* Note: HBLKPTR(p) == pointer to head of block containing *p */
/* Also subtract memory remaining from GC←mem←found count. */
/* Note that composite objects on free list are cleared. */
/* Thus accidentally marking a free list is not a problem; only */
/* objects on the list itself will be marked, and that's fixed here. */
{
register word size; /* current object size */
register ptr←t p; /* pointer to current object */
register struct hblk * h; /* pointer to block containing *p */
register hdr * hhdr;
register int word←no; /* "index" of *p in *q */
int kind;
for (kind = 0; kind < GC←n←kinds; kind++) {
for (size = 1; size <= MAXOBJSZ; size++) {
for (p= GC←obj←kinds[kind].ok←freelist[size];
p != 0; p=obj←link(p)){
h = HBLKPTR(p);
hhdr = HDR(h);
word←no = (((word *)p) - ((word *)h));
clear←mark←bit←from←hdr(hhdr, word←no);
GC←mem←found -= size;
}
}
}
}
# ifdef PRINTSTATS
GC←printf1("Bytes recovered before GC←reclaim - f.l. count = %ld\n",
(long)WORDS←TO←BYTES(GC←mem←found));
# endif
/* Reconstruct free lists to contain everything not marked */
GC←start←reclaim(FALSE);
# endif /* FIND←LEAK */
# ifdef PRINTSTATS
GC←printf2(
"Immediately reclaimed %ld bytes in heap of size %lu bytes\n",
(long)WORDS←TO←BYTES(GC←mem←found),
(unsigned long)GC←heapsize);
GC←printf2("%lu (atomic) + %lu (composite) bytes in use\n",
(unsigned long)WORDS←TO←BYTES(GC←atomic←in←use),
(unsigned long)WORDS←TO←BYTES(GC←composite←in←use));
# endif
/* Reset or increment counters for next cycle */
GC←words←allocd←before←gc += GC←words←allocd;
GC←non←gc←bytes←at←gc = GC←non←gc←bytes;
GC←words←allocd = 0;
GC←mem←freed = 0;
/* Get final time */
# ifdef PRINTTIMES
GET←TIME(done←time);
GC←printf2("Garbage collection took %lu + %lu msecs\n",
MS←TIME←DIFF(mark←time,start←time),
MS←TIME←DIFF(done←time,mark←time));
# endif
return(TRUE);
}
/* Externally callable version of above */
void GC←gcollect()
{
DCL←LOCK←STATE;
DISABLE←SIGNALS();
LOCK();
if (!GC←is←initialized) GC←init←inner();
/* Minimize junk left in my registers */
GC←noop(0,0,0,0,0,0);
(void) GC←gcollect←inner(TRUE);
UNLOCK();
ENABLE←SIGNALS();
}
/*
* Use the chunk of memory starting at p of syze bytes as part of the heap.
* Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
*/
void GC←add←to←heap(p, bytes)
struct hblk *p;
word bytes;
{
word words;
GC←install←header(p);
words = BYTES←TO←WORDS(bytes - HDR←BYTES);
HDR(p) -> hb←sz = words;
GC←freehblk(p);
GC←heapsize += bytes;
if ((ptr←t)p <= GC←least←plausible←heap←addr
|| GC←least←plausible←heap←addr == 0) {
GC←least←plausible←heap←addr = (ptr←t)p - sizeof(word);
/* Making it a little smaller than necessary prevents */
/* us from getting a false hit from the variable */
/* itself. There's some unintentional reflection */
/* here. */
}
if ((ptr←t)p + bytes >= GC←greatest←plausible←heap←addr) {
GC←greatest←plausible←heap←addr = (ptr←t)p + bytes;
}
}
ptr←t GC←least←plausible←heap←addr = (ptr←t)ONES;
ptr←t GC←greatest←plausible←heap←addr = 0;
ptr←t GC←max(x,y)
ptr←t x, y;
{
return(x > y? x : y);
}
ptr←t GC←min(x,y)
ptr←t x, y;
{
return(x < y? x : y);
}
/*
* this explicitly increases the size of the heap. It is used
* internally, but my also be invoked from GC←expand←hp by the user.
* The argument is in units of HBLKSIZE.
* Returns FALSE on failure.
*/
bool GC←expand←hp←inner(n)
word n;
{
word bytes = n * HBLKSIZE;
struct hblk * space = GET←MEM(bytes);
word expansion←slop; /* Number of bytes by which we expect the */
/* heap to expand soon. */
if (n > 2*GC←hincr) {
GC←hincr = n/2;
}
if( space == 0 ) {
return(FALSE);
}
# ifdef PRINTSTATS
GC←printf1("Increasing heap size by %lu\n",
(unsigned long)bytes);
# endif
expansion←slop = 8 * WORDS←TO←BYTES(min←words←allocd());
if (5 * HBLKSIZE * MAXHINCR > expansion←slop) {
expansion←slop = 5 * HBLKSIZE * MAXHINCR;
}
if (GC←last←heap←addr == 0 && !((word)space & SIGNB)
|| GC←last←heap←addr != 0 && GC←last←heap←addr < (ptr←t)space) {
/* Assume the heap is growing up */
GC←greatest←plausible←heap←addr =
GC←max(GC←greatest←plausible←heap←addr,
(ptr←t)space + bytes + expansion←slop);
} else {
/* Heap is growing down */
GC←least←plausible←heap←addr =
GC←min(GC←least←plausible←heap←addr,
(ptr←t)space - expansion←slop);
}
GC←prev←heap←addr = GC←last←heap←addr;
GC←last←heap←addr = (ptr←t)space;
GC←add←to←heap(space, bytes);
return(TRUE);
}
/* Really returns a bool, but it's externally visible, so that's clumsy. */
int GC←expand←hp(n)
int n;
{
int result;
DCL←LOCK←STATE;
DISABLE←SIGNALS();
LOCK();
if (!GC←is←initialized) GC←init←inner();
result = (int)GC←expand←hp←inner((word)n);
UNLOCK();
ENABLE←SIGNALS();
return(result);
}
void GC←collect←or←expand(needed←blocks)
word needed←blocks;
{
static int count = 0; /* How many failures? */
if (GC←dont←gc || !GC←gcollect←inner(FALSE)) {
if (!GC←expand←hp←inner(GC←hincr + needed←blocks)
&& !GC←expand←hp←inner(needed←blocks)) {
if (count++ < 20) {
WARN("Out of Memory! Trying to continue ...\n");
(void) GC←gcollect←inner(TRUE);
} else {
GC←err←printf0("Out of Memory! Giving up!\n");
EXIT();
}
}
update←GC←hincr;
}
}
/*
* Make sure the object free list for sz is not empty.
* Return a pointer to the first object on the free list.
* The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
*
*/
ptr←t GC←allocobj(sz, kind)
word sz;
int kind;
{
register ptr←t * flh = &(GC←obj←kinds[kind].ok←freelist[sz]);
if (sz == 0) return(0);
while (*flh == 0) {
GC←continue←reclaim(sz, kind);
if (*flh == 0) {
GC←new←hblk(sz, kind);
}
if (*flh == 0) {
GC←collect←or←expand((word)1);
}
}
return(*flh);
}