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;
initialize(uptr ShadowScale)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
getAppRegion(u32 i,uptr * Start,uptr * End)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
isAppMem(uptr Mem)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
appToShadow(uptr App)158 uptr appToShadow(uptr App) {
159 return (((App & ShadowMapping::Mask) + Mapping.Offset) >> Mapping.Scale);
160 }
161
getShadowRegion(u32 i,uptr * Start,uptr * End)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
isShadowMem(uptr Mem)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 */
204