/*
* 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.
*/
#include <stdio.h>
#include "gc←private.h"
signed←word GC←mem←found = 0;
/* Number of longwords of memory GC←reclaimed */
# ifdef FIND←LEAK
static report←leak(p, sz)
ptr←t p;
word sz;
{
if (HDR(p) -> hb←obj←kind == PTRFREE) {
GC←err←printf0("Leaked atomic object at ");
} else {
GC←err←printf0("Leaked composite object at ");
}
if (GC←debugging←started && GC←has←debug←info(p)) {
GC←print←obj(p);
} else {
GC←err←printf1("0x%lx (appr. size = %ld)\n",
(unsigned long)WORDS←TO←BYTES(sz));
}
}
# define FOUND←FREE(hblk, word←no) \
if (abort←if←found) { \
report←leak((long)hblk + WORDS←TO←BYTES(word←no), \
HDR(hblk) -> hb←sz); \
}
# else
# define FOUND←FREE(hblk, word←no)
# endif
/*
* reclaim phase
*
*/
/*
* Test whether a block is completely empty, i.e. contains no marked
* objects. This does not require the block to be in physical
* memory.
*/
bool GC←block←empty(hhdr)
register hdr * hhdr;
{
register word *p = (word *)(&(hhdr -> hb←marks[0]));
register word * plim =
(word *)(&(hhdr -> hb←marks[MARK←BITS←SZ]));
while (p < plim) {
if (*p++) return(FALSE);
}
return(TRUE);
}
# ifdef GATHERSTATS
# define INCR←WORDS(sz) n←words←found += (sz)
# else
# define INCR←WORDS(sz)
# endif
/*
* Restore unmarked small objects in h of size sz to the object
* free list. Returns the new list.
* Clears unmarked objects.
*/
/*ARGSUSED*/
ptr←t GC←reclaim←clear(hbp, hhdr, sz, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
register hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
register word sz;
{
register int word←no;
register word *p, *q, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
p = (word *)(hbp->hb←body);
word←no = HDR←WORDS;
plim = (word *)((((word)hbp) + HBLKSIZE)
- WORDS←TO←BYTES(sz));
/* go through all words in block */
while( p <= plim ) {
if( mark←bit←from←hdr(hhdr, word←no) ) {
p += sz;
} else {
FOUND←FREE(hbp, word←no);
INCR←WORDS(sz);
/* object is available - put on list */
obj←link(p) = list;
list = ((ptr←t)p);
/* Clear object, advance p to next object in the process */
q = p + sz;
p++; /* Skip link field */
while (p < q) {
*p++ = 0;
}
}
word←no += sz;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
}
/*
* A special case for 2 word composite objects (e.g. cons cells):
*/
/*ARGSUSED*/
ptr←t GC←reclaim←clear2(hbp, hhdr, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
{
register word * mark←word←addr = &(hhdr->hb←marks[divWORDSZ(HDR←WORDS)]);
register word *p, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
register int mark←word;
# define DO←OBJ(start←displ) \
if (!(mark←word & (1 << start←displ))) { \
FOUND←FREE(hbp, p - (word *)hbp + start←displ); \
p[start←displ] = (word)list; \
list = (ptr←t)(p+start←displ); \
p[start←displ+1] = 0; \
INCR←WORDS(2); \
}
p = (word *)(hbp->hb←body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
/* go through all words in block */
while( p < plim ) {
mark←word = *mark←word←addr++;
DO←OBJ(0);
DO←OBJ(2);
DO←OBJ(4);
DO←OBJ(6);
DO←OBJ(8);
DO←OBJ(10);
DO←OBJ(12);
DO←OBJ(14);
DO←OBJ(16);
DO←OBJ(18);
DO←OBJ(20);
DO←OBJ(22);
DO←OBJ(24);
DO←OBJ(26);
DO←OBJ(28);
DO←OBJ(30);
p+=32;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
# undef DO←OBJ
}
/*
* Another special case for 4 word composite objects:
*/
/*ARGSUSED*/
ptr←t GC←reclaim←clear4(hbp, hhdr, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
{
register word * mark←word←addr = &(hhdr->hb←marks[divWORDSZ(HDR←WORDS)]);
register word *p, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
register int mark←word;
# define DO←OBJ(start←displ) \
if (!(mark←word & (1 << start←displ))) { \
FOUND←FREE(hbp, p - (word *)hbp + start←displ); \
p[start←displ] = (word)list; \
list = (ptr←t)(p+start←displ); \
p[start←displ+1] = 0; \
p[start←displ+2] = 0; \
p[start←displ+3] = 0; \
INCR←WORDS(4); \
}
p = (word *)(hbp->hb←body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
/* go through all words in block */
while( p < plim ) {
mark←word = *mark←word←addr++;
DO←OBJ(0);
DO←OBJ(4);
DO←OBJ(8);
DO←OBJ(12);
DO←OBJ(16);
DO←OBJ(20);
DO←OBJ(24);
DO←OBJ(28);
p+=32;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
# undef DO←OBJ
}
/* The same thing, but don't clear objects: */
/*ARGSUSED*/
ptr←t GC←reclaim←uninit(hbp, hhdr, sz, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
register hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
register word sz;
{
register int word←no;
register word *p, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
p = (word *)(hbp->hb←body);
word←no = HDR←WORDS;
plim = (word *)((((unsigned)hbp) + HBLKSIZE)
- WORDS←TO←BYTES(sz));
/* go through all words in block */
while( p <= plim ) {
if( !mark←bit←from←hdr(hhdr, word←no) ) {
FOUND←FREE(hbp, word←no);
INCR←WORDS(sz);
/* object is available - put on list */
obj←link(p) = list;
list = ((ptr←t)p);
}
p += sz;
word←no += sz;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
}
/*
* Another special case for 2 word atomic objects:
*/
/*ARGSUSED*/
ptr←t GC←reclaim←uninit2(hbp, hhdr, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
{
register word * mark←word←addr = &(hhdr->hb←marks[divWORDSZ(HDR←WORDS)]);
register word *p, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
register int mark←word;
# define DO←OBJ(start←displ) \
if (!(mark←word & (1 << start←displ))) { \
FOUND←FREE(hbp, p - (word *)hbp + start←displ); \
p[start←displ] = (word)list; \
list = (ptr←t)(p+start←displ); \
INCR←WORDS(2); \
}
p = (word *)(hbp->hb←body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
/* go through all words in block */
while( p < plim ) {
mark←word = *mark←word←addr++;
DO←OBJ(0);
DO←OBJ(2);
DO←OBJ(4);
DO←OBJ(6);
DO←OBJ(8);
DO←OBJ(10);
DO←OBJ(12);
DO←OBJ(14);
DO←OBJ(16);
DO←OBJ(18);
DO←OBJ(20);
DO←OBJ(22);
DO←OBJ(24);
DO←OBJ(26);
DO←OBJ(28);
DO←OBJ(30);
p+=32;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
# undef DO←OBJ
}
/*
* Another special case for 4 word atomic objects:
*/
/*ARGSUSED*/
ptr←t GC←reclaim←uninit4(hbp, hhdr, list, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
hdr * hhdr;
bool abort←if←found; /* Abort if a reclaimable object is found */
register ptr←t list;
{
register word * mark←word←addr = &(hhdr->hb←marks[divWORDSZ(HDR←WORDS)]);
register word *p, *plim;
# ifdef GATHERSTATS
register int n←words←found = 0;
# endif
register int mark←word;
# define DO←OBJ(start←displ) \
if (!(mark←word & (1 << start←displ))) { \
FOUND←FREE(hbp, p - (word *)hbp + start←displ); \
p[start←displ] = (word)list; \
list = (ptr←t)(p+start←displ); \
INCR←WORDS(4); \
}
p = (word *)(hbp->hb←body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
/* go through all words in block */
while( p < plim ) {
mark←word = *mark←word←addr++;
DO←OBJ(0);
DO←OBJ(4);
DO←OBJ(8);
DO←OBJ(12);
DO←OBJ(16);
DO←OBJ(20);
DO←OBJ(24);
DO←OBJ(28);
p+=32;
}
# ifdef GATHERSTATS
GC←mem←found += n←words←found;
# endif
return(list);
# undef DO←OBJ
}
/*
* Restore unmarked small objects in the block pointed to by hbp
* to the appropriate object free list.
* If entirely empty blocks are to be completely deallocated, then
* caller should perform that check.
*/
GC←reclaim←small←nonempty←block(hbp, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
int abort←if←found; /* Abort if a reclaimable object is found */
{
hdr * hhdr;
register word sz; /* size of objects in current block */
register struct obj←kind * ok;
register ptr←t * flh;
hhdr = HDR(hbp);
sz = hhdr -> hb←sz;
ok = &GC←obj←kinds[hhdr -> hb←obj←kind];
flh = &(ok -> ok←freelist[sz]);
if (ok -> ok←init) {
switch(sz) {
case 2:
*flh = GC←reclaim←clear2(hbp, hhdr, *flh, abort←if←found);
break;
case 4:
*flh = GC←reclaim←clear4(hbp, hhdr, *flh, abort←if←found);
break;
default:
*flh = GC←reclaim←clear(hbp, hhdr, sz, *flh, abort←if←found);
break;
}
} else {
switch(sz) {
case 2:
*flh = GC←reclaim←uninit2(hbp, hhdr, *flh, abort←if←found);
break;
case 4:
*flh = GC←reclaim←uninit4(hbp, hhdr, *flh, abort←if←found);
break;
default:
*flh = GC←reclaim←uninit(hbp, hhdr, sz, *flh, abort←if←found);
break;
}
}
}
/*
* Restore an unmarked large object or an entirely empty blocks of small objects
* to the heap block free list.
* Otherwise enqueue the block for later processing
* by GC←reclaim←small←nonempty←block.
* If abort←if←found is TRUE, then process any block immediately.
*/
void GC←reclaim←block(hbp, abort←if←found)
register struct hblk *hbp; /* ptr to current heap block */
int abort←if←found; /* Abort if a reclaimable object is found */
{
register hdr * hhdr;
register word sz; /* size of objects in current block */
bool empty; /* used only for PRINTBLOCKS */
register struct obj←kind * ok;
struct hblk ** rlh;
hhdr = HDR(hbp);
sz = hhdr -> hb←sz;
ok = &GC←obj←kinds[hhdr -> hb←obj←kind];
# ifdef PRINTBLOCKS
GC←printf1("%ld(", (unsigned long)sz);
if (hhdr -> hb←obj←kind == PTRFREE) {
GC←printf0("a");
} else if (hhdr -> hb←obj←kind == NORMAL){
GC←printf0("c");
} else {
GC←printf0("o");
}
# endif
if( sz > MAXOBJSZ ) { /* 1 big object */
if( mark←bit←from←hdr(hhdr, HDR←WORDS) ) {
empty = FALSE;
} else {
FOUND←FREE(hbp, HDR←WORDS);
# ifdef GATHERSTATS
GC←mem←found += sz;
# endif
GC←freehblk(hbp);
empty = TRUE;
}
} else {
empty = GC←block←empty(hhdr);
if (abort←if←found) {
GC←reclaim←small←nonempty←block(hbp, abort←if←found);
} else if (empty) {
# ifdef GATHERSTATS
GC←mem←found += BYTES←TO←WORDS(HBLKSIZE);
# endif
GC←freehblk(hbp);
} else {
/* group of smaller objects, enqueue the real work */
rlh = &(ok -> ok←reclaim←list[sz]);
hhdr -> hb←next = *rlh;
*rlh = hbp;
}
}
# ifdef PRINTBLOCKS
if (empty) {GC←printf0("e),");} else {GC←printf0("n),");}
# endif
}
/*
* Do the same thing on the entire heap, after first clearing small object
* free lists (if we are not just looking for leaks).
*/
void GC←start←reclaim(abort←if←found)
int abort←if←found; /* Abort if a GC←reclaimable object is found */
{
int kind;
/* Clear reclaim- and free-lists */
for (kind = 0; kind < GC←n←kinds; kind++) {
register ptr←t *fop;
register ptr←t *lim;
register struct hblk ** hbpp;
register struct hblk ** hlim;
if (!abort←if←found) {
lim = &(GC←obj←kinds[kind].ok←freelist[MAXOBJSZ+1]);
for( fop = GC←obj←kinds[kind].ok←freelist; fop < lim; fop++ ) {
*fop = 0;
}
} /* otherwise free list objects are marked, */
/* and its safe to leave them */
hlim = &(GC←obj←kinds[kind].ok←reclaim←list[MAXOBJSZ+1]);
for( hbpp = GC←obj←kinds[kind].ok←reclaim←list;
hbpp < hlim; hbpp++ ) {
*hbpp = 0;
}
}
# ifdef PRINTBLOCKS
GC←printf0("GC←reclaim: current block sizes:\n");
# endif
/* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
/* or enqueue the block for later processing. */
GC←apply←to←all←blocks(GC←reclaim←block, abort←if←found);
# ifdef PRINTBLOCKS
GC←printf0("\n");
# endif
}
/*
* Sweep blocks of the indicated object size and kind until either the
* appropriate free list is nonempty, or there are no more blocks to
* sweep.
*/
void GC←continue←reclaim(sz, kind)
word sz; /* words */
int kind;
{
register hdr * hhdr;
register struct hblk * hbp;
register struct obj←kind * ok = &(GC←obj←kinds[kind]);
struct hblk ** rlh = &(ok -> ok←reclaim←list[sz]);
ptr←t *flh = &(ok -> ok←freelist[sz]);
while ((hbp = *rlh) != 0) {
hhdr = HDR(hbp);
*rlh = hhdr -> hb←next;
GC←reclaim←small←nonempty←block(hbp, FALSE);
if (*flh != 0) break;
}
}