1
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* ***** BEGIN LICENSE BLOCK *****
3
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5
* The contents of this file are subject to the Mozilla Public License Version
6
* 1.1 (the "License"); you may not use this file except in compliance with
7
* the License. You may obtain a copy of the License at
8
* http://www.mozilla.org/MPL/
10
* Software distributed under the License is distributed on an "AS IS" basis,
11
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12
* for the specific language governing rights and limitations under the
15
* The Original Code is the Netscape Portable Runtime (NSPR).
17
* The Initial Developer of the Original Code is
18
* Netscape Communications Corporation.
19
* Portions created by the Initial Developer are Copyright (C) 1998-2000
20
* the Initial Developer. All Rights Reserved.
24
* Alternatively, the contents of this file may be used under the terms of
25
* either the GNU General Public License Version 2 or later (the "GPL"), or
26
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
27
* in which case the provisions of the GPL or the LGPL are applicable instead
28
* of those above. If you wish to allow use of your version of this file only
29
* under the terms of either the GPL or the LGPL, and not to allow others to
30
* use your version of this file under the terms of the MPL, indicate your
31
* decision by deleting the provisions above and replace them with the notice
32
* and other provisions required by the GPL or the LGPL. If you do not delete
33
* the provisions above, a recipient may use your version of this file under
34
* the terms of any one of the MPL, the GPL or the LGPL.
36
* ***** END LICENSE BLOCK ***** */
61
#include "private/pprthred.h"
63
typedef void (*PRFileDumper)(FILE *out, PRBool detailed);
66
PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed);
69
** Mark&sweep garbage collector. Supports objects that require
70
** finalization, objects that can have a single weak link, and special
71
** objects that require care during sweeping.
74
PRLogModuleInfo *_pr_msgc_lm;
77
static PRInt32 _pr_pageShift;
78
static PRInt32 _pr_pageSize;
94
** Make this constant bigger to reduce the amount of recursion during
95
** garbage collection.
97
#define MAX_SCAN_Q 100L
99
#if defined(XP_PC) && !defined(WIN32)
100
#define MAX_SEGS 400L
101
#define MAX_SEGMENT_SIZE (65536L - 4096L)
102
#define SEGMENT_SIZE (65536L - 4096L)
103
#define MAX_ALLOC_SIZE (65536L - 4096L)
105
#define MAX_SEGS 400L
106
#define MAX_SEGMENT_SIZE (2L * 256L * 1024L)
107
#define SEGMENT_SIZE (1L * 256L * 1024L)
108
#define MAX_ALLOC_SIZE (4L * 1024L * 1024L)
112
* The highest value that can fit into a signed integer. This
113
* is used to prevent overflow of allocation size in alloc routines.
116
#define MAX_INT ((1UL << (PR_BITS_PER_INT - 1)) - 1)
119
* On 32-bit machines, only 22 bits are used in the cibx integer to
120
* store size since 8 bits of the integer are used to store type, and
121
* of the remainder, 2 are user defined. Max allocation size = 2^22 -1
124
#define MAX_ALLOC ( (1L << (PR_BYTES_PER_WORD_LOG2 + WORDS_BITS )) -1)
126
/* The minimum percentage of free heap space after a collection. If
127
the amount of free space doesn't meet this criteria then we will
128
attempt to grow the heap */
129
#define MIN_FREE_THRESHOLD_AFTER_GC 20L
131
static PRInt32 segmentSize = SEGMENT_SIZE;
133
static PRInt32 collectorCleanupNeeded;
136
PRUint32 _pr_gcMeter;
138
#define _GC_METER_STATS 0x01L
139
#define _GC_METER_GROWTH 0x02L
140
#define _GC_METER_FREE_LIST 0x04L
143
/************************************************************************/
145
#define LINEAR_BIN_EXPONENT 5
146
#define NUM_LINEAR_BINS ((PRUint32)1 << LINEAR_BIN_EXPONENT)
147
#define FIRST_LOG_BIN (NUM_LINEAR_BINS - LINEAR_BIN_EXPONENT)
149
/* Each free list bin holds a chunk of memory sized from
150
2^n to (2^(n+1))-1 inclusive. */
151
#define NUM_BINS (FIRST_LOG_BIN + 32)
154
* Find the bin number for a given size (in bytes). This does not round up as
155
* values from 2^n to (2^(n+1))-1 share the same bin.
157
#define InlineBinNumber(_bin,_bytes) \
159
PRUint32 _t, _n = (PRUint32) _bytes / 4; \
160
if (_n < NUM_LINEAR_BINS) { \
163
_bin = FIRST_LOG_BIN; \
164
if ((_t = (_n >> 16)) != 0) { _bin += 16; _n = _t; } \
165
if ((_t = (_n >> 8)) != 0) { _bin += 8; _n = _t; } \
166
if ((_t = (_n >> 4)) != 0) { _bin += 4; _n = _t; } \
167
if ((_t = (_n >> 2)) != 0) { _bin += 2; _n = _t; } \
168
if ((_n >> 1) != 0) _bin++; \
172
#define BIG_ALLOC 16384L
174
#define MIN_FREE_CHUNK_BYTES ((PRInt32)sizeof(GCFreeChunk))
176
/* Note: fix code in PR_AllocMemory if you change the size of GCFreeChunk
177
so that it zeros the right number of words */
178
typedef struct GCFreeChunk {
179
struct GCFreeChunk *next;
180
struct GCSeg *segment;
184
typedef struct GCSegInfo {
185
struct GCSegInfo *next;
192
typedef struct GCSeg {
200
typedef struct GCMeter {
203
PRInt32 numFreeChunks;
204
PRInt32 skippedFreeChunks;
206
static GCMeter meter;
210
** There is one of these for each segment of GC'able memory.
212
static GCSeg segs[MAX_SEGS];
213
static GCSegInfo *freeSegs;
214
static GCSeg* lastInHeap;
217
static GCFreeChunk *bins[NUM_BINS];
218
static PRInt32 minBin;
219
static PRInt32 maxBin;
222
** Scan Q used to avoid deep recursion when scanning live objects for
225
typedef struct GCScanQStr {
226
PRWord *q[MAX_SCAN_Q];
230
static GCScanQ *pScanQ;
233
PRInt32 _pr_maxScanDepth;
234
PRInt32 _pr_scanDepth;
238
** Keeps track of the number of bytes allocated via the BigAlloc()
239
** allocator. When the number of bytes allocated, exceeds the
240
** BIG_ALLOC_GC_SIZE, then a GC will occur before the next allocation
243
#define BIG_ALLOC_GC_SIZE (4*SEGMENT_SIZE)
244
static PRWord bigAllocBytes = 0;
247
** There is one GC header word in front of each GC allocated object. We
248
** use it to contain information about the object (what TYPEIX to use for
249
** scanning it, how big it is, it's mark status, and if it's a root).
251
#define TYPEIX_BITS 8L
252
#define WORDS_BITS 20L
253
#define MAX_CBS (1L << GC_TYPEIX_BITS)
254
#define MAX_WORDS (1L << GC_WORDS_BITS)
255
#define TYPEIX_SHIFT 24L
256
#define MAX_TYPEIX ((1L << TYPEIX_BITS) - 1L)
257
#define TYPEIX_MASK PR_BITMASK(TYPEIX_BITS)
258
#define WORDS_SHIFT 2L
259
#define WORDS_MASK PR_BITMASK(WORDS_BITS)
263
/* Two bits per object header are reserved for the user of the memory
264
system to store information into. */
265
#define GC_USER_BITS_SHIFT 22L
266
#define GC_USER_BITS 0x00c00000L
268
#define MAKE_HEADER(_cbix,_words) \
269
((PRWord) (((unsigned long)(_cbix) << TYPEIX_SHIFT) \
270
| ((unsigned long)(_words) << WORDS_SHIFT)))
272
#define GET_TYPEIX(_h) \
273
(((PRUword)(_h) >> TYPEIX_SHIFT) & 0xff)
275
#define MARK(_sp,_p) \
276
(((PRWord *)(_p))[0] |= MARK_BIT)
277
#define IS_MARKED(_sp,_p) \
278
(((PRWord *)(_p))[0] & MARK_BIT)
279
#define OBJ_BYTES(_h) \
280
(((PRInt32) (_h) & 0x003ffffcL) << (PR_BYTES_PER_WORD_LOG2-2L))
282
#define GC_GET_USER_BITS(_h) (((_h) & GC_USER_BITS) >> GC_USER_BITS_SHIFT)
284
/************************************************************************/
287
** Mark the start of an object in a segment. Note that we mark the header
288
** word (which we always have), not the data word (which we may not have
289
** for empty objects).
290
** XXX tune: put subtract of _sp->base into _sp->hbits pointer?
292
#define SET_HBIT(_sp,_ph) \
293
SET_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
295
#define CLEAR_HBIT(_sp,_ph) \
296
CLEAR_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
298
#define IS_HBIT(_sp,_ph) \
299
TEST_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
302
** Given a pointer into this segment, back it up until we are at the
303
** start of the object the pointer points into. Each heap segment has a
304
** bitmap that has one bit for each word of the objects it contains. The
305
** bit's are set for the firstword of an object, and clear for it's other
308
static PRWord *FindObject(GCSeg *sp, PRWord *p)
312
/* Align p to it's proper boundary before we start fiddling with it */
313
p = (PRWord*) ((PRWord)p & ~(PR_BYTES_PER_WORD-1L));
315
base = (PRWord *) sp->base;
317
if (IS_HBIT(sp, p)) {
321
} while ( p >= base );
323
/* Heap is corrupted! */
324
_GCTRACE(GC_TRACE, ("ERROR: The heap is corrupted!!! aborting now!"));
329
/************************************************************************/
330
#if !defined(XP_PC) || defined(XP_OS2)
331
#define OutputDebugString(msg)
334
#define IN_SEGMENT(_sp, _p) \
335
((((char *)(_p)) >= (_sp)->base) && \
336
(((char *)(_p)) < (_sp)->limit))
338
static GCSeg *InHeap(void *p)
342
if (lastInHeap && IN_SEGMENT(lastInHeap, p)) {
348
for (; sp < esp; sp++) {
349
if (IN_SEGMENT(sp, p)) {
358
** Grow the heap by allocating another segment. Fudge the requestedSize
359
** value to try to pre-account for the HBITS.
361
static GCSeg* DoGrowHeap(PRInt32 requestedSize, PRBool exactly)
368
PRInt32 nhbytes, nhbits;
371
if (nsegs == MAX_SEGS) {
372
/* No room for more segments */
376
segInfo = (GCSegInfo*) PR_MALLOC(sizeof(GCSegInfo));
380
sprintf(str, "[1] Allocated %ld bytes at %p\n",
381
(long) sizeof(GCSegInfo), segInfo);
382
OutputDebugString(str);
389
/* Get more memory from the OS */
391
allocSize = requestedSize;
392
base = (char *) PR_MALLOC(requestedSize);
394
allocSize = requestedSize;
395
allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
396
allocSize <<= _pr_pageShift;
397
base = (char*)_MD_GrowGCHeap(&allocSize);
405
(allocSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2);
406
nhbytes = ((nhbits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
409
/* Get bitmap memory from malloc heap */
410
hbits = (PRWord *) PR_CALLOC((PRUint32)nhbytes);
417
/* XXX do something about this */
418
/* _MD_FreeGCSegment(base, allocSize); */
424
** Setup new segment.
427
segInfo->base = sp->base = base;
428
segInfo->limit = sp->limit = base + allocSize;
429
segInfo->hbits = sp->hbits = hbits;
431
segInfo->fromMalloc = exactly;
432
memset(base, 0, allocSize);
435
if (_pr_gcMeter & _GC_METER_GROWTH) {
436
fprintf(stderr, "[GC: new segment base=%p size=%ld]\n",
437
sp->base, (long) allocSize);
441
_pr_gcData.allocMemory += allocSize;
442
_pr_gcData.freeMemory += allocSize;
447
/* Put free memory into a freelist bin */
448
cp = (GCFreeChunk *) base;
450
cp->chunkSize = allocSize;
451
InlineBinNumber(bin, allocSize)
452
cp->next = bins[bin];
454
if (bin < minBin) minBin = bin;
455
if (bin > maxBin) maxBin = bin;
458
** When exactly allocating the entire segment is given over to a
459
** single object to prevent fragmentation
463
if (!_pr_gcData.lowSeg) {
464
_pr_gcData.lowSeg = (PRWord*) sp->base;
465
_pr_gcData.highSeg = (PRWord*) sp->limit;
467
if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
468
_pr_gcData.lowSeg = (PRWord*) sp->base;
470
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
471
_pr_gcData.highSeg = (PRWord*) sp->limit;
476
** Get rid of the GC pointer in case it shows up in some uninitialized
477
** local stack variable later (while scanning the C stack looking for
480
memset(&base, 0, sizeof(base)); /* optimizers beware */
482
PR_LOG(_pr_msgc_lm, PR_LOG_WARNING, ("grow heap: total gc memory now %d",
483
_pr_gcData.allocMemory));
488
#ifdef USE_EXTEND_HEAP
489
static PRBool ExtendHeap(PRInt32 requestedSize) {
492
PRInt32 oldSize, newSize;
493
PRInt32 newHBits, newHBytes;
494
PRInt32 oldHBits, oldHBytes;
499
/* Can't extend nothing */
500
if (nsegs == 0) return PR_FALSE;
502
/* Round up requested size to the size of a page */
503
allocSize = (PRUint32) requestedSize;
504
allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
505
allocSize <<= _pr_pageShift;
507
/* Malloc some memory for the new hbits array */
509
oldSize = sp->limit - sp->base;
510
newSize = oldSize + allocSize;
511
newHBits = (newSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
512
newHBytes = ((newHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
514
hbits = (PRWord*) PR_MALLOC(newHBytes);
515
if (0 == hbits) return PR_FALSE;
517
/* Attempt to extend the last segment by the desired amount */
518
if (_MD_ExtendGCHeap(sp->base, oldSize, newSize)) {
519
oldHBits = (oldSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
520
oldHBytes = ((oldHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
523
/* Copy hbits from old memory into new memory */
524
memset(hbits, 0, newHBytes);
525
memcpy(hbits, sp->hbits, oldHBytes);
526
PR_DELETE(sp->hbits);
527
memset(sp->base + oldSize, 0, allocSize);
529
/* Adjust segment state */
530
sp->limit += allocSize;
532
sp->info->limit = sp->limit;
533
sp->info->hbits = hbits;
535
/* Put free memory into a freelist bin */
536
cp = (GCFreeChunk *) (sp->base + oldSize);
538
cp->chunkSize = allocSize;
539
InlineBinNumber(bin, allocSize)
540
cp->next = bins[bin];
542
if (bin < minBin) minBin = bin;
543
if (bin > maxBin) maxBin = bin;
545
/* Prevent a pointer that points to the free memory from showing
546
up on the call stack later on */
547
memset(&cp, 0, sizeof(cp));
549
/* Update heap brackets and counters */
550
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
551
_pr_gcData.highSeg = (PRWord*) sp->limit;
553
_pr_gcData.allocMemory += allocSize;
554
_pr_gcData.freeMemory += allocSize;
561
#endif /* USE_EXTEND_HEAP */
563
static GCSeg *GrowHeapExactly(PRInt32 requestedSize)
565
GCSeg *sp = DoGrowHeap(requestedSize, PR_TRUE);
569
static PRBool GrowHeap(PRInt32 requestedSize)
572
#ifdef USE_EXTEND_HEAP
573
if (ExtendHeap(requestedSize)) {
577
p = DoGrowHeap(requestedSize, PR_FALSE);
578
return (p != NULL ? PR_TRUE : PR_FALSE);
582
** Release a segment when it is entirely free.
584
static void ShrinkGCHeap(GCSeg *sp)
587
if (_pr_gcMeter & _GC_METER_GROWTH) {
588
fprintf(stderr, "[GC: free segment base=%p size=%ld]\n",
589
sp->base, (long) (sp->limit - sp->base));
594
* Put segment onto free seginfo list (we can't call free right now
595
* because we have the GC lock and all of the other threads are
596
* suspended; if one of them has the malloc lock we would deadlock)
598
sp->info->next = freeSegs;
600
collectorCleanupNeeded = 1;
601
_pr_gcData.allocMemory -= sp->limit - sp->base;
602
if (sp == lastInHeap) lastInHeap = 0;
604
/* Squish out disappearing segment from segment table */
606
if ((sp - segs) != nsegs) {
615
/* Recalculate the lowSeg and highSeg values */
616
_pr_gcData.lowSeg = (PRWord*) segs[0].base;
617
_pr_gcData.highSeg = (PRWord*) segs[0].limit;
618
for (sp = segs; sp < &segs[nsegs]; sp++) {
619
if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
620
_pr_gcData.lowSeg = (PRWord*) sp->base;
622
if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
623
_pr_gcData.highSeg = (PRWord*) sp->limit;
628
static void FreeSegments(void)
632
while (0 != freeSegs) {
644
PR_DELETE(si->hbits);
649
/************************************************************************/
651
void ScanScanQ(GCScanQ *iscan)
656
GCScanQ nextQ, *scan, *next, *temp;
659
if (!iscan->queued) return;
661
_GCTRACE(GC_MARK, ("begin scanQ @ 0x%x (%d)", iscan, iscan->queued));
664
while (scan->queued) {
665
_GCTRACE(GC_MARK, ("continue scanQ @ 0x%x (%d)", scan, scan->queued));
667
* Set pointer to current scanQ so that _pr_gcData.livePointer
673
/* Now scan the scan Q */
675
epp = &scan->q[scan->queued];
679
ct = &_pr_collectorTypes[GET_TYPEIX(p[0])];
680
PR_ASSERT(0 != ct->gctype.scan);
681
/* Scan object ... */
682
(*ct->gctype.scan)(p + 1);
685
/* Exchange pointers so that we scan next */
692
PR_ASSERT(nextQ.queued == 0);
693
PR_ASSERT(iscan->queued == 0);
697
** Called during root finding step to identify "root" pointers into the
698
** GC heap. First validate if it is a real heap pointer and then mark the
699
** object being pointed to and add it to the scan Q for eventual
702
static void PR_CALLBACK ProcessRootBlock(void **base, PRInt32 count)
705
PRWord *p0, *p, h, tix, *low, *high, *segBase;
711
low = _pr_gcData.lowSeg;
712
high = _pr_gcData.highSeg;
713
while (--count >= 0) {
714
p0 = (PRWord*) *base++;
715
if (p0 < low) continue; /* below gc heap */
716
if (p0 >= high) continue; /* above gc heap */
717
/* NOTE: inline expansion of InHeap */
720
if (!sp || !IN_SEGMENT(sp,p0)) {
724
for (; sp < esp; sp++) {
725
if (IN_SEGMENT(sp, p0)) {
734
/* NOTE: Inline expansion of FindObject */
735
/* Align p to it's proper boundary before we start fiddling with it */
736
p = (PRWord*) ((PRWord)p0 & ~(PR_BYTES_PER_WORD-1L));
737
segBase = (PRWord *) sp->base;
739
if (IS_HBIT(sp, p)) {
743
} while (p >= segBase);
746
** We have a pointer into the heap, but it has no header
747
** bit. This means that somehow the very first object in the heap
748
** doesn't have a header. This is impossible so when debugging
757
if ((h & MARK_BIT) == 0) {
760
("root 0x%p (%d) base0=%p off=%d",
761
p, OBJ_BYTES(h), base0, (base-1) - base0));
764
/* Mark the root we just found */
768
* See if object we just found needs scanning. It must
769
* have a scan function to be placed on the scanQ.
771
tix = (PRWord)GET_TYPEIX(h);
772
ct = &_pr_collectorTypes[tix];
773
if (0 == ct->gctype.scan) {
778
** Put a pointer onto the scan Q. We use the scan Q to avoid
779
** deep recursion on the C call stack. Objects are added to
780
** the scan Q until the scan Q fills up. At that point we
781
** make a call to ScanScanQ which proceeds to scan each of
782
** the objects in the Q. This limits the recursion level by a
783
** large amount though the stack frames get larger to hold
786
pScanQ->q[pScanQ->queued++] = p;
787
if (pScanQ->queued == MAX_SCAN_Q) {
788
METER(_pr_scanDepth++);
795
static void PR_CALLBACK ProcessRootPointer(void *ptr)
797
PRWord *p0, *p, h, tix, *segBase;
803
if (p0 < _pr_gcData.lowSeg) return; /* below gc heap */
804
if (p0 >= _pr_gcData.highSeg) return; /* above gc heap */
806
/* NOTE: inline expansion of InHeap */
809
if (!sp || !IN_SEGMENT(sp,p0)) {
813
for (; sp < esp; sp++) {
814
if (IN_SEGMENT(sp, p0)) {
823
/* NOTE: Inline expansion of FindObject */
824
/* Align p to it's proper boundary before we start fiddling with it */
825
p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
826
segBase = (PRWord *) sp->base;
828
if (IS_HBIT(sp, p)) {
832
} while (p >= segBase);
835
** We have a pointer into the heap, but it has no header
836
** bit. This means that somehow the very first object in the heap
837
** doesn't have a header. This is impossible so when debugging
846
if ((h & MARK_BIT) == 0) {
848
_GCTRACE(GC_ROOTS, ("root 0x%p (%d)", p, OBJ_BYTES(h)));
851
/* Mark the root we just found */
855
* See if object we just found needs scanning. It must
856
* have a scan function to be placed on the scanQ.
858
tix = (PRWord)GET_TYPEIX(h);
859
ct = &_pr_collectorTypes[tix];
860
if (0 == ct->gctype.scan) {
865
** Put a pointer onto the scan Q. We use the scan Q to avoid
866
** deep recursion on the C call stack. Objects are added to
867
** the scan Q until the scan Q fills up. At that point we
868
** make a call to ScanScanQ which proceeds to scan each of
869
** the objects in the Q. This limits the recursion level by a
870
** large amount though the stack frames get larger to hold
873
pScanQ->q[pScanQ->queued++] = p;
874
if (pScanQ->queued == MAX_SCAN_Q) {
875
METER(_pr_scanDepth++);
881
/************************************************************************/
884
** Empty the freelist for each segment. This is done to make sure that
885
** the root finding step works properly (otherwise, if we had a pointer
886
** into a free section, we might not find its header word and abort in
889
static void EmptyFreelists(void)
899
** Run over the freelist and make all of the free chunks look like
902
for (bin = 0; bin <= NUM_BINS-1; bin++) {
907
chunkSize = cp->chunkSize >> BYTES_PER_WORD_LOG2;
909
PR_ASSERT(chunkSize != 0);
910
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
916
minBin = NUM_BINS - 1;
920
typedef struct GCBlockEnd {
923
PRInt32 requestedBytes;
930
PRInt32 traceGeneration;
934
#define PR_BLOCK_END 0xDEADBEEF
936
/************************************************************************/
940
typedef struct GCStat {
943
double allocTimeVariance;
946
double lifetimeVariance;
949
#define GCSTAT_BINS NUM_BINS
951
GCStat gcstats[GCSTAT_BINS];
953
#define GCLTFREQ_BINS NUM_BINS
955
PRInt32 gcltfreq[GCSTAT_BINS][GCLTFREQ_BINS];
960
pr_GetSizeString(PRUint32 size)
964
sizeStr = PR_smprintf("<= %ld", size);
965
else if (size < 1024 * 1024)
966
sizeStr = PR_smprintf("<= %ldk", size / 1024);
968
sizeStr = PR_smprintf("<= %ldM", size / (1024 * 1024));
973
pr_FreeSizeString(char *sizestr)
975
PR_smprintf_free(sizestr);
980
pr_PrintGCAllocStats(FILE* out)
983
_PR_DebugPrint(out, "\n--Allocation-Stats-----------------------------------------------------------");
984
_PR_DebugPrint(out, "\n--Obj-Size----Count-----Avg-Alloc-Time-----------Avg-Lifetime---------%%Freed-\n");
985
for (i = 0; i < GCSTAT_BINS; i++) {
986
GCStat stat = gcstats[i];
987
double allocTimeMean = 0.0, allocTimeVariance = 0.0, lifetimeMean = 0.0, lifetimeVariance = 0.0;
988
PRUint32 maxSize = (1 << i);
990
if (stat.nallocs != 0.0) {
991
allocTimeMean = stat.allocTime / stat.nallocs;
992
allocTimeVariance = fabs(stat.allocTimeVariance / stat.nallocs - allocTimeMean * allocTimeMean);
994
if (stat.nfrees != 0.0) {
995
lifetimeMean = stat.lifetime / stat.nfrees;
996
lifetimeVariance = fabs(stat.lifetimeVariance / stat.nfrees - lifetimeMean * lifetimeMean);
998
sizeStr = pr_GetSizeString(maxSize);
999
_PR_DebugPrint(out, "%10s %8lu %10.3f +- %10.3f %10.3f +- %10.3f (%2ld%%)\n",
1000
sizeStr, stat.nallocs,
1001
allocTimeMean, sqrt(allocTimeVariance),
1002
lifetimeMean, sqrt(lifetimeVariance),
1003
(stat.nallocs ? (stat.nfrees * 100 / stat.nallocs) : 0));
1004
pr_FreeSizeString(sizeStr);
1006
_PR_DebugPrint(out, "--Lifetime-Frequency-Counts----------------------------------------------------\n");
1007
_PR_DebugPrint(out, "size\\cnt");
1008
for (j = 0; j < GCLTFREQ_BINS; j++) {
1009
_PR_DebugPrint(out, "\t%lu", j);
1011
_PR_DebugPrint(out, "\n");
1012
for (i = 0; i < GCSTAT_BINS; i++) {
1013
PRInt32* freqs = gcltfreq[i];
1014
_PR_DebugPrint(out, "%lu", (1 << i));
1015
for (j = 0; j < GCLTFREQ_BINS; j++) {
1016
_PR_DebugPrint(out, "\t%lu", freqs[j]);
1018
_PR_DebugPrint(out, "\n");
1020
_PR_DebugPrint(out, "-------------------------------------------------------------------------------\n");
1024
PR_PrintGCAllocStats(void)
1026
pr_PrintGCAllocStats(stderr);
1029
#endif /* GC_STATS */
1031
/************************************************************************/
1034
** Sweep a segment, cleaning up all of the debris. Coallese the debris
1035
** into GCFreeChunk's which are added to the freelist bins.
1037
static PRBool SweepSegment(GCSeg *sp)
1044
PRInt32 bytes, chunkSize, segmentSize, totalFree;
1049
** Now scan over the segment's memory in memory order, coallescing
1050
** all of the debris into a FreeChunk list.
1053
segmentSize = sp->limit - sp->base;
1054
p = (PRWord *) sp->base;
1055
limit = (PRWord *) sp->limit;
1056
PR_ASSERT(segmentSize > 0);
1059
cp = (GCFreeChunk *) p;
1061
/* Attempt to coallesce any neighboring free objects */
1063
PR_ASSERT(IS_HBIT(sp, p) != 0);
1065
bytes = OBJ_BYTES(h);
1066
PR_ASSERT(bytes != 0);
1067
np = (PRWord *) ((char *)p + bytes);
1068
tix = (PRWord)GET_TYPEIX(h);
1069
if ((h & MARK_BIT) && (tix != FREE_MEMORY_TYPEIX)) {
1071
if (tix != FREE_MEMORY_TYPEIX) {
1072
PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
1075
p[0] = h & ~(MARK_BIT|FINAL_BIT);
1076
_GCTRACE(GC_SWEEP, ("busy 0x%x (%d)", p, bytes));
1079
_GCTRACE(GC_SWEEP, ("free 0x%x (%d)", p, bytes));
1081
/* Found a free object */
1084
PRInt32 userSize = bytes - sizeof(GCBlockEnd);
1085
GCBlockEnd* end = (GCBlockEnd*)((char*)p + userSize);
1086
if (userSize >= 0 && end->check == PR_BLOCK_END) {
1087
PRInt64 now = PR_Now();
1091
delta = nowd - end->allocTime;
1092
gcstats[end->bin].nfrees++;
1093
gcstats[end->bin].lifetime += delta;
1094
gcstats[end->bin].lifetimeVariance += delta * delta;
1096
InlineBinNumber(freq, delta);
1097
gcltfreq[end->bin][freq]++;
1104
ct = &_pr_collectorTypes[tix];
1105
if (0 != ct->gctype.free) {
1106
(*ct->gctype.free)(p + 1);
1108
chunkSize = chunkSize + bytes;
1110
/* Found the end of heap */
1113
PR_ASSERT(np < limit);
1118
_GCTRACE(GC_SWEEP, ("free chunk 0x%p to 0x%p (%d)",
1119
cp, (char*)cp + chunkSize - 1, chunkSize));
1120
if (chunkSize < MIN_FREE_CHUNK_BYTES) {
1121
/* Lost a tiny fragment until (maybe) next time */
1122
METER(meter.wastedBytes += chunkSize);
1124
chunkSize >>= BYTES_PER_WORD_LOG2;
1125
PR_ASSERT(chunkSize != 0);
1126
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
1129
/* See if the chunk constitutes the entire segment */
1130
if (chunkSize == segmentSize) {
1131
/* Free up the segment right now */
1132
if (sp->info->fromMalloc) {
1138
/* Put free chunk into the appropriate bin */
1140
cp->chunkSize = chunkSize;
1141
InlineBinNumber(bin, chunkSize)
1142
cp->next = bins[bin];
1144
if (bin < minBin) minBin = bin;
1145
if (bin > maxBin) maxBin = bin;
1147
/* Zero swept memory now */
1148
memset(cp+1, 0, chunkSize - sizeof(*cp));
1149
METER(meter.numFreeChunks++);
1150
totalFree += chunkSize;
1154
/* Advance to next object */
1158
PR_ASSERT(totalFree <= segmentSize);
1160
_pr_gcData.freeMemory += totalFree;
1161
_pr_gcData.busyMemory += (sp->limit - sp->base) - totalFree;
1165
/************************************************************************/
1167
/* This is a list of all the objects that are finalizable. This is not
1168
the list of objects that are awaiting finalization because they
1169
have been collected. */
1170
PRCList _pr_finalizeableObjects;
1172
/* This is the list of objects that are awaiting finalization because
1173
they have been collected. */
1174
PRCList _pr_finalQueue;
1176
/* Each object that requires finalization has one of these objects
1177
allocated as well. The GCFinal objects are put on the
1178
_pr_finalizeableObjects list until the object is collected at which
1179
point the GCFinal object is moved to the _pr_finalQueue */
1180
typedef struct GCFinalStr {
1185
/* Find pointer to GCFinal struct from the list linkaged embedded in it */
1186
#define FinalPtr(_qp) \
1187
((GCFinal*) ((char*) (_qp) - offsetof(GCFinal,links)))
1189
static GCFinal *AllocFinalNode(void)
1191
return PR_NEWZAP(GCFinal);
1194
static void FreeFinalNode(GCFinal *node)
1200
** Prepare for finalization. At this point in the GC cycle we have
1201
** identified all of the live objects. For each object on the
1202
** _pr_finalizeableObjects list see if the object is alive or dead. If
1203
** it's dead, resurrect it and move it from the _pr_finalizeableObjects
1204
** list to the _pr_finalQueue (object's only get finalized once).
1206
** Once _pr_finalizeableObjects has been processed we can finish the
1207
** GC and free up memory and release the threading lock. After that we
1208
** can invoke the finalization procs for each object that is on the
1211
static void PrepareFinalize(void)
1217
void (PR_CALLBACK *livePointer)(void *ptr);
1222
/* This must be done under the same lock that the finalizer uses */
1223
PR_ASSERT( GC_IS_LOCKED() );
1225
/* cache this ptr */
1226
livePointer = _pr_gcData.livePointer;
1229
* Pass #1: Identify objects that are to be finalized, set their
1232
qp = _pr_finalizeableObjects.next;
1233
while (qp != &_pr_finalizeableObjects) {
1236
h = fp->object[0]; /* Grab header word */
1238
/* Object is already alive */
1243
ct = &_pr_collectorTypes[GET_TYPEIX(h)];
1244
PR_ASSERT((0 != ct->flags) && (0 != ct->gctype.finalize));
1246
fp->object[0] |= FINAL_BIT;
1247
_GCTRACE(GC_FINAL, ("moving %p (%d) to finalQueue",
1248
fp->object, OBJ_BYTES(h)));
1252
* Pass #2: For each object that is going to be finalized, move it to
1253
* the finalization queue and resurrect it
1255
qp = _pr_finalizeableObjects.next;
1256
while (qp != &_pr_finalizeableObjects) {
1259
h = fp->object[0]; /* Grab header word */
1260
if ((h & FINAL_BIT) == 0) {
1264
/* Resurrect the object and any objects it refers to */
1267
PR_REMOVE_LINK(&fp->links);
1268
PR_APPEND_LINK(&fp->links, &_pr_finalQueue);
1273
** Scan the finalQ, marking each and every object on it live. This is
1274
** necessary because we might do a GC before objects that are on the
1275
** final queue get finalized. Since there are no other references
1276
** (otherwise they would be on the final queue), we have to scan them.
1277
** This really only does work if we call the GC before the finalizer
1278
** has a chance to do its job.
1280
extern void PR_CALLBACK _PR_ScanFinalQueue(void *notused)
1285
void ( PR_CALLBACK *livePointer)(void *ptr);
1287
livePointer = _pr_gcData.livePointer;
1288
qp = _pr_finalQueue.next;
1289
while (qp != &_pr_finalQueue) {
1291
_GCTRACE(GC_FINAL, ("marking 0x%x (on final queue)", fp->object));
1298
void PR_CALLBACK FinalizerLoop(void* unused)
1307
p = 0; h = 0; /* don't let the gc find these pointers */
1308
while (PR_CLIST_IS_EMPTY(&_pr_finalQueue))
1309
PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
1311
_GCTRACE(GC_FINAL, ("begin finalization"));
1312
while (_pr_finalQueue.next != &_pr_finalQueue) {
1313
fp = FinalPtr(_pr_finalQueue.next);
1314
PR_REMOVE_LINK(&fp->links);
1317
h = p[0]; /* Grab header word */
1318
tix = (PRWord)GET_TYPEIX(h);
1319
ct = &_pr_collectorTypes[tix];
1320
_GCTRACE(GC_FINAL, ("finalize 0x%x (%d)", p, OBJ_BYTES(h)));
1323
** Give up the GC lock so that other threads can allocate memory
1324
** while this finalization method is running. Get it back
1325
** afterwards so that the list remains thread safe.
1329
PR_ASSERT(ct->gctype.finalize != 0);
1330
(*ct->gctype.finalize)(p + 1);
1333
_GCTRACE(GC_FINAL, ("end finalization"));
1334
PR_Notify(_pr_gcData.lock);
1338
static void NotifyFinalizer(void)
1340
if (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
1341
PR_ASSERT( GC_IS_LOCKED() );
1342
PR_Notify(_pr_gcData.lock);
1346
void _PR_CreateFinalizer(PRThreadScope scope)
1348
if (!_pr_gcData.finalizer) {
1349
_pr_gcData.finalizer = PR_CreateThreadGCAble(PR_SYSTEM_THREAD,
1351
PR_PRIORITY_LOW, scope,
1352
PR_UNJOINABLE_THREAD, 0);
1354
if (_pr_gcData.finalizer == NULL)
1355
/* We are doomed if we can't start the finalizer */
1361
void pr_FinalizeOnExit(void)
1364
OutputDebugString("### Doing finalize-on-exit pass\n");
1368
OutputDebugString("### Finalize-on-exit complete. Dumping object left to memory.out\n");
1369
PR_DumpMemorySummary();
1370
PR_DumpMemory(PR_TRUE);
1374
PR_IMPLEMENT(void) PR_ForceFinalize()
1378
while (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
1379
PR_ASSERT( GC_IS_LOCKED() );
1380
(void) PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
1384
/* XXX I don't know how to make it wait (yet) */
1387
/************************************************************************/
1389
typedef struct GCWeakStr {
1395
** Find pointer to GCWeak struct from the list linkaged embedded in it
1397
#define WeakPtr(_qp) \
1398
((GCWeak*) ((char*) (_qp) - offsetof(GCWeak,links)))
1400
PRCList _pr_weakLinks = PR_INIT_STATIC_CLIST(&_pr_weakLinks);
1401
PRCList _pr_freeWeakLinks = PR_INIT_STATIC_CLIST(&_pr_freeWeakLinks);
1403
#define WEAK_FREELIST_ISEMPTY() (_pr_freeWeakLinks.next == &_pr_freeWeakLinks)
1406
* Keep objects referred to by weak free list alive until they can be
1409
static void PR_CALLBACK ScanWeakFreeList(void *notused) {
1410
PRCList *qp = _pr_freeWeakLinks.next;
1411
while (qp != &_pr_freeWeakLinks) {
1412
GCWeak *wp = WeakPtr(qp);
1414
ProcessRootPointer(wp->object);
1419
* Empty the list of weak objects. Note that we can't call malloc/free
1420
* under the cover of the GC's lock (we might deadlock), so transfer the
1421
* list of free objects to a local list under the cover of the lock, then
1422
* release the lock and free up the memory.
1424
static void EmptyWeakFreeList(void) {
1425
if (!WEAK_FREELIST_ISEMPTY()) {
1426
PRCList *qp, freeLinks;
1428
PR_INIT_CLIST(&freeLinks);
1431
* Transfer list of free weak links from the global list to a
1435
qp = _pr_freeWeakLinks.next;
1436
while (qp != &_pr_freeWeakLinks) {
1437
GCWeak *wp = WeakPtr(qp);
1439
PR_REMOVE_LINK(&wp->links);
1440
PR_APPEND_LINK(&wp->links, &freeLinks);
1444
/* Free up storage now */
1445
qp = freeLinks.next;
1446
while (qp != &freeLinks) {
1447
GCWeak *wp = WeakPtr(qp);
1455
* Allocate a new weak node in the weak objects list
1457
static GCWeak *AllocWeakNode(void)
1459
EmptyWeakFreeList();
1460
return PR_NEWZAP(GCWeak);
1463
static void FreeWeakNode(GCWeak *node)
1469
* Check the weak links for validity. Note that the list of weak links is
1470
* itself weak (otherwise we would keep the objects with weak links in
1471
* them alive forever). As we scan the list check the weak link object
1472
* itself and if it's not marked then remove it from the weak link list
1474
static void CheckWeakLinks(void) {
1477
PRWord *p, h, tix, **weakPtrAddress;
1481
qp = _pr_weakLinks.next;
1482
while (qp != &_pr_weakLinks) {
1485
if ((p = wp->object) != 0) {
1486
h = p[0]; /* Grab header word */
1487
if ((h & MARK_BIT) == 0) {
1489
* The object that has a weak link is no longer being
1490
* referenced; remove it from the chain and let it get
1491
* swept away by the GC. Transfer it to the list of
1492
* free weak links for later freeing.
1494
PR_REMOVE_LINK(&wp->links);
1495
PR_APPEND_LINK(&wp->links, &_pr_freeWeakLinks);
1496
collectorCleanupNeeded = 1;
1500
/* Examine a live object that contains weak links */
1501
tix = GET_TYPEIX(h);
1502
ct = &_pr_collectorTypes[tix];
1503
PR_ASSERT((ct->flags != 0) && (ct->gctype.getWeakLinkOffset != 0));
1504
if (0 == ct->gctype.getWeakLinkOffset) {
1505
/* Heap is probably corrupted */
1509
/* Get offset into the object of where the weak pointer is */
1510
offset = (*ct->gctype.getWeakLinkOffset)(p + 1);
1512
/* Check the weak pointer */
1513
weakPtrAddress = (PRWord**)((char*)(p + 1) + offset);
1514
p = *weakPtrAddress;
1516
h = p[-1]; /* Grab header word for pointed to object */
1518
/* Object can't be dead */
1521
/* Break weak link to an object that is about to be swept */
1522
*weakPtrAddress = 0;
1528
/************************************************************************/
1531
** Perform a complete garbage collection
1534
extern GCLockHook *_pr_GCLockHook;
1536
static void dogc(void)
1543
PRInt64 start, end, diff;
1545
#if defined(GCMETER) || defined(GCTIMINGHOOK)
1550
** Stop all of the other threads. This also promises to capture the
1551
** register state of each and every thread
1555
** Get all the locks that will be need during GC after SuspendAll. We
1556
** cannot make any locking/library calls after SuspendAll.
1558
if (_pr_GCLockHook) {
1559
for (lhook = _pr_GCLockHook->next; lhook != _pr_GCLockHook;
1560
lhook = lhook->next) {
1561
(*lhook->func)(PR_GCBEGIN, lhook->arg);
1568
/* Reset meter info */
1569
if (_pr_gcMeter & _GC_METER_STATS) {
1571
"[GCSTATS: busy:%ld skipped:%ld, alloced:%ld+wasted:%ld+free:%ld = total:%ld]\n",
1572
(long) _pr_gcData.busyMemory,
1573
(long) meter.skippedFreeChunks,
1574
(long) meter.allocBytes,
1575
(long) meter.wastedBytes,
1576
(long) _pr_gcData.freeMemory,
1577
(long) _pr_gcData.allocMemory);
1579
memset(&meter, 0, sizeof(meter));
1582
PR_LOG(_pr_msgc_lm, PR_LOG_ALWAYS, ("begin mark phase; busy=%d free=%d total=%d",
1583
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
1584
_pr_gcData.allocMemory));
1586
if (_pr_beginGCHook) {
1587
(*_pr_beginGCHook)(_pr_beginGCHookArg);
1591
** Initialize scanQ to all zero's so that root finder doesn't walk
1594
memset(&scanQ, 0, sizeof(scanQ));
1597
/******************************************/
1603
PR_LOG(_pr_msgc_lm, PR_LOG_WARNING,
1604
("begin mark phase; busy=%d free=%d total=%d",
1605
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
1606
_pr_gcData.allocMemory));
1607
METER(_pr_scanDepth = 0);
1608
rf = _pr_rootFinders;
1610
_GCTRACE(GC_ROOTS, ("finding roots in %s", rf->name));
1611
(*rf->func)(rf->arg);
1614
_GCTRACE(GC_ROOTS, ("done finding roots"));
1616
/* Scan remaining object's that need scanning */
1618
PR_ASSERT(pScanQ == &scanQ);
1619
PR_ASSERT(scanQ.queued == 0);
1621
if (_pr_scanDepth > _pr_maxScanDepth) {
1622
_pr_maxScanDepth = _pr_scanDepth;
1626
/******************************************/
1627
/* FINALIZATION PHASE */
1629
METER(_pr_scanDepth = 0);
1632
/* Scan any resurrected objects found during finalization */
1634
PR_ASSERT(pScanQ == &scanQ);
1635
PR_ASSERT(scanQ.queued == 0);
1637
if (_pr_scanDepth > _pr_maxScanDepth) {
1638
_pr_maxScanDepth = _pr_scanDepth;
1643
/******************************************/
1647
** Sweep each segment clean. While we are at it, figure out which
1648
** segment has the most free space and make that the current segment.
1651
_GCTRACE(GC_SWEEP, ("begin sweep phase"));
1652
_pr_gcData.freeMemory = 0;
1653
_pr_gcData.busyMemory = 0;
1657
if (SweepSegment(sp)) {
1659
** Segment is now free and has been replaced with a different
1668
#if defined(GCMETER) || defined(GCTIMINGHOOK)
1672
LL_SUB(diff, end, start);
1673
PR_LOG(GC, PR_LOG_ALWAYS,
1674
("done; busy=%d free=%d chunks=%d total=%d time=%lldms",
1675
_pr_gcData.busyMemory, _pr_gcData.freeMemory,
1676
meter.numFreeChunks, _pr_gcData.allocMemory, diff));
1677
if (_pr_gcMeter & _GC_METER_FREE_LIST) {
1679
fprintf(stderr, "Freelist bins:\n");
1680
for (bin = 0; bin < NUM_BINS; bin++) {
1681
GCFreeChunk *cp = bins[bin];
1682
while (cp != NULL) {
1683
fprintf(stderr, "%3d: %p %8ld\n",
1684
bin, cp, (long) cp->chunkSize);
1691
if (_pr_endGCHook) {
1692
(*_pr_endGCHook)(_pr_endGCHookArg);
1695
/* clear the running total of the bytes allocated via BigAlloc() */
1698
/* And resume multi-threading */
1701
if (_pr_GCLockHook) {
1702
for (lhook = _pr_GCLockHook->prev; lhook != _pr_GCLockHook;
1703
lhook = lhook->prev) {
1704
(*lhook->func)(PR_GCEND, lhook->arg);
1708
/* Kick finalizer */
1711
if (_pr_gcData.gcTimingHook) {
1713
LL_SUB(diff, end, start);
1715
_pr_gcData.gcTimingHook(time);
1720
PR_IMPLEMENT(void) PR_GC(void)
1726
EmptyWeakFreeList();
1729
/*******************************************************************************
1731
******************************************************************************/
1734
** This is yet another disgusting copy of the body of ProcessRootPointer
1735
** (the other being ProcessRootBlock), but we're not leveraging a single
1736
** function in their cases in interest of performance (avoiding the function
1739
static PRInt32 PR_CALLBACK
1740
pr_ConservativeWalkPointer(void* ptr, PRWalkFun walkRootPointer, void* data)
1742
PRWord *p0, *p, *segBase;
1747
if (p0 < _pr_gcData.lowSeg) return 0; /* below gc heap */
1748
if (p0 >= _pr_gcData.highSeg) return 0; /* above gc heap */
1750
/* NOTE: inline expansion of InHeap */
1753
if (!sp || !IN_SEGMENT(sp,p0)) {
1757
for (; sp < esp; sp++) {
1758
if (IN_SEGMENT(sp, p0)) {
1767
/* NOTE: Inline expansion of FindObject */
1768
/* Align p to it's proper boundary before we start fiddling with it */
1769
p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
1770
segBase = (PRWord *) sp->base;
1772
if (IS_HBIT(sp, p)) {
1776
} while (p >= segBase);
1779
** We have a pointer into the heap, but it has no header
1780
** bit. This means that somehow the very first object in the heap
1781
** doesn't have a header. This is impossible so when debugging
1790
return walkRootPointer(p, data);
1793
static PRInt32 PR_CALLBACK
1794
pr_ConservativeWalkBlock(void **base, PRInt32 count,
1795
PRWalkFun walkRootPointer, void* data)
1798
while (--count >= 0) {
1800
p0 = (PRWord*) *base++;
1801
status = pr_ConservativeWalkPointer(p0, walkRootPointer, data);
1802
if (status) return status;
1807
/******************************************************************************/
1809
typedef void (*WalkObject_t)(FILE *out, GCType* tp, PRWord *obj,
1810
size_t bytes, PRBool detailed);
1811
typedef void (*WalkUnknown_t)(FILE *out, GCType* tp, PRWord tix, PRWord *p,
1812
size_t bytes, PRBool detailed);
1813
typedef void (*WalkFree_t)(FILE *out, PRWord *p, size_t size, PRBool detailed);
1814
typedef void (*WalkSegment_t)(FILE *out, GCSeg* sp, PRBool detailed);
1817
pr_WalkSegment(FILE* out, GCSeg* sp, PRBool detailed,
1818
char* enterMsg, char* exitMsg,
1819
WalkObject_t walkObject, WalkUnknown_t walkUnknown, WalkFree_t walkFree)
1823
p = (PRWord *) sp->base;
1824
limit = (PRWord *) sp->limit;
1826
fprintf(out, enterMsg, p);
1829
if (IS_HBIT(sp, p)) /* Is this an object header? */
1832
PRWord tix = GET_TYPEIX(h);
1833
size_t bytes = OBJ_BYTES(h);
1834
PRWord* np = (PRWord*) ((char*)p + bytes);
1836
GCType* tp = &_pr_collectorTypes[tix].gctype;
1837
if ((0 != tp) && walkObject)
1838
walkObject(out, tp, p, bytes, detailed);
1839
else if (walkUnknown)
1840
walkUnknown(out, tp, tix, p, bytes, detailed);
1845
/* Must be a freelist item */
1846
size_t size = ((GCFreeChunk*)p)->chunkSize;
1848
walkFree(out, p, size, detailed);
1849
p = (PRWord*)((char*)p + size);
1853
fprintf(out, "SEGMENT OVERRUN (end should be at 0x%p)\n", limit);
1855
fprintf(out, exitMsg, p);
1859
pr_WalkSegments(FILE *out, WalkSegment_t walkSegment, PRBool detailed)
1868
walkSegment(out, sp, detailed);
1871
fprintf(out, "End of heap\n");
1875
/*******************************************************************************
1877
******************************************************************************/
1880
PR_DumpIndent(FILE *out, int indent)
1882
while (--indent >= 0)
1887
PR_DumpHexWords(FILE *out, PRWord *p, int nWords,
1888
int indent, int nWordsPerLine)
1894
PR_DumpIndent(out, indent);
1901
fprintf(out, "0x%.8lX", (long) *p++);
1909
static void PR_CALLBACK
1910
pr_DumpObject(FILE *out, GCType* tp, PRWord *p,
1911
size_t bytes, PRBool detailed)
1913
char kindChar = tp->kindChar;
1914
fprintf(out, "0x%p: 0x%.6lX %c ",
1915
p, (long) bytes, kindChar ? kindChar : '?');
1917
(*tp->dump)(out, (void*) (p + 1), detailed, 0);
1919
PR_DumpHexWords(out, p, bytes>>2, 22, 4);
1922
static void PR_CALLBACK
1923
pr_DumpUnknown(FILE *out, GCType* tp, PRWord tix, PRWord *p,
1924
size_t bytes, PRBool detailed)
1926
char kindChar = tp->kindChar;
1927
fprintf(out, "0x%p: 0x%.6lX %c ",
1928
p, (long) bytes, kindChar ? kindChar : '?');
1929
fprintf(out, "UNKNOWN KIND %ld\n", (long) tix);
1931
PR_DumpHexWords(out, p, bytes>>2, 22, 4);
1934
static void PR_CALLBACK
1935
pr_DumpFree(FILE *out, PRWord *p, size_t size, PRBool detailed)
1937
fprintf(out, "0x%p: 0x%.6lX - FREE\n", p, (long) size);
1940
static void PR_CALLBACK
1941
pr_DumpSegment(FILE* out, GCSeg* sp, PRBool detailed)
1943
pr_WalkSegment(out, sp, detailed,
1944
"\n Address: Length\n0x%p: Beginning of segment\n",
1945
"0x%p: End of segment\n\n",
1946
pr_DumpObject, pr_DumpUnknown, pr_DumpFree);
1949
static void pr_DumpRoots(FILE *out);
1952
** Dump out the GC heap.
1955
PR_DumpGCHeap(FILE *out, PRBool detailed)
1959
" U unscanned block\n"
1960
" W weak link block\n"
1961
" S scanned block\n"
1962
" F scanned and final block\n"
1964
" X context record\n"
1965
" - free list item\n"
1968
pr_WalkSegments(out, pr_DumpSegment, detailed);
1975
PR_DumpMemory(PRBool detailed)
1977
PR_DumpToFile("memory.out", "Dumping memory", PR_DumpGCHeap, detailed);
1980
/******************************************************************************/
1982
static PRInt32 PR_CALLBACK
1983
pr_DumpRootPointer(PRWord* p, void* data)
1986
PRWord tix = GET_TYPEIX(h);
1987
size_t bytes = OBJ_BYTES(h);
1989
GCType* tp = &_pr_collectorTypes[tix].gctype;
1991
pr_DumpObject(_pr_gcData.dumpOutput, tp, p, bytes, PR_FALSE);
1993
pr_DumpUnknown(_pr_gcData.dumpOutput, tp, tix, p, bytes, PR_FALSE);
1997
static void PR_CALLBACK
1998
pr_ConservativeDumpRootPointer(void* ptr)
2000
(void)pr_ConservativeWalkPointer(ptr, (PRWalkFun) pr_DumpRootPointer, NULL);
2003
static void PR_CALLBACK
2004
pr_ConservativeDumpRootBlock(void **base, PRInt32 count)
2006
(void)pr_ConservativeWalkBlock(base, count, (PRWalkFun) pr_DumpRootPointer, NULL);
2010
DumpThreadRoots(PRThread *t, int i, void *notused);
2013
pr_DumpRoots(FILE *out)
2016
void (*liveBlock)(void **base, PRInt32 count);
2017
void (*livePointer)(void *ptr);
2018
void (*processRootBlock)(void **base, PRInt32 count);
2019
void (*processRootPointer)(void *ptr);
2023
liveBlock = _pr_gcData.liveBlock;
2024
livePointer = _pr_gcData.livePointer;
2025
processRootBlock = _pr_gcData.processRootBlock;
2026
processRootPointer = _pr_gcData.processRootPointer;
2028
_pr_gcData.liveBlock = pr_ConservativeDumpRootBlock;
2029
_pr_gcData.livePointer = pr_ConservativeDumpRootPointer;
2030
_pr_gcData.processRootBlock = pr_ConservativeDumpRootBlock;
2031
_pr_gcData.processRootPointer = pr_ConservativeDumpRootPointer;
2032
_pr_gcData.dumpOutput = out;
2034
rf = _pr_rootFinders;
2036
fprintf(out, "\n===== Roots for %s\n", rf->name);
2037
(*rf->func)(rf->arg);
2041
_pr_gcData.liveBlock = liveBlock;
2042
_pr_gcData.livePointer = livePointer;
2043
_pr_gcData.processRootBlock = processRootBlock;
2044
_pr_gcData.processRootPointer = processRootPointer;
2045
_pr_gcData.dumpOutput = NULL;
2050
/*******************************************************************************
2051
* Heap Summary Dumper
2052
******************************************************************************/
2054
PRSummaryPrinter summaryPrinter = NULL;
2055
void* summaryPrinterClosure = NULL;
2058
PR_RegisterSummaryPrinter(PRSummaryPrinter fun, void* closure)
2060
summaryPrinter = fun;
2061
summaryPrinterClosure = closure;
2064
static void PR_CALLBACK
2065
pr_SummarizeObject(FILE *out, GCType* tp, PRWord *p,
2066
size_t bytes, PRBool detailed)
2069
(*tp->summarize)((void GCPTR*)(p + 1), bytes);
2072
static void PR_CALLBACK
2073
pr_DumpSummary(FILE* out, GCSeg* sp, PRBool detailed)
2075
pr_WalkSegment(out, sp, detailed, NULL, NULL,
2076
pr_SummarizeObject, NULL, NULL);
2080
PR_DumpGCSummary(FILE *out, PRBool detailed)
2082
if (summaryPrinter) {
2083
pr_WalkSegments(out, pr_DumpSummary, detailed);
2084
summaryPrinter(out, summaryPrinterClosure);
2087
fprintf(out, "\nFinalizable objects:\n");
2090
qp = _pr_pendingFinalQueue.next;
2091
while (qp != &_pr_pendingFinalQueue) {
2092
GCFinal* fp = FinalPtr(qp);
2093
PRWord h = fp->object[0]; /* Grab header word */
2094
PRWord tix = GET_TYPEIX(h);
2095
GCType* tp = _pr_gcTypes[tix];
2096
size_t bytes = OBJ_BYTES(h);
2097
pr_DumpObject(out, tp, fp->object, bytes, PR_FALSE);
2105
PR_DumpMemorySummary(void)
2107
PR_DumpToFile("memory.out", "Memory Summary", PR_DumpGCSummary, PR_FALSE);
2110
/*******************************************************************************
2111
* End Of Heap Walker
2112
******************************************************************************/
2114
#ifdef GC_TRACEROOTS
2116
PRInt32 pr_traceGen = 0;
2119
pr_IsMarked(PRWord* p)
2121
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
2122
PR_ASSERT(end->check == PR_BLOCK_END);
2123
return end->traceGeneration == pr_traceGen;
2129
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
2130
PR_ASSERT(end->check == PR_BLOCK_END);
2131
end->traceGeneration = pr_traceGen;
2134
PRWord* pr_traceObj; /* set this in the debugger, then execute PR_TraceRoot() */
2136
static PRInt32 PR_CALLBACK
2137
pr_TraceRootObject(void* obj, void* data);
2139
static PRInt32 PR_CALLBACK
2140
pr_TraceRootPointer(PRWord *p, void* data)
2142
PRInt32 printTrace = 0;
2144
PRWord tix = GET_TYPEIX(h);
2145
GCType* tp = &_pr_collectorTypes[tix].gctype;
2146
FILE* out = _pr_gcData.dumpOutput;
2153
if (p == pr_traceObj) {
2154
fprintf(out, "\n### Found path to:\n");
2158
if (PR_StackSpaceLeft(PR_GetCurrentThread()) < 512) {
2159
fprintf(out, "\n### Path too deep (giving up):\n");
2162
else if (tp->walk) {
2163
printTrace = tp->walk((void*)(p + 1), pr_TraceRootObject, data);
2165
/* else there's no way to walk this object, so we
2166
haven't found what we're looking for */
2169
if (printTrace == 1) {
2170
PR_ASSERT(tp->dump);
2171
fprintf(out, "0x%p: ", p);
2172
tp->dump(out, (void*)(p + 1), PR_FALSE, 1);
2177
static PRInt32 PR_CALLBACK
2178
pr_TraceRootObject(void* obj, void* data)
2180
/* This version of pr_TraceRootPointer takes object
2181
pointers, instead of gc header pointers. */
2182
return pr_TraceRootPointer((PRWord*)obj - 1, data);
2185
static void PR_CALLBACK
2186
pr_ConservativeTraceRootPointer(PRWord *p)
2190
status = pr_ConservativeWalkPointer(p, pr_TraceRootPointer, NULL);
2192
FILE* out = _pr_gcData.dumpOutput;
2193
fprintf(out, "### from root at 0x%p\n\n", p);
2197
static void PR_CALLBACK
2198
pr_ConservativeTraceRootBlock(void **base, PRInt32 count)
2202
status = pr_ConservativeWalkBlock(base, count, pr_TraceRootPointer, NULL);
2204
FILE* out = _pr_gcData.dumpOutput;
2205
fprintf(out, "### from root in range 0x%p + 0x%lx\n\n",
2206
base, (long) count);
2211
PR_TraceRoot1(FILE* out, PRBool detailed)
2214
void (*liveBlock)(void **base, PRInt32 count);
2215
void (*livePointer)(void *ptr);
2216
void (*processRootBlock)(void **base, PRInt32 count);
2217
void (*processRootPointer)(void *ptr);
2221
liveBlock = _pr_gcData.liveBlock;
2222
livePointer = _pr_gcData.livePointer;
2223
processRootBlock = _pr_gcData.processRootBlock;
2224
processRootPointer = _pr_gcData.processRootPointer;
2226
_pr_gcData.liveBlock = pr_ConservativeTraceRootBlock;
2227
_pr_gcData.livePointer = pr_ConservativeTraceRootPointer;
2228
_pr_gcData.processRootBlock = pr_ConservativeTraceRootBlock;
2229
_pr_gcData.processRootPointer = pr_ConservativeTraceRootPointer;
2230
_pr_gcData.dumpOutput = out;
2232
fprintf(out, "### Looking for paths to 0x%p\n\n", pr_traceObj);
2234
rf = _pr_rootFinders;
2236
fprintf(out, "\n===== Roots for %s\n", rf->name);
2237
(*rf->func)(rf->arg);
2241
_pr_gcData.liveBlock = liveBlock;
2242
_pr_gcData.livePointer = livePointer;
2243
_pr_gcData.processRootBlock = processRootBlock;
2244
_pr_gcData.processRootPointer = processRootPointer;
2245
_pr_gcData.dumpOutput = NULL;
2255
** Once you find the object you want to trace the roots of, set the
2256
** global variable pr_traceObj to point to it (the header, not the
2257
** java handle), and then call this routine (on Windows, you can set
2258
** a breakpoint at the end of a function that returns void (e.g. dogc)
2259
** and then do a "set next statement" to point to this routine and go.
2260
** This will dump a list of the paths from the roots to the object in
2261
** question to your memory.out file.
2263
PR_DumpToFile("memory.out", "Tracing Roots", PR_TraceRoot1, PR_FALSE);
2266
#endif /* GC_TRACEROOTS */
2268
/******************************************************************************/
2270
#if defined(DEBUG) && defined(WIN32)
2271
static void DumpApplicationHeap(FILE *out, HANDLE heap)
2273
PROCESS_HEAP_ENTRY entry;
2276
if (!HeapLock(heap))
2277
OutputDebugString("Can't lock the heap.\n");
2279
fprintf(out, " address: size ovhd region\n");
2280
while (HeapWalk(heap, &entry))
2282
WORD flags = entry.wFlags;
2284
fprintf(out, "0x%.8X: 0x%.8X 0x%.2X 0x%.2X ", entry.lpData, entry.cbData,
2285
entry.cbOverhead, entry.iRegionIndex);
2286
if (flags & PROCESS_HEAP_REGION)
2287
fprintf(out, "REGION committedSize=0x%.8X uncommittedSize=0x%.8X firstBlock=0x%.8X lastBlock=0x%.8X",
2288
entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
2289
entry.Region.lpFirstBlock, entry.Region.lpLastBlock);
2290
else if (flags & PROCESS_HEAP_UNCOMMITTED_RANGE)
2291
fprintf(out, "UNCOMMITTED");
2292
else if (flags & PROCESS_HEAP_ENTRY_BUSY)
2294
if (flags & PROCESS_HEAP_ENTRY_DDESHARE)
2295
fprintf(out, "DDEShare ");
2296
if (flags & PROCESS_HEAP_ENTRY_MOVEABLE)
2297
fprintf(out, "Moveable Block handle=0x%.8X", entry.Block.hMem);
2299
fprintf(out, "Block");
2303
if ((err = GetLastError()) != ERROR_NO_MORE_ITEMS)
2304
fprintf(out, "ERROR %d iterating through the heap\n", err);
2305
if (!HeapUnlock(heap))
2306
OutputDebugString("Can't unlock the heap.\n");
2310
#if defined(DEBUG) && defined(WIN32)
2311
static void DumpApplicationHeaps(FILE *out)
2318
mainHeap = GetProcessHeap();
2319
nHeaps = GetProcessHeaps(100, heaps);
2322
fprintf(out, "%ld heaps:\n", (long) nHeaps);
2323
for (i = 0; i<nHeaps; i++)
2325
HANDLE heap = heaps[i];
2327
fprintf(out, "Heap at 0x%.8lX", (long) heap);
2328
if (heap == mainHeap)
2329
fprintf(out, " (main)");
2330
fprintf(out, ":\n");
2331
DumpApplicationHeap(out, heap);
2334
fprintf(out, "End of heap dump\n\n");
2338
#if defined(DEBUG) && defined(WIN32)
2339
PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
2343
OutputDebugString("Dumping heaps...");
2344
out = fopen("heaps.out", "a");
2346
OutputDebugString("Can't open \"heaps.out\"\n");
2353
newtime = localtime(&aclock);
2354
fprintf(out, "Heap dump on %s\n", asctime(newtime)); /* Print current time */
2355
DumpApplicationHeaps(out);
2356
fprintf(out, "\n\n");
2359
OutputDebugString(" done\n");
2363
PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
2365
fprintf(stderr, "Native heap dumping is currently implemented only for Windows32.\n");
2369
/************************************************************************/
2372
** Scan the freelist bins looking for a big enough chunk of memory to
2373
** hold "bytes" worth of allocation. "bytes" already has the
2374
** per-allocation header added to it. Return a pointer to the object with
2375
** its per-allocation header already prepared.
2377
static PRWord *BinAlloc(int cbix, PRInt32 bytes, int dub)
2379
GCFreeChunk **cpp, *cp, *cpNext;
2381
PRInt32 chunkSize, remainder;
2383
PRInt32 bin, newbin;
2385
/* Compute bin that allocation belongs in */
2386
InlineBinNumber(bin,bytes)
2388
bin = minBin; /* Start at first filled bin */
2391
/* Search in the bin, and larger bins, for a big enough piece */
2392
for (; bin <= NUM_BINS-1; bin++) {
2394
while ((cp = *cpp) != 0) {
2395
chunkSize = cp->chunkSize;
2396
if (chunkSize < bytes) {
2397
/* Too small; skip it */
2398
METER(meter.skippedFreeChunks++);
2403
/* We have found a hunk of memory large enough to use */
2408
if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
2410
* We are double aligning the memory and the current free
2411
* chunk is aligned on an even boundary. Because header
2412
* words are one word long we need to discard the first
2415
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
2418
chunkSize -= PR_BYTES_PER_WORD;
2419
bytes -= PR_BYTES_PER_WORD;
2420
PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
2421
_pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
2422
_pr_gcData.busyMemory += PR_BYTES_PER_WORD;
2425
np = (PRWord*) ((char*) p + bytes);
2426
remainder = chunkSize - bytes;
2427
if (remainder >= MIN_FREE_CHUNK_BYTES) {
2428
/* The left over memory is large enough to be freed. */
2429
cp = (GCFreeChunk*) np;
2431
cp->chunkSize = remainder;
2432
InlineBinNumber(newbin, remainder)
2433
if (newbin != bin) {
2434
*cpp = (GCFreeChunk*) cpNext; /* remove */
2435
cp->next = bins[newbin]; /* insert */
2437
if (newbin < minBin) minBin = newbin;
2438
if (newbin > maxBin) maxBin = newbin;
2440
/* Leave it on the same list */
2442
*cpp = (GCFreeChunk*) np;
2446
* The left over memory is too small to be released. Just
2447
* leave it attached to the chunk of memory being
2453
p[0] = MAKE_HEADER(cbix, (bytes >> PR_BYTES_PER_WORD_LOG2));
2455
_pr_gcData.freeMemory -= bytes;
2456
_pr_gcData.busyMemory += bytes;
2464
** Allocate a piece of memory that is "big" in it's own segment. Make
2465
** the object consume the entire segment to avoid fragmentation. When
2466
** the object is no longer referenced, the segment is freed.
2468
static PRWord *BigAlloc(int cbix, PRInt32 bytes, int dub)
2475
** If the number of bytes allocated via BigAlloc() since the last GC
2476
** exceeds BIG_ALLOC_GC_SIZE then do a GC Now...
2478
if (bigAllocBytes >= BIG_ALLOC_GC_SIZE) {
2481
bigAllocBytes += bytes;
2483
/* Get a segment to hold this allocation */
2484
sp = GrowHeapExactly(bytes);
2487
p = (PRWord*) sp->base;
2488
chunkSize = sp->limit - sp->base;
2490
/* All memory is double aligned on 64 bit machines... */
2492
if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
2494
** Consume the first word of the chunk with a dummy
2495
** unreferenced object.
2497
p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
2500
chunkSize -= PR_BYTES_PER_WORD;
2501
_pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
2502
_pr_gcData.busyMemory += PR_BYTES_PER_WORD;
2503
PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
2507
/* Consume the *entire* segment with a single allocation */
2508
h = MAKE_HEADER(cbix, (chunkSize >> PR_BYTES_PER_WORD_LOG2));
2511
_pr_gcData.freeMemory -= chunkSize;
2512
_pr_gcData.busyMemory += chunkSize;
2518
/* we disable gc allocation during low memory conditions */
2519
static PRBool allocationEnabled = PR_TRUE;
2521
PR_IMPLEMENT(void) PR_EnableAllocation(PRBool yesOrNo)
2523
allocationEnabled = yesOrNo;
2526
static void CollectorCleanup(void) {
2527
while (collectorCleanupNeeded) {
2529
collectorCleanupNeeded = 0;
2534
if (!WEAK_FREELIST_ISEMPTY()) {
2535
EmptyWeakFreeList();
2540
/******************************************************************************/
2543
static PRInt32 allocationCount;
2545
static void EarthShatteringKaBoom(PRInt32 whichOne) {
2550
/* Check a segment of heap memory. Verify that the object memory
2551
hasn't been overwritten (past the end at least) */
2552
static void CheckSegment(GCSeg* sp) {
2554
PRWord *p, *lastp, *np, *limit;
2556
lastp = p = (PRWord *) sp->base;
2557
limit = (PRWord *) sp->limit;
2559
if (IS_HBIT(sp, p)) {
2562
PRWord bytes, requestedBytes;
2565
tix = GET_TYPEIX(h);
2566
bytes = OBJ_BYTES(h);
2567
np = (PRWord *) ((char *)p + bytes);
2568
if (tix != FREE_MEMORY_TYPEIX) {
2569
PRInt32 test; /* msdev get's fooled without this local */
2570
/* A live object is here. The last word in the object will
2571
contain the objects requestedSize */
2572
end = (GCBlockEnd*)((char*)(p) + bytes - sizeof(GCBlockEnd));
2574
if (test != PR_BLOCK_END) {
2575
PR_ASSERT(test == PR_BLOCK_END);
2577
requestedBytes = end->requestedBytes;
2578
if (requestedBytes >= bytes) EarthShatteringKaBoom(0);
2579
cp = (char*)(p + 1) + requestedBytes;
2581
while (cp < (char*)end) {
2582
if (*cp != i) EarthShatteringKaBoom(1);
2590
/* Must be a freelist item */
2591
GCFreeChunk *cp = (GCFreeChunk*) p;
2592
if ((PRInt32)cp->chunkSize < (PRInt32)sizeof(GCFreeChunk)) {
2593
EarthShatteringKaBoom(3);
2596
p = (PRWord*) ((char*)p + cp->chunkSize);
2601
static void CheckHeap(void) {
2603
GCSeg *esp = sp + nsegs;
2610
#endif /* GC_CHECK */
2612
/******************************************************************************/
2615
long gc_thrash = -1L;
2619
** Allocate memory from the GC Heap. Performs garbage collections if
2620
** memory gets tight and grows the heap as needed. May return NULL if
2621
** memory cannot be found.
2623
PR_IMPLEMENT(PRWord GCPTR *)PR_AllocMemory(
2624
PRWord requestedBytes, PRInt32 tix, PRWord flags)
2631
int dub = flags & PR_ALLOC_DOUBLE;
2634
PRInt64 allocTime, ldelta;
2637
if (!allocationEnabled) return NULL;
2639
PR_ASSERT(requestedBytes >= 0);
2640
PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
2643
if (_pr_do_a_dump) {
2645
** Collect, pause for a second (lets finalizer run), and then GC
2649
PR_Sleep(PR_MicrosecondsToInterval(1000000L));
2651
PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
2657
allocTime = PR_Now();
2659
bytes = (PRInt32) requestedBytes;
2662
** Align bytes to a multiple of a PRWord, then add in enough space
2663
** to hold the header word.
2665
** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
2667
/* Check for possible overflow of bytes before performing add */
2668
if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
2669
bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
2670
bytes <<= PR_BYTES_PER_WORD_LOG2;
2671
/* Check for possible overflow of bytes before performing add */
2672
if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
2673
bytes += sizeof(PRWord);
2675
* Add in an extra word of memory for double-aligned memory. Some
2676
* percentage of the time this will waste a word of memory (too
2677
* bad). Howver, it makes the allocation logic much simpler and
2682
/* Check for possible overflow of bytes before performing add */
2683
if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
2684
bytes += PR_BYTES_PER_WORD;
2689
if (_pr_gcData.flags & GC_CHECK) {
2690
/* Bloat the allocation a bit so that we can lay down
2691
a check pattern that we will validate */
2692
/* Check for possible overflow of bytes before performing add */
2693
if ((MAX_INT - PR_BYTES_PER_WORD * 3) < bytes ) return NULL;
2694
bytes += PR_BYTES_PER_WORD * 3;
2698
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
2699
if ((MAX_INT - sizeof(GCBlockEnd)) < bytes ) return NULL;
2700
bytes += sizeof(GCBlockEnd);
2703
PR_ASSERT( bytes < MAX_ALLOC_SIZE );
2705
** Java can ask for objects bigger than MAX_ALLOC_SIZE,
2706
** but it won't get them.
2708
if (bytes >= MAX_ALLOC_SIZE) return NULL;
2711
if (gc_thrash == -1L ? (gc_thrash = (long)PR_GetEnv("GC_THRASH")):gc_thrash) PR_GC();
2714
ct = &_pr_collectorTypes[tix];
2715
if (ct->flags & (_GC_TYPE_FINAL|_GC_TYPE_WEAK)) {
2716
if (0 != ct->gctype.finalize) {
2718
** Allocate a GCFinal struct for this object in advance. Don't put
2719
** it on the pending list until we have allocated the object
2721
final = AllocFinalNode();
2723
/* XXX THIS IS NOT ACCEPTABLE*/
2728
if (0 != ct->gctype.getWeakLinkOffset) {
2730
** Allocate a GCWeak struct for this object in advance. Don't put
2731
** it on the weak links list until we have allocated the object
2733
weak = AllocWeakNode();
2735
/* XXX THIS IS NOT ACCEPTABLE*/
2737
FreeFinalNode(final);
2747
if (_pr_gcData.flags & GC_CHECK) CheckHeap();
2751
/* Check for overflow of maximum size we can handle */
2752
if (bytes > MAX_ALLOC) goto lost;
2754
/* Try default allocation */
2755
p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
2756
BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
2759
LL_SUB(ldelta, PR_Now(), allocTime);
2761
/* Collect some memory */
2762
_GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
2764
PR_ASSERT( GC_IS_LOCKED() );
2766
/* After a collection we check and see if we should grow the
2767
** heap. We grow the heap when the amount of memory free is less
2768
** than a certain percentage of the heap size. We don't check to
2769
** see if the grow succeeded because our fallback strategy in
2770
** either case is to try one more time to allocate. */
2771
if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory)
2772
&& ((_pr_gcData.freeMemory <
2773
((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))
2774
|| (_pr_gcData.freeMemory < bytes))) {
2775
GrowHeap(PR_MAX(bytes, segmentSize));
2778
LL_ADD(allocTime, PR_Now(), ldelta);
2782
p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
2783
BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
2785
/* Well that lost big time. Memory must be pretty well fragmented */
2786
if (!GrowHeap(PR_MAX(bytes, segmentSize))) goto lost;
2787
p = BinAlloc(tix, bytes, dub);
2788
if (0 == p) goto lost;
2792
/* Zero out the portion of the object memory that was used by
2793
the GCFreeChunk structure (skip the first word because it
2794
was already overwritten by the gc header word) */
2795
objBytes = OBJ_BYTES(p[0]);
2796
if (objBytes > sizeof(PRWord)) p[1] = 0;
2797
if (objBytes > sizeof(PRWord)*2) p[2] = 0;
2800
_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d) final=0x%x",
2803
PR_APPEND_LINK(&final->links, &_pr_finalizeableObjects);
2805
_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d)", p, bytes));
2809
PR_APPEND_LINK(&weak->links, &_pr_weakLinks);
2811
METER(meter.allocBytes += bytes);
2812
METER(meter.wastedBytes += (bytes - requestedBytes));
2815
if (collectorCleanupNeeded) {
2819
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
2821
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
2822
end->check = PR_BLOCK_END;
2827
PRInt64 now = PR_Now();
2830
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
2832
end->allocTime = allocTime;
2833
LL_SUB(ldelta, now, allocTime);
2834
LL_L2D(delta, ldelta);
2835
InlineBinNumber(bin, requestedBytes);
2837
gcstats[bin].nallocs++;
2838
gcstats[bin].allocTime += delta;
2839
gcstats[bin].allocTimeVariance += delta * delta;
2843
if (_pr_gcData.flags & GC_CHECK) {
2844
/* Place a pattern in the memory that was allocated that was not
2845
requested. We will check the pattern later. */
2846
char* cp = (char*)(p + 1) + requestedBytes;
2847
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
2848
char i = (char) 0xff;
2849
while (cp < (char*)end) {
2852
end->requestedBytes = requestedBytes;
2862
FreeFinalNode(final);
2867
if (collectorCleanupNeeded) {
2873
/* Shortcut allocator for objects that do not require finalization or
2875
PR_IMPLEMENT(PRWord GCPTR *)
2876
PR_AllocSimpleMemory(PRWord requestedBytes, PRInt32 tix)
2882
PRInt64 allocTime, ldelta;
2885
if (!allocationEnabled) return NULL;
2887
PR_ASSERT(requestedBytes >= 0);
2888
PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
2891
if (_pr_do_a_dump) {
2893
** Collect, pause for a second (lets finalizer run), and then GC
2897
PR_Sleep(PR_MicrosecondsToInterval(1000000L));
2899
PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
2905
allocTime = PR_NowMS();
2907
bytes = (PRInt32) requestedBytes;
2910
** Align bytes to a multiple of a PRWord, then add in enough space
2911
** to hold the header word.
2913
** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
2915
bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
2916
bytes <<= PR_BYTES_PER_WORD_LOG2;
2917
bytes += sizeof(PRWord);
2920
* Add in an extra word of memory for double-aligned memory. Some
2921
* percentage of the time this will waste a word of memory (too
2922
* bad). Howver, it makes the allocation logic much simpler and
2926
bytes += PR_BYTES_PER_WORD;
2930
if (_pr_gcData.flags & GC_CHECK) {
2931
/* Bloat the allocation a bit so that we can lay down
2932
a check pattern that we will validate */
2933
bytes += PR_BYTES_PER_WORD * 2;
2937
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
2938
bytes += sizeof(GCBlockEnd);
2941
/* Java can ask for objects bigger than 4M, but it won't get them */
2943
* This check was added because there is a fundamental limit of
2944
* the size field maintained by the gc code. Going over the 4M
2945
* limit caused some bits to roll over into another bit field,
2946
* violating the max segment size and causing a bug.
2948
if (bytes >= MAX_ALLOC_SIZE) {
2952
if (gc_thrash == -1L
2953
? (gc_thrash = (long)PR_GetEnv("GC_THRASH"))
2961
if (_pr_gcData.flags & GC_CHECK) {
2967
/* Try default allocation */
2968
if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
2969
p = BigAlloc(tix, bytes, 1);
2971
p = BinAlloc(tix, bytes, 1);
2975
LL_SUB(ldelta, PR_Now(), allocTime);
2977
/* Collect some memory */
2978
_GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
2980
PR_ASSERT( GC_IS_LOCKED() );
2982
/* After a collection we check and see if we should grow the
2983
heap. We grow the heap when the amount of memory free is less
2984
than a certain percentage of the heap size. We don't check to
2985
see if the grow succeeded because our fallback strategy in
2986
either case is to try one more time to allocate. */
2987
if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory) &&
2988
(_pr_gcData.freeMemory <
2989
((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))) {
2990
GrowHeap(PR_MAX(bytes, segmentSize));
2993
LL_ADD(allocTime, PR_Now(), ldelta);
2996
/* Try one last time */
2997
if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
2998
p = BigAlloc(tix, bytes, 1);
3000
p = BinAlloc(tix, bytes, 1);
3003
/* Well that lost big time. Memory must be pretty well fragmented */
3004
if (!GrowHeap(PR_MAX(bytes, segmentSize))) {
3007
p = BinAlloc(tix, bytes, 1);
3008
if (0 == p) goto lost;
3012
/* Zero out the portion of the object memory that was used by
3013
the GCFreeChunk structure (skip the first word because it
3014
was already overwritten by the gc header word) */
3015
objBytes = OBJ_BYTES(p[0]);
3016
if (objBytes > sizeof(PRWord)) p[1] = 0;
3017
if (objBytes > sizeof(PRWord)*2) p[2] = 0;
3019
METER(meter.allocBytes += bytes);
3020
METER(meter.wastedBytes += (bytes - requestedBytes));
3023
if (collectorCleanupNeeded) {
3027
#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
3029
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
3030
end->check = PR_BLOCK_END;
3035
PRInt64 now = PR_Now();
3038
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
3040
end->allocTime = allocTime;
3041
LL_SUB(ldelta, now, allocTime);
3042
LL_L2D(delta, ldelta);
3043
InlineBinNumber(bin, requestedBytes);
3045
gcstats[bin].nallocs++;
3046
gcstats[bin].allocTime += delta;
3047
gcstats[bin].allocTimeVariance += delta * delta;
3051
if (_pr_gcData.flags & GC_CHECK) {
3052
/* Place a pattern in the memory that was allocated that was not
3053
requested. We will check the pattern later. */
3054
char* cp = (char*)(p + 1) + requestedBytes;
3055
GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
3056
char i = (char) 0xff;
3057
while (cp < (char*)end) {
3060
end->requestedBytes = requestedBytes;
3069
if (collectorCleanupNeeded) {
3075
/************************************************************************/
3077
PR_IMPLEMENT(PRWord) PR_GetObjectHeader(void *ptr) {
3081
if (ptr == 0) return 0;
3083
if (sp == 0) return 0;
3084
h = (PRWord*)FindObject(sp, (PRWord*)ptr);
3085
return GC_GET_USER_BITS(h[0]);
3088
PR_IMPLEMENT(PRWord) PR_SetObjectHeader(void *ptr, PRWord newUserBits) {
3092
if (ptr == 0) return 0;
3094
if (sp == 0) return 0;
3095
h = (PRWord*)FindObject(sp, (PRWord*)ptr);
3096
rv = GC_GET_USER_BITS(h[0]);
3097
h[0] = (h[0] & ~GC_USER_BITS) |
3098
((newUserBits << GC_USER_BITS_SHIFT) & GC_USER_BITS);
3102
PR_IMPLEMENT(void) PR_InitGC(
3103
PRWord flags, PRInt32 initialHeapSize, PRInt32 segSize, PRThreadScope scope)
3105
static char firstTime = 1;
3107
if (!firstTime) return;
3110
_pr_msgc_lm = PR_NewLogModule("msgc");
3111
_pr_pageShift = PR_GetPageShift();
3112
_pr_pageSize = PR_GetPageSize();
3114
/* Setup initial heap size and initial segment size */
3115
if (0 != segSize) segmentSize = segSize;
3117
GC = PR_NewLogModule("GC");
3119
char *ev = PR_GetEnv("GC_SEGMENT_SIZE");
3121
PRInt32 newSegmentSize = atoi(ev);
3122
if (0 != newSegmentSize) segmentSize = newSegmentSize;
3124
ev = PR_GetEnv("GC_INITIAL_HEAP_SIZE");
3126
PRInt32 newInitialHeapSize = atoi(ev);
3127
if (0 != newInitialHeapSize) initialHeapSize = newInitialHeapSize;
3129
ev = PR_GetEnv("GC_FLAGS");
3134
ev = PR_GetEnv("GC_METER");
3136
_pr_gcMeter = atoi(ev);
3141
if (0 == initialHeapSize) initialHeapSize = segmentSize;
3142
if (initialHeapSize < segmentSize) initialHeapSize = segmentSize;
3144
_pr_gcData.maxMemory = MAX_SEGS * segmentSize;
3145
_pr_gcData.liveBlock = ProcessRootBlock;
3146
_pr_gcData.livePointer = ProcessRootPointer;
3147
_pr_gcData.processRootBlock = ProcessRootBlock;
3148
_pr_gcData.processRootPointer = ProcessRootPointer;
3149
_pr_gcData.dumpOutput = NULL;
3151
PR_INIT_CLIST(&_pr_finalizeableObjects);
3152
PR_INIT_CLIST(&_pr_finalQueue);
3155
/* Create finalizer thread */
3156
_PR_CreateFinalizer(scope);
3158
/* Allocate the initial segment for the heap */
3161
GrowHeap(initialHeapSize);
3162
PR_RegisterRootFinder(ScanWeakFreeList, "scan weak free list", 0);
3165
/** Added by Vishy for sanity checking a few GC structures **/
3166
/** Can use SanityCheckGC to debug corrupted GC Heap situations **/
3170
static int SegmentOverlaps(int i, int j)
3173
(((segs[i].limit > segs[j].base) && (segs[i].base < segs[j].base)) ||
3174
((segs[j].limit > segs[i].base) && (segs[j].base < segs[i].base)));
3177
static void NoSegmentOverlaps(void)
3181
for (i = 0; i < nsegs; i++)
3182
for (j = i+1 ; j < nsegs ; j++)
3183
PR_ASSERT(!SegmentOverlaps(i,j));
3186
static void SegInfoCheck(void)
3189
for (i = 0 ; i < nsegs ; i++)
3190
PR_ASSERT((segs[i].info->hbits) &&
3191
(segs[i].info->hbits == segs[i].hbits) &&
3192
(segs[i].info->base == segs[i].base) &&
3193
(segs[i].info->limit == segs[i].limit));
3196
static void SanityCheckGC()
3198
NoSegmentOverlaps();
3204
#if defined(DEBUG) && defined(WIN32)
3206
extern void *baseaddr;
3207
extern void *lastaddr;
3210
PR_PrintGCStats(void)
3212
long reportedSegSpace = _pr_gcData.busyMemory + _pr_gcData.freeMemory;
3214
long largeCount = 0, largeSize = 0;
3215
long segCount = 0, segSize = 0;
3216
long freeCount = 0, freeSize = 0;
3225
long size = sp->info->limit - sp->info->base;
3228
if (sp->info->fromMalloc) {
3236
while (si != NULL) {
3237
long size = si->limit - si->base;
3243
msg = PR_smprintf("\
3246
# range: %ld - %ld\n\
3249
# range: %ld - %ld\n\
3250
# count: %ld (reported: %ld)\n\
3251
# size: %ld (reported: %ld)\n\
3252
# free count: %ld\n\
3254
# busy objs: %ld (%ld%%)\n\
3255
# free objs: %ld (%ld%%)\n\
3258
# total size: %ld (%ld%%)\n\
3262
(long)baseaddr, (long)lastaddr,
3263
(long)lastaddr - (long)baseaddr,
3265
_pr_gcData.lowSeg, _pr_gcData.highSeg,
3267
segSize, reportedSegSpace,
3270
_pr_gcData.busyMemory,
3271
(_pr_gcData.busyMemory * 100 / reportedSegSpace),
3272
_pr_gcData.freeMemory,
3273
(_pr_gcData.freeMemory * 100 / reportedSegSpace),
3276
largeSize, (largeSize * 100 / reportedSegSpace),
3277
(largeCount ? largeSize / largeCount : 0)
3280
fprintf(stderr, msg);
3281
OutputDebugString(msg);
3282
PR_smprintf_free(msg);
3284
PR_PrintGCAllocStats();
3290
PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed)
3293
OutputDebugString(msg);
3294
out = fopen(filename, "a");
3297
PR_ASSERT(strlen(filename) < sizeof(buf) - 16);
3298
PR_snprintf(buf, sizeof(buf), "Can't open \"%s\"\n",
3300
OutputDebugString(buf);
3309
newtime = localtime(&aclock);
3310
fprintf(out, "%s on %s\n", msg, asctime(newtime)); /* Print current time */
3311
dump(out, detailed);
3312
fprintf(out, "\n\n");
3313
for (i = 0; i < 80; i++)
3315
fprintf(out, "\n\n");
3318
OutputDebugString(" done\n");