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_string_util.h"
12
13 namespace net {
14
15 using base::StringPiece;
16
17 namespace {
18
19 // An entry in the static table. Must be a POD in order to avoid
20 // static initializers, i.e. no user-defined constructors or
21 // destructors.
22 struct StaticEntry {
23 const char* const name;
24 const size_t name_len;
25 const char* const value;
26 const size_t value_len;
27 };
28
29 // The "constructor" for a StaticEntry that computes the lengths at
30 // compile time.
31 #define STATIC_ENTRY(name, value) \
32 { name, arraysize(name) - 1, value, arraysize(value) - 1 }
33
34 const StaticEntry kStaticTable[] = {
35 STATIC_ENTRY(":authority" , ""), // 1
36 STATIC_ENTRY(":method" , "GET"), // 2
37 STATIC_ENTRY(":method" , "POST"), // 3
38 STATIC_ENTRY(":path" , "/"), // 4
39 STATIC_ENTRY(":path" , "/index.html"), // 5
40 STATIC_ENTRY(":scheme" , "http"), // 6
41 STATIC_ENTRY(":scheme" , "https"), // 7
42 STATIC_ENTRY(":status" , "200"), // 8
43 STATIC_ENTRY(":status" , "204"), // 9
44 STATIC_ENTRY(":status" , "206"), // 10
45 STATIC_ENTRY(":status" , "304"), // 11
46 STATIC_ENTRY(":status" , "400"), // 12
47 STATIC_ENTRY(":status" , "404"), // 13
48 STATIC_ENTRY(":status" , "500"), // 14
49 STATIC_ENTRY("accept-charset" , ""), // 15
50 STATIC_ENTRY("accept-encoding" , ""), // 16
51 STATIC_ENTRY("accept-language" , ""), // 17
52 STATIC_ENTRY("accept-ranges" , ""), // 18
53 STATIC_ENTRY("accept" , ""), // 19
54 STATIC_ENTRY("access-control-allow-origin" , ""), // 20
55 STATIC_ENTRY("age" , ""), // 21
56 STATIC_ENTRY("allow" , ""), // 22
57 STATIC_ENTRY("authorization" , ""), // 23
58 STATIC_ENTRY("cache-control" , ""), // 24
59 STATIC_ENTRY("content-disposition" , ""), // 25
60 STATIC_ENTRY("content-encoding" , ""), // 26
61 STATIC_ENTRY("content-language" , ""), // 27
62 STATIC_ENTRY("content-length" , ""), // 28
63 STATIC_ENTRY("content-location" , ""), // 29
64 STATIC_ENTRY("content-range" , ""), // 30
65 STATIC_ENTRY("content-type" , ""), // 31
66 STATIC_ENTRY("cookie" , ""), // 32
67 STATIC_ENTRY("date" , ""), // 33
68 STATIC_ENTRY("etag" , ""), // 34
69 STATIC_ENTRY("expect" , ""), // 35
70 STATIC_ENTRY("expires" , ""), // 36
71 STATIC_ENTRY("from" , ""), // 37
72 STATIC_ENTRY("host" , ""), // 38
73 STATIC_ENTRY("if-match" , ""), // 39
74 STATIC_ENTRY("if-modified-since" , ""), // 40
75 STATIC_ENTRY("if-none-match" , ""), // 41
76 STATIC_ENTRY("if-range" , ""), // 42
77 STATIC_ENTRY("if-unmodified-since" , ""), // 43
78 STATIC_ENTRY("last-modified" , ""), // 44
79 STATIC_ENTRY("link" , ""), // 45
80 STATIC_ENTRY("location" , ""), // 46
81 STATIC_ENTRY("max-forwards" , ""), // 47
82 STATIC_ENTRY("proxy-authenticate" , ""), // 48
83 STATIC_ENTRY("proxy-authorization" , ""), // 49
84 STATIC_ENTRY("range" , ""), // 50
85 STATIC_ENTRY("referer" , ""), // 51
86 STATIC_ENTRY("refresh" , ""), // 52
87 STATIC_ENTRY("retry-after" , ""), // 53
88 STATIC_ENTRY("server" , ""), // 54
89 STATIC_ENTRY("set-cookie" , ""), // 55
90 STATIC_ENTRY("strict-transport-security" , ""), // 56
91 STATIC_ENTRY("transfer-encoding" , ""), // 57
92 STATIC_ENTRY("user-agent" , ""), // 58
93 STATIC_ENTRY("vary" , ""), // 59
94 STATIC_ENTRY("via" , ""), // 60
95 STATIC_ENTRY("www-authenticate" , ""), // 61
96 };
97
98 #undef STATIC_ENTRY
99
100 } // namespace
101
operator ()(const HpackEntry * lhs,const HpackEntry * rhs) const102 bool HpackHeaderTable::EntryComparator::operator() (
103 const HpackEntry* lhs, const HpackEntry* rhs) const {
104 int result = lhs->name().compare(rhs->name());
105 if (result != 0)
106 return result < 0;
107 result = lhs->value().compare(rhs->value());
108 if (result != 0)
109 return result < 0;
110 const size_t lhs_index = table_->IndexOf(lhs);
111 const size_t rhs_index = table_->IndexOf(rhs);
112 DCHECK(lhs == rhs || lhs_index != rhs_index)
113 << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: ("
114 << rhs->name() << ", " << rhs->value() << ")"
115 << " lhs index: " << lhs_index << " rhs index: " << rhs_index;
116 return lhs_index < rhs_index;
117 }
118
HpackHeaderTable()119 HpackHeaderTable::HpackHeaderTable()
120 : index_(EntryComparator(this)),
121 reference_set_(EntryComparator(this)),
122 settings_size_bound_(kDefaultHeaderTableSizeSetting),
123 size_(0),
124 max_size_(kDefaultHeaderTableSizeSetting),
125 total_insertions_(0) {
126 for (const StaticEntry* it = kStaticTable;
127 it != kStaticTable + arraysize(kStaticTable); ++it) {
128 static_entries_.push_back(
129 HpackEntry(StringPiece(it->name, it->name_len),
130 StringPiece(it->value, it->value_len),
131 true, // is_static
132 total_insertions_));
133 CHECK(index_.insert(&static_entries_.back()).second);
134
135 ++total_insertions_;
136 }
137 }
138
~HpackHeaderTable()139 HpackHeaderTable::~HpackHeaderTable() {}
140
GetByIndex(size_t index)141 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
142 if (index == 0) {
143 return NULL;
144 }
145 index -= 1;
146 if (index < dynamic_entries_.size()) {
147 return &dynamic_entries_[index];
148 }
149 index -= dynamic_entries_.size();
150 if (index < static_entries_.size()) {
151 return &static_entries_[index];
152 }
153 return NULL;
154 }
155
GetByName(StringPiece name)156 HpackEntry* HpackHeaderTable::GetByName(StringPiece name) {
157 HpackEntry query(name, "");
158 OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
159 if (it != index_.end() && (*it)->name() == name) {
160 return *it;
161 }
162 return NULL;
163 }
164
GetByNameAndValue(StringPiece name,StringPiece value)165 HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name,
166 StringPiece value) {
167 HpackEntry query(name, value);
168 OrderedEntrySet::const_iterator it = index_.lower_bound(&query);
169 if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) {
170 return *it;
171 }
172 return NULL;
173 }
174
IndexOf(const HpackEntry * entry) const175 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
176 if (entry->IsLookup()) {
177 return 0;
178 } else if (entry->IsStatic()) {
179 return 1 + entry->InsertionIndex() + dynamic_entries_.size();
180 } else {
181 return total_insertions_ - entry->InsertionIndex();
182 }
183 }
184
SetMaxSize(size_t max_size)185 void HpackHeaderTable::SetMaxSize(size_t max_size) {
186 CHECK_LE(max_size, settings_size_bound_);
187
188 max_size_ = max_size;
189 if (size_ > max_size_) {
190 Evict(EvictionCountToReclaim(size_ - max_size_));
191 CHECK_LE(size_, max_size_);
192 }
193 }
194
SetSettingsHeaderTableSize(size_t settings_size)195 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
196 settings_size_bound_ = settings_size;
197 if (settings_size_bound_ < max_size_) {
198 SetMaxSize(settings_size_bound_);
199 }
200 }
201
EvictionSet(StringPiece name,StringPiece value,EntryTable::iterator * begin_out,EntryTable::iterator * end_out)202 void HpackHeaderTable::EvictionSet(StringPiece name,
203 StringPiece value,
204 EntryTable::iterator* begin_out,
205 EntryTable::iterator* end_out) {
206 size_t eviction_count = EvictionCountForEntry(name, value);
207 *begin_out = dynamic_entries_.end() - eviction_count;
208 *end_out = dynamic_entries_.end();
209 }
210
EvictionCountForEntry(StringPiece name,StringPiece value) const211 size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name,
212 StringPiece value) const {
213 size_t available_size = max_size_ - size_;
214 size_t entry_size = HpackEntry::Size(name, value);
215
216 if (entry_size <= available_size) {
217 // No evictions are required.
218 return 0;
219 }
220 return EvictionCountToReclaim(entry_size - available_size);
221 }
222
EvictionCountToReclaim(size_t reclaim_size) const223 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
224 size_t count = 0;
225 for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin();
226 it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
227 reclaim_size -= std::min(reclaim_size, it->Size());
228 }
229 return count;
230 }
231
Evict(size_t count)232 void HpackHeaderTable::Evict(size_t count) {
233 for (size_t i = 0; i != count; ++i) {
234 CHECK(!dynamic_entries_.empty());
235 HpackEntry* entry = &dynamic_entries_.back();
236
237 size_ -= entry->Size();
238 CHECK_EQ(1u, index_.erase(entry));
239 reference_set_.erase(entry);
240 dynamic_entries_.pop_back();
241 }
242 }
243
TryAddEntry(StringPiece name,StringPiece value)244 HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece value) {
245 Evict(EvictionCountForEntry(name, value));
246
247 size_t entry_size = HpackEntry::Size(name, value);
248 if (entry_size > (max_size_ - size_)) {
249 // Entire table has been emptied, but there's still insufficient room.
250 DCHECK(dynamic_entries_.empty());
251 DCHECK_EQ(0u, size_);
252 return NULL;
253 }
254 dynamic_entries_.push_front(HpackEntry(name,
255 value,
256 false, // is_static
257 total_insertions_));
258 CHECK(index_.insert(&dynamic_entries_.front()).second);
259
260 size_ += entry_size;
261 ++total_insertions_;
262
263 return &dynamic_entries_.front();
264 }
265
ClearReferenceSet()266 void HpackHeaderTable::ClearReferenceSet() {
267 for (OrderedEntrySet::iterator it = reference_set_.begin();
268 it != reference_set_.end(); ++it) {
269 (*it)->set_state(0);
270 }
271 reference_set_.clear();
272 }
273
Toggle(HpackEntry * entry)274 bool HpackHeaderTable::Toggle(HpackEntry* entry) {
275 CHECK(!entry->IsStatic());
276 CHECK_EQ(0u, entry->state());
277
278 std::pair<OrderedEntrySet::iterator, bool> insert_result =
279 reference_set_.insert(entry);
280 if (insert_result.second) {
281 return true;
282 } else {
283 reference_set_.erase(insert_result.first);
284 return false;
285 }
286 }
287
DebugLogTableState() const288 void HpackHeaderTable::DebugLogTableState() const {
289 DVLOG(2) << "Reference Set:";
290 for (OrderedEntrySet::const_iterator it = reference_set_.begin();
291 it != reference_set_.end(); ++it) {
292 DVLOG(2) << " " << (*it)->GetDebugString();
293 }
294 DVLOG(2) << "Dynamic table:";
295 for (EntryTable::const_iterator it = dynamic_entries_.begin();
296 it != dynamic_entries_.end(); ++it) {
297 DVLOG(2) << " " << it->GetDebugString();
298 }
299 DVLOG(2) << "Full Index:";
300 for (OrderedEntrySet::const_iterator it = index_.begin();
301 it != index_.end(); ++it) {
302 DVLOG(2) << " " << (*it)->GetDebugString();
303 }
304 }
305
306 } // namespace net
307