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 "quiche/spdy/core/hpack/hpack_header_table.h"
6
7 #include <algorithm>
8
9 #include "quiche/common/platform/api/quiche_logging.h"
10 #include "quiche/spdy/core/hpack/hpack_constants.h"
11 #include "quiche/spdy/core/hpack/hpack_static_table.h"
12
13 namespace spdy {
14
HpackHeaderTable()15 HpackHeaderTable::HpackHeaderTable()
16 : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
17 static_index_(ObtainHpackStaticTable().GetStaticIndex()),
18 static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()),
19 settings_size_bound_(kDefaultHeaderTableSizeSetting),
20 size_(0),
21 max_size_(kDefaultHeaderTableSizeSetting),
22 dynamic_table_insertions_(0) {}
23
24 HpackHeaderTable::~HpackHeaderTable() = default;
25
GetByName(absl::string_view name)26 size_t HpackHeaderTable::GetByName(absl::string_view name) {
27 {
28 auto it = static_name_index_.find(name);
29 if (it != static_name_index_.end()) {
30 return 1 + it->second;
31 }
32 }
33 {
34 NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
35 if (it != dynamic_name_index_.end()) {
36 return dynamic_table_insertions_ - it->second + kStaticTableSize;
37 }
38 }
39 return kHpackEntryNotFound;
40 }
41
GetByNameAndValue(absl::string_view name,absl::string_view value)42 size_t HpackHeaderTable::GetByNameAndValue(absl::string_view name,
43 absl::string_view value) {
44 HpackLookupEntry query{name, value};
45 {
46 auto it = static_index_.find(query);
47 if (it != static_index_.end()) {
48 return 1 + it->second;
49 }
50 }
51 {
52 auto it = dynamic_index_.find(query);
53 if (it != dynamic_index_.end()) {
54 return dynamic_table_insertions_ - it->second + kStaticTableSize;
55 }
56 }
57 return kHpackEntryNotFound;
58 }
59
SetMaxSize(size_t max_size)60 void HpackHeaderTable::SetMaxSize(size_t max_size) {
61 QUICHE_CHECK_LE(max_size, settings_size_bound_);
62
63 max_size_ = max_size;
64 if (size_ > max_size_) {
65 Evict(EvictionCountToReclaim(size_ - max_size_));
66 QUICHE_CHECK_LE(size_, max_size_);
67 }
68 }
69
SetSettingsHeaderTableSize(size_t settings_size)70 void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
71 settings_size_bound_ = settings_size;
72 SetMaxSize(settings_size_bound_);
73 }
74
EvictionSet(absl::string_view name,absl::string_view value,DynamicEntryTable::iterator * begin_out,DynamicEntryTable::iterator * end_out)75 void HpackHeaderTable::EvictionSet(absl::string_view name,
76 absl::string_view value,
77 DynamicEntryTable::iterator* begin_out,
78 DynamicEntryTable::iterator* end_out) {
79 size_t eviction_count = EvictionCountForEntry(name, value);
80 *begin_out = dynamic_entries_.end() - eviction_count;
81 *end_out = dynamic_entries_.end();
82 }
83
EvictionCountForEntry(absl::string_view name,absl::string_view value) const84 size_t HpackHeaderTable::EvictionCountForEntry(absl::string_view name,
85 absl::string_view value) const {
86 size_t available_size = max_size_ - size_;
87 size_t entry_size = HpackEntry::Size(name, value);
88
89 if (entry_size <= available_size) {
90 // No evictions are required.
91 return 0;
92 }
93 return EvictionCountToReclaim(entry_size - available_size);
94 }
95
EvictionCountToReclaim(size_t reclaim_size) const96 size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
97 size_t count = 0;
98 for (auto it = dynamic_entries_.rbegin();
99 it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
100 reclaim_size -= std::min(reclaim_size, (*it)->Size());
101 }
102 return count;
103 }
104
Evict(size_t count)105 void HpackHeaderTable::Evict(size_t count) {
106 for (size_t i = 0; i != count; ++i) {
107 QUICHE_CHECK(!dynamic_entries_.empty());
108
109 HpackEntry* entry = dynamic_entries_.back().get();
110 const size_t index = dynamic_table_insertions_ - dynamic_entries_.size();
111
112 size_ -= entry->Size();
113 auto it = dynamic_index_.find({entry->name(), entry->value()});
114 QUICHE_DCHECK(it != dynamic_index_.end());
115 // Only remove an entry from the index if its insertion index matches;
116 // otherwise, the index refers to another entry with the same name and
117 // value.
118 if (it->second == index) {
119 dynamic_index_.erase(it);
120 }
121 auto name_it = dynamic_name_index_.find(entry->name());
122 QUICHE_DCHECK(name_it != dynamic_name_index_.end());
123 // Only remove an entry from the literal index if its insertion index
124 /// matches; otherwise, the index refers to another entry with the same
125 // name.
126 if (name_it->second == index) {
127 dynamic_name_index_.erase(name_it);
128 }
129 dynamic_entries_.pop_back();
130 }
131 }
132
TryAddEntry(absl::string_view name,absl::string_view value)133 const HpackEntry* HpackHeaderTable::TryAddEntry(absl::string_view name,
134 absl::string_view value) {
135 // Since |dynamic_entries_| has iterator stability, |name| and |value| are
136 // valid even after evicting other entries and push_front() making room for
137 // the new one.
138 Evict(EvictionCountForEntry(name, value));
139
140 size_t entry_size = HpackEntry::Size(name, value);
141 if (entry_size > (max_size_ - size_)) {
142 // Entire table has been emptied, but there's still insufficient room.
143 QUICHE_DCHECK(dynamic_entries_.empty());
144 QUICHE_DCHECK_EQ(0u, size_);
145 return nullptr;
146 }
147
148 const size_t index = dynamic_table_insertions_;
149 dynamic_entries_.push_front(
150 std::make_unique<HpackEntry>(std::string(name), std::string(value)));
151 HpackEntry* new_entry = dynamic_entries_.front().get();
152 auto index_result = dynamic_index_.insert(std::make_pair(
153 HpackLookupEntry{new_entry->name(), new_entry->value()}, index));
154 if (!index_result.second) {
155 // An entry with the same name and value already exists in the dynamic
156 // index. We should replace it with the newly added entry.
157 QUICHE_DVLOG(1) << "Found existing entry at: " << index_result.first->second
158 << " replacing with: " << new_entry->GetDebugString()
159 << " at: " << index;
160 QUICHE_DCHECK_GT(index, index_result.first->second);
161 dynamic_index_.erase(index_result.first);
162 auto insert_result = dynamic_index_.insert(std::make_pair(
163 HpackLookupEntry{new_entry->name(), new_entry->value()}, index));
164 QUICHE_CHECK(insert_result.second);
165 }
166
167 auto name_result =
168 dynamic_name_index_.insert(std::make_pair(new_entry->name(), index));
169 if (!name_result.second) {
170 // An entry with the same name already exists in the dynamic index. We
171 // should replace it with the newly added entry.
172 QUICHE_DVLOG(1) << "Found existing entry at: " << name_result.first->second
173 << " replacing with: " << new_entry->GetDebugString()
174 << " at: " << index;
175 QUICHE_DCHECK_GT(index, name_result.first->second);
176 dynamic_name_index_.erase(name_result.first);
177 auto insert_result =
178 dynamic_name_index_.insert(std::make_pair(new_entry->name(), index));
179 QUICHE_CHECK(insert_result.second);
180 }
181
182 size_ += entry_size;
183 ++dynamic_table_insertions_;
184
185 return dynamic_entries_.front().get();
186 }
187
188 } // namespace spdy
189