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