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#include "RWLocker.h"
10
11#include <String.h>
12
13// info about a read lock owner
14struct RWLocker::ReadLockInfo {
15	thread_id	reader;
16	int32		count;
17};
18
19
20// constructor
21RWLocker::RWLocker()
22	: fLock(),
23	  fMutex(),
24	  fQueue(),
25	  fReaderCount(0),
26	  fWriterCount(0),
27	  fReadLockInfos(8),
28	  fWriter(B_ERROR),
29	  fWriterWriterCount(0),
30	  fWriterReaderCount(0)
31{
32	_Init(NULL);
33}
34
35// constructor
36RWLocker::RWLocker(const char* name)
37	: fLock(name),
38	  fMutex(),
39	  fQueue(),
40	  fReaderCount(0),
41	  fWriterCount(0),
42	  fReadLockInfos(8),
43	  fWriter(B_ERROR),
44	  fWriterWriterCount(0),
45	  fWriterReaderCount(0)
46{
47	_Init(name);
48}
49
50// destructor
51RWLocker::~RWLocker()
52{
53	fLock.Lock();
54	delete_sem(fMutex.semaphore);
55	delete_sem(fQueue.semaphore);
56	for (int32 i = 0; ReadLockInfo* info = _ReadLockInfoAt(i); i++)
57		delete info;
58}
59
60// ReadLock
61bool
62RWLocker::ReadLock()
63{
64	status_t error = _ReadLock(B_INFINITE_TIMEOUT);
65	return (error == B_OK);
66}
67
68// ReadLockWithTimeout
69status_t
70RWLocker::ReadLockWithTimeout(bigtime_t timeout)
71{
72	bigtime_t absoluteTimeout = system_time() + timeout;
73	// take care of overflow
74	if (timeout > 0 && absoluteTimeout < 0)
75		absoluteTimeout = B_INFINITE_TIMEOUT;
76	return _ReadLock(absoluteTimeout);
77}
78
79// ReadUnlock
80void
81RWLocker::ReadUnlock()
82{
83	if (fLock.Lock()) {
84		thread_id thread = find_thread(NULL);
85		if (thread == fWriter) {
86			// We (also) have a write lock.
87			if (fWriterReaderCount > 0)
88				fWriterReaderCount--;
89			// else: error: unmatched ReadUnlock()
90		} else {
91			int32 index = _IndexOf(thread);
92			if (ReadLockInfo* info = _ReadLockInfoAt(index)) {
93				fReaderCount--;
94				if (--info->count == 0) {
95					// The outer read lock bracket for the thread has been
96					// reached. Dispose the info.
97					_DeleteReadLockInfo(index);
98				}
99				if (fReaderCount == 0) {
100					// The last reader needs to unlock the mutex.
101					_ReleaseBenaphore(fMutex);
102				}
103			}	// else: error: caller has no read lock
104		}
105		fLock.Unlock();
106	}	// else: we are probably going to be destroyed
107}
108
109// IsReadLocked
110//
111// Returns whether or not the calling thread owns a read lock or even a
112// write lock.
113bool
114RWLocker::IsReadLocked() const
115{
116	bool result = false;
117	if (fLock.Lock()) {
118		thread_id thread = find_thread(NULL);
119		result = (thread == fWriter || _IndexOf(thread) >= 0);
120		fLock.Unlock();
121	}
122	return result;
123}
124
125// WriteLock
126bool
127RWLocker::WriteLock()
128{
129	status_t error = _WriteLock(B_INFINITE_TIMEOUT);
130	return (error == B_OK);
131}
132
133// WriteLockWithTimeout
134status_t
135RWLocker::WriteLockWithTimeout(bigtime_t timeout)
136{
137	bigtime_t absoluteTimeout = system_time() + timeout;
138	// take care of overflow
139	if (timeout > 0 && absoluteTimeout < 0)
140		absoluteTimeout = B_INFINITE_TIMEOUT;
141	return _WriteLock(absoluteTimeout);
142}
143
144// WriteUnlock
145void
146RWLocker::WriteUnlock()
147{
148	if (fLock.Lock()) {
149		thread_id thread = find_thread(NULL);
150		if (thread == fWriter) {
151			fWriterCount--;
152			if (--fWriterWriterCount == 0) {
153				// The outer write lock bracket for the thread has been
154				// reached.
155				fWriter = B_ERROR;
156				if (fWriterReaderCount > 0) {
157					// We still own read locks.
158					_NewReadLockInfo(thread, fWriterReaderCount);
159					// A reader that expects to be the first reader may wait
160					// at the mutex semaphore. We need to wake it up.
161					if (fReaderCount > 0)
162						_ReleaseBenaphore(fMutex);
163					fReaderCount += fWriterReaderCount;
164					fWriterReaderCount = 0;
165				} else {
166					// We don't own any read locks. So we have to release the
167					// mutex benaphore.
168					_ReleaseBenaphore(fMutex);
169				}
170			}
171		}	// else: error: unmatched WriteUnlock()
172		fLock.Unlock();
173	}	// else: We're probably going to die.
174}
175
176// IsWriteLocked
177//
178// Returns whether or not the calling thread owns a write lock.
179bool
180RWLocker::IsWriteLocked() const
181{
182	return (fWriter == find_thread(NULL));
183}
184
185// _Init
186void
187RWLocker::_Init(const char* name)
188{
189	// init the mutex benaphore
190	BString mutexName(name);
191	mutexName += "_RWLocker_mutex";
192	fMutex.semaphore = create_sem(0, mutexName.String());
193	fMutex.counter = 0;
194	// init the queueing benaphore
195	BString queueName(name);
196	queueName += "_RWLocker_queue";
197	fQueue.semaphore = create_sem(0, queueName.String());
198	fQueue.counter = 0;
199}
200
201// _ReadLock
202//
203// /timeout/ -- absolute timeout
204status_t
205RWLocker::_ReadLock(bigtime_t timeout)
206{
207	status_t error = B_OK;
208	thread_id thread = find_thread(NULL);
209	bool locked = false;
210	if (fLock.Lock()) {
211		// Check, if we already own a read (or write) lock. In this case we
212		// can skip the usual locking procedure.
213		if (thread == fWriter) {
214			// We already own a write lock.
215			fWriterReaderCount++;
216			locked = true;
217		} else if (ReadLockInfo* info = _ReadLockInfoAt(_IndexOf(thread))) {
218			// We already own a read lock.
219			info->count++;
220			fReaderCount++;
221			locked = true;
222		}
223		fLock.Unlock();
224	} else	// failed to lock the data
225		error = B_ERROR;
226	// Usual locking, i.e. we do not already own a read or write lock.
227	if (error == B_OK && !locked) {
228		error = _AcquireBenaphore(fQueue, timeout);
229		if (error == B_OK) {
230			if (fLock.Lock()) {
231				bool firstReader = false;
232				if (++fReaderCount == 1) {
233					// We are the first reader.
234					_NewReadLockInfo(thread);
235					firstReader = true;
236				} else
237					_NewReadLockInfo(thread);
238				fLock.Unlock();
239				// The first reader needs to lock the mutex.
240				if (firstReader) {
241					error = _AcquireBenaphore(fMutex, timeout);
242					switch (error) {
243						case B_OK:
244							// fine
245							break;
246						case B_TIMED_OUT: {
247							// clean up
248							if (fLock.Lock()) {
249								_DeleteReadLockInfo(_IndexOf(thread));
250								fReaderCount--;
251								fLock.Unlock();
252							}
253							break;
254						}
255						default:
256							// Probably we are going to be destroyed.
257							break;
258					}
259				}
260				// Let the next candidate enter the game.
261				_ReleaseBenaphore(fQueue);
262			} else {
263				// We couldn't lock the data, which can only happen, if
264				// we're going to be destroyed.
265				error = B_ERROR;
266			}
267		}
268	}
269	return error;
270}
271
272// _WriteLock
273//
274// /timeout/ -- absolute timeout
275status_t
276RWLocker::_WriteLock(bigtime_t timeout)
277{
278	status_t error = B_ERROR;
279	if (fLock.Lock()) {
280		bool infiniteTimeout = (timeout == B_INFINITE_TIMEOUT);
281		bool locked = false;
282		int32 readerCount = 0;
283		thread_id thread = find_thread(NULL);
284		int32 index = _IndexOf(thread);
285		if (ReadLockInfo* info = _ReadLockInfoAt(index)) {
286			// We already own a read lock.
287			if (fWriterCount > 0) {
288				// There are writers before us.
289				if (infiniteTimeout) {
290					// Timeout is infinite and there are writers before us.
291					// Unregister the read locks and lock as usual.
292					readerCount = info->count;
293					fWriterCount++;
294					fReaderCount -= readerCount;
295					_DeleteReadLockInfo(index);
296					error = B_OK;
297				} else {
298					// The timeout is finite and there are readers before us:
299					// let the write lock request fail.
300					error = B_WOULD_BLOCK;
301				}
302			} else if (info->count == fReaderCount) {
303				// No writers before us.
304				// We are the only read lock owners. Just move the read lock
305				// info data to the special writer fields and then we are done.
306				// Note: At this point we may overtake readers that already
307				// have acquired the queueing benaphore, but have not yet
308				// locked the data. But that doesn't harm.
309				fWriter = thread;
310				fWriterCount++;
311				fWriterWriterCount = 1;
312				fWriterReaderCount = info->count;
313				fReaderCount -= fWriterReaderCount;
314				_DeleteReadLockInfo(index);
315				locked = true;
316				error = B_OK;
317			} else {
318				// No writers before us, but other readers.
319				// Note, we're quite restrictive here. If there are only
320				// readers before us, we could reinstall our readers, if
321				// our request times out. Unfortunately it is not easy
322				// to ensure, that no writer overtakes us between unlocking
323				// the data and acquiring the queuing benaphore.
324				if (infiniteTimeout) {
325					// Unregister the readers and lock as usual.
326					readerCount = info->count;
327					fWriterCount++;
328					fReaderCount -= readerCount;
329					_DeleteReadLockInfo(index);
330					error = B_OK;
331				} else
332					error = B_WOULD_BLOCK;
333			}
334		} else {
335			// We don't own a read lock.
336			if (fWriter == thread) {
337				// ... but a write lock.
338				fWriterCount++;
339				fWriterWriterCount++;
340				locked = true;
341				error = B_OK;
342			} else {
343				// We own neither read nor write locks.
344				// Lock as usual.
345				fWriterCount++;
346				error = B_OK;
347			}
348		}
349		fLock.Unlock();
350		// Usual locking...
351		// First step: acquire the queueing benaphore.
352		if (!locked && error == B_OK) {
353			error = _AcquireBenaphore(fQueue, timeout);
354			switch (error) {
355				case B_OK:
356					break;
357				case B_TIMED_OUT: {
358					// clean up
359					if (fLock.Lock()) {
360						fWriterCount--;
361						fLock.Unlock();
362					}	// else: failed to lock the data: we're probably going
363						// to die.
364					break;
365				}
366				default:
367					// Probably we're going to die.
368					break;
369			}
370		}
371		// Second step: acquire the mutex benaphore.
372		if (!locked && error == B_OK) {
373			error = _AcquireBenaphore(fMutex, timeout);
374			switch (error) {
375				case B_OK: {
376					// Yeah, we made it. Set the special writer fields.
377					fWriter = thread;
378					fWriterWriterCount = 1;
379					fWriterReaderCount = readerCount;
380					break;
381				}
382				case B_TIMED_OUT: {
383					// clean up
384					if (fLock.Lock()) {
385						fWriterCount--;
386						fLock.Unlock();
387					}	// else: failed to lock the data: we're probably going
388						// to die.
389					break;
390				}
391				default:
392					// Probably we're going to die.
393					break;
394			}
395			// Whatever happened, we have to release the queueing benaphore.
396			_ReleaseBenaphore(fQueue);
397		}
398	} else	// failed to lock the data
399		error = B_ERROR;
400	return error;
401}
402
403// _AddReadLockInfo
404int32
405RWLocker::_AddReadLockInfo(ReadLockInfo* info)
406{
407	int32 index = fReadLockInfos.CountItems();
408	fReadLockInfos.AddItem(info, index);
409	return index;
410}
411
412// _NewReadLockInfo
413//
414// Create a new read lock info for the supplied thread and add it to the
415// list. Returns the index of the info.
416int32
417RWLocker::_NewReadLockInfo(thread_id thread, int32 count)
418{
419	ReadLockInfo* info = new ReadLockInfo;
420	info->reader = thread;
421	info->count = count;
422	return _AddReadLockInfo(info);
423}
424
425// _DeleteReadLockInfo
426void
427RWLocker::_DeleteReadLockInfo(int32 index)
428{
429	if (ReadLockInfo* info = (ReadLockInfo*)fReadLockInfos.RemoveItem(index))
430		delete info;
431}
432
433// _ReadLockInfoAt
434RWLocker::ReadLockInfo*
435RWLocker::_ReadLockInfoAt(int32 index) const
436{
437	return (ReadLockInfo*)fReadLockInfos.ItemAt(index);
438}
439
440// _IndexOf
441int32
442RWLocker::_IndexOf(thread_id thread) const
443{
444	int32 count = fReadLockInfos.CountItems();
445	for (int32 i = 0; i < count; i++) {
446		if (_ReadLockInfoAt(i)->reader == thread)
447			return i;
448	}
449	return -1;
450}
451
452// _AcquireBenaphore
453status_t
454RWLocker::_AcquireBenaphore(Benaphore& benaphore, bigtime_t timeout)
455{
456	status_t error = B_OK;
457	if (atomic_add(&benaphore.counter, 1) > 0) {
458		error = acquire_sem_etc(benaphore.semaphore, 1, B_ABSOLUTE_TIMEOUT,
459								timeout);
460	}
461	return error;
462}
463
464// _ReleaseBenaphore
465void
466RWLocker::_ReleaseBenaphore(Benaphore& benaphore)
467{
468	if (atomic_add(&benaphore.counter, -1) > 1)
469		release_sem(benaphore.semaphore);
470}
471
472