libbase/GC.h

   1 // GC.h: Garbage Collector for Gnash
   2 //
   3 //   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
   4 //   Free Software Foundation, Inc
   5 //
   6 // This program is free software; you can redistribute it and/or modify
   7 // it under the terms of the GNU General Public License as published by
   8 // the Free Software Foundation; either version 3 of the License, or
   9 // (at your option) any later version.
  10 //
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with this program; if not, write to the Free Software
  18 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19
  20 #ifndef GNASH_GC_H
  21 #define GNASH_GC_H
  22
  23 // Define the following macro to enable GC verbosity
  24 // Verbosity levels:
  25 //   1 - print stats about how many resources are registered and how many
  26 //       are deleted, everytime the GC collector runs.
  27 //   2 - print a message for every GcResource being registered and being deleted
  28 //   3 - print info about the mark scan
  29 //
  30 //#define GNASH_GC_DEBUG 1
  31
  32 #include <forward_list>
  33 #include <map>
  34 #include <string>
  35 #include <cassert>
  36
  37 #include "dsodefs.h"
  38 #ifdef GNASH_GC_DEBUG
  39 # include "log.h"
  40 # include "utility.h"
  41 #endif
  42
  43 // Forward declarations.
  44 namespace gnash {
  45     class GC;
  46 }
  47
  48 namespace gnash {
  49
  50 /// Abstract class to allow the GC to store "roots" into a container
  51 //
  52 /// Any class expected to act as a "root" for the garbage collection
  53 /// should derive from this class, and implement the markReachableResources()
  54 /// function.
  55 class GcRoot
  56 {
  57 public:
  58
  59     /// Scan all GC resources reachable by this instance.
  60     //
  61     /// This function is invoked on roots registered to
  62     /// the collector.
  63     ///
  64     /// Use setReachable() on the resources stored in this
  65     /// container.
  66     virtual void markReachableResources() const = 0;
  67
  68     virtual ~GcRoot() {}
  69 };
  70
  71 /// Collectable resource
  72 //
  73 /// Instances of this class can be managed by a GC object.
  74 class GcResource
  75 {
  76 public:
  77
  78     friend class GC;
  79
  80     /// Create a Garbage-collected resource associated with a GC
  81     //
  82     /// @param gc   The GC to register the resource with.
  83     GcResource(GC& gc);
  84
  85     /// Mark this resource as being reachable
  86     //
  87     /// This can trigger further marking of all resources reachable by this
  88     /// object.
  89     //
  90     /// If the object wasn't reachable before, this call triggers
  91     /// scan of all contained objects too.
  92     void setReachable() const {
  93
  94         if (_reachable) {
  95
  96 #if GNASH_GC_DEBUG > 2
  97             log_debug(_("Instance %p of class %s already reachable, "
  98                     "setReachable doing nothing"), (void*)this,
  99                     typeName(*this));
 100 #endif
 101             return;
 102         }
 103
 104 #if GNASH_GC_DEBUG  > 2
 105         log_debug(_("Instance %p of class %s set to reachable, scanning "
 106                 "reachable resources from it"), (void*)this,
 107                 typeName(*this));
 108 #endif
 109
 110         _reachable = true;
 111         markReachableResources();
 112     }
 113
 114     /// Return true if this object is marked as reachable
 115     bool isReachable() const { return _reachable; }
 116
 117     /// Clear the reachable flag
 118     void clearReachable() const { _reachable = false; }
 119
 120 protected:
 121
 122     /// Scan all GC resources reachable by this instance.
 123     //
 124     /// This function is invoked everytime this object
 125     /// switches from unreachable to reachable, and is
 126     /// used to recursively mark all contained resources
 127     /// as reachable.
 128     ///
 129     /// See setReachable(), which is the function to invoke
 130     /// against all reachable methods.
 131     ///
 132     /// Feel free to assert(_reachable) in your implementation.
 133     ///
 134     /// The default implementation doesn't mark anything.
 135     ///
 136     virtual void markReachableResources() const {
 137         assert(_reachable);
 138 #if GNASH_GC_DEBUG > 1
 139         log_debug(_("Class %s didn't override the markReachableResources() "
 140                     "method"), typeName(*this));
 141 #endif
 142     }
 143
 144     /// Delete this resource.
 145     //
 146     /// This is protected to allow subclassing, but ideally it
 147     /// sould be private, so only the GC is allowed to delete us.
 148     ///
 149     virtual ~GcResource() {}
 150
 151 private:
 152
 153     mutable bool _reachable;
 154
 155 };
 156
 157 /// Garbage collector singleton
 158 //
 159 /// Instances of this class manage a list of heap pointers (collectables),
 160 /// deleting them when no more needed/reachable.
 161 ///
 162 /// Their reachability is detected starting from a root, which in turn
 163 /// marks all reachable resources.
 164 class DSOEXPORT GC
 165 {
 166
 167 public:
 168
 169     /// Create a garbage collector using the given root
 170     //
 171     /// @param root     The top level of the GC, which takes care of marking
 172     ///                 all further resources.
 173     GC(GcRoot& root);
 174
 175     /// Destroy the collector, releasing all collectables.
 176     ~GC();
 177
 178     /// Add an object to the list of managed collectables
 179     //
 180     /// The given object is expected not to be already in the
 181     /// list. Failing to do so would just decrease performances
 182     /// but might not be a problem. Anyway, an assertion will fail
 183     /// if adding an object twice.
 184     ///
 185     /// PRECONDITIONS:
 186     /// - the object isn't already in this GC list.
 187     /// - the object isn't marked as reachable.
 188     /// - the object isn't managed by another GC (UNCHECKED)
 189     ///
 190     /// @param item
 191     /// The item to be managed by this collector.
 192     /// Can't be NULL. The caller gives up ownerhip
 193     /// of it, which will only be deleted by this GC.
 194     void addCollectable(const GcResource* item) {
 195
 196 #ifndef NDEBUG
 197         assert(item);
 198         assert(!item->isReachable());
 199 #endif
 200
 201         _resList.emplace_front(item); ++_resListSize;
 202
 203 #if GNASH_GC_DEBUG > 1
 204         log_debug(_("GC: collectable %p added, num collectables: %d"), item,
 205                 _resListSize);
 206 #endif
 207     }
 208
 209     /// Run the collector, if worth it
 210     void fuzzyCollect() {
 211
 212         // Heuristic to decide wheter or not to run the collection cycle
 213         //
 214         //
 215         // Things to consider:
 216         //
 217         //  - Cost
 218         //      - Depends on the number of reachable collectables
 219         //      - Depends on the frequency of runs
 220         //
 221         //  - Advantages
 222         //      - Depends on the number of unreachable collectables
 223         //
 224         //  - Cheaply computable informations
 225         //      - Number of collectables (currently O(n) but can be optimized)
 226         //      - Total heap-allocated memory (currently unavailable)
 227         //
 228         // Current heuristic:
 229         //
 230         //  - We run the cycle again if X new collectables were allocated
 231         //    since last cycle run. X defaults to maxNewCollectablesCount
 232         //    and can be changed by user (GNASH_GC_TRIGGER_THRESHOLD env
 233         //    variable).
 234         //
 235         // Possible improvements:
 236         //
 237         //  - Adapt X (maxNewCollectablesCount) based on cost/advantage
 238         //    runtime analisys
 239         //
 240
 241         if (_resListSize <  _lastResCount + _maxNewCollectablesCount) {
 242 #if GNASH_GC_DEBUG  > 1
 243             log_debug(_("GC: collection cycle skipped - %d/%d new resources "
 244                         "allocated since last run (from %d to %d)"),
 245                     _resListSize-_lastResCount, _maxNewCollectablesCount,
 246                     _lastResCount, _resListSize);
 247 #endif // GNASH_GC_DEBUG
 248             return;
 249         }
 250
 251         runCycle();
 252     }
 253
 254     /// Run the collection cycle
 255     //
 256     /// Find all reachable collectables, destroy all the others.
 257     ///
 258     void runCycle();
 259
 260     typedef std::map<std::string, unsigned int> CollectablesCount;
 261
 262     /// Count collectables
 263     void countCollectables(CollectablesCount& count) const;
 264
 265 private:
 266
 267     /// List of collectables
 268     typedef std::forward_list<const GcResource*> ResList;
 269
 270     /// Mark all reachable resources
 271     void markReachable() {
 272 #if GNASH_GC_DEBUG > 2
 273         log_debug(_("GC %p: MARK SCAN"), (void*)this);
 274 #endif
 275         _root.markReachableResources();
 276     }
 277
 278     /// Delete all unreachable objects, and mark the others unreachable again
 279     //
 280     /// @return number of objects deleted
 281     size_t cleanUnreachable();
 282
 283     /// Number of newly registered collectable since last collection run
 284     /// triggering next collection.
 285     size_t _maxNewCollectablesCount;
 286
 287     /// List of collectable resources
 288     ResList _resList;
 289
 290     /// Size of the ResList to avoid the cost of computing it
 291     ResList::size_type _resListSize;
 292
 293     /// The GcRoot.
 294     GcRoot& _root;
 295
 296     /// Number of resources in collectable list at end of last
 297     /// collect() call.
 298     ResList::size_type _lastResCount;
 299
 300 #ifdef GNASH_GC_DEBUG
 301     /// Number of times the collector runs (stats/profiling)
 302     size_t _collectorRuns;
 303 #endif
 304 };
 305
 306
 307 inline GcResource::GcResource(GC& gc)
 308     :
 309     _reachable(false)
 310 {
 311     gc.addCollectable(this);
 312 }
 313
 314 } // namespace gnash
 315
 316 #endif // GNASH_GC_H