AVR Libc Home Page AVRs AVR Libc Development Pages
Main Page FAQ Library Reference Additional Documentation Example Projects

Using malloc()

はじめに

マイクロコントローラのようなシンプルなデバイスでは、動的メモリ割り当ての実装はちょっとした挑戦となります。

avr-libcの対象となる多くのデバイスは最小限のサイズのRAMしか持っていません。C環境でサポートされている最も小さいデバイスではRAMは128バイトしかありません。これをさらに初期化済み・未初期化変数(sections .data と .bss にあたります)、ダイナミックメモリ割り当て、サブルーチンコールやローカル(automatic)変数に使われるスタックで分け合います。

さらに、大きなアーキテクチャーにはあまりない問題として、宣言したRAM領域を他の領域のための書き込みで重ね書きされるのを防ぐ、ハードウェアのメモリ管理機構がないことが挙げられます。

標準的なRAMレイアウトは、まず.data 変数が内蔵RAM領域の先頭に配置され、次に .bssが配置されます。スタックは内蔵RAMの最後尾(最高位アドレス)から始まり、若い番地の方へのびていきます。動的メモリアロケータが利用するいわゆる "heap"は、 .bss の後尾に置かれます。このように、heapとスタックはRAM上変数とはぶつかりません(アロケータにバグがない限りは)。ヒープとスタックについては、両者が多くのメモリを要求したとき衝突するリスクはあります。heapについては動的メモリ割り当てが繰り返された結果断片的になり、要求されたメモリを空きメモリの穴が満たせないときに起こりえます。スタックについては、大きな変数もしくはたくさんの変数を宣言する関数が呼ばれたり、再帰コールがなされたりしたとき起こりえます。

Note:
下図は以下の説明に関連する典型的なATmega128でのRAM配置図を示します。
メモリアドレスはリニアスケールでは表現されていません。
malloc-std.png

内蔵RAMのあるデバイスのメモリマップ

ついに、充分シンプルで、充分小さなコードで動作し、不要なメモリフラグメントを回避するのに充分な機能を持ち、充分少ないCPUサイクルで動作するメモリアロケータ作成への挑戦がなされました。これは今時のPCに比較してメモリも小さく、動作スピードも遅いマイクロコントローラに対応するため必要なことです。

メモリアロケータのavr-libcへの組み込みはこれらの制限を乗り越えなんとかうまくいきました。さらに、標準構成よりもう少し多くのリソースが利用可能なときのためにいくつかのオプションを用意しました。

内蔵 vs. 外付け RAM

もちろん、内蔵RAMでけの標準構成で満足すべき結果を得るには制限はより厳しくなります。スタック−ヒープ衝突を回避するため細心な注意を要します。関数のネストを深くしすぎないこと、ローカル変数確保であまりに大きいスタックスペースを要求しないこと、多すぎる動的メモリ確保を行わないこと、などなど。

外部RAMが利用可能な場合は、また、.data と .bss セクションが外部RAMに置かれるかどうかに関わらず、ヒープ領域を外部RAMに移動することが強く推奨されます。スタックは常に内部RAMに置かれるべきです。いくつかのデバイスはスタックを内部RAMに置くことが要求されますし、内蔵RAMは追加のウェイトなしで高速にアクセスできるからです。動的メモリ確保時、スタックとヒープは明確に分離されたメモリエリアに置かれます。これはスタックヒープ衝突を回避するために最も安全な方法です。

malloc()で調整可能なこと

アプリケーションの要求や制限に対するmalloc() の振る舞いを決定するため、に調整可能なたくさんの変数があります。これらの調整は最初の malloc()コールの前に行われなければなりません。いくつかのライブラリ関数( 標準入出力など)は動的メモリを使用しているかもしれないので、スタートアップシーケンスの充分早期で変更をしなければならないことに注意してください。

