GC.h

Go to the documentation of this file.

/* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 4 -*- */
/* ***** 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 [Open Source Virtual Machine.].
 *
 * The Initial Developer of the Original Code is
 * Adobe System Incorporated.
 * Portions created by the Initial Developer are Copyright (C) 2004-2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Adobe AS3 Team
 *   leon.sha@sun.com
 *
 * 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 ***** */

#ifndef __GC__
#define __GC__

#if defined(MMGC_PORTING_API)
    // When the porting API is in use, we exclude
    // stdlib functions or use them through
    // #defines for portability to platforms
    // that don't have them.
    #include "portapi_mmgc.h"
#else

#if defined MMGC_IA32

#ifdef WIN32
// save all registers: they might have pointers in them.  In theory, only
// need to save callee-saved regs.  In practice, saving three extra pointers
// is cheap insurance.
//
// These macros do not use the "do { ... } while (0)" idiom because they
// work by introducing local variables (save1, save2, ...) into the block
// where the macro is called.  If the macro enclosed these variables in a
// nested block, like a do-while block, they would go out of scope too
// soon.
//
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int save1,save2,save3,save4,save5,save6,save7;\
        __asm mov save1, eax \
        __asm mov save2, ebx \
        __asm mov save3, ecx \
        __asm mov save4, edx \
        __asm mov save5, ebp \
        __asm mov save6, esi \
        __asm mov save7, edi \
        __asm { mov _stack,esp } ;\
        MEMORY_BASIC_INFORMATION __mib;\
        VirtualQuery(_stack, &__mib, sizeof(MEMORY_BASIC_INFORMATION)); \
        _size = __mib.RegionSize - ((uintptr) _stack - (uintptr)__mib.BaseAddress);

#elif defined SOLARIS
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        _stack = (void *) _getsp();\
        _size = (uintptr)_gc->GetStackTop() - (uintptr)_stack;
#else
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        volatile auto int save1,save2,save3,save4,save5,save6,save7;\
        asm("movl %%eax,%0" : "=r" (save1));\
        asm("movl %%ebx,%0" : "=r" (save2));\
        asm("movl %%ecx,%0" : "=r" (save3));\
        asm("movl %%edx,%0" : "=r" (save4));\
        asm("movl %%ebp,%0" : "=r" (save5));\
        asm("movl %%esi,%0" : "=r" (save6));\
        asm("movl %%edi,%0" : "=r" (save7));\
        asm("movl %%esp,%0" : "=r" (_stack));\
        _size = (uintptr)_gc->GetStackTop() - (uintptr)_stack;
#endif 

#elif defined MMGC_AMD64
#ifdef _MSC_VER // inline assembler not allowed in x64 MSVC
struct saveregs {
    size_t  save1;
    size_t  save2;
    size_t  save3;
    size_t  save4;
    size_t  save5;
    size_t  save6;
    size_t  save7;
    size_t  save8;
    size_t  save9;
    size_t  save10;
};
extern "C" void saveRegs64(void* saves, const void* stack, int* size);

#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        saveregs saves;\
        saves.save1 = 0;\
        saveRegs64(&saves, &_stack, (int*)&_size);

#else
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        do { \
        volatile auto int64 save1,save2,save3,save4,save5,save6,save7,save8,save9,save10,save11,save12,save13;\
        asm("mov %%rax,%0" : "=r" (save1));\
        asm("mov %%rbx,%0" : "=r" (save2));\
        asm("mov %%rcx,%0" : "=r" (save3));\
        asm("mov %%rdx,%0" : "=r" (save4));\
        asm("mov %%rbp,%0" : "=r" (save5));\
        asm("mov %%rsi,%0" : "=r" (save6));\
        asm("mov %%rdi,%0" : "=r" (save7));\
        asm("mov %%r8,%0" : "=r" (save8));\
        asm("mov %%r9,%0" : "=r" (save9));\
        asm("mov %%r12,%0" : "=r" (save10));\
        asm("mov %%r13,%0" : "=r" (save11));\
        asm("mov %%r14,%0" : "=r" (save12));\
        asm("mov %%r15,%0" : "=r" (save13));\
        asm("mov %%rsp,%0" : "=r" (_stack));\
        _size = (uintptr)_gc->GetStackTop() - (uintptr)_stack;  } while (0) 
