// 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/spdy/hpack_header_table.h"
#include <algorithm>
#include "base/logging.h"
#include "net/spdy/hpack_constants.h"
#include "net/spdy/hpack_string_util.h"
namespace net {
using base::StringPiece;
namespace {
// An entry in the static table. Must be a POD in order to avoid
// static initializers, i.e. no user-defined constructors or
// destructors.
struct StaticEntry {
const char* const name;
const size_t name_len;
const char* const value;
const size_t value_len;
};
// The "constructor" for a StaticEntry that computes the lengths at
// compile time.
#define STATIC_ENTRY(name, value) \
{ name, arraysize(name) - 1, value, arraysize(value) - 1 }
const StaticEntry kStaticTable[] = {
STATIC_ENTRY(":authority" , ""), // 1
STATIC_ENTRY(":method" , "GET"), // 2
STATIC_ENTRY(":method" , "POST"), // 3
STATIC_ENTRY(":path" , "/"), // 4
STATIC_ENTRY(":path" , "/index.html"), // 5
STATIC_ENTRY(":scheme" , "http"), // 6
STATIC_ENTRY(":scheme" , "https"), // 7
STATIC_ENTRY(":status" , "200"), // 8
STATIC_ENTRY(":status" , "204"), // 9
STATIC_ENTRY(":status" , "206"), // 10
STATIC_ENTRY(":status" , "304"), // 11
STATIC_ENTRY(":status" , "400"), // 12
STATIC_ENTRY(":status" , "404"), // 13
STATIC_ENTRY(":status" , "500"), // 14
STATIC_ENTRY("accept-charset" , ""), // 15
STATIC_ENTRY("accept-encoding" , ""), // 16
STATIC_ENTRY("accept-language" , ""), // 17
STATIC_ENTRY("accept-ranges" , ""), // 18
STATIC_ENTRY("accept" , ""), // 19
STATIC_ENTRY("access-control-allow-origin" , ""), // 20
STATIC_ENTRY("age" , ""), // 21
STATIC_ENTRY("allow" , ""), // 22
STATIC_ENTRY("authorization" , ""), // 23
STATIC_ENTRY("cache-control" , ""), // 24
STATIC_ENTRY("content-disposition" , ""), // 25
STATIC_ENTRY("content-encoding" , ""), // 26
STATIC_ENTRY("content-language" , ""), // 27
STATIC_ENTRY("content-length" , ""), // 28
STATIC_ENTRY("content-location" , ""), // 29
STATIC_ENTRY("content-range" , ""), // 30
STATIC_ENTRY("content-type" , ""), // 31
STATIC_ENTRY("cookie" , ""), // 32
STATIC_ENTRY("date" , ""), // 33
STATIC_ENTRY("etag" , ""), // 34
STATIC_ENTRY("expect" , ""), // 35
STATIC_ENTRY("expires" , ""), // 36
STATIC_ENTRY("from" , ""), // 37
STATIC_ENTRY("host" , ""), // 38
STATIC_ENTRY("if-match" , ""), // 39
STATIC_ENTRY("if-modified-since" , ""), // 40
STATIC_ENTRY("if-none-match" , ""), // 41
STATIC_ENTRY("if-range" , ""), // 42
STATIC_ENTRY("if-unmodified-since" , ""), // 43
STATIC_ENTRY("last-modified" , ""), // 44
STATIC_ENTRY("link" , ""), // 45
STATIC_ENTRY("location" , ""), // 46
STATIC_ENTRY("max-forwards" , ""), // 47
STATIC_ENTRY("proxy-authenticate" , ""), // 48
STATIC_ENTRY("proxy-authorization" , ""), // 49
STATIC_ENTRY("range" , ""), // 50
STATIC_ENTRY("referer" , ""), // 51
STATIC_ENTRY("refresh" , ""), // 52
STATIC_ENTRY("retry-after" , ""), // 53
STATIC_ENTRY("server" , ""), // 54
STATIC_ENTRY("set-cookie" , ""), // 55
STATIC_ENTRY("strict-transport-security" , ""), // 56
STATIC_ENTRY("transfer-encoding" , ""), // 57
STATIC_ENTRY("user-agent" , ""), // 58
STATIC_ENTRY("vary" , ""), // 59
STATIC_ENTRY("via" , ""), // 60
STATIC_ENTRY("www-authenticate" , ""), // 61
};
#undef STATIC_ENTRY
} // namespace
bool HpackHeaderTable::EntryComparator::operator() (
const HpackEntry* lhs, const HpackEntry* rhs) const {
int result = lhs->name().compare(rhs->name());
if (result != 0)
return result < 0;
result = lhs->value().compare(rhs->value());
if (result != 0)
return result < 0;
const size_t lhs_index = table_->IndexOf(lhs);
const size_t rhs_index = table_->IndexOf(rhs);
DCHECK(lhs == rhs || lhs_index != rhs_index)
<< "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
<< rhs->name() << ", " << rhs->value() << ")"
<< " lhs index: " << lhs_index << " rhs index: " << rhs_index;
return lhs_index < rhs_index;
}
HpackHeaderTable::HpackHeaderTable()
: index_(EntryComparator(this)),
reference_set_(EntryComparator(this)),
settings_size_bound_(kDefaultHeaderTableSizeSetting),
size_(0),
max_size_(kDefaultHeaderTableSizeSetting),
total_insertions_(0) {
for (const StaticEntry* it = kStaticTable;
it != kStaticTable + arraysize(kStaticTable); ++it) {
static_entries_.push_back(
HpackEntry(StringPiece(it->name, it->name_len),
StringPiece(it->value, it->value_len),
true, // is_static
total_insertions_));
CHECK(index_.insert(&static_entries_.back()).second);
++total_insertions_;
}
}
HpackHeaderTable::~HpackHeaderTable() {}
HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
if (index == 0) {
return NULL;
}
index -= 1;
if (index < dynamic_entries_.size()) {
return &dynamic_entries_[index];
}
index -= dynamic_entries_.size();
if (index < static_entries_.size()) {
return &static_entries_[index];
}
return NULL;
}
HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
HpackEntry query(name, "");
OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
if (it != index_.end() && (*it)->name() == name) {
return *it;
}
return NULL;
}
HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
StringPiece value) {
HpackEntry query(name, value);
OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
return *it;
}
return NULL;
}
size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
if (entry->IsLookup()) {
return 0;
} else if (entry->IsStatic()) {
return 1 + entry->InsertionIndex() + dynamic_entries_.size();
} else {
return total_insertions_ - entry->InsertionIndex();
}
}
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;
if (settings_size_bound_ < max_size_) {
SetMaxSize(settings_size_bound_);
}
}
void HpackHeaderTable::EvictionSet(StringPiece name,
StringPiece 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(StringPiece name,
StringPiece 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 (EntryTable::const_reverse_iterator 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();
CHECK_EQ(1u, index_.erase(entry));
reference_set_.erase(entry);
dynamic_entries_.pop_back();
}
}
HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece 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 NULL;
}
dynamic_entries_.push_front(HpackEntry(name,
value,
false, // is_static
total_insertions_));
CHECK(index_.insert(&dynamic_entries_.front()).second);
size_ += entry_size;
++total_insertions_;
return &dynamic_entries_.front();
}
void HpackHeaderTable::ClearReferenceSet() {
for (OrderedEntrySet::iterator it = reference_set_.begin();
it != reference_set_.end(); ++it) {
(*it)->set_state(0);
}
reference_set_.clear();
}
bool HpackHeaderTable::Toggle(HpackEntry* entry) {
CHECK(!entry->IsStatic());
CHECK_EQ(0u, entry->state());
std::pair<OrderedEntrySet::iterator, bool> insert_result =
reference_set_.insert(entry);
if (insert_result.second) {
return true;
} else {
reference_set_.erase(insert_result.first);
return false;
}
}
void HpackHeaderTable::DebugLogTableState() const {
DVLOG(2) << "Reference Set:";
for (OrderedEntrySet::const_iterator it = reference_set_.begin();
it != reference_set_.end(); ++it) {
DVLOG(2) << " " << (*it)->GetDebugString();
}
DVLOG(2) << "Dynamic table:";
for (EntryTable::const_iterator it = dynamic_entries_.begin();
it != dynamic_entries_.end(); ++it) {
DVLOG(2) << " " << it->GetDebugString();
}
DVLOG(2) << "Full Index:";
for (OrderedEntrySet::const_iterator it = index_.begin();
it != index_.end(); ++it) {
DVLOG(2) << " " << (*it)->GetDebugString();
}
}
} // namespace net