変数 __malloc_heap_start__malloc_heap_end は、 malloc() 関数にメモリ領域を確定して制限をかけるために設けられています。これらの変数は静的に__heap_start__heap_end に初期化されています。リンカにより、 __heap_start は .bss 領域の終端に、__heap_end は 0 ( malloc() に対しheapはスタックの手前までと伝える) に設定されています。

ヒープが外部RAMに移動された場合は __malloc_heap_end を適切に調整しなければなりません。これは ランタイムにて値を直接書き込むか、シンボル値 __heap_end を書き換えることによって行われます。

以下の例題はすべての .data と .bss セグメント、及びヒープを外部RAMの0x1100に移動しています。ヒープはアドレス0xffffまで拡張可能です。

avr-gcc ... -Wl,-Tdata=0x801100,--defsym=__heap_end=0x80ffff ...
Note:
なぜ0x800000のオフセットを掛けているか(0xffffではなく0x80ffffである)の理由 については、 gccを使う の章の、 -Wl オプションの説明をお読みください。
malloc-x1.png

内蔵RAM:スタックのみ、外部RAM:変数とヒープ

動的メモリが外部RAMに置かれなければならないが、変数は内部RAMに置きたいという場合は、以下の設定が使用できます。これは説明のために書いたものです。この例題ではおのおのの領域は隣り合ってはいません。そのため、外部RAM上のヒープの前後には通常の変数やメモリ確保では利用不能な「穴」ができてしまいます。(下図で素焼きの色で示した部分)。

avr-gcc ... -Wl,--defsym=__heap_start=0x802000,--defsym=__heap_end=0x803fff ...
malloc-x2.png

内蔵RAM:変数とスタック、外部RAM:ヒープのみ

__malloc_heap_end が 0 なら、アロケータは、動的メモリ確保のためヒープサイズが大きくなったとき、スタックとヒープの衝突を回避するため、スタックの底をチェックしようと試みます。そして現在のスタックリミット(安全のため __malloc_margin バイトだけ減らされている)を越えないようにします。こうなると、現在実行中の関数に割り込む割り込みルーチンや、関数コールは追加のスタックスペースを要求できません。さもないとデータセグメント(※heap含む)との衝突をきたします。
※これは/data/bss/heap→空き←stack/のメモリ割り当て時の話と思われます。上図のheapが外部RAMに置かれた場合の話ではないようです。

__malloc_margin のデフォルト値は 32 です。

実装の詳細

動的メモリ割付要求を行うと、割り当てられたメモリサイズが記録された2バイトのヘッダが前置された領域が渡されます。これは後で free() で使用されます。malloc()で返されるアドレスはちょうどこのヘッダを越えたところを指しています。アプリケーションが誤って返されたメモリ領域より前に書き込んでも、メモリ割り当ての一貫性はなんとか維持されます。??※割り当てられた動的メモリを示す構造はヒープ上にないので安全と言うことでしょうか?
※例えば、ptr = malloc(16);としてptrに0x0074が返った場合、
 その直前の0x0072からの2バイトに確保された領域サイズを表す 00 10 があり、
 ユーザーは0x0074からの16バイトを利用できる。
Dynamic memory allocation requests will be returned with a two-byte header prepended that records the size of the allocation. This is later used by free(). The returned address points just beyond that header. Thus, if the application accidentally writes before the returned memory region, the internal consistency of the memory allocator is compromised.

この実装は簡素なフリーリストを維持します。これにはfree()の呼び出しで返されたメモリブロックも計算に入っています。このメモリの全てがheapに既に加えられている事に注意して下さい。そのため、フリーリストからメモリをリサイクルして再割付した場合はstack-heap衝突の再チェックは必要ありません。

