From 5b085e54a51322522ce8d38d3139228f035a9bf4 Mon Sep 17 00:00:00 2001 From: rpj Date: Mon, 11 Apr 2005 07:27:56 +0000 Subject: pthread_once post-cancel starvation solution --- pthread_once.c | 577 ++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 343 insertions(+), 234 deletions(-) (limited to 'pthread_once.c') diff --git a/pthread_once.c b/pthread_once.c index 1c0e01f..0a8c45e 100644 --- a/pthread_once.c +++ b/pthread_once.c @@ -1,234 +1,343 @@ -/* - * pthread_once.c - * - * Description: - * This translation unit implements miscellaneous thread functions. - * - * -------------------------------------------------------------------------- - * - * Pthreads-win32 - POSIX Threads Library for Win32 - * Copyright(C) 1998 John E. Bossom - * Copyright(C) 1999,2005 Pthreads-win32 contributors - * - * Contact Email: rpj@callisto.canberra.edu.au - * - * The current list of contributors is contained - * in the file CONTRIBUTORS included with the source - * code distribution. The list can also be seen at the - * following World Wide Web location: - * http://sources.redhat.com/pthreads-win32/contributors.html - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library in the file COPYING.LIB; - * if not, write to the Free Software Foundation, Inc., - * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#include "pthread.h" -#include "implement.h" - - -static void -ptw32_once_init_routine_cleanup(void * arg) -{ - pthread_once_t * once_control = (pthread_once_t *) arg; - - (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_CANCELLED); - (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started, (LONG)PTW32_FALSE); - - EnterCriticalSection(&ptw32_once_event_lock); - if (once_control->event) - { - /* - * There are waiters, wake some up - * We're deliberately not using PulseEvent. It's iffy, and deprecated. - */ - SetEvent(once_control->event); - } - LeaveCriticalSection(&ptw32_once_event_lock); -} - - -int -pthread_once (pthread_once_t * once_control, void (*init_routine) (void)) - /* - * ------------------------------------------------------ - * DOCPUBLIC - * If any thread in a process with a once_control parameter - * makes a call to pthread_once(), the first call will summon - * the init_routine(), but subsequent calls will not. The - * once_control parameter determines whether the associated - * initialization routine has been called. The init_routine() - * is complete upon return of pthread_once(). - * This function guarantees that one and only one thread - * executes the initialization routine, init_routine when - * access is controlled by the pthread_once_t control - * key. - * - * pthread_once() is not a cancelation point, but the init_routine - * can be. If it's cancelled then the effect on the once_control is - * as if pthread_once had never been entered. - * - * - * PARAMETERS - * once_control - * pointer to an instance of pthread_once_t - * - * init_routine - * pointer to an initialization routine - * - * - * DESCRIPTION - * See above. - * - * RESULTS - * 0 success, - * EINVAL once_control or init_routine is NULL - * - * ------------------------------------------------------ - */ -{ - int result; - - if (once_control == NULL || init_routine == NULL) - { - - result = EINVAL; - goto FAIL0; - - } - else - { - result = 0; - } - - while (!(InterlockedExchangeAdd((LPLONG)&once_control->state, 0L) /* Atomic Read */ - & (LONG)PTW32_ONCE_DONE)) - { - if (!PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started, (LONG)PTW32_TRUE)) - { - /* - * Clear residual state from a cancelled init_routine - * (and DONE still hasn't been set of course). - */ - if (PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_CLEAR) - & PTW32_ONCE_CANCELLED) - { - /* - * The previous initter was cancelled. - * We now have a new initter (us) and we need to make the rest wait again. - */ - EnterCriticalSection(&ptw32_once_event_lock); - if (once_control->event) - { - ResetEvent(once_control->event); - } - LeaveCriticalSection(&ptw32_once_event_lock); - - /* - * Any threads entering the wait section and getting out again before - * the CANCELLED state can be cleared and the event is reset will, at worst, just go - * around again or, if they suspend and we (the initter) completes before they resume, - * they will see state == DONE and leave immediately. - */ - } - - pthread_cleanup_push(ptw32_once_init_routine_cleanup, (void *) once_control); - (*init_routine)(); - pthread_cleanup_pop(0); - - (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_DONE); - - /* - * we didn't create the event. - * it is only there if there is someone waiting - */ - EnterCriticalSection(&ptw32_once_event_lock); - if (once_control->event) - { - SetEvent(once_control->event); - } - LeaveCriticalSection(&ptw32_once_event_lock); - } - else - { - /* - * wait for init. - * while waiting, create an event to wait on - */ - - EnterCriticalSection(&ptw32_once_event_lock); - once_control->eventUsers++; - - /* - * RE CANCELLATION: - * If we are the first thread after the initter thread, and the init_routine is cancelled - * while we're suspended at this point in the code:- - * - state will not get set to PTW32_ONCE_DONE; - * - cleanup will not see an event and cannot set it; - * - therefore, we will eventually resume, create an event and wait on it, maybe forever; - * Remedy: cleanup must set state == CANCELLED before checking for an event, so that - * we will see it and avoid waiting (as for state == DONE). We will go around again and - * we may become the initter. - * If we are still the only other thread when we get to the end of this block, we will - * have closed the event (good). If another thread beats us to be initter, then we will - * re-enter here (good). In case the old event is reused, the event is always reset by - * the new initter after clearing the CANCELLED state, causing any threads that are - * cycling around the loop to wait again. - */ - - if (!once_control->event) - { - once_control->event = CreateEvent(NULL, PTW32_TRUE, PTW32_FALSE, NULL); - } - LeaveCriticalSection(&ptw32_once_event_lock); - - /* - * check 'state' again in case the initting thread has finished or cancelled - * and left before seeing that there was an event to trigger. - * (Now that the event IS created, if init gets finished AFTER this, - * then the event handle is guaranteed to be seen and triggered). - */ - - if (!InterlockedExchangeAdd((LPLONG)&once_control->state, 0L)) /* Atomic Read */ - { - /* Neither DONE nor CANCELLED */ - (void) WaitForSingleObject(once_control->event, INFINITE); - } - - /* last one out shut off the lights */ - EnterCriticalSection(&ptw32_once_event_lock); - if (0 == --once_control->eventUsers) - { - /* we were last */ - CloseHandle(once_control->event); - once_control->event = 0; - } - LeaveCriticalSection(&ptw32_once_event_lock); - } - } - - - /* - * Fall through Intentionally - */ - - /* - * ------------ - * Failure Code - * ------------ - */ -FAIL0: - return (result); - -} /* pthread_once */ +/* + * pthread_once.c + * + * Description: + * This translation unit implements miscellaneous thread functions. + * + * -------------------------------------------------------------------------- + * + * Pthreads-win32 - POSIX Threads Library for Win32 + * Copyright(C) 1998 John E. Bossom + * Copyright(C) 1999,2005 Pthreads-win32 contributors + * + * Contact Email: rpj@callisto.canberra.edu.au + * + * The current list of contributors is contained + * in the file CONTRIBUTORS included with the source + * code distribution. The list can also be seen at the + * following World Wide Web location: + * http://sources.redhat.com/pthreads-win32/contributors.html + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file COPYING.LIB; + * if not, write to the Free Software Foundation, Inc., + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA + */ + +/* + * NOTES: + * pthread_once() performs a very simple task. So why is this implementation + * so complicated? + * + * The original implementation WAS very simple, but it relied on Windows random + * priority boosting to resolve starvation problems. Windows priority boosting + * does not occur for realtime priority classes (levels 16 to 31). + * + * You can check back to previous versions of code in the CVS repository or + * search the mailing list archives for discussion. + * + * Version A + * --------- + * Waiting threads would resume and suspend again using Sleep(0) until the + * init_routine had completed, but a higher priority waiter could hog the CPU and + * starve the initter thread until Windows randomly boosted it's priority, or forever + * for realtime applications. + * + * Version B + * --------- + * This was fixed by introducing a per once_control manual-reset event that is + * created and destroyed dynamically only if there are waiters. The design did not + * need global critical sections. Each once_control remained independent. A waiter + * could be confident that if the event was not null then it did not need to create + * the event. + * + * Version C + * --------- + * Since a change in ABI would result from version B, it was decided to take + * the opportunity and make pthread_once() fully compliant with the Single Unix + * Specification (version 3 at the time). This required allowing the init_routine + * to be a cancelation point. A cancelation meant that at least some waiting threads + * if any had to be woken so that one might become the new initter thread. + * Waiters could no longer simply assume that, if the event was not null, it did + * not need to create an event. Some real critical sections were needed, and in the + * current library, a global CRITICAL_SECTION is probably more efficient than a per + * once_control PTHREAD_MUTEX_INITIALIZER that should be somehow destroyed on exit from + * pthread_once(). Also, the cancelled init thread needed to set the event, and the + * new init thread (the winner of the race between any newly arriving threads and + * waking waiters) would need to reset it again. In the meantime, threads could be + * happily looping around until they either suspended on the reset event, or exited + * because the init thread had completed. It was also once again possible for a higher + * priority waiter to starve the init thread. + * + * Version D + * --------- + * There were now two options considered: + * - use an auto-reset event; OR + * - add our own priority boosting. + * + * An auto-reset event would stop threads from looping ok, but it makes threads + * dependent on earlier threads to successfully set the event in turn when it's time + * to wake up, and this serialises threads unecessarily on MP systems. It also adds + * an extra kernel call for each waking thread. If one waiter wakes and dies (async + * cancelled or killed) before it can set the event, then all remaining waiters are + * stranded. + * + * Priority boosting is a standard method for solving priority inversion and + * starvation problems. Furthermore, all of the priority boost logic can + * be restricted to the post cancellation tracks. That is, it need not slow + * the normal cancel-free behaviour. Threads remain independent of other threads. + * + * The implementation below adds only a few local (to the thread) integer comparisons + * to the normal track through the routine and additional bus locking/cache line + * syncing operations have been avoided altogether in the uncontended track. + */ + +#include "pthread.h" +#include "implement.h" + + +static void +ptw32_once_init_routine_cleanup(void * arg) +{ + pthread_once_t * once_control = (pthread_once_t *) arg; + + (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_CANCELLED); + (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started, (LONG)PTW32_FALSE); + + EnterCriticalSection(&ptw32_once_event_lock); + if (once_control->event) + { + /* + * There are waiters, wake some up + * We're deliberately not using PulseEvent. It's iffy, and deprecated. + */ + SetEvent(once_control->event); + } + LeaveCriticalSection(&ptw32_once_event_lock); +} + + +int +pthread_once (pthread_once_t * once_control, void (*init_routine) (void)) + /* + * ------------------------------------------------------ + * DOCPUBLIC + * If any thread in a process with a once_control parameter + * makes a call to pthread_once(), the first call will summon + * the init_routine(), but subsequent calls will not. The + * once_control parameter determines whether the associated + * initialization routine has been called. The init_routine() + * is complete upon return of pthread_once(). + * This function guarantees that one and only one thread + * executes the initialization routine, init_routine when + * access is controlled by the pthread_once_t control + * key. + * + * pthread_once() is not a cancelation point, but the init_routine + * can be. If it's cancelled then the effect on the once_control is + * as if pthread_once had never been entered. + * + * + * PARAMETERS + * once_control + * pointer to an instance of pthread_once_t + * + * init_routine + * pointer to an initialization routine + * + * + * DESCRIPTION + * See above. + * + * RESULTS + * 0 success, + * EINVAL once_control or init_routine is NULL + * + * ------------------------------------------------------ + */ +{ + int result; + LONG state; + pthread_t self; + HANDLE w32Thread = 0; + + if (once_control == NULL || init_routine == NULL) + { + + result = EINVAL; + goto FAIL0; + + } + else + { + result = 0; + } + + while (!((state = InterlockedExchangeAdd((LPLONG)&once_control->state, 0L)) /* Atomic Read */ + & (LONG)PTW32_ONCE_DONE)) + { + LONG cancelled = (state & PTW32_ONCE_CANCELLED); + + if (cancelled) + { + /* Boost priority momentarily */ + if (!w32Thread) + { + self = pthread_self(); + w32Thread = pthread_getw32threadhandle_np(self); + } + /* + * Prevent pthread_setschedparam() from changing our priority while we're boosted. + */ + pthread_mutex_lock(&((ptw32_thread_t *)self.p)->threadLock); + SetThreadPriority(w32Thread, THREAD_PRIORITY_HIGHEST); + } + + if (!PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started, (LONG)PTW32_TRUE)) + { + /* + * Clear residual state from a cancelled init_routine + * (and DONE still hasn't been set of course). + */ + if (cancelled) + { + /* + * The previous initter was cancelled. + * We now have a new initter (us) and we need to make the rest wait again. + * Furthermore, we're running at max priority until after we've reset the event + * so we will not be starved by any other threads that may now be looping + * around. + */ + EnterCriticalSection(&ptw32_once_event_lock); + if (once_control->event) + { + ResetEvent(once_control->event); + } + LeaveCriticalSection(&ptw32_once_event_lock); + + /* + * Any threads entering the wait section and getting out again before + * the event is reset and the CANCELLED state is cleared will, at worst, + * just go around again or, if they suspend and we (the initter) completes before + * they resume, they will see state == DONE and leave immediately. + */ + PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_CLEAR); + + /* + * Restore priority. We catch any changes to this thread's priority + * only if they were done through the POSIX API (i.e. pthread_setschedparam) + */ + SetThreadPriority(w32Thread, ((ptw32_thread_t *)self.p)->sched_priority); + pthread_mutex_unlock(&((ptw32_thread_t *)self.p)->threadLock); + } + + pthread_cleanup_push(ptw32_once_init_routine_cleanup, (void *) once_control); + (*init_routine)(); + pthread_cleanup_pop(0); + + (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_DONE); + + /* + * we didn't create the event. + * it is only there if there is someone waiting + */ + if (once_control->event) + { + SetEvent(once_control->event); + } + } + else + { + if (cancelled) + { + /* + * Restore priority. We catch any changes to this thread's priority + * only if they were done through the POSIX API (i.e. pthread_setschedparam. + */ + SetThreadPriority(w32Thread, ((ptw32_thread_t *)self.p)->sched_priority); + pthread_mutex_unlock(&((ptw32_thread_t *)self.p)->threadLock); + } + + /* + * wait for init. + * while waiting, create an event to wait on + */ + + EnterCriticalSection(&ptw32_once_event_lock); + once_control->eventUsers++; + + /* + * RE CANCELLATION: + * If we are the first thread after the initter thread, and the init_routine is cancelled + * while we're suspended at this point in the code:- + * - state will not get set to PTW32_ONCE_DONE; + * - cleanup will not see an event and cannot set it; + * - therefore, we will eventually resume, create an event and wait on it; + * cleanup will set state == CANCELLED before checking for an event, so that + * we will see it and avoid waiting (as for state == DONE). We will go around again and + * we may then become the initter. + * If we are still the only other thread when we get to the end of this block, we will + * have closed the event (good). If another thread beats us to be initter, then we will + * re-enter here (good). In case the old event is reused, the event is always reset by + * the new initter before clearing the CANCELLED state, causing any threads that are + * cycling around the loop to wait again. + * The initter thread is guaranteed to be at equal or higher priority than any waiters + * so no waiters will starve the initter, which might otherwise cause us to loop + * forever. + */ + + if (!once_control->event) + { + once_control->event = CreateEvent(NULL, PTW32_TRUE, PTW32_FALSE, NULL); + } + LeaveCriticalSection(&ptw32_once_event_lock); + + /* + * Check 'state' again in case the initting thread has finished or cancelled + * and left before seeing that there was an event to trigger. + * (Now that the event IS created, if init gets finished AFTER this, + * then the event handle is guaranteed to be seen and triggered). + */ + + if (!InterlockedExchangeAdd((LPLONG)&once_control->state, 0L)) /* Atomic Read */ + { + /* Neither DONE nor CANCELLED */ + (void) WaitForSingleObject(once_control->event, INFINITE); + } + + /* last one out shut off the lights */ + EnterCriticalSection(&ptw32_once_event_lock); + if (0 == --once_control->eventUsers) + { + /* we were last */ + CloseHandle(once_control->event); + once_control->event = 0; + } + LeaveCriticalSection(&ptw32_once_event_lock); + } + } + + + /* + * Fall through Intentionally + */ + + /* + * ------------ + * Failure Code + * ------------ + */ +FAIL0: + return (result); + +} /* pthread_once */ -- cgit v1.2.3