[PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Will Deacon]

Hi all,

This is version two of the patches I previously posted here:

  https://lkml.kernel.org/r/20190802101000.12958-1-will@kernel.org

Changes since v1 include:

  * Avoid duplicate WARNs when incrementing from zero
  * Some crude lktdm perf results to motivate the change:

    # 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% )

Cheers,

Will

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Cc: Hanjun Guo <guohanjun@huawei.com>
Cc: Jan Glauber <jglauber@marvell.com>

--->8

Will Deacon (6):
  lib/refcount: Define constants for saturation and max refcount values
  lib/refcount: Ensure integer operands are treated as signed
  lib/refcount: Remove unused refcount_*_checked() variants
  lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
  lib/refcount: Improve performance of generic REFCOUNT_FULL code
  lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions

 drivers/misc/lkdtm/refcount.c |   8 --
 include/linux/refcount.h      | 236 +++++++++++++++++++++++++++++++++++++----
 lib/refcount.c                | 237 +-----------------------------------------
 3 files changed, 218 insertions(+), 263 deletions(-)

-- 
2.11.0

[PATCH v2 1/6] lib/refcount: Define constants for saturation and max refcount values

[Will Deacon]

The REFCOUNT_FULL implementation uses a different saturation point than
the x86 implementation, which means that the shared refcount code in
lib/refcount.c (e.g. refcount_dec_not_one()) needs to be aware of the
difference.

Rather than duplicate the definitions from the lkdtm driver, instead
move them into linux/refcount.h and update all references accordingly.

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Will Deacon <will@kernel.org>
---
 drivers/misc/lkdtm/refcount.c |  8 --------
 include/linux/refcount.h      | 10 +++++++++-
 lib/refcount.c                | 37 ++++++++++++++++++++-----------------
 3 files changed, 29 insertions(+), 26 deletions(-)

diff --git a/drivers/misc/lkdtm/refcount.c b/drivers/misc/lkdtm/refcount.c
index 0a146b32da13..abf3b7c1f686 100644
--- a/drivers/misc/lkdtm/refcount.c
+++ b/drivers/misc/lkdtm/refcount.c
@@ -6,14 +6,6 @@
 #include "lkdtm.h"
 #include <linux/refcount.h>
 
-#ifdef CONFIG_REFCOUNT_FULL
-#define REFCOUNT_MAX		(UINT_MAX - 1)
-#define REFCOUNT_SATURATED	UINT_MAX
-#else
-#define REFCOUNT_MAX		INT_MAX
-#define REFCOUNT_SATURATED	(INT_MIN / 2)
-#endif
-
 static void overflow_check(refcount_t *ref)
 {
 	switch (refcount_read(ref)) {
diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index e28cce21bad6..79f62e8d2256 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -4,6 +4,7 @@
 
 #include <linux/atomic.h>
 #include <linux/compiler.h>
+#include <linux/limits.h>
 #include <linux/spinlock_types.h>
 
 struct mutex;
@@ -12,7 +13,7 @@ struct mutex;
  * struct refcount_t - variant of atomic_t specialized for reference counts
  * @refs: atomic_t counter field
  *
- * The counter saturates at UINT_MAX and will not move once
+ * The counter saturates at REFCOUNT_SATURATED and will not move once
  * there. This avoids wrapping the counter and causing 'spurious'
  * use-after-free bugs.
  */
@@ -56,6 +57,9 @@ extern void refcount_dec_checked(refcount_t *r);
 
 #ifdef CONFIG_REFCOUNT_FULL
 
+#define REFCOUNT_MAX		(UINT_MAX - 1)
+#define REFCOUNT_SATURATED	UINT_MAX
+
 #define refcount_add_not_zero	refcount_add_not_zero_checked
 #define refcount_add		refcount_add_checked
 
@@ -68,6 +72,10 @@ extern void refcount_dec_checked(refcount_t *r);
 #define refcount_dec		refcount_dec_checked
 
 #else
+
+#define REFCOUNT_MAX		INT_MAX
+#define REFCOUNT_SATURATED	(INT_MIN / 2)
+
 # ifdef CONFIG_ARCH_HAS_REFCOUNT
 #  include <asm/refcount.h>
 # else
diff --git a/lib/refcount.c b/lib/refcount.c
index 6e904af0fb3e..48b78a423d7d 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -5,8 +5,8 @@
  * 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 UINT_MAX and will not move once
- * there. This avoids wrapping the counter and causing 'spurious'
+ * 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.
  *
  * Memory ordering rules are slightly relaxed wrt regular atomic_t functions
@@ -48,7 +48,7 @@
  * @i: the value to add to the refcount
  * @r: the refcount
  *
- * Will saturate at UINT_MAX and WARN.
+ * Will saturate at REFCOUNT_SATURATED and WARN.
  *
  * 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
@@ -69,16 +69,17 @@ bool refcount_add_not_zero_checked(unsigned int i, refcount_t *r)
 		if (!val)
 			return false;
 
-		if (unlikely(val == UINT_MAX))
+		if (unlikely(val == REFCOUNT_SATURATED))
 			return true;
 
 		new = val + i;
 		if (new < val)
-			new = UINT_MAX;
+			new = REFCOUNT_SATURATED;
 
 	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
 
-	WARN_ONCE(new == UINT_MAX, "refcount_t: saturated; leaking memory.\n");
+	WARN_ONCE(new == REFCOUNT_SATURATED,
+		  "refcount_t: saturated; leaking memory.\n");
 
 	return true;
 }
@@ -89,7 +90,7 @@ EXPORT_SYMBOL(refcount_add_not_zero_checked);
  * @i: the value to add to the refcount
  * @r: the refcount
  *
- * Similar to atomic_add(), but will saturate at UINT_MAX and WARN.
+ * Similar to atomic_add(), but will saturate at REFCOUNT_SATURATED and WARN.
  *
  * 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
@@ -110,7 +111,8 @@ EXPORT_SYMBOL(refcount_add_checked);
  * refcount_inc_not_zero_checked - increment a refcount unless it is 0
  * @r: the refcount to increment
  *
- * Similar to atomic_inc_not_zero(), but will saturate at UINT_MAX and WARN.
+ * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED
+ * and WARN.
  *
  * 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
@@ -133,7 +135,8 @@ bool refcount_inc_not_zero_checked(refcount_t *r)
 
 	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
 
-	WARN_ONCE(new == UINT_MAX, "refcount_t: saturated; leaking memory.\n");
+	WARN_ONCE(new == REFCOUNT_SATURATED,
+		  "refcount_t: saturated; leaking memory.\n");
 
 	return true;
 }
@@ -143,7 +146,7 @@ EXPORT_SYMBOL(refcount_inc_not_zero_checked);
  * refcount_inc_checked - increment a refcount
  * @r: the refcount to increment
  *
- * Similar to atomic_inc(), but will saturate at UINT_MAX and WARN.
+ * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN.
  *
  * Provides no memory ordering, it is assumed the caller already has a
  * reference on the object.
@@ -164,7 +167,7 @@ EXPORT_SYMBOL(refcount_inc_checked);
  *
  * Similar to atomic_dec_and_test(), but it will WARN, return false and
  * ultimately leak on underflow and will fail to decrement when saturated
- * at UINT_MAX.
+ * at REFCOUNT_SATURATED.
  *
  * Provides release memory ordering, such that prior loads and stores are done
  * before, and provides an acquire ordering on success such that free()
