Boost logo

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