Skip to contentSkip to conversation

kmsan: simplify kmsan_internal_memmove_metadata()

PATCH Superseded Alexander Potapenko 3 participants 5 messages Sep 7, 2023 – Sep 11, 2023

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Alexander Potapenko

author maintainer
#0 lore raw

PATCH 1/2 kmsan: simplify kmsan_internal_memmove_metadata()

kmsan_internal_memmove_metadata() is the function that implements copying metadata every time memcpy()/memmove() is called. Because shadow memory stores 1 byte per each byte of kernel memory, copying the shadow is trivial and can be done by a single memmove() call.
Origins, on the other hand, are stored as 4-byte values corresponding to every aligned 4 bytes of kernel memory. Therefore, if either the source or the destination of kmsan_internal_memmove_metadata() is unaligned, the number of origin slots corresponding to the source or destination may differ:

1) memcpy(0xffff888080a00000, 0xffff888080900000, 4) copies 1 origin slot into 1 origin slot:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): xxxx
dst origins: o111

2) memcpy(0xffff888080a00001, 0xffff888080900000, 4) copies 1 origin slot into 2 origin slots:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): .xxx x...
dst origins: o111 o111

3) memcpy(0xffff888080a00000, 0xffff888080900001, 4) copies 2 origin slots into 1 origin slot:

src (0xffff888080900000): .xxx x...
src origins: o111 o222
dst (0xffff888080a00000): xxxx
dst origins: o111
(or o222)

Previously, kmsan_internal_memmove_metadata() tried to solve this problem by copying min(src_slots, dst_slots) as is and cloning the missing slot on one of the ends, if needed.
This was error-prone even in the simple cases where 4 bytes were copied, and did not account for situations where the total number of nonzero origin slots could have increased by more than one after copying:

memcpy(0xffff888080a00000, 0xffff888080900002, 8)

src (0xffff888080900002): ..xx .... xx..
src origins: o111 0000 o222
dst (0xffff888080a00000): xx.. ..xx

                            o111 0000
                        (or 0000 o222)

The new implementation simply copies the shadow byte by byte, and updates the corresponding origin slot, if the shadow byte is nonzero. This approach can handle complex cases with mixed initialized and uninitialized bytes. Similarly to KMSAN inline instrumentation, latter writes to bytes sharing the same origin slots take precedence.

---
 mm/kmsan/core.c | 127 ++++++++++++------------------------------------
 1 file changed, 31 insertions(+), 96 deletions(-)
mm/kmsan/core.c +31 -96
index 3adb4c1d3b193..c19f47af04241 100644
@@ -83,131 +83,66 @@ depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags,
 /* Copy the metadata following the memmove() behavior. */
 void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n)
 {
+	depot_stack_handle_t prev_old_origin = 0, prev_new_origin = 0;
+	int i, iter, step, src_off, dst_off, oiter_src, oiter_dst;
 	depot_stack_handle_t old_origin = 0, new_origin = 0;
-	int src_slots, dst_slots, i, iter, step, skip_bits;
 	depot_stack_handle_t *origin_src, *origin_dst;
-	void *shadow_src, *shadow_dst;
-	u32 *align_shadow_src, shadow;
+	u8 *shadow_src, *shadow_dst;
+	u32 *align_shadow_dst;
 	bool backwards;
 
 	shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW);
 	if (!shadow_dst)
 		return;
 	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n));
+	align_shadow_dst =
+		(u32 *)ALIGN_DOWN((u64)shadow_dst, KMSAN_ORIGIN_SIZE);
 
 	shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW);
 	if (!shadow_src) {
-		/*
-		 * @src is untracked: zero out destination shadow, ignore the
-		 * origins, we're done.
-		 */
-		__memset(shadow_dst, 0, n);
+		/* @src is untracked: mark @dst as initialized. */
+		kmsan_internal_unpoison_memory(dst, n, /*checked*/ false);
 		return;
 	}
 	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n));
 
