-
Notifications
You must be signed in to change notification settings - Fork 346
/
priorityqueue.go
147 lines (128 loc) · 4.75 KB
/
priorityqueue.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Copyright 2021 Antrea Authors
//
// Licensed under the Apache License, Version 2.0 (the “License”);
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an “AS IS” BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package priorityqueue
import (
"container/heap"
"time"
"antrea.io/antrea/pkg/agent/flowexporter"
)
// minExpiryTime provides two usages: 1. We want to avoid passing a non positive
// value to ticker 2. We want to avoid processing a single expired item per call.
// If multiple items have very close expiry time(<100ms), by adding a small constant,
// we can make these items expired and process in one call.
const minExpiryTime = 100 * time.Millisecond
type ExpirePriorityQueue struct {
items []*flowexporter.ItemToExpire
ActiveFlowTimeout time.Duration
IdleFlowTimeout time.Duration
KeyToItem map[flowexporter.ConnectionKey]*flowexporter.ItemToExpire
}
func NewExpirePriorityQueue(activeFlowTimeout time.Duration, idleFlowTimeout time.Duration) *ExpirePriorityQueue {
return &ExpirePriorityQueue{
items: make([]*flowexporter.ItemToExpire, 0),
ActiveFlowTimeout: activeFlowTimeout,
IdleFlowTimeout: idleFlowTimeout,
KeyToItem: make(map[flowexporter.ConnectionKey]*flowexporter.ItemToExpire),
}
}
func (pq *ExpirePriorityQueue) Len() int {
return len(pq.items)
}
func (pq *ExpirePriorityQueue) minExpireTime(i int) time.Time {
if pq.items[i].ActiveExpireTime.Before(pq.items[i].IdleExpireTime) {
return pq.items[i].ActiveExpireTime
} else {
return pq.items[i].IdleExpireTime
}
}
func (pq *ExpirePriorityQueue) Less(i, j int) bool {
return pq.minExpireTime(i).Before(pq.minExpireTime(j))
}
func (pq *ExpirePriorityQueue) Swap(i, j int) {
pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
pq.items[i].Index = i
pq.items[j].Index = j
}
func (pq *ExpirePriorityQueue) Push(x interface{}) {
n := len((*pq).items)
item := x.(*flowexporter.ItemToExpire)
item.Index = n
(*pq).items = append((*pq).items, item)
}
func (pq *ExpirePriorityQueue) Pop() interface{} {
n := len((*pq).items)
item := ((*pq).items)[n-1]
item.Index = -1
(*pq).items = ((*pq).items)[0:(n - 1)]
return item
}
// Peek returns the item at the beginning of the queue, without removing the
// item or otherwise mutating the queue. It is safe to call directly.
func (pq *ExpirePriorityQueue) Peek() *flowexporter.ItemToExpire {
if pq.Len() == 0 {
return nil
}
return pq.items[0]
}
// Update modifies the priority of an Item in the queue.
func (pq *ExpirePriorityQueue) Update(item *flowexporter.ItemToExpire, activeExpireTime time.Time, idleExpireTime time.Time) {
item.ActiveExpireTime = activeExpireTime
item.IdleExpireTime = idleExpireTime
heap.Fix(pq, item.Index)
}
// GetExpiryFromExpirePriorityQueue returns the shortest expire time duration
// from expire priority queue.
func (pq *ExpirePriorityQueue) GetExpiryFromExpirePriorityQueue() time.Duration {
currTime := time.Now()
if pq.Len() > 0 {
// Get the minExpireTime of the top item in ExpirePriorityQueue.
expiryDuration := minExpiryTime + pq.minExpireTime(0).Sub(currTime)
if expiryDuration < 0 {
return minExpiryTime
}
return expiryDuration
}
if pq.ActiveFlowTimeout < pq.IdleFlowTimeout {
return pq.ActiveFlowTimeout
}
return pq.IdleFlowTimeout
}
func (pq *ExpirePriorityQueue) AddItemToQueue(connKey flowexporter.ConnectionKey, conn *flowexporter.Connection) {
currTime := time.Now()
pqItem := &flowexporter.ItemToExpire{
Conn: conn,
ActiveExpireTime: currTime.Add(pq.ActiveFlowTimeout),
IdleExpireTime: currTime.Add(pq.IdleFlowTimeout),
}
heap.Push(pq, pqItem)
pq.KeyToItem[connKey] = pqItem
}
func (pq *ExpirePriorityQueue) ResetActiveExpireTimeAndPush(pqItem *flowexporter.ItemToExpire, currTime time.Time) {
pqItem.ActiveExpireTime = currTime.Add(pq.ActiveFlowTimeout)
heap.Push(pq, pqItem)
}
func (pq *ExpirePriorityQueue) RemoveItemFromMap(conn *flowexporter.Connection) {
connKey := flowexporter.NewConnectionKey(conn)
delete(pq.KeyToItem, connKey)
}
func (pq *ExpirePriorityQueue) GetTopExpiredItem(currTime time.Time) *flowexporter.ItemToExpire {
// If the queue is empty or top item is not timeout, then we do not have to
// check the following items.
topItem := pq.Peek()
if topItem == nil || (topItem.ActiveExpireTime.After(currTime) && topItem.IdleExpireTime.After(currTime)) {
return nil
}
pqItem := heap.Pop(pq).(*flowexporter.ItemToExpire)
return pqItem
}