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

このコミットは、Go言語のランタイムにおけるマップ（map）の実装に関するバグ修正です。具体的には、マップが拡張（grow）している最中にイテレータが開始され、かつマップがNaN（Not a Number）をキーとして含んでいる場合に、イテレータが同じNaNキーを複数回返す可能性があるという問題に対処しています。この修正は、NaNキーに対する要素の退避（evacuation）決定を決定論的かつ再現可能にすることで、各NaNキーがイテレータによって一度だけ返されるようにします。

コミット

commit 869368a528cf4a8b154176b34182dbfa4a42f21a
Author: Keith Randall <khr@golang.org>
Date:   Fri Oct 4 13:54:03 2013 -0700

    runtime: fix bug in maps at the intersection of iterators, growing, and NaN keys
    
    If an iterator is started while a map is in the middle of a grow,
    and the map has NaN keys, then those keys might get returned by
    the iterator more than once.  This fix makes the evacuation decision
    deterministic and repeatable for NaN keys so each one gets returned
    only once.
    
    R=golang-dev, r, khr, iant
    CC=golang-dev
    https://golang.org/cl/14367043

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

https://github.com/golang/go/commit/869368a528cf4a8b154176b34182dbfa4a42f21a

元コミット内容

runtime: fix bug in maps at the intersection of iterators, growing, and NaN keys

If an iterator is started while a map is in the middle of a grow,
and the map has NaN keys, then those keys might get returned by
the iterator more than once. This fix makes the evacuation decision
deterministic and repeatable for NaN keys so each one gets returned
only once.

変更の背景

Goのマップは、要素数が一定の閾値を超えると、より大きなバケット配列に拡張（grow）されます。この拡張プロセスは、既存の要素を新しいバケットに「退避（evacuate）」させることで行われます。同時に、Goのマップはイテレータ（for rangeループなど）をサポートしており、マップの要素を順次処理することができます。

このコミットが修正しようとしている問題は、以下の3つの条件が重なった場合に発生していました。

マップが拡張処理の途中である。
マップに対してイテレータが開始されている。
マップのキーとしてNaN（Not a Number）値が使用されている。

NaNは浮動小数点数の一種で、NaN == NaNがfalseとなるという特殊な性質を持っています。これは、ハッシュ計算や等価性比較において問題を引き起こす可能性があります。従来のGoマップの実装では、NaNキーのハッシュ値が非決定論的になることがあり、マップの拡張中にイテレータが動作していると、同じNaNキーが新しいバケットと古いバケットの両方から複数回返される可能性がありました。これは、イテレータがマップの要素を正確に一度だけ返すという期待に反するバグでした。

このバグは、マップの拡張とイテレータの同時実行という複雑なシナリオで発生するため、デバッグが困難な種類の問題です。

前提知識の解説

Go言語のマップ（`map`）

Go言語のマップはハッシュテーブルとして実装されており、キーと値のペアを格納します。内部的には、キーのハッシュ値に基づいて要素がバケットに分散されます。

ハッシュ関数: キーのハッシュ値を計算するために使用されます。Goのマップは、キーの型に応じて適切なハッシュ関数を選択します。
バケット: マップの要素が格納される基本的な単位です。各バケットは複数のキーと値を保持できます。
ロードファクタ（Load Factor）: マップの要素数とバケット数の比率です。この値が一定の閾値を超えると、マップはより大きなバケット配列に拡張されます。
マップの拡張（Grow）: ロードファクタが閾値を超えた場合、Goランタイムはマップのバケット配列を2倍のサイズに拡張します。このプロセスは段階的に行われ、古いバケットから新しいバケットへの要素の移動（退避）が徐々に行われます。この間、マップは古いバケットと新しいバケットの両方を持つ「中間状態」になります。
イテレータ: for rangeループなどを使用してマップの要素を順に処理するメカニズムです。イテレータは、マップの現在の状態をスナップショットとして捉えるわけではなく、マップの変更（特に拡張）と並行して動作する可能性があります。

NaN（Not a Number）

NaNはIEEE 754浮動小数点標準で定義されている特殊な値で、数値演算の結果が未定義または表現不能な場合に生成されます（例: 0.0 / 0.0、sqrt(-1.0)）。

NaNの重要な特性は以下の通りです。

非等価性: どのような値と比較しても（NaN自身と比較しても）、常にfalseを返します。つまり、NaN == NaNはfalseです。
非決定論的なハッシュ: 多くのハッシュ関数では、同じNaN値であっても異なるハッシュ値を生成する可能性があります。これは、NaNのビット表現が複数存在しうるため、またはハッシュ関数がNaNの特殊な性質を考慮していない場合に発生します。

マップの拡張とイテレータの並行処理

Goのマップは、拡張中にイテレータが動作することを許容します。これは、マップの拡張がバックグラウンドで徐々に進行し、その間もマップへのアクセスやイテレーションが可能であることを意味します。イテレータは、古いバケットと新しいバケットの両方から要素を読み取ることで、マップの拡張中も一貫したビューを提供しようとします。

しかし、NaNキーの場合、その非等価性と非決定論的なハッシュの性質が、この並行処理を複雑にします。マップの拡張時には、各要素が新しいバケットのどこに移動するかを決定するために、キーのハッシュ値が再計算されます。NaNキーの場合、この再計算されたハッシュ値が以前のハッシュ値と異なったり、同じNaNキーであっても複数回のハッシュ計算で異なる結果になったりする可能性があります。これにより、イテレータが同じNaNキーを複数回「発見」してしまうという問題が発生していました。

技術的詳細

このコミットの核心は、マップの拡張（evacuate関数）とイテレータ（next関数）がNaNキーを扱う方法を調整することにあります。

`evacuate`関数におけるNaNキーの処理

マップの拡張時、evacuate関数は古いバケットから新しいバケットへ要素を移動させます。この際、キーのハッシュ値に基づいて、要素が新しい2つのバケットのどちらに移動するか（newbitが0か1か）が決定されます。

NaNキーの場合、k != k（!eq）が真となります。このとき、従来のハッシュ計算では非決定論的な結果が生じる可能性がありました。修正後のコードでは、イテレータが動作している（h->flags & Iteratorがセットされている）場合に、NaNキーの退避決定を決定論的にするために、キーのtophashの最下位ビット（top & 1）を利用します。

具体的には、以下のロジックが追加されました。

if ((h->flags & Iterator) != 0): イテレータが動作中の場合。
if (!eq): キーがNaNの場合（k != k）。
- NaNキーのハッシュ値は再現性がないため、tophashの最下位ビット（top & 1）を退避決定に利用します。
- if ((top & 1) != 0): tophashの最下位ビットが1の場合、ハッシュ値のnewbitをセットします。
- else: tophashの最下位ビットが0の場合、ハッシュ値のnewbitをクリアします。
- これにより、NaNキーの退避先がtophashの最下位ビットに基づいて決定論的に決まるようになります。
- さらに、次のレベルの拡張のために新しいランダムなtophashを再計算し、NaNキーが将来の拡張で均等に分散されるようにします。

この変更により、NaNキーの退避先がイテレータの動作中に一貫して決定されるようになり、同じNaNキーが複数回退避されることがなくなります。

`next`関数におけるNaNキーの処理

next関数はマップのイテレータの実装です。マップが拡張中の場合、イテレータは古いバケットと新しいバケットの両方を考慮して要素を返します。

修正前のコードでは、NaNキー（!eq）の場合、ハッシュ値が無意味であるため、最初の新しいバケット（bucket >= ((uintptr)1 << (it->B - 1))が偽の場合）で全てのNaNを返すというロジックがありました。これは、イテレータが拡張中のマップを走査する際に、NaNキーが重複して返される原因となっていました。

