git.oblomov.eu Git - wine/blob - 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 }