#endif

#elif defined MMGC_PPC

/* On PowerPC, we need to mark the PPC non-volatile registers,
 * since they may contain register variables that aren't
 * anywhere on the machine stack. */
// TPR - increasing to 20 causes this code to not get optimized out

#ifdef __GNUC__

#ifdef _MAC

#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int __ppcregs[20]; \
        asm("stmw r13,0(%0)" : : "b" (__ppcregs));\
        _stack = __ppcregs;\
        void *__stackBase;\
        asm ("mr r3,r1\n"\
            "1: mr %0,r3\n"\
            "lwz r3,0(%0)\n"\
                "rlwinm r3,r3,0,0,30\n"\
            "cmpi cr0,r3,0\n"\
            "bne 1b" : "=b" (__stackBase) : : "r3");\
        _size = (uintptr) __stackBase - (uintptr) _stack;

#else // _MAC

#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int __ppcregs[20]; \
        asm("stmw %%r13,0(%0)" : : "b" (__ppcregs));\
        _stack = __ppcregs;\
        void *__stackBase;\
        asm ("mr %%r3,%%r1\n"\
             "StackBaseLoop%1%2: mr %0,%%r3\n"  \
            "lwz %%r3,0(%0)\n"\
                "rlwinm %%r3,%%r3,0,0,30\n"\
            "cmpi cr0,%%r3,0\n"\
             "bne StackBaseLoop%1%2" : "=b" (__stackBase) : "i" (__FILE__), "i" (__LINE__) : "r3"); \
        _size = (uintptr) __stackBase - (uintptr) _stack;

#endif // _MAC

#else // __GNUC__

#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int __ppcregs[20]; \
        asm("stmw r13,0(%0)" : : "b" (__ppcregs));\
        _stack = __ppcregs;\
        void *__stackBase;\
        asm ("mr r3,r1\n"\
            "StackBaseLoop: mr %0,r3\n"\
            "lwz r3,0(%0)\n"\
                "rlwinm r3,r3,0,0,30\n"\
            "cmpi cr0,r3,0\n"\
             "bne StackBaseLoop" : "=b" (__stackBase) : : "r3"); \
        _size = (uintptr) __stackBase - (uintptr) _stack;

#endif // __GNUC__

#elif defined MMGC_ARM

#ifdef UNDER_CE
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int GC_tmp_1; void* tmp_ptr = &GC_tmp_1;\
        MEMORY_BASIC_INFORMATION __mib;\
        VirtualQuery(tmp_ptr, &__mib, sizeof(MEMORY_BASIC_INFORMATION)); \
        _size = __mib.RegionSize - ((int)tmp_ptr - (int)__mib.BaseAddress); \
        _stack = tmp_ptr;
#else
#ifdef __ARMCC__
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        _stack =  (void*)__current_sp(); \
        _size = (unsigned int*)_gc->GetStackTop() - (unsigned int*)_stack;
#else
// Store nonvolatile registers r4-r10
// Find stack pointer
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        int regs[7];\
        asm("stmia %0,{r4-r10}" : : "r" (regs));\
        asm("mov %0,sp" : "=r" (_stack));\
        _size = (uintptr)_gc->GetStackTop() - (uintptr)_stack;
#endif //__ARMCC__

#endif


#elif defined MMGC_SPARC
#define MMGC_GET_STACK_EXTENTS(_gc, _stack, _size) \
        asm("ta 3");\
        _stack = (void *) _getsp();\
        _size = (uintptr)_gc->GetStackTop() - (uintptr)_stack;
#endif

#ifdef MMGC_THREADSAFE
#define MMGC_ASSERT_GC_LOCK(gc)  GCAssert((gc)->m_lock.IsHeld() || (gc)->destroying)
#define MMGC_ASSERT_EXCLUSIVE_GC(gc) \
    GCAssert(((gc)->m_gcRunning \
              && (gc)->m_exclusiveGCThread == GCThread::GetCurrentThread()) \
             || (gc)->destroying)
