1 //===-- release_test.cpp ----------------------------------------*- C++ -*-===//
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 #include "tests/scudo_unit_test.h"
10
11 #include "list.h"
12 #include "release.h"
13 #include "size_class_map.h"
14
15 #include <string.h>
16
17 #include <algorithm>
18 #include <random>
19 #include <set>
20
TEST(ScudoReleaseTest,RegionPageMap)21 TEST(ScudoReleaseTest, RegionPageMap) {
22 for (scudo::uptr I = 0; I < SCUDO_WORDSIZE; I++) {
23 // Various valid counter's max values packed into one word.
24 scudo::RegionPageMap PageMap2N(1U, 1U, 1UL << I);
25 EXPECT_EQ(sizeof(scudo::uptr), PageMap2N.getBufferSize());
26 // Check the "all bit set" values too.
27 scudo::RegionPageMap PageMap2N1_1(1U, 1U, ~0UL >> I);
28 EXPECT_EQ(sizeof(scudo::uptr), PageMap2N1_1.getBufferSize());
29 // Verify the packing ratio, the counter is Expected to be packed into the
30 // closest power of 2 bits.
31 scudo::RegionPageMap PageMap(1U, SCUDO_WORDSIZE, 1UL << I);
32 EXPECT_EQ(sizeof(scudo::uptr) * scudo::roundUpToPowerOfTwo(I + 1),
33 PageMap.getBufferSize());
34 }
35
36 // Go through 1, 2, 4, 8, .. {32,64} bits per counter.
37 for (scudo::uptr I = 0; (SCUDO_WORDSIZE >> I) != 0; I++) {
38 // Make sure counters request one memory page for the buffer.
39 const scudo::uptr NumCounters =
40 (scudo::getPageSizeCached() / 8) * (SCUDO_WORDSIZE >> I);
41 scudo::RegionPageMap PageMap(1U, NumCounters,
42 1UL << ((1UL << I) - 1));
43 PageMap.inc(0U, 0U);
44 for (scudo::uptr C = 1; C < NumCounters - 1; C++) {
45 EXPECT_EQ(0UL, PageMap.get(0U, C));
46 PageMap.inc(0U, C);
47 EXPECT_EQ(1UL, PageMap.get(0U, C - 1));
48 }
49 EXPECT_EQ(0UL, PageMap.get(0U, NumCounters - 1));
50 PageMap.inc(0U, NumCounters - 1);
51 if (I > 0) {
52 PageMap.incRange(0u, 0U, NumCounters - 1);
53 for (scudo::uptr C = 0; C < NumCounters; C++)
54 EXPECT_EQ(2UL, PageMap.get(0U, C));
55 }
56 }
57 }
58
59 class StringRangeRecorder {
60 public:
61 std::string ReportedPages;
62
StringRangeRecorder()63 StringRangeRecorder()
64 : PageSizeScaledLog(scudo::getLog2(scudo::getPageSizeCached())) {}
65
releasePageRangeToOS(scudo::uptr From,scudo::uptr To)66 void releasePageRangeToOS(scudo::uptr From, scudo::uptr To) {
67 From >>= PageSizeScaledLog;
68 To >>= PageSizeScaledLog;
69 EXPECT_LT(From, To);
70 if (!ReportedPages.empty())
71 EXPECT_LT(LastPageReported, From);
72 ReportedPages.append(From - LastPageReported, '.');
73 ReportedPages.append(To - From, 'x');
74 LastPageReported = To;
75 }
76
77 private:
78 const scudo::uptr PageSizeScaledLog;
79 scudo::uptr LastPageReported = 0;
80 };
81
TEST(ScudoReleaseTest,FreePagesRangeTracker)82 TEST(ScudoReleaseTest, FreePagesRangeTracker) {
83 // 'x' denotes a page to be released, '.' denotes a page to be kept around.
84 const char *TestCases[] = {
85 "",
86 ".",
87 "x",
88 "........",
89 "xxxxxxxxxxx",
90 "..............xxxxx",
91 "xxxxxxxxxxxxxxxxxx.....",
92 "......xxxxxxxx........",
93 "xxx..........xxxxxxxxxxxxxxx",
94 "......xxxx....xxxx........",
95 "xxx..........xxxxxxxx....xxxxxxx",
96 "x.x.x.x.x.x.x.x.x.x.x.x.",
97 ".x.x.x.x.x.x.x.x.x.x.x.x",
98 ".x.x.x.x.x.x.x.x.x.x.x.x.",
99 "x.x.x.x.x.x.x.x.x.x.x.x.x",
100 };
101 typedef scudo::FreePagesRangeTracker<StringRangeRecorder> RangeTracker;
102
103 for (auto TestCase : TestCases) {
104 StringRangeRecorder Recorder;
105 RangeTracker Tracker(Recorder);
106 for (scudo::uptr I = 0; TestCase[I] != 0; I++)
107 Tracker.processNextPage(TestCase[I] == 'x');
108 Tracker.finish();
109 // Strip trailing '.'-pages before comparing the results as they are not
110 // going to be reported to range_recorder anyway.
111 const char *LastX = strrchr(TestCase, 'x');
112 std::string Expected(TestCase,
113 LastX == nullptr ? 0 : (LastX - TestCase + 1));
114 EXPECT_STREQ(Expected.c_str(), Recorder.ReportedPages.c_str());
115 }
116 }
117
118 class ReleasedPagesRecorder {
119 public:
120 std::set<scudo::uptr> ReportedPages;
121
releasePageRangeToOS(scudo::uptr From,scudo::uptr To)122 void releasePageRangeToOS(scudo::uptr From, scudo::uptr To) {
123 const scudo::uptr PageSize = scudo::getPageSizeCached();
124 for (scudo::uptr I = From; I < To; I += PageSize)
125 ReportedPages.insert(I);
126 }
127
getBase() const128 scudo::uptr getBase() const { return 0; }
129 };
130
131 // Simplified version of a TransferBatch.
132 template <class SizeClassMap> struct FreeBatch {
133 static const scudo::u16 MaxCount = SizeClassMap::MaxNumCachedHint;
clearFreeBatch134 void clear() { Count = 0; }
addFreeBatch135 void add(scudo::uptr P) {
136 DCHECK_LT(Count, MaxCount);
137 Batch[Count++] = P;
138 }
getCountFreeBatch139 scudo::u16 getCount() const { return Count; }
getFreeBatch140 scudo::uptr get(scudo::u16 I) const {
141 DCHECK_LE(I, Count);
142 return Batch[I];
143 }
144 FreeBatch *Next;
145
146 private:
147 scudo::uptr Batch[MaxCount];
148 scudo::u16 Count;
149 };
150
testReleaseFreeMemoryToOS()151 template <class SizeClassMap> void testReleaseFreeMemoryToOS() {
152 typedef FreeBatch<SizeClassMap> Batch;
153 const scudo::uptr PagesCount = 1024;
154 const scudo::uptr PageSize = scudo::getPageSizeCached();
155 const scudo::uptr PageSizeLog = scudo::getLog2(PageSize);
156 std::mt19937 R;
157 scudo::u32 RandState = 42;
158
159 for (scudo::uptr I = 1; I <= SizeClassMap::LargestClassId; I++) {
160 const scudo::uptr BlockSize = SizeClassMap::getSizeByClassId(I);
161 const scudo::uptr MaxBlocks = PagesCount * PageSize / BlockSize;
162
163 // Generate the random free list.
164 std::vector<scudo::uptr> FreeArray;
165 bool InFreeRange = false;
166 scudo::uptr CurrentRangeEnd = 0;
167 for (scudo::uptr I = 0; I < MaxBlocks; I++) {
168 if (I == CurrentRangeEnd) {
169 InFreeRange = (scudo::getRandomU32(&RandState) & 1U) == 1;
170 CurrentRangeEnd += (scudo::getRandomU32(&RandState) & 0x7f) + 1;
171 }
172 if (InFreeRange)
173 FreeArray.push_back(I * BlockSize);
174 }
175 if (FreeArray.empty())
176 continue;
177 // Shuffle the array to ensure that the order is irrelevant.
178 std::shuffle(FreeArray.begin(), FreeArray.end(), R);
179
180 // Build the FreeList from the FreeArray.
181 scudo::SinglyLinkedList<Batch> FreeList;
182 FreeList.clear();
183 Batch *CurrentBatch = nullptr;
184 for (auto const &Block : FreeArray) {
185 if (!CurrentBatch) {
186 CurrentBatch = new Batch;
187 CurrentBatch->clear();
188 FreeList.push_back(CurrentBatch);
189 }
190 CurrentBatch->add(Block);
191 if (CurrentBatch->getCount() == Batch::MaxCount)
192 CurrentBatch = nullptr;
193 }
194
195 // Release the memory.
196 auto SkipRegion = [](UNUSED scudo::uptr RegionIndex) { return false; };
197 auto DecompactPtr = [](scudo::uptr P) { return P; };
198 ReleasedPagesRecorder Recorder;
199 scudo::PageReleaseContext Context(BlockSize,
200 /*RegionSize=*/MaxBlocks * BlockSize,
201 /*NumberOfRegions=*/1U);
202 ASSERT_FALSE(Context.hasBlockMarked());
203 Context.markFreeBlocks(FreeList, DecompactPtr, Recorder.getBase());
204 ASSERT_TRUE(Context.hasBlockMarked());
205 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
206 scudo::RegionPageMap &PageMap = Context.PageMap;
207
208 // Verify that there are no released pages touched by used chunks and all
209 // ranges of free chunks big enough to contain the entire memory pages had
210 // these pages released.
211 scudo::uptr VerifiedReleasedPages = 0;
212 std::set<scudo::uptr> FreeBlocks(FreeArray.begin(), FreeArray.end());
213
214 scudo::uptr CurrentBlock = 0;
215 InFreeRange = false;
216 scudo::uptr CurrentFreeRangeStart = 0;
217 for (scudo::uptr I = 0; I < MaxBlocks; I++) {
218 const bool IsFreeBlock =
219 FreeBlocks.find(CurrentBlock) != FreeBlocks.end();
220 if (IsFreeBlock) {
221 if (!InFreeRange) {
222 InFreeRange = true;
223 CurrentFreeRangeStart = CurrentBlock;
224 }
225 } else {
226 // Verify that this used chunk does not touch any released page.
227 const scudo::uptr StartPage = CurrentBlock / PageSize;
228 const scudo::uptr EndPage = (CurrentBlock + BlockSize - 1) / PageSize;
229 for (scudo::uptr J = StartPage; J <= EndPage; J++) {
230 const bool PageReleased = Recorder.ReportedPages.find(J * PageSize) !=
231 Recorder.ReportedPages.end();
232 EXPECT_EQ(false, PageReleased);
233 EXPECT_EQ(false,
234 PageMap.isAllCounted(0, (J * PageSize) >> PageSizeLog));
235 }
236
237 if (InFreeRange) {
238 InFreeRange = false;
239 // Verify that all entire memory pages covered by this range of free
240 // chunks were released.
241 scudo::uptr P = scudo::roundUpTo(CurrentFreeRangeStart, PageSize);
242 while (P + PageSize <= CurrentBlock) {
243 const bool PageReleased =
244 Recorder.ReportedPages.find(P) != Recorder.ReportedPages.end();
245 EXPECT_EQ(true, PageReleased);
246 EXPECT_EQ(true, PageMap.isAllCounted(0, P >> PageSizeLog));
247 VerifiedReleasedPages++;
248 P += PageSize;
249 }
250 }
251 }
252
253 CurrentBlock += BlockSize;
254 }
255
256 if (InFreeRange) {
257 scudo::uptr P = scudo::roundUpTo(CurrentFreeRangeStart, PageSize);
258 const scudo::uptr EndPage =
259 scudo::roundUpTo(MaxBlocks * BlockSize, PageSize);
260 while (P + PageSize <= EndPage) {
261 const bool PageReleased =
262 Recorder.ReportedPages.find(P) != Recorder.ReportedPages.end();
263 EXPECT_EQ(true, PageReleased);
264 EXPECT_EQ(true, PageMap.isAllCounted(0, P >> PageSizeLog));
265 VerifiedReleasedPages++;
266 P += PageSize;
267 }
268 }
269
270 EXPECT_EQ(Recorder.ReportedPages.size(), VerifiedReleasedPages);
271
272 while (!FreeList.empty()) {
273 CurrentBatch = FreeList.front();
274 FreeList.pop_front();
275 delete CurrentBatch;
276 }
277 }
278 }
279
TEST(ScudoReleaseTest,ReleaseFreeMemoryToOSDefault)280 TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSDefault) {
281 testReleaseFreeMemoryToOS<scudo::DefaultSizeClassMap>();
282 }
283
TEST(ScudoReleaseTest,ReleaseFreeMemoryToOSAndroid)284 TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSAndroid) {
285 testReleaseFreeMemoryToOS<scudo::AndroidSizeClassMap>();
286 }
287
TEST(ScudoReleaseTest,ReleaseFreeMemoryToOSSvelte)288 TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSSvelte) {
289 testReleaseFreeMemoryToOS<scudo::SvelteSizeClassMap>();
290 }
291