動的メモリ割り当て入門
ここでは malloc や new などの背後にある動的メモリ割り当ての仕組みについて説明しましょう
はじめに
この頃では初心者といえども STL のコンテナを使ったり new でオブジェクトを動的に確保するようなことはもう当たり前にやっていると思いますが、その仕組みまできちんと理解して使っている人はあまりいないようです
動的に割り当てられるメモリは自動変数の置かれる場所や静的変数が置かれる場所とは違って何か特別なものがあるとなんとなく思っている人も多いのではないでしょうか
また動的に割り当てたメモリを指すポインタは普通のポインタとは何か違う特別なものだと漠然と思っているような人もいるのではないでしょうか
しかし全くそんなことはありません
ヒープ領域というのは別に特別でもなんでもありませんし、そこに確保されるメモリ領域も別に特別でも何でもありません
もちろん malloc や new から返ってきたアドレスやそれを受け取ったポインタ変数も別に特別でも何でもありません
ここでは簡単な動的メモリ確保の仕組みを実際に実装してみることでその理解を深めることとしましょう
用語
ヒープ領域
malloc や new などで動的に確保されるメモリのあるところを一般にヒープ領域と言います
日本語で言えば動的メモリ確保用の予約領域というくらいの意味ですから名前も別に特別でも何でもありませんね
チャンク・メモリブロック
malloc や new などで割り当てられたメモリ領域、まだ割り当てられていないメモリ領域、この個々のメモリ領域のことをチャンクと言ったりメモリブロックと言ったりします
一つ一つのメモリの塊、それぞれのメモリ領域のことです
別に特別な何かではありません
メモリ領域
メモリ領域といっているのはあるアドレスから一定バイト数の範囲の一連のメモリのことです
これも別に特別な何かではありません
動的・静的
動的というのは実行時という意味です
静的というのはコンパイル時という意味です
その他
ポインタの配列の確保はどうするのかとかポインタのポインタの確保はどうするのかといったことを疑問に思っている人はやはりポインタやヒープを何か特別なものだと思っているようです
ポインタ自体については「C/C++ ポインタ入門」を読むといいでしょう
実装
はじめに
動的メモリ割り当ては特別でも何でもないと言いました
そしてヒープ領域もまた特別でも何でもないと言いました
その通り本当に特別でも何でもないのです
これは自分で動的メモリ割り当ての仕組みを実装してみればわかります
まずヒープ領域だのなんだのというのは忘れて、下記のように指定されたサイズのメモリを確保するメソッドを持つクラスを自分で書いてみましょう
int main(){ cheap heap; int* p_int_x100 = static_cast<int*>(heap.alloc( sizeof( int ) * 100 )); char* p_char_x32 = static_cast<char*>(heap.alloc( sizeof( char ) * 32 )); heap.free( p_char_x32 ); heap.free( p_int_x100 ); return 0; }
実装例その１
これはただバッファを用意して指定されたサイズ分だけ空けてあげるというだけの実装です
何も特別なものなんてないですよね
たったこれだけのことで動的なメモリ割り当てができましたね
これでいいんです。malloc や new がやっていることなんて本当にこの程度のことなのです。簡単ですよね
そもそも「メモリを割り当てる」「メモリを確保する」とは一体何のことを言っているのか
これは何か特別なことをすることを指しているわけではありません
この実装にあるように、使っている間は誰にも壊されないことが保証されているメモリの範囲を決めるというだけのことです
class cheap { static const int c_size = 1024; char m_buffer[c_size]; size_t m_offset; public: void* alloc( size_t cb ){ void* result = 0; if( m_offset + cb <= c_size ){ result = &m_buffer[m_offset]; m_offset += cb; } return result; } void free( void* p ){ if( p ){ m_offset = static_cast<size_t>(static_cast<char*>(p) - m_buffer); } } cheap(): m_buffer(), m_offset(0) { } ~cheap(){ } };
ただこんな単純な実装では確保したメモリを解放する順番が制限されてしまっているというところは残念ですね
普通の malloc/free のように解放する順番を気にしなくてもいいようにしてみましょう
実装例その２
解放する順番を任意にできるということは、あるメモリブロックが空いているのか割り当てられているのかという情報と、そのメモリブロックが何バイトなのかという情報が必要になりそうですね
class cheap { static const int c_size = 1024; static const int c_chunks = 1024; struct chunk_header_t { size_t offset; size_t cb; size_t allocated; }; char m_buffer[c_size]; chunk_header_t m_chunks[c_chunks]; void dump(){ std::map<int,const chunk_header_t*> chunks; for( size_t n = 0; n < elementsof( m_chunks ); ++n ){ const chunk_header_t& chunk = m_chunks[n]; if( chunk.cb ){ chunks[chunk.offset] = &chunk; } } for( std::map<int,const chunk_header_t*>::const_iterator p = chunks.begin(); p != chunks.end(); ++p ){ const chunk_header_t& chunk = *p->second; const char* status = chunk.allocated ? " (allocated)" : " (available)"; output_debug_string( "%4d %4d %4d%s\n", chunk.offset, chunk.cb, chunk.allocated, status ); } } public: void* alloc( size_t cb ){ void* result = 0; chunk_header_t* next_chunk = 0; for( size_t n = 0; n < elementsof( m_chunks ); ++n ){ chunk_header_t& chunk = m_chunks[n]; if( !chunk.cb ){ next_chunk = &chunk; // 未使用 } else if( !chunk.allocated &&( cb <= chunk.cb )){ size_t next_chunk_cb = chunk.cb - cb; size_t next_chunk_offset = chunk.offset + cb; size_t m = n; while( !next_chunk || next_chunk->cb ){ next_chunk = &m_chunks[++m]; } next_chunk->offset = next_chunk_offset; next_chunk->cb = next_chunk_cb; chunk.cb = cb; chunk.allocated = cb; result = &m_buffer[chunk.offset]; break; } } if( result ){ output_debug_string( "alloc( %4d )... %4d\n", cb, static_cast<char*>(result) - m_buffer ); dump(); } return result; } void free( void* p ){ if( p ){ size_t offset = static_cast<size_t>(static_cast<char*>(p) - m_buffer ); for( size_t n = 0; n < elementsof( m_chunks ); ++n ){ chunk_header_t& chunk = m_chunks[n]; if( chunk.offset == offset ){ chunk.allocated = 0; output_debug_string( "free( %4d )\n", offset ); dump(); break; } } } } cheap(): m_buffer(), m_chunks() { m_chunks[0].cb = sizeof( m_buffer ); dump(); } ~cheap(){ } };
int main(){ srand( static_cast<unsigned int>(time( 0 ))); cheap heap; std::vector<void*> allocated; for( int n = 0; n < 1000; ++n ){ int r = static_cast<size_t>(rand()); size_t cb = r % 1024; if( cb ){ void* p = heap.alloc( cb ); if( p ){ allocated.push_back( p ); } else if( !allocated.empty()){ int m = r % allocated.size(); std::vector<void*>::iterator p = allocated.begin(); std::advance( p, m ); heap.free( *p ); allocated.erase( p ); } debug_sleep(); } } for( std::vector<void*>::iterator p = allocated.begin(); p != allocated.end(); ++p ){ heap.free( *p ); } return 0; }
この例では割り当てられるメモリブロックの数の上限が決まっています
割り当て用のバッファが 1024バイトなので 1バイトづつ 1024個割り当てる場合を想定して管理領域を 1024個取っています
割り当てられるメモリの何倍もの管理領域を使っていてとても無駄ですね
しかし管理領域をあまり少なくすると今度はメモリは余っているのに管理領域が足りなくてメモリを割り当てられないということが起こりそうです
管理領域の上限をいくつにしておくのが適切でしょうか
といってもそんなものは場面場面で変わるのでいくつが最適というような答はありません
この実装ではそうした問題がありますということです
本来であればメモリがあるならあるだけ割り当てられるようにしたいですね
ではそのように書き直してみましょう
実装例その３
メモリがあればあるだけというのはどうすれば実現できるでしょうか
割り当て用のメモリ領域と管理領域を別にしている限りは管理領域の上限の問題が出てくるので、ここは一緒にしてしまいましょう
ぱっと思いつくところでは方法は２つあります
一つはメモリ領域の上下どちらかを管理領域に、もう片方を割り当て用の領域にすることで、両者がぶつかるまで割り当てられるという仕組みです
もう一つは個々のメモリ領域の前に管理領域をくっつける仕組みです
ここでは後者で実装してみましょう
class cheap { static const int c_size = 1024; char m_buffer[c_size]; struct chunk_header_t { size_t cb; size_t allocated; }; void dump(){ std::map<int,const chunk_header_t*> chunks; chunk_header_t* p = reinterpret_cast<chunk_header_t*>(m_buffer); do{ const char* status = p->allocated ? " (allocated)" : " (available)"; output_debug_string( "%4d %4d %4d%s\n", reinterpret_cast<char*>(p) - m_buffer, p->cb, p->allocated, status ); p = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + p->cb ); }while( reinterpret_cast<char*>(p) < &m_buffer[sizeof( m_buffer )] ); } public: void* alloc( size_t cb ){ void* result = 0; chunk_header_t* p = reinterpret_cast<chunk_header_t*>(m_buffer); do{ if( !p->allocated ){ if( sizeof( chunk_header_t ) + cb + sizeof( chunk_header_t ) < p->cb ){ // 分割できるなら分割する chunk_header_t* p_next = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + sizeof( chunk_header_t ) + cb ); p_next->cb = p->cb - ( sizeof( chunk_header_t ) + cb ); p_next->allocated = 0; p->cb = sizeof( chunk_header_t ) + cb; p->allocated = cb; result = &p[1]; } else if( sizeof( chunk_header_t ) + cb <= p->cb ){ // 分割できないならそのまま使う p->allocated = cb; result = &p[1]; } } p = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + p->cb ); }while( !result &&( reinterpret_cast<char*>(p) < &m_buffer[sizeof( m_buffer )] )); if( result ){ output_debug_string( "alloc( %4d )... %4d\n", cb, ( static_cast<char*>(result) - m_buffer ) - sizeof( chunk_header_t )); dump(); } return result; } void free( void* p ){ if( p ){ size_t offset = static_cast<size_t>(static_cast<char*>(p) - m_buffer ); offset -= sizeof( chunk_header_t ); chunk_header_t* p = reinterpret_cast<chunk_header_t*>(&m_buffer[offset]); p->allocated = 0; output_debug_string( "free( %4d )\n", !p ? 0 : reinterpret_cast<char*>(p) - m_buffer ); dump(); } } cheap(): m_buffer() { reinterpret_cast<chunk_header_t*>(m_buffer)->cb = sizeof( m_buffer ); dump(); } ~cheap(){ } };
これでメモリの割り当てと解放の順番も管理領域の数も気にせずに使えるようになりました
しかしログを見てお分かりのことと思いますが、この実装ではメモリ割り当てを繰り返していると割り当て可能なメモリの大きさがどんどん小さくなっていってしまっていますね
これはなぜでしょう
これは解放されたメモリが割り当てられたときの大きさを保った状態のまま残っているためです
連続した空きメモリブロックはまとめて一つの大きな空きメモリブロックにしてほしいところですよね
ではそのように書き直してみましょう
実装例その４
連続した空きメモリブロックをまとめるといってもいつまとめればいいのでしょうか
ガーベイジコレクタのように適当に空いている時間を見つけてまとめればいいのでしょうか
いえそんなことをする必要はありません
個々のメモリブロックを解放するときに必ず前後の空きブロックをまとめる処理をするなら、空きブロックは常に１つだけ孤立した状態にあるはずで、空きメモリが連続して在るという状態には決してなりません
ですからメモリを解放するときに前後のブロックが空いていたら一つにまとめるというだけで構いません
class cheap { static const int c_size = 1024; char m_buffer[c_size]; struct chunk_header_t { size_t cb; size_t allocated; size_t prev; }; void dump(){ std::map<int,const chunk_header_t*> chunks; chunk_header_t* p = reinterpret_cast<chunk_header_t*>(m_buffer); do{ const char* status = p->allocated ? " (allocated)" : " (available)"; output_debug_string( "%4d %4d %4d %4d%s\n", reinterpret_cast<char*>(p) - m_buffer, p->prev, p->cb, p->allocated, status ); p = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + p->cb ); }while( reinterpret_cast<char*>(p) < &m_buffer[sizeof( m_buffer )] ); } public: void* alloc( size_t cb ){ void* result = 0; chunk_header_t* p = reinterpret_cast<chunk_header_t*>(m_buffer); do{ if( !p->allocated ){ if( sizeof( chunk_header_t ) + cb + sizeof( chunk_header_t ) < p->cb ){ // 分割できるなら分割する chunk_header_t* p_next = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + p->cb ); chunk_header_t* p_next_new = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + sizeof( chunk_header_t ) + cb ); if( reinterpret_cast<char*>(p_next) < &m_buffer[sizeof( m_buffer )] ){ p_next->prev = static_cast<size_t>(reinterpret_cast<char*>(p_next_new) - m_buffer); } p_next_new->cb = p->cb - ( sizeof( chunk_header_t ) + cb ); p_next_new->allocated = 0; p_next_new->prev = static_cast<size_t>(reinterpret_cast<char*>(p) - m_buffer); p->cb = sizeof( chunk_header_t ) + cb; p->allocated = cb; result = &p[1]; } else if( sizeof( chunk_header_t ) + cb <= p->cb ){ // 分割できないならそのまま使う p->allocated = cb; result = &p[1]; } } p = reinterpret_cast<chunk_header_t*>( reinterpret_cast<char*>(p) + p->cb ); }while( !result &&( reinterpret_cast<char*>(p) < &m_buffer[sizeof( m_buffer )] )); if( result ){ output_debug_string( "alloc( %4d )... %4d\n", cb, ( static_cast<char*>(result) - m_buffer ) - sizeof( chunk_header_t )); dump(); } return result; } void free( void* p_to_free ){ if( p_to_free ){ size_t offset = static_cast<size_t>(static_cast<char*>(p_to_free) - m_buffer ); offset -= sizeof( chunk_header_t ); chunk_header_t* p = reinterpret_cast<chunk_header_t*>(&m_buffer[offset]); p->allocated = 0; chunk_header_t* p_prev = reinterpret_cast<chunk_header_t*>(&m_buffer[p->prev]); chunk_header_t* p_next = reinterpret_cast<chunk_header_t*>(reinterpret_cast<char*>(p) + p->cb); if(( reinterpret_cast<char*>(p_next) < &m_buffer[sizeof( m_buffer )] )&& !p_next->allocated ){ // 直後が空いているなら統合する p->cb += p_next->cb; } if(( p_prev != p )&& !p_prev->allocated ){ // 直前が空いているなら統合する p_prev->cb += p->cb; p = p_prev; } p_next = reinterpret_cast<chunk_header_t*>(reinterpret_cast<char*>(p) + p->cb); if( reinterpret_cast<char*>(p_next) < &m_buffer[sizeof( m_buffer )] ){ // 直後の直前は自分 p_next->prev = static_cast<size_t>(reinterpret_cast<char*>(p) - m_buffer); } output_debug_string( "free( %4d )\n", reinterpret_cast<char*>(p) - m_buffer ); dump(); } } cheap(): m_buffer() { reinterpret_cast<chunk_header_t*>(m_buffer)->cb = sizeof( m_buffer ); dump(); } ~cheap(){ } };
これで無駄に連続した空きメモリがあるという状態にならないようにできました
この程度ではまだまだ製品レベルには遠く及ばないのですが、しかし malloc や new を呼んだときにその背後でどんな処理が動いているのかということは大分見えてきたのではないでしょうか
この cheap クラスの allocメソッドが返すポインタは m_buffer のどこかを指すポインタです
それはただメンバ変数の中を指しているだけで特別でもなんでもありません
ヒープとは
はじめに戻って「ヒープ領域」とは何のことでしょうか
ヒープ領域は malloc や new などで動的に確保されるメモリのあるところであると言いました
ここで今まで書いてきた cheap::alloc で確保されるメモリはすべて cheap::m_buffer の中にあります
ですからヒープ領域とはこの cheap::m_buffer のようなもののことです
cheapクラスはヒープ領域である m_buffer を管理するものなのでヒープマネージャと言ったり、動的にメモリを確保する仕組みを提供するのでメモリアロケータと言ったりします
ヒープ領域だヒープマネージャだと難しそうな言葉で言っても何か特別なものであるわけではなく、ただのクラスとそのメンバ変数です
動的メモリ確保なんてこんなものです
どうでしょうわかってみれば簡単なことじゃないですか
余談
さてここからは余談ですが、ここまで書いてきたメモリアロケータ・ヒープマネージャが製品レベルとなるためにはさらにどのような機能が必要なのかといったことについて考えてみましょう
0バイト割り当てへの対応
こちらは別に実用上問題があるわけではないのですが、malloc などの規格では 0バイトを割り当てることもできるようになっているので対応しておくか、あるいは assert を入れておくなどした方がいいでしょう
realloc対応
ここまでの実装には alloc と free だけあって realloc がありません
realloc的なものは何か用意しておいた方がいいでしょう
対数時間での割り当て
メモリを割り当てるときには先ず空いているメモリブロックを見つける必要があるわけですが、これまでの実装では先頭のメモリブロックから順番にこれはどうかな空いてないかなと探していました
しかしそれでは管理するメモリブロックが増えれば増えただけ検索に時間がかかってしまいます
そこで通常はツリー構造を導入して対数時間で検索できるようにします
それも単なる平衡二分木ではなくサイズごとの平衡三分木と同じサイズ用にアドレスで分ける平衡二分木を組み合わせたようなものなどを使います
ここをどのような構造にするかがパフォーマンスに大きな影響を与えるのでここはしっかりと設計する必要があります
マルチスレッド対応
今までの実装はマルチスレッドを考慮していませんが通常はマルチスレッド環境でも問題なく動くものが要求されます
そこで各メソッドには排他処理を導入する必要が出てきます
フラグメンテーション（断片化）対策
特に組み込み系では重要な問題です
現在の実装ではフラグメンテーション対策は何も考慮されていません
これは次のメモリアラインメントの指定や小さいメモリへの対応と重複する部分もありますが、割り当てるメモリの性質に応じて仕分ける仕組みなどがあるといいでしょう
メモリアラインメント（境界）に関する機能
ここまでの実装ではメモリのアラインメントについては何も考慮されていませんが、通常は例えば４バイト境界などといった一定の境界を考慮した作りになっている必要があります
またメモリ割り当て時に必要なメモリ境界を指定できたりする機能が必要になることも多いでしょう
小さいメモリへの対応
４バイトのメモリを割り当てるのに管理領域が１００バイトも２００バイトもあったのではメモリが無駄になりますね
そこで４バイトだとか１６バイトだとかいった管理領域の大きさより小さいようなメモリを割り当てるためには特別な仕組みが必要になります
簡単なのは例えば４バイト割り当て用に４バイトを３１個と１ビットずつの管理領域を３１ビット用意するというようなものです
