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       settings_size_bound_(kDefaultHeaderTableSizeSetting),
 122       size_(0),
 123       max_size_(kDefaultHeaderTableSizeSetting),
 124       total_insertions_(0) {
 125   for (const StaticEntry* it = kStaticTable;
 126        it != kStaticTable + arraysize(kStaticTable); ++it) {
 127     static_entries_.push_back(
 128         HpackEntry(StringPiece(it->name, it->name_len),
 129                    StringPiece(it->value, it->value_len),
 130                    true,  // is_static
 131                    total_insertions_));
 132     CHECK(index_.insert(&static_entries_.back()).second);
 133
 134     ++total_insertions_;
 135   }
 136 }
 137
 138 HpackHeaderTable::~HpackHeaderTable() {}
 139
 140 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
 141   if (index == 0) {
 142     return NULL;
 143   }
 144   index -= 1;
 145   if (index < static_entries_.size()) {
 146     return &static_entries_[index];
 147   }
 148   index -= static_entries_.size();
 149   if (index < dynamic_entries_.size()) {
 150     return &dynamic_entries_[index];
 151   }
 152   return NULL;
 153 }
 154
 155 HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
 156   HpackEntry query(name, "");
 157   OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
 158   if (it != index_.end() && (*it)->name() == name) {
 159     return *it;
 160   }
 161   return NULL;
 162 }
 163
 164 HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
 165                                                 StringPiece value) {
 166   HpackEntry query(name, value);
 167   OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
 168   if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
 169     return *it;
 170   }
 171   return NULL;
 172 }
 173
 174 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
 175   if (entry->IsLookup()) {
 176     return 0;
 177   } else if (entry->IsStatic()) {
 178     return 1 + entry->InsertionIndex();
 179   } else {
 180     return total_insertions_ - entry->InsertionIndex() + static_entries_.size();
 181   }
 182 }
 183
 184 void HpackHeaderTable::SetMaxSize(size_t max_size) {
 185   CHECK_LE(max_size, settings_size_bound_);
 186
 187   max_size_ = max_size;
 188   if (size_ > max_size_) {
 189     Evict(EvictionCountToReclaim(size_ - max_size_));
 190     CHECK_LE(size_, max_size_);
 191   }
 192 }
 193
 194 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
 195   settings_size_bound_ = settings_size;
 196   if (settings_size_bound_ < max_size_) {
 197     SetMaxSize(settings_size_bound_);
 198   }
 199 }
 200
 201 void HpackHeaderTable::EvictionSet(StringPiece name,
 202                                    StringPiece value,
 203                                    EntryTable::iterator* begin_out,
 204                                    EntryTable::iterator* end_out) {
 205   size_t eviction_count = EvictionCountForEntry(name, value);
 206   *begin_out = dynamic_entries_.end() - eviction_count;
 207   *end_out = dynamic_entries_.end();
 208 }
 209
 210 size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name,
 211                                                StringPiece value) const {
 212   size_t available_size = max_size_ - size_;
 213   size_t entry_size = HpackEntry::Size(name, value);
 214
 215   if (entry_size <= available_size) {
 216     // No evictions are required.
 217     return 0;
 218   }
 219   return EvictionCountToReclaim(entry_size - available_size);
 220 }
 221
 222 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
 223   size_t count = 0;
 224   for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin();
 225        it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
 226     reclaim_size -= std::min(reclaim_size, it->Size());
 227   }
 228   return count;
 229 }
 230
 231 void HpackHeaderTable::Evict(size_t count) {
 232   for (size_t i = 0; i != count; ++i) {
 233     CHECK(!dynamic_entries_.empty());
 234     HpackEntry* entry = &dynamic_entries_.back();
 235
 236     size_ -= entry->Size();
 237     CHECK_EQ(1u, index_.erase(entry));
 238     dynamic_entries_.pop_back();
 239   }
 240 }
 241
 242 HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece value) {
 243   Evict(EvictionCountForEntry(name, value));
 244
 245   size_t entry_size = HpackEntry::Size(name, value);
 246   if (entry_size > (max_size_ - size_)) {
 247     // Entire table has been emptied, but there's still insufficient room.
 248     DCHECK(dynamic_entries_.empty());
 249     DCHECK_EQ(0u, size_);
 250     return NULL;
 251   }
 252   dynamic_entries_.push_front(HpackEntry(name,
 253                                          value,
 254                                          false,  // is_static
 255                                          total_insertions_));
 256   CHECK(index_.insert(&dynamic_entries_.front()).second);
 257
 258   size_ += entry_size;
 259   ++total_insertions_;
 260
 261   return &dynamic_entries_.front();
 262 }
 263
 264 void HpackHeaderTable::DebugLogTableState() const {
 265   DVLOG(2) << "Dynamic table:";
 266   for (EntryTable::const_iterator it = dynamic_entries_.begin();
 267       it != dynamic_entries_.end(); ++it) {
 268     DVLOG(2) << "  " << it->GetDebugString();
 269   }
 270   DVLOG(2) << "Full Index:";
 271   for (OrderedEntrySet::const_iterator it = index_.begin();
 272       it != index_.end(); ++it) {
 273     DVLOG(2) << "  " << (*it)->GetDebugString();
 274   }
 275 }
 276
 277 }  // namespace net