1 //===-- tsan_shadow_test.cpp ----------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of ThreadSanitizer (TSan), a race detector.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "tsan_platform.h"
13 #include "tsan_rtl.h"
14 #include "gtest/gtest.h"
15
16 namespace __tsan {
17
18 struct Region {
19 uptr start;
20 uptr end;
21 };
22
CheckShadow(const Shadow * s,Sid sid,Epoch epoch,uptr addr,uptr size,AccessType typ)23 void CheckShadow(const Shadow *s, Sid sid, Epoch epoch, uptr addr, uptr size,
24 AccessType typ) {
25 uptr addr1 = 0;
26 uptr size1 = 0;
27 AccessType typ1 = 0;
28 s->GetAccess(&addr1, &size1, &typ1);
29 CHECK_EQ(s->sid(), sid);
30 CHECK_EQ(s->epoch(), epoch);
31 CHECK_EQ(addr1, addr);
32 CHECK_EQ(size1, size);
33 CHECK_EQ(typ1, typ);
34 }
35
TEST(Shadow,Shadow)36 TEST(Shadow, Shadow) {
37 Sid sid = static_cast<Sid>(11);
38 Epoch epoch = static_cast<Epoch>(22);
39 FastState fs;
40 fs.SetSid(sid);
41 fs.SetEpoch(epoch);
42 CHECK_EQ(fs.sid(), sid);
43 CHECK_EQ(fs.epoch(), epoch);
44 CHECK_EQ(fs.GetIgnoreBit(), false);
45 fs.SetIgnoreBit();
46 CHECK_EQ(fs.GetIgnoreBit(), true);
47 fs.ClearIgnoreBit();
48 CHECK_EQ(fs.GetIgnoreBit(), false);
49
50 Shadow s0(fs, 1, 2, kAccessWrite);
51 CheckShadow(&s0, sid, epoch, 1, 2, kAccessWrite);
52 Shadow s1(fs, 2, 3, kAccessRead);
53 CheckShadow(&s1, sid, epoch, 2, 3, kAccessRead);
54 Shadow s2(fs, 0xfffff8 + 4, 1, kAccessWrite | kAccessAtomic);
55 CheckShadow(&s2, sid, epoch, 4, 1, kAccessWrite | kAccessAtomic);
56 Shadow s3(fs, 0xfffff8 + 0, 8, kAccessRead | kAccessAtomic);
57 CheckShadow(&s3, sid, epoch, 0, 8, kAccessRead | kAccessAtomic);
58
59 CHECK(!s0.IsBothReadsOrAtomic(kAccessRead | kAccessAtomic));
60 CHECK(!s1.IsBothReadsOrAtomic(kAccessAtomic));
61 CHECK(!s1.IsBothReadsOrAtomic(kAccessWrite));
62 CHECK(s1.IsBothReadsOrAtomic(kAccessRead));
63 CHECK(s2.IsBothReadsOrAtomic(kAccessAtomic));
64 CHECK(!s2.IsBothReadsOrAtomic(kAccessWrite));
65 CHECK(!s2.IsBothReadsOrAtomic(kAccessRead));
66 CHECK(s3.IsBothReadsOrAtomic(kAccessAtomic));
67 CHECK(!s3.IsBothReadsOrAtomic(kAccessWrite));
68 CHECK(s3.IsBothReadsOrAtomic(kAccessRead));
69
70 CHECK(!s0.IsRWWeakerOrEqual(kAccessRead | kAccessAtomic));
71 CHECK(s1.IsRWWeakerOrEqual(kAccessWrite));
72 CHECK(s1.IsRWWeakerOrEqual(kAccessRead));
73 CHECK(!s1.IsRWWeakerOrEqual(kAccessWrite | kAccessAtomic));
74
75 CHECK(!s2.IsRWWeakerOrEqual(kAccessRead | kAccessAtomic));
76 CHECK(s2.IsRWWeakerOrEqual(kAccessWrite | kAccessAtomic));
77 CHECK(s2.IsRWWeakerOrEqual(kAccessRead));
78 CHECK(s2.IsRWWeakerOrEqual(kAccessWrite));
79
80 CHECK(s3.IsRWWeakerOrEqual(kAccessRead | kAccessAtomic));
81 CHECK(s3.IsRWWeakerOrEqual(kAccessWrite | kAccessAtomic));
82 CHECK(s3.IsRWWeakerOrEqual(kAccessRead));
83 CHECK(s3.IsRWWeakerOrEqual(kAccessWrite));
84
85 Shadow sro(Shadow::kRodata);
86 CheckShadow(&sro, static_cast<Sid>(0), kEpochZero, 0, 0, kAccessRead);
87 }
88
TEST(Shadow,Mapping)89 TEST(Shadow, Mapping) {
90 static int global;
91 int stack;
92 void *heap = malloc(0);
93 free(heap);
94
95 CHECK(IsAppMem((uptr)&global));
96 CHECK(IsAppMem((uptr)&stack));
97 CHECK(IsAppMem((uptr)heap));
98
99 CHECK(IsShadowMem(MemToShadow((uptr)&global)));
100 CHECK(IsShadowMem(MemToShadow((uptr)&stack)));
101 CHECK(IsShadowMem(MemToShadow((uptr)heap)));
102 }
103
TEST(Shadow,Celling)104 TEST(Shadow, Celling) {
105 u64 aligned_data[4];
106 char *data = (char*)aligned_data;
107 CHECK(IsAligned(reinterpret_cast<uptr>(data), kShadowSize));
108 RawShadow *s0 = MemToShadow((uptr)&data[0]);
109 CHECK(IsAligned(reinterpret_cast<uptr>(s0), kShadowSize));
110 for (unsigned i = 1; i < kShadowCell; i++)
111 CHECK_EQ(s0, MemToShadow((uptr)&data[i]));
112 for (unsigned i = kShadowCell; i < 2*kShadowCell; i++)
113 CHECK_EQ(s0 + kShadowCnt, MemToShadow((uptr)&data[i]));
114 for (unsigned i = 2*kShadowCell; i < 3*kShadowCell; i++)
115 CHECK_EQ(s0 + 2 * kShadowCnt, MemToShadow((uptr)&data[i]));
116 }
117
118 // Detect is the Mapping has kBroken field.
119 template <uptr>
120 struct Has {
121 typedef bool Result;
122 };
123
124 template <typename Mapping>
broken(...)125 bool broken(...) {
126 return false;
127 }
128
129 template <typename Mapping>
broken(uptr what,typename Has<Mapping::kBroken>::Result=false)130 bool broken(uptr what, typename Has<Mapping::kBroken>::Result = false) {
131 return Mapping::kBroken & what;
132 }
133
CompareRegion(const void * region_a,const void * region_b)134 static int CompareRegion(const void *region_a, const void *region_b) {
135 uptr start_a = ((const struct Region *)region_a)->start;
136 uptr start_b = ((const struct Region *)region_b)->start;
137
138 if (start_a < start_b) {
139 return -1;
140 } else if (start_a > start_b) {
141 return 1;
142 } else {
143 return 0;
144 }
145 }
146
147 template <typename Mapping>
AddMetaRegion(struct Region * shadows,int * num_regions,uptr start,uptr end)148 static void AddMetaRegion(struct Region *shadows, int *num_regions, uptr start,
149 uptr end) {
150 // If the app region is not empty, add its meta to the array.
151 if (start != end) {
152 shadows[*num_regions].start = (uptr)MemToMetaImpl::Apply<Mapping>(start);
153 shadows[*num_regions].end = (uptr)MemToMetaImpl::Apply<Mapping>(end - 1);
154 *num_regions = (*num_regions) + 1;
155 }
156 }
157
158 struct MappingTest {
159 template <typename Mapping>
Apply__tsan::MappingTest160 static void Apply() {
161 // Easy (but ugly) way to print the mapping name.
162 Printf("%s\n", __PRETTY_FUNCTION__);
163 TestRegion<Mapping>(Mapping::kLoAppMemBeg, Mapping::kLoAppMemEnd);
164 TestRegion<Mapping>(Mapping::kMidAppMemBeg, Mapping::kMidAppMemEnd);
165 TestRegion<Mapping>(Mapping::kHiAppMemBeg, Mapping::kHiAppMemEnd);
166 TestRegion<Mapping>(Mapping::kHeapMemBeg, Mapping::kHeapMemEnd);
167
168 TestDisjointMetas<Mapping>();
169
170 // Not tested: the ordering of regions (low app vs. shadow vs. mid app
171 // etc.). That is enforced at runtime by CheckAndProtect.
172 }
173
174 template <typename Mapping>
TestRegion__tsan::MappingTest175 static void TestRegion(uptr beg, uptr end) {
176 if (beg == end)
177 return;
178 Printf("checking region [0x%zx-0x%zx)\n", beg, end);
179 uptr prev = 0;
180 for (uptr p0 = beg; p0 <= end; p0 += (end - beg) / 256) {
181 for (int x = -(int)kShadowCell; x <= (int)kShadowCell; x += kShadowCell) {
182 const uptr p = RoundDown(p0 + x, kShadowCell);
183 if (p < beg || p >= end)
184 continue;
185 const uptr s = MemToShadowImpl::Apply<Mapping>(p);
186 u32 *const m = MemToMetaImpl::Apply<Mapping>(p);
187 const uptr r = ShadowToMemImpl::Apply<Mapping>(s);
188 Printf(" addr=0x%zx: shadow=0x%zx meta=%p reverse=0x%zx\n", p, s, m,
189 r);
190 CHECK(IsAppMemImpl::Apply<Mapping>(p));
191 if (!broken<Mapping>(kBrokenMapping))
192 CHECK(IsShadowMemImpl::Apply<Mapping>(s));
193 CHECK(IsMetaMemImpl::Apply<Mapping>(reinterpret_cast<uptr>(m)));
194 CHECK_EQ(p, RestoreAddrImpl::Apply<Mapping>(CompressAddr(p)));
195 if (!broken<Mapping>(kBrokenReverseMapping))
196 CHECK_EQ(p, r);
197 if (prev && !broken<Mapping>(kBrokenLinearity)) {
198 // Ensure that shadow and meta mappings are linear within a single
199 // user range. Lots of code that processes memory ranges assumes it.
200 const uptr prev_s = MemToShadowImpl::Apply<Mapping>(prev);
201 u32 *const prev_m = MemToMetaImpl::Apply<Mapping>(prev);
202 CHECK_EQ(s - prev_s, (p - prev) * kShadowMultiplier);
203 CHECK_EQ(m - prev_m, (p - prev) / kMetaShadowCell);
204 }
205 prev = p;
206 }
207 }
208 }
209
210 template <typename Mapping>
TestDisjointMetas__tsan::MappingTest211 static void TestDisjointMetas() {
212 // Checks that the meta for each app region does not overlap with
213 // the meta for other app regions. For example, the meta for a high
214 // app pointer shouldn't be aliased to the meta of a mid app pointer.
215 // Notice that this is important even though there does not exist a
216 // MetaToMem function.
217 // (If a MetaToMem function did exist, we could simply
218 // check in the TestRegion function that it inverts MemToMeta.)
219 //
220 // We don't try to be clever by allowing the non-PIE (low app)
221 // and PIE (mid and high app) meta regions to overlap.
222 struct Region metas[4];
223 int num_regions = 0;
224 AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kLoAppMemBeg,
225 Mapping::kLoAppMemEnd);
226 AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kMidAppMemBeg,
227 Mapping::kMidAppMemEnd);
228 AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kHiAppMemBeg,
229 Mapping::kHiAppMemEnd);
230 AddMetaRegion<Mapping>(metas, &num_regions, Mapping::kHeapMemBeg,
231 Mapping::kHeapMemEnd);
232
233 // It is not required that the low app shadow is below the mid app
234 // shadow etc., hence we sort the shadows.
235 qsort(metas, num_regions, sizeof(struct Region), CompareRegion);
236
237 for (int i = 0; i < num_regions; i++)
238 Printf("[0x%lu, 0x%lu]\n", metas[i].start, metas[i].end);
239
240 if (!broken<Mapping>(kBrokenAliasedMetas))
241 for (int i = 1; i < num_regions; i++)
242 CHECK(metas[i - 1].end <= metas[i].start);
243 }
244 };
245
TEST(Shadow,AllMappings)246 TEST(Shadow, AllMappings) { ForEachMapping<MappingTest>(); }
247
248 } // namespace __tsan
249