[boost] Any progress on atomic ops libraries?

From: Roland Schwarz (roland.schwarz_at_[hidden])
Date: 2006-11-18 13:44:26

Despite the obvious interest in lock free algorithms,
we still have no atomic ops library in boost.

Al though there have been some discussions on the list
I did not see any real attempt to come up with such
a library. I am unsure about the reasons for this:

1) Is it because it is believed that this will not
    be possible without language change?

2) Is it because it is too hard to do?

3) There are already some developments in preparatory,
    but yet unpublished state?

4) Any other, I cannot imagine?

Perhaps, I am on the wrong track, but I tried to
implement something along Boehms N2047 proposal.
I know that this is only a prototype yet, but I'd like
to spur discussion about the topic.

I attach the prototype, which currently is for 32bit
MSVC. I am planning to add support for gcc soon.

I would be very glad if this would trigger some
further development and fruitful discussions, which
eventually will lead into creation of such a library.

I would also be glad, if someone could tell me why
there is no such library yet.

Roland


//  (C) Roland Schwarz 2006.
//  Use, modification and distribution are subject to the Boost Software License,
//  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt).
//

#ifndef ATOMIC_HPP__
#define ATOMIC_HPP__

// Al though the following compiler intrinsics are available for
// msvc-6.1, the code does not compile, due to lack of partial
// specialization.

extern "C" {
   long  __cdecl _InterlockedCompareExchange(void volatile*, long, long);
   long  __cdecl _InterlockedExchange(void volatile*, long);
   long  __cdecl _InterlockedExchangeAdd(void volatile*, long Value);
//   void _ReadWriteBarrier();
}

#pragma intrinsic(_InterlockedCompareExchange)
#pragma intrinsic(_InterlockedExchange)
#pragma intrinsic(_InterlockedExchangeAdd)
//#pragma intrinsic(_ReadWriteBarrier)

// The interface of the atomic class is modelled after 
// proposal N2047 from Hans-J Boehm.
// However I did not try to implement the query interface,
// nor the native part, or the emulations.
//
// This implementation currently is for 32bit MSVC compilers, making
// use of the _Interlocked* intrinsics. Also I use the __declspec(align())
// statement to control proper alignment. I hope it will be straight
// forward to find similar compiler support on other compilers as
// well.
//
// I aimed for the following properties:
// 1) atomic<user_type> is a container which can be specialized
//    for "user_type"s that are POD and have same size as the
//    native atomic type of the compiler/platform.
// 2) atomic<user_type> can be extended to non POD types by
//    emulating atomicity with a mutex that protects ctor/dtor.
// 3) Can be extended to mixed 32 bit/64 bit.
// 4) Works with scalars/pointers/POD's
// 5) Dependency on other libs should be as minimal as possible
//    to make it suitable as a core class.
// 6) Shall be usable in single threaded applications too.
//
// Open questions:
// 1) Assignments between atomic<> types are currently not allowed.
//    This is in line with N2047. Should this feature be added?
//    What would it mean?
// 2) N2407 has only a boolean cas. I added the "previous value
//    returning" cas. I named the boolean: compare_and_store and
//    the other: compare_and_swap. Is this reasonable?
// 3) Should the scalar types further specialized to add
//    atomic incr and decr operators? Same question for pointers.
// 4) All ordering_constraints fall back to "ordered" unless
//    spezialized. Does this make sense?
// 5) Currently only types of same size, where object and value
//    representation is same (i.e POD) are allowed to make
//    reinterpret_cast safe. Is there a way to capture smaller 
//    POD types as well? E.g. atomic<bool>, atomic<short> ...

namespace concurrent {

    enum ordering_constraint {raw, acquire, release, ordered};

    template <class T, int size = sizeof(T)>
    struct atomic {
    private:
        // no implementation so far
        // could be used for mutex proteced specializations
        atomic();
    };

    // specialization for types with size of native atomic
    template <class T>
    struct atomic<T, sizeof(long)> {
        typedef long type;
        atomic(const T& x = T()) : pod(x){}

        // store
        template<ordering_constraint c>
            void store(const T& x)
        { _InterlockedExchange(&data, reinterpret_cast<const long&>(x)); }
        template<>
            void store<raw>(const T& x)
        { data = reinterpret_cast<volatile const long&>(x); }

            // load
        template <ordering_constraint c>
                T load() const 
        { long r = _InterlockedExchangeAdd(&data, 0);
            return reinterpret_cast<T&>(r);}
        template<>
            T load<raw>() const
        { return data; }
        
            // boolean cas
        template <ordering_constraint c>
                bool compare_and_store(const T& old_val, const T& new_val)
        { long r = _InterlockedCompareExchange(&data, 
            reinterpret_cast<const long&>(new_val), 
            reinterpret_cast<const long&>(old_val));
          return (reinterpret_cast<T&>(r) == old_val);
        }
            
        // returning previous cas
        template <ordering_constraint c>
                T compare_and_swap(const T& old_val, const T& new_val)
        { long r = _InterlockedCompareExchange(&data, 
            reinterpret_cast<const long&>(new_val), 
            reinterpret_cast<const long&>(old_val));
          return reinterpret_cast<T&>(r);
        }

        operator T() const { return load<ordered>(); }
            void operator=(const T& x) { store<ordered>(x); }
    private:
        // the union restricts usage to POD types only
        union {
            // force the alignment to requirements of compiler
            // intrinsics.
            // mutable is necessary, because the ExchangeAdd
            // is used to load data, so it is only conceptually
            // constant in the load function.
            __declspec(align(4)) mutable T volatile pod;
            __declspec(align(4)) mutable long volatile data;
        };
        // direct assignment between atomic types is not allowed
        atomic(const atomic<T, sizeof(long)>&);
        atomic<T,sizeof(long)>& operator=(const atomic<T,sizeof(long)>&);
    };
};

#endif


#include "atomic.hpp"

using namespace concurrent;

struct POD
{
    unsigned short low;
    unsigned short high;
};

struct nonPOD
{
    nonPOD() : low(0), high(0) {}
    unsigned short low;
    unsigned short high;
};

enum direction { north, east, south, west };

int main(int argc, char* argv[])
{
    atomic<POD> atomic_POD;
    POD aPOD= {1,2};

    atomic_POD.store<ordered>(aPOD);
    atomic_POD.store<raw>(aPOD);
    atomic_POD = aPOD;
    aPOD = atomic_POD;

    atomic<int> atomic_int;
    int aint = 42;

    atomic_int.store<ordered>(aint);
    atomic_int.store<raw>(aint);
    atomic_int = aint;
    aint = atomic_int;

    atomic<long> atomic_long;
    long along = 42;

    atomic_long.store<ordered>(along);
    atomic_long.store<raw>(along);
    atomic_long = along;
    along = atomic_long;

    atomic<int*> atomic_p;
    int* intp;

    atomic_p.store<ordered>(intp);
    atomic_p.store<raw>(intp);
    atomic_p = intp;
    intp = atomic_p;

    int prev;
    if (atomic_int.compare_and_store<ordered>(42,0)) {
        prev = atomic_int.compare_and_swap<ordered>(42,0);
    }

    atomic<direction> next_move;
    next_move = west;

    atomic<float> f;
    f.store<ordered>(1.2f);

    // the following line does not (and should not) compile
    //atomic<nonPOD> atomic_nonPOD;

    return 0;
}