@@ -182,7 +185,7 @@ bool refcount_sub_and_test_checked(unsigned int i, refcount_t *r)
 	unsigned int new, val = atomic_read(&r->refs);
 
 	do {
-		if (unlikely(val == UINT_MAX))
+		if (unlikely(val == REFCOUNT_SATURATED))
 			return false;
 
 		new = val - i;
@@ -207,7 +210,7 @@ EXPORT_SYMBOL(refcount_sub_and_test_checked);
  * @r: the refcount
  *
  * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
- * decrement when saturated at UINT_MAX.
+ * decrement when saturated at REFCOUNT_SATURATED.
  *
  * Provides release memory ordering, such that prior loads and stores are done
  * before, and provides an acquire ordering on success such that free()
@@ -226,7 +229,7 @@ EXPORT_SYMBOL(refcount_dec_and_test_checked);
  * @r: the refcount
  *
  * Similar to atomic_dec(), it will WARN on underflow and fail to decrement
- * when saturated at UINT_MAX.
+ * when saturated at REFCOUNT_SATURATED.
  *
  * Provides release memory ordering, such that prior loads and stores are done
  * before.
@@ -277,7 +280,7 @@ bool refcount_dec_not_one(refcount_t *r)
 	unsigned int new, val = atomic_read(&r->refs);
 
 	do {
-		if (unlikely(val == UINT_MAX))
+		if (unlikely(val == REFCOUNT_SATURATED))
 			return true;
 
 		if (val == 1)
@@ -302,7 +305,7 @@ EXPORT_SYMBOL(refcount_dec_not_one);
  * @lock: the mutex to be locked
  *
  * Similar to atomic_dec_and_mutex_lock(), it will WARN on underflow and fail
- * to decrement when saturated at UINT_MAX.
+ * to decrement when saturated at REFCOUNT_SATURATED.
  *
  * Provides release memory ordering, such that prior loads and stores are done
  * before, and provides a control dependency such that free() must come after.
@@ -333,7 +336,7 @@ EXPORT_SYMBOL(refcount_dec_and_mutex_lock);
  * @lock: the spinlock to be locked
  *
  * Similar to atomic_dec_and_lock(), it will WARN on underflow and fail to
- * decrement when saturated at UINT_MAX.
+ * decrement when saturated at REFCOUNT_SATURATED.
  *
  * Provides release memory ordering, such that prior loads and stores are done
  * before, and provides a control dependency such that free() must come after.
-- 
2.11.0

[PATCH v2 2/6] lib/refcount: Ensure integer operands are treated as signed

[Will Deacon]

In preparation for changing the saturation point of REFCOUNT_FULL to
INT_MIN / 2, change the type of integer operands passed into the API
from 'unsigned int' to 'int' so that we can avoid casting during
comparisons when we don't want to fall foul of C integral conversion
rules for signed and unsigned types.

Since the kernel is compiled with '-fno-strict-overflow', we don't need
to worry about the UB introduced by signed overflow here. Furthermore,
we're already making heavy use of the atomic_t API, which operates
exclusively on signed types.

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Will Deacon <will@kernel.org>
---
 include/linux/refcount.h | 14 +++++++-------
 lib/refcount.c           |  6 +++---
 2 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index 79f62e8d2256..89066a1471dd 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -28,7 +28,7 @@ typedef struct refcount_struct {
  * @r: the refcount
  * @n: value to which the refcount will be set
  */
-static inline void refcount_set(refcount_t *r, unsigned int n)
+static inline void refcount_set(refcount_t *r, int n)
 {
 	atomic_set(&r->refs, n);
 }
@@ -44,13 +44,13 @@ static inline unsigned int refcount_read(const refcount_t *r)
 	return atomic_read(&r->refs);
 }
 
-extern __must_check bool refcount_add_not_zero_checked(unsigned int i, refcount_t *r);
-extern void refcount_add_checked(unsigned int i, refcount_t *r);
+extern __must_check bool refcount_add_not_zero_checked(int i, refcount_t *r);
+extern void refcount_add_checked(int i, refcount_t *r);
 
 extern __must_check bool refcount_inc_not_zero_checked(refcount_t *r);
 extern void refcount_inc_checked(refcount_t *r);
 
-extern __must_check bool refcount_sub_and_test_checked(unsigned int i, refcount_t *r);
+extern __must_check bool refcount_sub_and_test_checked(int i, refcount_t *r);
 
 extern __must_check bool refcount_dec_and_test_checked(refcount_t *r);
 extern void refcount_dec_checked(refcount_t *r);
@@ -79,12 +79,12 @@ extern void refcount_dec_checked(refcount_t *r);
 # ifdef CONFIG_ARCH_HAS_REFCOUNT
 #  include <asm/refcount.h>
 # else
-static inline __must_check bool refcount_add_not_zero(unsigned int i, refcount_t *r)
+static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r)
 {
 	return atomic_add_unless(&r->refs, i, 0);
 }
 
-static inline void refcount_add(unsigned int i, refcount_t *r)
+static inline void refcount_add(int i, refcount_t *r)
 {
 	atomic_add(i, &r->refs);
 }
@@ -99,7 +99,7 @@ static inline void refcount_inc(refcount_t *r)
 	atomic_inc(&r->refs);
 }
 
-static inline __must_check bool refcount_sub_and_test(unsigned int i, refcount_t *r)
+static inline __must_check bool refcount_sub_and_test(int i, refcount_t *r)
 {
 	return atomic_sub_and_test(i, &r->refs);
 }
diff --git a/lib/refcount.c b/lib/refcount.c
index 48b78a423d7d..719b0bc42ab1 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -61,7 +61,7 @@
  *
  * Return: false if the passed refcount is 0, true otherwise
  */
