全手動ガベージコレクタを作った

マークからスイープまで全部自分で指定しないと動いてくれないガベージコレクタを作った。しかも1つのメモリ管理に付き1つの型しかつかえない。要はメモリアロケータなのだが、

static MemoryManager<int> mm;

int main() {
	int c = 0;
	
	while(1) {
		auto& item = mm.make();

		*item = 100;
		cout << &*item << ":" << *item << endl;

		if(++c > 5) {
			mm.sweep();
		}
		
		Sleep(10);
	}

	cin.get();
}

このようにしてもメモリは使い回され、メモリ使用量は増加しない。ちなみに配列型も使用可能である。

static MemoryManager<int[4]> mm(1);

int main() {
	auto& item = mm.make();
	
	item[3] = 0;

	std::cin.get();
}

ただし範囲はチェックしていないので簡単にメモリ破壊が起こる。しかもデバッガでは検出できない。サイズNとアクセスするインデックスnは分かっているので必要なら例外を投げてもいい。(C++の原則からそういうチェックはしないことにした。)

static MemoryManager<int[4]> mm(2);

int main() {
	auto& item = mm.make();
	auto& item2 = mm.make();
	int c = 0;

	for(auto& v : *item) {
		v = c++;
	}

	for(auto& v : *item2) {
		v = c++;
	}

	item2[8] = 100; // 破壊

	for(const auto& v : *item) {
		cout << v << endl;
	}

	for(const auto& v : *item2) {
		cout << v << endl;
	}

	std::cin.get();
}

struct C {
	C(int x) : x(x) { cout << "new" << endl; }
	~C() { cout << "delete" << endl; }

	void show() {
		cout << "id:" << x << endl;
	}

	int x;
};

static MemoryManager<C*> mm(3);

int main() {
	auto& item = mm.make(5); // new C(5)が実行される
	item->show(); // itemが呼び出される

	auto& item2 = mm.make(10); // new C(10)が実行される
	item2->show(); // item2が呼び出される

	mm.sweep(); // マークが解除される
	mm.sweep(); // マークされていないオブジェクトはフリーリストに繋がれ、deleteされる
	mm.dump(); // すべてフリー

	cin.get();
}

このように、メモリ管理用のMemoryManager<型>を宣言して使う。内部ではリンクリストでメモリブロックを作ってまとめて確保しているため、1つずつ確保したい場合は引数に1を指定する。デフォルトでは32である。

新しくメモリを割り当てるにはmakeをする。もしも型がポインタだったらnewを呼び出して初期化する。ポインタでなければ既に確保されているメモリが使用される。いずれにせよメモリを指す参照が返される。

取得した参照に対して*変数名とすれば内部のデータを取得できる。ポインタであれば、変数名->も使用可能である。

sweepメソッドを実行するとマークされていないオブジェクトが全てフリーリストに繋がれるされる。これは再利用される。また、ポンタだった場合はdeleteも実行される。いずれにせよ、回収されたオブジェクトにアクセスしようとすると例外が発生する。

dumpメソッドは現在のメモリを全て列挙するものである。データのポインタと、マークされているかどうかのフラグを表示する。

次に、スコープを抜けたときの処理を考える。

{
	Item<C*>& item = mm.make(5); // メモリを取得(この時点で既にマーク)
	item->show(); // item
} // 何もしない

mm.sweep(); // マークされているので次のsweepで解放される
mm.dump();

スコープを抜けてもメモリは保持したままである。またこの際マークされているのでそのまま使用可能である。ただし、特定のスコープでしか使わない場合、あるいはスコープを抜けたらマークを消したい場合がある。そのためにScopedItem<型>を用意した。これはItem<型>&を格納し、スコープを抜けたらマークを外す動作をする。

{
	ScopedItem<C*> item = mm.make(5); // メモリが確保され、マークもされる
	item->show();
} // スコープを抜けたのでマークが外される

mm.sweep(); // 解放される
mm.dump();

もしも途中でスコープを抜けてもマークを保持したいと変更したいときは、明示的にmark関数を実行する。

{
	ScopedItem<C*> item = mm.make(5);
	item->show();
	item.mark(); // 明示的にマーク
} // マークは外されない

mm.sweep(); // よって消されない
mm.dump();

