diff options
Diffstat (limited to 'src/boost/libs/lockfree')
23 files changed, 2152 insertions, 0 deletions
diff --git a/src/boost/libs/lockfree/examples/Jamfile.v2 b/src/boost/libs/lockfree/examples/Jamfile.v2 new file mode 100644 index 000000000..1868a4d23 --- /dev/null +++ b/src/boost/libs/lockfree/examples/Jamfile.v2 @@ -0,0 +1,13 @@ +# (C) Copyright 2009: Tim Blechmann +# 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) + +project boost/lockfree/example + : requirements + <library>../../thread/build//boost_thread/ + <library>../../atomic/build//boost_atomic + ; + +exe queue : queue.cpp ; +exe stack : stack.cpp ; +exe spsc_queue : spsc_queue.cpp ; diff --git a/src/boost/libs/lockfree/examples/queue.cpp b/src/boost/libs/lockfree/examples/queue.cpp new file mode 100644 index 000000000..9e599dbba --- /dev/null +++ b/src/boost/libs/lockfree/examples/queue.cpp @@ -0,0 +1,69 @@ +// Copyright (C) 2009 Tim Blechmann +// +// 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) + +//[queue_example +#include <boost/thread/thread.hpp> +#include <boost/lockfree/queue.hpp> +#include <iostream> + +#include <boost/atomic.hpp> + +boost::atomic_int producer_count(0); +boost::atomic_int consumer_count(0); + +boost::lockfree::queue<int> queue(128); + +const int iterations = 10000000; +const int producer_thread_count = 4; +const int consumer_thread_count = 4; + +void producer(void) +{ + for (int i = 0; i != iterations; ++i) { + int value = ++producer_count; + while (!queue.push(value)) + ; + } +} + +boost::atomic<bool> done (false); +void consumer(void) +{ + int value; + while (!done) { + while (queue.pop(value)) + ++consumer_count; + } + + while (queue.pop(value)) + ++consumer_count; +} + +int main(int argc, char* argv[]) +{ + using namespace std; + cout << "boost::lockfree::queue is "; + if (!queue.is_lock_free()) + cout << "not "; + cout << "lockfree" << endl; + + boost::thread_group producer_threads, consumer_threads; + + for (int i = 0; i != producer_thread_count; ++i) + producer_threads.create_thread(producer); + + for (int i = 0; i != consumer_thread_count; ++i) + consumer_threads.create_thread(consumer); + + producer_threads.join_all(); + done = true; + + consumer_threads.join_all(); + + cout << "produced " << producer_count << " objects." << endl; + cout << "consumed " << consumer_count << " objects." << endl; +} +//] diff --git a/src/boost/libs/lockfree/examples/spsc_queue.cpp b/src/boost/libs/lockfree/examples/spsc_queue.cpp new file mode 100644 index 000000000..6c6adc172 --- /dev/null +++ b/src/boost/libs/lockfree/examples/spsc_queue.cpp @@ -0,0 +1,62 @@ +// Copyright (C) 2009 Tim Blechmann +// +// 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) + +//[spsc_queue_example +#include <boost/thread/thread.hpp> +#include <boost/lockfree/spsc_queue.hpp> +#include <iostream> + +#include <boost/atomic.hpp> + +int producer_count = 0; +boost::atomic_int consumer_count (0); + +boost::lockfree::spsc_queue<int, boost::lockfree::capacity<1024> > spsc_queue; + +const int iterations = 10000000; + +void producer(void) +{ + for (int i = 0; i != iterations; ++i) { + int value = ++producer_count; + while (!spsc_queue.push(value)) + ; + } +} + +boost::atomic<bool> done (false); + +void consumer(void) +{ + int value; + while (!done) { + while (spsc_queue.pop(value)) + ++consumer_count; + } + + while (spsc_queue.pop(value)) + ++consumer_count; +} + +int main(int argc, char* argv[]) +{ + using namespace std; + cout << "boost::lockfree::queue is "; + if (!spsc_queue.is_lock_free()) + cout << "not "; + cout << "lockfree" << endl; + + boost::thread producer_thread(producer); + boost::thread consumer_thread(consumer); + + producer_thread.join(); + done = true; + consumer_thread.join(); + + cout << "produced " << producer_count << " objects." << endl; + cout << "consumed " << consumer_count << " objects." << endl; +} +//] diff --git a/src/boost/libs/lockfree/examples/stack.cpp b/src/boost/libs/lockfree/examples/stack.cpp new file mode 100644 index 000000000..ba1230269 --- /dev/null +++ b/src/boost/libs/lockfree/examples/stack.cpp @@ -0,0 +1,70 @@ +// Copyright (C) 2009 Tim Blechmann +// +// 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) + +//[stack_example +#include <boost/thread/thread.hpp> +#include <boost/lockfree/stack.hpp> +#include <iostream> + +#include <boost/atomic.hpp> + +boost::atomic_int producer_count(0); +boost::atomic_int consumer_count(0); + +boost::lockfree::stack<int> stack(128); + +const int iterations = 1000000; +const int producer_thread_count = 4; +const int consumer_thread_count = 4; + +void producer(void) +{ + for (int i = 0; i != iterations; ++i) { + int value = ++producer_count; + while (!stack.push(value)) + ; + } +} + +boost::atomic<bool> done (false); + +void consumer(void) +{ + int value; + while (!done) { + while (stack.pop(value)) + ++consumer_count; + } + + while (stack.pop(value)) + ++consumer_count; +} + +int main(int argc, char* argv[]) +{ + using namespace std; + cout << "boost::lockfree::stack is "; + if (!stack.is_lock_free()) + cout << "not "; + cout << "lockfree" << endl; + + boost::thread_group producer_threads, consumer_threads; + + for (int i = 0; i != producer_thread_count; ++i) + producer_threads.create_thread(producer); + + for (int i = 0; i != consumer_thread_count; ++i) + consumer_threads.create_thread(consumer); + + producer_threads.join_all(); + done = true; + + consumer_threads.join_all(); + + cout << "produced " << producer_count << " objects." << endl; + cout << "consumed " << consumer_count << " objects." << endl; +} +//] diff --git a/src/boost/libs/lockfree/index.html b/src/boost/libs/lockfree/index.html new file mode 100644 index 000000000..ccee53f70 --- /dev/null +++ b/src/boost/libs/lockfree/index.html @@ -0,0 +1,13 @@ +<html> +<head> +<meta http-equiv="refresh" content="0; URL=../../doc/html/lockfree.html"> +</head> +<body> +Automatic redirection failed, please go to +<a href="../../doc/html/lockfree.html">../../doc/html/lockfree.html</a> <hr> +<p>© Copyright Beman Dawes, 2001</p> +<p>Distributed under the Boost Software License, Version 1.0. (See accompanying +file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy +at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p> +</body> +</html> diff --git a/src/boost/libs/lockfree/meta/libraries.json b/src/boost/libs/lockfree/meta/libraries.json new file mode 100644 index 000000000..fb65281d2 --- /dev/null +++ b/src/boost/libs/lockfree/meta/libraries.json @@ -0,0 +1,14 @@ +{ + "key": "lockfree", + "name": "Lockfree", + "authors": [ + "Tim Blechmann" + ], + "description": "Lockfree data structures.", + "category": [ + "Concurrent" + ], + "maintainers": [ + "Tim Blechmann <tim -at- klingt.org>" + ] +} diff --git a/src/boost/libs/lockfree/test/Jamfile.v2 b/src/boost/libs/lockfree/test/Jamfile.v2 new file mode 100644 index 000000000..8ce4189c3 --- /dev/null +++ b/src/boost/libs/lockfree/test/Jamfile.v2 @@ -0,0 +1,44 @@ +# (C) Copyright 2010: Tim Blechmann +# 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) + +import testing ; + +lib boost_chrono ; +lib boost_interprocess ; +lib boost_system ; +lib boost_thread ; +lib boost_unit_test_framework ; + +project + : source-location . + : requirements + <library>../../test/build//boost_unit_test_framework + <library>../../atomic/build//boost_atomic + ; + + +rule test_all +{ + local all_rules = ; + + for local fileb in [ glob *.cpp ] + { + all_rules += [ run $(fileb) + : # additional args + : # test-files + : # requirements + <toolset>acc:<linkflags>-lrt + <toolset>acc-pa_risc:<linkflags>-lrt + <target-os>windows,<toolset>gcc:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32" + <host-os>hpux,<toolset>gcc:<linkflags>"-Wl,+as,mpas" + <library>../../thread/build//boost_thread/ + <threading>multi + <link>static + ] ; + } + + return $(all_rules) ; +} + +test-suite lockfree : [ test_all r ] : <threading>multi ; diff --git a/src/boost/libs/lockfree/test/freelist_test.cpp b/src/boost/libs/lockfree/test/freelist_test.cpp new file mode 100644 index 000000000..4eb9c5c4d --- /dev/null +++ b/src/boost/libs/lockfree/test/freelist_test.cpp @@ -0,0 +1,233 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +// enables error checks via dummy::~dtor +#define BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR + +#include <boost/lockfree/detail/freelist.hpp> +#include <boost/lockfree/queue.hpp> + +#include <boost/foreach.hpp> +#include <boost/thread.hpp> +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include <set> + +#include "test_helpers.hpp" + +using boost::lockfree::detail::atomic; + +atomic<bool> test_running(false); + +struct dummy +{ + dummy(void) + { + if (test_running.load(boost::lockfree::detail::memory_order_relaxed)) + assert(allocated == 0); + allocated = 1; + } + + ~dummy(void) + { + if (test_running.load(boost::lockfree::detail::memory_order_relaxed)) + assert(allocated == 1); + allocated = 0; + } + + size_t padding[2]; // for used for the freelist node + int allocated; +}; + +template <typename freelist_type, + bool threadsafe, + bool bounded> +void run_test(void) +{ + freelist_type fl(std::allocator<int>(), 8); + + std::set<dummy*> nodes; + + dummy d; + if (bounded) + test_running.store(true); + + for (int i = 0; i != 4; ++i) { + dummy * allocated = fl.template construct<threadsafe, bounded>(); + BOOST_REQUIRE(nodes.find(allocated) == nodes.end()); + nodes.insert(allocated); + } + + BOOST_FOREACH(dummy * d, nodes) + fl.template destruct<threadsafe>(d); + + nodes.clear(); + for (int i = 0; i != 4; ++i) + nodes.insert(fl.template construct<threadsafe, bounded>()); + + BOOST_FOREACH(dummy * d, nodes) + fl.template destruct<threadsafe>(d); + + for (int i = 0; i != 4; ++i) + nodes.insert(fl.template construct<threadsafe, bounded>()); + + if (bounded) + test_running.store(false); +} + +template <bool bounded> +void run_tests(void) +{ + run_test<boost::lockfree::detail::freelist_stack<dummy>, true, bounded>(); + run_test<boost::lockfree::detail::freelist_stack<dummy>, false, bounded>(); + run_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true, bounded>(); +} + +BOOST_AUTO_TEST_CASE( freelist_tests ) +{ + run_tests<false>(); + run_tests<true>(); +} + +template <typename freelist_type, bool threadsafe> +void oom_test(void) +{ + const bool bounded = true; + freelist_type fl(std::allocator<int>(), 8); + + for (int i = 0; i != 8; ++i) + fl.template construct<threadsafe, bounded>(); + + dummy * allocated = fl.template construct<threadsafe, bounded>(); + BOOST_REQUIRE(allocated == NULL); +} + +BOOST_AUTO_TEST_CASE( oom_tests ) +{ + oom_test<boost::lockfree::detail::freelist_stack<dummy>, true >(); + oom_test<boost::lockfree::detail::freelist_stack<dummy>, false >(); + oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true >(); + oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, false >(); +} + + +template <typename freelist_type, bool bounded> +struct freelist_tester +{ + static const int size = 128; + static const int thread_count = 4; +#ifndef BOOST_LOCKFREE_STRESS_TEST + static const int operations_per_thread = 1000; +#else + static const int operations_per_thread = 100000; +#endif + + freelist_type fl; + boost::lockfree::queue<dummy*> allocated_nodes; + + atomic<bool> running; + static_hashed_set<dummy*, 1<<16 > working_set; + + + freelist_tester(void): + fl(std::allocator<int>(), size), allocated_nodes(256) + {} + + void run() + { + running = true; + + if (bounded) + test_running.store(true); + boost::thread_group alloc_threads; + boost::thread_group dealloc_threads; + + for (int i = 0; i != thread_count; ++i) + dealloc_threads.create_thread(boost::bind(&freelist_tester::deallocate, this)); + + for (int i = 0; i != thread_count; ++i) + alloc_threads.create_thread(boost::bind(&freelist_tester::allocate, this)); + alloc_threads.join_all(); + test_running.store(false); + running = false; + dealloc_threads.join_all(); + } + + void allocate(void) + { + for (long i = 0; i != operations_per_thread; ++i) { + for (;;) { + dummy * node = fl.template construct<true, bounded>(); + if (node) { + bool success = working_set.insert(node); + assert(success); + allocated_nodes.push(node); + break; + } + } + } + } + + void deallocate(void) + { + for (;;) { + dummy * node; + if (allocated_nodes.pop(node)) { + bool success = working_set.erase(node); + assert(success); + fl.template destruct<true>(node); + } + + if (running.load() == false) + break; + +#ifdef __VXWORKS__ + boost::thread::yield(); +#endif + } + + dummy * node; + while (allocated_nodes.pop(node)) { + bool success = working_set.erase(node); + assert(success); + fl.template destruct<true>(node); + } + } +}; + +template <typename Tester> +void run_tester() +{ + boost::scoped_ptr<Tester> tester (new Tester); + tester->run(); +} + + +BOOST_AUTO_TEST_CASE( unbounded_freelist_test ) +{ + typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, false > test_type; + run_tester<test_type>(); +} + + +BOOST_AUTO_TEST_CASE( bounded_freelist_test ) +{ + typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, true > test_type; + run_tester<test_type>(); +} + +BOOST_AUTO_TEST_CASE( fixed_size_freelist_test ) +{ + typedef freelist_tester<boost::lockfree::detail::fixed_size_freelist<dummy>, true > test_type; + run_tester<test_type>(); +} diff --git a/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp b/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp new file mode 100644 index 000000000..aa882ce1f --- /dev/null +++ b/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp @@ -0,0 +1,27 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/queue.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + +BOOST_AUTO_TEST_CASE( queue_test_bounded ) +{ + typedef queue_stress_tester<true> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::queue<long> q(128); + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp b/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp new file mode 100644 index 000000000..8ae46f275 --- /dev/null +++ b/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp @@ -0,0 +1,28 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/queue.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + + +BOOST_AUTO_TEST_CASE( queue_test_fixed_size ) +{ + typedef queue_stress_tester<> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::queue<long, boost::lockfree::capacity<8> > q; + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/queue_interprocess_test.cpp b/src/boost/libs/lockfree/test/queue_interprocess_test.cpp new file mode 100644 index 000000000..78c0ce9fc --- /dev/null +++ b/src/boost/libs/lockfree/test/queue_interprocess_test.cpp @@ -0,0 +1,57 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <cstdlib> //std::system +#include <sstream> + +#include <boost/interprocess/managed_shared_memory.hpp> +#include <boost/lockfree/queue.hpp> +#include <boost/thread/thread.hpp> + +using namespace boost::interprocess; +typedef allocator<int, managed_shared_memory::segment_manager> ShmemAllocator; +typedef boost::lockfree::queue<int, + boost::lockfree::allocator<ShmemAllocator>, + boost::lockfree::capacity<2048> + > queue; + +int main (int argc, char *argv[]) +{ + if(argc == 1){ + struct shm_remove + { + shm_remove() { shared_memory_object::remove("boost_queue_interprocess_test_shm"); } + ~shm_remove(){ shared_memory_object::remove("boost_queue_interprocess_test_shm"); } + } remover; + + managed_shared_memory segment(create_only, "boost_queue_interprocess_test_shm", 262144); + ShmemAllocator alloc_inst (segment.get_segment_manager()); + + queue * q = segment.construct<queue>("queue")(alloc_inst); + for (int i = 0; i != 1024; ++i) + q->push(i); + + std::string s(argv[0]); s += " child "; + if(0 != std::system(s.c_str())) + return 1; + + while (!q->empty()) + boost::thread::yield(); + return 0; + } else { + managed_shared_memory segment(open_only, "boost_queue_interprocess_test_shm"); + queue * q = segment.find<queue>("queue").first; + + int from_queue; + for (int i = 0; i != 1024; ++i) { + bool success = q->pop(from_queue); + assert (success); + assert (from_queue == i); + } + segment.destroy<queue>("queue"); + } + return 0; +} diff --git a/src/boost/libs/lockfree/test/queue_test.cpp b/src/boost/libs/lockfree/test/queue_test.cpp new file mode 100644 index 000000000..79f6f0ed2 --- /dev/null +++ b/src/boost/libs/lockfree/test/queue_test.cpp @@ -0,0 +1,194 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/lockfree_forward.hpp> + +#include <boost/lockfree/queue.hpp> +#include <boost/thread.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include <memory> + +#include "test_helpers.hpp" + +using namespace boost; +using namespace boost::lockfree; +using namespace std; + +BOOST_AUTO_TEST_CASE( simple_queue_test ) +{ + queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + + BOOST_REQUIRE(f.empty()); + f.push(1); + f.push(2); + + int i1(0), i2(0); + + BOOST_REQUIRE(f.pop(i1)); + BOOST_REQUIRE_EQUAL(i1, 1); + + BOOST_REQUIRE(f.pop(i2)); + BOOST_REQUIRE_EQUAL(i2, 2); + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( simple_queue_test_capacity ) +{ + queue<int, capacity<64> > f; + + BOOST_WARN(f.is_lock_free()); + + BOOST_REQUIRE(f.empty()); + f.push(1); + f.push(2); + + int i1(0), i2(0); + + BOOST_REQUIRE(f.pop(i1)); + BOOST_REQUIRE_EQUAL(i1, 1); + + BOOST_REQUIRE(f.pop(i2)); + BOOST_REQUIRE_EQUAL(i2, 2); + BOOST_REQUIRE(f.empty()); +} + + +BOOST_AUTO_TEST_CASE( unsafe_queue_test ) +{ + queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + int i1(0), i2(0); + + f.unsynchronized_push(1); + f.unsynchronized_push(2); + + BOOST_REQUIRE(f.unsynchronized_pop(i1)); + BOOST_REQUIRE_EQUAL(i1, 1); + + BOOST_REQUIRE(f.unsynchronized_pop(i2)); + BOOST_REQUIRE_EQUAL(i2, 2); + BOOST_REQUIRE(f.empty()); +} + + +BOOST_AUTO_TEST_CASE( queue_consume_one_test ) +{ + queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + bool success1 = f.consume_one(test_equal(1)); + bool success2 = f.consume_one(test_equal(2)); +#else + bool success1 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 1); + }); + + bool success2 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 2); + }); +#endif + + BOOST_REQUIRE(success1); + BOOST_REQUIRE(success2); + + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( queue_consume_all_test ) +{ + queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + size_t consumed = f.consume_all(dummy_functor()); +#else + size_t consumed = f.consume_all([] (int i) { + }); +#endif + + BOOST_REQUIRE_EQUAL(consumed, 2u); + + BOOST_REQUIRE(f.empty()); +} + + +BOOST_AUTO_TEST_CASE( queue_convert_pop_test ) +{ + queue<int*> f(128); + BOOST_REQUIRE(f.empty()); + f.push(new int(1)); + f.push(new int(2)); + f.push(new int(3)); + f.push(new int(4)); + + { + int * i1; + + BOOST_REQUIRE(f.pop(i1)); + BOOST_REQUIRE_EQUAL(*i1, 1); + delete i1; + } + + + { + boost::shared_ptr<int> i2; + BOOST_REQUIRE(f.pop(i2)); + BOOST_REQUIRE_EQUAL(*i2, 2); + } + + { +#ifdef BOOST_NO_AUTO_PTR + unique_ptr<int> i3; +#else + auto_ptr<int> i3; +#endif + BOOST_REQUIRE(f.pop(i3)); + + BOOST_REQUIRE_EQUAL(*i3, 3); + } + + { + boost::shared_ptr<int> i4; + BOOST_REQUIRE(f.pop(i4)); + + BOOST_REQUIRE_EQUAL(*i4, 4); + } + + + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( reserve_test ) +{ + typedef boost::lockfree::queue< void* > memory_queue; + + memory_queue ms(1); + ms.reserve(1); + ms.reserve_unsafe(1); +} diff --git a/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp b/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp new file mode 100644 index 000000000..10b70e2ba --- /dev/null +++ b/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp @@ -0,0 +1,27 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/queue.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + +BOOST_AUTO_TEST_CASE( queue_test_unbounded ) +{ + typedef queue_stress_tester<false> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::queue<long> q(128); + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp b/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp new file mode 100644 index 000000000..a63afd0e5 --- /dev/null +++ b/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp @@ -0,0 +1,222 @@ +// Copyright (C) 2011-2013 Tim Blechmann +// +// 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) + +#include <boost/lockfree/spsc_queue.hpp> +#include <boost/thread.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include <iostream> +#include <memory> + +#include "test_helpers.hpp" +#include "test_common.hpp" + +using namespace boost; +using namespace boost::lockfree; +using namespace std; + +#ifndef BOOST_LOCKFREE_STRESS_TEST +static const boost::uint32_t nodes_per_thread = 100000; +#else +static const boost::uint32_t nodes_per_thread = 100000000; +#endif + +struct spsc_queue_tester +{ + spsc_queue<int, capacity<128> > sf; + + boost::lockfree::detail::atomic<long> spsc_queue_cnt, received_nodes; + +// In VxWorks one RTP just supports 65535 objects +#ifndef __VXWORKS__ + static_hashed_set<int, 1<<16 > working_set; +#else + static_hashed_set<int, 1<<15 > working_set; +#endif + + spsc_queue_tester(void): + spsc_queue_cnt(0), received_nodes(0) + {} + + void add(void) + { + for (boost::uint32_t i = 0; i != nodes_per_thread; ++i) { + int id = generate_id<int>(); + working_set.insert(id); + + while (sf.push(id) == false) + {} + + ++spsc_queue_cnt; + } + running = false; + } + + bool get_element(void) + { + int data; + bool success = sf.pop(data); + + if (success) { + ++received_nodes; + --spsc_queue_cnt; + bool erased = working_set.erase(data); + assert(erased); + return true; + } else + return false; + } + + boost::lockfree::detail::atomic<bool> running; + + void get(void) + { + for(;;) { + bool success = get_element(); + if (!running && !success) + break; + } + + while ( get_element() ); + } + + void run(void) + { + running = true; + + BOOST_REQUIRE(sf.empty()); + + boost::thread reader(boost::bind(&spsc_queue_tester::get, this)); + boost::thread writer(boost::bind(&spsc_queue_tester::add, this)); + cout << "reader and writer threads created" << endl; + + writer.join(); + cout << "writer threads joined. waiting for readers to finish" << endl; + + reader.join(); + + BOOST_REQUIRE_EQUAL(received_nodes, nodes_per_thread); + BOOST_REQUIRE_EQUAL(spsc_queue_cnt, 0); + BOOST_REQUIRE(sf.empty()); + BOOST_REQUIRE(working_set.count_nodes() == 0); + } +}; + +BOOST_AUTO_TEST_CASE( spsc_queue_test_caching ) +{ + boost::shared_ptr<spsc_queue_tester> test1(new spsc_queue_tester); + test1->run(); +} + +struct spsc_queue_tester_buffering +{ + spsc_queue<int, capacity<128> > sf; + + boost::lockfree::detail::atomic<long> spsc_queue_cnt; + +// In VxWorks one RTP just supports 65535 objects +#ifndef __VXWORKS__ + static_hashed_set<int, 1<<16 > working_set; +#else + static_hashed_set<int, 1<<15 > working_set; +#endif + + boost::lockfree::detail::atomic<size_t> received_nodes; + + spsc_queue_tester_buffering(void): + spsc_queue_cnt(0), received_nodes(0) + {} + + static const size_t buf_size = 5; + + void add(void) + { + boost::array<int, buf_size> input_buffer; + for (boost::uint32_t i = 0; i != nodes_per_thread; i+=buf_size) { + for (size_t i = 0; i != buf_size; ++i) { + int id = generate_id<int>(); + working_set.insert(id); + input_buffer[i] = id; + } + + size_t pushed = 0; + + do { + pushed += sf.push(input_buffer.c_array() + pushed, + input_buffer.size() - pushed); + } while (pushed != buf_size); + + spsc_queue_cnt+=buf_size; + } + running = false; + } + + bool get_elements(void) + { + boost::array<int, buf_size> output_buffer; + + size_t popd = sf.pop(output_buffer.c_array(), output_buffer.size()); + + if (popd) { + received_nodes += popd; + spsc_queue_cnt -= popd; + + for (size_t i = 0; i != popd; ++i) { + bool erased = working_set.erase(output_buffer[i]); + assert(erased); + } + + return true; + } else + return false; + } + + boost::lockfree::detail::atomic<bool> running; + + void get(void) + { + for(;;) { + bool success = get_elements(); + if (!running && !success) + break; + } + + while ( get_elements() ); + } + + void run(void) + { + running = true; + + boost::thread reader(boost::bind(&spsc_queue_tester_buffering::get, this)); + boost::thread writer(boost::bind(&spsc_queue_tester_buffering::add, this)); + cout << "reader and writer threads created" << endl; + + writer.join(); + cout << "writer threads joined. waiting for readers to finish" << endl; + + reader.join(); + + BOOST_REQUIRE_EQUAL(received_nodes, nodes_per_thread); + BOOST_REQUIRE_EQUAL(spsc_queue_cnt, 0); + BOOST_REQUIRE(sf.empty()); + BOOST_REQUIRE(working_set.count_nodes() == 0); + } +}; + + +BOOST_AUTO_TEST_CASE( spsc_queue_test_buffering ) +{ + boost::shared_ptr<spsc_queue_tester_buffering> test1(new spsc_queue_tester_buffering); + test1->run(); +} + diff --git a/src/boost/libs/lockfree/test/spsc_queue_test.cpp b/src/boost/libs/lockfree/test/spsc_queue_test.cpp new file mode 100644 index 000000000..99f393f05 --- /dev/null +++ b/src/boost/libs/lockfree/test/spsc_queue_test.cpp @@ -0,0 +1,407 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/spsc_queue.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include <iostream> +#include <memory> + +#include "test_helpers.hpp" +#include "test_common.hpp" + +using namespace boost; +using namespace boost::lockfree; +using namespace std; + +BOOST_AUTO_TEST_CASE( simple_spsc_queue_test ) +{ + spsc_queue<int, capacity<64> > f; + + BOOST_REQUIRE(f.empty()); + f.push(1); + f.push(2); + + int i1(0), i2(0); + + BOOST_REQUIRE(f.pop(i1)); + BOOST_REQUIRE_EQUAL(i1, 1); + + BOOST_REQUIRE(f.pop(i2)); + BOOST_REQUIRE_EQUAL(i2, 2); + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( simple_spsc_queue_test_compile_time_size ) +{ + spsc_queue<int> f(64); + + BOOST_REQUIRE(f.empty()); + f.push(1); + f.push(2); + + int i1(0), i2(0); + + BOOST_REQUIRE(f.pop(i1)); + BOOST_REQUIRE_EQUAL(i1, 1); + + BOOST_REQUIRE(f.pop(i2)); + BOOST_REQUIRE_EQUAL(i2, 2); + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( ranged_push_test ) +{ + spsc_queue<int> stk(64); + + int data[2] = {1, 2}; + + BOOST_REQUIRE_EQUAL(stk.push(data, data + 2), data + 2); + + int out; + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(!stk.pop(out)); +} + +BOOST_AUTO_TEST_CASE( spsc_queue_consume_one_test ) +{ + spsc_queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + bool success1 = f.consume_one(test_equal(1)); + bool success2 = f.consume_one(test_equal(2)); +#else + bool success1 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 1); + }); + + bool success2 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 2); + }); +#endif + + BOOST_REQUIRE(success1); + BOOST_REQUIRE(success2); + + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( spsc_queue_consume_all_test ) +{ + spsc_queue<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + size_t consumed = f.consume_all(dummy_functor()); +#else + size_t consumed = f.consume_all([] (int i) { + }); +#endif + + BOOST_REQUIRE_EQUAL(consumed, 2u); + + BOOST_REQUIRE(f.empty()); +} + +enum { + pointer_and_size, + reference_to_array, + iterator_pair, + output_iterator_ +}; + +BOOST_AUTO_TEST_CASE( spsc_queue_capacity_test ) +{ + spsc_queue<int, capacity<2> > f; + + BOOST_REQUIRE(f.push(1)); + BOOST_REQUIRE(f.push(2)); + BOOST_REQUIRE(!f.push(3)); + + spsc_queue<int> g(2); + + BOOST_REQUIRE(g.push(1)); + BOOST_REQUIRE(g.push(2)); + BOOST_REQUIRE(!g.push(3)); +} + +template <typename QueueType> +void spsc_queue_avail_test_run(QueueType & q) +{ + BOOST_REQUIRE_EQUAL( q.write_available(), 16 ); + BOOST_REQUIRE_EQUAL( q.read_available(), 0 ); + + for (size_t i = 0; i != 8; ++i) { + BOOST_REQUIRE_EQUAL( q.write_available(), 16 - i ); + BOOST_REQUIRE_EQUAL( q.read_available(), i ); + + q.push( 1 ); + } + + // empty queue + int dummy; + while (q.pop(dummy)) + {} + + for (size_t i = 0; i != 16; ++i) { + BOOST_REQUIRE_EQUAL( q.write_available(), 16 - i ); + BOOST_REQUIRE_EQUAL( q.read_available(), i ); + + q.push( 1 ); + } +} + +BOOST_AUTO_TEST_CASE( spsc_queue_avail_test ) +{ + spsc_queue<int, capacity<16> > f; + spsc_queue_avail_test_run(f); + + spsc_queue<int> g(16); + spsc_queue_avail_test_run(g); +} + + +template <int EnqueueMode> +void spsc_queue_buffer_push_return_value(void) +{ + const size_t xqueue_size = 64; + const size_t buffer_size = 100; + spsc_queue<int, capacity<100> > rb; + + int data[xqueue_size]; + for (size_t i = 0; i != xqueue_size; ++i) + data[i] = (int)i*2; + + switch (EnqueueMode) { + case pointer_and_size: + BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), xqueue_size); + break; + + case reference_to_array: + BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size); + break; + + case iterator_pair: + BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + xqueue_size); + break; + + default: + assert(false); + } + + switch (EnqueueMode) { + case pointer_and_size: + BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), buffer_size - xqueue_size); + break; + + case reference_to_array: + BOOST_REQUIRE_EQUAL(rb.push(data), buffer_size - xqueue_size); + break; + + case iterator_pair: + BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + buffer_size - xqueue_size); + break; + + default: + assert(false); + } +} + +BOOST_AUTO_TEST_CASE( spsc_queue_buffer_push_return_value_test ) +{ + spsc_queue_buffer_push_return_value<pointer_and_size>(); + spsc_queue_buffer_push_return_value<reference_to_array>(); + spsc_queue_buffer_push_return_value<iterator_pair>(); +} + +template <int EnqueueMode, + int ElementCount, + int BufferSize, + int NumberOfIterations + > +void spsc_queue_buffer_push(void) +{ + const size_t xqueue_size = ElementCount; + spsc_queue<int, capacity<BufferSize> > rb; + + int data[xqueue_size]; + for (size_t i = 0; i != xqueue_size; ++i) + data[i] = (int)i*2; + + std::vector<int> vdata(data, data + xqueue_size); + + for (int i = 0; i != NumberOfIterations; ++i) { + BOOST_REQUIRE(rb.empty()); + switch (EnqueueMode) { + case pointer_and_size: + BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), xqueue_size); + break; + + case reference_to_array: + BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size); + break; + + case iterator_pair: + BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + xqueue_size); + break; + + default: + assert(false); + } + + int out[xqueue_size]; + BOOST_REQUIRE_EQUAL(rb.pop(out, xqueue_size), xqueue_size); + for (size_t i = 0; i != xqueue_size; ++i) + BOOST_REQUIRE_EQUAL(data[i], out[i]); + } +} + +BOOST_AUTO_TEST_CASE( spsc_queue_buffer_push_test ) +{ + spsc_queue_buffer_push<pointer_and_size, 7, 16, 64>(); + spsc_queue_buffer_push<reference_to_array, 7, 16, 64>(); + spsc_queue_buffer_push<iterator_pair, 7, 16, 64>(); +} + +template <int EnqueueMode, + int ElementCount, + int BufferSize, + int NumberOfIterations + > +void spsc_queue_buffer_pop(void) +{ + const size_t xqueue_size = ElementCount; + spsc_queue<int, capacity<BufferSize> > rb; + + int data[xqueue_size]; + for (size_t i = 0; i != xqueue_size; ++i) + data[i] = (int)i*2; + + std::vector<int> vdata(data, data + xqueue_size); + + for (int i = 0; i != NumberOfIterations; ++i) { + BOOST_REQUIRE(rb.empty()); + BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size); + + int out[xqueue_size]; + vector<int> vout; + + switch (EnqueueMode) { + case pointer_and_size: + BOOST_REQUIRE_EQUAL(rb.pop(out, xqueue_size), xqueue_size); + break; + + case reference_to_array: + BOOST_REQUIRE_EQUAL(rb.pop(out), xqueue_size); + break; + + case output_iterator_: + BOOST_REQUIRE_EQUAL(rb.pop(std::back_inserter(vout)), xqueue_size); + break; + + default: + assert(false); + } + + if (EnqueueMode == output_iterator_) { + BOOST_REQUIRE_EQUAL(vout.size(), xqueue_size); + for (size_t i = 0; i != xqueue_size; ++i) + BOOST_REQUIRE_EQUAL(data[i], vout[i]); + } else { + for (size_t i = 0; i != xqueue_size; ++i) + BOOST_REQUIRE_EQUAL(data[i], out[i]); + } + } +} + +BOOST_AUTO_TEST_CASE( spsc_queue_buffer_pop_test ) +{ + spsc_queue_buffer_pop<pointer_and_size, 7, 16, 64>(); + spsc_queue_buffer_pop<reference_to_array, 7, 16, 64>(); + spsc_queue_buffer_pop<output_iterator_, 7, 16, 64>(); +} + +// Test front() and pop() +template < typename Queue > +void spsc_queue_front_pop(Queue& queue) +{ + queue.push(1); + queue.push(2); + queue.push(3); + + // front as ref and const ref + int& rfront = queue.front(); + const int& crfront = queue.front(); + + BOOST_REQUIRE_EQUAL(1, rfront); + BOOST_REQUIRE_EQUAL(1, crfront); + + int front = 0; + + // access element pushed first + front = queue.front(); + BOOST_REQUIRE_EQUAL(1, front); + + // front is still the same + front = queue.front(); + BOOST_REQUIRE_EQUAL(1, front); + + queue.pop(); + + front = queue.front(); + BOOST_REQUIRE_EQUAL(2, front); + + queue.pop(); // pop 2 + + bool pop_ret = queue.pop(); // pop 3 + BOOST_REQUIRE(pop_ret); + + pop_ret = queue.pop(); // pop on empty queue + BOOST_REQUIRE( ! pop_ret); +} + +BOOST_AUTO_TEST_CASE( spsc_queue_buffer_front_and_pop_runtime_sized_test ) +{ + spsc_queue<int, capacity<64> > queue; + spsc_queue_front_pop(queue); +} + +BOOST_AUTO_TEST_CASE( spsc_queue_buffer_front_and_pop_compiletime_sized_test ) +{ + spsc_queue<int> queue(64); + spsc_queue_front_pop(queue); +} + +BOOST_AUTO_TEST_CASE( spsc_queue_reset_test ) +{ + spsc_queue<int, capacity<64> > f; + + BOOST_REQUIRE(f.empty()); + f.push(1); + f.push(2); + + f.reset(); + + BOOST_REQUIRE(f.empty()); +} diff --git a/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp b/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp new file mode 100644 index 000000000..55d097fba --- /dev/null +++ b/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp @@ -0,0 +1,27 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/stack.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + +BOOST_AUTO_TEST_CASE( stack_test_bounded ) +{ + typedef queue_stress_tester<true> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::stack<long> q(128); + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp b/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp new file mode 100644 index 000000000..688af3081 --- /dev/null +++ b/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp @@ -0,0 +1,28 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/stack.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + + +BOOST_AUTO_TEST_CASE( stack_test_fixed_size ) +{ + typedef queue_stress_tester<> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::stack<long, boost::lockfree::capacity<8> > q; + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/stack_interprocess_test.cpp b/src/boost/libs/lockfree/test/stack_interprocess_test.cpp new file mode 100644 index 000000000..1a60e63f4 --- /dev/null +++ b/src/boost/libs/lockfree/test/stack_interprocess_test.cpp @@ -0,0 +1,57 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <cstdlib> //std::system +#include <sstream> + +#include <boost/interprocess/managed_shared_memory.hpp> +#include <boost/lockfree/stack.hpp> +#include <boost/thread/thread.hpp> + +using namespace boost::interprocess; +typedef allocator<int, managed_shared_memory::segment_manager> ShmemAllocator; +typedef boost::lockfree::stack<int, + boost::lockfree::allocator<ShmemAllocator>, + boost::lockfree::capacity<2048> + > stack; + +int main (int argc, char *argv[]) +{ + if(argc == 1){ + struct shm_remove + { + shm_remove() { shared_memory_object::remove("MySharedMemory"); } + ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); } + } remover; + + managed_shared_memory segment(create_only, "MySharedMemory", 65536); + ShmemAllocator alloc_inst (segment.get_segment_manager()); + + stack * queue = segment.construct<stack>("stack")(alloc_inst); + for (int i = 0; i != 1024; ++i) + queue->push(i); + + std::string s(argv[0]); s += " child "; + if(0 != std::system(s.c_str())) + return 1; + + while (!queue->empty()) + boost::thread::yield(); + return 0; + } else { + managed_shared_memory segment(open_only, "MySharedMemory"); + stack * queue = segment.find<stack>("stack").first; + + int from_queue; + for (int i = 0; i != 1024; ++i) { + bool success = queue->pop(from_queue); + assert (success); + assert (from_queue == 1023 - i); + } + segment.destroy<stack>("stack"); + } + return 0; +} diff --git a/src/boost/libs/lockfree/test/stack_test.cpp b/src/boost/libs/lockfree/test/stack_test.cpp new file mode 100644 index 000000000..303222b67 --- /dev/null +++ b/src/boost/libs/lockfree/test/stack_test.cpp @@ -0,0 +1,219 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + + +#include <boost/thread.hpp> +#include <boost/lockfree/stack.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_helpers.hpp" + +BOOST_AUTO_TEST_CASE( simple_stack_test ) +{ + boost::lockfree::stack<long> stk(128); + + stk.push(1); + stk.push(2); + long out; + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.pop(out)); +} + +BOOST_AUTO_TEST_CASE( unsafe_stack_test ) +{ + boost::lockfree::stack<long> stk(128); + + stk.unsynchronized_push(1); + stk.unsynchronized_push(2); + long out; + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.unsynchronized_pop(out)); +} + +BOOST_AUTO_TEST_CASE( ranged_push_test ) +{ + boost::lockfree::stack<long> stk(128); + + long data[2] = {1, 2}; + + BOOST_REQUIRE_EQUAL(stk.push(data, data + 2), data + 2); + + long out; + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.unsynchronized_pop(out)); +} + +BOOST_AUTO_TEST_CASE( ranged_unsynchronized_push_test ) +{ + boost::lockfree::stack<long> stk(128); + + long data[2] = {1, 2}; + + BOOST_REQUIRE_EQUAL(stk.unsynchronized_push(data, data + 2), data + 2); + + long out; + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.unsynchronized_pop(out)); +} + +BOOST_AUTO_TEST_CASE( fixed_size_stack_test ) +{ + boost::lockfree::stack<long, boost::lockfree::capacity<128> > stk; + + stk.push(1); + stk.push(2); + long out; + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.pop(out)); + BOOST_REQUIRE(stk.empty()); +} + +BOOST_AUTO_TEST_CASE( fixed_size_stack_test_exhausted ) +{ + boost::lockfree::stack<long, boost::lockfree::capacity<2> > stk; + + stk.push(1); + stk.push(2); + BOOST_REQUIRE(!stk.push(3)); + long out; + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.pop(out)); + BOOST_REQUIRE(stk.empty()); +} + +BOOST_AUTO_TEST_CASE( bounded_stack_test_exhausted ) +{ + boost::lockfree::stack<long> stk(2); + + stk.bounded_push(1); + stk.bounded_push(2); + BOOST_REQUIRE(!stk.bounded_push(3)); + long out; + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2); + BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1); + BOOST_REQUIRE(!stk.pop(out)); + BOOST_REQUIRE(stk.empty()); +} + +BOOST_AUTO_TEST_CASE( stack_consume_one_test ) +{ + boost::lockfree::stack<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + bool success1 = f.consume_one(test_equal(2)); + bool success2 = f.consume_one(test_equal(1)); +#else + bool success1 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 2); + }); + + bool success2 = f.consume_one([] (int i) { + BOOST_REQUIRE_EQUAL(i, 1); + }); +#endif + + BOOST_REQUIRE(success1); + BOOST_REQUIRE(success2); + + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( stack_consume_all_test ) +{ + boost::lockfree::stack<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + +#ifdef BOOST_NO_CXX11_LAMBDAS + size_t consumed = f.consume_all(dummy_functor()); +#else + size_t consumed = f.consume_all([] (int i) { + }); +#endif + + BOOST_REQUIRE_EQUAL(consumed, 2u); + + BOOST_REQUIRE(f.empty()); +} + +BOOST_AUTO_TEST_CASE( stack_consume_all_atomic_test ) +{ + boost::lockfree::stack<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + f.push(3); + +#ifdef BOOST_NO_CXX11_LAMBDAS + size_t consumed = f.consume_all_atomic(dummy_functor()); +#else + size_t consumed = f.consume_all_atomic([] (int i) { + }); +#endif + + BOOST_REQUIRE_EQUAL(consumed, 3u); + + BOOST_REQUIRE(f.empty()); +} + + +BOOST_AUTO_TEST_CASE( stack_consume_all_atomic_reversed_test ) +{ + boost::lockfree::stack<int> f(64); + + BOOST_WARN(f.is_lock_free()); + BOOST_REQUIRE(f.empty()); + + f.push(1); + f.push(2); + f.push(3); + +#ifdef BOOST_NO_CXX11_LAMBDAS + size_t consumed = f.consume_all_atomic_reversed(dummy_functor()); +#else + size_t consumed = f.consume_all_atomic_reversed([] (int i) { + }); +#endif + + BOOST_REQUIRE_EQUAL(consumed, 3u); + + BOOST_REQUIRE(f.empty()); +} + + +BOOST_AUTO_TEST_CASE( reserve_test ) +{ + typedef boost::lockfree::stack< void* > memory_stack; + + memory_stack ms(1); + ms.reserve(1); + ms.reserve_unsafe(1); +} diff --git a/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp b/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp new file mode 100644 index 000000000..98d975173 --- /dev/null +++ b/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp @@ -0,0 +1,28 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <boost/lockfree/stack.hpp> + +#include <boost/scoped_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +#include "test_common.hpp" + + +BOOST_AUTO_TEST_CASE( stack_test_unbounded ) +{ + typedef queue_stress_tester<false> tester_type; + boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) ); + + boost::lockfree::stack<long> q(128); + tester->run(q); +} diff --git a/src/boost/libs/lockfree/test/tagged_ptr_test.cpp b/src/boost/libs/lockfree/test/tagged_ptr_test.cpp new file mode 100644 index 000000000..4ce1dd741 --- /dev/null +++ b/src/boost/libs/lockfree/test/tagged_ptr_test.cpp @@ -0,0 +1,58 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <limits> + +#include <boost/lockfree/detail/tagged_ptr.hpp> + +#define BOOST_TEST_MAIN +#ifdef BOOST_LOCKFREE_INCLUDE_TESTS +#include <boost/test/included/unit_test.hpp> +#else +#include <boost/test/unit_test.hpp> +#endif + +BOOST_AUTO_TEST_CASE( tagged_ptr_test ) +{ + 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); + + i = j; + + BOOST_REQUIRE_EQUAL(i.get_ptr(), &b); + BOOST_REQUIRE_EQUAL(i.get_tag(), 1); + } + + { + tagged_ptr<int> i (&a, 0); + tagged_ptr<int> j (i); + + BOOST_REQUIRE_EQUAL(i.get_ptr(), j.get_ptr()); + 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); + } +} diff --git a/src/boost/libs/lockfree/test/test_common.hpp b/src/boost/libs/lockfree/test/test_common.hpp new file mode 100644 index 000000000..2db41a847 --- /dev/null +++ b/src/boost/libs/lockfree/test/test_common.hpp @@ -0,0 +1,145 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#include <cassert> +#include <iostream> +#include "test_helpers.hpp" + +#include <boost/array.hpp> +#include <boost/thread.hpp> + +namespace impl { + +using boost::array; +using namespace boost; +using namespace std; + +template <bool Bounded = false> +struct queue_stress_tester +{ + static const unsigned int buckets = 1<<13; +#ifndef BOOST_LOCKFREE_STRESS_TEST + static const long node_count = 5000; +#else + static const long node_count = 500000; +#endif + const int reader_threads; + const int writer_threads; + + boost::lockfree::detail::atomic<int> writers_finished; + + static_hashed_set<long, buckets> data; + static_hashed_set<long, buckets> dequeued; + array<std::set<long>, buckets> returned; + + boost::lockfree::detail::atomic<int> push_count, pop_count; + + queue_stress_tester(int reader, int writer): + reader_threads(reader), writer_threads(writer), push_count(0), pop_count(0) + {} + + template <typename queue> + void add_items(queue & stk) + { + for (long i = 0; i != node_count; ++i) { + long id = generate_id<long>(); + + bool inserted = data.insert(id); + assert(inserted); + + if (Bounded) + while(stk.bounded_push(id) == false) { +#ifdef __VXWORKS__ + thread::yield(); +#endif + } + else + while(stk.push(id) == false) { +#ifdef __VXWORKS__ + thread::yield(); +#endif + } + ++push_count; + } + writers_finished += 1; + } + + boost::lockfree::detail::atomic<bool> running; + + template <typename queue> + bool consume_element(queue & q) + { + long id; + bool ret = q.pop(id); + + if (!ret) + return false; + + bool erased = data.erase(id); + bool inserted = dequeued.insert(id); + assert(erased); + assert(inserted); + ++pop_count; + return true; + } + + template <typename queue> + void get_items(queue & q) + { + for (;;) { + bool received_element = consume_element(q); + if (received_element) + continue; + + if ( writers_finished.load() == writer_threads ) + break; + +#ifdef __VXWORKS__ + thread::yield(); +#endif + } + + while (consume_element(q)); + } + + template <typename queue> + void run(queue & stk) + { + BOOST_WARN(stk.is_lock_free()); + writers_finished.store(0); + + thread_group writer; + thread_group reader; + + BOOST_REQUIRE(stk.empty()); + + for (int i = 0; i != reader_threads; ++i) + reader.create_thread(boost::bind(&queue_stress_tester::template get_items<queue>, this, boost::ref(stk))); + + for (int i = 0; i != writer_threads; ++i) + writer.create_thread(boost::bind(&queue_stress_tester::template add_items<queue>, this, boost::ref(stk))); + + std::cout << "threads created" << std::endl; + + writer.join_all(); + + std::cout << "writer threads joined, waiting for readers" << std::endl; + + reader.join_all(); + + std::cout << "reader threads joined" << std::endl; + + BOOST_REQUIRE_EQUAL(data.count_nodes(), (size_t)0); + BOOST_REQUIRE(stk.empty()); + + BOOST_REQUIRE_EQUAL(push_count, pop_count); + BOOST_REQUIRE_EQUAL(push_count, writer_threads * node_count); + } +}; + +} + +using impl::queue_stress_tester; diff --git a/src/boost/libs/lockfree/test/test_helpers.hpp b/src/boost/libs/lockfree/test/test_helpers.hpp new file mode 100644 index 000000000..882fa1c45 --- /dev/null +++ b/src/boost/libs/lockfree/test/test_helpers.hpp @@ -0,0 +1,110 @@ +// Copyright (C) 2011 Tim Blechmann +// +// 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) + +#ifndef BOOST_LOCKFREE_TEST_HELPERS +#define BOOST_LOCKFREE_TEST_HELPERS + +#include <set> +#include <boost/array.hpp> +#include <boost/lockfree/detail/atomic.hpp> +#include <boost/thread.hpp> + +#include <boost/cstdint.hpp> + +template <typename int_type> +int_type generate_id(void) +{ + static boost::lockfree::detail::atomic<int_type> generator(0); + return ++generator; +} + +template <typename int_type, size_t buckets> +class static_hashed_set +{ + +public: + int calc_index(int_type id) + { + // knuth hash ... does not need to be good, but has to be portable + size_t factor = size_t((float)buckets * 1.616f); + + return ((size_t)id * factor) % buckets; + } + + bool insert(int_type const & id) + { + std::size_t index = calc_index(id); + + boost::lock_guard<boost::mutex> lock (ref_mutex[index]); + + std::pair<typename std::set<int_type>::iterator, bool> p; + p = data[index].insert(id); + + return p.second; + } + + bool find (int_type const & id) + { + std::size_t index = calc_index(id); + + boost::lock_guard<boost::mutex> lock (ref_mutex[index]); + + return data[index].find(id) != data[index].end(); + } + + bool erase(int_type const & id) + { + std::size_t index = calc_index(id); + + boost::lock_guard<boost::mutex> lock (ref_mutex[index]); + + if (data[index].find(id) != data[index].end()) { + data[index].erase(id); + assert(data[index].find(id) == data[index].end()); + return true; + } + else + return false; + } + + std::size_t count_nodes(void) const + { + std::size_t ret = 0; + for (int i = 0; i != buckets; ++i) { + boost::lock_guard<boost::mutex> lock (ref_mutex[i]); + ret += data[i].size(); + } + return ret; + } + +private: + boost::array<std::set<int_type>, buckets> data; + mutable boost::array<boost::mutex, buckets> ref_mutex; +}; + +struct test_equal +{ + test_equal(int i): + i(i) + {} + + void operator()(int arg) const + { + BOOST_REQUIRE_EQUAL(arg, i); + } + + int i; +}; + +struct dummy_functor +{ + void operator()(int /* arg */) const + { + } +}; + + +#endif |