From: xushiweizh_at_[hidden]
Date: 2008-05-12 10:53:18
Author: xushiwei
Date: 2008-05-12 10:53:17 EDT (Mon, 12 May 2008)
New Revision: 45299
URL: http://svn.boost.org/trac/boost/changeset/45299
Log:
ticket #1879: Workaround ABA problem.
Added:
sandbox/memory/boost/lockfree/tagged_ptr.hpp (contents, props changed)
Text files modified:
sandbox/memory/boost/detail/winapi/atomic/atomic_builtins.hpp | 27 +++++++++++
sandbox/memory/boost/detail/winapi/atomic/windows.hpp | 22 ++++++++
sandbox/memory/boost/lockfree/stack.hpp | 94 +++++++++++++++++++--------------------
3 files changed, 92 insertions(+), 51 deletions(-)
Modified: sandbox/memory/boost/detail/winapi/atomic/atomic_builtins.hpp
==============================================================================
--- sandbox/memory/boost/detail/winapi/atomic/atomic_builtins.hpp (original)
+++ sandbox/memory/boost/detail/winapi/atomic/atomic_builtins.hpp 2008-05-12 10:53:17 EDT (Mon, 12 May 2008)
@@ -60,6 +60,33 @@
}
// -------------------------------------------------------------------------
+
+__forceinline LONG64 WINAPI InterlockedExchange64(
+ volatile PLONG64 Target, LONG64 Value)
+{
+ __sync_synchronize();
+ return __sync_lock_test_and_set(Target, Value);
+}
+
+__forceinline bool WINAPI CompareAndSwap64(
+ PLONG64 Destination, LONG64 Exchange, LONG64 Comperand)
+{
+ return __sync_bool_compare_and_swap_8(Destination, Comperand, Exchange);
+}
+
+// -------------------------------------------------------------------------
+
+typedef int ATOMIC_LONG128_ __attribute__ ((mode (TI)));
+typedef ATOMIC_LONG128_ ATOMIC_LONG128;
+typedef ATOMIC_LONG128_* PATOMIC_LONG128;
+
+__forceinline bool WINAPI CompareAndSwap128(
+ PATOMIC_LONG128 Destination, ATOMIC_LONG128 Exchange, ATOMIC_LONG128 Comperand)
+{
+ return __sync_bool_compare_and_swap_16(Destination, Comperand, Exchange);
+}
+
+// -------------------------------------------------------------------------
// $Log: $
#endif /* BOOST_DETAIL_WINAPI_ATOMIC_ATOMIC_BUILTINS_HPP */
Modified: sandbox/memory/boost/detail/winapi/atomic/windows.hpp
==============================================================================
--- sandbox/memory/boost/detail/winapi/atomic/windows.hpp (original)
+++ sandbox/memory/boost/detail/winapi/atomic/windows.hpp 2008-05-12 10:53:17 EDT (Mon, 12 May 2008)
@@ -32,10 +32,10 @@
#if defined(BOOST_DETAIL_WINSDK_VC6)
-__forceinline PVOID WINAPI boost_InterlockedCompareExchange(
+__forceinline LONG WINAPI boost_InterlockedCompareExchange(
LPLONG Destination, LONG Exchange, LONG Comperand)
{
- return InterlockedCompareExchange(
+ return (LONG)InterlockedCompareExchange(
(PVOID*)Destination, (PVOID)Exchange, (PVOID)Comperand);
}
@@ -68,6 +68,24 @@
#endif
// -------------------------------------------------------------------------
+
+__forceinline bool WINAPI CompareAndSwap64(
+ PLONG64 Destination, LONG64 Exchange, LONG64 Comperand)
+{
+ bool ok;
+ __asm {
+ mov eax,[long ptr Comperand]
+ mov edx,[long ptr Comperand+1]
+ mov ebx,[long ptr Exchange]
+ mov ecx,[long ptr Exchange+1]
+ mov edi,[Destination]
+ lock cmpxchg8b [edi]
+ setz [ok]
+ }
+ return ok;
+}
+
+// -------------------------------------------------------------------------
// $Log: $
#endif /* BOOST_DETAIL_WINAPI_ATOMIC_WINDOWS_HPP */
Modified: sandbox/memory/boost/lockfree/stack.hpp
==============================================================================
--- sandbox/memory/boost/lockfree/stack.hpp (original)
+++ sandbox/memory/boost/lockfree/stack.hpp 2008-05-12 10:53:17 EDT (Mon, 12 May 2008)
@@ -12,24 +12,8 @@
#ifndef BOOST_LOCKFREE_STACK_HPP
#define BOOST_LOCKFREE_STACK_HPP
-#ifndef BOOST_DETAIL_DEBUG_HPP
-#include <boost/detail/debug.hpp>
-#endif
-
-#ifndef BOOST_DETAIL_WINAPI_WINBASE_H
-#include <boost/detail/winapi/winbase.h>
-#endif
-
-// -------------------------------------------------------------------------
-
-#ifndef NS_BOOST_LOCKFREE_BEGIN
-#define NS_BOOST_LOCKFREE_BEGIN namespace boost { namespace lockfree {
-#define NS_BOOST_LOCKFREE_END } }
-#define NS_BOOST_LOCKFREE boost::lockfree
-#endif
-
-#ifndef BOOST_LOCKFREE_CALL
-#define BOOST_LOCKFREE_CALL
+#ifndef BOOST_LOCKFREE_TAGGED_PTR_HPP
+#include "tagged_ptr.hpp"
#endif
NS_BOOST_LOCKFREE_BEGIN
@@ -46,54 +30,66 @@
public:
class node
{
- private:
- node* m_prev;
- friend class stack;
-
public:
- node* prev() const { return m_prev; }
+ node* _m_prev;
+ node* prev() const { return _m_prev; }
+#if defined(_DEBUG)
+ node() : _m_prev(NULL) {}
+#endif
};
private:
- node* m_top;
+ tagged_ptr<node> m_top;
-public:
- stack() : m_top(NULL)
+ struct PushOp
{
- }
+ node* m_val;
+ PushOp(node* val) : m_val(val) {}
+ node* BOOST_LOCKFREE_CALL operator()(node* top) const {
+ m_val->_m_prev = top;
+ return m_val;
+ }
+ static bool BOOST_LOCKFREE_CALL valid(node* top) {
+ return true;
+ }
+ };
- void BOOST_LOCKFREE_CALL push(node* val)
+ struct PopOp
{
- node* the_top = m_top;
- for (;;)
- {
- val->m_prev = the_top;
- node* the_top2 = (node*)
- InterlockedCompareExchangePointer((PVOID*)&m_top, val, the_top);
- if (the_top2 == the_top)
- return;
- the_top = the_top2;
+ node* m_ret;
+ PopOp() : m_ret(NULL) {}
+ node* BOOST_LOCKFREE_CALL operator()(node* top) {
+ m_ret = top;
+ return top->_m_prev;
}
+ static bool BOOST_LOCKFREE_CALL valid(node* top) {
+ return top != NULL;
+ }
+ };
+
+public:
+ stack() {}
+
+ void BOOST_LOCKFREE_CALL push(node* val)
+ {
+ BOOST_DETAIL_ASSERT(val->_m_prev == NULL);
+ m_top.set(PushOp(val));
}
node* BOOST_LOCKFREE_CALL clear()
{
- return (node*)InterlockedExchangePointer((PVOID*)&m_top, NULL);
+ return m_top.clear();
}
node* BOOST_LOCKFREE_CALL pop()
{
- node* the_top = m_top;
- for (;;)
- {
- if (the_top == NULL)
- return NULL;
- node* the_top2 = (node*)
- InterlockedCompareExchangePointer((PVOID*)&m_top, the_top->m_prev, the_top);
- if (the_top2 == the_top)
- return the_top;
- the_top = the_top2;
- }
+ PopOp popOp;
+ m_top.set(popOp);
+#if defined(_DEBUG)
+ if (popOp.m_ret)
+ popOp.m_ret->_m_prev = NULL;
+#endif
+ return popOp.m_ret;
}
};
Added: sandbox/memory/boost/lockfree/tagged_ptr.hpp
==============================================================================
--- (empty file)
+++ sandbox/memory/boost/lockfree/tagged_ptr.hpp 2008-05-12 10:53:17 EDT (Mon, 12 May 2008)
@@ -0,0 +1,139 @@
+//
+// boost/lockfree/tagged_ptr.hpp
+//
+// Copyright (c) 2004 - 2008 xushiwei (xushiweizh_at_[hidden])
+//
+// Distributed under 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)
+//
+// See http://www.boost.org/libs/lockfree/todo.htm for documentation.
+//
+#ifndef BOOST_LOCKFREE_TAGGED_PTR_HPP
+#define BOOST_LOCKFREE_TAGGED_PTR_HPP
+
+#ifndef BOOST_DETAIL_WINAPI_WINBASE_H
+#include <boost/detail/winapi/winbase.h>
+#endif
+
+#ifndef BOOST_DETAIL_DEBUG_HPP
+#include <boost/detail/debug.hpp>
+#endif
+
+// -------------------------------------------------------------------------
+
+#ifndef NS_BOOST_LOCKFREE_BEGIN
+#define NS_BOOST_LOCKFREE_BEGIN namespace boost { namespace lockfree {
+#define NS_BOOST_LOCKFREE_END } }
+#define NS_BOOST_LOCKFREE boost::lockfree
+#endif
+
+#ifndef BOOST_LOCKFREE_CALL
+#define BOOST_LOCKFREE_CALL
+#endif
+
+#if defined(_WIN32) || defined(__BIT32__)
+#define NS_BOOST_LOCKFREE_BIT32
+#elif defined(_WIN64) || defined(__BIT64__) || defined(__x86_64__)
+#define NS_BOOST_LOCKFREE_BIT64
+#else
+#error "Unknown Configurations"
+#endif
+
+NS_BOOST_LOCKFREE_BEGIN
+
+// -------------------------------------------------------------------------
+// class tagged_ptr
+
+#if defined(NS_BOOST_LOCKFREE_BIT32)
+
+template <class Type>
+class tagged_ptr
+{
+private:
+ LONG64 m_p;
+
+public:
+ tagged_ptr() : m_p(0) {}
+
+ template <class FuncT>
+ bool BOOST_LOCKFREE_CALL set(FuncT op)
+ {
+ BOOST_DETAIL_ASSERT(sizeof(Type*) == sizeof(LONG32));
+ for (;;)
+ {
+ tagged_ptr vOld = *this;
+ Type* pOld = vOld.get();
+ if (!op.valid(pOld))
+ return false;
+
+ tagged_ptr vNew = vOld;
+ vNew.m_p += (LONG64)1 << 32;
+ *(LONG32*)&vNew.m_p = (LONG32)static_cast<Type*>(op(pOld));
+ if (CompareAndSwap64(&m_p, vNew.m_p, vOld.m_p))
+ return true;
+ }
+ }
+
+ __forceinline Type* BOOST_LOCKFREE_CALL clear()
+ {
+ return (Type*)InterlockedExchangePointer((PVOID*)&m_p, NULL);
+ }
+
+ __forceinline Type* BOOST_LOCKFREE_CALL get() const
+ {
+ return (Type*)(LONG32)m_p;
+ }
+};
+
+#elif defined(NS_BOOST_LOCKFREE_BIT64)
+
+template <class Type>
+class tagged_ptr
+{
+private:
+ ATOMIC_LONG128 m_p;
+
+public:
+ tagged_ptr() : m_p(0) {}
+
+ template <class FuncT>
+ bool BOOST_LOCKFREE_CALL set(FuncT op)
+ {
+ BOOST_DETAIL_ASSERT(sizeof(Type*) == sizeof(LONG64));
+ for (;;)
+ {
+ tagged_ptr vOld = *this;
+ Type* pOld = vOld.get();
+ if (!op.valid(pOld))
+ return false;
+
+ tagged_ptr vNew = vOld;
+ vNew.m_p += (ATOMIC_LONG128)1 << 64;
+ *(LONG64*)&vNew.m_p = (LONG64)static_cast<Type*>(op(pOld));
+ if (CompareAndSwap128(&m_p, vNew.m_p, vOld.m_p))
+ return true;
+ }
+ }
+
+ __forceinline Type* BOOST_LOCKFREE_CALL clear()
+ {
+ return (Type*)InterlockedExchangePointer((PVOID*)&m_p, NULL);
+ }
+
+ __forceinline Type* BOOST_LOCKFREE_CALL get() const
+ {
+ return (Type*)(LONG64)m_p;
+ }
+};
+
+#else
+#error "Unknown Configurations"
+#endif
+
+// -------------------------------------------------------------------------
+// $Log: $
+
+NS_BOOST_LOCKFREE_END
+
+#endif /* BOOST_LOCKFREE_TAGGED_PTR_HPP */