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