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