alloc.c

内存垃圾收集程序

/*
 * This file contains the functions:
 *	void new_hblk(n)
 *	static void clear_marks()
 *	tl_mark(p)
 *	mark()
 *	mark_all(b,t)
 *	void gcollect()
 *	expand_hp: func[val Short] val Void
 *	struct obj * _allocobj(sz)
 *	struct obj * _allocaobj(sz)
 *
 * And the global variables:
 *	struct obj * objfreelist[MAXOBJSZ+1];
 *	struct obj * aobjfreelist[MAXOBJSZ+1];
 *	word * mark_stack_bottom;
 *	word * mark_stack_top;
 */


# include <stdio.h>
# include <signal.h>
# include <sys/types.h>
# include <sys/times.h>
# include "runtime.h"

/* Leaving these defined enables output to stderr.  In order of */
/* increasing verbosity:                                        */
#define REPORT_FAILURE   /* Print values that looked "almost" like pointers */
#undef REPORT_FAILURE
#define DEBUG            /* Verbose debugging output */
#undef DEBUG
#define DEBUG2           /* EXTREMELY verbose debugging output */
#undef DEBUG2
#define USE_STACK       /* Put mark stack onto process stack.  This assumes */
			/* that it's safe to put data below the stack ptr,  */
			/* and that the system will expand the stack as     */
			/* necessary.  This is known to be true under Sun   */
			/* UNIX (tm) and Vax Berkeley UNIX.  It is also     */
			/* known to be false under some other UNIX          */
			/* implementations.                                 */
#undef USE_HEAP
#ifdef RT
#   define USE_HEAP
#   undef USE_STACK
#endif
#ifdef MIPS
#   define USE_HEAP
#   undef USE_STACK
#endif

/*
 * This is an attempt at a garbage collecting storage allocator
 * on a Motorola 68000 series or an a Vax.  The garbage
 * collector is overly conservative in that it may fail to reclaim
 * inaccessible storage.  On the other hand, it does not assume
 * any runtime tag information.
 * We make the following assumptions:
 *  1.  We are running under something that looks like Berkeley UNIX,
 *      on one of the supported architectures.
 *  2.  For every accessible object, a pointer to it is stored in
 *          a) the stack segment, or
 *          b) the data or bss segment, or
 *          c) the registers, or
 *          d) an accessible block.
 *
 */

/*
 * Separate free lists are maintained for different sized objects
 * up to MAXOBJSZ or MAXAOBJSZ.
 * The lists objfreelist[i] contain free objects of size i which may
 * contain nested pointers.  The lists aobjfreelist[i] contain free
 * atomic objects, which may not contain nested pointers.
 * The call allocobj(i) insures that objfreelist[i] points to a non-empty
 * free list it returns a pointer to the first entry on the free list.
 * Allocobj may be called from C to allocate an object of (small) size i
 * as follows:
 *
 *            opp = &(objfreelist[i]);
 *            if (*opp == (struct obj *)0) allocobj(i);
 *            ptr = *opp;
 *            *opp = ptr->next;
 *
 * Note that this is very fast if the free list is non-empty; it should
 * only involve the execution of 4 or 5 simple instructions.
 * All composite objects on freelists are cleared, except for
 * their first longword.
 */

/*
 *  The allocator uses allochblk to allocate large chunks of objects.
 * These chunks all start on addresses which are multiples of
 * HBLKSZ.  All starting addresses are maintained on a contiguous
 * list so that they can be traversed in the sweep phase of garbage collection.
 * This makes it possible to check quickly whether an
 * arbitrary address corresponds to an object administered by the
 * allocator.
 *  We make the (probably false) claim that this can be interrupted
 * by a signal with at most the loss of some chunk of memory.
 */

/* Declarations for fundamental data structures.  These are grouped */
/* in a single structure, so that the collector can skip over them. */

struct __gc_arrays _gc_arrays;

long heapsize = 0;      /* Heap size in bytes */

long non_gc_bytes = 0;  /* Number of bytes not intended to be collected */

char copyright[] = "Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers";

/* Return a rough approximation to the stack pointer.  A hack,  */
/* but it's semi-portable.                                      */
word * get_current_sp()
{
    word x;
    return(&x);
}

/*
 * Allocate a new heapblock for objects of size n.
 * Add all of the heapblock's objects to the free list for objects
 * of that size.  A negative n requests atomic objects.
 */
