メモリアロケータ書いた

ええ、車輪の再発明だということは承知しておる!
Xtal全体がまぁ再発明ともいえるんですけど。

Xtalはユーザーが自由にmalloc, free関数を登録できるようになってるんですが、
「メモリ確保関数を用意して登録するのめんどくさい。単純にメモリのここからここまで使ってほしいんよ」ということもあると思うんです。
そのために、
・クラス一つで完結している
・メモリ領域を指定するだけ
・グローバル変数などを使用しない
・まあいろいろととにかくシンプル
そんなライブラリを作ろうということで作りました。


チャンクの管理は赤黒木で行っています。
要求されたサイズにもっとも近く、またアドレス値が小さいチャンクを検索します。
管理領域のサイズは、フリーチャンクのときは16byte(というかポインタ4つ分)、使用チャンク時は8byte(というかポインタ二つ分)です。
赤黒木のノードとしての色と、使用中かどうかのフラグは、前チャンクを指すポインタに埋め込んでます。

性能評価して、まるでダメなら素直にdlmalloc組み込むか…。
しかし、メモリアロケータの性能評価ってどう計ったら効果的なんだろか？

以下ソース。

class MemoryManager{
	enum{
		USED = 1<<0,
		RED = 1<<1,
		FLAGS_MASK = RED | USED,
		
		MIN_ALIGNMENT = 8,

		GUARD_MAX = 32,
	};

	struct Chunk;

	// デバッグ情報はここに埋め込む
	struct DebugInfo{
		int line;
		const char* file;
		int size;
	};

	union PtrWithFlags{
		uint_t u;
		Chunk* p;
	};

	struct ChunkHeader{
#ifdef XTAL_DEBUG
		DebugInfo debug;
#endif
		Chunk* next;
		PtrWithFlags prev; // prevを指すポインタに、色と使用中かのフラグを埋め込む
	};

	struct ChunkBody{
		Chunk* left;
		Chunk* right;
	};

	struct Chunk{
		ChunkHeader h;
		ChunkBody b;

		void init(){ 
			h.next = h.prev.p = b.left = b.right = 0; 
		}

		int size(){ return (unsigned char*)h.next - (unsigned char*)buf(); }
		void* buf(){ return (unsigned char*)(&h+1); }

		Chunk* next(){
			return h.next; 
		}

		Chunk* prev(){ 
			PtrWithFlags u = h.prev;
			u.u &= ~FLAGS_MASK;
			return u.p; 
		}

		void set_next(Chunk* p){ 
			h.next = p; 
		}

		void set_prev(Chunk* p){
			PtrWithFlags u;
			u.p = p;
			u.u |= h.prev.u & FLAGS_MASK;
			h.prev = u; 
		}

		void ref(){			
			h.prev.u |= USED;
		}

		void unref(){
			h.prev.u &= ~USED;
		}

		bool is_used(){			
			return h.prev.u & USED;
		}

		bool is_red(){ 
			return h.prev.u & RED;
		}

		void set_red(){ 
			h.prev.u |= RED;
		}

		void set_black(){
			h.prev.u &= ~RED;
		}

		void flip_color(){ 
			h.prev.u ^= RED;
		}

		void set_same_color(Chunk* a){ 
			set_black(); 
			h.prev.u |= a->h.prev.u&RED; 
		}
	};

public:


	MemoryManager(){ 
		head_ = begin_ = end_ = 0; 
	}
	
	MemoryManager(void* buffer, size_t size){
		init(buffer, size);
	}

	void init(void* buffer, size_t size);

	/**
	* \brief メモリ確保
	*/
	void* malloc(size_t size, int alignment = sizeof(int_t), const char* file = "", int line = 0);

	/**
	* \brief メモリ解放
	*/
	void free(void* p);

private:

	Chunk* chunk_align(Chunk* it, int alignment);

	void* malloc_inner(size_t size, int alignment = MIN_ALIGNMENT, const char* file = "", int line = 0);

	void free_inner(void* p);

	Chunk* begin(){ return begin_; }

	Chunk* end(){ return end_; }

	Chunk* to_chunk(void* p){ 
		return (Chunk*)((ChunkHeader*)p - 1);
	}
	
private:

	int compare(Chunk* a, Chunk* b){
		if(int ret = a->size() - b->size()){
			return ret;
		}

		return a - b;
	}

	Chunk* find(Chunk* l, int key);

	Chunk* find(int key){
		return find(root_, key);
	}

	void flip_colors(Chunk* n);

	Chunk* rotate_left(Chunk* n);

	Chunk* rotate_right(Chunk* n);

	Chunk* fixup(Chunk* n);

	Chunk* insert(Chunk* n, Chunk* key);

	void insert(Chunk* key);

	Chunk* minv(Chunk* n);

	Chunk* move_red_left(Chunk* n);

	Chunk* move_red_right(Chunk* n);

	Chunk* remove_min(Chunk* n);

	Chunk* remove(Chunk* n, Chunk* key);

	void remove(Chunk* key){
		root_ = remove(root_, key);
		root_->set_black();
	}

public:

