From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/5784 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Explaining cond var destroy [Re: [musl] C threads, v3.0] Date: Fri, 8 Aug 2014 12:53:21 -0400 Message-ID: <20140808165321.GN1674@brightrain.aerifal.cx> References: <20140806173254.GC1674@brightrain.aerifal.cx> <1407358510.24324.328.camel@eris.loria.fr> <20140806220453.GD1674@brightrain.aerifal.cx> <1407365015.24324.334.camel@eris.loria.fr> <20140806231539.GE1674@brightrain.aerifal.cx> <1407397851.24324.354.camel@eris.loria.fr> <20140807161342.GH1674@brightrain.aerifal.cx> <1407430024.24324.387.camel@eris.loria.fr> <20140807172514.GI1674@brightrain.aerifal.cx> <1407489627.24324.419.camel@eris.loria.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 1407516822 19658 80.91.229.3 (8 Aug 2014 16:53:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 8 Aug 2014 16:53:42 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-5789-gllmg-musl=m.gmane.org@lists.openwall.com Fri Aug 08 18:53:35 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 1XFnQ7-0000kc-0o for gllmg-musl@plane.gmane.org; Fri, 08 Aug 2014 18:53:35 +0200 Original-Received: (qmail 18061 invoked by uid 550); 8 Aug 2014 16:53:34 -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 18049 invoked from network); 8 Aug 2014 16:53:34 -0000 Content-Disposition: inline In-Reply-To: <1407489627.24324.419.camel@eris.loria.fr> User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:5784 Archived-At: On Fri, Aug 08, 2014 at 11:20:27AM +0200, Jens Gustedt wrote: > Hello, > > Am Donnerstag, den 07.08.2014, 13:25 -0400 schrieb Rich Felker: > > Most futex operations (including wait) access an object for read. Some > > rarely-used ones write to an object too. Wake does neither. Wake is > > purely an operation on the address/futex-waitqueue-object. This > > property is not just a side effect but absolutely necessary in order > > for futex to be useful, since you _always_ perform the futex wake > > after releasing (and thereby potentially allowing destruction) of the > > object. > > I agree with almost all what you are saying, in particular the > facts, ;) and your statement is a good summary of what I learned with > our discussion. > > I don't agree with your appreciation of these facts, though. > > In particular the "(and thereby potentially allowing destruction)" > bothers me a lot, and I don't think that *doing* this with control > structures is desirable. Do you have a reason it's undesirable? The only reason I've seen so far is that it causes spurious wakes and makes the return values of futex calls unusable. I agree it would be nice if the return values were usable, but the benefit to having them seems to be limited to making small optimizations in the implementation of synchronization primitives. On the other hand, the cost to make such optimizations (added synchronization to preclude sending a wake to an invalid address) seems to be much higher, and essentially infinite (i.e. fundamentally possible without moving the whole lock to kernelspace and incurring a syscall for each operation) for process-shared objects. So even if it is desirable, buying it seems like a HUGE net loss. > I think it is possible to have control structures that guarantee that > no wake (or any other futex operation) is done on an address that > isn't a valid address of a life object. So far the way you've proposed to do this is using dynamic allocation. This incurs additional synchronization cost (in malloc) for creation/destruction, incurs a complexity cost (in no longer being fail-safe) for both the implementation and the application, and it's not even possible for process-shared objects because there is fundamentally no way to allocate shared memory which is accessible only by the exact set of processes which have access to the original object. Any attempt to do so would either have false negatives (some processes that nominally have access to the object would fail to operate on it) or false positives (malicious processes would potentially have access to operate on the object). > I also think if only done for > non-shared structures (such as for C threads) that such a design can > be relatively simple, and with much less implicit state than what the > current musl implementation does, in particular for pthread_cond_t. Making mutexes heavy to make cond vars lighter seems like a net loss. Cond vars are supposed to be a heavy primitive (typical case is waiting) and mutexes a light one (typical case is immediately acquiring the lock). I would still like to explore ways to improve cond vars without resorting to allocation. One potential idea (but I don't see a way to make it work with cond vars yet) is to try something like the barriers implementation, where the actual synchronization object lies on the stack of the first waiter. Obviously this is only for non-process-shared objects (barriers do something else more costly in the process-shared case). The need for both signal and broadcast semantics complicates it somewhat though; with such a design it might be necessary for broadcast to simply keep signaling until the original list is empty rather than using a single broadcast wake. > Such an implementation should by design avoid late wakes from the > kernel for addresses that are recycled for new control objects. (It > can't inhibit them since other userspace tools might still have the > late wake problem.) > > I am currently debugging such a C thread implementation, and I'll come > back to you once I have something to show. I'm happy to see what you come up with, but I doubt it's right for musl. Rich