1 /* 2 Copyright 2014 The Kubernetes Authors. 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 // Package wait is a subset of k8s.io/apimachinery to avoid conflicts 18 // in dependencies (specifically, logging). 19 package wait 20 21 import ( 22 "errors" 23 "math/rand" 24 "time" 25 ) 26 27 // Jitter returns a time.Duration between duration and duration + maxFactor * 28 // duration. 29 // 30 // This allows clients to avoid converging on periodic behavior. If maxFactor 31 // is 0.0, a suggested default value will be chosen. 32 func Jitter(duration time.Duration, maxFactor float64) time.Duration { 33 if maxFactor <= 0.0 { 34 maxFactor = 1.0 35 } 36 wait := duration + time.Duration(rand.Float64()*maxFactor*float64(duration)) 37 return wait 38 } 39 40 // ErrWaitTimeout is returned when the condition exited without success. 41 var ErrWaitTimeout = errors.New("timed out waiting for the condition") 42 43 // ConditionFunc returns true if the condition is satisfied, or an error 44 // if the loop should be aborted. 45 type ConditionFunc func() (done bool, err error) 46 47 // Backoff holds parameters applied to a Backoff function. 48 type Backoff struct { 49 // The initial duration. 50 Duration time.Duration 51 // Duration is multiplied by factor each iteration, if factor is not zero 52 // and the limits imposed by Steps and Cap have not been reached. 53 // Should not be negative. 54 // The jitter does not contribute to the updates to the duration parameter. 55 Factor float64 56 // The sleep at each iteration is the duration plus an additional 57 // amount chosen uniformly at random from the interval between 58 // zero and `jitter*duration`. 59 Jitter float64 60 // The remaining number of iterations in which the duration 61 // parameter may change (but progress can be stopped earlier by 62 // hitting the cap). If not positive, the duration is not 63 // changed. Used for exponential backoff in combination with 64 // Factor and Cap. 65 Steps int 66 // A limit on revised values of the duration parameter. If a 67 // multiplication by the factor parameter would make the duration 68 // exceed the cap then the duration is set to the cap and the 69 // steps parameter is set to zero. 70 Cap time.Duration 71 } 72 73 // Step (1) returns an amount of time to sleep determined by the 74 // original Duration and Jitter and (2) mutates the provided Backoff 75 // to update its Steps and Duration. 76 func (b *Backoff) Step() time.Duration { 77 if b.Steps < 1 { 78 if b.Jitter > 0 { 79 return Jitter(b.Duration, b.Jitter) 80 } 81 return b.Duration 82 } 83 b.Steps-- 84 85 duration := b.Duration 86 87 // calculate the next step 88 if b.Factor != 0 { 89 b.Duration = time.Duration(float64(b.Duration) * b.Factor) 90 if b.Cap > 0 && b.Duration > b.Cap { 91 b.Duration = b.Cap 92 b.Steps = 0 93 } 94 } 95 96 if b.Jitter > 0 { 97 duration = Jitter(duration, b.Jitter) 98 } 99 return duration 100 } 101 102 // ExponentialBackoff repeats a condition check with exponential backoff. 103 // 104 // It repeatedly checks the condition and then sleeps, using `backoff.Step()` 105 // to determine the length of the sleep and adjust Duration and Steps. 106 // Stops and returns as soon as: 107 // 1. the condition check returns true or an error, 108 // 2. `backoff.Steps` checks of the condition have been done, or 109 // 3. a sleep truncated by the cap on duration has been completed. 110 // In case (1) the returned error is what the condition function returned. 111 // In all other cases, ErrWaitTimeout is returned. 112 func ExponentialBackoff(backoff Backoff, condition ConditionFunc) error { 113 for backoff.Steps > 0 { 114 if ok, err := condition(); err != nil || ok { 115 return err 116 } 117 if backoff.Steps == 1 { 118 break 119 } 120 time.Sleep(backoff.Step()) 121 } 122 return ErrWaitTimeout 123 } 124