// 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