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

[Maciej Wieczor-Retman <maciej.wieczor-retman@intel.com>]

On 2025-02-27 at 13:27:32 +0100, Maciej Wieczor-Retman wrote:
>On 2025-02-26 at 20:44:35 +0100, Andrey Konovalov wrote:
>>On Wed, Feb 26, 2025 at 5:43 PM Maciej Wieczor-Retman
>><maciej.wieczor-retman@intel.com> wrote:
>>
>>> >With the way the compiler works right now, for the perfectly precise
>>> >check, I think we need to check 2 ranges: [0xfe00000000000000,
>>> >0xffffffffffffffff] for when bit 63 is set (of a potentially-invalid
>>> >pointer to which memory-to-shadow mapping is to be applied) and
>>> >[0x7e00000000000000, 0x7fffffffffffffff] for when bit 63 is reset. Bit
>>> >56 ranges through [0, 1] in both cases.
>>> >
>>> >However, in these patches, you use only bits [60:57]. The compiler is
>>> >not aware of this, so it still sets bits [62:57], and we end up with
>>> >the same two ranges. But in the KASAN code, you only set bits [60:57],
>>> >and thus we can end up with 8 potential ranges (2 possible values for
>>> >each of the top 3 bits), which gets complicated. So checking only one
>>> >range that covers all of them seems to be reasonable for simplicity
>>> >even though not entirely precise. And yes, [0x1e00000000000000,
>>> >0xffffffffffffffff] looks like the what we need.
>>>
>>> Aren't the 2 ranges you mentioned in the previous paragraph still valid, no
>>> matter what bits the __tag_set() function uses? I mean bits 62:57 are still
>>> reset by the compiler so bits 62:61 still won't matter. For example addresses
>>> 0x1e00000000000000 and 0x3e00000000000000 will resolve to the same thing after
>>> the compiler is done with them right?
>>
>>Ah, yes, you're right, it's the same 2 ranges.
>>
>>I was thinking about the outline instrumentation mode, where the
>>shadow address would be calculated based on resetting only bits
>>[60:57]. But then there we have a addr_has_metadata() check in
>>kasan_check_range(), so KASAN should not try to deference a bad shadow
>>address and thus should not reach kasan_non_canonical_hook() anyway.
>
>Okay, so I guess we should do the same check for both arm64 and x86 right? (and
>risc-v in the future). Just use the wider range - in this case the 2 ranges that
>x86 needs. Then it could look something like:
>
>			// 0xffffffffffffffff maps just below the shadow offset
>	if (addr > KASAN_SHADOW_OFFSET ||
>			// and check below the most negative address
>		(addr < kasan_mem_to_shadow(0xFE << 56) &&
>			// biggest positive address that overflows so check both above it
>		addr > kasan_mem_to_shadow(~0UL >> 1)) ||
>			// smallest positive address but will overflow so check addresses below it
>		addr < kasan_mem_to_shadow(0x7E << 56))
>		return
>
>so first two lines deal with the first range, and the next two lines deal with
>the second one.
>
>Or do you want me to make this part of non_canonical_hook() arch specific for
>maximum accuracy?
>

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

-- 
Kind regards
Maciej Wieczór-Retman