[esan] EfficiencySanitizer shadow memory

[bruening]

Summary

Adds shadow memory mapping support common to all tools to the new
Efficiencysanitizer ("esan") family of tools. This includes:

+ Shadow memory layout and mapping support for 64-bit Linux for any

power-of-2 scale-down (1x, 2x, 4x, 8x, 16x, etc.) that ensures that
shadow(shadow(address)) does not overlap shadow or application
memory.

+ Mmap interception to ensure the application does not map on top of

our shadow memory.

+ Init-time sanity checks for shadow regions.

+ A test of the mmap conflict mechanism.

[filcab]

The OS-related stuff like fix_mmap_addr should be in a esan_posix.cc file, which can include external headers (like the ones in asan do).
That way you don't need to hard-code values or anything, you just include the required headers.

Can you explain a bit better why there's so much complexity around the mapping? I have some inline comments about it.

Thank you,

Filipe

lib/esan/esan.cpp

68 ↗

(On Diff #56152)

Don't abbreviate "offset".

72 ↗

(On Diff #56152)

Why loop over the regions and mapping them to different shadow regions? Why not do the same as ASan and use the system's virtual memory to your advantage, by simply mapping a huge region which covers everything you want, especially since your shadow is so much smaller?

73 ↗

(On Diff #56152)

ShadowStart

74 ↗

(On Diff #56152)

Why?
Do we want the byte after the last shadow byte and this may not be the same as the shadow of the byte past the last byte of the region? When does that happen?

75 ↗

(On Diff #56152)

[start,end) is a better way to show half-open ranges (like what ASan does when it shows the mapping).

lib/esan/esan_interceptors.cpp

26 ↗

(On Diff #56152)

No.
This should, at the very least, be under an #if SANITIZER_LINUX, since it's clearly Linux only.
I think we might end up not needing this, either.

425 ↗

(On Diff #56152)

What if addr+sz gets to the next region?

lib/esan/esan_shadow.h

47 ↗

(On Diff #56152)

Don't abbreviate "offset" (same for next line).

50 ↗

(On Diff #56152)

What is that strategy, and why the tweaks?

54 ↗

(On Diff #56152)

Is this better than having a simple offset? I'm unclear on what this complexity is trying to accomplish.

77 ↗

(On Diff #56152)

ShadowMapping

86 ↗

(On Diff #56152)

An array of regions would be better than a bunch of constants.

90 ↗

(On Diff #56152)

Scale
Offset
(We should just mention it's "shadow"-related on the type and be done with it)

91 ↗

(On Diff #56152)

init(uptr ShadowScale)

92 ↗

(On Diff #56152)

OffsetArray

105 ↗

(On Diff #56152)

I would just call it Mapping, unless it could be confused with anything, in which case the current name is ok.

157 ↗

(On Diff #56152)

Should we #ifndef NDEBUG, to make sure it's only there in debug versions?

[aizatsky]

lib/esan/esan.cpp

66 ↗

(On Diff #56152)

Looks like mapping won't be initialized for other tools.

lib/esan/esan_interceptors.cpp

425 ↗

(On Diff #56152)

theoretically addr & addr + sz - 1 could be in app memory, but in different regions. Do we worry about such scenario?

lib/esan/esan_shadow.h

39 ↗

(On Diff #56152)

Any reference? Paper/source code/github project.

47 ↗

(On Diff #56152)

Mask choice surprises me. Why 3 f's?

51 ↗

(On Diff #56152)

Why can't we use the same shadow offset for all scales? You'll need 2 loads now to calculate shadow address. Why not:

(app & mask) >> scale + offs?

[bruening]

The OS-related stuff like fix_mmap_addr should be in a esan_posix.cc file, which can include external headers (like the ones in asan do).
That way you don't need to hard-code values or anything, you just include the required headers.

Making it #if LINUX should be sufficient. This matches what tsan does.

Can you explain a bit better why there's so much complexity around the mapping? I have some inline comments about it.

Please see the commit message and esan_shadow.h comments: this supports multiple scales, as different tools need different shadow configurations. I would argue that it is not much more complex than other mappings: it simply varies the offset for the different scales.

lib/esan/esan.cpp

66 ↗

(On Diff #56152)

Other tools need to set their own mapping, but I think your point is that it's too easy to accidentally be uninitialized, so I will add an else case here.

72 ↗

(On Diff #56152)

ASan also has multiple shadow regions. Any direct-map shadow approach has to use different shadow regions for the different 64-bit app regions. Our shadow mapping supports both larger and smaller scales than ASan (please see the commit message and the esan_shadow.h comments).

74 ↗

(On Diff #56152)

The mapping expression does not work for the excluded endpoint.

75 ↗

(On Diff #56152)

Address ranges are pretty much always open-ended. It looks a little cluttered with the brackets there next to the parentheses for the size.

lib/esan/esan_interceptors.cpp

425 ↗

(On Diff #56152)

That would be a pretty big mmap. Tsan does not check for it. I suppose it's not hard to check.

lib/esan/esan_shadow.h

47 ↗

(On Diff #56152)

To distinguish PIE, lib/stack, and low app addresses, which differ by that 1st nibble of the mask.

50 ↗

(On Diff #56152)

That is the entirety of it, to shift the offs by the scale, but it does not work for two of the scales and has to be tweaked to avoid failing the double-shadow test.

51 ↗

(On Diff #56152)

It fails the double-shadow test for scales 1 and 2.

There are not two loads at execution time for the fastpath in the compiler instrumentation.

77 ↗

(On Diff #56152)

That's the var name.

86 ↗

(On Diff #56152)

See the comment above.

90 ↗

(On Diff #56152)

The other constants here have App in them, this distinguishes.

157 ↗

(On Diff #56152)

Really it's more that it's assumed to not be on a critical path.

[bruening]

Addresses reviewer comments + better separates the vsyscall shadow

Addresses the reviewer comments.

Adds better handling of the vsyscall vs library shadow overlap.

[filcab]

Making it #if LINUX should be sufficient. This matches what tsan does.

It's still very Linux-specific, and we don't need to over-specialize the sanitizer when stopping at POSIX is more than enough.
TSan does this and look at the mess of #if it has for things that are called only once. Especially bad since many of them are not performance-critical (e.g: SIG* definitions), and we end up making a mess, but gaining next to nothing.

Sometimes we end up with #if SANITIZER_LINUX (or another OS) inside a function because it's performance-sensitive, or extracting all the information needed for the Linux-specific code would be a big refactoring and not worth it. This is not one of those cases.

... it is not much more complex than other mappings: it simply varies the offset...

That is more complex, though. Both me and Mike asked about this, so it seems like a better explanation would be nice.
I am not seeing a reason for the different offsets. I understand it's all a simple transformation to get each offset, but the "why" still eludes me (can't talk for Mike, though).

lib/esan/esan.cpp

72 ↗

(On Diff #56237)

Not really. ASan has one special case where there's more than a shadow region.
All the others have one shadow region (divided into low shadow, high shadow, and shadow gap).

You mention that "Any direct-map shadow approach has to use different shadow regions for the different 64-bit app regions", what's missing is the "why?".

I might be missing something, but like I said, I don't see a reason to have all this complexity.
Having a single, big, shadow region would also help with not needing to mask addresses in the memToShadow transformation. This also avoids having problems in the appToShadow(appToShadow(x)) transformation, as that hits the shadow gap, which has no read nor write permissions.

74 ↗

(On Diff #56237)

Right, you have white-listed some app memory, and we end up with appToShadow(AppEnd) not falling into shadow memory because there are blanks in the address space that aren't "app" nor "shadow", is that so?

lib/esan/esan_interceptors.cpp

427 ↗

(On Diff #56237)

fixMmapAddr

438 ↗

(On Diff #56237)

[%p, %p)

lib/esan/esan_shadow.h

18 ↗

(On Diff #56237)

`#include <sanitizer_common/sanitizer_platform.h>
#if SANITIZER_WORDSIZE !=64
#error ...
`

24 ↗

(On Diff #56237)

#if SANITIZER_LINUX

25 ↗

(On Diff #56237)

Linux. We've already seen differences in mapping for Linux and FreeBSD, so I wouldn't lump them together unless an actual port is in the way and the same mapping works.

48 ↗

(On Diff #56237)

Nothing in this patch mentions "why" supporting different offsets is a priority. Is it not possible to do just the one offset (with possibly varying scales) on Linux due to virtual address space fragmentation?
Are there performance concerns which we can address when we scale down the shadow, but can't when the shadow is very large?

I really want to avoid this code being more complex than it needs to. Especially since it will likely change among different OS.

78 ↗

(On Diff #56237)

Mapping is more ambiguous, and it's a top-level (in ESan) name.
ShadowMapping is explicitly for a shadow memory mapping. We only have the one class and is easily reachable everywhere in ESan. It should be more explicit.

[bruening]

That is more complex, though. Both me and Mike asked about this, so it seems like a better explanation would be nice.

I think you are overlooking the very similar complexities in the other sanitizers. ASan has to use a different offset to handle PIE versus the offset it uses for non-PIE, which is a complexity I do not want. Each of the other sanitizers has its own, different, set of offsets. Our mapping handles PIE and vsyscall and handles multiple scales to support multiple tools, all with one formula with two instances of tweaked offset.

I am not seeing a reason for the different offsets. I understand it's all a simple transformation to get each offset, but the "why" still eludes me (can't talk for Mike, though).

This is explained in esan_shadow.h: for two scale cases, the base offset produces a shadow(shadow) conflict. Tweaking it satisfies the shadow(shadow) property, helping to avoid wild accesses by the app clobbering a tool's own metadata. It makes the tools more robust.

lib/esan/esan.cpp

72 ↗

(On Diff #56237)

Low shadow and high shadow are two different regions. There is not a third region for PIE in that same scheme because ASan has to use a different offset when PIE is present, resulting in a completely different mapping. There is as much complexity there as in our mapping here, yet ours handles multiples scales and it handles PIE and the vsyscall page.

Look at the application memory ranges: they are distinct and far apart. Using a linear mapping that preserves their identities places them into distinct shadow ranges.

74 ↗

(On Diff #56237)

Anything outside of the listed regions is disallowed.

lib/esan/esan_shadow.h

48 ↗

(On Diff #56237)

Please read the full comment. This is explained. Pasting:

56              // For other scales, the
57		​// offset is shifted left by the scale, except for scales of 1 and 2 where
58		​// it must be tweaked in order to pass the double-shadow test
59		​// (see the "shadow(shadow)" comments below):"

No, it is not possible to use one offset.

Again, there is as much complexity in the other sanitizer shadow mappings. They have special offsets as well, and they all have to be tweaked on different platforms.

If you can come up with a linear mapping involving a scale and an add that uses a single offset for every scale and avoids colliding with anything (including shadow(shadow)), please let me know.

[bruening]

Addresses reviewer comments

[bruening]

lib/esan/esan_shadow.h

78 ↗

(On Diff #56237)

I'm seeing requests for s/ShadowMapping/Mapping/ here, but later s/ShadowMapping/Mapping/ for the global variable; similarly, s/ShadowScale/Scale/ for the field, yet later s/Scale/ShadowScale/ for the parameter. The global variable is the one referenced the most externally and it is ShadowMapping. "Mapping" is used throughout the sanitizers: asan_mapping.h, AsanMappingProfile[], ASAN_FIXED_MAPPING, tsan's struct Mapping, enum MappingType.

[filcab]

Can you hide some more complexity of the Mapping?
This almost looks like it will have to be fully rewritten for any port (with all the different App spaces, etc, which will very likely not map to other OS).
isAppMem, isShadowMem, and other functions should be more general than they are here.

lib/esan/esan_shadow.h

79 ↗

(On Diff #56293)

The rationale was that the type *should* already explicitly state that it was shadow related. Added to that, the struct members, since it's a struct used to describe a shadow mapping, shouldn't have "shadow" in their name, since that struct is "all about shadow memory". A bit like llvm's struct ShadowMapping, in AddressSanitizer.cpp. The ones where I asked to add shadow (other than the class name) were simply a way to avoid clashes in names.
AsanMappingProfile is a recent addition and it ends up being the profile for asan_mapping.h, so it makes sense to me to "keep" the file name, transformed to a proper variable name.

But this is only bike-shedding on names, so if you feel strongly, I won't push back on this any more. Except for the initMapping method in the Mapping class. No sense repeating Mapping all the time.

87 ↗

(On Diff #56293)

Has this been measured?
We'll get huge 64-bit mov instructions vs a few loads with high locality.
I would prefer readibility over "potential performance" unless this has been shown to have a good performance impact.

[bruening]

Rewrite to use an array

[aizatsky]

lib/esan/esan_shadow.h

79 ↗

(On Diff #56447)

The protection from this kind of wild access adds significant complexity to the mapping scheme. Is it really important for esan?

I can imagine this being important for asan, even though it seems to ignore this issue atm. Do we really need this complexity?

[bruening]

lib/esan/esan_shadow.h

79 ↗

(On Diff #56447)

IMHO this is not adding much complexity: the offset for two of the scale values is tweaked slightly from the formula. It makes the mapping more robust and has no performance cost in the fastpath. This general mapping could potentially be used for other non-efficiency sanitizers in the future. I don't see much value in removing a robustness feature from the mapping.

[filcab]

ASan is not ignoring this issue. ASan's mapping makes any
shadow(shadow(x)) end up in the shadow gap, which is protected against
reading and writing.

Filipe

[bruening]

In D19921#425615, @filcab wrote:

ASan is not ignoring this issue. ASan's mapping makes any
shadow(shadow(x)) end up in the shadow gap, which is protected against
reading and writing.

Yes, and FTR I was the one who pointed this out and had it added to asan back in its early days, as its original shadow mapping did not have this feature.

[bruening]

If there are no other issues I would like to move forward.

[filcab]

LGTM.

compiler-rt/trunk/lib/esan/esan.cpp

 //===-- esan.cpp ----------------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of EfficiencySanitizer, a family of performance tuners.
 //
 // Main file (entry points) for the Esan run-time.
 //===----------------------------------------------------------------------===//
 
 #include "esan.h"
 #include "esan_interface_internal.h"
+#include "esan_shadow.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_flag_parser.h"
 #include "sanitizer_common/sanitizer_flags.h"
 
 // See comment below.
 extern "C" {
 extern void __cxa_atexit(void (*function)(void));
 }
 
 namespace __esan {
 
 bool EsanIsInitialized;
 ToolType WhichTool;
+ShadowMapping Mapping;
 
 static const char EsanOptsEnv[] = "ESAN_OPTIONS";
 
 // We are combining multiple performance tuning tools under the umbrella of
 // one EfficiencySanitizer super-tool.  Most of our tools have very similar
 // memory access instrumentation, shadow memory mapping, libc interception,
 // etc., and there is typically more shared code than distinct code.
 //
void processRangeAccess(uptr PC, uptr Addr, int Size, bool IsWrite) {
   VPrintf(3, "in esan::%s %p: %c %p %d\n", __FUNCTION__, PC,
           IsWrite ? 'w' : 'r', Addr, Size);
   if (WhichTool == ESAN_CacheFrag) {
     // TODO(bruening): add shadow mapping and update shadow bits here.
     // We'll move this to cache_frag.cpp once we have something.
   }
 }
 
+#if SANITIZER_DEBUG
+static bool verifyShadowScheme() {
+  // Sanity checks for our shadow mapping scheme.
+  for (int Scale = 0; Scale < 8; ++Scale) {
+    Mapping.initialize(Scale);
+    uptr AppStart, AppEnd;
+    for (int i = 0; getAppRegion(i, &AppStart, &AppEnd); ++i) {
+      DCHECK(isAppMem(AppStart));
+      DCHECK(!isAppMem(AppStart - 1));
+      DCHECK(isAppMem(AppEnd - 1));
+      DCHECK(!isAppMem(AppEnd));
+      DCHECK(!isShadowMem(AppStart));
+      DCHECK(!isShadowMem(AppEnd - 1));
+      DCHECK(isShadowMem(appToShadow(AppStart)));
+      DCHECK(isShadowMem(appToShadow(AppEnd - 1)));
+      // Double-shadow checks.
+      DCHECK(!isShadowMem(appToShadow(appToShadow(AppStart))));
+      DCHECK(!isShadowMem(appToShadow(appToShadow(AppEnd - 1))));
+    }
+    // Ensure no shadow regions overlap each other.
+    uptr ShadowAStart, ShadowBStart, ShadowAEnd, ShadowBEnd;
+    for (int i = 0; getShadowRegion(i, &ShadowAStart, &ShadowAEnd); ++i) {
+      for (int j = 0; getShadowRegion(j, &ShadowBStart, &ShadowBEnd); ++j) {
+        DCHECK(i == j || ShadowAStart >= ShadowBEnd ||
+               ShadowAEnd <= ShadowBStart);
+      }
+    }
+  }
+  return true;
+}
+#endif
+
+static void initializeShadow() {
+  DCHECK(verifyShadowScheme());
+
+  if (WhichTool == ESAN_CacheFrag)
+    Mapping.initialize(2); // 4B:1B, so 4 to 1 == >>2.
+  else
+    UNREACHABLE("unknown tool shadow mapping");
+
+  VPrintf(1, "Shadow scale=%d offset=%p\n", Mapping.Scale, Mapping.Offset);
+
+  uptr ShadowStart, ShadowEnd;
+  for (int i = 0; getShadowRegion(i, &ShadowStart, &ShadowEnd); ++i) {
+    VPrintf(1, "Shadow #%d: [%zx-%zx) (%zuGB)\n", i, ShadowStart, ShadowEnd,
+            (ShadowEnd - ShadowStart) >> 30);
+
+    uptr Map = (uptr)MmapFixedNoReserve(ShadowStart, ShadowEnd - ShadowStart,
+                                        "shadow");
+    if (Map != ShadowStart) {
+      Printf("FATAL: EfficiencySanitizer failed to map its shadow memory.\n");
+      Die();
+    }
+
+    if (common_flags()->no_huge_pages_for_shadow)
+      NoHugePagesInRegion(ShadowStart, ShadowEnd - ShadowStart);
+    if (common_flags()->use_madv_dontdump)
+      DontDumpShadowMemory(ShadowStart, ShadowEnd - ShadowStart);
+
+    // TODO: Call MmapNoAccess() on in-between regions.
+  }
+}
+
 static void initializeFlags() {
   // Once we add our own flags we'll parse them here.
   // For now the common ones are sufficient.
   FlagParser Parser;
   SetCommonFlagsDefaults();
   RegisterCommonFlags(&Parser);
   Parser.ParseString(GetEnv(EsanOptsEnv));
   InitializeCommonFlags();
void initializeLibrary(ToolType Tool) {
   ::__cxa_atexit((void (*)())finalizeLibrary);
 
   VPrintf(1, "in esan::%s\n", __FUNCTION__);
   if (WhichTool != ESAN_CacheFrag) {
     Printf("ERROR: unknown tool %d requested\n", WhichTool);
     Die();
   }
 
+  initializeShadow();
   initializeInterceptors();
 
   EsanIsInitialized = true;
 }
 
 int finalizeLibrary() {
   VPrintf(1, "in esan::%s\n", __FUNCTION__);
   if (WhichTool == ESAN_CacheFrag) {

compiler-rt/trunk/lib/esan/esan_interceptors.cpp

 //===-- esan_interceptors.cpp ---------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of EfficiencySanitizer, a family of performance tuners.
 //
 // Interception routines for the esan run-time.
 //===----------------------------------------------------------------------===//
 
 #include "esan.h"
+#include "esan_shadow.h"
 #include "interception/interception.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_stacktrace.h"
 
 using namespace __esan; // NOLINT
 
+// FIXME: if this gets more complex as more platforms are added we may
+// want to split pieces into separate platform-specific files.
+#if SANITIZER_LINUX
+// Sanitizer runtimes in general want to avoid including system headers.
+// We define the few constants we need here:
+const int EINVAL = 22; // from /usr/include/asm-generic/errno-base.h
+const int MAP_FIXED = 0x10; // from /usr/include/sys/mman.h
+extern "C" int *__errno_location();
+#define errno (*__errno_location())
+#else
+#error Other platforms are not yet supported.
+#endif
+
 #define CUR_PC() (StackTrace::GetCurrentPc())
 
 //===----------------------------------------------------------------------===//
 // Interception via sanitizer common interceptors
 //===----------------------------------------------------------------------===//
 
 // Get the per-platform defines for what is possible to intercept
 #include "sanitizer_common/sanitizer_platform_interceptors.h"

 
 INTERCEPTOR(int, rmdir, char *path) {
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, rmdir, path);
   COMMON_INTERCEPTOR_READ_STRING(ctx, path, 0);
   return REAL(rmdir)(path);
 }
 
+//===----------------------------------------------------------------------===//
+// Shadow-related interceptors
+//===----------------------------------------------------------------------===//
+
+// These are candidates for sharing with all sanitizers if shadow memory
+// support is also standardized.
+
+static bool fixMmapAddr(void **addr, SIZE_T sz, int flags) {
+  if (*addr) {
+    uptr AppStart, AppEnd;
+    bool SingleApp = false;
+    for (int i = 0; getAppRegion(i, &AppStart, &AppEnd); ++i) {
+      if ((uptr)*addr >= AppStart && (uptr)*addr + sz - 1 <= AppEnd) {
+        SingleApp = true;
+        break;
+      }
+    }
+    if (!SingleApp) {
+      VPrintf(1, "mmap conflict: [%p-%p) is not in an app region\n",
+              *addr, (uptr)*addr + sz);
+      if (flags & MAP_FIXED) {
+        errno = EINVAL;
+        return false;
+      } else {
+        *addr = 0;
+      }
+    }
+  }
+  return true;
+}
+
+INTERCEPTOR(void *, mmap, void *addr, SIZE_T sz, int prot, int flags,
+                 int fd, OFF_T off) {
+  if (!fixMmapAddr(&addr, sz, flags))
+    return (void *)-1;
+  return REAL(mmap)(addr, sz, prot, flags, fd, off);
+}
+
+#if SANITIZER_LINUX
+INTERCEPTOR(void *, mmap64, void *addr, SIZE_T sz, int prot, int flags,
+                 int fd, OFF64_T off) {
+  if (!fixMmapAddr(&addr, sz, flags))
+    return (void *)-1;
+  return REAL(mmap64)(addr, sz, prot, flags, fd, off);
+}
+#define ESAN_MAYBE_INTERCEPT_MMAP64 INTERCEPT_FUNCTION(mmap64)
+#else
+#define ESAN_MAYBE_INTERCEPT_MMAP64
+#endif
+
 namespace __esan {
 
 void initializeInterceptors() {
   InitializeCommonInterceptors();
 
   INTERCEPT_FUNCTION(strcpy); // NOLINT
   INTERCEPT_FUNCTION(strncpy);
 
   ESAN_MAYBE_INTERCEPT_STAT64;
   ESAN_MAYBE_INTERCEPT___XSTAT64;
   ESAN_INTERCEPT_LSTAT;
   ESAN_MAYBE_INTERCEPT_LSTAT64;
   ESAN_MAYBE_INTERCEPT___LXSTAT64;
   INTERCEPT_FUNCTION(open);
   ESAN_MAYBE_INTERCEPT_OPEN64;
   INTERCEPT_FUNCTION(creat);
   ESAN_MAYBE_INTERCEPT_CREAT64;
   INTERCEPT_FUNCTION(unlink);
   INTERCEPT_FUNCTION(fread);
   INTERCEPT_FUNCTION(fwrite);
   INTERCEPT_FUNCTION(puts);
   INTERCEPT_FUNCTION(rmdir);
 
+  INTERCEPT_FUNCTION(mmap);
+  ESAN_MAYBE_INTERCEPT_MMAP64;
+
   // TODO(bruening): we should intercept calloc() and other memory allocation
   // routines that zero memory and update our shadow memory appropriately.
 
   // TODO(bruening): intercept routines that other sanitizers intercept that
   // are not in the common pool or here yet, ideally by adding to the common
   // pool.  Examples include wcslen and bcopy.
 
   // TODO(bruening): there are many more libc routines that read or write data
   // structures that no sanitizer is intercepting: sigaction, strtol, etc.
 }
 
 } // namespace __esan

compiler-rt/trunk/lib/esan/esan_shadow.h

+//===-- esan_shadow.h -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of EfficiencySanitizer, a family of performance tuners.
+//
+// Shadow memory mappings for the esan run-time.
+//===----------------------------------------------------------------------===//
+
+#ifndef ESAN_SHADOW_H
+#define ESAN_SHADOW_H
+
+#include <sanitizer_common/sanitizer_platform.h>
+
+#if SANITIZER_WORDSIZE != 64
+#error Only 64-bit is supported
+#endif
+
+namespace __esan {
+
+#if SANITIZER_LINUX && defined(__x86_64__)
+// Linux x86_64
+//
+// Application memory falls into these 5 regions (ignoring the corner case
+// of PIE with a non-zero PT_LOAD base):
+//
+// [0x00000000'00000000, 0x00000100'00000000) non-PIE + heap
+// [0x00005500'00000000, 0x00005700'00000000) PIE
+// [0x00007f00'00000000, 0x00007fff'ff600000) libraries + stack, part 1
+// [0x00007fff'ff601000, 0x00008000'00000000) libraries + stack, part 2
+// [0xffffffff'ff600000, 0xffffffff'ff601000) vsyscall
+//
+// Although we can ignore the vsyscall for the most part as there are few data
+// references there (other sanitizers ignore it), we enforce a gap inside the
+// library region to distinguish the vsyscall's shadow, considering this gap to
+// be an invalid app region.
+//
+// We disallow application memory outside of those 5 regions.
+//
+// Our shadow memory is scaled from a 1:1 mapping and supports a scale
+// specified at library initialization time that can be any power-of-2
+// scaledown (1x, 2x, 4x, 8x, 16x, etc.).
+//
+// We model our shadow memory after Umbra, a library used by the Dr. Memory
+// tool: https://github.com/DynamoRIO/drmemory/blob/master/umbra/umbra_x64.c.
+// We use Umbra's scheme as it was designed to support different
+// offsets, it supports two different shadow mappings (which we may want to
+// use for future tools), and it ensures that the shadow of a shadow will
+// not overlap either shadow memory or application memory.
+//
+// This formula translates from application memory to shadow memory:
+//
+//   shadow(app) = ((app & 0x00000fff'ffffffff) + offset) >> scale
+//
+// Where the offset for 1:1 is 0x00001200'00000000.  For other scales, the
+// offset is shifted left by the scale, except for scales of 1 and 2 where
+// it must be tweaked in order to pass the double-shadow test
+// (see the "shadow(shadow)" comments below):
+//   scale == 0: 0x0000120'000000000
+//   scale == 1: 0x0000220'000000000
+//   scale == 2: 0x0000440'000000000
+//   scale >= 3: (0x0000120'000000000 << scale)
+//
+// Do not pass in the open-ended end value to the formula as it will fail.
+//
+// The resulting shadow memory regions for a 0 scaling are:
+//
+// [0x00001200'00000000, 0x00001300'00000000)
+// [0x00001700'00000000, 0x00001900'00000000)
+// [0x00002100'00000000, 0x000021ff'ff600000)
+// [0x000021ff'ff601000, 0x00002200'00000000)
+// [0x000021ff'ff600000, 0x000021ff'ff601000]
+//
+// We also want to ensure that a wild access by the application into the shadow
+// regions will not corrupt our own shadow memory.  shadow(shadow) ends up
+// disjoint from shadow(app):
+//
+// [0x00001400'00000000, 0x00001500'00000000)
+// [0x00001900'00000000, 0x00001b00'00000000)
+// [0x00001300'00000000, 0x000013ff'ff600000]
+// [0x000013ff'ff601000, 0x00001400'00000000]
+// [0x000013ff'ff600000, 0x000013ff'ff601000]
+
+struct ApplicationRegion {
+  uptr Start;
+  uptr End;
+  bool ShadowMergedWithPrev;
+};
+
+static const struct ApplicationRegion AppRegions[] = {
+  {0x0000000000000000ull, 0x0000010000000000u, false},
+  {0x0000550000000000u,   0x0000570000000000u, false},
+  // We make one shadow mapping to hold the shadow regions for all 3 of these
+  // app regions, as the mappings interleave, and the gap between the 3rd and
+  // 4th scales down below a page.
+  {0x00007f0000000000u,   0x00007fffff600000u, false},
+  {0x00007fffff601000u,   0x0000800000000000u, true},
+  {0xffffffffff600000u,   0xffffffffff601000u, true},
+};
+static const u32 NumAppRegions = sizeof(AppRegions)/sizeof(AppRegions[0]);
+
+class ShadowMapping {
+public:
+  static const uptr Mask = 0x00000fffffffffffu;
+  // The scale and offset vary by tool.
+  uptr Scale;
+  uptr Offset;
+  void initialize(uptr ShadowScale) {
+    static const uptr OffsetArray[3] = {
+        0x0000120000000000u,
+        0x0000220000000000u,
+        0x0000440000000000u,
+    };
+    Scale = ShadowScale;
+    if (Scale <= 2)
+      Offset = OffsetArray[Scale];
+    else
+      Offset = OffsetArray[0] << Scale;
+  }
+};
+extern ShadowMapping Mapping;
+#else
+// We'll want to use templatized functions over the ShadowMapping once
+// we support more platforms.
+#error Platform not supported
+#endif
+
+static inline bool getAppRegion(u32 i, uptr *Start, uptr *End) {
+  if (i >= NumAppRegions)
+    return false;
+  *Start = AppRegions[i].Start;
+  *End = AppRegions[i].End;
+  return true;
+}
+
+ALWAYS_INLINE
+bool isAppMem(uptr Mem) {
+  for (u32 i = 0; i < NumAppRegions; ++i) {
+    if (Mem >= AppRegions[i].Start && Mem < AppRegions[i].End)
+      return true;
+  }
+  return false;
+}
+
+ALWAYS_INLINE
+uptr appToShadow(uptr App) {
+  DCHECK(isAppMem(App));
+  return (((App & ShadowMapping::Mask) + Mapping.Offset) >> Mapping.Scale);
+}
+
+static inline bool getShadowRegion(u32 i, uptr *Start, uptr *End) {
+  if (i >= NumAppRegions)
+    return false;
+  u32 UnmergedShadowCount = 0;
+  u32 AppIdx;
+  for (AppIdx = 0; AppIdx < NumAppRegions; ++AppIdx) {
+    if (!AppRegions[AppIdx].ShadowMergedWithPrev) {
+      if (UnmergedShadowCount == i)
+        break;
+      UnmergedShadowCount++;
+    }
+  }
+  if (AppIdx >= NumAppRegions || UnmergedShadowCount != i)
+    return false;
+  *Start = appToShadow(AppRegions[AppIdx].Start);
+  // The formula fails for the end itself.
+  *End = appToShadow(AppRegions[AppIdx].End - 1) + 1;
+  // Merge with adjacent shadow regions:
+  for (++AppIdx; AppIdx < NumAppRegions; ++AppIdx) {
+    if (!AppRegions[AppIdx].ShadowMergedWithPrev)
+      break;
+    *Start = Min(*Start, appToShadow(AppRegions[AppIdx].Start));
+    *End = Max(*End, appToShadow(AppRegions[AppIdx].End - 1) + 1);
+  }
+  return true;
+}
+
+ALWAYS_INLINE
+bool isShadowMem(uptr Mem) {
+  // We assume this is not used on any critical performance path and so there's
+  // no need to hardcode the mapping results.
+  for (uptr i = 0; i < NumAppRegions; ++i) {
+    if (Mem >= appToShadow(AppRegions[i].Start) &&
+        Mem < appToShadow(AppRegions[i].End))
+      return true;
+  }
+  return false;
+}
+
+} // namespace __esan
+
+#endif /* ESAN_SHADOW_H */

compiler-rt/trunk/test/esan/TestCases/mmap-shadow-conflict.c

+// RUN: %clang_esan_frag -O0 %s -o %t 2>&1
+// RUN: %env_esan_opts=verbosity=1 %run %t 2>&1 | FileCheck %s
+
+#include <unistd.h>
+#include <sys/mman.h>
+#include <stdio.h>
+
+int main(int argc, char **argv) {
+  void *Map = mmap((void *)0x0000016000000000ULL, 0x1000, PROT_READ,
+                   MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
+  if (Map == (void *)-1)
+    fprintf(stderr, "map failed\n");
+  else
+    fprintf(stderr, "mapped %p\n", Map);
+  Map = mmap((void *)0x0000016000000000ULL, 0x1000, PROT_READ,
+                   MAP_ANON|MAP_PRIVATE, -1, 0);
+  fprintf(stderr, "mapped %p\n", Map);
+  // CHECK:      in esan::initializeLibrary
+  // CHECK-NEXT: Shadow scale=2 offset=0x440000000000
+  // CHECK-NEXT: Shadow #0: [110000000000-114000000000) (256GB)
+  // CHECK-NEXT: Shadow #1: [124000000000-12c000000000) (512GB)
+  // CHECK-NEXT: Shadow #2: [14c000000000-150000000000) (256GB)
+  // CHECK-NEXT: mmap conflict: {{.*}}
+  // CHECK-NEXT: map failed
+  // CHECK-NEXT: mmap conflict: {{.*}}
+  // CHECK-NEXT: mapped {{.*}}
+  // CHECK-NEXT: in esan::finalizeLibrary
+  return 0;
+}

compiler-rt/trunk/test/esan/TestCases/verbose-simple.c

 // RUN: %clang_esan_frag -O0 %s -o %t 2>&1
 // RUN: %env_esan_opts=verbosity=1 %run %t 2>&1 | FileCheck %s
 
 int main(int argc, char **argv) {
   // CHECK:      in esan::initializeLibrary
+  // CHECK-NEXT: Shadow scale=2 offset=0x440000000000
+  // CHECK-NEXT: Shadow #0: [110000000000-114000000000) (256GB)
+  // CHECK-NEXT: Shadow #1: [124000000000-12c000000000) (512GB)
+  // CHECK-NEXT: Shadow #2: [14c000000000-150000000000) (256GB)
   // CHECK-NEXT: in esan::finalizeLibrary
   // CHECK-NEXT: {{.*}}EfficiencySanitizer is not finished: nothing yet to report
   return 0;
 }