| 1 | |
| 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 | * @cnt: The resulting value of the fastpath decrement
|
| 224 | *
|
| 225 | * Invoked when the reference count is outside of the valid zone.
|
| 226 | *
|
| 227 | * Return:
|
| 228 | * True if this was the last reference with no future references
|
| 229 | * possible. This signals the caller that it can safely schedule the
|
| 230 | * object, which is protected by the reference counter, for
|
| 231 | * deconstruction.
|
| 232 | *
|
| 233 | * False if there are still active references or the put() raced
|
| 234 | * with a concurrent get()/put() pair. Caller is not allowed to
|
| 235 | * deconstruct the protected object.
|
| 236 |
|
| 237 | bool rcuref_put_slowpath(rcuref_t *ref, unsigned int cnt)
|
| 238 | {
|
| 239 |
|
| 240 | if (likely(cnt == RCUREF_NOREF)) {
|
| 241 | |
| 242 | * Carefully try to set the reference count to RCUREF_DEAD.
|
| 243 | *
|
| 244 | * This can fail if a concurrent get() operation has
|
| 245 | * elevated it again or the corresponding put() even marked
|
| 246 | * it dead already. Both are valid situations and do not
|
| 247 | * require a retry. If this fails the caller is not
|
| 248 | * allowed to deconstruct the object.
|
| 249 |
|
| 250 | if (!atomic_try_cmpxchg_release(&ref->refcnt, &cnt, RCUREF_DEAD))
|
| 251 | return false;
|
| 252 |
|
| 253 | |
| 254 | * The caller can safely schedule the object for
|
| 255 | * deconstruction. Provide acquire ordering.
|
| 256 |
|
| 257 | smp_acquire__after_ctrl_dep();
|
| 258 | return true;
|
| 259 | }
|
| 260 |
|
| 261 | |
| 262 | * If the reference count was already in the dead zone, then this
|
| 263 | * put() operation is imbalanced. Warn, put the reference count back to
|
| 264 | * DEAD and tell the caller to not deconstruct the object.
|
| 265 |
|
| 266 | if (WARN_ONCE(cnt >= RCUREF_RELEASED, "rcuref - imbalanced put()")) {
|
| 267 | atomic_set(&ref->refcnt, RCUREF_DEAD);
|
| 268 | return false;
|
| 269 | }
|
| 270 |
|
| 271 | |
| 272 | * This is a put() operation on a saturated refcount. Restore the
|
| 273 | * mean saturation value and tell the caller to not deconstruct the
|
| 274 | * object.
|
| 275 |
|
| 276 | if (cnt > RCUREF_MAXREF)
|
| 277 | atomic_set(&ref->refcnt, RCUREF_SATURATED);
|
| 278 | return false;
|
| 279 | }
|
| 280 | EXPORT_SYMBOL_GPL(rcuref_put_slowpath);
|