]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
77e9971c WD |
2 | /* |
3 | * Variant of atomic_t specialized for reference counts. | |
4 | * | |
5 | * The interface matches the atomic_t interface (to aid in porting) but only | |
6 | * provides the few functions one should use for reference counting. | |
7 | * | |
dcb78649 WD |
8 | * Saturation semantics |
9 | * ==================== | |
10 | * | |
11 | * refcount_t differs from atomic_t in that the counter saturates at | |
12 | * REFCOUNT_SATURATED and will not move once there. This avoids wrapping the | |
13 | * counter and causing 'spurious' use-after-free issues. In order to avoid the | |
14 | * cost associated with introducing cmpxchg() loops into all of the saturating | |
15 | * operations, we temporarily allow the counter to take on an unchecked value | |
16 | * and then explicitly set it to REFCOUNT_SATURATED on detecting that underflow | |
17 | * or overflow has occurred. Although this is racy when multiple threads | |
18 | * access the refcount concurrently, by placing REFCOUNT_SATURATED roughly | |
19 | * equidistant from 0 and INT_MAX we minimise the scope for error: | |
20 | * | |
21 | * INT_MAX REFCOUNT_SATURATED UINT_MAX | |
22 | * 0 (0x7fff_ffff) (0xc000_0000) (0xffff_ffff) | |
23 | * +--------------------------------+----------------+----------------+ | |
24 | * <---------- bad value! ----------> | |
25 | * | |
26 | * (in a signed view of the world, the "bad value" range corresponds to | |
27 | * a negative counter value). | |
28 | * | |
29 | * As an example, consider a refcount_inc() operation that causes the counter | |
30 | * to overflow: | |
31 | * | |
32 | * int old = atomic_fetch_add_relaxed(r); | |
33 | * // old is INT_MAX, refcount now INT_MIN (0x8000_0000) | |
34 | * if (old < 0) | |
35 | * atomic_set(r, REFCOUNT_SATURATED); | |
36 | * | |
37 | * If another thread also performs a refcount_inc() operation between the two | |
38 | * atomic operations, then the count will continue to edge closer to 0. If it | |
39 | * reaches a value of 1 before /any/ of the threads reset it to the saturated | |
40 | * value, then a concurrent refcount_dec_and_test() may erroneously free the | |
a13f58a0 JH |
41 | * underlying object. |
42 | * Linux limits the maximum number of tasks to PID_MAX_LIMIT, which is currently | |
43 | * 0x400000 (and can't easily be raised in the future beyond FUTEX_TID_MASK). | |
44 | * With the current PID limit, if no batched refcounting operations are used and | |
45 | * the attacker can't repeatedly trigger kernel oopses in the middle of refcount | |
46 | * operations, this makes it impossible for a saturated refcount to leave the | |
47 | * saturation range, even if it is possible for multiple uses of the same | |
48 | * refcount to nest in the context of a single task: | |
49 | * | |
50 | * (UINT_MAX+1-REFCOUNT_SATURATED) / PID_MAX_LIMIT = | |
51 | * 0x40000000 / 0x400000 = 0x100 = 256 | |
52 | * | |
53 | * If hundreds of references are added/removed with a single refcounting | |
54 | * operation, it may potentially be possible to leave the saturation range; but | |
55 | * given the precise timing details involved with the round-robin scheduling of | |
56 | * each thread manipulating the refcount and the need to hit the race multiple | |
57 | * times in succession, there doesn't appear to be a practical avenue of attack | |
58 | * even if using refcount_add() operations with larger increments. | |
dcb78649 WD |
59 | * |
60 | * Memory ordering | |
61 | * =============== | |
77e9971c WD |
62 | * |
63 | * Memory ordering rules are slightly relaxed wrt regular atomic_t functions | |
64 | * and provide only what is strictly required for refcounts. | |
65 | * | |
66 | * The increments are fully relaxed; these will not provide ordering. The | |
67 | * rationale is that whatever is used to obtain the object we're increasing the | |
68 | * reference count on will provide the ordering. For locked data structures, | |
69 | * its the lock acquire, for RCU/lockless data structures its the dependent | |
70 | * load. | |
71 | * | |
72 | * Do note that inc_not_zero() provides a control dependency which will order | |
73 | * future stores against the inc, this ensures we'll never modify the object | |
74 | * if we did not in fact acquire a reference. | |
75 | * | |
76 | * The decrements will provide release order, such that all the prior loads and | |
77 | * stores will be issued before, it also provides a control dependency, which | |
78 | * will order us against the subsequent free(). | |
79 | * | |
80 | * The control dependency is against the load of the cmpxchg (ll/sc) that | |
81 | * succeeded. This means the stores aren't fully ordered, but this is fine | |
82 | * because the 1->0 transition indicates no concurrency. | |
83 | * | |
84 | * Note that the allocator is responsible for ordering things between free() | |
85 | * and alloc(). | |
86 | * | |
87 | * The decrements dec_and_test() and sub_and_test() also provide acquire | |
88 | * ordering on success. | |
89 | * | |
90 | */ | |
91 | ||
fb041bb7 WD |
92 | #ifndef _LINUX_REFCOUNT_H |
93 | #define _LINUX_REFCOUNT_H | |
94 | ||
95 | #include <linux/atomic.h> | |
96 | #include <linux/bug.h> | |
97 | #include <linux/compiler.h> | |
98 | #include <linux/limits.h> | |
99 | #include <linux/spinlock_types.h> | |
100 | ||
101 | struct mutex; | |
102 | ||
103 | /** | |
104 | * struct refcount_t - variant of atomic_t specialized for reference counts | |
105 | * @refs: atomic_t counter field | |
106 | * | |
107 | * The counter saturates at REFCOUNT_SATURATED and will not move once | |
108 | * there. This avoids wrapping the counter and causing 'spurious' | |
109 | * use-after-free bugs. | |
110 | */ | |
111 | typedef struct refcount_struct { | |
112 | atomic_t refs; | |
113 | } refcount_t; | |
114 | ||
115 | #define REFCOUNT_INIT(n) { .refs = ATOMIC_INIT(n), } | |
116 | #define REFCOUNT_MAX INT_MAX | |
117 | #define REFCOUNT_SATURATED (INT_MIN / 2) | |
118 | ||
119 | enum refcount_saturation_type { | |
120 | REFCOUNT_ADD_NOT_ZERO_OVF, | |
121 | REFCOUNT_ADD_OVF, | |
122 | REFCOUNT_ADD_UAF, | |
123 | REFCOUNT_SUB_UAF, | |
124 | REFCOUNT_DEC_LEAK, | |
125 | }; | |
126 | ||
127 | void refcount_warn_saturate(refcount_t *r, enum refcount_saturation_type t); | |
128 | ||
129 | /** | |
130 | * refcount_set - set a refcount's value | |
131 | * @r: the refcount | |
132 | * @n: value to which the refcount will be set | |
133 | */ | |
134 | static inline void refcount_set(refcount_t *r, int n) | |
135 | { | |
136 | atomic_set(&r->refs, n); | |
137 | } | |
138 | ||
139 | /** | |
140 | * refcount_read - get a refcount's value | |
141 | * @r: the refcount | |
142 | * | |
143 | * Return: the refcount's value | |
144 | */ | |
145 | static inline unsigned int refcount_read(const refcount_t *r) | |
146 | { | |
147 | return atomic_read(&r->refs); | |
148 | } | |
149 | ||
77e9971c WD |
150 | /** |
151 | * refcount_add_not_zero - add a value to a refcount unless it is 0 | |
152 | * @i: the value to add to the refcount | |
153 | * @r: the refcount | |
154 | * | |
155 | * Will saturate at REFCOUNT_SATURATED and WARN. | |
156 | * | |
157 | * Provides no memory ordering, it is assumed the caller has guaranteed the | |
158 | * object memory to be stable (RCU, etc.). It does provide a control dependency | |
159 | * and thereby orders future stores. See the comment on top. | |
160 | * | |
161 | * Use of this function is not recommended for the normal reference counting | |
162 | * use case in which references are taken and released one at a time. In these | |
163 | * cases, refcount_inc(), or one of its variants, should instead be used to | |
164 | * increment a reference count. | |
165 | * | |
166 | * Return: false if the passed refcount is 0, true otherwise | |
167 | */ | |
168 | static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r) | |
169 | { | |
dcb78649 | 170 | int old = refcount_read(r); |
77e9971c WD |
171 | |
172 | do { | |
dcb78649 WD |
173 | if (!old) |
174 | break; | |
175 | } while (!atomic_try_cmpxchg_relaxed(&r->refs, &old, old + i)); | |
77e9971c | 176 | |
1eb085d9 WD |
177 | if (unlikely(old < 0 || old + i < 0)) |
178 | refcount_warn_saturate(r, REFCOUNT_ADD_NOT_ZERO_OVF); | |
77e9971c | 179 | |
dcb78649 | 180 | return old; |
77e9971c WD |
181 | } |
182 | ||
183 | /** | |
184 | * refcount_add - add a value to a refcount | |
185 | * @i: the value to add to the refcount | |
186 | * @r: the refcount | |
187 | * | |
188 | * Similar to atomic_add(), but will saturate at REFCOUNT_SATURATED and WARN. | |
189 | * | |
190 | * Provides no memory ordering, it is assumed the caller has guaranteed the | |
191 | * object memory to be stable (RCU, etc.). It does provide a control dependency | |
192 | * and thereby orders future stores. See the comment on top. | |
193 | * | |
194 | * Use of this function is not recommended for the normal reference counting | |
195 | * use case in which references are taken and released one at a time. In these | |
196 | * cases, refcount_inc(), or one of its variants, should instead be used to | |
197 | * increment a reference count. | |
198 | */ | |
199 | static inline void refcount_add(int i, refcount_t *r) | |
200 | { | |
dcb78649 WD |
201 | int old = atomic_fetch_add_relaxed(i, &r->refs); |
202 | ||
1eb085d9 WD |
203 | if (unlikely(!old)) |
204 | refcount_warn_saturate(r, REFCOUNT_ADD_UAF); | |
205 | else if (unlikely(old < 0 || old + i < 0)) | |
206 | refcount_warn_saturate(r, REFCOUNT_ADD_OVF); | |
77e9971c WD |
207 | } |
208 | ||
209 | /** | |
210 | * refcount_inc_not_zero - increment a refcount unless it is 0 | |
211 | * @r: the refcount to increment | |
212 | * | |
213 | * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED | |
214 | * and WARN. | |
215 | * | |
216 | * Provides no memory ordering, it is assumed the caller has guaranteed the | |
217 | * object memory to be stable (RCU, etc.). It does provide a control dependency | |
218 | * and thereby orders future stores. See the comment on top. | |
219 | * | |
220 | * Return: true if the increment was successful, false otherwise | |
221 | */ | |
222 | static inline __must_check bool refcount_inc_not_zero(refcount_t *r) | |
223 | { | |
dcb78649 | 224 | return refcount_add_not_zero(1, r); |
77e9971c WD |
225 | } |
226 | ||
227 | /** | |
228 | * refcount_inc - increment a refcount | |
229 | * @r: the refcount to increment | |
230 | * | |
231 | * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN. | |
232 | * | |
233 | * Provides no memory ordering, it is assumed the caller already has a | |
234 | * reference on the object. | |
235 | * | |
236 | * Will WARN if the refcount is 0, as this represents a possible use-after-free | |
237 | * condition. | |
238 | */ | |
239 | static inline void refcount_inc(refcount_t *r) | |
240 | { | |
dcb78649 | 241 | refcount_add(1, r); |
77e9971c WD |
242 | } |
243 | ||
244 | /** | |
245 | * refcount_sub_and_test - subtract from a refcount and test if it is 0 | |
246 | * @i: amount to subtract from the refcount | |
247 | * @r: the refcount | |
248 | * | |
249 | * Similar to atomic_dec_and_test(), but it will WARN, return false and | |
250 | * ultimately leak on underflow and will fail to decrement when saturated | |
251 | * at REFCOUNT_SATURATED. | |
252 | * | |
253 | * Provides release memory ordering, such that prior loads and stores are done | |
254 | * before, and provides an acquire ordering on success such that free() | |
255 | * must come after. | |
256 | * | |
257 | * Use of this function is not recommended for the normal reference counting | |
258 | * use case in which references are taken and released one at a time. In these | |
259 | * cases, refcount_dec(), or one of its variants, should instead be used to | |
260 | * decrement a reference count. | |
261 | * | |
262 | * Return: true if the resulting refcount is 0, false otherwise | |
263 | */ | |
264 | static inline __must_check bool refcount_sub_and_test(int i, refcount_t *r) | |
265 | { | |
dcb78649 | 266 | int old = atomic_fetch_sub_release(i, &r->refs); |
77e9971c | 267 | |
dcb78649 | 268 | if (old == i) { |
77e9971c WD |
269 | smp_acquire__after_ctrl_dep(); |
270 | return true; | |
271 | } | |
77e9971c | 272 | |
1eb085d9 WD |
273 | if (unlikely(old < 0 || old - i < 0)) |
274 | refcount_warn_saturate(r, REFCOUNT_SUB_UAF); | |
dcb78649 WD |
275 | |
276 | return false; | |
77e9971c WD |
277 | } |
278 | ||
279 | /** | |
280 | * refcount_dec_and_test - decrement a refcount and test if it is 0 | |
281 | * @r: the refcount | |
282 | * | |
283 | * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to | |
284 | * decrement when saturated at REFCOUNT_SATURATED. | |
285 | * | |
286 | * Provides release memory ordering, such that prior loads and stores are done | |
287 | * before, and provides an acquire ordering on success such that free() | |
288 | * must come after. | |
289 | * | |
290 | * Return: true if the resulting refcount is 0, false otherwise | |
291 | */ | |
292 | static inline __must_check bool refcount_dec_and_test(refcount_t *r) | |
293 | { | |
294 | return refcount_sub_and_test(1, r); | |
295 | } | |
296 | ||
297 | /** | |
298 | * refcount_dec - decrement a refcount | |
299 | * @r: the refcount | |
300 | * | |
301 | * Similar to atomic_dec(), it will WARN on underflow and fail to decrement | |
302 | * when saturated at REFCOUNT_SATURATED. | |
303 | * | |
304 | * Provides release memory ordering, such that prior loads and stores are done | |
305 | * before. | |
306 | */ | |
307 | static inline void refcount_dec(refcount_t *r) | |
308 | { | |
1eb085d9 WD |
309 | if (unlikely(atomic_fetch_sub_release(1, &r->refs) <= 1)) |
310 | refcount_warn_saturate(r, REFCOUNT_DEC_LEAK); | |
dcb78649 | 311 | } |
f405df5d | 312 | |
29dee3c0 PZ |
313 | extern __must_check bool refcount_dec_if_one(refcount_t *r); |
314 | extern __must_check bool refcount_dec_not_one(refcount_t *r); | |
315 | extern __must_check bool refcount_dec_and_mutex_lock(refcount_t *r, struct mutex *lock); | |
316 | extern __must_check bool refcount_dec_and_lock(refcount_t *r, spinlock_t *lock); | |
7ea959c4 AMG |
317 | extern __must_check bool refcount_dec_and_lock_irqsave(refcount_t *r, |
318 | spinlock_t *lock, | |
319 | unsigned long *flags); | |
f405df5d | 320 | #endif /* _LINUX_REFCOUNT_H */ |