Chapter 2 ヒープメモリ管理(Heap Memory Management) (FreeRTOS チュートリアル日本語訳)

この記事について

Mastering the FreeRTOS Real Time Kernel-A Hands-On Tutorial Guildの日本語訳

Pros/Consまとめ（チュートリアルに記載されてはいない。内容を自分でまとめたもの。）

	heap_1	heap_2(heap_4のfree時結合なしバージョン)	heap_3(libcのmalloc/free)	heap_4	heap_5(heap_4で複数のRAM領域を使えるバージョン)
サイズの定義	configTOTAL_HEAP_SIZE	configTOTAL_HEAP_SIZE	リンカの設定次第	configTOTAL_HEAP_SIZE	configTOTAL_HEAP_SIZE
Allocアルゴリズム	freeしないので先頭から順番	Best Fit(要求サイズに一番近いブロック)		First Fit(要求サイズを満たす一番早く見つけたブロック)	First Fit
Free可能か？	x	o	o	o	o
deterministic(決定的)	o	x	x	x	x
フラグメンテーション	発生しない	発生する	発生する	発生する	発生する
Free時のフラグメンテーション防止	-	しない		隣接freeブロックを1つに結合する	隣接freeブロックを1つに結合する
run time時のアロケート失敗	発生しない	発生する	発生する	発生する	発生する
libc malloc/freeより早い？	o	o	-	o	言及無し
heap用のRAMを複数領域指定できるか？	x	x	x	x	o
おすすめシステム	小規模、クリティカルなシステム	同じサイズのalloc/freeを繰り返す	言及無し	alloc/freeを繰り返す	使えるRAM領域が離散的

Chapter 2 ヒープメモリ管理

2.1 イントロダクション、スコープ

FreeRTOSはCで提供されます。CプログラマーであることがFreeRTOSを使える前提条件です。
このチャプタでは以下の知識を前提とします
・Cがどのようにコンパイル、リンクしてビルドされるか
・ヒープとスタックとは何か
・libcのmalloc

動的なメモリアロケーションとFreeRTOSとの関係

FreeRTOS Ver.9.0.0から、カーネルはコンパイル時に静的にアロケートすることもできます。
この章では、task, queue, semaphore, event groupsなどのカーネルオブジェクトを紹介します。FreeRTOSをできるだけ簡単に使うには、カーネルオブジェクトはコンパイル時に静的に確保するのではなく、ラインタイム時に動的に確保する。
FreeRTOSはカーネルオブジェクトが生成されるたびにRAMを確保し、破棄されるたびに解放する。
この方針は設計を簡単にして、APIを単純にし、RAMの使用量を最小化する。

このチャプターでは動的なメモリアロケーションについて説明する。動的アロケーションはC言語のコンセプトであり、FreeRTOSやマルチタスキングの仕様ではない。
FreeRTOSカーネルオブジェクトが動的にアロケートされるので関係してくる。また、一般的な目的による動的メモリアロケーションはリアルタイムシステムにおいては最適であるとは限らない。

メモリは標準Cのmalloc(), free()でアロケートされる。ただしこれらは以下の理由で最適でないことがある。

• 小さな組み込みシステムではいつも利用可能なわけではない
• 実装サイズが大きいので、貴重なコードのスペースを占有してします。
• スレッドセーフであることがほとんどない
• 決定的でない。関数の実行時間が呼び出すたびに変わる
• フラグメンテーション
• リンカコンフィギュレーションを複雑にする
• ヒープ領域が他の変数を壊すようなときには、デバッグが困難

動的メモリアロケーションの選択肢

初期のFreeRTOSはメモリプールアロケーションスキームを使っていた。そのため、異なるサイズのメモリブロックがコンパイル時にアロケートされ、メモリアロケーション関数が返していた。これはリアルタイムシステムでは一般的な方法だが、圧倒的に多くのサポート要求が来る。なぜなら、RAMを効率的に使わないので、小さな組み込みシステムでは致命的になる。そのため、このスキームは非採用となった。

