refcount-vs-atomic.rst

  1===================================
  2refcount_t API compared to atomic_t
  3===================================
  4
  5.. contents:: :local:
  6
  7Introduction
  8============
  9
 10The goal of refcount_t API is to provide a minimal API for implementing
 11an object's reference counters. While a generic architecture-independent
 12implementation from lib/refcount.c uses atomic operations underneath,
 13there are a number of differences between some of the ``refcount_*()`` and
 14``atomic_*()`` functions with regards to the memory ordering guarantees.
 15This document outlines the differences and provides respective examples
 16in order to help maintainers validate their code against the change in
 17these memory ordering guarantees.
 18
 19The terms used through this document try to follow the formal LKMM defined in
 20tools/memory-model/Documentation/explanation.txt.
 21
 22memory-barriers.txt and atomic_t.txt provide more background to the
 23memory ordering in general and for atomic operations specifically.
 24
 25Relevant types of memory ordering
 26=================================
 27
 28.. note:: The following section only covers some of the memory
 29   ordering types that are relevant for the atomics and reference
 30   counters and used through this document. For a much broader picture
 31   please consult memory-barriers.txt document.
 32
 33In the absence of any memory ordering guarantees (i.e. fully unordered)
 34atomics & refcounters only provide atomicity and
 35program order (po) relation (on the same CPU). It guarantees that
 36each ``atomic_*()`` and ``refcount_*()`` operation is atomic and instructions
 37are executed in program order on a single CPU.
 38This is implemented using READ_ONCE()/WRITE_ONCE() and
 39compare-and-swap primitives.
 40
 41A strong (full) memory ordering guarantees that all prior loads and
 42stores (all po-earlier instructions) on the same CPU are completed
 43before any po-later instruction is executed on the same CPU.
 44It also guarantees that all po-earlier stores on the same CPU
 45and all propagated stores from other CPUs must propagate to all
 46other CPUs before any po-later instruction is executed on the original
 47CPU (A-cumulative property). This is implemented using smp_mb().
 48
 49A RELEASE memory ordering guarantees that all prior loads and
 50stores (all po-earlier instructions) on the same CPU are completed
 51before the operation. It also guarantees that all po-earlier
 52stores on the same CPU and all propagated stores from other CPUs
 53must propagate to all other CPUs before the release operation
 54(A-cumulative property). This is implemented using
 55smp_store_release().
 56
 57An ACQUIRE memory ordering guarantees that all post loads and
 58stores (all po-later instructions) on the same CPU are
 59completed after the acquire operation. It also guarantees that all
 60po-later stores on the same CPU must propagate to all other CPUs
 61after the acquire operation executes. This is implemented using
 62smp_acquire__after_ctrl_dep().
 63
 64A control dependency (on success) for refcounters guarantees that
 65if a reference for an object was successfully obtained (reference
 66counter increment or addition happened, function returned true),
 67then further stores are ordered against this operation.
 68Control dependency on stores are not implemented using any explicit
 69barriers, but rely on CPU not to speculate on stores. This is only
 70a single CPU relation and provides no guarantees for other CPUs.
 71
 72
 73Comparison of functions
 74=======================
 75
 76case 1) - non-"Read/Modify/Write" (RMW) ops
 77-------------------------------------------
 78
 79Function changes:
 80
 81 * atomic_set() --> refcount_set()
 82 * atomic_read() --> refcount_read()
 83
 84Memory ordering guarantee changes:
 85
 86 * none (both fully unordered)
 87
 88
 89case 2) - non-"Read/Modify/Write" (RMW) ops with release ordering
 90-----------------------------------------------------------------
 91
 92Function changes:
 93
 94 * atomic_set_release() --> refcount_set_release()
 95
 96Memory ordering guarantee changes:
 97
 98 * none (both provide RELEASE ordering)
 99
100
101case 3) - increment-based ops that return no value
102--------------------------------------------------
103
104Function changes:
105
106 * atomic_inc() --> refcount_inc()
107 * atomic_add() --> refcount_add()
108
109Memory ordering guarantee changes:
110
111 * none (both fully unordered)
112
113case 4) - decrement-based RMW ops that return no value
114------------------------------------------------------
115
116Function changes:
117
118 * atomic_dec() --> refcount_dec()
119
120Memory ordering guarantee changes:
121
122 * fully unordered --> RELEASE ordering
123
124
125case 5) - increment-based RMW ops that return a value
126-----------------------------------------------------
127
128Function changes:
129
130 * atomic_inc_not_zero() --> refcount_inc_not_zero()
131 * no atomic counterpart --> refcount_add_not_zero()
132
133Memory ordering guarantees changes:
134
135 * fully ordered --> control dependency on success for stores
136
137.. note:: We really assume here that necessary ordering is provided as a
138   result of obtaining pointer to the object!
139
140
141case 6) - increment-based RMW ops with acquire ordering that return a value
142---------------------------------------------------------------------------
143
144Function changes:
145
146 * atomic_inc_not_zero() --> refcount_inc_not_zero_acquire()
147 * no atomic counterpart --> refcount_add_not_zero_acquire()
148
149Memory ordering guarantees changes:
150
151 * fully ordered --> ACQUIRE ordering on success
152
153
154case 7) - generic dec/sub decrement-based RMW ops that return a value
155---------------------------------------------------------------------
156
157Function changes:
158
159 * atomic_dec_and_test() --> refcount_dec_and_test()
160 * atomic_sub_and_test() --> refcount_sub_and_test()
161
162Memory ordering guarantees changes:
163
164 * fully ordered --> RELEASE ordering + ACQUIRE ordering on success
165
166
167case 8) other decrement-based RMW ops that return a value
168---------------------------------------------------------
169
170Function changes:
171
172 * no atomic counterpart --> refcount_dec_if_one()
173 * ``atomic_add_unless(&var, -1, 1)`` --> ``refcount_dec_not_one(&var)``
174
175Memory ordering guarantees changes:
176
177 * fully ordered --> RELEASE ordering + control dependency
178
179.. note:: atomic_add_unless() only provides full order on success.
180
181
182case 9) - lock-based RMW
183------------------------
184
185Function changes:
186
187 * atomic_dec_and_lock() --> refcount_dec_and_lock()
188 * atomic_dec_and_mutex_lock() --> refcount_dec_and_mutex_lock()
189
190Memory ordering guarantees changes:
191
192 * fully ordered --> RELEASE ordering + control dependency + hold
193   spin_lock() on success