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