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 #ifndef GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_ENCODER_H
20 #define GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_ENCODER_H
21
22 #include <grpc/slice.h>
23 #include <grpc/support/port_platform.h>
24 #include <stddef.h>
25
26 #include <cstdint>
27 #include <utility>
28 #include <vector>
29
30 #include "absl/log/log.h"
31 #include "absl/strings/match.h"
32 #include "absl/strings/str_cat.h"
33 #include "absl/strings/string_view.h"
34 #include "src/core/ext/transport/chttp2/transport/hpack_constants.h"
35 #include "src/core/ext/transport/chttp2/transport/hpack_encoder_table.h"
36 #include "src/core/lib/slice/slice.h"
37 #include "src/core/lib/slice/slice_buffer.h"
38 #include "src/core/lib/transport/metadata_batch.h"
39 #include "src/core/lib/transport/metadata_compression_traits.h"
40 #include "src/core/lib/transport/timeout_encoding.h"
41 #include "src/core/lib/transport/transport.h"
42 #include "src/core/telemetry/call_tracer.h"
43 #include "src/core/util/time.h"
44
45 namespace grpc_core {
46
47 // Forward decl for encoder
48 class HPackCompressor;
49
50 namespace hpack_encoder_detail {
51
52 class Encoder {
53 public:
54 Encoder(HPackCompressor* compressor, bool use_true_binary_metadata,
55 SliceBuffer& output);
56
57 void Encode(const Slice& key, const Slice& value);
58 template <typename MetadataTrait>
59 void Encode(MetadataTrait, const typename MetadataTrait::ValueType& value);
60
61 void AdvertiseTableSizeChange();
62 void EmitIndexed(uint32_t index);
63 GRPC_MUST_USE_RESULT
64 uint32_t EmitLitHdrWithNonBinaryStringKeyIncIdx(Slice key_slice,
65 Slice value_slice);
66 GRPC_MUST_USE_RESULT
67 uint32_t EmitLitHdrWithBinaryStringKeyIncIdx(Slice key_slice,
68 Slice value_slice);
69 void EmitLitHdrWithBinaryStringKeyNotIdx(Slice key_slice, Slice value_slice);
70 void EmitLitHdrWithBinaryStringKeyNotIdx(uint32_t key_index,
71 Slice value_slice);
72 void EmitLitHdrWithNonBinaryStringKeyNotIdx(Slice key_slice,
73 Slice value_slice);
74
75 void EncodeAlwaysIndexed(uint32_t* index, absl::string_view key, Slice value,
76 size_t transport_length);
77 void EncodeIndexedKeyWithBinaryValue(uint32_t* index, absl::string_view key,
78 Slice value);
79
80 void EncodeRepeatingSliceValue(const absl::string_view& key,
81 const Slice& slice, uint32_t* index,
82 size_t max_compression_size);
83
NoteEncodingError()84 void NoteEncodingError() { saw_encoding_errors_ = true; }
saw_encoding_errors()85 bool saw_encoding_errors() const { return saw_encoding_errors_; }
86
87 HPackEncoderTable& hpack_table();
88
89 private:
90 const bool use_true_binary_metadata_;
91 bool saw_encoding_errors_ = false;
92 HPackCompressor* const compressor_;
93 SliceBuffer& output_;
94 };
95
96 // Compressor is partially specialized on CompressionTraits, but leaves
97 // MetadataTrait as variable.
98 // Via MetadataMap::StatefulCompressor it builds compression state for
99 // HPackCompressor.
100 // Each trait compressor gets to have some persistent state across the channel
101 // (declared as Compressor member variables).
102 // The compressors expose a single method:
103 // void EncodeWith(MetadataTrait, const MetadataTrait::ValueType, Encoder*);
104 // This method figures out how to encode the value, and then delegates to
105 // Encoder to perform the encoding.
106 template <typename MetadataTrait, typename CompressionTraits>
107 class Compressor;
108
109 // No compression encoder: just emit the key and value as literals.
110 template <typename MetadataTrait>
111 class Compressor<MetadataTrait, NoCompressionCompressor> {
112 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)113 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
114 Encoder* encoder) {
115 const Slice& slice = MetadataValueAsSlice<MetadataTrait>(value);
116 if (absl::EndsWith(MetadataTrait::key(), "-bin")) {
117 encoder->EmitLitHdrWithBinaryStringKeyNotIdx(
118 Slice::FromStaticString(MetadataTrait::key()), slice.Ref());
119 } else {
120 encoder->EmitLitHdrWithNonBinaryStringKeyNotIdx(
121 Slice::FromStaticString(MetadataTrait::key()), slice.Ref());
122 }
123 }
124 };
125
126 // Frequent key with no value compression encoder
127 template <typename MetadataTrait>
128 class Compressor<MetadataTrait, FrequentKeyWithNoValueCompressionCompressor> {
129 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)130 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
131 Encoder* encoder) {
132 const Slice& slice = MetadataValueAsSlice<MetadataTrait>(value);
133 encoder->EncodeRepeatingSliceValue(MetadataTrait::key(), slice,
134 &some_sent_value_,
135 HPackEncoderTable::MaxEntrySize());
136 }
137
138 private:
139 // Some previously sent value with this tag.
140 uint32_t some_sent_value_ = 0;
141 };
142
143 // Helper to determine if two objects have the same identity.
144 // Equivalent here => equality, but equality does not imply equivalency.
145 // For example, two slices with the same contents are equal, but not
146 // equivalent.
147 // Used as a much faster check for equality than the full equality check,
148 // since many metadatum that are stable have the same root object in metadata
149 // maps.
150 template <typename T>
IsEquivalent(T a,T b)151 static bool IsEquivalent(T a, T b) {
152 return a == b;
153 }
154
155 template <typename T>
IsEquivalent(const Slice & a,const Slice & b)156 static bool IsEquivalent(const Slice& a, const Slice& b) {
157 return a.is_equivalent(b);
158 }
159
160 template <typename T>
SaveCopyTo(const T & value,T & copy)161 static void SaveCopyTo(const T& value, T& copy) {
162 copy = value;
163 }
164
SaveCopyTo(const Slice & value,Slice & copy)165 static inline void SaveCopyTo(const Slice& value, Slice& copy) {
166 copy = value.Ref();
167 }
168
169 template <typename MetadataTrait>
170 class Compressor<MetadataTrait, StableValueCompressor> {
171 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)172 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
173 Encoder* encoder) {
174 auto& table = encoder->hpack_table();
175 if (previously_sent_value_ == value &&
176 table.ConvertibleToDynamicIndex(previously_sent_index_)) {
177 encoder->EmitIndexed(table.DynamicIndex(previously_sent_index_));
178 return;
179 }
180 previously_sent_index_ = 0;
181 auto key = MetadataTrait::key();
182 const Slice& value_slice = MetadataValueAsSlice<MetadataTrait>(value);
183 if (hpack_constants::SizeForEntry(key.size(), value_slice.size()) >
184 HPackEncoderTable::MaxEntrySize()) {
185 encoder->EmitLitHdrWithNonBinaryStringKeyNotIdx(
186 Slice::FromStaticString(key), value_slice.Ref());
187 return;
188 }
189 encoder->EncodeAlwaysIndexed(
190 &previously_sent_index_, key, value_slice.Ref(),
191 hpack_constants::SizeForEntry(key.size(), value_slice.size()));
192 SaveCopyTo(value, previously_sent_value_);
193 }
194
195 private:
196 // Previously sent value
197 typename MetadataTrait::ValueType previously_sent_value_{};
198 // And its index in the table
199 uint32_t previously_sent_index_ = 0;
200 };
201
202 template <typename MetadataTrait, typename MetadataTrait::ValueType known_value>
203 class Compressor<
204 MetadataTrait,
205 KnownValueCompressor<typename MetadataTrait::ValueType, known_value>> {
206 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)207 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
208 Encoder* encoder) {
209 if (value != known_value) {
210 LOG(ERROR) << "Not encoding bad " << MetadataTrait::key() << " header";
211 encoder->NoteEncodingError();
212 return;
213 }
214 Slice encoded(MetadataTrait::Encode(known_value));
215 const auto encoded_length = encoded.length();
216 encoder->EncodeAlwaysIndexed(&previously_sent_index_, MetadataTrait::key(),
217 std::move(encoded),
218 MetadataTrait::key().size() + encoded_length +
219 hpack_constants::kEntryOverhead);
220 }
221
222 private:
223 uint32_t previously_sent_index_ = 0;
224 };
225 template <typename MetadataTrait, size_t N>
226 class Compressor<MetadataTrait, SmallIntegralValuesCompressor<N>> {
227 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)228 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
229 Encoder* encoder) {
230 uint32_t* index = nullptr;
231 auto& table = encoder->hpack_table();
232 if (static_cast<size_t>(value) < N) {
233 index = &previously_sent_[static_cast<uint32_t>(value)];
234 if (table.ConvertibleToDynamicIndex(*index)) {
235 encoder->EmitIndexed(table.DynamicIndex(*index));
236 return;
237 }
238 }
239 auto key = Slice::FromStaticString(MetadataTrait::key());
240 auto encoded_value = MetadataTrait::Encode(value);
241 if (index != nullptr) {
242 *index = encoder->EmitLitHdrWithNonBinaryStringKeyIncIdx(
243 std::move(key), std::move(encoded_value));
244 } else {
245 encoder->EmitLitHdrWithNonBinaryStringKeyNotIdx(std::move(key),
246 std::move(encoded_value));
247 }
248 }
249
250 private:
251 uint32_t previously_sent_[N] = {};
252 };
253
254 class SliceIndex {
255 public:
256 void EmitTo(absl::string_view key, const Slice& value, Encoder* encoder);
257
258 private:
259 struct ValueIndex {
ValueIndexValueIndex260 ValueIndex(Slice value, uint32_t index)
261 : value(std::move(value)), index(index) {}
262 Slice value;
263 uint32_t index;
264 };
265 std::vector<ValueIndex> values_;
266 };
267
268 template <typename MetadataTrait>
269 class Compressor<MetadataTrait, SmallSetOfValuesCompressor> {
270 public:
EncodeWith(MetadataTrait,const Slice & value,Encoder * encoder)271 void EncodeWith(MetadataTrait, const Slice& value, Encoder* encoder) {
272 index_.EmitTo(MetadataTrait::key(), value, encoder);
273 }
274
275 private:
276 SliceIndex index_;
277 };
278
279 struct PreviousTimeout {
280 Timeout timeout = Timeout::FromDuration(Duration::Zero());
281 // Dynamic table index of a previously sent timeout
282 // 0 is guaranteed not in the dynamic table so is a safe initializer
283 uint32_t index = 0;
284 };
285
286 class TimeoutCompressorImpl {
287 public:
288 void EncodeWith(absl::string_view key, Timestamp deadline, Encoder* encoder);
289
290 private:
291 static constexpr const size_t kNumPreviousValues = 5;
292 PreviousTimeout previous_timeouts_[kNumPreviousValues];
293 uint32_t next_previous_value_ = 0;
294 };
295
296 template <typename MetadataTrait>
297 class Compressor<MetadataTrait, TimeoutCompressor>
298 : public TimeoutCompressorImpl {
299 public:
EncodeWith(MetadataTrait,const typename MetadataTrait::ValueType & value,Encoder * encoder)300 void EncodeWith(MetadataTrait, const typename MetadataTrait::ValueType& value,
301 Encoder* encoder) {
302 TimeoutCompressorImpl::EncodeWith(MetadataTrait::key(), value, encoder);
303 }
304 };
305
306 template <>
307 class Compressor<HttpStatusMetadata, HttpStatusCompressor> {
308 public:
309 void EncodeWith(HttpStatusMetadata, uint32_t status, Encoder* encoder);
310 };
311
312 template <>
313 class Compressor<HttpMethodMetadata, HttpMethodCompressor> {
314 public:
315 void EncodeWith(HttpMethodMetadata, HttpMethodMetadata::ValueType method,
316 Encoder* encoder);
317 };
318
319 template <>
320 class Compressor<HttpSchemeMetadata, HttpSchemeCompressor> {
321 public:
322 void EncodeWith(HttpSchemeMetadata, HttpSchemeMetadata::ValueType value,
323 Encoder* encoder);
324 };
325
326 } // namespace hpack_encoder_detail
327
328 class HPackCompressor {
329 class SliceIndex;
330
331 public:
332 HPackCompressor() = default;
333 ~HPackCompressor() = default;
334
335 HPackCompressor(const HPackCompressor&) = delete;
336 HPackCompressor& operator=(const HPackCompressor&) = delete;
337 HPackCompressor(HPackCompressor&&) = default;
338 HPackCompressor& operator=(HPackCompressor&&) = default;
339
340 // Maximum table size we'll actually use.
341 static constexpr uint32_t kMaxTableSize = 1024 * 1024;
342
343 void SetMaxTableSize(uint32_t max_table_size);
344 void SetMaxUsableSize(uint32_t max_table_size);
345
test_only_table_size()346 uint32_t test_only_table_size() const {
347 return table_.test_only_table_size();
348 }
349
350 struct EncodeHeaderOptions {
351 uint32_t stream_id;
352 bool is_end_of_stream;
353 bool use_true_binary_metadata;
354 size_t max_frame_size;
355 CallTracerInterface* call_tracer;
356 };
357
358 template <typename HeaderSet>
EncodeHeaders(const EncodeHeaderOptions & options,const HeaderSet & headers,grpc_slice_buffer * output)359 bool EncodeHeaders(const EncodeHeaderOptions& options,
360 const HeaderSet& headers, grpc_slice_buffer* output) {
361 SliceBuffer raw;
362 hpack_encoder_detail::Encoder encoder(
363 this, options.use_true_binary_metadata, raw);
364 headers.Encode(&encoder);
365 Frame(options, raw, output);
366 return !encoder.saw_encoding_errors();
367 }
368
369 template <typename HeaderSet>
EncodeRawHeaders(const HeaderSet & headers,SliceBuffer & output)370 bool EncodeRawHeaders(const HeaderSet& headers, SliceBuffer& output) {
371 hpack_encoder_detail::Encoder encoder(this, true, output);
372 headers.Encode(&encoder);
373 return !encoder.saw_encoding_errors();
374 }
375
376 private:
377 static constexpr size_t kNumFilterValues = 64;
378 static constexpr uint32_t kNumCachedGrpcStatusValues = 16;
379 friend class hpack_encoder_detail::Encoder;
380
381 void Frame(const EncodeHeaderOptions& options, SliceBuffer& raw,
382 grpc_slice_buffer* output);
383
384 // maximum number of bytes we'll use for the decode table (to guard against
385 // peers ooming us by setting decode table size high)
386 uint32_t max_usable_size_ = hpack_constants::kInitialTableSize;
387 // if non-zero, advertise to the decoder that we'll start using a table
388 // of this size
389 bool advertise_table_size_change_ = false;
390 HPackEncoderTable table_;
391
392 grpc_metadata_batch::StatefulCompressor<hpack_encoder_detail::Compressor>
393 compression_state_;
394 };
395
396 namespace hpack_encoder_detail {
397
398 template <typename MetadataTrait>
Encode(MetadataTrait,const typename MetadataTrait::ValueType & value)399 void Encoder::Encode(MetadataTrait,
400 const typename MetadataTrait::ValueType& value) {
401 compressor_->compression_state_
402 .Compressor<MetadataTrait, typename MetadataTrait::CompressionTraits>::
403 EncodeWith(MetadataTrait(), value, this);
404 }
405
hpack_table()406 inline HPackEncoderTable& Encoder::hpack_table() { return compressor_->table_; }
407
408 } // namespace hpack_encoder_detail
409
410 } // namespace grpc_core
411
412 #endif // GRPC_SRC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_ENCODER_H
413