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

runtime: improve runtime.overLoadFactor calculation #20195

Closed
josharian opened this issue May 1, 2017 · 3 comments
Closed

runtime: improve runtime.overLoadFactor calculation #20195

josharian opened this issue May 1, 2017 · 3 comments
Labels
FrozenDueToAge
Milestone
Go1.11

Comments

@josharian
Copy link
Contributor

runtime.overLoadFactor could use some improvement.

First, a bug: uintptr is 32 bits wide on a 32 bit system, so calculating uintptr(1<<B) can overflow when B >= 32. That's Go 1.9 material, and I'll send a CL shortly. Maybe even 1.8.2, given the devastating result (infinite loop) and simplicity of fix. Marking 1.8.2 for discussion.

Second, an improvement: We should rewrite this to use integer arithmetic and pay more careful attention to potential overflow. That should probably wait for Go 1.10.

Exposed by CL 40854 when working with a hint of 1 << 62. CL 40854 will also help with the bug, once it is correctly implemented.
@josharian josharian added this to the Go1.8.2 milestone May 1, 2017
@gopherbot
Copy link
Contributor

CL https://golang.org/cl/42185 mentions this issue.

gopherbot pushed a commit that referenced this issue May 1, 2017
@josharian
runtime: use 64 bit calculation in overLoadFactor
b666f28 
overLoadFactor used a uintptr for its calculations.
When the number of potential buckets was large,
perhaps due to a coding error or corrupt/malicious user input
leading to a very large map size hint,
this led to overflow on 32 bit systems.
This overflow resulted in an infinite loop.

Prevent it by always using a 64 bit calculation.

Updates #20195

Change-Id: Iaabc710773cd5da6754f43b913478cc5562d89a2
Reviewed-on: https://go-review.googlesource.com/42185
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
@josharian josharian modified the milestones: Go1.10, Go1.8.2 May 1, 2017
@josharian
Copy link
Contributor Author

Keith points out that the bug can't occur in 1.8, and the initial fix is in, so setting to 1.10 to use int calculations.

josharian added a commit to josharian/go that referenced this issue May 2, 2017
@josharian
runtime: use 64 bit calculation in overLoadFactor
03f90c9 
overLoadFactor used a uintptr for its calculations.
When the number of potential buckets was large,
perhaps due to a coding error or corrupt/malicious user input
leading to a very large map size hint,
this led to overflow on 32 bit systems.
This overflow resulted in an infinite loop.

Prevent it by always using a 64 bit calculation.

Updates golang#20195

Change-Id: Iaabc710773cd5da6754f43b913478cc5562d89a2
@rsc rsc modified the milestones: Go1.10, Go1.11 Nov 22, 2017
@ianlancetaylor
Copy link
Member

This was fixed by https://golang.org/cl/54655.

@golang golang locked and limited conversation to collaborators Jul 10, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.11
Development

No branches or pull requests
4 participants
@josharian @rsc @ianlancetaylor @gopherbot