もっともシンプルなmalloc,freeの実装と理解

mallocはOSからメモリを動的に確保する？

　mallocをするとOSからメモリを確保出来る。

　mallocで確保したメモリはfreeでOSに返される。

　一体どこの誰だ、こんな嘘の解説を世に出したのはぁ！

　こんな説明がまかり通っているから、初心者の脳内メモリイメージが何だかよく分からない、お花畑な状態になってしまうのだ。

　なんかOSっていうスゲーのが何かしてるらしい。よくわからないけど、なんか駄目って言われてるから2回解放したら駄目らしい。使ったら解放しないと駄目って言うから解放したけど、何か動かない。なんか駄目って言われたから、やっちゃ駄目なことは分かるけど、逆に何をしても良いのか実はわかってない。

　どうも、こんな感じのイメージになっているっぽい。

　同じ嘘をつくなら、mallocはOSからメモリを確保しない、freeはOSにメモリを返さないと説明した方がまだマシである。

　なぜなら、mallocはOSから動的にメモリを確保する場合もあるが、動的にメモリを確保しない場合もある。そして後者の方が、理解に圧倒的に重要な項目だからだ。

　この記事では、OSから一切動的にメモリを確保しない極シンプルなmalloc、freeを作る。なんだかmalloc,freeがよく分からない、と思っている初心者の方々の理解の手助けになれば良いと思う。

　とにかく簡単な物が、どう動くのかを理解することが、一番手っ取り早い理解だ。

　※本格的なmallocを実装する為の記事ではありません。

OSからメモリを動的に確保しないmallocを作ろう

　mallocにまつわる技術は中々に奥深い物があるのだが、そんな物を解説したって混乱するだけである。とにかく、ヒープだのなんだのを全て排除した、簡単で、機能としては十分なmallocとfreeを作ることを目標としよう。

　まず、一番簡単でかつ、仕様を満たすmallocとfreeの実装は以下だ。

int* my_malloc(int size)
{
  return 0;
}

void my_free(int* ptr)
{
}

　今回はわかりやすさを最優先する為に、全てをintの単位で管理する。sizeも何int分かを表す。voidポインタなんてまだキミ達には早すぎる。アライメントとか気にしなくていい。

　ただ、実際のmallocのsizeと今回のmy_mallocのsizeは単位が違うことだけは認識しておいて欲しい。

　さて、これは完全で一切バグのないmalloc、freeだ。決して問題を起こすことはない。そして、このmalloc、freeにOSは一切絡んでいないことは納得して頂けるだろう。（OSどころか、処理すらないのだから！）

　とはいえ、10という入力が来たら、長さ10のメモリのアドレスを返さなければ、流石に実用に耐えない。追加の実装が必要だ。

（　・Д・）「あ、そこでOSからメモリを持ってく…………

　持ってきません。この記事は最後までOS絡みません。

グローバル変数でメモリを管理

　さて、OSからメモリを取ってこないと言っても、どこかにメモリは必要。ということで、以下の様にグローバル変数memoryを用意しよう。

int memory[20];

　10個分のメモリが欲しいと言われたら、このmemoryから10個分返してあげれば、別にOSに頼らなくてもメモリを10個動的に確保したのと同じだ。

　というわけで、memoryを返してあげよう。

int memory[20];
int* my_malloc(int size)
{
  return memory;
}
void my_free(int* ptr)
{
}

　完璧である。さぁ、実際に使ってみよう。

int main(int argc, char *argv[])
{
  int *a = my_malloc(10);
  int *b = my_malloc(10);

  a[0] = 1;    a[1] = 2;
  b[0] = 10;   b[1] = 20;

  printf("a[0]=%d, a[1]=%d\nb[0]=%d, b[1]=%d\n", a[0], a[1], b[0], b[1] );
  my_free(a);  my_free(b);
  return 0;
}

　まぁ、言うまでもなく、これの結果は以下の様になる。

a[0]=10, a[1]=20
b[0]=10, b[1]=20

　問題は1回目のmy_mallocも2回目も、同じポインタを返しているから、同じ場所を書き換えてしまうのだ。

a,bのアドレスと範囲

使用した場所を記録する

　毎回違う場所を返せる様にするには、いったい何処が使われているか記録しておかなければならない。

　これをどのような理論、データ構造で実装するかが、mallocとfreeの最重要な部分である。が、今回はわかりやすさが何よりも優先である。

　グローバル変数usedを用意し、そこに使っているか使っていないかの状態を保存しよう。usedの値が0なら未使用、1なら使用中である。

　size分の領域が必要な場合、0番目から1つ1つ、使われているかいないかを確認し、使われていなければ、使用中(1)をマークして返す。

int memory[20];
int used[20]={0};

