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

このコミットは、Go言語の初期ランタイムにおける文字列ハッシュ関数のバグ修正に関するものです。具体的には、空文字列（またはnilポインタの文字列）がハッシュ関数に渡された際に発生する障害を修正し、これによりマップのキーとして空文字列が正しく扱われるようにします。

コミット

commit e956429166632c68785a17be44b649ae6205bfb0
Author: Ken Thompson <ken@golang.org>
Date:   Wed Dec 10 13:28:46 2008 -0800

    string hash function faults w empty string
    fixes maps[""]

    R=r
    OCL=20909
    CL=20911

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

https://github.com/golang/go/commit/e956429166632c68785a17be44b649ae6205bfb0

元コミット内容

string hash function faults w empty string
fixes maps[""]

R=r
OCL=20909
CL=20911

変更の背景

Go言語のマップ（map）は、キーと値のペアを格納するためのデータ構造です。マップが効率的に動作するためには、キーのハッシュ値を計算するハッシュ関数が不可欠です。このハッシュ関数は、キーを一意の数値に変換し、その数値を使って内部のデータ構造（通常はハッシュテーブル）内の適切な位置に値を格納・検索します。

このコミットが行われた2008年当時、Go言語はまだ開発の初期段階にありました。src/runtime/runtime.c に実装されていた文字列ハッシュ関数 stringhash に、特定の条件下でバグが存在していました。具体的には、空文字列がハッシュ関数の入力として渡された際に、関数が正しく動作せず、障害（fault）を引き起こす可能性がありました。

この問題は、特にマップのキーとして空文字列 "" を使用しようとした場合に顕在化しました。マップはキーのハッシュ値に基づいて動作するため、ハッシュ関数が空文字列を適切に処理できないと、maps[""] のような操作が失敗したり、予期せぬ動作を引き起こしたりする原因となります。このコミットは、この根本的なハッシュ関数の問題を修正し、Goプログラムが空文字列をマップのキーとして安全かつ正確に使用できるようにすることを目的としています。

前提知識の解説

1. Go言語の初期ランタイム (src/runtime/runtime.c)

Go言語は、その設計思想として「シンプルさ」と「効率性」を重視しています。初期のGo言語のランタイムは、C言語で記述された部分が多く存在しました。src/runtime/runtime.c は、ガベージコレクション、スケジューリング、メモリ管理、そして今回問題となっているハッシュ関数など、Goプログラムの実行を支える低レベルな機能の多くを実装していました。Go言語の進化とともに、これらのC言語で書かれた部分は徐々にGo言語自身で書き直されていきましたが、このコミットの時点ではC言語が主要な実装言語でした。

2. ハッシュ関数 (stringhash, memhash)

• ハッシュ関数: 任意の長さのデータを固定長のデータ（ハッシュ値）に変換する関数です。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値の衝突（異なる入力が同じハッシュ値になること）を最小限に抑える必要があります。
• stringhash: このコミットで修正対象となっている関数で、Goの文字列型 (string) のハッシュ値を計算するために使用されます。
• memhash: 一般的なメモリブロックのハッシュ値を計算する低レベルな関数です。stringhash は内部的に memhash を呼び出して、文字列のバイト列のハッシュ値を計算します。

3. Goにおける文字列の表現と nil

Go言語の string 型は、内部的には読み取り専用のバイト列へのポインタと、その長さ（バイト数）のペアとして表現されます。Goの文字列は不変（immutable）であり、値型として扱われます。

重要な点として、Goの string 型のゼロ値は空文字列 "" であり、nil ではありません。しかし、このコミットのコード string *a は「文字列へのポインタ」を意味します。C言語の文脈では、ポインタが nil であることは、それが有効なメモリを指していない状態を示します。したがって、*a == nil という条件は、a が指す先の string 構造体自体が nil である、つまり有効な文字列データが存在しない状態をチェックしていると考えられます。これは、Goのユーザーが直接 nil 文字列を作成することは通常ありませんが、内部的なランタイム処理や、C言語との相互運用において発生しうるエッジケースだった可能性があります。

