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

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

コミット

commit bca01cd0bfdb9bfda3f076697bda4fae27d4e768
Author: Russ Cox <rsc@golang.org>
Date:   Sun Jun 24 19:47:50 2012 -0400

    runtime: detect hash map collision problems
    
    This can only happen if the hash function we're using is getting
    far more than it's fair share of collisions, but that has happened
    to us repeatedly as we've expanded the allowed use cases for
    hash tables (issue 1544, issue 2609, issue 2630, issue 2883, issue 3695).
    Maybe this will help the next time we try something new.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/6306083

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

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

元コミット内容

このコミットは、Goランタイムにおけるハッシュマップの衝突問題を検出するための変更を導入しています。具体的には、ハッシュ関数が過剰な衝突を引き起こしている場合に、それを検知してランタイムパニックを発生させることで、問題の早期発見とデバッグを支援することを目的としています。

変更の背景

Go言語のハッシュマップ（map型）は、内部的にハッシュ関数を使用してキーをバケットにマッピングします。理想的なハッシュ関数は、異なるキーに対して均等にハッシュ値を分散させ、衝突（異なるキーが同じハッシュ値を持つこと）を最小限に抑えます。しかし、現実にはハッシュ衝突は避けられず、特に悪意のある入力や特定のデータパターンによって、ハッシュ衝突が頻繁に発生することがあります。

過去にGoのハッシュマップでは、以下のような複数のIssueでハッシュ衝突に起因するパフォーマンス問題やサービス拒否（DoS）攻撃の脆弱性が報告されていました。

  • Issue 1544: mapのキーとして構造体を使用した場合のハッシュ衝突に関する問題。
  • Issue 2609: ハッシュ衝突が原因でmapのパフォーマンスが著しく低下する問題。
  • Issue 2630: 同上。
  • Issue 2883: 同上。
  • Issue 3695: 同上。

これらの問題は、ハッシュ関数が特定の入力に対して「公平な」衝突分散を提供できていないことを示唆していました。ハッシュテーブルの利用が拡大するにつれて、このような問題が繰り返し発生する可能性があったため、将来的な同様の問題を未然に防ぐ、あるいは早期に発見するためのメカニズムが必要とされていました。

このコミットは、ハッシュ衝突が過剰に発生し、ハッシュマップの内部処理が無限ループに陥るような状況を検出するための防御策として導入されました。これにより、ハッシュ関数の問題や、ハッシュマップの利用方法に潜在する問題を早期に特定し、デバッグを容易にすることが期待されます。

前提知識の解説

ハッシュテーブル（ハッシュマップ）

ハッシュテーブルは、キーと値のペアを格納するためのデータ構造です。キーをハッシュ関数に通して得られるハッシュ値を使って、値を格納するメモリ上の位置（バケット）を決定します。これにより、キーを使って高速に値の検索、挿入、削除を行うことができます。

ハッシュ衝突

異なるキーが同じハッシュ値を持つことをハッシュ衝突と呼びます。ハッシュ衝突が発生した場合、ハッシュテーブルは衝突解決メカニズム（例：チェイニング、オープンアドレス法）を使用して、同じバケットに複数の要素を格納します。

オープンアドレス法

オープンアドレス法は、ハッシュ衝突が発生した際に、別の空いているバケットを探して要素を格納する衝突解決メカニズムの一つです。線形プロービング、二次プロービング、ダブルハッシングなどの方法があります。このコミットで変更されているhash_insert_internal関数は、衝突が発生した場合にハッシュ値をインクリメントして次のバケットを探す、線形プロービングに似た動作をしています。

ランタイムパニック (runtime·throw)

Go言語において、runtime·throwは回復不可能なエラーが発生した場合にGoランタイムが呼び出す関数です。これはプログラムの実行を即座に停止させ、スタックトレースを出力します。このコミットでは、ハッシュ衝突が過剰に発生した場合にこの関数を呼び出すことで、問題の発生を開発者に知らせるようにしています。

技術的詳細

このコミットは、Goランタイムのsrc/pkg/runtime/hashmap.cファイル内のhash_insert_internal関数に変更を加えています。この関数は、ハッシュマップに新しい要素を挿入する際の内部ロジックを処理します。

変更の核心は、ハッシュ衝突が発生した際の挙動にあります。既存のコードでは、衝突が発生した場合にhash値をインクリメントして次のバケットを探していました。しかし、この処理が無限に続く可能性がある、つまりハッシュ衝突が極端に多く発生し、適切な挿入位置が見つからない場合に、ループが終了しない可能性がありました。

新しいコードでは、衝突が発生しhash値をインクリメントする際に、hash & HASH_MASKがHASH_SUBHASHと等しくなるかをチェックしています。

  • HASH_MASKは、ハッシュ値の特定のビットマスクであり、ハッシュテーブルのバケット数を決定する際に使用される可能性があります。
  • HASH_SUBHASHは、ハッシュ値の特定のパターンを示す定数であると考えられます。

この条件が真になった場合、つまりハッシュ値が特定の閾値を超えてインクリメントされ続けた場合、それはハッシュ衝突が異常に多く発生していることを示唆します。このような状況は、ハッシュ関数が適切に機能していないか、またはハッシュテーブルの構造に問題があることを意味します。

この異常な状態を検出した場合、runtime·throw("runtime: map hash collision overflow")を呼び出してランタイムパニックを発生させます。これにより、開発者はハッシュマップの異常な動作を即座に認識し、デバッグを開始することができます。

また、元のコードにあったassert (e_hash != hash || (flags & HASH_REHASH) == 0);というアサート文が、if (e_hash == hash)ブロック内に移動し、assert ((flags & HASH_REHASH) == 0);に変更されています。これは、HASH_REHASHフラグが設定されている場合は、ハッシュ値が衝突してもhashを調整しないという前提をより明確にしています。HASH_REHASHは、ハッシュテーブルのリハッシュ（サイズ変更）中に使用されるフラグであり、このフェーズでは衝突解決のロジックが異なる場合があります。

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

src/pkg/runtime/hashmap.cファイルのhash_insert_internal関数内の変更です。

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -416,8 +416,12 @@ hash_insert_internal (MapType *t, struct hash_subtable **pst, int32 flags, hash_
 					*pres = ins_e->data;
 					return (1);
 				}
-				assert (e_hash != hash || (flags & HASH_REHASH) == 0);
-				hash += (e_hash == hash);	   /* adjust hash if it collides */
+				if (e_hash == hash) {	   /* adjust hash if it collides */
+					assert ((flags & HASH_REHASH) == 0);
+					hash++;
+					if ((hash & HASH_MASK) == HASH_SUBHASH)
+						runtime·throw("runtime: map hash collision overflow");
+				}
 				ins_e = HASH_OFFSET (ins_e, elemsize);
 				ins_i++;
 				if (e_hash <= hash) {	       /* set e to insertion point */

コアとなるコードの解説

変更されたコードブロックは、ハッシュマップへの要素挿入時にハッシュ衝突が発生した場合の処理を制御しています。

  1. if (e_hash == hash):

    • これは、現在調べたエントリ（e_hash）のハッシュ値が、挿入しようとしている要素の現在のハッシュ値（hash）と一致するかどうかをチェックしています。一致する場合、ハッシュ衝突が発生しています。

  2. assert ((flags & HASH_REHASH) == 0);:

    • ハッシュ衝突が発生した場合、HASH_REHASHフラグが設定されていないことをアサートしています。これは、リハッシュ操作中ではないことを確認するためのものです。リハッシュ中は、衝突解決のロジックが異なる場合があるため、このアサートは通常の挿入操作における前提条件を強化しています。

  3. hash++;:

    • ハッシュ衝突が発生した場合、次のバケットを探すためにhash値をインクリメントしています。これはオープンアドレス法の一種である線形プロービングに似た動作です。

  4. if ((hash & HASH_MASK) == HASH_SUBHASH):

    • これがこのコミットの主要な変更点です。hash値がインクリメントされた後、その値が特定のパターン（HASH_MASKとのビットAND演算結果がHASH_SUBHASHと等しい）に達したかどうかをチェックしています。
    • この条件が真になるということは、ハッシュ衝突が非常に頻繁に発生し、hash値が異常に大きくインクリメントされ続けていることを意味します。これは、ハッシュ関数がうまく機能していないか、またはハッシュテーブルが過剰な衝突に直面している兆候です。

  5. runtime·throw("runtime: map hash collision overflow");:

    • 上記の条件が真になった場合、つまりハッシュ衝突が過剰に発生して「オーバーフロー」状態になったと判断された場合、runtime·throwを呼び出してランタイムパニックを発生させます。これにより、プログラムは異常終了し、開発者はこの問題に気づくことができます。

この変更により、Goのハッシュマップは、ハッシュ衝突が制御不能なレベルに達した場合に、無限ループに陥るのではなく、明示的にエラーを報告するようになりました。これにより、ハッシュ関数の品質問題や、ハッシュマップの悪用（DoS攻撃など）に対する耐性が向上し、デバッグが容易になります。

関連リンク

  • Go言語のmap型に関する公式ドキュメントやブログ記事
  • ハッシュテーブル、ハッシュ関数、衝突解決に関する一般的なコンピュータサイエンスの資料

参考にした情報源リンク