On Tue, Oct 22, 2024 at 3:59 AM Samuel Holland <samuel.holland@xxxxxxxxxx> wrote: > > Currently, kasan_mem_to_shadow() uses a logical right shift, which turns > canonical kernel addresses into non-canonical addresses by clearing the > high KASAN_SHADOW_SCALE_SHIFT bits. The value of KASAN_SHADOW_OFFSET is > then chosen so that the addition results in a canonical address for the > shadow memory. > > For KASAN_GENERIC, this shift/add combination is ABI with the compiler, > because KASAN_SHADOW_OFFSET is used in compiler-generated inline tag > checks[1], which must only attempt to dereference canonical addresses. > > However, for KASAN_SW_TAGS we have some freedom to change the algorithm > without breaking the ABI. Because TBI is enabled for kernel addresses, > the top bits of shadow memory addresses computed during tag checks are > irrelevant, and so likewise are the top bits of KASAN_SHADOW_OFFSET. > This is demonstrated by the fact that LLVM uses a logical right shift > in the tag check fast path[2] but a sbfx (signed bitfield extract) > instruction in the slow path[3] without causing any issues. > > Using an arithmetic shift in kasan_mem_to_shadow() provides a number of > benefits: > > 1) The memory layout is easier to understand. KASAN_SHADOW_OFFSET > becomes a canonical memory address, and the shifted pointer becomes a > negative offset, so KASAN_SHADOW_OFFSET == KASAN_SHADOW_END regardless > of the shift amount or the size of the virtual address space. > > 2) KASAN_SHADOW_OFFSET becomes a simpler constant, requiring only one > instruction to load instead of two. Since it must be loaded in each > function with a tag check, this decreases kernel text size by 0.5%. > > 3) This shift and the sign extension from kasan_reset_tag() can be > combined into a single sbfx instruction. When this same algorithm change > is applied to the compiler, it removes an instruction from each inline > tag check, further reducing kernel text size by an additional 4.6%. > > These benefits extend to other architectures as well. On RISC-V, where > the baseline ISA does not shifted addition or have an equivalent to the > sbfx instruction, loading KASAN_SHADOW_OFFSET is reduced from 3 to 2 > instructions, and kasan_mem_to_shadow(kasan_reset_tag(addr)) similarly > combines two consecutive right shifts. > > Link: https://github.com/llvm/llvm-project/blob/llvmorg-20-init/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp#L1316 [1] > Link: https://github.com/llvm/llvm-project/blob/llvmorg-20-init/llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp#L895 [2] > Link: https://github.com/llvm/llvm-project/blob/llvmorg-20-init/llvm/lib/Target/AArch64/AArch64AsmPrinter.cpp#L669 [3] > Signed-off-by: Samuel Holland <samuel.holland@xxxxxxxxxx> > --- > > Changes in v2: > - Improve the explanation for how KASAN_SHADOW_END is derived > - Update the range check in kasan_non_canonical_hook() > > arch/arm64/Kconfig | 10 +++++----- > arch/arm64/include/asm/memory.h | 17 +++++++++++++++-- > arch/arm64/mm/kasan_init.c | 7 +++++-- > include/linux/kasan.h | 10 ++++++++-- > mm/kasan/report.c | 22 ++++++++++++++++++---- > scripts/gdb/linux/mm.py | 5 +++-- > 6 files changed, 54 insertions(+), 17 deletions(-) > > diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig > index fd9df6dcc593..6a326908c941 100644 > --- a/arch/arm64/Kconfig > +++ b/arch/arm64/Kconfig > @@ -418,11 +418,11 @@ config KASAN_SHADOW_OFFSET > default 0xdffffe0000000000 if ARM64_VA_BITS_42 && !KASAN_SW_TAGS > default 0xdfffffc000000000 if ARM64_VA_BITS_39 && !KASAN_SW_TAGS > default 0xdffffff800000000 if ARM64_VA_BITS_36 && !KASAN_SW_TAGS > - default 0xefff800000000000 if (ARM64_VA_BITS_48 || (ARM64_VA_BITS_52 && !ARM64_16K_PAGES)) && KASAN_SW_TAGS > - default 0xefffc00000000000 if (ARM64_VA_BITS_47 || ARM64_VA_BITS_52) && ARM64_16K_PAGES && KASAN_SW_TAGS > - default 0xeffffe0000000000 if ARM64_VA_BITS_42 && KASAN_SW_TAGS > - default 0xefffffc000000000 if ARM64_VA_BITS_39 && KASAN_SW_TAGS > - default 0xeffffff800000000 if ARM64_VA_BITS_36 && KASAN_SW_TAGS > + default 0xffff800000000000 if (ARM64_VA_BITS_48 || (ARM64_VA_BITS_52 && !ARM64_16K_PAGES)) && KASAN_SW_TAGS > + default 0xffffc00000000000 if (ARM64_VA_BITS_47 || ARM64_VA_BITS_52) && ARM64_16K_PAGES && KASAN_SW_TAGS > + default 0xfffffe0000000000 if ARM64_VA_BITS_42 && KASAN_SW_TAGS > + default 0xffffffc000000000 if ARM64_VA_BITS_39 && KASAN_SW_TAGS > + default 0xfffffff800000000 if ARM64_VA_BITS_36 && KASAN_SW_TAGS > default 0xffffffffffffffff > > config UNWIND_TABLES > diff --git a/arch/arm64/include/asm/memory.h b/arch/arm64/include/asm/memory.h > index 0480c61dbb4f..a93fc9dc16f3 100644 > --- a/arch/arm64/include/asm/memory.h > +++ b/arch/arm64/include/asm/memory.h > @@ -80,7 +80,8 @@ > * where KASAN_SHADOW_SCALE_SHIFT is the order of the number of bits that map > * to a single shadow byte and KASAN_SHADOW_OFFSET is a constant that offsets > * the mapping. Note that KASAN_SHADOW_OFFSET does not point to the start of > - * the shadow memory region. > + * the shadow memory region, since not all possible addresses have shadow > + * memory allocated for them. I'm not sure this addition makes sense: the original statement was to point out that KASAN_SHADOW_OFFSET and KASAN_SHADOW_START are different values. Even if we were to map shadow for userspace, KASAN_SHADOW_OFFSET would still be a weird offset value for Generic KASAN. > * > * Based on this mapping, we define two constants: > * > @@ -89,7 +90,15 @@ > * > * KASAN_SHADOW_END is defined first as the shadow address that corresponds to > * the upper bound of possible virtual kernel memory addresses UL(1) << 64 > - * according to the mapping formula. > + * according to the mapping formula. For Generic KASAN, the address in the > + * mapping formula is treated as unsigned (part of the compiler's ABI), so the > + * end of the shadow memory region is at a large positive offset from > + * KASAN_SHADOW_OFFSET. For Software Tag-Based KASAN, the address in the > + * formula is treated as signed. Since all kernel addresses are negative, they > + * map to shadow memory below KASAN_SHADOW_OFFSET, making KASAN_SHADOW_OFFSET > + * itself the end of the shadow memory region. (User pointers are positive and > + * would map to shadow memory above KASAN_SHADOW_OFFSET, but shadow memory is > + * not allocated for them.) This looks good! > * > * KASAN_SHADOW_START is defined second based on KASAN_SHADOW_END. The shadow > * memory start must map to the lowest possible kernel virtual memory address > @@ -100,7 +109,11 @@ > */ > #if defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS) > #define KASAN_SHADOW_OFFSET _AC(CONFIG_KASAN_SHADOW_OFFSET, UL) > +#ifdef CONFIG_KASAN_GENERIC > #define KASAN_SHADOW_END ((UL(1) << (64 - KASAN_SHADOW_SCALE_SHIFT)) + KASAN_SHADOW_OFFSET) > +#else > +#define KASAN_SHADOW_END KASAN_SHADOW_OFFSET > +#endif > #define _KASAN_SHADOW_START(va) (KASAN_SHADOW_END - (UL(1) << ((va) - KASAN_SHADOW_SCALE_SHIFT))) > #define KASAN_SHADOW_START _KASAN_SHADOW_START(vabits_actual) > #define PAGE_END KASAN_SHADOW_START > diff --git a/arch/arm64/mm/kasan_init.c b/arch/arm64/mm/kasan_init.c > index b65a29440a0c..6836e571555c 100644 > --- a/arch/arm64/mm/kasan_init.c > +++ b/arch/arm64/mm/kasan_init.c > @@ -198,8 +198,11 @@ static bool __init root_level_aligned(u64 addr) > /* The early shadow maps everything to a single page of zeroes */ > asmlinkage void __init kasan_early_init(void) > { > - BUILD_BUG_ON(KASAN_SHADOW_OFFSET != > - KASAN_SHADOW_END - (1UL << (64 - KASAN_SHADOW_SCALE_SHIFT))); > + if (IS_ENABLED(CONFIG_KASAN_GENERIC)) > + BUILD_BUG_ON(KASAN_SHADOW_OFFSET != > + KASAN_SHADOW_END - (1UL << (64 - KASAN_SHADOW_SCALE_SHIFT))); > + else > + BUILD_BUG_ON(KASAN_SHADOW_OFFSET != KASAN_SHADOW_END); > BUILD_BUG_ON(!IS_ALIGNED(_KASAN_SHADOW_START(VA_BITS), SHADOW_ALIGN)); > BUILD_BUG_ON(!IS_ALIGNED(_KASAN_SHADOW_START(VA_BITS_MIN), SHADOW_ALIGN)); > BUILD_BUG_ON(!IS_ALIGNED(KASAN_SHADOW_END, SHADOW_ALIGN)); > diff --git a/include/linux/kasan.h b/include/linux/kasan.h > index 00a3bf7c0d8f..03b440658817 100644 > --- a/include/linux/kasan.h > +++ b/include/linux/kasan.h > @@ -58,8 +58,14 @@ int kasan_populate_early_shadow(const void *shadow_start, > #ifndef kasan_mem_to_shadow > static inline void *kasan_mem_to_shadow(const void *addr) > { > - return (void *)((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT) > - + KASAN_SHADOW_OFFSET; > + void *scaled; > + > + if (IS_ENABLED(CONFIG_KASAN_GENERIC)) > + scaled = (void *)((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT); > + else > + scaled = (void *)((long)addr >> KASAN_SHADOW_SCALE_SHIFT); > + > + return KASAN_SHADOW_OFFSET + scaled; > } > #endif > > diff --git a/mm/kasan/report.c b/mm/kasan/report.c > index b48c768acc84..c08097715686 100644 > --- a/mm/kasan/report.c > +++ b/mm/kasan/report.c > @@ -644,15 +644,29 @@ void kasan_report_async(void) > */ > void kasan_non_canonical_hook(unsigned long addr) > { > + unsigned long max_shadow_size = BIT(BITS_PER_LONG - KASAN_SHADOW_SCALE_SHIFT); > unsigned long orig_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. > + * 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 > + * KASAN_SHADOW_OFFSET is the smallest possible shadow address. For This part of the comment doesn't seem correct: KASAN_SHADOW_OFFSET is still a weird offset value for Generic KASAN, not the smallest possible shadow address. > + * Software Tag-Based KASAN, the displacement is signed, so > + * KASAN_SHADOW_OFFSET is the center of the range. > */ > - if (addr < KASAN_SHADOW_OFFSET) > - return; > + if (IS_ENABLED(CONFIG_KASAN_GENERIC)) { > + if (addr < KASAN_SHADOW_OFFSET || > + addr >= KASAN_SHADOW_OFFSET + max_shadow_size) > + return; > + } else { > + if (addr < KASAN_SHADOW_OFFSET - max_shadow_size / 2 || > + addr >= KASAN_SHADOW_OFFSET + max_shadow_size / 2) > + return; Hm, I might be wrong, but I think this check does not work. Let's say we have non-canonical address 0x4242424242424242 and number of VA bits is 48. Then: KASAN_SHADOW_OFFSET == 0xffff800000000000 kasan_mem_to_shadow(0x4242424242424242) == 0x0423a42424242424 max_shadow_size == 0x1000000000000000 KASAN_SHADOW_OFFSET - max_shadow_size / 2 == 0xf7ff800000000000 KASAN_SHADOW_OFFSET + max_shadow_size / 2 == 0x07ff800000000000 (overflows) 0x0423a42424242424 is < than 0xf7ff800000000000, so the function will wrongly return. > + } > > orig_addr = (unsigned long)kasan_shadow_to_mem((void *)addr); > Just to double-check: kasan_shadow_to_mem() and addr_has_metadata() don't need any changes, right? > diff --git a/scripts/gdb/linux/mm.py b/scripts/gdb/linux/mm.py > index 7571aebbe650..2e63f3dedd53 100644 > --- a/scripts/gdb/linux/mm.py > +++ b/scripts/gdb/linux/mm.py > @@ -110,12 +110,13 @@ class aarch64_page_ops(): > self.KERNEL_END = gdb.parse_and_eval("_end") > > if constants.LX_CONFIG_KASAN_GENERIC or constants.LX_CONFIG_KASAN_SW_TAGS: > + self.KASAN_SHADOW_OFFSET = constants.LX_CONFIG_KASAN_SHADOW_OFFSET > if constants.LX_CONFIG_KASAN_GENERIC: > self.KASAN_SHADOW_SCALE_SHIFT = 3 > + self.KASAN_SHADOW_END = (1 << (64 - self.KASAN_SHADOW_SCALE_SHIFT)) + self.KASAN_SHADOW_OFFSET > else: > self.KASAN_SHADOW_SCALE_SHIFT = 4 > - self.KASAN_SHADOW_OFFSET = constants.LX_CONFIG_KASAN_SHADOW_OFFSET > - self.KASAN_SHADOW_END = (1 << (64 - self.KASAN_SHADOW_SCALE_SHIFT)) + self.KASAN_SHADOW_OFFSET > + self.KASAN_SHADOW_END = self.KASAN_SHADOW_OFFSET > self.PAGE_END = self.KASAN_SHADOW_END - (1 << (self.vabits_actual - self.KASAN_SHADOW_SCALE_SHIFT)) > else: > self.PAGE_END = self._PAGE_END(self.VA_BITS_MIN) > -- > 2.45.1 > Could you also check that everything works when CONFIG_KASAN_SW_TAGS + CONFIG_KASAN_OUTLINE? I think it should, be makes sense to confirm. Thank you!
