OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/spdy/hpack_header_table.h" | 5 #include "net/spdy/hpack_header_table.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "net/spdy/hpack_constants.h" | 10 #include "net/spdy/hpack_constants.h" |
(...skipping 14 matching lines...) Expand all Loading... |
25 const char* const value; | 25 const char* const value; |
26 const size_t value_len; | 26 const size_t value_len; |
27 }; | 27 }; |
28 | 28 |
29 // The "constructor" for a StaticEntry that computes the lengths at | 29 // The "constructor" for a StaticEntry that computes the lengths at |
30 // compile time. | 30 // compile time. |
31 #define STATIC_ENTRY(name, value) \ | 31 #define STATIC_ENTRY(name, value) \ |
32 { name, arraysize(name) - 1, value, arraysize(value) - 1 } | 32 { name, arraysize(name) - 1, value, arraysize(value) - 1 } |
33 | 33 |
34 const StaticEntry kStaticTable[] = { | 34 const StaticEntry kStaticTable[] = { |
35 STATIC_ENTRY(":authority" , ""), // 1 | 35 STATIC_ENTRY(":authority", ""), // 1 |
36 STATIC_ENTRY(":method" , "GET"), // 2 | 36 STATIC_ENTRY(":method", "GET"), // 2 |
37 STATIC_ENTRY(":method" , "POST"), // 3 | 37 STATIC_ENTRY(":method", "POST"), // 3 |
38 STATIC_ENTRY(":path" , "/"), // 4 | 38 STATIC_ENTRY(":path", "/"), // 4 |
39 STATIC_ENTRY(":path" , "/index.html"), // 5 | 39 STATIC_ENTRY(":path", "/index.html"), // 5 |
40 STATIC_ENTRY(":scheme" , "http"), // 6 | 40 STATIC_ENTRY(":scheme", "http"), // 6 |
41 STATIC_ENTRY(":scheme" , "https"), // 7 | 41 STATIC_ENTRY(":scheme", "https"), // 7 |
42 STATIC_ENTRY(":status" , "200"), // 8 | 42 STATIC_ENTRY(":status", "200"), // 8 |
43 STATIC_ENTRY(":status" , "500"), // 9 | 43 STATIC_ENTRY(":status", "500"), // 9 |
44 STATIC_ENTRY(":status" , "404"), // 10 | 44 STATIC_ENTRY(":status", "404"), // 10 |
45 STATIC_ENTRY(":status" , "403"), // 11 | 45 STATIC_ENTRY(":status", "403"), // 11 |
46 STATIC_ENTRY(":status" , "400"), // 12 | 46 STATIC_ENTRY(":status", "400"), // 12 |
47 STATIC_ENTRY(":status" , "401"), // 13 | 47 STATIC_ENTRY(":status", "401"), // 13 |
48 STATIC_ENTRY("accept-charset" , ""), // 14 | 48 STATIC_ENTRY("accept-charset", ""), // 14 |
49 STATIC_ENTRY("accept-encoding" , ""), // 15 | 49 STATIC_ENTRY("accept-encoding", ""), // 15 |
50 STATIC_ENTRY("accept-language" , ""), // 16 | 50 STATIC_ENTRY("accept-language", ""), // 16 |
51 STATIC_ENTRY("accept-ranges" , ""), // 17 | 51 STATIC_ENTRY("accept-ranges", ""), // 17 |
52 STATIC_ENTRY("accept" , ""), // 18 | 52 STATIC_ENTRY("accept", ""), // 18 |
53 STATIC_ENTRY("access-control-allow-origin" , ""), // 19 | 53 STATIC_ENTRY("access-control-allow-origin", ""), // 19 |
54 STATIC_ENTRY("age" , ""), // 20 | 54 STATIC_ENTRY("age", ""), // 20 |
55 STATIC_ENTRY("allow" , ""), // 21 | 55 STATIC_ENTRY("allow", ""), // 21 |
56 STATIC_ENTRY("authorization" , ""), // 22 | 56 STATIC_ENTRY("authorization", ""), // 22 |
57 STATIC_ENTRY("cache-control" , ""), // 23 | 57 STATIC_ENTRY("cache-control", ""), // 23 |
58 STATIC_ENTRY("content-disposition" , ""), // 24 | 58 STATIC_ENTRY("content-disposition", ""), // 24 |
59 STATIC_ENTRY("content-encoding" , ""), // 25 | 59 STATIC_ENTRY("content-encoding", ""), // 25 |
60 STATIC_ENTRY("content-language" , ""), // 26 | 60 STATIC_ENTRY("content-language", ""), // 26 |
61 STATIC_ENTRY("content-length" , ""), // 27 | 61 STATIC_ENTRY("content-length", ""), // 27 |
62 STATIC_ENTRY("content-location" , ""), // 28 | 62 STATIC_ENTRY("content-location", ""), // 28 |
63 STATIC_ENTRY("content-range" , ""), // 29 | 63 STATIC_ENTRY("content-range", ""), // 29 |
64 STATIC_ENTRY("content-type" , ""), // 30 | 64 STATIC_ENTRY("content-type", ""), // 30 |
65 STATIC_ENTRY("cookie" , ""), // 31 | 65 STATIC_ENTRY("cookie", ""), // 31 |
66 STATIC_ENTRY("date" , ""), // 32 | 66 STATIC_ENTRY("date", ""), // 32 |
67 STATIC_ENTRY("etag" , ""), // 33 | 67 STATIC_ENTRY("etag", ""), // 33 |
68 STATIC_ENTRY("expect" , ""), // 34 | 68 STATIC_ENTRY("expect", ""), // 34 |
69 STATIC_ENTRY("expires" , ""), // 35 | 69 STATIC_ENTRY("expires", ""), // 35 |
70 STATIC_ENTRY("from" , ""), // 36 | 70 STATIC_ENTRY("from", ""), // 36 |
71 STATIC_ENTRY("host" , ""), // 37 | 71 STATIC_ENTRY("host", ""), // 37 |
72 STATIC_ENTRY("if-match" , ""), // 38 | 72 STATIC_ENTRY("if-match", ""), // 38 |
73 STATIC_ENTRY("if-modified-since" , ""), // 39 | 73 STATIC_ENTRY("if-modified-since", ""), // 39 |
74 STATIC_ENTRY("if-none-match" , ""), // 40 | 74 STATIC_ENTRY("if-none-match", ""), // 40 |
75 STATIC_ENTRY("if-range" , ""), // 41 | 75 STATIC_ENTRY("if-range", ""), // 41 |
76 STATIC_ENTRY("if-unmodified-since" , ""), // 42 | 76 STATIC_ENTRY("if-unmodified-since", ""), // 42 |
77 STATIC_ENTRY("last-modified" , ""), // 43 | 77 STATIC_ENTRY("last-modified", ""), // 43 |
78 STATIC_ENTRY("link" , ""), // 44 | 78 STATIC_ENTRY("link", ""), // 44 |
79 STATIC_ENTRY("location" , ""), // 45 | 79 STATIC_ENTRY("location", ""), // 45 |
80 STATIC_ENTRY("max-forwards" , ""), // 46 | 80 STATIC_ENTRY("max-forwards", ""), // 46 |
81 STATIC_ENTRY("proxy-authenticate" , ""), // 47 | 81 STATIC_ENTRY("proxy-authenticate", ""), // 47 |
82 STATIC_ENTRY("proxy-authorization" , ""), // 48 | 82 STATIC_ENTRY("proxy-authorization", ""), // 48 |
83 STATIC_ENTRY("range" , ""), // 49 | 83 STATIC_ENTRY("range", ""), // 49 |
84 STATIC_ENTRY("referer" , ""), // 50 | 84 STATIC_ENTRY("referer", ""), // 50 |
85 STATIC_ENTRY("refresh" , ""), // 51 | 85 STATIC_ENTRY("refresh", ""), // 51 |
86 STATIC_ENTRY("retry-after" , ""), // 52 | 86 STATIC_ENTRY("retry-after", ""), // 52 |
87 STATIC_ENTRY("server" , ""), // 53 | 87 STATIC_ENTRY("server", ""), // 53 |
88 STATIC_ENTRY("set-cookie" , ""), // 54 | 88 STATIC_ENTRY("set-cookie", ""), // 54 |
89 STATIC_ENTRY("strict-transport-security" , ""), // 55 | 89 STATIC_ENTRY("strict-transport-security", ""), // 55 |
90 STATIC_ENTRY("transfer-encoding" , ""), // 56 | 90 STATIC_ENTRY("transfer-encoding", ""), // 56 |
91 STATIC_ENTRY("user-agent" , ""), // 57 | 91 STATIC_ENTRY("user-agent", ""), // 57 |
92 STATIC_ENTRY("vary" , ""), // 58 | 92 STATIC_ENTRY("vary", ""), // 58 |
93 STATIC_ENTRY("via" , ""), // 59 | 93 STATIC_ENTRY("via", ""), // 59 |
94 STATIC_ENTRY("www-authenticate" , ""), // 60 | 94 STATIC_ENTRY("www-authenticate", ""), // 60 |
95 }; | 95 }; |
96 | 96 |
97 #undef STATIC_ENTRY | 97 #undef STATIC_ENTRY |
98 | 98 |
99 } // namespace | 99 } // namespace |
100 | 100 |
101 HpackHeaderTable::HpackHeaderTable() | 101 HpackHeaderTable::HpackHeaderTable() |
102 : settings_size_bound_(kDefaultHeaderTableSizeSetting), | 102 : settings_size_bound_(kDefaultHeaderTableSizeSetting), |
103 size_(0), | 103 size_(0), |
104 max_size_(kDefaultHeaderTableSizeSetting), | 104 max_size_(kDefaultHeaderTableSizeSetting), |
105 total_insertions_(0), | 105 total_insertions_(0), |
106 dynamic_entries_count_(0) { | 106 dynamic_entries_count_(0) { |
107 for (const StaticEntry* it = kStaticTable; | 107 for (const StaticEntry* it = kStaticTable; |
108 it != kStaticTable + arraysize(kStaticTable); ++it) { | 108 it != kStaticTable + arraysize(kStaticTable); |
109 static_entries_.push_back( | 109 ++it) { |
110 HpackEntry(StringPiece(it->name, it->name_len), | 110 static_entries_.push_back(HpackEntry(StringPiece(it->name, it->name_len), |
111 StringPiece(it->value, it->value_len), | 111 StringPiece(it->value, it->value_len), |
112 true, // is_static | 112 true, // is_static |
113 total_insertions_, | 113 total_insertions_, |
114 &dynamic_entries_count_)); | 114 &dynamic_entries_count_)); |
115 CHECK(index_.insert(&static_entries_.back()).second); | 115 CHECK(index_.insert(&static_entries_.back()).second); |
116 | 116 |
117 ++total_insertions_; | 117 ++total_insertions_; |
118 } | 118 } |
119 } | 119 } |
120 | 120 |
121 HpackHeaderTable::~HpackHeaderTable() {} | 121 HpackHeaderTable::~HpackHeaderTable() { |
| 122 } |
122 | 123 |
123 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) { | 124 HpackEntry* HpackHeaderTable::GetByIndex(size_t index) { |
124 if (index == 0) { | 125 if (index == 0) { |
125 return NULL; | 126 return NULL; |
126 } | 127 } |
127 index -= 1; | 128 index -= 1; |
128 if (index < dynamic_entries_.size()) { | 129 if (index < dynamic_entries_.size()) { |
129 return &dynamic_entries_[index]; | 130 return &dynamic_entries_[index]; |
130 } | 131 } |
131 index -= dynamic_entries_.size(); | 132 index -= dynamic_entries_.size(); |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
188 if (entry_size <= available_size) { | 189 if (entry_size <= available_size) { |
189 // No evictions are required. | 190 // No evictions are required. |
190 return 0; | 191 return 0; |
191 } | 192 } |
192 return EvictionCountToReclaim(entry_size - available_size); | 193 return EvictionCountToReclaim(entry_size - available_size); |
193 } | 194 } |
194 | 195 |
195 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const { | 196 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const { |
196 size_t count = 0; | 197 size_t count = 0; |
197 for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin(); | 198 for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin(); |
198 it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) { | 199 it != dynamic_entries_.rend() && reclaim_size != 0; |
| 200 ++it, ++count) { |
199 reclaim_size -= std::min(reclaim_size, it->Size()); | 201 reclaim_size -= std::min(reclaim_size, it->Size()); |
200 } | 202 } |
201 return count; | 203 return count; |
202 } | 204 } |
203 | 205 |
204 void HpackHeaderTable::Evict(size_t count) { | 206 void HpackHeaderTable::Evict(size_t count) { |
205 for (size_t i = 0; i != count; ++i) { | 207 for (size_t i = 0; i != count; ++i) { |
206 CHECK(!dynamic_entries_.empty()); | 208 CHECK(!dynamic_entries_.empty()); |
207 HpackEntry* entry = &dynamic_entries_.back(); | 209 HpackEntry* entry = &dynamic_entries_.back(); |
208 | 210 |
(...skipping 27 matching lines...) Expand all Loading... |
236 size_ += entry_size; | 238 size_ += entry_size; |
237 ++dynamic_entries_count_; | 239 ++dynamic_entries_count_; |
238 ++total_insertions_; | 240 ++total_insertions_; |
239 | 241 |
240 DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size()); | 242 DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size()); |
241 return &dynamic_entries_.front(); | 243 return &dynamic_entries_.front(); |
242 } | 244 } |
243 | 245 |
244 void HpackHeaderTable::ClearReferenceSet() { | 246 void HpackHeaderTable::ClearReferenceSet() { |
245 for (HpackEntry::OrderedSet::iterator it = reference_set_.begin(); | 247 for (HpackEntry::OrderedSet::iterator it = reference_set_.begin(); |
246 it != reference_set_.end(); ++it) { | 248 it != reference_set_.end(); |
| 249 ++it) { |
247 (*it)->set_state(0); | 250 (*it)->set_state(0); |
248 } | 251 } |
249 reference_set_.clear(); | 252 reference_set_.clear(); |
250 } | 253 } |
251 | 254 |
252 bool HpackHeaderTable::Toggle(HpackEntry* entry) { | 255 bool HpackHeaderTable::Toggle(HpackEntry* entry) { |
253 CHECK(!entry->IsStatic()); | 256 CHECK(!entry->IsStatic()); |
254 CHECK_EQ(0u, entry->state()); | 257 CHECK_EQ(0u, entry->state()); |
255 | 258 |
256 std::pair<HpackEntry::OrderedSet::iterator, bool> insert_result = | 259 std::pair<HpackEntry::OrderedSet::iterator, bool> insert_result = |
257 reference_set_.insert(entry); | 260 reference_set_.insert(entry); |
258 if (insert_result.second) { | 261 if (insert_result.second) { |
259 return true; | 262 return true; |
260 } else { | 263 } else { |
261 reference_set_.erase(insert_result.first); | 264 reference_set_.erase(insert_result.first); |
262 return false; | 265 return false; |
263 } | 266 } |
264 } | 267 } |
265 | 268 |
266 void HpackHeaderTable::DebugLogTableState() const { | 269 void HpackHeaderTable::DebugLogTableState() const { |
267 DVLOG(2) << "Reference Set:"; | 270 DVLOG(2) << "Reference Set:"; |
268 for (HpackEntry::OrderedSet::const_iterator it = reference_set_.begin(); | 271 for (HpackEntry::OrderedSet::const_iterator it = reference_set_.begin(); |
269 it != reference_set_.end(); ++it) { | 272 it != reference_set_.end(); |
| 273 ++it) { |
270 DVLOG(2) << " " << (*it)->GetDebugString(); | 274 DVLOG(2) << " " << (*it)->GetDebugString(); |
271 } | 275 } |
272 DVLOG(2) << "Dynamic table:"; | 276 DVLOG(2) << "Dynamic table:"; |
273 for (EntryTable::const_iterator it = dynamic_entries_.begin(); | 277 for (EntryTable::const_iterator it = dynamic_entries_.begin(); |
274 it != dynamic_entries_.end(); ++it) { | 278 it != dynamic_entries_.end(); |
| 279 ++it) { |
275 DVLOG(2) << " " << it->GetDebugString(); | 280 DVLOG(2) << " " << it->GetDebugString(); |
276 } | 281 } |
277 DVLOG(2) << "Full Index:"; | 282 DVLOG(2) << "Full Index:"; |
278 for (HpackEntry::OrderedSet::const_iterator it = index_.begin(); | 283 for (HpackEntry::OrderedSet::const_iterator it = index_.begin(); |
279 it != index_.end(); ++it) { | 284 it != index_.end(); |
| 285 ++it) { |
280 DVLOG(2) << " " << (*it)->GetDebugString(); | 286 DVLOG(2) << " " << (*it)->GetDebugString(); |
281 } | 287 } |
282 } | 288 } |
283 | 289 |
284 } // namespace net | 290 } // namespace net |
OLD | NEW |