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

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

このコミットは、Goランタイムにおける32ビットシステムでのメモリ割り当て（malloc）に関するバグ修正です。具体的には、ポインタアドレスが0x80000000（2GB）以上になる場合に発生する問題に対処しています。Goのメモリ管理において、mheap構造体内のspans配列がメモリ領域を管理しますが、32ビットシステムではこのspans配列のインデックス計算に誤りがあり、特定の高位アドレスで不正なメモリ参照が発生する可能性がありました。この修正は、64ビットシステムと同様に、arena_start（ヒープの開始アドレス）を基準としてspans配列のインデックスを計算することで、この問題を解決しています。

コミット

commit 8da8b37674732ca4532dabcabe7f495b3d6455e9
Author: Ian Lance Taylor <iant@golang.org>
Date:   Thu Jan 9 15:00:00 2014 -0800

    runtime: fix 32-bit malloc for pointers >= 0x80000000
    
    The spans array is allocated in runtime·mallocinit.  On a
    32-bit system the number of entries in the spans array is
    MaxArena32 / PageSize, which (2U << 30) / (1 << 12) == (1 << 19).
    So we are allocating an array that can hold 19 bits for an
    index that can hold 20 bits.  According to the comment in the
    function, this is intentional: we only allocate enough spans
    (and bitmaps) for a 2G arena, because allocating more would
    probably be wasteful.
    
    But since the span index is simply the upper 20 bits of the
    memory address, this scheme only works if memory addresses are
    limited to the low 2G of memory.  That would be OK if we were
    careful to enforce it, but we're not.  What we are careful to
    enforce, in functions like runtime·MHeap_SysAlloc, is that we
    always return addresses between the heap's arena_start and
    arena_start + MaxArena32.
    
    We generally get away with it because we start allocating just
    after the program end, so we only run into trouble with
    programs that allocate a lot of memory, enough to get past
    address 0x80000000.
    
    This changes the code that computes a span index to subtract
    arena_start on 32-bit systems just as we currently do on
    64-bit systems.
    
    R=golang-codereviews, rsc
    CC=golang-codereviews
    https://golang.org/cl/49460043

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

https://github.com/golang/go/commit/8da8b37674732ca4532dabcabe7f495b3d6455e9

元コミット内容

Goランタイムにおいて、32ビットシステムでのmalloc（メモリ割り当て）が、ポインタアドレスが0x80000000（2GB）以上になる場合に正しく動作しない問題を修正します。

spans配列はruntime·mallocinitで割り当てられます。32ビットシステムでは、spans配列のエントリ数はMaxArena32 / PageSize、すなわち(2U << 30) / (1 << 12) == (1 << 19)となります。これは、19ビットを保持できる配列に、20ビットを保持できるインデックスを使用していることを意味します。関数内のコメントによると、これは意図的なもので、2GBのアリーナ（メモリ領域）に対してのみspans（およびビットマップ）を割り当てるのは、それ以上割り当てると無駄になる可能性が高いからです。

しかし、スパンインデックスが単にメモリアドレスの上位20ビットであるため、このスキームはメモリアドレスが下位2GBに制限されている場合にのみ機能します。これを厳密に強制していれば問題ありませんが、実際にはそうではありません。runtime·MHeap_SysAllocのような関数では、常にヒープのarena_startからarena_start + MaxArena32の間のアドレスを返すように厳密に強制しています。

通常、プログラムの終了直後からメモリ割り当てが開始されるため、この問題は大量のメモリを割り当て、アドレスが0x80000000を超えるようなプログラムでのみ発生していました。

この変更により、スパンインデックスを計算するコードが、64ビットシステムと同様に、32ビットシステムでもarena_startを減算するように修正されます。

変更の背景

Goのランタイムは、効率的なメモリ管理のためにヒープをmspanと呼ばれる固定サイズのチャンクに分割し、これらのmspanをmheap構造体内のspans配列で管理しています。spans配列は、特定のメモリページアドレスに対応するmspanへのポインタを格納することで、メモリページから対応するmspanを高速にルックアップできるように設計されています。

問題は32ビットシステムに特有のものでした。32ビットシステムでは、アドレス空間が4GBに制限されます。Goのランタイムは、ヒープ領域として最大2GB（MaxArena32）を想定し、これに対応するspans配列を割り当てていました。spans配列のインデックスは、メモリアドレスをPageShift（通常12ビット、つまり4KB）で右シフトすることで計算されます。これにより、メモリアドレスの上位ビットがspans配列のインデックスとして使用されます。

しかし、32ビットシステムでは、spans配列がカバーする範囲が2GBに限定されているにもかかわらず、runtime·MHeap_SysAllocなどのシステムコールは、arena_start（ヒープの開始アドレス）からarena_start + MaxArena32の範囲でメモリを割り当てます。もしarena_startが0に近い値であれば問題ありませんが、プログラムが大量のメモリを割り当てたり、OSがヒープを0x80000000（2GB）以上の高位アドレスに配置したりすると、spans配列のインデックス計算がずれてしまう可能性がありました。

具体的には、spans配列のインデックスは、アドレスをページサイズで割った値（ページインデックス）をそのまま使用していました。64ビットシステムでは、アドレス空間が広いため、arena_startを減算してページインデックスを正規化していました。しかし、32ビットシステムではこの正規化が行われていなかったため、0x80000000以上の高位アドレスが割り当てられた場合、そのアドレスに対応するspans配列のインデックスが、実際に割り当てられたspans配列の範囲外になってしまい、不正なメモリ参照やクラッシュを引き起こす可能性がありました。

このバグは、特に大量のメモリを割り当てるプログラムや、OSがヒープを高位アドレスに配置する環境で顕在化しました。

前提知識の解説

このコミットを理解するためには、Goランタイムのメモリ管理に関するいくつかの基本的な概念を理解しておく必要があります。

  • Goのメモリ管理（GC）: Goは独自のガベージコレクタ（GC）を持ち、ヒープメモリの割り当てと解放を管理します。開発者は通常、メモリの明示的な解放を行う必要はありません。
  • ヒープ (Heap): プログラムが動的にメモリを割り当てる領域です。Goのランタイムは、このヒープを効率的に管理します。
  • mheap: Goランタイムにおけるヒープ全体の管理構造体です。シングルトンとして存在し、ヒープのグローバルな状態を保持します。
    • arena_start: ヒープ領域が開始される仮想アドレス。
    • MaxArena32: 32ビットシステムにおけるヒープの最大サイズ（2GB）。
    • spans: mspan構造体へのポインタの配列。メモリページから対応するmspanをルックアップするために使用されます。
  • mspan: ヒープ内の連続したメモリページ群を表す構造体です。mspanは、特定のサイズのオブジェクトを格納するために使用されます。
    • start: mspanがカバーする最初のメモリページのページインデックス。
    • npages: mspanがカバーするページ数。
    • state: mspanの状態（使用中、解放済みなど）。
  • PageSize: メモリページのサイズ。Goランタイムでは通常4KB（1 << 12バイト）です。
  • PageShift: PageSizeの対数（log2(PageSize)）。PageSizeが4KBの場合、PageShiftは12です。メモリアドレスをPageShiftで右シフトすることで、ページインデックス（ページ番号）が得られます。
    • uintptr(v) >> PageShift: アドレスvが属するメモリページのインデックスを計算します。
  • sizeof(void*): ポインタのサイズ。32ビットシステムでは4バイト、64ビットシステムでは8バイトです。この値は、コンパイル時に決定されるマクロや定数として使用されます。

Goのメモリ管理では、あるメモリアドレスvがどのmspanに属するかを調べるために、vのページインデックスを計算し、そのページインデックスをmheap.spans配列のインデックスとして使用します。

技術的詳細

このコミットの核心は、spans配列のインデックス計算における32ビットシステムと64ビットシステム間の不整合を解消することにあります。

問題の根源:

Goのランタイムは、メモリをページ単位で管理し、各ページがどのmspanに属するかをmheap.spans配列で追跡します。spans配列のインデックスは、メモリアドレスをPageShiftで右シフトすることで得られる「ページインデックス」です。

  • 64ビットシステム: 仮想アドレス空間が非常に広いため、ヒープがどこに配置されても、arena_startを基準とした相対的なページインデックスを使用することが不可欠です。つまり、p = (uintptr)v >> PageShift; p -= (uintptr)runtime·mheap.arena_start >> PageShift; のように、アドレスvからarena_startを減算してからページインデックスを計算していました。これにより、spans配列のインデックスは常に0から始まる正規化された値になります。
  • 32ビットシステム（修正前）: 32ビットシステムでは、sizeof(void*) == 8（64ビットシステムの場合）という条件でarena_startの減算をスキップしていました。これは、32ビットシステムのアドレス空間が2GBに制限されているため、arena_startが0に近いと仮定し、絶対的なページインデックスをそのままspans配列のインデックスとして使用しても問題ないと考えていたためです。しかし、この仮定は、OSがヒープを高位アドレス（例: 0x80000000以上）に配置する可能性があるという事実を見落としていました。
    • MaxArena32は2GBであり、spans配列も2GB分のページインデックスをカバーするように割り当てられていました。つまり、spans配列のインデックスは0から(2GB / PageSize) - 1の範囲を想定していました。
    • もしarena_startが0でなく、例えば0x80000000だった場合、0x80000000のアドレスのページインデックスは0x80000000 >> PageShiftとなり、これはspans配列がカバーする範囲外の大きな値になってしまいます。これにより、mheap.spans[インデックス]へのアクセスが配列の境界外となり、クラッシュや不正なメモリ参照が発生していました。

修正内容:

このコミットは、32ビットシステムでも64ビットシステムと同様に、spans配列のインデックス計算時にarena_startを減算するように変更します。これにより、メモリアドレスがヒープのどこに割り当てられても、spans配列のインデックスが常に0から始まる正規化された値となり、spans配列の境界外アクセスを防ぎます。

具体的には、sizeof(void*) == 8という条件分岐を削除し、p -= (uintptr)runtime·mheap.arena_start >> PageShift; または p -= (uintptr)h->arena_start >> PageShift; のようなarena_startを減算する処理を、32ビットシステムでも無条件に実行するように変更しています。

この変更により、Goランタイムは32ビットシステムにおいても、ヒープがどの仮想アドレスに配置されても、spans配列を介したmspanのルックアップを正確に行えるようになります。

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

このコミットでは、主に以下の3つのファイルが変更されています。

  1. src/pkg/runtime/malloc.goc
  2. src/pkg/runtime/mgc0.c
  3. src/pkg/runtime/mheap.c

これらのファイルでは、mheap.spans配列へのインデックス計算を行う箇所から、if(sizeof(void*) == 8)という条件分岐が削除されています。

src/pkg/runtime/malloc.goc の変更点:

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -593,8 +593,7 @@ runtime·settype_flush(M *mp)
 
 		// (Manually inlined copy of runtime·MHeap_Lookup)
 		p = (uintptr)v>>PageShift;
-		if(sizeof(void*) == 8)
-			p -= (uintptr)runtime·mheap.arena_start >> PageShift;
+		p -= (uintptr)runtime·mheap.arena_start >> PageShift;
 		s = runtime·mheap.spans[p];
 
 		if(s->sizeclass == 0) {

src/pkg/runtime/mgc0.c の変更点:

このファイルでは、markonly, flushptrbuf, checkptr 関数内で同様の変更が行われています。

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -292,8 +292,7 @@ markonly(void *obj)
 	// (Manually inlined copy of MHeap_LookupMaybe.)
 	k = (uintptr)obj>>PageShift;
 	x = k;
-	if(sizeof(void*) == 8)
-		x -= (uintptr)runtime·mheap.arena_start>>PageShift;
+	x -= (uintptr)runtime·mheap.arena_start>>PageShift;
 	s = runtime·mheap.spans[x];
 	if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse)
 		return false;
@@ -492,8 +491,7 @@ flushptrbuf(Scanbuf *sbuf)
 		// (Manually inlined copy of MHeap_LookupMaybe.)
 		k = (uintptr)obj>>PageShift;
 		x = k;
-		if(sizeof(void*) == 8)
-			x -= (uintptr)arena_start>>PageShift;
+		x -= (uintptr)arena_start>>PageShift;
 		s = runtime·mheap.spans[x];
 		if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse)
 			continue;
@@ -540,8 +538,7 @@ flushptrbuf(Scanbuf *sbuf)
 		// Ask span about size class.
 		// (Manually inlined copy of MHeap_Lookup.)
 		x = (uintptr)obj >> PageShift;
-		if(sizeof(void*) == 8)
-			x -= (uintptr)arena_start>>PageShift;
+		x -= (uintptr)arena_start>>PageShift;
 		s = runtime·mheap.spans[x];
 
 		PREFETCH(obj);
@@ -658,8 +655,7 @@ checkptr(void *obj, uintptr objti)
 	if(t == nil)
 		return;
 	x = (uintptr)obj >> PageShift;
-	if(sizeof(void*) == 8)
-		x -= (uintptr)(runtime·mheap.arena_start)>>PageShift;
+	x -= (uintptr)(runtime·mheap.arena_start)>>PageShift;
 	s = runtime·mheap.spans[x];
 	objstart = (byte*)((uintptr)s->start<<PageShift);
 	if(s->sizeclass != 0) {

src/pkg/runtime/mheap.c の変更点:

このファイルでは、runtime·MHeap_MapSpans, HaveSpan（複数箇所）, MHeap_Grow, runtime·MHeap_Lookup, runtime·MHeap_LookupMaybe, MHeap_FreeLocked 関数内で同様の変更が行われています。

--- a/src/pkg/runtime/mheap.c
+++ b/src/pkg/runtime/mheap.c
@@ -74,8 +74,7 @@ runtime·MHeap_MapSpans(MHeap *h)
 
 	// Map spans array, PageSize at a time.
 	n = (uintptr)h->arena_used;
-	if(sizeof(void*) == 8)
-		n -= (uintptr)h->arena_start;
+	n -= (uintptr)h->arena_start;
 	n = n / PageSize * sizeof(h->spans[0]);
 	n = ROUND(n, PageSize);
 	if(h->spans_mapped >= n)
@@ -169,8 +168,7 @@ HaveSpan:
 		runtime·MSpan_Init(t, s->start + npage, s->npages - npage);
 		s->npages = npage;
 		p = t->start;
-		if(sizeof(void*) == 8)
-			p -= ((uintptr)h->arena_start>>PageShift);
+		p -= ((uintptr)h->arena_start>>PageShift);
 		if(p > 0)
 			h->spans[p-1] = s;
 		h->spans[p] = t;
@@ -188,8 +186,7 @@ HaveSpan:
 	s->elemsize = (sizeclass==0 ? s->npages<<PageShift : runtime·class_to_size[sizeclass]);
 	s->types.compression = MTypes_Empty;
 	p = s->start;
-	if(sizeof(void*) == 8)
-		p -= ((uintptr)h->arena_start>>PageShift);
+	p -= ((uintptr)h->arena_start>>PageShift);
 	for(n=0; n<npage; n++)
 		h->spans[p+n] = s;
 	return s;
@@ -257,8 +254,7 @@ MHeap_Grow(MHeap *h, uintptr npage)
 	s = runtime·FixAlloc_Alloc(&h->spanalloc);
 	runtime·MSpan_Init(s, (uintptr)v>>PageShift, ask>>PageShift);
 	p = s->start;
-	if(sizeof(void*) == 8)
-		p -= ((uintptr)h->arena_start>>PageShift);
+	p -= ((uintptr)h->arena_start>>PageShift);
 	h->spans[p] = s;
 	h->spans[p + s->npages - 1] = s;
 	s->state = MSpanInUse;
@@ -275,8 +271,7 @@ runtime·MHeap_Lookup(MHeap *h, void *v)
 	uintptr p;
 	
 	p = (uintptr)v;
-	if(sizeof(void*) == 8)
-		p -= (uintptr)h->arena_start;
+	p -= (uintptr)h->arena_start;
 	return h->spans[p >> PageShift];
 }
 
@@ -297,8 +292,7 @@ runtime·MHeap_LookupMaybe(MHeap *h, void *v)
 		return nil;
 	p = (uintptr)v>>PageShift;
 	q = p;
-	if(sizeof(void*) == 8)
-		q -= (uintptr)h->arena_start >> PageShift;
+	q -= (uintptr)h->arena_start >> PageShift;
 	s = h->spans[q];
 	if(s == nil || p < s->start || v >= s->limit || s->state != MSpanInUse)
 		return nil;
@@ -345,8 +339,7 @@ MHeap_FreeLocked(MHeap *h, MSpan *s)
 
 	// Coalesce with earlier, later spans.
 	p = s->start;
-	if(sizeof(void*) == 8)
-		p -= (uintptr)h->arena_start >> PageShift;
+	p -= (uintptr)h->arena_start >> PageShift;
 	if(p > 0 && (t = h->spans[p-1]) != nil && t->state != MSpanInUse) {
 		if(t->npreleased == 0) {  // cant't touch this otherwise
 			tp = (uintptr*)(t->start<<PageShift);

コアとなるコードの解説

変更されたコードの核心は、sizeof(void*) == 8という条件分岐の削除です。

  • 変更前:

    p = (uintptr)v>>PageShift;
if(sizeof(void*) == 8) // 64ビットシステムの場合のみ
    p -= (uintptr)runtime·mheap.arena_start >> PageShift;
s = runtime·mheap.spans[p];

    このコードは、64ビットシステムではarena_startを減算してページインデックスを正規化していましたが、32ビットシステムではこの減算を行っていませんでした。32ビットシステムでは、sizeof(void*)は4であるため、if文の条件が偽となり、pはarena_startからのオフセットではなく、絶対的なページインデックスのまま使用されていました。

  • 変更後:

    p = (uintptr)v>>PageShift;
p -= (uintptr)runtime·mheap.arena_start >> PageShift; // 無条件に減算
s = runtime·mheap.spans[p];

    この変更により、sizeof(void*) == 8の条件が削除され、p -= (uintptr)runtime·mheap.arena_start >> PageShift; の行が32ビットシステムでも無条件に実行されるようになりました。

この変更が問題を解決する理由:

mheap.spans配列は、ヒープの開始アドレス（arena_start）を基準として、そのヒープ領域内のページインデックスに対応するmspanを格納しています。したがって、spans配列にアクセスするためのインデックスは、常にarena_startからの相対的なページインデックスである必要があります。

  • 32ビットシステムでの問題の再確認: 修正前は、32ビットシステムでarena_startが0でない場合（例えば0x80000000）、0x80000000のアドレスのページインデックスは0x80000000 >> PageShiftとなり、これはspans配列の有効な範囲（0からMaxArena32 / PageSize - 1）をはるかに超える値になっていました。これにより、mheap.spans[大きなインデックス]という不正なアクセスが発生していました。

  • 修正後の動作: 修正後は、32ビットシステムでもp -= (uintptr)runtime·mheap.arena_start >> PageShift; が実行されます。これにより、pは常にarena_startからの相対的なページインデックスに変換されます。例えば、arena_startが0x80000000で、vが0x80001000の場合、

    1. p = (uintptr)0x80001000 >> PageShift; （0x80001000のページインデックス）
    2. p -= (uintptr)0x80000000 >> PageShift; （arena_startのページインデックスを減算） これにより、pはarena_startを基準とした相対的なページインデックス（この例では1）となり、spans配列の有効な範囲内のインデックスとして使用されるようになります。

この修正により、Goランタイムは32ビットシステムにおいても、ヒープがどの仮想アドレスに配置されても、spans配列を介したmspanのルックアップを正確に行えるようになり、0x80000000以上の高位アドレスでのメモリ割り当てに関するバグが解消されました。

関連リンク

参考にした情報源リンク

  • Goのソースコード（特にsrc/runtime/mheap.go, src/runtime/mspan.goなど）
  • Goのメモリ管理に関する公式ドキュメントやブログ記事（GoのGCの仕組み、ヒープの構造など）
  • Goのランタイムに関する技術解説記事
  • sizeof(void*)の動作に関するC言語の一般的な知識
  • 32ビットおよび64ビットシステムにおける仮想メモリとアドレス空間の概念
  • PageSizeとPageShiftの概念
  • MaxArena32の定義とGoの32ビットサポートに関する情報
  • runtime·MHeap_SysAllocの動作に関する情報
  • mheap.spans配列の役割とインデックス計算に関する情報
  • Goのガベージコレクションの内部動作に関する情報
  • Goのコミット履歴と関連する議論