net/spdy/hpack/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/hpack_header_table.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10 #include "net/spdy/hpack/hpack_constants.h"
  11 #include "net/spdy/hpack/hpack_static_table.h"
  12 #include "net/spdy/hpack/hpack_string_util.h"
  13
  14 namespace net {
  15
  16 using base::StringPiece;
  17
  18 bool HpackHeaderTable::EntryComparator::operator()(
  19     const HpackEntry* lhs,
  20     const HpackEntry* rhs) const {
  21   int result = lhs->name().compare(rhs->name());
  22   if (result != 0)
  23     return result < 0;
  24   result = lhs->value().compare(rhs->value());
  25   if (result != 0)
  26     return result < 0;
  27   const size_t lhs_index = lhs->IsLookup() ? 0 : 1 + lhs->InsertionIndex();
  28   const size_t rhs_index = rhs->IsLookup() ? 0 : 1 + rhs->InsertionIndex();
  29   DCHECK(lhs == rhs || lhs_index != rhs_index)
  30       << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
  31       << rhs->name() << ", " << rhs->value() << ")"
  32       << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
  33   return lhs_index < rhs_index;
  34 }
  35
  36 HpackHeaderTable::HpackHeaderTable()
  37     : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
  38       static_index_(ObtainHpackStaticTable().GetStaticIndex()),
  39       settings_size_bound_(kDefaultHeaderTableSizeSetting),
  40       size_(0),
  41       max_size_(kDefaultHeaderTableSizeSetting),
  42       total_insertions_(static_entries_.size()) {}
  43
  44 HpackHeaderTable::~HpackHeaderTable() {}
  45
  46 const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
  47   if (index == 0) {
  48     return NULL;
  49   }
  50   index -= 1;
  51   if (index < static_entries_.size()) {
  52     return &static_entries_[index];
  53   }
  54   index -= static_entries_.size();
  55   if (index < dynamic_entries_.size()) {
  56     return &dynamic_entries_[index];
  57   }
  58   return NULL;
  59 }
  60
  61 const HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
  62   HpackEntry query(name, "");
  63   {
  64     OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
  65     if (it != static_index_.end() && (*it)->name() == name) {
  66       return *it;
  67     }
  68   }
  69   {
  70     OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query);
  71     if (it != dynamic_index_.end() && (*it)->name() == name) {
  72       return *it;
  73     }
  74   }
  75   return NULL;
  76 }
  77
  78 const HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
  79                                                       StringPiece value) {
  80   HpackEntry query(name, value);
  81   {
  82     OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
  83     if (it != static_index_.end() && (*it)->name() == name &&
  84         (*it)->value() == value) {
  85       return *it;
  86     }
  87   }
  88   {
  89     OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query);
  90     if (it != dynamic_index_.end() && (*it)->name() == name &&
  91         (*it)->value() == value) {
  92       return *it;
  93     }
  94   }
  95   return NULL;
  96 }
  97
  98 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
  99   if (entry->IsLookup()) {
 100     return 0;
 101   } else if (entry->IsStatic()) {
 102     return 1 + entry->InsertionIndex();
 103   } else {
 104     return total_insertions_ - entry->InsertionIndex() + static_entries_.size();
 105   }
 106 }
 107
 108 void HpackHeaderTable::SetMaxSize(size_t max_size) {
 109   CHECK_LE(max_size, settings_size_bound_);
 110
 111   max_size_ = max_size;
 112   if (size_ > max_size_) {
 113     Evict(EvictionCountToReclaim(size_ - max_size_));
 114     CHECK_LE(size_, max_size_);
 115   }
 116 }
 117
 118 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
 119   settings_size_bound_ = settings_size;
 120   if (settings_size_bound_ < max_size_) {
 121     SetMaxSize(settings_size_bound_);
 122   }
 123 }
 124
 125 void HpackHeaderTable::EvictionSet(StringPiece name,
 126                                    StringPiece value,
 127                                    EntryTable::iterator* begin_out,
 128                                    EntryTable::iterator* end_out) {
 129   size_t eviction_count = EvictionCountForEntry(name, value);
 130   *begin_out = dynamic_entries_.end() - eviction_count;
 131   *end_out = dynamic_entries_.end();
 132 }
 133
 134 size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name,
 135                                                StringPiece value) const {
 136   size_t available_size = max_size_ - size_;
 137   size_t entry_size = HpackEntry::Size(name, value);
 138
 139   if (entry_size <= available_size) {
 140     // No evictions are required.
 141     return 0;
 142   }
 143   return EvictionCountToReclaim(entry_size - available_size);
 144 }
 145
 146 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
 147   size_t count = 0;
 148   for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin();
 149        it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
 150     reclaim_size -= std::min(reclaim_size, it->Size());
 151   }
 152   return count;
 153 }
 154
 155 void HpackHeaderTable::Evict(size_t count) {
 156   for (size_t i = 0; i != count; ++i) {
 157     CHECK(!dynamic_entries_.empty());
 158     HpackEntry* entry = &dynamic_entries_.back();
 159
 160     size_ -= entry->Size();
 161     CHECK_EQ(1u, dynamic_index_.erase(entry));
 162     dynamic_entries_.pop_back();
 163   }
 164 }
 165
 166 const HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name,
 167                                                 StringPiece value) {
 168   Evict(EvictionCountForEntry(name, value));
 169
 170   size_t entry_size = HpackEntry::Size(name, value);
 171   if (entry_size > (max_size_ - size_)) {
 172     // Entire table has been emptied, but there's still insufficient room.
 173     DCHECK(dynamic_entries_.empty());
 174     DCHECK_EQ(0u, size_);
 175     return NULL;
 176   }
 177   dynamic_entries_.push_front(HpackEntry(name, value,
 178                                          false,  // is_static
 179                                          total_insertions_));
 180   CHECK(dynamic_index_.insert(&dynamic_entries_.front()).second);
 181
 182   size_ += entry_size;
 183   ++total_insertions_;
 184
 185   return &dynamic_entries_.front();
 186 }
 187
 188 void HpackHeaderTable::DebugLogTableState() const {
 189   DVLOG(2) << "Dynamic table:";
 190   for (EntryTable::const_iterator it = dynamic_entries_.begin();
 191        it != dynamic_entries_.end(); ++it) {
 192     DVLOG(2) << "  " << it->GetDebugString();
 193   }
 194   DVLOG(2) << "Full Static Index:";
 195   for (OrderedEntrySet::const_iterator it = static_index_.begin();
 196        it != static_index_.end(); ++it) {
 197     DVLOG(2) << "  " << (*it)->GetDebugString();
 198   }
 199   DVLOG(2) << "Full Dynamic Index:";
 200   for (OrderedEntrySet::const_iterator it = dynamic_index_.begin();
 201        it != dynamic_index_.end(); ++it) {
 202     DVLOG(2) << "  " << (*it)->GetDebugString();
 203   }
 204 }
 205
 206 }  // namespace net