Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 15503] ファイルの概要

このコミットは、Go言語のリンカ (cmd/ld) とランタイム (src/pkg/runtime) におけるシンボルテーブルのソートに関する重要な修正を含んでいます。特に、シンボルテーブルが正しくソートされていない場合に発生する問題、すなわちスタックトレースの早期停止やガベージコレクタの誤動作を防ぐことを目的としています。

コミット

commit 40ed753ebd6b74747816fde7b130116ff7ef9580
Author: Russ Cox <rsc@golang.org>
Date:   Thu Feb 28 16:21:58 2013 -0500

    cmd/ld: fix symbol table sorting
    runtime: double-check that symbol table is sorted
    
    If the symbol table is unsorted, the binary search in findfunc
    will not find its func, which will make stack traces stop early.
    When the garbage collector starts using the stack tracer,
    that would be a serious problem.
    
    The unsorted symbol addresses came from from two things:
    
    1. The symbols in an ELF object are not necessarily sorted,
       so sort them before adding them to the symbol list.
    
    2. The __i686.get_pc_thunk.bx symbol is present in multiple
       object files and was having its address adjusted multiple
       times, producing an incorrect address in the symbol table.
    
    R=golang-dev, iant
    CC=golang-dev
    https://golang.org/cl/7440044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/40ed753ebd6b74747816fde7b130116ff7ef9580

元コミット内容

cmd/ld: fix symbol table sorting runtime: double-check that symbol table is sorted

シンボルテーブルがソートされていない場合、findfunc 内のバイナリサーチが関数を見つけられず、スタックトレースが途中で停止する問題が発生していました。ガベージコレクタがスタックトレーサーを使用し始めると、これは深刻な問題となるため、この修正は非常に重要です。

シンボルアドレスがソートされていなかった原因は主に以下の2点でした。

  1. ELFオブジェクト内のシンボルが必ずしもソートされているとは限らないため、シンボルリストに追加する前にソートする必要がありました。
  2. __i686.get_pc_thunk.bx シンボルが複数のオブジェクトファイルに存在し、そのアドレスが複数回調整されることで、シンボルテーブル内で誤ったアドレスが生成されていました。

変更の背景

Go言語の実行時環境において、スタックトレースの正確性はデバッグやプロファイリングにおいて極めて重要です。特に、ガベージコレクタ（GC）がスタックトレーサーを利用するようになると、スタックトレースの信頼性がシステムの安定性やパフォーマンスに直結します。

このコミット以前は、リンカが生成するシンボルテーブルが常にアドレス順にソートされているとは限りませんでした。シンボルテーブルは、プログラム内の関数や変数などのシンボルと、それらがメモリ上で配置されるアドレスとのマッピングを保持するデータ構造です。Goランタイムの findfunc 関数は、特定のプログラムカウンタ（PC）値に対応する関数情報を見つけるために、このシンボルテーブルに対してバイナリサーチを実行します。バイナリサーチはデータがソートされていることを前提とするため、シンボルテーブルがソートされていないと、findfunc は正しい関数情報を見つけることができず、結果としてスタックトレースが不完全になったり、誤った情報が表示されたりする可能性がありました。

さらに、特定の環境（特にi686アーキテクチャ）で生成される __i686.get_pc_thunk.bx のような特殊なシンボルが、複数のオブジェクトファイルに重複して存在し、リンカがそれらのアドレスを誤って処理することで、シンボルテーブルの整合性が損なわれる問題も発生していました。これらの問題が複合的に作用し、Goプログラムの実行時における信頼性に影響を与えていたため、根本的な解決が必要とされていました。

前提知識の解説

1. シンボルテーブル (Symbol Table)

シンボルテーブルは、コンパイルされたプログラム内で使用されるシンボル（関数名、変数名など）と、それらがメモリ上で占めるアドレスやサイズなどの情報との対応付けを記録したデータ構造です。リンカは、複数のオブジェクトファイルやライブラリを結合して最終的な実行可能ファイルを生成する際に、これらのシンボルテーブルを参照し、シンボル参照を解決します。デバッガやプロファイラは、実行中のプログラムのシンボルテーブルを利用して、メモリ上のアドレスを人間が理解できる関数名や変数名に変換し、スタックトレースの生成や変数内容の表示を行います。

2. リンカ (Linker)

リンカは、コンパイラによって生成された複数のオブジェクトファイル（.o や .obj ファイル）とライブラリを結合し、単一の実行可能ファイルや共有ライブラリを生成するプログラムです。リンカの主な役割は以下の通りです。

  • シンボル解決: あるオブジェクトファイルで定義された関数や変数を、別のオブジェクトファイルから参照している場合、リンカはその参照を解決し、正しいメモリ位置にリンクします。
  • アドレス割り当て: 各セクション（コード、データなど）をメモリ上の特定のアドレスに配置します。
  • 再配置: コード内のアドレス参照を、最終的なメモリ配置に合わせて調整します。

3. ELF (Executable and Linkable Format)

ELFは、Unix系システム（Linuxなど）で広く使用されている実行可能ファイル、オブジェクトファイル、共有ライブラリの標準ファイルフォーマットです。ELFファイルは、ヘッダ、プログラムヘッダテーブル、セクションヘッダテーブル、および様々なセクション（.text、.data、.symtab など）で構成されます。.symtab セクションはシンボルテーブルを格納します。ELF仕様では、シンボルテーブル内のエントリが特定のアドレス順にソートされていることを義務付けていません。

4. findfunc 関数とスタックトレース

Goランタイムには、プログラムカウンタ（PC）値から対応する関数情報を検索する findfunc のような関数が存在します。この関数は通常、シンボルテーブルに対してバイナリサーチを実行することで効率的に検索を行います。バイナリサーチは、データがソートされている場合にのみ正しく機能し、検索時間を大幅に短縮できます。スタックトレースは、プログラムがクラッシュしたり、特定のイベントが発生したりしたときに、その時点での関数呼び出しの履歴（コールスタック）を表示するものです。これはデバッグにおいて非常に有用な情報であり、findfunc のような関数が正確に動作することが不可欠です。

5. ガベージコレクタ (Garbage Collector)

ガベージコレクタは、プログラムが動的に確保したメモリのうち、もはや使用されていない（到達不能な）領域を自動的に解放するシステムです。Go言語のGCは、スタックをスキャンして到達可能なオブジェクトを特定する際に、スタックトレースの情報を利用することがあります。もしスタックトレースが不正確であれば、GCが誤って使用中のメモリを解放してしまったり、逆に不要なメモリを解放し損ねたりする可能性があり、プログラムのクラッシュやメモリリークにつながる可能性があります。

6. __i686.get_pc_thunk.bx シンボル

このシンボルは、主にi686（32ビットx86）アーキテクチャにおいて、位置独立コード（PIC: Position-Independent Code）を生成する際に使用される特殊なシンボルです。PICは、プログラムがメモリ上のどこにロードされても正しく実行できるように設計されたコードであり、共有ライブラリなどでよく用いられます。get_pc_thunk は、現在のプログラムカウンタ（PC）の値をレジスタにロードするための小さなコードスニペット（thunk）を指します。bx は、ebx レジスタを使用することを示唆しています。複数のオブジェクトファイルがそれぞれ独自の __i686.get_pc_thunk.bx シンボルを持つことがあり、リンカがこれらを適切にマージまたは処理しないと、シンボルテーブル内で重複したエントリや誤ったアドレスが生成される原因となります。

技術的詳細

このコミットは、Goリンカ (cmd/ld) とランタイム (src/pkg/runtime) の両方に変更を加えて、シンボルテーブルのソート問題を解決しています。

リンカ (cmd/ld) 側の変更

リンカは、オブジェクトファイルからシンボルを読み込み、それらを結合して最終的なシンボルテーブルを構築します。このコミットでは、以下の主要な変更が行われました。

  1. 汎用ソート関数の導入:

    • src/cmd/ld/data.c にあった datsort 関数が、より汎用的な listsort 関数に置き換えられました。
    • listsort は、連結リストをソートするためのマージソートアルゴリズムを実装しており、比較関数 (cmp) と次の要素へのオフセット (off) を引数として受け取ります。これにより、異なる種類のシンボルリスト（例えば、アドレス順や名前順）をソートする際に再利用可能になります。
    • #define NEXT(l) (*(Sym**)((char*)(l)+off)) マクロが導入され、リストの次の要素へのポインタを抽象化しています。

  2. ELFシンボルのソート:

    • src/cmd/ld/ldelf.c において、ELFオブジェクトファイルから読み込まれたシンボルが、アドレス (value) に基づいてソートされるようになりました。
    • 新しい比較関数 valuecmp が導入され、シンボルの value フィールドを比較します。
    • listsort 関数が s->sub リスト（サブシンボルリスト）のソートにも使用され、textp (テキストセクションのシンボルリスト) に追加される前に、アドレス順にソートされることが保証されます。
    • これにより、ELFオブジェクトファイル内のシンボルが必ずしもソートされていないという問題が解決されます。

  3. Mach-O および PE シンボルのソート:

    • src/cmd/ld/ldmacho.c (Mach-Oフォーマット、macOSで使用) および src/cmd/ld/ldpe.c (PEフォーマット、Windowsで使用) においても、同様にシンボルがアドレス順にソートされるようになりました。
    • これらのリンカバックエンドでも、listsort と valuecmp を使用して、テキストセクションのシンボルリストがアドレス順に維持されるように変更されています。

  4. 重複シンボル参照の検出とエラー処理:

    • ldelf.c, ldmacho.c, ldpe.c の各ファイルで、s->outer != S のチェックが追加されました。これは、シンボルが既に別のセクションに属している場合に、重複参照として診断し、エラー終了するロジックです。ただし、s->dupok が設定されている場合は重複を許容します。これは、__i686.get_pc_thunk.bx のような特定のシンボルが複数のオブジェクトファイルに存在しうるケースに対応するためです。

  5. SHIDDEN フラグの扱い:

    • src/cmd/ld/ldelf.c において、SHIDDEN フラグが s->type = SHIDDEN; ではなく s->type |= SHIDDEN; と設定されるようになりました。これは、シンボルの既存のタイプ情報を保持しつつ、隠しシンボルであることを示すフラグを追加するための変更です。SHIDDEN は、リンカがシンボルを処理する際に、そのシンボルが外部に公開されないことを示すために使用されます。

ランタイム (src/pkg/runtime) 側の変更

ランタイムは、リンカによって生成されたシンボルテーブルを利用します。このコミットでは、シンボルテーブルの整合性を実行時に検証するためのチェックが追加されました。

  1. シンボル順序の実行時チェック:
    • src/pkg/runtime/symtab.c の dofunc 関数に、シンボルアドレスの順序をチェックするロジックが追加されました。
    • lastvalue という静的変数が導入され、処理された最後のシンボルのアドレスを保持します。
    • 新しいシンボルのアドレス (sym->value) が lastvalue よりも小さい場合（つまり、シンボルが順序通りでない場合）、runtime·throw("malformed symbol table"); を呼び出してパニックを発生させます。
    • このチェックは、buildfuncs 関数がシンボルテーブルを構築する際に walksymtab(dofunc) を呼び出すたびに実行されます。
    • これにより、リンカがシンボルテーブルを正しくソートしなかった場合に、実行時に早期に問題を検出できるようになります。

これらの変更により、リンカはシンボルテーブルを常にアドレス順にソートして出力するようになり、ランタイムはそれを検証することで、findfunc の正確な動作と、それを利用するスタックトレースやガベージコレクタの信頼性が向上します。

コアとなるコードの変更箇所

src/cmd/ld/data.c

  • datsort 関数が削除され、より汎用的な listsort 関数が導入されました。
  • dodata 関数内で、datap = datsort(datap); が datap = listsort(datap, datcmp, offsetof(Sym, next)); に変更され、データシンボルリストのソートに新しい汎用関数が使用されるようになりました。

src/cmd/ld/ldelf.c

  • valuecmp 関数が追加され、シンボルの value (アドレス) に基づいて比較を行います。
  • ldelf 関数内で、シンボルを textp (テキストセクションのシンボルリスト) に追加する際に、listsort と valuecmp を使用してアドレス順にソートされるようになりました。
  • 重複シンボル参照のチェックとエラー処理が追加されました。
  • s->type = SHIDDEN; が s->type |= SHIDDEN; に変更されました。

src/cmd/ld/ldmacho.c および src/cmd/ld/ldpe.c

  • ldmacho および ldpe 関数内で、ldelf.c と同様に、シンボルを textp に追加する際に listsort と valuecmp を使用してアドレス順にソートされるようになりました。
  • 重複シンボル参照のチェックとエラー処理が追加されました。

src/cmd/ld/lib.h

  • datsort 関数の宣言が削除され、listsort と valuecmp 関数の宣言が追加されました。

src/pkg/runtime/symtab.c

  • lastvalue という静的変数が追加されました。
  • dofunc 関数内で、sym->value < lastvalue のチェックが追加され、シンボルアドレスが順序通りでない場合にパニックを発生させるようになりました。
  • buildfuncs 関数内で、nfunc と lastvalue が初期化されるようになりました。

