[PATCH 1/3] lib/test_kasan: Add bitops tests

[Marco Elver]

This adds bitops tests to the test_kasan module. In a follow-up patch,
support for bitops instrumentation will be added.

Signed-off-by: Marco Elver <el...@google.com>
---
lib/test_kasan.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 70 insertions(+), 3 deletions(-)

diff --git a/lib/test_kasan.c b/lib/test_kasan.c
index 7de2702621dc..f67f3b52251d 100644
--- a/lib/test_kasan.c
+++ b/lib/test_kasan.c
@@ -11,16 +11,17 @@

#define pr_fmt(fmt) "kasan test: %s " fmt, __func__

+#include <linux/bitops.h>
#include <linux/delay.h>
+#include <linux/kasan.h>
#include <linux/kernel.h>
-#include <linux/mman.h>
#include <linux/mm.h>
+#include <linux/mman.h>
+#include <linux/module.h>
#include <linux/printk.h>
#include <linux/slab.h>
#include <linux/string.h>
#include <linux/uaccess.h>
-#include <linux/module.h>
-#include <linux/kasan.h>

/*
* Note: test functions are marked noinline so that their names appear in
@@ -623,6 +624,71 @@ static noinline void __init kasan_strings(void)
strnlen(ptr, 1);
}

+static noinline void __init kasan_bitops(void)
+{
+ long bits = 0;
+ const long bit = sizeof(bits) * 8;
+
+ pr_info("within-bounds in set_bit");
+ set_bit(0, &bits);
+
+ pr_info("within-bounds in set_bit");
+ set_bit(bit - 1, &bits);
+
+ pr_info("out-of-bounds in set_bit\n");
+ set_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __set_bit\n");
+ __set_bit(bit, &bits);
+
+ pr_info("out-of-bounds in clear_bit\n");
+ clear_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __clear_bit\n");
+ __clear_bit(bit, &bits);
+
+ pr_info("out-of-bounds in clear_bit_unlock\n");
+ clear_bit_unlock(bit, &bits);
+
+ pr_info("out-of-bounds in __clear_bit_unlock\n");
+ __clear_bit_unlock(bit, &bits);
+
+ pr_info("out-of-bounds in change_bit\n");
+ change_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __change_bit\n");
+ __change_bit(bit, &bits);
+
+ pr_info("out-of-bounds in test_and_set_bit\n");
+ test_and_set_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __test_and_set_bit\n");
+ __test_and_set_bit(bit, &bits);
+
+ pr_info("out-of-bounds in test_and_set_bit_lock\n");
+ test_and_set_bit_lock(bit, &bits);
+
+ pr_info("out-of-bounds in test_and_clear_bit\n");
+ test_and_clear_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __test_and_clear_bit\n");
+ __test_and_clear_bit(bit, &bits);
+
+ pr_info("out-of-bounds in test_and_change_bit\n");
+ test_and_change_bit(bit, &bits);
+
+ pr_info("out-of-bounds in __test_and_change_bit\n");
+ __test_and_change_bit(bit, &bits);
+
+ pr_info("out-of-bounds in test_bit\n");
+ (void)test_bit(bit, &bits);
+
+#if defined(clear_bit_unlock_is_negative_byte)
+ pr_info("out-of-bounds in clear_bit_unlock_is_negative_byte\n");
+ clear_bit_unlock_is_negative_byte(bit, &bits);
+#endif
+}
+
static int __init kmalloc_tests_init(void)
{
/*
@@ -664,6 +730,7 @@ static int __init kmalloc_tests_init(void)
kasan_memchr();
kasan_memcmp();
kasan_strings();
+ kasan_bitops();

kasan_restore_multi_shot(multishot);

--
2.22.0.rc1.257.g3120a18244-goog

[Marco Elver]

This is a pre-requisite for enabling bitops instrumentation. Some bitops
may safely be used with instrumentation in uaccess regions.

For example, on x86, `test_bit` is used to test a CPU-feature in a
uaccess region: arch/x86/ia32/ia32_signal.c:361

Signed-off-by: Marco Elver <el...@google.com>
---

tools/objtool/check.c | 2 ++
1 file changed, 2 insertions(+)

diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 172f99195726..eff0e5209402 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -443,6 +443,8 @@ static void add_ignores(struct objtool_file *file)
static const char *uaccess_safe_builtin[] = {
/* KASAN */
"kasan_report",
+ "kasan_check_read",
+ "kasan_check_write",
"check_memory_region",
/* KASAN out-of-line */
"__asan_loadN_noabort",
--
2.22.0.rc1.257.g3120a18244-goog

[Marco Elver]

This adds a new header to asm-generic to allow optionally instrumenting
architecture-specific asm implementations of bitops.

