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 102 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 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 139 HpackHeaderTable::~HpackHeaderTable() {} 140 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 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 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 175 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 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 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 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 211 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 223 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 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 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 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 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 288 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
