/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is the Netscape Portable Runtime (NSPR).
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1998-2000
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

#include <string.h>
#include <stddef.h>
#include <stdarg.h>
#include <time.h>

#ifdef WIN32
#include <windef.h>
#include <winbase.h>
#endif

#include "prclist.h"
#include "prbit.h"

#include "prtypes.h"
#include "prenv.h"
#include "prgc.h"
#include "prthread.h"
#include "prlog.h"
#include "prlong.h"
#include "prinrval.h"
#include "prprf.h"
#include "gcint.h"

#include "private/pprthred.h"

typedef void (*PRFileDumper)(FILE *out, PRBool detailed);

PR_EXTERN(void)
PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed);

/*
** Mark&sweep garbage collector. Supports objects that require
** finalization, objects that can have a single weak link, and special
** objects that require care during sweeping.
*/

PRLogModuleInfo *_pr_msgc_lm;
PRLogModuleInfo* GC;

static PRInt32 _pr_pageShift;
static PRInt32 _pr_pageSize;

#ifdef DEBUG
#define GCMETER
#endif
#ifdef DEBUG_jwz
# undef GCMETER
#endif /* 1 */

#ifdef GCMETER
#define METER(x) x
#else
#define METER(x)
#endif

/*
** Make this constant bigger to reduce the amount of recursion during
** garbage collection.
*/
#define MAX_SCAN_Q    100L

#if defined(XP_PC) && !defined(WIN32)
#define MAX_SEGS            400L
#define MAX_SEGMENT_SIZE    (65536L - 4096L)
#define SEGMENT_SIZE        (65536L - 4096L)
#define MAX_ALLOC_SIZE      (65536L - 4096L)
#else
#define MAX_SEGS                    400L
#define MAX_SEGMENT_SIZE            (2L * 256L * 1024L)
#define SEGMENT_SIZE                (1L * 256L * 1024L)
#define MAX_ALLOC_SIZE              (4L * 1024L * 1024L)
#endif  

/* 
 * The highest value that can fit into a signed integer. This
 * is used to prevent overflow of allocation size in alloc routines.
 */
 
#define MAX_INT ((1UL << (PR_BITS_PER_INT - 1)) - 1)

/* 
 * On 32-bit machines, only 22 bits are used in the cibx integer to
 * store size since 8 bits of the integer are used to store type, and
 * of the remainder, 2 are user defined. Max allocation size = 2^22 -1
 */

#define MAX_ALLOC ( (1L << (PR_BYTES_PER_WORD_LOG2 + WORDS_BITS )) -1)

/* The minimum percentage of free heap space after a collection. If
   the amount of free space doesn't meet this criteria then we will
   attempt to grow the heap */
#define MIN_FREE_THRESHOLD_AFTER_GC 20L

static PRInt32 segmentSize = SEGMENT_SIZE;

static PRInt32 collectorCleanupNeeded;

#ifdef GCMETER
PRUint32 _pr_gcMeter;

#define _GC_METER_STATS         0x01L
#define _GC_METER_GROWTH        0x02L
#define _GC_METER_FREE_LIST     0x04L
#endif

/************************************************************************/

#define LINEAR_BIN_EXPONENT 5
#define NUM_LINEAR_BINS ((PRUint32)1 << LINEAR_BIN_EXPONENT)
#define FIRST_LOG_BIN (NUM_LINEAR_BINS - LINEAR_BIN_EXPONENT)

/* Each free list bin holds a chunk of memory sized from
   2^n to (2^(n+1))-1 inclusive. */
#define NUM_BINS        (FIRST_LOG_BIN + 32)

/*
 * Find the bin number for a given size (in bytes). This does not round up as
 * values from 2^n to (2^(n+1))-1 share the same bin.
 */
#define InlineBinNumber(_bin,_bytes)  \
{  \
    PRUint32 _t, _n = (PRUint32) _bytes / 4;  \
    if (_n < NUM_LINEAR_BINS) {  \
        _bin = _n;  \
    } else {  \
        _bin = FIRST_LOG_BIN;  \
        if ((_t = (_n >> 16)) != 0) { _bin += 16; _n = _t; }  \
        if ((_t = (_n >> 8)) != 0)  { _bin += 8; _n = _t; }  \
        if ((_t = (_n >> 4)) != 0)  { _bin += 4; _n = _t; }  \
        if ((_t = (_n >> 2)) != 0) { _bin += 2; _n = _t; }  \
        if ((_n >> 1) != 0) _bin++;  \
    }  \
}

#define BIG_ALLOC       16384L

#define MIN_FREE_CHUNK_BYTES    ((PRInt32)sizeof(GCFreeChunk))

/* Note: fix code in PR_AllocMemory if you change the size of GCFreeChunk
   so that it zeros the right number of words */
typedef struct GCFreeChunk {
    struct GCFreeChunk *next;
    struct GCSeg *segment;
    PRInt32 chunkSize;
} GCFreeChunk;

typedef struct GCSegInfo {
    struct GCSegInfo *next;
    char *base;
    char *limit;
    PRWord *hbits;
    int fromMalloc;
} GCSegInfo;
    
typedef struct GCSeg {
    char *base;
    char *limit;
    PRWord *hbits;
    GCSegInfo *info;
} GCSeg;

#ifdef GCMETER
typedef struct GCMeter {
    PRInt32 allocBytes;
    PRInt32 wastedBytes;
    PRInt32 numFreeChunks;
    PRInt32 skippedFreeChunks;
} GCMeter;
static GCMeter meter;
#endif

/*
** There is one of these for each segment of GC'able memory.
*/
static GCSeg segs[MAX_SEGS];
static GCSegInfo *freeSegs;
static GCSeg* lastInHeap;
static int nsegs;

static GCFreeChunk *bins[NUM_BINS];
static PRInt32 minBin;
static PRInt32 maxBin;

/*
** Scan Q used to avoid deep recursion when scanning live objects for
** heap pointers
*/
typedef struct GCScanQStr {
    PRWord *q[MAX_SCAN_Q];
    int queued;
} GCScanQ;

static GCScanQ *pScanQ;

#ifdef GCMETER
PRInt32 _pr_maxScanDepth;
PRInt32 _pr_scanDepth;
#endif

/*
** Keeps track of the number of bytes allocated via the BigAlloc() 
** allocator.  When the number of bytes allocated, exceeds the 
** BIG_ALLOC_GC_SIZE, then a GC will occur before the next allocation
** is done...
*/
#define BIG_ALLOC_GC_SIZE       (4*SEGMENT_SIZE)
static PRWord bigAllocBytes = 0;

/*
** There is one GC header word in front of each GC allocated object.  We
** use it to contain information about the object (what TYPEIX to use for
** scanning it, how big it is, it's mark status, and if it's a root).
*/
#define TYPEIX_BITS    8L
#define WORDS_BITS    20L
#define MAX_CBS        (1L << GC_TYPEIX_BITS)
#define MAX_WORDS    (1L << GC_WORDS_BITS)
#define TYPEIX_SHIFT    24L
#define MAX_TYPEIX    ((1L << TYPEIX_BITS) - 1L)
#define TYPEIX_MASK    PR_BITMASK(TYPEIX_BITS)
#define WORDS_SHIFT    2L
#define WORDS_MASK    PR_BITMASK(WORDS_BITS)
#define MARK_BIT    1L
#define FINAL_BIT    2L

/* Two bits per object header are reserved for the user of the memory
   system to store information into. */
#define GC_USER_BITS_SHIFT 22L
#define GC_USER_BITS    0x00c00000L

#define MAKE_HEADER(_cbix,_words)              \
    ((PRWord) (((unsigned long)(_cbix) << TYPEIX_SHIFT) \
         | ((unsigned long)(_words) << WORDS_SHIFT)))

#define GET_TYPEIX(_h) \
    (((PRUword)(_h) >> TYPEIX_SHIFT) & 0xff)

#define MARK(_sp,_p) \
    (((PRWord *)(_p))[0] |= MARK_BIT)
#define IS_MARKED(_sp,_p) \
    (((PRWord *)(_p))[0] & MARK_BIT)
#define OBJ_BYTES(_h) \
    (((PRInt32) (_h) & 0x003ffffcL) << (PR_BYTES_PER_WORD_LOG2-2L))

#define GC_GET_USER_BITS(_h) (((_h) & GC_USER_BITS) >> GC_USER_BITS_SHIFT)

/************************************************************************/

/*
** Mark the start of an object in a segment. Note that we mark the header
** word (which we always have), not the data word (which we may not have
** for empty objects).
** XXX tune: put subtract of _sp->base into _sp->hbits pointer?
*/
#define SET_HBIT(_sp,_ph) \
    SET_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))

#define CLEAR_HBIT(_sp,_ph) \
    CLEAR_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))

#define IS_HBIT(_sp,_ph) \
    TEST_BIT((_sp)->hbits, (((PRWord*)(_ph)) - ((PRWord*) (_sp)->base)))

/*
** Given a pointer into this segment, back it up until we are at the
** start of the object the pointer points into. Each heap segment has a
** bitmap that has one bit for each word of the objects it contains.  The
** bit's are set for the firstword of an object, and clear for it's other
** words.
*/
static PRWord *FindObject(GCSeg *sp, PRWord *p)
{
    PRWord *base;
    
    /* Align p to it's proper boundary before we start fiddling with it */
    p = (PRWord*) ((PRWord)p & ~(PR_BYTES_PER_WORD-1L));

    base = (PRWord *) sp->base;
    do {
    if (IS_HBIT(sp, p)) {
        return (p);
    }
    p--;
    } while ( p >= base );

    /* Heap is corrupted! */
    _GCTRACE(GC_TRACE, ("ERROR: The heap is corrupted!!! aborting now!"));
    abort();
    return NULL;
}

/************************************************************************/
#if !defined(XP_PC) || defined(XP_OS2)
#define OutputDebugString(msg)
#endif 

#define IN_SEGMENT(_sp, _p)             \
    ((((char *)(_p)) >= (_sp)->base) &&    \
     (((char *)(_p)) < (_sp)->limit))

static GCSeg *InHeap(void *p)
{
    GCSeg *sp, *esp;

    if (lastInHeap && IN_SEGMENT(lastInHeap, p)) {
    return lastInHeap;
    }

    sp = segs;
    esp = segs + nsegs;
    for (; sp < esp; sp++) {
    if (IN_SEGMENT(sp, p)) {
        lastInHeap = sp;
        return sp;
    }
    }
    return 0;
}

/*
** Grow the heap by allocating another segment. Fudge the requestedSize
** value to try to pre-account for the HBITS.
*/
static GCSeg* DoGrowHeap(PRInt32 requestedSize, PRBool exactly)
{
    GCSeg *sp;
    GCSegInfo *segInfo;
    GCFreeChunk *cp;
    char *base;
    PRWord *hbits;
    PRInt32 nhbytes, nhbits;
    PRUint32 allocSize;

    if (nsegs == MAX_SEGS) {
    /* No room for more segments */
    return 0;
    }

    segInfo = (GCSegInfo*) PR_MALLOC(sizeof(GCSegInfo));
#ifdef DEBUG
    {
    char str[256];
    sprintf(str, "[1] Allocated %ld bytes at %p\n",
        (long) sizeof(GCSegInfo), segInfo);
    OutputDebugString(str);
    }
#endif
    if (!segInfo) {
    return 0;
    }

    /* Get more memory from the OS */
    if (exactly) {
    allocSize = requestedSize;
    base = (char *) PR_MALLOC(requestedSize);
    } else {
    allocSize = requestedSize;
    allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
    allocSize <<= _pr_pageShift;
    base = (char*)_MD_GrowGCHeap(&allocSize);
    }
    if (!base) {
    PR_DELETE(segInfo);
    return 0;
    }

    nhbits = (PRInt32)(
        (allocSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2);
    nhbytes = ((nhbits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
    * sizeof(PRWord);

    /* Get bitmap memory from malloc heap */
    hbits = (PRWord *) PR_CALLOC((PRUint32)nhbytes);
    if (!hbits) {
    /* Loser! */
    PR_DELETE(segInfo);
    if (exactly) {
        PR_DELETE(base);
    } else {
      /* XXX do something about this */
      /* _MD_FreeGCSegment(base, allocSize); */
    }
    return 0;
    }

    /*
    ** Setup new segment.
    */
    sp = &segs[nsegs++];
    segInfo->base = sp->base = base;
    segInfo->limit = sp->limit = base + allocSize;
    segInfo->hbits = sp->hbits = hbits;
    sp->info = segInfo;
    segInfo->fromMalloc = exactly;
    memset(base, 0, allocSize);

#ifdef GCMETER
    if (_pr_gcMeter & _GC_METER_GROWTH) {
        fprintf(stderr, "[GC: new segment base=%p size=%ld]\n",
                sp->base, (long) allocSize);
    }
#endif    

    _pr_gcData.allocMemory += allocSize;
    _pr_gcData.freeMemory  += allocSize;

    if (!exactly) {
    PRInt32 bin;

        /* Put free memory into a freelist bin */
        cp = (GCFreeChunk *) base;
        cp->segment = sp;
        cp->chunkSize = allocSize;
        InlineBinNumber(bin, allocSize)
        cp->next = bins[bin];
        bins[bin] = cp;
    if (bin < minBin) minBin = bin;
    if (bin > maxBin) maxBin = bin;
    } else {
        /*
        ** When exactly allocating the entire segment is given over to a
        ** single object to prevent fragmentation
        */
    }

    if (!_pr_gcData.lowSeg) {
    _pr_gcData.lowSeg  = (PRWord*) sp->base;
    _pr_gcData.highSeg = (PRWord*) sp->limit;
    } else {
    if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
        _pr_gcData.lowSeg = (PRWord*) sp->base;
    }
    if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
        _pr_gcData.highSeg = (PRWord*) sp->limit;
    }
    }

    /* 
    ** Get rid of the GC pointer in case it shows up in some uninitialized
    ** local stack variable later (while scanning the C stack looking for
    ** roots).
    */ 
    memset(&base, 0, sizeof(base));  /* optimizers beware */

    PR_LOG(_pr_msgc_lm, PR_LOG_WARNING, ("grow heap: total gc memory now %d",
                      _pr_gcData.allocMemory));

    return sp;
}

#ifdef USE_EXTEND_HEAP
static PRBool ExtendHeap(PRInt32 requestedSize) {
  GCSeg* sp;
  PRUint32 allocSize;
  PRInt32 oldSize, newSize;
  PRInt32 newHBits, newHBytes;
  PRInt32 oldHBits, oldHBytes;
  PRWord* hbits;
  GCFreeChunk* cp;
  PRInt32 bin;

  /* Can't extend nothing */
  if (nsegs == 0) return PR_FALSE;

  /* Round up requested size to the size of a page */
  allocSize = (PRUint32) requestedSize;
  allocSize = (allocSize + _pr_pageSize - 1L) >> _pr_pageShift;
  allocSize <<= _pr_pageShift;

  /* Malloc some memory for the new hbits array */
  sp = segs;
  oldSize = sp->limit - sp->base;
  newSize = oldSize + allocSize;
  newHBits = (newSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
  newHBytes = ((newHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
    * sizeof(PRWord);
  hbits = (PRWord*) PR_MALLOC(newHBytes);
  if (0 == hbits) return PR_FALSE;

  /* Attempt to extend the last segment by the desired amount */
  if (_MD_ExtendGCHeap(sp->base, oldSize, newSize)) {
    oldHBits = (oldSize + PR_BYTES_PER_WORD - 1L) >> PR_BYTES_PER_WORD_LOG2;
    oldHBytes = ((oldHBits + PR_BITS_PER_WORD - 1L) >> PR_BITS_PER_WORD_LOG2)
      * sizeof(PRWord);

    /* Copy hbits from old memory into new memory */
    memset(hbits, 0, newHBytes);
    memcpy(hbits, sp->hbits, oldHBytes);
    PR_DELETE(sp->hbits);
    memset(sp->base + oldSize, 0, allocSize);

    /* Adjust segment state */
    sp->limit += allocSize;
    sp->hbits = hbits;
    sp->info->limit = sp->limit;
    sp->info->hbits = hbits;

    /* Put free memory into a freelist bin */
    cp = (GCFreeChunk *) (sp->base + oldSize);
    cp->segment = sp;
    cp->chunkSize = allocSize;
    InlineBinNumber(bin, allocSize)
    cp->next = bins[bin];
    bins[bin] = cp;
    if (bin < minBin) minBin = bin;
    if (bin > maxBin) maxBin = bin;

    /* Prevent a pointer that points to the free memory from showing
       up on the call stack later on */
    memset(&cp, 0, sizeof(cp));

    /* Update heap brackets and counters */
    if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
      _pr_gcData.highSeg = (PRWord*) sp->limit;
    }
    _pr_gcData.allocMemory += allocSize;
    _pr_gcData.freeMemory  += allocSize;

    return PR_TRUE;
  }
  PR_DELETE(hbits);
  return PR_FALSE;
}
#endif /* USE_EXTEND_HEAP */

static GCSeg *GrowHeapExactly(PRInt32 requestedSize)
{
    GCSeg *sp = DoGrowHeap(requestedSize, PR_TRUE);
    return sp;
}

static PRBool GrowHeap(PRInt32 requestedSize)
{
  void *p;
#ifdef USE_EXTEND_HEAP
  if (ExtendHeap(requestedSize)) {
    return PR_TRUE;
  }
#endif
  p = DoGrowHeap(requestedSize, PR_FALSE);
  return (p != NULL ? PR_TRUE : PR_FALSE);
}

/*
** Release a segment when it is entirely free.
*/
static void ShrinkGCHeap(GCSeg *sp)
{
#ifdef GCMETER
    if (_pr_gcMeter & _GC_METER_GROWTH) {
        fprintf(stderr, "[GC: free segment base=%p size=%ld]\n",
                sp->base, (long) (sp->limit - sp->base));
    }
#endif    

    /*
     * Put segment onto free seginfo list (we can't call free right now
     * because we have the GC lock and all of the other threads are
     * suspended; if one of them has the malloc lock we would deadlock)
     */
    sp->info->next = freeSegs;
    freeSegs = sp->info;
    collectorCleanupNeeded = 1;
    _pr_gcData.allocMemory -= sp->limit - sp->base;
    if (sp == lastInHeap) lastInHeap = 0;

    /* Squish out disappearing segment from segment table */
    --nsegs;
    if ((sp - segs) != nsegs) {
        *sp = segs[nsegs];
    } else {
        sp->base = 0;
        sp->limit = 0;
        sp->hbits = 0;
    sp->info = 0;
    }

    /* Recalculate the lowSeg and highSeg values */
    _pr_gcData.lowSeg  = (PRWord*) segs[0].base;
    _pr_gcData.highSeg = (PRWord*) segs[0].limit;
    for (sp = segs; sp < &segs[nsegs]; sp++) {
    if ((PRWord*)sp->base < _pr_gcData.lowSeg) {
        _pr_gcData.lowSeg = (PRWord*) sp->base;
    }
    if ((PRWord*)sp->limit > _pr_gcData.highSeg) {
        _pr_gcData.highSeg = (PRWord*) sp->limit;
    }
    }
}

static void FreeSegments(void)
{
    GCSegInfo *si;

    while (0 != freeSegs) {
    LOCK_GC();
    si = freeSegs;
    if (si) {
        freeSegs = si->next;
    }
    UNLOCK_GC();

    if (!si) {
        break;
    }
    PR_DELETE(si->base);
    PR_DELETE(si->hbits);
    PR_DELETE(si);
    }
}

/************************************************************************/

void ScanScanQ(GCScanQ *iscan)
{
    PRWord *p;
    PRWord **pp;
    PRWord **epp;
    GCScanQ nextQ, *scan, *next, *temp;
    CollectorType *ct;

    if (!iscan->queued) return;

    _GCTRACE(GC_MARK, ("begin scanQ @ 0x%x (%d)", iscan, iscan->queued));
    scan = iscan;
    next = &nextQ;
    while (scan->queued) {
	_GCTRACE(GC_MARK, ("continue scanQ @ 0x%x (%d)", scan, scan->queued));
    /*
     * Set pointer to current scanQ so that _pr_gcData.livePointer
     * can find it.
     */
    pScanQ = next;
    next->queued = 0;

    /* Now scan the scan Q */
    pp = scan->q;
    epp = &scan->q[scan->queued];
    scan->queued = 0;
    while (pp < epp) {
        p = *pp++;
        ct = &_pr_collectorTypes[GET_TYPEIX(p[0])];
        PR_ASSERT(0 != ct->gctype.scan);
        /* Scan object ... */
        (*ct->gctype.scan)(p + 1);
    }

    /* Exchange pointers so that we scan next */
    temp = scan;
    scan = next;
    next = temp;
    }

    pScanQ = iscan;
    PR_ASSERT(nextQ.queued == 0);
    PR_ASSERT(iscan->queued == 0);
}

/*
** Called during root finding step to identify "root" pointers into the
** GC heap. First validate if it is a real heap pointer and then mark the
** object being pointed to and add it to the scan Q for eventual
** scanning.
*/
static void PR_CALLBACK ProcessRootBlock(void **base, PRInt32 count)
{
    GCSeg *sp;
    PRWord *p0, *p, h, tix, *low, *high, *segBase;
    CollectorType *ct;
#ifdef DEBUG
    void **base0 = base;
#endif

    low = _pr_gcData.lowSeg;
    high = _pr_gcData.highSeg;
    while (--count >= 0) {
        p0 = (PRWord*) *base++;
        if (p0 < low) continue;                  /* below gc heap */
        if (p0 >= high) continue;                /* above gc heap */
        /* NOTE: inline expansion of InHeap */
        /* Find segment */
    sp = lastInHeap;
        if (!sp || !IN_SEGMENT(sp,p0)) {
            GCSeg *esp;
            sp = segs;
        esp = segs + nsegs;
            for (; sp < esp; sp++) {
                if (IN_SEGMENT(sp, p0)) {
                    lastInHeap = sp;
                    goto find_object;
                }
            }
            continue;
        }

      find_object:
        /* NOTE: Inline expansion of FindObject */
        /* Align p to it's proper boundary before we start fiddling with it */
        p = (PRWord*) ((PRWord)p0 & ~(PR_BYTES_PER_WORD-1L));
        segBase = (PRWord *) sp->base;
        do {
            if (IS_HBIT(sp, p)) {
                goto winner;
            }
            p--;
        } while (p >= segBase);

        /*
        ** We have a pointer into the heap, but it has no header
        ** bit. This means that somehow the very first object in the heap
        ** doesn't have a header. This is impossible so when debugging
        ** lets abort.
        */
#ifdef DEBUG
        PR_Abort();
#endif

      winner:
        h = p[0];
        if ((h & MARK_BIT) == 0) {
#ifdef DEBUG
            _GCTRACE(GC_ROOTS,
            ("root 0x%p (%d) base0=%p off=%d",
             p, OBJ_BYTES(h), base0, (base-1) - base0));
#endif

            /* Mark the root we just found */
            p[0] = h | MARK_BIT;

            /*
         * See if object we just found needs scanning. It must
         * have a scan function to be placed on the scanQ.
         */
            tix = (PRWord)GET_TYPEIX(h);
        ct = &_pr_collectorTypes[tix];
        if (0 == ct->gctype.scan) {
        continue;
        }

            /*
            ** Put a pointer onto the scan Q. We use the scan Q to avoid
            ** deep recursion on the C call stack. Objects are added to
            ** the scan Q until the scan Q fills up. At that point we
            ** make a call to ScanScanQ which proceeds to scan each of
            ** the objects in the Q. This limits the recursion level by a
            ** large amount though the stack frames get larger to hold
            ** the GCScanQ's.
            */
            pScanQ->q[pScanQ->queued++] = p;
            if (pScanQ->queued == MAX_SCAN_Q) {
                METER(_pr_scanDepth++);
                ScanScanQ(pScanQ);
            }
        }
    }
}

static void PR_CALLBACK ProcessRootPointer(void *ptr)
{
  PRWord *p0, *p, h, tix, *segBase;
  GCSeg* sp;
  CollectorType *ct;

  p0 = (PRWord*) ptr;

  if (p0 < _pr_gcData.lowSeg) return;                  /* below gc heap */
  if (p0 >= _pr_gcData.highSeg) return;                /* above gc heap */

  /* NOTE: inline expansion of InHeap */
  /* Find segment */
  sp = lastInHeap;
  if (!sp || !IN_SEGMENT(sp,p0)) {
    GCSeg *esp;
    sp = segs;
    esp = segs + nsegs;
    for (; sp < esp; sp++) {
      if (IN_SEGMENT(sp, p0)) {
    lastInHeap = sp;
    goto find_object;
      }
    }
    return;
  }

 find_object:
  /* NOTE: Inline expansion of FindObject */
  /* Align p to it's proper boundary before we start fiddling with it */
    p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
    segBase = (PRWord *) sp->base;
    do {
      if (IS_HBIT(sp, p)) {
    goto winner;
      }
      p--;
    } while (p >= segBase);

    /*
    ** We have a pointer into the heap, but it has no header
    ** bit. This means that somehow the very first object in the heap
    ** doesn't have a header. This is impossible so when debugging
    ** lets abort.
    */
#ifdef DEBUG
    PR_Abort();
#endif

 winner:
  h = p[0];
  if ((h & MARK_BIT) == 0) {
#ifdef DEBUG
    _GCTRACE(GC_ROOTS, ("root 0x%p (%d)", p, OBJ_BYTES(h)));
#endif

    /* Mark the root we just found */
    p[0] = h | MARK_BIT;

    /*
     * See if object we just found needs scanning. It must
     * have a scan function to be placed on the scanQ.
     */
    tix = (PRWord)GET_TYPEIX(h);
    ct = &_pr_collectorTypes[tix];
    if (0 == ct->gctype.scan) {
      return;
    }

    /*
    ** Put a pointer onto the scan Q. We use the scan Q to avoid
    ** deep recursion on the C call stack. Objects are added to
    ** the scan Q until the scan Q fills up. At that point we
    ** make a call to ScanScanQ which proceeds to scan each of
    ** the objects in the Q. This limits the recursion level by a
    ** large amount though the stack frames get larger to hold
    ** the GCScanQ's.
    */
    pScanQ->q[pScanQ->queued++] = p;
    if (pScanQ->queued == MAX_SCAN_Q) {
      METER(_pr_scanDepth++);
      ScanScanQ(pScanQ);
    }
  }
}

/************************************************************************/

/*
** Empty the freelist for each segment. This is done to make sure that
** the root finding step works properly (otherwise, if we had a pointer
** into a free section, we might not find its header word and abort in
** FindObject)
*/
static void EmptyFreelists(void)
{
    GCFreeChunk *cp;
    GCFreeChunk *next;
    GCSeg *sp;
    PRWord *p;
    PRInt32 chunkSize;
    PRInt32 bin;

    /*
    ** Run over the freelist and make all of the free chunks look like
    ** object debris.
    */
    for (bin = 0; bin <= NUM_BINS-1; bin++) {
        cp = bins[bin];
        while (cp) {
            next = cp->next;
            sp = cp->segment;
            chunkSize = cp->chunkSize >> BYTES_PER_WORD_LOG2;
            p = (PRWord*) cp;
            PR_ASSERT(chunkSize != 0);
            p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
            SET_HBIT(sp, p);
            cp = next;
        }
        bins[bin] = 0;
    }
    minBin = NUM_BINS - 1;
    maxBin = 0;
}

typedef struct GCBlockEnd {
    PRInt32	check;
#ifdef GC_CHECK
    PRInt32	requestedBytes;
#endif
#ifdef GC_STATS
    PRInt32	bin;
    PRInt64	allocTime; 
#endif
#ifdef GC_TRACEROOTS
    PRInt32	traceGeneration;	
#endif
} GCBlockEnd;

#define PR_BLOCK_END	0xDEADBEEF

/************************************************************************/

#ifdef GC_STATS

typedef struct GCStat {
    PRInt32	nallocs;
    double	allocTime;
    double	allocTimeVariance;
    PRInt32	nfrees;
    double	lifetime;
    double	lifetimeVariance;
} GCStat;

#define GCSTAT_BINS	NUM_BINS

GCStat gcstats[GCSTAT_BINS];

#define GCLTFREQ_BINS	NUM_BINS

PRInt32 gcltfreq[GCSTAT_BINS][GCLTFREQ_BINS];

#include <math.h>

static char* 
pr_GetSizeString(PRUint32 size)
{
    char* sizeStr;
    if (size < 1024)
	sizeStr = PR_smprintf("<= %ld", size);
    else if (size < 1024 * 1024)
	sizeStr = PR_smprintf("<= %ldk", size / 1024);
    else 
	sizeStr = PR_smprintf("<= %ldM", size / (1024 * 1024));
    return sizeStr;
}

static void
pr_FreeSizeString(char *sizestr)
{
	PR_smprintf_free(sizestr);
}


static void
pr_PrintGCAllocStats(FILE* out)
{
    PRInt32 i, j;
    _PR_DebugPrint(out, "\n--Allocation-Stats-----------------------------------------------------------");
    _PR_DebugPrint(out, "\n--Obj-Size----Count-----Avg-Alloc-Time-----------Avg-Lifetime---------%%Freed-\n");
    for (i = 0; i < GCSTAT_BINS; i++) {
	GCStat stat = gcstats[i];
	double allocTimeMean = 0.0, allocTimeVariance = 0.0, lifetimeMean = 0.0, lifetimeVariance = 0.0;
	PRUint32 maxSize = (1 << i);
	char* sizeStr;
	if (stat.nallocs != 0.0) {
	    allocTimeMean = stat.allocTime / stat.nallocs;
	    allocTimeVariance = fabs(stat.allocTimeVariance / stat.nallocs - allocTimeMean * allocTimeMean);
	}
	if (stat.nfrees != 0.0) {
	    lifetimeMean = stat.lifetime / stat.nfrees;
	    lifetimeVariance = fabs(stat.lifetimeVariance / stat.nfrees - lifetimeMean * lifetimeMean);
	}
	sizeStr = pr_GetSizeString(maxSize);
	_PR_DebugPrint(out, "%10s %8lu %10.3f +- %10.3f %10.3f +- %10.3f (%2ld%%)\n",
		       sizeStr, stat.nallocs,
		       allocTimeMean, sqrt(allocTimeVariance),
		       lifetimeMean, sqrt(lifetimeVariance),
		       (stat.nallocs ? (stat.nfrees * 100 / stat.nallocs) : 0));
	pr_FreeSizeString(sizeStr);
    }
    _PR_DebugPrint(out, "--Lifetime-Frequency-Counts----------------------------------------------------\n");
    _PR_DebugPrint(out, "size\\cnt");
    for (j = 0; j < GCLTFREQ_BINS; j++) {
	_PR_DebugPrint(out, "\t%lu", j);
    }
    _PR_DebugPrint(out, "\n");
    for (i = 0; i < GCSTAT_BINS; i++) {
	PRInt32* freqs = gcltfreq[i];
	_PR_DebugPrint(out, "%lu", (1 << i));
	for (j = 0; j < GCLTFREQ_BINS; j++) {
	    _PR_DebugPrint(out, "\t%lu", freqs[j]);
	}
	_PR_DebugPrint(out, "\n");
    }
    _PR_DebugPrint(out, "-------------------------------------------------------------------------------\n");
}

PR_PUBLIC_API(void)
PR_PrintGCAllocStats(void)
{
    pr_PrintGCAllocStats(stderr);
}

#endif /* GC_STATS */

/************************************************************************/

/*
** Sweep a segment, cleaning up all of the debris. Coallese the debris
** into GCFreeChunk's which are added to the freelist bins.
*/
static PRBool SweepSegment(GCSeg *sp)
{
    PRWord h, tix;
    PRWord *p;
    PRWord *np;
    PRWord *limit;
    GCFreeChunk *cp;
    PRInt32 bytes, chunkSize, segmentSize, totalFree;
    CollectorType *ct;
    PRInt32 bin;

    /*
    ** Now scan over the segment's memory in memory order, coallescing
    ** all of the debris into a FreeChunk list.
    */
    totalFree = 0;
    segmentSize = sp->limit - sp->base;
    p = (PRWord *) sp->base;
    limit = (PRWord *) sp->limit;
    PR_ASSERT(segmentSize > 0);
    while (p < limit) {
    chunkSize = 0;
    cp = (GCFreeChunk *) p;

    /* Attempt to coallesce any neighboring free objects */
    for (;;) {
        PR_ASSERT(IS_HBIT(sp, p) != 0);
        h = p[0];
        bytes = OBJ_BYTES(h);
        PR_ASSERT(bytes != 0);
        np = (PRWord *) ((char *)p + bytes);
        tix = (PRWord)GET_TYPEIX(h);
        if ((h & MARK_BIT) && (tix != FREE_MEMORY_TYPEIX)) {
#ifdef DEBUG
        if (tix != FREE_MEMORY_TYPEIX) {
            PR_ASSERT(_pr_collectorTypes[tix].flags != 0);
        }
#endif
        p[0] = h & ~(MARK_BIT|FINAL_BIT);
		_GCTRACE(GC_SWEEP, ("busy 0x%x (%d)", p, bytes));
		break;
	    }
	    _GCTRACE(GC_SWEEP, ("free 0x%x (%d)", p, bytes));

	    /* Found a free object */
#ifdef GC_STATS
	    {
		PRInt32 userSize = bytes - sizeof(GCBlockEnd);
		GCBlockEnd* end = (GCBlockEnd*)((char*)p + userSize);
		if (userSize >= 0 && end->check == PR_BLOCK_END) {
		    PRInt64 now = PR_Now();
		    double nowd, delta;
		    PRInt32 freq;
		    LL_L2D(nowd, now);
		    delta = nowd - end->allocTime;
		    gcstats[end->bin].nfrees++;
		    gcstats[end->bin].lifetime += delta;
		    gcstats[end->bin].lifetimeVariance += delta * delta;

		    InlineBinNumber(freq, delta);
		    gcltfreq[end->bin][freq]++;

		    end->check = 0;
		}
	    }
#endif
        CLEAR_HBIT(sp, p);
        ct = &_pr_collectorTypes[tix];
        if (0 != ct->gctype.free) {
                (*ct->gctype.free)(p + 1);
            }
        chunkSize = chunkSize + bytes;
        if (np == limit) {
        /* Found the end of heap */
        break;
        }
        PR_ASSERT(np < limit);
        p = np;
    }

    if (chunkSize) {
        _GCTRACE(GC_SWEEP, ("free chunk 0x%p to 0x%p (%d)",
                   cp, (char*)cp + chunkSize - 1, chunkSize));
        if (chunkSize < MIN_FREE_CHUNK_BYTES) {
        /* Lost a tiny fragment until (maybe) next time */
                METER(meter.wastedBytes += chunkSize);
        p = (PRWord *) cp;
        chunkSize >>= BYTES_PER_WORD_LOG2;
        PR_ASSERT(chunkSize != 0);
        p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, chunkSize);
        SET_HBIT(sp, p);
        } else {
                /* See if the chunk constitutes the entire segment */
                if (chunkSize == segmentSize) {
                    /* Free up the segment right now */
            if (sp->info->fromMalloc) {
                    ShrinkGCHeap(sp);
                    return PR_TRUE;
                }
                }

                /* Put free chunk into the appropriate bin */
                cp->segment = sp;
        cp->chunkSize = chunkSize;
                InlineBinNumber(bin, chunkSize)
                cp->next = bins[bin];
                bins[bin] = cp;
        if (bin < minBin) minBin = bin;
        if (bin > maxBin) maxBin = bin;

        /* Zero swept memory now */
        memset(cp+1, 0, chunkSize - sizeof(*cp));
                METER(meter.numFreeChunks++);
        totalFree += chunkSize;
        }
    }

    /* Advance to next object */
    p = np;
    }

    PR_ASSERT(totalFree <= segmentSize);

    _pr_gcData.freeMemory += totalFree;
    _pr_gcData.busyMemory += (sp->limit - sp->base) - totalFree;
    return PR_FALSE;
}

/************************************************************************/

/* This is a list of all the objects that are finalizable. This is not
   the list of objects that are awaiting finalization because they
   have been collected. */
PRCList _pr_finalizeableObjects;

/* This is the list of objects that are awaiting finalization because
   they have been collected. */
PRCList _pr_finalQueue;

/* Each object that requires finalization has one of these objects
   allocated as well. The GCFinal objects are put on the
   _pr_finalizeableObjects list until the object is collected at which
   point the GCFinal object is moved to the _pr_finalQueue */
typedef struct GCFinalStr {
    PRCList links;
    PRWord *object;
} GCFinal;

/* Find pointer to GCFinal struct from the list linkaged embedded in it */
#define FinalPtr(_qp) \
    ((GCFinal*) ((char*) (_qp) - offsetof(GCFinal,links)))

static GCFinal *AllocFinalNode(void)
{
    return PR_NEWZAP(GCFinal);
}

static void FreeFinalNode(GCFinal *node)
{
    PR_DELETE(node);
}

/*
** Prepare for finalization. At this point in the GC cycle we have
** identified all of the live objects. For each object on the
** _pr_finalizeableObjects list see if the object is alive or dead. If
** it's dead, resurrect it and move it from the _pr_finalizeableObjects
** list to the _pr_finalQueue (object's only get finalized once).
**
** Once _pr_finalizeableObjects has been processed we can finish the
** GC and free up memory and release the threading lock. After that we
** can invoke the finalization procs for each object that is on the
** _pr_finalQueue.
*/
static void PrepareFinalize(void)
{
    PRCList *qp;
    GCFinal *fp;
    PRWord h;
    PRWord *p;
    void (PR_CALLBACK *livePointer)(void *ptr);
#ifdef DEBUG
    CollectorType *ct;
#endif

    /* This must be done under the same lock that the finalizer uses */
    PR_ASSERT( GC_IS_LOCKED() );

    /* cache this ptr */
    livePointer = _pr_gcData.livePointer;

    /*
     * Pass #1: Identify objects that are to be finalized, set their
     * FINAL_BIT.
     */
    qp = _pr_finalizeableObjects.next;
    while (qp != &_pr_finalizeableObjects) {
    fp = FinalPtr(qp);
    qp = qp->next;
    h = fp->object[0];        /* Grab header word */
    if (h & MARK_BIT) {
        /* Object is already alive */
        continue;
    }

#ifdef DEBUG
    ct = &_pr_collectorTypes[GET_TYPEIX(h)];
    PR_ASSERT((0 != ct->flags) && (0 != ct->gctype.finalize));
#endif
    fp->object[0] |= FINAL_BIT;
    _GCTRACE(GC_FINAL, ("moving %p (%d) to finalQueue",
               fp->object, OBJ_BYTES(h)));
    }

    /*
     * Pass #2: For each object that is going to be finalized, move it to
     * the finalization queue and resurrect it
     */
    qp = _pr_finalizeableObjects.next;
    while (qp != &_pr_finalizeableObjects) {
    fp = FinalPtr(qp);
    qp = qp->next;
    h = fp->object[0];        /* Grab header word */
    if ((h & FINAL_BIT) == 0) {
        continue;
    }

    /* Resurrect the object and any objects it refers to */
        p = &fp->object[1];
    (*livePointer)(p);
    PR_REMOVE_LINK(&fp->links);
    PR_APPEND_LINK(&fp->links, &_pr_finalQueue);
    }
}

/*
** Scan the finalQ, marking each and every object on it live.  This is
** necessary because we might do a GC before objects that are on the
** final queue get finalized. Since there are no other references
** (otherwise they would be on the final queue), we have to scan them.
** This really only does work if we call the GC before the finalizer
** has a chance to do its job.
*/
extern void PR_CALLBACK _PR_ScanFinalQueue(void *notused)
{
    PRCList *qp;
    GCFinal *fp;
    PRWord *p;
    void ( PR_CALLBACK *livePointer)(void *ptr);

    livePointer = _pr_gcData.livePointer;
    qp = _pr_finalQueue.next;
    while (qp != &_pr_finalQueue) {
    fp = FinalPtr(qp);
	_GCTRACE(GC_FINAL, ("marking 0x%x (on final queue)", fp->object));
        p = &fp->object[1];
    (*livePointer)(p);
    qp = qp->next;
    }
}

void PR_CALLBACK FinalizerLoop(void* unused)
{
    GCFinal *fp;
    PRWord *p;
    PRWord h, tix;
    CollectorType *ct;

    LOCK_GC();
    for (;;) {
	p = 0; h = 0;		/* don't let the gc find these pointers */
    while (PR_CLIST_IS_EMPTY(&_pr_finalQueue))
        PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);

    _GCTRACE(GC_FINAL, ("begin finalization"));
    while (_pr_finalQueue.next != &_pr_finalQueue) {
        fp = FinalPtr(_pr_finalQueue.next);
        PR_REMOVE_LINK(&fp->links);
        p = fp->object;

        h = p[0];        /* Grab header word */
        tix = (PRWord)GET_TYPEIX(h);
        ct = &_pr_collectorTypes[tix];
	    _GCTRACE(GC_FINAL, ("finalize 0x%x (%d)", p, OBJ_BYTES(h)));

        /*
        ** Give up the GC lock so that other threads can allocate memory
        ** while this finalization method is running. Get it back
        ** afterwards so that the list remains thread safe.
        */
        UNLOCK_GC();
        FreeFinalNode(fp);
        PR_ASSERT(ct->gctype.finalize != 0);
        (*ct->gctype.finalize)(p + 1);
        LOCK_GC();
    }
    _GCTRACE(GC_FINAL, ("end finalization"));
    PR_Notify(_pr_gcData.lock);
    }
}

static void NotifyFinalizer(void)
{
    if (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
    PR_ASSERT( GC_IS_LOCKED() );
    PR_Notify(_pr_gcData.lock);
    }
}

void _PR_CreateFinalizer(PRThreadScope scope)
{
    if (!_pr_gcData.finalizer) {
    _pr_gcData.finalizer = PR_CreateThreadGCAble(PR_SYSTEM_THREAD,
                                        FinalizerLoop, 0,
                                        PR_PRIORITY_LOW, scope,
                                        PR_UNJOINABLE_THREAD, 0);
    
    if (_pr_gcData.finalizer == NULL)
        /* We are doomed if we can't start the finalizer */
        PR_Abort();

    }
}

void pr_FinalizeOnExit(void)
{
#ifdef DEBUG_warren
    OutputDebugString("### Doing finalize-on-exit pass\n");
#endif
    PR_ForceFinalize();
#ifdef DEBUG_warren
    OutputDebugString("### Finalize-on-exit complete. Dumping object left to memory.out\n");
    PR_DumpMemorySummary();
    PR_DumpMemory(PR_TRUE);
#endif
}

PR_IMPLEMENT(void) PR_ForceFinalize()
{
    LOCK_GC();
    NotifyFinalizer();
    while (!PR_CLIST_IS_EMPTY(&_pr_finalQueue)) {
    PR_ASSERT( GC_IS_LOCKED() );
    (void) PR_Wait(_pr_gcData.lock, PR_INTERVAL_NO_TIMEOUT);
    }
    UNLOCK_GC();

    /* XXX I don't know how to make it wait (yet) */
}

/************************************************************************/

typedef struct GCWeakStr {
    PRCList links;
    PRWord *object;
} GCWeak;

/*
** Find pointer to GCWeak struct from the list linkaged embedded in it
*/
#define WeakPtr(_qp) \
    ((GCWeak*) ((char*) (_qp) - offsetof(GCWeak,links)))

PRCList _pr_weakLinks = PR_INIT_STATIC_CLIST(&_pr_weakLinks);
PRCList _pr_freeWeakLinks = PR_INIT_STATIC_CLIST(&_pr_freeWeakLinks);

#define WEAK_FREELIST_ISEMPTY() (_pr_freeWeakLinks.next == &_pr_freeWeakLinks)

/*
 * Keep objects referred to by weak free list alive until they can be
 * freed
 */
static void PR_CALLBACK ScanWeakFreeList(void *notused) {
    PRCList *qp = _pr_freeWeakLinks.next;
    while (qp != &_pr_freeWeakLinks) {
    GCWeak *wp = WeakPtr(qp);
    qp = qp->next;
    ProcessRootPointer(wp->object);
    }
}

/*
 * Empty the list of weak objects. Note that we can't call malloc/free
 * under the cover of the GC's lock (we might deadlock), so transfer the
 * list of free objects to a local list under the cover of the lock, then
 * release the lock and free up the memory.
 */
static void EmptyWeakFreeList(void) {
    if (!WEAK_FREELIST_ISEMPTY()) {
    PRCList *qp, freeLinks;

    PR_INIT_CLIST(&freeLinks);

    /*
     * Transfer list of free weak links from the global list to a
     * local list.
     */
    LOCK_GC();
    qp = _pr_freeWeakLinks.next;
    while (qp != &_pr_freeWeakLinks) {
        GCWeak *wp = WeakPtr(qp);
        qp = qp->next;
        PR_REMOVE_LINK(&wp->links);
        PR_APPEND_LINK(&wp->links, &freeLinks);
    }
    UNLOCK_GC();

    /* Free up storage now */
    qp = freeLinks.next;
    while (qp != &freeLinks) {
        GCWeak *wp = WeakPtr(qp);
        qp = qp->next;
        PR_DELETE(wp);
    }
    }
}

/*
 * Allocate a new weak node in the weak objects list
 */
static GCWeak *AllocWeakNode(void)
{
    EmptyWeakFreeList();
    return PR_NEWZAP(GCWeak);
}

static void FreeWeakNode(GCWeak *node)
{
    PR_DELETE(node);
}

/*
 * Check the weak links for validity. Note that the list of weak links is
 * itself weak (otherwise we would keep the objects with weak links in
 * them alive forever). As we scan the list check the weak link object
 * itself and if it's not marked then remove it from the weak link list
 */
static void CheckWeakLinks(void) {
    PRCList *qp;
    GCWeak *wp;
    PRWord *p, h, tix, **weakPtrAddress;
    CollectorType *ct;
    PRUint32 offset;

    qp = _pr_weakLinks.next;
    while (qp != &_pr_weakLinks) {
    wp = WeakPtr(qp);
    qp = qp->next;
    if ((p = wp->object) != 0) {
        h = p[0];        /* Grab header word */
        if ((h & MARK_BIT) == 0) {
        /*
         * The object that has a weak link is no longer being
         * referenced; remove it from the chain and let it get
         * swept away by the GC. Transfer it to the list of
         * free weak links for later freeing.
         */
        PR_REMOVE_LINK(&wp->links);
        PR_APPEND_LINK(&wp->links, &_pr_freeWeakLinks);
        collectorCleanupNeeded = 1;
        continue;
        }
        
	    /* Examine a live object that contains weak links */
        tix = GET_TYPEIX(h);
        ct = &_pr_collectorTypes[tix];
        PR_ASSERT((ct->flags != 0) && (ct->gctype.getWeakLinkOffset != 0));
        if (0 == ct->gctype.getWeakLinkOffset) {
        /* Heap is probably corrupted */
        continue;
        }

        /* Get offset into the object of where the weak pointer is */
        offset = (*ct->gctype.getWeakLinkOffset)(p + 1);

        /* Check the weak pointer */
        weakPtrAddress = (PRWord**)((char*)(p + 1) + offset);
        p = *weakPtrAddress;
        if (p != 0) {
        h = p[-1];    /* Grab header word for pointed to object */
        if (h & MARK_BIT) {
            /* Object can't be dead */
            continue;
        }
        /* Break weak link to an object that is about to be swept */
        *weakPtrAddress = 0;
        }
    }
    }
}

/************************************************************************/

/*
** Perform a complete garbage collection
*/

extern GCLockHook *_pr_GCLockHook;

static void dogc(void)
{
    RootFinder *rf;
    GCLockHook* lhook;

    GCScanQ scanQ;
    GCSeg *sp, *esp;
    PRInt64 start, end, diff;

#if defined(GCMETER) || defined(GCTIMINGHOOK)
    start = PR_Now();
#endif

    /*
    ** Stop all of the other threads. This also promises to capture the
    ** register state of each and every thread
    */

    /* 
    ** Get all the locks that will be need during GC after SuspendAll. We 
    ** cannot make any locking/library calls after SuspendAll.
    */
    if (_pr_GCLockHook) {
        for (lhook = _pr_GCLockHook->next; lhook != _pr_GCLockHook; 
          lhook = lhook->next) {
          (*lhook->func)(PR_GCBEGIN, lhook->arg);
        }
    }

    PR_SuspendAll();

#ifdef GCMETER
    /* Reset meter info */
    if (_pr_gcMeter & _GC_METER_STATS) {
        fprintf(stderr,
                "[GCSTATS: busy:%ld skipped:%ld, alloced:%ld+wasted:%ld+free:%ld = total:%ld]\n",
                (long) _pr_gcData.busyMemory,
                (long) meter.skippedFreeChunks,
                (long) meter.allocBytes,
                (long) meter.wastedBytes,
                (long) _pr_gcData.freeMemory,
                (long) _pr_gcData.allocMemory);
    }        
    memset(&meter, 0, sizeof(meter));
#endif

    PR_LOG(_pr_msgc_lm, PR_LOG_ALWAYS, ("begin mark phase; busy=%d free=%d total=%d",
                     _pr_gcData.busyMemory, _pr_gcData.freeMemory,
                     _pr_gcData.allocMemory));

    if (_pr_beginGCHook) {
    (*_pr_beginGCHook)(_pr_beginGCHookArg);
    }

    /*
    ** Initialize scanQ to all zero's so that root finder doesn't walk
    ** over it...
    */
    memset(&scanQ, 0, sizeof(scanQ));
    pScanQ = &scanQ;

    /******************************************/
    /* MARK PHASE */

    EmptyFreelists();

    /* Find root's */
    PR_LOG(_pr_msgc_lm, PR_LOG_WARNING,
           ("begin mark phase; busy=%d free=%d total=%d",
        _pr_gcData.busyMemory, _pr_gcData.freeMemory,
            _pr_gcData.allocMemory));
    METER(_pr_scanDepth = 0);
    rf = _pr_rootFinders;
    while (rf) {
    _GCTRACE(GC_ROOTS, ("finding roots in %s", rf->name));
    (*rf->func)(rf->arg);
    rf = rf->next;
    }
    _GCTRACE(GC_ROOTS, ("done finding roots"));

    /* Scan remaining object's that need scanning */
    ScanScanQ(&scanQ);
    PR_ASSERT(pScanQ == &scanQ);
    PR_ASSERT(scanQ.queued == 0);
    METER({
    if (_pr_scanDepth > _pr_maxScanDepth) {
        _pr_maxScanDepth = _pr_scanDepth;
    }
    });

    /******************************************/
    /* FINALIZATION PHASE */

    METER(_pr_scanDepth = 0);
    PrepareFinalize();

    /* Scan any resurrected objects found during finalization */
    ScanScanQ(&scanQ);
    PR_ASSERT(pScanQ == &scanQ);
    PR_ASSERT(scanQ.queued == 0);
    METER({
    if (_pr_scanDepth > _pr_maxScanDepth) {
        _pr_maxScanDepth = _pr_scanDepth;
    }
    });
    pScanQ = 0;

    /******************************************/
    /* SWEEP PHASE */

    /*
    ** Sweep each segment clean. While we are at it, figure out which
    ** segment has the most free space and make that the current segment.
    */
    CheckWeakLinks();
    _GCTRACE(GC_SWEEP, ("begin sweep phase"));
    _pr_gcData.freeMemory = 0;
    _pr_gcData.busyMemory = 0;
    sp = segs;
    esp = sp + nsegs;
    while (sp < esp) {
        if (SweepSegment(sp)) {
            /*
            ** Segment is now free and has been replaced with a different
            ** segment object.
            */
            esp--;
            continue;
        }
        sp++;
    }

#if defined(GCMETER) || defined(GCTIMINGHOOK)
    end = PR_Now();
#endif
#ifdef GCMETER
    LL_SUB(diff, end, start);
    PR_LOG(GC, PR_LOG_ALWAYS,
	   ("done; busy=%d free=%d chunks=%d total=%d time=%lldms",
	    _pr_gcData.busyMemory, _pr_gcData.freeMemory,
	    meter.numFreeChunks, _pr_gcData.allocMemory, diff));
    if (_pr_gcMeter & _GC_METER_FREE_LIST) {
        PRIntn bin;
        fprintf(stderr, "Freelist bins:\n");
        for (bin = 0; bin < NUM_BINS; bin++) {
            GCFreeChunk *cp = bins[bin];
            while (cp != NULL) {
                fprintf(stderr, "%3d: %p %8ld\n",
                        bin, cp, (long) cp->chunkSize);
                cp = cp->next;
            }
        }
    }
#endif

    if (_pr_endGCHook) {
    (*_pr_endGCHook)(_pr_endGCHookArg);
    }

    /* clear the running total of the bytes allocated via BigAlloc() */
    bigAllocBytes = 0;

    /* And resume multi-threading */
    PR_ResumeAll();

    if (_pr_GCLockHook) {
        for (lhook = _pr_GCLockHook->prev; lhook != _pr_GCLockHook; 
          lhook = lhook->prev) {
          (*lhook->func)(PR_GCEND, lhook->arg);
        }
    }

    /* Kick finalizer */
    NotifyFinalizer();
#ifdef GCTIMINGHOOK
    if (_pr_gcData.gcTimingHook) {
	PRInt32 time;
	LL_SUB(diff, end, start);
	LL_L2I(time, diff);
	_pr_gcData.gcTimingHook(time);
    }
#endif
}

PR_IMPLEMENT(void) PR_GC(void)
{
    LOCK_GC();
    dogc();
    UNLOCK_GC();

    EmptyWeakFreeList();
}

/*******************************************************************************
 * Heap Walker
 ******************************************************************************/

/*
** This is yet another disgusting copy of the body of ProcessRootPointer
** (the other being ProcessRootBlock), but we're not leveraging a single
** function in their cases in interest of performance (avoiding the function
** call).
*/
static PRInt32 PR_CALLBACK
pr_ConservativeWalkPointer(void* ptr, PRWalkFun walkRootPointer, void* data)
{
  PRWord *p0, *p, *segBase;
  GCSeg* sp;

  p0 = (PRWord*) ptr;

  if (p0 < _pr_gcData.lowSeg) return 0;                  /* below gc heap */
  if (p0 >= _pr_gcData.highSeg) return 0;                /* above gc heap */

  /* NOTE: inline expansion of InHeap */
  /* Find segment */
  sp = lastInHeap;
  if (!sp || !IN_SEGMENT(sp,p0)) {
    GCSeg *esp;
    sp = segs;
    esp = segs + nsegs;
    for (; sp < esp; sp++) {
      if (IN_SEGMENT(sp, p0)) {
	lastInHeap = sp;
	goto find_object;
      }
    }
    return 0;
  }

  find_object:
    /* NOTE: Inline expansion of FindObject */
    /* Align p to it's proper boundary before we start fiddling with it */
    p = (PRWord*) ((PRWord)p0 & ~(BYTES_PER_WORD-1L));
    segBase = (PRWord *) sp->base;
    do {
        if (IS_HBIT(sp, p)) {
            goto winner;
        }
        p--;
    } while (p >= segBase);

    /*
    ** We have a pointer into the heap, but it has no header
    ** bit. This means that somehow the very first object in the heap
    ** doesn't have a header. This is impossible so when debugging
    ** lets abort.
    */
#ifdef DEBUG
    PR_Abort();
#endif
    return 0;

 winner:
    return walkRootPointer(p, data);
}

static PRInt32 PR_CALLBACK
pr_ConservativeWalkBlock(void **base, PRInt32 count,
			 PRWalkFun walkRootPointer, void* data)
{
    PRWord *p0;
    while (--count >= 0) {
	PRInt32 status;
        p0 = (PRWord*) *base++;
	status = pr_ConservativeWalkPointer(p0, walkRootPointer, data);
	if (status) return status;
    }
    return 0;
}

/******************************************************************************/

typedef void (*WalkObject_t)(FILE *out, GCType* tp, PRWord *obj,
			     size_t bytes, PRBool detailed);
typedef void (*WalkUnknown_t)(FILE *out, GCType* tp, PRWord tix, PRWord *p,
			      size_t bytes, PRBool detailed);
typedef void (*WalkFree_t)(FILE *out, PRWord *p, size_t size, PRBool detailed);
typedef void (*WalkSegment_t)(FILE *out, GCSeg* sp, PRBool detailed);

static void
pr_WalkSegment(FILE* out, GCSeg* sp, PRBool detailed,
           char* enterMsg, char* exitMsg,
           WalkObject_t walkObject, WalkUnknown_t walkUnknown, WalkFree_t walkFree)
{
    PRWord *p, *limit;

    p = (PRWord *) sp->base;
    limit = (PRWord *) sp->limit;
    if (enterMsg)
    fprintf(out, enterMsg, p);
    while (p < limit)
    {
    if (IS_HBIT(sp, p)) /* Is this an object header? */
    {
        PRWord h = p[0];
        PRWord tix = GET_TYPEIX(h);
        size_t bytes = OBJ_BYTES(h);
        PRWord* np = (PRWord*) ((char*)p + bytes);

        GCType* tp = &_pr_collectorTypes[tix].gctype;
        if ((0 != tp) && walkObject)
        walkObject(out, tp, p, bytes, detailed);
        else if (walkUnknown)
        walkUnknown(out, tp, tix, p, bytes, detailed);
        p = np;
    }
    else
    {
        /* Must be a freelist item */
        size_t size = ((GCFreeChunk*)p)->chunkSize;
        if (walkFree)
        walkFree(out, p, size, detailed);
        p = (PRWord*)((char*)p + size);
    }
    }
    if (p != limit)
    fprintf(out, "SEGMENT OVERRUN (end should be at 0x%p)\n", limit);
    if (exitMsg)
    fprintf(out, exitMsg, p);
}

static void
pr_WalkSegments(FILE *out, WalkSegment_t walkSegment, PRBool detailed)
{
    GCSeg *sp = segs;
    GCSeg *esp;

    LOCK_GC();
    esp = sp + nsegs;
    while (sp < esp)
    {
    walkSegment(out, sp, detailed);
    sp++;
    }
    fprintf(out, "End of heap\n");
    UNLOCK_GC();
}

/*******************************************************************************
 * Heap Dumper
 ******************************************************************************/

PR_IMPLEMENT(void)
PR_DumpIndent(FILE *out, int indent)
{
    while (--indent >= 0)
    fprintf(out, " ");
}

static void
PR_DumpHexWords(FILE *out, PRWord *p, int nWords,
        int indent, int nWordsPerLine)
{
    while (nWords > 0)
    {
    int i;

    PR_DumpIndent(out, indent);
    i = nWordsPerLine;
    if (i > nWords)
        i = nWords;
    nWords -= i;
    while (i--)
    {
        fprintf(out, "0x%.8lX", (long) *p++);
        if (i)
        fputc(' ', out);
    }
    fputc('\n', out);
    }
}

static void PR_CALLBACK
pr_DumpObject(FILE *out, GCType* tp, PRWord *p, 
          size_t bytes, PRBool detailed)
{
    char kindChar = tp->kindChar;
    fprintf(out, "0x%p: 0x%.6lX %c  ",
            p, (long) bytes, kindChar ? kindChar : '?');
    if (tp->dump)
    (*tp->dump)(out, (void*) (p + 1), detailed, 0);
    if (detailed)
    PR_DumpHexWords(out, p, bytes>>2, 22, 4);
}
    
static void PR_CALLBACK
pr_DumpUnknown(FILE *out, GCType* tp, PRWord tix, PRWord *p, 
           size_t bytes, PRBool detailed)
{
    char kindChar = tp->kindChar;
    fprintf(out, "0x%p: 0x%.6lX %c  ",
            p, (long) bytes, kindChar ? kindChar : '?');
    fprintf(out, "UNKNOWN KIND %ld\n", (long) tix);
    if (detailed)
    PR_DumpHexWords(out, p, bytes>>2, 22, 4);
}

static void PR_CALLBACK
pr_DumpFree(FILE *out, PRWord *p, size_t size, PRBool detailed)
{
    fprintf(out, "0x%p: 0x%.6lX -  FREE\n", p, (long) size);
}

static void PR_CALLBACK
pr_DumpSegment(FILE* out, GCSeg* sp, PRBool detailed)
{
    pr_WalkSegment(out, sp, detailed,
           "\n   Address: Length\n0x%p: Beginning of segment\n",
           "0x%p: End of segment\n\n",
           pr_DumpObject, pr_DumpUnknown, pr_DumpFree);
}

static void pr_DumpRoots(FILE *out);

/*
** Dump out the GC heap.
*/
PR_IMPLEMENT(void)
PR_DumpGCHeap(FILE *out, PRBool detailed)
{
    fprintf(out, "\n"
        "The kinds are:\n"
        " U unscanned block\n"
        " W weak link block\n"
        " S scanned block\n"
        " F scanned and final block\n"
        " C class record\n"
        " X context record\n"
        " - free list item\n"
        " ? other\n");
    LOCK_GC();
    pr_WalkSegments(out, pr_DumpSegment, detailed);
    if (detailed)
    pr_DumpRoots(out);
    UNLOCK_GC();
}

PR_IMPLEMENT(void)
PR_DumpMemory(PRBool detailed)
{
    PR_DumpToFile("memory.out", "Dumping memory", PR_DumpGCHeap, detailed);
}

/******************************************************************************/

static PRInt32 PR_CALLBACK
pr_DumpRootPointer(PRWord* p, void* data)
{
    PRWord h = p[0];
    PRWord tix = GET_TYPEIX(h);
      size_t bytes = OBJ_BYTES(h);
      
      GCType* tp = &_pr_collectorTypes[tix].gctype;
      if (0 != tp)
      pr_DumpObject(_pr_gcData.dumpOutput, tp, p, bytes, PR_FALSE);
      else
      pr_DumpUnknown(_pr_gcData.dumpOutput, tp, tix, p, bytes, PR_FALSE);
    return 0;
}

static void PR_CALLBACK
pr_ConservativeDumpRootPointer(void* ptr)
{
    (void)pr_ConservativeWalkPointer(ptr, (PRWalkFun) pr_DumpRootPointer, NULL);
}

static void PR_CALLBACK
pr_ConservativeDumpRootBlock(void **base, PRInt32 count)
{
    (void)pr_ConservativeWalkBlock(base, count, (PRWalkFun) pr_DumpRootPointer, NULL);
}

extern int
DumpThreadRoots(PRThread *t, int i, void *notused);

static void
pr_DumpRoots(FILE *out)
{
    RootFinder *rf;
    void (*liveBlock)(void **base, PRInt32 count);
    void (*livePointer)(void *ptr);
    void (*processRootBlock)(void **base, PRInt32 count);
    void (*processRootPointer)(void *ptr);

    LOCK_GC();

    liveBlock = _pr_gcData.liveBlock;
    livePointer = _pr_gcData.livePointer;
    processRootBlock = _pr_gcData.processRootBlock;
    processRootPointer = _pr_gcData.processRootPointer;
    
    _pr_gcData.liveBlock = pr_ConservativeDumpRootBlock;
    _pr_gcData.livePointer = pr_ConservativeDumpRootPointer;
    _pr_gcData.processRootBlock = pr_ConservativeDumpRootBlock;
    _pr_gcData.processRootPointer = pr_ConservativeDumpRootPointer;
    _pr_gcData.dumpOutput = out;

    rf = _pr_rootFinders;
    while (rf) {
    fprintf(out, "\n===== Roots for %s\n", rf->name);
    (*rf->func)(rf->arg);
    rf = rf->next;
    }

    _pr_gcData.liveBlock = liveBlock;
    _pr_gcData.livePointer = livePointer;
    _pr_gcData.processRootBlock = processRootBlock;
    _pr_gcData.processRootPointer = processRootPointer;
    _pr_gcData.dumpOutput = NULL;

    UNLOCK_GC();
}

/*******************************************************************************
 * Heap Summary Dumper
 ******************************************************************************/

PRSummaryPrinter summaryPrinter = NULL;
void* summaryPrinterClosure = NULL;

PR_IMPLEMENT(void) 
PR_RegisterSummaryPrinter(PRSummaryPrinter fun, void* closure)
{
    summaryPrinter = fun;
    summaryPrinterClosure = closure;
}

static void PR_CALLBACK
pr_SummarizeObject(FILE *out, GCType* tp, PRWord *p,
           size_t bytes, PRBool detailed)
{
    if (tp->summarize)
    (*tp->summarize)((void GCPTR*)(p + 1), bytes);
}

static void PR_CALLBACK
pr_DumpSummary(FILE* out, GCSeg* sp, PRBool detailed)
{
    pr_WalkSegment(out, sp, detailed, NULL, NULL,
           pr_SummarizeObject, NULL, NULL);
}

PR_IMPLEMENT(void)
PR_DumpGCSummary(FILE *out, PRBool detailed)
{
    if (summaryPrinter) {
    pr_WalkSegments(out, pr_DumpSummary, detailed);
    summaryPrinter(out, summaryPrinterClosure);
    }
#if 0
    fprintf(out, "\nFinalizable objects:\n");
    {
    PRCList *qp;
    qp = _pr_pendingFinalQueue.next;
    while (qp != &_pr_pendingFinalQueue) {
        GCFinal* fp = FinalPtr(qp);
        PRWord h = fp->object[0];        /* Grab header word */
        PRWord tix = GET_TYPEIX(h);
        GCType* tp = _pr_gcTypes[tix];
        size_t bytes = OBJ_BYTES(h);
        pr_DumpObject(out, tp, fp->object, bytes, PR_FALSE);
        qp = qp->next;
    }
    }
#endif
}

PR_IMPLEMENT(void)
PR_DumpMemorySummary(void)
{
    PR_DumpToFile("memory.out", "Memory Summary", PR_DumpGCSummary, PR_FALSE);
}

/*******************************************************************************
 * End Of Heap Walker 
 ******************************************************************************/

#ifdef GC_TRACEROOTS

PRInt32 pr_traceGen = 0;

static PRBool
pr_IsMarked(PRWord* p)
{
    GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
    PR_ASSERT(end->check == PR_BLOCK_END);
    return end->traceGeneration == pr_traceGen;
}

static void
pr_Mark(PRWord* p)
{
    GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
    PR_ASSERT(end->check == PR_BLOCK_END);
    end->traceGeneration = pr_traceGen;
}

PRWord* pr_traceObj;	/* set this in the debugger, then execute PR_TraceRoot() */

static PRInt32 PR_CALLBACK
pr_TraceRootObject(void* obj, void* data);

static PRInt32 PR_CALLBACK
pr_TraceRootPointer(PRWord *p, void* data)
{
    PRInt32 printTrace = 0;
    PRWord h = p[0];
    PRWord tix = GET_TYPEIX(h);
    GCType* tp = &_pr_collectorTypes[tix].gctype;
    FILE* out = _pr_gcData.dumpOutput;

    PR_ASSERT(tp);
    if (pr_IsMarked(p))
	return printTrace;

    pr_Mark(p);
    if (p == pr_traceObj) {
	fprintf(out, "\n### Found path to:\n");
	printTrace = 1;
    }
    else {
	if (PR_StackSpaceLeft(PR_GetCurrentThread()) < 512) {
	    fprintf(out, "\n### Path too deep (giving up):\n");
	    printTrace = 1;
	}
	else if (tp->walk) {
	    printTrace = tp->walk((void*)(p + 1), pr_TraceRootObject, data);
	}
	/* else there's no way to walk this object, so we
	   haven't found what we're looking for */
    }

    if (printTrace == 1) {
	PR_ASSERT(tp->dump);
	fprintf(out, "0x%p: ", p);
	tp->dump(out, (void*)(p + 1), PR_FALSE, 1);
    }
    return printTrace;
}

static PRInt32 PR_CALLBACK
pr_TraceRootObject(void* obj, void* data)
{
    /* This version of pr_TraceRootPointer takes object
       pointers, instead of gc header pointers. */
    return pr_TraceRootPointer((PRWord*)obj - 1, data);
}

static void PR_CALLBACK
pr_ConservativeTraceRootPointer(PRWord *p)
{
    PRInt32 status;
    ++pr_traceGen;
    status = pr_ConservativeWalkPointer(p, pr_TraceRootPointer, NULL);
    if (status) {
	FILE* out = _pr_gcData.dumpOutput;
	fprintf(out, "### from root at 0x%p\n\n", p);
    }
}

static void PR_CALLBACK
pr_ConservativeTraceRootBlock(void **base, PRInt32 count)
{
    PRInt32 status;
    ++pr_traceGen;
    status = pr_ConservativeWalkBlock(base, count, pr_TraceRootPointer, NULL);
    if (status) {
	FILE* out = _pr_gcData.dumpOutput;
	fprintf(out, "### from root in range 0x%p + 0x%lx\n\n",
                base, (long) count);
    }
}

static void
PR_TraceRoot1(FILE* out, PRBool detailed)
{
    RootFinder *rf;
    void (*liveBlock)(void **base, PRInt32 count);
    void (*livePointer)(void *ptr);
    void (*processRootBlock)(void **base, PRInt32 count);
    void (*processRootPointer)(void *ptr);

    LOCK_GC();

    liveBlock = _pr_gcData.liveBlock;
    livePointer = _pr_gcData.livePointer;
    processRootBlock = _pr_gcData.processRootBlock;
    processRootPointer = _pr_gcData.processRootPointer;
    
    _pr_gcData.liveBlock = pr_ConservativeTraceRootBlock;
    _pr_gcData.livePointer = pr_ConservativeTraceRootPointer;
    _pr_gcData.processRootBlock = pr_ConservativeTraceRootBlock;
    _pr_gcData.processRootPointer = pr_ConservativeTraceRootPointer;
    _pr_gcData.dumpOutput = out;

    fprintf(out, "### Looking for paths to 0x%p\n\n", pr_traceObj);

    rf = _pr_rootFinders;
    while (rf) {
	fprintf(out, "\n===== Roots for %s\n", rf->name);
	(*rf->func)(rf->arg);
	rf = rf->next;
    }

    _pr_gcData.liveBlock = liveBlock;
    _pr_gcData.livePointer = livePointer;
    _pr_gcData.processRootBlock = processRootBlock;
    _pr_gcData.processRootPointer = processRootPointer;
    _pr_gcData.dumpOutput = NULL;

    UNLOCK_GC();
}

PR_PUBLIC_API(void)
PR_TraceRoot()
{
    /*
    ** How this works: 
    ** Once you find the object you want to trace the roots of, set the
    ** global variable pr_traceObj to point to it (the header, not the
    ** java handle), and then call this routine (on Windows, you can set
    ** a breakpoint at the end of a function that returns void (e.g. dogc)
    ** and then do a "set next statement" to point to this routine and go.
    ** This will dump a list of the paths from the roots to the object in
    ** question to your memory.out file.
    */
    PR_DumpToFile("memory.out", "Tracing Roots", PR_TraceRoot1, PR_FALSE);
}

#endif /* GC_TRACEROOTS */

/******************************************************************************/

#if defined(DEBUG) && defined(WIN32)
static void DumpApplicationHeap(FILE *out, HANDLE heap)
{
    PROCESS_HEAP_ENTRY entry;
    DWORD err;

    if (!HeapLock(heap))
    OutputDebugString("Can't lock the heap.\n");
    entry.lpData = 0;
    fprintf(out, "   address:       size ovhd region\n");
    while (HeapWalk(heap, &entry))
    {
    WORD flags = entry.wFlags;

    fprintf(out, "0x%.8X: 0x%.8X 0x%.2X 0x%.2X  ", entry.lpData, entry.cbData,
        entry.cbOverhead, entry.iRegionIndex);
    if (flags & PROCESS_HEAP_REGION)
        fprintf(out, "REGION  committedSize=0x%.8X uncommittedSize=0x%.8X firstBlock=0x%.8X lastBlock=0x%.8X",
            entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
            entry.Region.lpFirstBlock, entry.Region.lpLastBlock);
    else if (flags & PROCESS_HEAP_UNCOMMITTED_RANGE)
        fprintf(out, "UNCOMMITTED");
    else if (flags & PROCESS_HEAP_ENTRY_BUSY)
    {
        if (flags & PROCESS_HEAP_ENTRY_DDESHARE)
        fprintf(out, "DDEShare ");
        if (flags & PROCESS_HEAP_ENTRY_MOVEABLE)
        fprintf(out, "Moveable Block  handle=0x%.8X", entry.Block.hMem);
        else
        fprintf(out, "Block");
    }
    fprintf(out, "\n");
    }
    if ((err = GetLastError()) != ERROR_NO_MORE_ITEMS)
    fprintf(out, "ERROR %d iterating through the heap\n", err);
    if (!HeapUnlock(heap))
    OutputDebugString("Can't unlock the heap.\n");
}
#endif

#if defined(DEBUG) && defined(WIN32)
static void DumpApplicationHeaps(FILE *out)
{
    HANDLE mainHeap;
    HANDLE heaps[100];
    DWORD nHeaps;
    PRInt32 i;

    mainHeap = GetProcessHeap();
    nHeaps = GetProcessHeaps(100, heaps);
    if (nHeaps > 100)
    nHeaps = 0;
    fprintf(out, "%ld heaps:\n", (long) nHeaps);
    for (i = 0; i<nHeaps; i++)
    {
    HANDLE heap = heaps[i];

    fprintf(out, "Heap at 0x%.8lX", (long) heap);
    if (heap == mainHeap)
        fprintf(out, " (main)");
    fprintf(out, ":\n");
    DumpApplicationHeap(out, heap);
    fprintf(out, "\n");
    }
    fprintf(out, "End of heap dump\n\n");
}
#endif

#if defined(DEBUG) && defined(WIN32)
PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
{
    FILE *out;

    OutputDebugString("Dumping heaps...");
    out = fopen("heaps.out", "a");
    if (!out)
    OutputDebugString("Can't open \"heaps.out\"\n");
    else
    {
    struct tm *newtime;
    time_t aclock;

    time(&aclock);
    newtime = localtime(&aclock);
    fprintf(out, "Heap dump on %s\n", asctime(newtime));    /* Print current time */
    DumpApplicationHeaps(out);
    fprintf(out, "\n\n");
    fclose(out);
    }
    OutputDebugString(" done\n");
}
#else

PR_IMPLEMENT(void) PR_DumpApplicationHeaps(void)
{
    fprintf(stderr, "Native heap dumping is currently implemented only for Windows32.\n");
}
#endif

/************************************************************************/

/*
** Scan the freelist bins looking for a big enough chunk of memory to
** hold "bytes" worth of allocation. "bytes" already has the
** per-allocation header added to it. Return a pointer to the object with
** its per-allocation header already prepared.
*/
static PRWord *BinAlloc(int cbix, PRInt32 bytes, int dub)
{
    GCFreeChunk **cpp, *cp, *cpNext;
    GCSeg *sp;
    PRInt32 chunkSize, remainder;
    PRWord *p, *np;
    PRInt32 bin, newbin;

    /* Compute bin that allocation belongs in */
    InlineBinNumber(bin,bytes)
    if (bin < minBin) {
    bin = minBin;    /* Start at first filled bin */
    }

    /* Search in the bin, and larger bins, for a big enough piece */
    for (; bin <= NUM_BINS-1; bin++) {
        cpp = &bins[bin];
    while ((cp = *cpp) != 0) {
        chunkSize = cp->chunkSize;
        if (chunkSize < bytes) {
        /* Too small; skip it */
            METER(meter.skippedFreeChunks++);
        cpp = &cp->next;
        continue;
        }

        /* We have found a hunk of memory large enough to use */
        p = (PRWord*) cp;
        sp = cp->segment;
        cpNext = cp->next;
#ifndef IS_64
        if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
        /*
         * We are double aligning the memory and the current free
         * chunk is aligned on an even boundary. Because header
         * words are one word long we need to discard the first
         * word of memory.
         */
        p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
        SET_HBIT(sp, p);
        p++;
        chunkSize -= PR_BYTES_PER_WORD;
        bytes -= PR_BYTES_PER_WORD;
        PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
        _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
        _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
        }
#endif
        np = (PRWord*) ((char*) p + bytes);
        remainder = chunkSize - bytes;
        if (remainder >= MIN_FREE_CHUNK_BYTES) {
        /* The left over memory is large enough to be freed. */
        cp = (GCFreeChunk*) np;
        cp->segment = sp;
        cp->chunkSize = remainder;
        InlineBinNumber(newbin, remainder)
        if (newbin != bin) {
            *cpp = (GCFreeChunk*) cpNext; /* remove */
            cp->next = bins[newbin];      /* insert */
            bins[newbin] = cp;
            if (newbin < minBin) minBin = newbin;
            if (newbin > maxBin) maxBin = newbin;
        } else {
            /* Leave it on the same list */
            cp->next = cpNext;
            *cpp = (GCFreeChunk*) np;
        }
        } else {
        /*
         * The left over memory is too small to be released. Just
         * leave it attached to the chunk of memory being
         * returned.
         */
        *cpp = cpNext;
        bytes = chunkSize;
        }
        p[0] = MAKE_HEADER(cbix, (bytes >> PR_BYTES_PER_WORD_LOG2));
        SET_HBIT(sp, p);
        _pr_gcData.freeMemory -= bytes;
        _pr_gcData.busyMemory += bytes;
        return p;
    }
    }
    return 0;
}

