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

このコミットは、Goランタイムのガベージコレクタ（GC）の中核部分である src/pkg/runtime/mgc0.c ファイルに大幅な変更を加えるものです。主な目的は、GCの精度を向上させるための基盤を構築することにあります。具体的には、メモリブロックを表す Obj 構造体の定義を拡張し、scanblock 関数におけるポインタ走査のメカニズムを刷新しています。これにより、将来的にオブジェクトの型情報を利用したより精密なGCを実現するための準備が行われています。

コミット

commit 013fa63c901e4a08548821bcc46393584b8c701e
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Sun Dec 16 19:32:12 2012 -0500

    runtime: struct Obj in mgc0.c and buffers in scanblock()
    
    Details:
    
    - This CL is the conceptual skeleton of code found in CL 6114046
    
    - The garbage collector uses struct Obj to specify memory blocks
    
    - scanblock() is putting found memory blocks into an intermediate buffer
      (xbuf) before adding/flushing them to the main work buffer (wbuf)
    
    - The main loop in scanblock() is replaced with a skeleton code that
      in the future will be able to recognize the type of objects and
      thus will improve the garbage collector's precision.
      For now, all objects are simply sequences of pointers so
      the precision of the garbage collector remains unchanged.
    
    - The code plugs .gcdata and .gcbss sections into the garbage collector.
      scanblock() in this CL is unable to make any use of this.
    
    R=rsc, dvyukov, remyoudompheng
    CC=dave, golang-dev, minux.ma
    https://golang.org/cl/6856121

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

https://github.com/golang/go/commit/013fa63c901e4a08548821bcc46393584b8c701e

元コミット内容

上記の「コミット」セクションに記載されている内容が元コミット内容です。

変更の背景

このコミットの背景には、Go言語のガベージコレクタの進化があります。当時のGoのGCは、主に「マーク＆スイープ」方式を採用していましたが、その精度（どのメモリがポインタを含み、どのメモリがそうでないかを正確に識別する能力）には改善の余地がありました。特に、オブジェクトの内部構造に関する型情報がGCに十分に活用されていませんでした。

このコミットは、より「正確な（precise）」GCを実現するための重要なステップです。正確なGCは、ポインタではないデータ（例えば、整数や文字列のバイト列）をポインタとして誤って解釈し、到達可能なオブジェクトとしてマークしてしまう「保守的な（conservative）」GCの問題を解決します。保守的なGCは、誤ってメモリを解放しないという安全性は高いものの、不要なメモリを保持し続けることでメモリ使用量が増加する可能性があります。

この変更では、Obj 構造体に型情報（tiフィールド）を導入し、scanblock 関数がこの型情報を利用して、メモリブロック内のどこにポインタが存在するかを正確に識別できるようにするための基盤を構築しています。また、.gcdata および .gcbss セクション（コンパイル時に生成される、ポインタの配置に関するメタデータを含むセクション）をGCに統合することで、プログラムの静的な型情報をGCプロセスに提供する道を開いています。

コミットメッセージに記載されている「CL 6114046の概念的な骨格」という記述は、この変更がより大きなGC改善計画の一部であることを示唆しています。ただし、このCL 6114046に関する具体的な情報は、現在の検索では見つかりませんでした。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムおよびガベージコレクションに関する前提知識が必要です。

1. Goのガベージコレクション (GC):

   • GoのGCは、主に「マーク＆スイープ」アルゴリズムに基づいています。これは、プログラムが使用しているオブジェクト（到達可能なオブジェクト）をマークし、マークされていないオブジェクト（到達不可能なオブジェクト、つまり不要なメモリ）を解放するプロセスです。
   • マークフェーズ: ルート（グローバル変数、スタック、レジスタなど）から開始し、到達可能なすべてのオブジェクトをたどってマークします。
   • スイープフェーズ: ヒープ全体を走査し、マークされていないオブジェクトを解放します。
   • 並行GC: GoのGCは、アプリケーションの実行と並行して動作するように設計されており、アプリケーションの一時停止（ストップ・ザ・ワールド）時間を最小限に抑えることを目指しています。

2. src/pkg/runtime/mgc0.c:

   • GoランタイムのC言語で書かれた部分で、ガベージコレクタの主要なロジックが含まれています。mgc は "memory garbage collection" を意味します。

3. scanblock 関数:

   • GCのマークフェーズにおいて、特定のメモリブロックを走査し、その中に含まれるポインタを識別して、それらが指すオブジェクトをマークするための関数です。この関数がGCの精度に直接影響を与えます。

