本の虫: C++30周年を記念してCFrontのバグ調査をしてみた

Finding Bugs In The First C++ Compiler - What does Bjarne Think!

CFrontの30週年を記念して、C++の設計者にして最初の実装者であるBjarne Stroustrupの実装したC++実装、CFrontに静的解析ツールをかけてバグを洗い出してみた記事が上がっている。

C++の最初のコンパイラーのバグの調査：Bjarneは何考えてたんだ！

C++は先月30周年を記念したので、PVS-Studio開発部署は自前の静的コード解析ツールを使って、最初のC++コンパイラーであるCFrontのバグを探してみようと思い立った。これは奇妙なお祝いの仕方のように思われるだろう、とくに、C++の創始者であるBjarne Stroustrupを問い詰めるわけだから。彼の返答も載っている。

C++の30年の歩み、Bjarne Stroustrup on the 30th anniversary of Cfront (the first C++ compiler)

Bjarne Stroustrupによって開発されたC++は、C with Classesと認知されていた[訳注: これは謝り、C++はC with Classesの経験を元に新たに設計された]。C++の30周年を祝って作成されたこの時系列表は、この言語が1979年に始まって、1985年の10月14日に、BjarneのThe C++ Programming Language初版本とともにリリースされたと書いている。

この時系列表によれば、1985年のCFrontの初リリースから、開発が終了する1993年までに、3度のリリースがあったようだ。

Cpreを元にしたCFrontは、完全なパーサーと、シンボルテーブルと、クラスや関数などのツリー構築を備えている。C++の不思議な制限の多くは、CFrontの実装上の制限に由来している。その理由は、CFrontはC++からCへの変換を行うからだ。つまり、CFrontとはC++プログラマーにとっての神聖なるアーティファクトなのだ。そこで、30周年を記念して、PVS-Studioを使って最初のバージョンをチェックしたくなった。

筆者はCFrontのコードを入手するために、Bjarne Stroustrupに連絡を取った。筆者はコードの入手だけでも長い話になるだろうと考えていたが、とても簡単だった。

ソースコードはオープンで、以下から誰でもダウンロードできる。

C++ Historical Sources Archive — Software Preservation Group

Bjarneによれば、CFrontを検証するのは難しいだろうとのことだ。曰く、

これはとても古いソフトウェアで、1MB 1Mhzのマシンで動作するよう設計されていて、オリジナルのPC(640KB)でも使われていた。これは一人の人間（私）の仕事の一部として開発されていたのだ。

そして、このプロジェクトを検証するのは不可能だと判明した。この当時、クラス名と関数名を分けるのに、ダブルコロン(::)ではなく単一のドット(.)を使っていたのだ。例えば、
inline Pptr type.addrof() { return new ptr(PTR,this,0); }
弊社のPVS-Studioアナライザーはこのコードを解析できない。そこで、筆者は同僚に、コードを見て、このような箇所を手で修正するように依頼した。一応動いたが、まだ問題はあった。アナライザーにコードをチェックさせてみると、混乱して解析を停止する箇所が多々ある。

とにかく、我々はこのプロジェクトを検証した。

結論から言うと、我々は重大な問題を発見できなかった。PVS-Studioが問題を発見できなかった理由は、

プロジェクトサイズが小さい。143ファイル、10万行のコードにすぎない

コードの品質が高い

PVS-Studioはコードの一部を認識できなかった

発見されたバグ

とはいえ、かのStroustrup本人のバグが発見されることを期待している読者をがっかりさせないためにも、コードをみてみよう。

コード1
typedef class classdef = Pclass;

#define PERM(p) p->permanent=1

Pexpr expr.typ(Ptable tbl)
{
    ...
    pclass cl ;
    ...
    cl = (Pclas) nn->tp;
    PERM(cl);
    if(cl == 0) error('i', "%k %s'sT missing", CLASS,s);
    ...
}
PVS-Studio warning: V595 The 'cl' pointer was utilized before it was verified against nullptr. Check lines: 927, 928. expr.c 927

clポインターはNULLに等しい可能性がある。if (cl == 0)によるチェックがその可能性を示唆している。問題は、このポインターはチェックの前に参照されている。問題はPERMマクロの中で発生している。

マクロを展開すると、
cl = (Pclass) nn-tp;
cl->permanent=1;
if (cl == 0) error('i', "%k %s'sT missing", CLASS,s);
コード例2

同じ問題。ポインターが参照された後にチェックされている。
Panme name.normalize(Pbaseb, Pblock bl, bit cast)
{
    ...
    Pname n;
    Pname nn;
    TOK stc = b->b_sto;
    bit tpdf = b->b_typedef;
    bit inli = b->b_inline;
    bit virt = b->b_virtual;
    Pfct f;
    Pname nx;
    if (b == 0) error('i',"#d->N.normalize(0)",this);
    ...
}
PVS-Studio warning: V595 The 'b' pointer was utilized before it was verified against nullptr. Check lines: 608, 615. norm.c 608

コード例3
int error(int i, loc* lc, char* s ...)
{
    ...
    if (in_error++)
        if (t!='t' || 4<in_error) {
            fprintf(stderr, "\nUPS!, error while handling error\n");
            ext(13);
        }
    else if (t == 't')
        t = 'i';
    ...
}
PVS-Studio warning: V563 It is possible that this 'else' branch must apply to the previous 'if' statement. error.c 164

筆者はこれに問題があるのかどうか判別できなかったが、コードのインデントが正しくはない。elseは直近のifに対応する。そのため、このコードは見た目通りに実行されない。