修正後のコードでは、if (eq)ブロックとelseブロックが明確に分けられました。

if (eq): キーがNaNでない場合（k == k）。
- 通常のハッシュ計算を行い、要素が現在のイテレーションの新しいバケットに属するかどうかを判断します。
else: キーがNaNの場合（k != k）。
- evacuate関数と同様に、tophashの最下位ビット（b->tophash[i] & 1）を使用して、NaNキーが現在のイテレーションの新しいバケットに属するかどうかを決定します。
- if (check_bucket >> (it->B - 1) != (b->tophash[i] & 1))：現在のバケットが、tophashの最下位ビットに基づいてNaNキーが移動すべきバケットと一致しない場合、そのキーはスキップされます。

この変更により、イテレータはNaNキーを、evacuate関数が決定したのと同じ決定論的な方法で処理するようになり、重複してNaNキーが返されることがなくなります。

テストの追加

src/pkg/runtime/map_test.goにTestMapNanGrowIteratorという新しいテストが追加されました。このテストは、マップがNaNキーを含み、拡張中にイテレータが動作するシナリオをシミュレートします。テストは、イテレータが各NaNキーを正確に一度だけ返すことを検証します。

nBucketsとnKeysを定義し、マップが拡張を開始する直前の状態までNaNキーで埋めます。
m[1.0] = 1とdelete(m, 1.0)でマップの拡張をトリガーします。
マップをイテレートし、foundマップを使用して重複する値がないかチェックします。
イテレーションの途中で、delete(m, 1.0)を複数回呼び出すことで、マップの拡張を完了させます。
最終的に、イテレータがnKeys個のユニークな値を全て見つけたことを検証します。

このテストは、修正が正しく機能していることを確認するための重要な追加です。

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

`src/pkg/runtime/export_test.go`

--- a/src/pkg/runtime/export_test.go
+++ b/src/pkg/runtime/export_test.go
@@ -81,3 +81,6 @@ var Int32Hash = int32Hash
 var Int64Hash = int64Hash
 
 func GogoBytes() int32
+
+var hashLoad float64 // declared in hashmap.c
+var HashLoad = &hashLoad

hashLoad変数をテストからアクセスできるようにエクスポートしています。これはmap_test.goでマップの拡張をトリガーする際のロードファクタ計算に使用されます。