応用例として、複雑な構造の中で使うサンプルを挙げる。あるクラスの中に再帰的にクラスを作るが、そのメモリ確保を外部で行うというものである。この例ではunique_ptrを使っても実現できるが、より複雑になると管理が大変だと思う。

struct C;
static MemoryManager<C*> mm(2);

struct C {
	C(int x) : x(x) { cout << "new: " << x << endl; }
	~C() { cout << "delete: " << x << endl; }

	void show() {
		cout << "id:" << x << endl;
		for(auto& it : c) {
			it->show();
		}
	}

	void create() {
		static int n = 0;
		++n;
		c.push_back(mm.make(x + n));
	}

	int x;
	list<Item<C*>> c;
};

int main() {
	{
		ScopedItem<C*> item = mm.make(5); // new: 5
		item->show();

		item->create(); // new: 6
		item->create(); // new: 7
		item->show();
	}
	
	mm.sweep(); // delete 5

	cin.get();
}

このようにItemのコピーも可能である。上記の例の場合はクラスCのメンバがScopedItemではなくItemなため、せっかくScopedItemとして生成したitemがsweepで回収されるのに他のitemが削除されない。〔もちろん、もう一度sweepすればマークする術がないためほぼ確実に回収される。〕

list<ScopedItem<C*>> c;

とすることで確実にsweepで回収される。というよりも、このように回収できるようにsweepを実装した。というのも、sweep作業を2回行い、1回目のdeleteによってマークが外されたようなものがあればそれも削除するようにしてある。

基本的にはRAIIによってリソースは閉じ込め、スタックを使って処理をするべきだが、場合によってはunique_ptrを使ってヒープに確保する方が良い場合がある。また、場合によってはshared_ptrを使って共有した方がいい。このガベージコレクタが使える場合はどんな場合だろう?

実装例

#pragma once
#include <stdexcept>

template <class T> class MemoryManager;
template <class T> class ScopedItem;

class AccessFailedException : public std::exception { };
class MoveFailedException : public std::exception { };

template <class T>
class Item {
	friend ScopedItem<T>;
	friend MemoryManager<T>;
private:
	enum MARK {
		USED = 0x80000000,
		FREE = 0x40000000,
		UNUSED = 0x20000000,
		USER_MARK = 0x10000000,
		SAFE = 0x08000000,
		SCOPED = 0x04000000,
		TEMP_SCOPED = 0x02000000
	};

public:
	Item() {
		set_mark(MARK::UNUSED);
	};

	T& operator*() {
		if(isMarked(MARK::UNUSED)) {
			throw AccessFailedException();
		}
		mark(MARK::USED);
		return item;
	}

	T& operator->() {
		return this->operator*();
	}

	operator bool() {
		return !isMarked(MARK::UNUSED);
	}

	void mark() {
		mark(MARK::USER_MARK);
	}

private:
	// マークの判定
	bool isMarked(int mark) const {
		if(f_marked & mark) {
			return true;
		}
		else {
			return false;
		}
	}

	void mark(int mark) {
		f_marked |= mark;
	}

	void set_mark(int mark) {
		f_marked = mark;
	}

	void sweep(int mark) {
		f_marked &= ~mark;
	}

	Item<T>* next;
	T item;
	int f_marked;
};

/*
	copy
*/
template <class T, size_t N>
class Item<T[N]> {
	using TYPE = T[N];

	friend ScopedItem<TYPE>;
	friend MemoryManager<TYPE>;
private:
	enum MARK {
		USED = 0x80000000,
		FREE = 0x40000000,
		UNUSED = 0x20000000,
		USER_MARK = 0x10000000,
		SAFE = 0x08000000,
		SCOPED = 0x04000000,
		TEMP_SCOPED = 0x02000000
	};

public:
	Item() {
		set_mark(MARK::UNUSED);
	};

	TYPE& operator*() {
		if(isMarked(MARK::UNUSED)) {
			throw AccessFailedException();
		}
		mark(MARK::USED);
		return item;
	}

	T& operator[](size_t index) {
		return item[index];
	}

	TYPE& operator->() {
		return this->operator*();
	}

	operator bool() {
		return !isMarked(MARK::UNUSED);
	}

