runtime.h

内存垃圾收集程序

#define HBLKSIZE   0x1000


/*  max size objects supported by freelist (larger objects may be   */
/*  allocated, but less efficiently)                                */
/*      asm(".set MAXOBJSZ,0x200")      if HBLKSIZE/2 == 0x200          */

#define MAXOBJSZ    (HBLKSIZE/8)
		/* Should be BYTES_TO_WORDS(HBLKSIZE/2), but a cpp */
		/* misfeature prevents that.                       */
#define MAXAOBJSZ   (HBLKSIZE/8)

# define divHBLKSZ(n) ((n) >> 12)
 
# define modHBLKSZ(n) ((n) & 0xfff)
 
# define HBLKPTR(objptr) ((struct hblk *)(((long) (objptr)) & ~0xfff))



/********************************************/
/*                                          */
/*    H e a p   B l o c k s                 */
/*                                          */
/********************************************/

/*  heap block header */
#define HBLKMASK   (HBLKSIZE-1)

#define BITS_PER_HBLK (HBLKSIZE * 8)

#define MARK_BITS_PER_HBLK (BITS_PER_HBLK/WORDSZ)
	   /* upper bound                                    */
	   /* We allocate 1 bit/word.  Only the first word   */
	   /* in each object is actually marked.             */

# define MARK_BITS_SZ ((MARK_BITS_PER_HBLK + WORDSZ - 1)/WORDSZ)
	   /* Upper bound on number of mark words per heap block  */

struct hblkhdr {
    long hbh_sz;    /* sz > 0 ==> objects are sz-tuples of poss. pointers */
		    /* sz < 0 ==> objects are sz-tuples not pointers      */
		    /* if free, the size in bytes of the whole block      */
		    /* Misc.c knows that hbh_sz comes first.              */
# ifndef HBLK_MAP
    struct hblk ** hbh_index;   /* Pointer to heap block list entry   */
				/* for this block                     */
# endif
    struct hblk * hbh_next; /* Link field for hblk free list */
    long hbh_mask;      /* If hbh_mask >= 0 then:                          */
			/*   x % (4 * hbh_sz) == x & hbh_mask              */
			/*   sz is a power of 2 and < the size of a heap   */
			/*     block.                                      */
			/* A hack to speed up pointer validity check on    */
			/* machines with slow division.                    */
    long hbh_marks[MARK_BITS_SZ];
			    /* Bits 2i and 2i+1 in the array refer to the   */
			    /* object starting at the ith word (header      */
			    /* INCLUDED) in the heap block.                 */
			    /* For free blocks, hbh_marks[0] = 1, indicates */
			    /* block is uninitialized.                      */
};

/*  heap block body */

# define BODY_SZ ((HBLKSIZE-sizeof(struct hblkhdr))/sizeof(word))

struct hblk {
    struct hblkhdr hb_hdr;
    word hb_body[BODY_SZ];
};

# define hb_sz hb_hdr.hbh_sz
# ifndef HBLK_MAP
#   define hb_index hb_hdr.hbh_index
# endif
# define hb_marks hb_hdr.hbh_marks
# define hb_next hb_hdr.hbh_next
# define hb_uninit hb_hdr.hbh_marks[0]
# define hb_mask hb_hdr.hbh_mask

/*  lists of all heap blocks and free lists  */
/* Object declaration is in alloc.c          */
/* These are grouped together in a struct    */
/* so that they can be easily skipped by the */
/* mark routine.                             */
/* misc.c knows about their relative order.  */

struct __gc_arrays {
  struct obj * _aobjfreelist[MAXAOBJSZ+1];         /* free list for atomic objs*/
  struct obj * _objfreelist[MAXOBJSZ+1];           /* free list for objects */
# ifdef HBLK_MAP
    char _hblkmap[MAP_SIZE];
#   define HBLK_INVALID 0    /* Not administered by collector   */
#   define HBLK_VALID 0x7f   /* Beginning of a valid heap block */
    /* A value n, 0 < n < 0x7f denotes the continuation of a valid heap    */
    /* block which starts at the current address - n * HBLKSIZE or earlier */
# else
    struct hblk * _hblklist[MAXHBLKS];
# endif
};

extern struct __gc_arrays _gc_arrays; 

# define objfreelist _gc_arrays._objfreelist
# define aobjfreelist _gc_arrays._aobjfreelist
# ifdef HBLK_MAP
#   define hblkmap _gc_arrays._hblkmap
# else
#   define hblklist _gc_arrays._hblklist
# endif

# define begin_gc_arrays ((char *)(&_gc_arrays))
# define end_gc_arrays (((char *)(&_gc_arrays)) + (sizeof _gc_arrays))

struct hblk ** last_hblk;  /* Pointer to one past the real end of hblklist */

struct hblk * hblkfreelist;

extern long heapsize;       /* Heap size in bytes */

# define HINCR 16          /* Initial heap increment, in blocks              */
long hincr;                /* current heap increment, in blocks              */

/* Operations */
# define update_hincr  hincr = (hincr * HINCR_MULT)/HINCR_DIV
# define HB_SIZE(p) abs((p) -> hb_sz)
# define abs(x)  ((x) < 0? (-(x)) : (x))

/*  procedures */

extern void
freehblk();

extern struct hblk *
allochblk();

/****************************/
/*                          */
/*   Objects                */
/*                          */
/****************************/

/*  object structure */

struct obj {
    union {
	struct obj *oun_link;   /* --> next object in freelist */
#         define obj_link       obj_un.oun_link
	word oun_component[1];  /* treats obj as list of words */
#         define obj_component  obj_un.oun_component
    } obj_un;
};

