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