Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/transport/chttp2/stream_encoder.h"
35 :
36 : #include <assert.h>
37 : #include <string.h>
38 :
39 : #include <grpc/support/log.h>
40 : #include <grpc/support/useful.h>
41 : #include "src/core/transport/chttp2/bin_encoder.h"
42 : #include "src/core/transport/chttp2/hpack_table.h"
43 : #include "src/core/transport/chttp2/timeout_encoding.h"
44 : #include "src/core/transport/chttp2/varint.h"
45 :
46 : #define HASH_FRAGMENT_1(x) ((x)&255)
47 : #define HASH_FRAGMENT_2(x) ((x >> 8) & 255)
48 : #define HASH_FRAGMENT_3(x) ((x >> 16) & 255)
49 : #define HASH_FRAGMENT_4(x) ((x >> 24) & 255)
50 :
51 : /* if the probability of this item being seen again is < 1/x then don't add
52 : it to the table */
53 : #define ONE_ON_ADD_PROBABILITY 128
54 : /* don't consider adding anything bigger than this to the hpack table */
55 : #define MAX_DECODER_SPACE_USAGE 512
56 :
57 : /* what kind of frame our we encoding? */
58 : typedef enum { HEADER, DATA, NONE } frame_type;
59 :
60 : typedef struct {
61 : frame_type cur_frame_type;
62 : /* number of bytes in 'output' when we started the frame - used to calculate
63 : frame length */
64 : size_t output_length_at_start_of_frame;
65 : /* index (in output) of the header for the current frame */
66 : size_t header_idx;
67 : /* was the last frame emitted a header? (if yes, we'll need a CONTINUATION */
68 : gpr_uint8 last_was_header;
69 : /* have we seen a regular (non-colon-prefixed) header yet? */
70 : gpr_uint8 seen_regular_header;
71 : /* output stream id */
72 : gpr_uint32 stream_id;
73 : gpr_slice_buffer *output;
74 : } framer_state;
75 :
76 : /* fills p (which is expected to be 9 bytes long) with a data frame header */
77 7130049 : static void fill_header(gpr_uint8 *p, gpr_uint8 type, gpr_uint32 id, size_t len,
78 : gpr_uint8 flags) {
79 7130049 : GPR_ASSERT(len < 16777316);
80 7130049 : *p++ = (gpr_uint8)(len >> 16);
81 7130049 : *p++ = (gpr_uint8)(len >> 8);
82 7130049 : *p++ = (gpr_uint8)(len);
83 7130049 : *p++ = type;
84 7130049 : *p++ = flags;
85 7130049 : *p++ = (gpr_uint8)(id >> 24);
86 7130049 : *p++ = (gpr_uint8)(id >> 16);
87 7130049 : *p++ = (gpr_uint8)(id >> 8);
88 7130049 : *p++ = (gpr_uint8)(id);
89 7130049 : }
90 :
91 : /* finish a frame - fill in the previously reserved header */
92 10262014 : static void finish_frame(framer_state *st, int is_header_boundary,
93 : int is_last_in_stream) {
94 10262014 : gpr_uint8 type = 0xff;
95 10262014 : switch (st->cur_frame_type) {
96 : case HEADER:
97 4116403 : type = st->last_was_header ? GRPC_CHTTP2_FRAME_CONTINUATION
98 : : GRPC_CHTTP2_FRAME_HEADER;
99 4116403 : st->last_was_header = 1;
100 4116403 : break;
101 : case DATA:
102 3017566 : type = GRPC_CHTTP2_FRAME_DATA;
103 3017566 : st->last_was_header = 0;
104 3017566 : is_header_boundary = 0;
105 3017566 : break;
106 : case NONE:
107 13397403 : return;
108 : }
109 28520012 : fill_header(
110 14260006 : GPR_SLICE_START_PTR(st->output->slices[st->header_idx]), type,
111 7130003 : st->stream_id, st->output->length - st->output_length_at_start_of_frame,
112 7130003 : (gpr_uint8)(
113 : (is_last_in_stream ? GRPC_CHTTP2_DATA_FLAG_END_STREAM : 0) |
114 : (is_header_boundary ? GRPC_CHTTP2_DATA_FLAG_END_HEADERS : 0)));
115 7133381 : st->cur_frame_type = NONE;
116 : }
117 :
118 : /* begin a new frame: reserve off header space, remember how many bytes we'd
119 : output before beginning */
120 7126812 : static void begin_frame(framer_state *st, frame_type type) {
121 7126812 : GPR_ASSERT(type != NONE);
122 7126812 : GPR_ASSERT(st->cur_frame_type == NONE);
123 7126812 : st->cur_frame_type = type;
124 7134758 : st->header_idx =
125 7126812 : gpr_slice_buffer_add_indexed(st->output, gpr_slice_malloc(9));
126 7134758 : st->output_length_at_start_of_frame = st->output->length;
127 7134758 : }
128 :
129 4113069 : static void begin_new_frame(framer_state *st, frame_type type) {
130 4113069 : finish_frame(st, 1, 0);
131 4114572 : st->last_was_header = 0;
132 4114572 : begin_frame(st, type);
133 4116397 : }
134 :
135 : /* make sure that the current frame is of the type desired, and has sufficient
136 : space to add at least about_to_add bytes -- finishes the current frame if
137 : needed */
138 25690506 : static void ensure_frame_type(framer_state *st, frame_type type,
139 : size_t need_bytes) {
140 48389883 : if (st->cur_frame_type == type &&
141 22699377 : st->output->length - st->output_length_at_start_of_frame + need_bytes <=
142 : GRPC_CHTTP2_MAX_PAYLOAD_LENGTH) {
143 48430912 : return;
144 : }
145 2983778 : finish_frame(st, type != HEADER, 0);
146 3018659 : begin_frame(st, type);
147 : }
148 :
149 : /* increment a filter count, halve all counts if one element reaches max */
150 19193342 : static void inc_filter(gpr_uint8 idx, gpr_uint32 *sum, gpr_uint8 *elems) {
151 19193342 : elems[idx]++;
152 19193342 : if (elems[idx] < 255) {
153 19170312 : (*sum)++;
154 : } else {
155 : int i;
156 23030 : *sum = 0;
157 5917969 : for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_FILTERS; i++) {
158 5894939 : elems[i] /= 2;
159 5894939 : (*sum) += elems[i];
160 : }
161 : }
162 19193342 : }
163 :
164 258011 : static void add_header_data(framer_state *st, gpr_slice slice) {
165 258011 : size_t len = GPR_SLICE_LENGTH(slice);
166 : size_t remaining;
167 516022 : if (len == 0) return;
168 258005 : ensure_frame_type(st, HEADER, 1);
169 258005 : remaining = GRPC_CHTTP2_MAX_PAYLOAD_LENGTH +
170 258005 : st->output_length_at_start_of_frame - st->output->length;
171 258005 : if (len <= remaining) {
172 257901 : gpr_slice_buffer_add(st->output, slice);
173 : } else {
174 104 : gpr_slice_buffer_add(st->output, gpr_slice_split_head(&slice, remaining));
175 104 : add_header_data(st, slice);
176 : }
177 : }
178 :
179 19460951 : static gpr_uint8 *add_tiny_header_data(framer_state *st, size_t len) {
180 19460951 : ensure_frame_type(st, HEADER, len);
181 19465333 : return gpr_slice_buffer_tiny_add(st->output, len);
182 : }
183 :
184 : /* add an element to the decoder table: returns metadata element to unref */
185 37664 : static grpc_mdelem *add_elem(grpc_chttp2_hpack_compressor *c,
186 : grpc_mdelem *elem) {
187 37664 : gpr_uint32 key_hash = elem->key->hash;
188 37664 : gpr_uint32 elem_hash = GRPC_MDSTR_KV_HASH(key_hash, elem->value->hash);
189 37664 : gpr_uint32 new_index = c->tail_remote_index + c->table_elems + 1;
190 75328 : size_t elem_size = 32 + GPR_SLICE_LENGTH(elem->key->slice) +
191 37664 : GPR_SLICE_LENGTH(elem->value->slice);
192 : grpc_mdelem *elem_to_unref;
193 :
194 37664 : GPR_ASSERT(elem_size < 65536);
195 :
196 : /* Reserve space for this element in the remote table: if this overflows
197 : the current table, drop elements until it fits, matching the decompressor
198 : algorithm */
199 : /* TODO(ctiller): constant */
200 82496 : while (c->table_size + elem_size > 4096) {
201 7168 : c->tail_remote_index++;
202 7168 : GPR_ASSERT(c->tail_remote_index > 0);
203 7168 : GPR_ASSERT(c->table_size >=
204 : c->table_elem_size[c->tail_remote_index %
205 : GRPC_CHTTP2_HPACKC_MAX_TABLE_ELEMS]);
206 7168 : GPR_ASSERT(c->table_elems > 0);
207 7168 : c->table_size =
208 14336 : (gpr_uint16)(c->table_size -
209 7168 : c->table_elem_size[c->tail_remote_index %
210 : GRPC_CHTTP2_HPACKC_MAX_TABLE_ELEMS]);
211 7168 : c->table_elems--;
212 : }
213 37664 : GPR_ASSERT(c->table_elems < GRPC_CHTTP2_HPACKC_MAX_TABLE_ELEMS);
214 75328 : c->table_elem_size[new_index % GRPC_CHTTP2_HPACKC_MAX_TABLE_ELEMS] =
215 37664 : (gpr_uint16)elem_size;
216 37664 : c->table_size = (gpr_uint16)(c->table_size + elem_size);
217 37664 : c->table_elems++;
218 :
219 : /* Store this element into {entries,indices}_elem */
220 37664 : if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == elem) {
221 : /* already there: update with new index */
222 378 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
223 378 : elem_to_unref = elem;
224 37286 : } else if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == elem) {
225 : /* already there (cuckoo): update with new index */
226 313 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
227 313 : elem_to_unref = elem;
228 36973 : } else if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == NULL) {
229 : /* not there, but a free element: add */
230 31012 : c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = elem;
231 31012 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
232 31012 : elem_to_unref = NULL;
233 5961 : } else if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == NULL) {
234 : /* not there (cuckoo), but a free element: add */
235 1349 : c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = elem;
236 1349 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
237 1349 : elem_to_unref = NULL;
238 9224 : } else if (c->indices_elems[HASH_FRAGMENT_2(elem_hash)] <
239 4612 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)]) {
240 : /* not there: replace oldest */
241 2275 : elem_to_unref = c->entries_elems[HASH_FRAGMENT_2(elem_hash)];
242 2275 : c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = elem;
243 2275 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
244 : } else {
245 : /* not there: replace oldest */
246 2337 : elem_to_unref = c->entries_elems[HASH_FRAGMENT_3(elem_hash)];
247 2337 : c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = elem;
248 2337 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
249 : }
250 :
251 : /* do exactly the same for the key (so we can find by that again too) */
252 :
253 37664 : if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == elem->key) {
254 2104 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
255 35560 : } else if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == elem->key) {
256 261 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
257 35299 : } else if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == NULL) {
258 30672 : c->entries_keys[HASH_FRAGMENT_2(key_hash)] = GRPC_MDSTR_REF(elem->key);
259 30672 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
260 4627 : } else if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == NULL) {
261 1237 : c->entries_keys[HASH_FRAGMENT_3(key_hash)] = GRPC_MDSTR_REF(elem->key);
262 1237 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
263 6780 : } else if (c->indices_keys[HASH_FRAGMENT_2(key_hash)] <
264 3390 : c->indices_keys[HASH_FRAGMENT_3(key_hash)]) {
265 1667 : GRPC_MDSTR_UNREF(c->entries_keys[HASH_FRAGMENT_2(key_hash)]);
266 1667 : c->entries_keys[HASH_FRAGMENT_2(key_hash)] = GRPC_MDSTR_REF(elem->key);
267 1667 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
268 : } else {
269 1723 : GRPC_MDSTR_UNREF(c->entries_keys[HASH_FRAGMENT_3(key_hash)]);
270 1723 : c->entries_keys[HASH_FRAGMENT_3(key_hash)] = GRPC_MDSTR_REF(elem->key);
271 1723 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
272 : }
273 :
274 37664 : return elem_to_unref;
275 : }
276 :
277 19052585 : static void emit_indexed(grpc_chttp2_hpack_compressor *c, gpr_uint32 elem_index,
278 : framer_state *st) {
279 19052585 : gpr_uint32 len = GRPC_CHTTP2_VARINT_LENGTH(elem_index, 1);
280 19052585 : GRPC_CHTTP2_WRITE_VARINT(elem_index, 1, 0x80, add_tiny_header_data(st, len),
281 : len);
282 19066235 : }
283 :
284 137866 : static gpr_slice get_wire_value(grpc_mdelem *elem, gpr_uint8 *huffman_prefix) {
285 275732 : if (grpc_is_binary_header((const char *)GPR_SLICE_START_PTR(elem->key->slice),
286 275732 : GPR_SLICE_LENGTH(elem->key->slice))) {
287 110 : *huffman_prefix = 0x80;
288 110 : return grpc_mdstr_as_base64_encoded_and_huffman_compressed(elem->value);
289 : }
290 : /* TODO(ctiller): opportunistically compress non-binary headers */
291 137756 : *huffman_prefix = 0x00;
292 137756 : return elem->value->slice;
293 : }
294 :
295 2191 : static void emit_lithdr_incidx(grpc_chttp2_hpack_compressor *c,
296 : gpr_uint32 key_index, grpc_mdelem *elem,
297 : framer_state *st) {
298 2191 : gpr_uint32 len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 2);
299 : gpr_uint8 huffman_prefix;
300 2191 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
301 2191 : size_t len_val = GPR_SLICE_LENGTH(value_slice);
302 : gpr_uint32 len_val_len;
303 2191 : GPR_ASSERT(len_val <= GPR_UINT32_MAX);
304 2191 : len_val_len = GRPC_CHTTP2_VARINT_LENGTH((gpr_uint32)len_val, 1);
305 2191 : GRPC_CHTTP2_WRITE_VARINT(key_index, 2, 0x40,
306 : add_tiny_header_data(st, len_pfx), len_pfx);
307 2191 : GRPC_CHTTP2_WRITE_VARINT((gpr_uint32)len_val, 1, 0x00,
308 : add_tiny_header_data(st, len_val_len), len_val_len);
309 2191 : add_header_data(st, gpr_slice_ref(value_slice));
310 2191 : }
311 :
312 15634 : static void emit_lithdr_noidx(grpc_chttp2_hpack_compressor *c,
313 : gpr_uint32 key_index, grpc_mdelem *elem,
314 : framer_state *st) {
315 15634 : gpr_uint32 len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 4);
316 : gpr_uint8 huffman_prefix;
317 15634 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
318 15634 : size_t len_val = GPR_SLICE_LENGTH(value_slice);
319 : gpr_uint32 len_val_len;
320 15634 : GPR_ASSERT(len_val <= GPR_UINT32_MAX);
321 15634 : len_val_len = GRPC_CHTTP2_VARINT_LENGTH((gpr_uint32)len_val, 1);
322 15634 : GRPC_CHTTP2_WRITE_VARINT(key_index, 4, 0x00,
323 : add_tiny_header_data(st, len_pfx), len_pfx);
324 15634 : GRPC_CHTTP2_WRITE_VARINT((gpr_uint32)len_val, 1, 0x00,
325 : add_tiny_header_data(st, len_val_len), len_val_len);
326 15634 : add_header_data(st, gpr_slice_ref(value_slice));
327 15634 : }
328 :
329 35473 : static void emit_lithdr_incidx_v(grpc_chttp2_hpack_compressor *c,
330 : grpc_mdelem *elem, framer_state *st) {
331 35473 : gpr_uint32 len_key = (gpr_uint32)GPR_SLICE_LENGTH(elem->key->slice);
332 : gpr_uint8 huffman_prefix;
333 35473 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
334 35473 : gpr_uint32 len_val = (gpr_uint32)GPR_SLICE_LENGTH(value_slice);
335 35473 : gpr_uint32 len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
336 35473 : gpr_uint32 len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
337 : GPR_ASSERT(len_key <= GPR_UINT32_MAX);
338 35473 : GPR_ASSERT(GPR_SLICE_LENGTH(value_slice) <= GPR_UINT32_MAX);
339 35473 : *add_tiny_header_data(st, 1) = 0x40;
340 35473 : GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
341 : add_tiny_header_data(st, len_key_len), len_key_len);
342 35473 : add_header_data(st, gpr_slice_ref(elem->key->slice));
343 35473 : GRPC_CHTTP2_WRITE_VARINT(len_val, 1, huffman_prefix,
344 : add_tiny_header_data(st, len_val_len), len_val_len);
345 35473 : add_header_data(st, gpr_slice_ref(value_slice));
346 35473 : }
347 :
348 84568 : static void emit_lithdr_noidx_v(grpc_chttp2_hpack_compressor *c,
349 : grpc_mdelem *elem, framer_state *st) {
350 84568 : gpr_uint32 len_key = (gpr_uint32)GPR_SLICE_LENGTH(elem->key->slice);
351 : gpr_uint8 huffman_prefix;
352 84568 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
353 84568 : gpr_uint32 len_val = (gpr_uint32)GPR_SLICE_LENGTH(value_slice);
354 84568 : gpr_uint32 len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
355 84568 : gpr_uint32 len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
356 : GPR_ASSERT(len_key <= GPR_UINT32_MAX);
357 84568 : GPR_ASSERT(GPR_SLICE_LENGTH(value_slice) <= GPR_UINT32_MAX);
358 84568 : *add_tiny_header_data(st, 1) = 0x00;
359 84568 : GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
360 : add_tiny_header_data(st, len_key_len), len_key_len);
361 84568 : add_header_data(st, gpr_slice_ref(elem->key->slice));
362 84568 : GRPC_CHTTP2_WRITE_VARINT(len_val, 1, huffman_prefix,
363 : add_tiny_header_data(st, len_val_len), len_val_len);
364 84568 : add_header_data(st, gpr_slice_ref(value_slice));
365 84568 : }
366 :
367 19085612 : static gpr_uint32 dynidx(grpc_chttp2_hpack_compressor *c,
368 : gpr_uint32 elem_index) {
369 57256836 : return 1 + GRPC_CHTTP2_LAST_STATIC_ENTRY + c->tail_remote_index +
370 38171224 : c->table_elems - elem_index;
371 : }
372 :
373 : /* encode an mdelem; returns metadata element to unref */
374 19221143 : static grpc_mdelem *hpack_enc(grpc_chttp2_hpack_compressor *c,
375 : grpc_mdelem *elem, framer_state *st) {
376 19221143 : gpr_uint32 key_hash = elem->key->hash;
377 19221143 : gpr_uint32 elem_hash = GRPC_MDSTR_KV_HASH(key_hash, elem->value->hash);
378 : size_t decoder_space_usage;
379 : gpr_uint32 indices_key;
380 : int should_add_elem;
381 :
382 19221143 : GPR_ASSERT(GPR_SLICE_LENGTH(elem->key->slice) > 0);
383 19221143 : if (GPR_SLICE_START_PTR(elem->key->slice)[0] != ':') { /* regular header */
384 12321207 : st->seen_regular_header = 1;
385 6899936 : } else if (st->seen_regular_header != 0) { /* reserved header */
386 0 : gpr_log(GPR_ERROR,
387 : "Reserved header (colon-prefixed) happening after regular ones.");
388 0 : abort();
389 : }
390 :
391 19221143 : inc_filter(HASH_FRAGMENT_1(elem_hash), &c->filter_elems_sum, c->filter_elems);
392 :
393 : /* is this elem currently in the decoders table? */
394 :
395 38163691 : if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == elem &&
396 18952727 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] > c->tail_remote_index) {
397 : /* HIT: complete element (first cuckoo hash) */
398 18962355 : emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_2(elem_hash)]),
399 : st);
400 18953954 : return elem;
401 : }
402 :
403 360249 : if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == elem &&
404 111640 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] > c->tail_remote_index) {
405 : /* HIT: complete element (second cuckoo hash) */
406 110743 : emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_3(elem_hash)]),
407 : st);
408 110743 : return elem;
409 : }
410 :
411 : /* should this elem be in the table? */
412 275732 : decoder_space_usage = 32 + GPR_SLICE_LENGTH(elem->key->slice) +
413 137866 : GPR_SLICE_LENGTH(elem->value->slice);
414 275706 : should_add_elem = decoder_space_usage < MAX_DECODER_SPACE_USAGE &&
415 137840 : c->filter_elems[HASH_FRAGMENT_1(elem_hash)] >=
416 137840 : c->filter_elems_sum / ONE_ON_ADD_PROBABILITY;
417 :
418 : /* no hits for the elem... maybe there's a key? */
419 :
420 137866 : indices_key = c->indices_keys[HASH_FRAGMENT_2(key_hash)];
421 154321 : if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == elem->key &&
422 16455 : indices_key > c->tail_remote_index) {
423 : /* HIT: key (first cuckoo hash) */
424 14407 : if (should_add_elem) {
425 1979 : emit_lithdr_incidx(c, dynidx(c, indices_key), elem, st);
426 1979 : return add_elem(c, elem);
427 : } else {
428 12428 : emit_lithdr_noidx(c, dynidx(c, indices_key), elem, st);
429 12428 : return elem;
430 : }
431 : GPR_UNREACHABLE_CODE(return NULL);
432 : }
433 :
434 123459 : indices_key = c->indices_keys[HASH_FRAGMENT_3(key_hash)];
435 128300 : if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == elem->key &&
436 4841 : indices_key > c->tail_remote_index) {
437 : /* HIT: key (first cuckoo hash) */
438 3418 : if (should_add_elem) {
439 212 : emit_lithdr_incidx(c, dynidx(c, indices_key), elem, st);
440 212 : return add_elem(c, elem);
441 : } else {
442 3206 : emit_lithdr_noidx(c, dynidx(c, indices_key), elem, st);
443 3206 : return elem;
444 : }
445 : GPR_UNREACHABLE_CODE(return NULL);
446 : }
447 :
448 : /* no elem, key in the table... fall back to literal emission */
449 :
450 120041 : if (should_add_elem) {
451 35473 : emit_lithdr_incidx_v(c, elem, st);
452 35473 : return add_elem(c, elem);
453 : } else {
454 84568 : emit_lithdr_noidx_v(c, elem, st);
455 84568 : return elem;
456 : }
457 : GPR_UNREACHABLE_CODE(return NULL);
458 : }
459 :
460 : #define STRLEN_LIT(x) (sizeof(x) - 1)
461 : #define TIMEOUT_KEY "grpc-timeout"
462 :
463 5272 : static void deadline_enc(grpc_chttp2_hpack_compressor *c, gpr_timespec deadline,
464 : framer_state *st) {
465 : char timeout_str[GRPC_CHTTP2_TIMEOUT_ENCODE_MIN_BUFSIZE];
466 : grpc_mdelem *mdelem;
467 5272 : grpc_chttp2_encode_timeout(
468 : gpr_time_sub(deadline, gpr_now(deadline.clock_type)), timeout_str);
469 5272 : mdelem = grpc_mdelem_from_metadata_strings(
470 : c->mdctx, GRPC_MDSTR_REF(c->timeout_key_str),
471 : grpc_mdstr_from_string(c->mdctx, timeout_str));
472 5272 : mdelem = hpack_enc(c, mdelem, st);
473 5272 : if (mdelem) GRPC_MDELEM_UNREF(mdelem);
474 5272 : }
475 :
476 0 : gpr_slice grpc_chttp2_data_frame_create_empty_close(gpr_uint32 id) {
477 0 : gpr_slice slice = gpr_slice_malloc(9);
478 0 : fill_header(GPR_SLICE_START_PTR(slice), GRPC_CHTTP2_FRAME_DATA, id, 0, 1);
479 0 : return slice;
480 : }
481 :
482 4026 : void grpc_chttp2_hpack_compressor_init(grpc_chttp2_hpack_compressor *c,
483 : grpc_mdctx *ctx) {
484 4026 : memset(c, 0, sizeof(*c));
485 4026 : c->mdctx = ctx;
486 4026 : c->timeout_key_str = grpc_mdstr_from_string(ctx, "grpc-timeout");
487 4028 : }
488 :
489 4020 : void grpc_chttp2_hpack_compressor_destroy(grpc_chttp2_hpack_compressor *c) {
490 : int i;
491 1035045 : for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
492 1031017 : if (c->entries_keys[i]) GRPC_MDSTR_UNREF(c->entries_keys[i]);
493 1031021 : if (c->entries_elems[i]) GRPC_MDELEM_UNREF(c->entries_elems[i]);
494 : }
495 4028 : GRPC_MDSTR_UNREF(c->timeout_key_str);
496 4028 : }
497 :
498 3175104 : gpr_uint32 grpc_chttp2_preencode(grpc_stream_op *inops, size_t *inops_count,
499 : gpr_uint32 max_flow_controlled_bytes,
500 : grpc_stream_op_buffer *outops) {
501 : gpr_slice slice;
502 : grpc_stream_op *op;
503 : gpr_uint32 max_take_size;
504 3175104 : gpr_uint32 flow_controlled_bytes_taken = 0;
505 3175104 : gpr_uint32 curop = 0;
506 : gpr_uint8 *p;
507 3175104 : gpr_uint8 compressed_flag_set = 0;
508 :
509 16470040 : while (curop < *inops_count) {
510 10181647 : GPR_ASSERT(flow_controlled_bytes_taken <= max_flow_controlled_bytes);
511 10183564 : op = &inops[curop];
512 10183564 : switch (op->type) {
513 : case GRPC_NO_OP:
514 : /* skip */
515 1 : curop++;
516 1 : break;
517 : case GRPC_OP_METADATA:
518 4113988 : grpc_metadata_batch_assert_ok(&op->data.metadata);
519 : /* these just get copied as they don't impact the number of flow
520 : controlled bytes */
521 4113314 : grpc_sopb_append(outops, op, 1);
522 4113956 : curop++;
523 4113956 : break;
524 : case GRPC_OP_BEGIN_MESSAGE:
525 : /* begin op: for now we just convert the op to a slice and fall
526 : through - this lets us reuse the slice framing code below */
527 3000562 : compressed_flag_set =
528 3000562 : (op->data.begin_message.flags & GRPC_WRITE_INTERNAL_COMPRESS) != 0;
529 3000562 : slice = gpr_slice_malloc(5);
530 :
531 3001619 : p = GPR_SLICE_START_PTR(slice);
532 3001619 : p[0] = compressed_flag_set;
533 3001619 : p[1] = (gpr_uint8)(op->data.begin_message.length >> 24);
534 3001619 : p[2] = (gpr_uint8)(op->data.begin_message.length >> 16);
535 3001619 : p[3] = (gpr_uint8)(op->data.begin_message.length >> 8);
536 3001619 : p[4] = (gpr_uint8)(op->data.begin_message.length);
537 3001619 : op->type = GRPC_OP_SLICE;
538 3001619 : op->data.slice = slice;
539 : /* fallthrough */
540 : case GRPC_OP_SLICE:
541 6079007 : slice = op->data.slice;
542 6079007 : if (!GPR_SLICE_LENGTH(slice)) {
543 : /* skip zero length slices */
544 10 : gpr_slice_unref(slice);
545 10 : curop++;
546 10 : break;
547 : }
548 6078997 : max_take_size = max_flow_controlled_bytes - flow_controlled_bytes_taken;
549 6078997 : if (max_take_size == 0) {
550 64335 : goto exit_loop;
551 : }
552 6014662 : if (GPR_SLICE_LENGTH(slice) > max_take_size) {
553 13603 : slice = gpr_slice_split_head(&op->data.slice, max_take_size);
554 13603 : grpc_sopb_add_slice(outops, slice);
555 : } else {
556 : /* consume this op immediately */
557 6001059 : grpc_sopb_append(outops, op, 1);
558 6000521 : curop++;
559 : }
560 6014240 : flow_controlled_bytes_taken += (gpr_uint32)GPR_SLICE_LENGTH(slice);
561 6014240 : break;
562 : }
563 : }
564 : exit_loop:
565 3177624 : *inops_count -= curop;
566 3177624 : memmove(inops, inops + curop, *inops_count * sizeof(grpc_stream_op));
567 :
568 3243968 : for (curop = 0; curop < *inops_count; curop++) {
569 66344 : if (inops[curop].type == GRPC_OP_METADATA) {
570 47 : grpc_metadata_batch_assert_ok(&inops[curop].data.metadata);
571 : }
572 : }
573 :
574 3177624 : return flow_controlled_bytes_taken;
575 : }
576 :
577 3127144 : void grpc_chttp2_encode(grpc_stream_op *ops, size_t ops_count, int eof,
578 : gpr_uint32 stream_id,
579 : grpc_chttp2_hpack_compressor *compressor,
580 : gpr_slice_buffer *output) {
581 : framer_state st;
582 : gpr_slice slice;
583 : grpc_stream_op *op;
584 : size_t max_take_size;
585 3127144 : gpr_uint32 curop = 0;
586 : gpr_uint32 unref_op;
587 3127144 : grpc_mdctx *mdctx = compressor->mdctx;
588 : grpc_linked_mdelem *l;
589 3127144 : int need_unref = 0;
590 : gpr_timespec deadline;
591 :
592 3127144 : GPR_ASSERT(stream_id != 0);
593 :
594 3127144 : st.cur_frame_type = NONE;
595 3127144 : st.last_was_header = 0;
596 3127144 : st.seen_regular_header = 0;
597 3127144 : st.stream_id = stream_id;
598 3127144 : st.output = output;
599 :
600 16376410 : while (curop < ops_count) {
601 10119171 : op = &ops[curop];
602 10119171 : switch (op->type) {
603 : case GRPC_NO_OP:
604 : case GRPC_OP_BEGIN_MESSAGE:
605 0 : gpr_log(
606 : GPR_ERROR,
607 : "These stream ops should be filtered out by grpc_chttp2_preencode");
608 0 : abort();
609 : case GRPC_OP_METADATA:
610 : /* Encode a metadata batch; store the returned values, representing
611 : a metadata element that needs to be unreffed back into the metadata
612 : slot. THIS MAY NOT BE THE SAME ELEMENT (if a decoder table slot got
613 : updated). After this loop, we'll do a batch unref of elements. */
614 4112443 : begin_new_frame(&st, HEADER);
615 4116384 : need_unref |= op->data.metadata.garbage.head != NULL;
616 4116384 : grpc_metadata_batch_assert_ok(&op->data.metadata);
617 23289568 : for (l = op->data.metadata.list.head; l; l = l->next) {
618 19174514 : l->md = hpack_enc(compressor, l->md, &st);
619 19201336 : need_unref |= l->md != NULL;
620 : }
621 4115054 : deadline = op->data.metadata.deadline;
622 4115054 : if (gpr_time_cmp(deadline, gpr_inf_future(deadline.clock_type)) != 0) {
623 5272 : deadline_enc(compressor, deadline, &st);
624 : }
625 4116737 : curop++;
626 4116737 : break;
627 : case GRPC_OP_SLICE:
628 6018209 : slice = op->data.slice;
629 9024572 : if (st.cur_frame_type == DATA &&
630 3006363 : st.output->length - st.output_length_at_start_of_frame ==
631 : GRPC_CHTTP2_MAX_PAYLOAD_LENGTH) {
632 3271 : finish_frame(&st, 0, 0);
633 : }
634 6018209 : ensure_frame_type(&st, DATA, 1);
635 6015757 : max_take_size = GRPC_CHTTP2_MAX_PAYLOAD_LENGTH +
636 6015757 : st.output_length_at_start_of_frame - st.output->length;
637 6015757 : if (GPR_SLICE_LENGTH(slice) > max_take_size) {
638 3202 : slice = gpr_slice_split_head(&op->data.slice, max_take_size);
639 : } else {
640 : /* consume this op immediately */
641 6012555 : curop++;
642 : }
643 6015757 : gpr_slice_buffer_add(output, slice);
644 6016866 : break;
645 : }
646 : }
647 3130095 : if (eof && st.cur_frame_type == NONE) {
648 512 : begin_frame(&st, DATA);
649 : }
650 3130095 : finish_frame(&st, 1, eof);
651 :
652 3130855 : if (need_unref) {
653 2807605 : grpc_mdctx_lock(mdctx);
654 12312264 : for (unref_op = 0; unref_op < curop; unref_op++) {
655 9503661 : op = &ops[unref_op];
656 9503661 : if (op->type != GRPC_OP_METADATA) continue;
657 23293729 : for (l = op->data.metadata.list.head; l; l = l->next) {
658 19185744 : if (l->md) GRPC_MDCTX_LOCKED_MDELEM_UNREF(mdctx, l->md);
659 : }
660 4108740 : for (l = op->data.metadata.garbage.head; l; l = l->next) {
661 755 : GRPC_MDCTX_LOCKED_MDELEM_UNREF(mdctx, l->md);
662 : }
663 : }
664 2808603 : grpc_mdctx_unlock(mdctx);
665 : }
666 3132534 : }
|