4. emptystring

emptystring は、Goランタイム内部で定義されている、長さが0の空文字列を表す特別な定数またはグローバル変数です。空文字列のハッシュ値を計算する際には、この emptystring のバイト列と長さを使用するのが適切です。

技術的詳細

コミットの差分を見ると、stringhash 関数に以下の2行が追加されています。

+	if(*a == nil)
+		return memhash(emptystring->len, emptystring->str);

元の stringhash 関数は、引数 string *a が指す文字列の長さ (*a)->len と、その文字列のバイト列 (*a)->str を memhash 関数に渡してハッシュ値を計算していました。

この修正が導入される前は、もし *a が nil ポインタであった場合、(*a)->len や (*a)->str にアクセスしようとすると、nil ポインタのデリファレンスが発生し、プログラムがクラッシュするなどの未定義動作を引き起こす可能性がありました。これは、GoのランタイムがC言語で書かれていたため、C言語のポインタのセマンティクスが直接影響していたためです。

追加された if(*a == nil) のチェックは、この潜在的な nil ポインタデリファレンスの問題を回避します。もし *a が nil であった場合、それは有効な文字列データが存在しないことを意味します。このような場合、Goのセマンティクスでは空文字列として扱われるべきであるため、emptystring の長さとバイト列を使って memhash を呼び出すことで、空文字列のハッシュ値を返します。これにより、マップが空文字列をキーとして正しく処理できるようになります。

この修正は、Goのランタイムが、内部的に nil ポインタの文字列を安全に処理し、それを空文字列のハッシュ値にマッピングすることで、堅牢性を高めるための重要なステップでした。

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

diff --git a/src/runtime/runtime.c b/src/runtime/runtime.c
index 3d0ee7f1e6..c075181a02 100644
--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -583,6 +583,8 @@ static uint64
 stringhash(uint32 s, string *a)
 {
 	USED(s);\n+\tif(*a == nil)\n+\t\treturn memhash(emptystring->len, emptystring->str);\n 	return memhash((*a)->len, (*a)->str);\
 }\n \

コアとなるコードの解説

変更は src/runtime/runtime.c ファイル内の stringhash 関数に集中しています。

static uint64
stringhash(uint32 s, string *a)
{
	USED(s); // s は使用されていないことを示すマクロ（コンパイラの警告抑制など）
	if(*a == nil) // ここが追加された行1: 引数 'a' が指す文字列構造体が nil かどうかをチェック
		return memhash(emptystring->len, emptystring->str); // ここが追加された行2: nil の場合は emptystring のハッシュ値を返す
	return memhash((*a)->len, (*a)->str); // 元々あった行: 通常の文字列のハッシュ値を計算
}

• static uint64 stringhash(uint32 s, string *a):

  • static: この関数が現在のファイル内でのみ可視であることを示します。
  • uint64: 関数が64ビットの符号なし整数（ハッシュ値）を返すことを示します。
  • uint32 s: シード値（ハッシュ計算の初期値）として使用される可能性のある32ビット符号なし整数。このコミットの時点では USED(s) となっており、実際には使用されていないようです。
  • string *a: ハッシュ値を計算したい文字列へのポインタ。Goの string 型はC言語の構造体として定義されており、その構造体へのポインタが渡されます。

• if(*a == nil):

  • この条件文が追加された最も重要な部分です。*a はポインタ a が指す先の string 構造体そのものを意味します。
  • nil はC言語におけるヌルポインタ（NULL）に相当します。このチェックは、string 構造体へのポインタが有効なメモリを指しているか、それともヌルであるかを判断します。
  • もし *a が nil であった場合、それは有効な文字列データが存在しない、あるいは初期化されていない状態を示します。