/*
** Allocate a piece of memory that is "big" in it's own segment.  Make
** the object consume the entire segment to avoid fragmentation.  When
** the object is no longer referenced, the segment is freed.
*/
static PRWord *BigAlloc(int cbix, PRInt32 bytes, int dub)
{
    GCSeg *sp;
    PRWord *p, h;
    PRInt32 chunkSize;

    /*
    ** If the number of bytes allocated via BigAlloc() since the last GC
    ** exceeds BIG_ALLOC_GC_SIZE then do a GC Now...
    */
    if (bigAllocBytes >= BIG_ALLOC_GC_SIZE) {
        dogc();
    }
    bigAllocBytes += bytes;

    /* Get a segment to hold this allocation */
    sp = GrowHeapExactly(bytes);

    if (sp) {
        p = (PRWord*) sp->base;
        chunkSize = sp->limit - sp->base;

        /* All memory is double aligned on 64 bit machines... */
#ifndef IS_64
        if (dub && (((PRWord)p & (PR_BYTES_PER_DWORD-1)) == 0)) {
            /*
            ** Consume the first word of the chunk with a dummy
            ** unreferenced object.
            */
            p[0] = MAKE_HEADER(FREE_MEMORY_TYPEIX, 1);
            SET_HBIT(sp, p);
            p++;
            chunkSize -= PR_BYTES_PER_WORD;
            _pr_gcData.freeMemory -= PR_BYTES_PER_WORD;
            _pr_gcData.busyMemory += PR_BYTES_PER_WORD;
            PR_ASSERT(((PRWord)p & (PR_BYTES_PER_DWORD-1)) != 0);
        }
#endif

        /* Consume the *entire* segment with a single allocation */
        h = MAKE_HEADER(cbix, (chunkSize >> PR_BYTES_PER_WORD_LOG2));
        p[0] = h;
        SET_HBIT(sp, p);
        _pr_gcData.freeMemory -= chunkSize;
        _pr_gcData.busyMemory += chunkSize;
    return p;
    }
    return 0;
}

