diff options
Diffstat (limited to 'chromium/net/spdy/hpack_header_table.cc')
| -rw-r--r-- | chromium/net/spdy/hpack_header_table.cc | 306 |
1 files changed, 306 insertions, 0 deletions
diff --git a/chromium/net/spdy/hpack_header_table.cc b/chromium/net/spdy/hpack_header_table.cc new file mode 100644 index 00000000000..130d7a56374 --- /dev/null +++ b/chromium/net/spdy/hpack_header_table.cc @@ -0,0 +1,306 @@ +// 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 |