C++ による Copying GC の実装について

機能

Copying GC が何なのか, という事については authorNari さんの記述や pasberth さんの記述に任せるとして, ここでは満たすべき機能を列挙したいと思います.

(1) プログラマの記述した型に適合した heap から allocate してくる. manager 実装時に segmentation fault が発生しない様に alignment に注意.

// int に適合した heap を適当に 256 用意する.
memory_manager<int> manager(256);
// ここで allocate する.
int *x = manager.alloc(10);

(2) GC が有効なメモリ領域かそうでないかを判断できるように, root を設定する.

// alloc した x にある領域を root として設定する.
manager.set_root(x);

(3) とあるメモリ領域から, 別のメモリ領域を接続する.

int *y = manager.alloc(1), *z = manager.alloc(2);

// x -> y -> z -> x
manager.join(x, y);
manager.join(y, z);
manager.join(z, x);

(4) 孤立したメモリ領域を自動的に検出して破棄する.

// int[5] の孤立した空間を alloc してみる.
manager.alloc(5);

// プログラマの決めたタイミングで gc を走らせる.
// manager.alloc(5) した空間が消えている.
manager.run();

// x -/-> y -> z -> x の場合,
// z が x に依存していても, x から最終的に z までの依存が切れているので
// y, z は消える.
manager.disjoin(x, y);
manager.run();

(5) MSVC と gcc で動作する. これはただ単純に利便性を図るための条件であって, 後発の機能や処理系依存の機能があれば適当に書き換えても良いがここではその課題には取り組まない.

構造

header

manager はメモリ領域を確保する時, GC へ提供する情報の格納された header へのポインタを, heap から用意した領域の前方に埋め込む. そしてプログラマが manager から得られる値は (B) へのポインタになるため, 普通の raw な配列の様に特に GC の存在を意識する必要はない.

         +--> (A) allocate された配列の情報が格納される固定領域ヘッダへのポインタ.
         |
         |                    +--> (B) allocate されたメモリ領域.
         |                    |
- - - ---+--------------------+-----------------------------------------+--- - - -
         | header<ValueType>* | std::aligned_storage<                   |
         |                    |     sizeof(ValueType),                  |
         |                    |     std::alignment_of<ValueType>::value |
         |                    | >::type[n]                              |
- - - ---+--------------------+-----------------------------------------+--- - - -

header の構造は以下になっている.

template<class ValueType>
struct header{
    header *next, *prev, *copied = nullptr;
    std::size_t size = 0;
    reference_list<ValueType> *linked_reference_list = nullptr;
    typename std::aligned_storage<
        sizeof(ValueType),
        std::alignment_of<ValueType>::value
    >::type *data = nullptr;
};

• next, prev は後述する侵入型リンクリスト intrusive_linked_list に対応させるためのもの.
• copied は GC の処理中に別の heap にコピーされたかどうかを判別するためのポインタ.
• size は data の長さを整数として持つ. ただし header のポインタはコンパイル時にサイズが明確なのでこの値に含まれない.
• linked_reference_list はこの header が指す ValueType 型のインスタンスが参照している別のインスタンスへのリンクの情報が入る.
• data 確保されたメモリ領域へのポインタ.

reference_list

確保されたメモリ領域上にあるインスタンスは他のインスタンスを参照し依存している場合がある. この関係を保存するのに linked-list を用いるのは有効だろう.

template<class ValueType>
struct reference_list{
    reference_list *next, *prev, *next_reference = nullptr;
    header<ValueType> *ptr;
};

• next, prev は header と同様, 後述する侵入型リンクリスト intrusive_linked_list に用いられる.
• next_reference は参照関係にある次の reference_list を指す. 双方向リンクリストでなくても良い.
• ptr は依存しているインスタンスを指すポインタ.

intrusive_linked_list

C++ の template はメンバに対して Duck Typing としての挙動を示す. ここでは header, reference_list 内にある next, prev をそれぞれ利用し, リンクリスト構築に使用する.

// 侵入式リンクリスト.
// active な要素と free な要素に分かれており両者は区別される.
// 最大要素数は初期化時の要素数指定に依存する.
template<class Type>
class intrusive_linked_list{
public:
    intrusive_linked_list() = delete;
    intrusive_linked_list(const intrusive_linked_list&) = delete;

