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

コミット

commit 37f046bac67053773d2ed34299a2e7e520c88037
Author: Ivan Krasin <krasin@golang.org>
Date:   Wed May 30 16:08:38 2012 -0400

    compress/flate: fix overflow on 2GB input. Reset hashOffset every 16 MB.
    
    This bug has been introduced in the following revision:
    
    changeset:   11404:26dceba5c610
    user:        Ivan Krasin <krasin@golang.org>
    date:        Mon Jan 23 09:19:39 2012 -0500
    summary:     compress/flate: reduce memory pressure at cost of additional arithmetic operation.
    
    This is the review page for that CL: https://golang.org/cl/5555070/
    
    R=rsc, imkrasin
    CC=golang-dev
    https://golang.org/cl/6249067

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

https://github.com/golang/go/commit/37f046bac67053773d2ed34299a2e7e520c88037

元コミット内容

このコミットは、Go言語のcompress/flateパッケージにおけるバグ修正を目的としています。具体的には、2GBを超える入力データに対して圧縮を行う際に発生するオーバーフローを修正し、その対策としてhashOffsetを16MBごとにリセットする変更が加えられています。

このバグは、以前のコミット（changeset: 11404:26dceba5c610、summary: compress/flate: reduce memory pressure at cost of additional arithmetic operation.）で導入されたものであり、その変更はメモリ使用量を削減することを目的としていました。

変更の背景

compress/flateパッケージは、DEFLATEアルゴリズムを実装しており、データ圧縮に利用されます。DEFLATEアルゴリズムは、LZ77アルゴリズムとハフマン符号化を組み合わせたものです。LZ77アルゴリズムでは、入力データ内の繰り返しパターン（一致する文字列）を見つけて、そのパターンを「距離（distance）」と「長さ（length）」のペアで置き換えることで圧縮を行います。この「距離」は、現在の位置からどれだけ前に同じパターンが出現したかを示します。

この距離を効率的に検索するために、DEFLATEの実装ではハッシュテーブルが使用されます。入力データの各位置から始まる短いバイトシーケンス（通常は3バイト）のハッシュ値を計算し、そのハッシュ値に対応するハッシュテーブルのエントリに、そのシーケンスが出現した入力データの位置を記録します。これにより、同じハッシュ値を持つ以前のシーケンスを素早く見つけることができます。

問題は、このハッシュテーブルに記録される位置情報が、入力データのオフセット（hashOffset）に基づいて相対的に管理されている点にありました。以前のコミット（11404:26dceba5c610）では、メモリ使用量を削減するために、このオフセットの管理方法が変更されました。しかし、この変更が2GBを超えるような非常に大きな入力データに対して、オフセット値がオーバーフローする可能性を生み出してしまいました。

具体的には、hashOffsetが非常に大きな値になった場合、ハッシュテーブルに格納されている以前の位置情報との差分を計算する際に、符号付き整数型の最大値を超えてしまい、不正な距離が計算されることで圧縮処理が失敗したり、誤った圧縮結果が生成されたりする問題が発生しました。

このコミットは、このオーバーフロー問題を解決し、大規模なデータに対しても安定して圧縮処理が行えるようにするために導入されました。

前提知識の解説

• DEFLATEアルゴリズム:
  • データ圧縮アルゴリズムの一つで、LZ77アルゴリズムとハフマン符号化を組み合わせたものです。ZIP、gzip、PNGなどのファイル形式で広く利用されています。
  • LZ77: 繰り返し出現するバイト列を、以前に出現した同じバイト列への参照（距離と長さのペア）で置き換えることで圧縮します。例えば、「ABCABCABC」は「ABC」と「その3文字前からの繰り返し3回」のように表現されます。
  • ハフマン符号化: 出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。
