mallocの動作を追いかける(main_arenaとsbrk編)


# はじめに

[mall0c動画](https://www.youtube.com/watch?v=0-vWT-t0UHg)見てますか？＞挨拶

Twitterで「malloc動画」で検索かけると、眠れない夜に見ると良いとか、健康に良いとかいろいろ出てきて、健康に良い上にmallocのこともわかるなんて、もう見ない理由はないですね。

というわけで、今回はmallocにおけるmain_arenaとsbrkの振る舞いを追います。

* [mallocの動作を追いかける(mmap編)](https://qiita.com/kaityo256/items/9e78b507940b2292bf79)
* [mallocの動作を追いかける(prev_size編)](https://qiita.com/kaityo256/items/2e9a368a5b627daa2ff6) 
* [mallocの動作を追いかける(main_arenaとsbrk編)](https://qiita.com/kaityo256/items/94a84dbe922eb5996a27) ← イマココ
* [mallocの動作を追いかける(fastbins編)](https://qiita.com/kaityo256/items/ca54b1b921d8ab96cb82)
* [mallocの動作を追いかける(マルチスレッド編)](https://qiita.com/kaityo256/items/bf6563361c502bbf062e) 
* [mallocの動作を追いかける(環境変数編)](https://qiita.com/kaityo256/items/fc9a27d0df1371246951)

# main_arenaとsbrkの動作を追いかける

## gdbで追いかける

mallocは、メモリをアリーナ(arena)という単位で管理している。その管理に使われるのがmalloc_state構造体。普通はアリーナは一つだけで、それにmain_arenaという名前がついており、グローバル変数として宣言されている。malloc_state構造体の定義は例えば[こちら](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc_state)を参照。

さて、プログラム実行開始直後はmain_arenaは何も管理していない、まっさらな状態になっている。最初にmallocが呼ばれた時、sbrkを呼ぶことでプログラムのヒープを拡張し、それで得たメモリプールからチャンクを切り取って、ユーザに返す。まずはそのあたりの振る舞いを見てみよう。

こんなコードを書いてみる。

```cpp:test1.cpp
#include <cstdio>
#include <cstdlib>
int
main(void){
  char *buf=(char*)malloc(1);
  free(buf);
}
```

なんの変哲もない、ただmallocで1バイトを要求して、それをfreeするだけのコードであるが、このコードを実行すると、

1. 初めてのmalloc実行なのでsrbkによりヒープ拡張が起きて
2. 得たアドレスの最初をチャンクとして切り出し、
3. ヘッダ部を除いた部分をユーザに返し、
4. freeする時に、チャンクをfastbinsに登録する

という、およそmallocに必要な種々のことが起きるので動作確認には都合が良い。これを`-g`つきでコンパイルして、gdbで動作を追いかけよう。

まずはmainにブレークポイントを置いて、そこまで実行する。

```shell-session
$ g++ -g test1.cpp
$ gdb -q ./a.out
(gdb) break main
Breakpoint 1 at 0x4006b8: file test1.cpp, line 5.
(gdb) r
Starting program: /path/to/a.out 
Breakpoint 1, main () at test1.cpp:5
5	  char *buf=(char*)malloc(1);
(gdb) 
```

この状態で、main_arenaにアクセスできる。ただし、今は中身は空っぽである。中身を表示させてみよう。

```shell-session
(gdb) p/x &main_arena
$1 = 0x2aaaab813e80
(gdb) x/24xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813e90 <main_arena+16>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ea0 <main_arena+32>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813eb0 <main_arena+48>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ec0 <main_arena+64>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ed0 <main_arena+80>:	0x00000000	0x00000000	0x00000000	0x00000000
```

こんな感じで、main_arena構造体のアドレスは0x2aaaab813e80であり、中身は全部ゼロであることがわかる。

さて、このあと最初のmallocが呼ばれるため、sbrkによりヒープ拡張が行われる。[sbrk](http://linuxjm.osdn.jp/html/LDP_man-pages/man2/brk.2.html)とは、program break、つまりプログラムの一番最後(データセグメントの最後尾)を拡張するためのシステムコールである[^1]。brkが位置の変更、sbrkがサイズを増やす要求をするシステムコールで、同名の関数が用意されている。とりあえずsbrkにブレークポイントを置いて続行してみよう。

```shell-session
(gdb) break sbrk
Breakpoint 2 at 0x2aaaab5728e0
(gdb) c
Continuing.

Breakpoint 2, 0x00002aaaab5728e0 in sbrk () from /lib64/libc.so.6
(gdb) 
```

sbrkにひっかかった。バックトレースも表示してみる。

```shell-session
(gdb) bt
#0  0x00002aaaab5728e0 in sbrk () from /lib64/libc.so.6
#1  0x00002aaaab51c179 in __default_morecore () from /lib64/libc.so.6
#2  0x00002aaaab51896f in _int_malloc () from /lib64/libc.so.6
#3  0x00002aaaab51a1f7 in malloc () from /lib64/libc.so.6
#4  0x00000000004006c2 in main () at test1.cpp:5
```

malloc内部から呼ばれていることがわかる。

さて、sbrkは、引数として、ヒープを拡張するサイズを取る。したがって、sbrkにブレークポイントを置いて、ひっかかったら引数の値を表示させれば、mallocがどれくらいヒープ拡張を要求したかがわかる。第一引数は`%rdi`に入っている。

```shell-session
(gdb) p/x $rdi
$2 = 0x21000
```

0x21000(135168)バイト要求しているようだ。

さて、malloc実行直後まで続けよう。

```shell-session
(gdb) n
Single stepping until exit from function malloc,
which has no line number information.
main () at test1.cpp:6
6	  free(buf);
```

mallocした直後まで来た。`buf`にどんなアドレスが入っているか調べる。

```shell-session
(gdb) p/x buf
$3 = 0x602010
```

`buf`には0x602010というアドレスが返された。したがってチャンクの先頭アドレスは0x602000である。

この状態で、再度main_arenaの中身を表示してみよう。

```shell-session
(gdb) x/24xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000001	0x00000000	0x00000000
0x2aaaab813e90 <main_arena+16>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ea0 <main_arena+32>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813eb0 <main_arena+48>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ec0 <main_arena+64>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ed0 <main_arena+80>:	0x00000000	0x00000000	0x00602020	0x00000000
```

いくつかゼロでない値が入ったことがわかる。上記の表示対応する形で、malloc_state構造体の最初の方を図示するとこんな感じ。

<img width="638" alt="main_arena.png" src="https://qiita-image-store.s3.amazonaws.com/0/79744/7c3c38c7-2162-826c-8d37-c75698193403.png">


まず、0x00000001はフラグ(`main_arena->flags`)であり、fastbinsにチャンクがあるかどうかを示す。その後fastbinYの配列が10個続くが、本稿では詳細を説明しない。0x00602020は`main_arena->top`の値であり、次にメモリ要求があった場合に切り出す位置を示す。

さて、さらにプログラムを進め、free直後の状態を見てみる。

```shell-session
(gdb) n
7	}
(gdb) x/24xw &main_arena
0x2aaaab813e80 <main_arena>:	0x00000000	0x00000000	0x00602000	0x00000000
0x2aaaab813e90 <main_arena+16>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ea0 <main_arena+32>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813eb0 <main_arena+48>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ec0 <main_arena+64>:	0x00000000	0x00000000	0x00000000	0x00000000
0x2aaaab813ed0 <main_arena+80>:	0x00000000	0x00000000	0x00602020	0x00000000
```

先程1が入っていた`flags`が0となり、fastbins対象のチャンクが存在することを示している。[^flags]次に、fastbinsの一番小さいメモリのビンに、先程のチャンクアドレス0x00602000が登録された。ヒープのトップは相変わらず0x00602020である。

[^flags]: 古いmallocでは、fastbinsの最大サイズ`maxfast`というメンバ変数を持ち、その値の最下位bitをこのフラグに使っていた模様。下位bitをフラグに使うの好きね・・・

## プログラムから追いかける

先程みたいに全部gdbで追いかけても良いが、今後いちいちアドレス指定して値を読むものタルいので、malloc_state構造体を定義して使おう。あとで使いまわすためにヘッダにしてみよう。

```cpp:malloc.h
struct malloc_state{
  int mutex;
  int flags;
  size_t *fastbinsY[10];
  size_t *top;
};
typedef malloc_state* mstate;
mstate main_arena = (mstate)0x2aaaab813e80;
```

いろいろ手抜きをしているが、とりあえずの目的にはこの程度で十分。最後にmain_arenaを先程gdbで見たアドレス決め打ちでゲットしている。もちろん、アドレス空間が毎回ランダマイズされるようなOSでこの手は使えない。

これを使ってこんなコードを書いてみる。

```cpp:test2.cpp
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "malloc.h"
int
main(void){
  printf("---start program---\n");
  void *p = sbrk(0);
  printf("program break: 0x%lx\n",p);
  printf("---call malloc---\n");
  char *buf=(char*)malloc(1);
  p = sbrk(0);
  printf("program break: 0x%lx\n",p);
  printf("buf address: 0x%lx\n",buf);
  printf("chunk top: 0x%lx\n",buf-0x10);
  size_t csize = (size_t)(*(buf-8));
  csize ^= 1;
  printf("chunk size: 0x%lx\n",csize);
  printf("main_arena->fastbinsY[0]:0x%lx\n",main_arena->fastbinsY[0]);
  printf("main_arena->top:0x%lx\n",main_arena->top);
  printf("---call free---\n");
  free(buf);
  p = sbrk(0);
  printf("program break: 0x%lx\n",p);
  printf("main_arena->fastbinsY[0]:0x%lx\n",main_arena->fastbinsY[0]);
  printf("main_arena->top:0x%lx\n",main_arena->top);
}

```

実行するとこんな感じになる。

```shell-session
$ g++ test2.cpp   
$ ./a.out 
---start program---
program break: 0x602000  // 1.
---call malloc---
program break: 0x623000  // 2.
buf address: 0x602010    // 3.
chunk top: 0x602000      // 4.
chunk size: 0x20         // 5.
main_arena->fastbinsY[0]:0x0  // 6.
main_arena->top:0x602020 // 7.
---call free---
program break: 0x623000  // 8.
main_arena->fastbinsY[0]:0x602000  //9. 
main_arena->top:0x602020 // 10.
```

sbrkは、成功すると前回のプログラムブレーク、つまりヒープの最後尾を返す。したがって、要求サイズ0で実行すると、現在のヒープの最後尾のアドレスを返してくれる。それを使ってヒープの最後尾をモニタできる。

実際のプログラムの動作は以下の通り。

1. プログラム開始直後、ヒープの最後尾は0x602000になっている。
2. mallocを実行すると、ヒープが拡張されて、位置が0x623000になった(先程gdbで確認したとおり、0x21000バイトだけ拡張されている)。
3. ユーザに返されたのは、その0x10バイト後の0x602010である
4. その0x10バイト前がチャンクの先頭であり、拡張されたヒープの先頭アドレス0x602000に一致する。
5. チャンクサイズは0x20(32)バイトである。
6. この時点では`fastbinsY[0]`にチャンクは登録されていない
7. `main_arena->top`は、確保したチャンクの直後、つまり先頭アドレス0x602000にチャンクサイズ0x20を足した0x602020を指している
8. freeした直後も、ヒープ位置は変わらない
9. `fastbinsY[0]`に先程解放したチャンクが登録された
10. `main_arena->top`の指す位置は(確保したメモリがfreeされたにもかかわらず)変わらない。

図解するとこんな感じ。

<img width="825" alt="sbrk.png" src="https://qiita-image-store.s3.amazonaws.com/0/79744/d016b679-fd91-7b71-5dc0-bd5b562f3c5e.png">

(1) 最初はアリーナがなかったのが、
(2) sbrkでヒープが拡張され、
(3) 拡張された領域の先頭からチャンクが切り出された

という感じ。

# まとめ

mallocが初めて呼ばれたときにsbrkでヒープ領域が拡張され、チャンクが切り出される様子を確認した。また、main_arenaの内部の変化も観察してみた。全部「こうなるだろう」と思ったことが確認できただけなのだが、実際にプログラムを実行して確認したり、gdbで中身を見たりすると、なんとなくmallocがより身近に感じたり感じなかったりするかもしれない。

[続く](https://qiita.com/kaityo256/items/ca54b1b921d8ab96cb82)

# 参考

* [malloc動画](https://www.youtube.com/watch?v=0-vWT-t0UHg) 元動画
* [mallocの旅(glibc編)](https://www.slideshare.net/kosaki55tea/glibc-malloc) 上の動画のスライド
* [malloc(3)のメモリ管理構造](http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/) 説明がわかりやすい記事。
* [malloc.c](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html) mallocのソース
* [Man page of BRK](http://linuxjm.osdn.jp/html/LDP_man-pages/man2/brk.2.html)



[^1]: より正確には、Linuxではsbrkは内部でbrkシステムコールを使っている。