1 /*
2  * Copyright (c) Facebook, Inc. and its affiliates.
3  *
4  * This source code is licensed under the MIT license found in the
5  * LICENSE file in the root directory of this source tree.
6  *
7  */
8 
9 #include <quic/state/QuicStateFunctions.h>
10 #include <quic/state/QuicStreamFunctions.h>
11 
12 #include <quic/common/TimeUtil.h>
13 
14 namespace {
15 std::deque<quic::OutstandingPacket>::reverse_iterator
getPreviousOutstandingPacket(quic::QuicConnectionStateBase & conn,quic::PacketNumberSpace packetNumberSpace,std::deque<quic::OutstandingPacket>::reverse_iterator from)16 getPreviousOutstandingPacket(
17     quic::QuicConnectionStateBase& conn,
18     quic::PacketNumberSpace packetNumberSpace,
19     std::deque<quic::OutstandingPacket>::reverse_iterator from) {
20   return std::find_if(
21       from, conn.outstandings.packets.rend(), [=](const auto& op) {
22         return !op.declaredLost &&
23             packetNumberSpace == op.packet.header.getPacketNumberSpace();
24       });
25 }
26 std::deque<quic::OutstandingPacket>::reverse_iterator
getPreviousOutstandingPacketIncludingLost(quic::QuicConnectionStateBase & conn,quic::PacketNumberSpace packetNumberSpace,std::deque<quic::OutstandingPacket>::reverse_iterator from)27 getPreviousOutstandingPacketIncludingLost(
28     quic::QuicConnectionStateBase& conn,
29     quic::PacketNumberSpace packetNumberSpace,
30     std::deque<quic::OutstandingPacket>::reverse_iterator from) {
31   return std::find_if(
32       from, conn.outstandings.packets.rend(), [=](const auto& op) {
33         return packetNumberSpace == op.packet.header.getPacketNumberSpace();
34       });
35 }
36 
37 } // namespace
38 
39 namespace quic {
40 
updateRtt(QuicConnectionStateBase & conn,std::chrono::microseconds rttSample,std::chrono::microseconds ackDelay)41 void updateRtt(
42     QuicConnectionStateBase& conn,
43     std::chrono::microseconds rttSample,
44     std::chrono::microseconds ackDelay) {
45   std::chrono::microseconds minRtt = timeMin(conn.lossState.mrtt, rttSample);
46   conn.lossState.maxAckDelay = timeMax(conn.lossState.maxAckDelay, ackDelay);
47   bool shouldUseAckDelay = (rttSample > ackDelay) &&
48       (rttSample > minRtt + ackDelay || conn.lossState.mrtt == kDefaultMinRtt);
49   if (shouldUseAckDelay) {
50     rttSample -= ackDelay;
51   }
52   // mrtt ignores ack delay. This is the same in the current recovery draft
53   // section A.6.
54   conn.lossState.mrtt = minRtt;
55   // We use the original minRtt without the ack delay included here
56   // explicitly. We might want to change this by including ackDelay
57   // as well.
58   conn.lossState.lrtt = rttSample;
59   if (conn.lossState.srtt == 0us) {
60     conn.lossState.srtt = rttSample;
61     conn.lossState.rttvar = rttSample / 2;
62   } else {
63     conn.lossState.rttvar = conn.lossState.rttvar * (kRttBeta - 1) / kRttBeta +
64         (conn.lossState.srtt > rttSample ? conn.lossState.srtt - rttSample
65                                          : rttSample - conn.lossState.srtt) /
66             kRttBeta;
67     conn.lossState.srtt = conn.lossState.srtt * (kRttAlpha - 1) / kRttAlpha +
68         rttSample / kRttAlpha;
69   }
70   if (conn.qLogger) {
71     conn.qLogger->addMetricUpdate(
72         rttSample, conn.lossState.mrtt, conn.lossState.srtt, ackDelay);
73   }
74 }
75 
updateAckSendStateOnRecvPacket(QuicConnectionStateBase & conn,AckState & ackState,bool pktOutOfOrder,bool pktHasRetransmittableData,bool pktHasCryptoData)76 void updateAckSendStateOnRecvPacket(
77     QuicConnectionStateBase& conn,
78     AckState& ackState,
79     bool pktOutOfOrder,
80     bool pktHasRetransmittableData,
81     bool pktHasCryptoData) {
82   DCHECK(!pktHasCryptoData || pktHasRetransmittableData);
83   auto thresh = kNonRtxRxPacketsPendingBeforeAck;
84   if (pktHasRetransmittableData || ackState.numRxPacketsRecvd) {
85     if (ackState.tolerance.hasValue()) {
86       thresh = ackState.tolerance.value();
87     } else {
88       thresh = ackState.largestReceivedPacketNum.value_or(0) >
89               conn.transportSettings.rxPacketsBeforeAckInitThreshold
90           ? conn.transportSettings.rxPacketsBeforeAckAfterInit
91           : conn.transportSettings.rxPacketsBeforeAckBeforeInit;
92     }
93   }
94   if (ackState.ignoreReorder) {
95     pktOutOfOrder = false;
96   }
97   if (pktHasRetransmittableData) {
98     if (pktHasCryptoData || pktOutOfOrder ||
99         ++ackState.numRxPacketsRecvd + ackState.numNonRxPacketsRecvd >=
100             thresh) {
101       VLOG(10) << conn
102                << " ack immediately because packet threshold pktHasCryptoData="
103                << pktHasCryptoData << " pktHasRetransmittableData="
104                << static_cast<int>(pktHasRetransmittableData)
105                << " numRxPacketsRecvd="
106                << static_cast<int>(ackState.numRxPacketsRecvd)
107                << " numNonRxPacketsRecvd="
108                << static_cast<int>(ackState.numNonRxPacketsRecvd);
109       conn.pendingEvents.scheduleAckTimeout = false;
110       ackState.needsToSendAckImmediately = true;
111     } else if (!ackState.needsToSendAckImmediately) {
112       VLOG(10) << conn << " scheduling ack timeout pktHasCryptoData="
113                << pktHasCryptoData << " pktHasRetransmittableData="
114                << static_cast<int>(pktHasRetransmittableData)
115                << " numRxPacketsRecvd="
116                << static_cast<int>(ackState.numRxPacketsRecvd)
117                << " numNonRxPacketsRecvd="
118                << static_cast<int>(ackState.numNonRxPacketsRecvd);
119       conn.pendingEvents.scheduleAckTimeout = true;
120     }
121   } else if (
122       ++ackState.numNonRxPacketsRecvd + ackState.numRxPacketsRecvd >= thresh) {
123     VLOG(10)
124         << conn
125         << " ack immediately because exceeds nonrx threshold numNonRxPacketsRecvd="
126         << static_cast<int>(ackState.numNonRxPacketsRecvd)
127         << " numRxPacketsRecvd="
128         << static_cast<int>(ackState.numRxPacketsRecvd);
129     conn.pendingEvents.scheduleAckTimeout = false;
130     ackState.needsToSendAckImmediately = true;
131   }
132   if (ackState.needsToSendAckImmediately) {
133     ackState.numRxPacketsRecvd = 0;
134     ackState.numNonRxPacketsRecvd = 0;
135   }
136 }
137 
updateAckStateOnAckTimeout(QuicConnectionStateBase & conn)138 void updateAckStateOnAckTimeout(QuicConnectionStateBase& conn) {
139   VLOG(10) << conn << " ack immediately due to ack timeout";
140   conn.ackStates.appDataAckState.needsToSendAckImmediately = true;
141   conn.ackStates.appDataAckState.numRxPacketsRecvd = 0;
142   conn.ackStates.appDataAckState.numNonRxPacketsRecvd = 0;
143   conn.pendingEvents.scheduleAckTimeout = false;
144 }
145 
updateAckSendStateOnSentPacketWithAcks(QuicConnectionStateBase & conn,AckState & ackState,PacketNum largestAckScheduled)146 void updateAckSendStateOnSentPacketWithAcks(
147     QuicConnectionStateBase& conn,
148     AckState& ackState,
149     PacketNum largestAckScheduled) {
150   VLOG(10) << conn << " unset ack immediately due to sending packet with acks";
151   conn.pendingEvents.scheduleAckTimeout = false;
152   ackState.needsToSendAckImmediately = false;
153   // When we send an ack we're most likely going to ack the largest received
154   // packet, so reset the counters for numRxPacketsRecvd and
155   // numNonRxPacketsRecvd. Since our ack threshold is quite small, we make the
156   // critical assumtion here that that all the needed acks can fit into one
157   // packet if needed. If this is not the case, then some packets may not get
158   // acked as a result and the receiver might retransmit them.
159   ackState.numRxPacketsRecvd = 0;
160   ackState.numNonRxPacketsRecvd = 0;
161   ackState.largestAckScheduled = largestAckScheduled;
162 }
163 
isConnectionPaced(const QuicConnectionStateBase & conn)164 bool isConnectionPaced(const QuicConnectionStateBase& conn) noexcept {
165   return (
166       conn.transportSettings.pacingEnabled && conn.canBePaced && conn.pacer);
167 }
168 
getAckState(QuicConnectionStateBase & conn,PacketNumberSpace pnSpace)169 AckState& getAckState(
170     QuicConnectionStateBase& conn,
171     PacketNumberSpace pnSpace) noexcept {
172   switch (pnSpace) {
173     case PacketNumberSpace::Initial:
174       return conn.ackStates.initialAckState;
175     case PacketNumberSpace::Handshake:
176       return conn.ackStates.handshakeAckState;
177     case PacketNumberSpace::AppData:
178       return conn.ackStates.appDataAckState;
179   }
180   folly::assume_unreachable();
181 }
182 
getAckState(const QuicConnectionStateBase & conn,PacketNumberSpace pnSpace)183 const AckState& getAckState(
184     const QuicConnectionStateBase& conn,
185     PacketNumberSpace pnSpace) noexcept {
186   switch (pnSpace) {
187     case PacketNumberSpace::Initial:
188       return conn.ackStates.initialAckState;
189     case PacketNumberSpace::Handshake:
190       return conn.ackStates.handshakeAckState;
191     case PacketNumberSpace::AppData:
192       return conn.ackStates.appDataAckState;
193   }
194   folly::assume_unreachable();
195 }
196 
currentAckStateVersion(const QuicConnectionStateBase & conn)197 AckStateVersion currentAckStateVersion(
198     const QuicConnectionStateBase& conn) noexcept {
199   return AckStateVersion(
200       conn.ackStates.initialAckState.acks.insertVersion(),
201       conn.ackStates.handshakeAckState.acks.insertVersion(),
202       conn.ackStates.appDataAckState.acks.insertVersion());
203 }
204 
getNextPacketNum(const QuicConnectionStateBase & conn,PacketNumberSpace pnSpace)205 PacketNum getNextPacketNum(
206     const QuicConnectionStateBase& conn,
207     PacketNumberSpace pnSpace) noexcept {
208   return getAckState(conn, pnSpace).nextPacketNum;
209 }
210 
increaseNextPacketNum(QuicConnectionStateBase & conn,PacketNumberSpace pnSpace)211 void increaseNextPacketNum(
212     QuicConnectionStateBase& conn,
213     PacketNumberSpace pnSpace) noexcept {
214   getAckState(conn, pnSpace).nextPacketNum++;
215   if (getAckState(conn, pnSpace).nextPacketNum == kMaxPacketNumber - 1) {
216     conn.pendingEvents.closeTransport = true;
217   }
218 }
219 
getFirstOutstandingPacket(QuicConnectionStateBase & conn,PacketNumberSpace packetNumberSpace)220 std::deque<OutstandingPacket>::iterator getFirstOutstandingPacket(
221     QuicConnectionStateBase& conn,
222     PacketNumberSpace packetNumberSpace) {
223   return getNextOutstandingPacket(
224       conn, packetNumberSpace, conn.outstandings.packets.begin());
225 }
226 
getLastOutstandingPacket(QuicConnectionStateBase & conn,PacketNumberSpace packetNumberSpace)227 std::deque<OutstandingPacket>::reverse_iterator getLastOutstandingPacket(
228     QuicConnectionStateBase& conn,
229     PacketNumberSpace packetNumberSpace) {
230   return getPreviousOutstandingPacket(
231       conn, packetNumberSpace, conn.outstandings.packets.rbegin());
232 }
233 
234 std::deque<OutstandingPacket>::reverse_iterator
getLastOutstandingPacketIncludingLost(QuicConnectionStateBase & conn,PacketNumberSpace packetNumberSpace)235 getLastOutstandingPacketIncludingLost(
236     QuicConnectionStateBase& conn,
237     PacketNumberSpace packetNumberSpace) {
238   return getPreviousOutstandingPacketIncludingLost(
239       conn, packetNumberSpace, conn.outstandings.packets.rbegin());
240 }
241 
getNextOutstandingPacket(QuicConnectionStateBase & conn,PacketNumberSpace packetNumberSpace,std::deque<OutstandingPacket>::iterator from)242 std::deque<OutstandingPacket>::iterator getNextOutstandingPacket(
243     QuicConnectionStateBase& conn,
244     PacketNumberSpace packetNumberSpace,
245     std::deque<OutstandingPacket>::iterator from) {
246   return std::find_if(
247       from, conn.outstandings.packets.end(), [=](const auto& op) {
248         return !op.declaredLost &&
249             packetNumberSpace == op.packet.header.getPacketNumberSpace();
250       });
251 }
252 
hasReceivedPacketsAtLastCloseSent(const QuicConnectionStateBase & conn)253 bool hasReceivedPacketsAtLastCloseSent(
254     const QuicConnectionStateBase& conn) noexcept {
255   return conn.ackStates.initialAckState.largestReceivedAtLastCloseSent ||
256       conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent ||
257       conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent;
258 }
259 
hasNotReceivedNewPacketsSinceLastCloseSent(const QuicConnectionStateBase & conn)260 bool hasNotReceivedNewPacketsSinceLastCloseSent(
261     const QuicConnectionStateBase& conn) noexcept {
262   DCHECK(
263       !conn.ackStates.initialAckState.largestReceivedAtLastCloseSent ||
264       *conn.ackStates.initialAckState.largestReceivedAtLastCloseSent <=
265           *conn.ackStates.initialAckState.largestReceivedPacketNum);
266   DCHECK(
267       !conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent ||
268       *conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent <=
269           *conn.ackStates.handshakeAckState.largestReceivedPacketNum);
270   DCHECK(
271       !conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent ||
272       *conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent <=
273           *conn.ackStates.appDataAckState.largestReceivedPacketNum);
274   return conn.ackStates.initialAckState.largestReceivedAtLastCloseSent ==
275       conn.ackStates.initialAckState.largestReceivedPacketNum &&
276       conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent ==
277       conn.ackStates.handshakeAckState.largestReceivedPacketNum &&
278       conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent ==
279       conn.ackStates.appDataAckState.largestReceivedPacketNum;
280 }
281 
updateLargestReceivedPacketsAtLastCloseSent(QuicConnectionStateBase & conn)282 void updateLargestReceivedPacketsAtLastCloseSent(
283     QuicConnectionStateBase& conn) noexcept {
284   conn.ackStates.initialAckState.largestReceivedAtLastCloseSent =
285       conn.ackStates.initialAckState.largestReceivedPacketNum;
286   conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent =
287       conn.ackStates.handshakeAckState.largestReceivedPacketNum;
288   conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent =
289       conn.ackStates.appDataAckState.largestReceivedPacketNum;
290 }
291 
hasReceivedPackets(const QuicConnectionStateBase & conn)292 bool hasReceivedPackets(const QuicConnectionStateBase& conn) noexcept {
293   return conn.ackStates.initialAckState.largestReceivedPacketNum ||
294       conn.ackStates.handshakeAckState.largestReceivedPacketNum ||
295       conn.ackStates.appDataAckState.largestReceivedPacketNum;
296 }
297 
getLossTime(QuicConnectionStateBase & conn,PacketNumberSpace pnSpace)298 folly::Optional<TimePoint>& getLossTime(
299     QuicConnectionStateBase& conn,
300     PacketNumberSpace pnSpace) noexcept {
301   return conn.lossState.lossTimes[pnSpace];
302 }
303 
canSetLossTimerForAppData(const QuicConnectionStateBase & conn)304 bool canSetLossTimerForAppData(const QuicConnectionStateBase& conn) noexcept {
305   return conn.oneRttWriteCipher != nullptr;
306 }
307 
earliestLossTimer(const QuicConnectionStateBase & conn)308 std::pair<folly::Optional<TimePoint>, PacketNumberSpace> earliestLossTimer(
309     const QuicConnectionStateBase& conn) noexcept {
310   bool considerAppData = canSetLossTimerForAppData(conn);
311   return earliestTimeAndSpace(conn.lossState.lossTimes, considerAppData);
312 }
313 
earliestTimeAndSpace(const EnumArray<PacketNumberSpace,folly::Optional<TimePoint>> & times,bool considerAppData)314 std::pair<folly::Optional<TimePoint>, PacketNumberSpace> earliestTimeAndSpace(
315     const EnumArray<PacketNumberSpace, folly::Optional<TimePoint>>& times,
316     bool considerAppData) noexcept {
317   std::pair<folly::Optional<TimePoint>, PacketNumberSpace> res = {
318       folly::none, PacketNumberSpace::Initial};
319   for (PacketNumberSpace pns : times.keys()) {
320     if (!times[pns]) {
321       continue;
322     }
323     if (pns == PacketNumberSpace::AppData && !considerAppData) {
324       continue;
325     }
326     if (!res.first || *res.first > *times[pns]) {
327       res.first = times[pns];
328       res.second = pns;
329     }
330   }
331   return res;
332 }
333 
334 } // namespace quic
335