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
MultiLocker(const char * semaphoreBaseName)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
~MultiLocker()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
InitCheck()117 MultiLocker::InitCheck()
118 {
119 return fInit;
120 }
121
122 bool
ReadLock()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
WriteLock()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
ReadUnlock()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
WriteUnlock()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
IsWriteLocked(uint32 * the_stack_base,thread_id * the_thread)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
IsReadLocked()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
register_thread()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
unregister_thread()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