    intrusive_linked_list(std::size_t n) : pool(new Type[n]){
        active_dummy.next = active_dummy.prev = &active_dummy;
        for(std::size_t i = 0; i < n - 1; ++i){
            pool.get()[i].next = &pool.get()[i + 1];
            pool.get()[i + 1].prev = &pool.get()[i];
        }
        free->next = pool.get();
        pool.get()->prev = free;
        free->prev = (pool.get() + n - 1);
        (pool.get() + n - 1)->next = free;
    }

    ~intrusive_linked_list() = default;

    // 生成し, 取得する.
    Type *get(){
        if(free->next == free){
            throw std::bad_alloc();
        }
        Type *ptr = free->next;
        free->next = free->next->next;
        free->next->prev = free;
        ptr->next = active->next;
        ptr->next->prev = ptr;
        ptr->prev = active;
        active->next = ptr;
        return ptr;
    }

    // 破棄する.
    void dispose(Type *ptr){
        ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        ptr->next = free;
        ptr->prev = free->prev;
        free->prev->next = ptr;
        free->prev = ptr;
    }

    // さっさと破棄する.
    void sassato_dispose(Type *ptr){
        ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        ptr->next = free->next;
        ptr->prev = free;
        free->next->prev = ptr;
        free->next = ptr;
    }

private:
    std::unique_ptr<Type[]> pool;
    Type active_dummy, *active = &active_dummy, free_dummy, *free = &free_dummy;

public:
    const Type *const active_dummy_ptr = &active_dummy;
};

intrusive_linked_list<header>, intrusive_linked_list<reference_list>, heap 内部でのポインタの参照関係を以下の図に示した.

,==[[ intrusive_linked_list<header> (active) ]]===============================､
|                                                                             |
|  - - - ---+    +-------------------------------------------+    +--- - - -  |
|      next----------->                                 next----------->      |
|           |    |       +linked_reference_list  +data       |    |           |
|      <-----------prev  |                       |      <-----------prev      |
|  - - - ---+    +-------|-----------------------|-----------+    +--- - - -  |
|                        |                 +-----+                            |
`========================|=================|=================================='
               +---------+                 |
               |    ,==[[ heap ]]==========|=================================､
               |    |                      V                                 |
               |    |  - - - ---+----------+---------------------+--- - - -  |
               |    |           |  header  |  (aligned storage)  |           |
               |    |  - - - ---+----------+---------------------+--- - - -  |
               |    |           ^                                            |
               |    `===========|============================================'
               +-+              +---------+
,================|========================|=============================､
|                V                        |                             |
|  - - - ---+    +------------------------|------------+    +--- - - -  |
|      next----------->                   |        next------------->   |
|           |    |       +next_reference  +header      |    |           |
|      <-----------prev  |                         <-------------prev   |
|  - - - ---+    +-------|-----------------------------+    +--- - - -  |
|                        |                                              |
|  - - - - -+    + - - - V - - - - - - - - - - - - - - +    +- - - - -  |
|      next---------->                            next---------->       |
|           :    :        (other reference_list)       :    :           |
|      <-----------prev                           <-----------prev      |
|  - - - - -+    +- - - - - - - - - - - - - - - - - - -+    +- - - - -  |
|                                                                       |
`=================[[ intrusive_linked_list<reference_list> (active) ]]=='

storage

storage はふたつの heap, heap_1, heap_2 と current heap, それに続き current heap の待機中の先頭 head を保持する.

std::unique_ptr<element_type[]> heap_1, heap_2;
element_type *heap, *head;
const std::size_t max;

以下のメンバも付け加えておくと便利だろう.

using element_type = typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type;
static const std::size_t void_ptr_size_in_heap = sizeof(void*) / sizeof(element_type) + (sizeof(void*) % sizeof(element_type) ? 1 : 0);

storage のメンバ関数には雑多なものが少なからずあるので, 要点のみ書き記しておく.

• run()
  GC を起動する.

• copy()
  GC 処理中に再帰的に接続を辿って孤立していないメモリ領域を探査し, 別の heap へ copy する.

• alloc()
  メモリ領域を割り当てる.

• free()
  割り当てられたメモリ領域を開放する. このコールによって heap に fragmentation が発生する場合は, この処理は意味をなさない.

memory_manager

一部を除き単に storage をラップしただけなので, この項目も要点のみ記述する.

• alloc()
  与えられた型のメモリ領域を allocate する.

• free()
  与えられたメモリ領域を開放する.

• set_root()
  root を設定する.

• run()
  GC を起動する.

• join()
  参照を設定する.

• disjoin()
  参照を解除する.

ソースコード

以上から実装したソースコードの例はこちらのリンクから.