From 1f9b498405be032de2422440577f9a04dc7ad066 Mon Sep 17 00:00:00 2001 From: Dimitar Trendafilov Date: Thu, 24 Dec 2020 13:57:04 +0200 Subject: Test bench app for garbage collectors --- gctest/gc.h | 54 +++++++ gctest/gc_leak.cpp | 25 ++++ gctest/genie.lua | 44 ++++++ gctest/main.cpp | 356 +++++++++++++++++++++++++++++++++++++++++++++++ gctest/weighted_action.h | 33 +++++ 5 files changed, 512 insertions(+) create mode 100644 gctest/gc.h create mode 100644 gctest/gc_leak.cpp create mode 100644 gctest/genie.lua create mode 100644 gctest/main.cpp create mode 100644 gctest/weighted_action.h diff --git a/gctest/gc.h b/gctest/gc.h new file mode 100644 index 0000000..42612ed --- /dev/null +++ b/gctest/gc.h @@ -0,0 +1,54 @@ +#pragma once + +#include +#include + +class ObjectVisitor; + +class Object +{ +public: + virtual ~Object() {} + virtual void VisitReferences(ObjectVisitor* visitor, void* state) = 0; +}; + +class ObjectVisitor +{ +public: + virtual ~ObjectVisitor() {} + + virtual void VisitReference(Object* from, Object* to, void* state) = 0; +}; + +class GarbageCollector : public ObjectVisitor +{ +public: + virtual void* Allocate(size_t size) = 0; + + virtual void SetRoot(Object* root) = 0; + + virtual void Shutdown() = 0; +}; + +class DestroyVisitor : public ObjectVisitor +{ +public: + virtual void Destroy(Object* o) + { + auto insert_result = m_Visited.insert(o); + if (insert_result.second) + { + o->VisitReferences(this, nullptr); + o->~Object(); + } + } + + void VisitReference(Object*, Object* to, void*) override + { + if (to) + { + Destroy(to); + } + } + std::unordered_set m_Visited; +}; diff --git a/gctest/gc_leak.cpp b/gctest/gc_leak.cpp new file mode 100644 index 0000000..2a1b493 --- /dev/null +++ b/gctest/gc_leak.cpp @@ -0,0 +1,25 @@ +#include + +#include "gc.h" + +class LeakGC : public GarbageCollector +{ + void* Allocate(size_t size) override { return ::operator new(size); } + + void SetRoot(Object* root) override { m_Root = root; } + + void VisitReference(Object*, Object*, void*) override {} + + void Shutdown() override + { + DestroyVisitor dv; + dv.Destroy(m_Root); + } + + Object* m_Root; +}; + +std::unique_ptr CreateGarbageCollector(int&, const char*[]) +{ + return std::unique_ptr(new LeakGC()); +} diff --git a/gctest/genie.lua b/gctest/genie.lua new file mode 100644 index 0000000..0165e7a --- /dev/null +++ b/gctest/genie.lua @@ -0,0 +1,44 @@ +solution 'gctest' + if _ACTION ~= 'jcdb' then + platforms { 'x32', 'x64' } + configurations {'Debug', 'Release'} + else + configurations {'Debug'} + end + flags { + 'FatalWarnings', + 'ExtraWarnings', + 'Cpp17', + 'Symbols', + } + defines { + '_SCL_SECURE_NO_WARNINGS', + 'MTR_ENABLED', + } + + + local root = './build/' + + configuration 'Debug' + targetdir(root .. 'bin/Debug') + objdir(root .. 'obj/Debug') + + configuration 'Release' + flags 'OptimizeSpeed' + targetdir(root .. 'bin/Release') + objdir(root .. 'obj/Release') + configuration '*' + + project 'test_bench' + kind 'StaticLib' + language 'C++' + files { + 'main.cpp', + } + + project 'leak_gc' + kind 'ConsoleApp' + language 'C++' + files 'gc_leak.cpp' + links 'test_bench' + diff --git a/gctest/main.cpp b/gctest/main.cpp new file mode 100644 index 0000000..06bb5a8 --- /dev/null +++ b/gctest/main.cpp @@ -0,0 +1,356 @@ +#include +#include +#include +#include +#include +#include +#include +#include "weighted_action.h" + +#include "minitrace/minitrace.c" +#include "minitrace/minitrace.h" + +#include "gc.h" + +typedef std::mt19937 RandomGenerator; + +std::unique_ptr CreateGarbageCollector(int& argc, + const char* argv[]); + +class RecycledObject : public Object +{ +public: + RecycledObject() { ++Alive; } + + ~RecycledObject() { --Alive; } + static std::atomic Alive; + typedef Object** Location; + + virtual Location GetLocation(RandomGenerator& random) = 0; + virtual size_t GetSize() const = 0; + unsigned m_Generation; +}; + +std::atomic RecycledObject::Alive = 0; + +class LeafObject : public RecycledObject +{ +public: + LeafObject(unsigned size) : m_Size(size) + { + std::fill(m_Extra, m_Extra + size, 0xab); + } + + ~LeafObject() {} + + void VisitReferences(ObjectVisitor*, void*) override {} + + RecycledObject::Location GetLocation(RandomGenerator&) override + { + return nullptr; + } + + size_t GetSize() const override { return sizeof(*this) + m_Size; } + +private: + unsigned m_Size; + uint8_t m_Extra[1]; +}; + +Object* CreateLeaf(GarbageCollector* gc, unsigned extraSize) +{ + auto memory = gc->Allocate(sizeof(LeafObject) + extraSize); + auto result = new (memory) LeafObject(extraSize); + return result; +} + +class ScannedObject : public RecycledObject +{ +public: + ScannedObject(unsigned children) : m_Size(children) + { + std::fill(m_Children, m_Children + m_Size, nullptr); + } + ~ScannedObject() {} + + void VisitReferences(ObjectVisitor* visitor, void* state) override + { + for (auto i = 0u; i < m_Size; ++i) + { + auto child = m_Children[i]; + if (child) + { + visitor->VisitReference(this, child, state); + } + } + } + + RecycledObject::Location GetLocation(RandomGenerator& generator) override + { + std::uniform_int_distribution dist(0, m_Size - 1); + return m_Children + dist(generator); + } + + size_t GetSize() const override + { + return sizeof(*this) + m_Size * sizeof(Object*); + } + +private: + unsigned m_Size; + Object* m_Children[1]; +}; + +Object* CreateScanned(GarbageCollector* gc, unsigned children) +{ + auto extraSize = children * sizeof(Object*); + auto memory = gc->Allocate(sizeof(ScannedObject) + extraSize); + auto result = new (memory) ScannedObject(children); + return result; +} + +RecycledObject::Location GetRandomLocation(Object* root, + RandomGenerator& generator) +{ + auto result = static_cast(root)->GetLocation(generator); + std::uniform_int_distribution dist(0, 99); + auto nonleaf = result; + while (result && *result) + { + if (dist(generator) < 5) + { + return result; + } + nonleaf = result; + result = static_cast(*result)->GetLocation(generator); + } + + return result ? result : nonleaf; +} + +template +struct ObjectFactory +{ + ObjectFactory(Factory f, + Dist dist, + RandomGenerator* g, + GarbageCollector* gc) + : m_Factory(f), m_Dist(dist), m_Generator(g), m_GC(gc) + { + } + + Object* operator()() const { return m_Factory(m_GC, m_Dist(*m_Generator)); } + + Factory m_Factory; + Dist m_Dist; + RandomGenerator* m_Generator; + GarbageCollector* m_GC; +}; + +template +ObjectFactory MakeFactory(Factory f, + Dist d, + RandomGenerator* g, + GarbageCollector* gc) +{ + return ObjectFactory(f, d, g, gc); +} + +template +struct SizeDistribution +{ + SizeDistribution(Dist dist, unsigned min, unsigned max) + : m_Dist(dist), m_Min(min), m_Max(max) + { + } + + template + unsigned operator()(G& g) const + { + auto r = m_Dist(g); + return (m_Min < r) ? (r < m_Max ? r : m_Max) : m_Min; + } + + mutable Dist m_Dist; + unsigned m_Min; + unsigned m_Max; +}; + +template +SizeDistribution MakeSizeDist(Dist d, unsigned min, unsigned max) +{ + return SizeDistribution(d, min, max); +} + +typedef WeightedActionTable CreateTable; + +void NewObject(RecycledObject* root, CreateTable& create, RandomGenerator& rg) +{ + auto location = GetRandomLocation(root, rg); + *location = create.RunRandomAction(); +} + +void NewTempObject(CreateTable& create) +{ + create.RunRandomAction(); +} + +void DeleteObject(RecycledObject* root, RandomGenerator& rg) +{ + auto location = GetRandomLocation(root, rg); + *location = nullptr; +} + +void CopyObject(RecycledObject* root, RandomGenerator& rg) +{ + auto from = GetRandomLocation(root, rg); + auto to = GetRandomLocation(root, rg); + *to = *from; +} + +void MoveObject(RecycledObject* root, RandomGenerator& rg) +{ + auto from = GetRandomLocation(root, rg); + auto to = GetRandomLocation(root, rg); + *to = *from; + *from = nullptr; +} + +void SwapObjects(RecycledObject* root, RandomGenerator& rg) +{ + auto a = GetRandomLocation(root, rg); + auto b = GetRandomLocation(root, rg); + std::swap(*a, *b); +} + +struct HeapStatsVisitor : ObjectVisitor +{ + void ComputeStats(Object* root) + { + auto recycled = static_cast(root); + m_CurrentGeneration = ++recycled->m_Generation; + m_Reachable = 1; + m_UsedMemory += recycled->GetSize(); + m_Depth = 1; + unsigned depth = 1; + root->VisitReferences(this, &depth); + } + void VisitReference(Object*, Object* to, void* state) override + { + auto recycled = static_cast(to); + if (recycled->m_Generation < m_CurrentGeneration) + { + ++m_Reachable; + m_UsedMemory += recycled->GetSize(); + recycled->m_Generation = m_CurrentGeneration; + auto depth = *static_cast(state); + ++depth; + if (depth > m_Depth) + { + m_Depth = depth; + } + to->VisitReferences(this, &depth); + } + } + size_t m_Reachable = 0; + unsigned m_Depth = 0; + unsigned m_CurrentGeneration = 0; + size_t m_UsedMemory = 0; +}; + +//extern std::atomic TotalMemory; + +int main(int argc, const char* argv[]) +{ + assert(argc > 0); + mtr_init((std::string(argv[0]) + ".json").c_str()); + // MTR_META_PROCESS_NAME(argv[0]); + MTR_META_THREAD_NAME("Mutator thread"); + + RandomGenerator rg; + if (argc > 1) + { + rg.seed(std::atoi(argv[1])); + } + auto gc = CreateGarbageCollector(argc, argv); + + CreateTable create(&rg); + + std::normal_distribution u_small(64, 16); + std::normal_distribution u_medium(512, 128); + std::normal_distribution u_large(4096, 1024); + + auto size_small = MakeSizeDist(u_small, 16, 128); + auto size_medium = MakeSizeDist(u_medium, 128, 1024); + auto size_large = MakeSizeDist(u_large, 1024, 8192); + + create.AddAction(MakeFactory(CreateLeaf, size_small, &rg, gc.get()), 20); + create.AddAction(MakeFactory(CreateLeaf, size_medium, &rg, gc.get()), 30); + create.AddAction(MakeFactory(CreateLeaf, size_large, &rg, gc.get()), 20); + + create.AddAction(MakeFactory(CreateScanned, size_small, &rg, gc.get()), 20); + create.AddAction(MakeFactory(CreateScanned, size_medium, &rg, gc.get()), + 30); + create.AddAction(MakeFactory(CreateScanned, size_large, &rg, gc.get()), 20); + + auto root = static_cast(CreateScanned(gc.get(), 1000)); + gc->SetRoot(root); + + WeightedActionTable operations(&rg); + + operations.AddAction( + [&create, &rg, root]() { NewObject(root, create, rg); }, 30); + + operations.AddAction([&create]() { NewTempObject(create); }, 40); + + operations.AddAction([root, &rg]() { DeleteObject(root, rg); }, 5); + + operations.AddAction([root, &rg]() { CopyObject(root, rg); }, 20); + + operations.AddAction([root, &rg]() { MoveObject(root, rg); }, 10); + + operations.AddAction([root, &rg]() { SwapObjects(root, rg); }, 20); + + auto initial_count = 50000u; + auto loops = 100u; + auto operations_count = 5000u; + + { + MTR_SCOPE("Mutator", "Initialize Heap"); + for (auto i = 0u; i < initial_count; ++i) + { + auto location = GetRandomLocation(root, rg); + *location = create.RunRandomAction(); + } + } + + for (auto l = 0u; l < loops; ++l) + { + { + MTR_SCOPE_I("Mutator", "Step", "loop", l); + for (auto o = 0u; o < operations_count; ++o) + { + operations.RunRandomAction(); + } + } + MTR_SCOPE_I("Mutator", "Walk Heap", "loop", l); + HeapStatsVisitor stats; + stats.ComputeStats(root); + MTR_COUNTER("Heap", "Reachable", int(stats.m_Reachable)); + MTR_COUNTER("Heap", "Living", int(RecycledObject::Alive)); + MTR_COUNTER("Heap", "Depth", int(stats.m_Depth)); + //MTR_COUNTER("Heap", "Total KB", int(TotalMemory / 1024)); + MTR_COUNTER("Heap", "Useful KB", int(stats.m_UsedMemory / 1024)); + } + + gc->Shutdown(); + + if (RecycledObject::Alive) + { + std::fprintf(stderr, "%lld objects leaked\n", + (size_t)RecycledObject::Alive); + } + + mtr_shutdown(); + return 0; +} diff --git a/gctest/weighted_action.h b/gctest/weighted_action.h new file mode 100644 index 0000000..4bcdd6f --- /dev/null +++ b/gctest/weighted_action.h @@ -0,0 +1,33 @@ +#pragma once +#include +#include +#include + +template +class WeightedActionTable +{ +public: + WeightedActionTable(Generator* generator) : m_Generator(generator) {} + + typedef std::function ActionCallback; + + void AddAction(ActionCallback action, unsigned weight) + { + m_Actions.emplace_back(action); + m_Weights.emplace_back(weight); + m_Distribution = + std::discrete_distribution(m_Weights.begin(), m_Weights.end()); + } + + Result RunRandomAction() + { + auto random = m_Distribution(*m_Generator); + return m_Actions[random](); + } + +private: + std::vector m_Actions; + std::vector m_Weights; + Generator* m_Generator; + std::discrete_distribution m_Distribution; +}; -- cgit v1.3.1-26-gb76a