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     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_count(&q->timers) == 0)
 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;
 609     NtQuerySystemTime(&now);
 610     return now.QuadPart / 10000;
 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         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
 655         if (!t->destroy && t->expire <= queue_current_time())
 656         {
 657             ++t->runcount;
 658             queue_move_timer(
 659                 t, t->period ? queue_current_time() + t->period : EXPIRE_NEVER,
 660                 FALSE);
 661         }
 662         else
 663             t = NULL;
 664     }
 665     RtlLeaveCriticalSection(&q->cs);
 666
 667     if (t)
 668     {
 669         if (t->flags & WT_EXECUTEINTIMERTHREAD)
 670             timer_callback_wrapper(t);
 671         else
 672         {
 673             ULONG flags
 674                 = (t->flags
 675                    & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD
 676                       | WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION));
 677             NTSTATUS status = RtlQueueWorkItem(timer_callback_wrapper, t, flags);
 678             if (status != STATUS_SUCCESS)
 679                 timer_cleanup_callback(t);
 680         }
 681     }
 682 }
 683
 684 static ULONG queue_get_timeout(struct timer_queue *q)
 685 {
 686     struct queue_timer *t;
 687     ULONG timeout = INFINITE;
 688
 689     RtlEnterCriticalSection(&q->cs);
 690     if (list_head(&q->timers))
 691     {
 692         t = LIST_ENTRY(list_head(&q->timers), struct queue_timer, entry);
 693         assert(!t->destroy || t->expire == EXPIRE_NEVER);
 694
 695         if (t->expire != EXPIRE_NEVER)
 696         {
 697             ULONGLONG time = queue_current_time();
 698             timeout = t->expire < time ? 0 : t->expire - time;
 699         }
 700     }
 701     RtlLeaveCriticalSection(&q->cs);
 702
 703     return timeout;
 704 }
 705
 706 static void WINAPI timer_queue_thread_proc(LPVOID p)
 707 {
 708     struct timer_queue *q = p;
 709     ULONG timeout_ms;
 710
 711     timeout_ms = INFINITE;
 712     for (;;)
 713     {
 714         LARGE_INTEGER timeout;
 715         NTSTATUS status;
 716         BOOL done = FALSE;
 717
 718         status = NtWaitForSingleObject(
 719             q->event, FALSE, get_nt_timeout(&timeout, timeout_ms));
 720
 721         if (status == STATUS_WAIT_0)
 722         {
 723             /* There are two possible ways to trigger the event.  Either
 724                we are quitting and the last timer got removed, or a new
 725                timer got put at the head of the list so we need to adjust
 726                our timeout.  */
 727             RtlEnterCriticalSection(&q->cs);
 728             if (q->quit && list_count(&q->timers) == 0)
 729                 done = TRUE;
 730             RtlLeaveCriticalSection(&q->cs);
 731         }
 732         else if (status == STATUS_TIMEOUT)
 733             queue_timer_expire(q);
 734
 735         if (done)
 736             break;
 737
 738         timeout_ms = queue_get_timeout(q);
 739     }
 740
 741     NtClose(q->event);
 742     RtlDeleteCriticalSection(&q->cs);
 743     RtlFreeHeap(GetProcessHeap(), 0, q);
 744 }
 745
 746 static void queue_destroy_timer(struct queue_timer *t)
 747 {
 748     /* We MUST hold the queue cs while calling this function.  */
 749     t->destroy = TRUE;
 750     if (t->runcount == 0)
 751         /* Ensure a timer is promptly removed.  If callbacks are pending,
 752            it will be removed after the last one finishes by the callback
 753            cleanup wrapper.  */
 754         queue_remove_timer(t);
 755     else
 756         /* Make sure no destroyed timer masks an active timer at the head
 757            of the sorted list.  */
 758         queue_move_timer(t, EXPIRE_NEVER, FALSE);
 759 }
 760
 761 /***********************************************************************
 762  *              RtlCreateTimerQueue   (NTDLL.@)
 763  *
 764  * Creates a timer queue object and returns a handle to it.
 765  *
 766  * PARAMS
 767  *  NewTimerQueue [O] The newly created queue.
 768  *
 769  * RETURNS
 770  *  Success: STATUS_SUCCESS.
 771  *  Failure: Any NTSTATUS code.
 772  */
 773 NTSTATUS WINAPI RtlCreateTimerQueue(PHANDLE NewTimerQueue)
 774 {
 775     NTSTATUS status;
 776     struct timer_queue *q = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *q);
 777     if (!q)
 778         return STATUS_NO_MEMORY;
 779
 780     RtlInitializeCriticalSection(&q->cs);
 781     list_init(&q->timers);
 782     q->quit = FALSE;
 783     status = NtCreateEvent(&q->event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
 784     if (status != STATUS_SUCCESS)
 785     {
 786         RtlFreeHeap(GetProcessHeap(), 0, q);
 787         return status;
 788     }
 789     status = RtlCreateUserThread(GetCurrentProcess(), NULL, FALSE, NULL, 0, 0,
 790                                  timer_queue_thread_proc, q, &q->thread, NULL);
 791     if (status != STATUS_SUCCESS)
 792     {
 793         NtClose(q->event);
 794         RtlFreeHeap(GetProcessHeap(), 0, q);
 795         return status;
 796     }
 797
 798     *NewTimerQueue = q;
 799     return STATUS_SUCCESS;
 800 }
 801
 802 /***********************************************************************
 803  *              RtlDeleteTimerQueueEx   (NTDLL.@)
 804  *
 805  * Deletes a timer queue object.
 806  *
 807  * PARAMS
 808  *  TimerQueue      [I] The timer queue to destroy.
 809  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
 810  *                      wait until all timers are finished firing before
 811  *                      returning.  Otherwise, return immediately and set the
 812  *                      event when all timers are done.
 813  *
 814  * RETURNS
 815  *  Success: STATUS_SUCCESS if synchronous, STATUS_PENDING if not.
 816  *  Failure: Any NTSTATUS code.
 817  */
 818 NTSTATUS WINAPI RtlDeleteTimerQueueEx(HANDLE TimerQueue, HANDLE CompletionEvent)
 819 {
 820     struct timer_queue *q = TimerQueue;
 821     struct queue_timer *t, *temp;
 822     HANDLE thread;
 823     NTSTATUS status;
 824
 825     if (!q)
 826         return STATUS_INVALID_HANDLE;
 827
 828     thread = q->thread;
 829
 830     RtlEnterCriticalSection(&q->cs);
 831     q->quit = TRUE;
 832     if (list_head(&q->timers))
 833         /* When the last timer is removed, it will signal the timer thread to
 834            exit...  */
 835         LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
 836             queue_destroy_timer(t);
 837     else
 838         /* However if we have none, we must do it ourselves.  */
 839         NtSetEvent(q->event, NULL);
 840     RtlLeaveCriticalSection(&q->cs);
 841
 842     if (CompletionEvent == INVALID_HANDLE_VALUE)
 843     {
 844         NtWaitForSingleObject(thread, FALSE, NULL);
 845         status = STATUS_SUCCESS;
 846     }
 847     else
 848     {
 849         if (CompletionEvent)
 850         {
 851             FIXME("asynchronous return on completion event unimplemented\n");
 852             NtWaitForSingleObject(thread, FALSE, NULL);
 853             NtSetEvent(CompletionEvent, NULL);
 854         }
 855         status = STATUS_PENDING;
 856     }
 857
 858     NtClose(thread);
 859     return status;
 860 }
 861
 862 static struct timer_queue *default_timer_queue;
 863
 864 static struct timer_queue *get_timer_queue(HANDLE TimerQueue)
 865 {
 866     if (TimerQueue)
 867         return TimerQueue;
 868     else
 869     {
 870         if (!default_timer_queue)
 871         {
 872             HANDLE q;
 873             NTSTATUS status = RtlCreateTimerQueue(&q);
 874             if (status == STATUS_SUCCESS)
 875             {
 876                 PVOID p = interlocked_cmpxchg_ptr(
 877                     (void **) &default_timer_queue, q, NULL);
 878                 if (p)
 879                     /* Got beat to the punch.  */
 880                     RtlDeleteTimerQueueEx(p, NULL);
 881             }
 882         }
 883         return default_timer_queue;
 884     }
 885 }
 886
 887 /***********************************************************************
 888  *              RtlCreateTimer   (NTDLL.@)
 889  *
 890  * Creates a new timer associated with the given queue.
 891  *
 892  * PARAMS
 893  *  NewTimer   [O] The newly created timer.
 894  *  TimerQueue [I] The queue to hold the timer.
 895  *  Callback   [I] The callback to fire.
 896  *  Parameter  [I] The argument for the callback.
 897  *  DueTime    [I] The delay, in milliseconds, before first firing the
 898  *                 timer.
 899  *  Period     [I] The period, in milliseconds, at which to fire the timer
 900  *                 after the first callback.  If zero, the timer will only
 901  *                 fire once.  It still needs to be deleted with
 902  *                 RtlDeleteTimer.
 903  * Flags       [I] Flags controling the execution of the callback.  In
 904  *                 addition to the WT_* thread pool flags (see
 905  *                 RtlQueueWorkItem), WT_EXECUTEINTIMERTHREAD and
 906  *                 WT_EXECUTEONLYONCE are supported.
 907  *
 908  * RETURNS
 909  *  Success: STATUS_SUCCESS.
 910  *  Failure: Any NTSTATUS code.
 911  */
 912 NTSTATUS WINAPI RtlCreateTimer(PHANDLE NewTimer, HANDLE TimerQueue,
 913                                RTL_WAITORTIMERCALLBACKFUNC Callback,
 914                                PVOID Parameter, DWORD DueTime, DWORD Period,
 915                                ULONG Flags)
 916 {
 917     NTSTATUS status;
 918     struct queue_timer *t;
 919     struct timer_queue *q = get_timer_queue(TimerQueue);
 920     if (!q)
 921         return STATUS_NO_MEMORY;
 922
 923     t = RtlAllocateHeap(GetProcessHeap(), 0, sizeof *t);
 924     if (!t)
 925         return STATUS_NO_MEMORY;
 926
 927     t->q = q;
 928     t->runcount = 0;
 929     t->callback = Callback;
 930     t->param = Parameter;
 931     t->period = Period;
 932     t->flags = Flags;
 933     t->destroy = FALSE;
 934     t->event = NULL;
 935
 936     status = STATUS_SUCCESS;
 937     RtlEnterCriticalSection(&q->cs);
 938     if (q->quit)
 939         status = STATUS_INVALID_HANDLE;
 940     else
 941         queue_add_timer(t, queue_current_time() + DueTime, TRUE);
 942     RtlLeaveCriticalSection(&q->cs);
 943
 944     if (status == STATUS_SUCCESS)
 945         *NewTimer = t;
 946     else
 947         RtlFreeHeap(GetProcessHeap(), 0, t);
 948
 949     return status;
 950 }
 951
 952 /***********************************************************************
 953  *              RtlUpdateTimer   (NTDLL.@)
 954  *
 955  * Changes the time at which a timer expires.
 956  *
 957  * PARAMS
 958  *  TimerQueue [I] The queue that holds the timer.
 959  *  Timer      [I] The timer to update.
 960  *  DueTime    [I] The delay, in milliseconds, before next firing the timer.
 961  *  Period     [I] The period, in milliseconds, at which to fire the timer
 962  *                 after the first callback.  If zero, the timer will not
 963  *                 refire once.  It still needs to be deleted with
 964  *                 RtlDeleteTimer.
 965  *
 966  * RETURNS
 967  *  Success: STATUS_SUCCESS.
 968  *  Failure: Any NTSTATUS code.
 969  */
 970 NTSTATUS WINAPI RtlUpdateTimer(HANDLE TimerQueue, HANDLE Timer,
 971                                DWORD DueTime, DWORD Period)
 972 {
 973     struct queue_timer *t = Timer;
 974     struct timer_queue *q = t->q;
 975
 976     RtlEnterCriticalSection(&q->cs);
 977     /* Can't change a timer if it was once-only or destroyed.  */
 978     if (t->expire != EXPIRE_NEVER)
 979     {
 980         t->period = Period;
 981         queue_move_timer(t, queue_current_time() + DueTime, TRUE);
 982     }
 983     RtlLeaveCriticalSection(&q->cs);
 984
 985     return STATUS_SUCCESS;
 986 }
 987
 988 /***********************************************************************
 989  *              RtlDeleteTimer   (NTDLL.@)
 990  *
 991  * Cancels a timer-queue timer.
 992  *
 993  * PARAMS
 994  *  TimerQueue      [I] The queue that holds the timer.
 995  *  Timer           [I] The timer to update.
 996  *  CompletionEvent [I] If NULL, return immediately.  If INVALID_HANDLE_VALUE,
 997  *                      wait until the timer is finished firing all pending
 998  *                      callbacks before returning.  Otherwise, return
 999  *                      immediately and set the timer is done.
1000  *
1001  * RETURNS
1002  *  Success: STATUS_SUCCESS if the timer is done, STATUS_PENDING if not,
1003              or if the completion event is NULL.
1004  *  Failure: Any NTSTATUS code.
1005  */
1006 NTSTATUS WINAPI RtlDeleteTimer(HANDLE TimerQueue, HANDLE Timer,
1007                                HANDLE CompletionEvent)
1008 {
1009     struct queue_timer *t = Timer;
1010     struct timer_queue *q;
1011     NTSTATUS status = STATUS_PENDING;
1012     HANDLE event = NULL;
1013
1014     if (!Timer)
1015         return STATUS_INVALID_PARAMETER_1;
1016     q = t->q;
1017     if (CompletionEvent == INVALID_HANDLE_VALUE)
1018         status = NtCreateEvent(&event, EVENT_ALL_ACCESS, NULL, SynchronizationEvent, FALSE);
1019     else if (CompletionEvent)
1020         event = CompletionEvent;
1021
1022     RtlEnterCriticalSection(&q->cs);
1023     t->event = event;
1024     if (t->runcount == 0 && event)
1025         status = STATUS_SUCCESS;
1026     queue_destroy_timer(t);
1027     RtlLeaveCriticalSection(&q->cs);
1028
1029     if (CompletionEvent == INVALID_HANDLE_VALUE && event)
1030     {
1031         if (status == STATUS_PENDING)
1032             NtWaitForSingleObject(event, FALSE, NULL);
1033         NtClose(event);
1034     }
1035
1036     return status;
1037 }