| OLD | NEW |
|---|
| (Empty) |
| 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/hpack_header_table.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 | |
| 9 #include "base/logging.h" | |
| 10 #include "net/spdy/hpack/hpack_constants.h" | |
| 11 #include "net/spdy/hpack/hpack_static_table.h" | |
| 12 #include "net/spdy/platform/api/spdy_estimate_memory_usage.h" | |
| 13 #include "net/spdy/spdy_flags.h" | |
| 14 | |
| 15 namespace net { | |
| 16 | |
| 17 size_t HpackHeaderTable::EntryHasher::operator()( | |
| 18 const HpackEntry* entry) const { | |
| 19 return base::StringPieceHash()(entry->name()) ^ | |
| 20 base::StringPieceHash()(entry->value()); | |
| 21 } | |
| 22 | |
| 23 bool HpackHeaderTable::EntriesEq::operator()(const HpackEntry* lhs, | |
| 24 const HpackEntry* rhs) const { | |
| 25 if (lhs == nullptr) { | |
| 26 return rhs == nullptr; | |
| 27 } | |
| 28 if (rhs == nullptr) { | |
| 29 return false; | |
| 30 } | |
| 31 return lhs->name() == rhs->name() && lhs->value() == rhs->value(); | |
| 32 } | |
| 33 | |
| 34 HpackHeaderTable::HpackHeaderTable() | |
| 35 : static_entries_(ObtainHpackStaticTable().GetStaticEntries()), | |
| 36 static_index_(ObtainHpackStaticTable().GetStaticIndex()), | |
| 37 static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()), | |
| 38 settings_size_bound_(kDefaultHeaderTableSizeSetting), | |
| 39 size_(0), | |
| 40 max_size_(kDefaultHeaderTableSizeSetting), | |
| 41 total_insertions_(static_entries_.size()) {} | |
| 42 | |
| 43 HpackHeaderTable::~HpackHeaderTable() {} | |
| 44 | |
| 45 const 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 const HpackEntry* result = &dynamic_entries_[index]; | |
| 56 if (debug_visitor_ != nullptr) { | |
| 57 debug_visitor_->OnUseEntry(*result); | |
| 58 } | |
| 59 return result; | |
| 60 } | |
| 61 return NULL; | |
| 62 } | |
| 63 | |
| 64 const HpackEntry* HpackHeaderTable::GetByName(SpdyStringPiece name) { | |
| 65 { | |
| 66 NameToEntryMap::const_iterator it = static_name_index_.find(name); | |
| 67 if (it != static_name_index_.end()) { | |
| 68 return it->second; | |
| 69 } | |
| 70 } | |
| 71 { | |
| 72 NameToEntryMap::const_iterator it = dynamic_name_index_.find(name); | |
| 73 if (it != dynamic_name_index_.end()) { | |
| 74 const HpackEntry* result = it->second; | |
| 75 if (debug_visitor_ != nullptr) { | |
| 76 debug_visitor_->OnUseEntry(*result); | |
| 77 } | |
| 78 return result; | |
| 79 } | |
| 80 } | |
| 81 return NULL; | |
| 82 } | |
| 83 | |
| 84 const HpackEntry* HpackHeaderTable::GetByNameAndValue(SpdyStringPiece name, | |
| 85 SpdyStringPiece value) { | |
| 86 HpackEntry query(name, value); | |
| 87 { | |
| 88 UnorderedEntrySet::const_iterator it = static_index_.find(&query); | |
| 89 if (it != static_index_.end()) { | |
| 90 return *it; | |
| 91 } | |
| 92 } | |
| 93 { | |
| 94 UnorderedEntrySet::const_iterator it = dynamic_index_.find(&query); | |
| 95 if (it != dynamic_index_.end()) { | |
| 96 const HpackEntry* result = *it; | |
| 97 if (debug_visitor_ != nullptr) { | |
| 98 debug_visitor_->OnUseEntry(*result); | |
| 99 } | |
| 100 return result; | |
| 101 } | |
| 102 } | |
| 103 return NULL; | |
| 104 } | |
| 105 | |
| 106 size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const { | |
| 107 if (entry->IsLookup()) { | |
| 108 return 0; | |
| 109 } else if (entry->IsStatic()) { | |
| 110 return 1 + entry->InsertionIndex(); | |
| 111 } else { | |
| 112 return total_insertions_ - entry->InsertionIndex() + static_entries_.size(); | |
| 113 } | |
| 114 } | |
| 115 | |
| 116 void HpackHeaderTable::SetMaxSize(size_t max_size) { | |
| 117 CHECK_LE(max_size, settings_size_bound_); | |
| 118 | |
| 119 max_size_ = max_size; | |
| 120 if (size_ > max_size_) { | |
| 121 Evict(EvictionCountToReclaim(size_ - max_size_)); | |
| 122 CHECK_LE(size_, max_size_); | |
| 123 } | |
| 124 } | |
| 125 | |
| 126 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) { | |
| 127 settings_size_bound_ = settings_size; | |
| 128 SetMaxSize(settings_size_bound_); | |
| 129 } | |
| 130 | |
| 131 void HpackHeaderTable::EvictionSet(SpdyStringPiece name, | |
| 132 SpdyStringPiece value, | |
| 133 EntryTable::iterator* begin_out, | |
| 134 EntryTable::iterator* end_out) { | |
| 135 size_t eviction_count = EvictionCountForEntry(name, value); | |
| 136 *begin_out = dynamic_entries_.end() - eviction_count; | |
| 137 *end_out = dynamic_entries_.end(); | |
| 138 } | |
| 139 | |
| 140 size_t HpackHeaderTable::EvictionCountForEntry(SpdyStringPiece name, | |
| 141 SpdyStringPiece value) const { | |
| 142 size_t available_size = max_size_ - size_; | |
| 143 size_t entry_size = HpackEntry::Size(name, value); | |
| 144 | |
| 145 if (entry_size <= available_size) { | |
| 146 // No evictions are required. | |
| 147 return 0; | |
| 148 } | |
| 149 return EvictionCountToReclaim(entry_size - available_size); | |
| 150 } | |
| 151 | |
| 152 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const { | |
| 153 size_t count = 0; | |
| 154 for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin(); | |
| 155 it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) { | |
| 156 reclaim_size -= std::min(reclaim_size, it->Size()); | |
| 157 } | |
| 158 return count; | |
| 159 } | |
| 160 | |
| 161 void HpackHeaderTable::Evict(size_t count) { | |
| 162 for (size_t i = 0; i != count; ++i) { | |
| 163 CHECK(!dynamic_entries_.empty()); | |
| 164 HpackEntry* entry = &dynamic_entries_.back(); | |
| 165 | |
| 166 size_ -= entry->Size(); | |
| 167 UnorderedEntrySet::iterator it = dynamic_index_.find(entry); | |
| 168 DCHECK(it != dynamic_index_.end()); | |
| 169 // Only remove an entry from the index if its insertion index matches; | |
| 170 // otherwise, the index refers to another entry with the same name and | |
| 171 // value. | |
| 172 if ((*it)->InsertionIndex() == entry->InsertionIndex()) { | |
| 173 dynamic_index_.erase(it); | |
| 174 } | |
| 175 NameToEntryMap::iterator name_it = dynamic_name_index_.find(entry->name()); | |
| 176 DCHECK(name_it != dynamic_name_index_.end()); | |
| 177 // Only remove an entry from the literal index if its insertion index | |
| 178 /// matches; otherwise, the index refers to another entry with the same | |
| 179 // name. | |
| 180 if (name_it->second->InsertionIndex() == entry->InsertionIndex()) { | |
| 181 dynamic_name_index_.erase(name_it); | |
| 182 } | |
| 183 dynamic_entries_.pop_back(); | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 const HpackEntry* HpackHeaderTable::TryAddEntry(SpdyStringPiece name, | |
| 188 SpdyStringPiece value) { | |
| 189 Evict(EvictionCountForEntry(name, value)); | |
| 190 | |
| 191 size_t entry_size = HpackEntry::Size(name, value); | |
| 192 if (entry_size > (max_size_ - size_)) { | |
| 193 // Entire table has been emptied, but there's still insufficient room. | |
| 194 DCHECK(dynamic_entries_.empty()); | |
| 195 DCHECK_EQ(0u, size_); | |
| 196 return NULL; | |
| 197 } | |
| 198 dynamic_entries_.push_front(HpackEntry(name, value, | |
| 199 false, // is_static | |
| 200 total_insertions_)); | |
| 201 HpackEntry* new_entry = &dynamic_entries_.front(); | |
| 202 auto index_result = dynamic_index_.insert(new_entry); | |
| 203 if (!index_result.second) { | |
| 204 // An entry with the same name and value already exists in the dynamic | |
| 205 // index. We should replace it with the newly added entry. | |
| 206 DVLOG(1) << "Found existing entry: " | |
| 207 << (*index_result.first)->GetDebugString() | |
| 208 << " replacing with: " << new_entry->GetDebugString(); | |
| 209 DCHECK_GT(new_entry->InsertionIndex(), | |
| 210 (*index_result.first)->InsertionIndex()); | |
| 211 dynamic_index_.erase(index_result.first); | |
| 212 CHECK(dynamic_index_.insert(new_entry).second); | |
| 213 } | |
| 214 | |
| 215 auto name_result = | |
| 216 dynamic_name_index_.insert(std::make_pair(new_entry->name(), new_entry)); | |
| 217 if (!name_result.second) { | |
| 218 // An entry with the same name already exists in the dynamic index. We | |
| 219 // should replace it with the newly added entry. | |
| 220 DVLOG(1) << "Found existing entry: " | |
| 221 << name_result.first->second->GetDebugString() | |
| 222 << " replacing with: " << new_entry->GetDebugString(); | |
| 223 DCHECK_GT(new_entry->InsertionIndex(), | |
| 224 name_result.first->second->InsertionIndex()); | |
| 225 dynamic_name_index_.erase(name_result.first); | |
| 226 auto insert_result = dynamic_name_index_.insert( | |
| 227 std::make_pair(new_entry->name(), new_entry)); | |
| 228 CHECK(insert_result.second); | |
| 229 } | |
| 230 | |
| 231 size_ += entry_size; | |
| 232 ++total_insertions_; | |
| 233 if (debug_visitor_ != nullptr) { | |
| 234 // Call |debug_visitor_->OnNewEntry()| to get the current time. | |
| 235 HpackEntry& entry = dynamic_entries_.front(); | |
| 236 entry.set_time_added(debug_visitor_->OnNewEntry(entry)); | |
| 237 DVLOG(2) << "HpackHeaderTable::OnNewEntry: name=" << entry.name() | |
| 238 << ", value=" << entry.value() | |
| 239 << ", insert_index=" << entry.InsertionIndex() | |
| 240 << ", time_added=" << entry.time_added(); | |
| 241 } | |
| 242 | |
| 243 return &dynamic_entries_.front(); | |
| 244 } | |
| 245 | |
| 246 void HpackHeaderTable::DebugLogTableState() const { | |
| 247 DVLOG(2) << "Dynamic table:"; | |
| 248 for (EntryTable::const_iterator it = dynamic_entries_.begin(); | |
| 249 it != dynamic_entries_.end(); ++it) { | |
| 250 DVLOG(2) << " " << it->GetDebugString(); | |
| 251 } | |
| 252 DVLOG(2) << "Full Static Index:"; | |
| 253 for (auto* entry : static_index_) { | |
| 254 DVLOG(2) << " " << entry->GetDebugString(); | |
| 255 } | |
| 256 DVLOG(2) << "Full Static Name Index:"; | |
| 257 for (const auto it : static_name_index_) { | |
| 258 DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString(); | |
| 259 } | |
| 260 DVLOG(2) << "Full Dynamic Index:"; | |
| 261 for (auto* entry : dynamic_index_) { | |
| 262 DVLOG(2) << " " << entry->GetDebugString(); | |
| 263 } | |
| 264 DVLOG(2) << "Full Dynamic Name Index:"; | |
| 265 for (const auto it : dynamic_name_index_) { | |
| 266 DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString(); | |
| 267 } | |
| 268 } | |
| 269 | |
| 270 size_t HpackHeaderTable::EstimateMemoryUsage() const { | |
| 271 return SpdyEstimateMemoryUsage(dynamic_entries_) + | |
| 272 SpdyEstimateMemoryUsage(dynamic_index_) + | |
| 273 SpdyEstimateMemoryUsage(dynamic_name_index_); | |
| 274 } | |
| 275 | |
| 276 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2832973003:
Split net/spdy into core and chromium subdirectories. (Closed)
