All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-01  6:58 Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
                   ` (4 more replies)
  0 siblings, 5 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

Currently, vmalloc space is backed by the early shadow page. This
means that kasan is incompatible with VMAP_STACK.

This series provides a mechanism to back vmalloc space with real,
dynamically allocated memory. I have only wired up x86, because that's
the only currently supported arch I can work with easily, but it's
very easy to wire up other architectures, and it appears that there is
some work-in-progress code to do this on arm64 and s390.

This has been discussed before in the context of VMAP_STACK:
 - https://bugzilla.kernel.org/show_bug.cgi?id=202009
 - https://lkml.org/lkml/2018/7/22/198
 - https://lkml.org/lkml/2019/7/19/822

In terms of implementation details:

Most mappings in vmalloc space are small, requiring less than a full
page of shadow space. Allocating a full shadow page per mapping would
therefore be wasteful. Furthermore, to ensure that different mappings
use different shadow pages, mappings would have to be aligned to
KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.

Instead, share backing space across multiple mappings. Allocate a
backing page when a mapping in vmalloc space uses a particular page of
the shadow region. This page can be shared by other vmalloc mappings
later on.

We hook in to the vmap infrastructure to lazily clean up unused shadow
memory.

v1: https://lore.kernel.org/linux-mm/20190725055503.19507-1-dja@axtens.net/
v2: https://lore.kernel.org/linux-mm/20190729142108.23343-1-dja@axtens.net/
 Address review comments:
 - Patch 1: use kasan_unpoison_shadow's built-in handling of
            ranges that do not align to a full shadow byte
 - Patch 3: prepopulate pgds rather than faulting things in
v3: https://lore.kernel.org/linux-mm/20190731071550.31814-1-dja@axtens.net/
 Address comments from Mark Rutland:
 - kasan_populate_vmalloc is a better name
 - handle concurrency correctly
 - various nits and cleanups
 - relax module alignment in KASAN_VMALLOC case
v4: https://lore.kernel.org/linux-mm/20190815001636.12235-1-dja@axtens.net/
 Changes to patch 1 only:
 - Integrate Mark's rework, thanks Mark!
 - handle the case where kasan_populate_shadow might fail
 - poision shadow on free, allowing the alloc path to just
     unpoision memory that it uses
v5: https://lore.kernel.org/linux-mm/20190830003821.10737-1-dja@axtens.net/
 Address comments from Christophe Leroy:
 - Fix some issues with my descriptions in commit messages and docs
 - Dynamically free unused shadow pages by hooking into the vmap book-keeping
 - Split out the test into a separate patch
 - Optional patch to track the number of pages allocated
 - minor checkpatch cleanups
v6: https://lore.kernel.org/linux-mm/20190902112028.23773-1-dja@axtens.net/
 Properly guard freeing pages in patch 1, drop debugging code.
v7: https://lore.kernel.org/linux-mm/20190903145536.3390-1-dja@axtens.net/
    Add a TLB flush on freeing, thanks Mark Rutland.
    Explain more clearly how I think freeing is concurrency-safe.
v8: rename kasan_vmalloc/shadow_pages to kasan/vmalloc_shadow_pages

Daniel Axtens (5):
  kasan: support backing vmalloc space with real shadow memory
  kasan: add test for vmalloc
  fork: support VMAP_STACK with KASAN_VMALLOC
  x86/kasan: support KASAN_VMALLOC
  kasan debug: track pages allocated for vmalloc shadow

 Documentation/dev-tools/kasan.rst |  63 ++++++++
 arch/Kconfig                      |   9 +-
 arch/x86/Kconfig                  |   1 +
 arch/x86/mm/kasan_init_64.c       |  60 ++++++++
 include/linux/kasan.h             |  31 ++++
 include/linux/moduleloader.h      |   2 +-
 include/linux/vmalloc.h           |  12 ++
 kernel/fork.c                     |   4 +
 lib/Kconfig.kasan                 |  16 +++
 lib/test_kasan.c                  |  26 ++++
 mm/kasan/common.c                 | 230 ++++++++++++++++++++++++++++++
 mm/kasan/generic_report.c         |   3 +
 mm/kasan/kasan.h                  |   1 +
 mm/vmalloc.c                      |  45 +++++-
 14 files changed, 497 insertions(+), 6 deletions(-)

-- 
2.20.1


^ permalink raw reply	[flat|nested] 38+ messages in thread

* [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
@ 2019-10-01  6:58 ` Daniel Axtens
  2019-10-01 10:17     ` Uladzislau Rezki
                     ` (3 more replies)
  2019-10-01  6:58 ` [PATCH v8 2/5] kasan: add test for vmalloc Daniel Axtens
                   ` (3 subsequent siblings)
  4 siblings, 4 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

Hook into vmalloc and vmap, and dynamically allocate real shadow
memory to back the mappings.

Most mappings in vmalloc space are small, requiring less than a full
page of shadow space. Allocating a full shadow page per mapping would
therefore be wasteful. Furthermore, to ensure that different mappings
use different shadow pages, mappings would have to be aligned to
KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.

Instead, share backing space across multiple mappings. Allocate a
backing page when a mapping in vmalloc space uses a particular page of
the shadow region. This page can be shared by other vmalloc mappings
later on.

We hook in to the vmap infrastructure to lazily clean up unused shadow
memory.

To avoid the difficulties around swapping mappings around, this code
expects that the part of the shadow region that covers the vmalloc
space will not be covered by the early shadow page, but will be left
unmapped. This will require changes in arch-specific code.

This allows KASAN with VMAP_STACK, and may be helpful for architectures
that do not have a separate module space (e.g. powerpc64, which I am
currently working on). It also allows relaxing the module alignment
back to PAGE_SIZE.

Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009
Acked-by: Vasily Gorbik <gor@linux.ibm.com>
Signed-off-by: Daniel Axtens <dja@axtens.net>
[Mark: rework shadow allocation]
Signed-off-by: Mark Rutland <mark.rutland@arm.com>

--

v2: let kasan_unpoison_shadow deal with ranges that do not use a
    full shadow byte.

v3: relax module alignment
    rename to kasan_populate_vmalloc which is a much better name
    deal with concurrency correctly

v4: Mark's rework
    Poision pages on vfree
    Handle allocation failures

v5: Per Christophe Leroy, split out test and dynamically free pages.

v6: Guard freeing page properly. Drop WARN_ON_ONCE(pte_none(*ptep)),
     on reflection it's unnecessary debugging cruft with too high a
     false positive rate.

v7: tlb flush, thanks Mark.
    explain more clearly how freeing works and is concurrency-safe.
---
 Documentation/dev-tools/kasan.rst |  63 +++++++++
 include/linux/kasan.h             |  31 +++++
 include/linux/moduleloader.h      |   2 +-
 include/linux/vmalloc.h           |  12 ++
 lib/Kconfig.kasan                 |  16 +++
 mm/kasan/common.c                 | 204 ++++++++++++++++++++++++++++++
 mm/kasan/generic_report.c         |   3 +
 mm/kasan/kasan.h                  |   1 +
 mm/vmalloc.c                      |  45 ++++++-
 9 files changed, 375 insertions(+), 2 deletions(-)

diff --git a/Documentation/dev-tools/kasan.rst b/Documentation/dev-tools/kasan.rst
index b72d07d70239..bdb92c3de7a5 100644
--- a/Documentation/dev-tools/kasan.rst
+++ b/Documentation/dev-tools/kasan.rst
@@ -215,3 +215,66 @@ brk handler is used to print bug reports.
 A potential expansion of this mode is a hardware tag-based mode, which would
 use hardware memory tagging support instead of compiler instrumentation and
 manual shadow memory manipulation.
+
+What memory accesses are sanitised by KASAN?
+--------------------------------------------
+
+The kernel maps memory in a number of different parts of the address
+space. This poses something of a problem for KASAN, which requires
+that all addresses accessed by instrumented code have a valid shadow
+region.
+
+The range of kernel virtual addresses is large: there is not enough
+real memory to support a real shadow region for every address that
+could be accessed by the kernel.
+
+By default
+~~~~~~~~~~
+
+By default, architectures only map real memory over the shadow region
+for the linear mapping (and potentially other small areas). For all
+other areas - such as vmalloc and vmemmap space - a single read-only
+page is mapped over the shadow area. This read-only shadow page
+declares all memory accesses as permitted.
+
+This presents a problem for modules: they do not live in the linear
+mapping, but in a dedicated module space. By hooking in to the module
+allocator, KASAN can temporarily map real shadow memory to cover
+them. This allows detection of invalid accesses to module globals, for
+example.
+
+This also creates an incompatibility with ``VMAP_STACK``: if the stack
+lives in vmalloc space, it will be shadowed by the read-only page, and
+the kernel will fault when trying to set up the shadow data for stack
+variables.
+
+CONFIG_KASAN_VMALLOC
+~~~~~~~~~~~~~~~~~~~~
+
+With ``CONFIG_KASAN_VMALLOC``, KASAN can cover vmalloc space at the
+cost of greater memory usage. Currently this is only supported on x86.
+
+This works by hooking into vmalloc and vmap, and dynamically
+allocating real shadow memory to back the mappings.
+
+Most mappings in vmalloc space are small, requiring less than a full
+page of shadow space. Allocating a full shadow page per mapping would
+therefore be wasteful. Furthermore, to ensure that different mappings
+use different shadow pages, mappings would have to be aligned to
+``KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE``.
+
+Instead, we share backing space across multiple mappings. We allocate
+a backing page when a mapping in vmalloc space uses a particular page
+of the shadow region. This page can be shared by other vmalloc
+mappings later on.
+
+We hook in to the vmap infrastructure to lazily clean up unused shadow
+memory.
+
+To avoid the difficulties around swapping mappings around, we expect
+that the part of the shadow region that covers the vmalloc space will
+not be covered by the early shadow page, but will be left
+unmapped. This will require changes in arch-specific code.
+
+This allows ``VMAP_STACK`` support on x86, and can simplify support of
+architectures that do not have a fixed module region.
diff --git a/include/linux/kasan.h b/include/linux/kasan.h
index cc8a03cc9674..4f404c565db1 100644
--- a/include/linux/kasan.h
+++ b/include/linux/kasan.h
@@ -70,8 +70,18 @@ struct kasan_cache {
 	int free_meta_offset;
 };
 
+/*
+ * These functions provide a special case to support backing module
+ * allocations with real shadow memory. With KASAN vmalloc, the special
+ * case is unnecessary, as the work is handled in the generic case.
+ */
+#ifndef CONFIG_KASAN_VMALLOC
 int kasan_module_alloc(void *addr, size_t size);
 void kasan_free_shadow(const struct vm_struct *vm);
+#else
+static inline int kasan_module_alloc(void *addr, size_t size) { return 0; }
+static inline void kasan_free_shadow(const struct vm_struct *vm) {}
+#endif
 
 int kasan_add_zero_shadow(void *start, unsigned long size);
 void kasan_remove_zero_shadow(void *start, unsigned long size);
@@ -194,4 +204,25 @@ static inline void *kasan_reset_tag(const void *addr)
 
 #endif /* CONFIG_KASAN_SW_TAGS */
 
+#ifdef CONFIG_KASAN_VMALLOC
+int kasan_populate_vmalloc(unsigned long requested_size,
+			   struct vm_struct *area);
+void kasan_poison_vmalloc(void *start, unsigned long size);
+void kasan_release_vmalloc(unsigned long start, unsigned long end,
+			   unsigned long free_region_start,
+			   unsigned long free_region_end);
+#else
+static inline int kasan_populate_vmalloc(unsigned long requested_size,
+					 struct vm_struct *area)
+{
+	return 0;
+}
+
+static inline void kasan_poison_vmalloc(void *start, unsigned long size) {}
+static inline void kasan_release_vmalloc(unsigned long start,
+					 unsigned long end,
+					 unsigned long free_region_start,
+					 unsigned long free_region_end) {}
+#endif
+
 #endif /* LINUX_KASAN_H */
diff --git a/include/linux/moduleloader.h b/include/linux/moduleloader.h
index 5229c18025e9..ca92aea8a6bd 100644
--- a/include/linux/moduleloader.h
+++ b/include/linux/moduleloader.h
@@ -91,7 +91,7 @@ void module_arch_cleanup(struct module *mod);
 /* Any cleanup before freeing mod->module_init */
 void module_arch_freeing_init(struct module *mod);
 
-#ifdef CONFIG_KASAN
+#if defined(CONFIG_KASAN) && !defined(CONFIG_KASAN_VMALLOC)
 #include <linux/kasan.h>
 #define MODULE_ALIGN (PAGE_SIZE << KASAN_SHADOW_SCALE_SHIFT)
 #else
diff --git a/include/linux/vmalloc.h b/include/linux/vmalloc.h
index 4e7809408073..61c43d1a29ca 100644
--- a/include/linux/vmalloc.h
+++ b/include/linux/vmalloc.h
@@ -22,6 +22,18 @@ struct notifier_block;		/* in notifier.h */
 #define VM_UNINITIALIZED	0x00000020	/* vm_struct is not fully initialized */
 #define VM_NO_GUARD		0x00000040      /* don't add guard page */
 #define VM_KASAN		0x00000080      /* has allocated kasan shadow memory */
+
+/*
+ * VM_KASAN is used slighly differently depending on CONFIG_KASAN_VMALLOC.
+ *
+ * If IS_ENABLED(CONFIG_KASAN_VMALLOC), VM_KASAN is set on a vm_struct after
+ * shadow memory has been mapped. It's used to handle allocation errors so that
+ * we don't try to poision shadow on free if it was never allocated.
+ *
+ * Otherwise, VM_KASAN is set for kasan_module_alloc() allocations and used to
+ * determine which allocations need the module shadow freed.
+ */
+
 /*
  * Memory with VM_FLUSH_RESET_PERMS cannot be freed in an interrupt or with
  * vfree_atomic().
diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan
index 6c9682ce0254..81f5464ea9e1 100644
--- a/lib/Kconfig.kasan
+++ b/lib/Kconfig.kasan
@@ -6,6 +6,9 @@ config HAVE_ARCH_KASAN
 config HAVE_ARCH_KASAN_SW_TAGS
 	bool
 
+config	HAVE_ARCH_KASAN_VMALLOC
+	bool
+
 config CC_HAS_KASAN_GENERIC
 	def_bool $(cc-option, -fsanitize=kernel-address)
 
@@ -142,6 +145,19 @@ config KASAN_SW_TAGS_IDENTIFY
 	  (use-after-free or out-of-bounds) at the cost of increased
 	  memory consumption.
 
+config KASAN_VMALLOC
+	bool "Back mappings in vmalloc space with real shadow memory"
+	depends on KASAN && HAVE_ARCH_KASAN_VMALLOC
+	help
+	  By default, the shadow region for vmalloc space is the read-only
+	  zero page. This means that KASAN cannot detect errors involving
+	  vmalloc space.
+
+	  Enabling this option will hook in to vmap/vmalloc and back those
+	  mappings with real shadow memory allocated on demand. This allows
+	  for KASAN to detect more sorts of errors (and to support vmapped
+	  stacks), but at the cost of higher memory usage.
+
 config TEST_KASAN
 	tristate "Module for testing KASAN for bug detection"
 	depends on m && KASAN
diff --git a/mm/kasan/common.c b/mm/kasan/common.c
index 6814d6d6a023..e33cbab83309 100644
--- a/mm/kasan/common.c
+++ b/mm/kasan/common.c
@@ -36,6 +36,8 @@
 #include <linux/bug.h>
 #include <linux/uaccess.h>
 
+#include <asm/tlbflush.h>
+
 #include "kasan.h"
 #include "../slab.h"
 
@@ -590,6 +592,7 @@ void kasan_kfree_large(void *ptr, unsigned long ip)
 	/* The object will be poisoned by page_alloc. */
 }
 
+#ifndef CONFIG_KASAN_VMALLOC
 int kasan_module_alloc(void *addr, size_t size)
 {
 	void *ret;
@@ -625,6 +628,7 @@ void kasan_free_shadow(const struct vm_struct *vm)
 	if (vm->flags & VM_KASAN)
 		vfree(kasan_mem_to_shadow(vm->addr));
 }
+#endif
 
 extern void __kasan_report(unsigned long addr, size_t size, bool is_write, unsigned long ip);
 
@@ -744,3 +748,203 @@ static int __init kasan_memhotplug_init(void)
 
 core_initcall(kasan_memhotplug_init);
 #endif