4. Workbuf (Work Buffer):

   • GCのマークフェーズ中に、走査すべきオブジェクトのポインタを一時的に格納するためのバッファです。GCワーカーゴルーチンは、このバッファからオブジェクトを取り出し、走査し、新しい到達可能なオブジェクトをバッファに追加します。

5. .gcdata および .gcbss セクション:

   • Goのコンパイラは、実行可能ファイル内に特別なセクションを生成します。
   • .gcdata: データセクション（初期化されたグローバル変数など）内のポインタに関するメタデータを含みます。
   • .gcbss: BSSセクション（初期化されていないグローバル変数など）内のポインタに関するメタデータを含みます。
   • これらのセクションは、GCがプログラムの静的な部分（グローバル変数など）を正確に走査するために使用されます。

6. ポインタサイズ (PtrSize):

   • システムアーキテクチャ（32ビットまたは64ビット）に応じて、ポインタのサイズ（4バイトまたは8バイト）を定義する定数です。

7. MSpan:

   • Goのメモリ管理において、ヒープメモリはページ（通常8KB）の連続したブロックである「スパン（span）」に分割されます。MSpan 構造体は、これらのスパンに関する情報（開始アドレス、ページ数、サイズクラスなど）を保持します。

8. runtime·casp (Compare-and-Swap Pointer):

   • アトミック操作の一つで、特定のメモリ位置の現在の値が期待する値と一致する場合にのみ、そのメモリ位置を新しい値で更新します。並行処理において、ロックなしで共有データを安全に操作するために使用されます。

技術的詳細

このコミットは、Goのガベージコレクタの内部構造にいくつかの重要な変更を導入しています。

1. Obj 構造体の導入と GcRoot の置き換え:

   • 以前は GcRoot 構造体がポインタとサイズ (p, n) を保持していましたが、これを Obj 構造体に置き換えました。
   • Obj 構造体には新たに ti (type info) フィールドが追加されました。これは uintptr 型で、将来的にオブジェクトの型情報を格納するために使用されます。これにより、GCがオブジェクトの内部構造を理解し、どこにポインタがあるかを正確に判断できるようになります。

2. 中間バッファ (PtrTarget, BitTarget, BufferList) の導入:

   • scanblock 関数がポインタを走査する際に、直接 Workbuf に追加するのではなく、PtrTarget と BitTarget という2種類の中間バッファを使用するようになりました。
   • PtrTarget: ポインタとその型情報 (p, ti) を保持します。
   • BitTarget: ポインタ、型情報、およびそのポインタがヒープビットマップのどこに対応するかを示す情報 (bitp, shift) を保持します。
   • BufferList: これらの PtrTarget と BitTarget の配列を保持し、GCワーカー間でバッファを再利用するためのリンクリストとして機能します。
   • これらのバッファは IntermediateBufferCapacity (64要素) という小さなサイズで定義されており、GCの効率を向上させるための工夫です。

3. flushptrbuf 関数の追加:

   • この新しい関数は、PtrTarget バッファから BitTarget バッファへ、そして最終的にメインの Workbuf へとポインタを移動させる役割を担います。
   • PtrTarget バッファ内のポインタを走査し、それがヒープ内の有効なオブジェクトの開始点であるかを判断します。
   • 有効なオブジェクトであれば、そのオブジェクトに対応するヒープビットマップのビットをマークし、Workbuf に追加します。
   • この関数は、ポインタのマークとキューイングのロジックをカプセル化し、scanblock の複雑さを軽減しています。

4. scanblock 関数の大幅な改修:

   • 関数のシグネチャが変更され、直接メモリブロック (byte *b, uintptr n) を受け取るのではなく、Workbuf の状態 (Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking) を受け取るようになりました。これは、scanblock がより高レベルのGCロジックの一部として機能するようになったことを示しています。
   • 内部の走査ループが完全に書き直され、PtrTarget と BitTarget を使用した新しい中間バッファリングメカニズムが導入されました。
   • GC_DEFAULT_PTR と defaultProg という概念が導入されていますが、コミットメッセージにあるように、この時点ではまだ「スケルトンコード」であり、オブジェクトの型を認識する機能は将来のCLで拡張される予定です。
   • flush_buffers というラベルと、そこで flushptrbuf が呼び出されることで、中間バッファのフラッシュ処理が明確に定義されています。

