ISO/IEC JTC1 SC22 WG21 N2360 = 07-0220 - 2007-08-04
Paul E. McKenney, paulmck@linux.vnet.ibm.com
This document presents the memory-model implications of dependency ordering, which is further described in N2359 and N2361. The rationale for this proposal may be found in N2359.
This proposal is based on N2153 by Silvera, Wong, McKenney, and Blainey, on N2176 by Hans Boehm, on N2195 by Peter Dimov, on N2260 by Paul E. McKenney, on N2334 by Clark Nelson and Hans Boehm, on discussions on the cpp-threads list, and on discussions in the concurrency workgroup at the 2007 Oxford and Toronto meetings.
See N2359.
See N2359.
See N2359.
As noted earlier, this proposal is based on N2334, which is under active revision. Therefore, the rest of this document must be considered a work in progress. In any case, the general approach is to define dependency ordering in terms of the modification order of a given object. We cannot leverage happens before or synchronizes with because doing so would introduce spurious ordering constraints that are inconsistent with data dependency ordering.
First, we define "dependency-synchronizes with":
An evaluation A that performs a release operation on an object M dependency-synchronizes with an evaluation B that performs a dependency operation on M and reads a value written by any side effect in the release sequence headed by A.
Next, we define "dependency tree" (or, perhaps more accurately, attempt to do so):
An evaluation H that performs a dependency operation on an object M heads a dependency tree, and is also a member of that dependency tree. Any subsequent evaluation that consumes the result of a prior evaluation that is a member of H's dependency tree is also a member of H's dependency tree, unless that prior evaluation is an unannotated formal parameter or is a return value from a function whose function prototype specifies an unannotated return value. [Note: dependency annotations are described in N2361.] [Note: a given evaluation can be a member of multiple dependency trees.]
Finally, we present the data-dependency constraints:
If a value computation A of object M happens before a release operation X that dependency-synchronizes with an evaluation H, and if evaluation H's dependency tree contains a value computation B of object M, then the value computed by B must either be the same as that computed by A or shall correspond to a value stored by a side-effect Y that occurs later than A in M's modification order.
If a value computation A of object M happens before a release operation X that dependency-synchronizes with an evaluation H, and if evaluation H's dependency tree contains a side effect Y that modifies object M, then the value computed by A shall precede that stored by Y in M's modification order.
If a side effect X that modifies object M happens before a release operation Y that dependency-synchronizes with an evaluation H, and if evaluation H's dependency tree contains a value computation B of M, then the value computed by B shall either equal the value stored by side effect X, or be the value stored by some side effect Z that modifies M, where Z follows X in the modification order of M.
If a side-effect X that modifies object M happens before a release operation Y that dependency-synchronizes with an evaluation H, and if evaluation H's dependency tree contains a side effect Z that also modifies object M, then Z must follow X in M's modification order.