Changes in rcuref.c

b9a49520 - rcuref: Plug slowpath race in rcuref_put()

Sat, 18 Jan 2025 23:55:32 +0000

rcuref: Plug slowpath race in rcuref_put()Kernel test robot reported an "imbalanced put" in the rcuref_put() slowpath, which turned out to be a false positive. Consider the following race: ref = 0 (via rcuref_init(ref, 1)) T1 T2 rcuref_put(ref) -> atomic_add_negative_release(-1, ref) # ref -> 0xffffffff -> rcuref_put_slowpath(ref) rcuref_get(ref) -> atomic_add_negative_relaxed(1, &ref->refcnt) -> return true; # ref -> 0 rcuref_put(ref) -> atomic_add_negative_release(-1, ref) # ref -> 0xffffffff -> rcuref_put_slowpath() -> cnt = atomic_read(&ref->refcnt); # cnt -> 0xffffffff / RCUREF_NOREF -> atomic_try_cmpxchg_release(&ref->refcnt, &cnt, RCUREF_DEAD)) # ref -> 0xe0000000 / RCUREF_DEAD -> return true -> cnt = atomic_read(&ref->refcnt); # cnt -> 0xe0000000 / RCUREF_DEAD -> if (cnt > RCUREF_RELEASED) # 0xe0000000 > 0xc0000000 -> WARN_ONCE(cnt >= RCUREF_RELEASED, "rcuref - imbalanced put()")The problem is the additional read in the slow path (after itdecremented to RCUREF_NOREF) which can happen after the counter has beenmarked RCUREF_DEAD.Prevent this by reusing the return value of the decrement. Now every "final"put uses RCUREF_NOREF in the slow path and attempts the final cmpxchg() toRCUREF_DEAD.[ bigeasy: Add changelog ]Fixes: ee1ee6db07795 ("atomics: Provide rcuref - scalable reference counting")Reported-by: kernel test robot Debugged-by: Sebastian Andrzej Siewior Signed-off-by: Thomas Gleixner Signed-off-by: Sebastian Andrzej Siewior Signed-off-by: Thomas Gleixner Reviewed-by: Sebastian Andrzej Siewior Cc: stable@vger.kernel.orgCloses: https://lore.kernel.org/oe-lkp/202412311453.9d7636a2-lkp@intel.com List of files: /linux-6.15/lib/rcuref.c

4fbf8b13 - locking/atomics: Use atomic_try_cmpxchg_release() to micro-optimize rcuref_put_slowpath()

Tue, 09 May 2023 15:02:55 +0000

locking/atomics: Use atomic_try_cmpxchg_release() to micro-optimize rcuref_put_slowpath()Use atomic_try_cmpxchg() instead of atomic_cmpxchg(*ptr, old, new) == oldin rcuref_put_slowpath(). On x86 the CMPXCHG instruction returns success in theZF flag, so this change saves a compare after CMPXCHG. Additionaly,the compiler reorders some code blocks to follow likely/unlikelyannotations in the atomic_try_cmpxchg() macro, improving the code from: 9a: f0 0f b1 0b lock cmpxchg %ecx,(%rbx) 9e: 83 f8 ff cmp $0xffffffff,%eax a1: 74 04 je a7 a3: 31 c0 xor %eax,%eaxto: 9a: f0 0f b1 0b lock cmpxchg %ecx,(%rbx) 9e: 75 4c jne ec a0: b0 01 mov $0x1,%alNo functional change intended.Signed-off-by: Uros Bizjak Signed-off-by: Ingo Molnar Cc: Peter Zijlstra Cc: Paul E. McKenney Link: https://lore.kernel.org/r/20230509150255.3691-1-ubizjak@gmail.com List of files: /linux-6.15/lib/rcuref.c

ee1ee6db - atomics: Provide rcuref - scalable reference counting

Thu, 23 Mar 2023 20:55:31 +0000

atomics: Provide rcuref - scalable reference countingatomic_t based reference counting, including refcount_t, usesatomic_inc_not_zero() for acquiring a reference. atomic_inc_not_zero() isimplemented with a atomic_try_cmpxchg() loop. High contention of thereference count leads to retry loops and scales badly. There is nothing toimprove on this implementation as the semantics have to be preserved.Provide rcuref as a scalable alternative solution which is suitable for RCUmanaged objects. Similar to refcount_t it comes with overflow and underflowdetection and mitigation.rcuref treats the underlying atomic_t as an unsigned integer and partitionsthis space into zones: 0x00000000 - 0x7FFFFFFF valid zone (1 .. (INT_MAX + 1) references) 0x80000000 - 0xBFFFFFFF saturation zone 0xC0000000 - 0xFFFFFFFE dead zone 0xFFFFFFFF no referencercuref_get() unconditionally increments the reference count withatomic_add_negative_relaxed(). rcuref_put() unconditionally decrements thereference count with atomic_add_negative_release().This unconditional increment avoids the inc_not_zero() problem, butrequires a more complex implementation on the put() side when the countdrops from 0 to -1.When this transition is detected then it is attempted to mark the referencecount dead, by setting it to the midpoint of the dead zone with a singleatomic_cmpxchg_release() operation. This operation can fail due to aconcurrent rcuref_get() elevating the reference count from -1 to 0 again.If the unconditional increment in rcuref_get() hits a reference count whichis marked dead (or saturated) it will detect it after the fact and bringback the reference count to the midpoint of the respective zone. The zonesprovide enough tolerance which makes it practically impossible to escapefrom 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 afterfree. As RCU is the only mechanism which allows to protect against that, itis not possible to fully replace the atomic_inc_not_zero() basedimplementation 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. Theoptimization is on the high frequeunt get()/put() pairs and theirscalability.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 atomicoperations, while at the same time providing overflow and underflowdetection and mitigation.The performance of rcuref compared to plain atomic_inc_not_zero() andatomic_dec_return() based reference counting under contention: - Micro benchmark: All CPUs running a increment/decrement loop on an elevated reference count, which means the 0 to -1 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 Reported-by: Arjan Van De Ven Signed-off-by: Thomas Gleixner Signed-off-by: Peter Zijlstra (Intel) Link: https://lore.kernel.org/r/20230323102800.158429195@linutronix.de List of files: /linux-6.15/lib/rcuref.c