Пример GC для С++
От: NikeByNike Россия  
Дата: 18.06.08 19:08
Оценка: 26 (2)
Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.

Задача

Хочется сделать GC для С++ и показать, что он вполне возможен. Вопрос: "а почему же GC не используется в С++?" за пределами данной темы.

Задача 1: свести оверхед по синтаксису к минимуму
Хочется писать нормально, без специальных наследований и функций, т.е. использовать обычные классы и встроенные типы, со стандартизированной аллокацией памяти, без необходимости её индивидуальной отчистки.

Задача 2: свести оверхед по перфомансу к минимуму
Хотелось бы, чтобы всё работало более-менее быстро и чётко. Т.е. GC не должен пробегать всю память в поисках всего, а проверть только то что нужно.


Вводная

Буду использовать следующие названия:
P<Type> — обозначение gc указателя. Пример:
P<int>, P<CMySuperClass>

gc_array<Type> — обозначение gc массива, аналогичного стандартному сишному. Пример:
gc_array<int>, gc_array<Node>

gc_new<Type> — функция аллокации gc блока. Пример:
P<CMySuperClass> super_object = gc_new<CMySuperClass>( param1, param2, param3 );

gc_new_array<Type> — функция аллокации массива. Пример:
gc_array<P<Node> > node = gc_new_array<P<Node> >( 10 ); node[1] = gc_new<Node>();

gc_this, GC_NULL — думаю понятно.
Эти названия не преследуют никаких религиозных целей, просто первые что пришли в голову.
Деструкторы объектов превращаются в финализаторы. Следовательно, внутри GC-объектов можно хранить данные аллокированные обычным путём.
Пример который должен корректно работать:
#include "rtl_gc.h"

struct A {
    float m_f;

    virtual ~A() {}
};

struct B : public A {
    int     m_i;
    P<A>    m_a;
    P<B>    m_b;
};

struct C : public A {
    std::vector<int> vec;
};

P<A> MakeA()
{
    P<C> c = gc_new<C>();
    c->vec.resize(10);
    return c;
};

void Test()
{
    P<A> a1;
    {
        P<B> b1 = gc_new<B>();
        b1->m_a = MakeA();
        b1->m_b = b1;

        a1 = b1->m_b;
    }
    Pool::Instance().GC();
    // Всё что мы создали - ещё живо
    a1 = GC_NULL;
    // Недоступно, но ещё живо
    Pool::Instance().GC();
    // Всё убито
}



Ограничения

Важная особенность системы на данный момент:
GC-указатели могут храниться только в статической памяти, в стеке и в gc-объектах
Т.е. пока нельзя делать так:
std::vector<P<Node> >

или так:
void Func()
{
    static P<Node> node;
}

После некоторых размышлений решил, что первое ограничение вполне допустимо — так как оно спасает от возникновения циклических ссылок, а следовательно от утечек памяти. Второе ограничение, в будущем, можно разрешить.
Ещё важное, на данный момент, ограничение — указатель всегда должен указывать на начало блока памяти выделенной для объекта. Т.е. ситуации со сложным наследованием, указатели на агрегированные мемберы объектов или элементы массивов — недопустимы. При необходимости эту фичу можно реализовать (хотя такой фичи нет под явой и шарпом).
Так же:
  • О стиле оформления кода пока совершенно не заботился. Многие мемберы почём зря в паблик секции и т.п. Пока это не важно.
  • Так же целенаправленно не заботился о низкоуровневой оптимизации, в частности о работе внутренних контейнеров.
  • Совершенно не заботился об оптимальности алгоритма отчиски и выделения памяти, корректной работе с потоками и о множестве других важных вещей, которые счёл второстепенными на данном этапе, но решаемыми в будущем.


    Основа

    Для предоставления аллокатору всей необходимой информации об объекте был использован один старый вспомогательный класс:
    class variant_type
    {
    public:
        typedef void (*TFCopyConstructor)(void* /*dst*/, const void* /*src*/);
        typedef void (*TFDestructor)(void* obj);
    
        typedef std::vector<std::pair<ptrdiff_t, const variant_type*> > TSubPointers;
    
        const char*         m_Name;
        size_t              m_Size;
        size_t              m_AlignSize;
        TFCopyConstructor   m_CopyCnstr;
        TFDestructor        m_Destructor;
    
        bool                m_Initialized;
        TSubPointers        m_Pointers;
    
        template<class T>
        static variant_type* type_id()
        {
            static variant_type static_type( *(T const*)0 );
            return &static_type;
        }
    private:
        ...
    };

    Надеюсь, тут всё понятно из контекста.
    Все мемберы кроме m_Pointers заполняются в конструкторе данного класса который вызывается внутри функции variant_type::type_id. Примеры допустимого использования:
    const variant_type* vt = variant_type::type_id<CMySuperClass>();
    std::cout << vt->m_Name << " " << vt->m_Size;
    
    CMySuperClass my_super_class;
    byte* buf = new byte[vt->m_AlignSize];
    vt->m_CopyCnstr( buf, &my_super_class );
    CMySuperClass* object = reinterpret_cast<CMySuperClass*>( buf );
    AnyUse( object );
    vt->m_Destructor( buf );
    delete[] buf;


    m_Pointers (которых не было раньше) — инициализируются внутри функций аллокации gc памяти только один раз, контролируется это флажком m_Initialized. m_Pointers хранит смещение субуказателя от начала блока памяти объекта. Т.е. для класса:
    class Foo
    {
        P<int> i;
        int fake;
        P<CMySuperClass> m;
    };

    значение type_id<Foo>->m_Pointers, после первого вызова gc_new<Foo>, будет примерно такое: [0, 8]
    Данный класс поможет нам:
    1. обходить граф объектов без оверхеда по скорости.
    2. перемещать объекты из одного куска памяти, в другой. Естественно у них должны быть корректные копирующие конструкторы.
    3. корректно уничтожать объект в ходе отчистки мусора.
    Конечному пользователю знать про данный класс не обязательно, хотя его можно выгодно использовать в variant'e, для которого он и был изначально разработан.


    Общее описание пула памяти

    class Pool — синглетон, содержит следующие функции:
  • template<class T> void ProcessPointer(void** ppointer);
    Функция проверяет, что указатель попадает в аллокируемый блок памяти, а следовательно, что он является мембером нового объекта. Иначе — он считается корневым и попадает в стек корневых указателей.
  • template<class T> void FreePointer(void** ppointer);
    Функция проверяет — является ли данный указатель корневым. Если он корневой — его удаляют из стека.
  • void GC();
    Чистка памяти. Обходится граф объектов, помечаются используемые, после чего используемые копируются в новый блок памяти, а неиспользуемые — удаляются. Все существующие указатели правятся автоматически.
  • static Pool& Instance();
    Возвращает глобальный пул.
  • template<class T, class Arg1, ...> P<T> gc_new(const Arg1& arg1, ...)
    Функции аллокации памяти.

    Пул содержит следующие данные:
  • Блок памяти в котором распределяются все объекты. Эта часть пока очень примитивна — выделяется мегабайт в std::vector. В памяти последовательно располагаются блоки под объект(ы), каждый блок содержит шапку: variant_type* и unsigned int. В первых 30 битах инта хранится количество объектов в блоке памяти (для массивов), в 2 битах — флаги. Флаг пока один — Marked, отметка о том, что до данного блока можно дойти от корневых указателей. Выглядит всё как-то так:
    [variant_type*][30 бит — count of objects][2 бита — флаги][(variant_type::m_Size * Count + 3) & (~3) байт под объект(ы)]][следующий объект]
  • Стек корневых указателей. Предполагается, что все корневые указатели выделяются в глобальной памяти или на стеке — а следовательно создаются и уничтожаются в режиме FIFO (c одним исключением).
  • Стек конструкторов. После выделения памяти, но перед созданием объекта — в этот стек добавляется описание нового блока. Это нужно для работы следующего псевдокода:
    - Для каждого конструктора объекта-указателя:
    -   Если я пересекаюсь с верхним элементом стека конструкторов то:
    -     Следовательно я мембер нового объекта и должен попытаються
    отметиться в соответствующем variant_type если флажок m_Initialized == false
    -   Иначе:
    -     Я корневой указатель и должен добавиться в стек корневых указателей.
    После конструирования объекта описание блока удаляется из стека.


    Указатель

    Очень простой класс, регистрирующий и разрегистрирующий объект-указатель в пуле и лишающий возможности совершать над указателем арифметические действия. gc_array — сделан строго аналогично, разве что операторы * и -> не определяет, но взамен есть оператор [].
    template<class T>
    class P
    {
    public:
        P()             { Pool::Instance().ProcessPointer( (void**)this ); } 
        P(const P<T>& ) { Pool::Instance().ProcessPointer( (void**)this ); }
        ~P()            { Pool::Instance().FreePointer( (void**)this ); }
    
        template<class U>
        P(const P<U>& ) { Pool::Instance().ProcessPointer( (void**)this ); }
    
        T* operator->() { return p; }
    
       // функции сравнения, разыменования, работы с GC_NULL и т.п.
       ...
    
    private:
        T* p;
    };



    gc_new

    Работает примерно так:
    template<class T>
    P<T> Pool::gc_new()
    {
        // Получаем рантайм тип.
        variant_type* vt = variant_type::type_id<T>();
        // Получаем блок памяти для объекта
        // Очень дешёвая операция, просто увелчиваем счётчик размера выделенной памяти на (sizeof(TMemBlock) + sizeof(T))
        P<T> p; p.p = (T*)GetMemory( vt );
        // проверяем иницилизированность рантайм типа и если нет - начинаем инициализацию:
        if ( !vt->m_Initialized )
            vt->m_Pointers.resize( 0 );
        // добавляем в стек конструкторов информацию об обрабатываемом блоке памяти:
        m_builder.push_back( Pool::TAllocatingBlock( (byte*)p.p, vt) );
        // конструируем объект
        new (p.p) T;
        // все указатели-мемберы уже отмечены
        m_builder.pop_back();
        // и рантаймтип в любом случае уже инициализирован
        vt->m_Initialized = true;
        return p;
    }
    
    P<T> gc_new()
    {
        return Pool::Instance().gc_new<T>();
    }

    Остальные gc_new и gc_new_array сделаны по аналогии.


    Чистка памяти

    После работы с объектами у нас, в едином блоке памяти, существует сформированный граф объектов и список корневых указателей. Алгоритм отчитки очень прост:

    void Pool::GC()
    {
        //Рекурсивно, начиная с корневых указателей, обходим доступный граф и помечаем заголовки блоков как доступные.
        MarkUsedBlocks();
    
        // Выделяем новый кусок памяти.
        std::vector<uint8_t> window( m_buffer.size() );
    
        // Последовательно проходим по всем блокам.
        // Если они отмечены - копируем соответствующий объект с помощью variant_type::m_CopyCnstr
        // в новый блок, и в заголовок старого блока (вместо variant_type) происываем diffptr_t между новым и старым блоком.
        // Если блок не был отмечен - он удаляется с помощью функции: variant_type::m_Destructor
        MoveUsedBlocks( &window[0], m_allocated );
    
        // делаем актуальным новый блок
        window.swap( m_buffer );
    
        // Последовательно проходим по всем блокам и обновляем им указатели используя diffptr_t записанный в старой памяти
        UpdatePointersInNewBlocks( &m_buffer[0], &m_buffer[0] + m_allocated );
    
        // Проходим по всем корневым указателям и обновляем их тоже
        UpdateRootPointers();


    В качестве проверки минимальной работоспособности я написал простой аналог stl::list — gc_list. Его можно посмотреть в примере.
    В примере же продемонстрировны базовые возможности.


    Немного о проблемах

  • Нельзя создавать указатели указывающие не на начало блока.
    Данная возможность по понятным причинам не предусмотренна ни в шарпе ни в яве. В данной системе её тоже хотелось бы избежать, но если очень нужно в класс-указатель можно внест ещё один мембер — diffptr_t, который будет хранить разницу между данным указателем и началом блока объекта. Это чревато увеличением размера указателя в 2 раза.
  • Нельзя создавать корневые указатели в качестве статических объектов в функциях.
    Пока решение видится только путём введения ещё одного специализированного типа-указателя, например: StaticP. Это плохое решение. Надо думать.
  • Метод аллокации и отчитки нужно разрабатывать, то что существует сейчас — исключительно в первородном состоянии.
  • Пока аллокатор не работает в рамках нескольких модулей (exe и dll)
    Эта проблема решается сравнительно легко — путём введения кроссмодульного синглетона который отвечает за синхронизацию внутримодульных синглетонов (variant_type и Pool).
  • На данный момент может существовать только один аллокатор памяти, нельзя делать отдельные пулы.
    По этому поводу есть мысли, надо развивать. Например, внутри основного пула можно сделать несколько внутрених и выделять память в них, и при необходимости чистить только только их, а не всю память.
  • Почти не думал на тему многопоточности и exception safe
  • Возвращаемые из функций переменные живут не в режиме FIFO.
    Для исправления этого сделано некрасивое решение — при удалении из стека корневых указателей рассматриваются последние 2 элемента, а не один как то положено для нормального стека.
  • Выравнивание сделано очень криво.
    Предусмотрено выравнивание по 4 байта, но этого едостаточно.
  • Про вопрос применимости всей этой системы — вообще молчу 8-)

    Код и примеры тут: http://www.dr-gucho.com/downloads/TestGC.zip
  • Нужно разобрать угил.
     
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.