Tamarin::MMgc: Difference between revisions

MMgc is the Tamarin (nee Macromedia) Garbage Collector, a garbage collection library that has been built as part of the AVM2/Tamarin effort.  It is a static library that is linked into the Flash Player but kept separate, and can be incorporated into other products.  By keeping it separate, it could also theoretically be replaced in the future with a different garbage collector... we see value in making garbage control "pluggable."

MMgc is not only a garbage collector, but a general-purpose memory manager.  In the Flash Player, we use it for nearly all memory allocations.

* Managed memory is C++ operator new, with optional delete

The MMgc library is in the C++ namespace <tt>MMgc</tt>.

   GCObject* gcObject;

The class MMgc::GC is the main class of the GC.  It represents a full, self-contained instance of the garbage collector.

There are a few methods that you may need to call directly, such as <tt>Alloc</tt> and <tt>Free</tt>.   

The <tt>Alloc</tt> and <tt>Free</tt> methods are garbage-collected analogs for <tt>malloc</tt> and <tt>free</tt>.  Memory allocated with <tt>Alloc</tt> doesn't need to be explicitly freed, although it can be freed with <tt>Free</tt> if it is known that there are no other references to it.

<tt>kFinalize</tt> and <tt>kRCObject</tt> are used internally by the GC; you should not need to set them in your user code.

Given the pointer to any GCObject, it is possible to get a pointer to the GC object that allocated it.

This practice should be used sparingly, but is sometimes useful.

A basic garbage collected object.

  };

  GCWeakRef *GetWeakRef() const;

The <tt>GetWeakRef</tt> method returns a weak reference to the object.  Normally, a pointer to the object is considered a hard reference -- any such reference will prevent the object from being destroyed.  Sometimes, it is desirable to hold a pointer to a GCObject, but to let the object be destroyed if there are no other references.  GCWeakRef can be used for this purpose.  It has a <tt>get</tt> method which returns the pointer to the original object, or <tt>NULL</tt> if that object has already been destroyed.

Base class: GCObject

  };

Base class: GCFinalizedObject

If you have a pointer to a GCObject from an object in unmanaged memory, the unmanaged object must be a subclass of GCRoot.

  GCRoot(GC *gc, const void *object, size_t size);

Allocating unmanaged objects is as simple as using global operator new/delete, the same way you always have.

  MyObject* myObject = new (gc) MyObject();

There are several smart pointer templates which must be used in your C++ code to work properly with MMgc.

DWB stands for Declared Write Barrier.

  };

DRC stands for Deferred Reference Counted.

  };

DRCWB stands for Deferred Reference Counted, with Write Barrier.

  };

Write barriers are not needed for stack-based local variables, regardless of whether the object pointed to is GCObject, GCFinalizedObject, RCObject or RCFinalizedObject.  The GC marks the entire stack during collection, and not incrementally, so write barriers aren't needed.

Write barriers are not needed for C++ objects that exist purely on the stack, and never in the heap.  The Flash Player class "NativeInfo" is a good example.  Such objects are essentially the same as stack-based local variables.

All RCObjects (including all subclasses) must zero themselves out completely upon destruction. This has been done and asserts enforce it. The reason is that our collector zero's memory upon free and this was hurting us performance wise, since we need to traverse objects to decrement ref counts properly upon destruction I just made destructors do zeroing too. This mostly applies to non-pointer fields as the write barrier smart pointers do this for you.

In DEBUG builds, MMgc writes "poison" into deallocated memory as a debugging aid.  Here's what the different poison values mean:

|}

If your C++ class is a subclass of GCFinalizedObject or RCFinalizedObject, it has finalizer support.

It's best to avoid finalizers if you can, since finalization behavior can be unpredictable and nondeterministic, and also slows down the GC since the finalizers need to be invoked.

The GC routines are not currently thread safe, we're operating under the assumption that none of the player spawned threads create GC'd things.  If this isn't true we hope to eliminate other threads from doing this and if we can't do that we will be forced to make our GC thread safe, although we hope we don't have to do that.  

Threading gets more complicated because it makes sense to re-write ChunkMalloc and ChunkAllocBase to get their blocks from the GCHeap.  They can also take advantage of the 4K boundary to eliminate the 4 byte per allocation penalty.

GC bugs are hard.

If you forget to put a write barrier on a pointer, the incremental mark process might miss the pointer being changed.  The result will be an object that your code has a pointer to, but which the GC thinks is unreachable.  The GC will destroy the object, and later you will crash with a dangling pointer.

When you crash with what looks like a dangling pointer to a GC object, check for missing write barriers in the vicinity.

If you forget to put a DRC macro on a pointer to an RCObject from unmanaged memory, you can get a dangling pointer.  The reference count of the object may go to zero, and the object will be placed in the ZCT.  Later, the ZCT will be reaped and the object will be destroyed.  But you still have a pointer to it.  When you dereference the pointer later, you'll crash with a dangling pointer.

When you crash with what looks like a dangling pointer to a RC object, look at who refers to the object.  See if there are missing DRC macros that need to be put in.

If you put DWB instead of DRCWB, you'll avoid dangling pointer issues from a missing write barrier, but you might hit dangling pointer issues from a zero reference count.

If you crash with a dangling pointer to a RC object, check for DWB macros that need to be DRCWB.

If you have pointers to GC objects in your unmanaged memory objects, the unmanaged objects need to be GCRoots.

If you get a crash dereferencing a pointer to a GC object, and the pointer was a member variable in an unmanaged (non-GC) object, check whether the unmanaged object is a GCRoot.  If it isn't, maybe it needs to be.

There are some automatic aids in the MMgc library which can help you find missing write barriers.  Look in MMgc/GC.cpp.

Sometimes, this missing write barrier detection will turn up a false positive.  If you can't find anything wrong with the code, it might just be a false positive.

MMgc has several debugging aids that can be useful in your development work.

MMgc can often detect when you write outside the boundaries of an object, and will throw an assert in debugging builds when this happens.

When the application is exiting, MMgc will detect memory leaks in its unmanaged memory allocators and print out the addresses and sizes of the leaked objects, and stack traces if stack traces are enabled.

  const bool enableTraces = false;

MMgc will "poison" memory for deleted objects, and will detect if the poison has been written over by the application, which would indicate a write to a deleted object.

When <tt>#define MEMORY_INFO</tt> is on, MMgc will capture a stack trace for every object allocation.  This slows the application down but can be invaluable when debugging.  Memory leaks will be displayed with their stack trace of origin.

  xmlclass.cpp:391 toplevel.cpp:164 toplevel.cpp:507 interpreter.cpp:1098 interpreter.cpp:20 methodenv.cpp:47

If you're trying to see why memory is not getting reclaimed; GC::WhosPointingAtMe() can be called from the msvc debugger and will spit out objects that are pointing to the given memory location.

MMgc's memory profiler can display the state of your application's heap, showing the different classes of object in memory, along with object counts, byte counts, and percentage of total memory.  It can also display stack traces for where every object was allocated.  The report can be output to the console or to a file, and can be configured to be displayed pre/post sweep or via API call.

     6.5%  -  103 kb -  3311 items - avmcore.cpp:2300 abcparser.cpp:1077 …

The MMgc garbage collector uses a mark/sweep algorithm.  This is one of the most common garbage collection algorithms.

<gflash>600 300 GC.swf</gflash>

The mark sweep algorithm described above decomposes into ClearMarks/Mark/Finalize/Sweep.  In our original implementation ClearMarks/Finalize/Sweep visited every GC page and every object on that page.  3 passes!  Now we have one pass where marks are cleared during sweep so clear marks isn't needed at the start.  Also Finalize builds up a lists of pages that need sweeping so sweep doesn't need to visit every page.  This has been shown to cut the Finalize/Sweep pause in half (which happens back to back atomically).  Overall this wasn't a huge performance increase due to the fact the majority of our time is spent in the Mark phase.

