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> {
82   ~TestAllocator() { this->unmapTestOnly(); }
83 
84   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 
90   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 
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.
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 
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 
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.
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