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

このコミットは、Go言語のリンカ（liblink）におけるハッシュ衝突の誤った処理を修正するものです。特に、シンボルルックアップ時のハッシュテーブルの挙動と、それに起因するシンボルリストの破損、そして最終的なクラッシュの問題に対処しています。

コミット

commit 468cf827803ddffd0d72167c44f750dde004aae4
Author: Russ Cox <rsc@golang.org>
Date:   Wed Apr 16 11:53:14 2014 -0400

    liblink: fix incorrect hash collision in lookup
    
    linklookup uses hash(name, v) as the hash table index but then
    only compares name to find a symbol to return.
    If hash(name, v1) == hash(name, v2) for v1 != v2, the lookup
    for v2 will return the symbol with v1.
    
    The input routines assume that each symbol is found only once,
    and then each symbol is added to a linked list, with the list header
    in the symbol. Adding a symbol to such a list multiple times
    short-circuits the list the second time it is added, causing symbols
    to be dropped.
    
    The liblink rewrite introduced an elegant, if inefficient, handling
    of duplicated symbols by creating a dummy symbol to read the
    duplicate into. The dummy symbols are named .dup with
    sequential version numbers. With many .dup symbols, eventually
    there will be a conflict, causing a duplicate list add, causing elided
    symbols, causing a crash when calling one of the elided symbols.
    
    The bug is old (2011) but could not have manifested until the
    liblink rewrite introduced this heavily duplicated symbol .dup.
    (See History section below.)
    
    1. Correct the lookup function.
    
    2. Since we want all the .dup symbols to be different, there's no
    point in inserting them into the table. Call linknewsym directly,
    avoiding the lookup function entirely.
    
    3. Since nothing can refer to the .dup symbols, do not bother
    adding them to the list of functions (textp) at all.
    
    4. In lieu of a unit test, introduce additional consistency checks to
    detect adding a symbol to a list multiple times. This would have
    caught the short-circuit more directly, and it will detect a variety
    of double-use bugs, including the one arising from the bad lookup.
    
    Fixes #7749.
    
    History
    
    On April 9, 2011, I submitted CL 4383047, making ld 25% faster.
    Much of the focus was on the hash table lookup function, and
    one of the changes was to remove the s->version == v comparison [1].
    
    I don't know if this was a simple editing error or if I reasoned that
    same name but different v would yield a different hash slot and
    so the name test alone sufficed. It is tempting to claim the former,
    but it was probably the latter.
    
    Because the hash is an iterated multiply+add, the version ends up
    adding v*3ⁿ to the hash, where n is the length of the name.
    A collision would need x*3ⁿ ≡ y*3ⁿ (mod 2²⁴ mod 100003),\n    or equivalently x*3ⁿ ≡ x*3ⁿ + (y-x)*3ⁿ (mod 2²⁴ mod 100003),\n    so collisions will actually be periodic: versions x and y collide\n    when d = y-x satisfies d*3ⁿ ≡ 0 (mod 2²⁴ mod 100003).\n    Since we allocate version numbers sequentially, this is actually\n    about the best case one could imagine: the collision rate is\n    much lower than if the hash were more random.\n    http://play.golang.org/p/TScD41c_hA computes the collision\n    period for various name lengths.\n    \n    The most common symbol in the new linker is .dup, and for n=4\n    the period is maximized: the 100004th symbol is the first collision.\n    Unfortunately, there are programs with more duplicated symbols\n    than that.\n    \n    In Go 1.2 and before, duplicate symbols were handled without\n    creating a dummy symbol, so this particular case for generating\n    many duplicate symbols could not happen. Go does not use\n    versioned symbols. Only C does; each input file gives a different\n    version to its static declarations. There just aren't enough C files\n    for this to come up in that context.\n    \n    So the bug is old but the realization of the bug is new.\n    \n    [1] https://golang.org/cl/4383047/diff/5001/src/cmd/ld/lib.c\n    \n    LGTM=minux.ma, iant, dave\n    R=golang-codereviews, minux.ma, bradfitz, iant, dave\n    CC=golang-codereviews, r\n    https://golang.org/cl/87910047\n```

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

