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 | |
28 | using boost::lockfree::detail::atomic; |
29 | |
30 | atomic<bool> test_running(false); |
31 | |
32 | struct 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 | |
52 | template <typename freelist_type, |
53 | bool threadsafe, |
54 | bool bounded> |
55 | void 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 | |
88 | template <bool bounded> |
89 | void 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 | |
96 | BOOST_AUTO_TEST_CASE( freelist_tests ) |
97 | { |
98 | run_tests<false>(); |
99 | run_tests<true>(); |
100 | } |
101 | |
102 | template <typename freelist_type, bool threadsafe> |
103 | void 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 | |
115 | BOOST_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 | |
124 | template <typename freelist_type, bool bounded> |
125 | struct 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 | |
208 | template <typename Tester> |
209 | void run_tester() |
210 | { |
211 | boost::scoped_ptr<Tester> tester (new Tester); |
212 | tester->run(); |
213 | } |
214 | |
215 | |
216 | BOOST_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 | |
223 | BOOST_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 | |
229 | BOOST_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 | |