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 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 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 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 62 RWLocker::ReadLock() 63 { 64 status_t error = _ReadLock(B_INFINITE_TIMEOUT); 65 return (error == B_OK); 66 } 67 68 // ReadLockWithTimeout 69 status_t 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 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 114 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 127 RWLocker::WriteLock() 128 { 129 status_t error = _WriteLock(B_INFINITE_TIMEOUT); 130 return (error == B_OK); 131 } 132 133 // WriteLockWithTimeout 134 status_t 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 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 180 RWLocker::IsWriteLocked() const 181 { 182 return (fWriter == find_thread(NULL)); 183 } 184 185 // _Init 186 void 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 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 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 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 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 427 RWLocker::_DeleteReadLockInfo(int32 index) 428 { 429 if (ReadLockInfo* info = (ReadLockInfo*)fReadLockInfos.RemoveItem(index)) 430 delete info; 431 } 432 433 // _ReadLockInfoAt 434 RWLocker::ReadLockInfo* 435 RWLocker::_ReadLockInfoAt(int32 index) const 436 { 437 return (ReadLockInfo*)fReadLockInfos.ItemAt(index); 438 } 439 440 // _IndexOf 441 int32 442 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 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 466 RWLocker::_ReleaseBenaphore(Benaphore& benaphore) 467 { 468 if (atomic_add(&benaphore.counter, -1) > 1) 469 release_sem(benaphore.semaphore); 470 } 471 472