Would anybody help to review my implementation of user-space RCU with shared_ptr?

[Yong Sun]

Here is the question I raised on stack-overflow, no reply yet :(

http://stackoverflow.com/questions/2823512/using-shared-ptr-to-implement-rcu-read-copy-update

Thanks in advance ...

Regards,

[Dmitriy Vyukov]

On Jun 7, 6:26 am, Yong Sun <find...@gmail.com> wrote:
> Here is the question I raised on stack-overflow, no reply yet :(
>

> http://stackoverflow.com/questions/2823512/using-shared-ptr-to-implem...

Hi Yong,

You've came to the right shop :)

It won't work with the current implementation.

Consider:
rcu_const_pointer get_reading_copy ()
{
spin_until_eq (m_is_swapping, 0);
return m_data_ptr;
}
Reader waits for m_is_swapping==0, then reader starts copying the
pointer, and writer simultaneously starts mutating the pointer ->
crash.

// as spin_until_eq does not have memory barrier protection,
// we need to place a read barrier to protect the loading of
// new_data_ptr not to be re-ordered before its construction
Memory barriers is always a game of two. If one thread omits a memory
barrier, there is nothing another thread can do to compensate for
that. Memory barriers must be executed by both threads to get any
effect.

The easiest way to emulate smart pointer with strong thread-safety (a
thread can obtain a reference to an object even if he does not hold a
one yet) is to use shared_ptr+rw_mutex. I.e. When a thread reads the
ptr, he locks the mutex for reading; when a thread writes the ptr, he
locks the mutex for writing.
However both C++0x and boost provide reference counted objects with
strong thread safety. Consult latest boost sources - there are free
standing functions atomic_load/atomic_store/atomic_exchange/
atomic_compare_exchange for shared_ptr.


--
Dmitriy V'jukov

[Yong Sun]

Hi, Dmitriy,

Thanks so much for the reviewing !!! :)

As my understanding, it's quite clear to me, that I should protect the
copying of reader pointer, to prevent the writer to update it. While,
regarding to the memory barriers, did you mean that they are
unnecessary? Is it possible that the writer thread may get an pointer
of an un-constructed object due to the out-of-order execution on CPU?

I'm sorry that I am really a newbie on concurrent programming, please
forgive me if I asked a stupid questions :$

Regards,

--
Yong Sun <ma...@yongsun.me>

[Dmitriy Vyukov]

On Jun 8, 12:30 pm, Yong Sun <find...@gmail.com> wrote:
> Hi, Dmitriy,
>
> Thanks so much for the reviewing !!! :)
>
> As my understanding, it's quite clear to me, that I should protect the
> copying of reader pointer, to prevent the writer to update it. While,
> regarding to the memory barriers, did you mean that they are
> unnecessary? Is it possible that the writer thread may get an pointer
> of an un-constructed object due to the out-of-order execution on CPU?

It depends on how exactly you implement the whole thing.
boost/std/tr1 shared_ptr is not thread-safe. So you need to protect
concurrent accesses to it with some form of mutual exclusion. If you
use some ready-for-use mutex, then it will provide all the necessary
memory barriers internally. If you implement a mutex manually by means
of atomic operations, then you need to provide all the necessary
memory barriers too (that's not so about shared ptr, every mutex
implementation must do that).
If you use boost/std atomic functions for shared_ptr, then they will
provide all the necessary memory barriers internally, because they are
synchronization functions and meant for concurrent access.

You may also take a look at atomic-ptr-plus project:
http://sourceforge.net/projects/atomic-ptr-plus/files/
It provides to kinds of pointers - atomic and local. Local is similar
to shared_ptr, i.e. not thread-safe. And atomic is fully thread safe,
i.e. you are allowed to copy it in one thread, and concurrently mutate
it in another.


--
Dmitriy V'jukov

[Yong Sun]

Thanks a lot for your kindly help! :)

--
Yong Sun <ma...@yongsun.me>