x/time: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

mpl · 2021-07-15T15:48:44Z

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

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
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.

The text was updated successfully, but these errors were encountered:

cherrymui · 2021-07-15T22:12:01Z

cc @Sajmani

nishanths · 2021-07-18T17:25:14Z

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 · 2021-07-18T17:37:21Z

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

nishanths · 2021-07-18T17:48:25Z

@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 · 2021-07-18T17:54:29Z

Sure. Everything I said should of course take into account the burst as well.

…

On Sun, Jul 18, 2021, 19:48 Nishanth Shanmugham ***@***.***> wrote: @mpl <https://github.com/mpl>: 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: 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. 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. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#47221 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAEY3F5SFKMOP3IBSDPPHGTTYMHXLANCNFSM5AN2NWHA> .

Sajmani · 2021-07-29T12:36:24Z

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 · 2021-07-29T13:27:31Z

@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. :-)

mpl · 2023-01-02T10:47:00Z

The root cause of this issue was fixed in f0f3c7e86c11ca8f8b99d970e28445dda0b41195 (https://go-review.googlesource.com/c/time/+/323429) so as far as I'm concerned we can clean things up now.
Thanks!

gopherbot added this to the Unreleased milestone Jul 15, 2021

cherrymui added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 15, 2021

amwolff mentioned this issue Aug 19, 2021

x/time/rate: Wait's behaviour is inconsistent when the limit is 0 (tested on darwin/arm64 and linux/amd64) #47817

Closed

mpl mentioned this issue Dec 27, 2022

Prevent from no rate limiting when average is zero traefik/traefik#9621

Merged

2 tasks

mpl closed this as completed Jan 2, 2023

golang locked and limited conversation to collaborators Jan 2, 2024

gopherbot added the FrozenDueToAge label Jan 2, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

x/time: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

x/time: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

mpl commented Jul 15, 2021 •

edited

cherrymui commented Jul 15, 2021

nishanths commented Jul 18, 2021 •

edited

nishanths commented Jul 18, 2021 •

edited

nishanths commented Jul 18, 2021 •

edited

mpl commented Jul 18, 2021 via email

Sajmani commented Jul 29, 2021

mpl commented Jul 29, 2021

mpl commented Jan 2, 2023

x/time: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

x/time: Reserve on zero rate limiter allows infinite reservations (because of divide by zero) #47221

Comments

mpl commented Jul 15, 2021 • edited

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

cherrymui commented Jul 15, 2021

nishanths commented Jul 18, 2021 • edited

nishanths commented Jul 18, 2021 • edited

nishanths commented Jul 18, 2021 • edited

mpl commented Jul 18, 2021 via email

Sajmani commented Jul 29, 2021

mpl commented Jul 29, 2021

mpl commented Jan 2, 2023

mpl commented Jul 15, 2021 •

edited

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

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

nishanths commented Jul 18, 2021 •

edited

nishanths commented Jul 18, 2021 •

edited

nishanths commented Jul 18, 2021 •

edited