[Tsan] How shadow memory is determined？

[847567161]

Hello guys, 

  I'm enabling Tsan on Openharmony and  have a few questions:

  Q1: Why do tsan need to close ASLR,  the previous email mentioned that it will speed up the check, could you give more details?

  Q2: How is the address range of MappingAarch64_39 in tsan_platform.h determined, how is it adapted to the kernel, and where can I find how kernel set them？

 https://gitee.com/openharmony/third_party_llvm-project/blob/master/compiler-rt/lib/tsan/rtl/tsan_platform.h#L149

  Q3：How the scope of shadow memory is determined？How the values of Mapping::kShadowMsk and Mapping::kShadowXor are determined？ What is the logic behind this function？

struct MemToShadowImpl {
  template <typename Mapping>
  static uptr Apply(uptr x) {
    DCHECK(IsAppMemImpl::Apply<Mapping>(x));
    return (((x) & ~(Mapping::kShadowMsk | (kShadowCell - 1))) ^
            Mapping::kShadowXor) *
               kShadowMultiplier +
           Mapping::kShadowAdd;
  }
};

https://gitee.com/openharmony/third_party_llvm-project/blob/master/compiler-rt/lib/tsan/rtl/tsan_platform.h#L768

[Thurston Dang]

I'll answer these questions out of order because that will (hopefully) naturally explain why TSan is the way it is.

On Thu, Mar 14, 2024 at 6:52 PM '847567161' via thread-sanitizer <thread-s...@googlegroups.com> wrote:

Hello guys, 

  I'm enabling Tsan on Openharmony and  have a few questions: 

  Q1: Why do tsan need to close ASLR,  the previous email mentioned that it will speed up the check, could you give more details?

Conceptually, MemToShadowImpl::Apply() could just use a hash table that maps any App memory address to a Shadow memory address. With this method, ASLR doesn't matter. Unfortunately, the hash table method is relatively slow.

Instead, TSan uses a simple mathematical formula (explained below) that maps App memory addresses to Shadow memory addresses.

However, aggressive ASLR means that there is a wide range of App memory addresses that the binaries/libraries could be loaded into; we would also need to have a wide range of corresponding Shadow memory areas, and that's very hard (and often infeasible, because shadow memory takes 2.5x as much memory compared to App memory). If ASLR is too aggressive, TSan will disable ASLR entirely.

 

how is it adapted to the kernel, and where can I find how kernel set them？

- High App: PIE libraries (top of the address space):

https://elixir.bootlin.com/linux/latest/source/mm/util.c#L415

static unsigned long mmap_base(unsigned long rnd, struct rlimit *rlim_stack)

- Mid App: PIE binaries (2/3rd of the address space):

https://elixir.bootlin.com/linux/v5.19.17/source/arch/arm64/include/asm/elf.h#L131

/*
 * This is the base location for PIE (ET_DYN with INTERP) loads. On
 * 64-bit, this is above 4GB to leave the entire 32-bit address
 * space open for things that want to use the area for 32-bit pointers.
 */
#ifdef CONFIG_ARM64_FORCE_52BIT
#define ELF_ET_DYN_BASE (2 * TASK_SIZE_64 / 3)
#else
#define ELF_ET_DYN_BASE (2 * DEFAULT_MAP_WINDOW_64 / 3)
#endif /* CONFIG_ARM64_FORCE_52BIT */

- Low App: Non-PIE (bottom of the address space)

Citation is left as an exercise for the reader :-)

- ASLR setting:

https://elixir.bootlin.com/linux/v6.6.6/source/arch/Kconfig#L1031
'config ARCH_MMAP_RND_BITS
int "Number of bits to use for ASLR of mmap base address" if EXPERT

 

What is the logic behind this function？

struct MemToShadowImpl {
  template <typename Mapping>
  static uptr Apply(uptr x) {
    DCHECK(IsAppMemImpl::Apply<Mapping>(x));
    return (((x) & ~(Mapping::kShadowMsk | (kShadowCell - 1))) ^
            Mapping::kShadowXor) *
               kShadowMultiplier +
           Mapping::kShadowAdd;
  }
};

https://gitee.com/openharmony/third_party_llvm-project/blob/master/compiler-rt/lib/tsan/rtl/tsan_platform.h#L768

