winebus.sys: Add missing keyboard free_device callback.
[wine.git] / dlls / ntdll / sync.c
blobf1263ae33fddd027305633c4f16497ad4307ad74
1 /*
2 * Process synchronisation
4 * Copyright 1996, 1997, 1998 Marcus Meissner
5 * Copyright 1997, 1999 Alexandre Julliard
6 * Copyright 1999, 2000 Juergen Schmied
7 * Copyright 2003 Eric Pouech
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
24 #include <limits.h>
25 #include <string.h>
26 #include <stdarg.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <time.h>
31 #include "ntstatus.h"
32 #define WIN32_NO_STATUS
33 #define NONAMELESSUNION
34 #include "windef.h"
35 #include "winternl.h"
36 #include "wine/debug.h"
37 #include "ntdll_misc.h"
40 /******************************************************************
41 * RtlRunOnceInitialize (NTDLL.@)
43 void WINAPI RtlRunOnceInitialize( RTL_RUN_ONCE *once )
45 once->Ptr = NULL;
48 /******************************************************************
49 * RtlRunOnceBeginInitialize (NTDLL.@)
51 DWORD WINAPI RtlRunOnceBeginInitialize( RTL_RUN_ONCE *once, ULONG flags, void **context )
53 if (flags & RTL_RUN_ONCE_CHECK_ONLY)
55 ULONG_PTR val = (ULONG_PTR)once->Ptr;
57 if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
58 if ((val & 3) != 2) return STATUS_UNSUCCESSFUL;
59 if (context) *context = (void *)(val & ~3);
60 return STATUS_SUCCESS;
63 for (;;)
65 ULONG_PTR next, val = (ULONG_PTR)once->Ptr;
67 switch (val & 3)
69 case 0: /* first time */
70 if (!InterlockedCompareExchangePointer( &once->Ptr,
71 (flags & RTL_RUN_ONCE_ASYNC) ? (void *)3 : (void *)1, 0 ))
72 return STATUS_PENDING;
73 break;
75 case 1: /* in progress, wait */
76 if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
77 next = val & ~3;
78 if (InterlockedCompareExchangePointer( &once->Ptr, (void *)((ULONG_PTR)&next | 1),
79 (void *)val ) == (void *)val)
80 NtWaitForKeyedEvent( 0, &next, FALSE, NULL );
81 break;
83 case 2: /* done */
84 if (context) *context = (void *)(val & ~3);
85 return STATUS_SUCCESS;
87 case 3: /* in progress, async */
88 if (!(flags & RTL_RUN_ONCE_ASYNC)) return STATUS_INVALID_PARAMETER;
89 return STATUS_PENDING;
94 /******************************************************************
95 * RtlRunOnceComplete (NTDLL.@)
97 DWORD WINAPI RtlRunOnceComplete( RTL_RUN_ONCE *once, ULONG flags, void *context )
99 if ((ULONG_PTR)context & 3) return STATUS_INVALID_PARAMETER;
101 if (flags & RTL_RUN_ONCE_INIT_FAILED)
103 if (context) return STATUS_INVALID_PARAMETER;
104 if (flags & RTL_RUN_ONCE_ASYNC) return STATUS_INVALID_PARAMETER;
106 else context = (void *)((ULONG_PTR)context | 2);
108 for (;;)
110 ULONG_PTR val = (ULONG_PTR)once->Ptr;
112 switch (val & 3)
114 case 1: /* in progress */
115 if (InterlockedCompareExchangePointer( &once->Ptr, context, (void *)val ) != (void *)val) break;
116 val &= ~3;
117 while (val)
119 ULONG_PTR next = *(ULONG_PTR *)val;
120 NtReleaseKeyedEvent( 0, (void *)val, FALSE, NULL );
121 val = next;
123 return STATUS_SUCCESS;
125 case 3: /* in progress, async */
126 if (!(flags & RTL_RUN_ONCE_ASYNC)) return STATUS_INVALID_PARAMETER;
127 if (InterlockedCompareExchangePointer( &once->Ptr, context, (void *)val ) != (void *)val) break;
128 return STATUS_SUCCESS;
130 default:
131 return STATUS_UNSUCCESSFUL;
136 /******************************************************************
137 * RtlRunOnceExecuteOnce (NTDLL.@)
139 DWORD WINAPI RtlRunOnceExecuteOnce( RTL_RUN_ONCE *once, PRTL_RUN_ONCE_INIT_FN func,
140 void *param, void **context )
142 DWORD ret = RtlRunOnceBeginInitialize( once, 0, context );
144 if (ret != STATUS_PENDING) return ret;
146 if (!func( once, param, context ))
148 RtlRunOnceComplete( once, RTL_RUN_ONCE_INIT_FAILED, NULL );
149 return STATUS_UNSUCCESSFUL;
152 return RtlRunOnceComplete( once, 0, context ? *context : NULL );
156 /* SRW locks implementation
158 * The memory layout used by the lock is:
160 * 32 31 16 0
161 * ________________ ________________
162 * | X| #exclusive | #shared |
163 * ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
164 * Since there is no space left for a separate counter of shared access
165 * threads inside the locked section the #shared field is used for multiple
166 * purposes. The following table lists all possible states the lock can be
167 * in, notation: [X, #exclusive, #shared]:
169 * [0, 0, N] -> locked by N shared access threads, if N=0 it's unlocked
170 * [0, >=1, >=1] -> threads are requesting exclusive locks, but there are
171 * still shared access threads inside. #shared should not be incremented
172 * anymore!
173 * [1, >=1, >=0] -> lock is owned by an exclusive thread and the #shared
174 * counter can be used again to count the number of threads waiting in the
175 * queue for shared access.
177 * the following states are invalid and will never occur:
178 * [0, >=1, 0], [1, 0, >=0]
180 * The main problem arising from the fact that we have no separate counter
181 * of shared access threads inside the locked section is that in the state
182 * [0, >=1, >=1] above we cannot add additional waiting threads to the
183 * shared access queue - it wouldn't be possible to distinguish waiting
184 * threads and those that are still inside. To solve this problem the lock
185 * uses the following approach: a thread that isn't able to allocate a
186 * shared lock just uses the exclusive queue instead. As soon as the thread
187 * is woken up it is in the state [1, >=1, >=0]. In this state it's again
188 * possible to use the shared access queue. The thread atomically moves
189 * itself to the shared access queue and releases the exclusive lock, so
190 * that the "real" exclusive access threads have a chance. As soon as they
191 * are all ready the shared access threads are processed.
194 #define SRWLOCK_MASK_IN_EXCLUSIVE 0x80000000
195 #define SRWLOCK_MASK_EXCLUSIVE_QUEUE 0x7fff0000
196 #define SRWLOCK_MASK_SHARED_QUEUE 0x0000ffff
197 #define SRWLOCK_RES_EXCLUSIVE 0x00010000
198 #define SRWLOCK_RES_SHARED 0x00000001
200 #ifdef WORDS_BIGENDIAN
201 #define srwlock_key_exclusive(lock) ((void *)(((ULONG_PTR)&lock->Ptr + 1) & ~1))
202 #define srwlock_key_shared(lock) ((void *)(((ULONG_PTR)&lock->Ptr + 3) & ~1))
203 #else
204 #define srwlock_key_exclusive(lock) ((void *)(((ULONG_PTR)&lock->Ptr + 3) & ~1))
205 #define srwlock_key_shared(lock) ((void *)(((ULONG_PTR)&lock->Ptr + 1) & ~1))
206 #endif
208 static inline void srwlock_check_invalid( unsigned int val )
210 /* Throw exception if it's impossible to acquire/release this lock. */
211 if ((val & SRWLOCK_MASK_EXCLUSIVE_QUEUE) == SRWLOCK_MASK_EXCLUSIVE_QUEUE ||
212 (val & SRWLOCK_MASK_SHARED_QUEUE) == SRWLOCK_MASK_SHARED_QUEUE)
213 RtlRaiseStatus(STATUS_RESOURCE_NOT_OWNED);
216 static inline unsigned int srwlock_lock_exclusive( unsigned int *dest, int incr )
218 unsigned int val, tmp;
219 /* Atomically modifies the value of *dest by adding incr. If the shared
220 * queue is empty and there are threads waiting for exclusive access, then
221 * sets the mark SRWLOCK_MASK_IN_EXCLUSIVE to signal other threads that
222 * they are allowed again to use the shared queue counter. */
223 for (val = *dest;; val = tmp)
225 tmp = val + incr;
226 srwlock_check_invalid( tmp );
227 if ((tmp & SRWLOCK_MASK_EXCLUSIVE_QUEUE) && !(tmp & SRWLOCK_MASK_SHARED_QUEUE))
228 tmp |= SRWLOCK_MASK_IN_EXCLUSIVE;
229 if ((tmp = InterlockedCompareExchange( (int *)dest, tmp, val )) == val)
230 break;
232 return val;
235 static inline unsigned int srwlock_unlock_exclusive( unsigned int *dest, int incr )
237 unsigned int val, tmp;
238 /* Atomically modifies the value of *dest by adding incr. If the queue of
239 * threads waiting for exclusive access is empty, then remove the
240 * SRWLOCK_MASK_IN_EXCLUSIVE flag (only the shared queue counter will
241 * remain). */
242 for (val = *dest;; val = tmp)
244 tmp = val + incr;
245 srwlock_check_invalid( tmp );
246 if (!(tmp & SRWLOCK_MASK_EXCLUSIVE_QUEUE))
247 tmp &= SRWLOCK_MASK_SHARED_QUEUE;
248 if ((tmp = InterlockedCompareExchange( (int *)dest, tmp, val )) == val)
249 break;
251 return val;
254 static inline void srwlock_leave_exclusive( RTL_SRWLOCK *lock, unsigned int val )
256 /* Used when a thread leaves an exclusive section. If there are other
257 * exclusive access threads they are processed first, followed by
258 * the shared waiters. */
259 if (val & SRWLOCK_MASK_EXCLUSIVE_QUEUE)
260 NtReleaseKeyedEvent( 0, srwlock_key_exclusive(lock), FALSE, NULL );
261 else
263 val &= SRWLOCK_MASK_SHARED_QUEUE; /* remove SRWLOCK_MASK_IN_EXCLUSIVE */
264 while (val--)
265 NtReleaseKeyedEvent( 0, srwlock_key_shared(lock), FALSE, NULL );
269 static inline void srwlock_leave_shared( RTL_SRWLOCK *lock, unsigned int val )
271 /* Wake up one exclusive thread as soon as the last shared access thread
272 * has left. */
273 if ((val & SRWLOCK_MASK_EXCLUSIVE_QUEUE) && !(val & SRWLOCK_MASK_SHARED_QUEUE))
274 NtReleaseKeyedEvent( 0, srwlock_key_exclusive(lock), FALSE, NULL );
277 /***********************************************************************
278 * RtlInitializeSRWLock (NTDLL.@)
280 * NOTES
281 * Please note that SRWLocks do not keep track of the owner of a lock.
282 * It doesn't make any difference which thread for example unlocks an
283 * SRWLock (see corresponding tests). This implementation uses two
284 * keyed events (one for the exclusive waiters and one for the shared
285 * waiters) and is limited to 2^15-1 waiting threads.
287 void WINAPI RtlInitializeSRWLock( RTL_SRWLOCK *lock )
289 lock->Ptr = NULL;
292 /***********************************************************************
293 * RtlAcquireSRWLockExclusive (NTDLL.@)
295 * NOTES
296 * Unlike RtlAcquireResourceExclusive this function doesn't allow
297 * nested calls from the same thread. "Upgrading" a shared access lock
298 * to an exclusive access lock also doesn't seem to be supported.
300 void WINAPI RtlAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
302 if (unix_funcs->fast_RtlAcquireSRWLockExclusive( lock ) != STATUS_NOT_IMPLEMENTED)
303 return;
305 if (srwlock_lock_exclusive( (unsigned int *)&lock->Ptr, SRWLOCK_RES_EXCLUSIVE ))
306 NtWaitForKeyedEvent( 0, srwlock_key_exclusive(lock), FALSE, NULL );
309 /***********************************************************************
310 * RtlAcquireSRWLockShared (NTDLL.@)
312 * NOTES
313 * Do not call this function recursively - it will only succeed when
314 * there are no threads waiting for an exclusive lock!
316 void WINAPI RtlAcquireSRWLockShared( RTL_SRWLOCK *lock )
318 unsigned int val, tmp;
320 if (unix_funcs->fast_RtlAcquireSRWLockShared( lock ) != STATUS_NOT_IMPLEMENTED)
321 return;
323 /* Acquires a shared lock. If it's currently not possible to add elements to
324 * the shared queue, then request exclusive access instead. */
325 for (val = *(unsigned int *)&lock->Ptr;; val = tmp)
327 if ((val & SRWLOCK_MASK_EXCLUSIVE_QUEUE) && !(val & SRWLOCK_MASK_IN_EXCLUSIVE))
328 tmp = val + SRWLOCK_RES_EXCLUSIVE;
329 else
330 tmp = val + SRWLOCK_RES_SHARED;
331 if ((tmp = InterlockedCompareExchange( (int *)&lock->Ptr, tmp, val )) == val)
332 break;
335 /* Drop exclusive access again and instead requeue for shared access. */
336 if ((val & SRWLOCK_MASK_EXCLUSIVE_QUEUE) && !(val & SRWLOCK_MASK_IN_EXCLUSIVE))
338 NtWaitForKeyedEvent( 0, srwlock_key_exclusive(lock), FALSE, NULL );
339 val = srwlock_unlock_exclusive( (unsigned int *)&lock->Ptr, (SRWLOCK_RES_SHARED
340 - SRWLOCK_RES_EXCLUSIVE) ) - SRWLOCK_RES_EXCLUSIVE;
341 srwlock_leave_exclusive( lock, val );
344 if (val & SRWLOCK_MASK_EXCLUSIVE_QUEUE)
345 NtWaitForKeyedEvent( 0, srwlock_key_shared(lock), FALSE, NULL );
348 /***********************************************************************
349 * RtlReleaseSRWLockExclusive (NTDLL.@)
351 void WINAPI RtlReleaseSRWLockExclusive( RTL_SRWLOCK *lock )
353 if (unix_funcs->fast_RtlReleaseSRWLockExclusive( lock ) != STATUS_NOT_IMPLEMENTED)
354 return;
356 srwlock_leave_exclusive( lock, srwlock_unlock_exclusive( (unsigned int *)&lock->Ptr,
357 - SRWLOCK_RES_EXCLUSIVE ) - SRWLOCK_RES_EXCLUSIVE );
360 /***********************************************************************
361 * RtlReleaseSRWLockShared (NTDLL.@)
363 void WINAPI RtlReleaseSRWLockShared( RTL_SRWLOCK *lock )
365 if (unix_funcs->fast_RtlReleaseSRWLockShared( lock ) != STATUS_NOT_IMPLEMENTED)
366 return;
368 srwlock_leave_shared( lock, srwlock_lock_exclusive( (unsigned int *)&lock->Ptr,
369 - SRWLOCK_RES_SHARED ) - SRWLOCK_RES_SHARED );
372 /***********************************************************************
373 * RtlTryAcquireSRWLockExclusive (NTDLL.@)
375 * NOTES
376 * Similarly to AcquireSRWLockExclusive, recursive calls are not allowed
377 * and will fail with a FALSE return value.
379 BOOLEAN WINAPI RtlTryAcquireSRWLockExclusive( RTL_SRWLOCK *lock )
381 NTSTATUS ret;
383 if ((ret = unix_funcs->fast_RtlTryAcquireSRWLockExclusive( lock )) != STATUS_NOT_IMPLEMENTED)
384 return (ret == STATUS_SUCCESS);
386 return InterlockedCompareExchange( (int *)&lock->Ptr, SRWLOCK_MASK_IN_EXCLUSIVE |
387 SRWLOCK_RES_EXCLUSIVE, 0 ) == 0;
390 /***********************************************************************
391 * RtlTryAcquireSRWLockShared (NTDLL.@)
393 BOOLEAN WINAPI RtlTryAcquireSRWLockShared( RTL_SRWLOCK *lock )
395 unsigned int val, tmp;
396 NTSTATUS ret;
398 if ((ret = unix_funcs->fast_RtlTryAcquireSRWLockShared( lock )) != STATUS_NOT_IMPLEMENTED)
399 return (ret == STATUS_SUCCESS);
401 for (val = *(unsigned int *)&lock->Ptr;; val = tmp)
403 if (val & SRWLOCK_MASK_EXCLUSIVE_QUEUE)
404 return FALSE;
405 if ((tmp = InterlockedCompareExchange( (int *)&lock->Ptr, val + SRWLOCK_RES_SHARED, val )) == val)
406 break;
408 return TRUE;
411 /***********************************************************************
412 * RtlInitializeConditionVariable (NTDLL.@)
414 * Initializes the condition variable with NULL.
416 * PARAMS
417 * variable [O] condition variable
419 * RETURNS
420 * Nothing.
422 void WINAPI RtlInitializeConditionVariable( RTL_CONDITION_VARIABLE *variable )
424 variable->Ptr = NULL;
427 /***********************************************************************
428 * RtlWakeConditionVariable (NTDLL.@)
430 * Wakes up one thread waiting on the condition variable.
432 * PARAMS
433 * variable [I/O] condition variable to wake up.
435 * RETURNS
436 * Nothing.
438 * NOTES
439 * The calling thread does not have to own any lock in order to call
440 * this function.
442 void WINAPI RtlWakeConditionVariable( RTL_CONDITION_VARIABLE *variable )
444 if (unix_funcs->fast_RtlWakeConditionVariable( variable, 1 ) == STATUS_NOT_IMPLEMENTED)
446 InterlockedIncrement( (int *)&variable->Ptr );
447 RtlWakeAddressSingle( variable );
451 /***********************************************************************
452 * RtlWakeAllConditionVariable (NTDLL.@)
454 * See WakeConditionVariable, wakes up all waiting threads.
456 void WINAPI RtlWakeAllConditionVariable( RTL_CONDITION_VARIABLE *variable )
458 if (unix_funcs->fast_RtlWakeConditionVariable( variable, INT_MAX ) == STATUS_NOT_IMPLEMENTED)
460 InterlockedIncrement( (int *)&variable->Ptr );
461 RtlWakeAddressAll( variable );
465 /***********************************************************************
466 * RtlSleepConditionVariableCS (NTDLL.@)
468 * Atomically releases the critical section and suspends the thread,
469 * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
470 * the critical section again and returns.
472 * PARAMS
473 * variable [I/O] condition variable
474 * crit [I/O] critical section to leave temporarily
475 * timeout [I] timeout
477 * RETURNS
478 * see NtWaitForKeyedEvent for all possible return values.
480 NTSTATUS WINAPI RtlSleepConditionVariableCS( RTL_CONDITION_VARIABLE *variable, RTL_CRITICAL_SECTION *crit,
481 const LARGE_INTEGER *timeout )
483 const void *value = variable->Ptr;
484 NTSTATUS status;
486 RtlLeaveCriticalSection( crit );
487 if ((status = unix_funcs->fast_wait_cv( variable, value, timeout )) == STATUS_NOT_IMPLEMENTED)
488 status = RtlWaitOnAddress( &variable->Ptr, &value, sizeof(value), timeout );
489 RtlEnterCriticalSection( crit );
490 return status;
493 /***********************************************************************
494 * RtlSleepConditionVariableSRW (NTDLL.@)
496 * Atomically releases the SRWLock and suspends the thread,
497 * waiting for a Wake(All)ConditionVariable event. Afterwards it enters
498 * the SRWLock again with the same access rights and returns.
500 * PARAMS
501 * variable [I/O] condition variable
502 * lock [I/O] SRWLock to leave temporarily
503 * timeout [I] timeout
504 * flags [I] type of the current lock (exclusive / shared)
506 * RETURNS
507 * see NtWaitForKeyedEvent for all possible return values.
509 * NOTES
510 * the behaviour is undefined if the thread doesn't own the lock.
512 NTSTATUS WINAPI RtlSleepConditionVariableSRW( RTL_CONDITION_VARIABLE *variable, RTL_SRWLOCK *lock,
513 const LARGE_INTEGER *timeout, ULONG flags )
515 const void *value = variable->Ptr;
516 NTSTATUS status;
518 if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
519 RtlReleaseSRWLockShared( lock );
520 else
521 RtlReleaseSRWLockExclusive( lock );
523 if ((status = unix_funcs->fast_wait_cv( variable, value, timeout )) == STATUS_NOT_IMPLEMENTED)
524 status = RtlWaitOnAddress( variable, &value, sizeof(value), timeout );
526 if (flags & RTL_CONDITION_VARIABLE_LOCKMODE_SHARED)
527 RtlAcquireSRWLockShared( lock );
528 else
529 RtlAcquireSRWLockExclusive( lock );
530 return status;
533 /***********************************************************************
534 * RtlWaitOnAddress (NTDLL.@)
536 NTSTATUS WINAPI RtlWaitOnAddress( const void *addr, const void *cmp, SIZE_T size,
537 const LARGE_INTEGER *timeout )
539 return unix_funcs->RtlWaitOnAddress( addr, cmp, size, timeout );
542 /***********************************************************************
543 * RtlWakeAddressAll (NTDLL.@)
545 void WINAPI RtlWakeAddressAll( const void *addr )
547 return unix_funcs->RtlWakeAddressAll( addr );
550 /***********************************************************************
551 * RtlWakeAddressSingle (NTDLL.@)
553 void WINAPI RtlWakeAddressSingle( const void *addr )
555 return unix_funcs->RtlWakeAddressSingle( addr );