• ハッシュテーブル (Hash Table):
  • キーと値のペアを格納するデータ構造で、キーからハッシュ関数を用いて値を格納するメモリ上の位置（インデックス）を計算します。これにより、高速なデータの検索、挿入、削除が可能になります。
  • DEFLATEの実装では、入力データの短いバイトシーケンス（例: 3バイト）をキーとして、そのシーケンスが出現した入力データ内の位置を値としてハッシュテーブルに格納します。
• スライディングウィンドウ (Sliding Window):
  • LZ77アルゴリズムで用いられる概念で、入力データを処理する際に、現在処理中の位置から一定の範囲（ウィンドウ）を「辞書」として利用します。このウィンドウ内でのみ、一致するパターンを検索します。DEFLATEでは、通常32KBのウィンドウサイズが使われます。
• hashOffset:
  • DEFLATE圧縮器の内部状態変数の一つで、ハッシュテーブルに格納されている位置情報が、入力データのどのオフセットを基準にしているかを示す値です。入力データが大きくなるにつれて、このオフセットも増加します。
• オーバーフロー (Overflow):
  • コンピュータの数値計算において、あるデータ型で表現できる最大値を超えた結果が生じることです。例えば、32ビット符号付き整数型で表現できる最大値は2,147,483,647ですが、これを超える値を計算しようとすると、予期しない結果（負の値になったり、最小値に戻ったり）が生じます。

技術的詳細

このコミットの核心は、compress/flateパッケージのdeflate.goファイルにおけるhashOffsetの管理方法の改善です。

DEFLATE圧縮器は、入力データを処理する際に、過去のデータとの一致を効率的に見つけるためにハッシュテーブル（hashHeadとhashPrev）を使用します。hashHead[h]は、ハッシュ値hを持つ最新の一致の開始位置を格納し、hashPrev[p]は、位置pの前の、同じハッシュ値を持つ一致の開始位置を格納します。これらの位置は、入力データの先頭からの絶対オフセットとして扱われます。

しかし、入力データが非常に大きくなると、これらの絶対オフセット値も非常に大きくなります。特に、hashOffsetは、スライディングウィンドウが移動するにつれて増加し、ハッシュテーブルに格納される位置情報もこのオフセットに基づいて更新されます。

以前のバグでは、hashOffsetが2GB（約2 * 10^9バイト）を超えると、内部的な計算でオーバーフローが発生し、ハッシュテーブルに格納された位置情報が不正になる可能性がありました。これにより、正しい一致が見つけられなくなったり、存在しない一致を参照しようとしたりして、圧縮処理が失敗したり、効率が著しく低下したりする問題が生じていました。

このコミットでは、maxHashOffsetという新しい定数（1 << 24、つまり16MB）を導入し、hashOffsetがこの値を超えた場合に、ハッシュテーブル内のすべての位置情報をリセットするロジックを追加しました。

具体的には、d.hashOffset > maxHashOffsetという条件が満たされた場合、以下の処理が行われます。

1. delta := d.hashOffset - 1: hashOffsetがmaxHashOffsetを超えた量（厳密にはhashOffset - 1）をdeltaとして計算します。
2. d.hashOffset -= delta: hashOffsetをdelta分だけ減算し、実質的に1にリセットします。
3. d.chainHead -= delta: 現在のチェーンの先頭位置もdelta分だけ調整します。
4. for i, v := range d.hashPrev と for i, v := range d.hashHead:
   • d.hashPrevとd.hashHeadの各エントリ（以前の一致の位置情報）をループで処理します。
   • if v > delta: もし格納されている位置vがdeltaよりも大きい場合、その位置もdelta分だけ減算して調整します。
   • else: そうでない場合（つまり、vがdelta以下の場合）、その位置はもはや有効な参照ではないため、0にリセットします。これは、deltaよりも小さい位置は、現在のスライディングウィンドウの範囲外にあるか、または非常に古い参照であり、もはや利用できないことを意味します。

