prmsgc.c

Netscape NSPR库源码

      return;
    }

    /*
    ** Put a pointer onto the scan Q. We use the scan Q to avoid
    ** deep recursion on the C call stack. Objects are added to
    ** the scan Q until the scan Q fills up. At that point we
    ** make a call to ScanScanQ which proceeds to scan each of
    ** the objects in the Q. This limits the recursion level by a
    ** large amount though the stack frames get larger to hold
    ** the GCScanQ's.
    */
    pScanQ->q[pScanQ->queued++] = p;
    if (pScanQ->queued == MAX_SCAN_Q) {
      METER(_pr_scanDepth++);
      ScanScanQ(pScanQ);
    }
  }
}

/************************************************************************/

/*
** Empty the freelist for each segment. This is done to make sure that
** the root finding step works properly (otherwise, if we had a pointer
** into a free section, we might not find its header word and abort in
** FindObject)
*/
static void EmptyFreelists(void)
{
    GCFreeChunk *cp;
    GCFreeChunk *next;
    GCSeg *sp;
    PRWord *p;
    PRInt32 chunkSize;
    PRInt32 bin;

    /*
    ** Run over the freelist and make all of the free chunks look like
    ** object debris.
    */
    for (bin = 0; bin <= NUM_BINS-1; bin++) {
        cp = bins[bin];
        while (cp) {
            next = cp->next;
            sp = cp->segment;
            chunkSize = cp->chunkSize >> BYTES_PER_WORD_LOG2;
            p = (PRWord*) cp;
            PR_ASSERT(chunkSize != 0);
            p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
            SET_HBIT(sp, p);
            cp = next;
        }
        bins[bin] = 0;
    }
    minBin = NUM_BINS - 1;
    maxBin = 0;
}

typedef struct GCBlockEnd {
    PRInt32	check;
#ifdef GC_CHECK
    PRInt32	requestedBytes;
#endif
#ifdef GC_STATS
    PRInt32	bin;
    PRInt64	allocTime; 
#endif
#ifdef GC_TRACEROOTS
    PRInt32	traceGeneration;	
#endif
} GCBlockEnd;

#define PR_BLOCK_END	0xDEADBEEF

/************************************************************************/

#ifdef GC_STATS

typedef struct GCStat {
    PRInt32	nallocs;
    double	allocTime;
    double	allocTimeVariance;
    PRInt32	nfrees;
    double	lifetime;
    double	lifetimeVariance;
} GCStat;

#define GCSTAT_BINS	NUM_BINS

GCStat gcstats[GCSTAT_BINS];

#define GCLTFREQ_BINS	NUM_BINS

PRInt32 gcltfreq[GCSTAT_BINS][GCLTFREQ_BINS];

#include <math.h>

static char* 
pr_GetSizeString(PRUint32 size)
{
    char* sizeStr;
    if (size < 1024)
	sizeStr = PR_smprintf("<= %ld", size);
    else if (size < 1024 * 1024)
	sizeStr = PR_smprintf("<= %ldk", size / 1024);
    else 
	sizeStr = PR_smprintf("<= %ldM", size / (1024 * 1024));
    return sizeStr;
}

static void
pr_FreeSizeString(char *sizestr)
{
	PR_smprintf_free(sizestr);
}


static void
pr_PrintGCAllocStats(FILE* out)
{
    PRInt32 i, j;
    _PR_DebugPrint(out, "\n--Allocation-Stats-----------------------------------------------------------");
    _PR_DebugPrint(out, "\n--Obj-Size----Count-----Avg-Alloc-Time-----------Avg-Lifetime---------%%Freed-\n");
    for (i = 0; i < GCSTAT_BINS; i++) {
	GCStat stat = gcstats[i];
	double allocTimeMean = 0.0, allocTimeVariance = 0.0, lifetimeMean = 0.0, lifetimeVariance = 0.0;
	PRUint32 maxSize = (1 << i);
	char* sizeStr;
	if (stat.nallocs != 0.0) {
	    allocTimeMean = stat.allocTime / stat.nallocs;
	    allocTimeVariance = fabs(stat.allocTimeVariance / stat.nallocs - allocTimeMean * allocTimeMean);
	}
	if (stat.nfrees != 0.0) {
	    lifetimeMean = stat.lifetime / stat.nfrees;
	    lifetimeVariance = fabs(stat.lifetimeVariance / stat.nfrees - lifetimeMean * lifetimeMean);
	}
	sizeStr = pr_GetSizeString(maxSize);
	_PR_DebugPrint(out, "%10s %8lu %10.3f +- %10.3f %10.3f +- %10.3f (%2ld%%)\n",
		       sizeStr, stat.nallocs,
		       allocTimeMean, sqrt(allocTimeVariance),
		       lifetimeMean, sqrt(lifetimeVariance),
		       (stat.nallocs ? (stat.nfrees * 100 / stat.nallocs) : 0));
	pr_FreeSizeString(sizeStr);
    }
    _PR_DebugPrint(out, "--Lifetime-Frequency-Counts----------------------------------------------------\n");
    _PR_DebugPrint(out, "size\\cnt");
    for (j = 0; j < GCLTFREQ_BINS; j++) {
	_PR_DebugPrint(out, "\t%lu", j);
    }
    _PR_DebugPrint(out, "\n");
    for (i = 0; i < GCSTAT_BINS; i++) {
	PRInt32* freqs = gcltfreq[i];
	_PR_DebugPrint(out, "%lu", (1 << i));
	for (j = 0; j < GCLTFREQ_BINS; j++) {
	    _PR_DebugPrint(out, "\t%lu", freqs[j]);
	}
	_PR_DebugPrint(out, "\n");
    }
    _PR_DebugPrint(out, "-------------------------------------------------------------------------------\n");
}

PR_PUBLIC_API(void)
PR_PrintGCAllocStats(void)
{
    pr_PrintGCAllocStats(stderr);
}

#endif /* GC_STATS */

/************************************************************************/

