test.c

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

/* 
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
 * Copyright (c) 1996 by Silicon Graphics.  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 use or copy this program
 * for any purpose,  provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 */
/* An incomplete test for the garbage collector.  		*/
/* Some more obscure entry points are not tested at all.	*/
/* This must be compiled with the same flags used to build the 	*/
/* GC.  It uses GC internals to allow more precise results	*/
/* checking for some of the tests.				*/

# undef GC_BUILD

#if defined(DBG_HDRS_ALL) || defined(MAKE_BACK_GRAPH)
#  define GC_DEBUG
#endif

# if defined(mips) && defined(SYSTYPE_BSD43)
    /* MIPS RISCOS 4 */
# else
#   include <stdlib.h>
# endif
# include <stdio.h>
# ifdef _WIN32_WCE
#   include <winbase.h>
#   define assert ASSERT
# else
#   include <assert.h>        /* Not normally used, but handy for debugging. */
# endif
# include "gc.h"
# include "gc_typed.h"
# include "private/gc_priv.h"	/* For output, locking, MIN_WORDS, 	*/
				/* and some statistics, and gcconfig.h.	*/

# if defined(MSWIN32) || defined(MSWINCE)
#   include <windows.h>
# endif

# ifdef PCR
#   include "th/PCR_ThCrSec.h"
#   include "th/PCR_Th.h"
#   define GC_printf printf
# endif

# if defined(GC_PTHREADS)
#   include <pthread.h>
# endif

# if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
    static CRITICAL_SECTION incr_cs;
# endif

#ifdef __STDC__
# include <stdarg.h>
#endif


/* Allocation Statistics */
int stubborn_count = 0;
int uncollectable_count = 0;
int collectable_count = 0;
int atomic_count = 0;
int realloc_count = 0;

#if defined(GC_AMIGA_FASTALLOC) && defined(AMIGA)

  extern void GC_amiga_free_all_mem(void);
  void Amiga_Fail(void){GC_amiga_free_all_mem();abort();}
# define FAIL (void)Amiga_Fail()
  void *GC_amiga_gctest_malloc_explicitly_typed(size_t lb, GC_descr d){
    void *ret=GC_malloc_explicitly_typed(lb,d);
    if(ret==NULL){
		if(!GC_dont_gc){
	      GC_gcollect();
	      ret=GC_malloc_explicitly_typed(lb,d);
		}
      if(ret==NULL){
        GC_printf("Out of memory, (typed allocations are not directly "
		  "supported with the GC_AMIGA_FASTALLOC option.)\n");
        FAIL;
      }
    }
    return ret;
  }
  void *GC_amiga_gctest_calloc_explicitly_typed(size_t a,size_t lb, GC_descr d){
    void *ret=GC_calloc_explicitly_typed(a,lb,d);
    if(ret==NULL){
		if(!GC_dont_gc){
	      GC_gcollect();
	      ret=GC_calloc_explicitly_typed(a,lb,d);
		}
      if(ret==NULL){
        GC_printf("Out of memory, (typed allocations are not directly "
		  "supported with the GC_AMIGA_FASTALLOC option.)\n");
        FAIL;
      }
    }
    return ret;
  }
# define GC_malloc_explicitly_typed(a,b) GC_amiga_gctest_malloc_explicitly_typed(a,b) 
# define GC_calloc_explicitly_typed(a,b,c) GC_amiga_gctest_calloc_explicitly_typed(a,b,c) 

#else /* !AMIGA_FASTALLOC */

# ifdef PCR
#   define FAIL (void)abort()
# else
#   ifdef MSWINCE
#     define FAIL DebugBreak()
#   else
#     define FAIL GC_abort("Test failed");
#   endif
# endif

#endif /* !AMIGA_FASTALLOC */

