//===-- primary_test.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "tests/scudo_unit_test.h"
#include "allocator_config.h"
#include "allocator_config_wrapper.h"
#include "condition_variable.h"
#include "primary32.h"
#include "primary64.h"
#include "size_class_map.h"
#include <algorithm>
#include <chrono>
#include <condition_variable>
#include <mutex>
#include <random>
#include <stdlib.h>
#include <thread>
#include <vector>
// Note that with small enough regions, the SizeClassAllocator64 also works on
// 32-bit architectures. It's not something we want to encourage, but we still
// should ensure the tests pass.
template <typename SizeClassMapT> struct TestConfig1 {
static const bool MaySupportMemoryTagging = false;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = SizeClassMapT;
static const scudo::uptr RegionSizeLog = 18U;
static const scudo::uptr GroupSizeLog = 18U;
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
typedef scudo::uptr CompactPtrT;
static const scudo::uptr CompactPtrScale = 0;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
};
};
template <typename SizeClassMapT> struct TestConfig2 {
static const bool MaySupportMemoryTagging = false;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = SizeClassMapT;
#if defined(__mips__)
// Unable to allocate greater size on QEMU-user.
static const scudo::uptr RegionSizeLog = 23U;
#else
static const scudo::uptr RegionSizeLog = 24U;
#endif
static const scudo::uptr GroupSizeLog = 20U;
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
typedef scudo::uptr CompactPtrT;
static const scudo::uptr CompactPtrScale = 0;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
};
};
template <typename SizeClassMapT> struct TestConfig3 {
static const bool MaySupportMemoryTagging = true;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = SizeClassMapT;
#if defined(__mips__)
// Unable to allocate greater size on QEMU-user.
static const scudo::uptr RegionSizeLog = 23U;
#else
static const scudo::uptr RegionSizeLog = 24U;
#endif
static const scudo::uptr GroupSizeLog = 20U;
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
typedef scudo::uptr CompactPtrT;
static const scudo::uptr CompactPtrScale = 0;
static const bool EnableContiguousRegions = false;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
};
};
template <typename SizeClassMapT> struct TestConfig4 {
static const bool MaySupportMemoryTagging = true;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = SizeClassMapT;
#if defined(__mips__)
// Unable to allocate greater size on QEMU-user.
static const scudo::uptr RegionSizeLog = 23U;
#else
static const scudo::uptr RegionSizeLog = 24U;
#endif
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
static const scudo::uptr CompactPtrScale = 3U;
static const scudo::uptr GroupSizeLog = 20U;
typedef scudo::u32 CompactPtrT;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
};
};
// This is the only test config that enables the condition variable.
template <typename SizeClassMapT> struct TestConfig5 {
static const bool MaySupportMemoryTagging = true;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = SizeClassMapT;
#if defined(__mips__)
// Unable to allocate greater size on QEMU-user.
static const scudo::uptr RegionSizeLog = 23U;
#else
static const scudo::uptr RegionSizeLog = 24U;
#endif
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
static const scudo::uptr CompactPtrScale = SCUDO_MIN_ALIGNMENT_LOG;
static const scudo::uptr GroupSizeLog = 18U;
typedef scudo::u32 CompactPtrT;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
#if SCUDO_LINUX
using ConditionVariableT = scudo::ConditionVariableLinux;
#else
using ConditionVariableT = scudo::ConditionVariableDummy;
#endif
};
};
template <template <typename> class BaseConfig, typename SizeClassMapT>
struct Config : public BaseConfig<SizeClassMapT> {};
template <template <typename> class BaseConfig, typename SizeClassMapT>
struct SizeClassAllocator
: public scudo::SizeClassAllocator64<
scudo::PrimaryConfig<Config<BaseConfig, SizeClassMapT>>> {};
template <typename SizeClassMapT>
struct SizeClassAllocator<TestConfig1, SizeClassMapT>
: public scudo::SizeClassAllocator32<
scudo::PrimaryConfig<Config<TestConfig1, SizeClassMapT>>> {};
template <template <typename> class BaseConfig, typename SizeClassMapT>
struct TestAllocator : public SizeClassAllocator<BaseConfig, SizeClassMapT> {
~TestAllocator() {
this->verifyAllBlocksAreReleasedTestOnly();
this->unmapTestOnly();
}
void *operator new(size_t size) {
void *p = nullptr;
EXPECT_EQ(0, posix_memalign(&p, alignof(TestAllocator), size));
return p;
}
void operator delete(void *ptr) { free(ptr); }
};
template <template <typename> class BaseConfig>
struct ScudoPrimaryTest : public Test {};
#if SCUDO_FUCHSIA
#define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3)
#else
#define SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig1) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig2) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig3) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig4) \
SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TestConfig5)
#endif
#define SCUDO_TYPED_TEST_TYPE(FIXTURE, NAME, TYPE) \
using FIXTURE##NAME##_##TYPE = FIXTURE##NAME<TYPE>; \
TEST_F(FIXTURE##NAME##_##TYPE, NAME) { FIXTURE##NAME<TYPE>::Run(); }
#define SCUDO_TYPED_TEST(FIXTURE, NAME) \
template <template <typename> class TypeParam> \
struct FIXTURE##NAME : public FIXTURE<TypeParam> { \
void Run(); \
}; \
SCUDO_TYPED_TEST_ALL_TYPES(FIXTURE, NAME) \
template <template <typename> class TypeParam> \
void FIXTURE##NAME<TypeParam>::Run()
SCUDO_TYPED_TEST(ScudoPrimaryTest, BasicPrimary) {
using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
std::unique_ptr<Primary> Allocator(new Primary);
Allocator->init(/*ReleaseToOsInterval=*/-1);
typename Primary::CacheT Cache;
Cache.init(nullptr, Allocator.get());
const scudo::uptr NumberOfAllocations = 32U;
for (scudo::uptr I = 0; I <= 16U; I++) {
const scudo::uptr Size = 1UL << I;
if (!Primary::canAllocate(Size))
continue;
const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
void *Pointers[NumberOfAllocations];
for (scudo::uptr J = 0; J < NumberOfAllocations; J++) {
void *P = Cache.allocate(ClassId);
memset(P, 'B', Size);
Pointers[J] = P;
}
for (scudo::uptr J = 0; J < NumberOfAllocations; J++)
Cache.deallocate(ClassId, Pointers[J]);
}
Cache.destroy(nullptr);
Allocator->releaseToOS(scudo::ReleaseToOS::Force);
scudo::ScopedString Str;
Allocator->getStats(&Str);
Str.output();
}
struct SmallRegionsConfig {
static const bool MaySupportMemoryTagging = false;
template <typename> using TSDRegistryT = void;
template <typename> using PrimaryT = void;
template <typename> using SecondaryT = void;
struct Primary {
using SizeClassMap = scudo::DefaultSizeClassMap;
static const scudo::uptr RegionSizeLog = 21U;
static const scudo::s32 MinReleaseToOsIntervalMs = INT32_MIN;
static const scudo::s32 MaxReleaseToOsIntervalMs = INT32_MAX;
typedef scudo::uptr CompactPtrT;
static const scudo::uptr CompactPtrScale = 0;
static const bool EnableRandomOffset = true;
static const scudo::uptr MapSizeIncrement = 1UL << 18;
static const scudo::uptr GroupSizeLog = 20U;
};
};
// The 64-bit SizeClassAllocator can be easily OOM'd with small region sizes.
// For the 32-bit one, it requires actually exhausting memory, so we skip it.
TEST(ScudoPrimaryTest, Primary64OOM) {
using Primary =
scudo::SizeClassAllocator64<scudo::PrimaryConfig<SmallRegionsConfig>>;
Primary Allocator;
Allocator.init(/*ReleaseToOsInterval=*/-1);
typename Primary::CacheT Cache;
scudo::GlobalStats Stats;
Stats.init();
Cache.init(&Stats, &Allocator);
bool AllocationFailed = false;
std::vector<void *> Blocks;
const scudo::uptr ClassId = Primary::SizeClassMap::LargestClassId;
const scudo::uptr Size = Primary::getSizeByClassId(ClassId);
const scudo::u16 MaxCachedBlockCount = Primary::CacheT::getMaxCached(Size);
for (scudo::uptr I = 0; I < 10000U; I++) {
for (scudo::uptr J = 0; J < MaxCachedBlockCount; ++J) {
void *Ptr = Cache.allocate(ClassId);
if (Ptr == nullptr) {
AllocationFailed = true;
break;
}
memset(Ptr, 'B', Size);
Blocks.push_back(Ptr);
}
}
for (auto *Ptr : Blocks)
Cache.deallocate(ClassId, Ptr);
Cache.destroy(nullptr);
Allocator.releaseToOS(scudo::ReleaseToOS::Force);
scudo::ScopedString Str;
Allocator.getStats(&Str);
Str.output();
EXPECT_EQ(AllocationFailed, true);
Allocator.unmapTestOnly();
}
SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryIterate) {
using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
std::unique_ptr<Primary> Allocator(new Primary);
Allocator->init(/*ReleaseToOsInterval=*/-1);
typename Primary::CacheT Cache;
Cache.init(nullptr, Allocator.get());
std::vector<std::pair<scudo::uptr, void *>> V;
for (scudo::uptr I = 0; I < 64U; I++) {
const scudo::uptr Size =
static_cast<scudo::uptr>(std::rand()) % Primary::SizeClassMap::MaxSize;
const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
void *P = Cache.allocate(ClassId);
V.push_back(std::make_pair(ClassId, P));
}
scudo::uptr Found = 0;
auto Lambda = [&V, &Found](scudo::uptr Block) {
for (const auto &Pair : V) {
if (Pair.second == reinterpret_cast<void *>(Block))
Found++;
}
};
Allocator->disable();
Allocator->iterateOverBlocks(Lambda);
Allocator->enable();
EXPECT_EQ(Found, V.size());
while (!V.empty()) {
auto Pair = V.back();
Cache.deallocate(Pair.first, Pair.second);
V.pop_back();
}
Cache.destroy(nullptr);
Allocator->releaseToOS(scudo::ReleaseToOS::Force);
scudo::ScopedString Str;
Allocator->getStats(&Str);
Str.output();
}
SCUDO_TYPED_TEST(ScudoPrimaryTest, PrimaryThreaded) {
using Primary = TestAllocator<TypeParam, scudo::Config::Primary::SizeClassMap>;
std::unique_ptr<Primary> Allocator(new Primary);
Allocator->init(/*ReleaseToOsInterval=*/-1);
std::mutex Mutex;
std::condition_variable Cv;
bool Ready = false;
std::thread Threads[32];
for (scudo::uptr I = 0; I < ARRAY_SIZE(Threads); I++) {
Threads[I] = std::thread([&]() {
static thread_local typename Primary::CacheT Cache;
Cache.init(nullptr, Allocator.get());
std::vector<std::pair<scudo::uptr, void *>> V;
{
std::unique_lock<std::mutex> Lock(Mutex);
while (!Ready)
Cv.wait(Lock);
}
for (scudo::uptr I = 0; I < 256U; I++) {
const scudo::uptr Size = static_cast<scudo::uptr>(std::rand()) %
Primary::SizeClassMap::MaxSize / 4;
const scudo::uptr ClassId =
Primary::SizeClassMap::getClassIdBySize(Size);
void *P = Cache.allocate(ClassId);
if (P)
V.push_back(std::make_pair(ClassId, P));
}
// Try to interleave pushBlocks(), popBlocks() and releaseToOS().
Allocator->releaseToOS(scudo::ReleaseToOS::Force);
while (!V.empty()) {
auto Pair = V.back();
Cache.deallocate(Pair.first, Pair.second);
V.pop_back();
// This increases the chance of having non-full TransferBatches and it
// will jump into the code path of merging TransferBatches.
if (std::rand() % 8 == 0)
Cache.drain();
}
Cache.destroy(nullptr);
});
}
{
std::unique_lock<std::mutex> Lock(Mutex);
Ready = true;
Cv.notify_all();
}
for (auto &T : Threads)
T.join();
Allocator->releaseToOS(scudo::ReleaseToOS::Force);
scudo::ScopedString Str;
Allocator->getStats(&Str);
Allocator->getFragmentationInfo(&Str);
Str.output();
}
// Through a simple allocation that spans two pages, verify that releaseToOS
// actually releases some bytes (at least one page worth). This is a regression
// test for an error in how the release criteria were computed.
SCUDO_TYPED_TEST(ScudoPrimaryTest, ReleaseToOS) {
using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
std::unique_ptr<Primary> Allocator(new Primary);
Allocator->init(/*ReleaseToOsInterval=*/-1);
typename Primary::CacheT Cache;
Cache.init(nullptr, Allocator.get());
const scudo::uptr Size = scudo::getPageSizeCached() * 2;
EXPECT_TRUE(Primary::canAllocate(Size));
const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
void *P = Cache.allocate(ClassId);
EXPECT_NE(P, nullptr);
Cache.deallocate(ClassId, P);
Cache.destroy(nullptr);
EXPECT_GT(Allocator->releaseToOS(scudo::ReleaseToOS::ForceAll), 0U);
}
SCUDO_TYPED_TEST(ScudoPrimaryTest, MemoryGroup) {
using Primary = TestAllocator<TypeParam, scudo::DefaultSizeClassMap>;
std::unique_ptr<Primary> Allocator(new Primary);
Allocator->init(/*ReleaseToOsInterval=*/-1);
typename Primary::CacheT Cache;
Cache.init(nullptr, Allocator.get());
const scudo::uptr Size = 32U;
const scudo::uptr ClassId = Primary::SizeClassMap::getClassIdBySize(Size);
// We will allocate 4 times the group size memory and release all of them. We
// expect the free blocks will be classified with groups. Then we will
// allocate the same amount of memory as group size and expect the blocks will
// have the max address difference smaller or equal to 2 times the group size.
// Note that it isn't necessary to be in the range of single group size
// because the way we get the group id is doing compact pointer shifting.
// According to configuration, the compact pointer may not align to group
// size. As a result, the blocks can cross two groups at most.
const scudo::uptr GroupSizeMem = (1ULL << Primary::GroupSizeLog);
const scudo::uptr PeakAllocationMem = 4 * GroupSizeMem;
const scudo::uptr PeakNumberOfAllocations = PeakAllocationMem / Size;
const scudo::uptr FinalNumberOfAllocations = GroupSizeMem / Size;
std::vector<scudo::uptr> Blocks;
std::mt19937 R;
for (scudo::uptr I = 0; I < PeakNumberOfAllocations; ++I)
Blocks.push_back(reinterpret_cast<scudo::uptr>(Cache.allocate(ClassId)));
std::shuffle(Blocks.begin(), Blocks.end(), R);
// Release all the allocated blocks, including those held by local cache.
while (!Blocks.empty()) {
Cache.deallocate(ClassId, reinterpret_cast<void *>(Blocks.back()));
Blocks.pop_back();
}
Cache.drain();
for (scudo::uptr I = 0; I < FinalNumberOfAllocations; ++I)
Blocks.push_back(reinterpret_cast<scudo::uptr>(Cache.allocate(ClassId)));
EXPECT_LE(*std::max_element(Blocks.begin(), Blocks.end()) -
*std::min_element(Blocks.begin(), Blocks.end()),
GroupSizeMem * 2);
while (!Blocks.empty()) {
Cache.deallocate(ClassId, reinterpret_cast<void *>(Blocks.back()));
Blocks.pop_back();
}
Cache.drain();
}
Codebase Browser
llvm