language/duchain

duchainlock.cpp

00001 /* This file is part of KDevelop
00002     Copyright 2007 Kris Wong <kris.p.wong@gmail.com>
00003     Copyright 2007 Hamish Rodda <rodda@kde.org>
00004    Copyright 2007 David Nolden <david.nolden.kdevelop@art-master.de>
00005 
00006    This library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Library General Public
00008    License version 2 as published by the Free Software Foundation.
00009 
00010    This library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Library General Public License for more details.
00014 
00015    You should have received a copy of the GNU Library General Public License
00016    along with this library; see the file COPYING.LIB.  If not, write to
00017    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018    Boston, MA 02110-1301, USA.
00019 */
00020 
00021 #include "duchainlock.h"
00022 
00023 
00024 #include <unistd.h>
00025 #include <QtCore/QThread>
00026 #include <QtCore/QMutex>
00027 #include <QtCore/QWaitCondition>
00028 #include <QtCore/QHash>
00029 #include <QtCore/QStack>
00030 #include <QTime>
00031 #include <util/google/dense_hash_map>
00032 
00033 
00034 // Uncomment the following to turn on verbose locking information
00035 //#define DUCHAIN_LOCK_VERBOSE_OUTPUT
00036 
00037 // Uncomment this to enable checking for long lock times. It adds significant performance cost though.
00038 //#define DEBUG_LOG_TIMING
00039 
00040 // When uncommented, a backtrace will be printed whenever a too long lock-time is discovered
00041 //#define DEBUG_LOG_BACKTRACE
00042 
00043 //If DEBUG_LOG_TIMING is uncommented, and the duchain is locked for more than this count of milliseconds, a message is printed
00044 #define LOCK_LOG_MILLISECONDS 1000
00045 
00046 //If this is uncommented, backtraces are produced whenever the duchain is read-locked, and shows it when the same thread tries to get a write-lock, triggering an assertion.
00047 //Very expensive!
00048 //#define DEBUG_ASSERTION_BACKTRACES
00049 
00050 //Uncomment this to search for Deadlocks. DEBUG_LOG_TIMING must be enabled too, and DEBUG_LOG_BACKTRACE is recommended
00051 //Warning: this may result in a total spamming of the command-line.
00052 //#define SEARCH_DEADLOCKS
00053 
00054 #include <kdebug.h>
00055 #include <sys/time.h>
00056 
00057 namespace std {
00058 #if defined(Q_CC_MSVC)
00059   using namespace stdext;
00060 #else
00061   using namespace __gnu_cxx;
00062 #endif
00063 }
00064 
00065 #ifndef Q_CC_MSVC
00066 namespace __gnu_cxx {
00067     template<>
00068     struct hash<void *>
00069     {
00070         inline size_t operator() (const void *ptr) const { return reinterpret_cast<size_t>(ptr); }
00071     };
00072 }
00073 #endif
00074 
00075 namespace KDevelop
00076 {
00077 class DUChainLockPrivate
00078 {
00079 public:
00080   DUChainLockPrivate() {
00081     m_writer = 0;
00082     m_writerRecursion = 0;
00083     m_totalReaderRecursion = 0;
00084     m_readers.set_empty_key(0); //Assuming that no thread can ever have handle zero
00085     m_readersEnd = m_readers.end(); //This is used to speedup currentThreadHasReadLock()
00086   }
00087 
00091   bool haveOtherReaders() const {
00093     return m_totalReaderRecursion != ownReaderRecursion();
00094   }
00095 
00096   int ownReaderRecursion() const {
00097     int ownReaderRecursion = 0;
00098 
00099     ReaderMap::const_iterator it = m_readers.find( QThread::currentThreadId() );
00100     if( it != m_readersEnd )
00101       ownReaderRecursion = (*it).second;
00102     return ownReaderRecursion;
00103   }
00104 
00105 #ifdef DEBUG_LOG_TIMING
00106   inline void auditTime() const {
00107     int ms = m_lockTime.elapsed();
00108     if (ms > LOCK_LOG_MILLISECONDS) {
00109 #ifndef DEBUG_LOG_BACKTRACE
00110       kWarning(9512) << "Long lock time:" << ms << "milliseconds." ;
00111 #else
00112       kWarning(9512) << "Long lock time:" << ms << "milliseconds, locked from:\n" << m_lockBacktrace ;
00113 #endif
00114     }
00115   }
00116   inline void startLockTiming() {
00117     m_lockTime.start();
00118 #ifdef DEBUG_LOG_BACKTRACE
00119     m_lockBacktrace = kBacktrace();
00120 #endif
00121   }
00122 #endif
00123 
00124   QMutex m_mutex;
00125   Qt::HANDLE m_writer;
00126 
00127   int m_writerRecursion; 
00128   int m_totalReaderRecursion; 
00129 
00130   QWaitCondition m_waitForWriter;
00131 
00133   typedef google::dense_hash_map<Qt::HANDLE, int> ReaderMap;
00134   ReaderMap m_readers;
00135   DUChainLockPrivate::ReaderMap::const_iterator m_readersEnd; //Must always be updated when a new reader was added
00136 
00137 #ifdef DEBUG_LOG_TIMING
00138   QTime m_lockTime;
00139 #ifdef DEBUG_LOG_BACKTRACE
00140   QString m_lockBacktrace;
00141 #endif
00142 #endif
00143   
00144 #ifdef DEBUG_ASSERTION_BACKTRACES
00145   QHash<Qt::HANDLE, QStack<QString> > m_readerBacktraces;
00146 #endif
00147 };
00148 
00149 class DUChainWriteLockerPrivate
00150 {
00151 public:
00152   DUChainWriteLockerPrivate() : m_locked(false) {
00153   }
00154   DUChainLock* m_lock;
00155   bool m_locked;
00156   int m_timeout;
00157 };
00158 
00159 
00160 DUChainLock::DUChainLock()
00161   : d(new DUChainLockPrivate)
00162 {
00163 }
00164 
00165 DUChainLock::~DUChainLock()
00166 {
00167   delete d;
00168 }
00169 
00170 inline uint toMilliSeconds(timeval v) {
00171   return v.tv_sec * 1000 + v.tv_usec / 1000;
00172 }
00173 
00174 bool DUChainLock::lockForRead(unsigned int timeout)
00175 {
00176 #ifdef DUCHAIN_LOCK_VERBOSE_OUTPUT
00177   kDebug(9505) << "DUChain read lock requested by thread:" << QThread::currentThreadId();
00178 #endif
00179   if(timeout == 0)
00180     timeout = 60000;
00181 
00182   d->m_mutex.lock();
00183 
00184   bool locked = false;
00185 
00186   timeval startTime;
00187   gettimeofday(&startTime, 0);
00188   
00189   while((d->m_writer && d->m_writer != QThread::currentThreadId())) {
00190     timeval currentTime;
00191     gettimeofday(&currentTime, 0);
00192     timeval waited;
00193     timersub(&currentTime, &startTime, &waited);
00194     
00195     if(toMilliSeconds(waited) < timeout)
00196       d->m_waitForWriter.wait(&d->m_mutex, timeout);
00197     else
00198       break;
00199   }
00200   
00201   if (d->m_writer == 0 || d->m_writer == QThread::currentThreadId()) {
00202     DUChainLockPrivate::ReaderMap::iterator it = d->m_readers.find( QThread::currentThreadId() );
00203     if ( it != d->m_readers.end() ) {
00204       ++(*it).second;
00205     } else {
00206       d->m_readers.insert( DUChainLockPrivate::ReaderMap::value_type(QThread::currentThreadId(), 1) );
00207       d->m_readersEnd = d->m_readers.end();
00208     }
00209     locked = true;
00210   }
00211 
00212   if(locked) {
00213     ++d->m_totalReaderRecursion;
00214 #ifdef DEBUG_LOCK_TIMING
00215     d->startLockTiming();
00216 #endif
00217     
00218 #ifdef DEBUG_ASSERTION_BACKTRACES
00219     d->m_readerBacktraces[QThread::currentThreadId()].push(kBacktrace());
00220     Q_ASSERT(d->m_readerBacktraces[QThread::currentThreadId()].size() == d->m_readers[QThread::currentThreadId()]);
00221 #endif
00222   }
00223 
00224   d->m_mutex.unlock();
00225   return locked;
00226 }
00227 
00228 bool DUChainLock::lockForRead() {
00229   bool ret = lockForRead(100000);
00230   Q_ASSERT(currentThreadHasReadLock());
00231   return ret;
00232 }
00233 
00234 void DUChainLock::releaseReadLock()
00235 {
00236 #ifdef DUCHAIN_LOCK_VERBOSE_OUTPUT
00237   kDebug(9505) << "DUChain read lock released by thread:" << QThread::currentThreadId();
00238 #endif
00239 
00240   QMutexLocker lock(&d->m_mutex);
00241   DUChainLockPrivate::ReaderMap::iterator it = d->m_readers.find( QThread::currentThreadId() );
00242   Q_ASSERT(it != d->m_readers.end());
00243   --(*it).second;
00244   Q_ASSERT((*it).second>=0);
00245   --d->m_totalReaderRecursion;
00246 
00249 
00250 /*  if( *it == 0 )
00251     d->m_readers.erase(it); //Maybe it would even be wise simply leaving it there*/
00252 
00253 #ifdef DEBUG_ASSERTION_BACKTRACES
00254   d->m_readerBacktraces[QThread::currentThreadId()].pop();
00255 #endif
00256 
00257 #ifdef DEBUG_LOCK_TIMING
00258   d->auditTime();
00259 #endif
00260 }
00261 
00262 bool DUChainLock::currentThreadHasReadLock()
00263 {
00264   d->m_mutex.lock();
00265   
00266   DUChainLockPrivate::ReaderMap::const_iterator it = d->m_readers.find( QThread::currentThreadId() );
00267   bool ret = false;
00268   if( it != d->m_readersEnd )
00269     ret = ((*it).second != 0);
00270 
00271   d->m_mutex.unlock();
00272   return ret;
00273 }
00274 
00275 bool DUChainLock::lockForWrite(uint timeout)
00276 {
00277 #ifdef DUCHAIN_LOCK_VERBOSE_OUTPUT
00278   kDebug(9505) << "DUChain write lock requested by thread:" << QThread::currentThreadId();
00279   kDebug(9505) << "Current backtrace:" << kBacktrace();
00280 #endif
00281 
00282   if(timeout == 0)
00283     timeout = 10000;
00284   
00285   QMutexLocker lock(&d->m_mutex);
00286   //It is not allowed to acquire a write-lock while holding read-lock
00287 
00288 #ifdef DEBUG_ASSERTION_BACKTRACES
00289   if(d->ownReaderRecursion())
00290     kWarning(9505) << "Tried to lock the duchain for writing, but it was already locked for reading here:\n" << d->m_readerBacktraces[QThread::currentThreadId()].top();
00291 #endif
00292 
00293   Q_ASSERT(d->ownReaderRecursion() == 0);
00294 
00295   bool locked = false;
00296   uint currentTime = 0;
00297 
00298   //We cannot use m_waitForWriterForWriter here, because we also have to wait for other readers to finish
00299   while ( ( (d->m_writer && d->m_writer != QThread::currentThreadId()) || d->haveOtherReaders()) && currentTime < timeout) {
00300     lock.unlock();
00301     usleep(10000);
00302     currentTime++;
00303     lock.relock();
00304 #ifdef DEBUG_LOG_BACKTRACE
00305     d->auditTime(); //Search for deadlocks
00306 #endif
00307   }
00308 
00309   if ( (d->m_writer == 0 || d->m_writer == QThread::currentThreadId()) && !d->haveOtherReaders()) {
00310     d->m_writer = QThread::currentThreadId();
00311     ++d->m_writerRecursion;
00312     locked = true;
00313 #ifdef DEBUG_LOCK_TIMING
00314     d->startLockTiming();
00315 #endif
00316   }
00317 
00318   return locked;
00319 }
00320 
00321 void DUChainLock::releaseWriteLock()
00322 {
00323 #ifdef DUCHAIN_LOCK_VERBOSE_OUTPUT
00324   kDebug(9505) << "DUChain write lock released by thread:" << QThread::currentThreadId();
00325 #endif
00326 
00327   Q_ASSERT(currentThreadHasWriteLock());
00328   QMutexLocker lock(&d->m_mutex);
00329   
00330   --d->m_writerRecursion;
00331   
00332   if( !d->m_writerRecursion )
00333     d->m_writer = 0;
00334 
00335   d->m_waitForWriter.wakeAll();
00336 #ifdef DEBUG_LOCK_TIMING
00337   d->auditTime();
00338 #endif
00339 }
00340 
00341 bool DUChainLock::currentThreadHasWriteLock()
00342 {
00343   d->m_mutex.lock();
00344   bool ret = d->m_writer == QThread::currentThreadId();
00345   d->m_mutex.unlock();
00346   return ret;
00347 }
00348 
00349 
00350 DUChainReadLocker::DUChainReadLocker(DUChainLock* duChainLock, uint timeout) : m_locked(false), m_timeout(timeout)
00351 {
00352   m_lock = duChainLock;
00353   m_timeout = timeout;
00354   lock();
00355 }
00356 
00357 DUChainReadLocker::~DUChainReadLocker()
00358 {
00359   unlock();
00360 }
00361 
00362 bool DUChainReadLocker::locked() const {
00363   return m_locked;
00364 }
00365 
00366 bool DUChainReadLocker::lock()
00367 {
00368   if( m_locked )
00369     return true;
00370   
00371   bool l = false;
00372   if (m_lock) {
00373     l = m_lock->lockForRead(m_timeout);
00374     Q_ASSERT(m_timeout || l);
00375   };
00376 
00377   m_locked = l;
00378   
00379   return l;
00380 }
00381 
00382 void DUChainReadLocker::unlock()
00383 {
00384   if (m_locked && m_lock) {
00385     m_lock->releaseReadLock();
00386     m_locked = false;
00387   }
00388 }
00389 
00390 
00391 DUChainWriteLocker::DUChainWriteLocker(DUChainLock* duChainLock, uint timeout)
00392   : d(new DUChainWriteLockerPrivate)
00393 {
00394   d->m_timeout = timeout;
00395   d->m_lock = duChainLock;
00396   lock();
00397 }
00398 DUChainWriteLocker::~DUChainWriteLocker()
00399 {
00400   unlock();
00401   delete d;
00402 }
00403 
00404 bool DUChainWriteLocker::lock()
00405 {
00406   if( d->m_locked )
00407     return true;
00408   
00409   bool l = false;
00410   if (d->m_lock) {
00411     l = d->m_lock->lockForWrite(d->m_timeout);
00412     Q_ASSERT(d->m_timeout || l);
00413   };
00414 
00415   d->m_locked = l;
00416   
00417   return l;
00418 }
00419 
00420 bool DUChainWriteLocker::locked() const {
00421   return d->m_locked;
00422 }
00423 
00424 void DUChainWriteLocker::unlock()
00425 {
00426   if (d->m_locked && d->m_lock) {
00427     d->m_lock->releaseWriteLock();
00428     d->m_locked = false;
00429   }
00430 }
00431 }
00432 
00433 
00434 // kate: space-indent on; indent-width 2; tab-width 4; replace-tabs on; auto-insert-doxygen on
language/duchain

duchainlock.cpp

language/duchain

KDevelop Platform Libraries