int* my_malloc(int size)
{
  if ( size <= 0 || size > 20 ) return 0;
  
  for (int i = 0; i < 20 - (size - 1); i++){
    if ( !used[i] ) {
      //size分の領域が連続して空かを確認してから返す
      int not_used = 1;

      for (int k = 0; k < size; k++)
        if ( used[i + k] ) not_used = 0;

      if ( not_used ) {
        // 空だった場合は
        // used[i] ～ used[i + size - 1] を全て1にして
        // &memory[i] を返す
        for (int k = 0; k < size; k++)  used[i + k] = 1;
        return memory + i;
      }
    }
  }
  return 0;
}

　（continue, break, gotoを使う誘惑に駆られたが、わかりやすさ優先の為に我慢した）

　これで、先ほどのmainを実行してみると………

a[0]=1,  a[1]=2
b[0]=10, b[1]=20

　エクセレンッ！完璧である。

usedのお陰で、aとbが違う場所に割り当てられた

　と、言いたいところだが、まだ問題がある。freeが実装されていない。

　このままだと、以下のコードでcの確保に失敗してしまう。

int main(int argc, char *argv[])
{
  int *a = my_malloc(10),*b = my_malloc(10);

  my_free(a); // aを解放
  int *c = my_malloc(10);// 0(NULL)が返ってしまう

  return 0;
}

　cを確保する前に同じサイズのaをfreeしているので、cは確保出来て当然だろう。

　というわけで、freeを実装したいのだが………

void my_free(int* ptr)
{
  if (!ptr) return;

  int index = ptr - memory; // ポインタの引き算
  for(int i = 0; i <    /* ????? */   ;i++)
    used[index + i] = 0; // 未使用に
}

　ちょっと待って、何メモリ分を解放すれば良いのか分からない。for文の条件式が作れない。

　Note: ポインタの引き算が分からない人へ

　 ptr = &memory[index] とした場合、&memory[index] - memoryを計算すると、indexが取得できる、と言う意味。ポインタも頑張って勉強しよう！

使用量を保存し、freeを実装

　どうやらusedをクリアする為には、ptrがどれだけの大きさのブロックなのかを保存する必要もあるらしい。

　usedに使用サイズを保存しよう。

int memory[20];
int used[20]={0};

int* my_malloc(int size)
{
  if ( size <= 0 || size > 20 ) return 0;
  
  for (int i = 0; i < 20 - (size - 1); i++) {
    if ( !used[i] ) {
      int not_used = 1;

      for (int k = 0; k < size; k++)
        if ( used[i + k] ) not_used = 0;

      if ( not_used ) {
        // usedに終わりまでの距離を保存してから、&memory[i]を返す
        // ※used[i] = size, used[i + 1] = size - 1, used[i + 2] = size - 2, ....を保存する
        for (int k = 0; k < size; k++) used[i + k] = size - k;
        return memory + i;
      }
    }
  }
  return 0;
}

void my_free(int* ptr)
{
  if (!ptr) return;
  
  int index = ptr - memory;
  int size  = used[index];
  for (int i = 0; i < size ; i++)
    used[i + index] = 0;
}

　これでmallocとfreeの実装は完成だ。 　

　さて、実際にサンプルコードを動かしてみよう。

int main(int argc, char *argv[])
{
  int *a = my_malloc(10),*b = my_malloc(10);
  printf("a address=%d, b address = %d\n",a,b);

  my_free(a); // aを解放
  int *c = my_malloc(10);//aの領域と同じところが確保される
  int *d = my_malloc(10);//足りないので0

  printf("c address=%d, d address = %d\n",c,d);

  return 0;
}

　結果は下の様になり、完璧な動作をしている。

a address=4225504, b address = 4225544
c address=4225504, d address = 0

c,bがmemoryに割り当てられている

malloc , freeを理解する

　さて、どうだっただろうか？実に簡単だったと思う。

　無論、今回作ったmalloc,freeは実用には全く耐えない。（usedの為に2倍のメモリを使うのだから目も当てられない。その上、ブログ記事の為に、わざとすぐに問題を起こせる様にしてある。）

　しかし、メモリの確保、解放がなんなのかを理解するに十分である。

　ここまで見てきた様に、メモリを動的に割り当てる、解放する行為にOSは一切関係ない。

　OSからメモリを確保する、返すというのは、次の段階の話だ。キミ達が先ず理解しなくてはならないのは、OSレベルの話ではなく、アプリケーションレイヤーでの話なのだ。

　例えば、メモリ確保直後の値はどうなっているのだろう？初期化されているだろうか？

　否である。mallocやfree関数内でmemory配列に対して一切の操作はしていない。誰かが使った後だと、使いっぱなしで、次に渡される。

　例えば、NULL（0）の解放をするとどうなるだろう？問題が何か起こるだろうか？