/*  Test whether something points to a legitimate heap object */


extern char end;

# ifdef HBLK_MAP
  char * heapstart; /* A lower bound on all heap addresses */
		    /* Known to be HBLKSIZE aligned.       */
# endif

char * heaplim;   /* 1 + last address in heap */

char * startup_sfp; /* Frame pointer for Russell startup routine */

/* Check whether the given HBLKSIZE aligned hblk pointer refers to the   */
/* beginning of a legitimate chunk.                                      */
/* Assumes that *p is addressable                                        */
# ifdef HBLK_MAP
#   define is_hblk(p)  (hblkmap[divHBLKSZ(((long)p) - ((long)heapstart))] \
			== HBLK_VALID)
# else
#   define is_hblk(p) ( (p) -> hb_index >= hblklist \
			&& (p) -> hb_index < last_hblk \
			&& *((p)->hb_index) == (p))
# endif
# ifdef INTERIOR_POINTERS
    /* Return the hblk_map entry for the pointer p */
#     define get_map(p)  (hblkmap[divHBLKSZ(((long)p) - ((long)heapstart))])
# endif

# ifdef INTERIOR_POINTERS
  /* Return the word displacement of the beginning of the object to       */
  /* which q points.  q is an address inside hblk p for objects of size s */
  /* with mask m corresponding to s.                                      */
#  define get_word_no(q,p,s,m) \
	    (((long)(m)) >= 0 ? \
		(((((long)q) - ((long)p) - (sizeof (struct hblkhdr))) & ~(m)) \
		 + (sizeof (struct hblkhdr)) >> 2) \
		: ((((long)q) - ((long)p) - (sizeof (struct hblkhdr)) >> 2) \
		   / (s)) * (s) \
		   + ((sizeof (struct hblkhdr)) >> 2))
# else
  /* Check whether q points to an object inside hblk p for objects of size s */
  /* with mask m corresponding to s.                                         */
#  define is_proper_obj(q,p,s,m) \
	    (((long)(m)) >= 0 ? \
		(((((long)(q)) - (sizeof (struct hblkhdr))) & (m)) == 0) \
		: (((long) (q)) - ((long)(p)) - (sizeof (struct hblkhdr))) \
		   % ((s) << 2) == 0)
#  endif

/* The following is a quick test whether something is an object pointer */
/* It may err in the direction of identifying bogus pointers            */
/* Assumes heap + text + data + bss < 64 Meg.                           */
#ifdef M68K
#   define TMP_POINTER_MASK 0xfc000003  /* pointer & POINTER_MASK should be 0 */
#else
# ifdef RT
#   define TMP_POINTER_MASK 0xc0000003
# else
#   ifdef VAX
#     define TMP_POINTER_MASK 0xfc000003
#   else
#     ifdef SPARC
#       define TMP_POINTER_MASK 0xfc000003
#     else
#       ifdef I386
#         define TMP_POINTER_MASK 0xfc000003
#       else
#         ifdef NS32K
#           define TMP_POINTER_MASK 0xfc000003
#         else
#           ifdef MIPS
#             define TMP_POINTER_MASK 0xc0000003
#           else
	      --> dont know <--
#           endif
#         endif
#       endif
#     endif
#   endif
# endif
#endif

#ifdef INTERIOR_POINTERS
#   define POINTER_MASK (TMP_POINTER_MASK & 0xfffffff8)
	/* Don't pay attention to whether address is properly aligned */
#else
#   define POINTER_MASK TMP_POINTER_MASK
#endif

#ifdef HBLK_MAP
#  define quicktest(p) (((long)(p)) > ((long)(heapstart)) \
			&& !(((unsigned long)(p)) & POINTER_MASK))
#else
# ifdef UNALIGNED
#  define quicktest(p) (((long)(p)) > ((long)(&end)) \
                        && !(((unsigned long)(p)) & POINTER_MASK) \
                        && (((long)(p)) & HBLKMASK))
	/* The last test throws out pointers to the beginning of heap */
        /* blocks.  Small integers shifted by 16 bits tend to look    */
        /* like these.                                                */
# else
#  define quicktest(p) (((long)(p)) > ((long)(&end)) \
			&& !(((unsigned long)(p)) & POINTER_MASK))
# endif
#endif


/*  Marks are in a reserved area in                          */
/*  each heap block.  Each word has one mark bits associated */
/*  with it. Only those corresponding to the beginning of an */
/*  object are used.                                         */


/* Operations */

/*
 * Retrieve, set, clear the mark bit corresponding
 * to the nth word in a given heap block.
 * Note that retrieval will work, so long as *hblk is addressable.
 * In particular, the check whether hblk is a legitimate heap block
 * can be postponed until after the mark bit is examined.
 *
 * (Recall that bit n corresponds to object beginning at word n)
 */

# define mark_bit(hblk,n) (((hblk)->hb_marks[divWORDSZ(n)] \
			    >> (modWORDSZ(n))) & 1)

/* The following assume the mark bit in question is either initially */
/* cleared or it already has its final value                         */
# define set_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] \
				|= 1 << modWORDSZ(n)

# define clear_mark_bit(hblk,n) (hblk)->hb_marks[divWORDSZ(n)] \
				&= ~(1 << modWORDSZ(n))

/*  procedures */

/* Small object allocation routines */
extern struct obj * allocobj();
extern struct obj * allocaobj();

/* general purpose allocation routines */
extern struct obj * gc_malloc();

extern struct obj * gc_malloc_comp();