forked from google/gvisor
/
sack_scoreboard.go
306 lines (280 loc) · 8.42 KB
/
sack_scoreboard.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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
// Copyright 2018 The gVisor 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 tcp
import (
"fmt"
"strings"
"github.com/google/btree"
"github.com/sagernet/gvisor/pkg/tcpip/header"
"github.com/sagernet/gvisor/pkg/tcpip/seqnum"
)
const (
// maxSACKBlocks is the maximum number of distinct SACKBlocks the
// scoreboard will track. Once there are 100 distinct blocks, new
// insertions will fail.
maxSACKBlocks = 100
// defaultBtreeDegree is set to 2 as btree.New(2) results in a 2-3-4
// tree.
defaultBtreeDegree = 2
)
// SACKScoreboard stores a set of disjoint SACK ranges.
//
// +stateify savable
type SACKScoreboard struct {
// smss is defined in RFC5681 as following:
//
// The SMSS is the size of the largest segment that the sender can
// transmit. This value can be based on the maximum transmission unit
// of the network, the path MTU discovery [RFC1191, RFC4821] algorithm,
// RMSS (see next item), or other factors. The size does not include
// the TCP/IP headers and options.
smss uint16
maxSACKED seqnum.Value
sacked seqnum.Size `state:"nosave"`
ranges *btree.BTree `state:"nosave"`
}
// NewSACKScoreboard returns a new SACK Scoreboard.
func NewSACKScoreboard(smss uint16, iss seqnum.Value) *SACKScoreboard {
return &SACKScoreboard{
smss: smss,
ranges: btree.New(defaultBtreeDegree),
maxSACKED: iss,
}
}
// Reset erases all known range information from the SACK scoreboard.
func (s *SACKScoreboard) Reset() {
s.ranges = btree.New(defaultBtreeDegree)
s.sacked = 0
}
// Insert inserts/merges the provided SACKBlock into the scoreboard.
func (s *SACKScoreboard) Insert(r header.SACKBlock) {
if s.ranges.Len() >= maxSACKBlocks {
return
}
// Check if we can merge the new range with a range before or after it.
var toDelete []btree.Item
if s.maxSACKED.LessThan(r.End - 1) {
s.maxSACKED = r.End - 1
}
s.ranges.AscendGreaterOrEqual(r, func(i btree.Item) bool {
if i == r {
return true
}
sacked := i.(header.SACKBlock)
// There is a hole between these two SACK blocks, so we can't
// merge anymore.
if r.End.LessThan(sacked.Start) {
return false
}
// There is some overlap at this point, merge the blocks and
// delete the other one.
//
// ----sS--------sE
// r.S---------------rE
// -------sE
if sacked.End.LessThan(r.End) {
// sacked is contained in the newly inserted range.
// Delete this block.
toDelete = append(toDelete, i)
return true
}
// sacked covers a range past end of the newly inserted
// block.
r.End = sacked.End
toDelete = append(toDelete, i)
return true
})
s.ranges.DescendLessOrEqual(r, func(i btree.Item) bool {
if i == r {
return true
}
sacked := i.(header.SACKBlock)
// sA------sE
// rA----rE
if sacked.End.LessThan(r.Start) {
return false
}
// The previous range extends into the current block. Merge it
// into the newly inserted range and delete the other one.
//
// <-rA---rE----<---rE--->
// sA--------------sE
r.Start = sacked.Start
// Extend r to cover sacked if sacked extends past r.
if r.End.LessThan(sacked.End) {
r.End = sacked.End
}
toDelete = append(toDelete, i)
return true
})
for _, i := range toDelete {
if sb := s.ranges.Delete(i); sb != nil {
sb := i.(header.SACKBlock)
s.sacked -= sb.Start.Size(sb.End)
}
}
replaced := s.ranges.ReplaceOrInsert(r)
if replaced == nil {
s.sacked += r.Start.Size(r.End)
}
}
// IsSACKED returns true if the a given range of sequence numbers denoted by r
// are already covered by SACK information in the scoreboard.
func (s *SACKScoreboard) IsSACKED(r header.SACKBlock) bool {
if s.Empty() {
return false
}
found := false
s.ranges.DescendLessOrEqual(r, func(i btree.Item) bool {
sacked := i.(header.SACKBlock)
if sacked.End.LessThan(r.Start) {
return false
}
if sacked.Contains(r) {
found = true
return false
}
return true
})
return found
}
// String returns human-readable state of the scoreboard structure.
func (s *SACKScoreboard) String() string {
var str strings.Builder
str.WriteString("SACKScoreboard: {")
s.ranges.Ascend(func(i btree.Item) bool {
str.WriteString(fmt.Sprintf("%v,", i))
return true
})
str.WriteString("}\n")
return str.String()
}
// Delete removes all SACK information prior to seq.
func (s *SACKScoreboard) Delete(seq seqnum.Value) {
if s.Empty() {
return
}
toDelete := []btree.Item{}
toInsert := []btree.Item{}
r := header.SACKBlock{seq, seq.Add(1)}
s.ranges.DescendLessOrEqual(r, func(i btree.Item) bool {
if i == r {
return true
}
sb := i.(header.SACKBlock)
toDelete = append(toDelete, i)
if sb.End.LessThanEq(seq) {
s.sacked -= sb.Start.Size(sb.End)
} else {
newSB := header.SACKBlock{seq, sb.End}
toInsert = append(toInsert, newSB)
s.sacked -= sb.Start.Size(seq)
}
return true
})
for _, sb := range toDelete {
s.ranges.Delete(sb)
}
for _, sb := range toInsert {
s.ranges.ReplaceOrInsert(sb)
}
}
// Copy provides a copy of the SACK scoreboard.
func (s *SACKScoreboard) Copy() (sackBlocks []header.SACKBlock, maxSACKED seqnum.Value) {
s.ranges.Ascend(func(i btree.Item) bool {
sackBlocks = append(sackBlocks, i.(header.SACKBlock))
return true
})
return sackBlocks, s.maxSACKED
}
// IsRangeLost implements the IsLost(SeqNum) operation defined in RFC 6675
// section 4 but operates on a range of sequence numbers and returns true if
// there are at least nDupAckThreshold SACK blocks greater than the range being
// checked or if at least (nDupAckThreshold-1)*s.smss bytes have been SACKED
// with sequence numbers greater than the block being checked.
func (s *SACKScoreboard) IsRangeLost(r header.SACKBlock) bool {
if s.Empty() {
return false
}
nDupSACK := 0
nDupSACKBytes := seqnum.Size(0)
isLost := false
// We need to check if the immediate lower (if any) sacked
// range contains or partially overlaps with r.
searchMore := true
s.ranges.DescendLessOrEqual(r, func(i btree.Item) bool {
sacked := i.(header.SACKBlock)
if sacked.Contains(r) {
searchMore = false
return false
}
if sacked.End.LessThanEq(r.Start) {
// all sequence numbers covered by sacked are below
// r so we continue searching.
return false
}
// There is a partial overlap. In this case we r.Start is
// between sacked.Start & sacked.End and r.End extends beyond
// sacked.End.
// Move r.Start to sacked.End and continuing searching blocks
// above r.Start.
r.Start = sacked.End
return false
})
if !searchMore {
return isLost
}
s.ranges.AscendGreaterOrEqual(r, func(i btree.Item) bool {
sacked := i.(header.SACKBlock)
if sacked.Contains(r) {
return false
}
nDupSACKBytes += sacked.Start.Size(sacked.End)
nDupSACK++
if nDupSACK >= nDupAckThreshold || nDupSACKBytes >= seqnum.Size((nDupAckThreshold-1)*s.smss) {
isLost = true
return false
}
return true
})
return isLost
}
// IsLost implements the IsLost(SeqNum) operation defined in RFC3517 section
// 4.
//
// This routine returns whether the given sequence number is considered to be
// lost. The routine returns true when either nDupAckThreshold discontiguous
// SACKed sequences have arrived above 'SeqNum' or (nDupAckThreshold * SMSS)
// bytes with sequence numbers greater than 'SeqNum' have been SACKed.
// Otherwise, the routine returns false.
func (s *SACKScoreboard) IsLost(seq seqnum.Value) bool {
return s.IsRangeLost(header.SACKBlock{seq, seq.Add(1)})
}
// Empty returns true if the SACK scoreboard has no entries, false otherwise.
func (s *SACKScoreboard) Empty() bool {
return s.ranges.Len() == 0
}
// Sacked returns the current number of bytes held in the SACK scoreboard.
func (s *SACKScoreboard) Sacked() seqnum.Size {
return s.sacked
}
// MaxSACKED returns the highest sequence number ever inserted in the SACK
// scoreboard.
func (s *SACKScoreboard) MaxSACKED() seqnum.Value {
return s.maxSACKED
}
// SMSS returns the sender's MSS as held by the SACK scoreboard.
func (s *SACKScoreboard) SMSS() uint16 {
return s.smss
}