src/tests/servers/app/newerClipping/MultiLocker.cpp

   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