/* An incomplete test for the garbage collector. */
/* Some more obscure entry points are not tested at all. */
# include <stdlib.h>
# include <stdio.h>
# include "gc.h"
# ifdef PCR
# include "th/PCR←ThCrSec.h"
# include "th/PCR←Th.h"
# endif
/* AT←END may be defined to excercise the interior pointer test */
/* if the collector is configured with ALL←INTERIOR←POINTERS. */
/* As it stands, this test should succeed with either */
/* configuration. In the FIND←LEAK configuration, it should */
/* find lots of leaks, since we free almost nothing. */
struct SEXPR {
struct SEXPR * sexpr←car;
struct SEXPR * sexpr←cdr;
};
# ifdef ←←STDC←←
typedef void * void←star;
# else
typedef char * void←star;
# endif
typedef struct SEXPR * sexpr;
extern sexpr cons();
# define nil ((sexpr) 0)
# define car(x) ((x) -> sexpr←car)
# define cdr(x) ((x) -> sexpr←cdr)
# define is←nil(x) ((x) == nil)
int extra←count = 0; /* Amount of space wasted in cons node */
/* Silly implementation of Lisp cons. Intentionally wastes lots of space */
/* to test collector. */
sexpr cons (x, y)
sexpr x;
sexpr y;
{
register sexpr r;
register int *p;
register my←extra = extra←count;
r = (sexpr) GC←MALLOC(sizeof(struct SEXPR) + my←extra);
if (r == 0) {
(void)printf("Out of memory\n");
exit(1);
}
for (p = (int *)r;
((char *)p) < ((char *)r) + my←extra + sizeof(struct SEXPR); p++) {
if (*p) {
(void)printf("Found nonzero at %X\n - allocator is broken", p);
exit(1);
}
*p = 13;
}
# ifdef AT←END
r = (sexpr)((char *)r + (my←extra & ~7));
# endif
r -> sexpr←car = x;
r -> sexpr←cdr = y;
extra←count = (my←extra + 1) % 5000;
return(r);
}
sexpr small←cons (x, y)
sexpr x;
sexpr y;
{
register sexpr r;
register int *p;
r = (sexpr) GC←MALLOC(sizeof(struct SEXPR));
if (r == 0) {
(void)printf("Out of memory\n");
exit(1);
}
r -> sexpr←car = x;
r -> sexpr←cdr = y;
return(r);
}
/* Return reverse(x) concatenated with y */
sexpr reverse1(x, y)
sexpr x, y;
{
if (is←nil(x)) {
return(y);
} else {
return( reverse1(cdr(x), cons(car(x), y)) );
}
}
sexpr reverse(x)
sexpr x;
{
return( reverse1(x, nil) );
}
sexpr ints(low, up)
int low, up;
{
if (low > up) {
return(nil);
} else {
return(small←cons(small←cons((sexpr)low, 0), ints(low+1, up)));
}
}
void check←ints(list, low, up)
sexpr list;
int low, up;
{
if ((int)(car(car(list))) != low) {
(void)printf(
"List reversal produced incorrect list - collector is broken\n");
exit(1);
}
if (low == up) {
if (cdr(list) != nil) {
(void)printf("List too long - collector is broken\n");
exit(1);
}
} else {
check←ints(cdr(list), low+1, up);
}
}
/* Not used, but useful for debugging: */
void print←int←list(x)
sexpr x;
{
if (is←nil(x)) {
(void)printf("NIL\n");
} else {
(void)printf("(%d)", car(car(x)));
if (!is←nil(cdr(x))) {
(void)printf(", ");
(void)print←int←list(cdr(x));
} else {
(void)printf("\n");
}
}
}
/* Try to force a to be strangely aligned */
struct {
char dummy;
sexpr aa;
} A;
#define a A.aa
/*
* Repeatedly reverse lists built out of very different sized cons cells.
* Check that we didn't lose anything.
*/
reverse←test()
{
int i;
sexpr b;
sexpr c;
a = ints(1, 100);
b = ints(1, 50);
c = ints(1, 4500);
for (i = 0; i < 50; i++) {
b = reverse(reverse(b));
}
for (i = 0; i < 10; i++) {
/* This maintains the invariant that a always points to a list of */
/* 100 integers. Thus this is thread safe without locks. */
a = reverse(reverse(a));
# if !defined(AT←END) && !defined(PCR)
/* This is not thread safe, since realloc explicitly deallocates */
if (i & 1) {
a = (sexpr)GC←REALLOC((void←star)a, 500);
} else {
a = (sexpr)GC←REALLOC((void←star)a, 4200);
}
# endif
}
check←ints(a,1,100);
check←ints(b,1,50);
check←ints(c,1,4500);
a = b = c = 0;
}
/*
* The rest of this builds balanced binary trees, checks that they don't
* disappear, and tests finalization.
*/
typedef struct treenode {
int level;
struct treenode * lchild;
struct treenode * rchild;
} tn;
int finalizable←count = 0;
int finalized←count = 0;
int dropped←something = 0;
# ifdef ←←STDC←←
void finalizer(void * obj, void * client←data)
# else
void finalizer(obj, client←data)
char * obj;
char * client←data;
# endif
{
tn * t = (tn *)obj;
if ((int)client←data != t -> level) {
(void)printf("Wrong finalization data - collector is broken\n");
exit(1);
}
finalized←count++;
}
size←t counter = 0;
tn * mktree(n)
int n;
{
tn * result = (tn *)GC←MALLOC(sizeof(tn));
if (n == 0) return(0);
if (result == 0) {
(void)printf("Out of memory\n");
exit(1);
}
result -> level = n;
result -> lchild = mktree(n-1);
result -> rchild = mktree(n-1);
if (counter++ % 119 == 0) {
GC←REGISTER←FINALIZER((void←star)result, finalizer, (void←star)n,
(GC←finalization←proc *)0, (void←star *)0);
# ifdef PCR
PCR←ThCrSec←EnterSys();
/* Losing a count here causes erroneous report of failure. */
# endif
finalizable←count++;
# ifdef PCR
PCR←ThCrSec←ExitSys();
# endif
}
return(result);
}
void chktree(t,n)
tn *t;
int n;
{
if (n == 0 && t != 0) {
(void)printf("Clobbered a leaf - collector is broken\n");
exit(1);
}
if (n == 0) return;
if (t -> level != n) {
(void)printf("Lost a node at level %d - collector is broken\n", n);
exit(1);
}
if (counter++ % 373 == 0) (void) GC←MALLOC(counter%5001);
chktree(t -> lchild, n-1);
if (counter++ % 73 == 0) (void) GC←MALLOC(counter%373);
chktree(t -> rchild, n-1);
}
void alloc←small(n)
int n;
{
register int i;
for (i = 0; i < n; i += 8) {
if (GC←MALLOC←ATOMIC(8) == 0) {
(void)printf("Out of memory\n");
exit(1);
}
}
}
tree←test()
{
tn * root = mktree(16);
register int i;
alloc←small(5000000);
chktree(root, 16);
if (finalized←count && ! dropped←something) {
(void)printf("Premature finalization - collector is broken\n");
exit(1);
}
dropped←something = 1;
root = mktree(16);
chktree(root, 16);
for (i = 16; i >= 0; i--) {
root = mktree(i);
chktree(root, i);
}
alloc←small(5000000);
}
# include "gc←private.h"
int n←tests = 0;
void run←one←test()
{
DCL←LOCK←STATE;
reverse←test();
tree←test();
LOCK();
n←tests++;
UNLOCK();
}
void check←heap←stats()
{
(void)printf("Completed %d tests\n", n←tests);
(void)printf("Finalized %d/%d objects - ",
finalized←count, finalizable←count);
if (finalized←count > finalizable←count
|| finalized←count < finalizable←count/2) {
(void)printf ("finalization is probably broken\n");
exit(1);
} else {
(void)printf ("finalization is probably ok\n");
}
(void)printf("Total number of bytes allocated is %d\n",
WORDS←TO←BYTES(GC←words←allocd + GC←words←allocd←before←gc));
(void)printf("Final heap size is %d bytes\n", GC←heapsize);
if (WORDS←TO←BYTES(GC←words←allocd + GC←words←allocd←before←gc)
< 33500000*n←tests) {
(void)printf("Incorrect execution - missed some allocations\n");
exit(1);
}
if (GC←heapsize > 10000000*n←tests) {
(void)printf("Unexpected heap growth - collector may be broken\n");
exit(1);
}
(void)printf("Collector appears to work\n");
}
#ifndef PCR
main()
{
n←tests = 0;
run←one←test();
check←heap←stats();
(void)fflush(stdout);
return(0);
}
# else
test()
{
PCR←Th←T * th1;
PCR←Th←T * th2;
int code;
n←tests = 0;
th1 = PCR←Th←Fork(run←one←test, 0);
th2 = PCR←Th←Fork(run←one←test, 0);
run←one←test();
if (PCR←Th←T←Join(th1, &code, NIL, PCR←allSigsBlocked, PCR←waitForever)
!= PCR←ERes←okay || code != 0) {
(void)printf("Thread 1 failed\n");
}
if (PCR←Th←T←Join(th2, &code, NIL, PCR←allSigsBlocked, PCR←waitForever)
!= PCR←ERes←okay || code != 0) {
(void)printf("Thread 2 failed\n");
}
check←heap←stats();
(void)fflush(stdout);
return(0);
}
#endif