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) != 0;
 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     Flags = Flags & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD |
 451                      WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION);
 452     status = RtlQueueWorkItem( wait_thread_proc, wait_work_item, Flags );
 453     if (status != STATUS_SUCCESS)
 454     {
 455         delete_wait_work_item( wait_work_item );
 456         return status;
 457     }
 458
 459     *NewWaitObject = wait_work_item;
 460     return status;
 461 }
 462
 463 /***********************************************************************
 464  *              RtlDeregisterWaitEx   (NTDLL.@)
 465  *
 466  * Cancels a wait operation and frees the resources associated with calling
 467  * RtlRegisterWait().
 468  *
 469  * PARAMS
 470  *  WaitObject [I] Handle to the wait object to free.
 471  *
 472  * RETURNS
 473  *  Success: STATUS_SUCCESS.
 474  *  Failure: Any NTSTATUS code.
 475  */
 476 NTSTATUS WINAPI RtlDeregisterWaitEx(HANDLE WaitHandle, HANDLE CompletionEvent)
 477 {
 478     struct wait_work_item *wait_work_item = WaitHandle;
 479     NTSTATUS status = STATUS_SUCCESS;
 480
 481     TRACE( "(%p)\n", WaitHandle );
 482
 483     NtSetEvent( wait_work_item->CancelEvent, NULL );
 484     if (wait_work_item->CallbackInProgress)
 485     {
 486         if (CompletionEvent != NULL)
 487         {
 488             if (CompletionEvent == INVALID_HANDLE_VALUE)
 489             {
 490                 status = NtCreateEvent( &CompletionEvent, EVENT_ALL_ACCESS, NULL, NotificationEvent, FALSE );
 491                 if (status != STATUS_SUCCESS)
 492                     return status;
 493                 interlocked_xchg_ptr( &wait_work_item->CompletionEvent, CompletionEvent );
 494                 if (wait_work_item->CallbackInProgress)
 495                     NtWaitForSingleObject( CompletionEvent, FALSE, NULL );
 496                 NtClose( CompletionEvent );
 497             }
 498             else
 499             {
 500                 interlocked_xchg_ptr( &wait_work_item->CompletionEvent, CompletionEvent );
 501                 if (wait_work_item->CallbackInProgress)
 502                     status = STATUS_PENDING;
 503             }
 504         }
 505         else
 506             status = STATUS_PENDING;
 507     }
 508
 509     if (interlocked_inc( &wait_work_item->DeleteCount ) == 2 )
 510     {
 511         status = STATUS_SUCCESS;
 512         delete_wait_work_item( wait_work_item );
 513     }
 514
 515     return status;
 516 }
 517
 518 /***********************************************************************
 519  *              RtlDeregisterWait   (NTDLL.@)
 520  *
 521  * Cancels a wait operation and frees the resources associated with calling
 522  * RtlRegisterWait().
 523  *
 524  * PARAMS
 525  *  WaitObject [I] Handle to the wait object to free.
 526  *
 527  * RETURNS
 528  *  Success: STATUS_SUCCESS.
 529  *  Failure: Any NTSTATUS code.
 530  */
 531 NTSTATUS WINAPI RtlDeregisterWait(HANDLE WaitHandle)
 532 {
 533     return RtlDeregisterWaitEx(WaitHandle, NULL);
 534 }
 535
 536
 537 /************************** Timer Queue Impl **************************/
 538
 539 struct timer_queue;
 540 struct queue_timer
 541 {
 542     struct timer_queue *q;
 543     struct list entry;
 544     ULONG runcount;             /* number of callbacks pending execution */
 545     RTL_WAITORTIMERCALLBACKFUNC callback;
 546     PVOID param;
 547     DWORD period;
 548     ULONG flags;
 549     ULONGLONG expire;
 550     BOOL destroy;      /* timer should be deleted; once set, never unset */
 551     HANDLE event;      /* removal event */
 552 };
 553
 554 struct timer_queue
 555 {
 556     RTL_CRITICAL_SECTION cs;
 557     struct list timers;          /* sorted by expiration time */
 558     BOOL quit;         /* queue should be deleted; once set, never unset */
 559     HANDLE event;
 560     HANDLE thread;
 561 };
 562
 563 #define EXPIRE_NEVER (~(ULONGLONG) 0)
 564
 565 static void queue_remove_timer(struct queue_timer *t)
 566 {
 567     /* We MUST hold the queue cs while calling this function.  This ensures
 568        that we cannot queue another callback for this timer.  The runcount
 569        being zero makes sure we don't have any already queued.  */
 570     struct timer_queue *q = t->q;
 571
 572     assert(t->runcount == 0);
 573     assert(t->destroy);
 574
 575     list_remove(&t->entry);
 576     if (t->event)
 577         NtSetEvent(t->event, NULL);
 578     RtlFreeHeap(GetProcessHeap(), 0, t);
 579
 580     if (q->quit && list_empty(&q->timers))
 581         NtSetEvent(q->event, NULL);
 582 }
 583
 584 static void timer_cleanup_callback(struct queue_timer *t)
 585 {
 586     struct timer_queue *q = t->q;
 587     RtlEnterCriticalSection(&q->cs);
 588
 589     assert(0 < t->runcount);
 590     --t->runcount;
 591
 592     if (t->destroy && t->runcount == 0)
 593         queue_remove_timer(t);
 594
 595     RtlLeaveCriticalSection(&q->cs);
 596 }
 597
 598 static DWORD WINAPI timer_callback_wrapper(LPVOID p)
 599 {
 600     struct queue_timer *t = p;
 601     t->callback(t->param, TRUE);
 602     timer_cleanup_callback(t);
 603     return 0;
 604 }
 605
 606 static inline ULONGLONG queue_current_time(void)
 607 {
 608     LARGE_INTEGER now, freq;
 609     NtQueryPerformanceCounter(&now, &freq);
 610     return now.QuadPart * 1000 / freq.QuadPart;
 611 }
 612
 613 static void queue_add_timer(struct queue_timer *t, ULONGLONG time,
 614                             BOOL set_event)
 615 {
 616     /* We MUST hold the queue cs while calling this function.  */
 617     struct timer_queue *q = t->q;
 618     struct list *ptr = &q->timers;
 619
 620     assert(!q->quit || (t->destroy && time == EXPIRE_NEVER));
 621
 622     if (time != EXPIRE_NEVER)
 623         LIST_FOR_EACH(ptr, &q->timers)
 624         {
 625             struct queue_timer *cur = LIST_ENTRY(ptr, struct queue_timer, entry);
 626             if (time < cur->expire)
 627                 break;
 628         }
 629     list_add_before(ptr, &t->entry);
 630
 631     t->expire = time;
 632
 633     /* If we insert at the head of the list, we need to expire sooner
 634        than expected.  */
 635     if (set_event && &t->entry == list_head(&q->timers))
 636         NtSetEvent(q->event, NULL);
 637 }
 638
 639 static inline void queue_move_timer(struct queue_timer *t, ULONGLONG time,
 640                                     BOOL set_event)
 641 {
 642     /* We MUST hold the queue cs while calling this function.  */
 643     list_remove(&t->entry);
 644     queue_add_timer(t, time, set_event);
 645 }
 646
 647 static void queue_timer_expire(struct timer_queue *q)
 648 {
 649     struct queue_timer *t = NULL;
 650
 651     RtlEnterCriticalSection(&q->cs);
 652     if (list_head(&q->timers))
 653     {
 654         ULONGLONG now, next;
 655         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
 656         if (!t->destroy && t->expire <= ((now = queue_current_time())))
 657         {
 658             ++t->runcount;
 659             if (t->period)
 660             {
 661                 next = t->expire + t->period;
 662                 /* avoid trigger cascade if overloaded / hibernated */
 663                 if (next < now)
 664                     next = now + t->period;
 665             }
 666             else
 667                 next = EXPIRE_NEVER;
 668             queue_move_timer(t, next, FALSE);
 669         }
 670         else
 671             t = NULL;
 672     }
 673     RtlLeaveCriticalSection(&q->cs);
 674
 675     if (t)
 676     {
 677         if (t->flags & WT_EXECUTEINTIMERTHREAD)
 678             timer_callback_wrapper(t);
 679         else
 680         {
 681             ULONG flags
 682                 = (t->flags
 683                    & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD
 684                       | WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION));
 685             NTSTATUS status = RtlQueueWorkItem(timer_callback_wrapper, t, flags);
 686             if (status != STATUS_SUCCESS)
 687                 timer_cleanup_callback(t);
 688         }
 689     }
 690 }
 691
 692 static ULONG queue_get_timeout(struct timer_queue *q)
 693 {
 694     struct queue_timer *t;
 695     ULONG timeout = INFINITE;
 696
 697     RtlEnterCriticalSection(&q->cs);
 698     if (list_head(&q->timers))
 699     {
 700         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
 701         assert(!t->destroy || t->expire == EXPIRE_NEVER);
 702
 703         if (t->expire != EXPIRE_NEVER)
 704         {
 705             ULONGLONG time = queue_current_time();
 706             timeout = t->expire < time ? 0 : t->expire - time;
 707         }
 708     }
 709     RtlLeaveCriticalSection(&q->cs);
 710
 711     return timeout;
 712 }
 713
 714 static void WINAPI timer_queue_thread_proc(LPVOID p)
 715 {
 716     struct timer_queue *q = p;
 717     ULONG timeout_ms;
 718
 719     timeout_ms = INFINITE;
 720     for (;;)
 721     {
 722         LARGE_INTEGER timeout;
 723         NTSTATUS status;
 724         BOOL done = FALSE;
 725
 726         status = NtWaitForSingleObject(
 727             q->event, FALSE, get_nt_timeout(&timeout, timeout_ms));
 728
 729         if (status == STATUS_WAIT_0)
 730         {
 731             /* There are two possible ways to trigger the event.  Either
 732                we are quitting and the last timer got removed, or a new
 733                timer got put at the head of the list so we need to adjust
 734                our timeout.  */
 735             RtlEnterCriticalSection(&q->cs);
 736             if (q->quit && list_empty(&q->timers))
 737                 done = TRUE;
 738             RtlLeaveCriticalSection(&q->cs);
 739         }
 740         else if (status == STATUS_TIMEOUT)
 741             queue_timer_expire(q);
 742
 743         if (done)
 744             break;
 745
 746         timeout_ms = queue_get_timeout(q);
 747     }
 748
 749     NtClose(q->event);
 750     RtlDeleteCriticalSection(&q->cs);
 751     RtlFreeHeap(GetProcessHeap(), 0, q);
 752 }
 753
 754 static void queue_destroy_timer(struct queue_timer *t)
 755 {
 756     /* We MUST hold the queue cs while calling this function.  */
 757     t->destroy = TRUE;
 758     if (t->runcount == 0)
 759         /* Ensure a timer is promptly removed.  If callbacks are pending,
 760            it will be removed after the last one finishes by the callback
 761            cleanup wrapper.  */
 762         queue_remove_timer(t);
 763     else
 764         /* Make sure no destroyed timer masks an active timer at the head
 765            of the sorted list.  */
 766         queue_move_timer(t, EXPIRE_NEVER, FALSE);
 767 }
 768
 769 /***********************************************************************
 770  *              RtlCreateTimerQueue   (NTDLL.@)
 771  *
 772  * Creates a timer queue object and returns a handle to it.
 773  *
 774  * PARAMS
 775  *  NewTimerQueue [O] The newly created queue.
 776  *
 777  * RETURNS
 778  *  Success: STATUS_SUCCESS.
 779  *  Failure: Any NTSTATUS code.
 780  */
 781 NTSTATUS WINAPI RtlCreateTimerQueue(PHANDLE NewTimerQueue)
 782 {
 783     NTSTATUS status;
 784     struct timer_queue *q = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *q);
 785     if (!q)
 786         return STATUS_NO_MEMORY;
 787
 788     RtlInitializeCriticalSection(&q->cs);
 789     list_init(&q->timers);
 790     q->quit = FALSE;
 791     status = NtCreateEvent(&q->event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
 792     if (status != STATUS_SUCCESS)
 793     {
 794         RtlFreeHeap(GetProcessHeap(), 0, q);
 795         return status;
 796     }
 797     status = RtlCreateUserThread(GetCurrentProcess(), NULL, FALSE, NULL, 0, 0,
 798                                  timer_queue_thread_proc, q, &q->thread, NULL);
 799     if (status != STATUS_SUCCESS)
 800     {
 801         NtClose(q->event);
 802         RtlFreeHeap(GetProcessHeap(), 0, q);
 803         return status;
 804     }
 805
 806     *NewTimerQueue = q;
 807     return STATUS_SUCCESS;
 808 }
 809
 810 /***********************************************************************
 811  *              RtlDeleteTimerQueueEx   (NTDLL.@)
 812  *
 813  * Deletes a timer queue object.
 814  *
 815  * PARAMS
 816  *  TimerQueue      [I] The timer queue to destroy.
 817  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
 818  *                      wait until all timers are finished firing before
 819  *                      returning.  Otherwise, return immediately and set the
 820  *                      event when all timers are done.
 821  *
 822  * RETURNS
 823  *  Success: STATUS_SUCCESS if synchronous, STATUS_PENDING if not.
 824  *  Failure: Any NTSTATUS code.
 825  */
 826 NTSTATUS WINAPI RtlDeleteTimerQueueEx(HANDLE TimerQueue, HANDLE CompletionEvent)
 827 {
 828     struct timer_queue *q = TimerQueue;
 829     struct queue_timer *t, *temp;
 830     HANDLE thread;
 831     NTSTATUS status;
 832
 833     if (!q)
 834         return STATUS_INVALID_HANDLE;
 835
 836     thread = q->thread;
 837
 838     RtlEnterCriticalSection(&q->cs);
 839     q->quit = TRUE;
 840     if (list_head(&q->timers))
 841         /* When the last timer is removed, it will signal the timer thread to
 842            exit...  */
 843         LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
 844             queue_destroy_timer(t);
 845     else
 846         /* However if we have none, we must do it ourselves.  */
 847         NtSetEvent(q->event, NULL);
 848     RtlLeaveCriticalSection(&q->cs);
 849
 850     if (CompletionEvent == INVALID_HANDLE_VALUE)
 851     {
 852         NtWaitForSingleObject(thread, FALSE, NULL);
 853         status = STATUS_SUCCESS;
 854     }
 855     else
 856     {
 857         if (CompletionEvent)
 858         {
 859             FIXME("asynchronous return on completion event unimplemented\n");
 860             NtWaitForSingleObject(thread, FALSE, NULL);
 861             NtSetEvent(CompletionEvent, NULL);
 862         }
 863         status = STATUS_PENDING;
 864     }
 865
 866     NtClose(thread);
 867     return status;
 868 }
 869
 870 static struct timer_queue *default_timer_queue;
 871
 872 static struct timer_queue *get_timer_queue(HANDLE TimerQueue)
 873 {
 874     if (TimerQueue)
 875         return TimerQueue;
 876     else
 877     {
 878         if (!default_timer_queue)
 879         {
 880             HANDLE q;
 881             NTSTATUS status = RtlCreateTimerQueue(&q);
 882             if (status == STATUS_SUCCESS)
 883             {
 884                 PVOID p = interlocked_cmpxchg_ptr(
 885                     (void **) &default_timer_queue, q, NULL);
 886                 if (p)
 887                     /* Got beat to the punch.  */
 888                     RtlDeleteTimerQueueEx(p, NULL);
 889             }
 890         }
 891         return default_timer_queue;
 892     }
 893 }
 894
 895 /***********************************************************************
 896  *              RtlCreateTimer   (NTDLL.@)
 897  *
 898  * Creates a new timer associated with the given queue.
 899  *
 900  * PARAMS
 901  *  NewTimer   [O] The newly created timer.
 902  *  TimerQueue [I] The queue to hold the timer.
 903  *  Callback   [I] The callback to fire.
 904  *  Parameter  [I] The argument for the callback.
 905  *  DueTime    [I] The delay, in milliseconds, before first firing the
 906  *                 timer.
 907  *  Period     [I] The period, in milliseconds, at which to fire the timer
 908  *                 after the first callback.  If zero, the timer will only
 909  *                 fire once.  It still needs to be deleted with
 910  *                 RtlDeleteTimer.
 911  * Flags       [I] Flags controlling the execution of the callback.  In
 912  *                 addition to the WT_* thread pool flags (see
 913  *                 RtlQueueWorkItem), WT_EXECUTEINTIMERTHREAD and
 914  *                 WT_EXECUTEONLYONCE are supported.
 915  *
 916  * RETURNS
 917  *  Success: STATUS_SUCCESS.
 918  *  Failure: Any NTSTATUS code.
 919  */
 920 NTSTATUS WINAPI RtlCreateTimer(PHANDLE NewTimer, HANDLE TimerQueue,
 921                                RTL_WAITORTIMERCALLBACKFUNC Callback,
 922                                PVOID Parameter, DWORD DueTime, DWORD Period,
 923                                ULONG Flags)
 924 {
 925     NTSTATUS status;
 926     struct queue_timer *t;
 927     struct timer_queue *q = get_timer_queue(TimerQueue);
 928     if (!q)
 929         return STATUS_NO_MEMORY;
 930
 931     t = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *t);
 932     if (!t)
 933         return STATUS_NO_MEMORY;
 934
 935     t->q = q;
 936     t->runcount = 0;
 937     t->callback = Callback;
 938     t->param = Parameter;
 939     t->period = Period;
 940     t->flags = Flags;
 941     t->destroy = FALSE;
 942     t->event = NULL;
 943
 944     status = STATUS_SUCCESS;
 945     RtlEnterCriticalSection(&q->cs);
 946     if (q->quit)
 947         status = STATUS_INVALID_HANDLE;
 948     else
 949         queue_add_timer(t, queue_current_time() + DueTime, TRUE);
 950     RtlLeaveCriticalSection(&q->cs);
 951
 952     if (status == STATUS_SUCCESS)
 953         *NewTimer = t;
 954     else
 955         RtlFreeHeap(GetProcessHeap(), 0, t);
 956
 957     return status;
 958 }
 959
 960 /***********************************************************************
 961  *              RtlUpdateTimer   (NTDLL.@)
 962  *
 963  * Changes the time at which a timer expires.
 964  *
 965  * PARAMS
 966  *  TimerQueue [I] The queue that holds the timer.
 967  *  Timer      [I] The timer to update.
 968  *  DueTime    [I] The delay, in milliseconds, before next firing the timer.
 969  *  Period     [I] The period, in milliseconds, at which to fire the timer
 970  *                 after the first callback.  If zero, the timer will not
 971  *                 refire once.  It still needs to be deleted with
 972  *                 RtlDeleteTimer.
 973  *
 974  * RETURNS
 975  *  Success: STATUS_SUCCESS.
 976  *  Failure: Any NTSTATUS code.
 977  */
 978 NTSTATUS WINAPI RtlUpdateTimer(HANDLE TimerQueue, HANDLE Timer,
 979                                DWORD DueTime, DWORD Period)
 980 {
 981     struct queue_timer *t = Timer;
 982     struct timer_queue *q = t->q;
 983
 984     RtlEnterCriticalSection(&q->cs);
 985     /* Can't change a timer if it was once-only or destroyed.  */
 986     if (t->expire != EXPIRE_NEVER)
 987     {
 988         t->period = Period;
 989         queue_move_timer(t, queue_current_time() + DueTime, TRUE);
 990     }
 991     RtlLeaveCriticalSection(&q->cs);
 992
 993     return STATUS_SUCCESS;
 994 }
 995
 996 /***********************************************************************
 997  *              RtlDeleteTimer   (NTDLL.@)
 998  *
 999  * Cancels a timer-queue timer.
1000  *
1001  * PARAMS
1002  *  TimerQueue      [I] The queue that holds the timer.
1003  *  Timer           [I] The timer to update.
1004  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
1005  *                      wait until the timer is finished firing all pending
1006  *                      callbacks before returning.  Otherwise, return
1007  *                      immediately and set the timer is done.
1008  *
1009  * RETURNS
1010  *  Success: STATUS_SUCCESS if the timer is done, STATUS_PENDING if not,
1011              or if the completion event is NULL.
1012  *  Failure: Any NTSTATUS code.
1013  */
1014 NTSTATUS WINAPI RtlDeleteTimer(HANDLE TimerQueue, HANDLE Timer,
1015                                HANDLE CompletionEvent)
1016 {
1017     struct queue_timer *t = Timer;
1018     struct timer_queue *q;
1019     NTSTATUS status = STATUS_PENDING;
1020     HANDLE event = NULL;
1021
1022     if (!Timer)
1023         return STATUS_INVALID_PARAMETER_1;
1024     q = t->q;
1025     if (CompletionEvent == INVALID_HANDLE_VALUE)
1026     {
1027         status = NtCreateEvent(&event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
1028         if (status == STATUS_SUCCESS)
1029             status = STATUS_PENDING;
1030     }
1031     else if (CompletionEvent)
1032         event = CompletionEvent;
1033
1034     RtlEnterCriticalSection(&q->cs);
1035     t->event = event;
1036     if (t->runcount == 0 && event)
1037         status = STATUS_SUCCESS;
1038     queue_destroy_timer(t);
1039     RtlLeaveCriticalSection(&q->cs);
1040
1041     if (CompletionEvent == INVALID_HANDLE_VALUE && event)
1042     {
1043         if (status == STATUS_PENDING)
1044         {
1045             NtWaitForSingleObject(event, FALSE, NULL);
1046             status = STATUS_SUCCESS;
1047         }
1048         NtClose(event);
1049     }
1050
1051     return status;
1052 }