1 //===-- primary_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 "primary32.h"
12 #include "primary64.h"
13 #include "size_class_map.h"
14 
15 #include <condition_variable>
16 #include <mutex>
17 #include <thread>
18 #include <vector>
19 
20 // Note that with small enough regions, the SizeClassAllocator64 also works on
21 // 32-bit architectures. It's not something we want to encourage, but we still
22 // should ensure the tests pass.
23 
24 template <typename Primary> static void testPrimary() {
25   const scudo::uptr NumberOfAllocations = 32U;
26   auto Deleter = [](Primary *P) {
27     P->unmapTestOnly();
28     delete P;
29   };
30   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
31   Allocator->init(/*ReleaseToOsInterval=*/-1);
32   typename Primary::CacheT Cache;
33   Cache.init(nullptr, Allocator.get());
34   for (scudo::uptr I = 0; I <= 16U; I++) {
35     const scudo::uptr Size = 1UL << I;
36     if (!Primary::canAllocate(Size))
37       continue;
38     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
39     void *Pointers[NumberOfAllocations];
40     for (scudo::uptr J = 0; J < NumberOfAllocations; J++) {
41       void *P = Cache.allocate(ClassId);
42       memset(P, 'B', Size);
43       Pointers[J] = P;
44     }
45     for (scudo::uptr J = 0; J < NumberOfAllocations; J++)
46       Cache.deallocate(ClassId, Pointers[J]);
47   }
48   Cache.destroy(nullptr);
49   Allocator->releaseToOS();
50   scudo::ScopedString Str(1024);
51   Allocator->getStats(&Str);
52   Str.output();
53 }
54 
55 template <typename SizeClassMapT> struct TestConfig1 {
56   using SizeClassMap = SizeClassMapT;
57   static const scudo::uptr PrimaryRegionSizeLog = 18U;
58   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
59   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
60   static const bool MaySupportMemoryTagging = false;
61   typedef scudo::uptr PrimaryCompactPtrT;
62   static const scudo::uptr PrimaryCompactPtrScale = 0;
63 };
64 
65 template <typename SizeClassMapT> struct TestConfig2 {
66   using SizeClassMap = SizeClassMapT;
67   static const scudo::uptr PrimaryRegionSizeLog = 24U;
68   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
69   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
70   static const bool MaySupportMemoryTagging = false;
71   typedef scudo::uptr PrimaryCompactPtrT;
72   static const scudo::uptr PrimaryCompactPtrScale = 0;
73 };
74 
75 template <typename SizeClassMapT> struct TestConfig3 {
76   using SizeClassMap = SizeClassMapT;
77   static const scudo::uptr PrimaryRegionSizeLog = 24U;
78   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
79   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
80   static const bool MaySupportMemoryTagging = true;
81   typedef scudo::uptr PrimaryCompactPtrT;
82   static const scudo::uptr PrimaryCompactPtrScale = 0;
83 };
84 
85 TEST(ScudoPrimaryTest, BasicPrimary) {
86   using SizeClassMap = scudo::DefaultSizeClassMap;
87 #if !SCUDO_FUCHSIA
88   testPrimary<scudo::SizeClassAllocator32<TestConfig1<SizeClassMap>>>();
89 #endif
90   testPrimary<scudo::SizeClassAllocator64<TestConfig2<SizeClassMap>>>();
91   testPrimary<scudo::SizeClassAllocator64<TestConfig3<SizeClassMap>>>();
92 }
93 
94 struct SmallRegionsConfig {
95   using SizeClassMap = scudo::DefaultSizeClassMap;
96   static const scudo::uptr PrimaryRegionSizeLog = 20U;
97   static const scudo::s32 PrimaryMinReleaseToOsIntervalMs = INT32_MIN;
98   static const scudo::s32 PrimaryMaxReleaseToOsIntervalMs = INT32_MAX;
99   static const bool MaySupportMemoryTagging = false;
100   typedef scudo::uptr PrimaryCompactPtrT;
101   static const scudo::uptr PrimaryCompactPtrScale = 0;
102 };
103 
104 // The 64-bit SizeClassAllocator can be easily OOM'd with small region sizes.
105 // For the 32-bit one, it requires actually exhausting memory, so we skip it.
106 TEST(ScudoPrimaryTest, Primary64OOM) {
107   using Primary = scudo::SizeClassAllocator64<SmallRegionsConfig>;
108   using TransferBatch = Primary::CacheT::TransferBatch;
109   Primary Allocator;
110   Allocator.init(/*ReleaseToOsInterval=*/-1);
111   typename Primary::CacheT Cache;
112   scudo::GlobalStats Stats;
113   Stats.init();
114   Cache.init(&Stats, &Allocator);
115   bool AllocationFailed = false;
116   std::vector<TransferBatch *> Batches;
117   const scudo::uptr ClassId = Primary::SizeClassMap::LargestClassId;
118   const scudo::uptr Size = Primary::getSizeByClassId(ClassId);
119   for (scudo::uptr I = 0; I < 10000U; I++) {
120     TransferBatch *B = Allocator.popBatch(&Cache, ClassId);
121     if (!B) {
122       AllocationFailed = true;
123       break;
124     }
125     for (scudo::u32 J = 0; J < B->getCount(); J++)
126       memset(Allocator.decompactPtr(ClassId, B->get(J)), 'B', Size);
127     Batches.push_back(B);
128   }
129   while (!Batches.empty()) {
130     Allocator.pushBatch(ClassId, Batches.back());
131     Batches.pop_back();
132   }
133   Cache.destroy(nullptr);
134   Allocator.releaseToOS();
135   scudo::ScopedString Str(1024);
136   Allocator.getStats(&Str);
137   Str.output();
138   EXPECT_EQ(AllocationFailed, true);
139   Allocator.unmapTestOnly();
140 }
141 
142 template <typename Primary> static void testIteratePrimary() {
143   auto Deleter = [](Primary *P) {
144     P->unmapTestOnly();
145     delete P;
146   };
147   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
148   Allocator->init(/*ReleaseToOsInterval=*/-1);
149   typename Primary::CacheT Cache;
150   Cache.init(nullptr, Allocator.get());
151   std::vector<std::pair<scudo::uptr, void *>> V;
152   for (scudo::uptr I = 0; I < 64U; I++) {
153     const scudo::uptr Size = std::rand() % Primary::SizeClassMap::MaxSize;
154     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
155     void *P = Cache.allocate(ClassId);
156     V.push_back(std::make_pair(ClassId, P));
157   }
158   scudo::uptr Found = 0;
159   auto Lambda = [V, &Found](scudo::uptr Block) {
160     for (const auto &Pair : V) {
161       if (Pair.second == reinterpret_cast<void *>(Block))
162         Found++;
163     }
164   };
165   Allocator->disable();
166   Allocator->iterateOverBlocks(Lambda);
167   Allocator->enable();
168   EXPECT_EQ(Found, V.size());
169   while (!V.empty()) {
170     auto Pair = V.back();
171     Cache.deallocate(Pair.first, Pair.second);
172     V.pop_back();
173   }
174   Cache.destroy(nullptr);
175   Allocator->releaseToOS();
176   scudo::ScopedString Str(1024);
177   Allocator->getStats(&Str);
178   Str.output();
179 }
180 
181 TEST(ScudoPrimaryTest, PrimaryIterate) {
182   using SizeClassMap = scudo::DefaultSizeClassMap;
183 #if !SCUDO_FUCHSIA
184   testIteratePrimary<scudo::SizeClassAllocator32<TestConfig1<SizeClassMap>>>();
185 #endif
186   testIteratePrimary<scudo::SizeClassAllocator64<TestConfig2<SizeClassMap>>>();
187   testIteratePrimary<scudo::SizeClassAllocator64<TestConfig3<SizeClassMap>>>();
188 }
189 
190 static std::mutex Mutex;
191 static std::condition_variable Cv;
192 static bool Ready;
193 
194 template <typename Primary> static void performAllocations(Primary *Allocator) {
195   static thread_local typename Primary::CacheT Cache;
196   Cache.init(nullptr, Allocator);
197   std::vector<std::pair<scudo::uptr, void *>> V;
198   {
199     std::unique_lock<std::mutex> Lock(Mutex);
200     while (!Ready)
201       Cv.wait(Lock);
202   }
203   for (scudo::uptr I = 0; I < 256U; I++) {
204     const scudo::uptr Size = std::rand() % Primary::SizeClassMap::MaxSize / 4;
205     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
206     void *P = Cache.allocate(ClassId);
207     if (P)
208       V.push_back(std::make_pair(ClassId, P));
209   }
210   while (!V.empty()) {
211     auto Pair = V.back();
212     Cache.deallocate(Pair.first, Pair.second);
213     V.pop_back();
214   }
215   Cache.destroy(nullptr);
216 }
217 
218 template <typename Primary> static void testPrimaryThreaded() {
219   Ready = false;
220   auto Deleter = [](Primary *P) {
221     P->unmapTestOnly();
222     delete P;
223   };
224   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
225   Allocator->init(/*ReleaseToOsInterval=*/-1);
226   std::thread Threads[32];
227   for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++)
228     Threads[I] = std::thread(performAllocations<Primary>, Allocator.get());
229   {
230     std::unique_lock<std::mutex> Lock(Mutex);
231     Ready = true;
232     Cv.notify_all();
233   }
234   for (auto &T : Threads)
235     T.join();
236   Allocator->releaseToOS();
237   scudo::ScopedString Str(1024);
238   Allocator->getStats(&Str);
239   Str.output();
240 }
241 
242 TEST(ScudoPrimaryTest, PrimaryThreaded) {
243   using SizeClassMap = scudo::SvelteSizeClassMap;
244 #if !SCUDO_FUCHSIA
245   testPrimaryThreaded<scudo::SizeClassAllocator32<TestConfig1<SizeClassMap>>>();
246 #endif
247   testPrimaryThreaded<scudo::SizeClassAllocator64<TestConfig2<SizeClassMap>>>();
248   testPrimaryThreaded<scudo::SizeClassAllocator64<TestConfig3<SizeClassMap>>>();
249 }
250 
251 // Through a simple allocation that spans two pages, verify that releaseToOS
252 // actually releases some bytes (at least one page worth). This is a regression
253 // test for an error in how the release criteria were computed.
254 template <typename Primary> static void testReleaseToOS() {
255   auto Deleter = [](Primary *P) {
256     P->unmapTestOnly();
257     delete P;
258   };
259   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
260   Allocator->init(/*ReleaseToOsInterval=*/-1);
261   typename Primary::CacheT Cache;
262   Cache.init(nullptr, Allocator.get());
263   const scudo::uptr Size = scudo::getPageSizeCached() * 2;
264   EXPECT_TRUE(Primary::canAllocate(Size));
265   const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
266   void *P = Cache.allocate(ClassId);
267   EXPECT_NE(P, nullptr);
268   Cache.deallocate(ClassId, P);
269   Cache.destroy(nullptr);
270   EXPECT_GT(Allocator->releaseToOS(), 0U);
271 }
272 
273 TEST(ScudoPrimaryTest, ReleaseToOS) {
274   using SizeClassMap = scudo::DefaultSizeClassMap;
275 #if !SCUDO_FUCHSIA
276   testReleaseToOS<scudo::SizeClassAllocator32<TestConfig1<SizeClassMap>>>();
277 #endif
278   testReleaseToOS<scudo::SizeClassAllocator64<TestConfig2<SizeClassMap>>>();
279   testReleaseToOS<scudo::SizeClassAllocator64<TestConfig3<SizeClassMap>>>();
280 }
281