herd-representation.txt

  1#
  2# Legend:
  3#	R,	a Load event
  4#	W,	a Store event
  5#	F,	a Fence event
  6#	LKR,	a Lock-Read event
  7#	LKW,	a Lock-Write event
  8#	UL,	an Unlock event
  9#	LF,	a Lock-Fail event
 10#	RL,	a Read-Locked event
 11#	RU,	a Read-Unlocked event
 12#	R*,	a Load event included in RMW
 13#	W*,	a Store event included in RMW
 14#	SRCU,	a Sleepable-Read-Copy-Update event
 15#
 16#	po,	a Program-Order link
 17#	rmw,	a Read-Modify-Write link - every rmw link is a po link
 18#
 19# By convention, a blank line in a cell means "same as the preceding line".
 20#
 21# Note that the syntactic representation does not always match the sets and
 22# relations in linux-kernel.cat, due to redefinitions in linux-kernel.bell and
 23# lock.cat. For example, the po link between LKR and LKW is upgraded to an rmw
 24# link, and W[ACQUIRE] are not included in the Acquire set.
 25#
 26# Disclaimer.  The table includes representations of "add" and "and" operations;
 27# corresponding/identical representations of "sub", "inc", "dec" and "or", "xor",
 28# "andnot" operations are omitted.
 29#
 30    ------------------------------------------------------------------------------
 31    |                        C macro | Events                                    |
 32    ------------------------------------------------------------------------------
 33    |                    Non-RMW ops |                                           |
 34    ------------------------------------------------------------------------------
 35    |                      READ_ONCE | R[ONCE]                                   |
 36    |                    atomic_read |                                           |
 37    |                     WRITE_ONCE | W[ONCE]                                   |
 38    |                     atomic_set |                                           |
 39    |               smp_load_acquire | R[ACQUIRE]                                |
 40    |            atomic_read_acquire |                                           |
 41    |              smp_store_release | W[RELEASE]                                |
 42    |             atomic_set_release |                                           |
 43    |                   smp_store_mb | W[ONCE] ->po F[MB]                        |
 44    |                         smp_mb | F[MB]                                     |
 45    |                        smp_rmb | F[rmb]                                    |
 46    |                        smp_wmb | F[wmb]                                    |
 47    |          smp_mb__before_atomic | F[before-atomic]                          |
 48    |           smp_mb__after_atomic | F[after-atomic]                           |
 49    |                    spin_unlock | UL                                        |
 50    |                 spin_is_locked | On success: RL                            |
 51    |                                | On failure: RU                            |
 52    |         smp_mb__after_spinlock | F[after-spinlock]                         |
 53    |      smp_mb__after_unlock_lock | F[after-unlock-lock]                      |
 54    |                  rcu_read_lock | F[rcu-lock]                               |
 55    |                rcu_read_unlock | F[rcu-unlock]                             |
 56    |                synchronize_rcu | F[sync-rcu]                               |
 57    |                rcu_dereference | R[ONCE]                                   |
 58    |             rcu_assign_pointer | W[RELEASE]                                |
 59    |                 srcu_read_lock | R[srcu-lock]                              |
 60    |                 srcu_down_read |                                           |
 61    |               srcu_read_unlock | W[srcu-unlock]                            |
 62    |                   srcu_up_read |                                           |
 63    |               synchronize_srcu | SRCU[sync-srcu]                           |
 64    | smp_mb__after_srcu_read_unlock | F[after-srcu-read-unlock]                 |
 65    ------------------------------------------------------------------------------
 66    |       RMW ops w/o return value |                                           |
 67    ------------------------------------------------------------------------------
 68    |                     atomic_add | R*[NORETURN] ->rmw W*[NORETURN]           |
 69    |                     atomic_and |                                           |
 70    |                      spin_lock | LKR ->po LKW                              |
 71    ------------------------------------------------------------------------------
 72    |        RMW ops w/ return value |                                           |
 73    ------------------------------------------------------------------------------
 74    |              atomic_add_return | R*[MB] ->rmw W*[MB]                       |
 75    |               atomic_fetch_add |                                           |
 76    |               atomic_fetch_and |                                           |
 77    |                    atomic_xchg |                                           |
 78    |                           xchg |                                           |
 79    |            atomic_add_negative |                                           |
 80    |      atomic_add_return_relaxed | R*[ONCE] ->rmw W*[ONCE]                   |
 81    |       atomic_fetch_add_relaxed |                                           |
 82    |       atomic_fetch_and_relaxed |                                           |
 83    |            atomic_xchg_relaxed |                                           |
 84    |                   xchg_relaxed |                                           |
 85    |    atomic_add_negative_relaxed |                                           |
 86    |      atomic_add_return_acquire | R*[ACQUIRE] ->rmw W*[ACQUIRE]             |
 87    |       atomic_fetch_add_acquire |                                           |
 88    |       atomic_fetch_and_acquire |                                           |
 89    |            atomic_xchg_acquire |                                           |
 90    |                   xchg_acquire |                                           |
 91    |    atomic_add_negative_acquire |                                           |
 92    |      atomic_add_return_release | R*[RELEASE] ->rmw W*[RELEASE]             |
 93    |       atomic_fetch_add_release |                                           |
 94    |       atomic_fetch_and_release |                                           |
 95    |            atomic_xchg_release |                                           |
 96    |                   xchg_release |                                           |
 97    |    atomic_add_negative_release |                                           |
 98    ------------------------------------------------------------------------------
 99    |            Conditional RMW ops |                                           |
100    ------------------------------------------------------------------------------
101    |                 atomic_cmpxchg | On success: R*[MB] ->rmw W*[MB]           |
102    |                                | On failure: R*[MB]                        |
103    |                        cmpxchg |                                           |
104    |              atomic_add_unless |                                           |
105    |         atomic_cmpxchg_relaxed | On success: R*[ONCE] ->rmw W*[ONCE]       |
106    |                                | On failure: R*[ONCE]                      |
107    |         atomic_cmpxchg_acquire | On success: R*[ACQUIRE] ->rmw W*[ACQUIRE] |
108    |                                | On failure: R*[ACQUIRE]                   |
109    |         atomic_cmpxchg_release | On success: R*[RELEASE] ->rmw W*[RELEASE] |
110    |                                | On failure: R*[RELEASE]                   |
111    |                   spin_trylock | On success: LKR ->po LKW                  |
112    |                                | On failure: LF                            |
113    ------------------------------------------------------------------------------