/*
* 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.
*/
#define DEBUG
#undef DEBUG
#include <stdio.h>
#include "gc←private.h"
/**/
/* allocate/free routines for heap blocks
/* Note that everything called from outside the garbage collector
/* should be prepared to abort at any point as the result of a signal.
/**/
/*
* Free heap blocks are kept on a list sorted by address.
* The hb←hdr.hbh←sz field of a free heap block contains the length
* (in bytes) of the entire block.
* Neighbors are coalesced.
*/
# define MAX←BLACK←LIST←ALLOC (2*HBLKSIZE)
/* largest block we will allocate starting on a black */
/* listed block. Must be >= HBLKSIZE. */
struct hblk * GC←hblkfreelist = 0;
struct hblk *GC←savhbp = (struct hblk *)0; /* heap block preceding next */
/* block to be examined by */
/* GC←allochblk. */
/* Initialize hdr for a block containing the indicated size and */
/* kind of objects. */
static setup←header(hhdr, sz, kind)
register hdr * hhdr;
word sz; /* object size in words */
int kind;
{
/* Set size, kind and mark proc fields */
hhdr -> hb←sz = sz;
hhdr -> hb←obj←kind = kind;
hhdr -> hb←mark←proc = GC←obj←kinds[kind].ok←mark←proc;
/* Add description of valid object pointers */
GC←add←map←entry(sz);
hhdr -> hb←map = GC←obj←map[sz > MAXOBJSZ? 0 : sz];
/* Clear mark bits */
GC←clear←hdr←marks(hhdr);
}
/*
* Allocate (and return pointer to) a heap block
* for objects of size |sz| words.
*
* NOTE: We set obj←map field in header correctly.
* Caller is resposnsible for building an object freelist in block.
*
* We clear the block if it is destined for large objects, and if
* kind requires that newly allocated objects be cleared.
*/
struct hblk *
GC←allochblk(sz, kind)
word sz;
int kind;
{
register struct hblk *thishbp;
register hdr * thishdr; /* Header corr. to thishbp */
register struct hblk *hbp;
register hdr * hhdr; /* Header corr. to hbp */
struct hblk *prevhbp;
register hdr * phdr; /* Header corr. to prevhbp */
signed←word size←needed; /* number of bytes in requested objects */
signed←word size←avail; /* bytes available in this block */
bool first←time = TRUE;
size←needed = WORDS←TO←BYTES(sz);
size←needed = (size←needed+HDR←BYTES+HBLKSIZE-1) & ~HBLKMASK;
/* search for a big enough block in free list */
hbp = GC←savhbp;
hhdr = HDR(hbp);
for(;;) {
prevhbp = hbp;
phdr = hhdr;
hbp = (prevhbp == 0? GC←hblkfreelist : phdr->hb←next);
hhdr = HDR(hbp);
if( prevhbp == GC←savhbp && !first←time) {
return(0);
}
first←time = FALSE;
if( hbp == 0 ) continue;
size←avail = hhdr->hb←sz;
if (size←avail < size←needed) continue;
/* If the next heap block is obviously better, go on. */
/* This prevents us from disassembling a single large block */
/* to get tiny blocks. */
{
word next←size;
thishbp = hhdr -> hb←next;
if (thishbp == 0) thishbp = GC←hblkfreelist;
thishdr = HDR(thishbp);
next←size = thishdr -> hb←sz;
if (next←size < size←avail
&& next←size >= size←needed
&& !GC←is←black←listed(thishbp, (word)size←needed)) {
continue;
}
}
if ( kind != PTRFREE || size←needed > MAX←BLACK←LIST←ALLOC) {
struct hblk * lasthbp = hbp;
while (size←avail >= size←needed
&& (thishbp = GC←is←black←listed(lasthbp,
(word)size←needed))) {
lasthbp = thishbp;
}
size←avail -= (ptr←t)lasthbp - (ptr←t)hbp;
thishbp = lasthbp;
if (size←avail >= size←needed && thishbp != hbp) {
/* Split the block at thishbp */
GC←install←header(thishbp);
thishdr = HDR(thishbp);
/* GC←invalidate←map not needed, since we will */
/* allocate this block. */
thishdr -> hb←next = hhdr -> hb←next;
thishdr -> hb←sz = size←avail;
hhdr -> hb←sz = (ptr←t)thishbp - (ptr←t)hbp;
hhdr -> hb←next = thishbp;
/* Advance to thishbp */
prevhbp = hbp;
phdr = hhdr;
hbp = thishbp;
hhdr = thishdr;
} else if (size←avail == 0
&& size←needed == HBLKSIZE
&& prevhbp != 0) {
static unsigned count = 0;
/* The block is completely blacklisted. We need */
/* to drop some such blocks, since otherwise we spend */
/* all our time traversing them if pointerfree */
/* blocks are unpopular. */
/* A dropped block will be reconsidered at next GC. */
if ((++count & 3) == 0) {
/* Allocate and drop the block */
phdr -> hb←next = hhdr -> hb←next;
GC←install←counts(hbp, hhdr->hb←sz);
setup←header(hhdr,
BYTES←TO←WORDS(hhdr->hb←sz - HDR←BYTES),
PTRFREE);
if (GC←savhbp == hbp) GC←savhbp = prevhbp;
/* Restore hbp to point at free block */
hbp = prevhbp;
hhdr = phdr;
if (hbp == GC←savhbp) first←time = TRUE;
}
}
}
if( size←avail >= size←needed ) {
/* found a big enough block */
/* let thishbp --> the block */
/* set prevhbp, hbp to bracket it */
thishbp = hbp;
thishdr = hhdr;
if( size←avail == size←needed ) {
hbp = hhdr->hb←next;
hhdr = HDR(hbp);
} else {
hbp = (struct hblk *)
(((unsigned)thishbp) + size←needed);
GC←install←header(hbp);
hhdr = HDR(hbp);
GC←invalidate←map(hhdr);
hhdr->hb←next = thishdr->hb←next;
hhdr->hb←sz = size←avail - size←needed;
}
/* remove *thishbp from hblk freelist */
if( prevhbp == 0 ) {
GC←hblkfreelist = hbp;
} else {
phdr->hb←next = hbp;
}
/* save current list search position */
GC←savhbp = hbp;
break;
}
}
/* Clear block if necessary */
if (sz > MAXOBJSZ && GC←obj←kinds[kind].ok←init) {
bzero((char *)thishbp + HDR←BYTES, (int)(size←needed - HDR←BYTES));
}
/* Set up header */
setup←header(thishdr, sz, kind);
/* Add it to map of valid blocks */
GC←install←counts(thishbp, (word)size←needed);
return( thishbp );
}
/*
* Free a heap block.
*
* Coalesce the block with its neighbors if possible.
*
* All mark words are assumed to be cleared.
*/
void
GC←freehblk(p)
register struct hblk *p;
{
register hdr *phdr; /* Header corresponding to p */
register struct hblk *hbp, *prevhbp;
register hdr *hhdr, *prevhdr;
register signed←word size;
/* GC←savhbp may become invalid due to coalescing. Clear it. */
GC←savhbp = (struct hblk *)0;
phdr = HDR(p);
size = phdr->hb←sz;
size =
((WORDS←TO←BYTES(size)+HDR←BYTES+HBLKSIZE-1)
& (~HBLKMASK));
GC←remove←counts(p, (word)size);
phdr->hb←sz = size;
GC←invalidate←map(phdr);
prevhbp = 0;
hbp = GC←hblkfreelist;
hhdr = HDR(hbp);
while( (hbp != 0) && (hbp < p) ) {
prevhbp = hbp;
prevhdr = hhdr;
hbp = hhdr->hb←next;
hhdr = HDR(hbp);
}
/* Check for duplicate deallocation in the easy case */
if (hbp != 0 && (ptr←t)p + size > (ptr←t)hbp
|| prevhbp != 0 && (ptr←t)prevhbp + prevhdr->hb←sz > (ptr←t)p) {
GC←printf1("Duplicate large block deallocation of 0x%lx\n",
(unsigned long) p);
GC←printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
(unsigned long) prevhbp, (unsigned long) hbp);
}
/* Coalesce with successor, if possible */
if( (((word)p)+size) == ((word)hbp) ) {
phdr->hb←next = hhdr->hb←next;
phdr->hb←sz += hhdr->hb←sz;
GC←remove←header(hbp);
} else {
phdr->hb←next = hbp;
}
if( prevhbp == 0 ) {
GC←hblkfreelist = p;
} else if( (((word)prevhbp) + prevhdr->hb←sz)
== ((word)p) ) {
/* Coalesce with predecessor */
prevhdr->hb←next = phdr->hb←next;
prevhdr->hb←sz += phdr->hb←sz;
GC←remove←header(p);
} else {
prevhdr->hb←next = p;
}
}