mozilla/nsprpub/lib/msgc/src/prmsgc.c

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