/*
** Sweep a segment, cleaning up all of the debris. Coallese the debris
** into GCFreeChunk's which are added to the freelist bins.
*/
static PRBool SweepSegment(GCSeg *sp)
{
    PRWord h, tix;
    PRWord *p;
    PRWord *np;
    PRWord *limit;
    GCFreeChunk *cp;
    PRInt32 bytes, chunkSize, segmentSize, totalFree;
    CollectorType *ct;
    PRInt32 bin;

    /*
    ** Now scan over the segment's memory in memory order, coallescing
    ** all of the debris into a FreeChunk list.
    */
    totalFree = 0;
    segmentSize = sp->limit - sp->base;
    p = (PRWord *) sp->base;
    limit = (PRWord *) sp->limit;
    PR_ASSERT(segmentSize > 0);
    while (p < limit) {
    chunkSize = 0;
    cp = (GCFreeChunk *) p;

    /* Attempt to coallesce any neighboring free objects */
    for (;;) {
        PR_ASSERT(IS_HBIT(sp, p) != 0);
        h = p[0];
        bytes = OBJ_BYTES(h);
        PR_ASSERT(bytes != 0);
        np = (PRWord *) ((char *)p + bytes);
        tix = (PRWord)GET_TYPEIX(h);
        if ((h & MARK_BIT) && (tix != FREE_MEMORY_TYPEIX)) {
#ifdef DEBUG
        if (tix != FREE_MEMORY_TYPEIX) {
            PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
        }
#endif
        p[0] = h & ~(MARK_BIT|FINAL_BIT);
		_GCTRACE(GC_SWEEP, ("busy 0x%x (%d)", p, bytes));
		break;
	    }
	    _GCTRACE(GC_SWEEP, ("free 0x%x (%d)", p, bytes));

	    /* Found a free object */
#ifdef GC_STATS
	    {
		PRInt32 userSize = bytes - sizeof(GCBlockEnd);
		GCBlockEnd* end = (GCBlockEnd*)((char*)p + userSize);
		if (userSize >= 0 && end->check == PR_BLOCK_END) {
		    PRInt64 now = PR_Now();
		    double nowd, delta;
		    PRInt32 freq;
		    LL_L2D(nowd, now);
		    delta = nowd - end->allocTime;
		    gcstats[end->bin].nfrees++;
		    gcstats[end->bin].lifetime += delta;
		    gcstats[end->bin].lifetimeVariance += delta * delta;

		    InlineBinNumber(freq, delta);
		    gcltfreq[end->bin][freq]++;

		    end->check = 0;
		}
	    }
#endif
        CLEAR_HBIT(sp, p);
        ct = &_pr_collectorTypes[tix];
        if (0 != ct->gctype.free) {
                (*ct->gctype.free)(p + 1);
            }
        chunkSize = chunkSize + bytes;
        if (np == limit) {
        /* Found the end of heap */
        break;
        }
        PR_ASSERT(np < limit);
        p = np;
    }

    if (chunkSize) {
        _GCTRACE(GC_SWEEP, ("free chunk 0x%p to 0x%p (%d)",
                   cp, (char*)cp + chunkSize - 1, chunkSize));
        if (chunkSize < MIN_FREE_CHUNK_BYTES) {
        /* Lost a tiny fragment until (maybe) next time */
                METER(meter.wastedBytes += chunkSize);
        p = (PRWord *) cp;
        chunkSize >>= BYTES_PER_WORD_LOG2;
        PR_ASSERT(chunkSize != 0);
        p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
        SET_HBIT(sp, p);
        } else {
                /* See if the chunk constitutes the entire segment */
                if (chunkSize == segmentSize) {
                    /* Free up the segment right now */
            if (sp->info->fromMalloc) {
                    ShrinkGCHeap(sp);
                    return PR_TRUE;
                }
                }

                /* Put free chunk into the appropriate bin */
                cp->segment = sp;
        cp->chunkSize = chunkSize;
                InlineBinNumber(bin, chunkSize)
                cp->next = bins[bin];
                bins[bin] = cp;
        if (bin < minBin) minBin = bin;
        if (bin > maxBin) maxBin = bin;

        /* Zero swept memory now */
        memset(cp+1, 0, chunkSize - sizeof(*cp));
                METER(meter.numFreeChunks++);
        totalFree += chunkSize;
        }
    }

    /* Advance to next object */
    p = np;
    }

    PR_ASSERT(totalFree <= segmentSize);

    _pr_gcData.freeMemory += totalFree;
    _pr_gcData.busyMemory += (sp->limit - sp->base) - totalFree;
    return PR_FALSE;
}

/************************************************************************/

/* This is a list of all the objects that are finalizable. This is not
   the list of objects that are awaiting finalization because they
   have been collected. */
PRCList _pr_finalizeableObjects;

/* This is the list of objects that are awaiting finalization because
   they have been collected. */
PRCList _pr_finalQueue;

/* Each object that requires finalization has one of these objects
   allocated as well. The GCFinal objects are put on the
   _pr_finalizeableObjects list until the object is collected at which
   point the GCFinal object is moved to the _pr_finalQueue */
typedef struct GCFinalStr {
    PRCList links;
    PRWord *object;
} GCFinal;

/* Find pointer to GCFinal struct from the list linkaged embedded in it */
#define FinalPtr(_qp) \
    ((GCFinal*) ((char*) (_qp) - offsetof(GCFinal,links)))

static GCFinal *AllocFinalNode(void)
{
    return PR_NEWZAP(GCFinal);
}

static void FreeFinalNode(GCFinal *node)
{
    PR_DELETE(node);
}

/*
** Prepare for finalization. At this point in the GC cycle we have
** identified all of the live objects. For each object on the
** _pr_finalizeableObjects list see if the object is alive or dead. If
** it's dead, resurrect it and move it from the _pr_finalizeableObjects
** list to the _pr_finalQueue (object's only get finalized once).
**
** Once _pr_finalizeableObjects has been processed we can finish the
** GC and free up memory and release the threading lock. After that we
** can invoke the finalization procs for each object that is on the
** _pr_finalQueue.
*/
static void PrepareFinalize(void)
{
    PRCList *qp;
    GCFinal *fp;
    PRWord h;
    PRWord *p;
    void (PR_CALLBACK *livePointer)(void *ptr);
#ifdef DEBUG
    CollectorType *ct;
#endif

    /* This must be done under the same lock that the finalizer uses */
    PR_ASSERT( GC_IS_LOCKED() );

    /* cache this ptr */
    livePointer = _pr_gcData.livePointer;

    /*
     * Pass #1: Identify objects that are to be finalized, set their
     * FINAL_BIT.
     */
    qp = _pr_finalizeableObjects.next;
    while (qp != &_pr_finalizeableObjects) {
    fp = FinalPtr(qp);
    qp = qp->next;
    h = fp->object[0];        /* Grab header word */
    if (h & MARK_BIT) {
        /* Object is already alive */
        continue;
    }

#ifdef DEBUG
    ct = &_pr_collectorTypes[GET_TYPEIX(h)];
    PR_ASSERT((0 != ct->flags) && (0 != ct->gctype.finalize));
#endif
    fp->object[0] |= FINAL_BIT;
    _GCTRACE(GC_FINAL, ("moving %p (%d) to finalQueue",
               fp->object, OBJ_BYTES(h)));
    }

    /*
     * Pass #2: For each object that is going to be finalized, move it to
     * the finalization queue and resurrect it
     */
    qp = _pr_finalizeableObjects.next;
    while (qp != &_pr_finalizeableObjects) {
    fp = FinalPtr(qp);
    qp = qp->next;
    h = fp->object[0];        /* Grab header word */
    if ((h & FINAL_BIT) == 0) {
        continue;
    }

    /* Resurrect the object and any objects it refers to */
        p = &fp->object[1];
    (*livePointer)(p);
    PR_REMOVE_LINK(&fp->links);
    PR_APPEND_LINK(&fp->links, &_pr_finalQueue);
    }
}

/*
** Scan the finalQ, marking each and every object on it live.  This is
** necessary because we might do a GC before objects that are on the
** final queue get finalized. Since there are no other references
** (otherwise they would be on the final queue), we have to scan them.
** This really only does work if we call the GC before the finalizer
** has a chance to do its job.
*/
extern void PR_CALLBACK _PR_ScanFinalQueue(void *notused)
{
#ifdef XP_MAC
#pragma unused (notused)
#endif
    PRCList *qp;
    GCFinal *fp;
    PRWord *p;
    void ( PR_CALLBACK *livePointer)(void *ptr);

    livePointer = _pr_gcData.livePointer;
    qp = _pr_finalQueue.next;
    while (qp != &_pr_finalQueue) {
    fp = FinalPtr(qp);
	_GCTRACE(GC_FINAL, ("marking 0x%x (on final queue)", fp->object));
        p = &fp->object[1];
    (*livePointer)(p);
    qp = qp->next;
    }
}

void PR_CALLBACK FinalizerLoop(void* unused)
{
#ifdef XP_MAC
#pragma unused (unused)
#endif
    GCFinal *fp;
    PRWord *p;
    PRWord h, tix;
    CollectorType *ct;

    LOCK_GC();
    for (;;) {
	p = 0; h = 0;		/* don't let the gc find these pointers */
    while (PR_CLIST_IS_EMPTY(&_pr_finalQueue))
        PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);

    _GCTRACE(GC_FINAL, ("begin finalization"));
    while (_pr_finalQueue.next != &_pr_finalQueue) {
        fp = FinalPtr(_pr_finalQueue.next);
        PR_REMOVE_LINK(&fp->links);
        p = fp->object;

        h = p[0];        /* Grab header word */
        tix = (PRWord)GET_TYPEIX(h);
        ct = &_pr_collectorTypes[tix];
	    _GCTRACE(GC_FINAL, ("finalize 0x%x (%d)", p, OBJ_BYTES(h)));

        /*
        ** Give up the GC lock so that other threads can allocate memory
        ** while this finalization method is running. Get it back
        ** afterwards so that the list remains thread safe.
        */
        UNLOCK_GC();
        FreeFinalNode(fp);
        PR_ASSERT(ct->gctype.finalize != 0);
        (*ct->gctype.finalize)(p + 1);
        LOCK_GC();
    }
    _GCTRACE(GC_FINAL, ("end finalization"));
    PR_Notify(_pr_gcData.lock);
    }