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