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

このコミットは、Go言語のランタイムにおけるマップ（ハッシュマップ）の読み取り操作がマルチスレッド環境で安全に行われるようにするための修正です。具体的には、マップの「成長作業」（リハッシュやバケットの再配置）が読み取り時に行われるとスレッドセーフではないという問題に対処しています。この修正により、成長作業は挿入（insert）と削除（delete）の操作時にのみ行われるようになり、読み取り操作の安全性が向上しました。

コミット

commit 0e7144a875aae64a0029c7cbbd1b7fa2d5e7f691
Author: Keith Randall <khr@golang.org>
Date:   Mon Apr 1 18:59:58 2013 -0700

    runtime: make map reads multithreaded safe.
    
    Doing grow work on reads is not multithreaded safe.
    Changed code to do grow work only on inserts & deletes.
    
    This is a short-term fix, eventually we'll want to do
    grow work in parallel to recover the space of the old
    table.
    
    Fixes #5120.
    
    R=bradfitz, khr
    CC=golang-dev
    https://golang.org/cl/8242043

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

https://github.com/golang/go/commit/0e7144a875aae64a0029c7cbbd1b7fa2d5e7f691

元コミット内容

Go言語のランタイムにおいて、マップの読み取り操作をマルチスレッドセーフにするための変更。読み取り時にマップの「成長作業」（リハッシュやバケットの再配置）を行うことはマルチスレッドセーフではないため、この成長作業を挿入および削除操作時のみに行うようにコードが変更されました。これは短期的な修正であり、将来的には古いテーブルのスペースを回復するために、成長作業を並行して行うことが望ましいとされています。このコミットは、Issue 5120を修正します。

変更の背景

Go言語のマップは、要素数が一定の閾値を超えると、より大きなバケット配列にリサイズ（成長）し、既存の要素を新しいバケットに再配置する「成長作業」を行います。この成長作業は、マップのパフォーマンスを維持するために重要です。

しかし、元の実装では、マップの読み取り操作（hash_lookup）中にこの成長作業の一部が行われる可能性がありました。マルチスレッド環境において、複数のゴルーチンが同時にマップを読み取ろうとした際に、そのうちの1つが成長作業を開始してしまうと、他のゴルーチンが不整合な状態のマップを読み取ってしまう可能性があり、データ競合やクラッシュの原因となるスレッドセーフティの問題が発生していました。

特に、Goのマップは内部的にロックを使用せずに並行アクセスを許可する設計（ただし、書き込み操作はロックされる）であるため、読み取り操作が成長作業のような状態変更を伴う処理を行うことは、並行性の保証を困難にしていました。

この問題は、GoのIssue 5120として報告されており、このコミットはその問題に対する短期的な解決策として導入されました。長期的な目標は、成長作業自体を並行して行い、古いテーブルのスペースを効率的に解放することですが、このコミットではまず読み取り操作の安全性を確保することに焦点を当てています。

前提知識の解説

Go言語のマップ (map)

Go言語のマップは、キーと値のペアを格納するハッシュテーブルの実装です。内部的には、ハッシュ関数を用いてキーをバケット（bucket）と呼ばれる配列のインデックスにマッピングし、そのバケットにキーと値を格納します。

ハッシュテーブルの成長 (Growing/Resizing)

ハッシュテーブルは、要素数が増えると衝突（異なるキーが同じバケットにマッピングされること）が増え、パフォーマンスが低下します。これを防ぐため、要素数が一定の閾値を超えると、より大きなサイズの新しいバケット配列を割り当て、既存の要素を新しい配列に再配置します。このプロセスを「成長作業」または「リハッシュ」と呼びます。

Goのマップの成長作業は、一度に全ての要素を移動するのではなく、段階的に行われます。新しいバケット配列が作成され、古いバケット配列と新しいバケット配列が共存する期間があります。この期間中、要素の読み書きは両方の配列を参照しながら行われます。

マルチスレッドセーフティ (Multithreaded Safety)

複数のスレッド（Goではゴルーチン）が同時に共有データにアクセスする際に、データの整合性が保たれることを指します。データ競合（data race）が発生しないように、適切な同期メカニズム（ロックなど）を使用する必要があります。

Goのマップは、読み取り操作に関してはロックなしで並行アクセスを許可する設計ですが、書き込み操作（挿入、削除、更新）は内部的にロックによって保護されています。しかし、読み取り操作中にマップの内部構造が変更される「成長作業」が行われると、この並行読み取りの安全性が損なわれる可能性がありました。

