282 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2 3/*4 * rcuref - A scalable reference count implementation for RCU managed objects5 *6 * rcuref is provided to replace open coded reference count implementations7 * based on atomic_t. It protects explicitely RCU managed objects which can8 * be visible even after the last reference has been dropped and the object9 * is heading towards destruction.10 *11 * A common usage pattern is:12 *13 * get()14 * rcu_read_lock();15 * p = get_ptr();16 * if (p && !atomic_inc_not_zero(&p->refcnt))17 * p = NULL;18 * rcu_read_unlock();19 * return p;20 *21 * put()22 * if (!atomic_dec_return(&->refcnt)) {23 * remove_ptr(p);24 * kfree_rcu((p, rcu);25 * }26 *27 * atomic_inc_not_zero() is implemented with a try_cmpxchg() loop which has28 * O(N^2) behaviour under contention with N concurrent operations.29 *30 * rcuref uses atomic_add_negative_relaxed() for the fast path, which scales31 * better under contention.32 *33 * Why not refcount?34 * =================35 *36 * In principle it should be possible to make refcount use the rcuref37 * scheme, but the destruction race described below cannot be prevented38 * unless the protected object is RCU managed.39 *40 * Theory of operation41 * ===================42 *43 * rcuref uses an unsigned integer reference counter. As long as the44 * counter value is greater than or equal to RCUREF_ONEREF and not larger45 * than RCUREF_MAXREF the reference is alive:46 *47 * ONEREF MAXREF SATURATED RELEASED DEAD NOREF48 * 0 0x7FFFFFFF 0x8000000 0xA0000000 0xBFFFFFFF 0xC0000000 0xE0000000 0xFFFFFFFF49 * <---valid --------> <-------saturation zone-------> <-----dead zone----->50 *51 * The get() and put() operations do unconditional increments and52 * decrements. The result is checked after the operation. This optimizes53 * for the fast path.54 *55 * If the reference count is saturated or dead, then the increments and56 * decrements are not harmful as the reference count still stays in the57 * respective zones and is always set back to STATURATED resp. DEAD. The58 * zones have room for 2^28 racing operations in each direction, which59 * makes it practically impossible to escape the zones.60 *61 * Once the last reference is dropped the reference count becomes62 * RCUREF_NOREF which forces rcuref_put() into the slowpath operation. The63 * slowpath then tries to set the reference count from RCUREF_NOREF to64 * RCUREF_DEAD via a cmpxchg(). This opens a small window where a65 * concurrent rcuref_get() can acquire the reference count and bring it66 * back to RCUREF_ONEREF or even drop the reference again and mark it DEAD.67 *68 * If the cmpxchg() succeeds then a concurrent rcuref_get() will result in69 * DEAD + 1, which is inside the dead zone. If that happens the reference70 * count is put back to DEAD.71 *72 * The actual race is possible due to the unconditional increment and73 * decrements in rcuref_get() and rcuref_put():74 *75 * T1 T276 * get() put()77 * if (atomic_add_negative(-1, &ref->refcnt))78 * succeeds-> atomic_cmpxchg(&ref->refcnt, NOREF, DEAD);79 *80 * atomic_add_negative(1, &ref->refcnt); <- Elevates refcount to DEAD + 181 *82 * As the result of T1's add is negative, the get() goes into the slow path83 * and observes refcnt being in the dead zone which makes the operation fail.84 *85 * Possible critical states:86 *87 * Context Counter References Operation88 * T1 0 1 init()89 * T2 1 2 get()90 * T1 0 1 put()91 * T2 -1 0 put() tries to mark dead92 * T1 0 1 get()93 * T2 0 1 put() mark dead fails94 * T1 -1 0 put() tries to mark dead95 * T1 DEAD 0 put() mark dead succeeds96 * T2 DEAD+1 0 get() fails and puts it back to DEAD97 *98 * Of course there are more complex scenarios, but the above illustrates99 * the working principle. The rest is left to the imagination of the100 * reader.101 *102 * Deconstruction race103 * ===================104 *105 * The release operation must be protected by prohibiting a grace period in106 * order to prevent a possible use after free:107 *108 * T1 T2109 * put() get()110 * // ref->refcnt = ONEREF111 * if (!atomic_add_negative(-1, &ref->refcnt))112 * return false; <- Not taken113 *114 * // ref->refcnt == NOREF115 * --> preemption116 * // Elevates ref->refcnt to ONEREF117 * if (!atomic_add_negative(1, &ref->refcnt))118 * return true; <- taken119 *120 * if (put(&p->ref)) { <-- Succeeds121 * remove_pointer(p);122 * kfree_rcu(p, rcu);123 * }124 *125 * RCU grace period ends, object is freed126 *127 * atomic_cmpxchg(&ref->refcnt, NOREF, DEAD); <- UAF128 *129 * This is prevented by disabling preemption around the put() operation as130 * that's in most kernel configurations cheaper than a rcu_read_lock() /131 * rcu_read_unlock() pair and in many cases even a NOOP. In any case it132 * prevents the grace period which keeps the object alive until all put()133 * operations complete.134 *135 * Saturation protection136 * =====================137 *138 * The reference count has a saturation limit RCUREF_MAXREF (INT_MAX).139 * Once this is exceedded the reference count becomes stale by setting it140 * to RCUREF_SATURATED, which will cause a memory leak, but it prevents141 * wrap arounds which obviously cause worse problems than a memory142 * leak. When saturation is reached a warning is emitted.143 *144 * Race conditions145 * ===============146 *147 * All reference count increment/decrement operations are unconditional and148 * only verified after the fact. This optimizes for the good case and takes149 * the occasional race vs. a dead or already saturated refcount into150 * account. The saturation and dead zones are large enough to accomodate151 * for that.152 *153 * Memory ordering154 * ===============155 *156 * Memory ordering rules are slightly relaxed wrt regular atomic_t functions157 * and provide only what is strictly required for refcounts.158 *159 * The increments are fully relaxed; these will not provide ordering. The160 * rationale is that whatever is used to obtain the object to increase the161 * reference count on will provide the ordering. For locked data162 * structures, its the lock acquire, for RCU/lockless data structures its163 * the dependent load.164 *165 * rcuref_get() provides a control dependency ordering future stores which166 * ensures that the object is not modified when acquiring a reference167 * fails.168 *169 * rcuref_put() provides release order, i.e. all prior loads and stores170 * will be issued before. It also provides a control dependency ordering171 * against the subsequent destruction of the object.172 *173 * If rcuref_put() successfully dropped the last reference and marked the174 * object DEAD it also provides acquire ordering.175 */176 177#include <linux/export.h>178#include <linux/rcuref.h>179 180/**181 * rcuref_get_slowpath - Slowpath of rcuref_get()182 * @ref: Pointer to the reference count183 *184 * Invoked when the reference count is outside of the valid zone.185 *186 * Return:187 * False if the reference count was already marked dead188 *189 * True if the reference count is saturated, which prevents the190 * object from being deconstructed ever.191 */192bool rcuref_get_slowpath(rcuref_t *ref)193{194 unsigned int cnt = atomic_read(&ref->refcnt);195 196 /*197 * If the reference count was already marked dead, undo the198 * increment so it stays in the middle of the dead zone and return199 * fail.200 */201 if (cnt >= RCUREF_RELEASED) {202 atomic_set(&ref->refcnt, RCUREF_DEAD);203 return false;204 }205 206 /*207 * If it was saturated, warn and mark it so. In case the increment208 * was already on a saturated value restore the saturation209 * marker. This keeps it in the middle of the saturation zone and210 * prevents the reference count from overflowing. This leaks the211 * object memory, but prevents the obvious reference count overflow212 * damage.213 */214 if (WARN_ONCE(cnt > RCUREF_MAXREF, "rcuref saturated - leaking memory"))215 atomic_set(&ref->refcnt, RCUREF_SATURATED);216 return true;217}218EXPORT_SYMBOL_GPL(rcuref_get_slowpath);219 220/**221 * rcuref_put_slowpath - Slowpath of __rcuref_put()222 * @ref: Pointer to the reference count223 *224 * Invoked when the reference count is outside of the valid zone.225 *226 * Return:227 * True if this was the last reference with no future references228 * possible. This signals the caller that it can safely schedule the229 * object, which is protected by the reference counter, for230 * deconstruction.231 *232 * False if there are still active references or the put() raced233 * with a concurrent get()/put() pair. Caller is not allowed to234 * deconstruct the protected object.235 */236bool rcuref_put_slowpath(rcuref_t *ref)237{238 unsigned int cnt = atomic_read(&ref->refcnt);239 240 /* Did this drop the last reference? */241 if (likely(cnt == RCUREF_NOREF)) {242 /*243 * Carefully try to set the reference count to RCUREF_DEAD.244 *245 * This can fail if a concurrent get() operation has246 * elevated it again or the corresponding put() even marked247 * it dead already. Both are valid situations and do not248 * require a retry. If this fails the caller is not249 * allowed to deconstruct the object.250 */251 if (!atomic_try_cmpxchg_release(&ref->refcnt, &cnt, RCUREF_DEAD))252 return false;253 254 /*255 * The caller can safely schedule the object for256 * deconstruction. Provide acquire ordering.257 */258 smp_acquire__after_ctrl_dep();259 return true;260 }261 262 /*263 * If the reference count was already in the dead zone, then this264 * put() operation is imbalanced. Warn, put the reference count back to265 * DEAD and tell the caller to not deconstruct the object.266 */267 if (WARN_ONCE(cnt >= RCUREF_RELEASED, "rcuref - imbalanced put()")) {268 atomic_set(&ref->refcnt, RCUREF_DEAD);269 return false;270 }271 272 /*273 * This is a put() operation on a saturated refcount. Restore the274 * mean saturation value and tell the caller to not deconstruct the275 * object.276 */277 if (cnt > RCUREF_MAXREF)278 atomic_set(&ref->refcnt, RCUREF_SATURATED);279 return false;280}281EXPORT_SYMBOL_GPL(rcuref_put_slowpath);282