#else
#define MMGC_ASSERT_GC_LOCK(gc)      ((void) 0)
#define MMGC_ASSERT_EXCLUSIVE_GC(gc) ((void) 0)
#endif

#endif // MMGC_PORTING_API

namespace avmplus
{
    class AvmCore;
}

namespace MMgc
{
    class GCWorkItem
    {
    public:
        GCWorkItem() : ptr(NULL), _size(0) { }
        inline GCWorkItem(const void *p, uint32 s, bool isGCItem);

        uint32 GetSize() const { return _size & ~1; }
        uint32 IsGCItem() const { return _size & 1; }

        // If a WI is a GC item, `ptr` is the UserPointer; it must not
        // be the RealPointer nor an interior pointer
        const void *ptr;

        // The low bit of _size stores whether this is a GC item.
        // Always access this through `GetSize` and `IsGCItem`
        uint32 _size;
    };

    class MMGC_API GCRoot
    {
        friend class GC;
        GCRoot();
        void init(GC*gc, const void *object, size_t size);
    public:
        GCRoot(GC *gc);
        GCRoot(GC *gc, const void *object, size_t size);
        virtual ~GCRoot();

        // override new and delete so we can know the objects extents (via FixedMalloc::Size())
        void *operator new(size_t size)
        {
            return FixedMalloc::GetInstance()->Alloc(size);
        }
        
        void operator delete (void *object)
        {
            FixedMalloc::GetInstance()->Free(object);
        }

        const void *Get() const { return object; }
        void Set(const void *object, size_t size);

        GC *GetGC() const { return gc; }
        void Destroy();
    
    private:
        GC * gc;

        GCRoot *next;
        GCRoot *prev;
        const void *object;
        size_t size;

        GCWorkItem GetWorkItem() const { return GCWorkItem(object, (uint32)size, false); }
    };

    class MMGC_API GCCallback
    {
        friend class GC;
        friend class ZCT;
    public:
        GCCallback(GC *gc);
        virtual ~GCCallback();
        
        GC *GetGC() const { return gc; }
        void Destroy();

        virtual void presweep() {}

        virtual void postsweep() {}

        virtual void heapgrew() {}

#ifdef MMGC_DRC
        // called before a ZCT reap begins
        virtual void prereap() {}

        // called after a ZCT reap completes
        virtual void postreap() {}
#endif

        virtual void enterExclusiveGC() {}

        virtual void enterExclusiveGCNoLock() {}

        virtual void leaveExclusiveGC() {}

        virtual void prereap(void* /*rcobj*/) {}
        virtual void log(const char* /*str*/) {}

#ifdef DEBUGGER
        virtual void startGCActivity() {}   
        virtual void stopGCActivity() {}
        // negative when blocks are reclaimed
        virtual void allocActivity(int /*blocks*/) {}
#endif

    private:
        GC *gc;
        GCCallback *nextCB;
        GCCallback *prevCB;
    };

    #ifdef MMGC_64BIT
    #define HIDDENPTRMASK (uintptr(0x1L)<<63)
    #else
    #define HIDDENPTRMASK (uintptr(0x1L)<<31)
    #endif

    template <class T>
    class GCHiddenPointer
    {
    public:
        GCHiddenPointer(T obj=NULL) { set(obj); }
        operator T() const { return (T) (val^HIDDENPTRMASK);     }
        T operator=(T tNew) 
        { 
            set(tNew); 
            return (T)this; 
        }
        T operator->() const { return (T) (val^HIDDENPTRMASK); }

    private:
        // private to prevent its use and someone adding it, GCC creates
        // WriteBarrier's on the stack with it
        GCHiddenPointer(const GCHiddenPointer<T>& toCopy) { GCAssert(false); }
        
        void set(T obj) 
        {
            uintptr p = (uintptr)obj;
            val = p ^ HIDDENPTRMASK;
        }
        uintptr val;
    };

    class MMGC_API ZCT
    {
        friend class GC;
        // how many items there have to be to trigger a Reap
        static const int ZCT_REAP_THRESHOLD;

        // size of table in pages
        static const int ZCT_START_SIZE;
    public:
        ZCT();
        ~ZCT();
        void Add(RCObject *obj);
        void Remove(RCObject *obj);
        void Reap();
    private:
        // for MMGC_GET_STACK_EXTENTS
        uintptr StackTop;

