From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/5874 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: New private cond var design Date: Sun, 17 Aug 2014 11:44:09 -0400 Message-ID: <20140817154409.GJ12888@brightrain.aerifal.cx> References: <20140815193536.GA26312@brightrain.aerifal.cx> <1490621384.18463628.1408283055075.JavaMail.zimbra@inria.fr> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1408290276 4921 80.91.229.3 (17 Aug 2014 15:44:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 17 Aug 2014 15:44:36 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-5880-gllmg-musl=m.gmane.org@lists.openwall.com Sun Aug 17 17:44:29 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1XJ2d5-0002vi-St for gllmg-musl@plane.gmane.org; Sun, 17 Aug 2014 17:44:23 +0200 Original-Received: (qmail 3224 invoked by uid 550); 17 Aug 2014 15:44:23 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 3216 invoked from network); 17 Aug 2014 15:44:22 -0000 Content-Disposition: inline In-Reply-To: <1490621384.18463628.1408283055075.JavaMail.zimbra@inria.fr> User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:5874 Archived-At: On Sun, Aug 17, 2014 at 03:44:15PM +0200, Jens Gustedt wrote: > Hi, > I definitively like this idea of the list items on the stack. Do you have a preference which variant? It's not clear to me whether your comments are in regard to variant 1 or 2 or apply to both. > Some thoughts: > > Threads can leave the list prematurely, so we need a doubly linked list. Yes, obviously. > Threads that are inside the wait function can be organized that they hold the mutex, > this should avoid a lot of race trouble maintaining the list. If we have one list per 'instance' rather than a single list of all waiters that haven't yet exited, then yes, the waiters are all using the mutex and thereby excluding one another from access to the list. But the signal/broadcast thread(s) still need a way to access the list and cv object safely... > Broadcast can be done in O(1) when delegating the wake up to the > threads on the list one after another. These have to acquire the > mutex anyhow, one at a time. Is your thought to have each waiter, after acquiring the mutex in preparation to return, requeue the next waiter (if any) onto the mutex? I think this works and should be conforming. And with this approach there seems to be no reason to prefer having all waiters use the same futex rather than a futex local to their own stacks, so the option 2 looks very attractive. Rich