malloc/free

id:higepon が malloc/free のことを日記で書いていたので、BayOS で使っているものを紹介します。といっても自前実装ではなく、MonaWiki/MonaDat にある Mona-20050620-MonaDat.tar.bz2 を改良して使っています。割り当てが早いらしいのと、なによりソースコードがすごく小さいのが採用の理由です。new / delete がこれだけで使えるようになりますので、C++ で OS を書きたいと思っている人におすすめです（アプリプログラマには関係ないですが、メモリの割り当てと解放は OS やライブリーの仕事なので、OS を書く人はこれも自前でやらないとインスタンス１つさえ生成できません）。あと、MonaWiki にある sms_gc を組み合わせるとすごくコンパクトな GC が作れるので、D言語や Java などで OS を書きたいと思っている人にもおすすめです（笑）。ちなみに、メモリ割り当て時にゼロクリアしていないので、危険だとおもったら、g_km.allocate 後にゼロクリアして使ってください。

memory.h

#ifndef _MEMORY_H_
#define _MEMORY_H_

#include "types.h"

typedef struct MemoryInfo {
	dword total, free;
};

class Memory {
private:
	dword start, end, used, firstFree;

public:
	void init(dword size, dword end);
	void* allocate(dword size);
	void free(void* address);
	void get_status(MemoryInfo* minfo);

private:
	dword search_fit(dword size);
	bool check_address(dword ptr, dword* prev);
	void set_next(dword ptr, dword next);
	dword get_next(dword ptr);
};

// カーネルメモリ
extern Memory g_km;

//
// ここから下は C++言語の new / delete サポート
// および C言語の malloc / free サポート
//

void* operator new(size_t size);
void  operator delete(void* address);

#ifdef __cplusplus
extern "C" {
#endif

void* malloc(size_t size);
void free(void * address);

#ifdef __cplusplus
}
#endif

void __builtin_delete(void* address);
void* __builtin_new(size_t size);
void* __builtin_vec_new(size_t size);
void __builtin_vec_delete(void* address);
inline void* operator new(size_t, void* __p) { return __p; }

#endif

memory.cpp

#include "Memory.h"

class MemoryEntry {
public:
	int Size;
	dword Prev, Next;

	inline static void write_used(dword ptr, dword size) {
		*(dword*)ptr = *(dword*)(ptr + size - sizeof(dword)) = size;
	}

	inline static void write_free(dword ptr, dword size, dword prev, dword next) {
		dword* p = (dword*)ptr;
		*(p++) = *(dword*)(ptr + size - sizeof(dword)) = size | 0x80000000;
		*(p++) = prev;
		*p = next;
	}
	
	inline static void write_last(dword ptr, dword prev) {
		dword* p = (dword*)ptr;
		*(p++) = 0;
		*p = prev;
	}
};

void Memory::init(dword start, dword end)
{
	this->start = this->firstFree = start;
	this->end = end;
	this->used = 0;
	MemoryEntry::write_last(this->start, 0);
}

void* Memory::allocate(dword size)
{
	dword sz = (sizeof(dword) + size + sizeof(dword) + 15) & 0xfffffff0; // align16
	dword ptr = this->search_fit(sz);
	if (ptr == 0 || ptr + sz > this->end) return NULL;
	this->used += sz;

	MemoryEntry* h = (MemoryEntry*)ptr;
	dword sz_old = h->Size & 0x7fffffff;
	dword nptr = ptr + sz, prev = h->Prev, next = nptr;
	if (sz_old == 0) {
		MemoryEntry::write_last(nptr, prev);
	} else {
		if (sz < sz_old) {
			MemoryEntry::write_free(nptr, sz_old - sz, prev, h->Next);
			((MemoryEntry*)h->Next)->Prev = nptr;
		} else {
			next = h->Next;
			((MemoryEntry*)next)->Prev = prev;
		}
	}
	MemoryEntry::write_used(ptr, sz);
	this->set_next(prev, next);
	return (void*)(ptr + sizeof(dword));
}

dword Memory::search_fit(dword size)
{
	for (dword p = this->firstFree; p <= this->end; p = ((MemoryEntry*)p)->Next) {
		int sz = ((MemoryEntry*)p)->Size;
		if (sz == 0) {
			return p;
		} else if (sz > 0) {
			break;
		}
		sz &= 0x7fffffff;
		if (size <= (dword)sz) return p;
	}
	return 0;
}

void Memory::free(void* address)
{
	dword ptr = ((dword)address) - sizeof(dword), prev = 0;
	if (!this->check_address(ptr, &prev)) return;
	this->used -= ((MemoryEntry*)ptr)->Size;

	dword sz = *(int*)ptr, next = this->get_next(prev);
	if (ptr > this->start) {
		int psz = *(int*)(ptr - sizeof(int));
		if (psz < 0)
		{
			psz &= 0x7fffffff;
			ptr -= psz;
			sz  += psz;
			prev = ((MemoryEntry*)ptr)->Prev;
		}
	}
	dword nptr = ptr + sz, nsz = *(dword*)nptr;
	if (nsz < 0) {
		sz += nsz & 0x7fffffff;
		next = ((MemoryEntry*)nptr)->Next;
	}

	if (nsz == 0) {
		MemoryEntry::write_last(ptr, prev);
	} else {
		MemoryEntry::write_free(ptr, sz, prev, next);
		((MemoryEntry*)next)->Prev = ptr;
	}
	this->set_next(prev, ptr);
}

bool Memory::check_address(dword ptr, dword* prev)
{
	if (ptr < this->start || ptr > this->end) return false;

	int psz1 = *(int*)ptr;
	if (psz1 < 16 || (psz1 & 15) != 0 || ptr + psz1 > this->end) return false;

	int psz2 = *(int*)(ptr + psz1 - sizeof(int));
	if (psz1 != psz2) return false;

	for (dword p = this->firstFree; p <= ptr; p = ((MemoryEntry*)p)->Next) {
		if (((MemoryEntry*)p)->Size >= 0) return false;
		*prev = p;
	}
	return true;
}

void Memory::set_next(dword ptr, dword next)
{
	if (ptr == 0) {
		this->firstFree = next;
	} else {
		((MemoryEntry*)ptr)->Next = next;
	}
}

dword Memory::get_next(dword ptr)
{
	return ptr == 0 ? this->firstFree : ((MemoryEntry*)ptr)->Next;
}

void Memory::get_status(MemoryInfo* minfo)
{
	minfo->total = this->end - this->start;
	minfo->free  = minfo->total - this->used;
}

//
// ここから下は C++言語の new / delete サポート
// および C言語の malloc / free サポート
//

void* operator new(size_t size)
{
  void* p = g_km.allocate(size);
  return p;
}

void operator delete(void* address)
{
  g_km.free(address);
  return;
}

void* operator new[](size_t size)
{
  void* p = g_km.allocate(size);
  return p;
}

void operator delete[](void* address)
{
  g_km.free(address);
  return;
}

void* malloc(size_t size)
{
  void* p = g_km.allocate(size);
  return p;
}

void free(void * address)
{
  g_km.free(address);
  return;
}

使い方

#include "memory.h"

/* カーネルメモリの初期化 */
Memory g_km;
dword km_start = 0x000200000;
dword km_end   = 0x0007fffff;
g_km.init(km_start, km_end);

/* new / delete */
Test* test = new Test();
delete(test);

/* malloc / free */
char* buff = (char*)malloc(1024);
free(buff);