Home | History | Annotate | Download | only in spdy 
      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_static_table.h"
     12 #include "net/spdy/hpack_string_util.h"
     13 
     14 namespace net {
     15 
     16 using base::StringPiece;
     17 
     18 bool HpackHeaderTable::EntryComparator::operator() (
     19     const HpackEntry* lhs, const HpackEntry* rhs) const {
     20   int result = lhs->name().compare(rhs->name());
     21   if (result != 0)
     22     return result < 0;
     23   result = lhs->value().compare(rhs->value());
     24   if (result != 0)
     25     return result < 0;
     26   const size_t lhs_index = lhs->IsLookup() ? 0 : 1 + lhs->InsertionIndex();
     27   const size_t rhs_index = rhs->IsLookup() ? 0 : 1 + rhs->InsertionIndex();
     28   DCHECK(lhs == rhs || lhs_index != rhs_index)
     29       << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
     30       << rhs->name() << ", " << rhs->value() << ")"
     31       << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
     32   return lhs_index < rhs_index;
     33 }
     34 
     35 HpackHeaderTable::HpackHeaderTable()
     36     : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
     37       static_index_(ObtainHpackStaticTable().GetStaticIndex()),
     38       settings_size_bound_(kDefaultHeaderTableSizeSetting),
     39       size_(0),
     40       max_size_(kDefaultHeaderTableSizeSetting),
     41       total_insertions_(static_entries_.size()) {}
     42 
     43 HpackHeaderTable::~HpackHeaderTable() {}
     44 
     45 const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
     46   if (index == 0) {
     47     return NULL;
     48   }
     49   index -= 1;
     50   if (index < static_entries_.size()) {
     51     return &static_entries_[index];
     52   }
     53   index -= static_entries_.size();
     54   if (index < dynamic_entries_.size()) {
     55     return &dynamic_entries_[index];
     56   }
     57   return NULL;
     58 }
     59 
     60 const HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
     61   HpackEntry query(name, "");
     62   {
     63     OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
     64     if (it != static_index_.end() && (*it)->name() == name) {
     65       return *it;
     66     }
     67   }
     68   {
     69     OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query);
     70     if (it != dynamic_index_.end() && (*it)->name() == name) {
     71       return *it;
     72     }
     73   }
     74   return NULL;
     75 }
     76 
     77 const HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
     78                                                       StringPiece value) {
     79   HpackEntry query(name, value);
     80   {
     81     OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query);
     82     if (it != static_index_.end() &&
     83         (*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() &&
     91         (*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,
    179                                          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
    209