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