This change includes the required change for x86 as reference and
changes the kernel API doc to point to bitops-instrumented.h instead.
Rationale: the functions in x86's bitops.h are no longer the kernel API
functions, but instead the arch_ prefixed functions, which are then
instrumented via bitops-instrumented.h.

Other architectures can similarly add support for asm implementations of
bitops.

The documentation text has been copied/moved, and *no* changes to it
have been made in this patch.

Tested: using lib/test_kasan with bitops tests (pre-requisite patch).

Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=198439

Signed-off-by: Marco Elver <el...@google.com>
---

Documentation/core-api/kernel-api.rst | 2 +-
arch/x86/include/asm/bitops.h | 210 ++++----------
include/asm-generic/bitops-instrumented.h | 327 ++++++++++++++++++++++
3 files changed, 380 insertions(+), 159 deletions(-)
create mode 100644 include/asm-generic/bitops-instrumented.h

diff --git a/Documentation/core-api/kernel-api.rst b/Documentation/core-api/kernel-api.rst
index a29c99d13331..65266fa1b706 100644
--- a/Documentation/core-api/kernel-api.rst
+++ b/Documentation/core-api/kernel-api.rst
@@ -51,7 +51,7 @@ The Linux kernel provides more basic utility functions.
Bit Operations
--------------

-.. kernel-doc:: arch/x86/include/asm/bitops.h
+.. kernel-doc:: include/asm-generic/bitops-instrumented.h
:internal:

Bitmap Operations
diff --git a/arch/x86/include/asm/bitops.h b/arch/x86/include/asm/bitops.h
index 8e790ec219a5..8ebf7af9a0f4 100644
--- a/arch/x86/include/asm/bitops.h
+++ b/arch/x86/include/asm/bitops.h
@@ -49,23 +49,8 @@
#define CONST_MASK_ADDR(nr, addr) WBYTE_ADDR((void *)(addr) + ((nr)>>3))
#define CONST_MASK(nr) (1 << ((nr) & 7))

-/**
- * set_bit - Atomically set a bit in memory
- * @nr: the bit to set
- * @addr: the address to start counting from
- *
- * This function is atomic and may not be reordered. See __set_bit()
- * if you do not require the atomic guarantees.
- *
- * Note: there are no guarantees that this function will not be reordered
- * on non x86 architectures, so if you are writing portable code,
- * make sure not to rely on its reordering guarantees.
- *
- * Note that @nr may be almost arbitrarily large; this function is not
- * restricted to acting on a single-word quantity.
- */
static __always_inline void
-set_bit(long nr, volatile unsigned long *addr)
+arch_set_bit(long nr, volatile unsigned long *addr)
{
if (IS_IMMEDIATE(nr)) {
asm volatile(LOCK_PREFIX "orb %1,%0"
@@ -77,33 +62,17 @@ set_bit(long nr, volatile unsigned long *addr)
: : RLONG_ADDR(addr), "Ir" (nr) : "memory");
}
}
+#define arch_set_bit arch_set_bit

