// SPDX-License-Identifier: GPL-2.0-only /* * rcuref - A scalable reference count implementation for RCU managed objects * * rcuref is provided to replace open coded reference count implementations * based on atomic_t. It protects explicitely RCU managed objects which can * be visible even after the last reference has been dropped and the object * is heading towards destruction. * * A common usage pattern is: * * get() *	rcu_read_lock(); *	p = get_ptr(); *	if (p && !atomic_inc_not_zero(&p->refcnt)) *		p = NULL; *	rcu_read_unlock(); *	return p; * * put() *	if (!atomic_dec_return(&->refcnt)) { *		remove_ptr(p); *		kfree_rcu((p, rcu); *	} * * atomic_inc_not_zero() is implemented with a try_cmpxchg() loop which has * O(N^2) behaviour under contention with N concurrent operations. * * rcuref uses atomic_add_negative_relaxed() for the fast path, which scales * better under contention. * * Why not refcount? * ================= * * In principle it should be possible to make refcount use the rcuref * scheme, but the destruction race described below cannot be prevented * unless the protected object is RCU managed. * * Theory of operation * =================== * * rcuref uses an unsigned integer reference counter. As long as the * counter value is greater than or equal to RCUREF_ONEREF and not larger * than RCUREF_MAXREF the reference is alive: * * ONEREF   MAXREF               SATURATED             RELEASED      DEAD    NOREF * 0        0x7FFFFFFF 0x8000000 0xA0000000 0xBFFFFFFF 0xC0000000 0xE0000000 0xFFFFFFFF * <---valid --------> <-------saturation zone-------> <-----dead zone-----> * * The get() and put() operations do unconditional increments and * decrements. The result is checked after the operation. This optimizes * for the fast path. * * If the reference count is saturated or dead, then the increments and * decrements are not harmful as the reference count still stays in the * respective zones and is always set back to STATURATED resp. DEAD. The * zones have room for 2^28 racing operations in each direction, which * makes it practically impossible to escape the zones. * * Once the last reference is dropped the reference count becomes * RCUREF_NOREF which forces rcuref_put() into the slowpath operation. The * slowpath then tries to set the reference count from RCUREF_NOREF to * RCUREF_DEAD via a cmpxchg(). This opens a small window where a * concurrent rcuref_get() can acquire the reference count and bring it * back to RCUREF_ONEREF or even drop the reference again and mark it DEAD. * * If the cmpxchg() succeeds then a concurrent rcuref_get() will result in * DEAD + 1, which is inside the dead zone. If that happens the reference * count is put back to DEAD. * * The actual race is possible due to the unconditional increment and * decrements in rcuref_get() and rcuref_put(): * *	T1				T2 *	get()				put() *					if (atomic_add_negative(-1, &ref->refcnt)) *		succeeds->			atomic_cmpxchg(&ref->refcnt, NOREF, DEAD); * *	atomic_add_negative(1, &ref->refcnt);	<- Elevates refcount to DEAD + 1 * * As the result of T1's add is negative, the get() goes into the slow path * and observes refcnt being in the dead zone which makes the operation fail. * * Possible critical states: * *	Context Counter	References	Operation *	T1	0	1		init() *	T2	1	2		get() *	T1	0	1		put() *	T2     -1	0		put() tries to mark dead *	T1	0	1		get() *	T2	0	1		put() mark dead fails *	T1     -1	0		put() tries to mark dead *	T1    DEAD	0		put() mark dead succeeds *	T2    DEAD+1	0		get() fails and puts it back to DEAD * * Of course there are more complex scenarios, but the above illustrates * the working principle. The rest is left to the imagination of the * reader. * * Deconstruction race * =================== * * The release operation must be protected by prohibiting a grace period in * order to prevent a possible use after free: * *	T1				T2 *	put()				get() *	// ref->refcnt = ONEREF *	if (!atomic_add_negative(-1, &ref->refcnt)) *		return false;				<- Not taken * *	// ref->refcnt == NOREF *	--> preemption *					// Elevates ref->refcnt to ONEREF *					if (!atomic_add_negative(1, &ref->refcnt)) *						return true;			<- taken * *					if (put(&p->ref)) { <-- Succeeds *						remove_pointer(p); *						kfree_rcu(p, rcu); *					} * *		RCU grace period ends, object is freed * *	atomic_cmpxchg(&ref->refcnt, NOREF, DEAD);	<- UAF * * This is prevented by disabling preemption around the put() operation as * that's in most kernel configurations cheaper than a rcu_read_lock() / * rcu_read_unlock() pair and in many cases even a NOOP. In any case it * prevents the grace period which keeps the object alive until all put() * operations complete. * * Saturation protection * ===================== * * The reference count has a saturation limit RCUREF_MAXREF (INT_MAX). * Once this is exceedded the reference count becomes stale by setting it * to RCUREF_SATURATED, which will cause a memory leak, but it prevents * wrap arounds which obviously cause worse problems than a memory * leak. When saturation is reached a warning is emitted. * * Race conditions * =============== * * All reference count increment/decrement operations are unconditional and * only verified after the fact. This optimizes for the good case and takes * the occasional race vs. a dead or already saturated refcount into * account. The saturation and dead zones are large enough to accomodate * for that. * * Memory ordering * =============== * * Memory ordering rules are slightly relaxed wrt regular atomic_t functions * and provide only what is strictly required for refcounts. * * The increments are fully relaxed; these will not provide ordering. The * rationale is that whatever is used to obtain the object to increase the * reference count on will provide the ordering. For locked data * structures, its the lock acquire, for RCU/lockless data structures its * the dependent load. * * rcuref_get() provides a control dependency ordering future stores which * ensures that the object is not modified when acquiring a reference * fails. * * rcuref_put() provides release order, i.e. all prior loads and stores * will be issued before. It also provides a control dependency ordering * against the subsequent destruction of the object. * * If rcuref_put() successfully dropped the last reference and marked the * object DEAD it also provides acquire ordering. */ #include <linux/export.h>#include <linux/rcuref.h> /** * rcuref_get_slowpath - Slowpath of rcuref_get() * @ref:	Pointer to the reference count * * Invoked when the reference count is outside of the valid zone. * * Return: *	False if the reference count was already marked dead * *	True if the reference count is saturated, which prevents the *	object from being deconstructed ever. */bool rcuref_get_slowpath(rcuref_t *ref){	unsigned int cnt = atomic_read(&ref->refcnt); 	/*	 * If the reference count was already marked dead, undo the	 * increment so it stays in the middle of the dead zone and return	 * fail.	 */	if (cnt >= RCUREF_RELEASED) {		atomic_set(&ref->refcnt, RCUREF_DEAD);		return false;	} 	/*	 * If it was saturated, warn and mark it so. In case the increment	 * was already on a saturated value restore the saturation	 * marker. This keeps it in the middle of the saturation zone and	 * prevents the reference count from overflowing. This leaks the	 * object memory, but prevents the obvious reference count overflow	 * damage.	 */	if (WARN_ONCE(cnt > RCUREF_MAXREF, "rcuref saturated - leaking memory"))		atomic_set(&ref->refcnt, RCUREF_SATURATED);	return true;}EXPORT_SYMBOL_GPL(rcuref_get_slowpath); /** * rcuref_put_slowpath - Slowpath of __rcuref_put() * @ref:	Pointer to the reference count * @cnt:	The resulting value of the fastpath decrement * * Invoked when the reference count is outside of the valid zone. * * Return: *	True if this was the last reference with no future references *	possible. This signals the caller that it can safely schedule the *	object, which is protected by the reference counter, for *	deconstruction. * *	False if there are still active references or the put() raced *	with a concurrent get()/put() pair. Caller is not allowed to *	deconstruct the protected object. */bool rcuref_put_slowpath(rcuref_t *ref, unsigned int cnt){	/* Did this drop the last reference? */	if (likely(cnt == RCUREF_NOREF)) {		/*		 * Carefully try to set the reference count to RCUREF_DEAD.		 *		 * This can fail if a concurrent get() operation has		 * elevated it again or the corresponding put() even marked		 * it dead already. Both are valid situations and do not		 * require a retry. If this fails the caller is not		 * allowed to deconstruct the object.		 */		if (!atomic_try_cmpxchg_release(&ref->refcnt, &cnt, RCUREF_DEAD))			return false; 		/*		 * The caller can safely schedule the object for		 * deconstruction. Provide acquire ordering.		 */		smp_acquire__after_ctrl_dep();		return true;	} 	/*	 * If the reference count was already in the dead zone, then this	 * put() operation is imbalanced. Warn, put the reference count back to	 * DEAD and tell the caller to not deconstruct the object.	 */	if (WARN_ONCE(cnt >= RCUREF_RELEASED, "rcuref - imbalanced put()")) {		atomic_set(&ref->refcnt, RCUREF_DEAD);		return false;	} 	/*	 * This is a put() operation on a saturated refcount. Restore the	 * mean saturation value and tell the caller to not deconstruct the	 * object.	 */	if (cnt > RCUREF_MAXREF)		atomic_set(&ref->refcnt, RCUREF_SATURATED);	return false;}EXPORT_SYMBOL_GPL(rcuref_put_slowpath);