Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 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 | |
Dynamic Tools Team | 09e6d48 | 2019-11-26 18:18:14 -0800 | [diff] [blame] | 9 | #include "tests/scudo_unit_test.h" |
| 10 | |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 11 | #include "list.h" |
| 12 | #include "release.h" |
| 13 | #include "size_class_map.h" |
| 14 | |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 15 | #include <string.h> |
| 16 | |
| 17 | #include <algorithm> |
| 18 | #include <random> |
Dynamic Tools Team | 09e6d48 | 2019-11-26 18:18:14 -0800 | [diff] [blame] | 19 | #include <set> |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 20 | |
| 21 | TEST(ScudoReleaseTest, PackedCounterArray) { |
| 22 | for (scudo::uptr I = 0; I < SCUDO_WORDSIZE; I++) { |
| 23 | // Various valid counter's max values packed into one word. |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 24 | scudo::PackedCounterArray Counters2N(1U, 1U, 1UL << I); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 25 | EXPECT_EQ(sizeof(scudo::uptr), Counters2N.getBufferSize()); |
| 26 | // Check the "all bit set" values too. |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 27 | scudo::PackedCounterArray Counters2N1_1(1U, 1U, ~0UL >> I); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 28 | EXPECT_EQ(sizeof(scudo::uptr), Counters2N1_1.getBufferSize()); |
| 29 | // Verify the packing ratio, the counter is Expected to be packed into the |
| 30 | // closest power of 2 bits. |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 31 | scudo::PackedCounterArray Counters(1U, SCUDO_WORDSIZE, 1UL << I); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 32 | EXPECT_EQ(sizeof(scudo::uptr) * scudo::roundUpToPowerOfTwo(I + 1), |
| 33 | Counters.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); |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 41 | scudo::PackedCounterArray Counters(1U, NumCounters, |
| 42 | 1UL << ((1UL << I) - 1)); |
| 43 | Counters.inc(0U, 0U); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 44 | for (scudo::uptr C = 1; C < NumCounters - 1; C++) { |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 45 | EXPECT_EQ(0UL, Counters.get(0U, C)); |
| 46 | Counters.inc(0U, C); |
| 47 | EXPECT_EQ(1UL, Counters.get(0U, C - 1)); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 48 | } |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 49 | EXPECT_EQ(0UL, Counters.get(0U, NumCounters - 1)); |
| 50 | Counters.inc(0U, NumCounters - 1); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 51 | if (I > 0) { |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 52 | Counters.incRange(0u, 0U, NumCounters - 1); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 53 | for (scudo::uptr C = 0; C < NumCounters; C++) |
Kostya Kortchinsky | d618cbf | 2020-07-16 16:13:04 -0700 | [diff] [blame] | 54 | EXPECT_EQ(2UL, Counters.get(0U, C)); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 55 | } |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | class StringRangeRecorder { |
| 60 | public: |
| 61 | std::string ReportedPages; |
| 62 | |
| 63 | StringRangeRecorder() |
| 64 | : PageSizeScaledLog(scudo::getLog2(scudo::getPageSizeCached())) {} |
| 65 | |
| 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 | |
| 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 | |
| 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 | } |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame^] | 127 | |
| 128 | scudo::uptr getBase() const { return 0; } |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 129 | }; |
| 130 | |
| 131 | // Simplified version of a TransferBatch. |
| 132 | template <class SizeClassMap> struct FreeBatch { |
| 133 | static const scudo::u32 MaxCount = SizeClassMap::MaxNumCachedHint; |
| 134 | void clear() { Count = 0; } |
| 135 | void add(scudo::uptr P) { |
| 136 | DCHECK_LT(Count, MaxCount); |
| 137 | Batch[Count++] = P; |
| 138 | } |
| 139 | scudo::u32 getCount() const { return Count; } |
| 140 | scudo::uptr get(scudo::u32 I) const { |
| 141 | DCHECK_LE(I, Count); |
| 142 | return Batch[I]; |
| 143 | } |
| 144 | FreeBatch *Next; |
| 145 | |
| 146 | private: |
| 147 | scudo::u32 Count; |
| 148 | scudo::uptr Batch[MaxCount]; |
| 149 | }; |
| 150 | |
| 151 | template <class SizeClassMap> void testReleaseFreeMemoryToOS() { |
| 152 | typedef FreeBatch<SizeClassMap> Batch; |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 153 | const scudo::uptr PagesCount = 1024; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 154 | const scudo::uptr PageSize = scudo::getPageSizeCached(); |
| 155 | std::mt19937 R; |
| 156 | scudo::u32 RandState = 42; |
| 157 | |
| 158 | for (scudo::uptr I = 1; I <= SizeClassMap::LargestClassId; I++) { |
| 159 | const scudo::uptr BlockSize = SizeClassMap::getSizeByClassId(I); |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 160 | const scudo::uptr MaxBlocks = PagesCount * PageSize / BlockSize; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 161 | |
| 162 | // Generate the random free list. |
| 163 | std::vector<scudo::uptr> FreeArray; |
| 164 | bool InFreeRange = false; |
| 165 | scudo::uptr CurrentRangeEnd = 0; |
| 166 | for (scudo::uptr I = 0; I < MaxBlocks; I++) { |
| 167 | if (I == CurrentRangeEnd) { |
| 168 | InFreeRange = (scudo::getRandomU32(&RandState) & 1U) == 1; |
| 169 | CurrentRangeEnd += (scudo::getRandomU32(&RandState) & 0x7f) + 1; |
| 170 | } |
| 171 | if (InFreeRange) |
| 172 | FreeArray.push_back(I * BlockSize); |
| 173 | } |
| 174 | if (FreeArray.empty()) |
| 175 | continue; |
| 176 | // Shuffle the array to ensure that the order is irrelevant. |
| 177 | std::shuffle(FreeArray.begin(), FreeArray.end(), R); |
| 178 | |
| 179 | // Build the FreeList from the FreeArray. |
Dynamic Tools Team | 3599770 | 2019-10-28 15:06:10 -0700 | [diff] [blame] | 180 | scudo::SinglyLinkedList<Batch> FreeList; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 181 | FreeList.clear(); |
| 182 | Batch *CurrentBatch = nullptr; |
| 183 | for (auto const &Block : FreeArray) { |
| 184 | if (!CurrentBatch) { |
| 185 | CurrentBatch = new Batch; |
| 186 | CurrentBatch->clear(); |
| 187 | FreeList.push_back(CurrentBatch); |
| 188 | } |
| 189 | CurrentBatch->add(Block); |
| 190 | if (CurrentBatch->getCount() == Batch::MaxCount) |
| 191 | CurrentBatch = nullptr; |
| 192 | } |
| 193 | |
| 194 | // Release the memory. |
Kostya Kortchinsky | bcd746b | 2020-08-24 14:13:12 -0700 | [diff] [blame] | 195 | auto SkipRegion = [](UNUSED scudo::uptr RegionIndex) { return false; }; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame^] | 196 | auto DecompactPtr = [](scudo::uptr P) { return P; }; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 197 | ReleasedPagesRecorder Recorder; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame^] | 198 | releaseFreeMemoryToOS(FreeList, MaxBlocks * BlockSize, 1U, BlockSize, |
| 199 | &Recorder, DecompactPtr, SkipRegion); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 200 | |
| 201 | // Verify that there are no released pages touched by used chunks and all |
| 202 | // ranges of free chunks big enough to contain the entire memory pages had |
| 203 | // these pages released. |
| 204 | scudo::uptr VerifiedReleasedPages = 0; |
| 205 | std::set<scudo::uptr> FreeBlocks(FreeArray.begin(), FreeArray.end()); |
| 206 | |
| 207 | scudo::uptr CurrentBlock = 0; |
| 208 | InFreeRange = false; |
| 209 | scudo::uptr CurrentFreeRangeStart = 0; |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 210 | for (scudo::uptr I = 0; I < MaxBlocks; I++) { |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 211 | const bool IsFreeBlock = |
| 212 | FreeBlocks.find(CurrentBlock) != FreeBlocks.end(); |
| 213 | if (IsFreeBlock) { |
| 214 | if (!InFreeRange) { |
| 215 | InFreeRange = true; |
| 216 | CurrentFreeRangeStart = CurrentBlock; |
| 217 | } |
| 218 | } else { |
| 219 | // Verify that this used chunk does not touch any released page. |
| 220 | const scudo::uptr StartPage = CurrentBlock / PageSize; |
| 221 | const scudo::uptr EndPage = (CurrentBlock + BlockSize - 1) / PageSize; |
| 222 | for (scudo::uptr J = StartPage; J <= EndPage; J++) { |
| 223 | const bool PageReleased = Recorder.ReportedPages.find(J * PageSize) != |
| 224 | Recorder.ReportedPages.end(); |
| 225 | EXPECT_EQ(false, PageReleased); |
| 226 | } |
| 227 | |
| 228 | if (InFreeRange) { |
| 229 | InFreeRange = false; |
| 230 | // Verify that all entire memory pages covered by this range of free |
| 231 | // chunks were released. |
| 232 | scudo::uptr P = scudo::roundUpTo(CurrentFreeRangeStart, PageSize); |
| 233 | while (P + PageSize <= CurrentBlock) { |
| 234 | const bool PageReleased = |
| 235 | Recorder.ReportedPages.find(P) != Recorder.ReportedPages.end(); |
| 236 | EXPECT_EQ(true, PageReleased); |
| 237 | VerifiedReleasedPages++; |
| 238 | P += PageSize; |
| 239 | } |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | CurrentBlock += BlockSize; |
| 244 | } |
| 245 | |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 246 | if (InFreeRange) { |
| 247 | scudo::uptr P = scudo::roundUpTo(CurrentFreeRangeStart, PageSize); |
| 248 | const scudo::uptr EndPage = |
| 249 | scudo::roundUpTo(MaxBlocks * BlockSize, PageSize); |
| 250 | while (P + PageSize <= EndPage) { |
| 251 | const bool PageReleased = |
| 252 | Recorder.ReportedPages.find(P) != Recorder.ReportedPages.end(); |
| 253 | EXPECT_EQ(true, PageReleased); |
| 254 | VerifiedReleasedPages++; |
| 255 | P += PageSize; |
| 256 | } |
| 257 | } |
| 258 | |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 259 | EXPECT_EQ(Recorder.ReportedPages.size(), VerifiedReleasedPages); |
| 260 | |
| 261 | while (!FreeList.empty()) { |
| 262 | CurrentBatch = FreeList.front(); |
| 263 | FreeList.pop_front(); |
| 264 | delete CurrentBatch; |
| 265 | } |
| 266 | } |
| 267 | } |
| 268 | |
| 269 | TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSDefault) { |
| 270 | testReleaseFreeMemoryToOS<scudo::DefaultSizeClassMap>(); |
| 271 | } |
| 272 | |
| 273 | TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSAndroid) { |
| 274 | testReleaseFreeMemoryToOS<scudo::AndroidSizeClassMap>(); |
| 275 | } |
| 276 | |
| 277 | TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSSvelte) { |
| 278 | testReleaseFreeMemoryToOS<scudo::SvelteSizeClassMap>(); |
| 279 | } |