1/* 2 * Copyright 2006, Haiku. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * IngoWeinhold <bonefish@cs.tu-berlin.de> 7 */ 8 9// This class provides a reader/writer locking mechanism: 10// * A writer needs an exclusive lock. 11// * For a reader a non-exclusive lock to be shared with other readers is 12// sufficient. 13// * The ownership of a lock is bound to the thread that requested the lock; 14// the same thread has to call Unlock() later. 15// * Nested locking is supported: a number of XXXLock() calls needs to be 16// bracketed by the same number of XXXUnlock() calls. 17// * The lock acquiration strategy is fair: a lock applicant needs to wait 18// only for those threads that already own a lock or requested one before 19// the current thread. No one can overtake. E.g. if a thread owns a read 20// lock, another one is waiting for a write lock, then a third one 21// requesting a read lock has to wait until the write locker is done. 22// This does not hold for threads that already own a lock (nested locking). 23// A read lock owner is immediately granted another read lock and a write 24// lock owner another write or a read lock. 25// * A write lock owner is allowed to request a read lock and a read lock 26// owner a write lock. While the first case is not problematic, the 27// second one needs some further explanation: A read lock owner requesting 28// a write lock temporarily looses its read lock(s) until the write lock 29// is granted. Otherwise two read lock owning threads trying to get 30// write locks at the same time would dead lock each other. The only 31// problem with this solution is, that the write lock acquiration must 32// not fail, because in that case the thread could not be given back 33// its read lock(s), since another thread may have been given a write lock 34// in the mean time. Fortunately locking can fail only either, if the 35// locker has been deleted, or, if a timeout occured. Therefore 36// WriteLockWithTimeout() immediatlely returns with a B_WOULD_BLOCK error 37// code, if the caller already owns a read lock (but no write lock) and 38// another thread already owns or has requested a read or write lock. 39// * Calls to read and write locking methods may interleave arbitrarily, 40// e.g.: ReadLock(); WriteLock(); ReadUnlock(); WriteUnlock(); 41// 42// Important note: Read/WriteLock() can fail only, if the locker has been 43// deleted. However, it is NOT save to invoke any method on a deleted 44// locker object. 45// 46// Implementation details: 47// A locker needs three semaphores (a BLocker and two semaphores): one 48// to protect the lockers data, one as a reader/writer mutex (to be 49// acquired by each writer and the first reader) and one for queueing 50// waiting readers and writers. The simplified locking/unlocking 51// algorithm is the following: 52// 53// writer reader 54// queue.acquire() queue.acquire() 55// mutex.acquire() if (first reader) mutex.acquire() 56// queue.release() queue.release() 57// ... ... 58// mutex.release() if (last reader) mutex.release() 59// 60// One thread at maximum waits at the mutex, the others at the queueing 61// semaphore. Unfortunately features as nested locking and timeouts make 62// things more difficult. Therefore readers as well as writers need to check 63// whether they already own a lock before acquiring the queueing semaphore. 64// The data for the readers are stored in a list of ReadLockInfo structures; 65// the writer data are stored in some special fields. /fReaderCount/ and 66// /fWriterCount/ contain the total count of unbalanced Read/WriteLock() 67// calls, /fWriterReaderCount/ and /fWriterWriterCount/ only from those of 68// the current write lock owner (/fWriter/). To be a bit more precise: 69// /fWriterReaderCount/ is not contained in /fReaderCount/, but 70// /fWriterWriterCount/ is contained in /fWriterCount/. Therefore 71// /fReaderCount/ can be considered to be the count of true reader's read 72// locks. 73 74#ifndef RW_LOCKER_H 75#define RW_LOCKER_H 76 77#include <List.h> 78#include <Locker.h> 79 80#include "AutoLocker.h" 81 82class RWLocker { 83 public: 84 RWLocker(); 85 RWLocker(const char* name); 86 virtual ~RWLocker(); 87 88 bool ReadLock(); 89 status_t ReadLockWithTimeout(bigtime_t timeout); 90 void ReadUnlock(); 91 bool IsReadLocked() const; 92 93 bool WriteLock(); 94 status_t WriteLockWithTimeout(bigtime_t timeout); 95 void WriteUnlock(); 96 bool IsWriteLocked() const; 97 98 private: 99 struct ReadLockInfo; 100 struct Benaphore { 101 sem_id semaphore; 102 int32 counter; 103 }; 104 105 private: 106 void _Init(const char* name); 107 status_t _ReadLock(bigtime_t timeout); 108 status_t _WriteLock(bigtime_t timeout); 109 110 int32 _AddReadLockInfo(ReadLockInfo* info); 111 int32 _NewReadLockInfo(thread_id thread, 112 int32 count = 1); 113 void _DeleteReadLockInfo(int32 index); 114 ReadLockInfo* _ReadLockInfoAt(int32 index) const; 115 int32 _IndexOf(thread_id thread) const; 116 117 static status_t _AcquireBenaphore(Benaphore& benaphore, 118 bigtime_t timeout); 119 static void _ReleaseBenaphore(Benaphore& benaphore); 120 121 private: 122 mutable BLocker fLock; // data lock 123 Benaphore fMutex; // critical code mutex 124 Benaphore fQueue; // queueing semaphore 125 int32 fReaderCount; // total count... 126 int32 fWriterCount; // total count... 127 BList fReadLockInfos; 128 thread_id fWriter; // current write lock owner 129 int32 fWriterWriterCount; // write lock owner count 130 int32 fWriterReaderCount; // writer read lock owner 131 // count 132}; 133 134typedef AutoLocker<RWLocker, AutoLockerReadLocking<RWLocker> > AutoReadLocker; 135typedef AutoLocker<RWLocker, AutoLockerWriteLocking<RWLocker> > AutoWriteLocker; 136 137#endif // RW_LOCKER_H 138