/*
* 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 "gc←private.h"
/*
* We maintain several hash tables of hblks that have had false hits.
* Each contains one bit per hash bucket; If any page in the bucket
* has had a false hit, we assume that all of them have.
* False hits from the stack(s) are much more dangerous than false hits
* from elsewhere, since the former can pin a large object that spans the
* block, eventhough it does not start on the dangerous block.
*/
/*
* Externally callable routines are:
* GC←add←to←black←list←normal
* GC←add←to←black←list←stack
* GC←promote←black←lists
* GC←is←black←listed
*
* All require that the allocator lock is held.
*/
# define LOG←HT←ENTRIES 14 /* Collisions are likely if heap grows */
/* to more than 16K hblks = 64MB. */
/* Each hash table occupies 2K bytes. */
# define HT←ENTRIES ((word)1 << LOG←HT←ENTRIES)
# define HT←SIZE (HT←ENTRIES >> LOGWL)
typedef word black←list←t[HT←SIZE];
# define HASH(addr) (((addr) >> LOG←HBLKSIZE) & (HT←ENTRIES - 1))
/* Pointers to individual tables. We replace one table by another by */
/* switching these pointers. GC←black←lists is not used directly. */
word * GC←new←normal←bl;
/* Nonstack false references seen at last complete */
/* collection. */
word * GC←old←normal←bl;
/* Nonstack false references seen at preceding */
/* collection. */
word * GC←incomplete←normal←bl;
/* Nonstack false references seen at current, */
/* not yet completed collection. */
word * GC←new←stack←bl;
word * GC←old←stack←bl;
word * GC←incomplete←stack←bl;
# define get←bl←entry←from←index(bl, index) \
(((bl)[divWORDSZ(index)] >> modWORDSZ(index)) & 1)
# define set←bl←entry←from←index(bl, index) \
(bl)[divWORDSZ(index)] |= 1 << modWORDSZ(index)
# define clear←bl←entry←from←index(bl, index) \
(bl)[divWORDSZ(index)] &= ~(1 << modWORDSZ(index))
GC←bl←init()
{
# ifndef ALL←INTERIOR←POINTERS
GC←new←normal←bl = (word *)GC←scratch←alloc((word)(sizeof(black←list←t)));
GC←old←normal←bl = (word *)GC←scratch←alloc((word)(sizeof (black←list←t)));
GC←incomplete←normal←bl = (word *)GC←scratch←alloc
((word)(sizeof(black←list←t)));
# endif
GC←new←stack←bl = (word *)GC←scratch←alloc((word)(sizeof(black←list←t)));
GC←old←stack←bl = (word *)GC←scratch←alloc((word)(sizeof(black←list←t)));
GC←incomplete←stack←bl = (word *)GC←scratch←alloc
((word)(sizeof(black←list←t)));
}
void GC←clear←bl(doomed)
word *doomed;
{
bzero((char *)doomed, (int)HT←SIZE*sizeof(word));
}
/* Signal the completion of a collection. Turn the incomplete black */
/* lists into new black lists, etc. */
void GC←promote←black←lists()
{
word * very←old←normal←bl = GC←old←normal←bl;
word * very←old←stack←bl = GC←old←stack←bl;
GC←old←normal←bl = GC←new←normal←bl;
GC←new←normal←bl = GC←incomplete←normal←bl;
GC←old←stack←bl = GC←new←stack←bl;
GC←new←stack←bl = GC←incomplete←stack←bl;
# ifndef ALL←INTERIOR←POINTERS
GC←clear←bl(very←old←normal←bl);
# endif
GC←clear←bl(very←old←stack←bl);
GC←incomplete←normal←bl = very←old←normal←bl;
GC←incomplete←stack←bl = very←old←stack←bl;
}
# ifndef ALL←INTERIOR←POINTERS
/* P is not a valid pointer reference, but it falls inside */
/* the plausible heap bounds. */
/* Add it to the normal incomplete black list if appropriate. */
void GC←add←to←black←list←normal(p)
word p;
{
if (!(GC←modws←valid←offsets[p & (sizeof(word)-1)])) return;
{
register int index = HASH(p);
if (HDR(p) == 0 || get←bl←entry←from←index(GC←new←normal←bl, index)) {
# ifdef PRINTBLACKLIST
if (!get←bl←entry←from←index(GC←incomplete←normal←bl, index)) {
GC←printf1("Black listing (normal) 0x%lx\n",
(unsigned long) p);
}
# endif
set←bl←entry←from←index(GC←incomplete←normal←bl, index);
} /* else this is probably just an interior pointer to an allocated */
/* object, and isn't worth black listing. */
}
}
# endif
/* And the same for false pointers from the stack. */
void GC←add←to←black←list←stack(p)
word p;
{
register int index = HASH(p);
if (HDR(p) == 0 || get←bl←entry←from←index(GC←new←stack←bl, index)) {
# ifdef PRINTBLACKLIST
if (!get←bl←entry←from←index(GC←incomplete←stack←bl, index)) {
GC←printf1("Black listing (stack) 0x%lx\n",
(unsigned long)p);
}
# endif
set←bl←entry←from←index(GC←incomplete←stack←bl, index);
}
}
/*
* Is the block starting at h of size len bytes black listed? If so,
* return the address of the next plausible r such that (r, len) might not
* be black listed. (R may not actually be in the heap. We guarantee only
* that every smaller value of r after h is also black listed.)
* If (h,len) is not black listed, return 0.
* Knows about the structure of the black list hash tables.
*/
struct hblk * GC←is←black←listed(h, len)
struct hblk * h;
word len;
{
register int index = HASH((word)h);
register word i;
word nblocks = divHBLKSZ(len);
# ifndef ALL←INTERIOR←POINTERS
if (get←bl←entry←from←index(GC←new←normal←bl, index)
&& get←bl←entry←from←index(GC←old←normal←bl, index)) {
return(h+1);
}
# endif
for (i = 0; ; ) {
if (GC←new←stack←bl[divWORDSZ(index)] == 0) {
/* An easy case */
i += WORDSZ - modWORDSZ(index);
} else {
if (get←bl←entry←from←index(GC←new←stack←bl, index)
&& get←bl←entry←from←index(GC←old←stack←bl, index)) {
return(h+i+1);
}
i++;
}
if (i >= nblocks) break;
index = HASH((word)(h+i));
}
return(0);
}