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

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

このコミットは、Goランタイムにおけるハッシュマップの拡張（grow）処理に関する変更を元に戻すものです。具体的には、以前のコミット（CL 8852047）で導入された「読み取り時（read）にハッシュマップの拡張作業を行う」という機能が、freebsd-386環境で問題を引き起こしたため、その変更をリバート（revert）しています。これにより、ハッシュマップの拡張作業は再び書き込み時や明示的な拡張時にのみ行われるようになります。

コミット

commit 7f0ee023baf8dca4b328c0a1c1fecfa45b555923
Author: Keith Randall <khr@golang.org>
Date:   Fri May 31 21:44:32 2013 -0700

    runtime: revert of CL 8852047: do hashmap grow work during reads.
    seems to break freebsd-386.
    
    R=golang-dev, dave
    CC=golang-dev
    https://golang.org/cl/9915047

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

https://github.com/golang/go/commit/7f0ee023baf8dca4b328c0a1c1fecfa45b555923

元コミット内容

このコミットは、以前のコミット（CL 8852047）のリバートです。元のCL 8852047は、Goランタイムのハッシュマップ（map型）において、マップの読み取り操作（hash_lookupやイテレータのhash_next）中に、マップの拡張（リサイズ）作業の一部を非同期的に実行する機能を追加しました。

この機能の目的は、マップが一定の閾値を超えて大きくなった際に発生する、コストの高いリサイズ処理（既存の要素を新しい、より大きなバケット構造に再配置する「evacuate」処理）を、単一の書き込み操作で一括して行うのではなく、複数の読み取り操作に分散させることで、レイテンシースパイクを緩和し、全体的なパフォーマンスを向上させることにありました。

具体的には、読み取り時にgrow_work_readという関数が呼び出され、これがアトミック操作とロック機構を用いて、まだ拡張されていない古いバケットの一部を新しいバケットに移動させる処理を行っていました。

変更の背景

元のCL 8852047で導入された「読み取り時のハッシュマップ拡張作業」は、freebsd-386という特定のアーキテクチャ・OSの組み合わせで問題を引き起こしました。コミットメッセージには「seems to break freebsd-386.」と簡潔に記されていますが、これはこの変更がfreebsd-386環境でクラッシュや不正な動作、あるいはデッドロックなどの深刻なバグを引き起こしたことを示唆しています。

ランタイムレベルの並行処理やアトミック操作は、特定のCPUアーキテクチャやメモリモデル、OSのスケジューリング特性に依存して、予期せぬ競合状態やメモリ破壊を引き起こすことがあります。freebsd-386は32ビットシステムであり、メモリのアライメント、ポインタのサイズ、アトミック操作の実装などが他の64ビットシステムや異なるOSと異なる可能性があり、それが問題の原因となったと考えられます。

このような低レベルのバグはデバッグが非常に困難であるため、安定性を最優先し、問題の原因を特定して修正するよりも、問題のある変更を迅速に元に戻す（リバートする）という判断が下されました。

前提知識の解説

Goのハッシュマップ（map）の内部構造と拡張（Grow）

Goのmap型は、内部的にはハッシュテーブルとして実装されています。その主要な特徴は以下の通りです。

  1. バケット（Bucket）: ハッシュマップのデータはバケットと呼ばれる固定サイズの構造体に格納されます。各バケットは複数のキーと値のペアを保持できます。
  2. オーバーフローバケット（Overflow Bucket）: 1つのバケットが満杯になった場合、Goは新しいオーバーフローバケットを割り当て、そこに余分なキーと値のペアを格納します。これにより、衝突（collision）が発生しても効率的にデータを格納できます。
  3. ハッシュ関数: キーはハッシュ関数によってハッシュ値に変換され、そのハッシュ値に基づいてどのバケットに格納されるかが決定されます。
  4. 拡張（Grow/Resizing）: ハッシュマップに要素が追加され、バケットの密度が一定の閾値（ロードファクタ）を超えると、マップは自動的に拡張されます。拡張プロセスでは、より多くのバケットを持つ新しいハッシュテーブルが割り当てられ、既存の要素が古いバケットから新しいバケットに移動されます。この移動プロセスは「evacuation（避難）」と呼ばれます。
  5. 段階的な拡張: Goのマップ拡張は、一度にすべての要素を移動するのではなく、段階的に行われます。これは、マップのリサイズが非常に大きな操作になる可能性があり、アプリケーションの応答性を損なう可能性があるためです。古いバケットと新しいバケットが一時的に共存し、要素は徐々に新しいバケットに移動されます。
  6. oldbucketsとbuckets: 拡張中、ハッシュマップは2つのバケット配列を保持します。oldbucketsは古いバケット配列を指し、bucketsは新しいバケット配列を指します。要素の移動が完了すると、oldbucketsは解放されます。
  7. nevacuate: これは、拡張プロセスにおける進行状況を示すカウンターです。どのバケットまでが新しいバケットに移動されたか（evacuatedされたか）を追跡します。