今のFreeRTOSはportable layer(core codeでない)でメモリアロケーションを扱っている。

portable layerは各port(コンパイラとプロセッサアーキの組み合わせ)専用のソースコード
これは異なる組み込みシステムでは動的メモリアロケーションとタイミング制約を持っているため、1つのメモリアロケーションアルゴリズムの場合アプリケーションの1つのサブセットのみに最適になってしまう、ことを認識しているためです。
また、core codeから除外したのは、必要な場合には開発者に最適な実装をできるようにするためです。

FreeRTOSがRAMを要求するときには、malloc()ではなくpvPortMalloc()を呼ぶ。解放するときにはfree()でなくvPortFree()を呼ぶ。
pvPortFree()はmallocと同じIFを持っている。pvPortFreeはFree()と同じIFを持っている。

pvPortMalloc(), pvPortFree()はpulbic関数なので、アプリケーションからも呼べます。

pvPortMalloc(), pvPortFree()の5つの実装例はこのチャプターで説明します。
5つの例は、heap_1.c, heap_2.c, heap_3.c, heap_4.c, heap_5.c で定義されています。
ソースコードはそれぞれ、FreeRTOS/Source/portable/MemMang ディレクトリにあります。

スコープ

このチャプターでは以下の理解を目指します

• いつFreeRTOSがRAMをアロケートするのか
• 5つのメモリアロケーションスキーム
• 5つのスキームの選び方

2.2 メモリアロケーションスキームの例

Heap_1

これはスケジューラーが動く前に、タスクや他のカーネルオブジェクトを生成するような小さい組み込みシステムで一般的な方法です。
アプリケーションがリアルタイム機能を開始する前に、一度だけメモリはアロケートされ、アプリケーションのライフタイム中はアロケートが維持されます。
アプリケーションは決定論、フラグメンテーション、アロケート失敗など、メモリに関する問題を考える必要がありません。
代わりにコードサイズの特性を考えればよいです。

Heap_1.cはpvPortMalloc()の基本バージョンです。vPortFreeは実装されていません。
タスクや他のカーネルオブジェクトを破棄することがないアプリケーションはHeap1.cを使える可能性があります。

いくつかの商業的でクリティカルなシステムは、ダイナミックアロケーションの代わりに、heap_1.cを使う可能性があります。クリティカルシステムは大抵動的メモリアロケーションを禁止しています。予期せぬ決定論、フラグメンテーション、アロケーション失敗を防ぐためにです。heap_1.cは常に決定的でフラグメンテーションを起こしません。

heap_1はpvPortMallocが呼ばれると単純なarrayをより小さなブロックに分けます。このarrayはFreeRTOSヒープと呼ばれます。

arrayのトータルサイズは、configTOTAL_HEAP_SIZE(FreeRTOSConfig.h)によって定義されます。大きなarrayは何もメモリをアロケートしていなくても、アプリケーションが大きなRAMを消費しているように見えます。

Figure 5参照：

• "A"はどのタスクも生成される前です。すべてのarrayは解放されています。
• "B"は1つのタスクが生成されたあとです。
• "C"は3つのタスクが生成されたあとです。

Heap_2

Heap_2はFreeRTOSディストリビューションの後方互換のために維持しています。新しい設計には推奨しません。
heap_4を使うことを検討してください。heap_4はheap_2を強化した機能です。

Heap_2.cもまたconfigTOTAL_HEAP_SIZEで設定したarrayを分割します。
best fit algorithm(要求に合うブロックで最小のサイズを選ぶ)を使っていて、heap_1と違いメモリをfreeすることが許されています。
ただし、同じように何もアロケーションしていなくてもRAMは消費します。

best fit algorithmはpvPortMallocは要求されたサイズに最も近いブロックを使うことを保証します。例えば

• ヒープが5byte, 25byte, 100byteの3ブロック持っている
• pvPortMallocで20byte要求される

この時にはリクエストに一番近いのは25byteのブロックとなり、pvPortMallocは25byteのブロックを20byte, 5byteのブロックに分けて、20byteブロックのポインターを返す。
新しい5byteブロックは、pvPortMallocが再度呼ばれたときに利用可能となっている。

heap_4と違ってheap_2は2つのブロックをくっつけて、1つの大きなブロックにすることはしない。そのため、よりフラグメンテーションの影響を受けやすい。
しかし、ブロックがアロケートされてからフリーまでがいつも同じサイズで行われれば、フラグメンテーションは問題とはならない。Heap_2はスタックサイズが変化しないタスクを繰り返し消すようなアプリケーションに適している。

Figure 6にbest fit algorithmがどのように動作するのか示す。タスクを生成、破棄また生成したケース。

• "A"は3つのタスクが生成された後を示す。大きなfreeブロックはarrayのトップに維持されている。
• "B"はタスクの1つが破棄された状態を示す。topの大きなfreeブロックのほかに、TCB, スタックのfreeブロックができた
• "C"は他のタスクが生成された状態をしめす。タスク生成は2回のpvPortMalloc()呼び出しにつながる。1つはTCB、もう一つはスタック。タスクは3.4セクションで説明するxTaskCreate() APIで生成される。pvPortMalloc()はxTaskCreateの内部で呼ばれる。
• すべてのTCBは完全に同じサイズなので、best fit algorithmは新しいタスクで再利用できることを保証できる
• 新しいタスクのスタックのサイズが古いタスクのサイズと同一であれば、、best fit algorithmは新しいタスクで再利用できることを保証できる
• topにある大きいfreeブロックは触れずに維持できている

Heap_2は決定的ではないが、ほとんどの標準的なmalloc, freeよりは動作が速い。

Heap_3

Heap_3.cは標準Cライブラリのmalloc, freeを使う。そのためヒープサイズはリンカの設定で決まり、configTOTAL_HEAP_SIZEは影響しない。

Heap_3は一時的にスケジューラーをサスペンドして、malloc, freeをスレッドセーフにする。スレッドセーフとスケジューラサスペンションに関してはチャプター7で扱う。

Heap_4

heap_1, heap_2と同じようにarrayをブロックに分割する。事前にarrayはconfigTOTAL_HEAP_SIZEで計算され、静的に宣言される。
何もアロケーションしていなくてもRAMは消費する。

Heap_4はfirst fit algorithmをアロケーションに使っている。heap_2と違ってheap_4はfreeブロックを調整して1つの大きなブロックを作る。これはフラグメンテーションリスクを最小化できる。

first fit algorithmはpvPortMallocがリクエストの合ったサイズに対して十分大きいメモリで最初のブロックをアロケーションすることを保証する。たとえば

• ヒープは3つのfree blockを持っている。順番は5byte, 200byte, 100byte。
• pvPortMalloc()は20byteのリクエストを受けた

最初にfitするのは200byteのブロックなので、pvPortMallocは200byteのブロックを20byte, 180byteに分けて、20byteをreturnする。
新しい180byteのブロックは次のpvPOrtMallocで使用できる。

Heap_4はfree blockを1つの大きなブロックに調整し、フラグメンテーションリスクを最小化できる。異なるRAMサイズのアロケートとフリーを繰り返すアプリケーションに最適なスキームとなっている。

Figire 7に動作例を示す。