        GC *gc;
        void SetGC(GC*);

        // in pages
        int zctSize;

        // the zero count table
        RCObject **zct;

        // index to the end
        RCObject **zctNext;

        // freelist of open slots
        RCObject **zctFreelist;

        // during a reap where we are
        int zctIndex;

        // during a reap becomes zctNext
        int nextPinnedIndex;

        int count;
        int zctReapThreshold;

        // are we reaping the zct?
        bool reaping;

        void PinStackObjects(const void *start, size_t len);
        bool IsZCTFreelist(RCObject **obj)
        {
            return obj >= zct && obj < (RCObject**)(zct+zctSize/sizeof(RCObject*));
        }
    };

    class MMGC_API GC : public GCAllocObject
    {
        friend class GCRoot;
        friend class GCCallback;
        friend class GCAlloc;
        friend class GCLargeAlloc;
        friend class RCObject;
        friend class GCInterval;
        friend class ZCT;
    public:

        enum
        {
            GCV_COREPLAYER,
            GCV_AVMCORE,
            GCV_COUNT
        };
        void *GetGCContextVariable(int var) const { return m_contextVars[var]; }
        void SetGCContextVariable(int var, void *val) { m_contextVars[var] = val; }
        
        avmplus::AvmCore *core() const { return (avmplus::AvmCore*)GetGCContextVariable(GCV_AVMCORE); }

        bool greedy;

        bool nogc;

        bool findUnmarkedPointers;

        bool validateDefRef;        
        bool keepDRCHistory;

        size_t collectThreshold;

        bool gcstats;

        bool dontAddToZCTDuringCollection;
        bool incrementalValidation;

#ifdef _DEBUG
        bool incrementalValidationPedantic;
#endif

        bool incremental;

        // -- Interface
        GC(GCHeap *heap);
        ~GC();
        
        void Collect();

        void MaybeGC(bool callerHasActiveRequest=false);

        enum AllocFlags
        {
            kZero=1,
            kContainsPointers=2,
            kFinalize=4,
            kRCObject=8
        };

        enum PageType
        {
            kNonGC = 0,
            kGCAllocPage = 1,
            kGCLargeAllocPageRest = 2,
            kGCLargeAllocPageFirst = 3
        };

        void *Alloc(size_t size, int flags=0);

        void *AllocAlreadyLocked(size_t size, int flags=0);

        
        void *Calloc(size_t num, size_t elsize, int flags=0);

        void Free(const void *ptr);

        static size_t Size(const void *ptr)
        {
            GCAssert(GetGC(ptr)->IsGCMemory(ptr));          
            size_t size = GCLargeAlloc::GetBlockHeader(ptr)->usableSize;
            size -= DebugSize();
            return size;

        }

        static int GetMark(const void *item);

        static int SetMark(const void *item)
        {
            GCAssert(item != NULL);
#ifdef MEMORY_INFO
            GC *gc = GetGC(item);   
            item = GetRealPointer(item);
            GCAssert(gc->IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                return GCLargeAlloc::SetMark(item);
            } else {
                return GCAlloc::SetMark(item);
            }
        }
        
        void SetQueued(const void *item)
        {
#ifdef MEMORY_INFO
            item = GetRealPointer(item);
            GCAssert(IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                GCLargeAlloc::SetQueued(item);
            } else {
                GCAlloc::SetQueued(item);
            }
        }

        static void ClearFinalized(const void *item)
        {
#ifdef MEMORY_INFO
            GC *gc = GetGC(item);   
            item = GetRealPointer(item);
            GCAssert(gc->IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                GCLargeAlloc::ClearFinalized(item);
            } else {
                GCAlloc::ClearFinalized(item);
            }
        }

        static void SetFinalize(const void *item)
        {
#ifdef MEMORY_INFO
            GC *gc = GetGC(item);   
            item = GetRealPointer(item);
            GCAssert(gc->IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                GCLargeAlloc::SetFinalize(item);
            } else {
                GCAlloc::SetFinalize(item);
            }
        }

