X-Git-Url: https://main.carlh.net/gitweb/?a=blobdiff_plain;f=libs%2Fpbd%2Fpbd%2Frcu.h;h=909954fc0e1a8a681d19f3d931d93a5cb6e8b938;hb=d074bc586e494d7dd83d415a487195a477095a4f;hp=58a92a206a574e3e4066af422ff065cbfad304b8;hpb=f99a016f17a890aa4c71f2aa8771e52314492db7;p=ardour.git diff --git a/libs/pbd/pbd/rcu.h b/libs/pbd/pbd/rcu.h index 58a92a206a..909954fc0e 100644 --- a/libs/pbd/pbd/rcu.h +++ b/libs/pbd/pbd/rcu.h @@ -1,49 +1,124 @@ +/* + Copyright (C) 2000-2007 Paul Davis + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + +*/ + #ifndef __pbd_rcu_h__ #define __pbd_rcu_h__ #include "boost/shared_ptr.hpp" -#include "glibmm/thread.h" - -#include - - +#include "glibmm/threads.h" + +#include + +/** @file Defines a set of classes to implement Read-Copy-Update. We do not attempt to define RCU here - use google. + + The design consists of two parts: an RCUManager and an RCUWriter. +*/ + +/** An RCUManager is an object which takes over management of a pointer to another object. + It provides three key methods: + + - reader() : obtains a shared pointer to the managed object that may be used for reading, without synchronization + - write_copy() : obtains a shared pointer to the object that may be used for writing/modification + - update() : accepts a shared pointer to a (presumed) modified instance of the object and causes all + future reader() and write_copy() calls to use that instance. + + Any existing users of the value returned by reader() can continue to use their copy even as a write_copy()/update() takes place. + The RCU manager will manage the various instances of "the managed object" in a way that is transparent to users of the manager + and managed object. +*/ template class RCUManager { public: - + RCUManager (T* new_rcu_value) { - m_rcu_value = new boost::shared_ptr (new_rcu_value); + x.m_rcu_value = new boost::shared_ptr (new_rcu_value); } - - virtual ~RCUManager() { delete m_rcu_value; } - - boost::shared_ptr reader () const { return *((boost::shared_ptr *) g_atomic_pointer_get (&m_rcu_value)); } - + + virtual ~RCUManager() { delete x.m_rcu_value; } + + boost::shared_ptr reader () const { return *((boost::shared_ptr *) g_atomic_pointer_get (&x.gptr)); } + + /* this is an abstract base class - how these are implemented depends on the assumptions + that one can make about the users of the RCUManager. See SerializedRCUManager below + for one implementation. + */ + virtual boost::shared_ptr write_copy () = 0; virtual bool update (boost::shared_ptr new_value) = 0; protected: - boost::shared_ptr* m_rcu_value; + /* ordinarily this would simply be a declaration of a ptr to a shared_ptr. however, the atomic + operations that we are using (from glib) have sufficiently strict typing that it proved hard + to get them to accept even a cast value of the ptr-to-shared-ptr() as the argument to get() + and comp_and_exchange(). Consequently, we play a litle trick here that relies on the fact + that sizeof(A*) == sizeof(B*) no matter what the types of A and B are. for most purposes + we will use x.m_rcu_value, but when we need to use an atomic op, we use x.gptr. Both expressions + evaluate to the same address. + */ + + union { + boost::shared_ptr* m_rcu_value; + mutable volatile gpointer gptr; + } x; +}; - // this monstrosity is needed because of some wierd behavior by g++ - gpointer * the_pointer() const { return (gpointer *) &m_rcu_value; } -}; - - +/** Serialized RCUManager implements the RCUManager interface. It is based on the + following key assumption: among its users we have readers that are bound by + RT time constraints, and writers who are not. Therefore, we do not care how + slow the write_copy()/update() operations are, or what synchronization + primitives they use. + + Because of this design assumption, this class will serialize all + writers. That is, objects calling write_copy()/update() will be serialized by + a mutex. Only a single writer may be in the middle of write_copy()/update(); + all other writers will block until the first has finished. The order of + execution of multiple writers if more than one is blocked in this way is + undefined. + + The class maintains a lock-protected "dead wood" list of old value of + *m_rcu_value (i.e. shared_ptr). The list is cleaned up every time we call + write_copy(). If the list is the last instance of a shared_ptr that + references the object (determined by shared_ptr::unique()) then we + erase it from the list, thus deleting the object it points to. This is lazy + destruction - the SerializedRCUManager assumes that there will sufficient + calls to write_copy() to ensure that we do not inadvertently leave objects + around for excessive periods of time. + + For extremely well defined circumstances (i.e. it is known that there are no + other writer objects in existence), SerializedRCUManager also provides a + flush() method that will unconditionally clear out the "dead wood" list. It + must be used with significant caution, although the use of shared_ptr + means that no actual objects will be deleted incorrectly if this is misused. +*/ template class SerializedRCUManager : public RCUManager { public: - + SerializedRCUManager(T* new_rcu_value) : RCUManager(new_rcu_value) { - } - - virtual boost::shared_ptr write_copy () + + boost::shared_ptr write_copy () { m_lock.lock(); @@ -52,35 +127,45 @@ public: typename std::list >::iterator i; for (i = m_dead_wood.begin(); i != m_dead_wood.end(); ) { - if ((*i).use_count() == 1) { + if ((*i).unique()) { i = m_dead_wood.erase (i); } else { ++i; } } - // store the current + /* store the current so that we can do compare and exchange + when someone calls update(). Notice that we hold + a lock, so this store of m_rcu_value is atomic. + */ + + current_write_old = RCUManager::x.m_rcu_value; - current_write_old = RCUManager::m_rcu_value; - boost::shared_ptr new_copy (new T(**current_write_old)); - + return new_copy; + + /* notice that the write lock is still held: update() MUST + be called or we will cause another writer to stall. + */ } - - virtual bool update (boost::shared_ptr new_value) + + bool update (boost::shared_ptr new_value) { - // we hold the lock at this point effectively blocking - // other writers. + /* we still hold the write lock - other writers are locked out */ boost::shared_ptr* new_spp = new boost::shared_ptr (new_value); - // update, checking that nobody beat us to it + /* update, by atomic compare&swap. Only succeeds if the old + value has not been changed. - bool ret = g_atomic_pointer_compare_and_exchange (RCUManager::the_pointer(), + XXX but how could it? we hold the freakin' lock! + */ + + bool ret = g_atomic_pointer_compare_and_exchange (&RCUManager::x.gptr, (gpointer) current_write_old, (gpointer) new_spp); - + if (ret) { // successful update : put the old value into dead_wood, @@ -94,49 +179,76 @@ public: delete current_write_old; } + /* unlock, allowing other writers to proceed */ + m_lock.unlock(); return ret; } - + + void flush () { + Glib::Threads::Mutex::Lock lm (m_lock); + m_dead_wood.clear (); + } + private: - Glib::Mutex m_lock; + Glib::Threads::Mutex m_lock; boost::shared_ptr* current_write_old; std::list > m_dead_wood; }; - + +/** RCUWriter is a convenience object that implements write_copy/update via + lifetime management. Creating the object obtains a writable copy, which can + be obtained via the get_copy() method; deleting the object will update + the manager's copy. Code doing a write/update thus looks like: + + { + + RCUWriter writer (object_manager); + boost::shared_ptr copy = writer.get_copy(); + ... modify copy ... + + } <= writer goes out of scope, update invoked + +*/ template class RCUWriter { public: - + RCUWriter(RCUManager& manager) - : m_manager(manager) - { - m_copy = m_manager.write_copy(); + : m_manager(manager) { + m_copy = m_manager.write_copy(); } - - ~RCUWriter() - { - // we can check here that the refcount of m_copy is 1 - - if(m_copy.use_count() == 1) { + + ~RCUWriter() { + if (m_copy.unique()) { + /* As intended, our copy is the only reference + to the object pointed to by m_copy. Update + the manager with the (presumed) modified + version. + */ m_manager.update(m_copy); } else { - - // critical error. + /* This means that some other object is using our copy + of the object. This can only happen if the scope in + which this RCUWriter exists passed it to a function + that created a persistent reference to it, since the + copy was private to this particular RCUWriter. Doing + so will not actually break anything but it violates + the design intention here and so we do not bother to + update the manager's copy. + + XXX should we print a warning about this? + */ } - + } - - // or operator boost::shared_ptr (); - boost::shared_ptr get_copy() { return m_copy; } - + + boost::shared_ptr get_copy() const { return m_copy; } + private: - RCUManager& m_manager; - - // preferably this holds a pointer to T boost::shared_ptr m_copy; };