Hello everyone,
For your consideration.
A more expansive garbage collection proposal --
I think we ought to unify our garbage collection scheme, and I propose
that we use either the attached collector or something similar. This GC
would run concurrently with the rest of the program and require some
basic support from the objects code, as I'll explain. The following
classes are defined:
GC -- the garbage collector itself, a singleton accessed only through
static functions.
GC_runner -- Also a singleton, this is the thread which runs
continuously for garbage collecting.
GcResource -- the base class from which (I think) all objects which
might ever be dynamically allocated ought to derive.
GcInvoke -- Explained in the How To Use section, this is a mechanism to
allow the GC to run concurrently.
ModifyLock -- A typedef to a boost scoped_lock
ModifySync -- a typedef to a boost mutex
Allocation of new memory
========================
1) When a new object is dynamically allocated, its memory address is
added to a list of objects allocated in this thread. When all objects
which will be allocated at a certain point (defined by GcInvoke and in
the 'How to Use' section) are finished constructing, these objects are
added to the list of resources maintained by the garbage collector.
This ensures that new objects are not recycled before they have a chance
to become reachable.
2) When a new object is added to the list of GcResources, it goes into a
list of new additions. This may happen from (1), or it may be done
directly -- doing so directly is more expensive if multiple allocations
are being done, as at parsing time.
Marking reachable objects
=========================
1) When the collector wants to mark the reachable objects, it first
moves all objects from the new additions list into its list of managed
memory.
2) Beginning from the roots (see the 'How to Use' section), all
reachable memory is marked. When an object is seen for a second time in
the marking, it is not re-marked. This avoids loops.
3) While the objects are being marked, new objects may be added to the
Gc, since these will go on the 'new additions' list -- they may be
marked, but they won't be collected.
Removing unreachable objects
============================
1) All objects in the list of managed memory which are not marked as
reachable are removed.
How To Use
==========
Allocating new GcResources
==========================
A GcInvoke object should be on the stack when new GcResource objects are
heap allocated. The GcInvoke object either 'on' or 'off'. ('on' is the
default). If it is on, the newly allocated memory will be managed by the
Gc. If it is off, the newly allocated memory must be managed by hand.
When all GcInvoke objects have gone out of scope (they may be nested),
any GcResource objects which were heap allocated in the scope of an 'on'
GcInvoke is added to the list of managed objects.
By constructing in this way, the newly allocated resources don't face
the possibility of collection until they have had a chance to be placed
into a reachable state. With a single-threaded GC this is not a
problem, but since the collection happens concurrently, it otherwise
risks this:
SomeGcClass *p = new SomeGcClass;
/* At this point, or perhaps even during the construction of p, the
GC finishes its last run and beings a new run. Since p has been put into
the new list of memory at allocation time (not at the finish of
construction), it is in the memory list but not reachable, so it may be
destroyed during construction, or: */
/* p is DESTROYED here by the Gc, since it isn't reachable (no root)
*/
p->do_something();
/* or maybe p is DESTROYED here by the Gc. */
this->markable_member = p;
/* Whew! p is finally safe, right? Only if 'this' is safe and
unmarked in this GC cycle. */
Instead, the following code is used:
{ // Scope.
GcInvoke GcI;
SomeGcClass *p = new SomeGcClass;
p->do_something();
this->markable_member = p;
/* It would be safe to manage p from here, if it is safe to manage
'this' */
} /* GcInvoke falls out of scope. 'p' is as safe as 'this'. Since
GcInvoke objects stack, 'p' is only managed once 'this' is managed. */
A Caveat: It is NOT safe to spawn a new thread inside the scope of a
GcInvoke. (Strictly speaking, any dynamic resources allocated in a
spawned thread must provide for their own safety, and not rely on
'this'.)
Marking GcResources
===================
Objects do not need to be immutable while they are being marked, except
that the _structure_ of any containers which hold GcResource objects
must not be changed while the object is being marked.
There are three functions (with some variants) used to make this
possible, all defined in GcResource:
1) mark(const GcResource*); -- This marks a single contained resource.
It is NOT safe to mark a resource in this way:
if (p) p->setReachable();
because 'p' may be invalidated between 'if (p)' and 'p->'.
2) markContainer(...); -- This marks all resources in an iterable
container. It requires that a mutex be passed to it, with which it will
lock the container until it has copied a list of the pointers. This
should be the same mutex that locks any modificactions to the container
structure (see 'Needed Support').
3) markRContainer(...); -- This is the same as markContainer, but the
Container must be locked any time it OR its contents are modified. These
are containers which contain instances of GcResource objects, and not
pointers to them. These may still need to be marked to keep other
resources reachable.
4) markMap(...); -- This is the same as markContainer, but the resources
of a map are stored in a pair. This function just adds '->second' to
find the resource, rather than the pair object.
Running the GC
==============
The garbage collector runs concurrently and self-constructs when the
first manageable memory is allocated. It may never be destroyed,
although it may have its memory cleared (call 'obliterateResources' --
the name is a warning).
Calling 'collectSoon' will schedule the GC to run the next time that its
thread is awakened.
Calling 'pause' will force the GC to finish its current collection (the
caller waits for this) and not to begin any new collections until
'resume' is called. Maybe useful in special cases, but ordinarily should
not be used.
Calling 'manage' with a GcResource will cause that resource to be
managed -- this might be needed if the resource was allocated in an
'off' GcInvoke and now needs to change its mind. It is cheaper and
safer to use the GcInvoke structure to manage memory, so this is another
specialty function.
Needed Support
==============
Only heap allocate GcResources within the scope of a GcInvoke object.
Don't spawn threads in the scope of a GcInvoke object.
Call 'touch' on any resources you receive from outside and store in
'this'. E.g.:
void someResourceClass::setMyPtr(GcResource *p) { p->touch(); m_p = p; }
Use a ModifyLock to lock any containers which contain GcResources before
modifying their structure. Lock them before modifying their contents if
they contain objects and not pointers.
Define a function 'void markResources() const' which uses the 'mark',
and 'mark*' variants to mark all of its contained resources.
Correctness, Aggressiveness of the Algorithm
============================================
The scheme used is essentially a tri-color marking scheme. See
http://www.memorymanagement.org/glossary/t.html#tri-color.marking
In this terminology:
Objects are black until they have been released into the GC (GcInvoke
scheme).
Objects are white when their parity doesn't match that of the GC, or
when their reachable flag is off. The parity avoids a need to keep a
list of all objects. This allows GcResource objects to be stack
allocated when this makes better sense.
Objects are gray after setReachable is called in them. Since
markResources calls setReachable in all contained resources, the object
is black when this function returns. In effect, only roots ever remain
gray, since all other gray objects are black by the time that marking
them gray has returned. To maintain the tri-color invariant, no white
sub-resources may be added to a black object. In order to not violate
the invariant, any added resources are tinted gray by the 'touch'
function. (This function adds them as root objects to the GC to color
them gray, and the GC removes them from the root list once it makes them
black.)
It is possible that some objects which are not reachable will escape
collection for one cycle of collection. This may occur if a resource is
touched, and then subsequently discarded. Since it was touched, it is a
root until the finish of the GC run, and so it will not be collected on
that run.
Drawbacks of the system
=======================
The biggest drawback is that all objects which store GcResource objects
must themselves be GcResource objects. This could be changed by
introducing a common base class for GcResource objects and 'roots' of
GcResource objects, but I recommend against this. Since GcResource
objects may be stack allocated under this scheme with minimal overhead,
this is probably not as big a problem as it sounds.
Non-deterministic collection -- because the GC runs concurrently, it is
not possible to know exactly when a given object will be collected. It
would be possible to write a method to allow explicit deletion, but this
would require one of two things:
linear time deletion of the resource
storage of an iterator in all resources to allow constant-time deletions
In either case, if you really know that it is safe to delete an object,
you should probably either stack allocate it or use the GcInvoke scheme
to manage it yourself from the beginning.
Complexity -- Although I have designed the mechanisms to be as straight
forward as I could, they require discipline in their use. I would
welcome any suggestions about how to better structure these, as I can
only write them in a way that seems most straightforward to me --
someone else may have a better idea.
Benefits of the system
======================
Safety -- the current system disallows the stack allocation of
resources, but there is no C++ language feature to enforce this. This
restriction may be violated by a fully ISO-compliant compiler, so this
is a portability issue as well. (Even a private constructor may be
accessed by another member of the same class, and this solution would
require a factory for each type of object.)
Unification -- all garbage collected resources would be managed under a
single system.
Configurability -- This would allow easier control of memory issues. As
an example, the 'new' operator could be specialized to allow the
run-time limiting of heap size or block allocations for the heap. The GC
could be tested under various scenarios for the optimal times to
collect, since scheduling a collection does not make the caller wait.
Responsiveness -- Because this GC runs concurrently with the rest of
Gnash, it is not necessary to pause the program in order to collect
garbage. This will result in greater responsivity of the program in
some instances.
// GC.h: Garbage Collector for Gnash
//
// Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
#ifndef GNASH_GC_H
#define GNASH_GC_H
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include <cassert>
#include <list>
#include <vector>
#include <boost/thread.hpp>
#define GCDEBUG
namespace gnash {
class GC;
class GcResource;
class GC_runner;
class GcInvoke;
typedef std::list<const GcResource*> GcResourceList;
/// The garbage collector.
class GC
{
public:
// The GC_runner class is responsible for managing the GC thread,
// and so it is a friend.
friend class GC_runner;
// Calling manage with a GcResource will put that resource
// under the management of the GC. This gives the GC the
// right to delete it, so don't manage stack allocated resources,
// and be sure that managed objects have a root which can access
// them.
static void manage(const GcResource* g);
// This version of manage takes a GcResourceList* and manages
// all objects up to but not including the passed iter,
// which should be in the list.
static void manage(GcResourceList*, GcResourceList::iterator);
// Call preManage is done to put the GcResource* into a special
// list that will be processed later for managing. This allows
// the objects to be assigned to roots before they face the
// possibility of collection. Let GcResource objects do this
// themselves, unless you have strange needs.
static void preManage(const GcResource* g);
// The GC should not ordinarily be invoked directly -- it will
// decide when to collect, but there may be times when some other
// portion of the program knows that collection would be good.
// This function lets the garbage collector know about those times.
static void collectSoon();
// This will destroy all managed memory. It will also destroy all
// hope of the program functioning correctly unless _no_ managed
// resources are valid any more. Do you really know this?
// If permanent is true, the GC will not be restarted until
// resume() is called.
static void obliterateResources(bool permanent);
// Some resources are top-level and know about other resources
// and should not themselves be collected. Use this function to
// let the GC know about these objects.
static void addRoot(const GcResource* g);
// The opposite of AddRoot, this will remove the resource from the
// list of roots. This may expose that resource to immediate
// collection!
static void removeRoot(const GcResource* g);
// Use this function with care -- it will pause the calling thread
// until the current collection is finished. Afterwards, the
// GC will not do any collections until resume() is called, but it
// _will_ continue to track new resources.
//
// If you want to stop the GC from tracking some new
// resources, this is not the right function. Use the GcInvoke
// object instead, like this:
// { // I don't want these resources managed. Scoping to be kind.
// GcInvoke GcI(false);
// /* Code which creates unmanaged resources goes here. */
// } // GcInvoke falls out of scale, GC reverts to previous behavior.
// GcInvoke works properly even if nested.
static void pause();
// If the GC has been paused, this will cause it to restart collections.
static void resume();
// This has the effect of making the object a root for one run of the GC.
static void addTouch(const GcResource* g);
private:
// This function begins the actual work of collecting.
void collect();
// Mark all reachable resources.
void markReachableResources();
// Clean out the unreachable resources.
void cleanUnreachableResources();
// We use an actual object, and so we need a way to construct it.
static void initialize();
// Only the initialize function should construct a GC.
GC();
// The static GC functions need to know where to find the GC object
// and be sure that it is initialized correctly.
static GC* getGC();
// Change this where it is set to change the behavior of the GC.
// The GC will never run itself if there is not this much newly
// managed memory, unless CollectSoon() has been called.
static const unsigned int mAutoTriggerSize;
// There is no need to access this directly, as all functions intended
// for outside use are static.
static GC* m_TheGC;
// Keep track of how many new additions there have been since the
// last collection cycle. In the presence of a concurrent GC, this
// may not be the right model to use, but it will take some trials
// to determine how to improve this.
unsigned int m_new_additions;
// These lists contain the managed data.
// m_res_list_add is data which has never been marked.
// m_res_list_mark is data which is part of the mark/sweep cycle.
// m_root_list is resources which can vouch for themselves.
std::list<const GcResource*> m_res_list_add;
std::list<const GcResource*> m_res_list_mark;
std::list<const GcResource*> m_root_list;
// This mutex is used to safely manage new resources. It is not
// used during mark/sweep, except to transfer the list of newly
// managed resources to the list of known resources. Its ordinary
// use is on the addition of a new resource.
boost::mutex m_res_mutex;
// This mutex is used to safely add and remove new roots.
boost::mutex m_root_mutex;
// This mutex is used to allow only one collection at a time.
boost::mutex m_collect_mutex;
// If this is true, we are scheduled for a collection.
bool m_collect;
// If this is true, we are scheduled to shut down. Don't start any
// new collections.
bool m_shutdown;
// We need to know who is running the GC so that the thread can
// be joined when the GC is shut down.
boost::thread* m_runner;
bool m_parity;
};
/// Any object which should have its memory managed by the Garbage
/// Collector or act as a root for objects which can should be a
/// GcResource descendant.
class GcResource
{
public:
// The Gc is our friend.
friend class GC;
// Mark this resource as relevant.
void markReachable(bool parity) const
{
if (!m_ever_marked)
m_gc_parity = parity;
else if (m_gc_parity == parity)
{
return; // Avoid recursive marking.
}
m_gc_parity = parity;
m_reachable = true;
markResources();
}
// Clear the relevance of this resource, usually to prepare
// for marking.
void clearReachable() const
{ m_reachable = false; }
// Is this resource reachable?
bool isReachable() const { return m_reachable; }
// The new operator is overloaded so that heap allocated resources
// can be managed. This is the whole point of the class.
// inlined below
void* operator new(unsigned int num_bytes);
// Any time we have a new operator, we need a delete operator.
// inlined below
void operator delete(void *p);
// Marking a GcResource object directly is only safe if
// the pointer to the object never changes. Otherwise,
// it may cause an invalid reference call and corrupt good
// data. Use mark instead.
//
// Heed the volatile mark on h, and don't eliminate it!
void mark(const GcResource* g) const
{
const volatile GcResource* h = g;
if (h)
(const_cast<GcResource*> (h))->markReachable(m_gc_parity);
}
// ModifyLock is used to lock the object if we are going to
// do something which might invalidate access to markable
// data. The ordinary case in which this arises is when
// a list of markable data is maintained. If the list is
// modified while mark is traversing it, bad things may happen.
// Note that single pointers may be used without any locking,
// since access to them is not invalidated by assignment.
// To avoid threading problems, use the locking in only the
// following way:
// { // Note the block opener.
// ModifyLock aLock(mSync);
// // Some code which modifies a list goes here.
// } // Note the block closer.
// Beginning a new block causes the lock to fall out of scope
// and open as soon as the list modifier is done.
// Note: It is not necessary to lock before modifying a
// resource, only to modify a container of resources.
typedef boost::mutex::scoped_lock ModifyLock;
typedef boost::mutex ModifySync;
// Marking a GcResource container may be a problem if the list is
// modified while it is being marked. This function automatically
// locks the container before marking it. Note that in order for this
// function to work, any functions which modify the container must also
// lock it using the same object passed as pSync.
template<class T, class T_iter> void markContainer(const T *gContainer,
ModifySync *pSync) const;
// The same function, except that the values contained are references,
// instead of pointers. This keeps the container locked for longer.
template<class T, class T_iter> void markRContainer(const T *gContainer,
ModifySync *pSync) const;
// Marking a map is so different that we provide a special function to
// do so. Only the value will be marked, not the keys.
template<class T, class T_iter> void markMap(const T *gMap,
ModifySync *pSync) const;
// Construct the resource. There is no way to construct a resource
// as a root -- use enableRoot() instead.
GcResource() :
m_reachable(false), m_is_a_root(false), m_ever_marked(false),
m_gc_parity(false) // Just pick a parity -- it doesn't matter.
{/**/}
// Copy a resource -- this should be separately managed from the
// resource of which it is a copy, so make sure it is set this way.
GcResource(const GcResource& /*g*/) :
m_reachable(false), m_is_a_root(false), m_ever_marked(false),
m_gc_parity(false)
{/**/}
// Resource assignment -- this resource should not take the
// resource values from the other object, but maintain its own.
GcResource& operator=(const GcResource& /*g*/)
{ /*No modification of manage data.*/ return *this; }
// GcResource will remove itself from the Garbage collector if
// it is a root object when it is destroyed. This need not be
// done manually. Don't destroy managed objects yourself.
virtual ~GcResource();
// isRoot() tells us whether or not this is a root.
bool isRoot() const { return m_is_a_root; }
// enableRoot() will allow this object to vouch for the
// usefulness of any objects it wants to. Calling this multiple
// times is a waste of time, but otherwise harmless.
// disableRoot() will do the opposite, and this can also be
// set at construction time.
void enableRoot()
{ if (m_is_a_root) return; m_is_a_root = true; GC::addRoot(this); }
// disableRoot() will prevent this object from vouching
// for the usefulness of any other objects. If this object
// is itself a collectible resource, this may result in its
// eventual destruction, since it won't vouch for itself either.
void disableRoot()
{ if (!m_is_a_root) return; m_is_a_root = false; GC::removeRoot(this); }
// touch() lets the GC know that the object has been updated since the
// last time that it was read, and so it needs itself read again.
// Do this before you invalidate it, not after!
// Because of Timing Issues, this may add itself to the GC touch list
// twice, but this is okay, since the GC will realize that it has
// been marked already.
void touch()
{ if (m_touched || m_is_a_root) return; m_touched = true; GC::addTouch(this); }
protected:
// This allows the root to vouch for the usefulness of objects.
// The object itself is already marked as reachable -- use this
// to mark owned objects, by calling mark, markList, markContainer,
// or in the unusual cases writing your own safe marker.
virtual void markResources() const { }
private:
// true if the object is reachable, false if the object is not.
mutable bool m_reachable;
// true if the object is a root, false if it is not.
bool m_is_a_root;
// true if the object has ever been marked, otherwise false.
mutable bool m_ever_marked;
// The parity of the garbage collection run. In conjunction
// with m_ever_marked, this avoids repeated recursive markings.
mutable bool m_gc_parity;
// The object has been touched since the last time it was
// read. This is used to avoid accessing the GC unnecessarily,
// since adding a touch will lock the GC mutex.
mutable bool m_touched;
};
class GcInvoke
{
public:
GcInvoke(bool manage = true)
{ GcInvoke::enter(manage, &m_manage, &m_iter); }
~GcInvoke()
{ GcInvoke::leave(this); }
#ifndef NDEBUG
#ifdef GCDEBUG
// This will help you make sure that all of your code is wrapped
// properly, but the code is faster without it, and it provides
// nothing but checking.
static bool isOn();
#endif /* GCDEBUG */
#endif /* !NDEBUG */
private:
// Know that we are in an invoke, and how we want to handle it.
static void enter(bool manage, bool *store_old,
GcResourceList::iterator *iter);
// We are leaving the invoke.
static void leave(GcInvoke *p);
// Heap creation is not allowed. This would defeat the whole point.
void* operator new(unsigned int) throw()
{ assert(0); throw(1); return NULL; }
// The management state to return to when we exit.
bool m_manage;
// A pointer into the list to which we are attached.
GcResourceList::iterator m_iter;
};
template<class T, class T_iter> inline void
GcResource::markContainer(const T *gContainer, ModifySync *pSync) const
{
if (!gContainer)
return;
T gCopy;
// Scope to lock.
{
ModifyLock aLock(*pSync);
gCopy = *gContainer;
}
T_iter i = gCopy.begin();
T_iter j = gCopy.end();
for (/**/; i != j; ++i)
{
(*i)->markReachable(m_gc_parity);
}
}
template<class T, class T_iter> inline void
GcResource::markRContainer(const T* gContainer, ModifySync *pSync) const
{
if (!gContainer)
return;
T gCopy;
// Scope to lock.
{
ModifyLock aLock(*pSync);
gCopy = *gContainer;
}
T_iter i = gCopy.begin();
T_iter j = gCopy.end();
for (/**/; i != j; ++i)
{
(*i).markReachable(m_gc_parity);
}
}
template<class T, class T_iter> inline void
GcResource::markMap(const T *gMap, ModifySync *pSync) const
{
if (!gMap)
return;
std::vector<const GcResource*> gCopy;
// Scope to lock.
{
ModifyLock aLock(*pSync);
gCopy.reserve(gMap->size());
T_iter i = gMap->begin();
T_iter j = gMap->end();
for (/**/; i != j; ++i)
{
gCopy.push_back(i->second);
}
} // Unlock.
std::vector<const GcResource*>::iterator i = gCopy.begin();
std::vector<const GcResource*>::iterator j = gCopy.end();
for (/**/; i != j; ++i)
{
(*i)->markReachable(m_gc_parity);
}
}
inline void*
GcResource::operator new(unsigned int num_bytes)
{
#ifndef NDEBUG
#ifdef GCDEBUG /* Can be off even if NDEBUG is on. */
assert(GcInvoke::isOn());
#endif /* GCDEBUG */
#endif /* !NDEBUG */
void* p = malloc(num_bytes);
GC::preManage(static_cast<const GcResource*>(p));
return p;
}
inline void
GcResource::operator delete(void *p)
{
free(p);
}
} // namespace gnash
#endif // GNASH_GC_H
// GC.cpp: Garbage Collector for Gnash
//
// Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
#include "GC.h"
#include <boost/thread/tss.hpp>
#include <boost/thread/once.hpp>
namespace gnash {
// Only initialize the GC once.
static boost::once_flag once = BOOST_ONCE_INIT;
// Track additions to the list since it was pushed to the GC
// here.
static boost::thread_specific_ptr<GcResourceList> GcPendingList;
static boost::thread_specific_ptr<bool> GcManageInvoke;
// Only track our depth if we are debugging.
#ifndef NDEBUG
#ifdef GCDEBUG
static boost::thread_specific_ptr<int> GcInvokeDepth;
bool
GcInvoke::isOn()
{
return true;
if (GcInvokeDepth.get() == NULL)
{
GcInvokeDepth.reset(new int(0));
return false;
}
return *GcInvokeDepth > 0;
}
#endif /* GCDEBUG */
#endif /* !NDEBUG */
void
GcInvoke::enter(bool manage, bool *store_old, GcResourceList::iterator *iter)
{
if (GcManageInvoke.get() == NULL)
{
GcManageInvoke.reset(new bool(manage));
*store_old = false;
}
else
{
*store_old = *GcManageInvoke;
*GcManageInvoke = manage;
}
#ifndef NDEBUG
#ifdef GCDEBUG
if (GcInvokeDepth.get() == NULL)
{
GcInvokeDepth.reset(new int(0));
}
++(*GcInvokeDepth);
#endif /* GCDEBUG */
#endif /* !NDEBUG */
if (GcPendingList.get() == NULL)
{
GcPendingList.reset(new GcResourceList);
}
*iter = GcPendingList->begin();
}
void
GcInvoke::leave(GcInvoke *pInvoke)
{
// Our usual checks aren't necessary, since we did them in enter.
(*GcManageInvoke) = pInvoke->m_manage;
#ifndef NDEBUG
#ifdef GCDEBUG
--(*GcInvokeDepth);
#endif /* GCDEBUG */
#endif /* !NDEBUG */
// Add the managed stuff to the Gc, but only if we are depthless.
// Don't erase -- the GC will do that by using splice()
if (pInvoke->m_iter == GcPendingList->end())
{
GC::manage(GcPendingList.get(), pInvoke->m_iter);
}
}
// This is a function object whose sole job is to make sure that the
// garbage collector runs.
class GC_runner
{
public:
GC_runner(GC* g) : mGC(g) { }
void operator()()
{
while (1)
{
if (mGC->m_shutdown)
return;
if (!mGC->m_collect)
boost::thread::yield();
else
mGC->collect();
}
}
static boost::thread* begin(GC* g)
{
GC_runner runit(g);
boost::thread *f = new boost::thread(runit);
return f;
}
private:
GC* mGC;
};
// Define the static data members declared in the definition of GC.
// If we have 10 new resources, trigger an automatic collection.
// Try different values of this to opitmize the GC.
const unsigned int GC::mAutoTriggerSize = 10;
// Although the externally useful functions are static, we operate on an
// actual object.
GC* GC::m_TheGC = NULL;
GC* GC::getGC()
{
boost::call_once(&GC::initialize, once);
return m_TheGC;
}
// Constructor of the GC.
// This is called once in the whole program. Please don't inline it.
GC::GC() :
m_new_additions(0),
m_res_list_add(),
m_res_list_mark(),
m_root_list(),
m_res_mutex(),
m_root_mutex(),
m_collect_mutex(),
m_collect(false),
m_shutdown(false),
m_runner(NULL),
m_parity(false)
{ }
// This constructs a garbage collector and starts a collection thread.
void
GC::initialize()
{
m_TheGC = new GC;
m_TheGC->m_runner = GC_runner::begin(m_TheGC);
}
// This puts resources into a thread local list before management.
void
GC::preManage(const GcResource* g)
{
// We don't manage if there's no invoker. This results in
// bad memory management, but not a segfault.
if (GcManageInvoke.get() == NULL)
{
GcManageInvoke.reset(new bool(false));
}
if (!(*GcManageInvoke))
return; // Nothing to do for unmanaged memory.
if (GcPendingList.get() == NULL)
{
GcPendingList.reset(new GcResourceList);
}
GcPendingList->push_front(g);
}
// This puts resources under management.
void
GC::manage(const GcResource* g)
{
GC *gc = getGC();
// If we don't lock the addition list, how do we know this is safe?
{ // So we lock it.
boost::mutex::scoped_lock aLock(gc->m_res_mutex);
gc->m_res_list_add.push_back(g);
++gc->m_new_additions;
}
if (gc->m_new_additions > mAutoTriggerSize)
GC::collectSoon();
}
// This puts a list of resources under management.
void
GC::manage(GcResourceList *pList, GcResourceList::iterator iter_end)
{
GC *gc = getGC();
{ // Scope for locking.
boost::mutex::scoped_lock aLock(gc->m_res_mutex);
// Count them, for new addition tracking. SPEED: Eliminate this.
for (GcResourceList::iterator i = pList->begin(); i != iter_end; ++i)
++gc->m_new_additions;
gc->m_res_list_add.splice(gc->m_res_list_add.end(),
*pList, pList->begin(), iter_end);
}
if (gc->m_new_additions > mAutoTriggerSize)
GC::collectSoon();
}
// Set the collector to run.
void
GC::collectSoon()
{
GC *gc = getGC();
gc->m_collect = true;
}
// Destroy everything we can lay our hands on.
void
GC::obliterateResources(bool permanent)
{
GC *g = getGC();
boost::mutex::scoped_lock aLock(g->m_res_mutex);
g->m_shutdown = true;
if (g->m_runner)
g->m_runner->join();
delete g->m_runner;
std::list<const GcResource*>::iterator i;
for (i = g->m_res_list_mark.begin(); i != g->m_res_list_mark.end(); ++i)
{
delete *i;
}
for (i = g->m_res_list_add.begin(); i != g->m_res_list_add.end(); ++i)
{
delete *i;
}
g->m_res_list_add.erase(g->m_res_list_add.begin(),
g->m_res_list_add.end());
g->m_res_list_mark.erase(g->m_res_list_mark.begin(),
g->m_res_list_mark.end());
g->m_new_additions = 0;
if (!permanent)
{
g->m_shutdown = false;
g->m_runner = GC_runner::begin(g);
}
}
// Add a root to the garbage collector.
void
GC::addRoot(const GcResource* g)
{
GC *gc = getGC();
{
boost::mutex::scoped_lock aLock(gc->m_root_mutex);
gc->m_root_list.push_back(g);
}
}
// Remove a root from the garbage collector.
void
GC::removeRoot(const GcResource* g)
{
GC *gc = getGC();
{
boost::mutex::scoped_lock aLock(gc->m_root_mutex);
std::list<const GcResource*>::iterator i;
i = std::find(gc->m_root_list.begin(), gc->m_root_list.end(), g);
if (i != gc->m_root_list.end())
gc->m_root_list.erase(i);
}
}
// Pause the GC, as explained in the header.
void
GC::pause()
{
GC *g = getGC();
boost::mutex::scoped_lock aLock(g->m_res_mutex);
g->m_shutdown = true;
if (g->m_runner)
g->m_runner->join();
delete g->m_runner;
}
// Resume the GC, after a pause.
void
GC::resume()
{
GC *g = getGC();
if (g->m_runner)
return; // Already running.
{ // Scoping.
boost::mutex::scoped_lock aLock(g->m_collect_mutex);
g->m_shutdown = false;
g->m_runner = GC_runner::begin(g);
}
}
// Add a one-time use root.
void
GC::addTouch(const GcResource* g)
{
addRoot(g);
}
// Collect garbage.
void
GC::collect()
{
boost::mutex::scoped_lock bLock(m_collect_mutex);
m_parity = !m_parity; // To avoid recursive markings.
m_collect = false;
{ // Scope for quick unlocking.
boost::mutex::scoped_lock aLock(m_res_mutex);
// Splice from the new additions onto the known ones.
// This does not invalidate the iterators of the new
// additions -- it moves them from one list to the other.
m_res_list_mark.splice(m_res_list_mark.end(), m_res_list_add,
m_res_list_add.begin(), m_res_list_add.end());
m_new_additions = 0;
} // The lock falls out of scope, allowing new additions while we work.
markReachableResources();
cleanUnreachableResources();
}
// Mark all of the resources which can be reached from the roots.
void
GC::markReachableResources()
{
std::list<const GcResource*>::iterator i;
i = m_root_list.begin();
while (i != m_root_list.end())
{
(*i)->markReachable(m_parity);
// Remove any temporary roots.
if (!(*i)->m_is_a_root)
{
(*i)->m_touched = false;
{
boost::mutex::scoped_lock aLock(m_root_mutex);
i = m_root_list.erase(i);
}
}
else
++i;
}
}
// Destroy any resources that weren't reached in marking.
void
GC::cleanUnreachableResources()
{
std::list<const GcResource*>::iterator i;
for (i = m_res_list_mark.begin(); i != m_res_list_mark.end(); /**/)
{
if (!(*i)->isReachable())
{
delete *i;
i = m_res_list_mark.erase(i);
}
else
{
(*i)->clearReachable();
++i;
}
}
}
GcResource::~GcResource()
{
if (isRoot())
disableRoot();
}
} // namespace gnash
_______________________________________________
Gnash-dev mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/gnash-dev
