Commit | Line | Data |
---|---|---|
b6e859f6 ER |
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 | |
a9251553 | 20 | tools/memory-model/Documentation/explanation.txt. |
b6e859f6 ER |
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 :c:func:`READ_ONCE`/:c:func:`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 :c:func:`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 | :c:func:`smp_store_release`. | |
56 | ||
47b8f3ab ER |
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 | :c:func:`smp_acquire__after_ctrl_dep`. | |
63 | ||
b6e859f6 ER |
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 | * :c:func:`atomic_set` --> :c:func:`refcount_set` | |
82 | * :c:func:`atomic_read` --> :c:func:`refcount_read` | |
83 | ||
84 | Memory ordering guarantee changes: | |
85 | ||
86 | * none (both fully unordered) | |
87 | ||
88 | ||
89 | case 2) - increment-based ops that return no value | |
90 | -------------------------------------------------- | |
91 | ||
92 | Function changes: | |
93 | ||
94 | * :c:func:`atomic_inc` --> :c:func:`refcount_inc` | |
95 | * :c:func:`atomic_add` --> :c:func:`refcount_add` | |
96 | ||
97 | Memory ordering guarantee changes: | |
98 | ||
99 | * none (both fully unordered) | |
100 | ||
101 | case 3) - decrement-based RMW ops that return no value | |
102 | ------------------------------------------------------ | |
103 | ||
104 | Function changes: | |
105 | ||
106 | * :c:func:`atomic_dec` --> :c:func:`refcount_dec` | |
107 | ||
108 | Memory ordering guarantee changes: | |
109 | ||
110 | * fully unordered --> RELEASE ordering | |
111 | ||
112 | ||
113 | case 4) - increment-based RMW ops that return a value | |
114 | ----------------------------------------------------- | |
115 | ||
116 | Function changes: | |
117 | ||
118 | * :c:func:`atomic_inc_not_zero` --> :c:func:`refcount_inc_not_zero` | |
119 | * no atomic counterpart --> :c:func:`refcount_add_not_zero` | |
120 | ||
121 | Memory ordering guarantees changes: | |
122 | ||
123 | * fully ordered --> control dependency on success for stores | |
124 | ||
125 | .. note:: We really assume here that necessary ordering is provided as a | |
126 | result of obtaining pointer to the object! | |
127 | ||
128 | ||
47b8f3ab ER |
129 | case 5) - generic dec/sub decrement-based RMW ops that return a value |
130 | --------------------------------------------------------------------- | |
b6e859f6 ER |
131 | |
132 | Function changes: | |
133 | ||
134 | * :c:func:`atomic_dec_and_test` --> :c:func:`refcount_dec_and_test` | |
135 | * :c:func:`atomic_sub_and_test` --> :c:func:`refcount_sub_and_test` | |
47b8f3ab ER |
136 | |
137 | Memory ordering guarantees changes: | |
138 | ||
139 | * fully ordered --> RELEASE ordering + ACQUIRE ordering on success | |
140 | ||
141 | ||
142 | case 6) other decrement-based RMW ops that return a value | |
143 | --------------------------------------------------------- | |
144 | ||
145 | Function changes: | |
146 | ||
b6e859f6 ER |
147 | * no atomic counterpart --> :c:func:`refcount_dec_if_one` |
148 | * ``atomic_add_unless(&var, -1, 1)`` --> ``refcount_dec_not_one(&var)`` | |
149 | ||
150 | Memory ordering guarantees changes: | |
151 | ||
152 | * fully ordered --> RELEASE ordering + control dependency | |
153 | ||
154 | .. note:: :c:func:`atomic_add_unless` only provides full order on success. | |
155 | ||
156 | ||
47b8f3ab | 157 | case 7) - lock-based RMW |
b6e859f6 ER |
158 | ------------------------ |
159 | ||
160 | Function changes: | |
161 | ||
162 | * :c:func:`atomic_dec_and_lock` --> :c:func:`refcount_dec_and_lock` | |
163 | * :c:func:`atomic_dec_and_mutex_lock` --> :c:func:`refcount_dec_and_mutex_lock` | |
164 | ||
165 | Memory ordering guarantees changes: | |
166 | ||
167 | * fully ordered --> RELEASE ordering + control dependency + hold | |
168 | :c:func:`spin_lock` on success |