compress/flate: fix overflow on 2GB input. Reset hashOf...

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: http://codereview.appspot.com/5555070/

[rsc, 2012-05-30 03:19:10]

Looks good. Now that you understand the bug, is it possible to write a
simple test that will trigger it (one that doesn't require a 2GB input
file)? It would be good to have such a test that was disabled for
testing.Short() but run during long tests.

Thanks.
Russ

[imkrasin, 2012-05-30 17:11:21]

Hi Russ,

I have added the test (a very long, sparse input). Also, I don't run
DeflateInflateTest on the inputs larger than a threshold.

Short tests for compress/flate run 0.8 sec on my machine and large tests run 16
sec. This might be a problem on ARM.

[rsc, 2012-05-30 17:23:01]

I patched this in, reverted deflate.go, and changed 2*maxHashOffset to
1<<25 in the test, and the test passes. I was hoping for a test that
fails without this CL. Is that possible?

Thanks.
Russ

[imkrasin, 2012-05-30 17:25:21]

Just a sec.

[imkrasin, 2012-05-30 18:26:12]

On 2012/05/30 17:25:21, imkrasin wrote:
> Just a sec.

My estimation was about 3600x more optimistic than the reality, but the test is
ready. Please, take a look. It works ~ 15 sec on my machine.

[imkrasin, 2012-05-30 18:31:13]

The idea of the test: the bug is reproduced when hashHead contains a very (> 2GB
ago) stale reference that is being requested. So, the test satisfies: 

111111111 <many zeros> 111111111

because most of the time we update the same hash.

[rsc, 2012-05-30 18:39:18]

Thanks for working out a test.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
File src/pkg/compress/flate/deflate_test.go (right):

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:103: type sparseReader struct {
// A sparseReader returns a stream consisting of 10 1s followed by l-20 0s
followed by 10 1s.
// This tests very old hash references.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:115: n -= int(cur - r.l)
add
cur = r.l

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:118: if cur+int64(i) < 10 || cur+int64(i)
>= r.l-10 {
Looks like this should be r.cur. Otherwise the location of the 1s depends on
exactly how big a read was done, no?

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:130: return
t.Logf("skipping sparse chunk during short test")

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:132: w, err := NewWriter(&nullWriter{},
1)
You can use ioutil.Discard instead of defining nullWriter.

[imkrasin, 2012-05-30 20:01:19]

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
File src/pkg/compress/flate/deflate_test.go (right):

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:103: type sparseReader struct {
On 2012/05/30 18:39:18, rsc wrote:
> // A sparseReader returns a stream consisting of 10 1s followed by l-20 0s
> followed by 10 1s.
> // This tests very old hash references.

Done.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:115: n -= int(cur - r.l)
On 2012/05/30 18:39:18, rsc wrote:
> add
> cur = r.l

Done.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:118: if cur+int64(i) < 10 || cur+int64(i)
>= r.l-10 {
On 2012/05/30 18:39:18, rsc wrote:
> Looks like this should be r.cur. Otherwise the location of the 1s depends on
> exactly how big a read was done, no?
It turns out that the bug is harder to reproduce than I thought. I have changed
the test to a more correct form that reproduces the issue.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:130: return
On 2012/05/30 18:39:18, rsc wrote:
> t.Logf("skipping sparse chunk during short test")

Done.

http://codereview.appspot.com/6249067/diff/6004/src/pkg/compress/flate/deflat...
src/pkg/compress/flate/deflate_test.go:132: w, err := NewWriter(&nullWriter{},
1)
On 2012/05/30 18:39:18, rsc wrote:
> You can use ioutil.Discard instead of defining nullWriter.

Done.

[rsc, 2012-05-30 20:08:44]

*** Submitted as http://code.google.com/p/go/source/detail?r=00a1ca1ea3bd ***

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: http://codereview.appspot.com/5555070/

R=rsc, imkrasin
CC=golang-dev
http://codereview.appspot.com/6249067

Committer: Russ Cox <rsc@golang.org>

[rsc, 2012-05-30 20:08:52]

LGTM

Thanks for all the revisions. I feel good about this fix now.

[imkrasin, 2012-05-30 20:21:55]

On 2012/05/30 20:08:52, rsc wrote:
> LGTM
> 
> Thanks for all the revisions. I feel good about this fix now.

Thank for showing me ioutil.Discard (I tend to look at types and methods in the
docs, and frequently ignore vars).

Sorry for yet another bug in my code.

[remyoudompheng, 2013-07-21 19:57:26]

R=close