進撃のmalloc

2014年に開催された「第十回 カーネル／VM探検隊＆懇親会 がちゃぴん先生来日記念 進撃のmalloc」というカンファレンスの講演内容です。
いや、このカンファレンス題名ふざけすぎだろ

Transcript

1. がちゃぴん先生来日記念 進撃のmalloc
2. 201x年、ガチャピンは 悩んでいた
3. 進撃のmallocってなに？
4. プロローグ • 突然の発表要請 • 話す内容なんてない • お題が意味不明（日本語でOK） • この３重苦をはたして俺氏は乗り越えること が出来るか
5. 今日話すこと • あまり知られていないが、昔mallocの実装解説 動画を作ったことがある • 動画・スライドのURLは秘密（黒歴史なので） • そのへんの経験から、最近ちょっとだけ glibc の malloc 近辺の開発に関わった • 最近のハックやらの経験に malloc を disったり、 最近の動向をご紹介したりします • カーネルやVMの話はしません • 途中でコードが乱舞したりしません。初心者向け
6. Who am I • Linux メモリ管理コア開発者 • MM Summit(上位20人のコア開発者会議）５ 年連続招待 • Kernelよくわかりません • Ruby core committer • コミット率TOP10コミッタのうちの一人 • Rubyよくわかりません • ボストン在住、Red Hat でお仕事
7. LSF/MM 2014 photo
8. はじまりの朝 • ある日のLKMLでのこと、いつものようにパッ チをdisったりパッチ作者をdisったり、反撃して フレームウォーになったりと平和な日々をくら しておったのじゃ • 誰かがebizzy 30%高速化パッチを出してきた • 30%が大きいのかどうか分からない • Ebizzyってなんやねん • ちょっと自分で測定してみる
9. What is ebizzy? • Webアプリケーション模擬ベンチマーク • http://sourceforge.net/projects/ebizzy/ • N個のスレッドがs秒の間に何回malloc, memcpy, freeが出来るかを測定 • 意図：PHPとかみたいにHTMLテンプレート＋ プログラミング言語みたいなのは、式を評価 しながらテンプレートを最終HTMLにコピーし ていき、クライアントに送ったらそのHTMLは 破棄する
10. Perf 測定 83.67% ebizzy ebizzy [.] memcpy 7.52% ebizzy [kernel.kallsyms] [k] _raw_spin_unlock_irqrestore 1.00% ebizzy ebizzy [.] write_pattern 0.89% ebizzy [kernel.kallsyms] [k] finish_task_switch 0.83% ebizzy [kernel.kallsyms] [k] rwsem_down_write_failed 0.47% ebizzy [kernel.kallsyms] [k] vma_adjust 0.40% ebizzy [kernel.kallsyms] [k] find_vma 0.39% ebizzy ebizzy [.] _int_malloc 0.35% ebizzy ebizzy [.] _int_free 0.28% ebizzy ebizzy [.] search_mem
12. 考察 • カーネルでは時間をあまり食ってない • ワタシglibcチョトダケワカル • こ、この症状は10年前に、malloc動画を書い た時に見たことあるぞー
13. 10年近く秘匿した malloc バグ知識を 爆発させるチャンス ここかなー
14. お試しパッチあててビルド diff --git a/malloc/arena.c b/malloc/arena.c index 9d49f93..a859c59 100644 --- a/malloc/arena.c +++ b/malloc/arena.c @@ -611,8 +611,8 @@ shrink_heap(heap_info *h, long diff) return -2; h->mprotect_size = new_size; } - else - __madvise ((char *)h + new_size, diff, MADV_DONTNEED); /*fprintf(stderr, "shrink %p %08lx¥n", h, new_size);*/ h->size = new_size;
15. 結果 # of # of # of thread iter iter (patched glibc) ---------------------------------- 1 438 10740 2 842 20916 4 987 32534 8 717 15155 12 714 14109 16 708 13457 20 720 13742 24 727 13642 28 715 13328 32 709 13096 36 705 13661 40 708 13634 44 707 13367 48 714 13377 20倍高速化 やはりザビ家はゆるせんと 分かった（20歳無職談）
16. Glibc mallocのスレッド対応 • Glibc はなるべく１スレッド：１Arena（ヒープの中の サブヒープのようなもん）に収束するように動く • 諸般の事情(歴史的事情、大人の事情、カーネ ルの事情)で main arenaとそれ以外とで動きが違 う • いつKernelにメモリを返却するかのポリシーもそ の１つ • メインは128K（malloptで変更可）、非メインは 4k(pagesize)かつ(mallopt無効）
17. 考察 • memcpyしてるベンチでプロファイラにmemcpyって 書いてあるかといってアプリが時間を食ってると思う のは間違い。 • Glibc はスレッドが4k以上freeするとほぼ毎回 madvise(DONTNEED) でメモリ返却するので超遅い • Glibcは madvise(DONTNEED) が超高速と仮定してる けど、間違い。俺ぐらいのておくれになるとはっきり とわかんだね
18. 考察２： madvise(MADV_DONTNEED) • POSIX的にはメモリを回収されやすくするようにプ ライオリティを調整するアドバイス • Linuxではなぜかその場で解放してしまう • それだけじゃなく、mappingのinvalidate保証する ためにその場でTLB shootdownで全CPUにIPI飛 ばし、かつ全CPUから返事来るまで止まるのでク ソ^2 • 一回メモリ解放しちゃうと次回ページフォルトで 同期的にpage zeroing 始めるのでクソ^3 • なお zero page daemon は今年も否決された模 様
19. 考察３： DONTNEED sucks • カーネルはDONTNEEDされた領域は99.9% 二度 と使われないと思ってる • free(3) されたメモリは99.9%再利用される。 semantic gap • MADV_DONTNEEDがPOSIXと異なるのは色々と 問題。posix_madvise(MADV_DONTNEED)はNOP になるよう関数先頭で弾いてる • Glibc mallocのDONTNEEDの使い方がPOSIX semanticsを期待してる気がしたので問い合わせ たところ、いや以前はmunmapしてたのでこれで も改善されたんだ、と言われる
20. 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 55,000 60,000 65,000 70,000 75,000 80,000 85,000 90,000 95,000 1 2 4 8 12 16 20 24 Never return memory to kern DONTNEED (Vanilla) num threads iterations (higher is better) CPUs = 12 num threads iterations (higher is better) CPUs = 12
21. 結論 • Glibc はクソ • Kernel もクソ • jemalloc いいよ、jemalloc
22. おわり うそ、まだもうちょっとだけ続くんじゃよ
23. その後の展開
24. madvise(MADV_FREE) • *BSDにはmadvise(MADV_FREE)というアドバイスがある • Kernelにいつ解放してもいいよとアドバイスしてあげる • ほぼfree(3)から使うの専用 • メモリは解放されるかもしれない。されないかもしれない • 実装的にはDONTNEED+dirty bitのクリア（dirty bitが消 えることによって、結果的にswap outしなくなる） • Free済みメモリをスワップアウトするの最高に馬鹿らしい • Linuxでも作ろう。LSFMM14でだいたい合意とれた。glibc コミュからもカーネルがmalloc用feature作ってくれたら使 うよーと言質取った
25. 0 5,000 10,000 15,000 20,000 25,000 30,000 35,000 40,000 45,000 50,000 55,000 60,000 65,000 70,000 75,000 80,000 85,000 90,000 95,000 1 2 4 8 12 16 20 24 Never return memory to kern MADV_FREE DONTNEED (Vanilla) num threads iterations (higher is better) CPUs = 12 num threads iterations (higher is better) CPUs = 12
26. Subject: The direction of malloc? * Make it easier for us to maintain the malloc implementation. - Removing dead code. - Simplifying macros. - Removing features we don't use. * Add new and required features. - Add support for "have but don't need" kernel pages via vrange. * Fix bugs. (snip) I even encourage the discussion of providing alternate allocators like jemalloc. • 去年１２月に突然流れたmallocの今後の開発方針
27. malloc_set_state • この議論で malloc_set_state を実装してる mallocなんてないから置き換え不可能なんじゃ ね？と嫌疑が提出される • 何する関数だっけ？ • Emacs専用API • malloc_get_stateでmalloc内部状態を保存。 malloc_get_stateで復元 • Emacsコミュ「え？なにそれ？そんなのいらねー よ」 • 消そう → ABI非互換なめるな！ • 結論： ヘッダから削除。Compat symbol行き
28. signal-safe malloc replacement • __signal_safe_memalign, __signal_safe_free, __signal_safe_realloc, __signal_safe_calloc などの名前でメモリ確保関数をもう１セット実装 • Dynamic linkerのTLS確保関数はこっちを使う • シグナルハンドラからTLSアクセスしても平気 • 今後は async-signal-safe 関数からのmallocは 徐々にこちらで置き換えられていくと予想
29. オレはようやくのぼりはじめたば かりだからな このはてしなく遠い malloc坂をよ…
30. 俺氏先生の次回作に ご期待ください