/* we disable gc allocation during low memory conditions */
static PRBool allocationEnabled = PR_TRUE;

PR_IMPLEMENT(void) PR_EnableAllocation(PRBool yesOrNo)
{
    allocationEnabled = yesOrNo;
}

static void CollectorCleanup(void) {
    while (collectorCleanupNeeded) {
    LOCK_GC();
    collectorCleanupNeeded = 0;
    UNLOCK_GC();
    if (freeSegs) {
        FreeSegments();
    }
    if (!WEAK_FREELIST_ISEMPTY()) {
        EmptyWeakFreeList();
    }
    }
}

/******************************************************************************/

#ifdef GC_CHECK
static PRInt32 allocationCount;

static void EarthShatteringKaBoom(PRInt32 whichOne) {
    long* p = 0;
    *p = 0;
}

/* Check a segment of heap memory. Verify that the object memory
   hasn't been overwritten (past the end at least) */
static void CheckSegment(GCSeg* sp) {
    PRWord h, tix;
    PRWord *p, *lastp, *np, *limit;

    lastp = p = (PRWord *) sp->base;
    limit = (PRWord *) sp->limit;
    while (p < limit) {
    if (IS_HBIT(sp, p)) {
	    char *cp, i;
	    GCBlockEnd* end;
	    PRWord bytes, requestedBytes;

	    h = p[0];
	    tix = GET_TYPEIX(h);
	    bytes = OBJ_BYTES(h);
	    np = (PRWord *) ((char *)p + bytes);
	    if (tix != FREE_MEMORY_TYPEIX) {
                PRInt32 test;	/* msdev get's fooled without this local */
		/* A live object is here. The last word in the object will
		   contain the objects requestedSize */
		end = (GCBlockEnd*)((char*)(p) + bytes - sizeof(GCBlockEnd));
		test = end->check;
		if (test != PR_BLOCK_END) {
		    PR_ASSERT(test == PR_BLOCK_END);
		}
		requestedBytes = end->requestedBytes;
		if (requestedBytes >= bytes) EarthShatteringKaBoom(0);
		cp = (char*)(p + 1) + requestedBytes;
		i = (char) 0xff;
		while (cp < (char*)end) {
            if (*cp != i) EarthShatteringKaBoom(1);
            cp++;
            i--;
        }
        }
        lastp = p;
        p = np;
    } else {
        /* Must be a freelist item */
        GCFreeChunk *cp = (GCFreeChunk*) p;
        if ((PRInt32)cp->chunkSize < (PRInt32)sizeof(GCFreeChunk)) {
            EarthShatteringKaBoom(3);
        }
        lastp = p;
        p = (PRWord*) ((char*)p + cp->chunkSize);
    }
    }
}