MMgc is a conservative mark/sweep collector.  Conservative means that it may not reclaim all of the memory that it is possible to reclaim; it will sometimes make a "conservative" decision and not reclaim memory that might've actually been free.

It is possible that a future version of MMgc might do exact marking.  This would be needed for a generational collector.

MMgc uses Deferred Reference Counting (DRC).  DRC is a scheme for getting more immediate reclamation of objects, while still achieving high performance and getting the other benefits of garbage collection.

Previous versions of the Flash Player, up to Flash Player 7, used reference counting to track object lifetimes.

Reference counting is a kind of automatic memory management.  Reference counting can track relationships between objects, and as long as AddRef and Release are called at the proper times, can reclaim memory from objects that are no longer referenced.

Reference counting falls down when circular references occur in objects.  If object A and object B are reference counted and refer to each other, their reference counts will both be nonzero even if no other objects in the system point to them.  Locked in this embrace, they will never be destroyed.

However, reference counting is also slow because the reference counts need to be constantly maintained.  So, it's attractive to find some form of reference counting that doesn't require maintaining reference counts for every single reference.

In Deferred Reference Counting, a distinction is made between heap and stack references.

We basically ignore the stack and registers.  They are considered stack memory.

Of course, when an object's reference count goes to zero, what happens?  If the object was immediately destroyed, that could leave dangling pointers on the stack, since we didn't bump up the object's reference count when stack references were made to it.

If an object is in the ZCT, it is known that there are no heap references to it.  So, there can only be stack references to it.  MMgc scans the stack to see if there are any stack references to ZCT objects.  Any objects in the ZCT that are NOT found on the stack are deleted.

The Flash Player is frequently used for animations and video that must maintain a certain framerate to play properly.  Applications are also getting larger and larger and consuming more memory with scripting giving way to full fledged application component models (ala Flex).  Unfortunately the flash player suffers a periodic pause (at least every 60 seconds) due to garbage collection requirements that may cause unbounded pauses (the GC pause is proportional to the amount of memory the application is using).  One way to avoid this unbounded pause is to break up the work the GC needs to do into "increments".

# How much time to spend marking in each increment

A correct collector never deletes a live object (duh).  In order to be correct we must account for a new or unmarked object being stored into an object we've already marked.  In implementation terms this means a new or unmarked object is stored in an object that has already been processed by the marking algorithm and is no longer in the queue.  Unless we do something we will delete this object and leave a dangling pointer to it in its referant.  

1 and 2 are pretty well isolated.  1 is the SetSlot method in the AVM- and some assembly code in the AVM+.  #2 can be found by examining all non-const methods of GC objects (and making all fields private, something the AVM+ code base does already).  #3 is a little harder because there are a good # of GC roots.  This is an unfortunate artifact of the existing code base, the AVM+ is relatively clean and its reachability graph consists of basically 2 GC roots (the AvmCore and URLStreams) but the AVM- has a bunch (currently includes SecurityCallbackData, MovieClipLoader, CameraInstance, FAPPacket, MicrophoneInstance, CSoundChannel, URLRequest, ResponceObject, URLStream and UrlStreamSecurity).  In order to make things easier we could avoid WB's for #3 by marking the root set twice.  The first increment pushes the root set on to the queue and when the queue is empty we process the root set again, this second root set processing should very fast since the majority of objects should already be marked and the root set is usually small (marked objects are ignored and not pushed on to the work queue).  This would mean that developers would only have to take into account #2 really when writing new code.

The following Flash animation demonstrates how a write barrier works.

<gflash>600 300 GC2.swf</gflash>

To make sure that we injected write barriers into all the right places we plan on implementing a debug mode that will search for missing write barriers.  The signature of a missing write barrier is a black to white pointer that exists right before we sweep, after the sweep the pointer will point to deleted memory.  Also we can check throughout the incremental mark by making sure any black -> white pointers have been recorded by the write barrier.  Furthermore we can run this check even more frequently than every mark increment, for instance every time our GC memory allocators request a new block from our primary allocator (the way our extremely helpful greedy collection mode works).  This would of course be slow but with good code coverage should be capable of finding all missing write barriers.  Only checking for missing write barriers before every sweep will probably be a small enough performance impact to enable it in DEBUG builds.  The more frequent ones will have to be turned on manually.

