blob: 8adbf43aad37989fe42174c841537296c5438d3b [file] [log] [blame]
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
#include <algorithm>
#include "net/third_party/quiche/src/common/platform/api/quiche_string_piece.h"
#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h"
#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h"
#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
#include "net/third_party/quiche/src/spdy/platform/api/spdy_logging.h"
namespace spdy {
size_t HpackHeaderTable::EntryHasher::operator()(
const HpackEntry* entry) const {
return quiche::QuicheHashStringPair(entry->name(), entry->value());
}
bool HpackHeaderTable::EntriesEq::operator()(const HpackEntry* lhs,
const HpackEntry* rhs) const {
if (lhs == nullptr) {
return rhs == nullptr;
}
if (rhs == nullptr) {
return false;
}
return lhs->name() == rhs->name() && lhs->value() == rhs->value();
}
HpackHeaderTable::HpackHeaderTable()
: static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
static_index_(ObtainHpackStaticTable().GetStaticIndex()),
static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()),
settings_size_bound_(kDefaultHeaderTableSizeSetting),
size_(0),
max_size_(kDefaultHeaderTableSizeSetting),
total_insertions_(static_entries_.size()) {}
HpackHeaderTable::~HpackHeaderTable() = default;
const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
if (index == 0) {
return nullptr;
}
index -= 1;
if (index < static_entries_.size()) {
return &static_entries_[index];
}
index -= static_entries_.size();
if (index < dynamic_entries_.size()) {
const HpackEntry* result = &dynamic_entries_[index];
if (debug_visitor_ != nullptr) {
debug_visitor_->OnUseEntry(*result);
}
return result;
}
return nullptr;
}
const HpackEntry* HpackHeaderTable::GetByName(absl::string_view name) {
{
auto it = static_name_index_.find(name);
if (it != static_name_index_.end()) {
return it->second;
}
}
{
NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
if (it != dynamic_name_index_.end()) {
const HpackEntry* result = it->second;
if (debug_visitor_ != nullptr) {
debug_visitor_->OnUseEntry(*result);
}
return result;
}
}
return nullptr;
}
const HpackEntry* HpackHeaderTable::GetByNameAndValue(absl::string_view name,
absl::string_view value) {
HpackEntry query(name, value);
{
auto it = static_index_.find(&query);
if (it != static_index_.end()) {
return *it;
}
}
{
auto it = dynamic_index_.find(&query);
if (it != dynamic_index_.end()) {
const HpackEntry* result = *it;
if (debug_visitor_ != nullptr) {
debug_visitor_->OnUseEntry(*result);
}
return result;
}
}
return nullptr;
}
size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
if (entry->IsLookup()) {
return 0;
} else if (entry->IsStatic()) {
return 1 + entry->InsertionIndex();
} else {
return total_insertions_ - entry->InsertionIndex() + static_entries_.size();
}
}
void HpackHeaderTable::SetMaxSize(size_t max_size) {
CHECK_LE(max_size, settings_size_bound_);
max_size_ = max_size;
if (size_ > max_size_) {
Evict(EvictionCountToReclaim(size_ - max_size_));
CHECK_LE(size_, max_size_);
}
}
void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
settings_size_bound_ = settings_size;
SetMaxSize(settings_size_bound_);
}
void HpackHeaderTable::EvictionSet(absl::string_view name,
absl::string_view value,
EntryTable::iterator* begin_out,
EntryTable::iterator* end_out) {
size_t eviction_count = EvictionCountForEntry(name, value);
*begin_out = dynamic_entries_.end() - eviction_count;
*end_out = dynamic_entries_.end();
}
size_t HpackHeaderTable::EvictionCountForEntry(absl::string_view name,
absl::string_view value) const {
size_t available_size = max_size_ - size_;
size_t entry_size = HpackEntry::Size(name, value);
if (entry_size <= available_size) {
// No evictions are required.
return 0;
}
return EvictionCountToReclaim(entry_size - available_size);
}
size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
size_t count = 0;
for (auto it = dynamic_entries_.rbegin();
it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
reclaim_size -= std::min(reclaim_size, it->Size());
}
return count;
}
void HpackHeaderTable::Evict(size_t count) {
for (size_t i = 0; i != count; ++i) {
CHECK(!dynamic_entries_.empty());
HpackEntry* entry = &dynamic_entries_.back();
size_ -= entry->Size();
auto it = dynamic_index_.find(entry);
DCHECK(it != dynamic_index_.end());
// Only remove an entry from the index if its insertion index matches;
// otherwise, the index refers to another entry with the same name and
// value.
if ((*it)->InsertionIndex() == entry->InsertionIndex()) {
dynamic_index_.erase(it);
}
auto name_it = dynamic_name_index_.find(entry->name());
DCHECK(name_it != dynamic_name_index_.end());
// Only remove an entry from the literal index if its insertion index
/// matches; otherwise, the index refers to another entry with the same
// name.
if (name_it->second->InsertionIndex() == entry->InsertionIndex()) {
dynamic_name_index_.erase(name_it);
}
dynamic_entries_.pop_back();
}
}
const HpackEntry* HpackHeaderTable::TryAddEntry(absl::string_view name,
absl::string_view value) {
Evict(EvictionCountForEntry(name, value));
size_t entry_size = HpackEntry::Size(name, value);
if (entry_size > (max_size_ - size_)) {
// Entire table has been emptied, but there's still insufficient room.
DCHECK(dynamic_entries_.empty());
DCHECK_EQ(0u, size_);
return nullptr;
}
dynamic_entries_.push_front(HpackEntry(name, value,
false, // is_static
total_insertions_));
HpackEntry* new_entry = &dynamic_entries_.front();
auto index_result = dynamic_index_.insert(new_entry);
if (!index_result.second) {
// An entry with the same name and value already exists in the dynamic
// index. We should replace it with the newly added entry.
SPDY_DVLOG(1) << "Found existing entry: "
<< (*index_result.first)->GetDebugString()
<< " replacing with: " << new_entry->GetDebugString();
DCHECK_GT(new_entry->InsertionIndex(),
(*index_result.first)->InsertionIndex());
dynamic_index_.erase(index_result.first);
CHECK(dynamic_index_.insert(new_entry).second);
}
auto name_result =
dynamic_name_index_.insert(std::make_pair(new_entry->name(), new_entry));
if (!name_result.second) {
// An entry with the same name already exists in the dynamic index. We
// should replace it with the newly added entry.
SPDY_DVLOG(1) << "Found existing entry: "
<< name_result.first->second->GetDebugString()
<< " replacing with: " << new_entry->GetDebugString();
DCHECK_GT(new_entry->InsertionIndex(),
name_result.first->second->InsertionIndex());
dynamic_name_index_.erase(name_result.first);
auto insert_result = dynamic_name_index_.insert(
std::make_pair(new_entry->name(), new_entry));
CHECK(insert_result.second);
}
size_ += entry_size;
++total_insertions_;
if (debug_visitor_ != nullptr) {
// Call |debug_visitor_->OnNewEntry()| to get the current time.
HpackEntry& entry = dynamic_entries_.front();
entry.set_time_added(debug_visitor_->OnNewEntry(entry));
SPDY_DVLOG(2) << "HpackHeaderTable::OnNewEntry: name=" << entry.name()
<< ", value=" << entry.value()
<< ", insert_index=" << entry.InsertionIndex()
<< ", time_added=" << entry.time_added();
}
return &dynamic_entries_.front();
}
void HpackHeaderTable::DebugLogTableState() const {
SPDY_DVLOG(2) << "Dynamic table:";
for (auto it = dynamic_entries_.begin(); it != dynamic_entries_.end(); ++it) {
SPDY_DVLOG(2) << " " << it->GetDebugString();
}
SPDY_DVLOG(2) << "Full Static Index:";
for (const auto* entry : static_index_) {
SPDY_DVLOG(2) << " " << entry->GetDebugString();
}
SPDY_DVLOG(2) << "Full Static Name Index:";
for (const auto& it : static_name_index_) {
SPDY_DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString();
}
SPDY_DVLOG(2) << "Full Dynamic Index:";
for (const auto* entry : dynamic_index_) {
SPDY_DVLOG(2) << " " << entry->GetDebugString();
}
SPDY_DVLOG(2) << "Full Dynamic Name Index:";
for (const auto& it : dynamic_name_index_) {
SPDY_DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString();
}
}
size_t HpackHeaderTable::EstimateMemoryUsage() const {
return SpdyEstimateMemoryUsage(dynamic_entries_) +
SpdyEstimateMemoryUsage(dynamic_index_) +
SpdyEstimateMemoryUsage(dynamic_name_index_);
}
} // namespace spdy