HPACK: Refactor and expand HpackHeaderTable indexing.

net/spdy/hpack_header_table.cc

Index: net/spdy/hpack_header_table.cc
diff --git a/net/spdy/hpack_header_table.cc b/net/spdy/hpack_header_table.cc
index 1320bfbac1262ce7b26760d205b89cf4165df626..a7da21bff44244b22057e96265e19b32633ac3e1 100644
--- a/net/spdy/hpack_header_table.cc
+++ b/net/spdy/hpack_header_table.cc
@@ -4,76 +4,280 @@
 
 #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"                     , "500"),          // 9
+  STATIC_ENTRY(":status"                     , "404"),          // 10
+  STATIC_ENTRY(":status"                     , "403"),          // 11
+  STATIC_ENTRY(":status"                     , "400"),          // 12
+  STATIC_ENTRY(":status"                     , "401"),          // 13
+  STATIC_ENTRY("accept-charset"              , ""),             // 14
+  STATIC_ENTRY("accept-encoding"             , ""),             // 15
+  STATIC_ENTRY("accept-language"             , ""),             // 16
+  STATIC_ENTRY("accept-ranges"               , ""),             // 17
+  STATIC_ENTRY("accept"                      , ""),             // 18
+  STATIC_ENTRY("access-control-allow-origin" , ""),             // 19
+  STATIC_ENTRY("age"                         , ""),             // 20
+  STATIC_ENTRY("allow"                       , ""),             // 21
+  STATIC_ENTRY("authorization"               , ""),             // 22
+  STATIC_ENTRY("cache-control"               , ""),             // 23
+  STATIC_ENTRY("content-disposition"         , ""),             // 24
+  STATIC_ENTRY("content-encoding"            , ""),             // 25
+  STATIC_ENTRY("content-language"            , ""),             // 26
+  STATIC_ENTRY("content-length"              , ""),             // 27
+  STATIC_ENTRY("content-location"            , ""),             // 28
+  STATIC_ENTRY("content-range"               , ""),             // 29
+  STATIC_ENTRY("content-type"                , ""),             // 30
+  STATIC_ENTRY("cookie"                      , ""),             // 31
+  STATIC_ENTRY("date"                        , ""),             // 32
+  STATIC_ENTRY("etag"                        , ""),             // 33
+  STATIC_ENTRY("expect"                      , ""),             // 34
+  STATIC_ENTRY("expires"                     , ""),             // 35
+  STATIC_ENTRY("from"                        , ""),             // 36
+  STATIC_ENTRY("host"                        , ""),             // 37
+  STATIC_ENTRY("if-match"                    , ""),             // 38
+  STATIC_ENTRY("if-modified-since"           , ""),             // 39
+  STATIC_ENTRY("if-none-match"               , ""),             // 40
+  STATIC_ENTRY("if-range"                    , ""),             // 41
+  STATIC_ENTRY("if-unmodified-since"         , ""),             // 42
+  STATIC_ENTRY("last-modified"               , ""),             // 43
+  STATIC_ENTRY("link"                        , ""),             // 44
+  STATIC_ENTRY("location"                    , ""),             // 45
+  STATIC_ENTRY("max-forwards"                , ""),             // 46
+  STATIC_ENTRY("proxy-authenticate"          , ""),             // 47
+  STATIC_ENTRY("proxy-authorization"         , ""),             // 48
+  STATIC_ENTRY("range"                       , ""),             // 49
+  STATIC_ENTRY("referer"                     , ""),             // 50
+  STATIC_ENTRY("refresh"                     , ""),             // 51
+  STATIC_ENTRY("retry-after"                 , ""),             // 52
+  STATIC_ENTRY("server"                      , ""),             // 53
+  STATIC_ENTRY("set-cookie"                  , ""),             // 54
+  STATIC_ENTRY("strict-transport-security"   , ""),             // 55
+  STATIC_ENTRY("transfer-encoding"           , ""),             // 56
+  STATIC_ENTRY("user-agent"                  , ""),             // 57
+  STATIC_ENTRY("vary"                        , ""),             // 58
+  STATIC_ENTRY("via"                         , ""),             // 59
+  STATIC_ENTRY("www-authenticate"            , ""),             // 60
+};
+
+#undef STATIC_ENTRY
+
+}  // namespace
+
 HpackHeaderTable::HpackHeaderTable()