並行処理とアトミック操作

Goランタイムは、ガベージコレクションやスケジューリングなど、多くの低レベルな処理で並行性を活用しています。ハッシュマップのような共有データ構造を複数のゴルーチンから安全にアクセスするためには、ミューテックス（ロック）やアトミック操作が不可欠です。

  • アトミック操作: 複数のCPUコアから同時にアクセスされても、その操作が不可分（atomic）であることを保証するCPU命令です。例えば、CompareAndSwap (CAS) は、特定のメモリ位置の値が期待する値と一致する場合にのみ、新しい値に更新するという操作をアトミックに行います。これにより、ロックを使用せずに競合状態を避けることができます。
  • メモリバリア/フェンス: CPUの命令再順序付けやキャッシュの一貫性問題を解決するために使用されます。アトミック操作は通常、適切なメモリバリアを含んでいますが、低レベルな並行処理ではこれらを意識する必要があります。

freebsd-386特有の考慮事項

freebsd-386は、FreeBSDオペレーティングシステムがIntel 80386互換の32ビットアーキテクチャ（i386）上で動作する環境を指します。

  • 32ビットアーキテクチャ: ポインタのサイズが32ビット（4バイト）であり、64ビットシステムとは異なるメモリレイアウトやアライメント要件を持つ場合があります。
  • アトミック操作の実装: 32ビットCPUにおけるアトミック操作の実装は、64ビットCPUとは異なる複雑さを持つことがあります。特に、特定のサイズのデータに対するアトミック操作が、特定のCPU命令セットやOSカーネルのサポートに依存する場合があります。
  • メモリモデル: CPUのメモリモデル（命令の実行順序とメモリへの書き込みの可視性に関するルール）は、並行処理の正確性に影響を与えます。異なるアーキテクチャでは、メモリモデルの保証が異なる場合があります。

これらの要因が複合的に作用し、他の環境では問題なく動作するコードがfreebsd-386で問題を引き起こすことがあります。

技術的詳細

このコミットは、主にsrc/pkg/runtime/hashmap.cとsrc/pkg/runtime/hashmap_fast.cの2つのファイルに対する変更を元に戻しています。

