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

このコミットは、Goランタイムにロックフリースタックの実装を追加するものです。具体的には、src/pkg/runtime/lfstack.c にロックフリースタックのコアロジックがC言語で記述され、src/pkg/runtime/lfstack_test.go にそのテストが追加されています。また、関連する型定義と関数宣言が src/pkg/runtime/runtime.h に、テスト用のエクスポートが src/pkg/runtime/export_test.go に追加されています。

コミット

commit a5dc7793c0fba8d6c81098248a4fc2e8b0ddad34
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu Apr 12 11:49:25 2012 +0400

    runtime: add lock-free stack
    This is factored out part of the:
    https://golang.org/cl/5279048/
    (parallel GC)
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5993043

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

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

元コミット内容

このコミットの元々の内容は、「runtime: add lock-free stack」であり、Goランタイムにロックフリースタックを追加することです。コミットメッセージには、これが並列GC（Garbage Collection）の一部として切り出されたものであることが明記されており、関連するGerritの変更リスト（https://golang.org/cl/5279048/ および https://golang.org/cl/5993043）が参照されています。

変更の背景

この変更の主な背景は、Goランタイムにおける並列ガベージコレクション（GC）の実現です。並列GCでは、複数のゴルーチン（またはスレッド）が同時にメモリの解放や再利用に関与します。このような並行処理環境において、データ構造へのアクセスを同期するために従来のロック機構（ミューテックスなど）を使用すると、パフォーマンスのボトルネックになったり、デッドロックのリスクが生じたりする可能性があります。

ロックフリーデータ構造は、アトミック操作（不可分な操作）とCPUの比較交換（Compare-And-Swap: CAS）命令を利用することで、ロックを使用せずに複数のスレッドが同時にデータ構造を安全に操作できるようにします。これにより、並列GCの効率とスケーラビリティを向上させることが可能になります。特に、GCがオブジェクトをスキャンしたり、再利用可能なメモリチャンクを管理したりする際に、ロックフリースタックのようなデータ構造が役立ちます。

前提知識の解説

1. ロックフリーデータ構造

ロックフリーデータ構造とは、ミューテックスやセマフォといった従来のロック機構を使用せずに、複数のスレッドが同時にアクセスしてもデータの一貫性と正確性を保証するデータ構造のことです。これにより、スレッド間の競合による待ち時間を減らし、並行処理のパフォーマンスを向上させることができます。

• 利点:
  • デッドロックの回避: ロックを使用しないため、デッドロックが発生しません。
  • スループットの向上: ロックの取得・解放に伴うオーバーヘッドがなく、スレッドがブロックされることが少ないため、高いスループットが期待できます。
  • リアルタイム性の向上: 予測可能な実行時間を提供しやすくなります。
• 課題:
  • 複雑性: 実装が非常に複雑で、正しく設計・実装することが難しいです。
  • ABA問題: ロックフリーアルゴリズムでよく遭遇する問題の一つです。ある値Aを読み込み、その後に別の値Bに変化し、さらに元の値Aに戻った場合、CAS操作では値がAに戻ったことを検出できません。これにより、誤った操作が行われる可能性があります。

2. スタック

スタックは、Last-In, First-Out (LIFO) の原則に従う線形データ構造です。要素はスタックの「トップ」に追加（プッシュ）され、スタックの「トップ」から削除（ポップ）されます。

3. アトミック操作とCAS (Compare-And-Swap)

• アトミック操作: 複数のCPU命令から構成される操作であっても、それが中断されることなく、単一の不可分な操作として実行されることを保証するものです。これにより、複数のスレッドが同時に同じデータにアクセスしても、データの破損を防ぎます。
• CAS (Compare-And-Swap): ロックフリープログラミングの基盤となるアトミック操作です。CASは3つの引数を取ります: メモリ位置のポインタ、期待される現在の値、新しい値。メモリ位置の現在の値が期待される値と一致する場合にのみ、そのメモリ位置を新しい値で更新し、成功を示すブール値を返します。一致しない場合は更新せず、失敗を示します。

4. ABA問題の対策

ABA問題は、ロックフリーアルゴリズムで頻繁に発生する問題です。このコミットでは、ポインタにカウンタ（pushcnt）を付加することでABA問題に対処しています。具体的には、ポインタの上位ビットにカウンタ値を格納し、CAS操作時にポインタ値だけでなくカウンタ値も比較することで、ポインタが同じ値に戻ったとしても、その間に変更があったことを検出できるようにしています。