-bool refcount_add_not_zero_checked(unsigned int i, refcount_t *r)
+bool refcount_add_not_zero_checked(int i, refcount_t *r)
 {
 	unsigned int new, val = atomic_read(&r->refs);
 
@@ -101,7 +101,7 @@ EXPORT_SYMBOL(refcount_add_not_zero_checked);
  * cases, refcount_inc(), or one of its variants, should instead be used to
  * increment a reference count.
  */
-void refcount_add_checked(unsigned int i, refcount_t *r)
+void refcount_add_checked(int i, refcount_t *r)
 {
 	WARN_ONCE(!refcount_add_not_zero_checked(i, r), "refcount_t: addition on 0; use-after-free.\n");
 }
@@ -180,7 +180,7 @@ EXPORT_SYMBOL(refcount_inc_checked);
  *
  * Return: true if the resulting refcount is 0, false otherwise
  */
-bool refcount_sub_and_test_checked(unsigned int i, refcount_t *r)
+bool refcount_sub_and_test_checked(int i, refcount_t *r)
 {
 	unsigned int new, val = atomic_read(&r->refs);
 
-- 
2.11.0

[PATCH v2 3/6] lib/refcount: Remove unused refcount_*_checked() variants

[Will Deacon]

The full-fat refcount implementation is exposed via a set of functions
suffixed with "_checked()", the idea being that code can choose to use
the more expensive, yet more secure implementation on a case-by-case
basis.

In reality, this hasn't happened, so with a grand total of zero users,
let's remove the checked variants for now by simply dropping the suffix
and predicating the out-of-line functions on CONFIG_REFCOUNT_FULL=y.

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Will Deacon <will@kernel.org>
---
 include/linux/refcount.h | 25 +++++++---------------
 lib/refcount.c           | 54 ++++++++++++++++++++++++++----------------------
 2 files changed, 36 insertions(+), 43 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index 89066a1471dd..edd505d1a23b 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -44,32 +44,21 @@ static inline unsigned int refcount_read(const refcount_t *r)
 	return atomic_read(&r->refs);
 }
 
-extern __must_check bool refcount_add_not_zero_checked(int i, refcount_t *r);
-extern void refcount_add_checked(int i, refcount_t *r);
-
-extern __must_check bool refcount_inc_not_zero_checked(refcount_t *r);
-extern void refcount_inc_checked(refcount_t *r);
-
-extern __must_check bool refcount_sub_and_test_checked(int i, refcount_t *r);
-
-extern __must_check bool refcount_dec_and_test_checked(refcount_t *r);
-extern void refcount_dec_checked(refcount_t *r);
-
 #ifdef CONFIG_REFCOUNT_FULL
 
 #define REFCOUNT_MAX		(UINT_MAX - 1)
 #define REFCOUNT_SATURATED	UINT_MAX
 
-#define refcount_add_not_zero	refcount_add_not_zero_checked
-#define refcount_add		refcount_add_checked
+extern __must_check bool refcount_add_not_zero(int i, refcount_t *r);
+extern void refcount_add(int i, refcount_t *r);
 
-#define refcount_inc_not_zero	refcount_inc_not_zero_checked
-#define refcount_inc		refcount_inc_checked
+extern __must_check bool refcount_inc_not_zero(refcount_t *r);
+extern void refcount_inc(refcount_t *r);
 
-#define refcount_sub_and_test	refcount_sub_and_test_checked
+extern __must_check bool refcount_sub_and_test(int i, refcount_t *r);
 
-#define refcount_dec_and_test	refcount_dec_and_test_checked
-#define refcount_dec		refcount_dec_checked
+extern __must_check bool refcount_dec_and_test(refcount_t *r);
+extern void refcount_dec(refcount_t *r);
 
 #else
 
diff --git a/lib/refcount.c b/lib/refcount.c
index 719b0bc42ab1..a2f670998cee 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -43,8 +43,10 @@
 #include <linux/spinlock.h>
 #include <linux/bug.h>
 
+#ifdef CONFIG_REFCOUNT_FULL
+
 /**
- * refcount_add_not_zero_checked - add a value to a refcount unless it is 0
+ * refcount_add_not_zero - add a value to a refcount unless it is 0
  * @i: the value to add to the refcount
  * @r: the refcount
  *
@@ -61,7 +63,7 @@
  *
  * Return: false if the passed refcount is 0, true otherwise
  */
-bool refcount_add_not_zero_checked(int i, refcount_t *r)
+bool refcount_add_not_zero(int i, refcount_t *r)
 {
 	unsigned int new, val = atomic_read(&r->refs);
 
@@ -83,10 +85,10 @@ bool refcount_add_not_zero_checked(int i, refcount_t *r)
 
 	return true;
 }
-EXPORT_SYMBOL(refcount_add_not_zero_checked);
+EXPORT_SYMBOL(refcount_add_not_zero);
 
 /**
- * refcount_add_checked - add a value to a refcount
+ * refcount_add - add a value to a refcount
  * @i: the value to add to the refcount
  * @r: the refcount
  *
@@ -101,14 +103,14 @@ EXPORT_SYMBOL(refcount_add_not_zero_checked);
  * cases, refcount_inc(), or one of its variants, should instead be used to
  * increment a reference count.
  */
-void refcount_add_checked(int i, refcount_t *r)
+void refcount_add(int i, refcount_t *r)
 {
-	WARN_ONCE(!refcount_add_not_zero_checked(i, r), "refcount_t: addition on 0; use-after-free.\n");
+	WARN_ONCE(!refcount_add_not_zero(i, r), "refcount_t: addition on 0; use-after-free.\n");
 }
-EXPORT_SYMBOL(refcount_add_checked);
+EXPORT_SYMBOL(refcount_add);
 
 /**
- * refcount_inc_not_zero_checked - increment a refcount unless it is 0
+ * refcount_inc_not_zero - increment a refcount unless it is 0
  * @r: the refcount to increment
  *
  * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED
@@ -120,7 +122,7 @@ EXPORT_SYMBOL(refcount_add_checked);
  *
  * Return: true if the increment was successful, false otherwise
  */
-bool refcount_inc_not_zero_checked(refcount_t *r)
+bool refcount_inc_not_zero(refcount_t *r)
 {
 	unsigned int new, val = atomic_read(&r->refs);
 
@@ -140,10 +142,10 @@ bool refcount_inc_not_zero_checked(refcount_t *r)
 
 	return true;
 }
-EXPORT_SYMBOL(refcount_inc_not_zero_checked);
+EXPORT_SYMBOL(refcount_inc_not_zero);
 
 /**
- * refcount_inc_checked - increment a refcount
+ * refcount_inc - increment a refcount
  * @r: the refcount to increment
  *
  * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN.
@@ -154,14 +156,14 @@ EXPORT_SYMBOL(refcount_inc_not_zero_checked);
  * Will WARN if the refcount is 0, as this represents a possible use-after-free
  * condition.
  */
-void refcount_inc_checked(refcount_t *r)
+void refcount_inc(refcount_t *r)
 {
-	WARN_ONCE(!refcount_inc_not_zero_checked(r), "refcount_t: increment on 0; use-after-free.\n");
+	WARN_ONCE(!refcount_inc_not_zero(r), "refcount_t: increment on 0; use-after-free.\n");
 }
-EXPORT_SYMBOL(refcount_inc_checked);
+EXPORT_SYMBOL(refcount_inc);
 
 /**
- * refcount_sub_and_test_checked - subtract from a refcount and test if it is 0
+ * refcount_sub_and_test - subtract from a refcount and test if it is 0
  * @i: amount to subtract from the refcount
  * @r: the refcount
  *
@@ -180,7 +182,7 @@ EXPORT_SYMBOL(refcount_inc_checked);
  *
  * Return: true if the resulting refcount is 0, false otherwise
  */
-bool refcount_sub_and_test_checked(int i, refcount_t *r)
+bool refcount_sub_and_test(int i, refcount_t *r)
 {
 	unsigned int new, val = atomic_read(&r->refs);
 
@@ -203,10 +205,10 @@ bool refcount_sub_and_test_checked(int i, refcount_t *r)
 	return false;
 
 }
-EXPORT_SYMBOL(refcount_sub_and_test_checked);
+EXPORT_SYMBOL(refcount_sub_and_test);
 
 /**
- * refcount_dec_and_test_checked - decrement a refcount and test if it is 0
+ * refcount_dec_and_test - decrement a refcount and test if it is 0
  * @r: the refcount
  *
  * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
@@ -218,14 +220,14 @@ EXPORT_SYMBOL(refcount_sub_and_test_checked);
  *
  * Return: true if the resulting refcount is 0, false otherwise
  */
-bool refcount_dec_and_test_checked(refcount_t *r)
+bool refcount_dec_and_test(refcount_t *r)
 {
-	return refcount_sub_and_test_checked(1, r);
+	return refcount_sub_and_test(1, r);
 }
-EXPORT_SYMBOL(refcount_dec_and_test_checked);
+EXPORT_SYMBOL(refcount_dec_and_test);
 
 /**
- * refcount_dec_checked - decrement a refcount
+ * refcount_dec - decrement a refcount
  * @r: the refcount
  *
  * Similar to atomic_dec(), it will WARN on underflow and fail to decrement
@@ -234,11 +236,13 @@ EXPORT_SYMBOL(refcount_dec_and_test_checked);
  * Provides release memory ordering, such that prior loads and stores are done
  * before.
  */
-void refcount_dec_checked(refcount_t *r)
+void refcount_dec(refcount_t *r)
 {
-	WARN_ONCE(refcount_dec_and_test_checked(r), "refcount_t: decrement hit 0; leaking memory.\n");
+	WARN_ONCE(refcount_dec_and_test(r), "refcount_t: decrement hit 0; leaking memory.\n");
 }
-EXPORT_SYMBOL(refcount_dec_checked);
+EXPORT_SYMBOL(refcount_dec);
+
+#endif /* CONFIG_REFCOUNT_FULL */
 
 /**
  * refcount_dec_if_one - decrement a refcount if it is 1
-- 
2.11.0

[PATCH v2 4/6] lib/refcount: Move bulk of REFCOUNT_FULL implementation into header

[Will Deacon]

In an effort to improve performance of the REFCOUNT_FULL implementation,
move the bulk of its functions into linux/refcount.h. This allows them
to be inlined in the same way as if they had been provided via
CONFIG_ARCH_HAS_REFCOUNT.

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Will Deacon <will@kernel.org>
---
 include/linux/refcount.h | 237 ++++++++++++++++++++++++++++++++++++++++++++--
 lib/refcount.c           | 238 +----------------------------------------------
 2 files changed, 229 insertions(+), 246 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index edd505d1a23b..e719b5b1220e 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -45,22 +45,241 @@ 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
 
-extern __must_check bool refcount_add_not_zero(int i, refcount_t *r);
-extern void refcount_add(int i, refcount_t *r);
+/*
+ * Variant of atomic_t specialized for reference counts.
+ *
+ * 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.
+ *
+ * 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 we're increasing 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.
+ *
+ * Do note that inc_not_zero() provides a control dependency which will order
+ * future stores against the inc, this ensures we'll never modify the object
+ * if we did not in fact acquire a reference.
+ *
+ * The decrements will provide release order, such that all the prior loads and
+ * stores will be issued before, it also provides a control dependency, which
+ * will order us against the subsequent free().
+ *
+ * The control dependency is against the load of the cmpxchg (ll/sc) that
+ * succeeded. This means the stores aren't fully ordered, but this is fine
+ * because the 1->0 transition indicates no concurrency.
+ *
+ * Note that the allocator is responsible for ordering things between free()
+ * and alloc().
+ *
+ * The decrements dec_and_test() and sub_and_test() also provide acquire
+ * ordering on success.
+ *
+ */
+
+/**
+ * refcount_add_not_zero - add a value to a refcount unless it is 0
+ * @i: the value to add to the refcount
+ * @r: the refcount
+ *
+ * Will saturate at REFCOUNT_SATURATED and WARN.
+ *
+ * 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 the comment on top.
+ *
+ * Use of this function is not recommended for the normal reference counting
+ * use case in which references are taken and released one at a time.  In these
+ * cases, refcount_inc(), or one of its variants, should instead be used to
+ * increment a reference count.
+ *
+ * Return: false if the passed refcount is 0, true otherwise
+ */
+static inline __must_check bool refcount_add_not_zero(int i, refcount_t *r)
+{
+	unsigned int new, val = atomic_read(&r->refs);
+
+	do {
+		if (!val)
+			return false;
+
+		if (unlikely(val == REFCOUNT_SATURATED))
+			return true;
+
+		new = val + i;
+		if (new < val)
+			new = REFCOUNT_SATURATED;
+
+	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
+
+	WARN_ONCE(new == REFCOUNT_SATURATED,
+		  "refcount_t: saturated; leaking memory.\n");
+
+	return true;
+}
+
+/**
+ * refcount_add - add a value to a refcount
+ * @i: the value to add to the refcount
+ * @r: the refcount
+ *
+ * Similar to atomic_add(), but will saturate at REFCOUNT_SATURATED and WARN.
+ *
+ * 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 the comment on top.
+ *
+ * Use of this function is not recommended for the normal reference counting
+ * use case in which references are taken and released one at a time.  In these
+ * cases, refcount_inc(), or one of its variants, should instead be used to
+ * increment a reference count.
+ */
+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");
+}
+
+/**
+ * refcount_inc_not_zero - increment a refcount unless it is 0
+ * @r: the refcount to increment
+ *
+ * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED
+ * and WARN.
+ *
+ * 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 the comment on top.
+ *
+ * Return: true if the increment was successful, false otherwise
+ */
+static inline __must_check bool refcount_inc_not_zero(refcount_t *r)
+{
+	unsigned int new, val = atomic_read(&r->refs);
+
+	do {
+		new = val + 1;
 
-extern __must_check bool refcount_inc_not_zero(refcount_t *r);
-extern void refcount_inc(refcount_t *r);
+		if (!val)
+			return false;
 
-extern __must_check bool refcount_sub_and_test(int i, refcount_t *r);
+		if (unlikely(!new))
+			return true;
 
-extern __must_check bool refcount_dec_and_test(refcount_t *r);
-extern void refcount_dec(refcount_t *r);
+	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
+
+	WARN_ONCE(new == REFCOUNT_SATURATED,
+		  "refcount_t: saturated; leaking memory.\n");
+
+	return true;
+}
+
+/**
+ * refcount_inc - increment a refcount
+ * @r: the refcount to increment
+ *
+ * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN.
+ *
+ * Provides no memory ordering, it is assumed the caller already has a
+ * reference on the object.
+ *
+ * Will WARN if the refcount is 0, as this represents a possible use-after-free
+ * condition.
+ */
+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_sub_and_test - subtract from a refcount and test if it is 0
+ * @i: amount to subtract from the refcount
+ * @r: the refcount
+ *
+ * Similar to atomic_dec_and_test(), but it will WARN, return false and
+ * ultimately leak on underflow and will fail to decrement when saturated
+ * at REFCOUNT_SATURATED.
+ *
+ * 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.
+ *
+ * Use of this function is not recommended for the normal reference counting
+ * use case in which references are taken and released one at a time.  In these
+ * cases, refcount_dec(), or one of its variants, should instead be used to
+ * decrement a reference count.
+ *
+ * Return: true if the resulting refcount is 0, false otherwise
+ */
+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;
+
+		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) {
+		smp_acquire__after_ctrl_dep();
+		return true;
+	}
+	return false;
+
+}
+
+/**
+ * refcount_dec_and_test - decrement a refcount and test if it is 0
+ * @r: the refcount
+ *
+ * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
+ * decrement when saturated at REFCOUNT_SATURATED.
+ *
+ * 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 the resulting refcount is 0, false otherwise
+ */
+static inline __must_check bool refcount_dec_and_test(refcount_t *r)
+{
+	return refcount_sub_and_test(1, r);
+}
+
+/**
+ * refcount_dec - decrement a refcount
+ * @r: the refcount
+ *
+ * Similar to atomic_dec(), it will WARN on underflow and fail to decrement
+ * when saturated at REFCOUNT_SATURATED.
+ *
+ * Provides release memory ordering, such that prior loads and stores are done
+ * before.
+ */
+static inline void refcount_dec(refcount_t *r)
+{
+	WARN_ONCE(refcount_dec_and_test(r), "refcount_t: decrement hit 0; leaking memory.\n");
+}
 
