alloc.c

内存垃圾收集程序

    }
    {
      /* Mark from fields inside the object */
	register struct obj ** q;
	register struct obj * r;
	register long lim;   /* Should be struct obj **, but we're out of */
			     /* A registers on a 68000.                   */

#       ifdef INTERIOR_POINTERS
	  /* Adjust p, so that it's properly aligned */
#           ifdef DEBUG
	      if (p != ((struct obj *)(((word *)h) + word_no))) {
		printf("Adjusting from %X to ", p);
		p = ((struct obj *)(((word *)h) + word_no));
		printf("%X\n", p);
	      } else {
		p = ((struct obj *)(((word *)h) + word_no));
	      }
#           else
	      p = ((struct obj *)(((word *)h) + word_no));
#           endif
#       endif
#       ifdef UNALIGNED
	  lim = ((long)(&(p -> obj_component[sz]))) - 3;
#       else
	  lim = (long)(&(p -> obj_component[sz]));
#       endif
	for (q = (struct obj **)(&(p -> obj_component[0]));
					q < (struct obj **)lim;) {
	    r = *q;
	    if (quicktest(r)) {
#               ifdef DEBUG2
		    printf("Found plausible nested pointer");
		    printf(": 0x%X inside 0x%X at 0x%X\n", r, p, q);
#               endif
		PUSH_MS(((word)r));
	    }
#           ifdef UNALIGNED
		q = ((struct obj **)(((long)q)+ALIGNMENT));
#           else
		q++;
#           endif 
	}
    }
  }
}


/*********************************************************************/
/* Mark all locations reachable via pointers located between b and t */
/*********************************************************************/
mark_all(b, t)
word * b;
word * t;
{
    register word *p;
    register word r;
    register word *lim;

#   ifdef DEBUG
	printf("Checking for pointers between 0x%X and 0x%X\n",
		b, t);
#   endif

    /* 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

  /* Round b down so it is properly aligned */
#   if (ALIGNMENT == 2)
      b = (word *)(((long) b) & ~1);
#   else
#     if (ALIGNMENT == 4 || !defined(UNALIGNED))
	b = (word *)(((long) b) & ~3);
#     endif
#   endif

  /* check all pointers in range and put on mark_stack if quicktest true */
    lim = t - 1 /* longword */;
    for (p = b; ((unsigned) p) <= ((unsigned) lim);) {
	    /* Coercion to unsigned in the preceding appears to be necessary */
	    /* due to a bug in the VAX C compiler.                           */
	r = *p;
	if (quicktest(r)) {
#           ifdef DEBUG2
		printf("Found plausible pointer: %X\n", r);
#           endif
	    PUSH_MS(r);         /* push r onto the mark stack */
	}
#       ifdef UNALIGNED
	  p = (word *)(((char *)p) + ALIGNMENT);
#       else
	  p++;
#       endif
    }
    if (mark_stack_top != mark_stack_bottom) mark();

#   ifdef USE_HEAP
      brk(mark_stack_bottom);     /* reset break to where it was before */
      cur_break = (char *) mark_stack_bottom;
#   endif
}

/*
 * Restore inaccessible objects to the free list 
 * update mem_found (number of reclaimed longwords after garbage collection)
 */
void gcollect()
{
    extern void mark_regs();
    register long TMP_SP; /* must be bound to r11 on VAX or RT, d7 on M68K */
			  /* or r3 on NS32K                                */

    extern int holdsigs();  /* disables non-urgent signals - see the	*/
			    /* file "callcc.c"				*/

    long Omask;		/* mask to restore signal mask to after
			 * critical section.  This variable is assumed
			 * to be the first variable on the stack frame
			 * and to be longword aligned.
			 */

#   ifdef PRINTTIMES
      /* some debugging values */
	double start_time;
	double mark_time;
	double done_time;
	struct tms time_buf;
#       define FTIME \
		 (((double)(time_buf.tms_utime + time_buf.tms_stime))/60.0)

      /* Get starting time */
	    times(&time_buf);
	    start_time = FTIME;
#   endif

#   ifdef DEBUG2
	printf("Here we are in gcollect\n"); 
#   endif

    /* Don't want to deal with signals in the middle so mask 'em out */
	Omask = holdsigs();

    /*
     * mark from registers - i.e., call tl_mark(i) for each
     * register i
     */
	mark_regs();

#       ifdef DEBUG
	    printf("done marking from regs - calling mark_all\n");
#	endif

      /* put stack pointer into TMP_SP               */
      /* and mark everything on the stack.           */
	/* A hack */
	TMP_SP = ((long)(&Omask));
	mark_all( TMP_SP, STACKTOP );


    /* Mark everything in data and bss segments.                             */
    /* Skip gc data structures. (It's OK to mark these, but it wastes time.) */
	{
	    extern char etext, end;

            mark_all(DATASTART, begin_gc_arrays);
            mark_all(end_gc_arrays, &end);
	}

    /* Clear free list mark bits, in case they got accidentally marked   */
    /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
    /* Also subtract memory remaining from mem_found count.              */
    /* Note that composite objects on free list are cleared.             */
    /* Thus accidentally marking a free list is not a problem;  only     */
    /* objects on the list itself will be marked, and that's fixed here. */
      {
	register int size;		/* current object size		*/
	register struct obj * p;	/* pointer to current object	*/
	register struct hblk * q;	/* pointer to block containing *p */
	register int word_no;           /* "index" of *p in *q          */
#       ifdef REPORT_FAILURE
	    int prev_failure = 0;
#       endif

	for (size = 1; size < MAXOBJSZ; size++) {
	    for (p= objfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
		q = HBLKPTR(p);
		word_no = (((word *)p) - ((word *)q));
#               ifdef REPORT_FAILURE
		  if (!prev_failure && mark_bit(q, word_no)) {
		    printf("-> Pointer to composite free list: %X,sz = %d\n",
			    p, size);
		    prev_failure = 1;
		  }
#               endif
		clear_mark_bit(q, word_no);
		mem_found -= size;
	    }
#           ifdef REPORT_FAILURE
		prev_failure = 0;
#           endif
	}
	for (size = 1; size < MAXAOBJSZ; size++) {
	    for(p= aobjfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
		q = HBLKPTR(p);
		word_no = (((long *)p) - ((long *)q));
#               ifdef REPORT_FAILURE
		  if (!prev_failure && mark_bit(q, word_no)) {
		    printf("-> Pointer to atomic free list: %X,sz = %d\n",
			    p, size);
		    prev_failure = 1;
		  }
#               endif
		clear_mark_bit(q, word_no);
		mem_found -= size;
	    }
#           ifdef REPORT_FAILURE
		prev_failure = 0;
#           endif
	}
      }

#   ifdef PRINTTIMES
      /* Get intermediate time */
	times(&time_buf);
	mark_time = FTIME;
#   endif

#   ifdef PRINTSTATS
	printf("Bytes recovered before reclaim - f.l. count = %d\n",
	       WORDS_TO_BYTES(mem_found));
#   endif

  /* Reconstruct free lists to contain everything not marked */
    reclaim();

  /* clear mark bits in all allocated heap blocks */
    clear_marks();

#   ifdef PRINTSTATS
	printf("Reclaimed %d bytes in heap of size %d bytes\n",
	       WORDS_TO_BYTES(mem_found), heapsize);
	printf("%d (atomic) + %d (composite) bytes in use\n",
	       WORDS_TO_BYTES(atomic_in_use),
	       WORDS_TO_BYTES(composite_in_use));
#   endif

  /*
   * What follows is somewhat heuristic.  Constant may benefit
   * from tuning ...
   */
    if (WORDS_TO_BYTES(mem_found) * 4 < heapsize) {
      /* Less than about 1/4 of available memory was reclaimed - get more */
	{
	    long size_to_get = HBLKSIZE + hincr * HBLKSIZE;
	    struct hblk * thishbp;
	    char * nheaplim;

	    thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
	    nheaplim = (char *) (((unsigned)thishbp) + size_to_get);
	    if( ((char *) brk(nheaplim)) == ((char *)-1) ) {
		write(2,"Out of memory, trying to continue ...\n",38);
	    } else {
		heaplim = nheaplim;
		thishbp->hb_sz = 
		    BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));
		freehblk(thishbp);
		heapsize += size_to_get;
		update_hincr;
	    }
#           ifdef PRINTSTATS
		printf("Gcollect: needed to increase heap size by %d\n",
		       size_to_get);
#           endif
	}
    }

   /* Reset mem_found for next collection */
     mem_found = 0;

  /* Reenable signals */
    sigsetmask(Omask);

  /* Get final time */
#   ifdef PRINTTIMES
	times(&time_buf);
	done_time = FTIME;
	printf("Garbage collection took %7.2f + %7.2f secs\n",
	       mark_time - start_time, done_time - mark_time);
#   endif
}

/*
 * this is a function callable from Russell to explicity make the heap
 * bigger for use by programs which know they'll need a bigger heap than
 * the default.
 */
void expand_hp(n)
int n;
{
    struct hblk * thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
    extern int holdsigs();
    int Omask;

    /* Don't want to deal with signals in the middle of this */
	Omask = holdsigs();

    heaplim = (char *) (((unsigned)thishbp) + n * HBLKSIZE);
    if (n > 2*hincr) {
	hincr = n/2;
    }
    if( ((char *) brk(heaplim)) == ((char *)-1) ) {
	write(2,"Out of Memory!\n",15);
	exit(-1);
    }
#   ifdef PRINTSTATS
	printf("Voluntarily increasing heap size by %d\n",
	       n*HBLKSIZE);
#   endif
    thishbp->hb_sz = BYTES_TO_WORDS(n * HBLKSIZE - sizeof(struct hblkhdr));
    freehblk(thishbp);
    heapsize += ((char *)heaplim) - ((char *)thishbp);
    /* Reenable signals */
	sigsetmask(Omask);
}


extern int dont_gc;  /* Unsafe to start garbage collection */

/*
 * Make sure the composite object free list for sz is not empty.
 * Return a pointer to the first object on the free list.
 * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
 *
 * note: _allocobj
 */
struct obj * _allocobj(sz)
long sz;
{
    if (sz == 0) return((struct obj *)0);

#   ifdef DEBUG2
	printf("here we are in _allocobj\n");
#   endif

    if (objfreelist[sz] == ((struct obj *)0)) {
      if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
	if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
#         ifdef DEBUG
	    printf("Calling gcollect\n");
#         endif
	  gcollect();
	} else {
	  expand_hp(NON_GC_HINCR);
	}
      }
      if (objfreelist[sz] == ((struct obj *)0)) {
#       ifdef DEBUG
	    printf("Calling new_hblk\n");
#	endif
	  new_hblk(sz);
      }
    }
#   ifdef DEBUG2
	printf("Returning %x from _allocobj\n",objfreelist[sz]);
	printf("Objfreelist[%d] = %x\n",sz,objfreelist[sz]);
#   endif
    return(objfreelist[sz]);
}

/*
 * Make sure the atomic object free list for sz is not empty.
 * Return a pointer to the first object on the free list.
 * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
 *
 * note: this is called by allocaobj (see the file allocobj.s)
 */
struct obj * _allocaobj(sz)
long sz;
{
    if (sz == 0) return((struct obj *)0);

    if (aobjfreelist[sz] == ((struct obj *) 0)) {
      if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
	if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
#         ifdef DEBUG
	    printf("Calling gcollect\n");
#         endif
	  gcollect();
	} else {
	  expand_hp(NON_GC_HINCR);
	}
      }
      if (aobjfreelist[sz] == ((struct obj *) 0)) {
	  new_hblk(-sz);
      }
    }
    return(aobjfreelist[sz]);
}

# ifdef SPARC
  put_mark_stack_bottom(val)
  long val;
  {
    mark_stack_bottom = (word *)val;
  }
# endif