static void CheckHeap(void) {
    GCSeg *sp = segs;
    GCSeg *esp = sp + nsegs;
    while (sp < esp) {
    CheckSegment(sp);
    sp++;
    }
}

#endif /* GC_CHECK */

/******************************************************************************/

#ifdef DEBUG
long gc_thrash = -1L;
#endif

/*
** Allocate memory from the GC Heap. Performs garbage collections if
** memory gets tight and grows the heap as needed. May return NULL if
** memory cannot be found.
*/
PR_IMPLEMENT(PRWord GCPTR *)PR_AllocMemory(
    PRWord requestedBytes, PRInt32 tix, PRWord flags)
{
    PRWord *p;
    CollectorType *ct;
    PRInt32 bytes;
    GCFinal *final = 0;
    GCWeak *weak = 0;
    int dub = flags & PR_ALLOC_DOUBLE;
    PRInt32 objBytes;
#ifdef GC_STATS
    PRInt64 allocTime, ldelta;
#endif

    if (!allocationEnabled) return NULL;

    PR_ASSERT(requestedBytes >= 0);
    PR_ASSERT(_pr_collectorTypes[tix].flags != 0);

#ifdef DEBUG
    if (_pr_do_a_dump) {
    /*
    ** Collect, pause for a second (lets finalizer run), and then GC
    ** again.
    */
    PR_GC();
    PR_Sleep(PR_MicrosecondsToInterval(1000000L));
    PR_GC();
    PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
    _pr_do_a_dump = 0;
    }
#endif

#ifdef GC_STATS
    allocTime = PR_Now();
#endif
    bytes = (PRInt32) requestedBytes;

    /*
    ** Align bytes to a multiple of a PRWord, then add in enough space
    ** to hold the header word.
    **
    ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
    */
    /* Check for possible overflow of bytes before performing add */
    if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
    bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
    bytes <<= PR_BYTES_PER_WORD_LOG2;
    /* Check for possible overflow of bytes before performing add */
    if ((MAX_INT - sizeof(PRWord)) < bytes ) return NULL;
    bytes += sizeof(PRWord);
    /*
     * Add in an extra word of memory for double-aligned memory. Some
     * percentage of the time this will waste a word of memory (too
     * bad). Howver, it makes the allocation logic much simpler and
     * faster.
     */
#ifndef IS_64
    if (dub) {
        /* Check for possible overflow of bytes before performing add */
        if ((MAX_INT - PR_BYTES_PER_WORD) < bytes ) return NULL;
        bytes += PR_BYTES_PER_WORD;
    }
#endif

#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) {
        /* Bloat the allocation a bit so that we can lay down
           a check pattern that we will validate */
        /* Check for possible overflow of bytes before performing add */
        if ((MAX_INT - PR_BYTES_PER_WORD * 3) < bytes ) return NULL;
        bytes += PR_BYTES_PER_WORD * 3;
    }
