1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/quic_connection_id_manager.h"
6
7 #include <cstdio>
8
9 #include "quiche/quic/core/quic_clock.h"
10 #include "quiche/quic/core/quic_connection_id.h"
11 #include "quiche/quic/core/quic_error_codes.h"
12 #include "quiche/quic/core/quic_utils.h"
13 #include "quiche/quic/platform/api/quic_flag_utils.h"
14 #include "quiche/quic/platform/api/quic_flags.h"
15 #include "quiche/common/platform/api/quiche_logging.h"
16
17 namespace quic {
18
QuicConnectionIdData(const QuicConnectionId & connection_id,uint64_t sequence_number,const StatelessResetToken & stateless_reset_token)19 QuicConnectionIdData::QuicConnectionIdData(
20 const QuicConnectionId& connection_id, uint64_t sequence_number,
21 const StatelessResetToken& stateless_reset_token)
22 : connection_id(connection_id),
23 sequence_number(sequence_number),
24 stateless_reset_token(stateless_reset_token) {}
25
26 namespace {
27
28 class RetirePeerIssuedConnectionIdAlarm
29 : public QuicAlarm::DelegateWithContext {
30 public:
RetirePeerIssuedConnectionIdAlarm(QuicConnectionIdManagerVisitorInterface * visitor,QuicConnectionContext * context)31 explicit RetirePeerIssuedConnectionIdAlarm(
32 QuicConnectionIdManagerVisitorInterface* visitor,
33 QuicConnectionContext* context)
34 : QuicAlarm::DelegateWithContext(context), visitor_(visitor) {}
35 RetirePeerIssuedConnectionIdAlarm(const RetirePeerIssuedConnectionIdAlarm&) =
36 delete;
37 RetirePeerIssuedConnectionIdAlarm& operator=(
38 const RetirePeerIssuedConnectionIdAlarm&) = delete;
39
OnAlarm()40 void OnAlarm() override { visitor_->OnPeerIssuedConnectionIdRetired(); }
41
42 private:
43 QuicConnectionIdManagerVisitorInterface* visitor_;
44 };
45
FindConnectionIdData(const std::vector<QuicConnectionIdData> & cid_data_vector,const QuicConnectionId & cid)46 std::vector<QuicConnectionIdData>::const_iterator FindConnectionIdData(
47 const std::vector<QuicConnectionIdData>& cid_data_vector,
48 const QuicConnectionId& cid) {
49 return std::find_if(cid_data_vector.begin(), cid_data_vector.end(),
50 [&cid](const QuicConnectionIdData& cid_data) {
51 return cid == cid_data.connection_id;
52 });
53 }
54
FindConnectionIdData(std::vector<QuicConnectionIdData> * cid_data_vector,const QuicConnectionId & cid)55 std::vector<QuicConnectionIdData>::iterator FindConnectionIdData(
56 std::vector<QuicConnectionIdData>* cid_data_vector,
57 const QuicConnectionId& cid) {
58 return std::find_if(cid_data_vector->begin(), cid_data_vector->end(),
59 [&cid](const QuicConnectionIdData& cid_data) {
60 return cid == cid_data.connection_id;
61 });
62 }
63
64 } // namespace
65
QuicPeerIssuedConnectionIdManager(size_t active_connection_id_limit,const QuicConnectionId & initial_peer_issued_connection_id,const QuicClock * clock,QuicAlarmFactory * alarm_factory,QuicConnectionIdManagerVisitorInterface * visitor,QuicConnectionContext * context)66 QuicPeerIssuedConnectionIdManager::QuicPeerIssuedConnectionIdManager(
67 size_t active_connection_id_limit,
68 const QuicConnectionId& initial_peer_issued_connection_id,
69 const QuicClock* clock, QuicAlarmFactory* alarm_factory,
70 QuicConnectionIdManagerVisitorInterface* visitor,
71 QuicConnectionContext* context)
72 : active_connection_id_limit_(active_connection_id_limit),
73 clock_(clock),
74 retire_connection_id_alarm_(alarm_factory->CreateAlarm(
75 new RetirePeerIssuedConnectionIdAlarm(visitor, context))) {
76 QUICHE_DCHECK_GE(active_connection_id_limit_, 2u);
77 QUICHE_DCHECK(!initial_peer_issued_connection_id.IsEmpty());
78 active_connection_id_data_.emplace_back<const QuicConnectionId&, uint64_t,
79 const StatelessResetToken&>(
80 initial_peer_issued_connection_id,
81 /*sequence_number=*/0u, {});
82 recent_new_connection_id_sequence_numbers_.Add(0u, 1u);
83 }
84
~QuicPeerIssuedConnectionIdManager()85 QuicPeerIssuedConnectionIdManager::~QuicPeerIssuedConnectionIdManager() {
86 retire_connection_id_alarm_->Cancel();
87 }
88
IsConnectionIdNew(const QuicNewConnectionIdFrame & frame)89 bool QuicPeerIssuedConnectionIdManager::IsConnectionIdNew(
90 const QuicNewConnectionIdFrame& frame) {
91 auto is_old_connection_id = [&frame](const QuicConnectionIdData& cid_data) {
92 return cid_data.connection_id == frame.connection_id;
93 };
94 if (std::any_of(active_connection_id_data_.begin(),
95 active_connection_id_data_.end(), is_old_connection_id)) {
96 return false;
97 }
98 if (std::any_of(unused_connection_id_data_.begin(),
99 unused_connection_id_data_.end(), is_old_connection_id)) {
100 return false;
101 }
102 if (std::any_of(to_be_retired_connection_id_data_.begin(),
103 to_be_retired_connection_id_data_.end(),
104 is_old_connection_id)) {
105 return false;
106 }
107 return true;
108 }
109
PrepareToRetireConnectionIdPriorTo(uint64_t retire_prior_to,std::vector<QuicConnectionIdData> * cid_data_vector)110 void QuicPeerIssuedConnectionIdManager::PrepareToRetireConnectionIdPriorTo(
111 uint64_t retire_prior_to,
112 std::vector<QuicConnectionIdData>* cid_data_vector) {
113 auto it2 = cid_data_vector->begin();
114 for (auto it = cid_data_vector->begin(); it != cid_data_vector->end(); ++it) {
115 if (it->sequence_number >= retire_prior_to) {
116 *it2++ = *it;
117 } else {
118 to_be_retired_connection_id_data_.push_back(*it);
119 if (!retire_connection_id_alarm_->IsSet()) {
120 retire_connection_id_alarm_->Set(clock_->ApproximateNow());
121 }
122 }
123 }
124 cid_data_vector->erase(it2, cid_data_vector->end());
125 }
126
OnNewConnectionIdFrame(const QuicNewConnectionIdFrame & frame,std::string * error_detail,bool * is_duplicate_frame)127 QuicErrorCode QuicPeerIssuedConnectionIdManager::OnNewConnectionIdFrame(
128 const QuicNewConnectionIdFrame& frame, std::string* error_detail,
129 bool* is_duplicate_frame) {
130 if (recent_new_connection_id_sequence_numbers_.Contains(
131 frame.sequence_number)) {
132 // This frame has a recently seen sequence number. Ignore.
133 *is_duplicate_frame = true;
134 return QUIC_NO_ERROR;
135 }
136 if (!IsConnectionIdNew(frame)) {
137 *error_detail =
138 "Received a NEW_CONNECTION_ID frame that reuses a previously seen Id.";
139 return IETF_QUIC_PROTOCOL_VIOLATION;
140 }
141
142 recent_new_connection_id_sequence_numbers_.AddOptimizedForAppend(
143 frame.sequence_number, frame.sequence_number + 1);
144
145 if (recent_new_connection_id_sequence_numbers_.Size() >
146 kMaxNumConnectionIdSequenceNumberIntervals) {
147 *error_detail =
148 "Too many disjoint connection Id sequence number intervals.";
149 return IETF_QUIC_PROTOCOL_VIOLATION;
150 }
151
152 // QuicFramer::ProcessNewConnectionIdFrame guarantees that
153 // frame.sequence_number >= frame.retire_prior_to, and hence there is no need
154 // to check that.
155 if (frame.sequence_number < max_new_connection_id_frame_retire_prior_to_) {
156 // Later frames have asked for retirement of the current frame.
157 to_be_retired_connection_id_data_.emplace_back(frame.connection_id,
158 frame.sequence_number,
159 frame.stateless_reset_token);
160 if (!retire_connection_id_alarm_->IsSet()) {
161 retire_connection_id_alarm_->Set(clock_->ApproximateNow());
162 }
163 return QUIC_NO_ERROR;
164 }
165 if (frame.retire_prior_to > max_new_connection_id_frame_retire_prior_to_) {
166 max_new_connection_id_frame_retire_prior_to_ = frame.retire_prior_to;
167 PrepareToRetireConnectionIdPriorTo(frame.retire_prior_to,
168 &active_connection_id_data_);
169 PrepareToRetireConnectionIdPriorTo(frame.retire_prior_to,
170 &unused_connection_id_data_);
171 }
172
173 if (active_connection_id_data_.size() + unused_connection_id_data_.size() >=
174 active_connection_id_limit_) {
175 *error_detail = "Peer provides more connection IDs than the limit.";
176 return QUIC_CONNECTION_ID_LIMIT_ERROR;
177 }
178
179 unused_connection_id_data_.emplace_back(
180 frame.connection_id, frame.sequence_number, frame.stateless_reset_token);
181 return QUIC_NO_ERROR;
182 }
183
184 const QuicConnectionIdData*
ConsumeOneUnusedConnectionId()185 QuicPeerIssuedConnectionIdManager::ConsumeOneUnusedConnectionId() {
186 if (unused_connection_id_data_.empty()) {
187 return nullptr;
188 }
189 active_connection_id_data_.push_back(unused_connection_id_data_.back());
190 unused_connection_id_data_.pop_back();
191 return &active_connection_id_data_.back();
192 }
193
PrepareToRetireActiveConnectionId(const QuicConnectionId & cid)194 void QuicPeerIssuedConnectionIdManager::PrepareToRetireActiveConnectionId(
195 const QuicConnectionId& cid) {
196 auto it = FindConnectionIdData(active_connection_id_data_, cid);
197 if (it == active_connection_id_data_.end()) {
198 // The cid has already been retired.
199 return;
200 }
201 to_be_retired_connection_id_data_.push_back(*it);
202 active_connection_id_data_.erase(it);
203 if (!retire_connection_id_alarm_->IsSet()) {
204 retire_connection_id_alarm_->Set(clock_->ApproximateNow());
205 }
206 }
207
MaybeRetireUnusedConnectionIds(const std::vector<QuicConnectionId> & active_connection_ids_on_path)208 void QuicPeerIssuedConnectionIdManager::MaybeRetireUnusedConnectionIds(
209 const std::vector<QuicConnectionId>& active_connection_ids_on_path) {
210 std::vector<QuicConnectionId> cids_to_retire;
211 for (const auto& cid_data : active_connection_id_data_) {
212 if (std::find(active_connection_ids_on_path.begin(),
213 active_connection_ids_on_path.end(),
214 cid_data.connection_id) ==
215 active_connection_ids_on_path.end()) {
216 cids_to_retire.push_back(cid_data.connection_id);
217 }
218 }
219 for (const auto& cid : cids_to_retire) {
220 PrepareToRetireActiveConnectionId(cid);
221 }
222 }
223
IsConnectionIdActive(const QuicConnectionId & cid) const224 bool QuicPeerIssuedConnectionIdManager::IsConnectionIdActive(
225 const QuicConnectionId& cid) const {
226 return FindConnectionIdData(active_connection_id_data_, cid) !=
227 active_connection_id_data_.end();
228 }
229
230 std::vector<uint64_t> QuicPeerIssuedConnectionIdManager::
ConsumeToBeRetiredConnectionIdSequenceNumbers()231 ConsumeToBeRetiredConnectionIdSequenceNumbers() {
232 std::vector<uint64_t> result;
233 for (auto const& cid_data : to_be_retired_connection_id_data_) {
234 result.push_back(cid_data.sequence_number);
235 }
236 to_be_retired_connection_id_data_.clear();
237 return result;
238 }
239
ReplaceConnectionId(const QuicConnectionId & old_connection_id,const QuicConnectionId & new_connection_id)240 void QuicPeerIssuedConnectionIdManager::ReplaceConnectionId(
241 const QuicConnectionId& old_connection_id,
242 const QuicConnectionId& new_connection_id) {
243 auto it1 =
244 FindConnectionIdData(&active_connection_id_data_, old_connection_id);
245 if (it1 != active_connection_id_data_.end()) {
246 it1->connection_id = new_connection_id;
247 return;
248 }
249 auto it2 = FindConnectionIdData(&to_be_retired_connection_id_data_,
250 old_connection_id);
251 if (it2 != to_be_retired_connection_id_data_.end()) {
252 it2->connection_id = new_connection_id;
253 }
254 }
255
256 namespace {
257
258 class RetireSelfIssuedConnectionIdAlarmDelegate
259 : public QuicAlarm::DelegateWithContext {
260 public:
RetireSelfIssuedConnectionIdAlarmDelegate(QuicSelfIssuedConnectionIdManager * connection_id_manager,QuicConnectionContext * context)261 explicit RetireSelfIssuedConnectionIdAlarmDelegate(
262 QuicSelfIssuedConnectionIdManager* connection_id_manager,
263 QuicConnectionContext* context)
264 : QuicAlarm::DelegateWithContext(context),
265 connection_id_manager_(connection_id_manager) {}
266 RetireSelfIssuedConnectionIdAlarmDelegate(
267 const RetireSelfIssuedConnectionIdAlarmDelegate&) = delete;
268 RetireSelfIssuedConnectionIdAlarmDelegate& operator=(
269 const RetireSelfIssuedConnectionIdAlarmDelegate&) = delete;
270
OnAlarm()271 void OnAlarm() override { connection_id_manager_->RetireConnectionId(); }
272
273 private:
274 QuicSelfIssuedConnectionIdManager* connection_id_manager_;
275 };
276
277 } // namespace
278
QuicSelfIssuedConnectionIdManager(size_t active_connection_id_limit,const QuicConnectionId & initial_connection_id,const QuicClock * clock,QuicAlarmFactory * alarm_factory,QuicConnectionIdManagerVisitorInterface * visitor,QuicConnectionContext * context,ConnectionIdGeneratorInterface & generator)279 QuicSelfIssuedConnectionIdManager::QuicSelfIssuedConnectionIdManager(
280 size_t active_connection_id_limit,
281 const QuicConnectionId& initial_connection_id, const QuicClock* clock,
282 QuicAlarmFactory* alarm_factory,
283 QuicConnectionIdManagerVisitorInterface* visitor,
284 QuicConnectionContext* context, ConnectionIdGeneratorInterface& generator)
285 : active_connection_id_limit_(active_connection_id_limit),
286 clock_(clock),
287 visitor_(visitor),
288 retire_connection_id_alarm_(alarm_factory->CreateAlarm(
289 new RetireSelfIssuedConnectionIdAlarmDelegate(this, context))),
290 last_connection_id_(initial_connection_id),
291 next_connection_id_sequence_number_(1u),
292 last_connection_id_consumed_by_self_sequence_number_(0u),
293 connection_id_generator_(generator) {
294 active_connection_ids_.emplace_back(initial_connection_id, 0u);
295 }
296
~QuicSelfIssuedConnectionIdManager()297 QuicSelfIssuedConnectionIdManager::~QuicSelfIssuedConnectionIdManager() {
298 retire_connection_id_alarm_->Cancel();
299 }
300
301 std::optional<QuicNewConnectionIdFrame>
MaybeIssueNewConnectionId()302 QuicSelfIssuedConnectionIdManager::MaybeIssueNewConnectionId() {
303 std::optional<QuicConnectionId> new_cid =
304 connection_id_generator_.GenerateNextConnectionId(last_connection_id_);
305 if (!new_cid.has_value()) {
306 return {};
307 }
308 if (!visitor_->MaybeReserveConnectionId(*new_cid)) {
309 return {};
310 }
311 QuicNewConnectionIdFrame frame;
312 frame.connection_id = *new_cid;
313 frame.sequence_number = next_connection_id_sequence_number_++;
314 frame.stateless_reset_token =
315 QuicUtils::GenerateStatelessResetToken(frame.connection_id);
316 active_connection_ids_.emplace_back(frame.connection_id,
317 frame.sequence_number);
318 frame.retire_prior_to = active_connection_ids_.front().second;
319 last_connection_id_ = frame.connection_id;
320 return frame;
321 }
322
323 std::optional<QuicNewConnectionIdFrame> QuicSelfIssuedConnectionIdManager::
MaybeIssueNewConnectionIdForPreferredAddress()324 MaybeIssueNewConnectionIdForPreferredAddress() {
325 std::optional<QuicNewConnectionIdFrame> frame = MaybeIssueNewConnectionId();
326 QUICHE_DCHECK(!frame.has_value() || (frame->sequence_number == 1u));
327 return frame;
328 }
329
OnRetireConnectionIdFrame(const QuicRetireConnectionIdFrame & frame,QuicTime::Delta pto_delay,std::string * error_detail)330 QuicErrorCode QuicSelfIssuedConnectionIdManager::OnRetireConnectionIdFrame(
331 const QuicRetireConnectionIdFrame& frame, QuicTime::Delta pto_delay,
332 std::string* error_detail) {
333 QUICHE_DCHECK(!active_connection_ids_.empty());
334 if (frame.sequence_number >= next_connection_id_sequence_number_) {
335 *error_detail = "To be retired connecton ID is never issued.";
336 return IETF_QUIC_PROTOCOL_VIOLATION;
337 }
338
339 auto it =
340 std::find_if(active_connection_ids_.begin(), active_connection_ids_.end(),
341 [&frame](const std::pair<QuicConnectionId, uint64_t>& p) {
342 return p.second == frame.sequence_number;
343 });
344 // The corresponding connection ID has been retired. Ignore.
345 if (it == active_connection_ids_.end()) {
346 return QUIC_NO_ERROR;
347 }
348
349 if (to_be_retired_connection_ids_.size() + active_connection_ids_.size() >=
350 kMaxNumConnectonIdsInUse) {
351 // Close connection if the number of connection IDs in use will exeed the
352 // limit, i.e., peer retires connection ID too fast.
353 *error_detail = "There are too many connection IDs in use.";
354 return QUIC_TOO_MANY_CONNECTION_ID_WAITING_TO_RETIRE;
355 }
356
357 QuicTime retirement_time = clock_->ApproximateNow() + 3 * pto_delay;
358 if (!to_be_retired_connection_ids_.empty()) {
359 retirement_time =
360 std::max(retirement_time, to_be_retired_connection_ids_.back().second);
361 }
362
363 to_be_retired_connection_ids_.emplace_back(it->first, retirement_time);
364 if (!retire_connection_id_alarm_->IsSet()) {
365 retire_connection_id_alarm_->Set(retirement_time);
366 }
367
368 active_connection_ids_.erase(it);
369 MaybeSendNewConnectionIds();
370
371 return QUIC_NO_ERROR;
372 }
373
374 std::vector<QuicConnectionId>
GetUnretiredConnectionIds() const375 QuicSelfIssuedConnectionIdManager::GetUnretiredConnectionIds() const {
376 std::vector<QuicConnectionId> unretired_ids;
377 for (const auto& cid_pair : to_be_retired_connection_ids_) {
378 unretired_ids.push_back(cid_pair.first);
379 }
380 for (const auto& cid_pair : active_connection_ids_) {
381 unretired_ids.push_back(cid_pair.first);
382 }
383 return unretired_ids;
384 }
385
GetOneActiveConnectionId() const386 QuicConnectionId QuicSelfIssuedConnectionIdManager::GetOneActiveConnectionId()
387 const {
388 QUICHE_DCHECK(!active_connection_ids_.empty());
389 return active_connection_ids_.front().first;
390 }
391
RetireConnectionId()392 void QuicSelfIssuedConnectionIdManager::RetireConnectionId() {
393 if (to_be_retired_connection_ids_.empty()) {
394 QUIC_BUG(quic_bug_12420_1)
395 << "retire_connection_id_alarm fired but there is no connection ID "
396 "to be retired.";
397 return;
398 }
399 QuicTime now = clock_->ApproximateNow();
400 auto it = to_be_retired_connection_ids_.begin();
401 do {
402 visitor_->OnSelfIssuedConnectionIdRetired(it->first);
403 ++it;
404 } while (it != to_be_retired_connection_ids_.end() && it->second <= now);
405 to_be_retired_connection_ids_.erase(to_be_retired_connection_ids_.begin(),
406 it);
407 // Set the alarm again if there is another connection ID to be removed.
408 if (!to_be_retired_connection_ids_.empty()) {
409 retire_connection_id_alarm_->Set(
410 to_be_retired_connection_ids_.front().second);
411 }
412 }
413
MaybeSendNewConnectionIds()414 void QuicSelfIssuedConnectionIdManager::MaybeSendNewConnectionIds() {
415 while (active_connection_ids_.size() < active_connection_id_limit_) {
416 std::optional<QuicNewConnectionIdFrame> frame = MaybeIssueNewConnectionId();
417 if (!frame.has_value()) {
418 break;
419 }
420 if (!visitor_->SendNewConnectionId(*frame)) {
421 break;
422 }
423 }
424 }
425
HasConnectionIdToConsume() const426 bool QuicSelfIssuedConnectionIdManager::HasConnectionIdToConsume() const {
427 for (const auto& active_cid_data : active_connection_ids_) {
428 if (active_cid_data.second >
429 last_connection_id_consumed_by_self_sequence_number_) {
430 return true;
431 }
432 }
433 return false;
434 }
435
436 std::optional<QuicConnectionId>
ConsumeOneConnectionId()437 QuicSelfIssuedConnectionIdManager::ConsumeOneConnectionId() {
438 for (const auto& active_cid_data : active_connection_ids_) {
439 if (active_cid_data.second >
440 last_connection_id_consumed_by_self_sequence_number_) {
441 // Since connection IDs in active_connection_ids_ has monotonically
442 // increasing sequence numbers, the returned connection ID has the
443 // smallest sequence number among all unconsumed active connection IDs.
444 last_connection_id_consumed_by_self_sequence_number_ =
445 active_cid_data.second;
446 return active_cid_data.first;
447 }
448 }
449 return std::nullopt;
450 }
451
IsConnectionIdInUse(const QuicConnectionId & cid) const452 bool QuicSelfIssuedConnectionIdManager::IsConnectionIdInUse(
453 const QuicConnectionId& cid) const {
454 for (const auto& active_cid_data : active_connection_ids_) {
455 if (active_cid_data.first == cid) {
456 return true;
457 }
458 }
459 for (const auto& to_be_retired_cid_data : to_be_retired_connection_ids_) {
460 if (to_be_retired_cid_data.first == cid) {
461 return true;
462 }
463 }
464 return false;
465 }
466
467 } // namespace quic
468