B演習(言語処理系演習)第9回 メモリ管理・ごみ集め 田浦

我々の処理系はmalloc/newを使っている 字句解析器 構文解析結果(構文木) 関数を呼び出すたびに作られる「環境」 式を評価した結果 例: 2.3 + 3.4, [ 1, 2, 3 ], { a : b }, …

復習: C/C++言語で代表的な3種類のメモリ割り当て方法 局所変数・配列  関数呼び出し終了と共に使えなくなる int* f() { int a[1000]; …; return a; } double* g() { double f; …; return &f; } 大域変数・配列  プログラム実行中常に使える．しかし，実行中に「追加割り当て」できない ヒープ : OSから実行時に取得．代表API : malloc (C), new (C++), … 注 : 中でmallocを呼ぶ関数(e.g., strdup)もある おそらく間違い

基本フォーム 関数呼び出し後も使いたいメモリ 局所変数・配列の領域は使うな 何バイト確保すべきか，同時にいくつ確保すべきかわからない 大域変数・配列の領域は使うな そのような時はmalloc/newを使う しかしmalloc/newされた領域をいつfree/deleteすべきかはプログラマの責任…

割り当てたメモリは「いらなくなったら」解放しなくてはならない いつ「いらなくなる」のか あまり気にする必要ないもの 字句解析器 構文解析結果(構文木) 大いに問題となるもの 「環境」 式を評価した結果

実験: mallocしっぱなしだと何が起こるか

GC (Garbage Collection) あるメモリ領域が「いらなくなった」かどうか，自動的に見つけていらなければ解放(再利用)する仕組み Java, Python, Perl, VBA, … (最近の)言語には必ずといっていいほど備わっている C/C++にはそれがないのだが…

天の助け GC ライブラリ http://www.hpl.hp.com/personal/Hans_Boehm/gc/ (Ubuntu) apt-get install libgc-dev C/C++プログラムのmallocをGC_MALLOCに置き換え, freeを除去するだけで再コンパイル&リンクをするだけで，自動的にいらないメモリを解放してくれるライブラリ 演習HP「各種情報」参照

GCの原理

GC以前のメモリ管理の基本原理 メモリ管理モジュールが「現在使われている/いない領域」を把握するデータ構造を構築 割り当て(e.g., malloc(100)) 使われていない領域から，要求サイズを満たす領域を探索 解放(e.g., free(p)) 解放された領域を「使われていない領域」として記録(以降のmallocで利用)

メモリ管理データ構造の例 空き領域リスト(フリーリスト) 使用中アドレス サイズの表(例: ハッシュ表) free 空き領域 使用中領域

例(続) 空き領域リストのデータ表現 typedef struct free_region * free_region_t; typedef struct free_region{ free_region_t next; int sz; } free_region; malloc(sz) { 空き領域リストをたどって要求szを満たす regionを検索; }

GCなしのメモリ管理の危険 メモリ管理ライブラリは盲目的にユーザプログラム(malloc/freeの呼び出し)を信ずる 早すぎるfree 本来別のアドレスに割り当てられるべき複数の領域が同じアドレスに割り当てられる意図しないデータの破壊 メモリリーク freeすべきものをfreeしない 本来他の目的に使われるべきアドレスが再利用されない意図しない使用メモリ領域の増大

自動メモリ管理(ごみ集め; Garbage Collection) 「もう使われない領域」を自動的に発見して解放 プログラムの安全性は格段に向上する GC用語 (プログラム実行中のある時点で) 「生きている領域」 = その時点以降使われる(アクセスされる)領域 反対語: 「死んでいる領域」

もう使われない領域をどう発見するのか? (実現不可能な)理想  プログラムを実行し続けた際に，今後使われる領域とそうでない領域を各時点で100%正しく判定する(一種の未来予知? アルゴリズム自動理解?) main() { …; for (i = 0; i < n; i++) { p = a[i * i]; … *p … } } この地点以降使われるメモリ領域はa[0], a[1], a[4], a[9], a[16], …

実際のGCが行っている「近似」 現在局所・大域変数に入っているアドレス(が指すメモリ領域)は「生きている」 注: アドレスが指す「メモリ領域」  そのアドレスを含む，一回のメモリ割り当てで割り当てられた領域 ある「使われる」メモリ領域中に入っているアドレス(が指すメモリ領域)は「生きている」 配列の要素，構造体のフィールドなど 「今後使われる」  「生きている」

同じことの書き換え LIVE : (ある注目している時点で)「生きている」アドレスの集合 ある局所・大域変数の値 = a  a  LIVE “a  LIVE” かつ “pが，aが指すメモリ領域内に格納されている”  p  LIVE a p

要するに局所・大域変数から「到達可能」なものが「生きている」 局所変数 大域変数

GCの基本原理 割り当て (e.g., malloc(sz);) このとき，空き領域が足りなくなったら(基準は様々)， 空き領域からszバイト分の連続した空き領域(a)を発見 [a, a + sz) を使用中と記録 (a をキーとして探索するとszが分かるよう，何らかのデータ構造に記録しておく) このとき，空き領域が足りなくなったら(基準は様々)， 1. 生きている領域をすべて見つける(マーク) 2. 残りの領域を解放(スイープ)

マーク 生きているものすべてに「印」をつける 要するにグラフの探索問題(例えばdepth-first) 印の場所: オブジェクトの先頭に専用の領域を作っておく，ハッシュ表などを作る，などがある 要するにグラフの探索問題(例えばdepth-first)

擬似コード: void GC() { mark_stack = mk_empty_mark_stack(); initialize all memory blocks as `not marked’; for each word p in global variable { mark(p); } for each word p in local variable { mark(p); } while (! empty(mark_stack)) { p = pop (mark_stack); for each word q in the memory block pointed to by p { mark(q); } } for all memory block p not marked { free(p); } } void mark(p) { if (! marked(p)) { record p as `marked’; push(p, mark_stack); } }

「mini-Pythonに自力GCを実装」のチャレンジャーへ 最低限必要なこと アドレスa  aが割り当て中領域であるかどうかが判定できる．そうならばそのサイズ 割り当てた領域のアドレスをすべて列挙できる 全局所変数中のポインタの列挙 全大域変数中のポインタの列挙 あるアドレスaで指されている領域中のポインタの列挙

チャレンジャー用tips 要領1: 空き領域管理は，それ自身重労働．これをmallocにまかせると楽かもしれない my_GC_malloc(sz) { a = malloc(sz); aからszバイト割り当て中と記録; return a; } application my_GC_malloc my_GC_malloc malloc free malloc/free

チャレンジャー用tips 要領2 : 主たる手間は「割り当て中領域」を記録するデータ構造 おそらくハッシュ表を作るのが良いだろう キー : アドレス 値 : 割り当てサイズ + 「印」 注: ポインタとしてありえない値(最下位2bitが0でない)はハッシュ表を引くまでもない

全局所変数の列挙 局所変数はスタックに格納されている．ごく一部はレジスタ スタック: main関数における局所変数のアドレスとGCが起動されたときの局所変数のアドレスに挟まれた領域 レジスタ上の値については，挑戦したい人は質問してください(try “man setjmp”) main interpreter (ほぼすべての)局所変数 eval_... GC()

大域変数の列挙 インタプリタ実装時に，大域変数を使わない(大域変数にポインタを置かない)のが一番簡単 使う場合は， 「大域変数のアドレスをGCに登録するAPI」を用意すると良いかもしれない int * global_var; GC_register_root(&global_var, sizeof(int)); 奥の手については，チャレンジする人は質問してください

GCはいつ起動すべきか ×mallocが成功する限り起動しない 自らある制限(使用中メモリサイズ <= A)を課す メモリ使用量が多くなりすぎる 自らある制限(使用中メモリサイズ <= A)を課す Aをいくらにするか? GC終了後に「生きている量」を測り，その最大値×定数(2～3)とするのが基本