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