-/**
- * __set_bit - Set a bit in memory
- * @nr: the bit to set
- * @addr: the address to start counting from
- *
- * Unlike set_bit(), this function is non-atomic and may be reordered.
- * If it's called on the same region of memory simultaneously, the effect
- * may be that only one operation succeeds.
- */
-static __always_inline void __set_bit(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch___set_bit(long nr, volatile unsigned long *addr)
{
asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}
+#define arch___set_bit arch___set_bit

-/**
- * clear_bit - Clears a bit in memory
- * @nr: Bit to clear
- * @addr: Address to start counting from
- *
- * clear_bit() is atomic and may not be reordered. However, it does
- * not contain a memory barrier, so if it is used for locking purposes,
- * you should call smp_mb__before_atomic() and/or smp_mb__after_atomic()
- * in order to ensure changes are visible on other processors.
- */
static __always_inline void
-clear_bit(long nr, volatile unsigned long *addr)
+arch_clear_bit(long nr, volatile unsigned long *addr)
{
if (IS_IMMEDIATE(nr)) {
asm volatile(LOCK_PREFIX "andb %1,%0"
@@ -114,27 +83,25 @@ clear_bit(long nr, volatile unsigned long *addr)
: : RLONG_ADDR(addr), "Ir" (nr) : "memory");
}
}
+#define arch_clear_bit arch_clear_bit

-/*
- * clear_bit_unlock - Clears a bit in memory
- * @nr: Bit to clear
- * @addr: Address to start counting from
- *
- * clear_bit() is atomic and implies release semantics before the memory
- * operation. It can be used for an unlock.
- */
-static __always_inline void clear_bit_unlock(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch_clear_bit_unlock(long nr, volatile unsigned long *addr)
{
barrier();
- clear_bit(nr, addr);
+ arch_clear_bit(nr, addr);
}
+#define arch_clear_bit_unlock arch_clear_bit_unlock

-static __always_inline void __clear_bit(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch___clear_bit(long nr, volatile unsigned long *addr)
{
asm volatile(__ASM_SIZE(btr) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}
+#define arch___clear_bit arch___clear_bit

-static __always_inline bool clear_bit_unlock_is_negative_byte(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch_clear_bit_unlock_is_negative_byte(long nr, volatile unsigned long *addr)
{
bool negative;
asm volatile(LOCK_PREFIX "andb %2,%1"
@@ -143,48 +110,25 @@ static __always_inline bool clear_bit_unlock_is_negative_byte(long nr, volatile
: "ir" ((char) ~(1 << nr)) : "memory");
return negative;
}
+#define arch_clear_bit_unlock_is_negative_byte \
+ arch_clear_bit_unlock_is_negative_byte

-// Let everybody know we have it
-#define clear_bit_unlock_is_negative_byte clear_bit_unlock_is_negative_byte
-
-/*
- * __clear_bit_unlock - Clears a bit in memory
- * @nr: Bit to clear
- * @addr: Address to start counting from
- *
- * __clear_bit() is non-atomic and implies release semantics before the memory
- * operation. It can be used for an unlock if no other CPUs can concurrently
- * modify other bits in the word.
- */
-static __always_inline void __clear_bit_unlock(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch___clear_bit_unlock(long nr, volatile unsigned long *addr)
{
- __clear_bit(nr, addr);
+ arch___clear_bit(nr, addr);
}
+#define arch___clear_bit_unlock arch___clear_bit_unlock

-/**
- * __change_bit - Toggle a bit in memory
- * @nr: the bit to change
- * @addr: the address to start counting from
- *
- * Unlike change_bit(), this function is non-atomic and may be reordered.
- * If it's called on the same region of memory simultaneously, the effect
- * may be that only one operation succeeds.
- */
-static __always_inline void __change_bit(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch___change_bit(long nr, volatile unsigned long *addr)
{
asm volatile(__ASM_SIZE(btc) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}
+#define arch___change_bit arch___change_bit

-/**
- * change_bit - Toggle a bit in memory
- * @nr: Bit to change
- * @addr: Address to start counting from
- *
- * change_bit() is atomic and may not be reordered.
- * Note that @nr may be almost arbitrarily large; this function is not
- * restricted to acting on a single-word quantity.
- */
-static __always_inline void change_bit(long nr, volatile unsigned long *addr)
+static __always_inline void
+arch_change_bit(long nr, volatile unsigned long *addr)
{
if (IS_IMMEDIATE(nr)) {
asm volatile(LOCK_PREFIX "xorb %1,%0"
@@ -195,43 +139,24 @@ static __always_inline void change_bit(long nr, volatile unsigned long *addr)
: : RLONG_ADDR(addr), "Ir" (nr) : "memory");
}
}
+#define arch_change_bit arch_change_bit

-/**
- * test_and_set_bit - Set a bit and return its old value
- * @nr: Bit to set
- * @addr: Address to count from
- *
- * This operation is atomic and cannot be reordered.
- * It also implies a memory barrier.
- */
-static __always_inline bool test_and_set_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch_test_and_set_bit(long nr, volatile unsigned long *addr)
{
return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(bts), *addr, c, "Ir", nr);
}
+#define arch_test_and_set_bit arch_test_and_set_bit

-/**
- * test_and_set_bit_lock - Set a bit and return its old value for lock
- * @nr: Bit to set
- * @addr: Address to count from
- *
- * This is the same as test_and_set_bit on x86.
- */
static __always_inline bool
-test_and_set_bit_lock(long nr, volatile unsigned long *addr)
+arch_test_and_set_bit_lock(long nr, volatile unsigned long *addr)
{
- return test_and_set_bit(nr, addr);
+ return arch_test_and_set_bit(nr, addr);
}
+#define arch_test_and_set_bit_lock arch_test_and_set_bit_lock

-/**
- * __test_and_set_bit - Set a bit and return its old value
- * @nr: Bit to set
- * @addr: Address to count from
- *
- * This operation is non-atomic and can be reordered.
- * If two examples of this operation race, one can appear to succeed
- * but actually fail. You must protect multiple accesses with a lock.
- */
-static __always_inline bool __test_and_set_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch___test_and_set_bit(long nr, volatile unsigned long *addr)
{
bool oldbit;

@@ -241,37 +166,17 @@ static __always_inline bool __test_and_set_bit(long nr, volatile unsigned long *
: ADDR, "Ir" (nr) : "memory");
return oldbit;
}
+#define arch___test_and_set_bit arch___test_and_set_bit

-/**
- * test_and_clear_bit - Clear a bit and return its old value
- * @nr: Bit to clear
- * @addr: Address to count from
- *
- * This operation is atomic and cannot be reordered.
- * It also implies a memory barrier.
- */
-static __always_inline bool test_and_clear_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch_test_and_clear_bit(long nr, volatile unsigned long *addr)
{
return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(btr), *addr, c, "Ir", nr);
}
+#define arch_test_and_clear_bit arch_test_and_clear_bit

-/**
- * __test_and_clear_bit - Clear a bit and return its old value
- * @nr: Bit to clear
- * @addr: Address to count from
- *
- * This operation is non-atomic and can be reordered.
- * If two examples of this operation race, one can appear to succeed
- * but actually fail. You must protect multiple accesses with a lock.
- *
- * Note: the operation is performed atomically with respect to
- * the local CPU, but not other CPUs. Portable code should not
- * rely on this behaviour.
- * KVM relies on this behaviour on x86 for modifying memory that is also
- * accessed from a hypervisor on the same CPU if running in a VM: don't change
- * this without also updating arch/x86/kernel/kvm.c
- */
-static __always_inline bool __test_and_clear_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch___test_and_clear_bit(long nr, volatile unsigned long *addr)
{
bool oldbit;

@@ -281,9 +186,10 @@ static __always_inline bool __test_and_clear_bit(long nr, volatile unsigned long
: ADDR, "Ir" (nr) : "memory");
return oldbit;
}
+#define arch___test_and_clear_bit arch___test_and_clear_bit

-/* WARNING: non atomic and it can be reordered! */
-static __always_inline bool __test_and_change_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch___test_and_change_bit(long nr, volatile unsigned long *addr)
{
bool oldbit;

@@ -294,19 +200,14 @@ static __always_inline bool __test_and_change_bit(long nr, volatile unsigned lon

return oldbit;
}
+#define arch___test_and_change_bit arch___test_and_change_bit

-/**
- * test_and_change_bit - Change a bit and return its old value
- * @nr: Bit to change
- * @addr: Address to count from
- *
- * This operation is atomic and cannot be reordered.
- * It also implies a memory barrier.
- */
-static __always_inline bool test_and_change_bit(long nr, volatile unsigned long *addr)
+static __always_inline bool
+arch_test_and_change_bit(long nr, volatile unsigned long *addr)
{
return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(btc), *addr, c, "Ir", nr);
}
+#define arch_test_and_change_bit arch_test_and_change_bit

static __always_inline bool constant_test_bit(long nr, const volatile unsigned long *addr)
{
@@ -326,16 +227,7 @@ static __always_inline bool variable_test_bit(long nr, volatile const unsigned l
return oldbit;
}

-#if 0 /* Fool kernel-doc since it doesn't do macros yet */
-/**
- * test_bit - Determine whether a bit is set
- * @nr: bit number to test
- * @addr: Address to start counting from
- */
-static bool test_bit(int nr, const volatile unsigned long *addr);
-#endif
-
-#define test_bit(nr, addr) \
+#define arch_test_bit(nr, addr) \
(__builtin_constant_p((nr)) \
? constant_test_bit((nr), (addr)) \
: variable_test_bit((nr), (addr)))
@@ -504,6 +396,8 @@ static __always_inline int fls64(__u64 x)

#include <asm-generic/bitops/const_hweight.h>

+#include <asm-generic/bitops-instrumented.h>
+
#include <asm-generic/bitops/le.h>

#include <asm-generic/bitops/ext2-atomic-setbit.h>
diff --git a/include/asm-generic/bitops-instrumented.h b/include/asm-generic/bitops-instrumented.h
new file mode 100644
index 000000000000..52140a5626c3
--- /dev/null
+++ b/include/asm-generic/bitops-instrumented.h
@@ -0,0 +1,327 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+/*
+ * This file provides wrappers with sanitizer instrumentation for bit
+ * operations.
+ *
+ * To use this functionality, an arch's bitops.h file needs to define each of
+ * the below bit operations with an arch_ prefix (e.g. arch_set_bit(),
+ * arch___set_bit(), etc.), #define each provided arch_ function, and include
+ * this file after their definitions. For undefined arch_ functions, it is
+ * assumed that they are provided via asm-generic/bitops, which are implicitly
+ * instrumented.
+ */
+#ifndef _ASM_GENERIC_BITOPS_INSTRUMENTED_H
+#define _ASM_GENERIC_BITOPS_INSTRUMENTED_H
+
+#include <linux/kasan-checks.h>
+
+#if !defined(BITOPS_INSTRUMENT_RANGE)
+/*
+ * This may be defined by an arch's bitops.h, in case bitops do not operate on
+ * single bytes only. The default version here is conservative and assumes that
+ * bitops operate only on the byte with the target bit.
+ */
+#define BITOPS_INSTRUMENT_RANGE(addr, nr) \
+ (const volatile char *)(addr) + ((nr) / BITS_PER_BYTE), 1
+#endif
+
+#if defined(arch_set_bit)
+/**
+ * set_bit - Atomically set a bit in memory
+ * @nr: the bit to set
+ * @addr: the address to start counting from
+ *
+ * This function is atomic and may not be reordered. See __set_bit()
+ * if you do not require the atomic guarantees.
+ *
+ * Note: there are no guarantees that this function will not be reordered
+ * on non x86 architectures, so if you are writing portable code,
+ * make sure not to rely on its reordering guarantees.
+ *
+ * Note that @nr may be almost arbitrarily large; this function is not
+ * restricted to acting on a single-word quantity.
+ */
+static inline void set_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch_set_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___set_bit)
+/**
+ * __set_bit - Set a bit in memory
+ * @nr: the bit to set
+ * @addr: the address to start counting from
+ *
+ * Unlike set_bit(), this function is non-atomic and may be reordered.
+ * If it's called on the same region of memory simultaneously, the effect
+ * may be that only one operation succeeds.
+ */
+static inline void __set_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch___set_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_clear_bit)
+/**
+ * clear_bit - Clears a bit in memory
+ * @nr: Bit to clear
+ * @addr: Address to start counting from
+ *
+ * clear_bit() is atomic and may not be reordered. However, it does
+ * not contain a memory barrier, so if it is used for locking purposes,
+ * you should call smp_mb__before_atomic() and/or smp_mb__after_atomic()
+ * in order to ensure changes are visible on other processors.
+ */
+static inline void clear_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch_clear_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___clear_bit)
+/**
+ * __clear_bit - Clears a bit in memory
+ * @nr: the bit to clear
+ * @addr: the address to start counting from
+ *
+ * Unlike clear_bit(), this function is non-atomic and may be reordered.
+ * If it's called on the same region of memory simultaneously, the effect
+ * may be that only one operation succeeds.
+ */
+static inline void __clear_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch___clear_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_clear_bit_unlock)
+/**
+ * clear_bit_unlock - Clears a bit in memory
+ * @nr: Bit to clear
+ * @addr: Address to start counting from
+ *
+ * clear_bit_unlock() is atomic and implies release semantics before the memory
+ * operation. It can be used for an unlock.
+ */
+static inline void clear_bit_unlock(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch_clear_bit_unlock(nr, addr);
+}
+#endif
+
+#if defined(arch___clear_bit_unlock)
+/**
+ * __clear_bit_unlock - Clears a bit in memory
+ * @nr: Bit to clear
+ * @addr: Address to start counting from
+ *
+ * __clear_bit_unlock() is non-atomic and implies release semantics before the
+ * memory operation. It can be used for an unlock if no other CPUs can
+ * concurrently modify other bits in the word.
+ */
+static inline void __clear_bit_unlock(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch___clear_bit_unlock(nr, addr);
+}
+#endif
+
+#if defined(arch_change_bit)
+/**
+ * change_bit - Toggle a bit in memory
+ * @nr: Bit to change
+ * @addr: Address to start counting from
+ *
+ * change_bit() is atomic and may not be reordered.
+ * Note that @nr may be almost arbitrarily large; this function is not
+ * restricted to acting on a single-word quantity.
+ */
+static inline void change_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch_change_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___change_bit)
+/**
+ * __change_bit - Toggle a bit in memory
+ * @nr: the bit to change
+ * @addr: the address to start counting from
+ *
+ * Unlike change_bit(), this function is non-atomic and may be reordered.
+ * If it's called on the same region of memory simultaneously, the effect
+ * may be that only one operation succeeds.
+ */
+static inline void __change_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ arch___change_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_test_and_set_bit)
+/**
+ * test_and_set_bit - Set a bit and return its old value
+ * @nr: Bit to set
+ * @addr: Address to count from
+ *
+ * This operation is atomic and cannot be reordered.
+ * It also implies a memory barrier.
+ */
+static inline bool test_and_set_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_test_and_set_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___test_and_set_bit)
+/**
+ * __test_and_set_bit - Set a bit and return its old value
+ * @nr: Bit to set
+ * @addr: Address to count from
+ *
+ * This operation is non-atomic and can be reordered.
+ * If two examples of this operation race, one can appear to succeed
+ * but actually fail. You must protect multiple accesses with a lock.
+ */
+static inline bool __test_and_set_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch___test_and_set_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_test_and_set_bit_lock)
+/**
+ * test_and_set_bit_lock - Set a bit and return its old value, for lock
+ * @nr: Bit to set
+ * @addr: Address to count from
+ *
+ * This operation is atomic and provides acquire barrier semantics if
+ * the returned value is 0.
+ * It can be used to implement bit locks.
+ */
+static inline bool test_and_set_bit_lock(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_test_and_set_bit_lock(nr, addr);
+}
+#endif
+
+#if defined(arch_test_and_clear_bit)
+/**
+ * test_and_clear_bit - Clear a bit and return its old value
+ * @nr: Bit to clear
+ * @addr: Address to count from
+ *
+ * This operation is atomic and cannot be reordered.
+ * It also implies a memory barrier.
+ */
+static inline bool test_and_clear_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_test_and_clear_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___test_and_clear_bit)
+/**
+ * __test_and_clear_bit - Clear a bit and return its old value
+ * @nr: Bit to clear
+ * @addr: Address to count from
+ *
+ * This operation is non-atomic and can be reordered.
+ * If two examples of this operation race, one can appear to succeed
+ * but actually fail. You must protect multiple accesses with a lock.
+ *
+ * Note: the operation is performed atomically with respect to
+ * the local CPU, but not other CPUs. Portable code should not
+ * rely on this behaviour.
+ * KVM relies on this behaviour on x86 for modifying memory that is also
+ * accessed from a hypervisor on the same CPU if running in a VM: don't change
+ * this without also updating arch/x86/kernel/kvm.c
+ */
+static inline bool __test_and_clear_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch___test_and_clear_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_test_and_change_bit)
+/**
+ * test_and_change_bit - Change a bit and return its old value
+ * @nr: Bit to change
+ * @addr: Address to count from
+ *
+ * This operation is atomic and cannot be reordered.
+ * It also implies a memory barrier.
+ */
+static inline bool test_and_change_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_test_and_change_bit(nr, addr);
+}
+#endif
+
+#if defined(arch___test_and_change_bit)
+/**
+ * __test_and_change_bit - Change a bit and return its old value
+ * @nr: Bit to change
+ * @addr: Address to count from
+ *
+ * This operation is non-atomic and can be reordered.
+ * If two examples of this operation race, one can appear to succeed
+ * but actually fail. You must protect multiple accesses with a lock.
+ */
+static inline bool __test_and_change_bit(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch___test_and_change_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_test_bit)
+/**
+ * test_bit - Determine whether a bit is set
+ * @nr: bit number to test
+ * @addr: Address to start counting from
+ */
+static inline bool test_bit(long nr, const volatile unsigned long *addr)
+{
+ kasan_check_read(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_test_bit(nr, addr);
+}
+#endif
+
+#if defined(arch_clear_bit_unlock_is_negative_byte)
+/**
+ * clear_bit_unlock_is_negative_byte - Clear a bit in memory and test if bottom
+ * byte is negative, for unlock.
+ * @nr: the bit to clear
+ * @addr: the address to start counting from
+ *
+ * This is a bit of a one-trick-pony for the filemap code, which clears
+ * PG_locked and tests PG_waiters,
+ */
+static inline bool
+clear_bit_unlock_is_negative_byte(long nr, volatile unsigned long *addr)
+{
+ kasan_check_write(BITOPS_INSTRUMENT_RANGE(addr, nr));
+ return arch_clear_bit_unlock_is_negative_byte(nr, addr);
+}
+/* Let everybody know we have it. */
+#define clear_bit_unlock_is_negative_byte clear_bit_unlock_is_negative_byte
+#endif
+
+#endif /* _ASM_GENERIC_BITOPS_INSTRUMENTED_H */
--
2.22.0.rc1.257.g3120a18244-goog

[Mark Rutland]

On Tue, May 28, 2019 at 06:32:58PM +0200, Marco Elver wrote:
> This adds a new header to asm-generic to allow optionally instrumenting
> architecture-specific asm implementations of bitops.
>
> This change includes the required change for x86 as reference and
> changes the kernel API doc to point to bitops-instrumented.h instead.
> Rationale: the functions in x86's bitops.h are no longer the kernel API
> functions, but instead the arch_ prefixed functions, which are then
> instrumented via bitops-instrumented.h.
>
> Other architectures can similarly add support for asm implementations of
> bitops.
>
> The documentation text has been copied/moved, and *no* changes to it
> have been made in this patch.
>
> Tested: using lib/test_kasan with bitops tests (pre-requisite patch).
>
> Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=198439
> Signed-off-by: Marco Elver <el...@google.com>
> ---
> Documentation/core-api/kernel-api.rst | 2 +-
> arch/x86/include/asm/bitops.h | 210 ++++----------
> include/asm-generic/bitops-instrumented.h | 327 ++++++++++++++++++++++
> 3 files changed, 380 insertions(+), 159 deletions(-)
> create mode 100644 include/asm-generic/bitops-instrumented.h

[...]

> +#if !defined(BITOPS_INSTRUMENT_RANGE)
> +/*
> + * This may be defined by an arch's bitops.h, in case bitops do not operate on
> + * single bytes only. The default version here is conservative and assumes that
> + * bitops operate only on the byte with the target bit.
> + */
> +#define BITOPS_INSTRUMENT_RANGE(addr, nr) \
> + (const volatile char *)(addr) + ((nr) / BITS_PER_BYTE), 1
> +#endif

I was under the impression that logically, all the bitops operated on
the entire long the bit happend to be contained in, so checking the
entire long would make more sense to me.

FWIW, arm64's atomic bit ops are all implemented atop of atomic_long_*
functions, which are instrumented, and always checks at the granularity
of a long. I haven't seen splats from that when fuzzing with Syzkaller.

Are you seeing bugs without this?

Thanks,
Mark.

[Mark Rutland]

Hi,

On Tue, May 28, 2019 at 06:32:56PM +0200, Marco Elver wrote:
> +static noinline void __init kasan_bitops(void)
> +{
> + long bits = 0;
> + const long bit = sizeof(bits) * 8;

You can use BITS_PER_LONG here.

Thanks,
Mark.

[Peter Zijlstra]

On Tue, May 28, 2019 at 06:32:57PM +0200, Marco Elver wrote:
> This is a pre-requisite for enabling bitops instrumentation. Some bitops
> may safely be used with instrumentation in uaccess regions.
>
> For example, on x86, `test_bit` is used to test a CPU-feature in a
> uaccess region: arch/x86/ia32/ia32_signal.c:361

That one can easily be moved out of the uaccess region. Any else?

[Dmitry Vyukov]

bitops are not instrumented on x86 at all at the moment, so we have
not seen any splats. What we've seen are assorted crashes caused by
previous silent memory corruptions by incorrect bitops :)

Good point. If arm already does this, I guess we also need to check
whole long's.

[Dmitry Vyukov]

On Tue, May 28, 2019 at 7:19 PM Peter Zijlstra <pet...@infradead.org> wrote:
>
> On Tue, May 28, 2019 at 06:32:57PM +0200, Marco Elver wrote:
> > This is a pre-requisite for enabling bitops instrumentation. Some bitops
> > may safely be used with instrumentation in uaccess regions.
> >
> > For example, on x86, `test_bit` is used to test a CPU-feature in a
> > uaccess region: arch/x86/ia32/ia32_signal.c:361
>
> That one can easily be moved out of the uaccess region. Any else?

Marco, try to update config with "make allyesconfig" and then build
the kernel without this change.

[Marco Elver]

For the default, we decided to err on the conservative side for now,
since it seems that e.g. x86 operates only on the byte the bit is on.
Other architectures that need bitops-instrumented.h may redefine
BITOPS_INSTRUMENT_RANGE.

Let me know what you prefer.

Thanks,
-- Marco

[Marco Elver]

On Wed, 29 May 2019 at 10:55, Dmitry Vyukov <dvy...@google.com> wrote:
>
> On Tue, May 28, 2019 at 7:19 PM Peter Zijlstra <pet...@infradead.org> wrote:
> >
> > On Tue, May 28, 2019 at 06:32:57PM +0200, Marco Elver wrote:
> > > This is a pre-requisite for enabling bitops instrumentation. Some bitops
> > > may safely be used with instrumentation in uaccess regions.
> > >
> > > For example, on x86, `test_bit` is used to test a CPU-feature in a
> > > uaccess region: arch/x86/ia32/ia32_signal.c:361
> >
> > That one can easily be moved out of the uaccess region. Any else?
>
> Marco, try to update config with "make allyesconfig" and then build
> the kernel without this change.
>

Done. The only instance of the uaccess warning is still in
arch/x86/ia32/ia32_signal.c.

Change the patch to move this access instead? Let me know what you prefer.

Thanks,
-- Marco

[Peter Zijlstra]

Yes, I think that might be best. The whitelist should be minimal.

[Peter Zijlstra]

On Wed, May 29, 2019 at 11:20:17AM +0200, Marco Elver wrote:
> For the default, we decided to err on the conservative side for now,
> since it seems that e.g. x86 operates only on the byte the bit is on.

This is not correct, see for instance set_bit():

static __always_inline void

set_bit(long nr, volatile unsigned long *addr)

{
if (IS_IMMEDIATE(nr)) {
asm volatile(LOCK_PREFIX "orb %1,%0"

: CONST_MASK_ADDR(nr, addr)
: "iq" ((u8)CONST_MASK(nr))
: "memory");
} else {
asm volatile(LOCK_PREFIX __ASM_SIZE(bts) " %1,%0"

: : RLONG_ADDR(addr), "Ir" (nr) : "memory");
}
}

That results in:

LOCK BTSQ nr, (addr)

when @nr is not an immediate.

[Marco Elver]

Thanks for the clarification. Given that arm64 already instruments
bitops access to whole words, and x86 may also do so for some bitops,
it seems fine to instrument word-sized accesses by default. Is that
reasonable?

[Peter Zijlstra]

Eminently -- the API is defined such; for bonus points KASAN should also
do alignment checks on atomic ops. Future hardware will #AC on unaligned
[*] LOCK prefix instructions.

(*) not entirely accurate, it will only trap when crossing a line.
https://lkml.kernel.org/r/1556134382-58814-1-git...@intel.com

[Dmitry Vyukov]

Interesting. Does an address passed to bitops also should be aligned,
or alignment is supposed to be handled by bitops themselves?

This probably should be done as a separate config as not related to
KASAN per se. But obviously via the same
{atomicops,bitops}-instrumented.h hooks which will make it
significantly easier.

[David Laight]

From: Dmitry Vyukov
> Sent: 29 May 2019 11:57

The bitops are defined on 'long []' and it is expected to be aligned.
Any code that casts the argument is likely to be broken on big-endian.
I did a quick grep a few weeks ago and found some very dubious code.
Not all the casts seemed to be on code that was LE only (although
I didn't try to find out what the casts were from).

The alignment trap on x86 could be avoided by only ever requesting 32bit
cycles - and assuming the buffer is always 32bit aligned (eg int []).
But on BE passing an 'int []' is just so wrong ....

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

[Andrey Ryabinin]

It should be aligned. This even documented in Documentation/core-api/atomic_ops.rst:

Native atomic bit operations are defined to operate on objects aligned
to the size of an "unsigned long" C data type, and are least of that
size. The endianness of the bits within each "unsigned long" are the
native endianness of the cpu.

> This probably should be done as a separate config as not related to
> KASAN per se. But obviously via the same
> {atomicops,bitops}-instrumented.h hooks which will make it
> significantly easier.
>

Agreed.

[Dmitry Vyukov]

Thanks. I've filed https://bugzilla.kernel.org/show_bug.cgi?id=203751
for checking alignment with all the points and references, so that
it's not lost.

[Peter Zijlstra]

On Wed, May 29, 2019 at 11:20:56AM +0000, David Laight wrote:
> From: Dmitry Vyukov
> > Sent: 29 May 2019 11:57

> > Interesting. Does an address passed to bitops also should be aligned,
> > or alignment is supposed to be handled by bitops themselves?
>
> The bitops are defined on 'long []' and it is expected to be aligned.
> Any code that casts the argument is likely to be broken on big-endian.
> I did a quick grep a few weeks ago and found some very dubious code.
> Not all the casts seemed to be on code that was LE only (although
> I didn't try to find out what the casts were from).
>
> The alignment trap on x86 could be avoided by only ever requesting 32bit
> cycles - and assuming the buffer is always 32bit aligned (eg int []).
> But on BE passing an 'int []' is just so wrong ....

Right, but as argued elsewhere, I feel we should clean up the dubious
code instead of enabling it.

[Peter Zijlstra]

On Wed, May 29, 2019 at 01:29:51PM +0200, Dmitry Vyukov wrote:
> Thanks. I've filed https://bugzilla.kernel.org/show_bug.cgi?id=203751
> for checking alignment with all the points and references, so that
> it's not lost.

Thanks!

[Mark Rutland]

Makes sense to me -- that should be easy to hack into gen_param_check()
in gen-atomic-instrumented.sh, something like:

----
diff --git a/scripts/atomic/gen-atomic-instrumented.sh b/scripts/atomic/gen-atomic-instrumented.sh
index e09812372b17..2f6b8f521e57 100755
--- a/scripts/atomic/gen-atomic-instrumented.sh
+++ b/scripts/atomic/gen-atomic-instrumented.sh
@@ -21,6 +21,13 @@ gen_param_check()
[ ${type#c} != ${type} ] && rw="read"

printf "\tkasan_check_${rw}(${name}, sizeof(*${name}));\n"
+
+ [ "${type#c}" = "v" ] || return
+
+cat <<EOF
+ if (IS_ENABLED(CONFIG_PETERZ))
+ WARN_ON(!IS_ALIGNED(${name}, sizeof(*${name})));
+EOF
}

#gen_param_check(arg...)
----

On arm64 our atomic instructions always perform an alignment check, so
we'd only miss if an atomic op bailed out after a plain READ_ONCE() of
an unaligned atomic variable.

Thanks,
Mark.