OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2013 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/http2_encoding_context.h" |
| 6 |
| 7 #include "base/logging.h" |
| 8 |
| 9 namespace net { |
| 10 |
| 11 const uint8 kIndexOpcode = 0x1; |
| 12 const uint8 kIndexN = 7; |
| 13 |
| 14 const uint8 kLiteralNoIndexOpcode = 0x3; |
| 15 const uint8 kLiteralNoIndexN= 5; |
| 16 |
| 17 const uint8 kLiteralIncrementalOpcode = 0x2; |
| 18 const uint8 kLiteralIncrementalN = 5; |
| 19 |
| 20 const uint8 kLiteralSubstitutionOpcode = 0x0; |
| 21 const uint8 kLiteralSubstitutionN = 6; |
| 22 |
| 23 const uint32 kUntouched = kuint32max; |
| 24 |
| 25 namespace { |
| 26 |
| 27 const char* kPreDefinedRequestHeaderTable[][2] = { |
| 28 { ":scheme", "http" }, // 0 |
| 29 { ":scheme", "https" }, // 1 |
| 30 { ":host", "" }, // 2 |
| 31 { ":path", "/" }, // 3 |
| 32 { ":method", "GET" }, // 4 |
| 33 { "accept", "" }, // 5 |
| 34 { "accept-charset", "" }, // 6 |
| 35 { "accept-encoding", "" }, // 7 |
| 36 { "accept-language", "" }, // 8 |
| 37 { "cookie", "" }, // 9 |
| 38 { "if-modified-since", "" }, // 10 |
| 39 { "user-agent", "" }, // 11 |
| 40 { "referer", "" }, // 12 |
| 41 { "authorization", "" }, // 13 |
| 42 { "allow", "" }, // 14 |
| 43 { "cache-control", "" }, // 15 |
| 44 { "connection", "" }, // 16 |
| 45 { "content-length", "" }, // 17 |
| 46 { "content-type", "" }, // 18 |
| 47 { "date", "" }, // 19 |
| 48 { "expect", "" }, // 20 |
| 49 { "from", "" }, // 21 |
| 50 { "if-match", "" }, // 22 |
| 51 { "if-none-match", "" }, // 23 |
| 52 { "if-range", "" }, // 24 |
| 53 { "if-unmodified-since", "" }, // 25 |
| 54 { "max-forwards", "" }, // 26 |
| 55 { "proxy-authorization", "" }, // 27 |
| 56 { "range", "" }, // 28 |
| 57 { "via", "" } // 29 |
| 58 }; |
| 59 |
| 60 const char* kPreDefinedResponseHeaderTable[][2] = { |
| 61 { ":status", "200" }, // 0 |
| 62 { "age", "" }, // 1 |
| 63 { "cache-control", "" }, // 2 |
| 64 { "content-length", "" }, // 3 |
| 65 { "content-type", "" }, // 4 |
| 66 { "date", "" }, // 5 |
| 67 { "etag", "" }, // 6 |
| 68 { "expires", "" }, // 7 |
| 69 { "last-modified", "" }, // 8 |
| 70 { "server", "" }, // 9 |
| 71 { "set-cookie", "" }, // 10 |
| 72 { "vary", "" }, // 11 |
| 73 { "via", "" }, // 12 |
| 74 { "access-control-allow-origin", "" }, // 13 |
| 75 { "accept-ranges", "" }, // 14 |
| 76 { "allow", "" }, // 15 |
| 77 { "connection", "" }, // 16 |
| 78 { "content-disposition", "" }, // 17 |
| 79 { "content-encoding", "" }, // 18 |
| 80 { "content-language", "" }, // 19 |
| 81 { "content-location", "" }, // 20 |
| 82 { "content-range", "" }, // 21 |
| 83 { "link", "" }, // 22 |
| 84 { "location", "" }, // 23 |
| 85 { "proxy-authenticate", "" }, // 24 |
| 86 { "refresh", "" }, // 25 |
| 87 { "retry-after", "" }, // 26 |
| 88 { "strict-transport-security", "" }, // 27 |
| 89 { "transfer-encoding", "" }, // 28 |
| 90 { "www-authenticate", "" }, // 29 |
| 91 }; |
| 92 |
| 93 } // namespace |
| 94 |
| 95 bool IsValidHeaderName(const std::string& str) { |
| 96 size_t start = (str.empty() || str[0] != ':') ? 0 : 1; |
| 97 |
| 98 if (start == str.size()) |
| 99 return false; |
| 100 |
| 101 for (size_t i = start; i < str.size(); ++i) { |
| 102 switch (str[i]) { |
| 103 case '!': |
| 104 case '#': |
| 105 case '$': |
| 106 case '%': |
| 107 case '&': |
| 108 case '\'': |
| 109 |
| 110 case '*': |
| 111 case '+': |
| 112 case '-': |
| 113 case '.': |
| 114 case '^': |
| 115 case '_': |
| 116 |
| 117 case '`': |
| 118 case '|': |
| 119 case '~': |
| 120 break; |
| 121 |
| 122 default: |
| 123 if (str[i] >= '0' && str[i] <= '9') |
| 124 break; |
| 125 |
| 126 if (str[i] >= 'a' && str[i] <= 'z') |
| 127 break; |
| 128 |
| 129 return false; |
| 130 } |
| 131 } |
| 132 |
| 133 return true; |
| 134 } |
| 135 |
| 136 bool IsValidHeaderValue(const std::string& str) { |
| 137 return true; |
| 138 } |
| 139 |
| 140 bool StringsEqualConstantTime(const std::string& str1, |
| 141 const std::string& str2) { |
| 142 size_t size = str1.size(); |
| 143 if (str2.size() != size) |
| 144 return false; |
| 145 |
| 146 uint8 x = 0; |
| 147 for (size_t i = 0; i < size; ++i) { |
| 148 x |= str1[i] ^ str2[i]; |
| 149 } |
| 150 return x == 0; |
| 151 } |
| 152 |
| 153 HeaderTableEntry::HeaderTableEntry() |
| 154 : referenced(false), |
| 155 touch_count(kUntouched) {} |
| 156 |
| 157 HeaderTableEntry::HeaderTableEntry(const std::string& name, |
| 158 const std::string& value) |
| 159 : name(name), |
| 160 value(value), |
| 161 referenced(false), |
| 162 touch_count(kUntouched) {} |
| 163 |
| 164 bool HeaderTableEntry::Equals(const HeaderTableEntry& other) const { |
| 165 return |
| 166 StringsEqualConstantTime(name, other.name) && |
| 167 StringsEqualConstantTime(value, other.value) && |
| 168 (referenced == other.referenced) && |
| 169 (touch_count == other.touch_count); |
| 170 } |
| 171 |
| 172 size_t HeaderTableEntry::Size() const { |
| 173 return name.size() + value.size() + 32; |
| 174 } |
| 175 |
| 176 HeaderTable::HeaderTable() : size_(0), max_size_(4096) {} |
| 177 |
| 178 HeaderTable::~HeaderTable() {} |
| 179 |
| 180 size_t HeaderTable::GetEntryCount() const { |
| 181 return entries_.size(); |
| 182 } |
| 183 |
| 184 void HeaderTable::SetMaxSize(size_t max_size) { |
| 185 max_size_ = max_size; |
| 186 while (size_ > max_size_) { |
| 187 RemoveFirstEntry(); |
| 188 } |
| 189 } |
| 190 |
| 191 const HeaderTableEntry* HeaderTable::GetEntry(int32 index) const { |
| 192 DCHECK_GE(index, 0); |
| 193 DCHECK_LT(static_cast<size_t>(index), entries_.size()); |
| 194 return &entries_[index]; |
| 195 } |
| 196 |
| 197 HeaderTableEntry* HeaderTable::GetMutableEntry(int32 index) { |
| 198 DCHECK_GE(index, 0); |
| 199 DCHECK_LT(static_cast<size_t>(index), entries_.size()); |
| 200 return &entries_[index]; |
| 201 } |
| 202 |
| 203 void HeaderTable::TryAppendEntry( |
| 204 const HeaderTableEntry& entry, |
| 205 int32* index, |
| 206 std::vector<uint32>* removed_referenced_indices) { |
| 207 DCHECK(IsValidHeaderName(entry.name)); |
| 208 DCHECK(IsValidHeaderValue(entry.value)); |
| 209 |
| 210 *index = -1; |
| 211 removed_referenced_indices->clear(); |
| 212 |
| 213 size_t size_delta = entry.Size(); |
| 214 size_t num_to_shift = 0; |
| 215 size_t size_after_shift = size_; |
| 216 while ((num_to_shift < entries_.size()) && |
| 217 (size_after_shift + size_delta) > max_size_) { |
| 218 size_after_shift -= entries_[num_to_shift].Size(); |
| 219 ++num_to_shift; |
| 220 } |
| 221 |
| 222 for (size_t i = 0; i < num_to_shift; ++i) { |
| 223 if (entries_[i].referenced) { |
| 224 removed_referenced_indices->push_back(i); |
| 225 } |
| 226 } |
| 227 |
| 228 entries_.erase(entries_.begin(), entries_.begin() + num_to_shift); |
| 229 size_ = size_after_shift; |
| 230 if ((size_ + size_delta) <= max_size_) { |
| 231 size_ += size_delta; |
| 232 *index = entries_.size(); |
| 233 entries_.push_back(entry); |
| 234 } |
| 235 } |
| 236 |
| 237 void HeaderTable::TryReplaceEntry( |
| 238 uint32 substituted_index, |
| 239 const HeaderTableEntry& entry, |
| 240 int32* index, |
| 241 std::vector<uint32>* removed_referenced_indices) { |
| 242 DCHECK(IsValidHeaderName(entry.name)); |
| 243 DCHECK(IsValidHeaderValue(entry.value)); |
| 244 |
| 245 *index = substituted_index; |
| 246 removed_referenced_indices->clear(); |
| 247 |
| 248 size_t size_delta = entry.Size() - GetEntry(*index)->Size(); |
| 249 size_t num_to_shift = 0; |
| 250 size_t size_after_shift = size_; |
| 251 while ((num_to_shift < entries_.size()) && |
| 252 (size_after_shift + size_delta) > max_size_) { |
| 253 size_after_shift -= entries_[num_to_shift].Size(); |
| 254 ++num_to_shift; |
| 255 if (num_to_shift >= static_cast<size_t>(*index)) { |
| 256 size_delta = entry.Size(); |
| 257 } |
| 258 } |
| 259 |
| 260 for (size_t i = 0; i < num_to_shift; ++i) { |
| 261 if (entries_[i].referenced) { |
| 262 removed_referenced_indices->push_back(i); |
| 263 } |
| 264 } |
| 265 |
| 266 entries_.erase(entries_.begin(), entries_.begin() + num_to_shift); |
| 267 *index -= num_to_shift; |
| 268 size_ = size_after_shift; |
| 269 if ((size_ + size_delta) <= max_size_) { |
| 270 size_ += size_delta; |
| 271 if (*index >= 0) { |
| 272 entries_[*index] = entry; |
| 273 } else { |
| 274 *index = 0; |
| 275 entries_.push_front(entry); |
| 276 } |
| 277 } else { |
| 278 *index = -1; |
| 279 } |
| 280 } |
| 281 |
| 282 void HeaderTable::RemoveFirstEntry() { |
| 283 DCHECK(!entries_.empty()); |
| 284 size_ -= entries_.front().Size(); |
| 285 entries_.pop_front(); |
| 286 } |
| 287 |
| 288 EncodingContext::EncodingContext(Http2Direction direction) { |
| 289 const char* (*initial_header_table)[2] = NULL; |
| 290 size_t initial_header_table_size = 0; |
| 291 switch (direction) { |
| 292 case HTTP2_REQUEST: |
| 293 initial_header_table = kPreDefinedRequestHeaderTable; |
| 294 initial_header_table_size = arraysize(kPreDefinedRequestHeaderTable); |
| 295 case HTTP2_RESPONSE: |
| 296 initial_header_table = kPreDefinedResponseHeaderTable; |
| 297 initial_header_table_size = arraysize(kPreDefinedResponseHeaderTable); |
| 298 } |
| 299 DCHECK(initial_header_table); |
| 300 DCHECK_GT(initial_header_table_size, 0u); |
| 301 |
| 302 for (size_t i = 0; i < initial_header_table_size; ++i) { |
| 303 int32 index = 0; |
| 304 std::vector<uint32> removed_referenced_indices; |
| 305 header_table_.TryAppendEntry( |
| 306 HeaderTableEntry(initial_header_table[i][0], |
| 307 initial_header_table[i][1]), |
| 308 &index, |
| 309 &removed_referenced_indices); |
| 310 DCHECK_GE(index, 0); |
| 311 DCHECK(removed_referenced_indices.empty()); |
| 312 } |
| 313 } |
| 314 |
| 315 EncodingContext::~EncodingContext() {} |
| 316 |
| 317 size_t EncodingContext::GetEntryCount() const { |
| 318 return header_table_.GetEntryCount(); |
| 319 } |
| 320 |
| 321 bool EncodingContext::IsReferenced(uint32 index) const { |
| 322 return header_table_.GetEntry(index)->referenced; |
| 323 } |
| 324 |
| 325 bool EncodingContext::GetIndexedHeaderName(uint32 index, |
| 326 std::string* name) const { |
| 327 *name = header_table_.GetEntry(index)->name; |
| 328 return true; |
| 329 } |
| 330 |
| 331 bool EncodingContext::GetIndexedHeaderValue(uint32 index, |
| 332 std::string* value) const { |
| 333 *value = header_table_.GetEntry(index)->value; |
| 334 return true; |
| 335 } |
| 336 |
| 337 void EncodingContext::ProcessIndexedHeader(uint32 index) { |
| 338 HeaderTableEntry* entry = header_table_.GetMutableEntry(index); |
| 339 entry->referenced = !entry->referenced; |
| 340 } |
| 341 |
| 342 void EncodingContext::ProcessLiteralHeaderWithIncrementalIndexing( |
| 343 const std::string& name, |
| 344 const std::string& value, |
| 345 int32* index, |
| 346 std::vector<uint32>* removed_referenced_indices) { |
| 347 header_table_.TryAppendEntry(HeaderTableEntry(name, value), |
| 348 index, removed_referenced_indices); |
| 349 if (*index >= 0) { |
| 350 header_table_.GetMutableEntry(*index)->referenced = true; |
| 351 } |
| 352 } |
| 353 |
| 354 void EncodingContext::ProcessLiteralHeaderWithSubstitutionIndexing( |
| 355 const std::string& name, |
| 356 uint32 substituted_index, |
| 357 const std::string& value, |
| 358 int32* index, |
| 359 std::vector<uint32>* removed_referenced_indices) { |
| 360 header_table_.TryReplaceEntry(substituted_index, |
| 361 HeaderTableEntry(name, value), |
| 362 index, removed_referenced_indices); |
| 363 if (*index >= 0) { |
| 364 header_table_.GetMutableEntry(*index)->referenced = true; |
| 365 } |
| 366 } |
| 367 |
| 368 void EncodingContext::AddTouches(uint32 index, uint32 touch_count) { |
| 369 HeaderTableEntry* entry = header_table_.GetMutableEntry(index); |
| 370 if (entry->touch_count == kUntouched) |
| 371 entry->touch_count = 0; |
| 372 entry->touch_count += touch_count; |
| 373 } |
| 374 |
| 375 HeaderTableEntry* EncodingContext::GetMutableEntry(int32 index) { |
| 376 return header_table_.GetMutableEntry(index); |
| 377 } |
| 378 |
| 379 } // namespace net |
OLD | NEW |