lkml.org 
[lkml]   [2022]   [Jul]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 5.4 64/87] locking/refcount: Improve performance of generic REFCOUNT_FULL code
    Date
    From: Will Deacon <will@kernel.org>

    [ Upstream commit dcb786493f3e48da3272b710028d42ec608cfda1 ]

    Rewrite the generic REFCOUNT_FULL implementation so that the saturation
    point is moved to INT_MIN / 2. This allows us to defer the sanity checks
    until after the atomic operation, which removes many uses of cmpxchg()
    in favour of atomic_fetch_{add,sub}().

    Some crude perf results obtained from lkdtm show substantially less
    overhead, despite the checking:

    $ perf stat -r 3 -B -- echo {ATOMIC,REFCOUNT}_TIMING >/sys/kernel/debug/provoke-crash/DIRECT

    # arm64
    ATOMIC_TIMING: 46.50451 +- 0.00134 seconds time elapsed ( +- 0.00% )
    REFCOUNT_TIMING (REFCOUNT_FULL, mainline): 77.57522 +- 0.00982 seconds time elapsed ( +- 0.01% )
    REFCOUNT_TIMING (REFCOUNT_FULL, this series): 48.7181 +- 0.0256 seconds time elapsed ( +- 0.05% )

    # x86
    ATOMIC_TIMING: 31.6225 +- 0.0776 seconds time elapsed ( +- 0.25% )
    REFCOUNT_TIMING (!REFCOUNT_FULL, mainline/x86 asm): 31.6689 +- 0.0901 seconds time elapsed ( +- 0.28% )
    REFCOUNT_TIMING (REFCOUNT_FULL, mainline): 53.203 +- 0.138 seconds time elapsed ( +- 0.26% )
    REFCOUNT_TIMING (REFCOUNT_FULL, this series): 31.7408 +- 0.0486 seconds time elapsed ( +- 0.15% )

    Signed-off-by: Will Deacon <will@kernel.org>
    Reviewed-by: Ard Biesheuvel <ardb@kernel.org>
    Reviewed-by: Kees Cook <keescook@chromium.org>
    Tested-by: Hanjun Guo <guohanjun@huawei.com>
    Tested-by: Jan Glauber <jglauber@marvell.com>
    Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
    Cc: Elena Reshetova <elena.reshetova@intel.com>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Link: https://lkml.kernel.org/r/20191121115902.2551-6-will@kernel.org
    Signed-off-by: Ingo Molnar <mingo@kernel.org>
    Signed-off-by: Sasha Levin <sashal@kernel.org>
    ---
    include/linux/refcount.h | 131 ++++++++++++++++++++++-----------------
    1 file changed, 75 insertions(+), 56 deletions(-)

    diff --git a/include/linux/refcount.h b/include/linux/refcount.h
    index e719b5b1220e..e3b218d669ce 100644
    --- a/include/linux/refcount.h
    +++ b/include/linux/refcount.h
    @@ -47,8 +47,8 @@ static inline unsigned int refcount_read(const refcount_t *r)
    #ifdef CONFIG_REFCOUNT_FULL
    #include <linux/bug.h>

    -#define REFCOUNT_MAX (UINT_MAX - 1)
    -#define REFCOUNT_SATURATED UINT_MAX
    +#define REFCOUNT_MAX INT_MAX
    +#define REFCOUNT_SATURATED (INT_MIN / 2)

    /*
    * Variant of atomic_t specialized for reference counts.
    @@ -56,9 +56,47 @@ static inline unsigned int refcount_read(const refcount_t *r)
    * The interface matches the atomic_t interface (to aid in porting) but only
    * provides the few functions one should use for reference counting.
    *
    - * It differs in that the counter saturates at REFCOUNT_SATURATED and will not
    - * move once there. This avoids wrapping the counter and causing 'spurious'
    - * use-after-free issues.
    + * Saturation semantics
    + * ====================
    + *
    + * refcount_t differs from atomic_t in that the counter saturates at
    + * REFCOUNT_SATURATED and will not move once there. This avoids wrapping the
    + * counter and causing 'spurious' use-after-free issues. In order to avoid the
    + * cost associated with introducing cmpxchg() loops into all of the saturating
    + * operations, we temporarily allow the counter to take on an unchecked value
    + * and then explicitly set it to REFCOUNT_SATURATED on detecting that underflow
    + * or overflow has occurred. Although this is racy when multiple threads
    + * access the refcount concurrently, by placing REFCOUNT_SATURATED roughly
    + * equidistant from 0 and INT_MAX we minimise the scope for error:
    + *
    + * INT_MAX REFCOUNT_SATURATED UINT_MAX
    + * 0 (0x7fff_ffff) (0xc000_0000) (0xffff_ffff)
    + * +--------------------------------+----------------+----------------+
    + * <---------- bad value! ---------->
    + *
    + * (in a signed view of the world, the "bad value" range corresponds to
    + * a negative counter value).
    + *
    + * As an example, consider a refcount_inc() operation that causes the counter
    + * to overflow:
    + *
    + * int old = atomic_fetch_add_relaxed(r);
    + * // old is INT_MAX, refcount now INT_MIN (0x8000_0000)
    + * if (old < 0)
    + * atomic_set(r, REFCOUNT_SATURATED);
    + *
    + * If another thread also performs a refcount_inc() operation between the two
    + * atomic operations, then the count will continue to edge closer to 0. If it
    + * reaches a value of 1 before /any/ of the threads reset it to the saturated
    + * value, then a concurrent refcount_dec_and_test() may erroneously free the
    + * underlying object. Given the precise timing details involved with the
    + * round-robin scheduling of each thread manipulating the refcount and the need
    + * to hit the race multiple times in succession, there doesn't appear to be a
    + * practical avenue of attack even if using refcount_add() operations with
    + * larger increments.
    + *
    + * Memory ordering
    + * ===============
    *
    * Memory ordering rules are slightly relaxed wrt regular atomic_t functions
    * and provide only what is strictly required for refcounts.
    @@ -109,25 +147,19 @@ static inline unsigned int refcount_read(const refcount_t *r)
    */
    static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r)
    {
    - unsigned int new, val = atomic_read(&r->refs);
    + int old = refcount_read(r);

    do {
    - if (!val)
    - return false;
    -
    - if (unlikely(val == REFCOUNT_SATURATED))
    - return true;
    -
    - new = val + i;
    - if (new < val)
    - new = REFCOUNT_SATURATED;
    + if (!old)
    + break;
    + } while (!atomic_try_cmpxchg_relaxed(&r->refs, &old, old + i));

    - } while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
    -
    - WARN_ONCE(new == REFCOUNT_SATURATED,
    - "refcount_t: saturated; leaking memory.\n");
    + if (unlikely(old < 0 || old + i < 0)) {
    + refcount_set(r, REFCOUNT_SATURATED);
    + WARN_ONCE(1, "refcount_t: saturated; leaking memory.\n");
    + }

    - return true;
    + return old;
    }

    /**
    @@ -148,7 +180,13 @@ static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r)
    */
    static inline void refcount_add(int i, refcount_t *r)
    {
    - WARN_ONCE(!refcount_add_not_zero(i, r), "refcount_t: addition on 0; use-after-free.\n");
    + int old = atomic_fetch_add_relaxed(i, &r->refs);
    +
    + WARN_ONCE(!old, "refcount_t: addition on 0; use-after-free.\n");
    + if (unlikely(old <= 0 || old + i <= 0)) {
    + refcount_set(r, REFCOUNT_SATURATED);
    + WARN_ONCE(old, "refcount_t: saturated; leaking memory.\n");
    + }
    }

    /**
    @@ -166,23 +204,7 @@ static inline void refcount_add(int i, refcount_t *r)
    */
    static inline __must_check bool refcount_inc_not_zero(refcount_t *r)
    {
    - unsigned int new, val = atomic_read(&r->refs);
    -
    - do {
    - new = val + 1;
    -
    - if (!val)
    - return false;
    -
    - if (unlikely(!new))
    - return true;
    -
    - } while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
    -
    - WARN_ONCE(new == REFCOUNT_SATURATED,
    - "refcount_t: saturated; leaking memory.\n");
    -
    - return true;
    + return refcount_add_not_zero(1, r);
    }

    /**
    @@ -199,7 +221,7 @@ static inline __must_check bool refcount_inc_not_zero(refcount_t *r)
    */
    static inline void refcount_inc(refcount_t *r)
    {
    - WARN_ONCE(!refcount_inc_not_zero(r), "refcount_t: increment on 0; use-after-free.\n");
    + refcount_add(1, r);
    }

    /**
    @@ -224,26 +246,19 @@ static inline void refcount_inc(refcount_t *r)
    */
    static inline __must_check bool refcount_sub_and_test(int i, refcount_t *r)
    {
    - unsigned int new, val = atomic_read(&r->refs);
    -
    - do {
    - if (unlikely(val == REFCOUNT_SATURATED))
    - return false;
    + int old = atomic_fetch_sub_release(i, &r->refs);

    - new = val - i;
    - if (new > val) {
    - WARN_ONCE(new > val, "refcount_t: underflow; use-after-free.\n");
    - return false;
    - }
    -
    - } while (!atomic_try_cmpxchg_release(&r->refs, &val, new));
    -
    - if (!new) {
    + if (old == i) {
    smp_acquire__after_ctrl_dep();
    return true;
    }
    - return false;

    + if (unlikely(old < 0 || old - i < 0)) {
    + refcount_set(r, REFCOUNT_SATURATED);
    + WARN_ONCE(1, "refcount_t: underflow; use-after-free.\n");
    + }
    +
    + return false;
    }

    /**
    @@ -276,9 +291,13 @@ static inline __must_check bool refcount_dec_and_test(refcount_t *r)
    */
    static inline void refcount_dec(refcount_t *r)
    {
    - WARN_ONCE(refcount_dec_and_test(r), "refcount_t: decrement hit 0; leaking memory.\n");
    -}
    + int old = atomic_fetch_sub_release(1, &r->refs);

    + if (unlikely(old <= 1)) {
    + refcount_set(r, REFCOUNT_SATURATED);
    + WARN_ONCE(1, "refcount_t: decrement hit 0; leaking memory.\n");
    + }
    +}
    #else /* CONFIG_REFCOUNT_FULL */

    #define REFCOUNT_MAX INT_MAX
    --
    2.35.1


    \
     
     \ /
      Last update: 2022-07-27 18:45    [W:5.257 / U:0.016 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site