00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #include <gtest/gtest.h>
00036
00037
00038 #include "lockfree/free_list.h"
00039
00040 #include <boost/thread.hpp>
00041
00042 #include <set>
00043 #include "ros/time.h"
00044
00045 using namespace lockfree;
00046
00047 TEST(FreeList, oneElement)
00048 {
00049 FreeList pool(4, 1);
00050 pool.constructAll<uint32_t>(5);
00051
00052 uint32_t* item = static_cast<uint32_t*>(pool.allocate());
00053 ASSERT_TRUE(item);
00054 EXPECT_EQ(*item, 5UL);
00055 *item = 6;
00056 ASSERT_FALSE(pool.allocate());
00057 pool.free(item);
00058 item = static_cast<uint32_t*>(pool.allocate());
00059 ASSERT_TRUE(item);
00060 EXPECT_EQ(*item, 6UL);
00061 }
00062
00063 TEST(FreeList, multipleElements)
00064 {
00065 const uint32_t count = 5;
00066 FreeList pool(4, count);
00067 pool.constructAll<uint32_t>(5);
00068
00069 std::vector<uint32_t*> items;
00070 items.reserve(count);
00071
00072 for (uint32_t i = 0; i < count; ++i)
00073 {
00074 items.push_back(static_cast<uint32_t*>(pool.allocate()));
00075 ASSERT_TRUE(items[i]);
00076 EXPECT_EQ(*items[i], 5UL);
00077 *items[i] = i;
00078 }
00079
00080 ASSERT_FALSE(pool.allocate());
00081 pool.free(items.back());
00082 items.pop_back();
00083 items.push_back(static_cast<uint32_t*>(pool.allocate()));
00084 ASSERT_TRUE(items.back());
00085 ASSERT_FALSE(pool.allocate());
00086
00087 std::set<uint32_t*> set;
00088 set.insert(items.begin(), items.end());
00089 EXPECT_EQ(set.size(), count);
00090 }
00091
00092 #if FREE_LIST_DEBUG
00093 boost::mutex g_debug_mutex;
00094 std::vector<FreeList::Debug> g_debug;
00095
00096 std::ostream& operator<<(std::ostream& o, const FreeList::Debug::Item& i)
00097 {
00098 o.width(20);
00099 o << (i.success ? 1 : 0);
00100 o << " ";
00101 o << i.time;
00102 o << ": ";
00103 o << ((i.op == FreeList::Debug::Alloc) ? std::string("alloc") : std::string("free "));
00104 o << std::string(" head: ");
00105 o << std::hex;
00106 o << i.head;
00107 o << std::string(" new_head: ");
00108 o << i.new_head;
00109 o << " addr:" << (uint32_t*)i.addr;
00110 return o;
00111 }
00112 #endif
00113
00114 struct PerfCounter
00115 {
00116 PerfCounter()
00117 : start(ros::WallTime::now())
00118 {}
00119
00120 double elapsed() { return (ros::WallTime::now() - start).toSec(); }
00121 void reset() { start = ros::WallTime::now(); }
00122
00123 ros::WallTime start;
00124 };
00125
00126 void threadFunc(FreeList& pool, ros::atomic<bool>& done, ros::atomic<bool>& failed, boost::barrier& b)
00127 {
00128 b.wait();
00129
00130
00131
00132 uint32_t* vals[10];
00133 uint64_t alloc_count = 0;
00134 while (!done.load())
00135 {
00136 for (uint32_t i = 0; i < 10; ++i)
00137 {
00138 vals[i] = static_cast<uint32_t*>(pool.allocate());
00139
00140 if (vals[i])
00141 {
00142 ++alloc_count;
00143 *vals[i] = i;
00144 }
00145 else
00146 {
00147 ROS_ERROR_STREAM("Thread " << boost::this_thread::get_id() << " failed to allocate");
00148 }
00149 }
00150
00151 for (uint32_t i = 0; i < 10; ++i)
00152 {
00153 if (vals[i])
00154 {
00155 if (*vals[i] != i)
00156 {
00157 ROS_ERROR_STREAM("Thread " << boost::this_thread::get_id() << " val " << vals[i] << " " << i << " = " << *vals[i]);
00158 failed.store(true);
00159 }
00160
00161 pool.free(vals[i]);
00162 }
00163 }
00164
00165 if (failed.load())
00166 {
00167 #if FREE_LIST_DEBUG
00168 boost::mutex::scoped_lock lock(g_debug_mutex);
00169 g_debug.push_back(*pool.getDebug());
00170 #endif
00171 return;
00172 }
00173 }
00174
00175
00176 }
00177
00178 TEST(FreeList, multipleThreads)
00179 {
00180 const uint32_t thread_count = boost::thread::hardware_concurrency() * 2;
00181 FreeList pool(4, thread_count * 10);
00182 ros::atomic<bool> done(false);
00183 ros::atomic<bool> failed(false);
00184 boost::thread_group tg;
00185 boost::barrier bar(thread_count);
00186 for (uint32_t i = 0; i < thread_count; ++i)
00187 {
00188 tg.create_thread(boost::bind(threadFunc, boost::ref(pool), boost::ref(done), boost::ref(failed), boost::ref(bar)));
00189 }
00190
00191 ros::WallTime start = ros::WallTime::now();
00192 while (ros::WallTime::now() - start < ros::WallDuration(10.0))
00193 {
00194 ros::WallDuration(0.01).sleep();
00195
00196 if (failed.load())
00197 {
00198 break;
00199 }
00200 }
00201 done.store(true);
00202 tg.join_all();
00203
00204 #if FREE_LIST_DEBUG
00205 if (failed.load())
00206 {
00207 std::vector<std::vector<FreeList::Debug::Item>::iterator> its;
00208 its.resize(g_debug.size());
00209 for (size_t i = 0; i < its.size(); ++i)
00210 {
00211 int32_t start = std::max((int32_t)g_debug[i].items.size() - 10000, 0);
00212 ROS_INFO_STREAM(start << " " << g_debug[i].items.size());
00213 its[i] = g_debug[i].items.begin() + start;
00214 }
00215 while (true)
00216 {
00217 size_t ind = 999999;
00218 ros::WallTime time(0xffffffff, 0);
00219 for (size_t j = 0; j < its.size(); ++j)
00220 {
00221 if (its[j] != g_debug[j].items.end() && its[j]->time < time)
00222 {
00223 ind = j;
00224 time = its[j]->time;
00225 }
00226 }
00227
00228 if (ind == 999999)
00229 {
00230 break;
00231 }
00232
00233 ROS_ERROR_STREAM("[" << std::setw(20) << g_debug[ind].thread << "] " << *its[ind]);
00234 ++its[ind];
00235 }
00236 }
00237 #endif
00238
00239 ASSERT_TRUE(!failed.load());
00240 }
00241
00242 TEST(FreeList, hasOutstandingAllocations)
00243 {
00244 const uint32_t count = 5;
00245 FreeList pool(4, count);
00246
00247 std::vector<uint32_t*> items;
00248 items.reserve(count);
00249
00250 ASSERT_TRUE(pool.hasOutstandingAllocations());
00251
00252 for (uint32_t i = 0; i < count; ++i)
00253 {
00254 items.push_back(static_cast<uint32_t*>(pool.allocate()));
00255 ASSERT_FALSE(pool.hasOutstandingAllocations());
00256 }
00257
00258 for (uint32_t i = 0; i < count; ++i)
00259 {
00260 ASSERT_FALSE(pool.hasOutstandingAllocations());
00261 pool.free(items[i]);
00262 }
00263
00264 ASSERT_TRUE(pool.hasOutstandingAllocations());
00265 }
00266
00267 int main(int argc, char** argv)
00268 {
00269 testing::InitGoogleTest(&argc, argv);
00270 return RUN_ALL_TESTS();
00271 }
00272