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
14namespace net {
15
16using base::StringPiece;
17
18bool 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
35HpackHeaderTable::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
43HpackHeaderTable::~HpackHeaderTable() {}
44
45const 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
60const 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
77const 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
99size_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
109void 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
119void 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
126void 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
135size_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
147size_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
156void 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
167const 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
190void 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