この処理により、hashOffsetとハッシュテーブル内の位置情報が定期的にリセットされ、常に相対的なオフセットが小さな値に保たれるようになります。これにより、2GBを超えるような大きな入力データに対しても、オーバーフローを回避し、ハッシュテーブルが正しく機能するようになります。

また、このコミットでは、非常に長い疎な（sparse）入力データ（0が続き、最後に1が続くようなデータ）に対するテストケースTestVeryLongSparseChunkが追加されています。これは、ハッシュ参照が欠落する可能性のある大規模な入力に対する圧縮器の堅牢性を検証するためのものです。

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

src/pkg/compress/flate/deflate.go

@@ -32,6 +32,7 @@ const (
 	hashSize            = 1 << hashBits
 	hashMask            = (1 << hashBits) - 1
 	hashShift           = (hashBits + minMatchLength - 1) / minMatchLength
+	maxHashOffset       = 1 << 24 // 16MB
 
 	skipNever = math.MaxInt32
 )
@@ -106,6 +107,25 @@ func (d *compressor) fillDeflate(b []byte) int {
 			d.blockStart = math.MaxInt32
 		}
 		d.hashOffset += windowSize
+		if d.hashOffset > maxHashOffset {
+			delta := d.hashOffset - 1
+			d.hashOffset -= delta
+			d.chainHead -= delta
+			for i, v := range d.hashPrev {
+				if v > delta {
+					d.hashPrev[i] -= delta
+				} else {
+					d.hashPrev[i] = 0
+				}
+			}
+			for i, v := range d.hashHead {
+				if v > delta {
+					d.hashHead[i] -= delta
+				} else {
+					d.hashHead[i] = 0
+				}
+			}
+		}
 	}
 	n := copy(d.window[d.windowEnd:], b)
 	d.windowEnd += n

src/pkg/compress/flate/deflate_test.go

@@ -94,6 +94,50 @@ func TestDeflate(t *testing.T) {
 	}
 }
 