-#else
+#else /* CONFIG_REFCOUNT_FULL */
 
 #define REFCOUNT_MAX		INT_MAX
 #define REFCOUNT_SATURATED	(INT_MIN / 2)
@@ -103,7 +322,7 @@ static inline void refcount_dec(refcount_t *r)
 	atomic_dec(&r->refs);
 }
 # endif /* !CONFIG_ARCH_HAS_REFCOUNT */
-#endif /* CONFIG_REFCOUNT_FULL */
+#endif /* !CONFIG_REFCOUNT_FULL */
 
 extern __must_check bool refcount_dec_if_one(refcount_t *r);
 extern __must_check bool refcount_dec_not_one(refcount_t *r);
diff --git a/lib/refcount.c b/lib/refcount.c
index a2f670998cee..3a534fbebdcc 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -1,41 +1,6 @@
 // SPDX-License-Identifier: GPL-2.0
 /*
- * Variant of atomic_t specialized for reference counts.
- *
- * 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.
- *
- * 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 we're increasing 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.
- *
- * Do note that inc_not_zero() provides a control dependency which will order
- * future stores against the inc, this ensures we'll never modify the object
- * if we did not in fact acquire a reference.
- *
- * The decrements will provide release order, such that all the prior loads and
- * stores will be issued before, it also provides a control dependency, which
- * will order us against the subsequent free().
- *
- * The control dependency is against the load of the cmpxchg (ll/sc) that
- * succeeded. This means the stores aren't fully ordered, but this is fine
- * because the 1->0 transition indicates no concurrency.
- *
- * Note that the allocator is responsible for ordering things between free()
- * and alloc().
- *
- * The decrements dec_and_test() and sub_and_test() also provide acquire
- * ordering on success.
- *
+ * Out-of-line refcount functions common to all refcount implementations.
  */
 
 #include <linux/mutex.h>
@@ -43,207 +8,6 @@
 #include <linux/spinlock.h>
 #include <linux/bug.h>
 
-#ifdef CONFIG_REFCOUNT_FULL
-
-/**
- * refcount_add_not_zero - add a value to a refcount unless it is 0
- * @i: the value to add to the refcount
- * @r: the refcount
- *
- * Will saturate at REFCOUNT_SATURATED and WARN.
- *
- * 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 the comment on top.
- *
- * Use of this function is not recommended for the normal reference counting
- * use case in which references are taken and released one at a time.  In these
- * cases, refcount_inc(), or one of its variants, should instead be used to
- * increment a reference count.
- *
- * Return: false if the passed refcount is 0, true otherwise
- */
-bool refcount_add_not_zero(int i, refcount_t *r)
-{
-	unsigned int new, val = atomic_read(&r->refs);
-
-	do {
-		if (!val)
-			return false;
-
-		if (unlikely(val == REFCOUNT_SATURATED))
-			return true;
-
-		new = val + i;
-		if (new < val)
-			new = REFCOUNT_SATURATED;
-
-	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
-
-	WARN_ONCE(new == REFCOUNT_SATURATED,
-		  "refcount_t: saturated; leaking memory.\n");
-
-	return true;
-}
-EXPORT_SYMBOL(refcount_add_not_zero);
-
-/**
- * refcount_add - add a value to a refcount
- * @i: the value to add to the refcount
- * @r: the refcount
- *
- * Similar to atomic_add(), but will saturate at REFCOUNT_SATURATED and WARN.
- *
- * 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 the comment on top.
- *
- * Use of this function is not recommended for the normal reference counting
- * use case in which references are taken and released one at a time.  In these
- * cases, refcount_inc(), or one of its variants, should instead be used to
- * increment a reference count.
- */
-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");
-}
-EXPORT_SYMBOL(refcount_add);
-
-/**
- * refcount_inc_not_zero - increment a refcount unless it is 0
- * @r: the refcount to increment
- *
- * Similar to atomic_inc_not_zero(), but will saturate at REFCOUNT_SATURATED
- * and WARN.
- *
- * 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 the comment on top.
- *
- * Return: true if the increment was successful, false otherwise
- */
-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;
-}
-EXPORT_SYMBOL(refcount_inc_not_zero);
-
-/**
- * refcount_inc - increment a refcount
- * @r: the refcount to increment
- *
- * Similar to atomic_inc(), but will saturate at REFCOUNT_SATURATED and WARN.
- *
- * Provides no memory ordering, it is assumed the caller already has a
- * reference on the object.
- *
- * Will WARN if the refcount is 0, as this represents a possible use-after-free
- * condition.
- */
-void refcount_inc(refcount_t *r)
-{
-	WARN_ONCE(!refcount_inc_not_zero(r), "refcount_t: increment on 0; use-after-free.\n");
-}
-EXPORT_SYMBOL(refcount_inc);
-
-/**
- * refcount_sub_and_test - subtract from a refcount and test if it is 0
- * @i: amount to subtract from the refcount
- * @r: the refcount
- *
- * Similar to atomic_dec_and_test(), but it will WARN, return false and
- * ultimately leak on underflow and will fail to decrement when saturated
- * at REFCOUNT_SATURATED.
- *
- * 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.
- *
- * Use of this function is not recommended for the normal reference counting
- * use case in which references are taken and released one at a time.  In these
- * cases, refcount_dec(), or one of its variants, should instead be used to
- * decrement a reference count.
- *
- * Return: true if the resulting refcount is 0, false otherwise
- */
-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;
-
-		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) {
-		smp_acquire__after_ctrl_dep();
-		return true;
-	}
-	return false;
-
-}
-EXPORT_SYMBOL(refcount_sub_and_test);
-
-/**
- * refcount_dec_and_test - decrement a refcount and test if it is 0
- * @r: the refcount
- *
- * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
- * decrement when saturated at REFCOUNT_SATURATED.
- *
- * 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 the resulting refcount is 0, false otherwise
- */
-bool refcount_dec_and_test(refcount_t *r)
-{
-	return refcount_sub_and_test(1, r);
-}
-EXPORT_SYMBOL(refcount_dec_and_test);
-
-/**
- * refcount_dec - decrement a refcount
- * @r: the refcount
- *
- * Similar to atomic_dec(), it will WARN on underflow and fail to decrement
- * when saturated at REFCOUNT_SATURATED.
- *
- * Provides release memory ordering, such that prior loads and stores are done
- * before.
- */
-void refcount_dec(refcount_t *r)
-{
-	WARN_ONCE(refcount_dec_and_test(r), "refcount_t: decrement hit 0; leaking memory.\n");
-}
-EXPORT_SYMBOL(refcount_dec);
-
-#endif /* CONFIG_REFCOUNT_FULL */
-
 /**
  * refcount_dec_if_one - decrement a refcount if it is 1
  * @r: the refcount
-- 
2.11.0

[PATCH v2 5/6] lib/refcount: Improve performance of generic REFCOUNT_FULL code

[Will Deacon]

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}().

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Tested-by: Hanjun Guo <guohanjun@huawei.com>
Tested-by: Jan Glauber <jglauber@marvell.com>
Signed-off-by: Will Deacon <will@kernel.org>
---
 include/linux/refcount.h | 87 +++++++++++++++++++-----------------------------
 1 file changed, 34 insertions(+), 53 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index e719b5b1220e..7f9aa6511142 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.
@@ -109,25 +109,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 +142,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 +166,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 +183,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 +208,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 - i < 0)) {
+		refcount_set(r, REFCOUNT_SATURATED);
+		WARN_ONCE(1, "refcount_t: underflow; use-after-free.\n");
+	}
+
+	return false;
 }
 
 /**
@@ -276,9 +253,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.11.0

[PATCH v2 6/6] lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions

[Will Deacon]

The definitions of REFCOUNT_MAX and REFCOUNT_SATURATED are the same,
regardless of CONFIG_REFCOUNT_FULL, so consolidate them into a single
pair of definitions.

Cc: Kees Cook <keescook@chromium.org>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Elena Reshetova <elena.reshetova@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Will Deacon <will@kernel.org>
---
 include/linux/refcount.h | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index 7f9aa6511142..1f7e364cfb6d 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -22,6 +22,8 @@ typedef struct refcount_struct {
 } refcount_t;
 
 #define REFCOUNT_INIT(n)	{ .refs = ATOMIC_INIT(n), }
+#define REFCOUNT_MAX		INT_MAX
+#define REFCOUNT_SATURATED	(INT_MIN / 2)
 
 /**
  * refcount_set - set a refcount's value
@@ -47,9 +49,6 @@ static inline unsigned int refcount_read(const refcount_t *r)
 #ifdef CONFIG_REFCOUNT_FULL
 #include <linux/bug.h>
 
-#define REFCOUNT_MAX		INT_MAX
-#define REFCOUNT_SATURATED	(INT_MIN / 2)
-
 /*
  * Variant of atomic_t specialized for reference counts.
  *
@@ -261,10 +260,6 @@ static inline void refcount_dec(refcount_t *r)
 	}
 }
 #else /* CONFIG_REFCOUNT_FULL */