-	__memmove(shadow_dst, shadow_src, n);
-
 	origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN);
 	origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN);
 	KMSAN_WARN_ON(!origin_dst || !origin_src);
-	src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) -
-		     ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) /
-		    KMSAN_ORIGIN_SIZE;
-	dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) -
-		     ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) /
-		    KMSAN_ORIGIN_SIZE;
-	KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1));
-	KMSAN_WARN_ON((src_slots - dst_slots > 1) ||
-		      (dst_slots - src_slots < -1));
 
 	backwards = dst > src;
-	i = backwards ? min(src_slots, dst_slots) - 1 : 0;
-	iter = backwards ? -1 : 1;
-
-	align_shadow_src =
-		(u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE);
-	for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) {
-		KMSAN_WARN_ON(i < 0);
-		shadow = align_shadow_src[i];
-		if (i == 0) {
-			/*
-			 * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't
-			 * look at the first @src % KMSAN_ORIGIN_SIZE bytes
-			 * of the first shadow slot.
-			 */
-			skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8;
-			shadow = (shadow >> skip_bits) << skip_bits;
+	step = backwards ? -1 : 1;
+	iter = backwards ? n - 1 : 0;
+	src_off = (u64)src % KMSAN_ORIGIN_SIZE;
+	dst_off = (u64)dst % KMSAN_ORIGIN_SIZE;
+
+	/* Copy shadow bytes one by one, updating the origins if necessary. */
+	for (i = 0; i < n; i++, iter += step) {
+		oiter_src = (iter + src_off) / KMSAN_ORIGIN_SIZE;
+		oiter_dst = (iter + dst_off) / KMSAN_ORIGIN_SIZE;
+		if (!shadow_src[iter]) {
+			shadow_dst[iter] = 0;
+			if (!align_shadow_dst[oiter_dst])
+				origin_dst[oiter_dst] = 0;
+			continue;
 		}
-		if (i == src_slots - 1) {
-			/*
-			 * If @src + n isn't aligned on
-			 * KMSAN_ORIGIN_SIZE, don't look at the last
-			 * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the
-			 * last shadow slot.
-			 */
-			skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8;
-			shadow = (shadow << skip_bits) >> skip_bits;
-		}
-		/*
-		 * Overwrite the origin only if the corresponding
-		 * shadow is nonempty.
-		 */
-		if (origin_src[i] && (origin_src[i] != old_origin) && shadow) {
-			old_origin = origin_src[i];
-			new_origin = kmsan_internal_chain_origin(old_origin);
+		shadow_dst[iter] = shadow_src[iter];
+		old_origin = origin_src[oiter_src];
+		if (old_origin == prev_old_origin)
+			new_origin = prev_new_origin;
+		else {
 			/*
 			 * kmsan_internal_chain_origin() may return
 			 * NULL, but we don't want to lose the previous
 			 * origin value.
 			 */
+			new_origin = kmsan_internal_chain_origin(old_origin);
 			if (!new_origin)
 				new_origin = old_origin;
 		}
-		if (shadow)
-			origin_dst[i] = new_origin;
-		else
-			origin_dst[i] = 0;
-	}
-	/*
-	 * If dst_slots is greater than src_slots (i.e.
-	 * dst_slots == src_slots + 1), there is an extra origin slot at the
-	 * beginning or end of the destination buffer, for which we take the
-	 * origin from the previous slot.
-	 * This is only done if the part of the source shadow corresponding to
-	 * slot is non-zero.
-	 *
-	 * E.g. if we copy 8 aligned bytes that are marked as uninitialized
-	 * and have origins o111 and o222, to an unaligned buffer with offset 1,
-	 * these two origins are copied to three origin slots, so one of then
-	 * needs to be duplicated, depending on the copy direction (@backwards)
-	 *
-	 *   src shadow: |uuuu|uuuu|....|
-	 *   src origin: |o111|o222|....|
-	 *
-	 * backwards = 0:
-	 *   dst shadow: |.uuu|uuuu|u...|
-	 *   dst origin: |....|o111|o222| - fill the empty slot with o111
-	 * backwards = 1:
-	 *   dst shadow: |.uuu|uuuu|u...|
-	 *   dst origin: |o111|o222|....| - fill the empty slot with o222
-	 */
-	if (src_slots < dst_slots) {
-		if (backwards) {
-			shadow = align_shadow_src[src_slots - 1];
-			skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8;
-			shadow = (shadow << skip_bits) >> skip_bits;
-			if (shadow)
-				/* src_slots > 0, therefore dst_slots is at least 2 */
-				origin_dst[dst_slots - 1] =
-					origin_dst[dst_slots - 2];
-		} else {
-			shadow = align_shadow_src[0];
-			skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8;
-			shadow = (shadow >> skip_bits) << skip_bits;
-			if (shadow)
-				origin_dst[0] = origin_dst[1];
-		}
+		origin_dst[oiter_dst] = new_origin;
+		prev_new_origin = new_origin;
+		prev_old_origin = old_origin;
 	}
 }
 
Signature · 1 line
2.42.0.283.g2d96d420d3-goog
author maintainer
#1 lore raw

PATCH 2/2 kmsan: prevent optimizations in memcpy tests

Clang 18 learned to optimize away memcpy() calls of small uninitialized scalar values. To ensure that memcpy tests in kmsan_test.c still perform calls to memcpy() (which KMSAN replaces with __msan_memcpy()), declare a separate memcpy_noinline() function with volatile parameters, which won't be optimized.

Also retire DO_NOT_OPTIMIZE(), as memcpy_noinline() is apparently enough.

---
 mm/kmsan/kmsan_test.c | 37 ++++++++++++++-----------------------
 1 file changed, 14 insertions(+), 23 deletions(-)
mm/kmsan/kmsan_test.c +14 -23
index 312989aa2865c..0c32c917b489a 100644
@@ -407,33 +407,25 @@ static void test_printk(struct kunit *test)
 	KUNIT_EXPECT_TRUE(test, report_matches(&expect));
 }
 
-/*
- * Prevent the compiler from optimizing @var away. Without this, Clang may
- * notice that @var is uninitialized and drop memcpy() calls that use it.
- *
- * There is OPTIMIZER_HIDE_VAR() in linux/compier.h that we cannot use here,
- * because it is implemented as inline assembly receiving @var as a parameter
- * and will enforce a KMSAN check. Same is true for e.g. barrier_data(var).
- */
-#define DO_NOT_OPTIMIZE(var) barrier()
+/* Prevent the compiler from inlining a memcpy() call. */
+static noinline void *memcpy_noinline(volatile void *dst,
+				      const volatile void *src, size_t size)
+{
+	return memcpy(dst, src, size);
+}
 
-/*
- * Test case: ensure that memcpy() correctly copies initialized values.
- * Also serves as a regression test to ensure DO_NOT_OPTIMIZE() does not cause
- * extra checks.
- */
+/* Test case: ensure that memcpy() correctly copies initialized values. */
 static void test_init_memcpy(struct kunit *test)
 {
 	EXPECTATION_NO_REPORT(expect);
 	volatile int src;
 	volatile int dst = 0;
 
-	DO_NOT_OPTIMIZE(src);
 	src = 1;
 	kunit_info(
 		test,
 		"memcpy()ing aligned initialized src to aligned dst (no reports)\n");
-	memcpy((void *)&dst, (void *)&src, sizeof(src));
+	memcpy_noinline((void *)&dst, (void *)&src, sizeof(src));
 	kmsan_check_memory((void *)&dst, sizeof(dst));
 	KUNIT_EXPECT_TRUE(test, report_matches(&expect));
 }
@@ -451,8 +443,7 @@ static void test_memcpy_aligned_to_aligned(struct kunit *test)
 	kunit_info(
 		test,
 		"memcpy()ing aligned uninit src to aligned dst (UMR report)\n");
-	DO_NOT_OPTIMIZE(uninit_src);
-	memcpy((void *)&dst, (void *)&uninit_src, sizeof(uninit_src));
+	memcpy_noinline((void *)&dst, (void *)&uninit_src, sizeof(uninit_src));
 	kmsan_check_memory((void *)&dst, sizeof(dst));
 	KUNIT_EXPECT_TRUE(test, report_matches(&expect));
 }