src/pkg/runtime/hashmap.cの変更点

  1. EVAC_LOCKの削除:

    • 元のコミットでは、nevacuateフィールドに-1（EVAC_LOCK）を格納することで、ハッシュマップの拡張作業中に特定のバケットがロックされていることを示すメカニズムがありました。このリバートにより、その概念と関連するコードが削除されました。これは、読み取り時に拡張作業を行うための並行制御メカニズムの一部でした。

  2. evacuate関数の変更:

    • 元のコミットでは、evacuate関数の冒頭にif(evacuated(mainb)) return;というチェックがあり、既にevacuateされたバケットはスキップされていました。このリバートにより、このチェックが削除され、evacuate関数は常にバケットの移動を試みるようになります。これは、読み取り時に部分的な拡張を行う際の競合状態を避けるためのものでしたが、リバートによりその必要がなくなりました。
    • バケットのoverflowポインタを操作して、バケットがevacuate済みであることをマークするロジックが変更されました。元のコミットではアトミックなruntime·atomicstorepを使用していましたが、リバート後はよりシンプルなポインタ操作に戻されています。これは、読み取り時の並行拡張がなくなったため、厳密なアトミックなマーク付けが不要になったことを示します。
    • OldIteratorフラグのチェックが追加され、古いイテレータが残っていない場合にのみ、古いオーバーフローバケットを解放するロジックが導入されました。これは、リバートによって拡張のタイミングが変わり、イテレータの整合性を保つための変更です。

  3. grow_work_read関数の削除:

    • これがこのリバートの最も重要な変更点です。grow_work_read関数は、読み取り操作中にハッシュマップの拡張作業（バケットのevacuate）を段階的に行うために導入されていました。この関数は、アトミックなruntime·casp（CompareAndSwapPointer）を使用して排他ロックを取得し、nevacuateカウンターを進めることで、複数のゴルーチンが同時に拡張作業を行うことを調整していました。この関数の削除により、読み取り時の拡張は完全に停止します。

  4. grow_work関数の簡素化:

    • grow_work関数は、主に書き込み操作中に呼び出されるハッシュマップの拡張を進行させる関数です。元のコミットでは、この関数もgrow_work_readを呼び出していましたが、リバートによりその呼び出しが削除され、よりシンプルなロジックに戻されました。

  5. hash_lookupおよびhash_nextからのgrow_work_read呼び出しの削除:

    • hash_lookup（マップのキー検索）とhash_next（マップイテレータの次の要素取得）の関数から、grow_work_read(t, h);の呼び出しが削除されました。これにより、これらの読み取り操作がハッシュマップの拡張作業をトリガーすることはなくなります。
    • evacuated(b)のチェック方法も、アトミックなruntime·atomicloadpを介したチェックから、より直接的なevacuated(b)関数呼び出しに簡素化されました。これは、読み取り時の並行拡張がなくなったため、アトミックな読み込みが不要になったことを反映しています。

src/pkg/runtime/hashmap_fast.cの変更点

このファイルは、特定の型（例えば、stringキーやintキー）に最適化されたハッシュマップの実装を含んでいます。ここでも、hashmap.cと同様に、HASH_LOOKUP1およびHASH_LOOKUP2関数からgrow_work_readの呼び出しが削除され、関連するアトミック操作やevacuatedチェックのロジックが簡素化されています。

変更の全体的な影響

このリバートにより、Goランタイムのハッシュマップは、読み取り操作中に拡張作業を行うことはなくなりました。これにより、freebsd-386で発生していた問題は解消されるはずですが、その代償として、マップが非常に大きくなった際のリサイズ処理が、単一の書き込み操作でより大きなレイテンシースパイクを引き起こす可能性が再び生じます。これは、安定性を優先した結果のトレードオフと言えます。

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

src/pkg/runtime/hashmap.c

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -107,9 +107,6 @@ struct Hmap
 	uintptr nevacuate;    // progress counter for evacuation (buckets less than this have been evacuated)
 };
 
