Tag Discussion Solution Statistics Submit
 

Time Limit : sec, Memory Limit : KB
English / Japanese  

Memory Leak

Time Limit: 8 sec / Memory Limit: 64 MB

D: メモリーリーク

あなたの研究室の同期が, 実装中のソフトウェアのバグに悩まされていた. 彼のソフトウェアは, かなり下位のレイヤで動作するソフトウェアであるため, 高機能のデバッガやテストツールなどは使用することができない. OS による補助がない環境であるため, 言語上使えるはずの例外処理など使えないし, 標準ライブラリですら大半のものが使用できない. ガベージコレクタなんて夢のまた夢である. そのため彼は, これまでトライアルアンドエラーによって自力で検証を行い, 修正を行ってきた. しかし, 今回のバグは相当根が深いらしく, 彼はもう一ヶ月近くに渡り検証を繰り返していた. 締切までにこのバグが修正できなかったため, 彼は論文提出を見送っている. 夜中の研究室には, 断続的に彼の奇声が聞こえている始末である. 見兼ねたあなたは, 彼のソフトウェアの検証を手伝うことにした.

これまでの彼のがんばりによって, プログラムではいわゆるメモリリークが発生している可能性が高いらしい. どうやらプログラムのどこかで, 確保したメモリを解放し忘れていることが原因で, 使用できるメモリを使い果たしてしまっているようである. 彼のプログラムはそのままでは複雑すぎるので, 彼はメモリの確保や解放を行う処理を簡単に表現し, パターン化したものを用意してくれた. このパターンごとにどの程度メモリリークが発生するかを調べて欲しいとのことである.

まず前提として, 彼のプログラムでは, メモリマネージャというモジュールによって, メモリ領域の確保や解放といった機能が提供されているらしい. メモリ領域を確保するとは, 正確にはメモリマネージャが管理するヒープと呼ばれるメモリ領域から, 必要な分を借り受け, その領域への「参照」を得ることである. なお, ヒープには上限があり, プログラムからそれ以上のメモリは利用できない. メモリ領域の大きさには「バイト」が用いられる.

「参照」とは, その領域が存在する場所を示す値である. 参照は, 変数に代入するか, 直接別のメモリ領域の確保や解放の機能へ渡す引数として利用することができる. メモリ領域を解放するとは, 使わなくなったメモリ領域をメモリマネージャに返却することである.

そして, 彼の用意したパターンは以下の BNF で表現できるものであった. 

<line>           ::= <expr> | <free>
<expr>           ::= "(" <expr> ")" | <assign> | "NULL" | <variable> | <malloc> | <clone>
<assign>         ::= <variable> "=" <expr>
<malloc>         ::= "malloc(" <number> ")"
<free>           ::= "free(" <expr> ")"
<clone>          ::= "clone(" <expr> ")"
<variable>       ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I"
                   | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R"
                   | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z"
<number>         ::= <non_zero_digit> | <number> <digit>
<non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit>          ::= "0" | <non_zero_digit>

変数(variables)は, 参照の入れ物とて機能し, 名前としてアルファベットの大文字一文字を使用できる. 変数は, 今回問題となるヒープとは別の領域に確保されるため, 変数そのものが使用するメモリ量を気にする必要はない. なお, 変数は明示的に値を代入されない限り, 更新されない. また, 初期値は特に決まっておらず, どのような値を持っているかわからないことに注意しなければならない. なお, 変数は評価結果として, その変数の持つ参照を返す.

代入(assign)は, 参照の値をコピーする. 右辺の式を評価して得られる参照を左辺の変数にコピーする. 初期化されていない変数や free された変数も代入することができる. これは, 参照とは領域の場所を示す「値」でしかないため, 別の変数に代入しても, 実際に意図しない領域を操作してしまうことはない. なお, 代入そのものは, 変数に代入された参照を返す.

malloc, free, clone は, メモリマネージャの機能を呼び出ていることを示している.

  • malloc は, 引数で渡された1以上の整数サイズ分のメモリ領域を確保し, その領域への参照を返す.
  • free は, 引数に確保済みのメモリ領域への参照を与えることで, その領域を解放する. なお, 評価しても何も返さない.
  • clone は, 引数に確保済みのメモリ領域への参照を与えることで, その領域をコピーする. 今回の検証では同じサイズ分の領域をもう一つ確保すると考えればよい.

なお, malloc や clone のメモリ確保のアルゴリズム自体は精錬されているため, 割り当て用のメモリ領域が断片化することはない. また, free した領域は即座に解放され, 再利用可能になる. ただし, 初期化されていない領域や既に free された領域に対して clone や free した場合, 意図しないメモリ領域に対してコピーや解放が行なわれてしまい, 何が起こるかわからない. このような動作は, 別のバグの原因となっている可能性があるため, 彼に知らせる必要がある. 与えられたメモリの上限超えて malloc しようとした場合には, NULL という特殊な参照が返される. 同様に clone でコピーされる領域分のメモリが残っていない場合にも, NULL が返される.

この NULL は特定のメモリ領域を参照していないことを示す. 通常の参照と同様に NULL は変数に代入でき, 参照を引数にとる clone や free に渡すことができる. ただし, free に NULL を引数で渡していた場合, 何も起こらないことが保証されている. また, clone に NULL を引数で渡した場合でも, 何も起こらず, NULL が返される.

評価すると参照を返す式(expr)は, "(" ")" を使うことで入れ子にすることができる. この場合, "(" ")"の内部の評価結果がその外側へ返されることになる. なお, free は参照を返さないので, 入れ子にすることができない.

あなたの仕事は, パターンとして与えられた全ての行を実行した後に, 参照されていない確保済みのメモリ領域のバイト数の合計を計算することである. なお, 与えられた全ての行を実行した後に, 一つ以上の変数が参照を持っている領域については気にしなくてよい. また, 別のバグの原因を発見した場合には, 彼に知らせなければならない.

あなたは, パターンの分析をするためのプログラムを組むことした. そのために, 彼の示すいくつかのパターンについて考察した.

図1

図1は, ヒープが 100 バイト存在する状態で, 以下のようなパターンを実行したときの状態の遷移を示している 

A=malloc(10)
B=clone(A)
free(A)

まず, 1行目では, malloc によって 10 バイトの領域を確保し, その領域への参照を変数 A に代入している. 残りの使用可能なヒープは, 90 バイトとなる 次に, 2行目では, 先ほど確保した領域への参照を持つ変数 A を clone に渡している. これにより, 新たに10バイトの領域が確保され, 残りの使用可能なヒープは, 80 バイトとなる. 新たに確保された 10 バイトの領域への参照は, 変数 B に代入される. そして, 3行目では, 1行目で確保された領域への参照を持つ変数 A を free に渡している. これにより, 10バイトの領域が解放され, 残りの使用可能なヒープは, 90 バイトとなる. 以上で, このパターンの実行は終了である. この場合では, 参照されていない確保済みの領域は存在しないため, 検証の結果は 0 バイトとなる. 2行目で確保された 10 バイトの領域は, 変数 B が参照を持っているため, メモリリークとして扱わない. また, 変数 A は3行目で free に渡された後, 代入によって更新されていない. そのため, この時点でも先ほど解放された領域への参照を持ったままである. もしこの後に, この領域を free あるいは clone するような命令があった場合は, 検証結果として Error を出力する必要がある.

図2

図2は, ヒープが100存在する状態で, 以下のようなパターンを実行したときの状態の遷移を示している 

A=clone(clone(malloc(10)))

この場合は, まず malloc(10) が実行され, 10バイトの領域が確保される. この領域への参照はそのまま clone に渡され, さらに 10バイトの領域が確保される. この clone によって確保された領域も外側の clone に渡され, さらに10バイトの領域が確保される. 最後に確保された領域への参照が変数 A に代入される. 最初の malloc で確保された領域や内側の clone で確保された領域は, どの変数も参照を持っておらず, 解放することができなくなってしまう. よって, このパターンの検証結果は 20 バイトとなる.

Input

入力は以下の形式で与えられる． 

M
line1
line2
line3
...
linei
...

入力の形式で用いられる変数の意味は次の通りである．

  • 1行目の M はヒープの上限であり, 0 <= M <= 5000 である.
  • linei は前述 BNF で示される式であり, EOF まで続き，100行を超えない．
  • linei は 300 文字を超えないとする
  • malloc に引数として与えられるメモリ領域の大きさ size は 1 <= size <= 5000 である.

Output

入力で与えられた全ての行を実行した後に, 参照されていない確保済みのメモリ領域のバイト数の合計を出力せよ. メモリリーク以外のエラーが発生していた場合には, "Error" と出力せよ.

Sample Input 1

100
A=malloc(10)
B=clone(A)
free(A)

Sample Output 1

0

Sample Input 2

100
A=clone(clone(malloc(10)))

Sample Output 2

20

Sample Input 3

30
clone(clone(clone(clone(malloc(10)))))

Sample Output 3

30

Sample Input 4

100
free(A)
A=malloc(12)
NULL
N=clone(NULL)

Sample Output 4

Error
Source: https://onlinejudge.u-aizu.ac.jp/problems/2365