5. Goランタイムと並列GC

• Goランタイム: Goプログラムの実行を管理するシステムです。これには、ゴルーチンのスケジューリング、メモリ管理（ガベージコレクションを含む）、チャネル通信などが含まれます。
• 並列GC: 複数のCPUコアやスレッドを利用してガベージコレクションを同時に実行する手法です。これにより、GCの一時停止時間（ストップ・ザ・ワールド時間）を短縮し、アプリケーションの応答性を向上させることができます。並列GCでは、複数のコレクタースレッドが同時にヒープを走査し、到達可能なオブジェクトをマークしたり、不要なオブジェクトを解放したりします。このプロセスにおいて、共有されるデータ構造（例えば、フリーリストやオブジェクトのキュー/スタック）への効率的かつ安全なアクセスが不可欠であり、ロックフリーデータ構造がその解決策となります。

技術的詳細

このコミットで追加されたロックフリースタックは、Goランタイムの内部で利用されることを想定しており、C言語で実装されています。主要な技術的特徴は以下の通りです。

1. ポインタとカウンタの結合:

   • lfstack.c のコードを見ると、PTR_BITS と PTR_MASK が定義されています。これは、ポインタ値とABAカウンタを単一の uint64 変数にパックするためのものです。
   • _64BIT 環境では、ポインタの下位 PTR_BITS (47ビット) が実際のポインタアドレスに使用され、残りの上位ビットが pushcnt (プッシュ回数カウンタ) として使用されます。これにより、CAS操作時にポインタが指すアドレスだけでなく、そのポインタが何回更新されたかという情報も同時に比較・更新できます。
   • new = (uint64)node|(((uint64)node->pushcnt)<<PTR_BITS); の行は、ノードのポインタと pushcnt を結合して新しいスタックヘッドの値を生成しています。

2. アトミック操作の利用:

   • runtime·atomicload64(head): スタックのヘッドをアトミックに読み込みます。
   • runtime·cas64(head, &old, new): スタックのヘッドをアトミックに比較・交換します。これはロックフリーアルゴリズムの核心であり、複数のスレッドが同時にスタックを操作しても競合状態を防ぎます。

3. プッシュ操作 (runtime·lfstackpush):

   • 新しいノードの pushcnt をインクリメントします。
   • 現在のスタックヘッドを読み込みます。
   • 新しいノードの next ポインタを現在のスタックヘッドが指すノードに設定します。
   • CASループを使用して、スタックヘッドを新しいノードにアトミックに更新します。このループは、CASが成功するまで繰り返されます。

4. ポップ操作 (runtime·lfstackpop):

   • 現在のスタックヘッドを読み込みます。
   • スタックが空の場合（ヘッドが0の場合）は nil を返します。
   • ヘッドからポインタ部分を抽出し、それが指すノードの next ポインタをアトミックに読み込みます。
   • CASループを使用して、スタックヘッドを次のノードにアトミックに更新します。このループも、CASが成功するまで繰り返されます。

5. テストの重要性:

   • lfstack_test.go には、基本的なプッシュ/ポップ操作のテスト (TestLFStack) と、複数のゴルーチンが同時にスタックを操作するストレス テスト (TestLFStackStress) が含まれています。
   • ストレス テストでは、GOMAXPROCS の数に応じて並列度を調整し、ランダムなスタック操作を多数実行することで、ロックフリースタックの並行安全性とデータ整合性を検証しています。これは、ロックフリーデータ構造の正しさを保証するために非常に重要です。

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

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

1. src/pkg/runtime/lfstack.c (新規ファイル):

   • ロックフリースタックのプッシュ (runtime·lfstackpush) およびポップ (runtime·lfstackpop, runtime·lfstackpop2) 操作のC言語実装。
   • ABA問題対策のためのポインタとカウンタの結合ロジック (PTR_BITS, PTR_MASK)。
   • アトミック操作 (runtime·atomicload64, runtime·cas64) の使用。

2. src/pkg/runtime/lfstack_test.go (新規ファイル):

   • ロックフリースタックの機能テスト (TestLFStack)。
   • 並行環境下での堅牢性を検証するストレス テスト (TestLFStackStress)。

