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 sprintf(name, "%s-%s", baseName, "ReadSem"); 46 fReadSem = create_sem(0, name); 47 sprintf(name, "%s-%s", baseName, "WriteSem"); 48 fWriteSem = create_sem(0, name); 49 sprintf(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(uint32* _stackBase, thread_id* _thread) 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 uint32 stackBase = (uint32)&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 uint32 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 uint32 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 DEBUG 449 if (IsReadLocked()) 450 debugger("Reader wants to become writer!"); 451 #endif 452 453 status_t status; 454 do { 455 status = acquire_sem_etc(fLock, LARGE_NUMBER, 0, 0); 456 } while (status == B_INTERRUPTED); 457 458 locked = status == B_OK; 459 if (locked) { 460 // record thread information 461 fWriterThread = thread; 462 fWriterStackBase = stackBase; 463 } 464 } 465 466 return locked; 467 } 468 469 470 bool 471 MultiLocker::ReadUnlock() 472 { 473 bool unlocked = false; 474 475 if (IsWriteLocked()) { 476 // writers simply decrement the nesting count 477 fWriterNest--; 478 if (fWriterNest < 0) 479 debugger("ReadUnlock() - negative writer nest count"); 480 481 unlocked = true; 482 } else { 483 // decrement and retrieve the read counter 484 unlocked = release_sem_etc(fLock, 1, B_DO_NOT_RESCHEDULE) == B_OK; 485 if (unlocked) 486 _UnregisterThread(); 487 } 488 489 return unlocked; 490 } 491 492 493 bool 494 MultiLocker::WriteUnlock() 495 { 496 bool unlocked = false; 497 498 if (IsWriteLocked()) { 499 // if this is a nested lock simply decrement the nest count 500 if (fWriterNest > 0) { 501 fWriterNest--; 502 unlocked = true; 503 } else { 504 unlocked = release_sem_etc(fLock, LARGE_NUMBER, B_DO_NOT_RESCHEDULE) == B_OK; 505 if (unlocked) { 506 // clear the information 507 fWriterThread = -1; 508 fWriterStackBase = 0; 509 } 510 } 511 } else { 512 debug_printf("write holder %ld\n", fWriterThread); 513 debugger("Non-writer attempting to WriteUnlock()"); 514 } 515 516 return unlocked; 517 } 518 519 520 bool 521 MultiLocker::IsReadLocked() 522 { 523 if (fInit == B_NO_INIT) 524 return false; 525 526 // determine if the lock is actually held 527 thread_id thread = find_thread(NULL); 528 return fDebugArray[thread % fMaxThreads] > 0; 529 } 530 531 532 /* these two functions manage the debug array for readers */ 533 /* an array is created in the constructor large enough to hold */ 534 /* an int32 for each of the maximum number of threads the system */ 535 /* can have at one time. */ 536 /* this array does not need to be locked because each running thread */ 537 /* can be uniquely mapped to a slot in the array by performing: */ 538 /* thread_id % max_threads */ 539 /* each time ReadLock is called while in debug mode the thread_id */ 540 /* is retrived in register_thread() and the count is adjusted in the */ 541 /* array. If register thread is ever called and the count is not 0 then */ 542 /* an illegal, potentially deadlocking nested ReadLock occured */ 543 /* unregister_thread clears the appropriate slot in the array */ 544 545 /* this system could be expanded or retracted to include multiple arrays of information */ 546 /* in all fairness for it's current use, fDebugArray could be an array of bools */ 547 548 /* The disadvantage of this system for maintaining state is that it sucks up a ton of */ 549 /* memory. The other method (which would be slower), would involve an additional lock and */ 550 /* traversing a list of cached information. As this is only for a debug mode, the extra memory */ 551 /* was not deemed to be a problem */ 552 553 void 554 MultiLocker::_RegisterThread() 555 { 556 thread_id thread = find_thread(NULL); 557 558 if (fDebugArray[thread % fMaxThreads] != 0) 559 debugger("Nested ReadLock!"); 560 561 fDebugArray[thread % fMaxThreads]++; 562 } 563 564 565 void 566 MultiLocker::_UnregisterThread() 567 { 568 thread_id thread = find_thread(NULL); 569 570 ASSERT(fDebugArray[thread % fMaxThreads] == 1); 571 fDebugArray[thread % fMaxThreads]--; 572 } 573 574 #endif // DEBUG 575