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