test_freelist.cpp
Go to the documentation of this file.
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2010, Willow Garage, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Willow Garage nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 #include <gtest/gtest.h>
36 
37 //#define FREE_LIST_DEBUG 1
38 #include "lockfree/free_list.h"
39 
40 #include <boost/thread.hpp>
41 
42 #include <set>
43 #include "ros/time.h"
44 
45 using namespace lockfree;
46 
47 TEST(FreeList, oneElement)
48 {
49  FreeList pool(4, 1);
50  pool.constructAll<uint32_t>(5);
51 
52  uint32_t* item = static_cast<uint32_t*>(pool.allocate());
53  ASSERT_TRUE(item);
54  EXPECT_EQ(*item, 5UL);
55  *item = 6;
56  ASSERT_FALSE(pool.allocate());
57  pool.free(item);
58  item = static_cast<uint32_t*>(pool.allocate());
59  ASSERT_TRUE(item);
60  EXPECT_EQ(*item, 6UL);
61 }
62 
63 TEST(FreeList, multipleElements)
64 {
65  const uint32_t count = 5;
66  FreeList pool(4, count);
67  pool.constructAll<uint32_t>(5);
68 
69  std::vector<uint32_t*> items;
70  items.reserve(count);
71 
72  for (uint32_t i = 0; i < count; ++i)
73  {
74  items.push_back(static_cast<uint32_t*>(pool.allocate()));
75  ASSERT_TRUE(items[i]);
76  EXPECT_EQ(*items[i], 5UL);
77  *items[i] = i;
78  }
79 
80  ASSERT_FALSE(pool.allocate());
81  pool.free(items.back());
82  items.pop_back();
83  items.push_back(static_cast<uint32_t*>(pool.allocate()));
84  ASSERT_TRUE(items.back());
85  ASSERT_FALSE(pool.allocate());
86 
87  std::set<uint32_t*> set;
88  set.insert(items.begin(), items.end());
89  EXPECT_EQ(set.size(), count);
90 }
91 
92 #if FREE_LIST_DEBUG
93 boost::mutex g_debug_mutex;
94 std::vector<FreeList::Debug> g_debug;
95 
96 std::ostream& operator<<(std::ostream& o, const FreeList::Debug::Item& i)
97 {
98  o.width(20);
99  o << (i.success ? 1 : 0);
100  o << " ";
101  o << i.time;
102  o << ": ";
103  o << ((i.op == FreeList::Debug::Alloc) ? std::string("alloc") : std::string("free "));
104  o << std::string(" head: ");
105  o << std::hex;
106  o << i.head;
107  o << std::string(" new_head: ");
108  o << i.new_head;
109  o << " addr:" << (uint32_t*)i.addr;
110  return o;
111 }
112 #endif
113 
115 {
117  : start(ros::WallTime::now())
118  {}
119 
120  double elapsed() { return (ros::WallTime::now() - start).toSec(); }
121  void reset() { start = ros::WallTime::now(); }
122 
124 };
125 
126 void threadFunc(FreeList& pool, ros::atomic<bool>& done, ros::atomic<bool>& failed, boost::barrier& b)
127 {
128  b.wait();
129 
130  //ROS_INFO_STREAM("Thread " << boost::this_thread::get_id() << " starting");
131 
132  uint32_t* vals[10];
133  uint64_t alloc_count = 0;
134  while (!done.load())
135  {
136  for (uint32_t i = 0; i < 10; ++i)
137  {
138  vals[i] = static_cast<uint32_t*>(pool.allocate());
139 
140  if (vals[i])
141  {
142  ++alloc_count;
143  *vals[i] = i;
144  }
145  else
146  {
147  ROS_ERROR_STREAM("Thread " << boost::this_thread::get_id() << " failed to allocate");
148  }
149  }
150 
151  for (uint32_t i = 0; i < 10; ++i)
152  {
153  if (vals[i])
154  {
155  if (*vals[i] != i)
156  {
157  ROS_ERROR_STREAM("Thread " << boost::this_thread::get_id() << " val " << vals[i] << " " << i << " = " << *vals[i]);
158  failed.store(true);
159  }
160 
161  pool.free(vals[i]);
162  }
163  }
164 
165  if (failed.load())
166  {
167 #if FREE_LIST_DEBUG
168  boost::mutex::scoped_lock lock(g_debug_mutex);
169  g_debug.push_back(*pool.getDebug());
170 #endif
171  return;
172  }
173  }
174 
175  //ROS_INFO_STREAM("Thread " << boost::this_thread::get_id() << " allocated " << alloc_count << " blocks");
176 }
177 
178 TEST(FreeList, multipleThreads)
179 {
180  const uint32_t thread_count = boost::thread::hardware_concurrency() * 2;
181  FreeList pool(4, thread_count * 10);
182  ros::atomic<bool> done(false);
183  ros::atomic<bool> failed(false);
184  boost::thread_group tg;
185  boost::barrier bar(thread_count);
186  for (uint32_t i = 0; i < thread_count; ++i)
187  {
188  tg.create_thread(boost::bind(threadFunc, boost::ref(pool), boost::ref(done), boost::ref(failed), boost::ref(bar)));
189  }
190 
192  while (ros::WallTime::now() - start < ros::WallDuration(10.0))
193  {
194  ros::WallDuration(0.01).sleep();
195 
196  if (failed.load())
197  {
198  break;
199  }
200  }
201  done.store(true);
202  tg.join_all();
203 
204 #if FREE_LIST_DEBUG
205  if (failed.load())
206  {
207  std::vector<std::vector<FreeList::Debug::Item>::iterator> its;
208  its.resize(g_debug.size());
209  for (size_t i = 0; i < its.size(); ++i)
210  {
211  int32_t start = std::max((int32_t)g_debug[i].items.size() - 10000, 0);
212  ROS_INFO_STREAM(start << " " << g_debug[i].items.size());
213  its[i] = g_debug[i].items.begin() + start;
214  }
215  while (true)
216  {
217  size_t ind = 999999;
218  ros::WallTime time(0xffffffff, 0);
219  for (size_t j = 0; j < its.size(); ++j)
220  {
221  if (its[j] != g_debug[j].items.end() && its[j]->time < time)
222  {
223  ind = j;
224  time = its[j]->time;
225  }
226  }
227 
228  if (ind == 999999)
229  {
230  break;
231  }
232 
233  ROS_ERROR_STREAM("[" << std::setw(20) << g_debug[ind].thread << "] " << *its[ind]);
234  ++its[ind];
235  }
236  }
237 #endif
238 
239  ASSERT_TRUE(!failed.load());
240 }
241 
242 TEST(FreeList, hasOutstandingAllocations)
243 {
244  const uint32_t count = 5;
245  FreeList pool(4, count);
246 
247  std::vector<uint32_t*> items;
248  items.reserve(count);
249 
250  ASSERT_TRUE(pool.hasOutstandingAllocations());
251 
252  for (uint32_t i = 0; i < count; ++i)
253  {
254  items.push_back(static_cast<uint32_t*>(pool.allocate()));
255  ASSERT_FALSE(pool.hasOutstandingAllocations());
256  }
257 
258  for (uint32_t i = 0; i < count; ++i)
259  {
260  ASSERT_FALSE(pool.hasOutstandingAllocations());
261  pool.free(items[i]);
262  }
263 
264  ASSERT_TRUE(pool.hasOutstandingAllocations());
265 }
266 
267 int main(int argc, char** argv)
268 {
269  testing::InitGoogleTest(&argc, argv);
270  return RUN_ALL_TESTS();
271 }
272 
ros::WallTime start
void free(void const *mem)
Free a block of memory allocated from this FreeList.
Definition: free_list.cpp:170
double elapsed()
void * allocate()
Allocate a single block from this FreeList.
Definition: free_list.cpp:108
TEST(FreeList, oneElement)
bool sleep() const
void threadFunc(FreeList &pool, ros::atomic< bool > &done, ros::atomic< bool > &failed, boost::barrier &b)
bool hasOutstandingAllocations()
Returns whether or not this FreeList currently has any outstanding allocations.
Definition: free_list.cpp:103
#define ROS_INFO_STREAM(args)
static WallTime now()
#define ROS_ERROR_STREAM(args)
A lock-free (not wait-free) statically-sized free-list implemented with CAS.
Definition: free_list.h:67
void constructAll(const T &tmpl)
Construct all the blocks with a specific template. If you call this you must call destructAll() prior...
Definition: free_list.h:121
int main(int argc, char **argv)


lockfree
Author(s): Josh Faust
autogenerated on Mon Jun 10 2019 14:44:44