-
-#define REFCOUNT_MAX		INT_MAX
-#define REFCOUNT_SATURATED	(INT_MIN / 2)
-
 # ifdef CONFIG_ARCH_HAS_REFCOUNT
 #  include <asm/refcount.h>
 # else
-- 
2.11.0

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Kees Cook]

On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> Hi all,
> 
> This is version two of the patches I previously posted here:
> 
>   https://lkml.kernel.org/r/20190802101000.12958-1-will@kernel.org
> 
> Changes since v1 include:
> 
>   * Avoid duplicate WARNs when incrementing from zero
>   * Some crude lktdm perf results to motivate the change:
> 
>     # 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% )

Nice improvements! :) Please consider the series:

Reviewed-by: Kees Cook <keescook@chromium.org>

-Kees

> 
> Cheers,
> 
> Will
> 
> Cc: Kees Cook <keescook@chromium.org>
> Cc: Ingo Molnar <mingo@kernel.org>
> Cc: Elena Reshetova <elena.reshetova@intel.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
> Cc: Hanjun Guo <guohanjun@huawei.com>
> Cc: Jan Glauber <jglauber@marvell.com>
> 
> --->8
> 
> Will Deacon (6):
>   lib/refcount: Define constants for saturation and max refcount values
>   lib/refcount: Ensure integer operands are treated as signed
>   lib/refcount: Remove unused refcount_*_checked() variants
>   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
>   lib/refcount: Improve performance of generic REFCOUNT_FULL code
>   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions
> 
>  drivers/misc/lkdtm/refcount.c |   8 --
>  include/linux/refcount.h      | 236 +++++++++++++++++++++++++++++++++++++----
>  lib/refcount.c                | 237 +-----------------------------------------
>  3 files changed, 218 insertions(+), 263 deletions(-)
> 
> -- 
> 2.11.0
> 

-- 
Kees Cook

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Peter Zijlstra]

On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> Will Deacon (6):
>   lib/refcount: Define constants for saturation and max refcount values
>   lib/refcount: Ensure integer operands are treated as signed
>   lib/refcount: Remove unused refcount_*_checked() variants
>   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
>   lib/refcount: Improve performance of generic REFCOUNT_FULL code
>   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions

So I'm not a fan; I itch at the whole racy nature of this thing and I
find the code less than obvious. Yet, I have to agree it is exceedingly
unlikely the race will ever actually happen, I just don't want to be the
one having to debug it.

I've not looked at the implementation much; does it do all the same
checks the FULL one does? The x86-asm one misses a few iirc, so if this
is similarly fast but has all the checks, it is in fact better.

Can't we make this a default !FULL implementation?

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Will Deacon]

On Wed, Aug 28, 2019 at 09:30:52AM +0200, Peter Zijlstra wrote:
> On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> > Will Deacon (6):
> >   lib/refcount: Define constants for saturation and max refcount values
> >   lib/refcount: Ensure integer operands are treated as signed
> >   lib/refcount: Remove unused refcount_*_checked() variants
> >   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
> >   lib/refcount: Improve performance of generic REFCOUNT_FULL code
> >   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions
> 
> So I'm not a fan; I itch at the whole racy nature of this thing and I
> find the code less than obvious. Yet, I have to agree it is exceedingly
> unlikely the race will ever actually happen, I just don't want to be the
> one having to debug it.

FWIW, I think much the same about the version under arch/x86 ;)

> I've not looked at the implementation much; does it do all the same
> checks the FULL one does? The x86-asm one misses a few iirc, so if this
> is similarly fast but has all the checks, it is in fact better.

Yes, it passes all of the REFCOUNT_* tests in lkdtm [1] so I agree that
it's an improvement over the asm version.

> Can't we make this a default !FULL implementation?

My concern with doing that is I think it would make the FULL implementation
entirely pointless. I can't see anybody using it, and it would only exist
as an academic exercise in handling the theoretical races. That's a change
from the current situation where it genuinely handles cases which the
x86-specific code does not and, judging by the Kconfig text, that's the
only reason for its existence.

Will

[1]