#endif

#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
    if ((MAX_INT - sizeof(GCBlockEnd)) < bytes ) return NULL;
    bytes += sizeof(GCBlockEnd);
#endif

    PR_ASSERT( bytes < MAX_ALLOC_SIZE );
    /*
    ** Java can ask for objects bigger than MAX_ALLOC_SIZE,
    ** but it won't get them.
    */
    if (bytes >= MAX_ALLOC_SIZE) return NULL;

#ifdef DEBUG
    if (gc_thrash == -1L ? (gc_thrash = (long)PR_GetEnv("GC_THRASH")):gc_thrash) PR_GC();
#endif

    ct = &_pr_collectorTypes[tix];
    if (ct->flags & (_GC_TYPE_FINAL|_GC_TYPE_WEAK)) {
    if (0 != ct->gctype.finalize) {
        /*
        ** Allocate a GCFinal struct for this object in advance. Don't put
        ** it on the pending list until we have allocated the object
        */
        final = AllocFinalNode();
        if (!final) {
        /* XXX THIS IS NOT ACCEPTABLE*/
		PR_ASSERT(0);
        return 0;
        }
    }
    if (0 != ct->gctype.getWeakLinkOffset) {
        /*
        ** Allocate a GCWeak struct for this object in advance. Don't put
        ** it on the weak links list until we have allocated the object
        */
        weak = AllocWeakNode();
        if (!weak) {
        /* XXX THIS IS NOT ACCEPTABLE*/
        if (0 != final) {
            FreeFinalNode(final);
        }
		PR_ASSERT(0);
        return 0;
        }
    }
    }

    LOCK_GC();
