Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

compress/flate: deflatefast does not deliver consistent results after reset #34121

Closed
tbushnell opened this issue Sep 5, 2019 · 9 comments
Closed

compress/flate: deflatefast does not deliver consistent results after reset #34121

tbushnell opened this issue Sep 5, 2019 · 9 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Go1.15

Comments

@tbushnell
Copy link

in compress/flate/deflatefast.go:

Omitting here the reasons why stableflate does what it does, and focusing just on the one bad effect:

deflatefast.go maintains a counter "cur" in the object. When cur advances past 1<<30, resetAll is called, which discards the current match table. Discarding the match table changes the behavior of further compression at that point, of course.

Normal reset of the object calls reset, which advances cur by 1<<15 (and then is one of the places that checks if it's now past 1<<30, but this is not important here).

If the same object is repeatedly used for compression runs, with a reset in between, then two different objects, with different histories, but both reset, will have different values for cur. This in turn means there is a different run distance before the match table is discarded, and therefore, potentially different compression behavior even with identical input.

O(32K) (1<<30 / 1<<15) resets is sufficient to produce the problem, which is not absurd for a high-volume server.
@dsnet dsnet changed the title deflatefast does not deliver consistent results after reset [compress/flate] compress/flate: deflatefast does not deliver consistent results after reset Sep 5, 2019
@dsnet dsnet added the NeedsFix The path to resolution is known, but the work has not been done. label Sep 5, 2019
@dsnet
Copy link
Member

dsnet commented Sep 5, 2019

\cc @klauspost as this issue probably affects your fork as well.

@dsnet dsnet added this to the Go1.14 milestone Sep 5, 2019
@tbushnell
Copy link
Author

I have a change to the existing tests which will expose the bug, but I'm working on making it flexible instead of based on knowing the exact current implementation. Also getting a fix ready to suggest.

@klauspost
Copy link
Contributor

klauspost commented Sep 5, 2019 •
edited

Thanks for the ping!

I am about to replace it with code that shifts down the table instead of clearing it. That should make it transparent.

Let me see if I can cook up a PR with similar functionality.

klauspost added a commit to klauspost/go that referenced this issue Sep 5, 2019
@klauspost
compress/flate: Fix deflate Reset consistency
034795c 
Make the reset point retain the current table so compression is unaffected by resets.

Fixes golang#34121
@klauspost klauspost mentioned this issue Sep 5, 2019
Closed
@klauspost
Copy link
Contributor

PR added.

@gopherbot
Copy link

Change https://golang.org/cl/193605 mentions this issue: compress/flate: fix deflate Reset consistency

@tbushnell
Copy link
Author

My concern with shifting down the table is that it makes compression slower. If we had Reset clear the table entirely, then compression remains as fast as it does now. Reset doesn't need to be super fast IMO.

However, I have no objection to this style of fix if it's what you prefer.

@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
@rsc rsc modified the milestones: Backlog, Go1.15 Jul 15, 2020
@rsc
Copy link
Contributor

rsc commented Jul 15, 2020

Received a report of this problem from a Go 1.15 beta 1 tester.
I wrote a test and tried the pending CL 193605, but it didn't fix my test.
I will see if I can find a simple fix for Go 1.15.

@rsc rsc reopened this Jul 16, 2020
@rsc
Copy link
Contributor

rsc commented Jul 16, 2020

Not completely fixed. There is another.

@gopherbot
Copy link

Change https://golang.org/cl/243140 mentions this issue: compress/flate: fix another deflate Reset inconsistency

@atetubou atetubou mentioned this issue Sep 16, 2020
Closed
@golang golang locked and limited conversation to collaborators Jul 16, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Go1.15
Development

Successfully merging a pull request may close this issue.

compress/flate: fix deflate Reset consistency klauspost/go
5 participants
@tbushnell @rsc @klauspost @dsnet @gopherbot