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

Jump to bottom

x/time: when rate is 0.7692307692307693 (10/13), Allow() returns false #34861

Closed
on99 opened this issue Oct 12, 2019 · 4 comments
Closed

x/time: when rate is 0.7692307692307693 (10/13), Allow() returns false #34861

on99 opened this issue Oct 12, 2019 · 4 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Unreleased

Comments

@on99
Copy link

on99 commented Oct 12, 2019 •
edited

What version of Go are you using (go version)?

$ go version
go version go1.12.7 darwin/amd64

Does this issue reproduce with the latest release?

Yes, it reproduces with go 1.13.1

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/on99/Library/Caches/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/on99/.gvm/pkgsets/go1.12.7/global"
GOPROXY=""
GORACE=""
GOROOT="/Users/on99/.gvm/gos/go1.12.7"
GOTMPDIR=""
GOTOOLDIR="/Users/on99/.gvm/gos/go1.12.7/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/18/tghhmy8j77bgv7c0p4zqgw440000gp/T/go-build762921926=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

https://play.golang.org/p/mtyMTtDj5vj

What did you expect to see?

I expect it returns true.

What did you see instead?

It returns false.
@gopherbot gopherbot added this to the Unreleased milestone Oct 12, 2019
@ericlagergren
Copy link
Contributor

ericlagergren commented Oct 13, 2019 •
edited

I'm not too familiar with the rate limiting algorithm, but the bug seems to come from a floating-point imprecision.

First, Limiter.advance calls tokensFromDuration(1299999999), which computes

1.299999999 * 0.7692307692307693 = 0.9999999992307692 (current)
1.299999999 * 0.7692307692307693 = 0.9999999992307693207692307 (actual)

That result (after subtracting n on line 320, which is 1) then skews durationFromTokens

(7.692307901763229e-10 / 0.7692307692307693)*1e9 = 1.0000000272292198 (current)
(7.692306792307693e-10 / 0.7692307692307693)*1e9 = 0.9999998830000000000000105300000000 (actual)

Since that result is truncated (converted to an int64), the comparison on line 329 evaluates to false since waitDuration (1) <= maxFutureReserve (0).

Manually fixing the inaccuracy inside tokensFromDuration fixes the bug.

@changkun changkun mentioned this issue Oct 13, 2019
Closed
@gopherbot
Copy link

Change https://golang.org/cl/200917 mentions this issue: rate: fix truncated seconds in tokensFromDuration

@on99
Copy link
Author

on99 commented Oct 14, 2019

@ericlagergren Thank you, I got it.

@katiehockman katiehockman added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 14, 2019
@gopherbot
Copy link

Change https://golang.org/cl/200900 mentions this issue: rate: fix rounding error in tokensFromDuration

@golang golang locked and limited conversation to collaborators Oct 22, 2020
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
Unreleased
Development

Successfully merging a pull request may close this issue.

rate: fix truncated seconds in tokensFromDuration
4 participants
@ericlagergren @gopherbot @on99 @katiehockman