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