There are a couple options for implementing write barriers.  At the finest level of granularity everytime a a white object is written to a black object we push the white object onto the work queue (thus making it grey).  Another solution is to put the black object on the work queue, thus if multiple writes occur to the black object we only needed one push on the the queue.  This could be a significant speedup if the black object was a large array getting populated with a bunch of new objects.  On the other hand if the black is a huge array and only a couple slots had new objects written to them we are wasting time by marking the whole thing.

A popular solution to this is what's called card marking.  Here you divide memory into "cards" and when a white object is written to a black object you mark the card containing the slot the pointer to the white object was written to.  After all marking is done you circle back and remark the black portion of any card that was flagged by the write barrier.  There are two techniques to optimize this process.  One is to save all the addresses of all pages that had cards marked (so you don't have to bring every page into memory to check its hand, so to speak).  Another option is to check every page while doing the normal marking and it any of its cards where flagged handle them immediately since your already reading/writing from that page.  The result will be at the end of the mark cycle fewer things need to be marked.  These two optimizations can be combined.

Increment Time Slice

If we don't maintain the frame rate the movie will appear to pause and if we don't mark fast enough the mutator could get ahread of the collector and allocate memory so fast that the collection never finishes and memory grows unbounded.  The ideal solution will result in only one mark incremental per frame unless the mutator is allocating memory so fast we need to mark more aggressively to get to the sweep.  So the frequency of the incremental marking will be based on two factors: the rate at which we can trace memory and the rate at which the mutator is requesting more memory.  Study of real world apps will be used to determine how best to factor these to rates together.

The GC library has a tiered memory allocation strategy, consisting of 3 parts:

When you want to allocate something we figure out what size class it's in and then ask that allocator for the memory.  Each fixed size allocator maintains a doubly linked list of 4K blocks that it obtains from the <code>GCHeap</code>.  These 4K blocks are aligned on 4K boundaries so we can easily allocate everything on 8-byte boundaries (a necessary consequence of the 32-bit atom design-- 3 type bits and 29 pointer bits).  Also we store the <code>GCAlloc::GCBlock</code> structure at the beginning of the 4K block so each allocation doesn't need a pointer to its block (just zero the lower 12 bits of any GC-allocated thing to get the <code>GCBlock</code> pointer).  The <code>GCBlock</code> contains bitmaps for marking and indicating if an item has a destructor that needs to be called (a <code>GCFinalizedObject</code> base class exists defining a virtual destructor for GC items that need it).  Deleted items are stored in a per-block free list which is used if there are any otherwise we get the next free item at the end.  If we don't have anything free and we reach the end, we get another block from the Heap.

GCHeap reserves 16 MB of address space per heap region. The goal of reserving so much address space is so that subsequent expansions of the heap are able to obtain contiguous memory blocks. If we can keep the heap contiguous, that reduces fragmentation and the possibility of many small "Balkanized" heap regions.

GCHeap serves up 4K blocks to the size class allocators or groups of continguous 4K blocks for requests from the large allocator.  It maintains a free list and blocks are coalesced with their neighbors when freed.  If we use up the 16 MB reserved chunk we reserve another one, contiguously with the previous if possible.

GCHeap can fall back on a malloc/free approach for obtaining memory if a memory mapping API like VirtualAlloc or mmap is not available. In this case, GCHeap will allocate exactly as much memory as is requested when the heap is expanded and not try to reserve additional memory pages to expand into. GCHeap won't attempt to allocate contiguous regions in this case.

We currently use VirtualAlloc for Windows (supported on all flavors of Windows back to 95), mmap on Mach-O and Linux. On Classic and Carbon, we do not currently use a memory mapping strategy... these implementations are calling MPAllocAligned, which can allocate 4096-byte aligned memory. We could potentially bind to the Mach-O Framework dynamically from Carbon, if the user's system is Mac OS X, and call mmap/munmap.