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