1// +build !providerless
2
3/*
4Copyright 2019 The Kubernetes Authors.
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10    http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17*/
18
19package retry
20
21import (
22	"math/rand"
23	"net/http"
24	"strings"
25	"time"
26
27	"github.com/Azure/go-autorest/autorest"
28	"github.com/Azure/go-autorest/autorest/mocks"
29	"k8s.io/klog/v2"
30)
31
32// Ensure package autorest/mocks is imported and vendored.
33var _ autorest.Sender = mocks.NewSender()
34
35// Backoff holds parameters applied to a Backoff function.
36type Backoff struct {
37	// The initial duration.
38	Duration time.Duration
39	// Duration is multiplied by factor each iteration, if factor is not zero
40	// and the limits imposed by Steps and Cap have not been reached.
41	// Should not be negative.
42	// The jitter does not contribute to the updates to the duration parameter.
43	Factor float64
44	// The sleep at each iteration is the duration plus an additional
45	// amount chosen uniformly at random from the interval between
46	// zero and `jitter*duration`.
47	Jitter float64
48	// The remaining number of iterations in which the duration
49	// parameter may change (but progress can be stopped earlier by
50	// hitting the cap). If not positive, the duration is not
51	// changed. Used for exponential backoff in combination with
52	// Factor and Cap.
53	Steps int
54	// A limit on revised values of the duration parameter. If a
55	// multiplication by the factor parameter would make the duration
56	// exceed the cap then the duration is set to the cap and the
57	// steps parameter is set to zero.
58	Cap time.Duration
59	// The errors indicate that the request shouldn't do more retrying.
60	NonRetriableErrors []string
61	// The RetriableHTTPStatusCodes indicates that the HTTPStatusCode should do more retrying.
62	RetriableHTTPStatusCodes []int
63}
64
65// NewBackoff creates a new Backoff.
66func NewBackoff(duration time.Duration, factor float64, jitter float64, steps int, cap time.Duration) *Backoff {
67	return &Backoff{
68		Duration: duration,
69		Factor:   factor,
70		Jitter:   jitter,
71		Steps:    steps,
72		Cap:      cap,
73	}
74}
75
76// WithNonRetriableErrors returns a new *Backoff with NonRetriableErrors assigned.
77func (b *Backoff) WithNonRetriableErrors(errs []string) *Backoff {
78	newBackoff := *b
79	newBackoff.NonRetriableErrors = errs
80	return &newBackoff
81}
82
83// WithRetriableHTTPStatusCodes returns a new *Backoff with RetriableHTTPStatusCode assigned.
84func (b *Backoff) WithRetriableHTTPStatusCodes(httpStatusCodes []int) *Backoff {
85	newBackoff := *b
86	newBackoff.RetriableHTTPStatusCodes = httpStatusCodes
87	return &newBackoff
88}
89
90// isNonRetriableError returns true if the Error is one of NonRetriableErrors.
91func (b *Backoff) isNonRetriableError(rerr *Error) bool {
92	if rerr == nil {
93		return false
94	}
95
96	for _, err := range b.NonRetriableErrors {
97		if strings.Contains(rerr.RawError.Error(), err) {
98			return true
99		}
100	}
101
102	return false
103}
104
105// Step (1) returns an amount of time to sleep determined by the
106// original Duration and Jitter and (2) mutates the provided Backoff
107// to update its Steps and Duration.
108func (b *Backoff) Step() time.Duration {
109	if b.Steps < 1 {
110		if b.Jitter > 0 {
111			return jitter(b.Duration, b.Jitter)
112		}
113		return b.Duration
114	}
115	b.Steps--
116
117	duration := b.Duration
118
119	// calculate the next step
120	if b.Factor != 0 {
121		b.Duration = time.Duration(float64(b.Duration) * b.Factor)
122		if b.Cap > 0 && b.Duration > b.Cap {
123			b.Duration = b.Cap
124			b.Steps = 0
125		}
126	}
127
128	if b.Jitter > 0 {
129		duration = jitter(duration, b.Jitter)
130	}
131	return duration
132}
133
134// Jitter returns a time.Duration between duration and duration + maxFactor *
135// duration.
136//
137// This allows clients to avoid converging on periodic behavior. If maxFactor
138// is 0.0, a suggested default value will be chosen.
139func jitter(duration time.Duration, maxFactor float64) time.Duration {
140	if maxFactor <= 0.0 {
141		maxFactor = 1.0
142	}
143	wait := duration + time.Duration(rand.Float64()*maxFactor*float64(duration))
144	return wait
145}
146
147// DoExponentialBackoffRetry represents an autorest.SendDecorator with backoff retry.
148func DoExponentialBackoffRetry(backoff *Backoff) autorest.SendDecorator {
149	return func(s autorest.Sender) autorest.Sender {
150		return autorest.SenderFunc(func(r *http.Request) (*http.Response, error) {
151			return doBackoffRetry(s, r, backoff)
152		})
153	}
154}
155
156// doBackoffRetry does the backoff retries for the request.
157func doBackoffRetry(s autorest.Sender, r *http.Request, backoff *Backoff) (resp *http.Response, err error) {
158	rr := autorest.NewRetriableRequest(r)
159	// Increment to add the first call (attempts denotes number of retries)
160	for backoff.Steps > 0 {
161		err = rr.Prepare()
162		if err != nil {
163			return
164		}
165		resp, err = s.Do(rr.Request())
166		rerr := GetErrorWithRetriableHTTPStatusCodes(resp, err, backoff.RetriableHTTPStatusCodes)
167		// Abort retries in the following scenarios:
168		// 1) request succeed
169		// 2) request is not retriable
170		// 3) request has been throttled
171		// 4) request contains non-retriable errors
172		// 5) request has completed all the retry steps
173		if rerr == nil || !rerr.Retriable || rerr.IsThrottled() || backoff.isNonRetriableError(rerr) || backoff.Steps == 1 {
174			return resp, rerr.Error()
175		}
176
177		if !delayForBackOff(backoff, r.Context().Done()) {
178			if r.Context().Err() != nil {
179				return resp, r.Context().Err()
180			}
181			return resp, rerr.Error()
182		}
183
184		klog.V(3).Infof("Backoff retrying %s %q with error %v", r.Method, r.URL.String(), rerr)
185	}
186
187	return resp, err
188}
189
190// delayForBackOff invokes time.After for the supplied backoff duration.
191// The delay may be canceled by closing the passed channel. If terminated early, returns false.
192func delayForBackOff(backoff *Backoff, cancel <-chan struct{}) bool {
193	d := backoff.Step()
194	select {
195	case <-time.After(d):
196		return true
197	case <-cancel:
198		return false
199	}
200}
201