ASan: move allocator base to avoid conflict with high-entropy ASLR for x86-64 Linux

[thurston]

Summary

Users have discovered [*] that when CONFIG_ARCH_MMAP_RND_BITS == 32,
it will frequently conflict with ASan's allocator on x86-64 Linux, because the
PIE program segment base address of 0x555555555554 plus an ASLR shift of up to
((2**32) * 4K == 0x100000000000) will sometimes exceed ASan's hardcoded
base address of 0x600000000000. We fix this by simply moving the allocator base
to 0x500000000000, which is below the PIE program segment base address. This is
cleaner than trying to move it to another location that is sandwiched between
the PIE program and library segments, because if either of those grow too large,
it will collide with the allocator region.

Note that we will never need to change this base address again (unless we want to increase
the size of the allocator), because ASLR cannot be set above 32-bits for x86-64 Linux (the
PIE program segment and library segments would collide with each other; see also
ARCH_MMAP_RND_BITS_MAX in https://github.com/torvalds/linux/blob/master/arch/x86/Kconfig).

• see https://b.corp.google.com/issues/276925478

and https://groups.google.com/a/google.com/g/chrome-os-gardeners/c/BbfzCP3dEeo/m/h3C_vVUxCQAJ

[thurston]

I ran a mondo comparing the new allocator base vs. old allocator base; the results are within statistical noise (ordinary flakiness).

[MaskRay]

Q: Let a = 0x555555555000 + 2**CONFIG_ARCH_MMAP_RND_BITS * 4096 (is this the max load base in the kernel?), is this patch try to make [a, a+image_size) and [kAllocatorSpace,kAllocatorSpace+kAllocatorSize) not interact?

If yes, 0x500000000000ULL looks like a good choice!

[thurston]

In D147984#4263779, @MaskRay wrote:

Q: Let a = 0x555555555000 + 2**CONFIG_ARCH_MMAP_RND_BITS * 4096 (is this the max load base in the kernel?), is this patch try to make [a, a+image_size) and [kAllocatorSpace,kAllocatorSpace+kAllocatorSize) not interact?

Yes, that is one of the constraints.

The other constraint is: let b be the library segments, which start at roughly (ignoring the stack) 0x7FFFFFFFFFFF - 2**CONFIG_ARCH_MMAP_RND_BITS * 4096, growing downwards. We need to have [b, b-library_images_size] and [kAllocatorSpace,kAllocatorSpace+kAllocatorSize) not conflict either.

For "reasonable" sizes of image_size, library_images_size and allocator_size, it's actually possible to squeeze the allocator in between the program segment and library segment regions ((0x7fffffffffff - 0x555500000000 - 2* ((2**32) * 4096)) = 10.7TB that can be distributed between the three sizes), but placing it underneath the program segments sidesteps the issue entirely.

Bonus pics of the ASan memory layout before and after the change: https://docs.google.com/presentation/d/1z39DhQxUCT31OBOWWAtjd48BwCm0PgXeaG67QDs3TZI/edit

[MaskRay]

In D147984#4263790, @thurston wrote:

In D147984#4263779, @MaskRay wrote:

Q: Let a = 0x555555555000 + 2**CONFIG_ARCH_MMAP_RND_BITS * 4096 (is this the max load base in the kernel?), is this patch try to make [a, a+image_size) and [kAllocatorSpace,kAllocatorSpace+kAllocatorSize) not interact?

Yes, that is one of the constraints.

The other constraint is: let b be the library segments, which start at roughly (ignoring the stack) 0x7FFFFFFFFFFF - 2**CONFIG_ARCH_MMAP_RND_BITS * 4096, growing downwards. We need to have [b, b-library_images_size] and [kAllocatorSpace,kAllocatorSpace+kAllocatorSize) not conflict either.

For "reasonable" sizes of image_size, library_images_size and allocator_size, it's actually possible to squeeze the allocator in between the program segment and library segment regions ((0x7fffffffffff - 0x555500000000 - 2* ((2**32) * 4096)) = 10.7TB that can be distributed between the three sizes), but placing it underneath the program segments sidesteps the issue entirely.

Bonus pics of the ASan memory layout before and after the change: https://docs.google.com/presentation/d/1z39DhQxUCT31OBOWWAtjd48BwCm0PgXeaG67QDs3TZI/edit

Thank you! The formula and the doc are very useful. I have some understanding of CONFIG_ARCH_MMAP_RND_BITS now...

[hans]

This broke the lit tests on Mac: LeakSanitizer-AddressSanitizer-x86_64 :: TestCases/Darwin/trampoline.mm
@lgrey who added that in D129385 maybe has some idea of what's going on?

I'll revert this for now.

[lgrey]

In D147984#4264112, @hans wrote:

This broke the lit tests on Mac: LeakSanitizer-AddressSanitizer-x86_64 :: TestCases/Darwin/trampoline.mm
@lgrey who added that in D129385 maybe has some idea of what's going on?

I'll revert this for now.

Thanks, looking now. Since this wasn't intended to affect Darwin anyway, it can probably reland with SANITIZER_APPLE excluded

[MaskRay]

Confining this to non-Apple platforms looks good to me.

Note that this change (I believe) also affects other less-used 64-bit platforms like s390x/mips64 that I don't know how to test... I think they are likely fine with the change but I cannot say for sure.
Does the Linux kernel documentation give some way to derive the memory mapping layout easily? ;-)