#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) CheckHeap();
    allocationCount++;
#endif

    /* Check for overflow of maximum size we can handle */
    if (bytes > MAX_ALLOC) goto lost;

    /* Try default allocation */
    p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
        BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
    if (0 == p) {
#ifdef GC_STATS
        LL_SUB(ldelta, PR_Now(), allocTime);
#endif
        /* Collect some memory */
        _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
        dogc();
        PR_ASSERT( GC_IS_LOCKED() );

        /* After a collection we check and see if we should grow the
        ** heap. We grow the heap when the amount of memory free is less
        ** than a certain percentage of the heap size. We don't check to
        ** see if the grow succeeded because our fallback strategy in
        ** either case is to try one more time to allocate. */
        if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory)
        && ((_pr_gcData.freeMemory <
            ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))
        || (_pr_gcData.freeMemory < bytes))) {
            GrowHeap(PR_MAX(bytes, segmentSize));
        }
#ifdef GC_STATS
        LL_ADD(allocTime, PR_Now(), ldelta);
#endif

        /* Try again */
        p = ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) ?
            BigAlloc(tix, bytes, dub) : BinAlloc(tix, bytes, dub);
        if (0 == p) {
            /* Well that lost big time. Memory must be pretty well fragmented */
            if (!GrowHeap(PR_MAX(bytes, segmentSize))) goto lost;
            p = BinAlloc(tix, bytes, dub);
            if (0 == p) goto lost;
        }
    }

    /* Zero out the portion of the object memory that was used by
       the GCFreeChunk structure (skip the first word because it
       was already overwritten by the gc header word) */
    objBytes = OBJ_BYTES(p[0]);
    if (objBytes > sizeof(PRWord)) p[1] = 0;
    if (objBytes > sizeof(PRWord)*2) p[2] = 0;

    if (final) {
	_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d) final=0x%x",
                p, bytes, final));
    final->object = p;
    PR_APPEND_LINK(&final->links, &_pr_finalizeableObjects);
    } else {
	_GCTRACE(GC_ALLOC, ("alloc 0x%x (%d)", p, bytes));
    }
    if (weak) {
    weak->object = p;
    PR_APPEND_LINK(&weak->links, &_pr_weakLinks);
    }
    METER(meter.allocBytes += bytes);
    METER(meter.wastedBytes += (bytes - requestedBytes));
    UNLOCK_GC();

    if (collectorCleanupNeeded) {
	CollectorCleanup();
    }

#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
    {
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
	end->check = PR_BLOCK_END;
    }
#endif
#ifdef GC_STATS
    {
	PRInt64 now = PR_Now();
	double delta;
	PRInt32 bin;
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));

	end->allocTime = allocTime;
	LL_SUB(ldelta, now, allocTime);
	LL_L2D(delta, ldelta);
	InlineBinNumber(bin, requestedBytes);
	end->bin = bin;
	gcstats[bin].nallocs++;
	gcstats[bin].allocTime += delta;
	gcstats[bin].allocTimeVariance += delta * delta;
    }
#endif
#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) {
    /* Place a pattern in the memory that was allocated that was not
       requested. We will check the pattern later. */
    char* cp = (char*)(p + 1) + requestedBytes;
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
	char i = (char) 0xff;
	while (cp < (char*)end) {
	    *cp++ = i--;
	}
	end->requestedBytes = requestedBytes;
	CheckHeap();
    }
#endif
    return p + 1;

  lost:
    /* Out of memory */
    UNLOCK_GC();
    if (final) {
    FreeFinalNode(final);
    }
    if (weak) {
    FreeWeakNode(weak);
    }
    if (collectorCleanupNeeded) {
    CollectorCleanup();
    }
    return 0;
}

/* Shortcut allocator for objects that do not require finalization or
   are weak objects */
PR_IMPLEMENT(PRWord GCPTR *)
PR_AllocSimpleMemory(PRWord requestedBytes, PRInt32 tix)
{
    PRWord *p;
    PRInt32 bytes;
    PRInt32 objBytes;
#ifdef GC_STATS
    PRInt64 allocTime, ldelta;
#endif

    if (!allocationEnabled) return NULL;

    PR_ASSERT(requestedBytes >= 0);
    PR_ASSERT(_pr_collectorTypes[tix].flags != 0);

#ifdef DEBUG
    if (_pr_do_a_dump) {
	/*
	** Collect, pause for a second (lets finalizer run), and then GC
	** again.
	*/
	PR_GC();
	PR_Sleep(PR_MicrosecondsToInterval(1000000L));
	PR_GC();
	PR_DumpGCHeap(_pr_dump_file, PR_TRUE);
	_pr_do_a_dump = 0;
    }
#endif

#ifdef GC_STATS
    allocTime = PR_NowMS();
#endif
    bytes = (PRInt32) requestedBytes;

    /*
    ** Align bytes to a multiple of a PRWord, then add in enough space
    ** to hold the header word.
    **
    ** MSVC 1.52 crashed on the ff. code because of the "complex" shifting :-(
    */
    bytes = (bytes + PR_BYTES_PER_WORD - 1) >> PR_BYTES_PER_WORD_LOG2;
    bytes <<= PR_BYTES_PER_WORD_LOG2;
    bytes += sizeof(PRWord);
    
    /*
     * Add in an extra word of memory for double-aligned memory. Some
     * percentage of the time this will waste a word of memory (too
     * bad). Howver, it makes the allocation logic much simpler and
     * faster.
     */
#ifndef IS_64
    bytes += PR_BYTES_PER_WORD;
#endif

#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) {
    /* Bloat the allocation a bit so that we can lay down
       a check pattern that we will validate */
    bytes += PR_BYTES_PER_WORD * 2;
    }
