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_try_cmpxchg_release(&ref->refcnt, &cnt, RCUREF_DEAD)) 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