Skip to contentSkip to conversation

KFENCE: A low-overhead sampling-based memory safety error detector

PATCH Superseded Marco Elver 6 participants 36 messages Sep 29, 2020 – Oct 12, 2020

Subsystems (13)

v4 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Marco Elver

author maintainer
#0 lore raw

v4 cover KFENCE: A low-overhead sampling-based memory safety error detector

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors. This series enables KFENCE for the x86 and arm64 architectures, and adds KFENCE hooks to the SLAB and SLUB allocators.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

KFENCE objects each reside on a dedicated page, at either the left or right page boundaries. The pages to the left and right of the object page are "guard pages", whose attributes are changed to a protected state, and cause page faults on any attempted access to them. Such page faults are then intercepted by KFENCE, which handles the fault gracefully by reporting a memory access error.

Guarded allocations are set up based on a sample interval (can be set via kfence.sample_interval). After expiration of the sample interval, the next allocation through the main allocator (SLAB or SLUB) returns a guarded allocation from the KFENCE object pool. At this point, the timer is reset, and the next allocation is set up after the expiration of the interval.

To enable/disable a KFENCE allocation through the main allocator's fast-path without overhead, KFENCE relies on static branches via the static keys infrastructure. The static branch is toggled to redirect the allocation to KFENCE.

The KFENCE memory pool is of fixed size, and if the pool is exhausted no further KFENCE allocations occur. The default config is conservative with only 255 objects, resulting in a pool size of 2 MiB (with 4 KiB pages).

We have verified by running synthetic benchmarks (sysbench I/O, hackbench) that a kernel with KFENCE is performance-neutral compared to a non-KFENCE baseline kernel.

KFENCE is inspired by GWP-ASan [1], a userspace tool with similar properties. The name "KFENCE" is a homage to the Electric Fence Malloc Debugger [2].

For more details, see Documentation/dev-tools/kfence.rst added in the series -- also viewable here:

https://raw.githubusercontent.com/google/kasan/kfence/Documentation/dev-tools/kfence.rst

[1] http://llvm.org/docs/GwpAsan.html
[2] https://linux.die.net/man/3/efence

v4:
* MAINTAINERS: Split out from first patch.
* Make static memory pool's attrs entirely arch-dependent.
* Fix report generation if __slab_free tail-called.
* Clarify RCU test comment [reported by Paul E. McKenney].

v3: https://lkml.kernel.org/r/[email protected]
* Rewrite SLAB/SLUB patch descriptions to clarify need for 'orig_size'.
* Various smaller fixes (see details in patches).

v2: https://lkml.kernel.org/r/[email protected]
* Various comment/documentation changes (see details in patches).
* Various smaller fixes (see details in patches).
* Change all reports to reference the kfence object, "kfence-#nn".
* Skip allocation/free internals stack trace.
* Rework KMEMLEAK compatibility patch.

RFC/v1: https://lkml.kernel.org/r/[email protected]

Alexander Potapenko (6):
mm: add Kernel Electric-Fence infrastructure x86, kfence: enable KFENCE for x86
mm, kfence: insert KFENCE hooks for SLAB
mm, kfence: insert KFENCE hooks for SLUB kfence, kasan: make KFENCE compatible with KASAN kfence, kmemleak: make KFENCE compatible with KMEMLEAK

Marco Elver (5):
arm64, kfence: enable KFENCE for ARM64 kfence, lockdep: make KFENCE compatible with lockdep kfence, Documentation: add KFENCE documentation
kfence: add test suite
MAINTAINERS: Add entry for KFENCE

 Documentation/dev-tools/index.rst  |   1 +
 Documentation/dev-tools/kfence.rst | 291 +++++++++++
 MAINTAINERS                        |  11 +
 arch/arm64/Kconfig                 |   1 +
 arch/arm64/include/asm/kfence.h    |  39 ++
 arch/arm64/mm/fault.c              |   4 +
 arch/x86/Kconfig                   |   2 +
 arch/x86/include/asm/kfence.h      |  60 +++
 arch/x86/mm/fault.c                |   4 +
 include/linux/kfence.h             | 174 +++++++
 init/main.c                        |   2 +
 kernel/locking/lockdep.c           |   8 +
 lib/Kconfig.debug                  |   1 +
 lib/Kconfig.kfence                 |  78 +++
 mm/Makefile                        |   1 +
 mm/kasan/common.c                  |   7 +
 mm/kfence/Makefile                 |   6 +
 mm/kfence/core.c                   | 733 +++++++++++++++++++++++++++
 mm/kfence/kfence.h                 | 102 ++++
 mm/kfence/kfence_test.c            | 783 +++++++++++++++++++++++++++++
 mm/kfence/report.c                 | 225 +++++++++
 mm/kmemleak.c                      |   6 +
 mm/slab.c                          |  46 +-
 mm/slab_common.c                   |   6 +-
 mm/slub.c                          |  72 ++-
 25 files changed, 2631 insertions(+), 32 deletions(-)
 create mode 100644 Documentation/dev-tools/kfence.rst
 create mode 100644 arch/arm64/include/asm/kfence.h
 create mode 100644 arch/x86/include/asm/kfence.h
 create mode 100644 include/linux/kfence.h
 create mode 100644 lib/Kconfig.kfence
 create mode 100644 mm/kfence/Makefile
 create mode 100644 mm/kfence/core.c
 create mode 100644 mm/kfence/kfence.h
 create mode 100644 mm/kfence/kfence_test.c
 create mode 100644 mm/kfence/report.c
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#1 lore raw

PATCH v4 1/11 mm: add Kernel Electric-Fence infrastructure

From: Alexander Potapenko <[email protected]>

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

KFENCE objects each reside on a dedicated page, at either the left or right page boundaries. The pages to the left and right of the object page are "guard pages", whose attributes are changed to a protected state, and cause page faults on any attempted access to them. Such page faults are then intercepted by KFENCE, which handles the fault gracefully by reporting a memory access error. To detect out-of-bounds writes to memory within the object's page itself, KFENCE also uses pattern-based redzones. The following figure illustrates the page layout:

---+-----------+-----------+-----------+-----------+-----------+---

     | xxxxxxxxx | O :       | xxxxxxxxx |       : O | xxxxxxxxx |
     | xxxxxxxxx | B :       | xxxxxxxxx |       : B | xxxxxxxxx |
     | x GUARD x | J : RED-  | x GUARD x | RED-  : J | x GUARD x |
     | xxxxxxxxx | E :  ZONE | xxxxxxxxx |  ZONE : E | xxxxxxxxx |
     | xxxxxxxxx | C :       | xxxxxxxxx |       : C | xxxxxxxxx |
     | xxxxxxxxx | T :       | xxxxxxxxx |       : T | xxxxxxxxx |

---+-----------+-----------+-----------+-----------+-----------+---

Guarded allocations are set up based on a sample interval (can be set via kfence.sample_interval). After expiration of the sample interval, a guarded allocation from the KFENCE object pool is returned to the main allocator (SLAB or SLUB). At this point, the timer is reset, and the next allocation is set up after the expiration of the interval.

To enable/disable a KFENCE allocation through the main allocator's fast-path without overhead, KFENCE relies on static branches via the static keys infrastructure. The static branch is toggled to redirect the allocation to KFENCE. To date, we have verified by running synthetic benchmarks (sysbench I/O workloads) that a kernel compiled with KFENCE is performance-neutral compared to the non-KFENCE baseline.

For more details, see Documentation/dev-tools/kfence.rst (added later in the series).

---
v4
* Make static memory pool's attrs entirely arch-dependent.
* Revert MAINTAINERS, and make separate patch.
* Fix report generation if __slab_free tail-called.

v3:
* Reports by SeongJae Park:
* Remove reference to Documentation/dev-tools/kfence.rst.
* Remove redundant braces.
* Use CONFIG_KFENCE_NUM_OBJECTS instead of ARRAY_SIZE(...).
* Align some comments.
* Add figure from Documentation/dev-tools/kfence.rst added later in series to patch description.

v2:
* Add missing __printf attribute to seq_con_printf, and fix new warning. [reported by kernel test robot <[email protected]>]
* Fix up some comments [reported by Jonathan Cameron].
* Remove 2 cases of redundant stack variable initialization [reported by Jonathan Cameron].
* Fix printf format [reported by kernel test robot <[email protected]>].
* Print (in kfence-#nn) after address, to more clearly establish link between first and second stacktrace [reported by Andrey Konovalov].
* Make choice between KASAN and KFENCE clearer in Kconfig help text [suggested by Dave Hansen].
* Document CONFIG_KFENCE_SAMPLE_INTERVAL=0.
* Shorten memory corruption report line length.
* Make /sys/module/kfence/parameters/sample_interval root-writable for all builds (to enable debugging, automatic dynamic tweaking).
* Reports by Dmitry Vyukov:
* Do not store negative size for right-located objects
* Only cache-align addresses of right-located objects.
* Run toggle_allocation_gate() after KFENCE is enabled.
* Add empty line between allocation and free stacks.
* Add comment about SLAB_TYPESAFE_BY_RCU.
* Also skip internals for allocation/free stacks.
* s/KFENCE_FAULT_INJECTION/KFENCE_STRESS_TEST_FAULTS/ as FAULT_INJECTION is already overloaded in different contexts.
* Parenthesis for macro variable.
* Lower max of KFENCE_NUM_OBJECTS config variable.

---
 include/linux/kfence.h | 174 ++++++++++
 init/main.c            |   2 +
 lib/Kconfig.debug      |   1 +
 lib/Kconfig.kfence     |  63 ++++
 mm/Makefile            |   1 +
 mm/kfence/Makefile     |   3 +
 mm/kfence/core.c       | 733 +++++++++++++++++++++++++++++++++++++++++
 mm/kfence/kfence.h     | 102 ++++++
 mm/kfence/report.c     | 225 +++++++++++++
 9 files changed, 1304 insertions(+)
 create mode 100644 include/linux/kfence.h
 create mode 100644 lib/Kconfig.kfence
 create mode 100644 mm/kfence/Makefile
 create mode 100644 mm/kfence/core.c
 create mode 100644 mm/kfence/kfence.h
 create mode 100644 mm/kfence/report.c
include/linux/kfence.h new file +174 -0
new file mode 100644
index 000000000000..8128ba7b5e90
@@ -0,0 +1,174 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef _LINUX_KFENCE_H
+#define _LINUX_KFENCE_H
+
+#include <linux/mm.h>
+#include <linux/percpu.h>
+#include <linux/static_key.h>
+#include <linux/types.h>
+
+#ifdef CONFIG_KFENCE
+
+/*
+ * We allocate an even number of pages, as it simplifies calculations to map
+ * address to metadata indices; effectively, the very first page serves as an
+ * extended guard page, but otherwise has no special purpose.
+ */
+#define KFENCE_POOL_SIZE ((CONFIG_KFENCE_NUM_OBJECTS + 1) * 2 * PAGE_SIZE)
+#ifdef CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL
+extern char __kfence_pool[KFENCE_POOL_SIZE];
+#else
+extern char *__kfence_pool;
+#endif
+
+extern struct static_key_false kfence_allocation_key;
+
+/**
+ * is_kfence_address() - check if an address belongs to KFENCE pool
+ * @addr: address to check
+ *
+ * Return: true or false depending on whether the address is within the KFENCE
+ * object range.
+ *
+ * KFENCE objects live in a separate page range and are not to be intermixed
+ * with regular heap objects (e.g. KFENCE objects must never be added to the
+ * allocator freelists). Failing to do so may and will result in heap
+ * corruptions, therefore is_kfence_address() must be used to check whether
+ * an object requires specific handling.
+ */
+static __always_inline bool is_kfence_address(const void *addr)
+{
+	return unlikely((char *)addr >= __kfence_pool &&
+			(char *)addr < __kfence_pool + KFENCE_POOL_SIZE);
+}
+
+/**
+ * kfence_init() - perform KFENCE initialization at boot time
+ */
+void kfence_init(void);
+
+/**
+ * kfence_shutdown_cache() - handle shutdown_cache() for KFENCE objects
+ * @s: cache being shut down
+ *
+ * Return: true on success, false if any leftover objects persist.
+ *
+ * Before shutting down a cache, one must ensure there are no remaining objects
+ * allocated from it. KFENCE objects are not referenced from the cache, so
+ * kfence_shutdown_cache() takes care of them.
+ */
+bool __must_check kfence_shutdown_cache(struct kmem_cache *s);
+
+/*
+ * Allocate a KFENCE object. Allocators must not call this function directly,
+ * use kfence_alloc() instead.
+ */
+void *__kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags);
+
+/**
+ * kfence_alloc() - allocate a KFENCE object with a low probability
+ * @s:     struct kmem_cache with object requirements
+ * @size:  exact size of the object to allocate (can be less than @s->size
+ *         e.g. for kmalloc caches)
+ * @flags: GFP flags
+ *
+ * Return:
+ * * NULL     - must proceed with allocating as usual,
+ * * non-NULL - pointer to a KFENCE object.
+ *
+ * kfence_alloc() should be inserted into the heap allocation fast path,
+ * allowing it to transparently return KFENCE-allocated objects with a low
+ * probability using a static branch (the probability is controlled by the
+ * kfence.sample_interval boot parameter).
+ */
+static __always_inline void *kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags)
+{
+	return static_branch_unlikely(&kfence_allocation_key) ? __kfence_alloc(s, size, flags) :
+								      NULL;
+}
+
+/**
+ * kfence_ksize() - get actual amount of memory allocated for a KFENCE object
+ * @addr: pointer to a heap object
+ *
+ * Return:
+ * * 0     - not a KFENCE object, must call __ksize() instead,
+ * * non-0 - this many bytes can be accessed without causing a memory error.
+ *
+ * kfence_ksize() returns the number of bytes requested for a KFENCE object at
+ * allocation time. This number may be less than the object size of the
+ * corresponding struct kmem_cache.
+ */
+size_t kfence_ksize(const void *addr);
+
+/**
+ * kfence_object_start() - find the beginning of a KFENCE object
+ * @addr - address within a KFENCE-allocated object
+ *
+ * Return: address of the beginning of the object.
+ *
+ * SL[AU]B-allocated objects are laid out within a page one by one, so it is
+ * easy to calculate the beginning of an object given a pointer inside it and
+ * the object size. The same is not true for KFENCE, which places a single
+ * object at either end of the page. This helper function is used to find the
+ * beginning of a KFENCE-allocated object.
+ */
+void *kfence_object_start(const void *addr);
+
+/*
+ * Release a KFENCE-allocated object to KFENCE pool. Allocators must not call
+ * this function directly, use kfence_free() instead.
+ */
+void __kfence_free(void *addr);
+
+/**
+ * kfence_free() - try to release an arbitrary heap object to KFENCE pool
+ * @addr: object to be freed
+ *
+ * Return:
+ * * false - object doesn't belong to KFENCE pool and was ignored,
+ * * true  - object was released to KFENCE pool.
+ *
+ * Release a KFENCE object and mark it as freed. May be called on any object,
+ * even non-KFENCE objects, to simplify integration of the hooks into the
+ * allocator's free codepath. The allocator must check the return value to
+ * determine if it was a KFENCE object or not.
+ */
+static __always_inline __must_check bool kfence_free(void *addr)
+{
+	if (!is_kfence_address(addr))
+		return false;
+	__kfence_free(addr);
+	return true;
+}
+
+/**
+ * kfence_handle_page_fault() - perform page fault handling for KFENCE pages
+ * @addr: faulting address
+ *
+ * Return:
+ * * false - address outside KFENCE pool,
+ * * true  - page fault handled by KFENCE, no additional handling required.
+ *
+ * A page fault inside KFENCE pool indicates a memory error, such as an
+ * out-of-bounds access, a use-after-free or an invalid memory access. In these
+ * cases KFENCE prints an error message and marks the offending page as
+ * present, so that the kernel can proceed.
+ */
+bool __must_check kfence_handle_page_fault(unsigned long addr);
+
+#else /* CONFIG_KFENCE */
+
+static inline bool is_kfence_address(const void *addr) { return false; }
+static inline void kfence_init(void) { }
+static inline bool __must_check kfence_shutdown_cache(struct kmem_cache *s) { return true; }
+static inline void *kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags) { return NULL; }
+static inline size_t kfence_ksize(const void *addr) { return 0; }
+static inline void *kfence_object_start(const void *addr) { return NULL; }
+static inline bool __must_check kfence_free(void *addr) { return false; }
+static inline bool __must_check kfence_handle_page_fault(unsigned long addr) { return false; }
+
+#endif
+
+#endif /* _LINUX_KFENCE_H */
init/main.c +2 -0
index ae78fb68d231..ec7de9dc1ed8 100644
@@ -39,6 +39,7 @@
 #include <linux/security.h>
 #include <linux/smp.h>
 #include <linux/profile.h>
+#include <linux/kfence.h>
 #include <linux/rcupdate.h>
 #include <linux/moduleparam.h>
 #include <linux/kallsyms.h>
@@ -942,6 +943,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
 	hrtimers_init();
 	softirq_init();
 	timekeeping_init();
+	kfence_init();
 
 	/*
 	 * For best initial stack canary entropy, prepare it after:
lib/Kconfig.debug +1 -0
index e068c3c7189a..d09c6a306532 100644
@@ -880,6 +880,7 @@ config DEBUG_STACKOVERFLOW
 	  If in doubt, say "N".
 
 source "lib/Kconfig.kasan"
+source "lib/Kconfig.kfence"
 
 endmenu # "Memory Debugging"
 
lib/Kconfig.kfence new file +63 -0

63 lines not on this page · raw message

mm/Makefile +1 -0
index d5649f1c12c0..afdf1ae0900b 100644
@@ -81,6 +81,7 @@ obj-$(CONFIG_PAGE_POISONING) += page_poison.o
 obj-$(CONFIG_SLAB) += slab.o
 obj-$(CONFIG_SLUB) += slub.o
 obj-$(CONFIG_KASAN)	+= kasan/
+obj-$(CONFIG_KFENCE) += kfence/
 obj-$(CONFIG_FAILSLAB) += failslab.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o
 obj-$(CONFIG_MEMTEST)		+= memtest.o
mm/kfence/Makefile new file +3 -0
new file mode 100644
index 000000000000..d991e9a349f0
@@ -0,0 +1,3 @@
+# SPDX-License-Identifier: GPL-2.0
+
+obj-$(CONFIG_KFENCE) := core.o report.o
mm/kfence/core.c new file +733 -0

733 lines not on this page · raw message

mm/kfence/kfence.h new file +102 -0

102 lines not on this page · raw message

mm/kfence/report.c new file +225 -0

225 lines not on this page · raw message

Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
#2 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 12 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

Quoted 2 lines

KFENCE objects each reside on a dedicated page, at either the left or right page boundaries.

(modulo slab alignment)

Quoted 8 lines

The pages to the left and right of the object
page are "guard pages", whose attributes are changed to a protected state, and cause page faults on any attempted access to them. Such page faults are then intercepted by KFENCE, which handles the fault gracefully by reporting a memory access error. To detect out-of-bounds writes to memory within the object's page itself, KFENCE also uses pattern-based redzones. The following figure illustrates the page layout:

[...]

Quoted 1 line
include/linux/kfence.h +0 -0

[...]

Quoted 8 lines
include/linux/kfence.h +8 -0
+/**
+ * is_kfence_address() - check if an address belongs to KFENCE pool
+ * @addr: address to check
+ *
+ * Return: true or false depending on whether the address is within the KFENCE
+ * object range.
+ *
+ * KFENCE objects live in a separate page range and are not to be intermixed

include/linux/kfence.h line 44

Quoted 10 lines
include/linux/kfence.h +10 -0
+ * with regular heap objects (e.g. KFENCE objects must never be added to the
+ * allocator freelists). Failing to do so may and will result in heap
+ * corruptions, therefore is_kfence_address() must be used to check whether
+ * an object requires specific handling.
+ */
+static __always_inline bool is_kfence_address(const void *addr)
+{
+       return unlikely((char *)addr >= __kfence_pool &&
+                       (char *)addr < __kfence_pool + KFENCE_POOL_SIZE);
+}

If !CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL, this should probably always return false if __kfence_pool is NULL, right?

[...]

Quoted 1 line
lib/Kconfig.kfence +0 -0

[...]

lib/Kconfig.kfence line 17

Quoted 7 lines
lib/Kconfig.kfence +7 -0
+menuconfig KFENCE
+       bool "KFENCE: low-overhead sampling-based memory safety error detector"
+       depends on HAVE_ARCH_KFENCE && !KASAN && (SLAB || SLUB)
+       depends on JUMP_LABEL # To ensure performance, require jump labels
+       select STACKTRACE
+       help
+         KFENCE is low-overhead sampling-based detector for heap out-of-bounds

nit: "is a"

Quoted 3 lines
lib/Kconfig.kfence +3 -0
+         access, use-after-free, and invalid-free errors. KFENCE is designed
+         to have negligible cost to permit enabling it in production
+         environments.

[...]

Quoted 1 line
mm/kfence/core.c +0 -0

[...]

Quoted 1 line

+module_param_named(sample_interval, kfence_sample_interval, ulong, 0600);

This is a writable module parameter, but if the sample interval was 0 or a very large value, changing this value at runtime won't actually change the effective interval because the work item will never get kicked off again, right?

Should this maybe use module_param_cb() instead, with a "set" callback that not only changes the value, but also schedules the work item?

[...]

Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

If this actually brings a performance win, the proper way to do this would probably be to implement this as generic kernel infrastructure that makes the compiler emit large-offset relocations (either through compiler support or using inline asm statements that move an immediate into a register output and register the location in a special section, kinda like how e.g. static keys work) and patches them at boot time, or something like that - there are other places in the kernel where very hot code uses global pointers that are only ever written once during boot, e.g. the dentry cache of the VFS and the futex hash table. Those are probably far hotter than the kfence code.

While I understand that that goes beyond the scope of this project, it might be something to work on going forward - this kind of special-case logic that turns the kernel data section into heap memory would not be needed if we had that kind of infrastructure.

mm/kfence/core.c line 59

Quoted 4 lines
mm/kfence/core.c +4 -0
+#ifdef CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL
+char __kfence_pool[KFENCE_POOL_SIZE] __kfence_pool_attrs;
+#else
+char *__kfence_pool __read_mostly;

not __ro_after_init ?

Quoted 1 line

+#endif

[...]

Quoted 3 lines
mm/kfence/core.c +3 -0
+/* Freelist with available objects. */
+static struct list_head kfence_freelist = LIST_HEAD_INIT(kfence_freelist);
+static DEFINE_RAW_SPINLOCK(kfence_freelist_lock); /* Lock protecting freelist. */

[...]

mm/kfence/core.c line 78

Quoted 2 lines
mm/kfence/core.c +2 -0
+/* Gates the allocation, ensuring only one succeeds in a given period. */
+static atomic_t allocation_gate = ATOMIC_INIT(1);

I don't think you need to initialize this to anything? toggle_allocation_gate() will set it to zero before enabling the static key, so I don't think anyone will ever see this value.

[...]

mm/kfence/core.c line 194

Quoted 4 lines
mm/kfence/core.c +4 -0
+/* Check canary byte at @addr. */
+static inline bool check_canary_byte(u8 *addr)
+{
+       if (*addr == KFENCE_CANARY_PATTERN(addr))

You could maybe add a likely() hint here if you want.

mm/kfence/core.c line 203

Quoted 9 lines
mm/kfence/core.c +9 -0
+               return true;
+
+       atomic_long_inc(&counters[KFENCE_COUNTER_BUGS]);
+       kfence_report_error((unsigned long)addr, addr_to_metadata((unsigned long)addr),
+                           KFENCE_ERROR_CORRUPTION);
+       return false;
+}
+
+static inline void for_each_canary(const struct kfence_metadata *meta, bool (*fn)(u8 *))

Given how horrendously slow this would be if the compiler decided to disregard the "inline" hint and did an indirect call for every byte, you may want to use __always_inline here.

mm/kfence/core.c line 214

Quoted 11 lines
mm/kfence/core.c +11 -0
+{
+       unsigned long addr;
+
+       lockdep_assert_held(&meta->lock);
+
+       for (addr = ALIGN_DOWN(meta->addr, PAGE_SIZE); addr < meta->addr; addr++) {
+               if (!fn((u8 *)addr))
+                       break;
+       }
+
+       for (addr = meta->addr + meta->size; addr < PAGE_ALIGN(meta->addr); addr++) {

Hmm... if the object is on the left side (meaning meta->addr is page-aligned) and the padding is on the right side, won't PAGE_ALIGN(meta->addr)==meta->addr , and therefore none of the padding will be checked?

Quoted 10 lines
mm/kfence/core.c +10 -0
+               if (!fn((u8 *)addr))
+                       break;
+       }
+}
+
+static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t gfp)
+{
+       struct kfence_metadata *meta = NULL;
+       unsigned long flags;
+       void *addr;

mm/kfence/core.c line 234

Quoted 10 lines
mm/kfence/core.c +10 -0
+
+       /* Try to obtain a free object. */
+       raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+       if (!list_empty(&kfence_freelist)) {
+               meta = list_entry(kfence_freelist.next, struct kfence_metadata, list);
+               list_del_init(&meta->list);
+       }
+       raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+       if (!meta)
+               return NULL;

Should this use pr_warn_once(), or something like that, to inform the user that kfence might be stuck with all allocations used by long-living objects and therefore no longer doing anything?

[...]

Quoted 1 line

+}

[...]

Quoted 11 lines
mm/kfence/core.c +11 -0
+/* === Allocation Gate Timer ================================================ */
+
+/*
+ * Set up delayed work, which will enable and disable the static key. We need to
+ * use a work queue (rather than a simple timer), since enabling and disabling a
+ * static key cannot be done from an interrupt.
+ */
+static struct delayed_work kfence_timer;
+static void toggle_allocation_gate(struct work_struct *work)
+{
+       if (!READ_ONCE(kfence_enabled))

mm/kfence/core.c line 531

Quoted 10 lines
mm/kfence/core.c +10 -0
+               return;
+
+       /* Enable static key, and await allocation to happen. */
+       atomic_set(&allocation_gate, 0);
+       static_branch_enable(&kfence_allocation_key);
+       wait_event(allocation_wait, atomic_read(&allocation_gate) != 0);
+
+       /* Disable static key and reset timer. */
+       static_branch_disable(&kfence_allocation_key);
+       schedule_delayed_work(&kfence_timer, msecs_to_jiffies(kfence_sample_interval));

We end up doing two IPIs to all CPU cores for each kfence allocation because of those static branch calls, right? Might be worth adding a comment to point that out, or something like that. (And if it ends up being a problem in the future, we could probably get away with using some variant that avoids the IPI, but flushes the instruction pipeline if we observe the allocation_gate being nonzero, or something like that. At the cost of not immediately capturing new allocations if the relevant instructions are cached. But the current version is definitely fine for an initial implementation, and for now, you should probably *not* implement what I just described.)

Quoted 8 lines
mm/kfence/core.c +8 -0
+}
+static DECLARE_DELAYED_WORK(kfence_timer, toggle_allocation_gate);
+
+/* === Public interface ===================================================== */
+
+void __init kfence_init(void)
+{
+       /* Setting kfence_sample_interval to 0 on boot disables KFENCE. */

mm/kfence/core.c line 549

Quoted 10 lines
mm/kfence/core.c +10 -0
+       if (!kfence_sample_interval)
+               return;
+
+       if (!kfence_initialize_pool()) {
+               pr_err("%s failed\n", __func__);
+               return;
+       }
+
+       WRITE_ONCE(kfence_enabled, true);
+       schedule_delayed_work(&kfence_timer, 0);

This is schedule_work(&kfence_timer).

[...]

Quoted 1 line

+}

[...]

Quoted 1 line
mm/kfence/kfence.h +0 -0

[...]

Quoted 2 lines
mm/kfence/kfence.h +2 -0
+/* KFENCE metadata per guarded allocation. */
+struct kfence_metadata {

[...]

mm/kfence/kfence.h line 75

Quoted 3 lines
mm/kfence/kfence.h +3 -0
+       /*
+        * In case of an invalid access, the page that was unprotected; we
+        * optimistically only store address.

Is this supposed to say something like "only store one address"?

Quoted 3 lines
mm/kfence/kfence.h +3 -0
+        */
+       unsigned long unprotected_page;
+};

[...]

Quoted 2 lines
mm/kfence/kfence.h +1 -0
+#endif /* MM_KFENCE_KFENCE_H */
mm/kfence/report.c +0 -0

[...]

Quoted 3 lines
mm/kfence/report.c +3 -0
+void kfence_report_error(unsigned long address, const struct kfence_metadata *meta,
+                        enum kfence_error_type type)
+{

[...]

Quoted 3 lines
mm/kfence/report.c +3 -0
+       pr_err("==================================================================\n");
+       /* Print report header. */
+       switch (type) {

[...]

Quoted 8 lines
mm/kfence/report.c +8 -0
+       case KFENCE_ERROR_INVALID_FREE:
+               pr_err("BUG: KFENCE: invalid free in %pS\n\n", (void *)stack_entries[skipnr]);
+               pr_err("Invalid free of 0x" PTR_FMT " (in kfence-#%zd):\n", (void *)address,
+                      object_index);
+               break;
+       }
+
+       /* Print stack trace and object info. */

mm/kfence/report.c line 215

Quoted 10 lines
mm/kfence/report.c +10 -0
+       stack_trace_print(stack_entries + skipnr, num_stack_entries - skipnr, 0);
+
+       if (meta) {
+               pr_err("\n");
+               kfence_print_object(NULL, meta);
+       }
+
+       /* Print report footer. */
+       pr_err("\n");
+       dump_stack_print_info(KERN_DEFAULT);

Shouldn't this be KERN_ERR, to keep the loglevel consistent with the previous messages?

#3 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 12 lines · Jann Horn
Quoted 11 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

[...]

Quoted 19 lines
Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

If this actually brings a performance win, the proper way to do this would probably be to implement this as generic kernel infrastructure that makes the compiler emit large-offset relocations (either through compiler support or using inline asm statements that move an immediate into a register output and register the location in a special section, kinda like how e.g. static keys work) and patches them at boot time, or something like that - there are other places in the kernel where very hot code uses global pointers that are only ever written once during boot, e.g. the dentry cache of the VFS and the futex hash table. Those are probably far hotter than the kfence code.

Quoted 4 lines

While I understand that that goes beyond the scope of this project, it might be something to work on going forward - this kind of special-case logic that turns the kernel data section into heap memory would not be needed if we had that kind of infrastructure.

After thinking about it a bit more, I'm not even convinced that this is a net positive in terms of overall performance - while it allows you to avoid one level of indirection in some parts of kfence, that kfence code by design only runs pretty infrequently. And to enable this indirection avoidance, your x86 arch_kfence_initialize_pool() is shattering potentially unrelated hugepages in the kernel data section, which might increase the TLB pressure (and therefore the number of memory loads that have to fall back to slow page walks) in code that is much hotter than yours.

And if this indirection is a real performance problem, that problem would be many times worse in the VFS and the futex subsystem, so developing a more generic framework for doing this cleanly would be far more important than designing special-case code to allow kfence to do this.

And from what I've seen, a non-trivial chunk of the code in this series, especially the arch/ parts, is only necessary to enable this microoptimization.

Do you have performance numbers or a description of why you believe that this part of kfence is exceptionally performance-sensitive? If not, it might be a good idea to remove this optimization, at least for the initial version of this code. (And even if the optimization is worthwhile, it might be a better idea to go for the generic version immediately.)

reviewer
#4 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 59 lines · Jann Horn
Quoted 12 lines · Jann Horn
Quoted 11 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

[...]

Quoted 19 lines
Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

If this actually brings a performance win, the proper way to do this would probably be to implement this as generic kernel infrastructure that makes the compiler emit large-offset relocations (either through compiler support or using inline asm statements that move an immediate into a register output and register the location in a special section, kinda like how e.g. static keys work) and patches them at boot time, or something like that - there are other places in the kernel where very hot code uses global pointers that are only ever written once during boot, e.g. the dentry cache of the VFS and the futex hash table. Those are probably far hotter than the kfence code.

Quoted 4 lines

While I understand that that goes beyond the scope of this project, it might be something to work on going forward - this kind of special-case logic that turns the kernel data section into heap memory would not be needed if we had that kind of infrastructure.

After thinking about it a bit more, I'm not even convinced that this is a net positive in terms of overall performance - while it allows you to avoid one level of indirection in some parts of kfence, that kfence code by design only runs pretty infrequently. And to enable this indirection avoidance, your x86 arch_kfence_initialize_pool() is shattering potentially unrelated hugepages in the kernel data section, which might increase the TLB pressure (and therefore the number of memory loads that have to fall back to slow page walks) in code that is much hotter than yours.

And if this indirection is a real performance problem, that problem would be many times worse in the VFS and the futex subsystem, so developing a more generic framework for doing this cleanly would be far more important than designing special-case code to allow kfence to do this.

And from what I've seen, a non-trivial chunk of the code in this series, especially the arch/ parts, is only necessary to enable this microoptimization.

Quoted 6 lines

Do you have performance numbers or a description of why you believe that this part of kfence is exceptionally performance-sensitive? If not, it might be a good idea to remove this optimization, at least for the initial version of this code. (And even if the optimization is worthwhile, it might be a better idea to go for the generic version immediately.)

This check is very hot, it happens on every free. For every freed object we need to understand if it belongs to KFENCE or not.

The generic framework for this already exists -- you simply create a global variable ;)
KFENCE needs the range to be covered by struct page's and that's what creates problems for arm64. But I would assume most other users don't need that.

reviewer
#5 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 24 lines · Dmitry Vyukov
Quoted 14 lines · Jann Horn
Quoted 5 lines · Jann Horn
Quoted 4 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

Quoted 7 lines
Quoted 7 lines

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

Quoted 8 lines

[...]

Quoted 7 lines
Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

Quoted 3 lines

KFENCE needs the range to be covered by struct page's and that's what creates problems for arm64. But I would assume most other users don't need that.

I've said this in a few other sub-threads, but the issue being attributed to arm64 is a red herring, and indicates a more fundamental issue that also applies to x86, which will introduce a regression for existing correctly-written code. I don't think that's acceptable for a feature expected to be deployed in production kernels, especially given that the failures are going to be non-deterministic and hard to debug.

The code in question is mostly going to be in drivers, and it's very likely you may not hit it in local testing.

If it is critical to avoid a pointer load here, then we need to either:

* Build some infrastructure for patching constants. The x86 static_call work is vaguely the right shape for this. Then we can place the KFENCE region anywhere (e.g. within the linear/direct map), and potentially dynamically allocate it.

* Go audit usage of {page,phys}_to_virt() to find any va->{page,pa}->va round-trips, and go modify that code to do something else which avoids a round-trip. When I last looked at this it didn't seem viable in general since in many cases the physcial address was the only piece of information which was retained.

I'd be really curious to see how using an immediate compares to loading an __ro_after_init pointer value.

Thanks,
Mark.

#6 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

In reply to Dmitry Vyukov
Quoted 66 lines · Dmitry Vyukov
Quoted 58 lines · Jann Horn
Quoted 12 lines · Jann Horn
Quoted 11 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

[...]

Quoted 19 lines
Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

If this actually brings a performance win, the proper way to do this would probably be to implement this as generic kernel infrastructure that makes the compiler emit large-offset relocations (either through compiler support or using inline asm statements that move an immediate into a register output and register the location in a special section, kinda like how e.g. static keys work) and patches them at boot time, or something like that - there are other places in the kernel where very hot code uses global pointers that are only ever written once during boot, e.g. the dentry cache of the VFS and the futex hash table. Those are probably far hotter than the kfence code.

Quoted 4 lines

While I understand that that goes beyond the scope of this project, it might be something to work on going forward - this kind of special-case logic that turns the kernel data section into heap memory would not be needed if we had that kind of infrastructure.

After thinking about it a bit more, I'm not even convinced that this is a net positive in terms of overall performance - while it allows you to avoid one level of indirection in some parts of kfence, that kfence code by design only runs pretty infrequently. And to enable this indirection avoidance, your x86 arch_kfence_initialize_pool() is shattering potentially unrelated hugepages in the kernel data section, which might increase the TLB pressure (and therefore the number of memory loads that have to fall back to slow page walks) in code that is much hotter than yours.

And if this indirection is a real performance problem, that problem would be many times worse in the VFS and the futex subsystem, so developing a more generic framework for doing this cleanly would be far more important than designing special-case code to allow kfence to do this.

And from what I've seen, a non-trivial chunk of the code in this series, especially the arch/ parts, is only necessary to enable this microoptimization.

Quoted 6 lines

Do you have performance numbers or a description of why you believe that this part of kfence is exceptionally performance-sensitive? If not, it might be a good idea to remove this optimization, at least for the initial version of this code. (And even if the optimization is worthwhile, it might be a better idea to go for the generic version immediately.)

Quoted 2 lines

This check is very hot, it happens on every free. For every freed object we need to understand if it belongs to KFENCE or not.

Ah, so the path you care about does not dereference __kfence_pool, it just compares it to the supplied pointer?

First off: The way you've written is_kfence_address(), GCC 10.2 at -O3 seems to generate *utterly* *terrible* code (and the newest clang release isn't any better); something like this:

kfree_inefficient:
mov rax, QWORD PTR __kfence_pool[rip]
cmp rax, rdi
jbe .L4
.L2:
jmp kfree_not_kfence
.L4:
add rax, 0x200000
cmp rax, rdi
jbe .L2
jmp kfree_kfence

So pointers to the left of the region and pointers to the right of the region will take different branches, and so if you have a mix of objects on both sides of the kfence region, you'll get tons of branch mispredictions for no good reason. You'll want to rewrite that check as "unlikely(ptr - base <= SIZE)" instead of "unlikely(ptr >= base && ptr < base + SIZE" unless you know that all the objects will be on one side. This would also reduce the performance impact of loading __kfence_pool from the data section, because the branch prediction can then speculate the branch that depends on the load properly and doesn't have to go roll back everything that happened when the object turns out to be on the opposite side of the kfence memory region - the latency of the load will hopefully become almost irrelevant.

So in x86 intel assembly (assuming that we want to ensure that we only do a single branch on the object type), the straightforward and non-terrible version would be:

kfree_unoptimized:
mov rax, rdi
sub rax, QWORD PTR __kfence_pool[rip]
cmp rax, 0x200000
jbe 1f
/* non-kfence case goes here */
1:
/* kfence case goes here */

while the version you want is:

kfree_static:
mov rax, rdi
sub rax, OFFSET FLAT:__kfence_pool
cmp rax, 0x200000
jbe 1f
jmp kfree_not_kfence
1:
jmp kfree_kfence

If we instead use something like

#define STATIC_VARIABLE_LOAD(variable) \
({ \
typeof(variable) value; \
BUILD_BUG_ON(sizeof(variable) != sizeof(unsigned long)); \

  asm( \
    ".pushsection .static_variable_users\n\t" \
    ".long "  #variable " - .\n\t" \
    ".long 123f - .\n\t" /* offset to end of constant */ \
    ".popsection\n\t" \
    "movabs $0x0123456789abcdef, %0" \
    "123:\n\t" \
    :"=r"(value) \

); \
value; \
})
static __always_inline bool is_kfence_address(const void *addr) {
return unlikely((char*)addr - STATIC_VARIABLE_LOAD(__kfence_pool) <
KFENCE_POOL_SIZE);
}

to locate the pool (which could again be normally allocated with alloc_pages()), we'd get code like this, which is like the previous except that we need an extra "movabs" because x86's "sub" can only use immediates up to 32 bits:

kfree_hotpatchable_bigreloc:
mov rax, rdi
movabs rdx, 0x0123456789abcdef
sub rax, rdx
cmp rax, 0x200000
jbe .1f
jmp kfree_not_kfence
1:
jmp kfree_kfence

The arch-specific part of this could probably be packaged up pretty nicely into a generic interface. If it actually turns out to have a performance benefit, that is.

If that one extra "movabs" is actually a problem, it would *theoretically* be possible to get rid of that by using module_alloc() to allocate virtual memory to which offsets from kernel text are 32 bits, and using special-cased inline asm, but we probably shouldn't do that, because as Mark pointed out, we'd then risk getting extremely infrequent extra bugs when drivers use phys_to_virt() on allocations that were done through kfence. Adding new, extremely infrequent and sporadically occurring bugs to the kernel seems like the exact opposite of the goal of KFENCE. :P

Overall my expectation would be that the MOVABS version should probably at worst be something like one cycle slower - it adds 5 instruction bytes (and we pay 1 cycle in the frontend per 16 bytes of instructions, I think?) and 1 backend cycle (for the MOVABS - Agner Fog's tables seem to say that at least on Skylake, MOVABS is 1 cycle). But that backend cycle shouldn't even be on the critical path (and it has a wider choice of ports than e.g. a load, and I think typical kernel code isn't exactly highly parallelizable, so we can probably schedule on a port that would've been free otherwise?), and I think typical kernel code should be fairly light on the backend, so with the MOVABS version, compared to the version with __kfence_pool in the data section, we probably overall just pay a fraction of a cycle in execution cost? I'm not a professional performance engineer, but this sounds to me like the MOVABS version should probably perform roughly as well as your version.

Anyway, I guess this is all pretty vague without actually having concrete benchmark results. :P

See <https://godbolt.org/z/Kev9dc> for examples of actual code generation for different options of writing this check.

Quoted 2 lines

The generic framework for this already exists -- you simply create a global variable ;)

Yeah, except for all the arch-specific bits you then need to twiddle with because nobody expects heap memory inside the data section...

Quoted 3 lines

KFENCE needs the range to be covered by struct page's and that's what creates problems for arm64. But I would assume most other users don't need that.

Things like the big VFS dentry cache and the futex hashtable have their size chosen at boot time, so they also can't be placed in the data/bss section.

author maintainer
#7 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

On Fri, 2 Oct 2020 at 20:28, Jann Horn <[email protected]> wrote:
[...]

Quoted 31 lines
Quoted 10 lines
Quoted 7 lines

Do you have performance numbers or a description of why you believe that this part of kfence is exceptionally performance-sensitive? If not, it might be a good idea to remove this optimization, at least for the initial version of this code. (And even if the optimization is worthwhile, it might be a better idea to go for the generic version immediately.)

This check is very hot, it happens on every free. For every freed object we need to understand if it belongs to KFENCE or not.

Ah, so the path you care about does not dereference __kfence_pool, it just compares it to the supplied pointer?

First off: The way you've written is_kfence_address(), GCC 10.2 at -O3 seems to generate *utterly* *terrible* code (and the newest clang release isn't any better); something like this:

kfree_inefficient:
mov rax, QWORD PTR __kfence_pool[rip]
cmp rax, rdi
jbe .L4
.L2:
jmp kfree_not_kfence
.L4:
add rax, 0x200000
cmp rax, rdi
jbe .L2
jmp kfree_kfence

Quoted 12 lines

So pointers to the left of the region and pointers to the right of the region will take different branches, and so if you have a mix of objects on both sides of the kfence region, you'll get tons of branch mispredictions for no good reason. You'll want to rewrite that check as "unlikely(ptr - base <= SIZE)" instead of "unlikely(ptr >= base && ptr < base + SIZE" unless you know that all the objects will be on one side. This would also reduce the performance impact of loading __kfence_pool from the data section, because the branch prediction can then speculate the branch that depends on the load properly and doesn't have to go roll back everything that happened when the object turns out to be on the opposite side of the kfence memory region - the latency of the load will hopefully become almost irrelevant.

Good point, implemented that. (It's "ptr - base < SIZE" I take it.)

Quoted 66 lines

So in x86 intel assembly (assuming that we want to ensure that we only do a single branch on the object type), the straightforward and non-terrible version would be:

kfree_unoptimized:
mov rax, rdi
sub rax, QWORD PTR __kfence_pool[rip]
cmp rax, 0x200000
jbe 1f
/* non-kfence case goes here */
1:
/* kfence case goes here */

while the version you want is:

kfree_static:
mov rax, rdi
sub rax, OFFSET FLAT:__kfence_pool
cmp rax, 0x200000
jbe 1f
jmp kfree_not_kfence
1:
jmp kfree_kfence

If we instead use something like

#define STATIC_VARIABLE_LOAD(variable) \
({ \
typeof(variable) value; \
BUILD_BUG_ON(sizeof(variable) != sizeof(unsigned long)); \

  asm( \
    ".pushsection .static_variable_users\n\t" \
    ".long "  #variable " - .\n\t" \
    ".long 123f - .\n\t" /* offset to end of constant */ \
    ".popsection\n\t" \
    "movabs $0x0123456789abcdef, %0" \
    "123:\n\t" \
    :"=r"(value) \

); \
value; \
})
static __always_inline bool is_kfence_address(const void *addr) {
return unlikely((char*)addr - STATIC_VARIABLE_LOAD(__kfence_pool) <
KFENCE_POOL_SIZE);
}

to locate the pool (which could again be normally allocated with alloc_pages()), we'd get code like this, which is like the previous except that we need an extra "movabs" because x86's "sub" can only use immediates up to 32 bits:

kfree_hotpatchable_bigreloc:
mov rax, rdi
movabs rdx, 0x0123456789abcdef
sub rax, rdx
cmp rax, 0x200000
jbe .1f
jmp kfree_not_kfence
1:
jmp kfree_kfence

Quoted 3 lines

The arch-specific part of this could probably be packaged up pretty nicely into a generic interface. If it actually turns out to have a performance benefit, that is.

Something like this would certainly be nice, but we'll do the due diligence and see if it's even worth it.

Quoted 26 lines

If that one extra "movabs" is actually a problem, it would *theoretically* be possible to get rid of that by using module_alloc() to allocate virtual memory to which offsets from kernel text are 32 bits, and using special-cased inline asm, but we probably shouldn't do that, because as Mark pointed out, we'd then risk getting extremely infrequent extra bugs when drivers use phys_to_virt() on allocations that were done through kfence. Adding new, extremely infrequent and sporadically occurring bugs to the kernel seems like the exact opposite of the goal of KFENCE. :P

Overall my expectation would be that the MOVABS version should probably at worst be something like one cycle slower - it adds 5 instruction bytes (and we pay 1 cycle in the frontend per 16 bytes of instructions, I think?) and 1 backend cycle (for the MOVABS - Agner Fog's tables seem to say that at least on Skylake, MOVABS is 1 cycle). But that backend cycle shouldn't even be on the critical path (and it has a wider choice of ports than e.g. a load, and I think typical kernel code isn't exactly highly parallelizable, so we can probably schedule on a port that would've been free otherwise?), and I think typical kernel code should be fairly light on the backend, so with the MOVABS version, compared to the version with __kfence_pool in the data section, we probably overall just pay a fraction of a cycle in execution cost? I'm not a professional performance engineer, but this sounds to me like the MOVABS version should probably perform roughly as well as your version.

Quoted 5 lines

Anyway, I guess this is all pretty vague without actually having concrete benchmark results. :P

See <https://godbolt.org/z/Kev9dc> for examples of actual code generation for different options of writing this check.

Thanks for the analysis! There is also some (11 year old) prior art, that seems to never have made it into the kernel:
https://lore.kernel.org/lkml/[email protected]/

Maybe we need to understand why that never made it.

But I think, even if we drop the static pool, a first version of KFENCE should not depend on it.

Thanks,
-- Marco

author maintainer
#8 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

In reply to Jann Horn

Hi Jann,

Thanks for your comments!!

Quoted 13 lines · Jann Horn
Quoted 12 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

Quoted 4 lines
Quoted 2 lines

KFENCE objects each reside on a dedicated page, at either the left or right page boundaries.

(modulo slab alignment)

There are a bunch more details missing; this is just a high-level summary. Because as soon as we mention "modulo slab alignment" one may wonder about missed OOBs, which we solve with redzones. We should not replicate Documentation/dev-tools/kfence.rst; we do refer to it instead. ;-)

Quoted 24 lines
Quoted 8 lines

The pages to the left and right of the object
page are "guard pages", whose attributes are changed to a protected state, and cause page faults on any attempted access to them. Such page faults are then intercepted by KFENCE, which handles the fault gracefully by reporting a memory access error. To detect out-of-bounds writes to memory within the object's page itself, KFENCE also uses pattern-based redzones. The following figure illustrates the page layout:

[...]

Quoted 1 line
include/linux/kfence.h +0 -0

[...]

Quoted 13 lines

+/**
+ * is_kfence_address() - check if an address belongs to KFENCE pool
+ * @addr: address to check
+ *
+ * Return: true or false depending on whether the address is within the KFENCE
+ * object range.
+ *
+ * KFENCE objects live in a separate page range and are not to be intermixed
+ * with regular heap objects (e.g. KFENCE objects must never be added to the
+ * allocator freelists). Failing to do so may and will result in heap
+ * corruptions, therefore is_kfence_address() must be used to check whether
+ * an object requires specific handling.
+ */

Quoted 8 lines

include/linux/kfence.h line 44

Quoted 5 lines
include/linux/kfence.h +5 -0
+static __always_inline bool is_kfence_address(const void *addr)
+{
+       return unlikely((char *)addr >= __kfence_pool &&
+                       (char *)addr < __kfence_pool + KFENCE_POOL_SIZE);
+}

If !CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL, this should probably always return false if __kfence_pool is NULL, right?

That's another check; we don't want to make this more expensive.

This should never receive a NULL, given the places it's used from, which should only be allocator internals where we already know we have a non-NULL object. If it did receive a NULL, I think something else is wrong. Or did we miss a place where it can legally receive a NULL?

Quoted 11 lines

[...]

Quoted 1 line
lib/Kconfig.kfence +0 -0

[...]

lib/Kconfig.kfence line 17

Quoted 7 lines
lib/Kconfig.kfence +7 -0
+menuconfig KFENCE
+       bool "KFENCE: low-overhead sampling-based memory safety error detector"
+       depends on HAVE_ARCH_KFENCE && !KASAN && (SLAB || SLUB)
+       depends on JUMP_LABEL # To ensure performance, require jump labels
+       select STACKTRACE
+       help
+         KFENCE is low-overhead sampling-based detector for heap out-of-bounds
Quoted 1 line

nit: "is a"

Done.

Quoted 4 lines
Quoted 3 lines
lib/Kconfig.kfence +3 -0
+         access, use-after-free, and invalid-free errors. KFENCE is designed
+         to have negligible cost to permit enabling it in production
+         environments.

[...]

Quoted 8 lines
Quoted 1 line
mm/kfence/core.c +0 -0

[...]

Quoted 1 line

+module_param_named(sample_interval, kfence_sample_interval, ulong, 0600);

This is a writable module parameter, but if the sample interval was 0 or a very large value, changing this value at runtime won't actually change the effective interval because the work item will never get kicked off again, right?

When KFENCE has been enabled, setting this to 0 actually reschedules the work immediately; we do not disable KFENCE once it has been enabled.

Conversely, if KFENCE has been disabled at boot (this param is 0), changing this to anything else will not enable KFENCE.

This simplifies a lot of things, in particular, if KFENCE was disabled we do not want to run initialization code and also do not want to kick off KFENCE initialization code were we to allow dynamically turning KFENCE on/off (it complicates a bunch of things, e.g. the various arch-specific initialization would need to be able to deal with all this).

Quoted 2 lines

Should this maybe use module_param_cb() instead, with a "set" callback that not only changes the value, but also schedules the work item?

Whether or not we want to reschedule the work if the value was changed from a huge value to a smaller one is another question. Probably... we'll consider it.

Quoted 25 lines

[...]

Quoted 7 lines

+/*
+ * The pool of pages used for guard pages and objects. If supported, allocated
+ * statically, so that is_kfence_address() avoids a pointer load, and simply
+ * compares against a constant address. Assume that if KFENCE is compiled into
+ * the kernel, it is usually enabled, and the space is to be allocated one way
+ * or another.
+ */

If this actually brings a performance win, the proper way to do this would probably be to implement this as generic kernel infrastructure that makes the compiler emit large-offset relocations (either through compiler support or using inline asm statements that move an immediate into a register output and register the location in a special section, kinda like how e.g. static keys work) and patches them at boot time, or something like that - there are other places in the kernel where very hot code uses global pointers that are only ever written once during boot, e.g. the dentry cache of the VFS and the futex hash table. Those are probably far hotter than the kfence code.

While I understand that that goes beyond the scope of this project, it might be something to work on going forward - this kind of special-case logic that turns the kernel data section into heap memory would not be needed if we had that kind of infrastructure.

Quoted 6 lines

mm/kfence/core.c line 59

Quoted 4 lines
mm/kfence/core.c +4 -0
+#ifdef CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL
+char __kfence_pool[KFENCE_POOL_SIZE] __kfence_pool_attrs;
+#else
+char *__kfence_pool __read_mostly;

not __ro_after_init ?

Changed, thanks.

Quoted 6 lines
Quoted 1 line

+#endif

[...]

Quoted 3 lines
mm/kfence/core.c +3 -0
+/* Freelist with available objects. */
+static struct list_head kfence_freelist = LIST_HEAD_INIT(kfence_freelist);
+static DEFINE_RAW_SPINLOCK(kfence_freelist_lock); /* Lock protecting freelist. */

[...]

Quoted 6 lines

mm/kfence/core.c line 78

Quoted 2 lines
mm/kfence/core.c +2 -0
+/* Gates the allocation, ensuring only one succeeds in a given period. */
+static atomic_t allocation_gate = ATOMIC_INIT(1);

I don't think you need to initialize this to anything? toggle_allocation_gate() will set it to zero before enabling the static key, so I don't think anyone will ever see this value.

Sure. But does it hurt anyone? At least this way we don't need to think about yet another state that only exists on initialization; who knows what we'll change in future.

Quoted 7 lines

[...]

mm/kfence/core.c line 194

Quoted 4 lines
mm/kfence/core.c +4 -0
+/* Check canary byte at @addr. */
+static inline bool check_canary_byte(u8 *addr)
+{
+       if (*addr == KFENCE_CANARY_PATTERN(addr))

You could maybe add a likely() hint here if you want.

Added; but none of this is in a hot path.

Quoted 5 lines
Quoted 5 lines
mm/kfence/core.c +5 -0
+               return true;
+
+       atomic_long_inc(&counters[KFENCE_COUNTER_BUGS]);
+       kfence_report_error((unsigned long)addr, addr_to_metadata((unsigned long)addr),
+                           KFENCE_ERROR_CORRUPTION);
Quoted 8 lines

mm/kfence/core.c line 203

Quoted 4 lines
mm/kfence/core.c +4 -0
+       return false;
+}
+
+static inline void for_each_canary(const struct kfence_metadata *meta, bool (*fn)(u8 *))

Given how horrendously slow this would be if the compiler decided to disregard the "inline" hint and did an indirect call for every byte, you may want to use __always_inline here.

Done.

Quoted 8 lines
Quoted 8 lines
mm/kfence/core.c +8 -0
+{
+       unsigned long addr;
+
+       lockdep_assert_held(&meta->lock);
+
+       for (addr = ALIGN_DOWN(meta->addr, PAGE_SIZE); addr < meta->addr; addr++) {
+               if (!fn((u8 *)addr))
+                       break;
Quoted 8 lines

mm/kfence/core.c line 214

Quoted 3 lines
mm/kfence/core.c +3 -0
+       }
+
+       for (addr = meta->addr + meta->size; addr < PAGE_ALIGN(meta->addr); addr++) {

Hmm... if the object is on the left side (meaning meta->addr is page-aligned) and the padding is on the right side, won't PAGE_ALIGN(meta->addr)==meta->addr , and therefore none of the padding will be checked?

No, you're thinking of ALIGN_DOWN. PAGE_ALIGN gives us the next page.

Quoted 16 lines
Quoted 16 lines
mm/kfence/core.c +16 -0
+               if (!fn((u8 *)addr))
+                       break;
+       }
+}
+
+static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t gfp)
+{
+       struct kfence_metadata *meta = NULL;
+       unsigned long flags;
+       void *addr;
+
+       /* Try to obtain a free object. */
+       raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+       if (!list_empty(&kfence_freelist)) {
+               meta = list_entry(kfence_freelist.next, struct kfence_metadata, list);
+               list_del_init(&meta->list);
Quoted 8 lines

mm/kfence/core.c line 234

Quoted 4 lines
mm/kfence/core.c +4 -0
+       }
+       raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+       if (!meta)
+               return NULL;

Should this use pr_warn_once(), or something like that, to inform the user that kfence might be stuck with all allocations used by long-living objects and therefore no longer doing anything?

I don't think so; it might as well recover, and seeing this message once is no indication that we're stuck. Instead, we should (and plan to) monitor /sys/kernel/debug/kfence/stats.

Quoted 27 lines

[...]

Quoted 1 line

+}

[...]

Quoted 11 lines
mm/kfence/core.c +11 -0
+/* === Allocation Gate Timer ================================================ */
+
+/*
+ * Set up delayed work, which will enable and disable the static key. We need to
+ * use a work queue (rather than a simple timer), since enabling and disabling a
+ * static key cannot be done from an interrupt.
+ */
+static struct delayed_work kfence_timer;
+static void toggle_allocation_gate(struct work_struct *work)
+{
+       if (!READ_ONCE(kfence_enabled))

mm/kfence/core.c line 531

Quoted 10 lines
mm/kfence/core.c +10 -0
+               return;
+
+       /* Enable static key, and await allocation to happen. */
+       atomic_set(&allocation_gate, 0);
+       static_branch_enable(&kfence_allocation_key);
+       wait_event(allocation_wait, atomic_read(&allocation_gate) != 0);
+
+       /* Disable static key and reset timer. */
+       static_branch_disable(&kfence_allocation_key);
+       schedule_delayed_work(&kfence_timer, msecs_to_jiffies(kfence_sample_interval));

We end up doing two IPIs to all CPU cores for each kfence allocation because of those static branch calls, right? Might be worth adding a

Quoted 8 lines

comment to point that out, or something like that. (And if it ends up being a problem in the future, we could probably get away with using some variant that avoids the IPI, but flushes the instruction pipeline if we observe the allocation_gate being nonzero, or something like that. At the cost of not immediately capturing new allocations if the relevant instructions are cached. But the current version is definitely fine for an initial implementation, and for now, you should probably *not* implement what I just described.)

Thanks, yeah, this is a good point, and I wondered if we could optimize this along these lines. We'll add a comment. Maybe somebody wants to optimize this in future. :-)

Quoted 12 lines
Quoted 12 lines
mm/kfence/core.c +12 -0
+}
+static DECLARE_DELAYED_WORK(kfence_timer, toggle_allocation_gate);
+
+/* === Public interface ===================================================== */
+
+void __init kfence_init(void)
+{
+       /* Setting kfence_sample_interval to 0 on boot disables KFENCE. */
+       if (!kfence_sample_interval)
+               return;
+
+       if (!kfence_initialize_pool()) {
Quoted 8 lines

mm/kfence/core.c line 549

Quoted 6 lines
mm/kfence/core.c +6 -0
+               pr_err("%s failed\n", __func__);
+               return;
+       }
+
+       WRITE_ONCE(kfence_enabled, true);
+       schedule_delayed_work(&kfence_timer, 0);

This is schedule_work(&kfence_timer).

No, schedule_work() is not generic and does not take a struct delayed_work.

Quoted 5 lines

[...]

Quoted 1 line

+}

[...]

Quoted 1 line
mm/kfence/kfence.h +0 -0

[...]

Quoted 8 lines
Quoted 2 lines
mm/kfence/kfence.h +2 -0
+/* KFENCE metadata per guarded allocation. */
+struct kfence_metadata {

[...]

mm/kfence/kfence.h line 75

Quoted 3 lines
mm/kfence/kfence.h +3 -0
+       /*
+        * In case of an invalid access, the page that was unprotected; we
+        * optimistically only store address.

Is this supposed to say something like "only store one address"?

Done.

Quoted 28 lines
Quoted 3 lines
mm/kfence/kfence.h +3 -0
+        */
+       unsigned long unprotected_page;
+};

[...]

Quoted 2 lines
mm/kfence/kfence.h +1 -0
+#endif /* MM_KFENCE_KFENCE_H */
mm/kfence/report.c +0 -0

[...]

Quoted 3 lines
mm/kfence/report.c +3 -0
+void kfence_report_error(unsigned long address, const struct kfence_metadata *meta,
+                        enum kfence_error_type type)
+{

[...]

Quoted 3 lines
mm/kfence/report.c +3 -0
+       pr_err("==================================================================\n");
+       /* Print report header. */
+       switch (type) {

[...]

Quoted 13 lines
mm/kfence/report.c +13 -0
+       case KFENCE_ERROR_INVALID_FREE:
+               pr_err("BUG: KFENCE: invalid free in %pS\n\n", (void *)stack_entries[skipnr]);
+               pr_err("Invalid free of 0x" PTR_FMT " (in kfence-#%zd):\n", (void *)address,
+                      object_index);
+               break;
+       }
+
+       /* Print stack trace and object info. */
+       stack_trace_print(stack_entries + skipnr, num_stack_entries - skipnr, 0);
+
+       if (meta) {
+               pr_err("\n");
+               kfence_print_object(NULL, meta);
Quoted 8 lines

mm/kfence/report.c line 215

Quoted 5 lines
mm/kfence/report.c +5 -0
+       }
+
+       /* Print report footer. */
+       pr_err("\n");
+       dump_stack_print_info(KERN_DEFAULT);

Shouldn't this be KERN_ERR, to keep the loglevel consistent with the previous messages?

Done.

Thanks,
-- Marco

#9 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 17 lines · Marco Elver
Quoted 16 lines · Jann Horn
Quoted 14 lines · Marco Elver

This adds the Kernel Electric-Fence (KFENCE) infrastructure. KFENCE is a low-overhead sampling-based memory safety error detector of heap use-after-free, invalid-free, and out-of-bounds access errors.

KFENCE is designed to be enabled in production kernels, and has near zero performance overhead. Compared to KASAN, KFENCE trades performance for precision. The main motivation behind KFENCE's design, is that with enough total uptime KFENCE will detect bugs in code paths not typically exercised by non-production test workloads. One way to quickly achieve a large enough total uptime is when the tool is deployed across a large fleet of machines.

KFENCE objects each reside on a dedicated page, at either the left or right page boundaries.

Quoted 7 lines
Quoted 1 line

(modulo slab alignment)

There are a bunch more details missing; this is just a high-level summary. Because as soon as we mention "modulo slab alignment" one may wonder about missed OOBs, which we solve with redzones. We should not replicate Documentation/dev-tools/kfence.rst; we do refer to it instead. ;-)

Heh, fair.

Quoted 33 lines
Quoted 24 lines
Quoted 8 lines

The pages to the left and right of the object
page are "guard pages", whose attributes are changed to a protected state, and cause page faults on any attempted access to them. Such page faults are then intercepted by KFENCE, which handles the fault gracefully by reporting a memory access error. To detect out-of-bounds writes to memory within the object's page itself, KFENCE also uses pattern-based redzones. The following figure illustrates the page layout:

[...]

Quoted 1 line
include/linux/kfence.h +0 -0

[...]

Quoted 13 lines

+/**
+ * is_kfence_address() - check if an address belongs to KFENCE pool
+ * @addr: address to check
+ *
+ * Return: true or false depending on whether the address is within the KFENCE
+ * object range.
+ *
+ * KFENCE objects live in a separate page range and are not to be intermixed
+ * with regular heap objects (e.g. KFENCE objects must never be added to the
+ * allocator freelists). Failing to do so may and will result in heap
+ * corruptions, therefore is_kfence_address() must be used to check whether
+ * an object requires specific handling.
+ */

Quoted 8 lines

include/linux/kfence.h line 44

Quoted 5 lines
include/linux/kfence.h +5 -0
+static __always_inline bool is_kfence_address(const void *addr)
+{
+       return unlikely((char *)addr >= __kfence_pool &&
+                       (char *)addr < __kfence_pool + KFENCE_POOL_SIZE);
+}

If !CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL, this should probably always return false if __kfence_pool is NULL, right?

Quoted 1 line

That's another check; we don't want to make this more expensive.

Ah, right, I missed that this is the one piece of KFENCE that is actually really hot code until Dmitry pointed that out.

But actually, can't you reduce how hot this is for SLUB by moving is_kfence_address() down into the freeing slowpath? At the moment you use it in slab_free_freelist_hook(), which is in the super-hot fastpath, but you should be able to at least move it down into __slab_free()...

Actually, you already have hooked into __slab_free(), so can't you just get rid of the check in the slab_free_freelist_hook()?

Also, you could do the NULL *after* the range check said "true". That way the NULL check would be on the slowpath and have basically no performance impact.

Quoted 4 lines

This should never receive a NULL, given the places it's used from, which should only be allocator internals where we already know we have a non-NULL object. If it did receive a NULL, I think something else is wrong. Or did we miss a place where it can legally receive a NULL?

Well... not exactly "legally", but e.g. a kernel NULL deref (landing in kfence_handle_page_fault()) might get weird.

[...]

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines
include/linux/kfence.h +3 -0
+         access, use-after-free, and invalid-free errors. KFENCE is designed
+         to have negligible cost to permit enabling it in production
+         environments.

[...]

Quoted 1 line
mm/kfence/core.c +0 -0

[...]

Quoted 1 line

+module_param_named(sample_interval, kfence_sample_interval, ulong, 0600);

Quoted 7 lines
Quoted 4 lines

This is a writable module parameter, but if the sample interval was 0 or a very large value, changing this value at runtime won't actually change the effective interval because the work item will never get kicked off again, right?

When KFENCE has been enabled, setting this to 0 actually reschedules the work immediately; we do not disable KFENCE once it has been enabled.

Those are weird semantics. One value should IMO unambiguously mean one thing, independent of when it was set. In particular, I think that if someone decides to read the current value of kfence_sample_interval through sysfs, and sees the value "0", that should not ambiguously mean "either kfence triggers all the time or it is completely off".

If you don't want to support runtime disabling, can you maybe make the handler refuse to write 0 if kfence has already been initialized?

[...]

Quoted 13 lines
Quoted 6 lines
Quoted 1 line

+#endif

[...]

Quoted 3 lines
mm/kfence/core.c +3 -0
+/* Freelist with available objects. */
+static struct list_head kfence_freelist = LIST_HEAD_INIT(kfence_freelist);
+static DEFINE_RAW_SPINLOCK(kfence_freelist_lock); /* Lock protecting freelist. */

[...]

Quoted 6 lines

mm/kfence/core.c line 78

Quoted 2 lines
mm/kfence/core.c +2 -0
+/* Gates the allocation, ensuring only one succeeds in a given period. */
+static atomic_t allocation_gate = ATOMIC_INIT(1);

I don't think you need to initialize this to anything? toggle_allocation_gate() will set it to zero before enabling the static key, so I don't think anyone will ever see this value.

Quoted 3 lines

Sure. But does it hurt anyone? At least this way we don't need to think about yet another state that only exists on initialization; who knows what we'll change in future.

Well, no, it doesn't hurt. But I see this as equivalent to writing code like:

int ret = 0;
ret = -EINVAL;
if (...)
return ret;

where a write can never have any effect because a second write will clobber the value before it can be read, which is IMO an antipattern. But it admittedly is less clear here, so if you like it better your way, I don't really have a problem with that.

Quoted 9 lines
Quoted 7 lines

[...]

mm/kfence/core.c line 194

Quoted 4 lines
mm/kfence/core.c +4 -0
+/* Check canary byte at @addr. */
+static inline bool check_canary_byte(u8 *addr)
+{
+       if (*addr == KFENCE_CANARY_PATTERN(addr))

You could maybe add a likely() hint here if you want.

Added; but none of this is in a hot path.

Yeah, but when we do hit the kfence alloc/free paths, we should probably still try to be reasonably fast to reduce jitter?

[...]

Quoted 17 lines
Quoted 8 lines
Quoted 8 lines
mm/kfence/core.c +8 -0
+{
+       unsigned long addr;
+
+       lockdep_assert_held(&meta->lock);
+
+       for (addr = ALIGN_DOWN(meta->addr, PAGE_SIZE); addr < meta->addr; addr++) {
+               if (!fn((u8 *)addr))
+                       break;
Quoted 8 lines

mm/kfence/core.c line 214

Quoted 3 lines
mm/kfence/core.c +3 -0
+       }
+
+       for (addr = meta->addr + meta->size; addr < PAGE_ALIGN(meta->addr); addr++) {

Hmm... if the object is on the left side (meaning meta->addr is page-aligned) and the padding is on the right side, won't PAGE_ALIGN(meta->addr)==meta->addr , and therefore none of the padding will be checked?

Quoted 1 line

No, you're thinking of ALIGN_DOWN. PAGE_ALIGN gives us the next page.

Hm, really? Let me go through those macros...

#define __AC(X,Y) (X##Y)
#define _AC(X,Y) __AC(X,Y)
#define PAGE_SHIFT 12
#define PAGE_SIZE (_AC(1,UL) << PAGE_SHIFT)

so:
PAGE_SIZE == (1UL << 12) == 0x1000UL

#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask)) #define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1) #define ALIGN(x, a) __ALIGN_KERNEL((x), (a))

so (omitting casts):
ALIGN(x, a) == ((x + (a - 1)) & ~(a - 1))

#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)

so (omitting casts):
PAGE_ALIGN(addr) == ((addr + (0x1000UL - 1)) & ~(0x1000UL - 1))
== ((addr + 0xfffUL) & 0xfffffffffffff000UL)

meaning that if we e.g. pass in 0x5000, we get:

PAGE_ALIGN(0x5000) == ((0x5000 + 0xfffUL) & 0xfffffffffffff000UL)
== 0x5fffUL & 0xfffffffffffff000UL == 0x5000UL

So if the object is on the left side (meaning meta->addr is page-aligned), we won't check padding.

ALIGN_DOWN rounds down, while PAGE_ALIGN rounds up, but both leave the value as-is if it is already page-aligned.

Quoted 25 lines
Quoted 16 lines
Quoted 16 lines
mm/kfence/core.c +16 -0
+               if (!fn((u8 *)addr))
+                       break;
+       }
+}
+
+static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t gfp)
+{
+       struct kfence_metadata *meta = NULL;
+       unsigned long flags;
+       void *addr;
+
+       /* Try to obtain a free object. */
+       raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+       if (!list_empty(&kfence_freelist)) {
+               meta = list_entry(kfence_freelist.next, struct kfence_metadata, list);
+               list_del_init(&meta->list);
Quoted 8 lines

mm/kfence/core.c line 234

Quoted 4 lines
mm/kfence/core.c +4 -0
+       }
+       raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+       if (!meta)
+               return NULL;

Should this use pr_warn_once(), or something like that, to inform the user that kfence might be stuck with all allocations used by long-living objects and therefore no longer doing anything?

Quoted 3 lines

I don't think so; it might as well recover, and seeing this message once is no indication that we're stuck. Instead, we should (and plan to) monitor /sys/kernel/debug/kfence/stats.

Ah, I guess that's reasonable.

[...]

Quoted 21 lines
Quoted 12 lines
Quoted 12 lines
mm/kfence/core.c +12 -0
+}
+static DECLARE_DELAYED_WORK(kfence_timer, toggle_allocation_gate);
+
+/* === Public interface ===================================================== */
+
+void __init kfence_init(void)
+{
+       /* Setting kfence_sample_interval to 0 on boot disables KFENCE. */
+       if (!kfence_sample_interval)
+               return;
+
+       if (!kfence_initialize_pool()) {
Quoted 8 lines

mm/kfence/core.c line 549

Quoted 6 lines
mm/kfence/core.c +6 -0
+               pr_err("%s failed\n", __func__);
+               return;
+       }
+
+       WRITE_ONCE(kfence_enabled, true);
+       schedule_delayed_work(&kfence_timer, 0);

This is schedule_work(&kfence_timer).

Quoted 1 line

No, schedule_work() is not generic and does not take a struct delayed_work.

Ah, of course. Never mind.

author maintainer
#10 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

On Fri, Oct 02, 2020 at 09:31PM +0200, Jann Horn wrote:
[...]

Quoted 15 lines
Quoted 5 lines
Quoted 3 lines

If !CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL, this should probably always return false if __kfence_pool is NULL, right?

That's another check; we don't want to make this more expensive.

Ah, right, I missed that this is the one piece of KFENCE that is actually really hot code until Dmitry pointed that out.

But actually, can't you reduce how hot this is for SLUB by moving is_kfence_address() down into the freeing slowpath? At the moment you use it in slab_free_freelist_hook(), which is in the super-hot fastpath, but you should be able to at least move it down into __slab_free()...

Quoted 6 lines

Actually, you already have hooked into __slab_free(), so can't you just get rid of the check in the slab_free_freelist_hook()?

Also, you could do the NULL *after* the range check said "true". That way the NULL check would be on the slowpath and have basically no performance impact.

True; let's try to do that then, and hope the few extra instructions do not hurt us.

Quoted 25 lines
Quoted 4 lines

This should never receive a NULL, given the places it's used from, which should only be allocator internals where we already know we have a non-NULL object. If it did receive a NULL, I think something else is wrong. Or did we miss a place where it can legally receive a NULL?

Well... not exactly "legally", but e.g. a kernel NULL deref (landing in kfence_handle_page_fault()) might get weird.

[...]

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines
lib/Kconfig.kfence new file +3 -0
+         access, use-after-free, and invalid-free errors. KFENCE is designed
+         to have negligible cost to permit enabling it in production
+         environments.

[...]

Quoted 1 line
mm/kfence/core.c +0 -0

[...]

Quoted 1 line

+module_param_named(sample_interval, kfence_sample_interval, ulong, 0600);

Quoted 7 lines
Quoted 4 lines

This is a writable module parameter, but if the sample interval was 0 or a very large value, changing this value at runtime won't actually change the effective interval because the work item will never get kicked off again, right?

When KFENCE has been enabled, setting this to 0 actually reschedules the work immediately; we do not disable KFENCE once it has been enabled.

Quoted 8 lines

Those are weird semantics. One value should IMO unambiguously mean one thing, independent of when it was set. In particular, I think that if someone decides to read the current value of kfence_sample_interval through sysfs, and sees the value "0", that should not ambiguously mean "either kfence triggers all the time or it is completely off".

If you don't want to support runtime disabling, can you maybe make the handler refuse to write 0 if kfence has already been initialized?

I could live with 0 being rejected; will change it. (I personally had used piping 0 at runtime to stress test, but perhaps if it's only devs doing it we can just change the code for debugging/testing.)

Quoted 20 lines

[...]

Quoted 13 lines
Quoted 6 lines
Quoted 1 line

+#endif

[...]

Quoted 3 lines
mm/kfence/core.c +3 -0
+/* Freelist with available objects. */
+static struct list_head kfence_freelist = LIST_HEAD_INIT(kfence_freelist);
+static DEFINE_RAW_SPINLOCK(kfence_freelist_lock); /* Lock protecting freelist. */

[...]

Quoted 6 lines

mm/kfence/core.c line 78

Quoted 2 lines
mm/kfence/core.c +2 -0
+/* Gates the allocation, ensuring only one succeeds in a given period. */
+static atomic_t allocation_gate = ATOMIC_INIT(1);

I don't think you need to initialize this to anything? toggle_allocation_gate() will set it to zero before enabling the static key, so I don't think anyone will ever see this value.

Quoted 3 lines

Sure. But does it hurt anyone? At least this way we don't need to think about yet another state that only exists on initialization; who knows what we'll change in future.

Well, no, it doesn't hurt. But I see this as equivalent to writing code like:

Quoted 7 lines

int ret = 0;
ret = -EINVAL;
if (...)
return ret;

where a write can never have any effect because a second write will clobber the value before it can be read, which is IMO an antipattern.

Agree fully ^

Just being defensive with global states that can potentially be read for other purposes before toggle_allocation_gate(); I think elsewhere you e.g. suggested to use allocation_gate for the IPI optimization. It's these types of changes that depend on our global states, where making the initial state non-special just saves us trouble.

Quoted 2 lines

But it admittedly is less clear here, so if you like it better your way, I don't really have a problem with that.

[...]

Quoted 49 lines

[...]

Quoted 17 lines
Quoted 8 lines
Quoted 8 lines
mm/kfence/core.c +8 -0
+{
+       unsigned long addr;
+
+       lockdep_assert_held(&meta->lock);
+
+       for (addr = ALIGN_DOWN(meta->addr, PAGE_SIZE); addr < meta->addr; addr++) {
+               if (!fn((u8 *)addr))
+                       break;
Quoted 8 lines

mm/kfence/core.c line 214

Quoted 3 lines
mm/kfence/core.c +3 -0
+       }
+
+       for (addr = meta->addr + meta->size; addr < PAGE_ALIGN(meta->addr); addr++) {

Hmm... if the object is on the left side (meaning meta->addr is page-aligned) and the padding is on the right side, won't PAGE_ALIGN(meta->addr)==meta->addr , and therefore none of the padding will be checked?

Quoted 1 line

No, you're thinking of ALIGN_DOWN. PAGE_ALIGN gives us the next page.

Hm, really? Let me go through those macros...

#define __AC(X,Y) (X##Y)
#define _AC(X,Y) __AC(X,Y)
#define PAGE_SHIFT 12
#define PAGE_SIZE (_AC(1,UL) << PAGE_SHIFT)

so:
PAGE_SIZE == (1UL << 12) == 0x1000UL

#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask)) #define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1) #define ALIGN(x, a) __ALIGN_KERNEL((x), (a))

so (omitting casts):
ALIGN(x, a) == ((x + (a - 1)) & ~(a - 1))

#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)

so (omitting casts):
PAGE_ALIGN(addr) == ((addr + (0x1000UL - 1)) & ~(0x1000UL - 1))
== ((addr + 0xfffUL) & 0xfffffffffffff000UL)

meaning that if we e.g. pass in 0x5000, we get:

PAGE_ALIGN(0x5000) == ((0x5000 + 0xfffUL) & 0xfffffffffffff000UL)
== 0x5fffUL & 0xfffffffffffff000UL == 0x5000UL

Quoted 6 lines

So if the object is on the left side (meaning meta->addr is page-aligned), we won't check padding.

ALIGN_DOWN rounds down, while PAGE_ALIGN rounds up, but both leave the value as-is if it is already page-aligned.

Ah, yes, sorry about that; I confused myself with the comment above PAGE_ALIGN.

We'll fix this. And add a test. :-)

Thanks,
-- Marco

author maintainer
#11 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

In reply to Jann Horn
Quoted 5 lines · Jann Horn
Quoted 1 line

That's another check; we don't want to make this more expensive.

Ah, right, I missed that this is the one piece of KFENCE that is actually really hot code until Dmitry pointed that out.

Quoted 8 lines

But actually, can't you reduce how hot this is for SLUB by moving is_kfence_address() down into the freeing slowpath? At the moment you use it in slab_free_freelist_hook(), which is in the super-hot fastpath, but you should be able to at least move it down into __slab_free()...

Actually, you already have hooked into __slab_free(), so can't you just get rid of the check in the slab_free_freelist_hook()?

I missed this bit: the loop that follows wants the free pointer, so I currently see how this might work. :-/

We'll look at your other email re optimizing is_kfence_address() next week; and thank you for the detailed comments thus far!

Thanks,
-- Marco

#12 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

Quoted 12 lines · Marco Elver
Quoted 11 lines · Jann Horn
Quoted 1 line

That's another check; we don't want to make this more expensive.

Ah, right, I missed that this is the one piece of KFENCE that is actually really hot code until Dmitry pointed that out.

But actually, can't you reduce how hot this is for SLUB by moving is_kfence_address() down into the freeing slowpath? At the moment you use it in slab_free_freelist_hook(), which is in the super-hot fastpath, but you should be able to at least move it down into __slab_free()...

Quoted 5 lines
Quoted 2 lines

Actually, you already have hooked into __slab_free(), so can't you just get rid of the check in the slab_free_freelist_hook()?

I missed this bit: the loop that follows wants the free pointer, so I currently see how this might work. :-/

reverse call graph:
__slab_free
do_slab_free
slab_free
kmem_cache_free (frees a single non-kmalloc allocation) kmem_cache_free_bulk (frees multiple)
kfree (frees a single kmalloc allocation)
___cache_free (frees a single allocation for KASAN)

So the only path for which we can actually loop in __slab_free() is kmem_cache_free_bulk(); and you've already changed build_detached_freelist() (which is used by kmem_cache_free_bulk() to group objects from the same page) to consume KFENCE allocations before they can ever reach __slab_free(). So we know that if we've reached __slab_free(), then we are being called with either a single object (which may be a KFENCE object) or with a list of objects that all belong to the same page and don't contain any KFENCE allocations.

author maintainer
#13 lore raw

Re: [PATCH v4 01/11] mm: add Kernel Electric-Fence infrastructure

[ Sorry for delay, just noticed this one doesn't have a reply yet. ]

Quoted 28 lines · Jann Horn
Quoted 12 lines · Marco Elver
Quoted 11 lines · Jann Horn
Quoted 1 line

That's another check; we don't want to make this more expensive.

Ah, right, I missed that this is the one piece of KFENCE that is actually really hot code until Dmitry pointed that out.

But actually, can't you reduce how hot this is for SLUB by moving is_kfence_address() down into the freeing slowpath? At the moment you use it in slab_free_freelist_hook(), which is in the super-hot fastpath, but you should be able to at least move it down into __slab_free()...

Quoted 5 lines
Quoted 2 lines

Actually, you already have hooked into __slab_free(), so can't you just get rid of the check in the slab_free_freelist_hook()?

I missed this bit: the loop that follows wants the free pointer, so I currently see how this might work. :-/

reverse call graph:
__slab_free
do_slab_free
slab_free
kmem_cache_free (frees a single non-kmalloc allocation) kmem_cache_free_bulk (frees multiple)
kfree (frees a single kmalloc allocation)
___cache_free (frees a single allocation for KASAN)

Quoted 8 lines

So the only path for which we can actually loop in __slab_free() is kmem_cache_free_bulk(); and you've already changed build_detached_freelist() (which is used by kmem_cache_free_bulk() to group objects from the same page) to consume KFENCE allocations before they can ever reach __slab_free(). So we know that if we've reached __slab_free(), then we are being called with either a single object (which may be a KFENCE object) or with a list of objects that all belong to the same page and don't contain any KFENCE allocations.

Yes, while that is true, we still cannot execute the code in slab_free_freelist_hook(). There are several problems:

- getting the freepointer which accesses object + s->offset, may result in KFENCE OOB errors.

- similarly for setting the freepointer.

- slab_want_init_on_free zeroing object according to memcache object_size, because it'll corrupt KFENCE's redzone if memcache object_size > actual allocation size.

Leaving this here is fine, since we have determined that recent optimizations make the check in slab_free_freelist_hook() negligible.

Thanks,
-- Marco

author maintainer
#14 lore raw

PATCH v4 2/11 x86, kfence: enable KFENCE for x86

In reply to Marco Elver

From: Alexander Potapenko <[email protected]>

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

For x86, we need to ensure that the pool uses 4K pages, which is done using the set_memory_4k() helper function.

---
v4:
* Define __kfence_pool_attrs.

---
 arch/x86/Kconfig              |  2 ++
 arch/x86/include/asm/kfence.h | 60 +++++++++++++++++++++++++++++++++++
 arch/x86/mm/fault.c           |  4 +++
 3 files changed, 66 insertions(+)
 create mode 100644 arch/x86/include/asm/kfence.h
arch/x86/Kconfig +2 -0
index 7101ac64bb20..e22dc722698c 100644
@@ -144,6 +144,8 @@ config X86
 	select HAVE_ARCH_JUMP_LABEL_RELATIVE
 	select HAVE_ARCH_KASAN			if X86_64
 	select HAVE_ARCH_KASAN_VMALLOC		if X86_64
+	select HAVE_ARCH_KFENCE
+	select HAVE_ARCH_KFENCE_STATIC_POOL
 	select HAVE_ARCH_KGDB
 	select HAVE_ARCH_MMAP_RND_BITS		if MMU
 	select HAVE_ARCH_MMAP_RND_COMPAT_BITS	if MMU && COMPAT
arch/x86/include/asm/kfence.h new file +60 -0

60 lines not on this page · raw message

arch/x86/mm/fault.c +4 -0
index 6e3e8a124903..423e15ad5eb6 100644
@@ -9,6 +9,7 @@
 #include <linux/kdebug.h>		/* oops_begin/end, ...		*/
 #include <linux/extable.h>		/* search_exception_tables	*/
 #include <linux/memblock.h>		/* max_low_pfn			*/
+#include <linux/kfence.h>		/* kfence_handle_page_fault	*/
 #include <linux/kprobes.h>		/* NOKPROBE_SYMBOL, ...		*/
 #include <linux/mmiotrace.h>		/* kmmio_handler, ...		*/
 #include <linux/perf_event.h>		/* perf_sw_event		*/
@@ -701,6 +702,9 @@ no_context(struct pt_regs *regs, unsigned long error_code,
 	}
 #endif
 
+	if (kfence_handle_page_fault(address))
+		return;
+
 	/*
 	 * 32-bit:
 	 *
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
#15 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

Quoted 7 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

For x86, we need to ensure that the pool uses 4K pages, which is done using the set_memory_4k() helper function.

[...]

Quoted 1 line
arch/x86/include/asm/kfence.h +0 -0

[...]

arch/x86/include/asm/kfence.h line 48

Quoted 7 lines
arch/x86/include/asm/kfence.h +7 -0
+/* Protect the given page and flush TLBs. */
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{
+       unsigned int level;
+       pte_t *pte = lookup_address(addr, &level);
+
+       if (!pte || level != PG_LEVEL_4K)

Do we actually expect this to happen, or is this just a "robustness" check? If we don't expect this to happen, there should be a WARN_ON() around the condition.

arch/x86/include/asm/kfence.h line 54

Quoted 6 lines
arch/x86/include/asm/kfence.h +6 -0
+               return false;
+
+       if (protect)
+               set_pte(pte, __pte(pte_val(*pte) & ~_PAGE_PRESENT));
+       else
+               set_pte(pte, __pte(pte_val(*pte) | _PAGE_PRESENT));

Hmm... do we have this helper (instead of using the existing helpers for modifying memory permissions) to work around the allocation out of the data section?

Quoted 6 lines
arch/x86/include/asm/kfence.h +5 -0
+       flush_tlb_one_kernel(addr);
+       return true;
+}
+
+#endif /* _ASM_X86_KFENCE_H */
arch/x86/mm/fault.c +0 -0

[...]

arch/x86/mm/fault.c no_context(struct pt_regs *regs, unsigned long error_code, · line 710

Quoted 10 lines
arch/x86/mm/fault.c +3 -0
@@ -701,6 +702,9 @@ no_context(struct pt_regs *regs, unsigned long error_code,
        }
 #endif
 
+       if (kfence_handle_page_fault(address))
+               return;
+
        /*
         * 32-bit:
         *

The standard 5 lines of diff context don't really make it obvious what's going on here. Here's a diff with more context:

        /*
         * Stack overflow?  During boot, we can fault near the initial
         * stack in the direct map, but that's not an overflow -- check
         * that we're in vmalloc space to avoid this.
         */
        if (is_vmalloc_addr((void *)address) &&
            (((unsigned long)tsk->stack - 1 - address < PAGE_SIZE) ||
             address - ((unsigned long)tsk->stack + THREAD_SIZE) < PAGE_SIZE)) {
                unsigned long stack = __this_cpu_ist_top_va(DF) -
sizeof(void *);
                /*
                 * We're likely to be running with very little stack space
                 * left.  It's plausible that we'd hit this condition but
                 * double-fault even before we get this far, in which case
                 * we're fine: the double-fault handler will deal with it.
                 *
                 * We don't want to make it all the way into the oops code
                 * and then double-fault, though, because we're likely to
                 * break the console driver and lose most of the stack dump.
                 */
                asm volatile ("movq %[stack], %%rsp\n\t"
                              "call handle_stack_overflow\n\t"
                              "1: jmp 1b"
                              : ASM_CALL_CONSTRAINT
                              : "D" ("kernel stack overflow (page fault)"),
                                "S" (regs), "d" (address),
                                [stack] "rm" (stack));
                unreachable();
        }

#endif

+ if (kfence_handle_page_fault(address))
+ return;
+

        /*
         * 32-bit:
         *
         *   Valid to do another page fault here, because if this fault
         *   had been triggered by is_prefetch fixup_exception would have
         *   handled it.
         *
         * 64-bit:
         *
         *   Hall of shame of CPU/BIOS bugs.
         */
        if (is_prefetch(regs, error_code, address))
                return;

        if (is_errata93(regs, address))
                return;

        /*
         * Buggy firmware could access regions which might page fault, try to
         * recover from such faults.
         */
        if (IS_ENABLED(CONFIG_EFI))
                efi_recover_from_page_fault(address);

oops:

        /*
         * Oops. The kernel tried to access some bad page. We'll have to
         * terminate things with extreme prejudice:
         */
        flags = oops_begin();

Shouldn't kfence_handle_page_fault() happen after prefetch handling, at least? Maybe directly above the "oops" label?

author maintainer
#16 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

Quoted 12 lines · Jann Horn
Quoted 7 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

For x86, we need to ensure that the pool uses 4K pages, which is done using the set_memory_4k() helper function.

[...]

Quoted 1 line
arch/x86/include/asm/kfence.h +0 -0

[...]

Quoted 11 lines

arch/x86/include/asm/kfence.h line 48

Quoted 7 lines
arch/x86/include/asm/kfence.h +7 -0
+/* Protect the given page and flush TLBs. */
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{
+       unsigned int level;
+       pte_t *pte = lookup_address(addr, &level);
+
+       if (!pte || level != PG_LEVEL_4K)

Do we actually expect this to happen, or is this just a "robustness" check? If we don't expect this to happen, there should be a WARN_ON() around the condition.

It's not obvious here, but we already have this covered with a WARN:
the core.c code has a KFENCE_WARN_ON, which disables KFENCE on a warning.

Quoted 10 lines

arch/x86/include/asm/kfence.h line 54

Quoted 6 lines
arch/x86/include/asm/kfence.h +6 -0
+               return false;
+
+       if (protect)
+               set_pte(pte, __pte(pte_val(*pte) & ~_PAGE_PRESENT));
+       else
+               set_pte(pte, __pte(pte_val(*pte) | _PAGE_PRESENT));

Hmm... do we have this helper (instead of using the existing helpers for modifying memory permissions) to work around the allocation out of the data section?

I just played around with using the set_memory.c functions, to remind myself why this didn't work. I experimented with using set_memory_{np,p}() functions; set_memory_p() isn't implemented, but is easily added (which I did for below experiment). However, this didn't quite work:

WARNING: CPU: 6 PID: 107 at kernel/smp.c:490
smp_call_function_many_cond+0x9c/0x2a0 kernel/smp.c:490
[...]
Call Trace:
 smp_call_function_many kernel/smp.c:577 [inline]
 smp_call_function kernel/smp.c:599 [inline]
 on_each_cpu+0x3e/0x90 kernel/smp.c:698
 __purge_vmap_area_lazy+0x58/0x670 mm/vmalloc.c:1352
 _vm_unmap_aliases.part.0+0x10b/0x140 mm/vmalloc.c:1770
 change_page_attr_set_clr+0xb4/0x1c0 arch/x86/mm/pat/set_memory.c:1732
 change_page_attr_set arch/x86/mm/pat/set_memory.c:1782 [inline]
 set_memory_p+0x21/0x30 arch/x86/mm/pat/set_memory.c:1950
 kfence_protect_page arch/x86/include/asm/kfence.h:55 [inline]
 kfence_protect_page arch/x86/include/asm/kfence.h:43 [inline]
 kfence_unprotect+0x42/0x70 mm/kfence/core.c:139
 no_context+0x115/0x300 arch/x86/mm/fault.c:705
 handle_page_fault arch/x86/mm/fault.c:1431 [inline]
 exc_page_fault+0xa7/0x170 arch/x86/mm/fault.c:1486
 asm_exc_page_fault+0x1e/0x30 arch/x86/include/asm/idtentry.h:538

For one, smp_call_function_many_cond() doesn't want to be called with interrupts disabled, and we may very well get a KFENCE allocation or page fault with interrupts disabled / within interrupts.

Therefore, to be safe, we should avoid IPIs. It follows that setting the page attribute is best-effort, and we can tolerate some inaccuracy. Lazy fault handling should take care of faults after we set the page as PRESENT.

Which hopefully also answers your other comment:

Quoted 5 lines

flush_tlb_one_kernel() -> flush_tlb_one_user() -> __flush_tlb_one_user() -> native_flush_tlb_one_user() only flushes on the local CPU core, not on others. If you want to leave it this way, I think this needs a comment explaining why we're not doing a global flush (locking context / performance overhead / ... ?).

We'll add a comment to clarify why it's done this way.

Quoted 89 lines
Quoted 6 lines
arch/x86/include/asm/kfence.h +5 -0
+       flush_tlb_one_kernel(addr);
+       return true;
+}
+
+#endif /* _ASM_X86_KFENCE_H */
arch/x86/mm/fault.c +0 -0

[...]

arch/x86/mm/fault.c no_context(struct pt_regs *regs, unsigned long error_code, · line 710

Quoted 10 lines
arch/x86/mm/fault.c +3 -0
@@ -701,6 +702,9 @@ no_context(struct pt_regs *regs, unsigned long error_code,
        }
 #endif
 
+       if (kfence_handle_page_fault(address))
+               return;
+
        /*
         * 32-bit:
         *

The standard 5 lines of diff context don't really make it obvious what's going on here. Here's a diff with more context:

        /*
         * Stack overflow?  During boot, we can fault near the initial
         * stack in the direct map, but that's not an overflow -- check
         * that we're in vmalloc space to avoid this.
         */
        if (is_vmalloc_addr((void *)address) &&
            (((unsigned long)tsk->stack - 1 - address < PAGE_SIZE) ||
             address - ((unsigned long)tsk->stack + THREAD_SIZE) < PAGE_SIZE)) {
                unsigned long stack = __this_cpu_ist_top_va(DF) -
sizeof(void *);
                /*
                 * We're likely to be running with very little stack space
                 * left.  It's plausible that we'd hit this condition but
                 * double-fault even before we get this far, in which case
                 * we're fine: the double-fault handler will deal with it.
                 *
                 * We don't want to make it all the way into the oops code
                 * and then double-fault, though, because we're likely to
                 * break the console driver and lose most of the stack dump.
                 */
                asm volatile ("movq %[stack], %%rsp\n\t"
                              "call handle_stack_overflow\n\t"
                              "1: jmp 1b"
                              : ASM_CALL_CONSTRAINT
                              : "D" ("kernel stack overflow (page fault)"),
                                "S" (regs), "d" (address),
                                [stack] "rm" (stack));
                unreachable();
        }

#endif

(quoted diff) +3 -0
+       if (kfence_handle_page_fault(address))
+               return;
+
        /*
         * 32-bit:
         *
         *   Valid to do another page fault here, because if this fault
         *   had been triggered by is_prefetch fixup_exception would have
         *   handled it.
         *
         * 64-bit:
         *
         *   Hall of shame of CPU/BIOS bugs.
         */
        if (is_prefetch(regs, error_code, address))
                return;
 
        if (is_errata93(regs, address))
                return;
 
        /*
         * Buggy firmware could access regions which might page fault, try to
         * recover from such faults.
         */
        if (IS_ENABLED(CONFIG_EFI))
                efi_recover_from_page_fault(address);
 
 oops:
        /*
         * Oops. The kernel tried to access some bad page. We'll have to
         * terminate things with extreme prejudice:
         */
        flags = oops_begin();
Quoted 2 lines

Shouldn't kfence_handle_page_fault() happen after prefetch handling, at least? Maybe directly above the "oops" label?

Good question. AFAIK it doesn't matter, as is_kfence_address() should never apply for any of those that follow, right? In any case, it shouldn't hurt to move it down.

Thanks,
-- Marco

#17 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

Quoted 24 lines · Marco Elver
Quoted 11 lines · Jann Horn
Quoted 7 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

For x86, we need to ensure that the pool uses 4K pages, which is done using the set_memory_4k() helper function.

[...]

Quoted 1 line
arch/x86/include/asm/kfence.h +0 -0

[...]

Quoted 11 lines

arch/x86/include/asm/kfence.h line 48

Quoted 7 lines
arch/x86/include/asm/kfence.h +7 -0
+/* Protect the given page and flush TLBs. */
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{
+       unsigned int level;
+       pte_t *pte = lookup_address(addr, &level);
+
+       if (!pte || level != PG_LEVEL_4K)

Do we actually expect this to happen, or is this just a "robustness" check? If we don't expect this to happen, there should be a WARN_ON() around the condition.

Quoted 3 lines

It's not obvious here, but we already have this covered with a WARN:
the core.c code has a KFENCE_WARN_ON, which disables KFENCE on a warning.

So for this specific branch: Can it ever happen? If not, please either remove it or add WARN_ON(). That serves two functions: It ensures that if something unexpected happens, we see a warning, and it hints to people reading the code "this isn't actually expected to happen, you don't have to wrack your brain trying to figure out for which scenario this branch is intended".

Quoted 16 lines
Quoted 10 lines

arch/x86/include/asm/kfence.h line 54

Quoted 6 lines
arch/x86/include/asm/kfence.h +6 -0
+               return false;
+
+       if (protect)
+               set_pte(pte, __pte(pte_val(*pte) & ~_PAGE_PRESENT));
+       else
+               set_pte(pte, __pte(pte_val(*pte) | _PAGE_PRESENT));

Hmm... do we have this helper (instead of using the existing helpers for modifying memory permissions) to work around the allocation out of the data section?

I just played around with using the set_memory.c functions, to remind myself why this didn't work. I experimented with using set_memory_{np,p}() functions; set_memory_p() isn't implemented, but is easily added (which I did for below experiment). However, this didn't quite work:

[...]

Quoted 5 lines

For one, smp_call_function_many_cond() doesn't want to be called with interrupts disabled, and we may very well get a KFENCE allocation or page fault with interrupts disabled / within interrupts.

Therefore, to be safe, we should avoid IPIs.

set_direct_map_invalid_noflush() does that, too, I think? And that's already implemented for both arm64 and x86.

Quoted 4 lines

It follows that setting
the page attribute is best-effort, and we can tolerate some inaccuracy. Lazy fault handling should take care of faults after we set the page as PRESENT.

[...]

Quoted 6 lines
Quoted 2 lines

Shouldn't kfence_handle_page_fault() happen after prefetch handling, at least? Maybe directly above the "oops" label?

Good question. AFAIK it doesn't matter, as is_kfence_address() should never apply for any of those that follow, right? In any case, it shouldn't hurt to move it down.

is_prefetch() ignores any #PF not caused by instruction fetch if it comes from kernel mode and the faulting instruction is one of the PREFETCH* instructions. (Which is not supposed to happen - the processor should just be ignoring the fault for PREFETCH instead of generating an exception AFAIK. But the comments say that this is about CPU bugs and stuff.) While this is probably not a big deal anymore partly because the kernel doesn't use software prefetching in many places anymore, it seems to me like, in principle, this could also cause page faults that should be ignored in KFENCE regions if someone tries to do PREFETCH on an out-of-bounds array element or a dangling pointer or something.

author maintainer
#18 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

Quoted 30 lines · Jann Horn
Quoted 24 lines · Marco Elver
Quoted 11 lines · Jann Horn
Quoted 7 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

For x86, we need to ensure that the pool uses 4K pages, which is done using the set_memory_4k() helper function.

[...]

Quoted 1 line
arch/x86/include/asm/kfence.h +0 -0

[...]

Quoted 11 lines

arch/x86/include/asm/kfence.h line 48

Quoted 7 lines
arch/x86/include/asm/kfence.h +7 -0
+/* Protect the given page and flush TLBs. */
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{
+       unsigned int level;
+       pte_t *pte = lookup_address(addr, &level);
+
+       if (!pte || level != PG_LEVEL_4K)

Do we actually expect this to happen, or is this just a "robustness" check? If we don't expect this to happen, there should be a WARN_ON() around the condition.

Quoted 3 lines

It's not obvious here, but we already have this covered with a WARN:
the core.c code has a KFENCE_WARN_ON, which disables KFENCE on a warning.

Quoted 6 lines

So for this specific branch: Can it ever happen? If not, please either remove it or add WARN_ON(). That serves two functions: It ensures that if something unexpected happens, we see a warning, and it hints to people reading the code "this isn't actually expected to happen, you don't have to wrack your brain trying to figure out for which scenario this branch is intended".

Perhaps I could have been clearer: we already have this returning false covered by a WARN+disable KFENCE in core.c.

We'll add another WARN_ON right here, as it doesn't hurt, and hopefully improves readability.

Quoted 17 lines
Quoted 16 lines
Quoted 10 lines

arch/x86/include/asm/kfence.h line 54

Quoted 6 lines
arch/x86/include/asm/kfence.h +6 -0
+               return false;
+
+       if (protect)
+               set_pte(pte, __pte(pte_val(*pte) & ~_PAGE_PRESENT));
+       else
+               set_pte(pte, __pte(pte_val(*pte) | _PAGE_PRESENT));

Hmm... do we have this helper (instead of using the existing helpers for modifying memory permissions) to work around the allocation out of the data section?

I just played around with using the set_memory.c functions, to remind myself why this didn't work. I experimented with using set_memory_{np,p}() functions; set_memory_p() isn't implemented, but is easily added (which I did for below experiment). However, this didn't quite work:

[...]

Quoted 8 lines
Quoted 5 lines

For one, smp_call_function_many_cond() doesn't want to be called with interrupts disabled, and we may very well get a KFENCE allocation or page fault with interrupts disabled / within interrupts.

Therefore, to be safe, we should avoid IPIs.

set_direct_map_invalid_noflush() does that, too, I think? And that's already implemented for both arm64 and x86.

Sure, that works.

We still want the flush_tlb_one_kernel(), at least so the local CPU's TLB is flushed.

Quoted 12 lines
Quoted 4 lines

It follows that setting
the page attribute is best-effort, and we can tolerate some inaccuracy. Lazy fault handling should take care of faults after we set the page as PRESENT.

[...]

Quoted 6 lines
Quoted 2 lines

Shouldn't kfence_handle_page_fault() happen after prefetch handling, at least? Maybe directly above the "oops" label?

Good question. AFAIK it doesn't matter, as is_kfence_address() should never apply for any of those that follow, right? In any case, it shouldn't hurt to move it down.

Quoted 11 lines

is_prefetch() ignores any #PF not caused by instruction fetch if it comes from kernel mode and the faulting instruction is one of the PREFETCH* instructions. (Which is not supposed to happen - the processor should just be ignoring the fault for PREFETCH instead of generating an exception AFAIK. But the comments say that this is about CPU bugs and stuff.) While this is probably not a big deal anymore partly because the kernel doesn't use software prefetching in many places anymore, it seems to me like, in principle, this could also cause page faults that should be ignored in KFENCE regions if someone tries to do PREFETCH on an out-of-bounds array element or a dangling pointer or something.

Thanks for the clarification.

author maintainer
#19 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

Quoted 1 line · Marco Elver

On Wed, 7 Oct 2020 at 16:15, Jann Horn <[email protected]> wrote:

[...]

Quoted 23 lines
Quoted 23 lines
Quoted 16 lines
Quoted 10 lines

arch/x86/include/asm/kfence.h line 54

Quoted 6 lines
arch/x86/include/asm/kfence.h new file +6 -0
+               return false;
+
+       if (protect)
+               set_pte(pte, __pte(pte_val(*pte) & ~_PAGE_PRESENT));
+       else
+               set_pte(pte, __pte(pte_val(*pte) | _PAGE_PRESENT));

Hmm... do we have this helper (instead of using the existing helpers for modifying memory permissions) to work around the allocation out of the data section?

I just played around with using the set_memory.c functions, to remind myself why this didn't work. I experimented with using set_memory_{np,p}() functions; set_memory_p() isn't implemented, but is easily added (which I did for below experiment). However, this didn't quite work:

[...]

Quoted 5 lines

For one, smp_call_function_many_cond() doesn't want to be called with interrupts disabled, and we may very well get a KFENCE allocation or page fault with interrupts disabled / within interrupts.

Therefore, to be safe, we should avoid IPIs.

Quoted 7 lines
Quoted 2 lines

set_direct_map_invalid_noflush() does that, too, I think? And that's already implemented for both arm64 and x86.

Sure, that works.

We still want the flush_tlb_one_kernel(), at least so the local CPU's TLB is flushed.

Nope, sorry, set_direct_map_invalid_noflush() does not work -- this results in potential deadlock.

	================================
	WARNING: inconsistent lock state
	5.9.0-rc4+ #2 Not tainted
	--------------------------------
	inconsistent {SOFTIRQ-ON-W} -> {IN-SOFTIRQ-W} usage.
	ksoftirqd/1/16 [HC0[0]:SC1[1]:HE1:SE0] takes:
	ffffffff89fcf9b8 (cpa_lock){+.?.}-{2:2}, at: spin_lock include/linux/spinlock.h:354 [inline]
	ffffffff89fcf9b8 (cpa_lock){+.?.}-{2:2}, at: __change_page_attr_set_clr+0x1b0/0x2510 arch/x86/mm/pat/set_memory.c:1658
	{SOFTIRQ-ON-W} state was registered at:
	  lock_acquire+0x1f3/0xae0 kernel/locking/lockdep.c:5006
	  __raw_spin_lock include/linux/spinlock_api_smp.h:142 [inline]
	  _raw_spin_lock+0x2a/0x40 kernel/locking/spinlock.c:151
	  spin_lock include/linux/spinlock.h:354 [inline]
	  __change_page_attr_set_clr+0x1b0/0x2510 arch/x86/mm/pat/set_memory.c:1658
	  change_page_attr_set_clr+0x333/0x500 arch/x86/mm/pat/set_memory.c:1752
	  change_page_attr_set arch/x86/mm/pat/set_memory.c:1782 [inline]
	  set_memory_nx+0xb2/0x110 arch/x86/mm/pat/set_memory.c:1930
	  free_init_pages+0x73/0xc0 arch/x86/mm/init.c:876
	  alternative_instructions+0x155/0x1a4 arch/x86/kernel/alternative.c:738
	  check_bugs+0x1bd0/0x1c77 arch/x86/kernel/cpu/bugs.c:140
	  start_kernel+0x486/0x4b6 init/main.c:1042
	  secondary_startup_64+0xa4/0xb0 arch/x86/kernel/head_64.S:243
	irq event stamp: 14564
	hardirqs last  enabled at (14564): [<ffffffff8828cadf>] __raw_spin_unlock_irqrestore include/linux/spinlock_api_smp.h:160 [inline]
	hardirqs last  enabled at (14564): [<ffffffff8828cadf>] _raw_spin_unlock_irqrestore+0x6f/0x90 kernel/locking/spinlock.c:191
	hardirqs last disabled at (14563): [<ffffffff8828d239>] __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:108 [inline]
	hardirqs last disabled at (14563): [<ffffffff8828d239>] _raw_spin_lock_irqsave+0xa9/0xce kernel/locking/spinlock.c:159
	softirqs last  enabled at (14486): [<ffffffff8147fcff>] run_ksoftirqd kernel/softirq.c:652 [inline]
	softirqs last  enabled at (14486): [<ffffffff8147fcff>] run_ksoftirqd+0xcf/0x170 kernel/softirq.c:644
	softirqs last disabled at (14491): [<ffffffff8147fcff>] run_ksoftirqd kernel/softirq.c:652 [inline]
	softirqs last disabled at (14491): [<ffffffff8147fcff>] run_ksoftirqd+0xcf/0x170 kernel/softirq.c:644

	other info that might help us debug this:
	 Possible unsafe locking scenario:

	       CPU0
	       ----
	  lock(cpa_lock);
	  <Interrupt>
	    lock(cpa_lock);

	 *** DEADLOCK ***

	1 lock held by ksoftirqd/1/16:
	 #0: ffffffff8a067e20 (rcu_callback){....}-{0:0}, at: rcu_do_batch kernel/rcu/tree.c:2418 [inline]
	 #0: ffffffff8a067e20 (rcu_callback){....}-{0:0}, at: rcu_core+0x55d/0x1130 kernel/rcu/tree.c:2656

	stack backtrace:
	CPU: 1 PID: 16 Comm: ksoftirqd/1 Not tainted 5.9.0-rc4+ #2
	Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1 04/01/2014
	Call Trace:
	 __dump_stack lib/dump_stack.c:77 [inline]
	 dump_stack+0x198/0x1fd lib/dump_stack.c:118
	 print_usage_bug kernel/locking/lockdep.c:3350 [inline]
	 valid_state kernel/locking/lockdep.c:3361 [inline]
	 mark_lock_irq kernel/locking/lockdep.c:3575 [inline]
	 mark_lock.cold+0x12/0x17 kernel/locking/lockdep.c:4006
	 mark_usage kernel/locking/lockdep.c:3905 [inline]
	 __lock_acquire+0x1159/0x5780 kernel/locking/lockdep.c:4380
	 lock_acquire+0x1f3/0xae0 kernel/locking/lockdep.c:5006
	 __raw_spin_lock include/linux/spinlock_api_smp.h:142 [inline]
	 _raw_spin_lock+0x2a/0x40 kernel/locking/spinlock.c:151
	 spin_lock include/linux/spinlock.h:354 [inline]
	 __change_page_attr_set_clr+0x1b0/0x2510 arch/x86/mm/pat/set_memory.c:1658
	 __set_pages_np arch/x86/mm/pat/set_memory.c:2184 [inline]
	 set_direct_map_invalid_noflush+0xd2/0x110 arch/x86/mm/pat/set_memory.c:2189
	 kfence_protect_page arch/x86/include/asm/kfence.h:62 [inline]
	 kfence_protect+0x10e/0x120 mm/kfence/core.c:124
	 kfence_guarded_free+0x380/0x880 mm/kfence/core.c:375
	 rcu_do_batch kernel/rcu/tree.c:2428 [inline]
	 rcu_core+0x5ca/0x1130 kernel/rcu/tree.c:2656
	 __do_softirq+0x1f8/0xb23 kernel/softirq.c:298
	 run_ksoftirqd kernel/softirq.c:652 [inline]
	 run_ksoftirqd+0xcf/0x170 kernel/softirq.c:644
	 smpboot_thread_fn+0x655/0x9e0 kernel/smpboot.c:165
	 kthread+0x3b5/0x4a0 kernel/kthread.c:292
	 ret_from_fork+0x1f/0x30 arch/x86/entry/entry_64.S:294
#20 lore raw

Re: [PATCH v4 02/11] x86, kfence: enable KFENCE for x86

In reply to Marco Elver
Quoted 4 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the x86 architecture. In particular, this implements the required interface in <asm/kfence.h> for setting up the pool and providing helper functions for protecting and unprotecting pages.

[...]

Quoted 1 line
arch/x86/include/asm/kfence.h +0 -0

[...]

Quoted 3 lines
arch/x86/include/asm/kfence.h +3 -0
+/* Protect the given page and flush TLBs. */
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{

[...]

Quoted 1 line

+ flush_tlb_one_kernel(addr);

flush_tlb_one_kernel() -> flush_tlb_one_user() -> __flush_tlb_one_user() -> native_flush_tlb_one_user() only flushes on the local CPU core, not on others. If you want to leave it this way, I think this needs a comment explaining why we're not doing a global flush (locking context / performance overhead / ... ?).

author maintainer
#21 lore raw

PATCH v4 3/11 arm64, kfence: enable KFENCE for ARM64

In reply to Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the arm64 architecture. In particular, this implements the required interface in <asm/kfence.h>. Currently, the arm64 version does not yet use a statically allocated memory pool, at the cost of a pointer load for each is_kfence_address().

---
 arch/arm64/Kconfig              |  1 +
 arch/arm64/include/asm/kfence.h | 39 +++++++++++++++++++++++++++++++++
 arch/arm64/mm/fault.c           |  4 ++++
 3 files changed, 44 insertions(+)
 create mode 100644 arch/arm64/include/asm/kfence.h
arch/arm64/Kconfig +1 -0
index 6d232837cbee..1acc6b2877c3 100644
@@ -132,6 +132,7 @@ config ARM64
 	select HAVE_ARCH_JUMP_LABEL_RELATIVE
 	select HAVE_ARCH_KASAN if !(ARM64_16K_PAGES && ARM64_VA_BITS_48)
 	select HAVE_ARCH_KASAN_SW_TAGS if HAVE_ARCH_KASAN
+	select HAVE_ARCH_KFENCE if (!ARM64_16K_PAGES && !ARM64_64K_PAGES)
 	select HAVE_ARCH_KGDB
 	select HAVE_ARCH_MMAP_RND_BITS
 	select HAVE_ARCH_MMAP_RND_COMPAT_BITS if COMPAT
arch/arm64/include/asm/kfence.h new file +39 -0
new file mode 100644
index 000000000000..608dde80e5ca
@@ -0,0 +1,39 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef __ASM_KFENCE_H
+#define __ASM_KFENCE_H
+
+#include <linux/kfence.h>
+#include <linux/log2.h>
+#include <linux/mm.h>
+
+#include <asm/cacheflush.h>
+
+#define KFENCE_SKIP_ARCH_FAULT_HANDLER "el1_sync"
+
+/*
+ * FIXME: Support HAVE_ARCH_KFENCE_STATIC_POOL: Use the statically allocated
+ * __kfence_pool, to avoid the extra pointer load for is_kfence_address(). By
+ * default, however, we do not have struct pages for static allocations.
+ */
+
+static inline bool arch_kfence_initialize_pool(void)
+{
+	const unsigned int num_pages = ilog2(roundup_pow_of_two(KFENCE_POOL_SIZE / PAGE_SIZE));
+	struct page *pages = alloc_pages(GFP_KERNEL, num_pages);
+
+	if (!pages)
+		return false;
+
+	__kfence_pool = page_address(pages);
+	return true;
+}
+
+static inline bool kfence_protect_page(unsigned long addr, bool protect)
+{
+	set_memory_valid(addr, 1, !protect);
+
+	return true;
+}
+
+#endif /* __ASM_KFENCE_H */
arch/arm64/mm/fault.c +4 -0
index f07333e86c2f..d5b72ecbeeea 100644
@@ -10,6 +10,7 @@
 #include <linux/acpi.h>
 #include <linux/bitfield.h>
 #include <linux/extable.h>
+#include <linux/kfence.h>
 #include <linux/signal.h>
 #include <linux/mm.h>
 #include <linux/hardirq.h>
@@ -310,6 +311,9 @@ static void __do_kernel_fault(unsigned long addr, unsigned int esr,
 	    "Ignoring spurious kernel translation fault at virtual address %016lx\n", addr))
 		return;
 
+	if (kfence_handle_page_fault(addr))
+		return;
+
 	if (is_el1_permission_fault(addr, esr, regs)) {
 		if (esr & ESR_ELx_WNR)
 			msg = "write to read-only memory";
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
#22 lore raw

Re: [PATCH v4 03/11] arm64, kfence: enable KFENCE for ARM64

Quoted 5 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the arm64 architecture. In particular, this implements the required interface in <asm/kfence.h>. Currently, the arm64 version does not yet use a statically allocated memory pool, at the cost of a pointer load for each is_kfence_address().

[...]

Quoted 1 line
arch/arm64/include/asm/kfence.h +0 -0

[...]

arch/arm64/include/asm/kfence.h line 30

Quoted 11 lines
arch/arm64/include/asm/kfence.h +11 -0
+static inline bool arch_kfence_initialize_pool(void)
+{
+       const unsigned int num_pages = ilog2(roundup_pow_of_two(KFENCE_POOL_SIZE / PAGE_SIZE));
+       struct page *pages = alloc_pages(GFP_KERNEL, num_pages);
+
+       if (!pages)
+               return false;
+
+       __kfence_pool = page_address(pages);
+       return true;
+}

If you're going to do "virt_to_page(meta->addr)->slab_cache = cache;" on these pages in kfence_guarded_alloc(), and pass them into kfree(), you'd better mark these pages as non-compound - something like alloc_pages_exact() or split_page() may help. Otherwise, I think when SLUB's kfree() does virt_to_head_page() right at the start, that will return a pointer to the first page of the entire __kfence_pool, and then when it loads page->slab_cache, it gets some random cache and stuff blows up. Kinda surprising that you haven't run into that during your testing, maybe I'm missing something...

Also, this kinda feels like it should be the "generic" version of arch_kfence_initialize_pool() and live in mm/kfence/core.c ?

author maintainer
#23 lore raw

Re: [PATCH v4 03/11] arm64, kfence: enable KFENCE for ARM64

Quoted 23 lines · Jann Horn
Quoted 5 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the arm64 architecture. In particular, this implements the required interface in <asm/kfence.h>. Currently, the arm64 version does not yet use a statically allocated memory pool, at the cost of a pointer load for each is_kfence_address().

[...]

Quoted 1 line
arch/arm64/include/asm/kfence.h +0 -0

[...]

arch/arm64/include/asm/kfence.h line 30

Quoted 11 lines
arch/arm64/include/asm/kfence.h +11 -0
+static inline bool arch_kfence_initialize_pool(void)
+{
+       const unsigned int num_pages = ilog2(roundup_pow_of_two(KFENCE_POOL_SIZE / PAGE_SIZE));
+       struct page *pages = alloc_pages(GFP_KERNEL, num_pages);
+
+       if (!pages)
+               return false;
+
+       __kfence_pool = page_address(pages);
+       return true;
+}

If you're going to do "virt_to_page(meta->addr)->slab_cache = cache;"

Quoted 8 lines

on these pages in kfence_guarded_alloc(), and pass them into kfree(), you'd better mark these pages as non-compound - something like alloc_pages_exact() or split_page() may help. Otherwise, I think when SLUB's kfree() does virt_to_head_page() right at the start, that will return a pointer to the first page of the entire __kfence_pool, and then when it loads page->slab_cache, it gets some random cache and stuff blows up. Kinda surprising that you haven't run into that during your testing, maybe I'm missing something...

I added a WARN_ON() check in kfence_initialize_pool() to check if our pages are compound or not; they are not.

In slub.c, __GFP_COMP is passed to alloc_pages(), which causes them to have a compound head I believe.

Quoted 2 lines

Also, this kinda feels like it should be the "generic" version of arch_kfence_initialize_pool() and live in mm/kfence/core.c ?

Done for v5.

Thanks,
-- Marco

#24 lore raw

Re: [PATCH v4 03/11] arm64, kfence: enable KFENCE for ARM64

Quoted 34 lines · Marco Elver
Quoted 23 lines · Jann Horn
Quoted 5 lines · Marco Elver

Add architecture specific implementation details for KFENCE and enable KFENCE for the arm64 architecture. In particular, this implements the required interface in <asm/kfence.h>. Currently, the arm64 version does not yet use a statically allocated memory pool, at the cost of a pointer load for each is_kfence_address().

[...]

Quoted 1 line
arch/arm64/include/asm/kfence.h +0 -0

[...]

arch/arm64/include/asm/kfence.h line 30

Quoted 11 lines
arch/arm64/include/asm/kfence.h +11 -0
+static inline bool arch_kfence_initialize_pool(void)
+{
+       const unsigned int num_pages = ilog2(roundup_pow_of_two(KFENCE_POOL_SIZE / PAGE_SIZE));
+       struct page *pages = alloc_pages(GFP_KERNEL, num_pages);
+
+       if (!pages)
+               return false;
+
+       __kfence_pool = page_address(pages);
+       return true;
+}

If you're going to do "virt_to_page(meta->addr)->slab_cache = cache;"

Quoted 8 lines

on these pages in kfence_guarded_alloc(), and pass them into kfree(), you'd better mark these pages as non-compound - something like alloc_pages_exact() or split_page() may help. Otherwise, I think when SLUB's kfree() does virt_to_head_page() right at the start, that will return a pointer to the first page of the entire __kfence_pool, and then when it loads page->slab_cache, it gets some random cache and stuff blows up. Kinda surprising that you haven't run into that during your testing, maybe I'm missing something...

Quoted 5 lines

I added a WARN_ON() check in kfence_initialize_pool() to check if our pages are compound or not; they are not.

In slub.c, __GFP_COMP is passed to alloc_pages(), which causes them to have a compound head I believe.

Aah, I mixed up high-order pages and compound pages. Sorry for the noise.

author maintainer
#25 lore raw

PATCH v4 4/11 mm, kfence: insert KFENCE hooks for SLAB

In reply to Marco Elver

From: Alexander Potapenko <[email protected]>

Inserts KFENCE hooks into the SLAB allocator.

To pass the originally requested size to KFENCE, add an argument 'orig_size' to slab_alloc*(). The additional argument is required to preserve the requested original size for kmalloc() allocations, which uses size classes (e.g. an allocation of 272 bytes will return an object of size 512). Therefore, kmem_cache::size does not represent the kmalloc-caller's requested size, and we must introduce the argument 'orig_size' to propagate the originally requested size to KFENCE.

Without the originally requested size, we would not be able to detect out-of-bounds accesses for objects placed at the end of a KFENCE object page if that object is not equal to the kmalloc-size class it was bucketed into.

When KFENCE is disabled, there is no additional overhead, since slab_alloc*() functions are __always_inline.

---
v3:
* Rewrite patch description to clarify need for 'orig_size' [reported by Christopher Lameter].

---
 mm/slab.c        | 46 ++++++++++++++++++++++++++++++++++------------
 mm/slab_common.c |  6 +++++-
 2 files changed, 39 insertions(+), 13 deletions(-)
mm/slab.c +34 -12
index 3160dff6fd76..30aba06ae02b 100644
@@ -100,6 +100,7 @@
 #include	<linux/seq_file.h>
 #include	<linux/notifier.h>
 #include	<linux/kallsyms.h>
+#include	<linux/kfence.h>
 #include	<linux/cpu.h>
 #include	<linux/sysctl.h>
 #include	<linux/module.h>
@@ -3206,7 +3207,7 @@ static void *____cache_alloc_node(struct kmem_cache *cachep, gfp_t flags,
 }
 
 static __always_inline void *
-slab_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid,
+slab_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid, size_t orig_size,
 		   unsigned long caller)
 {
 	unsigned long save_flags;
@@ -3219,6 +3220,10 @@ slab_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid,
 	if (unlikely(!cachep))
 		return NULL;
 
+	ptr = kfence_alloc(cachep, orig_size, flags);
+	if (unlikely(ptr))
+		goto out_hooks;
+
 	cache_alloc_debugcheck_before(cachep, flags);
 	local_irq_save(save_flags);
 
@@ -3251,6 +3256,7 @@ slab_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid,
 	if (unlikely(slab_want_init_on_alloc(flags, cachep)) && ptr)
 		memset(ptr, 0, cachep->object_size);
 
+out_hooks:
 	slab_post_alloc_hook(cachep, objcg, flags, 1, &ptr);
 	return ptr;
 }
@@ -3288,7 +3294,7 @@ __do_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
 #endif /* CONFIG_NUMA */
 
 static __always_inline void *
-slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
+slab_alloc(struct kmem_cache *cachep, gfp_t flags, size_t orig_size, unsigned long caller)
 {
 	unsigned long save_flags;
 	void *objp;
@@ -3299,6 +3305,10 @@ slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
 	if (unlikely(!cachep))
 		return NULL;
 
+	objp = kfence_alloc(cachep, orig_size, flags);
+	if (unlikely(objp))
+		goto leave;
+
 	cache_alloc_debugcheck_before(cachep, flags);
 	local_irq_save(save_flags);
 	objp = __do_cache_alloc(cachep, flags);
@@ -3309,6 +3319,7 @@ slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
 	if (unlikely(slab_want_init_on_alloc(flags, cachep)) && objp)
 		memset(objp, 0, cachep->object_size);
 
+leave:
 	slab_post_alloc_hook(cachep, objcg, flags, 1, &objp);
 	return objp;
 }
@@ -3414,6 +3425,11 @@ static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
 static __always_inline void __cache_free(struct kmem_cache *cachep, void *objp,
 					 unsigned long caller)
 {
+	if (kfence_free(objp)) {
+		kmemleak_free_recursive(objp, cachep->flags);
+		return;
+	}
+
 	/* Put the object into the quarantine, don't touch it for now. */
 	if (kasan_slab_free(cachep, objp, _RET_IP_))
 		return;
@@ -3479,7 +3495,7 @@ void ___cache_free(struct kmem_cache *cachep, void *objp,
  */
 void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
 {
-	void *ret = slab_alloc(cachep, flags, _RET_IP_);
+	void *ret = slab_alloc(cachep, flags, cachep->object_size, _RET_IP_);
 
 	trace_kmem_cache_alloc(_RET_IP_, ret,
 			       cachep->object_size, cachep->size, flags);
@@ -3512,7 +3528,7 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 
 	local_irq_disable();
 	for (i = 0; i < size; i++) {
-		void *objp = __do_cache_alloc(s, flags);
+		void *objp = kfence_alloc(s, s->object_size, flags) ?: __do_cache_alloc(s, flags);
 
 		if (unlikely(!objp))
 			goto error;
@@ -3545,7 +3561,7 @@ kmem_cache_alloc_trace(struct kmem_cache *cachep, gfp_t flags, size_t size)
 {
 	void *ret;
 
-	ret = slab_alloc(cachep, flags, _RET_IP_);
+	ret = slab_alloc(cachep, flags, size, _RET_IP_);
 
 	ret = kasan_kmalloc(cachep, ret, size, flags);
 	trace_kmalloc(_RET_IP_, ret,
@@ -3571,7 +3587,7 @@ EXPORT_SYMBOL(kmem_cache_alloc_trace);
  */
 void *kmem_cache_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid)
 {
-	void *ret = slab_alloc_node(cachep, flags, nodeid, _RET_IP_);
+	void *ret = slab_alloc_node(cachep, flags, nodeid, cachep->object_size, _RET_IP_);
 
 	trace_kmem_cache_alloc_node(_RET_IP_, ret,
 				    cachep->object_size, cachep->size,
@@ -3589,7 +3605,7 @@ void *kmem_cache_alloc_node_trace(struct kmem_cache *cachep,
 {
 	void *ret;
 
-	ret = slab_alloc_node(cachep, flags, nodeid, _RET_IP_);
+	ret = slab_alloc_node(cachep, flags, nodeid, size, _RET_IP_);
 
 	ret = kasan_kmalloc(cachep, ret, size, flags);
 	trace_kmalloc_node(_RET_IP_, ret,
@@ -3650,7 +3666,7 @@ static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
 	cachep = kmalloc_slab(size, flags);
 	if (unlikely(ZERO_OR_NULL_PTR(cachep)))
 		return cachep;
-	ret = slab_alloc(cachep, flags, caller);
+	ret = slab_alloc(cachep, flags, size, caller);
 
 	ret = kasan_kmalloc(cachep, ret, size, flags);
 	trace_kmalloc(caller, ret,
@@ -4138,18 +4154,24 @@ void __check_heap_object(const void *ptr, unsigned long n, struct page *page,
 			 bool to_user)
 {
 	struct kmem_cache *cachep;
-	unsigned int objnr;
+	unsigned int objnr = 0;
 	unsigned long offset;
+	bool is_kfence = is_kfence_address(ptr);
 
 	ptr = kasan_reset_tag(ptr);
 
 	/* Find and validate object. */
 	cachep = page->slab_cache;
-	objnr = obj_to_index(cachep, page, (void *)ptr);
-	BUG_ON(objnr >= cachep->num);
+	if (!is_kfence) {
+		objnr = obj_to_index(cachep, page, (void *)ptr);
+		BUG_ON(objnr >= cachep->num);
+	}
 
 	/* Find offset within object. */
-	offset = ptr - index_to_obj(cachep, page, objnr) - obj_offset(cachep);
+	if (is_kfence_address(ptr))
+		offset = ptr - kfence_object_start(ptr);
+	else
+		offset = ptr - index_to_obj(cachep, page, objnr) - obj_offset(cachep);
 
 	/* Allow address range falling entirely within usercopy region. */
 	if (offset >= cachep->useroffset &&
mm/slab_common.c +5 -1
index f9ccd5dc13f3..6e35e273681a 100644
@@ -12,6 +12,7 @@
 #include <linux/memory.h>
 #include <linux/cache.h>
 #include <linux/compiler.h>
+#include <linux/kfence.h>
 #include <linux/module.h>
 #include <linux/cpu.h>
 #include <linux/uaccess.h>
@@ -448,6 +449,9 @@ static int shutdown_cache(struct kmem_cache *s)
 	/* free asan quarantined objects */
 	kasan_cache_shutdown(s);
 
+	if (!kfence_shutdown_cache(s))
+		return -EBUSY;
+
 	if (__kmem_cache_shutdown(s) != 0)
 		return -EBUSY;
 
@@ -1171,7 +1175,7 @@ size_t ksize(const void *objp)
 	if (unlikely(ZERO_OR_NULL_PTR(objp)) || !__kasan_check_read(objp, 1))
 		return 0;
 
-	size = __ksize(objp);
+	size = kfence_ksize(objp) ?: __ksize(objp);
 	/*
 	 * We assume that ksize callers could use whole allocated area,
 	 * so we need to unpoison this area.
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#26 lore raw

PATCH v4 5/11 mm, kfence: insert KFENCE hooks for SLUB

In reply to Marco Elver

From: Alexander Potapenko <[email protected]>

Inserts KFENCE hooks into the SLUB allocator.

To pass the originally requested size to KFENCE, add an argument 'orig_size' to slab_alloc*(). The additional argument is required to preserve the requested original size for kmalloc() allocations, which uses size classes (e.g. an allocation of 272 bytes will return an object of size 512). Therefore, kmem_cache::size does not represent the kmalloc-caller's requested size, and we must introduce the argument 'orig_size' to propagate the originally requested size to KFENCE.

Without the originally requested size, we would not be able to detect out-of-bounds accesses for objects placed at the end of a KFENCE object page if that object is not equal to the kmalloc-size class it was bucketed into.

When KFENCE is disabled, there is no additional overhead, since slab_alloc*() functions are __always_inline.

---
v3:
* Rewrite patch description to clarify need for 'orig_size' [reported by Christopher Lameter].

---
 mm/slub.c | 72 ++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 53 insertions(+), 19 deletions(-)
mm/slub.c +53 -19
index d4177aecedf6..5c5a13a7857c 100644
@@ -27,6 +27,7 @@
 #include <linux/ctype.h>
 #include <linux/debugobjects.h>
 #include <linux/kallsyms.h>
+#include <linux/kfence.h>
 #include <linux/memory.h>
 #include <linux/math64.h>
 #include <linux/fault-inject.h>
@@ -1557,6 +1558,11 @@ static inline bool slab_free_freelist_hook(struct kmem_cache *s,
 	void *old_tail = *tail ? *tail : *head;
 	int rsize;
 
+	if (is_kfence_address(next)) {
+		slab_free_hook(s, next);
+		return true;
+	}
+
 	/* Head and tail of the reconstructed freelist */
 	*head = NULL;
 	*tail = NULL;
@@ -2660,7 +2666,8 @@ static inline void *get_freelist(struct kmem_cache *s, struct page *page)
  * already disabled (which is the case for bulk allocation).
  */
 static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
-			  unsigned long addr, struct kmem_cache_cpu *c)
+			  unsigned long addr, struct kmem_cache_cpu *c,
+			  size_t orig_size)
 {
 	void *freelist;
 	struct page *page;
@@ -2763,7 +2770,8 @@ static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
  * cpu changes by refetching the per cpu area pointer.
  */
 static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
-			  unsigned long addr, struct kmem_cache_cpu *c)
+			  unsigned long addr, struct kmem_cache_cpu *c,
+			  size_t orig_size)
 {
 	void *p;
 	unsigned long flags;
@@ -2778,7 +2786,7 @@ static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
 	c = this_cpu_ptr(s->cpu_slab);
 #endif
 
-	p = ___slab_alloc(s, gfpflags, node, addr, c);
+	p = ___slab_alloc(s, gfpflags, node, addr, c, orig_size);
 	local_irq_restore(flags);
 	return p;
 }
@@ -2805,7 +2813,7 @@ static __always_inline void maybe_wipe_obj_freeptr(struct kmem_cache *s,
  * Otherwise we can simply pick the next object from the lockless free list.
  */
 static __always_inline void *slab_alloc_node(struct kmem_cache *s,
-		gfp_t gfpflags, int node, unsigned long addr)
+		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
 {
 	void *object;
 	struct kmem_cache_cpu *c;
@@ -2816,6 +2824,11 @@ static __always_inline void *slab_alloc_node(struct kmem_cache *s,
 	s = slab_pre_alloc_hook(s, &objcg, 1, gfpflags);
 	if (!s)
 		return NULL;
+
+	object = kfence_alloc(s, orig_size, gfpflags);
+	if (unlikely(object))
+		goto out;
+
 redo:
 	/*
 	 * Must read kmem_cache cpu data via this cpu ptr. Preemption is
@@ -2853,7 +2866,7 @@ static __always_inline void *slab_alloc_node(struct kmem_cache *s,
 	object = c->freelist;
 	page = c->page;
 	if (unlikely(!object || !node_match(page, node))) {
-		object = __slab_alloc(s, gfpflags, node, addr, c);
+		object = __slab_alloc(s, gfpflags, node, addr, c, orig_size);
 		stat(s, ALLOC_SLOWPATH);
 	} else {
 		void *next_object = get_freepointer_safe(s, object);
@@ -2889,20 +2902,21 @@ static __always_inline void *slab_alloc_node(struct kmem_cache *s,
 	if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
 		memset(object, 0, s->object_size);
 
+out:
 	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object);
 
 	return object;
 }
 
 static __always_inline void *slab_alloc(struct kmem_cache *s,
-		gfp_t gfpflags, unsigned long addr)
+		gfp_t gfpflags, unsigned long addr, size_t orig_size)
 {
-	return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
+	return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr, orig_size);
 }
 
 void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
 {
-	void *ret = slab_alloc(s, gfpflags, _RET_IP_);
+	void *ret = slab_alloc(s, gfpflags, _RET_IP_, s->object_size);
 
 	trace_kmem_cache_alloc(_RET_IP_, ret, s->object_size,
 				s->size, gfpflags);
@@ -2914,7 +2928,7 @@ EXPORT_SYMBOL(kmem_cache_alloc);
 #ifdef CONFIG_TRACING
 void *kmem_cache_alloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
 {
-	void *ret = slab_alloc(s, gfpflags, _RET_IP_);
+	void *ret = slab_alloc(s, gfpflags, _RET_IP_, size);
 	trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags);
 	ret = kasan_kmalloc(s, ret, size, gfpflags);
 	return ret;
@@ -2925,7 +2939,7 @@ EXPORT_SYMBOL(kmem_cache_alloc_trace);
 #ifdef CONFIG_NUMA
 void *kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node)
 {
-	void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_);
+	void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_, s->object_size);
 
 	trace_kmem_cache_alloc_node(_RET_IP_, ret,
 				    s->object_size, s->size, gfpflags, node);
@@ -2939,7 +2953,7 @@ void *kmem_cache_alloc_node_trace(struct kmem_cache *s,
 				    gfp_t gfpflags,
 				    int node, size_t size)
 {
-	void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_);
+	void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_, size);
 
 	trace_kmalloc_node(_RET_IP_, ret,
 			   size, s->size, gfpflags, node);
@@ -2973,6 +2987,9 @@ static void __slab_free(struct kmem_cache *s, struct page *page,
 
 	stat(s, FREE_SLOWPATH);
 
+	if (kfence_free(head))
+		return;
+
 	if (kmem_cache_debug(s) &&
 	    !free_debug_processing(s, page, head, tail, cnt, addr))
 		return;
@@ -3216,6 +3233,13 @@ int build_detached_freelist(struct kmem_cache *s, size_t size,
 		df->s = cache_from_obj(s, object); /* Support for memcg */
 	}
 
+	if (is_kfence_address(object)) {
+		slab_free_hook(df->s, object);
+		WARN_ON(!kfence_free(object));
+		p[size] = NULL; /* mark object processed */
+		return size;
+	}
+
 	/* Start new detached freelist */
 	df->page = page;
 	set_freepointer(df->s, object, NULL);
@@ -3290,8 +3314,14 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 	c = this_cpu_ptr(s->cpu_slab);
 
 	for (i = 0; i < size; i++) {
-		void *object = c->freelist;
+		void *object = kfence_alloc(s, s->object_size, flags);
 
+		if (unlikely(object)) {
+			p[i] = object;
+			continue;
+		}
+
+		object = c->freelist;
 		if (unlikely(!object)) {
 			/*
 			 * We may have removed an object from c->freelist using
@@ -3307,7 +3337,7 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
 			 * of re-populating per CPU c->freelist
 			 */
 			p[i] = ___slab_alloc(s, flags, NUMA_NO_NODE,
-					    _RET_IP_, c);
+					    _RET_IP_, c, size);
 			if (unlikely(!p[i]))
 				goto error;
 
@@ -3962,7 +3992,7 @@ void *__kmalloc(size_t size, gfp_t flags)
 	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
-	ret = slab_alloc(s, flags, _RET_IP_);
+	ret = slab_alloc(s, flags, _RET_IP_, size);
 
 	trace_kmalloc(_RET_IP_, ret, size, s->size, flags);
 
@@ -4010,7 +4040,7 @@ void *__kmalloc_node(size_t size, gfp_t flags, int node)
 	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
-	ret = slab_alloc_node(s, flags, node, _RET_IP_);
+	ret = slab_alloc_node(s, flags, node, _RET_IP_, size);
 
 	trace_kmalloc_node(_RET_IP_, ret, size, s->size, flags, node);
 
@@ -4036,6 +4066,7 @@ void __check_heap_object(const void *ptr, unsigned long n, struct page *page,
 	struct kmem_cache *s;
 	unsigned int offset;
 	size_t object_size;
+	bool is_kfence = is_kfence_address(ptr);
 
 	ptr = kasan_reset_tag(ptr);
 
@@ -4048,10 +4079,13 @@ void __check_heap_object(const void *ptr, unsigned long n, struct page *page,
 			       to_user, 0, n);
 
 	/* Find offset within object. */
-	offset = (ptr - page_address(page)) % s->size;
+	if (is_kfence)
+		offset = ptr - kfence_object_start(ptr);
+	else
+		offset = (ptr - page_address(page)) % s->size;
 
 	/* Adjust for redzone and reject if within the redzone. */
-	if (kmem_cache_debug_flags(s, SLAB_RED_ZONE)) {
+	if (!is_kfence && kmem_cache_debug_flags(s, SLAB_RED_ZONE)) {
 		if (offset < s->red_left_pad)
 			usercopy_abort("SLUB object in left red zone",
 				       s->name, to_user, offset, n);
@@ -4460,7 +4494,7 @@ void *__kmalloc_track_caller(size_t size, gfp_t gfpflags, unsigned long caller)
 	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
-	ret = slab_alloc(s, gfpflags, caller);
+	ret = slab_alloc(s, gfpflags, caller, size);
 
 	/* Honor the call site pointer we received. */
 	trace_kmalloc(caller, ret, size, s->size, gfpflags);
@@ -4491,7 +4525,7 @@ void *__kmalloc_node_track_caller(size_t size, gfp_t gfpflags,
 	if (unlikely(ZERO_OR_NULL_PTR(s)))
 		return s;
 
-	ret = slab_alloc_node(s, gfpflags, node, caller);
+	ret = slab_alloc_node(s, gfpflags, node, caller, size);
 
 	/* Honor the call site pointer we received. */
 	trace_kmalloc_node(caller, ret, size, s->size, gfpflags, node);
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
#27 lore raw

Re: [PATCH v4 05/11] mm, kfence: insert KFENCE hooks for SLUB

Quoted 1 line · Marco Elver

Inserts KFENCE hooks into the SLUB allocator.

[...]

Quoted 1 line
mm/slub.c +0 -0

[...]

mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 3317

Quoted 6 lines
mm/slub.c +1 -1
@@ -3290,8 +3314,14 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
        c = this_cpu_ptr(s->cpu_slab);
 
        for (i = 0; i < size; i++) {
-               void *object = c->freelist;
+               void *object = kfence_alloc(s, s->object_size, flags);

kfence_alloc() will invoke ->ctor() callbacks if the current slab has them. Is it fine to invoke such callbacks from here, where we're in the middle of a section that disables interrupts to protect against concurrent freelist changes? If someone decides to be extra smart and uses a kmem_cache with a ->ctor that can allocate memory from the same kmem_cache, or something along those lines, this could lead to corruption of the SLUB freelist. But I'm not sure whether that can happen in practice.

Still, it might be nicer if you could code this to behave like a fastpath miss: Update c->tid, turn interrupts back on (___slab_alloc() will also do that if it has to call into the page allocator), then let kfence do the actual allocation in a more normal context, then turn interrupts back off and go on. If that's not too complicated?

Maybe Christoph Lameter has opinions on whether this is necessary... it admittedly is fairly theoretical.

Quoted 9 lines
mm/slub.c +6 -0
+               if (unlikely(object)) {
+                       p[i] = object;
+                       continue;
+               }
+
+               object = c->freelist;
                if (unlikely(!object)) {
                        /*
                         * We may have removed an object from c->freelist using
#28 lore raw

Re: [PATCH v4 05/11] mm, kfence: insert KFENCE hooks for SLUB

Quoted 9 lines · Jann Horn
Quoted 1 line · Marco Elver

Inserts KFENCE hooks into the SLUB allocator.

[...]

Quoted 1 line
mm/slub.c +0 -0

[...]

Quoted 3 lines
mm/slub.c +0 -0
@@ -3290,8 +3314,14 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size,
        c = this_cpu_ptr(s->cpu_slab);
 
Quoted 12 lines

mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 3317

Quoted 3 lines
mm/slub.c +1 -1
        for (i = 0; i < size; i++) {
-               void *object = c->freelist;
+               void *object = kfence_alloc(s, s->object_size, flags);

kfence_alloc() will invoke ->ctor() callbacks if the current slab has them. Is it fine to invoke such callbacks from here, where we're in the middle of a section that disables interrupts to protect against concurrent freelist changes? If someone decides to be extra smart and uses a kmem_cache with a ->ctor that can allocate memory from the same kmem_cache, or something along those lines, this could lead to corruption of the SLUB freelist. But I'm not sure whether that can happen in practice.

From cache_init_objs_debug() in mm/slab.c:

/*
* Constructors are not allowed to allocate memory from the same
* cache which they are a constructor for. Otherwise, deadlock.
* They must also be threaded.
*/

So, no, it is not allowed to allocate from the same cache in the constructor.

Quoted 6 lines

Still, it might be nicer if you could code this to behave like a fastpath miss: Update c->tid, turn interrupts back on (___slab_alloc() will also do that if it has to call into the page allocator), then let kfence do the actual allocation in a more normal context, then turn interrupts back off and go on. If that's not too complicated?

Quoted 12 lines

Maybe Christoph Lameter has opinions on whether this is necessary... it admittedly is fairly theoretical.

Quoted 9 lines
mm/slub.c +6 -0
+               if (unlikely(object)) {
+                       p[i] = object;
+                       continue;
+               }
+
+               object = c->freelist;
                if (unlikely(!object)) {
                        /*
                         * We may have removed an object from c->freelist using

--
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado Registergericht und -nummer: Hamburg, HRB 86891 Sitz der Gesellschaft: Hamburg

author maintainer
#29 lore raw

PATCH v4 6/11 kfence, kasan: make KFENCE compatible with KASAN

In reply to Marco Elver

From: Alexander Potapenko <[email protected]>

We make KFENCE compatible with KASAN for testing KFENCE itself. In particular, KASAN helps to catch any potential corruptions to KFENCE state, or other corruptions that may be a result of freepointer corruptions in the main allocators.

To indicate that the combination of the two is generally discouraged, CONFIG_EXPERT=y should be set. It also gives us the nice property that KFENCE will be build-tested by allyesconfig builds.

---
 lib/Kconfig.kfence | 2 +-
 mm/kasan/common.c  | 7 +++++++
 2 files changed, 8 insertions(+), 1 deletion(-)
lib/Kconfig.kfence +1 -1
index 4c2ea1c722de..6825c1c07a10 100644
@@ -10,7 +10,7 @@ config HAVE_ARCH_KFENCE_STATIC_POOL
 
 menuconfig KFENCE
 	bool "KFENCE: low-overhead sampling-based memory safety error detector"
-	depends on HAVE_ARCH_KFENCE && !KASAN && (SLAB || SLUB)
+	depends on HAVE_ARCH_KFENCE && (!KASAN || EXPERT) && (SLAB || SLUB)
 	depends on JUMP_LABEL # To ensure performance, require jump labels
 	select STACKTRACE
 	help
mm/kasan/common.c +7 -0
index 950fd372a07e..f5c49f0fdeff 100644
@@ -18,6 +18,7 @@
 #include <linux/init.h>
 #include <linux/kasan.h>
 #include <linux/kernel.h>
+#include <linux/kfence.h>
 #include <linux/kmemleak.h>
 #include <linux/linkage.h>
 #include <linux/memblock.h>
@@ -396,6 +397,9 @@ static bool __kasan_slab_free(struct kmem_cache *cache, void *object,
 	tagged_object = object;
 	object = reset_tag(object);
 
+	if (is_kfence_address(object))
+		return false;
+
 	if (unlikely(nearest_obj(cache, virt_to_head_page(object), object) !=
 	    object)) {
 		kasan_report_invalid_free(tagged_object, ip);
@@ -444,6 +448,9 @@ static void *__kasan_kmalloc(struct kmem_cache *cache, const void *object,
 	if (unlikely(object == NULL))
 		return NULL;
 
+	if (is_kfence_address(object))
+		return (void *)object;
+
 	redzone_start = round_up((unsigned long)(object + size),
 				KASAN_SHADOW_SCALE_SIZE);
 	redzone_end = round_up((unsigned long)object + cache->object_size,
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#30 lore raw

PATCH v4 7/11 kfence, kmemleak: make KFENCE compatible with KMEMLEAK

In reply to Marco Elver

From: Alexander Potapenko <[email protected]>

Add compatibility with KMEMLEAK, by making KMEMLEAK aware of the KFENCE memory pool. This allows building debug kernels with both enabled, which also helped in debugging KFENCE.

---
v2:
* Rework using delete_object_part() [suggested by Catalin Marinas].

---
 mm/kmemleak.c | 6 ++++++
 1 file changed, 6 insertions(+)
mm/kmemleak.c +6 -0
index 5e252d91eb14..feff16068e8e 100644
@@ -97,6 +97,7 @@
 #include <linux/atomic.h>
 
 #include <linux/kasan.h>
+#include <linux/kfence.h>
 #include <linux/kmemleak.h>
 #include <linux/memory_hotplug.h>
 
@@ -1948,6 +1949,11 @@ void __init kmemleak_init(void)
 		      KMEMLEAK_GREY, GFP_ATOMIC);
 	create_object((unsigned long)__bss_start, __bss_stop - __bss_start,
 		      KMEMLEAK_GREY, GFP_ATOMIC);
+#if defined(CONFIG_KFENCE) && defined(CONFIG_HAVE_ARCH_KFENCE_STATIC_POOL)
+	/* KFENCE objects are located in .bss, which may confuse kmemleak. Skip them. */
+	delete_object_part((unsigned long)__kfence_pool, KFENCE_POOL_SIZE);
+#endif
+
 	/* only register .data..ro_after_init if not within .data */
 	if (&__start_ro_after_init < &_sdata || &__end_ro_after_init > &_edata)
 		create_object((unsigned long)__start_ro_after_init,
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#31 lore raw

PATCH v4 8/11 kfence, lockdep: make KFENCE compatible with lockdep

In reply to Marco Elver

Lockdep checks that dynamic key registration is only performed on keys that are not static objects. With KFENCE, it is possible that such a dynamically allocated key is a KFENCE object which may, however, be allocated from a static memory pool (if HAVE_ARCH_KFENCE_STATIC_POOL).

Therefore, ignore KFENCE-allocated objects in static_obj().

---
 kernel/locking/lockdep.c | 8 ++++++++
 1 file changed, 8 insertions(+)
kernel/locking/lockdep.c +8 -0
index 54b74fabf40c..0cf5d5ecbd31 100644
@@ -38,6 +38,7 @@
 #include <linux/seq_file.h>
 #include <linux/spinlock.h>
 #include <linux/kallsyms.h>
+#include <linux/kfence.h>
 #include <linux/interrupt.h>
 #include <linux/stacktrace.h>
 #include <linux/debug_locks.h>
@@ -755,6 +756,13 @@ static int static_obj(const void *obj)
 	if (arch_is_kernel_initmem_freed(addr))
 		return 0;
 
+	/*
+	 * KFENCE objects may be allocated from a static memory pool, but are
+	 * not actually static objects.
+	 */
+	if (is_kfence_address(obj))
+		return 0;
+
 	/*
 	 * static variable?
 	 */
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#32 lore raw

PATCH v4 9/11 kfence, Documentation: add KFENCE documentation

In reply to Marco Elver

Add KFENCE documentation in dev-tools/kfence.rst, and add to index.

---
v3:
* Re-introduce reference to Documentation/dev-tools/kfence.rst.

v2:
* Many clarifications based on comments from Andrey Konovalov.
* Document CONFIG_KFENCE_SAMPLE_INTERVAL=0 usage.
* Make use-cases between KASAN and KFENCE clearer.
* Be clearer about the fact the pool is fixed size.
* Update based on reporting changes.
* Explicitly mention max supported allocation size is PAGE_SIZE.

---
 Documentation/dev-tools/index.rst  |   1 +
 Documentation/dev-tools/kfence.rst | 291 +++++++++++++++++++++++++++++
 lib/Kconfig.kfence                 |   2 +
 3 files changed, 294 insertions(+)
 create mode 100644 Documentation/dev-tools/kfence.rst
Documentation/dev-tools/index.rst +1 -0
index f7809c7b1ba9..1b1cf4f5c9d9 100644
@@ -22,6 +22,7 @@ whole; patches welcome!
    ubsan
    kmemleak
    kcsan
+   kfence
    gdb-kernel-debugging
    kgdb
    kselftest
Documentation/dev-tools/kfence.rst new file +291 -0

291 lines not on this page · raw message

lib/Kconfig.kfence +2 -0
index 6825c1c07a10..872bcbdd8cc4 100644
@@ -19,6 +19,8 @@ menuconfig KFENCE
 	  to have negligible cost to permit enabling it in production
 	  environments.
 
+	  See <file:Documentation/dev-tools/kfence.rst> for more details.
+
 	  Note that, KFENCE is not a substitute for explicit testing with tools
 	  such as KASAN. KFENCE can detect a subset of bugs that KASAN can
 	  detect, albeit at very different performance profiles. If you can
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#33 lore raw

PATCH v4 10/11 kfence: add test suite

In reply to Marco Elver

Add KFENCE test suite, testing various error detection scenarios. Makes use of KUnit for test organization. Since KFENCE's interface to obtain error reports is via the console, the test verifies that KFENCE outputs expected reports to the console.

---
v4:
* Clarify RCU test comment [reported by Paul E. McKenney].

v3:
* Lower line buffer size to avoid warnings of using more than 1024 bytes stack usage [reported by kernel test robot <[email protected]>].

v2:
* Update for shortened memory corruption report.

---
 lib/Kconfig.kfence      |  13 +
 mm/kfence/Makefile      |   3 +
 mm/kfence/kfence_test.c | 783 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 799 insertions(+)
 create mode 100644 mm/kfence/kfence_test.c
lib/Kconfig.kfence +13 -0
index 872bcbdd8cc4..46d9b6693abb 100644
@@ -62,4 +62,17 @@ config KFENCE_STRESS_TEST_FAULTS
 
 	  The option is only to test KFENCE; set to 0 if you are unsure.
 
+config KFENCE_KUNIT_TEST
+	tristate "KFENCE integration test suite" if !KUNIT_ALL_TESTS
+	default KUNIT_ALL_TESTS
+	depends on TRACEPOINTS && KUNIT
+	help
+	  Test suite for KFENCE, testing various error detection scenarios with
+	  various allocation types, and checking that reports are correctly
+	  output to console.
+
+	  Say Y here if you want the test to be built into the kernel and run
+	  during boot; say M if you want the test to build as a module; say N
+	  if you are unsure.
+
 endif # KFENCE
mm/kfence/Makefile +3 -0
index d991e9a349f0..6872cd5e5390 100644
@@ -1,3 +1,6 @@
 # SPDX-License-Identifier: GPL-2.0
 
 obj-$(CONFIG_KFENCE) := core.o report.o
+
+CFLAGS_kfence_test.o := -g -fno-omit-frame-pointer -fno-optimize-sibling-calls
+obj-$(CONFIG_KFENCE_KUNIT_TEST) += kfence_test.o
mm/kfence/kfence_test.c new file +783 -0

783 lines not on this page · raw message

Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
author maintainer
#34 lore raw

PATCH v4 11/11 MAINTAINERS: Add entry for KFENCE

In reply to Marco Elver

Add entry for KFENCE maintainers.

---
v4:
* Split out from first patch.

---
 MAINTAINERS | 11 +++++++++++
 1 file changed, 11 insertions(+)
MAINTAINERS +11 -0
index b5cfab015bd6..863899ed9a29 100644
@@ -9673,6 +9673,17 @@ F:	include/linux/keyctl.h
 F:	include/uapi/linux/keyctl.h
 F:	security/keys/
 
+KFENCE
+M:	Alexander Potapenko <[email protected]>
+M:	Marco Elver <[email protected]>
+R:	Dmitry Vyukov <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	Documentation/dev-tools/kfence.rst
+F:	include/linux/kfence.h
+F:	lib/Kconfig.kfence
+F:	mm/kfence/
+
 KFIFO
 M:	Stefani Seibold <[email protected]>
 S:	Maintained
Signature · 1 line
2.28.0.709.gb0816b6eb0-goog
Reviewed-by on v4 11/11
#35 lore raw

Re: [PATCH v4 11/11] MAINTAINERS: Add entry for KFENCE

Quoted 6 lines · On Tue, 29 Sep 2020 15:38:14 +0200 Marco Elver <[email protected]> wrote:

Add entry for KFENCE maintainers.

Thanks,
SeongJae Park