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.

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

runtime: improve runtime.overLoadFactor calculation #20195

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

Comments

Projects
None yet
4 participants
@josharian
Copy link
Contributor

commented May 1, 2017

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

This comment has been minimized.

Copy link

commented May 1, 2017

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

gopherbot pushed a commit that referenced this issue May 1, 2017

runtime: use 64 bit calculation in overLoadFactor
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

This comment has been minimized.

Copy link
Contributor Author

commented May 1, 2017

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

runtime: use 64 bit calculation in overLoadFactor
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

This comment has been minimized.

Copy link
Contributor

commented Jul 10, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.