	enum{
		COLOR_FREE,
		COLOR_USED
	};

	void dump(unsigned char* dest, size_t size, unsigned char* marks);

	void dump(unsigned char* dest, size_t size);

private:
	Chunk* head_;
	Chunk* begin_;
	Chunk* end_;
	Chunk* root_;

	size_t buffer_size_;
};

void MemoryManager::init(void* buffer, size_t size){
	buffer_size_ = size;

	head_ = (Chunk*)align_p(buffer, MIN_ALIGNMENT);
	begin_ = head_+1;
	end_ = (Chunk*)align_p((Chunk*)((char*)buffer+size)-2, MIN_ALIGNMENT);
	
	head_->init();
	head_->set_next(begin_);
	head_->set_prev(head_);
	head_->set_black();
	head_->ref();
	
	begin_->init();
	begin_->set_next(end_);
	begin_->set_prev(head_);
	begin_->set_red();
	
	end_->init();
	end_->set_next(end_);
	end_->set_prev(begin_);
	end_->set_black();
	end_->ref();
	end_->b.left = end();
	end_->b.right = end();

	begin_ = chunk_align(begin_, MIN_ALIGNMENT);
	
	root_ = begin_;
	root_->b.left = end();
	root_->b.right = end();
	root_->set_red();
}

void* MemoryManager::malloc(size_t size, int alignment, const char* file, int line){
#ifdef XTAL_DEBUG
	if(void* p = malloc_inner(size+GUARD_MAX, alignment, file, line)){
		Chunk* cp = to_chunk(p);
		cp->h.debug.size = size;
		cp->h.debug.file = file;
		cp->h.debug.line = line;
		memset((unsigned char*)p+size, 0xcc, GUARD_MAX);
		memset(p, 0xdd, size);
		return p;
	}
	return 0;
#else
	return malloc_inner(size, alignment, file, line);
#endif
}

void MemoryManager::free(void* p){
#ifdef XTAL_DEBUG
	Chunk* cp = to_chunk(p);
	unsigned char* ucp = (unsigned char*)p+cp->h.debug.size;
	for(int i=0; i<GUARD_MAX; ++i){
		int cc = *((unsigned char*)p+cp->h.debug.size+i);
		XTAL_ASSERT(*((unsigned char*)p+cp->h.debug.size+i)==0xcc);
	}

	free_inner(p);
#else
	free_inner(p);
#endif
}

MemoryManager::Chunk* MemoryManager::chunk_align(Chunk* it, int alignment){
	// ユーザーへ返すメモリの先頭アドレスを計算
	void* p = align_p(it->buf(), alignment);

	// アライメント調整のため、ノードの再設定
	if(it!=to_chunk(p)){
		Chunk temp = *it;
		it = to_chunk(p);
		*it = temp;
		it->prev()->set_next(it);
		it->next()->set_prev(it);
	}

	return it;
}

/**
* \brief メモリ確保
*/
void* MemoryManager::malloc_inner(size_t size, int alignment, const char* file, int line){
	if(alignment>MIN_ALIGNMENT){
		alignment = align_2(alignment);
	}
	else{
		alignment = MIN_ALIGNMENT;
	}

	if(size<alignment){
		size = alignment;
	}
	else{
		size = align(size, alignment);
	}

	size_t find_size = size + (alignment-MIN_ALIGNMENT);

	// もっとも要求サイズに近いノードを探す
	Chunk* it = find(find_size);
	if(it!=end()){
		// 赤黒木から外す
		remove(it);
		it->ref();

		// it->buf()のアドレスがアラインしているように調整
		it = chunk_align(it, alignment);

		Chunk* newchunk = (Chunk*)((unsigned char*)it->buf()+size);
		newchunk = to_chunk(align_p(newchunk->buf(), MIN_ALIGNMENT));

		if(it->next()-1>=newchunk){
			newchunk->init();
			it->next()->set_prev(newchunk);
			newchunk->set_next(it->next());
			it->set_next(newchunk);
			newchunk->set_prev(it);

			insert(newchunk);
		}

		return it->buf();
	}
		
	return 0;
}

void MemoryManager::free_inner(void* p){
	if(p){
		Chunk* it = to_chunk(p);
		it->unref();

		if(!it->prev()->is_used()){
			remove(it->prev());
			it->prev()->set_next(it->next());
			it->next()->set_prev(it->prev());
			it = it->prev();
		}
	
		if(!it->next()->is_used()){
			remove(it->next());
			it->next()->next()->set_prev(it);
			it->set_next(it->next()->next());
		}

		insert(it);
	}
}

MemoryManager::Chunk* MemoryManager::find(Chunk* l, int key){
	Chunk* ret = end();
	while(l!=end()){
		int cmp = key - l->size();

		// 探している大きさより同じか大きいノードを発見
		if(cmp<=0){
			// とりあえず当てはまる大きさのノードは見つけたので保存する
			ret = l; 

			// 基本的に一番左のノードを優先する
			// 左にいくほど、サイズが小さく、小さいアドレスのノードであるため
			l = l->b.left;
		}
		// 探している大きさより小さいノードだった
		else{
			// 右のノードを検索しなくてももう既に当てはまる大きさのノードは見つかっている
			if(ret!=end()){
				return ret;
			}

			l = l->b.right;
		}
	}

	return ret;
}