• "A"は3つのタスクを生成した状態を示す。topの大きなfreeブロックは維持されている。
• "B"は1つのタスクを破棄した状態。topの大きなfreeブロックは維持されている。ここではTCB, スタックが破棄された場所がfreeブロックになっている。heap_2と違って、TCBが消されたときにメモリはフリーされ、スタックが消されたときにメモリはフリーされ、2つのブロックが残らずに結合された1つのブロックが残る。
• "C"はxQueueCreate()でキューが生成された状態。heap_4のfirst fit algorithmによって、pvPortMallocは十分なサイズがある中で最初のfreeブロックからアロケートする。このキューはブロックすべてを使用するのではなく、ブロックを分割して必要なサイズだけ使う。使われない方のブロックは次のpvPortMallocで再利用できる。
• "D"はアプリケーションコードから直接pvPOrtMallcoが呼ばれたパターン。freeブロックの中でのfirst fitブロックをアロケートする。ここでもともとタスクがあった領域は3つに分割された。3つの領域はfreeブロックを維持している。
• "E"はキューが破棄された状態。ユーザーアロケートブロックの両サイドにfreeブロックが存在する
• "F"はユーザーメモリがフリーされた状態。両サイドのブロックを合わせて、大きな１つのブロックにしている。

heap_4はdeterminisiticではないが、ほとんどの標準ライブラリのmalloc, freeより早く動く。

Heap_4で使われるArrayのスタートアドレス設定

このセクションでは上級レベルの情報を含む。Heap_4を使うために必ずしも必要でない。

時々、アプリケーション開発者はheap_4で使うarrayを特定のアドレスに置きたいことがある。例えばFreeRTOSタスクのスタックをヒープからとる場合には、外部の遅いメモリより内部の早いメモリにヒープを配置したい。

デフォルトでは、heap_4で使うarrayはheap_4.cで宣言され、スタートアドレスはリンカによって自動的に決まる。しかしconfigAPPLICATION_ALLOCATED_HEAP(FreeRTOSConfig.h)を1にすると、arrayは代わりにアプリケーション側で宣言できる。arrayがアプリケーションの一部であれば、開発者はスタートアドレスを設定できる。

configAPPLICATION_ALLOCATED_HEAPが1の場合には、uint8_t arrayを ucHeapと呼ぶ。 configTOTAL_HEAP_SIZE もアプリケーションで宣言する必要がある。

特定のアドレスに変数を置くシンタックスはコンパイラに依存するので、コンパイラのドキュメントを参照すること。2つのコンパイラの例を挙げる。

Heap_5

heap_5で使われるアルゴリズムは、heap_4と同一となる。heap_4と違ってheap_5ではアロケートされるメモリは1つの静的に宣言したarrayだけに限定されない。
つまりheap_5は複数の分離した領域からアロケート可能である。Heap_5はRAMばシステム制約で、1つの連続する領域に見えない時に有用である。

コードを書く時には、heap_5はpvPortMallocが呼ばれる前に、アロケーションスキームを明示的に初期化するだけで良い。
Heap_5はvPortDefineHeapRegions APIで初期化される。heap_5が使うときには、カーネルオブジェクトが生成されるまえにvPortDefineHeapRegionsを呼ぶ必要がある。

vPortDefineHeapRegion() API関数

vPortDefineHeapRegionは、それぞれの領域のスタートアドレスを設定する必要がある。heap_5はそれらを合わせて使う。
それぞれの分かれたメモリ領域はHeapRegion_tで記載される。

void vPortDefineHeapRegions(const HeapRegion_t * const pxHeapRegions);
typedef struct HeapRegion 
{ 
    /* The start address of a block of memory that will be part of the heap.*/ 
    uint8_t *pucStartAddress; 
 
    /* The size of the block of memory in bytes. */ 
    size_t xSizeInBytes; 
 
} HeapRegion_t; 
/*
pxHeapRegions :
HeapRegion構造体配列へのポインタ。各構造体はスタートアドレスと長さが記載される。
HeapRegion_t構造体はstartアドレスから順に置かれなければならない。つまりメモリが一番小さいアドレスからスタートする構造体を配列の最初に置く必要がある。
最も大きいアドレスは最後の要素にする。
構造体の最後はNULLでマーキングすること。
*/

