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

このコミットは、Goランタイムのメモリ管理におけるMSpan構造体のlimitフィールドの扱いを改善し、それによってポインタの境界チェックを最適化することを目的としています。特に、大きなメモリ領域（large spans）に対するMSpan.limitの正確な設定と、そのlimitを利用した効率的なポインタ検証に焦点を当てています。

コミット

commit d6f89d735e66c7b955f262d38ba95f5e9a793b95
Author: Keith Randall <khr@golang.org>
Date:   Thu May 30 21:32:20 2013 -0700

    runtime: set MSpan.limit properly for large spans.
    Then use the limit to make sure MHeap_LookupMaybe & inlined
    copies don't return a span if the pointer is beyond the limit.
    Use this fact to optimize all call sites.
    
    R=golang-dev, dvyukov
    CC=golang-dev
    https://golang.org/cl/9869045

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

https://github.com/golang/go/commit/d6f89d735e66c7b955f262d38ba95f5e9a793b95

元コミット内容

runtime: set MSpan.limit properly for large spans.
Then use the limit to make sure MHeap_LookupMaybe & inlined
copies don't return a span if the pointer is beyond the limit.
Use this fact to optimize all call sites.

R=golang-dev, dvyukov
CC=golang-dev
https://golang.org/cl/9869045

変更の背景

Goランタイムのメモリ管理では、ヒープはMSpanと呼ばれる連続したメモリページ群に分割されます。各MSpanは、特定のサイズのオブジェクト（small objects）を格納するか、または単一の大きなオブジェクト（large objects）を格納するために使用されます。MSpan構造体には、そのスパンがカバーするメモリ範囲の開始アドレスと終了アドレスを示すフィールドが含まれています。

このコミット以前は、特に大きなメモリ領域（sizeclass == 0、つまり特定のサイズクラスに属さない大きなアロケーション）の場合に、MSpan.limitフィールドが常に正確に設定されているわけではありませんでした。そのため、ポインタが特定のスパン内に収まっているかをチェックする際に、s->limitだけでは不十分であり、s->startとs->npages（ページ数）を組み合わせて計算する必要がありました。これは、冗長な計算や、場合によっては複数の場所での同様のチェックロジックの重複を招いていました。

このコミットの背景には、以下の課題がありました。

1. 非効率な境界チェック: MSpan.limitが信頼できないため、ポインタがスパンの範囲内にあるかを確認する際に、s->startとs->npagesを用いたより複雑な計算が必要でした。これは、特にガベージコレクションのマークフェーズやポインタルックアップのような頻繁に実行される操作において、パフォーマンスのオーバーヘッドとなっていました。
2. コードの重複と保守性の低下: 同じような境界チェックロジックがランタイムの複数の箇所に散在しており、コードの可読性と保守性を低下させていました。
3. 最適化の機会: MSpan.limitが常に正確であれば、よりシンプルで効率的な単一の比較操作で境界チェックを完了できるはずでした。

このコミットは、これらの課題を解決し、ランタイムのメモリ管理部分のパフォーマンスとコード品質を向上させることを目指しています。

前提知識の解説

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

• Goランタイム (Go Runtime): Goプログラムの実行を管理する部分で、ガベージコレクション、スケジューリング、メモリ割り当てなどを担当します。C言語で書かれた部分（.cファイル）とGo言語で書かれた部分（.goファイル、またはGoのC言語拡張である.gocファイル）があります。
• MHeap: Goランタイムのグローバルヒープを表す構造体です。メモリの割り当てと解放を管理し、MSpanのリストを保持します。
• MSpan: ヒープメモリの連続したページ群を表す構造体です。MSpanは、Goのメモリ割り当ての基本的な単位です。
  • start: スパンの開始アドレス（ページ単位）。
  • npages: スパンに含まれるページ数。
  • limit: スパンがカバーするメモリ範囲の終了アドレス（バイト単位）。このコミットの主要な変更点です。
  • state: スパンの状態（例: MSpanInUse - 使用中、MSpanFree - 空き）。
  • sizeclass: スパンが割り当てるオブジェクトのサイズクラス。sizeclass == 0は、特定のサイズクラスに属さない大きなオブジェクト（large object）が割り当てられていることを意味します。
  • elemsize: スパンが割り当てる各オブジェクトのサイズ（small objectsの場合）。
• PageShift: メモリページのサイズをビットシフトで表す定数。例えば、ページサイズが4KB（4096バイト）の場合、PageShiftは12（2^12 = 4096）となります。s->start << PageShiftは、ページ単位の開始アドレスをバイト単位の開始アドレスに変換します。
• ガベージコレクション (Garbage Collection - GC): Goの自動メモリ管理機能。不要になったメモリを自動的に解放します。GCのプロセスでは、ヒープ上のポインタを走査し、到達可能なオブジェクトをマークするフェーズ（マークフェーズ）があります。
• runtime·MHeap_LookupMaybe: 特定のポインタがどのMSpanに属するかをルックアップするランタイム関数。ガベージコレクタやデバッガなどがポインタの情報を取得する際に使用します。
• markonly: ガベージコレクションのマークフェーズで、オブジェクトをマークする関数。ポインタが有効なヒープオブジェクトを指しているかを確認します。
• flushptrbuf: ガベージコレクション中にポインタバッファをフラッシュする関数。ここでもポインタの有効性チェックが行われます。
• debug_scanblock: デバッグ目的でメモリブロックをスキャンする関数。

技術的詳細

このコミットの核心は、MSpan.limitフィールドの役割を強化し、それをメモリ範囲チェックの主要な手段として利用することにあります。

1. MSpan.limitの正確な設定:

   • src/pkg/runtime/malloc.gocのruntime·mallocgc関数内で、sizeclass == 0（大きなアロケーション）の場合に、s->limit = (byte*)(s->start<<PageShift) + size;という行が追加されました。
   • これにより、大きなスパンが割り当てられる際に、そのスパンがカバーする正確なメモリ範囲の終了アドレスがs->limitに設定されるようになりました。以前は、このlimitが正しく設定されていなかったか、または利用されていなかった可能性があります。s->start<<PageShiftはスパンの開始バイトアドレスを、sizeはそのスパンに割り当てられたオブジェクトのバイトサイズを示します。この二つを合計することで、スパンの有効なメモリ範囲の終端が正確に計算されます。

2. 境界チェックの最適化と簡素化:

   • src/pkg/runtime/malloc.goc (runtime·mlookup):
     • 以前存在した冗長なチェック if((byte*)v >= (byte*)s->limit) が削除されました。これは、s->limitが常に正確であるという新しい前提に基づいています。runtime·mlookupは、与えられたポインタvがどのMSpanに属するかを判断する関数であり、この変更により、ポインタがスパンの範囲外である場合のチェックがより効率的になります。
   • src/pkg/runtime/mgc0.c (markonly, flushptrbuf, debug_scanblock):
     • これらの関数では、ポインタobjが有効なヒープオブジェクトを指しているか、特定のスパンの範囲内にあるかを確認する際に、s->limitが活用されるようになりました。
     • 特に、k - s->start >= s->npagesという、ページ数に基づく範囲チェックが、より直接的なobj >= s->limitというバイトアドレスに基づくチェックに置き換えられました。これは、s->limitがスパンの有効な終端を正確に表すようになったため可能になりました。
     • また、これらの関数内にあったif((byte*)obj >= (byte*)s->limit)のような冗長なチェックも削除されました。これは、MSpan.limitがMHeap_LookupMaybeのような上位レベルの関数で既に適切にチェックされているため、下位レベルの関数で再度チェックする必要がなくなったことを示唆しています。
   • src/pkg/runtime/mheap.c (runtime·MHeap_LookupMaybe):
     • if(s == nil || p < s->start || p - s->start >= s->npages)という条件が、if(s == nil || p < s->start || v >= s->limit || s->state != MSpanInUse)に変更されました。
     • ここでも、p - s->start >= s->npagesというページ数に基づくチェックが、v >= s->limitというバイトアドレスに基づくチェックに置き換えられています。これは、MHeap_LookupMaybeがポインタvが属するスパンを特定する際に、s->limitを直接利用して効率的に境界を判断できるようになったことを意味します。

この変更により、Goランタイムはポインタの有効性をより効率的に判断できるようになり、特にガベージコレクションのパフォーマンス向上に寄与します。MSpan.limitを信頼できる単一の情報源とすることで、コードの重複が減り、保守性も向上します。

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

src/pkg/runtime/malloc.goc

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -84,6 +84,7 @@ runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
 		s = runtime·MHeap_Alloc(&runtime·mheap, npages, 0, 1, zeroed);
 		if(s == nil)
 			runtime·throw("out of memory");
+		s->limit = (byte*)(s->start<<PageShift) + size;
 		size = npages<<PageShift;
 		c->local_alloc += size;
 		c->local_total_alloc += size;
@@ -238,11 +239,6 @@ runtime·mlookup(void *v, byte **base, uintptr *size, MSpan **sp)
 		return 1;
 	}
 
-	if((byte*)v >= (byte*)s->limit) {
-		// pointers past the last block do not count as pointers.
-		return 0;
-	}
-
 	n = s->elemsize;
 	if(base) {
 		i = ((byte*)v - p)/n;

src/pkg/runtime/mgc0.c

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -231,14 +231,12 @@ markonly(void *obj)
 	if(sizeof(void*) == 8)
 		x -= (uintptr)runtime·mheap.arena_start>>PageShift;
 	s = runtime·mheap.spans[x];
-	if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
+	if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse)
 		return false;
 	p = (byte*)((uintptr)s->start<<PageShift);
 	if(s->sizeclass == 0) {
 		obj = p;
 	} else {
-		if((byte*)obj >= (byte*)s->limit)
-			return false;
 		uintptr size = s->elemsize;
 		int32 i = ((byte*)obj - p)/size;
 		obj = p+i*size;
@@ -411,14 +409,12 @@ flushptrbuf(PtrTarget *ptrbuf, PtrTarget **ptrbufpos, Obj **_wp, Workbuf **_wbuf
 			if(sizeof(void*) == 8)
 				x -= (uintptr)arena_start>>PageShift;
 			s = runtime·mheap.spans[x];
-			if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
+			if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse)
 				continue;
 			p = (byte*)((uintptr)s->start<<PageShift);
 			if(s->sizeclass == 0) {
 				obj = p;
 			} else {
-				if((byte*)obj >= (byte*)s->limit)
-					continue;
 				size = s->elemsize;
 				int32 i = ((byte*)obj - p)/size;
 				obj = p+i*size;
@@ -1173,8 +1169,6 @@ debug_scanblock(byte *b, uintptr n)
 		if(s->sizeclass == 0) {
 			obj = p;
 		} else {
-			if((byte*)obj >= (byte*)s->limit)
-				continue;
 			int32 i = ((byte*)obj - p)/size;
 			obj = p+i*size;
 		}

src/pkg/runtime/mheap.c

--- a/src/pkg/runtime/mheap.c
+++ b/src/pkg/runtime/mheap.c
@@ -303,9 +303,7 @@ runtime·MHeap_LookupMaybe(MHeap *h, void *v)
 	if(sizeof(void*) == 8)
 		q -= (uintptr)h->arena_start >> PageShift;
 	s = h->spans[q];
-	if(s == nil || p < s->start || p - s->start >= s->npages)
-		return nil;
-	if(s->state != MSpanInUse)
+	if(s == nil || p < s->start || v >= s->limit || s->state != MSpanInUse)
 		return nil;
 	return s;
 }

コアとなるコードの解説

src/pkg/runtime/malloc.goc

• runtime·mallocgc関数内の追加行:

  +		s->limit = (byte*)(s->start<<PageShift) + size;
  

  この行は、runtime·mallocgcが大きなオブジェクト（sizeclass == 0）のために新しいMSpanを割り当てる際に、そのMSpanのlimitフィールドを正確に設定します。s->start<<PageShiftはスパンの開始バイトアドレスを計算し、それに割り当てられたsize（バイト単位）を加えることで、スパンがカバーするメモリ範囲の正確な終了アドレスをs->limitに格納します。これにより、MSpan.limitが常に信頼できる境界情報を持つようになります。

• runtime·mlookup関数内の削除行:

  -	if((byte*)v >= (byte*)s->limit) {
  -		// pointers past the last block do not count as pointers.
  -		return 0;
  -	}
  

  runtime·mlookupは、与えられたポインタvがどのMSpanに属するかをルックアップする関数です。MSpan.limitがruntime·mallocgcで正確に設定されるようになったため、この冗長な境界チェックは不要になりました。ポインタがスパンの範囲外であるかどうかのチェックは、runtime·MHeap_LookupMaybeのような上位レベルの関数でより効率的に行われるようになりました。

src/pkg/runtime/mgc0.c

• markonly、flushptrbuf、debug_scanblock関数内の条件変更:

  -	if(s == nil || k < s->start || k - s->start >= s->npages || s->state != MSpanInUse)
  +	if(s == nil || k < s->start || obj >= s->limit || s->state != MSpanInUse)
  

  これらのガベージコレクション関連の関数では、ポインタobjが有効なヒープオブジェクトを指しているか、特定のスパンの範囲内にあるかを確認する際に、条件が変更されました。以前はk - s->start >= s->npagesという、ページ数に基づく計算と比較が行われていましたが、MSpan.limitが正確になったことで、より直接的なobj >= s->limitというバイトアドレスに基づく比較に置き換えられました。これは、計算量を減らし、チェックをより効率的にします。

• markonly、flushptrbuf、debug_scanblock関数内の削除行:

  -		if((byte*)obj >= (byte*)s->limit)
  -			return false; // or continue;
  

  これらの関数内にあった、MSpan.limitを用いた冗長な境界チェックが削除されました。これは、runtime·MHeap_LookupMaybeなどの上位レベルの関数で既にs->limitが適切にチェックされているため、これらの下位レベルの関数で再度チェックする必要がなくなったためです。これにより、コードの重複が解消され、簡潔性が向上します。

src/pkg/runtime/mheap.c

• runtime·MHeap_LookupMaybe関数内の条件変更:

  -	if(s == nil || p < s->start || p - s->start >= s->npages)
  -		return nil;
  -	if(s->state != MSpanInUse)
  +	if(s == nil || p < s->start || v >= s->limit || s->state != MSpanInUse)
  		return nil;
  

  runtime·MHeap_LookupMaybeは、与えられたポインタvがどのMSpanに属するかをルックアップする重要な関数です。ここでも、p - s->start >= s->npagesというページ数に基づくチェックが、v >= s->limitというバイトアドレスに基づくチェックに置き換えられました。これにより、ポインタがスパンの有効な範囲内にあるかどうかの判断が、MSpan.limitを直接参照することで、より高速かつシンプルに行えるようになりました。また、s->state != MSpanInUseのチェックが前の条件と統合され、よりコンパクトな表現になっています。

これらの変更は、Goランタイムのメモリ管理におけるポインタの境界チェックを全体的に最適化し、パフォーマンスを向上させるとともに、コードの可読性と保守性を高める効果があります。

関連リンク

• Goのメモリ管理に関する公式ドキュメントやブログ記事 (当時のものがあれば)
• Goのガベージコレクションに関する詳細な解説
• Goランタイムのソースコードリポジトリ

参考にした情報源リンク

• Goのメモリ管理について (日本語記事) (一般的なGoメモリ管理の概念理解のため)
• Goのガベージコレクションについて (日本語記事) (一般的なGo GCの概念理解のため)
• golang/go GitHub Repository (ソースコードの参照)
• Go CL 9869045 (元のコードレビューへのリンク)
• Go runtime source code (malloc.goc) (現在のmalloc.goの参照、当時のmalloc.gocとは異なる可能性あり)
• Go runtime source code (mgc.go) (現在のmgc.goの参照、当時のmgc0.cとは異なる可能性あり)
• Go runtime source code (mheap.go) (現在のmheap.goの参照、当時のmheap.cとは異なる可能性あり)

注記: 上記の参考リンクは、コミット当時のファイル名（.goc, .c）とは異なる現在のGoランタイムのファイル名（.go）に基づいています。Goランタイムの進化に伴い、ファイル名や実装が変更されている可能性があるため、当時の正確なコンテキストを把握するには、コミット時のソースコードを参照する必要があります。