+
+#ifdef CONFIG_KASAN_VMALLOC
+static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
+				      void *unused)
+{
+	unsigned long page;
+	pte_t pte;
+
+	if (likely(!pte_none(*ptep)))
+		return 0;
+
+	page = __get_free_page(GFP_KERNEL);
+	if (!page)
+		return -ENOMEM;
+
+	memset((void *)page, KASAN_VMALLOC_INVALID, PAGE_SIZE);
+	pte = pfn_pte(PFN_DOWN(__pa(page)), PAGE_KERNEL);
+
+	/*
+	 * Ensure poisoning is visible before the shadow is made visible
+	 * to other CPUs.
+	 */
+	smp_wmb();
+
+	spin_lock(&init_mm.page_table_lock);
+	if (likely(pte_none(*ptep))) {
+		set_pte_at(&init_mm, addr, ptep, pte);
+		page = 0;
+	}
+	spin_unlock(&init_mm.page_table_lock);
+	if (page)
+		free_page(page);
+	return 0;
+}
+
+int kasan_populate_vmalloc(unsigned long requested_size, struct vm_struct *area)
+{
+	unsigned long shadow_start, shadow_end;
+	int ret;
+
+	shadow_start = (unsigned long)kasan_mem_to_shadow(area->addr);
+	shadow_start = ALIGN_DOWN(shadow_start, PAGE_SIZE);
+	shadow_end = (unsigned long)kasan_mem_to_shadow(area->addr +
+							area->size);
+	shadow_end = ALIGN(shadow_end, PAGE_SIZE);
+
+	ret = apply_to_page_range(&init_mm, shadow_start,
+				  shadow_end - shadow_start,
+				  kasan_populate_vmalloc_pte, NULL);
+	if (ret)
+		return ret;
+
+	kasan_unpoison_shadow(area->addr, requested_size);
+
+	area->flags |= VM_KASAN;
+
+	return 0;
+}
+
+/*
+ * Poison the shadow for a vmalloc region. Called as part of the
+ * freeing process at the time the region is freed.
+ */
+void kasan_poison_vmalloc(void *start, unsigned long size)
+{
+	size = round_up(size, KASAN_SHADOW_SCALE_SIZE);
+	kasan_poison_shadow(start, size, KASAN_VMALLOC_INVALID);
+}
+
+static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
+					void *unused)
+{
+	unsigned long page;
+
+	page = (unsigned long)__va(pte_pfn(*ptep) << PAGE_SHIFT);
+
+	spin_lock(&init_mm.page_table_lock);
+
+	if (likely(!pte_none(*ptep))) {
+		pte_clear(&init_mm, addr, ptep);
+		free_page(page);
+	}
+	spin_unlock(&init_mm.page_table_lock);
+
+	return 0;
+}
+
+/*
+ * Release the backing for the vmalloc region [start, end), which
+ * lies within the free region [free_region_start, free_region_end).
+ *
+ * This can be run lazily, long after the region was freed. It runs
+ * under vmap_area_lock, so it's not safe to interact with the vmalloc/vmap
+ * infrastructure.
+ *
+ * How does this work?
+ * -------------------
+ *
+ * We have a region that is page aligned, labelled as A.
+ * That might not map onto the shadow in a way that is page-aligned:
+ *
+ *                    start                     end
+ *                    v                         v
+ * |????????|????????|AAAAAAAA|AA....AA|AAAAAAAA|????????| < vmalloc
+ *  -------- -------- --------          -------- --------
+ *      |        |       |                 |        |
+ *      |        |       |         /-------/        |
+ *      \-------\|/------/         |/---------------/
+ *              |||                ||
+ *             |??AAAAAA|AAAAAAAA|AA??????|                < shadow
+ *                 (1)      (2)      (3)
+ *
+ * First we align the start upwards and the end downwards, so that the
+ * shadow of the region aligns with shadow page boundaries. In the
+ * example, this gives us the shadow page (2). This is the shadow entirely
+ * covered by this allocation.
+ *
+ * Then we have the tricky bits. We want to know if we can free the
+ * partially covered shadow pages - (1) and (3) in the example. For this,
+ * we are given the start and end of the free region that contains this
+ * allocation. Extending our previous example, we could have:
+ *
+ *  free_region_start                                    free_region_end
+ *  |                 start                     end      |
+ *  v                 v                         v        v
+ * |FFFFFFFF|FFFFFFFF|AAAAAAAA|AA....AA|AAAAAAAA|FFFFFFFF| < vmalloc
+ *  -------- -------- --------          -------- --------
+ *      |        |       |                 |        |
+ *      |        |       |         /-------/        |
+ *      \-------\|/------/         |/---------------/
+ *              |||                ||
+ *             |FFAAAAAA|AAAAAAAA|AAF?????|                < shadow
+ *                 (1)      (2)      (3) 
+ *
+ * Once again, we align the start of the free region up, and the end of
+ * the free region down so that the shadow is page aligned. So we can free
+ * page (1) - we know no allocation currently uses anything in that page,
+ * because all of it is in the vmalloc free region. But we cannot free
+ * page (3), because we can't be sure that the rest of it is unused.
+ *
+ * We only consider pages that contain part of the original region for
+ * freeing: we don't try to free other pages from the free region or we'd
+ * end up trying to free huge chunks of virtual address space.
+ *
+ * Concurrency
+ * -----------
+ *
+ * How do we know that we're not freeing a page that is simultaneously
+ * being used for a fresh allocation in kasan_populate_vmalloc(_pte)?
+ *
+ * We _can_ have kasan_release_vmalloc and kasan_populate_vmalloc running
+ * at the same time. While we run under vmap_area_lock, the population
+ * code does not: alloc_vmap_area and the per-cpu allocator both take the
+ * lock before calling __alloc_vmap_area to identify and reserve a region,
+ * and both release the lock before we call kasan_populate_vmalloc.
+ *
+ * vmap_area_lock instead operates to ensure that the larger range
+ * [free_region_start, free_region_end) is safe: because __alloc_vmap_area
+ * is excluded, no space identified as free will become non-free while we
+ * are running. This means that so long as we are careful with alignment
+ * and only free shadow pages entirely covered by the free region, we will
+ * not run in to trouble - any simultaneous allocations will be for
+ * disjoint regions.
+ */
+void kasan_release_vmalloc(unsigned long start, unsigned long end,
+			   unsigned long free_region_start,
+			   unsigned long free_region_end)
+{
+	void *shadow_start, *shadow_end;
+	unsigned long region_start, region_end;
+
+	region_start = ALIGN(start, PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE);
+	region_end = ALIGN_DOWN(end, PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE);
+
+	free_region_start = ALIGN(free_region_start,
+				  PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE);
+
+	if (start != region_start &&
+	    free_region_start < region_start)
+		region_start -= PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE;
+
+	free_region_end = ALIGN_DOWN(free_region_end,
+				     PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE);
+
+	if (end != region_end &&
+	    free_region_end > region_end)
+		region_end += PAGE_SIZE * KASAN_SHADOW_SCALE_SIZE;
+
+	shadow_start = kasan_mem_to_shadow((void *)region_start);
+	shadow_end = kasan_mem_to_shadow((void *)region_end);
+
+	if (shadow_end > shadow_start) {
+		apply_to_page_range(&init_mm, (unsigned long)shadow_start,
+				    (unsigned long)(shadow_end - shadow_start),
+				    kasan_depopulate_vmalloc_pte, NULL);
+		flush_tlb_kernel_range((unsigned long)shadow_start,
+				       (unsigned long)shadow_end);
+	}
+}
+#endif
diff --git a/mm/kasan/generic_report.c b/mm/kasan/generic_report.c
index 36c645939bc9..2d97efd4954f 100644
--- a/mm/kasan/generic_report.c
+++ b/mm/kasan/generic_report.c
@@ -86,6 +86,9 @@ static const char *get_shadow_bug_type(struct kasan_access_info *info)
 	case KASAN_ALLOCA_RIGHT:
 		bug_type = "alloca-out-of-bounds";
 		break;
+	case KASAN_VMALLOC_INVALID:
+		bug_type = "vmalloc-out-of-bounds";
+		break;
 	}
 
 	return bug_type;
diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
index 35cff6bbb716..3a083274628e 100644
--- a/mm/kasan/kasan.h
+++ b/mm/kasan/kasan.h
@@ -25,6 +25,7 @@
 #endif
 
 #define KASAN_GLOBAL_REDZONE    0xFA  /* redzone for global variable */
+#define KASAN_VMALLOC_INVALID   0xF9  /* unallocated space in vmapped page */
 
 /*
  * Stack redzone shadow values
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index a3c70e275f4e..9fb7a16f42ae 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -690,8 +690,19 @@ merge_or_add_vmap_area(struct vmap_area *va,
 	struct list_head *next;
 	struct rb_node **link;
 	struct rb_node *parent;
+	unsigned long orig_start, orig_end;
 	bool merged = false;
 
+	/*
+	 * To manage KASAN vmalloc memory usage, we use this opportunity to
+	 * clean up the shadow memory allocated to back this allocation.
+	 * Because a vmalloc shadow page covers several pages, the start or end
+	 * of an allocation might not align with a shadow page. Use the merging
+	 * opportunities to try to extend the region we can release.
+	 */
+	orig_start = va->va_start;
+	orig_end = va->va_end;
+
 	/*
 	 * Find a place in the tree where VA potentially will be
 	 * inserted, unless it is merged with its sibling/siblings.
@@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
 		if (sibling->va_end == va->va_start) {
 			sibling->va_end = va->va_end;
 
+			kasan_release_vmalloc(orig_start, orig_end,
+					      sibling->va_start,
+					      sibling->va_end);
+
 			/* Check and update the tree if needed. */
 			augment_tree_propagate_from(sibling);
 
@@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
 	}
 
 insert:
+	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
+
 	if (!merged) {
 		link_va(va, root, parent, link, head);
 		augment_tree_propagate_from(va);
@@ -2068,6 +2085,22 @@ static struct vm_struct *__get_vm_area_node(unsigned long size,
 
 	setup_vmalloc_vm(area, va, flags, caller);
 
+	/*
+	 * For KASAN, if we are in vmalloc space, we need to cover the shadow
+	 * area with real memory. If we come here through VM_ALLOC, this is
+	 * done by a higher level function that has access to the true size,
+	 * which might not be a full page.
+	 *
+	 * We assume module space comes via VM_ALLOC path.
+	 */
+	if (is_vmalloc_addr(area->addr) && !(area->flags & VM_ALLOC)) {
+		if (kasan_populate_vmalloc(area->size, area)) {
+			unmap_vmap_area(va);
+			kfree(area);
+			return NULL;
+		}
+	}
+
 	return area;
 }
 
@@ -2245,6 +2278,9 @@ static void __vunmap(const void *addr, int deallocate_pages)
 	debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
 	debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
 
+	if (area->flags & VM_KASAN)
+		kasan_poison_vmalloc(area->addr, area->size);
+
 	vm_remove_mappings(area, deallocate_pages);
 
 	if (deallocate_pages) {
@@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
 	if (!addr)
 		return NULL;
 
+	if (kasan_populate_vmalloc(real_size, area))
+		return NULL;
+
 	/*
 	 * In this function, newly allocated vm_struct has VM_UNINITIALIZED
 	 * flag. It means that vm_struct is not fully initialized.
@@ -3351,10 +3390,14 @@ struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
 	spin_unlock(&vmap_area_lock);
 
 	/* insert all vm's */
-	for (area = 0; area < nr_vms; area++)
+	for (area = 0; area < nr_vms; area++) {
 		setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC,
 				 pcpu_get_vm_areas);
 
+		/* assume success here */
+		kasan_populate_vmalloc(sizes[area], vms[area]);
+	}
+
 	kfree(vas);
 	return vms;
 
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 38+ messages in thread

* [PATCH v8 2/5] kasan: add test for vmalloc
  2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
@ 2019-10-01  6:58 ` Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 3/5] fork: support VMAP_STACK with KASAN_VMALLOC Daniel Axtens
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

Test kasan vmalloc support by adding a new test to the module.

Signed-off-by: Daniel Axtens <dja@axtens.net>

--

v5: split out per Christophe Leroy
---
 lib/test_kasan.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/lib/test_kasan.c b/lib/test_kasan.c
index 49cc4d570a40..328d33beae36 100644
--- a/lib/test_kasan.c
+++ b/lib/test_kasan.c
@@ -19,6 +19,7 @@
 #include <linux/string.h>
 #include <linux/uaccess.h>
 #include <linux/io.h>
+#include <linux/vmalloc.h>
 
 #include <asm/page.h>
 
@@ -748,6 +749,30 @@ static noinline void __init kmalloc_double_kzfree(void)
 	kzfree(ptr);
 }
 
+#ifdef CONFIG_KASAN_VMALLOC
+static noinline void __init vmalloc_oob(void)
+{
+	void *area;
+
+	pr_info("vmalloc out-of-bounds\n");
+
+	/*
+	 * We have to be careful not to hit the guard page.
+	 * The MMU will catch that and crash us.
+	 */
+	area = vmalloc(3000);
+	if (!area) {
+		pr_err("Allocation failed\n");
+		return;
+	}
+
+	((volatile char *)area)[3100];
+	vfree(area);
+}
+#else
+static void __init vmalloc_oob(void) {}
+#endif
+
 static int __init kmalloc_tests_init(void)
 {
 	/*
@@ -793,6 +818,7 @@ static int __init kmalloc_tests_init(void)
 	kasan_strings();
 	kasan_bitops();
 	kmalloc_double_kzfree();
+	vmalloc_oob();
 
 	kasan_restore_multi_shot(multishot);
 
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 38+ messages in thread

* [PATCH v8 3/5] fork: support VMAP_STACK with KASAN_VMALLOC
  2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 2/5] kasan: add test for vmalloc Daniel Axtens
@ 2019-10-01  6:58 ` Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 4/5] x86/kasan: support KASAN_VMALLOC Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 5/5] kasan debug: track pages allocated for vmalloc shadow Daniel Axtens
  4 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

Supporting VMAP_STACK with KASAN_VMALLOC is straightforward:

 - clear the shadow region of vmapped stacks when swapping them in
 - tweak Kconfig to allow VMAP_STACK to be turned on with KASAN

Reviewed-by: Dmitry Vyukov <dvyukov@google.com>
Signed-off-by: Daniel Axtens <dja@axtens.net>
---
 arch/Kconfig  | 9 +++++----
 kernel/fork.c | 4 ++++
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/arch/Kconfig b/arch/Kconfig
index 5f8a5d84dbbe..2d914990402f 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -843,16 +843,17 @@ config HAVE_ARCH_VMAP_STACK
 config VMAP_STACK
 	default y
 	bool "Use a virtually-mapped stack"
-	depends on HAVE_ARCH_VMAP_STACK && !KASAN
+	depends on HAVE_ARCH_VMAP_STACK
+	depends on !KASAN || KASAN_VMALLOC
 	---help---
 	  Enable this if you want the use virtually-mapped kernel stacks
 	  with guard pages.  This causes kernel stack overflows to be
 	  caught immediately rather than causing difficult-to-diagnose
 	  corruption.
 
-	  This is presently incompatible with KASAN because KASAN expects
-	  the stack to map directly to the KASAN shadow map using a formula
-	  that is incorrect if the stack is in vmalloc space.
+	  To use this with KASAN, the architecture must support backing
+	  virtual mappings with real shadow memory, and KASAN_VMALLOC must
+	  be enabled.
 
 config ARCH_OPTIONAL_KERNEL_RWX
 	def_bool n
diff --git a/kernel/fork.c b/kernel/fork.c
index 6adbbcf448c3..0c9e6478ba85 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -94,6 +94,7 @@
 #include <linux/livepatch.h>
 #include <linux/thread_info.h>
 #include <linux/stackleak.h>
+#include <linux/kasan.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -229,6 +230,9 @@ static unsigned long *alloc_thread_stack_node(struct task_struct *tsk, int node)
 		if (!s)
 			continue;
 
+		/* Clear the KASAN shadow of the stack. */
+		kasan_unpoison_shadow(s->addr, THREAD_SIZE);
+
 		/* Clear stale pointers from reused stack. */
 		memset(s->addr, 0, THREAD_SIZE);
 
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 38+ messages in thread

* [PATCH v8 4/5] x86/kasan: support KASAN_VMALLOC
  2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
                   ` (2 preceding siblings ...)
  2019-10-01  6:58 ` [PATCH v8 3/5] fork: support VMAP_STACK with KASAN_VMALLOC Daniel Axtens
@ 2019-10-01  6:58 ` Daniel Axtens
  2019-10-01  6:58 ` [PATCH v8 5/5] kasan debug: track pages allocated for vmalloc shadow Daniel Axtens
  4 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

In the case where KASAN directly allocates memory to back vmalloc
space, don't map the early shadow page over it.

We prepopulate pgds/p4ds for the range that would otherwise be empty.
This is required to get it synced to hardware on boot, allowing the
lower levels of the page tables to be filled dynamically.

Acked-by: Dmitry Vyukov <dvyukov@google.com>
Signed-off-by: Daniel Axtens <dja@axtens.net>

---
v5: fix some checkpatch CHECK warnings. There are some that remain
    around lines ending with '(': I have not changed these because
    it's consistent with the rest of the file and it's not easy to
    see how to fix it without creating an overlong line or lots of
    temporary variables.

v2: move from faulting in shadow pgds to prepopulating
---
 arch/x86/Kconfig            |  1 +
 arch/x86/mm/kasan_init_64.c | 60 +++++++++++++++++++++++++++++++++++++
 2 files changed, 61 insertions(+)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 96ea2c7449ef..3590651e95f5 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -135,6 +135,7 @@ config X86
 	select HAVE_ARCH_JUMP_LABEL
 	select HAVE_ARCH_JUMP_LABEL_RELATIVE
 	select HAVE_ARCH_KASAN			if X86_64
+	select HAVE_ARCH_KASAN_VMALLOC		if X86_64
 	select HAVE_ARCH_KGDB
 	select HAVE_ARCH_MMAP_RND_BITS		if MMU
 	select HAVE_ARCH_MMAP_RND_COMPAT_BITS	if MMU && COMPAT
diff --git a/arch/x86/mm/kasan_init_64.c b/arch/x86/mm/kasan_init_64.c
index 296da58f3013..8f00f462709e 100644
--- a/arch/x86/mm/kasan_init_64.c
+++ b/arch/x86/mm/kasan_init_64.c
@@ -245,6 +245,51 @@ static void __init kasan_map_early_shadow(pgd_t *pgd)
 	} while (pgd++, addr = next, addr != end);
 }
 