bash-4.4# for t in `grep REFCOUNT DIRECT`; do echo $t > DIRECT; done
[  439.626480] lkdtm: Performing direct entry REFCOUNT_INC_OVERFLOW
[  439.629352] lkdtm: attempting good refcount_inc() without overflow
[  439.631335] lkdtm: attempting bad refcount_inc() overflow
[  439.633335] ------------[ cut here ]------------
[  439.635334] refcount_t: saturated; leaking memory.
[  439.636364] WARNING: CPU: 12 PID: 177 at ./include/linux/refcount.h:149 refcount_add.part.7+0x13/0x20
[  439.637329] Modules linked in:
[  439.637329] CPU: 12 PID: 177 Comm: bash Not tainted 5.3.0-rc3+ #1
[  439.637329] RIP: 0010:refcount_add.part.7+0x13/0x20
[  439.637329] Code: 32 a9 ff 48 c7 c7 f0 c1 e5 83 e9 81 32 a9 ff 0f 1f 84 00 00 00 00 00 48 c7 c7 20 39 dd 83 c6 05 00 ad f0 00 01 e8 4d cd a3 ff <0f> 0b c3 66 2e 0f 1f 84 00 00 00 00 00 8b 07 3d ff ff ff 7f 74 21
[  439.637329] RSP: 0018:ffffb51ec040be40 EFLAGS: 00010286
[  439.637329] RAX: 0000000000000000 RBX: 0000000000000027 RCX: ffffffff84049418
[  439.637329] RDX: 0000000000000001 RSI: 0000000000000082 RDI: ffffffff847030ac
[  439.637329] RBP: ffffffff83e5b35b R08: 000000000009b1c6 R09: 000000000000015c
[  439.637329] R10: ffffd77ac120fd00 R11: ffffb51ec040bce5 R12: ffff9dca883f4000
[  439.637329] R13: 0000000000d86408 R14: 0000000000000016 R15: ffffb51ec040bf08
[  439.637329] FS:  00007f7b86147700(0000) GS:ffff9dca8a400000(0000) knlGS:0000000000000000
[  439.637329] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  439.637329] CR2: 0000000000d86408 CR3: 00000000482b6003 CR4: 00000000001606a0
[  439.637329] Call Trace:
[  439.637329]  lkdtm_REFCOUNT_INC_OVERFLOW+0x16d/0x210
[  439.637329]  direct_entry+0xc5/0x110
[  439.637329]  full_proxy_write+0x4e/0x70
[  439.637329]  vfs_write+0xab/0x190
[  439.637329]  ksys_write+0x57/0xd0
[  439.637329]  do_syscall_64+0x43/0x110
[  439.637329]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[  439.637329] RIP: 0033:0x7f7b85836970
[  439.637329] Code: 73 01 c3 48 8b 0d 28 d5 2b 00 f7 d8 64 89 01 48 83 c8 ff c3 66 0f 1f 44 00 00 83 3d 99 2d 2c 00 00 75 10 b8 01 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 7e 9b 01 00 48 89 04 24
[  439.637329] RSP: 002b:00007ffc7ad9ae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  439.637329] RAX: ffffffffffffffda RBX: 0000000000000016 RCX: 00007f7b85836970
[  439.637329] RDX: 0000000000000016 RSI: 0000000000d86408 RDI: 0000000000000001
[  439.637329] RBP: 0000000000d86408 R08: 00007f7b85af6760 R09: 00007f7b86147700
[  439.637329] R10: 0000000000000073 R11: 0000000000000246 R12: 0000000000000016
[  439.637329] R13: 0000000000000001 R14: 00007f7b85af5600 R15: 0000000000000016
[  439.637329] ---[ end trace aedef77d83b518cc ]---
[  439.676328] lkdtm: Overflow detected: saturated
[  439.677384] lkdtm: Performing direct entry REFCOUNT_ADD_OVERFLOW
[  439.678326] lkdtm: attempting good refcount_add() without overflow
[  439.679325] lkdtm: attempting bad refcount_add() overflow
[  439.680325] lkdtm: Overflow detected: saturated
[  439.681117] lkdtm: Performing direct entry REFCOUNT_INC_NOT_ZERO_OVERFLOW
[  439.682325] lkdtm: attempting bad refcount_inc_not_zero() overflow
[  439.683324] ------------[ cut here ]------------
[  439.684071] refcount_t: saturated; leaking memory.
[  439.684340] WARNING: CPU: 12 PID: 177 at ./include/linux/refcount.h:120 lkdtm_REFCOUNT_INC_NOT_ZERO_OVERFLOW+0x88/0xb0
[  439.685321] Modules linked in:
[  439.685321] CPU: 12 PID: 177 Comm: bash Tainted: G        W         5.3.0-rc3+ #1
[  439.685321] RIP: 0010:lkdtm_REFCOUNT_INC_NOT_ZERO_OVERFLOW+0x88/0xb0
[  439.685321] Code: 41 48 83 c4 10 c3 80 3d e5 a7 f0 00 00 c7 44 24 04 00 00 00 c0 75 d0 48 c7 c7 20 39 dd 83 c6 05 cd a7 f0 00 01 e8 18 c8 a3 ff <0f> 0b eb b9 85 c0 89 c2 75 9e 48 c7 c7 50 c4 e5 83 e8 1b 2d a9 ff
[  439.685321] RSP: 0018:ffffb51ec040be48 EFLAGS: 00010282
[  439.685321] RAX: 0000000000000000 RBX: 0000000000000029 RCX: ffffffff84049418
[  439.685321] RDX: 0000000000000001 RSI: 0000000000000096 RDI: ffffffff847030ac
[  439.685321] RBP: ffffffff83e5aff0 R08: 00000000000a7027 R09: 0000000000000184
[  439.685321] R10: ffffd77ac120fd00 R11: ffffb51ec040bced R12: ffff9dca883f4000
[  439.685321] R13: 0000000000d86408 R14: 000000000000001f R15: ffffb51ec040bf08
[  439.685321] FS:  00007f7b86147700(0000) GS:ffff9dca8a400000(0000) knlGS:0000000000000000
[  439.685321] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  439.685321] CR2: 0000000000d88ea4 CR3: 00000000482b6003 CR4: 00000000001606a0
[  439.685321] Call Trace:
[  439.685321]  direct_entry+0xc5/0x110
[  439.685321]  full_proxy_write+0x4e/0x70
[  439.685321]  vfs_write+0xab/0x190
[  439.685321]  ksys_write+0x57/0xd0
[  439.685321]  do_syscall_64+0x43/0x110
[  439.685321]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[  439.685321] RIP: 0033:0x7f7b85836970
[  439.685321] Code: 73 01 c3 48 8b 0d 28 d5 2b 00 f7 d8 64 89 01 48 83 c8 ff c3 66 0f 1f 44 00 00 83 3d 99 2d 2c 00 00 75 10 b8 01 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 7e 9b 01 00 48 89 04 24
[  439.685321] RSP: 002b:00007ffc7ad9ae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  439.685321] RAX: ffffffffffffffda RBX: 000000000000001f RCX: 00007f7b85836970
[  439.685321] RDX: 000000000000001f RSI: 0000000000d86408 RDI: 0000000000000001
[  439.685321] RBP: 0000000000d86408 R08: 00007f7b85af6760 R09: 00007f7b86147700
[  439.685321] R10: 0000000000000073 R11: 0000000000000246 R12: 000000000000001f
[  439.685321] R13: 0000000000000001 R14: 00007f7b85af5600 R15: 000000000000001f
[  439.685321] ---[ end trace aedef77d83b518cd ]---
[  439.717319] lkdtm: Overflow detected: saturated
[  439.718352] lkdtm: Performing direct entry REFCOUNT_ADD_NOT_ZERO_OVERFLOW
[  439.719321] lkdtm: attempting bad refcount_add_not_zero() overflow
[  439.720319] lkdtm: Overflow detected: saturated
[  439.721036] lkdtm: Performing direct entry REFCOUNT_DEC_ZERO
[  439.721319] lkdtm: attempting good refcount_dec()
[  439.722318] lkdtm: attempting bad refcount_dec() to zero
[  439.723318] ------------[ cut here ]------------
[  439.724008] refcount_t: decrement hit 0; leaking memory.
[  439.724331] WARNING: CPU: 12 PID: 177 at ./include/linux/refcount.h:259 lkdtm_REFCOUNT_DEC_ZERO+0xe5/0x120
[  439.725315] Modules linked in:
[  439.725315] CPU: 12 PID: 177 Comm: bash Tainted: G        W         5.3.0-rc3+ #1
[  439.725315] RIP: 0010:lkdtm_REFCOUNT_DEC_ZERO+0xe5/0x120
[  439.725315] Code: 9a 2b a9 ff eb bd 80 3d 24 a6 f0 00 00 c7 44 24 04 00 00 00 c0 75 86 48 c7 c7 18 7d e0 83 c6 05 0c a6 f0 00 01 e8 5b c6 a3 ff <0f> 0b e9 6c ff ff ff 80 3d f9 a5 f0 00 00 c7 44 24 04 00 00 00 c0
[  439.725315] RSP: 0018:ffffb51ec040be48 EFLAGS: 00010282
[  439.725315] RAX: 0000000000000000 RBX: 000000000000002b RCX: ffffffff84049418
[  439.725315] RDX: 0000000000000001 RSI: 0000000000000096 RDI: ffffffff847030ac
[  439.725315] RBP: ffffffff83e5b387 R08: 00000000000b0c28 R09: 00000000000001ab
[  439.725315] R10: ffffd77ac120fd00 R11: ffffb51ec040bced R12: ffff9dca883f4000
[  439.725315] R13: 0000000000d86408 R14: 0000000000000012 R15: ffffb51ec040bf08
[  439.725315] FS:  00007f7b86147700(0000) GS:ffff9dca8a400000(0000) knlGS:0000000000000000
[  439.725315] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  439.725315] CR2: 0000000000d88ea4 CR3: 00000000482b6003 CR4: 00000000001606a0
[  439.725315] Call Trace:
[  439.725315]  direct_entry+0xc5/0x110
[  439.725315]  full_proxy_write+0x4e/0x70
[  439.725315]  vfs_write+0xab/0x190
[  439.725315]  ksys_write+0x57/0xd0
[  439.725315]  do_syscall_64+0x43/0x110
[  439.725315]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[  439.725315] RIP: 0033:0x7f7b85836970
[  439.725315] Code: 73 01 c3 48 8b 0d 28 d5 2b 00 f7 d8 64 89 01 48 83 c8 ff c3 66 0f 1f 44 00 00 83 3d 99 2d 2c 00 00 75 10 b8 01 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 7e 9b 01 00 48 89 04 24
[  439.725315] RSP: 002b:00007ffc7ad9ae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  439.725315] RAX: ffffffffffffffda RBX: 0000000000000012 RCX: 00007f7b85836970
[  439.725315] RDX: 0000000000000012 RSI: 0000000000d86408 RDI: 0000000000000001
[  439.725315] RBP: 0000000000d86408 R08: 00007f7b85af6760 R09: 00007f7b86147700
[  439.725315] R10: 0000000000000073 R11: 0000000000000246 R12: 0000000000000012
[  439.725315] R13: 0000000000000001 R14: 00007f7b85af5600 R15: 0000000000000012
[  439.725315] ---[ end trace aedef77d83b518ce ]---
[  439.755314] lkdtm: Zero detected: saturated
[  439.756357] lkdtm: Performing direct entry REFCOUNT_DEC_NEGATIVE
[  439.757313] lkdtm: attempting bad refcount_dec() below zero
[  439.758313] lkdtm: Negative detected: saturated
[  439.759351] lkdtm: Performing direct entry REFCOUNT_DEC_AND_TEST_NEGATIVE
[  439.760313] lkdtm: attempting bad refcount_dec_and_test() below zero
[  439.761312] ------------[ cut here ]------------
[  439.761990] refcount_t: underflow; use-after-free.
[  439.762326] WARNING: CPU: 12 PID: 177 at ./include/linux/refcount.h:219 lkdtm_REFCOUNT_DEC_AND_TEST_NEGATIVE+0x90/0xa0
[  439.763309] Modules linked in:
[  439.763309] CPU: 12 PID: 177 Comm: bash Tainted: G        W         5.3.0-rc3+ #1
[  439.763309] RIP: 0010:lkdtm_REFCOUNT_DEC_AND_TEST_NEGATIVE+0x90/0xa0
[  439.763309] Code: 3f 2a a9 ff eb d1 80 3d ca a4 f0 00 00 c7 44 24 04 00 00 00 c0 75 c0 48 c7 c7 f8 6a dd 83 c6 05 b2 a4 f0 00 01 e8 00 c5 a3 ff <0f> 0b eb a9 e8 77 c7 a3 ff 0f 1f 80 00 00 00 00 48 83 ec 10 48 c7
[  439.763309] RSP: 0018:ffffb51ec040be48 EFLAGS: 00010282
[  439.763309] RAX: 0000000000000000 RBX: 000000000000002d RCX: ffffffff84049418
[  439.763309] RDX: 0000000000000001 RSI: 0000000000000096 RDI: ffffffff847030ac
[  439.763309] RBP: ffffffff83e5b030 R08: 00000000000ba086 R09: 00000000000001d1
[  439.763309] R10: ffffd77ac120fd00 R11: ffffb51ec040bced R12: ffff9dca883f4000
[  439.763309] R13: 0000000000d86408 R14: 000000000000001f R15: ffffb51ec040bf08
[  439.763309] FS:  00007f7b86147700(0000) GS:ffff9dca8a400000(0000) knlGS:0000000000000000
[  439.763309] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  439.763309] CR2: 0000000000d88ea4 CR3: 00000000482b6003 CR4: 00000000001606a0
[  439.763309] Call Trace:
[  439.763309]  direct_entry+0xc5/0x110
[  439.763309]  full_proxy_write+0x4e/0x70
[  439.763309]  vfs_write+0xab/0x190
[  439.763309]  ksys_write+0x57/0xd0
[  439.763309]  do_syscall_64+0x43/0x110
[  439.763309]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[  439.763309] RIP: 0033:0x7f7b85836970
[  439.763309] Code: 73 01 c3 48 8b 0d 28 d5 2b 00 f7 d8 64 89 01 48 83 c8 ff c3 66 0f 1f 44 00 00 83 3d 99 2d 2c 00 00 75 10 b8 01 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 7e 9b 01 00 48 89 04 24
[  439.763309] RSP: 002b:00007ffc7ad9ae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  439.763309] RAX: ffffffffffffffda RBX: 000000000000001f RCX: 00007f7b85836970
[  439.763309] RDX: 000000000000001f RSI: 0000000000d86408 RDI: 0000000000000001
[  439.763309] RBP: 0000000000d86408 R08: 00007f7b85af6760 R09: 00007f7b86147700
[  439.763309] R10: 0000000000000073 R11: 0000000000000246 R12: 000000000000001f
[  439.763309] R13: 0000000000000001 R14: 00007f7b85af5600 R15: 000000000000001f
[  439.763309] ---[ end trace aedef77d83b518cf ]---
[  439.792308] lkdtm: Negative detected: saturated
[  439.793349] lkdtm: Performing direct entry REFCOUNT_SUB_AND_TEST_NEGATIVE
[  439.794308] lkdtm: attempting bad refcount_sub_and_test() below zero
[  439.795307] lkdtm: Negative detected: saturated
[  439.796344] lkdtm: Performing direct entry REFCOUNT_INC_ZERO
[  439.797307] lkdtm: attempting safe refcount_inc_not_zero() from zero
[  439.798307] lkdtm: Good: zero detected
[  439.798864] lkdtm: Correctly stayed at zero
[  439.799306] lkdtm: attempting bad refcount_inc() from zero
[  439.800307] ------------[ cut here ]------------
[  439.801003] refcount_t: addition on 0; use-after-free.
[  439.801319] WARNING: CPU: 12 PID: 177 at ./include/linux/refcount.h:146 lkdtm_REFCOUNT_INC_ZERO+0x165/0x170
[  439.802303] Modules linked in:
[  439.802303] CPU: 12 PID: 177 Comm: bash Tainted: G        W         5.3.0-rc3+ #1
[  439.802303] RIP: 0010:lkdtm_REFCOUNT_INC_ZERO+0x165/0x170
[  439.802303] Code: 44 24 04 00 00 00 c0 0f 85 46 ff ff ff e8 a3 f5 ff ff e9 3c ff ff ff 48 c7 c7 20 6b dd 83 c6 05 9f a2 f0 00 01 e8 eb c2 a3 ff <0f> 0b eb bd e8 62 c5 a3 ff 66 90 48 83 ec 10 48 c7 c7 c0 c7 e5 83
[  439.802303] RSP: 0018:ffffb51ec040be48 EFLAGS: 00010282
[  439.802303] RAX: 0000000000000000 RBX: 000000000000002f RCX: ffffffff84049418
[  439.802303] RDX: 0000000000000001 RSI: 0000000000000096 RDI: ffffffff847030ac
[  439.802303] RBP: ffffffff83e5b3af R08: 00000000000c38eb R09: 00000000000001fa
[  439.802303] R10: ffffd77ac120fd00 R11: ffffb51ec040bced R12: ffff9dca883f4000
[  439.802303] R13: 0000000000d86408 R14: 0000000000000012 R15: ffffb51ec040bf08
[  439.802303] FS:  00007f7b86147700(0000) GS:ffff9dca8a400000(0000) knlGS:0000000000000000
[  439.802303] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  439.802303] CR2: 0000000000d88ea4 CR3: 00000000482b6003 CR4: 00000000001606a0
[  439.802303] Call Trace:
[  439.802303]  direct_entry+0xc5/0x110
[  439.802303]  full_proxy_write+0x4e/0x70
[  439.802303]  vfs_write+0xab/0x190
[  439.802303]  ksys_write+0x57/0xd0
[  439.802303]  do_syscall_64+0x43/0x110
[  439.802303]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[  439.802303] RIP: 0033:0x7f7b85836970
[  439.802303] Code: 73 01 c3 48 8b 0d 28 d5 2b 00 f7 d8 64 89 01 48 83 c8 ff c3 66 0f 1f 44 00 00 83 3d 99 2d 2c 00 00 75 10 b8 01 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 7e 9b 01 00 48 89 04 24
[  439.802303] RSP: 002b:00007ffc7ad9ae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[  439.802303] RAX: ffffffffffffffda RBX: 0000000000000012 RCX: 00007f7b85836970
[  439.802303] RDX: 0000000000000012 RSI: 0000000000d86408 RDI: 0000000000000001
[  439.802303] RBP: 0000000000d86408 R08: 00007f7b85af6760 R09: 00007f7b86147700
[  439.802303] R10: 0000000000000073 R11: 0000000000000246 R12: 0000000000000012
[  439.802303] R13: 0000000000000001 R14: 00007f7b85af5600 R15: 0000000000000012
[  439.802303] ---[ end trace aedef77d83b518d0 ]---
[  439.831302] lkdtm: Zero detected: saturated
[  439.832344] lkdtm: Performing direct entry REFCOUNT_ADD_ZERO
[  439.833189] lkdtm: attempting safe refcount_add_not_zero() from zero
[  439.833309] lkdtm: Good: zero detected
[  439.834308] lkdtm: Correctly stayed at zero
[  439.835301] lkdtm: attempting bad refcount_add() from zero
[  439.836105] lkdtm: Zero detected: saturated
[  439.836339] lkdtm: Performing direct entry REFCOUNT_INC_SATURATED
[  439.837301] lkdtm: attempting bad refcount_inc() from saturated
[  439.838301] lkdtm: Saturation detected: still saturated
[  439.839338] lkdtm: Performing direct entry REFCOUNT_DEC_SATURATED
[  439.840301] lkdtm: attempting bad refcount_dec() from saturated
[  439.841300] lkdtm: Saturation detected: still saturated
[  439.842093] lkdtm: Performing direct entry REFCOUNT_ADD_SATURATED
[  439.842300] lkdtm: attempting bad refcount_dec() from saturated
[  439.843300] lkdtm: Saturation detected: still saturated
[  439.844337] lkdtm: Performing direct entry REFCOUNT_INC_NOT_ZERO_SATURATED
[  439.845300] lkdtm: attempting bad refcount_inc_not_zero() from saturated
[  439.846299] lkdtm: Saturation detected: still saturated
[  439.847344] lkdtm: Performing direct entry REFCOUNT_ADD_NOT_ZERO_SATURATED
[  439.848306] lkdtm: attempting bad refcount_add_not_zero() from saturated
[  439.849300] lkdtm: Saturation detected: still saturated
[  439.850335] lkdtm: Performing direct entry REFCOUNT_DEC_AND_TEST_SATURATED
[  439.851299] lkdtm: attempting bad refcount_dec_and_test() from saturated
[  439.852299] lkdtm: Saturation detected: still saturated
[  439.853335] lkdtm: Performing direct entry REFCOUNT_SUB_AND_TEST_SATURATED
[  439.854298] lkdtm: attempting bad refcount_sub_and_test() from saturated
[  439.855298] lkdtm: Saturation detected: still saturated
[  439.856333] lkdtm: Performing direct entry REFCOUNT_TIMING
[  471.816139] lkdtm: refcount timing: done

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Kees Cook]