@@ -474,8 +465,9 @@ static void test_memcpy_aligned_to_unaligned(struct kunit *test)
 	kunit_info(
 		test,
 		"memcpy()ing aligned uninit src to unaligned dst (UMR report)\n");
-	DO_NOT_OPTIMIZE(uninit_src);
-	memcpy((void *)&dst[1], (void *)&uninit_src, sizeof(uninit_src));
+	kmsan_check_memory(&uninit_src, sizeof(uninit_src));
+	memcpy_noinline((void *)&dst[1], (void *)&uninit_src,
+			sizeof(uninit_src));
 	kmsan_check_memory((void *)dst, 4);
 	KUNIT_EXPECT_TRUE(test, report_matches(&expect));
 }
@@ -498,8 +490,8 @@ static void test_memcpy_aligned_to_unaligned2(struct kunit *test)
 	kunit_info(
 		test,
 		"memcpy()ing aligned uninit src to unaligned dst - part 2 (UMR report)\n");
-	DO_NOT_OPTIMIZE(uninit_src);
-	memcpy((void *)&dst[1], (void *)&uninit_src, sizeof(uninit_src));
+	memcpy_noinline((void *)&dst[1], (void *)&uninit_src,
+			sizeof(uninit_src));
 	kmsan_check_memory((void *)&dst[4], sizeof(uninit_src));
 	KUNIT_EXPECT_TRUE(test, report_matches(&expect));
 }
@@ -513,7 +505,6 @@ static void test_memcpy_aligned_to_unaligned2(struct kunit *test)
                                                                             \
 		kunit_info(test,                                            \
 			   "memset" #size "() should initialize memory\n"); \
-		DO_NOT_OPTIMIZE(uninit);                                    \
 		memset##size((uint##size##_t *)&uninit, 0, 1);              \
 		kmsan_check_memory((void *)&uninit, sizeof(uninit));        \
 		KUNIT_EXPECT_TRUE(test, report_matches(&expect));           \
Signature · 1 line
2.42.0.283.g2d96d420d3-goog
#2 lore raw

Re: [PATCH 2/2] kmsan: prevent optimizations in memcpy tests

kernel test robot noticed the following build errors:

Hi Alexander,

kernel test robot noticed the following build errors:

[auto build test ERROR on akpm-mm/mm-everything]
[also build test ERROR on linus/master v6.5 next-20230908] [If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Alexander-Potapenko/kmsan-prevent-optimizations-in-memcpy-tests/20230907-210817
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link:    https://lore.kernel.org/r/20230907130642.245222-2-glider%40google.com
patch subject: [PATCH 2/2] kmsan: prevent optimizations in memcpy tests
config: x86_64-buildonly-randconfig-006-20230910 (https://download.01.org/0day-ci/archive/20230910/[email protected]/config)
compiler: clang version 16.0.4 (https://github.com/llvm/llvm-project.git ae42196bc493ffe877a7e3dff8be32035dea4d07)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20230910/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

>> mm/kmsan/kmsan_test.c:414:16: error: passing 'volatile void *' to parameter of type 'void *' discards qualifiers [-Werror,-Wincompatible-pointer-types-discards-qualifiers]
           return memcpy(dst, src, size);
                         ^~~
   arch/x86/include/asm/string_64.h:18:27: note: passing argument to parameter 'to' here
   extern void *memcpy(void *to, const void *from, size_t len);
                             ^
>> mm/kmsan/kmsan_test.c:414:21: error: passing 'const volatile void *' to parameter of type 'const void *' discards qualifiers [-Werror,-Wincompatible-pointer-types-discards-qualifiers]
           return memcpy(dst, src, size);
                              ^~~
   arch/x86/include/asm/string_64.h:18:43: note: passing argument to parameter 'from' here
   extern void *memcpy(void *to, const void *from, size_t len);
                                             ^
>> mm/kmsan/kmsan_test.c:468:21: error: passing 'volatile int *' to parameter of type 'const void *' discards qualifiers [-Werror,-Wincompatible-pointer-types-discards-qualifiers]
           kmsan_check_memory(&uninit_src, sizeof(uninit_src));
                              ^~~~~~~~~~~
   include/linux/kmsan-checks.h:47:37: note: passing argument to parameter 'address' here
   void kmsan_check_memory(const void *address, size_t size);
                                       ^

3 errors generated.

vim +414 mm/kmsan/kmsan_test.c

409
410 /* Prevent the compiler from inlining a memcpy() call. */
411 static noinline void *memcpy_noinline(volatile void *dst,
412 const volatile void *src, size_t size)
413 {

 > 414		return memcpy(dst, src, size);
   415	}
   416	
   417	/* Test case: ensure that memcpy() correctly copies initialized values. */
   418	static void test_init_memcpy(struct kunit *test)
   419	{
   420		EXPECTATION_NO_REPORT(expect);
   421		volatile int src;
   422		volatile int dst = 0;
   423	
   424		src = 1;
   425		kunit_info(
   426			test,
   427			"memcpy()ing aligned initialized src to aligned dst (no reports)\n");
   428		memcpy_noinline((void *)&dst, (void *)&src, sizeof(src));
   429		kmsan_check_memory((void *)&dst, sizeof(dst));
   430		KUNIT_EXPECT_TRUE(test, report_matches(&expect));
   431	}
   432	
   433	/*
   434	 * Test case: ensure that memcpy() correctly copies uninitialized values between
   435	 * aligned `src` and `dst`.
   436	 */
   437	static void test_memcpy_aligned_to_aligned(struct kunit *test)
   438	{
   439		EXPECTATION_UNINIT_VALUE_FN(expect, "test_memcpy_aligned_to_aligned");
   440		volatile int uninit_src;
   441		volatile int dst = 0;
   442	
   443		kunit_info(
   444			test,
   445			"memcpy()ing aligned uninit src to aligned dst (UMR report)\n");
   446		memcpy_noinline((void *)&dst, (void *)&uninit_src, sizeof(uninit_src));
   447		kmsan_check_memory((void *)&dst, sizeof(dst));
   448		KUNIT_EXPECT_TRUE(test, report_matches(&expect));
   449	}
   450	
   451	/*
   452	 * Test case: ensure that memcpy() correctly copies uninitialized values between
   453	 * aligned `src` and unaligned `dst`.
   454	 *
   455	 * Copying aligned 4-byte value to an unaligned one leads to touching two
   456	 * aligned 4-byte values. This test case checks that KMSAN correctly reports an
   457	 * error on the first of the two values.
   458	 */
   459	static void test_memcpy_aligned_to_unaligned(struct kunit *test)
   460	{
   461		EXPECTATION_UNINIT_VALUE_FN(expect, "test_memcpy_aligned_to_unaligned");
   462		volatile int uninit_src;
   463		volatile char dst[8] = { 0 };
   464	
   465		kunit_info(
   466			test,
   467			"memcpy()ing aligned uninit src to unaligned dst (UMR report)\n");
 > 468		kmsan_check_memory(&uninit_src, sizeof(uninit_src));

469 memcpy_noinline((void *)&dst[1], (void *)&uninit_src,
470 sizeof(uninit_src));
471 kmsan_check_memory((void *)dst, 4);
472 KUNIT_EXPECT_TRUE(test, report_matches(&expect));
473 }
474

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
reviewer Acked-by on v1 1/2
#3 lore raw
In reply to Alexander Potapenko
Quoted 52 lines · Alexander Potapenko

kmsan_internal_memmove_metadata() is the function that implements copying metadata every time memcpy()/memmove() is called. Because shadow memory stores 1 byte per each byte of kernel memory, copying the shadow is trivial and can be done by a single memmove() call.
Origins, on the other hand, are stored as 4-byte values corresponding to every aligned 4 bytes of kernel memory. Therefore, if either the source or the destination of kmsan_internal_memmove_metadata() is unaligned, the number of origin slots corresponding to the source or destination may differ:

1) memcpy(0xffff888080a00000, 0xffff888080900000, 4) copies 1 origin slot into 1 origin slot:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): xxxx
dst origins: o111

2) memcpy(0xffff888080a00001, 0xffff888080900000, 4) copies 1 origin slot into 2 origin slots:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): .xxx x...
dst origins: o111 o111

3) memcpy(0xffff888080a00000, 0xffff888080900001, 4) copies 2 origin slots into 1 origin slot:

src (0xffff888080900000): .xxx x...
src origins: o111 o222
dst (0xffff888080a00000): xxxx
dst origins: o111
(or o222)

Previously, kmsan_internal_memmove_metadata() tried to solve this problem by copying min(src_slots, dst_slots) as is and cloning the missing slot on one of the ends, if needed.
This was error-prone even in the simple cases where 4 bytes were copied, and did not account for situations where the total number of nonzero origin slots could have increased by more than one after copying:

memcpy(0xffff888080a00000, 0xffff888080900002, 8)

src (0xffff888080900002): ..xx .... xx..
src origins: o111 0000 o222
dst (0xffff888080a00000): xx.. ..xx

                            o111 0000
                        (or 0000 o222)
Quoted 7 lines

The new implementation simply copies the shadow byte by byte, and updates the corresponding origin slot, if the shadow byte is nonzero. This approach can handle complex cases with mixed initialized and uninitialized bytes. Similarly to KMSAN inline instrumentation, latter writes to bytes sharing the same origin slots take precedence.

I think this needs a Fixes tag.
Also, is this corner case exercised by one of the KMSAN KUnit test cases?

Otherwise,

Quoted 174 lines
---
 mm/kmsan/core.c | 127 ++++++++++++------------------------------------
 1 file changed, 31 insertions(+), 96 deletions(-)
