rcu.h

Go to the documentation of this file.

/*
 * Copyright (C) 2000-2013 Paul Davis <paul@linuxaudiosystems.com>
 * Copyright (C) 2009 David Robillard <d@drobilla.net>
 *
 * 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.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
#ifndef __pbd_rcu_h__
#define __pbd_rcu_h__
 
#include <atomic>
#include <mutex>
#include <memory>
 
#include "boost/smart_ptr/detail/yield_k.hpp"
 
#include <list>
 
#include "pbd/libpbd_visibility.h"
 
template <class T>
class /*LIBPBD_API*/ RCUManager
{
public:
        RCUManager (T* object_to_be_managed)
        {
                _active_reads = 0;
                managed_object = new std::shared_ptr<T> (object_to_be_managed);
        }
 
        virtual ~RCUManager ()
        {
                /* This just deletes the shared ptr, but of course this may
                   also be the last reference to the managed object.
                */
                delete managed_object.load ();
        }
 
        std::shared_ptr<T const> reader () const
        {
                std::shared_ptr<T> rv;
 
                /* Keep count of any readers in this section of code, so writers can
                 * wait until managed_object is no longer in use after an atomic exchange
                 * before dropping it.
                 */
                /* no reads or writes below this atomic store (e.g. the copying
                 * of *managed_object) can move before this "barrier".
                 */
                _active_reads.fetch_add (1, std::memory_order_release);
                rv = *managed_object;
                /* no reads or writes below this atomic store (e.g. the copying
                 * of *managed_object) can move before this "barrier", and this
                 * also synchronizes with a memory_order_acquire load when
                 * testing for active readers (see below).
                 */
                _active_reads.fetch_sub (1, std::memory_order_release);
 
                return rv;
        }
 
        /* 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 std::shared_ptr<T> write_copy ()                         = 0;
        virtual bool               update (std::shared_ptr<T> new_value) = 0;
 
protected:
        typedef std::shared_ptr<T>* PtrToSharedPtr;
        std::atomic<PtrToSharedPtr> managed_object;
 
        inline bool active_read () const {
                return _active_reads.load (std::memory_order_acquire) != 0;
        }
 
private:
        mutable std::atomic<int> _active_reads;
};
 
template <class T>
class /*LIBPBD_API*/ SerializedRCUManager : public RCUManager<T>
{
public:
        SerializedRCUManager(T* new_managed_object)
                : RCUManager<T>(new_managed_object)
                , _current_write_old (0)
        {
        }
 
        void init (std::shared_ptr<T> object_to_be_managed) {
                assert  (*RCUManager<T>::managed_object == std::shared_ptr<T> ());
                RCUManager<T>::managed_object = new std::shared_ptr<T> (object_to_be_managed);
        }
 
        std::shared_ptr<T> write_copy ()
        {
                _lock.lock ();
 
                // clean out any dead wood
 
                typename std::list<std::shared_ptr<T> >::iterator i;
 
                for (i = _dead_wood.begin (); i != _dead_wood.end ();) {
                        if ((*i).unique ()) {
                                i = _dead_wood.erase (i);
                        } else {
                                ++i;
                        }
                }
 
                /* 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 managed_object is atomic.
                 */
 
                _current_write_old = RCUManager<T>::managed_object;
 
                /* now do the (potentially arbitrarily expensive data copy of
                 * the RCU-managed object
                 */
 
                std::shared_ptr<T> new_copy (new T (**_current_write_old));
 
                return new_copy;
 
                /* notice that the write lock is still held: update() or abort() MUST
                 * be called or we will cause another writer to stall.
                 */
        }
 
        void abort () {
                _lock.unlock();
        }
 
        bool update (std::shared_ptr<T> new_value)
        {
                /* we still hold the write lock - other writers are locked out */
 
                typename RCUManager<T>::PtrToSharedPtr new_spp = new std::shared_ptr<T> (new_value);
 
                /* update, by atomic compare&swap. Only succeeds if the old
                 * value has not been changed.
                 *
                 * XXX but how could it? we hold the freakin' lock!
                 */
 
                bool ret = RCUManager<T>::managed_object.compare_exchange_strong (_current_write_old, new_spp);
 
                if (ret) {
                        /* successful update
                         *
                         * wait until there are no active readers. This ensures that any
                         * references to the old value have been fully copied into a new
                         * shared_ptr, and thus have had their reference count incremented.
                         */
 
                        for (unsigned i = 0; RCUManager<T>::active_read (); ++i) {
                                /* spin being nice to the scheduler/CPU */
                                boost::detail::yield (i);
                        }
 
#if 0 // TODO find a good solition here...
                        /* if we are not the only user, put the old value into dead_wood.
                         * if we are the only user, then it is safe to drop it here.
                         */
 
                        if (!_current_write_old->unique ()) {
                                _dead_wood.push_back (*_current_write_old);
                        }
#else
                        /* above ->unique() condition is subject to a race condition.
                         *
                         * Particulalry with JACK2 graph-order callbacks arriving
                         * concurrently to processing, which can lead to heap-use-after-free
                         * of the RouteList.
                         *
                         * std::shared_ptr<T>::use_count documetation reads:
                         * > In multithreaded environment, the value returned by use_count is approximate
                         * > (typical implementations use a memory_order_relaxed load).
                         */
                        _dead_wood.push_back (*_current_write_old);
#endif
 
                        /* now delete it - if we are the only user, this deletes the
                         * underlying object. If other users existed, then there will
                         * be an extra reference in _dead_wood, ensuring that the
                         * underlying object lives on even when the other users
                         * are done with it
                         */
 
                        delete _current_write_old;
                }
 
                /* unlock, allowing other writers to proceed */
 
                _lock.unlock ();
 
                return ret;
        }
 
        void no_update () {
                /* just releases the lock, in the event that no changes are
                   made to a write copy.
                */
                _lock.unlock ();
        }
 
        void flush ()
        {
                std::lock_guard<std::mutex> lm (_lock);
                _dead_wood.clear ();
        }
 
private:
        std::mutex                             _lock;
        typename RCUManager<T>::PtrToSharedPtr _current_write_old;
        std::list<std::shared_ptr<T> >         _dead_wood;
};
 
template <class T>
class /*LIBPBD_API*/ RCUWriter
{
public:
        RCUWriter (RCUManager<T>& manager)
            : _manager (manager)
            , _copy (_manager.write_copy ())
        {
        }
 
        ~RCUWriter ()
        {
                if (_copy.unique ()) {
                        /* As intended, our copy is the only reference
                           to the object pointed to by _copy. Update
                           the manager with the (presumed) modified
                           version.
                        */
                        _manager.update (_copy);
                } else {
                        /* 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?
                         */
                }
        }
 
        std::shared_ptr<T> get_copy () const
        {
                return _copy;
        }
 
private:
        RCUManager<T>&     _manager;
        std::shared_ptr<T> _copy;
};
 
#endif /* __pbd_rcu_h__ */