Re: atomic operations for shared_ptr ?

[Bronek Kozicki <brok at spamcop dot net>]

On 25/08/2013 09:34, Federico Terraneo wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 08/24/2013 08:58 PM, Bronek Kozicki wrote:
> > On 24/08/2013 18:51, Jonathan Wakely wrote:
> > > On 24 August 2013 18:45, Bronek Kozicki wrote:
> > > > what are the current plans for supporting atomic_* free
> > > > functions for shared_ptr, as defined in C++11 (20.6.2 "Header
> > > > <memory> synopsis")? These would be very useful for passing
> > > > shared_ptr objects between threads, esp. if there are multiple
> > > > readers and single writer.
> > >
> > > I've been thinking about it recently and am probably just going
> > > to implement it with a single global mutex used for all
> > > shared_ptr instances.
> >
> >
> > erm, but that would be even worse than using mutexes as in my
> > example code ....
>
> A while ago I was looking for a lock-free algorithm for reference
> counted smart pointers, and found this:
> http://www.drdobbs.com/atomic-reference-counting-pointers/184401888.

The problem with implementation of atomic_load and atomic_store is not 
reference counters, these have been atomic for a long time already. And 
are guaranteed to be so by C++11 , so the following is safe to be 
executed on many threads, concurrently:

shared_ptr<Data> data() { return data_; } // data_ owned by thread1

thread2:
  auto a1 = data();

thread3:
  auto a2 = data();

// etc.

Each thread atomically bumps up the reference counter (typically single 
assembly instruction), and there is very little space for performance 
improvements too.

The problem is with accessing the shared_ptr at the same moment when it 
is being reset by another thread, to a new pointee. This is not 
guaranteed to be thread-safe and thus either separate synchronization is 
needed, or one has to use atomic_load, atomic_store etc. overloads for 
shared_ptr, if they are implemented.

Trouble implementing those is that, in the typical implementation of 
shared pointer with reference count (both boost and libstdc++ happen to 
be such), two pointers have to be updated atomically: one is a pointer 
to actual data (_M_ptr in shared_ptr here) and the other is pointer to 
reference counters (_Sp_counted_base<_Lp>* encapsulated in _M_refcount 
in shared_ptr here). Since changing the object layout would break ABI, 
we are not at freedom to change this, even if it made some efficient 
lockfree algorithm available. The implementation of atomic_load, 
atomic_store etc. has to ensure that, once one data member (eg _M_ptr) 
has been read or updated, the other (eg  _M_refcount) will be read (or 
updated) in state consistent with the first one.

I do not quite see how the instructions you point to could help here, 
they seem to be a crutch in PowerPC architecture for the lack of 
read-modify-write instructions (in 2004). For more modern architectures 
we do have those, for single memory location. The example you point to 
does not deal with two memory locations either, as in example routine 
aSwap the operation is not actually atomic in respect to both r1 and r2 
(i.e. r2 could have been modified while update to r1 was being 
performed, and the operation would update r2 nevertheless - or as the 
author says "second memory location (arg r2) must not be subject to 
contention").

Actually, our problem can be easily solved on architectures with 
optimistic synchronisation primitives (since they enable atomic updates 
of multiple memory locations), but currently only one processer type has 
the necessary instructions, it is Intel TSX (only some processors of 
Haswell family). Before this becomes more popular (and supported by gcc, 
e.g. via intrinsics) we simply need a way to efficiently lock _M_ptr and 
_M_refcount before reading or writing those inside implementation of 
atomic_load, etc. overloads for shared_ptr.


B.