On Wed, Aug 28, 2019 at 03:14:40PM +0100, Will Deacon wrote:
> On Wed, Aug 28, 2019 at 09:30:52AM +0200, Peter Zijlstra wrote:
> > On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> > > Will Deacon (6):
> > >   lib/refcount: Define constants for saturation and max refcount values
> > >   lib/refcount: Ensure integer operands are treated as signed
> > >   lib/refcount: Remove unused refcount_*_checked() variants
> > >   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
> > >   lib/refcount: Improve performance of generic REFCOUNT_FULL code
> > >   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions

BTW, can you repeat the timing details into the "Improve performance of
generic REFCOUNT_FULL code" patch?

> > So I'm not a fan; I itch at the whole racy nature of this thing and I
> > find the code less than obvious. Yet, I have to agree it is exceedingly
> > unlikely the race will ever actually happen, I just don't want to be the
> > one having to debug it.
> 
> FWIW, I think much the same about the version under arch/x86 ;)
> 
> > I've not looked at the implementation much; does it do all the same
> > checks the FULL one does? The x86-asm one misses a few iirc, so if this
> > is similarly fast but has all the checks, it is in fact better.
> 
> Yes, it passes all of the REFCOUNT_* tests in lkdtm [1] so I agree that
> it's an improvement over the asm version.
> 
> > Can't we make this a default !FULL implementation?
> 
> My concern with doing that is I think it would make the FULL implementation
> entirely pointless. I can't see anybody using it, and it would only exist
> as an academic exercise in handling the theoretical races. That's a change
> from the current situation where it genuinely handles cases which the
> x86-specific code does not and, judging by the Kconfig text, that's the
> only reason for its existence.

Looking at timing details, the new implementation is close enough to the
x86 asm version that I would be fine to drop the x86-specific case
entirely as long as we could drop "FULL" entirely too -- we'd have _one_
refcount_t implementation: it would be both complete and fast.

However, I do think a defconfig image size comparison should be done as
part of that too. I think this implementation will be larger than the
x86 asm one (but not by any amount that I think is a problem).

I'd also note that the saturation speed is likely faster in this
implementation (i.e. the number of instructions between noticing the
wrap and setting the saturation value), as it is on the other side of
a branch instead of across a trap, trap handler lookup, and call. So
the race window should even be smaller (though I continue to think it
remains hard enough to hit as to make it a non-issue in all cases: if
you can schedule INT_MAX / 2 increments before a handful of instructions
resets it to INT_MAX / 2, I suspect there are much larger problems. :)

-- 
Kees Cook

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Ard Biesheuvel]