5. enqueue 関数の追加:

   • Obj を Workbuf に追加するためのヘルパー関数です。ポインタのアライメント調整や、handoff (他のGCワーカーへの作業の引き渡し) のロジックを含んでいます。

6. ルート走査の変更 (addroot, addstackroots, addfinroots, addroots):

   • すべてのルート（スタック、ファイナライザ、グローバル変数など）が Obj 構造体を使用してGCに登録されるようになりました。
   • 特に、addroots 関数では、data セクションと bss セクションが Obj として追加され、それぞれ gcdata と gcbss のアドレスが型情報 (ti) として渡されています。これは、これらの静的メモリ領域のポインタ情報をGCが利用できるようにするための重要な変更です。

これらの変更は、GoのGCがより正確なポインタ識別を行い、メモリ使用量を最適化し、将来的なGCアルゴリズムの改善（例えば、コンカレントなスイープや世代別GCなど）のための強固な基盤を築くことを目的としています。

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

このコミットにおけるコアとなるコードの変更箇所は、主に以下のファイルとセクションに集中しています。

• src/pkg/runtime/mgc0.c:
  • Obj 構造体の定義（新規追加）
  • Workbuf 構造体の変更（obj フィールドの型変更）
  • PtrTarget, BitTarget, BufferList 構造体の定義（新規追加）
  • flushptrbuf 関数の定義（新規追加）
  • scanblock 関数のシグネチャと内部ロジックの大幅な変更
  • enqueue 関数の定義（新規追加）
  • addroot 関数のシグネチャと内部ロジックの変更
  • addstackroots, addfinroots, addroots 関数における Obj 構造体の使用

コアとなるコードの解説

以下に、主要な変更点とそのコードを抜粋して解説します。

1. Obj 構造体の定義:

   typedef struct Obj Obj;
   struct Obj
   {
       byte    *p; // data pointer
       uintptr n;  // size of data in bytes
       uintptr ti; // type info
   };
   

   この新しい構造体は、GCが扱うメモリブロックの基本単位となります。p はデータへのポインタ、n はデータのサイズ、そして最も重要なのが ti (type info) です。この ti フィールドは、そのメモリブロックがどのような型情報を持っているかを示すもので、将来的にGCがポインタの場所を正確に特定するために使用されます。

2. Workbuf 構造体の変更:

   typedef struct Workbuf Workbuf;
   struct Workbuf
   {
   #define SIZE (2*PageSize-sizeof(LFNode)-sizeof(uintptr))
       LFNode  node; // must be first
       uintptr nobj;
       Obj     obj[SIZE/sizeof(Obj) - 1]; // byte* から Obj に変更
       uint8   _padding[SIZE%sizeof(Obj) + sizeof(Obj)];
   #undef SIZE
   };
   

   Workbuf はGCが走査すべきオブジェクトのキューとして機能します。以前は byte *obj[] で生ポインタを格納していましたが、この変更により Obj obj[] となり、ポインタだけでなくサイズや型情報もまとめて管理できるようになりました。

3. 中間バッファ構造体 (PtrTarget, BitTarget, BufferList):

   struct PtrTarget
   {
       void *p;
       uintptr ti;
   };
   
   struct BitTarget
   {
       void *p;
       uintptr ti;
       uintptr *bitp, shift;
   };
   
   struct BufferList
   {
       struct PtrTarget ptrtarget[IntermediateBufferCapacity];
       struct BitTarget bittarget[IntermediateBufferCapacity];
       struct BufferList *next;
   };
   

   これらの中間バッファは、scanblock がポインタを走査する際の効率を向上させます。PtrTarget は見つかったポインタとその型情報を一時的に保持し、BitTarget はさらにヒープビットマップ上の位置情報も追加します。BufferList はこれらのバッファを管理し、再利用を可能にします。

