こんにちは、めのんです！
昨日の「malloc関数の簡単な実装例」はいかがだったでしょうか？
機能を簡略化しすぎていてこんなの使えないなど、いろんなご感想が出てくることは想定しています。
そういうこともあって、今回は予告通り固定長のアロケータを作っていくことにします。
固定長のアロケータと書きましたが、私はμITRONを使ってきたこともあって「固定長メモリプール」という名前の方がしっくりきます。
そこで、以後は固定長メモリプールという表現にしますね。
とりあえずソースコード
前回と同じで今回もいきなりソースコードを掲載するところから始めます。
あとでゆっくり解説しますので、まずはどんな感じなのかだけでもざっと見ていただければ幸いです。
#include <stdio.h>
#include <stddef.h>
// 処理系の最大境界調整要求を持つ型
union max_align_type
{
long long a;
double b;
long double c;
void* d;
};
// 処理系の最大調整要求
const size_t max_align_size = offsetof(struct { char a; union max_align_type b; }, b);
union node
{
union max_align_type aligner;
char array[256]; // 固定長配列（ここでは256バイト）
union node* next;
};
// 固定長メモリプールの管理領域
union node memory[256];
union node *top;
// 固定長メモリプールの初期設定
void fmp_setup(void)
{
const size_t n = sizeof(memory)/sizeof(memory[0]);
for (size_t i = 0; i < n - 1; i++)
memory[i].next = &memory[i + 1];
memory[n - 1].next = NULL;
top = &memory[0];
}
// 固定長メモリプールからメモリブロックを割り付ける。
void *fmp_alloc(void)
{
if (top == NULL)
return NULL;
void *r = top->array;
top = top->next;
return r;
}
// 固定長メモリプールから割り付けたメモリブロックを解放する。
void fmp_free(void* p)
{
if (p == NULL)
return;
((union node*)p)->next = top;
top = p;
}
int main(void)
{
void *array[0x10];
fmp_setup();
// 16回メモリブロックを割り付ける。
for (int i = 0; i < 0x10; i++)
{
printf("i = %d\n", i);
void *p = fmp_alloc();
array[i] = p;
printf("p = %p top = %p\n", p,top);
}
// 16回メモリブロックを解放する。
for (int i = 0; i < 0x10; i++)
{
printf("i = %d\n", i);
void *p = array[i];
fmp_free(p);
printf("p = %p top = %p\n", p,top);
}
return 0;
}
まったくの偶然なんですけど、前回のソースコードとまったく同じ行数になりました。
main関数の使用例はあまり適切ではないんですけど、前回の実装とは違って、割付けと解放をこまめに繰り返してもうまく動作するように工夫しています。
最初にfmp_setup関数を呼ばないといけないことだけ注意が必要です。
各関数の仕様
今回実装した関数は私のオリジナルですので、どこかから引用するといったことはできません。
ちゃんと自分で仕様を書いていくことにします（すごく簡単ですけどね）。
内部のデータ構造や動作については、何度も同じことを書くことになるので実装を解説する際にまとめて書くことにします。
fmp_setup関数
固定長メモリプールを使うにはあらかじめこの関数を呼び出す必要があります。
引数も返却値もありません。
fmp_alloc関数
固定長メモリプールからメモリブロックを割り付けます。
固定長ですので引数はありません。
割り付けられるメモリブロックのサイズは256バイトです。
割付けに失敗した場合はNULLを返します。
割り付けたまま解放していないメモリブロックがある場合でも、fmp_setup関数を呼び出せば再初期化されます。
その場合、以前割り付けたままになっているメモリブロックを読み書きした場合の動作は未定義です。
fmp_free関数
fmp_alloc関数で割り付けたメモリブロックを解放します。
引数にNULLを指定した場合は何もしません。
解放したメモリブロックは直ちに再利用可能になります
返却値はありません。
fmp_alloc関数で割り付けたメモリブロック以外を渡した場合の動作は未定義です。
また、すでに解放済みのメモリブロックや、以前割り付けていたメモリブロックをfmp_setup関数によって再初期化されたあとで渡した場合も未定義の動作になります。
実装の解説
それでは順に実装を解説していきます。
max_align_type共用体やmax_align_sizeは前回と同じですので解説は省略します。
必要な方は前回の記事をご覧ください。
メモリブロック割り付けと解放に必要な管理領域
まずはfmp_alloc関数とfmp_free関数で共通に使う管理領域を見ていきます。
union node
{
union max_align_type aligner;
char array[256]; // 固定長配列（ここでは256バイト）
union node* next;
};
// 固定長メモリプールの管理領域
union node memory[256];
union node *top;共用体を使ってたりしてちょっと複雑ですが、線形リストです。
union nodeのメンバは3つあります。
1つめはalignerでこれは境界調整のためのもので、前回と同じです。
2つめのarrayがメモリブロックそのものになります。
3つめのnextは線形リストのノードになるための自己参照ポインタです。
このunion node型256要素の配列memoryがメモリプールの実態だといえます。
もっと割り付けられる数を増やしたければ、逆に減らしたければ、memoryの要素数を変更すればOKです。
topは線形リストの先頭ノードへのポインタです。
このtopがNULLであれば、すべてのメモリブロックが使用中なのでそれ以上割り付けられないことを意味しています。
fmp_setup関数の実装
次はfmp_setup関数の実装を見ていきます。
// 固定長メモリプールの初期設定
void fmp_setup(void)
{
const size_t n = sizeof(memory)/sizeof(memory[0]);
for (size_t i = 0; i < n - 1; i++)
memory[i].next = &memory[i + 1];
memory[n - 1].next = NULL;
top = &memory[0];
}この関数では配列memoryの0番目からn – 2番目の要素のメンバnextに次の要素へのポインタを格納しています。
末尾の要素（＝memory[n – 1]）は、ループを抜けたあとではメンバnextにNULLを格納しています。
これは線形リストの番兵でしたね。
線形リストの理解が怪しい方は過去の記事をご覧ください。
最後にtopにmemory配列の先頭要素のアドレスを格納しています。
これで配列memoryの全要素がつながり、線形リストが完成しました。
今回の固定長メモリプールは、割付け時にはこの線形リストの先頭ノードを取り出し、解放時には線形リストの先頭につなぐ方法で実現しています。
fmp_alloc関数の実装
今度はfmp_alloc関数を見ていきます。
// 固定長メモリプールからメモリブロックを割り付ける。
void *fmp_alloc(void)
{
if (top == NULL)
return NULL;
void *r = top->array;
top = top->next;
return r;
}fmp_setup関数で構築した線形リストが理解できていれば、何をやっているかはすぐに理解できると思います。
まず、topがNULLであれば、もう割り付けられるメモリブロックが残っていないので失敗します。
失敗した場合はNULLを返す仕様です。
topがNULでなければ、topが指すノードのメンバarrayを取り出して返却値にしています。
そして、メンバnextを次のtopにすることで、もとのtopが指すノードを線形リストから切り離しています。
union nodeは共用体ですので、メンバarrayとメンバnextは同じアドレスに配置されていますが、これらを同時に使うことはないので問題ありません。
メンバarrayは割り付けられてから解放されるまでしか使いませんし、メンバnextは割り付けられていないときしか使わないからです。
fmp_free関数の実装
最後にfmp_free関数を見ていきます。
// 固定長メモリプールから割り付けたメモリブロックを解放する。
void fmp_free(void* p)
{
if (p == NULL)
return;
((union node*)p)->next = top;
top = p;
}最初に引数pがNULLかどうかを判断して、NULLであれば何もせずに関数から抜けています。
そういう仕様だからですね。
次に、引数pをunion node*に明示的に型変換した上で、メンバnextにtopを格納しています。
最後に引数pをtopにすることで、pと以前の線形リストが一列につながりました。
次にfmp_alloc関数を読んだ際は、この引数pが新たなメモリブロックとして割り付けられることになります。
今回は、固定長という制約はありますが、自由に割付け、解放を繰り返すことができるメモリプールを作ってみました。
マイコンのプログラムなんかでは、こういう固定長メモリプールが多用されることが結構あります。
また、サイズ違いの固定長メモリプールをいくつか組み合わせて、実質的な可変長メモリプールを作ることもあります。
万能なライブラリ関数というのはなかなか作れませんし、機能的には実現できたとしてもサイズ効率や速度効率の面で要件を満たさないということは多多あります。
そんなときのために、こういうシンプルなライブラリを自分自身で作れるようにしておくのがいいと思います。
今回の解説は以上となります。
明日は平日になりますので、少し簡単なテーマを扱いたいと思います。
まだ何にするか考えていませんけど、明日までにネタ出しをしようと思います。
それでは！