/* AT_END may be defined to exercise 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;
};


typedef struct SEXPR * sexpr;

# define INT_TO_SEXPR(x) ((sexpr)(GC_word)(x))
# define SEXPR_TO_INT(x) ((int)(GC_word)(x))

# undef nil
# define nil (INT_TO_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.                                                    */
# ifdef VERY_SMALL_CONFIG
#   define cons small_cons
# else
sexpr cons (sexpr x, sexpr y)
{
    sexpr r;
    int *p;
    int my_extra = extra_count;
    
    stubborn_count++;
    r = (sexpr) GC_MALLOC_STUBBORN(sizeof(struct SEXPR) + my_extra);
    if (r == 0) {
        (void)GC_printf("Out of memory\n");
        exit(1);
    }
    for (p = (int *)r;
         ((char *)p) < ((char *)r) + my_extra + sizeof(struct SEXPR); p++) {
	if (*p) {
	    (void)GC_printf("Found nonzero at %p - allocator is broken\n", p);
	    FAIL;
        }
        *p = (int)((13 << 12) + ((p - (int *)r) & 0xfff));
    }
#   ifdef AT_END
	r = (sexpr)((char *)r + (my_extra & ~7));
#   endif
    r -> sexpr_car = x;
    r -> sexpr_cdr = y;
    my_extra++;
    if ( my_extra >= 5000 ) {
        extra_count = 0;
    } else {
        extra_count = my_extra;
    }
    GC_END_STUBBORN_CHANGE((char *)r);
    return(r);
}
# endif

#ifdef GC_GCJ_SUPPORT

#include "gc_mark.h"
#include "gc_gcj.h"

/* The following struct emulates the vtable in gcj.	*/
/* This assumes the default value of MARK_DESCR_OFFSET. */
struct fake_vtable {
  void * dummy;		/* class pointer in real gcj.	*/
  size_t descr;
};

struct fake_vtable gcj_class_struct1 = { 0, sizeof(struct SEXPR)
					    + sizeof(struct fake_vtable *) };
			/* length based descriptor.	*/
struct fake_vtable gcj_class_struct2 =
				{ 0, (3l << (CPP_WORDSZ - 3)) | GC_DS_BITMAP};
			/* Bitmap based descriptor.	*/

struct GC_ms_entry * fake_gcj_mark_proc(word * addr,
				        struct GC_ms_entry *mark_stack_ptr,
				        struct GC_ms_entry *mark_stack_limit,
				        word env   )
{
    sexpr x;
    if (1 == env) {
	/* Object allocated with debug allocator.	*/
	addr = (word *)GC_USR_PTR_FROM_BASE(addr);
    }
    x = (sexpr)(addr + 1); /* Skip the vtable pointer. */
    mark_stack_ptr = GC_MARK_AND_PUSH(
			      (void *)(x -> sexpr_cdr), mark_stack_ptr,
			      mark_stack_limit, (void * *)&(x -> sexpr_cdr));
    mark_stack_ptr = GC_MARK_AND_PUSH(
			      (void *)(x -> sexpr_car), mark_stack_ptr,
			      mark_stack_limit, (void * *)&(x -> sexpr_car));
    return(mark_stack_ptr);
}

#endif /* GC_GCJ_SUPPORT */


sexpr small_cons (sexpr x, sexpr y)
{
    sexpr r;
    
    collectable_count++;
    r = (sexpr) GC_MALLOC(sizeof(struct SEXPR));
    if (r == 0) {
        (void)GC_printf("Out of memory\n");
        exit(1);
    }
    r -> sexpr_car = x;
    r -> sexpr_cdr = y;
    return(r);
}

sexpr small_cons_uncollectable (sexpr x, sexpr y)
{
    sexpr r;
    
    uncollectable_count++;
    r = (sexpr) GC_MALLOC_UNCOLLECTABLE(sizeof(struct SEXPR));
    if (r == 0) {
        (void)GC_printf("Out of memory\n");
        exit(1);
    }
    r -> sexpr_car = x;
    r -> sexpr_cdr = (sexpr)(~(GC_word)y);
    return(r);
}

#ifdef GC_GCJ_SUPPORT


sexpr gcj_cons(sexpr x, sexpr y)
{
    GC_word * r;
    sexpr result;
    static int count = 0;
    
    r = (GC_word *) GC_GCJ_MALLOC(sizeof(struct SEXPR)
		   		  + sizeof(struct fake_vtable*),
				   &gcj_class_struct2);
    if (r == 0) {
        (void)GC_printf("Out of memory\n");
        exit(1);
    }
    result = (sexpr)(r + 1);
    result -> sexpr_car = x;
    result -> sexpr_cdr = y;
    return(result);
}
#endif

/* Return reverse(x) concatenated with y */
sexpr reverse1(sexpr x, sexpr y)
{
    if (is_nil(x)) {
        return(y);
    } else {
        return( reverse1(cdr(x), cons(car(x), y)) );
    }
}

sexpr reverse(sexpr x)
{
#   ifdef TEST_WITH_SYSTEM_MALLOC
      malloc(100000);
#   endif
    return( reverse1(x, nil) );
}

sexpr ints(int low, int up)
{
    if (low > up) {
	return(nil);
    } else {
        return(small_cons(small_cons(INT_TO_SEXPR(low), nil), ints(low+1, up)));
    }
}

#ifdef GC_GCJ_SUPPORT
/* Return reverse(x) concatenated with y */
sexpr gcj_reverse1(sexpr x, sexpr y)
{
    if (is_nil(x)) {
        return(y);
    } else {
        return( gcj_reverse1(cdr(x), gcj_cons(car(x), y)) );
    }
}

sexpr gcj_reverse(sexpr x)
{
    return( gcj_reverse1(x, nil) );
}

sexpr gcj_ints(int low, int up)
{
    if (low > up) {
	return(nil);
    } else {
        return(gcj_cons(gcj_cons(INT_TO_SEXPR(low), nil), gcj_ints(low+1, up)));
    }
}
#endif /* GC_GCJ_SUPPORT */

/* To check uncollectable allocation we build lists with disguised cdr	*/
/* pointers, and make sure they don't go away.				*/
sexpr uncollectable_ints(int low, int up)
{
    if (low > up) {
	return(nil);
    } else {
        return(small_cons_uncollectable(small_cons(INT_TO_SEXPR(low), nil),
               uncollectable_ints(low+1, up)));
    }
}

void check_ints(sexpr list, int low, int up)
{
    if (SEXPR_TO_INT(car(car(list))) != low) {
        (void)GC_printf(
           "List reversal produced incorrect list - collector is broken\n");
        FAIL;
    }
    if (low == up) {
        if (cdr(list) != nil) {
           (void)GC_printf("List too long - collector is broken\n");
           FAIL;
        }
    } else {
        check_ints(cdr(list), low+1, up);
    }
}

# define UNCOLLECTABLE_CDR(x) (sexpr)(~(GC_word)(cdr(x)))

void check_uncollectable_ints(sexpr list, int low, int up)
{
    if (SEXPR_TO_INT(car(car(list))) != low) {
        (void)GC_printf(
           "Uncollectable list corrupted - collector is broken\n");
        FAIL;
    }
    if (low == up) {
        if (UNCOLLECTABLE_CDR(list) != nil) {
           (void)GC_printf("Uncollectable list too long - collector is broken\n");
           FAIL;
        }
    } else {
        check_uncollectable_ints(UNCOLLECTABLE_CDR(list), low+1, up);
    }
}

/* Not used, but useful for debugging: */
void print_int_list(sexpr x)
{
    if (is_nil(x)) {
        (void)GC_printf("NIL\n");
    } else {
        (void)GC_printf("(%d)", SEXPR_TO_INT(car(car(x))));
        if (!is_nil(cdr(x))) {
            (void)GC_printf(", ");
            (void)print_int_list(cdr(x));
        } else {
            (void)GC_printf("\n");
        }
    }
}