mm/kmsan/core.c +31 -97
index 3adb4c1d3b193..c19f47af04241 100644
@@ -83,131 +83,66 @@ depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags,
 /* Copy the metadata following the memmove() behavior. */
 void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n)
 {
+       depot_stack_handle_t prev_old_origin = 0, prev_new_origin = 0;
+       int i, iter, step, src_off, dst_off, oiter_src, oiter_dst;
        depot_stack_handle_t old_origin = 0, new_origin = 0;
-       int src_slots, dst_slots, i, iter, step, skip_bits;
        depot_stack_handle_t *origin_src, *origin_dst;
-       void *shadow_src, *shadow_dst;
-       u32 *align_shadow_src, shadow;
+       u8 *shadow_src, *shadow_dst;
+       u32 *align_shadow_dst;
        bool backwards;
 
        shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW);
        if (!shadow_dst)
                return;
        KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n));
+       align_shadow_dst =
+               (u32 *)ALIGN_DOWN((u64)shadow_dst, KMSAN_ORIGIN_SIZE);
 
        shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW);
        if (!shadow_src) {
-               /*
-                * @src is untracked: zero out destination shadow, ignore the
-                * origins, we're done.
-                */
-               __memset(shadow_dst, 0, n);
+               /* @src is untracked: mark @dst as initialized. */
+               kmsan_internal_unpoison_memory(dst, n, /*checked*/ false);
                return;
        }
        KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n));
 