We can derive this from first principles, given these design requirements for a function that will map App memory to shadow memory:
1) Each 8 byte chunk of App memory is mapped to 16 bytes of shadow memory.
2a) High App memory region (from the top of the address space) maps to High Shadow
2b) Mid App memory region maps to Mid Shadow
2c) Low App memory region maps to Low Shadow
3) Every app and shadow region does not overlap
(I've omitted a few other constraints, such as "linearity" and "aliased metas", that are explained in tsan/rtl/tsan_platform.h.)

The easiest (fastest) way to fulfil requirement 1) is to do:

((x) & ~(kShadowCell - 1)) * kShadowMultiplier

where kShadowCell == 8, and kShadowMultiplier == 2. (Try substituting some values to see what happens.)

How do we fulfil requirement 2)? Because of the "constant folding" compiler optimization, we can do a bitwise AND of another constant for free:

((x) & ~(kShadowMsk | kShadowCell - 1)) * kShadowMultiplier

If we're clever with kShadowMsk, we can fulfil requirements 2a) and 2b), because bitwise AND'ing can result in a lower numeric value. However, no matter what value of kShadowMsk we choose, it cannot fulfil requirement 2c): the Low App region starts at zero, and bitwise AND'ing by any value will not move it above zero.

How can we fulfil requirement 2c)? Perhaps we could add a constant:

(((x) & ~(kShadowMsk | kShadowCell - 1)) + kShadowOffset)* kShadowMultiplier

but the way that was chosen for TSan was to use carefully selected XORs:

(((x) & ~(kShadowMsk | kShadowCell - 1)) ^ kShadowXor) * kShadowMultiplier

 

  Q3：How the scope of shadow memory is determined？

We want to make the Mid App region (starting at 2/3rd, and growing upwards) and the High App region (starting from the top, growing downwards) as large as possible, because 1) some binaries/libraries can be very large (gigabytes) 2) the kernel may randomize the placement within those locations, due to ASLR. However, it's hard to make the App regions too large, because the App regions have corresponding shadow regions.

(Minor optimization: TSan defines a single Shadow region and a single Meta region. These span the Low/Mid/High Shadow and Meta regions respectively.)

 https://gitee.com/openharmony/third_party_llvm-project/blob/master/compiler-rt/lib/tsan/rtl/tsan_platform.h#L149

  Q2: How is the address range of MappingAarch64_39 in tsan_platform.h determined, 

How the values of Mapping::kShadowMsk and Mapping::kShadowXor are determined？  

By trial and error, given all the constraints listed above. The kernel defines one end of the Low/Mid/High app regions; we then try to make those app regions as large as possible, and devise kShadowMsk/kShadowXor/kShadowAdd constants that will map appropriate corresponding shadow regions.

A fun (and/or frustrating) exercise: given

  static const uptr kLoAppMemBeg   = 0x0000001000ull;
  static const uptr kLoAppMemEnd   = 0x0100000000ull;
  static const uptr kMidAppMemBeg  = 0x5500000000ull;
  static const uptr kMidAppMemEnd = 0x5600000000ull;
  static const uptr kHiAppMemBeg   = 0x7e00000000ull;
  static const uptr kHiAppMemEnd   = 0x7fffffffffull;
do some experimentation to come up with your own set of kShadowMsk/kShadowXor/kShadowAdd constants (given the MemToShadow formula) and calculate where the corresponding shadow memory regions are.

Regards,

 Thurston

[Thurston Dang]

On Fri, Mar 15, 2024 at 6:52 AM 847567161 <8475...@qq.com> wrote:

Thank you very much for these explanations.

Another question is: How Tsan implement ignore_noninstrumented_modules? I don't see how to identify the no-instremented so in Tsan.

I'm not familiar with this aspect of TSan, but from a cursory glance, it looks like it depends on sanitizer_common functionality: tsan_rtl.cpp::Initialize() calls tsan_interceptors_posix.cpp::InitializeLibIgnore() which in turn calls sanitizer_common/sanitizer_lignore.h::IgnoreNoninstrumentedModules().

Regards,

 Thurston

 

------------------ 原始邮件 ------------------

发件人: "Thurston Dang" <thur...@google.com>;

发送时间: 2024年3月15日(星期五) 中午1:22

收件人: "847567161"<8475...@qq.com>;

抄送: "thread-sanitizer"<thread-s...@googlegroups.com>;

主题: Re: [Tsan] How shadow memory is determined？