Re: [PATCH v2 01/14] kasan: sw_tags: Use arithmetic shift for shadow computation

[Andrey Konovalov <andreyknvl@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2950 bytes --]

On Fri, Feb 28, 2025 at 5:13 PM Maciej Wieczor-Retman
<maciej.wieczor-retman@intel.com> wrote:
>
> I was applying your other comments to the series and came up with something like
> this. What do you think?
>
>         /*
>          * With the default kasan_mem_to_shadow() algorithm, all addresses
>          * returned by the memory-to-shadow mapping (even for bogus pointers)
>          * must be within a certain displacement from KASAN_SHADOW_OFFSET.
>          *
>          * For Generic KASAN the displacement is unsigned so the mapping from zero
>          * to the last kernel address needs checking.
>          */
>         if (IS_ENABLED(CONFIG_KASAN_GENERIC)) {
>                 if (addr < KASAN_SHADOW_OFFSET ||
>                     addr >= KASAN_SHADOW_OFFSET + max_shadow_size)
>                         return;
>         } else {
>                 /*
>                  * For the tag-based mode the compiler resets tags in addresses at
>                  * the start of kasan_mem_to_shadow(). Because of this it's not
>                  * necessary to check a mapping of the entire address space but only
>                  * whether a range of [0xFF00000000000000 - 0xFFFFFFFFFFFFFFFF] is a
>                  * valid memory-to-shadow mapping. On x86, tags are located in bits
>                  * 62:57 so the range becomes [0x7E00000000000000 - 0xFFFFFFFFFFFFFFFF].
>                  * The check below tries to exclude invalid addresses by
>                  * checking spaces between [0x7E00000000000000 - 0x7FFFFFFFFFFFFFFF]
>                  * (which are positive and will overflow the memory-to-shadow
>                  * mapping) and [0xFE00000000000000 - 0xFFFFFFFFFFFFFFFF]
>                  */
>                  if (addr > KASAN_SHADOW_OFFSET ||
>                      (addr < (u64)kasan_mem_to_shadow((void *)(0xFEUL << 56)) &&
>                      addr > (u64)kasan_mem_to_shadow((void *)(~0UL >> 1))) ||
>                      addr < (u64)kasan_mem_to_shadow((void *)(0x7EUL << 56)))
>                         return;
>         }
>
> The comment is a bit long and has a lot of hexes but maybe it's good to leave a
> longer explanation so no one has to dig through the mailing archives to
> understand the logic :b

Explaining the logic sounds good to me!

I think your patch is close to what would look good, but I think the
parentheses in the long if condition look suspicious.

Please check the attached diff (Gmail makes it hard to inline code): I
fixed the parentheses (if I'm right about them being wrong), made the
checks look uniform, added an arm-specific check, and reworked the
comments (please check if they make sense).

If the diff looks good to you, let's use that.

It also would be great, if you could test this: add some code that
dereferences various bad addresses and see if the extra KASAN message
line gets printed during the GPF.

[-- Attachment #2: kasan_non_canonical_hook.patch --]
[-- Type: text/x-patch, Size: 2896 bytes --]

diff --git a/mm/kasan/report.c b/mm/kasan/report.c
index 8357e1a33699..7edde1a26a41 100644
--- a/mm/kasan/report.c
+++ b/mm/kasan/report.c
@@ -681,11 +681,56 @@ void kasan_non_canonical_hook(unsigned long addr)
 	const char *bug_type;
 
 	/*
-	 * All addresses that came as a result of the memory-to-shadow mapping
-	 * (even for bogus pointers) must be >= KASAN_SHADOW_OFFSET.
+	 * For Generic KASAN, kasan_mem_to_shadow() uses the logical right shift
+	 * and never overflows with the chosen KASAN_SHADOW_OFFSET values (on
+	 * both x86 and arm64). Thus, the possible shadow addresses (even for
+	 * bogus pointers) belong to a single contiguous region that is the
+	 * result of kasan_mem_to_shadow() applied to the whole address space.
 	 */
-	if (addr < KASAN_SHADOW_OFFSET)
-		return;
+	if (IS_ENABLED(CONFIG_KASAN_GENERIC)) {
+		if (addr < (u64)kasan_mem_to_shadow((void *)(0UL)) ||
+		    addr > (u64)kasan_mem_to_shadow((void *)(~0UL)))
+			return;
+	}
+
+	/*
+	 * For Software Tag-Based KASAN, kasan_mem_to_shadow() uses the
+	 * arithmetic shift. Normally, this would make checking for a possible
+	 * shadow address complicated, as the shadow address computation
+	 * operation would overflow only for some memory addresses. However, due
+	 * to the chosen KASAN_SHADOW_OFFSET values and the fact the
+	 * kasan_mem_to_shadow() only operates on pointers with the tag reset,
+	 * the overflow always happens (for both x86 and arm64).
+	 *
+	 * For arm64, the top byte of the pointer gets reset to 0xFF. Thus, the
+	 * possible shadow addresses belong to a region that is the result of
+	 * kasan_mem_to_shadow() applied to the memory range
+	 * [0xFF000000000000, 0xFFFFFFFFFFFFFFFF]. Despite the overflow, the
+	 * resulting possible shadow region is contiguous, as the overflow
+	 * happens for both 0xFF000000000000 and 0xFFFFFFFFFFFFFFFF.
+	 */
+	if (IS_ENABLED(CONFIG_KASAN_SW_TAGS) && IS_ENABLED(CONFIG_ARM64)) {
+		if (addr < (u64)kasan_mem_to_shadow((void *)(0xFFUL << 56)) ||
+		    addr > (u64)kasan_mem_to_shadow((void *)(~0UL)))
+			return;
+	}
+
+	 /*
+	  * For x86-64, only the pointer bits [62:57] get reset, and bits #63
+	  * and #56 can be 0 or 1. Thus, kasan_mem_to_shadow() can be possibly
+	  * applied to two regions of memory:
+	  * [0x7E00000000000000, 0x7FFFFFFFFFFFFFFF] and
+	  * [0xFE00000000000000, 0xFFFFFFFFFFFFFFFF]. As the overflow happens
+	  * for both ends of both memory ranges, both possible shadow regions
+	  * are contiguous.
+	 */
+	if (IS_ENABLED(CONFIG_KASAN_SW_TAGS) && IS_ENABLED(CONFIG_X86_64)) {
+		if ((addr < (u64)kasan_mem_to_shadow((void *)(0x7EUL << 56)) ||
+		     addr > (u64)kasan_mem_to_shadow((void *)(~0UL >> 1))) &&
+		    (addr < (u64)kasan_mem_to_shadow((void *)(0xFEUL << 56)) ||
+		     addr > (u64)kasan_mem_to_shadow((void *)(~0UL))))
+			return;
+	}
 
 	orig_addr = (unsigned long)kasan_shadow_to_mem((void *)addr);