例を使って、Figure 8のような仮想的なメモリマップを考える。マップはRAM1, RAM2, RAM3を含んでいる。
実行ファイルはread onlyメモリに置かれて、図には出てこないとする。

Listing 6にHeapRegion_t構造体を示す。

/* Define the start address and size of the three RAM regions. */ 
#define RAM1_START_ADDRESS    ( ( uint8_t * ) 0x00010000 ) 
#define RAM1_SIZE             ( 65 * 1024 ) 
 
#define RAM2_START_ADDRESS    ( ( uint8_t * ) 0x00020000 ) 
#define RAM2_SIZE             ( 32 * 1024 ) 
 
#define RAM3_START_ADDRESS    ( ( uint8_t * ) 0x00030000 ) 
#define RAM3_SIZE             ( 32 * 1024 ) 
 
/* Create an array of HeapRegion_t definitions, with an index for each of the three 
RAM regions, and terminating the array with a NULL address.  The HeapRegion_t 
structures must appear in start address order, with the structure that contains the 
lowest start address appearing first. */ 
const HeapRegion_t xHeapRegions[] = 
{ 
    { RAM1_START_ADDRESS, RAM1_SIZE }, 
    { RAM2_START_ADDRESS, RAM2_SIZE }, 
    { RAM3_START_ADDRESS, RAM3_SIZE }, 
    { NULL,               0         }  /* Marks the end of the array. */ 
}; 
 
int main( void ) 
{ 
    /* Initialize heap_5. */ 
    vPortDefineHeapRegions( xHeapRegions ); 
 
    /* Add application code here. */ 
} 

Listing 6はこのRAMの正しい記述ですが、デモとして動作しません。すべてのRAMがheapとしてアロケートされ、他の変数用の領域がないからです。

プロジェクトをビルドしたときに、リンクでRAMアドレスはそれぞれの変数に割り当てされます。
通常RAMの仕様設定はリンカスクリプトのようなコンフィギュレーションファイルに記述されます。
Figure BではリンカスクリプトはRAM1の情報は含んでいるが、RAM2, RAM3は含んでいないと仮定しています。
そのためリンカーはRAM1に変数を置いて、0x0001nnnnがheap_5によって利用可能になります。実際のアドレス値はアプリケーションに含まれる変数のサイズに依存します。
リンカーはRAM2, RAM3は使用しないので、RAM2, RAM3のすべてはheap_5によって利用可能となります。

Listing 6のコードの場合、heap_5に割り当てられたRAMの0x0001nnn以下は、変数保持領域にオーバーラップします。これを避けるにはHeapRegion_t構造体の最初の要素のスタートアドレスを0x0001nnnnにします。しかし、これは以下の理由で推奨された解決法ではありません。

• スタートアドレスを決めることが難しい
• リンカによって使うRAMサイズは後のビルドで変更される可能性がある。スタートアドレスのアップデートが必要とされることがある。
• ビルドツールはこのことを知らないので、もしオーバーラップしていても、開発者に警告が出せない。

Listing 7は便利で維持しやすい例のデモです。ucHeapを宣言します。ucHeapは普通の変数で、リンカによってRAM1の一部としてアロケートされます。
HeapRegion_t構造体最初の要素は、スタートアドレスをucHeapにします。ucHeapはheap_5で管理されることになります。
ucHeapのサイズはFigure 8のCのように、リンカがRAM1のすべてを消費するまでは増えます。

Listing7

/* Define the start address and size of the two RAM regions not used by the  
linker. */ 
#define RAM2_START_ADDRESS    ( ( uint8_t * ) 0x00020000 ) 
#define RAM2_SIZE             ( 32 * 1024 ) 
 
#define RAM3_START_ADDRESS    ( ( uint8_t * ) 0x00030000 ) 
#define RAM3_SIZE             ( 32 * 1024 ) 
 
/* Declare an array that will be part of the heap used by heap_5.  The array will be 
placed in RAM1 by the linker. */ 
#define RAM1_HEAP_SIZE ( 30 * 1024 ) 
static uint8_t ucHeap[ RAM1_HEAP_SIZE ]; 
 
