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