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

コミット

このコミットは、Go言語のランタイムにおけるハッシュマップの整数オーバーフローのバグを修正するものです。特に、ハッシュマップのサイズを計算する際に発生する可能性のあるオーバーフローを防ぐための型キャストが導入されています。

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

https://github.com/golang.org/cl/8550043

元コミット内容

commit c8b2b725e098bdc85130f2e00ea43c74a4c4346d
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Mon Apr 8 18:56:38 2013 -0700

    runtime: fix integer overflow in hashmap
    The test is problematic, because it requires 8GB+ of RAM.
    Fixes #5239.
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/8550043
---
 src/pkg/runtime/hashmap.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n
diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c
index 0f32d94e0f..892f0a1700 100644
--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -451,7 +451,7 @@ hash_grow(MapType *t, Hmap *h)\
  	old_buckets = h->buckets;\
  	// NOTE: this could be a big malloc, but since we don't need zeroing it is probably fast.\
  	if(checkgc) mstats.next_gc = mstats.heap_alloc;\
-\tnew_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0);\
+\tnew_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, 1, 0);\
  	flags = (h->flags & ~(Iterator | OldIterator));\
  	if((h->flags & Iterator) != 0) {\
  	\tflags |= OldIterator;\

変更の背景

この変更は、Go言語のランタイムにおけるハッシュマップ（map型）の拡張処理中に発生する可能性のある整数オーバーフローのバグを修正するために行われました。具体的には、Issue #5239で報告された問題に対応しています。

ハッシュマップが要素の追加によって容量を増やす必要がある場合、新しいバケット（bucket）のメモリを確保します。このメモリ確保のサイズ計算において、h->bucketsize << (h->B + 1)という式が使われていました。ここで、h->bucketsizeは現在のバケットのサイズ、h->Bはバケットの数を表す対数（2のべき乗）です。

問題は、h->bucketsizeが比較的小さな整数型（例えばint）であった場合、h->bucketsize << (h->B + 1)の計算結果がその整数型の最大値を超えてしまい、オーバーフローが発生する可能性があったことです。オーバーフローが発生すると、runtime·mallocgc関数に渡されるメモリ確保サイズが意図しない小さな値になり、結果としてメモリ不足やクラッシュ、あるいは予期せぬ動作を引き起こす可能性がありました。

コミットメッセージにある「The test is problematic, because it requires 8GB+ of RAM.」という記述は、このオーバーフローが非常に大きなハッシュマップ、つまり大量のメモリを必要とする状況で顕在化することを示唆しています。このような大規模なテストケースは、通常の開発環境では実行が困難であるため、バグの発見が遅れた可能性があります。

前提知識の解説

1. Go言語の`map`型とハッシュマップ

Go言語のmapは、キーと値のペアを格納するための組み込みデータ構造であり、内部的にはハッシュマップ（またはハッシュテーブル）として実装されています。ハッシュマップは、キーのハッシュ値を使ってメモリ上の位置を決定し、高速な要素の挿入、検索、削除を可能にします。

2. ハッシュマップの拡張（リサイズ）

ハッシュマップは、格納される要素数が増えるにつれて、パフォーマンスを維持するために内部のバケット数を増やす（リサイズする）必要があります。リサイズ時には、通常、現在のバケット数の2倍の新しいバケットを確保し、既存の要素を新しいバケットに再配置します。このプロセスは「成長（grow）」と呼ばれます。

3. ビットシフト演算子 (`<<`)

<<は左ビットシフト演算子です。A << Bは、AのビットをBビットだけ左にシフトすることを意味します。これは、A * (2^B)と等価です。このコミットの文脈では、h->bucketsize << (h->B + 1)は、h->bucketsizeを2^(h->B + 1)倍することを意味し、これは新しいバケットの総サイズを計算するために使用されます。

4. 整数オーバーフロー

整数オーバーフローは、計算結果がそのデータ型で表現できる最大値を超えた場合に発生します。例えば、8ビット符号なし整数（0-255）で200 + 100を計算すると、結果は300ですが、オーバーフローして44（300 % 256）になることがあります。プログラミング言語によっては、オーバーフローがエラーとして扱われることもありますが、Goのランタイムのような低レベルのCコードでは、サイレントにラップアラウンドすることが一般的であり、これがバグの原因となることがあります。

5. `uintptr`型

Go言語にはuintptrという型があります。これは、ポインタを保持するのに十分な大きさの符号なし整数型です。そのサイズは、実行環境のポインタサイズ（32ビットシステムでは4バイト、64ビットシステムでは8バイト）に依存します。uintptrは、ポインタと整数の間で変換を行う際に使用され、特にメモリ管理やシステムコールなどの低レベルプログラミングで重要になります。この型は、メモリサイズやアドレスを表現する際に、プラットフォームに依存しない形で十分なビット幅を保証するために利用されます。

6. `runtime·mallocgc`関数

runtime·mallocgcは、Goランタイム内部で使用されるメモリ確保関数です。Goのガベージコレクタと連携して動作し、ヒープからメモリを割り当てます。この関数は、確保するメモリのサイズを引数として受け取ります。

技術的詳細

変更前のコードでは、新しいバケットのメモリサイズを計算するために以下の式が使われていました。

new_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0);

