1 /* Copyright (c) 2008-2010, Google Inc. 2 * All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Neither the name of Google Inc. nor the names of its 11 * contributors may be used to endorse or promote products derived from 12 * this software without specific prior written permission. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 // This file is part of ThreadSanitizer, a dynamic data race detector. 28 // Author: Konstantin Serebryany. 29 30 // This file contains tests for various parts of ThreadSanitizer. 31 32 #include <gtest/gtest.h> 33 34 #include "ts_heap_info.h" 35 #include "ts_simple_cache.h" 36 #include "dense_multimap.h" 37 38 // Testing the HeapMap. 39 struct TestHeapInfo { 40 uintptr_t ptr; 41 uintptr_t size; 42 int val; 43 TestHeapInfo() : ptr(0), size(0), val(0) { } 44 TestHeapInfo(uintptr_t p, uintptr_t s, uintptr_t v) : 45 ptr(p), size(s), val(v) { } 46 }; 47 48 TEST(ThreadSanitizer, HeapInfoTest) { 49 HeapMap<TestHeapInfo> map; 50 TestHeapInfo *info; 51 EXPECT_EQ(0U, map.size()); 52 EXPECT_EQ(NULL, map.GetInfo(12345)); 53 54 // Insert range [1000, 1000+100) with value 1. 55 map.InsertInfo(1000, TestHeapInfo(1000, 100, 1)); 56 EXPECT_EQ(1U, map.size()); 57 info = map.GetInfo(1000); 58 EXPECT_TRUE(info); 59 EXPECT_EQ(1000U, info->ptr); 60 EXPECT_EQ(100U, info->size); 61 EXPECT_EQ(1, info->val); 62 63 EXPECT_TRUE(map.GetInfo(1000)); 64 EXPECT_EQ(1, info->val); 65 EXPECT_TRUE(map.GetInfo(1050)); 66 EXPECT_EQ(1, info->val); 67 EXPECT_TRUE(map.GetInfo(1099)); 68 EXPECT_EQ(1, info->val); 69 EXPECT_FALSE(map.GetInfo(1100)); 70 EXPECT_FALSE(map.GetInfo(2000)); 71 72 EXPECT_EQ(NULL, map.GetInfo(2000)); 73 EXPECT_EQ(NULL, map.GetInfo(3000)); 74 75 // Insert range [2000, 2000+200) with value 2. 76 map.InsertInfo(2000, TestHeapInfo(2000, 200, 2)); 77 EXPECT_EQ(2U, map.size()); 78 79 info = map.GetInfo(1000); 80 EXPECT_TRUE(info); 81 EXPECT_EQ(1, info->val); 82 83 info = map.GetInfo(2000); 84 EXPECT_TRUE(info); 85 EXPECT_EQ(2, info->val); 86 87 info = map.GetInfo(1000); 88 EXPECT_TRUE(info); 89 EXPECT_EQ(1, info->val); 90 EXPECT_TRUE((info = map.GetInfo(1050))); 91 EXPECT_EQ(1, info->val); 92 EXPECT_TRUE((info = map.GetInfo(1099))); 93 EXPECT_EQ(1, info->val); 94 EXPECT_FALSE(map.GetInfo(1100)); 95 96 EXPECT_TRUE((info = map.GetInfo(2000))); 97 EXPECT_EQ(2, info->val); 98 EXPECT_TRUE((info = map.GetInfo(2199))); 99 EXPECT_EQ(2, info->val); 100 101 EXPECT_FALSE(map.GetInfo(2200)); 102 EXPECT_FALSE(map.GetInfo(3000)); 103 104 // Insert range [3000, 3000+300) with value 3. 105 map.InsertInfo(3000, TestHeapInfo(3000, 300, 3)); 106 EXPECT_EQ(3U, map.size()); 107 108 EXPECT_TRUE((info = map.GetInfo(1000))); 109 EXPECT_EQ(1, info->val); 110 111 EXPECT_TRUE((info = map.GetInfo(2000))); 112 EXPECT_EQ(2, info->val); 113 114 EXPECT_TRUE((info = map.GetInfo(3000))); 115 EXPECT_EQ(3, info->val); 116 117 EXPECT_TRUE((info = map.GetInfo(1050))); 118 EXPECT_EQ(1, info->val); 119 120 EXPECT_TRUE((info = map.GetInfo(2100))); 121 EXPECT_EQ(2, info->val); 122 123 EXPECT_TRUE((info = map.GetInfo(3200))); 124 EXPECT_EQ(3, info->val); 125 126 // Remove range [2000,2000+200) 127 map.EraseInfo(2000); 128 EXPECT_EQ(2U, map.size()); 129 130 EXPECT_TRUE((info = map.GetInfo(1050))); 131 EXPECT_EQ(1, info->val); 132 133 EXPECT_FALSE(map.GetInfo(2100)); 134 135 EXPECT_TRUE((info = map.GetInfo(3200))); 136 EXPECT_EQ(3, info->val); 137 138 } 139 140 TEST(ThreadSanitizer, PtrToBoolCacheTest) { 141 PtrToBoolCache<256> c; 142 bool val = false; 143 EXPECT_FALSE(c.Lookup(123, &val)); 144 145 c.Insert(0, false); 146 c.Insert(1, true); 147 c.Insert(2, false); 148 c.Insert(3, true); 149 150 EXPECT_TRUE(c.Lookup(0, &val)); 151 EXPECT_EQ(false, val); 152 EXPECT_TRUE(c.Lookup(1, &val)); 153 EXPECT_EQ(true, val); 154 EXPECT_TRUE(c.Lookup(2, &val)); 155 EXPECT_EQ(false, val); 156 EXPECT_TRUE(c.Lookup(3, &val)); 157 EXPECT_EQ(true, val); 158 159 EXPECT_FALSE(c.Lookup(256, &val)); 160 EXPECT_FALSE(c.Lookup(257, &val)); 161 EXPECT_FALSE(c.Lookup(258, &val)); 162 EXPECT_FALSE(c.Lookup(259, &val)); 163 164 c.Insert(0, true); 165 c.Insert(1, false); 166 167 EXPECT_TRUE(c.Lookup(0, &val)); 168 EXPECT_EQ(true, val); 169 EXPECT_TRUE(c.Lookup(1, &val)); 170 EXPECT_EQ(false, val); 171 EXPECT_TRUE(c.Lookup(2, &val)); 172 EXPECT_EQ(false, val); 173 EXPECT_TRUE(c.Lookup(3, &val)); 174 EXPECT_EQ(true, val); 175 176 c.Insert(256, false); 177 c.Insert(257, false); 178 EXPECT_FALSE(c.Lookup(0, &val)); 179 EXPECT_FALSE(c.Lookup(1, &val)); 180 EXPECT_TRUE(c.Lookup(2, &val)); 181 EXPECT_EQ(false, val); 182 EXPECT_TRUE(c.Lookup(3, &val)); 183 EXPECT_EQ(true, val); 184 EXPECT_TRUE(c.Lookup(256, &val)); 185 EXPECT_EQ(false, val); 186 EXPECT_TRUE(c.Lookup(257, &val)); 187 EXPECT_EQ(false, val); 188 } 189 190 TEST(ThreadSanitizer, IntPairToBoolCacheTest) { 191 IntPairToBoolCache<257> c; 192 bool val = false; 193 map<pair<int,int>, bool> m; 194 195 for (int i = 0; i < 1000000; i++) { 196 int a = (rand() % 1024) + 1; 197 int b = (rand() % 1024) + 1; 198 199 if (c.Lookup(a, b, &val)) { 200 EXPECT_EQ(1U, m.count(make_pair(a,b))); 201 EXPECT_EQ(val, m[make_pair(a,b)]); 202 } 203 204 val = (rand() % 2) == 1; 205 c.Insert(a, b, val); 206 m[make_pair(a,b)] = val; 207 } 208 } 209 210 TEST(ThreadSanitizer, DenseMultimapTest) { 211 typedef DenseMultimap<int, 3> Map; 212 213 Map m1(1, 2); 214 EXPECT_EQ(m1[0], 1); 215 EXPECT_EQ(m1[1], 2); 216 EXPECT_EQ(m1.size(), 2U); 217 218 Map m2(3, 2); 219 EXPECT_EQ(m2[0], 2); 220 EXPECT_EQ(m2[1], 3); 221 EXPECT_EQ(m2.size(), 2U); 222 223 Map m3(m1, 0); 224 EXPECT_EQ(m3.size(), 3U); 225 EXPECT_EQ(m3[0], 0); 226 EXPECT_EQ(m3[1], 1); 227 EXPECT_EQ(m3[2], 2); 228 229 Map m4(m3, 1); 230 EXPECT_EQ(m4.size(), 4U); 231 EXPECT_EQ(m4[0], 0); 232 EXPECT_EQ(m4[1], 1); 233 EXPECT_EQ(m4[2], 1); 234 EXPECT_EQ(m4[3], 2); 235 236 Map m5(m4, 5); 237 Map m6(m5, -2); 238 Map m7(m6, 2); 239 EXPECT_EQ(m7.size(), 7U); 240 241 EXPECT_TRUE(m7.has(-2)); 242 EXPECT_TRUE(m7.has(0)); 243 EXPECT_TRUE(m7.has(1)); 244 EXPECT_TRUE(m7.has(2)); 245 EXPECT_TRUE(m7.has(5)); 246 EXPECT_FALSE(m7.has(3)); 247 EXPECT_FALSE(m7.has(-1)); 248 EXPECT_FALSE(m7.has(4)); 249 250 Map m8(m7, Map::REMOVE, 1); 251 EXPECT_EQ(m8.size(), 6U); 252 EXPECT_TRUE(m8.has(1)); 253 254 Map m9(m8, Map::REMOVE, 1); 255 EXPECT_EQ(m9.size(), 5U); 256 EXPECT_FALSE(m9.has(1)); 257 } 258 259 TEST(ThreadSanitizer, NormalizeFunctionNameNotChangingTest) { 260 const char *samples[] = { 261 // These functions should not be changed by NormalizeFunctionName(): 262 // C functions 263 "main", 264 "pthread_mutex_unlock", 265 "pthread_create@@GLIBC_2.2.5", 266 "pthread_create@*" 267 268 // Valgrind can give us this, we should keep it. 269 "(below main)", 270 271 // C++ operators 272 "operator new[]", 273 "operator delete[]", 274 275 // PIN on Windows handles non-templated C++ code well 276 "my_namespace::ClassName::Method", 277 "PositiveTests_HarmfulRaceInDtor::A::~A", 278 "PositiveTests_HarmfulRaceInDtor::B::`scalar deleting destructor'", 279 280 // Objective-C on Mac 281 "+[NSNavFBENode _virtualNodeOfType:]", 282 "-[NSObject(NSObject) autorelease]", 283 "-[NSObject(NSKeyValueCoding) setValue:forKeyPath:]", 284 "-[NSCell(NSPrivate_CellMouseTracking) _setMouseTrackingInRect:ofView:]", 285 // TODO(glider): other interesting cases from Objective-C? 286 // Should we "s/:.*\]/\]/" ? 287 }; 288 289 for (size_t i = 0; i < sizeof(samples) / sizeof(samples[0]); i += 2) { 290 EXPECT_STREQ(samples[i], NormalizeFunctionName(samples[i]).c_str()); 291 } 292 } 293 294 TEST(ThreadSanitizer, NormalizeFunctionNameChangingTest) { 295 const char *samples[] = { 296 // These functions should be changed by removing <.*> and (.*) while 297 // correctly handling the "function returns a [template] function pointer" 298 // case. 299 // This is a list of (full demangled name, short name) pairs. 300 "SuppressionTests::Foo(int*)", "SuppressionTests::Foo", 301 "logging::LogMessage::Init(char const*, int)", "logging::LogMessage::Init", 302 "void DispatchToMethod<net::SpdySession, void (net::SpdySession::*)(int), int>(net::SpdySession*, void (net::SpdySession::*)(int), Tuple1<int> const&)", 303 "DispatchToMethod", 304 "MessageLoop::DeferOrRunPendingTask(MessageLoop::PendingTask const&)", 305 "MessageLoop::DeferOrRunPendingTask", 306 "spdy::SpdyFramer::ProcessInput(char const*, unsigned long)", 307 "spdy::SpdyFramer::ProcessInput", 308 "base::RefCountedThreadSafe<history::HistoryBackend, base::DefaultRefCountedThreadSafeTraits<history::HistoryBackend> >::Release() const", 309 "base::RefCountedThreadSafe::Release", 310 "net::X509Certificate::Verify(std::string const&, int, net::CertVerifyResult*) const", 311 "net::X509Certificate::Verify", 312 313 "(anonymous namespace)::ExtentToStringSet(ExtensionExtent const&, std::set<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::basic_string<char, std::char_traits<char>, std::allocator<char> > > >*)", 314 "::ExtentToStringSet", 315 316 "scoped_ptr<(anonymous namespace)::ImportEndedObserver>::operator->() const", 317 "scoped_ptr::operator->", 318 319 "int (anonymous namespace)::ValueCompare<long>(long, long)", 320 "::ValueCompare", 321 322 "std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > const& std::__median<std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> >, (anonymous namespace)::CompareQuality>(std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > const&, std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > const&, std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > const&, (anonymous namespace)::CompareQuality)", 323 "std::__median", 324 325 "std::basic_ostream<char, std::char_traits<char> >& std::operator<< <char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, std::_Setprecision)", 326 "std::operator<<", 327 328 "net::(anonymous namespace)::CookieSignature::operator<(net::(anonymous namespace)::CookieSignature const&) const", 329 "net::::CookieSignature::operator<", 330 331 "v8::Handle<v8::Value> (*v8::ToCData<v8::Handle<v8::Value> (*)(v8::Arguments const&)>(v8::internal::Object*))(v8::Arguments const&)", 332 "v8::ToCData", 333 334 "v8::internal::Handle<v8::internal::Object> v8::FromCData<v8::Handle<v8::Value> (*)(v8::Local<v8::String>, v8::AccessorInfo const&)>(v8::Handle<v8::Value> (*)(v8::Local<v8::String>, v8::AccessorInfo const&))", 335 "v8::FromCData", 336 337 "WebCore::operator<<(WebCore::TextStream&, WebCore::LineCap)", 338 "WebCore::operator<<", 339 340 "__gnu_cxx::__normal_iterator<void (**)(), std::vector<void (*)(), std::allocator<void (*)()> > >::base() const", 341 "__gnu_cxx::__normal_iterator::base", 342 343 "__gnu_cxx::__normal_iterator<device_orientation::DataFetcher* (* const*)(), std::vector<device_orientation::DataFetcher* (*)(), std::allocator<device_orientation::DataFetcher* (*)()> > >::operator++()", 344 "__gnu_cxx::__normal_iterator::operator++", 345 346 "__gnu_cxx::__normal_iterator<std::pair<int, std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > >*, std::vector<std::pair<int, std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > >, std::allocator<std::pair<int, std::basic_string<unsigned short, base::string16_char_traits, std::allocator<unsigned short> > > > > >::operator->() const", 347 "__gnu_cxx::__normal_iterator::operator->", 348 349 "std::less<CancelableRequestConsumerTSimple<PageUsageData*>::PendingRequest>::operator()(CancelableRequestConsumerTSimple<PageUsageData*>::PendingRequest const&, CancelableRequestConsumerTSimple<PageUsageData*>::PendingRequest const&) const", 350 "std::less::operator()", 351 352 "SuppressionTests::MyClass<int>::Fooz(int*) const", 353 "SuppressionTests::MyClass::Fooz", 354 355 // Templates and functions returning function pointers 356 "void (*SuppressionTests::TemplateFunction1<void (*)(int*)>(void (*)(int*)))(int*)", 357 "SuppressionTests::TemplateFunction1", // Valgrind, Linux 358 "void SuppressionTests::TemplateFunction2<void>()", 359 "SuppressionTests::TemplateFunction2", // OMG, return type in template 360 "void (**&SuppressionTests::TemplateFunction3<void (*)(int)>())", 361 "SuppressionTests::TemplateFunction3", // Valgrind, Linux 362 363 "SuppressionTests::TemplateFunction1<void (__cdecl*)(int *)>", 364 "SuppressionTests::TemplateFunction1", // PIN, Windows 365 "SuppressionTests::MyClass<int>::Fooz", 366 "SuppressionTests::MyClass::Fooz", 367 "std::operator<<char,std::char_traits<char>,std::allocator<char> >", 368 "(malformed frame)", // Should be "std::operator<"? Really? 369 "std::_Ranit<stdext::_Hash<stdext::_Hmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,int,stdext::hash_compare<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,int> >,0> >::_List_position,int,stdext::_Hash<stdext::_Hmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,int,stdext::hash_compare<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,int> >,0> >::_List_position const *,stdext::_Hash<stdext::_Hmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,int,stdext::hash_compare<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,int> >,0> >::_List_position const &>::_Ranit<stdext::_Hash<stdext::_Hmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,int,stdext::hash_compare<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,int> >,0> >::_List_position,int,stdext::_Hash<stdext::_Hmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,int,stdext::hash_compare<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >,std::allocator<std::pair<std::basic", 370 "(malformed frame)", 371 "std::_Tree_val<std::_Tmap_traits<net::`anonymous namespace'::CookieSignature,std::set<std::_Tree<std::_Tmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,net::CookieMonster::CanonicalCookie *,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,net::CookieMonster::CanonicalCookie *> >,1> >::iterator,net::`anonymous namespace'::OrderByCreationTimeDesc,std::allocator<std::_Tree<std::_Tmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,net::CookieMonster::CanonicalCookie *,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,net::CookieMonster::CanonicalCookie *> >,1> >::iterator> >,std::less<net::`anonymous namespace'::CookieSignature>,std::allocator<std::pair<net::`anonymous namespace'::CookieSignature const ,std::set<std::_Tree<std::_Tmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,net::CookieMonster::CanonicalCookie *,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,net::CookieMonster::CanonicalCookie *> >,1> >::iterator,net::`anonymous namespace'::OrderByCreationTimeDesc,std::allocator<std::_Tree<std::_Tmap_traits<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,net::CookieMonster::CanonicalCookie *,std::less<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,std::allocator<std::pair<std::basic_string<char,std::char_traits<char>,std::allocator<char> > const ,net::CookieMonster::CanonicalCookie *> >,1> >::iterator> > > >,0> >::~_Tree_val<std::_Tmap_traits<net::`anonymous namespace'::CookieSignature,std::set<std::_Tree<std::_Tmap_traits<std::basic_string<", 372 "(malformed frame)", 373 374 "__gnu_cxx::new_allocator<char>::allocate(unsigned long, void const*)", 375 "__gnu_cxx::new_allocator::allocate", 376 377 "PositiveTests_HarmfulRaceInDtor::A::~A()", // Valgrind, Linux 378 "PositiveTests_HarmfulRaceInDtor::A::~A", 379 380 "X::foo(int*) const()", // GCC, Linux 381 "X::foo", 382 "X::foo(int*) const volatile", 383 "X::foo", 384 385 "base::(anonymous namespace)::ThreadFunc(void*)", 386 "base::::ThreadFunc", // TODO(timurrrr): keep "anonymous namespace"? 387 388 "operator new[](unsigned long)", "operator new[]", // Valgrind, Linux 389 }; 390 391 for (size_t i = 0; i < sizeof(samples) / sizeof(samples[0]); i += 2) { 392 EXPECT_STREQ(samples[i+1], NormalizeFunctionName(samples[i]).c_str()); 393 } 394 } 395 396 int main(int argc, char **argv) { 397 testing::InitGoogleTest(&argc, argv); 398 return RUN_ALL_TESTS(); 399 } 400