-       __memmove(shadow_dst, shadow_src, n);
-
        origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN);
        origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN);
        KMSAN_WARN_ON(!origin_dst || !origin_src);
-       src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) -
-                    ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) /
-                   KMSAN_ORIGIN_SIZE;
-       dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) -
-                    ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) /
-                   KMSAN_ORIGIN_SIZE;
-       KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1));
-       KMSAN_WARN_ON((src_slots - dst_slots > 1) ||
-                     (dst_slots - src_slots < -1));
 
        backwards = dst > src;
-       i = backwards ? min(src_slots, dst_slots) - 1 : 0;
-       iter = backwards ? -1 : 1;
-
-       align_shadow_src =
-               (u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE);
-       for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) {
-               KMSAN_WARN_ON(i < 0);
-               shadow = align_shadow_src[i];
-               if (i == 0) {
-                       /*
-                        * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't
-                        * look at the first @src % KMSAN_ORIGIN_SIZE bytes
-                        * of the first shadow slot.
-                        */
-                       skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8;
-                       shadow = (shadow >> skip_bits) << skip_bits;
+       step = backwards ? -1 : 1;
+       iter = backwards ? n - 1 : 0;
+       src_off = (u64)src % KMSAN_ORIGIN_SIZE;
+       dst_off = (u64)dst % KMSAN_ORIGIN_SIZE;
+
+       /* Copy shadow bytes one by one, updating the origins if necessary. */
+       for (i = 0; i < n; i++, iter += step) {
+               oiter_src = (iter + src_off) / KMSAN_ORIGIN_SIZE;
+               oiter_dst = (iter + dst_off) / KMSAN_ORIGIN_SIZE;
+               if (!shadow_src[iter]) {
+                       shadow_dst[iter] = 0;
+                       if (!align_shadow_dst[oiter_dst])
+                               origin_dst[oiter_dst] = 0;
+                       continue;
                }
-               if (i == src_slots - 1) {
-                       /*
-                        * If @src + n isn't aligned on
-                        * KMSAN_ORIGIN_SIZE, don't look at the last
-                        * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the
-                        * last shadow slot.
-                        */
-                       skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8;
-                       shadow = (shadow << skip_bits) >> skip_bits;
-               }
-               /*
-                * Overwrite the origin only if the corresponding
-                * shadow is nonempty.
-                */
-               if (origin_src[i] && (origin_src[i] != old_origin) && shadow) {
-                       old_origin = origin_src[i];
-                       new_origin = kmsan_internal_chain_origin(old_origin);
+               shadow_dst[iter] = shadow_src[iter];
+               old_origin = origin_src[oiter_src];
+               if (old_origin == prev_old_origin)
+                       new_origin = prev_new_origin;
+               else {
                        /*
                         * kmsan_internal_chain_origin() may return
                         * NULL, but we don't want to lose the previous
                         * origin value.
                         */
+                       new_origin = kmsan_internal_chain_origin(old_origin);
                        if (!new_origin)
                                new_origin = old_origin;
                }
-               if (shadow)
-                       origin_dst[i] = new_origin;
-               else
-                       origin_dst[i] = 0;
-       }
-       /*
-        * If dst_slots is greater than src_slots (i.e.
-        * dst_slots == src_slots + 1), there is an extra origin slot at the
-        * beginning or end of the destination buffer, for which we take the
-        * origin from the previous slot.
-        * This is only done if the part of the source shadow corresponding to
-        * slot is non-zero.
-        *
-        * E.g. if we copy 8 aligned bytes that are marked as uninitialized
-        * and have origins o111 and o222, to an unaligned buffer with offset 1,
-        * these two origins are copied to three origin slots, so one of then
-        * needs to be duplicated, depending on the copy direction (@backwards)
-        *
-        *   src shadow: |uuuu|uuuu|....|
-        *   src origin: |o111|o222|....|
-        *
-        * backwards = 0:
-        *   dst shadow: |.uuu|uuuu|u...|
-        *   dst origin: |....|o111|o222| - fill the empty slot with o111
-        * backwards = 1:
-        *   dst shadow: |.uuu|uuuu|u...|
-        *   dst origin: |o111|o222|....| - fill the empty slot with o222
-        */
-       if (src_slots < dst_slots) {
-               if (backwards) {
-                       shadow = align_shadow_src[src_slots - 1];
-                       skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8;
-                       shadow = (shadow << skip_bits) >> skip_bits;
-                       if (shadow)
-                               /* src_slots > 0, therefore dst_slots is at least 2 */
-                               origin_dst[dst_slots - 1] =
-                                       origin_dst[dst_slots - 2];
-               } else {
-                       shadow = align_shadow_src[0];
-                       skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8;
-                       shadow = (shadow >> skip_bits) << skip_bits;
-                       if (shadow)
-                               origin_dst[0] = origin_dst[1];
-               }
+               origin_dst[oiter_dst] = new_origin;
+               prev_new_origin = new_origin;
+               prev_old_origin = old_origin;
        }
 }
 
--

2.42.0.283.g2d96d420d3-goog

author maintainer
#4 lore raw
Quoted 60 lines · Marco Elver
Quoted 58 lines · Alexander Potapenko

kmsan_internal_memmove_metadata() is the function that implements copying metadata every time memcpy()/memmove() is called. Because shadow memory stores 1 byte per each byte of kernel memory, copying the shadow is trivial and can be done by a single memmove() call.
Origins, on the other hand, are stored as 4-byte values corresponding to every aligned 4 bytes of kernel memory. Therefore, if either the source or the destination of kmsan_internal_memmove_metadata() is unaligned, the number of origin slots corresponding to the source or destination may differ:

1) memcpy(0xffff888080a00000, 0xffff888080900000, 4) copies 1 origin slot into 1 origin slot:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): xxxx
dst origins: o111

