GCNode.hpp

Go to the documentation of this file.

/*CXXR $Id: GCNode.hpp 1390 2013-06-11 14:41:41Z arr $
 *CXXR
 *CXXR This file is part of CXXR, a project to refactor the R interpreter
 *CXXR into C++.  It may consist in whole or in part of program code and
 *CXXR documentation taken from the R project itself, incorporated into
 *CXXR CXXR (and possibly MODIFIED) under the terms of the GNU General Public
 *CXXR Licence.
 *CXXR 
 *CXXR CXXR is Copyright (C) 2008-13 Andrew R. Runnalls, subject to such other
 *CXXR copyrights and copyright restrictions as may be stated below.
 *CXXR 
 *CXXR CXXR is not part of the R project, and bugs and other issues should
 *CXXR not be reported via r-bugs or other R project channels; instead refer
 *CXXR to the CXXR website.
 *CXXR */

/*
 *  R : A Computer Language for Statistical Data Analysis
 *  Copyright (C) 1995, 1996  Robert Gentleman and Ross Ihaka
 *  Copyright (C) 1999-2006   The R Development Core Team.
 *
 *  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 2.1 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 Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, a copy is available at
 *  http://www.r-project.org/Licenses/
 */

#ifndef GCNODE_HPP
#define GCNODE_HPP

#include <sstream>

#include "CXXR/Allocator.hpp"
#include "CXXR/HeterogeneousList.hpp"
#include "CXXR/MemoryBank.hpp"
#include "CXXR/SchwarzCounter.hpp"

// According to various web postings (and arr's experience) it is
// necessary for the compiler to have seen the headers for the archive
// types in use before it encounters any of the BOOST_CLASS_EXPORT_*
// macros.  So we include them here, along with export.hpp itself.
#include <boost/archive/xml_oarchive.hpp>
#include <boost/archive/xml_iarchive.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/export.hpp>
#include <boost/serialization/version.hpp>

#ifdef DOXYGEN
#define GC_FIND_LOOPS
#endif

#define CXXR_NEW(T) CXXR::GCNode::expose(new T)

namespace CXXR {
    class GCNode : public HeterogeneousListBase::Link {
    public:
        struct const_visitor {
            virtual ~const_visitor() {}

            virtual void operator()(const GCNode* node) = 0;
        };

        struct GCInhibitor {
            GCInhibitor()
            {
                ++GCNode::s_inhibitor_count;
            }

            ~GCInhibitor()
            {
                --GCNode::s_inhibitor_count;
            }

            static bool active()
            {
                return s_inhibitor_count != 0;
            }
        };

        // Serialization of pointers to GCNodes.  Defined in
        // GCNode_PtrS11n.hpp .
        class PtrS11n;

        GCNode()
            : HeterogeneousListBase::Link(s_live),
#ifdef GCID
              m_id(++s_last_id),
#endif
              m_rcmmu(s_mark | s_moribund_mask | 1)
        {
            ++s_num_nodes;
            ++s_inhibitor_count;
            s_moribund->push_back(this);
#ifdef GCID
            watch();
#endif
        }

#ifdef __GNUC__
        __attribute__((hot,fastcall))
#endif
        static void* operator new(size_t bytes);

        static void* operator new(size_t, void* where)
        {
            return where;
        }

        static void operator delete(void* p, size_t bytes)
        {
            MemoryBank::deallocate(p, bytes);
        }

        static bool check();

        virtual void detachReferents()  {}

        void expose() const
        {
#ifndef NDEBUG
            if (isExposed())
                alreadyExposedError();
#endif
            m_rcmmu &= ~1;
            --s_inhibitor_count;
        }

        template <class T>
        static T* expose(T* node)
        {
            node->expose();
            return node;
        }

        static void gc();

        static void gclite();

        bool isExposed() const
        {
            return (m_rcmmu & 1) == 0;
        }

        static void maybeCheckExposed(const GCNode* node)
        {
#ifdef CHECK_EXPOSURE
            abortIfNotExposed(node);
#endif
        }

        static size_t numNodes() {return s_num_nodes;}

        virtual void visitReferents(const_visitor* v) const {}
    protected:
        virtual ~GCNode()
        {
#ifdef GCID
            watch();
#endif
            // Is the node still under construction?
            if (m_rcmmu & 1)
                destruct_aux();
            --s_num_nodes;
        }
    private:
        friend class boost::serialization::access;
        friend class GCRootBase;
        friend class GCStackRootBase;
        friend class NodeStack;
        friend class WeakRef;

        class Marker : public const_visitor {
        public:
            Marker()
                : m_marks_applied(0)
            {}

            unsigned int marksApplied() const
            {
                return m_marks_applied;
            }

            // Virtual function of const_visitor:
            void operator()(const GCNode* node);
        private:
            unsigned int m_marks_applied;
#ifdef GC_FIND_LOOPS
            std::vector<const GCNode*> m_ariadne;
#endif
        };

        typedef HeterogeneousList<GCNode> List;

