Fixed integer overflow bug in rate limiter. #31396

foxish · 2016-08-25T00:30:50Z

Fix overflow issue in controller-manager rate limiter

This PR fixes a bug in the delayed work-queue used by some controllers.
The integer overflow bug would previously cause hotlooping behavior after a few failures
as time.Duration(..) on values larger than MaxInt64 behaves unpredictably, and
after a certain value returns 0 always.

cc @bprashanth @pwittrock

This change is

bprashanth · 2016-08-25T01:44:12Z

pkg/util/workqueue/default_rate_limiters.go

+	// The maximum exponent maxExp is chosen such that the 'calculated' value never
+	// exceeds MaxInt64.
+	maxExp := int(math.Log10(float64(math.MaxInt64)/float64(r.baseDelay.Nanoseconds())) - 1)
+	if exp > maxExp {


Hmm, maybe just cap it? the probelm is that time.Duration can't handle the float right

backoff := math.Pod10(r.failures[items]) if backoff >= math.MaxInt64 { return r.maxDelay }

Done, simplified with an early return.

bprashanth · 2016-08-25T01:44:25Z

Just the one nit, thanks

k8s-bot · 2016-08-25T02:34:21Z

GCE e2e build/test passed for commit 00e4188.

pwittrock · 2016-08-25T03:06:52Z

Review status: 0 of 2 files reviewed at latest revision, 3 unresolved discussions.

pkg/util/workqueue/default_rate_limiters.go, line 97 [r2] (raw file):

  // The backoff is capped such that 'calculated' value never overflows.
  backoff := float64(r.baseDelay.Nanoseconds()) * math.Pow10(exp)

I am surprised the exponent base is not 2 at the most. 10 seems really really steep (100 ms -> 1 s -> 10 s -> 100 s -> 1000s).

pkg/util/workqueue/default_rate_limiters.go, line 98 [r2] (raw file):

  // The backoff is capped such that 'calculated' value never overflows.
  backoff := float64(r.baseDelay.Nanoseconds()) * math.Pow10(exp)
  if backoff > math.MaxInt64 {

I wonder what we should do here. I suspect the item probably shouldn't even be enqueued at this point. FWIW MaxInt64 in ns is ~500 Years. Will probably do a master upgrade before the duration expires :)

FWIW, I always liked this rater limiter implementation https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/RateLimiter.java

Comments from Reviewable

pwittrock · 2016-08-25T03:07:55Z

Review status: 0 of 2 files reviewed at latest revision, 4 unresolved discussions.

pkg/util/workqueue/default_rate_limiters.go, line 97 [r2] (raw file):

  // The backoff is capped such that 'calculated' value never overflows.
  backoff := float64(r.baseDelay.Nanoseconds()) * math.Pow10(exp)

We could potentially just short circuit this whole thing and say if the exp > 20, return or something.

Comments from Reviewable

foxish · 2016-08-25T03:44:45Z

pkg/util/workqueue/default_rate_limiters.go, line 98 [r2] (raw file):

Previously, pwittrock (Phillip Wittrock) wrote…

I wonder what we should do here. I suspect the item probably shouldn't even be enqueued at this point. FWIW MaxInt64 in ns is ~500 Years. Will probably do a master upgrade before the duration expires :)

FWIW, I always liked this rater limiter implementation https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/RateLimiter.java

We cap the wait duration to maxDelay, which is typically 1000s (16 mins), so, we don't ever wait for that long, so, I don't think this is hit because of an error condition.

Comments from Reviewable

foxish · 2016-08-25T03:56:09Z

pkg/util/workqueue/default_rate_limiters.go, line 97 [r2] (raw file):

Previously, pwittrock (Phillip Wittrock) wrote…

We could potentially just short circuit this whole thing and say if the exp > 20, return or something.

I feel that is more brittle because it's the product of the baseDelay with the exp that we're checking. If the baseDelay is bigger, we might overflow before we hit 20 for example.

Comments from Reviewable

deads2k · 2016-08-25T12:00:24Z

I don't have a 2 vs 10 preference.

lgtm. Seems like this should be 1.4.

smarterclayton · 2016-08-25T14:47:38Z

This may be cherry pick candidate?

pwittrock · 2016-08-25T15:36:06Z

@deads2k I agree that this should be in 1.4. Conviniently I am the release czar that gets to make those decisions :)
@smarterclayton Do you mean cherry pick into 1.3? I am hoping we can get this into 1.4 during the code slush.

pwittrock · 2016-08-25T15:50:47Z

Reviewed 1 of 2 files at r1.
Review status: 0 of 2 files reviewed at latest revision, 4 unresolved discussions.

Comments from Reviewable

smarterclayton · 2016-08-25T15:51:01Z

Yes, 1.3. The symptom seemed like something that could affect us in 1.3 - I thought we converted a few of the core controllers to delaying wait queues before 1.3 shipped.

pwittrock · 2016-08-25T15:51:52Z

+lgtm

Reviewed 1 of 2 files at r1.
Review status: 1 of 2 files reviewed at latest revision, 4 unresolved discussions.

Comments from Reviewable

pwittrock · 2016-08-25T16:04:24Z

@foxish Thanks

k8s-github-robot · 2016-08-25T17:16:18Z

@k8s-bot test this [submit-queue is verifying that this PR is safe to merge]

lavalamp · 2016-08-25T17:50:50Z

pkg/util/workqueue/default_rate_limiters.go

-	calculated := r.baseDelay * time.Duration(math.Pow10(r.failures[item]-1))
+	// The backoff is capped such that 'calculated' value never overflows.
+	backoff := float64(r.baseDelay.Nanoseconds()) * math.Pow10(exp)
+	if backoff > math.MaxInt64 {


Please cap exp before the Pow10 instead of doing a float64 comparison.

Yeah sorry didn't catch this last night. Youre implicitly converting maxint64 into a float larger than maxint64. You can early return with something like exp >= int64(math.Log10(math.MaxInt64)) instaed.

Ack. Will follow up with another PR fixing this.

k8s-bot · 2016-08-25T18:17:12Z

GCE e2e build/test passed for commit 00e4188.

k8s-github-robot · 2016-08-25T18:17:38Z

Automatic merge from submit-queue

Automatic merge from submit-queue Petset hotlooping issue. Part of the fix for #27634 It completely fixes it when we also get #31396 merged.

Automatic merge from submit-queue Bump glbc to 0.8.0 Don't think this hits the bar for 1.4.0, but hopefully it can make 1.4.1. The version bump is for the godep update that fixes an issue with the throttling workqueue (kubernetes/kubernetes#31396). I should've done this sooner, dropped it. Also fixes #1776 and #1783

Automatic merge from submit-queue Bump glbc to 0.8.0 Don't think this hits the bar for 1.4.0, but hopefully it can make 1.4.1. The version bump is for the godep update that fixes an issue with the throttling workqueue (kubernetes/kubernetes#31396). I should've done this sooner, dropped it. Also fixes kubernetes-retired#1776 and kubernetes-retired#1783

foxish added the kind/bug Categorizes issue or PR as related to a bug. label Aug 25, 2016

foxish assigned deads2k Aug 25, 2016

googlebot added the cla: yes label Aug 25, 2016

foxish added the area/controller-manager label Aug 25, 2016

k8s-github-robot added size/M Denotes a PR that changes 30-99 lines, ignoring generated files. release-note-label-needed labels Aug 25, 2016

bprashanth reviewed Aug 25, 2016
View reviewed changes

k8s-github-robot mentioned this pull request Aug 25, 2016

[k8s.io] ScheduledJob should replace jobs when ReplaceConcurrent {Kubernetes e2e suite} #30542

Closed

Fixed integer overflow bug in rate limiter.

00e4188

foxish force-pushed the integer-overflow branch from 9811ee2 to 00e4188 Compare August 25, 2016 01:55

foxish mentioned this pull request Aug 25, 2016

Petset hotlooping issue. #31406

Merged

k8s-github-robot mentioned this pull request Aug 25, 2016

[k8s.io] ScheduledJob should not schedule new jobs when ForbidConcurrent {Kubernetes e2e suite} #30549

Closed

pwittrock added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 25, 2016

pwittrock added this to the v1.4 milestone Aug 25, 2016

k8s-github-robot added the do-not-merge DEPRECATED. Indicates that a PR should not merge. Label can only be manually applied/removed. label Aug 25, 2016

pwittrock added release-note Denotes a PR that will be considered when it comes time to generate release notes. and removed release-note-label-needed do-not-merge DEPRECATED. Indicates that a PR should not merge. Label can only be manually applied/removed. labels Aug 25, 2016

pwittrock added the priority/important-soon Must be staffed and worked on either currently, or very soon, ideally in time for the next release. label Aug 25, 2016

foxish mentioned this pull request Aug 25, 2016

cluster-autoscaler, ingress, keepalived-vip: update vendored work-queue kubernetes-retired/contrib#1623

Closed

lavalamp reviewed Aug 25, 2016
View reviewed changes

k8s-github-robot merged commit c63cd8f into kubernetes:master Aug 25, 2016

k8s-github-robot pushed a commit that referenced this pull request Aug 26, 2016

Merge pull request #31406 from foxish/petset-hotloop

f0bc7d4

Automatic merge from submit-queue Petset hotlooping issue. Part of the fix for #27634 It completely fixes it when we also get #31396 merged.

bprashanth mentioned this pull request Sep 22, 2016

Bump glbc to 0.8.0 kubernetes-retired/contrib#1771

Merged

foxish deleted the integer-overflow branch May 16, 2019 22:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fixed integer overflow bug in rate limiter. #31396

Fixed integer overflow bug in rate limiter. #31396

foxish commented Aug 25, 2016 •

edited by pwittrock

Loading

bprashanth Aug 25, 2016

foxish Aug 25, 2016

bprashanth commented Aug 25, 2016

k8s-bot commented Aug 25, 2016

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

foxish commented Aug 25, 2016

foxish commented Aug 25, 2016

deads2k commented Aug 25, 2016

smarterclayton commented Aug 25, 2016

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

smarterclayton commented Aug 25, 2016 via email

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

k8s-github-robot commented Aug 25, 2016

lavalamp Aug 25, 2016

bprashanth Aug 25, 2016

foxish Aug 25, 2016

k8s-bot commented Aug 25, 2016

k8s-github-robot commented Aug 25, 2016

Fixed integer overflow bug in rate limiter. #31396

Fixed integer overflow bug in rate limiter. #31396

Conversation

foxish commented Aug 25, 2016 • edited by pwittrock Loading

bprashanth Aug 25, 2016

Choose a reason for hiding this comment

foxish Aug 25, 2016

Choose a reason for hiding this comment

bprashanth commented Aug 25, 2016

k8s-bot commented Aug 25, 2016

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

foxish commented Aug 25, 2016

foxish commented Aug 25, 2016

deads2k commented Aug 25, 2016

smarterclayton commented Aug 25, 2016

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

smarterclayton commented Aug 25, 2016 via email

pwittrock commented Aug 25, 2016

pwittrock commented Aug 25, 2016

k8s-github-robot commented Aug 25, 2016

lavalamp Aug 25, 2016

Choose a reason for hiding this comment

bprashanth Aug 25, 2016

Choose a reason for hiding this comment

foxish Aug 25, 2016

Choose a reason for hiding this comment

k8s-bot commented Aug 25, 2016

k8s-github-robot commented Aug 25, 2016

foxish commented Aug 25, 2016 •

edited by pwittrock

Loading