マーク＆スイープ法をテスト実装してみる

#c #gc

ガベコレも、なんとなくやってることはわかるんだけど、実際のところよくわからない…なので実装して確かめる。手始めにマーク＆スイープ法。

GCを自分で実装、ということでメモリ管理も自分で好きに扱えるように、自分で作る。というかK&Rのmallocルーチンの管理構造体を外から渡すようにしたもの：

balloc.c

/// Buffer Allocator
/**
  K&R「プログラミング言語Ｃ」の malloc ルーチン
*/

#include "balloc.h"

typedef union balloc_header Header;

/* 領域初期化 */
void balloc_init(BAlloc* balc, void* buf, unsigned size)
{
  Header* up;

  balc->base.s.ptr = balc->freep = &balc->base;
  balc->base.s.size = 0;
  balc->used = balc->marked = NULL;

  up = (Header*)buf;
  up->s.size = size / sizeof(Header);
  bfree(balc, up + 1);
}

/* malloc: 汎用の記憶割当てプログラム */
void *balloc(BAlloc* balc, unsigned nbytes)
{
  Header *p, *prevp;
  Header *root;
  unsigned nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
  prevp = root = balc->freep;
  for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
    if (p->s.size >= nunits) {    /* 十分大きい */
      Header *q;
      if (p->s.size == nunits) {    /* 正確に */
        prevp->s.ptr = p->s.ptr;
        q = p;
      } else {            /* 後尾の部分を割り当て */
        p->s.size -= nunits;
        q = p + p->s.size;
        q->s.size = nunits;
      }
      balc->freep = prevp;
      q->s.ptr = balc->used;
      balc->used = q;
      return (void*)(q + 1);
    }
    if (p == root)    /* 空きリストをリング状につなぐ */
      return NULL;    /* 残りなし */
  }
}

/* free: ブロック ap を空きリストに入れる */
void bfree(BAlloc* balc, void* ap)
{
  if (ap != NULL) {
    Header *bp, *p;

    bp = (Header*)ap - 1;    /* ブロック・ヘッダを指す */
    for (p = balc->freep; !(p < bp && bp < p->s.ptr); p = p->s.ptr) {
      if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
        break;    /* 領域の始めあるいは終りの解放ブロック */
    }

    if (bp + bp->s.size == p->s.ptr) {  /* 上の nbr へ結合 */
      bp->s.size += p->s.ptr->s.size;
      bp->s.ptr = p->s.ptr->s.ptr;
    } else {
      bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {      /* 下の nbr へ結合 */
      p->s.size += bp->s.size;
      p->s.ptr = bp->s.ptr;
    } else {
      p->s.ptr = bp;
    }
    balc->freep = p;
  }
}

未使用のブロックがリングにつながってる
確保されたメモリはリストにつなぐ
ひとまず、要求されたメモリが確保できなくても gc は起動せず NULL を返すだけ

balloc.h

/// Buffer Allocator

#pragma once

/// アライメント用
typedef long BAllocAlign;

/// ヘッダ
union balloc_header {    /* ブロックのヘッダ */
  struct {
    union balloc_header* ptr;    /* 空きリストの上なら次のブロック */
    unsigned size;          /* このブロックの大きさ */
  } s;
  BAllocAlign _align;    /* ブロックの整合を強制 */
};

/// 構造体
typedef struct {
  union balloc_header base;    /* 開始時の空きリスト */
  union balloc_header* freep;    /* 空きリストの先頭 */
  union balloc_header* used;    /* 空きリストの先頭 */
  union balloc_header* marked;  /* マーク済みの先頭 */
} BAlloc;

/// 初期化
void balloc_init(BAlloc* balc, void* buf, unsigned size);

/// バッファからメモリ確保
void *balloc(BAlloc* balc, unsigned nbytes);

/// 確保したメモリの解放
void bfree(BAlloc* balc, void* ap);

テストとして確保する構造体とワーク：

struct Test {
  int no;
};

const int NBUF = 4;
Test* test[NBUF];

ヒープの初期化：

const int HEAPSIZ = 1 * 1024;
char heap[HEAPSIZ];

int main(int argc, char* argv[]) {
  BAlloc allocator, *balc = &allocator;
  balloc_init(balc, heap, sizeof(heap));

確保して、次々に捨てるコード。最終的にバッファに残ったものだけが生存するワークとなる：

  const int N = 32;
  for (int i=0; i<N; ++i) {
    int r = rand() * NBUF / (RAND_MAX + 1);
    Test* p = (Test*)balloc(balc, sizeof(Test));
    p->no = i;
    test[r] = p;
  }

  dump_meminfo(balc);

...

void dump_meminfo(BAlloc* balc) {
  int freesize, nalloc;
  nalloc = balloc_get_info(balc, &freesize);
  printf("mem: free=%d, #%d\n", freesize, nalloc);

  for (int i=0; i<NBUF; ++i) {
    Test* p = test[i];
    if (p != NULL) {
      printf("%p: %d\n", p, p->no);
    }
  }
}

int balloc_get_info(BAlloc* balc, int* pfreesize) {
  int size = 0;
  int nalloc = 0;

  {
    Header* p;
    for (p = &balc->base; p = p->s.ptr, p != &balc->base; ) {
      size += p->s.size;
    }
    *pfreesize = size * sizeof(Header);
  }

  {
    Header* p;
    for (p = balc->used; p != NULL; p = p->s.ptr) {
      ++nalloc;
    }
  }

  return nalloc;
}

GCのルートから辿れるものを全てマークして、マークされなかったものをスイープ：

  mark_all(balc);
  sweep(balc);

  dump_meminfo(balc);

  return 0;
}

今回のものは、内部にポインタを持たないので、ルートのみをマーク

void mark_all(BAlloc* balc) {
  for (int i=0; i<NBUF; ++i) {
    Test* p = test[i];
    mark(balc, p);
  }
}

ひとつのワークをマーク。ワークがヒープから取られたものかどうか確認する。そうだったらマーク済みに移す。マークしたかどうかはブロックのサイズの最上位ビットを使う：

#define  MARK_FLAG  (1<<(sizeof(unsigned) * 8-1))
#define  MARK(ptr)  ((ptr)->s.size |= MARK_FLAG)
#define  UNMARK(ptr)  ((ptr)->s.size &= ~MARK_FLAG)

int mark(BAlloc* balc, void* work) {
    // 使ってるリストから検索
  Header* h = ((Header*)work) - 1;
  Header* pre = NULL;
  Header* p;
  for (p = balc->used; p != NULL; pre = p, p = p->s.ptr) {
    if (p == h) {  // あった
        // マークをつける
      MARK(p);
        // 使用中からはずす
      if (pre != NULL) {
        pre->s.ptr = p->s.ptr;
      } else {
        balc->used = p->s.ptr;
      }
        // マーク済みに移動
      p->s.ptr = balc->marked;
      balc->marked = p;
      return TRUE;
    }
  }
  return FALSE;
}

回収は、使用済みに残ったもの（＝マークされてない）を全て解放。マーク済みのものをマークをはずして使用中に戻す：

void sweep(BAlloc* balc) {
  Header* p;
  // マークされてないものを解放する
  //  used に残ったものがマークされてないもの
  for (p = balc->used; p != NULL; ) {
    Header* q = p->s.ptr;
    void* work = p + 1;    // 貸し出したポインタ
    bfree(balc, work);
    p = q;
  }
  // マーク済みのマークを落として、使用中に戻す
  balc->used = balc->marked;
  balc->marked = NULL;
  for (p = balc->used; p != NULL; p = p->s.ptr) {
    UNMARK(p);
  }
}

実行結果：

mem: free=1024, #0
mem: free=512, #32
004286F8: 30
00428748: 25
004286E8: 31
00428798: 20
mem: free=960, #4
004286F8: 30
00428748: 25
004286E8: 31
00428798: 20

なんかすっきりしない…

使用中のワークをマークするためには、アプリ側でどれが gc のルートとなるかをすべて列挙してやらなきゃいけない
確保されてるワークの、どのメンバがポインタかを知ってなきゃいけない
指してるポインタが、GC用のバッファから確保したものかどうかを確認するとすごく時間がかかりそう(O(n^2)?)
- ヒープの範囲かどうか調べればマシになるけど、そうするとブロックの先頭以外を指してるポインタがあると誤動作する
確保したメモリの途中を指してると回収されてしまう
malloc ルーチン自体も自作してやらんと非効率的になりそうな
- 使用中のヒープ全てのポインタを知っている
- マークビットをどこかにセットできる

どこかに猫でもわかる簡単なGC実装のサンプルはないでしょうか。

関連記事

【C】constポインタは何が上書き不可なのか

【C】printfに独自の表示形式を追加する

【C】可変長引数の回避と引数の数による関数の呼び分け

関数ポインタを返す関数のパースと型の構築

【C】プリプロセッサのマクロ展開アルゴリズム

新着記事