gcc.cpp

#pragma once

#include <vector>
#include <assert.h>
#include <memory>
#include <algorithm>
#include <stdio.h>
#include <conio.h>

#include "gtest.h"


namespace GC {

using namespace std;

// GC_Entity is a garbage-collectable object that
// can reference other objects

struct Entity;
struct ClientObject {};
struct ClientStruct {};

typedef void (*Finalizer)(ClientStruct *);

// offset - pointer offset
// tInfo - if not nil then it's 
struct OffsetInfo {
    int offset;
    struct TypeInfo const *tInfo;
};

struct TypeInfoArgs {
    int size;
    Finalizer finalizer;
    int offsetCount;
    OffsetInfo *offsets;
};

// All info GC needed to manage object's lifetime: 
// - finalizer method pointer
// - object size in bytes
// - array of offsets
struct TypeInfo
{
private:
    int _size;
    Finalizer _finalizer;
    int _offsetCount;
    int * _pointerOffsets;

    TypeInfo() {}
    TypeInfo(const TypeInfo&);
    TypeInfo& operator = (const TypeInfo&);

    static TypeInfo * _allocPointerInfo() {
        OffsetInfo offset = {0, nullptr};
        TypeInfoArgs args = {sizeof(void*), nullptr, 1, &offset};
        return alloc(args);
    }

    // Extracts array of offsets from TypeInfoArgs
    static vector<int> offsetsArray(const TypeInfoArgs& args) {
        vector<int> offsets;
        for (int i = 0; i < args.offsetCount; ++i) {
            const OffsetInfo& currInfo = args.offsets[i];

            if (currInfo.tInfo) {
                for (int ofsIdx = 0; ofsIdx < currInfo.tInfo->offsetCount(); ++ofsIdx) {
                    offsets.push_back(currInfo.offset + currInfo.tInfo->offsetAt(ofsIdx));
                }
            } else { // special case for pointer type info initialization
                offsets.push_back(currInfo.offset);
            }
        }

        int prevOffset = -1;
        for each (int offset in offsets) {
            assert(prevOffset < offset);
            prevOffset = offset;
        }

        return offsets;
    }

public:

    int offsetAt(int offsetIdx) const {
        assert(offsetIdx < _offsetCount);
        return _pointerOffsets[offsetIdx];
    }
    int offsetCount() const { return _offsetCount;}
    Finalizer finalizer() const { return _finalizer;}
    int size() const { return _size;}
    bool isPointer() const { return this == TypeInfo::pointerInfo();}

    ClientObject * pointerAtIndexOfStruct(const ClientStruct *structure, int pointerIdx) const {
        assert(structure);
        assert(pointerIdx < _offsetCount);
        return *(ClientObject **) ((char *)structure + _pointerOffsets[pointerIdx]);
    }

     static TypeInfo * pointerInfo() {
         static TypeInfo *typeInfo = _allocPointerInfo();
         return typeInfo;
     }

    static TypeInfo * alloc(const TypeInfoArgs& args) {
        const vector<int>& offsets = offsetsArray(args);

        TypeInfo *info = (TypeInfo*)operator new(sizeof(TypeInfo) + offsets.size() * sizeof(int));
        info->_size = args.size;
        info->_finalizer = args.finalizer;
        info->_offsetCount = args.offsetCount;
        info->_pointerOffsets = (int *) ((char *)info + sizeof(TypeInfo));

        memcpy(info->_pointerOffsets, &offsets[0], offsets.size() * sizeof(int));
        return info;
    }

    static void free(TypeInfo *typeInfo) {
        delete typeInfo;
    }
};

// Entity is garbage-collectable object that allocated dynamically
// It's an array of structures of same type
struct Entity
{
    bool _reachable;
private:
    const TypeInfo * const _type;

    void * const _dbg_Code;
    const int _structCount;

protected:

    void validate() const { assert(this == _dbg_Code); }

    explicit Entity(const TypeInfo *typeInfo, int structCount)
        : _type(typeInfo),
        _reachable(false),
        _dbg_Code(this),
        _structCount(structCount)
    {}

    Entity();
    ~Entity() {}

    ClientStruct * structAtIndex(int index) const {
        assert(index < _structCount);
        return (ClientStruct *) ((char *)memory() + index * _type->size());
    }

public:

    ClientObject * pointerAtIndex(int pointerIdx) const {

        if (pointerIdx >= _structCount * _type->offsetCount()) {
            return nullptr;
        }

        int elemIdx = pointerIdx / _type->offsetCount();
        int ptrIdx = pointerIdx % _type->offsetCount();

        return _type->pointerAtIndexOfStruct(structAtIndex(elemIdx), ptrIdx);
    }

    static Entity * alloc(const TypeInfo *typeInfo, int count) {
        size_t memorySize = sizeof(Entity) + count * typeInfo->size();
        void *memory = operator new(memorySize);
        memset(memory, 0, memorySize);
        Entity *entity = new (memory) Entity(typeInfo, count);
        return entity;
    }

    static void dealloc(Entity *entity) {
        if (!entity) {
            return;
        }

        entity->validate();

        Finalizer finalizer = entity->type().finalizer();
        if (finalizer != nullptr) {
            for (int idx = 0; idx < entity->_structCount; ++idx) {
                (*finalizer) (entity->structAtIndex(idx));        
            }
        }

        delete entity;
    }

    static Entity * fromMemory(ClientObject *memory) {
        if (memory) {
            Entity *entity = (Entity *) ((char *)memory - sizeof(Entity));
            entity->validate();
            return entity;
        }

        return nullptr;
    }

    const TypeInfo & type() const { return *_type;}
    ClientObject * memory() { return (ClientObject *) ((char *)this + sizeof(Entity));}
    const ClientObject * memory() const { return const_cast<Entity *>(this)->memory();}

    struct EntityReferenceIterator pointerIterator() const;
};

struct EntityReferenceIterator
{
private:
    const Entity &_entity;
    int _offset;

public:

    explicit EntityReferenceIterator(const Entity &entity)
        : _entity(entity), _offset(0)
    {}

    Entity * reference() const {
        return Entity::fromMemory(_entity.pointerAtIndex(_offset));
    }

    bool next() {
        ++_offset;
        return true;
    }
};

EntityReferenceIterator Entity::pointerIterator() const {
    return EntityReferenceIterator(*this);
}

class Environment
{
    vector<Entity *> _entities;
    vector<Entity *> _roots;

public:

    size_t entitiesCount() const { return _entities.size();}

    Entity * allocEntity(TypeInfo *typeInfo) {
        Entity *entity = Entity::alloc(typeInfo, 1);
        _entities.push_back(entity);
        return entity;
    }

    Entity * allocEntityRoot(TypeInfo *typeInfo) {
        Entity *entity = allocEntity(typeInfo);
        _roots.push_back(entity);
        return entity;
    }

    template<typename T>
    T * allocEntity() {
        return (T *)allocEntity(T::typeInfo())->memory();
    }

    template<typename T>
    T * allocEntityRoot() {
        return (T *)allocEntityRoot(T::typeInfo())->memory();
    }

    void collectGarbage() {
        determineReachability();

        _entities.erase(
            std::remove_if(_entities.begin(),_entities.end(),[](Entity *entity) {
                bool notReachable = !entity->_reachable;
                if (notReachable) {
                    Entity::dealloc(entity);
                }
                return notReachable;
            }),
            _entities.end()
        );
        
    }

    void determineReachability() const
    {
        for each (auto entity in _entities) {
            entity->_reachable = false;
        }

        vector<Entity *> entities = _roots;
        vector<Entity *> entitiesTemp;

        do  {
            for each (Entity *entity in entities) {
                if (!entity->_reachable) {
                    entity->_reachable = true;

                    auto itr = entity->pointerIterator();
                    while (Entity *referenced = itr.reference()) {
                        // TODO: what to do if referenced object is already reachable?
                        if (!referenced->_reachable) {
                            entitiesTemp.push_back(referenced);
                        }
                        itr.next();
                    }
                }
            }

            entities.clear();
            entities.swap(entitiesTemp);

        } while (!entities.empty());
    }

};

}

tests.cpp

#include "gc_impl.hpp"

#include <type_traits>
#include <assert.h>

#define countOf(array)  (sizeof(array)/sizeof(array[0]))

using namespace GC;

struct PtrAndType
{
    const void *ptr;
    TypeInfo *type;
};

template<class T>
struct GC_Traits {
    static TypeInfo* typeInfo() {
        return T::typeInfo();
    }
};

template<class T>
struct GC_Traits<T *> {
    static TypeInfo* typeInfo() {
        return TypeInfo::pointerInfo();
    }
};

template<class T> inline OffsetInfo fld(const T& field) {
    OffsetInfo info = {(int)&field, GC_Traits<T>::typeInfo()};
    return info;
}

template<class T, class Base> inline OffsetInfo baseOfs() {
    static_assert(std::is_base_of<Base, T>::value, "");
    int offset = (int)static_cast<Base*>((T *)0x01) - 0x01;
    OffsetInfo info = {offset, Base::typeInfo()};
    return info;
}