#endif

#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
    bytes += sizeof(GCBlockEnd);
#endif

    /* Java can ask for objects bigger than 4M, but it won't get them */
    /*
     * This check was added because there is a fundamental limit of
     * the size field maintained by the gc code.  Going over the 4M
     * limit caused some bits to roll over into another bit field,
     * violating the max segment size and causing a bug.
     */
    if (bytes >= MAX_ALLOC_SIZE) {
        return NULL;
    }
#ifdef DEBUG
    if (gc_thrash == -1L
	? (gc_thrash = (long)PR_GetEnv("GC_THRASH"))
	: gc_thrash) {
	PR_GC();
    }
#endif

    LOCK_GC();
#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) {
    CheckHeap();
    }
    allocationCount++;
#endif

    /* Try default allocation */
    if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
    p = BigAlloc(tix, bytes, 1);
    } else {
    p = BinAlloc(tix, bytes, 1);
    }
    if (0 == p) {
#ifdef GC_STATS
      LL_SUB(ldelta, PR_Now(), allocTime);
#endif
      /* Collect some memory */
      _GCTRACE(GC_ALLOC, ("force GC: want %d", bytes));
      dogc();
      PR_ASSERT( GC_IS_LOCKED() );

      /* After a collection we check and see if we should grow the
     heap. We grow the heap when the amount of memory free is less
     than a certain percentage of the heap size. We don't check to
     see if the grow succeeded because our fallback strategy in
     either case is to try one more time to allocate. */
      if ((_pr_gcData.allocMemory < _pr_gcData.maxMemory) &&
      (_pr_gcData.freeMemory <
       ((_pr_gcData.allocMemory * MIN_FREE_THRESHOLD_AFTER_GC) / 100L))) {
    GrowHeap(PR_MAX(bytes, segmentSize));
      }
#ifdef GC_STATS
      LL_ADD(allocTime, PR_Now(), ldelta);
#endif

      /* Try one last time */
      if ((bytes >= BIG_ALLOC) && (nsegs < MAX_SEGS)) {
    p = BigAlloc(tix, bytes, 1);
      } else {
    p = BinAlloc(tix, bytes, 1);
      }
      if (0 == p) {
    /* Well that lost big time. Memory must be pretty well fragmented */
    if (!GrowHeap(PR_MAX(bytes, segmentSize))) {
      goto lost;
    }
    p = BinAlloc(tix, bytes, 1);
    if (0 == p) goto lost;
      }
    }

    /* Zero out the portion of the object memory that was used by
       the GCFreeChunk structure (skip the first word because it
       was already overwritten by the gc header word) */
    objBytes = OBJ_BYTES(p[0]);
    if (objBytes > sizeof(PRWord)) p[1] = 0;
    if (objBytes > sizeof(PRWord)*2) p[2] = 0;

    METER(meter.allocBytes += bytes);
    METER(meter.wastedBytes += (bytes - requestedBytes));
    UNLOCK_GC();

    if (collectorCleanupNeeded) {
	CollectorCleanup();
    }

#if defined(GC_CHECK) || defined(GC_STATS) || defined(GC_TRACEROOTS)
    {
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
	end->check = PR_BLOCK_END;
    }
#endif
#ifdef GC_STATS
    {
	PRInt64 now = PR_Now();
	double delta;
	PRInt32 bin;
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));

	end->allocTime = allocTime;
	LL_SUB(ldelta, now, allocTime);
	LL_L2D(delta, ldelta);
	InlineBinNumber(bin, requestedBytes);
	end->bin = bin;
	gcstats[bin].nallocs++;
	gcstats[bin].allocTime += delta;
	gcstats[bin].allocTimeVariance += delta * delta;
    }
#endif
#ifdef GC_CHECK
    if (_pr_gcData.flags & GC_CHECK) {
    /* Place a pattern in the memory that was allocated that was not
       requested. We will check the pattern later. */
    char* cp = (char*)(p + 1) + requestedBytes;
	GCBlockEnd* end = (GCBlockEnd*)((char*)p + OBJ_BYTES(p[0]) - sizeof(GCBlockEnd));
	char i = (char) 0xff;
	while (cp < (char*)end) {
	    *cp++ = i--;
	}
	end->requestedBytes = requestedBytes;
	CheckHeap();
    }
#endif
    return p + 1;

  lost:
    /* Out of memory */
    UNLOCK_GC();
    if (collectorCleanupNeeded) {
    CollectorCleanup();
    }
    return 0;
}

/************************************************************************/

PR_IMPLEMENT(PRWord) PR_GetObjectHeader(void *ptr) {
    GCSeg *sp;
    PRWord *h;

    if (ptr == 0) return 0;
    sp = InHeap(ptr);
    if (sp == 0) return 0;
    h = (PRWord*)FindObject(sp, (PRWord*)ptr);
    return GC_GET_USER_BITS(h[0]);
}

PR_IMPLEMENT(PRWord) PR_SetObjectHeader(void *ptr, PRWord newUserBits) {
    GCSeg *sp;
    PRWord *h, rv;

    if (ptr == 0) return 0;
    sp = InHeap(ptr);
    if (sp == 0) return 0;
    h = (PRWord*)FindObject(sp, (PRWord*)ptr);
    rv = GC_GET_USER_BITS(h[0]);
    h[0] = (h[0] & ~GC_USER_BITS) |
    ((newUserBits << GC_USER_BITS_SHIFT) & GC_USER_BITS);
    return rv;
}

PR_IMPLEMENT(void) PR_InitGC(
    PRWord flags, PRInt32 initialHeapSize, PRInt32 segSize, PRThreadScope scope)
{
    static char firstTime = 1;

    if (!firstTime) return;
    firstTime = 0;

    _pr_msgc_lm = PR_NewLogModule("msgc");
    _pr_pageShift = PR_GetPageShift();
    _pr_pageSize = PR_GetPageSize();

  /* Setup initial heap size and initial segment size */
  if (0 != segSize) segmentSize = segSize;
#ifdef DEBUG
    GC = PR_NewLogModule("GC");
    {
    char *ev = PR_GetEnv("GC_SEGMENT_SIZE");
    if (ev && ev[0]) {
      PRInt32 newSegmentSize = atoi(ev);
      if (0 != newSegmentSize) segmentSize = newSegmentSize;
    }
    ev = PR_GetEnv("GC_INITIAL_HEAP_SIZE");
    if (ev && ev[0]) {
      PRInt32 newInitialHeapSize = atoi(ev);
      if (0 != newInitialHeapSize) initialHeapSize = newInitialHeapSize;
    }
    ev = PR_GetEnv("GC_FLAGS");
    if (ev && ev[0]) {
        flags |= atoi(ev);
    }
#ifdef GCMETER
        ev = PR_GetEnv("GC_METER");
        if (ev && ev[0]) {
            _pr_gcMeter = atoi(ev);
        }
#endif
    }
#endif
  if (0 == initialHeapSize) initialHeapSize = segmentSize;
  if (initialHeapSize < segmentSize) initialHeapSize = segmentSize;

  _pr_gcData.maxMemory   = MAX_SEGS * segmentSize;
  _pr_gcData.liveBlock  = ProcessRootBlock;
  _pr_gcData.livePointer = ProcessRootPointer;
  _pr_gcData.processRootBlock  = ProcessRootBlock;
  _pr_gcData.processRootPointer = ProcessRootPointer;
  _pr_gcData.dumpOutput = NULL;

  PR_INIT_CLIST(&_pr_finalizeableObjects);
    PR_INIT_CLIST(&_pr_finalQueue);
    _PR_InitGC(flags);

    /* Create finalizer thread */
    _PR_CreateFinalizer(scope);

  /* Allocate the initial segment for the heap */
  minBin = 31;
  maxBin = 0;
  GrowHeap(initialHeapSize);
    PR_RegisterRootFinder(ScanWeakFreeList, "scan weak free list", 0);
}

/** Added by Vishy for sanity checking a few GC structures **/
/** Can use SanityCheckGC to debug corrupted GC Heap situations **/

#ifdef DEBUG

static int SegmentOverlaps(int i, int j)
{
  return
    (((segs[i].limit > segs[j].base) && (segs[i].base < segs[j].base)) ||
     ((segs[j].limit > segs[i].base) && (segs[j].base < segs[i].base)));
}

static void NoSegmentOverlaps(void)
{
  int i,j;

  for (i = 0; i < nsegs; i++)
    for (j = i+1 ; j < nsegs ; j++)
      PR_ASSERT(!SegmentOverlaps(i,j));
}

static void SegInfoCheck(void)
{
  int i;
  for (i = 0 ; i < nsegs ; i++)
    PR_ASSERT((segs[i].info->hbits) &&
	      (segs[i].info->hbits == segs[i].hbits) &&
	      (segs[i].info->base == segs[i].base) &&
	      (segs[i].info->limit == segs[i].limit));
}

static void SanityCheckGC()
{
  NoSegmentOverlaps();
  SegInfoCheck();
}

#endif

#if defined(DEBUG) && defined(WIN32)

extern void *baseaddr;
extern void *lastaddr;

PR_IMPLEMENT(void)
PR_PrintGCStats(void)
{
    long reportedSegSpace = _pr_gcData.busyMemory + _pr_gcData.freeMemory;
    char* msg;
    long largeCount = 0, largeSize = 0;
    long segCount = 0, segSize = 0;
    long freeCount = 0, freeSize = 0;
    GCSeg *sp, *esp;
    GCSegInfo* si;

    LOCK_GC();

    sp = segs;
    esp = sp + nsegs;
    while (sp < esp) {
    long size = sp->info->limit - sp->info->base;
    segCount++;
    segSize += size;
        if (sp->info->fromMalloc) {
        largeCount++;
        largeSize += size;
    }
        sp++;
    }

    si = freeSegs;
    while (si != NULL) {
    long size = si->limit - si->base;
    freeCount++;
    freeSize += size;
    si = si->next;
    }
    
    msg = PR_smprintf("\
# GC Stats:\n\
#   vm space:\n\
#     range:      %ld - %ld\n\
#     size:       %ld\n\
#   segments:\n\
#     range:      %ld - %ld\n\
#     count:      %ld (reported: %ld)\n\
#     size:       %ld (reported: %ld)\n\
#     free count: %ld\n\
#     free size:  %ld\n\
#     busy objs:  %ld (%ld%%)\n\
#     free objs:  %ld (%ld%%)\n\
#   large blocks:\n\
#     count:      %ld\n\
#     total size: %ld (%ld%%)\n\
#     avg size:   %ld\n\
",
              /* vm space */
              (long)baseaddr, (long)lastaddr,
              (long)lastaddr - (long)baseaddr,
              /* segments */
              _pr_gcData.lowSeg, _pr_gcData.highSeg,
              segCount, nsegs,
              segSize, reportedSegSpace,
              freeCount,
              freeSize,
              _pr_gcData.busyMemory,
              (_pr_gcData.busyMemory * 100 / reportedSegSpace),
              _pr_gcData.freeMemory,
              (_pr_gcData.freeMemory * 100 / reportedSegSpace),
              /* large blocks */
              largeCount,
              largeSize, (largeSize * 100 / reportedSegSpace),
              (largeCount ? largeSize / largeCount : 0)
              );
    UNLOCK_GC();
    fprintf(stderr, msg);
    OutputDebugString(msg);
    PR_smprintf_free(msg);
#ifdef GC_STATS
    PR_PrintGCAllocStats();
#endif
}
#endif

PR_IMPLEMENT(void)
PR_DumpToFile(char* filename, char* msg, PRFileDumper dump, PRBool detailed)
{
    FILE *out;
    OutputDebugString(msg);
    out = fopen(filename, "a");
    if (!out) {
	char buf[64];
	PR_ASSERT(strlen(filename) < sizeof(buf) - 16);
	PR_snprintf(buf, sizeof(buf), "Can't open \"%s\"\n",
		    filename);
	OutputDebugString(buf);
    }
    else
    {
	struct tm *newtime;
	time_t aclock;
	int i;

	time(&aclock);
	newtime = localtime(&aclock);
	fprintf(out, "%s on %s\n", msg, asctime(newtime));  /* Print current time */
	dump(out, detailed);
	fprintf(out, "\n\n");
	for (i = 0; i < 80; i++)
	    fprintf(out, "=");
	fprintf(out, "\n\n");
	fclose(out);
    }
    OutputDebugString(" done\n");
}