From: Vladimir Kliatchko <vladimir@kliatchko.com>
To: 'Ross Johnson' <ross.johnson@homemail.com.au>
Cc: 'Gottlob Frege' <gottlobfrege@gmail.com>,
pthreads-win32@sources.redhat.com
Subject: RE: New pthread_once implementation
Date: Sun, 29 May 2005 12:58:00 -0000 [thread overview]
Message-ID: <0IH9009LF5DVF3@mta7.srv.hcvlny.cv.net> (raw)
In-Reply-To: <0IH700C30EV237@mta8.srv.hcvlny.cv.net>
[-- Attachment #1: Type: text/plain, Size: 6169 bytes --]
Hi,
I tried fixing that last problem (semaphore leak when multiple threads are
cancelled and the initialization is never completed) but it appears the
reference counting approach is inherently flawed. So I had to re-implement
the whole thing from scratch. This implementation uses MCS locks which are
not only fast but also require no clean-up thus avoiding the above problem.
The implementation of MCS locks, which I had to build, probably deserves a
module (.c and .h) of its own since we may want to use them in other places.
This implementation has passed all the tests (again on a single CPU only)
and I hope it is finally bug-free now.
Pls, let me know what you think.
--vlad
PS.
Sorry it takes me so many iterations. I feel like I have been spamming you
with too many versions of this routine.
> -----Original Message-----
> From: pthreads-win32-owner@sources.redhat.com [mailto:pthreads-win32-
> owner@sources.redhat.com] On Behalf Of Vladimir Kliatchko
> Sent: Saturday, May 28, 2005 10:30 AM
> To: 'Ross Johnson'
> Cc: 'Gottlob Frege'; pthreads-win32@sources.redhat.com
> Subject: RE: New pthread_once implementation
>
> What do you think of the attached implementation? I am still analyzing it,
> but it passes the tests and appears to be free of that problem. It does
> have
> one minor glitch though:
> If two threads come in, the semaphore is created. If both are cancelled
> and
> no new calls a made to finish the job, the semaphore is never destroyed.
> I am not sure how big a deal this is.
>
> Re. optimizations: Great, I will try to do something.
>
> Thnx,
> --vlad
>
> > -----Original Message-----
> > From: pthreads-win32-owner@sources.redhat.com [mailto:pthreads-win32-
> > owner@sources.redhat.com] On Behalf Of Ross Johnson
> > Sent: Saturday, May 28, 2005 9:55 AM
> > To: Vladimir Kliatchko
> > Cc: 'Gottlob Frege'; Pthreads-Win32 list
> > Subject: RE: New pthread_once implementation
> >
> > On Sat, 2005-05-28 at 06:51 -0400, Vladimir Kliatchko wrote:
> > >
> > > > -----Original Message-----
> > > > From: pthreads-win32-owner@sources.redhat.com [mailto:pthreads-
> win32-
> > > > owner@sources.redhat.com] On Behalf Of Ross Johnson
> > > > Sent: Friday, May 27, 2005 11:48 PM
> > > > To: Vladimir Kliatchko
> > > > Cc: 'Gottlob Frege'; Pthreads-Win32 list
> > > > Subject: RE: New pthread_once implementation
> > > >
> > > > On Fri, 2005-05-27 at 21:30 -0400, Vladimir Kliatchko wrote:
> > > > > Nice catch. Let me see if I can fix it.
> > > > >
> > > > > Note that the same problem exists in the currently released event-
> > based
> > > > > implementation (cvs version 1.16):
> > > > >
> > > > > thread1 comes in, start initing
> > > > > thread2 creates event, starts waiting
> > > > > thread3 comes in starts waiting
> > > > > thread1 is cancelled, signals event
> > > > > thread2 wakes up, proceeds to the point right before the
> resetEvent
> > > > > thread3 wakes up, closes event handle
> > > > > thread2 resets closed handle
> > > >
> > > > Relies on HANDLE uniqueness and assumes that an error will result.
> > This
> > > > is why the 2.6.0 version (and earlier) checks the return code and
> > > > restores Win32 LastError if necessary - for GetLastError
> transparency.
> > >
> > > Does Windows guarantee that the handles are not reused? What happens
> if
> > a
> > > thread closes a handle while another thread is blocked on it? Is any
> of
> > this
> > > in Microsoft documentation? Consider the following scenario for the
> > > event-based implementation:
> >
> > Well, apparently they're not unique when recycled, so there is a bug
> > here to fix in both versions:
> > http://msdn.microsoft.com/library/default.asp?url=/library/en-
> > us/dngenlib/html/msdn_handles1.asp
> > [Under "Native Windows NT Objects"]
> > "Unlike the handles that are maintained by the Win32 USER and GDI
> > subsystem components, handles to native objects under Windows NT are not
> > unique; that is, upon destruction of an object, the corresponding handle
> > may be recycled and will look exactly like the handle to the destroyed
> > object."
> >
> > But they are local to the process, rather than system wide if that
> > helps.
> >
> > > > > Also, regarding my previous comment to Ross about very high cost
> of
> > > > using
> > > > > InterlockedExchangeAdd for MBR:
> > > > > I did some simple benchmarking. Running pthread_once 50,000,000 on
> > my
> > > > pretty
> > > > > slow single CPU machine takes about 2.1 seconds. Replacing
> > > > > InterlockedExchangeAdd with simple read brings it down to 0.6
> > seconds.
> > > > This
> > > > > looks significant.
> > > >
> > > > Using the PTW32_INTERLOCKED_COMPARE_EXCHANGE macro as in your latest
> > (in
> > > > CVS) version and building the library for inlined functions (nmake
> VC-
> > > > inlined) and x86 architecture causes customised versions of
> > > > InterlockedCompareExchange to be used, and this results in inlined
> > asm.
> > > > Same for PTW32_INTERLOCKED_EXCHANGE.
> > > >
> > > > Also, on single-CPU x86, the library dynamically switches to using
> > > > 'cmpxchg' rather than 'lock cmpxchg' to avoid locking the bus. This
> > > > appears to match what the kernel32.dll versions do. On non-x86
> > > > architectures the kernel32.dll versions are called, with call
> > overhead.
> > > >
> > > > PTW32_INTERLOCKED_EXCHANGE_ADD could be added, as could other
> > > > architectures. See ptw32_InterlockedCompareExchange.c
> > >
> > > I have rerun my benchmark with VC-inline. The difference is now less
> > > significant 0.9 vs 0.6 but still noticeable. I guess cmpxchg even
> > without
> > > locking is quite expensive. On multi-CPU systems the difference should
> > be
> > > much higher due to the time it takes to lock the bus and to the
> > contention
> > > it may cause. It sounded as if you did not care much to try to
> optimize
> > it.
> > > I did not mean to suggest that we have to do it right now either. I
> just
> > > wanted to get your opinion on whether we want to deal with this in the
> > > future.
> >
> > By all means include any optimisation you think is worthwhile. I was
> > just pointing out that the difference isn't necessarily 2.1 v 0.6.
> >
[-- Attachment #2: vk_pthread_once5.c --]
[-- Type: text/plain, Size: 4834 bytes --]
#define PTHREAD_ONCE_INIT {PTW32_FALSE, 0, 0, 0}
struct pthread_once_t_
{
int done;
void *lock;
int reserved1;
int reserved2;
};
struct ptw32_mcs_node_
{
struct ptw32_mcs_node_ **lock; /* ptr to tail of queue */
struct ptw32_mcs_node_ *next; /* ptr to successor in queue */
LONG readyFlag; /* set after lock is released by
predecessor */
LONG nextFlag; /* set after 'next' ptr is set by
successor */
};
typedef struct ptw32_mcs_node_ ptw32_mcs_node;
typedef struct ptw32_mcs_node_ *ptw32_mcs_lock;
/*
* ptw32_mcs_flag_set -- notify another thread about an event.
*
* Set event if an event handle has been stored in the flag, and
* set flag to -1 otherwise. Note that -1 cannot be a valid hande value.
*/
static void
ptw32_mcs_flag_set(LONG *flag)
{
HANDLE e = (HANDLE)PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)flag,
(PTW32_INTERLOCKED_LONG)-1,
(PTW32_INTERLOCKED_LONG)0);
if (0 != e)
{
/* another thread has already stored an event handle in the flag */
SetEvent(e);
}
}
/*
* ptw32_mcs_flag_set -- wait for notification from another.
*
* Store an event handle in the flag and wait on it if the flag has not been
* set, and proceed without creating an event otherwise.
*/
static void
ptw32_mcs_flag_wait(LONG *flag)
{
if (0 == InterlockedExchangeAdd((LPLONG)flag, 0)) /* MBR fence */
{
/* the flag is not set. create event. */
HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);
if (0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)flag,
(PTW32_INTERLOCKED_LONG)e,
(PTW32_INTERLOCKED_LONG)0))
{
/* stored handle in the flag. wait on it now. */
WaitForSingleObject(e, INFINITE);
}
CloseHandle(e);
}
}
/*
* ptw32_mcs_lock_aquire -- acquire an MCS lock.
*
* See:
* J. M. Mellor-Crummey and M. L. Scott.
* Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
* ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
*/
static void
ptw32_mcs_lock_aquire(ptw32_mcs_lock *lock,
ptw32_mcs_node *node)
{
ptw32_mcs_node *pred;
node->lock = lock;
node->nextFlag = 0;
node->readyFlag = 0;
node->next = 0; /* initially, no successor */
/* queue for the lock */
pred = (ptw32_mcs_node *)PTW32_INTERLOCKED_EXCHANGE((LPLONG)lock,
(LONG)node);
if (0 != pred)
{
/* the lock was not free. link behind predecessor. */
pred->next = node;
ptw32_mcs_flag_set(&pred->nextFlag);
ptw32_mcs_flag_wait(&node->readyFlag);
}
}
/*
* ptw32_mcs_lock_aquire -- release an MCS lock.
*
* See:
* J. M. Mellor-Crummey and M. L. Scott.
* Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
* ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
*/
static void
ptw32_mcs_lock_release(ptw32_mcs_node *node)
{
ptw32_mcs_lock *lock = node->lock;
ptw32_mcs_node *next = (ptw32_mcs_node *)
InterlockedExchangeAdd((LPLONG)&node->next, 0); /* MBR fence */
if (0 == next)
{
/* no known successor */
if (node == (ptw32_mcs_node *)PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)lock,
(PTW32_INTERLOCKED_LONG)0,
(PTW32_INTERLOCKED_LONG)node))
{
/* no successor, lock is free now */
return;
}
/* wait for successor */
ptw32_mcs_flag_wait(&node->nextFlag);
next = (ptw32_mcs_node *)InterlockedExchangeAdd((LPLONG)&node->next, 0);
/* MBR fence */
}
/* pass the lock */
ptw32_mcs_flag_set(&next->readyFlag);
}
static void PTW32_CDECL
ptw32_once_on_init_cancel (void * arg)
{
/* when the initting thread is cancelled we have to release the lock */
ptw32_mcs_node *node = (ptw32_mcs_node*)arg;
ptw32_mcs_lock_release(node);
}
int
pthread_once (pthread_once_t * once_control, void (*init_routine) (void))
{
if (once_control == NULL || init_routine == NULL)
{
return EINVAL;
}
if (!InterlockedExchangeAdd((LPLONG)&once_control->done, 0)) /* MBR fence */
{
ptw32_mcs_node node;
ptw32_mcs_lock_aquire(&(ptw32_mcs_lock)once_control->lock, &node);
if (!once_control->done)
{
#ifdef _MSC_VER
#pragma inline_depth(0)
#endif
pthread_cleanup_push(ptw32_once_on_init_cancel, (void *)&node);
(*init_routine)();
pthread_cleanup_pop(0);
#ifdef _MSC_VER
#pragma inline_depth()
#endif
once_control->done = PTW32_TRUE;
}
ptw32_mcs_lock_release(&node);
}
return 0;
} /* pthread_once */
next prev parent reply other threads:[~2005-05-29 12:58 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <97ffb3105052709425ce1126a@mail.gmail.com>
2005-05-28 1:30 ` Vladimir Kliatchko
2005-05-28 3:46 ` Ross Johnson
2005-05-28 10:51 ` Vladimir Kliatchko
2005-05-28 13:54 ` Ross Johnson
2005-05-28 14:29 ` Vladimir Kliatchko
2005-05-29 12:58 ` Vladimir Kliatchko [this message]
2005-05-30 14:48 ` Ross Johnson
2005-05-30 15:26 ` Vladimir Kliatchko
2005-05-31 16:28 ` Gottlob Frege
2005-06-01 3:02 ` Ross Johnson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0IH9009LF5DVF3@mta7.srv.hcvlny.cv.net \
--to=vladimir@kliatchko.com \
--cc=gottlobfrege@gmail.com \
--cc=pthreads-win32@sources.redhat.com \
--cc=ross.johnson@homemail.com.au \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).