-    : size_(0),
-      max_size_(kDefaultHeaderTableSizeSetting) {}
+    : settings_size_bound_(kDefaultHeaderTableSizeSetting),
+      size_(0),
+      max_size_(kDefaultHeaderTableSizeSetting),
+      total_insertions_(0),
+      dynamic_entries_count_(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_,
+                   &dynamic_entries_count_));
+    CHECK(index_.insert(&static_entries_.back()).second);
+
+    ++total_insertions_;
+  }
+}
 
 HpackHeaderTable::~HpackHeaderTable() {}
 
-uint32 HpackHeaderTable::GetEntryCount() const {
-  size_t size = entries_.size();
-  DCHECK_LE(size, kuint32max);
-  return static_cast<uint32>(size);
+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;
 }
 
-const HpackEntry& HpackHeaderTable::GetEntry(uint32 index) const {
-  CHECK_GE(index, 1u);
-  CHECK_LE(index, GetEntryCount());
-  return entries_[index-1];
+HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
+  HpackEntry query(name, "");
+  HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query);
+  if (it != index_.end() && (*it)->name() == name) {
+    return *it;
+  }
+  return NULL;
 }
 
-HpackEntry* HpackHeaderTable::GetMutableEntry(uint32 index) {
-  CHECK_GE(index, 1u);
-  CHECK_LE(index, GetEntryCount());
-  return &entries_[index-1];
+HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
+                                                StringPiece value) {
+  HpackEntry query(name, value);
+  HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query);
+  if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
+    return *it;
+  }
+  return NULL;
 }
 
-void HpackHeaderTable::SetMaxSize(uint32 max_size) {
+void HpackHeaderTable::SetMaxSize(size_t max_size) {
+  CHECK_LE(max_size, settings_size_bound_);
+
   max_size_ = max_size;
-  while (size_ > max_size_) {
-    CHECK(!entries_.empty());
-    size_ -= entries_.back().Size();
-    entries_.pop_back();
+  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::TryAddEntry(
-    const HpackEntry& entry,
-    uint32* index,
-    std::vector<uint32>* removed_referenced_indices) {
-  *index = 0;
-  removed_referenced_indices->clear();
-
-  // The algorithm used here is described in 3.3.3. We're assuming
-  // that the given entry is caching the name/value.
-  size_t target_size = 0;
-  size_t size_t_max_size = static_cast<size_t>(max_size_);
-  if (entry.Size() <= size_t_max_size) {
-    // The conditional implies the difference can fit in 32 bits.
-    target_size = size_t_max_size - entry.Size();
-  }
-  while (static_cast<size_t>(size_) > target_size) {
-    DCHECK(!entries_.empty());
-    if (entries_.back().IsReferenced()) {
-      removed_referenced_indices->push_back(entries_.size());
-    }
-    size_ -= entries_.back().Size();
-    entries_.pop_back();
-  }
-
-  if (entry.Size() <= size_t_max_size) {
-    // Implied by the exit condition of the while loop above and the
-    // condition of the if.
-    DCHECK_LE(static_cast<size_t>(size_) + entry.Size(), size_t_max_size);
-    size_ += entry.Size();
-    *index = 1;
-    entries_.push_front(entry);
+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();
+
+    --dynamic_entries_count_;
+    DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size());
+  }
+}
+
+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_,
+                                         &total_insertions_));
+  CHECK(index_.insert(&dynamic_entries_.front()).second);
+
+  size_ += entry_size;
+  ++dynamic_entries_count_;
+  ++total_insertions_;
+
+  DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size());
+  return &dynamic_entries_.front();
+}
+
+void HpackHeaderTable::ClearReferenceSet() {
+  for (HpackEntry::OrderedSet::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<HpackEntry::OrderedSet::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 (HpackEntry::OrderedSet::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 (HpackEntry::OrderedSet::const_iterator it = index_.begin();
+      it != index_.end(); ++it) {
+    DVLOG(2) << "  " << (*it)->GetDebugString();
   }
 }