xref: /openbmc/linux/lib/rcuref.c (revision 724ba675)
1 // SPDX-License-Identifier: GPL-2.0-only
2 
3 /*
4  * rcuref - A scalable reference count implementation for RCU managed objects
5  *
6  * rcuref is provided to replace open coded reference count implementations
7  * based on atomic_t. It protects explicitely RCU managed objects which can
8  * be visible even after the last reference has been dropped and the object
9  * 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 has
28  * O(N^2) behaviour under contention with N concurrent operations.
29  *
30  * rcuref uses atomic_add_negative_relaxed() for the fast path, which scales
31  * better under contention.
32  *
33  * Why not refcount?
34  * =================
35  *
36  * In principle it should be possible to make refcount use the rcuref
37  * scheme, but the destruction race described below cannot be prevented
38  * unless the protected object is RCU managed.
39  *
40  * Theory of operation
41  * ===================
42  *
43  * rcuref uses an unsigned integer reference counter. As long as the
44  * counter value is greater than or equal to RCUREF_ONEREF and not larger
45  * than RCUREF_MAXREF the reference is alive:
46  *
47  * ONEREF   MAXREF               SATURATED             RELEASED      DEAD    NOREF
48  * 0        0x7FFFFFFF 0x8000000 0xA0000000 0xBFFFFFFF 0xC0000000 0xE0000000 0xFFFFFFFF
49  * <---valid --------> <-------saturation zone-------> <-----dead zone----->
50  *
51  * The get() and put() operations do unconditional increments and
52  * decrements. The result is checked after the operation. This optimizes
53  * for the fast path.
54  *
55  * If the reference count is saturated or dead, then the increments and
56  * decrements are not harmful as the reference count still stays in the
57  * respective zones and is always set back to STATURATED resp. DEAD. The
58  * zones have room for 2^28 racing operations in each direction, which
59  * makes it practically impossible to escape the zones.
60  *
61  * Once the last reference is dropped the reference count becomes
62  * RCUREF_NOREF which forces rcuref_put() into the slowpath operation. The
63  * slowpath then tries to set the reference count from RCUREF_NOREF to
64  * RCUREF_DEAD via a cmpxchg(). This opens a small window where a
65  * concurrent rcuref_get() can acquire the reference count and bring it
66  * 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 in
69  * DEAD + 1, which is inside the dead zone. If that happens the reference
70  * count is put back to DEAD.
71  *
72  * The actual race is possible due to the unconditional increment and
73  * decrements in rcuref_get() and rcuref_put():
74  *
75  *	T1				T2
76  *	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 + 1
81  *
82  * As the result of T1's add is negative, the get() goes into the slow path
83  * and observes refcnt being in the dead zone which makes the operation fail.
84  *
85  * Possible critical states:
86  *
87  *	Context Counter	References	Operation
88  *	T1	0	1		init()
89  *	T2	1	2		get()
90  *	T1	0	1		put()
91  *	T2     -1	0		put() tries to mark dead
92  *	T1	0	1		get()
93  *	T2	0	1		put() mark dead fails
94  *	T1     -1	0		put() tries to mark dead
95  *	T1    DEAD	0		put() mark dead succeeds
96  *	T2    DEAD+1	0		get() fails and puts it back to DEAD
97  *
98  * Of course there are more complex scenarios, but the above illustrates
99  * the working principle. The rest is left to the imagination of the
100  * reader.
101  *
102  * Deconstruction race
103  * ===================
104  *
105  * The release operation must be protected by prohibiting a grace period in
106  * order to prevent a possible use after free:
107  *
108  *	T1				T2
109  *	put()				get()
110  *	// ref->refcnt = ONEREF
111  *	if (!atomic_add_negative(-1, &ref->refcnt))
112  *		return false;				<- Not taken
113  *
114  *	// ref->refcnt == NOREF
115  *	--> preemption
116  *					// Elevates ref->refcnt to ONEREF
117  *					if (!atomic_add_negative(1, &ref->refcnt))
118  *						return true;			<- taken
119  *
120  *					if (put(&p->ref)) { <-- Succeeds
121  *						remove_pointer(p);
122  *						kfree_rcu(p, rcu);
123  *					}
124  *
125  *		RCU grace period ends, object is freed
126  *
127  *	atomic_cmpxchg(&ref->refcnt, NOREF, DEAD);	<- UAF
128  *
129  * This is prevented by disabling preemption around the put() operation as
130  * 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 it
132  * prevents the grace period which keeps the object alive until all put()
133  * operations complete.
134  *
135  * Saturation protection
136  * =====================
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 it
140  * to RCUREF_SATURATED, which will cause a memory leak, but it prevents
141  * wrap arounds which obviously cause worse problems than a memory
142  * leak. When saturation is reached a warning is emitted.
143  *
144  * Race conditions
145  * ===============
146  *
147  * All reference count increment/decrement operations are unconditional and
148  * only verified after the fact. This optimizes for the good case and takes
149  * the occasional race vs. a dead or already saturated refcount into
150  * account. The saturation and dead zones are large enough to accomodate
151  * for that.
152  *
153  * Memory ordering
154  * ===============
155  *
156  * Memory ordering rules are slightly relaxed wrt regular atomic_t functions
157  * and provide only what is strictly required for refcounts.
158  *
159  * The increments are fully relaxed; these will not provide ordering. The
160  * rationale is that whatever is used to obtain the object to increase the
161  * reference count on will provide the ordering. For locked data
162  * structures, its the lock acquire, for RCU/lockless data structures its
163  * the dependent load.
164  *
165  * rcuref_get() provides a control dependency ordering future stores which
166  * ensures that the object is not modified when acquiring a reference
167  * fails.
168  *
169  * rcuref_put() provides release order, i.e. all prior loads and stores
170  * will be issued before. It also provides a control dependency ordering
171  * against the subsequent destruction of the object.
172  *
173  * If rcuref_put() successfully dropped the last reference and marked the
174  * 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 count
183  *
184  * Invoked when the reference count is outside of the valid zone.
185  *
186  * Return:
187  *	False if the reference count was already marked dead
188  *
189  *	True if the reference count is saturated, which prevents the
190  *	object from being deconstructed ever.
191  */
192 bool 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 the
198 	 * increment so it stays in the middle of the dead zone and return
199 	 * 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 increment
208 	 * was already on a saturated value restore the saturation
209 	 * marker. This keeps it in the middle of the saturation zone and
210 	 * prevents the reference count from overflowing. This leaks the
211 	 * object memory, but prevents the obvious reference count overflow
212 	 * damage.
213 	 */
214 	if (WARN_ONCE(cnt > RCUREF_MAXREF, "rcuref saturated - leaking memory"))
215 		atomic_set(&ref->refcnt, RCUREF_SATURATED);
216 	return true;
217 }
218 EXPORT_SYMBOL_GPL(rcuref_get_slowpath);
219 
220 /**
221  * rcuref_put_slowpath - Slowpath of __rcuref_put()
222  * @ref:	Pointer to the reference count
223  *
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 references
228  *	possible. This signals the caller that it can safely schedule the
229  *	object, which is protected by the reference counter, for
230  *	deconstruction.
231  *
232  *	False if there are still active references or the put() raced
233  *	with a concurrent get()/put() pair. Caller is not allowed to
234  *	deconstruct the protected object.
235  */
236 bool 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 has
246 		 * elevated it again or the corresponding put() even marked
247 		 * it dead already. Both are valid situations and do not
248 		 * require a retry. If this fails the caller is not
249 		 * allowed to deconstruct the object.
250 		 */
251 		if (atomic_cmpxchg_release(&ref->refcnt, RCUREF_NOREF, RCUREF_DEAD) != RCUREF_NOREF)
252 			return false;
253 
254 		/*
255 		 * The caller can safely schedule the object for
256 		 * 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 this
264 	 * put() operation is imbalanced. Warn, put the reference count back to
265 	 * 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 the
274 	 * mean saturation value and tell the caller to not deconstruct the
275 	 * object.
276 	 */
277 	if (cnt > RCUREF_MAXREF)
278 		atomic_set(&ref->refcnt, RCUREF_SATURATED);
279 	return false;
280 }
281 EXPORT_SYMBOL_GPL(rcuref_put_slowpath);
282