2) memcpy(0xffff888080a00001, 0xffff888080900000, 4) copies 1 origin slot into 2 origin slots:

src (0xffff888080900000): xxxx
src origins: o111
dst (0xffff888080a00000): .xxx x...
dst origins: o111 o111

3) memcpy(0xffff888080a00000, 0xffff888080900001, 4) copies 2 origin slots into 1 origin slot:

src (0xffff888080900000): .xxx x...
src origins: o111 o222
dst (0xffff888080a00000): xxxx
dst origins: o111
(or o222)

Previously, kmsan_internal_memmove_metadata() tried to solve this problem by copying min(src_slots, dst_slots) as is and cloning the missing slot on one of the ends, if needed.
This was error-prone even in the simple cases where 4 bytes were copied, and did not account for situations where the total number of nonzero origin slots could have increased by more than one after copying:

memcpy(0xffff888080a00000, 0xffff888080900002, 8)

src (0xffff888080900002): ..xx .... xx..
src origins: o111 0000 o222
dst (0xffff888080a00000): xx.. ..xx

                            o111 0000
                        (or 0000 o222)

The new implementation simply copies the shadow byte by byte, and updates the corresponding origin slot, if the shadow byte is nonzero. This approach can handle complex cases with mixed initialized and uninitialized bytes. Similarly to KMSAN inline instrumentation, latter writes to bytes sharing the same origin slots take precedence.

Quoted 3 lines
Quoted 1 line

I think this needs a Fixes tag.

Thanks, will add in v2!

Quoted 1 line

Also, is this corner case exercised by one of the KMSAN KUnit test cases?

Ditto

Quoted 3 lines

Otherwise,