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 "primary32.h"
10 #include "primary64.h"
11 #include "size_class_map.h"
12 
13 #include "gtest/gtest.h"
14 
15 #include <condition_variable>
16 #include <mutex>
17 #include <thread>
18 
19 // Note that with small enough regions, the SizeClassAllocator64 also works on
20 // 32-bit architectures. It's not something we want to encourage, but we still
21 // should ensure the tests pass.
22 
23 template <typename Primary> static void testPrimary() {
24   const scudo::uptr NumberOfAllocations = 32U;
25   auto Deleter = [](Primary *P) {
26     P->unmapTestOnly();
27     delete P;
28   };
29   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
30   Allocator->init(/*ReleaseToOsInterval=*/-1);
31   typename Primary::CacheT Cache;
32   Cache.init(nullptr, Allocator.get());
33   for (scudo::uptr I = 0; I <= 16U; I++) {
34     const scudo::uptr Size = 1UL << I;
35     if (!Primary::canAllocate(Size))
36       continue;
37     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
38     void *Pointers[NumberOfAllocations];
39     for (scudo::uptr J = 0; J < NumberOfAllocations; J++) {
40       void *P = Cache.allocate(ClassId);
41       memset(P, 'B', Size);
42       Pointers[J] = P;
43     }
44     for (scudo::uptr J = 0; J < NumberOfAllocations; J++)
45       Cache.deallocate(ClassId, Pointers[J]);
46   }
47   Cache.destroy(nullptr);
48   Allocator->releaseToOS();
49   Allocator->printStats();
50 }
51 
52 TEST(ScudoPrimaryTest, BasicPrimary) {
53   using SizeClassMap = scudo::DefaultSizeClassMap;
54   testPrimary<scudo::SizeClassAllocator32<SizeClassMap, 18U>>();
55   testPrimary<scudo::SizeClassAllocator64<SizeClassMap, 24U>>();
56 }
57 
58 // The 64-bit SizeClassAllocator can be easily OOM'd with small region sizes.
59 // For the 32-bit one, it requires actually exhausting memory, so we skip it.
60 TEST(ScudoPrimaryTest, Primary64OOM) {
61   using Primary = scudo::SizeClassAllocator64<scudo::DefaultSizeClassMap, 20U>;
62   using TransferBatch = Primary::CacheT::TransferBatch;
63   Primary Allocator;
64   Allocator.init(/*ReleaseToOsInterval=*/-1);
65   typename Primary::CacheT Cache;
66   scudo::GlobalStats Stats;
67   Stats.init();
68   Cache.init(&Stats, &Allocator);
69   bool AllocationFailed = false;
70   std::vector<TransferBatch *> Batches;
71   const scudo::uptr ClassId = Primary::SizeClassMap::LargestClassId;
72   const scudo::uptr Size = Primary::getSizeByClassId(ClassId);
73   for (scudo::uptr I = 0; I < 10000U; I++) {
74     TransferBatch *B = Allocator.popBatch(&Cache, ClassId);
75     if (!B) {
76       AllocationFailed = true;
77       break;
78     }
79     for (scudo::uptr J = 0; J < B->getCount(); J++)
80       memset(B->get(J), 'B', Size);
81     Batches.push_back(B);
82   }
83   while (!Batches.empty()) {
84     Allocator.pushBatch(ClassId, Batches.back());
85     Batches.pop_back();
86   }
87   Cache.destroy(nullptr);
88   Allocator.releaseToOS();
89   Allocator.printStats();
90   EXPECT_EQ(AllocationFailed, true);
91   Allocator.unmapTestOnly();
92 }
93 
94 template <typename Primary> static void testIteratePrimary() {
95   auto Deleter = [](Primary *P) {
96     P->unmapTestOnly();
97     delete P;
98   };
99   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
100   Allocator->init(/*ReleaseToOsInterval=*/-1);
101   typename Primary::CacheT Cache;
102   Cache.init(nullptr, Allocator.get());
103   std::vector<std::pair<scudo::uptr, void *>> V;
104   for (scudo::uptr I = 0; I < 64U; I++) {
105     const scudo::uptr Size = std::rand() % Primary::SizeClassMap::MaxSize;
106     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
107     void *P = Cache.allocate(ClassId);
108     V.push_back(std::make_pair(ClassId, P));
109   }
110   scudo::uptr Found = 0;
111   auto Lambda = [V, &Found](scudo::uptr Block) {
112     for (const auto &Pair : V) {
113       if (Pair.second == reinterpret_cast<void *>(Block))
114         Found++;
115     }
116   };
117   Allocator->disable();
118   Allocator->iterateOverBlocks(Lambda);
119   Allocator->enable();
120   EXPECT_EQ(Found, V.size());
121   while (!V.empty()) {
122     auto Pair = V.back();
123     Cache.deallocate(Pair.first, Pair.second);
124     V.pop_back();
125   }
126   Cache.destroy(nullptr);
127   Allocator->releaseToOS();
128   Allocator->printStats();
129 }
130 
131 TEST(ScudoPrimaryTest, PrimaryIterate) {
132   using SizeClassMap = scudo::DefaultSizeClassMap;
133   testIteratePrimary<scudo::SizeClassAllocator32<SizeClassMap, 18U>>();
134   testIteratePrimary<scudo::SizeClassAllocator64<SizeClassMap, 24U>>();
135 }
136 
137 static std::mutex Mutex;
138 static std::condition_variable Cv;
139 static bool Ready = false;
140 
141 template <typename Primary> static void performAllocations(Primary *Allocator) {
142   static THREADLOCAL typename Primary::CacheT Cache;
143   Cache.init(nullptr, Allocator);
144   std::vector<std::pair<scudo::uptr, void *>> V;
145   {
146     std::unique_lock<std::mutex> Lock(Mutex);
147     while (!Ready)
148       Cv.wait(Lock);
149   }
150   for (scudo::uptr I = 0; I < 256U; I++) {
151     const scudo::uptr Size = std::rand() % Primary::SizeClassMap::MaxSize / 4;
152     const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
153     void *P = Cache.allocate(ClassId);
154     if (P)
155       V.push_back(std::make_pair(ClassId, P));
156   }
157   while (!V.empty()) {
158     auto Pair = V.back();
159     Cache.deallocate(Pair.first, Pair.second);
160     V.pop_back();
161   }
162   Cache.destroy(nullptr);
163 }
164 
165 template <typename Primary> static void testPrimaryThreaded() {
166   auto Deleter = [](Primary *P) {
167     P->unmapTestOnly();
168     delete P;
169   };
170   std::unique_ptr<Primary, decltype(Deleter)> Allocator(new Primary, Deleter);
171   Allocator->init(/*ReleaseToOsInterval=*/-1);
172   std::thread Threads[32];
173   for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++)
174     Threads[I] = std::thread(performAllocations<Primary>, Allocator.get());
175   {
176     std::unique_lock<std::mutex> Lock(Mutex);
177     Ready = true;
178     Cv.notify_all();
179   }
180   for (auto &T : Threads)
181     T.join();
182   Allocator->releaseToOS();
183   Allocator->printStats();
184 }
185 
186 TEST(ScudoPrimaryTest, PrimaryThreaded) {
187   using SizeClassMap = scudo::SvelteSizeClassMap;
188   testPrimaryThreaded<scudo::SizeClassAllocator32<SizeClassMap, 18U>>();
189   testPrimaryThreaded<scudo::SizeClassAllocator64<SizeClassMap, 24U>>();
190 }
191