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