my_free(0);
my_free(NULL);

　これは、実は何も問題を起こさない。なぜなら、1行目で即座にreturnしているからだ。 別に私が気を利かしたのではなく、freeがそういう定義だからである。

void my_free(int* ptr)
{
  if (!ptr) return;

　じゃぁ、0が大丈夫なら1は？

my_free(1);

void my_free(int* ptr)//ptr = 1
{
  if (!ptr) return;

  int index = ptr - memory; // ここが負になる
  int size  = used[index]; // 負のインデックスでアクセス
  for(int i = 0; i < size; i++)
    used[ i + index ] = 0;  // used [ 0 + 負 = 負 ]  = 0;という処理になる
}

　実装に依存するが、今回の実装では明らかに問題が起こる。つまり、やってはならないと分かるだろう。

　なら、次はmallocで確保した領域を途中から開放した場合はどうなるだろう。

int *a = my_malloc(10);
my_free(a + 5);
int *b = my_malloc(10);
my_free(a);
int *c = my_malloc(10);

　今回作ったmallocはとても簡単だ。動きをゆっくり追ってみて欲しい。（そのために、役に立たない簡単なmallocを作ったのだから。）

1. aが0番目に割り当てられる
2. my_free(a+5) を解放しようとする。used[5]=5なので、5,6,7,8,9を未使用に変更する
3. 5～14が未使用なのでbが5番目に割り当てられる
4. my_free(a)でused[0]=10なので、0～9を未使用に変更する
5. 0～9が未使用なのでcが0番目に割り当てられる

　最終的には以下の図の様になる。酷い有様だ。

b,cが中途半端に重なる

　途中から解放したり、mallocで取得したアドレスをなくしたら困ると分かるだろう。

　では、二回解放をするとどうなるだろう。今回の実装では、直ちに影響はない。だが、暫くすると影響がある。

int *a = my_malloc(5);
int *b = my_malloc(5);
my_free(b);
int *c = my_malloc(10);

my_free(a);
my_free(a);//　今回は連続して解放しても特に問題は起こさない

my_free(b);// cを解放してしまう
int *d = my_malloc(10);

　最終的にこれは以下の図の様なメモリ配置になる。やっぱり酷い有様だ。この上cを開放しようものならdが……となり、収集がつかない。

bの2回解放の所為で、c,dが重なっている

　小さなメモリを何度も取るとどうなるだろう。

int *a = my_malloc(5);//残り容量 15
int *b = my_malloc(5);//残り容量 10
int *c = my_malloc(5);//残り容量 5
my_free(b);//残り容量 10

int *d = my_malloc(10); // 失敗

　残り容量は10なのに、dの確保に失敗する。これは空き容量の断片化が起こるからだ。

容量は足りていてもdを確保出来ない

　gccとかのmallocは、私が作ったのに比べずっと賢いが、基本的にはmalloc,freeは頻繁に行わず、大きな単位で行った方が良い。

　実行環境にも依存するが、小さいオブジェクトなら、普通にスタックに置けば良い（ローカル変数で定義すれば良い）。SPの移動でメモリの解放がされるので0コストだ。（組み込みだとSRAMが小さくて、すぐパンクする可能性があるので気をつけたし）

まとめ

　さて、malloc,freeの大事なところを理解するのに、OSからメモリを確保とか糞みたいなどうでも良いことだと理解して貰えただろうか。

　mallocをするとOSからメモリを確保出来る………。確かにその通りではある。

　だが、その話を鵜呑みにして、OSからメモリがご降臨されて、OSにメモリがご帰還なさっていく様なふんわりしたイメージをいつまでも持っていると、大事なことが理解出来ない。

　メモリの確保が行われるのは、mallocが管理しているリソースが足りなくなった時だ。常にOSからメモリを確保している訳ではない。

　mallocはOSからメモリを確保しないし、freeはOSにメモリを解放しないと覚えていた方がまだマシだ。

　今日から「mallocとfreeはメモリを確保、解放しない」と念仏の様に唱えてC言語を捨て、RustやC++を完全に理解しよう。

参考文献：glibcのmalloc実装

　実際のmallocがどういう実装になっているのかに興味が湧いたら、以下の記事を読んでみると良いでしょう

Glibc malloc internal

あなたのメモリはどこから来てる？malloc入門 - Qiita

　あと、今回は説明事項から省いたsizeofに関する話など。

sizeof演算子にまつわるアレコレ - Qiita

侍エンジニア塾のC言語のサンプルがヤバすぎる。 - Qiita

Cの本

　楽してとか、わかる、とか、そういうタイトルで良い本だったことはない

苦しんで覚えるC言語

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

プログラミング言語C 第2版 ANSI規格準拠

(古いのであまりお勧めはしないけど）