mallocの動作を追いかける(mmap編)


# はじめに

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

こんな記事に興味持つような人はみんなmalloc動画見てる人たちばかりだと思いますが、僕はmalloc動画見るまでは「え？メモリの管理ってOS側じゃなくてユーザランドでやってたの？」って感じでした。ここでは僕みたいなmalloc初心者のために、mallocの動作を実際に追いかけて見ようと思います。

* [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)

# mallocについて

mallocについては、それこそmalloc動画とか、[このへん](http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/)を見ていただければと思うけれど、要するに

* ユーザプログラムはsbrkによるヒープの拡張かmmapでOSにメモリを要求する
* OSはメモリを確保してユーザに返すけれど、その使い方はユーザプログラムに一任している
* 細かいメモリアクセスが多発するとメモリ効率が悪くなったりするので、mallocの中でうまいことやる

みたいな感じになっている。この「mallocの中でうまいことやる」っていうのが曲者で、ソースみても初見では何やってるかさっぱりわからないと思う。特に小さいサイズのメモリ確保のためにビンで切ってリンクリストで管理して・・・というところはかなりややこしい。

しかし、ある程度以上のサイズのメモリ要求に関しては、mallocはmmapでメモリを確保するが、mmapで確保されたメモリの管理はかなりシンプルなので、まずはそのあたりの動作確認をする。

# chunkについて

mallocはメモリをチャンク(chunk)という単位で扱う。これは「ヘッダ＋ユーザが使える領域」という形になっている。これは[malloc_chunk](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc_chunk)という構造体で、以下のように定義されている。

```cpp
struct malloc_chunk {

	INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
	INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

	struct malloc_chunk* fd;         /* double links -- used only if free. */
	struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size.  */
	struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
	struct malloc_chunk* bk_nextsize;
};
```

ここでいくつかメンバが定義されているが、mmapされたメモリでは`mchunk_prev_size`と`mchunk_size`しか使わず、その直後がユーザが使うメモリとなる。

# mmapによるメモリ確保

mallocは、ある程度以上の大きさのメモリを確保する際は、内部でmmapを呼ぶ。その際、要求されたメモリに、ヘッダとして必要な16バイトと、8バイトアラインメントのための余分な分を付け足し、さらにシステムのページサイズで丸めた分を確保する。mallocで管理するメモリは8バイトアラインされていることが前提になっているため、chunkは、mmapで確保したメモリの、8バイトアラインされたところを先頭にする。そこから8バイトをオフセット(malloc_chunkの`mchunk_prev_size`)とし、次の8バイト(malloc_chunkの`mchunk_size `)にチャンクサイズが入る。

図解するとこんな感じ。