	void mark() {
		mark(MARK::USER_MARK);
	}

private:
	// マークの判定
	bool isMarked(int mark) const {
		if(f_marked & mark) {
			return true;
		}
		else {
			return false;
		}
	}

	void mark(int mark) {
		f_marked |= mark;
	}

	void set_mark(int mark) {
		f_marked = mark;
	}

	void sweep(int mark) {
		f_marked &= ~mark;
	}

	Item<TYPE>* next;
	T item[N];
	int f_marked;
};

template <class T>
class ScopedItem {
public:
	ScopedItem() : item() { }
	// Itemからのコピーコンストラクタ
	// 破棄されても何もしない
	ScopedItem(Item<T>& item) : item(&item) {
		item.mark(Item<T>::MARK::TEMP_SCOPED);
	}

	ScopedItem& operator=(const ScopedItem& it) {
		item = it.item;
		item->mark(Item<T>::MARK::SCOPED);
		
		return *this;
	}
	~ScopedItem() {
		if(item->isMarked(Item<T>::MARK::TEMP_SCOPED)) {
			item->sweep(Item<T>::MARK::TEMP_SCOPED);
			return;
		}

		if(!item->isMarked(Item<T>::MARK::USER_MARK)) {
			item->sweep(Item<T>::MARK::USED);
		}
		item->sweep(Item<T>::MARK::USER_MARK | Item<T>::MARK::SCOPED);
	}

	T& operator*() {
		return **item;
	}
	T& operator->() {
		return this->operator*();
	}
	operator Item<T>&() {
		return *item;
	}

	operator bool() {
		return *item;
	}

	void mark() {
		item->mark();
	}
private:
	Item<T>* item;
};

template <class T>
class MemoryManager {
private:
	struct MemoryBlock {
		MemoryBlock* next;
		Item<T>* list;
		int mark_flag;
	};

public:
	MemoryManager(int unit_size = 32) {
		this->unit_size = unit_size;
		first = nullptr;
		last = nullptr;
		free_pool = nullptr;
	}

	template <class ...Args>
	Item<T>& make(Args ...args) {
		Item<T>* ret;

		// フリープールになければブロックを確保
		if(free_pool == nullptr) {
			MemoryBlock* new_block = allocateMemoryBlock();

			// 一番最初の状態
			if(last == nullptr) {
				first = new_block;
			}
			// ブロックのつなぎ替え
			else {
				last->next = new_block;
			}

			last = new_block;

			setFreePool(new_block);
		}

		// 最新のフリープールのポインタを返す
		ret = free_pool;
		// 今後フリープールの次を参照するようにする
		free_pool = ret->next;
		// 自分が実データの先頭となる
		ret->next = nullptr;
		// マークの初期化
		ret->set_mark(Item<T>::MARK::USED);

		// ポインタだったらnewして初期化
		_make<T>()(ret, args...);

		return *ret;
	}

	void deleteItem(Item<T>* at) {
		// 次を現在のフリープールにする
		at->next = free_pool;
		// 現在のフリープールの先頭を自身にする
		free_pool = at;
		// フリーな要素としてマークする
		at->set_mark(Item<T>::MARK::FREE | Item<T>::MARK::UNUSED);

		_deleteItem<T>()(at);
	}

	template <class U>
	struct _deleteItem {
		void operator()(Item<U>*) { }
	};

	// ポインタだったら解放する
	template <class U>
	struct _deleteItem<U*> {
		void operator()(Item<U*>* at) {
			delete at->item;
		}
	};

	template <class U>
	struct _make {
		void operator()(Item<U>*) { }
	};

	// ポインタだったら生成する
	template <class U>
	struct _make<U*> {
		template <class ...Args>
		void operator()(Item<U*>* at, Args ...args) {
			at->item = new U(args...);
		}
	};

	// ポインタでなければsweepは1回
	void _sweep_nonpointer() {
		MemoryBlock* at = first;
		Item<T>* item;
		int i, count;

		// 全てのメモリブロックについてスイープ
		while(at) {
			item = at->list;
			count = 0;

			// 全てのリスト要素についてマーク判定に基づき処理
			for(i = 0; i < unit_size; ++i) {
				// 何もフラグが立っていないデータ
				if(!item->isMarked(-1)) {
					deleteItem(item);
					++count;
				}

				item->sweep(Item<T>::MARK::USED | Item<T>::MARK::USER_MARK);

				// 次のリスト要素を探索
				++item;
			}

			// メモリブロック上の全てのリスト要素がフリーならマークしておく
			if(count == unit_size) {
				at->mark_flag |= 0x80000000;
			}

			at = at->next;
		}
	}

