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

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

On 2025-03-07 at 02:10:39 +0100, Andrey Konovalov wrote:
>On Tue, Mar 4, 2025 at 3:08 PM Maciej Wieczor-Retman
><maciej.wieczor-retman@intel.com> wrote:
>>
>> But looking at the patch you sent I'm wondering - are we treating the arithmetic
>> in kasan_mem_to_shadow() as unsigned?
>
>The shift is signed (arithmetic). But for the addition, it doesn't
>matter? Adding an integer to a void* pointer should result in the same
>value, regardless of whether the integer is signed or unsigned.

Yes, you're right, sorry.

>
>> You wrote that all the ranges will
>> overflow but I thought we're interpreting the arithmetic as signed - so only
>> positive addresses will overflow and negative addresses (with bit 63 set) will
>> only be more negative thus not causing an overflow.
>
>Ah, yes, I see what you mean. From the C point of view, calculating
>the shadow address for a pointer with bit 63 set can be interpreted as
>subtracting from KASAN_SHADOW_OFFSET, and there's no overflow. But on
>the assembly level, the compiler should generate the add instruction,
>and the addition will overflow in both cases.
>
>The important thing is that both possible shadow memory ranges are
>contiguous (either both start and end overflow or none of them).
>
>So this was my brain converting things to assembly. Feel free to
>reword/clarify the comments.

Right, I focused too much on the signed aspect. Treating everything as
overflowing sounds better, more unified.

>
>> That was my assumption when
>> writing the previous checks - we need to check below the overflown range, above
>> the negative (not overflown) range, and between the two.
>
>It could be that your checks are equivalent to mine. What I did was to
>check that the address lies outside of both contiguous regions, which
>makes the checks symmetrical and IMO easier to follow.

I drew this out and yeah, it looks like it's the same, just grouping the logical
expressions differently. What do you think about incorporating something like
the following into your comment about the x86 part? :

	Given the KASAN_SHADOW_OFFSET equal 0xffeffc0000000000
	the following ranges are valid mem-to-shadow mappings:

	0xFFFFFFFFFFFFFFFF
		INVALID
	0xFFEFFBFFFFFFFFFF - kasan_mem_to_shadow(~0UL)
		VALID	- kasan shadow mem
		VALID	- non-canonical kernel virtual address
	0xFFCFFC0000000000 - kasan_mem_to_shadow(0xFEUL << 56)
		INVALID
	0x07EFFBFFFFFFFFFF - kasan_mem_to_shadow(~0UL >> 1)
		VALID	- non-canonical user virtual addresses
		VALID	- user addresses
	0x07CFFC0000000000 - kasan_mem_to_shadow(0x7EUL << 56)
		INVALID
	0x0000000000000000

-- 
Kind regards
Maciej Wieczór-Retman