| 1 |
|
| 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 | *
|
| 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
|
| 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.
|
| 59 | *
|
| 60 | * Memory ordering
|
| 61 | * ===============
|
| 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 |
|
| 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/refcount_types.h>
|
| 100 | #include <linux/spinlock_types.h>
|
| 101 |
|
| 102 | struct mutex;
|
| 103 |
|
| 104 | #define REFCOUNT_INIT(n) { .refs = ATOMIC_INIT(n), }
|
| 105 | #define REFCOUNT_MAX INT_MAX
|
| 106 | #define REFCOUNT_SATURATED (INT_MIN / 2)
|
| 107 |
|
| 108 | enum refcount_saturation_type {
|
| 109 | REFCOUNT_ADD_NOT_ZERO_OVF,
|
| 110 | REFCOUNT_ADD_OVF,
|
| 111 | REFCOUNT_ADD_UAF,
|
| 112 | REFCOUNT_SUB_UAF,
|
| 113 | REFCOUNT_DEC_LEAK,
|
| 114 | };
|
| 115 |
|
| 116 | void refcount_warn_saturate(refcount_t *r, enum refcount_saturation_type t);
|
| 117 |
|
| 118 | |
| 119 | * refcount_set - set a refcount's value
|
| 120 | * @r: the refcount
|
| 121 | * @n: value to which the refcount will be set
|
| 122 |
|
| 123 | static inline void refcount_set(refcount_t *r, int n)
|
| 124 | {
|
| 125 | atomic_set(&r->refs, n);
|
| 126 | }
|
| 127 |
|
| 128 | |
| 129 | * refcount_read - get a refcount's value
|
| 130 | * @r: the refcount
|
| 131 | *
|
| 132 | * Return: the refcount's value
|
| 133 |
|
| 134 | static inline unsigned int refcount_read(const refcount_t *r)
|
| 135 | {
|
| 136 | return atomic_read(&r->refs);
|
| 137 | }
|
| 138 |
|
| 139 | static inline __must_check bool __refcount_add_not_zero(int i, refcount_t *r, int *oldp)
|
| 140 | {
|
| 141 | int old = refcount_read(r);
|
| 142 |
|
| 143 | do {
|
| 144 | if (!old)
|
| 145 | break;
|
| 146 | } while (!atomic_try_cmpxchg_relaxed(&r->refs, &old, old + i));
|
| 147 |
|
| 148 | if (oldp)
|
| 149 | *oldp = old;
|
| 150 |
|
| 151 | if (unlikely(old < 0 || old + i < 0))
|
| 152 | refcount_warn_saturate(r, REFCOUNT_ADD_NOT_ZERO_OVF);
|
| 153 |
|
| 154 | return old;
|
| 155 | }
|
| 156 |
|
| 157 | |
| 158 | * refcount_add_not_zero - add a value to a refcount unless it is 0
|
| 159 | * @i: the value to add to the refcount
|
| 160 | * @r: the refcount
|
| 161 | *
|
| 162 | * Will saturate at REFCOUNT_SATURATED and WARN.
|
| 163 | *
|
| 164 | * Provides no memory ordering, it is assumed the caller has guaranteed the
|
| 165 | * object memory to be stable (RCU, etc.). It does provide a control dependency
|
| 166 | * and thereby orders future stores. See the comment on top.
|
| 167 | *
|
| 168 | * Use of this function is not recommended for the normal reference counting
|
| 169 | * use case in which references are taken and released one at a time. In these
|
| 170 | * cases, refcount_inc(), or one of its variants, should instead be used to
|
| 171 | * increment a reference count.
|
| 172 | *
|
| 173 | * Return: false if the passed refcount is 0, true otherwise
|
| 174 |
|
| 175 | static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r)
|
| 176 | {
|
| 177 | return __refcount_add_not_zero(i, r, NULL);
|
| 178 | }
|
| 179 |
|
| 180 | static inline void __refcount_add(int i, refcount_t *r, int *oldp)
|
| 181 | {
|
| 182 | int old = atomic_fetch_add_relaxed(i, &r->refs);
|
| 183 |
|
| 184 | if (oldp)
|
| 185 | *oldp = old;
|
| 186 |
|
| 187 | if (unlikely(!old))
|
| 188 | refcount_warn_saturate(r, REFCOUNT_ADD_UAF);
|
| 189 | else if (unlikely(old < 0 || old + i < 0))
|
| 190 | refcount_warn_saturate(r, REFCOUNT_ADD_OVF);
|
| 191 | }
|
| 192 |
|
| 193 | |
| 194 | * refcount_add - add a value to a refcount
|
| 195 | * @i: the value to add to the refcount
|
| 196 | * @r: the refcount
|
| 197 | *
|
| 198 | * Similar to atomic_add(), but will saturate at REFCOUNT_SATURATED and WARN.
|
| 199 | *
|
| 200 | * Provides no memory ordering, it is assumed the caller has guaranteed the
|
| 201 | * object memory to be stable (RCU, etc.). It does provide a control dependency
|
| 202 | * and thereby orders future stores. See the comment on top.
|
| 203 | *
|
| 204 | * Use of this function is not recommended for the normal reference counting
|
| 205 | * use case in which references are taken and released one at a time. In these
|
| 206 | * cases, refcount_inc(), or one of its variants, should instead be used to
|
| 207 | * increment a reference count.
|
| 208 |
|
| 209 | static inline void refcount_add(int i, refcount_t *r)
|
| 210 | {
|
| 211 | __refcount_add(i, r, NULL);
|
| 212 | }
|
| 213 |
|
| 214 | static inline __must_check bool __refcount_inc_not_zero(refcount_t *r, int *oldp)
|
| 215 | {
|
| 216 | return __refcount_add_not_zero(1, r, oldp);
|
| 217 | }
|
| 218 |
|
| 219 | |
| 220 | * refcount_inc_not_zero - increment a refcount unless it is 0
|
| 221 | * @r: the refcount to increment
|
| 222 | *
|
| 223 | * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED
|
| 224 | * and WARN.
|
| 225 | *
|
| 226 | * Provides no memory ordering, it is assumed the caller has guaranteed the
|
| 227 | * object memory to be stable (RCU, etc.). It does provide a control dependency
|
| 228 | * and thereby orders future stores. See the comment on top.
|
| 229 | *
|
| 230 | * Return: true if the increment was successful, false otherwise
|
| 231 |
|
| 232 | static inline __must_check bool refcount_inc_not_zero(refcount_t *r)
|
| 233 | {
|
| 234 | return __refcount_inc_not_zero(r, NULL);
|
| 235 | }
|
| 236 |
|
| 237 | static inline void __refcount_inc(refcount_t *r, int *oldp)
|
| 238 | {
|
| 239 | __refcount_add(1, r, oldp);
|
| 240 | }
|
| 241 |
|
| 242 | |
| 243 | * refcount_inc - increment a refcount
|
| 244 | * @r: the refcount to increment
|
| 245 | *
|
| 246 | * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN.
|
| 247 | *
|
| 248 | * Provides no memory ordering, it is assumed the caller already has a
|
| 249 | * reference on the object.
|
| 250 | *
|
| 251 | * Will WARN if the refcount is 0, as this represents a possible use-after-free
|
| 252 | * condition.
|
| 253 |
|
| 254 | static inline void refcount_inc(refcount_t *r)
|
| 255 | {
|
| 256 | __refcount_inc(r, NULL);
|
| 257 | }
|
| 258 |
|
| 259 | static inline __must_check bool __refcount_sub_and_test(int i, refcount_t *r, int *oldp)
|
| 260 | {
|
| 261 | int old = atomic_fetch_sub_release(i, &r->refs);
|
| 262 |
|
| 263 | if (oldp)
|
| 264 | *oldp = old;
|
| 265 |
|
| 266 | if (old == i) {
|
| 267 | smp_acquire__after_ctrl_dep();
|
| 268 | return true;
|
| 269 | }
|
| 270 |
|
| 271 | if (unlikely(old < 0 || old - i < 0))
|
| 272 | refcount_warn_saturate(r, REFCOUNT_SUB_UAF);
|
| 273 |
|
| 274 | return false;
|
| 275 | }
|
| 276 |
|
| 277 | |
| 278 | * refcount_sub_and_test - subtract from a refcount and test if it is 0
|
| 279 | * @i: amount to subtract from the refcount
|
| 280 | * @r: the refcount
|
| 281 | *
|
| 282 | * Similar to atomic_dec_and_test(), but it will WARN, return false and
|
| 283 | * ultimately leak on underflow and will fail to decrement when saturated
|
| 284 | * 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 | * Use of this function is not recommended for the normal reference counting
|
| 291 | * use case in which references are taken and released one at a time. In these
|
| 292 | * cases, refcount_dec(), or one of its variants, should instead be used to
|
| 293 | * decrement a reference count.
|
| 294 | *
|
| 295 | * Return: true if the resulting refcount is 0, false otherwise
|
| 296 |
|
| 297 | static inline __must_check bool refcount_sub_and_test(int i, refcount_t *r)
|
| 298 | {
|
| 299 | return __refcount_sub_and_test(i, r, NULL);
|
| 300 | }
|
| 301 |
|
| 302 | static inline __must_check bool __refcount_dec_and_test(refcount_t *r, int *oldp)
|
| 303 | {
|
| 304 | return __refcount_sub_and_test(1, r, oldp);
|
| 305 | }
|
| 306 |
|
| 307 | |
| 308 | * refcount_dec_and_test - decrement a refcount and test if it is 0
|
| 309 | * @r: the refcount
|
| 310 | *
|
| 311 | * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
|
| 312 | * decrement when saturated at REFCOUNT_SATURATED.
|
| 313 | *
|
| 314 | * Provides release memory ordering, such that prior loads and stores are done
|
| 315 | * before, and provides an acquire ordering on success such that free()
|
| 316 | * must come after.
|
| 317 | *
|
| 318 | * Return: true if the resulting refcount is 0, false otherwise
|
| 319 |
|
| 320 | static inline __must_check bool refcount_dec_and_test(refcount_t *r)
|
| 321 | {
|
| 322 | return __refcount_dec_and_test(r, NULL);
|
| 323 | }
|
| 324 |
|
| 325 | static inline void __refcount_dec(refcount_t *r, int *oldp)
|
| 326 | {
|
| 327 | int old = atomic_fetch_sub_release(1, &r->refs);
|
| 328 |
|
| 329 | if (oldp)
|
| 330 | *oldp = old;
|
| 331 |
|
| 332 | if (unlikely(old <= 1))
|
| 333 | refcount_warn_saturate(r, REFCOUNT_DEC_LEAK);
|
| 334 | }
|
| 335 |
|
| 336 | |
| 337 | * refcount_dec - decrement a refcount
|
| 338 | * @r: the refcount
|
| 339 | *
|
| 340 | * Similar to atomic_dec(), it will WARN on underflow and fail to decrement
|
| 341 | * when saturated at REFCOUNT_SATURATED.
|
| 342 | *
|
| 343 | * Provides release memory ordering, such that prior loads and stores are done
|
| 344 | * before.
|
| 345 |
|
| 346 | static inline void refcount_dec(refcount_t *r)
|
| 347 | {
|
| 348 | __refcount_dec(r, NULL);
|
| 349 | }
|
| 350 |
|
| 351 | extern __must_check bool refcount_dec_if_one(refcount_t *r);
|
| 352 | extern __must_check bool refcount_dec_not_one(refcount_t *r);
|
| 353 | extern __must_check bool refcount_dec_and_mutex_lock(refcount_t *r, struct mutex *lock) __cond_acquires(lock);
|
| 354 | extern __must_check bool refcount_dec_and_lock(refcount_t *r, spinlock_t *lock) __cond_acquires(lock);
|
| 355 | extern __must_check bool refcount_dec_and_lock_irqsave(refcount_t *r,
|
| 356 | spinlock_t *lock,
|
| 357 | unsigned long *flags) __cond_acquires(lock);
|
| 358 | #endif
|