malloc関数の簡単な実装例

こんにちは、めのんです！

約1週間かけて下準備をしてきたので、ようやくmalloc関数の簡単な実装例を紹介できるようになりました。
今回の実装例では、オリジナルのmalloc関数やfree関数を破壊してしまわないように、関数名を「my_malloc」、「my_free」とさせていただきます。
あらかじめご了承ください。

とりあえずソースコード

いつもとは違って、今回はいきなり全体のソースコードを掲載することにします。
ちょっと長いですけど、まずは雰囲気をつかんでいただければと思います。

#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);

// my_mallocで割り付けるメモリ領域
union
{
  union max_align_type aligner;  // 最大の境界調整
  char array[0x10000];
} memory;

size_t pos = 0;     // may_mallocが次に返すmemory.arrayの位置
size_t count = 0;   // my_mallocで割り付けた数

// 自家製malloc関数
void *my_malloc(size_t size)
{
  // sizeが0のときはNULLを返す。
  if (size == 0)
    return NULL;

  // sizeを最大境界調整要求の倍数に切り上げる。
  size = (size + max_align_size - 1) / max_align_size * max_align_size;
  if (pos + size >= sizeof(memory.array))
    return NULL;

  void *r = &memory.array[pos];
  pos = pos + size;
  ++count;
  return r;
}

// 自家製free関数
void my_free(void *p)
{
  // NULLを渡したときは何もしない。
  if (p == NULL)
    return;

  // 割付け済みのメモリブロックがすべて解放された時点で再割付け可能にする。
  if (--count == 0)
    pos = 0;
}

int main(void)
{
  void *array[0x10];

  printf("max_align_size = %zu\n", max_align_size);

  // 16回メモリブロックを割り付ける。
  for (int i = 0; i < 0x10; i++)
  {
    printf("i = %d\n", i);
    void *p = my_malloc(0x1000);
    array[i] = p;
    printf("pos = 0x%zx count = %zu\n", pos, count);
  }
  // 16回メモリブロックを解放する。
  for (int i = 0; i < 0x10; i++)
  {
    printf("i = %d\n", i);
    void *p = array[i];
    my_free(p);
    printf("pos = 0x%zx count = %zu\n", pos, count);
  }
  return 0;
}

上のソースコードでは、my_malloc関数とmy_free関数の定義のほか、実際に動かしてみられるように簡単ですがmain関数も用意しました。

malloc関数とfree関数の仕様を確認

関数の実装例を見ていく前に、malloc関数とfree関数の仕様を確認することにしましょう。

malloc関数

まずは規格から引用しますね。

7.20.3.3 malloc関数
形式
　　　　#include <stdlib.h>
　　　　void *malloc(size̲t size);
機能 malloc関数は，大きさがsizeであるオブジェクトの領域を割り付ける。割り付けられたオブジェクトの値は，不定とする。
返却値 malloc関数は，空ポインタ又は割り付けた領域へのポインタを返す。

引用元: JIS X3010:2003より

引用した部分はmalloc関数に関する部分だけなんですけど、実際には少し前に「7.20.3 記憶域管理関数」ということで共通の仕様があります。
そこについては私が説明します。

malloc関数で割り付けたメモリブロックはどんな型のオブジェクトとしても使えるように境界調整する必要があります。
割り付けたメモリブロックは他のどんなオブジェクトとも重ならないようにしなければなりません。

指定したsizeがゼロの場合はゼロ以外を割り付けたときと同じように有効なポインタを返してもいいですし、空ポインタ（NULL）を返してもいいことになっています。
つまり処理系定義ということですね。

割り付けられたメモリブロックはfree関数で解放されるまで有効です。

fee関数

次はfree関数の規格を引用します。

7.20.3.2 free関数
形式
　　　　#include
　　　　void free(void *ptr);
機能 free関数は，ptrが指す領域を解放し，その後の割付けに使用できるようにする。ptrが空ポインタの場合，何もしない。それ以外の場合，実引数がcalloc関数，malloc関数若しくはrealloc関数によって以前に返されたポインタと一致しないとき，又はその領域がfree若しくはreallocの呼出しによって解放されているとき，その動作は未定義とする。返却値 free関数は，値を返さない。

引用元: JIS X3010:2003より

「calloc」や「realloc」という関数名が出てきましたが、これらはmalloc関数と同じようにメモリブロックを割り付けるための関数です。
今回は詳しい解説は割愛しますが、いずれ別の機会に解説できたらと思います。

free関数についてはとくに補足しなくてもいいでしょう。

実装の解説

それでは順に実装を解説していきます。

境界調整のための準備

前回の記事は読んでいただけましたか？
あれだけだと何に使うのかよくわからなかったと思うのですが、ここで出てくるんですよ！

// 処理系の最大境界調整要求を持つ型
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);

max_align_type共用体はいろんな型を並べて、最大の境界調整要求になる型になるようにしたものです。
MinGW-w64の64ビット版GCCではlong double型の境界調整要求が一番大きくて16になります。
Visual C++など32ビット以上の多くの処理系ではlong double型とdouble型は同じサイズなので8になると思います。

