CXXR (C++ R) API
GCNode.hpp
Go to the documentation of this file.
1 /*CXXR $Id: GCNode.hpp 1390 2013-06-11 14:41:41Z arr $
2  *CXXR
3  *CXXR This file is part of CXXR, a project to refactor the R interpreter
4  *CXXR into C++. It may consist in whole or in part of program code and
5  *CXXR documentation taken from the R project itself, incorporated into
6  *CXXR CXXR (and possibly MODIFIED) under the terms of the GNU General Public
7  *CXXR Licence.
8  *CXXR
9  *CXXR CXXR is Copyright (C) 2008-13 Andrew R. Runnalls, subject to such other
10  *CXXR copyrights and copyright restrictions as may be stated below.
11  *CXXR
12  *CXXR CXXR is not part of the R project, and bugs and other issues should
13  *CXXR not be reported via r-bugs or other R project channels; instead refer
14  *CXXR to the CXXR website.
15  *CXXR */
16 
17 /*
18  * R : A Computer Language for Statistical Data Analysis
19  * Copyright (C) 1995, 1996 Robert Gentleman and Ross Ihaka
20  * Copyright (C) 1999-2006 The R Development Core Team.
21  *
22  * This program is free software; you can redistribute it and/or modify
23  * it under the terms of the GNU General Public License as published by
24  * the Free Software Foundation; either version 2.1 of the License, or
25  * (at your option) any later version.
26  *
27  * This program is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU General Public License
33  * along with this program; if not, a copy is available at
34  * http://www.r-project.org/Licenses/
35  */
36 
41 #ifndef GCNODE_HPP
42 #define GCNODE_HPP
43 
44 #include <sstream>
45 
46 #include "CXXR/Allocator.hpp"
48 #include "CXXR/MemoryBank.hpp"
49 #include "CXXR/SchwarzCounter.hpp"
50 
51 // According to various web postings (and arr's experience) it is
52 // necessary for the compiler to have seen the headers for the archive
53 // types in use before it encounters any of the BOOST_CLASS_EXPORT_*
54 // macros. So we include them here, along with export.hpp itself.
55 #include <boost/archive/xml_oarchive.hpp>
56 #include <boost/archive/xml_iarchive.hpp>
57 #include <boost/serialization/access.hpp>
58 #include <boost/serialization/export.hpp>
59 #include <boost/serialization/version.hpp>
60 
68 #ifdef DOXYGEN
69 #define GC_FIND_LOOPS
70 #endif
71 
79 #define CXXR_NEW(T) CXXR::GCNode::expose(new T)
80 
81 namespace CXXR {
140  public:
152  struct const_visitor {
153  virtual ~const_visitor() {}
154 
164  virtual void operator()(const GCNode* node) = 0;
165  };
166 
186  struct GCInhibitor {
187  GCInhibitor()
188  {
189  ++GCNode::s_inhibitor_count;
190  }
191 
192  ~GCInhibitor()
193  {
194  --GCNode::s_inhibitor_count;
195  }
196 
201  static bool active()
202  {
203  return s_inhibitor_count != 0;
204  }
205  };
206 
207  // Serialization of pointers to GCNodes. Defined in
208  // GCNode_PtrS11n.hpp .
209  class PtrS11n;
210 
211  GCNode()
212  : HeterogeneousListBase::Link(s_live),
213 #ifdef GCID
214  m_id(++s_last_id),
215 #endif
216  m_rcmmu(s_mark | s_moribund_mask | 1)
217  {
218  ++s_num_nodes;
219  ++s_inhibitor_count;
220  s_moribund->push_back(this);
221 #ifdef GCID
222  watch();
223 #endif
224  }
225 
241 #ifdef __GNUC__
242  __attribute__((hot,fastcall))
243 #endif
244  static void* operator new(size_t bytes);
245 
248  static void* operator new(size_t, void* where)
249  {
250  return where;
251  }
252 
262  static void operator delete(void* p, size_t bytes)
263  {
264  MemoryBank::deallocate(p, bytes);
265  }
266 
275  static bool check();
276 
296  virtual void detachReferents() {}
297 
302  void expose() const
303  {
304 #ifndef NDEBUG
305  if (isExposed())
306  alreadyExposedError();
307 #endif
308  m_rcmmu &= ~1;
309  --s_inhibitor_count;
310  }
311 
349  template <class T>
350  static T* expose(T* node)
351  {
352  node->expose();
353  return node;
354  }
355 
358  static void gc();
359 
370  static void gclite();
371 
377  bool isExposed() const
378  {
379  return (m_rcmmu & 1) == 0;
380  }
381 
393  static void maybeCheckExposed(const GCNode* node)
394  {
395 #ifdef CHECK_EXPOSURE
396  abortIfNotExposed(node);
397 #endif
398  }
399 
405  static size_t numNodes() {return s_num_nodes;}
406 
425  virtual void visitReferents(const_visitor* v) const {}
426  protected:
433  virtual ~GCNode()
434  {
435 #ifdef GCID
436  watch();
437 #endif
438  // Is the node still under construction?
439  if (m_rcmmu & 1)
440  destruct_aux();
441  --s_num_nodes;
442  }
443  private:
444  friend class boost::serialization::access;
445  friend class GCRootBase;
446  friend class GCStackRootBase;
447  friend class NodeStack;
448  friend class WeakRef;
449 
456  class Marker : public const_visitor {
457  public:
458  Marker()
459  : m_marks_applied(0)
460  {}
461 
462  unsigned int marksApplied() const
463  {
464  return m_marks_applied;
465  }
466 
467  // Virtual function of const_visitor:
468  void operator()(const GCNode* node);
469  private:
470  unsigned int m_marks_applied;
471 #ifdef GC_FIND_LOOPS
472  std::vector<const GCNode*> m_ariadne;
473 #endif
474  };
475 
476  typedef HeterogeneousList<GCNode> List;
477 
478  static List* s_live; // Except during mark-sweep garbage
479  // collection, all existing nodes are threaded on this
480  // list.
481  static std::vector<const GCNode*>* s_moribund; // Vector of
482  // pointers to nodes whose reference count has fallen to
483  // zero (but may subsequently have increased again).
484  static List* s_reachable; // During the mark phase of garbage
485  // collection, if a node is found to be reachable from the
486  // roots, it is moved to this list. Between garbage
487  // collections, this list should be empty.
488  static const size_t s_gclite_margin; // operator new will
489  // invoke gclite() when MemoryBank::bytesAllocated() exceeds
490  // by at least s_gclite_margin the number of bytes that were
491  // allocated following the previous gclite(). This is a
492  // tuning parameter.
493  static size_t s_gclite_threshold; // operator new calls
494  // gclite() when the number of bytes allocated reaches this
495  // level.
496  static unsigned int s_num_nodes; // Number of nodes in existence
497  static unsigned int s_inhibitor_count; // Number of GCInhibitor
498  // objects in existence, plus the number of nodes currently
499  // under construction (i.e. not yet exposed).
500 #ifdef GCID
501  // If GCID is defined, each GCNode is given an identity
502  // number. The numbers are not unique: they wrap around
503  // eventually. This is the number that was most recently
504  // assigned to a node:
505  static unsigned int s_last_id;
506 
507  // Using a debugger, the following can be set to non-null values
508  // to monitor operations on nodes at a particular address, or
509  // a node with a particular id:
510  static const GCNode* s_watch_addr;
511  static unsigned int s_watch_id;
512 #endif
513  // Bit patterns XORd into m_rcmmu to decrement or increment the
514  // reference count. Patterns 0, 2, 4, ... are used to
515  // decrement; 1, 3, 5, .. to increment.
516  static const unsigned char s_decinc_refcount[];
517  static unsigned char s_mark; // During garbage collection, a
518  // node is considered marked if its s_mark_mask bit matches the
519  // corresponding bit of s_mark. (Only this bit will ever be
520  // set in s_mark.)
521 #ifdef GCID
522  unsigned int m_id;
523 #endif
524 
525  static const unsigned char s_mark_mask = 0x80;
526  static const unsigned char s_moribund_mask = 0x40;
527  static const unsigned char s_refcount_mask = 0x3e;
528  mutable unsigned char m_rcmmu;
529  // Refcount/moribund/marked/under-construction. The least
530  // significant bit is set to signify that the node is under
531  // construction. The reference count is held in the next 5
532  // bits, and saturates at 31. The 0x40 bit is set to
533  // signify that the node is on the moribund list. The most
534  // significant bit is set to s_mark on construction; this
535  // bit is then toggled in the mark phase of a mark-sweep
536  // garbage collection to identify reachable nodes.
537 
538  // Not implemented. Declared to prevent compiler-generated
539  // versions:
540  GCNode(const GCNode&);
541  GCNode& operator=(const GCNode&);
542 
543  // Not implemented. Declared private to prevent clients
544  // allocating arrays of GCNode.
545  //
546  // But boost::serialization doesn't like this.
547  // static void* operator new[](size_t);
548 
549  // Abort program if 'node' is not exposed to GC.
550  static void abortIfNotExposed(const GCNode* node);
551 
552  // Abort program with an error message if an attempt is made
553  // to expose a node more than once.
554  static void alreadyExposedError();
555 
556  // Clean up static data at end of run:
557  static void cleanup();
558 
559  // Decrement the reference count (subject to the stickiness of
560  // its MSB). If as a result the reference count falls to
561  // zero, mark the node as moribund.
562  static void decRefCount(const GCNode* node)
563  {
564  if (node) {
565  unsigned char& rcmmu = node->m_rcmmu;
566  rcmmu ^= s_decinc_refcount[rcmmu & s_refcount_mask];
567  if ((rcmmu & (s_refcount_mask | s_moribund_mask)) == 0)
568  node->makeMoribund();
569  }
570  }
571 
572  // Helper function for the destructor, handling the case where
573  // the node is still under construction. This should happen
574  // only in the case where a derived class constructor has
575  // thrown an exception.
576 #ifdef __GNUC__
577  __attribute__((cold))
578 #endif
579  void destruct_aux();
580 
581  // Increment the reference count. Overflow is handled by the
582  // stickiness of the MSB.
583  static void incRefCount(const GCNode* node)
584  {
585  if (node) {
586  unsigned char& rcmmu = node->m_rcmmu;
587  rcmmu ^= s_decinc_refcount[(rcmmu & s_refcount_mask) + 1];
588  }
589  }
590 
600  static void initialize();
601 
602  bool isMarked() const
603  {
604  return (m_rcmmu & s_mark_mask) == s_mark;
605  }
606 
607  // Mark this node as moribund:
608 #ifdef __GNUC__
609  __attribute__((hot,fastcall))
610 #endif
611  void makeMoribund() const;
612 
615  static void mark();
616 
617  // boost::serialization. Version 0 is for debugging, and will
618  // be used for output if the preprocessor variable DEBUG_S11N
619  // is defined. It writes the GCNode's address and id to the
620  // archive; these fields are parsed but ignored on input.
621  // Version 1 is the default version.
622  template <class Archive>
623  void serialize(Archive & ar, const unsigned int version);
624 
627  static void sweep();
628 #ifdef GCID
629  // Used to monitor a particular node (or nodes at a particular
630  // address) using a debugger.
631  void watch() const;
632 #endif
633 
634  friend class GCEdgeBase;
635  friend class SchwarzCounter<GCNode>;
636  };
637 } // namespace CXXR
638 
639 template <class Archive>
640 void CXXR::GCNode::serialize(Archive & ar, const unsigned int version) {
641  if (version == 0) {
642  std::ostringstream oss;
643  oss << this;
644  std::string addr = oss.str();
645  ar & BOOST_SERIALIZATION_NVP(addr);
646  unsigned int id = 0;
647 #ifdef GCID
648  id = m_id;
649 #endif
650  ar & BOOST_SERIALIZATION_NVP(id);
651  }
652 }
653 
654 #ifndef DEBUG_S11N
655 BOOST_CLASS_VERSION(CXXR::GCNode, 1)
656 #endif
657 
658 namespace {
659  CXXR::SchwarzCounter<CXXR::GCNode> gcnode_schwarz_ctr;
660 }
661 
662 #endif /* GCNODE_HPP */