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