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