4. flushptrbuf 関数の追加:

   static void
   flushptrbuf(struct PtrTarget *ptrbuf, uintptr n, Obj **_wp, Workbuf **_wbuf, uintptr *_nobj, struct BitTarget *bitbuf)
   {
       // ... (省略) ...
       // Multi-threaded version.
       bitbufpos = bitbuf;
       while(ptrbuf < ptrbuf_end) {
           obj = ptrbuf->p;
           ti = ptrbuf->ti;
           ptrbuf++;
   
           // ... (オブジェクトの開始位置とビットマップ情報の取得ロジック) ...
   
           // Mark the block
           *bt->bitp = xbits | (bitMarked << bt->shift);
   
           // If object has no pointers, don't need to scan further.
           if((bits & bitNoPointers) != 0)
               continue;
   
           obj = bt->p;
           *wp = (Obj){obj, s->elemsize, bt->ti}; // Obj 構造体として Workbuf に追加
           wp++;
           nobj++;
       }
       // ... (省略) ...
   }
   

   この関数は、PtrTarget バッファからポインタを取り出し、それが有効なオブジェクトの開始点であるかを判断し、ヒープビットマップにマークを付け、最終的に Obj 構造体として Workbuf に追加する一連の処理を行います。これにより、ポインタのマークとキューイングのロジックが scanblock から分離され、モジュール性が向上しています。

5. scanblock 関数の変更:

   static void
   scanblock(Workbuf *wbuf, Obj *wp, uintptr nobj, bool keepworking)
   {
       // ... (省略) ...
       // Allocate ptrbuf, bitbuf
       // ... (BufferList から中間バッファを取得するロジック) ...
   
       // ... (省略) ...
   
       for(;;) {
           // ... (省略) ...
           // TODO(atom): to be replaced in a next CL
           pc = defaultProg; // 現時点ではデフォルトの走査プログラムを使用
   
           // ... (省略) ...
   
           case GC_DEFAULT_PTR:
               while(true) {
                   // ... (ポインタの読み取りと arena_start/arena_used の範囲チェック) ...
                   if(obj >= arena_start && obj < arena_used) {
                       *ptrbufpos = (struct PtrTarget){obj, 0}; // PtrTarget に追加
                       ptrbufpos++;
                       if(ptrbufpos == ptrbuf_end)
                           goto flush_buffers; // バッファが満杯になったらフラッシュ
                   }
               }
           // ... (省略) ...
   
       flush_buffers:
           flushptrbuf(ptrbuf, ptrbufpos-ptrbuf, &wp, &wbuf, &nobj, bitbuf); // 中間バッファをフラッシュ
           ptrbufpos = ptrbuf;
           goto next_instr;
   
       next_block:
           // ... (Workbuf から次の Obj を取得するロジック) ...
           --wp;
           b = wp->p;
           n = wp->n;
           nobj--;
       }
       // ... (省略) ...
   }
   

   scanblock は、Workbuf から Obj を取得し、そのメモリブロックを走査します。走査中に見つかったポインタは、まず PtrTarget 中間バッファに追加され、バッファが満杯になると flushptrbuf を呼び出して Workbuf にフラッシュされます。この構造は、将来的に defaultProg の部分がオブジェクトの型情報 (ti) に基づいてより賢い走査ロジックに置き換えられることを想定しています。

6. addroots 関数の変更:

   static void
   addroots(void)
   {
       // ... (省略) ...
       // data & bss
       // TODO(atom): load balancing
       addroot((Obj){data, edata - data, (uintptr)gcdata}); // gcdata を ti として追加
       addroot((Obj){bss, ebss - bss, (uintptr)gcbss});     // gcbss を ti として追加
   
       // ... (省略) ...
   
       // stacks
       for(gp=runtime·allg; gp!=nil; gp=gp->alllink) {
           // ... (省略) ...
           addroot((Obj){sp, (byte*)stk - sp, 0}); // スタックルートも Obj として追加
       }
       // ... (省略) ...
   }
   

   addroots 関数は、GCのマークフェーズの開始点となる「ルート」を登録します。この変更により、data セクションと bss セクションが Obj 構造体として登録され、それぞれの ti フィールドに gcdata および gcbss のアドレスが渡されるようになりました。これは、これらの静的メモリ領域内のポインタをGCが正確に識別するために非常に重要です。スタックルートやファイナライザのルートも同様に Obj として登録されます。

これらの変更は、GoのGCがより詳細な型情報を利用して、メモリをより効率的かつ正確に管理するための基盤を構築するものです。

関連リンク

• Go Gerrit Change-ID: https://golang.org/cl/6856121
• GitHub上のコミットページ: https://github.com/golang/go/commit/013fa63c901e4a08548821bcc46393584b8c701e

参考にした情報源リンク

• Go言語のソースコード (src/pkg/runtime/mgc0.c)
• Go言語のガベージコレクションに関する一般的な知識
• コミットメッセージに記載されている情報

（注: コミットメッセージに記載されていた「CL 6114046」については、現在の検索では具体的な情報を見つけることができませんでした。）