1 //===-- combined_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 "allocator_config.h"
10 #include "combined.h"
11 
12 #include "gtest/gtest.h"
13 
14 #include <condition_variable>
15 #include <mutex>
16 #include <thread>
17 
18 static std::mutex Mutex;
19 static std::condition_variable Cv;
20 static bool Ready = false;
21 
22 static constexpr scudo::Chunk::Origin Origin = scudo::Chunk::Origin::Malloc;
23 
24 // This allows us to turn on the Quarantine for specific tests. The Quarantine
25 // parameters are on the low end, to avoid having to loop excessively in some
26 // tests.
27 static bool UseQuarantine = false;
28 extern "C" const char *__scudo_default_options() {
29   if (!UseQuarantine)
30     return "";
31   return "quarantine_size_kb=256:thread_local_quarantine_size_kb=128:"
32          "quarantine_max_chunk_size=1024";
33 }
34 
35 template <class Config> static void testAllocator() {
36   using AllocatorT = scudo::Allocator<Config>;
37   auto Deleter = [](AllocatorT *A) {
38     A->unmapTestOnly();
39     delete A;
40   };
41   std::unique_ptr<AllocatorT, decltype(Deleter)> Allocator(new AllocatorT,
42                                                            Deleter);
43   Allocator->reset();
44 
45   constexpr scudo::uptr MinAlignLog = FIRST_32_SECOND_64(3U, 4U);
46 
47   // This allocates and deallocates a bunch of chunks, with a wide range of
48   // sizes and alignments, with a focus on sizes that could trigger weird
49   // behaviors (plus or minus a small delta of a power of two for example).
50   for (scudo::uptr SizeLog = 0U; SizeLog <= 20U; SizeLog++) {
51     for (scudo::uptr AlignLog = MinAlignLog; AlignLog <= 16U; AlignLog++) {
52       const scudo::uptr Align = 1U << AlignLog;
53       for (scudo::sptr Delta = -32; Delta <= 32; Delta++) {
54         if (static_cast<scudo::sptr>(1U << SizeLog) + Delta <= 0)
55           continue;
56         const scudo::uptr Size = (1U << SizeLog) + Delta;
57         void *P = Allocator->allocate(Size, Origin, Align);
58         EXPECT_NE(P, nullptr);
59         EXPECT_TRUE(scudo::isAligned(reinterpret_cast<scudo::uptr>(P), Align));
60         EXPECT_LE(Size, Allocator->getUsableSize(P));
61         memset(P, 0xaa, Size);
62         Allocator->deallocate(P, Origin, Size);
63       }
64     }
65   }
66   Allocator->releaseToOS();
67 
68   // Ensure that specifying ZeroContents returns a zero'd out block.
69   for (scudo::uptr SizeLog = 0U; SizeLog <= 20U; SizeLog++) {
70     for (scudo::uptr Delta = 0U; Delta <= 4U; Delta++) {
71       const scudo::uptr Size = (1U << SizeLog) + Delta * 128U;
72       void *P = Allocator->allocate(Size, Origin, 1U << MinAlignLog, true);
73       EXPECT_NE(P, nullptr);
74       for (scudo::uptr I = 0; I < Size; I++)
75         EXPECT_EQ((reinterpret_cast<char *>(P))[I], 0);
76       memset(P, 0xaa, Size);
77       Allocator->deallocate(P, Origin, Size);
78     }
79   }
80   Allocator->releaseToOS();
81 
82   // Verify that a chunk will end up being reused, at some point.
83   const scudo::uptr NeedleSize = 1024U;
84   void *NeedleP = Allocator->allocate(NeedleSize, Origin);
85   Allocator->deallocate(NeedleP, Origin);
86   bool Found = false;
87   for (scudo::uptr I = 0; I < 1024U && !Found; I++) {
88     void *P = Allocator->allocate(NeedleSize, Origin);
89     if (P == NeedleP)
90       Found = true;
91     Allocator->deallocate(P, Origin);
92   }
93   EXPECT_TRUE(Found);
94 
95   constexpr scudo::uptr MaxSize = Config::Primary::SizeClassMap::MaxSize;
96 
97   // Reallocate a large chunk all the way down to a byte, verifying that we
98   // preserve the data in the process.
99   scudo::uptr Size = MaxSize * 2;
100   const scudo::uptr DataSize = 2048U;
101   void *P = Allocator->allocate(Size, Origin);
102   const char Marker = 0xab;
103   memset(P, Marker, scudo::Min(Size, DataSize));
104   while (Size > 1U) {
105     Size /= 2U;
106     void *NewP = Allocator->reallocate(P, Size);
107     EXPECT_NE(NewP, nullptr);
108     for (scudo::uptr J = 0; J < scudo::Min(Size, DataSize); J++)
109       EXPECT_EQ((reinterpret_cast<char *>(NewP))[J], Marker);
110     P = NewP;
111   }
112   Allocator->deallocate(P, Origin);
113 
114   // Check that reallocating a chunk to a slightly smaller or larger size
115   // returns the same chunk. This requires that all the sizes we iterate on use
116   // the same block size, but that should be the case for 2048 with our default
117   // class size maps.
118   P = Allocator->allocate(DataSize, Origin);
119   memset(P, Marker, DataSize);
120   for (scudo::sptr Delta = -32; Delta < 32; Delta += 8) {
121     const scudo::uptr NewSize = DataSize + Delta;
122     void *NewP = Allocator->reallocate(P, NewSize);
123     EXPECT_EQ(NewP, P);
124     for (scudo::uptr I = 0; I < scudo::Min(DataSize, NewSize); I++)
125       EXPECT_EQ((reinterpret_cast<char *>(NewP))[I], Marker);
126   }
127   Allocator->deallocate(P, Origin);
128 
129   // Allocates a bunch of chunks, then iterate over all the chunks, ensuring
130   // they are the ones we allocated. This requires the allocator to not have any
131   // other allocated chunk at this point (eg: won't work with the Quarantine).
132   if (!UseQuarantine) {
133     std::vector<void *> V;
134     for (scudo::uptr I = 0; I < 64U; I++)
135       V.push_back(Allocator->allocate(rand() % (MaxSize / 2U), Origin));
136     Allocator->disable();
137     Allocator->iterateOverChunks(
138         0U, static_cast<scudo::uptr>(SCUDO_MMAP_RANGE_SIZE - 1),
139         [](uintptr_t Base, size_t Size, void *Arg) {
140           std::vector<void *> *V = reinterpret_cast<std::vector<void *> *>(Arg);
141           void *P = reinterpret_cast<void *>(Base);
142           EXPECT_NE(std::find(V->begin(), V->end(), P), V->end());
143         },
144         reinterpret_cast<void *>(&V));
145     Allocator->enable();
146     while (!V.empty()) {
147       Allocator->deallocate(V.back(), Origin);
148       V.pop_back();
149     }
150   }
151 
152   Allocator->releaseToOS();
153 
154   scudo::uptr BufferSize = 8192;
155   std::vector<char> Buffer(BufferSize);
156   scudo::uptr ActualSize = Allocator->getStats(Buffer.data(), BufferSize);
157   while (ActualSize > BufferSize) {
158     BufferSize = ActualSize + 1024;
159     Buffer.resize(BufferSize);
160     ActualSize = Allocator->getStats(Buffer.data(), BufferSize);
161   }
162   std::string Stats(Buffer.begin(), Buffer.end());
163   // Basic checks on the contents of the statistics output, which also allows us
164   // to verify that we got it all.
165   EXPECT_NE(Stats.find("Stats: SizeClassAllocator"), std::string::npos);
166   EXPECT_NE(Stats.find("Stats: MapAllocator"), std::string::npos);
167   EXPECT_NE(Stats.find("Stats: Quarantine"), std::string::npos);
168 }
169 
170 TEST(ScudoCombinedTest, BasicCombined) {
171   testAllocator<scudo::DefaultConfig>();
172 #if SCUDO_WORDSIZE == 64U
173   testAllocator<scudo::FuchsiaConfig>();
174 #endif
175   // The following configs should work on all platforms.
176   UseQuarantine = true;
177   testAllocator<scudo::AndroidConfig>();
178   UseQuarantine = false;
179   testAllocator<scudo::AndroidSvelteConfig>();
180 }
181 
182 template <typename AllocatorT> static void stressAllocator(AllocatorT *A) {
183   {
184     std::unique_lock<std::mutex> Lock(Mutex);
185     while (!Ready)
186       Cv.wait(Lock);
187   }
188   std::vector<std::pair<void *, scudo::uptr>> V;
189   for (scudo::uptr I = 0; I < 256U; I++) {
190     const scudo::uptr Size = std::rand() % 4096U;
191     void *P = A->allocate(Size, Origin);
192     // A region could have ran out of memory, resulting in a null P.
193     if (P)
194       V.push_back(std::make_pair(P, Size));
195   }
196   while (!V.empty()) {
197     auto Pair = V.back();
198     A->deallocate(Pair.first, Origin, Pair.second);
199     V.pop_back();
200   }
201 }
202 
203 template <class Config> static void testAllocatorThreaded() {
204   using AllocatorT = scudo::Allocator<Config>;
205   auto Deleter = [](AllocatorT *A) {
206     A->unmapTestOnly();
207     delete A;
208   };
209   std::unique_ptr<AllocatorT, decltype(Deleter)> Allocator(new AllocatorT,
210                                                            Deleter);
211   Allocator->reset();
212   std::thread Threads[32];
213   for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++)
214     Threads[I] = std::thread(stressAllocator<AllocatorT>, Allocator.get());
215   {
216     std::unique_lock<std::mutex> Lock(Mutex);
217     Ready = true;
218     Cv.notify_all();
219   }
220   for (auto &T : Threads)
221     T.join();
222   Allocator->releaseToOS();
223 }
224 
225 TEST(ScudoCombinedTest, ThreadedCombined) {
226   testAllocatorThreaded<scudo::DefaultConfig>();
227 #if SCUDO_WORDSIZE == 64U
228   testAllocatorThreaded<scudo::FuchsiaConfig>();
229 #endif
230   UseQuarantine = true;
231   testAllocatorThreaded<scudo::AndroidConfig>();
232   UseQuarantine = false;
233   testAllocatorThreaded<scudo::AndroidSvelteConfig>();
234 }
235 
236 struct DeathConfig {
237   // Tiny allocator, its Primary only serves chunks of 1024 bytes.
238   using DeathSizeClassMap = scudo::SizeClassMap<1U, 10U, 10U, 10U, 1U, 10U>;
239   typedef scudo::SizeClassAllocator32<DeathSizeClassMap, 18U> Primary;
240   typedef scudo::MapAllocator<0U> Secondary;
241   template <class A> using TSDRegistryT = scudo::TSDRegistrySharedT<A, 1U>;
242 };
243 
244 TEST(ScudoCombinedTest, DeathCombined) {
245   using AllocatorT = scudo::Allocator<DeathConfig>;
246   auto Deleter = [](AllocatorT *A) {
247     A->unmapTestOnly();
248     delete A;
249   };
250   std::unique_ptr<AllocatorT, decltype(Deleter)> Allocator(new AllocatorT,
251                                                            Deleter);
252   Allocator->reset();
253 
254   const scudo::uptr Size = 1000U;
255   void *P = Allocator->allocate(Size, Origin);
256   EXPECT_NE(P, nullptr);
257 
258   // Invalid sized deallocation.
259   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size + 8U), "");
260 
261   // Misaligned pointer.
262   void *MisalignedP =
263       reinterpret_cast<void *>(reinterpret_cast<scudo::uptr>(P) | 1U);
264   EXPECT_DEATH(Allocator->deallocate(MisalignedP, Origin, Size), "");
265   EXPECT_DEATH(Allocator->reallocate(MisalignedP, Size * 2U), "");
266 
267   // Header corruption.
268   scudo::u64 *H =
269       reinterpret_cast<scudo::u64 *>(scudo::Chunk::getAtomicHeader(P));
270   *H ^= 0x42U;
271   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size), "");
272   *H ^= 0x420042U;
273   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size), "");
274   *H ^= 0x420000U;
275 
276   // Invalid chunk state.
277   Allocator->deallocate(P, Origin, Size);
278   EXPECT_DEATH(Allocator->deallocate(P, Origin, Size), "");
279   EXPECT_DEATH(Allocator->reallocate(P, Size * 2U), "");
280   EXPECT_DEATH(Allocator->getUsableSize(P), "");
281 }
282