From -3112864227068113282 X-Google-Thread: f78e5,4c3ccbaec057287f,start X-Google-NewGroupId: yes X-Google-Attributes: gid7894ca11fe,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news2.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail NNTP-Posting-Date: Wed, 02 Mar 2011 17:00:02 -0600 Return-Path: Sender: std-cpp-request@vandevoorde.com Approved: austern@google.com Message-ID: Newsgroups: comp.std.c++ From: Masakuni Oishi Subject: proposal for memory_order_seq_cst constraints Organization: http://groups.google.com Content-Type: text/plain; charset=ISO-8859-1 X-Original-Date: Wed, 2 Mar 2011 09:22:03 -0800 (PST) X-Submission-Address: std-c++-submit@vandevoorde.com To: undisclosed-recipients:; Date: Wed, 2 Mar 2011 16:55:27 CST Lines: 166 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-1FQqPrFtJS9MW9vKEL/QRpw/YIQgrt+EQ4SmnEsqXTVexBKx+ssevVPMDy6zbpNbK4RyxkM7VevDN50!rfgX1MvlYWOnxYyh6eSi4ixlw7zOO4/YSGgOPfD55PqLFcSguCOq7gAbHfh+IBjjgIrzxuUySj7Q!KuxNc3yqhUvrx7R2U/F+bVcHepE= X-Complaints-To: abuse@giganews.com X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 6849 Xref: g2news2.google.com comp.std.c++:3170 Hello, I'd like to propose some changes about constraints between memory_order_seq_cst and other memory orders. In N3242 29.3.3, constraints of visible values with respect to a memory_order_seq_cst load is described as below: > There shall be a single total order S on all memory_order_seq_cst > operations, consistent with the "happens before" order and > modification orders for all affected locations, such that each > memory_order_seq_cst operation that loads a value observes either the > last preceding modification according to this order S, or the result > of an operation that is not memory_order_seq_cst. Under these constraints, the following cases can happen. /*** Case 1 ***/ // Initially atomic x(0), y(0); // Thread 1: x.store(2, memory_order_release); // (1) x.store(1, memory_order_seq_cst); // (2) r1 = y.load(memory_order_seq_cst); // (3) // Thread 2: y.store(1, memory_order_seq_cst); // (4) r2 = x.load(memory_order_seq_cst); // (5) r1 == 0 && r2 == 2 is possible, in case of (2) -> (3) -> (4) -> (5) in S. /*** Case 2 ***/ // Initially atomic x(0), y(0); // Thread 1: r1 = x.load(memory_order_seq_cst); // (1) r2 = y.load(memory_order_seq_cst); // (2) // Thread 2: y.store(1, memory_order_seq_cst); // (3) x.store(1, memory_order_seq_cst); // (4) r3 = x.load(memory_order_seq_cst); // (5) // Thread 3: x.store(2, memory_order_release); // (6) r1 == 2 && r2 == 0 && r3 == 2 is possible, in case of (1) -> (2) -> (3) -> (4) -> (5) in S, and (4) -> (6) in modification order of x. /*** Case 3 ***/ // Initially atomic x(0), y(0); // Thread 1: x.store(1, memory_order_seq_cst); // (1) x.store(2, memory_order_release); // (2) // Thread 2: r1 = x.load(memory_order_seq_cst); // (3) r2 = y.load(memory_order_seq_cst); // (4) // Thread 3: y.store(1, memory_order_seq_cst); // (5) r3 = x.load(memory_order_seq_cst); // (6) r1 == 2 && r2 == 0 && r3 == 1 is possible, in case of (1) -> (3) -> (4) -> (5) -> (6) in S. The above results are allowed in the current specification, but I think this should not be allowed. So, I propose new requirements for memory_order_seq_cst, similar to the four coherence requirements in 1.10. 1. For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if A precedes B in S, then the evaluation B shall take its value from A or from a side effect that follows A in the modification order of M. [ write-read coherence according to S ] 2. For atomic operations A and B on an atomic object M, where A is a value computation of M and B modifies it, if A precedes B in S, then A shall take its value from a side effect X on M, where X precedes B in the modification order of M. [ read-write coherence according to S ] 3. For value computations A and B on an atomic object M, where A takes its value from a side effect X on M, if A precedes B in S, then the evaluation B shall take its value from X or from a side effect that follows X in the modification order of M. [ read-read coherence according to S ] 4. For atomic modifications A and B on an atomic object M, if A precedes B in S, then A shall precede B in the modification order of M. [ write-write coherence according to S ] Additionally, I'll define a new relationship S' to treat memory_order_seq_cst fences in the same way. There is a relationship S' derived from the total order S and "happens before" relation. An atomic operation A precedes an atomic operation B in S' if: - A precedes B in S, or - there is a memory_order_seq_cst fence X such that A happens before X and X precedes B in S, or - there is a memory_order_seq_cst fence X such that X happens before B and A precedes X in S, or - there are memory_order_seq_cst fences X and Y such that A happens before X, Y happens before B, and X precedes Y in S. And the above four coherence requirements should be applied to S'. In the definition of S', I used "happens before" instead of "is sequenced before". That is because even if S' was derived from the "sequenced before" relation, it is easy to extend to the "happens before" relation. For example, // Thread 1: x.store(1, memory_order_seq_cst); // (1) // Thread 2: atomic_thread_fence(memory_order_seq_cst); // (2) r1 = x.load(memory_order_relaxed); // (3) y.store(1, memory_order_release); // Thread 3: r2 = y.load(memory_order_acquire); x.store(2, memory_order_relaxed); // (4) It assumes (1) precedes (2) in S, and r2 == 1. Then, because of write-read coherence according to S' (or N3242 29.3.4), (3) shall take a value from (1) or from a side effect that follows (1) in the modification order of x. And also, since (3) happens before (4), (3) shall take a value from a side effect which precedes (4) in the modification order of x. Consequently, (1) shall precedes (4) in the modification order of x. In a same way, the "sequenced before" relation in S' can be extended to the "happens before" relation with considering in-between load(memory_order_relaxed) operation. -- masakuni -- [ comp.std.c++ is moderated. To submit articles, try posting with your ] [ newsreader. If that fails, use mailto:std-cpp-submit@vandevoorde.com ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ]