mailing list of musl libc
 help / color / mirror / code / Atom feed
* New private cond var design
@ 2014-08-15 19:35 Rich Felker
  2014-08-15 20:28 ` Rich Felker
                   ` (2 more replies)
  0 siblings, 3 replies; 5+ messages in thread
From: Rich Felker @ 2014-08-15 19:35 UTC (permalink / raw)
  To: musl

The current cv bug reported by Jens occurs when a cv is reused with a
new mutex before all the former-waiters from the previous mutex have
woken up and decremented themselves from the waiter count. In this
case, they can't know whether to decrement the in-cv waiter count or
the in-mutex waiter count, and thereby end up corrupting these counts.

Jens' proposed solution tracked "instances" via dynamically allocated,
reference-counted objects. I finally think I have a solution which
avoids dynamic allocation: representing the "instance" as a
doubly-linked-list of automatic objects on the stack of each waiter.

The cv object itself needs a single pointer to the head of the current
instance. This pointer is set by the first waiter on an instance.
Subsequent waiters which arrive when it's already set can check that
the mutex argument is the same; if not, this is an error. The pointer
is cleared when the last (formal) waiter is removed by the signal or
broadcast operation.

Storing this list eliminates the need to keep a waiter count. The
length of the linked list itself is the number of waiters which need
to be moved to the mutex on broadcast. This requires an O(n) walk of
the list at broadcast time, but that's really a non-issue since the
kernel is already doing a much more expensive O(n) walk of the futex
waiter list anyway.

The list also allows us to eliminate the sequence number wrapping
issue (sadly, only for private, non-process-shared cv's, since
process-shared can't use process-local memory like this) in one of two
ways:

Option 1: If the list elements store the sequence number their waiter
is waiting on, the signal/broadcast operations can choose a new
sequence number distinct from that of all waiters.

Option 2: Each waiter can wait on a separate futex on its own stack,
so that sequence numbers are totally unneeded. This eliminates all
spurious wakes; signal can precisely control exactly which waiter
wakes (e.g. choosing the oldest), thereby waking only one waiter.
Broadcast then becomes much more expensive: the broadcasting thread
has to make one requeue syscall per waiter. But this still might be a
good design.

Unless anyone sees problems with this design, I'll probably start
working on it soon. I think I'll try to commit the private-futex stuff
first, though, to avoid having to rebase it; fixing the cv issue in
1.0.x will not be a direct cherry-pick anyway, so there's no point in
putting off 1.0.x-incompatible changes pending the fix.

Rich


^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2014-08-18  4:04 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-08-15 19:35 New private cond var design Rich Felker
2014-08-15 20:28 ` Rich Felker
2014-08-17 13:44 ` AW: " Jens Gustedt
2014-08-17 15:44   ` Rich Felker
2014-08-18  4:04 ` Rich Felker

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

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 NNTP newsgroup(s).