| Message ID | 20230228132910.991359171@linutronix.de (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | Netdev Maintainers |
| Headers | show |
| Series | net, refcount: Address dst_entry reference count scalability issues | expand |
On Tue, Feb 28, 2023 at 6:33 AM Thomas Gleixner <tglx@linutronix.de> wrote: > > This unconditional increment avoids the inc_not_zero() problem, but > requires a more complex implementation on the put() side when the count > drops from 1 to 0. > > When this transition is detected then it is attempted to mark the reference > count dead, by setting it to the midpoint of the dead zone with a single > atomic_cmpxchg_release() operation. This operation can fail due to a > concurrent rcuref_get() elevating the reference count from 0 to 1. This looks sane to me, however it does look like the code is not really optimal. This is supposed to be a critical function, and is inlined: > +static inline __must_check bool rcuref_get(rcuref_t *ref) > +{ > + unsigned int old = atomic_fetch_add_relaxed(1, &ref->refcnt); > + > + if (likely(old < RCUREF_MAXREF)) > + return true; but that comparison would be much better if RCUREF_MAXREF was 0x80000000 and you'd end up just checking the sign of the result, instead of checking big numbers. Also, this optimal value choice ends up being architecture-specific, since some do the "fetch_add", and others tend to prefer "add_return", and so the point that is cheapest to check ends up depending on which architecture it is. This may seem like nit-picking, but I absolutely *HATE* our current refcount interface for how absolutely horrid the code generation ends up being. It's gotten better, but it's still not great. So if we're introducing yet another refcount interface, and it's done in the name of efficiency, I would *really* want it to actually be exactly that: efficient. Not some half-way thing. And yes, that may mean that it should have some architecture-specific code (with fallback defaults for the generic case). Linus
On Tue, Feb 28, 2023 at 4:42 PM Linus Torvalds <torvalds@linuxfoundation.org> wrote: > > And yes, that may mean that it should have some architecture-specific > code (with fallback defaults for the generic case). Another reason for architecture-specific code is that anybody who doesn't have atomics and just relies on an LL/SC model is actually better of *not* having any of this complexity. In fact, the Intel RAO instruction set would likely do that on x86 too. With that alleged future "CMPccXADD", there likely is no longer any advantage to this model of rcuref. Now, I don't know when - if ever - said RAO instruction set extension comes, but I'd hope that the new scalable reference counting would be ready for it. Linus
On Tue, Feb 28 2023 at 16:42, Linus Torvalds wrote: > On Tue, Feb 28, 2023 at 6:33 AM Thomas Gleixner <tglx@linutronix.de> wrote: > This may seem like nit-picking, but I absolutely *HATE* our current > refcount interface for how absolutely horrid the code generation ends > up being. It's gotten better, but it's still not great. > > So if we're introducing yet another refcount interface, and it's done > in the name of efficiency, I would *really* want it to actually be > exactly that: efficient. Not some half-way thing. > > And yes, that may mean that it should have some architecture-specific > code (with fallback defaults for the generic case). Let me stare at that some more. Thanks, tglx
On Wed, Mar 01 2023 at 12:09, Thomas Gleixner wrote: > On Tue, Feb 28 2023 at 16:42, Linus Torvalds wrote: >> On Tue, Feb 28, 2023 at 6:33 AM Thomas Gleixner <tglx@linutronix.de> wrote: >> And yes, that may mean that it should have some architecture-specific >> code (with fallback defaults for the generic case). > > Let me stare at that some more. So I went back to something which I tried first and dumped it because I couldn't convince myself that it is correct. That first implementation was actually incorrect as I could not wrap my head around that dead race UAF problem. I should have revisited it once I got that sorted. Duh! The result of staring more is: get(): 6b57: f0 41 83 45 40 01 lock addl $0x1,0x40(%r13) 6b5d: 0f 88 cd 00 00 00 js 6c30 // -> slowpath if negative Success put(), PREEMPT=n or invoked from RCU safe code 414: f0 83 47 40 ff lock addl $0xffffffff,0x40(%rdi) 419: 78 06 js 421 // -> slowpath if negative not last reference (fast path) put(), PREEMPT=y: 574: 65 ff 05 00 00 00 00 incl %gs:0x0(%rip) // preempt_disable() 57b: f0 83 47 40 ff lock addl $0xffffffff,0x40(%rdi) 580: 0f 98 c0 sets %al // safe result 583: 78 2b js 5b0 // -> slowpath if negative 585: 65 ff 0d 00 00 00 00 decl %gs:0x0(%rip) // preempt_enable() 58c: 74 1b je 5a9 // -> preempt_schedule() 58e: 84 c0 test %al,%al // The actual result checked 590: 75 06 jne 598 // -> destruct object not last reference The current code looks like this: get(): 63b4: 41 8b 47 40 mov 0x40(%r15),%eax // initial read 63b8: 85 c0 test %eax,%eax // check for 0 63ba: 0f 84 e9 00 00 00 je 64a9 // fail if 0 63c0: 8d 50 01 lea 0x1(%rax),%edx // + 1 63c3: f0 41 0f b1 57 40 lock cmpxchg %edx,0x40(%r15) // try update 63c9: 0f 94 44 24 07 sete 0x7(%rsp) // store result 63ce: 0f b6 4c 24 07 movzbl 0x7(%rsp),%ecx // read it back !?! 63d3: 84 c9 test %cl,%cl // test for success 63d5: 74 e1 je 63b8 // repeat on fail Success put(), w/o sanity checking: 29a: b8 ff ff ff ff mov $0xffffffff,%eax // -1 29f: f0 0f c1 47 40 lock xadd %eax,0x40(%rdi) // add 2a4: 83 f8 01 cmp $0x1,%eax // check old == 1 2a7: 74 05 je 2ae // slowpath destroy object Not last reference but the actual network code does some sanity checking: 29a: 41 55 push %r13 // extra push 29c: b9 ff ff ff ff mov $0xffffffff,%ecx // -1 2a1: 41 54 push %r12 // extra push 2a3: 49 89 fc mov %rdi,%r12 // extra save RDI 2a6: f0 0f c1 4f 40 lock xadd %ecx,0x40(%rdi) // add 2ab: 83 e9 01 sub $0x1,%ecx // new = old - 1 2ae: 41 89 cd mov %ecx,%r13d // extra save 2b1: 78 24 js 2d7 // slowpath underrun 2b3: 74 09 je 2be // slowpath destroy object 2b5: 41 5c pop %r12 // extra pop 2b7: 41 5d pop %r13 // extra pop 2b9: e9 00 00 00 00 jmpq 2be // not last reference (fast path) Awesome, right? I also thought about the newfangled CMPccXADD instruction. That will need some macro wrappery to handle the alternative and it get's rid of the dead race in put(). There will be some ugly involved, but I'm sure that this can be handled halfways sanely in common code. All the ugly will be in the slowpath, which will still be there to provide saturation and UAF detection/mitigation. The fast path will grow in size as CMPccXADD is not one of the slim size instructions, but the basic operating principle will still work out. See the reworked patch below. This needs some atomic-fallback changes to build. I force pushed the complete lot to: git://git.kernel.org/pub/scm/linux/kernel/git/tglx/devel.git rcuref in case you want the full picture. The main change is how the zones are defined. They are off by one now. I'm glad I kept the defines of the initial version around. :) The pathological test case showed a slight improvement in a quick test, but I'm way too tired to say anything conclusive right now, Thanks for nudging me! tglx --- --- /dev/null +++ b/include/linux/rcuref.h @@ -0,0 +1,155 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _LINUX_RCUREF_H +#define _LINUX_RCUREF_H + +#include <linux/atomic.h> +#include <linux/bug.h> +#include <linux/limits.h> +#include <linux/lockdep.h> +#include <linux/preempt.h> +#include <linux/rcupdate.h> + +#define RCUREF_ONEREF 0x00000000U +#define RCUREF_MAXREF 0x7FFFFFFFU +#define RCUREF_SATURATED 0xA0000000U +#define RCUREF_RELEASED 0xC0000000U +#define RCUREF_DEAD 0xE0000000U +#define RCUREF_NOREF 0xFFFFFFFFU + +/** + * rcuref_init - Initialize a rcuref reference count with the given reference count + * @ref: Pointer to the reference count + * @cnt: The initial reference count typically '1' + */ +static inline void rcuref_init(rcuref_t *ref, unsigned int cnt) +{ + atomic_set(&ref->refcnt, cnt - 1); +} + +/** + * rcuref_read - Read the number of held reference counts of a rcuref + * @ref: Pointer to the reference count + * + * Return: The number of held references (0 ... N) + */ +static inline unsigned int rcuref_read(rcuref_t *ref) +{ + unsigned int c = atomic_read(&ref->refcnt); + + /* Return 0 if within the DEAD zone. */ + return c >= RCUREF_RELEASED ? 0 : c + 1; +} + +extern __must_check bool rcuref_get_slowpath(rcuref_t *ref); + +/** + * rcuref_get - Acquire one reference on a rcuref reference count + * @ref: Pointer to the reference count + * + * Similar to atomic_inc_not_zero() but saturates at RCUREF_MAXREF. + * + * Provides no memory ordering, it is assumed the caller has guaranteed the + * object memory to be stable (RCU, etc.). It does provide a control dependency + * and thereby orders future stores. See documentation in lib/rcuref.c + * + * Return: + * False if the attempt to acquire a reference failed. This happens + * when the last reference has been put already + * + * True if a reference was successfully acquired + */ +static inline __must_check bool rcuref_get(rcuref_t *ref) +{ + /* + * Unconditionally increase the reference count. The saturation and + * dead zones provide enough tolerance for this. + */ + if (likely(!atomic_add_negative_relaxed(1, &ref->refcnt))) + return true; + + /* Handle the cases inside the saturation and dead zones */ + return rcuref_get_slowpath(ref); +} + +extern __must_check bool rcuref_put_slowpath(rcuref_t *ref); + +/* + * Internal helper. Do not invoke directly. + */ +static __always_inline __must_check bool __rcuref_put(rcuref_t *ref) +{ + RCU_LOCKDEP_WARN(!rcu_read_lock_held() && preemptible(), + "suspicious rcuref_put_rcusafe() usage"); + /* + * Unconditionally decrease the reference count. The saturation and + * dead zones provide enough tolerance for this. + */ + if (likely(!atomic_add_negative_release(-1, &ref->refcnt))) + return false; + + /* + * Handle the last reference drop and cases inside the saturation + * and dead zones. + */ + return rcuref_put_slowpath(ref); +} + +/** + * rcuref_put_rcusafe -- Release one reference for a rcuref reference count RCU safe + * @ref: Pointer to the reference count + * + * Provides release memory ordering, such that prior loads and stores are done + * before, and provides an acquire ordering on success such that free() + * must come after. + * + * Can be invoked from contexts, which guarantee that no grace period can + * happen which would free the object concurrently if the decrement drops + * the last reference and the slowpath races against a concurrent get() and + * put() pair. rcu_read_lock()'ed and atomic contexts qualify. + * + * Return: + * True if this was the last reference with no future references + * possible. This signals the caller that it can safely release the + * object which is protected by the reference counter. + * + * False if there are still active references or the put() raced + * with a concurrent get()/put() pair. Caller is not allowed to + * release the protected object. + */ +static inline __must_check bool rcuref_put_rcusafe(rcuref_t *ref) +{ + return __rcuref_put(ref); +} + +/** + * rcuref_put -- Release one reference for a rcuref reference count + * @ref: Pointer to the reference count + * + * Can be invoked from any context. + * + * Provides release memory ordering, such that prior loads and stores are done + * before, and provides an acquire ordering on success such that free() + * must come after. + * + * 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. + */ +static inline __must_check bool rcuref_put(rcuref_t *ref) +{ + bool released; + + preempt_disable(); + released = __rcuref_put(ref); + preempt_enable(); + return released; +} + +#endif --- a/include/linux/types.h +++ b/include/linux/types.h @@ -175,6 +175,12 @@ typedef struct { } atomic64_t; #endif +typedef struct { + atomic_t refcnt; +} rcuref_t; + +#define RCUREF_INIT(i) { .refcnt = ATOMIC_INIT(i - 1) } + struct list_head { struct list_head *next, *prev; }; --- a/lib/Makefile +++ b/lib/Makefile @@ -47,7 +47,7 @@ obj-y += bcd.o sort.o parser.o debug_loc list_sort.o uuid.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o rhashtable.o base64.o \ - once.o refcount.o usercopy.o errseq.o bucket_locks.o \ + once.o refcount.o rcuref.o usercopy.o errseq.o bucket_locks.o \ generic-radix-tree.o obj-$(CONFIG_STRING_SELFTEST) += test_string.o obj-y += string_helpers.o --- /dev/null +++ b/lib/rcuref.c @@ -0,0 +1,281 @@ +// 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, -1, 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->cnt)) + * return false; <- Not taken + * + * // ref->refcnt == NOREF + * --> preemption + * // Elevates ref->c 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, NONE, 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 + * + * 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 = atomic_read(&ref->refcnt); + + /* 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_cmpxchg_release(&ref->refcnt, RCUREF_NOREF, RCUREF_DEAD) != RCUREF_NOREF) + 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; + } + + /* + * Is this a put() operation on a saturated refcount? If so, rRestore 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);
(typos) On 3/1/23 17:05, Thomas Gleixner wrote: > On Wed, Mar 01 2023 at 12:09, Thomas Gleixner wrote: > --- > --- /dev/null > +++ b/include/linux/rcuref.h > @@ -0,0 +1,155 @@ > +/* SPDX-License-Identifier: GPL-2.0-only */ > +#ifndef _LINUX_RCUREF_H > +#define _LINUX_RCUREF_H > + > +#include <linux/atomic.h> > +#include <linux/bug.h> > +#include <linux/limits.h> > +#include <linux/lockdep.h> > +#include <linux/preempt.h> > +#include <linux/rcupdate.h> > + > +#define RCUREF_ONEREF 0x00000000U > +#define RCUREF_MAXREF 0x7FFFFFFFU > +#define RCUREF_SATURATED 0xA0000000U > +#define RCUREF_RELEASED 0xC0000000U > +#define RCUREF_DEAD 0xE0000000U > +#define RCUREF_NOREF 0xFFFFFFFFU > + > +/** > + * rcuref_init - Initialize a rcuref reference count with the given reference count > + * @ref: Pointer to the reference count > + * @cnt: The initial reference count typically '1' count, typically > + */ > +static inline void rcuref_init(rcuref_t *ref, unsigned int cnt) > +{ > + atomic_set(&ref->refcnt, cnt - 1); > +} > + [snip] > --- /dev/null > +++ b/lib/rcuref.c > @@ -0,0 +1,281 @@ > +// 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 explicitly > + * 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 SATURATED > + * 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, -1, 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->cnt)) > + * return false; <- Not taken > + * > + * // ref->refcnt == NOREF > + * --> preemption > + * // Elevates ref->c 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, NONE, 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 exceeded > + * to RCUREF_SATURATED, which will cause a memory leak, but it prevents > + * wrap arounds which obviously cause worse problems than a memory wraparounds > + * 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 accommodate "accommodate that" or "allow for that". > + * for that. > + * > + * Memory ordering > + * =============== > + * > + * Memory ordering rules are slightly relaxed wrt regular atomic_t functions Preferably "with respect to". > + * 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> > + [snip] > +/** > + * rcuref_put_slowpath - Slowpath of __rcuref_put() > + * @ref: Pointer to the reference count > + * > + * 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 = atomic_read(&ref->refcnt); > + > + /* 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_cmpxchg_release(&ref->refcnt, RCUREF_NOREF, RCUREF_DEAD) != RCUREF_NOREF) > + 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; > + } > + > + /* > + * Is this a put() operation on a saturated refcount? If so, rRestore the restore > + * 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);
On Wed, Mar 1, 2023 at 5:05 PM Thomas Gleixner <tglx@linutronix.de> wrote: > > The result of staring more is: > > get(): > 6b57: f0 41 83 45 40 01 lock addl $0x1,0x40(%r13) > 6b5d: 0f 88 cd 00 00 00 js 6c30 // -> slowpath if negative [ rest removed ] Yeah, so this looks like I was hoping for. That PREEMPT=y case of 'put() makes me slightly unhappy, and I'm wondering if it can be improved with better placement of the preempt_disable/enable, but apart from maybe some massaging to that I don't see a good way to avoid it. And the ugliness is mostly about the preemption side, not about the refcount itself. I've looked at that "preempt_enable -> preempt_schedule" code generation before, and I've disliked it before, and I don't have an answer to it. > but the actual network code does some sanity checking: Ok. Not pretty. But at least it's just an xadd on the access itself, there's just some extra noise around it. Linus
--- /dev/null +++ b/include/linux/rcuref.h @@ -0,0 +1,89 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _LINUX_RCUREF_H +#define _LINUX_RCUREF_H + +#include <linux/atomic.h> +#include <linux/bug.h> +#include <linux/limits.h> +#include <linux/lockdep.h> +#include <linux/preempt.h> +#include <linux/rcupdate.h> + +#define RCUREF_NOREF 0x00000000 +#define RCUREF_ONEREF 0x00000001 +#define RCUREF_MAXREF 0x7FFFFFFF +#define RCUREF_SATURATED 0xA0000000 +#define RCUREF_RELEASED 0xC0000000 +#define RCUREF_DEAD 0xE0000000 + +/** + * rcuref_init - Initialize a rcuref reference count with the given reference count + * @ref: Pointer to the reference count + * @cnt: The initial reference count typically '1' + */ +static inline void rcuref_init(rcuref_t *ref, unsigned int cnt) +{ + atomic_set(&ref->refcnt, cnt); +} + +/** + * rcuref_read - Read the number of held reference counts of a rcuref + * @ref: Pointer to the reference count + * + * Return: The number of held references (0 ... N) + */ +static inline unsigned int rcuref_read(rcuref_t *ref) +{ + unsigned int c = atomic_read(&ref->refcnt); + + /* Return 0 if within the DEAD zone. */ + return c >= RCUREF_RELEASED ? 0 : c; +} + +extern __must_check bool rcuref_get_slowpath(rcuref_t *ref, unsigned int new); + +/** + * rcuref_get - Acquire one reference on a rcuref reference count + * @ref: Pointer to the reference count + * + * Similar to atomic_inc_not_zero() but saturates at RCUREF_MAXREF. + * + * Provides no memory ordering, it is assumed the caller has guaranteed the + * object memory to be stable (RCU, etc.). It does provide a control dependency + * and thereby orders future stores. See documentation in lib/rcuref.c + * + * Return: + * False if the attempt to acquire a reference failed. This happens + * when the last reference has been put already + * + * True if a reference was successfully acquired + */ +static inline __must_check bool rcuref_get(rcuref_t *ref) +{ + /* + * Unconditionally increase the reference count. The saturation and + * dead zones provide enough tolerance for this. + */ + unsigned int old = atomic_fetch_add_relaxed(1, &ref->refcnt); + + /* + * If the old value is less than RCUREF_MAXREF, this is a valid + * reference. + * + * In case the original value was RCUREF_NOREF the above + * unconditional increment raced with a concurrent put() operation + * dropping the last reference. That racing put() operation + * subsequently fails to mark the reference count dead because the + * count is now elevated again and the concurrent caller is + * therefore not allowed to deconstruct the object. + */ + if (likely(old < RCUREF_MAXREF)) + return true; + + /* Handle the cases inside the saturation and dead zones */ + return rcuref_get_slowpath(ref, old); +} + +extern __must_check bool rcuref_put(rcuref_t *ref); + +#endif --- a/include/linux/types.h +++ b/include/linux/types.h @@ -175,6 +175,12 @@ typedef struct { } atomic64_t; #endif +typedef struct { + atomic_t refcnt; +} rcuref_t; + +#define RCUREF_INIT(i) { .refcnt = ATOMIC_INIT(i) } + struct list_head { struct list_head *next, *prev; }; --- a/lib/Makefile +++ b/lib/Makefile @@ -47,7 +47,7 @@ obj-y += bcd.o sort.o parser.o debug_loc list_sort.o uuid.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ percpu-refcount.o rhashtable.o base64.o \ - once.o refcount.o usercopy.o errseq.o bucket_locks.o \ + once.o refcount.o rcuref.o usercopy.o errseq.o bucket_locks.o \ generic-radix-tree.o obj-$(CONFIG_STRING_SELFTEST) += test_string.o obj-y += string_helpers.o --- /dev/null +++ b/lib/rcuref.c @@ -0,0 +1,311 @@ +// 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_fetch_add_relaxed() and atomic_fetch_sub_release() + * for the fast path, which scale 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: + * + * NOREF ONEREF MAXREF SATURATED RELEASED DEAD + * 0 1 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_fetch_sub(1, &ref->refcnt) >= 0) + * succeeds-> atomic_try_cmpxchg(&ref->refcnt, -1, DEAD); + * + * old = atomic_fetch_add(1, &ref->refcnt); <- Elevates refcount to DEAD + 1 + * + * As @old observed by T1 is within the dead zone the T1 get() fails. + * + * Possible critical states: + * + * Context Counter References Operation + * T1 1 1 init() + * T2 2 2 get() + * T1 1 1 put() + * T2 0 0 put() tries to mark dead + * T1 1 1 get() + * T2 1 1 put() mark dead fails + * T1 0 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_fetch_sub(1, &ref->cnt) > ONEREF) + * return false; <- Not taken + * + * // ref->refcnt == NOREF + * --> preemption + * // Elevates ref->c to ONEREF + * if (!atomic_fetch_add(1, &ref->refcnt) >= NOREF) + * 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, NONE, 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 + * @old: The reference count before the unconditional increment + * operation in rcuref_get() + * + * 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 old) +{ + /* + * 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 (old >= 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. + */ + WARN_ONCE(old >= RCUREF_MAXREF, "rcuref saturated - leaking memory"); + atomic_set(&ref->refcnt, RCUREF_SATURATED); + return true; +} +EXPORT_SYMBOL_GPL(rcuref_get_slowpath); + +static __must_check bool __rcuref_put(rcuref_t *ref) +{ + /* + * Unconditionally decrement the reference count. The saturation and + * dead zones provide enough tolerance for this. + */ + unsigned int old = atomic_fetch_sub_release(1, &ref->refcnt); + + /* + * If the old value is in the valid range and is greater than + * RCUREF_ONEREF, nothing to do. + */ + if (likely(old > RCUREF_ONEREF && old <= RCUREF_MAXREF)) + return false; + + /* Did this drop the last reference? */ + if (likely(old == RCUREF_ONEREF)) { + /* + * 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_cmpxchg_release(&ref->refcnt, RCUREF_NOREF, RCUREF_DEAD) != RCUREF_NOREF) + 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(old >= 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. + */ + atomic_set(&ref->refcnt, RCUREF_SATURATED); + return false; +} + +/** + * rcuref_put -- Release one reference for a rcuref reference count + * @ref: Pointer to the reference count + * + * Can be invoked from any context. + * + * Provides release memory ordering, such that prior loads and stores are done + * before, and provides an acquire ordering on success such that free() + * must come after. + * + * 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(rcuref_t *ref) +{ + bool released; + + /* + * Protect against a concurrent get()/put() pair which marks the + * reference count DEAD and schedules it for RCU free. This + * prevents a grace period and is cheaper than + * rcu_read_lock()/unlock(). + */ + preempt_disable(); + released = __rcuref_put(ref); + preempt_enable(); + return released; +} +EXPORT_SYMBOL_GPL(rcuref_put);
atomic_t based reference counting, including refcount_t, uses atomic_inc_not_zero() for acquiring a reference. atomic_inc_not_zero() is implemented with a atomic_try_cmpxchg() loop. High contention of the reference count leads to retry loops and scales badly. There is nothing to improve on this implementation as the semantics have to be preserved. Provide rcuref as a scalable alternative solution which is suitable for RCU managed objects. Similar to refcount_t it comes with overflow and underflow detection and mitigation. rcuref treats the underlying atomic_t as an unsigned integer and partitions this space into zones: 0x00000000 - 0x7FFFFFFF valid zone 0x80000000 - 0xBFFFFFFF saturation zone 0xC0000000 - 0xFFFFFFFF dead zone rcuref_get() unconditionally increments the reference count with atomic_fetch_add_relaxed(). rcuref_put() unconditionally decrements the reference count with atomic_fetch_sub_relaxed(). This unconditional increment avoids the inc_not_zero() problem, but requires a more complex implementation on the put() side when the count drops from 1 to 0. When this transition is detected then it is attempted to mark the reference count dead, by setting it to the midpoint of the dead zone with a single atomic_cmpxchg_release() operation. This operation can fail due to a concurrent rcuref_get() elevating the reference count from 0 to 1. If the unconditional increment in rcuref_get() hits a reference count which is marked dead (or saturated) it will detect it after the fact and bring back the reference count to the midpoint of the respective zone. The zones provide enough tolerance which makes it practically impossible to escape from a zone. The racy implementation of rcuref_put() requires to protect rcuref_put() against a grace period ending in order to prevent a subtle use after free. As RCU is the only mechanism which allows to protect against that, it is not possible to replace the atomic_inc_not_zero() based implementation of refcount_t with this scheme. The final drop is slightly more expensive than the atomic_dec_return() counterpart, but that's not the case which this is optimized for. The optimization is on the high frequeunt get()/put() pairs and their scalability. The performance of an uncontended rcuref_get()/put() pair where the put() is not dropping the last reference is still on par with the plain atomic operations, while at the same time providing overflow and underflow detection and mitigation. The performance of rcuref compared to plain atomic_inc_not_zero() and atomic_dec_return() based reference counting under contention: - Micro benchmark: All CPUs running a increment/decrement loop on an elevated reference count, which means the 1 to 0 transition never happens. The performance gain depends on microarchitecture and the number of CPUs and has been observed in the range of 1.3X to 4.7X - Conversion of dst_entry::__refcnt to rcuref and testing with the localhost memtier/memcached benchmark. That benchmark shows the reference count contention prominently. The performance gain depends on microarchitecture and the number of CPUs and has been observed in the range of 1.1X to 2.6X over the previous fix for the false sharing issue vs. struct dst_entry::__refcnt. When memtier is run over a real 1Gb network connection, there is a small gain on top of the false sharing fix. The two changes combined result in a 2%-5% total gain for that networked test. Reported-by: Wangyang Guo <wangyang.guo@intel.com> Reported-by: Arjan Van De Ven <arjan.van.de.ven@intel.com> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Cc: Will Deacon <will@kernel.org> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Boqun Feng <boqun.feng@gmail.com> Cc: Mark Rutland <mark.rutland@arm.com> --- include/linux/rcuref.h | 89 ++++++++++++++ include/linux/types.h | 6 lib/Makefile | 2 lib/rcuref.c | 311 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 407 insertions(+), 1 deletion(-)