1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 #include "nssrwlk.h"
6 #include "nspr.h"
7
8 PR_BEGIN_EXTERN_C
9
10 /*
11 * Reader-writer lock
12 */
13 struct nssRWLockStr {
14 PZLock *rw_lock;
15 char *rw_name; /* lock name */
16 PRUint32 rw_rank; /* rank of the lock */
17 PRInt32 rw_writer_locks; /* == 0, if unlocked */
18 PRInt32 rw_reader_locks; /* == 0, if unlocked */
19 /* > 0 , # of read locks */
20 PRUint32 rw_waiting_readers; /* number of waiting readers */
21 PRUint32 rw_waiting_writers; /* number of waiting writers */
22 PZCondVar *rw_reader_waitq; /* cvar for readers */
23 PZCondVar *rw_writer_waitq; /* cvar for writers */
24 PRThread *rw_owner; /* lock owner for write-lock */
25 /* Non-null if write lock held. */
26 };
27
28 PR_END_EXTERN_C
29
30 #include <string.h>
31
32 #ifdef DEBUG_RANK_ORDER
33 #define NSS_RWLOCK_RANK_ORDER_DEBUG /* enable deadlock detection using \
34 rank-order for locks \
35 */
36 #endif
37
38 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
39
40 static PRUintn nss_thread_rwlock_initialized;
41 static PRUintn nss_thread_rwlock; /* TPD key for lock stack */
42 static PRUintn nss_thread_rwlock_alloc_failed;
43
44 #define _NSS_RWLOCK_RANK_ORDER_LIMIT 10
45
46 typedef struct thread_rwlock_stack {
47 PRInt32 trs_index; /* top of stack */
48 NSSRWLock *trs_stack[_NSS_RWLOCK_RANK_ORDER_LIMIT]; /* stack of lock
49 pointers */
50 } thread_rwlock_stack;
51
52 /* forward static declarations. */
53 static PRUint32 nssRWLock_GetThreadRank(PRThread *me);
54 static void nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock);
55 static void nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock);
56 static void nssRWLock_ReleaseLockStack(void *lock_stack);
57
58 #endif
59
60 #define UNTIL(x) while (!(x))
61
62 /*
63 * Reader/Writer Locks
64 */
65
66 /*
67 * NSSRWLock_New
68 * Create a reader-writer lock, with the given lock rank and lock name
69 *
70 */
71
72 NSSRWLock *
NSSRWLock_New(PRUint32 lock_rank,const char * lock_name)73 NSSRWLock_New(PRUint32 lock_rank, const char *lock_name)
74 {
75 NSSRWLock *rwlock;
76
77 rwlock = PR_NEWZAP(NSSRWLock);
78 if (rwlock == NULL)
79 return NULL;
80
81 rwlock->rw_lock = PZ_NewLock(nssILockRWLock);
82 if (rwlock->rw_lock == NULL) {
83 goto loser;
84 }
85 rwlock->rw_reader_waitq = PZ_NewCondVar(rwlock->rw_lock);
86 if (rwlock->rw_reader_waitq == NULL) {
87 goto loser;
88 }
89 rwlock->rw_writer_waitq = PZ_NewCondVar(rwlock->rw_lock);
90 if (rwlock->rw_writer_waitq == NULL) {
91 goto loser;
92 }
93 if (lock_name != NULL) {
94 rwlock->rw_name = (char *)PR_Malloc((PRUint32)strlen(lock_name) + 1);
95 if (rwlock->rw_name == NULL) {
96 goto loser;
97 }
98 strcpy(rwlock->rw_name, lock_name);
99 } else {
100 rwlock->rw_name = NULL;
101 }
102 rwlock->rw_rank = lock_rank;
103 rwlock->rw_waiting_readers = 0;
104 rwlock->rw_waiting_writers = 0;
105 rwlock->rw_reader_locks = 0;
106 rwlock->rw_writer_locks = 0;
107
108 return rwlock;
109
110 loser:
111 NSSRWLock_Destroy(rwlock);
112 return (NULL);
113 }
114
115 /*
116 ** Destroy the given RWLock "lock".
117 */
118 void
NSSRWLock_Destroy(NSSRWLock * rwlock)119 NSSRWLock_Destroy(NSSRWLock *rwlock)
120 {
121 PR_ASSERT(rwlock != NULL);
122 PR_ASSERT(rwlock->rw_waiting_readers == 0);
123 PR_ASSERT(rwlock->rw_writer_locks == 0);
124 PR_ASSERT(rwlock->rw_reader_locks == 0);
125
126 /* XXX Shouldn't we lock the PZLock before destroying this?? */
127
128 if (rwlock->rw_name)
129 PR_Free(rwlock->rw_name);
130 if (rwlock->rw_reader_waitq)
131 PZ_DestroyCondVar(rwlock->rw_reader_waitq);
132 if (rwlock->rw_writer_waitq)
133 PZ_DestroyCondVar(rwlock->rw_writer_waitq);
134 if (rwlock->rw_lock)
135 PZ_DestroyLock(rwlock->rw_lock);
136 PR_DELETE(rwlock);
137 }
138
139 /*
140 ** Read-lock the RWLock.
141 */
142 void
NSSRWLock_LockRead(NSSRWLock * rwlock)143 NSSRWLock_LockRead(NSSRWLock *rwlock)
144 {
145 PRThread *me = PR_GetCurrentThread();
146
147 PZ_Lock(rwlock->rw_lock);
148 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
149
150 /*
151 * assert that rank ordering is not violated; the rank of 'rwlock' should
152 * be equal to or greater than the highest rank of all the locks held by
153 * the thread.
154 */
155 PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
156 (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
157 #endif
158 /*
159 * wait if write-locked or if a writer is waiting; preference for writers
160 */
161 UNTIL((rwlock->rw_owner == me) || /* I own it, or */
162 ((rwlock->rw_owner == NULL) && /* no-one owns it, and */
163 (rwlock->rw_waiting_writers == 0)))
164 { /* no-one is waiting to own */
165
166 rwlock->rw_waiting_readers++;
167 PZ_WaitCondVar(rwlock->rw_reader_waitq, PR_INTERVAL_NO_TIMEOUT);
168 rwlock->rw_waiting_readers--;
169 }
170 rwlock->rw_reader_locks++; /* Increment read-lock count */
171
172 PZ_Unlock(rwlock->rw_lock);
173
174 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
175 nssRWLock_SetThreadRank(me, rwlock); /* update thread's lock rank */
176 #endif
177 }
178
179 /* Unlock a Read lock held on this RW lock.
180 */
181 void
NSSRWLock_UnlockRead(NSSRWLock * rwlock)182 NSSRWLock_UnlockRead(NSSRWLock *rwlock)
183 {
184 PZ_Lock(rwlock->rw_lock);
185
186 PR_ASSERT(rwlock->rw_reader_locks > 0); /* lock must be read locked */
187
188 if ((rwlock->rw_reader_locks > 0) && /* caller isn't screwey */
189 (--rwlock->rw_reader_locks == 0) && /* not read locked any more */
190 (rwlock->rw_owner == NULL) && /* not write locked */
191 (rwlock->rw_waiting_writers > 0)) { /* someone's waiting. */
192
193 PZ_NotifyCondVar(rwlock->rw_writer_waitq); /* wake him up. */
194 }
195
196 PZ_Unlock(rwlock->rw_lock);
197
198 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
199 /*
200 * update thread's lock rank
201 */
202 nssRWLock_UnsetThreadRank(me, rwlock);
203 #endif
204 return;
205 }
206
207 /*
208 ** Write-lock the RWLock.
209 */
210 void
NSSRWLock_LockWrite(NSSRWLock * rwlock)211 NSSRWLock_LockWrite(NSSRWLock *rwlock)
212 {
213 PRThread *me = PR_GetCurrentThread();
214
215 PZ_Lock(rwlock->rw_lock);
216 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
217 /*
218 * assert that rank ordering is not violated; the rank of 'rwlock' should
219 * be equal to or greater than the highest rank of all the locks held by
220 * the thread.
221 */
222 PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
223 (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
224 #endif
225 /*
226 * wait if read locked or write locked.
227 */
228 PR_ASSERT(rwlock->rw_reader_locks >= 0);
229 PR_ASSERT(me != NULL);
230
231 UNTIL((rwlock->rw_owner == me) || /* I own write lock, or */
232 ((rwlock->rw_owner == NULL) && /* no writer and */
233 (rwlock->rw_reader_locks == 0)))
234 { /* no readers, either. */
235
236 rwlock->rw_waiting_writers++;
237 PZ_WaitCondVar(rwlock->rw_writer_waitq, PR_INTERVAL_NO_TIMEOUT);
238 rwlock->rw_waiting_writers--;
239 PR_ASSERT(rwlock->rw_reader_locks >= 0);
240 }
241
242 PR_ASSERT(rwlock->rw_reader_locks == 0);
243 /*
244 * apply write lock
245 */
246 rwlock->rw_owner = me;
247 rwlock->rw_writer_locks++; /* Increment write-lock count */
248
249 PZ_Unlock(rwlock->rw_lock);
250
251 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
252 /*
253 * update thread's lock rank
254 */
255 nssRWLock_SetThreadRank(me, rwlock);
256 #endif
257 }
258
259 /* Unlock a Read lock held on this RW lock.
260 */
261 void
NSSRWLock_UnlockWrite(NSSRWLock * rwlock)262 NSSRWLock_UnlockWrite(NSSRWLock *rwlock)
263 {
264 PRThread *me = PR_GetCurrentThread();
265
266 PZ_Lock(rwlock->rw_lock);
267 PR_ASSERT(rwlock->rw_owner == me); /* lock must be write-locked by me. */
268 PR_ASSERT(rwlock->rw_writer_locks > 0); /* lock must be write locked */
269
270 if (rwlock->rw_owner == me && /* I own it, and */
271 rwlock->rw_writer_locks > 0 && /* I own it, and */
272 --rwlock->rw_writer_locks == 0) { /* I'm all done with it */
273
274 rwlock->rw_owner = NULL; /* I don't own it any more. */
275
276 /* Give preference to waiting writers. */
277 if (rwlock->rw_waiting_writers > 0) {
278 if (rwlock->rw_reader_locks == 0)
279 PZ_NotifyCondVar(rwlock->rw_writer_waitq);
280 } else if (rwlock->rw_waiting_readers > 0) {
281 PZ_NotifyAllCondVar(rwlock->rw_reader_waitq);
282 }
283 }
284 PZ_Unlock(rwlock->rw_lock);
285
286 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
287 /*
288 * update thread's lock rank
289 */
290 nssRWLock_UnsetThreadRank(me, rwlock);
291 #endif
292 return;
293 }
294
295 /* This is primarily for debugging, i.e. for inclusion in ASSERT calls. */
296 PRBool
NSSRWLock_HaveWriteLock(NSSRWLock * rwlock)297 NSSRWLock_HaveWriteLock(NSSRWLock *rwlock)
298 {
299 PRBool ownWriteLock;
300 PRThread *me = PR_GetCurrentThread();
301
302 /* This lock call isn't really necessary.
303 ** If this thread is the owner, that fact cannot change during this call,
304 ** because this thread is in this call.
305 ** If this thread is NOT the owner, the owner could change, but it
306 ** could not become this thread.
307 */
308 #if UNNECESSARY
309 PZ_Lock(rwlock->rw_lock);
310 #endif
311 ownWriteLock = (PRBool)(me == rwlock->rw_owner);
312 #if UNNECESSARY
313 PZ_Unlock(rwlock->rw_lock);
314 #endif
315 return ownWriteLock;
316 }
317
318 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
319
320 /*
321 * nssRWLock_SetThreadRank
322 * Set a thread's lock rank, which is the highest of the ranks of all
323 * the locks held by the thread. Pointers to the locks are added to a
324 * per-thread list, which is anchored off a thread-private data key.
325 */
326
327 static void
nssRWLock_SetThreadRank(PRThread * me,NSSRWLock * rwlock)328 nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock)
329 {
330 thread_rwlock_stack *lock_stack;
331 PRStatus rv;
332
333 /*
334 * allocated thread-private-data for rwlock list, if not already allocated
335 */
336 if (!nss_thread_rwlock_initialized) {
337 /*
338 * allocate tpd, only if not failed already
339 */
340 if (!nss_thread_rwlock_alloc_failed) {
341 if (PR_NewThreadPrivateIndex(&nss_thread_rwlock,
342 nssRWLock_ReleaseLockStack) == PR_FAILURE) {
343 nss_thread_rwlock_alloc_failed = 1;
344 return;
345 }
346 } else
347 return;
348 }
349 /*
350 * allocate a lock stack
351 */
352 if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL) {
353 lock_stack = (thread_rwlock_stack *)
354 PR_CALLOC(1 * sizeof(thread_rwlock_stack));
355 if (lock_stack) {
356 rv = PR_SetThreadPrivate(nss_thread_rwlock, lock_stack);
357 if (rv == PR_FAILURE) {
358 PR_DELETE(lock_stack);
359 nss_thread_rwlock_alloc_failed = 1;
360 return;
361 }
362 } else {
363 nss_thread_rwlock_alloc_failed = 1;
364 return;
365 }
366 }
367 /*
368 * add rwlock to lock stack, if limit is not exceeded
369 */
370 if (lock_stack) {
371 if (lock_stack->trs_index < _NSS_RWLOCK_RANK_ORDER_LIMIT)
372 lock_stack->trs_stack[lock_stack->trs_index++] = rwlock;
373 }
374 nss_thread_rwlock_initialized = 1;
375 }
376
377 static void
nssRWLock_ReleaseLockStack(void * lock_stack)378 nssRWLock_ReleaseLockStack(void *lock_stack)
379 {
380 PR_ASSERT(lock_stack);
381 PR_DELETE(lock_stack);
382 }
383
384 /*
385 * nssRWLock_GetThreadRank
386 *
387 * return thread's lock rank. If thread-private-data for the lock
388 * stack is not allocated, return NSS_RWLOCK_RANK_NONE.
389 */
390
391 static PRUint32
nssRWLock_GetThreadRank(PRThread * me)392 nssRWLock_GetThreadRank(PRThread *me)
393 {
394 thread_rwlock_stack *lock_stack;
395
396 if (nss_thread_rwlock_initialized) {
397 if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL)
398 return (NSS_RWLOCK_RANK_NONE);
399 else
400 return (lock_stack->trs_stack[lock_stack->trs_index - 1]->rw_rank);
401
402 } else
403 return (NSS_RWLOCK_RANK_NONE);
404 }
405
406 /*
407 * nssRWLock_UnsetThreadRank
408 *
409 * remove the rwlock from the lock stack. Since locks may not be
410 * unlocked in a FIFO order, the entire lock stack is searched.
411 */
412
413 static void
nssRWLock_UnsetThreadRank(PRThread * me,NSSRWLock * rwlock)414 nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock)
415 {
416 thread_rwlock_stack *lock_stack;
417 int new_index = 0, index, done = 0;
418
419 if (!nss_thread_rwlock_initialized)
420 return;
421
422 lock_stack = PR_GetThreadPrivate(nss_thread_rwlock);
423
424 PR_ASSERT(lock_stack != NULL);
425
426 index = lock_stack->trs_index - 1;
427 while (index-- >= 0) {
428 if ((lock_stack->trs_stack[index] == rwlock) && !done) {
429 /*
430 * reset the slot for rwlock
431 */
432 lock_stack->trs_stack[index] = NULL;
433 done = 1;
434 }
435 /*
436 * search for the lowest-numbered empty slot, above which there are
437 * no non-empty slots
438 */
439 if ((lock_stack->trs_stack[index] != NULL) && !new_index)
440 new_index = index + 1;
441 if (done && new_index)
442 break;
443 }
444 /*
445 * set top of stack to highest numbered empty slot
446 */
447 lock_stack->trs_index = new_index;
448 }
449
450 #endif /* NSS_RWLOCK_RANK_ORDER_DEBUG */
451