        static int IsFinalized(const void *item)
        {
#ifdef MEMORY_INFO
            GC *gc = GetGC(item);   
            item = GetRealPointer(item);
            GCAssert(gc->IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                return GCLargeAlloc::IsFinalized(item);
            } else {
                return GCAlloc::IsFinalized(item);
            }
        }

        static int HasWeakRef(const void *item)
        {
#ifdef MEMORY_INFO
            GC *gc = GetGC(item);   
            item = GetRealPointer(item);
            GCAssert(gc->IsPointerToGCPage(item));
#endif          
            if (GCLargeAlloc::IsLargeBlock(item)) {
                return GCLargeAlloc::HasWeakRef(item);
            } else {
                return GCAlloc::HasWeakRef(item);
            }
        }

        static GC* GetGC(const void *item)
        {
            GC **gc = (GC**) ((uintptr)item&~0xfff);
            return *gc;
        }

        void* AllocBlock(int size, int pageType, bool zero=true);

        void FreeBlock(void *ptr, uint32 size);

        GCHeap *GetGCHeap() const { return heap; }

#ifdef MMGC_DRC
        void ReapZCT() { zct.Reap(); }
        bool Reaping() { return zct.reaping; }
#ifdef _DEBUG
        void RCObjectZeroCheck(RCObject *);
#endif
#endif

        bool IsPointerToGCPage(const void *item);

        void IncrementalMark();

        bool IncrementalMarking() { return marking; }

        static void WriteBarrier(const void *address, const void *value);

        static void WriteBarrierNoSub(const void *address, const void *value);

        void writeBarrier(const void *container, const void *address, const void *value)
        {
            GCAssert(!container || IsPointerToGCPage(container));
            GCAssert(((uintptr)address & 3) == 0);

            if (container) {
                GCAssert(address >= container);
                GCAssert(address < (char*)container + Size(container));
                WriteBarrierNoSubstitute(container, value);
            }
            WriteBarrierWrite(address, value);
        }

        void writeBarrierRC(const void *container, const void *address, const void *value);

        __forceinline void WriteBarrierNoSubstitute(const void *container, const void *value)
        {
            WriteBarrierTrap(container, (const void*)((uintptr)value&~7));
        }
            
        __forceinline void WriteBarrierTrap(const void *container, const void *valuePtr)
        {
            GCAssert(IsPointerToGCPage(container));
            GCAssert(((uintptr)valuePtr&7) == 0);
            GCAssert(IsPointerToGCPage(container));
            if(marking && valuePtr && GetMark(container) && IsWhite(valuePtr))
            {
                TrapWrite(container, valuePtr);
            }
        }

        void ConservativeWriteBarrierNoSubstitute(const void *address, const void *value)
        {
            if(IsPointerToGCPage(address))
                WriteBarrierNoSubstitute(FindBeginning(address), value);
        }

    private:
        __forceinline void WriteBarrierWrite(const void *address, const void *value);
        __forceinline void WriteBarrierWriteRC(const void *address, const void *value);

    public:

        bool ContainsPointers(const void *item);

        void *FindBeginning(const void *gcItem)
        {
            GCAssert(gcItem != NULL);
            GCAssert(GetPageMapValue((uintptr)gcItem) != 0);
            void *realItem = NULL;
            if((uintptr)gcItem < memStart || (uintptr)gcItem >= memEnd)
                return NULL;
            int bits = GetPageMapValue((uintptr)gcItem);
            switch(bits)
            {
            case kGCAllocPage:
                realItem = GCAlloc::FindBeginning(gcItem);
                break;
            case kGCLargeAllocPageFirst:
                realItem = GCLargeAlloc::FindBeginning(gcItem);
                break;
            case kGCLargeAllocPageRest:
                while(bits == kGCLargeAllocPageRest)
                {
                    gcItem = (void*) ((uintptr)gcItem - GCHeap::kBlockSize);
                    bits = GetPageMapValue((uintptr)gcItem);
                }
                realItem = GCLargeAlloc::FindBeginning(gcItem);
                break;
            default:
                return NULL;
            }       
#ifdef MEMORY_INFO
            realItem = GetUserPointer(realItem);
#endif
            return realItem;
        }

#ifdef MMGC_DRC
        bool IsRCObject(const void *);
#else 
        bool IsRCObject(const void *) { return false; }
#endif