void new_hblk(n)
long n;
{
    register word *p,
		  *r;
    word *last_object;		/* points to last object in new hblk	*/
    register struct hblk *h;	/* the new heap block			*/
    register long abs_sz;	/* |n|	*/
    register int i;

#   ifdef PRINTSTATS
	if ((sizeof (struct hblk)) > HBLKSIZE) {
	    abort("HBLK SZ inconsistency");
        }
#   endif

  /* Allocate a new heap block */
    h = allochblk(n);

  /* Add it to hblklist */
    add_hblklist(h);

  /* Add objects to free list */
    abs_sz = abs(n);
    p = &(h -> hb_body[abs_sz]);	/* second object in *h	*/
    r = &(h -> hb_body[0]);       	/* One object behind p	*/
    last_object = ((word *)((char *)h + HBLKSIZE)) - abs_sz;
			    /* Last place for last object to start */

  /* make a list of all objects in *h with head as last object */
    while (p <= last_object) {
      /* current object's link points to last object */
	((struct obj *)p) -> obj_link = (struct obj *)r;
	r = p;
	p += abs_sz;
    }
    p -= abs_sz;			/* p now points to last object */

  /*
   * put p (which is now head of list of objects in *h) as first
   * pointer in the appropriate free list for this size.
   */
    if (n < 0) {
	((struct obj *)(h -> hb_body)) -> obj_link = aobjfreelist[abs_sz];
	aobjfreelist[abs_sz] = ((struct obj *)p);
    } else {
	((struct obj *)(h -> hb_body)) -> obj_link = objfreelist[abs_sz];
	objfreelist[abs_sz] = ((struct obj *)p);
    }

  /*
   * Set up mask in header to facilitate alignment checks
   * See "runtime.h" for a description of how this works.
   */
#   ifndef RT
	switch (abs_sz) {
	    case 1:
		h -> hb_mask = 0x3;
		break;
	    case 2:
		h -> hb_mask = 0x7;
		break;
	    case 4:
		h -> hb_mask = 0xf;
		break;
	    case 8:
		h -> hb_mask = 0x1f;
		break;
	    case 16:
		h -> hb_mask = 0x3f;
		break;
	    /* By default it remains set to a negative value */
	}
#   else
      /* the 4.2 pcc C compiler did not produce correct code for the switch */
	if (abs_sz == 1)	{ h -> hb_mask = 0x3; }
	else if (abs_sz == 2)	{ h -> hb_mask = 0x7; }
	else if (abs_sz == 4)	{ h -> hb_mask = 0xf; }
	else if (abs_sz == 8)	{ h -> hb_mask = 0x1f; }
	else if (abs_sz == 16)	{ h -> hb_mask = 0x3f; }
	/* else skip; */
#   endif

#   ifdef DEBUG
	printf("Allocated new heap block at address 0x%X\n",
		h);
#   endif
}


/* some more variables */

extern long mem_found;  /* Number of reclaimed longwords */
			/* after garbage collection      */

extern long atomic_in_use, composite_in_use;
extern errno;

/*
 * Clear mark bits in all allocated heap blocks
 */
