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_encoder.h"
22
23 #include <assert.h>
24 #include <string.h>
25
26 /* This is here for grpc_is_binary_header
27 * TODO(murgatroid99): Remove this
28 */
29 #include <grpc/grpc.h>
30
31 #include <grpc/support/alloc.h>
32 #include <grpc/support/log.h>
33
34 #include "src/core/ext/transport/chttp2/transport/bin_encoder.h"
35 #include "src/core/ext/transport/chttp2/transport/hpack_table.h"
36 #include "src/core/ext/transport/chttp2/transport/varint.h"
37 #include "src/core/lib/debug/stats.h"
38 #include "src/core/lib/slice/slice_internal.h"
39 #include "src/core/lib/slice/slice_string_helpers.h"
40 #include "src/core/lib/transport/metadata.h"
41 #include "src/core/lib/transport/static_metadata.h"
42 #include "src/core/lib/transport/timeout_encoding.h"
43
44 #define HASH_FRAGMENT_MASK (GRPC_CHTTP2_HPACKC_NUM_VALUES - 1)
45 #define HASH_FRAGMENT_1(x) ((x)&HASH_FRAGMENT_MASK)
46 #define HASH_FRAGMENT_2(x) \
47 (((x) >> GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS) & HASH_FRAGMENT_MASK)
48 #define HASH_FRAGMENT_3(x) \
49 (((x) >> (GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS * 2)) & HASH_FRAGMENT_MASK)
50 #define HASH_FRAGMENT_4(x) \
51 (((x) >> (GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS * 3)) & HASH_FRAGMENT_MASK)
52
53 /* if the probability of this item being seen again is < 1/x then don't add
54 it to the table */
55 #define ONE_ON_ADD_PROBABILITY (GRPC_CHTTP2_HPACKC_NUM_VALUES >> 1)
56 /* don't consider adding anything bigger than this to the hpack table */
57 #define MAX_DECODER_SPACE_USAGE 512
58
59 static grpc_slice_refcount terminal_slice_refcount = {nullptr, nullptr};
60 static const grpc_slice terminal_slice = {
61 &terminal_slice_refcount, /* refcount */
62 {{nullptr, 0}} /* data.refcounted */
63 };
64
65 typedef struct {
66 int is_first_frame;
67 /* number of bytes in 'output' when we started the frame - used to calculate
68 frame length */
69 size_t output_length_at_start_of_frame;
70 /* index (in output) of the header for the current frame */
71 size_t header_idx;
72 /* have we seen a regular (non-colon-prefixed) header yet? */
73 uint8_t seen_regular_header;
74 /* output stream id */
75 uint32_t stream_id;
76 grpc_slice_buffer* output;
77 grpc_transport_one_way_stats* stats;
78 /* maximum size of a frame */
79 size_t max_frame_size;
80 bool use_true_binary_metadata;
81 } framer_state;
82
83 /* fills p (which is expected to be 9 bytes long) with a data frame header */
fill_header(uint8_t * p,uint8_t type,uint32_t id,size_t len,uint8_t flags)84 static void fill_header(uint8_t* p, uint8_t type, uint32_t id, size_t len,
85 uint8_t flags) {
86 GPR_ASSERT(len < 16777316);
87 *p++ = static_cast<uint8_t>(len >> 16);
88 *p++ = static_cast<uint8_t>(len >> 8);
89 *p++ = static_cast<uint8_t>(len);
90 *p++ = type;
91 *p++ = flags;
92 *p++ = static_cast<uint8_t>(id >> 24);
93 *p++ = static_cast<uint8_t>(id >> 16);
94 *p++ = static_cast<uint8_t>(id >> 8);
95 *p++ = static_cast<uint8_t>(id);
96 }
97
98 /* finish a frame - fill in the previously reserved header */
finish_frame(framer_state * st,int is_header_boundary,int is_last_in_stream)99 static void finish_frame(framer_state* st, int is_header_boundary,
100 int is_last_in_stream) {
101 uint8_t type = 0xff;
102 type = st->is_first_frame ? GRPC_CHTTP2_FRAME_HEADER
103 : GRPC_CHTTP2_FRAME_CONTINUATION;
104 fill_header(
105 GRPC_SLICE_START_PTR(st->output->slices[st->header_idx]), type,
106 st->stream_id, st->output->length - st->output_length_at_start_of_frame,
107 static_cast<uint8_t>(
108 (is_last_in_stream ? GRPC_CHTTP2_DATA_FLAG_END_STREAM : 0) |
109 (is_header_boundary ? GRPC_CHTTP2_DATA_FLAG_END_HEADERS : 0)));
110 st->stats->framing_bytes += 9;
111 st->is_first_frame = 0;
112 }
113
114 /* begin a new frame: reserve off header space, remember how many bytes we'd
115 output before beginning */
begin_frame(framer_state * st)116 static void begin_frame(framer_state* st) {
117 st->header_idx =
118 grpc_slice_buffer_add_indexed(st->output, GRPC_SLICE_MALLOC(9));
119 st->output_length_at_start_of_frame = st->output->length;
120 }
121
122 /* make sure that the current frame is of the type desired, and has sufficient
123 space to add at least about_to_add bytes -- finishes the current frame if
124 needed */
ensure_space(framer_state * st,size_t need_bytes)125 static void ensure_space(framer_state* st, size_t need_bytes) {
126 if (st->output->length - st->output_length_at_start_of_frame + need_bytes <=
127 st->max_frame_size) {
128 return;
129 }
130 finish_frame(st, 0, 0);
131 begin_frame(st);
132 }
133
134 /* increment a filter count, halve all counts if one element reaches max */
inc_filter(uint8_t idx,uint32_t * sum,uint8_t * elems)135 static void inc_filter(uint8_t idx, uint32_t* sum, uint8_t* elems) {
136 elems[idx]++;
137 if (elems[idx] < 255) {
138 (*sum)++;
139 } else {
140 int i;
141 *sum = 0;
142 for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
143 elems[i] /= 2;
144 (*sum) += elems[i];
145 }
146 }
147 }
148
add_header_data(framer_state * st,grpc_slice slice)149 static void add_header_data(framer_state* st, grpc_slice slice) {
150 size_t len = GRPC_SLICE_LENGTH(slice);
151 size_t remaining;
152 if (len == 0) return;
153 remaining = st->max_frame_size + st->output_length_at_start_of_frame -
154 st->output->length;
155 if (len <= remaining) {
156 st->stats->header_bytes += len;
157 grpc_slice_buffer_add(st->output, slice);
158 } else {
159 st->stats->header_bytes += remaining;
160 grpc_slice_buffer_add(st->output, grpc_slice_split_head(&slice, remaining));
161 finish_frame(st, 0, 0);
162 begin_frame(st);
163 add_header_data(st, slice);
164 }
165 }
166
add_tiny_header_data(framer_state * st,size_t len)167 static uint8_t* add_tiny_header_data(framer_state* st, size_t len) {
168 ensure_space(st, len);
169 st->stats->header_bytes += len;
170 return grpc_slice_buffer_tiny_add(st->output, len);
171 }
172
evict_entry(grpc_chttp2_hpack_compressor * c)173 static void evict_entry(grpc_chttp2_hpack_compressor* c) {
174 c->tail_remote_index++;
175 GPR_ASSERT(c->tail_remote_index > 0);
176 GPR_ASSERT(c->table_size >=
177 c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
178 GPR_ASSERT(c->table_elems > 0);
179 c->table_size = static_cast<uint16_t>(
180 c->table_size -
181 c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
182 c->table_elems--;
183 }
184
185 // Reserve space in table for the new element, evict entries if needed.
186 // Return the new index of the element. Return 0 to indicate not adding to
187 // table.
prepare_space_for_new_elem(grpc_chttp2_hpack_compressor * c,size_t elem_size)188 static uint32_t prepare_space_for_new_elem(grpc_chttp2_hpack_compressor* c,
189 size_t elem_size) {
190 uint32_t new_index = c->tail_remote_index + c->table_elems + 1;
191 GPR_ASSERT(elem_size < 65536);
192
193 if (elem_size > c->max_table_size) {
194 while (c->table_size > 0) {
195 evict_entry(c);
196 }
197 return 0;
198 }
199
200 /* Reserve space for this element in the remote table: if this overflows
201 the current table, drop elements until it fits, matching the decompressor
202 algorithm */
203 while (c->table_size + elem_size > c->max_table_size) {
204 evict_entry(c);
205 }
206 GPR_ASSERT(c->table_elems < c->max_table_size);
207 c->table_elem_size[new_index % c->cap_table_elems] =
208 static_cast<uint16_t>(elem_size);
209 c->table_size = static_cast<uint16_t>(c->table_size + elem_size);
210 c->table_elems++;
211
212 return new_index;
213 }
214
215 /* dummy function */
add_nothing(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,size_t elem_size)216 static void add_nothing(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
217 size_t elem_size) {}
218
219 // Add a key to the dynamic table. Both key and value will be added to table at
220 // the decoder.
add_key_with_index(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,uint32_t new_index)221 static void add_key_with_index(grpc_chttp2_hpack_compressor* c,
222 grpc_mdelem elem, uint32_t new_index) {
223 if (new_index == 0) {
224 return;
225 }
226
227 uint32_t key_hash = grpc_slice_hash(GRPC_MDKEY(elem));
228
229 /* Store the key into {entries,indices}_keys */
230 if (grpc_slice_eq(c->entries_keys[HASH_FRAGMENT_2(key_hash)],
231 GRPC_MDKEY(elem))) {
232 c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
233 } else if (grpc_slice_eq(c->entries_keys[HASH_FRAGMENT_3(key_hash)],
234 GRPC_MDKEY(elem))) {
235 c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
236 } else if (c->entries_keys[HASH_FRAGMENT_2(key_hash)].refcount ==
237 &terminal_slice_refcount) {
238 c->entries_keys[HASH_FRAGMENT_2(key_hash)] =
239 grpc_slice_ref_internal(GRPC_MDKEY(elem));
240 c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
241 } else if (c->entries_keys[HASH_FRAGMENT_3(key_hash)].refcount ==
242 &terminal_slice_refcount) {
243 c->entries_keys[HASH_FRAGMENT_3(key_hash)] =
244 grpc_slice_ref_internal(GRPC_MDKEY(elem));
245 c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
246 } else if (c->indices_keys[HASH_FRAGMENT_2(key_hash)] <
247 c->indices_keys[HASH_FRAGMENT_3(key_hash)]) {
248 grpc_slice_unref_internal(c->entries_keys[HASH_FRAGMENT_2(key_hash)]);
249 c->entries_keys[HASH_FRAGMENT_2(key_hash)] =
250 grpc_slice_ref_internal(GRPC_MDKEY(elem));
251 c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
252 } else {
253 grpc_slice_unref_internal(c->entries_keys[HASH_FRAGMENT_3(key_hash)]);
254 c->entries_keys[HASH_FRAGMENT_3(key_hash)] =
255 grpc_slice_ref_internal(GRPC_MDKEY(elem));
256 c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
257 }
258 }
259
260 /* add an element to the decoder table */
add_elem_with_index(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,uint32_t new_index)261 static void add_elem_with_index(grpc_chttp2_hpack_compressor* c,
262 grpc_mdelem elem, uint32_t new_index) {
263 if (new_index == 0) {
264 return;
265 }
266 GPR_ASSERT(GRPC_MDELEM_IS_INTERNED(elem));
267
268 uint32_t key_hash = grpc_slice_hash(GRPC_MDKEY(elem));
269 uint32_t value_hash = grpc_slice_hash(GRPC_MDVALUE(elem));
270 uint32_t elem_hash = GRPC_MDSTR_KV_HASH(key_hash, value_hash);
271
272 /* Store this element into {entries,indices}_elem */
273 if (grpc_mdelem_eq(c->entries_elems[HASH_FRAGMENT_2(elem_hash)], elem)) {
274 /* already there: update with new index */
275 c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
276 } else if (grpc_mdelem_eq(c->entries_elems[HASH_FRAGMENT_3(elem_hash)],
277 elem)) {
278 /* already there (cuckoo): update with new index */
279 c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
280 } else if (GRPC_MDISNULL(c->entries_elems[HASH_FRAGMENT_2(elem_hash)])) {
281 /* not there, but a free element: add */
282 c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = GRPC_MDELEM_REF(elem);
283 c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
284 } else if (GRPC_MDISNULL(c->entries_elems[HASH_FRAGMENT_3(elem_hash)])) {
285 /* not there (cuckoo), but a free element: add */
286 c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = GRPC_MDELEM_REF(elem);
287 c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
288 } else if (c->indices_elems[HASH_FRAGMENT_2(elem_hash)] <
289 c->indices_elems[HASH_FRAGMENT_3(elem_hash)]) {
290 /* not there: replace oldest */
291 GRPC_MDELEM_UNREF(c->entries_elems[HASH_FRAGMENT_2(elem_hash)]);
292 c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = GRPC_MDELEM_REF(elem);
293 c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
294 } else {
295 /* not there: replace oldest */
296 GRPC_MDELEM_UNREF(c->entries_elems[HASH_FRAGMENT_3(elem_hash)]);
297 c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = GRPC_MDELEM_REF(elem);
298 c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
299 }
300
301 add_key_with_index(c, elem, new_index);
302 }
303
add_elem(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,size_t elem_size)304 static void add_elem(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
305 size_t elem_size) {
306 uint32_t new_index = prepare_space_for_new_elem(c, elem_size);
307 add_elem_with_index(c, elem, new_index);
308 }
309
add_key(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,size_t elem_size)310 static void add_key(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
311 size_t elem_size) {
312 uint32_t new_index = prepare_space_for_new_elem(c, elem_size);
313 add_key_with_index(c, elem, new_index);
314 }
315
emit_indexed(grpc_chttp2_hpack_compressor * c,uint32_t elem_index,framer_state * st)316 static void emit_indexed(grpc_chttp2_hpack_compressor* c, uint32_t elem_index,
317 framer_state* st) {
318 GRPC_STATS_INC_HPACK_SEND_INDEXED();
319 uint32_t len = GRPC_CHTTP2_VARINT_LENGTH(elem_index, 1);
320 GRPC_CHTTP2_WRITE_VARINT(elem_index, 1, 0x80, add_tiny_header_data(st, len),
321 len);
322 }
323
324 typedef struct {
325 grpc_slice data;
326 uint8_t huffman_prefix;
327 bool insert_null_before_wire_value;
328 } wire_value;
329
get_wire_value(grpc_mdelem elem,bool true_binary_enabled)330 static wire_value get_wire_value(grpc_mdelem elem, bool true_binary_enabled) {
331 wire_value wire_val;
332 if (grpc_is_binary_header(GRPC_MDKEY(elem))) {
333 if (true_binary_enabled) {
334 GRPC_STATS_INC_HPACK_SEND_BINARY();
335 wire_val.huffman_prefix = 0x00;
336 wire_val.insert_null_before_wire_value = true;
337 wire_val.data = grpc_slice_ref_internal(GRPC_MDVALUE(elem));
338
339 } else {
340 GRPC_STATS_INC_HPACK_SEND_BINARY_BASE64();
341 wire_val.huffman_prefix = 0x80;
342 wire_val.insert_null_before_wire_value = false;
343 wire_val.data =
344 grpc_chttp2_base64_encode_and_huffman_compress(GRPC_MDVALUE(elem));
345 }
346 } else {
347 /* TODO(ctiller): opportunistically compress non-binary headers */
348 GRPC_STATS_INC_HPACK_SEND_UNCOMPRESSED();
349 wire_val.huffman_prefix = 0x00;
350 wire_val.insert_null_before_wire_value = false;
351 wire_val.data = grpc_slice_ref_internal(GRPC_MDVALUE(elem));
352 }
353 return wire_val;
354 }
355
wire_value_length(wire_value v)356 static size_t wire_value_length(wire_value v) {
357 return GPR_SLICE_LENGTH(v.data) + v.insert_null_before_wire_value;
358 }
359
add_wire_value(framer_state * st,wire_value v)360 static void add_wire_value(framer_state* st, wire_value v) {
361 if (v.insert_null_before_wire_value) *add_tiny_header_data(st, 1) = 0;
362 add_header_data(st, v.data);
363 }
364
emit_lithdr_incidx(grpc_chttp2_hpack_compressor * c,uint32_t key_index,grpc_mdelem elem,framer_state * st)365 static void emit_lithdr_incidx(grpc_chttp2_hpack_compressor* c,
366 uint32_t key_index, grpc_mdelem elem,
367 framer_state* st) {
368 GRPC_STATS_INC_HPACK_SEND_LITHDR_INCIDX();
369 uint32_t len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 2);
370 wire_value value = get_wire_value(elem, st->use_true_binary_metadata);
371 size_t len_val = wire_value_length(value);
372 uint32_t len_val_len;
373 GPR_ASSERT(len_val <= UINT32_MAX);
374 len_val_len = GRPC_CHTTP2_VARINT_LENGTH((uint32_t)len_val, 1);
375 GRPC_CHTTP2_WRITE_VARINT(key_index, 2, 0x40,
376 add_tiny_header_data(st, len_pfx), len_pfx);
377 GRPC_CHTTP2_WRITE_VARINT((uint32_t)len_val, 1, value.huffman_prefix,
378 add_tiny_header_data(st, len_val_len), len_val_len);
379 add_wire_value(st, value);
380 }
381
emit_lithdr_noidx(grpc_chttp2_hpack_compressor * c,uint32_t key_index,grpc_mdelem elem,framer_state * st)382 static void emit_lithdr_noidx(grpc_chttp2_hpack_compressor* c,
383 uint32_t key_index, grpc_mdelem elem,
384 framer_state* st) {
385 GRPC_STATS_INC_HPACK_SEND_LITHDR_NOTIDX();
386 uint32_t len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 4);
387 wire_value value = get_wire_value(elem, st->use_true_binary_metadata);
388 size_t len_val = wire_value_length(value);
389 uint32_t len_val_len;
390 GPR_ASSERT(len_val <= UINT32_MAX);
391 len_val_len = GRPC_CHTTP2_VARINT_LENGTH((uint32_t)len_val, 1);
392 GRPC_CHTTP2_WRITE_VARINT(key_index, 4, 0x00,
393 add_tiny_header_data(st, len_pfx), len_pfx);
394 GRPC_CHTTP2_WRITE_VARINT((uint32_t)len_val, 1, value.huffman_prefix,
395 add_tiny_header_data(st, len_val_len), len_val_len);
396 add_wire_value(st, value);
397 }
398
emit_lithdr_incidx_v(grpc_chttp2_hpack_compressor * c,uint32_t unused_index,grpc_mdelem elem,framer_state * st)399 static void emit_lithdr_incidx_v(grpc_chttp2_hpack_compressor* c,
400 uint32_t unused_index, grpc_mdelem elem,
401 framer_state* st) {
402 GPR_ASSERT(unused_index == 0);
403 GRPC_STATS_INC_HPACK_SEND_LITHDR_INCIDX_V();
404 GRPC_STATS_INC_HPACK_SEND_UNCOMPRESSED();
405 uint32_t len_key = static_cast<uint32_t> GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
406 wire_value value = get_wire_value(elem, st->use_true_binary_metadata);
407 uint32_t len_val = static_cast<uint32_t>(wire_value_length(value));
408 uint32_t len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
409 uint32_t len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
410 GPR_ASSERT(len_key <= UINT32_MAX);
411 GPR_ASSERT(wire_value_length(value) <= UINT32_MAX);
412 *add_tiny_header_data(st, 1) = 0x40;
413 GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
414 add_tiny_header_data(st, len_key_len), len_key_len);
415 add_header_data(st, grpc_slice_ref_internal(GRPC_MDKEY(elem)));
416 GRPC_CHTTP2_WRITE_VARINT(len_val, 1, value.huffman_prefix,
417 add_tiny_header_data(st, len_val_len), len_val_len);
418 add_wire_value(st, value);
419 }
420
emit_lithdr_noidx_v(grpc_chttp2_hpack_compressor * c,uint32_t unused_index,grpc_mdelem elem,framer_state * st)421 static void emit_lithdr_noidx_v(grpc_chttp2_hpack_compressor* c,
422 uint32_t unused_index, grpc_mdelem elem,
423 framer_state* st) {
424 GPR_ASSERT(unused_index == 0);
425 GRPC_STATS_INC_HPACK_SEND_LITHDR_NOTIDX_V();
426 GRPC_STATS_INC_HPACK_SEND_UNCOMPRESSED();
427 uint32_t len_key = static_cast<uint32_t> GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
428 wire_value value = get_wire_value(elem, st->use_true_binary_metadata);
429 uint32_t len_val = static_cast<uint32_t>(wire_value_length(value));
430 uint32_t len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
431 uint32_t len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
432 GPR_ASSERT(len_key <= UINT32_MAX);
433 GPR_ASSERT(wire_value_length(value) <= UINT32_MAX);
434 *add_tiny_header_data(st, 1) = 0x00;
435 GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
436 add_tiny_header_data(st, len_key_len), len_key_len);
437 add_header_data(st, grpc_slice_ref_internal(GRPC_MDKEY(elem)));
438 GRPC_CHTTP2_WRITE_VARINT(len_val, 1, value.huffman_prefix,
439 add_tiny_header_data(st, len_val_len), len_val_len);
440 add_wire_value(st, value);
441 }
442
emit_advertise_table_size_change(grpc_chttp2_hpack_compressor * c,framer_state * st)443 static void emit_advertise_table_size_change(grpc_chttp2_hpack_compressor* c,
444 framer_state* st) {
445 uint32_t len = GRPC_CHTTP2_VARINT_LENGTH(c->max_table_size, 3);
446 GRPC_CHTTP2_WRITE_VARINT(c->max_table_size, 3, 0x20,
447 add_tiny_header_data(st, len), len);
448 c->advertise_table_size_change = 0;
449 }
450
dynidx(grpc_chttp2_hpack_compressor * c,uint32_t elem_index)451 static uint32_t dynidx(grpc_chttp2_hpack_compressor* c, uint32_t elem_index) {
452 return 1 + GRPC_CHTTP2_LAST_STATIC_ENTRY + c->tail_remote_index +
453 c->table_elems - elem_index;
454 }
455
456 /* encode an mdelem */
hpack_enc(grpc_chttp2_hpack_compressor * c,grpc_mdelem elem,framer_state * st)457 static void hpack_enc(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
458 framer_state* st) {
459 GPR_ASSERT(GRPC_SLICE_LENGTH(GRPC_MDKEY(elem)) > 0);
460 if (GRPC_SLICE_START_PTR(GRPC_MDKEY(elem))[0] != ':') { /* regular header */
461 st->seen_regular_header = 1;
462 } else {
463 GPR_ASSERT(
464 st->seen_regular_header == 0 &&
465 "Reserved header (colon-prefixed) happening after regular ones.");
466 }
467
468 if (grpc_http_trace.enabled()) {
469 char* k = grpc_slice_to_c_string(GRPC_MDKEY(elem));
470 char* v = nullptr;
471 if (grpc_is_binary_header(GRPC_MDKEY(elem))) {
472 v = grpc_dump_slice(GRPC_MDVALUE(elem), GPR_DUMP_HEX);
473 } else {
474 v = grpc_slice_to_c_string(GRPC_MDVALUE(elem));
475 }
476 gpr_log(
477 GPR_INFO,
478 "Encode: '%s: %s', elem_interned=%d [%d], k_interned=%d, v_interned=%d",
479 k, v, GRPC_MDELEM_IS_INTERNED(elem), GRPC_MDELEM_STORAGE(elem),
480 grpc_slice_is_interned(GRPC_MDKEY(elem)),
481 grpc_slice_is_interned(GRPC_MDVALUE(elem)));
482 gpr_free(k);
483 gpr_free(v);
484 }
485
486 bool elem_interned = GRPC_MDELEM_IS_INTERNED(elem);
487 bool key_interned = elem_interned || grpc_slice_is_interned(GRPC_MDKEY(elem));
488
489 // Key is not interned, emit literals.
490 if (!key_interned) {
491 emit_lithdr_noidx_v(c, 0, elem, st);
492 return;
493 }
494
495 uint32_t key_hash = grpc_slice_hash(GRPC_MDKEY(elem));
496 uint32_t elem_hash = 0;
497
498 if (elem_interned) {
499 uint32_t value_hash = grpc_slice_hash(GRPC_MDVALUE(elem));
500 elem_hash = GRPC_MDSTR_KV_HASH(key_hash, value_hash);
501
502 inc_filter(HASH_FRAGMENT_1(elem_hash), &c->filter_elems_sum,
503 c->filter_elems);
504
505 /* is this elem currently in the decoders table? */
506
507 if (grpc_mdelem_eq(c->entries_elems[HASH_FRAGMENT_2(elem_hash)], elem) &&
508 c->indices_elems[HASH_FRAGMENT_2(elem_hash)] > c->tail_remote_index) {
509 /* HIT: complete element (first cuckoo hash) */
510 emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_2(elem_hash)]),
511 st);
512 return;
513 }
514
515 if (grpc_mdelem_eq(c->entries_elems[HASH_FRAGMENT_3(elem_hash)], elem) &&
516 c->indices_elems[HASH_FRAGMENT_3(elem_hash)] > c->tail_remote_index) {
517 /* HIT: complete element (second cuckoo hash) */
518 emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_3(elem_hash)]),
519 st);
520 return;
521 }
522 }
523
524 uint32_t indices_key;
525
526 /* should this elem be in the table? */
527 size_t decoder_space_usage =
528 grpc_chttp2_get_size_in_hpack_table(elem, st->use_true_binary_metadata);
529 bool should_add_elem = elem_interned &&
530 decoder_space_usage < MAX_DECODER_SPACE_USAGE &&
531 c->filter_elems[HASH_FRAGMENT_1(elem_hash)] >=
532 c->filter_elems_sum / ONE_ON_ADD_PROBABILITY;
533 void (*maybe_add)(grpc_chttp2_hpack_compressor*, grpc_mdelem, size_t) =
534 should_add_elem ? add_elem : add_nothing;
535 void (*emit)(grpc_chttp2_hpack_compressor*, uint32_t, grpc_mdelem,
536 framer_state*) =
537 should_add_elem ? emit_lithdr_incidx : emit_lithdr_noidx;
538
539 /* no hits for the elem... maybe there's a key? */
540 indices_key = c->indices_keys[HASH_FRAGMENT_2(key_hash)];
541 if (grpc_slice_eq(c->entries_keys[HASH_FRAGMENT_2(key_hash)],
542 GRPC_MDKEY(elem)) &&
543 indices_key > c->tail_remote_index) {
544 /* HIT: key (first cuckoo hash) */
545 emit(c, dynidx(c, indices_key), elem, st);
546 maybe_add(c, elem, decoder_space_usage);
547 return;
548 }
549
550 indices_key = c->indices_keys[HASH_FRAGMENT_3(key_hash)];
551 if (grpc_slice_eq(c->entries_keys[HASH_FRAGMENT_3(key_hash)],
552 GRPC_MDKEY(elem)) &&
553 indices_key > c->tail_remote_index) {
554 /* HIT: key (first cuckoo hash) */
555 emit(c, dynidx(c, indices_key), elem, st);
556 maybe_add(c, elem, decoder_space_usage);
557 return;
558 }
559
560 /* no elem, key in the table... fall back to literal emission */
561 bool should_add_key =
562 !elem_interned && decoder_space_usage < MAX_DECODER_SPACE_USAGE;
563 emit = (should_add_elem || should_add_key) ? emit_lithdr_incidx_v
564 : emit_lithdr_noidx_v;
565 maybe_add =
566 should_add_elem ? add_elem : (should_add_key ? add_key : add_nothing);
567 emit(c, 0, elem, st);
568 maybe_add(c, elem, decoder_space_usage);
569 }
570
571 #define STRLEN_LIT(x) (sizeof(x) - 1)
572 #define TIMEOUT_KEY "grpc-timeout"
573
deadline_enc(grpc_chttp2_hpack_compressor * c,grpc_millis deadline,framer_state * st)574 static void deadline_enc(grpc_chttp2_hpack_compressor* c, grpc_millis deadline,
575 framer_state* st) {
576 char timeout_str[GRPC_HTTP2_TIMEOUT_ENCODE_MIN_BUFSIZE];
577 grpc_mdelem mdelem;
578 grpc_http2_encode_timeout(deadline - grpc_core::ExecCtx::Get()->Now(),
579 timeout_str);
580 mdelem = grpc_mdelem_from_slices(GRPC_MDSTR_GRPC_TIMEOUT,
581 grpc_slice_from_copied_string(timeout_str));
582 hpack_enc(c, mdelem, st);
583 GRPC_MDELEM_UNREF(mdelem);
584 }
585
elems_for_bytes(uint32_t bytes)586 static uint32_t elems_for_bytes(uint32_t bytes) { return (bytes + 31) / 32; }
587
grpc_chttp2_hpack_compressor_init(grpc_chttp2_hpack_compressor * c)588 void grpc_chttp2_hpack_compressor_init(grpc_chttp2_hpack_compressor* c) {
589 memset(c, 0, sizeof(*c));
590 c->max_table_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
591 c->cap_table_elems = elems_for_bytes(c->max_table_size);
592 c->max_table_elems = c->cap_table_elems;
593 c->max_usable_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
594 c->table_elem_size = static_cast<uint16_t*>(
595 gpr_malloc(sizeof(*c->table_elem_size) * c->cap_table_elems));
596 memset(c->table_elem_size, 0,
597 sizeof(*c->table_elem_size) * c->cap_table_elems);
598 for (size_t i = 0; i < GPR_ARRAY_SIZE(c->entries_keys); i++) {
599 c->entries_keys[i] = terminal_slice;
600 }
601 }
602
grpc_chttp2_hpack_compressor_destroy(grpc_chttp2_hpack_compressor * c)603 void grpc_chttp2_hpack_compressor_destroy(grpc_chttp2_hpack_compressor* c) {
604 int i;
605 for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
606 if (c->entries_keys[i].refcount != &terminal_slice_refcount) {
607 grpc_slice_unref_internal(c->entries_keys[i]);
608 }
609 GRPC_MDELEM_UNREF(c->entries_elems[i]);
610 }
611 gpr_free(c->table_elem_size);
612 }
613
grpc_chttp2_hpack_compressor_set_max_usable_size(grpc_chttp2_hpack_compressor * c,uint32_t max_table_size)614 void grpc_chttp2_hpack_compressor_set_max_usable_size(
615 grpc_chttp2_hpack_compressor* c, uint32_t max_table_size) {
616 c->max_usable_size = max_table_size;
617 grpc_chttp2_hpack_compressor_set_max_table_size(
618 c, GPR_MIN(c->max_table_size, max_table_size));
619 }
620
rebuild_elems(grpc_chttp2_hpack_compressor * c,uint32_t new_cap)621 static void rebuild_elems(grpc_chttp2_hpack_compressor* c, uint32_t new_cap) {
622 uint16_t* table_elem_size =
623 static_cast<uint16_t*>(gpr_malloc(sizeof(*table_elem_size) * new_cap));
624 uint32_t i;
625
626 memset(table_elem_size, 0, sizeof(*table_elem_size) * new_cap);
627 GPR_ASSERT(c->table_elems <= new_cap);
628
629 for (i = 0; i < c->table_elems; i++) {
630 uint32_t ofs = c->tail_remote_index + i + 1;
631 table_elem_size[ofs % new_cap] =
632 c->table_elem_size[ofs % c->cap_table_elems];
633 }
634
635 c->cap_table_elems = new_cap;
636 gpr_free(c->table_elem_size);
637 c->table_elem_size = table_elem_size;
638 }
639
grpc_chttp2_hpack_compressor_set_max_table_size(grpc_chttp2_hpack_compressor * c,uint32_t max_table_size)640 void grpc_chttp2_hpack_compressor_set_max_table_size(
641 grpc_chttp2_hpack_compressor* c, uint32_t max_table_size) {
642 max_table_size = GPR_MIN(max_table_size, c->max_usable_size);
643 if (max_table_size == c->max_table_size) {
644 return;
645 }
646 while (c->table_size > 0 && c->table_size > max_table_size) {
647 evict_entry(c);
648 }
649 c->max_table_size = max_table_size;
650 c->max_table_elems = elems_for_bytes(max_table_size);
651 if (c->max_table_elems > c->cap_table_elems) {
652 rebuild_elems(c, GPR_MAX(c->max_table_elems, 2 * c->cap_table_elems));
653 } else if (c->max_table_elems < c->cap_table_elems / 3) {
654 uint32_t new_cap = GPR_MAX(c->max_table_elems, 16);
655 if (new_cap != c->cap_table_elems) {
656 rebuild_elems(c, new_cap);
657 }
658 }
659 c->advertise_table_size_change = 1;
660 if (grpc_http_trace.enabled()) {
661 gpr_log(GPR_INFO, "set max table size from encoder to %d", max_table_size);
662 }
663 }
664
grpc_chttp2_encode_header(grpc_chttp2_hpack_compressor * c,grpc_mdelem ** extra_headers,size_t extra_headers_size,grpc_metadata_batch * metadata,const grpc_encode_header_options * options,grpc_slice_buffer * outbuf)665 void grpc_chttp2_encode_header(grpc_chttp2_hpack_compressor* c,
666 grpc_mdelem** extra_headers,
667 size_t extra_headers_size,
668 grpc_metadata_batch* metadata,
669 const grpc_encode_header_options* options,
670 grpc_slice_buffer* outbuf) {
671 GPR_ASSERT(options->stream_id != 0);
672
673 framer_state st;
674 st.seen_regular_header = 0;
675 st.stream_id = options->stream_id;
676 st.output = outbuf;
677 st.is_first_frame = 1;
678 st.stats = options->stats;
679 st.max_frame_size = options->max_frame_size;
680 st.use_true_binary_metadata = options->use_true_binary_metadata;
681
682 /* Encode a metadata batch; store the returned values, representing
683 a metadata element that needs to be unreffed back into the metadata
684 slot. THIS MAY NOT BE THE SAME ELEMENT (if a decoder table slot got
685 updated). After this loop, we'll do a batch unref of elements. */
686 begin_frame(&st);
687 if (c->advertise_table_size_change != 0) {
688 emit_advertise_table_size_change(c, &st);
689 }
690 for (size_t i = 0; i < extra_headers_size; ++i) {
691 grpc_mdelem md = *extra_headers[i];
692 uint8_t static_index = grpc_chttp2_get_static_hpack_table_index(md);
693 if (static_index) {
694 emit_indexed(c, static_index, &st);
695 } else {
696 hpack_enc(c, md, &st);
697 }
698 }
699 grpc_metadata_batch_assert_ok(metadata);
700 for (grpc_linked_mdelem* l = metadata->list.head; l; l = l->next) {
701 uint8_t static_index = grpc_chttp2_get_static_hpack_table_index(l->md);
702 if (static_index) {
703 emit_indexed(c, static_index, &st);
704 } else {
705 hpack_enc(c, l->md, &st);
706 }
707 }
708 grpc_millis deadline = metadata->deadline;
709 if (deadline != GRPC_MILLIS_INF_FUTURE) {
710 deadline_enc(c, deadline, &st);
711 }
712
713 finish_frame(&st, 1, options->is_eof);
714 }
715