src/Utils/ReaderWriterLock.cpp

   1 /*********************************************************************
   2 CReaderWriterLock: A simple and fast reader-writer lock class in C++
   3 has characters of .NET ReaderWriterLock class
   4 Copyright (C) 2006 Quynh Nguyen Huu
   5
   6 This library is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Lesser General Public
   8 License as published by the Free Software Foundation; either
   9 version 2.1 of the License, or (at your option) any later version.
  10
  11 This library is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Lesser General Public License for more details.
  15
  16 Email questions, comments or suggestions to quynhnguyenhuu@gmail.com
  17 *********************************************************************/
  18
  19 #include "stdafx.h"
  20 #include <crtdbg.h>
  21 #include "ReaderWriterLock.h"
  22
  23 /////////////////////////////////////////////////////////////////
  24 // Following macros make this file can be used in non-MFC project
  25 #ifndef ASSERT
  26 // Define ASSERT macro
  27 #   define ASSERT _ASSERT
  28
  29 // Define VERIFY macro
  30 #   ifdef _DEBUG
  31 #       define VERIFY ASSERT
  32 #       define DEBUG_ONLY(f) ((void)(f))
  33 #   else
  34 #       define VERIFY(f) ((void)(f))
  35 #       define DEBUG_ONLY(f)
  36 #   endif
  37 #endif
  38
  39 ///////////////////////////////////////////////////////
  40 // CReaderWriterLockNonReentrance implementation
  41
  42 CReaderWriterLockNonReentrance::CReaderWriterLockNonReentrance()
  43     : m_hSafeToReadEvent(NULL)
  44     , m_hSafeToWriteEvent(NULL)
  45     , m_iNumOfWriter(0)
  46     , m_iNumOfReaderWaiting(0)
  47     , m_iNumOfReaderEntered(0)
  48 {
  49     SecureZeroMemory(this, sizeof(*this));
  50 #if (_WIN32_WINNT >= 0x0403)
  51     InitializeCriticalSectionAndSpinCount(&m_cs, READER_WRITER_SPIN_COUNT);
  52 #else
  53     InitializeCriticalSection(&m_cs);
  54 #endif
  55 }
  56
  57 CReaderWriterLockNonReentrance::~CReaderWriterLockNonReentrance()
  58 {
  59     _ASSERT( (NULL == m_hSafeToReadEvent) &&
  60         (NULL == m_hSafeToWriteEvent) );
  61     DeleteCriticalSection(&m_cs);
  62 }
  63
  64 bool CReaderWriterLockNonReentrance::_ReaderWait(DWORD dwTimeout) throw()
  65 {
  66     bool blCanRead;
  67
  68     ++m_iNumOfReaderWaiting;
  69     if(NULL == m_hSafeToReadEvent)
  70     {
  71         m_hSafeToReadEvent = CreateEvent(NULL, TRUE, FALSE, NULL);
  72     }
  73
  74     if(INFINITE == dwTimeout) // INFINITE is a special value
  75     {
  76         do
  77         {
  78             LeaveCS();
  79             WaitForSingleObject(m_hSafeToReadEvent, INFINITE);
  80             // There might be one or more Writers entered, that's
  81             // why we need DO-WHILE loop here
  82             EnterCS();
  83         }
  84         while(0 != m_iNumOfWriter);
  85
  86         ++m_iNumOfReaderEntered;
  87         blCanRead = TRUE;
  88     }
  89     else
  90     {
  91         LeaveCS();
  92
  93         DWORD const dwBeginTime = GetTickCount();
  94         DWORD dwConsumedTime = 0;
  95
  96         while(TRUE)
  97         {
  98             blCanRead = (WAIT_OBJECT_0 == WaitForSingleObject(m_hSafeToReadEvent,
  99                 dwTimeout - dwConsumedTime));
 100
 101             EnterCS();
 102
 103             if(0 == m_iNumOfWriter)
 104             {
 105                 // Regardless timeout or not, there is no Writer
 106                 // So it's safe to be Reader right now
 107                 ++m_iNumOfReaderEntered;
 108                 blCanRead = TRUE;
 109                 break;
 110             }
 111
 112             if(FALSE == blCanRead)
 113             {
 114                 // Timeout after waiting
 115                 break;
 116             }
 117
 118             // There are some Writers have just entered
 119             // So leave CS and prepare to try again
 120             LeaveCS();
 121
 122             dwConsumedTime = GetTickCount() - dwBeginTime;
 123             if(dwConsumedTime > dwTimeout)
 124             {
 125                 // Don't worry why the code here looks stupid
 126                 // Because this case rarely happens, it's better
 127                 //  to optimize code for the usual case
 128                 blCanRead = FALSE;
 129                 EnterCS();
 130                 break;
 131             }
 132         }
 133     }
 134
 135     if(0==--m_iNumOfReaderWaiting)
 136     {
 137         CloseHandle(m_hSafeToReadEvent);
 138         m_hSafeToReadEvent = NULL;
 139     }
 140
 141     return blCanRead;
 142 }
 143
 144 void CReaderWriterLockNonReentrance::_ReaderRelease()
 145 {
 146     INT _iNumOfReaderEntered = --m_iNumOfReaderEntered;
 147     _ASSERT(0 <= _iNumOfReaderEntered);
 148
 149     if( (0 == _iNumOfReaderEntered) &&
 150         (NULL != m_hSafeToWriteEvent) )
 151     {
 152         SetEvent(m_hSafeToWriteEvent);
 153     }
 154 }
 155
 156 bool CReaderWriterLockNonReentrance::_WriterWaitAndLeaveCSIfSuccess(DWORD dwTimeout)
 157 {
 158     //EnterCS();
 159     _ASSERT(0 != dwTimeout);
 160
 161     // Increase Writer-counter & reset Reader-event if necessary
 162     INT _iNumOfWriter = ++m_iNumOfWriter;
 163     if( (1 == _iNumOfWriter) && (NULL != m_hSafeToReadEvent) )
 164     {
 165         ResetEvent(m_hSafeToReadEvent);
 166     }
 167
 168     if(NULL == m_hSafeToWriteEvent)
 169     {
 170         m_hSafeToWriteEvent = CreateEvent(NULL, FALSE, FALSE, NULL);
 171     }
 172     LeaveCS();
 173
 174     bool blCanWrite = (WAIT_OBJECT_0 == WaitForSingleObject(m_hSafeToWriteEvent, dwTimeout));
 175     if(FALSE == blCanWrite)
 176     {
 177         // Undo what we changed after timeout
 178         EnterCS();
 179         if(0 == --m_iNumOfWriter)
 180         {
 181             CloseHandle(m_hSafeToWriteEvent);
 182             m_hSafeToWriteEvent = NULL;
 183
 184             if(0 == m_iNumOfReaderEntered)
 185             {
 186                 // Although it was timeout, it's still safe to be writer now
 187                 ++m_iNumOfWriter;
 188                 LeaveCS();
 189                 blCanWrite = TRUE;
 190             }
 191             else if(m_hSafeToReadEvent)
 192             {
 193                 SetEvent(m_hSafeToReadEvent);
 194             }
 195         }
 196     }
 197     return blCanWrite;
 198 }
 199
 200 bool CReaderWriterLockNonReentrance::_UpgradeToWriterLockAndLeaveCS(DWORD dwTimeout) throw()
 201 {
 202     _ASSERT(m_iNumOfReaderEntered > 0);
 203
 204     if(0 == dwTimeout)
 205     {
 206         LeaveCS();
 207         return FALSE;
 208     }
 209
 210     --m_iNumOfReaderEntered;
 211     bool blCanWrite = _WriterWaitAndLeaveCSIfSuccess(dwTimeout);
 212     if(FALSE == blCanWrite)
 213     {
 214         // Now analyze why it was failed to have suitable action
 215         if(0 == m_iNumOfWriter)
 216         {
 217             _ASSERT(0 < m_iNumOfReaderEntered);
 218             // There are some readers still owning the lock
 219             // It's safe to be a reader again after failure
 220             ++m_iNumOfReaderEntered;
 221         }
 222         else
 223         {
 224             // Reach to here, it's NOT safe to be a reader immediately
 225             _ReaderWait(INFINITE);
 226             if(1 == m_iNumOfReaderEntered)
 227             {
 228                 // After wait, now it's safe to be writer
 229                 _ASSERT(0 == m_iNumOfWriter);
 230                 m_iNumOfReaderEntered = 0;
 231                 m_iNumOfWriter = 1;
 232                 blCanWrite = TRUE;
 233             }
 234         }
 235         LeaveCS();
 236     }
 237
 238     return blCanWrite;
 239 }
 240
 241 void CReaderWriterLockNonReentrance::_WriterRelease(bool blDowngrade)
 242 {
 243     _ASSERT(0 == m_iNumOfReaderEntered);
 244
 245     if(blDowngrade)
 246     {
 247         ++m_iNumOfReaderEntered;
 248     }
 249
 250     if(0 == --m_iNumOfWriter)
 251     {
 252         if(NULL != m_hSafeToWriteEvent)
 253         {
 254             CloseHandle(m_hSafeToWriteEvent);
 255             m_hSafeToWriteEvent = NULL;
 256         }
 257
 258         if(m_hSafeToReadEvent)
 259         {
 260             SetEvent(m_hSafeToReadEvent);
 261         }
 262     }
 263     else
 264     {
 265         //////////////////////////////////////////////////////////////////////////
 266         // Some WRITERs are queued
 267         _ASSERT( (0 < m_iNumOfWriter) && (NULL != m_hSafeToWriteEvent));
 268
 269         if(FALSE == blDowngrade)
 270         {
 271             SetEvent(m_hSafeToWriteEvent);
 272         }
 273     }
 274 }
 275
 276 bool CReaderWriterLockNonReentrance::AcquireReaderLock(DWORD dwTimeout)
 277 {
 278     bool blCanRead;
 279
 280     EnterCS();
 281     if(0 == m_iNumOfWriter)
 282     {
 283         // Enter successful without wait
 284         ++m_iNumOfReaderEntered;
 285         blCanRead = TRUE;
 286     }
 287     else
 288     {
 289         blCanRead = (dwTimeout)? _ReaderWait(dwTimeout) : FALSE;
 290     }
 291     LeaveCS();
 292
 293     return blCanRead;
 294 }
 295
 296 void CReaderWriterLockNonReentrance::ReleaseReaderLock()
 297 {
 298     EnterCS();
 299     _ReaderRelease();
 300     LeaveCS();
 301 }
 302
 303 bool CReaderWriterLockNonReentrance::AcquireWriterLock(DWORD dwTimeout)
 304 {
 305     bool blCanWrite ;
 306
 307     EnterCS();
 308     if(0 == (m_iNumOfWriter | m_iNumOfReaderEntered))
 309     {
 310         ++m_iNumOfWriter;
 311         blCanWrite = TRUE;
 312     }
 313     else if(0 == dwTimeout)
 314     {
 315         blCanWrite = FALSE;
 316     }
 317     else
 318     {
 319         blCanWrite = _WriterWaitAndLeaveCSIfSuccess(dwTimeout);
 320         if(blCanWrite)
 321         {
 322             return TRUE;
 323         }
 324     }
 325
 326     LeaveCS();
 327     return blCanWrite;
 328 }
 329
 330 void CReaderWriterLockNonReentrance::ReleaseWriterLock()
 331 {
 332     EnterCS();
 333     _WriterRelease(FALSE);
 334     LeaveCS();
 335 }
 336
 337 void CReaderWriterLockNonReentrance::DowngradeFromWriterLock()
 338 {
 339     EnterCS();
 340     _WriterRelease(TRUE);
 341     LeaveCS();
 342 }
 343
 344 bool CReaderWriterLockNonReentrance::UpgradeToWriterLock(DWORD dwTimeout) throw()
 345 {
 346     EnterCS();
 347     return _UpgradeToWriterLockAndLeaveCS(dwTimeout);
 348 }
 349
 350 // END CReaderWriterLockNonReentrance implementation
 351 ///////////////////////////////////////////////////////
 352
 353 ///////////////////////////////////////////////////////
 354 // CReaderWriterLock implementation
 355
 356 #define READER_RECURRENCE_UNIT 0x00000001
 357 #define READER_RECURRENCE_MASK 0x0000FFFF
 358 #define WRITER_RECURRENCE_UNIT 0x00010000
 359
 360 CReaderWriterLock::CReaderWriterLock()
 361 {
 362 }
 363
 364 CReaderWriterLock::~CReaderWriterLock()
 365 {
 366 }
 367
 368 bool CReaderWriterLock::AcquireReaderLock(DWORD dwTimeout)
 369 {
 370     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 371
 372     m_impl.EnterCS();
 373     CMapThreadToState::iterator ite = m_map.find(dwCurrentThreadId);
 374
 375     if(ite != m_map.end())
 376     {
 377         //////////////////////////////////////////////////////////////////////////
 378         // Current thread was already a WRITER or READER
 379         _ASSERT(0 < ite->second);
 380         ite->second += READER_RECURRENCE_UNIT;
 381         m_impl.LeaveCS();
 382
 383         return TRUE;
 384     }
 385
 386     if(0 == m_impl.m_iNumOfWriter)
 387     {
 388         // There is NO WRITER on this RW object
 389         // Current thread is going to be a READER
 390         ++m_impl.m_iNumOfReaderEntered;
 391         m_map.insert(std::make_pair(dwCurrentThreadId, READER_RECURRENCE_UNIT));
 392
 393         m_impl.LeaveCS();
 394         return TRUE;
 395     }
 396
 397     if(0 == dwTimeout)
 398     {
 399         m_impl.LeaveCS();
 400         return FALSE;
 401     }
 402
 403     bool blCanRead = m_impl._ReaderWait(dwTimeout);
 404     if(blCanRead)
 405     {
 406         m_map.insert(std::make_pair(dwCurrentThreadId, READER_RECURRENCE_UNIT));
 407     }
 408     m_impl.LeaveCS();
 409
 410     return blCanRead;
 411 }
 412
 413 void CReaderWriterLock::ReleaseReaderLock()
 414 {
 415     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 416     m_impl.EnterCS();
 417
 418     CMapThreadToState::iterator ite = m_map.find(dwCurrentThreadId);
 419     _ASSERT( (ite != m_map.end()) && (READER_RECURRENCE_MASK & ite->second));
 420
 421     const DWORD dwThreadState = (ite->second -= READER_RECURRENCE_UNIT);
 422     if(0 == dwThreadState)
 423     {
 424         m_map.erase(ite);
 425         m_impl._ReaderRelease();
 426     }
 427     m_impl.LeaveCS();
 428 }
 429
 430 bool CReaderWriterLock::AcquireWriterLock(DWORD dwTimeout)
 431 {
 432     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 433     bool blCanWrite;
 434
 435     m_impl.EnterCS();
 436     CMapThreadToState::iterator ite = m_map.find(dwCurrentThreadId);
 437
 438     if(ite != m_map.end())
 439     {
 440         _ASSERT(0 < ite->second);
 441
 442         if(ite->second >= WRITER_RECURRENCE_UNIT)
 443         {
 444             // Current thread was already a WRITER
 445             ite->second += WRITER_RECURRENCE_UNIT;
 446             m_impl.LeaveCS();
 447             return TRUE;
 448         }
 449
 450         // Current thread was already a READER
 451         _ASSERT(1 <= m_impl.m_iNumOfReaderEntered);
 452         if(1 == m_impl.m_iNumOfReaderEntered)
 453         {
 454             // This object is owned by ONLY current thread for READ
 455             // There might be some threads queued to be WRITERs
 456             // but for effectiveness (higher throughput), we allow current
 457             // thread upgrading to be WRITER right now
 458             m_impl.m_iNumOfReaderEntered = 0;
 459             ++m_impl.m_iNumOfWriter;
 460             ite->second += WRITER_RECURRENCE_UNIT;
 461             m_impl.LeaveCS();
 462             return TRUE;
 463         }
 464
 465         // Try upgrading from reader to writer
 466         blCanWrite = m_impl._UpgradeToWriterLockAndLeaveCS(dwTimeout);
 467         if(blCanWrite)
 468         {
 469             m_impl.EnterCS();
 470             ite = m_map.find(dwCurrentThreadId);
 471             ite->second += WRITER_RECURRENCE_UNIT;
 472             m_impl.LeaveCS();
 473         }
 474     }
 475     else
 476     {
 477         if(0 == (m_impl.m_iNumOfWriter | m_impl.m_iNumOfReaderEntered))
 478         {
 479             // This RW object is not owned by any thread
 480             // --> it's safe to make this thread to be WRITER
 481             ++m_impl.m_iNumOfWriter;
 482             m_map.insert(std::make_pair(dwCurrentThreadId, WRITER_RECURRENCE_UNIT));
 483             m_impl.LeaveCS();
 484             return TRUE;
 485         }
 486
 487         if(0 == dwTimeout)
 488         {
 489             m_impl.LeaveCS();
 490             return FALSE;
 491         }
 492
 493         blCanWrite = m_impl._WriterWaitAndLeaveCSIfSuccess(dwTimeout);
 494         if(blCanWrite)
 495         {
 496             m_impl.EnterCS();
 497             m_map.insert(std::make_pair(dwCurrentThreadId, WRITER_RECURRENCE_UNIT));
 498         }
 499         m_impl.LeaveCS();
 500     }
 501
 502     return blCanWrite;
 503 }
 504
 505 void CReaderWriterLock::ReleaseWriterLock()
 506 {
 507     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 508     m_impl.EnterCS();
 509
 510     CMapThreadToState::iterator ite = m_map.find(dwCurrentThreadId);
 511     _ASSERT( (ite != m_map.end()) && (WRITER_RECURRENCE_UNIT <= ite->second));
 512
 513     const DWORD dwThreadState = (ite->second -= WRITER_RECURRENCE_UNIT);
 514     if(0 == dwThreadState)
 515     {
 516         m_map.erase(ite);
 517         m_impl._WriterRelease(FALSE);
 518     }
 519     else if (WRITER_RECURRENCE_UNIT > dwThreadState)
 520     {
 521         // Down-grading from writer to reader
 522         m_impl._WriterRelease(TRUE);
 523     }
 524     m_impl.LeaveCS();
 525 }
 526
 527 void CReaderWriterLock::ReleaseAllLocks()
 528 {
 529     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 530
 531     m_impl.EnterCS();
 532     CMapThreadToState::iterator ite = m_map.find(dwCurrentThreadId);
 533     if(ite != m_map.end())
 534     {
 535         const DWORD dwThreadState = ite->second;
 536         m_map.erase(ite);
 537         if(WRITER_RECURRENCE_UNIT <= dwThreadState)
 538         {
 539             m_impl._WriterRelease(FALSE);
 540         }
 541         else
 542         {
 543             _ASSERT(0 < dwThreadState);
 544             m_impl._ReaderRelease();
 545         }
 546     }
 547     m_impl.LeaveCS();
 548 }
 549
 550 DWORD CReaderWriterLock::GetCurrentThreadStatus() const throw()
 551 {
 552     DWORD dwThreadState;
 553     const DWORD dwCurrentThreadId = GetCurrentThreadId();
 554
 555     m_impl.EnterCS();
 556     CMapThreadToState::const_iterator ite = m_map.find(dwCurrentThreadId);
 557     if(ite != m_map.end())
 558     {
 559         dwThreadState = ite->second;
 560         m_impl.LeaveCS();
 561         _ASSERT(dwThreadState > 0);
 562     }
 563     else
 564     {
 565         dwThreadState = 0;
 566         m_impl.LeaveCS();
 567     }
 568
 569     return dwThreadState;
 570 }
 571
 572 void CReaderWriterLock::GetCurrentThreadStatus(DWORD* lpdwReaderLockCounter,
 573     DWORD* lpdwWriterLockCounter) const
 574 {
 575     const DWORD dwThreadState = GetCurrentThreadStatus();
 576
 577     if(NULL != lpdwReaderLockCounter)
 578     {
 579         *lpdwReaderLockCounter = (dwThreadState & READER_RECURRENCE_MASK);
 580     }
 581
 582     if(NULL != lpdwWriterLockCounter)
 583     {
 584         *lpdwWriterLockCounter = (dwThreadState / WRITER_RECURRENCE_UNIT);
 585     }
 586 }
 587