1// Copyright (C) 2011 Tim Blechmann
2//
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// enables error checks via dummy::~dtor
8#define BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
9
10#include <boost/lockfree/detail/freelist.hpp>
11#include <boost/lockfree/queue.hpp>
12
13#include <boost/foreach.hpp>
14#include <boost/thread.hpp>
15#include <boost/scoped_ptr.hpp>
16
17#define BOOST_TEST_MAIN
18#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
19#include <boost/test/included/unit_test.hpp>
20#else
21#include <boost/test/unit_test.hpp>
22#endif
23
24#include <set>
25
26#include "test_helpers.hpp"
27
28using boost::lockfree::detail::atomic;
29
30atomic<bool> test_running(false);
31
32struct dummy
33{
34 dummy(void)
35 {
36 if (test_running.load(m: boost::lockfree::detail::memory_order_relaxed))
37 assert(allocated == 0);
38 allocated = 1;
39 }
40
41 ~dummy(void)
42 {
43 if (test_running.load(m: boost::lockfree::detail::memory_order_relaxed))
44 assert(allocated == 1);
45 allocated = 0;
46 }
47
48 size_t padding[2]; // for used for the freelist node
49 int allocated;
50};
51
52template <typename freelist_type,
53 bool threadsafe,
54 bool bounded>
55void run_test(void)
56{
57 freelist_type fl(std::allocator<int>(), 8);
58
59 std::set<dummy*> nodes;
60
61 dummy d;
62 if (bounded)
63 test_running.store(i: true);
64
65 for (int i = 0; i != 4; ++i) {
66 dummy * allocated = fl.template construct<threadsafe, bounded>();
67 BOOST_REQUIRE(nodes.find(allocated) == nodes.end());
68 nodes.insert(x: allocated);
69 }
70
71 BOOST_FOREACH(dummy * d, nodes)
72 fl.template destruct<threadsafe>(d);
73
74 nodes.clear();
75 for (int i = 0; i != 4; ++i)
76 nodes.insert(fl.template construct<threadsafe, bounded>());
77
78 BOOST_FOREACH(dummy * d, nodes)
79 fl.template destruct<threadsafe>(d);
80
81 for (int i = 0; i != 4; ++i)
82 nodes.insert(fl.template construct<threadsafe, bounded>());
83
84 if (bounded)
85 test_running.store(i: false);
86}
87
88template <bool bounded>
89void run_tests(void)
90{
91 run_test<boost::lockfree::detail::freelist_stack<dummy>, true, bounded>();
92 run_test<boost::lockfree::detail::freelist_stack<dummy>, false, bounded>();
93 run_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true, bounded>();
94}
95
96BOOST_AUTO_TEST_CASE( freelist_tests )
97{
98 run_tests<false>();
99 run_tests<true>();
100}
101
102template <typename freelist_type, bool threadsafe>
103void oom_test(void)
104{
105 const bool bounded = true;
106 freelist_type fl(std::allocator<int>(), 8);
107
108 for (int i = 0; i != 8; ++i)
109 fl.template construct<threadsafe, bounded>();
110
111 dummy * allocated = fl.template construct<threadsafe, bounded>();
112 BOOST_REQUIRE(allocated == NULL);
113}
114
115BOOST_AUTO_TEST_CASE( oom_tests )
116{
117 oom_test<boost::lockfree::detail::freelist_stack<dummy>, true >();
118 oom_test<boost::lockfree::detail::freelist_stack<dummy>, false >();
119 oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true >();
120 oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, false >();
121}
122
123
124template <typename freelist_type, bool bounded>
125struct freelist_tester
126{
127 static const int size = 128;
128 static const int thread_count = 4;
129#ifndef BOOST_LOCKFREE_STRESS_TEST
130 static const int operations_per_thread = 1000;
131#else
132 static const int operations_per_thread = 100000;
133#endif
134
135 freelist_type fl;
136 boost::lockfree::queue<dummy*> allocated_nodes;
137
138 atomic<bool> running;
139 static_hashed_set<dummy*, 1<<16 > working_set;
140
141
142 freelist_tester(void):
143 fl(std::allocator<int>(), size), allocated_nodes(256)
144 {}
145
146 void run()
147 {
148 running = true;
149
150 if (bounded)
151 test_running.store(i: true);
152 boost::thread_group alloc_threads;
153 boost::thread_group dealloc_threads;
154
155 for (int i = 0; i != thread_count; ++i)
156 dealloc_threads.create_thread(boost::bind(&freelist_tester::deallocate, this));
157
158 for (int i = 0; i != thread_count; ++i)
159 alloc_threads.create_thread(boost::bind(&freelist_tester::allocate, this));
160 alloc_threads.join_all();
161 test_running.store(i: false);
162 running = false;
163 dealloc_threads.join_all();
164 }
165
166 void allocate(void)
167 {
168 for (long i = 0; i != operations_per_thread; ++i) {
169 for (;;) {
170 dummy * node = fl.template construct<true, bounded>();
171 if (node) {
172 bool success = working_set.insert(id: node);
173 assert(success);
174 allocated_nodes.push(t: node);
175 break;
176 }
177 }
178 }
179 }
180
181 void deallocate(void)
182 {
183 for (;;) {
184 dummy * node;
185 if (allocated_nodes.pop(ret&: node)) {
186 bool success = working_set.erase(id: node);
187 assert(success);
188 fl.template destruct<true>(node);
189 }
190
191 if (running.load() == false)
192 break;
193
194#ifdef __VXWORKS__
195 boost::thread::yield();
196#endif
197 }
198
199 dummy * node;
200 while (allocated_nodes.pop(ret&: node)) {
201 bool success = working_set.erase(id: node);
202 assert(success);
203 fl.template destruct<true>(node);
204 }
205 }
206};
207
208template <typename Tester>
209void run_tester()
210{
211 boost::scoped_ptr<Tester> tester (new Tester);
212 tester->run();
213}
214
215
216BOOST_AUTO_TEST_CASE( unbounded_freelist_test )
217{
218 typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, false > test_type;
219 run_tester<test_type>();
220}
221
222
223BOOST_AUTO_TEST_CASE( bounded_freelist_test )
224{
225 typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, true > test_type;
226 run_tester<test_type>();
227}
228
229BOOST_AUTO_TEST_CASE( fixed_size_freelist_test )
230{
231 typedef freelist_tester<boost::lockfree::detail::fixed_size_freelist<dummy>, true > test_type;
232 run_tester<test_type>();
233}
234

source code of boost/libs/lockfree/test/freelist_test.cpp