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