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