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