-// token to store in nevacuate field when locking the table to evacuate a bucket.
-#define EVAC_LOCK ((uintptr)-1)
-
 // possible flags
 enum
 {
@@ -288,14 +285,12 @@ hash_init(MapType *t, Hmap *h, uint32 hint)
 
 // Moves entries in oldbuckets[i] to buckets[i] and buckets[i+2^k].
 // We leave the original bucket intact, except for the evacuated marks, so that
-// lookup and iterators can still iterate through the old buckets.
-// Multiple threads must not be evacuating the same bucket at the same time.
+// iterators can still iterate through the old buckets.
 static void
 evacuate(MapType *t, Hmap *h, uintptr oldbucket)
 {
 	Bucket *b;
 	Bucket *nextb;
-\tBucket *mainb;\n
 	Bucket *x, *y;\n
 	Bucket *newx, *newy;\n
 	uintptr xi, yi;\n
@@ -304,154 +299,143 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)
 	uintptr i;\n
 	byte *k, *v;\n
 	byte *xk, *yk, *xv, *yv;\n
+\tbyte *ob;\n
 
-\tmainb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n
+\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n
 	newbit = (uintptr)1 << (h->B - 1);\n
 
-\tif(evacuated(mainb))\t\t// someone else already evacuated this bucket.\n-\t\treturn;\n-\n-\tb = mainb;\n-\tx = (Bucket*)(h->buckets + oldbucket * h->bucketsize);\n-\ty = (Bucket*)(h->buckets + (oldbucket + newbit) * h->bucketsize);\n-\tclearbucket(x);\n-\tclearbucket(y);\n-\txi = 0;\n-\tyi = 0;\n-\txk = x->data;\n-\tyk = y->data;\n-\txv = xk + h->keysize * BUCKETSIZE;\n-\tyv = yk + h->keysize * BUCKETSIZE;\n-\tdo {\n-\t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\n-\t\t\tif(b->tophash[i] == 0)\n-\t\t\t\tcontinue;\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// NOTE: if key != key, then this hash could be (and probably will be)\n-\t\t\t// entirely different from the old hash.  We effectively only update\n-\t\t\t// the B\'th bit of the hash in this case.\n-\t\t\tif((hash & newbit) == 0) {\n-\t\t\t\tif(xi == BUCKETSIZE) {\n-\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\n-\t\t\t\t\tnewx = runtime·mallocgc(h->bucketsize, 0, 1, 0);\n-\t\t\t\t\tclearbucket(newx);\n-\t\t\t\t\tx->overflow = newx;\n-\t\t\t\t\tx = newx;\n-\t\t\t\t\txi = 0;\n-\t\t\t\t\txk = x->data;\n-\t\t\t\t\txv = xk + h->keysize * BUCKETSIZE;\n-\t\t\t\t}\n-\t\t\t\tx->tophash[xi] = b->tophash[i];\n-\t\t\t\tif((h->flags & IndirectKey) != 0) {\n-\t\t\t\t\t*(byte**)xk = *(byte**)k;               // copy pointer\n+\tif(!evacuated(b)) {\n+\t\t// TODO: reuse overflow buckets instead of using new ones, if there\n+\t\t// is no iterator using the old buckets.  (If CanFreeBuckets and !OldIterator.)\n+\n+\t\tx = (Bucket*)(h->buckets + oldbucket * h->bucketsize);\n+\t\ty = (Bucket*)(h->buckets + (oldbucket + newbit) * h->bucketsize);\n+\t\tclearbucket(x);\n+\t\tclearbucket(y);\n+\t\txi = 0;\n+\t\tyi = 0;\n+\t\txk = x->data;\n+\t\tyk = y->data;\n+\t\txv = xk + h->keysize * BUCKETSIZE;\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\t\tcontinue;\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((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+\t\t\t\t\t\tnewx = runtime·mallocgc(h->bucketsize, 0, 1, 0);\n+\t\t\t\t\t\tclearbucket(newx);\n+\t\t\t\t\t\tx->overflow = newx;\n+\t\t\t\t\t\tx = newx;\n+\t\t\t\t\t\txi = 0;\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\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+\t\t\t\t\t\tt->key->alg->copy(t->key->size, xk, k); // copy value\n+\t\t\t\t\t}\n+\t\t\t\t\tif((h->flags & IndirectValue) != 0) {\n+\t\t\t\t\t\t*(byte**)xv = *(byte**)v;\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\tt->elem->alg->copy(t->elem->size, xv, v);\n+\t\t\t\t\t}\n+\t\t\t\t\txi++;\n+\t\t\t\t\txk += h->keysize;\n+\t\t\t\t\txv += h->valuesize;\n \t\t\t\t} else {\n-\t\t\t\t\tt->key->alg->copy(t->key->size, xk, k); // copy value\n+\t\t\t\t\tif(yi == BUCKETSIZE) {\n+\t\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\n+\t\t\t\t\t\tnewy = runtime·mallocgc(h->bucketsize, 0, 1, 0);\n+\t\t\t\t\t\tclearbucket(newy);\n+\t\t\t\t\t\ty->overflow = newy;\n+\t\t\t\t\t\ty = newy;\n+\t\t\t\t\t\tyi = 0;\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\tif((h->flags & IndirectKey) != 0) {\n+\t\t\t\t\t\t*(byte**)yk = *(byte**)k;\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\tt->key->alg->copy(t->key->size, yk, k);\n+\t\t\t\t\t}\n+\t\t\t\t\tif((h->flags & IndirectValue) != 0) {\n+\t\t\t\t\t\t*(byte**)yv = *(byte**)v;\n+\t\t\t\t\t} else {\n+\t\t\t\t\t\tt->elem->alg->copy(t->elem->size, yv, v);\n+\t\t\t\t\t}\n+\t\t\t\t\tyi++;\n+\t\t\t\t\tyk += h->keysize;\n+\t\t\t\t\tyv += h->valuesize;\n \t\t\t\t}\n-\t\t\t\tif((h->flags & IndirectValue) != 0) {\n-\t\t\t\t\t*(byte**)xv = *(byte**)v;\n-\t\t\t\t} else {\n-\t\t\t\t\tt->elem->alg->copy(t->elem->size, xv, v);\n+\t\t\t}\n+\n+\t\t\t// mark as evacuated so we don\'t do it again.\n+\t\t\t// this also tells any iterators that this data isn\'t golden anymore.\n+\t\t\tnextb = b->overflow;\n+\t\t\tb->overflow = (Bucket*)((uintptr)nextb + 1);\n+\n+\t\t\tb = nextb;\n+\t\t} while(b != nil);\n+\n+\t\t// Free old overflow buckets as much as we can.\n+\t\tif((h->flags & OldIterator) == 0) {\n+\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n+\t\t\tif((h->flags & CanFreeBucket) != 0) {\n+\t\t\t\twhile((nextb = overflowptr(b)) != nil) {\n+\t\t\t\t\tb->overflow = nextb->overflow;\n+\t\t\t\t\truntime·free(nextb);\n \t\t\t\t}\n-\t\t\t\txi++;\n-\t\t\t\txk += h->keysize;\n-\t\t\t\txv += h->valuesize;\n \t\t\t} else {\n-\t\t\t\tif(yi == BUCKETSIZE) {\n-\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\n-\t\t\t\t\tnewy = runtime·mallocgc(h->bucketsize, 0, 1, 0);\n-\t\t\t\t\tclearbucket(newy);\n-\t\t\t\t\ty->overflow = newy;\n-\t\t\t\t\ty = newy;\n-\t\t\t\t\tyi = 0;\n-\t\t\t\t\tyk = y->data;\n-\t\t\t\t\tyv = yk + h->keysize * BUCKETSIZE;\n-\t\t\t\t}\n-\t\t\t\ty->tophash[yi] = b->tophash[i];\n-\t\t\t\tif((h->flags & IndirectKey) != 0) {\n-\t\t\t\t\t*(byte**)yk = *(byte**)k;\n-\t\t\t\t} else {\n-\t\t\t\t\tt->key->alg->copy(t->key->size, yk, k);\n-\t\t\t\t}\n-\t\t\t\tif((h->flags & IndirectValue) != 0) {\n-\t\t\t\t\t*(byte**)yv = *(byte**)v;\n-\t\t\t\t} else {\n-\t\t\t\t\tt->elem->alg->copy(t->elem->size, yv, v);\n+\t\t\t\t// can\'t explicitly free overflow buckets, but at least\n+\t\t\t\t// we can unlink them.\n+\t\t\t\tb->overflow = (Bucket*)1;\n \t\t\t}\n-\t\t\t\tyi++;\n-\t\t\t\tyk += h->keysize;\n-\t\t\t\tyv += h->valuesize;\n \t\t\t}\n \t\t}\n-\t\tb = b->overflow;\n-\t} while(b != nil);\n-\n-\t// Mark main bucket as evacuated.  This write commits the\n-\t// bucket evacuation (readers can start using the new buckets).\n-\tb = mainb->overflow;\n-\truntime·atomicstorep(&mainb->overflow, (Bucket*)((uintptr)b + 1));\n-\n-\t// Mark overflow buckets for any iterators.\n-\t// These writes don\'t need to reach anyone until the next hashtable\n-\t// modification, so they don\'t need to be synchronized.\n-\twhile(b != nil) {\n-\t\tnextb = b->overflow;\n-\t\tb->overflow = (Bucket*)((uintptr)nextb + 1);\n-\t\tb = nextb;\n \t}\n \n+\t// advance evacuation mark\n+\tif(oldbucket == h->nevacuate) {\n+\t\th->nevacuate = oldbucket + 1;\n+\t\tif(oldbucket + 1 == newbit) { // newbit == # of oldbuckets\n+\t\t\t// free main bucket array\n+\t\t\tif((h->flags & (OldIterator | CanFreeBucket)) == CanFreeBucket) {\n+\t\t\t\tob = h->oldbuckets;\n+\t\t\t\th->oldbuckets = nil;\n+\t\t\t\truntime·free(ob);\n+\t\t\t} else {\n+\t\t\t\th->oldbuckets = nil;\n+\t\t\t}\n+\t\t}\n+\t}\n \tif(docheck)\n \t\tcheck(t, h);\n }\n \n-// Ensure that bucket has been evacuated from oldbuckets so that we can modify it.\n-// Not multithreaded safe - you must not call this from anywhere except hash table\n-// modifications (where we\'re guaranteed external synchronization).\n static void\n grow_work(MapType *t, Hmap *h, uintptr bucket)\n {\n \tuintptr noldbuckets;\n-\tintptr n;\n \n-\t// evac the bucket we\'re going to need\n \tnoldbuckets = (uintptr)1 << (h->B - 1);\n-\tevacuate(t, h, bucket & (noldbuckets - 1));\n-\t// evac another bucket to make progress\n-\tn = h->nevacuate;\n-\tevacuate(t, h, n);\n-\t// record what we\'ve done\n-\th->nevacuate = n + 1;\n-\tif(n + 1 == noldbuckets)\n-\t\th->oldbuckets = nil;\n-}\n-\n-// Do some work for growing the table.\n-// Multithreaded-safe.\n-static void\n-grow_work_read(MapType *t, Hmap *h) {\n-\tuintptr noldbuckets;\n-\tintptr n;\n \n-\tnoldbuckets = (uintptr)1 << (h->B - 1);\n+\t// make sure we evacuate the oldbucket corresponding\n+\t// to the bucket we\'re about to use\n+\tevacuate(t, h, bucket & (noldbuckets - 1));\n \n-\t// Get evacuation lock.  If we can\'t get it, fine, that means\n-\t// someone else is making progress which is good enough.\n-\tn = h->nevacuate;\n-\tif(n != EVAC_LOCK &&\t// no one has evac lock\n-\t   n != noldbuckets &&\t// there\'s still work to do\n-\t   runtime·casp((void**)&h->nevacuate, (void*)n, (void*)EVAC_LOCK)) { // we acquired lock\n-\t\t// We\'re now the exclusive evacuator.\n-\t\tevacuate(t, h, n);\n-\n-\t\t// record that we\'re done.\n-\t\truntime·atomicstorep((void**)&h->nevacuate, (void*)(n + 1));\n-\t\tif(n + 1 == noldbuckets) {\n-\t\t\t// commit finishing of grow.\n-\t\t\truntime·atomicstorep(&h->oldbuckets, nil);\n-\t\t\t// note: can\'t free oldbuckets, someone might be using it.\n-\t\t\t// it will have to get GCed.\n-\t\t}\n-\t}\n+\t// evacuate one more oldbucket to make progress on growing\n+\tif(h->oldbuckets != nil)\n+\t\tevacuate(t, h, h->nevacuate);\n }\n \n static void\n@@ -496,7 +480,7 @@ hash_lookup(MapType *t, Hmap *h, byte **keyp)\n {\n \tvoid *key;\n \tuintptr hash;\n-\tuintptr bucket;\n+\tuintptr bucket, oldbucket;\n \tBucket *b;\n \tuint8 top;\n \tuintptr i;\n@@ -511,14 +495,13 @@ hash_lookup(MapType *t, Hmap *h, byte **keyp)\n \thash = h->hash0;\n \tt->key->alg->hash(&hash, t->key->size, key);\n \tbucket = hash & (((uintptr)1 << h->B) - 1);\n-\tb = runtime·atomicloadp(&h->oldbuckets);\n-\tif(b != nil) {\n-\t\tgrow_work_read(t, h);\n-\t\tb = (Bucket*)((byte*)b + (bucket & (((uintptr)1 << (h->B - 1)) - 1)) * h->bucketsize);\n-\t\tif(((uintptr)runtime·atomicloadp(&b->overflow) & 1) != 0)\n-\t\t\tgoto newbucket;\n+\tif(h->oldbuckets != nil) {\n+\t\toldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);\n+\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n+\t\tif(evacuated(b)) {\n+\t\t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n+\t\t}\n \t} else {\n-\tnewbucket:\n \t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n \t}\n \ttop = hash >> (sizeof(uintptr)*8 - 8);\n@@ -535,7 +518,7 @@ hash_lookup(MapType *t, Hmap *h, byte **keyp)\n \t\t\t\t}\n \t\t\t}\n \t\t}\n-\t\tb = overflowptr(b);\n+\t\tb = b->overflow;\n \t} while(b != nil);\n \treturn nil;\n }\n@@ -829,7 +812,6 @@ hash_next(struct hash_iter *it)\n \tuintptr bucket, oldbucket;\n \tuintptr hash;\n \tBucket *b;\n-\tbyte *oldbuckets;\n \tuintptr i;\n \tintptr check_bucket;\n \tbool eq;\n@@ -851,15 +833,14 @@ next:\n \t\t\tit->value = nil;\n \t\t\treturn;\n \t\t}\n-\t\tif(it->B == h->B && (oldbuckets = runtime·atomicloadp(&h->oldbuckets)) != nil) {\n+\t\tif(h->oldbuckets != nil && it->B == h->B) {\n \t\t\t// Iterator was started in the middle of a grow, and the grow isn\'t done yet.\n \t\t\t// If the bucket we\'re looking at hasn\'t been filled in yet (i.e. the old\n \t\t\t// bucket hasn\'t been evacuated) then we need to iterate through the old\n \t\t\t// bucket and only return the ones that will be migrated to this bucket.\n-\t\t\tgrow_work_read(t, h);\n \t\t\toldbucket = bucket & (((uintptr)1 << (it->B - 1)) - 1);\n-\t\t\tb = (Bucket*)(oldbuckets + oldbucket * h->bucketsize);\n-\t\t\tif(((uintptr)runtime·atomicloadp(&b->overflow) & 1) == 0) {\n+\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n+\t\t\tif(!evacuated(b)) {\n \t\t\t\tcheck_bucket = bucket;\n \t\t\t} else {\n \t\t\t\tb = (Bucket*)(it->buckets + bucket * h->bucketsize);\n```

### `src/pkg/runtime/hashmap_fast.c`

```diff
--- a/src/pkg/runtime/hashmap_fast.c
+++ b/src/pkg/runtime/hashmap_fast.c
@@ -17,7 +17,7 @@ void
 HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value)
 {
 	uintptr hash;\n
-\tuintptr bucket;\n
+\tuintptr bucket, oldbucket;\n
 	Bucket *b;\n
 	uintptr i;\n
 	KEYTYPE *k;\n
@@ -83,14 +83,13 @@ dohash:\n 	\thash = h->hash0;\n 	\tHASHFUNC(&hash, sizeof(KEYTYPE), &key);\n 	\tbucket = hash & (((uintptr)1 << h->B) - 1);\n-\t\tb = runtime·atomicloadp(&h->oldbuckets);\n-\t\tif(b != nil) {\n-\t\t\tgrow_work_read(t, h);\n-\t\t\tb = (Bucket*)((byte*)b + (bucket & (((uintptr)1 << (h->B - 1)) - 1)) * h->bucketsize);\n-\t\t\tif(((uintptr)runtime·atomicloadp(&b->overflow) & 1) != 0)\n-\t\t\t\tgoto newbucket;\n+\t\tif(h->oldbuckets != nil) {\n+\t\t\toldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);\n+\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n+\t\t\tif(evacuated(b)) {\n+\t\t\t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n+\t\t\t}\n \t\t} else {\n-\t\tnewbucket:\n \t\t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n \t\t}\n \t\ttop = hash >> (sizeof(uintptr)*8 - 8);\n@@ -104,7 +103,7 @@ dohash:\n \t\t\t\t\treturn;\n \t\t\t\t}\n \t\t\t}\n-\t\t\tb = overflowptr(b);\n+\t\t\tb = b->overflow;\n \t\t} while(b != nil);\n \t}\n \tvalue = empty_value;\n@@ -116,7 +115,7 @@ void
 HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res)
 {\n 	uintptr hash;\n-\tuintptr bucket;\n
+\tuintptr bucket, oldbucket;\n
 	Bucket *b;\n
 	uintptr i;\n
 	KEYTYPE *k;\n
@@ -188,14 +187,13 @@ dohash:\n 	\thash = h->hash0;\n 	\tHASHFUNC(&hash, sizeof(KEYTYPE), &key);\n 	\tbucket = hash & (((uintptr)1 << h->B) - 1);\n-\t\tb = runtime·atomicloadp(&h->oldbuckets);\n-\t\tif(b != nil) {\n-\t\t\tgrow_work_read(t, h);\n-\t\t\tb = (Bucket*)((byte*)b + (bucket & (((uintptr)1 << (h->B - 1)) - 1)) * h->bucketsize);\n-\t\t\tif(((uintptr)runtime·atomicloadp(&b->overflow) & 1) != 0)\n-\t\t\t\tgoto newbucket;\n+\t\tif(h->oldbuckets != nil) {\n+\t\t\toldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);\n+\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\n+\t\t\tif(evacuated(b)) {\n+\t\t\t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n+\t\t\t}\n \t\t} else {\n-\t\tnewbucket:\n \t\t\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\n \t\t}\n \t\ttop = hash >> (sizeof(uintptr)*8 - 8);\n@@ -211,7 +209,7 @@ dohash:\n \t\t\t\t\treturn;\n \t\t\t\t}\n \t\t\t}\n-\t\t\tb = overflowptr(b);\n+\t\t\tb = b->overflow;\n \t\t} while(b != nil);\n \t}\n \tvalue = empty_value;\n```

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

このコミットの核心は、Goランタイムのハッシュマップが、読み取り操作中にその内部構造をリサイズ（拡張）する機能を削除することです。

元の実装では、マップの読み取り（`hash_lookup`）やイテレーション（`hash_next`）が行われる際に、`grow_work_read`という関数が呼び出されていました。この関数は、マップが拡張中である場合に、古いバケットから新しいバケットへの要素の移動（evacuation）を少しずつ進める役割を担っていました。これは、マップのリサイズという重い処理を、単一の書き込み操作に集中させるのではなく、複数の読み取り操作に分散させることで、アプリケーションの応答性を高めるための最適化でした。

しかし、この「読み取り時の拡張作業」は、`freebsd-386`環境で問題を引き起こしました。具体的な問題の内容は明記されていませんが、低レベルな並行処理やアトミック操作が絡むため、競合状態、メモリ破壊、あるいはデッドロックなどの深刻なバグが発生した可能性が高いです。

このコミットでは、以下の主要な変更によって、読み取り時の拡張作業を完全に元に戻しています。

1.  **`grow_work_read`関数の削除**: この関数自体がコードベースから削除されました。これにより、読み取り時に拡張作業を行うためのエントリポイントがなくなります。
2.  **`hash_lookup`および`hash_next`からの呼び出しの削除**: マップの検索関数とイテレータ関数から、削除された`grow_work_read`への呼び出しが削除されました。これにより、これらの操作がマップの拡張をトリガーすることはなくなります。
3.  **並行制御メカニズムの削除**: `EVAC_LOCK`マクロや、`runtime·atomicstorep`、`runtime·casp`といったアトミック操作を用いた複雑なロックおよび進行管理のロジックが`evacuate`関数や`grow_work`関数から削除または簡素化されました。これは、読み取り時の並行拡張がなくなったため、これらの厳密な並行制御が不要になったためです。
4.  **`evacuated`チェックの簡素化**: バケットがevacuate済みであるかをチェックするロジックが、アトミックな読み込みを伴うものから、より直接的なポインタ操作に基づくものに簡素化されました。

結果として、Goのハッシュマップの拡張は、再び書き込み操作（要素の追加や削除）によってのみトリガーされ、その際に`grow_work`関数が呼び出されて段階的なevacuationが進められることになります。これにより、`freebsd-386`での問題は解決されますが、マップが非常に大きくなった際の書き込み操作のレイテンシーは、元の最適化が適用されていた時よりも長くなる可能性があります。これは、安定性とパフォーマンスの間のトレードオフとして受け入れられた変更です。

## 関連リンク

*   Go言語の`map`型に関する公式ドキュメントやブログ記事（Goの内部実装に関する詳細な解説は、通常、公式ブログやGoのソースコードコメント、またはGoの設計ドキュメントで見つけることができます）。
*   Goのランタイムソースコード（特に`src/runtime/map.go`や`src/runtime/hashmap.c`など）。

## 参考にした情報源リンク

*   Go言語のソースコード: `https://github.com/golang/go`
*   Goのハッシュマップ実装に関する一般的な情報源（例: Goの公式ブログ、Goの内部実装を解説する技術記事など）。
*   GoのCL（Change List）システムに関する情報（Gerritなど）。
*   FreeBSDおよびi386アーキテクチャに関する技術文書。