	// ポインタだったら2回sweepを実行する
	void _sweep_pointer() {
		MemoryBlock* at = first;
		Item<T>* item;
		int i, count;

		// 全てのメモリブロックについてスイープ
		while(at) {
			item = at->list;
			count = 0;

			// 全てのリスト要素についてマーク判定に基づき処理
			for(i = 0; i < unit_size; ++i) {
				// 何もフラグが立っていない
				if(!item->isMarked(-1)) {
					deleteItem(item);
					++count;
				}
				// 使用されているデータはセーフフラグを立てる
				else if(item->isMarked(Item<T>::MARK::USED)) {
					item->mark(Item<T>::MARK::SAFE);
				}

				item->sweep(Item<T>::MARK::USER_MARK);

				// 次のリスト要素を探索
				++item;
			}

			// メモリブロック上の全てのリスト要素がフリーならマークしておく
			if(count == unit_size) {
				at->mark_flag |= 0x80000000;
			}

			at = at->next;
		}

		// 解放の処理によってフラグがクリアされたものも解放する
		at = first;

		while(at) {
			item = at->list;

			for(i = 0; i < unit_size; ++i) {
				// セーフフラグが立っていて
				if(item->isMarked(Item<T>::MARK::SAFE)) {
					// マークが削除されたものは更に削除
					if(!item->isMarked(Item<T>::MARK::USED)) {
						deleteItem(item);
					}
				}

				// セーフフラグ及びマークをクリア
				item->sweep(Item<T>::MARK::SAFE | Item<T>::MARK::USED);

				++item;
			}

			at = at->next;
		}
	}

	// ポインタでなければsweep2回
	template <class U>
	struct _sweep {
		void operator()(MemoryManager<U>* it) {
			it->_sweep_nonpointer();
		}
	};

	// ポインタだったらsweep2回
	template <class U>
	struct _sweep<U*> {
		template <class ...Args>
		void operator()(MemoryManager<U*>* it) {
			it->_sweep_pointer();
		}
	};

	void sweep() {
		_sweep<T>()(this);
	}

	void dump() {
		MemoryBlock* at = first;
		Item<T>* item;
		int i, n = 0;

		while(at) {
			item = at->list;
			++n;
			cout << "block no." << n << endl;
			for(i = 0; i < unit_size; ++i) {
				cout << &item->item << "\t"
					<< item->isMarked(Item<T>::MARK::USED)
					<< item->isMarked(Item<T>::MARK::USER_MARK)
					<< item->isMarked(Item<T>::MARK::FREE)
					<< item->isMarked(Item<T>::MARK::UNUSED)
					<< item->isMarked(Item<T>::MARK::SCOPED)
					<< endl;
				++item;
			}
			at = at->next;
		}
	}

private:
	MemoryBlock* allocateMemoryBlock() {
		MemoryBlock* ret;
		Item<T>* list;

		ret = new MemoryBlock;
		list = new Item<T>[unit_size];

		ret->list = list;
		ret->next = nullptr;
		return ret;
	}

	// 全てのListを連結し、前後をフリープールに繋ぐ
	void setFreePool(MemoryBlock* at) {
		int i;
		Item<T>* item = at->list;
		Item<T>* previous_item;

		// 最初の要素の次をフリープールに繋ぐ
		item->next = free_pool;

		for(i = 1; i < unit_size; ++i) {
			// 直前のリストを保存
			previous_item = item;
			// 次のリスト要素に進めて
			++item;
			// 次のリスト要素のnextは、直前のリスト要素を指すようにする
			item->next = previous_item;
		}

		// フリープールを最後の要素に設定する
		free_pool = item;
	}

	int unit_size;
	MemoryBlock* first;
	MemoryBlock* last;
	Item<T>* free_pool;
};

• ちょっと実用に耐えないので設計し直します……