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 "I_EventSystem.h"
25 #include "QUICAckFrameCreator.h"
26 #include "QUICConfig.h"
27 #include <algorithm>
28 
QUICAckFrameManager()29 QUICAckFrameManager::QUICAckFrameManager()
30 {
31   for (auto i = 0; i < kPacketNumberSpace; i++) {
32     this->_ack_creator[i] = std::make_unique<QUICAckFrameCreator>(static_cast<QUICPacketNumberSpace>(i), this);
33   }
34 }
35 
~QUICAckFrameManager()36 QUICAckFrameManager::~QUICAckFrameManager() {}
37 
38 void
set_ack_delay_exponent(uint8_t ack_delay_exponent)39 QUICAckFrameManager::set_ack_delay_exponent(uint8_t ack_delay_exponent)
40 {
41   // This function should be called only once
42   ink_assert(this->_ack_delay_exponent == 0);
43   this->_ack_delay_exponent = ack_delay_exponent;
44 }
45 
46 int
update(QUICEncryptionLevel level,QUICPacketNumber packet_number,size_t size,bool ack_only)47 QUICAckFrameManager::update(QUICEncryptionLevel level, QUICPacketNumber packet_number, size_t size, bool ack_only)
48 {
49   if (!this->_is_level_matched(level)) {
50     return 0;
51   }
52 
53   auto index        = QUICTypeUtil::pn_space(level);
54   auto &ack_creator = this->_ack_creator[static_cast<int>(index)];
55   ack_creator->push_back(packet_number, size, ack_only);
56   return 0;
57 }
58 
59 /**
60  * @param connection_credit This is not used. Because ACK frame is not flow-controlled
61  */
62 QUICFrame *
generate_frame(uint8_t * buf,QUICEncryptionLevel level,uint64_t,uint16_t maximum_frame_size,size_t current_packet_size,uint32_t seq_num)63 QUICAckFrameManager::generate_frame(uint8_t *buf, QUICEncryptionLevel level, uint64_t /* connection_credit */,
64                                     uint16_t maximum_frame_size, size_t current_packet_size, uint32_t seq_num)
65 {
66   QUICAckFrame *ack_frame = nullptr;
67 
68   if (!this->_is_level_matched(level) || level == QUICEncryptionLevel::ZERO_RTT) {
69     return ack_frame;
70   }
71 
72   auto index        = QUICTypeUtil::pn_space(level);
73   auto &ack_creator = this->_ack_creator[static_cast<int>(index)];
74   ack_frame         = ack_creator->generate_ack_frame(buf, maximum_frame_size);
75 
76   if (ack_frame != nullptr) {
77     QUICFrameInformationUPtr info  = QUICFrameInformationUPtr(quicFrameInformationAllocator.alloc());
78     AckFrameInfo *ack_info         = reinterpret_cast<AckFrameInfo *>(info->data);
79     ack_info->largest_acknowledged = ack_frame->largest_acknowledged();
80 
81     info->level = level;
82     info->type  = ack_frame->type();
83     this->_records_frame(ack_frame->id(), std::move(info));
84   }
85 
86   return ack_frame;
87 }
88 
89 bool
will_generate_frame(QUICEncryptionLevel level,size_t current_packet_size,bool ack_eliciting,uint32_t seq_num)90 QUICAckFrameManager::will_generate_frame(QUICEncryptionLevel level, size_t current_packet_size, bool ack_eliciting,
91                                          uint32_t seq_num)
92 {
93   // No ACK frame on ZERO_RTT level
94   if (!this->_is_level_matched(level) || level == QUICEncryptionLevel::ZERO_RTT) {
95     return false;
96   }
97 
98   auto index = QUICTypeUtil::pn_space(level);
99   return this->_ack_creator[static_cast<int>(index)]->is_ack_frame_ready();
100 }
101 
102 void
_on_frame_acked(QUICFrameInformationUPtr & info)103 QUICAckFrameManager::_on_frame_acked(QUICFrameInformationUPtr &info)
104 {
105   ink_assert(info->type == QUICFrameType::ACK);
106   AckFrameInfo *ack_info = reinterpret_cast<AckFrameInfo *>(info->data);
107   auto index             = QUICTypeUtil::pn_space(info->level);
108   this->_ack_creator[static_cast<int>(index)]->forget(ack_info->largest_acknowledged);
109 }
110 
111 void
_on_frame_lost(QUICFrameInformationUPtr & info)112 QUICAckFrameManager::_on_frame_lost(QUICFrameInformationUPtr &info)
113 {
114   ink_assert(info->type == QUICFrameType::ACK);
115   auto index = QUICTypeUtil::pn_space(info->level);
116   // when ack frame lost. Force to refresh the frame.
117   this->_ack_creator[static_cast<int>(index)]->refresh_state();
118 }
119 
120 QUICFrameId
issue_frame_id()121 QUICAckFrameManager::issue_frame_id()
122 {
123   return this->_issue_frame_id();
124 }
125 
126 uint8_t
ack_delay_exponent() const127 QUICAckFrameManager::ack_delay_exponent() const
128 {
129   return this->_ack_delay_exponent;
130 }
131 
132 void
set_max_ack_delay(uint16_t delay)133 QUICAckFrameManager::set_max_ack_delay(uint16_t delay)
134 {
135   for (auto i = 0; i < kPacketNumberSpace; i++) {
136     this->_ack_creator[i]->set_max_ack_delay(delay);
137   }
138 }
139 
140 //
141 // QUICAckFrameManager::QUICAckFrameCreator
142 //
143 void
refresh_state()144 QUICAckFrameManager::QUICAckFrameCreator::refresh_state()
145 {
146   if (this->_packet_numbers.empty() || !this->_available) {
147     return;
148   }
149 
150   // we have something to send
151   this->_should_send = true;
152 }
153 
154 void
forget(QUICPacketNumber largest_acknowledged)155 QUICAckFrameManager::QUICAckFrameCreator::forget(QUICPacketNumber largest_acknowledged)
156 {
157   this->_available = false;
158   this->sort();
159   std::list<RecvdPacket> remove_list;
160   for (auto it = this->_packet_numbers.begin(); it != this->_packet_numbers.end(); it++) {
161     if ((*it).packet_number == largest_acknowledged) {
162       remove_list.splice(remove_list.begin(), this->_packet_numbers, it, this->_packet_numbers.end());
163       break;
164     }
165     this->_available |= !(*it).ack_only;
166   }
167 
168   if (this->_packet_numbers.empty() || !this->_available) {
169     this->_should_send = false;
170   }
171 }
172 
173 void
push_back(QUICPacketNumber packet_number,size_t size,bool ack_only)174 QUICAckFrameManager::QUICAckFrameCreator::push_back(QUICPacketNumber packet_number, size_t size, bool ack_only)
175 {
176   if (packet_number == 0 || packet_number > this->_largest_ack_number) {
177     this->_largest_ack_received_time = Thread::get_hrtime();
178     this->_largest_ack_number        = packet_number;
179   }
180 
181   if (!this->_latest_packet_received_time) {
182     this->_latest_packet_received_time = Thread::get_hrtime();
183   }
184 
185   // unorder packet should send ack immediately to accellerate the recovery
186   if (this->_expect_next != packet_number) {
187     this->_should_send = true;
188   }
189 
190   // every 2 full-packet should send a ack frame like tcp
191   this->_size_unsend += size;
192   // FIXME: this size should be fixed with PMTU
193   if (this->_size_unsend > 2 * 1480) {
194     this->_size_unsend = 0;
195     this->_should_send = true;
196   }
197 
198   // can not delay handshake packet
199   if ((this->_pn_space == QUICPacketNumberSpace::Initial || this->_pn_space == QUICPacketNumberSpace::Handshake) && !ack_only) {
200     this->_should_send = true;
201   }
202 
203   if (!ack_only) {
204     this->_available    = true;
205     this->_has_new_data = true;
206   } else {
207     this->_should_send = this->_available ? this->_should_send : false;
208   }
209 
210   this->_expect_next = packet_number + 1;
211   this->_packet_numbers.push_back({ack_only, packet_number});
212 }
213 
214 size_t
size()215 QUICAckFrameManager::QUICAckFrameCreator::size()
216 {
217   return this->_packet_numbers.size();
218 }
219 
220 void
clear()221 QUICAckFrameManager::QUICAckFrameCreator::clear()
222 {
223   this->_packet_numbers.clear();
224   this->_largest_ack_number          = 0;
225   this->_largest_ack_received_time   = 0;
226   this->_latest_packet_received_time = 0;
227   this->_size_unsend                 = 0;
228   this->_should_send                 = false;
229   this->_available                   = false;
230 }
231 
232 QUICPacketNumber
largest_ack_number()233 QUICAckFrameManager::QUICAckFrameCreator::largest_ack_number()
234 {
235   return this->_largest_ack_number;
236 }
237 
238 ink_hrtime
largest_ack_received_time()239 QUICAckFrameManager::QUICAckFrameCreator::largest_ack_received_time()
240 {
241   return this->_largest_ack_received_time;
242 }
243 
244 void
sort()245 QUICAckFrameManager::QUICAckFrameCreator::sort()
246 {
247   //  TODO Find more smart way
248   this->_packet_numbers.sort([](const RecvdPacket &a, const RecvdPacket &b) -> bool { return a.packet_number > b.packet_number; });
249 }
250 
251 QUICAckFrame *
generate_ack_frame(uint8_t * buf,uint16_t maximum_frame_size)252 QUICAckFrameManager::QUICAckFrameCreator::generate_ack_frame(uint8_t *buf, uint16_t maximum_frame_size)
253 {
254   QUICAckFrame *ack_frame = nullptr;
255   if (!this->_available) {
256     this->_should_send = false;
257     return ack_frame;
258   }
259 
260   ack_frame = this->_create_ack_frame(buf);
261   if (ack_frame == nullptr || ack_frame->size() < maximum_frame_size) {
262     this->_should_send                 = false;
263     this->_latest_packet_received_time = 0;
264   } else {
265     return nullptr;
266   }
267 
268   return ack_frame;
269 }
270 
271 QUICAckFrame *
_create_ack_frame(uint8_t * buf)272 QUICAckFrameManager::QUICAckFrameCreator::_create_ack_frame(uint8_t *buf)
273 {
274   ink_assert(!this->_packet_numbers.empty());
275   QUICAckFrame *ack_frame = nullptr;
276   this->sort();
277   std::list<RecvdPacket> &list = this->_packet_numbers;
278 
279   this->_has_new_data = false;
280 
281   uint8_t gap     = 0;
282   uint64_t length = 0;
283   auto it         = list.begin();
284 
285   // skip ack_only packets
286   for (; it != list.end(); it++) {
287     if (!(*it).ack_only) {
288       break;
289     }
290   }
291 
292   if (it == list.end()) {
293     return ack_frame;
294   }
295 
296   QUICPacketNumber largest_ack_number = (*it).packet_number;
297   QUICPacketNumber last_ack_number    = largest_ack_number;
298 
299   while (it != list.end()) {
300     QUICPacketNumber pn = (*it).packet_number;
301     if (pn == last_ack_number) {
302       last_ack_number--;
303       length++;
304       it++;
305       continue;
306     }
307 
308     ink_assert(length > 0);
309 
310     if (ack_frame) {
311       ack_frame->ack_block_section()->add_ack_block({static_cast<uint8_t>(gap - 1), length - 1});
312     } else {
313       uint64_t delay = this->_calculate_delay();
314       ack_frame      = QUICFrameFactory::create_ack_frame(buf, largest_ack_number, delay, length - 1,
315                                                      this->_ack_manager->issue_frame_id(), this->_ack_manager);
316     }
317 
318     gap             = last_ack_number - pn;
319     last_ack_number = pn;
320     length          = 0;
321   }
322 
323   if (ack_frame) {
324     ack_frame->ack_block_section()->add_ack_block({static_cast<uint8_t>(gap - 1), length - 1});
325   } else {
326     uint64_t delay = this->_calculate_delay();
327     ack_frame = QUICFrameFactory::create_ack_frame(buf, largest_ack_number, delay, length - 1, this->_ack_manager->issue_frame_id(),
328                                                    this->_ack_manager);
329   }
330 
331   return ack_frame;
332 }
333 
334 uint64_t
_calculate_delay()335 QUICAckFrameManager::QUICAckFrameCreator::_calculate_delay()
336 {
337   // Ack delay is in microseconds and scaled
338   ink_hrtime now             = Thread::get_hrtime();
339   uint64_t delay             = (now - this->_largest_ack_received_time) / 1000;
340   uint8_t ack_delay_exponent = 3;
341   if (this->_pn_space != QUICPacketNumberSpace::Initial && this->_pn_space != QUICPacketNumberSpace::Handshake) {
342     ack_delay_exponent = this->_ack_manager->ack_delay_exponent();
343   }
344   return delay >> ack_delay_exponent;
345 }
346 
347 bool
available() const348 QUICAckFrameManager::QUICAckFrameCreator::available() const
349 {
350   return this->_available;
351 }
352 
353 bool
is_ack_frame_ready()354 QUICAckFrameManager::QUICAckFrameCreator::is_ack_frame_ready()
355 {
356   if (this->_available && this->_has_new_data && !this->_packet_numbers.empty() &&
357       this->_latest_packet_received_time + this->_max_ack_delay * HRTIME_MSECOND <= Thread::get_hrtime()) {
358     // when we has new data and the data is available to send (not ack only). and we delay for too much time. Send it out
359     this->_should_send = true;
360   }
361 
362   return this->_should_send && this->_available && !this->_packet_numbers.empty();
363 }
364 
365 void
set_max_ack_delay(uint16_t delay)366 QUICAckFrameManager::QUICAckFrameCreator::set_max_ack_delay(uint16_t delay)
367 {
368   this->_max_ack_delay = delay;
369 }
370 
QUICAckFrameCreator(QUICPacketNumberSpace pn_space,QUICAckFrameManager * ack_manager)371 QUICAckFrameManager::QUICAckFrameCreator::QUICAckFrameCreator(QUICPacketNumberSpace pn_space, QUICAckFrameManager *ack_manager)
372   : _ack_manager(ack_manager), _pn_space(pn_space)
373 {
374 }
375 
~QUICAckFrameCreator()376 QUICAckFrameManager::QUICAckFrameCreator::~QUICAckFrameCreator() {}
377 
378 /*
379    No limit of encryption level.
380    ```
381    std::array<QUICEncryptionLevel, 4> _encryption_level_filter = {
382      QUICEncryptionLevel::INITIAL,
383      QUICEncryptionLevel::ZERO_RTT,
384      QUICEncryptionLevel::HANDSHAKE,
385      QUICEncryptionLevel::ONE_RTT,
386    };
387    ```
388 */
389 bool
_is_level_matched(QUICEncryptionLevel level)390 QUICAckFrameManager::_is_level_matched(QUICEncryptionLevel level)
391 {
392   return true;
393 }
394