[boost] Re: Smart Pointers - (many) thanks and (some)questions

From: Andy Glew (glew_at_[hidden])
Date: 1999-12-30 20:35:38

> The atomicity of storing pointers (yes,
> platform-dependent) is often the exact mechanism used to accomplish
> thread-safety. The corresponding use of shared_ptr might make a lot of
> sense. If you don't build the support directly into shared_ptr, then adding
> it in an external wrapper will incur an undesirable cost at runtime,
> especially on those platforms with support for the atomic decrement-and-test
> operations.

????

Scalar pointers are only read and write atomic.

While only reads and writes are required, on systems with suitable memory
ordering, to implement synchronization, such lock free synchronization
algorithms are nearly always either encapsulated, or user visible.

Urgh...  what I am trying to say is that just about any general implementation
of thread-safe containers, or any other compound object, will require 
an atomic read-modify-write. Which is not directly expressible in C or C++;
which requires an escape from the language.
    I.e. atomic RMWs are not C++, so this is non-portable.

Lock free synchronization algorithms, if I remember my thesis correctly,
nearly all depend on having storage poroportional to the number of processors.
So I don't think these are *general* in any reasonable sense.

However, testing and releasing a lock is often a component of atomic-RMW
synchronization:
        do {
            while( lockptr != 0 );
         } while CMPXCHG( lockptr, 0, my_address );
        ...
        lockptr = 0

This leads me to suggest the following as a potential goal:
    Read*/Write atomicity - multiple readers, one writer
and to suggest that Write* atomicity - having multiple simultaneous
writes be atomic - is something that can be dropped.

However^2, just about any non-intrusive smart pointer implementation
involves a coordinated action to two separate memory locations - the
pointer, and the bookkeeping info.

I don't think that there are any existing systems that can handle this 
with a hardware primitive, although a recent Stanford PhD thesis
suggests a new hardware primitive, DCAS2.  (For history buffs, the
Intel i860 *could* handle this.)

So, I am not 100% sure, but I suspect that there is no way to code
Read*/Write atomicity for a non-intrusive smart pointer that is general, 
without using a mutex or lock. At least not without assuming very
non-portable memory ordering rules.

So, again I suggest 

Required flavour:
    smart pointer with no synchronization or ordering

Desirable flavour:
    mutexed smart pointer

    Probably an optional parameter "synchronized" as 
    someone described would be the way to go, except for parameter creep.
    Such a parameter would allow specialization to use more
    efficient algorithms when desired, but might just
    fall back to basic mutexing.

    Probably most of the time an implementation that corresponded
    to a mutexed_ptr<T> template would suffice for mutexing,
    e.g.

        shared_ptr<T,/*synchronized=*/1> 
            == mutexed_ptr< shared_ptr<T,/*synchronized=*/0> >

    except for implicit conversion issues.

Desirable flavour, but I think unimplementable:
    read/write atomic, but not mutexed, smart pointer.