`grow_work` 関数

Goのランタイムにおけるマップの実装で、成長作業の一部を実行する関数です。この関数は、古いバケットから新しいバケットへの要素の移動を段階的に行います。

`hash_iter` 構造体

マップのイテレータ（for rangeループなどでマップを走査する際に使用される）の内部状態を保持する構造体です。この構造体のサイズが変更されると、コンパイラ（gc）とランタイムの間で不整合が生じる可能性があるため、サイズチェックが行われます。

技術的詳細

このコミットの主要な変更点は、マップの読み取り関数である hash_lookup から grow_work の呼び出しを削除し、成長作業を挿入 (hash_insert) および削除 (hash_delete) 操作に限定したことです。

`hash_lookup` の変更

変更前は、hash_lookup 関数内で h->oldbuckets != nil （古いバケットが存在する場合、つまり成長作業が進行中の場合）であれば grow_work(t, h, bucket) を呼び出して、現在のバケットの成長作業を進めていました。

変更後は、hash_lookup 内で grow_work の直接的な呼び出しが削除されました。代わりに、h->oldbuckets != nil の場合、まず古いバケット (oldbucket) を参照し、そのバケットが既に evacuated（新しいバケットに移動済み）であるかどうかをチェックします。もし evacuated であれば、新しいバケット (h->buckets) を参照します。これにより、読み取り操作は成長作業をトリガーすることなく、既存のバケットの状態に基づいて適切なデータを参照するようになります。

`hash_iter` 構造体の変更と `range.c` の更新

マップのイテレータである hash_iter 構造体に intptr check_bucket; という新しいフィールドが追加されました。これにより、hash_iter のサイズが変更されました。

src/cmd/gc/range.c はGoコンパイラのバックエンドの一部であり、マップのイテレータのサイズに関する情報を持っています。hash_iter のサイズが変更されたため、range.c 内の th->bound = 10; が th->bound = 11; に更新されました。これは、hash_iter 構造体のサイズがポインタの数で10から11に増えたことを反映しています。

また、hash_iter_init 関数に sizeof(struct hash_iter) / sizeof(uintptr) != 11 のチェックが追加され、コンパイラとランタイムの間で hash_iter のサイズに関する不整合がないことを保証しています。もしサイズが一致しない場合、runtime·throw("hash_iter size incorrect"); が呼び出され、ランタイムパニックが発生します。

イテレータの挙動の変更 (`hash_next`)

hash_next 関数（マップのイテレータが次の要素に進むための関数）も、成長作業中のマップの走査を正しく処理するように変更されました。特に、イテレータが成長作業の途中で開始された場合（h->oldbuckets != nil && it->B == h->B）、古いバケットがまだ evacuated されていない場合に、check_bucket を用いて、古いバケットから新しいバケットに移動する際にどの要素が現在の新しいバケットに属するかを判断するロジックが追加されました。これにより、成長作業中のマップをイテレートする際に、重複や欠落なく要素を走査できるようになります。

`map_test.go` の変更

src/pkg/runtime/map_test.go から TestConcurrentReadsAfterGrowth テストのスキップコメントが削除されました。これは、このコミットによって修正された問題に関連するテストであり、修正が適用されたことでテストがパスするようになったため、スキップする必要がなくなったことを示唆しています。

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

src/pkg/runtime/hashmap.c:
- hash_lookup 関数から grow_work の呼び出しを削除し、古いバケットの参照ロジックを変更。
- hash_iter 構造体に intptr check_bucket; フィールドを追加。
- hash_iter_init 関数に hash_iter サイズのチェックを追加。
- hash_next 関数で、成長中のマップのイテレーションロジックを修正。
src/pkg/runtime/hashmap_fast.c:
- HASH_LOOKUP1 および HASH_LOOKUP2 マクロ（高速パスのマップルックアップ）から grow_work の呼び出しを削除し、古いバケットの参照ロジックを変更。
src/cmd/gc/range.c:
- walkrange 関数内で、hash_iter のサイズを示す th->bound の値を 10 から 11 に変更。
src/pkg/runtime/map_test.go:
- TestConcurrentReadsAfterGrowth テストのスキップコメントを削除。

コアとなるコードの解説

`src/pkg/runtime/hashmap.c` の `hash_lookup` 変更

 // 変更前
 if(h->oldbuckets != nil)
  grow_work(t, h, bucket);
 b = (Bucket*)(h->buckets + bucket * h->bucketsize);

 // 変更後
 if(h->oldbuckets != nil) {
  oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);
  b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
  if(evacuated(b)) {
   b = (Bucket*)(h->buckets + bucket * h->bucketsize);
  }
 } else {
  b = (Bucket*)(h->buckets + bucket * h->bucketsize);
 }

