1 /** @file
2  *
3  *  A brief file description
4  *
5  *  @section license License
6  *
7  *  Licensed to the Apache Software Foundation (ASF) under one
8  *  or more contributor license agreements.  See the NOTICE file
9  *  distributed with this work for additional information
10  *  regarding copyright ownership.  The ASF licenses this file
11  *  to you under the Apache License, Version 2.0 (the
12  *  "License"); you may not use this file except in compliance
13  *  with the License.  You may obtain a copy of the License at
14  *
15  *      http://www.apache.org/licenses/LICENSE-2.0
16  *
17  *  Unless required by applicable law or agreed to in writing, software
18  *  distributed under the License is distributed on an "AS IS" BASIS,
19  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20  *  See the License for the specific language governing permissions and
21  *  limitations under the License.
22  */
23 
24 #include "QUICLossDetector.h"
25 
26 #include "tscore/ink_assert.h"
27 
28 #include "QUICConfig.h"
29 #include "QUICEvents.h"
30 #include "QUICDebugNames.h"
31 #include "QUICFrameGenerator.h"
32 #include "QUICPinger.h"
33 #include "QUICPadder.h"
34 #include "QUICPacketProtectionKeyInfo.h"
35 
36 #define QUICLDDebug(fmt, ...) \
37   Debug("quic_loss_detector", "[%s] " fmt, this->_context.connection_info()->cids().data(), ##__VA_ARGS__)
38 #define QUICLDVDebug(fmt, ...) \
39   Debug("v_quic_loss_detector", "[%s] " fmt, this->_context.connection_info()->cids().data(), ##__VA_ARGS__)
40 
QUICLossDetector(QUICLDContext & context,QUICCongestionController * cc,QUICRTTMeasure * rtt_measure,QUICPinger * pinger,QUICPadder * padder)41 QUICLossDetector::QUICLossDetector(QUICLDContext &context, QUICCongestionController *cc, QUICRTTMeasure *rtt_measure,
42                                    QUICPinger *pinger, QUICPadder *padder)
43   : _rtt_measure(rtt_measure), _pinger(pinger), _padder(padder), _cc(cc), _context(context)
44 {
45   auto &ld_config             = _context.ld_config();
46   this->mutex                 = new_ProxyMutex();
47   this->_loss_detection_mutex = new_ProxyMutex();
48 
49   this->_k_packet_threshold = ld_config.packet_threshold();
50   this->_k_time_threshold   = ld_config.time_threshold();
51 
52   this->reset();
53 
54   SET_HANDLER(&QUICLossDetector::event_handler);
55 }
56 
~QUICLossDetector()57 QUICLossDetector::~QUICLossDetector()
58 {
59   if (this->_loss_detection_timer) {
60     this->_loss_detection_timer->cancel();
61     this->_loss_detection_timer = nullptr;
62   }
63 
64   for (auto i = 0; i < kPacketNumberSpace; i++) {
65     this->_sent_packets[i].clear();
66   }
67 }
68 
69 int
event_handler(int event,Event * edata)70 QUICLossDetector::event_handler(int event, Event *edata)
71 {
72   switch (event) {
73   case EVENT_INTERVAL: {
74     if (this->_loss_detection_alarm_at <= Thread::get_hrtime()) {
75       this->_loss_detection_alarm_at = 0;
76       this->_on_loss_detection_timeout();
77     }
78     break;
79   }
80   case QUIC_EVENT_LD_SHUTDOWN: {
81     SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
82     QUICLDDebug("Shutdown");
83 
84     if (this->_loss_detection_timer) {
85       this->_loss_detection_timer->cancel();
86       this->_loss_detection_timer = nullptr;
87     }
88     break;
89   }
90   default:
91     break;
92   }
93   return EVENT_CONT;
94 }
95 
96 std::vector<QUICFrameType>
interests()97 QUICLossDetector::interests()
98 {
99   return {QUICFrameType::ACK};
100 }
101 
102 QUICConnectionErrorUPtr
handle_frame(QUICEncryptionLevel level,const QUICFrame & frame)103 QUICLossDetector::handle_frame(QUICEncryptionLevel level, const QUICFrame &frame)
104 {
105   QUICConnectionErrorUPtr error = nullptr;
106 
107   switch (frame.type()) {
108   case QUICFrameType::ACK:
109     this->_on_ack_received(static_cast<const QUICAckFrame &>(frame), QUICTypeUtil::pn_space(level));
110     break;
111   default:
112     QUICLDDebug("Unexpected frame type: %02x", static_cast<unsigned int>(frame.type()));
113     ink_assert(false);
114     break;
115   }
116 
117   return error;
118 }
119 
120 QUICPacketNumber
largest_acked_packet_number(QUICPacketNumberSpace pn_space)121 QUICLossDetector::largest_acked_packet_number(QUICPacketNumberSpace pn_space)
122 {
123   int index = static_cast<int>(pn_space);
124   return this->_largest_acked_packet[index];
125 }
126 
127 void
on_packet_sent(QUICPacketInfoUPtr packet_info,bool in_flight)128 QUICLossDetector::on_packet_sent(QUICPacketInfoUPtr packet_info, bool in_flight)
129 {
130   if (packet_info->type == QUICPacketType::VERSION_NEGOTIATION) {
131     return;
132   }
133 
134   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
135 
136   QUICPacketNumber packet_number = packet_info->packet_number;
137   bool ack_eliciting             = packet_info->ack_eliciting;
138   bool is_crypto_packet          = packet_info->is_crypto_packet;
139   ink_hrtime now                 = packet_info->time_sent;
140   size_t sent_bytes              = packet_info->sent_bytes;
141 
142   QUICLDDebug("%s packet sent : %" PRIu64 " bytes: %lu ack_eliciting: %d", QUICDebugNames::pn_space(packet_info->pn_space),
143               packet_number, sent_bytes, ack_eliciting);
144 
145   this->_add_to_sent_packet_list(packet_number, std::move(packet_info));
146 
147   if (in_flight) {
148     if (is_crypto_packet) {
149       this->_time_of_last_sent_crypto_packet = now;
150     }
151 
152     if (ack_eliciting) {
153       this->_time_of_last_sent_ack_eliciting_packet = now;
154     }
155     this->_cc->on_packet_sent(sent_bytes);
156     this->_set_loss_detection_timer();
157   }
158 }
159 
160 void
reset()161 QUICLossDetector::reset()
162 {
163   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
164   if (this->_loss_detection_timer) {
165     this->_loss_detection_timer->cancel();
166     this->_loss_detection_timer = nullptr;
167   }
168 
169   this->_ack_eliciting_outstanding = 0;
170   this->_crypto_outstanding        = 0;
171 
172   // [draft-17 recovery] 6.4.3.  Initialization
173   this->_time_of_last_sent_ack_eliciting_packet = 0;
174   this->_time_of_last_sent_crypto_packet        = 0;
175   for (auto i = 0; i < kPacketNumberSpace; i++) {
176     this->_largest_acked_packet[i] = 0;
177     this->_loss_time[i]            = 0;
178     this->_sent_packets[i].clear();
179   }
180 
181   this->_rtt_measure->reset();
182 }
183 
184 void
update_ack_delay_exponent(uint8_t ack_delay_exponent)185 QUICLossDetector::update_ack_delay_exponent(uint8_t ack_delay_exponent)
186 {
187   this->_ack_delay_exponent = ack_delay_exponent;
188 }
189 
190 bool
_include_ack_eliciting(const std::vector<QUICPacketInfo * > & acked_packets,int index) const191 QUICLossDetector::_include_ack_eliciting(const std::vector<QUICPacketInfo *> &acked_packets, int index) const
192 {
193   // Find out ack_elicting packet.
194   // FIXME: this loop is the same as _on_ack_received's loop it would better
195   // to combine it.
196   for (auto packet : acked_packets) {
197     if (packet->ack_eliciting) {
198       return true;
199     }
200   }
201 
202   return false;
203 }
204 
205 void
_on_ack_received(const QUICAckFrame & ack_frame,QUICPacketNumberSpace pn_space)206 QUICLossDetector::_on_ack_received(const QUICAckFrame &ack_frame, QUICPacketNumberSpace pn_space)
207 {
208   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
209 
210   int index                          = static_cast<int>(pn_space);
211   this->_largest_acked_packet[index] = std::max(this->_largest_acked_packet[index], ack_frame.largest_acknowledged());
212 
213   auto newly_acked_packets = this->_determine_newly_acked_packets(ack_frame, index);
214   if (newly_acked_packets.empty()) {
215     return;
216   }
217 
218   // If the largest acknowledged is newly acked and
219   //  ack-eliciting, update the RTT.
220   auto pi = this->_sent_packets[index].find(ack_frame.largest_acknowledged());
221   if (pi != this->_sent_packets[index].end() &&
222       (pi->second->ack_eliciting || this->_include_ack_eliciting(newly_acked_packets, index))) {
223     ink_hrtime latest_rtt = Thread::get_hrtime() - pi->second->time_sent;
224     // _latest_rtt is nanosecond but ack_frame.ack_delay is microsecond and scaled
225     ink_hrtime delay = HRTIME_USECONDS(ack_frame.ack_delay() << this->_ack_delay_exponent);
226     this->_rtt_measure->update_rtt(latest_rtt, delay);
227   }
228 
229   QUICLDVDebug("[%s] Unacked packets %lu (retransmittable %u, includes %u handshake packets)", QUICDebugNames::pn_space(pn_space),
230                this->_sent_packets[index].size(), this->_ack_eliciting_outstanding.load(), this->_crypto_outstanding.load());
231 
232   // if (ACK frame contains ECN information):
233   //   ProcessECN(ack)
234   if (ack_frame.ecn_section() != nullptr && pi != this->_sent_packets[index].end()) {
235     this->_cc->process_ecn(*pi->second, ack_frame.ecn_section());
236   }
237 
238   // Find all newly acked packets.
239   for (auto info : newly_acked_packets) {
240     this->_on_packet_acked(*info);
241   }
242 
243   QUICLDVDebug("[%s] Unacked packets %lu (retransmittable %u, includes %u handshake packets)", QUICDebugNames::pn_space(pn_space),
244                this->_sent_packets[index].size(), this->_ack_eliciting_outstanding.load(), this->_crypto_outstanding.load());
245 
246   this->_detect_lost_packets(pn_space);
247 
248   this->_rtt_measure->set_crypto_count(0);
249   this->_rtt_measure->set_pto_count(0);
250 
251   QUICLDDebug("[%s] Unacked packets %lu (retransmittable %u, includes %u handshake packets)", QUICDebugNames::pn_space(pn_space),
252               this->_sent_packets[index].size(), this->_ack_eliciting_outstanding.load(), this->_crypto_outstanding.load());
253 
254   this->_set_loss_detection_timer();
255 }
256 
257 void
_on_packet_acked(const QUICPacketInfo & acked_packet)258 QUICLossDetector::_on_packet_acked(const QUICPacketInfo &acked_packet)
259 {
260   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
261   QUICLDDebug("[%s] Packet number %" PRIu64 " has been acked", QUICDebugNames::pn_space(acked_packet.pn_space),
262               acked_packet.packet_number);
263 
264   if (acked_packet.in_flight) {
265     this->_cc->on_packet_acked(acked_packet);
266   }
267 
268   for (const QUICFrameInfo &frame_info : acked_packet.frames) {
269     auto reactor = frame_info.generated_by();
270     if (reactor == nullptr) {
271       continue;
272     }
273 
274     reactor->on_frame_acked(frame_info.id());
275   }
276 
277   this->_remove_from_sent_packet_list(acked_packet.packet_number, acked_packet.pn_space);
278 }
279 
280 ink_hrtime
_get_earliest_loss_time(QUICPacketNumberSpace & pn_space)281 QUICLossDetector::_get_earliest_loss_time(QUICPacketNumberSpace &pn_space)
282 {
283   ink_hrtime time = this->_loss_time[static_cast<int>(QUICPacketNumberSpace::Initial)];
284   pn_space        = QUICPacketNumberSpace::Initial;
285   for (auto i = 1; i < kPacketNumberSpace; i++) {
286     if (this->_loss_time[i] != 0 && (time != 0 || this->_loss_time[i] < time)) {
287       time     = this->_loss_time[i];
288       pn_space = static_cast<QUICPacketNumberSpace>(i);
289     }
290   }
291 
292   return time;
293 }
294 
295 void
_set_loss_detection_timer()296 QUICLossDetector::_set_loss_detection_timer()
297 {
298   std::function<void(ink_hrtime)> update_timer = [this](ink_hrtime time) {
299     this->_loss_detection_alarm_at = time;
300     if (!this->_loss_detection_timer) {
301       this->_loss_detection_timer = eventProcessor.schedule_every(this, HRTIME_MSECONDS(25));
302     }
303   };
304 
305   QUICPacketNumberSpace pn_space;
306   ink_hrtime alarm = this->_get_earliest_loss_time(pn_space);
307   if (alarm != 0) {
308     update_timer(alarm);
309     QUICLDDebug("[%s] time threshold loss detection timer: %" PRId64 "ms", QUICDebugNames::pn_space(pn_space),
310                 (this->_loss_detection_alarm_at - Thread::get_hrtime()) / HRTIME_MSECOND);
311     return;
312   }
313 
314   if (this->_crypto_outstanding > 0 || this->_is_client_without_one_rtt_key()) {
315     // Crypto retransmission timer.
316     alarm = this->_time_of_last_sent_crypto_packet + this->_rtt_measure->handshake_retransmit_timeout();
317     update_timer(alarm);
318     QUICLDDebug("%s crypto packet alarm will be set: %" PRId64 "ms", QUICDebugNames::pn_space(pn_space),
319                 (alarm - this->_time_of_last_sent_crypto_packet) / HRTIME_MSECOND);
320     return;
321   }
322 
323   // Don't arm the alarm if there are no packets with retransmittable data in flight.
324   // -- MODIFIED CODE --
325   // In psuedocode, `bytes_in_flight` is used, but we're tracking "retransmittable data in flight" by `_ack_eliciting_outstanding`
326   if (this->_ack_eliciting_outstanding == 0) {
327     if (this->_loss_detection_timer) {
328       this->_loss_detection_alarm_at = 0;
329       this->_loss_detection_timer->cancel();
330       this->_loss_detection_timer = nullptr;
331       QUICLDDebug("Loss detection alarm has been unset");
332     }
333 
334     return;
335   }
336   // -- END OF MODIFIED CODE --
337 
338   // PTO Duration
339   alarm = this->_time_of_last_sent_ack_eliciting_packet + this->_rtt_measure->current_pto_period();
340   update_timer(alarm);
341   QUICLDDebug("[%s] PTO timeout will be set: %" PRId64 "ms", QUICDebugNames::pn_space(pn_space),
342               (alarm - this->_time_of_last_sent_ack_eliciting_packet) / HRTIME_MSECOND);
343 }
344 
345 void
_on_loss_detection_timeout()346 QUICLossDetector::_on_loss_detection_timeout()
347 {
348   QUICPacketNumberSpace pn_space;
349   ink_hrtime loss_time = this->_get_earliest_loss_time(pn_space);
350   if (loss_time != 0) {
351     // Time threshold loss Detection
352     this->_detect_lost_packets(pn_space);
353   } else if (this->_crypto_outstanding) {
354     // Handshake retransmission alarm.
355     QUICLDVDebug("Crypto Retranmission");
356     this->_retransmit_all_unacked_crypto_data();
357     this->_rtt_measure->set_crypto_count(this->_rtt_measure->crypto_count() + 1);
358   } else if (this->_is_client_without_one_rtt_key()) {
359     // Client sends an anti-deadlock packet: Initial is padded
360     // to earn more anti-amplification credit,
361     // a Handshake packet proves address ownership.
362     if (this->_context.key_info()->is_encryption_key_available(QUICKeyPhase::HANDSHAKE)) {
363       this->_send_one_handshake_packets();
364     } else {
365       this->_send_one_padded_packets();
366     }
367 
368     this->_rtt_measure->set_crypto_count(this->_rtt_measure->crypto_count() + 1);
369   } else {
370     QUICLDVDebug("PTO");
371     this->_send_one_or_two_packet();
372     this->_rtt_measure->set_pto_count(this->_rtt_measure->pto_count() + 1);
373   }
374 
375   QUICLDDebug("[%s] Unacked packets %lu (retransmittable %u, includes %u handshake packets)", QUICDebugNames::pn_space(pn_space),
376               this->_sent_packets[static_cast<int>(pn_space)].size(), this->_ack_eliciting_outstanding.load(),
377               this->_crypto_outstanding.load());
378 
379   if (is_debug_tag_set("v_quic_loss_detector")) {
380     for (auto i = 0; i < 3; i++) {
381       for (auto &unacked : this->_sent_packets[i]) {
382         QUICLDVDebug("[%s] #%" PRIu64 " is_crypto=%i ack_eliciting=%i size=%zu %u %u",
383                      QUICDebugNames::pn_space(static_cast<QUICPacketNumberSpace>(i)), unacked.first,
384                      unacked.second->is_crypto_packet, unacked.second->ack_eliciting, unacked.second->sent_bytes,
385                      this->_ack_eliciting_outstanding.load(), this->_crypto_outstanding.load());
386       }
387     }
388   }
389 
390   this->_set_loss_detection_timer();
391 }
392 
393 void
_detect_lost_packets(QUICPacketNumberSpace pn_space)394 QUICLossDetector::_detect_lost_packets(QUICPacketNumberSpace pn_space)
395 {
396   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
397   this->_loss_time[static_cast<int>(pn_space)] = 0;
398   ink_hrtime loss_delay = this->_k_time_threshold * std::max(this->_rtt_measure->latest_rtt(), this->_rtt_measure->smoothed_rtt());
399   loss_delay            = std::min(loss_delay, this->_rtt_measure->k_granularity());
400 
401   std::map<QUICPacketNumber, QUICPacketInfo *> lost_packets;
402 
403   // Packets sent before this time are deemed lost.
404   ink_hrtime lost_send_time = Thread::get_hrtime() - loss_delay;
405 
406   // Packets with packet numbers before this are deemed lost.
407   QUICPacketNumber lost_pn = this->_largest_acked_packet[static_cast<int>(pn_space)] - this->_k_packet_threshold;
408 
409   for (auto it = this->_sent_packets[static_cast<int>(pn_space)].begin();
410        it != this->_sent_packets[static_cast<int>(pn_space)].end(); ++it) {
411     if (it->first > this->_largest_acked_packet[static_cast<int>(pn_space)]) {
412       // the spec uses continue but we can break here because the _sent_packets is sorted by packet_number.
413       break;
414     }
415 
416     auto &unacked = it->second;
417 
418     // Mark packet as lost, or set time when it should be marked.
419     if (unacked->time_sent < lost_send_time || unacked->packet_number < lost_pn) {
420       if (unacked->time_sent < lost_send_time) {
421         QUICLDDebug("[%s] Lost: time since sent is too long (#%" PRId64 " sent=%" PRId64 ", delay=%" PRId64
422                     ", fraction=%lf, lrtt=%" PRId64 ", srtt=%" PRId64 ")",
423                     QUICDebugNames::pn_space(pn_space), it->first, unacked->time_sent, lost_send_time, this->_k_time_threshold,
424                     this->_rtt_measure->latest_rtt(), this->_rtt_measure->smoothed_rtt());
425       } else {
426         QUICLDDebug("[%s] Lost: packet delta is too large (#%" PRId64 " largest=%" PRId64 " threshold=%" PRId32 ")",
427                     QUICDebugNames::pn_space(pn_space), it->first, this->_largest_acked_packet[static_cast<int>(pn_space)],
428                     this->_k_packet_threshold);
429       }
430 
431       if (unacked->in_flight) {
432         lost_packets.insert({it->first, it->second.get()});
433       }
434     } else if (this->_loss_time[static_cast<int>(pn_space)] == 0) {
435       this->_loss_time[static_cast<int>(pn_space)] = unacked->time_sent + loss_delay;
436     } else {
437       this->_loss_time[static_cast<int>(pn_space)] =
438         std::min(this->_loss_time[static_cast<int>(pn_space)], unacked->time_sent + loss_delay);
439     }
440   }
441 
442   // Inform the congestion controller of lost packets and
443   // lets it decide whether to retransmit immediately.
444   if (!lost_packets.empty()) {
445     this->_cc->on_packets_lost(lost_packets);
446     for (auto lost_packet : lost_packets) {
447       // -- ADDITIONAL CODE --
448       // Not sure how we can get feedback from congestion control and when we should retransmit the lost packets but we need to send
449       // them somewhere.
450       // I couldn't find the place so just send them here for now.
451       this->_retransmit_lost_packet(*lost_packet.second);
452       // -- END OF ADDITIONAL CODE --
453       // -- ADDITIONAL CODE --
454       this->_remove_from_sent_packet_list(lost_packet.first, pn_space);
455       // -- END OF ADDITIONAL CODE --
456     }
457   }
458 }
459 
460 // ===== Functions below are used on the spec but there're no pseudo code  =====
461 
462 void
_retransmit_all_unacked_crypto_data()463 QUICLossDetector::_retransmit_all_unacked_crypto_data()
464 {
465   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
466   for (auto i = 0; i < kPacketNumberSpace; i++) {
467     std::set<QUICPacketNumber> retransmitted_crypto_packets;
468     std::map<QUICPacketNumber, QUICPacketInfo *> lost_packets;
469     for (auto &info : this->_sent_packets[i]) {
470       if (info.second->is_crypto_packet) {
471         retransmitted_crypto_packets.insert(info.first);
472         this->_retransmit_lost_packet(*info.second);
473         lost_packets.insert({info.first, info.second.get()});
474       }
475     }
476 
477     this->_cc->on_packets_lost(lost_packets);
478     for (auto packet_number : retransmitted_crypto_packets) {
479       this->_remove_from_sent_packet_list(packet_number, static_cast<QUICPacketNumberSpace>(i));
480     }
481   }
482 }
483 
484 void
_send_packet(QUICEncryptionLevel level,bool padded)485 QUICLossDetector::_send_packet(QUICEncryptionLevel level, bool padded)
486 {
487   if (padded) {
488     this->_padder->request(level);
489   } else {
490     this->_pinger->request();
491   }
492   this->_cc->add_extra_credit();
493 }
494 
495 void
_send_one_or_two_packet()496 QUICLossDetector::_send_one_or_two_packet()
497 {
498   this->_send_packet(QUICEncryptionLevel::ONE_RTT);
499   this->_send_packet(QUICEncryptionLevel::ONE_RTT);
500   ink_assert(this->_pinger->count() >= 2);
501   QUICLDDebug("[%s] send ping frame %" PRIu64, QUICDebugNames::encryption_level(QUICEncryptionLevel::ONE_RTT),
502               this->_pinger->count());
503 }
504 
505 void
_send_one_handshake_packets()506 QUICLossDetector::_send_one_handshake_packets()
507 {
508   this->_send_packet(QUICEncryptionLevel::HANDSHAKE);
509   QUICLDDebug("[%s] send handshake packet", QUICDebugNames::encryption_level(QUICEncryptionLevel::HANDSHAKE));
510 }
511 
512 void
_send_one_padded_packets()513 QUICLossDetector::_send_one_padded_packets()
514 {
515   this->_send_packet(QUICEncryptionLevel::INITIAL, true);
516   QUICLDDebug("[%s] send PADDING frame", QUICDebugNames::encryption_level(QUICEncryptionLevel::INITIAL));
517 }
518 
519 // ===== Functions below are helper functions =====
520 
521 void
_retransmit_lost_packet(QUICPacketInfo & packet_info)522 QUICLossDetector::_retransmit_lost_packet(QUICPacketInfo &packet_info)
523 {
524   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
525 
526   QUICLDDebug("Retransmit %s packet #%" PRIu64, QUICDebugNames::packet_type(packet_info.type), packet_info.packet_number);
527   for (QUICFrameInfo &frame_info : packet_info.frames) {
528     auto reactor = frame_info.generated_by();
529     if (reactor == nullptr) {
530       continue;
531     }
532 
533     reactor->on_frame_lost(frame_info.id());
534   }
535 }
536 
537 std::vector<QUICPacketInfo *>
_determine_newly_acked_packets(const QUICAckFrame & ack_frame,int pn_space)538 QUICLossDetector::_determine_newly_acked_packets(const QUICAckFrame &ack_frame, int pn_space)
539 {
540   std::vector<QUICPacketInfo *> packets;
541   std::set<QUICAckFrame::PacketNumberRange> numbers;
542   QUICPacketNumber x = ack_frame.largest_acknowledged();
543   numbers.insert({x, static_cast<uint64_t>(x) - ack_frame.ack_block_section()->first_ack_block()});
544   x -= ack_frame.ack_block_section()->first_ack_block() + 1;
545   for (auto &&block : *(ack_frame.ack_block_section())) {
546     x -= block.gap() + 1;
547     numbers.insert({x, static_cast<uint64_t>(x) - block.length()});
548     x -= block.length() + 1;
549   }
550 
551   for (auto &&range : numbers) {
552     for (auto ite = this->_sent_packets[pn_space].rbegin(); ite != this->_sent_packets[pn_space].rend(); ite++) {
553       if (range.contains(ite->first)) {
554         packets.push_back(ite->second.get());
555       }
556     }
557   }
558 
559   return packets;
560 }
561 
562 void
_add_to_sent_packet_list(QUICPacketNumber packet_number,QUICPacketInfoUPtr packet_info)563 QUICLossDetector::_add_to_sent_packet_list(QUICPacketNumber packet_number, QUICPacketInfoUPtr packet_info)
564 {
565   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
566 
567   // Add to the list
568   int index = static_cast<int>(packet_info->pn_space);
569   this->_sent_packets[index].insert(std::pair<QUICPacketNumber, QUICPacketInfoUPtr>(packet_number, std::move(packet_info)));
570 
571   // Increment counters
572   auto ite = this->_sent_packets[index].find(packet_number);
573   if (ite != this->_sent_packets[index].end()) {
574     if (ite->second->is_crypto_packet) {
575       ++this->_crypto_outstanding;
576       ink_assert(this->_crypto_outstanding.load() > 0);
577     }
578     if (ite->second->ack_eliciting) {
579       ++this->_ack_eliciting_outstanding;
580       ink_assert(this->_ack_eliciting_outstanding.load() > 0);
581     }
582   }
583 }
584 
585 void
_remove_from_sent_packet_list(QUICPacketNumber packet_number,QUICPacketNumberSpace pn_space)586 QUICLossDetector::_remove_from_sent_packet_list(QUICPacketNumber packet_number, QUICPacketNumberSpace pn_space)
587 {
588   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
589 
590   auto ite = this->_sent_packets[static_cast<int>(pn_space)].find(packet_number);
591   this->_decrement_outstanding_counters(ite, pn_space);
592   this->_sent_packets[static_cast<int>(pn_space)].erase(packet_number);
593 }
594 
595 std::map<QUICPacketNumber, QUICPacketInfoUPtr>::iterator
_remove_from_sent_packet_list(std::map<QUICPacketNumber,QUICPacketInfoUPtr>::iterator it,QUICPacketNumberSpace pn_space)596 QUICLossDetector::_remove_from_sent_packet_list(std::map<QUICPacketNumber, QUICPacketInfoUPtr>::iterator it,
597                                                 QUICPacketNumberSpace pn_space)
598 {
599   SCOPED_MUTEX_LOCK(lock, this->_loss_detection_mutex, this_ethread());
600 
601   this->_decrement_outstanding_counters(it, pn_space);
602   return this->_sent_packets[static_cast<int>(pn_space)].erase(it);
603 }
604 
605 void
_decrement_outstanding_counters(std::map<QUICPacketNumber,QUICPacketInfoUPtr>::iterator it,QUICPacketNumberSpace pn_space)606 QUICLossDetector::_decrement_outstanding_counters(std::map<QUICPacketNumber, QUICPacketInfoUPtr>::iterator it,
607                                                   QUICPacketNumberSpace pn_space)
608 {
609   if (it != this->_sent_packets[static_cast<int>(pn_space)].end()) {
610     // Decrement counters
611     if (it->second->is_crypto_packet) {
612       ink_assert(this->_crypto_outstanding.load() > 0);
613       --this->_crypto_outstanding;
614     }
615     if (it->second->ack_eliciting) {
616       ink_assert(this->_ack_eliciting_outstanding.load() > 0);
617       --this->_ack_eliciting_outstanding;
618     }
619   }
620 }
621 
622 bool
_is_client_without_one_rtt_key() const623 QUICLossDetector::_is_client_without_one_rtt_key() const
624 {
625   return this->_context.connection_info()->direction() == NET_VCONNECTION_OUT &&
626          !((this->_context.key_info()->is_encryption_key_available(QUICKeyPhase::PHASE_1) &&
627             this->_context.key_info()->is_decryption_key_available(QUICKeyPhase::PHASE_1)) ||
628            (this->_context.key_info()->is_encryption_key_available(QUICKeyPhase::PHASE_0) &&
629             this->_context.key_info()->is_decryption_key_available(QUICKeyPhase::PHASE_0)));
630 }
631 
632 //
633 // QUICRTTMeasure
634 //
QUICRTTMeasure(const QUICLDConfig & ld_config)635 QUICRTTMeasure::QUICRTTMeasure(const QUICLDConfig &ld_config)
636   : _k_granularity(ld_config.granularity()), _k_initial_rtt(ld_config.initial_rtt())
637 {
638 }
639 
640 void
init(const QUICLDConfig & ld_config)641 QUICRTTMeasure::init(const QUICLDConfig &ld_config)
642 {
643   this->_k_granularity = ld_config.granularity();
644   this->_k_initial_rtt = ld_config.initial_rtt();
645 }
646 
647 ink_hrtime
smoothed_rtt() const648 QUICRTTMeasure::smoothed_rtt() const
649 {
650   return this->_smoothed_rtt;
651 }
652 
653 void
update_rtt(ink_hrtime latest_rtt,ink_hrtime ack_delay)654 QUICRTTMeasure::update_rtt(ink_hrtime latest_rtt, ink_hrtime ack_delay)
655 {
656   this->_latest_rtt = latest_rtt;
657 
658   if (this->_smoothed_rtt == 0) {
659     this->_min_rtt      = 0;
660     this->_smoothed_rtt = this->_latest_rtt;
661     this->_rttvar       = this->_latest_rtt / 2;
662     return;
663   }
664 
665   // min_rtt ignores ack delay.
666   this->_min_rtt = std::min(this->_min_rtt, latest_rtt);
667   // Limit ack_delay by max_ack_delay
668   ack_delay = std::min(ack_delay, this->_max_ack_delay);
669   // Adjust for ack delay if it's plausible.
670   auto adjusted_rtt = this->_latest_rtt;
671   if (adjusted_rtt > this->_min_rtt + ack_delay) {
672     adjusted_rtt -= ack_delay;
673   }
674 
675   // Based on {{RFC6298}}.
676   this->_rttvar       = 3.0 / 4.0 * this->_rttvar + 1.0 / 4.0 * ABS(this->_smoothed_rtt - adjusted_rtt);
677   this->_smoothed_rtt = 7.0 / 8.0 * this->_smoothed_rtt + 1.0 / 8.0 * adjusted_rtt;
678 }
679 
680 ink_hrtime
current_pto_period() const681 QUICRTTMeasure::current_pto_period() const
682 {
683   // PTO timeout
684   ink_hrtime alarm_duration;
685   alarm_duration = this->_smoothed_rtt + 4 * this->_rttvar + this->_max_ack_delay;
686   alarm_duration = std::max(alarm_duration, this->_k_granularity);
687   alarm_duration = alarm_duration * (1 << this->_pto_count);
688   return alarm_duration;
689 }
690 
691 ink_hrtime
congestion_period(uint32_t threshold) const692 QUICRTTMeasure::congestion_period(uint32_t threshold) const
693 {
694   ink_hrtime pto = this->_smoothed_rtt + std::max(this->_rttvar * 4, this->_k_granularity);
695   return pto * threshold;
696 }
697 
698 ink_hrtime
handshake_retransmit_timeout() const699 QUICRTTMeasure::handshake_retransmit_timeout() const
700 {
701   // Handshake retransmission alarm.
702   ink_hrtime timeout = 0;
703   if (this->_smoothed_rtt == 0) {
704     timeout = 2 * this->_k_initial_rtt;
705   } else {
706     timeout = 2 * this->_smoothed_rtt;
707   }
708   timeout = std::max(timeout, this->_k_granularity);
709   timeout = timeout * (1 << this->_crypto_count);
710 
711   return timeout;
712 }
713 
714 void
set_crypto_count(uint32_t count)715 QUICRTTMeasure::set_crypto_count(uint32_t count)
716 {
717   this->_crypto_count = count;
718 }
719 
720 void
set_pto_count(uint32_t count)721 QUICRTTMeasure::set_pto_count(uint32_t count)
722 {
723   this->_pto_count = count;
724 }
725 
726 ink_hrtime
rttvar() const727 QUICRTTMeasure::rttvar() const
728 {
729   return this->_rttvar;
730 }
731 
732 ink_hrtime
latest_rtt() const733 QUICRTTMeasure::latest_rtt() const
734 {
735   return this->_latest_rtt;
736 }
737 
738 uint32_t
crypto_count() const739 QUICRTTMeasure::crypto_count() const
740 {
741   return this->_crypto_count;
742 }
743 
744 uint32_t
pto_count() const745 QUICRTTMeasure::pto_count() const
746 {
747   return this->_pto_count;
748 }
749 
750 ink_hrtime
k_granularity() const751 QUICRTTMeasure::k_granularity() const
752 {
753   return this->_k_granularity;
754 }
755 
756 void
reset()757 QUICRTTMeasure::reset()
758 {
759   this->_crypto_count = 0;
760   this->_pto_count    = 0;
761   this->_smoothed_rtt = 0;
762   this->_rttvar       = 0;
763   this->_min_rtt      = 0;
764   this->_latest_rtt   = 0;
765 }
766