フリーリストそれ自体は分離したデータ構造としては維持されていません。フリーになったメモリ(メモリ領域のかけらをチェーンするポインタを含む)の内容を変更することで行われています。この方法は、リストを維持するための追加のメモリ領域を要求しません(再アロケートの際利用できる最下位メモリセグメントを保持する変数を除く)。チェーンポインタとフリーメモリブロックのサイズの両方が各メモリブロックについて記録される必要があります。ブロックの最小サイズは4バイトになります。

※フリーリストの構造: ( ) 内は各要素のサイズ 
解放前:[size情報(2)] [割り当てられた領域___(割り当てサイズ)----------------------]
解放後:[size情報(2)] [次のフリーエリアのアドレス(2)] [空き領域(割り当てサイズ-2) ]
次のフリーエリアのアドレスは、開放された領域の先頭に書かれる(開放されている間はここは使わない)。

freelist管理ポインタ変数(隠されている)→最初のフリーエリア先頭(size情報部)
最初のフリーエリアの、次のフリーエリアへのアドレス部→次のフリーエリア先頭
  :
最後のフリーエリアの、次のフリーエリアへのアドレス部にはNULLが入る。

メモリを割り当てるときは、まず最初にリクエストを満足させるフリーエリアがあるかどうかフリーリストをチェックします。もしフリーリスト上に要求をちょうど満足させる利用可能なメモリブロックがあれば、これが採用され、フリーリストから切り離され、呼び出し元に返されます。完全に合致するものが無かった場合は、最も近いサイズでリクエストを満たすものが使われます。※要求量以上のメモリサイズで最も小さいものが選ばれる。メモリブロックは通常は呼び出し元へ返されるものとフリーリストの止まるもの(小さい方)に分割されます。このメモリブロックがリクエストよりちょうど2バイト大きい場合は、リクエストは単純に内部的にこの余剰バイト分も含まれるように変更されます。この場合は分離フリーリストエントリが生成できないからです。

フリーリスト内に利用可能なメモリが見つからなかった場合は、ヒープの拡大が試みられます。ヒープがスタックの下で運用されている場合は __malloc_margin が考慮されます。 そうでない場合は __malloc_heap_end がチェックされます。

残りメモリがリクエストを満たすには充分でない場合は、NULLが返されます。

free() をコールする場合は、新しいフリーリストエントリが用意されます。このとき隣接するエントリと合併し、今後のメモリ割り当てに使える1つのより大きなエントリーを生み出すよう試みられます。こうして、ヒープ分断化の可能性は減少すると期待できます。

realloc() の呼び出しは、まず最初にサイズ変更が増大の方向か縮小の方向かを決定します。
縮小の場合は簡単です。現在のメモリブロックを分割し、使われなくなった末尾を free() 関数に渡し、フリーリストに追加します。

領域拡大の場合は、まず現在存在する割り当て領域がその場で拡大できるかチェックします。OKなら実行され、データ内容コピーなしでポインタがそのまま渡されます。副作用として、このチェックはフリーリストの最大のメモリブロックのサイズも記録してしまいます。??As a side-effect, this check will also record the size of the largest chunk on the freelist.
※その場で拡大できる条件=領域がヒープの最上位にある/領域上位側に隣接してフリーブロックがあり、足し合わせると要求を満たす

もし領域がその場では拡大できないが、ヒープトップに古いフリーブロックがあり、新しいフリーリスト探索で要求を満たす充分な大きさのフリーブロックがない場合、最上位のフリーブロックのサイズを拡大(結果、ヒープも拡大される)します。現存するデータをコピーする必要はありません??

ヒープにも充分な容量が無かった場合は( malloc()と同様のチェックがなされ)、全てのリクエストは失敗に終わります。
※heapに拡大の余地がある場合でも、新たにmalloc()で確保してデータをコピーするという動作はrealloc()はやってくれないようです。

別なメモリ領域変更方法として、新しいリクエストサイズで malloc() をコールして、現存するデータをそこにコピーして、その後 free() で古い領域を削除するという方法もあります。


Automatically generated by Doxygen 1.4.1 on 23 Jan 2006.