+static void __init kasan_shallow_populate_p4ds(pgd_t *pgd,
+					       unsigned long addr,
+					       unsigned long end,
+					       int nid)
+{
+	p4d_t *p4d;
+	unsigned long next;
+	void *p;
+
+	p4d = p4d_offset(pgd, addr);
+	do {
+		next = p4d_addr_end(addr, end);
+
+		if (p4d_none(*p4d)) {
+			p = early_alloc(PAGE_SIZE, nid, true);
+			p4d_populate(&init_mm, p4d, p);
+		}
+	} while (p4d++, addr = next, addr != end);
+}
+
+static void __init kasan_shallow_populate_pgds(void *start, void *end)
+{
+	unsigned long addr, next;
+	pgd_t *pgd;
+	void *p;
+	int nid = early_pfn_to_nid((unsigned long)start);
+
+	addr = (unsigned long)start;
+	pgd = pgd_offset_k(addr);
+	do {
+		next = pgd_addr_end(addr, (unsigned long)end);
+
+		if (pgd_none(*pgd)) {
+			p = early_alloc(PAGE_SIZE, nid, true);
+			pgd_populate(&init_mm, pgd, p);
+		}
+
+		/*
+		 * we need to populate p4ds to be synced when running in
+		 * four level mode - see sync_global_pgds_l4()
+		 */
+		kasan_shallow_populate_p4ds(pgd, addr, next, nid);
+	} while (pgd++, addr = next, addr != (unsigned long)end);
+}
+
 #ifdef CONFIG_KASAN_INLINE
 static int kasan_die_handler(struct notifier_block *self,
 			     unsigned long val,
@@ -352,9 +397,24 @@ void __init kasan_init(void)
 	shadow_cpu_entry_end = (void *)round_up(
 			(unsigned long)shadow_cpu_entry_end, PAGE_SIZE);
 
+	/*
+	 * If we're in full vmalloc mode, don't back vmalloc space with early
+	 * shadow pages. Instead, prepopulate pgds/p4ds so they are synced to
+	 * the global table and we can populate the lower levels on demand.
+	 */
+#ifdef CONFIG_KASAN_VMALLOC
+	kasan_shallow_populate_pgds(
+		kasan_mem_to_shadow((void *)PAGE_OFFSET + MAXMEM),
+		kasan_mem_to_shadow((void *)VMALLOC_END));
+
+	kasan_populate_early_shadow(
+		kasan_mem_to_shadow((void *)VMALLOC_END + 1),
+		shadow_cpu_entry_begin);
+#else
 	kasan_populate_early_shadow(
 		kasan_mem_to_shadow((void *)PAGE_OFFSET + MAXMEM),
 		shadow_cpu_entry_begin);
+#endif
 
 	kasan_populate_shadow((unsigned long)shadow_cpu_entry_begin,
 			      (unsigned long)shadow_cpu_entry_end, 0);
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 38+ messages in thread

* [PATCH v8 5/5] kasan debug: track pages allocated for vmalloc shadow
  2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
                   ` (3 preceding siblings ...)
  2019-10-01  6:58 ` [PATCH v8 4/5] x86/kasan: support KASAN_VMALLOC Daniel Axtens
@ 2019-10-01  6:58 ` Daniel Axtens
  4 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-01  6:58 UTC (permalink / raw)
  To: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor, Daniel Axtens

Provide the current number of vmalloc shadow pages in
/sys/kernel/debug/kasan/vmalloc_shadow_pages.

Signed-off-by: Daniel Axtens <dja@axtens.net>

---

v8: rename kasan_vmalloc/shadow_pages -> kasan/vmalloc_shadow_pages

On v4 (no dynamic freeing), I saw the following approximate figures
on my test VM:

 - fresh boot: 720
 - after test_vmalloc: ~14000

With v5 (lazy dynamic freeing):

 - boot: ~490-500
 - running modprobe test_vmalloc pushes the figures up to sometimes
    as high as ~14000, but they drop down to ~560 after the test ends.
    I'm not sure where the extra sixty pages are from, but running the
    test repeately doesn't cause the number to keep growing, so I don't
    think we're leaking.
 - with vmap_stack, spawning tasks pushes the figure up to ~4200, then
    some clearing kicks in and drops it down to previous levels again.
---
 mm/kasan/common.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/mm/kasan/common.c b/mm/kasan/common.c
index e33cbab83309..5b924f860a32 100644
--- a/mm/kasan/common.c
+++ b/mm/kasan/common.c
@@ -35,6 +35,7 @@
 #include <linux/vmalloc.h>
 #include <linux/bug.h>
 #include <linux/uaccess.h>
+#include <linux/debugfs.h>
 
 #include <asm/tlbflush.h>
 
@@ -750,6 +751,8 @@ core_initcall(kasan_memhotplug_init);
 #endif
 
 #ifdef CONFIG_KASAN_VMALLOC
+static u64 vmalloc_shadow_pages;
+
 static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
 				      void *unused)
 {
@@ -776,6 +779,7 @@ static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
 	if (likely(pte_none(*ptep))) {
 		set_pte_at(&init_mm, addr, ptep, pte);
 		page = 0;
+		vmalloc_shadow_pages++;
 	}
 	spin_unlock(&init_mm.page_table_lock);
 	if (page)
@@ -829,6 +833,7 @@ static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
 	if (likely(!pte_none(*ptep))) {
 		pte_clear(&init_mm, addr, ptep);
 		free_page(page);
+		vmalloc_shadow_pages--;
 	}
 	spin_unlock(&init_mm.page_table_lock);
 
@@ -947,4 +952,25 @@ void kasan_release_vmalloc(unsigned long start, unsigned long end,
 				       (unsigned long)shadow_end);
 	}
 }
+
+static __init int kasan_init_debugfs(void)
+{
+	struct dentry *root, *count;
+
+	root = debugfs_create_dir("kasan", NULL);
+	if (IS_ERR(root)) {
+		if (PTR_ERR(root) == -ENODEV)
+			return 0;
+		return PTR_ERR(root);
+	}
+
+	count = debugfs_create_u64("vmalloc_shadow_pages", 0444, root,
+				   &vmalloc_shadow_pages);
+
+	if (IS_ERR(count))
+		return PTR_ERR(root);
+
+	return 0;
+}
+late_initcall(kasan_init_debugfs);
 #endif
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
@ 2019-10-01 10:17     ` Uladzislau Rezki
  2019-10-07  8:02     ` Uladzislau Rezki
                       ` (2 subsequent siblings)
  3 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-01 10:17 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy, linuxppc-dev, gor

Hello, Daniel.

> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index a3c70e275f4e..9fb7a16f42ae 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -690,8 +690,19 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	struct list_head *next;
>  	struct rb_node **link;
>  	struct rb_node *parent;
> +	unsigned long orig_start, orig_end;
Shouldn't that be wrapped around #ifdef CONFIG_KASAN_VMALLOC?

>  	bool merged = false;
>  
> +	/*
> +	 * To manage KASAN vmalloc memory usage, we use this opportunity to
> +	 * clean up the shadow memory allocated to back this allocation.
> +	 * Because a vmalloc shadow page covers several pages, the start or end
> +	 * of an allocation might not align with a shadow page. Use the merging
> +	 * opportunities to try to extend the region we can release.
> +	 */
> +	orig_start = va->va_start;
> +	orig_end = va->va_end;
> +
The same.

>  	/*
>  	 * Find a place in the tree where VA potentially will be
>  	 * inserted, unless it is merged with its sibling/siblings.
> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  		if (sibling->va_end == va->va_start) {
>  			sibling->va_end = va->va_end;
>  
> +			kasan_release_vmalloc(orig_start, orig_end,
> +					      sibling->va_start,
> +					      sibling->va_end);
> +
The same.

>  			/* Check and update the tree if needed. */
>  			augment_tree_propagate_from(sibling);
>  
> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	}
>  
>  insert:
> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
> +
The same + all further changes in this file.
>  	if (!merged) {
>  		link_va(va, root, parent, link, head);
>  		augment_tree_propagate_from(va);
> @@ -2068,6 +2085,22 @@ static struct vm_struct *__get_vm_area_node(unsigned long size,
>  
>  	setup_vmalloc_vm(area, va, flags, caller);
>  
> +	/*
> +	 * For KASAN, if we are in vmalloc space, we need to cover the shadow
> +	 * area with real memory. If we come here through VM_ALLOC, this is
> +	 * done by a higher level function that has access to the true size,
> +	 * which might not be a full page.
> +	 *
> +	 * We assume module space comes via VM_ALLOC path.
> +	 */
> +	if (is_vmalloc_addr(area->addr) && !(area->flags & VM_ALLOC)) {
> +		if (kasan_populate_vmalloc(area->size, area)) {
> +			unmap_vmap_area(va);
> +			kfree(area);
> +			return NULL;
> +		}
> +	}
> +
>  	return area;
>  }
>  
> @@ -2245,6 +2278,9 @@ static void __vunmap(const void *addr, int deallocate_pages)
>  	debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
>  	debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
>  
> +	if (area->flags & VM_KASAN)
> +		kasan_poison_vmalloc(area->addr, area->size);
> +
>  	vm_remove_mappings(area, deallocate_pages);
>  
>  	if (deallocate_pages) {
> @@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
>  	if (!addr)
>  		return NULL;
>  
> +	if (kasan_populate_vmalloc(real_size, area))
> +		return NULL;
> +
>  	/*
>  	 * In this function, newly allocated vm_struct has VM_UNINITIALIZED
>  	 * flag. It means that vm_struct is not fully initialized.
> @@ -3351,10 +3390,14 @@ struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
>  	spin_unlock(&vmap_area_lock);
>  
>  	/* insert all vm's */
> -	for (area = 0; area < nr_vms; area++)
> +	for (area = 0; area < nr_vms; area++) {
>  		setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC,
>  				 pcpu_get_vm_areas);
>  
> +		/* assume success here */
> +		kasan_populate_vmalloc(sizes[area], vms[area]);
> +	}
> +
>  	kfree(vas);
>  	return vms;
>  


--
Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-01 10:17     ` Uladzislau Rezki
  0 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-01 10:17 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	glider, luto, aryabinin, linuxppc-dev, dvyukov

Hello, Daniel.

> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index a3c70e275f4e..9fb7a16f42ae 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -690,8 +690,19 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	struct list_head *next;
>  	struct rb_node **link;
>  	struct rb_node *parent;
> +	unsigned long orig_start, orig_end;
Shouldn't that be wrapped around #ifdef CONFIG_KASAN_VMALLOC?

>  	bool merged = false;
>  
> +	/*
> +	 * To manage KASAN vmalloc memory usage, we use this opportunity to
> +	 * clean up the shadow memory allocated to back this allocation.
> +	 * Because a vmalloc shadow page covers several pages, the start or end
> +	 * of an allocation might not align with a shadow page. Use the merging
> +	 * opportunities to try to extend the region we can release.
> +	 */
> +	orig_start = va->va_start;
> +	orig_end = va->va_end;
> +
The same.

>  	/*
>  	 * Find a place in the tree where VA potentially will be
>  	 * inserted, unless it is merged with its sibling/siblings.
> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  		if (sibling->va_end == va->va_start) {
>  			sibling->va_end = va->va_end;
>  
> +			kasan_release_vmalloc(orig_start, orig_end,
> +					      sibling->va_start,
> +					      sibling->va_end);
> +
The same.

>  			/* Check and update the tree if needed. */
>  			augment_tree_propagate_from(sibling);
>  
> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	}
>  
>  insert:
> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
> +
The same + all further changes in this file.
>  	if (!merged) {
>  		link_va(va, root, parent, link, head);
>  		augment_tree_propagate_from(va);
> @@ -2068,6 +2085,22 @@ static struct vm_struct *__get_vm_area_node(unsigned long size,
>  
>  	setup_vmalloc_vm(area, va, flags, caller);
>  
> +	/*
> +	 * For KASAN, if we are in vmalloc space, we need to cover the shadow
> +	 * area with real memory. If we come here through VM_ALLOC, this is
> +	 * done by a higher level function that has access to the true size,
> +	 * which might not be a full page.
> +	 *
> +	 * We assume module space comes via VM_ALLOC path.
> +	 */
> +	if (is_vmalloc_addr(area->addr) && !(area->flags & VM_ALLOC)) {
> +		if (kasan_populate_vmalloc(area->size, area)) {
> +			unmap_vmap_area(va);
> +			kfree(area);
> +			return NULL;
> +		}
> +	}
> +
>  	return area;
>  }
>  
> @@ -2245,6 +2278,9 @@ static void __vunmap(const void *addr, int deallocate_pages)
>  	debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
>  	debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
>  
> +	if (area->flags & VM_KASAN)
> +		kasan_poison_vmalloc(area->addr, area->size);
> +
>  	vm_remove_mappings(area, deallocate_pages);
>  
>  	if (deallocate_pages) {
> @@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
>  	if (!addr)
>  		return NULL;
>  
> +	if (kasan_populate_vmalloc(real_size, area))
> +		return NULL;
> +
>  	/*
>  	 * In this function, newly allocated vm_struct has VM_UNINITIALIZED
>  	 * flag. It means that vm_struct is not fully initialized.
> @@ -3351,10 +3390,14 @@ struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
>  	spin_unlock(&vmap_area_lock);
>  
>  	/* insert all vm's */
> -	for (area = 0; area < nr_vms; area++)
> +	for (area = 0; area < nr_vms; area++) {
>  		setup_vmalloc_vm(vms[area], vas[area], VM_ALLOC,
>  				 pcpu_get_vm_areas);
>  
> +		/* assume success here */
> +		kasan_populate_vmalloc(sizes[area], vms[area]);
> +	}
> +
>  	kfree(vas);
>  	return vms;
>  


--
Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01 10:17     ` Uladzislau Rezki
@ 2019-10-02  1:23       ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-02  1:23 UTC (permalink / raw)
  To: Uladzislau Rezki
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy, linuxppc-dev, gor

Hi,

>>  	/*
>>  	 * Find a place in the tree where VA potentially will be
>>  	 * inserted, unless it is merged with its sibling/siblings.
>> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>>  		if (sibling->va_end == va->va_start) {
>>  			sibling->va_end = va->va_end;
>>  
>> +			kasan_release_vmalloc(orig_start, orig_end,
>> +					      sibling->va_start,
>> +					      sibling->va_end);
>> +
> The same.

The call to kasan_release_vmalloc() is a static inline no-op if
CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
way to do things rather than sprinkling the code with ifdefs?

The complier should be smart enough to eliminate all the
orig_state/orig_end stuff at compile time because it can see that it's
not used, so there's no cost in the binary.

Regards,
Daniel

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-02  1:23       ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-02  1:23 UTC (permalink / raw)
  To: Uladzislau Rezki
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	glider, luto, aryabinin, linuxppc-dev, dvyukov

Hi,

>>  	/*
>>  	 * Find a place in the tree where VA potentially will be
>>  	 * inserted, unless it is merged with its sibling/siblings.
>> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>>  		if (sibling->va_end == va->va_start) {
>>  			sibling->va_end = va->va_end;
>>  
>> +			kasan_release_vmalloc(orig_start, orig_end,
>> +					      sibling->va_start,
>> +					      sibling->va_end);
>> +
> The same.

The call to kasan_release_vmalloc() is a static inline no-op if
CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
way to do things rather than sprinkling the code with ifdefs?

The complier should be smart enough to eliminate all the
orig_state/orig_end stuff at compile time because it can see that it's
not used, so there's no cost in the binary.

Regards,
Daniel

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-02  1:23       ` Daniel Axtens
@ 2019-10-02  7:13         ` Christophe Leroy
  -1 siblings, 0 replies; 38+ messages in thread
From: Christophe Leroy @ 2019-10-02  7:13 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: gor, linuxppc-dev, dvyukov, mark.rutland, linux-kernel, luto,
	glider, aryabinin, x86, linux-mm, kasan-dev, Uladzislau Rezki

Daniel Axtens <dja@axtens.net> a écrit :

> Hi,
>
>>>  	/*
>>>  	 * Find a place in the tree where VA potentially will be
>>>  	 * inserted, unless it is merged with its sibling/siblings.
>>> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>>>  		if (sibling->va_end == va->va_start) {
>>>  			sibling->va_end = va->va_end;
>>>
>>> +			kasan_release_vmalloc(orig_start, orig_end,
>>> +					      sibling->va_start,
>>> +					      sibling->va_end);
>>> +
>> The same.
>
> The call to kasan_release_vmalloc() is a static inline no-op if
> CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
> way to do things rather than sprinkling the code with ifdefs?
>
> The complier should be smart enough to eliminate all the
> orig_state/orig_end stuff at compile time because it can see that it's
> not used, so there's no cost in the binary.
>


Daniel,

You are entirely right in your way to do i, that's fully in line with  
Linux kernel codying style  
https://www.kernel.org/doc/html/latest/process/coding-style.html#conditional-compilation

Christophe


^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-02  7:13         ` Christophe Leroy
  0 siblings, 0 replies; 38+ messages in thread
From: Christophe Leroy @ 2019-10-02  7:13 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	Uladzislau Rezki, glider, luto, aryabinin, linuxppc-dev, dvyukov

Daniel Axtens <dja@axtens.net> a écrit :

> Hi,
>
>>>  	/*
>>>  	 * Find a place in the tree where VA potentially will be
>>>  	 * inserted, unless it is merged with its sibling/siblings.
>>> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>>>  		if (sibling->va_end == va->va_start) {
>>>  			sibling->va_end = va->va_end;
>>>
>>> +			kasan_release_vmalloc(orig_start, orig_end,
>>> +					      sibling->va_start,
>>> +					      sibling->va_end);
>>> +
>> The same.
>
> The call to kasan_release_vmalloc() is a static inline no-op if
> CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
> way to do things rather than sprinkling the code with ifdefs?
>
> The complier should be smart enough to eliminate all the
> orig_state/orig_end stuff at compile time because it can see that it's
> not used, so there's no cost in the binary.
>


Daniel,

You are entirely right in your way to do i, that's fully in line with  
Linux kernel codying style  
https://www.kernel.org/doc/html/latest/process/coding-style.html#conditional-compilation

Christophe


^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-02  1:23       ` Daniel Axtens
@ 2019-10-02 11:49         ` Uladzislau Rezki
  -1 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-02 11:49 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: Uladzislau Rezki, kasan-dev, linux-mm, x86, aryabinin, glider,
	luto, linux-kernel, mark.rutland, dvyukov, christophe.leroy,
	linuxppc-dev, gor

On Wed, Oct 02, 2019 at 11:23:06AM +1000, Daniel Axtens wrote:
> Hi,
> 
> >>  	/*
> >>  	 * Find a place in the tree where VA potentially will be
> >>  	 * inserted, unless it is merged with its sibling/siblings.
> >> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
> >>  		if (sibling->va_end == va->va_start) {
> >>  			sibling->va_end = va->va_end;
> >>  
> >> +			kasan_release_vmalloc(orig_start, orig_end,
> >> +					      sibling->va_start,
> >> +					      sibling->va_end);
> >> +
> > The same.
> 
> The call to kasan_release_vmalloc() is a static inline no-op if
> CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
> way to do things rather than sprinkling the code with ifdefs?
> 
I agree that is totally correct.

> The complier should be smart enough to eliminate all the
> orig_state/orig_end stuff at compile time because it can see that it's
> not used, so there's no cost in the binary.
> 
It should. I was more thinking about if those two variables can be
considered as unused, resulting in compile warning like "set but not used".
But that is theory and in case of having any warning the test robot will
notify anyway about that.

So, i am totally fine with that if compiler does not complain. If so,
please ignore my comments :)

--
Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-02 11:49         ` Uladzislau Rezki
  0 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-02 11:49 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	Uladzislau Rezki, glider, luto, aryabinin, linuxppc-dev, dvyukov

On Wed, Oct 02, 2019 at 11:23:06AM +1000, Daniel Axtens wrote:
> Hi,
> 
> >>  	/*
> >>  	 * Find a place in the tree where VA potentially will be
> >>  	 * inserted, unless it is merged with its sibling/siblings.
> >> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
> >>  		if (sibling->va_end == va->va_start) {
> >>  			sibling->va_end = va->va_end;
> >>  
> >> +			kasan_release_vmalloc(orig_start, orig_end,
> >> +					      sibling->va_start,
> >> +					      sibling->va_end);
> >> +
> > The same.
> 
> The call to kasan_release_vmalloc() is a static inline no-op if
> CONFIG_KASAN_VMALLOC is not defined, which I thought was the preferred
> way to do things rather than sprinkling the code with ifdefs?
> 
I agree that is totally correct.

> The complier should be smart enough to eliminate all the
> orig_state/orig_end stuff at compile time because it can see that it's
> not used, so there's no cost in the binary.
> 
It should. I was more thinking about if those two variables can be
considered as unused, resulting in compile warning like "set but not used".
But that is theory and in case of having any warning the test robot will
notify anyway about that.

So, i am totally fine with that if compiler does not complain. If so,
please ignore my comments :)

--
Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
@ 2019-10-07  8:02     ` Uladzislau Rezki
  2019-10-07  8:02     ` Uladzislau Rezki
                       ` (2 subsequent siblings)
  3 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-07  8:02 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy, linuxppc-dev, gor

> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index a3c70e275f4e..9fb7a16f42ae 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -690,8 +690,19 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	struct list_head *next;
>  	struct rb_node **link;
>  	struct rb_node *parent;
> +	unsigned long orig_start, orig_end;
>  	bool merged = false;
>  
> +	/*
> +	 * To manage KASAN vmalloc memory usage, we use this opportunity to
> +	 * clean up the shadow memory allocated to back this allocation.
> +	 * Because a vmalloc shadow page covers several pages, the start or end
> +	 * of an allocation might not align with a shadow page. Use the merging
> +	 * opportunities to try to extend the region we can release.
> +	 */
> +	orig_start = va->va_start;
> +	orig_end = va->va_end;
> +
>  	/*
>  	 * Find a place in the tree where VA potentially will be
>  	 * inserted, unless it is merged with its sibling/siblings.
> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  		if (sibling->va_end == va->va_start) {
>  			sibling->va_end = va->va_end;
>  
> +			kasan_release_vmalloc(orig_start, orig_end,
> +					      sibling->va_start,
> +					      sibling->va_end);
> +
>  			/* Check and update the tree if needed. */
>  			augment_tree_propagate_from(sibling);
>  
> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	}
>  
>  insert:
> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
> +
>  	if (!merged) {
>  		link_va(va, root, parent, link, head);
>  		augment_tree_propagate_from(va);
Hello, Daniel.

Looking at it one more, i think above part of code is a bit wrong
and should be separated from merge_or_add_vmap_area() logic. The
reason is to keep it simple and do only what it is supposed to do:
merging or adding.

Also the kasan_release_vmalloc() gets called twice there and looks like
a duplication. Apart of that, merge_or_add_vmap_area() can be called via
recovery path when vmap/vmaps is/are not even setup. See percpu
allocator.

I guess your part could be moved directly to the __purge_vmap_area_lazy()
where all vmaps are lazily freed. To do so, we also need to modify
merge_or_add_vmap_area() to return merged area:

<snip>
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index e92ff5f7dd8b..fecde4312d68 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -683,7 +683,7 @@ insert_vmap_area_augment(struct vmap_area *va,
  * free area is inserted. If VA has been merged, it is
  * freed.
  */
-static __always_inline void
+static __always_inline struct vmap_area *
 merge_or_add_vmap_area(struct vmap_area *va,
        struct rb_root *root, struct list_head *head)
 {
@@ -750,7 +750,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
 
                        /* Free vmap_area object. */
                        kmem_cache_free(vmap_area_cachep, va);
-                       return;
+
+                       /* Point to the new merged area. */
+                       va = sibling;
+                       merged = true;
                }
        }
 
@@ -759,6 +762,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
                link_va(va, root, parent, link, head);
                augment_tree_propagate_from(va);
        }