![mmap.png](https://qiita-image-store.s3.amazonaws.com/0/79744/3d364f31-b75f-b29b-a0f1-2bc927a18aca.png "mmap.png")

ただし、malloc動画にもあるように、チャンクサイズの下位3ビットは別の意味に使われているので注意。チャンクサイズの下位3ビットをマスクしたものが本当のチャンクサイズになる。

# 実際に追いかける

## プログラムから確認

まずはこんなソースを書いてみる。

```cpp:test.cpp
#include <cstdio>
#include <cstdlib>
#include <unistd.h>

void
func(size_t request_size){
  char *buf;
  buf = (char*)malloc(request_size);
  printf("request size: 0x%lx\n",request_size);
  printf("obtained pointer: 0x%lx\n",buf);
  size_t offset = *(size_t*)(buf-16);
  size_t size = *(size_t*)(buf-8);
  printf("size = 0x%x\n",size);
  if(size & 2){
    printf("Memory is mmapped.\n");
    size ^= 2;
    printf("offset = 0x%x\n",offset);
    printf("chunk size = 0x%x\n",size);
  }
  free(buf);
}


int
main(void){
  printf("page size = 0x%x\n",getpagesize());
  func(1<<17);
}
```

普通にコンパイルして実行すると、こんな結果になると思う(このサイズでmmapになるか環境によるかも)。

```shell-session
$ g++ test.cpp
$ ./a.out
page size = 0x1000
request size: 0x20000
obtained pointer: 0x2aaaaafd7010
size = 0x21002
Memory is mmapped.
offset = 0x0
chunk size = 0x21000
```

10進よりも16進の方がわかりやすいと思ったので、16進で表示している。
これは要するに、

* システムのページサイズは0x1000(4096)バイト
* ユーザがmallocに0x20000(131072)バイトを要求
* mallocは0x2aaaaafd7010という場所を返してきた。

わけなのだが、先程の図解の通り、mallocが返してきた場所の8バイト前がチャンクサイズ、さらに8バイト前がオフセットになっているので、それを表示する。

```cpp
  size_t size = *(size_t*)(buf-8);
```

によって、mallocが返してきた場所の8バイト前を64bit整数として受け取っている。このまま表示すると

```shell-session
size = 0x21002
```

となっているが、先述の通り、サイズの下位3bitは別の意味を持っている。今回は下位2bit目が立っているので「メモリがmmapで確保された」ことが分かる(残りのbitは「前のチャンクが使用中か」と「Main Arenaであるかどうか」)。

従ってチャンクサイズは

```shell-session
chunk size = 0x21000
```

となる。さらに、mallocが返してきたポインタ(`buf`)の16バイト前がオフセットだが、今回はゼロなので、チャンクの先頭とmmapで確保したメモリの先頭は等しい。

チャンクサイズとしては、最低でもユーザ要求の0x20000バイトと、チャンクヘッダの0x10バイトが必要だが、ページサイズが0x1000バイトであることからそれで丸められて0x21000バイトとなっている。

## gdbで動作を追いかける

先程の実行結果から、たしかにメモリがmmapで確保されたっぽいこと、mallocが返したポインタの8バイト前、16バイト前にチャンクヘッダの情報があることがわかったが、本当にmmapが呼ばれているか不安な人(＝俺)のためにgdbで実行を追いかける。

メモリ確保のところはややこしいので、メモリ解放のところを追いかけてみよう。

先のプログラムを`g++ -g test.cpp`でコンパイルして、gdbで読み込もう。僕の趣味でTUIモードで開く。

```shell-session
$ g++ -g test.cpp
$ gdb --tui -q ./a.out
```

こんな感じの画面になる。
![gdb1.png](https://qiita-image-store.s3.amazonaws.com/0/79744/95532799-8bca-a095-52f7-a53559473aa6.png "gdb1.png")

ここで、20行目(free直前)にブレークポイントを置いて実行。

```gdb
(gdb) break 20
Breakpoint 1 at	0x4007da: file test.cpp, line 20.
(gdb) r
Breakpoint 1, func (request_size=131072) at test.cpp:20
```

ブレークポイントにひっかかった状態で、bufの指す場所を確認する。

```gdb
(gdb) print/x buf
$1 = 0x2aaaaafd7010
```

この8バイト前がチャンクサイズのはずなので、それを表示する。

```gdb
(gdb) x/xw 0x2aaaaafd7008
0x2aaaaafd7008: 0x00021002
```

ちゃんと「0x21002」という値になっていた。

さらに8バイト前(buf-16)がオフセットなので、それを表示する。

```gdb
(gdb) x/xw 0x2aaaaafd7000
0x2aaaaafd7000: 0x00000000
```

オフセットはゼロになっている。

さて、この状態から、`munmap_chunk`にブレークポイントを置いて続行。

```gdb
(gdb) break munmap_chunk  
Breakpoint 2 at 0x2aaaab516480
(gdb) n

Breakpoint 2, 0x00002aaaab516480 in munmap_chunk () from /lib64/libc.so.6
```

これは、`free`の中でチャンクサイズの下位2bit目を見て、mmapされたことがわかったので、内部でmunmapを呼ぶ関数`munmap_chunk`が呼ばれたことを示す。[munmap_chunkのソース](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#munmap_chunk)はこんな感じ。

```cpp
static void
munmap_chunk (mchunkptr p)
{
  INTERNAL_SIZE_T size = chunksize (p);
 
  assert (chunk_is_mmapped (p));
 
  /* Do nothing if the chunk is a faked mmapped chunk in the dumped
     main arena.  We never free this memory.  */
  if (DUMPED_MAIN_ARENA_CHUNK (p))
    return;
 
  uintptr_t block = (uintptr_t) p - prev_size (p);
  size_t total_size = prev_size (p) + size;
  /* Unfortunately we have to do the compilers job by hand here.  Normally
     we would test BLOCK and TOTAL-SIZE separately for compliance with the
     page size.  But gcc does not recognize the optimization possibility
     (in the moment at least) so we combine the two values into one before
     the bit test.  */
  if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
    malloc_printerr ("munmap_chunk(): invalid pointer");
 
  atomic_decrement (&mp_.n_mmaps);
  atomic_add (&mp_.mmapped_mem, -total_size);
 
  /* If munmap failed the process virtual memory address space is in a
     bad shape.  Just leave the block hanging around, the process will
     terminate shortly anyway since not much can be done.  */
  __munmap ((char *) block, total_size);
}
```

オフセットとサイズの調整をしてmunmapしているだけ。

先程の状態で、アセンブリを表示する。

```gdb
(gdb) layout asm
```
![gdb2.png](https://qiita-image-store.s3.amazonaws.com/0/79744/c9fa3831-a574-e552-b165-99041d51096f.png "gdb2.png")

関数`munmap_chunk`に入ったことがわかる。少しスクロールすると、アドレス0x2aaaab5164c6で`munmap`を呼んでいることがわかる。そこにブレークポイントを置く。

```gdb
(gdb) break *0x2aaaab5164c6
Breakpoint 3 at 0x2aaaab5164c6
```
![gdb3.png](https://qiita-image-store.s3.amazonaws.com/0/79744/5ce33496-fdc9-d767-d90e-18b0d0ec56f6.png "gdb3.png")

続行すると、`munmap`を呼ぶ直前で止まる。

```gdb
(gdb) n
Single stepping until exit from function munmap_chunk,
which has no line number information.

Breakpoint 3, 0x00002aaaab5164c6 in munmap_chunk () from /lib64/libc.so.6
```

この状態で、`%rdi`に解放するアドレスが、`%rsi`に解放するサイズが入ってるはずなので表示してみる。

```gdb
(gdb) print/x $rdi
$1 = 0x2aaaaafd7000
(gdb) print/x $rsi
$2 = 0x21000
```

ユーザがもらった(mallocが返した)アドレスは0x2aaaaafd7010であった。そこからチャンクヘッダの16バイト分引いた0x2aaaaafd7000がチャンクヘッダであり、オフセットが0なのでこれはmmapが確保したアドレスの先頭と一致する。また、オフセットがゼロだからチャンクサイズとmmapの確保領域は一致するので、munmapに渡す第二引数はチャンクサイズ0x21000を渡せば良いが、たしかにレジスタ`%rsi`の値はそうなっている。

# まとめ

mallocがmmapを使う場合にその動作を追いかけてみた。リンクリストとかfastbinsとか使い始めるとややこしいが、mmapが使われる時にはその動作は単純でわかりやすい。個人的にマルチスレッド環境でmallocがどう動くか調べたいのだが、続くかどうかは微妙・・・

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

# 参考

* [malloc動画](https://www.youtube.com/watch?v=0-vWT-t0UHg) 伝説の動画
* [malloc(3)のメモリ管理構造](http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/) 説明がわかりやすい記事。
* [malloc.c](https://code.woboq.org/userspace/glibc/malloc/malloc.c.html) mallocのソース