475 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "tests/scudo_unit_test.h"10 11#include "allocator_config.h"12#include "allocator_config_wrapper.h"13#include "condition_variable.h"14#include "primary32.h"15#include "primary64.h"16#include "size_class_map.h"17 18#include <algorithm>19#include <chrono>20#include <condition_variable>21#include <mutex>22#include <random>23#include <stdlib.h>24#include <thread>25#include <vector>26 27// Note that with small enough regions, the SizeClassAllocator64 also works on28// 32-bit architectures. It's not something we want to encourage, but we still29// should ensure the tests pass.30 31template <typename SizeClassMapT> struct TestConfig1 {32 static const bool MaySupportMemoryTagging = false;33 template <typename> using TSDRegistryT = void;34 template <typename> using PrimaryT = void;35 template <typename> using SecondaryT = void;36 37 struct Primary {38 using SizeClassMap = SizeClassMapT;39 static const scudo::uptr RegionSizeLog = 18U;40 static const scudo::uptr GroupSizeLog = 18U;41 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;42 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;43 typedef scudo::uptr CompactPtrT;44 static const scudo::uptr CompactPtrScale = 0;45 static const bool EnableRandomOffset = true;46 static const scudo::uptr MapSizeIncrement = 1UL << 18;47 };48};49 50template <typename SizeClassMapT> struct TestConfig2 {51 static const bool MaySupportMemoryTagging = false;52 template <typename> using TSDRegistryT = void;53 template <typename> using PrimaryT = void;54 template <typename> using SecondaryT = void;55 56 struct Primary {57 using SizeClassMap = SizeClassMapT;58#if defined(__mips__)59 // Unable to allocate greater size on QEMU-user.60 static const scudo::uptr RegionSizeLog = 23U;61#else62 static const scudo::uptr RegionSizeLog = 24U;63#endif64 static const scudo::uptr GroupSizeLog = 20U;65 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;66 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;67 typedef scudo::uptr CompactPtrT;68 static const scudo::uptr CompactPtrScale = 0;69 static const bool EnableRandomOffset = true;70 static const scudo::uptr MapSizeIncrement = 1UL << 18;71 };72};73 74template <typename SizeClassMapT> struct TestConfig3 {75 static const bool MaySupportMemoryTagging = true;76 template <typename> using TSDRegistryT = void;77 template <typename> using PrimaryT = void;78 template <typename> using SecondaryT = void;79 80 struct Primary {81 using SizeClassMap = SizeClassMapT;82#if defined(__mips__)83 // Unable to allocate greater size on QEMU-user.84 static const scudo::uptr RegionSizeLog = 23U;85#else86 static const scudo::uptr RegionSizeLog = 24U;87#endif88 static const scudo::uptr GroupSizeLog = 20U;89 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;90 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;91 typedef scudo::uptr CompactPtrT;92 static const scudo::uptr CompactPtrScale = 0;93 static const bool EnableContiguousRegions = false;94 static const bool EnableRandomOffset = true;95 static const scudo::uptr MapSizeIncrement = 1UL << 18;96 };97};98 99template <typename SizeClassMapT> struct TestConfig4 {100 static const bool MaySupportMemoryTagging = true;101 template <typename> using TSDRegistryT = void;102 template <typename> using PrimaryT = void;103 template <typename> using SecondaryT = void;104 105 struct Primary {106 using SizeClassMap = SizeClassMapT;107#if defined(__mips__)108 // Unable to allocate greater size on QEMU-user.109 static const scudo::uptr RegionSizeLog = 23U;110#else111 static const scudo::uptr RegionSizeLog = 24U;112#endif113 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;114 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;115 static const scudo::uptr CompactPtrScale = 3U;116 static const scudo::uptr GroupSizeLog = 20U;117 typedef scudo::u32 CompactPtrT;118 static const bool EnableRandomOffset = true;119 static const scudo::uptr MapSizeIncrement = 1UL << 18;120 };121};122 123// This is the only test config that enables the condition variable.124template <typename SizeClassMapT> struct TestConfig5 {125 static const bool MaySupportMemoryTagging = true;126 template <typename> using TSDRegistryT = void;127 template <typename> using PrimaryT = void;128 template <typename> using SecondaryT = void;129 130 struct Primary {131 using SizeClassMap = SizeClassMapT;132#if defined(__mips__)133 // Unable to allocate greater size on QEMU-user.134 static const scudo::uptr RegionSizeLog = 23U;135#else136 static const scudo::uptr RegionSizeLog = 24U;137#endif138 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;139 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;140 static const scudo::uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;141 static const scudo::uptr GroupSizeLog = 18U;142 typedef scudo::u32 CompactPtrT;143 static const bool EnableRandomOffset = true;144 static const scudo::uptr MapSizeIncrement = 1UL << 18;145#if SCUDO_LINUX146 using ConditionVariableT = scudo::ConditionVariableLinux;147#else148 using ConditionVariableT = scudo::ConditionVariableDummy;149#endif150 };151};152 153template <template <typename> class BaseConfig, typename SizeClassMapT>154struct Config : public BaseConfig<SizeClassMapT> {};155 156template <template <typename> class BaseConfig, typename SizeClassMapT>157struct SizeClassAllocator158 : public scudo::SizeClassAllocator64<159 scudo::PrimaryConfig<Config<BaseConfig, SizeClassMapT>>> {};160template <typename SizeClassMapT>161struct SizeClassAllocator<TestConfig1, SizeClassMapT>162 : public scudo::SizeClassAllocator32<163 scudo::PrimaryConfig<Config<TestConfig1, SizeClassMapT>>> {};164 165template <template <typename> class BaseConfig, typename SizeClassMapT>166struct TestAllocator : public SizeClassAllocator<BaseConfig, SizeClassMapT> {167 ~TestAllocator() {168 this->verifyAllBlocksAreReleasedTestOnly();169 this->unmapTestOnly();170 }171 172 void *operator new(size_t size) {173 void *p = nullptr;174 EXPECT_EQ(0, posix_memalign(&p, alignof(TestAllocator), size));175 return p;176 }177 178 void operator delete(void *ptr) { free(ptr); }179};180 181template <template <typename> class BaseConfig>182struct ScudoPrimaryTest : public Test {};183 184#if SCUDO_FUCHSIA185#define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \186 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2) \187 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)188#else189#define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \190 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig1) \191 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2) \192 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3) \193 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig4) \194 SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig5)195#endif196 197#define SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TYPE) \198 using FIXTURE##NAME##_##TYPE = FIXTURE##NAME<TYPE>; \199 TEST_F(FIXTURE##NAME##_##TYPE, NAME) { FIXTURE##NAME<TYPE>::Run(); }200 201#define SCUDO_TYPED_TEST(FIXTURE, NAME) \202 template <template <typename> class TypeParam> \203 struct FIXTURE##NAME : public FIXTURE<TypeParam> { \204 void Run(); \205 }; \206 SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \207 template <template <typename> class TypeParam> \208 void FIXTURE##NAME<TypeParam>::Run()209 210SCUDO_TYPED_TEST(ScudoPrimaryTest, BasicPrimary) {211 using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;212 std::unique_ptr<Primary> Allocator(new Primary);213 Allocator->init(/*ReleaseToOsInterval=*/-1);214 typename Primary::SizeClassAllocatorT SizeClassAllocator;215 SizeClassAllocator.init(nullptr, Allocator.get());216 const scudo::uptr NumberOfAllocations = 32U;217 for (scudo::uptr I = 0; I <= 16U; I++) {218 const scudo::uptr Size = 1UL << I;219 if (!Primary::canAllocate(Size))220 continue;221 const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);222 void *Pointers[NumberOfAllocations];223 for (scudo::uptr J = 0; J < NumberOfAllocations; J++) {224 void *P = SizeClassAllocator.allocate(ClassId);225 memset(P, 'B', Size);226 Pointers[J] = P;227 }228 for (scudo::uptr J = 0; J < NumberOfAllocations; J++)229 SizeClassAllocator.deallocate(ClassId, Pointers[J]);230 }231 SizeClassAllocator.destroy(nullptr);232 Allocator->releaseToOS(scudo::ReleaseToOS::Force);233 if (TEST_HAS_FAILURE) {234 scudo::ScopedString Str;235 Allocator->getStats(&Str);236 Str.output();237 }238}239 240struct SmallRegionsConfig {241 static const bool MaySupportMemoryTagging = false;242 template <typename> using TSDRegistryT = void;243 template <typename> using PrimaryT = void;244 template <typename> using SecondaryT = void;245 246 struct Primary {247 using SizeClassMap = scudo::DefaultSizeClassMap;248 static const scudo::uptr RegionSizeLog = 21U;249 static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;250 static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;251 typedef scudo::uptr CompactPtrT;252 static const scudo::uptr CompactPtrScale = 0;253 static const bool EnableRandomOffset = true;254 static const scudo::uptr MapSizeIncrement = 1UL << 18;255 static const scudo::uptr GroupSizeLog = 20U;256 };257};258 259// The 64-bit SizeClassAllocator can be easily OOM'd with small region sizes.260// For the 32-bit one, it requires actually exhausting memory, so we skip it.261TEST(ScudoPrimaryTest, Primary64OOM) {262 using Primary =263 scudo::SizeClassAllocator64<scudo::PrimaryConfig<SmallRegionsConfig>>;264 Primary Allocator;265 Allocator.init(/*ReleaseToOsInterval=*/-1);266 typename Primary::SizeClassAllocatorT SizeClassAllocator;267 scudo::GlobalStats Stats;268 Stats.init();269 SizeClassAllocator.init(&Stats, &Allocator);270 bool AllocationFailed = false;271 std::vector<void *> Blocks;272 const scudo::uptr ClassId = Primary::SizeClassMap::LargestClassId;273 const scudo::uptr Size = Primary::getSizeByClassId(ClassId);274 const scudo::u16 MaxCachedBlockCount =275 Primary::SizeClassAllocatorT::getMaxCached(Size);276 277 for (scudo::uptr I = 0; I < 10000U; I++) {278 for (scudo::uptr J = 0; J < MaxCachedBlockCount; ++J) {279 void *Ptr = SizeClassAllocator.allocate(ClassId);280 if (Ptr == nullptr) {281 AllocationFailed = true;282 break;283 }284 memset(Ptr, 'B', Size);285 Blocks.push_back(Ptr);286 }287 }288 289 for (auto *Ptr : Blocks)290 SizeClassAllocator.deallocate(ClassId, Ptr);291 292 SizeClassAllocator.destroy(nullptr);293 Allocator.releaseToOS(scudo::ReleaseToOS::Force);294 EXPECT_EQ(AllocationFailed, true);295 if (TEST_HAS_FAILURE) {296 scudo::ScopedString Str;297 Allocator.getStats(&Str);298 Str.output();299 }300 Allocator.unmapTestOnly();301}302 303SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryIterate) {304 using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;305 std::unique_ptr<Primary> Allocator(new Primary);306 Allocator->init(/*ReleaseToOsInterval=*/-1);307 typename Primary::SizeClassAllocatorT SizeClassAllocator;308 SizeClassAllocator.init(nullptr, Allocator.get());309 std::vector<std::pair<scudo::uptr, void *>> V;310 for (scudo::uptr I = 0; I < 64U; I++) {311 const scudo::uptr Size =312 static_cast<scudo::uptr>(std::rand()) % Primary::SizeClassMap::MaxSize;313 const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);314 void *P = SizeClassAllocator.allocate(ClassId);315 V.push_back(std::make_pair(ClassId, P));316 }317 scudo::uptr Found = 0;318 auto Lambda = [&V, &Found](scudo::uptr Block) {319 for (const auto &Pair : V) {320 if (Pair.second == reinterpret_cast<void *>(Block))321 Found++;322 }323 };324 Allocator->disable();325 Allocator->iterateOverBlocks(Lambda);326 Allocator->enable();327 EXPECT_EQ(Found, V.size());328 while (!V.empty()) {329 auto Pair = V.back();330 SizeClassAllocator.deallocate(Pair.first, Pair.second);331 V.pop_back();332 }333 SizeClassAllocator.destroy(nullptr);334 Allocator->releaseToOS(scudo::ReleaseToOS::Force);335 if (TEST_HAS_FAILURE) {336 scudo::ScopedString Str;337 Allocator->getStats(&Str);338 Str.output();339 }340}341 342SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryThreaded) {343 using Primary = TestAllocator<TypeParam, scudo::Config::Primary::SizeClassMap>;344 std::unique_ptr<Primary> Allocator(new Primary);345 Allocator->init(/*ReleaseToOsInterval=*/-1);346 std::mutex Mutex;347 std::condition_variable Cv;348 bool Ready = false;349 std::thread Threads[32];350 for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++) {351 Threads[I] = std::thread([&]() {352 static thread_local353 typename Primary::SizeClassAllocatorT SizeClassAllocator;354 SizeClassAllocator.init(nullptr, Allocator.get());355 std::vector<std::pair<scudo::uptr, void *>> V;356 {357 std::unique_lock<std::mutex> Lock(Mutex);358 while (!Ready)359 Cv.wait(Lock);360 }361 for (scudo::uptr I = 0; I < 256U; I++) {362 const scudo::uptr Size = static_cast<scudo::uptr>(std::rand()) %363 Primary::SizeClassMap::MaxSize / 4;364 const scudo::uptr ClassId =365 Primary::SizeClassMap::getClassIdBySize(Size);366 void *P = SizeClassAllocator.allocate(ClassId);367 if (P)368 V.push_back(std::make_pair(ClassId, P));369 }370 371 // Try to interleave pushBlocks(), popBlocks() and releaseToOS().372 Allocator->releaseToOS(scudo::ReleaseToOS::Force);373 374 while (!V.empty()) {375 auto Pair = V.back();376 SizeClassAllocator.deallocate(Pair.first, Pair.second);377 V.pop_back();378 // This increases the chance of having non-full Batches and it will jump379 // into the code path of merging Batches.380 if (std::rand() % 8 == 0)381 SizeClassAllocator.drain();382 }383 SizeClassAllocator.destroy(nullptr);384 });385 }386 {387 std::unique_lock<std::mutex> Lock(Mutex);388 Ready = true;389 Cv.notify_all();390 }391 for (auto &T : Threads)392 T.join();393 Allocator->releaseToOS(scudo::ReleaseToOS::Force);394 if (TEST_HAS_FAILURE) {395 scudo::ScopedString Str;396 Allocator->getStats(&Str);397 Allocator->getFragmentationInfo(&Str);398 Allocator->getMemoryGroupFragmentationInfo(&Str);399 Str.output();400 }401}402 403// Through a simple allocation that spans two pages, verify that releaseToOS404// actually releases some bytes (at least one page worth). This is a regression405// test for an error in how the release criteria were computed.406SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {407 using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;408 std::unique_ptr<Primary> Allocator(new Primary);409 Allocator->init(/*ReleaseToOsInterval=*/-1);410 typename Primary::SizeClassAllocatorT SizeClassAllocator;411 SizeClassAllocator.init(nullptr, Allocator.get());412 const scudo::uptr Size = scudo::getPageSizeCached() * 2;413 EXPECT_TRUE(Primary::canAllocate(Size));414 const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);415 void *P = SizeClassAllocator.allocate(ClassId);416 EXPECT_NE(P, nullptr);417 SizeClassAllocator.deallocate(ClassId, P);418 SizeClassAllocator.destroy(nullptr);419 EXPECT_GT(Allocator->releaseToOS(scudo::ReleaseToOS::ForceAll), 0U);420}421 422SCUDO_TYPED_TEST(ScudoPrimaryTest, MemoryGroup) {423 using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;424 std::unique_ptr<Primary> Allocator(new Primary);425 Allocator->init(/*ReleaseToOsInterval=*/-1);426 typename Primary::SizeClassAllocatorT SizeClassAllocator;427 SizeClassAllocator.init(nullptr, Allocator.get());428 const scudo::uptr Size = 32U;429 const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);430 431 // We will allocate 4 times the group size memory and release all of them. We432 // expect the free blocks will be classified with groups. Then we will433 // allocate the same amount of memory as group size and expect the blocks will434 // have the max address difference smaller or equal to 2 times the group size.435 // Note that it isn't necessary to be in the range of single group size436 // because the way we get the group id is doing compact pointer shifting.437 // According to configuration, the compact pointer may not align to group438 // size. As a result, the blocks can cross two groups at most.439 const scudo::uptr GroupSizeMem = (1ULL << Primary::GroupSizeLog);440 const scudo::uptr PeakAllocationMem = 4 * GroupSizeMem;441 const scudo::uptr PeakNumberOfAllocations = PeakAllocationMem / Size;442 const scudo::uptr FinalNumberOfAllocations = GroupSizeMem / Size;443 std::vector<scudo::uptr> Blocks;444 std::mt19937 R;445 446 for (scudo::uptr I = 0; I < PeakNumberOfAllocations; ++I)447 Blocks.push_back(448 reinterpret_cast<scudo::uptr>(SizeClassAllocator.allocate(ClassId)));449 450 std::shuffle(Blocks.begin(), Blocks.end(), R);451 452 // Release all the allocated blocks, including those held by local cache.453 while (!Blocks.empty()) {454 SizeClassAllocator.deallocate(ClassId,455 reinterpret_cast<void *>(Blocks.back()));456 Blocks.pop_back();457 }458 SizeClassAllocator.drain();459 460 for (scudo::uptr I = 0; I < FinalNumberOfAllocations; ++I)461 Blocks.push_back(462 reinterpret_cast<scudo::uptr>(SizeClassAllocator.allocate(ClassId)));463 464 EXPECT_LE(*std::max_element(Blocks.begin(), Blocks.end()) -465 *std::min_element(Blocks.begin(), Blocks.end()),466 GroupSizeMem * 2);467 468 while (!Blocks.empty()) {469 SizeClassAllocator.deallocate(ClassId,470 reinterpret_cast<void *>(Blocks.back()));471 Blocks.pop_back();472 }473 SizeClassAllocator.drain();474}475