`src/pkg/runtime/hashmap.c`

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -288,6 +288,8 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\n \tuintptr i;\n \tbyte *k, *v;\n \tbyte *xk, *yk, *xv, *yv;\n+\tuint8 top;\n+\tbool eq;\n \n \tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n \tnewbit = (uintptr)1 << (h->B - 1);\n@@ -306,13 +308,38 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\n \t\tyv = yk + h->keysize * BUCKETSIZE;\n \t\tdo {\n \t\t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\n-\t\t\t\tif(b->tophash[i] == 0)\n+\t\t\t\ttop = b->tophash[i];\n+\t\t\t\tif(top == 0)\n \t\t\t\t\tcontinue;\n+\n+\t\t\t\t// Compute hash to make our evacuation decision (whether we need\n+\t\t\t\t// to send this key/value to bucket x or bucket y).\n \t\t\t\thash = h->hash0;\n \t\t\t\tt->key->alg->hash(&hash, t->key->size, IK(h, k));\n-\t\t\t\t// NOTE: if key != key, then this hash could be (and probably will be)\n-\t\t\t\t// entirely different from the old hash.  We effectively only update\n-\t\t\t\t// the B'th bit of the hash in this case.\n+\t\t\t\tif((h->flags & Iterator) != 0) {\n+\t\t\t\t\tt->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k));\n+\t\t\t\t\tif(!eq) {\n+\t\t\t\t\t\t// If key != key (NaNs), then the hash could be (and probably\n+\t\t\t\t\t\t// will be) entirely different from the old hash.  Moreover,\n+\t\t\t\t\t\t// it isn't reproducible.  Reproducibility is required in the\n+\t\t\t\t\t\t// presence of iterators, as our evacuation decision must\n+\t\t\t\t\t\t// match whatever decision the iterator made.\n+\t\t\t\t\t\t// Fortunately, we have the freedom to send these keys either\n+\t\t\t\t\t\t// way.  Also, tophash is meaningless for these kinds of keys.\n+\t\t\t\t\t\t// We let the low bit of tophash drive the evacuation decision.\n+\t\t\t\t\t\t// We recompute a new random tophash for the next level so\n+\t\t\t\t\t\t// these keys will get evenly distributed across all buckets\n+\t\t\t\t\t\t// after multiple grows.\n+\t\t\t\t\t\tif((top & 1) != 0)\n+\t\t\t\t\t\t\thash |= newbit;\n+\t\t\t\t\t\telse\n+\t\t\t\t\t\t\thash &= ~newbit;\n+\t\t\t\t\t\ttop = hash >> (8*sizeof(uintptr)-8);\n+\t\t\t\t\t\tif(top == 0)\n+\t\t\t\t\t\t\ttop = 1;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\n \t\t\t\tif((hash & newbit) == 0) {\n \t\t\t\t\tif(xi == BUCKETSIZE) {\n \t\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\n@@ -323,7 +350,7 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\n \t\t\t\t\t\txk = x->data;\n \t\t\t\t\t\txv = xk + h->keysize * BUCKETSIZE;\n \t\t\t\t\t}\n-\t\t\t\t\tx->tophash[xi] = b->tophash[i];\n+\t\t\t\t\tx->tophash[xi] = top;\n \t\t\t\t\tif((h->flags & IndirectKey) != 0) {\n \t\t\t\t\t\t*(byte**)xk = *(byte**)k;               // copy pointer\n \t\t\t\t\t} else {\n@@ -347,7 +374,7 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\n \t\t\t\t\t\tyk = y->data;\n \t\t\t\t\t\tyv = yk + h->keysize * BUCKETSIZE;\n \t\t\t\t\t}\n-\t\t\t\t\ty->tophash[yi] = b->tophash[i];\n+\t\t\t\t\ty->tophash[yi] = top;\n \t\t\t\t\tif((h->flags & IndirectKey) != 0) {\n \t\t\t\t\t\t*(byte**)yk = *(byte**)k;\n \t\t\t\t\t} else {\n@@ -838,18 +865,12 @@ next:\n \t\t\tif(check_bucket >= 0) {\n \t\t\t\t// Special case: iterator was started during a grow and the\n \t\t\t\t// grow is not done yet.  We're working on a bucket whose\n-\t\t\t\t// oldbucket has not been evacuated yet.  So we iterate\n+\t\t\t\t// oldbucket has not been evacuated yet.  So we're iterating\n \t\t\t\t// through the oldbucket, skipping any keys that will go\n \t\t\t\t// to the other new bucket (each oldbucket expands to two\n \t\t\t\t// buckets during a grow).\n \t\t\t\tt->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k));\n-\t\t\t\tif(!eq) {\n-\t\t\t\t\t// Hash is meaningless if k != k (NaNs).  Return all\n-\t\t\t\t\t// NaNs during the first of the two new buckets.\n-\t\t\t\t\tif(bucket >= ((uintptr)1 << (it->B - 1))) {\n-\t\t\t\t\t\tcontinue;\n-\t\t\t\t\t}\n-\t\t\t\t} else {\n+\t\t\t\tif(eq) {\n \t\t\t\t\t// If the item in the oldbucket is not destined for\n \t\t\t\t\t// the current new bucket in the iteration, skip it.\n \t\t\t\t\thash = h->hash0;\n@@ -857,6 +878,14 @@ next:\n \t\t\t\t\tif((hash & (((uintptr)1 << it->B) - 1)) != check_bucket) {\n \t\t\t\t\t\tcontinue;\n \t\t\t\t\t}\n+\t\t\t\t} else {\n+\t\t\t\t\t// Hash isn't repeatable if k != k (NaNs).  We need a\n+\t\t\t\t\t// repeatable and randomish choice of which direction\n+\t\t\t\t\t// to send NaNs during evacuation.  We'll use the low\n+\t\t\t\t\t// bit of tophash to decide which way NaNs go.\n+\t\t\t\t\tif(check_bucket >> (it->B - 1) != (b->tophash[i] & 1)) {\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\t}\n \t\t\t\t}\n \t\t\t}\n \t\t\tif(!evacuated(b)) {\n@@ -1091,7 +1120,10 @@ runtime·mapassign(MapType *t, Hmap *h, byte *ak, byte *av)\n \t\truntime·prints(\"; key=\");\n \t\tt->key->alg->print(t->key->size, ak);\n \t\truntime·prints(\"; val=\");\n-\t\tt->elem->alg->print(t->elem->size, av);\n+\t\tif(av)\n+\t\t\tt->elem->alg->print(t->elem->size, av);\n+\t\telse\n+\t\t\truntime·prints(\"nil\");\n \t\truntime·prints(\"\\n\");\n \t}\n }\n@@ -1330,3 +1362,6 @@ runtime·mapiter2(struct hash_iter *it, ...)\n \t\truntime·prints(\"\\n\");\n \t}\n }\n+\n+// exported value for testing\n+float64 runtime·hashLoad = LOAD;\n```
*   `evacuate`関数に`top`と`eq`変数を追加。
*   `evacuate`関数内で、イテレータが動作中でNaNキーの場合の特殊なハッシュ計算ロジックを追加。`tophash`の最下位ビットに基づいて退避先を決定し、新しい`tophash`を再計算。
*   `x->tophash[xi] = top;` と `y->tophash[yi] = top;` で、更新された`top`値を使用するように変更。
*   `next`関数内で、NaNキーの場合のイテレータの動作を修正。`tophash`の最下位ビットに基づいて、要素をスキップするかどうかを決定。
*   `runtime·mapassign`のデバッグ出力で、`av`が`nil`の場合に"nil"と表示するように修正。
*   `runtime·hashLoad`をテスト用にエクスポート。

### `src/pkg/runtime/map_test.go`

```diff
--- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -371,3 +371,41 @@ func testMapLookups(t *testing.T, m map[string]string) {\n \t\t}\n \t}\n }\n+\n+// Tests whether the iterator returns the right elements when\n+// started in the middle of a grow, when the keys are NaNs.\n+func TestMapNanGrowIterator(t *testing.T) {\n+\tm := make(map[float64]int)\n+\tnan := math.NaN()\n+\tconst nBuckets = 16\n+\t// To fill nBuckets buckets takes LOAD * nBuckets keys.\n+\tnKeys := int(nBuckets * *runtime.HashLoad)\n+\n+\t// Get map to full point with nan keys.\n+\tfor i := 0; i < nKeys; i++ {\n+\t\tm[nan] = i\n+\t}\n+\t// Trigger grow\n+\tm[1.0] = 1\n+\tdelete(m, 1.0)\n+\n+\t// Run iterator\n+\tfound := make(map[int]struct{})\n+\tfor _, v := range m {\n+\t\tif v != -1 {\n+\t\t\tif _, repeat := found[v]; repeat {\n+\t\t\t\tt.Fatalf(\"repeat of value %d\", v)\n+\t\t\t}\n+\t\t\tfound[v] = struct{}{}\n+\t\t}\n+\t\tif len(found) == nKeys/2 {\n+\t\t\t// Halfway through iteration, finish grow.\n+\t\t\tfor i := 0; i < nBuckets; i++ {\n+\t\t\t\tdelete(m, 1.0)\n+\t\t\t}\n+\t\t}\n+\t}\n+\tif len(found) != nKeys {\n+\t\tt.Fatalf(\"missing value\")\n+\t}\n+}\n```
*   `TestMapNanGrowIterator`という新しいテスト関数を追加。このテストは、NaNキーを含むマップが拡張中にイテレータによって正しく処理されることを検証します。

## コアとなるコードの解説

このコミットの主要な変更は、`src/pkg/runtime/hashmap.c`内の`evacuate`関数と`next`関数に集中しています。

### `evacuate`関数における変更

`evacuate`関数は、マップが拡張される際に、古いバケットから新しいバケットへ要素を移動させる役割を担います。
変更前は、NaNキーのハッシュ値が非決定論的であるため、イテレータが動作している最中にNaNキーがどの新しいバケットに移動するかを正確に追跡することが困難でした。

追加されたコードブロックは、この問題を解決します。
```c
				if((h->flags & Iterator) != 0) {
					t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k));
					if(!eq) {
						// If key != key (NaNs), then the hash could be (and probably
						// will be) entirely different from the old hash.  Moreover,
						// it isn't reproducible.  Reproducibility is required in the
						// presence of iterators, as our evacuation decision must
						// match whatever decision the iterator made.
						// Fortunately, we have the freedom to send these keys either
						// way.  Also, tophash is meaningless for these kinds of keys.
						// We let the low bit of tophash drive the evacuation decision.
						// We recompute a new random tophash for the next level so
						// these keys will get evenly distributed across all buckets
						// after multiple grows.
						if((top & 1) != 0)
							hash |= newbit;
						else
							hash &= ~newbit;
						top = hash >> (8*sizeof(uintptr)-8);
						if(top == 0)
							top = 1;
					}
				}

このコードは、以下の条件が満たされた場合に実行されます。

h->flags & Iterator：マップにイテレータがアクティブである。
!eq：現在のキーがNaNである（k != kが真）。

NaNキーのハッシュ値は再現性がないため、要素を新しいバケットのどちらに移動させるか（newbitが0か1か）を決定するために、キーのtophashの最下位ビット（top & 1）を利用します。これにより、NaNキーの退避先が決定論的に決まるようになります。また、top（tophash）を再計算することで、将来のマップ拡張時にNaNキーがバケット全体に均等に分散されるようにしています。この新しいtop値は、その後のx->tophash[xi] = top;やy->tophash[yi] = top;で新しいバケットに書き込まれます。

`next`関数における変更

next関数は、マップのイテレータが次の要素を取得する際に呼び出されます。マップが拡張中の場合、イテレータは古いバケットと新しいバケットの両方を走査する必要があります。

変更前は、NaNキーの場合にハッシュ値が無意味であるため、特定の条件でNaNキーをスキップするロジックがありましたが、これが重複の原因となっていました。

変更後のコードは、NaNキーの処理をif (eq)（キーがNaNでない場合）とelse（キーがNaNの場合）で明確に分離しています。

				} else {
					// Hash isn't repeatable if k != k (NaNs).  We need a
					// repeatable and randomish choice of which direction
					// to send NaNs during evacuation.  We'll use the low
					// bit of tophash to decide which way NaNs go.
					if(check_bucket >> (it->B - 1) != (b->tophash[i] & 1)) {
						continue;
					}
				}

このelseブロックは、現在のキーがNaNである場合に実行されます。ここでは、evacuate関数で行われた決定論的な退避ロジックと一致するように、tophashの最下位ビット（b->tophash[i] & 1）を使用して、現在のNaNキーがイテレータが現在走査している新しいバケットに属するかどうかを判断します。もし一致しない場合、そのNaNキーはスキップされ、重複して返されることを防ぎます。

これらの変更により、マップの拡張中にNaNキーを含むマップをイテレートしても、各NaNキーが正確に一度だけ返されることが保証されます。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコードリポジトリ
IEEE 754 浮動小数点数標準に関する技術文書
Go言語のマップ実装に関する技術ブログや解説記事
Goのマップの内部構造に関するプレゼンテーションや論文

comemo