void MemoryManager::flip_colors(Chunk* n){
	n->flip_color();
	n->b.left->flip_color();
	n->b.right->flip_color();
}

MemoryManager::Chunk* MemoryManager::rotate_left(Chunk* n){
	Chunk* x = n->b.right;
	n->b.right = x->b.left;
	x->b.left = n;
	x->set_same_color(n);
	n->set_red();
	return x;
}

MemoryManager::Chunk* MemoryManager::rotate_right(Chunk* n){
	Chunk* x = n->b.left;
	n->b.left = x->b.right;
	x->b.right = n;
	x->set_same_color(n);
	n->set_red();
	return x;
}

MemoryManager::Chunk* MemoryManager::fixup(Chunk* n){
	if(n->b.right->is_red()){
		n = rotate_left(n);
	}
	
	if(n->b.left->is_red() && n->b.left->b.left->is_red()){
		n = rotate_right(n);
	}
	
	if(n->b.left->is_red() && n->b.right->is_red()){
		flip_colors(n);
	}

	return n;
}

MemoryManager::Chunk* MemoryManager::insert(Chunk* n, Chunk* key){
	if(n==end()){
		return key;
	}

	int cmp = compare(key, n);
	
	if(cmp<0){
		n->b.left = insert(n->b.left, key);
	}
	else{
		n->b.right = insert(n->b.right, key);
	}
	
	if(n->b.right->is_red() && !n->b.left->is_red()){
		n = rotate_left(n);
	}
	
	if(n->b.left->is_red() && n->b.left->b.left->is_red()){
		n = rotate_right(n);
	}
	
	if(n->b.left->is_red() && n->b.right->is_red()){
		flip_colors(n);
	}
	
	return n;
}

void MemoryManager::insert(Chunk* key){
	key->b.right = key->b.left = end();
	key->set_red();

	root_ = insert(root_, key);
	root_->set_black();
}

MemoryManager::Chunk* MemoryManager::minv(Chunk* n){
	while(n->b.left!=end()){
		n = n->b.left;
	}
	return n;
}

MemoryManager::Chunk* MemoryManager::move_red_left(Chunk* n){
	flip_colors(n);
	if(n->b.right->b.left->is_red()){
		n->b.right = rotate_right(n->b.right);
		n = rotate_left(n);
		flip_colors(n);
	}
	return n;
}

MemoryManager::Chunk* MemoryManager::move_red_right(Chunk* n){
	flip_colors(n);
	
	if(n->b.left->b.left->is_red()){
		n = rotate_right(n);
		flip_colors(n);
	}
	return n;
}

MemoryManager::Chunk* MemoryManager::remove_min(Chunk* n){
	if(n->b.left==end()){
		return end();
	}
	
	if(!n->b.left->is_red() && !n->b.left->b.left->is_red()){
		n = move_red_left(n);
	}

	n->b.left = remove_min(n->b.left);
	return fixup(n);
}

MemoryManager::Chunk* MemoryManager::remove(Chunk* n, Chunk* key){
	if(compare(key, n) < 0){
		if(!n->b.left->is_red() && !n->b.left->b.left->is_red()){
			n = move_red_left(n);
		}
		
		n->b.left = remove(n->b.left, key);
	}
	else{
		if(n->b.left->is_red()){
			n = rotate_right(n);
		}
		
		if(n==key && n->b.right==end()){
			return end();
		}
		
		if(!n->b.right->is_red() && !n->b.right->b.left->is_red()){
			n = move_red_right(n);
		}
		
		if(n==key){
			Chunk* x = minv(n->b.right);
			x->b.right = remove_min(n->b.right);
			x->b.left = n->b.left;
			x->set_same_color(n);
			n = x;
		}
		else{
			n->b.right = remove(n->b.right, key);
		}
	}

	return fixup(n);
}

void MemoryManager::dump(unsigned char* dest, size_t size, unsigned char* marks){
	Chunk* p = head_;
	int_t* it = (int_t*)head_;

	size -= 1;

	size_t n = 0;
	while(p!=end()){
		double sz = p->size()*size/(double)buffer_size_;
		size_t szm = (size_t)sz+1;
		if(szm!=0){
			memset(dest+(size_t)n, marks[!p->is_used()], szm);
		}

		n += sz;
		p = p->next();
	}

	size_t m = (size_t)n;
	memset(dest+m, 0, (size+1)-m);
}

void MemoryManager::dump(unsigned char* dest, size_t size){
	unsigned char marks[] = {'O', 'X'};
	dump(dest, size, marks);
}

使用方法は次のとおりです。

char memory[1024*1024*200];
MemoryManager mm(memory, 1024*1024*200);

void* p = mm.molloc(222);

mm.free(p);