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 82 class 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 134 typedef AutoLocker<RWLocker, AutoLockerReadLocking<RWLocker> > AutoReadLocker; 135 typedef AutoLocker<RWLocker, AutoLockerWriteLocking<RWLocker> > AutoWriteLocker; 136 137 #endif // RW_LOCKER_H 138