Ancient bugs on Yacc

New Otto malloc helps spot ancient bugs
OpenBSDの開発に多大な貢献（最近はFFS2対応）をしているOtto Moerbeekが、先ごろの c2k8 hackathon で新しいmallocの実装を試みていた。これはページサイズを1として(1/2, 1)の領域を割当てる。もし MALLOC_OPTIONS がG（guard pagesを有効にする）で無い場合でも、アドレスの実体は mmap(2) でランダム化されているため、割当てた領域より後ろへの参照をより確実に SEGV として捉えることが出来る。実装は上手く機能していると思われた。

ところがNikolay Sturmはsparc64上で巨大なC++プロジェクトをコンパイル時にエラーが出る事を発見する。調査を始めたOttoは、どうやら obj/cp/parse.c 内の yyparse() が悪さをしている事を突き止める。

Yacc (Wikipedia)はルール毎にアクションを記述し、ルールに適合した要素を使って結果を定義する。もしアクションの記述が無い場合には、暗黙的に次の記述が補われ、ルールに適合した要素が結果としてそのまま保持される。

{ $$ = $1; }

そして、これに該当する yyparse() 内の処理が次の二行である。

yym   = yylen[yyn];
yyval = yyvsp[1-yym];

ここで yym が 0 の場合、スタックに積まれた先頭の要素、つまりカレントポインタの一つ上のエントリーが yyval に代入される。

この処理は例えば次のようなテキストをパースするとちょっとした問題が発生する。

A: /* empty */ { foo(); };

期待される要素が無いために yyval にはゴミが代入される。実際にその要素は使われる事が無いため、多くの場合は大した問題にはならない。しかしもしスタックが上限値に近い場合、つまり氏の malloc が提供するあそび部分（未割当領域）を参照すると SEGV が発生する。実際、バグが確認されたのはC++コードのコンパイル時、24bytes 先の要素を参照しようとした時点で氏の malloc が確保していたのは 16bytes 先までだった。

振り返ると、このバグはsparc64のページサイズが 8k だったから発見された。Yaccの標準スタックサイズはC++の場合に 24bytes*200=4800bytes で、これはページサイズの半分より若干大きく、ページサイズより小さい。結果、ページの移動が発生することなく正しく SEGV が検知されたわけである。

氏はこの部分を過去に遡って調べた。すると1975年リリースのUNIX 6th editionにおいて、同様の二行が発見されたのだった。

yypv  =- yyr2[n];
yyval =  yypv[1];

まだ -= を =- と表記していた頃の産物である。