[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140815193536.GA26312@brightrain.aerifal.cx>
Date: Fri, 15 Aug 2014 15:35:36 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: New private cond var design
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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
