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: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

Open
mpl opened this issue Jul 15, 2021 · 7 comments
Labels
NeedsInvestigation
Milestone

Comments

@mpl
Copy link
Contributor

@mpl mpl commented Jul 15, 2021

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

$ go version
go version go1.16 darwin/amd64

Does this issue reproduce with the latest release?

Yes (with go version go1.16.6 darwin/amd64)

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

go env Output
$ go env

GOARCH="amd64"
GOOS="darwin"

What did you do?

Consider these two, that only differ in their argument to NewLimiter:

func TestReserveAtZero(t *testing.T) {
	atZero := NewLimiter(0, 1)
	for i := 0; i < 1000; i++ {
		res := atZero.Reserve()
		if !res.OK() {
			println(fmt.Sprintf("Reservation %d denied, as expected", i))
			return
		}
		if delay := res.Delay(); delay != 0 {
			println(fmt.Sprintf("Reservation %d delay not zero (%v), as expected", i, delay))
			return
		}
	}
	t.Fatal("zero rate limiter allows unlimited reservations")
}
func TestReserveAtAlmostZero(t *testing.T) {
	almostAtZero := NewLimiter(0.00001, 1)
	for i := 0; i < 1000; i++ {
		res := almostAtZero.Reserve()
		if !res.OK() {
			println(fmt.Sprintf("Reservation denied, as expected, at %d", i))
			return
		}
		if delay := res.Delay(); delay != 0 {
			println(fmt.Sprintf("Reservation %d delay not zero (%v), as expected", i, delay))
			return
		}
	}
	t.Fatal("almost zero rate limiter allows unlimited reservations")
}
% go test -run TestReserveAtAlmostZero
Reservation 1 delay not zero (27h46m39.999999087s), as expected
PASS
ok  	golang.org/x/time/rate	0.128s
% go test -run TestReserveAtZero
--- FAIL: TestReserveAtZero (0.00s)
    rate_test.go:34: zero rate limiter allows unlimited reservations
FAIL
exit status 1
FAIL	golang.org/x/time/rate	0.262s

The behaviour at zero happens afaict because in:

// durationFromTokens is a unit conversion function from the number of tokens to the duration
// of time it takes to accumulate them at a rate of limit tokens per second.
func (limit Limit) durationFromTokens(tokens float64) time.Duration {
	seconds := tokens / float64(limit)
	return time.Nanosecond * time.Duration(1e9*seconds)
}

there is no safeguard for a division by a limit at zero, which means seconds is then Inf. Then it gets "worse" because the final operation is an overflow, so the returned number is a huge negative (-9223372036854775808).

Then in reserveN, we have:

	if tokens < 0 {
		waitDuration = lim.limit.durationFromTokens(-tokens)
	}

	// Decide result
	ok := n <= lim.burst && waitDuration <= maxFutureReserve

which results in the reservation being ok, because of the huge negative.

And in addition, in DelayFrom, we have:

	delay := r.timeToAct.Sub(now)
	if delay < 0 {
		return 0
	}

which explains why we always get a zero delay instead of an increasingly large delay when we pile on the reservations on the Limiter.

So in summary, I think we have

  1. a problem with the behaviour of Reserve, which imho should always return non ok reservation if it is on a Limiter that was initialized with a zero Limit
  2. a bug that in the implementation of durationFromTokens (or before in the flow), which allows a division by zero, which at least partially explains the above problem with Reserve (and Delay).

What did you expect to see?

I expected Reserve to return a non-ok reservation on a Limiter initialized with a zero Limit. And if not, I would at least expect the resulting reservation to not have a delay of zero.

What did you see instead?

Reserve returns an ok reservation, with a zero delay.

@gopherbot gopherbot added this to the Unreleased milestone Jul 15, 2021
@cherrymui cherrymui added the NeedsInvestigation label Jul 15, 2021
@cherrymui
Copy link
Contributor

@cherrymui cherrymui commented Jul 15, 2021

@nishanths
Copy link

@nishanths nishanths commented Jul 18, 2021

Same underlying cause: #39984.

But this report additionally describes an issue with Reservation.Delay:

we always get a zero delay instead of an increasingly large delay when we pile on the reservations on the Limiter [...] And if not, I would at least expect the resulting reservation to not have a delay of zero.

@nishanths
Copy link

@nishanths nishanths commented Jul 18, 2021

CL https://go-review.googlesource.com/c/time/+/323429 mentions the linked issue, but hasn't been reviewed completely yet.

@nishanths
Copy link

@nishanths nishanths commented Jul 18, 2021

@mpl: I agree with the overall issue. But not the following:

Reserve, which imho should always return non ok reservation if it is on a Limiter that was initialized with a zero Limit

I don't think this would be correct based on the existing Limiter docs, copied below. Particularly, the burst must also be considered; it is not sufficient to consider only the zero Limit and return a non-ok reservation. So the first call to Reserve, even with a zero Limiter, should return an ok reservation if the burst > 0.

A Limiter controls how frequently events are allowed to happen. It implements a "token bucket" of size b, initially full and refilled at rate r tokens per second.

@mpl
Copy link
Contributor Author

@mpl mpl commented Jul 18, 2021

@Sajmani
Copy link
Contributor

@Sajmani Sajmani commented Jul 29, 2021

We should certainly fix the division by zero (#2 in your summary).
I'm less certain about changing the behavior of Reserve (#1); it's not clear whether that's a backwards-compatible change (while x/time is not necessarily covered by the Go 1 compatibility guarantee, the rate package is widely used that we should take care not to break existing users).

@mpl
Copy link
Contributor Author

@mpl mpl commented Jul 29, 2021

@Sajmani just as one data point, in https://github.com/traefik/traefik we are one of these users of Reserve (and we actually rely on the "broken" behaviour in question), but we'll be ready to adapt if the behaviour changes.

I personally think that the behaviour should change because it irks me that it does not behave consistently with how Allow does at zero, but I understand your concerns.
However, if we keep it as is, I think the doc should be clarified that Reserve is an exception in that way. Especially parts like "Limit defines the maximum frequency of some events. Limit is represented as number of events per second. A zero Limit allows no events." lead me to believe that all parts of the API (both Allow and Reserve) would behave similarly at zero. Until I read the code. :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation
Projects
None yet
Development

No branches or pull requests

5 participants