        bool Collecting() const
        {
            return collecting;
        }

        bool IsGCMemory (const void *);

        bool IsQueued(const void *item);

        static uint64 GetPerformanceCounter();
        static uint64 GetPerformanceFrequency();
        
        static double duration(uint64 start) 
        {
            return (double(GC::GetPerformanceCounter() - start) * 1000) / GC::GetPerformanceFrequency();
        }

#ifndef MMGC_THREADSAFE
        void DisableThreadCheck() { disableThreadCheck = true; }
#endif

        const uint64 t0;

        // a tick is the unit of GetPerformanceCounter()
        static uint64 ticksToMicros(uint64 ticks) 
        { 
#ifdef WIN32
            return (ticks*1000000)/GetPerformanceFrequency();
#else
            return ticks;
#endif
        }


        static uint64 ticksToMillis(uint64 ticks) 
        { 
#ifdef WIN32
            return (ticks*1000)/GetPerformanceFrequency();
#else
            return ticks/1000;
#endif
        }

        uint64 bytesMarked;

        uint64 markTicks;

        // calls to mark item
        uint32 lastStartMarkIncrementCount;
        uint32 markIncrements;

        uint32 marks;

        uint32 sweeps;

        uint32 numObjects;

        uint32 objSize;

        uint64 sweepStart;

        bool hitZeroObjects;

        // called at some apropos moment from the mututor, ideally at a point
        // where all possible GC references will be below the current stack pointer
        // (ie in memory we can safely zero).  This will return right away if
        // called more than once between collections so it can safely be called
        // a lot without impacting performance
        void CleanStack(bool force=false);

        bool Destroying() { return destroying; }

        static GCWeakRef *GetWeakRef(const void *obj);

        void ClearWeakRef(const void *obj);

        uintptr GetStackTop() const;

        // for deciding a tree of things should be scanned from presweep
        void PushWorkItem(GCWorkItem &item) { PushWorkItem(m_incrementalWork, item); }

    private:

        void *heapAlloc(size_t size, bool expand=true, bool zero=true);
        void heapFree(void *ptr, size_t siz=0);

        void gclog(const char *format, ...);
        void log_mem(const char *name, size_t s, size_t comp );

        const static int kNumSizeClasses = 40;

        // FIXME: only used for FixedAlloc, GCAlloc sized dynamically
        const static int kPageUsableSpace = 3936;

        uint32 *GetBits(int numBytes, int sizeClass);

        void FreeBits(uint32 *bits, int sizeClass)
        {
#ifdef _DEBUG
            for(int i=0, n=noPointersAllocs[sizeClass]->m_numBitmapBytes; i<n;i++) GCAssert(((uint8*)bits)[i] == 0);
#endif
            *(uint32**)bits = m_bitsFreelists[sizeClass];
            m_bitsFreelists[sizeClass] = bits;
        }

        uint32 *m_bitsFreelists[kNumSizeClasses];
        uint32 *m_bitsNext;

        GCHashtable weakRefs;

        bool destroying;

        size_t heapSizeAtLastAlloc;

        // we track the top and bottom of the stack for cleaning purposes.
        // the top tells us how far up the stack as been dirtied.
        // the bottom is also tracked so we can ensure we're on the same
        // stack that the GC responsible for cleaning.  necessary if multiple
        // threads use the GC.  only thread that creates the GC will have its stack
        // tracked and cleaned.
        bool stackCleaned;
        const void *rememberedStackTop;
        const void *rememberedStackBottom;

#ifndef MMGC_THREADSAFE
        // for external which does thread safe multi-thread AS execution
        bool disableThreadCheck;
#endif

        bool marking;
        GCStack<GCWorkItem> m_incrementalWork;
        void StartIncrementalMark();
        void FinishIncrementalMark();

        int IsWhite(const void *item);
        
        uint64 lastMarkTicks;
        uint64 lastSweepTicks;

        const static int16 kSizeClasses[kNumSizeClasses];       
        const static uint8 kSizeClassIndex[246];

        void *m_contextVars[GCV_COUNT];

        // bitmap for what pages are in use, 2 bits for every page
        // 0 - not in use
        // 1 - used by GCAlloc
        // 3 - used by GCLargeAlloc