[https://github.com/golang/go/commit/468cf827803ddffd0d72167c44f750dde004aae4](https://github.com/golang/go/commit/468cf827803ddffd0d72167c44f750dde004aae4)

## 元コミット内容

このコミットは、Goリンカの`liblink`におけるハッシュ衝突の誤った処理を修正するものです。具体的には、`linklookup`関数がハッシュテーブルのインデックスとしてシンボルの名前とバージョン（`hash(name, v)`）を使用しているにもかかわらず、実際のシンボル比較では名前（`name`）のみを比較していた問題が指摘されています。

この不整合により、`hash(name, v1) == hash(name, v2)`となるが`v1 != v2`であるような場合に、`v2`のルックアップが誤って`v1`のシンボルを返してしまう可能性がありました。

さらに、リンカの入力ルーチンは各シンボルが一度だけ見つかり、その後リンクリストに追加されることを前提としています。しかし、上記のハッシュ衝突によって同じシンボルが複数回リストに追加されると、リストが短絡（short-circuit）され、一部のシンボルがリストから脱落（elided）してしまう問題が発生しました。

この問題は、`liblink`の書き換えによって導入された、重複シンボルを処理するためのダミーシンボル（`.dup`という名前で連番のバージョンを持つ）の存在によって顕在化しました。多数の`.dup`シンボルが生成されると、最終的にハッシュ衝突が発生し、シンボルが重複してリストに追加され、結果として脱落したシンボルを呼び出そうとした際にクラッシュを引き起こしていました。

このバグ自体は2011年と古くから存在していましたが、`liblink`の書き換えによって`.dup`シンボルが大量に生成されるようになるまで、その影響が表面化することはありませんでした。

## 変更の背景

このコミットの背景には、Goリンカの性能改善と、それに伴う意図しない副作用があります。

2011年4月9日にRuss Cox氏によって提出されたCL 4383047は、リンカ（`ld`）の処理速度を25%向上させることを目的としていました。この変更の一環として、ハッシュテーブルのルックアップ関数からシンボルのバージョン比較（`s->version == v`）が削除されました。コミットメッセージによると、この削除が単純な編集ミスだったのか、あるいは「同じ名前でもバージョンが異なれば異なるハッシュスロットになるため、名前の比較だけで十分」という推論に基づいていたのかは不明ですが、後者の可能性が高いとされています。

しかし、この変更がハッシュ衝突の潜在的な問題を引き起こしました。ハッシュ関数が名前とバージョンに基づいて計算されるにもかかわらず、ルックアップ時にバージョンを比較しないことで、異なるバージョンのシンボルが同じハッシュスロットに格納され、誤って取得される可能性が生じたのです。

この問題が顕在化したのは、`liblink`の内部的な書き換えによって、重複シンボルを扱うための新しいメカニズムが導入されてからです。Go 1.2以前では、重複シンボルはダミーシンボルを作成せずに処理されていました。しかし、新しいリンカでは、重複シンボルを読み込む際に`.dup`という名前のダミーシンボルが連番のバージョンを付けて大量に生成されるようになりました。

この`.dup`シンボルは、その性質上、同じ名前（`.dup`）を持ちながら異なるバージョンを持つシンボルが多数存在することになります。これにより、以前は問題にならなかったハッシュ衝突が頻繁に発生するようになり、リンカのシンボル管理ロジックに深刻な影響を与え、最終的にクラッシュを引き起こすようになりました。

つまり、リンカの性能改善のための変更が、後のリンカの内部構造変更によって、予期せぬ形で古いバグを表面化させた、という経緯があります。

## 前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

### リンカ (Linker)
リンカは、コンパイラによって生成された複数のオブジェクトファイルやライブラリを結合し、実行可能なプログラムやライブラリを生成するソフトウェアです。シンボル解決（異なるファイルで定義された関数や変数を結びつける）や、メモリ配置の決定などを行います。

### シンボル (Symbol)
プログラミングにおいて、シンボルとは関数名、変数名、ラベルなど、プログラム内の特定のエンティティを識別するための名前です。リンカはこれらのシンボルを使って、プログラムの異なる部分を結合します。

### ハッシュテーブル (Hash Table)
ハッシュテーブルは、キーと値のペアを格納するためのデータ構造です。キーをハッシュ関数に通して得られるハッシュ値を使って、データが格納されるメモリ上の位置（インデックス）を計算します。これにより、高速なデータの挿入、検索、削除が可能になります。
ハッシュテーブルでは、異なるキーが同じハッシュ値を生成する「ハッシュ衝突（Hash Collision）」が発生する可能性があります。これを解決するために、チェイニング（同じハッシュ値を持つ要素をリンクリストでつなぐ）やオープンアドレス法などの手法が用いられます。

### シンボルバージョン (Symbol Version)
一部のリンカやプログラミング言語（特にC言語の静的変数など）では、同じ名前のシンボルでも、異なるソースファイルやコンパイル単位で定義された場合に、区別するためにバージョン番号が付与されることがあります。これにより、リンカは同じ名前のシンボルの中から適切なものを選択できます。Go言語自体は通常、バージョン付きシンボルを使用しませんが、C言語のコードをリンクする際にリンカが内部的に扱うことがあります。

### `liblink`
`liblink`は、Go言語のツールチェインの一部であるリンカのライブラリです。Goプログラムのビルドプロセスにおいて、コンパイルされたGoコードとCgoによってリンクされるC/C++コードなどを結合し、最終的な実行ファイルを生成する役割を担っています。

### リンクリスト (Linked List)
リンクリストは、データの要素（ノード）が順序付けられて並べられたデータ構造です。各ノードはデータと、次のノードへのポインタ（参照）を含みます。シンボルを管理するために、リンカの内部でシンボルを特定の順序で保持するために使用されることがあります。

### `sysfatal`
Go言語のツールチェインにおける内部的なエラー報告メカニズムの一つです。致命的なエラーが発生した場合にプログラムを終了させ、エラーメッセージを出力します。開発時やデバッグ時に、予期せぬ状態を検出するために用いられます。

## 技術的詳細

このコミットの技術的詳細は、主にリンカのシンボル管理、特にハッシュテーブルのルックアップロジックと、シンボルがリンクリストに追加される際の整合性チェックに焦点を当てています。

### 1. `linklookup`関数の修正
リンカのシンボルルックアップ関数である`linklookup`は、シンボル名とバージョン番号`v`に基づいてハッシュ値を計算し、ハッシュテーブルのインデックスとして使用していました。しかし、ハッシュテーブルからシンボルを取得する際の比較ロジックが不完全で、シンボル名（`s->name`）のみを比較し、バージョン（`s->version`）を比較していませんでした。

```c
// src/liblink/sym.c の変更前
for(s = ctxt->hash[h]; s != nil; s = s->hash)
    if(strcmp(s->name, symb) == 0) // バージョン比較が欠落
        return s;

// src/liblink/sym.c の変更後
for(s = ctxt->hash[h]; s != nil; s = s->hash)
    if(s->version == v && strcmp(s->name, symb) == 0) // バージョン比較を追加
        return s;

この修正により、linklookupは名前とバージョンの両方が一致するシンボルのみを返すようになり、異なるバージョンのシンボルが同じハッシュスロットに衝突した場合でも、誤ったシンボルが選択されることがなくなりました。

2. .dupシンボルの特殊な扱い

liblinkの書き換えにより導入された.dupシンボルは、重複するシンボルを一時的に保持するためのダミーシンボルです。これらのシンボルは、リンカの内部処理で一時的に使用されるものであり、最終的な実行ファイルには含まれませんし、他のシンボルから参照されることもありません。

コミットでは、これらの.dupシンボルをハッシュテーブルに挿入すること自体が無意味であると判断されました。なぜなら、これらのシンボルは常に新しいものであり、ルックアップされる必要がないからです。

// src/liblink/objfile.c の変更前
s = linklookup(ctxt, ".dup", ndup++); // linklookup を使用

// src/liblink/objfile.c の変更後
s = linknewsym(ctxt, ".dup", ndup++); // linknewsym を直接呼び出し

linknewsymを直接呼び出すことで、ハッシュテーブルのルックアッププロセスを完全に回避し、.dupシンボルがハッシュ衝突を引き起こす可能性を根本的に排除しています。

さらに、.dupシンボルは実行可能なコード（テキストセグメント）やデータセグメントのリンクリスト（textpやdatap）に追加する必要がないと判断されました。これは、これらのシンボルがプログラムの実行時に意味を持つものではないためです。この変更により、リンカの内部リストの肥大化を防ぎ、不必要な処理を削減しています。

3. シンボルリストへの複数回追加の検出 (onlistフラグ)

このバグの根本的な原因の一つは、シンボルがリンクリストに複数回追加されることでリストが破損し、シンボルが脱落してしまうことでした。これを防ぐため、LSym構造体に新しいフィールドonlist（uchar型）が追加されました。

// include/link.h
struct	LSym
{
    // ... 既存のフィールド ...
    uchar	onlist;	// on the textp or datap lists
    // ... 既存のフィールド ...
};

このonlistフラグは、シンボルがtextp（テキストセグメントのシンボルリスト）またはdatap（データセグメントのシンボルリスト）に既に追加されているかどうかを示すために使用されます。シンボルをリストに追加する直前にonlistフラグをチェックし、既にセットされている場合はsysfatalを呼び出して致命的なエラーとして報告します。

このチェックは、src/cmd/ld/data.c, src/cmd/ld/ldelf.c, src/cmd/ld/ldmacho.c, src/cmd/ld/ldpe.c, src/liblink/objfile.cなど、シンボルがリンクリストに追加される可能性のある複数の箇所に導入されています。

// 例: src/cmd/ld/data.c
if(s->onlist)
    sysfatal("symbol %s listed multiple times", s->name);
s->onlist = 1;

この整合性チェックは、ユニットテストの代わりとして機能し、将来的に同様の「シンボルの二重使用」バグが発生した場合に、より直接的に問題を検出できるようにします。

ハッシュ衝突の数学的分析

コミットメッセージの「History」セクションでは、ハッシュ衝突の数学的な分析が提供されています。linklookupで使用されるハッシュ関数は、シンボル名とバージョンvに基づいて計算され、v*3^n（nは名前の長さ）がハッシュ値に加算されるという特性を持っていました。

この特性により、衝突は周期的に発生します。バージョンxとyが衝突するのは、差分d = y-xがd*3^n ≡ 0 (mod 2^24 mod 100003)を満たす場合です。このハッシュ関数は、ランダムなハッシュ関数よりも衝突率が低いという「最良のケース」に近い挙動を示していました。

しかし、最も一般的なシンボルである.dup（名前の長さn=4）の場合、衝突周期は最大で100004番目のシンボルで最初の衝突が発生します。これは、多くの重複シンボルを持つプログラムでは、この周期を超えて衝突が発生し、問題が顕在化する可能性があることを意味します。

この分析は、ハッシュ関数の設計と、それが特定の入力パターン（.dupシンボルの大量生成）と組み合わさったときにどのように振る舞うかを理解する上で重要です。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

1. include/link.h:

   • LSym構造体にonlistフィールド（uchar型）が追加されました。これは、シンボルがリンカの内部リスト（textpやdatap）に既に追加されているかを追跡するためのフラグです。

2. src/liblink/sym.c:

   • _lookup関数（linklookupの実体）において、ハッシュテーブルからシンボルを検索する際の比較ロジックが修正されました。これまではシンボル名のみを比較していましたが、新たにシンボルバージョン（s->version == v）も比較するようになりました。

3. src/liblink/objfile.c:

   • readsym関数内で、重複シンボルを処理するために.dupシンボルを生成する際に、linklookupの代わりにlinknewsymが直接呼び出されるようになりました。これにより、.dupシンボルがハッシュテーブルに挿入されることを回避し、ルックアップ時のハッシュ衝突の可能性を排除しています。
   • また、readsym関数内で、dup == nilの場合（つまり、新しいシンボルが追加される場合）に、onlistフラグをチェックしてシンボルの二重追加を検出するロジックが追加されました。
   • linkwriteobj関数内でも、dataおよびtextリストにシンボルを追加する際にonlistフラグのチェックが追加されました。

4. src/cmd/ld/data.c, src/cmd/ld/ldelf.c, src/cmd/ld/ldmacho.c, src/cmd/ld/ldpe.c:

   • これらのファイルは、リンカの様々な入力処理（ELF、Mach-O、PE形式のオブジェクトファイルの読み込みなど）を担当しており、シンボルをリンカの内部リスト（textpやdatap）に追加する箇所で、onlistフラグのチェックと設定が追加されました。これにより、シンボルがこれらのリストに複数回追加されることを防ぎ、整合性を保つようになります。

5. src/cmd/ld/go.c:

   • deadcode関数内で、textpリストからシンボルを削除し、新しいリストに再構築する際に、コメントが追加されました。これは直接的なバグ修正ではありませんが、リスト操作の意図を明確にしています。

コアとなるコードの解説

src/liblink/sym.c の _lookup 関数 (変更点)

// 変更前:
// for(s = ctxt->hash[h]; s != nil; s = s->hash)
//     if(strcmp(s->name, symb) == 0)
//         return s;

// 変更後:
for(s = ctxt->hash[h]; s != nil; s = s->hash)
    if(s->version == v && strcmp(s->name, symb) == 0)
        return s;

この変更は、ハッシュテーブルのルックアップにおける最も重要な修正です。以前は、ハッシュ値が衝突した場合に、同じハッシュバケット内のシンボルを名前だけで比較していました。しかし、リンカはシンボル名だけでなくバージョン番号も区別する必要があるため、s->version == vという条件が追加されました。これにより、名前が同じでもバージョンが異なるシンボルが誤って一致と判断されることがなくなり、正確なシンボル解決が可能になります。

src/liblink/objfile.c の readsym 関数 (変更点)

// 変更前:
// s = linklookup(ctxt, ".dup", ndup++); // scratch

// 変更後:
s = linknewsym(ctxt, ".dup", ndup++); // scratch

この変更は、.dupシンボルの生成方法を変更しています。linklookupは既存のシンボルを検索し、見つからなければ新しいシンボルを作成する関数です。しかし、.dupシンボルは常に新しいダミーシンボルとして扱われるべきであり、既存のシンボルと衝突する可能性を考慮する必要がありません。linknewsymを直接呼び出すことで、ハッシュテーブルの検索プロセスを完全にスキップし、.dupシンボルがハッシュ衝突を引き起こす可能性を排除しています。これは性能面でも有利であり、リンカの内部的な整合性を高めます。

LSym 構造体への onlist フィールド追加とチェック

// include/link.h
struct	LSym
{
    // ...
    uchar	onlist;	// on the textp or datap lists
    // ...
};

// 例: src/cmd/ld/data.c, src/cmd/ld/ldelf.c, src/liblink/objfile.c など
// シンボルをリストに追加する直前
if(s->onlist)
    sysfatal("symbol %s listed multiple times", s->name);
s->onlist = 1;

onlistフィールドの追加と、シンボルをリンクリストに追加する際のこのフラグのチェックは、リンカの堅牢性を大幅に向上させます。このフラグは、シンボルが既にtextp（テキストシンボルリスト）またはdatap（データシンボルリスト）のいずれかに含まれているかどうかを示します。もしシンボルが既にリストに存在しているにもかかわらず、再度追加しようとした場合、sysfatalが呼び出され、リンカは致命的なエラーとして終了します。

このメカニズムは、ハッシュ衝突によってシンボルが誤って複数回処理され、結果としてリンクリストが破損するような状況を早期に検出するために導入されました。これは、ユニットテストがない状況での「二重使用」バグに対する強力な防御策となります。

これらの変更は、リンカのシンボル管理の正確性を高め、特に大量の重複シンボルが存在するようなエッジケースでの安定性を確保するために不可欠でした。

関連リンク

• Go Issue #7749: https://github.com/golang/go/issues/7749
• 元の性能改善コミット (CL 4383047): https://golang.org/cl/4383047
• ハッシュ衝突周期の計算例 (Go Playground): http://play.golang.org/p/TScD41c_hA
• このコミットのGo Code Review (CL 87910047): https://golang.org/cl/87910047

参考にした情報源リンク

• Go言語のリンカに関する一般的な情報:
  • Go linker internals (Goソースコード内のリンカのREADME)
  • Go linker design (Go 1.2 リリースノートのリンカに関する記述)
• ハッシュテーブルとハッシュ衝突に関する一般的な情報:
  • Hash table - Wikipedia
  • Hash collision - Wikipedia
• C言語のリンカに関する一般的な情報:
  • Linker (computing) - Wikipedia
• Go言語のツールチェインに関する情報:
  • Go toolchain - Wikipedia
• sysfatalに関する情報:
  • Go言語のソースコード内でsysfatalの定義や使用箇所を検索することで、その役割を理解できます。 (例: grep -r sysfatal go/src/cmd/)
• Go言語のCL (Change List) について:
  • Go Code Review Comments
  • Gerrit Code Review (Goプロジェクトがコードレビューに利用しているシステム)
• Go言語のバージョン付きシンボルに関する情報:
  • Go言語自体は通常バージョン付きシンボルを使用しませんが、Cgoを介してCライブラリをリンクする際に、リンカがCのバージョン付きシンボルを内部的に扱うことがあります。この点については、C言語のリンカの挙動やABIに関するドキュメントを参照すると理解が深まります。 (例: ELF Symbol Versioning)
• Go言語のリンカの歴史と進化に関する情報:
  • Goの公式ブログや設計ドキュメント、過去のコミット履歴などを追うことで、リンカの設計思想や変更の経緯を深く理解できます。 (例: Go Blog) (例: Go Design Documents) (例: Go source code history)