* RE: pthread_once suggestions
2005-05-26 16:22 ` pthread_once suggestions Gottlob Frege
@ 2005-05-27 1:42 ` Vladimir Kliatchko
0 siblings, 0 replies; 2+ messages in thread
From: Vladimir Kliatchko @ 2005-05-27 1:42 UTC (permalink / raw)
To: 'Gottlob Frege'; +Cc: pthreads-win32
[-- Attachment #1: Type: text/plain, Size: 15093 bytes --]
Sure. Here is the code.
--vlad
#define PTHREAD_ONCE_INIT { 0, 0, 0, 0}
enum ptw32_once_state {
PTW32_ONCE_INIT = 0x0,
PTW32_ONCE_STARTED = 0x1,
PTW32_ONCE_DONE = 0x2
};
struct pthread_once_t_
{
int state;
int reserved;
int numSemaphoreUsers;
HANDLE semaphore;
};
static void PTW32_CDECL
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_INIT);
if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
ReleaseSemaphore(once_control->semaphore, 1, NULL);
}
}
int
pthread_once (pthread_once_t * once_control, void (*init_routine) (void))
{
int result;
int state;
HANDLE sema;
if (once_control == NULL || init_routine == NULL)
{
result = EINVAL;
goto FAIL0;
}
else
{
result = 0;
}
while ((state = PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)&once_control->state,
(PTW32_INTERLOCKED_LONG)PTW32_ONCE_STARTED,
(PTW32_INTERLOCKED_LONG)PTW32_ONCE_INIT)) !=
PTW32_ONCE_DONE)
{
if (PTW32_ONCE_INIT == state)
{
#ifdef _MSC_VER
#pragma inline_depth(0)
#endif
pthread_cleanup_push(ptw32_once_init_routine_cleanup,
(void *) once_control);
(*init_routine)();
pthread_cleanup_pop(0);
#ifdef _MSC_VER
#pragma inline_depth()
#endif
(void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state,
(LONG)PTW32_ONCE_DONE);
/*
* we didn't create the semaphore.
* it is only there if there is someone waiting.
*/
if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
ReleaseSemaphore(once_control->semaphore,
once_control->numSemaphoreUsers, NULL);
}
}
else
{
InterlockedIncrement((LPLONG)&once_control->numSemaphoreUsers);
if (!InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
sema = CreateSemaphore(NULL, 0, INT_MAX, NULL);
if (PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)&once_control->semaphore,
(PTW32_INTERLOCKED_LONG)sema,
(PTW32_INTERLOCKED_LONG)0))
{
CloseHandle(sema);
}
}
/*
* Check 'state' again in case the initting thread has finished or
cancelled and left before seeing that there was a semaphore.
*/
if (InterlockedExchangeAdd((LPLONG)&once_control->state,
0L) == PTW32_ONCE_STARTED)
{
WaitForSingleObject(once_control->semaphore, INFINITE);
}
if (0 ==
InterlockedDecrement((LPLONG)&once_control->numSemaphoreUsers))
{
/* we were last */
if ((sema = (HANDLE) PTW32_INTERLOCKED_EXCHANGE(
(LPLONG)&once_control->semaphore,
(LONG)0)))
{
CloseHandle(sema);
}
}
}
}
/*
* ------------
* Failure Code
* ------------
*/
FAIL0:
return (result);
} /* pthread_once */
-----Original Message-----
From: pthreads-win32-owner@sources.redhat.com
[mailto:pthreads-win32-owner@sources.redhat.com] On Behalf Of Gottlob Frege
Sent: Thursday, May 26, 2005 12:23 PM
To: Ross Johnson
Cc: Pthreads-Win32 list
Subject: Re: pthread_once suggestions
To get me back into the loop, can someone post a version with these
latest ideas (pseudocode or whatever)?
On 5/25/05, Ross Johnson <Ross.Johnson@homemail.com.au> wrote:
> On Thu, 2005-05-26 at 01:42 +1000, Ross Johnson wrote:
> > On Wed, 2005-05-25 at 06:40 -0400, Vladimir Kliatchko wrote:
> > > Hi,
> > > I did not have much time to look into it, but from the top of my head
it
> > > appears that the problem you pointed out is similar to the problem
with the
> > > initializing thread not being canceled but completing while the thread
B is
> > > suspended before creating the semaphore. This last problem was
addressed by
> > > simply rechecking the 'done' flag. Can't we similarly recheck
'started'
> > > flag?
> >
> > I don't see why this won't work, but it's really late here so I will
> > continue to look at it tomorrow. If it does work then I may owe Gottlob
> > an apology because he also used this flag in this way, and I'm hoping I
> > had a good reason not to do the same, but I'm too tired to look
tonight..
>
> Good morning,
>
> Sorry if I seem to be unnecessarily confusing this, but I need to
> satisfy myself that all the older issues can truly be set aside.
>
> Here's my explanation of why 'started' wasn't sufficient in the current
> version (but is now in your version):
>
> The current event based version uses a manual-reset event, which the new
> initter must reset (the alternative using auto-reset and daisy chaining
> resets was not acceptable) and priority manipulation was needed because
> of this. The cancelled state flag is useful here and elsewhere because
> it meant all of this extra complexity could be kept out of the no-
> cancellation paths efficiently.
>
> Your semaphore version removes the need for any extra post-cancellation
> processing by the new initter thread, and I think I can agree - it's now
> possible to simply recheck 'started' as you've now done.
>
> I think it's looking much much better now and I'm very exited at the
> prospects.
>
> Thanks.
> Ross
>
> > I would love to have been wrong all along.
> >
> > > See the attached code.
> > >
> > > --vlad
> > >
> > > PS.
> > > I did rerun all the regression tests but only on a single CPU system.
The
> > > condition above I tested by sticking a 'sleep' call before creating
the
> > > semaphore.
> > > Do you have a multi-CPU box around?
> >
> > Not I, but Tim Theisen runs the tests on his 4-way before I release a
> > new version. He was certainly picking up problems that ran fine on my
> > uni-processor.
> >
> > Regards.
> > Ross
> >
> > >
> > > -----Original Message-----
> > > From: Ross Johnson [mailto:Ross.Johnson@homemail.com.au]
> > > Sent: Wednesday, May 25, 2005 5:41 AM
> > > To: Vladimir Kliatchko
> > > Cc: Gottlob Frege
> > > Subject: Re: pthread_once suggestions
> > >
> > > On Wed, 2005-05-25 at 17:48 +1000, Ross Johnson wrote:
> > > > I think there is a problem after all.
> > > >
> > > > If thread A is running the init_routine and thread B is suspended
> > > > immediately before it is about to increment numSemaphoreUsers, and
> > > > thread A is cancelled, then: there may not be a semaphore yet for
the
> > > > cancelled thread A to release; thread B will eventually resume,
create
> > > > the semaphore, and then wait on it until a new thread C arrives to
> > > > finally complete the init_routine and release thread B.
> > > >
> > > > If there are only ever 2 threads then thread B will wait forever.
But
> > > > even if there are more than 2 threads, thread B should not have to
wait
> > > > until thread C arrives.
> > > >
> > > > So I think it's still necessary to have a flag to tell potential
waiters
> > > > that the init_routine has been cancelled.
> > > >
> > > > Even so, I think the semaphore can still eliminate a lot of the
current
> > > > complexity, especially the priority management.
> > >
> > > Hi Vlad,
> > >
> > > Sorry, it's all coming back to me - but slowly. If I add the cancelled
> > > state flag back in to prevent thread B waiting on the semaphore that
it
> > > has just created (see above), then I seem to be returning to the
> > > situation where starvation occurs.
> > >
> > > If thread C arrives and sets 'started' to true first, but suspends
> > > before it can clear the cancelled flag, then if thread B (which has
been
> > > woken) has a higher priority than thread C, it could busy loop and
> > > starve thread C of CPU, preventing it from ever clearing the cancelled
> > > flag. This is a problem that Gottlob noted during the previous effort
to
> > > tame this routine using events. It's what ultimately forced the
> > > inclusion of the priority promotion code.
> > >
> > > Regards.
> > > Ross
> > >
> > > > Is this correct?
> > > >
> > > > Regards.
> > > > Ross
> > > >
> > > > On Wed, 2005-05-25 at 16:55 +1000, Ross Johnson wrote:
> > > > > On Tue, 2005-05-24 at 20:56 -0400, Vladimir Kliatchko wrote:
> > > > > > Dear Ross,
> > > > > > I was looking at the implementation of the pthread_once and came
up
> > > > > > with what seemed a simpler and more robust implementation. I
would
> > > > > > like to contribute this implementation. Pls, let me know what
think.
> > > > > >
> > > > > > Thx,
> > > > > > --vlad
> > > > >
> > > > > Hi Vlad,
> > > > >
> > > > > This is great. It seems to have everything and I can't find fault
with
> > > > > it - I'm still looking since I think there were some very obscure
> > > > > scenarios, but you seem to have fundamentally eliminated them.
> > > > >
> > > > > This is actually much closer to the simple [working] version
posted by
> > > > > Gottlob Frege initially:-
> > > > > http://sources.redhat.com/ml/pthreads-win32/2005/msg00029.html
> > > > > which uses events but didn't include cancelation. Your's is even a
> > > > > little simpler I think.
> > > > >
> > > > > The advantage your semaphore has over the event is that you can
release
> > > > > just one waiter after a cancellation but still release all waiters
when
> > > > > done (PulseEvent is deprecated and dangerous and wasn't an
option). If
> > > > > there are really no problems with it then I think you've
legitimised the
> > > > > whole approach, as opposed to the named or reference counting
mutex
> > > > > trick etc.
> > > > >
> > > > > And you've done it without changing pthread_once_t_ or
PTHREAD_ONCE_INIT
> > > > > - so the ABI is unaffected. Fantastic!
> > > > >
> > > > > I presume you've already run the test suite, and once4.c in
particular
> > > > > has passed? I'll let you know if any problems arise. Did you test
it on
> > > > > a multi-processor system?
> > > > >
> > > > > Thank you.
> > > > > Ross
> > > > >
> > > > > > The implementation:
> > > > > > #define PTHREAD_ONCE_INIT { PTW32_FALSE, PTW32_FALSE, 0,
0}
> > > > > >
> > > > > >
> > > > > >
> > > > > > struct pthread_once_t_
> > > > > > {
> > > > > > int done;
> > > > > > int started;
> > > > > > int numSemaphoreUsers;
> > > > > > HANDLE semaphore;
> > > > > > };
> > > > > >
> > > > > > static void PTW32_CDECL
> > > > > > ptw32_once_init_routine_cleanup(void * arg)
> > > > > > {
> > > > > > pthread_once_t * once_control = (pthread_once_t *) arg;
> > > > > >
> > > > > > (void)
PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started,
> > > (LONG)PTW32_FALSE);
> > > > > >
> > > > > > if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /*
> > > MBR fence */
> > > > > > {
> > > > > > ReleaseSemaphore(once_control->semaphore, 1, NULL);
> > > > > > }
> > > > > > }
> > > > > >
> > > > > > int
> > > > > > pthread_once (pthread_once_t * once_control, void
(*init_routine)
> > > (void))
> > > > > > {
> > > > > > int result;
> > > > > > HANDLE sema;
> > > > > >
> > > > > > if (once_control == NULL || init_routine == NULL)
> > > > > > {
> > > > > > result = EINVAL;
> > > > > > goto FAIL0;
> > > > > > }
> > > > > > else
> > > > > > {
> > > > > > result = 0;
> > > > > > }
> > > > > >
> > > > > > while (!InterlockedExchangeAdd((LPLONG)&once_control->done,
0L)) /*
> > > Atomic Read */
> > > > > > {
> > > > > > if
(!PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started,
> > > (LONG)PTW32_TRUE))
> > > > > > {
> > > > > >
> > > > > > #ifdef _MSC_VER
> > > > > > #pragma inline_depth(0)
> > > > > > #endif
> > > > > >
> > > > > >
pthread_cleanup_push(ptw32_once_init_routine_cleanup,
> > > (void *) once_control);
> > > > > > (*init_routine)();
> > > > > > pthread_cleanup_pop(0);
> > > > > >
> > > > > > #ifdef _MSC_VER
> > > > > > #pragma inline_depth()
> > > > > > #endif
> > > > > >
> > > > > > (void)
> > > PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->done,
(LONG)PTW32_TRUE);
> > > > > >
> > > > > > /*
> > > > > > * we didn't create the event.
> > > > > > * it is only there if there is someone waiting.
> > > > > > * Avoid using the global event_lock but still
prevent
> > > SetEvent
> > > > > > * from overwriting any 'lasterror' if the event
is
> > > closed before we
> > > > > > * are done with it.
> > > > > > */
> > > > > > if
> > > (InterlockedExchangeAdd((LPLONG)&once_control->semaphore, 0L)) /* MBR
fence
> > > */
> > > > > > {
> > > > > > ReleaseSemaphore(once_control->semaphore,
> > > once_control->numSemaphoreUsers, NULL);
> > > > > > }
> > > > > > }
> > > > > > else
> > > > > > {
> > > > > >
> > > InterlockedIncrement((LPLONG)&once_control->numSemaphoreUsers);
> > > > > > if
> > > (!InterlockedExchangeAdd((LPLONG)&once_control->semaphore, 0L)) /* MBR
fence
> > > */
> > > > > > {
> > > > > > sema = CreateSemaphore(NULL, 0, INT_MAX,
NULL);
> > > > > > if
> > >
(PTW32_INTERLOCKED_COMPARE_EXCHANGE((PTW32_INTERLOCKED_LPLONG)&once_control-
> > > >semaphore,
> > > > > >
> > > (PTW32_INTERLOCKED_LONG)sema,
> > > > > >
> > > (PTW32_INTERLOCKED_LONG)0))
> > > > > > {
> > > > > > CloseHandle(sema);
> > > > > > }
> > > > > > }
> > > > > >
> > > > > > /*
> > > > > > * Check 'state' again in case the initting thread
has
> > > finished or cancelled
> > > > > > * and left before seeing that there was an event
to
> > > trigger.
> > > > > > */
> > > > > > if
(InterlockedExchangeAdd((LPLONG)&once_control->done,
> > > 0L) ||
> > > > > > WaitForSingleObject(once_control->semaphore,
> > > INFINITE))
> > > > > > {
> > > > > > if (0 ==
> > > InterlockedDecrement((LPLONG)&once_control->numSemaphoreUsers))
> > > > > > {
> > > > > > /* we were last */
> > > > > > if ((sema = (HANDLE)
> > > PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->semaphore,
> > > > > >
> > > (LONG)0)))
> > > > > > {
> > > > > > CloseHandle(sema);
> > > > > > }
> > > > > > }
> > > > > > }
> > > > > > }
> > > > > > }
> > > > > >
> > > > > > /*
> > > > > > * ------------
> > > > > > * Failure Code
> > > > > > * ------------
> > > > > > */
> > > > > > FAIL0:
> > > > > > return (result);
> > > > > >
> > > > > > } /* pthread_once
*/
> > > > > >
> > >
>
>
[-- Attachment #2: vk_pthread_once2.c --]
[-- Type: text/plain, Size: 3162 bytes --]
#define PTHREAD_ONCE_INIT { 0, 0, 0, 0}
enum ptw32_once_state {
PTW32_ONCE_INIT = 0x0,
PTW32_ONCE_STARTED = 0x1,
PTW32_ONCE_DONE = 0x2
};
struct pthread_once_t_
{
int state;
int reserved;
int numSemaphoreUsers;
HANDLE semaphore;
};
static void PTW32_CDECL
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_INIT);
if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
ReleaseSemaphore(once_control->semaphore, 1, NULL);
}
}
int
pthread_once (pthread_once_t * once_control, void (*init_routine) (void))
{
int result;
int state;
HANDLE sema;
if (once_control == NULL || init_routine == NULL)
{
result = EINVAL;
goto FAIL0;
}
else
{
result = 0;
}
while ((state = PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)&once_control->state,
(PTW32_INTERLOCKED_LONG)PTW32_ONCE_STARTED,
(PTW32_INTERLOCKED_LONG)PTW32_ONCE_INIT)) !=
PTW32_ONCE_DONE)
{
if (PTW32_ONCE_INIT == state)
{
#ifdef _MSC_VER
#pragma inline_depth(0)
#endif
pthread_cleanup_push(ptw32_once_init_routine_cleanup,
(void *) once_control);
(*init_routine)();
pthread_cleanup_pop(0);
#ifdef _MSC_VER
#pragma inline_depth()
#endif
(void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state,
(LONG)PTW32_ONCE_DONE);
/*
* we didn't create the semaphore.
* it is only there if there is someone waiting.
*/
if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
ReleaseSemaphore(once_control->semaphore,
once_control->numSemaphoreUsers, NULL);
}
}
else
{
InterlockedIncrement((LPLONG)&once_control->numSemaphoreUsers);
if (!InterlockedExchangeAdd((LPLONG)&once_control->semaphore,
0L)) /* MBR fence */
{
sema = CreateSemaphore(NULL, 0, INT_MAX, NULL);
if (PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)&once_control->semaphore,
(PTW32_INTERLOCKED_LONG)sema,
(PTW32_INTERLOCKED_LONG)0))
{
CloseHandle(sema);
}
}
/*
* Check 'state' again in case the initting thread has finished or
cancelled and left before seeing that there was a semaphore.
*/
if (InterlockedExchangeAdd((LPLONG)&once_control->state,
0L) == PTW32_ONCE_STARTED)
{
WaitForSingleObject(once_control->semaphore, INFINITE);
}
if (0 ==
InterlockedDecrement((LPLONG)&once_control->numSemaphoreUsers))
{
/* we were last */
if ((sema = (HANDLE) PTW32_INTERLOCKED_EXCHANGE(
(LPLONG)&once_control->semaphore,
(LONG)0)))
{
CloseHandle(sema);
}
}
}
}
/*
* ------------
* Failure Code
* ------------
*/
FAIL0:
return (result);
} /* pthread_once */
^ permalink raw reply [flat|nested] 2+ messages in thread