src/core/ext/transport/chttp2/transport/hpack_encoder.cc

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