net/spdy/hpack_header_table.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/spdy/hpack_header_table.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10 #include "net/spdy/hpack_constants.h"
  11 #include "net/spdy/hpack_string_util.h"
  12
  13 namespace net {
  14
  15 using base::StringPiece;
  16
  17 namespace {
  18
  19 // An entry in the static table. Must be a POD in order to avoid
  20 // static initializers, i.e. no user-defined constructors or
  21 // destructors.
  22 struct StaticEntry {
  23   const char* const name;
  24   const size_t name_len;
  25   const char* const value;
  26   const size_t value_len;
  27 };
  28
  29 // The "constructor" for a StaticEntry that computes the lengths at
  30 // compile time.
  31 #define STATIC_ENTRY(name, value) \
  32   { name, arraysize(name) - 1, value, arraysize(value) - 1 }
  33
  34 const StaticEntry kStaticTable[] = {
  35   STATIC_ENTRY(":authority"                 , ""),               // 1
  36   STATIC_ENTRY(":method"                    , "GET"),            // 2
  37   STATIC_ENTRY(":method"                    , "POST"),           // 3
  38   STATIC_ENTRY(":path"                      , "/"),              // 4
  39   STATIC_ENTRY(":path"                      , "/index.html"),    // 5
  40   STATIC_ENTRY(":scheme"                    , "http"),           // 6
  41   STATIC_ENTRY(":scheme"                    , "https"),          // 7
  42   STATIC_ENTRY(":status"                    , "200"),            // 8
  43   STATIC_ENTRY(":status"                    , "204"),            // 9
  44   STATIC_ENTRY(":status"                    , "206"),            // 10
  45   STATIC_ENTRY(":status"                    , "304"),            // 11
  46   STATIC_ENTRY(":status"                    , "400"),            // 12
  47   STATIC_ENTRY(":status"                    , "404"),            // 13
  48   STATIC_ENTRY(":status"                    , "500"),            // 14
  49   STATIC_ENTRY("accept-charset"             , ""),               // 15
  50   STATIC_ENTRY("accept-encoding"            , "gzip, deflate"),  // 16
  51   STATIC_ENTRY("accept-language"            , ""),               // 17
  52   STATIC_ENTRY("accept-ranges"              , ""),               // 18
  53   STATIC_ENTRY("accept"                     , ""),               // 19
  54   STATIC_ENTRY("access-control-allow-origin", ""),               // 20
  55   STATIC_ENTRY("age"                        , ""),               // 21
  56   STATIC_ENTRY("allow"                      , ""),               // 22
  57   STATIC_ENTRY("authorization"              , ""),               // 23
  58   STATIC_ENTRY("cache-control"              , ""),               // 24
  59   STATIC_ENTRY("content-disposition"        , ""),               // 25
  60   STATIC_ENTRY("content-encoding"           , ""),               // 26
  61   STATIC_ENTRY("content-language"           , ""),               // 27
  62   STATIC_ENTRY("content-length"             , ""),               // 28
  63   STATIC_ENTRY("content-location"           , ""),               // 29
  64   STATIC_ENTRY("content-range"              , ""),               // 30
  65   STATIC_ENTRY("content-type"               , ""),               // 31
  66   STATIC_ENTRY("cookie"                     , ""),               // 32
  67   STATIC_ENTRY("date"                       , ""),               // 33
  68   STATIC_ENTRY("etag"                       , ""),               // 34
  69   STATIC_ENTRY("expect"                     , ""),               // 35
  70   STATIC_ENTRY("expires"                    , ""),               // 36
  71   STATIC_ENTRY("from"                       , ""),               // 37
  72   STATIC_ENTRY("host"                       , ""),               // 38
  73   STATIC_ENTRY("if-match"                   , ""),               // 39
  74   STATIC_ENTRY("if-modified-since"          , ""),               // 40
  75   STATIC_ENTRY("if-none-match"              , ""),               // 41
  76   STATIC_ENTRY("if-range"                   , ""),               // 42
  77   STATIC_ENTRY("if-unmodified-since"        , ""),               // 43
  78   STATIC_ENTRY("last-modified"              , ""),               // 44
  79   STATIC_ENTRY("link"                       , ""),               // 45
  80   STATIC_ENTRY("location"                   , ""),               // 46
  81   STATIC_ENTRY("max-forwards"               , ""),               // 47
  82   STATIC_ENTRY("proxy-authenticate"         , ""),               // 48
  83   STATIC_ENTRY("proxy-authorization"        , ""),               // 49
  84   STATIC_ENTRY("range"                      , ""),               // 50
  85   STATIC_ENTRY("referer"                    , ""),               // 51
  86   STATIC_ENTRY("refresh"                    , ""),               // 52
  87   STATIC_ENTRY("retry-after"                , ""),               // 53
  88   STATIC_ENTRY("server"                     , ""),               // 54
  89   STATIC_ENTRY("set-cookie"                 , ""),               // 55
  90   STATIC_ENTRY("strict-transport-security"  , ""),               // 56
  91   STATIC_ENTRY("transfer-encoding"          , ""),               // 57
  92   STATIC_ENTRY("user-agent"                 , ""),               // 58
  93   STATIC_ENTRY("vary"                       , ""),               // 59
  94   STATIC_ENTRY("via"                        , ""),               // 60
  95   STATIC_ENTRY("www-authenticate"           , ""),               // 61
  96 };
  97
  98 #undef STATIC_ENTRY
  99
 100 }  // namespace
 101
 102 bool HpackHeaderTable::EntryComparator::operator() (
 103     const HpackEntry* lhs, const HpackEntry* rhs) const {
 104   int result = lhs->name().compare(rhs->name());
 105   if (result != 0)
 106     return result < 0;
 107   result = lhs->value().compare(rhs->value());
 108   if (result != 0)
 109     return result < 0;
 110   const size_t lhs_index = table_->IndexOf(lhs);
 111   const size_t rhs_index = table_->IndexOf(rhs);
 112   DCHECK(lhs == rhs || lhs_index != rhs_index)
 113       << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
 114       << rhs->name() << ", " << rhs->value() << ")"
 115       << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
 116   return lhs_index < rhs_index;
 117 }
 118
 119 HpackHeaderTable::HpackHeaderTable()
 120     : index_(EntryComparator(this)),
 121       reference_set_(EntryComparator(this)),
 122       settings_size_bound_(kDefaultHeaderTableSizeSetting),
 123       size_(0),
 124       max_size_(kDefaultHeaderTableSizeSetting),
 125       total_insertions_(0) {
 126   for (const StaticEntry* it = kStaticTable;
 127        it != kStaticTable + arraysize(kStaticTable); ++it) {
 128     static_entries_.push_back(
 129         HpackEntry(StringPiece(it->name, it->name_len),
 130                    StringPiece(it->value, it->value_len),
 131                    true,  // is_static
 132                    total_insertions_));
 133     CHECK(index_.insert(&static_entries_.back()).second);
 134
 135     ++total_insertions_;
 136   }
 137 }
 138
 139 HpackHeaderTable::~HpackHeaderTable() {}
 140
 141 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
 142   if (index == 0) {
 143     return NULL;
 144   }
 145   index -= 1;
 146   if (index < dynamic_entries_.size()) {
 147     return &dynamic_entries_[index];
 148   }
 149   index -= dynamic_entries_.size();
 150   if (index < static_entries_.size()) {
 151     return &static_entries_[index];
 152   }
 153   return NULL;
 154 }
 155
 156 HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
 157   HpackEntry query(name, "");
 158   OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
 159   if (it != index_.end() && (*it)->name() == name) {
 160     return *it;
 161   }
 162   return NULL;
 163 }
 164
 165 HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
 166                                                 StringPiece value) {
 167   HpackEntry query(name, value);
 168   OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
 169   if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
 170     return *it;
 171   }
 172   return NULL;
 173 }
 174
 175 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
 176   if (entry->IsLookup()) {
 177     return 0;
 178   } else if (entry->IsStatic()) {
 179     return 1 + entry->InsertionIndex() + dynamic_entries_.size();
 180   } else {
 181     return total_insertions_ - entry->InsertionIndex();
 182   }
 183 }
 184
 185 void HpackHeaderTable::SetMaxSize(size_t max_size) {
 186   CHECK_LE(max_size, settings_size_bound_);
 187
 188   max_size_ = max_size;
 189   if (size_ > max_size_) {
 190     Evict(EvictionCountToReclaim(size_ - max_size_));
 191     CHECK_LE(size_, max_size_);
 192   }
 193 }
 194
 195 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
 196   settings_size_bound_ = settings_size;
 197   if (settings_size_bound_ < max_size_) {
 198     SetMaxSize(settings_size_bound_);
 199   }
 200 }
 201
 202 void HpackHeaderTable::EvictionSet(StringPiece name,
 203                                    StringPiece value,
 204                                    EntryTable::iterator* begin_out,
 205                                    EntryTable::iterator* end_out) {
 206   size_t eviction_count = EvictionCountForEntry(name, value);
 207   *begin_out = dynamic_entries_.end() - eviction_count;
 208   *end_out = dynamic_entries_.end();
 209 }
 210
 211 size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name,
 212                                                StringPiece value) const {
 213   size_t available_size = max_size_ - size_;
 214   size_t entry_size = HpackEntry::Size(name, value);
 215
 216   if (entry_size <= available_size) {
 217     // No evictions are required.
 218     return 0;
 219   }
 220   return EvictionCountToReclaim(entry_size - available_size);
 221 }
 222
 223 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
 224   size_t count = 0;
 225   for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin();
 226        it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
 227     reclaim_size -= std::min(reclaim_size, it->Size());
 228   }
 229   return count;
 230 }
 231
 232 void HpackHeaderTable::Evict(size_t count) {
 233   for (size_t i = 0; i != count; ++i) {
 234     CHECK(!dynamic_entries_.empty());
 235     HpackEntry* entry = &dynamic_entries_.back();
 236
 237     size_ -= entry->Size();
 238     CHECK_EQ(1u, index_.erase(entry));
 239     reference_set_.erase(entry);
 240     dynamic_entries_.pop_back();
 241   }
 242 }
 243
 244 HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece value) {
 245   Evict(EvictionCountForEntry(name, value));
 246
 247   size_t entry_size = HpackEntry::Size(name, value);
 248   if (entry_size > (max_size_ - size_)) {
 249     // Entire table has been emptied, but there's still insufficient room.
 250     DCHECK(dynamic_entries_.empty());
 251     DCHECK_EQ(0u, size_);
 252     return NULL;
 253   }
 254   dynamic_entries_.push_front(HpackEntry(name,
 255                                          value,
 256                                          false,  // is_static
 257                                          total_insertions_));
 258   CHECK(index_.insert(&dynamic_entries_.front()).second);
 259
 260   size_ += entry_size;
 261   ++total_insertions_;
 262
 263   return &dynamic_entries_.front();
 264 }
 265
 266 void HpackHeaderTable::ClearReferenceSet() {
 267   for (OrderedEntrySet::iterator it = reference_set_.begin();
 268        it != reference_set_.end(); ++it) {
 269     (*it)->set_state(0);
 270   }
 271   reference_set_.clear();
 272 }
 273
 274 bool HpackHeaderTable::Toggle(HpackEntry* entry) {
 275   CHECK(!entry->IsStatic());
 276   CHECK_EQ(0u, entry->state());
 277
 278   std::pair<OrderedEntrySet::iterator, bool> insert_result =
 279       reference_set_.insert(entry);
 280   if (insert_result.second) {
 281     return true;
 282   } else {
 283     reference_set_.erase(insert_result.first);
 284     return false;
 285   }
 286 }
 287
 288 void HpackHeaderTable::DebugLogTableState() const {
 289   DVLOG(2) << "Reference Set:";
 290   for (OrderedEntrySet::const_iterator it = reference_set_.begin();
 291       it != reference_set_.end(); ++it) {
 292     DVLOG(2) << "  " << (*it)->GetDebugString();
 293   }
 294   DVLOG(2) << "Dynamic table:";
 295   for (EntryTable::const_iterator it = dynamic_entries_.begin();
 296       it != dynamic_entries_.end(); ++it) {
 297     DVLOG(2) << "  " << it->GetDebugString();
 298   }
 299   DVLOG(2) << "Full Index:";
 300   for (OrderedEntrySet::const_iterator it = index_.begin();
 301       it != index_.end(); ++it) {
 302     DVLOG(2) << "  " << (*it)->GetDebugString();
 303   }
 304 }
 305
 306 }  // namespace net