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

   1 //===-- esan_shadow.h -------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is a part of EfficiencySanitizer, a family of performance tuners.
  11 //
  12 // Shadow memory mappings for the esan run-time.
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef ESAN_SHADOW_H
  16 #define ESAN_SHADOW_H
  17
  18 #include <sanitizer_common/sanitizer_platform.h>
  19
  20 #if SANITIZER_WORDSIZE != 64
  21 #error Only 64-bit is supported
  22 #endif
  23
  24 namespace __esan {
  25
  26 #if SANITIZER_LINUX && defined(__x86_64__)
  27 // Linux x86_64
  28 //
  29 // Application memory falls into these 5 regions (ignoring the corner case
  30 // of PIE with a non-zero PT_LOAD base):
  31 //
  32 // [0x00000000'00000000, 0x00000100'00000000) non-PIE + heap
  33 // [0x00005500'00000000, 0x00005700'00000000) PIE
  34 // [0x00007e00'00000000, 0x00007fff'ff600000) libraries + stack, part 1
  35 // [0x00007fff'ff601000, 0x00008000'00000000) libraries + stack, part 2
  36 // [0xffffffff'ff600000, 0xffffffff'ff601000) vsyscall
  37 //
  38 // Although we can ignore the vsyscall for the most part as there are few data
  39 // references there (other sanitizers ignore it), we enforce a gap inside the
  40 // library region to distinguish the vsyscall's shadow, considering this gap to
  41 // be an invalid app region.
  42 // We disallow application memory outside of those 5 regions.
  43 // Our regions assume that the stack rlimit is less than a terabyte (otherwise
  44 // the Linux kernel's default mmap region drops below 0x7e00'), which we enforce
  45 // at init time (we can support larger and unlimited sizes for shadow
  46 // scaledowns, but it is difficult for 1:1 mappings).
  47 //
  48 // Our shadow memory is scaled from a 1:1 mapping and supports a scale
  49 // specified at library initialization time that can be any power-of-2
  50 // scaledown (1x, 2x, 4x, 8x, 16x, etc.).
  51 //
  52 // We model our shadow memory after Umbra, a library used by the Dr. Memory
  53 // tool: https://github.com/DynamoRIO/drmemory/blob/master/umbra/umbra_x64.c.
  54 // We use Umbra's scheme as it was designed to support different
  55 // offsets, it supports two different shadow mappings (which we may want to
  56 // use for future tools), and it ensures that the shadow of a shadow will
  57 // not overlap either shadow memory or application memory.
  58 //
  59 // This formula translates from application memory to shadow memory:
  60 //
  61 //   shadow(app) = ((app & 0x00000fff'ffffffff) + offset) >> scale
  62 //
  63 // Where the offset for 1:1 is 0x00001300'00000000.  For other scales, the
  64 // offset is shifted left by the scale, except for scales of 1 and 2 where
  65 // it must be tweaked in order to pass the double-shadow test
  66 // (see the "shadow(shadow)" comments below):
  67 //   scale == 0: 0x00001300'000000000
  68 //   scale == 1: 0x00002200'000000000
  69 //   scale == 2: 0x00004400'000000000
  70 //   scale >= 3: (0x00001300'000000000 << scale)
  71 //
  72 // Do not pass in the open-ended end value to the formula as it will fail.
  73 //
  74 // The resulting shadow memory regions for a 0 scaling are:
  75 //
  76 // [0x00001300'00000000, 0x00001400'00000000)
  77 // [0x00001800'00000000, 0x00001a00'00000000)
  78 // [0x00002100'00000000, 0x000022ff'ff600000)
  79 // [0x000022ff'ff601000, 0x00002300'00000000)
  80 // [0x000022ff'ff600000, 0x000022ff'ff601000]
  81 //
  82 // We also want to ensure that a wild access by the application into the shadow
  83 // regions will not corrupt our own shadow memory.  shadow(shadow) ends up
  84 // disjoint from shadow(app):
  85 //
  86 // [0x00001600'00000000, 0x00001700'00000000)
  87 // [0x00001b00'00000000, 0x00001d00'00000000)
  88 // [0x00001400'00000000, 0x000015ff'ff600000]
  89 // [0x000015ff'ff601000, 0x00001600'00000000]
  90 // [0x000015ff'ff600000, 0x000015ff'ff601000]
  91
  92 struct ApplicationRegion {
  93   uptr Start;
  94   uptr End;
  95   bool ShadowMergedWithPrev;
  96 };
  97
  98 static const struct ApplicationRegion AppRegions[] = {
  99   {0x0000000000000000ull, 0x0000010000000000u, false},
 100   {0x0000550000000000u,   0x0000570000000000u, false},
 101   // We make one shadow mapping to hold the shadow regions for all 3 of these
 102   // app regions, as the mappings interleave, and the gap between the 3rd and
 103   // 4th scales down below a page.
 104   {0x00007e0000000000u,   0x00007fffff600000u, false},
 105   {0x00007fffff601000u,   0x0000800000000000u, true},
 106   {0xffffffffff600000u,   0xffffffffff601000u, true},
 107 };
 108 static const u32 NumAppRegions = sizeof(AppRegions)/sizeof(AppRegions[0]);
 109
 110 // See the comment above: we do not currently support a stack size rlimit
 111 // equal to or larger than 1TB.
 112 static const uptr MaxStackSize = (1ULL << 40) - 4096;
 113
 114 class ShadowMapping {
 115 public:
 116   static const uptr Mask = 0x00000fffffffffffu;
 117   // The scale and offset vary by tool.
 118   uptr Scale;
 119   uptr Offset;
 120   void initialize(uptr ShadowScale) {
 121     static const uptr OffsetArray[3] = {
 122         0x0000130000000000u,
 123         0x0000220000000000u,
 124         0x0000440000000000u,
 125     };
 126     Scale = ShadowScale;
 127     if (Scale <= 2)
 128       Offset = OffsetArray[Scale];
 129     else
 130       Offset = OffsetArray[0] << Scale;
 131   }
 132 };
 133 extern ShadowMapping Mapping;
 134 #else
 135 // We'll want to use templatized functions over the ShadowMapping once
 136 // we support more platforms.
 137 #error Platform not supported
 138 #endif
 139
 140 static inline bool getAppRegion(u32 i, uptr *Start, uptr *End) {
 141   if (i >= NumAppRegions)
 142     return false;
 143   *Start = AppRegions[i].Start;
 144   *End = AppRegions[i].End;
 145   return true;
 146 }
 147
 148 ALWAYS_INLINE
 149 bool isAppMem(uptr Mem) {
 150   for (u32 i = 0; i < NumAppRegions; ++i) {
 151     if (Mem >= AppRegions[i].Start && Mem < AppRegions[i].End)
 152       return true;
 153   }
 154   return false;
 155 }
 156
 157 ALWAYS_INLINE
 158 uptr appToShadow(uptr App) {
 159   return (((App & ShadowMapping::Mask) + Mapping.Offset) >> Mapping.Scale);
 160 }
 161
 162 static inline bool getShadowRegion(u32 i, uptr *Start, uptr *End) {
 163   if (i >= NumAppRegions)
 164     return false;
 165   u32 UnmergedShadowCount = 0;
 166   u32 AppIdx;
 167   for (AppIdx = 0; AppIdx < NumAppRegions; ++AppIdx) {
 168     if (!AppRegions[AppIdx].ShadowMergedWithPrev) {
 169       if (UnmergedShadowCount == i)
 170         break;
 171       UnmergedShadowCount++;
 172     }
 173   }
 174   if (AppIdx >= NumAppRegions || UnmergedShadowCount != i)
 175     return false;
 176   *Start = appToShadow(AppRegions[AppIdx].Start);
 177   // The formula fails for the end itself.
 178   *End = appToShadow(AppRegions[AppIdx].End - 1) + 1;
 179   // Merge with adjacent shadow regions:
 180   for (++AppIdx; AppIdx < NumAppRegions; ++AppIdx) {
 181     if (!AppRegions[AppIdx].ShadowMergedWithPrev)
 182       break;
 183     *Start = Min(*Start, appToShadow(AppRegions[AppIdx].Start));
 184     *End = Max(*End, appToShadow(AppRegions[AppIdx].End - 1) + 1);
 185   }
 186   return true;
 187 }
 188
 189 ALWAYS_INLINE
 190 bool isShadowMem(uptr Mem) {
 191   // We assume this is not used on any critical performance path and so there's
 192   // no need to hardcode the mapping results.
 193   for (uptr i = 0; i < NumAppRegions; ++i) {
 194     if (Mem >= appToShadow(AppRegions[i].Start) &&
 195         Mem < appToShadow(AppRegions[i].End - 1) + 1)
 196       return true;
 197   }
 198   return false;
 199 }
 200
 201 } // namespace __esan
 202
 203 #endif /* ESAN_SHADOW_H */