1 // Copyright (c) 2016 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_buffered_packet_store.h"
6
7 #include <cstddef>
8 #include <list>
9 #include <memory>
10 #include <optional>
11 #include <string>
12 #include <utility>
13
14 #include "absl/strings/string_view.h"
15 #include "quiche/quic/core/connection_id_generator.h"
16 #include "quiche/quic/core/quic_alarm.h"
17 #include "quiche/quic/core/quic_alarm_factory.h"
18 #include "quiche/quic/core/quic_clock.h"
19 #include "quiche/quic/core/quic_connection_id.h"
20 #include "quiche/quic/core/quic_constants.h"
21 #include "quiche/quic/core/quic_error_codes.h"
22 #include "quiche/quic/core/quic_framer.h"
23 #include "quiche/quic/core/quic_packets.h"
24 #include "quiche/quic/core/quic_time.h"
25 #include "quiche/quic/core/quic_types.h"
26 #include "quiche/quic/core/quic_versions.h"
27 #include "quiche/quic/platform/api/quic_bug_tracker.h"
28 #include "quiche/quic/platform/api/quic_flags.h"
29 #include "quiche/quic/platform/api/quic_socket_address.h"
30 #include "quiche/common/platform/api/quiche_logging.h"
31
32 namespace quic {
33
34 using BufferedPacket = QuicBufferedPacketStore::BufferedPacket;
35 using BufferedPacketList = QuicBufferedPacketStore::BufferedPacketList;
36 using EnqueuePacketResult = QuicBufferedPacketStore::EnqueuePacketResult;
37
38 // Max number of connections this store can keep track.
39 static const size_t kDefaultMaxConnectionsInStore = 100;
40 // Up to half of the capacity can be used for storing non-CHLO packets.
41 static const size_t kMaxConnectionsWithoutCHLO =
42 kDefaultMaxConnectionsInStore / 2;
43
44 namespace {
45
46 // This alarm removes expired entries in map each time this alarm fires.
47 class ConnectionExpireAlarm : public QuicAlarm::DelegateWithoutContext {
48 public:
ConnectionExpireAlarm(QuicBufferedPacketStore * store)49 explicit ConnectionExpireAlarm(QuicBufferedPacketStore* store)
50 : connection_store_(store) {}
51
OnAlarm()52 void OnAlarm() override { connection_store_->OnExpirationTimeout(); }
53
54 ConnectionExpireAlarm(const ConnectionExpireAlarm&) = delete;
55 ConnectionExpireAlarm& operator=(const ConnectionExpireAlarm&) = delete;
56
57 private:
58 QuicBufferedPacketStore* connection_store_;
59 };
60
61 } // namespace
62
BufferedPacket(std::unique_ptr<QuicReceivedPacket> packet,QuicSocketAddress self_address,QuicSocketAddress peer_address)63 BufferedPacket::BufferedPacket(std::unique_ptr<QuicReceivedPacket> packet,
64 QuicSocketAddress self_address,
65 QuicSocketAddress peer_address)
66 : packet(std::move(packet)),
67 self_address(self_address),
68 peer_address(peer_address) {}
69
70 BufferedPacket::BufferedPacket(BufferedPacket&& other) = default;
71
72 BufferedPacket& BufferedPacket::operator=(BufferedPacket&& other) = default;
73
~BufferedPacket()74 BufferedPacket::~BufferedPacket() {}
75
BufferedPacketList()76 BufferedPacketList::BufferedPacketList()
77 : creation_time(QuicTime::Zero()),
78 ietf_quic(false),
79 version(ParsedQuicVersion::Unsupported()) {}
80
81 BufferedPacketList::BufferedPacketList(BufferedPacketList&& other) = default;
82
83 BufferedPacketList& BufferedPacketList::operator=(BufferedPacketList&& other) =
84 default;
85
~BufferedPacketList()86 BufferedPacketList::~BufferedPacketList() {}
87
QuicBufferedPacketStore(VisitorInterface * visitor,const QuicClock * clock,QuicAlarmFactory * alarm_factory)88 QuicBufferedPacketStore::QuicBufferedPacketStore(
89 VisitorInterface* visitor, const QuicClock* clock,
90 QuicAlarmFactory* alarm_factory)
91 : connection_life_span_(
92 QuicTime::Delta::FromSeconds(kInitialIdleTimeoutSecs)),
93 visitor_(visitor),
94 clock_(clock),
95 expiration_alarm_(
96 alarm_factory->CreateAlarm(new ConnectionExpireAlarm(this))) {}
97
~QuicBufferedPacketStore()98 QuicBufferedPacketStore::~QuicBufferedPacketStore() {
99 if (expiration_alarm_ != nullptr) {
100 expiration_alarm_->PermanentCancel();
101 }
102 }
103
EnqueuePacket(QuicConnectionId connection_id,bool ietf_quic,const QuicReceivedPacket & packet,QuicSocketAddress self_address,QuicSocketAddress peer_address,const ParsedQuicVersion & version,std::optional<ParsedClientHello> parsed_chlo,ConnectionIdGeneratorInterface * connection_id_generator)104 EnqueuePacketResult QuicBufferedPacketStore::EnqueuePacket(
105 QuicConnectionId connection_id, bool ietf_quic,
106 const QuicReceivedPacket& packet, QuicSocketAddress self_address,
107 QuicSocketAddress peer_address, const ParsedQuicVersion& version,
108 std::optional<ParsedClientHello> parsed_chlo,
109 ConnectionIdGeneratorInterface* connection_id_generator) {
110 const bool is_chlo = parsed_chlo.has_value();
111 QUIC_BUG_IF(quic_bug_12410_1, !GetQuicFlag(quic_allow_chlo_buffering))
112 << "Shouldn't buffer packets if disabled via flag.";
113 QUIC_BUG_IF(quic_bug_12410_2,
114 is_chlo && connections_with_chlo_.contains(connection_id))
115 << "Shouldn't buffer duplicated CHLO on connection " << connection_id;
116 QUIC_BUG_IF(quic_bug_12410_4, is_chlo && !version.IsKnown())
117 << "Should have version for CHLO packet.";
118
119 const bool is_first_packet = !undecryptable_packets_.contains(connection_id);
120 if (is_first_packet) {
121 if (ShouldNotBufferPacket(is_chlo)) {
122 // Drop the packet if the upper limit of undecryptable packets has been
123 // reached or the whole capacity of the store has been reached.
124 return TOO_MANY_CONNECTIONS;
125 }
126 undecryptable_packets_.emplace(
127 std::make_pair(connection_id, BufferedPacketList()));
128 undecryptable_packets_.back().second.ietf_quic = ietf_quic;
129 undecryptable_packets_.back().second.version = version;
130 }
131 QUICHE_CHECK(undecryptable_packets_.contains(connection_id));
132 BufferedPacketList& queue =
133 undecryptable_packets_.find(connection_id)->second;
134
135 if (!is_chlo) {
136 // If current packet is not CHLO, it might not be buffered because store
137 // only buffers certain number of undecryptable packets per connection.
138 size_t num_non_chlo_packets = connections_with_chlo_.contains(connection_id)
139 ? (queue.buffered_packets.size() - 1)
140 : queue.buffered_packets.size();
141 if (num_non_chlo_packets >= kDefaultMaxUndecryptablePackets) {
142 // If there are kMaxBufferedPacketsPerConnection packets buffered up for
143 // this connection, drop the current packet.
144 return TOO_MANY_PACKETS;
145 }
146 }
147
148 if (queue.buffered_packets.empty()) {
149 // If this is the first packet arrived on a new connection, initialize the
150 // creation time.
151 queue.creation_time = clock_->ApproximateNow();
152 }
153
154 BufferedPacket new_entry(std::unique_ptr<QuicReceivedPacket>(packet.Clone()),
155 self_address, peer_address);
156 if (is_chlo) {
157 // Add CHLO to the beginning of buffered packets so that it can be delivered
158 // first later.
159 queue.buffered_packets.push_front(std::move(new_entry));
160 queue.parsed_chlo = std::move(parsed_chlo);
161 connections_with_chlo_[connection_id] = false; // Dummy value.
162 // Set the version of buffered packets of this connection on CHLO.
163 queue.version = version;
164 queue.connection_id_generator = connection_id_generator;
165 } else {
166 // Buffer non-CHLO packets in arrival order.
167 queue.buffered_packets.push_back(std::move(new_entry));
168
169 // Attempt to parse multi-packet TLS CHLOs.
170 if (is_first_packet) {
171 queue.tls_chlo_extractor.IngestPacket(version, packet);
172 // Since this is the first packet and it's not a CHLO, the
173 // TlsChloExtractor should not have the entire CHLO.
174 QUIC_BUG_IF(quic_bug_12410_5,
175 queue.tls_chlo_extractor.HasParsedFullChlo())
176 << "First packet in list should not contain full CHLO";
177 }
178 // TODO(b/154857081) Reorder CHLO packets ahead of other ones.
179 }
180
181 MaybeSetExpirationAlarm();
182 return SUCCESS;
183 }
184
HasBufferedPackets(QuicConnectionId connection_id) const185 bool QuicBufferedPacketStore::HasBufferedPackets(
186 QuicConnectionId connection_id) const {
187 return undecryptable_packets_.contains(connection_id);
188 }
189
HasChlosBuffered() const190 bool QuicBufferedPacketStore::HasChlosBuffered() const {
191 return !connections_with_chlo_.empty();
192 }
193
DeliverPackets(QuicConnectionId connection_id)194 BufferedPacketList QuicBufferedPacketStore::DeliverPackets(
195 QuicConnectionId connection_id) {
196 BufferedPacketList packets_to_deliver;
197 auto it = undecryptable_packets_.find(connection_id);
198 if (it != undecryptable_packets_.end()) {
199 packets_to_deliver = std::move(it->second);
200 undecryptable_packets_.erase(connection_id);
201 std::list<BufferedPacket> initial_packets;
202 std::list<BufferedPacket> other_packets;
203 for (auto& packet : packets_to_deliver.buffered_packets) {
204 QuicLongHeaderType long_packet_type = INVALID_PACKET_TYPE;
205 PacketHeaderFormat unused_format;
206 bool unused_version_flag;
207 bool unused_use_length_prefix;
208 QuicVersionLabel unused_version_label;
209 ParsedQuicVersion unused_parsed_version = UnsupportedQuicVersion();
210 QuicConnectionId unused_destination_connection_id;
211 QuicConnectionId unused_source_connection_id;
212 std::optional<absl::string_view> unused_retry_token;
213 std::string unused_detailed_error;
214
215 // We don't need to pass |generator| because we already got the correct
216 // connection ID length when we buffered the packet and indexed by
217 // connection ID.
218 QuicErrorCode error_code = QuicFramer::ParsePublicHeaderDispatcher(
219 *packet.packet, connection_id.length(), &unused_format,
220 &long_packet_type, &unused_version_flag, &unused_use_length_prefix,
221 &unused_version_label, &unused_parsed_version,
222 &unused_destination_connection_id, &unused_source_connection_id,
223 &unused_retry_token, &unused_detailed_error);
224
225 if (error_code == QUIC_NO_ERROR && long_packet_type == INITIAL) {
226 initial_packets.push_back(std::move(packet));
227 } else {
228 other_packets.push_back(std::move(packet));
229 }
230 }
231
232 initial_packets.splice(initial_packets.end(), other_packets);
233 packets_to_deliver.buffered_packets = std::move(initial_packets);
234 }
235 return packets_to_deliver;
236 }
237
DiscardPackets(QuicConnectionId connection_id)238 void QuicBufferedPacketStore::DiscardPackets(QuicConnectionId connection_id) {
239 undecryptable_packets_.erase(connection_id);
240 connections_with_chlo_.erase(connection_id);
241 }
242
DiscardAllPackets()243 void QuicBufferedPacketStore::DiscardAllPackets() {
244 undecryptable_packets_.clear();
245 connections_with_chlo_.clear();
246 expiration_alarm_->Cancel();
247 }
248
OnExpirationTimeout()249 void QuicBufferedPacketStore::OnExpirationTimeout() {
250 QuicTime expiration_time = clock_->ApproximateNow() - connection_life_span_;
251 while (!undecryptable_packets_.empty()) {
252 auto& entry = undecryptable_packets_.front();
253 if (entry.second.creation_time > expiration_time) {
254 break;
255 }
256 QuicConnectionId connection_id = entry.first;
257 visitor_->OnExpiredPackets(connection_id, std::move(entry.second));
258 undecryptable_packets_.pop_front();
259 connections_with_chlo_.erase(connection_id);
260 }
261 if (!undecryptable_packets_.empty()) {
262 MaybeSetExpirationAlarm();
263 }
264 }
265
MaybeSetExpirationAlarm()266 void QuicBufferedPacketStore::MaybeSetExpirationAlarm() {
267 if (!expiration_alarm_->IsSet()) {
268 expiration_alarm_->Set(clock_->ApproximateNow() + connection_life_span_);
269 }
270 }
271
ShouldNotBufferPacket(bool is_chlo)272 bool QuicBufferedPacketStore::ShouldNotBufferPacket(bool is_chlo) {
273 bool is_store_full =
274 undecryptable_packets_.size() >= kDefaultMaxConnectionsInStore;
275
276 if (is_chlo) {
277 return is_store_full;
278 }
279
280 size_t num_connections_without_chlo =
281 undecryptable_packets_.size() - connections_with_chlo_.size();
282 bool reach_non_chlo_limit =
283 num_connections_without_chlo >= kMaxConnectionsWithoutCHLO;
284
285 return is_store_full || reach_non_chlo_limit;
286 }
287
DeliverPacketsForNextConnection(QuicConnectionId * connection_id)288 BufferedPacketList QuicBufferedPacketStore::DeliverPacketsForNextConnection(
289 QuicConnectionId* connection_id) {
290 if (connections_with_chlo_.empty()) {
291 // Returns empty list if no CHLO has been buffered.
292 return BufferedPacketList();
293 }
294 *connection_id = connections_with_chlo_.front().first;
295 connections_with_chlo_.pop_front();
296
297 BufferedPacketList packets = DeliverPackets(*connection_id);
298 QUICHE_DCHECK(!packets.buffered_packets.empty() &&
299 packets.parsed_chlo.has_value())
300 << "Try to deliver connectons without CHLO. # packets:"
301 << packets.buffered_packets.size()
302 << ", has_parsed_chlo:" << packets.parsed_chlo.has_value();
303 return packets;
304 }
305
HasChloForConnection(QuicConnectionId connection_id)306 bool QuicBufferedPacketStore::HasChloForConnection(
307 QuicConnectionId connection_id) {
308 return connections_with_chlo_.contains(connection_id);
309 }
310
IngestPacketForTlsChloExtraction(const QuicConnectionId & connection_id,const ParsedQuicVersion & version,const QuicReceivedPacket & packet,std::vector<uint16_t> * out_supported_groups,std::vector<std::string> * out_alpns,std::string * out_sni,bool * out_resumption_attempted,bool * out_early_data_attempted,std::optional<uint8_t> * tls_alert)311 bool QuicBufferedPacketStore::IngestPacketForTlsChloExtraction(
312 const QuicConnectionId& connection_id, const ParsedQuicVersion& version,
313 const QuicReceivedPacket& packet,
314 std::vector<uint16_t>* out_supported_groups,
315 std::vector<std::string>* out_alpns, std::string* out_sni,
316 bool* out_resumption_attempted, bool* out_early_data_attempted,
317 std::optional<uint8_t>* tls_alert) {
318 QUICHE_DCHECK_NE(out_alpns, nullptr);
319 QUICHE_DCHECK_NE(out_sni, nullptr);
320 QUICHE_DCHECK_NE(tls_alert, nullptr);
321 QUICHE_DCHECK_EQ(version.handshake_protocol, PROTOCOL_TLS1_3);
322 auto it = undecryptable_packets_.find(connection_id);
323 if (it == undecryptable_packets_.end()) {
324 QUIC_BUG(quic_bug_10838_1)
325 << "Cannot ingest packet for unknown connection ID " << connection_id;
326 return false;
327 }
328 it->second.tls_chlo_extractor.IngestPacket(version, packet);
329 if (!it->second.tls_chlo_extractor.HasParsedFullChlo()) {
330 *tls_alert = it->second.tls_chlo_extractor.tls_alert();
331 return false;
332 }
333 const TlsChloExtractor& tls_chlo_extractor = it->second.tls_chlo_extractor;
334 *out_supported_groups = tls_chlo_extractor.supported_groups();
335 *out_alpns = tls_chlo_extractor.alpns();
336 *out_sni = tls_chlo_extractor.server_name();
337 *out_resumption_attempted = tls_chlo_extractor.resumption_attempted();
338 *out_early_data_attempted = tls_chlo_extractor.early_data_attempted();
339 return true;
340 }
341
342 } // namespace quic
343