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/hpack_encoder.h"
35 :
36 : #include <assert.h>
37 : #include <string.h>
38 :
39 : #include <grpc/support/alloc.h>
40 : #include <grpc/support/log.h>
41 : #include <grpc/support/useful.h>
42 :
43 : #include "src/core/transport/chttp2/bin_encoder.h"
44 : #include "src/core/transport/chttp2/hpack_table.h"
45 : #include "src/core/transport/chttp2/timeout_encoding.h"
46 : #include "src/core/transport/chttp2/varint.h"
47 : #include "src/core/transport/static_metadata.h"
48 :
49 : #define HASH_FRAGMENT_1(x) ((x)&255)
50 : #define HASH_FRAGMENT_2(x) ((x >> 8) & 255)
51 : #define HASH_FRAGMENT_3(x) ((x >> 16) & 255)
52 : #define HASH_FRAGMENT_4(x) ((x >> 24) & 255)
53 :
54 : /* if the probability of this item being seen again is < 1/x then don't add
55 : it to the table */
56 : #define ONE_ON_ADD_PROBABILITY 128
57 : /* don't consider adding anything bigger than this to the hpack table */
58 : #define MAX_DECODER_SPACE_USAGE 512
59 :
60 : typedef struct {
61 : int is_first_frame;
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 : /* have we seen a regular (non-colon-prefixed) header yet? */
68 : gpr_uint8 seen_regular_header;
69 : /* output stream id */
70 : gpr_uint32 stream_id;
71 : gpr_slice_buffer *output;
72 : } framer_state;
73 :
74 : /* fills p (which is expected to be 9 bytes long) with a data frame header */
75 6614210 : static void fill_header(gpr_uint8 *p, gpr_uint8 type, gpr_uint32 id, size_t len,
76 : gpr_uint8 flags) {
77 6614210 : GPR_ASSERT(len < 16777316);
78 6614210 : *p++ = (gpr_uint8)(len >> 16);
79 6614210 : *p++ = (gpr_uint8)(len >> 8);
80 6614210 : *p++ = (gpr_uint8)(len);
81 6614210 : *p++ = type;
82 6614210 : *p++ = flags;
83 6614210 : *p++ = (gpr_uint8)(id >> 24);
84 6614210 : *p++ = (gpr_uint8)(id >> 16);
85 6614210 : *p++ = (gpr_uint8)(id >> 8);
86 6614210 : *p++ = (gpr_uint8)(id);
87 6614210 : }
88 :
89 : /* finish a frame - fill in the previously reserved header */
90 6614336 : static void finish_frame(framer_state *st, int is_header_boundary,
91 : int is_last_in_stream) {
92 6614101 : gpr_uint8 type = 0xff;
93 6614336 : type = st->is_first_frame ? GRPC_CHTTP2_FRAME_HEADER
94 : : GRPC_CHTTP2_FRAME_CONTINUATION;
95 26457109 : fill_header(
96 13228437 : GPR_SLICE_START_PTR(st->output->slices[st->header_idx]), type,
97 6614336 : st->stream_id, st->output->length - st->output_length_at_start_of_frame,
98 6614336 : (gpr_uint8)(
99 : (is_last_in_stream ? GRPC_CHTTP2_DATA_FLAG_END_STREAM : 0) |
100 : (is_header_boundary ? GRPC_CHTTP2_DATA_FLAG_END_HEADERS : 0)));
101 6614242 : st->is_first_frame = 0;
102 6614242 : }
103 :
104 : /* begin a new frame: reserve off header space, remember how many bytes we'd
105 : output before beginning */
106 6604929 : static void begin_frame(framer_state *st) {
107 6613634 : st->header_idx =
108 6604929 : gpr_slice_buffer_add_indexed(st->output, gpr_slice_malloc(9));
109 6613634 : st->output_length_at_start_of_frame = st->output->length;
110 6613634 : }
111 :
112 : /* make sure that the current frame is of the type desired, and has sufficient
113 : space to add at least about_to_add bytes -- finishes the current frame if
114 : needed */
115 42204152 : static void ensure_space(framer_state *st, size_t need_bytes) {
116 42204152 : if (st->output->length - st->output_length_at_start_of_frame + need_bytes <=
117 : GRPC_CHTTP2_MAX_PAYLOAD_LENGTH) {
118 84405902 : return;
119 : }
120 0 : finish_frame(st, 0, 0);
121 0 : begin_frame(st);
122 : }
123 :
124 : /* increment a filter count, halve all counts if one element reaches max */
125 34135559 : static void inc_filter(gpr_uint8 idx, gpr_uint32 *sum, gpr_uint8 *elems) {
126 34135559 : elems[idx]++;
127 34135559 : if (elems[idx] < 255) {
128 34102070 : (*sum)++;
129 : } else {
130 : int i;
131 33489 : *sum = 0;
132 8606205 : for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_FILTERS; i++) {
133 8572716 : elems[i] /= 2;
134 8572716 : (*sum) += elems[i];
135 : }
136 : }
137 34135559 : }
138 :
139 8040472 : static void add_header_data(framer_state *st, gpr_slice slice) {
140 8040472 : size_t len = GPR_SLICE_LENGTH(slice);
141 : size_t remaining;
142 16080944 : if (len == 0) return;
143 8040436 : remaining = GRPC_CHTTP2_MAX_PAYLOAD_LENGTH +
144 8040436 : st->output_length_at_start_of_frame - st->output->length;
145 8040436 : if (len <= remaining) {
146 8040324 : gpr_slice_buffer_add(st->output, slice);
147 : } else {
148 112 : gpr_slice_buffer_add(st->output, gpr_slice_split_head(&slice, remaining));
149 112 : finish_frame(st, 0, 0);
150 112 : begin_frame(st);
151 112 : add_header_data(st, slice);
152 : }
153 : }
154 :
155 42192155 : static gpr_uint8 *add_tiny_header_data(framer_state *st, size_t len) {
156 42192155 : ensure_space(st, len);
157 42201827 : return gpr_slice_buffer_tiny_add(st->output, len);
158 : }
159 :
160 1605797 : static void evict_entry(grpc_chttp2_hpack_compressor *c) {
161 1605797 : c->tail_remote_index++;
162 1605797 : GPR_ASSERT(c->tail_remote_index > 0);
163 1605797 : GPR_ASSERT(c->table_size >=
164 : c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
165 1605797 : GPR_ASSERT(c->table_elems > 0);
166 3211594 : c->table_size = (gpr_uint16)(
167 1605797 : c->table_size -
168 1605797 : c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
169 1605797 : c->table_elems--;
170 1605797 : }
171 :
172 : /* add an element to the decoder table */
173 3524961 : static void add_elem(grpc_chttp2_hpack_compressor *c, grpc_mdelem *elem) {
174 3524961 : gpr_uint32 key_hash = elem->key->hash;
175 3524961 : gpr_uint32 elem_hash = GRPC_MDSTR_KV_HASH(key_hash, elem->value->hash);
176 3524961 : gpr_uint32 new_index = c->tail_remote_index + c->table_elems + 1;
177 7049922 : size_t elem_size = 32 + GPR_SLICE_LENGTH(elem->key->slice) +
178 3524961 : GPR_SLICE_LENGTH(elem->value->slice);
179 :
180 3524961 : GPR_ASSERT(elem_size < 65536);
181 :
182 3524961 : if (elem_size > c->max_table_size) {
183 3736304 : while (c->table_size > 0) {
184 0 : evict_entry(c);
185 : }
186 5393113 : return;
187 : }
188 :
189 : /* Reserve space for this element in the remote table: if this overflows
190 : the current table, drop elements until it fits, matching the decompressor
191 : algorithm */
192 4917466 : while (c->table_size + elem_size > c->max_table_size) {
193 1604400 : evict_entry(c);
194 : }
195 1656809 : GPR_ASSERT(c->table_elems < c->max_table_size);
196 1656809 : c->table_elem_size[new_index % c->cap_table_elems] = (gpr_uint16)elem_size;
197 1656809 : c->table_size = (gpr_uint16)(c->table_size + elem_size);
198 1656809 : c->table_elems++;
199 :
200 : /* Store this element into {entries,indices}_elem */
201 1656809 : if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == elem) {
202 : /* already there: update with new index */
203 1522101 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
204 134708 : } else if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == elem) {
205 : /* already there (cuckoo): update with new index */
206 67008 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
207 67700 : } else if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == NULL) {
208 : /* not there, but a free element: add */
209 63510 : c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = GRPC_MDELEM_REF(elem);
210 63510 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
211 4190 : } else if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == NULL) {
212 : /* not there (cuckoo), but a free element: add */
213 3545 : c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = GRPC_MDELEM_REF(elem);
214 3545 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
215 1290 : } else if (c->indices_elems[HASH_FRAGMENT_2(elem_hash)] <
216 645 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)]) {
217 : /* not there: replace oldest */
218 304 : GRPC_MDELEM_UNREF(c->entries_elems[HASH_FRAGMENT_2(elem_hash)]);
219 304 : c->entries_elems[HASH_FRAGMENT_2(elem_hash)] = GRPC_MDELEM_REF(elem);
220 304 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] = new_index;
221 : } else {
222 : /* not there: replace oldest */
223 341 : GRPC_MDELEM_UNREF(c->entries_elems[HASH_FRAGMENT_3(elem_hash)]);
224 341 : c->entries_elems[HASH_FRAGMENT_3(elem_hash)] = GRPC_MDELEM_REF(elem);
225 341 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] = new_index;
226 : }
227 :
228 : /* do exactly the same for the key (so we can find by that again too) */
229 :
230 1656809 : if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == elem->key) {
231 1583316 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
232 73493 : } else if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == elem->key) {
233 28691 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
234 44802 : } else if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == NULL) {
235 44008 : c->entries_keys[HASH_FRAGMENT_2(key_hash)] = GRPC_MDSTR_REF(elem->key);
236 44008 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
237 794 : } else if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == NULL) {
238 734 : c->entries_keys[HASH_FRAGMENT_3(key_hash)] = GRPC_MDSTR_REF(elem->key);
239 734 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
240 120 : } else if (c->indices_keys[HASH_FRAGMENT_2(key_hash)] <
241 60 : c->indices_keys[HASH_FRAGMENT_3(key_hash)]) {
242 29 : GRPC_MDSTR_UNREF(c->entries_keys[HASH_FRAGMENT_2(key_hash)]);
243 29 : c->entries_keys[HASH_FRAGMENT_2(key_hash)] = GRPC_MDSTR_REF(elem->key);
244 29 : c->indices_keys[HASH_FRAGMENT_2(key_hash)] = new_index;
245 : } else {
246 31 : GRPC_MDSTR_UNREF(c->entries_keys[HASH_FRAGMENT_3(key_hash)]);
247 31 : c->entries_keys[HASH_FRAGMENT_3(key_hash)] = GRPC_MDSTR_REF(elem->key);
248 31 : c->indices_keys[HASH_FRAGMENT_3(key_hash)] = new_index;
249 : }
250 : }
251 :
252 29952261 : static void emit_indexed(grpc_chttp2_hpack_compressor *c, gpr_uint32 elem_index,
253 : framer_state *st) {
254 29952261 : gpr_uint32 len = GRPC_CHTTP2_VARINT_LENGTH(elem_index, 1);
255 29952261 : GRPC_CHTTP2_WRITE_VARINT(elem_index, 1, 0x80, add_tiny_header_data(st, len),
256 : len);
257 29989910 : }
258 :
259 4166290 : static gpr_slice get_wire_value(grpc_mdelem *elem, gpr_uint8 *huffman_prefix) {
260 8332045 : if (grpc_is_binary_header((const char *)GPR_SLICE_START_PTR(elem->key->slice),
261 8332045 : GPR_SLICE_LENGTH(elem->key->slice))) {
262 126 : *huffman_prefix = 0x80;
263 126 : return grpc_mdstr_as_base64_encoded_and_huffman_compressed(elem->value);
264 : }
265 : /* TODO(ctiller): opportunistically compress non-binary headers */
266 4166164 : *huffman_prefix = 0x00;
267 4166164 : return elem->value->slice;
268 : }
269 :
270 44565 : static void emit_lithdr_incidx(grpc_chttp2_hpack_compressor *c,
271 : gpr_uint32 key_index, grpc_mdelem *elem,
272 : framer_state *st) {
273 44565 : gpr_uint32 len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 2);
274 : gpr_uint8 huffman_prefix;
275 44565 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
276 44565 : size_t len_val = GPR_SLICE_LENGTH(value_slice);
277 : gpr_uint32 len_val_len;
278 44565 : GPR_ASSERT(len_val <= GPR_UINT32_MAX);
279 44565 : len_val_len = GRPC_CHTTP2_VARINT_LENGTH((gpr_uint32)len_val, 1);
280 44565 : GRPC_CHTTP2_WRITE_VARINT(key_index, 2, 0x40,
281 : add_tiny_header_data(st, len_pfx), len_pfx);
282 44565 : GRPC_CHTTP2_WRITE_VARINT((gpr_uint32)len_val, 1, 0x00,
283 : add_tiny_header_data(st, len_val_len), len_val_len);
284 44565 : add_header_data(st, gpr_slice_ref(value_slice));
285 44565 : }
286 :
287 247655 : static void emit_lithdr_noidx(grpc_chttp2_hpack_compressor *c,
288 : gpr_uint32 key_index, grpc_mdelem *elem,
289 : framer_state *st) {
290 247655 : gpr_uint32 len_pfx = GRPC_CHTTP2_VARINT_LENGTH(key_index, 4);
291 : gpr_uint8 huffman_prefix;
292 247655 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
293 247655 : size_t len_val = GPR_SLICE_LENGTH(value_slice);
294 : gpr_uint32 len_val_len;
295 247655 : GPR_ASSERT(len_val <= GPR_UINT32_MAX);
296 247655 : len_val_len = GRPC_CHTTP2_VARINT_LENGTH((gpr_uint32)len_val, 1);
297 247655 : GRPC_CHTTP2_WRITE_VARINT(key_index, 4, 0x00,
298 : add_tiny_header_data(st, len_pfx), len_pfx);
299 247655 : GRPC_CHTTP2_WRITE_VARINT((gpr_uint32)len_val, 1, 0x00,
300 : add_tiny_header_data(st, len_val_len), len_val_len);
301 247655 : add_header_data(st, gpr_slice_ref(value_slice));
302 247655 : }
303 :
304 3480396 : static void emit_lithdr_incidx_v(grpc_chttp2_hpack_compressor *c,
305 : grpc_mdelem *elem, framer_state *st) {
306 3480396 : gpr_uint32 len_key = (gpr_uint32)GPR_SLICE_LENGTH(elem->key->slice);
307 : gpr_uint8 huffman_prefix;
308 3480396 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
309 3480396 : gpr_uint32 len_val = (gpr_uint32)GPR_SLICE_LENGTH(value_slice);
310 3480396 : gpr_uint32 len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
311 3480396 : gpr_uint32 len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
312 : GPR_ASSERT(len_key <= GPR_UINT32_MAX);
313 3480396 : GPR_ASSERT(GPR_SLICE_LENGTH(value_slice) <= GPR_UINT32_MAX);
314 3480396 : *add_tiny_header_data(st, 1) = 0x40;
315 3480396 : GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
316 : add_tiny_header_data(st, len_key_len), len_key_len);
317 3480396 : add_header_data(st, gpr_slice_ref(elem->key->slice));
318 3480396 : GRPC_CHTTP2_WRITE_VARINT(len_val, 1, huffman_prefix,
319 : add_tiny_header_data(st, len_val_len), len_val_len);
320 3480396 : add_header_data(st, gpr_slice_ref(value_slice));
321 3480396 : }
322 :
323 393674 : static void emit_lithdr_noidx_v(grpc_chttp2_hpack_compressor *c,
324 : grpc_mdelem *elem, framer_state *st) {
325 393674 : gpr_uint32 len_key = (gpr_uint32)GPR_SLICE_LENGTH(elem->key->slice);
326 : gpr_uint8 huffman_prefix;
327 393674 : gpr_slice value_slice = get_wire_value(elem, &huffman_prefix);
328 393674 : gpr_uint32 len_val = (gpr_uint32)GPR_SLICE_LENGTH(value_slice);
329 393674 : gpr_uint32 len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
330 393674 : gpr_uint32 len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
331 : GPR_ASSERT(len_key <= GPR_UINT32_MAX);
332 393674 : GPR_ASSERT(GPR_SLICE_LENGTH(value_slice) <= GPR_UINT32_MAX);
333 393674 : *add_tiny_header_data(st, 1) = 0x00;
334 393674 : GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00,
335 : add_tiny_header_data(st, len_key_len), len_key_len);
336 393674 : add_header_data(st, gpr_slice_ref(elem->key->slice));
337 393674 : GRPC_CHTTP2_WRITE_VARINT(len_val, 1, huffman_prefix,
338 : add_tiny_header_data(st, len_val_len), len_val_len);
339 393674 : add_header_data(st, gpr_slice_ref(value_slice));
340 393674 : }
341 :
342 666 : static void emit_advertise_table_size_change(grpc_chttp2_hpack_compressor *c,
343 : framer_state *st) {
344 666 : gpr_uint32 len = GRPC_CHTTP2_VARINT_LENGTH(c->max_table_size, 3);
345 666 : GRPC_CHTTP2_WRITE_VARINT(c->max_table_size, 3, 0x20,
346 : add_tiny_header_data(st, len), len);
347 666 : c->advertise_table_size_change = 0;
348 666 : }
349 :
350 30268727 : static gpr_uint32 dynidx(grpc_chttp2_hpack_compressor *c,
351 : gpr_uint32 elem_index) {
352 90807805 : return 1 + GRPC_CHTTP2_LAST_STATIC_ENTRY + c->tail_remote_index +
353 60538266 : c->table_elems - elem_index;
354 : }
355 :
356 : /* encode an mdelem */
357 34187561 : static void hpack_enc(grpc_chttp2_hpack_compressor *c, grpc_mdelem *elem,
358 : framer_state *st) {
359 34187561 : gpr_uint32 key_hash = elem->key->hash;
360 34187561 : gpr_uint32 elem_hash = GRPC_MDSTR_KV_HASH(key_hash, elem->value->hash);
361 : size_t decoder_space_usage;
362 : gpr_uint32 indices_key;
363 : int should_add_elem;
364 :
365 34187561 : GPR_ASSERT(GPR_SLICE_LENGTH(elem->key->slice) > 0);
366 34187561 : if (GPR_SLICE_START_PTR(elem->key->slice)[0] != ':') { /* regular header */
367 22958853 : st->seen_regular_header = 1;
368 11228708 : } else if (st->seen_regular_header != 0) { /* reserved header */
369 0 : gpr_log(GPR_ERROR,
370 : "Reserved header (colon-prefixed) happening after regular ones.");
371 0 : abort();
372 : }
373 :
374 34187561 : inc_filter(HASH_FRAGMENT_1(elem_hash), &c->filter_elems_sum, c->filter_elems);
375 :
376 : /* is this elem currently in the decoders table? */
377 :
378 65999950 : if (c->entries_elems[HASH_FRAGMENT_2(elem_hash)] == elem &&
379 31844752 : c->indices_elems[HASH_FRAGMENT_2(elem_hash)] > c->tail_remote_index) {
380 : /* HIT: complete element (first cuckoo hash) */
381 29747152 : emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_2(elem_hash)]),
382 : st);
383 29750873 : return;
384 : }
385 :
386 4734083 : if (c->entries_elems[HASH_FRAGMENT_3(elem_hash)] == elem &&
387 326037 : c->indices_elems[HASH_FRAGMENT_3(elem_hash)] > c->tail_remote_index) {
388 : /* HIT: complete element (second cuckoo hash) */
389 241756 : emit_indexed(c, dynidx(c, c->indices_elems[HASH_FRAGMENT_3(elem_hash)]),
390 : st);
391 241756 : return;
392 : }
393 :
394 : /* should this elem be in the table? */
395 8332580 : decoder_space_usage = 32 + GPR_SLICE_LENGTH(elem->key->slice) +
396 4166290 : GPR_SLICE_LENGTH(elem->value->slice);
397 8332552 : should_add_elem = decoder_space_usage < MAX_DECODER_SPACE_USAGE &&
398 4166262 : c->filter_elems[HASH_FRAGMENT_1(elem_hash)] >=
399 4166262 : c->filter_elems_sum / ONE_ON_ADD_PROBABILITY;
400 :
401 : /* no hits for the elem... maybe there's a key? */
402 :
403 4166290 : indices_key = c->indices_keys[HASH_FRAGMENT_2(key_hash)];
404 6811847 : if (c->entries_keys[HASH_FRAGMENT_2(key_hash)] == elem->key &&
405 2645557 : indices_key > c->tail_remote_index) {
406 : /* HIT: key (first cuckoo hash) */
407 281315 : if (should_add_elem) {
408 43061 : emit_lithdr_incidx(c, dynidx(c, indices_key), elem, st);
409 43061 : add_elem(c, elem);
410 43061 : return;
411 : } else {
412 238254 : emit_lithdr_noidx(c, dynidx(c, indices_key), elem, st);
413 238254 : return;
414 : }
415 : GPR_UNREACHABLE_CODE(return );
416 : }
417 :
418 3884975 : indices_key = c->indices_keys[HASH_FRAGMENT_3(key_hash)];
419 3953583 : if (c->entries_keys[HASH_FRAGMENT_3(key_hash)] == elem->key &&
420 68608 : indices_key > c->tail_remote_index) {
421 : /* HIT: key (first cuckoo hash) */
422 10905 : if (should_add_elem) {
423 1504 : emit_lithdr_incidx(c, dynidx(c, indices_key), elem, st);
424 1504 : add_elem(c, elem);
425 1504 : return;
426 : } else {
427 9401 : emit_lithdr_noidx(c, dynidx(c, indices_key), elem, st);
428 9401 : return;
429 : }
430 : GPR_UNREACHABLE_CODE(return );
431 : }
432 :
433 : /* no elem, key in the table... fall back to literal emission */
434 :
435 3874070 : if (should_add_elem) {
436 3480396 : emit_lithdr_incidx_v(c, elem, st);
437 3480396 : add_elem(c, elem);
438 3480396 : return;
439 : } else {
440 393674 : emit_lithdr_noidx_v(c, elem, st);
441 393674 : return;
442 : }
443 : GPR_UNREACHABLE_CODE(return );
444 : }
445 :
446 : #define STRLEN_LIT(x) (sizeof(x) - 1)
447 : #define TIMEOUT_KEY "grpc-timeout"
448 :
449 1048119 : static void deadline_enc(grpc_chttp2_hpack_compressor *c, gpr_timespec deadline,
450 : framer_state *st) {
451 : char timeout_str[GRPC_CHTTP2_TIMEOUT_ENCODE_MIN_BUFSIZE];
452 : grpc_mdelem *mdelem;
453 1048119 : grpc_chttp2_encode_timeout(
454 : gpr_time_sub(deadline, gpr_now(deadline.clock_type)), timeout_str);
455 1048119 : mdelem = grpc_mdelem_from_metadata_strings(
456 : GRPC_MDSTR_GRPC_TIMEOUT, grpc_mdstr_from_string(timeout_str));
457 1048119 : hpack_enc(c, mdelem, st);
458 1048119 : GRPC_MDELEM_UNREF(mdelem);
459 1048119 : }
460 :
461 6636 : static gpr_uint32 elems_for_bytes(gpr_uint32 bytes) {
462 6636 : return (bytes + 31) / 32;
463 : }
464 :
465 6039 : void grpc_chttp2_hpack_compressor_init(grpc_chttp2_hpack_compressor *c) {
466 6039 : memset(c, 0, sizeof(*c));
467 6039 : c->max_table_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
468 6039 : c->cap_table_elems = elems_for_bytes(c->max_table_size);
469 6038 : c->max_table_elems = c->cap_table_elems;
470 6038 : c->max_usable_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
471 6039 : c->table_elem_size =
472 6038 : gpr_malloc(sizeof(*c->table_elem_size) * c->cap_table_elems);
473 6039 : memset(c->table_elem_size, 0,
474 6039 : sizeof(*c->table_elem_size) * c->cap_table_elems);
475 6039 : }
476 :
477 5963 : void grpc_chttp2_hpack_compressor_destroy(grpc_chttp2_hpack_compressor *c) {
478 : int i;
479 1531902 : for (i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
480 1525936 : if (c->entries_keys[i]) GRPC_MDSTR_UNREF(c->entries_keys[i]);
481 1525938 : if (c->entries_elems[i]) GRPC_MDELEM_UNREF(c->entries_elems[i]);
482 : }
483 5966 : gpr_free(c->table_elem_size);
484 5966 : }
485 :
486 600 : void grpc_chttp2_hpack_compressor_set_max_usable_size(
487 : grpc_chttp2_hpack_compressor *c, gpr_uint32 max_table_size) {
488 600 : c->max_usable_size = max_table_size;
489 600 : grpc_chttp2_hpack_compressor_set_max_table_size(
490 600 : c, GPR_MIN(c->max_table_size, max_table_size));
491 600 : }
492 :
493 660 : static void rebuild_elems(grpc_chttp2_hpack_compressor *c, gpr_uint32 new_cap) {
494 660 : gpr_uint16 *table_elem_size = gpr_malloc(sizeof(*table_elem_size) * new_cap);
495 : gpr_uint32 i;
496 :
497 660 : memset(table_elem_size, 0, sizeof(*table_elem_size) * new_cap);
498 660 : GPR_ASSERT(c->table_elems <= new_cap);
499 :
500 1944 : for (i = 0; i < c->table_elems; i++) {
501 1284 : gpr_uint32 ofs = c->tail_remote_index + i + 1;
502 2568 : table_elem_size[ofs % new_cap] =
503 1284 : c->table_elem_size[ofs % c->cap_table_elems];
504 : }
505 :
506 660 : c->cap_table_elems = new_cap;
507 660 : gpr_free(c->table_elem_size);
508 660 : c->table_elem_size = table_elem_size;
509 660 : }
510 :
511 34900881 : void grpc_chttp2_hpack_compressor_set_max_table_size(
512 : grpc_chttp2_hpack_compressor *c, gpr_uint32 max_table_size) {
513 34900881 : max_table_size = GPR_MIN(max_table_size, c->max_usable_size);
514 34900881 : if (max_table_size == c->max_table_size) {
515 69798380 : return;
516 : }
517 2757 : while (c->table_size > 0 && c->table_size > max_table_size) {
518 1397 : evict_entry(c);
519 : }
520 680 : c->max_table_size = max_table_size;
521 680 : c->max_table_elems = elems_for_bytes(max_table_size);
522 680 : if (c->max_table_elems > c->cap_table_elems) {
523 80 : rebuild_elems(c, GPR_MAX(c->max_table_elems, 2 * c->cap_table_elems));
524 600 : } else if (c->max_table_elems < c->cap_table_elems / 3) {
525 600 : gpr_uint32 new_cap = GPR_MAX(c->max_table_elems, 16);
526 600 : if (new_cap != c->cap_table_elems) {
527 580 : rebuild_elems(c, new_cap);
528 : }
529 : }
530 680 : c->advertise_table_size_change = 1;
531 680 : gpr_log(GPR_DEBUG, "set max table size from encoder to %d", max_table_size);
532 : }
533 :
534 6595229 : void grpc_chttp2_encode_header(grpc_chttp2_hpack_compressor *c,
535 : gpr_uint32 stream_id,
536 : grpc_metadata_batch *metadata, int is_eof,
537 : gpr_slice_buffer *outbuf) {
538 : framer_state st;
539 : grpc_linked_mdelem *l;
540 : gpr_timespec deadline;
541 :
542 6595229 : GPR_ASSERT(stream_id != 0);
543 :
544 6595229 : st.seen_regular_header = 0;
545 6595229 : st.stream_id = stream_id;
546 6595229 : st.output = outbuf;
547 6595229 : st.is_first_frame = 1;
548 :
549 : /* Encode a metadata batch; store the returned values, representing
550 : a metadata element that needs to be unreffed back into the metadata
551 : slot. THIS MAY NOT BE THE SAME ELEMENT (if a decoder table slot got
552 : updated). After this loop, we'll do a batch unref of elements. */
553 6595229 : begin_frame(&st);
554 6613575 : if (c->advertise_table_size_change != 0) {
555 666 : emit_advertise_table_size_change(c, &st);
556 : }
557 6613575 : grpc_metadata_batch_assert_ok(metadata);
558 39695904 : for (l = metadata->list.head; l; l = l->next) {
559 33087462 : hpack_enc(c, l->md, &st);
560 : }
561 6608442 : deadline = metadata->deadline;
562 6608442 : if (gpr_time_cmp(deadline, gpr_inf_future(deadline.clock_type)) != 0) {
563 1048119 : deadline_enc(c, deadline, &st);
564 : }
565 :
566 6614222 : finish_frame(&st, 1, is_eof);
567 6613444 : }
|