        uintptr memStart;
        uintptr memEnd;

        size_t totalGCPages;

        GCHashtable stats;
        void updateGrossMemoryStats();

        unsigned char *pageMap;

#ifdef MMGC_THREADSAFE
        mutable GCSpinLock pageMapLock;
#endif

        inline int GetPageMapValue(uintptr addr) const
        {
#ifdef MMGC_THREADSAFE
            GCAcquireSpinlock lock(pageMapLock);
#endif
            return GetPageMapValueAlreadyLocked(addr);
        }

        int GetPageMapValueAlreadyLocked(uintptr addr) const;

        void SetPageMapValue(uintptr addr, int val);

        void ClearPageMapValue(uintptr addr);

        void MarkGCPages(void *item, uint32 numpages, int val);
        void UnmarkGCPages(void *item, uint32 numpages);
        
        void ConservativeMarkRegion(const void *base, size_t bytes);

        GCAlloc *containsPointersAllocs[kNumSizeClasses];
#ifdef MMGC_DRC
        GCAlloc *containsPointersRCAllocs[kNumSizeClasses];
#endif
        GCAlloc *noPointersAllocs[kNumSizeClasses];
        GCLargeAlloc *largeAlloc;
        GCHeap *heap;
        
        void* AllocBlockIncremental(int size, bool zero=true);

        void* AllocBlockNonIncremental(int size, bool zero=true);

    protected:
        void CollectWithBookkeeping(bool callerHoldsLock,
                                    bool callerHasActiveRequest);

    private:
        void CollectImpl();

#ifdef _DEBUG
        public:
#endif

        void ClearMarks();
#ifdef _DEBUG
        private:
#endif


#ifdef _DEBUG
        public:
        // sometimes useful for mutator to call this
        void Trace(const void *stackStart=NULL, uint32 stackSize=0);
        private:
#endif

        void Finalize();
        void Sweep(bool force=false);
        void ForceSweep() { Sweep(true); }
        void Mark(GCStack<GCWorkItem> &work);
        void MarkQueueAndStack(GCStack<GCWorkItem> &work);
        void MarkItem(GCStack<GCWorkItem> &work)
        {
            GCWorkItem workitem = work.Pop();
            MarkItem(workitem, work);
        }
        void MarkItem(GCWorkItem &workitem, GCStack<GCWorkItem> &work);

        void TrapWrite(const void *black, const void *white);

        unsigned int allocsSinceCollect;

        bool collecting;
 
        bool finalizedValue;

        void AddToSmallEmptyBlockList(GCAlloc::GCBlock *b)
        {
            b->next = smallEmptyPageList;
            smallEmptyPageList = b;
        }

        GCAlloc::GCBlock *smallEmptyPageList;
        
        void AddToLargeEmptyBlockList(GCLargeAlloc::LargeBlock *lb)
        {
            lb->next = largeEmptyPageList;
            largeEmptyPageList = lb;
        }

        GCLargeAlloc::LargeBlock *largeEmptyPageList;
        
#ifdef GCHEAP_LOCK
        GCSpinLock m_rootListLock;
#endif

        GCRoot *m_roots;
        void AddRoot(GCRoot *root);
        void RemoveRoot(GCRoot *root);
        
#ifdef MMGC_THREADSAFE
        GCSpinLock m_callbackListLock;
#endif

        GCCallback *m_callbacks;
        void AddCallback(GCCallback *cb);
        void RemoveCallback(GCCallback *cb);

#ifdef MMGC_DRC
        // Deferred ref counting implementation
        ZCT zct;
        void AddToZCT(RCObject *obj) { zct.Add(obj); }
        // public for one hack from Interval.cpp - no one else should call
        // this out of the GC
public:
        void RemoveFromZCT(RCObject *obj) { zct.Remove(obj); }
private:
#endif

        static const void *Pointer(const void *p) { return (const void*)(((uintptr)p)&~7); }

#ifdef MEMORY_INFO
public:
        void DumpMemoryInfo();
private:
#endif

#ifndef MMGC_THREADSAFE
        void CheckThread();
#endif

