Re: [8/11] kernel32: Implement the timer queue thread.

[Rob Shearman]

2008/7/19 Dan Hipschman :
> This patch implements the timer thread, running callbacks, cleaning up
> timers, and all that good stuff.  It should be very efficient, using mostly
> atomic operations and one critical section for thread safety.

It would be more efficient for queues with large numbers of timers if
you used the approach used by server/fd.c of keeping a list of timers
sorted by when they next expire to avoid having to search through the
entire list every time a timer expires.
> I designed
> it with thread-safety in mind, and once I got it working the way I wanted,
> ran the tests in a loop a few thousand times while I ate lunch.  I also did
> this with the following patches and never once got a single error, hang or
> crash.
>
> It punts on some integer-wrapping issues.  If someone runs their wineserver
> for 49 days they may run into that issue.  I just thought it would distract
> from the main content and wanted to finish everything else before I thought
> about it.
>
> Note that the one todo_wine that got added in the tests wasn't because
> something broke, it's just that the function never ran before.
>
> dlls/kernel32/sync.c       |  214 ++++++++++++++++++++++++++++++++++++++++----
>  dlls/kernel32/tests/sync.c |   42 +++++++--
>  2 files changed, 231 insertions(+), 25 deletions(-)

As mentioned previously, this should be implemented in ntdll.
> diff --git a/dlls/kernel32/sync.c b/dlls/kernel32/sync.c
> index 8085077..4df5b44 100644
> --- a/dlls/kernel32/sync.c
> +++ b/dlls/kernel32/sync.c
> @@ -21,6 +21,7 @@
>  #include "config.h"
>  #include "wine/port.h"
>
> +#include <assert.h>
>  #include <string.h>
>  #ifdef HAVE_UNISTD_H
>  # include <unistd.h>
> @@ -1043,17 +1044,145 @@ BOOL WINAPI CancelWaitableTimer( HANDLE handle )
>  }
>
> +struct timer_queue;
>  struct queue_timer
>  {
> - struct timer_queue *q;
> struct list entry;
> - LONG runcount;              /* number of callbacks pending execution */
> - WAITORTIMERCALLBACK callback;
> - PVOID param;
> - DWORD period;
> - ULONG flags;
> - DWORD expire;
> - BOOL die;          /* timer should be deleted; once set, never unset */

"destroy" or "delete" might be a better name for this field.
> };
>
> struct timer_queue
>  {
>     RTL_CRITICAL_SECTION cs;
>     struct list timers;
> - struct queue_timer *next;   /* the next timer to expire */
> - BOOL quit;         /* queue should be deleted; once set, never unset */
> - DWORD timeout;              /* when the next timer expires */
> - HANDLE event;
> - HANDLE thread;
>
> };
>
> +static void queue_remove_timer(struct timer_queue *q, struct queue_timer *t)
> +{
> - /* We MUST hold the queue cs while calling this function.  This ensures
> -
>   that we cannot queue another callback for this timer.  The runcount
> -
>   being zero makes sure we don't have any already queued.  */
> - assert(t->runcount == 0);
> - assert(t->die);
> - list_remove(&t->entry);
> - if (q->next == t)
> -
>    q->next = NULL;
> - HeapFree(GetProcessHeap(), 0, t);
>
> +}
> -
>
> +static DWORD WINAPI timer_callback_wrapper(LPVOID p)
> +{
> - struct queue_timer *t = (struct queue_timer *) p;

This cast is unnecessary.
> - struct timer_queue *q = t->q;
> -
> - t->callback(t->param, TRUE);
> -
> - RtlEnterCriticalSection(&q->cs);
> - InterlockedDecrement(&t->runcount);

Since you only ever access runcount while inside a critical section
then you don't need to use interlocked functions to modify it.
> - if (t->die && t->runcount == 0)
> - {
> -
>    queue_remove_timer(q, t);
> -
>    /* Wake up the cleanup loop so it can see if all timers are gone.  */
> -
>    if (q->quit)
> -
>        SetEvent(q->event);
> - }
> - RtlLeaveCriticalSection(&q->cs);
> -
> - return 0;
>
> +}
> -
>
> +static void queue_timer_expire(struct queue_timer *t)
> +{
> - /* We MUST hold the queue cs while calling this function.  */
> - if (!t->die)
> - {
> -
>    ULONG flags =
> -
>        t->flags & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD
> -
>                    | WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION);
> -
>    InterlockedIncrement(&t->runcount);
> -
>    QueueUserWorkItem(timer_callback_wrapper, t, flags);

You should check the return value and undo the incrementing of
t->runcount if it failed. However, you're also calling
QueueUserWorkItem inside a critical section so you're imposing a lock
ordering on the loader lock. This may cause a deadlock that may or may
not exist on Windows if a timer queue function is called from an
application's DllMain.
> - }
> -
> - if (t->period)
> - {
> -
>    /* FIXME: Solve this, here or in timer_queue_update.  */
> -
>    DWORD tick = GetTickCount();
> -
>    t->expire = tick + t->period;
> -
>    if (t->expire < tick)
> -
>        ERR("next expiration wrapped\n");
> - }
> - else
> -
>    t->die = TRUE;
>
> +}
> -
>
> +static void timer_queue_update(struct timer_queue *q)
> +{
> - /* We MUST hold the queue cs while calling this function.  */
> - struct queue_timer *t, *temp, *next = NULL;
> - DWORD tick, time = ~(DWORD) 0;

This cast is unnecessary is you use "~0U" instead.
> -
> - LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
> -
>    if (t->die)
> -
>    {
> -
>        if (t->runcount == 0)
> -
>            queue_remove_timer(q, t);
> -
>    }
> -
>    else if (t->expire < time)
> -
>    {
> -
>        time = t->expire;
> -
>        next = t;
> -
>    }
> -
> - tick = GetTickCount();
> - q->timeout = next ? (time < tick ? 0 : time - tick) : INFINITE;
> - q->next = next;
>
> +}
> -
>
> +static DWORD WINAPI timer_queue_thread_proc(LPVOID p)
> +{
> - struct timer_queue *q = p;
> - BOOL done;
> -
> - while (!q->quit)
> - {
> -
>    DWORD ret = WaitForSingleObject(q->event, q->timeout);
> -
>    RtlEnterCriticalSection(&q->cs);
> -
>    if (ret == WAIT_TIMEOUT && q->next)
> -
>        queue_timer_expire(q->next);
> -
>    timer_queue_update(q);
> -
>    RtlLeaveCriticalSection(&q->cs);
> - }
> -
> - done = FALSE;
> - while (!done)
> - {
> -
>    RtlEnterCriticalSection(&q->cs);
> -
>    timer_queue_update(q);
> -
>    if (list_count(&q->timers) == 0)
> -
>        done = TRUE;
> -
>    RtlLeaveCriticalSection(&q->cs);
> -
>    if (!done)
> -
>        WaitForSingleObject(q->event, INFINITE);
> - }
> -
> - CloseHandle(q->event);
> - CloseHandle(q->thread);
> - HeapFree(GetProcessHeap(), 0, q);
> - return 0;
>
> +}
> -
>
> /***********************************************************************
> -
>       CreateTimerQueue  (KERNEL32.@)
>
> */
> @@ -1065,15 +1194,27 @@ HANDLE WINAPI CreateTimerQueue(void)
>         SetLastError(ERROR_NOT_ENOUGH_MEMORY);
>         return NULL;
>     }
> - RtlInitializeCriticalSection(&q->cs);
>   list_init(&q->timers);
> - return q;
>
> -}
> - q->next = NULL;
> - q->quit = FALSE;
> - q->timeout = INFINITE;
> - q->event = CreateEventW(NULL, FALSE, FALSE, NULL);
> - if (!q->event)
> - {
> -
>    HeapFree(GetProcessHeap(), 0, q);
> -
>    return NULL;
> - }
> - q->thread = CreateThread(NULL, 0, timer_queue_thread_proc, q, 0, NULL);
> - if (!q->thread)
> - {
> -
>    CloseHandle(q->event);
> -
>    HeapFree(GetProcessHeap(), 0, q);
> -
>    return NULL;
> - }

It would be better to use a thread pool thread for processing timer
queue since it can be reused when the timer queue is destroyed. It
might then also be better to only start the timer queue thread when
there are timers to process and also release the timer queue thread
back to the thread pool when the last timer is removed from the queue.

Also, have you thought about using one thread for all timer queues?
This might not be appropriate for WT_EXECUTEINTIMERTHREAD timers, but
should improve the performance of the process as a whole without
affecting other timers.
> -static void queue_remove_timer(struct timer_queue *q, struct queue_timer *t)
> -{
> - list_remove(&t->entry);
> - HeapFree(GetProcessHeap(), 0, t);
> - return q;
>
> }
>
> /***********************************************************************
> @@ -1085,22 +1226,32 @@ BOOL WINAPI DeleteTimerQueueEx(HANDLE TimerQueue, HANDLE CompletionEvent)
>     struct queue_timer *t, *temp;
>     BOOL ret;
> - RtlEnterCriticalSection(&q->cs);
> - LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
> -
>    t->die = TRUE;
> - q->quit = TRUE;
> - RtlLeaveCriticalSection(&q->cs);
> - SetEvent(q->event);
> - if (CompletionEvent == INVALID_HANDLE_VALUE)
>   {
>       ret = TRUE;
> -
>    WaitForSingleObject(q->thread, INFINITE);

What if timer_queue_thread_proc exits before you reach here? q->thread
will now be invalid (and could be re-used by another thread in the
mean time). Another way of looking at it is that you don't own q after
the critical section where q->quit is set.
> }
> else
> {
> -
>    if (CompletionEvent)
> -
>    {
> -
>        /* FIXME: This should add the event to a list of events in the
> -
>           queue that it will signal when done.  */
> -
>        FIXME("returning and signaling events unimplemented; waiting instead\n");
> -
>        WaitForSingleObject(q->thread, INFINITE);
> -
>        SetEvent(CompletionEvent);
> -
>    }
>   ret = FALSE;
>   SetLastError(ERROR_IO_PENDING);
> }
> - RtlEnterCriticalSection(&q->cs);
> - LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
> -
>    queue_remove_timer(q, t);
> - RtlLeaveCriticalSection(&q->cs);
> -
> - HeapFree(GetProcessHeap(), 0, q);
> return ret;
>
> }
>
> @@ -1123,19 +1274,50 @@ BOOL WINAPI CreateTimerQueueTimer( PHANDLE phNewTimer, HANDLE TimerQueue,
>  {
>     struct timer_queue *q = TimerQueue;
>     struct queue_timer *t = HeapAlloc(GetProcessHeap(), 0, sizeof *t);
> - BOOL ret;
> - if (!t)
>   {
>       SetLastError(ERROR_NOT_ENOUGH_MEMORY);
>       return FALSE;
>   }
> - FIXME(": Timer expiration unimplemented\n");
> - t->q = q;
> - t->runcount = 0;
> - t->callback = Callback;
> - t->param = Parameter;
> - t->period = Period;
> - t->flags = Flags;
> - if (Flags & WT_EXECUTEINTIMERTHREAD)
> -
>    FIXME("WT_EXECUTEINTIMERTHREAD unimplemented\n");

If you use an expire list in a local variable then you won't need
locking when processing the expired timers and so this will be trivial
to implement.
> -
>
> {
> -
>    /* FIXME: Solve this, here or in timer_queue_update.  */
> -
>    DWORD tick = GetTickCount();
> -
>    t->expire = tick + DueTime;
> -
>    if (t->expire < tick)
> -
>        ERR("due time wrapped\n");
> -
>
> }
> -
>
> t->die = FALSE;
> -
>
> ret = TRUE;
> RtlEnterCriticalSection(&q->cs);
> - list_add_tail(&q->timers, &t->entry);
> - if (q->quit)
> -
>    ret = FALSE;
> - else
> -
>    list_add_tail(&q->timers, &t->entry);
> RtlLeaveCriticalSection(&q->cs);
> - *phNewTimer = t;
> - return TRUE;
> - if (ret)
> - {
> -
>    SetEvent(q->event);
> -
>    *phNewTimer = t;
> - }
> - else
> - {
> -
>    SetLastError(ERROR_INVALID_HANDLE);
> -
>    HeapFree(GetProcessHeap(), 0, t);
> - }
> -
> - return ret;
>
> }
>
> /***********************************************************************

Quite a few comments, but the patches are of a good general quality,
so well done.

[8/11] kernel32: Implement the timer queue thread.

[Dan Hipschman]

Thanks for these especially good comments, Rob!

On Sat, Jul 19, 2008 at 07:08:17PM +0100, Rob Shearman wrote:
> 2008/7/19 Dan Hipschman :
> > This patch implements the timer thread, running callbacks, cleaning up
> > timers, and all that good stuff.  It should be very efficient, using mostly
> > atomic operations and one critical section for thread safety.
>
> It would be more efficient for queues with large numbers of timers if
> you used the approach used by server/fd.c of keeping a list of timers
> sorted by when they next expire to avoid having to search through the
> entire list every time a timer expires.

The answer to most of your questions is, because I was trying to start
simple.  I'll look into this, though.
> > +static void queue_timer_expire(struct queue_timer *t)
> > +{
> > - /* We MUST hold the queue cs while calling this function.  */
> > - if (!t->die)
> > - {
> > -
> >    ULONG flags =
> > -
> >        t->flags & (WT_EXECUTEINIOTHREAD | WT_EXECUTEINPERSISTENTTHREAD
> > -
> >                    | WT_EXECUTELONGFUNCTION | WT_TRANSFER_IMPERSONATION);
> > -
> >    InterlockedIncrement(&t->runcount);
> > -
> >    QueueUserWorkItem(timer_callback_wrapper, t, flags);
>
> You should check the return value and undo the incrementing of
> t->runcount if it failed. However, you're also calling
> QueueUserWorkItem inside a critical section so you're imposing a lock
> ordering on the loader lock. This may cause a deadlock that may or may
> not exist on Windows if a timer queue function is called from an
> application's DllMain.

Thanks for telling me about this.  It should be safe to move
QueueUserWorkItem outside the CS.  I'll think about it later.
> It would be better to use a thread pool thread for processing timer
> queue since it can be reused when the timer queue is destroyed. It
> might then also be better to only start the timer queue thread when
> there are timers to process and also release the timer queue thread
> back to the thread pool when the last timer is removed from the queue.
>
> Also, have you thought about using one thread for all timer queues?
> This might not be appropriate for WT_EXECUTEINTIMERTHREAD timers, but
> should improve the performance of the process as a whole without
> affecting other timers.

Yes, I thought about these, but again, trying to keep it simple...
> > @@ -1085,22 +1226,32 @@ BOOL WINAPI DeleteTimerQueueEx(HANDLE TimerQueue, HANDLE CompletionEvent)
> >     struct queue_timer *t, *temp;
> >     BOOL ret;
> > - RtlEnterCriticalSection(&q->cs);
> > - LIST_FOR_EACH_ENTRY_SAFE(t, temp, &q->timers, struct queue_timer, entry)
> > -
> >    t->die = TRUE;
> > - q->quit = TRUE;
> > - RtlLeaveCriticalSection(&q->cs);
> > - SetEvent(q->event);
> > - if (CompletionEvent == INVALID_HANDLE_VALUE)
> >   {
> >       ret = TRUE;
> > -
> >    WaitForSingleObject(q->thread, INFINITE);
>
> What if timer_queue_thread_proc exits before you reach here? q->thread
> will now be invalid (and could be re-used by another thread in the
> mean time). Another way of looking at it is that you don't own q after
> the critical section where q->quit is set.

This is a great catch.  I utterly missed this.  Maybe the easiest fix is
to dup the thread handle into a local.  I'll look for a cleaner approach
as well.
> If you use an expire list in a local variable then you won't need
> locking when processing the expired timers and so this will be trivial
> to implement.

I'll take another look.
> Quite a few comments, but the patches are of a good general quality,
> so well done.

Thanks for taking the time to go over this so thoroughly.  Thanks, Hans,
for the comments as well; I'll check out GetTickCount64.

Dan