1610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov/* Copyright (c) 2008-2010, Google Inc. 2610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * All rights reserved. 3610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * 4610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * Redistribution and use in source and binary forms, with or without 5610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * modification, are permitted provided that the following conditions are 6610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * met: 7610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * 8610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * * Redistributions of source code must retain the above copyright 9610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * notice, this list of conditions and the following disclaimer. 10610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * * Neither the name of Google Inc. nor the names of its 11610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * contributors may be used to endorse or promote products derived from 12610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * this software without specific prior written permission. 13610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * 14610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov */ 26610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 27610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// This file is a part of a test suite for ThreadSanitizer, a race detector. 28610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// Author: Konstantin Serebryany. 29610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// 30610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// C++ tests for atomicity violations (aka high-level races). 31610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// See also: http://code.google.com/p/data-race-test/wiki/HighLevelDataRaces 32610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov#include "test_utils.h" 33610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 34610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov#include <gtest/gtest.h> 35610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 36610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov#include <map> 37610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 38610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovnamespace AtomicityTests_LockedVector { // {{{1 39610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// The most popular form of atomicity violation. 40610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// Every method of a class is locked, but not every method is atomic. 41610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// So, 42610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// if(v.size() > 0) 43610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// v.pop_back() 44610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// may fail, if another thread called v.pop_back() in between. 45610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovclass LockedVector { 46610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov public: 47610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov size_t size() { 48610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov MutexLock l(&mu_); 49610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov return v_.size(); 50610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 51610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 52610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov void push_back(int a) { 53610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov MutexLock l(&mu_); 54610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov v_.push_back(a); 55610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 56610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 57610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov void pop_back() { 58610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov MutexLock l(&mu_); 59610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov v_.pop_back(); 60610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 61610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 62610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov private: 63610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov vector<int> v_; 64610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov Mutex mu_; 65610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov}; 66610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 67610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovconst int N = 100; 68610969f87667a485b9207086b3ff475bab909f95Evgeniy StepanovLockedVector v; 69610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 70610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovvoid Worker() { 71610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov for (int i = 0; i < N; i++) { 72610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov if (v.size() > 0) 73610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov v.pop_back(); 74610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov v.push_back(i); 75610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov usleep(1); 76610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 77610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} 78610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 79610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// The test is disabled because it actually fails sometimes. 80610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// Run it with --gtest_also_run_disabled_tests 81610969f87667a485b9207086b3ff475bab909f95Evgeniy StepanovTEST(AtomicityTests, DISABLED_LockedVector) { 82610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov MyThreadArray t(Worker, Worker); 83610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov t.Start(); 84610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov t.Join(); 85610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} 86610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 87610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} // namespace 88610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 89610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 90610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovnamespace AtomicityTests_ReaderThenWriterLockTest { // {{{1 91610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov#ifndef _MSC_VER 92610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// Atomicity violation with a map and a reader lock. 93610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// The function CheckMapAndInsertIfNeeded first checks if an element 94610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// with a given key exists. If not, it inserts such element. 95610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// The problem here is that during the first part we hold a reader lock, 96610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// then we release it and grap writer lock, but the code has (incorrect) 97610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// assumption that the map has not been changed between ReaderUnlock and 98610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// WriterLock. 99610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 100610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovtypedef std::map<int, int> Map; 101610969f87667a485b9207086b3ff475bab909f95Evgeniy StepanovMap *m; 102610969f87667a485b9207086b3ff475bab909f95Evgeniy StepanovRWLock mu; 103610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovbool reported = false; 104610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 105610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovvoid CheckMapAndInsertIfNeeded(int key, int val) { 106610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov Map::iterator it; 107610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 108610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov { 109610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov ReaderLockScoped reader(&mu); 110610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov it = m->find(key); 111610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov if (it != m->end()) 112610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov return; 113610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 114610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov // <<<<< Another thread may change the map here. 115610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov { 116610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov WriterLockScoped writer(&mu); 117610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov // CHECK(m->find(key) == m->end()); 118610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov if (m->find(key) != m->end()) { 119610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov if (!reported) { 120610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov printf("Here comes the result of atomicity violation!\n"); 121610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov reported = true; 122610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 123610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov return; 124610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 125610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov (*m)[key] = val; 126610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 127610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} 128610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 129610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanovvoid Worker() { 130610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov for (int i = 0; i < 1000; i++) { 131610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov CheckMapAndInsertIfNeeded(i, i); 132610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov usleep(0); 133610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov } 134610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} 135610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 136610969f87667a485b9207086b3ff475bab909f95Evgeniy StepanovTEST(AtomicityTests, ReaderThenWriterLockTest) { 137610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov m = new Map(); 138610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov MyThreadArray t(Worker, Worker, Worker); 139610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov t.Start(); 140610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov t.Join(); 141610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov delete m; 142610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} 143610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov#endif // _MSC_VER 144610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov} // namespace 145610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov 146610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// End {{{1 147610969f87667a485b9207086b3ff475bab909f95Evgeniy Stepanov// vim:shiftwidth=2:softtabstop=2:expandtab:foldmethod=marker 148