| // 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 |