On Thu, 29 Aug 2019 at 00:03, Kees Cook <keescook@chromium.org> wrote:
>
> On Wed, Aug 28, 2019 at 03:14:40PM +0100, Will Deacon wrote:
> > On Wed, Aug 28, 2019 at 09:30:52AM +0200, Peter Zijlstra wrote:
> > > On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> > > > Will Deacon (6):
> > > >   lib/refcount: Define constants for saturation and max refcount values
> > > >   lib/refcount: Ensure integer operands are treated as signed
> > > >   lib/refcount: Remove unused refcount_*_checked() variants
> > > >   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
> > > >   lib/refcount: Improve performance of generic REFCOUNT_FULL code
> > > >   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions
>
> BTW, can you repeat the timing details into the "Improve performance of
> generic REFCOUNT_FULL code" patch?
>
> > > So I'm not a fan; I itch at the whole racy nature of this thing and I
> > > find the code less than obvious. Yet, I have to agree it is exceedingly
> > > unlikely the race will ever actually happen, I just don't want to be the
> > > one having to debug it.
> >
> > FWIW, I think much the same about the version under arch/x86 ;)
> >
> > > I've not looked at the implementation much; does it do all the same
> > > checks the FULL one does? The x86-asm one misses a few iirc, so if this
> > > is similarly fast but has all the checks, it is in fact better.
> >
> > Yes, it passes all of the REFCOUNT_* tests in lkdtm [1] so I agree that
> > it's an improvement over the asm version.
> >
> > > Can't we make this a default !FULL implementation?
> >
> > My concern with doing that is I think it would make the FULL implementation
> > entirely pointless. I can't see anybody using it, and it would only exist
> > as an academic exercise in handling the theoretical races. That's a change
> > from the current situation where it genuinely handles cases which the
> > x86-specific code does not and, judging by the Kconfig text, that's the
> > only reason for its existence.
>
> Looking at timing details, the new implementation is close enough to the
> x86 asm version that I would be fine to drop the x86-specific case
> entirely as long as we could drop "FULL" entirely too -- we'd have _one_
> refcount_t implementation: it would be both complete and fast.
>

+1

> However, I do think a defconfig image size comparison should be done as
> part of that too. I think this implementation will be larger than the
> x86 asm one (but not by any amount that I think is a problem).
>

It's been ~2 years since I looked at this code in detail, but IIRC, it
looked like the inc-from-zero check was missing from the x86
implementation because it requires a load/compare/increment/store
sequence instead of a single increment instruction taking a memory
operand. Was there more rationale at the time for omitting this
particular case, and if so, was it based on a benchmark? Can we run it
against this implementation as well?

> I'd also note that the saturation speed is likely faster in this
> implementation (i.e. the number of instructions between noticing the
> wrap and setting the saturation value), as it is on the other side of
> a branch instead of across a trap, trap handler lookup, and call. So
> the race window should even be smaller (though I continue to think it
> remains hard enough to hit as to make it a non-issue in all cases: if
> you can schedule INT_MAX / 2 increments before a handful of instructions
> resets it to INT_MAX / 2, I suspect there are much larger problems. :)
>
> --
> Kees Cook

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Kees Cook]

On Sat, Aug 31, 2019 at 08:48:56PM +0300, Ard Biesheuvel wrote:
> It's been ~2 years since I looked at this code in detail, but IIRC, it
> looked like the inc-from-zero check was missing from the x86
> implementation because it requires a load/compare/increment/store
> sequence instead of a single increment instruction taking a memory
> operand. Was there more rationale at the time for omitting this
> particular case, and if so, was it based on a benchmark? Can we run it
> against this implementation as well?

It was based on providing a protection against the pre-exploitation case
(overflow: "something bad is about to happen, let's stop it") rather
than the post-exploitation case (inc from zero, "something bad already
happened, eek") with absolutely the fewest possible extra cycles, as
various subsystem maintainers had zero tolerance for any measurable
changes in refcounting performance.

I much prefer the full coverage, even if it's a tiny bit slower. And
based on the worse-case timings (where literally nothing else is
happening) it seems like these changes should be WELL under the noise.

-- 
Kees Cook

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Ard Biesheuvel]

On Sat, 31 Aug 2019 at 22:02, Kees Cook <keescook@chromium.org> wrote:
>
> On Sat, Aug 31, 2019 at 08:48:56PM +0300, Ard Biesheuvel wrote:
> > It's been ~2 years since I looked at this code in detail, but IIRC, it
> > looked like the inc-from-zero check was missing from the x86
> > implementation because it requires a load/compare/increment/store
> > sequence instead of a single increment instruction taking a memory
> > operand. Was there more rationale at the time for omitting this
> > particular case, and if so, was it based on a benchmark? Can we run it
> > against this implementation as well?
>
> It was based on providing a protection against the pre-exploitation case
> (overflow: "something bad is about to happen, let's stop it") rather
> than the post-exploitation case (inc from zero, "something bad already
> happened, eek") with absolutely the fewest possible extra cycles, as
> various subsystem maintainers had zero tolerance for any measurable
> changes in refcounting performance.
>

Ah, of course.

> I much prefer the full coverage, even if it's a tiny bit slower. And
> based on the worse-case timings (where literally nothing else is
> happening) it seems like these changes should be WELL under the noise.
>

 Agreed.

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Will Deacon]

On Wed, Aug 28, 2019 at 02:03:37PM -0700, Kees Cook wrote:
> On Wed, Aug 28, 2019 at 03:14:40PM +0100, Will Deacon wrote:
> > On Wed, Aug 28, 2019 at 09:30:52AM +0200, Peter Zijlstra wrote:
> > > On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
> > > > Will Deacon (6):
> > > >   lib/refcount: Define constants for saturation and max refcount values
> > > >   lib/refcount: Ensure integer operands are treated as signed
> > > >   lib/refcount: Remove unused refcount_*_checked() variants
> > > >   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
> > > >   lib/refcount: Improve performance of generic REFCOUNT_FULL code
> > > >   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions
> 
> BTW, can you repeat the timing details into the "Improve performance of
> generic REFCOUNT_FULL code" patch?

Of course.

> > > So I'm not a fan; I itch at the whole racy nature of this thing and I
> > > find the code less than obvious. Yet, I have to agree it is exceedingly
> > > unlikely the race will ever actually happen, I just don't want to be the
> > > one having to debug it.
> > 
> > FWIW, I think much the same about the version under arch/x86 ;)
> > 
> > > I've not looked at the implementation much; does it do all the same
> > > checks the FULL one does? The x86-asm one misses a few iirc, so if this
> > > is similarly fast but has all the checks, it is in fact better.
> > 
> > Yes, it passes all of the REFCOUNT_* tests in lkdtm [1] so I agree that
> > it's an improvement over the asm version.
> > 
> > > Can't we make this a default !FULL implementation?
> > 
> > My concern with doing that is I think it would make the FULL implementation
> > entirely pointless. I can't see anybody using it, and it would only exist
> > as an academic exercise in handling the theoretical races. That's a change
> > from the current situation where it genuinely handles cases which the
> > x86-specific code does not and, judging by the Kconfig text, that's the
> > only reason for its existence.
> 
> Looking at timing details, the new implementation is close enough to the
> x86 asm version that I would be fine to drop the x86-specific case
> entirely as long as we could drop "FULL" entirely too -- we'd have _one_
> refcount_t implementation: it would be both complete and fast.

That works for me; I'll spin a new version of this series so you can see
what it looks like.

> However, I do think a defconfig image size comparison should be done as
> part of that too. I think this implementation will be larger than the
> x86 asm one (but not by any amount that I think is a problem).

I've managed to get it down to +0.5% when comparing an x86_64 defconfig
before these changes, to one afterwards with REFCOUNT_FULL enabled:

	Total: Before=14762076, After=14835497, chg +0.50%

Will

Re: [PATCH v2 0/6] Rework REFCOUNT_FULL using atomic_fetch_* operations

[Hanjun Guo]

On 2019/9/6 21:43, Will Deacon wrote:
> On Wed, Aug 28, 2019 at 02:03:37PM -0700, Kees Cook wrote:
>> On Wed, Aug 28, 2019 at 03:14:40PM +0100, Will Deacon wrote:
>>> On Wed, Aug 28, 2019 at 09:30:52AM +0200, Peter Zijlstra wrote:
>>>> On Tue, Aug 27, 2019 at 05:31:58PM +0100, Will Deacon wrote:
>>>>> Will Deacon (6):
>>>>>   lib/refcount: Define constants for saturation and max refcount values
>>>>>   lib/refcount: Ensure integer operands are treated as signed
>>>>>   lib/refcount: Remove unused refcount_*_checked() variants
>>>>>   lib/refcount: Move bulk of REFCOUNT_FULL implementation into header
>>>>>   lib/refcount: Improve performance of generic REFCOUNT_FULL code
>>>>>   lib/refcount: Consolidate REFCOUNT_{MAX,SATURATED} definitions
>> BTW, can you repeat the timing details into the "Improve performance of
>> generic REFCOUNT_FULL code" patch?
> Of course.
> 
>>>> So I'm not a fan; I itch at the whole racy nature of this thing and I
>>>> find the code less than obvious. Yet, I have to agree it is exceedingly
>>>> unlikely the race will ever actually happen, I just don't want to be the
>>>> one having to debug it.
>>> FWIW, I think much the same about the version under arch/x86 ;)
>>>
>>>> I've not looked at the implementation much; does it do all the same
>>>> checks the FULL one does? The x86-asm one misses a few iirc, so if this
>>>> is similarly fast but has all the checks, it is in fact better.
>>> Yes, it passes all of the REFCOUNT_* tests in lkdtm [1] so I agree that
>>> it's an improvement over the asm version.
>>>
>>>> Can't we make this a default !FULL implementation?
>>> My concern with doing that is I think it would make the FULL implementation
>>> entirely pointless. I can't see anybody using it, and it would only exist
>>> as an academic exercise in handling the theoretical races. That's a change
>>> from the current situation where it genuinely handles cases which the
>>> x86-specific code does not and, judging by the Kconfig text, that's the
>>> only reason for its existence.
>> Looking at timing details, the new implementation is close enough to the
>> x86 asm version that I would be fine to drop the x86-specific case
>> entirely as long as we could drop "FULL" entirely too -- we'd have _one_
>> refcount_t implementation: it would be both complete and fast.
> That works for me; I'll spin a new version of this series so you can see
> what it looks like.

I will wait for the new version then do the performance test on ARM64 server.

Thanks
Hanjun