doc/notes/fence.txt

   1 -------------------------------------------------------------------------------
   2  Fence support:
   3 -------------------------------------------------------------------------------
   4
   5 [refer to release sequence notes for some definitions and similar (but simpler)
   6 algorithm]
   7
   8 Fences provide a few new modification order constraints as well as an
   9 interesting extension to release sequences, detailed in 29.3 (p4-p7) and 29.8
  10 (p2-p4).
  11
  12 The Section 29.3 references detail the modification order constraints
  13 established by sequentially-consistent fences.
  14
  15 The Section 29.8 references detail the behavior of release and acquire fences
  16 (note that memory_order_seq_cst is both release and acquire).
  17
  18 The text of these rules are provided at the end of this document for reference.
  19
  20 *******************************
  21 Seq-cst MO constraints (29.3 p4-p7)
  22 *******************************
  23
  24 [INCOMPLETE]
  25
  26 The statements given in the specification regarding sequentially consistent
  27 fences can be transformed into the following 4 modification order constraints.
  28
  29 29.3p4
  30
  31 If
  32     is_write(A) && is_read(B) && is_write(X) && is_fence(Y) &&
  33     is_seqcst(X) && is_seqcst(Y) && A != X &&
  34     same_var(X, A, B) &&
  35     A --rf-> B &&
  36     X --sc-> Y --sb-> B
  37 then
  38     X --mo-> A
  39
  40 Intuition/Implementation:
  41  * We may (but don't currently) limit our considertion of X to only the most
  42    recent (in the SC order) store to the same variable as A and B
  43  * We should consider the "most recent" seq-cst fence Y that precedes B
  44  * This search can be combined with the r_modification_order search, since we
  45    already iterate through the necessary stores X
  46
  47 29.3p5
  48
  49 If
  50     is_write(A) && is_read(B) && is_write(X) && is_fence(Y) &&
  51     is_seqcst(B) && is_seqcst(Y) &&
  52     same_var(X, A, B) &&
  53     A != X &&
  54     A --rf-> B &&
  55     X --sb-> Y --sc-> B
  56 then
  57     X --mo-> A
  58
  59 Intuition/Implementation:
  60  * We only need to examine the "most recent" qualifying store X that precedes Y;
  61    all other X will provide a weaker MO constraint
  62  * Search for the most recent fence Y in the same thread as A
  63  * We should consider the "most recent" write
  64
  65 For atomic operations A and B on an atomic object M, where A modifies M and B
  66 takes its value, if there is a memory_order_seq_cst fence X such that A is
  67 sequenced before X and B follows X in S, then B observes either the effects of
  68 A or a later modification of M in its modification order.
  69
  70 29.3p6
  71
  72 If
  73     is_write(A) && is_read(B) && is_write(X) && is_fence(Y) is_fence(Z) &&
  74     is_seqcst(Y) && is_seqcst(Z) &&
  75     same_var(X, A, B) &&
  76     A != X &&
  77     A --rf-> B &&
  78     X --sb-> Y --sc-> Z --sb-> B
  79 then
  80     X --mo-> A
  81
  82 Intuition/Implementation:
  83  * We should consider the "most recent" write
  84
  85 For atomic operations A and B on an atomic object M, where A modifies M and B
  86 takes its value, if there are memory_order_seq_cst fences X and Y such that A
  87 is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B
  88 observes either the effects of A or a later modification of M in its
  89 modification order.
  90
  91 29.3p7
  92
  93 For atomic operations A and B on an atomic object M, if there are
  94 memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is
  95 sequenced before B, and X precedes Y in S, then B occurs later than A in the
  96 modification order of M.
  97
  98
  99 *******************************
 100 Miscellaneous Notes
 101 *******************************
 102
 103 fence(memory_order_consume) acts like memory_order_release, so if we ever
 104 support consume, we must alias consume -> release
 105
 106 fence(memory_order_relaxed) is a no-op
 107
 108 *******************************
 109  Approximate Algorithm [incomplete; just copied from the (out-of-date) release
 110  sequence notes
 111 *******************************
 112
 113 Check read-write chain...
 114
 115 Given:
 116 current action = curr
 117 read from = rf
 118 Cases:
 119 * rf is NULL: return uncertain
 120 * rf is RMW:
 121         - if rf is release:
 122                 add rf to release heads
 123         - if rf is rel_acq:
 124                 return certain [note: we don't need to extend release sequence
 125                 further because this acquire will have synchronized already]
 126           else
 127                 return (recursively) "get release sequence head of rf"
 128 * if rf is release:
 129         add rf to release heads
 130         return certain
 131 * else, rf is relaxed write (NOT RMW)
 132   - check same thread
 133
 134 **************************************
 135  From the C++11 specification (N3337)
 136 **************************************
 137
 138 -------------
 139 Section 29.3
 140 -------------
 141
 142 29.3p4
 143
 144 For an atomic operation B that reads the value of an atomic object M, if there
 145 is a memory_order_seq_cst fence X sequenced before B, then B observes either
 146 the last memory_order_seq_cst modification of M preceding X in the total order
 147 S or a later modification of M in its modification order.
 148
 149 29.3p5
 150
 151 For atomic operations A and B on an atomic object M, where A modifies M and B
 152 takes its value, if there is a memory_order_seq_cst fence X such that A is
 153 sequenced before X and B follows X in S, then B observes either the effects of
 154 A or a later modification of M in its modification order.
 155
 156 29.3p6
 157
 158 For atomic operations A and B on an atomic object M, where A modifies M and B
 159 takes its value, if there are memory_order_seq_cst fences X and Y such that A
 160 is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B
 161 observes either the effects of A or a later modification of M in its
 162 modification order.
 163
 164 29.3p7
 165
 166 For atomic operations A and B on an atomic object M, if there are
 167 memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is
 168 sequenced before B, and X precedes Y in S, then B occurs later than A in the
 169 modification order of M.
 170
 171 -------------
 172 Section 29.8
 173 -------------
 174
 175 29.8p2
 176
 177 A release fence A synchronizes with an acquire fence B if there exist atomic
 178 operations X and Y, both operating on some atomic object M, such that A is
 179 sequenced before X, X modifies M, Y is sequenced before B, and Y reads the value
 180 written by X or a value written by any side effect in the hypothetical release
 181 sequence X would head if it were a release operation.
 182
 183 29.8p3
 184
 185 A release fence A synchronizes with an atomic operation B that performs an
 186 acquire operation on an atomic object M if there exists an atomic operation X
 187 such that A is sequenced before X, X modifies M, and B reads the value written
 188 by X or a value written by any side effect in the hypothetical release sequence
 189 X would head if it were a release operation.
 190
 191 29.8p4
 192
 193 An atomic operation A that is a release operation on an atomic object M
 194 synchronizes with an acquire fence B if there exists some atomic operation X on
 195 M such that X is sequenced before B and reads the value written by A or a value
 196 written by any side effect in the release sequence headed by A.