static void clear_marks()
{
    register int j;
    register struct hblk **p;
    register struct hblk *q;

# ifdef HBLK_MAP
    for (q = (struct hblk *) heapstart; ((char*)q) < heaplim; q++)
      if (is_hblk(q)) {
# else
    for (p = hblklist; p < last_hblk; p++) {
	q = *p;
# endif
        for (j = 0; j < MARK_BITS_SZ; j++) {
	    q -> hb_marks[j] = 0;
        }
    }
}

/* Limits of stack for mark routine.  Set by caller to mark.           */
/* All items between mark_stack_top and mark_stack_bottom-1 still need */
/* to be marked.  All items on the stack satisfy quicktest.  They do   */
/* not necessarily reference real objects.                             */
word * mark_stack_bottom;
word * mark_stack_top;

#ifdef USE_STACK
# define STACKGAP 512 /* Gap in longwords between hardware stack and	*/
		      /* the mark stack.				*/
#endif


#ifdef USE_STACK
#   define PUSH_MS(ptr) *(--mark_stack_top) = (word) ptr
#   define NOT_DONE(a,b) (a < b)
#else
# ifdef USE_HEAP
    char *cur_break = 0;

#   define STACKINCR 0x4000
#   define PUSH_MS(ptr) 						\
	mark_stack_top++;                                               \
	if ((char*)mark_stack_top >= cur_break) { 			\
	    if (sbrk(STACKINCR) == -1) {				\
		fprintf(stderr, "sbrk failed, code = %d\n",errno);      \
		exit(1);						\
	    } else {							\
		cur_break += STACKINCR;                                \
	    }								\
	}								\
	*mark_stack_top = (word) ptr
#   define NOT_DONE(a,b) (a > b)
# else
	--> where does the mark stack go? <--
# endif
#endif


/* Top level mark routine */
tl_mark(p)
word * p;
{
    if (quicktest(p)) {
	/* Allocate mark stack, leaving a hole below the real stack. */
#         ifdef USE_STACK
	    mark_stack_bottom = get_current_sp() - STACKGAP;
	    mark_stack_top = mark_stack_bottom;
#         else
#           ifdef USE_HEAP
	      mark_stack_bottom = (word *) sbrk(0); /* current break */
	      cur_break = (char *) mark_stack_bottom;
	      mark_stack_top = mark_stack_bottom;
#           else
	      -> then where should the mark stack go ? <-
#           endif
#         endif
	PUSH_MS((word)p);

#       ifdef DEBUG2
	    printf("Tl_mark found plausible pointer: %X\n", p);
#       endif

	/* and now mark the one element on the stack */
	  mark();
    }
}

mark()
{
  register long sz;
  extern char end, etext;
  register struct obj *p; /* pointer to current object to be marked */

  while (NOT_DONE(mark_stack_top,mark_stack_bottom)) {
      register long word_no;
      register long mask;
      register struct hblk * h;

#    ifdef USE_STACK
	  p = (struct obj *)(*mark_stack_top++);
#    else
#     ifdef USE_HEAP
	p = (struct obj *)(*mark_stack_top--);
#     else
	--> fixit <--
#     endif
#    endif

  /* if not a pointer to obj on heap, skip it */
    if (((char *) p) >= heaplim) {
	continue;
    }

    h = HBLKPTR(p);

# ifndef INTERIOR_POINTERS
    /* Check mark bit first, since this test is much more likely to */
    /* fail than later ones.                                        */
      word_no = ((word *)p) - ((word *)h);
      if (mark_bit(h, word_no)) {
	continue;
      }
# endif

# ifdef INTERIOR_POINTERS
    if (!is_hblk(h)) {
	char m = get_map(h);
	while (m > 0 && m < 0x7f) {
	    h -= m;
	    m = get_map(h);
	}
	if (m == HBLK_INVALID) {
#         ifdef REPORT_FAILURE
	    printf("-> Pointer to non-heap loc: %X\n", p);
#         endif
	  continue;
	}
    }
    if (((long)p) - ((long)h) < sizeof (struct hblkhdr)) {
	continue;
    }
# else
    if (!is_hblk(h)) {
#	ifdef REPORT_FAILURE
	  printf("-> Pointer to non-heap loc: %X\n", p);
#       endif
	continue;
    }
# endif
    sz = HB_SIZE(h);
    mask = h -> hb_mask;

# ifdef INTERIOR_POINTERS
    word_no = get_word_no(p,h,sz,mask);
# else
    if (!is_proper_obj(p,h,sz,mask)) {
#       ifdef REPORT_FAILURE
	    printf("-> Bad pointer to heap block: %X,sz = %d\n",p,sz);
#	endif
	continue;
    }
# endif

    if (word_no + sz > BYTES_TO_WORDS(HBLKSIZE)
	&& word_no != BYTES_TO_WORDS(sizeof(struct hblkhdr))
	   /* Not first object */) {
      /* 
       * Note that we dont necessarily check for pointers to the block header.
       * This doesn't cause any problems, since we have mark
       * bits allocated for such bogus objects.
       * We have to check for references past the last object, since
       * marking from uch an "object" could cause an exception.
       */
#       ifdef REPORT_FAILURE
	    printf("-> Bad pointer to heap block: %X,sz = %d\n",p,sz);
#	endif
	continue;
    }

#   ifdef INTERIOR_POINTERS
      if (mark_bit(h, word_no)) {
	continue;
      }
#   endif

#   ifdef DEBUG2
	printf("*** set bit for heap %x, word %x\n",h,word_no);
#   endif
    set_mark_bit(h, word_no);
    if (h -> hb_sz < 0) {
	/* Atomic object */
	  continue;