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

x/time/rate: allows more than configured #45245

Open
Morainy opened this issue Mar 26, 2021 · 6 comments
Open

x/time/rate: allows more than configured #45245

Morainy opened this issue Mar 26, 2021 · 6 comments

Comments

@Morainy
Copy link

@Morainy Morainy commented Mar 26, 2021

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

go version go1.16.2 darwin/amd64

Does this issue reproduce with the latest release?

Yes

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

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOOS="darwin"
GOROOT="/usr/local/go"
GOSUMDB="off"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.16.2"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/tn/rljgjtgs4wg_mpjh961rmdyc0000gn/T/go-build3419748436=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

package main

import (
	"fmt"
	"golang.org/x/time/rate"
	"sync/atomic"
	"time"
)

func main() {
	var succCount, failCount int64
	limit := rate.Every(100 * time.Millisecond)
	burst := 1
	limiter := rate.NewLimiter(limit, burst)
	start := time.Now()
	for i := 0; i < 5000; i++ {
		go func() {
			for {
				if limiter.Allow() {
					atomic.AddInt64(&succCount, 1)
				} else {
					atomic.AddInt64(&failCount, 1)
				}
			}
		}()
	}
	time.Sleep(2 * time.Second)
	elapsed := time.Since(start)
	fmt.Println("elapsed=", elapsed, "succCount=", atomic.LoadInt64(&succCount), "failCount=", atomic.LoadInt64(&failCount))
}

What did you expect to see?

succCount should almost be 20 but it could get a number beyond 10000

What did you see instead?

elapsed= 2.01049986s succCount= 25629 failCount 6806127

@seankhliao seankhliao changed the title golang.org/x/time/rate concurrent bug x/time/rate: allows more than configured Mar 26, 2021
@gopherbot gopherbot added this to the Unreleased milestone Mar 26, 2021
@fraenkel
Copy link
Contributor

@fraenkel fraenkel commented Mar 26, 2021

@Morainy You might want to read the documentation for Allow(). It just says whether there is room. You want to use Wait() and you will get your expected behavior.

@b97tsk
Copy link

@b97tsk b97tsk commented Mar 26, 2021

Guys, this is a real issue and the fix is roughly mentioned in #23145:

--- a/rate/rate.go
+++ b/rate/rate.go
@@ -320,7 +320,7 @@ func (lim *Limiter) reserveN(now time.Time, n int, maxFutureReserve time.Duratio
 		}
 	}
 
-	now, last, tokens := lim.advance(now)
+	now, _, tokens := lim.advance(now)
 
 	// Calculate the remaining number of tokens resulting from the request.
 	tokens -= float64(n)
@@ -350,8 +350,6 @@ func (lim *Limiter) reserveN(now time.Time, n int, maxFutureReserve time.Duratio
 		lim.last = now
 		lim.tokens = tokens
 		lim.lastEvent = r.timeToAct
-	} else {
-		lim.last = last
 	}
 
 	lim.mu.Unlock()

(Now the second return value of (*Limiter).advance is not used anywhere, it can be removed; and the first return value is just the same value as the argument, it can be removed too.)

lim.last should not be updated alone. The comment about this field in rate/rate.go#L60 clearly says last is the last time the limiter's tokens field was updated.

This is the output after applied the fix:

elapsed= 2.0010308s succCount= 20 failCount= 7280081

When Allow is called, time.Now is immediately called before the limiter acquires its lock. So when the limiter holds the lock, the time returned by the time.Now call could be a bit outdated. Technically, this already seems wrong to me. You have to be in the hope that it won't get too racy.

@opennota
Copy link

@opennota opennota commented Mar 30, 2021

@fraenkel I believe that the documentation for AllowN is incomplete. It doesn't say anywhere that if you call AllowN two or more times without waiting only the first call will return true.

// AllowN reports whether n events may happen at time now.
// Use this method if you intend to drop / skip events that exceed the rate limit.
// Otherwise use Reserve or Wait.
package main

import (
	"fmt"
	"golang.org/x/time/rate"
	"time"
)

func main() {
	limit := rate.Every(100 * time.Millisecond)
	burst := 1
	limiter := rate.NewLimiter(limit, burst)
	for i := 0; i < 5; i++ {
		fmt.Println(limiter.Allow())
	}
	// Output:
	// true
	// false
	// false
	// false
	// false
}
@Morainy
Copy link
Author

@Morainy Morainy commented Mar 30, 2021

@b97tsk why couldn't this fix be merged into main?

@b97tsk
Copy link

@b97tsk b97tsk commented Mar 30, 2021

@Morainy I'm not a contributor. I was trying to help. I suggested a fix. It could be wrong.

This is an old package. It's hard to tell if there's any existing application relies on this behavior. So even I am correct, it could still be marked as WON'T FIX. Just my opinion.

@b97tsk
Copy link

@b97tsk b97tsk commented Apr 2, 2021

It could be a security issue, you know, if the package is used to mitigate DoS attacks or web scraping, it simply won't work.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants