quic/state/QuicStateFunctions.cpp (299 lines of code) (raw):

/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * This source code is licensed under the MIT license found in the * LICENSE file in the root directory of this source tree. */ #include <quic/state/QuicStateFunctions.h> #include <quic/state/QuicStreamFunctions.h> #include <quic/common/TimeUtil.h> namespace { std::deque<quic::OutstandingPacket>::reverse_iterator getPreviousOutstandingPacket( quic::QuicConnectionStateBase& conn, quic::PacketNumberSpace packetNumberSpace, std::deque<quic::OutstandingPacket>::reverse_iterator from) { return std::find_if( from, conn.outstandings.packets.rend(), [=](const auto& op) { return !op.declaredLost && packetNumberSpace == op.packet.header.getPacketNumberSpace(); }); } std::deque<quic::OutstandingPacket>::reverse_iterator getPreviousOutstandingPacketIncludingLost( quic::QuicConnectionStateBase& conn, quic::PacketNumberSpace packetNumberSpace, std::deque<quic::OutstandingPacket>::reverse_iterator from) { return std::find_if( from, conn.outstandings.packets.rend(), [=](const auto& op) { return packetNumberSpace == op.packet.header.getPacketNumberSpace(); }); } } // namespace namespace quic { void updateRtt( QuicConnectionStateBase& conn, const std::chrono::microseconds rttSample, const std::chrono::microseconds ackDelay) { // update mrtt // // mrtt ignores ack delay. This is the same in the current recovery draft // section A.6. conn.lossState.mrtt = timeMin(conn.lossState.mrtt, rttSample); // update mrttNoAckDelay // // keep a version of mrtt formed from rtt samples with ACK delay removed if (rttSample >= ackDelay) { const auto rttSampleNoAckDelay = std::chrono::ceil<std::chrono::microseconds>(rttSample - ackDelay); conn.lossState.maybeMrttNoAckDelay = (conn.lossState.maybeMrttNoAckDelay) ? std::min(*conn.lossState.maybeMrttNoAckDelay, rttSampleNoAckDelay) : rttSampleNoAckDelay; } // update lrtt and lrttAckDelay conn.lossState.lrtt = rttSample; conn.lossState.maybeLrtt = rttSample; conn.lossState.maybeLrttAckDelay = ackDelay; // update maxAckDelay conn.lossState.maxAckDelay = timeMax(conn.lossState.maxAckDelay, ackDelay); // determine the adjusted RTT sample we will use for srtt calculations // // do NOT subtract the acknowledgment delay from the RTT sample if the // resulting value is smaller than the min_rtt; this limits underestimation // of the smoothed_rtt due to a misreporting peer. // // if this is the first RTT sample, then it is also the minRTT and ACK delay // will not be subtracted const auto adjustedRtt = ((rttSample > ackDelay) && (rttSample > conn.lossState.mrtt + ackDelay)) ? rttSample - ackDelay : rttSample; if (conn.lossState.srtt == 0us) { conn.lossState.srtt = adjustedRtt; conn.lossState.rttvar = adjustedRtt / 2; } else { conn.lossState.rttvar = conn.lossState.rttvar * (kRttBeta - 1) / kRttBeta + (conn.lossState.srtt > adjustedRtt ? conn.lossState.srtt - adjustedRtt : adjustedRtt - conn.lossState.srtt) / kRttBeta; conn.lossState.srtt = conn.lossState.srtt * (kRttAlpha - 1) / kRttAlpha + adjustedRtt / kRttAlpha; } // inform qlog if (conn.qLogger) { conn.qLogger->addMetricUpdate( rttSample, conn.lossState.mrtt, conn.lossState.srtt, ackDelay); } } void updateAckSendStateOnRecvPacket( QuicConnectionStateBase& conn, AckState& ackState, bool pktOutOfOrder, bool pktHasRetransmittableData, bool pktHasCryptoData, bool initPktNumSpace) { DCHECK(!pktHasCryptoData || pktHasRetransmittableData); auto thresh = kNonRtxRxPacketsPendingBeforeAck; if (pktHasRetransmittableData || ackState.numRxPacketsRecvd) { if (ackState.tolerance.hasValue()) { thresh = ackState.tolerance.value(); } else { thresh = ackState.largestReceivedPacketNum.value_or(0) > conn.transportSettings.rxPacketsBeforeAckInitThreshold ? conn.transportSettings.rxPacketsBeforeAckAfterInit : conn.transportSettings.rxPacketsBeforeAckBeforeInit; } } if (ackState.ignoreReorder) { pktOutOfOrder = false; } if (pktHasRetransmittableData) { bool skipCryptoAck = conn.nodeType == QuicNodeType::Server && initPktNumSpace; if ((pktHasCryptoData && !skipCryptoAck) || pktOutOfOrder || ++ackState.numRxPacketsRecvd + ackState.numNonRxPacketsRecvd >= thresh) { VLOG(10) << conn << " ack immediately because packet threshold pktHasCryptoData=" << pktHasCryptoData << " pktHasRetransmittableData=" << static_cast<int>(pktHasRetransmittableData) << " numRxPacketsRecvd=" << static_cast<int>(ackState.numRxPacketsRecvd) << " numNonRxPacketsRecvd=" << static_cast<int>(ackState.numNonRxPacketsRecvd); conn.pendingEvents.scheduleAckTimeout = false; ackState.needsToSendAckImmediately = true; } else if (!ackState.needsToSendAckImmediately) { VLOG(10) << conn << " scheduling ack timeout pktHasCryptoData=" << pktHasCryptoData << " pktHasRetransmittableData=" << static_cast<int>(pktHasRetransmittableData) << " numRxPacketsRecvd=" << static_cast<int>(ackState.numRxPacketsRecvd) << " numNonRxPacketsRecvd=" << static_cast<int>(ackState.numNonRxPacketsRecvd); conn.pendingEvents.scheduleAckTimeout = true; } } else if ( ++ackState.numNonRxPacketsRecvd + ackState.numRxPacketsRecvd >= thresh) { VLOG(10) << conn << " ack immediately because exceeds nonrx threshold numNonRxPacketsRecvd=" << static_cast<int>(ackState.numNonRxPacketsRecvd) << " numRxPacketsRecvd=" << static_cast<int>(ackState.numRxPacketsRecvd); conn.pendingEvents.scheduleAckTimeout = false; ackState.needsToSendAckImmediately = true; } if (ackState.needsToSendAckImmediately) { ackState.numRxPacketsRecvd = 0; ackState.numNonRxPacketsRecvd = 0; } } void updateAckStateOnAckTimeout(QuicConnectionStateBase& conn) { VLOG(10) << conn << " ack immediately due to ack timeout"; conn.ackStates.appDataAckState.needsToSendAckImmediately = true; conn.ackStates.appDataAckState.numRxPacketsRecvd = 0; conn.ackStates.appDataAckState.numNonRxPacketsRecvd = 0; conn.pendingEvents.scheduleAckTimeout = false; } void updateAckSendStateOnSentPacketWithAcks( QuicConnectionStateBase& conn, AckState& ackState, PacketNum largestAckScheduled) { VLOG(10) << conn << " unset ack immediately due to sending packet with acks"; conn.pendingEvents.scheduleAckTimeout = false; ackState.needsToSendAckImmediately = false; // When we send an ack we're most likely going to ack the largest received // packet, so reset the counters for numRxPacketsRecvd and // numNonRxPacketsRecvd. Since our ack threshold is quite small, we make the // critical assumtion here that that all the needed acks can fit into one // packet if needed. If this is not the case, then some packets may not get // acked as a result and the receiver might retransmit them. ackState.numRxPacketsRecvd = 0; ackState.numNonRxPacketsRecvd = 0; ackState.largestAckScheduled = largestAckScheduled; } bool isConnectionPaced(const QuicConnectionStateBase& conn) noexcept { return ( conn.transportSettings.pacingEnabled && conn.canBePaced && conn.pacer); } AckState& getAckState( QuicConnectionStateBase& conn, PacketNumberSpace pnSpace) noexcept { switch (pnSpace) { case PacketNumberSpace::Initial: return conn.ackStates.initialAckState; case PacketNumberSpace::Handshake: return conn.ackStates.handshakeAckState; case PacketNumberSpace::AppData: return conn.ackStates.appDataAckState; } folly::assume_unreachable(); } const AckState& getAckState( const QuicConnectionStateBase& conn, PacketNumberSpace pnSpace) noexcept { switch (pnSpace) { case PacketNumberSpace::Initial: return conn.ackStates.initialAckState; case PacketNumberSpace::Handshake: return conn.ackStates.handshakeAckState; case PacketNumberSpace::AppData: return conn.ackStates.appDataAckState; } folly::assume_unreachable(); } AckStateVersion currentAckStateVersion( const QuicConnectionStateBase& conn) noexcept { return AckStateVersion( conn.ackStates.initialAckState.acks.insertVersion(), conn.ackStates.handshakeAckState.acks.insertVersion(), conn.ackStates.appDataAckState.acks.insertVersion()); } PacketNum getNextPacketNum( const QuicConnectionStateBase& conn, PacketNumberSpace pnSpace) noexcept { return getAckState(conn, pnSpace).nextPacketNum; } void increaseNextPacketNum( QuicConnectionStateBase& conn, PacketNumberSpace pnSpace) noexcept { getAckState(conn, pnSpace).nextPacketNum++; if (getAckState(conn, pnSpace).nextPacketNum == kMaxPacketNumber - 1) { conn.pendingEvents.closeTransport = true; } } std::deque<OutstandingPacket>::iterator getFirstOutstandingPacket( QuicConnectionStateBase& conn, PacketNumberSpace packetNumberSpace) { return getNextOutstandingPacket( conn, packetNumberSpace, conn.outstandings.packets.begin()); } std::deque<OutstandingPacket>::reverse_iterator getLastOutstandingPacket( QuicConnectionStateBase& conn, PacketNumberSpace packetNumberSpace) { return getPreviousOutstandingPacket( conn, packetNumberSpace, conn.outstandings.packets.rbegin()); } std::deque<OutstandingPacket>::reverse_iterator getLastOutstandingPacketIncludingLost( QuicConnectionStateBase& conn, PacketNumberSpace packetNumberSpace) { return getPreviousOutstandingPacketIncludingLost( conn, packetNumberSpace, conn.outstandings.packets.rbegin()); } std::deque<OutstandingPacket>::iterator getNextOutstandingPacket( QuicConnectionStateBase& conn, PacketNumberSpace packetNumberSpace, std::deque<OutstandingPacket>::iterator from) { return std::find_if( from, conn.outstandings.packets.end(), [=](const auto& op) { return !op.declaredLost && packetNumberSpace == op.packet.header.getPacketNumberSpace(); }); } bool hasReceivedPacketsAtLastCloseSent( const QuicConnectionStateBase& conn) noexcept { return conn.ackStates.initialAckState.largestReceivedAtLastCloseSent || conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent || conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent; } bool hasNotReceivedNewPacketsSinceLastCloseSent( const QuicConnectionStateBase& conn) noexcept { DCHECK( !conn.ackStates.initialAckState.largestReceivedAtLastCloseSent || *conn.ackStates.initialAckState.largestReceivedAtLastCloseSent <= *conn.ackStates.initialAckState.largestReceivedPacketNum); DCHECK( !conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent || *conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent <= *conn.ackStates.handshakeAckState.largestReceivedPacketNum); DCHECK( !conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent || *conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent <= *conn.ackStates.appDataAckState.largestReceivedPacketNum); return conn.ackStates.initialAckState.largestReceivedAtLastCloseSent == conn.ackStates.initialAckState.largestReceivedPacketNum && conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent == conn.ackStates.handshakeAckState.largestReceivedPacketNum && conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent == conn.ackStates.appDataAckState.largestReceivedPacketNum; } void updateLargestReceivedPacketsAtLastCloseSent( QuicConnectionStateBase& conn) noexcept { conn.ackStates.initialAckState.largestReceivedAtLastCloseSent = conn.ackStates.initialAckState.largestReceivedPacketNum; conn.ackStates.handshakeAckState.largestReceivedAtLastCloseSent = conn.ackStates.handshakeAckState.largestReceivedPacketNum; conn.ackStates.appDataAckState.largestReceivedAtLastCloseSent = conn.ackStates.appDataAckState.largestReceivedPacketNum; } bool hasReceivedPackets(const QuicConnectionStateBase& conn) noexcept { return conn.ackStates.initialAckState.largestReceivedPacketNum || conn.ackStates.handshakeAckState.largestReceivedPacketNum || conn.ackStates.appDataAckState.largestReceivedPacketNum; } folly::Optional<TimePoint>& getLossTime( QuicConnectionStateBase& conn, PacketNumberSpace pnSpace) noexcept { return conn.lossState.lossTimes[pnSpace]; } bool canSetLossTimerForAppData(const QuicConnectionStateBase& conn) noexcept { return conn.oneRttWriteCipher != nullptr; } std::pair<folly::Optional<TimePoint>, PacketNumberSpace> earliestLossTimer( const QuicConnectionStateBase& conn) noexcept { bool considerAppData = canSetLossTimerForAppData(conn); return earliestTimeAndSpace(conn.lossState.lossTimes, considerAppData); } std::pair<folly::Optional<TimePoint>, PacketNumberSpace> earliestTimeAndSpace( const EnumArray<PacketNumberSpace, folly::Optional<TimePoint>>& times, bool considerAppData) noexcept { std::pair<folly::Optional<TimePoint>, PacketNumberSpace> res = { folly::none, PacketNumberSpace::Initial}; for (PacketNumberSpace pns : times.keys()) { if (!times[pns]) { continue; } if (pns == PacketNumberSpace::AppData && !considerAppData) { continue; } if (!res.first || *res.first > *times[pns]) { res.first = times[pns]; res.second = pns; } } return res; } } // namespace quic