prmsgc.c

Netscape NSPR库源码

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* 
 * 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 Netscape are 
 * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
 * Rights Reserved.
 * 
 * Contributor(s):
 * 
 * Alternatively, the contents of this file may be used under the
 * terms of the GNU General Public License Version 2 or later (the
 * "GPL"), in which case the provisions of the GPL are applicable 
 * instead of those above.  If you wish to allow use of your 
 * version of this file only under the terms of the GPL and not to
 * allow others to use your version of this file under the MPL,
 * indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by
 * the GPL.  If you do not delete the provisions above, a recipient
 * may use your version of this file under either the MPL or the
 * GPL.
 */

#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"

#if defined(XP_MAC)
#include "pprthred.h"
#else
#include "private/pprthred.h"
#endif

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 */
#ifdef XP_MAC
#define MIN_FREE_THRESHOLD_AFTER_GC 10L
#else
#define MIN_FREE_THRESHOLD_AFTER_GC 20L
#endif

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?
*/
#if !defined(WIN16)
#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)))
#else

#define SET_HBIT(_sp,_ph) set_hbit(_sp,_ph)

#define CLEAR_HBIT(_sp,_ph) clear_hbit(_sp,_ph)

#define IS_HBIT(_sp,_ph) is_hbit(_sp,_ph)

static void
set_hbit(GCSeg *sp, PRWord *p)
{
    unsigned int distance;
    unsigned int index;
    PRWord     mask;

        PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
        PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );

        distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
    index    = distance >> PR_BITS_PER_WORD_LOG2;
    mask     = 1L << (distance&(PR_BITS_PER_WORD-1));

    sp->hbits[index] |= mask;
}

static void
clear_hbit(GCSeg *sp, PRWord *p)
{
    unsigned int distance;
    unsigned int index;
    PRWord    mask;

        PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
        PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );

        distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
    index    = distance >> PR_BITS_PER_WORD_LOG2;
    mask     = 1L << (distance&(PR_BITS_PER_WORD-1));

    sp->hbits[index] &= ~mask;
}

static int
is_hbit(GCSeg *sp, PRWord *p)
{
    unsigned int distance;
    unsigned int index;
    PRWord    mask;

        PR_ASSERT( SELECTOROF(p) == SELECTOROF(sp->base) );
        PR_ASSERT( OFFSETOF(p)   >= OFFSETOF(sp->base) );

        distance = (OFFSETOF(p) - OFFSETOF(sp->base)) >> 2;
    index    = distance >> PR_BITS_PER_WORD_LOG2;
    mask     = 1L << (distance&(PR_BITS_PER_WORD-1));

    return ((sp->hbits[index] & mask) != 0);
}


#endif  /* WIN16 */

/*
** 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;
#if defined(WIN16)
    PR_ASSERT( SELECTOROF(p) == SELECTOROF(base));
#endif
    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 

#if !defined(WIN16)
#define IN_SEGMENT(_sp, _p)             \
    ((((char *)(_p)) >= (_sp)->base) &&    \
     (((char *)(_p)) < (_sp)->limit))
#else
#define IN_SEGMENT(_sp, _p)                  \
    ((((PRWord)(_p)) >= ((PRWord)(_sp)->base)) && \
     (((PRWord)(_p)) < ((PRWord)(_sp)->limit)))
#endif

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;
    }

#if defined(WIN16)
    if (requestedSize > segmentSize) {
    PR_DELETE(segInfo);
    return 0;
    }
#endif

    /* 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);
    }