AVR Libc Home Page AVRs AVR Libc Development Pages
Main Page User Manual FAQ Library Reference Additional Documentation Example Projects
hina.html

メモリエリア解説、malloc()の使い方

Original page is here.

Introduction

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を持つデバイスのRAMメモリマップ

マイクロコントローラのような単純なデバイス上にダイナミックメモリ割当管理を実装するというのは、ちょっとした挑戦でした。
マイクロコントローラはしばしばメモリスペース条件が厳しく、今日の一般的なPCに比べずっと低いスピードで動いているので、コードサイズは十分小さく、不要なメモリ断片化を十分防げる能力を持ち、使いものになるCPUサイクルで実行しなければならないのです。

avr-libcに実装されたメモリ割り当て管理はこれらの制約をなんとか切り抜け、さらに標準状態よりさらにリソースが利用できるチューニングオプションも提供できました。

内蔵RAM 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,--section-start,.data=0x801100,--defsym=__heap_end=0x80ffff ・・・・
Note:
なぜ0x800000のオフセットを掛けているか(0xffffではなく0x80ffffである)の理由 については、 gccを使う の章の、 -Wl オプションの説明をお読みください。
ld (リンカ) のユーザーズマニュアルによると、リンカオプションとして -Tdata=<x> を加えれば、"--section-start,.data=<x>"と同等です。
しかし、上記のように --section-start を使うべきです。その理由は、SRAMが0x800060から始まっていないMCUに対しては、GCCフロントエンドも -Tdata オプションをセットしてしまうからです。リンカは2つの -Tdata オプションに対面してしまいます。binutils 2.16より、リンカは仕様変更しこのような状況を誤ったオプション設定として検出します。

※以前の日本語訳(1.4.3)から変更された部分です。
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含む)との衝突をきたします。
※ これは__malloc_heap_end が 0 の場合 == /data/bss/heap→空き←stack/のメモリ割り当て時の話と思われます。
  上図のheapが外部RAMに置かれた場合の話ではないようです。

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

実装の詳細

動的メモリ割付要求を行うと、割り当てられたメモリサイズが記録された2バイトのヘッダが前置された領域が渡されます。
これは後で free() で使用されます。malloc()で返されるアドレスはちょうどこのヘッダが終わった次のアドレスを指しています。
※例えば、ptr = malloc(16);としてptrに0x0074が返った場合、
 その直前の0x0072からの2バイトに確保された領域サイズを表す 00 10 があり、
 ユーザーは0x0074からの16バイトを利用できる。

アプリケーションが誤って返されたメモリ領域より前に書き込んでも、メモリ割り当ての一貫性はなんとか維持されます。??
※割り当てられた動的メモリを示す構造はヒープ上にないので安全と言うことでしょうか?

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

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

※フリーリストの構造: ( ) 内は各要素のサイズ 
使用中エリアは、malloc取得時に得たアドレスを保存するポインタ変数が把握し、
解放されたフリーエリアは、チェーン構造のフリーリストが把握するという方式。

  解放前:[size情報(2)] [割り当てられた領域___(割り当てサイズ)----------------------]
  解放後:[size情報(2)] [次のフリーエリアのアドレス(2)] [空き領域(割り当てサイズ-2) ]

次のフリーエリアのアドレスは、開放された領域の先頭に書かれる(開放されている間はここは使わない)。
 freelist管理ポインタ変数(隠し変数)→最初のフリーエリア先頭(size情報部)
 最初のフリーエリアの、次のフリーエリアへのアドレス部→次のフリーエリア先頭
 最後のフリーエリアの、次のフリーエリアへのアドレス部にはNULLが入る。
例:
  解放前:[00][01] [---256($0100)バイトの領域-------------] [00][01][--次の領域---]
  解放後:[00][01] [48][20] [---254($00FE)バイトの領域---] [00][01][--次の領域---]
  ※次の空き領域は$2048番地にある

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

フリーリスト内に利用可能なメモリが見つからなかった場合は、ヒープの拡大が試みられます。
ヒープがスタックの下で運用されている場合は __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.

もし領域がその場では拡大できなくて、現在の確保領域??(old chunk)がヒープトップ(※上位アドレス側)にあり、フリーリストをたどっても充分なサイズの空き領域が無かった場合は、ヒープTOP境界の変更により領域の拡大試みられます(結果、ヒープも拡大される)。この場合も現存するデータをコピーする必要はありません。

上記の試みが全て失敗した場合は、新たに要求サイズと同じ領域を新たに確保できないか( malloc()と同様の)チェックをします。
もしそれが可能なら、新しいリクエストサイズで malloc() をコールして領域を確保し、現存するデータをそこにコピーして、その後 free() で古い領域を削除する動作を行います。
領域確保ができなかった場合は、全ての試みは失敗となります。(※realloc()はNULLを返し、現在の確保領域には手を加えずに終わる)