Back to index

lightning-sunbird  0.9+nobinonly
prmsgc.c
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Netscape Portable Runtime (NSPR).
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-2000
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #include <string.h>
00039 #include <stddef.h>
00040 #include <stdarg.h>
00041 #include <time.h>
00042 
00043 #ifdef WIN32
00044 #include <windef.h>
00045 #include <winbase.h>
00046 #endif
00047 
00048 #include "prclist.h"
00049 #include "prbit.h"
00050 
00051 #include "prtypes.h"
00052 #include "prenv.h"
00053 #include "prgc.h"
00054 #include "prthread.h"
00055 #include "prlog.h"
00056 #include "prlong.h"
00057 #include "prinrval.h"
00058 #include "prprf.h"
00059 #include "gcint.h"
00060 
00061 #if defined(XP_MAC)
00062 #include "pprthred.h"
00063 #else
00064 #include "private/pprthred.h"
00065 #endif
00066 
00067 typedef void (*PRFileDumper)(FILE *out, PRBool detailed);
00068 
00069 PR_EXTERN(void)
00070 PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed);
00071 
00072 /*
00073 ** Mark&sweep garbage collector. Supports objects that require
00074 ** finalization, objects that can have a single weak link, and special
00075 ** objects that require care during sweeping.
00076 */
00077 
00078 PRLogModuleInfo *_pr_msgc_lm;
00079 PRLogModuleInfo* GC;
00080 
00081 static PRInt32 _pr_pageShift;
00082 static PRInt32 _pr_pageSize;
00083 
00084 #ifdef DEBUG
00085 #define GCMETER
00086 #endif
00087 #ifdef DEBUG_jwz
00088 # undef GCMETER
00089 #endif /* 1 */
00090 
00091 #ifdef GCMETER
00092 #define METER(x) x
00093 #else
00094 #define METER(x)
00095 #endif
00096 
00097 /*
00098 ** Make this constant bigger to reduce the amount of recursion during
00099 ** garbage collection.
00100 */
00101 #define MAX_SCAN_Q    100L
00102 
00103 #if defined(XP_PC) && !defined(WIN32)
00104 #define MAX_SEGS            400L
00105 #define MAX_SEGMENT_SIZE    (65536L - 4096L)
00106 #define SEGMENT_SIZE        (65536L - 4096L)
00107 #define MAX_ALLOC_SIZE      (65536L - 4096L)
00108 #else
00109 #define MAX_SEGS                    400L
00110 #define MAX_SEGMENT_SIZE            (2L * 256L * 1024L)
00111 #define SEGMENT_SIZE                (1L * 256L * 1024L)
00112 #define MAX_ALLOC_SIZE              (4L * 1024L * 1024L)
00113 #endif  
00114 
00115 /* 
00116  * The highest value that can fit into a signed integer. This
00117  * is used to prevent overflow of allocation size in alloc routines.
00118  */
00119  
00120 #define MAX_INT ((1UL << (PR_BITS_PER_INT - 1)) - 1)
00121 
00122 /* 
00123  * On 32-bit machines, only 22 bits are used in the cibx integer to
00124  * store size since 8 bits of the integer are used to store type, and
00125  * of the remainder, 2 are user defined. Max allocation size = 2^22 -1
00126  */
00127 
00128 #define MAX_ALLOC ( (1L << (PR_BYTES_PER_WORD_LOG2 + WORDS_BITS )) -1)
00129 
00130 /* The minimum percentage of free heap space after a collection. If
00131    the amount of free space doesn't meet this criteria then we will
00132    attempt to grow the heap */
00133 #ifdef XP_MAC
00134 #define MIN_FREE_THRESHOLD_AFTER_GC 10L
00135 #else
00136 #define MIN_FREE_THRESHOLD_AFTER_GC 20L
00137 #endif
00138 
00139 static PRInt32 segmentSize = SEGMENT_SIZE;
00140 
00141 static PRInt32 collectorCleanupNeeded;
00142 
00143 #ifdef GCMETER
00144 PRUint32 _pr_gcMeter;
00145 
00146 #define _GC_METER_STATS         0x01L
00147 #define _GC_METER_GROWTH        0x02L
00148 #define _GC_METER_FREE_LIST     0x04L
00149 #endif
00150 
00151 /************************************************************************/
00152 
00153 #define LINEAR_BIN_EXPONENT 5
00154 #define NUM_LINEAR_BINS ((PRUint32)1 << LINEAR_BIN_EXPONENT)
00155 #define FIRST_LOG_BIN (NUM_LINEAR_BINS - LINEAR_BIN_EXPONENT)
00156 
00157 /* Each free list bin holds a chunk of memory sized from
00158    2^n to (2^(n+1))-1 inclusive. */
00159 #define NUM_BINS        (FIRST_LOG_BIN + 32)
00160 
00161 /*
00162  * Find the bin number for a given size (in bytes). This does not round up as
00163  * values from 2^n to (2^(n+1))-1 share the same bin.
00164  */
00165 #define InlineBinNumber(_bin,_bytes)  \
00166 {  \
00167     PRUint32 _t, _n = (PRUint32) _bytes / 4;  \
00168     if (_n < NUM_LINEAR_BINS) {  \
00169         _bin = _n;  \
00170     } else {  \
00171         _bin = FIRST_LOG_BIN;  \
00172         if ((_t = (_n >> 16)) != 0) { _bin += 16; _n = _t; }  \
00173         if ((_t = (_n >> 8)) != 0)  { _bin += 8; _n = _t; }  \
00174         if ((_t = (_n >> 4)) != 0)  { _bin += 4; _n = _t; }  \
00175         if ((_t = (_n >> 2)) != 0) { _bin += 2; _n = _t; }  \
00176         if ((_n >> 1) != 0) _bin++;  \
00177     }  \
00178 }
00179 
00180 #define BIG_ALLOC       16384L
00181 
00182 #define MIN_FREE_CHUNK_BYTES    ((PRInt32)sizeof(GCFreeChunk))
00183 
00184 /* Note: fix code in PR_AllocMemory if you change the size of GCFreeChunk
00185    so that it zeros the right number of words */
00186 typedef struct GCFreeChunk {
00187     struct GCFreeChunk *next;
00188     struct GCSeg *segment;
00189     PRInt32 chunkSize;
00190 } GCFreeChunk;
00191 
00192 typedef struct GCSegInfo {
00193     struct GCSegInfo *next;
00194     char *base;
00195     char *limit;
00196     PRWord *hbits;
00197     int fromMalloc;
00198 } GCSegInfo;
00199     
00200 typedef struct GCSeg {
00201     char *base;
00202     char *limit;
00203     PRWord *hbits;
00204     GCSegInfo *info;
00205 } GCSeg;
00206 
00207 #ifdef GCMETER
00208 typedef struct GCMeter {
00209     PRInt32 allocBytes;
00210     PRInt32 wastedBytes;
00211     PRInt32 numFreeChunks;
00212     PRInt32 skippedFreeChunks;
00213 } GCMeter;
00214 static GCMeter meter;
00215 #endif
00216 
00217 /*
00218 ** There is one of these for each segment of GC'able memory.
00219 */
00220 static GCSeg segs[MAX_SEGS];
00221 static GCSegInfo *freeSegs;
00222 static GCSeg* lastInHeap;
00223 static int nsegs;
00224 
00225 static GCFreeChunk *bins[NUM_BINS];
00226 static PRInt32 minBin;
00227 static PRInt32 maxBin;
00228 
00229 /*
00230 ** Scan Q used to avoid deep recursion when scanning live objects for
00231 ** heap pointers
00232 */
00233 typedef struct GCScanQStr {
00234     PRWord *q[MAX_SCAN_Q];
00235     int queued;
00236 } GCScanQ;
00237 
00238 static GCScanQ *pScanQ;
00239 
00240 #ifdef GCMETER
00241 PRInt32 _pr_maxScanDepth;
00242 PRInt32 _pr_scanDepth;
00243 #endif
00244 
00245 /*
00246 ** Keeps track of the number of bytes allocated via the BigAlloc() 
00247 ** allocator.  When the number of bytes allocated, exceeds the 
00248 ** BIG_ALLOC_GC_SIZE, then a GC will occur before the next allocation
00249 ** is done...
00250 */
00251 #define BIG_ALLOC_GC_SIZE       (4*SEGMENT_SIZE)
00252 static PRWord bigAllocBytes = 0;
00253 
00254 /*
00255 ** There is one GC header word in front of each GC allocated object.  We
00256 ** use it to contain information about the object (what TYPEIX to use for
00257 ** scanning it, how big it is, it's mark status, and if it's a root).
00258 */
00259 #define TYPEIX_BITS    8L
00260 #define WORDS_BITS    20L
00261 #define MAX_CBS        (1L << GC_TYPEIX_BITS)
00262 #define MAX_WORDS    (1L << GC_WORDS_BITS)
00263 #define TYPEIX_SHIFT    24L
00264 #define MAX_TYPEIX    ((1L << TYPEIX_BITS) - 1L)
00265 #define TYPEIX_MASK    PR_BITMASK(TYPEIX_BITS)
00266 #define WORDS_SHIFT    2L
00267 #define WORDS_MASK    PR_BITMASK(WORDS_BITS)
00268 #define MARK_BIT    1L
00269 #define FINAL_BIT    2L
00270 
00271 /* Two bits per object header are reserved for the user of the memory
00272    system to store information into. */
00273 #define GC_USER_BITS_SHIFT 22L
00274 #define GC_USER_BITS    0x00c00000L
00275 
00276 #define MAKE_HEADER(_cbix,_words)              \
00277     ((PRWord) (((unsigned long)(_cbix) << TYPEIX_SHIFT) \
00278          | ((unsigned long)(_words) << WORDS_SHIFT)))
00279 
00280 #define GET_TYPEIX(_h) \
00281     (((PRUword)(_h) >> TYPEIX_SHIFT) & 0xff)
00282 
00283 #define MARK(_sp,_p) \
00284     (((PRWord *)(_p))[0] |= MARK_BIT)
00285 #define IS_MARKED(_sp,_p) \
00286     (((PRWord *)(_p))[0] & MARK_BIT)
00287 #define OBJ_BYTES(_h) \
00288     (((PRInt32) (_h) & 0x003ffffcL) << (PR_BYTES_PER_WORD_LOG2-2L))
00289 
00290 #define GC_GET_USER_BITS(_h) (((_h) & GC_USER_BITS) >> GC_USER_BITS_SHIFT)
00291 
00292 /************************************************************************/
00293 
00294 /*
00295 ** Mark the start of an object in a segment. Note that we mark the header
00296 ** word (which we always have), not the data word (which we may not have
00297 ** for empty objects).
00298 ** XXX tune: put subtract of _sp->base into _sp->hbits pointer?
00299 */
00300 #if !defined(WIN16)
00301 #define SET_HBIT(_sp,_ph) \
00302     SET_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
00303 
00304 #define CLEAR_HBIT(_sp,_ph) \
00305     CLEAR_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
00306 
00307 #define IS_HBIT(_sp,_ph) \
00308     TEST_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
00309 #else
00310 
00311 #define SET_HBIT(_sp,_ph) set_hbit(_sp,_ph)
00312 
00313 #define CLEAR_HBIT(_sp,_ph) clear_hbit(_sp,_ph)
00314 
00315 #define IS_HBIT(_sp,_ph) is_hbit(_sp,_ph)
00316 
00317 static void
00318 set_hbit(GCSeg *sp, PRWord *p)
00319 {
00320     unsigned int distance;
00321     unsigned int index;
00322     PRWord     mask;
00323 
00324         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
00325         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
00326 
00327         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
00328     index    = distance >> PR_BITS_PER_WORD_LOG2;
00329     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
00330 
00331     sp->hbits[index] |= mask;
00332 }
00333 
00334 static void
00335 clear_hbit(GCSeg *sp, PRWord *p)
00336 {
00337     unsigned int distance;
00338     unsigned int index;
00339     PRWord    mask;
00340 
00341         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
00342         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
00343 
00344         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
00345     index    = distance >> PR_BITS_PER_WORD_LOG2;
00346     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
00347 
00348     sp->hbits[index] &= ~mask;
00349 }
00350 
00351 static int
00352 is_hbit(GCSeg *sp, PRWord *p)
00353 {
00354     unsigned int distance;
00355     unsigned int index;
00356     PRWord    mask;
00357 
00358         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
00359         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
00360 
00361         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
00362     index    = distance >> PR_BITS_PER_WORD_LOG2;
00363     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
00364 
00365     return ((sp->hbits[index] & mask) != 0);
00366 }
00367 
00368 
00369 #endif  /* WIN16 */
00370 
00371 /*
00372 ** Given a pointer into this segment, back it up until we are at the
00373 ** start of the object the pointer points into. Each heap segment has a
00374 ** bitmap that has one bit for each word of the objects it contains.  The
00375 ** bit's are set for the firstword of an object, and clear for it's other
00376 ** words.
00377 */
00378 static PRWord *FindObject(GCSeg *sp, PRWord *p)
00379 {
00380     PRWord *base;
00381     
00382     /* Align p to it's proper boundary before we start fiddling with it */
00383     p = (PRWord*) ((PRWord)p & ~(PR_BYTES_PER_WORD-1L));
00384 
00385     base = (PRWord *) sp->base;
00386 #if defined(WIN16)
00387     PR_ASSERT( SELECTOROF(p) == SELECTOROF(base));
00388 #endif
00389     do {
00390     if (IS_HBIT(sp, p)) {
00391         return (p);
00392     }
00393     p--;
00394     } while ( p >= base );
00395 
00396     /* Heap is corrupted! */
00397     _GCTRACE(GC_TRACE, ("ERROR: The heap is corrupted!!! aborting now!"));
00398     abort();
00399     return NULL;
00400 }
00401 
00402 /************************************************************************/
00403 #if !defined(XP_PC) || defined(XP_OS2)
00404 #define OutputDebugString(msg)
00405 #endif 
00406 
00407 #if !defined(WIN16)
00408 #define IN_SEGMENT(_sp, _p)             \
00409     ((((char *)(_p)) >= (_sp)->base) &&    \
00410      (((char *)(_p)) < (_sp)->limit))
00411 #else
00412 #define IN_SEGMENT(_sp, _p)                  \
00413     ((((PRWord)(_p)) >= ((PRWord)(_sp)->base)) && \
00414      (((PRWord)(_p)) < ((PRWord)(_sp)->limit)))
00415 #endif
00416 
00417 static GCSeg *InHeap(void *p)
00418 {
00419     GCSeg *sp, *esp;
00420 
00421     if (lastInHeap && IN_SEGMENT(lastInHeap, p)) {
00422     return lastInHeap;
00423     }
00424 
00425     sp = segs;
00426     esp = segs + nsegs;
00427     for (; sp < esp; sp++) {
00428     if (IN_SEGMENT(sp, p)) {
00429         lastInHeap = sp;
00430         return sp;
00431     }
00432     }
00433     return 0;
00434 }
00435 
00436 /*
00437 ** Grow the heap by allocating another segment. Fudge the requestedSize
00438 ** value to try to pre-account for the HBITS.
00439 */
00440 static GCSeg* DoGrowHeap(PRInt32 requestedSize, PRBool exactly)
00441 {
00442     GCSeg *sp;
00443     GCSegInfo *segInfo;
00444     GCFreeChunk *cp;
00445     char *base;
00446     PRWord *hbits;
00447     PRInt32 nhbytes, nhbits;
00448     PRUint32 allocSize;
00449 
00450     if (nsegs == MAX_SEGS) {
00451     /* No room for more segments */
00452     return 0;
00453     }
00454 
00455     segInfo = (GCSegInfo*) PR_MALLOC(sizeof(GCSegInfo));
00456 #ifdef DEBUG
00457     {
00458     char str[256];
00459     sprintf(str, "[1] Allocated %ld bytes at %p\n",
00460         (long) sizeof(GCSegInfo), segInfo);
00461     OutputDebugString(str);
00462     }
00463 #endif
00464     if (!segInfo) {
00465     return 0;
00466     }
00467 
00468 #if defined(WIN16)
00469     if (requestedSize > segmentSize) {
00470     PR_DELETE(segInfo);
00471     return 0;
00472     }
00473 #endif
00474 
00475     /* Get more memory from the OS */
00476     if (exactly) {
00477     allocSize = requestedSize;
00478     base = (char *) PR_MALLOC(requestedSize);
00479     } else {
00480     allocSize = requestedSize;
00481     allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
00482     allocSize <<= _pr_pageShift;
00483     base = (char*)_MD_GrowGCHeap(&allocSize);
00484     }
00485     if (!base) {
00486     PR_DELETE(segInfo);
00487     return 0;
00488     }
00489 
00490     nhbits = (PRInt32)(
00491         (allocSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2);
00492     nhbytes = ((nhbits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
00493     * sizeof(PRWord);
00494 
00495     /* Get bitmap memory from malloc heap */
00496 #if defined(WIN16)
00497     PR_ASSERT( nhbytes < MAX_ALLOC_SIZE );
00498 #endif
00499     hbits = (PRWord *) PR_CALLOC((PRUint32)nhbytes);
00500     if (!hbits) {
00501     /* Loser! */
00502     PR_DELETE(segInfo);
00503     if (exactly) {
00504         PR_DELETE(base);
00505     } else {
00506       /* XXX do something about this */
00507       /* _MD_FreeGCSegment(base, allocSize); */
00508     }
00509     return 0;
00510     }
00511 
00512     /*
00513     ** Setup new segment.
00514     */
00515     sp = &segs[nsegs++];
00516     segInfo->base = sp->base = base;
00517     segInfo->limit = sp->limit = base + allocSize;
00518     segInfo->hbits = sp->hbits = hbits;
00519     sp->info = segInfo;
00520     segInfo->fromMalloc = exactly;
00521     memset(base, 0, allocSize);
00522 
00523 #ifdef GCMETER
00524     if (_pr_gcMeter & _GC_METER_GROWTH) {
00525         fprintf(stderr, "[GC: new segment base=%p size=%ld]\n",
00526                 sp->base, (long) allocSize);
00527     }
00528 #endif    
00529 
00530     _pr_gcData.allocMemory += allocSize;
00531     _pr_gcData.freeMemory  += allocSize;
00532 
00533     if (!exactly) {
00534     PRInt32 bin;
00535 
00536         /* Put free memory into a freelist bin */
00537         cp = (GCFreeChunk *) base;
00538         cp->segment = sp;
00539         cp->chunkSize = allocSize;
00540         InlineBinNumber(bin, allocSize)
00541         cp->next = bins[bin];
00542         bins[bin] = cp;
00543     if (bin < minBin) minBin = bin;
00544     if (bin > maxBin) maxBin = bin;
00545     } else {
00546         /*
00547         ** When exactly allocating the entire segment is given over to a
00548         ** single object to prevent fragmentation
00549         */
00550     }
00551 
00552     if (!_pr_gcData.lowSeg) {
00553     _pr_gcData.lowSeg  = (PRWord*) sp->base;
00554     _pr_gcData.highSeg = (PRWord*) sp->limit;
00555     } else {
00556     if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
00557         _pr_gcData.lowSeg = (PRWord*) sp->base;
00558     }
00559     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
00560         _pr_gcData.highSeg = (PRWord*) sp->limit;
00561     }
00562     }
00563 
00564     /* 
00565     ** Get rid of the GC pointer in case it shows up in some uninitialized
00566     ** local stack variable later (while scanning the C stack looking for
00567     ** roots).
00568     */ 
00569     memset(&base, 0, sizeof(base));  /* optimizers beware */
00570 
00571     PR_LOG(_pr_msgc_lm, PR_LOG_WARNING, ("grow heap: total gc memory now %d",
00572                       _pr_gcData.allocMemory));
00573 
00574     return sp;
00575 }
00576 
00577 #ifdef USE_EXTEND_HEAP
00578 static PRBool ExtendHeap(PRInt32 requestedSize) {
00579   GCSeg* sp;
00580   PRUint32 allocSize;
00581   PRInt32 oldSize, newSize;
00582   PRInt32 newHBits, newHBytes;
00583   PRInt32 oldHBits, oldHBytes;
00584   PRWord* hbits;
00585   GCFreeChunk* cp;
00586   PRInt32 bin;
00587 
00588   /* Can't extend nothing */
00589   if (nsegs == 0) return PR_FALSE;
00590 
00591   /* Round up requested size to the size of a page */
00592   allocSize = (PRUint32) requestedSize;
00593   allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
00594   allocSize <<= _pr_pageShift;
00595 
00596   /* Malloc some memory for the new hbits array */
00597   sp = segs;
00598   oldSize = sp->limit - sp->base;
00599   newSize = oldSize + allocSize;
00600   newHBits = (newSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
00601   newHBytes = ((newHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
00602     * sizeof(PRWord);
00603   hbits = (PRWord*) PR_MALLOC(newHBytes);
00604   if (0 == hbits) return PR_FALSE;
00605 
00606   /* Attempt to extend the last segment by the desired amount */
00607   if (_MD_ExtendGCHeap(sp->base, oldSize, newSize)) {
00608     oldHBits = (oldSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
00609     oldHBytes = ((oldHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
00610       * sizeof(PRWord);
00611 
00612     /* Copy hbits from old memory into new memory */
00613     memset(hbits, 0, newHBytes);
00614     memcpy(hbits, sp->hbits, oldHBytes);
00615     PR_DELETE(sp->hbits);
00616     memset(sp->base + oldSize, 0, allocSize);
00617 
00618     /* Adjust segment state */
00619     sp->limit += allocSize;
00620     sp->hbits = hbits;
00621     sp->info->limit = sp->limit;
00622     sp->info->hbits = hbits;
00623 
00624     /* Put free memory into a freelist bin */
00625     cp = (GCFreeChunk *) (sp->base + oldSize);
00626     cp->segment = sp;
00627     cp->chunkSize = allocSize;
00628     InlineBinNumber(bin, allocSize)
00629     cp->next = bins[bin];
00630     bins[bin] = cp;
00631     if (bin < minBin) minBin = bin;
00632     if (bin > maxBin) maxBin = bin;
00633 
00634     /* Prevent a pointer that points to the free memory from showing
00635        up on the call stack later on */
00636     memset(&cp, 0, sizeof(cp));
00637 
00638     /* Update heap brackets and counters */
00639     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
00640       _pr_gcData.highSeg = (PRWord*) sp->limit;
00641     }
00642     _pr_gcData.allocMemory += allocSize;
00643     _pr_gcData.freeMemory  += allocSize;
00644 
00645     return PR_TRUE;
00646   }
00647   PR_DELETE(hbits);
00648   return PR_FALSE;
00649 }
00650 #endif /* USE_EXTEND_HEAP */
00651 
00652 static GCSeg *GrowHeapExactly(PRInt32 requestedSize)
00653 {
00654     GCSeg *sp = DoGrowHeap(requestedSize, PR_TRUE);
00655     return sp;
00656 }
00657 
00658 static PRBool GrowHeap(PRInt32 requestedSize)
00659 {
00660   void *p;
00661 #ifdef USE_EXTEND_HEAP
00662   if (ExtendHeap(requestedSize)) {
00663     return PR_TRUE;
00664   }
00665 #endif
00666   p = DoGrowHeap(requestedSize, PR_FALSE);
00667   return (p != NULL ? PR_TRUE : PR_FALSE);
00668 }
00669 
00670 /*
00671 ** Release a segment when it is entirely free.
00672 */
00673 static void ShrinkGCHeap(GCSeg *sp)
00674 {
00675 #ifdef GCMETER
00676     if (_pr_gcMeter & _GC_METER_GROWTH) {
00677         fprintf(stderr, "[GC: free segment base=%p size=%ld]\n",
00678                 sp->base, (long) (sp->limit - sp->base));
00679     }
00680 #endif    
00681 
00682     /*
00683      * Put segment onto free seginfo list (we can't call free right now
00684      * because we have the GC lock and all of the other threads are
00685      * suspended; if one of them has the malloc lock we would deadlock)
00686      */
00687     sp->info->next = freeSegs;
00688     freeSegs = sp->info;
00689     collectorCleanupNeeded = 1;
00690     _pr_gcData.allocMemory -= sp->limit - sp->base;
00691     if (sp == lastInHeap) lastInHeap = 0;
00692 
00693     /* Squish out disappearing segment from segment table */
00694     --nsegs;
00695     if ((sp - segs) != nsegs) {
00696         *sp = segs[nsegs];
00697     } else {
00698         sp->base = 0;
00699         sp->limit = 0;
00700         sp->hbits = 0;
00701     sp->info = 0;
00702     }
00703 
00704     /* Recalculate the lowSeg and highSeg values */
00705     _pr_gcData.lowSeg  = (PRWord*) segs[0].base;
00706     _pr_gcData.highSeg = (PRWord*) segs[0].limit;
00707     for (sp = segs; sp < &segs[nsegs]; sp++) {
00708     if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
00709         _pr_gcData.lowSeg = (PRWord*) sp->base;
00710     }
00711     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
00712         _pr_gcData.highSeg = (PRWord*) sp->limit;
00713     }
00714     }
00715 }
00716 
00717 static void FreeSegments(void)
00718 {
00719     GCSegInfo *si;
00720 
00721     while (0 != freeSegs) {
00722     LOCK_GC();
00723     si = freeSegs;
00724     if (si) {
00725         freeSegs = si->next;
00726     }
00727     UNLOCK_GC();
00728 
00729     if (!si) {
00730         break;
00731     }
00732     PR_DELETE(si->base);
00733     PR_DELETE(si->hbits);
00734     PR_DELETE(si);
00735     }
00736 }
00737 
00738 /************************************************************************/
00739 
00740 void ScanScanQ(GCScanQ *iscan)
00741 {
00742     PRWord *p;
00743     PRWord **pp;
00744     PRWord **epp;
00745     GCScanQ nextQ, *scan, *next, *temp;
00746     CollectorType *ct;
00747 
00748     if (!iscan->queued) return;
00749 
00750     _GCTRACE(GC_MARK, ("begin scanQ @ 0x%x (%d)", iscan, iscan->queued));
00751     scan = iscan;
00752     next = &nextQ;
00753     while (scan->queued) {
00754        _GCTRACE(GC_MARK, ("continue scanQ @ 0x%x (%d)", scan, scan->queued));
00755     /*
00756      * Set pointer to current scanQ so that _pr_gcData.livePointer
00757      * can find it.
00758      */
00759     pScanQ = next;
00760     next->queued = 0;
00761 
00762     /* Now scan the scan Q */
00763     pp = scan->q;
00764     epp = &scan->q[scan->queued];
00765     scan->queued = 0;
00766     while (pp < epp) {
00767         p = *pp++;
00768         ct = &_pr_collectorTypes[GET_TYPEIX(p[0])];
00769         PR_ASSERT(0 != ct->gctype.scan);
00770         /* Scan object ... */
00771         (*ct->gctype.scan)(p + 1);
00772     }
00773 
00774     /* Exchange pointers so that we scan next */
00775     temp = scan;
00776     scan = next;
00777     next = temp;
00778     }
00779 
00780     pScanQ = iscan;
00781     PR_ASSERT(nextQ.queued == 0);
00782     PR_ASSERT(iscan->queued == 0);
00783 }
00784 
00785 /*
00786 ** Called during root finding step to identify "root" pointers into the
00787 ** GC heap. First validate if it is a real heap pointer and then mark the
00788 ** object being pointed to and add it to the scan Q for eventual
00789 ** scanning.
00790 */
00791 static void PR_CALLBACK ProcessRootBlock(void **base, PRInt32 count)
00792 {
00793     GCSeg *sp;
00794     PRWord *p0, *p, h, tix, *low, *high, *segBase;
00795     CollectorType *ct;
00796 #ifdef DEBUG
00797     void **base0 = base;
00798 #endif
00799 
00800     low = _pr_gcData.lowSeg;
00801     high = _pr_gcData.highSeg;
00802     while (--count >= 0) {
00803         p0 = (PRWord*) *base++;
00804         /*
00805         ** XXX:  
00806         ** Until Win16 maintains lowSeg and highSeg correctly,
00807         ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
00808         ** Allways scan through the segment list
00809         */
00810 #if !defined(WIN16)
00811         if (p0 < low) continue;                  /* below gc heap */
00812         if (p0 >= high) continue;                /* above gc heap */
00813 #endif
00814         /* NOTE: inline expansion of InHeap */
00815         /* Find segment */
00816     sp = lastInHeap;
00817         if (!sp || !IN_SEGMENT(sp,p0)) {
00818             GCSeg *esp;
00819             sp = segs;
00820         esp = segs + nsegs;
00821             for (; sp < esp; sp++) {
00822                 if (IN_SEGMENT(sp, p0)) {
00823                     lastInHeap = sp;
00824                     goto find_object;
00825                 }
00826             }
00827             continue;
00828         }
00829 
00830       find_object:
00831         /* NOTE: Inline expansion of FindObject */
00832         /* Align p to it's proper boundary before we start fiddling with it */
00833         p = (PRWord*) ((PRWord)p0 & ~(PR_BYTES_PER_WORD-1L));
00834         segBase = (PRWord *) sp->base;
00835         do {
00836             if (IS_HBIT(sp, p)) {
00837                 goto winner;
00838             }
00839             p--;
00840         } while (p >= segBase);
00841 
00842         /*
00843         ** We have a pointer into the heap, but it has no header
00844         ** bit. This means that somehow the very first object in the heap
00845         ** doesn't have a header. This is impossible so when debugging
00846         ** lets abort.
00847         */
00848 #ifdef DEBUG
00849         PR_Abort();
00850 #endif
00851 
00852       winner:
00853         h = p[0];
00854         if ((h & MARK_BIT) == 0) {
00855 #ifdef DEBUG
00856             _GCTRACE(GC_ROOTS,
00857             ("root 0x%p (%d) base0=%p off=%d",
00858              p, OBJ_BYTES(h), base0, (base-1) - base0));
00859 #endif
00860 
00861             /* Mark the root we just found */
00862             p[0] = h | MARK_BIT;
00863 
00864             /*
00865          * See if object we just found needs scanning. It must
00866          * have a scan function to be placed on the scanQ.
00867          */
00868             tix = (PRWord)GET_TYPEIX(h);
00869         ct = &_pr_collectorTypes[tix];
00870         if (0 == ct->gctype.scan) {
00871         continue;
00872         }
00873 
00874             /*
00875             ** Put a pointer onto the scan Q. We use the scan Q to avoid
00876             ** deep recursion on the C call stack. Objects are added to
00877             ** the scan Q until the scan Q fills up. At that point we
00878             ** make a call to ScanScanQ which proceeds to scan each of
00879             ** the objects in the Q. This limits the recursion level by a
00880             ** large amount though the stack frames get larger to hold
00881             ** the GCScanQ's.
00882             */
00883             pScanQ->q[pScanQ->queued++] = p;
00884             if (pScanQ->queued == MAX_SCAN_Q) {
00885                 METER(_pr_scanDepth++);
00886                 ScanScanQ(pScanQ);
00887             }
00888         }
00889     }
00890 }
00891 
00892 static void PR_CALLBACK ProcessRootPointer(void *ptr)
00893 {
00894   PRWord *p0, *p, h, tix, *segBase;
00895   GCSeg* sp;
00896   CollectorType *ct;
00897 
00898   p0 = (PRWord*) ptr;
00899 
00900   /*
00901   ** XXX:  
00902   ** Until Win16 maintains lowSeg and highSeg correctly,
00903   ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
00904   ** Allways scan through the segment list
00905   */
00906 #if !defined(WIN16)
00907   if (p0 < _pr_gcData.lowSeg) return;                  /* below gc heap */
00908   if (p0 >= _pr_gcData.highSeg) return;                /* above gc heap */
00909 #endif
00910 
00911   /* NOTE: inline expansion of InHeap */
00912   /* Find segment */
00913   sp = lastInHeap;
00914   if (!sp || !IN_SEGMENT(sp,p0)) {
00915     GCSeg *esp;
00916     sp = segs;
00917     esp = segs + nsegs;
00918     for (; sp < esp; sp++) {
00919       if (IN_SEGMENT(sp, p0)) {
00920     lastInHeap = sp;
00921     goto find_object;
00922       }
00923     }
00924     return;
00925   }
00926 
00927  find_object:
00928   /* NOTE: Inline expansion of FindObject */
00929   /* Align p to it's proper boundary before we start fiddling with it */
00930     p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
00931     segBase = (PRWord *) sp->base;
00932     do {
00933       if (IS_HBIT(sp, p)) {
00934     goto winner;
00935       }
00936       p--;
00937     } while (p >= segBase);
00938 
00939     /*
00940     ** We have a pointer into the heap, but it has no header
00941     ** bit. This means that somehow the very first object in the heap
00942     ** doesn't have a header. This is impossible so when debugging
00943     ** lets abort.
00944     */
00945 #ifdef DEBUG
00946     PR_Abort();
00947 #endif
00948 
00949  winner:
00950   h = p[0];
00951   if ((h & MARK_BIT) == 0) {
00952 #ifdef DEBUG
00953     _GCTRACE(GC_ROOTS, ("root 0x%p (%d)", p, OBJ_BYTES(h)));
00954 #endif
00955 
00956     /* Mark the root we just found */
00957     p[0] = h | MARK_BIT;
00958 
00959     /*
00960      * See if object we just found needs scanning. It must
00961      * have a scan function to be placed on the scanQ.
00962      */
00963     tix = (PRWord)GET_TYPEIX(h);
00964     ct = &_pr_collectorTypes[tix];
00965     if (0 == ct->gctype.scan) {
00966       return;
00967     }
00968 
00969     /*
00970     ** Put a pointer onto the scan Q. We use the scan Q to avoid
00971     ** deep recursion on the C call stack. Objects are added to
00972     ** the scan Q until the scan Q fills up. At that point we
00973     ** make a call to ScanScanQ which proceeds to scan each of
00974     ** the objects in the Q. This limits the recursion level by a
00975     ** large amount though the stack frames get larger to hold
00976     ** the GCScanQ's.
00977     */
00978     pScanQ->q[pScanQ->queued++] = p;
00979     if (pScanQ->queued == MAX_SCAN_Q) {
00980       METER(_pr_scanDepth++);
00981       ScanScanQ(pScanQ);
00982     }
00983   }
00984 }
00985 
00986 /************************************************************************/
00987 
00988 /*
00989 ** Empty the freelist for each segment. This is done to make sure that
00990 ** the root finding step works properly (otherwise, if we had a pointer
00991 ** into a free section, we might not find its header word and abort in
00992 ** FindObject)
00993 */
00994 static void EmptyFreelists(void)
00995 {
00996     GCFreeChunk *cp;
00997     GCFreeChunk *next;
00998     GCSeg *sp;
00999     PRWord *p;
01000     PRInt32 chunkSize;
01001     PRInt32 bin;
01002 
01003     /*
01004     ** Run over the freelist and make all of the free chunks look like
01005     ** object debris.
01006     */
01007     for (bin = 0; bin <= NUM_BINS-1; bin++) {
01008         cp = bins[bin];
01009         while (cp) {
01010             next = cp->next;
01011             sp = cp->segment;
01012             chunkSize = cp->chunkSize >> BYTES_PER_WORD_LOG2;
01013             p = (PRWord*) cp;
01014             PR_ASSERT(chunkSize != 0);
01015             p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
01016             SET_HBIT(sp, p);
01017             cp = next;
01018         }
01019         bins[bin] = 0;
01020     }
01021     minBin = NUM_BINS - 1;
01022     maxBin = 0;
01023 }
01024 
01025 typedef struct GCBlockEnd {
01026     PRInt32   check;
01027 #ifdef GC_CHECK
01028     PRInt32   requestedBytes;
01029 #endif
01030 #ifdef GC_STATS
01031     PRInt32   bin;
01032     PRInt64   allocTime; 
01033 #endif
01034 #ifdef GC_TRACEROOTS
01035     PRInt32   traceGeneration;     
01036 #endif
01037 } GCBlockEnd;
01038 
01039 #define PR_BLOCK_END 0xDEADBEEF
01040 
01041 /************************************************************************/
01042 
01043 #ifdef GC_STATS
01044 
01045 typedef struct GCStat {
01046     PRInt32   nallocs;
01047     double    allocTime;
01048     double    allocTimeVariance;
01049     PRInt32   nfrees;
01050     double    lifetime;
01051     double    lifetimeVariance;
01052 } GCStat;
01053 
01054 #define GCSTAT_BINS  NUM_BINS
01055 
01056 GCStat gcstats[GCSTAT_BINS];
01057 
01058 #define GCLTFREQ_BINS       NUM_BINS
01059 
01060 PRInt32 gcltfreq[GCSTAT_BINS][GCLTFREQ_BINS];
01061 
01062 #include <math.h>
01063 
01064 static char* 
01065 pr_GetSizeString(PRUint32 size)
01066 {
01067     char* sizeStr;
01068     if (size < 1024)
01069        sizeStr = PR_smprintf("<= %ld", size);
01070     else if (size < 1024 * 1024)
01071        sizeStr = PR_smprintf("<= %ldk", size / 1024);
01072     else 
01073        sizeStr = PR_smprintf("<= %ldM", size / (1024 * 1024));
01074     return sizeStr;
01075 }
01076 
01077 static void
01078 pr_FreeSizeString(char *sizestr)
01079 {
01080        PR_smprintf_free(sizestr);
01081 }
01082 
01083 
01084 static void
01085 pr_PrintGCAllocStats(FILE* out)
01086 {
01087     PRInt32 i, j;
01088     _PR_DebugPrint(out, "\n--Allocation-Stats-----------------------------------------------------------");
01089     _PR_DebugPrint(out, "\n--Obj-Size----Count-----Avg-Alloc-Time-----------Avg-Lifetime---------%%Freed-\n");
01090     for (i = 0; i < GCSTAT_BINS; i++) {
01091        GCStat stat = gcstats[i];
01092        double allocTimeMean = 0.0, allocTimeVariance = 0.0, lifetimeMean = 0.0, lifetimeVariance = 0.0;
01093        PRUint32 maxSize = (1 << i);
01094        char* sizeStr;
01095        if (stat.nallocs != 0.0) {
01096            allocTimeMean = stat.allocTime / stat.nallocs;
01097            allocTimeVariance = fabs(stat.allocTimeVariance / stat.nallocs - allocTimeMean * allocTimeMean);
01098        }
01099        if (stat.nfrees != 0.0) {
01100            lifetimeMean = stat.lifetime / stat.nfrees;
01101            lifetimeVariance = fabs(stat.lifetimeVariance / stat.nfrees - lifetimeMean * lifetimeMean);
01102        }
01103        sizeStr = pr_GetSizeString(maxSize);
01104        _PR_DebugPrint(out, "%10s %8lu %10.3f +- %10.3f %10.3f +- %10.3f (%2ld%%)\n",
01105                      sizeStr, stat.nallocs,
01106                      allocTimeMean, sqrt(allocTimeVariance),
01107                      lifetimeMean, sqrt(lifetimeVariance),
01108                      (stat.nallocs ? (stat.nfrees * 100 / stat.nallocs) : 0));
01109        pr_FreeSizeString(sizeStr);
01110     }
01111     _PR_DebugPrint(out, "--Lifetime-Frequency-Counts----------------------------------------------------\n");
01112     _PR_DebugPrint(out, "size\\cnt");
01113     for (j = 0; j < GCLTFREQ_BINS; j++) {
01114        _PR_DebugPrint(out, "\t%lu", j);
01115     }
01116     _PR_DebugPrint(out, "\n");
01117     for (i = 0; i < GCSTAT_BINS; i++) {
01118        PRInt32* freqs = gcltfreq[i];
01119        _PR_DebugPrint(out, "%lu", (1 << i));
01120        for (j = 0; j < GCLTFREQ_BINS; j++) {
01121            _PR_DebugPrint(out, "\t%lu", freqs[j]);
01122        }
01123        _PR_DebugPrint(out, "\n");
01124     }
01125     _PR_DebugPrint(out, "-------------------------------------------------------------------------------\n");
01126 }
01127 
01128 PR_PUBLIC_API(void)
01129 PR_PrintGCAllocStats(void)
01130 {
01131     pr_PrintGCAllocStats(stderr);
01132 }
01133 
01134 #endif /* GC_STATS */
01135 
01136 /************************************************************************/
01137 
01138 /*
01139 ** Sweep a segment, cleaning up all of the debris. Coallese the debris
01140 ** into GCFreeChunk's which are added to the freelist bins.
01141 */
01142 static PRBool SweepSegment(GCSeg *sp)
01143 {
01144     PRWord h, tix;
01145     PRWord *p;
01146     PRWord *np;
01147     PRWord *limit;
01148     GCFreeChunk *cp;
01149     PRInt32 bytes, chunkSize, segmentSize, totalFree;
01150     CollectorType *ct;
01151     PRInt32 bin;
01152 
01153     /*
01154     ** Now scan over the segment's memory in memory order, coallescing
01155     ** all of the debris into a FreeChunk list.
01156     */
01157     totalFree = 0;
01158     segmentSize = sp->limit - sp->base;
01159     p = (PRWord *) sp->base;
01160     limit = (PRWord *) sp->limit;
01161     PR_ASSERT(segmentSize > 0);
01162     while (p < limit) {
01163     chunkSize = 0;
01164     cp = (GCFreeChunk *) p;
01165 
01166     /* Attempt to coallesce any neighboring free objects */
01167     for (;;) {
01168         PR_ASSERT(IS_HBIT(sp, p) != 0);
01169         h = p[0];
01170         bytes = OBJ_BYTES(h);
01171         PR_ASSERT(bytes != 0);
01172         np = (PRWord *) ((char *)p + bytes);
01173         tix = (PRWord)GET_TYPEIX(h);
01174         if ((h & MARK_BIT) && (tix != FREE_MEMORY_TYPEIX)) {
01175 #ifdef DEBUG
01176         if (tix != FREE_MEMORY_TYPEIX) {
01177             PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
01178         }
01179 #endif
01180         p[0] = h & ~(MARK_BIT|FINAL_BIT);
01181               _GCTRACE(GC_SWEEP, ("busy 0x%x (%d)", p, bytes));
01182               break;
01183            }
01184            _GCTRACE(GC_SWEEP, ("free 0x%x (%d)", p, bytes));
01185 
01186            /* Found a free object */
01187 #ifdef GC_STATS
01188            {
01189               PRInt32 userSize = bytes - sizeof(GCBlockEnd);
01190               GCBlockEnd* end = (GCBlockEnd*)((char*)p + userSize);
01191               if (userSize >= 0 && end->check == PR_BLOCK_END) {
01192                   PRInt64 now = PR_Now();
01193                   double nowd, delta;
01194                   PRInt32 freq;
01195                   LL_L2D(nowd, now);
01196                   delta = nowd - end->allocTime;
01197                   gcstats[end->bin].nfrees++;
01198                   gcstats[end->bin].lifetime += delta;
01199                   gcstats[end->bin].lifetimeVariance += delta * delta;
01200 
01201                   InlineBinNumber(freq, delta);
01202                   gcltfreq[end->bin][freq]++;
01203 
01204                   end->check = 0;
01205               }
01206            }
01207 #endif
01208         CLEAR_HBIT(sp, p);
01209         ct = &_pr_collectorTypes[tix];
01210         if (0 != ct->gctype.free) {
01211                 (*ct->gctype.free)(p + 1);
01212             }
01213         chunkSize = chunkSize + bytes;
01214         if (np == limit) {
01215         /* Found the end of heap */
01216         break;
01217         }
01218         PR_ASSERT(np < limit);
01219         p = np;
01220     }
01221 
01222     if (chunkSize) {
01223         _GCTRACE(GC_SWEEP, ("free chunk 0x%p to 0x%p (%d)",
01224                    cp, (char*)cp + chunkSize - 1, chunkSize));
01225         if (chunkSize < MIN_FREE_CHUNK_BYTES) {
01226         /* Lost a tiny fragment until (maybe) next time */
01227                 METER(meter.wastedBytes += chunkSize);
01228         p = (PRWord *) cp;
01229         chunkSize >>= BYTES_PER_WORD_LOG2;
01230         PR_ASSERT(chunkSize != 0);
01231         p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
01232         SET_HBIT(sp, p);
01233         } else {
01234                 /* See if the chunk constitutes the entire segment */
01235                 if (chunkSize == segmentSize) {
01236                     /* Free up the segment right now */
01237             if (sp->info->fromMalloc) {
01238                     ShrinkGCHeap(sp);
01239                     return PR_TRUE;
01240                 }
01241                 }
01242 
01243                 /* Put free chunk into the appropriate bin */
01244                 cp->segment = sp;
01245         cp->chunkSize = chunkSize;
01246                 InlineBinNumber(bin, chunkSize)
01247                 cp->next = bins[bin];
01248                 bins[bin] = cp;
01249         if (bin < minBin) minBin = bin;
01250         if (bin > maxBin) maxBin = bin;
01251 
01252         /* Zero swept memory now */
01253         memset(cp+1, 0, chunkSize - sizeof(*cp));
01254                 METER(meter.numFreeChunks++);
01255         totalFree += chunkSize;
01256         }
01257     }
01258 
01259     /* Advance to next object */
01260     p = np;
01261     }
01262 
01263     PR_ASSERT(totalFree <= segmentSize);
01264 
01265     _pr_gcData.freeMemory += totalFree;
01266     _pr_gcData.busyMemory += (sp->limit - sp->base) - totalFree;
01267     return PR_FALSE;
01268 }
01269 
01270 /************************************************************************/
01271 
01272 /* This is a list of all the objects that are finalizable. This is not
01273    the list of objects that are awaiting finalization because they
01274    have been collected. */
01275 PRCList _pr_finalizeableObjects;
01276 
01277 /* This is the list of objects that are awaiting finalization because
01278    they have been collected. */
01279 PRCList _pr_finalQueue;
01280 
01281 /* Each object that requires finalization has one of these objects
01282    allocated as well. The GCFinal objects are put on the
01283    _pr_finalizeableObjects list until the object is collected at which
01284    point the GCFinal object is moved to the _pr_finalQueue */
01285 typedef struct GCFinalStr {
01286     PRCList links;
01287     PRWord *object;
01288 } GCFinal;
01289 
01290 /* Find pointer to GCFinal struct from the list linkaged embedded in it */
01291 #define FinalPtr(_qp) \
01292     ((GCFinal*) ((char*) (_qp) - offsetof(GCFinal,links)))
01293 
01294 static GCFinal *AllocFinalNode(void)
01295 {
01296     return PR_NEWZAP(GCFinal);
01297 }
01298 
01299 static void FreeFinalNode(GCFinal *node)
01300 {
01301     PR_DELETE(node);
01302 }
01303 
01304 /*
01305 ** Prepare for finalization. At this point in the GC cycle we have
01306 ** identified all of the live objects. For each object on the
01307 ** _pr_finalizeableObjects list see if the object is alive or dead. If
01308 ** it's dead, resurrect it and move it from the _pr_finalizeableObjects
01309 ** list to the _pr_finalQueue (object's only get finalized once).
01310 **
01311 ** Once _pr_finalizeableObjects has been processed we can finish the
01312 ** GC and free up memory and release the threading lock. After that we
01313 ** can invoke the finalization procs for each object that is on the
01314 ** _pr_finalQueue.
01315 */
01316 static void PrepareFinalize(void)
01317 {
01318     PRCList *qp;
01319     GCFinal *fp;
01320     PRWord h;
01321     PRWord *p;
01322     void (PR_CALLBACK *livePointer)(void *ptr);
01323 #ifdef DEBUG
01324     CollectorType *ct;
01325 #endif
01326 
01327     /* This must be done under the same lock that the finalizer uses */
01328     PR_ASSERT( GC_IS_LOCKED() );
01329 
01330     /* cache this ptr */
01331     livePointer = _pr_gcData.livePointer;
01332 
01333     /*
01334      * Pass #1: Identify objects that are to be finalized, set their
01335      * FINAL_BIT.
01336      */
01337     qp = _pr_finalizeableObjects.next;
01338     while (qp != &_pr_finalizeableObjects) {
01339     fp = FinalPtr(qp);
01340     qp = qp->next;
01341     h = fp->object[0];        /* Grab header word */
01342     if (h & MARK_BIT) {
01343         /* Object is already alive */
01344         continue;
01345     }
01346 
01347 #ifdef DEBUG
01348     ct = &_pr_collectorTypes[GET_TYPEIX(h)];
01349     PR_ASSERT((0 != ct->flags) && (0 != ct->gctype.finalize));
01350 #endif
01351     fp->object[0] |= FINAL_BIT;
01352     _GCTRACE(GC_FINAL, ("moving %p (%d) to finalQueue",
01353                fp->object, OBJ_BYTES(h)));
01354     }
01355 
01356     /*
01357      * Pass #2: For each object that is going to be finalized, move it to
01358      * the finalization queue and resurrect it
01359      */
01360     qp = _pr_finalizeableObjects.next;
01361     while (qp != &_pr_finalizeableObjects) {
01362     fp = FinalPtr(qp);
01363     qp = qp->next;
01364     h = fp->object[0];        /* Grab header word */
01365     if ((h & FINAL_BIT) == 0) {
01366         continue;
01367     }
01368 
01369     /* Resurrect the object and any objects it refers to */
01370         p = &fp->object[1];
01371     (*livePointer)(p);
01372     PR_REMOVE_LINK(&fp->links);
01373     PR_APPEND_LINK(&fp->links, &_pr_finalQueue);
01374     }
01375 }
01376 
01377 /*
01378 ** Scan the finalQ, marking each and every object on it live.  This is
01379 ** necessary because we might do a GC before objects that are on the
01380 ** final queue get finalized. Since there are no other references
01381 ** (otherwise they would be on the final queue), we have to scan them.
01382 ** This really only does work if we call the GC before the finalizer
01383 ** has a chance to do its job.
01384 */
01385 extern void PR_CALLBACK _PR_ScanFinalQueue(void *notused)
01386 {
01387 #ifdef XP_MAC
01388 #pragma unused (notused)
01389 #endif
01390     PRCList *qp;
01391     GCFinal *fp;
01392     PRWord *p;
01393     void ( PR_CALLBACK *livePointer)(void *ptr);
01394 
01395     livePointer = _pr_gcData.livePointer;
01396     qp = _pr_finalQueue.next;
01397     while (qp != &_pr_finalQueue) {
01398     fp = FinalPtr(qp);
01399        _GCTRACE(GC_FINAL, ("marking 0x%x (on final queue)", fp->object));
01400         p = &fp->object[1];
01401     (*livePointer)(p);
01402     qp = qp->next;
01403     }
01404 }
01405 
01406 void PR_CALLBACK FinalizerLoop(void* unused)
01407 {
01408 #ifdef XP_MAC
01409 #pragma unused (unused)
01410 #endif
01411     GCFinal *fp;
01412     PRWord *p;
01413     PRWord h, tix;
01414     CollectorType *ct;
01415 
01416     LOCK_GC();
01417     for (;;) {
01418        p = 0; h = 0;        /* don't let the gc find these pointers */
01419     while (PR_CLIST_IS_EMPTY(&_pr_finalQueue))
01420         PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
01421 
01422     _GCTRACE(GC_FINAL, ("begin finalization"));
01423     while (_pr_finalQueue.next != &_pr_finalQueue) {
01424         fp = FinalPtr(_pr_finalQueue.next);
01425         PR_REMOVE_LINK(&fp->links);
01426         p = fp->object;
01427 
01428         h = p[0];        /* Grab header word */
01429         tix = (PRWord)GET_TYPEIX(h);
01430         ct = &_pr_collectorTypes[tix];
01431            _GCTRACE(GC_FINAL, ("finalize 0x%x (%d)", p, OBJ_BYTES(h)));
01432 
01433         /*
01434         ** Give up the GC lock so that other threads can allocate memory
01435         ** while this finalization method is running. Get it back
01436         ** afterwards so that the list remains thread safe.
01437         */
01438         UNLOCK_GC();
01439         FreeFinalNode(fp);
01440         PR_ASSERT(ct->gctype.finalize != 0);
01441         (*ct->gctype.finalize)(p + 1);
01442         LOCK_GC();
01443     }
01444     _GCTRACE(GC_FINAL, ("end finalization"));
01445     PR_Notify(_pr_gcData.lock);
01446     }
01447 }
01448 
01449 static void NotifyFinalizer(void)
01450 {
01451     if (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
01452     PR_ASSERT( GC_IS_LOCKED() );
01453     PR_Notify(_pr_gcData.lock);
01454     }
01455 }
01456 
01457 void _PR_CreateFinalizer(PRThreadScope scope)
01458 {
01459     if (!_pr_gcData.finalizer) {
01460     _pr_gcData.finalizer = PR_CreateThreadGCAble(PR_SYSTEM_THREAD,
01461                                         FinalizerLoop, 0,
01462                                         PR_PRIORITY_LOW, scope,
01463                                         PR_UNJOINABLE_THREAD, 0);
01464     
01465     if (_pr_gcData.finalizer == NULL)
01466         /* We are doomed if we can't start the finalizer */
01467         PR_Abort();
01468 
01469     }
01470 }
01471 
01472 void pr_FinalizeOnExit(void)
01473 {
01474 #ifdef DEBUG_warren
01475     OutputDebugString("### Doing finalize-on-exit pass\n");
01476 #endif
01477     PR_ForceFinalize();
01478 #ifdef DEBUG_warren
01479     OutputDebugString("### Finalize-on-exit complete. Dumping object left to memory.out\n");
01480     PR_DumpMemorySummary();
01481     PR_DumpMemory(PR_TRUE);
01482 #endif
01483 }
01484 
01485 PR_IMPLEMENT(void) PR_ForceFinalize()
01486 {
01487     LOCK_GC();
01488     NotifyFinalizer();
01489     while (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
01490     PR_ASSERT( GC_IS_LOCKED() );
01491     (void) PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
01492     }
01493     UNLOCK_GC();
01494 
01495     /* XXX I don't know how to make it wait (yet) */
01496 }
01497 
01498 /************************************************************************/
01499 
01500 typedef struct GCWeakStr {
01501     PRCList links;
01502     PRWord *object;
01503 } GCWeak;
01504 
01505 /*
01506 ** Find pointer to GCWeak struct from the list linkaged embedded in it
01507 */
01508 #define WeakPtr(_qp) \
01509     ((GCWeak*) ((char*) (_qp) - offsetof(GCWeak,links)))
01510 
01511 PRCList _pr_weakLinks = PR_INIT_STATIC_CLIST(&_pr_weakLinks);
01512 PRCList _pr_freeWeakLinks = PR_INIT_STATIC_CLIST(&_pr_freeWeakLinks);
01513 
01514 #define WEAK_FREELIST_ISEMPTY() (_pr_freeWeakLinks.next == &_pr_freeWeakLinks)
01515 
01516 /*
01517  * Keep objects referred to by weak free list alive until they can be
01518  * freed
01519  */
01520 static void PR_CALLBACK ScanWeakFreeList(void *notused) {
01521 #ifdef XP_MAC
01522 #pragma unused (notused)
01523 #endif
01524     PRCList *qp = _pr_freeWeakLinks.next;
01525     while (qp != &_pr_freeWeakLinks) {
01526     GCWeak *wp = WeakPtr(qp);
01527     qp = qp->next;
01528     ProcessRootPointer(wp->object);
01529     }
01530 }
01531 
01532 /*
01533  * Empty the list of weak objects. Note that we can't call malloc/free
01534  * under the cover of the GC's lock (we might deadlock), so transfer the
01535  * list of free objects to a local list under the cover of the lock, then
01536  * release the lock and free up the memory.
01537  */
01538 static void EmptyWeakFreeList(void) {
01539     if (!WEAK_FREELIST_ISEMPTY()) {
01540     PRCList *qp, freeLinks;
01541 
01542     PR_INIT_CLIST(&freeLinks);
01543 
01544     /*
01545      * Transfer list of free weak links from the global list to a
01546      * local list.
01547      */
01548     LOCK_GC();
01549     qp = _pr_freeWeakLinks.next;
01550     while (qp != &_pr_freeWeakLinks) {
01551         GCWeak *wp = WeakPtr(qp);
01552         qp = qp->next;
01553         PR_REMOVE_LINK(&wp->links);
01554         PR_APPEND_LINK(&wp->links, &freeLinks);
01555     }
01556     UNLOCK_GC();
01557 
01558     /* Free up storage now */
01559     qp = freeLinks.next;
01560     while (qp != &freeLinks) {
01561         GCWeak *wp = WeakPtr(qp);
01562         qp = qp->next;
01563         PR_DELETE(wp);
01564     }
01565     }
01566 }
01567 
01568 /*
01569  * Allocate a new weak node in the weak objects list
01570  */
01571 static GCWeak *AllocWeakNode(void)
01572 {
01573     EmptyWeakFreeList();
01574     return PR_NEWZAP(GCWeak);
01575 }
01576 
01577 static void FreeWeakNode(GCWeak *node)
01578 {
01579     PR_DELETE(node);
01580 }
01581 
01582 /*
01583  * Check the weak links for validity. Note that the list of weak links is
01584  * itself weak (otherwise we would keep the objects with weak links in
01585  * them alive forever). As we scan the list check the weak link object
01586  * itself and if it's not marked then remove it from the weak link list
01587  */
01588 static void CheckWeakLinks(void) {
01589     PRCList *qp;
01590     GCWeak *wp;
01591     PRWord *p, h, tix, **weakPtrAddress;
01592     CollectorType *ct;
01593     PRUint32 offset;
01594 
01595     qp = _pr_weakLinks.next;
01596     while (qp != &_pr_weakLinks) {
01597     wp = WeakPtr(qp);
01598     qp = qp->next;
01599     if ((p = wp->object) != 0) {
01600         h = p[0];        /* Grab header word */
01601         if ((h & MARK_BIT) == 0) {
01602         /*
01603          * The object that has a weak link is no longer being
01604          * referenced; remove it from the chain and let it get
01605          * swept away by the GC. Transfer it to the list of
01606          * free weak links for later freeing.
01607          */
01608         PR_REMOVE_LINK(&wp->links);
01609         PR_APPEND_LINK(&wp->links, &_pr_freeWeakLinks);
01610         collectorCleanupNeeded = 1;
01611         continue;
01612         }
01613         
01614            /* Examine a live object that contains weak links */
01615         tix = GET_TYPEIX(h);
01616         ct = &_pr_collectorTypes[tix];
01617         PR_ASSERT((ct->flags != 0) && (ct->gctype.getWeakLinkOffset != 0));
01618         if (0 == ct->gctype.getWeakLinkOffset) {
01619         /* Heap is probably corrupted */
01620         continue;
01621         }
01622 
01623         /* Get offset into the object of where the weak pointer is */
01624         offset = (*ct->gctype.getWeakLinkOffset)(p + 1);
01625 
01626         /* Check the weak pointer */
01627         weakPtrAddress = (PRWord**)((char*)(p + 1) + offset);
01628         p = *weakPtrAddress;
01629         if (p != 0) {
01630         h = p[-1];    /* Grab header word for pointed to object */
01631         if (h & MARK_BIT) {
01632             /* Object can't be dead */
01633             continue;
01634         }
01635         /* Break weak link to an object that is about to be swept */
01636         *weakPtrAddress = 0;
01637         }
01638     }
01639     }
01640 }
01641 
01642 /************************************************************************/
01643 
01644 /*
01645 ** Perform a complete garbage collection
01646 */
01647 
01648 extern GCLockHook *_pr_GCLockHook;
01649 
01650 static void dogc(void)
01651 {
01652     RootFinder *rf;
01653     GCLockHook* lhook;
01654 
01655     GCScanQ scanQ;
01656     GCSeg *sp, *esp;
01657     PRInt64 start, end, diff;
01658 
01659 #if defined(GCMETER) || defined(GCTIMINGHOOK)
01660     start = PR_Now();
01661 #endif
01662 
01663     /*
01664     ** Stop all of the other threads. This also promises to capture the
01665     ** register state of each and every thread
01666     */
01667 
01668     /* 
01669     ** Get all the locks that will be need during GC after SuspendAll. We 
01670     ** cannot make any locking/library calls after SuspendAll.
01671     */
01672     if (_pr_GCLockHook) {
01673         for (lhook = _pr_GCLockHook->next; lhook != _pr_GCLockHook; 
01674           lhook = lhook->next) {
01675           (*lhook->func)(PR_GCBEGIN, lhook->arg);
01676         }
01677     }
01678 
01679     PR_SuspendAll();
01680 
01681 #ifdef GCMETER
01682     /* Reset meter info */
01683     if (_pr_gcMeter & _GC_METER_STATS) {
01684         fprintf(stderr,
01685                 "[GCSTATS: busy:%ld skipped:%ld, alloced:%ld+wasted:%ld+free:%ld = total:%ld]\n",
01686                 (long) _pr_gcData.busyMemory,
01687                 (long) meter.skippedFreeChunks,
01688                 (long) meter.allocBytes,
01689                 (long) meter.wastedBytes,
01690                 (long) _pr_gcData.freeMemory,
01691                 (long) _pr_gcData.allocMemory);
01692     }        
01693     memset(&meter, 0, sizeof(meter));
01694 #endif
01695 
01696     PR_LOG(_pr_msgc_lm, PR_LOG_ALWAYS, ("begin mark phase; busy=%d free=%d total=%d",
01697                      _pr_gcData.busyMemory, _pr_gcData.freeMemory,
01698                      _pr_gcData.allocMemory));
01699 
01700     if (_pr_beginGCHook) {
01701     (*_pr_beginGCHook)(_pr_beginGCHookArg);
01702     }
01703 
01704     /*
01705     ** Initialize scanQ to all zero's so that root finder doesn't walk
01706     ** over it...
01707     */
01708     memset(&scanQ, 0, sizeof(scanQ));
01709     pScanQ = &scanQ;
01710 
01711     /******************************************/
01712     /* MARK PHASE */
01713 
01714     EmptyFreelists();
01715 
01716     /* Find root's */
01717     PR_LOG(_pr_msgc_lm, PR_LOG_WARNING,
01718            ("begin mark phase; busy=%d free=%d total=%d",
01719         _pr_gcData.busyMemory, _pr_gcData.freeMemory,
01720             _pr_gcData.allocMemory));
01721     METER(_pr_scanDepth = 0);
01722     rf = _pr_rootFinders;
01723     while (rf) {
01724     _GCTRACE(GC_ROOTS, ("finding roots in %s", rf->name));
01725     (*rf->func)(rf->arg);
01726     rf = rf->next;
01727     }
01728     _GCTRACE(GC_ROOTS, ("done finding roots"));
01729 
01730     /* Scan remaining object's that need scanning */
01731     ScanScanQ(&scanQ);
01732     PR_ASSERT(pScanQ == &scanQ);
01733     PR_ASSERT(scanQ.queued == 0);
01734     METER({
01735     if (_pr_scanDepth > _pr_maxScanDepth) {
01736         _pr_maxScanDepth = _pr_scanDepth;
01737     }
01738     });
01739 
01740     /******************************************/
01741     /* FINALIZATION PHASE */
01742 
01743     METER(_pr_scanDepth = 0);
01744     PrepareFinalize();
01745 
01746     /* Scan any resurrected objects found during finalization */
01747     ScanScanQ(&scanQ);
01748     PR_ASSERT(pScanQ == &scanQ);
01749     PR_ASSERT(scanQ.queued == 0);
01750     METER({
01751     if (_pr_scanDepth > _pr_maxScanDepth) {
01752         _pr_maxScanDepth = _pr_scanDepth;
01753     }
01754     });
01755     pScanQ = 0;
01756 
01757     /******************************************/
01758     /* SWEEP PHASE */
01759 
01760     /*
01761     ** Sweep each segment clean. While we are at it, figure out which
01762     ** segment has the most free space and make that the current segment.
01763     */
01764     CheckWeakLinks();
01765     _GCTRACE(GC_SWEEP, ("begin sweep phase"));
01766     _pr_gcData.freeMemory = 0;
01767     _pr_gcData.busyMemory = 0;
01768     sp = segs;
01769     esp = sp + nsegs;
01770     while (sp < esp) {
01771         if (SweepSegment(sp)) {
01772             /*
01773             ** Segment is now free and has been replaced with a different
01774             ** segment object.
01775             */
01776             esp--;
01777             continue;
01778         }
01779         sp++;
01780     }
01781 
01782 #if defined(GCMETER) || defined(GCTIMINGHOOK)
01783     end = PR_Now();
01784 #endif
01785 #ifdef GCMETER
01786     LL_SUB(diff, end, start);
01787     PR_LOG(GC, PR_LOG_ALWAYS,
01788           ("done; busy=%d free=%d chunks=%d total=%d time=%lldms",
01789            _pr_gcData.busyMemory, _pr_gcData.freeMemory,
01790            meter.numFreeChunks, _pr_gcData.allocMemory, diff));
01791     if (_pr_gcMeter & _GC_METER_FREE_LIST) {
01792         PRIntn bin;
01793         fprintf(stderr, "Freelist bins:\n");
01794         for (bin = 0; bin < NUM_BINS; bin++) {
01795             GCFreeChunk *cp = bins[bin];
01796             while (cp != NULL) {
01797                 fprintf(stderr, "%3d: %p %8ld\n",
01798                         bin, cp, (long) cp->chunkSize);
01799                 cp = cp->next;
01800             }
01801         }
01802     }
01803 #endif
01804 
01805     if (_pr_endGCHook) {
01806     (*_pr_endGCHook)(_pr_endGCHookArg);
01807     }
01808 
01809     /* clear the running total of the bytes allocated via BigAlloc() */
01810     bigAllocBytes = 0;
01811 
01812     /* And resume multi-threading */
01813     PR_ResumeAll();
01814 
01815     if (_pr_GCLockHook) {
01816         for (lhook = _pr_GCLockHook->prev; lhook != _pr_GCLockHook; 
01817           lhook = lhook->prev) {
01818           (*lhook->func)(PR_GCEND, lhook->arg);
01819         }
01820     }
01821 
01822     /* Kick finalizer */
01823     NotifyFinalizer();
01824 #ifdef GCTIMINGHOOK
01825     if (_pr_gcData.gcTimingHook) {
01826        PRInt32 time;
01827        LL_SUB(diff, end, start);
01828        LL_L2I(time, diff);
01829        _pr_gcData.gcTimingHook(time);
01830     }
01831 #endif
01832 }
01833 
01834 PR_IMPLEMENT(void) PR_GC(void)
01835 {
01836     LOCK_GC();
01837     dogc();
01838     UNLOCK_GC();
01839 
01840     EmptyWeakFreeList();
01841 }
01842 
01843 /*******************************************************************************
01844  * Heap Walker
01845  ******************************************************************************/
01846 
01847 /*
01848 ** This is yet another disgusting copy of the body of ProcessRootPointer
01849 ** (the other being ProcessRootBlock), but we're not leveraging a single
01850 ** function in their cases in interest of performance (avoiding the function
01851 ** call).
01852 */
01853 static PRInt32 PR_CALLBACK
01854 pr_ConservativeWalkPointer(void* ptr, PRWalkFun walkRootPointer, void* data)
01855 {
01856   PRWord *p0, *p, *segBase;
01857   GCSeg* sp;
01858 
01859   p0 = (PRWord*) ptr;
01860 
01861   /*
01862   ** XXX:  
01863   ** Until Win16 maintains lowSeg and highSeg correctly,
01864   ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
01865   ** Allways scan through the segment list
01866   */
01867 #if !defined(WIN16)
01868   if (p0 < _pr_gcData.lowSeg) return 0;                  /* below gc heap */
01869   if (p0 >= _pr_gcData.highSeg) return 0;                /* above gc heap */
01870 #endif
01871 
01872   /* NOTE: inline expansion of InHeap */
01873   /* Find segment */
01874   sp = lastInHeap;
01875   if (!sp || !IN_SEGMENT(sp,p0)) {
01876     GCSeg *esp;
01877     sp = segs;
01878     esp = segs + nsegs;
01879     for (; sp < esp; sp++) {
01880       if (IN_SEGMENT(sp, p0)) {
01881        lastInHeap = sp;
01882        goto find_object;
01883       }
01884     }
01885     return 0;
01886   }
01887 
01888   find_object:
01889     /* NOTE: Inline expansion of FindObject */
01890     /* Align p to it's proper boundary before we start fiddling with it */
01891     p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
01892     segBase = (PRWord *) sp->base;
01893     do {
01894         if (IS_HBIT(sp, p)) {
01895             goto winner;
01896         }
01897         p--;
01898     } while (p >= segBase);
01899 
01900     /*
01901     ** We have a pointer into the heap, but it has no header
01902     ** bit. This means that somehow the very first object in the heap
01903     ** doesn't have a header. This is impossible so when debugging
01904     ** lets abort.
01905     */
01906 #ifdef DEBUG
01907     PR_Abort();
01908 #endif
01909     return 0;
01910 
01911  winner:
01912     return walkRootPointer(p, data);
01913 }
01914 
01915 static PRInt32 PR_CALLBACK
01916 pr_ConservativeWalkBlock(void **base, PRInt32 count,
01917                       PRWalkFun walkRootPointer, void* data)
01918 {
01919     PRWord *p0;
01920     while (--count >= 0) {
01921        PRInt32 status;
01922         p0 = (PRWord*) *base++;
01923        status = pr_ConservativeWalkPointer(p0, walkRootPointer, data);
01924        if (status) return status;
01925     }
01926     return 0;
01927 }
01928 
01929 /******************************************************************************/
01930 
01931 typedef void (*WalkObject_t)(FILE *out, GCType* tp, PRWord *obj,
01932                           size_t bytes, PRBool detailed);
01933 typedef void (*WalkUnknown_t)(FILE *out, GCType* tp, PRWord tix, PRWord *p,
01934                            size_t bytes, PRBool detailed);
01935 typedef void (*WalkFree_t)(FILE *out, PRWord *p, size_t size, PRBool detailed);
01936 typedef void (*WalkSegment_t)(FILE *out, GCSeg* sp, PRBool detailed);
01937 
01938 static void
01939 pr_WalkSegment(FILE* out, GCSeg* sp, PRBool detailed,
01940            char* enterMsg, char* exitMsg,
01941            WalkObject_t walkObject, WalkUnknown_t walkUnknown, WalkFree_t walkFree)
01942 {
01943     PRWord *p, *limit;
01944 
01945     p = (PRWord *) sp->base;
01946     limit = (PRWord *) sp->limit;
01947     if (enterMsg)
01948     fprintf(out, enterMsg, p);
01949     while (p < limit)
01950     {
01951     if (IS_HBIT(sp, p)) /* Is this an object header? */
01952     {
01953         PRWord h = p[0];
01954         PRWord tix = GET_TYPEIX(h);
01955         size_t bytes = OBJ_BYTES(h);
01956         PRWord* np = (PRWord*) ((char*)p + bytes);
01957 
01958         GCType* tp = &_pr_collectorTypes[tix].gctype;
01959         if ((0 != tp) && walkObject)
01960         walkObject(out, tp, p, bytes, detailed);
01961         else if (walkUnknown)
01962         walkUnknown(out, tp, tix, p, bytes, detailed);
01963         p = np;
01964     }
01965     else
01966     {
01967         /* Must be a freelist item */
01968         size_t size = ((GCFreeChunk*)p)->chunkSize;
01969         if (walkFree)
01970         walkFree(out, p, size, detailed);
01971         p = (PRWord*)((char*)p + size);
01972     }
01973     }
01974     if (p != limit)
01975     fprintf(out, "SEGMENT OVERRUN (end should be at 0x%p)\n", limit);
01976     if (exitMsg)
01977     fprintf(out, exitMsg, p);
01978 }
01979 
01980 static void
01981 pr_WalkSegments(FILE *out, WalkSegment_t walkSegment, PRBool detailed)
01982 {
01983     GCSeg *sp = segs;
01984     GCSeg *esp;
01985 
01986     LOCK_GC();
01987     esp = sp + nsegs;
01988     while (sp < esp)
01989     {
01990     walkSegment(out, sp, detailed);
01991     sp++;
01992     }
01993     fprintf(out, "End of heap\n");
01994     UNLOCK_GC();
01995 }
01996 
01997 /*******************************************************************************
01998  * Heap Dumper
01999  ******************************************************************************/
02000 
02001 PR_IMPLEMENT(void)
02002 PR_DumpIndent(FILE *out, int indent)
02003 {
02004     while (--indent >= 0)
02005     fprintf(out, " ");
02006 }
02007 
02008 static void
02009 PR_DumpHexWords(FILE *out, PRWord *p, int nWords,
02010         int indent, int nWordsPerLine)
02011 {
02012     while (nWords > 0)
02013     {
02014     int i;
02015 
02016     PR_DumpIndent(out, indent);
02017     i = nWordsPerLine;
02018     if (i > nWords)
02019         i = nWords;
02020     nWords -= i;
02021     while (i--)
02022     {
02023         fprintf(out, "0x%.8lX", (long) *p++);
02024         if (i)
02025         fputc(' ', out);
02026     }
02027     fputc('\n', out);
02028     }
02029 }
02030 
02031 static void PR_CALLBACK
02032 pr_DumpObject(FILE *out, GCType* tp, PRWord *p, 
02033           size_t bytes, PRBool detailed)
02034 {
02035     char kindChar = tp->kindChar;
02036     fprintf(out, "0x%p: 0x%.6lX %c  ",
02037             p, (long) bytes, kindChar ? kindChar : '?');
02038     if (tp->dump)
02039     (*tp->dump)(out, (void*) (p + 1), detailed, 0);
02040     if (detailed)
02041     PR_DumpHexWords(out, p, bytes>>2, 22, 4);
02042 }
02043     
02044 static void PR_CALLBACK
02045 pr_DumpUnknown(FILE *out, GCType* tp, PRWord tix, PRWord *p, 
02046            size_t bytes, PRBool detailed)
02047 {
02048     char kindChar = tp->kindChar;
02049     fprintf(out, "0x%p: 0x%.6lX %c  ",
02050             p, (long) bytes, kindChar ? kindChar : '?');
02051     fprintf(out, "UNKNOWN KIND %ld\n", (long) tix);
02052     if (detailed)
02053     PR_DumpHexWords(out, p, bytes>>2, 22, 4);
02054 }
02055 
02056 static void PR_CALLBACK
02057 pr_DumpFree(FILE *out, PRWord *p, size_t size, PRBool detailed)
02058 {
02059 #if defined(XP_MAC) && XP_MAC
02060 # pragma unused( detailed )
02061 #endif
02062 
02063     fprintf(out, "0x%p: 0x%.6lX -  FREE\n", p, (long) size);
02064 }
02065 
02066 static void PR_CALLBACK
02067 pr_DumpSegment(FILE* out, GCSeg* sp, PRBool detailed)
02068 {
02069     pr_WalkSegment(out, sp, detailed,
02070            "\n   Address: Length\n0x%p: Beginning of segment\n",
02071            "0x%p: End of segment\n\n",
02072            pr_DumpObject, pr_DumpUnknown, pr_DumpFree);
02073 }
02074 
02075 static void pr_DumpRoots(FILE *out);
02076 
02077 /*
02078 ** Dump out the GC heap.
02079 */
02080 PR_IMPLEMENT(void)
02081 PR_DumpGCHeap(FILE *out, PRBool detailed)
02082 {
02083     fprintf(out, "\n"
02084         "The kinds are:\n"
02085         " U unscanned block\n"
02086         " W weak link block\n"
02087         " S scanned block\n"
02088         " F scanned and final block\n"
02089         " C class record\n"
02090         " X context record\n"
02091         " - free list item\n"
02092         " ? other\n");
02093     LOCK_GC();
02094     pr_WalkSegments(out, pr_DumpSegment, detailed);
02095     if (detailed)
02096     pr_DumpRoots(out);
02097     UNLOCK_GC();
02098 }
02099 
02100 PR_IMPLEMENT(void)
02101 PR_DumpMemory(PRBool detailed)
02102 {
02103     PR_DumpToFile("memory.out", "Dumping memory", PR_DumpGCHeap, detailed);
02104 }
02105 
02106 /******************************************************************************/
02107 
02108 static PRInt32 PR_CALLBACK
02109 pr_DumpRootPointer(PRWord* p, void* data)
02110 {
02111 #ifdef XP_MAC
02112 #pragma unused(data)
02113 #endif
02114     PRWord h = p[0];
02115     PRWord tix = GET_TYPEIX(h);
02116       size_t bytes = OBJ_BYTES(h);
02117       
02118       GCType* tp = &_pr_collectorTypes[tix].gctype;
02119       if (0 != tp)
02120       pr_DumpObject(_pr_gcData.dumpOutput, tp, p, bytes, PR_FALSE);
02121       else
02122       pr_DumpUnknown(_pr_gcData.dumpOutput, tp, tix, p, bytes, PR_FALSE);
02123     return 0;
02124 }
02125 
02126 static void PR_CALLBACK
02127 pr_ConservativeDumpRootPointer(void* ptr)
02128 {
02129     (void)pr_ConservativeWalkPointer(ptr, (PRWalkFun) pr_DumpRootPointer, NULL);
02130 }
02131 
02132 static void PR_CALLBACK
02133 pr_ConservativeDumpRootBlock(void **base, PRInt32 count)
02134 {
02135     (void)pr_ConservativeWalkBlock(base, count, (PRWalkFun) pr_DumpRootPointer, NULL);
02136 }
02137 
02138 extern int
02139 DumpThreadRoots(PRThread *t, int i, void *notused);
02140 
02141 static void
02142 pr_DumpRoots(FILE *out)
02143 {
02144     RootFinder *rf;
02145     void (*liveBlock)(void **base, PRInt32 count);
02146     void (*livePointer)(void *ptr);
02147     void (*processRootBlock)(void **base, PRInt32 count);
02148     void (*processRootPointer)(void *ptr);
02149 
02150     LOCK_GC();
02151 
02152     liveBlock = _pr_gcData.liveBlock;
02153     livePointer = _pr_gcData.livePointer;
02154     processRootBlock = _pr_gcData.processRootBlock;
02155     processRootPointer = _pr_gcData.processRootPointer;
02156     
02157     _pr_gcData.liveBlock = pr_ConservativeDumpRootBlock;
02158     _pr_gcData.livePointer = pr_ConservativeDumpRootPointer;
02159     _pr_gcData.processRootBlock = pr_ConservativeDumpRootBlock;
02160     _pr_gcData.processRootPointer = pr_ConservativeDumpRootPointer;
02161     _pr_gcData.dumpOutput = out;
02162 
02163     rf = _pr_rootFinders;
02164     while (rf) {
02165     fprintf(out, "\n===== Roots for %s\n", rf->name);
02166     (*rf->func)(rf->arg);
02167     rf = rf->next;
02168     }
02169 
02170     _pr_gcData.liveBlock = liveBlock;
02171     _pr_gcData.livePointer = livePointer;
02172     _pr_gcData.processRootBlock = processRootBlock;
02173     _pr_gcData.processRootPointer = processRootPointer;
02174     _pr_gcData.dumpOutput = NULL;
02175 
02176     UNLOCK_GC();
02177 }
02178 
02179 /*******************************************************************************
02180  * Heap Summary Dumper
02181  ******************************************************************************/
02182 
02183 PRSummaryPrinter summaryPrinter = NULL;
02184 void* summaryPrinterClosure = NULL;
02185 
02186 PR_IMPLEMENT(void) 
02187 PR_RegisterSummaryPrinter(PRSummaryPrinter fun, void* closure)
02188 {
02189     summaryPrinter = fun;
02190     summaryPrinterClosure = closure;
02191 }
02192 
02193 static void PR_CALLBACK
02194 pr_SummarizeObject(FILE *out, GCType* tp, PRWord *p,
02195            size_t bytes, PRBool detailed)
02196 {
02197 #if defined(XP_MAC) && XP_MAC
02198 # pragma unused( out, detailed )
02199 #endif
02200 
02201     if (tp->summarize)
02202     (*tp->summarize)((void GCPTR*)(p + 1), bytes);
02203 }
02204 
02205 static void PR_CALLBACK
02206 pr_DumpSummary(FILE* out, GCSeg* sp, PRBool detailed)
02207 {
02208     pr_WalkSegment(out, sp, detailed, NULL, NULL,
02209            pr_SummarizeObject, NULL, NULL);
02210 }
02211 
02212 PR_IMPLEMENT(void)
02213 PR_DumpGCSummary(FILE *out, PRBool detailed)
02214 {
02215     if (summaryPrinter) {
02216     pr_WalkSegments(out, pr_DumpSummary, detailed);
02217     summaryPrinter(out, summaryPrinterClosure);
02218     }
02219 #if 0
02220     fprintf(out, "\nFinalizable objects:\n");
02221     {
02222     PRCList *qp;
02223     qp = _pr_pendingFinalQueue.next;
02224     while (qp != &_pr_pendingFinalQueue) {
02225         GCFinal* fp = FinalPtr(qp);
02226         PRWord h = fp->object[0];        /* Grab header word */
02227         PRWord tix = GET_TYPEIX(h);
02228         GCType* tp = _pr_gcTypes[tix];
02229         size_t bytes = OBJ_BYTES(h);
02230         pr_DumpObject(out, tp, fp->object, bytes, PR_FALSE);
02231         qp = qp->next;
02232     }
02233     }
02234 #endif
02235 }
02236 
02237 PR_IMPLEMENT(void)
02238 PR_DumpMemorySummary(void)
02239 {
02240     PR_DumpToFile("memory.out", "Memory Summary", PR_DumpGCSummary, PR_FALSE);
02241 }
02242 
02243 /*******************************************************************************
02244  * End Of Heap Walker 
02245  ******************************************************************************/
02246 
02247 #ifdef GC_TRACEROOTS
02248 
02249 PRInt32 pr_traceGen = 0;
02250 
02251 static PRBool
02252 pr_IsMarked(PRWord* p)
02253 {
02254     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
02255     PR_ASSERT(end->check == PR_BLOCK_END);
02256     return end->traceGeneration == pr_traceGen;
02257 }
02258 
02259 static void
02260 pr_Mark(PRWord* p)
02261 {
02262     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
02263     PR_ASSERT(end->check == PR_BLOCK_END);
02264     end->traceGeneration = pr_traceGen;
02265 }
02266 
02267 PRWord* pr_traceObj; /* set this in the debugger, then execute PR_TraceRoot() */
02268 
02269 static PRInt32 PR_CALLBACK
02270 pr_TraceRootObject(void* obj, void* data);
02271 
02272 static PRInt32 PR_CALLBACK
02273 pr_TraceRootPointer(PRWord *p, void* data)
02274 {
02275     PRInt32 printTrace = 0;
02276     PRWord h = p[0];
02277     PRWord tix = GET_TYPEIX(h);
02278     GCType* tp = &_pr_collectorTypes[tix].gctype;
02279     FILE* out = _pr_gcData.dumpOutput;
02280 
02281     PR_ASSERT(tp);
02282     if (pr_IsMarked(p))
02283        return printTrace;
02284 
02285     pr_Mark(p);
02286     if (p == pr_traceObj) {
02287        fprintf(out, "\n### Found path to:\n");
02288        printTrace = 1;
02289     }
02290     else {
02291        if (PR_StackSpaceLeft(PR_CurrentThread()) < 512) {
02292            fprintf(out, "\n### Path too deep (giving up):\n");
02293            printTrace = 1;
02294        }
02295        else if (tp->walk) {
02296            printTrace = tp->walk((void*)(p + 1), pr_TraceRootObject, data);
02297        }
02298        /* else there's no way to walk this object, so we
02299           haven't found what we're looking for */
02300     }
02301 
02302     if (printTrace == 1) {
02303        PR_ASSERT(tp->dump);
02304        fprintf(out, "0x%p: ", p);
02305        tp->dump(out, (void*)(p + 1), PR_FALSE, 1);
02306     }
02307     return printTrace;
02308 }
02309 
02310 static PRInt32 PR_CALLBACK
02311 pr_TraceRootObject(void* obj, void* data)
02312 {
02313     /* This version of pr_TraceRootPointer takes object
02314        pointers, instead of gc header pointers. */
02315     return pr_TraceRootPointer((PRWord*)obj - 1, data);
02316 }
02317 
02318 static void PR_CALLBACK
02319 pr_ConservativeTraceRootPointer(PRWord *p)
02320 {
02321     PRInt32 status;
02322     ++pr_traceGen;
02323     status = pr_ConservativeWalkPointer(p, pr_TraceRootPointer, NULL);
02324     if (status) {
02325        FILE* out = _pr_gcData.dumpOutput;
02326        fprintf(out, "### from root at 0x%p\n\n", p);
02327     }
02328 }
02329 
02330 static void PR_CALLBACK
02331 pr_ConservativeTraceRootBlock(void **base, PRInt32 count)
02332 {
02333     PRInt32 status;
02334     ++pr_traceGen;
02335     status = pr_ConservativeWalkBlock(base, count, pr_TraceRootPointer, NULL);
02336     if (status) {
02337        FILE* out = _pr_gcData.dumpOutput;
02338        fprintf(out, "### from root in range 0x%p + 0x%lx\n\n",
02339                 base, (long) count);
02340     }
02341 }
02342 
02343 static void
02344 PR_TraceRoot1(FILE* out, PRBool detailed)
02345 {
02346     RootFinder *rf;
02347     void (*liveBlock)(void **base, PRInt32 count);
02348     void (*livePointer)(void *ptr);
02349     void (*processRootBlock)(void **base, PRInt32 count);
02350     void (*processRootPointer)(void *ptr);
02351 
02352     LOCK_GC();
02353 
02354     liveBlock = _pr_gcData.liveBlock;
02355     livePointer = _pr_gcData.livePointer;
02356     processRootBlock = _pr_gcData.processRootBlock;
02357     processRootPointer = _pr_gcData.processRootPointer;
02358     
02359     _pr_gcData.liveBlock = pr_ConservativeTraceRootBlock;
02360     _pr_gcData.livePointer = pr_ConservativeTraceRootPointer;
02361     _pr_gcData.processRootBlock = pr_ConservativeTraceRootBlock;
02362     _pr_gcData.processRootPointer = pr_ConservativeTraceRootPointer;
02363     _pr_gcData.dumpOutput = out;
02364 
02365     fprintf(out, "### Looking for paths to 0x%p\n\n", pr_traceObj);
02366 
02367     rf = _pr_rootFinders;
02368     while (rf) {
02369        fprintf(out, "\n===== Roots for %s\n", rf->name);
02370        (*rf->func)(rf->arg);
02371        rf = rf->next;
02372     }
02373 
02374     _pr_gcData.liveBlock = liveBlock;
02375     _pr_gcData.livePointer = livePointer;
02376     _pr_gcData.processRootBlock = processRootBlock;
02377     _pr_gcData.processRootPointer = processRootPointer;
02378     _pr_gcData.dumpOutput = NULL;
02379 
02380     UNLOCK_GC();
02381 }
02382 
02383 PR_PUBLIC_API(void)
02384 PR_TraceRoot()
02385 {
02386     /*
02387     ** How this works: 
02388     ** Once you find the object you want to trace the roots of, set the
02389     ** global variable pr_traceObj to point to it (the header, not the
02390     ** java handle), and then call this routine (on Windows, you can set
02391     ** a breakpoint at the end of a function that returns void (e.g. dogc)
02392     ** and then do a "set next statement" to point to this routine and go.
02393     ** This will dump a list of the paths from the roots to the object in
02394     ** question to your memory.out file.
02395     */
02396     PR_DumpToFile("memory.out", "Tracing Roots", PR_TraceRoot1, PR_FALSE);
02397 }
02398 
02399 #endif /* GC_TRACEROOTS */
02400 
02401 /******************************************************************************/
02402 
02403 #if defined(DEBUG) && defined(WIN32)
02404 static void DumpApplicationHeap(FILE *out, HANDLE heap)
02405 {
02406     PROCESS_HEAP_ENTRY entry;
02407     DWORD err;
02408 
02409     if (!HeapLock(heap))
02410     OutputDebugString("Can't lock the heap.\n");
02411     entry.lpData = 0;
02412     fprintf(out, "   address:       size ovhd region\n");
02413     while (HeapWalk(heap, &entry))
02414     {
02415     WORD flags = entry.wFlags;
02416 
02417     fprintf(out, "0x%.8X: 0x%.8X 0x%.2X 0x%.2X  ", entry.lpData, entry.cbData,
02418         entry.cbOverhead, entry.iRegionIndex);
02419     if (flags & PROCESS_HEAP_REGION)
02420         fprintf(out, "REGION  committedSize=0x%.8X uncommittedSize=0x%.8X firstBlock=0x%.8X lastBlock=0x%.8X",
02421             entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
02422             entry.Region.lpFirstBlock, entry.Region.lpLastBlock);
02423     else if (flags & PROCESS_HEAP_UNCOMMITTED_RANGE)
02424         fprintf(out, "UNCOMMITTED");
02425     else if (flags & PROCESS_HEAP_ENTRY_BUSY)
02426     {
02427         if (flags & PROCESS_HEAP_ENTRY_DDESHARE)
02428         fprintf(out, "DDEShare ");
02429         if (flags & PROCESS_HEAP_ENTRY_MOVEABLE)
02430         fprintf(out, "Moveable Block  handle=0x%.8X", entry.Block.hMem);
02431         else
02432         fprintf(out, "Block");
02433     }
02434     fprintf(out, "\n");
02435     }
02436     if ((err = GetLastError()) != ERROR_NO_MORE_ITEMS)
02437     fprintf(out, "ERROR %d iterating through the heap\n", err);
02438     if (!HeapUnlock(heap))
02439     OutputDebugString("Can't unlock the heap.\n");
02440 }
02441 #endif
02442 
02443 #if defined(DEBUG) && defined(WIN32)
02444 static void DumpApplicationHeaps(FILE *out)
02445 {
02446     HANDLE mainHeap;
02447     HANDLE heaps[100];
02448     DWORD nHeaps;
02449     PRInt32 i;
02450 
02451     mainHeap = GetProcessHeap();
02452     nHeaps = GetProcessHeaps(100, heaps);
02453     if (nHeaps > 100)
02454     nHeaps = 0;
02455     fprintf(out, "%ld heaps:\n", (long) nHeaps);
02456     for (i = 0; i<nHeaps; i++)
02457     {
02458     HANDLE heap = heaps[i];
02459 
02460     fprintf(out, "Heap at 0x%.8lX", (long) heap);
02461     if (heap == mainHeap)
02462         fprintf(out, " (main)");
02463     fprintf(out, ":\n");
02464     DumpApplicationHeap(out, heap);
02465     fprintf(out, "\n");
02466     }
02467     fprintf(out, "End of heap dump\n\n");
02468 }
02469 #endif
02470 
02471 #if defined(DEBUG) && defined(WIN32)
02472 PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
02473 {
02474     FILE *out;
02475 
02476     OutputDebugString("Dumping heaps...");
02477     out = fopen("heaps.out", "a");
02478     if (!out)
02479     OutputDebugString("Can't open \"heaps.out\"\n");
02480     else
02481     {
02482     struct tm *newtime;
02483     time_t aclock;
02484 
02485     time(&aclock);
02486     newtime = localtime(&aclock);
02487     fprintf(out, "Heap dump on %s\n", asctime(newtime));    /* Print current time */
02488     DumpApplicationHeaps(out);
02489     fprintf(out, "\n\n");
02490     fclose(out);
02491     }
02492     OutputDebugString(" done\n");
02493 }
02494 #else
02495 
02496 PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
02497 {
02498     fprintf(stderr, "Native heap dumping is currently implemented only for Windows32.\n");
02499 }
02500 #endif
02501 
02502 /************************************************************************/
02503 
02504 /*
02505 ** Scan the freelist bins looking for a big enough chunk of memory to
02506 ** hold "bytes" worth of allocation. "bytes" already has the
02507 ** per-allocation header added to it. Return a pointer to the object with
02508 ** its per-allocation header already prepared.
02509 */
02510 static PRWord *BinAlloc(int cbix, PRInt32 bytes, int dub)
02511 {
02512     GCFreeChunk **cpp, *cp, *cpNext;
02513     GCSeg *sp;
02514     PRInt32 chunkSize, remainder;
02515     PRWord *p, *np;
02516     PRInt32 bin, newbin;
02517 
02518     /* Compute bin that allocation belongs in */
02519     InlineBinNumber(bin,bytes)
02520     if (bin < minBin) {
02521     bin = minBin;    /* Start at first filled bin */
02522     }
02523 
02524     /* Search in the bin, and larger bins, for a big enough piece */
02525     for (; bin <= NUM_BINS-1; bin++) {
02526         cpp = &bins[bin];
02527     while ((cp = *cpp) != 0) {
02528         chunkSize = cp->chunkSize;
02529         if (chunkSize < bytes) {
02530         /* Too small; skip it */
02531             METER(meter.skippedFreeChunks++);
02532         cpp = &cp->next;
02533         continue;
02534         }
02535 
02536         /* We have found a hunk of memory large enough to use */
02537         p = (PRWord*) cp;
02538         sp = cp->segment;
02539         cpNext = cp->next;
02540 #ifndef IS_64
02541         if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
02542         /*
02543          * We are double aligning the memory and the current free
02544          * chunk is aligned on an even boundary. Because header
02545          * words are one word long we need to discard the first
02546          * word of memory.
02547          */
02548         p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
02549         SET_HBIT(sp, p);
02550         p++;
02551         chunkSize -= PR_BYTES_PER_WORD;
02552         bytes -= PR_BYTES_PER_WORD;
02553         PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
02554         _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
02555         _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
02556         }
02557 #endif
02558         np = (PRWord*) ((char*) p + bytes);
02559         remainder = chunkSize - bytes;
02560         if (remainder >= MIN_FREE_CHUNK_BYTES) {
02561         /* The left over memory is large enough to be freed. */
02562         cp = (GCFreeChunk*) np;
02563         cp->segment = sp;
02564         cp->chunkSize = remainder;
02565         InlineBinNumber(newbin, remainder)
02566         if (newbin != bin) {
02567             *cpp = (GCFreeChunk*) cpNext; /* remove */
02568             cp->next = bins[newbin];      /* insert */
02569             bins[newbin] = cp;
02570             if (newbin < minBin) minBin = newbin;
02571             if (newbin > maxBin) maxBin = newbin;
02572         } else {
02573             /* Leave it on the same list */
02574             cp->next = cpNext;
02575             *cpp = (GCFreeChunk*) np;
02576         }
02577         } else {
02578         /*
02579          * The left over memory is too small to be released. Just
02580          * leave it attached to the chunk of memory being
02581          * returned.
02582          */
02583         *cpp = cpNext;
02584         bytes = chunkSize;
02585         }
02586         p[0] = MAKE_HEADER(cbix, (bytes >> PR_BYTES_PER_WORD_LOG2));
02587         SET_HBIT(sp, p);
02588         _pr_gcData.freeMemory -= bytes;
02589         _pr_gcData.busyMemory += bytes;
02590         return p;
02591     }
02592     }
02593     return 0;
02594 }
02595 
02596 /*
02597 ** Allocate a piece of memory that is "big" in it's own segment.  Make
02598 ** the object consume the entire segment to avoid fragmentation.  When
02599 ** the object is no longer referenced, the segment is freed.
02600 */
02601 static PRWord *BigAlloc(int cbix, PRInt32 bytes, int dub)
02602 {
02603     GCSeg *sp;
02604     PRWord *p, h;
02605     PRInt32 chunkSize;
02606 
02607     /*
02608     ** If the number of bytes allocated via BigAlloc() since the last GC
02609     ** exceeds BIG_ALLOC_GC_SIZE then do a GC Now...
02610     */
02611     if (bigAllocBytes >= BIG_ALLOC_GC_SIZE) {
02612         dogc();
02613     }
02614     bigAllocBytes += bytes;
02615 
02616     /* Get a segment to hold this allocation */
02617     sp = GrowHeapExactly(bytes);
02618 
02619     if (sp) {
02620         p = (PRWord*) sp->base;
02621         chunkSize = sp->limit - sp->base;
02622 
02623         /* All memory is double aligned on 64 bit machines... */
02624 #ifndef IS_64
02625         if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
02626             /*
02627             ** Consume the first word of the chunk with a dummy
02628             ** unreferenced object.
02629             */
02630             p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
02631             SET_HBIT(sp, p);
02632             p++;
02633             chunkSize -= PR_BYTES_PER_WORD;
02634             _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
02635             _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
02636             PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
02637         }
02638 #endif
02639 
02640 #if defined(WIN16)
02641             /* All memory MUST be aligned on 32bit boundaries */
02642             PR_ASSERT( (((PRWord)p) & (PR_BYTES_PER_WORD-1)) == 0 );
02643 #endif
02644 
02645         /* Consume the *entire* segment with a single allocation */
02646         h = MAKE_HEADER(cbix, (chunkSize >> PR_BYTES_PER_WORD_LOG2));
02647         p[0] = h;
02648         SET_HBIT(sp, p);
02649         _pr_gcData.freeMemory -= chunkSize;
02650         _pr_gcData.busyMemory += chunkSize;
02651     return p;
02652     }
02653     return 0;
02654 }
02655 
02656 /* we disable gc allocation during low memory conditions */
02657 static PRBool allocationEnabled = PR_TRUE;
02658 
02659 PR_IMPLEMENT(void) PR_EnableAllocation(PRBool yesOrNo)
02660 {
02661     allocationEnabled = yesOrNo;
02662 }
02663 
02664 static void CollectorCleanup(void) {
02665     while (collectorCleanupNeeded) {
02666     LOCK_GC();
02667     collectorCleanupNeeded = 0;
02668     UNLOCK_GC();
02669     if (freeSegs) {
02670         FreeSegments();
02671     }
02672     if (!WEAK_FREELIST_ISEMPTY()) {
02673         EmptyWeakFreeList();
02674     }
02675     }
02676 }
02677 
02678 /******************************************************************************/
02679 
02680 #ifdef GC_CHECK
02681 static PRInt32 allocationCount;
02682 
02683 static void EarthShatteringKaBoom(PRInt32 whichOne) {
02684     long* p = 0;
02685     *p = 0;
02686 }
02687 
02688 /* Check a segment of heap memory. Verify that the object memory
02689    hasn't been overwritten (past the end at least) */
02690 static void CheckSegment(GCSeg* sp) {
02691     PRWord h, tix;
02692     PRWord *p, *lastp, *np, *limit;
02693 
02694     lastp = p = (PRWord *) sp->base;
02695     limit = (PRWord *) sp->limit;
02696     while (p < limit) {
02697     if (IS_HBIT(sp, p)) {
02698            char *cp, i;
02699            GCBlockEnd* end;
02700            PRWord bytes, requestedBytes;
02701 
02702            h = p[0];
02703            tix = GET_TYPEIX(h);
02704            bytes = OBJ_BYTES(h);
02705            np = (PRWord *) ((char *)p + bytes);
02706            if (tix != FREE_MEMORY_TYPEIX) {
02707                 PRInt32 test;      /* msdev get's fooled without this local */
02708               /* A live object is here. The last word in the object will
02709                  contain the objects requestedSize */
02710               end = (GCBlockEnd*)((char*)(p) + bytes - sizeof(GCBlockEnd));
02711               test = end->check;
02712               if (test != PR_BLOCK_END) {
02713                   PR_ASSERT(test == PR_BLOCK_END);
02714               }
02715               requestedBytes = end->requestedBytes;
02716               if (requestedBytes >= bytes) EarthShatteringKaBoom(0);
02717               cp = (char*)(p + 1) + requestedBytes;
02718               i = (char) 0xff;
02719               while (cp < (char*)end) {
02720             if (*cp != i) EarthShatteringKaBoom(1);
02721             cp++;
02722             i--;
02723         }
02724         }
02725         lastp = p;
02726         p = np;
02727     } else {
02728         /* Must be a freelist item */
02729         GCFreeChunk *cp = (GCFreeChunk*) p;
02730         if ((PRInt32)cp->chunkSize < (PRInt32)sizeof(GCFreeChunk)) {
02731             EarthShatteringKaBoom(3);
02732         }
02733         lastp = p;
02734         p = (PRWord*) ((char*)p + cp->chunkSize);
02735     }
02736     }
02737 }
02738 
02739 static void CheckHeap(void) {
02740     GCSeg *sp = segs;
02741     GCSeg *esp = sp + nsegs;
02742     while (sp < esp) {
02743     CheckSegment(sp);
02744     sp++;
02745     }
02746 }
02747 
02748 #endif /* GC_CHECK */
02749 
02750 /******************************************************************************/
02751 
02752 #ifdef DEBUG
02753 long gc_thrash = -1L;
02754 #endif
02755 
02756 /*
02757 ** Allocate memory from the GC Heap. Performs garbage collections if
02758 ** memory gets tight and grows the heap as needed. May return NULL if
02759 ** memory cannot be found.
02760 */
02761 PR_IMPLEMENT(PRWord GCPTR *)PR_AllocMemory(
02762     PRWord requestedBytes, PRInt32 tix, PRWord flags)
02763 {
02764     PRWord *p;
02765     CollectorType *ct;
02766     PRInt32 bytes;
02767     GCFinal *final = 0;
02768     GCWeak *weak = 0;
02769     int dub = flags & PR_ALLOC_DOUBLE;
02770     PRInt32 objBytes;
02771 #ifdef GC_STATS
02772     PRInt64 allocTime, ldelta;
02773 #endif
02774 
02775     if (!allocationEnabled) return NULL;
02776 
02777     PR_ASSERT(requestedBytes >= 0);
02778     PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
02779 
02780 #ifdef DEBUG
02781     if (_pr_do_a_dump) {
02782     /*
02783     ** Collect, pause for a second (lets finalizer run), and then GC
02784     ** again.
02785     */
02786     PR_GC();
02787     PR_Sleep(PR_MicrosecondsToInterval(1000000L));
02788     PR_GC();
02789     PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
02790     _pr_do_a_dump = 0;
02791     }
02792 #endif
02793 
02794 #ifdef GC_STATS
02795     allocTime = PR_Now();
02796 #endif
02797     bytes = (PRInt32) requestedBytes;
02798 
02799     /*
02800     ** Align bytes to a multiple of a PRWord, then add in enough space
02801     ** to hold the header word.
02802     **
02803     ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
02804     */
02805 #if !defined(WIN16) 
02806     /* Check for possible overflow of bytes before performing add */
02807     if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
02808     bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
02809     bytes <<= PR_BYTES_PER_WORD_LOG2;
02810     /* Check for possible overflow of bytes before performing add */
02811     if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
02812     bytes += sizeof(PRWord);
02813 #else 
02814     /* 
02815     ** For WIN16 the shifts have been broken out into separate statements
02816     ** to prevent the compiler from crashing...
02817     */
02818     {
02819         PRWord shiftVal;
02820 
02821         /* Check for possible overflow of bytes before performing add */
02822         if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
02823         bytes += PR_BYTES_PER_WORD - 1L;
02824         shiftVal = PR_BYTES_PER_WORD_LOG2;
02825         bytes >>= shiftVal;
02826         bytes <<= shiftVal;
02827         /* Check for possible overflow of bytes before performing add */
02828         if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
02829         bytes += sizeof(PRWord);
02830     }
02831 #endif
02832     /*
02833      * Add in an extra word of memory for double-aligned memory. Some
02834      * percentage of the time this will waste a word of memory (too
02835      * bad). Howver, it makes the allocation logic much simpler and
02836      * faster.
02837      */
02838 #ifndef IS_64
02839     if (dub) {
02840         /* Check for possible overflow of bytes before performing add */
02841         if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
02842         bytes += PR_BYTES_PER_WORD;
02843     }
02844 #endif
02845 
02846 #ifdef GC_CHECK
02847     if (_pr_gcData.flags & GC_CHECK) {
02848         /* Bloat the allocation a bit so that we can lay down
02849            a check pattern that we will validate */
02850         /* Check for possible overflow of bytes before performing add */
02851         if ((MAX_INT - PR_BYTES_PER_WORD * 3) < bytes ) return NULL;
02852         bytes += PR_BYTES_PER_WORD * 3;
02853     }
02854 #endif
02855 
02856 #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
02857     if ((MAX_INT - sizeof(GCBlockEnd)) < bytes ) return NULL;
02858     bytes += sizeof(GCBlockEnd);
02859 #endif
02860 
02861     PR_ASSERT( bytes < MAX_ALLOC_SIZE );
02862     /*
02863     ** Java can ask for objects bigger than MAX_ALLOC_SIZE,
02864     ** but it won't get them.
02865     */
02866     if (bytes >= MAX_ALLOC_SIZE) return NULL;
02867 
02868 #ifdef DEBUG
02869     if (gc_thrash == -1L ? (gc_thrash = (long)PR_GetEnv("GC_THRASH")):gc_thrash) PR_GC();
02870 #endif
02871 
02872     ct = &_pr_collectorTypes[tix];
02873     if (ct->flags & (_GC_TYPE_FINAL|_GC_TYPE_WEAK)) {
02874     if (0 != ct->gctype.finalize) {
02875         /*
02876         ** Allocate a GCFinal struct for this object in advance. Don't put
02877         ** it on the pending list until we have allocated the object
02878         */
02879         final = AllocFinalNode();
02880         if (!final) {
02881         /* XXX THIS IS NOT ACCEPTABLE*/
02882               PR_ASSERT(0);
02883         return 0;
02884         }
02885     }
02886     if (0 != ct->gctype.getWeakLinkOffset) {
02887         /*
02888         ** Allocate a GCWeak struct for this object in advance. Don't put
02889         ** it on the weak links list until we have allocated the object
02890         */
02891         weak = AllocWeakNode();
02892         if (!weak) {
02893         /* XXX THIS IS NOT ACCEPTABLE*/
02894         if (0 != final) {
02895             FreeFinalNode(final);
02896         }
02897               PR_ASSERT(0);
02898         return 0;
02899         }
02900     }
02901     }
02902 
02903     LOCK_GC();
02904 #ifdef GC_CHECK
02905     if (_pr_gcData.flags & GC_CHECK) CheckHeap();
02906     allocationCount++;
02907 #endif
02908 
02909     /* Check for overflow of maximum size we can handle */
02910     if (bytes > MAX_ALLOC) goto lost;
02911 
02912     /* Try default allocation */
02913     p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
02914         BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
02915     if (0 == p) {
02916 #ifdef GC_STATS
02917         LL_SUB(ldelta, PR_Now(), allocTime);
02918 #endif
02919         /* Collect some memory */
02920         _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
02921         dogc();
02922         PR_ASSERT( GC_IS_LOCKED() );
02923 
02924         /* After a collection we check and see if we should grow the
02925         ** heap. We grow the heap when the amount of memory free is less
02926         ** than a certain percentage of the heap size. We don't check to
02927         ** see if the grow succeeded because our fallback strategy in
02928         ** either case is to try one more time to allocate. */
02929         if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory)
02930         && ((_pr_gcData.freeMemory <
02931             ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))
02932         || (_pr_gcData.freeMemory < bytes))) {
02933             GrowHeap(PR_MAX(bytes, segmentSize));
02934         }
02935 #ifdef GC_STATS
02936         LL_ADD(allocTime, PR_Now(), ldelta);
02937 #endif
02938 
02939         /* Try again */
02940         p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
02941             BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
02942         if (0 == p) {
02943             /* Well that lost big time. Memory must be pretty well fragmented */
02944             if (!GrowHeap(PR_MAX(bytes, segmentSize))) goto lost;
02945             p = BinAlloc(tix, bytes, dub);
02946             if (0 == p) goto lost;
02947         }
02948     }
02949 
02950     /* Zero out the portion of the object memory that was used by
02951        the GCFreeChunk structure (skip the first word because it
02952        was already overwritten by the gc header word) */
02953     objBytes = OBJ_BYTES(p[0]);
02954     if (objBytes > sizeof(PRWord)) p[1] = 0;
02955     if (objBytes > sizeof(PRWord)*2) p[2] = 0;
02956 
02957     if (final) {
02958        _GCTRACE(GC_ALLOC, ("alloc 0x%x (%d) final=0x%x",
02959                 p, bytes, final));
02960     final->object = p;
02961     PR_APPEND_LINK(&final->links, &_pr_finalizeableObjects);
02962     } else {
02963        _GCTRACE(GC_ALLOC, ("alloc 0x%x (%d)", p, bytes));
02964     }
02965     if (weak) {
02966     weak->object = p;
02967     PR_APPEND_LINK(&weak->links, &_pr_weakLinks);
02968     }
02969     METER(meter.allocBytes += bytes);
02970     METER(meter.wastedBytes += (bytes - requestedBytes));
02971     UNLOCK_GC();
02972 
02973     if (collectorCleanupNeeded) {
02974        CollectorCleanup();
02975     }
02976 
02977 #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
02978     {
02979        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
02980        end->check = PR_BLOCK_END;
02981     }
02982 #endif
02983 #ifdef GC_STATS
02984     {
02985        PRInt64 now = PR_Now();
02986        double delta;
02987        PRInt32 bin;
02988        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
02989 
02990        end->allocTime = allocTime;
02991        LL_SUB(ldelta, now, allocTime);
02992        LL_L2D(delta, ldelta);
02993        InlineBinNumber(bin, requestedBytes);
02994        end->bin = bin;
02995        gcstats[bin].nallocs++;
02996        gcstats[bin].allocTime += delta;
02997        gcstats[bin].allocTimeVariance += delta * delta;
02998     }
02999 #endif
03000 #ifdef GC_CHECK
03001     if (_pr_gcData.flags & GC_CHECK) {
03002     /* Place a pattern in the memory that was allocated that was not
03003        requested. We will check the pattern later. */
03004     char* cp = (char*)(p + 1) + requestedBytes;
03005        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
03006        char i = (char) 0xff;
03007        while (cp < (char*)end) {
03008            *cp++ = i--;
03009        }
03010        end->requestedBytes = requestedBytes;
03011        CheckHeap();
03012     }
03013 #endif
03014     return p + 1;
03015 
03016   lost:
03017     /* Out of memory */
03018     UNLOCK_GC();
03019     if (final) {
03020     FreeFinalNode(final);
03021     }
03022     if (weak) {
03023     FreeWeakNode(weak);
03024     }
03025     if (collectorCleanupNeeded) {
03026     CollectorCleanup();
03027     }
03028     return 0;
03029 }
03030 
03031 /* Shortcut allocator for objects that do not require finalization or
03032    are weak objects */
03033 PR_IMPLEMENT(PRWord GCPTR *)
03034 PR_AllocSimpleMemory(PRWord requestedBytes, PRInt32 tix)
03035 {
03036     PRWord *p;
03037     PRInt32 bytes;
03038     PRInt32 objBytes;
03039 #ifdef GC_STATS
03040     PRInt64 allocTime, ldelta;
03041 #endif
03042 
03043     if (!allocationEnabled) return NULL;
03044 
03045     PR_ASSERT(requestedBytes >= 0);
03046     PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
03047 
03048 #ifdef DEBUG
03049     if (_pr_do_a_dump) {
03050        /*
03051        ** Collect, pause for a second (lets finalizer run), and then GC
03052        ** again.
03053        */
03054        PR_GC();
03055        PR_Sleep(PR_MicrosecondsToInterval(1000000L));
03056        PR_GC();
03057        PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
03058        _pr_do_a_dump = 0;
03059     }
03060 #endif
03061 
03062 #ifdef GC_STATS
03063     allocTime = PR_NowMS();
03064 #endif
03065     bytes = (PRInt32) requestedBytes;
03066 
03067     /*
03068     ** Align bytes to a multiple of a PRWord, then add in enough space
03069     ** to hold the header word.
03070     **
03071     ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
03072     */
03073 #if !defined(WIN16) 
03074     bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
03075     bytes <<= PR_BYTES_PER_WORD_LOG2;
03076     bytes += sizeof(PRWord);
03077 #else 
03078     /* 
03079     ** For WIN16 the shifts have been broken out into separate statements
03080     ** to prevent the compiler from crashing...
03081     */
03082     {
03083     PRWord shiftVal;
03084 
03085     bytes += PR_BYTES_PER_WORD - 1L;
03086     shiftVal = PR_BYTES_PER_WORD_LOG2;
03087     bytes >>= shiftVal;
03088     bytes <<= shiftVal;
03089     bytes += sizeof(PRWord);
03090     }
03091 #endif
03092     
03093     /*
03094      * Add in an extra word of memory for double-aligned memory. Some
03095      * percentage of the time this will waste a word of memory (too
03096      * bad). Howver, it makes the allocation logic much simpler and
03097      * faster.
03098      */
03099 #ifndef IS_64
03100     bytes += PR_BYTES_PER_WORD;
03101 #endif
03102 
03103 #ifdef GC_CHECK
03104     if (_pr_gcData.flags & GC_CHECK) {
03105     /* Bloat the allocation a bit so that we can lay down
03106        a check pattern that we will validate */
03107     bytes += PR_BYTES_PER_WORD * 2;
03108     }
03109 #endif
03110 
03111 #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
03112     bytes += sizeof(GCBlockEnd);
03113 #endif
03114 
03115 #if defined(WIN16)
03116     PR_ASSERT( bytes < MAX_ALLOC_SIZE );
03117 #endif
03118     /* Java can ask for objects bigger than 4M, but it won't get them */
03119     /*
03120      * This check was added because there is a fundamental limit of
03121      * the size field maintained by the gc code.  Going over the 4M
03122      * limit caused some bits to roll over into another bit field,
03123      * violating the max segment size and causing a bug.
03124      */
03125     if (bytes >= MAX_ALLOC_SIZE) {
03126         return NULL;
03127     }
03128 #ifdef DEBUG
03129     if (gc_thrash == -1L
03130        ? (gc_thrash = (long)PR_GetEnv("GC_THRASH"))
03131        : gc_thrash) {
03132        PR_GC();
03133     }
03134 #endif
03135 
03136     LOCK_GC();
03137 #ifdef GC_CHECK
03138     if (_pr_gcData.flags & GC_CHECK) {
03139     CheckHeap();
03140     }
03141     allocationCount++;
03142 #endif
03143 
03144     /* Try default allocation */
03145     if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
03146     p = BigAlloc(tix, bytes, 1);
03147     } else {
03148     p = BinAlloc(tix, bytes, 1);
03149     }
03150     if (0 == p) {
03151 #ifdef GC_STATS
03152       LL_SUB(ldelta, PR_Now(), allocTime);
03153 #endif
03154       /* Collect some memory */
03155       _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
03156       dogc();
03157       PR_ASSERT( GC_IS_LOCKED() );
03158 
03159       /* After a collection we check and see if we should grow the
03160      heap. We grow the heap when the amount of memory free is less
03161      than a certain percentage of the heap size. We don't check to
03162      see if the grow succeeded because our fallback strategy in
03163      either case is to try one more time to allocate. */
03164       if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory) &&
03165       (_pr_gcData.freeMemory <
03166        ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))) {
03167     GrowHeap(PR_MAX(bytes, segmentSize));
03168       }
03169 #ifdef GC_STATS
03170       LL_ADD(allocTime, PR_Now(), ldelta);
03171 #endif
03172 
03173       /* Try one last time */
03174       if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
03175     p = BigAlloc(tix, bytes, 1);
03176       } else {
03177     p = BinAlloc(tix, bytes, 1);
03178       }
03179       if (0 == p) {
03180     /* Well that lost big time. Memory must be pretty well fragmented */
03181     if (!GrowHeap(PR_MAX(bytes, segmentSize))) {
03182       goto lost;
03183     }
03184     p = BinAlloc(tix, bytes, 1);
03185     if (0 == p) goto lost;
03186       }
03187     }
03188 
03189     /* Zero out the portion of the object memory that was used by
03190        the GCFreeChunk structure (skip the first word because it
03191        was already overwritten by the gc header word) */
03192     objBytes = OBJ_BYTES(p[0]);
03193     if (objBytes > sizeof(PRWord)) p[1] = 0;
03194     if (objBytes > sizeof(PRWord)*2) p[2] = 0;
03195 
03196     METER(meter.allocBytes += bytes);
03197     METER(meter.wastedBytes += (bytes - requestedBytes));
03198     UNLOCK_GC();
03199 
03200     if (collectorCleanupNeeded) {
03201        CollectorCleanup();
03202     }
03203 
03204 #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
03205     {
03206        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
03207        end->check = PR_BLOCK_END;
03208     }
03209 #endif
03210 #ifdef GC_STATS
03211     {
03212        PRInt64 now = PR_Now();
03213        double delta;
03214        PRInt32 bin;
03215        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
03216 
03217        end->allocTime = allocTime;
03218        LL_SUB(ldelta, now, allocTime);
03219        LL_L2D(delta, ldelta);
03220        InlineBinNumber(bin, requestedBytes);
03221        end->bin = bin;
03222        gcstats[bin].nallocs++;
03223        gcstats[bin].allocTime += delta;
03224        gcstats[bin].allocTimeVariance += delta * delta;
03225     }
03226 #endif
03227 #ifdef GC_CHECK
03228     if (_pr_gcData.flags & GC_CHECK) {
03229     /* Place a pattern in the memory that was allocated that was not
03230        requested. We will check the pattern later. */
03231     char* cp = (char*)(p + 1) + requestedBytes;
03232        GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
03233        char i = (char) 0xff;
03234        while (cp < (char*)end) {
03235            *cp++ = i--;
03236        }
03237        end->requestedBytes = requestedBytes;
03238        CheckHeap();
03239     }
03240 #endif
03241     return p + 1;
03242 
03243   lost:
03244     /* Out of memory */
03245     UNLOCK_GC();
03246     if (collectorCleanupNeeded) {
03247     CollectorCleanup();
03248     }
03249     return 0;
03250 }
03251 
03252 /************************************************************************/
03253 
03254 PR_IMPLEMENT(PRWord) PR_GetObjectHeader(void *ptr) {
03255     GCSeg *sp;
03256     PRWord *h;
03257 
03258     if (ptr == 0) return 0;
03259     sp = InHeap(ptr);
03260     if (sp == 0) return 0;
03261     h = (PRWord*)FindObject(sp, (PRWord*)ptr);
03262     return GC_GET_USER_BITS(h[0]);
03263 }
03264 
03265 PR_IMPLEMENT(PRWord) PR_SetObjectHeader(void *ptr, PRWord newUserBits) {
03266     GCSeg *sp;
03267     PRWord *h, rv;
03268 
03269     if (ptr == 0) return 0;
03270     sp = InHeap(ptr);
03271     if (sp == 0) return 0;
03272     h = (PRWord*)FindObject(sp, (PRWord*)ptr);
03273     rv = GC_GET_USER_BITS(h[0]);
03274     h[0] = (h[0] & ~GC_USER_BITS) |
03275     ((newUserBits << GC_USER_BITS_SHIFT) & GC_USER_BITS);
03276     return rv;
03277 }
03278 
03279 PR_IMPLEMENT(void) PR_InitGC(
03280     PRWord flags, PRInt32 initialHeapSize, PRInt32 segSize, PRThreadScope scope)
03281 {
03282     static char firstTime = 1;
03283 
03284     if (!firstTime) return;
03285     firstTime = 0;
03286 
03287     _pr_msgc_lm = PR_NewLogModule("msgc");
03288     _pr_pageShift = PR_GetPageShift();
03289     _pr_pageSize = PR_GetPageSize();
03290 
03291 #if defined(WIN16)
03292     PR_ASSERT( initialHeapSize < MAX_ALLOC_SIZE );
03293 #endif
03294 
03295   /* Setup initial heap size and initial segment size */
03296   if (0 != segSize) segmentSize = segSize;
03297 #ifdef DEBUG
03298     GC = PR_NewLogModule("GC");
03299     {
03300     char *ev = PR_GetEnv("GC_SEGMENT_SIZE");
03301     if (ev && ev[0]) {
03302       PRInt32 newSegmentSize = atoi(ev);
03303       if (0 != newSegmentSize) segmentSize = newSegmentSize;
03304     }
03305     ev = PR_GetEnv("GC_INITIAL_HEAP_SIZE");
03306     if (ev && ev[0]) {
03307       PRInt32 newInitialHeapSize = atoi(ev);
03308       if (0 != newInitialHeapSize) initialHeapSize = newInitialHeapSize;
03309     }
03310     ev = PR_GetEnv("GC_FLAGS");
03311     if (ev && ev[0]) {
03312         flags |= atoi(ev);
03313     }
03314 #ifdef GCMETER
03315         ev = PR_GetEnv("GC_METER");
03316         if (ev && ev[0]) {
03317             _pr_gcMeter = atoi(ev);
03318         }
03319 #endif
03320     }
03321 #endif
03322   if (0 == initialHeapSize) initialHeapSize = segmentSize;
03323   if (initialHeapSize < segmentSize) initialHeapSize = segmentSize;
03324 
03325   _pr_gcData.maxMemory   = MAX_SEGS * segmentSize;
03326   _pr_gcData.liveBlock  = ProcessRootBlock;
03327   _pr_gcData.livePointer = ProcessRootPointer;
03328   _pr_gcData.processRootBlock  = ProcessRootBlock;
03329   _pr_gcData.processRootPointer = ProcessRootPointer;
03330   _pr_gcData.dumpOutput = NULL;
03331 
03332   PR_INIT_CLIST(&_pr_finalizeableObjects);
03333     PR_INIT_CLIST(&_pr_finalQueue);
03334     _PR_InitGC(flags);
03335 
03336     /* Create finalizer thread */
03337     _PR_CreateFinalizer(scope);
03338 
03339   /* Allocate the initial segment for the heap */
03340   minBin = 31;
03341   maxBin = 0;
03342   GrowHeap(initialHeapSize);
03343     PR_RegisterRootFinder(ScanWeakFreeList, "scan weak free list", 0);
03344 }
03345 
03346 #if defined(WIN16)
03347 /*
03348 ** For WIN16 the GC_IN_HEAP() macro must call the private InHeap function.
03349 ** This public wrapper function makes this possible...
03350 */
03351 PR_IMPLEMENT(PRBool)
03352 PR_GC_In_Heap(void *object)
03353 {
03354     return InHeap( object ) != NULL;    
03355 }
03356 #endif
03357 
03358 
03362 #ifdef DEBUG
03363 
03364 static int SegmentOverlaps(int i, int j)
03365 {
03366   return
03367     (((segs[i].limit > segs[j].base) && (segs[i].base < segs[j].base)) ||
03368      ((segs[j].limit > segs[i].base) && (segs[j].base < segs[i].base)));
03369 }
03370 
03371 static void NoSegmentOverlaps(void)
03372 {
03373   int i,j;
03374 
03375   for (i = 0; i < nsegs; i++)
03376     for (j = i+1 ; j < nsegs ; j++)
03377       PR_ASSERT(!SegmentOverlaps(i,j));
03378 }
03379 
03380 static void SegInfoCheck(void)
03381 {
03382   int i;
03383   for (i = 0 ; i < nsegs ; i++)
03384     PR_ASSERT((segs[i].info->hbits) &&
03385              (segs[i].info->hbits == segs[i].hbits) &&
03386              (segs[i].info->base == segs[i].base) &&
03387              (segs[i].info->limit == segs[i].limit));
03388 }
03389 
03390 static void SanityCheckGC()
03391 {
03392   NoSegmentOverlaps();
03393   SegInfoCheck();
03394 }
03395 
03396 #endif
03397 
03398 #if defined(DEBUG) && defined(WIN32)
03399 
03400 extern void *baseaddr;
03401 extern void *lastaddr;
03402 
03403 PR_IMPLEMENT(void)
03404 PR_PrintGCStats(void)
03405 {
03406     long reportedSegSpace = _pr_gcData.busyMemory + _pr_gcData.freeMemory;
03407     char* msg;
03408     long largeCount = 0, largeSize = 0;
03409     long segCount = 0, segSize = 0;
03410     long freeCount = 0, freeSize = 0;
03411     GCSeg *sp, *esp;
03412     GCSegInfo* si;
03413 
03414     LOCK_GC();
03415 
03416     sp = segs;
03417     esp = sp + nsegs;
03418     while (sp < esp) {
03419     long size = sp->info->limit - sp->info->base;
03420     segCount++;
03421     segSize += size;
03422         if (sp->info->fromMalloc) {
03423         largeCount++;
03424         largeSize += size;
03425     }
03426         sp++;
03427     }
03428 
03429     si = freeSegs;
03430     while (si != NULL) {
03431     long size = si->limit - si->base;
03432     freeCount++;
03433     freeSize += size;
03434     si = si->next;
03435     }
03436     
03437     msg = PR_smprintf("\
03438 # GC Stats:\n\
03439 #   vm space:\n\
03440 #     range:      %ld - %ld\n\
03441 #     size:       %ld\n\
03442 #   segments:\n\
03443 #     range:      %ld - %ld\n\
03444 #     count:      %ld (reported: %ld)\n\
03445 #     size:       %ld (reported: %ld)\n\
03446 #     free count: %ld\n\
03447 #     free size:  %ld\n\
03448 #     busy objs:  %ld (%ld%%)\n\
03449 #     free objs:  %ld (%ld%%)\n\
03450 #   large blocks:\n\
03451 #     count:      %ld\n\
03452 #     total size: %ld (%ld%%)\n\
03453 #     avg size:   %ld\n\
03454 ",
03455               /* vm space */
03456               (long)baseaddr, (long)lastaddr,
03457               (long)lastaddr - (long)baseaddr,
03458               /* segments */
03459               _pr_gcData.lowSeg, _pr_gcData.highSeg,
03460               segCount, nsegs,
03461               segSize, reportedSegSpace,
03462               freeCount,
03463               freeSize,
03464               _pr_gcData.busyMemory,
03465               (_pr_gcData.busyMemory * 100 / reportedSegSpace),
03466               _pr_gcData.freeMemory,
03467               (_pr_gcData.freeMemory * 100 / reportedSegSpace),
03468               /* large blocks */
03469               largeCount,
03470               largeSize, (largeSize * 100 / reportedSegSpace),
03471               (largeCount ? largeSize / largeCount : 0)
03472               );
03473     UNLOCK_GC();
03474     fprintf(stderr, msg);
03475     OutputDebugString(msg);
03476     PR_smprintf_free(msg);
03477 #ifdef GC_STATS
03478     PR_PrintGCAllocStats();
03479 #endif
03480 }
03481 #endif
03482 
03483 PR_IMPLEMENT(void)
03484 PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed)
03485 {
03486     FILE *out;
03487     OutputDebugString(msg);
03488     out = fopen(filename, "a");
03489     if (!out) {
03490        char buf[64];
03491        PR_ASSERT(strlen(filename) < sizeof(buf) - 16);
03492        PR_snprintf(buf, sizeof(buf), "Can't open \"%s\"\n",
03493                   filename);
03494        OutputDebugString(buf);
03495     }
03496     else
03497     {
03498        struct tm *newtime;
03499        time_t aclock;
03500        int i;
03501 
03502        time(&aclock);
03503        newtime = localtime(&aclock);
03504        fprintf(out, "%s on %s\n", msg, asctime(newtime));  /* Print current time */
03505        dump(out, detailed);
03506        fprintf(out, "\n\n");
03507        for (i = 0; i < 80; i++)
03508            fprintf(out, "=");
03509        fprintf(out, "\n\n");
03510        fclose(out);
03511     }
03512     OutputDebugString(" done\n");
03513 }
03514