|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r84723 - in trunk: boost/lockfree boost/lockfree/detail libs/lockfree/test
From: tim_at_[hidden]
Date: 2013-06-10 08:31:39
Author: timblechmann
Date: 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013)
New Revision: 84723
URL: http://svn.boost.org/trac/boost/changeset/84723
Log:
lockfree: explicitly use bitmask to prevent aba tag overflow
workaround for msvc run-time check failure
Text files modified:
trunk/boost/lockfree/detail/freelist.hpp | 15 +++++++++++----
trunk/boost/lockfree/detail/tagged_ptr_dcas.hpp | 19 +++++++++++++------
trunk/boost/lockfree/detail/tagged_ptr_ptrcompression.hpp | 19 +++++++++++++------
trunk/boost/lockfree/queue.hpp | 22 +++++++++++-----------
trunk/boost/lockfree/stack.hpp | 4 ++--
trunk/libs/lockfree/test/tagged_ptr_test.cpp | 19 +++++++++++++++++++
6 files changed, 69 insertions(+), 29 deletions(-)
Modified: trunk/boost/lockfree/detail/freelist.hpp
==============================================================================
--- trunk/boost/lockfree/detail/freelist.hpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/boost/lockfree/detail/freelist.hpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -9,6 +9,7 @@
#ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
#define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
+#include <limits>
#include <memory>
#include <boost/array.hpp>
@@ -174,7 +175,7 @@
}
freelist_node * new_pool_ptr = old_pool->next.get_ptr();
- tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
+ tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_next_tag());
if (pool_.compare_exchange_weak(old_pool, new_pool)) {
void * ptr = old_pool.get_ptr();
@@ -196,7 +197,7 @@
}
freelist_node * new_pool_ptr = old_pool->next.get_ptr();
- tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
+ tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_next_tag());
pool_.store(new_pool, memory_order_relaxed);
void * ptr = old_pool.get_ptr();
@@ -287,6 +288,12 @@
return tag;
}
+ tag_t get_next_tag() const
+ {
+ tag_t next = (get_tag() + 1) & (std::numeric_limits<tag_t>::max)();
+ return next;
+ }
+
void set_tag(tag_t t)
{
tag = t;
@@ -528,7 +535,7 @@
T * old_node = NodeStorage::nodes() + index;
tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
- tagged_index new_pool(next_index->get_index(), old_pool.get_tag() + 1);
+ tagged_index new_pool(next_index->get_index(), old_pool.get_next_tag());
if (pool_.compare_exchange_weak(old_pool, new_pool))
return old_pool.get_index();
@@ -546,7 +553,7 @@
T * old_node = NodeStorage::nodes() + index;
tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
- tagged_index new_pool(next_index->get_index(), old_pool.get_tag() + 1);
+ tagged_index new_pool(next_index->get_index(), old_pool.get_next_tag());
pool_.store(new_pool, memory_order_relaxed);
return old_pool.get_index();
Modified: trunk/boost/lockfree/detail/tagged_ptr_dcas.hpp
==============================================================================
--- trunk/boost/lockfree/detail/tagged_ptr_dcas.hpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/boost/lockfree/detail/tagged_ptr_dcas.hpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -9,9 +9,10 @@
#ifndef BOOST_LOCKFREE_TAGGED_PTR_DCAS_HPP_INCLUDED
#define BOOST_LOCKFREE_TAGGED_PTR_DCAS_HPP_INCLUDED
-#include <boost/lockfree/detail/branch_hints.hpp>
-
#include <cstddef> /* for std::size_t */
+#include <limits>
+
+#include <boost/lockfree/detail/branch_hints.hpp>
namespace boost {
namespace lockfree {
@@ -73,12 +74,12 @@
/** pointer access */
/* @{ */
- T * get_ptr(void) const volatile
+ T * get_ptr(void) const
{
return ptr;
}
- void set_ptr(T * p) volatile
+ void set_ptr(T * p)
{
ptr = p;
}
@@ -86,12 +87,18 @@
/** tag access */
/* @{ */
- tag_t get_tag() const volatile
+ tag_t get_tag() const
{
return tag;
}
- void set_tag(tag_t t) volatile
+ tag_t get_next_tag() const
+ {
+ tag_t next = (get_tag() + 1) & (std::numeric_limits<tag_t>::max)();
+ return next;
+ }
+
+ void set_tag(tag_t t)
{
tag = t;
}
Modified: trunk/boost/lockfree/detail/tagged_ptr_ptrcompression.hpp
==============================================================================
--- trunk/boost/lockfree/detail/tagged_ptr_ptrcompression.hpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/boost/lockfree/detail/tagged_ptr_ptrcompression.hpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -9,12 +9,13 @@
#ifndef BOOST_LOCKFREE_TAGGED_PTR_PTRCOMPRESSION_HPP_INCLUDED
#define BOOST_LOCKFREE_TAGGED_PTR_PTRCOMPRESSION_HPP_INCLUDED
-#include <boost/lockfree/detail/branch_hints.hpp>
-
#include <cstddef> /* for std::size_t */
+#include <limits>
#include <boost/cstdint.hpp>
+#include <boost/lockfree/detail/branch_hints.hpp>
+
namespace boost {
namespace lockfree {
namespace detail {
@@ -110,12 +111,12 @@
/** pointer access */
/* @{ */
- T * get_ptr() const volatile
+ T * get_ptr() const
{
return extract_ptr(ptr);
}
- void set_ptr(T * p) volatile
+ void set_ptr(T * p)
{
tag_t tag = get_tag();
ptr = pack_ptr(p, tag);
@@ -124,12 +125,18 @@
/** tag access */
/* @{ */
- tag_t get_tag() const volatile
+ tag_t get_tag() const
{
return extract_tag(ptr);
}
- void set_tag(tag_t t) volatile
+ tag_t get_next_tag() const
+ {
+ tag_t next = (get_tag() + 1) & (std::numeric_limits<tag_t>::max)();
+ return next;
+ }
+
+ void set_tag(tag_t t)
{
T * p = get_ptr();
ptr = pack_ptr(p, t);
Modified: trunk/boost/lockfree/queue.hpp
==============================================================================
--- trunk/boost/lockfree/queue.hpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/boost/lockfree/queue.hpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -103,7 +103,7 @@
{
/* increment tag to avoid ABA problem */
tagged_node_handle old_next = next.load(memory_order_relaxed);
- tagged_node_handle new_next (null_handle, old_next.get_tag()+1);
+ tagged_node_handle new_next (null_handle, old_next.get_next_tag());
next.store(new_next, memory_order_release);
}
@@ -301,15 +301,15 @@
tagged_node_handle tail2 = tail_.load(memory_order_acquire);
if (likely(tail == tail2)) {
if (next_ptr == 0) {
- tagged_node_handle new_tail_next(node_handle, next.get_tag() + 1);
+ tagged_node_handle new_tail_next(node_handle, next.get_next_tag());
if ( tail_node->next.compare_exchange_weak(next, new_tail_next) ) {
- tagged_node_handle new_tail(node_handle, tail.get_tag() + 1);
+ tagged_node_handle new_tail(node_handle, tail.get_next_tag());
tail_.compare_exchange_strong(tail, new_tail);
return true;
}
}
else {
- tagged_node_handle new_tail(pool.get_handle(next_ptr), tail.get_tag() + 1);
+ tagged_node_handle new_tail(pool.get_handle(next_ptr), tail.get_next_tag());
tail_.compare_exchange_strong(tail, new_tail);
}
}
@@ -341,12 +341,12 @@
node * next_ptr = next.get_ptr();
if (next_ptr == 0) {
- tail->next.store(tagged_node_handle(n, next.get_tag() + 1), memory_order_relaxed);
- tail_.store(tagged_node_handle(n, tail.get_tag() + 1), memory_order_relaxed);
+ tail->next.store(tagged_node_handle(n, next.get_next_tag()), memory_order_relaxed);
+ tail_.store(tagged_node_handle(n, tail.get_next_tag()), memory_order_relaxed);
return true;
}
else
- tail_.store(tagged_node_handle(next_ptr, tail.get_tag() + 1), memory_order_relaxed);
+ tail_.store(tagged_node_handle(next_ptr, tail.get_next_tag()), memory_order_relaxed);
}
}
@@ -388,7 +388,7 @@
if (next_ptr == 0)
return false;
- tagged_node_handle new_tail(pool.get_handle(next), tail.get_tag() + 1);
+ tagged_node_handle new_tail(pool.get_handle(next), tail.get_next_tag());
tail_.compare_exchange_strong(tail, new_tail);
} else {
@@ -401,7 +401,7 @@
continue;
detail::copy_payload(next_ptr->data, ret);
- tagged_node_handle new_head(pool.get_handle(next), head.get_tag() + 1);
+ tagged_node_handle new_head(pool.get_handle(next), head.get_next_tag());
if (head_.compare_exchange_weak(head, new_head)) {
pool.template destruct<true>(head);
return true;
@@ -447,7 +447,7 @@
if (next_ptr == 0)
return false;
- tagged_node_handle new_tail(pool.get_handle(next), tail.get_tag() + 1);
+ tagged_node_handle new_tail(pool.get_handle(next), tail.get_next_tag());
tail_.store(new_tail);
} else {
if (next_ptr == 0)
@@ -458,7 +458,7 @@
* */
continue;
detail::copy_payload(next_ptr->data, ret);
- tagged_node_handle new_head(pool.get_handle(next), head.get_tag() + 1);
+ tagged_node_handle new_head(pool.get_handle(next), head.get_next_tag());
head_.store(new_head);
pool.template destruct<false>(head);
return true;
Modified: trunk/boost/lockfree/stack.hpp
==============================================================================
--- trunk/boost/lockfree/stack.hpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/boost/lockfree/stack.hpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -442,7 +442,7 @@
if (!old_tos_pointer)
return false;
- tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_tag() + 1);
+ tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
if (tos.compare_exchange_weak(old_tos, new_tos)) {
detail::copy_payload(old_tos_pointer->v, ret);
@@ -486,7 +486,7 @@
return false;
node * new_tos_ptr = pool.get_pointer(old_tos_pointer->next);
- tagged_node_handle new_tos(pool.get_handle(new_tos_ptr), old_tos.get_tag() + 1);
+ tagged_node_handle new_tos(pool.get_handle(new_tos_ptr), old_tos.get_next_tag());
tos.store(new_tos, memory_order_relaxed);
detail::copy_payload(old_tos_pointer->v, ret);
Modified: trunk/libs/lockfree/test/tagged_ptr_test.cpp
==============================================================================
--- trunk/libs/lockfree/test/tagged_ptr_test.cpp Mon Jun 10 07:59:52 2013 (r84722)
+++ trunk/libs/lockfree/test/tagged_ptr_test.cpp 2013-06-10 08:31:38 EDT (Mon, 10 Jun 2013) (r84723)
@@ -4,6 +4,8 @@
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
+#include <limits>
+
#include <boost/lockfree/detail/tagged_ptr.hpp>
#define BOOST_TEST_MAIN
@@ -18,6 +20,9 @@
using namespace boost::lockfree::detail;
int a(1), b(2);
+ typedef tagged_ptr<int>::tag_t tag_t;
+ const tag_t max_tag = (std::numeric_limits<tag_t>::max)();
+
{
tagged_ptr<int> i (&a, 0);
tagged_ptr<int> j (&b, 1);
@@ -36,4 +41,18 @@
BOOST_REQUIRE_EQUAL(i.get_tag(), j.get_tag());
}
+ {
+ tagged_ptr<int> i (&a, 0);
+ BOOST_REQUIRE_EQUAL(i.get_tag() + 1, i.get_next_tag());
+ }
+
+ {
+ tagged_ptr<int> j (&a, max_tag);
+ BOOST_REQUIRE_EQUAL(j.get_next_tag(), 0);
+ }
+
+ {
+ tagged_ptr<int> j (&a, max_tag - 1);
+ BOOST_REQUIRE_EQUAL(j.get_next_tag(), max_tag);
+ }
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk