Google Git
Sign in
nest-open-source / nest-learning-thermostat / 5.1.5 / nspr / b9c88dc7c668ea75ad01317836850262129c582a / . / nspr-4.8.6 / mozilla / nsprpub / lib / msgc / src / prmsgc.c
blob: 2c1e85397591c46ad90c887f77b34e54248c1343 [file] [log] [blame]
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is the Netscape Portable Runtime (NSPR).
*
* The Initial Developer of the Original Code is
* Netscape Communications Corporation.
* Portions created by the Initial Developer are Copyright (C) 1998-2000
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
*
* Alternatively, the contents of this file may be used under the terms of
* either the GNU General Public License Version 2 or later (the "GPL"), or
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
* in which case the provisions of the GPL or the LGPL are applicable instead
* of those above. If you wish to allow use of your version of this file only
* under the terms of either the GPL or the LGPL, and not to allow others to
* use your version of this file under the terms of the MPL, indicate your
* decision by deleting the provisions above and replace them with the notice
* and other provisions required by the GPL or the LGPL. If you do not delete
* the provisions above, a recipient may use your version of this file under
* the terms of any one of the MPL, the GPL or the LGPL.
*
* ***** END LICENSE BLOCK ***** */
#include <string.h>
#include <stddef.h>
#include <stdarg.h>
#include <time.h>
#ifdef WIN32
#include <windef.h>
#include <winbase.h>
#endif
#include "prclist.h"
#include "prbit.h"
#include "prtypes.h"
#include "prenv.h"
#include "prgc.h"
#include "prthread.h"
#include "prlog.h"
#include "prlong.h"
#include "prinrval.h"
#include "prprf.h"
#include "gcint.h"
#include "private/pprthred.h"
typedef void (*PRFileDumper)(FILE *out, PRBool detailed);
PR_EXTERN(void)
PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed);
/*
** Mark&sweep garbage collector. Supports objects that require
** finalization, objects that can have a single weak link, and special
** objects that require care during sweeping.
*/
PRLogModuleInfo *_pr_msgc_lm;
PRLogModuleInfo* GC;
static PRInt32 _pr_pageShift;
static PRInt32 _pr_pageSize;
#ifdef DEBUG
#define GCMETER
#endif
#ifdef DEBUG_jwz
# undef GCMETER
#endif /* 1 */
#ifdef GCMETER
#define METER(x) x
#else
#define METER(x)
#endif
/*
** Make this constant bigger to reduce the amount of recursion during
** garbage collection.
*/
#define MAX_SCAN_Q 100L
#if defined(XP_PC) && !defined(WIN32)
#define MAX_SEGS 400L
#define MAX_SEGMENT_SIZE (65536L - 4096L)
#define SEGMENT_SIZE (65536L - 4096L)
#define MAX_ALLOC_SIZE (65536L - 4096L)
#else
#define MAX_SEGS 400L
#define MAX_SEGMENT_SIZE (2L * 256L * 1024L)
#define SEGMENT_SIZE (1L * 256L * 1024L)
#define MAX_ALLOC_SIZE (4L * 1024L * 1024L)
#endif
/*
* The highest value that can fit into a signed integer. This
* is used to prevent overflow of allocation size in alloc routines.
*/
#define MAX_INT ((1UL << (PR_BITS_PER_INT - 1)) - 1)
/*
* On 32-bit machines, only 22 bits are used in the cibx integer to
* store size since 8 bits of the integer are used to store type, and
* of the remainder, 2 are user defined. Max allocation size = 2^22 -1
*/
#define MAX_ALLOC ( (1L << (PR_BYTES_PER_WORD_LOG2 + WORDS_BITS )) -1)
/* The minimum percentage of free heap space after a collection. If
the amount of free space doesn't meet this criteria then we will
attempt to grow the heap */
#define MIN_FREE_THRESHOLD_AFTER_GC 20L
static PRInt32 segmentSize = SEGMENT_SIZE;
static PRInt32 collectorCleanupNeeded;
#ifdef GCMETER
PRUint32 _pr_gcMeter;
#define _GC_METER_STATS 0x01L
#define _GC_METER_GROWTH 0x02L
#define _GC_METER_FREE_LIST 0x04L
#endif
/************************************************************************/
#define LINEAR_BIN_EXPONENT 5
#define NUM_LINEAR_BINS ((PRUint32)1 << LINEAR_BIN_EXPONENT)
#define FIRST_LOG_BIN (NUM_LINEAR_BINS - LINEAR_BIN_EXPONENT)
/* Each free list bin holds a chunk of memory sized from
2^n to (2^(n+1))-1 inclusive. */
#define NUM_BINS (FIRST_LOG_BIN + 32)
/*
* Find the bin number for a given size (in bytes). This does not round up as
* values from 2^n to (2^(n+1))-1 share the same bin.
*/
#define InlineBinNumber(_bin,_bytes) \
{ \
PRUint32 _t, _n = (PRUint32) _bytes / 4; \
if (_n < NUM_LINEAR_BINS) { \
_bin = _n; \
} else { \
_bin = FIRST_LOG_BIN; \
if ((_t = (_n >> 16)) != 0) { _bin += 16; _n = _t; } \
if ((_t = (_n >> 8)) != 0) { _bin += 8; _n = _t; } \
if ((_t = (_n >> 4)) != 0) { _bin += 4; _n = _t; } \
if ((_t = (_n >> 2)) != 0) { _bin += 2; _n = _t; } \
if ((_n >> 1) != 0) _bin++; \
} \
}
#define BIG_ALLOC 16384L
#define MIN_FREE_CHUNK_BYTES ((PRInt32)sizeof(GCFreeChunk))
/* Note: fix code in PR_AllocMemory if you change the size of GCFreeChunk
so that it zeros the right number of words */
typedef struct GCFreeChunk {
struct GCFreeChunk *next;
struct GCSeg *segment;
PRInt32 chunkSize;
} GCFreeChunk;
typedef struct GCSegInfo {
struct GCSegInfo *next;
char *base;
char *limit;
PRWord *hbits;
int fromMalloc;
} GCSegInfo;
typedef struct GCSeg {
char *base;
char *limit;
PRWord *hbits;
GCSegInfo *info;
} GCSeg;
#ifdef GCMETER
typedef struct GCMeter {
PRInt32 allocBytes;
PRInt32 wastedBytes;
PRInt32 numFreeChunks;
PRInt32 skippedFreeChunks;
} GCMeter;
static GCMeter meter;
#endif
/*
** There is one of these for each segment of GC'able memory.
*/
static GCSeg segs[MAX_SEGS];
static GCSegInfo *freeSegs;
static GCSeg* lastInHeap;
static int nsegs;
static GCFreeChunk *bins[NUM_BINS];
static PRInt32 minBin;
static PRInt32 maxBin;
/*
** Scan Q used to avoid deep recursion when scanning live objects for
** heap pointers
*/
typedef struct GCScanQStr {
PRWord *q[MAX_SCAN_Q];
int queued;
} GCScanQ;
static GCScanQ *pScanQ;
#ifdef GCMETER
PRInt32 _pr_maxScanDepth;
PRInt32 _pr_scanDepth;
#endif
/*
** Keeps track of the number of bytes allocated via the BigAlloc()
** allocator. When the number of bytes allocated, exceeds the
** BIG_ALLOC_GC_SIZE, then a GC will occur before the next allocation
** is done...
*/
#define BIG_ALLOC_GC_SIZE (4*SEGMENT_SIZE)
static PRWord bigAllocBytes = 0;
/*
** There is one GC header word in front of each GC allocated object. We
** use it to contain information about the object (what TYPEIX to use for
** scanning it, how big it is, it's mark status, and if it's a root).
*/
#define TYPEIX_BITS 8L
#define WORDS_BITS 20L
#define MAX_CBS (1L << GC_TYPEIX_BITS)
#define MAX_WORDS (1L << GC_WORDS_BITS)
#define TYPEIX_SHIFT 24L
#define MAX_TYPEIX ((1L << TYPEIX_BITS) - 1L)
#define TYPEIX_MASK PR_BITMASK(TYPEIX_BITS)
#define WORDS_SHIFT 2L
#define WORDS_MASK PR_BITMASK(WORDS_BITS)
#define MARK_BIT 1L
#define FINAL_BIT 2L
/* Two bits per object header are reserved for the user of the memory
system to store information into. */
#define GC_USER_BITS_SHIFT 22L
#define GC_USER_BITS 0x00c00000L
#define MAKE_HEADER(_cbix,_words) \
((PRWord) (((unsigned long)(_cbix) << TYPEIX_SHIFT) \
| ((unsigned long)(_words) << WORDS_SHIFT)))
#define GET_TYPEIX(_h) \
(((PRUword)(_h) >> TYPEIX_SHIFT) & 0xff)
#define MARK(_sp,_p) \
(((PRWord *)(_p))[0] |= MARK_BIT)
#define IS_MARKED(_sp,_p) \
(((PRWord *)(_p))[0] & MARK_BIT)
#define OBJ_BYTES(_h) \
(((PRInt32) (_h) & 0x003ffffcL) << (PR_BYTES_PER_WORD_LOG2-2L))
#define GC_GET_USER_BITS(_h) (((_h) & GC_USER_BITS) >> GC_USER_BITS_SHIFT)
/************************************************************************/
/*
** Mark the start of an object in a segment. Note that we mark the header
** word (which we always have), not the data word (which we may not have
** for empty objects).
** XXX tune: put subtract of _sp->base into _sp->hbits pointer?
*/
#define SET_HBIT(_sp,_ph) \
SET_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
#define CLEAR_HBIT(_sp,_ph) \
CLEAR_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
#define IS_HBIT(_sp,_ph) \
TEST_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
/*
** Given a pointer into this segment, back it up until we are at the
** start of the object the pointer points into. Each heap segment has a
** bitmap that has one bit for each word of the objects it contains. The
** bit's are set for the firstword of an object, and clear for it's other
** words.
*/
static PRWord *FindObject(GCSeg *sp, PRWord *p)
{
PRWord *base;
/* Align p to it's proper boundary before we start fiddling with it */
p = (PRWord*) ((PRWord)p & ~(PR_BYTES_PER_WORD-1L));
base = (PRWord *) sp->base;
do {
if (IS_HBIT(sp, p)) {
return (p);
}
p--;
} while ( p >= base );
/* Heap is corrupted! */
_GCTRACE(GC_TRACE, ("ERROR: The heap is corrupted!!! aborting now!"));
abort();
return NULL;
}
/************************************************************************/
#if !defined(XP_PC) || defined(XP_OS2)
#define OutputDebugString(msg)
#endif
#define IN_SEGMENT(_sp, _p) \
((((char *)(_p)) >= (_sp)->base) && \
(((char *)(_p)) < (_sp)->limit))
static GCSeg *InHeap(void *p)
{
GCSeg *sp, *esp;
if (lastInHeap && IN_SEGMENT(lastInHeap, p)) {
return lastInHeap;
}
sp = segs;
esp = segs + nsegs;
for (; sp < esp; sp++) {
if (IN_SEGMENT(sp, p)) {
lastInHeap = sp;
return sp;
}
}
return 0;
}
/*
** Grow the heap by allocating another segment. Fudge the requestedSize
** value to try to pre-account for the HBITS.
*/
static GCSeg* DoGrowHeap(PRInt32 requestedSize, PRBool exactly)
{
GCSeg *sp;
GCSegInfo *segInfo;
GCFreeChunk *cp;
char *base;
PRWord *hbits;
PRInt32 nhbytes, nhbits;
PRUint32 allocSize;
if (nsegs == MAX_SEGS) {
/* No room for more segments */
return 0;
}
segInfo = (GCSegInfo*) PR_MALLOC(sizeof(GCSegInfo));
#ifdef DEBUG
{
char str[256];
sprintf(str, "[1] Allocated %ld bytes at %p\n",
(long) sizeof(GCSegInfo), segInfo);
OutputDebugString(str);
}
#endif
if (!segInfo) {
return 0;
}
/* Get more memory from the OS */
if (exactly) {
allocSize = requestedSize;
base = (char *) PR_MALLOC(requestedSize);
} else {
allocSize = requestedSize;
allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
allocSize <<= _pr_pageShift;
base = (char*)_MD_GrowGCHeap(&allocSize);
}
if (!base) {
PR_DELETE(segInfo);
return 0;
}
nhbits = (PRInt32)(
(allocSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2);
nhbytes = ((nhbits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
* sizeof(PRWord);
/* Get bitmap memory from malloc heap */
hbits = (PRWord *) PR_CALLOC((PRUint32)nhbytes);
if (!hbits) {
/* Loser! */
PR_DELETE(segInfo);
if (exactly) {
PR_DELETE(base);
} else {
/* XXX do something about this */
/* _MD_FreeGCSegment(base, allocSize); */
}
return 0;
}
/*
** Setup new segment.
*/
sp = &segs[nsegs++];
segInfo->base = sp->base = base;
segInfo->limit = sp->limit = base + allocSize;
segInfo->hbits = sp->hbits = hbits;
sp->info = segInfo;
segInfo->fromMalloc = exactly;
memset(base, 0, allocSize);
#ifdef GCMETER
if (_pr_gcMeter & _GC_METER_GROWTH) {
fprintf(stderr, "[GC: new segment base=%p size=%ld]\n",
sp->base, (long) allocSize);
}
#endif
_pr_gcData.allocMemory += allocSize;
_pr_gcData.freeMemory += allocSize;
if (!exactly) {
PRInt32 bin;
/* Put free memory into a freelist bin */
cp = (GCFreeChunk *) base;
cp->segment = sp;
cp->chunkSize = allocSize;
InlineBinNumber(bin, allocSize)
cp->next = bins[bin];
bins[bin] = cp;
if (bin < minBin) minBin = bin;
if (bin > maxBin) maxBin = bin;
} else {
/*
** When exactly allocating the entire segment is given over to a
** single object to prevent fragmentation
*/
}
if (!_pr_gcData.lowSeg) {
_pr_gcData.lowSeg = (PRWord*) sp->base;
_pr_gcData.highSeg = (PRWord*) sp->limit;
} else {
if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
_pr_gcData.lowSeg = (PRWord*) sp->base;
}
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
_pr_gcData.highSeg = (PRWord*) sp->limit;
}
}
/*
** Get rid of the GC pointer in case it shows up in some uninitialized
** local stack variable later (while scanning the C stack looking for
** roots).
*/
memset(&base, 0, sizeof(base)); /* optimizers beware */
PR_LOG(_pr_msgc_lm, PR_LOG_WARNING, ("grow heap: total gc memory now %d",
_pr_gcData.allocMemory));
return sp;
}
#ifdef USE_EXTEND_HEAP
static PRBool ExtendHeap(PRInt32 requestedSize) {
GCSeg* sp;
PRUint32 allocSize;
PRInt32 oldSize, newSize;
PRInt32 newHBits, newHBytes;
PRInt32 oldHBits, oldHBytes;
PRWord* hbits;
GCFreeChunk* cp;
PRInt32 bin;
/* Can't extend nothing */
if (nsegs == 0) return PR_FALSE;
/* Round up requested size to the size of a page */
allocSize = (PRUint32) requestedSize;
allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
allocSize <<= _pr_pageShift;
/* Malloc some memory for the new hbits array */
sp = segs;
oldSize = sp->limit - sp->base;
newSize = oldSize + allocSize;
newHBits = (newSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
newHBytes = ((newHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
* sizeof(PRWord);
hbits = (PRWord*) PR_MALLOC(newHBytes);
if (0 == hbits) return PR_FALSE;
/* Attempt to extend the last segment by the desired amount */
if (_MD_ExtendGCHeap(sp->base, oldSize, newSize)) {
oldHBits = (oldSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
oldHBytes = ((oldHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
* sizeof(PRWord);
/* Copy hbits from old memory into new memory */
memset(hbits, 0, newHBytes);
memcpy(hbits, sp->hbits, oldHBytes);
PR_DELETE(sp->hbits);
memset(sp->base + oldSize, 0, allocSize);
/* Adjust segment state */
sp->limit += allocSize;
sp->hbits = hbits;
sp->info->limit = sp->limit;
sp->info->hbits = hbits;
/* Put free memory into a freelist bin */
cp = (GCFreeChunk *) (sp->base + oldSize);
cp->segment = sp;
cp->chunkSize = allocSize;
InlineBinNumber(bin, allocSize)
cp->next = bins[bin];
bins[bin] = cp;
if (bin < minBin) minBin = bin;
if (bin > maxBin) maxBin = bin;
/* Prevent a pointer that points to the free memory from showing
up on the call stack later on */
memset(&cp, 0, sizeof(cp));
/* Update heap brackets and counters */
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
_pr_gcData.highSeg = (PRWord*) sp->limit;
}
_pr_gcData.allocMemory += allocSize;
_pr_gcData.freeMemory += allocSize;
return PR_TRUE;
}
PR_DELETE(hbits);
return PR_FALSE;
}
#endif /* USE_EXTEND_HEAP */
static GCSeg *GrowHeapExactly(PRInt32 requestedSize)
{
GCSeg *sp = DoGrowHeap(requestedSize, PR_TRUE);
return sp;
}
static PRBool GrowHeap(PRInt32 requestedSize)
{
void *p;
#ifdef USE_EXTEND_HEAP
if (ExtendHeap(requestedSize)) {
return PR_TRUE;
}
#endif
p = DoGrowHeap(requestedSize, PR_FALSE);
return (p != NULL ? PR_TRUE : PR_FALSE);
}
/*
** Release a segment when it is entirely free.
*/
static void ShrinkGCHeap(GCSeg *sp)
{
#ifdef GCMETER
if (_pr_gcMeter & _GC_METER_GROWTH) {
fprintf(stderr, "[GC: free segment base=%p size=%ld]\n",
sp->base, (long) (sp->limit - sp->base));
}
#endif
/*
* Put segment onto free seginfo list (we can't call free right now
* because we have the GC lock and all of the other threads are
* suspended; if one of them has the malloc lock we would deadlock)
*/
sp->info->next = freeSegs;
freeSegs = sp->info;
collectorCleanupNeeded = 1;
_pr_gcData.allocMemory -= sp->limit - sp->base;
if (sp == lastInHeap) lastInHeap = 0;
/* Squish out disappearing segment from segment table */
--nsegs;
if ((sp - segs) != nsegs) {
*sp = segs[nsegs];
} else {
sp->base = 0;
sp->limit = 0;
sp->hbits = 0;
sp->info = 0;
}
/* Recalculate the lowSeg and highSeg values */
_pr_gcData.lowSeg = (PRWord*) segs[0].base;
_pr_gcData.highSeg = (PRWord*) segs[0].limit;
for (sp = segs; sp < &segs[nsegs]; sp++) {
if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
_pr_gcData.lowSeg = (PRWord*) sp->base;
}
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
_pr_gcData.highSeg = (PRWord*) sp->limit;
}
}
}
static void FreeSegments(void)
{
GCSegInfo *si;
while (0 != freeSegs) {
LOCK_GC();
si = freeSegs;
if (si) {
freeSegs = si->next;
}
UNLOCK_GC();
if (!si) {
break;
}
PR_DELETE(si->base);
PR_DELETE(si->hbits);
PR_DELETE(si);
}
}
/************************************************************************/
void ScanScanQ(GCScanQ *iscan)
{
PRWord *p;
PRWord **pp;
PRWord **epp;
GCScanQ nextQ, *scan, *next, *temp;
CollectorType *ct;
if (!iscan->queued) return;
_GCTRACE(GC_MARK, ("begin scanQ @ 0x%x (%d)", iscan, iscan->queued));
scan = iscan;
next = &nextQ;
while (scan->queued) {
_GCTRACE(GC_MARK, ("continue scanQ @ 0x%x (%d)", scan, scan->queued));
/*
* Set pointer to current scanQ so that _pr_gcData.livePointer
* can find it.
*/
pScanQ = next;
next->queued = 0;
/* Now scan the scan Q */
pp = scan->q;
epp = &scan->q[scan->queued];
scan->queued = 0;
while (pp < epp) {
p = *pp++;
ct = &_pr_collectorTypes[GET_TYPEIX(p[0])];
PR_ASSERT(0 != ct->gctype.scan);
/* Scan object ... */
(*ct->gctype.scan)(p + 1);
}
/* Exchange pointers so that we scan next */
temp = scan;
scan = next;
next = temp;
}
pScanQ = iscan;
PR_ASSERT(nextQ.queued == 0);
PR_ASSERT(iscan->queued == 0);
}
/*
** Called during root finding step to identify "root" pointers into the
** GC heap. First validate if it is a real heap pointer and then mark the
** object being pointed to and add it to the scan Q for eventual
** scanning.
*/
static void PR_CALLBACK ProcessRootBlock(void **base, PRInt32 count)
{
GCSeg *sp;
PRWord *p0, *p, h, tix, *low, *high, *segBase;
CollectorType *ct;
#ifdef DEBUG
void **base0 = base;
#endif
low = _pr_gcData.lowSeg;
high = _pr_gcData.highSeg;
while (--count >= 0) {
p0 = (PRWord*) *base++;
if (p0 < low) continue; /* below gc heap */
if (p0 >= high) continue; /* above gc heap */
/* NOTE: inline expansion of InHeap */
/* Find segment */
sp = lastInHeap;
if (!sp || !IN_SEGMENT(sp,p0)) {
GCSeg *esp;
sp = segs;
esp = segs + nsegs;
for (; sp < esp; sp++) {
if (IN_SEGMENT(sp, p0)) {
lastInHeap = sp;
goto find_object;
}
}
continue;
}
find_object:
/* NOTE: Inline expansion of FindObject */
/* Align p to it's proper boundary before we start fiddling with it */
p = (PRWord*) ((PRWord)p0 & ~(PR_BYTES_PER_WORD-1L));
segBase = (PRWord *) sp->base;
do {
if (IS_HBIT(sp, p)) {
goto winner;
}
p--;
} while (p >= segBase);
/*
** We have a pointer into the heap, but it has no header
** bit. This means that somehow the very first object in the heap
** doesn't have a header. This is impossible so when debugging
** lets abort.
*/
#ifdef DEBUG
PR_Abort();
#endif
winner:
h = p[0];
if ((h & MARK_BIT) == 0) {
#ifdef DEBUG
_GCTRACE(GC_ROOTS,
("root 0x%p (%d) base0=%p off=%d",
p, OBJ_BYTES(h), base0, (base-1) - base0));
#endif
/* Mark the root we just found */
p[0] = h | MARK_BIT;
/*
* See if object we just found needs scanning. It must
* have a scan function to be placed on the scanQ.
*/
tix = (PRWord)GET_TYPEIX(h);
ct = &_pr_collectorTypes[tix];
if (0 == ct->gctype.scan) {
continue;
}
/*
** 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);
}
}
}
}
static void PR_CALLBACK ProcessRootPointer(void *ptr)
{
PRWord *p0, *p, h, tix, *segBase;
GCSeg* sp;
CollectorType *ct;
p0 = (PRWord*) ptr;
if (p0 < _pr_gcData.lowSeg) return; /* below gc heap */
if (p0 >= _pr_gcData.highSeg) return; /* above gc heap */
/* NOTE: inline expansion of InHeap */
/* Find segment */
sp = lastInHeap;
if (!sp || !IN_SEGMENT(sp,p0)) {
GCSeg *esp;
sp = segs;
esp = segs + nsegs;
for (; sp < esp; sp++) {
if (IN_SEGMENT(sp, p0)) {
lastInHeap = sp;
goto find_object;
}
}
return;
}
find_object:
/* NOTE: Inline expansion of FindObject */
/* Align p to it's proper boundary before we start fiddling with it */
p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
segBase = (PRWord *) sp->base;
do {
if (IS_HBIT(sp, p)) {
goto winner;
}
p--;
} while (p >= segBase);
/*
** We have a pointer into the heap, but it has no header
** bit. This means that somehow the very first object in the heap
** doesn't have a header. This is impossible so when debugging
** lets abort.
*/
#ifdef DEBUG
PR_Abort();
#endif
winner:
h = p[0];
if ((h & MARK_BIT) == 0) {
#ifdef DEBUG
_GCTRACE(GC_ROOTS, ("root 0x%p (%d)", p, OBJ_BYTES(h)));
#endif
/* Mark the root we just found */
p[0] = h | MARK_BIT;
/*
* See if object we just found needs scanning. It must
* have a scan function to be placed on the scanQ.
*/
tix = (PRWord)GET_TYPEIX(h);
ct = &_pr_collectorTypes[tix];
if (0 == ct->gctype.scan) {
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)
{
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)
{
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);
}
}
static void NotifyFinalizer(void)
{
if (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
PR_ASSERT( GC_IS_LOCKED() );
PR_Notify(_pr_gcData.lock);
}
}
void _PR_CreateFinalizer(PRThreadScope scope)
{
if (!_pr_gcData.finalizer) {
_pr_gcData.finalizer = PR_CreateThreadGCAble(PR_SYSTEM_THREAD,
FinalizerLoop, 0,
PR_PRIORITY_LOW, scope,
PR_UNJOINABLE_THREAD, 0);
if (_pr_gcData.finalizer == NULL)
/* We are doomed if we can't start the finalizer */
PR_Abort();
}
}
void pr_FinalizeOnExit(void)
{
#ifdef DEBUG_warren
OutputDebugString("### Doing finalize-on-exit pass\n");
#endif
PR_ForceFinalize();
#ifdef DEBUG_warren
OutputDebugString("### Finalize-on-exit complete. Dumping object left to memory.out\n");
PR_DumpMemorySummary();
PR_DumpMemory(PR_TRUE);
#endif
}
PR_IMPLEMENT(void) PR_ForceFinalize()
{
LOCK_GC();
NotifyFinalizer();
while (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
PR_ASSERT( GC_IS_LOCKED() );
(void) PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
}
UNLOCK_GC();
/* XXX I don't know how to make it wait (yet) */
}
/************************************************************************/
typedef struct GCWeakStr {
PRCList links;
PRWord *object;
} GCWeak;
/*
** Find pointer to GCWeak struct from the list linkaged embedded in it
*/
#define WeakPtr(_qp) \
((GCWeak*) ((char*) (_qp) - offsetof(GCWeak,links)))
PRCList _pr_weakLinks = PR_INIT_STATIC_CLIST(&_pr_weakLinks);
PRCList _pr_freeWeakLinks = PR_INIT_STATIC_CLIST(&_pr_freeWeakLinks);
#define WEAK_FREELIST_ISEMPTY() (_pr_freeWeakLinks.next == &_pr_freeWeakLinks)
/*
* Keep objects referred to by weak free list alive until they can be
* freed
*/
static void PR_CALLBACK ScanWeakFreeList(void *notused) {
PRCList *qp = _pr_freeWeakLinks.next;
while (qp != &_pr_freeWeakLinks) {
GCWeak *wp = WeakPtr(qp);
qp = qp->next;
ProcessRootPointer(wp->object);
}
}
/*
* Empty the list of weak objects. Note that we can't call malloc/free
* under the cover of the GC's lock (we might deadlock), so transfer the
* list of free objects to a local list under the cover of the lock, then
* release the lock and free up the memory.
*/
static void EmptyWeakFreeList(void) {
if (!WEAK_FREELIST_ISEMPTY()) {
PRCList *qp, freeLinks;
PR_INIT_CLIST(&freeLinks);
/*
* Transfer list of free weak links from the global list to a
* local list.
*/
LOCK_GC();
qp = _pr_freeWeakLinks.next;
while (qp != &_pr_freeWeakLinks) {
GCWeak *wp = WeakPtr(qp);
qp = qp->next;
PR_REMOVE_LINK(&wp->links);
PR_APPEND_LINK(&wp->links, &freeLinks);
}
UNLOCK_GC();
/* Free up storage now */
qp = freeLinks.next;
while (qp != &freeLinks) {
GCWeak *wp = WeakPtr(qp);
qp = qp->next;
PR_DELETE(wp);
}
}
}
/*
* Allocate a new weak node in the weak objects list
*/
static GCWeak *AllocWeakNode(void)
{
EmptyWeakFreeList();
return PR_NEWZAP(GCWeak);
}
static void FreeWeakNode(GCWeak *node)
{
PR_DELETE(node);
}
/*
* Check the weak links for validity. Note that the list of weak links is
* itself weak (otherwise we would keep the objects with weak links in
* them alive forever). As we scan the list check the weak link object
* itself and if it's not marked then remove it from the weak link list
*/
static void CheckWeakLinks(void) {
PRCList *qp;
GCWeak *wp;
PRWord *p, h, tix, **weakPtrAddress;
CollectorType *ct;
PRUint32 offset;
qp = _pr_weakLinks.next;
while (qp != &_pr_weakLinks) {
wp = WeakPtr(qp);
qp = qp->next;
if ((p = wp->object) != 0) {
h = p[0]; /* Grab header word */
if ((h & MARK_BIT) == 0) {
/*
* The object that has a weak link is no longer being
* referenced; remove it from the chain and let it get
* swept away by the GC. Transfer it to the list of
* free weak links for later freeing.
*/
PR_REMOVE_LINK(&wp->links);
PR_APPEND_LINK(&wp->links, &_pr_freeWeakLinks);
collectorCleanupNeeded = 1;
continue;
}
/* Examine a live object that contains weak links */
tix = GET_TYPEIX(h);
ct = &_pr_collectorTypes[tix];
PR_ASSERT((ct->flags != 0) && (ct->gctype.getWeakLinkOffset != 0));
if (0 == ct->gctype.getWeakLinkOffset) {
/* Heap is probably corrupted */
continue;
}
/* Get offset into the object of where the weak pointer is */
offset = (*ct->gctype.getWeakLinkOffset)(p + 1);
/* Check the weak pointer */
weakPtrAddress = (PRWord**)((char*)(p + 1) + offset);
p = *weakPtrAddress;
if (p != 0) {
h = p[-1]; /* Grab header word for pointed to object */
if (h & MARK_BIT) {
/* Object can't be dead */
continue;
}
/* Break weak link to an object that is about to be swept */
*weakPtrAddress = 0;
}
}
}
}
/************************************************************************/
/*
** Perform a complete garbage collection
*/
extern GCLockHook *_pr_GCLockHook;
static void dogc(void)
{
RootFinder *rf;
GCLockHook* lhook;
GCScanQ scanQ;
GCSeg *sp, *esp;
PRInt64 start, end, diff;
#if defined(GCMETER) || defined(GCTIMINGHOOK)
start = PR_Now();
#endif
/*
** Stop all of the other threads. This also promises to capture the
** register state of each and every thread
*/
/*
** Get all the locks that will be need during GC after SuspendAll. We
** cannot make any locking/library calls after SuspendAll.
*/
if (_pr_GCLockHook) {
for (lhook = _pr_GCLockHook->next; lhook != _pr_GCLockHook;
lhook = lhook->next) {
(*lhook->func)(PR_GCBEGIN, lhook->arg);
}
}
PR_SuspendAll();
#ifdef GCMETER
/* Reset meter info */
if (_pr_gcMeter & _GC_METER_STATS) {
fprintf(stderr,
"[GCSTATS: busy:%ld skipped:%ld, alloced:%ld+wasted:%ld+free:%ld = total:%ld]\n",
(long) _pr_gcData.busyMemory,
(long) meter.skippedFreeChunks,
(long) meter.allocBytes,
(long) meter.wastedBytes,
(long) _pr_gcData.freeMemory,
(long) _pr_gcData.allocMemory);
}
memset(&meter, 0, sizeof(meter));
#endif
PR_LOG(_pr_msgc_lm, PR_LOG_ALWAYS, ("begin mark phase; busy=%d free=%d total=%d",
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
_pr_gcData.allocMemory));
if (_pr_beginGCHook) {
(*_pr_beginGCHook)(_pr_beginGCHookArg);
}
/*
** Initialize scanQ to all zero's so that root finder doesn't walk
** over it...
*/
memset(&scanQ, 0, sizeof(scanQ));
pScanQ = &scanQ;
/******************************************/
/* MARK PHASE */
EmptyFreelists();
/* Find root's */
PR_LOG(_pr_msgc_lm, PR_LOG_WARNING,
("begin mark phase; busy=%d free=%d total=%d",
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
_pr_gcData.allocMemory));
METER(_pr_scanDepth = 0);
rf = _pr_rootFinders;
while (rf) {
_GCTRACE(GC_ROOTS, ("finding roots in %s", rf->name));
(*rf->func)(rf->arg);
rf = rf->next;
}
_GCTRACE(GC_ROOTS, ("done finding roots"));
/* Scan remaining object's that need scanning */
ScanScanQ(&scanQ);
PR_ASSERT(pScanQ == &scanQ);
PR_ASSERT(scanQ.queued == 0);
METER({
if (_pr_scanDepth > _pr_maxScanDepth) {
_pr_maxScanDepth = _pr_scanDepth;
}
});
/******************************************/
/* FINALIZATION PHASE */
METER(_pr_scanDepth = 0);
PrepareFinalize();
/* Scan any resurrected objects found during finalization */
ScanScanQ(&scanQ);
PR_ASSERT(pScanQ == &scanQ);
PR_ASSERT(scanQ.queued == 0);
METER({
if (_pr_scanDepth > _pr_maxScanDepth) {
_pr_maxScanDepth = _pr_scanDepth;
}
});
pScanQ = 0;
/******************************************/
/* SWEEP PHASE */
/*
** Sweep each segment clean. While we are at it, figure out which
** segment has the most free space and make that the current segment.
*/
CheckWeakLinks();
_GCTRACE(GC_SWEEP, ("begin sweep phase"));
_pr_gcData.freeMemory = 0;
_pr_gcData.busyMemory = 0;
sp = segs;
esp = sp + nsegs;
while (sp < esp) {
if (SweepSegment(sp)) {
/*
** Segment is now free and has been replaced with a different
** segment object.
*/
esp--;
continue;
}
sp++;
}
#if defined(GCMETER) || defined(GCTIMINGHOOK)
end = PR_Now();
#endif
#ifdef GCMETER
LL_SUB(diff, end, start);
PR_LOG(GC, PR_LOG_ALWAYS,
("done; busy=%d free=%d chunks=%d total=%d time=%lldms",
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
meter.numFreeChunks, _pr_gcData.allocMemory, diff));
if (_pr_gcMeter & _GC_METER_FREE_LIST) {
PRIntn bin;
fprintf(stderr, "Freelist bins:\n");
for (bin = 0; bin < NUM_BINS; bin++) {
GCFreeChunk *cp = bins[bin];
while (cp != NULL) {
fprintf(stderr, "%3d: %p %8ld\n",
bin, cp, (long) cp->chunkSize);
cp = cp->next;
}
}
}
#endif
if (_pr_endGCHook) {
(*_pr_endGCHook)(_pr_endGCHookArg);
}
/* clear the running total of the bytes allocated via BigAlloc() */
bigAllocBytes = 0;
/* And resume multi-threading */
PR_ResumeAll();
if (_pr_GCLockHook) {
for (lhook = _pr_GCLockHook->prev; lhook != _pr_GCLockHook;
lhook = lhook->prev) {
(*lhook->func)(PR_GCEND, lhook->arg);
}
}
/* Kick finalizer */
NotifyFinalizer();
#ifdef GCTIMINGHOOK
if (_pr_gcData.gcTimingHook) {
PRInt32 time;
LL_SUB(diff, end, start);
LL_L2I(time, diff);
_pr_gcData.gcTimingHook(time);
}
#endif
}
PR_IMPLEMENT(void) PR_GC(void)
{
LOCK_GC();
dogc();
UNLOCK_GC();
EmptyWeakFreeList();
}
/*******************************************************************************
* Heap Walker
******************************************************************************/
/*
** This is yet another disgusting copy of the body of ProcessRootPointer
** (the other being ProcessRootBlock), but we're not leveraging a single
** function in their cases in interest of performance (avoiding the function
** call).
*/
static PRInt32 PR_CALLBACK
pr_ConservativeWalkPointer(void* ptr, PRWalkFun walkRootPointer, void* data)
{
PRWord *p0, *p, *segBase;
GCSeg* sp;
p0 = (PRWord*) ptr;
if (p0 < _pr_gcData.lowSeg) return 0; /* below gc heap */
if (p0 >= _pr_gcData.highSeg) return 0; /* above gc heap */
/* NOTE: inline expansion of InHeap */
/* Find segment */
sp = lastInHeap;
if (!sp || !IN_SEGMENT(sp,p0)) {
GCSeg *esp;
sp = segs;
esp = segs + nsegs;
for (; sp < esp; sp++) {
if (IN_SEGMENT(sp, p0)) {
lastInHeap = sp;
goto find_object;
}
}
return 0;
}
find_object:
/* NOTE: Inline expansion of FindObject */
/* Align p to it's proper boundary before we start fiddling with it */
p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
segBase = (PRWord *) sp->base;
do {
if (IS_HBIT(sp, p)) {
goto winner;
}
p--;
} while (p >= segBase);
/*
** We have a pointer into the heap, but it has no header
** bit. This means that somehow the very first object in the heap
** doesn't have a header. This is impossible so when debugging
** lets abort.
*/
#ifdef DEBUG
PR_Abort();
#endif
return 0;
winner:
return walkRootPointer(p, data);
}
static PRInt32 PR_CALLBACK
pr_ConservativeWalkBlock(void **base, PRInt32 count,
PRWalkFun walkRootPointer, void* data)
{
PRWord *p0;
while (--count >= 0) {
PRInt32 status;
p0 = (PRWord*) *base++;
status = pr_ConservativeWalkPointer(p0, walkRootPointer, data);
if (status) return status;
}
return 0;
}
/******************************************************************************/
typedef void (*WalkObject_t)(FILE *out, GCType* tp, PRWord *obj,
size_t bytes, PRBool detailed);
typedef void (*WalkUnknown_t)(FILE *out, GCType* tp, PRWord tix, PRWord *p,
size_t bytes, PRBool detailed);
typedef void (*WalkFree_t)(FILE *out, PRWord *p, size_t size, PRBool detailed);
typedef void (*WalkSegment_t)(FILE *out, GCSeg* sp, PRBool detailed);
static void
pr_WalkSegment(FILE* out, GCSeg* sp, PRBool detailed,
char* enterMsg, char* exitMsg,
WalkObject_t walkObject, WalkUnknown_t walkUnknown, WalkFree_t walkFree)
{
PRWord *p, *limit;
p = (PRWord *) sp->base;
limit = (PRWord *) sp->limit;
if (enterMsg)
fprintf(out, enterMsg, p);
while (p < limit)
{
if (IS_HBIT(sp, p)) /* Is this an object header? */
{
PRWord h = p[0];
PRWord tix = GET_TYPEIX(h);
size_t bytes = OBJ_BYTES(h);
PRWord* np = (PRWord*) ((char*)p + bytes);
GCType* tp = &_pr_collectorTypes[tix].gctype;
if ((0 != tp) && walkObject)
walkObject(out, tp, p, bytes, detailed);
else if (walkUnknown)
walkUnknown(out, tp, tix, p, bytes, detailed);
p = np;
}
else
{
/* Must be a freelist item */
size_t size = ((GCFreeChunk*)p)->chunkSize;
if (walkFree)
walkFree(out, p, size, detailed);
p = (PRWord*)((char*)p + size);
}
}
if (p != limit)
fprintf(out, "SEGMENT OVERRUN (end should be at 0x%p)\n", limit);
if (exitMsg)
fprintf(out, exitMsg, p);
}
static void
pr_WalkSegments(FILE *out, WalkSegment_t walkSegment, PRBool detailed)
{
GCSeg *sp = segs;
GCSeg *esp;
LOCK_GC();
esp = sp + nsegs;
while (sp < esp)
{
walkSegment(out, sp, detailed);
sp++;
}
fprintf(out, "End of heap\n");
UNLOCK_GC();
}
/*******************************************************************************
* Heap Dumper
******************************************************************************/
PR_IMPLEMENT(void)
PR_DumpIndent(FILE *out, int indent)
{
while (--indent >= 0)
fprintf(out, " ");
}
static void
PR_DumpHexWords(FILE *out, PRWord *p, int nWords,
int indent, int nWordsPerLine)
{
while (nWords > 0)
{
int i;
PR_DumpIndent(out, indent);
i = nWordsPerLine;
if (i > nWords)
i = nWords;
nWords -= i;
while (i--)
{
fprintf(out, "0x%.8lX", (long) *p++);
if (i)
fputc(' ', out);
}
fputc('\n', out);
}
}
static void PR_CALLBACK
pr_DumpObject(FILE *out, GCType* tp, PRWord *p,
size_t bytes, PRBool detailed)
{
char kindChar = tp->kindChar;
fprintf(out, "0x%p: 0x%.6lX %c ",
p, (long) bytes, kindChar ? kindChar : '?');
if (tp->dump)
(*tp->dump)(out, (void*) (p + 1), detailed, 0);
if (detailed)
PR_DumpHexWords(out, p, bytes>>2, 22, 4);
}
static void PR_CALLBACK
pr_DumpUnknown(FILE *out, GCType* tp, PRWord tix, PRWord *p,
size_t bytes, PRBool detailed)
{
char kindChar = tp->kindChar;
fprintf(out, "0x%p: 0x%.6lX %c ",
p, (long) bytes, kindChar ? kindChar : '?');
fprintf(out, "UNKNOWN KIND %ld\n", (long) tix);
if (detailed)
PR_DumpHexWords(out, p, bytes>>2, 22, 4);
}
static void PR_CALLBACK
pr_DumpFree(FILE *out, PRWord *p, size_t size, PRBool detailed)
{
fprintf(out, "0x%p: 0x%.6lX - FREE\n", p, (long) size);
}
static void PR_CALLBACK
pr_DumpSegment(FILE* out, GCSeg* sp, PRBool detailed)
{
pr_WalkSegment(out, sp, detailed,
"\n Address: Length\n0x%p: Beginning of segment\n",
"0x%p: End of segment\n\n",
pr_DumpObject, pr_DumpUnknown, pr_DumpFree);
}
static void pr_DumpRoots(FILE *out);
/*
** Dump out the GC heap.
*/
PR_IMPLEMENT(void)
PR_DumpGCHeap(FILE *out, PRBool detailed)
{
fprintf(out, "\n"
"The kinds are:\n"
" U unscanned block\n"
" W weak link block\n"
" S scanned block\n"
" F scanned and final block\n"
" C class record\n"
" X context record\n"
" - free list item\n"
" ? other\n");
LOCK_GC();
pr_WalkSegments(out, pr_DumpSegment, detailed);
if (detailed)
pr_DumpRoots(out);
UNLOCK_GC();
}
PR_IMPLEMENT(void)
PR_DumpMemory(PRBool detailed)
{
PR_DumpToFile("memory.out", "Dumping memory", PR_DumpGCHeap, detailed);
}
/******************************************************************************/
static PRInt32 PR_CALLBACK
pr_DumpRootPointer(PRWord* p, void* data)
{
PRWord h = p[0];
PRWord tix = GET_TYPEIX(h);
size_t bytes = OBJ_BYTES(h);
GCType* tp = &_pr_collectorTypes[tix].gctype;
if (0 != tp)
pr_DumpObject(_pr_gcData.dumpOutput, tp, p, bytes, PR_FALSE);
else
pr_DumpUnknown(_pr_gcData.dumpOutput, tp, tix, p, bytes, PR_FALSE);
return 0;
}
static void PR_CALLBACK
pr_ConservativeDumpRootPointer(void* ptr)
{
(void)pr_ConservativeWalkPointer(ptr, (PRWalkFun) pr_DumpRootPointer, NULL);
}
static void PR_CALLBACK
pr_ConservativeDumpRootBlock(void **base, PRInt32 count)
{
(void)pr_ConservativeWalkBlock(base, count, (PRWalkFun) pr_DumpRootPointer, NULL);
}
extern int
DumpThreadRoots(PRThread *t, int i, void *notused);
static void
pr_DumpRoots(FILE *out)
{
RootFinder *rf;
void (*liveBlock)(void **base, PRInt32 count);
void (*livePointer)(void *ptr);
void (*processRootBlock)(void **base, PRInt32 count);
void (*processRootPointer)(void *ptr);
LOCK_GC();
liveBlock = _pr_gcData.liveBlock;
livePointer = _pr_gcData.livePointer;
processRootBlock = _pr_gcData.processRootBlock;
processRootPointer = _pr_gcData.processRootPointer;
_pr_gcData.liveBlock = pr_ConservativeDumpRootBlock;
_pr_gcData.livePointer = pr_ConservativeDumpRootPointer;
_pr_gcData.processRootBlock = pr_ConservativeDumpRootBlock;
_pr_gcData.processRootPointer = pr_ConservativeDumpRootPointer;
_pr_gcData.dumpOutput = out;
rf = _pr_rootFinders;
while (rf) {
fprintf(out, "\n===== Roots for %s\n", rf->name);
(*rf->func)(rf->arg);
rf = rf->next;
}
_pr_gcData.liveBlock = liveBlock;
_pr_gcData.livePointer = livePointer;
_pr_gcData.processRootBlock = processRootBlock;
_pr_gcData.processRootPointer = processRootPointer;
_pr_gcData.dumpOutput = NULL;
UNLOCK_GC();
}
/*******************************************************************************
* Heap Summary Dumper
******************************************************************************/
PRSummaryPrinter summaryPrinter = NULL;
void* summaryPrinterClosure = NULL;
PR_IMPLEMENT(void)
PR_RegisterSummaryPrinter(PRSummaryPrinter fun, void* closure)
{
summaryPrinter = fun;
summaryPrinterClosure = closure;
}
static void PR_CALLBACK
pr_SummarizeObject(FILE *out, GCType* tp, PRWord *p,
size_t bytes, PRBool detailed)
{
if (tp->summarize)
(*tp->summarize)((void GCPTR*)(p + 1), bytes);
}
static void PR_CALLBACK
pr_DumpSummary(FILE* out, GCSeg* sp, PRBool detailed)
{
pr_WalkSegment(out, sp, detailed, NULL, NULL,
pr_SummarizeObject, NULL, NULL);
}
PR_IMPLEMENT(void)
PR_DumpGCSummary(FILE *out, PRBool detailed)
{
if (summaryPrinter) {
pr_WalkSegments(out, pr_DumpSummary, detailed);
summaryPrinter(out, summaryPrinterClosure);
}
#if 0
fprintf(out, "\nFinalizable objects:\n");
{
PRCList *qp;
qp = _pr_pendingFinalQueue.next;
while (qp != &_pr_pendingFinalQueue) {
GCFinal* fp = FinalPtr(qp);
PRWord h = fp->object[0]; /* Grab header word */
PRWord tix = GET_TYPEIX(h);
GCType* tp = _pr_gcTypes[tix];
size_t bytes = OBJ_BYTES(h);
pr_DumpObject(out, tp, fp->object, bytes, PR_FALSE);
qp = qp->next;
}
}
#endif
}
PR_IMPLEMENT(void)
PR_DumpMemorySummary(void)
{
PR_DumpToFile("memory.out", "Memory Summary", PR_DumpGCSummary, PR_FALSE);
}
/*******************************************************************************
* End Of Heap Walker
******************************************************************************/
#ifdef GC_TRACEROOTS
PRInt32 pr_traceGen = 0;
static PRBool
pr_IsMarked(PRWord* p)
{
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
PR_ASSERT(end->check == PR_BLOCK_END);
return end->traceGeneration == pr_traceGen;
}
static void
pr_Mark(PRWord* p)
{
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
PR_ASSERT(end->check == PR_BLOCK_END);
end->traceGeneration = pr_traceGen;
}
PRWord* pr_traceObj; /* set this in the debugger, then execute PR_TraceRoot() */
static PRInt32 PR_CALLBACK
pr_TraceRootObject(void* obj, void* data);
static PRInt32 PR_CALLBACK
pr_TraceRootPointer(PRWord *p, void* data)
{
PRInt32 printTrace = 0;
PRWord h = p[0];
PRWord tix = GET_TYPEIX(h);
GCType* tp = &_pr_collectorTypes[tix].gctype;
FILE* out = _pr_gcData.dumpOutput;
PR_ASSERT(tp);
if (pr_IsMarked(p))
return printTrace;
pr_Mark(p);
if (p == pr_traceObj) {
fprintf(out, "\n### Found path to:\n");
printTrace = 1;
}
else {
if (PR_StackSpaceLeft(PR_GetCurrentThread()) < 512) {
fprintf(out, "\n### Path too deep (giving up):\n");
printTrace = 1;
}
else if (tp->walk) {
printTrace = tp->walk((void*)(p + 1), pr_TraceRootObject, data);
}
/* else there's no way to walk this object, so we
haven't found what we're looking for */
}
if (printTrace == 1) {
PR_ASSERT(tp->dump);
fprintf(out, "0x%p: ", p);
tp->dump(out, (void*)(p + 1), PR_FALSE, 1);
}
return printTrace;
}
static PRInt32 PR_CALLBACK
pr_TraceRootObject(void* obj, void* data)
{
/* This version of pr_TraceRootPointer takes object
pointers, instead of gc header pointers. */
return pr_TraceRootPointer((PRWord*)obj - 1, data);
}
static void PR_CALLBACK
pr_ConservativeTraceRootPointer(PRWord *p)
{
PRInt32 status;
++pr_traceGen;
status = pr_ConservativeWalkPointer(p, pr_TraceRootPointer, NULL);
if (status) {
FILE* out = _pr_gcData.dumpOutput;
fprintf(out, "### from root at 0x%p\n\n", p);
}
}
static void PR_CALLBACK
pr_ConservativeTraceRootBlock(void **base, PRInt32 count)
{
PRInt32 status;
++pr_traceGen;
status = pr_ConservativeWalkBlock(base, count, pr_TraceRootPointer, NULL);
if (status) {
FILE* out = _pr_gcData.dumpOutput;
fprintf(out, "### from root in range 0x%p + 0x%lx\n\n",
base, (long) count);
}
}
static void
PR_TraceRoot1(FILE* out, PRBool detailed)
{
RootFinder *rf;
void (*liveBlock)(void **base, PRInt32 count);
void (*livePointer)(void *ptr);
void (*processRootBlock)(void **base, PRInt32 count);
void (*processRootPointer)(void *ptr);
LOCK_GC();
liveBlock = _pr_gcData.liveBlock;
livePointer = _pr_gcData.livePointer;
processRootBlock = _pr_gcData.processRootBlock;
processRootPointer = _pr_gcData.processRootPointer;
_pr_gcData.liveBlock = pr_ConservativeTraceRootBlock;
_pr_gcData.livePointer = pr_ConservativeTraceRootPointer;
_pr_gcData.processRootBlock = pr_ConservativeTraceRootBlock;
_pr_gcData.processRootPointer = pr_ConservativeTraceRootPointer;
_pr_gcData.dumpOutput = out;
fprintf(out, "### Looking for paths to 0x%p\n\n", pr_traceObj);
rf = _pr_rootFinders;
while (rf) {
fprintf(out, "\n===== Roots for %s\n", rf->name);
(*rf->func)(rf->arg);
rf = rf->next;
}
_pr_gcData.liveBlock = liveBlock;
_pr_gcData.livePointer = livePointer;
_pr_gcData.processRootBlock = processRootBlock;
_pr_gcData.processRootPointer = processRootPointer;
_pr_gcData.dumpOutput = NULL;
UNLOCK_GC();
}
PR_PUBLIC_API(void)
PR_TraceRoot()
{
/*
** How this works:
** Once you find the object you want to trace the roots of, set the
** global variable pr_traceObj to point to it (the header, not the
** java handle), and then call this routine (on Windows, you can set
** a breakpoint at the end of a function that returns void (e.g. dogc)
** and then do a "set next statement" to point to this routine and go.
** This will dump a list of the paths from the roots to the object in
** question to your memory.out file.
*/
PR_DumpToFile("memory.out", "Tracing Roots", PR_TraceRoot1, PR_FALSE);
}
#endif /* GC_TRACEROOTS */
/******************************************************************************/
#if defined(DEBUG) && defined(WIN32)
static void DumpApplicationHeap(FILE *out, HANDLE heap)
{
PROCESS_HEAP_ENTRY entry;
DWORD err;
if (!HeapLock(heap))
OutputDebugString("Can't lock the heap.\n");
entry.lpData = 0;
fprintf(out, " address: size ovhd region\n");
while (HeapWalk(heap, &entry))
{
WORD flags = entry.wFlags;
fprintf(out, "0x%.8X: 0x%.8X 0x%.2X 0x%.2X ", entry.lpData, entry.cbData,
entry.cbOverhead, entry.iRegionIndex);
if (flags & PROCESS_HEAP_REGION)
fprintf(out, "REGION committedSize=0x%.8X uncommittedSize=0x%.8X firstBlock=0x%.8X lastBlock=0x%.8X",
entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
entry.Region.lpFirstBlock, entry.Region.lpLastBlock);
else if (flags & PROCESS_HEAP_UNCOMMITTED_RANGE)
fprintf(out, "UNCOMMITTED");
else if (flags & PROCESS_HEAP_ENTRY_BUSY)
{
if (flags & PROCESS_HEAP_ENTRY_DDESHARE)
fprintf(out, "DDEShare ");
if (flags & PROCESS_HEAP_ENTRY_MOVEABLE)
fprintf(out, "Moveable Block handle=0x%.8X", entry.Block.hMem);
else
fprintf(out, "Block");
}
fprintf(out, "\n");
}
if ((err = GetLastError()) != ERROR_NO_MORE_ITEMS)
fprintf(out, "ERROR %d iterating through the heap\n", err);
if (!HeapUnlock(heap))
OutputDebugString("Can't unlock the heap.\n");
}
#endif
#if defined(DEBUG) && defined(WIN32)
static void DumpApplicationHeaps(FILE *out)
{
HANDLE mainHeap;
HANDLE heaps[100];
DWORD nHeaps;
PRInt32 i;
mainHeap = GetProcessHeap();
nHeaps = GetProcessHeaps(100, heaps);
if (nHeaps > 100)
nHeaps = 0;
fprintf(out, "%ld heaps:\n", (long) nHeaps);
for (i = 0; i<nHeaps; i++)
{
HANDLE heap = heaps[i];
fprintf(out, "Heap at 0x%.8lX", (long) heap);
if (heap == mainHeap)
fprintf(out, " (main)");
fprintf(out, ":\n");
DumpApplicationHeap(out, heap);
fprintf(out, "\n");
}
fprintf(out, "End of heap dump\n\n");
}
#endif
#if defined(DEBUG) && defined(WIN32)
PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
{
FILE *out;
OutputDebugString("Dumping heaps...");
out = fopen("heaps.out", "a");
if (!out)
OutputDebugString("Can't open \"heaps.out\"\n");
else
{
struct tm *newtime;
time_t aclock;
time(&aclock);
newtime = localtime(&aclock);
fprintf(out, "Heap dump on %s\n", asctime(newtime)); /* Print current time */
DumpApplicationHeaps(out);
fprintf(out, "\n\n");
fclose(out);
}
OutputDebugString(" done\n");
}
#else
PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
{
fprintf(stderr, "Native heap dumping is currently implemented only for Windows32.\n");
}
#endif
/************************************************************************/
/*
** Scan the freelist bins looking for a big enough chunk of memory to
** hold "bytes" worth of allocation. "bytes" already has the
** per-allocation header added to it. Return a pointer to the object with
** its per-allocation header already prepared.
*/
static PRWord *BinAlloc(int cbix, PRInt32 bytes, int dub)
{
GCFreeChunk **cpp, *cp, *cpNext;
GCSeg *sp;
PRInt32 chunkSize, remainder;
PRWord *p, *np;
PRInt32 bin, newbin;
/* Compute bin that allocation belongs in */
InlineBinNumber(bin,bytes)
if (bin < minBin) {
bin = minBin; /* Start at first filled bin */
}
/* Search in the bin, and larger bins, for a big enough piece */
for (; bin <= NUM_BINS-1; bin++) {
cpp = &bins[bin];
while ((cp = *cpp) != 0) {
chunkSize = cp->chunkSize;
if (chunkSize < bytes) {
/* Too small; skip it */
METER(meter.skippedFreeChunks++);
cpp = &cp->next;
continue;
}
/* We have found a hunk of memory large enough to use */
p = (PRWord*) cp;
sp = cp->segment;
cpNext = cp->next;
#ifndef IS_64
if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
/*
* We are double aligning the memory and the current free
* chunk is aligned on an even boundary. Because header
* words are one word long we need to discard the first
* word of memory.
*/
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
SET_HBIT(sp, p);
p++;
chunkSize -= PR_BYTES_PER_WORD;
bytes -= PR_BYTES_PER_WORD;
PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
_pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
_pr_gcData.busyMemory += PR_BYTES_PER_WORD;
}
#endif
np = (PRWord*) ((char*) p + bytes);
remainder = chunkSize - bytes;
if (remainder >= MIN_FREE_CHUNK_BYTES) {
/* The left over memory is large enough to be freed. */
cp = (GCFreeChunk*) np;
cp->segment = sp;
cp->chunkSize = remainder;
InlineBinNumber(newbin, remainder)
if (newbin != bin) {
*cpp = (GCFreeChunk*) cpNext; /* remove */
cp->next = bins[newbin]; /* insert */
bins[newbin] = cp;
if (newbin < minBin) minBin = newbin;
if (newbin > maxBin) maxBin = newbin;
} else {
/* Leave it on the same list */
cp->next = cpNext;
*cpp = (GCFreeChunk*) np;
}
} else {
/*
* The left over memory is too small to be released. Just
* leave it attached to the chunk of memory being
* returned.
*/
*cpp = cpNext;
bytes = chunkSize;
}
p[0] = MAKE_HEADER(cbix, (bytes >> PR_BYTES_PER_WORD_LOG2));
SET_HBIT(sp, p);
_pr_gcData.freeMemory -= bytes;
_pr_gcData.busyMemory += bytes;
return p;
}
}
return 0;
}
/*
** Allocate a piece of memory that is "big" in it's own segment. Make
** the object consume the entire segment to avoid fragmentation. When
** the object is no longer referenced, the segment is freed.
*/
static PRWord *BigAlloc(int cbix, PRInt32 bytes, int dub)
{
GCSeg *sp;
PRWord *p, h;
PRInt32 chunkSize;
/*
** If the number of bytes allocated via BigAlloc() since the last GC
** exceeds BIG_ALLOC_GC_SIZE then do a GC Now...
*/
if (bigAllocBytes >= BIG_ALLOC_GC_SIZE) {
dogc();
}
bigAllocBytes += bytes;
/* Get a segment to hold this allocation */
sp = GrowHeapExactly(bytes);
if (sp) {
p = (PRWord*) sp->base;
chunkSize = sp->limit - sp->base;
/* All memory is double aligned on 64 bit machines... */
#ifndef IS_64
if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
/*
** Consume the first word of the chunk with a dummy
** unreferenced object.
*/
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
SET_HBIT(sp, p);
p++;
chunkSize -= PR_BYTES_PER_WORD;
_pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
_pr_gcData.busyMemory += PR_BYTES_PER_WORD;
PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
}
#endif
/* Consume the *entire* segment with a single allocation */
h = MAKE_HEADER(cbix, (chunkSize >> PR_BYTES_PER_WORD_LOG2));
p[0] = h;
SET_HBIT(sp, p);
_pr_gcData.freeMemory -= chunkSize;
_pr_gcData.busyMemory += chunkSize;
return p;
}
return 0;
}
/* we disable gc allocation during low memory conditions */
static PRBool allocationEnabled = PR_TRUE;
PR_IMPLEMENT(void) PR_EnableAllocation(PRBool yesOrNo)
{
allocationEnabled = yesOrNo;
}
static void CollectorCleanup(void) {
while (collectorCleanupNeeded) {
LOCK_GC();
collectorCleanupNeeded = 0;
UNLOCK_GC();
if (freeSegs) {
FreeSegments();
}
if (!WEAK_FREELIST_ISEMPTY()) {
EmptyWeakFreeList();
}
}
}
/******************************************************************************/
#ifdef GC_CHECK
static PRInt32 allocationCount;
static void EarthShatteringKaBoom(PRInt32 whichOne) {
long* p = 0;
*p = 0;
}
/* Check a segment of heap memory. Verify that the object memory
hasn't been overwritten (past the end at least) */
static void CheckSegment(GCSeg* sp) {
PRWord h, tix;
PRWord *p, *lastp, *np, *limit;
lastp = p = (PRWord *) sp->base;
limit = (PRWord *) sp->limit;
while (p < limit) {
if (IS_HBIT(sp, p)) {
char *cp, i;
GCBlockEnd* end;
PRWord bytes, requestedBytes;
h = p[0];
tix = GET_TYPEIX(h);
bytes = OBJ_BYTES(h);
np = (PRWord *) ((char *)p + bytes);
if (tix != FREE_MEMORY_TYPEIX) {
PRInt32 test; /* msdev get's fooled without this local */
/* A live object is here. The last word in the object will
contain the objects requestedSize */
end = (GCBlockEnd*)((char*)(p) + bytes - sizeof(GCBlockEnd));
test = end->check;
if (test != PR_BLOCK_END) {
PR_ASSERT(test == PR_BLOCK_END);
}
requestedBytes = end->requestedBytes;
if (requestedBytes >= bytes) EarthShatteringKaBoom(0);
cp = (char*)(p + 1) + requestedBytes;
i = (char) 0xff;
while (cp < (char*)end) {
if (*cp != i) EarthShatteringKaBoom(1);
cp++;
i--;
}
}
lastp = p;
p = np;
} else {
/* Must be a freelist item */
GCFreeChunk *cp = (GCFreeChunk*) p;
if ((PRInt32)cp->chunkSize < (PRInt32)sizeof(GCFreeChunk)) {
EarthShatteringKaBoom(3);
}
lastp = p;
p = (PRWord*) ((char*)p + cp->chunkSize);
}
}
}
static void CheckHeap(void) {
GCSeg *sp = segs;
GCSeg *esp = sp + nsegs;
while (sp < esp) {
CheckSegment(sp);
sp++;
}
}
#endif /* GC_CHECK */
/******************************************************************************/
#ifdef DEBUG
long gc_thrash = -1L;
#endif
/*
** Allocate memory from the GC Heap. Performs garbage collections if
** memory gets tight and grows the heap as needed. May return NULL if
** memory cannot be found.
*/
PR_IMPLEMENT(PRWord GCPTR *)PR_AllocMemory(
PRWord requestedBytes, PRInt32 tix, PRWord flags)
{
PRWord *p;
CollectorType *ct;
PRInt32 bytes;
GCFinal *final = 0;
GCWeak *weak = 0;
int dub = flags & PR_ALLOC_DOUBLE;
PRInt32 objBytes;
#ifdef GC_STATS
PRInt64 allocTime, ldelta;
#endif
if (!allocationEnabled) return NULL;
PR_ASSERT(requestedBytes >= 0);
PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
#ifdef DEBUG
if (_pr_do_a_dump) {
/*
** Collect, pause for a second (lets finalizer run), and then GC
** again.
*/
PR_GC();
PR_Sleep(PR_MicrosecondsToInterval(1000000L));
PR_GC();
PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
_pr_do_a_dump = 0;
}
#endif
#ifdef GC_STATS
allocTime = PR_Now();
#endif
bytes = (PRInt32) requestedBytes;
/*
** Align bytes to a multiple of a PRWord, then add in enough space
** to hold the header word.
**
** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
*/
/* Check for possible overflow of bytes before performing add */
if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
bytes <<= PR_BYTES_PER_WORD_LOG2;
/* Check for possible overflow of bytes before performing add */
if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
bytes += sizeof(PRWord);
/*
* Add in an extra word of memory for double-aligned memory. Some
* percentage of the time this will waste a word of memory (too
* bad). Howver, it makes the allocation logic much simpler and
* faster.
*/
#ifndef IS_64
if (dub) {
/* Check for possible overflow of bytes before performing add */
if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
bytes += PR_BYTES_PER_WORD;
}
#endif
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) {
/* Bloat the allocation a bit so that we can lay down
a check pattern that we will validate */
/* Check for possible overflow of bytes before performing add */
if ((MAX_INT - PR_BYTES_PER_WORD * 3) < bytes ) return NULL;
bytes += PR_BYTES_PER_WORD * 3;
}
#endif
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
if ((MAX_INT - sizeof(GCBlockEnd)) < bytes ) return NULL;
bytes += sizeof(GCBlockEnd);
#endif
PR_ASSERT( bytes < MAX_ALLOC_SIZE );
/*
** Java can ask for objects bigger than MAX_ALLOC_SIZE,
** but it won't get them.
*/
if (bytes >= MAX_ALLOC_SIZE) return NULL;
#ifdef DEBUG
if (gc_thrash == -1L ? (gc_thrash = (long)PR_GetEnv("GC_THRASH")):gc_thrash) PR_GC();
#endif
ct = &_pr_collectorTypes[tix];
if (ct->flags & (_GC_TYPE_FINAL|_GC_TYPE_WEAK)) {
if (0 != ct->gctype.finalize) {
/*
** Allocate a GCFinal struct for this object in advance. Don't put
** it on the pending list until we have allocated the object
*/
final = AllocFinalNode();
if (!final) {
/* XXX THIS IS NOT ACCEPTABLE*/
PR_ASSERT(0);
return 0;
}
}
if (0 != ct->gctype.getWeakLinkOffset) {
/*
** Allocate a GCWeak struct for this object in advance. Don't put
** it on the weak links list until we have allocated the object
*/
weak = AllocWeakNode();
if (!weak) {
/* XXX THIS IS NOT ACCEPTABLE*/
if (0 != final) {
FreeFinalNode(final);
}
PR_ASSERT(0);
return 0;
}
}
}
LOCK_GC();
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) CheckHeap();
allocationCount++;
#endif
/* Check for overflow of maximum size we can handle */
if (bytes > MAX_ALLOC) goto lost;
/* Try default allocation */
p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
if (0 == p) {
#ifdef GC_STATS
LL_SUB(ldelta, PR_Now(), allocTime);
#endif
/* Collect some memory */
_GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
dogc();
PR_ASSERT( GC_IS_LOCKED() );
/* After a collection we check and see if we should grow the
** heap. We grow the heap when the amount of memory free is less
** than a certain percentage of the heap size. We don't check to
** see if the grow succeeded because our fallback strategy in
** either case is to try one more time to allocate. */
if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory)
&& ((_pr_gcData.freeMemory <
((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))
|| (_pr_gcData.freeMemory < bytes))) {
GrowHeap(PR_MAX(bytes, segmentSize));
}
#ifdef GC_STATS
LL_ADD(allocTime, PR_Now(), ldelta);
#endif
/* Try again */
p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
if (0 == p) {
/* Well that lost big time. Memory must be pretty well fragmented */
if (!GrowHeap(PR_MAX(bytes, segmentSize))) goto lost;
p = BinAlloc(tix, bytes, dub);
if (0 == p) goto lost;
}
}
/* Zero out the portion of the object memory that was used by
the GCFreeChunk structure (skip the first word because it
was already overwritten by the gc header word) */
objBytes = OBJ_BYTES(p[0]);
if (objBytes > sizeof(PRWord)) p[1] = 0;
if (objBytes > sizeof(PRWord)*2) p[2] = 0;
if (final) {
_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d) final=0x%x",
p, bytes, final));
final->object = p;
PR_APPEND_LINK(&final->links, &_pr_finalizeableObjects);
} else {
_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d)", p, bytes));
}
if (weak) {
weak->object = p;
PR_APPEND_LINK(&weak->links, &_pr_weakLinks);
}
METER(meter.allocBytes += bytes);
METER(meter.wastedBytes += (bytes - requestedBytes));
UNLOCK_GC();
if (collectorCleanupNeeded) {
CollectorCleanup();
}
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
{
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
end->check = PR_BLOCK_END;
}
#endif
#ifdef GC_STATS
{
PRInt64 now = PR_Now();
double delta;
PRInt32 bin;
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
end->allocTime = allocTime;
LL_SUB(ldelta, now, allocTime);
LL_L2D(delta, ldelta);
InlineBinNumber(bin, requestedBytes);
end->bin = bin;
gcstats[bin].nallocs++;
gcstats[bin].allocTime += delta;
gcstats[bin].allocTimeVariance += delta * delta;
}
#endif
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) {
/* Place a pattern in the memory that was allocated that was not
requested. We will check the pattern later. */
char* cp = (char*)(p + 1) + requestedBytes;
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
char i = (char) 0xff;
while (cp < (char*)end) {
*cp++ = i--;
}
end->requestedBytes = requestedBytes;
CheckHeap();
}
#endif
return p + 1;
lost:
/* Out of memory */
UNLOCK_GC();
if (final) {
FreeFinalNode(final);
}
if (weak) {
FreeWeakNode(weak);
}
if (collectorCleanupNeeded) {
CollectorCleanup();
}
return 0;
}
/* Shortcut allocator for objects that do not require finalization or
are weak objects */
PR_IMPLEMENT(PRWord GCPTR *)
PR_AllocSimpleMemory(PRWord requestedBytes, PRInt32 tix)
{
PRWord *p;
PRInt32 bytes;
PRInt32 objBytes;
#ifdef GC_STATS
PRInt64 allocTime, ldelta;
#endif
if (!allocationEnabled) return NULL;
PR_ASSERT(requestedBytes >= 0);
PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
#ifdef DEBUG
if (_pr_do_a_dump) {
/*
** Collect, pause for a second (lets finalizer run), and then GC
** again.
*/
PR_GC();
PR_Sleep(PR_MicrosecondsToInterval(1000000L));
PR_GC();
PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
_pr_do_a_dump = 0;
}
#endif
#ifdef GC_STATS
allocTime = PR_NowMS();
#endif
bytes = (PRInt32) requestedBytes;
/*
** Align bytes to a multiple of a PRWord, then add in enough space
** to hold the header word.
**
** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
*/
bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
bytes <<= PR_BYTES_PER_WORD_LOG2;
bytes += sizeof(PRWord);
/*
* Add in an extra word of memory for double-aligned memory. Some
* percentage of the time this will waste a word of memory (too
* bad). Howver, it makes the allocation logic much simpler and
* faster.
*/
#ifndef IS_64
bytes += PR_BYTES_PER_WORD;
#endif
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) {
/* Bloat the allocation a bit so that we can lay down
a check pattern that we will validate */
bytes += PR_BYTES_PER_WORD * 2;
}
#endif
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
bytes += sizeof(GCBlockEnd);
#endif
/* Java can ask for objects bigger than 4M, but it won't get them */
/*
* This check was added because there is a fundamental limit of
* the size field maintained by the gc code. Going over the 4M
* limit caused some bits to roll over into another bit field,
* violating the max segment size and causing a bug.
*/
if (bytes >= MAX_ALLOC_SIZE) {
return NULL;
}
#ifdef DEBUG
if (gc_thrash == -1L
? (gc_thrash = (long)PR_GetEnv("GC_THRASH"))
: gc_thrash) {
PR_GC();
}
#endif
LOCK_GC();
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) {
CheckHeap();
}
allocationCount++;
#endif
/* Try default allocation */
if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
p = BigAlloc(tix, bytes, 1);
} else {
p = BinAlloc(tix, bytes, 1);
}
if (0 == p) {
#ifdef GC_STATS
LL_SUB(ldelta, PR_Now(), allocTime);
#endif
/* Collect some memory */
_GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
dogc();
PR_ASSERT( GC_IS_LOCKED() );
/* After a collection we check and see if we should grow the
heap. We grow the heap when the amount of memory free is less
than a certain percentage of the heap size. We don't check to
see if the grow succeeded because our fallback strategy in
either case is to try one more time to allocate. */
if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory) &&
(_pr_gcData.freeMemory <
((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))) {
GrowHeap(PR_MAX(bytes, segmentSize));
}
#ifdef GC_STATS
LL_ADD(allocTime, PR_Now(), ldelta);
#endif
/* Try one last time */
if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
p = BigAlloc(tix, bytes, 1);
} else {
p = BinAlloc(tix, bytes, 1);
}
if (0 == p) {
/* Well that lost big time. Memory must be pretty well fragmented */
if (!GrowHeap(PR_MAX(bytes, segmentSize))) {
goto lost;
}
p = BinAlloc(tix, bytes, 1);
if (0 == p) goto lost;
}
}
/* Zero out the portion of the object memory that was used by
the GCFreeChunk structure (skip the first word because it
was already overwritten by the gc header word) */
objBytes = OBJ_BYTES(p[0]);
if (objBytes > sizeof(PRWord)) p[1] = 0;
if (objBytes > sizeof(PRWord)*2) p[2] = 0;
METER(meter.allocBytes += bytes);
METER(meter.wastedBytes += (bytes - requestedBytes));
UNLOCK_GC();
if (collectorCleanupNeeded) {
CollectorCleanup();
}
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
{
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
end->check = PR_BLOCK_END;
}
#endif
#ifdef GC_STATS
{
PRInt64 now = PR_Now();
double delta;
PRInt32 bin;
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
end->allocTime = allocTime;
LL_SUB(ldelta, now, allocTime);
LL_L2D(delta, ldelta);
InlineBinNumber(bin, requestedBytes);
end->bin = bin;
gcstats[bin].nallocs++;
gcstats[bin].allocTime += delta;
gcstats[bin].allocTimeVariance += delta * delta;
}
#endif
#ifdef GC_CHECK
if (_pr_gcData.flags & GC_CHECK) {
/* Place a pattern in the memory that was allocated that was not
requested. We will check the pattern later. */
char* cp = (char*)(p + 1) + requestedBytes;
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
char i = (char) 0xff;
while (cp < (char*)end) {
*cp++ = i--;
}
end->requestedBytes = requestedBytes;
CheckHeap();
}
#endif
return p + 1;
lost:
/* Out of memory */
UNLOCK_GC();
if (collectorCleanupNeeded) {
CollectorCleanup();
}
return 0;
}
/************************************************************************/
PR_IMPLEMENT(PRWord) PR_GetObjectHeader(void *ptr) {
GCSeg *sp;
PRWord *h;
if (ptr == 0) return 0;
sp = InHeap(ptr);
if (sp == 0) return 0;
h = (PRWord*)FindObject(sp, (PRWord*)ptr);
return GC_GET_USER_BITS(h[0]);
}
PR_IMPLEMENT(PRWord) PR_SetObjectHeader(void *ptr, PRWord newUserBits) {
GCSeg *sp;
PRWord *h, rv;
if (ptr == 0) return 0;
sp = InHeap(ptr);
if