1 // Copyright 2018 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "tools/render/processed_trace.h"
16
17 #include "absl/algorithm/container.h"
18 #include "absl/strings/str_cat.h"
19 #include "absl/strings/str_join.h"
20 #include "tools/render/layout_constants.h"
21
22 namespace quic_trace {
23 namespace render {
24
25 namespace {
26
FormatBandwidth(size_t total_bytes,uint64_t time_delta_us)27 std::string FormatBandwidth(size_t total_bytes, uint64_t time_delta_us) {
28 double rate = 8e6 * total_bytes / time_delta_us;
29
30 const char* unit = "";
31 for (const char* current_unit : {"k", "M", "G"}) {
32 if (rate < 1e3) {
33 break;
34 }
35 rate /= 1e3;
36 unit = current_unit;
37 }
38
39 char buffer[16];
40 snprintf(buffer, sizeof(buffer), "%.2f %sbps", rate, unit);
41 return buffer;
42 }
43
FormatPercentage(size_t numerator,size_t denominator)44 std::string FormatPercentage(size_t numerator, size_t denominator) {
45 double percentage = 100. * numerator / denominator;
46 char buffer[8];
47 snprintf(buffer, sizeof(buffer), "%.2f%%", percentage);
48 return buffer;
49 }
50
FormatTime(uint64_t time_us)51 std::string FormatTime(uint64_t time_us) {
52 char buffer[16];
53 snprintf(buffer, sizeof(buffer), "%.3fs", time_us / 1e6);
54 return buffer;
55 }
56
FormatRtt(uint64_t rtt_us)57 std::string FormatRtt(uint64_t rtt_us) {
58 if (rtt_us < 10 * 1000) {
59 return absl::StrCat(rtt_us, "µs");
60 }
61 if (rtt_us < 1000 * 1000) {
62 return absl::StrCat(rtt_us / 1000, "ms");
63 }
64 return FormatTime(rtt_us);
65 }
66
67 } // namespace
68
AddPacket(TraceRenderer * renderer,const Event & packet,Interval interval,PacketType type)69 void ProcessedTrace::AddPacket(TraceRenderer* renderer,
70 const Event& packet,
71 Interval interval,
72 PacketType type) {
73 renderer->AddPacket(packet.time_us(), interval.offset, interval.size, type);
74 rendered_packets_.push_back(
75 RenderedPacket{Box{vec2(packet.time_us(), interval.offset),
76 vec2(kSentPacketDurationMs, interval.size)},
77 &packet});
78 }
79
GetPacketsAcked(const EncryptionLevel enc_level)80 absl::flat_hash_set<uint64_t>* ProcessedTrace::GetPacketsAcked(
81 const EncryptionLevel enc_level) {
82 switch (enc_level) {
83 case ENCRYPTION_INITIAL:
84 return &packets_acked_initial_;
85 case ENCRYPTION_HANDSHAKE:
86 return &packets_acked_handshake_;
87 case ENCRYPTION_0RTT:
88 case ENCRYPTION_1RTT:
89 return &packets_acked_1rtt_;
90 default:
91 LOG(FATAL) << "Unknown encryption level.";
92 }
93 }
94
GetPacketsLost(const EncryptionLevel enc_level)95 absl::flat_hash_set<uint64_t>* ProcessedTrace::GetPacketsLost(
96 const EncryptionLevel enc_level) {
97 switch (enc_level) {
98 case ENCRYPTION_INITIAL:
99 return &packets_lost_initial_;
100 case ENCRYPTION_HANDSHAKE:
101 return &packets_lost_handshake_;
102 case ENCRYPTION_0RTT:
103 case ENCRYPTION_1RTT:
104 return &packets_lost_1rtt_;
105 default:
106 LOG(FATAL) << "Unknown encryption level.";
107 }
108 }
109
ProcessedTrace(std::unique_ptr<Trace> trace,TraceRenderer * renderer)110 ProcessedTrace::ProcessedTrace(std::unique_ptr<Trace> trace,
111 TraceRenderer* renderer) {
112 renderer->PacketCountHint(trace->events_size());
113
114 quic_trace::NumberingWithoutRetransmissions numbering;
115 size_t largest_sent = 0;
116 uint64_t largest_time = 0;
117 for (const Event& event : trace->events()) {
118 if (!event.has_time_us() || event.time_us() < largest_time) {
119 LOG(FATAL)
120 << "All events in the trace have to be sorted in chronological order";
121 }
122 largest_time = event.time_us();
123
124 if (event.event_type() == PACKET_SENT) {
125 Interval mapped = numbering.AssignTraceNumbering(event);
126 AddPacket(renderer, event, mapped, PacketType::SENT);
127 largest_sent =
128 std::max<size_t>(mapped.offset + mapped.size, largest_sent);
129 }
130 if (event.event_type() == PACKET_RECEIVED) {
131 for (const Frame& frame : event.frames()) {
132 for (const AckBlock& range : frame.ack_info().acked_packets()) {
133 for (size_t i = range.first_packet(); i <= range.last_packet(); i++) {
134 if (!GetPacketsAcked(event.encryption_level())->insert(i).second) {
135 continue;
136 }
137 Interval mapped =
138 numbering.GetTraceNumbering(i, event.encryption_level());
139 AddPacket(renderer, event, mapped, PacketType::ACKED);
140 acks_.emplace(vec2(event.time_us(), mapped.offset), i);
141 // Don't count spurious retransmissions as losses.
142 GetPacketsLost(event.encryption_level())->erase(i);
143 }
144 }
145 }
146 }
147 if (event.event_type() == PACKET_LOST) {
148 Interval mapped = numbering.GetTraceNumbering(event.packet_number(),
149 event.encryption_level());
150 AddPacket(renderer, event, mapped, PacketType::LOST);
151 GetPacketsLost(event.encryption_level())->insert(event.packet_number());
152 }
153 if (event.event_type() == APPLICATION_LIMITED) {
154 // Normally, we would use the size of the packet as height, but
155 // app-limited events have no size, so we pick an arbitrary number (in
156 // bytes).
157 const size_t kAppLimitedHeigth = 800;
158 AddPacket(renderer, event, Interval{largest_sent, kAppLimitedHeigth},
159 PacketType::APP_LIMITED);
160 }
161 }
162
163 renderer->FinishPackets();
164 trace_ = std::move(trace);
165 }
166
SummaryTable(Table * table,float start_time,float end_time)167 bool ProcessedTrace::SummaryTable(Table* table,
168 float start_time,
169 float end_time) {
170 auto compare = [](Event a, Event b) { return a.time_us() < b.time_us(); };
171 Event key_event;
172
173 key_event.set_time_us(start_time);
174 auto start_it = absl::c_lower_bound(trace_->events(), key_event, compare);
175
176 key_event.set_time_us(end_time);
177 auto end_it = absl::c_upper_bound(trace_->events(), key_event, compare);
178
179 if (start_it > end_it) {
180 return false;
181 }
182
183 // TODO(vasilvv): add actually useful information.
184 size_t count_sent = 0;
185 size_t bytes_sent = 0;
186 size_t bytes_sent_acked = 0;
187 size_t bytes_sent_lost = 0;
188 for (auto it = start_it; it != end_it; it++) {
189 switch (it->event_type()) {
190 case PACKET_SENT:
191 count_sent++;
192 bytes_sent += it->packet_size();
193 if (GetPacketsAcked(it->encryption_level())
194 ->count(it->packet_number()) > 0) {
195 bytes_sent_acked += it->packet_size();
196 }
197 if (GetPacketsLost(it->encryption_level())->count(it->packet_number()) >
198 0) {
199 bytes_sent_lost += it->packet_size();
200 }
201 break;
202 default:
203 break;
204 };
205 }
206
207 table->AddHeader("Selection summary");
208 table->AddRow("#sent", absl::StrCat(count_sent));
209 table->AddRow("Send rate",
210 FormatBandwidth(bytes_sent, end_time - start_time));
211 table->AddRow("Goodput",
212 FormatBandwidth(bytes_sent_acked, end_time - start_time));
213 table->AddRow("Loss rate", FormatPercentage(bytes_sent_lost, bytes_sent));
214 return true;
215 }
216
FindPacketContainingPoint(vec2 point,vec2 margin)217 ProcessedTrace::PacketSearchResult ProcessedTrace::FindPacketContainingPoint(
218 vec2 point,
219 vec2 margin) {
220 RenderedPacket key{Box(), nullptr};
221
222 key.box.origin.x = point.x - kSentPacketDurationMs - margin.x;
223 auto start_it = absl::c_lower_bound(rendered_packets_, key);
224
225 key.box.origin.x = point.x + kSentPacketDurationMs + margin.x;
226 auto end_it = absl::c_upper_bound(rendered_packets_, key);
227
228 if (start_it > end_it) {
229 return PacketSearchResult();
230 }
231
232 auto closest_box = end_it;
233 float closest_distance;
234 for (auto it = start_it; it != end_it; it++) {
235 Box target_box{it->box.origin - margin, it->box.size + 2 * margin};
236 if (IsInside(point, target_box)) {
237 float distance = DistanceSquared(point, BoxCenter(target_box));
238 if (closest_box == end_it || distance < closest_distance) {
239 closest_box = it;
240 closest_distance = distance;
241 }
242 }
243 }
244 if (closest_box != end_it) {
245 PacketSearchResult result;
246 result.index = closest_box - rendered_packets_.cbegin();
247 result.as_rendered = &closest_box->box;
248 result.event = closest_box->packet;
249 return result;
250 }
251
252 return PacketSearchResult();
253 }
254
255 namespace {
EncryptionLevelToString(EncryptionLevel level)256 const char* EncryptionLevelToString(EncryptionLevel level) {
257 switch (level) {
258 case ENCRYPTION_INITIAL:
259 return "Initial";
260 case ENCRYPTION_HANDSHAKE:
261 return "Handshake";
262 case ENCRYPTION_0RTT:
263 return "0-RTT";
264 case ENCRYPTION_1RTT:
265 return "1-RTT";
266
267 case ENCRYPTION_UNKNOWN:
268 default:
269 return "???";
270 }
271 }
272
273 constexpr int kMaxAckBlocksShown = 3;
AckSummary(const AckInfo & ack)274 std::string AckSummary(const AckInfo& ack) {
275 if (ack.acked_packets_size() == 0) {
276 return "";
277 }
278
279 bool overflow = false;
280 int blocks_to_show = ack.acked_packets_size();
281 if (blocks_to_show > kMaxAckBlocksShown) {
282 blocks_to_show = kMaxAckBlocksShown;
283 overflow = true;
284 }
285
286 std::vector<std::string> ack_ranges;
287 for (int i = 0; i < blocks_to_show; i++) {
288 const AckBlock& block = ack.acked_packets(i);
289 if (block.first_packet() == block.last_packet()) {
290 ack_ranges.push_back(absl::StrCat(block.first_packet()));
291 } else {
292 ack_ranges.push_back(
293 absl::StrCat(block.first_packet(), ":", block.last_packet()));
294 }
295 }
296
297 std::string result = absl::StrJoin(ack_ranges, ", ");
298 if (overflow) {
299 absl::StrAppend(&result, "...");
300 }
301 return result;
302 }
303 } // namespace
304
FillTableForPacket(Table * table,const Box * as_rendered,const Event * packet)305 void ProcessedTrace::FillTableForPacket(Table* table,
306 const Box* as_rendered,
307 const Event* packet) {
308 switch (packet->event_type()) {
309 case PACKET_SENT:
310 table->AddHeader(absl::StrCat("Sent packet #", packet->packet_number()));
311 break;
312 case PACKET_RECEIVED: {
313 std::string packet_acked = "???";
314 auto it = acks_.find(as_rendered->origin);
315 if (it != acks_.end()) {
316 packet_acked = absl::StrCat(it->second);
317 }
318 table->AddHeader(absl::StrCat("Ack for packet #", packet_acked));
319 break;
320 }
321 case PACKET_LOST:
322 table->AddHeader(absl::StrCat("Lost packet #", packet->packet_number()));
323 break;
324 case APPLICATION_LIMITED:
325 table->AddHeader("Application limited");
326 break;
327 default:
328 return;
329 }
330
331 table->AddRow("Time", FormatTime(packet->time_us()));
332
333 if (packet->event_type() == PACKET_SENT ||
334 packet->event_type() == PACKET_LOST ||
335 packet->event_type() == PACKET_RECEIVED) {
336 table->AddRow("Encryption",
337 EncryptionLevelToString(packet->encryption_level()));
338 }
339
340 if (packet->event_type() == PACKET_SENT ||
341 packet->event_type() == PACKET_LOST) {
342 table->AddRow("Size", absl::StrCat(packet->packet_size(), " bytes"));
343 }
344
345 if (packet->event_type() == PACKET_SENT) {
346 table->AddHeader("Frame list");
347 for (const Frame& frame : packet->frames()) {
348 switch (frame.frame_type()) {
349 case CRYPTO:
350 table->AddRow(
351 "Crypto",
352 absl::StrCat(frame.crypto_frame_info().offset(), "-",
353 frame.crypto_frame_info().offset() +
354 frame.crypto_frame_info().length(),
355 " (", frame.crypto_frame_info().length(), ")"));
356 break;
357 case STREAM:
358 table->AddRow(
359 "Stream",
360 absl::StrCat("#", frame.stream_frame_info().stream_id(), ": ",
361 frame.stream_frame_info().offset(), "-",
362 frame.stream_frame_info().offset() +
363 frame.stream_frame_info().length(),
364 " (", frame.stream_frame_info().length(), ")"));
365 break;
366 case RESET_STREAM:
367 table->AddRow(
368 "Reset stream",
369 absl::StrCat("#", frame.reset_stream_info().stream_id()));
370 break;
371 case CONNECTION_CLOSE:
372 table->AddRow(
373 "Connection close",
374 absl::StrCat(absl::Hex(frame.close_info().error_code())));
375 break;
376 case PING:
377 table->AddRow("Ping", "");
378 break;
379 case BLOCKED:
380 table->AddRow("Blocked", "");
381 break;
382 case STREAM_BLOCKED:
383 table->AddRow("Stream blocked",
384 absl::StrCat(frame.flow_control_info().stream_id()));
385 break;
386 case ACK:
387 table->AddRow("Ack", AckSummary(frame.ack_info()));
388 break;
389 default:
390 table->AddRow("Unknown", "");
391 break;
392 }
393 }
394 }
395
396 if (packet->has_transport_state()) {
397 const TransportState& state = packet->transport_state();
398 table->AddHeader("Transport state");
399 if (state.has_last_rtt_us()) {
400 table->AddRow("RTT", FormatRtt(state.last_rtt_us()));
401 }
402 if (state.has_smoothed_rtt_us()) {
403 table->AddRow("SRTT", FormatRtt(state.smoothed_rtt_us()));
404 }
405 if (state.has_min_rtt_us()) {
406 table->AddRow("Min RTT", FormatRtt(state.min_rtt_us()));
407 }
408 if (state.has_in_flight_bytes()) {
409 table->AddRow("In flight",
410 absl::StrCat(state.in_flight_bytes(), " bytes"));
411 }
412 if (state.has_cwnd_bytes()) {
413 table->AddRow("CWND", absl::StrCat(state.cwnd_bytes(), " bytes"));
414 }
415 if (state.has_pacing_rate_bps()) {
416 table->AddRow("Pacing rate",
417 FormatBandwidth(state.pacing_rate_bps(), 8000 * 1000));
418 }
419 if (state.has_congestion_control_state()) {
420 // Truncate CC state strings longer than 80 characters.
421 const int kMaxLen = 80;
422 std::string ccstate = state.congestion_control_state();
423 if (ccstate.length() > kMaxLen) {
424 ccstate = ccstate.substr(0, kMaxLen) + "...";
425 }
426 table->AddRow("CC State", ccstate);
427 }
428 }
429 }
430
BoundContainedPackets(Box boundary)431 absl::optional<Box> ProcessedTrace::BoundContainedPackets(Box boundary) {
432 RenderedPacket key{Box(), nullptr};
433
434 key.box.origin.x = boundary.origin.x;
435 auto range_start = absl::c_lower_bound(rendered_packets_, key);
436
437 key.box.origin.x =
438 boundary.origin.x + boundary.size.x + kSentPacketDurationMs;
439 auto range_end = absl::c_upper_bound(rendered_packets_, key);
440
441 if (range_start == rendered_packets_.end() ||
442 range_end == rendered_packets_.end() || range_start > range_end) {
443 return absl::nullopt;
444 }
445
446 absl::optional<Box> result;
447 for (auto it = range_start; it <= range_end; it++) {
448 if (IsInside(it->box, boundary)) {
449 result = result.has_value() ? BoundingBox(*result, it->box) : it->box;
450 }
451 }
452 return result;
453 }
454
455 } // namespace render
456 } // namespace quic_trace
457