/* ditto: */
void check_marks_int_list(sexpr x)
{
    if (!GC_is_marked((ptr_t)x))
	GC_printf("[unm:%p]", x);
    else
	GC_printf("[mkd:%p]", x);
    if (is_nil(x)) {
        (void)GC_printf("NIL\n");
    } else {
        if (!GC_is_marked((ptr_t)car(x))) GC_printf("[unm car:%p]", car(x));
        (void)GC_printf("(%d)", SEXPR_TO_INT(car(car(x))));
        if (!is_nil(cdr(x))) {
            (void)GC_printf(", ");
            (void)check_marks_int_list(cdr(x));
        } else {
            (void)GC_printf("\n");
        }
    }
}

/*
 * A tiny list reversal test to check thread creation.
 */
#ifdef THREADS

# if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
    DWORD  __stdcall tiny_reverse_test(void * arg)
# else
    void * tiny_reverse_test(void * arg)
# endif
{
    int i;
    for (i = 0; i < 5; ++i) {
      check_ints(reverse(reverse(ints(1,10))), 1, 10);
    }
    return 0;
}

# if defined(GC_PTHREADS)
    void fork_a_thread()
    {
      pthread_t t;
      int code;
      if ((code = pthread_create(&t, 0, tiny_reverse_test, 0)) != 0) {
    	(void)GC_printf("Small thread creation failed %d\n", code);
    	FAIL;
      }
      if ((code = pthread_join(t, 0)) != 0) {
        (void)GC_printf("Small thread join failed %d\n", code);
        FAIL;
      }
    }

# elif defined(GC_WIN32_THREADS)
    void fork_a_thread()
    {
  	DWORD thread_id;
	HANDLE h;
    	h = GC_CreateThread(NULL, 0, tiny_reverse_test, 0, 0, &thread_id);
        if (h == (HANDLE)NULL) {
            (void)GC_printf("Small thread creation failed %d\n",
			    GetLastError());
      	    FAIL;
        }
    	if (WaitForSingleObject(h, INFINITE) != WAIT_OBJECT_0) {
      	    (void)GC_printf("Small thread wait failed %d\n",
			    GetLastError());
      	    FAIL;
    	}
    }

# else

#   define fork_a_thread()

# endif

#else

# define fork_a_thread()

#endif 

/* 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.
 */
void reverse_test()
{
    int i;
    sexpr b;
    sexpr c;
    sexpr d;
    sexpr e;
    sexpr *f, *g, *h;
#   if defined(MSWIN32) || defined(MACOS)
      /* Win32S only allows 128K stacks */
#     define BIG 1000
#   else
#     if defined PCR
	/* PCR default stack is 100K.  Stack frames are up to 120 bytes. */
#	define BIG 700
#     else
#	if defined MSWINCE
	  /* WinCE only allows 64K stacks */
#	  define BIG 500
#	else
#	  if defined(OSF1)
	    /* OSF has limited stack space by default, and large frames. */
#           define BIG 200
#	  else
#           define BIG 4500
#	  endif
#	endif
#     endif
#   endif

    A.dummy = 17;
    a = ints(1, 49);
    b = ints(1, 50);
    c = ints(1, BIG);
    d = uncollectable_ints(1, 100);
    e = uncollectable_ints(1, 1);
    /* Check that realloc updates object descriptors correctly */
    collectable_count++;
    f = (sexpr *)GC_MALLOC(4 * sizeof(sexpr));
    realloc_count++;
    f = (sexpr *)GC_REALLOC((void *)f, 6 * sizeof(sexpr));
    f[5] = ints(1,17);
    collectable_count++;
    g = (sexpr *)GC_MALLOC(513 * sizeof(sexpr));
    realloc_count++;
    g = (sexpr *)GC_REALLOC((void *)g, 800 * sizeof(sexpr));