        void PushWorkItem(GCStack<GCWorkItem> &stack, GCWorkItem item);

#ifdef DEBUGGER
        // sent for Collect (fullgc)
        // and Start/IncrementalMark/Sweep for incremental
        void StartGCActivity();
        void StopGCActivity();
        void AllocActivity(int blocks);
#endif

#ifdef _DEBUG       
        void CheckFreelist(GCAlloc *gca);
        void CheckFreelists();


        int m_gcLastStackTrace;

        void UnmarkedScan(const void *mem, size_t size);

        void FindUnmarkedPointers();

        // methods for incremental verification

        void WhitePointerScan(const void *mem, size_t size);

        void FindMissingWriteBarriers();
#ifdef WIN32
        // store a handle to the thread that create the GC to ensure thread safety
        DWORD m_gcThread;
#endif
#endif

public:
#ifdef MEMORY_INFO
        typedef void (*pDumpBackCallbackProc)(void* pContext, void *obj, const char *type );
        void DumpBackPointerChain(void *o, pDumpBackCallbackProc p = NULL, void *context = NULL);

        // debugging routine that records who marked who, can be used to
        // answer the question, how did I get marked?  also could be used to
        // find false positives by verifying the back pointer chain gets back
        // to a GC root
        static void WriteBackPointer(const void *item, const void *container, size_t itemSize);
#endif
#ifdef _DEBUG
        // Dump a list of objects that have pointers to the given location.
        void WhosPointingAtMe(void* me, int recurseDepth=0, int currentDepth=0);

        void ProbeForMatch(const void *mem, size_t size, uintptr value, int recurseDepth, int currentDepth);
#endif

        void UpdateStat(const char *key, int delta)
        {
            stats.put(key, (const void*)((size_t)stats.get(key) + delta));
        }
        
        size_t GetBytesInUse();

#ifdef MMGC_THREADSAFE
    public:
        bool IsGCRunning() const { return m_gcRunning; }

    protected:
        void OnEnterRequestAlreadyLocked()
        {
            WaitForGCDone();
            m_requestCount++;
#ifdef _DEBUG
            GCThread::GetCurrentThread()->OnEnterRequest();
#endif
        }

        void OnLeaveRequestAlreadyLocked()
        {
            GCAssert(m_requestCount > 0);
            m_requestCount--;
            if (m_requestCount == 0)
                m_condNoRequests.NotifyAll();
#ifdef _DEBUG
            GCThread::GetCurrentThread()->OnLeaveRequest();
#endif
        }

    public:
        void OnEnterRequest()
        {
            GCAutoLock _lock(m_lock);
            OnEnterRequestAlreadyLocked();
        }

        void OnLeaveRequest()
        {
            GCAutoLock _lock(m_lock);
            OnLeaveRequestAlreadyLocked();
        }

        void CollectFromRequest()
        {
            CollectWithBookkeeping(false, true);
        }

    protected:
        void WaitForGCDone()
        {
            GCAssert(m_exclusiveGCThread != GCThread::GetCurrentThread());
            while (m_exclusiveGCThread != NULL)
                m_condDone.Wait();
        }

        mutable GCLock m_lock;

        GCThread *m_exclusiveGCThread;

        bool m_gcRunning;

        GCCondition m_condDone;

        int m_requestCount;

        GCCondition m_condNoRequests;
#endif
    };

    // helper class to wipe out vtable pointer of members for DRC
    class Cleaner
    {
    public:
        Cleaner() {}
        // don't let myself move between objects
        Cleaner& operator=(const Cleaner& /*rhs*/) { return *this; }
        void set(const void * _v, size_t _size) { this->v = (int*)_v; this->size = _size; }
        ~Cleaner() { 
            if(v) 
                memset(v, 0, size);
            v = 0; 
            size = 0;
        }
        int *v;
        size_t size;
    };

    inline GCWorkItem::GCWorkItem(const void *p, uint32 s, bool isGCItem)
        : ptr(p)
        , _size(s | uint32(isGCItem))
    {
#ifdef _DEBUG
        if (IsGCItem()) {
            GCAssert(GC::GetGC(p)->FindBeginning(p) == p);
        }
#endif
    }
}

#endif /* __GC__ */

---