+// A sparseReader returns a stream consisting of 0s followed by 1<<16 1s.
+// This tests missing hash references in a very large input.
+type sparseReader struct {
+	l   int64
+	cur int64
+}
+
+func (r *sparseReader) Read(b []byte) (n int, err error) {
+	if r.cur >= r.l {
+		return 0, io.EOF
+	}
+	n = len(b)
+	cur := r.cur + int64(n)
+	if cur > r.l {
+		n -= int(cur - r.l)
+		cur = r.l
+	}
+	for i := range b[0:n] {
+		if r.cur+int64(i) >= r.l-1<<16 {
+			b[i] = 1
+		} else {
+			b[i] = 0
+		}
+	}
+	r.cur = cur
+	return
+}
+
+func TestVeryLongSparseChunk(t *testing.T) {
+	if testing.Short() {
+		t.Logf("skipping sparse chunk during short test")
+		return
+	}
+	w, err := NewWriter(ioutil.Discard, 1)
+	if err != nil {
+		t.Errorf("NewWriter: %v", err)
+		return
+	}
+	if _, err = io.Copy(w, &sparseReader{l: 23E8}); err != nil {
+		t.Errorf("Compress failed: %v", err)
+		return
+	}
+}
+
 type syncBuffer struct {
 	buf    bytes.Buffer
 	mu     sync.RWMutex

コアとなるコードの解説

src/pkg/compress/flate/deflate.go

1. maxHashOffset定数の追加:
   • const maxHashOffset = 1 << 24 が追加されました。これは16,777,216、つまり16MBを意味します。この値は、hashOffsetがこれを超えた場合にリセット処理を行う閾値として使用されます。
2. hashOffsetのリセットロジックの追加:
   • d.hashOffset += windowSize の直後に、以下の条件分岐が追加されました。
   • if d.hashOffset > maxHashOffset { ... }
     • この条件は、hashOffsetが16MBを超えた場合に真となります。
     • delta := d.hashOffset - 1: hashOffsetがmaxHashOffsetを超えた分の差分を計算します。このdeltaは、ハッシュテーブル内の既存のオフセット値を調整するために使用されます。
     • d.hashOffset -= delta: hashOffsetをdelta分だけ減算し、実質的に1にリセットします。これにより、hashOffsetが常に小さな値に保たれ、オーバーフローのリスクがなくなります。
     • d.chainHead -= delta: chainHeadは、現在のスライディングウィンドウの先頭位置を示します。hashOffsetがリセットされたことに合わせて、この値もdelta分だけ調整されます。
     • for i, v := range d.hashPrev { ... } と for i, v := range d.hashHead { ... }:
       • d.hashPrevとd.hashHeadは、それぞれ以前の一致の連鎖と、ハッシュ値ごとの最新の一致の位置を格納する配列です。これらの配列に格納されている値は、入力データの絶対オフセットです。
       • if v > delta { d.hashPrev[i] -= delta } else { d.hashPrev[i] = 0 }:
         • 配列内の各エントリv（以前の一致の位置）がdeltaよりも大きい場合、その位置もdelta分だけ減算して調整します。これにより、相対的な位置関係が維持されます。
         • vがdelta以下の場合、その位置は現在のスライディングウィンドウの範囲外にあるか、または非常に古い参照であり、もはや有効ではないため、0にリセットされます。これは、無効な参照が使用されるのを防ぎます。

この変更により、hashOffsetが無限に増加するのを防ぎ、ハッシュテーブル内の位置情報が常に有効な範囲内に保たれるようになります。

src/pkg/compress/flate/deflate_test.go

1. sparseReader構造体の追加:
   • これはio.Readerインターフェースを実装するカスタムリーダーです。
   • lフィールドは読み取るデータの総バイト数、curは現在の読み取り位置を示します。
   • Readメソッドは、l - (1 << 16)バイトまでは0を返し、残りの1 << 16バイト（65536バイト）は1を返します。
   • このリーダーは、非常に長い入力データで、かつほとんどが0で構成され、最後に短いパターン（1の連続）が出現するような、ハッシュ参照が欠落しやすいシナリオをシミュレートするために設計されています。
2. TestVeryLongSparseChunkテスト関数の追加:
   • このテストは、sparseReaderを使用して非常に大きなデータ（23E8、つまり2.3GB）をflate圧縮器に供給し、圧縮処理が正常に完了するかどうかを検証します。
   • testing.Short()チェックにより、go test -short実行時にはスキップされます。これは、このテストが非常に時間がかかる可能性があるためです。
   • NewWriter(ioutil.Discard, 1)で新しいflate.Writerを作成し、出力はioutil.Discard（破棄）されます。圧縮レベルは1（最速）に設定されています。
   • io.Copy(w, &sparseReader{l: 23E8})で、sparseReaderからのデータを圧縮器にコピーします。
   • エラーが発生した場合、t.Errorfでテストが失敗したことを報告します。

このテストケースの追加は、hashOffsetのリセットロジックが、実際に大規模で特定のパターンを持つ入力データに対して正しく機能するかどうかを検証するために非常に重要です。

関連リンク

• Go言語のcompress/flateパッケージのドキュメント: https://pkg.go.dev/compress/flate
• DEFLATEアルゴリズムに関するWikipedia記事: https://ja.wikipedia.org/wiki/DEFLATE
• LZ77アルゴリズムに関するWikipedia記事: https://ja.wikipedia.org/wiki/LZ77%E3%81%8A%E3%82%88%E3%81%B3_LZ78
• ハフマン符号化に関するWikipedia記事: https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89

参考にした情報源リンク

• 元の変更リスト (CL) のレビューページ: https://golang.org/cl/6249067
• バグを導入した以前の変更リスト (CL) のレビューページ: https://golang.org/cl/5555070/
• Go言語のソースコード（compress/flateパッケージ）: https://github.com/golang/go/tree/master/src/compress/flate