この変更が最も重要です。hash_lookup から grow_work の呼び出しが削除されました。これにより、読み取り操作がマップの成長作業をトリガーすることがなくなります。代わりに、成長作業が進行中の場合（h->oldbuckets != nil）、まず対応する古いバケット (oldbucket) を特定し、そのバケットが既に新しいバケットに「避難済み」（evacuated）であるかをチェックします。もし避難済みであれば、新しいバケット (h->buckets) からデータを読み取ります。そうでなければ、古いバケットから読み取ります。これにより、読み取り操作はマップの現在の状態に応じて適切なバケットを参照し、成長作業による不整合を回避します。

`src/cmd/gc/range.c` の `hash_iter` サイズ変更

 // 変更前
 // see ../../pkg/runtime/hashmap.h:/hash_iter
 // Size of hash_iter in # of pointers.
 th->bound = 10;

 // 変更後
 // see ../../pkg/runtime/hashmap.c:/hash_iter
 // Size of hash_iter in # of pointers.
 th->bound = 11;

hash_iter 構造体に新しいフィールドが追加されたため、そのサイズが変更されました。コンパイラは、この th->bound の値を使って hash_iter のサイズを認識します。この値が正しくないと、コンパイラが生成するコードとランタイムの実際の構造体レイアウトとの間に不整合が生じ、クラッシュの原因となります。そのため、この変更は必須です。

`src/pkg/runtime/hashmap.c` の `hash_iter_init` と `hash_next` の変更

// hash_iter_init 内の追加
if(sizeof(struct hash_iter) / sizeof(uintptr) != 11) {
 runtime·throw("hash_iter size incorrect"); // see ../../cmd/gc/range.c
}

// hash_next 内の追加ロジック（一部抜粋）
if(h->oldbuckets != nil && it->B == h->B) {
 // Iterator was started in the middle of a grow, and the grow isn't done yet.
 // If the bucket we're looking at hasn't been filled in yet (i.e. the old
 // bucket hasn't been evacuated) then we need to iterate through the old
 // bucket and only return the ones that will be migrated to this bucket.
 oldbucket = bucket & (((uintptr)1 << (it->B - 1)) - 1);
 b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
 if(!evacuated(b)) {
  check_bucket = bucket;
 } else {
  b = (Bucket*)(it->buckets + bucket * h->bucketsize);
  check_bucket = -1;
 }
} else {
 b = (Bucket*)(it->buckets + bucket * h->bucketsize);
 check_bucket = -1;
}
// ...
if(check_bucket >= 0) {
 // Special case: iterator was started during a grow and the
 // grow is not done yet.  We're working on a bucket whose
 // oldbucket has not been evacuated yet.  So we iterate
 // through the oldbucket, skipping any keys that will go
 // to the other new bucket (each oldbucket expands to two
 // buckets during a grow).
 // ...
}

hash_iter_init のサイズチェックは、コンパイラとランタイムの整合性を保証するための防御的なコードです。 hash_next の変更は、マップのイテレーション中に成長作業が進行している場合の複雑なケースを処理します。マップが成長中の場合、古いバケットの要素は新しい2つのバケットに分割されます。イテレータが古いバケットを走査しているときに、そのバケットがまだ evacuated されていない場合、check_bucket を使用して、現在走査している要素が新しいバケットのどちらに属するかを判断し、適切な要素のみを返すようにします。これにより、成長作業中のマップをイテレートしても、正しい要素が重複なく、かつ欠落なく取得されることが保証されます。

参考にした情報源リンク

Go Issue 5120 (上記と同じ)
Go CL 8242043 (上記と同じ)
Go言語のマップの実装に関する一般的な情報源（例: Goのソースコード、Goのブログ記事、技術解説記事など）
- Goのマップの内部構造に関する解説記事 (例: "Go's map implementation" by Dave Cheney, "The Go Programming Language" by Alan A. A. Donovan and Brian W. Kernighan)
- Goのランタイムソースコード (src/runtime/map.go, src/runtime/hashmap.c など)
- ハッシュテーブルの一般的な概念に関する情報源 (例: Wikipedia, データ構造とアルゴリズムの教科書)
マルチスレッドプログラミングとデータ競合に関する一般的な情報源

comemo