home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / lib / msgc / src / prmsgc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  96.2 KB  |  3,474 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #include <string.h>
  20. #include <stddef.h>
  21. #include <stdarg.h>
  22. #include <time.h>
  23.  
  24. #include "prclist.h"
  25. #include "prbit.h"
  26.  
  27. #include "prtypes.h"
  28. #include "prenv.h"
  29. #include "prgc.h"
  30. #include "prthread.h"
  31. #include "prlog.h"
  32. #include "prlong.h"
  33. #include "prinrval.h"
  34. #include "prprf.h"
  35. #include "gcint.h"
  36.  
  37. #if defined(XP_MAC)
  38. #include "pprthred.h"
  39. #else
  40. #include "private/pprthred.h"
  41. #endif
  42.  
  43. typedef void (*PRFileDumper)(FILE *out, PRBool detailed);
  44.  
  45. PR_EXTERN(void)
  46. PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed);
  47.  
  48. /*
  49. ** Mark&sweep garbage collector. Supports objects that require
  50. ** finalization, objects that can have a single weak link, and special
  51. ** objects that require care during sweeping.
  52. */
  53.  
  54. PRLogModuleInfo *_pr_msgc_lm;
  55. PRLogModuleInfo* GC;
  56.  
  57. static PRInt32 _pr_pageShift;
  58. static PRInt32 _pr_pageSize;
  59.  
  60. #ifdef DEBUG
  61. #define GCMETER
  62. #endif
  63. #ifdef DEBUG_jwz
  64. # undef GCMETER
  65. #endif /* 1 */
  66.  
  67. #ifdef GCMETER
  68. #define METER(x) x
  69. #else
  70. #define METER(x)
  71. #endif
  72.  
  73. /*
  74. ** Make this constant bigger to reduce the amount of recursion during
  75. ** garbage collection.
  76. */
  77. #define MAX_SCAN_Q    100L
  78.  
  79. #if defined(XP_PC) && !defined(WIN32)
  80. #define MAX_SEGS            400L
  81. #define MAX_SEGMENT_SIZE    (65536L - 4096L)
  82. #define SEGMENT_SIZE        (65536L - 4096L)
  83. #define MAX_ALLOC_SIZE      (65536L - 4096L)
  84. #else
  85. #define MAX_SEGS                    400L
  86. #define MAX_SEGMENT_SIZE            (2L * 256L * 1024L)
  87. #define SEGMENT_SIZE                (1L * 256L * 1024L)
  88. #define MAX_ALLOC_SIZE              (4L * 1024L * 1024L)
  89. #endif  
  90.  
  91. /* 
  92.  * The highest value that can fit into a signed integer. This
  93.  * is used to prevent overflow of allocation size in alloc routines.
  94.  */
  95.  
  96. #define MAX_INT ((1UL << (PR_BITS_PER_INT - 1)) - 1)
  97.  
  98. /* 
  99.  * On 32-bit machines, only 22 bits are used in the cibx integer to
  100.  * store size since 8 bits of the integer are used to store type, and
  101.  * of the remainder, 2 are user defined. Max allocation size = 2^22 -1
  102.  */
  103.  
  104. #define MAX_ALLOC ( (1L << (PR_BYTES_PER_WORD_LOG2 + WORDS_BITS )) -1)
  105.  
  106. /* The minimum percentage of free heap space after a collection. If
  107.    the amount of free space doesn't meet this criteria then we will
  108.    attempt to grow the heap */
  109. #ifdef XP_MAC
  110. #define MIN_FREE_THRESHOLD_AFTER_GC 10L
  111. #else
  112. #define MIN_FREE_THRESHOLD_AFTER_GC 20L
  113. #endif
  114.  
  115. static PRInt32 segmentSize = SEGMENT_SIZE;
  116.  
  117. static PRInt32 collectorCleanupNeeded;
  118.  
  119. #ifdef GCMETER
  120. PRUint32 _pr_gcMeter;
  121.  
  122. #define _GC_METER_STATS         0x01L
  123. #define _GC_METER_GROWTH        0x02L
  124. #define _GC_METER_FREE_LIST     0x04L
  125. #endif
  126.  
  127. /************************************************************************/
  128.  
  129. /* Each free list bin holds a chunk of memory sized from
  130.    2^n to (2^(n+1))-1 inclusive. */
  131. #define NUM_BINS        32
  132.  
  133. /*
  134.  * Find the bin number for a given size (in bytes). This does not round up as
  135.  * values from 2^n to (2^(n+1))-1 share the same bin.
  136.  */
  137. #define InlineBinNumber(_bin,_bytes)              \
  138. {                              \
  139.     PRUint32 _t, _n = (PRUint32) _bytes;              \
  140.     _bin = 0;                          \
  141.     if ((_t = (_n >> 16)) != 0) { _bin += 16; _n = _t;    } \
  142.     if ((_t = (_n >> 8)) != 0)  { _bin += 8; _n = _t; }      \
  143.     if ((_t = (_n >> 4)) != 0)  { _bin += 4; _n = _t; }      \
  144.     if ((_t = (_n >> 2)) != 0) { _bin += 2; _n = _t; }      \
  145.     if ((_n >> 1) != 0) _bin++;                  \
  146. }
  147.  
  148. #define BIG_ALLOC       16384L
  149.  
  150. #define MIN_FREE_CHUNK_BYTES    ((PRInt32)sizeof(GCFreeChunk))
  151.  
  152. /* Note: fix code in PR_AllocMemory if you change the size of GCFreeChunk
  153.    so that it zeros the right number of words */
  154. typedef struct GCFreeChunk {
  155.     struct GCFreeChunk *next;
  156.     struct GCSeg *segment;
  157.     PRInt32 chunkSize;
  158. } GCFreeChunk;
  159.  
  160. typedef struct GCSegInfo {
  161.     struct GCSegInfo *next;
  162.     char *base;
  163.     char *limit;
  164.     PRWord *hbits;
  165.     int fromMalloc;
  166. } GCSegInfo;
  167.     
  168. typedef struct GCSeg {
  169.     char *base;
  170.     char *limit;
  171.     PRWord *hbits;
  172.     GCSegInfo *info;
  173. } GCSeg;
  174.  
  175. #ifdef GCMETER
  176. typedef struct GCMeter {
  177.     PRInt32 allocBytes;
  178.     PRInt32 wastedBytes;
  179.     PRInt32 numFreeChunks;
  180.     PRInt32 skippedFreeChunks;
  181. } GCMeter;
  182. static GCMeter meter;
  183. #endif
  184.  
  185. /*
  186. ** There is one of these for each segment of GC'able memory.
  187. */
  188. static GCSeg segs[MAX_SEGS];
  189. static GCSegInfo *freeSegs;
  190. static GCSeg* lastInHeap;
  191. static int nsegs;
  192.  
  193. static GCFreeChunk *bins[NUM_BINS];
  194. static PRInt32 minBin;
  195. static PRInt32 maxBin;
  196.  
  197. /*
  198. ** Scan Q used to avoid deep recursion when scanning live objects for
  199. ** heap pointers
  200. */
  201. typedef struct GCScanQStr {
  202.     PRWord *q[MAX_SCAN_Q];
  203.     int queued;
  204. } GCScanQ;
  205.  
  206. static GCScanQ *pScanQ;
  207.  
  208. #ifdef GCMETER
  209. PRInt32 _pr_maxScanDepth;
  210. PRInt32 _pr_scanDepth;
  211. #endif
  212.  
  213. /*
  214. ** Keeps track of the number of bytes allocated via the BigAlloc() 
  215. ** allocator.  When the number of bytes allocated, exceeds the 
  216. ** BIG_ALLOC_GC_SIZE, then a GC will occur before the next allocation
  217. ** is done...
  218. */
  219. #define BIG_ALLOC_GC_SIZE       (4*SEGMENT_SIZE)
  220. static PRWord bigAllocBytes = 0;
  221.  
  222. /*
  223. ** There is one GC header word in front of each GC allocated object.  We
  224. ** use it to contain information about the object (what TYPEIX to use for
  225. ** scanning it, how big it is, it's mark status, and if it's a root).
  226. */
  227. #define TYPEIX_BITS    8L
  228. #define WORDS_BITS    20L
  229. #define MAX_CBS        (1L << GC_TYPEIX_BITS)
  230. #define MAX_WORDS    (1L << GC_WORDS_BITS)
  231. #define TYPEIX_SHIFT    24L
  232. #define MAX_TYPEIX    ((1L << TYPEIX_BITS) - 1L)
  233. #define TYPEIX_MASK    PR_BITMASK(TYPEIX_BITS)
  234. #define WORDS_SHIFT    2L
  235. #define WORDS_MASK    PR_BITMASK(WORDS_BITS)
  236. #define MARK_BIT    1L
  237. #define FINAL_BIT    2L
  238.  
  239. /* Two bits per object header are reserved for the user of the memory
  240.    system to store information into. */
  241. #define GC_USER_BITS_SHIFT 22L
  242. #define GC_USER_BITS    0x00c00000L
  243.  
  244. #define MAKE_HEADER(_cbix,_words)              \
  245.     ((PRWord) (((unsigned long)(_cbix) << TYPEIX_SHIFT) \
  246.          | ((unsigned long)(_words) << WORDS_SHIFT)))
  247.  
  248. #define GET_TYPEIX(_h) \
  249.     (((PRUword)(_h) >> TYPEIX_SHIFT) & 0xff)
  250.  
  251. #define MARK(_sp,_p) \
  252.     (((PRWord *)(_p))[0] |= MARK_BIT)
  253. #define IS_MARKED(_sp,_p) \
  254.     (((PRWord *)(_p))[0] & MARK_BIT)
  255. #define OBJ_BYTES(_h) \
  256.     (((PRInt32) (_h) & 0x003ffffcL) << (PR_BYTES_PER_WORD_LOG2-2L))
  257.  
  258. #define GC_GET_USER_BITS(_h) (((_h) & GC_USER_BITS) >> GC_USER_BITS_SHIFT)
  259.  
  260. /************************************************************************/
  261.  
  262. /*
  263. ** Mark the start of an object in a segment. Note that we mark the header
  264. ** word (which we always have), not the data word (which we may not have
  265. ** for empty objects).
  266. ** XXX tune: put subtract of _sp->base into _sp->hbits pointer?
  267. */
  268. #if !defined(WIN16)
  269. #define SET_HBIT(_sp,_ph) \
  270.     SET_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
  271.  
  272. #define CLEAR_HBIT(_sp,_ph) \
  273.     CLEAR_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
  274.  
  275. #define IS_HBIT(_sp,_ph) \
  276.     TEST_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))
  277. #else
  278.  
  279. #define SET_HBIT(_sp,_ph) set_hbit(_sp,_ph)
  280.  
  281. #define CLEAR_HBIT(_sp,_ph) clear_hbit(_sp,_ph)
  282.  
  283. #define IS_HBIT(_sp,_ph) is_hbit(_sp,_ph)
  284.  
  285. static void
  286. set_hbit(GCSeg *sp, PRWord *p)
  287. {
  288.     unsigned int distance;
  289.     unsigned int index;
  290.     PRWord     mask;
  291.  
  292.         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
  293.         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
  294.  
  295.         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
  296.     index    = distance >> PR_BITS_PER_WORD_LOG2;
  297.     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
  298.  
  299.     sp->hbits[index] |= mask;
  300. }
  301.  
  302. static void
  303. clear_hbit(GCSeg *sp, PRWord *p)
  304. {
  305.     unsigned int distance;
  306.     unsigned int index;
  307.     PRWord    mask;
  308.  
  309.         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
  310.         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
  311.  
  312.         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
  313.     index    = distance >> PR_BITS_PER_WORD_LOG2;
  314.     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
  315.  
  316.     sp->hbits[index] &= ~mask;
  317. }
  318.  
  319. static int
  320. is_hbit(GCSeg *sp, PRWord *p)
  321. {
  322.     unsigned int distance;
  323.     unsigned int index;
  324.     PRWord    mask;
  325.  
  326.         PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
  327.         PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );
  328.  
  329.         distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
  330.     index    = distance >> PR_BITS_PER_WORD_LOG2;
  331.     mask     = 1L << (distance&(PR_BITS_PER_WORD-1));
  332.  
  333.     return ((sp->hbits[index] & mask) != 0);
  334. }
  335.  
  336.  
  337. #endif  /* WIN16 */
  338.  
  339. /*
  340. ** Given a pointer into this segment, back it up until we are at the
  341. ** start of the object the pointer points into. Each heap segment has a
  342. ** bitmap that has one bit for each word of the objects it contains.  The
  343. ** bit's are set for the firstword of an object, and clear for it's other
  344. ** words.
  345. */
  346. static PRWord *FindObject(GCSeg *sp, PRWord *p)
  347. {
  348.     PRWord *base;
  349.     
  350.     /* Align p to it's proper boundary before we start fiddling with it */
  351.     p = (PRWord*) ((PRWord)p & ~(PR_BYTES_PER_WORD-1L));
  352.  
  353.     base = (PRWord *) sp->base;
  354. #if defined(WIN16)
  355.     PR_ASSERT( SELECTOROF(p) == SELECTOROF(base));
  356. #endif
  357.     do {
  358.     if (IS_HBIT(sp, p)) {
  359.         return (p);
  360.     }
  361.     p--;
  362.     } while ( p >= base );
  363.  
  364.     /* Heap is corrupted! */
  365.     _GCTRACE(GC_TRACE, ("ERROR: The heap is corrupted!!! aborting now!"));
  366.     abort();
  367.     return NULL;
  368. }
  369.  
  370. /************************************************************************/
  371. #if !defined(XP_PC) || defined(XP_OS2)
  372. #define OutputDebugString(msg)
  373. #endif 
  374.  
  375. #if !defined(WIN16)
  376. #define IN_SEGMENT(_sp, _p)             \
  377.     ((((char *)(_p)) >= (_sp)->base) &&    \
  378.      (((char *)(_p)) < (_sp)->limit))
  379. #else
  380. #define IN_SEGMENT(_sp, _p)                  \
  381.     ((((PRWord)(_p)) >= ((PRWord)(_sp)->base)) && \
  382.      (((PRWord)(_p)) < ((PRWord)(_sp)->limit)))
  383. #endif
  384.  
  385. static GCSeg *InHeap(void *p)
  386. {
  387.     GCSeg *sp, *esp;
  388.  
  389.     if (lastInHeap && IN_SEGMENT(lastInHeap, p)) {
  390.     return lastInHeap;
  391.     }
  392.  
  393.     sp = segs;
  394.     esp = segs + nsegs;
  395.     for (; sp < esp; sp++) {
  396.     if (IN_SEGMENT(sp, p)) {
  397.         lastInHeap = sp;
  398.         return sp;
  399.     }
  400.     }
  401.     return 0;
  402. }
  403.  
  404. /*
  405. ** Grow the heap by allocating another segment. Fudge the requestedSize
  406. ** value to try to pre-account for the HBITS.
  407. */
  408. static GCSeg* DoGrowHeap(PRInt32 requestedSize, PRBool exactly)
  409. {
  410.     GCSeg *sp;
  411.     GCSegInfo *segInfo;
  412.     GCFreeChunk *cp;
  413.     char *base;
  414.     PRWord *hbits;
  415.     PRInt32 nhbytes, nhbits;
  416.     PRUint32 allocSize;
  417.  
  418.     if (nsegs == MAX_SEGS) {
  419.     /* No room for more segments */
  420.     return 0;
  421.     }
  422.  
  423.     segInfo = (GCSegInfo*) PR_MALLOC(sizeof(GCSegInfo));
  424. #ifdef DEBUG
  425.     {
  426.     char str[256];
  427.     sprintf(str, "[1] Allocated %d bytes at %p\n", sizeof(GCSegInfo), segInfo);
  428.     OutputDebugString(str);
  429.     }
  430. #endif
  431.     if (!segInfo) {
  432.     return 0;
  433.     }
  434.  
  435. #if defined(WIN16)
  436.     if (requestedSize > segmentSize) {
  437.     PR_DELETE(segInfo);
  438.     return 0;
  439.     }
  440. #endif
  441.  
  442.     /* Get more memory from the OS */
  443.     if (exactly) {
  444.     allocSize = requestedSize;
  445.     base = (char *) PR_MALLOC(requestedSize);
  446.     } else {
  447.     allocSize = requestedSize;
  448.     allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
  449.     allocSize <<= _pr_pageShift;
  450.     base = (char*)_MD_GrowGCHeap(&allocSize);
  451.     }
  452.     if (!base) {
  453.     PR_DELETE(segInfo);
  454.     return 0;
  455.     }
  456.  
  457.     nhbits = (PRInt32)(
  458.         (allocSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2);
  459.     nhbytes = ((nhbits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
  460.     * sizeof(PRWord);
  461.  
  462.     /* Get bitmap memory from malloc heap */
  463. #if defined(WIN16)
  464.     PR_ASSERT( nhbytes < MAX_ALLOC_SIZE );
  465. #endif
  466.     hbits = (PRWord *) PR_CALLOC((PRUint32)nhbytes);
  467.     if (!hbits) {
  468.     /* Loser! */
  469.     PR_DELETE(segInfo);
  470.     if (exactly) {
  471.         PR_DELETE(base);
  472.     } else {
  473.       /* XXX do something about this */
  474.       /* _MD_FreeGCSegment(base, allocSize); */
  475.     }
  476.     return 0;
  477.     }
  478.  
  479.     /*
  480.     ** Setup new segment.
  481.     */
  482.     sp = &segs[nsegs++];
  483.     segInfo->base = sp->base = base;
  484.     segInfo->limit = sp->limit = base + allocSize;
  485.     segInfo->hbits = sp->hbits = hbits;
  486.     sp->info = segInfo;
  487.     segInfo->fromMalloc = exactly;
  488.     memset(base, 0, allocSize);
  489.  
  490. #ifdef GCMETER
  491.     if (_pr_gcMeter & _GC_METER_GROWTH) {
  492.         fprintf(stderr, "[GC: new segment base=%p size=%d]\n",
  493.                 sp->base, allocSize);
  494.     }
  495. #endif    
  496.  
  497.     _pr_gcData.allocMemory += allocSize;
  498.     _pr_gcData.freeMemory  += allocSize;
  499.  
  500.     if (!exactly) {
  501.     PRInt32 bin;
  502.  
  503.         /* Put free memory into a freelist bin */
  504.         cp = (GCFreeChunk *) base;
  505.         cp->segment = sp;
  506.         cp->chunkSize = allocSize;
  507.         InlineBinNumber(bin, allocSize)
  508.         cp->next = bins[bin];
  509.         bins[bin] = cp;
  510.     if (bin < minBin) minBin = bin;
  511.     if (bin > maxBin) maxBin = bin;
  512.     } else {
  513.         /*
  514.         ** When exactly allocating the entire segment is given over to a
  515.         ** single object to prevent fragmentation
  516.         */
  517.     }
  518.  
  519.     if (!_pr_gcData.lowSeg) {
  520.     _pr_gcData.lowSeg  = (PRWord*) sp->base;
  521.     _pr_gcData.highSeg = (PRWord*) sp->limit;
  522.     } else {
  523.     if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
  524.         _pr_gcData.lowSeg = (PRWord*) sp->base;
  525.     }
  526.     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
  527.         _pr_gcData.highSeg = (PRWord*) sp->limit;
  528.     }
  529.     }
  530.  
  531.     /* 
  532.     ** Get rid of the GC pointer in case it shows up in some uninitialized
  533.     ** local stack variable later (while scanning the C stack looking for
  534.     ** roots).
  535.     */ 
  536.     memset(&base, 0, sizeof(base));  /* optimizers beware */
  537.  
  538.     PR_LOG(_pr_msgc_lm, PR_LOG_WARNING, ("grow heap: total gc memory now %d",
  539.                       _pr_gcData.allocMemory));
  540.  
  541.     return sp;
  542. }
  543.  
  544. #ifdef USE_EXTEND_HEAP
  545. static PRBool ExtendHeap(PRInt32 requestedSize) {
  546.   GCSeg* sp;
  547.   PRUint32 allocSize;
  548.   PRInt32 oldSize, newSize;
  549.   PRInt32 newHBits, newHBytes;
  550.   PRInt32 oldHBits, oldHBytes;
  551.   PRWord* hbits;
  552.   GCFreeChunk* cp;
  553.   PRInt32 bin;
  554.  
  555.   /* Can't extend nothing */
  556.   if (nsegs == 0) return PR_FALSE;
  557.  
  558.   /* Round up requested size to the size of a page */
  559.   allocSize = (PRUint32) requestedSize;
  560.   allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
  561.   allocSize <<= _pr_pageShift;
  562.  
  563.   /* Malloc some memory for the new hbits array */
  564.   sp = segs;
  565.   oldSize = sp->limit - sp->base;
  566.   newSize = oldSize + allocSize;
  567.   newHBits = (newSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
  568.   newHBytes = ((newHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
  569.     * sizeof(PRWord);
  570.   hbits = (PRWord*) PR_MALLOC(newHBytes);
  571.   if (0 == hbits) return PR_FALSE;
  572.  
  573.   /* Attempt to extend the last segment by the desired amount */
  574.   if (_MD_ExtendGCHeap(sp->base, oldSize, newSize)) {
  575.     oldHBits = (oldSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
  576.     oldHBytes = ((oldHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
  577.       * sizeof(PRWord);
  578.  
  579.     /* Copy hbits from old memory into new memory */
  580.     memset(hbits, 0, newHBytes);
  581.     memcpy(hbits, sp->hbits, oldHBytes);
  582.     PR_DELETE(sp->hbits);
  583.     memset(sp->base + oldSize, 0, allocSize);
  584.  
  585.     /* Adjust segment state */
  586.     sp->limit += allocSize;
  587.     sp->hbits = hbits;
  588.     sp->info->limit = sp->limit;
  589.     sp->info->hbits = hbits;
  590.  
  591.     /* Put free memory into a freelist bin */
  592.     cp = (GCFreeChunk *) (sp->base + oldSize);
  593.     cp->segment = sp;
  594.     cp->chunkSize = allocSize;
  595.     InlineBinNumber(bin, allocSize)
  596.     cp->next = bins[bin];
  597.     bins[bin] = cp;
  598.     if (bin < minBin) minBin = bin;
  599.     if (bin > maxBin) maxBin = bin;
  600.  
  601.     /* Prevent a pointer that points to the free memory from showing
  602.        up on the call stack later on */
  603.     memset(&cp, 0, sizeof(cp));
  604.  
  605.     /* Update heap brackets and counters */
  606.     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
  607.       _pr_gcData.highSeg = (PRWord*) sp->limit;
  608.     }
  609.     _pr_gcData.allocMemory += allocSize;
  610.     _pr_gcData.freeMemory  += allocSize;
  611.  
  612.     return PR_TRUE;
  613.   }
  614.   PR_DELETE(hbits);
  615.   return PR_FALSE;
  616. }
  617. #endif /* USE_EXTEND_HEAP */
  618.  
  619. static GCSeg *GrowHeapExactly(PRInt32 requestedSize)
  620. {
  621.     GCSeg *sp = DoGrowHeap(requestedSize, PR_TRUE);
  622.     return sp;
  623. }
  624.  
  625. static PRBool GrowHeap(PRInt32 requestedSize)
  626. {
  627.   void *p;
  628. #ifdef USE_EXTEND_HEAP
  629.   if (ExtendHeap(requestedSize)) {
  630.     return PR_TRUE;
  631.   }
  632. #endif
  633.   p = DoGrowHeap(requestedSize, PR_FALSE);
  634.   return (p != NULL ? PR_TRUE : PR_FALSE);
  635. }
  636.  
  637. /*
  638. ** Release a segment when it is entirely free.
  639. */
  640. static void ShrinkGCHeap(GCSeg *sp)
  641. {
  642. #ifdef GCMETER
  643.     if (_pr_gcMeter & _GC_METER_GROWTH) {
  644.         fprintf(stderr, "[GC: free segment base=%p size=%d]\n",
  645.                 sp->base, sp->limit - sp->base);
  646.     }
  647. #endif    
  648.  
  649.     /*
  650.      * Put segment onto free seginfo list (we can't call free right now
  651.      * because we have the GC lock and all of the other threads are
  652.      * suspended; if one of them has the malloc lock we would deadlock)
  653.      */
  654.     sp->info->next = freeSegs;
  655.     freeSegs = sp->info;
  656.     collectorCleanupNeeded = 1;
  657.     _pr_gcData.allocMemory -= sp->limit - sp->base;
  658.     if (sp == lastInHeap) lastInHeap = 0;
  659.  
  660.     /* Squish out disappearing segment from segment table */
  661.     --nsegs;
  662.     if ((sp - segs) != nsegs) {
  663.         *sp = segs[nsegs];
  664.     } else {
  665.         sp->base = 0;
  666.         sp->limit = 0;
  667.         sp->hbits = 0;
  668.     sp->info = 0;
  669.     }
  670.  
  671.     /* Recalculate the lowSeg and highSeg values */
  672.     _pr_gcData.lowSeg  = (PRWord*) segs[0].base;
  673.     _pr_gcData.highSeg = (PRWord*) segs[0].limit;
  674.     for (sp = segs; sp < &segs[nsegs]; sp++) {
  675.     if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
  676.         _pr_gcData.lowSeg = (PRWord*) sp->base;
  677.     }
  678.     if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
  679.         _pr_gcData.highSeg = (PRWord*) sp->limit;
  680.     }
  681.     }
  682. }
  683.  
  684. static void FreeSegments(void)
  685. {
  686.     GCSegInfo *si;
  687.  
  688.     while (0 != freeSegs) {
  689.     LOCK_GC();
  690.     si = freeSegs;
  691.     if (si) {
  692.         freeSegs = si->next;
  693.     }
  694.     UNLOCK_GC();
  695.  
  696.     if (!si) {
  697.         break;
  698.     }
  699.     PR_DELETE(si->base);
  700.     PR_DELETE(si->hbits);
  701.     PR_DELETE(si);
  702.     }
  703. }
  704.  
  705. /************************************************************************/
  706.  
  707. void ScanScanQ(GCScanQ *iscan)
  708. {
  709.     PRWord *p;
  710.     PRWord **pp;
  711.     PRWord **epp;
  712.     GCScanQ nextQ, *scan, *next, *temp;
  713.     CollectorType *ct;
  714.  
  715.     if (!iscan->queued) return;
  716.  
  717.     _GCTRACE(GC_MARK, ("begin scanQ @ 0x%x (%d)", iscan, iscan->queued));
  718.     scan = iscan;
  719.     next = &nextQ;
  720.     while (scan->queued) {
  721.     _GCTRACE(GC_MARK, ("continue scanQ @ 0x%x (%d)", scan, scan->queued));
  722.     /* Set pointer to current scanQ so that pr_liveObject can find it */
  723.     pScanQ = next;
  724.     next->queued = 0;
  725.  
  726.     /* Now scan the scan Q */
  727.     pp = scan->q;
  728.     epp = &scan->q[scan->queued];
  729.     scan->queued = 0;
  730.     while (pp < epp) {
  731.         p = *pp++;
  732.         ct = &_pr_collectorTypes[GET_TYPEIX(p[0])];
  733.         PR_ASSERT(0 != ct->gctype.scan);
  734.         /* Scan object ... */
  735.         (*ct->gctype.scan)(p + 1);
  736.     }
  737.  
  738.     /* Exchange pointers so that we scan next */
  739.     temp = scan;
  740.     scan = next;
  741.     next = temp;
  742.     }
  743.  
  744.     pScanQ = iscan;
  745.     PR_ASSERT(nextQ.queued == 0);
  746.     PR_ASSERT(iscan->queued == 0);
  747. }
  748.  
  749. /*
  750. ** Called during root finding step to identify "root" pointers into the
  751. ** GC heap. First validate if it is a real heap pointer and then mark the
  752. ** object being pointed to and add it to the scan Q for eventual
  753. ** scanning.
  754. */
  755. static void PR_CALLBACK ProcessRootBlock(void **base, PRInt32 count)
  756. {
  757.     GCSeg *sp;
  758.     PRWord *p0, *p, h, tix, *low, *high, *segBase;
  759.     CollectorType *ct;
  760. #ifdef DEBUG
  761.     void **base0 = base;
  762. #endif
  763.  
  764.     low = _pr_gcData.lowSeg;
  765.     high = _pr_gcData.highSeg;
  766.     while (--count >= 0) {
  767.         p0 = (PRWord*) *base++;
  768.         /*
  769.         ** XXX:  
  770.         ** Until Win16 maintains lowSeg and highSeg correctly,
  771.         ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
  772.         ** Allways scan through the segment list
  773.         */
  774. #if !defined(WIN16)
  775.         if (p0 < low) continue;                  /* below gc heap */
  776.         if (p0 >= high) continue;                /* above gc heap */
  777. #endif
  778.         /* NOTE: inline expansion of InHeap */
  779.         /* Find segment */
  780.     sp = lastInHeap;
  781.         if (!sp || !IN_SEGMENT(sp,p0)) {
  782.             GCSeg *esp;
  783.             sp = segs;
  784.         esp = segs + nsegs;
  785.             for (; sp < esp; sp++) {
  786.                 if (IN_SEGMENT(sp, p0)) {
  787.                     lastInHeap = sp;
  788.                     goto find_object;
  789.                 }
  790.             }
  791.             continue;
  792.         }
  793.  
  794.       find_object:
  795.         /* NOTE: Inline expansion of FindObject */
  796.         /* Align p to it's proper boundary before we start fiddling with it */
  797.         p = (PRWord*) ((PRWord)p0 & ~(PR_BYTES_PER_WORD-1L));
  798.         segBase = (PRWord *) sp->base;
  799.         do {
  800.             if (IS_HBIT(sp, p)) {
  801.                 goto winner;
  802.             }
  803.             p--;
  804.         } while (p >= segBase);
  805.  
  806.         /*
  807.         ** We have a pointer into the heap, but it has no header
  808.         ** bit. This means that somehow the very first object in the heap
  809.         ** doesn't have a header. This is impossible so when debugging
  810.         ** lets abort.
  811.         */
  812. #ifdef DEBUG
  813.         PR_Abort();
  814. #endif
  815.  
  816.       winner:
  817.         h = p[0];
  818.         if ((h & MARK_BIT) == 0) {
  819. #ifdef DEBUG
  820.             _GCTRACE(GC_ROOTS,
  821.             ("root 0x%p (%d) base0=%p off=%d",
  822.              p, OBJ_BYTES(h), base0, (base-1) - base0));
  823. #endif
  824.  
  825.             /* Mark the root we just found */
  826.             p[0] = h | MARK_BIT;
  827.  
  828.             /*
  829.          * See if object we just found needs scanning. It must
  830.          * have a scan function to be placed on the scanQ.
  831.          */
  832.             tix = (PRWord)GET_TYPEIX(h);
  833.         ct = &_pr_collectorTypes[tix];
  834.         if (0 == ct->gctype.scan) {
  835.         continue;
  836.         }
  837.  
  838.             /*
  839.             ** Put a pointer onto the scan Q. We use the scan Q to avoid
  840.             ** deep recursion on the C call stack. Objects are added to
  841.             ** the scan Q until the scan Q fills up. At that point we
  842.             ** make a call to ScanScanQ which proceeds to scan each of
  843.             ** the objects in the Q. This limits the recursion level by a
  844.             ** large amount though the stack frames get larger to hold
  845.             ** the GCScanQ's.
  846.             */
  847.             pScanQ->q[pScanQ->queued++] = p;
  848.             if (pScanQ->queued == MAX_SCAN_Q) {
  849.                 METER(_pr_scanDepth++);
  850.                 ScanScanQ(pScanQ);
  851.             }
  852.         }
  853.     }
  854. }
  855.  
  856. static void PR_CALLBACK ProcessRootPointer(void *ptr)
  857. {
  858.   PRWord *p0, *p, h, tix, *segBase;
  859.   GCSeg* sp;
  860.   CollectorType *ct;
  861.  
  862.   p0 = (PRWord*) ptr;
  863.  
  864.   /*
  865.   ** XXX:  
  866.   ** Until Win16 maintains lowSeg and highSeg correctly,
  867.   ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
  868.   ** Allways scan through the segment list
  869.   */
  870. #if !defined(WIN16)
  871.   if (p0 < _pr_gcData.lowSeg) return;                  /* below gc heap */
  872.   if (p0 >= _pr_gcData.highSeg) return;                /* above gc heap */
  873. #endif
  874.  
  875.   /* NOTE: inline expansion of InHeap */
  876.   /* Find segment */
  877.   sp = lastInHeap;
  878.   if (!sp || !IN_SEGMENT(sp,p0)) {
  879.     GCSeg *esp;
  880.     sp = segs;
  881.     esp = segs + nsegs;
  882.     for (; sp < esp; sp++) {
  883.       if (IN_SEGMENT(sp, p0)) {
  884.     lastInHeap = sp;
  885.     goto find_object;
  886.       }
  887.     }
  888.     return;
  889.   }
  890.  
  891.  find_object:
  892.   /* NOTE: Inline expansion of FindObject */
  893.   /* Align p to it's proper boundary before we start fiddling with it */
  894.     p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
  895.     segBase = (PRWord *) sp->base;
  896.     do {
  897.       if (IS_HBIT(sp, p)) {
  898.     goto winner;
  899.       }
  900.       p--;
  901.     } while (p >= segBase);
  902.  
  903.     /*
  904.     ** We have a pointer into the heap, but it has no header
  905.     ** bit. This means that somehow the very first object in the heap
  906.     ** doesn't have a header. This is impossible so when debugging
  907.     ** lets abort.
  908.     */
  909. #ifdef DEBUG
  910.     PR_Abort();
  911. #endif
  912.  
  913.  winner:
  914.   h = p[0];
  915.   if ((h & MARK_BIT) == 0) {
  916. #ifdef DEBUG
  917.     _GCTRACE(GC_ROOTS, ("root 0x%p (%d)", p, OBJ_BYTES(h)));
  918. #endif
  919.  
  920.     /* Mark the root we just found */
  921.     p[0] = h | MARK_BIT;
  922.  
  923.     /*
  924.      * See if object we just found needs scanning. It must
  925.      * have a scan function to be placed on the scanQ.
  926.      */
  927.     tix = (PRWord)GET_TYPEIX(h);
  928.     ct = &_pr_collectorTypes[tix];
  929.     if (0 == ct->gctype.scan) {
  930.       return;
  931.     }
  932.  
  933.     /*
  934.     ** Put a pointer onto the scan Q. We use the scan Q to avoid
  935.     ** deep recursion on the C call stack. Objects are added to
  936.     ** the scan Q until the scan Q fills up. At that point we
  937.     ** make a call to ScanScanQ which proceeds to scan each of
  938.     ** the objects in the Q. This limits the recursion level by a
  939.     ** large amount though the stack frames get larger to hold
  940.     ** the GCScanQ's.
  941.     */
  942.     pScanQ->q[pScanQ->queued++] = p;
  943.     if (pScanQ->queued == MAX_SCAN_Q) {
  944.       METER(_pr_scanDepth++);
  945.       ScanScanQ(pScanQ);
  946.     }
  947.   }
  948. }
  949.  
  950. /************************************************************************/
  951.  
  952. /*
  953. ** Empty the freelist for each segment. This is done to make sure that
  954. ** the root finding step works properly (otherwise, if we had a pointer
  955. ** into a free section, we might not find its header word and abort in
  956. ** FindObject)
  957. */
  958. static void EmptyFreelists(void)
  959. {
  960.     GCFreeChunk *cp;
  961.     GCFreeChunk *next;
  962.     GCSeg *sp;
  963.     PRWord *p;
  964.     PRInt32 chunkSize;
  965.     PRInt32 bin;
  966.  
  967.     /*
  968.     ** Run over the freelist and make all of the free chunks look like
  969.     ** object debris.
  970.     */
  971.     for (bin = 0; bin <= NUM_BINS-1; bin++) {
  972.         cp = bins[bin];
  973.         while (cp) {
  974.             next = cp->next;
  975.             sp = cp->segment;
  976.             chunkSize = cp->chunkSize >> BYTES_PER_WORD_LOG2;
  977.             p = (PRWord*) cp;
  978.             PR_ASSERT(chunkSize != 0);
  979.             p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
  980.             SET_HBIT(sp, p);
  981.             cp = next;
  982.         }
  983.         bins[bin] = 0;
  984.     }
  985.     minBin = 31;
  986.     maxBin = 0;
  987. }
  988.  
  989. typedef struct GCBlockEnd {
  990.     PRInt32    check;
  991. #ifdef GC_CHECK
  992.     PRInt32    requestedBytes;
  993. #endif
  994. #ifdef GC_STATS
  995.     PRInt32    bin;
  996.     PRInt64    allocTime; 
  997. #endif
  998. #ifdef GC_TRACEROOTS
  999.     PRInt32    traceGeneration;    
  1000. #endif
  1001. } GCBlockEnd;
  1002.  
  1003. #define PR_BLOCK_END    0xDEADBEEF
  1004.  
  1005. /************************************************************************/
  1006.  
  1007. #ifdef GC_STATS
  1008.  
  1009. typedef struct GCStat {
  1010.     PRInt32    nallocs;
  1011.     double    allocTime;
  1012.     double    allocTimeVariance;
  1013.     PRInt32    nfrees;
  1014.     double    lifetime;
  1015.     double    lifetimeVariance;
  1016. } GCStat;
  1017.  
  1018. #define GCSTAT_BINS    32
  1019.  
  1020. GCStat gcstats[GCSTAT_BINS];
  1021.  
  1022. #define GCLTFREQ_BINS    32
  1023.  
  1024. PRInt32 gcltfreq[GCSTAT_BINS][GCLTFREQ_BINS];
  1025.  
  1026. #include <math.h>
  1027.  
  1028. static char* 
  1029. pr_GetSizeString(PRUint32 size)
  1030. {
  1031.     char* sizeStr;
  1032.     if (size < 1024)
  1033.     sizeStr = PR_smprintf("<= %ld", size);
  1034.     else if (size < 1024 * 1024)
  1035.     sizeStr = PR_smprintf("<= %ldk", size / 1024);
  1036.     else 
  1037.     sizeStr = PR_smprintf("<= %ldM", size / (1024 * 1024));
  1038.     return sizeStr;
  1039. }
  1040.  
  1041. static void
  1042. pr_FreeSizeString(char *sizestr)
  1043. {
  1044.     PR_smprintf_free(sizestr);
  1045. }
  1046.  
  1047.  
  1048. static void
  1049. pr_PrintGCAllocStats(FILE* out)
  1050. {
  1051.     PRInt32 i, j;
  1052.     _PR_DebugPrint(out, "\n--Allocation-Stats-----------------------------------------------------------");
  1053.     _PR_DebugPrint(out, "\n--Obj-Size----Count-----Avg-Alloc-Time-----------Avg-Lifetime---------%%Freed-\n");
  1054.     for (i = 0; i < GCSTAT_BINS; i++) {
  1055.     GCStat stat = gcstats[i];
  1056.     double allocTimeMean = 0.0, allocTimeVariance = 0.0, lifetimeMean = 0.0, lifetimeVariance = 0.0;
  1057.     PRUint32 maxSize = (1 << i);
  1058.     char* sizeStr;
  1059.     if (stat.nallocs != 0.0) {
  1060.         allocTimeMean = stat.allocTime / stat.nallocs;
  1061.         allocTimeVariance = fabs(stat.allocTimeVariance / stat.nallocs - allocTimeMean * allocTimeMean);
  1062.     }
  1063.     if (stat.nfrees != 0.0) {
  1064.         lifetimeMean = stat.lifetime / stat.nfrees;
  1065.         lifetimeVariance = fabs(stat.lifetimeVariance / stat.nfrees - lifetimeMean * lifetimeMean);
  1066.     }
  1067.     sizeStr = pr_GetSizeString(maxSize);
  1068.     _PR_DebugPrint(out, "%10s %8lu %10.3f +- %10.3f %10.3f +- %10.3f (%2ld%%)\n",
  1069.                sizeStr, stat.nallocs,
  1070.                allocTimeMean, sqrt(allocTimeVariance),
  1071.                lifetimeMean, sqrt(lifetimeVariance),
  1072.                (stat.nallocs ? (stat.nfrees * 100 / stat.nallocs) : 0));
  1073.     pr_FreeSizeString(sizeStr);
  1074.     }
  1075.     _PR_DebugPrint(out, "--Lifetime-Frequency-Counts----------------------------------------------------\n");
  1076.     _PR_DebugPrint(out, "size\\cnt");
  1077.     for (j = 0; j < GCLTFREQ_BINS; j++) {
  1078.     _PR_DebugPrint(out, "\t%lu", j);
  1079.     }
  1080.     _PR_DebugPrint(out, "\n");
  1081.     for (i = 0; i < GCSTAT_BINS; i++) {
  1082.     PRInt32* freqs = gcltfreq[i];
  1083.     _PR_DebugPrint(out, "%lu", (1 << i));
  1084.     for (j = 0; j < GCLTFREQ_BINS; j++) {
  1085.         _PR_DebugPrint(out, "\t%lu", freqs[j]);
  1086.     }
  1087.     _PR_DebugPrint(out, "\n");
  1088.     }
  1089.     _PR_DebugPrint(out, "-------------------------------------------------------------------------------\n");
  1090. }
  1091.  
  1092. PR_PUBLIC_API(void)
  1093. PR_PrintGCAllocStats(void)
  1094. {
  1095.     pr_PrintGCAllocStats(stderr);
  1096. }
  1097.  
  1098. #endif /* GC_STATS */
  1099.  
  1100. /************************************************************************/
  1101.  
  1102. /*
  1103. ** Sweep a segment, cleaning up all of the debris. Coallese the debris
  1104. ** into GCFreeChunk's which are added to the freelist bins.
  1105. */
  1106. static PRBool SweepSegment(GCSeg *sp)
  1107. {
  1108.     PRWord h, tix;
  1109.     PRWord *p;
  1110.     PRWord *np;
  1111.     PRWord *limit;
  1112.     GCFreeChunk *cp;
  1113.     PRInt32 bytes, chunkSize, segmentSize, totalFree;
  1114.     CollectorType *ct;
  1115.     PRInt32 bin;
  1116.  
  1117.     /*
  1118.     ** Now scan over the segment's memory in memory order, coallescing
  1119.     ** all of the debris into a FreeChunk list.
  1120.     */
  1121.     totalFree = 0;
  1122.     segmentSize = sp->limit - sp->base;
  1123.     p = (PRWord *) sp->base;
  1124.     limit = (PRWord *) sp->limit;
  1125.     PR_ASSERT(segmentSize > 0);
  1126.     while (p < limit) {
  1127.     chunkSize = 0;
  1128.     cp = (GCFreeChunk *) p;
  1129.  
  1130.     /* Attempt to coallesce any neighboring free objects */
  1131.     for (;;) {
  1132.         PR_ASSERT(IS_HBIT(sp, p) != 0);
  1133.         h = p[0];
  1134.         bytes = OBJ_BYTES(h);
  1135.         PR_ASSERT(bytes != 0);
  1136.         np = (PRWord *) ((char *)p + bytes);
  1137.         tix = (PRWord)GET_TYPEIX(h);
  1138.         if ((h & MARK_BIT) && (tix != FREE_MEMORY_TYPEIX)) {
  1139. #ifdef DEBUG
  1140.         if (tix != FREE_MEMORY_TYPEIX) {
  1141.             PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
  1142.         }
  1143. #endif
  1144.         p[0] = h & ~(MARK_BIT|FINAL_BIT);
  1145.         _GCTRACE(GC_SWEEP, ("busy 0x%x (%d)", p, bytes));
  1146.         break;
  1147.         }
  1148.         _GCTRACE(GC_SWEEP, ("free 0x%x (%d)", p, bytes));
  1149.  
  1150.         /* Found a free object */
  1151. #ifdef GC_STATS
  1152.         {
  1153.         PRInt32 userSize = bytes - sizeof(GCBlockEnd);
  1154.         GCBlockEnd* end = (GCBlockEnd*)((char*)p + userSize);
  1155.         if (userSize >= 0 && end->check == PR_BLOCK_END) {
  1156.             PRInt64 now = PR_Now();
  1157.             double nowd, delta;
  1158.             PRInt32 freq;
  1159.             LL_L2D(nowd, now);
  1160.             delta = nowd - end->allocTime;
  1161.             gcstats[end->bin].nfrees++;
  1162.             gcstats[end->bin].lifetime += delta;
  1163.             gcstats[end->bin].lifetimeVariance += delta * delta;
  1164.  
  1165.             InlineBinNumber(freq, delta);
  1166.             gcltfreq[end->bin][freq]++;
  1167.  
  1168.             end->check = 0;
  1169.         }
  1170.         }
  1171. #endif
  1172.         CLEAR_HBIT(sp, p);
  1173.         ct = &_pr_collectorTypes[tix];
  1174.         if (0 != ct->gctype.free) {
  1175.                 (*ct->gctype.free)(p + 1);
  1176.             }
  1177.         chunkSize = chunkSize + bytes;
  1178.         if (np == limit) {
  1179.         /* Found the end of heap */
  1180.         break;
  1181.         }
  1182.         PR_ASSERT(np < limit);
  1183.         p = np;
  1184.     }
  1185.  
  1186.     if (chunkSize) {
  1187.         _GCTRACE(GC_SWEEP, ("free chunk 0x%p to 0x%p (%d)",
  1188.                    cp, (char*)cp + chunkSize - 1, chunkSize));
  1189.         if (chunkSize < MIN_FREE_CHUNK_BYTES) {
  1190.         /* Lost a tiny fragment until (maybe) next time */
  1191.                 METER(meter.wastedBytes += chunkSize);
  1192.         p = (PRWord *) cp;
  1193.         chunkSize >>= BYTES_PER_WORD_LOG2;
  1194.         PR_ASSERT(chunkSize != 0);
  1195.         p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
  1196.         SET_HBIT(sp, p);
  1197.         } else {
  1198.                 /* See if the chunk constitutes the entire segment */
  1199.                 if (chunkSize == segmentSize) {
  1200.                     /* Free up the segment right now */
  1201.             if (sp->info->fromMalloc) {
  1202.                     ShrinkGCHeap(sp);
  1203.                     return PR_TRUE;
  1204.                 }
  1205.                 }
  1206.  
  1207.                 /* Put free chunk into the appropriate bin */
  1208.                 cp->segment = sp;
  1209.         cp->chunkSize = chunkSize;
  1210.                 InlineBinNumber(bin, chunkSize)
  1211.                 cp->next = bins[bin];
  1212.                 bins[bin] = cp;
  1213.         if (bin < minBin) minBin = bin;
  1214.         if (bin > maxBin) maxBin = bin;
  1215.  
  1216.         /* Zero swept memory now */
  1217.         memset(cp+1, 0, chunkSize - sizeof(*cp));
  1218.                 METER(meter.numFreeChunks++);
  1219.         totalFree += chunkSize;
  1220.         }
  1221.     }
  1222.  
  1223.     /* Advance to next object */
  1224.     p = np;
  1225.     }
  1226.  
  1227.     PR_ASSERT(totalFree <= segmentSize);
  1228.  
  1229.     _pr_gcData.freeMemory += totalFree;
  1230.     _pr_gcData.busyMemory += (sp->limit - sp->base) - totalFree;
  1231.     return PR_FALSE;
  1232. }
  1233.  
  1234. /************************************************************************/
  1235.  
  1236. /* This is a list of all the objects that are finalizable. This is not
  1237.    the list of objects that are awaiting finalization because they
  1238.    have been collected. */
  1239. PRCList _pr_finalizeableObjects;
  1240.  
  1241. /* This is the list of objects that are awaiting finalization because
  1242.    they have been collected. */
  1243. PRCList _pr_finalQueue;
  1244.  
  1245. /* Each object that requires finalization has one of these objects
  1246.    allocated as well. The GCFinal objects are put on the
  1247.    _pr_finalizeableObjects list until the object is collected at which
  1248.    point the GCFinal object is moved to the _pr_finalQueue */
  1249. typedef struct GCFinalStr {
  1250.     PRCList links;
  1251.     PRWord *object;
  1252. } GCFinal;
  1253.  
  1254. /* Find pointer to GCFinal struct from the list linkaged embedded in it */
  1255. #define FinalPtr(_qp) \
  1256.     ((GCFinal*) ((char*) (_qp) - offsetof(GCFinal,links)))
  1257.  
  1258. static GCFinal *AllocFinalNode(void)
  1259. {
  1260.     return PR_NEWZAP(GCFinal);
  1261. }
  1262.  
  1263. static void FreeFinalNode(GCFinal *node)
  1264. {
  1265.     PR_DELETE(node);
  1266. }
  1267.  
  1268. /*
  1269. ** Prepare for finalization. At this point in the GC cycle we have
  1270. ** identified all of the live objects. For each object on the
  1271. ** _pr_finalizeableObjects list see if the object is alive or dead. If
  1272. ** it's dead, resurrect it and move it from the _pr_finalizeableObjects
  1273. ** list to the _pr_finalQueue (object's only get finalized once).
  1274. **
  1275. ** Once _pr_finalizeableObjects has been processed we can finish the
  1276. ** GC and free up memory and release the threading lock. After that we
  1277. ** can invoke the finalization procs for each object that is on the
  1278. ** _pr_finalQueue.
  1279. */
  1280. static void PrepareFinalize(void)
  1281. {
  1282.     PRCList *qp;
  1283.     GCFinal *fp;
  1284.     PRWord h;
  1285.     PRWord *p;
  1286.     void (PR_CALLBACK *livePointer)(void *ptr);
  1287. #ifdef DEBUG
  1288.     CollectorType *ct;
  1289. #endif
  1290.  
  1291.     /* This must be done under the same lock that the finalizer uses */
  1292.     PR_ASSERT( GC_IS_LOCKED() );
  1293.  
  1294.     /* cache this ptr */
  1295.     livePointer = _pr_gcData.livePointer;
  1296.  
  1297.     /*
  1298.      * Pass #1: Identify objects that are to be finalized, set their
  1299.      * FINAL_BIT.
  1300.      */
  1301.     qp = _pr_finalizeableObjects.next;
  1302.     while (qp != &_pr_finalizeableObjects) {
  1303.     fp = FinalPtr(qp);
  1304.     qp = qp->next;
  1305.     h = fp->object[0];        /* Grab header word */
  1306.     if (h & MARK_BIT) {
  1307.         /* Object is already alive */
  1308.         continue;
  1309.     }
  1310.  
  1311. #ifdef DEBUG
  1312.     ct = &_pr_collectorTypes[GET_TYPEIX(h)];
  1313.     PR_ASSERT((0 != ct->flags) && (0 != ct->gctype.finalize));
  1314. #endif
  1315.     fp->object[0] |= FINAL_BIT;
  1316.     _GCTRACE(GC_FINAL, ("moving %p (%d) to finalQueue",
  1317.                fp->object, OBJ_BYTES(h)));
  1318.     }
  1319.  
  1320.     /*
  1321.      * Pass #2: For each object that is going to be finalized, move it to
  1322.      * the finalization queue and resurrect it
  1323.      */
  1324.     qp = _pr_finalizeableObjects.next;
  1325.     while (qp != &_pr_finalizeableObjects) {
  1326.     fp = FinalPtr(qp);
  1327.     qp = qp->next;
  1328.     h = fp->object[0];        /* Grab header word */
  1329.     if ((h & FINAL_BIT) == 0) {
  1330.         continue;
  1331.     }
  1332.  
  1333.     /* Resurrect the object and any objects it refers to */
  1334.         p = &fp->object[1];
  1335.     (*livePointer)(p);
  1336.     PR_REMOVE_LINK(&fp->links);
  1337.     PR_APPEND_LINK(&fp->links, &_pr_finalQueue);
  1338.     }
  1339. }
  1340.  
  1341. /*
  1342. ** Scan the finalQ, marking each and every object on it live.  This is
  1343. ** necessary because we might do a GC before objects that are on the
  1344. ** final queue get finalized. Since there are no other references
  1345. ** (otherwise they would be on the final queue), we have to scan them.
  1346. ** This really only does work if we call the GC before the finalizer
  1347. ** has a chance to do its job.
  1348. */
  1349. extern void PR_CALLBACK _PR_ScanFinalQueue(void *notused)
  1350. {
  1351. #ifdef XP_MAC
  1352. #pragma unused (notused)
  1353. #endif
  1354.     PRCList *qp;
  1355.     GCFinal *fp;
  1356.     PRWord *p;
  1357.     void ( PR_CALLBACK *livePointer)(void *ptr);
  1358.  
  1359.     livePointer = _pr_gcData.livePointer;
  1360.     qp = _pr_finalQueue.next;
  1361.     while (qp != &_pr_finalQueue) {
  1362.     fp = FinalPtr(qp);
  1363.     _GCTRACE(GC_FINAL, ("marking 0x%x (on final queue)", fp->object));
  1364.         p = &fp->object[1];
  1365.     (*livePointer)(p);
  1366.     qp = qp->next;
  1367.     }
  1368. }
  1369.  
  1370. void PR_CALLBACK FinalizerLoop(void* unused)
  1371. {
  1372. #ifdef XP_MAC
  1373. #pragma unused (unused)
  1374. #endif
  1375.     GCFinal *fp;
  1376.     PRWord *p;
  1377.     PRWord h, tix;
  1378.     CollectorType *ct;
  1379.  
  1380.     LOCK_GC();
  1381.     for (;;) {
  1382.     p = 0; h = 0;        /* don't let the gc find these pointers */
  1383.     while (PR_CLIST_IS_EMPTY(&_pr_finalQueue))
  1384.         PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
  1385.  
  1386.     _GCTRACE(GC_FINAL, ("begin finalization"));
  1387.     while (_pr_finalQueue.next != &_pr_finalQueue) {
  1388.         fp = FinalPtr(_pr_finalQueue.next);
  1389.         PR_REMOVE_LINK(&fp->links);
  1390.         p = fp->object;
  1391.  
  1392.         h = p[0];        /* Grab header word */
  1393.         tix = (PRWord)GET_TYPEIX(h);
  1394.         ct = &_pr_collectorTypes[tix];
  1395.         _GCTRACE(GC_FINAL, ("finalize 0x%x (%d)", p, OBJ_BYTES(h)));
  1396.  
  1397.         /*
  1398.         ** Give up the GC lock so that other threads can allocate memory
  1399.         ** while this finalization method is running. Get it back
  1400.         ** afterwards so that the list remains thread safe.
  1401.         */
  1402.         UNLOCK_GC();
  1403.         FreeFinalNode(fp);
  1404.         PR_ASSERT(ct->gctype.finalize != 0);
  1405.         (*ct->gctype.finalize)(p + 1);
  1406.         LOCK_GC();
  1407.     }
  1408.     _GCTRACE(GC_FINAL, ("end finalization"));
  1409.     PR_Notify(_pr_gcData.lock);
  1410.     }
  1411. }
  1412.  
  1413. static void NotifyFinalizer(void)
  1414. {
  1415.     if (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
  1416.     PR_ASSERT( GC_IS_LOCKED() );
  1417.     PR_Notify(_pr_gcData.lock);
  1418.     }
  1419. }
  1420.  
  1421. void _PR_CreateFinalizer(PRThreadScope scope)
  1422. {
  1423.     if (!_pr_gcData.finalizer) {
  1424.     _pr_gcData.finalizer = PR_CreateThreadGCAble(PR_SYSTEM_THREAD,
  1425.                                         FinalizerLoop, 0,
  1426.                                         PR_PRIORITY_LOW, scope,
  1427.                                         PR_UNJOINABLE_THREAD, 0);
  1428.     
  1429.     if (_pr_gcData.finalizer == NULL)
  1430.         /* We are doomed if we can't start the finalizer */
  1431.         PR_Abort();
  1432.  
  1433.     }
  1434. }
  1435.  
  1436. void pr_FinalizeOnExit(void)
  1437. {
  1438. #ifdef DEBUG_warren
  1439.     OutputDebugString("### Doing finalize-on-exit pass\n");
  1440. #endif
  1441.     PR_ForceFinalize();
  1442. #ifdef DEBUG_warren
  1443.     OutputDebugString("### Finalize-on-exit complete. Dumping object left to memory.out\n");
  1444.     PR_DumpMemorySummary();
  1445.     PR_DumpMemory(PR_TRUE);
  1446. #endif
  1447. }
  1448.  
  1449. PR_IMPLEMENT(void) PR_ForceFinalize()
  1450. {
  1451.     LOCK_GC();
  1452.     NotifyFinalizer();
  1453.     while (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
  1454.     PR_ASSERT( GC_IS_LOCKED() );
  1455.     (void) PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
  1456.     }
  1457.     UNLOCK_GC();
  1458.  
  1459.     /* XXX I don't know how to make it wait (yet) */
  1460. }
  1461.  
  1462. /************************************************************************/
  1463.  
  1464. typedef struct GCWeakStr {
  1465.     PRCList links;
  1466.     PRWord *object;
  1467. } GCWeak;
  1468.  
  1469. /*
  1470. ** Find pointer to GCWeak struct from the list linkaged embedded in it
  1471. */
  1472. #define WeakPtr(_qp) \
  1473.     ((GCWeak*) ((char*) (_qp) - offsetof(GCWeak,links)))
  1474.  
  1475. PRCList _pr_weakLinks = PR_INIT_STATIC_CLIST(&_pr_weakLinks);
  1476. PRCList _pr_freeWeakLinks = PR_INIT_STATIC_CLIST(&_pr_freeWeakLinks);
  1477.  
  1478. #define WEAK_FREELIST_ISEMPTY() (_pr_freeWeakLinks.next == &_pr_freeWeakLinks)
  1479.  
  1480. /*
  1481.  * Keep objects referred to by weak free list alive until they can be
  1482.  * freed
  1483.  */
  1484. static void PR_CALLBACK ScanWeakFreeList(void *notused) {
  1485. #ifdef XP_MAC
  1486. #pragma unused (notused)
  1487. #endif
  1488.     PRCList *qp = _pr_freeWeakLinks.next;
  1489.     while (qp != &_pr_freeWeakLinks) {
  1490.     GCWeak *wp = WeakPtr(qp);
  1491.     qp = qp->next;
  1492.     ProcessRootPointer(wp->object);
  1493.     }
  1494. }
  1495.  
  1496. /*
  1497.  * Empty the list of weak objects. Note that we can't call malloc/free
  1498.  * under the cover of the GC's lock (we might deadlock), so transfer the
  1499.  * list of free objects to a local list under the cover of the lock, then
  1500.  * release the lock and free up the memory.
  1501.  */
  1502. static void EmptyWeakFreeList(void) {
  1503.     if (!WEAK_FREELIST_ISEMPTY()) {
  1504.     PRCList *qp, freeLinks;
  1505.  
  1506.     PR_INIT_CLIST(&freeLinks);
  1507.  
  1508.     /*
  1509.      * Transfer list of free weak links from the global list to a
  1510.      * local list.
  1511.      */
  1512.     LOCK_GC();
  1513.     qp = _pr_freeWeakLinks.next;
  1514.     while (qp != &_pr_freeWeakLinks) {
  1515.         GCWeak *wp = WeakPtr(qp);
  1516.         qp = qp->next;
  1517.         PR_REMOVE_LINK(&wp->links);
  1518.         PR_APPEND_LINK(&wp->links, &freeLinks);
  1519.     }
  1520.     UNLOCK_GC();
  1521.  
  1522.     /* Free up storage now */
  1523.     qp = freeLinks.next;
  1524.     while (qp != &freeLinks) {
  1525.         GCWeak *wp = WeakPtr(qp);
  1526.         qp = qp->next;
  1527.         PR_DELETE(wp);
  1528.     }
  1529.     }
  1530. }
  1531.  
  1532. /*
  1533.  * Allocate a new weak node in the weak objects list
  1534.  */
  1535. static GCWeak *AllocWeakNode(void)
  1536. {
  1537.     EmptyWeakFreeList();
  1538.     return PR_NEWZAP(GCWeak);
  1539. }
  1540.  
  1541. static void FreeWeakNode(GCWeak *node)
  1542. {
  1543.     PR_DELETE(node);
  1544. }
  1545.  
  1546. /*
  1547.  * Check the weak links for validity. Note that the list of weak links is
  1548.  * itself weak (otherwise we would keep the objects with weak links in
  1549.  * them alive forever). As we scan the list check the weak link object
  1550.  * itself and if it's not marked then remove it from the weak link list
  1551.  */
  1552. static void CheckWeakLinks(void) {
  1553.     PRCList *qp;
  1554.     GCWeak *wp;
  1555.     PRWord *p, h, tix, **weakPtrAddress;
  1556.     CollectorType *ct;
  1557.     PRUint32 offset;
  1558.  
  1559.     qp = _pr_weakLinks.next;
  1560.     while (qp != &_pr_weakLinks) {
  1561.     wp = WeakPtr(qp);
  1562.     qp = qp->next;
  1563.     if ((p = wp->object) != 0) {
  1564.         h = p[0];        /* Grab header word */
  1565.         if ((h & MARK_BIT) == 0) {
  1566.         /*
  1567.          * The object that has a weak link is no longer being
  1568.          * referenced; remove it from the chain and let it get
  1569.          * swept away by the GC. Transfer it to the list of
  1570.          * free weak links for later freeing.
  1571.          */
  1572.         PR_REMOVE_LINK(&wp->links);
  1573.         PR_APPEND_LINK(&wp->links, &_pr_freeWeakLinks);
  1574.         collectorCleanupNeeded = 1;
  1575.         continue;
  1576.         }
  1577.         
  1578.         /* Examine a live object that contains weak links */
  1579.         tix = GET_TYPEIX(h);
  1580.         ct = &_pr_collectorTypes[tix];
  1581.         PR_ASSERT((ct->flags != 0) && (ct->gctype.getWeakLinkOffset != 0));
  1582.         if (0 == ct->gctype.getWeakLinkOffset) {
  1583.         /* Heap is probably corrupted */
  1584.         continue;
  1585.         }
  1586.  
  1587.         /* Get offset into the object of where the weak pointer is */
  1588.         offset = (*ct->gctype.getWeakLinkOffset)(p + 1);
  1589.  
  1590.         /* Check the weak pointer */
  1591.         weakPtrAddress = (PRWord**)((char*)(p + 1) + offset);
  1592.         p = *weakPtrAddress;
  1593.         if (p != 0) {
  1594.         h = p[-1];    /* Grab header word for pointed to object */
  1595.         if (h & MARK_BIT) {
  1596.             /* Object can't be dead */
  1597.             continue;
  1598.         }
  1599.         /* Break weak link to an object that is about to be swept */
  1600.         *weakPtrAddress = 0;
  1601.         }
  1602.     }
  1603.     }
  1604. }
  1605.  
  1606. /************************************************************************/
  1607.  
  1608. /*
  1609. ** Perform a complete garbage collection
  1610. */
  1611.  
  1612. extern GCLockHook *_pr_GCLockHook;
  1613.  
  1614. static void dogc(void)
  1615. {
  1616.     RootFinder *rf;
  1617.     GCLockHook* lhook;
  1618.  
  1619.     GCScanQ scanQ;
  1620.     GCSeg *sp, *esp;
  1621.     PRInt64 start, end, diff;
  1622.  
  1623. #if defined(GCMETER) || defined(GCTIMINGHOOK)
  1624.     start = PR_Now();
  1625. #endif
  1626.  
  1627.     /*
  1628.     ** Stop all of the other threads. This also promises to capture the
  1629.     ** register state of each and every thread
  1630.     */
  1631.  
  1632.     /* 
  1633.     ** Get all the locks that will be need during GC after SuspendAll. We 
  1634.     ** cannot make any locking/library calls after SuspendAll.
  1635.     */
  1636.     if (_pr_GCLockHook) {
  1637.         for (lhook = _pr_GCLockHook->next; lhook != _pr_GCLockHook; 
  1638.           lhook = lhook->next) {
  1639.           (*lhook->func)(PR_GCBEGIN, lhook->arg);
  1640.         }
  1641.     }
  1642.  
  1643.     PR_SuspendAll();
  1644.  
  1645. #ifdef GCMETER
  1646.     /* Reset meter info */
  1647.     if (_pr_gcMeter & _GC_METER_STATS) {
  1648.         fprintf(stderr,
  1649.                 "[GCSTATS: busy:%d skipped:%d, alloced:%d+wasted:%d+free:%d = total:%d]\n",
  1650.                 _pr_gcData.busyMemory,
  1651.         meter.skippedFreeChunks,
  1652.                 meter.allocBytes, meter.wastedBytes, _pr_gcData.freeMemory,
  1653.                 _pr_gcData.allocMemory);
  1654.     }        
  1655.     memset(&meter, 0, sizeof(meter));
  1656. #endif
  1657.  
  1658.     PR_LOG(_pr_msgc_lm, PR_LOG_ALWAYS, ("begin mark phase; busy=%d free=%d total=%d",
  1659.                      _pr_gcData.busyMemory, _pr_gcData.freeMemory,
  1660.                      _pr_gcData.allocMemory));
  1661.  
  1662.     if (_pr_beginGCHook) {
  1663.     (*_pr_beginGCHook)(_pr_beginGCHookArg);
  1664.     }
  1665.  
  1666.     /*
  1667.     ** Initialize scanQ to all zero's so that root finder doesn't walk
  1668.     ** over it...
  1669.     */
  1670.     memset(&scanQ, 0, sizeof(scanQ));
  1671.     pScanQ = &scanQ;
  1672.  
  1673.     /******************************************/
  1674.     /* MARK PHASE */
  1675.  
  1676.     EmptyFreelists();
  1677.  
  1678.     /* Find root's */
  1679.     PR_LOG(_pr_msgc_lm, PR_LOG_WARNING,
  1680.            ("begin mark phase; busy=%d free=%d total=%d",
  1681.         _pr_gcData.busyMemory, _pr_gcData.freeMemory,
  1682.             _pr_gcData.allocMemory));
  1683.     METER(_pr_scanDepth = 0);
  1684.     rf = _pr_rootFinders;
  1685.     while (rf) {
  1686.     _GCTRACE(GC_ROOTS, ("finding roots in %s", rf->name));
  1687.     (*rf->func)(rf->arg);
  1688.     rf = rf->next;
  1689.     }
  1690.     _GCTRACE(GC_ROOTS, ("done finding roots"));
  1691.  
  1692.     /* Scan remaining object's that need scanning */
  1693.     ScanScanQ(&scanQ);
  1694.     PR_ASSERT(pScanQ == &scanQ);
  1695.     PR_ASSERT(scanQ.queued == 0);
  1696.     METER({
  1697.     if (_pr_scanDepth > _pr_maxScanDepth) {
  1698.         _pr_maxScanDepth = _pr_scanDepth;
  1699.     }
  1700.     });
  1701.  
  1702.     /******************************************/
  1703.     /* FINALIZATION PHASE */
  1704.  
  1705.     METER(_pr_scanDepth = 0);
  1706.     PrepareFinalize();
  1707.  
  1708.     /* Scan any resurrected objects found during finalization */
  1709.     ScanScanQ(&scanQ);
  1710.     PR_ASSERT(pScanQ == &scanQ);
  1711.     PR_ASSERT(scanQ.queued == 0);
  1712.     METER({
  1713.     if (_pr_scanDepth > _pr_maxScanDepth) {
  1714.         _pr_maxScanDepth = _pr_scanDepth;
  1715.     }
  1716.     });
  1717.     pScanQ = 0;
  1718.  
  1719.     /******************************************/
  1720.     /* SWEEP PHASE */
  1721.  
  1722.     /*
  1723.     ** Sweep each segment clean. While we are at it, figure out which
  1724.     ** segment has the most free space and make that the current segment.
  1725.     */
  1726.     CheckWeakLinks();
  1727.     _GCTRACE(GC_SWEEP, ("begin sweep phase"));
  1728.     _pr_gcData.freeMemory = 0;
  1729.     _pr_gcData.busyMemory = 0;
  1730.     sp = segs;
  1731.     esp = sp + nsegs;
  1732.     while (sp < esp) {
  1733.         if (SweepSegment(sp)) {
  1734.             /*
  1735.             ** Segment is now free and has been replaced with a different
  1736.             ** segment object.
  1737.             */
  1738.             esp--;
  1739.             continue;
  1740.         }
  1741.         sp++;
  1742.     }
  1743.  
  1744. #if defined(GCMETER) || defined(GCTIMINGHOOK)
  1745.     end = PR_Now();
  1746. #endif
  1747. #ifdef GCMETER
  1748.     LL_SUB(diff, end, start);
  1749.     PR_LOG(GC, PR_LOG_ALWAYS,
  1750.        ("done; busy=%d free=%d chunks=%d total=%d time=%lldms",
  1751.         _pr_gcData.busyMemory, _pr_gcData.freeMemory,
  1752.         meter.numFreeChunks, _pr_gcData.allocMemory, diff));
  1753.     if (_pr_gcMeter & _GC_METER_FREE_LIST) {
  1754.         PRInt32 bin;
  1755.         fprintf(stderr, "Freelist bins:\n");
  1756.         for (bin = 0; bin < NUM_BINS; bin++) {
  1757.             GCFreeChunk *cp = bins[bin];
  1758.             while (cp != NULL) {
  1759.                 fprintf(stderr, "%3d: %p %8d\n", bin, cp, cp->chunkSize);
  1760.                 cp = cp->next;
  1761.             }
  1762.         }
  1763.     }
  1764. #endif
  1765.  
  1766.     if (_pr_endGCHook) {
  1767.     (*_pr_endGCHook)(_pr_endGCHookArg);
  1768.     }
  1769.  
  1770.     /* clear the running total of the bytes allocated via BigAlloc() */
  1771.     bigAllocBytes = 0;
  1772.  
  1773.     /* And resume multi-threading */
  1774.     PR_ResumeAll();
  1775.  
  1776.     if (_pr_GCLockHook) {
  1777.         for (lhook = _pr_GCLockHook->prev; lhook != _pr_GCLockHook; 
  1778.           lhook = lhook->prev) {
  1779.           (*lhook->func)(PR_GCEND, lhook->arg);
  1780.         }
  1781.     }
  1782.  
  1783.     /* Kick finalizer */
  1784.     NotifyFinalizer();
  1785. #ifdef GCTIMINGHOOK
  1786.     if (_pr_gcData.gcTimingHook) {
  1787.     PRInt32 time;
  1788.     LL_SUB(diff, end, start);
  1789.     LL_L2I(time, diff);
  1790.     _pr_gcData.gcTimingHook(time);
  1791.     }
  1792. #endif
  1793. }
  1794.  
  1795. PR_IMPLEMENT(void) PR_GC(void)
  1796. {
  1797.     LOCK_GC();
  1798.     dogc();
  1799.     UNLOCK_GC();
  1800.  
  1801.     EmptyWeakFreeList();
  1802. }
  1803.  
  1804. /*******************************************************************************
  1805.  * Heap Walker
  1806.  ******************************************************************************/
  1807.  
  1808. /*
  1809. ** This is yet another disgusting copy of the body of ProcessRootPointer
  1810. ** (the other being ProcessRootBlock), but we're not leveraging a single
  1811. ** function in their cases in interest of performance (avoiding the function
  1812. ** call).
  1813. */
  1814. static PRInt32 PR_CALLBACK
  1815. pr_ConservativeWalkPointer(void* ptr, PRWalkFun walkRootPointer, void* data)
  1816. {
  1817.   PRWord *p0, *p, *segBase;
  1818.   GCSeg* sp;
  1819.  
  1820.   p0 = (PRWord*) ptr;
  1821.  
  1822.   /*
  1823.   ** XXX:  
  1824.   ** Until Win16 maintains lowSeg and highSeg correctly,
  1825.   ** (ie. lowSeg=MIN(all segs) and highSeg = MAX(all segs))
  1826.   ** Allways scan through the segment list
  1827.   */
  1828. #if !defined(WIN16)
  1829.   if (p0 < _pr_gcData.lowSeg) return 0;                  /* below gc heap */
  1830.   if (p0 >= _pr_gcData.highSeg) return 0;                /* above gc heap */
  1831. #endif
  1832.  
  1833.   /* NOTE: inline expansion of InHeap */
  1834.   /* Find segment */
  1835.   sp = lastInHeap;
  1836.   if (!sp || !IN_SEGMENT(sp,p0)) {
  1837.     GCSeg *esp;
  1838.     sp = segs;
  1839.     esp = segs + nsegs;
  1840.     for (; sp < esp; sp++) {
  1841.       if (IN_SEGMENT(sp, p0)) {
  1842.     lastInHeap = sp;
  1843.     goto find_object;
  1844.       }
  1845.     }
  1846.     return 0;
  1847.   }
  1848.  
  1849.   find_object:
  1850.     /* NOTE: Inline expansion of FindObject */
  1851.     /* Align p to it's proper boundary before we start fiddling with it */
  1852.     p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
  1853.     segBase = (PRWord *) sp->base;
  1854.     do {
  1855.         if (IS_HBIT(sp, p)) {
  1856.             goto winner;
  1857.         }
  1858.         p--;
  1859.     } while (p >= segBase);
  1860.  
  1861.     /*
  1862.     ** We have a pointer into the heap, but it has no header
  1863.     ** bit. This means that somehow the very first object in the heap
  1864.     ** doesn't have a header. This is impossible so when debugging
  1865.     ** lets abort.
  1866.     */
  1867. #ifdef DEBUG
  1868.     PR_Abort();
  1869. #endif
  1870.     return 0;
  1871.  
  1872.  winner:
  1873.     return walkRootPointer(p, data);
  1874. }
  1875.  
  1876. static int32 PR_CALLBACK
  1877. pr_ConservativeWalkBlock(void **base, PRInt32 count,
  1878.              PRWalkFun walkRootPointer, void* data)
  1879. {
  1880.     PRWord *p0;
  1881.     while (--count >= 0) {
  1882.     PRInt32 status;
  1883.         p0 = (PRWord*) *base++;
  1884.     status = pr_ConservativeWalkPointer(p0, walkRootPointer, data);
  1885.     if (status) return status;
  1886.     }
  1887.     return 0;
  1888. }
  1889.  
  1890. /******************************************************************************/
  1891.  
  1892. typedef void (*WalkObject_t)(FILE *out, GCType* tp, PRWord *obj,
  1893.                  size_t bytes, PRBool detailed);
  1894. typedef void (*WalkUnknown_t)(FILE *out, GCType* tp, PRWord tix, PRWord *p,
  1895.                   size_t bytes, PRBool detailed);
  1896. typedef void (*WalkFree_t)(FILE *out, PRWord *p, size_t size, PRBool detailed);
  1897. typedef void (*WalkSegment_t)(FILE *out, GCSeg* sp, PRBool detailed);
  1898.  
  1899. static void
  1900. pr_WalkSegment(FILE* out, GCSeg* sp, PRBool detailed,
  1901.            char* enterMsg, char* exitMsg,
  1902.            WalkObject_t walkObject, WalkUnknown_t walkUnknown, WalkFree_t walkFree)
  1903. {
  1904.     PRWord *p, *limit;
  1905.  
  1906.     p = (PRWord *) sp->base;
  1907.     limit = (PRWord *) sp->limit;
  1908.     if (enterMsg)
  1909.     fprintf(out, enterMsg, p);
  1910.     while (p < limit)
  1911.     {
  1912.     if (IS_HBIT(sp, p)) /* Is this an object header? */
  1913.     {
  1914.         PRWord h = p[0];
  1915.         PRWord tix = GET_TYPEIX(h);
  1916.         size_t bytes = OBJ_BYTES(h);
  1917.         PRWord* np = (PRWord*) ((char*)p + bytes);
  1918.  
  1919.         GCType* tp = &_pr_collectorTypes[tix].gctype;
  1920.         if ((0 != tp) && walkObject)
  1921.         walkObject(out, tp, p, bytes, detailed);
  1922.         else if (walkUnknown)
  1923.         walkUnknown(out, tp, tix, p, bytes, detailed);
  1924.         p = np;
  1925.     }
  1926.     else
  1927.     {
  1928.         /* Must be a freelist item */
  1929.         size_t size = ((GCFreeChunk*)p)->chunkSize;
  1930.         if (walkFree)
  1931.         walkFree(out, p, size, detailed);
  1932.         p = (PRWord*)((char*)p + size);
  1933.     }
  1934.     }
  1935.     if (p != limit)
  1936.     fprintf(out, "SEGMENT OVERRUN (end should be at 0x%p)\n", limit);
  1937.     if (exitMsg)
  1938.     fprintf(out, exitMsg, p);
  1939. }
  1940.  
  1941. static void
  1942. pr_WalkSegments(FILE *out, WalkSegment_t walkSegment, PRBool detailed)
  1943. {
  1944.     GCSeg *sp = segs;
  1945.     GCSeg *esp;
  1946.  
  1947.     LOCK_GC();
  1948.     esp = sp + nsegs;
  1949.     while (sp < esp)
  1950.     {
  1951.     walkSegment(out, sp, detailed);
  1952.     sp++;
  1953.     }
  1954.     fprintf(out, "End of heap\n");
  1955.     UNLOCK_GC();
  1956. }
  1957.  
  1958. /*******************************************************************************
  1959.  * Heap Dumper
  1960.  ******************************************************************************/
  1961.  
  1962. PR_IMPLEMENT(void)
  1963. PR_DumpIndent(FILE *out, int indent)
  1964. {
  1965.     while (--indent >= 0)
  1966.     fprintf(out, " ");
  1967. }
  1968.  
  1969. static void
  1970. PR_DumpHexWords(FILE *out, PRWord *p, int nWords,
  1971.         int indent, int nWordsPerLine)
  1972. {
  1973.     while (nWords > 0)
  1974.     {
  1975.     int i;
  1976.  
  1977.     PR_DumpIndent(out, indent);
  1978.     i = nWordsPerLine;
  1979.     if (i > nWords)
  1980.         i = nWords;
  1981.     nWords -= i;
  1982.     while (i--)
  1983.     {
  1984.         fprintf(out, "0x%.8X", *p++);
  1985.         if (i)
  1986.         fputc(' ', out);
  1987.     }
  1988.     fputc('\n', out);
  1989.     }
  1990. }
  1991.  
  1992. static void PR_CALLBACK
  1993. pr_DumpObject(FILE *out, GCType* tp, PRWord *p, 
  1994.           size_t bytes, PRBool detailed)
  1995. {
  1996.     char kindChar = tp->kindChar;
  1997.     fprintf(out, "0x%p: 0x%.6X %c  ", p, bytes, kindChar ? kindChar : '?');
  1998.     if (tp->dump)
  1999.     (*tp->dump)(out, (void*) (p + 1), detailed, 0);
  2000.     if (detailed)
  2001.     PR_DumpHexWords(out, p, bytes>>2, 22, 4);
  2002. }
  2003.     
  2004. static void PR_CALLBACK
  2005. pr_DumpUnknown(FILE *out, GCType* tp, PRWord tix, PRWord *p, 
  2006.            size_t bytes, PRBool detailed)
  2007. {
  2008.     char kindChar = tp->kindChar;
  2009.     fprintf(out, "0x%p: 0x%.6X %c  ", p, bytes, kindChar ? kindChar : '?');
  2010.     fprintf(out, "UNKNOWN KIND %d\n", tix);
  2011.     if (detailed)
  2012.     PR_DumpHexWords(out, p, bytes>>2, 22, 4);
  2013. }
  2014.  
  2015. static void PR_CALLBACK
  2016. pr_DumpFree(FILE *out, PRWord *p, size_t size, PRBool detailed)
  2017. {
  2018. #if defined(XP_MAC) && XP_MAC
  2019. # pragma unused( detailed )
  2020. #endif
  2021.  
  2022.     fprintf(out, "0x%p: 0x%.6X -  FREE\n", p, size);
  2023. }
  2024.  
  2025. static void PR_CALLBACK
  2026. pr_DumpSegment(FILE* out, GCSeg* sp, PRBool detailed)
  2027. {
  2028.     pr_WalkSegment(out, sp, detailed,
  2029.            "\n   Address: Length\n0x%p: Beginning of segment\n",
  2030.            "0x%p: End of segment\n\n",
  2031.            pr_DumpObject, pr_DumpUnknown, pr_DumpFree);
  2032. }
  2033.  
  2034. static void pr_DumpRoots(FILE *out);
  2035.  
  2036. /*
  2037. ** Dump out the GC heap.
  2038. */
  2039. PR_IMPLEMENT(void)
  2040. PR_DumpGCHeap(FILE *out, PRBool detailed)
  2041. {
  2042.     fprintf(out, "\n"
  2043.         "The kinds are:\n"
  2044.         " U unscanned block\n"
  2045.         " W weak link block\n"
  2046.         " S scanned block\n"
  2047.         " F scanned and final block\n"
  2048.         " C class record\n"
  2049.         " X context record\n"
  2050.         " - free list item\n"
  2051.         " ? other\n");
  2052.     LOCK_GC();
  2053.     pr_WalkSegments(out, pr_DumpSegment, detailed);
  2054.     if (detailed)
  2055.     pr_DumpRoots(out);
  2056.     UNLOCK_GC();
  2057. }
  2058.  
  2059. PR_IMPLEMENT(void)
  2060. PR_DumpMemory(PRBool detailed)
  2061. {
  2062.     PR_DumpToFile("memory.out", "Dumping memory", PR_DumpGCHeap, detailed);
  2063. }
  2064.  
  2065. /******************************************************************************/
  2066.  
  2067. static int32 PR_CALLBACK
  2068. pr_DumpRootPointer(PRWord* p, void* data)
  2069. {
  2070. #ifdef XP_MAC
  2071. #pragma unused(data)
  2072. #endif
  2073.     PRWord h = p[0];
  2074.     PRWord tix = GET_TYPEIX(h);
  2075.       size_t bytes = OBJ_BYTES(h);
  2076.       
  2077.       GCType* tp = &_pr_collectorTypes[tix].gctype;
  2078.       if (0 != tp)
  2079.       pr_DumpObject(_pr_gcData.dumpOutput, tp, p, bytes, PR_FALSE);
  2080.       else
  2081.       pr_DumpUnknown(_pr_gcData.dumpOutput, tp, tix, p, bytes, PR_FALSE);
  2082.     return 0;
  2083. }
  2084.  
  2085. static void PR_CALLBACK
  2086. pr_ConservativeDumpRootPointer(void* ptr)
  2087. {
  2088.     (void)pr_ConservativeWalkPointer(ptr, (PRWalkFun) pr_DumpRootPointer, NULL);
  2089. }
  2090.  
  2091. static void PR_CALLBACK
  2092. pr_ConservativeDumpRootBlock(void **base, PRInt32 count)
  2093. {
  2094.     (void)pr_ConservativeWalkBlock(base, count, (PRWalkFun) pr_DumpRootPointer, NULL);
  2095. }
  2096.  
  2097. extern int
  2098. DumpThreadRoots(PRThread *t, int i, void *notused);
  2099.  
  2100. static void
  2101. pr_DumpRoots(FILE *out)
  2102. {
  2103.     RootFinder *rf;
  2104.     void (*liveBlock)(void **base, PRInt32 count);
  2105.     void (*livePointer)(void *ptr);
  2106.     void (*processRootBlock)(void **base, PRInt32 count);
  2107.     void (*processRootPointer)(void *ptr);
  2108.  
  2109.     LOCK_GC();
  2110.  
  2111.     liveBlock = _pr_gcData.liveBlock;
  2112.     livePointer = _pr_gcData.livePointer;
  2113.     processRootBlock = _pr_gcData.processRootBlock;
  2114.     processRootPointer = _pr_gcData.processRootPointer;
  2115.     
  2116.     _pr_gcData.liveBlock = pr_ConservativeDumpRootBlock;
  2117.     _pr_gcData.livePointer = pr_ConservativeDumpRootPointer;
  2118.     _pr_gcData.processRootBlock = pr_ConservativeDumpRootBlock;
  2119.     _pr_gcData.processRootPointer = pr_ConservativeDumpRootPointer;
  2120.     _pr_gcData.dumpOutput = out;
  2121.  
  2122.     rf = _pr_rootFinders;
  2123.     while (rf) {
  2124.     fprintf(out, "\n===== Roots for %s\n", rf->name);
  2125.     (*rf->func)(rf->arg);
  2126.     rf = rf->next;
  2127.     }
  2128.  
  2129.     _pr_gcData.liveBlock = liveBlock;
  2130.     _pr_gcData.livePointer = livePointer;
  2131.     _pr_gcData.processRootBlock = processRootBlock;
  2132.     _pr_gcData.processRootPointer = processRootPointer;
  2133.     _pr_gcData.dumpOutput = NULL;
  2134.  
  2135.     UNLOCK_GC();
  2136. }
  2137.  
  2138. /*******************************************************************************
  2139.  * Heap Summary Dumper
  2140.  ******************************************************************************/
  2141.  
  2142. PRSummaryPrinter summaryPrinter = NULL;
  2143. void* summaryPrinterClosure = NULL;
  2144.  
  2145. PR_IMPLEMENT(void) 
  2146. PR_RegisterSummaryPrinter(PRSummaryPrinter fun, void* closure)
  2147. {
  2148.     summaryPrinter = fun;
  2149.     summaryPrinterClosure = closure;
  2150. }
  2151.  
  2152. static void PR_CALLBACK
  2153. pr_SummarizeObject(FILE *out, GCType* tp, PRWord *p,
  2154.            size_t bytes, PRBool detailed)
  2155. {
  2156. #if defined(XP_MAC) && XP_MAC
  2157. # pragma unused( out, detailed )
  2158. #endif
  2159.  
  2160.     if (tp->summarize)
  2161.     (*tp->summarize)((void GCPTR*)(p + 1), bytes);
  2162. }
  2163.  
  2164. static void PR_CALLBACK
  2165. pr_DumpSummary(FILE* out, GCSeg* sp, PRBool detailed)
  2166. {
  2167.     pr_WalkSegment(out, sp, detailed, NULL, NULL,
  2168.            pr_SummarizeObject, NULL, NULL);
  2169. }
  2170.  
  2171. PR_IMPLEMENT(void)
  2172. PR_DumpGCSummary(FILE *out, PRBool detailed)
  2173. {
  2174.     if (summaryPrinter) {
  2175.     pr_WalkSegments(out, pr_DumpSummary, detailed);
  2176.     summaryPrinter(out, summaryPrinterClosure);
  2177.     }
  2178. #ifdef xxx_WIN32
  2179.     {
  2180.     extern PRInt32 totalVirtual;
  2181.     fprintf(out, "Virtual memory reserve: %ld, in use: %ld (%ld%%)\n",
  2182.         GC_VMLIMIT, totalVirtual, (totalVirtual * 100 / GC_VMLIMIT));
  2183.     }
  2184. #endif
  2185. #if 0
  2186.     fprintf(out, "\nFinalizable objects:\n");
  2187.     {
  2188.     PRCList *qp;
  2189.     qp = _pr_pendingFinalQueue.next;
  2190.     while (qp != &_pr_pendingFinalQueue) {
  2191.         GCFinal* fp = FinalPtr(qp);
  2192.         PRWord h = fp->object[0];        /* Grab header word */
  2193.         PRWord tix = GET_TYPEIX(h);
  2194.         GCType* tp = _pr_gcTypes[tix];
  2195.         size_t bytes = OBJ_BYTES(h);
  2196.         pr_DumpObject(out, tp, fp->object, bytes, PR_FALSE);
  2197.         qp = qp->next;
  2198.     }
  2199.     }
  2200. #endif
  2201. }
  2202.  
  2203. PR_IMPLEMENT(void)
  2204. PR_DumpMemorySummary(void)
  2205. {
  2206.     PR_DumpToFile("memory.out", "Memory Summary", PR_DumpGCSummary, PR_FALSE);
  2207. }
  2208.  
  2209. /*******************************************************************************
  2210.  * End Of Heap Walker 
  2211.  ******************************************************************************/
  2212.  
  2213. #ifdef GC_TRACEROOTS
  2214.  
  2215. PRInt32 pr_traceGen = 0;
  2216.  
  2217. static PRBool
  2218. pr_IsMarked(PRWord* p)
  2219. {
  2220.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  2221.     PR_ASSERT(end->check == PR_BLOCK_END);
  2222.     return end->traceGeneration == pr_traceGen;
  2223. }
  2224.  
  2225. static void
  2226. pr_Mark(PRWord* p)
  2227. {
  2228.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  2229.     PR_ASSERT(end->check == PR_BLOCK_END);
  2230.     end->traceGeneration = pr_traceGen;
  2231. }
  2232.  
  2233. PRWord* pr_traceObj;    /* set this in the debugger, then execute PR_TraceRoot() */
  2234.  
  2235. static PRInt32 PR_CALLBACK
  2236. pr_TraceRootObject(void* obj, void* data);
  2237.  
  2238. static int32 PR_CALLBACK
  2239. pr_TraceRootPointer(PRWord *p, void* data)
  2240. {
  2241.     PRInt32 printTrace = 0;
  2242.     PRWord h = p[0];
  2243.     PRWord tix = GET_TYPEIX(h);
  2244.     GCType* tp = &_pr_collectorTypes[tix].gctype;
  2245.     FILE* out = _pr_gcData.dumpOutput;
  2246.  
  2247.     PR_ASSERT(tp);
  2248.     if (pr_IsMarked(p))
  2249.     return printTrace;
  2250.  
  2251.     pr_Mark(p);
  2252.     if (p == pr_traceObj) {
  2253.     fprintf(out, "\n### Found path to:\n");
  2254.     printTrace = 1;
  2255.     }
  2256.     else {
  2257.     if (PR_StackSpaceLeft(PR_CurrentThread()) < 512) {
  2258.         fprintf(out, "\n### Path too deep (giving up):\n");
  2259.         printTrace = 1;
  2260.     }
  2261.     else if (tp->walk) {
  2262.         printTrace = tp->walk((void*)(p + 1), pr_TraceRootObject, data);
  2263.     }
  2264.     /* else there's no way to walk this object, so we
  2265.        haven't found what we're looking for */
  2266.     }
  2267.  
  2268.     if (printTrace == 1) {
  2269.     PR_ASSERT(tp->dump);
  2270.     fprintf(out, "0x%p: ", p);
  2271.     tp->dump(out, (void*)(p + 1), PR_FALSE, 1);
  2272.     }
  2273.     return printTrace;
  2274. }
  2275.  
  2276. static PRInt32 PR_CALLBACK
  2277. pr_TraceRootObject(void* obj, void* data)
  2278. {
  2279.     /* This version of pr_TraceRootPointer takes object
  2280.        pointers, instead of gc header pointers. */
  2281.     return pr_TraceRootPointer((PRWord*)obj - 1, data);
  2282. }
  2283.  
  2284. static void PR_CALLBACK
  2285. pr_ConservativeTraceRootPointer(PRWord *p)
  2286. {
  2287.     PRInt32 status;
  2288.     ++pr_traceGen;
  2289.     status = pr_ConservativeWalkPointer(p, pr_TraceRootPointer, NULL);
  2290.     if (status) {
  2291.     FILE* out = _pr_gcData.dumpOutput;
  2292.     fprintf(out, "### from root at 0x%p\n\n", p);
  2293.     }
  2294. }
  2295.  
  2296. static void PR_CALLBACK
  2297. pr_ConservativeTraceRootBlock(void **base, PRInt32 count)
  2298. {
  2299.     PRInt32 status;
  2300.     ++pr_traceGen;
  2301.     status = pr_ConservativeWalkBlock(base, count, pr_TraceRootPointer, NULL);
  2302.     if (status) {
  2303.     FILE* out = _pr_gcData.dumpOutput;
  2304.     fprintf(out, "### from root in range 0x%p + 0x%x\n\n", base, count);
  2305.     }
  2306. }
  2307.  
  2308. static void
  2309. PR_TraceRoot1(FILE* out, PRBool detailed)
  2310. {
  2311.     RootFinder *rf;
  2312.     void (*liveBlock)(void **base, PRInt32 count);
  2313.     void (*livePointer)(void *ptr);
  2314.     void (*processRootBlock)(void **base, PRInt32 count);
  2315.     void (*processRootPointer)(void *ptr);
  2316.  
  2317.     LOCK_GC();
  2318.  
  2319.     liveBlock = _pr_gcData.liveBlock;
  2320.     livePointer = _pr_gcData.livePointer;
  2321.     processRootBlock = _pr_gcData.processRootBlock;
  2322.     processRootPointer = _pr_gcData.processRootPointer;
  2323.     
  2324.     _pr_gcData.liveBlock = pr_ConservativeTraceRootBlock;
  2325.     _pr_gcData.livePointer = pr_ConservativeTraceRootPointer;
  2326.     _pr_gcData.processRootBlock = pr_ConservativeTraceRootBlock;
  2327.     _pr_gcData.processRootPointer = pr_ConservativeTraceRootPointer;
  2328.     _pr_gcData.dumpOutput = out;
  2329.  
  2330.     fprintf(out, "### Looking for paths to 0x%p\n\n", pr_traceObj);
  2331.  
  2332.     rf = _pr_rootFinders;
  2333.     while (rf) {
  2334.     fprintf(out, "\n===== Roots for %s\n", rf->name);
  2335.     (*rf->func)(rf->arg);
  2336.     rf = rf->next;
  2337.     }
  2338.  
  2339.     _pr_gcData.liveBlock = liveBlock;
  2340.     _pr_gcData.livePointer = livePointer;
  2341.     _pr_gcData.processRootBlock = processRootBlock;
  2342.     _pr_gcData.processRootPointer = processRootPointer;
  2343.     _pr_gcData.dumpOutput = NULL;
  2344.  
  2345.     UNLOCK_GC();
  2346. }
  2347.  
  2348. PR_PUBLIC_API(void)
  2349. PR_TraceRoot()
  2350. {
  2351.     /*
  2352.     ** How this works: 
  2353.     ** Once you find the object you want to trace the roots of, set the
  2354.     ** global variable pr_traceObj to point to it (the header, not the
  2355.     ** java handle), and then call this routine (on Windows, you can set
  2356.     ** a breakpoint at the end of a function that returns void (e.g. dogc)
  2357.     ** and then do a "set next statement" to point to this routine and go.
  2358.     ** This will dump a list of the paths from the roots to the object in
  2359.     ** question to your memory.out file.
  2360.     */
  2361.     PR_DumpToFile("memory.out", "Tracing Roots", PR_TraceRoot1, PR_FALSE);
  2362. }
  2363.  
  2364. #endif /* GC_TRACEROOTS */
  2365.  
  2366. /******************************************************************************/
  2367.  
  2368. #if defined(DEBUG) && defined(_WIN32)
  2369. static void DumpApplicationHeap(FILE *out, HANDLE heap)
  2370. {
  2371.     PROCESS_HEAP_ENTRY entry;
  2372.     DWORD err;
  2373.  
  2374.     if (!HeapLock(heap))
  2375.     OutputDebugString("Can't lock the heap.\n");
  2376.     entry.lpData = 0;
  2377.     fprintf(out, "   address:       size ovhd region\n");
  2378.     while (HeapWalk(heap, &entry))
  2379.     {
  2380.     WORD flags = entry.wFlags;
  2381.  
  2382.     fprintf(out, "0x%.8X: 0x%.8X 0x%.2X 0x%.2X  ", entry.lpData, entry.cbData,
  2383.         entry.cbOverhead, entry.iRegionIndex);
  2384.     if (flags & PROCESS_HEAP_REGION)
  2385.         fprintf(out, "REGION  committedSize=0x%.8X uncommittedSize=0x%.8X firstBlock=0x%.8X lastBlock=0x%.8X",
  2386.             entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
  2387.             entry.Region.lpFirstBlock, entry.Region.lpLastBlock);
  2388.     else if (flags & PROCESS_HEAP_UNCOMMITTED_RANGE)
  2389.         fprintf(out, "UNCOMMITTED");
  2390.     else if (flags & PROCESS_HEAP_ENTRY_BUSY)
  2391.     {
  2392.         if (flags & PROCESS_HEAP_ENTRY_DDESHARE)
  2393.         fprintf(out, "DDEShare ");
  2394.         if (flags & PROCESS_HEAP_ENTRY_MOVEABLE)
  2395.         fprintf(out, "Moveable Block  handle=0x%.8X", entry.Block.hMem);
  2396.         else
  2397.         fprintf(out, "Block");
  2398.     }
  2399.     fprintf(out, "\n");
  2400.     }
  2401.     if ((err = GetLastError()) != ERROR_NO_MORE_ITEMS)
  2402.     fprintf(out, "ERROR %d iterating through the heap\n", err);
  2403.     if (!HeapUnlock(heap))
  2404.     OutputDebugString("Can't unlock the heap.\n");
  2405. }
  2406. #endif
  2407.  
  2408. #if defined(DEBUG) && defined(WIN32)
  2409. static void DumpApplicationHeaps(FILE *out)
  2410. {
  2411.     HANDLE mainHeap;
  2412.     HANDLE heaps[100];
  2413.     PRInt32 nHeaps;
  2414.     PRInt32 i;
  2415.  
  2416.     mainHeap = GetProcessHeap();
  2417.     nHeaps = GetProcessHeaps(100, heaps);
  2418.     if (nHeaps > 100)
  2419.     nHeaps = 0;
  2420.     fprintf(out, "%d heaps:\n", nHeaps);
  2421.     for (i = 0; i<nHeaps; i++)
  2422.     {
  2423.     HANDLE heap = heaps[i];
  2424.  
  2425.     fprintf(out, "Heap at 0x%.8X", heap);
  2426.     if (heap == mainHeap)
  2427.         fprintf(out, " (main)");
  2428.     fprintf(out, ":\n");
  2429.     DumpApplicationHeap(out, heap);
  2430.     fprintf(out, "\n");
  2431.     }
  2432.     fprintf(out, "End of heap dump\n\n");
  2433. }
  2434. #endif
  2435.  
  2436. #if defined(DEBUG) && defined(WIN32)
  2437. PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
  2438. {
  2439.     FILE *out;
  2440.  
  2441.     OutputDebugString("Dumping heaps...");
  2442.     out = fopen("heaps.out", "a");
  2443.     if (!out)
  2444.     OutputDebugString("Can't open \"heaps.out\"\n");
  2445.     else
  2446.     {
  2447.     struct tm *newtime;
  2448.     time_t aclock;
  2449.  
  2450.     time(&aclock);
  2451.     newtime = localtime(&aclock);
  2452.     fprintf(out, "Heap dump on %s\n", asctime(newtime));    /* Print current time */
  2453.     DumpApplicationHeaps(out);
  2454.     fprintf(out, "\n\n");
  2455.     fclose(out);
  2456.     }
  2457.     OutputDebugString(" done\n");
  2458. }
  2459. #else
  2460.  
  2461. PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
  2462. {
  2463.     fprintf(stderr, "Native heap dumping is currently implemented only for Windows32.\n");
  2464. }
  2465. #endif
  2466.  
  2467. /************************************************************************/
  2468.  
  2469. /*
  2470. ** Scan the freelist bins looking for a big enough chunk of memory to
  2471. ** hold "bytes" worth of allocation. "bytes" already has the
  2472. ** per-allocation header added to it. Return a pointer to the object with
  2473. ** its per-allocation header already prepared.
  2474. */
  2475. static PRWord *BinAlloc(int cbix, PRInt32 bytes, int dub)
  2476. {
  2477.     GCFreeChunk **cpp, *cp, *cpNext;
  2478.     GCSeg *sp;
  2479.     PRInt32 chunkSize, remainder;
  2480.     PRWord *p, *np;
  2481.     PRInt32 bin, newbin;
  2482.  
  2483.     /* Compute bin that allocation belongs in */
  2484.     InlineBinNumber(bin,bytes)
  2485.     if (bin < minBin) {
  2486.     bin = minBin;    /* Start at first filled bin */
  2487.     }
  2488.  
  2489.     /* Search in the bin, and larger bins, for a big enough piece */
  2490.     for (; bin <= NUM_BINS-1; bin++) {
  2491.         cpp = &bins[bin];
  2492.     while ((cp = *cpp) != 0) {
  2493.         chunkSize = cp->chunkSize;
  2494.         if (chunkSize < bytes) {
  2495.         /* Too small; skip it */
  2496.             METER(meter.skippedFreeChunks++);
  2497.         cpp = &cp->next;
  2498.         continue;
  2499.         }
  2500.  
  2501.         /* We have found a hunk of memory large enough to use */
  2502.         p = (PRWord*) cp;
  2503.         sp = cp->segment;
  2504.         cpNext = cp->next;
  2505. #ifndef IS_64
  2506.         if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
  2507.         /*
  2508.          * We are double aligning the memory and the current free
  2509.          * chunk is aligned on an even boundary. Because header
  2510.          * words are one word long we need to discard the first
  2511.          * word of memory.
  2512.          */
  2513.         p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
  2514.         SET_HBIT(sp, p);
  2515.         p++;
  2516.         chunkSize -= PR_BYTES_PER_WORD;
  2517.         bytes -= PR_BYTES_PER_WORD;
  2518.         PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
  2519.         _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
  2520.         _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
  2521.         }
  2522. #endif
  2523.         np = (PRWord*) ((char*) p + bytes);
  2524.         remainder = chunkSize - bytes;
  2525.         if (remainder >= MIN_FREE_CHUNK_BYTES) {
  2526.         /* The left over memory is large enough to be freed. */
  2527.         cp = (GCFreeChunk*) np;
  2528.         cp->segment = sp;
  2529.         cp->chunkSize = remainder;
  2530.         InlineBinNumber(newbin, remainder)
  2531.         if (newbin != bin) {
  2532.             *cpp = (GCFreeChunk*) cpNext; /* remove */
  2533.             cp->next = bins[newbin];      /* insert */
  2534.             bins[newbin] = cp;
  2535.             if (newbin < minBin) minBin = newbin;
  2536.             if (newbin > maxBin) maxBin = newbin;
  2537.         } else {
  2538.             /* Leave it on the same list */
  2539.             cp->next = cpNext;
  2540.             *cpp = (GCFreeChunk*) np;
  2541.         }
  2542.         } else {
  2543.         /*
  2544.          * The left over memory is too small to be released. Just
  2545.          * leave it attached to the chunk of memory being
  2546.          * returned.
  2547.          */
  2548.         *cpp = cpNext;
  2549.         bytes = chunkSize;
  2550.         }
  2551.         p[0] = MAKE_HEADER(cbix, (bytes >> PR_BYTES_PER_WORD_LOG2));
  2552.         SET_HBIT(sp, p);
  2553.         _pr_gcData.freeMemory -= bytes;
  2554.         _pr_gcData.busyMemory += bytes;
  2555.         return p;
  2556.     }
  2557.     }
  2558.     return 0;
  2559. }
  2560.  
  2561. /*
  2562. ** Allocate a piece of memory that is "big" in it's own segment.  Make
  2563. ** the object consume the entire segment to avoid fragmentation.  When
  2564. ** the object is no longer referenced, the segment is freed.
  2565. */
  2566. static PRWord *BigAlloc(int cbix, PRInt32 bytes, int dub)
  2567. {
  2568.     GCSeg *sp;
  2569.     PRWord *p, h;
  2570.     PRInt32 chunkSize;
  2571.  
  2572.     /*
  2573.     ** If the number of bytes allocated via BigAlloc() since the last GC
  2574.     ** exceeds BIG_ALLOC_GC_SIZE then do a GC Now...
  2575.     */
  2576.     if (bigAllocBytes >= BIG_ALLOC_GC_SIZE) {
  2577.         dogc();
  2578.     }
  2579.     bigAllocBytes += bytes;
  2580.  
  2581.     /* Get a segment to hold this allocation */
  2582.     sp = GrowHeapExactly(bytes);
  2583.  
  2584.     if (sp) {
  2585.         p = (PRWord*) sp->base;
  2586.         chunkSize = sp->limit - sp->base;
  2587.  
  2588.         /* All memory is double aligned on 64 bit machines... */
  2589. #ifndef IS_64
  2590.         if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
  2591.             /*
  2592.             ** Consume the first word of the chunk with a dummy
  2593.             ** unreferenced object.
  2594.             */
  2595.             p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
  2596.             SET_HBIT(sp, p);
  2597.             p++;
  2598.             chunkSize -= PR_BYTES_PER_WORD;
  2599.             _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
  2600.             _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
  2601.             PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
  2602.         }
  2603. #endif
  2604.  
  2605. #if defined(WIN16)
  2606.             /* All memory MUST be aligned on 32bit boundaries */
  2607.             PR_ASSERT( (((PRWord)p) & (PR_BYTES_PER_WORD-1)) == 0 );
  2608. #endif
  2609.  
  2610.         /* Consume the *entire* segment with a single allocation */
  2611.         h = MAKE_HEADER(cbix, (chunkSize >> PR_BYTES_PER_WORD_LOG2));
  2612.         p[0] = h;
  2613.         SET_HBIT(sp, p);
  2614.         _pr_gcData.freeMemory -= chunkSize;
  2615.         _pr_gcData.busyMemory += chunkSize;
  2616.     return p;
  2617.     }
  2618.     return 0;
  2619. }
  2620.  
  2621. /* we disable gc allocation during low memory conditions */
  2622. static PRBool allocationEnabled = PR_TRUE;
  2623.  
  2624. PR_IMPLEMENT(void) PR_EnableAllocation(PRBool yesOrNo)
  2625. {
  2626.     allocationEnabled = yesOrNo;
  2627. }
  2628.  
  2629. static void CollectorCleanup(void) {
  2630.     while (collectorCleanupNeeded) {
  2631.     LOCK_GC();
  2632.     collectorCleanupNeeded = 0;
  2633.     UNLOCK_GC();
  2634.     if (freeSegs) {
  2635.         FreeSegments();
  2636.     }
  2637.     if (!WEAK_FREELIST_ISEMPTY()) {
  2638.         EmptyWeakFreeList();
  2639.     }
  2640.     }
  2641. }
  2642.  
  2643. /******************************************************************************/
  2644.  
  2645. #ifdef GC_CHECK
  2646. static PRInt32 allocationCount;
  2647.  
  2648. static void EarthShatteringKaBoom(PRInt32 whichOne) {
  2649.     long* p = 0;
  2650.     *p = 0;
  2651. }
  2652.  
  2653. /* Check a segment of heap memory. Verify that the object memory
  2654.    hasn't been overwritten (past the end at least) */
  2655. static void CheckSegment(GCSeg* sp) {
  2656.     PRWord h, tix;
  2657.     PRWord *p, *lastp, *np, *limit;
  2658.  
  2659.     lastp = p = (PRWord *) sp->base;
  2660.     limit = (PRWord *) sp->limit;
  2661.     while (p < limit) {
  2662.     if (IS_HBIT(sp, p)) {
  2663.         char *cp, i;
  2664.         GCBlockEnd* end;
  2665.         PRWord bytes, requestedBytes;
  2666.  
  2667.         h = p[0];
  2668.         tix = GET_TYPEIX(h);
  2669.         bytes = OBJ_BYTES(h);
  2670.         np = (PRWord *) ((char *)p + bytes);
  2671.         if (tix != FREE_MEMORY_TYPEIX) {
  2672.                 PRInt32 test;    /* msdev get's fooled without this local */
  2673.         /* A live object is here. The last word in the object will
  2674.            contain the objects requestedSize */
  2675.         end = (GCBlockEnd*)((char*)(p) + bytes - sizeof(GCBlockEnd));
  2676.         test = end->check;
  2677.         if (test != PR_BLOCK_END) {
  2678.             PR_ASSERT(test == PR_BLOCK_END);
  2679.         }
  2680.         requestedBytes = end->requestedBytes;
  2681.         if (requestedBytes >= bytes) EarthShatteringKaBoom(0);
  2682.         cp = (char*)(p + 1) + requestedBytes;
  2683.         i = (char) 0xff;
  2684.         while (cp < (char*)end) {
  2685.             if (*cp != i) EarthShatteringKaBoom(1);
  2686.             cp++;
  2687.             i--;
  2688.         }
  2689.         }
  2690.         lastp = p;
  2691.         p = np;
  2692.     } else {
  2693.         /* Must be a freelist item */
  2694.         GCFreeChunk *cp = (GCFreeChunk*) p;
  2695.         if ((PRInt32)cp->chunkSize < (PRInt32)sizeof(GCFreeChunk)) {
  2696.             EarthShatteringKaBoom(3);
  2697.         }
  2698.         lastp = p;
  2699.         p = (PRWord*) ((char*)p + cp->chunkSize);
  2700.     }
  2701.     }
  2702. }
  2703.  
  2704. static void CheckHeap(void) {
  2705.     GCSeg *sp = segs;
  2706.     GCSeg *esp = sp + nsegs;
  2707.     while (sp < esp) {
  2708.     CheckSegment(sp);
  2709.     sp++;
  2710.     }
  2711. }
  2712.  
  2713. #endif /* GC_CHECK */
  2714.  
  2715. /******************************************************************************/
  2716.  
  2717. #ifdef DEBUG
  2718. int gc_thrash = -1;
  2719. #endif
  2720.  
  2721. /*
  2722. ** Allocate memory from the GC Heap. Performs garbage collections if
  2723. ** memory gets tight and grows the heap as needed. May return NULL if
  2724. ** memory cannot be found.
  2725. */
  2726. PR_IMPLEMENT(PRWord GCPTR *)PR_AllocMemory(
  2727.     PRWord requestedBytes, PRInt32 tix, PRWord flags)
  2728. {
  2729.     PRWord *p;
  2730.     CollectorType *ct;
  2731.     PRInt32 bytes;
  2732.     GCFinal *final = 0;
  2733.     GCWeak *weak = 0;
  2734.     int dub = flags & PR_ALLOC_DOUBLE;
  2735.     PRInt32 objBytes;
  2736. #ifdef GC_STATS
  2737.     PRInt64 allocTime, ldelta;
  2738. #endif
  2739.  
  2740.     if (!allocationEnabled) return NULL;
  2741.  
  2742.     PR_ASSERT(requestedBytes >= 0);
  2743.     PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
  2744.  
  2745. #ifdef DEBUG
  2746.     if (_pr_do_a_dump) {
  2747.     /*
  2748.     ** Collect, pause for a second (lets finalizer run), and then GC
  2749.     ** again.
  2750.     */
  2751.     PR_GC();
  2752.     PR_Sleep(PR_MicrosecondsToInterval(1000000L));
  2753.     PR_GC();
  2754.     PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
  2755.     _pr_do_a_dump = 0;
  2756.     }
  2757. #endif
  2758.  
  2759. #ifdef GC_STATS
  2760.     allocTime = PR_Now();
  2761. #endif
  2762.     bytes = (PRInt32) requestedBytes;
  2763.  
  2764.     /*
  2765.     ** Align bytes to a multiple of a PRWord, then add in enough space
  2766.     ** to hold the header word.
  2767.     **
  2768.     ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
  2769.     */
  2770. #if !defined(WIN16) 
  2771.     /* Check for possible overflow of bytes before performing add */
  2772.     if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
  2773.     bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
  2774.     bytes <<= PR_BYTES_PER_WORD_LOG2;
  2775.     /* Check for possible overflow of bytes before performing add */
  2776.     if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
  2777.     bytes += sizeof(PRWord);
  2778. #else 
  2779.     /* 
  2780.     ** For WIN16 the shifts have been broken out into separate statements
  2781.     ** to prevent the compiler from crashing...
  2782.     */
  2783.     {
  2784.         PRWord shiftVal;
  2785.  
  2786.         /* Check for possible overflow of bytes before performing add */
  2787.         if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
  2788.         bytes += PR_BYTES_PER_WORD - 1L;
  2789.         shiftVal = PR_BYTES_PER_WORD_LOG2;
  2790.         bytes >>= shiftVal;
  2791.         bytes <<= shiftVal;
  2792.         /* Check for possible overflow of bytes before performing add */
  2793.         if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
  2794.         bytes += sizeof(PRWord);
  2795.     }
  2796. #endif
  2797.     /*
  2798.      * Add in an extra word of memory for double-aligned memory. Some
  2799.      * percentage of the time this will waste a word of memory (too
  2800.      * bad). Howver, it makes the allocation logic much simpler and
  2801.      * faster.
  2802.      */
  2803. #ifndef IS_64
  2804.     if (dub) {
  2805.         /* Check for possible overflow of bytes before performing add */
  2806.         if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
  2807.         bytes += PR_BYTES_PER_WORD;
  2808.     }
  2809. #endif
  2810.  
  2811. #ifdef GC_CHECK
  2812.     if (_pr_gcData.flags & GC_CHECK) {
  2813.         /* Bloat the allocation a bit so that we can lay down
  2814.            a check pattern that we will validate */
  2815.         /* Check for possible overflow of bytes before performing add */
  2816.         if ((MAX_INT - PR_BYTES_PER_WORD * 3) < bytes ) return NULL;
  2817.         bytes += PR_BYTES_PER_WORD * 3;
  2818.     }
  2819. #endif
  2820.  
  2821. #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
  2822.     if ((MAX_INT - sizeof(GCBlockEnd)) < bytes ) return NULL;
  2823.     bytes += sizeof(GCBlockEnd);
  2824. #endif
  2825.  
  2826.     PR_ASSERT( bytes < MAX_ALLOC_SIZE );
  2827.     /*
  2828.     ** Java can ask for objects bigger than MAX_ALLOC_SIZE,
  2829.     ** but it won't get them.
  2830.     */
  2831.     if (bytes >= MAX_ALLOC_SIZE) return NULL;
  2832.  
  2833. #ifdef DEBUG
  2834.     if (gc_thrash == -1 ? (gc_thrash = (int)PR_GetEnv("GC_THRASH")):gc_thrash) PR_GC();
  2835. #endif
  2836.  
  2837.     ct = &_pr_collectorTypes[tix];
  2838.     if (ct->flags & (_GC_TYPE_FINAL|_GC_TYPE_WEAK)) {
  2839.     if (0 != ct->gctype.finalize) {
  2840.         /*
  2841.         ** Allocate a GCFinal struct for this object in advance. Don't put
  2842.         ** it on the pending list until we have allocated the object
  2843.         */
  2844.         final = AllocFinalNode();
  2845.         if (!final) {
  2846.         /* XXX THIS IS NOT ACCEPTABLE*/
  2847.         PR_ASSERT(0);
  2848.         return 0;
  2849.         }
  2850.     }
  2851.     if (0 != ct->gctype.getWeakLinkOffset) {
  2852.         /*
  2853.         ** Allocate a GCWeak struct for this object in advance. Don't put
  2854.         ** it on the weak links list until we have allocated the object
  2855.         */
  2856.         weak = AllocWeakNode();
  2857.         if (!weak) {
  2858.         /* XXX THIS IS NOT ACCEPTABLE*/
  2859.         if (0 != final) {
  2860.             FreeFinalNode(final);
  2861.         }
  2862.         PR_ASSERT(0);
  2863.         return 0;
  2864.         }
  2865.     }
  2866.     }
  2867.  
  2868.     LOCK_GC();
  2869. #ifdef GC_CHECK
  2870.     if (_pr_gcData.flags & GC_CHECK) CheckHeap();
  2871.     allocationCount++;
  2872. #endif
  2873.  
  2874.     /* Check for overflow of maximum size we can handle */
  2875.     if (bytes > MAX_ALLOC) goto lost;
  2876.  
  2877.     /* Try default allocation */
  2878.     p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
  2879.         BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
  2880.     if (0 == p) {
  2881. #ifdef GC_STATS
  2882.         LL_SUB(ldelta, PR_Now(), allocTime);
  2883. #endif
  2884.         /* Collect some memory */
  2885.         _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
  2886.         dogc();
  2887.         PR_ASSERT( GC_IS_LOCKED() );
  2888.  
  2889.         /* After a collection we check and see if we should grow the
  2890.         ** heap. We grow the heap when the amount of memory free is less
  2891.         ** than a certain percentage of the heap size. We don't check to
  2892.         ** see if the grow succeeded because our fallback strategy in
  2893.         ** either case is to try one more time to allocate. */
  2894.         if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory)
  2895.         && ((_pr_gcData.freeMemory <
  2896.             ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))
  2897.         || (_pr_gcData.freeMemory < bytes))) {
  2898.             GrowHeap(PR_MAX(bytes, segmentSize));
  2899.         }
  2900. #ifdef GC_STATS
  2901.         LL_ADD(allocTime, PR_Now(), ldelta);
  2902. #endif
  2903.  
  2904.         /* Try again */
  2905.         p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
  2906.             BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
  2907.         if (0 == p) {
  2908.             /* Well that lost big time. Memory must be pretty well fragmented */
  2909.             if (!GrowHeap(PR_MAX(bytes, segmentSize))) goto lost;
  2910.             p = BinAlloc(tix, bytes, dub);
  2911.             if (0 == p) goto lost;
  2912.         }
  2913.     }
  2914.  
  2915.     /* Zero out the portion of the object memory that was used by
  2916.        the GCFreeChunk structure (skip the first word because it
  2917.        was already overwritten by the gc header word) */
  2918.     objBytes = OBJ_BYTES(p[0]);
  2919.     if (objBytes > sizeof(PRWord)) p[1] = 0;
  2920.     if (objBytes > sizeof(PRWord)*2) p[2] = 0;
  2921.  
  2922.     if (final) {
  2923.     _GCTRACE(GC_ALLOC, ("alloc 0x%x (%d) final=0x%x",
  2924.                 p, bytes, final));
  2925.     final->object = p;
  2926.     PR_APPEND_LINK(&final->links, &_pr_finalizeableObjects);
  2927.     } else {
  2928.     _GCTRACE(GC_ALLOC, ("alloc 0x%x (%d)", p, bytes));
  2929.     }
  2930.     if (weak) {
  2931.     weak->object = p;
  2932.     PR_APPEND_LINK(&weak->links, &_pr_weakLinks);
  2933.     }
  2934.     METER(meter.allocBytes += bytes);
  2935.     METER(meter.wastedBytes += (bytes - requestedBytes));
  2936.     UNLOCK_GC();
  2937.  
  2938.     if (collectorCleanupNeeded) {
  2939.     CollectorCleanup();
  2940.     }
  2941.  
  2942. #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
  2943.     {
  2944.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  2945.     end->check = PR_BLOCK_END;
  2946.     }
  2947. #endif
  2948. #ifdef GC_STATS
  2949.     {
  2950.     PRInt64 now = PR_Now();
  2951.     double delta;
  2952.     PRInt32 bin;
  2953.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  2954.  
  2955.     end->allocTime = allocTime;
  2956.     LL_SUB(ldelta, now, allocTime);
  2957.     LL_L2D(delta, ldelta);
  2958.     InlineBinNumber(bin, requestedBytes);
  2959.     end->bin = bin;
  2960.     gcstats[bin].nallocs++;
  2961.     gcstats[bin].allocTime += delta;
  2962.     gcstats[bin].allocTimeVariance += delta * delta;
  2963.     }
  2964. #endif
  2965. #ifdef GC_CHECK
  2966.     if (_pr_gcData.flags & GC_CHECK) {
  2967.     /* Place a pattern in the memory that was allocated that was not
  2968.        requested. We will check the pattern later. */
  2969.     char* cp = (char*)(p + 1) + requestedBytes;
  2970.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  2971.     char i = (char) 0xff;
  2972.     while (cp < (char*)end) {
  2973.         *cp++ = i--;
  2974.     }
  2975.     end->requestedBytes = requestedBytes;
  2976.     CheckHeap();
  2977.     }
  2978. #endif
  2979.     return p + 1;
  2980.  
  2981.   lost:
  2982.     /* Out of memory */
  2983.     UNLOCK_GC();
  2984.     if (final) {
  2985.     FreeFinalNode(final);
  2986.     }
  2987.     if (weak) {
  2988.     FreeWeakNode(weak);
  2989.     }
  2990.     if (collectorCleanupNeeded) {
  2991.     CollectorCleanup();
  2992.     }
  2993.     return 0;
  2994. }
  2995.  
  2996. /* Shortcut allocator for objects that do not require finalization or
  2997.    are weak objects */
  2998. PR_IMPLEMENT(PRWord GCPTR *)
  2999. PR_AllocSimpleMemory(PRWord requestedBytes, PRInt32 tix)
  3000. {
  3001.     PRWord *p;
  3002.     PRInt32 bytes;
  3003.     PRInt32 objBytes;
  3004. #ifdef GC_STATS
  3005.     PRInt64 allocTime, ldelta;
  3006. #endif
  3007.  
  3008.     if (!allocationEnabled) return NULL;
  3009.  
  3010.     PR_ASSERT(requestedBytes >= 0);
  3011.     PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
  3012.  
  3013. #ifdef DEBUG
  3014.     if (_pr_do_a_dump) {
  3015.     /*
  3016.     ** Collect, pause for a second (lets finalizer run), and then GC
  3017.     ** again.
  3018.     */
  3019.     PR_GC();
  3020.     PR_Sleep(PR_MicrosecondsToInterval(1000000L));
  3021.     PR_GC();
  3022.     PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
  3023.     _pr_do_a_dump = 0;
  3024.     }
  3025. #endif
  3026.  
  3027. #ifdef GC_STATS
  3028.     allocTime = PR_NowMS();
  3029. #endif
  3030.     bytes = (PRInt32) requestedBytes;
  3031.  
  3032.     /*
  3033.     ** Align bytes to a multiple of a PRWord, then add in enough space
  3034.     ** to hold the header word.
  3035.     **
  3036.     ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
  3037.     */
  3038. #if !defined(WIN16) 
  3039.     bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
  3040.     bytes <<= PR_BYTES_PER_WORD_LOG2;
  3041.     bytes += sizeof(PRWord);
  3042. #else 
  3043.     /* 
  3044.     ** For WIN16 the shifts have been broken out into separate statements
  3045.     ** to prevent the compiler from crashing...
  3046.     */
  3047.     {
  3048.     PRWord shiftVal;
  3049.  
  3050.     bytes += PR_BYTES_PER_WORD - 1L;
  3051.     shiftVal = PR_BYTES_PER_WORD_LOG2;
  3052.     bytes >>= shiftVal;
  3053.     bytes <<= shiftVal;
  3054.     bytes += sizeof(PRWord);
  3055.     }
  3056. #endif
  3057.     
  3058.     /*
  3059.      * Add in an extra word of memory for double-aligned memory. Some
  3060.      * percentage of the time this will waste a word of memory (too
  3061.      * bad). Howver, it makes the allocation logic much simpler and
  3062.      * faster.
  3063.      */
  3064. #ifndef IS_64
  3065.     bytes += PR_BYTES_PER_WORD;
  3066. #endif
  3067.  
  3068. #ifdef GC_CHECK
  3069.     if (_pr_gcData.flags & GC_CHECK) {
  3070.     /* Bloat the allocation a bit so that we can lay down
  3071.        a check pattern that we will validate */
  3072.     bytes += PR_BYTES_PER_WORD * 2;
  3073.     }
  3074. #endif
  3075.  
  3076. #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
  3077.     bytes += sizeof(GCBlockEnd);
  3078. #endif
  3079.  
  3080. #if defined(WIN16)
  3081.     PR_ASSERT( bytes < MAX_ALLOC_SIZE );
  3082. #endif
  3083.     /* Java can ask for objects bigger than 4M, but it won't get them */
  3084.     if (bytes >= MAX_ALLOC_SIZE) {
  3085.         return NULL;
  3086.     }
  3087. #ifdef DEBUG
  3088.     if (gc_thrash == -1
  3089.     ? (gc_thrash = (int)PR_GetEnv("GC_THRASH"))
  3090.     : gc_thrash) {
  3091.     PR_GC();
  3092.     }
  3093. #endif
  3094.  
  3095.     LOCK_GC();
  3096. #ifdef GC_CHECK
  3097.     if (_pr_gcData.flags & GC_CHECK) {
  3098.     CheckHeap();
  3099.     }
  3100.     allocationCount++;
  3101. #endif
  3102.  
  3103.     /* Try default allocation */
  3104.     if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
  3105.     p = BigAlloc(tix, bytes, 1);
  3106.     } else {
  3107.     p = BinAlloc(tix, bytes, 1);
  3108.     }
  3109.     if (0 == p) {
  3110. #ifdef GC_STATS
  3111.       LL_SUB(ldelta, PR_Now(), allocTime);
  3112. #endif
  3113.       /* Collect some memory */
  3114.       _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
  3115.       dogc();
  3116.       PR_ASSERT( GC_IS_LOCKED() );
  3117.  
  3118.       /* After a collection we check and see if we should grow the
  3119.      heap. We grow the heap when the amount of memory free is less
  3120.      than a certain percentage of the heap size. We don't check to
  3121.      see if the grow succeeded because our fallback strategy in
  3122.      either case is to try one more time to allocate. */
  3123.       if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory) &&
  3124.       (_pr_gcData.freeMemory <
  3125.        ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))) {
  3126.     GrowHeap(PR_MAX(bytes, segmentSize));
  3127.       }
  3128. #ifdef GC_STATS
  3129.       LL_ADD(allocTime, PR_Now(), ldelta);
  3130. #endif
  3131.  
  3132.       /* Try one last time */
  3133.       if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
  3134.     p = BigAlloc(tix, bytes, 1);
  3135.       } else {
  3136.     p = BinAlloc(tix, bytes, 1);
  3137.       }
  3138.       if (0 == p) {
  3139.     /* Well that lost big time. Memory must be pretty well fragmented */
  3140.     if (!GrowHeap(PR_MAX(bytes, segmentSize))) {
  3141.       goto lost;
  3142.     }
  3143.     p = BinAlloc(tix, bytes, 1);
  3144.     if (0 == p) goto lost;
  3145.       }
  3146.     }
  3147.  
  3148.     /* Zero out the portion of the object memory that was used by
  3149.        the GCFreeChunk structure (skip the first word because it
  3150.        was already overwritten by the gc header word) */
  3151.     objBytes = OBJ_BYTES(p[0]);
  3152.     if (objBytes > sizeof(PRWord)) p[1] = 0;
  3153.     if (objBytes > sizeof(PRWord)*2) p[2] = 0;
  3154.  
  3155.     METER(meter.allocBytes += bytes);
  3156.     METER(meter.wastedBytes += (bytes - requestedBytes));
  3157.     UNLOCK_GC();
  3158.  
  3159.     if (collectorCleanupNeeded) {
  3160.     CollectorCleanup();
  3161.     }
  3162.  
  3163. #if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
  3164.     {
  3165.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  3166.     end->check = PR_BLOCK_END;
  3167.     }
  3168. #endif
  3169. #ifdef GC_STATS
  3170.     {
  3171.     PRInt64 now = PR_Now();
  3172.     double delta;
  3173.     int32 bin;
  3174.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  3175.  
  3176.     end->allocTime = allocTime;
  3177.     LL_SUB(ldelta, now, allocTime);
  3178.     LL_L2D(delta, ldelta);
  3179.     InlineBinNumber(bin, requestedBytes);
  3180.     end->bin = bin;
  3181.     gcstats[bin].nallocs++;
  3182.     gcstats[bin].allocTime += delta;
  3183.     gcstats[bin].allocTimeVariance += delta * delta;
  3184.     }
  3185. #endif
  3186. #ifdef GC_CHECK
  3187.     if (_pr_gcData.flags & GC_CHECK) {
  3188.     /* Place a pattern in the memory that was allocated that was not
  3189.        requested. We will check the pattern later. */
  3190.     char* cp = (char*)(p + 1) + requestedBytes;
  3191.     GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
  3192.     char i = (char) 0xff;
  3193.     while (cp < (char*)end) {
  3194.         *cp++ = i--;
  3195.     }
  3196.     end->requestedBytes = requestedBytes;
  3197.     CheckHeap();
  3198.     }
  3199. #endif
  3200.     return p + 1;
  3201.  
  3202.   lost:
  3203.     /* Out of memory */
  3204.     UNLOCK_GC();
  3205.     if (collectorCleanupNeeded) {
  3206.     CollectorCleanup();
  3207.     }
  3208.     return 0;
  3209. }
  3210.  
  3211. /************************************************************************/
  3212.  
  3213. PR_IMPLEMENT(PRWord) PR_GetObjectHeader(void *ptr) {
  3214.     GCSeg *sp;
  3215.     PRWord *h;
  3216.  
  3217.     if (ptr == 0) return 0;
  3218.     sp = InHeap(ptr);
  3219.     if (sp == 0) return 0;
  3220.     h = (PRWord*)FindObject(sp, (PRWord*)ptr);
  3221.     return GC_GET_USER_BITS(h[0]);
  3222. }
  3223.  
  3224. PR_IMPLEMENT(PRWord) PR_SetObjectHeader(void *ptr, PRWord newUserBits) {
  3225.     GCSeg *sp;
  3226.     PRWord *h, rv;
  3227.  
  3228.     if (ptr == 0) return 0;
  3229.     sp = InHeap(ptr);
  3230.     if (sp == 0) return 0;
  3231.     h = (PRWord*)FindObject(sp, (PRWord*)ptr);
  3232.     rv = GC_GET_USER_BITS(h[0]);
  3233.     h[0] = (h[0] & ~GC_USER_BITS) |
  3234.     ((newUserBits << GC_USER_BITS_SHIFT) & GC_USER_BITS);
  3235.     return rv;
  3236. }
  3237.  
  3238. PR_IMPLEMENT(void) PR_InitGC(
  3239.     PRWord flags, PRInt32 initialHeapSize, PRInt32 segSize, PRThreadScope scope)
  3240. {
  3241.     static char firstTime = 1;
  3242.  
  3243.     if (!firstTime) return;
  3244.     firstTime = 0;
  3245.  
  3246.     _pr_msgc_lm = PR_NewLogModule("msgc");
  3247.     _pr_pageShift = PR_GetPageShift();
  3248.     _pr_pageSize = PR_GetPageSize();
  3249.  
  3250. #if defined(WIN16)
  3251.     PR_ASSERT( initialHeapSize < MAX_ALLOC_SIZE );
  3252. #endif
  3253.  
  3254.   /* Setup initial heap size and initial segment size */
  3255.   if (0 != segSize) segmentSize = segSize;
  3256. #ifdef DEBUG
  3257.     GC = PR_NewLogModule("GC");
  3258.     {
  3259.     char *ev = PR_GetEnv("GC_SEGMENT_SIZE");
  3260.     if (ev && ev[0]) {
  3261.       PRInt32 newSegmentSize = atoi(ev);
  3262.       if (0 != newSegmentSize) segmentSize = newSegmentSize;
  3263.     }
  3264.     ev = PR_GetEnv("GC_INITIAL_HEAP_SIZE");
  3265.     if (ev && ev[0]) {
  3266.       PRInt32 newInitialHeapSize = atoi(ev);
  3267.       if (0 != newInitialHeapSize) initialHeapSize = newInitialHeapSize;
  3268.     }
  3269.     ev = PR_GetEnv("GC_FLAGS");
  3270.     if (ev && ev[0]) {
  3271.         flags |= atoi(ev);
  3272.     }
  3273. #ifdef GCMETER
  3274.         ev = PR_GetEnv("GC_METER");
  3275.         if (ev && ev[0]) {
  3276.             _pr_gcMeter = atoi(ev);
  3277.         }
  3278. #endif
  3279.     }
  3280. #endif
  3281.   if (0 == initialHeapSize) initialHeapSize = segmentSize;
  3282.   if (initialHeapSize < segmentSize) initialHeapSize = segmentSize;
  3283.  
  3284.   _pr_gcData.maxMemory   = MAX_SEGS * segmentSize;
  3285.   _pr_gcData.liveBlock  = ProcessRootBlock;
  3286.   _pr_gcData.livePointer = ProcessRootPointer;
  3287.   _pr_gcData.processRootBlock  = ProcessRootBlock;
  3288.   _pr_gcData.processRootPointer = ProcessRootPointer;
  3289.   _pr_gcData.dumpOutput = NULL;
  3290.  
  3291.   PR_INIT_CLIST(&_pr_finalizeableObjects);
  3292.     PR_INIT_CLIST(&_pr_finalQueue);
  3293.     _PR_InitGC(flags);
  3294.  
  3295.     /* Create finalizer thread */
  3296.     _PR_CreateFinalizer(scope);
  3297.  
  3298.   /* Allocate the initial segment for the heap */
  3299.   minBin = 31;
  3300.   maxBin = 0;
  3301.   GrowHeap(initialHeapSize);
  3302.     PR_RegisterRootFinder(ScanWeakFreeList, "scan weak free list", 0);
  3303. }
  3304.  
  3305. #if defined(WIN16)
  3306. /*
  3307. ** For WIN16 the GC_IN_HEAP() macro must call the private InHeap function.
  3308. ** This public wrapper function makes this possible...
  3309. */
  3310. PR_IMPLEMENT(PRBool)
  3311. PR_GC_In_Heap(void *object)
  3312. {
  3313.     return InHeap( object ) != NULL;    
  3314. }
  3315. #endif
  3316.  
  3317.  
  3318. /** Added by Vishy for sanity checking a few GC structures **/
  3319. /** Can use SanityCheckGC to debug corrupted GC Heap situations **/
  3320.  
  3321. #ifdef DEBUG
  3322.  
  3323. static int SegmentOverlaps(int i, int j)
  3324. {
  3325.   return
  3326.     (((segs[i].limit > segs[j].base) && (segs[i].base < segs[j].base)) ||
  3327.      ((segs[j].limit > segs[i].base) && (segs[j].base < segs[i].base)));
  3328. }
  3329.  
  3330. static void NoSegmentOverlaps(void)
  3331. {
  3332.   int i,j;
  3333.  
  3334.   for (i = 0; i < nsegs; i++)
  3335.     for (j = i+1 ; j < nsegs ; j++)
  3336.       PR_ASSERT(!SegmentOverlaps(i,j));
  3337. }
  3338.  
  3339. static void SegInfoCheck(void)
  3340. {
  3341.   int i;
  3342.   for (i = 0 ; i < nsegs ; i++)
  3343.     PR_ASSERT((segs[i].info->hbits) &&
  3344.           (segs[i].info->hbits == segs[i].hbits) &&
  3345.           (segs[i].info->base == segs[i].base) &&
  3346.           (segs[i].info->limit == segs[i].limit));
  3347. }
  3348.  
  3349. static void SanityCheckGC()
  3350. {
  3351.   NoSegmentOverlaps();
  3352.   SegInfoCheck();
  3353. }
  3354.  
  3355. #endif
  3356.  
  3357. #if defined(DEBUG) && defined(WIN32)
  3358.  
  3359. extern void *baseaddr;
  3360. extern void *lastaddr;
  3361.  
  3362. PR_IMPLEMENT(void)
  3363. PR_PrintGCStats(void)
  3364. {
  3365.     long reportedSegSpace = _pr_gcData.busyMemory + _pr_gcData.freeMemory;
  3366.     char* msg;
  3367.     long largeCount = 0, largeSize = 0;
  3368.     long segCount = 0, segSize = 0;
  3369.     long freeCount = 0, freeSize = 0;
  3370.     GCSeg *sp, *esp;
  3371.     GCSegInfo* si;
  3372.  
  3373.     LOCK_GC();
  3374.  
  3375.     sp = segs;
  3376.     esp = sp + nsegs;
  3377.     while (sp < esp) {
  3378.     long size = sp->info->limit - sp->info->base;
  3379.     segCount++;
  3380.     segSize += size;
  3381.         if (sp->info->fromMalloc) {
  3382.         largeCount++;
  3383.         largeSize += size;
  3384.     }
  3385.         sp++;
  3386.     }
  3387.  
  3388.     si = freeSegs;
  3389.     while (si != NULL) {
  3390.     long size = si->limit - si->base;
  3391.     freeCount++;
  3392.     freeSize += size;
  3393.     si = si->next;
  3394.     }
  3395.     
  3396.     msg = PR_smprintf("\
  3397. # GC Stats:\n\
  3398. #   vm space:\n\
  3399. #     range:      %ld - %ld\n\
  3400. #     size:       %ld\n\
  3401. #   segments:\n\
  3402. #     range:      %ld - %ld\n\
  3403. #     count:      %ld (reported: %ld)\n\
  3404. #     size:       %ld (reported: %ld)\n\
  3405. #     free count: %ld\n\
  3406. #     free size:  %ld\n\
  3407. #     busy objs:  %ld (%ld%%)\n\
  3408. #     free objs:  %ld (%ld%%)\n\
  3409. #   large blocks:\n\
  3410. #     count:      %ld\n\
  3411. #     total size: %ld (%ld%%)\n\
  3412. #     avg size:   %ld\n\
  3413. ",
  3414.               /* vm space */
  3415.               (long)baseaddr, (long)lastaddr,
  3416.               (long)lastaddr - (long)baseaddr,
  3417.               /* segments */
  3418.               _pr_gcData.lowSeg, _pr_gcData.highSeg,
  3419.               segCount, nsegs,
  3420.               segSize, reportedSegSpace,
  3421.               freeCount,
  3422.               freeSize,
  3423.               _pr_gcData.busyMemory,
  3424.               (_pr_gcData.busyMemory * 100 / reportedSegSpace),
  3425.               _pr_gcData.freeMemory,
  3426.               (_pr_gcData.freeMemory * 100 / reportedSegSpace),
  3427.               /* large blocks */
  3428.               largeCount,
  3429.               largeSize, (largeSize * 100 / reportedSegSpace),
  3430.               (largeCount ? largeSize / largeCount : 0)
  3431.               );
  3432.     UNLOCK_GC();
  3433.     fprintf(stderr, msg);
  3434.     OutputDebugString(msg);
  3435.     PR_smprintf_free(msg);
  3436. #ifdef GC_STATS
  3437.     PR_PrintGCAllocStats();
  3438. #endif
  3439. }
  3440. #endif
  3441.  
  3442. PR_IMPLEMENT(void)
  3443. PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed)
  3444. {
  3445.     FILE *out;
  3446.     OutputDebugString(msg);
  3447.     out = fopen(filename, "a");
  3448.     if (!out) {
  3449.     char buf[64];
  3450.     PR_ASSERT(strlen(filename) < sizeof(buf) - 16);
  3451.     PR_snprintf(buf, sizeof(buf), "Can't open \"%s\"\n",
  3452.             filename);
  3453.     OutputDebugString(buf);
  3454.     }
  3455.     else
  3456.     {
  3457.     struct tm *newtime;
  3458.     time_t aclock;
  3459.     int i;
  3460.  
  3461.     time(&aclock);
  3462.     newtime = localtime(&aclock);
  3463.     fprintf(out, "%s on %s\n", msg, asctime(newtime));  /* Print current time */
  3464.     dump(out, detailed);
  3465.     fprintf(out, "\n\n");
  3466.     for (i = 0; i < 80; i++)
  3467.         fprintf(out, "=");
  3468.     fprintf(out, "\n\n");
  3469.     fclose(out);
  3470.     }
  3471.     OutputDebugString(" done\n");
  3472. }
  3473.  
  3474.