• return memhash(emptystring->len, emptystring->str);:

  • *a が nil であった場合に実行される行です。
  • emptystring はGoランタイムが内部的に持つ、長さ0の空文字列を表すグローバルな string 構造体です。
  • emptystring->len は空文字列の長さ（0）を、emptystring->str は空文字列のバイト列へのポインタを指します。
  • この行は、nil ポインタの文字列が渡された場合でも、安全に空文字列のハッシュ値を計算して返すようにします。これにより、マップが nil ポインタの文字列をキーとして受け取った際に、空文字列のキーとして扱われるようになり、クラッシュを防ぎます。

この修正により、stringhash 関数は、有効な文字列だけでなく、内部的に nil ポインタとして表現される可能性のある文字列も適切に処理できるようになり、Goのマップがより堅牢に動作するようになりました。

関連リンク

• Go言語の初期の設計に関するドキュメントやメーリングリストのアーカイブは、Goプロジェクトの公式リポジトリやウェブサイトで確認できる場合があります。
• Go言語の map 型に関する公式ドキュメント: https://go.dev/blog/maps (これは現代のGoに関するものですが、基本的な概念は共通です)
• Go言語の string 型に関する公式ドキュメント: https://go.dev/blog/strings (これも現代のGoに関するものですが、基本的な概念は共通です)

参考にした情報源リンク

• GitHub: golang/go commit e956429166632c68785a17be44b649ae6205bfb0: https://github.com/golang/go/commit/e956429166632c68785a17be44b649ae6205bfb0
• Go言語の公式ブログ (マップと文字列に関する記事は、Goの基本的な動作を理解する上で役立ちます): https://go.dev/blog/
• Go言語のソースコード (特に src/runtime ディレクトリ): https://github.com/golang/go/tree/master/src/runtime
• C言語のポインタと NULL の概念に関する一般的な情報源。
• ハッシュ関数に関する一般的な情報源。# [インデックス 1313] ファイルの概要

このコミットは、Go言語の初期ランタイムにおける文字列ハッシュ関数のバグ修正に関するものです。具体的には、空文字列（またはnilポインタの文字列）がハッシュ関数に渡された際に発生する障害を修正し、これによりマップのキーとして空文字列が正しく扱われるようにします。

コミット

commit e956429166632c68785a17be44b649ae6205bfb0
Author: Ken Thompson <ken@golang.org>
Date:   Wed Dec 10 13:28:46 2008 -0800

    string hash function faults w empty string
    fixes maps[""]

    R=r
    OCL=20909
    CL=20911

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

https://github.com/golang/go/commit/e956429166632c68785a17be44b649ae6205bfb0

元コミット内容

string hash function faults w empty string
fixes maps[""]

R=r
OCL=20909
CL=20911

変更の背景

Go言語のマップ（map）は、キーと値のペアを格納するためのデータ構造です。マップが効率的に動作するためには、キーのハッシュ値を計算するハッシュ関数が不可欠です。このハッシュ関数は、キーを一意の数値に変換し、その数値を使って内部のデータ構造（通常はハッシュテーブル）内の適切な位置に値を格納・検索します。

このコミットが行われた2008年当時、Go言語はまだ開発の初期段階にありました。src/runtime/runtime.c に実装されていた文字列ハッシュ関数 stringhash に、特定の条件下でバグが存在していました。具体的には、空文字列がハッシュ関数の入力として渡された際に、関数が正しく動作せず、障害（fault）を引き起こす可能性がありました。

この問題は、特にマップのキーとして空文字列 "" を使用しようとした場合に顕在化しました。マップはキーのハッシュ値に基づいて動作するため、ハッシュ関数が空文字列を適切に処理できないと、maps[""] のような操作が失敗したり、予期せぬ動作を引き起こしたりする原因となります。このコミットは、この根本的なハッシュ関数の問題を修正し、Goプログラムが空文字列をマップのキーとして安全かつ正確に使用できるようにすることを目的としています。

