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
14 struct RWLocker::ReadLockInfo {
15 thread_id reader;
16 int32 count;
17 };
18
19
20 // constructor
RWLocker()21 RWLocker::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
RWLocker(const char * name)36 RWLocker::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
~RWLocker()51 RWLocker::~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
61 bool
ReadLock()62 RWLocker::ReadLock()
63 {
64 status_t error = _ReadLock(B_INFINITE_TIMEOUT);
65 return (error == B_OK);
66 }
67
68 // ReadLockWithTimeout
69 status_t
ReadLockWithTimeout(bigtime_t timeout)70 RWLocker::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
80 void
ReadUnlock()81 RWLocker::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.
113 bool
IsReadLocked() const114 RWLocker::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
126 bool
WriteLock()127 RWLocker::WriteLock()
128 {
129 status_t error = _WriteLock(B_INFINITE_TIMEOUT);
130 return (error == B_OK);
131 }
132
133 // WriteLockWithTimeout
134 status_t
WriteLockWithTimeout(bigtime_t timeout)135 RWLocker::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
145 void
WriteUnlock()146 RWLocker::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.
179 bool
IsWriteLocked() const180 RWLocker::IsWriteLocked() const
181 {
182 return (fWriter == find_thread(NULL));
183 }
184
185 // _Init
186 void
_Init(const char * name)187 RWLocker::_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
204 status_t
_ReadLock(bigtime_t timeout)205 RWLocker::_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
275 status_t
_WriteLock(bigtime_t timeout)276 RWLocker::_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
404 int32
_AddReadLockInfo(ReadLockInfo * info)405 RWLocker::_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.
416 int32
_NewReadLockInfo(thread_id thread,int32 count)417 RWLocker::_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
426 void
_DeleteReadLockInfo(int32 index)427 RWLocker::_DeleteReadLockInfo(int32 index)
428 {
429 if (ReadLockInfo* info = (ReadLockInfo*)fReadLockInfos.RemoveItem(index))
430 delete info;
431 }
432
433 // _ReadLockInfoAt
434 RWLocker::ReadLockInfo*
_ReadLockInfoAt(int32 index) const435 RWLocker::_ReadLockInfoAt(int32 index) const
436 {
437 return (ReadLockInfo*)fReadLockInfos.ItemAt(index);
438 }
439
440 // _IndexOf
441 int32
_IndexOf(thread_id thread) const442 RWLocker::_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
453 status_t
_AcquireBenaphore(Benaphore & benaphore,bigtime_t timeout)454 RWLocker::_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
465 void
_ReleaseBenaphore(Benaphore & benaphore)466 RWLocker::_ReleaseBenaphore(Benaphore& benaphore)
467 {
468 if (atomic_add(&benaphore.counter, -1) > 1)
469 release_sem(benaphore.semaphore);
470 }
471
472