1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 /*
7 * w95cv.c -- Windows 95 Machine-Dependent Code for Condition Variables
8 *
9 * We implement our own condition variable wait queue. Each thread
10 * has a semaphore object (thread->md.blocked_sema) to block on while
11 * waiting on a condition variable.
12 *
13 * We use a deferred condition notify algorithm. When PR_NotifyCondVar
14 * or PR_NotifyAllCondVar is called, the condition notifies are simply
15 * recorded in the _MDLock structure. We defer the condition notifies
16 * until right after we unlock the lock. This way the awakened threads
17 * have a better chance to reaquire the lock.
18 */
19
20 #include "primpl.h"
21
22 /*
23 * AddThreadToCVWaitQueueInternal --
24 *
25 * Add the thread to the end of the condition variable's wait queue.
26 * The CV's lock must be locked when this function is called.
27 */
28
29 static void
AddThreadToCVWaitQueueInternal(PRThread * thred,struct _MDCVar * cv)30 AddThreadToCVWaitQueueInternal(PRThread *thred, struct _MDCVar *cv)
31 {
32 PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL)
33 || (cv->waitTail == NULL && cv->waitHead == NULL));
34 cv->nwait += 1;
35 thred->md.inCVWaitQueue = PR_TRUE;
36 thred->md.next = NULL;
37 thred->md.prev = cv->waitTail;
38 if (cv->waitHead == NULL) {
39 cv->waitHead = thred;
40 } else {
41 cv->waitTail->md.next = thred;
42 }
43 cv->waitTail = thred;
44 }
45
46 /*
47 * md_UnlockAndPostNotifies --
48 *
49 * Unlock the lock, and then do the deferred condition notifies.
50 * If waitThred and waitCV are not NULL, waitThred is added to
51 * the wait queue of waitCV before the lock is unlocked.
52 *
53 * This function is called by _PR_MD_WAIT_CV and _PR_MD_UNLOCK,
54 * the two places where a lock is unlocked.
55 */
56 static void
md_UnlockAndPostNotifies(_MDLock * lock,PRThread * waitThred,_MDCVar * waitCV)57 md_UnlockAndPostNotifies(
58 _MDLock *lock,
59 PRThread *waitThred,
60 _MDCVar *waitCV)
61 {
62 PRIntn index;
63 _MDNotified post;
64 _MDNotified *notified, *prev = NULL;
65
66 /*
67 * Time to actually notify any conditions that were affected
68 * while the lock was held. Get a copy of the list that's in
69 * the lock structure and then zero the original. If it's
70 * linked to other such structures, we own that storage.
71 */
72 post = lock->notified; /* a safe copy; we own the lock */
73
74 #if defined(DEBUG)
75 ZeroMemory(&lock->notified, sizeof(_MDNotified)); /* reset */
76 #else
77 lock->notified.length = 0; /* these are really sufficient */
78 lock->notified.link = NULL;
79 #endif
80
81 /*
82 * Figure out how many threads we need to wake up.
83 */
84 notified = &post; /* this is where we start */
85 do {
86 for (index = 0; index < notified->length; ++index) {
87 _MDCVar *cv = notified->cv[index].cv;
88 PRThread *thred;
89 int i;
90
91 /* Fast special case: no waiting threads */
92 if (cv->waitHead == NULL) {
93 notified->cv[index].notifyHead = NULL;
94 continue;
95 }
96
97 /* General case */
98 if (-1 == notified->cv[index].times) {
99 /* broadcast */
100 thred = cv->waitHead;
101 while (thred != NULL) {
102 thred->md.inCVWaitQueue = PR_FALSE;
103 thred = thred->md.next;
104 }
105 notified->cv[index].notifyHead = cv->waitHead;
106 cv->waitHead = cv->waitTail = NULL;
107 cv->nwait = 0;
108 } else {
109 thred = cv->waitHead;
110 i = notified->cv[index].times;
111 while (thred != NULL && i > 0) {
112 thred->md.inCVWaitQueue = PR_FALSE;
113 thred = thred->md.next;
114 i--;
115 }
116 notified->cv[index].notifyHead = cv->waitHead;
117 cv->waitHead = thred;
118 if (cv->waitHead == NULL) {
119 cv->waitTail = NULL;
120 } else {
121 if (cv->waitHead->md.prev != NULL) {
122 cv->waitHead->md.prev->md.next = NULL;
123 cv->waitHead->md.prev = NULL;
124 }
125 }
126 cv->nwait -= notified->cv[index].times - i;
127 }
128 }
129 notified = notified->link;
130 } while (NULL != notified);
131
132 if (waitThred) {
133 AddThreadToCVWaitQueueInternal(waitThred, waitCV);
134 }
135
136 /* Release the lock before notifying */
137 LeaveCriticalSection(&lock->mutex);
138
139 notified = &post; /* this is where we start */
140 do {
141 for (index = 0; index < notified->length; ++index) {
142 PRThread *thred;
143 PRThread *next;
144
145 thred = notified->cv[index].notifyHead;
146 while (thred != NULL) {
147 BOOL rv;
148
149 next = thred->md.next;
150 thred->md.prev = thred->md.next = NULL;
151
152 rv = ReleaseSemaphore(thred->md.blocked_sema, 1, NULL);
153 PR_ASSERT(rv != 0);
154 thred = next;
155 }
156 }
157 prev = notified;
158 notified = notified->link;
159 if (&post != prev) {
160 PR_DELETE(prev);
161 }
162 } while (NULL != notified);
163 }
164
165 /*
166 * Notifies just get posted to the protecting mutex. The
167 * actual notification is done when the lock is released so that
168 * MP systems don't contend for a lock that they can't have.
169 */
md_PostNotifyToCvar(_MDCVar * cvar,_MDLock * lock,PRBool broadcast)170 static void md_PostNotifyToCvar(_MDCVar *cvar, _MDLock *lock,
171 PRBool broadcast)
172 {
173 PRIntn index = 0;
174 _MDNotified *notified = &lock->notified;
175
176 while (1) {
177 for (index = 0; index < notified->length; ++index) {
178 if (notified->cv[index].cv == cvar) {
179 if (broadcast) {
180 notified->cv[index].times = -1;
181 } else if (-1 != notified->cv[index].times) {
182 notified->cv[index].times += 1;
183 }
184 return;
185 }
186 }
187 /* if not full, enter new CV in this array */
188 if (notified->length < _MD_CV_NOTIFIED_LENGTH) {
189 break;
190 }
191
192 /* if there's no link, create an empty array and link it */
193 if (NULL == notified->link) {
194 notified->link = PR_NEWZAP(_MDNotified);
195 }
196
197 notified = notified->link;
198 }
199
200 /* A brand new entry in the array */
201 notified->cv[index].times = (broadcast) ? -1 : 1;
202 notified->cv[index].cv = cvar;
203 notified->length += 1;
204 }
205
206 /*
207 * _PR_MD_NEW_CV() -- Creating new condition variable
208 * ... Solaris uses cond_init() in similar function.
209 *
210 * returns: -1 on failure
211 * 0 when it succeeds.
212 *
213 */
214 PRInt32
_PR_MD_NEW_CV(_MDCVar * cv)215 _PR_MD_NEW_CV(_MDCVar *cv)
216 {
217 cv->magic = _MD_MAGIC_CV;
218 /*
219 * The waitHead, waitTail, and nwait fields are zeroed
220 * when the PRCondVar structure is created.
221 */
222 return 0;
223 }
224
_PR_MD_FREE_CV(_MDCVar * cv)225 void _PR_MD_FREE_CV(_MDCVar *cv)
226 {
227 cv->magic = (PRUint32)-1;
228 return;
229 }
230
231 /*
232 * _PR_MD_WAIT_CV() -- Wait on condition variable
233 */
_PR_MD_WAIT_CV(_MDCVar * cv,_MDLock * lock,PRIntervalTime timeout)234 void _PR_MD_WAIT_CV(_MDCVar *cv, _MDLock *lock, PRIntervalTime timeout )
235 {
236 PRThread *thred = _PR_MD_CURRENT_THREAD();
237 DWORD rv;
238 DWORD msecs = (timeout == PR_INTERVAL_NO_TIMEOUT) ?
239 INFINITE : PR_IntervalToMilliseconds(timeout);
240
241 /*
242 * If we have pending notifies, post them now.
243 */
244 if (0 != lock->notified.length) {
245 md_UnlockAndPostNotifies(lock, thred, cv);
246 } else {
247 AddThreadToCVWaitQueueInternal(thred, cv);
248 LeaveCriticalSection(&lock->mutex);
249 }
250
251 /* Wait for notification or timeout; don't really care which */
252 rv = WaitForSingleObject(thred->md.blocked_sema, msecs);
253
254 EnterCriticalSection(&(lock->mutex));
255
256 PR_ASSERT(rv != WAIT_ABANDONED);
257 PR_ASSERT(rv != WAIT_FAILED);
258 PR_ASSERT(rv != WAIT_OBJECT_0 || thred->md.inCVWaitQueue == PR_FALSE);
259
260 if (rv == WAIT_TIMEOUT) {
261 if (thred->md.inCVWaitQueue) {
262 PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL)
263 || (cv->waitTail == NULL && cv->waitHead == NULL));
264 cv->nwait -= 1;
265 thred->md.inCVWaitQueue = PR_FALSE;
266 if (cv->waitHead == thred) {
267 cv->waitHead = thred->md.next;
268 if (cv->waitHead == NULL) {
269 cv->waitTail = NULL;
270 } else {
271 cv->waitHead->md.prev = NULL;
272 }
273 } else {
274 PR_ASSERT(thred->md.prev != NULL);
275 thred->md.prev->md.next = thred->md.next;
276 if (thred->md.next != NULL) {
277 thred->md.next->md.prev = thred->md.prev;
278 } else {
279 PR_ASSERT(cv->waitTail == thred);
280 cv->waitTail = thred->md.prev;
281 }
282 }
283 thred->md.next = thred->md.prev = NULL;
284 } else {
285 /*
286 * This thread must have been notified, but the
287 * ReleaseSemaphore call happens after WaitForSingleObject
288 * times out. Wait on the semaphore again to make it
289 * non-signaled. We assume this wait won't take long.
290 */
291 rv = WaitForSingleObject(thred->md.blocked_sema, INFINITE);
292 PR_ASSERT(rv == WAIT_OBJECT_0);
293 }
294 }
295 PR_ASSERT(thred->md.inCVWaitQueue == PR_FALSE);
296 return;
297 } /* --- end _PR_MD_WAIT_CV() --- */
298
_PR_MD_NOTIFY_CV(_MDCVar * cv,_MDLock * lock)299 void _PR_MD_NOTIFY_CV(_MDCVar *cv, _MDLock *lock)
300 {
301 md_PostNotifyToCvar(cv, lock, PR_FALSE);
302 return;
303 }
304
_PR_MD_NOTIFYALL_CV(_MDCVar * cv,_MDLock * lock)305 void _PR_MD_NOTIFYALL_CV(_MDCVar *cv, _MDLock *lock)
306 {
307 md_PostNotifyToCvar(cv, lock, PR_TRUE);
308 return;
309 }
310
311 typedef BOOL (WINAPI *INITIALIZECRITICALSECTIONEX)(
312 CRITICAL_SECTION *lpCriticalSection,
313 DWORD dwSpinCount,
314 DWORD Flags);
315
316 static INITIALIZECRITICALSECTIONEX sInitializeCriticalSectionEx;
317
_PR_MD_INIT_LOCKS(void)318 void _PR_MD_INIT_LOCKS(void)
319 {
320 /*
321 * Starting with Windows Vista, every CRITICAL_SECTION allocates an extra
322 * RTL_CRITICAL_SECTION_DEBUG object. Unfortunately, this debug object is
323 * not reclaimed by DeleteCriticalSection(), causing an apparent memory
324 * leak. This is a debugging "feature", not a bug. If we are running on
325 * Vista or later, use InitializeCriticalSectionEx() to allocate
326 * CRITICAL_SECTIONs without debug objects.
327 */
328 HMODULE hKernel32 = GetModuleHandle("kernel32.dll");
329 PR_ASSERT(hKernel32);
330 PR_ASSERT(!sInitializeCriticalSectionEx);
331 sInitializeCriticalSectionEx = (INITIALIZECRITICALSECTIONEX)
332 GetProcAddress(hKernel32, "InitializeCriticalSectionEx");
333 }
334
335 /*
336 * By default, CRITICAL_SECTIONs are initialized with a spin count of 0.
337 * Joe Duffy's "Concurrent Programming on Windows" book suggests 1500 is
338 * a "reasonable starting point". On single-processor systems, the spin
339 * count is ignored and the critical section spin count is set to 0.
340 */
341 #define LOCK_SPIN_COUNT 1500
342
_PR_MD_NEW_LOCK(_MDLock * lock)343 PRStatus _PR_MD_NEW_LOCK(_MDLock *lock)
344 {
345 CRITICAL_SECTION *cs = &lock->mutex;
346 BOOL ok;
347
348 if (sInitializeCriticalSectionEx) {
349 ok = sInitializeCriticalSectionEx(cs, LOCK_SPIN_COUNT,
350 CRITICAL_SECTION_NO_DEBUG_INFO);
351 } else {
352 ok = InitializeCriticalSectionAndSpinCount(cs, LOCK_SPIN_COUNT);
353 }
354 if (!ok) {
355 _PR_MD_MAP_DEFAULT_ERROR(GetLastError());
356 return PR_FAILURE;
357 }
358
359 lock->notified.length = 0;
360 lock->notified.link = NULL;
361 return PR_SUCCESS;
362 }
363
_PR_MD_UNLOCK(_MDLock * lock)364 void _PR_MD_UNLOCK(_MDLock *lock)
365 {
366 if (0 != lock->notified.length) {
367 md_UnlockAndPostNotifies(lock, NULL, NULL);
368 } else {
369 LeaveCriticalSection(&lock->mutex);
370 }
371 }
372