前提知識の解説

1. Go言語の初期ランタイム (src/runtime/runtime.c)

Go言語は、その設計思想として「シンプルさ」と「効率性」を重視しています。初期のGo言語のランタイムは、C言語で記述された部分が多く存在しました。src/runtime/runtime.c は、ガベージコレクション、スケジューリング、メモリ管理、そして今回問題となっているハッシュ関数など、Goプログラムの実行を支える低レベルな機能の多くを実装していました。Go言語の進化とともに、これらのC言語で書かれた部分は徐々にGo言語自身で書き直されていきましたが、このコミットの時点ではC言語が主要な実装言語でした。

2. ハッシュ関数 (stringhash, memhash)

• ハッシュ関数: 任意の長さのデータを固定長のデータ（ハッシュ値）に変換する関数です。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値の衝突（異なる入力が同じハッシュ値になること）を最小限に抑える必要があります。
• stringhash: このコミットで修正対象となっている関数で、Goの文字列型 (string) のハッシュ値を計算するために使用されます。
• memhash: 一般的なメモリブロックのハッシュ値を計算する低レベルな関数です。stringhash は内部的に memhash を呼び出して、文字列のバイト列のハッシュ値を計算します。

3. Goにおける文字列の表現と nil

Go言語の string 型は、内部的には読み取り専用のバイト列へのポインタと、その長さ（バイト数）のペアとして表現されます。Goの文字列は不変（immutable）であり、値型として扱われます。

重要な点として、Goの string 型のゼロ値は空文字列 "" であり、nil ではありません。しかし、このコミットのコード string *a は「文字列へのポインタ」を意味します。C言語の文脈では、ポインタが nil であることは、それが有効なメモリを指していない状態を示します。したがって、*a == nil という条件は、a が指す先の string 構造体自体が nil である、つまり有効な文字列データが存在しない状態をチェックしていると考えられます。これは、Goのユーザーが直接 nil 文字列を作成することは通常ありませんが、内部的なランタイム処理や、C言語との相互運用において発生しうるエッジケースだった可能性があります。

4. emptystring

emptystring は、Goランタイム内部で定義されている、長さが0の空文字列を表す特別な定数またはグローバル変数です。空文字列のハッシュ値を計算する際には、この emptystring のバイト列と長さを使用するのが適切です。

技術的詳細

コミットの差分を見ると、stringhash 関数に以下の2行が追加されています。

+	if(*a == nil)
+		return memhash(emptystring->len, emptystring->str);

元の stringhash 関数は、引数 string *a が指す文字列の長さ (*a)->len と、その文字列のバイト列 (*a)->str を memhash 関数に渡してハッシュ値を計算していました。

この修正が導入される前は、もし *a が nil ポインタであった場合、(*a)->len や (*a)->str にアクセスしようとすると、nil ポインタのデリファレンスが発生し、プログラムがクラッシュするなどの未定義動作を引き起こす可能性がありました。これは、GoのランタイムがC言語で書かれていたため、C言語のポインタのセマンティクスが直接影響していたためです。

追加された if(*a == nil) のチェックは、この潜在的な nil ポインタデリファレンスの問題を回避します。もし *a が nil であった場合、それは有効な文字列データが存在しないことを意味します。このような場合、Goのセマンティクスでは空文字列として扱われるべきであるため、emptystring の長さとバイト列を使って memhash を呼び出すことで、空文字列のハッシュ値を返します。これにより、マップが空文字列をキーとして正しく処理できるようになります。

この修正は、Goのランタイムが、内部的に nil ポインタの文字列を安全に処理し、それを空文字列のハッシュ値にマッピングすることで、堅牢性を高めるための重要なステップでした。

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

