libs/pbd/pbd/rcu.h

   1 /*
   2     Copyright (C) 2000-2007 Paul Davis
   3
   4     This program is free software; you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation; either version 2 of the License, or
   7     (at your option) any later version.
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program; if not, write to the Free Software
  16     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18 */
  19
  20 #ifndef __pbd_rcu_h__
  21 #define __pbd_rcu_h__
  22
  23 #include "boost/shared_ptr.hpp"
  24 #include "glibmm/threads.h"
  25
  26 #include <list>
  27
  28 /** @file Defines a set of classes to implement Read-Copy-Update.  We do not attempt to define RCU here - use google.
  29
  30    The design consists of two parts: an RCUManager and an RCUWriter.
  31 */
  32
  33 /** An RCUManager is an object which takes over management of a pointer to another object.
  34    It provides three key methods:
  35
  36            - reader() : obtains a shared pointer to the managed object that may be used for reading, without synchronization
  37                - write_copy() : obtains a shared pointer to the object that may be used for writing/modification
  38                - update() : accepts a shared pointer to a (presumed) modified instance of the object and causes all
  39                             future reader() and write_copy() calls to use that instance.
  40
  41    Any existing users of the value returned by reader() can continue to use their copy even as a write_copy()/update() takes place.
  42    The RCU manager will manage the various instances of "the managed object" in a way that is transparent to users of the manager
  43    and managed object.
  44 */
  45 template<class T>
  46 class RCUManager
  47 {
  48   public:
  49
  50         RCUManager (T* new_rcu_value) {
  51                 x.m_rcu_value = new boost::shared_ptr<T> (new_rcu_value);
  52         }
  53
  54         virtual ~RCUManager() { delete x.m_rcu_value; }
  55
  56         boost::shared_ptr<T> reader () const { return *((boost::shared_ptr<T> *) g_atomic_pointer_get (&x.gptr)); }
  57
  58         /* this is an abstract base class - how these are implemented depends on the assumptions
  59            that one can make about the users of the RCUManager. See SerializedRCUManager below
  60            for one implementation.
  61         */
  62
  63         virtual boost::shared_ptr<T> write_copy () = 0;
  64         virtual bool update (boost::shared_ptr<T> new_value) = 0;
  65
  66   protected:
  67         /* ordinarily this would simply be a declaration of a ptr to a shared_ptr<T>. however, the atomic
  68            operations that we are using (from glib) have sufficiently strict typing that it proved hard
  69            to get them to accept even a cast value of the ptr-to-shared-ptr() as the argument to get()
  70            and comp_and_exchange(). Consequently, we play a litle trick here that relies on the fact
  71            that sizeof(A*) == sizeof(B*) no matter what the types of A and B are. for most purposes
  72            we will use x.m_rcu_value, but when we need to use an atomic op, we use x.gptr. Both expressions
  73            evaluate to the same address.
  74         */
  75
  76         union {
  77             boost::shared_ptr<T>* m_rcu_value;
  78             mutable volatile gpointer gptr;
  79         } x;
  80 };
  81
  82
  83 /** Serialized RCUManager implements the RCUManager interface. It is based on the
  84    following key assumption: among its users we have readers that are bound by
  85    RT time constraints, and writers who are not. Therefore, we do not care how
  86    slow the write_copy()/update() operations are, or what synchronization
  87    primitives they use.
  88
  89    Because of this design assumption, this class will serialize all
  90    writers. That is, objects calling write_copy()/update() will be serialized by
  91    a mutex. Only a single writer may be in the middle of write_copy()/update();
  92    all other writers will block until the first has finished. The order of
  93    execution of multiple writers if more than one is blocked in this way is
  94    undefined.
  95
  96    The class maintains a lock-protected "dead wood" list of old value of
  97    *m_rcu_value (i.e. shared_ptr<T>). The list is cleaned up every time we call
  98    write_copy(). If the list is the last instance of a shared_ptr<T> that
  99    references the object (determined by shared_ptr::unique()) then we
 100    erase it from the list, thus deleting the object it points to.  This is lazy
 101    destruction - the SerializedRCUManager assumes that there will sufficient
 102    calls to write_copy() to ensure that we do not inadvertently leave objects
 103    around for excessive periods of time.
 104
 105    For extremely well defined circumstances (i.e. it is known that there are no
 106    other writer objects in existence), SerializedRCUManager also provides a
 107    flush() method that will unconditionally clear out the "dead wood" list. It
 108    must be used with significant caution, although the use of shared_ptr<T>
 109    means that no actual objects will be deleted incorrectly if this is misused.
 110 */
 111 template<class T>
 112 class SerializedRCUManager : public RCUManager<T>
 113 {
 114 public:
 115
 116         SerializedRCUManager(T* new_rcu_value)
 117                 : RCUManager<T>(new_rcu_value)
 118         {
 119         }
 120
 121         boost::shared_ptr<T> write_copy ()
 122         {
 123                 m_lock.lock();
 124
 125                 // clean out any dead wood
 126
 127                 typename std::list<boost::shared_ptr<T> >::iterator i;
 128
 129                 for (i = m_dead_wood.begin(); i != m_dead_wood.end(); ) {
 130                         if ((*i).unique()) {
 131                                 i = m_dead_wood.erase (i);
 132                         } else {
 133                                 ++i;
 134                         }
 135                 }
 136
 137                 /* store the current so that we can do compare and exchange
 138                    when someone calls update(). Notice that we hold
 139                    a lock, so this store of m_rcu_value is atomic.
 140                 */
 141
 142                 current_write_old = RCUManager<T>::x.m_rcu_value;
 143
 144                 boost::shared_ptr<T> new_copy (new T(**current_write_old));
 145
 146                 return new_copy;
 147
 148                 /* notice that the write lock is still held: update() MUST
 149                    be called or we will cause another writer to stall.
 150                 */
 151         }
 152
 153         bool update (boost::shared_ptr<T> new_value)
 154         {
 155                 /* we still hold the write lock - other writers are locked out */
 156
 157                 boost::shared_ptr<T>* new_spp = new boost::shared_ptr<T> (new_value);
 158
 159                 /* update, by atomic compare&swap. Only succeeds if the old
 160                    value has not been changed.
 161
 162                    XXX but how could it? we hold the freakin' lock!
 163                 */
 164
 165                 bool ret = g_atomic_pointer_compare_and_exchange (&RCUManager<T>::x.gptr,
 166                                                                   (gpointer) current_write_old,
 167                                                                   (gpointer) new_spp);
 168
 169                 if (ret) {
 170
 171                         // successful update : put the old value into dead_wood,
 172
 173                         m_dead_wood.push_back (*current_write_old);
 174
 175                         // now delete it - this gets rid of the shared_ptr<T> but
 176                         // because dead_wood contains another shared_ptr<T> that
 177                         // references the same T, the underlying object lives on
 178
 179                         delete current_write_old;
 180                 }
 181
 182                 /* unlock, allowing other writers to proceed */
 183
 184                 m_lock.unlock();
 185
 186                 return ret;
 187         }
 188
 189         void flush () {
 190                 Glib::Threads::Mutex::Lock lm (m_lock);
 191                 m_dead_wood.clear ();
 192         }
 193
 194 private:
 195         Glib::Threads::Mutex                      m_lock;
 196         boost::shared_ptr<T>*            current_write_old;
 197         std::list<boost::shared_ptr<T> > m_dead_wood;
 198 };
 199
 200 /** RCUWriter is a convenience object that implements write_copy/update via
 201    lifetime management. Creating the object obtains a writable copy, which can
 202    be obtained via the get_copy() method; deleting the object will update
 203    the manager's copy. Code doing a write/update thus looks like:
 204
 205    {
 206
 207         RCUWriter writer (object_manager);
 208         boost::shared_ptr<T> copy = writer.get_copy();
 209         ... modify copy ...
 210
 211    } <= writer goes out of scope, update invoked
 212
 213 */
 214 template<class T>
 215 class RCUWriter
 216 {
 217 public:
 218
 219         RCUWriter(RCUManager<T>& manager)
 220                 : m_manager(manager) {
 221                 m_copy = m_manager.write_copy();
 222         }
 223
 224         ~RCUWriter() {
 225                 if (m_copy.unique()) {
 226                         /* As intended, our copy is the only reference
 227                            to the object pointed to by m_copy. Update
 228                            the manager with the (presumed) modified
 229                            version.
 230                         */
 231                         m_manager.update(m_copy);
 232                 } else {
 233                         /* This means that some other object is using our copy
 234                            of the object. This can only happen if the scope in
 235                            which this RCUWriter exists passed it to a function
 236                            that created a persistent reference to it, since the
 237                            copy was private to this particular RCUWriter. Doing
 238                            so will not actually break anything but it violates
 239                            the design intention here and so we do not bother to
 240                            update the manager's copy.
 241
 242                            XXX should we print a warning about this?
 243                         */
 244                 }
 245
 246         }
 247
 248         boost::shared_ptr<T> get_copy() const { return m_copy; }
 249
 250 private:
 251         RCUManager<T>& m_manager;
 252         boost::shared_ptr<T> m_copy;
 253 };
 254
 255 #endif /* __pbd_rcu_h__ */