From -4197612233791135271 X-Google-Thread: f78e5,4c3ccbaec057287f X-Google-NewGroupId: yes X-Google-Attributes: gid7894ca11fe,domainid0,public,usenet X-Google-Language: ENGLISH,UTF8 Path: g2news2.google.com!news1.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!news.alt.net From: Anthony Williams Newsgroups: comp.std.c++ Subject: Re: proposal for memory_order_seq_cst constraints Date: Wed, 9 Mar 2011 10:22:53 CST Organization: CNNTP Lines: 162 Sender: std-cpp-request@vandevoorde.com Approved: stephen.clamage@oracle.com Message-ID: <878vwoxq6b.fsf@justsoftwaresolutions.co.uk> References: <87zkpcjzim.fsf@justsoftwaresolutions.co.uk> Content-Type: text/plain; charset=utf-8 To: undisclosed-recipients:; Return-Path: X-Original-Date: Wed, 09 Mar 2011 15:35:24 +0000 X-Submission-Address: std-c++-submit@vandevoorde.com Xref: g2news2.google.com comp.std.c++:3185 Masakuni Oishi writes: > Hello, > > Anthony Williams wrote: >> Masakuni Oishi writes: >> > /*** 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. >> >> This is already disallowed. >> >> (1) is sequenced-before (2), so the value written by (2) must be later >> in the modification order of x than that written by (1). If (3) reads >> zero then (3) must be before (4) in S, so (2) precedes (5), and (5) must >> read the value written by (2) or a later value in the modification order >> of x. > > Hmm... N3242 29.3.3 doesn't restrict to "(2) or a later". > It only says that: > either the last preceding modification according to this order S, > or the result of an operation that is not memory_order_seq_cst. 29.3.3 is only one of the constraints. The bit you quote allows memory_order_seq_cst operations to return values written by non-memory_order_seq_cst operations (which is important), but that doesn't mean that *any* value written by a non-memory_order_seq_cst operation can be read: the other constraints on memory ordering still apply. >> > /*** 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. >> >> This is already disallowed. >> >> if (5) reads 2, then (6) must follow (4) in the modification order of >> x. If (1) reads 2, then (1) must follow (4) in S, otherwise the reads >> are inconsistent with the modification order of x. > > Why is it "inconsistent"? > Certainly, if (1) reads 2, then (6) happens before (1). > But, in N3242, "(4) precedes (6) in the modification order" and > "(6) happens before (1)" don't mean "(4) should precede (1) in S", > AFAIK. It certainly does! You missed the first part of the first sentence of 29.3.3: "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," (6) happens-before (1), so (1) can only read the value written by (6), or a value that is **later** in the MO of x. If (4) precedes (6) in the MO of x, then (1) cannot return the value written by (4). This comes from 1.10p18: "If a side effect X on an atomic object M happens before a value computation B of M , then the evaluation B shall take its value from X or from a side effect Y that follows X in the modification order of M . [ Note: This requirement is known as write-read coherence. — end note ]" In this case, X is the write (6), and B is the read (1). >> If (1) follows (4), >> then S must have (3)->(4)->(1)->(2) => (2) must read 1. >> >> If S is (1) -> (2) -> (3) -> (4) -> (5) then (1) precedes (4), so (1) >> can read 0 (the initial value) or 2 (from (6)), and (2) must read 0 (the >> initial value of y). >> >> If (1) reads 2 then the write at (6) must precede the write at (4) in >> the modification order of x, since (1) is before (4) in S. > > Same as above. > Do "(6) happens before (1)" and "(1) precedes (4) in S" mean > "(6) should precede (4) in the modification order"? Yes! >> > /*** 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. >> >> This is already disallowed. >> >> If S has (1) -> (3) -> (4) -> (5) -> (6), then (6) must read 2, since >> (2) follows (1) in the modification order of x, and (3) precedes (6) in >> S. > > Why? (2) follows (1) in the MO of x, since (1) is sequenced-before (2). If (3) reads 2, then (3) has seen the value written by (2). If (4) reads 0, then it has NOT seen the value written by (5), so must precede (5) in S. (2) is a memory_order_release, so if (3) reads 2 the (2) synchronizes-with (3), and happens-before (4). Since (6) follows (4) in S, if (6) reads the result of (1) then this is inconsistent with the happens-before ordering. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976 [ 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 ]