Page MenuHomePhabricator

[msan] Increase size of app/shadow/origin mappings on aarch64
ClosedPublic

Authored by thurston on Nov 8 2022, 12:58 PM.

Details

Summary

The app memory mappings for aarch64 are limited to 64GB, sometimes smaller in practice. This leads to a crash with the error message "MemorySanitizer can not mmap the shadow memory." (because an "invalid" region cannot be mapped).

This patch makes the app/shadow/origin memory mappings considerably larger, along with corresponding changes to the MEM_TO_SHADOW and SHADOW_TO_ORIGIN constants.

Note that this deprecates compatibility with 39- and 42-bit VMAs.

Diff Detail

Event Timeline

thurston created this revision.Nov 8 2022, 12:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 8 2022, 12:58 PM
thurston requested review of this revision.Nov 8 2022, 12:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 8 2022, 12:58 PM
thurston updated this revision to Diff 474084.Nov 8 2022, 1:42 PM

Removed comment about coverage of 39- and 42-bit mappings, since we have deprecated them.
(We still leave in the general comment about 39- and 42-bit segments, for reference.)

thurston updated this revision to Diff 474085.Nov 8 2022, 1:48 PM

Remove unnnecessary app mapping

kstoimenov accepted this revision.Nov 8 2022, 2:33 PM
This revision is now accepted and ready to land.Nov 8 2022, 2:33 PM
vitalybuka added inline comments.
compiler-rt/lib/msan/msan.h
72

Context not available.

Please prefer to upload patches with "arc" tool, to avoid that.

118

What about this one?

Sorry, I don't follow. What is limited to 64Gb (the sum of all app regions? why does it matter?) and why can't an "invalid" region be mapped?

Sorry, I don't follow. What is limited to 64Gb (the sum of all app regions? why does it matter?) and why can't an "invalid" region be mapped?

msan.h defines the "invalid" regions (anything except the app/origin/shadow), which msan will mprotect. If an app allocates memory outside of msan's expected app regions, msan will refuse to mprotect the invalid region (because it overlaps with the app's existing allocations). To fix this, I increased the app regions (and updated the invalid/origin/shadow regions accordingly).

Increasing the app regions will also increase the shadow and origin regions (they are exactly the same sizes). Since the origin region is calculated as shadow region + 0x1000000000ULL (64GB), if the region size is larger than 64GB, the start of the shadow region will overlap with the end of the origin region. The SHADOW_TO_ORIGIN constant therefore imposes a 64GB limit on the size of each contiguous region. I therefore increased this constant, as well as the MEM_TO_SHADOW XOR constant (which imposes a 384GB limit).

compiler-rt/lib/msan/msan.h
72

Sorry, will do

118

Good catch, thanks. It got lost in the g3 -> llvm diff migration. I'll upload a new diff with arc.

Ah, so is the problem with ASLR randomizing the initial executable mappings over a region larger than 64Gb? We do not care about app allocating memory, heap placement is defined by msan. Could you confirm that the new mapping covers all possible locations? Even with ex. a huge executable binary.

That's ok I guess, if we do not care about /39 and /42 on aarch64 linux. I'm also curious how much dynamic shadow mapping would cost (cpu and code size). It's not as straightforward as with ASan, because MSan can not allocate shadow in a single contiguous block, most likely. But it can save us a lot of pain down the road.

Ah, so is the problem with ASLR randomizing the initial executable mappings over a region larger than 64Gb? We do not care about app allocating memory, heap placement is defined by msan. Could you confirm that the new mapping covers all possible locations? Even with ex. a huge executable binary.

That's ok I guess, if we do not care about /39 and /42 on aarch64 linux. I'm also curious how much dynamic shadow mapping would cost (cpu and code size). It's not as straightforward as with ASan, because MSan can not allocate shadow in a single contiguous block, most likely. But it can save us a lot of pain down the road.

Yes, it is because of ASLR. The app mappings I changed are "app-14" (program segments) and "app-15" (libraries segments).

I tested the new mappings on Google3. On a corpus of 23,000 Google3 test cases:

If we are changing the mapping + the ABI, we should be 100% confident the new one covers all ASLR possibilities. Why not just run some binary a lot of times and collect the range of addresses, or even inspect the kernel source for possible executable locations? Also, make it a large binary.

vitalybuka requested changes to this revision.Nov 17 2022, 2:09 PM
This revision now requires changes to proceed.Nov 17 2022, 2:09 PM
thurston updated this revision to Diff 477317.Nov 22 2022, 3:04 PM

Larger mappings

If we are changing the mapping + the ABI, we should be 100% confident the new one covers all ASLR possibilities. Why not just run some binary a lot of times and collect the range of addresses, or even inspect the kernel source for possible executable locations? Also, make it a large binary.

tl;dr I've enlarged the regions as much as I can; it's not feasible to fully maximize the regions, but AFAICS they're large enough for typical configurations of ASLR.

The kernel source (https://elixir.bootlin.com/linux/v5.19/source/arch/arm64/Kconfig#L267) essentially does:

#define ARCH_MMAP_RND_BITS_MAX 33

for 48-bit VMA. That means each ASLR region is potentially 45-bits i.e., 2/16th of the 48-bit address space.

If we maximize the PIE regions, the address space used is:

  • program (non-PIE): 1/16
  • program (PIE): 2/16
  • libraries (PIE): 2/16
  • TOTAL: 5/16

We need to triple this, to account for the app, shadow and origin regions, which would make up 15/16th of the address space; this is theoretically doable. Unfortunately, if we use the constrained arithmetic (shadow = app XOR constant; origin = shadow + another constant) for performance, there is no set of constants that make a workable (non-overlapping) set of mappings (I brute-forced all possible constants). We would need to look into the dynamic mappings to make it work.

What the current patch does is:

  • program (non-PIE): 1/16
  • program (PIE): 1/16 i.e., half as large as it could theoretically be
  • libraries (PIE): 2/16

In practice, though, systems do not usually maximize the bits of randomness, so this set of mappings works well enough.

Alternatively, there is a workable set of mappings that makes the program (PIE) mapping larger at the expense of the libraries (PIE) mapping.

thurston updated this revision to Diff 477321.Nov 22 2022, 3:23 PM

Whitespace

If there are no concerns about deprecating 39 and 42 bit VMA support in MSan, then I'm fine with this. I'd love to see performance comparison of static vs dynamic shadow, but this is a separate issue.

vitalybuka accepted this revision.Nov 28 2022, 2:34 PM
This revision is now accepted and ready to land.Nov 28 2022, 2:34 PM
This revision was landed with ongoing or failed builds.Nov 29 2022, 12:57 PM
This revision was automatically updated to reflect the committed changes.

Hi, I think this change is currently breaking Fuchsia's Clang CI. https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-arm64/b8796124255499289009/overview

Can you take a look, and if it will be hard to fix, revert until it can be addressed?

Hi, I think this change is currently breaking Fuchsia's Clang CI. https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-arm64/b8796124255499289009/overview

Can you take a look, and if it will be hard to fix, revert until it can be addressed?

Sorry about that. The tests make hardcoded assumptions about the code; I'm working on updating the tests to match the new code. The first CL is already in: https://reviews.llvm.org/rGf5e2481b42fb4539232b5621adcfc03d2eeb4eb7
Other two coming soon.

Hi, I think this change is currently breaking Fuchsia's Clang CI. https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-arm64/b8796124255499289009/overview

Can you take a look, and if it will be hard to fix, revert until it can be addressed?

The other two tests have been fixed in https://reviews.llvm.org/rGb647d8f95d194e15d0335a644947c650f97041df