3. src/pkg/runtime/runtime.h:

   • ロックフリースタックのノード構造体 LFNode の定義。
   • runtime·lfstackpush および runtime·lfstackpop 関数のプロトタイプ宣言。

4. src/pkg/runtime/export_test.go:

   • テスト目的で LFNode 構造体と lfstackpush, lfstackpop2 関数をエクスポートするための定義。

コアとなるコードの解説

src/pkg/runtime/lfstack.c

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Lock-free stack.

#include "runtime.h"
#include "arch_GOARCH.h"

#ifdef _64BIT
// Amd64 uses 48-bit virtual addresses, 47-th bit is used as kernel/user flag.
// So we use 17msb of pointers as ABA counter.
# define PTR_BITS 47
#else
# define PTR_BITS 32
#endif
#define PTR_MASK ((1ull<<PTR_BITS)-1)

void
runtime·lfstackpush(uint64 *head, LFNode *node)
{
	uint64 old, new;

	// ポインタがPTR_MASKの範囲内にあるかチェック（デバッグ用）
	if((uint64)node != ((uint64)node&PTR_MASK)) {
		runtime·printf("p=%p\n", node);
		runtime·throw("runtime·lfstackpush: invalid pointer");
	}

	node->pushcnt++; // ABAカウンタをインクリメント
	// ノードのポインタとpushcntを結合して新しいヘッドの値を生成
	new = (uint64)node|(((uint64)node->pushcnt)<<PTR_BITS);
	old = runtime·atomicload64(head); // 現在のヘッドをアトミックに読み込み
	for(;;) { // CASループ
		node->next = (LFNode*)(old&PTR_MASK); // 新しいノードのnextを現在のヘッドが指すノードに設定
		if(runtime·cas64(head, &old, new)) // CAS操作: headがoldと一致すればnewに更新
			break; // 成功したらループを抜ける
	}
}

LFNode*
runtime·lfstackpop(uint64 *head)
{
	LFNode *node, *node2;
	uint64 old, new;

	old = runtime·atomicload64(head); // 現在のヘッドをアトミックに読み込み
	for(;;) { // CASループ
		if(old == 0) // スタックが空の場合
			return nil;
		node = (LFNode*)(old&PTR_MASK); // ヘッドからポインタ部分を抽出
		node2 = runtime·atomicloadp(&node->next); // ノードのnextポインタをアトミックに読み込み
		new = 0;
		if(node2 != nil)
			// 次のノードのポインタとpushcntを結合して新しいヘッドの値を生成
			new = (uint64)node2|(((uint64)node2->pushcnt)<<PTR_BITS);
		if(runtime·cas64(head, &old, new)) // CAS操作: headがoldと一致すればnewに更新
			return node; // 成功したらノードを返す
	}
}

void
runtime·lfstackpop2(uint64 *head, LFNode *node)
{
	node = runtime·lfstackpop(head);
	FLUSH(&node); // FLUSHはコンパイラ最適化を防ぐためのマクロ（ここでは詳細省略）
}

このCコードは、ロックフリースタックの核心部分です。runtime·lfstackpush と runtime·lfstackpop は、それぞれスタックへの要素の追加と削除をアトミックに行います。特に注目すべきは、uint64 型の head 変数にポインタと pushcnt（ABAカウンタ）を結合して格納している点です。これにより、CAS操作がポインタの変更だけでなく、そのポインタが何回再利用されたかという情報も考慮に入れるため、ABA問題を効果的に回避しています。

src/pkg/runtime/lfstack_test.go

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package runtime_test

import (
	"math/rand"
	. "runtime" // runtimeパッケージの関数を直接参照できるようにする
	"testing"
	"unsafe" // unsafeパッケージでポインタ操作を行う
)

type MyNode struct {
	LFNode // runtimeパッケージのLFNodeを埋め込み
	data int
}

// MyNodeからLFNodeへの変換
func fromMyNode(node *MyNode) *LFNode {
	return (*LFNode)(unsafe.Pointer(node))
}

// LFNodeからMyNodeへの変換
func toMyNode(node *LFNode) *MyNode {
	return (*MyNode)(unsafe.Pointer(node))
}