[thurston]

In D147984#4266106, @MaskRay wrote:

Confining this to non-Apple platforms looks good to me.

Note that this change (I believe) also affects other less-used 64-bit platforms like s390x/mips64 that I don't know how to test... I think they are likely fine with the change but I cannot say for sure.

Good point. How about limiting the change to SANITIZER_LINUX && (defined(__x86_64__)?

Does the Linux kernel documentation give some way to derive the memory mapping layout easily? ;-)

Dynamically or statically?

[MaskRay]

In D147984#4266183, @thurston wrote:

In D147984#4266106, @MaskRay wrote:

Confining this to non-Apple platforms looks good to me.

Note that this change (I believe) also affects other less-used 64-bit platforms like s390x/mips64 that I don't know how to test... I think they are likely fine with the change but I cannot say for sure.

Good point. How about limiting the change to SANITIZER_LINUX && (defined(__x86_64__)?

Not needed:) I have tested this on an AArch64 Linux machine and it works fine.
I think it works with aarch64/amd64 FreeBSD as well and have a fair chance to work on s390x/mips.
Perhaps just Apple platforms need to be excluded.

Does the Linux kernel documentation give some way to derive the memory mapping layout easily? ;-)

Dynamically or statically?

Statically to judge whether a kAllocatorSpace choice without having to run programs in a qemu-system environment:)

[thurston]

In D147984#4266218, @MaskRay wrote:

In D147984#4266183, @thurston wrote:

In D147984#4266106, @MaskRay wrote:

Confining this to non-Apple platforms looks good to me.

Note that this change (I believe) also affects other less-used 64-bit platforms like s390x/mips64 that I don't know how to test... I think they are likely fine with the change but I cannot say for sure.

Good point. How about limiting the change to SANITIZER_LINUX && (defined(__x86_64__)?

Not needed:) I have tested this on an AArch64 Linux machine and it works fine.
I think it works with aarch64/amd64 FreeBSD as well and have a fair chance to work on s390x/mips.
Perhaps just Apple platforms need to be excluded.

I wouldn't want to risk breaking anyone's S390 or MIPS setups. How about making it (SANITIZER_FREEBSD || SANITIZER_LINUX) && (defined(__x86_64__)?
(It's not necessary to opt-in aarch64 because the old mapping also works for them.)

Does the Linux kernel documentation give some way to derive the memory mapping layout easily? ;-)

Dynamically or statically?

Statically to judge whether a kAllocatorSpace choice without having to run programs in a qemu-system environment:)

That's pretty hard AFAICS. The kernel source code doesn't actually define constants such as 0x555555550000 (the program segment start location) - which made it fun trying to reverse engineer :-). The magic happens in:

#define ELF_ET_DYN_BASE		(2 * DEFAULT_MAP_WINDOW_64 / 3)

and then you need to go down the rabbit hole to find the DEFAULT_MAP_WINDOW_64 value (which is defined in terms of VA_BITS_MIN ...). We also need to calculate ASLR, and the library segments start location and stack size (if we want to place the allocator in between the library and program segments).

We also need to make sure that the allocator doesn't conflict with ASan's shadow mappings, though that can be trivially solved at runtime.

[MaskRay]

In D147984#4266390, @thurston wrote:

In D147984#4266218, @MaskRay wrote:

In D147984#4266183, @thurston wrote:

In D147984#4266106, @MaskRay wrote:

Confining this to non-Apple platforms looks good to me.

Note that this change (I believe) also affects other less-used 64-bit platforms like s390x/mips64 that I don't know how to test... I think they are likely fine with the change but I cannot say for sure.

Good point. How about limiting the change to SANITIZER_LINUX && (defined(__x86_64__)?

Not needed:) I have tested this on an AArch64 Linux machine and it works fine.
I think it works with aarch64/amd64 FreeBSD as well and have a fair chance to work on s390x/mips.
Perhaps just Apple platforms need to be excluded.

I wouldn't want to risk breaking anyone's S390 or MIPS setups. How about making it (SANITIZER_FREEBSD || SANITIZER_LINUX) && (defined(__x86_64__)?
(It's not necessary to opt-in aarch64 because the old mapping also works for them.)

I have checked mappings on an x86-64 FreeBSD machine. The address is fine. aarch64 FreeBSD should behave similarly.

I think there is very large chance that 0x500000000000ULL will work for s390x and mips64, so we don't need to be too defensive here.
In the worst case s390x and mips64 can opt out in a future commit...

Does the Linux kernel documentation give some way to derive the memory mapping layout easily? ;-)

Dynamically or statically?

Statically to judge whether a kAllocatorSpace choice without having to run programs in a qemu-system environment:)

That's pretty hard AFAICS. The kernel source code doesn't actually define constants such as 0x555555550000 (the program segment start location) - which made it fun trying to reverse engineer :-). The magic happens in:

#define ELF_ET_DYN_BASE		(2 * DEFAULT_MAP_WINDOW_64 / 3)

and then you need to go down the rabbit hole to find the DEFAULT_MAP_WINDOW_64 value (which is defined in terms of VA_BITS_MIN ...). We also need to calculate ASLR, and the library segments start location and stack size (if we want to place the allocator in between the library and program segments).

We also need to make sure that the allocator doesn't conflict with ASan's shadow mappings, though that can be trivially solved at runtime.

Reading #define ELF_ET_DYN_BASE is how I approached this as well. Sigh, no good way...

[thurston]

Thanks hans for the heads up about the failed test and taking care of the revert, and lgrey and MaskRay for the advice on how to revise the patch! It's been re-landed (with the suggested change) in D148280.

compiler-rt/lib/asan/asan_allocator.h

 const uptr kAllocatorSpace = ~(uptr)0;
 const uptr kAllocatorSize = 0x20000000000ULL;  // 2T.
 typedef DefaultSizeClassMap SizeClassMap;
 # elif SANITIZER_WINDOWS
 const uptr kAllocatorSpace = ~(uptr)0;
 const uptr kAllocatorSize  =  0x8000000000ULL;  // 500G
 typedef DefaultSizeClassMap SizeClassMap;
 # else
-const uptr kAllocatorSpace = 0x600000000000ULL;
+const uptr kAllocatorSpace = 0x500000000000ULL;
 const uptr kAllocatorSize  =  0x40000000000ULL;  // 4T.
 typedef DefaultSizeClassMap SizeClassMap;
 # endif
 template <typename AddressSpaceViewTy>
 struct AP64 {  // Allocator64 parameters. Deliberately using a short name.
   static const uptr kSpaceBeg = kAllocatorSpace;
   static const uptr kSpaceSize = kAllocatorSize;
   static const uptr kMetadataSize = 0;