# common/include/boost/lockfree/detail/cas.hpp

    00001 //  Copyright (C) 2007, 2008, 2009 Tim Blechmann & Thomas Grill
    00002 //
    00003 //  Distributed under the Boost Software License, Version 1.0. (See
    00004 //  accompanying file LICENSE_1_0.txt or copy at
    00005 //  http://www.boost.org/LICENSE_1_0.txt)
    00006
    00007 //  Disclaimer: Not a Boost library.
    00008
    00009 #ifndef BOOST_LOCKFREE_CAS_HPP_INCLUDED
    00010 #define BOOST_LOCKFREE_CAS_HPP_INCLUDED
    00011
    00012 #include <boost/lockfree/detail/prefix.hpp>
    00013 #include <boost/interprocess/detail/atomic.hpp>
    00014 #include <boost/detail/lightweight_mutex.hpp>
    00015 #include <boost/static_assert.hpp>
    00016
    00017 #include <boost/cstdint.hpp>
    00018
    00019 #include <boost/mpl/map.hpp>
    00020 #include <boost/mpl/at.hpp>
    00021 #include <boost/mpl/if.hpp>
    00022 #include <boost/mpl/long.hpp>
    00023
    00024 #ifdef __SSE2__
    00025 #include "emmintrin.h"
    00026 #endif
    00027
    00028 namespace boost
    00029 {
    00030 namespace lockfree
    00031 {
    00032
    00033 inline void memory_barrier(void)
    00034 {
    00035 #if defined(__SSE2__)
    00036     _mm_mfence();
    00037
    00038 #elif defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) &&      \
    00039                                                 (__GNUC_MINOR__ >= 1))) \
    00040     || defined(__INTEL_COMPILER)
    00041     __sync_synchronize();
    00042 #elif defined(__GNUC__) && defined (__i386__)
    00043     asm volatile("lock; addl $0,0(%%esp)":::"memory");
    00044 #elif defined(_MSC_VER) && (_MSC_VER >= 1300)
    00045     _ReadWriteBarrier();
    00046 #elif defined(__APPLE__)
    00047     OSMemoryBarrier();
    00048 #elif defined(AO_HAVE_nop_full)
    00049     AO_nop_full();
    00050 #else
    00051 #   warning "no memory barrier implemented for this platform"
    00052 #endif
    00053 }
    00054
    00055 inline void read_memory_barrier(void)
    00056 {
    00057 #if defined(__SSE2__)
    00058     _mm_lfence();
    00059 #else
    00060     memory_barrier();
    00061 #endif
    00062 }
    00063
    00064 template <typename C>
    00065 struct atomic_cas_emulator
    00066 {
    00067     static inline bool cas(C * addr, C old, C nw)
    00068     {
    00069         static boost::detail::lightweight_mutex guard;
    00070         boost::detail::lightweight_mutex::scoped_lock lock(guard);
    00071
    00072         if (*addr == old)
    00073         {
    00074             *addr = nw;
    00075             return true;
    00076         }
    00077         else
    00078             return false;
    00079     }
    00080
    00081     typedef C cas_type;
    00082 };
    00083
    00084
    00085 template <typename C>
    00086 inline bool atomic_cas_emulation(C * addr, C old, C nw)
    00087 {
    00088     return atomic_cas_emulator<C>::cas(addr, old, nw);
    00089 }
    00090
    00091 using boost::uint32_t;
    00092 using boost::uint64_t;
    00093
    00094 struct atomic_cas32
    00095 {
    00096     static inline bool cas(volatile uint32_t * addr,
    00097                            uint64_t const & old,
    00098                            uint64_t const & nw)
    00099     {
    00100 #if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) && (__GNUC_MINOR__ >= 1)) ) || defined(__INTEL_COMPILER)
    00101         return __sync_bool_compare_and_swap(addr, old, nw);
    00102 #else
    00103         return boost::interprocess::detail::atomic_cas32(addr, old, nw) == old;
    00104 #endif
    00105     }
    00106     typedef uint32_t cas_type;
    00107
    00108     static const bool is_lockfree = true;
    00109 };
    00110
    00111 struct atomic_cas64
    00112 {
    00113     typedef uint64_t cas_type;
    00114
    00115     static inline bool cas(volatile uint64_t * addr,
    00116                            uint64_t const & old,
    00117                            uint64_t const & nw)
    00118     {
    00119 #if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ > 1)) \
    00120                            || ((__GNUC__ == 4) && (__GNUC_MINOR__ == 1) && defined(__x86_64__)) ) \
    00121         || defined(__INTEL_COMPILER)
    00122         return __sync_bool_compare_and_swap(addr, old, nw);
    00123 #elif defined(_M_IX86)
    00124         return InterlockedCompareExchange(reinterpret_cast<volatile LONG*>(addr),
    00125                                           reinterpret_cast<LONG>(nw),
    00126                                           reinterpret_cast<LONG>(old)) == old;
    00127 #elif defined(_M_X64)
    00128         return InterlockedCompareExchange(reinterpret_cast<volatile LONG*>(addr),
    00129                                           reinterpret_cast<LONG>(nw),
    00130                                           reinterpret_cast<LONG>(old)) == old;
    00131 #else
    00132 #define CAS_BLOCKING
    00133 #warning ("blocking CAS emulation")
    00134         return atomic_cas_emulation((uint64_t *)addr, old, nw);
    00135 #endif
    00136     }
    00137
    00138 #ifdef CAS_BLOCKING
    00139 #undef CAS_BLOCKING
    00140     static const bool is_lockfree = false;
    00141 #else
    00142     static const bool is_lockfree = true;
    00143 #endif
    00144 };
    00145
    00146 struct atomic_cas128
    00147 {
    00148 #if defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_16)
    00149     typedef int cas_type __attribute__ ((mode (TI)));
    00150 #else
    00151     struct cas_type
    00152     {
    00153         bool operator==(cas_type const & rhs)
    00154         {
    00155             return (data[0] == rhs.data[0]) &&
    00156                 (data[1] == rhs.data[1]);
    00157         }
    00158
    00159         uint64_t data[2];
    00160     };
    00161 #endif
    00162
    00163     static inline bool cas(volatile cas_type * addr, cas_type const & old, cas_type const & nw)
    00164     {
    00165 #if defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_16)
    00166         return __sync_bool_compare_and_swap_16(addr, old, nw);
    00167 #else
    00168 #define CAS_BLOCKING
    00169 //#warning ("blocking CAS emulation")
    00170         return atomic_cas_emulation((cas_type*)addr, old, nw);
    00171 #endif
    00172     }
    00173
    00174 #ifdef CAS_BLOCKING
    00175 #undef CAS_BLOCKING
    00176     static const bool is_lockfree = false;
    00177 #else
    00178     static const bool is_lockfree = true;
    00179 #endif
    00180 };
    00181
    00182 namespace detail
    00183 {
    00184 using namespace boost::mpl;
    00185
    00186 template<typename C>
    00187 struct atomic_cas
    00188 {
    00189 private:
    00190     typedef map3<pair<long_<4>, atomic_cas32>,
    00191         pair<long_<8>, atomic_cas64>,
    00192         pair<long_<16>, atomic_cas128>
    00193         > cas_map;
    00194
    00195     typedef typename at<cas_map, long_<sizeof(C)> >::type atomic_cas_t;
    00196
    00197     typedef typename if_<has_key<cas_map, long_<sizeof(C)> >,
    00198         atomic_cas_t,
    00199         atomic_cas_emulator<C> >::type cas_t;
    00200
    00201     typedef typename cas_t::cas_type cas_value_t;
    00202
    00203 public:
    00204     static inline bool cas(volatile C * addr, C const & old, C const & nw)
    00205     {
    00206         return cas_t::cas((volatile cas_value_t*)addr,
    00207                           *(cas_value_t*)&old,
    00208                           *(cas_value_t*)&nw);
    00209     }
    00210
    00211     static const bool is_lockfree = cas_t::is_lockfree;
    00212 };
    00213
    00214 } /* namespace detail */
    00215
    00216 using detail::atomic_cas;
    00217
    00218 template <typename C>
    00219 inline bool cas(volatile C * addr, C const & old, C const & nw)
    00220 {
    00221     return atomic_cas<C>::cas(addr, old, nw);
    00222 }
    00223
    00224 } /* namespace lockfree */
    00225 } /* namespace boost */
    00226
    00227 #endif /* BOOST_LOCKFREE_CAS_HPP_INCLUDED */