1 //
2 //
3 // Copyright 2015 gRPC authors.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 //
18
19 #include <grpc/support/port_platform.h>
20
21 #include "src/core/ext/transport/chttp2/transport/hpack_parser_table.h"
22
23 #include <stdlib.h>
24
25 #include <algorithm>
26 #include <cstddef>
27 #include <cstring>
28 #include <utility>
29
30 #include "absl/status/status.h"
31 #include "absl/strings/str_cat.h"
32 #include "absl/strings/string_view.h"
33
34 #include <grpc/support/log.h>
35
36 #include "src/core/ext/transport/chttp2/transport/hpack_constants.h"
37 #include "src/core/ext/transport/chttp2/transport/hpack_parse_result.h"
38 #include "src/core/ext/transport/chttp2/transport/http_trace.h"
39 #include "src/core/lib/debug/trace.h"
40 #include "src/core/lib/slice/slice.h"
41
42 namespace grpc_core {
43
Put(Memento m)44 void HPackTable::MementoRingBuffer::Put(Memento m) {
45 GPR_ASSERT(num_entries_ < max_entries_);
46 if (entries_.size() < max_entries_) {
47 ++num_entries_;
48 return entries_.push_back(std::move(m));
49 }
50 size_t index = (first_entry_ + num_entries_) % max_entries_;
51 entries_[index] = std::move(m);
52 ++num_entries_;
53 }
54
PopOne()55 auto HPackTable::MementoRingBuffer::PopOne() -> Memento {
56 GPR_ASSERT(num_entries_ > 0);
57 size_t index = first_entry_ % max_entries_;
58 ++first_entry_;
59 --num_entries_;
60 return std::move(entries_[index]);
61 }
62
Lookup(uint32_t index) const63 auto HPackTable::MementoRingBuffer::Lookup(uint32_t index) const
64 -> const Memento* {
65 if (index >= num_entries_) return nullptr;
66 uint32_t offset = (num_entries_ - 1u - index + first_entry_) % max_entries_;
67 return &entries_[offset];
68 }
69
Rebuild(uint32_t max_entries)70 void HPackTable::MementoRingBuffer::Rebuild(uint32_t max_entries) {
71 if (max_entries == max_entries_) return;
72 max_entries_ = max_entries;
73 std::vector<Memento> entries;
74 entries.reserve(num_entries_);
75 for (size_t i = 0; i < num_entries_; i++) {
76 entries.push_back(
77 std::move(entries_[(first_entry_ + i) % entries_.size()]));
78 }
79 first_entry_ = 0;
80 entries_.swap(entries);
81 }
82
ForEach(absl::FunctionRef<void (uint32_t,const Memento &)> f) const83 void HPackTable::MementoRingBuffer::ForEach(
84 absl::FunctionRef<void(uint32_t, const Memento&)> f) const {
85 uint32_t index = 0;
86 while (auto* m = Lookup(index++)) {
87 f(index, *m);
88 }
89 }
90
91 // Evict one element from the table
EvictOne()92 void HPackTable::EvictOne() {
93 auto first_entry = entries_.PopOne();
94 GPR_ASSERT(first_entry.md.transport_size() <= mem_used_);
95 mem_used_ -= first_entry.md.transport_size();
96 }
97
SetMaxBytes(uint32_t max_bytes)98 void HPackTable::SetMaxBytes(uint32_t max_bytes) {
99 if (max_bytes_ == max_bytes) {
100 return;
101 }
102 if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
103 gpr_log(GPR_INFO, "Update hpack parser max size to %d", max_bytes);
104 }
105 while (mem_used_ > max_bytes) {
106 EvictOne();
107 }
108 max_bytes_ = max_bytes;
109 }
110
SetCurrentTableSize(uint32_t bytes)111 bool HPackTable::SetCurrentTableSize(uint32_t bytes) {
112 if (current_table_bytes_ == bytes) return true;
113 if (bytes > max_bytes_) return false;
114 if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
115 gpr_log(GPR_INFO, "Update hpack parser table size to %d", bytes);
116 }
117 while (mem_used_ > bytes) {
118 EvictOne();
119 }
120 current_table_bytes_ = bytes;
121 uint32_t new_cap = std::max(hpack_constants::EntriesForBytes(bytes),
122 hpack_constants::kInitialTableEntries);
123 entries_.Rebuild(new_cap);
124 return true;
125 }
126
Add(Memento md)127 bool HPackTable::Add(Memento md) {
128 if (current_table_bytes_ > max_bytes_) return false;
129
130 // we can't add elements bigger than the max table size
131 if (md.md.transport_size() > current_table_bytes_) {
132 AddLargerThanCurrentTableSize();
133 return true;
134 }
135
136 // evict entries to ensure no overflow
137 while (md.md.transport_size() >
138 static_cast<size_t>(current_table_bytes_) - mem_used_) {
139 EvictOne();
140 }
141
142 // copy the finalized entry in
143 mem_used_ += md.md.transport_size();
144 entries_.Put(std::move(md));
145 return true;
146 }
147
AddLargerThanCurrentTableSize()148 void HPackTable::AddLargerThanCurrentTableSize() {
149 // HPACK draft 10 section 4.4 states:
150 // If the size of the new entry is less than or equal to the maximum
151 // size, that entry is added to the table. It is not an error to
152 // attempt to add an entry that is larger than the maximum size; an
153 // attempt to add an entry larger than the entire table causes
154 // the table to be emptied of all existing entries, and results in an
155 // empty table.
156 while (entries_.num_entries()) {
157 EvictOne();
158 }
159 }
160
TestOnlyDynamicTableAsString() const161 std::string HPackTable::TestOnlyDynamicTableAsString() const {
162 std::string out;
163 entries_.ForEach([&out](uint32_t i, const Memento& m) {
164 if (m.parse_status.ok()) {
165 absl::StrAppend(&out, i, ": ", m.md.DebugString(), "\n");
166 } else {
167 absl::StrAppend(&out, i, ": ", m.parse_status.Materialize().ToString(),
168 "\n");
169 }
170 });
171 return out;
172 }
173
174 namespace {
175 struct StaticTableEntry {
176 const char* key;
177 const char* value;
178 };
179
180 const StaticTableEntry kStaticTable[hpack_constants::kLastStaticEntry] = {
181 {":authority", ""},
182 {":method", "GET"},
183 {":method", "POST"},
184 {":path", "/"},
185 {":path", "/index.html"},
186 {":scheme", "http"},
187 {":scheme", "https"},
188 {":status", "200"},
189 {":status", "204"},
190 {":status", "206"},
191 {":status", "304"},
192 {":status", "400"},
193 {":status", "404"},
194 {":status", "500"},
195 {"accept-charset", ""},
196 {"accept-encoding", "gzip, deflate"},
197 {"accept-language", ""},
198 {"accept-ranges", ""},
199 {"accept", ""},
200 {"access-control-allow-origin", ""},
201 {"age", ""},
202 {"allow", ""},
203 {"authorization", ""},
204 {"cache-control", ""},
205 {"content-disposition", ""},
206 {"content-encoding", ""},
207 {"content-language", ""},
208 {"content-length", ""},
209 {"content-location", ""},
210 {"content-range", ""},
211 {"content-type", ""},
212 {"cookie", ""},
213 {"date", ""},
214 {"etag", ""},
215 {"expect", ""},
216 {"expires", ""},
217 {"from", ""},
218 {"host", ""},
219 {"if-match", ""},
220 {"if-modified-since", ""},
221 {"if-none-match", ""},
222 {"if-range", ""},
223 {"if-unmodified-since", ""},
224 {"last-modified", ""},
225 {"link", ""},
226 {"location", ""},
227 {"max-forwards", ""},
228 {"proxy-authenticate", ""},
229 {"proxy-authorization", ""},
230 {"range", ""},
231 {"referer", ""},
232 {"refresh", ""},
233 {"retry-after", ""},
234 {"server", ""},
235 {"set-cookie", ""},
236 {"strict-transport-security", ""},
237 {"transfer-encoding", ""},
238 {"user-agent", ""},
239 {"vary", ""},
240 {"via", ""},
241 {"www-authenticate", ""},
242 };
243
MakeMemento(size_t i)244 HPackTable::Memento MakeMemento(size_t i) {
245 auto sm = kStaticTable[i];
246 return HPackTable::Memento{
247 grpc_metadata_batch::Parse(
248 sm.key, Slice::FromStaticString(sm.value),
249 strlen(sm.key) + strlen(sm.value) + hpack_constants::kEntryOverhead,
250 [](absl::string_view, const Slice&) {
251 abort(); // not expecting to see this
252 }),
253 HpackParseResult()};
254 }
255
256 } // namespace
257
StaticMementos()258 HPackTable::StaticMementos::StaticMementos() {
259 for (uint32_t i = 0; i < hpack_constants::kLastStaticEntry; i++) {
260 memento[i] = MakeMemento(i);
261 }
262 }
263
264 } // namespace grpc_core
265