#define DEFINE_OBJ_INFO(this_type, ...) \
    ::GC::TypeInfo * createTypeInfo() const { \
        ::GC::OffsetInfo offsets[] = {__VA_ARGS__}; \
        ::GC::TypeInfoArgs args = {sizeof(this_type), (::GC::Finalizer)&this_type::finalizer, countOf(offsets), offsets}; \
        return ::GC::TypeInfo::alloc(args); \
    }\
    \
    static ::GC::TypeInfo * typeInfo() {\
        static ::GC::TypeInfo *nodeTypeInfo = ((this_type *)nullptr)->createTypeInfo();\
        return nodeTypeInfo;\
    }\
    \
    static void finalizer(void *self) { \
        printf(#this_type " finalizer at 0x%x\n", self); \
        ((this_type *)self)->~this_type();\
    }

struct Node
{
    int value;
    Node *next;

    DEFINE_OBJ_INFO(Node,
        fld(next));

    static void NodeFIn(Node *node) {
        printf("Node 0x%x finalizer\n", node);
    }
};


TEST(TypeInfo, pointer_type_info)
{
    const TypeInfo *tinfo = TypeInfo::pointerInfo();
    EXPECT_TRUE(tinfo != nullptr);
    EXPECT_TRUE(tinfo->offsetCount() == 1);
    EXPECT_TRUE(tinfo->size() == sizeof(void*));
    EXPECT_TRUE(tinfo->finalizer() == nullptr);
}

TEST(TypeInfo, test)
{
    {
        TypeInfoArgs args;
        args.finalizer = (Finalizer)0x1;
        args.offsetCount = 2;
        OffsetInfo offsets[2] = {0, TypeInfo::pointerInfo(), 2, TypeInfo::pointerInfo()};
        args.offsets = offsets;
        std::auto_ptr<TypeInfo> info( TypeInfo::alloc(args) );

        EXPECT_TRUE(info->finalizer() == args.finalizer);
        EXPECT_TRUE(info->size() == args.size);
        EXPECT_TRUE(info->offsetCount() == args.offsetCount);
    }

    Node node;
    node.next = &node;
    ClientObject *nodePtr = Node::typeInfo()->pointerAtIndexOfStruct((ClientStruct *)&node, 0);
    EXPECT_TRUE((ClientObject *)node.next == nodePtr);
}

TEST(TypeInfo, macro_test_with_nested_types)
{
    struct MyStruct {
        Node next;
        Node prev;
        void *pointer;

        DEFINE_OBJ_INFO(MyStruct,
            fld(next),
            fld(prev),
            fld(pointer));
    };

    TypeInfo *info = MyStruct::typeInfo();

    EXPECT_TRUE(info->offsetCount() == 3);
    EXPECT_TRUE(info->size() == sizeof(MyStruct));
    EXPECT_TRUE(info->offsetAt(0) == 4);
    EXPECT_TRUE(info->offsetAt(1) == 12);
}

TEST(TypeInfo, macro_test_with_nested_types_and_derived)
{
    struct MyStruct : Node {
        int value;
        Node prev;
        void *pointer;

        DEFINE_OBJ_INFO(MyStruct,
            baseOfs<MyStruct, Node>(),
            fld(prev),
            fld(pointer));
    };

    TypeInfo *info = MyStruct::typeInfo();

    EXPECT_TRUE(info->offsetCount() == 3);
    EXPECT_TRUE(info->size() == sizeof(MyStruct));
    EXPECT_TRUE(info->offsetAt(0) == 4);
    //EXPECT_TRUE(info->offsetAt(1) == 12);
}


TEST(Entity, from_memory_cast)
{
    Entity *entity = Entity::alloc(Node::typeInfo(), 1);

    EXPECT_TRUE(entity == Entity::fromMemory(entity->memory()));

    Entity::dealloc(entity);
}

TEST(Environment, gc_simple_references)
{
    Environment environment;

    Node *node0 = environment.allocEntityRoot<Node>();
    Node *node1 = environment.allocEntity<Node>();
    Node *node2 = environment.allocEntity<Node>();
    Node *node3 = environment.allocEntity<Node>();

    node0->next = node1;

    EXPECT_TRUE(environment.entitiesCount() == 4);

    environment.collectGarbage();

    EXPECT_TRUE(environment.entitiesCount() == 2);
}


TEST(Environment, gc_circular_references)
{
    Environment environment;

    Node *node0 = environment.allocEntityRoot<Node>();
    Node *node1 = environment.allocEntity<Node>();
    Node *node2 = environment.allocEntity<Node>();
    Node *node3 = environment.allocEntity<Node>();

    node0->next = node1;
    node1->next = node0;

    // circular. reference
    node2->next = node3;
    node3->next = node2;

    EXPECT_TRUE(environment.entitiesCount() == 4);

    environment.collectGarbage();

    EXPECT_TRUE(environment.entitiesCount() == 2);
}