Message-ID: <mjyjkyiyhbbxyksiycywgh72laozztzwxxwi3gi252uk4b6f7j@3zwpv7l7aisk>
Date: Fri, 28 Feb 2025 17:12:49 +0100
From: Maciej Wieczor-Retman <maciej.wieczor-retman@...el.com>
To: Andrey Konovalov <andreyknvl@...il.com>
CC: Vitaly Buka <vitalybuka@...gle.com>, <kees@...nel.org>,
	<julian.stecklina@...erus-technology.de>, <kevinloughlin@...gle.com>,
	<peterz@...radead.org>, <tglx@...utronix.de>, <justinstitt@...gle.com>,
	<catalin.marinas@....com>, <wangkefeng.wang@...wei.com>, <bhe@...hat.com>,
	<ryabinin.a.a@...il.com>, <kirill.shutemov@...ux.intel.com>,
	<will@...nel.org>, <ardb@...nel.org>, <jason.andryuk@....com>,
	<dave.hansen@...ux.intel.com>, <pasha.tatashin@...een.com>,
	<guoweikang.kernel@...il.com>, <dwmw@...zon.co.uk>, <mark.rutland@....com>,
	<broonie@...nel.org>, <apopple@...dia.com>, <bp@...en8.de>,
	<rppt@...nel.org>, <kaleshsingh@...gle.com>, <richard.weiyang@...il.com>,
	<luto@...nel.org>, <glider@...gle.com>, <pankaj.gupta@....com>,
	<pawan.kumar.gupta@...ux.intel.com>, <kuan-ying.lee@...onical.com>,
	<tony.luck@...el.com>, <tj@...nel.org>, <jgross@...e.com>,
	<dvyukov@...gle.com>, <baohua@...nel.org>, <samuel.holland@...ive.com>,
	<dennis@...nel.org>, <akpm@...ux-foundation.org>,
	<thomas.weissschuh@...utronix.de>, <surenb@...gle.com>,
	<kbingham@...nel.org>, <ankita@...dia.com>, <nathan@...nel.org>,
	<ziy@...dia.com>, <xin@...or.com>, <rafael.j.wysocki@...el.com>,
	<andriy.shevchenko@...ux.intel.com>, <cl@...ux.com>, <jhubbard@...dia.com>,
	<hpa@...or.com>, <scott@...amperecomputing.com>, <david@...hat.com>,
	<jan.kiszka@...mens.com>, <vincenzo.frascino@....com>, <corbet@....net>,
	<maz@...nel.org>, <mingo@...hat.com>, <arnd@...db.de>, <ytcoode@...il.com>,
	<xur@...gle.com>, <morbo@...gle.com>, <thiago.bauermann@...aro.org>,
	<linux-doc@...r.kernel.org>, <kasan-dev@...glegroups.com>,
	<linux-kernel@...r.kernel.org>, <llvm@...ts.linux.dev>, <linux-mm@...ck.org>,
	<linux-arm-kernel@...ts.infradead.org>, <x86@...nel.org>
Subject: Re: [PATCH v2 01/14] kasan: sw_tags: Use arithmetic shift for shadow
 computation

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@...el.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

Powered by blists - more mailing lists