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 "esan.h"
  19 #include <sanitizer_common/sanitizer_platform.h>
  20
  21 #if SANITIZER_WORDSIZE != 64
  22 #error Only 64-bit is supported
  23 #endif
  24
  25 namespace __esan {
  26
  27 struct ApplicationRegion {
  28   uptr Start;
  29   uptr End;
  30   bool ShadowMergedWithPrev;
  31 };
  32
  33 #if (SANITIZER_LINUX || SANITIZER_FREEBSD) && defined(__x86_64__)
  34 // Linux x86_64
  35 //
  36 // Application memory falls into these 5 regions (ignoring the corner case
  37 // of PIE with a non-zero PT_LOAD base):
  38 //
  39 // [0x00000000'00000000, 0x00000100'00000000) non-PIE + heap
  40 // [0x00005500'00000000, 0x00005700'00000000) PIE
  41 // [0x00007e00'00000000, 0x00007fff'ff600000) libraries + stack, part 1
  42 // [0x00007fff'ff601000, 0x00008000'00000000) libraries + stack, part 2
  43 // [0xffffffff'ff600000, 0xffffffff'ff601000) vsyscall
  44 //
  45 // Although we can ignore the vsyscall for the most part as there are few data
  46 // references there (other sanitizers ignore it), we enforce a gap inside the
  47 // library region to distinguish the vsyscall's shadow, considering this gap to
  48 // be an invalid app region.
  49 // We disallow application memory outside of those 5 regions.
  50 // Our regions assume that the stack rlimit is less than a terabyte (otherwise
  51 // the Linux kernel's default mmap region drops below 0x7e00'), which we enforce
  52 // at init time (we can support larger and unlimited sizes for shadow
  53 // scaledowns, but it is difficult for 1:1 mappings).
  54 //
  55 // Our shadow memory is scaled from a 1:1 mapping and supports a scale
  56 // specified at library initialization time that can be any power-of-2
  57 // scaledown (1x, 2x, 4x, 8x, 16x, etc.).
  58 //
  59 // We model our shadow memory after Umbra, a library used by the Dr. Memory
  60 // tool: https://github.com/DynamoRIO/drmemory/blob/master/umbra/umbra_x64.c.
  61 // We use Umbra's scheme as it was designed to support different
  62 // offsets, it supports two different shadow mappings (which we may want to
  63 // use for future tools), and it ensures that the shadow of a shadow will
  64 // not overlap either shadow memory or application memory.
  65 //
  66 // This formula translates from application memory to shadow memory:
  67 //
  68 //   shadow(app) = ((app & 0x00000fff'ffffffff) + offset) >> scale
  69 //
  70 // Where the offset for 1:1 is 0x00001300'00000000.  For other scales, the
  71 // offset is shifted left by the scale, except for scales of 1 and 2 where
  72 // it must be tweaked in order to pass the double-shadow test
  73 // (see the "shadow(shadow)" comments below):
  74 //   scale == 0: 0x00001300'000000000
  75 //   scale == 1: 0x00002200'000000000
  76 //   scale == 2: 0x00004400'000000000
  77 //   scale >= 3: (0x00001300'000000000 << scale)
  78 //
  79 // Do not pass in the open-ended end value to the formula as it will fail.
  80 //
  81 // The resulting shadow memory regions for a 0 scaling are:
  82 //
  83 // [0x00001300'00000000, 0x00001400'00000000)
  84 // [0x00001800'00000000, 0x00001a00'00000000)
  85 // [0x00002100'00000000, 0x000022ff'ff600000)
  86 // [0x000022ff'ff601000, 0x00002300'00000000)
  87 // [0x000022ff'ff600000, 0x000022ff'ff601000]
  88 //
  89 // We also want to ensure that a wild access by the application into the shadow
  90 // regions will not corrupt our own shadow memory.  shadow(shadow) ends up
  91 // disjoint from shadow(app):
  92 //
  93 // [0x00001600'00000000, 0x00001700'00000000)
  94 // [0x00001b00'00000000, 0x00001d00'00000000)
  95 // [0x00001400'00000000, 0x000015ff'ff600000]
  96 // [0x000015ff'ff601000, 0x00001600'00000000]
  97 // [0x000015ff'ff600000, 0x000015ff'ff601000]
  98
  99 static const struct ApplicationRegion AppRegions[] = {
 100   {0x0000000000000000ull, 0x0000010000000000u, false},
 101   {0x0000550000000000u,   0x0000570000000000u, false},
 102   // We make one shadow mapping to hold the shadow regions for all 3 of these
 103   // app regions, as the mappings interleave, and the gap between the 3rd and
 104   // 4th scales down below a page.
 105   {0x00007e0000000000u,   0x00007fffff600000u, false},
 106   {0x00007fffff601000u,   0x0000800000000000u, true},
 107   {0xffffffffff600000u,   0xffffffffff601000u, true},
 108 };
 109
 110 #elif SANITIZER_LINUX && SANITIZER_MIPS64
 111
 112 // Application memory falls into these 3 regions
 113 //
 114 // [0x00000001'00000000, 0x00000002'00000000) non-PIE + heap
 115 // [0x000000aa'00000000, 0x000000ab'00000000) PIE
 116 // [0x000000ff'00000000, 0x000000ff'ffffffff) libraries + stack
 117 //
 118 // This formula translates from application memory to shadow memory:
 119 //
 120 //   shadow(app) = ((app & 0x00000f'ffffffff) + offset) >> scale
 121 //
 122 // Where the offset for 1:1 is 0x000013'00000000.  For other scales, the
 123 // offset is shifted left by the scale, except for scales of 1 and 2 where
 124 // it must be tweaked in order to pass the double-shadow test
 125 // (see the "shadow(shadow)" comments below):
 126 //   scale == 0: 0x000013'00000000
 127 //   scale == 1: 0x000022'00000000
 128 //   scale == 2: 0x000044'00000000
 129 //   scale >= 3: (0x000013'00000000 << scale)
 130 //
 131 // The resulting shadow memory regions for a 0 scaling are:
 132 //
 133 // [0x00000014'00000000, 0x00000015'00000000)
 134 // [0x0000001d'00000000, 0x0000001e'00000000)
 135 // [0x00000022'00000000, 0x00000022'ffffffff)
 136 //
 137 // We also want to ensure that a wild access by the application into the shadow
 138 // regions will not corrupt our own shadow memory. shadow(shadow) ends up
 139 // disjoint from shadow(app):
 140 //
 141 // [0x00000017'00000000, 0x00000018'00000000)
 142 // [0x00000020'00000000, 0x00000021'00000000)
 143 // [0x00000015'00000000, 0x00000015'ffffffff]
 144
 145 static const struct ApplicationRegion AppRegions[] = {
 146   {0x0100000000u, 0x0200000000u, false},
 147   {0xaa00000000u, 0xab00000000u, false},
 148   {0xff00000000u, 0xffffffffffu, false},
 149 };
 150
 151 #else
 152 #error Platform not supported
 153 #endif
 154
 155 static const u32 NumAppRegions = sizeof(AppRegions)/sizeof(AppRegions[0]);
 156
 157 // See the comment above: we do not currently support a stack size rlimit
 158 // equal to or larger than 1TB.
 159 static const uptr MaxStackSize = (1ULL << 40) - 4096;
 160
 161 class ShadowMapping {
 162 public:
 163
 164   // The scale and offset vary by tool.
 165   uptr Scale;
 166   uptr Offset;
 167
 168   // TODO(sagar.thakur): Try to hardcode the mask as done in the compiler
 169   // instrumentation to reduce the runtime cost of appToShadow.
 170   struct ShadowMemoryMask40 {
 171     static const uptr Mask = 0x0000000fffffffffu;
 172   };
 173
 174   struct ShadowMemoryMask47 {
 175     static const uptr Mask = 0x00000fffffffffffu;
 176   };
 177
 178   void initialize(uptr ShadowScale) {
 179
 180     const uptr OffsetArray40[3] = {
 181       0x0000001300000000u,
 182       0x0000002200000000u,
 183       0x0000004400000000u,
 184     };
 185
 186     const uptr OffsetArray47[3] = {
 187       0x0000130000000000u,
 188       0x0000220000000000u,
 189       0x0000440000000000u,
 190     };
 191
 192     Scale = ShadowScale;
 193     switch (VmaSize) {
 194       case 40: {
 195         if (Scale <= 2)
 196           Offset = OffsetArray40[Scale];
 197         else
 198           Offset = OffsetArray40[0] << Scale;
 199       }
 200       break;
 201       case 47: {
 202         if (Scale <= 2)
 203           Offset = OffsetArray47[Scale];
 204         else
 205           Offset = OffsetArray47[0] << Scale;
 206       }
 207       break;
 208       default: {
 209         Printf("ERROR: %d-bit virtual memory address size not supported\n", VmaSize);
 210         Die();
 211       }
 212     }
 213   }
 214 };
 215 extern ShadowMapping Mapping;
 216
 217 static inline bool getAppRegion(u32 i, uptr *Start, uptr *End) {
 218   if (i >= NumAppRegions)
 219     return false;
 220   *Start = AppRegions[i].Start;
 221   *End = AppRegions[i].End;
 222   return true;
 223 }
 224
 225 ALWAYS_INLINE
 226 bool isAppMem(uptr Mem) {
 227   for (u32 i = 0; i < NumAppRegions; ++i) {
 228     if (Mem >= AppRegions[i].Start && Mem < AppRegions[i].End)
 229       return true;
 230   }
 231   return false;
 232 }
 233
 234 template<typename Params>
 235 uptr appToShadowImpl(uptr App) {
 236   return (((App & Params::Mask) + Mapping.Offset) >> Mapping.Scale);
 237 }
 238
 239 ALWAYS_INLINE
 240 uptr appToShadow(uptr App) {
 241   switch (VmaSize) {
 242     case 40: return appToShadowImpl<ShadowMapping::ShadowMemoryMask40>(App);
 243     case 47: return appToShadowImpl<ShadowMapping::ShadowMemoryMask47>(App);
 244     default: {
 245       Printf("ERROR: %d-bit virtual memory address size not supported\n", VmaSize);
 246       Die();
 247     }
 248   }
 249 }
 250
 251 static inline bool getShadowRegion(u32 i, uptr *Start, uptr *End) {
 252   if (i >= NumAppRegions)
 253     return false;
 254   u32 UnmergedShadowCount = 0;
 255   u32 AppIdx;
 256   for (AppIdx = 0; AppIdx < NumAppRegions; ++AppIdx) {
 257     if (!AppRegions[AppIdx].ShadowMergedWithPrev) {
 258       if (UnmergedShadowCount == i)
 259         break;
 260       UnmergedShadowCount++;
 261     }
 262   }
 263   if (AppIdx >= NumAppRegions || UnmergedShadowCount != i)
 264     return false;
 265   *Start = appToShadow(AppRegions[AppIdx].Start);
 266   // The formula fails for the end itself.
 267   *End = appToShadow(AppRegions[AppIdx].End - 1) + 1;
 268   // Merge with adjacent shadow regions:
 269   for (++AppIdx; AppIdx < NumAppRegions; ++AppIdx) {
 270     if (!AppRegions[AppIdx].ShadowMergedWithPrev)
 271       break;
 272     *Start = Min(*Start, appToShadow(AppRegions[AppIdx].Start));
 273     *End = Max(*End, appToShadow(AppRegions[AppIdx].End - 1) + 1);
 274   }
 275   return true;
 276 }
 277
 278 ALWAYS_INLINE
 279 bool isShadowMem(uptr Mem) {
 280   // We assume this is not used on any critical performance path and so there's
 281   // no need to hardcode the mapping results.
 282   for (uptr i = 0; i < NumAppRegions; ++i) {
 283     if (Mem >= appToShadow(AppRegions[i].Start) &&
 284         Mem < appToShadow(AppRegions[i].End - 1) + 1)
 285       return true;
 286   }
 287   return false;
 288 }
 289
 290 } // namespace __esan
 291
 292 #endif /* ESAN_SHADOW_H */