ntdll: Don't require heap sizes to be 64K aligned.
[wine] / dlls / ntdll / threadpool.c
1 /*
2  * Thread pooling
3  *
4  * Copyright (c) 2006 Robert Shearman
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
19  */
20
21 #include "config.h"
22 #include "wine/port.h"
23
24 #include <assert.h>
25 #include <stdarg.h>
26 #include <limits.h>
27
28 #define NONAMELESSUNION
29 #include "ntstatus.h"
30 #define WIN32_NO_STATUS
31 #include "winternl.h"
32
33 #include "wine/debug.h"
34 #include "wine/list.h"
35
36 #include "ntdll_misc.h"
37
38 WINE_DEFAULT_DEBUG_CHANNEL(threadpool);
39
40 #define WORKER_TIMEOUT 30000 /* 30 seconds */
41
42 static LONG num_workers;
43 static LONG num_work_items;
44 static LONG num_busy_workers;
45
46 static struct list work_item_list = LIST_INIT(work_item_list);
47 static HANDLE work_item_event;
48
49 static RTL_CRITICAL_SECTION threadpool_cs;
50 static RTL_CRITICAL_SECTION_DEBUG critsect_debug =
51 {
52     0, 0, &threadpool_cs,
53     { &critsect_debug.ProcessLocksList, &critsect_debug.ProcessLocksList },
54     0, 0, { (DWORD_PTR)(__FILE__ ": threadpool_cs") }
55 };
56 static RTL_CRITICAL_SECTION threadpool_cs = { &critsect_debug, -1, 0, 0, 0, 0 };
57
58 static HANDLE compl_port = NULL;
59 static RTL_CRITICAL_SECTION threadpool_compl_cs;
60 static RTL_CRITICAL_SECTION_DEBUG critsect_compl_debug =
61 {
62     0, 0, &threadpool_compl_cs,
63     { &critsect_compl_debug.ProcessLocksList, &critsect_compl_debug.ProcessLocksList },
64     0, 0, { (DWORD_PTR)(__FILE__ ": threadpool_compl_cs") }
65 };
66 static RTL_CRITICAL_SECTION threadpool_compl_cs = { &critsect_compl_debug, -1, 0, 0, 0, 0 };
67
68 struct work_item
69 {
70     struct list entry;
71     PRTL_WORK_ITEM_ROUTINE function;
72     PVOID context;
73 };
74
75 static inline LONG interlocked_inc( PLONG dest )
76 {
77     return interlocked_xchg_add( dest, 1 ) + 1;
78 }
79
80 static inline LONG interlocked_dec( PLONG dest )
81 {
82     return interlocked_xchg_add( dest, -1 ) - 1;
83 }
84
85 static void WINAPI worker_thread_proc(void * param)
86 {
87     interlocked_inc(&num_workers);
88
89     /* free the work item memory sooner to reduce memory usage */
90     while (TRUE)
91     {
92         if (num_work_items > 0)
93         {
94             struct list *item;
95             RtlEnterCriticalSection(&threadpool_cs);
96             item = list_head(&work_item_list);
97             if (item)
98             {
99                 struct work_item *work_item_ptr = LIST_ENTRY(item, struct work_item, entry);
100                 struct work_item work_item;
101                 list_remove(&work_item_ptr->entry);
102                 interlocked_dec(&num_work_items);
103
104                 RtlLeaveCriticalSection(&threadpool_cs);
105
106                 work_item = *work_item_ptr;
107                 RtlFreeHeap(GetProcessHeap(), 0, work_item_ptr);
108
109                 TRACE("executing %p(%p)\n", work_item.function, work_item.context);
110
111                 interlocked_inc(&num_busy_workers);
112
113                 /* do the work */
114                 work_item.function(work_item.context);
115
116                 interlocked_dec(&num_busy_workers);
117             }
118             else
119                 RtlLeaveCriticalSection(&threadpool_cs);
120         }
121         else
122         {
123             NTSTATUS status;
124             LARGE_INTEGER timeout;
125             timeout.QuadPart = -(WORKER_TIMEOUT * (ULONGLONG)10000);
126             status = NtWaitForSingleObject(work_item_event, FALSE, &timeout);
127             if (status != STATUS_WAIT_0)
128                 break;
129         }
130     }
131
132     interlocked_dec(&num_workers);
133
134     RtlExitUserThread(0);
135
136     /* never reached */
137 }
138
139 static NTSTATUS add_work_item_to_queue(struct work_item *work_item)
140 {
141     NTSTATUS status;
142
143     RtlEnterCriticalSection(&threadpool_cs);
144     list_add_tail(&work_item_list, &work_item->entry);
145     num_work_items++;
146     RtlLeaveCriticalSection(&threadpool_cs);
147
148     if (!work_item_event)
149     {
150         HANDLE sem;
151         status = NtCreateSemaphore(&sem, SEMAPHORE_ALL_ACCESS, NULL, 1, INT_MAX);
152         if (interlocked_cmpxchg_ptr( &work_item_event, sem, 0 ))
153             NtClose(sem);  /* somebody beat us to it */
154     }
155     else
156         status = NtReleaseSemaphore(work_item_event, 1, NULL);
157
158     return status;
159 }
160
161 /***********************************************************************
162  *              RtlQueueWorkItem   (NTDLL.@)
163  *
164  * Queues a work item into a thread in the thread pool.
165  *
166  * PARAMS
167  *  Function [I] Work function to execute.
168  *  Context  [I] Context to pass to the work function when it is executed.
169  *  Flags    [I] Flags. See notes.
170  *
171  * RETURNS
172  *  Success: STATUS_SUCCESS.
173  *  Failure: Any NTSTATUS code.
174  *
175  * NOTES
176  *  Flags can be one or more of the following:
177  *|WT_EXECUTEDEFAULT - Executes the work item in a non-I/O worker thread.
178  *|WT_EXECUTEINIOTHREAD - Executes the work item in an I/O worker thread.
179  *|WT_EXECUTEINPERSISTENTTHREAD - Executes the work item in a thread that is persistent.
180  *|WT_EXECUTELONGFUNCTION - Hints that the execution can take a long time.
181  *|WT_TRANSFER_IMPERSONATION - Executes the function with the current access token.
182  */
183 NTSTATUS WINAPI RtlQueueWorkItem(PRTL_WORK_ITEM_ROUTINE Function, PVOID Context, ULONG Flags)
184 {
185     HANDLE thread;
186     NTSTATUS status;
187     struct work_item *work_item = RtlAllocateHeap(GetProcessHeap(), 0, sizeof(struct work_item));
188
189     if (!work_item)
190         return STATUS_NO_MEMORY;
191
192     work_item->function = Function;
193     work_item->context = Context;
194
195     if (Flags & ~WT_EXECUTELONGFUNCTION)
196         FIXME("Flags 0x%x not supported\n", Flags);
197
198     status = add_work_item_to_queue(work_item);
199
200     /* FIXME: tune this algorithm to not be as aggressive with creating threads
201      * if WT_EXECUTELONGFUNCTION isn't specified */
202     if ((status == STATUS_SUCCESS) &&
203         ((num_workers == 0) || (num_workers == num_busy_workers)))
204     {
205         status = RtlCreateUserThread( GetCurrentProcess(), NULL, FALSE,
206                                     NULL, 0, 0,
207                                     worker_thread_proc, NULL, &thread, NULL );
208         if (status == STATUS_SUCCESS)
209             NtClose( thread );
210
211         /* NOTE: we don't care if we couldn't create the thread if there is at
212          * least one other available to process the request */
213         if ((num_workers > 0) && (status != STATUS_SUCCESS))
214             status = STATUS_SUCCESS;
215     }
216
217     if (status != STATUS_SUCCESS)
218     {
219         RtlEnterCriticalSection(&threadpool_cs);
220
221         interlocked_dec(&num_work_items);
222         list_remove(&work_item->entry);
223         RtlFreeHeap(GetProcessHeap(), 0, work_item);
224
225         RtlLeaveCriticalSection(&threadpool_cs);
226
227         return status;
228     }
229
230     return STATUS_SUCCESS;
231 }
232
233 /***********************************************************************
234  * iocp_poller - get completion events and run callbacks
235  */
236 static DWORD CALLBACK iocp_poller(LPVOID Arg)
237 {
238     while( TRUE )
239     {
240         PRTL_OVERLAPPED_COMPLETION_ROUTINE callback;
241         LPVOID overlapped;
242         IO_STATUS_BLOCK iosb;
243         NTSTATUS res = NtRemoveIoCompletion( compl_port, (PULONG_PTR)&callback, (PULONG_PTR)&overlapped, &iosb, NULL );
244         if (res)
245         {
246             ERR("NtRemoveIoCompletion failed: 0x%x\n", res);
247         }
248         else
249         {
250             DWORD transferred = 0;
251             DWORD err = 0;
252
253             if (iosb.u.Status == STATUS_SUCCESS)
254                 transferred = iosb.Information;
255             else
256                 err = RtlNtStatusToDosError(iosb.u.Status);
257
258             callback( err, transferred, overlapped );
259         }
260     }
261     return 0;
262 }
263
264 /***********************************************************************
265  *              RtlSetIoCompletionCallback  (NTDLL.@)
266  *
267  * Binds a handle to a thread pool's completion port, and possibly
268  * starts a non-I/O thread to monitor this port and call functions back.
269  *
270  * PARAMS
271  *  FileHandle [I] Handle to bind to a completion port.
272  *  Function   [I] Callback function to call on I/O completions.
273  *  Flags      [I] Not used.
274  *
275  * RETURNS
276  *  Success: STATUS_SUCCESS.
277  *  Failure: Any NTSTATUS code.
278  *
279  */
280 NTSTATUS WINAPI RtlSetIoCompletionCallback(HANDLE FileHandle, PRTL_OVERLAPPED_COMPLETION_ROUTINE Function, ULONG Flags)
281 {
282     IO_STATUS_BLOCK iosb;
283     FILE_COMPLETION_INFORMATION info;
284
285     if (Flags) FIXME("Unknown value Flags=0x%x\n", Flags);
286
287     if (!compl_port)
288     {
289         NTSTATUS res = STATUS_SUCCESS;
290
291         RtlEnterCriticalSection(&threadpool_compl_cs);
292         if (!compl_port)
293         {
294             HANDLE cport;
295
296             res = NtCreateIoCompletion( &cport, IO_COMPLETION_ALL_ACCESS, NULL, 0 );
297             if (!res)
298             {
299                 /* FIXME native can start additional threads in case of e.g. hung callback function. */
300                 res = RtlQueueWorkItem( iocp_poller, NULL, WT_EXECUTEDEFAULT );
301                 if (!res)
302                     compl_port = cport;
303                 else
304                     NtClose( cport );
305             }
306         }
307         RtlLeaveCriticalSection(&threadpool_compl_cs);
308         if (res) return res;
309     }
310
311     info.CompletionPort = compl_port;
312     info.CompletionKey = (ULONG_PTR)Function;
313
314     return NtSetInformationFile( FileHandle, &iosb, &info, sizeof(info), FileCompletionInformation );
315 }
316
317 static inline PLARGE_INTEGER get_nt_timeout( PLARGE_INTEGER pTime, ULONG timeout )
318 {
319     if (timeout == INFINITE) return NULL;
320     pTime->QuadPart = (ULONGLONG)timeout * -10000;
321     return pTime;
322 }
323
324 struct wait_work_item
325 {
326     HANDLE Object;
327     HANDLE CancelEvent;
328     WAITORTIMERCALLBACK Callback;
329     PVOID Context;
330     ULONG Milliseconds;
331     ULONG Flags;
332     HANDLE CompletionEvent;
333     LONG DeleteCount;
334     BOOLEAN CallbackInProgress;
335 };
336
337 static void delete_wait_work_item(struct wait_work_item *wait_work_item)
338 {
339     NtClose( wait_work_item->CancelEvent );
340     RtlFreeHeap( GetProcessHeap(), 0, wait_work_item );
341 }
342
343 static DWORD CALLBACK wait_thread_proc(LPVOID Arg)
344 {
345     struct wait_work_item *wait_work_item = Arg;
346     NTSTATUS status;
347     BOOLEAN alertable = (wait_work_item->Flags & WT_EXECUTEINIOTHREAD) ? TRUE : FALSE;
348     HANDLE handles[2] = { wait_work_item->Object, wait_work_item->CancelEvent };
349     LARGE_INTEGER timeout;
350     HANDLE completion_event;
351
352     TRACE("\n");
353
354     while (TRUE)
355     {
356         status = NtWaitForMultipleObjects( 2, handles, FALSE, alertable,
357                                            get_nt_timeout( &timeout, wait_work_item->Milliseconds ) );
358         if (status == STATUS_WAIT_0 || status == STATUS_TIMEOUT)
359         {
360             BOOLEAN TimerOrWaitFired;
361
362             if (status == STATUS_WAIT_0)
363             {
364                 TRACE( "object %p signaled, calling callback %p with context %p\n",
365                     wait_work_item->Object, wait_work_item->Callback,
366                     wait_work_item->Context );
367                 TimerOrWaitFired = FALSE;
368             }
369             else
370             {
371                 TRACE( "wait for object %p timed out, calling callback %p with context %p\n",
372                     wait_work_item->Object, wait_work_item->Callback,
373                     wait_work_item->Context );
374                 TimerOrWaitFired = TRUE;
375             }
376             wait_work_item->CallbackInProgress = TRUE;
377             wait_work_item->Callback( wait_work_item->Context, TimerOrWaitFired );
378             wait_work_item->CallbackInProgress = FALSE;
379
380             if (wait_work_item->Flags & WT_EXECUTEONLYONCE)
381                 break;
382         }
383         else
384             break;
385     }
386
387     completion_event = wait_work_item->CompletionEvent;
388     if (completion_event) NtSetEvent( completion_event, NULL );
389
390     if (interlocked_inc( &wait_work_item->DeleteCount ) == 2 )
391         delete_wait_work_item( wait_work_item );
392
393     return 0;
394 }
395
396 /***********************************************************************
397  *              RtlRegisterWait   (NTDLL.@)
398  *
399  * Registers a wait for a handle to become signaled.
400  *
401  * PARAMS
402  *  NewWaitObject [I] Handle to the new wait object. Use RtlDeregisterWait() to free it.
403  *  Object   [I] Object to wait to become signaled.
404  *  Callback [I] Callback function to execute when the wait times out or the handle is signaled.
405  *  Context  [I] Context to pass to the callback function when it is executed.
406  *  Milliseconds [I] Number of milliseconds to wait before timing out.
407  *  Flags    [I] Flags. See notes.
408  *
409  * RETURNS
410  *  Success: STATUS_SUCCESS.
411  *  Failure: Any NTSTATUS code.
412  *
413  * NOTES
414  *  Flags can be one or more of the following:
415  *|WT_EXECUTEDEFAULT - Executes the work item in a non-I/O worker thread.
416  *|WT_EXECUTEINIOTHREAD - Executes the work item in an I/O worker thread.
417  *|WT_EXECUTEINPERSISTENTTHREAD - Executes the work item in a thread that is persistent.
418  *|WT_EXECUTELONGFUNCTION - Hints that the execution can take a long time.
419  *|WT_TRANSFER_IMPERSONATION - Executes the function with the current access token.
420  */
421 NTSTATUS WINAPI RtlRegisterWait(PHANDLE NewWaitObject, HANDLE Object,
422                                 RTL_WAITORTIMERCALLBACKFUNC Callback,
423                                 PVOID Context, ULONG Milliseconds, ULONG Flags)
424 {
425     struct wait_work_item *wait_work_item;
426     NTSTATUS status;
427
428     TRACE( "(%p, %p, %p, %p, %d, 0x%x)\n", NewWaitObject, Object, Callback, Context, Milliseconds, Flags );
429
430     wait_work_item = RtlAllocateHeap( GetProcessHeap(), 0, sizeof(*wait_work_item) );
431     if (!wait_work_item)
432         return STATUS_NO_MEMORY;
433
434     wait_work_item->Object = Object;
435     wait_work_item->Callback = Callback;
436     wait_work_item->Context = Context;
437     wait_work_item->Milliseconds = Milliseconds;
438     wait_work_item->Flags = Flags;
439     wait_work_item->CallbackInProgress = FALSE;
440     wait_work_item->DeleteCount = 0;
441     wait_work_item->CompletionEvent = NULL;
442
443     status = NtCreateEvent( &wait_work_item->CancelEvent, EVENT_ALL_ACCESS, NULL, NotificationEvent, FALSE );
444     if (status != STATUS_SUCCESS)
445     {
446         RtlFreeHeap( GetProcessHeap(), 0, wait_work_item );
447         return status;
448     }
449
450     status = RtlQueueWorkItem( wait_thread_proc, wait_work_item, Flags & ~WT_EXECUTEONLYONCE );
451     if (status != STATUS_SUCCESS)
452     {
453         delete_wait_work_item( wait_work_item );
454         return status;
455     }
456
457     *NewWaitObject = wait_work_item;
458     return status;
459 }
460
461 /***********************************************************************
462  *              RtlDeregisterWaitEx   (NTDLL.@)
463  *
464  * Cancels a wait operation and frees the resources associated with calling
465  * RtlRegisterWait().
466  *
467  * PARAMS
468  *  WaitObject [I] Handle to the wait object to free.
469  *
470  * RETURNS
471  *  Success: STATUS_SUCCESS.
472  *  Failure: Any NTSTATUS code.
473  */
474 NTSTATUS WINAPI RtlDeregisterWaitEx(HANDLE WaitHandle, HANDLE CompletionEvent)
475 {
476     struct wait_work_item *wait_work_item = WaitHandle;
477     NTSTATUS status = STATUS_SUCCESS;
478
479     TRACE( "(%p)\n", WaitHandle );
480
481     NtSetEvent( wait_work_item->CancelEvent, NULL );
482     if (wait_work_item->CallbackInProgress)
483     {
484         if (CompletionEvent != NULL)
485         {
486             if (CompletionEvent == INVALID_HANDLE_VALUE)
487             {
488                 status = NtCreateEvent( &CompletionEvent, EVENT_ALL_ACCESS, NULL, NotificationEvent, FALSE );
489                 if (status != STATUS_SUCCESS)
490                     return status;
491                 interlocked_xchg_ptr( &wait_work_item->CompletionEvent, CompletionEvent );
492                 if (wait_work_item->CallbackInProgress)
493                     NtWaitForSingleObject( CompletionEvent, FALSE, NULL );
494                 NtClose( CompletionEvent );
495             }
496             else
497             {
498                 interlocked_xchg_ptr( &wait_work_item->CompletionEvent, CompletionEvent );
499                 if (wait_work_item->CallbackInProgress)
500                     status = STATUS_PENDING;
501             }
502         }
503         else
504             status = STATUS_PENDING;
505     }
506
507     if (interlocked_inc( &wait_work_item->DeleteCount ) == 2 )
508     {
509         status = STATUS_SUCCESS;
510         delete_wait_work_item( wait_work_item );
511     }
512
513     return status;
514 }
515
516 /***********************************************************************
517  *              RtlDeregisterWait   (NTDLL.@)
518  *
519  * Cancels a wait operation and frees the resources associated with calling
520  * RtlRegisterWait().
521  *
522  * PARAMS
523  *  WaitObject [I] Handle to the wait object to free.
524  *
525  * RETURNS
526  *  Success: STATUS_SUCCESS.
527  *  Failure: Any NTSTATUS code.
528  */
529 NTSTATUS WINAPI RtlDeregisterWait(HANDLE WaitHandle)
530 {
531     return RtlDeregisterWaitEx(WaitHandle, NULL);
532 }
533
534
535 /************************** Timer Queue Impl **************************/
536
537 struct timer_queue;
538 struct queue_timer
539 {
540     struct timer_queue *q;
541     struct list entry;
542     ULONG runcount;             /* number of callbacks pending execution */
543     RTL_WAITORTIMERCALLBACKFUNC callback;
544     PVOID param;
545     DWORD period;
546     ULONG flags;
547     ULONGLONG expire;
548     BOOL destroy;      /* timer should be deleted; once set, never unset */
549     HANDLE event;      /* removal event */
550 };
551
552 struct timer_queue
553 {
554     RTL_CRITICAL_SECTION cs;
555     struct list timers;          /* sorted by expiration time */
556     BOOL quit;         /* queue should be deleted; once set, never unset */
557     HANDLE event;
558     HANDLE thread;
559 };
560
561 #define EXPIRE_NEVER (~(ULONGLONG) 0)
562
563 static void queue_remove_timer(struct queue_timer *t)
564 {
565     /* We MUST hold the queue cs while calling this function.  This ensures
566        that we cannot queue another callback for this timer.  The runcount
567        being zero makes sure we don't have any already queued.  */
568     struct timer_queue *q = t->q;
569
570     assert(t->runcount == 0);
571     assert(t->destroy);
572
573     list_remove(&t->entry);
574     if (t->event)
575         NtSetEvent(t->event, NULL);
576     RtlFreeHeap(GetProcessHeap(), 0, t);
577
578     if (q->quit && list_count(&q->timers) == 0)
579         NtSetEvent(q->event, NULL);
580 }
581
582 static void timer_cleanup_callback(struct queue_timer *t)
583 {
584     struct timer_queue *q = t->q;
585     RtlEnterCriticalSection(&q->cs);
586
587     assert(0 < t->runcount);
588     --t->runcount;
589
590     if (t->destroy && t->runcount == 0)
591         queue_remove_timer(t);
592
593     RtlLeaveCriticalSection(&q->cs);
594 }
595
596 static DWORD WINAPI timer_callback_wrapper(LPVOID p)
597 {
598     struct queue_timer *t = p;
599     t->callback(t->param, TRUE);
600     timer_cleanup_callback(t);
601     return 0;
602 }
603
604 static inline ULONGLONG queue_current_time(void)
605 {
606     LARGE_INTEGER now;
607     NtQuerySystemTime(&now);
608     return now.QuadPart / 10000;
609 }
610
611 static void queue_add_timer(struct queue_timer *t, ULONGLONG time,
612                             BOOL set_event)
613 {
614     /* We MUST hold the queue cs while calling this function.  */
615     struct timer_queue *q = t->q;
616     struct list *ptr = &q->timers;
617
618     assert(!q->quit || (t->destroy && time == EXPIRE_NEVER));
619
620     if (time != EXPIRE_NEVER)
621         LIST_FOR_EACH(ptr, &q->timers)
622         {
623             struct queue_timer *cur = LIST_ENTRY(ptr, struct queue_timer, entry);
624             if (time < cur->expire)
625                 break;
626         }
627     list_add_before(ptr, &t->entry);
628
629     t->expire = time;
630
631     /* If we insert at the head of the list, we need to expire sooner
632        than expected.  */
633     if (set_event && &t->entry == list_head(&q->timers))
634         NtSetEvent(q->event, NULL);
635 }
636
637 static inline void queue_move_timer(struct queue_timer *t, ULONGLONG time,
638                                     BOOL set_event)
639 {
640     /* We MUST hold the queue cs while calling this function.  */
641     list_remove(&t->entry);
642     queue_add_timer(t, time, set_event);
643 }
644
645 static void queue_timer_expire(struct timer_queue *q)
646 {
647     struct queue_timer *t = NULL;
648
649     RtlEnterCriticalSection(&q->cs);
650     if (list_head(&q->timers))
651     {
652         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
653         if (!t->destroy && t->expire <= queue_current_time())
654         {
655             ++t->runcount;
656             queue_move_timer(
657                 t, t->period ? queue_current_time() + t->period : EXPIRE_NEVER,
658                 FALSE);
659         }
660         else
661             t = NULL;
662     }
663     RtlLeaveCriticalSection(&q->cs);
664
665     if (t)
666     {
667         if (t->flags & WT_EXECUTEINTIMERTHREAD)
668             timer_callback_wrapper(t);
669         else
670         {
671             ULONG flags
672                 = (t->flags
673                    & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD
674                       | WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION));
675             NTSTATUS status = RtlQueueWorkItem(timer_callback_wrapper, t, flags);
676             if (status != STATUS_SUCCESS)
677                 timer_cleanup_callback(t);
678         }
679     }
680 }
681
682 static ULONG queue_get_timeout(struct timer_queue *q)
683 {
684     struct queue_timer *t;
685     ULONG timeout = INFINITE;
686
687     RtlEnterCriticalSection(&q->cs);
688     if (list_head(&q->timers))
689     {
690         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
691         assert(!t->destroy || t->expire == EXPIRE_NEVER);
692
693         if (t->expire != EXPIRE_NEVER)
694         {
695             ULONGLONG time = queue_current_time();
696             timeout = t->expire < time ? 0 : t->expire - time;
697         }
698     }
699     RtlLeaveCriticalSection(&q->cs);
700
701     return timeout;
702 }
703
704 static void WINAPI timer_queue_thread_proc(LPVOID p)
705 {
706     struct timer_queue *q = p;
707     ULONG timeout_ms;
708
709     timeout_ms = INFINITE;
710     for (;;)
711     {
712         LARGE_INTEGER timeout;
713         NTSTATUS status;
714         BOOL done = FALSE;
715
716         status = NtWaitForSingleObject(
717             q->event, FALSE, get_nt_timeout(&timeout, timeout_ms));
718
719         if (status == STATUS_WAIT_0)
720         {
721             /* There are two possible ways to trigger the event.  Either
722                we are quitting and the last timer got removed, or a new
723                timer got put at the head of the list so we need to adjust
724                our timeout.  */
725             RtlEnterCriticalSection(&q->cs);
726             if (q->quit && list_count(&q->timers) == 0)
727                 done = TRUE;
728             RtlLeaveCriticalSection(&q->cs);
729         }
730         else if (status == STATUS_TIMEOUT)
731             queue_timer_expire(q);
732
733         if (done)
734             break;
735
736         timeout_ms = queue_get_timeout(q);
737     }
738
739     NtClose(q->event);
740     RtlDeleteCriticalSection(&q->cs);
741     RtlFreeHeap(GetProcessHeap(), 0, q);
742 }
743
744 static void queue_destroy_timer(struct queue_timer *t)
745 {
746     /* We MUST hold the queue cs while calling this function.  */
747     t->destroy = TRUE;
748     if (t->runcount == 0)
749         /* Ensure a timer is promptly removed.  If callbacks are pending,
750            it will be removed after the last one finishes by the callback
751            cleanup wrapper.  */
752         queue_remove_timer(t);
753     else
754         /* Make sure no destroyed timer masks an active timer at the head
755            of the sorted list.  */
756         queue_move_timer(t, EXPIRE_NEVER, FALSE);
757 }
758
759 /***********************************************************************
760  *              RtlCreateTimerQueue   (NTDLL.@)
761  *
762  * Creates a timer queue object and returns a handle to it.
763  *
764  * PARAMS
765  *  NewTimerQueue [O] The newly created queue.
766  *
767  * RETURNS
768  *  Success: STATUS_SUCCESS.
769  *  Failure: Any NTSTATUS code.
770  */
771 NTSTATUS WINAPI RtlCreateTimerQueue(PHANDLE NewTimerQueue)
772 {
773     NTSTATUS status;
774     struct timer_queue *q = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *q);
775     if (!q)
776         return STATUS_NO_MEMORY;
777
778     RtlInitializeCriticalSection(&q->cs);
779     list_init(&q->timers);
780     q->quit = FALSE;
781     status = NtCreateEvent(&q->event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
782     if (status != STATUS_SUCCESS)
783     {
784         RtlFreeHeap(GetProcessHeap(), 0, q);
785         return status;
786     }
787     status = RtlCreateUserThread(GetCurrentProcess(), NULL, FALSE, NULL, 0, 0,
788                                  timer_queue_thread_proc, q, &q->thread, NULL);
789     if (status != STATUS_SUCCESS)
790     {
791         NtClose(q->event);
792         RtlFreeHeap(GetProcessHeap(), 0, q);
793         return status;
794     }
795
796     *NewTimerQueue = q;
797     return STATUS_SUCCESS;
798 }
799
800 /***********************************************************************
801  *              RtlDeleteTimerQueueEx   (NTDLL.@)
802  *
803  * Deletes a timer queue object.
804  *
805  * PARAMS
806  *  TimerQueue      [I] The timer queue to destroy.
807  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
808  *                      wait until all timers are finished firing before
809  *                      returning.  Otherwise, return immediately and set the
810  *                      event when all timers are done.
811  *
812  * RETURNS
813  *  Success: STATUS_SUCCESS if synchronous, STATUS_PENDING if not.
814  *  Failure: Any NTSTATUS code.
815  */
816 NTSTATUS WINAPI RtlDeleteTimerQueueEx(HANDLE TimerQueue, HANDLE CompletionEvent)
817 {
818     struct timer_queue *q = TimerQueue;
819     struct queue_timer *t, *temp;
820     HANDLE thread;
821     NTSTATUS status;
822
823     if (!q)
824         return STATUS_INVALID_HANDLE;
825
826     thread = q->thread;
827
828     RtlEnterCriticalSection(&q->cs);
829     q->quit = TRUE;
830     if (list_head(&q->timers))
831         /* When the last timer is removed, it will signal the timer thread to
832            exit...  */
833         LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
834             queue_destroy_timer(t);
835     else
836         /* However if we have none, we must do it ourselves.  */
837         NtSetEvent(q->event, NULL);
838     RtlLeaveCriticalSection(&q->cs);
839
840     if (CompletionEvent == INVALID_HANDLE_VALUE)
841     {
842         NtWaitForSingleObject(thread, FALSE, NULL);
843         status = STATUS_SUCCESS;
844     }
845     else
846     {
847         if (CompletionEvent)
848         {
849             FIXME("asynchronous return on completion event unimplemented\n");
850             NtWaitForSingleObject(thread, FALSE, NULL);
851             NtSetEvent(CompletionEvent, NULL);
852         }
853         status = STATUS_PENDING;
854     }
855
856     NtClose(thread);
857     return status;
858 }
859
860 static struct timer_queue *default_timer_queue;
861
862 static struct timer_queue *get_timer_queue(HANDLE TimerQueue)
863 {
864     if (TimerQueue)
865         return TimerQueue;
866     else
867     {
868         if (!default_timer_queue)
869         {
870             HANDLE q;
871             NTSTATUS status = RtlCreateTimerQueue(&q);
872             if (status == STATUS_SUCCESS)
873             {
874                 PVOID p = interlocked_cmpxchg_ptr(
875                     (void **) &default_timer_queue, q, NULL);
876                 if (p)
877                     /* Got beat to the punch.  */
878                     RtlDeleteTimerQueueEx(p, NULL);
879             }
880         }
881         return default_timer_queue;
882     }
883 }
884
885 /***********************************************************************
886  *              RtlCreateTimer   (NTDLL.@)
887  *
888  * Creates a new timer associated with the given queue.
889  *
890  * PARAMS
891  *  NewTimer   [O] The newly created timer.
892  *  TimerQueue [I] The queue to hold the timer.
893  *  Callback   [I] The callback to fire.
894  *  Parameter  [I] The argument for the callback.
895  *  DueTime    [I] The delay, in milliseconds, before first firing the
896  *                 timer.
897  *  Period     [I] The period, in milliseconds, at which to fire the timer
898  *                 after the first callback.  If zero, the timer will only
899  *                 fire once.  It still needs to be deleted with
900  *                 RtlDeleteTimer.
901  * Flags       [I] Flags controling the execution of the callback.  In
902  *                 addition to the WT_* thread pool flags (see
903  *                 RtlQueueWorkItem), WT_EXECUTEINTIMERTHREAD and
904  *                 WT_EXECUTEONLYONCE are supported.
905  *
906  * RETURNS
907  *  Success: STATUS_SUCCESS.
908  *  Failure: Any NTSTATUS code.
909  */
910 NTSTATUS WINAPI RtlCreateTimer(PHANDLE NewTimer, HANDLE TimerQueue,
911                                RTL_WAITORTIMERCALLBACKFUNC Callback,
912                                PVOID Parameter, DWORD DueTime, DWORD Period,
913                                ULONG Flags)
914 {
915     NTSTATUS status;
916     struct queue_timer *t;
917     struct timer_queue *q = get_timer_queue(TimerQueue);
918     if (!q)
919         return STATUS_NO_MEMORY;
920
921     t = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *t);
922     if (!t)
923         return STATUS_NO_MEMORY;
924
925     t->q = q;
926     t->runcount = 0;
927     t->callback = Callback;
928     t->param = Parameter;
929     t->period = Period;
930     t->flags = Flags;
931     t->destroy = FALSE;
932     t->event = NULL;
933
934     status = STATUS_SUCCESS;
935     RtlEnterCriticalSection(&q->cs);
936     if (q->quit)
937         status = STATUS_INVALID_HANDLE;
938     else
939         queue_add_timer(t, queue_current_time() + DueTime, TRUE);
940     RtlLeaveCriticalSection(&q->cs);
941
942     if (status == STATUS_SUCCESS)
943         *NewTimer = t;
944     else
945         RtlFreeHeap(GetProcessHeap(), 0, t);
946
947     return status;
948 }
949
950 /***********************************************************************
951  *              RtlUpdateTimer   (NTDLL.@)
952  *
953  * Changes the time at which a timer expires.
954  *
955  * PARAMS
956  *  TimerQueue [I] The queue that holds the timer.
957  *  Timer      [I] The timer to update.
958  *  DueTime    [I] The delay, in milliseconds, before next firing the timer.
959  *  Period     [I] The period, in milliseconds, at which to fire the timer
960  *                 after the first callback.  If zero, the timer will not
961  *                 refire once.  It still needs to be deleted with
962  *                 RtlDeleteTimer.
963  *
964  * RETURNS
965  *  Success: STATUS_SUCCESS.
966  *  Failure: Any NTSTATUS code.
967  */
968 NTSTATUS WINAPI RtlUpdateTimer(HANDLE TimerQueue, HANDLE Timer,
969                                DWORD DueTime, DWORD Period)
970 {
971     struct queue_timer *t = Timer;
972     struct timer_queue *q = t->q;
973
974     RtlEnterCriticalSection(&q->cs);
975     /* Can't change a timer if it was once-only or destroyed.  */
976     if (t->expire != EXPIRE_NEVER)
977     {
978         t->period = Period;
979         queue_move_timer(t, queue_current_time() + DueTime, TRUE);
980     }
981     RtlLeaveCriticalSection(&q->cs);
982
983     return STATUS_SUCCESS;
984 }
985
986 /***********************************************************************
987  *              RtlDeleteTimer   (NTDLL.@)
988  *
989  * Cancels a timer-queue timer.
990  *
991  * PARAMS
992  *  TimerQueue      [I] The queue that holds the timer.
993  *  Timer           [I] The timer to update.
994  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
995  *                      wait until the timer is finished firing all pending
996  *                      callbacks before returning.  Otherwise, return
997  *                      immediately and set the timer is done.
998  *
999  * RETURNS
1000  *  Success: STATUS_SUCCESS if the timer is done, STATUS_PENDING if not,
1001              or if the completion event is NULL.
1002  *  Failure: Any NTSTATUS code.
1003  */
1004 NTSTATUS WINAPI RtlDeleteTimer(HANDLE TimerQueue, HANDLE Timer,
1005                                HANDLE CompletionEvent)
1006 {
1007     struct queue_timer *t = Timer;
1008     struct timer_queue *q;
1009     NTSTATUS status = STATUS_PENDING;
1010     HANDLE event = NULL;
1011
1012     if (!Timer)
1013         return STATUS_INVALID_PARAMETER_1;
1014     q = t->q;
1015     if (CompletionEvent == INVALID_HANDLE_VALUE)
1016         status = NtCreateEvent(&event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
1017     else if (CompletionEvent)
1018         event = CompletionEvent;
1019
1020     RtlEnterCriticalSection(&q->cs);
1021     t->event = event;
1022     if (t->runcount == 0 && event)
1023         status = STATUS_SUCCESS;
1024     queue_destroy_timer(t);
1025     RtlLeaveCriticalSection(&q->cs);
1026
1027     if (CompletionEvent == INVALID_HANDLE_VALUE && event)
1028     {
1029         if (status == STATUS_PENDING)
1030             NtWaitForSingleObject(event, FALSE, NULL);
1031         NtClose(event);
1032     }
1033
1034     return status;
1035 }