1/*
2Copyright 2015 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package flowcontrol
18
19import (
20	"sync"
21	"time"
22
23	"k8s.io/apimachinery/pkg/util/clock"
24	"k8s.io/utils/integer"
25)
26
27type backoffEntry struct {
28	backoff    time.Duration
29	lastUpdate time.Time
30}
31
32type Backoff struct {
33	sync.RWMutex
34	Clock           clock.Clock
35	defaultDuration time.Duration
36	maxDuration     time.Duration
37	perItemBackoff  map[string]*backoffEntry
38}
39
40func NewFakeBackOff(initial, max time.Duration, tc *clock.FakeClock) *Backoff {
41	return &Backoff{
42		perItemBackoff:  map[string]*backoffEntry{},
43		Clock:           tc,
44		defaultDuration: initial,
45		maxDuration:     max,
46	}
47}
48
49func NewBackOff(initial, max time.Duration) *Backoff {
50	return &Backoff{
51		perItemBackoff:  map[string]*backoffEntry{},
52		Clock:           clock.RealClock{},
53		defaultDuration: initial,
54		maxDuration:     max,
55	}
56}
57
58// Get the current backoff Duration
59func (p *Backoff) Get(id string) time.Duration {
60	p.RLock()
61	defer p.RUnlock()
62	var delay time.Duration
63	entry, ok := p.perItemBackoff[id]
64	if ok {
65		delay = entry.backoff
66	}
67	return delay
68}
69
70// move backoff to the next mark, capping at maxDuration
71func (p *Backoff) Next(id string, eventTime time.Time) {
72	p.Lock()
73	defer p.Unlock()
74	entry, ok := p.perItemBackoff[id]
75	if !ok || hasExpired(eventTime, entry.lastUpdate, p.maxDuration) {
76		entry = p.initEntryUnsafe(id)
77	} else {
78		delay := entry.backoff * 2 // exponential
79		entry.backoff = time.Duration(integer.Int64Min(int64(delay), int64(p.maxDuration)))
80	}
81	entry.lastUpdate = p.Clock.Now()
82}
83
84// Reset forces clearing of all backoff data for a given key.
85func (p *Backoff) Reset(id string) {
86	p.Lock()
87	defer p.Unlock()
88	delete(p.perItemBackoff, id)
89}
90
91// Returns True if the elapsed time since eventTime is smaller than the current backoff window
92func (p *Backoff) IsInBackOffSince(id string, eventTime time.Time) bool {
93	p.RLock()
94	defer p.RUnlock()
95	entry, ok := p.perItemBackoff[id]
96	if !ok {
97		return false
98	}
99	if hasExpired(eventTime, entry.lastUpdate, p.maxDuration) {
100		return false
101	}
102	return p.Clock.Since(eventTime) < entry.backoff
103}
104
105// Returns True if time since lastupdate is less than the current backoff window.
106func (p *Backoff) IsInBackOffSinceUpdate(id string, eventTime time.Time) bool {
107	p.RLock()
108	defer p.RUnlock()
109	entry, ok := p.perItemBackoff[id]
110	if !ok {
111		return false
112	}
113	if hasExpired(eventTime, entry.lastUpdate, p.maxDuration) {
114		return false
115	}
116	return eventTime.Sub(entry.lastUpdate) < entry.backoff
117}
118
119// Garbage collect records that have aged past maxDuration. Backoff users are expected
120// to invoke this periodically.
121func (p *Backoff) GC() {
122	p.Lock()
123	defer p.Unlock()
124	now := p.Clock.Now()
125	for id, entry := range p.perItemBackoff {
126		if now.Sub(entry.lastUpdate) > p.maxDuration*2 {
127			// GC when entry has not been updated for 2*maxDuration
128			delete(p.perItemBackoff, id)
129		}
130	}
131}
132
133func (p *Backoff) DeleteEntry(id string) {
134	p.Lock()
135	defer p.Unlock()
136	delete(p.perItemBackoff, id)
137}
138
139// Take a lock on *Backoff, before calling initEntryUnsafe
140func (p *Backoff) initEntryUnsafe(id string) *backoffEntry {
141	entry := &backoffEntry{backoff: p.defaultDuration}
142	p.perItemBackoff[id] = entry
143	return entry
144}
145
146// After 2*maxDuration we restart the backoff factor to the beginning
147func hasExpired(eventTime time.Time, lastUpdate time.Time, maxDuration time.Duration) bool {
148	return eventTime.Sub(lastUpdate) > maxDuration*2 // consider stable if it's ok for twice the maxDuration
149}
150