+
+       return va;
 }
 
 static __always_inline bool
@@ -1172,7 +1177,7 @@ static void __free_vmap_area(struct vmap_area *va)
        /*
         * Merge VA with its neighbors, otherwise just add it.
         */
-       merge_or_add_vmap_area(va,
+       (void) merge_or_add_vmap_area(va,
                &free_vmap_area_root, &free_vmap_area_list);
 }
 
@@ -1279,15 +1284,20 @@ static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
        spin_lock(&vmap_area_lock);
        llist_for_each_entry_safe(va, n_va, valist, purge_list) {
                unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
+               unsigned long orig_start = va->va_start;
+               unsigned long orig_end = va->va_end;
 
                /*
                 * Finally insert or merge lazily-freed area. It is
                 * detached and there is no need to "unlink" it from
                 * anything.
                 */
-               merge_or_add_vmap_area(va,
+               va = merge_or_add_vmap_area(va,
                        &free_vmap_area_root, &free_vmap_area_list);
 
+               kasan_release_vmalloc(orig_start,
+                       orig_end, va->va_start, va->va_end);
+
                atomic_long_sub(nr, &vmap_lazy_nr);
 
                if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
<snip>

--
Vlad Rezki

^ permalink raw reply related	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-07  8:02     ` Uladzislau Rezki
  0 siblings, 0 replies; 38+ messages in thread
From: Uladzislau Rezki @ 2019-10-07  8:02 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	glider, luto, aryabinin, linuxppc-dev, dvyukov

> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index a3c70e275f4e..9fb7a16f42ae 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -690,8 +690,19 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	struct list_head *next;
>  	struct rb_node **link;
>  	struct rb_node *parent;
> +	unsigned long orig_start, orig_end;
>  	bool merged = false;
>  
> +	/*
> +	 * To manage KASAN vmalloc memory usage, we use this opportunity to
> +	 * clean up the shadow memory allocated to back this allocation.
> +	 * Because a vmalloc shadow page covers several pages, the start or end
> +	 * of an allocation might not align with a shadow page. Use the merging
> +	 * opportunities to try to extend the region we can release.
> +	 */
> +	orig_start = va->va_start;
> +	orig_end = va->va_end;
> +
>  	/*
>  	 * Find a place in the tree where VA potentially will be
>  	 * inserted, unless it is merged with its sibling/siblings.
> @@ -741,6 +752,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  		if (sibling->va_end == va->va_start) {
>  			sibling->va_end = va->va_end;
>  
> +			kasan_release_vmalloc(orig_start, orig_end,
> +					      sibling->va_start,
> +					      sibling->va_end);
> +
>  			/* Check and update the tree if needed. */
>  			augment_tree_propagate_from(sibling);
>  
> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	}
>  
>  insert:
> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
> +
>  	if (!merged) {
>  		link_va(va, root, parent, link, head);
>  		augment_tree_propagate_from(va);
Hello, Daniel.

Looking at it one more, i think above part of code is a bit wrong
and should be separated from merge_or_add_vmap_area() logic. The
reason is to keep it simple and do only what it is supposed to do:
merging or adding.

Also the kasan_release_vmalloc() gets called twice there and looks like
a duplication. Apart of that, merge_or_add_vmap_area() can be called via
recovery path when vmap/vmaps is/are not even setup. See percpu
allocator.

I guess your part could be moved directly to the __purge_vmap_area_lazy()
where all vmaps are lazily freed. To do so, we also need to modify
merge_or_add_vmap_area() to return merged area:

<snip>
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index e92ff5f7dd8b..fecde4312d68 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -683,7 +683,7 @@ insert_vmap_area_augment(struct vmap_area *va,
  * free area is inserted. If VA has been merged, it is
  * freed.
  */
-static __always_inline void
+static __always_inline struct vmap_area *
 merge_or_add_vmap_area(struct vmap_area *va,
        struct rb_root *root, struct list_head *head)
 {
@@ -750,7 +750,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
 
                        /* Free vmap_area object. */
                        kmem_cache_free(vmap_area_cachep, va);
-                       return;
+
+                       /* Point to the new merged area. */
+                       va = sibling;
+                       merged = true;
                }
        }
 
@@ -759,6 +762,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
                link_va(va, root, parent, link, head);
                augment_tree_propagate_from(va);
        }
+
+       return va;
 }
 
 static __always_inline bool
@@ -1172,7 +1177,7 @@ static void __free_vmap_area(struct vmap_area *va)
        /*
         * Merge VA with its neighbors, otherwise just add it.
         */
-       merge_or_add_vmap_area(va,
+       (void) merge_or_add_vmap_area(va,
                &free_vmap_area_root, &free_vmap_area_list);
 }
 
@@ -1279,15 +1284,20 @@ static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
        spin_lock(&vmap_area_lock);
        llist_for_each_entry_safe(va, n_va, valist, purge_list) {
                unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
+               unsigned long orig_start = va->va_start;
+               unsigned long orig_end = va->va_end;
 
                /*
                 * Finally insert or merge lazily-freed area. It is
                 * detached and there is no need to "unlink" it from
                 * anything.
                 */
-               merge_or_add_vmap_area(va,
+               va = merge_or_add_vmap_area(va,
                        &free_vmap_area_root, &free_vmap_area_list);
 
+               kasan_release_vmalloc(orig_start,
+                       orig_end, va->va_start, va->va_end);
+
                atomic_long_sub(nr, &vmap_lazy_nr);
 
                if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
<snip>

--
Vlad Rezki

^ permalink raw reply related	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-07  8:02     ` Uladzislau Rezki
@ 2019-10-11  5:15       ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-11  5:15 UTC (permalink / raw)
  To: Uladzislau Rezki
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	mark.rutland, dvyukov, christophe.leroy, linuxppc-dev, gor

Hi Uladzislau,


> Looking at it one more, i think above part of code is a bit wrong
> and should be separated from merge_or_add_vmap_area() logic. The
> reason is to keep it simple and do only what it is supposed to do:
> merging or adding.
>
> Also the kasan_release_vmalloc() gets called twice there and looks like
> a duplication. Apart of that, merge_or_add_vmap_area() can be called via
> recovery path when vmap/vmaps is/are not even setup. See percpu
> allocator.
>
> I guess your part could be moved directly to the __purge_vmap_area_lazy()
> where all vmaps are lazily freed. To do so, we also need to modify
> merge_or_add_vmap_area() to return merged area:

Thanks for the review. I've integrated your snippet - it seems to work
fine, and I agree that it is much simpler and clearer. so I've rolled it
in to v9 which I will post soon.

Regards,
Daniel

>
> <snip>
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index e92ff5f7dd8b..fecde4312d68 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -683,7 +683,7 @@ insert_vmap_area_augment(struct vmap_area *va,
>   * free area is inserted. If VA has been merged, it is
>   * freed.
>   */
> -static __always_inline void
> +static __always_inline struct vmap_area *
>  merge_or_add_vmap_area(struct vmap_area *va,
>         struct rb_root *root, struct list_head *head)
>  {
> @@ -750,7 +750,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  
>                         /* Free vmap_area object. */
>                         kmem_cache_free(vmap_area_cachep, va);
> -                       return;
> +
> +                       /* Point to the new merged area. */
> +                       va = sibling;
> +                       merged = true;
>                 }
>         }
>  
> @@ -759,6 +762,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>                 link_va(va, root, parent, link, head);
>                 augment_tree_propagate_from(va);
>         }
> +
> +       return va;
>  }
>  
>  static __always_inline bool
> @@ -1172,7 +1177,7 @@ static void __free_vmap_area(struct vmap_area *va)
>         /*
>          * Merge VA with its neighbors, otherwise just add it.
>          */
> -       merge_or_add_vmap_area(va,
> +       (void) merge_or_add_vmap_area(va,
>                 &free_vmap_area_root, &free_vmap_area_list);
>  }
>  
> @@ -1279,15 +1284,20 @@ static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
>         spin_lock(&vmap_area_lock);
>         llist_for_each_entry_safe(va, n_va, valist, purge_list) {
>                 unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
> +               unsigned long orig_start = va->va_start;
> +               unsigned long orig_end = va->va_end;
>  
>                 /*
>                  * Finally insert or merge lazily-freed area. It is
>                  * detached and there is no need to "unlink" it from
>                  * anything.
>                  */
> -               merge_or_add_vmap_area(va,
> +               va = merge_or_add_vmap_area(va,
>                         &free_vmap_area_root, &free_vmap_area_list);
>  
> +               kasan_release_vmalloc(orig_start,
> +                       orig_end, va->va_start, va->va_end);
> +
>                 atomic_long_sub(nr, &vmap_lazy_nr);
>  
>                 if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
> <snip>
>
> --
> Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-11  5:15       ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-11  5:15 UTC (permalink / raw)
  To: Uladzislau Rezki
  Cc: mark.rutland, gor, x86, linux-kernel, kasan-dev, linux-mm,
	glider, luto, aryabinin, linuxppc-dev, dvyukov

Hi Uladzislau,


> Looking at it one more, i think above part of code is a bit wrong
> and should be separated from merge_or_add_vmap_area() logic. The
> reason is to keep it simple and do only what it is supposed to do:
> merging or adding.
>
> Also the kasan_release_vmalloc() gets called twice there and looks like
> a duplication. Apart of that, merge_or_add_vmap_area() can be called via
> recovery path when vmap/vmaps is/are not even setup. See percpu
> allocator.
>
> I guess your part could be moved directly to the __purge_vmap_area_lazy()
> where all vmaps are lazily freed. To do so, we also need to modify
> merge_or_add_vmap_area() to return merged area:

Thanks for the review. I've integrated your snippet - it seems to work
fine, and I agree that it is much simpler and clearer. so I've rolled it
in to v9 which I will post soon.

Regards,
Daniel

>
> <snip>
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index e92ff5f7dd8b..fecde4312d68 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -683,7 +683,7 @@ insert_vmap_area_augment(struct vmap_area *va,
>   * free area is inserted. If VA has been merged, it is
>   * freed.
>   */
> -static __always_inline void
> +static __always_inline struct vmap_area *
>  merge_or_add_vmap_area(struct vmap_area *va,
>         struct rb_root *root, struct list_head *head)
>  {
> @@ -750,7 +750,10 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  
>                         /* Free vmap_area object. */
>                         kmem_cache_free(vmap_area_cachep, va);
> -                       return;
> +
> +                       /* Point to the new merged area. */
> +                       va = sibling;
> +                       merged = true;
>                 }
>         }
>  
> @@ -759,6 +762,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>                 link_va(va, root, parent, link, head);
>                 augment_tree_propagate_from(va);
>         }
> +
> +       return va;
>  }
>  
>  static __always_inline bool
> @@ -1172,7 +1177,7 @@ static void __free_vmap_area(struct vmap_area *va)
>         /*
>          * Merge VA with its neighbors, otherwise just add it.
>          */
> -       merge_or_add_vmap_area(va,
> +       (void) merge_or_add_vmap_area(va,
>                 &free_vmap_area_root, &free_vmap_area_list);
>  }
>  
> @@ -1279,15 +1284,20 @@ static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
>         spin_lock(&vmap_area_lock);
>         llist_for_each_entry_safe(va, n_va, valist, purge_list) {
>                 unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
> +               unsigned long orig_start = va->va_start;
> +               unsigned long orig_end = va->va_end;
>  
>                 /*
>                  * Finally insert or merge lazily-freed area. It is
>                  * detached and there is no need to "unlink" it from
>                  * anything.
>                  */
> -               merge_or_add_vmap_area(va,
> +               va = merge_or_add_vmap_area(va,
>                         &free_vmap_area_root, &free_vmap_area_list);
>  
> +               kasan_release_vmalloc(orig_start,
> +                       orig_end, va->va_start, va->va_end);
> +
>                 atomic_long_sub(nr, &vmap_lazy_nr);
>  
>                 if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
> <snip>
>
> --
> Vlad Rezki

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
  2019-10-01 10:17     ` Uladzislau Rezki
  2019-10-07  8:02     ` Uladzislau Rezki
@ 2019-10-11 19:57   ` Andrey Ryabinin
  2019-10-14 13:57     ` Daniel Axtens
  2019-10-14 15:43     ` Mark Rutland
  3 siblings, 1 reply; 38+ messages in thread
From: Andrey Ryabinin @ 2019-10-11 19:57 UTC (permalink / raw)
  To: Daniel Axtens, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor



On 10/1/19 9:58 AM, Daniel Axtens wrote:
 
>  core_initcall(kasan_memhotplug_init);
>  #endif
> +
> +#ifdef CONFIG_KASAN_VMALLOC
> +static int kasan_populate_vmalloc_pte(pte_t *ptep, unsigned long addr,
> +				      void *unused)
> +{
> +	unsigned long page;
> +	pte_t pte;
> +
> +	if (likely(!pte_none(*ptep)))
> +		return 0;
> +
> +	page = __get_free_page(GFP_KERNEL);
> +	if (!page)
> +		return -ENOMEM;
> +
> +	memset((void *)page, KASAN_VMALLOC_INVALID, PAGE_SIZE);
> +	pte = pfn_pte(PFN_DOWN(__pa(page)), PAGE_KERNEL);
> +
> +	/*
> +	 * Ensure poisoning is visible before the shadow is made visible
> +	 * to other CPUs.
> +	 */
> +	smp_wmb();

I'm not quite understand what this barrier do and why it needed.
And if it's really needed there should be a pairing barrier
on the other side which I don't see.

> +
> +	spin_lock(&init_mm.page_table_lock);
> +	if (likely(pte_none(*ptep))) {
> +		set_pte_at(&init_mm, addr, ptep, pte);
> +		page = 0;
> +	}
> +	spin_unlock(&init_mm.page_table_lock);
> +	if (page)
> +		free_page(page);
> +	return 0;
> +}
> +


...

> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>  	}
>  
>  insert:
> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
> +
>  	if (!merged) {
>  		link_va(va, root, parent, link, head);
>  		augment_tree_propagate_from(va);
> @@ -2068,6 +2085,22 @@ static struct vm_struct *__get_vm_area_node(unsigned long size,
>  
>  	setup_vmalloc_vm(area, va, flags, caller);
>  
> +	/*
> +	 * For KASAN, if we are in vmalloc space, we need to cover the shadow
> +	 * area with real memory. If we come here through VM_ALLOC, this is
> +	 * done by a higher level function that has access to the true size,
> +	 * which might not be a full page.
> +	 *
> +	 * We assume module space comes via VM_ALLOC path.
> +	 */
> +	if (is_vmalloc_addr(area->addr) && !(area->flags & VM_ALLOC)) {
> +		if (kasan_populate_vmalloc(area->size, area)) {
> +			unmap_vmap_area(va);
> +			kfree(area);
> +			return NULL;
> +		}
> +	}
> +
>  	return area;
>  }
>  
> @@ -2245,6 +2278,9 @@ static void __vunmap(const void *addr, int deallocate_pages)
>  	debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
>  	debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
>  
> +	if (area->flags & VM_KASAN)
> +		kasan_poison_vmalloc(area->addr, area->size);
> +
>  	vm_remove_mappings(area, deallocate_pages);
>  
>  	if (deallocate_pages) {
> @@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
>  	if (!addr)
>  		return NULL;
>  
> +	if (kasan_populate_vmalloc(real_size, area))
> +		return NULL;
> +

KASAN itself uses __vmalloc_node_range() to allocate and map shadow in memory online callback.
So we should either skip non-vmalloc and non-module addresses here or teach kasan's memory online/offline
callbacks to not use __vmalloc_node_range() (do something similar to kasan_populate_vmalloc() perhaps?). 

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-11 19:57   ` Andrey Ryabinin
@ 2019-10-14 13:57     ` Daniel Axtens
  2019-10-14 15:27         ` Mark Rutland
                         ` (2 more replies)
  0 siblings, 3 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-14 13:57 UTC (permalink / raw)
  To: Andrey Ryabinin, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor

Hi Andrey,


>> +	/*
>> +	 * Ensure poisoning is visible before the shadow is made visible
>> +	 * to other CPUs.
>> +	 */
>> +	smp_wmb();
>
> I'm not quite understand what this barrier do and why it needed.
> And if it's really needed there should be a pairing barrier
> on the other side which I don't see.

Mark might be better able to answer this, but my understanding is that
we want to make sure that we never have a situation where the writes are
reordered so that PTE is installed before all the poisioning is written
out. I think it follows the logic in __pte_alloc() in mm/memory.c:

	/*
	 * Ensure all pte setup (eg. pte page lock and page clearing) are
	 * visible before the pte is made visible to other CPUs by being
	 * put into page tables.
	 *
	 * The other side of the story is the pointer chasing in the page
	 * table walking code (when walking the page table without locking;
	 * ie. most of the time). Fortunately, these data accesses consist
	 * of a chain of data-dependent loads, meaning most CPUs (alpha
	 * being the notable exception) will already guarantee loads are
	 * seen in-order. See the alpha page table accessors for the
	 * smp_read_barrier_depends() barriers in page table walking code.
	 */
	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */

I can clarify the comment.

>> +
>> +	spin_lock(&init_mm.page_table_lock);
>> +	if (likely(pte_none(*ptep))) {
>> +		set_pte_at(&init_mm, addr, ptep, pte);
>> +		page = 0;
>> +	}
>> +	spin_unlock(&init_mm.page_table_lock);
>> +	if (page)
>> +		free_page(page);
>> +	return 0;
>> +}
>> +
>
>
> ...
>
>> @@ -754,6 +769,8 @@ merge_or_add_vmap_area(struct vmap_area *va,
>>  	}
>>  
>>  insert:
>> +	kasan_release_vmalloc(orig_start, orig_end, va->va_start, va->va_end);
>> +
>>  	if (!merged) {
>>  		link_va(va, root, parent, link, head);
>>  		augment_tree_propagate_from(va);
>> @@ -2068,6 +2085,22 @@ static struct vm_struct *__get_vm_area_node(unsigned long size,
>>  
>>  	setup_vmalloc_vm(area, va, flags, caller);
>>  
>> +	/*
>> +	 * For KASAN, if we are in vmalloc space, we need to cover the shadow
>> +	 * area with real memory. If we come here through VM_ALLOC, this is
>> +	 * done by a higher level function that has access to the true size,
>> +	 * which might not be a full page.
>> +	 *
>> +	 * We assume module space comes via VM_ALLOC path.
>> +	 */
>> +	if (is_vmalloc_addr(area->addr) && !(area->flags & VM_ALLOC)) {
>> +		if (kasan_populate_vmalloc(area->size, area)) {
>> +			unmap_vmap_area(va);
>> +			kfree(area);
>> +			return NULL;
>> +		}
>> +	}
>> +
>>  	return area;
>>  }
>>  
>> @@ -2245,6 +2278,9 @@ static void __vunmap(const void *addr, int deallocate_pages)
>>  	debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
>>  	debug_check_no_obj_freed(area->addr, get_vm_area_size(area));
>>  
>> +	if (area->flags & VM_KASAN)
>> +		kasan_poison_vmalloc(area->addr, area->size);
>> +
>>  	vm_remove_mappings(area, deallocate_pages);
>>  
>>  	if (deallocate_pages) {
>> @@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
>>  	if (!addr)
>>  		return NULL;
>>  
>> +	if (kasan_populate_vmalloc(real_size, area))
>> +		return NULL;
>> +
>
> KASAN itself uses __vmalloc_node_range() to allocate and map shadow in memory online callback.
> So we should either skip non-vmalloc and non-module addresses here or teach kasan's memory online/offline
> callbacks to not use __vmalloc_node_range() (do something similar to kasan_populate_vmalloc() perhaps?). 

Ah, right you are. I haven't been testing that.

I am a bit nervous about further restricting kasan_populate_vmalloc: I
seem to remember having problems with code using the vmalloc family of
functions to map memory that doesn't lie within vmalloc space but which
still has instrumented accesses.

On the other hand, I'm not keen on rewriting any of the memory
on/offline code if I can avoid it!

I'll have a look and get back you as soon as I can.

Thanks for catching this.

Kind regards,
Daniel

>
> -- 
> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+unsubscribe@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/352cb4fa-2e57-7e3b-23af-898e113bbe22%40virtuozzo.com.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-14 13:57     ` Daniel Axtens
@ 2019-10-14 15:27         ` Mark Rutland
  2019-10-15  6:29       ` Daniel Axtens
  2019-10-16 12:19       ` Andrey Ryabinin
  2 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-14 15:27 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: Andrey Ryabinin, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, dvyukov, christophe.leroy, linuxppc-dev, gor

On Tue, Oct 15, 2019 at 12:57:44AM +1100, Daniel Axtens wrote:
> Hi Andrey,
> 
> 
> >> +	/*
> >> +	 * Ensure poisoning is visible before the shadow is made visible
> >> +	 * to other CPUs.
> >> +	 */
> >> +	smp_wmb();
> >
> > I'm not quite understand what this barrier do and why it needed.
> > And if it's really needed there should be a pairing barrier
> > on the other side which I don't see.
> 
> Mark might be better able to answer this, but my understanding is that
> we want to make sure that we never have a situation where the writes are
> reordered so that PTE is installed before all the poisioning is written
> out. I think it follows the logic in __pte_alloc() in mm/memory.c:
> 
> 	/*
> 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
> 	 * visible before the pte is made visible to other CPUs by being
> 	 * put into page tables.

Yup. We need to ensure that if a thread sees a populated shadow PTE, the
corresponding shadow memory has been zeroed. Thus, we need to ensure
that the zeroing is observed by other CPUs before we update the PTE.

We're relying on the absence of a TLB entry preventing another CPU from
loading the corresponding shadow shadow memory until its PTE has been
populated (after the zeroing is visible). Consequently there is no
barrier on the other side, and just a control-dependency (which would be
insufficient on its own).

There is a potential problem here, as Will Deacon wrote up at:

  https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/

... in the section starting:

| *** Other architecture maintainers -- start here! ***

... whereby the CPU can spuriously fault on an access after observing a
valid PTE.

For arm64 we handle the spurious fault, and it looks like x86 would need
something like its vmalloc_fault() applying to the shadow region to
cater for this.

Thanks,
Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-14 15:27         ` Mark Rutland
  0 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-14 15:27 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	Andrey Ryabinin, linuxppc-dev, dvyukov

On Tue, Oct 15, 2019 at 12:57:44AM +1100, Daniel Axtens wrote:
> Hi Andrey,
> 
> 
> >> +	/*
> >> +	 * Ensure poisoning is visible before the shadow is made visible
> >> +	 * to other CPUs.
> >> +	 */
> >> +	smp_wmb();
> >
> > I'm not quite understand what this barrier do and why it needed.
> > And if it's really needed there should be a pairing barrier
> > on the other side which I don't see.
> 
> Mark might be better able to answer this, but my understanding is that
> we want to make sure that we never have a situation where the writes are
> reordered so that PTE is installed before all the poisioning is written
> out. I think it follows the logic in __pte_alloc() in mm/memory.c:
> 
> 	/*
> 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
> 	 * visible before the pte is made visible to other CPUs by being
> 	 * put into page tables.

Yup. We need to ensure that if a thread sees a populated shadow PTE, the
corresponding shadow memory has been zeroed. Thus, we need to ensure
that the zeroing is observed by other CPUs before we update the PTE.

We're relying on the absence of a TLB entry preventing another CPU from
loading the corresponding shadow shadow memory until its PTE has been
populated (after the zeroing is visible). Consequently there is no
barrier on the other side, and just a control-dependency (which would be
insufficient on its own).

There is a potential problem here, as Will Deacon wrote up at:

  https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/

... in the section starting:

| *** Other architecture maintainers -- start here! ***

... whereby the CPU can spuriously fault on an access after observing a
valid PTE.

For arm64 we handle the spurious fault, and it looks like x86 would need
something like its vmalloc_fault() applying to the shadow region to
cater for this.

Thanks,
Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
@ 2019-10-14 15:43     ` Mark Rutland
  2019-10-07  8:02     ` Uladzislau Rezki
                       ` (2 subsequent siblings)
  3 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-14 15:43 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	dvyukov, christophe.leroy, linuxppc-dev, gor

On Tue, Oct 01, 2019 at 04:58:30PM +1000, Daniel Axtens wrote:
> Hook into vmalloc and vmap, and dynamically allocate real shadow
> memory to back the mappings.
> 
> Most mappings in vmalloc space are small, requiring less than a full
> page of shadow space. Allocating a full shadow page per mapping would
> therefore be wasteful. Furthermore, to ensure that different mappings
> use different shadow pages, mappings would have to be aligned to
> KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.
> 
> Instead, share backing space across multiple mappings. Allocate a
> backing page when a mapping in vmalloc space uses a particular page of
> the shadow region. This page can be shared by other vmalloc mappings
> later on.
> 
> We hook in to the vmap infrastructure to lazily clean up unused shadow
> memory.
> 
> To avoid the difficulties around swapping mappings around, this code
> expects that the part of the shadow region that covers the vmalloc
> space will not be covered by the early shadow page, but will be left
> unmapped. This will require changes in arch-specific code.
> 
> This allows KASAN with VMAP_STACK, and may be helpful for architectures
> that do not have a separate module space (e.g. powerpc64, which I am
> currently working on). It also allows relaxing the module alignment
> back to PAGE_SIZE.
> 
> Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009
> Acked-by: Vasily Gorbik <gor@linux.ibm.com>
> Signed-off-by: Daniel Axtens <dja@axtens.net>
> [Mark: rework shadow allocation]
> Signed-off-by: Mark Rutland <mark.rutland@arm.com>

Sorry to point this out so late, but your S-o-B should come last in the
chain per Documentation/process/submitting-patches.rst. Judging by the
rest of that, I think you want something like:

Co-developed-by: Mark Rutland <mark.rutland@arm.com>
Signed-off-by: Mark Rutland <mark.rutland@arm.com> [shadow rework]
Signed-off-by: Daniel Axtens <dja@axtens.net>

... leaving yourself as the Author in the headers.

Sorry to have made that more complicated!

[...]

> +static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
> +					void *unused)
> +{
> +	unsigned long page;
> +
> +	page = (unsigned long)__va(pte_pfn(*ptep) << PAGE_SHIFT);
> +
> +	spin_lock(&init_mm.page_table_lock);
> +
> +	if (likely(!pte_none(*ptep))) {
> +		pte_clear(&init_mm, addr, ptep);
> +		free_page(page);
> +	}

There should be TLB maintenance between clearing the PTE and freeing the
page here.

Thanks,
Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-14 15:43     ` Mark Rutland
  0 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-14 15:43 UTC (permalink / raw)
  To: Daniel Axtens
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	aryabinin, linuxppc-dev, dvyukov

On Tue, Oct 01, 2019 at 04:58:30PM +1000, Daniel Axtens wrote:
> Hook into vmalloc and vmap, and dynamically allocate real shadow
> memory to back the mappings.
> 
> Most mappings in vmalloc space are small, requiring less than a full
> page of shadow space. Allocating a full shadow page per mapping would
> therefore be wasteful. Furthermore, to ensure that different mappings
> use different shadow pages, mappings would have to be aligned to
> KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.
> 
> Instead, share backing space across multiple mappings. Allocate a
> backing page when a mapping in vmalloc space uses a particular page of
> the shadow region. This page can be shared by other vmalloc mappings
> later on.
> 
> We hook in to the vmap infrastructure to lazily clean up unused shadow
> memory.
> 
> To avoid the difficulties around swapping mappings around, this code
> expects that the part of the shadow region that covers the vmalloc
> space will not be covered by the early shadow page, but will be left
> unmapped. This will require changes in arch-specific code.
> 
> This allows KASAN with VMAP_STACK, and may be helpful for architectures
> that do not have a separate module space (e.g. powerpc64, which I am
> currently working on). It also allows relaxing the module alignment
> back to PAGE_SIZE.
> 
> Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009
> Acked-by: Vasily Gorbik <gor@linux.ibm.com>
> Signed-off-by: Daniel Axtens <dja@axtens.net>
> [Mark: rework shadow allocation]
> Signed-off-by: Mark Rutland <mark.rutland@arm.com>

Sorry to point this out so late, but your S-o-B should come last in the
chain per Documentation/process/submitting-patches.rst. Judging by the
rest of that, I think you want something like:

Co-developed-by: Mark Rutland <mark.rutland@arm.com>
Signed-off-by: Mark Rutland <mark.rutland@arm.com> [shadow rework]
Signed-off-by: Daniel Axtens <dja@axtens.net>

... leaving yourself as the Author in the headers.

Sorry to have made that more complicated!

[...]

> +static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
> +					void *unused)
> +{
> +	unsigned long page;
> +
> +	page = (unsigned long)__va(pte_pfn(*ptep) << PAGE_SHIFT);
> +
> +	spin_lock(&init_mm.page_table_lock);
> +
> +	if (likely(!pte_none(*ptep))) {
> +		pte_clear(&init_mm, addr, ptep);
> +		free_page(page);
> +	}

There should be TLB maintenance between clearing the PTE and freeing the
page here.

Thanks,
Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-14 15:43     ` Mark Rutland
@ 2019-10-15  6:27       ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-15  6:27 UTC (permalink / raw)
  To: Mark Rutland
  Cc: kasan-dev, linux-mm, x86, aryabinin, glider, luto, linux-kernel,
	dvyukov, christophe.leroy, linuxppc-dev, gor

Mark Rutland <mark.rutland@arm.com> writes:

> On Tue, Oct 01, 2019 at 04:58:30PM +1000, Daniel Axtens wrote:
>> Hook into vmalloc and vmap, and dynamically allocate real shadow
>> memory to back the mappings.
>> 
>> Most mappings in vmalloc space are small, requiring less than a full
>> page of shadow space. Allocating a full shadow page per mapping would
>> therefore be wasteful. Furthermore, to ensure that different mappings
>> use different shadow pages, mappings would have to be aligned to
>> KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.
>> 
>> Instead, share backing space across multiple mappings. Allocate a
>> backing page when a mapping in vmalloc space uses a particular page of
>> the shadow region. This page can be shared by other vmalloc mappings
>> later on.
>> 
>> We hook in to the vmap infrastructure to lazily clean up unused shadow
>> memory.
>> 
>> To avoid the difficulties around swapping mappings around, this code
>> expects that the part of the shadow region that covers the vmalloc
>> space will not be covered by the early shadow page, but will be left
>> unmapped. This will require changes in arch-specific code.
>> 
>> This allows KASAN with VMAP_STACK, and may be helpful for architectures
>> that do not have a separate module space (e.g. powerpc64, which I am
>> currently working on). It also allows relaxing the module alignment
>> back to PAGE_SIZE.
>> 
>> Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009
>> Acked-by: Vasily Gorbik <gor@linux.ibm.com>
>> Signed-off-by: Daniel Axtens <dja@axtens.net>
>> [Mark: rework shadow allocation]
>> Signed-off-by: Mark Rutland <mark.rutland@arm.com>
>
> Sorry to point this out so late, but your S-o-B should come last in the
> chain per Documentation/process/submitting-patches.rst. Judging by the
> rest of that, I think you want something like:
>
> Co-developed-by: Mark Rutland <mark.rutland@arm.com>
> Signed-off-by: Mark Rutland <mark.rutland@arm.com> [shadow rework]
> Signed-off-by: Daniel Axtens <dja@axtens.net>
>
> ... leaving yourself as the Author in the headers.

no worries, I wasn't really sure how best to arrange them, so thanks for
clarifying!

>
> Sorry to have made that more complicated!
>
> [...]
>
>> +static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
>> +					void *unused)
>> +{
>> +	unsigned long page;
>> +
>> +	page = (unsigned long)__va(pte_pfn(*ptep) << PAGE_SHIFT);
>> +
>> +	spin_lock(&init_mm.page_table_lock);
>> +
>> +	if (likely(!pte_none(*ptep))) {
>> +		pte_clear(&init_mm, addr, ptep);
>> +		free_page(page);
>> +	}
>
> There should be TLB maintenance between clearing the PTE and freeing the
> page here.

Fixed for v9.

Regards,
Daniel

>
> Thanks,
> Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-15  6:27       ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-15  6:27 UTC (permalink / raw)
  To: Mark Rutland
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	aryabinin, linuxppc-dev, dvyukov

Mark Rutland <mark.rutland@arm.com> writes:

> On Tue, Oct 01, 2019 at 04:58:30PM +1000, Daniel Axtens wrote:
>> Hook into vmalloc and vmap, and dynamically allocate real shadow
>> memory to back the mappings.
>> 
>> Most mappings in vmalloc space are small, requiring less than a full
>> page of shadow space. Allocating a full shadow page per mapping would
>> therefore be wasteful. Furthermore, to ensure that different mappings
>> use different shadow pages, mappings would have to be aligned to
>> KASAN_SHADOW_SCALE_SIZE * PAGE_SIZE.
>> 
>> Instead, share backing space across multiple mappings. Allocate a
>> backing page when a mapping in vmalloc space uses a particular page of
>> the shadow region. This page can be shared by other vmalloc mappings
>> later on.
>> 
>> We hook in to the vmap infrastructure to lazily clean up unused shadow
>> memory.
>> 
>> To avoid the difficulties around swapping mappings around, this code
>> expects that the part of the shadow region that covers the vmalloc
>> space will not be covered by the early shadow page, but will be left
>> unmapped. This will require changes in arch-specific code.
>> 
>> This allows KASAN with VMAP_STACK, and may be helpful for architectures
>> that do not have a separate module space (e.g. powerpc64, which I am
>> currently working on). It also allows relaxing the module alignment
>> back to PAGE_SIZE.
>> 
>> Link: https://bugzilla.kernel.org/show_bug.cgi?id=202009
>> Acked-by: Vasily Gorbik <gor@linux.ibm.com>
>> Signed-off-by: Daniel Axtens <dja@axtens.net>
>> [Mark: rework shadow allocation]
>> Signed-off-by: Mark Rutland <mark.rutland@arm.com>
>
> Sorry to point this out so late, but your S-o-B should come last in the
> chain per Documentation/process/submitting-patches.rst. Judging by the
> rest of that, I think you want something like:
>
> Co-developed-by: Mark Rutland <mark.rutland@arm.com>
> Signed-off-by: Mark Rutland <mark.rutland@arm.com> [shadow rework]
> Signed-off-by: Daniel Axtens <dja@axtens.net>
>
> ... leaving yourself as the Author in the headers.

no worries, I wasn't really sure how best to arrange them, so thanks for
clarifying!

>
> Sorry to have made that more complicated!
>
> [...]
>
>> +static int kasan_depopulate_vmalloc_pte(pte_t *ptep, unsigned long addr,
>> +					void *unused)
>> +{
>> +	unsigned long page;
>> +
>> +	page = (unsigned long)__va(pte_pfn(*ptep) << PAGE_SHIFT);
>> +
>> +	spin_lock(&init_mm.page_table_lock);
>> +
>> +	if (likely(!pte_none(*ptep))) {
>> +		pte_clear(&init_mm, addr, ptep);
>> +		free_page(page);
>> +	}
>
> There should be TLB maintenance between clearing the PTE and freeing the
> page here.

Fixed for v9.

Regards,
Daniel

>
> Thanks,
> Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-14 13:57     ` Daniel Axtens
  2019-10-14 15:27         ` Mark Rutland
@ 2019-10-15  6:29       ` Daniel Axtens
  2019-10-16 12:19       ` Andrey Ryabinin
  2 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-15  6:29 UTC (permalink / raw)
  To: Andrey Ryabinin, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor

>>> @@ -2497,6 +2533,9 @@ void *__vmalloc_node_range(unsigned long size, unsigned long align,
>>>  	if (!addr)
>>>  		return NULL;
>>>  
>>> +	if (kasan_populate_vmalloc(real_size, area))
>>> +		return NULL;
>>> +
>>
>> KASAN itself uses __vmalloc_node_range() to allocate and map shadow in memory online callback.
>> So we should either skip non-vmalloc and non-module addresses here or teach kasan's memory online/offline
>> callbacks to not use __vmalloc_node_range() (do something similar to kasan_populate_vmalloc() perhaps?). 
>
> Ah, right you are. I haven't been testing that.
>
> I am a bit nervous about further restricting kasan_populate_vmalloc: I
> seem to remember having problems with code using the vmalloc family of
> functions to map memory that doesn't lie within vmalloc space but which
> still has instrumented accesses.

I was wrong or remembering early implementation bugs.

If the memory we're allocating in __vmalloc_node_range falls outside of
vmalloc and module space, it shouldn't be getting shadow mapped for it
by kasan_populate_vmalloc. For v9, I've guarded the call with
is_vmalloc_or_module. It seems to work fine when tested with hotplugged
memory.

Thanks again.

Regards,
Daniel

> On the other hand, I'm not keen on rewriting any of the memory
> on/offline code if I can avoid it!
>
> I'll have a look and get back you as soon as I can.
>
> Thanks for catching this.
>
> Kind regards,
> Daniel
>
>>
>> -- 
>> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+unsubscribe@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/352cb4fa-2e57-7e3b-23af-898e113bbe22%40virtuozzo.com.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-14 15:27         ` Mark Rutland
@ 2019-10-15  6:32           ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-15  6:32 UTC (permalink / raw)
  To: Mark Rutland
  Cc: Andrey Ryabinin, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, dvyukov, christophe.leroy, linuxppc-dev, gor


> There is a potential problem here, as Will Deacon wrote up at:
>
>   https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
>
> ... in the section starting:
>
> | *** Other architecture maintainers -- start here! ***
>
> ... whereby the CPU can spuriously fault on an access after observing a
> valid PTE.
>
> For arm64 we handle the spurious fault, and it looks like x86 would need
> something like its vmalloc_fault() applying to the shadow region to
> cater for this.

I'm not really up on x86 - my first thought would be that their stronger
memory ordering might be sufficient but I really don't know. Reading the
thread I see arm and powerpc discussions but nothing from anyone else,
so I'm none the wiser there...

Andy, do you have any thoughts?

Regards,
Daniel

>
> Thanks,
> Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-15  6:32           ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-15  6:32 UTC (permalink / raw)
  To: Mark Rutland
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	Andrey Ryabinin, linuxppc-dev, dvyukov


> There is a potential problem here, as Will Deacon wrote up at:
>
>   https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
>
> ... in the section starting:
>
> | *** Other architecture maintainers -- start here! ***
>
> ... whereby the CPU can spuriously fault on an access after observing a
> valid PTE.
>
> For arm64 we handle the spurious fault, and it looks like x86 would need
> something like its vmalloc_fault() applying to the shadow region to
> cater for this.

I'm not really up on x86 - my first thought would be that their stronger
memory ordering might be sufficient but I really don't know. Reading the
thread I see arm and powerpc discussions but nothing from anyone else,
so I'm none the wiser there...

Andy, do you have any thoughts?

Regards,
Daniel

>
> Thanks,
> Mark.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-14 13:57     ` Daniel Axtens
  2019-10-14 15:27         ` Mark Rutland
  2019-10-15  6:29       ` Daniel Axtens
@ 2019-10-16 12:19       ` Andrey Ryabinin
  2019-10-16 13:22           ` Mark Rutland
  2 siblings, 1 reply; 38+ messages in thread
From: Andrey Ryabinin @ 2019-10-16 12:19 UTC (permalink / raw)
  To: Daniel Axtens, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, mark.rutland, dvyukov, christophe.leroy
  Cc: linuxppc-dev, gor


On 10/14/19 4:57 PM, Daniel Axtens wrote:
> Hi Andrey,
> 
> 
>>> +	/*
>>> +	 * Ensure poisoning is visible before the shadow is made visible
>>> +	 * to other CPUs.
>>> +	 */
>>> +	smp_wmb();
>>
>> I'm not quite understand what this barrier do and why it needed.
>> And if it's really needed there should be a pairing barrier
>> on the other side which I don't see.
> 
> Mark might be better able to answer this, but my understanding is that
> we want to make sure that we never have a situation where the writes are
> reordered so that PTE is installed before all the poisioning is written
> out. I think it follows the logic in __pte_alloc() in mm/memory.c:
> 
> 	/*
> 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
> 	 * visible before the pte is made visible to other CPUs by being
> 	 * put into page tables.
> 	 *
> 	 * The other side of the story is the pointer chasing in the page
> 	 * table walking code (when walking the page table without locking;
> 	 * ie. most of the time). Fortunately, these data accesses consist
> 	 * of a chain of data-dependent loads, meaning most CPUs (alpha
> 	 * being the notable exception) will already guarantee loads are
> 	 * seen in-order. See the alpha page table accessors for the
> 	 * smp_read_barrier_depends() barriers in page table walking code.
> 	 */
> 	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */
> 
> I can clarify the comment.
> 

I don't see how is this relevant here.

barrier in __pte_alloc() for very the following case:

CPU 0							CPU 1
__pte_alloc():                                          pte_offset_kernel(pmd_t * dir, unsigned long address):
     pgtable_t new = pte_alloc_one(mm);                        pte_t *new = (pte_t *) pmd_page_vaddr(*dir) + ((address >> PAGE_SHIFT) & (PTRS_PER_PAGE - 1));  
     smp_wmb();                                                smp_read_barrier_depends();
     pmd_populate(mm, pmd, new);
							/* do something with pte, e.g. check if (pte_none(*new)) */


It's needed to ensure that if CPU1 sees pmd_populate() it also sees initialized contents of the 'new'.

In our case the barrier would have been needed if we had the other side like this:

if (!pte_none(*vmalloc_shadow_pte)) {
	shadow_addr = (unsigned long)__va(pte_pfn(*vmalloc_shadow_pte) << PAGE_SHIFT);
	smp_read_barrier_depends();
	*shadow_addr; /* read the shadow, barrier ensures that if we see installed pte, we will see initialized shadow memory. */
}


Without such other side the barrier is pointless.

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-16 12:19       ` Andrey Ryabinin
@ 2019-10-16 13:22           ` Mark Rutland
  0 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-16 13:22 UTC (permalink / raw)
  To: Andrey Ryabinin
  Cc: Daniel Axtens, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, dvyukov, christophe.leroy, linuxppc-dev, gor

Hi Andrey,

On Wed, Oct 16, 2019 at 03:19:50PM +0300, Andrey Ryabinin wrote:
> On 10/14/19 4:57 PM, Daniel Axtens wrote:
> >>> +	/*
> >>> +	 * Ensure poisoning is visible before the shadow is made visible
> >>> +	 * to other CPUs.
> >>> +	 */
> >>> +	smp_wmb();
> >>
> >> I'm not quite understand what this barrier do and why it needed.
> >> And if it's really needed there should be a pairing barrier
> >> on the other side which I don't see.
> > 
> > Mark might be better able to answer this, but my understanding is that
> > we want to make sure that we never have a situation where the writes are
> > reordered so that PTE is installed before all the poisioning is written
> > out. I think it follows the logic in __pte_alloc() in mm/memory.c:
> > 
> > 	/*
> > 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
> > 	 * visible before the pte is made visible to other CPUs by being
> > 	 * put into page tables.
> > 	 *
> > 	 * The other side of the story is the pointer chasing in the page
> > 	 * table walking code (when walking the page table without locking;
> > 	 * ie. most of the time). Fortunately, these data accesses consist
> > 	 * of a chain of data-dependent loads, meaning most CPUs (alpha
> > 	 * being the notable exception) will already guarantee loads are
> > 	 * seen in-order. See the alpha page table accessors for the
> > 	 * smp_read_barrier_depends() barriers in page table walking code.
> > 	 */
> > 	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */
> > 
> > I can clarify the comment.
> 
> I don't see how is this relevant here.

The problem isn't quite the same, but it's a similar shape. See below
for more details.

> barrier in __pte_alloc() for very the following case:
> 
> CPU 0							CPU 1
> __pte_alloc():                                          pte_offset_kernel(pmd_t * dir, unsigned long address):
>      pgtable_t new = pte_alloc_one(mm);                        pte_t *new = (pte_t *) pmd_page_vaddr(*dir) + ((address >> PAGE_SHIFT) & (PTRS_PER_PAGE - 1));  
>      smp_wmb();                                                smp_read_barrier_depends();
>      pmd_populate(mm, pmd, new);
> 							/* do something with pte, e.g. check if (pte_none(*new)) */
> 
> 
> It's needed to ensure that if CPU1 sees pmd_populate() it also sees initialized contents of the 'new'.
> 
> In our case the barrier would have been needed if we had the other side like this:
> 
> if (!pte_none(*vmalloc_shadow_pte)) {
> 	shadow_addr = (unsigned long)__va(pte_pfn(*vmalloc_shadow_pte) << PAGE_SHIFT);
> 	smp_read_barrier_depends();
> 	*shadow_addr; /* read the shadow, barrier ensures that if we see installed pte, we will see initialized shadow memory. */
> }
> 
> 
> Without such other side the barrier is pointless.

The barrier isn't pointless, but we are relying on a subtlety that is
not captured in LKMM, as one of the observers involved is the TLB (and
associated page table walkers) of the CPU.

Until the PTE written by CPU 0 has been observed by the TLB of CPU 1, it
is not possible for CPU 1 to satisfy loads from the memory that PTE
maps, as it doesn't yet know which memory that is.

Once the PTE written by CPU has been observed by the TLB of CPU 1, it is
possible for CPU 1 to satisfy those loads. At this instant, CPU 1 must
respect the smp_wmb() before the PTE was written, and hence sees zeroes
written before this. Note that if this were not true, we could not
safely swap userspace memory.

There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
loads of the shadow memory above the load of the PTE, samples a stale
(faulting) status from the TLB, then performs the load of the PTE and
sees a valid value. In this case (on arm64) a spurious fault could be
taken when the access is architecturally performed.

It is possible on arm64 to use a barrier here to prevent the spurious
fault, but this is not smp_read_barrier_depends(), as that does nothing
for everyone but alpha. On arm64 We have a spurious fault handler to fix
this up.

Thanks,
Mark.

[1] https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
[2] https://lore.kernel.org/linux-mm/20191014152717.GA20438@lakrids.cambridge.arm.com/

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-16 13:22           ` Mark Rutland
  0 siblings, 0 replies; 38+ messages in thread
From: Mark Rutland @ 2019-10-16 13:22 UTC (permalink / raw)
  To: Andrey Ryabinin
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	linuxppc-dev, dvyukov, Daniel Axtens

Hi Andrey,

On Wed, Oct 16, 2019 at 03:19:50PM +0300, Andrey Ryabinin wrote:
> On 10/14/19 4:57 PM, Daniel Axtens wrote:
> >>> +	/*
> >>> +	 * Ensure poisoning is visible before the shadow is made visible
> >>> +	 * to other CPUs.
> >>> +	 */
> >>> +	smp_wmb();
> >>
> >> I'm not quite understand what this barrier do and why it needed.
> >> And if it's really needed there should be a pairing barrier
> >> on the other side which I don't see.
> > 
> > Mark might be better able to answer this, but my understanding is that
> > we want to make sure that we never have a situation where the writes are
> > reordered so that PTE is installed before all the poisioning is written
> > out. I think it follows the logic in __pte_alloc() in mm/memory.c:
> > 
> > 	/*
> > 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
> > 	 * visible before the pte is made visible to other CPUs by being
> > 	 * put into page tables.
> > 	 *
> > 	 * The other side of the story is the pointer chasing in the page
> > 	 * table walking code (when walking the page table without locking;
> > 	 * ie. most of the time). Fortunately, these data accesses consist
> > 	 * of a chain of data-dependent loads, meaning most CPUs (alpha
> > 	 * being the notable exception) will already guarantee loads are
> > 	 * seen in-order. See the alpha page table accessors for the
> > 	 * smp_read_barrier_depends() barriers in page table walking code.
> > 	 */
> > 	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */
> > 
> > I can clarify the comment.
> 
> I don't see how is this relevant here.

The problem isn't quite the same, but it's a similar shape. See below
for more details.

> barrier in __pte_alloc() for very the following case:
> 
> CPU 0							CPU 1
> __pte_alloc():                                          pte_offset_kernel(pmd_t * dir, unsigned long address):
>      pgtable_t new = pte_alloc_one(mm);                        pte_t *new = (pte_t *) pmd_page_vaddr(*dir) + ((address >> PAGE_SHIFT) & (PTRS_PER_PAGE - 1));  
>      smp_wmb();                                                smp_read_barrier_depends();
>      pmd_populate(mm, pmd, new);
> 							/* do something with pte, e.g. check if (pte_none(*new)) */
> 
> 
> It's needed to ensure that if CPU1 sees pmd_populate() it also sees initialized contents of the 'new'.
> 
> In our case the barrier would have been needed if we had the other side like this:
> 
> if (!pte_none(*vmalloc_shadow_pte)) {
> 	shadow_addr = (unsigned long)__va(pte_pfn(*vmalloc_shadow_pte) << PAGE_SHIFT);
> 	smp_read_barrier_depends();
> 	*shadow_addr; /* read the shadow, barrier ensures that if we see installed pte, we will see initialized shadow memory. */
> }
> 
> 
> Without such other side the barrier is pointless.

The barrier isn't pointless, but we are relying on a subtlety that is
not captured in LKMM, as one of the observers involved is the TLB (and
associated page table walkers) of the CPU.

Until the PTE written by CPU 0 has been observed by the TLB of CPU 1, it
is not possible for CPU 1 to satisfy loads from the memory that PTE
maps, as it doesn't yet know which memory that is.

Once the PTE written by CPU has been observed by the TLB of CPU 1, it is
possible for CPU 1 to satisfy those loads. At this instant, CPU 1 must
respect the smp_wmb() before the PTE was written, and hence sees zeroes
written before this. Note that if this were not true, we could not
safely swap userspace memory.

There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
loads of the shadow memory above the load of the PTE, samples a stale
(faulting) status from the TLB, then performs the load of the PTE and
sees a valid value. In this case (on arm64) a spurious fault could be
taken when the access is architecturally performed.

It is possible on arm64 to use a barrier here to prevent the spurious
fault, but this is not smp_read_barrier_depends(), as that does nothing
for everyone but alpha. On arm64 We have a spurious fault handler to fix
this up.

Thanks,
Mark.

[1] https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
[2] https://lore.kernel.org/linux-mm/20191014152717.GA20438@lakrids.cambridge.arm.com/

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-16 13:22           ` Mark Rutland
@ 2019-10-18 10:43             ` Andrey Ryabinin
  -1 siblings, 0 replies; 38+ messages in thread
From: Andrey Ryabinin @ 2019-10-18 10:43 UTC (permalink / raw)
  To: Mark Rutland
  Cc: Daniel Axtens, kasan-dev, linux-mm, x86, glider, luto,
	linux-kernel, dvyukov, christophe.leroy, linuxppc-dev, gor



On 10/16/19 4:22 PM, Mark Rutland wrote:
> Hi Andrey,
> 
> On Wed, Oct 16, 2019 at 03:19:50PM +0300, Andrey Ryabinin wrote:
>> On 10/14/19 4:57 PM, Daniel Axtens wrote:
>>>>> +	/*
>>>>> +	 * Ensure poisoning is visible before the shadow is made visible
>>>>> +	 * to other CPUs.
>>>>> +	 */
>>>>> +	smp_wmb();
>>>>
>>>> I'm not quite understand what this barrier do and why it needed.
>>>> And if it's really needed there should be a pairing barrier
>>>> on the other side which I don't see.
>>>
>>> Mark might be better able to answer this, but my understanding is that
>>> we want to make sure that we never have a situation where the writes are
>>> reordered so that PTE is installed before all the poisioning is written
>>> out. I think it follows the logic in __pte_alloc() in mm/memory.c:
>>>
>>> 	/*
>>> 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
>>> 	 * visible before the pte is made visible to other CPUs by being
>>> 	 * put into page tables.
>>> 	 *
>>> 	 * The other side of the story is the pointer chasing in the page
>>> 	 * table walking code (when walking the page table without locking;
>>> 	 * ie. most of the time). Fortunately, these data accesses consist
>>> 	 * of a chain of data-dependent loads, meaning most CPUs (alpha
>>> 	 * being the notable exception) will already guarantee loads are
>>> 	 * seen in-order. See the alpha page table accessors for the
>>> 	 * smp_read_barrier_depends() barriers in page table walking code.
>>> 	 */
>>> 	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */
>>>
>>> I can clarify the comment.
>>
>> I don't see how is this relevant here.
> 
> The problem isn't quite the same, but it's a similar shape. See below
> for more details.
> 
>> barrier in __pte_alloc() for very the following case:
>>
>> CPU 0							CPU 1
>> __pte_alloc():                                          pte_offset_kernel(pmd_t * dir, unsigned long address):
>>      pgtable_t new = pte_alloc_one(mm);                        pte_t *new = (pte_t *) pmd_page_vaddr(*dir) + ((address >> PAGE_SHIFT) & (PTRS_PER_PAGE - 1));  
>>      smp_wmb();                                                smp_read_barrier_depends();
>>      pmd_populate(mm, pmd, new);
>> 							/* do something with pte, e.g. check if (pte_none(*new)) */
>>
>>
>> It's needed to ensure that if CPU1 sees pmd_populate() it also sees initialized contents of the 'new'.
>>
>> In our case the barrier would have been needed if we had the other side like this:
>>
>> if (!pte_none(*vmalloc_shadow_pte)) {
>> 	shadow_addr = (unsigned long)__va(pte_pfn(*vmalloc_shadow_pte) << PAGE_SHIFT);
>> 	smp_read_barrier_depends();
>> 	*shadow_addr; /* read the shadow, barrier ensures that if we see installed pte, we will see initialized shadow memory. */
>> }
>>
>>
>> Without such other side the barrier is pointless.
> 
> The barrier isn't pointless, but we are relying on a subtlety that is
> not captured in LKMM, as one of the observers involved is the TLB (and
> associated page table walkers) of the CPU.
> 
> Until the PTE written by CPU 0 has been observed by the TLB of CPU 1, it
> is not possible for CPU 1 to satisfy loads from the memory that PTE
> maps, as it doesn't yet know which memory that is.
> 
> Once the PTE written by CPU has been observed by the TLB of CPU 1, it is
> possible for CPU 1 to satisfy those loads. At this instant, CPU 1 must
> respect the smp_wmb() before the PTE was written, and hence sees zeroes
                                                                 s/zeroes/poison values

> written before this. Note that if this were not true, we could not
> safely swap userspace memory.
> 
> There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
> loads of the shadow memory above the load of the PTE, samples a stale
> (faulting) status from the TLB, then performs the load of the PTE and
> sees a valid value. In this case (on arm64) a spurious fault could be
> taken when the access is architecturally performed.
> 
> It is possible on arm64 to use a barrier here to prevent the spurious
> fault, but this is not smp_read_barrier_depends(), as that does nothing
> for everyone but alpha. On arm64 We have a spurious fault handler to fix
> this up.
>  

None of that really explains how the race looks like.
Please, describe concrete race race condition diagram starting with something like

CPU0                   CPU1
p0 = vmalloc()         p1 = vmalloc()
...




Or let me put it this way. Let's assume that CPU0 accesses shadow and CPU1 did the memset() and installed pte.
CPU0 may not observe memset() only if it dereferences completely random vmalloc addresses
or it performs out-of-bounds access which crosses KASAN_SHADOW_SCALE*PAGE_SIZE boundary, i.e. access to shadow crosses page boundary.
In both cases it will be hard to avoid crashes. OOB crossing the page boundary in vmalloc pretty much guarantees crash because of guard page,
and derefencing random address isn't going to last for long.

If CPU0 obtained pointer via vmalloc() call and it's doing out-of-bounds (within boundaries of the page) or use-after-free,
than the spin_[un]lock(&init_mm.page_table_lock) should allow CPU0 to see the memset done by CPU1 without any additional barrier.


^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-18 10:43             ` Andrey Ryabinin
  0 siblings, 0 replies; 38+ messages in thread
From: Andrey Ryabinin @ 2019-10-18 10:43 UTC (permalink / raw)
  To: Mark Rutland
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	linuxppc-dev, dvyukov, Daniel Axtens



On 10/16/19 4:22 PM, Mark Rutland wrote:
> Hi Andrey,
> 
> On Wed, Oct 16, 2019 at 03:19:50PM +0300, Andrey Ryabinin wrote:
>> On 10/14/19 4:57 PM, Daniel Axtens wrote:
>>>>> +	/*
>>>>> +	 * Ensure poisoning is visible before the shadow is made visible
>>>>> +	 * to other CPUs.
>>>>> +	 */
>>>>> +	smp_wmb();
>>>>
>>>> I'm not quite understand what this barrier do and why it needed.
>>>> And if it's really needed there should be a pairing barrier
>>>> on the other side which I don't see.
>>>
>>> Mark might be better able to answer this, but my understanding is that
>>> we want to make sure that we never have a situation where the writes are
>>> reordered so that PTE is installed before all the poisioning is written
>>> out. I think it follows the logic in __pte_alloc() in mm/memory.c:
>>>
>>> 	/*
>>> 	 * Ensure all pte setup (eg. pte page lock and page clearing) are
>>> 	 * visible before the pte is made visible to other CPUs by being
>>> 	 * put into page tables.
>>> 	 *
>>> 	 * The other side of the story is the pointer chasing in the page
>>> 	 * table walking code (when walking the page table without locking;
>>> 	 * ie. most of the time). Fortunately, these data accesses consist
>>> 	 * of a chain of data-dependent loads, meaning most CPUs (alpha
>>> 	 * being the notable exception) will already guarantee loads are
>>> 	 * seen in-order. See the alpha page table accessors for the
>>> 	 * smp_read_barrier_depends() barriers in page table walking code.
>>> 	 */
>>> 	smp_wmb(); /* Could be smp_wmb__xxx(before|after)_spin_lock */
>>>
>>> I can clarify the comment.
>>
>> I don't see how is this relevant here.
> 
> The problem isn't quite the same, but it's a similar shape. See below
> for more details.
> 
>> barrier in __pte_alloc() for very the following case:
>>
>> CPU 0							CPU 1
>> __pte_alloc():                                          pte_offset_kernel(pmd_t * dir, unsigned long address):
>>      pgtable_t new = pte_alloc_one(mm);                        pte_t *new = (pte_t *) pmd_page_vaddr(*dir) + ((address >> PAGE_SHIFT) & (PTRS_PER_PAGE - 1));  
>>      smp_wmb();                                                smp_read_barrier_depends();
>>      pmd_populate(mm, pmd, new);
>> 							/* do something with pte, e.g. check if (pte_none(*new)) */
>>
>>
>> It's needed to ensure that if CPU1 sees pmd_populate() it also sees initialized contents of the 'new'.
>>
>> In our case the barrier would have been needed if we had the other side like this:
>>
>> if (!pte_none(*vmalloc_shadow_pte)) {
>> 	shadow_addr = (unsigned long)__va(pte_pfn(*vmalloc_shadow_pte) << PAGE_SHIFT);
>> 	smp_read_barrier_depends();
>> 	*shadow_addr; /* read the shadow, barrier ensures that if we see installed pte, we will see initialized shadow memory. */
>> }
>>
>>
>> Without such other side the barrier is pointless.
> 
> The barrier isn't pointless, but we are relying on a subtlety that is
> not captured in LKMM, as one of the observers involved is the TLB (and
> associated page table walkers) of the CPU.
> 
> Until the PTE written by CPU 0 has been observed by the TLB of CPU 1, it
> is not possible for CPU 1 to satisfy loads from the memory that PTE
> maps, as it doesn't yet know which memory that is.
> 
> Once the PTE written by CPU has been observed by the TLB of CPU 1, it is
> possible for CPU 1 to satisfy those loads. At this instant, CPU 1 must
> respect the smp_wmb() before the PTE was written, and hence sees zeroes
                                                                 s/zeroes/poison values

> written before this. Note that if this were not true, we could not
> safely swap userspace memory.
> 
> There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
> loads of the shadow memory above the load of the PTE, samples a stale
> (faulting) status from the TLB, then performs the load of the PTE and
> sees a valid value. In this case (on arm64) a spurious fault could be
> taken when the access is architecturally performed.
> 
> It is possible on arm64 to use a barrier here to prevent the spurious
> fault, but this is not smp_read_barrier_depends(), as that does nothing
> for everyone but alpha. On arm64 We have a spurious fault handler to fix
> this up.
>  

None of that really explains how the race looks like.
Please, describe concrete race race condition diagram starting with something like

CPU0                   CPU1
p0 = vmalloc()         p1 = vmalloc()
...




Or let me put it this way. Let's assume that CPU0 accesses shadow and CPU1 did the memset() and installed pte.
CPU0 may not observe memset() only if it dereferences completely random vmalloc addresses
or it performs out-of-bounds access which crosses KASAN_SHADOW_SCALE*PAGE_SIZE boundary, i.e. access to shadow crosses page boundary.
In both cases it will be hard to avoid crashes. OOB crossing the page boundary in vmalloc pretty much guarantees crash because of guard page,
and derefencing random address isn't going to last for long.

If CPU0 obtained pointer via vmalloc() call and it's doing out-of-bounds (within boundaries of the page) or use-after-free,
than the spin_[un]lock(&init_mm.page_table_lock) should allow CPU0 to see the memset done by CPU1 without any additional barrier.


^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-16 13:22           ` Mark Rutland
@ 2019-10-28  1:26             ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-28  1:26 UTC (permalink / raw)
  To: Mark Rutland, Andrey Ryabinin
  Cc: kasan-dev, linux-mm, x86, glider, luto, linux-kernel, dvyukov,
	christophe.leroy, linuxppc-dev, gor

Hi Mark and Andrey,

I've spent some quality time with the barrier documentation and
all of your emails.

I'm still trying to puzzle out the barrier. The memory model
documentation doesn't talk about how synchronisation works when a
page-table walk is involved, so that's making things hard. However, I
think I have something for the spurious fault case. Apologies for the
length, and for any mistakes!

I am assuming here that the poison and zeros and PTEs are correctly
being stored and we're just concerned about whether an architecturally
correct load can cause a spurious fault on x86.

> There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
> loads of the shadow memory above the load of the PTE, samples a stale
> (faulting) status from the TLB, then performs the load of the PTE and
> sees a valid value. In this case (on arm64) a spurious fault could be
> taken when the access is architecturally performed.
>
> It is possible on arm64 to use a barrier here to prevent the spurious
> fault, but this is not smp_read_barrier_depends(), as that does nothing
> for everyone but alpha. On arm64 We have a spurious fault handler to fix
> this up.

Will's email has the following example:

	CPU 0				CPU 1
	-----				-----
	spin_lock(&lock);		spin_lock(&lock);
	set_fixmap(0, paddr, prot);	if (mapped)
	mapped = true;				foo = *fix_to_virt(0);
	spin_unlock(&lock);		spin_unlock(&lock);


If I understand the following properly, it's because of a quirk in
ARM, the translation of fix_to_virt(0) can escape outside the lock:

>   DDI0487E_a, B2-125:
> 
>   | DMB and DSB instructions affect reads and writes to the memory system
>   | generated by Load/Store instructions and data or unified cache maintenance
>   | instructions being executed by the PE. Instruction fetches or accesses
>   | caused by a hardware translation table access are not explicit accesses.
> 
> which appears to claim that the DSB alone is insufficient. Unfortunately,
> some CPU designers have followed the second clause above, whereas in Linux
> we've been relying on the first. This means that our mapping sequence:
> 
> 	MOV	X0, <valid pte> 
> 	STR	X0, [Xptep]	// Store new PTE to page table
> 	DSB	ISHST
> 	LDR	X1, [X2]	// Translates using the new PTE
> 
> can actually raise a translation fault on the load instruction because the
> translation can be performed speculatively before the page table update and
> then marked as "faulting" by the CPU. For user PTEs, this is ok because we
> can handle the spurious fault, but for kernel PTEs and intermediate table
> entries this results in a panic().

So the DSB isn't sufficient to stop the CPU speculating the
_translation_ above the page table store - to do that you need an
ISB. [I'm not an ARM person so apologies if I've butchered this!] Then
the load then uses the speculated translation and faults.

So, do we need to do something to protect ourselves against the case of
these sorts of spurious faults on x86? I'm also not an x86 person, so
again apologies in advance if I've butchered anything.

Firstly, it's not trivial to get a fixed address from the vmalloc
infrastructure - you have to do something like
__vmalloc_node_range(size, align, fixed_start_address, fixed_start_address + size, ...)
I don't see any callers doing that. But we press on just in case.

Section 4.10.2.3 of Book 3 of the Intel Developers Manual says:

 | The processor may cache translations required for prefetches and for
 | accesses that are a result of speculative execution that would never
 | actually occur in the executed code path.

That's all it says, it doesn't say if it will cache a negative or
faulting lookup in the speculative case. However, if you _could_ cache
a negative result, you'd hope the documentation on when to invalidate
would tell you. That's in 4.10.4.

4.10.4.3 Optional Invalidations includes:

 | The read of a paging-structure entry in translating an address being
 | used to fetch an instruction may appear to execute before an earlier
 | write to that paging-structure entry if there is no serializing
 | instruction between the write and the instruction fetch. Note that
 | the invalidating instructions identified in Section 4.10.4.1 are all
 | serializing instructions.

That only applies to _instruction fetch_, not data fetch. There's no
corresponding dot point for data fetch, suggesting that data fetches
aren't subject to this.

Lastly, arch/x86's native_set_pte_at() performs none of the extra
barriers that ARM does - this also suggests to me that this isn't a
concern on x86. Perhaps page-table walking for data fetches is able to
snoop the store queues, and that's how they get around it.

Given that analysis, that x86 has generally strong memory ordering, and
the lack of response to Will's email from x86ers, I think we probably do
not need a spurious fault handler on x86. (Although I'd love to hear
from any actual x86 experts on this!) Other architecture enablement will
have to do their own analysis.

As I said up top, I'm still puzzling through the smp_wmb() discussion
and I hope to have something for that soon.

Regards,
Daniel

>
> Thanks,
> Mark.
>
> [1] https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
> [2] https://lore.kernel.org/linux-mm/20191014152717.GA20438@lakrids.cambridge.arm.com/

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-28  1:26             ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-28  1:26 UTC (permalink / raw)
  To: Mark Rutland, Andrey Ryabinin
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	linuxppc-dev, dvyukov

Hi Mark and Andrey,

I've spent some quality time with the barrier documentation and
all of your emails.

I'm still trying to puzzle out the barrier. The memory model
documentation doesn't talk about how synchronisation works when a
page-table walk is involved, so that's making things hard. However, I
think I have something for the spurious fault case. Apologies for the
length, and for any mistakes!

I am assuming here that the poison and zeros and PTEs are correctly
being stored and we're just concerned about whether an architecturally
correct load can cause a spurious fault on x86.

> There is the risk (as laid out in [1]) that CPU 1 attempts to hoist the
> loads of the shadow memory above the load of the PTE, samples a stale
> (faulting) status from the TLB, then performs the load of the PTE and
> sees a valid value. In this case (on arm64) a spurious fault could be
> taken when the access is architecturally performed.
>
> It is possible on arm64 to use a barrier here to prevent the spurious
> fault, but this is not smp_read_barrier_depends(), as that does nothing
> for everyone but alpha. On arm64 We have a spurious fault handler to fix
> this up.

Will's email has the following example:

	CPU 0				CPU 1
	-----				-----
	spin_lock(&lock);		spin_lock(&lock);
	set_fixmap(0, paddr, prot);	if (mapped)
	mapped = true;				foo = *fix_to_virt(0);
	spin_unlock(&lock);		spin_unlock(&lock);


If I understand the following properly, it's because of a quirk in
ARM, the translation of fix_to_virt(0) can escape outside the lock:

>   DDI0487E_a, B2-125:
> 
>   | DMB and DSB instructions affect reads and writes to the memory system
>   | generated by Load/Store instructions and data or unified cache maintenance
>   | instructions being executed by the PE. Instruction fetches or accesses
>   | caused by a hardware translation table access are not explicit accesses.
> 
> which appears to claim that the DSB alone is insufficient. Unfortunately,
> some CPU designers have followed the second clause above, whereas in Linux
> we've been relying on the first. This means that our mapping sequence:
> 
> 	MOV	X0, <valid pte> 
> 	STR	X0, [Xptep]	// Store new PTE to page table
> 	DSB	ISHST
> 	LDR	X1, [X2]	// Translates using the new PTE
> 
> can actually raise a translation fault on the load instruction because the
> translation can be performed speculatively before the page table update and
> then marked as "faulting" by the CPU. For user PTEs, this is ok because we
> can handle the spurious fault, but for kernel PTEs and intermediate table
> entries this results in a panic().

So the DSB isn't sufficient to stop the CPU speculating the
_translation_ above the page table store - to do that you need an
ISB. [I'm not an ARM person so apologies if I've butchered this!] Then
the load then uses the speculated translation and faults.

So, do we need to do something to protect ourselves against the case of
these sorts of spurious faults on x86? I'm also not an x86 person, so
again apologies in advance if I've butchered anything.

Firstly, it's not trivial to get a fixed address from the vmalloc
infrastructure - you have to do something like
__vmalloc_node_range(size, align, fixed_start_address, fixed_start_address + size, ...)
I don't see any callers doing that. But we press on just in case.

Section 4.10.2.3 of Book 3 of the Intel Developers Manual says:

 | The processor may cache translations required for prefetches and for
 | accesses that are a result of speculative execution that would never
 | actually occur in the executed code path.

That's all it says, it doesn't say if it will cache a negative or
faulting lookup in the speculative case. However, if you _could_ cache
a negative result, you'd hope the documentation on when to invalidate
would tell you. That's in 4.10.4.

4.10.4.3 Optional Invalidations includes:

 | The read of a paging-structure entry in translating an address being
 | used to fetch an instruction may appear to execute before an earlier
 | write to that paging-structure entry if there is no serializing
 | instruction between the write and the instruction fetch. Note that
 | the invalidating instructions identified in Section 4.10.4.1 are all
 | serializing instructions.

That only applies to _instruction fetch_, not data fetch. There's no
corresponding dot point for data fetch, suggesting that data fetches
aren't subject to this.

Lastly, arch/x86's native_set_pte_at() performs none of the extra
barriers that ARM does - this also suggests to me that this isn't a
concern on x86. Perhaps page-table walking for data fetches is able to
snoop the store queues, and that's how they get around it.

Given that analysis, that x86 has generally strong memory ordering, and
the lack of response to Will's email from x86ers, I think we probably do
not need a spurious fault handler on x86. (Although I'd love to hear
from any actual x86 experts on this!) Other architecture enablement will
have to do their own analysis.

As I said up top, I'm still puzzling through the smp_wmb() discussion
and I hope to have something for that soon.

Regards,
Daniel

>
> Thanks,
> Mark.
>
> [1] https://lore.kernel.org/linux-arm-kernel/20190827131818.14724-1-will@kernel.org/
> [2] https://lore.kernel.org/linux-mm/20191014152717.GA20438@lakrids.cambridge.arm.com/

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
  2019-10-18 10:43             ` Andrey Ryabinin
@ 2019-10-28  7:39               ` Daniel Axtens
  -1 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-28  7:39 UTC (permalink / raw)
  To: Andrey Ryabinin, Mark Rutland
  Cc: kasan-dev, linux-mm, x86, glider, luto, linux-kernel, dvyukov,
	christophe.leroy, linuxppc-dev, gor

> Or let me put it this way. Let's assume that CPU0 accesses shadow and CPU1 did the memset() and installed pte.
> CPU0 may not observe memset() only if it dereferences completely random vmalloc addresses
> or it performs out-of-bounds access which crosses KASAN_SHADOW_SCALE*PAGE_SIZE boundary, i.e. access to shadow crosses page boundary.
> In both cases it will be hard to avoid crashes. OOB crossing the page boundary in vmalloc pretty much guarantees crash because of guard page,
> and derefencing random address isn't going to last for long.
>
> If CPU0 obtained pointer via vmalloc() call and it's doing out-of-bounds (within boundaries of the page) or use-after-free,
> than the spin_[un]lock(&init_mm.page_table_lock) should allow CPU0 to see the memset done by CPU1 without any additional barrier.


I have puzzled through the barrier stuff. Here's what I
have. Apologies for the length, and for any mistakes - I'm pretty new
to deep kernel memory model stuff!

One thing that I don't think we've considered so far is _un_poisioning:


|	ret = apply_to_page_range(&init_mm, shadow_start,
|				  shadow_end - shadow_start,
|				  kasan_populate_vmalloc_pte, NULL);
|	if (ret)
|		return ret;
|
|	kasan_unpoison_shadow(area->addr, requested_size);

That unpoisioning is going to write to the shadow via its virtual
address, loading translations into the TLB. So we cannot assume that
another CPU is doing the page table walk and loading the TLB entry for
the first time. We need to make sure that correctness does not depend
on that.

We have 2x2 cases to consider:

{Access via fixed address, access via unknown address}
x
{Access within object - unpoisioned, access just beyond object but
within shadow - poisoned}

I think we can first drop all consideration of access via fixed
addresses. Such accesses will have to be synchronised via some
external mechanism, such as a flag, with appropriate
locking/barriers. Those barriers will order the rest of the memory
accesses within vmalloc(), and I considered speculative faults in my
other email.

That leaves just memory accesses via an unknown address. I'm imagining
the following two cases:

[Access of Unpoisoned Shadow - valid access]

CPU#0                                   CPU#1
-----                                   -----
WRITE_ONCE(p, vmalloc(100))             while (!(x = READ_ONCE(p))) ;
                                        x[99] = 1;

[Access of Poisoned Shadow - invalid read past the end]

CPU#0                                   CPU#1
-----                                   -----
WRITE_ONCE(p, vmalloc(100))             while (!(x = READ_ONCE(p))) ;
                                        x[100] = 1;


---------- Access to the unpoisioned region of shadow ----------

Expanding the CPU#0 side, let `a` be area->addr:

// kasan_populate_vmalloc_pte
...
STORE page+PAGE_SIZE-1, poison
// Mark's proposed smp_wmb() goes here
ACQUIRE page_table_lock
STORE ptep, pte
RELEASE page_table_lock
// return to kasan_populate_vmalloc
// call kasan_unpoison_shadow(a, 100)
STORE shadow(a), unpoison
...
STORE shadow(a+99), unpoison
// rest of vmalloc()
STORE p, a


CPU#1 looks like (removing the loop bit):

x = LOAD p
<data dependency>
shadow_x = LOAD *shadow(x+99)
// if shadow_x poisoned, report
STORE (x+99), 1

Putting the last few operations side-by-side:

CPU#0                                    CPU#1
 STORE shadow(a+99), unpoision           x = LOAD p
                                         <data dependency>
 STORE p, a                              shadow_x = LOAD shadow(x+99)


While there is a data dependency between x and shadow_x, there's no
barrier in kasan_populate_vmalloc() that forces the _un_poisoning to
be correctly ordered.

My worry would be that CPU#0 might commit the store to p before it
commits the store to the shadow. Then, even with the data dependency,
CPU#1 could observe store to shadow(a+99) after it executed the load
of shadow(x+99). This would lead CPU#1 to observe a false-positive
poison.

We need a write barrier, and Mark's proposed smp_wmb() is too early to
help here.

Now, there is an smp_wmb() in clear_vm_uninitialized_flag(), which is
called by __vmalloc_node_range between kasan_populate_vmalloc and the
end of the function. That makes things look like this:

  CPU#0                                   CPU#1
STORE shadow(a+99), unpoision           x = LOAD p
smp_wmb()                               <data dependency>
STORE p, a                              shadow_x = LOAD shadow(x+99)

memory-barriers.txt says that a data dependency and a write barrier
are sufficient to order this correctly.

Outside of __vmalloc_node_range(), the other times we call
kasan_populate_vmalloc() are:

 - get_vm_area() and friends. get_vm_area does not mapping any pages
   into the area returned. So the caller will have to do that, which
   will require taking the page table lock. A release should pair with
   a data dependency, making the unpoisoning visible.

 - The per_cpu allocator: again the caller has to map pages into the
   area returned - pcpu_map_pages calls map_kernel_range_noflush.

So, where the address is not known in advance, the unpoisioning does
need a barrier. However, we do hit one anyway before we return. We
should document that we're relying on the barrier in
clear_vm_uninitialized_flag() or barriers from other callers.

---------- Access to the poisioned region of shadow ----------

Now, what about the case that we do an overread that's still in the
shadow page?

CPU#0                                    CPU#1
 STORE page+100, poison
 ...
 # Mark's proposed smp_wmb()
 ACQUIRE page_table_lock
 STORE ptep, pte
 RELEASE page_table_lock
 ...
 STORE shadow(a+99), unpoision           x = LOAD p
 smp_wmb()                               <data dependency>
 STORE p, a                              shadow_x = LOAD shadow(x+100)


Here, because of both the release and the smp_wmb(), the store of the
poison will be safe. Because we're not expecting anything funky with
fixed addresses or other CPUs doing page-table walks, I still think we
don't need an extra barrier where Mark has proposed.

-------------------- Conclusion --------------------

I will send a v10 that:

 - drops the smp_wmb() for poisoning
 
 - adds a comment that explains that we're dependent on later barriers
   for _un_poisioning

I'd really like to get this into the coming merge window, if at all
possible.

Regards,
Daniel

^ permalink raw reply	[flat|nested] 38+ messages in thread

* Re: [PATCH v8 1/5] kasan: support backing vmalloc space with real shadow memory
@ 2019-10-28  7:39               ` Daniel Axtens
  0 siblings, 0 replies; 38+ messages in thread
From: Daniel Axtens @ 2019-10-28  7:39 UTC (permalink / raw)
  To: Andrey Ryabinin, Mark Rutland
  Cc: gor, x86, linux-kernel, kasan-dev, linux-mm, glider, luto,
	linuxppc-dev, dvyukov

> Or let me put it this way. Let's assume that CPU0 accesses shadow and CPU1 did the memset() and installed pte.
> CPU0 may not observe memset() only if it dereferences completely random vmalloc addresses
> or it performs out-of-bounds access which crosses KASAN_SHADOW_SCALE*PAGE_SIZE boundary, i.e. access to shadow crosses page boundary.
> In both cases it will be hard to avoid crashes. OOB crossing the page boundary in vmalloc pretty much guarantees crash because of guard page,
> and derefencing random address isn't going to last for long.
>
> If CPU0 obtained pointer via vmalloc() call and it's doing out-of-bounds (within boundaries of the page) or use-after-free,
> than the spin_[un]lock(&init_mm.page_table_lock) should allow CPU0 to see the memset done by CPU1 without any additional barrier.


I have puzzled through the barrier stuff. Here's what I
have. Apologies for the length, and for any mistakes - I'm pretty new
to deep kernel memory model stuff!

One thing that I don't think we've considered so far is _un_poisioning:


|	ret = apply_to_page_range(&init_mm, shadow_start,
|				  shadow_end - shadow_start,
|				  kasan_populate_vmalloc_pte, NULL);
|	if (ret)
|		return ret;
|
|	kasan_unpoison_shadow(area->addr, requested_size);

That unpoisioning is going to write to the shadow via its virtual
address, loading translations into the TLB. So we cannot assume that
another CPU is doing the page table walk and loading the TLB entry for
the first time. We need to make sure that correctness does not depend
on that.

We have 2x2 cases to consider:

{Access via fixed address, access via unknown address}
x
{Access within object - unpoisioned, access just beyond object but
within shadow - poisoned}

I think we can first drop all consideration of access via fixed
addresses. Such accesses will have to be synchronised via some
external mechanism, such as a flag, with appropriate
locking/barriers. Those barriers will order the rest of the memory
accesses within vmalloc(), and I considered speculative faults in my
other email.

That leaves just memory accesses via an unknown address. I'm imagining
the following two cases:

[Access of Unpoisoned Shadow - valid access]

CPU#0                                   CPU#1
-----                                   -----
WRITE_ONCE(p, vmalloc(100))             while (!(x = READ_ONCE(p))) ;
                                        x[99] = 1;

[Access of Poisoned Shadow - invalid read past the end]

CPU#0                                   CPU#1
-----                                   -----
WRITE_ONCE(p, vmalloc(100))             while (!(x = READ_ONCE(p))) ;
                                        x[100] = 1;


---------- Access to the unpoisioned region of shadow ----------

Expanding the CPU#0 side, let `a` be area->addr:

// kasan_populate_vmalloc_pte
...
STORE page+PAGE_SIZE-1, poison
// Mark's proposed smp_wmb() goes here
ACQUIRE page_table_lock
STORE ptep, pte
RELEASE page_table_lock
// return to kasan_populate_vmalloc
// call kasan_unpoison_shadow(a, 100)
STORE shadow(a), unpoison
...
STORE shadow(a+99), unpoison
// rest of vmalloc()
STORE p, a


CPU#1 looks like (removing the loop bit):

x = LOAD p
<data dependency>
shadow_x = LOAD *shadow(x+99)
// if shadow_x poisoned, report
STORE (x+99), 1

Putting the last few operations side-by-side:

CPU#0                                    CPU#1
 STORE shadow(a+99), unpoision           x = LOAD p
                                         <data dependency>
 STORE p, a                              shadow_x = LOAD shadow(x+99)


While there is a data dependency between x and shadow_x, there's no
barrier in kasan_populate_vmalloc() that forces the _un_poisoning to
be correctly ordered.

My worry would be that CPU#0 might commit the store to p before it
commits the store to the shadow. Then, even with the data dependency,
CPU#1 could observe store to shadow(a+99) after it executed the load
of shadow(x+99). This would lead CPU#1 to observe a false-positive
poison.

We need a write barrier, and Mark's proposed smp_wmb() is too early to
help here.

Now, there is an smp_wmb() in clear_vm_uninitialized_flag(), which is
called by __vmalloc_node_range between kasan_populate_vmalloc and the
end of the function. That makes things look like this:

  CPU#0                                   CPU#1
STORE shadow(a+99), unpoision           x = LOAD p
smp_wmb()                               <data dependency>
STORE p, a                              shadow_x = LOAD shadow(x+99)

memory-barriers.txt says that a data dependency and a write barrier
are sufficient to order this correctly.

Outside of __vmalloc_node_range(), the other times we call
kasan_populate_vmalloc() are:

 - get_vm_area() and friends. get_vm_area does not mapping any pages
   into the area returned. So the caller will have to do that, which
   will require taking the page table lock. A release should pair with
   a data dependency, making the unpoisoning visible.

 - The per_cpu allocator: again the caller has to map pages into the
   area returned - pcpu_map_pages calls map_kernel_range_noflush.

So, where the address is not known in advance, the unpoisioning does
need a barrier. However, we do hit one anyway before we return. We
should document that we're relying on the barrier in
clear_vm_uninitialized_flag() or barriers from other callers.

---------- Access to the poisioned region of shadow ----------

Now, what about the case that we do an overread that's still in the
shadow page?

CPU#0                                    CPU#1
 STORE page+100, poison
 ...
 # Mark's proposed smp_wmb()
 ACQUIRE page_table_lock
 STORE ptep, pte
 RELEASE page_table_lock
 ...
 STORE shadow(a+99), unpoision           x = LOAD p
 smp_wmb()                               <data dependency>
 STORE p, a                              shadow_x = LOAD shadow(x+100)


Here, because of both the release and the smp_wmb(), the store of the
poison will be safe. Because we're not expecting anything funky with
fixed addresses or other CPUs doing page-table walks, I still think we
don't need an extra barrier where Mark has proposed.

-------------------- Conclusion --------------------

I will send a v10 that:

 - drops the smp_wmb() for poisoning
 
 - adds a comment that explains that we're dependent on later barriers
   for _un_poisioning

I'd really like to get this into the coming merge window, if at all
possible.

Regards,
Daniel

^ permalink raw reply	[flat|nested] 38+ messages in thread

end of thread, other threads:[~2019-10-28  7:41 UTC | newest]

Thread overview: 38+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-10-01  6:58 [PATCH v8 0/5] kasan: support backing vmalloc space with real shadow memory Daniel Axtens
2019-10-01  6:58 ` [PATCH v8 1/5] " Daniel Axtens
2019-10-01 10:17   ` Uladzislau Rezki
2019-10-01 10:17     ` Uladzislau Rezki
2019-10-02  1:23     ` Daniel Axtens
2019-10-02  1:23       ` Daniel Axtens
2019-10-02  7:13       ` Christophe Leroy
2019-10-02  7:13         ` Christophe Leroy
2019-10-02 11:49       ` Uladzislau Rezki
2019-10-02 11:49         ` Uladzislau Rezki
2019-10-07  8:02   ` Uladzislau Rezki
2019-10-07  8:02     ` Uladzislau Rezki
2019-10-11  5:15     ` Daniel Axtens
2019-10-11  5:15       ` Daniel Axtens
2019-10-11 19:57   ` Andrey Ryabinin
2019-10-14 13:57     ` Daniel Axtens
2019-10-14 15:27       ` Mark Rutland
2019-10-14 15:27         ` Mark Rutland
2019-10-15  6:32         ` Daniel Axtens
2019-10-15  6:32           ` Daniel Axtens
2019-10-15  6:29       ` Daniel Axtens
2019-10-16 12:19       ` Andrey Ryabinin
2019-10-16 13:22         ` Mark Rutland
2019-10-16 13:22           ` Mark Rutland
2019-10-18 10:43           ` Andrey Ryabinin
2019-10-18 10:43             ` Andrey Ryabinin
2019-10-28  7:39             ` Daniel Axtens
2019-10-28  7:39               ` Daniel Axtens
2019-10-28  1:26           ` Daniel Axtens
2019-10-28  1:26             ` Daniel Axtens
2019-10-14 15:43   ` Mark Rutland
2019-10-14 15:43     ` Mark Rutland
2019-10-15  6:27     ` Daniel Axtens
2019-10-15  6:27       ` Daniel Axtens
2019-10-01  6:58 ` [PATCH v8 2/5] kasan: add test for vmalloc Daniel Axtens
2019-10-01  6:58 ` [PATCH v8 3/5] fork: support VMAP_STACK with KASAN_VMALLOC Daniel Axtens
2019-10-01  6:58 ` [PATCH v8 4/5] x86/kasan: support KASAN_VMALLOC Daniel Axtens
2019-10-01  6:58 ` [PATCH v8 5/5] kasan debug: track pages allocated for vmalloc shadow Daniel Axtens

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.