Ardour  8.12
rcu.h
Go to the documentation of this file.
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 <atomic>
24 #include <mutex>
25 #include <memory>
26 
27 #include "boost/smart_ptr/detail/yield_k.hpp"
28 
29 #include <list>
30 
31 #include "pbd/libpbd_visibility.h"
32 
52 template <class T>
53 class /*LIBPBD_API*/ RCUManager
54 {
55 public:
56  RCUManager (T* object_to_be_managed)
57  {
58  _active_reads = 0;
59  managed_object = new std::shared_ptr<T> (object_to_be_managed);
60  }
61 
62  virtual ~RCUManager ()
63  {
64  /* This just deletes the shared ptr, but of course this may
65  also be the last reference to the managed object.
66  */
67  delete managed_object.load ();
68  }
69 
70  std::shared_ptr<T const> reader () const
71  {
72  std::shared_ptr<T> rv;
73 
74  /* Keep count of any readers in this section of code, so writers can
75  * wait until managed_object is no longer in use after an atomic exchange
76  * before dropping it.
77  */
78  /* no reads or writes below this atomic store (e.g. the copying
79  * of *managed_object) can move before this "barrier".
80  */
81  _active_reads.fetch_add (1, std::memory_order_release);
82  rv = *managed_object;
83  /* no reads or writes below this atomic store (e.g. the copying
84  * of *managed_object) can move before this "barrier", and this
85  * also synchronizes with a memory_order_acquire load when
86  * testing for active readers (see below).
87  */
88  _active_reads.fetch_sub (1, std::memory_order_release);
89 
90  return rv;
91  }
92 
93  /* this is an abstract base class - how these are implemented depends on the assumptions
94  * that one can make about the users of the RCUManager. See SerializedRCUManager below
95  * for one implementation.
96  */
97 
98  virtual std::shared_ptr<T> write_copy () = 0;
99  virtual bool update (std::shared_ptr<T> new_value) = 0;
100 
101 protected:
102  typedef std::shared_ptr<T>* PtrToSharedPtr;
103  std::atomic<PtrToSharedPtr> managed_object;
104 
105  inline bool active_read () const {
106  return _active_reads.load (std::memory_order_acquire) != 0;
107  }
108 
109 private:
110  mutable std::atomic<int> _active_reads;
111 };
112 
141 template <class T>
142 class /*LIBPBD_API*/ SerializedRCUManager : public RCUManager<T>
143 {
144 public:
145  SerializedRCUManager(T* new_managed_object)
146  : RCUManager<T>(new_managed_object)
147  , _current_write_old (0)
148  {
149  }
150 
151  void init (std::shared_ptr<T> object_to_be_managed) {
152  assert (*RCUManager<T>::managed_object == std::shared_ptr<T> ());
153  RCUManager<T>::managed_object = new std::shared_ptr<T> (object_to_be_managed);
154  }
155 
156  std::shared_ptr<T> write_copy ()
157  {
158  _lock.lock ();
159 
160  // clean out any dead wood
161 
162  typename std::list<std::shared_ptr<T> >::iterator i;
163 
164  for (i = _dead_wood.begin (); i != _dead_wood.end ();) {
165  if ((*i).unique ()) {
166  i = _dead_wood.erase (i);
167  } else {
168  ++i;
169  }
170  }
171 
172  /* store the current so that we can do compare and exchange
173  * when someone calls update(). Notice that we hold
174  * a lock, so this store of managed_object is atomic.
175  */
176 
178 
179  /* now do the (potentially arbitrarily expensive data copy of
180  * the RCU-managed object
181  */
182 
183  std::shared_ptr<T> new_copy (new T (**_current_write_old));
184 
185  return new_copy;
186 
187  /* notice that the write lock is still held: update() or abort() MUST
188  * be called or we will cause another writer to stall.
189  */
190  }
191 
192  void abort () {
193  _lock.unlock();
194  }
195 
196  bool update (std::shared_ptr<T> new_value)
197  {
198  /* we still hold the write lock - other writers are locked out */
199 
200  typename RCUManager<T>::PtrToSharedPtr new_spp = new std::shared_ptr<T> (new_value);
201 
202  /* update, by atomic compare&swap. Only succeeds if the old
203  * value has not been changed.
204  *
205  * XXX but how could it? we hold the freakin' lock!
206  */
207 
208  bool ret = RCUManager<T>::managed_object.compare_exchange_strong (_current_write_old, new_spp);
209 
210  if (ret) {
211  /* successful update
212  *
213  * wait until there are no active readers. This ensures that any
214  * references to the old value have been fully copied into a new
215  * shared_ptr, and thus have had their reference count incremented.
216  */
217 
218  for (unsigned i = 0; RCUManager<T>::active_read (); ++i) {
219  /* spin being nice to the scheduler/CPU */
220  boost::detail::yield (i);
221  }
222 
223 #if 0 // TODO find a good solition here...
224  /* if we are not the only user, put the old value into dead_wood.
225  * if we are the only user, then it is safe to drop it here.
226  */
227 
228  if (!_current_write_old->unique ()) {
229  _dead_wood.push_back (*_current_write_old);
230  }
231 #else
232  /* above ->unique() condition is subject to a race condition.
233  *
234  * Particulalry with JACK2 graph-order callbacks arriving
235  * concurrently to processing, which can lead to heap-use-after-free
236  * of the RouteList.
237  *
238  * std::shared_ptr<T>::use_count documetation reads:
239  * > In multithreaded environment, the value returned by use_count is approximate
240  * > (typical implementations use a memory_order_relaxed load).
241  */
242  _dead_wood.push_back (*_current_write_old);
243 #endif
244 
245  /* now delete it - if we are the only user, this deletes the
246  * underlying object. If other users existed, then there will
247  * be an extra reference in _dead_wood, ensuring that the
248  * underlying object lives on even when the other users
249  * are done with it
250  */
251 
252  delete _current_write_old;
253  }
254 
255  /* unlock, allowing other writers to proceed */
256 
257  _lock.unlock ();
258 
259  return ret;
260  }
261 
262  void no_update () {
263  /* just releases the lock, in the event that no changes are
264  made to a write copy.
265  */
266  _lock.unlock ();
267  }
268 
269  void flush ()
270  {
271  std::lock_guard<std::mutex> lm (_lock);
272  _dead_wood.clear ();
273  }
274 
275 private:
276  std::mutex _lock;
278  std::list<std::shared_ptr<T> > _dead_wood;
279 };
280 
296 template <class T>
297 class /*LIBPBD_API*/ RCUWriter
298 {
299 public:
301  : _manager (manager)
302  , _copy (_manager.write_copy ())
303  {
304  }
305 
307  {
308  if (_copy.unique ()) {
309  /* As intended, our copy is the only reference
310  to the object pointed to by _copy. Update
311  the manager with the (presumed) modified
312  version.
313  */
314  _manager.update (_copy);
315  } else {
316  /* This means that some other object is using our copy
317  * of the object. This can only happen if the scope in
318  * which this RCUWriter exists passed it to a function
319  * that created a persistent reference to it, since the
320  * copy was private to this particular RCUWriter. Doing
321  * so will not actually break anything but it violates
322  * the design intention here and so we do not bother to
323  * update the manager's copy.
324  *
325  * XXX should we print a warning about this?
326  */
327  }
328  }
329 
330  std::shared_ptr<T> get_copy () const
331  {
332  return _copy;
333  }
334 
335 private:
337  std::shared_ptr<T> _copy;
338 };
339 
340 #endif /* __pbd_rcu_h__ */
Definition: rcu.h:54
std::shared_ptr< T > * PtrToSharedPtr
Definition: rcu.h:102
virtual bool update(std::shared_ptr< T > new_value)=0
std::atomic< PtrToSharedPtr > managed_object
Definition: rcu.h:103
virtual std::shared_ptr< T > write_copy()=0
std::atomic< int > _active_reads
Definition: rcu.h:110
std::shared_ptr< T const > reader() const
Definition: rcu.h:70
virtual ~RCUManager()
Definition: rcu.h:62
bool active_read() const
Definition: rcu.h:105
RCUManager(T *object_to_be_managed)
Definition: rcu.h:56
Definition: rcu.h:298
std::shared_ptr< T > get_copy() const
Definition: rcu.h:330
RCUManager< T > & _manager
Definition: rcu.h:336
RCUWriter(RCUManager< T > &manager)
Definition: rcu.h:300
std::shared_ptr< T > _copy
Definition: rcu.h:337
~RCUWriter()
Definition: rcu.h:306
void flush()
Definition: rcu.h:269
void no_update()
Definition: rcu.h:262
RCUManager< T >::PtrToSharedPtr _current_write_old
Definition: rcu.h:277
std::shared_ptr< T > write_copy()
Definition: rcu.h:156
void init(std::shared_ptr< T > object_to_be_managed)
Definition: rcu.h:151
void abort()
Definition: rcu.h:192
SerializedRCUManager(T *new_managed_object)
Definition: rcu.h:145
std::mutex _lock
Definition: rcu.h:276
std::list< std::shared_ptr< T > > _dead_wood
Definition: rcu.h:278
bool update(std::shared_ptr< T > new_value)
Definition: rcu.h:196