/* Create an array of HeapRegion_t definitions.  Whereas in Listing 6 the first entry 
described all of RAM1, so heap_5 will have used all of RAM1, this time the first 
entry only describes the ucHeap array, so heap_5 will only use the part of RAM1 that 
contains the ucHeap array.  The HeapRegion_t structures must still appear in start 
address order, with the structure that contains the lowest start address appearing 
first. */ 
const HeapRegion_t xHeapRegions[] = 
{ 
    { ucHeap,             RAM1_HEAP_SIZE }, 
    { RAM2_START_ADDRESS, RAM2_SIZE }, 
    { RAM3_START_ADDRESS, RAM3_SIZE }, 
    { NULL,               0         }  /* Marks the end of the array. */ 
}; 

Listing 7のテクニックは以下の利点があります。

• スタートアドレスをハードコーディングする必要がない。
• HeapRegion_t構造体のアドレスがリンカによって自動的に決まる。リンカの使うRAMサイズが変わってもアドレスは常に正しい。
• heap_5のRAMがリンカによって配置されたRAM上のデータをオーバーラップしない
• ucHeapが大きすぎる場合は、アプリケーションはリンクされない（不具合に気づける）

2.3 ヒープに関連したユーティリティ関数

xPortGetFreeHeapSize API関数

PortGetFreeHeapSizeはヒープのフリー領域のバイト数を返す。これはヒープの最適化に使えます。
例えば、すべてのカーネルオブジェクトが生成された後にPortGetFreeHeapSizeが2000を返した場合、configTOTAL_HEAP_SIZE は2000減らすことが可能です。
PortGetFreeHeapSizeはheap_3では使えません。

heap_3はcのmalloc, freeを使うからかな

Listing8

size_t xPortGetFreeHeapSize( void ); 
// 戻り値 : The number of bytes that remain unallocated in the heap at the time xPortGetFreeHeapSize() is called. 

xPortGetMinimumEverFreeHeapSize() API関数

xPortGetMinimumEverFreeHeapSizeはFreeRTOSアプリケーションが実行開始してから、アロケートされていないヒープの量の最小値を返す。

xPortGetMinimumEverFreeHeapSizeはアプリケーションがどれだけヒープを使い切りそうかを示す。たとえばxPortGetMinimumEverFreeHeapSizeが200を返すと、アプリケーションが開始されてから、残りのヒープが200byteになったことがある、ことを示す。

xPortGetMinimumEverFreeHeapSizeはheap_4, heap_5で使える

Listing9

size_t xPortGetMinimumEverFreeHeapSize( void ); 
// 戻り値 : The minimum number of unallocated bytes that have existed in the heap since the FreeRTOS application started executing.  

Malloc Failed Hook 関数

pvPortMallocはアプリケーションコードから直接呼ばれることがある。また、カーネルオブジェクトが生成されるときにはFreeRTOSソースコードから呼ばれる。

標準ライブラリのmallocのように、もしpvPortMallocがサイズ不足でRAMブロックを返せない時はNULLを返す。アプリケーションからカーネルオブジェクトを作ろうとして、pvPortMallocからNULLが帰ってきたときには、カーネルオブジェクトは生成されないことになる。

全てのヒープアロケーションスキームはpvPortMallocがNULLを返したときにはhook(もしくはcallback)を呼ぶ設定がある。

configUSE_MALLOC_FAILED_HOOK(FreeRTOSConfig.h)が1の場合、アプリケーションはmallocが失敗したときにhookする関数を用意する必要がある。プロトタイプはListing10に示す。
この関数はアプリケーションに合わせて実装すればよい

Listing10

void vApplicationMallocFailedHook( void ); 
// 戻り値 : The minimum number of unallocated bytes that have existed in the heap since the FreeRTOS application started executing.