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