1 /* 2 * Copyright 2005-2009, Haiku, Inc. All Rights Reserved. 3 * Distributed under the terms of the MIT license. 4 * 5 * Copyright 1999, Be Incorporated. All Rights Reserved. 6 * This file may be used under the terms of the Be Sample Code License. 7 */ 8 9 10 #include "MultiLocker.h" 11 12 #include <Debug.h> 13 #include <Errors.h> 14 #include <OS.h> 15 16 17 #define TIMING MULTI_LOCKER_TIMING 18 #ifndef DEBUG 19 # define DEBUG MULTI_LOCKER_DEBUG 20 #endif 21 22 23 const int32 LARGE_NUMBER = 100000; 24 25 26 MultiLocker::MultiLocker(const char* baseName) 27 : 28 #if DEBUG 29 fDebugArray(NULL), 30 fMaxThreads(0), 31 #else 32 fReadCount(0), 33 fWriteCount(0), 34 fLockCount(0), 35 #endif 36 fInit(B_NO_INIT), 37 fWriterNest(0), 38 fWriterThread(-1), 39 fWriterStackBase(0) 40 { 41 // build the semaphores 42 #if !DEBUG 43 if (baseName) { 44 char name[128]; 45 snprintf(name, sizeof(name), "%s-%s", baseName, "ReadSem"); 46 fReadSem = create_sem(0, name); 47 snprintf(name, sizeof(name), "%s-%s", baseName, "WriteSem"); 48 fWriteSem = create_sem(0, name); 49 snprintf(name, sizeof(name), "%s-%s", baseName, "WriterLock"); 50 fWriterLock = create_sem(0, name); 51 } else { 52 fReadSem = create_sem(0, "MultiLocker_ReadSem"); 53 fWriteSem = create_sem(0, "MultiLocker_WriteSem"); 54 fWriterLock = create_sem(0, "MultiLocker_WriterLock"); 55 } 56 57 if (fReadSem >= 0 && fWriteSem >=0 && fWriterLock >= 0) 58 fInit = B_OK; 59 #else 60 fLock = create_sem(LARGE_NUMBER, baseName != NULL ? baseName : "MultiLocker"); 61 if (fLock >= 0) 62 fInit = B_OK; 63 64 // we are in debug mode! 65 // create the reader tracking list 66 // the array needs to be large enough to hold all possible threads 67 system_info sys; 68 get_system_info(&sys); 69 fMaxThreads = sys.max_threads; 70 fDebugArray = (int32 *) malloc(fMaxThreads * sizeof(int32)); 71 for (int32 i = 0; i < fMaxThreads; i++) { 72 fDebugArray[i] = 0; 73 } 74 #endif 75 #if TIMING 76 //initialize the counter variables 77 rl_count = ru_count = wl_count = wu_count = islock_count = 0; 78 rl_time = ru_time = wl_time = wu_time = islock_time = 0; 79 #if DEBUG 80 reg_count = unreg_count = 0; 81 reg_time = unreg_time = 0; 82 #endif 83 #endif 84 } 85 86 87 MultiLocker::~MultiLocker() 88 { 89 // become the writer 90 if (!IsWriteLocked()) 91 WriteLock(); 92 93 // set locker to be uninitialized 94 fInit = B_NO_INIT; 95 96 #if !DEBUG 97 // delete the semaphores 98 delete_sem(fReadSem); 99 delete_sem(fWriteSem); 100 delete_sem(fWriterLock); 101 #else 102 delete_sem(fLock); 103 free(fDebugArray); 104 #endif 105 #if TIMING 106 // let's produce some performance numbers 107 printf("MultiLocker Statistics:\n" 108 "Avg ReadLock: %lld\n" 109 "Avg ReadUnlock: %lld\n" 110 "Avg WriteLock: %lld\n" 111 "Avg WriteUnlock: %lld\n" 112 "Avg IsWriteLocked: %lld\n", 113 rl_count > 0 ? rl_time / rl_count : 0, 114 ru_count > 0 ? ru_time / ru_count : 0, 115 wl_count > 0 ? wl_time / wl_count : 0, 116 wu_count > 0 ? wu_time / wu_count : 0, 117 islock_count > 0 ? islock_time / islock_count : 0); 118 #endif 119 } 120 121 122 status_t 123 MultiLocker::InitCheck() 124 { 125 return fInit; 126 } 127 128 129 /*! 130 This function demonstrates a nice method of determining if the current thread 131 is the writer or not. The method involves caching the index of the page in memory 132 where the thread's stack is located. Each time a new writer acquires the lock, 133 its thread_id and stack_page are recorded. IsWriteLocked gets the stack_page of the 134 current thread and sees if it is a match. If the stack_page matches you are guaranteed 135 to have the matching thread. If the stack page doesn't match the more traditional 136 find_thread(NULL) method of matching the thread_ids is used. 137 138 This technique is very useful when dealing with a lock that is acquired in a nested fashion. 139 It could be expanded to cache the information of the last thread in the lock, and then if 140 the same thread returns while there is no one in the lock, it could save some time, if the 141 same thread is likely to acquire the lock again and again. 142 I should note another shortcut that could be implemented here 143 If fWriterThread is set to -1 then there is no writer in the lock, and we could 144 return from this function much faster. However the function is currently set up 145 so all of the stack_base and thread_id info is determined here. WriteLock passes 146 in some variables so that if the lock is not held it does not have to get the thread_id 147 and stack base again. Instead this function returns that information. So this shortcut 148 would only move this information gathering outside of this function, and I like it all 149 contained. 150 */ 151 bool 152 MultiLocker::IsWriteLocked(addr_t* _stackBase, thread_id* _thread) const 153 { 154 #if TIMING 155 bigtime_t start = system_time(); 156 #endif 157 158 // get a variable on the stack 159 bool writeLockHolder = false; 160 161 if (fInit == B_OK) { 162 // determine which page in memory this stack represents 163 // this is managed by taking the address of the item on the 164 // stack and dividing it by the size of the memory pages 165 // if it is the same as the cached stack_page, there is a match 166 addr_t stackBase = (addr_t)&writeLockHolder / B_PAGE_SIZE; 167 thread_id thread = 0; 168 169 if (fWriterStackBase == stackBase) { 170 writeLockHolder = true; 171 } else { 172 // as there was no stack page match we resort to the 173 // tried and true methods 174 thread = find_thread(NULL); 175 if (fWriterThread == thread) 176 writeLockHolder = true; 177 } 178 179 // if someone wants this information, give it to them 180 if (_stackBase != NULL) 181 *_stackBase = stackBase; 182 if (_thread != NULL) 183 *_thread = thread; 184 } 185 186 #if TIMING 187 bigtime_t end = system_time(); 188 islock_time += (end - start); 189 islock_count++; 190 #endif 191 192 return writeLockHolder; 193 } 194 195 196 #if !DEBUG 197 // #pragma mark - Standard versions 198 199 200 bool 201 MultiLocker::ReadLock() 202 { 203 #if TIMING 204 bigtime_t start = system_time(); 205 #endif 206 207 bool locked = false; 208 209 // the lock must be initialized 210 if (fInit == B_OK) { 211 if (IsWriteLocked()) { 212 // the writer simply increments the nesting 213 fWriterNest++; 214 locked = true; 215 } else { 216 // increment and retrieve the current count of readers 217 int32 currentCount = atomic_add(&fReadCount, 1); 218 if (currentCount < 0) { 219 // a writer holds the lock so wait for fReadSem to be released 220 status_t status; 221 do { 222 status = acquire_sem(fReadSem); 223 } while (status == B_INTERRUPTED); 224 225 locked = status == B_OK; 226 } else 227 locked = true; 228 } 229 } 230 231 #if TIMING 232 bigtime_t end = system_time(); 233 rl_time += (end - start); 234 rl_count++; 235 #endif 236 237 return locked; 238 } 239 240 241 bool 242 MultiLocker::WriteLock() 243 { 244 #if TIMING 245 bigtime_t start = system_time(); 246 #endif 247 248 bool locked = false; 249 250 if (fInit == B_OK) { 251 addr_t stackBase = 0; 252 thread_id thread = -1; 253 254 if (IsWriteLocked(&stackBase, &thread)) { 255 // already the writer - increment the nesting count 256 fWriterNest++; 257 locked = true; 258 } else { 259 // new writer acquiring the lock 260 if (atomic_add(&fLockCount, 1) >= 1) { 261 // another writer in the lock - acquire the semaphore 262 status_t status; 263 do { 264 status = acquire_sem(fWriterLock); 265 } while (status == B_INTERRUPTED); 266 267 locked = status == B_OK; 268 } else 269 locked = true; 270 271 if (locked) { 272 // new holder of the lock 273 274 // decrement fReadCount by a very large number 275 // this will cause new readers to block on fReadSem 276 int32 readers = atomic_add(&fReadCount, -LARGE_NUMBER); 277 if (readers > 0) { 278 // readers hold the lock - acquire fWriteSem 279 status_t status; 280 do { 281 status = acquire_sem_etc(fWriteSem, readers, 0, 0); 282 } while (status == B_INTERRUPTED); 283 284 locked = status == B_OK; 285 } 286 if (locked) { 287 ASSERT(fWriterThread == -1); 288 // record thread information 289 fWriterThread = thread; 290 fWriterStackBase = stackBase; 291 } 292 } 293 } 294 } 295 296 #if TIMING 297 bigtime_t end = system_time(); 298 wl_time += (end - start); 299 wl_count++; 300 #endif 301 302 return locked; 303 } 304 305 306 bool 307 MultiLocker::ReadUnlock() 308 { 309 #if TIMING 310 bigtime_t start = system_time(); 311 #endif 312 313 bool unlocked = false; 314 315 if (IsWriteLocked()) { 316 // writers simply decrement the nesting count 317 fWriterNest--; 318 unlocked = true; 319 } else { 320 // decrement and retrieve the read counter 321 int32 current_count = atomic_add(&fReadCount, -1); 322 if (current_count < 0) { 323 // a writer is waiting for the lock so release fWriteSem 324 unlocked = release_sem_etc(fWriteSem, 1, B_DO_NOT_RESCHEDULE) == B_OK; 325 } else 326 unlocked = true; 327 } 328 329 #if TIMING 330 bigtime_t end = system_time(); 331 ru_time += (end - start); 332 ru_count++; 333 #endif 334 335 return unlocked; 336 } 337 338 339 bool 340 MultiLocker::WriteUnlock() 341 { 342 #if TIMING 343 bigtime_t start = system_time(); 344 #endif 345 346 bool unlocked = false; 347 348 if (IsWriteLocked()) { 349 // if this is a nested lock simply decrement the nest count 350 if (fWriterNest > 0) { 351 fWriterNest--; 352 unlocked = true; 353 } else { 354 // writer finally unlocking 355 356 // increment fReadCount by a large number 357 // this will let new readers acquire the read lock 358 // retrieve the number of current waiters 359 int32 readersWaiting = atomic_add(&fReadCount, LARGE_NUMBER) 360 + LARGE_NUMBER; 361 362 if (readersWaiting > 0) { 363 // readers are waiting to acquire the lock 364 unlocked = release_sem_etc(fReadSem, readersWaiting, 365 B_DO_NOT_RESCHEDULE) == B_OK; 366 } else 367 unlocked = true; 368 369 if (unlocked) { 370 // clear the information 371 fWriterThread = -1; 372 fWriterStackBase = 0; 373 374 // decrement and retrieve the lock count 375 if (atomic_add(&fLockCount, -1) > 1) { 376 // other writers are waiting so release fWriterLock 377 unlocked = release_sem_etc(fWriterLock, 1, 378 B_DO_NOT_RESCHEDULE) == B_OK; 379 } 380 } 381 } 382 } else 383 debugger("Non-writer attempting to WriteUnlock()"); 384 385 #if TIMING 386 bigtime_t end = system_time(); 387 wu_time += (end - start); 388 wu_count++; 389 #endif 390 391 return unlocked; 392 } 393 394 395 #else // DEBUG 396 // #pragma mark - Debug versions 397 398 399 bool 400 MultiLocker::ReadLock() 401 { 402 bool locked = false; 403 404 if (fInit != B_OK) 405 debugger("lock not initialized"); 406 407 if (IsWriteLocked()) { 408 if (fWriterNest < 0) 409 debugger("ReadLock() - negative writer nest count"); 410 411 fWriterNest++; 412 locked = true; 413 } else { 414 status_t status; 415 do { 416 status = acquire_sem(fLock); 417 } while (status == B_INTERRUPTED); 418 419 locked = status == B_OK; 420 421 if (locked) 422 _RegisterThread(); 423 } 424 425 return locked; 426 } 427 428 429 bool 430 MultiLocker::WriteLock() 431 { 432 bool locked = false; 433 434 if (fInit != B_OK) 435 debugger("lock not initialized"); 436 437 addr_t stackBase = 0; 438 thread_id thread = -1; 439 440 if (IsWriteLocked(&stackBase, &thread)) { 441 if (fWriterNest < 0) 442 debugger("WriteLock() - negative writer nest count"); 443 444 fWriterNest++; 445 locked = true; 446 } else { 447 // new writer acquiring the lock 448 if (IsReadLocked()) 449 debugger("Reader wants to become writer!"); 450 451 status_t status; 452 do { 453 status = acquire_sem_etc(fLock, LARGE_NUMBER, 0, 0); 454 } while (status == B_INTERRUPTED); 455 456 locked = status == B_OK; 457 if (locked) { 458 // record thread information 459 fWriterThread = thread; 460 fWriterStackBase = stackBase; 461 } 462 } 463 464 return locked; 465 } 466 467 468 bool 469 MultiLocker::ReadUnlock() 470 { 471 bool unlocked = false; 472 473 if (IsWriteLocked()) { 474 // writers simply decrement the nesting count 475 fWriterNest--; 476 if (fWriterNest < 0) 477 debugger("ReadUnlock() - negative writer nest count"); 478 479 unlocked = true; 480 } else { 481 // decrement and retrieve the read counter 482 unlocked = release_sem_etc(fLock, 1, B_DO_NOT_RESCHEDULE) == B_OK; 483 if (unlocked) 484 _UnregisterThread(); 485 } 486 487 return unlocked; 488 } 489 490 491 bool 492 MultiLocker::WriteUnlock() 493 { 494 bool unlocked = false; 495 496 if (IsWriteLocked()) { 497 // if this is a nested lock simply decrement the nest count 498 if (fWriterNest > 0) { 499 fWriterNest--; 500 unlocked = true; 501 } else { 502 // clear the information while still holding the lock 503 fWriterThread = -1; 504 fWriterStackBase = 0; 505 unlocked = release_sem_etc(fLock, LARGE_NUMBER, 506 B_DO_NOT_RESCHEDULE) == B_OK; 507 } 508 } else { 509 char message[256]; 510 snprintf(message, sizeof(message), "Non-writer attempting to " 511 "WriteUnlock() - write holder: %" B_PRId32, fWriterThread); 512 debugger(message); 513 } 514 515 return unlocked; 516 } 517 518 519 bool 520 MultiLocker::IsReadLocked() const 521 { 522 if (fInit == B_NO_INIT) 523 return false; 524 525 // determine if the lock is actually held 526 thread_id thread = find_thread(NULL); 527 return fDebugArray[thread % fMaxThreads] > 0; 528 } 529 530 531 /* these two functions manage the debug array for readers */ 532 /* an array is created in the constructor large enough to hold */ 533 /* an int32 for each of the maximum number of threads the system */ 534 /* can have at one time. */ 535 /* this array does not need to be locked because each running thread */ 536 /* can be uniquely mapped to a slot in the array by performing: */ 537 /* thread_id % max_threads */ 538 /* each time ReadLock is called while in debug mode the thread_id */ 539 /* is retrived in register_thread() and the count is adjusted in the */ 540 /* array. If register thread is ever called and the count is not 0 then */ 541 /* an illegal, potentially deadlocking nested ReadLock occured */ 542 /* unregister_thread clears the appropriate slot in the array */ 543 544 /* this system could be expanded or retracted to include multiple arrays of information */ 545 /* in all fairness for it's current use, fDebugArray could be an array of bools */ 546 547 /* The disadvantage of this system for maintaining state is that it sucks up a ton of */ 548 /* memory. The other method (which would be slower), would involve an additional lock and */ 549 /* traversing a list of cached information. As this is only for a debug mode, the extra memory */ 550 /* was not deemed to be a problem */ 551 552 void 553 MultiLocker::_RegisterThread() 554 { 555 thread_id thread = find_thread(NULL); 556 557 if (fDebugArray[thread % fMaxThreads] != 0) 558 debugger("Nested ReadLock!"); 559 560 fDebugArray[thread % fMaxThreads]++; 561 } 562 563 564 void 565 MultiLocker::_UnregisterThread() 566 { 567 thread_id thread = find_thread(NULL); 568 569 ASSERT(fDebugArray[thread % fMaxThreads] == 1); 570 fDebugArray[thread % fMaxThreads]--; 571 } 572 573 #endif // DEBUG 574