コアとなるコードの解説

listsort 関数 (src/cmd/ld/data.c)

Sym*
listsort(Sym *l, int (*cmp)(Sym*, Sym*), int off)
{
 	Sym *l1, *l2, *le;
 	#define NEXT(l) (*(Sym**)((char*)(l)+off))

 	if(l == 0 || NEXT(l) == 0)
 		return l;

 	l1 = l;
 	l2 = l;
 	for(;;) {
 		l2 = NEXT(l2);
 		if(l2 == 0)
 			break;
 		l2 = NEXT(l2);
 		if(l2 == 0)
 			break;
 		l1 = NEXT(l1);
 	}

 	l2 = NEXT(l1);
 	NEXT(l1) = 0;
 	l1 = listsort(l, cmp, off);
 	l2 = listsort(l2, cmp, off);

 	/* set up lead element */
 	if(cmp(l1, l2) < 0) {
 		l = l1;
 		l1 = NEXT(l1);
 	} else {
 		l = l2;
 		l2 = NEXT(l2);
 	}
 	le = l;

 	for(;;) {
 		if(l1 == 0) {
 			while(l2) {
 				NEXT(le) = l2;
 				le = l2;
 				l2 = NEXT(l2);
 			}
 			NEXT(le) = 0;
 			break;
 		}
 		if(l2 == 0) {
 			while(l1) {
 				NEXT(le) = l1;
 				le = l1;
 				l1 = NEXT(l1);
 			}
 			break;
 		}
 		if(cmp(l1, l2) < 0) {
 			NEXT(le) = l1;
 			le = l1;
 			l1 = NEXT(l1);
 		} else {
 			NEXT(le) = l2;
 			le = l2;
 			l2 = NEXT(l2);
 		}
 	}
 	NEXT(le) = 0;
 	return l;
 	
 	#undef NEXT
}

この関数は、連結リストをソートするためのマージソートアルゴリズムを実装しています。

  • l: ソートする連結リストの先頭要素へのポインタ。
  • cmp: 2つの Sym ポインタを受け取り、それらの相対順序を示す整数を返す比較関数。
  • off: Sym 構造体内で次の要素へのポインタが格納されているメンバのオフセット。これにより、Sym 構造体の異なる連結リスト（例: next や sub）をソートできます。
  • NEXT(l) マクロは、off を使用して次の要素へのポインタを間接的に取得します。
  • 関数はリストを2つに分割し、それぞれを再帰的にソートした後、マージして最終的なソート済みリストを生成します。

valuecmp 関数 (src/cmd/ld/ldelf.c)

int
valuecmp(Sym *a, Sym *b)
{
	if(a->value < b->value)
		return -1;
	if(a->value > b->value)
		return +1;
	return 0;
}

この関数は、2つの Sym ポインタ a と b を受け取り、それらの value フィールド（シンボルのアドレス）を比較します。listsort 関数に渡される比較関数として使用され、シンボルをアドレス順にソートするために利用されます。

dofunc 関数内のシンボル順序チェック (src/pkg/runtime/symtab.c)

static uintptr lastvalue;

static void
dofunc(Sym *sym)
{
 	Func *f;
 	
 	switch(sym->symtype) {
 	case 't':
 	case 'T':
 	case 'l':
 	case 'L':
 		if(runtime·strcmp(sym->name, (byte*)"etext") == 0)
 			break;
 		if(sym->value < lastvalue) {
 			runtime·printf("symbols out of order: %p before %p\n", lastvalue, sym->value);
 			runtime·throw("malformed symbol table");
 		}
 		lastvalue = sym->value;
 		if(func == nil) {
 			nfunc++;
 			break;
 		}
 		// ... (既存の処理)
 	}
}

このコードスニペットは、Goランタイムがシンボルテーブルを走査する際に、シンボルがアドレス順に並んでいるかを検証します。

  • lastvalue は、直前に処理されたシンボルのアドレスを保持します。
  • 現在のシンボル sym のアドレス (sym->value) が lastvalue よりも小さい場合、シンボルテーブルが正しくソートされていないことを意味します。
  • このような不整合が検出された場合、エラーメッセージを出力し、runtime·throw("malformed symbol table"); を呼び出してプログラムを異常終了させます。これにより、シンボルテーブルの破損が原因で発生する可能性のある、より深刻な実行時エラー（例: 不正確なスタックトレース、GCの誤動作）を未然に防ぎます。

関連リンク

参考にした情報源リンク