| // 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" |
| "gvisor.dev/gvisor/pkg/tcpip/header" |
| "gvisor.dev/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 |
| } |