Ultra-compatible memory mapping

[ramosian-glider]

Originally reported on Google Code with ID 76

Inspired by http://reviews.llvm.org/D6387 and earlier changes to TSan memory layout,
here is a plan to change MSan memory layout to
 * support gdb (i.e. non-ASLR case, with code at 0x555...),
 * support non-PIE (with main executable at 0x40000),
 * and even make origin mapping a little bit cheaper!

#define MEM_TO_SHADOW(x) (x) ^ 0x200000000000ULL;
#define SHADOW_TO_ORIGIN(x) (x) ^ 0x100000000000ULL

I.e., mem-to-shadow mapping flips the second highest bit; shadow-to-origin flips the
third highest bit. This makes mem-to-origin a single XOR, instead of OR+ADD in the
current scheme.

addr 000000000000 shadow 200000000000 origin 300000000000
addr 0fffffffffff shadow 2fffffffffff origin 3fffffffffff
addr 500000000000 shadow 700000000000 origin 600000000000
addr 5d0000000000 shadow 7d0000000000 origin 6d0000000000
addr 7d0000000000 shadow 5d0000000000 origin 4d0000000000
addr 7fffffffffff shadow 5fffffffffff origin 4fffffffffff

000000000000 - 0fffffffffff app-1
100000000000 - 1fffffffffff invalid
200000000000 - 2fffffffffff shadow-1
300000000000 - 3fffffffffff origin-1
400000000000 - 4cffffffffff invalid
4d0000000000 - 4fffffffffff origin-3
500000000000 - 5cffffffffff app-2
5d0000000000 - 5fffffffffff shadow-3
600000000000 - 6cffffffffff origin-2
6d0000000000 - 6fffffffffff invalid
700000000000 - 7cffffffffff shadow-2
7d0000000000 - 7fffffffffff app-3

Looks a bit crazy, but I don't see why it would not work.

Reported by eugenis@google.com on 2014-11-27 09:23:52

[ramosian-glider]

That's Linux-x86_64 of course.
Heap goes to 0x7d..0x7e, as in TSan.

Reported by eugenis@google.com on 2014-11-27 09:24:46

[ramosian-glider]

There is a weird code size (and maybe performance) regression due to llvm doing something
inefficient with xor(xor(x)) on X86:
http://llvm.org/bugs/show_bug.cgi?id=21749

We will probably win more by disabling PIE, so I'm inclined to go ahead with this anyway
and optimize it later. This problem should be fixable with some kind of peephole optimization
in the backend.

Reported by eugenis@google.com on 2014-12-05 12:59:54

[ramosian-glider]

W/o disabling PIE performance measurements are inconclusive.
470.lbm speeds up by ~10% with the new mapping for some reason.
The rest are +-3%.
Code size grows by ~2.5%, but on one of the specs - by close to 10%.

Reported by eugenis@google.com on 2014-12-12 16:32:50

[ramosian-glider]

Here is another idea with all the same properties.

#define MEM_TO_SHADOW(mem) (((uptr)(mem)) ^ 0x500000000000ULL)
#define SHADOW_TO_ORIGIN(mem) (((uptr)(mem)) + 0x100000000000ULL)

Here, shadow-to-origin is an addition of a constant, which can be wrapped into the
addressing mode without using an extra register.

Memory layout:

000000000000 - 050000000000 app-1
050000000000 - 100000000000 shadow-2
100000000000 - 150000000000 invalid
150000000000 - 200000000000 origin-2
200000000000 - 300000000000 shadow-3
300000000000 - 400000000000 origin-3
400000000000 - 500000000000 invalid
500000000000 - 550000000000 shadow-1
550000000000 - 600000000000 app-2
600000000000 - 650000000000 origin-1
650000000000 - 700000000000 invalid
700000000000 - 800000000000 app-3

Performance is the same or better (old, new, new/old ratio):
       400.perlbench,      2822.00,      2849.00,         1.01
           401.bzip2,      1975.00,      1978.00,         1.00
             429.mcf,      1665.00,      1619.00,         0.97
           445.gobmk,      2257.00,      2224.00,         0.99
           456.hmmer,      2954.00,      2977.00,         1.01
           458.sjeng,      3613.00,      3567.00,         0.99
      462.libquantum,      1381.00,      1380.00,         1.00
         464.h264ref,      4348.00,      4366.00,         1.00
           473.astar,      1312.00,      1311.00,         1.00
       483.xalancbmk,      1287.00,      1227.00,         0.95
            433.milc,      1404.00,      1405.00,         1.00
            444.namd,      1684.00,      1690.00,         1.00
          447.dealII,      1309.00,      1305.00,         1.00
          450.soplex,       996.00,       983.00,         0.99
          453.povray,      1505.00,      1519.00,         1.01
             470.lbm,      1325.00,      1329.00,         1.00
         482.sphinx3,      2593.00,      2590.00,         1.00

Code size:
- instrumented code is smaller by 0.5% on average
- run-time library is larger by 40Kb, mostly because MEM_IS_APP(x) check is more complex,
and it is inline in multiple places (ex. all interceptors, as part of __msan_poison()).
A lot of these are redundant and can be removed later.

Reported by eugenis@google.com on 2015-01-26 08:52:12

[ramosian-glider]

attaching the current patchset just in case

Reported by eugenis@google.com on 2015-01-27 15:16:55

---

- _Attachment: [split-layout-compiler-rt.patch](https://storage.googleapis.com/google-code-attachments/memory-sanitizer/issue-76/comment-5/split-layout-compiler-rt.patch)_ - _Attachment: [split-layout-llvm.patch](https://storage.googleapis.com/google-code-attachments/memory-sanitizer/issue-76/comment-5/split-layout-llvm.patch)_

[ramosian-glider]

Adding Project:MemorySanitizer as part of GitHub migration.

Reported by glider@google.com on 2015-07-30 09:22:27

• Labels added: ProjectMemorySanitizer

[eugenis]

The final version differs a bit from above description.
000000000000 - 010000000000 app-1
510000000000 - 600000000000 app-2
(used to be 00-05 and 55-60).
The point is to give more application space in the 50...60 range (that's were randomized binary mappings go with newer linux kernels) at the cost of space in 00..10 range (where we are only interested in the first 4GB to support mmap(MAP_32BITS)). This is not an ABI breaking decision and can be easily changed later.