        static List* s_live;  // Except during mark-sweep garbage
          // collection, all existing nodes are threaded on this
          // list.
        static std::vector<const GCNode*>* s_moribund;  // Vector of
          // pointers to nodes whose reference count has fallen to
          // zero (but may subsequently have increased again).
        static List* s_reachable;  // During the mark phase of garbage
          // collection, if a node is found to be reachable from the
          // roots, it is moved to this list. Between garbage
          // collections, this list should be empty.
        static const size_t s_gclite_margin;  // operator new will
          // invoke gclite() when MemoryBank::bytesAllocated() exceeds
          // by at least s_gclite_margin the number of bytes that were
          // allocated following the previous gclite().  This is a
          // tuning parameter.
        static size_t s_gclite_threshold;  // operator new calls
          // gclite() when the number of bytes allocated reaches this
          // level.
        static unsigned int s_num_nodes;  // Number of nodes in existence
        static unsigned int s_inhibitor_count;  // Number of GCInhibitor
          // objects in existence, plus the number of nodes currently
          // under construction (i.e. not yet exposed).
#ifdef GCID
        // If GCID is defined, each GCNode is given an identity
        // number.  The numbers are not unique: they wrap around
        // eventually.  This is the number that was most recently
        // assigned to a node:
        static unsigned int s_last_id;

        // Using a debugger, the following can be set to non-null values
        // to monitor operations on nodes at a particular address, or
        // a node with a particular id:
        static const GCNode* s_watch_addr;
        static unsigned int s_watch_id;
#endif
        // Bit patterns XORd into m_rcmmu to decrement or increment the
        // reference count.  Patterns 0, 2, 4, ... are used to
        // decrement; 1, 3, 5, .. to increment.
        static const unsigned char s_decinc_refcount[];
        static unsigned char s_mark;  // During garbage collection, a
          // node is considered marked if its s_mark_mask bit matches the
          // corresponding bit of s_mark.  (Only this bit will ever be
          // set in s_mark.)
#ifdef GCID
        unsigned int m_id;
#endif

        static const unsigned char s_mark_mask = 0x80;
        static const unsigned char s_moribund_mask = 0x40;
        static const unsigned char s_refcount_mask = 0x3e;
        mutable unsigned char m_rcmmu;
          // Refcount/moribund/marked/under-construction.  The least
          // significant bit is set to signify that the node is under
          // construction.  The reference count is held in the next 5
          // bits, and saturates at 31.  The 0x40 bit is set to
          // signify that the node is on the moribund list.  The most
          // significant bit is set to s_mark on construction; this
          // bit is then toggled in the mark phase of a mark-sweep
          // garbage collection to identify reachable nodes.

        // Not implemented.  Declared to prevent compiler-generated
        // versions:
        GCNode(const GCNode&);
        GCNode& operator=(const GCNode&);

        // Not implemented.  Declared private to prevent clients
        // allocating arrays of GCNode.
        //
        // But boost::serialization doesn't like this.
        // static void* operator new[](size_t);

        // Abort program if 'node' is not exposed to GC.
        static void abortIfNotExposed(const GCNode* node);

        // Abort program with an error message if an attempt is made
        // to expose a node more than once.
        static void alreadyExposedError();

        // Clean up static data at end of run:
        static void cleanup();

        // Decrement the reference count (subject to the stickiness of
        // its MSB).  If as a result the reference count falls to
        // zero, mark the node as moribund.
        static void decRefCount(const GCNode* node)
        {
            if (node) {
                unsigned char& rcmmu = node->m_rcmmu;
                rcmmu ^= s_decinc_refcount[rcmmu & s_refcount_mask];
                if ((rcmmu & (s_refcount_mask | s_moribund_mask)) == 0)
                    node->makeMoribund();
            }
        }

        // Helper function for the destructor, handling the case where
        // the node is still under construction.  This should happen
        // only in the case where a derived class constructor has
        // thrown an exception.
#ifdef __GNUC__
        __attribute__((cold))
#endif
        void destruct_aux();

        // Increment the reference count.  Overflow is handled by the
        // stickiness of the MSB.
        static void incRefCount(const GCNode* node)
        {
            if (node) {
                unsigned char& rcmmu = node->m_rcmmu;
                rcmmu ^= s_decinc_refcount[(rcmmu & s_refcount_mask) + 1];
            }
        }

        static void initialize();

        bool isMarked() const
        {
            return (m_rcmmu & s_mark_mask) == s_mark;
        }

        // Mark this node as moribund:
#ifdef __GNUC__
        __attribute__((hot,fastcall))
#endif
        void makeMoribund() const;

        static void mark();

        // boost::serialization.  Version 0 is for debugging, and will
        // be used for output if the preprocessor variable DEBUG_S11N
        // is defined.  It writes the GCNode's address and id to the
        // archive; these fields are parsed but ignored on input.
        // Version 1 is the default version.
        template <class Archive>
        void serialize(Archive & ar, const unsigned int version);

        static void sweep();
#ifdef GCID
        // Used to monitor a particular node (or nodes at a particular
        // address) using a debugger.
        void watch() const;
#endif

        friend class GCEdgeBase;
        friend class SchwarzCounter<GCNode>;
    };
}  // namespace CXXR

template <class Archive>
void CXXR::GCNode::serialize(Archive & ar, const unsigned int version) {
    if (version == 0) {
        std::ostringstream oss;
        oss << this;
        std::string addr = oss.str();
        ar & BOOST_SERIALIZATION_NVP(addr);
        unsigned int id = 0;
#ifdef GCID
        id = m_id;
#endif
        ar & BOOST_SERIALIZATION_NVP(id);
    }
}

#ifndef DEBUG_S11N
BOOST_CLASS_VERSION(CXXR::GCNode, 1)
#endif

namespace {
    CXXR::SchwarzCounter<CXXR::GCNode> gcnode_schwarz_ctr;
}

#endif /* GCNODE_HPP */