http://coliru.stacked-crooked.com/a/f24b9c8c57ba82cf

gc.cpp

#include <boost/intrusive_ptr.hpp>
#include <cassert>
#include <cstddef>
#include <map>
#include <memory>
#include <mutex>
#include <shared_mutex>
#include <unordered_map>
#include <unordered_set>

template<typename SharedMutex>
class unique_lock_prioritizing_shared_mutex {
public:
    void lock() {
        std::lock_guard<decltype(control)> lock(control);
        mutex.lock();
    }

    void unlock() {
        mutex.unlock();
    }

    bool try_lock() {
        return mutex.try_lock();
    }

    void lock_shared() {
        std::lock_guard<decltype(control)> lock(control);
        mutex.lock_shared();
    }

    bool try_lock_shared() {
        return mutex.try_lock_shared();
    }

    void unlock_shared() {
        mutex.unlock_shared();
    }

private:
    std::mutex control;
    SharedMutex mutex;
};

class gc;
struct object;

using gc_ptr = boost::intrusive_ptr<object>;

struct object {
public:
    object* read_field(std::size_t index);
    void write_field(std::size_t index, object* value);

    object* read_field_atomically(std::size_t index);
    void write_field_atomically(std::size_t index, object* value);

    void* auxiliary_data();

private:
    gc* gc;
    std::size_t field_count;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc99-extensions"
    object* fields[];
#pragma GCC diagnostic pop

    friend class gc;

    friend void intrusive_ptr_add_ref(object* ptr);
    friend void intrusive_ptr_release(object* ptr);
};

class root_provider {
public:
    virtual ~root_provider();
    virtual std::unordered_set<object*> roots() const = 0;
};

struct gc_stats {
    std::size_t object_count;
    std::size_t root_count;
    std::size_t unique_root_count;
};

class gc {
public:
    object* allocate(std::size_t field_count, std::size_t auxiliary_data_size);

    std::shared_lock<unique_lock_prioritizing_shared_mutex<std::shared_timed_mutex>> allow_mutations();

    void collect();

    void register_root_provider(root_provider const& rp);
    void unregister_root_provider(root_provider const& rp);

    gc_stats stats() const;

private:
    struct operator_delete_delete {
        void operator()(void* ptr) const;
    };

    void enroot(object* ptr);
    void deroot(object* ptr);

    unique_lock_prioritizing_shared_mutex<std::shared_timed_mutex> stop_the_world_mutex;

    mutable std::mutex internals_mutex;

    std::map<object*, std::unique_ptr<object, operator_delete_delete>> objects;
    std::unordered_map<object*, std::size_t> roots;
    std::unordered_set<root_provider const*> root_providers;

    friend void intrusive_ptr_add_ref(object* ptr);
    friend void intrusive_ptr_release(object* ptr);
};

object* object::read_field(std::size_t index) {
    assert(index < field_count);
    return fields[index];
}

void object::write_field(std::size_t index, object* value) {
    assert(index < field_count);
    fields[index] = value;
}

object* object::read_field_atomically(std::size_t index) {
    assert(index < field_count);
    return __atomic_load_n(&fields[index], __ATOMIC_SEQ_CST);
}

void object::write_field_atomically(std::size_t index, object* value) {
    assert(index < field_count);
    __atomic_store_n(&fields[index], value, __ATOMIC_SEQ_CST);
}

void* object::auxiliary_data() {
    return static_cast<void*>(fields + field_count);
}

root_provider::~root_provider() = default;

object* gc::allocate(std::size_t field_count, std::size_t auxiliary_data_size) {
    auto ptr = static_cast<object*>(operator new(sizeof(object) + sizeof(void*) * field_count + auxiliary_data_size));
    ptr->gc = this;
    ptr->field_count = field_count;
    {
        std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);
        objects.emplace(ptr, std::unique_ptr<object, operator_delete_delete>(ptr));
    }
    return ptr;
}

std::shared_lock<unique_lock_prioritizing_shared_mutex<std::shared_timed_mutex>> gc::allow_mutations() {
    return std::shared_lock<decltype(stop_the_world_mutex)>(stop_the_world_mutex);
}

void gc::collect() {
    std::unique_lock<decltype(stop_the_world_mutex)> stop_the_world_lock(stop_the_world_mutex);
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);

    std::unordered_set<object*> reachable_objects;

    auto mark = [&] (auto self, object* ptr) {
        if (reachable_objects.count(ptr)) {
            return;
        }
        reachable_objects.insert(ptr);
        for (auto it = ptr->fields; it != ptr->fields + ptr->field_count; ++it) {
            self(self, *it);
        }
    };
    for (auto root : roots) {
        mark(mark, root.first);
    }
    for (auto* root_provider : root_providers) {
        for (auto root : root_provider->roots()) {
            mark(mark, root);
        }
    }

    auto objects_begin = objects.begin();
    auto objects_end = objects.end();
    for (auto it = objects_begin; it != objects_end; ++it) {
        if (!reachable_objects.count(it->first)) {
            objects.erase(it);
        }
    }
}

void gc::register_root_provider(root_provider const& rp) {
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);
    root_providers.insert(&rp);
}

void gc::unregister_root_provider(root_provider const& rp) {
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);
    root_providers.erase(&rp);
}

gc_stats gc::stats() const {
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);

    gc_stats stats;
    stats.object_count = objects.size();
    stats.root_count = 0;
    for (auto root : roots) {
        stats.root_count += root.second;
    }
    stats.unique_root_count = roots.size();
    return stats;
}

void gc::operator_delete_delete::operator()(void* ptr) const {
    operator delete(ptr);
}

void gc::enroot(object* ptr) {
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);
    ++roots[ptr];
}

void gc::deroot(object* ptr) {
    std::lock_guard<decltype(internals_mutex)> internals_lock(internals_mutex);
    --roots[ptr];
    if (roots.at(ptr) == 0) {
        roots.erase(ptr);
    }
}

void intrusive_ptr_add_ref(object* ptr) {
    ptr->gc->enroot(ptr);
}

void intrusive_ptr_release(object* ptr) {
    ptr->gc->deroot(ptr);
}

#include <cstdlib>
#include <iostream>

std::ostream& operator<<(std::ostream& stream, gc_stats const& stats) {
    stream << "objects: " << stats.object_count << "; ";
    stream << "roots: " << stats.root_count << "; ";
    stream << "unique roots: " << stats.unique_root_count;
    return stream;
}

int main() {
    gc gc;

    gc_ptr question(gc.allocate(0, sizeof(char const*)));
    *static_cast<char const**>(question->auxiliary_data()) = "universe";

    std::cout << "after question creation: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    gc_ptr answer(gc.allocate(0, sizeof(int)));
    *static_cast<int*>(answer->auxiliary_data()) = 42;

    std::cout << "after answer creation: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    gc_ptr question_and_answer(gc.allocate(2, 0));
    question_and_answer->write_field_atomically(0, question.get());
    question_and_answer->write_field(1, answer.get());

    std::cout << "after question_and_answer creation: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    question.~gc_ptr();

    std::cout << "after question destruction: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    answer.~gc_ptr();

    std::cout << "after answer destruction: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    question_and_answer.~gc_ptr();

    std::cout << "after question_and_answer destruction: " << gc.stats() << '\n';

    gc.collect();

    std::cout << "after collection: " << gc.stats() << '\n';

    std::cout.flush();

    std::exit(0);
}