blob: c96d05750cbdb8a9e306d0cec06592b722c20cf8 [file]
// Copyright 2018 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "tools/render/processed_trace.h"
#include "absl/algorithm/container.h"
#include "absl/strings/str_cat.h"
#include "tools/render/layout_constants.h"
namespace quic_trace {
namespace render {
namespace {
std::string FormatBandwidth(size_t total_bytes, uint64_t time_delta_us) {
double rate = 8e6 * total_bytes / time_delta_us;
const char* unit = "";
for (const char* current_unit : {"k", "M", "G"}) {
if (rate < 1e3) {
break;
}
rate /= 1e3;
unit = current_unit;
}
char buffer[16];
snprintf(buffer, sizeof(buffer), "%.2f %sbps", rate, unit);
return buffer;
}
std::string FormatPercentage(size_t numerator, size_t denominator) {
double percentage = 100. * numerator / denominator;
char buffer[8];
snprintf(buffer, sizeof(buffer), "%.2f%%", percentage);
return buffer;
}
std::string FormatTime(uint64_t time_us) {
char buffer[16];
snprintf(buffer, sizeof(buffer), "%.3fs", time_us / 1e6);
return buffer;
}
std::string FormatRtt(uint64_t rtt_us) {
if (rtt_us < 10 * 1000) {
return absl::StrCat(rtt_us, "µs");
}
if (rtt_us < 1000 * 1000) {
return absl::StrCat(rtt_us / 1000, "ms");
}
return FormatTime(rtt_us);
}
} // namespace
void ProcessedTrace::AddPacket(TraceRenderer* renderer,
const Event& packet,
Interval interval,
PacketType type) {
renderer->AddPacket(packet.time_us(), interval.offset, interval.size, type);
rendered_packets_.push_back(
RenderedPacket{Box{vec2(packet.time_us(), interval.offset),
vec2(kSentPacketDurationMs, interval.size)},
&packet});
}
ProcessedTrace::ProcessedTrace(std::unique_ptr<Trace> trace,
TraceRenderer* renderer) {
renderer->PacketCountHint(trace->events_size());
quic_trace::NumberingWithoutRetransmissions numbering;
size_t largest_sent = 0;
uint64_t largest_time = 0;
for (const Event& event : trace->events()) {
if (!event.has_time_us() || event.time_us() < largest_time) {
LOG(FATAL)
<< "All events in the trace have to be sorted in chronological order";
}
largest_time = event.time_us();
if (event.event_type() == PACKET_SENT) {
Interval mapped = numbering.AssignTraceNumbering(event);
AddPacket(renderer, event, mapped, PacketType::SENT);
largest_sent = std::max<size_t>(mapped.offset + mapped.size, largest_sent);
}
if (event.event_type() == PACKET_RECEIVED) {
for (const Frame& frame : event.frames()) {
for (const AckBlock& range : frame.ack_info().acked_packets()) {
for (size_t i = range.first_packet(); i <= range.last_packet(); i++) {
if (!packets_acked_.insert(i).second) {
continue;
}
Interval mapped = numbering.GetTraceNumbering(i);
AddPacket(renderer, event, mapped, PacketType::ACKED);
acks_.emplace(vec2(event.time_us(), mapped.offset), i);
// Don't count spurious retransmissions as losses.
packets_lost_.erase(i);
}
}
}
}
if (event.event_type() == PACKET_LOST) {
Interval mapped = numbering.GetTraceNumbering(event.packet_number());
AddPacket(renderer, event, mapped, PacketType::LOST);
packets_lost_.insert(event.packet_number());
}
if (event.event_type() == APPLICATION_LIMITED) {
// Normally, we would use the size of the packet as height, but
// app-limited events have no size, so we pick an arbitrary number (in
// bytes).
const size_t kAppLimitedHeigth = 800;
AddPacket(renderer, event, Interval{largest_sent, kAppLimitedHeigth},
PacketType::APP_LIMITED);
}
}
renderer->FinishPackets();
trace_ = std::move(trace);
}
bool ProcessedTrace::SummaryTable(Table* table,
float start_time,
float end_time) {
auto compare = [](Event a, Event b) { return a.time_us() < b.time_us(); };
Event key_event;
key_event.set_time_us(start_time);
auto start_it = absl::c_lower_bound(trace_->events(), key_event, compare);
key_event.set_time_us(end_time);
auto end_it = absl::c_upper_bound(trace_->events(), key_event, compare);
if (start_it > end_it) {
return false;
}
// TODO(vasilvv): add actually useful information.
size_t count_sent = 0;
size_t bytes_sent = 0;
size_t bytes_sent_acked = 0;
size_t bytes_sent_lost = 0;
for (auto it = start_it; it != end_it; it++) {
switch (it->event_type()) {
case PACKET_SENT:
count_sent++;
bytes_sent += it->packet_size();
if (packets_acked_.count(it->packet_number()) > 0) {
bytes_sent_acked += it->packet_size();
}
if (packets_lost_.count(it->packet_number()) > 0) {
bytes_sent_lost += it->packet_size();
}
break;
default:
break;
};
}
table->AddHeader("Selection summary");
table->AddRow("#sent", absl::StrCat(count_sent));
table->AddRow("Send rate",
FormatBandwidth(bytes_sent, end_time - start_time));
table->AddRow("Goodput",
FormatBandwidth(bytes_sent_acked, end_time - start_time));
table->AddRow("Loss rate", FormatPercentage(bytes_sent_lost, bytes_sent));
return true;
}
ProcessedTrace::PacketSearchResult ProcessedTrace::FindPacketContainingPoint(
vec2 point,
vec2 margin) {
RenderedPacket key{Box(), nullptr};
key.box.origin.x = point.x - kSentPacketDurationMs - margin.x;
auto start_it = absl::c_lower_bound(rendered_packets_, key);
key.box.origin.x = point.x + kSentPacketDurationMs + margin.x;
auto end_it = absl::c_upper_bound(rendered_packets_, key);
if (start_it > end_it) {
return PacketSearchResult();
}
auto closest_box = end_it;
float closest_distance;
for (auto it = start_it; it != end_it; it++) {
Box target_box{it->box.origin - margin, it->box.size + 2 * margin};
if (IsInside(point, target_box)) {
float distance = DistanceSquared(point, BoxCenter(target_box));
if (closest_box == end_it || distance < closest_distance) {
closest_box = it;
closest_distance = distance;
}
}
}
if (closest_box != end_it) {
PacketSearchResult result;
result.index = closest_box - rendered_packets_.cbegin();
result.as_rendered = &closest_box->box;
result.event = closest_box->packet;
return result;
}
return PacketSearchResult();
}
namespace {
const char* EncryptionLevelToString(EncryptionLevel level) {
switch (level) {
case ENCRYPTION_INITIAL:
return "Initial";
case ENCRYPTION_0RTT:
return "0-RTT";
case ENCRYPTION_1RTT:
return "1-RTT";
case ENCRYPTION_UNKNOWN:
default:
return "???";
}
}
} // namespace
void ProcessedTrace::FillTableForPacket(Table* table,
const Box* as_rendered,
const Event* packet) {
switch (packet->event_type()) {
case PACKET_SENT:
table->AddHeader(absl::StrCat("Sent packet #", packet->packet_number()));
break;
case PACKET_RECEIVED: {
std::string packet_acked = "???";
auto it = acks_.find(as_rendered->origin);
if (it != acks_.end()) {
packet_acked = absl::StrCat(it->second);
}
table->AddHeader(absl::StrCat("Ack for packet #", packet_acked));
break;
}
case PACKET_LOST:
table->AddHeader(absl::StrCat("Lost packet #", packet->packet_number()));
break;
case APPLICATION_LIMITED:
table->AddHeader("Application limited");
break;
default:
return;
}
table->AddRow("Time", FormatTime(packet->time_us()));
if (packet->event_type() == PACKET_SENT) {
table->AddRow("Size", absl::StrCat(packet->packet_size(), "bytes"));
table->AddRow("Encryption",
EncryptionLevelToString(packet->encryption_level()));
table->AddHeader("Frame list");
for (const Frame& frame : packet->frames()) {
switch (frame.frame_type()) {
case STREAM:
table->AddRow(
"Stream",
absl::StrCat("#", frame.stream_frame_info().stream_id()));
break;
case RESET_STREAM:
table->AddRow(
"Reset stream",
absl::StrCat("#", frame.reset_stream_info().stream_id()));
break;
case CONNECTION_CLOSE:
table->AddRow(
"Connection close",
absl::StrCat(absl::Hex(frame.close_info().error_code())));
break;
case PING:
table->AddRow("Ping", "");
break;
case BLOCKED:
table->AddRow("Blocked", "");
break;
case STREAM_BLOCKED:
table->AddRow("Stream blocked",
absl::StrCat(frame.flow_control_info().stream_id()));
break;
default:
table->AddRow("Unknown", "");
break;
}
}
}
if (packet->has_transport_state()) {
const TransportState& state = packet->transport_state();
table->AddHeader("Transport state");
if (state.has_last_rtt_us()) {
table->AddRow("RTT", FormatRtt(state.last_rtt_us()));
}
if (state.has_smoothed_rtt_us()) {
table->AddRow("SRTT", FormatRtt(state.smoothed_rtt_us()));
}
if (state.has_min_rtt_us()) {
table->AddRow("Min RTT", FormatRtt(state.min_rtt_us()));
}
if (state.has_in_flight_bytes()) {
table->AddRow("In flight",
absl::StrCat(state.in_flight_bytes(), " bytes"));
}
if (state.has_cwnd_bytes()) {
table->AddRow("CWND", absl::StrCat(state.cwnd_bytes(), " bytes"));
}
if (state.has_pacing_rate_bps()) {
table->AddRow("Pacing rate",
FormatBandwidth(state.pacing_rate_bps(), 8000 * 1000));
}
}
}
absl::optional<Box> ProcessedTrace::BoundContainedPackets(Box boundary) {
RenderedPacket key{Box(), nullptr};
key.box.origin.x = boundary.origin.x;
auto range_start = absl::c_lower_bound(rendered_packets_, key);
key.box.origin.x =
boundary.origin.x + boundary.size.x + kSentPacketDurationMs;
auto range_end = absl::c_upper_bound(rendered_packets_, key);
if (range_start == rendered_packets_.end() ||
range_end == rendered_packets_.end() || range_start > range_end) {
return absl::nullopt;
}
absl::optional<Box> result;
for (auto it = range_start; it <= range_end; it++) {
if (IsInside(it->box, boundary)) {
result = result.has_value() ? BoundingBox(*result, it->box) : it->box;
}
}
return result;
}
} // namespace render
} // namespace quic_trace