diff --git a/src/runtime/runtime.c b/src/runtime/runtime.c
index 3d0ee7f1e6..c075181a02 100644
--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -583,6 +583,8 @@ static uint64
 stringhash(uint32 s, string *a)
 {
 	USED(s);\n+\tif(*a == nil)\n+\t\treturn memhash(emptystring->len, emptystring->str);\n 	return memhash((*a)->len, (*a)->str);\
 }\n \

コアとなるコードの解説

変更は src/runtime/runtime.c ファイル内の stringhash 関数に集中しています。

static uint64
stringhash(uint32 s, string *a)
{
	USED(s); // s は使用されていないことを示すマクロ（コンパイラの警告抑制など）
	if(*a == nil) // ここが追加された行1: 引数 'a' が指す文字列構造体が nil かどうかをチェック
		return memhash(emptystring->len, emptystring->str); // ここが追加された行2: nil の場合は emptystring のハッシュ値を返す
	return memhash((*a)->len, (*a)->str); // 元々あった行: 通常の文字列のハッシュ値を計算
}

• static uint64 stringhash(uint32 s, string *a):

  • static: この関数が現在のファイル内でのみ可視であることを示します。
  • uint64: 関数が64ビットの符号なし整数（ハッシュ値）を返すことを示します。
  • uint32 s: シード値（ハッシュ計算の初期値）として使用される可能性のある32ビット符号なし整数。このコミットの時点では USED(s) となっており、実際には使用されていないようです。
  • string *a: ハッシュ値を計算したい文字列へのポインタ。Goの string 型はC言語の構造体として定義されており、その構造体へのポインタが渡されます。

• if(*a == nil):

  • この条件文が追加された最も重要な部分です。*a はポインタ a が指す先の string 構造体そのものを意味します。
  • nil はC言語におけるヌルポインタ（NULL）に相当します。このチェックは、string 構造体へのポインタが有効なメモリを指しているか、それともヌルであるかを判断します。
  • もし *a が nil であった場合、それは有効な文字列データが存在しない、あるいは初期化されていない状態を示します。

• return memhash(emptystring->len, emptystring->str);:

  • *a が nil であった場合に実行される行です。
  • emptystring はGoランタイムが内部的に持つ、長さ0の空文字列を表すグローバルな string 構造体です。
  • emptystring->len は空文字列の長さ（0）を、emptystring->str は空文字列のバイト列へのポインタを指します。
  • この行は、nil ポインタの文字列が渡された場合でも、安全に空文字列のハッシュ値を計算して返すようにします。これにより、マップが nil ポインタの文字列をキーとして受け取った際に、空文字列のキーとして扱われるようになり、クラッシュを防ぎます。

この修正により、stringhash 関数は、有効な文字列だけでなく、内部的に nil ポインタとして表現される可能性のある文字列も適切に処理できるようになり、Goのマップがより堅牢に動作するようになりました。

関連リンク

• Go言語の初期の設計に関するドキュメントやメーリングリストのアーカイブは、Goプロジェクトの公式リポジトリやウェブサイトで確認できる場合があります。
• Go言語の map 型に関する公式ドキュメント: https://go.dev/blog/maps (これは現代のGoに関するものですが、基本的な概念は共通です)
• Go言語の string 型に関する公式ドキュメント: https://go.dev/blog/strings (これも現代のGoに関するものですが、基本的な概念は共通です)

参考にした情報源リンク

• GitHub: golang/go commit e956429166632c68785a17be44b649ae6205bfb0: https://github.com/golang/go/commit/e956429166632c68785a17be44b649ae6205bfb0
• Go言語の公式ブログ (マップと文字列に関する記事は、Goの基本的な動作を理解する上で役立ちます): https://go.dev/blog/
• Go言語のソースコード (特に src/runtime ディレクトリ): https://github.com/golang/go/tree/master/src/runtime
• C言語のポインタと NULL の概念に関する一般的な情報源。
• ハッシュ関数に関する一般的な情報源。