func TestLFStack(t *testing.T) {
	stack := new(uint64) // スタックのヘッドを表すuint64ポインタ
	var nodes []*MyNode // ノードへの参照を保持するためのスライス

	// 初期状態が空であることを確認
	if LFStackPop(stack) != nil {
		t.Fatalf("stack is not empty")
	}

	// 要素をプッシュ
	node := &MyNode{data: 42}
	nodes = append(nodes, node)
	LFStackPush(stack, fromMyNode(node))

	node = &MyNode{data: 43}
	nodes = append(nodes, node)
	LFStackPush(stack, fromMyNode(node))

	// 要素をポップし、LIFO順であることを確認
	node = toMyNode(LFStackPop(stack))
	if node == nil || node.data != 43 {
		t.Fatalf("no lifo or stack empty")
	}

	node = toMyNode(LFStackPop(stack))
	if node == nil || node.data != 42 {
		t.Fatalf("no lifo or stack empty")
	}

	// スタックが再び空であることを確認
	if LFStackPop(stack) != nil || *stack != 0 {
		t.Fatalf("stack is not empty")
	}
}

func TestLFStackStress(t *testing.T) {
	const K = 100 // 初期ノード数
	P := 4 * GOMAXPROCS(-1) // 並列ゴルーチン数
	N := 100000 // 各ゴルーチンの操作回数
	if testing.Short() {
		N /= 10
	}

	stacks := [2]*uint64{new(uint64), new(uint64)} // 2つのスタック
	var nodes []*MyNode // ノードへの参照を保持

	sum := 0
	for i := 0; i < K; i++ { // 初期ノードをランダムに2つのスタックにプッシュ
		sum += i
		node := &MyNode{data: i}
		nodes = append(nodes, node)
		LFStackPush(stacks[i%2], fromMyNode(node))
	}

	c := make(chan bool, P)
	for p := 0; p < P; p++ { // P個のゴルーチンを起動
		go func() {
			r := rand.New(rand.NewSource(rand.Int63()))
			for i := 0; i < N; i++ { // 各ゴルーチンがランダムなスタックからポップし、別のランダムなスタックにプッシュ
				node := toMyNode(LFStackPop(stacks[r.Intn(2)]))
				if node != nil {
					LFStackPush(stacks[r.Intn(2)], fromMyNode(node))
				}
			}
			c <- true
		}()
	}
	for i := 0; i < P; i++ { // 全てのゴルーチンの完了を待つ
		<-c
	}

	// 全ての要素をポップし、失われたものがないか、合計値が正しいかを確認
	sum2 := 0
	cnt := 0
	for i := 0; i < 2; i++ {
		for {
			node := toMyNode(LFStackPop(stacks[i]))
			if node == nil {
				break
			}
			cnt++
			sum2 += node.data
			node.Next = nil // 参照をクリア
		}
	}
	if cnt != K {
		t.Fatalf("Wrong number of nodes %d/%d", cnt, K)
	}
	if sum2 != sum {
		t.Fatalf("Wrong sum %d/%d", sum2, sum)
	}
}

テストコードは、ロックフリースタックが正しく機能し、並行環境下でもデータの整合性を保つことを検証しています。TestLFStackStress は特に重要で、複数のゴルーチンが同時にスタックを操作するシナリオをシミュレートし、ABA問題やその他の並行処理のバグがないことを確認します。

関連リンク

• 元のGerrit変更リスト (並列GC関連): https://golang.org/cl/5279048/
• このコミットのGerrit変更リスト: https://golang.org/cl/5993043

参考にした情報源リンク

• Go言語のガベージコレクション: GoのGCの進化と並列GCの概念について理解を深めるために、Goの公式ドキュメントやブログ記事が参考になります。
  • Go's Garbage Collector: From 1.5 to 1.8
  • Go's high-performance GC in Go 1.8
• ロックフリーデータ構造とABA問題: ロックフリーアルゴリズムの基礎、特にCAS操作とABA問題の解決策について学ぶために、並行プログラミングに関する一般的な資料が役立ちます。
  • Lock-free and wait-free algorithms
  • ABA problem
• Dmitriy Vyukovの作業: コミットの作者であるDmitriy Vyukovは、Goランタイムと並行処理の分野で多くの貢献をしています。彼の他のコミットや論文も参考になります。
  • Dmitriy Vyukov's GitHub profile
  • Go Concurrency Patterns: Context (彼が共同執筆した記事)