ここで、h->bucketsizeはint型（またはそれに準ずる整数型）であると仮定されます。h->B + 1は、新しいバケットの総数を決定するための指数です。h->bucketsizeと2^(h->B + 1)の積が、int型で表現できる最大値を超えると、整数オーバーフローが発生します。

例えば、h->bucketsizeが1で、h->B + 1が31（32ビットシステムでintが32ビットの場合、1 << 31は負の値になるか、オーバーフローして0になる可能性があります）のような大きな値になった場合、計算結果は正しくない小さな値になってしまいます。この不正なサイズがruntime·mallocgcに渡されると、必要なメモリが確保されず、ランタイムエラーやクラッシュにつながります。

修正では、この問題に対処するためにh->bucketsizeをuintptr型にキャストしています。

new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, 1, 0);

uintptrはポインタサイズと同じビット幅を持つ符号なし整数型であるため、通常はシステムのアドレス空間全体をカバーできるだけの十分な大きさを持ちます（例えば64ビットシステムでは64ビット）。h->bucketsizeをuintptrにキャストすることで、左ビットシフト演算<<がuintptrのコンテキストで行われるようになります。これにより、計算結果がint型の最大値を超えても、uintptrの範囲内で正しく表現され、オーバーフローが回避されます。結果として、runtime·mallocgcには正しいメモリサイズが渡され、ハッシュマップの拡張が適切に行われるようになります。

この修正は、特に大規模なハッシュマップを使用するアプリケーションにおいて、メモリ関連のクラッシュや不安定性を防ぐ上で非常に重要です。

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

変更はsrc/pkg/runtime/hashmap.cファイルの1箇所のみです。

--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -451,7 +451,7 @@ hash_grow(MapType *t, Hmap *h)\
  	old_buckets = h->buckets;\
  	// NOTE: this could be a big malloc, but since we don't need zeroing it is probably fast.\
  	if(checkgc) mstats.next_gc = mstats.heap_alloc;\
-\tnew_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0);\
+\tnew_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, 1, 0);\
  	flags = (h->flags & ~(Iterator | OldIterator));\
  	if((h->flags & Iterator) != 0) {\
  	\tflags |= OldIterator;\

コアとなるコードの解説

変更された行は、hash_grow関数内で新しいバケットのためのメモリを割り当てる部分です。

変更前: new_buckets = runtime·mallocgc(h->bucketsize << (h->B + 1), 0, 1, 0); この行では、h->bucketsizeという変数が、新しいバケットの総サイズを計算するための左ビットシフト演算の左オペランドとして使用されています。h->bucketsizeがint型の場合、計算結果がint型の最大値を超えるとオーバーフローが発生します。
変更後: new_buckets = runtime·mallocgc((uintptr)h->bucketsize << (h->B + 1), 0, 1, 0); この変更では、h->bucketsizeがuintptr型に明示的にキャストされています。これにより、左ビットシフト演算<<がuintptrのコンテキストで実行されるようになります。uintptrはポインタサイズと同じビット幅を持つ符号なし整数型であり、通常はシステムが扱える最大メモリサイズを表現できるため、計算結果がオーバーフローする可能性が大幅に低減されます。結果として、runtime·mallocgc関数には、ハッシュマップの拡張に必要な正しいメモリサイズが渡されるようになります。

この修正は、Goのmapが非常に多くの要素を格納するような、メモリを大量に消費するシナリオにおいて、ランタイムの安定性と堅牢性を向上させるものです。

参考にした情報源リンク

Go言語の公式ドキュメント (map型): https://go.dev/doc/effective_go#maps
Go言語のランタイムソースコード (hashmap.c): https://github.com/golang/go/blob/master/src/runtime/hashmap.go (現在のGoバージョンではhashmap.goにGoで実装されていますが、当時のバージョンではCで実装されていました。)
Go言語のuintptrに関する情報: https://go.dev/ref/spec#Numeric_types
整数オーバーフローに関する一般的な情報 (Wikipediaなど)
Go言語のコミット履歴と関連する議論

comemo