インデントを直すと、以下のようになる。
if (in_error++)
    if (t!='t' || 4<in_error) {
        fprintf(stderr, "\nUPS!, error while handling error\n");
        exit(13);
    } else if (t == 't')
    t = 'i';
コード例4
extern
genericerror(int n, char* s)
{
    fprintf(stderr,"%s\n",
        s?s:"error in generic library function",n);
    abort(111);
    return 0;
}
PVS-Studio warning: V576 Incorrect format. A different number of actual arguments is expected while calling 'fprintf' function. Expected: 3. Present: 4. generic.c 8

フォーマット指定が"%s"なので、文字列は表示されるが、変数nは使われない。

残念ながら（あるいは幸運にも）、筆者はこれ以上の問題を見つけられなかった。アナライザーは他にも警告を出していて、興味深いものもあるが、それほど深刻な問題ではない。

例えば、アナライザーは一部のグローバル変数名が気に入らない様子だ。
extern int Nspy, Nn, Nbt, Nt, Ne, Ns, Nstr, Nc, Nl;
PVS-Studio warning: V707 Giving short names to global variables is considered to be bad practice. It is suggested to rename 'Nn' variable. cfront.h 50

他の例としては、ポインターの値をfprintf()関数で表示する際に、Cfrontは%iを使っている。現代版では、%pがある。とはいえ、筆者の識る限り、30年前に%pはなかったので、コードは正しい。

筆者はまた、この当時のthisポインターは別の方法で使われていたことに注目した。以下のような例だ。
expr.expr(TOK ba, Pexpr a, Pexpr b)
{
    register Pexpr p;

    if (this) goto ret:
    ...
    this=p;
    ...
}

inline toknode.~toknode()
{
    next = free_toks;
    free_toks = this ;
    this = 0;
}
見てわかるように、thisの値を変えるのは禁止されていなかった。今はthisポインターを変更するのは禁止されている。そのため、thisをnullと比較するのは現代では理屈に合わない。

筆者はまた、特に興味深いコード片を発見した。
/* this is the place for paranoia */
if (this == 0) error('i',"->Cdef.dcl(%d)",tbl);
if (base != CLASS) error('i', "Cdef.dcl(%d)",base);
if (cname == 0) error('i',"unNdC");
if (cname->tp != this) error('i',badCdef");
if (tbl == 0) error('i',"Cdef.dcl(%d,0)",cname);
if (tbl->base != TABLE) error('i',""Cdef.dcl(%n,tbl=%d)",
                              cname,tbl->base); 
Bjarne Stroustrupの返答

さて、Bjarneは30年前のエラーに対しどう返答するのか。以下が彼の返した返事だ。

CFrontはCpreからブートストラップされたが、完全な書きかえがあった。CFrontにはCpreのコードは一行もない

use-before-test-of-0はもちろんダメだが、興味深いことに、私が当時使っていたマシンとOS（DECと研究用UNIX）には、page zero write protectがあったので、このバグによる問題が実際発生したならば見逃されずにいただろう

if-then-elseバグは変だ。ソースを読んだところ、単なるインデント間違いではなく、実際の間違いであった。しかし、それほど問題ではない。違いは、異常終了するまえのエラーメッセージの些細な間違いでしかない。見つけられなかったのも無理はない。

そうだ。もっと読みやすい名前を使うべきだった。このコードを他の人間が長期間保守することは想定していなかった（それと私はタイプが下手だった）

そうだ。%pは当時なかった。

そうだ。thisの仕様は変更された。

そのパラノイアテストはコンパイラーのメインループに仕掛けてある。もしソフトウェアかハードウェアに不具合があったならば、そのテストのうちのどれかは失敗するだろう。少なくとも一度、そのコードはCFrontをビルドするツールのコード生成のバグを発見した。思うに、すべての大規模なプログラムは、「不可能」なエラーを発見するための「パラノイアテスト」を含むべきである。

結論

CFrontの価値は計り知れない。プログラミングの開発に多大な影響を与えたし、未だに開発され続けているC++言語を生み出した。C++を作って開発したBjarneの作業には感謝してもし尽くせない。この素晴らしいコンパイラーを検証出来なのはとてもよかった。

Andrey KarpovはProgram Verification Systemsの共同創始者かつCTOである。この会社の主な活動は静的コード解析ツール、PVS-Studioの開発である。AndreyはVisual C++エキスパートとして4回のMicrosoft MVP賞を獲得し、C++ Hintsウェブサイトを運営している。

パラノイアテストが興味深い。

例えば、Chromiumにも含まれている。

「宇宙線が降ってきてメモリのビットが狂う」「ハードウェアのバグでメモリのビットが狂う」というのは非常にまれな現象だけど、Chromeくらいのユーザ数規模になるとけっこう日常的に起きます。なのでChromeで走ってるGCには、それらのビット異常を検知する機構をわざわざ入れてます。
— Kentaro Hara (@xharaken) June 3, 2013

また、URLを忘れたが、どこかのオンラインゲームが、ゲームクライアントのメインループに絶対に失敗しないチェック（簡単な数値計算と結果の比較）を淹れてみたところ、少なからぬ割合のユーザーがチェックに失敗したという。

また、Microsoft Windowsのエラー報告で、xor eax,eaxのような絶対に失敗するはずのないコード箇所でクラッシュした報告を受け取った（ユーザーのCPUにそのようなエラッタはない）ので、調査してみたところ、そのユーザーのPCはショップで組み立て済みで販売されているもので、過剰にオーバークロックされていたとの話もある。

本の虫

2015-11-27

C++30周年を記念してCFrontのバグ調査をしてみた

2 comments: