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

このコミットは、Goランタイムにおけるunion型をstruct型に置き換える変更を導入しています。主な目的は、union型がGoの正確なガベージコレクション（Precise GC）を妨げる可能性があったため、その問題を解決することです。具体的には、src/pkg/runtime/atomic_arm.cとsrc/pkg/runtime/sema.gocの2つのファイルで変更が行われました。

コミット

• コミットハッシュ: 60682c4f596803f102ae8694f790995d1e99c273
• Author: Dmitriy Vyukov dvyukov@google.com
• Date: Sat Apr 6 20:02:49 2013 -0700
• 変更ファイル:
  • src/pkg/runtime/atomic_arm.c: 2行追加, 2行削除
  • src/pkg/runtime/sema.goc: 3行追加, 3行削除
• 合計: 2ファイル変更, 5挿入(+), 5削除(-)

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

https://github.com/golang/go/commit/60682c4f596803f102ae8694f790995d1e99c273

元コミット内容

runtime: replace unions with structs
Unions can break precise GC.
Update #5193.

R=golang-dev, iant
CC=golang-dev
https://golang.org/cl/8456043

変更の背景

このコミットの主要な背景は、Go言語のランタイムにおけるガベージコレクション（GC）の正確性に関する問題です。元のコミットメッセージに「Unions can break precise GC.」と明記されている通り、C言語のunion型がGoの正確なGCの動作を妨げる可能性がありました。

GoのGCは、ヒープ上のオブジェクトがどこから参照されているかを正確に追跡することで、到達可能なオブジェクトを特定し、到達不能なオブジェクトを解放します。この「正確な」追跡は、ポインタと非ポインタデータを区別できることを前提としています。

union型は、異なる型のメンバーが同じメモリ領域を共有することを可能にします。これにより、ある時点では整数として扱われていたメモリ領域が、別の時点ではポインタとして扱われる可能性があります。GCがメモリをスキャンする際、このunionの性質により、どのメンバーが現在アクティブであるかを判断するのが困難になります。もしGCが誤って非ポインタデータをポインタとして解釈し、その「ポインタ」が不正なアドレスを指していた場合、GCはクラッシュしたり、誤ったメモリを解放してデータ破損を引き起こしたりする可能性があります。

この問題は、Go issue #5193で議論されていました。このissueでは、unionの使用がGCの正確性を損なう可能性が指摘され、特にクロスコンパイル環境や特定のアーキテクチャ（ARMなど）で問題が顕在化することが示唆されていました。このコミットは、その問題に対する直接的な解決策として、unionをstructに置き換えることで、メモリレイアウトを明確にし、GCがポインタを正確に識別できるようにすることを目的としています。

前提知識の解説

ガベージコレクション (GC) と正確なGC (Precise GC)

• ガベージコレクション (GC): プログラムが動的に確保したメモリ領域のうち、もはや使用されていない（到達不能な）ものを自動的に解放する仕組みです。プログラマが手動でメモリを解放する手間を省き、メモリリークなどのバグを防ぐのに役立ちます。
• 正確なGC (Precise GC): GCの一種で、メモリ領域内のどの値が実際にポインタであるかを正確に識別できるGCを指します。これにより、GCはポインタが指すオブジェクトのみを追跡し、非ポインタデータを誤ってポインタとして解釈することによる問題を回避できます。GoのGCは基本的に正確なGCを目指しています。対義語として「保守的なGC (Conservative GC)」があり、これはメモリ領域内のすべての値をポインタである可能性があると仮定してスキャンします。保守的なGCは実装が容易ですが、誤って非ポインタデータをポインタと解釈し、到達不能なメモリを解放できない（メモリリーク）などの問題を引き起こす可能性があります。

C言語の union と struct

• struct (構造体): 複数の異なる型のメンバーをまとめた複合データ型です。各メンバーはそれぞれ異なるメモリ領域を占有し、メモリ上では連続して配置されます（パディングによって隙間ができることもあります）。

  struct MyStruct {
      int a;
      char b;
      float c;
  };
  

  この場合、a, b, cはそれぞれ独立したメモリ領域を持ちます。
• union (共用体): 複数の異なる型のメンバーをまとめた複合データ型ですが、すべてのメンバーが同じメモリ領域を共有します。unionのサイズは、その中で最も大きいメンバーのサイズによって決まります。一度にアクティブにできるメンバーは1つだけです。

  union MyUnion {
      int i;
      float f;
      char c;
  };
  

  この場合、i, f, cはすべて同じメモリ領域を共有します。iに値を書き込むと、そのメモリ領域がintとして解釈され、次にfに値を書き込むと、同じメモリ領域がfloatとして解釈されます。

CacheLineSize とパディング

• キャッシュライン (Cache Line): CPUのキャッシュメモリがデータを読み書きする際の最小単位です。通常、32バイト、64バイト、128バイトなどの固定サイズです。CPUはメモリからデータを読み込む際、要求されたデータだけでなく、そのデータを含むキャッシュライン全体を読み込みます。
• パディング (Padding): 構造体や配列のメンバーが特定のメモリ境界にアラインされるように、コンパイラが自動的に挿入する未使用のバイトのことです。これは、CPUが効率的にメモリにアクセスできるようにするために行われます。例えば、CacheLineSizeの倍数にアラインすることで、キャッシュラインの境界をまたぐアクセス（False Sharingなど）を避けることができます。
• byte pad[CacheLineSize]: これは、構造体や共用体のサイズをCacheLineSizeの倍数に拡張し、次のデータが新しいキャッシュラインの先頭から始まるようにするための一般的なテクニックです。これにより、異なるCPUコアが異なるデータにアクセスする際に、意図せず同じキャッシュラインを共有してしまう「False Sharing」というパフォーマンス問題を回避できます。
• byte pad[CacheLineSize-sizeof(Lock)] / uint8 pad[CacheLineSize-sizeof(SemaRoot)]: これは、構造体や共用体の最初のメンバーの後に、残りのキャッシュラインを埋めるためのパディングです。例えば、Lock構造体のサイズがCacheLineSizeよりも小さい場合、残りのバイトをpadで埋めることで、locktab配列の各要素がキャッシュラインの先頭から始まるようにします。これにより、配列の要素が常に異なるキャッシュラインに配置され、並行処理におけるキャッシュ競合を減らすことができます。

技術的詳細

このコミットの技術的な核心は、GoランタイムがC言語のunion型をどのように扱っていたか、そしてそれが正確なGCにどのような影響を与えていたかという点にあります。

Goランタイムは、C言語で書かれた部分（特に低レベルなメモリ管理やスケジューラなど）とGo言語で書かれた部分が混在しています。C言語のコードでは、メモリ効率や特定のハードウェア特性を考慮してunionが使用されることがありました。しかし、GoのGCは、ヒープ上のオブジェクトをスキャンする際に、どのメモリ領域がポインタを含んでいるかを正確に知る必要があります。

unionを使用すると、同じメモリ領域が異なる型として解釈される可能性があるため、GCがその領域をスキャンする際に、それがポインタであるか非ポインタであるかを確実に判断することが困難になります。例えば、unionのあるメンバーが整数型で、別のメンバーがポインタ型である場合、GCがそのunionのメモリ領域をスキャンする際に、現在アクティブなメンバーがどちらであるかを判断できなければ、誤って整数値をポインタとして解釈してしまう可能性があります。このような誤解釈は、GCが不正なメモリアドレスを追跡しようとしてクラッシュしたり、本来解放すべきでないメモリを解放してデータ破損を引き起こしたりする原因となります。

このコミットでは、unionをstructに置き換えることで、この問題を解決しています。structでは、各メンバーが明確に異なるメモリ領域を占有するため、GCは各メンバーの型情報を利用して、それがポインタであるかどうかを正確に判断できます。

具体的には、以下の変更が行われています。

1. unionからstructへの変更:

   • static union { Lock l; byte pad [CacheLineSize]; } locktab[57]; を static struct { Lock l; byte pad[CacheLineSize-sizeof(Lock)]; } locktab[57]; に変更。
   • union semtable { SemaRoot; uint8 pad[CacheLineSize]; }; を struct semtable { SemaRoot; uint8 pad[CacheLineSize-sizeof(SemaRoot)]; }; に変更。
   • static union semtable semtable[SEMTABLESZ]; を static struct semtable semtable[SEMTABLESZ]; に変更。

2. パディングの調整: 元のunionでは、CacheLineSize全体をパディングとして確保していました。これは、unionのサイズが最大メンバーのサイズに依存するため、LockやSemaRootのサイズがCacheLineSizeより小さい場合でも、union全体のサイズをCacheLineSizeに揃えるためでした。 structに置き換えることで、LockやSemaRootが独立したメンバーとなり、その後に残りのキャッシュラインを埋めるためのパディングが必要になります。そのため、パディングのサイズがCacheLineSize - sizeof(Lock)やCacheLineSize - sizeof(SemaRoot)に調整されています。これにより、各構造体のインスタンスがキャッシュラインの先頭から始まり、かつキャッシュライン全体を占有するように配置され、False Sharingなどのパフォーマンス問題を回避しつつ、メモリレイアウトの明確性を保っています。

この変更により、GoのGCはこれらのデータ構造内のポインタをより確実に識別できるようになり、ランタイムの安定性と正確性が向上しました。

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

src/pkg/runtime/atomic_arm.c

--- a/src/pkg/runtime/atomic_arm.c
+++ b/src/pkg/runtime/atomic_arm.c
@@ -5,9 +5,9 @@
 #include "runtime.h"
 #include "arch_GOARCH.h"
 
-static union {
+static struct {
 	Lock l;
-	byte pad [CacheLineSize];
+	byte pad[CacheLineSize-sizeof(Lock)];
 } locktab[57];
 
 #define LOCK(addr) (&locktab[((uintptr)(addr)>>3)%nelem(locktab)].l)

src/pkg/runtime/sema.goc

--- a/src/pkg/runtime/sema.goc
+++ b/src/pkg/runtime/sema.goc
@@ -44,13 +44,13 @@ struct SemaRoot
 // Prime to not correlate with any user patterns.
 #define SEMTABLESZ 251
 
-union semtable
+struct semtable
 {
 	SemaRoot;
-	uint8 pad[CacheLineSize];
+	uint8 pad[CacheLineSize-sizeof(SemaRoot)];
 };
 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage collector */
-static union semtable semtable[SEMTABLESZ];
+static struct semtable semtable[SEMTABLESZ];
 
 static SemaRoot*
 semroot(uint32 *addr)

コアとなるコードの解説

src/pkg/runtime/atomic_arm.c の変更

このファイルは、ARMアーキテクチャにおけるアトミック操作に関連するランタイムコードを含んでいます。変更箇所はlocktabという配列の定義です。

• 変更前:

  static union {
      Lock l;
      byte pad [CacheLineSize];
  } locktab[57];
  

  ここでは、Lock型のメンバーlと、CacheLineSize分のパディングを持つunionが定義されていました。このunionは、lとpadが同じメモリ領域を共有することを意味します。locktabは、アトミック操作の際に使用されるロックを管理するためのテーブルです。

• 変更後:

  static struct {
      Lock l;
      byte pad[CacheLineSize-sizeof(Lock)];
  } locktab[57];
  

  unionがstructに置き換えられました。これにより、lとpadは異なるメモリ領域を占有するようになります。padのサイズはCacheLineSize - sizeof(Lock)に変更され、Lock構造体の直後に残りのキャッシュラインを埋めるように調整されています。 この変更により、locktabの各要素が明確なメモリレイアウトを持つようになり、GCがLock構造体内のポインタ（もしあれば）を正確に識別できるようになります。また、各ロックが異なるキャッシュラインに配置されることで、並行アクセス時のキャッシュ競合（False Sharing）を軽減し、パフォーマンスを向上させる効果も期待できます。

src/pkg/runtime/sema.goc の変更

このファイルは、Goランタイムにおけるセマフォ（同期プリミティブ）の実装に関連するコードを含んでいます。変更箇所はsemtableという構造体の定義と、その配列の定義です。

• 変更前:

  union semtable
  {
      SemaRoot;
      uint8 pad[CacheLineSize];
  };
  // ...
  static union semtable semtable[SEMTABLESZ];
  

  ここでは、SemaRoot型のメンバーと、CacheLineSize分のパディングを持つunionが定義されていました。SemaRootはセマフォのルート構造体であり、ポインタを含む可能性があります。

• 変更後:

  struct semtable
  {
      SemaRoot;
      uint8 pad[CacheLineSize-sizeof(SemaRoot)];
  };
  // ...
  static struct semtable semtable[SEMTABLESZ];
  

  ここでもunionがstructに置き換えられました。SemaRootとpadは異なるメモリ領域を占有し、padのサイズはCacheLineSize - sizeof(SemaRoot)に調整されています。 この変更により、semtable配列の各要素が明確なメモリレイアウトを持つようになり、GCがSemaRoot内のポインタを正確に識別できるようになります。セマフォは並行処理において頻繁にアクセスされるため、そのデータ構造のメモリレイアウトがGCの正確性とパフォーマンスに与える影響は大きいです。structへの変更は、GCの正確性を保証し、ランタイムの安定性を高める上で重要な役割を果たします。

両方の変更において、unionからstructへの置き換えは、Goの正確なGCがポインタを確実に識別できるようにするためのものです。パディングの調整は、キャッシュラインアラインメントを維持し、並行処理におけるパフォーマンス問題を回避するためのものです。

関連リンク

• Go issue #5193: https://github.com/golang/go/issues/5193
• Go CL 8456043: https://golang.org/cl/8456043 (これは元のコミットメッセージに記載されているGo Code Reviewのリンクです)
• Goのガベージコレクションに関する公式ドキュメント（当時のバージョンに近いもの、または一般的な概念）:
  • A Guide to the Go Garbage Collector: https://go.dev/doc/gc-guide (現在のドキュメントですが、GCの基本的な概念を理解するのに役立ちます)
• C言語のunionとstructに関する一般的な情報:
  • C言語の構造体と共用体: https://ja.wikipedia.org/wiki/%E6%A7%8B%E9%80%A0%E4%BD%93_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)
  • C言語の共用体: https://ja.wikipedia.org/wiki/%E5%85%B1%E7%94%A8%E4%BD%93)
• キャッシュラインとFalse Sharingに関する情報:
  • False Sharing: https://ja.wikipedia.org/wiki/False_sharing

参考にした情報源リンク

• Go issue #5193: https://github.com/golang/go/issues/5193
• Go CL 8456043: https://golang.org/cl/8456043
• Goのガベージコレクションに関する一般的な知識 (Go公式ドキュメント、ブログ記事など)
• C言語のunionとstructに関する一般的な知識 (C言語の教科書、オンラインリソースなど)
• CPUキャッシュとメモリパディング、False Sharingに関する一般的な知識 (コンピュータアーキテクチャの教科書、オンラインリソースなど)
• Google検索: "Go precise GC unions", "Go issue 5193", "CacheLineSize padding"