Index: lib/esan/esan.cpp =================================================================== --- lib/esan/esan.cpp +++ lib/esan/esan.cpp @@ -14,6 +14,7 @@ #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" @@ -27,6 +28,7 @@ bool EsanIsInitialized; ToolType WhichTool; +Mapping ShadowMapping; static const char EsanOptsEnv[] = "ESAN_OPTIONS"; @@ -59,6 +61,70 @@ } } +#if SANITIZER_DEBUG +static bool verifyShadowScheme() { + // Sanity checks for our shadow mapping scheme. + for (int Scale = 0; Scale < 8; ++Scale) { + ShadowMapping.initMapping(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) + ShadowMapping.initMapping(2); // 4B:1B, so 4 to 1 == >>2. + else + UNREACHABLE("unknown tool shadow mapping"); + + VPrintf(1, "Shadow scale=%d offset=%p\n", ShadowMapping.ShadowScale, + ShadowMapping.ShadowOffset); + + 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. @@ -95,6 +161,7 @@ Die(); } + initializeShadow(); initializeInterceptors(); EsanIsInitialized = true; Index: lib/esan/esan_interceptors.cpp =================================================================== --- lib/esan/esan_interceptors.cpp +++ lib/esan/esan_interceptors.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "esan.h" +#include "esan_shadow.h" #include "interception/interception.h" #include "sanitizer_common/sanitizer_common.h" #include "sanitizer_common/sanitizer_libc.h" @@ -20,6 +21,19 @@ 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()) //===----------------------------------------------------------------------===// @@ -405,6 +419,56 @@ 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() { @@ -429,6 +493,9 @@ 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. Index: lib/esan/esan_shadow.h =================================================================== --- /dev/null +++ lib/esan/esan_shadow.h @@ -0,0 +1,226 @@ +//===-- 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 + +#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] + +// While an array seems simpler, we'll get faster code with constants +// that need no data load. +class Mapping { +public: + static const uptr App1Start = 0x0000000000000000ull; + static const uptr App1End = 0x0000010000000000u; + static const uptr App2Start = 0x0000550000000000u; + static const uptr App2End = 0x0000570000000000u; + static const uptr App3Start = 0x00007f0000000000u; + static const uptr App3End = 0x00007fffff600000u; + static const uptr App4Start = 0x00007fffff601000u; + static const uptr App4End = 0x0000800000000000u; + static const uptr App5Start = 0xffffffffff600000u; + static const uptr App5End = 0xffffffffff601000u; + static const uptr ShadowMask = 0x00000fffffffffffu; + // The scale and offset vary by tool. + uptr ShadowScale; + uptr ShadowOffset; + void initMapping(uptr Scale) { + static const uptr ShadowOffsetArray[3] = { + 0x0000120000000000u, + 0x0000220000000000u, + 0x0000440000000000u, + }; + ShadowScale = Scale; + if (Scale <= 2) + ShadowOffset = ShadowOffsetArray[Scale]; + else + ShadowOffset = ShadowOffsetArray[0] << ShadowScale; + } +}; +extern Mapping ShadowMapping; +#else +// We'll want to use templatized functions over the Mapping once +// we support more platforms. +#error Platform not supported +#endif + +static inline bool getAppRegion(int i, uptr *Start, uptr *End) { + switch (i) { + default: + return false; + case 0: + *Start = Mapping::App1Start; + *End = Mapping::App1End; + return true; + case 1: + *Start = Mapping::App2Start; + *End = Mapping::App2End; + return true; + case 2: + *Start = Mapping::App3Start; + *End = Mapping::App3End; + return true; + case 3: + *Start = Mapping::App4Start; + *End = Mapping::App4End; + return true; + case 4: + *Start = Mapping::App5Start; + *End = Mapping::App5End; + return true; + } +} + +ALWAYS_INLINE +bool isAppMem(uptr Mem) { +#if SANITIZER_LINUX && defined(__x86_64__) + return ( + (/*always true: Mem >= Mapping::App1Start &&*/ Mem < Mapping::App1End) || + (Mem >= Mapping::App2Start && Mem < Mapping::App2End) || + (Mem >= Mapping::App3Start && Mem < Mapping::App3End) || + (Mem >= Mapping::App4Start && Mem < Mapping::App4End) || + (Mem >= Mapping::App5Start && Mem < Mapping::App5End)); +#else +#error Platform not supported +#endif +} + +ALWAYS_INLINE +uptr appToShadow(uptr App) { + DCHECK(IsAppMem(x)); + return (((App & Mapping::ShadowMask) + ShadowMapping.ShadowOffset) >> + ShadowMapping.ShadowScale); +} + +static inline bool getShadowRegion(int i, uptr *Start, uptr *End) { + switch (i) { + default: + return false; + case 0: + *Start = appToShadow(Mapping::App1Start); + *End = appToShadow(Mapping::App1End - 1) + 1; // Formula fails for end itself. + return true; + case 1: + *Start = appToShadow(Mapping::App2Start); + *End = appToShadow(Mapping::App2End - 1) + 1; // Formula fails for end itself. + return true; + case 2: + // We make one shadow mapping to hold the shadow regions for App3, App4, and + // App5, as the mappings interleave, and the gap between 3 and 4 scales down + // below a page. + *Start = appToShadow(Mapping::App3Start); + *End = appToShadow(Mapping::App4End - 1) + 1; // Formula fails for end itself. + DCHECK(appToShadow(Mapping::App3End - 1) >= *Start && + appToShadow(Mapping::App3End - 1) < *End && + appToShadow(Mapping::App4Start) >= *Start && + appToShadow(Mapping::App4Start) <= *End && + appToShadow(Mapping::App5Start) >= *Start && + appToShadow(Mapping::App5End - 1) < *End); + 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. +#if SANITIZER_LINUX && defined(__x86_64__) + return ((Mem >= appToShadow(Mapping::App1Start) && + Mem <= appToShadow(Mapping::App1End - 1)) || + (Mem >= appToShadow(Mapping::App2Start) && + Mem <= appToShadow(Mapping::App2End - 1)) || + // App3 and App4 are contiguous so we could do one check. + (Mem >= appToShadow(Mapping::App3Start) && + Mem <= appToShadow(Mapping::App3End - 1)) || + (Mem >= appToShadow(Mapping::App4Start) && + Mem <= appToShadow(Mapping::App4End - 1)) || + (Mem >= appToShadow(Mapping::App5Start) && + Mem <= appToShadow(Mapping::App5End - 1))); +#else +#error Platform not supported +#endif +} + +} // namespace __esan + +#endif /* ESAN_SHADOW_H */ Index: test/esan/TestCases/mmap-shadow-conflict.c =================================================================== --- /dev/null +++ test/esan/TestCases/mmap-shadow-conflict.c @@ -0,0 +1,29 @@ +// RUN: %clang_esan_frag -O0 %s -o %t 2>&1 +// RUN: %env_esan_opts=verbosity=1 %run %t 2>&1 | FileCheck %s + +#include +#include +#include + +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; +} Index: test/esan/TestCases/verbose-simple.c =================================================================== --- test/esan/TestCases/verbose-simple.c +++ test/esan/TestCases/verbose-simple.c @@ -3,6 +3,10 @@ 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;