libs/pbd/pbd/rcu.h

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