max_align_sizeはmax_align_type共用体の境界調整要求を格納しています。
この値で境界調整すればどんなオブジェクトでも扱えるようになります。

メモリブロック割り付けと解放に必要な管理領域

次はmalloc関数とfree関数で共通に使う管理領域を見ていきます。

// my_mallocで割り付けるメモリ領域
union
{
  union max_align_type aligner;  // 最大の境界調整
  char array[0x10000];
} memory;

size_t pos = 0;     // my_mallocが次に返すmemory.arrayの位置
size_t count = 0;   // my_mallocで割り付けた数

オブジェクトmemoryは64kバイト（＝0x10000バイト）の配列を用意するためのものです。
メンバalignerを持たせることでメンバarrayをmax_align_sizeに境界調整することができます。
共用体にはこういう使い方もあるんです。

posは次にmay_malloc関数が呼ばれたときに返すmemory.arrayの位置（添え数）です。
my_malloc関数を呼ぶたびにposは大きくなっていきます。

countはmy_malloc関数が呼ばれるたびにインクリメントされ、my_free関数が呼ばれるたびにデクリメントされます。
my_free関数が呼ばれたときにcountがゼロになれば、全部メモリブロックが解放済みなのでposをゼロに戻してmemory.arrayを再利用できるようにします。

本来ならmalloc関数が返すメモリブロックはどんなオブジェクトとも重複してはいけないのですが、それだとCだけでは実装できなくなってしまいます。
今回は話を簡単にするためにオブジェクトmemoryを使ってメモリブロックを切り出すようにしています。

my_malloc関数

いよいよmy_malloc関数の実装を見ていきます。

// 自家製malloc関数
void *my_malloc(size_t size)
{
  // sizeが0のときはNULLを返す。
  if (size == 0)
    return NULL;

  // sizeを最大境界調整要求の倍数に切り上げる。
  size = (size + max_align_size - 1) / max_align_size * max_align_size;
  if (pos + size >= sizeof(memory.array))
    return NULL;

  void *r = &memory.array[pos];
  pos = pos + size;
  ++count;
  return r;
}

この実装ではsizeにゼロを指定するとNULLを返すようにしています。
NULLを返すかどうかは処理系定義でしたが、今回はNULLを返すことを選択しました。

次にsizeをmax_align_sizeの倍数になるように切り上げています。
そのときだけのことを考えれば、posはmax_align_sizeの倍数になっているのでこんなことをする必要はないのですが、次回の呼び出しに備えています。

そして、memory.arrayの残量が十分にあるかどうかを調べて、もし足りなければNULLを返しています。
残量が足りていれば、memory.array[pos]へのアドレスを返せるようにいったん返却値にするオブジェクトrに格納しています。

最後に管理領域の更新を行っています。
posは次回のmy_malloc関数の呼び出しに備えてsizeを足しています。
countもインクリメントしています。

落ち着いて見ていけば、そんなに難しいコードではないと思います。

my_free関数

最後はmy_free関数の実装を見ていきます。

// 自家製free関数
void my_free(void *p)
{
  // NULLを渡したときは何もしない。
  if (p == NULL)
    return;

  // 割付け済みのメモリブロックがすべて解放された時点で再割付け可能にする。
  if (--count == 0)
    pos = 0;
}

free関数にNULLを渡した場合は何もしない仕様ですので、my_free関数も同じようにしています。
そして、countをデクリメントしてゼロになればposをゼロに戻しています。

これだけです！

気の利いた実装になっているとはとてもいえませんね。
何しろmy_malloc関数で割り付けた全メモリブロックを解放するまで、memory.arrayの残量が増えないのですから。

でも、こんな実装でも（どんなオブジェクトとも重複しない点を除けば）malloc関数とfree関数の仕様は満たしていると思います。

特定用途向けのアロケータであれば、実際にこんな実装しているライブラリもあります。
シンプルなので高速に割り付け、解放ができますし、フラグメンテーションなどの問題も起きないので用途によっては重宝するからです。

もっと汎用的な用途では、この実装ではさすがに物足りないですね。

今回の解説は以上となります。
次回は、もう少し実用的なアロケータを考えていきます。
ただし、一度に欲張ると大変なので、まずは固定サイズのアロケータから扱うことにします。
どぞご期待ください！

malloc関数の簡単な実装例

とりあえずソースコード

malloc関数とfree関数の仕様を確認

malloc関数

fee関数

実装の解説

境界調整のための準備

メモリブロック割り付けと解放に必要な管理領域

my_malloc関数

my_free関数

この記事を書いている人

めのん

コメントを残すコメントをキャンセル

とりあえずソースコード

malloc関数とfree関数の仕様を確認

malloc関数

fee関数

実装の解説

境界調整のための準備

メモリブロック割り付けと解放に必要な管理領域

my_malloc関数

my_free関数

この記事を書いている人

めのん

関連記事

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル