OpenHarmony-v3.2.1-Release/s

/*
 *
 * Copyright 2015 gRPC authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */

#include <grpc/support/port_platform.h>

#include "src/core/ext/transport/chttp2/transport/hpack_encoder.h"

#include <assert.h>
#include <string.h>

/* This is here for grpc_is_binary_header
 * TODO(murgatroid99): Remove this
 */
#include <grpc/grpc.h>

#include <grpc/support/alloc.h>
#include <grpc/support/log.h>

#include "src/core/ext/transport/chttp2/transport/bin_encoder.h"
#include "src/core/ext/transport/chttp2/transport/hpack_table.h"
#include "src/core/ext/transport/chttp2/transport/varint.h"
#include "src/core/lib/debug/stats.h"
#include "src/core/lib/slice/slice_internal.h"
#include "src/core/lib/slice/slice_string_helpers.h"
#include "src/core/lib/surface/validate_metadata.h"
#include "src/core/lib/transport/metadata.h"
#include "src/core/lib/transport/static_metadata.h"
#include "src/core/lib/transport/timeout_encoding.h"

namespace {
/* (Maybe-cuckoo) hpack encoder hash table implementation.

   This hashtable implementation is a subset of a proper cuckoo hash; while we
   have fallback cells that a value can be hashed to if the first cell is full,
   we do not attempt to iteratively rearrange entries into backup cells to get
   things to fit. Instead, if both a cell and the backup cell for a value are
   occupied, the older existing entry is evicted.

   Note that we can disable backup-cell picking by setting
   GRPC_HPACK_ENCODER_USE_CUCKOO_HASH to 0. In that case, we simply evict an
   existing entry rather than try to use a backup. Hence, "maybe-cuckoo."
   TODO(arjunroy): Add unit tests for hashtable implementation. */
#define GRPC_HPACK_ENCODER_USE_CUCKOO_HASH 1
#define HASH_FRAGMENT_MASK (GRPC_CHTTP2_HPACKC_NUM_VALUES - 1)
#define HASH_FRAGMENT_1(x) ((x)&HASH_FRAGMENT_MASK)
#define HASH_FRAGMENT_2(x) \
  (((x) >> GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS) & HASH_FRAGMENT_MASK)
#define HASH_FRAGMENT_3(x) \
  (((x) >> (GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS * 2)) & HASH_FRAGMENT_MASK)
#define HASH_FRAGMENT_4(x) \
  (((x) >> (GRPC_CHTTP2_HPACKC_NUM_VALUES_BITS * 3)) & HASH_FRAGMENT_MASK)

/* don't consider adding anything bigger than this to the hpack table */
constexpr size_t kMaxDecoderSpaceUsage = 512;
constexpr size_t kDataFrameHeaderSize = 9;
constexpr uint8_t kMaxFilterValue = 255;

/* if the probability of this item being seen again is < 1/x then don't add
   it to the table */
#define ONE_ON_ADD_PROBABILITY (GRPC_CHTTP2_HPACKC_NUM_VALUES >> 1)
/* The hpack index we encode over the wire. Meaningful to the hpack encoder and
   parser on the remote end as well as HTTP2. *Not* the same as
   HpackEncoderSlotHash, which is only meaningful to the hpack encoder
   implementation (HpackEncoderSlotHash is used for the hashtable implementation
   when mapping from metadata to HpackEncoderIndex. */
typedef uint32_t HpackEncoderIndex;
/* Internal-table bookkeeping (*not* the hpack index). */
typedef uint32_t HpackEncoderSlotHash;

struct SliceRefComparator {
  typedef grpc_slice_refcount* Type;
  static grpc_slice_refcount* Null() { return nullptr; }
  static bool IsNull(const grpc_slice_refcount* sref) {
    return sref == nullptr;
  }
  static bool Equals(const grpc_slice_refcount* s1,
                     const grpc_slice_refcount* s2) {
    return s1 == s2;
  }
  static void Ref(grpc_slice_refcount* sref) {
    GPR_DEBUG_ASSERT(sref != nullptr);
    sref->Ref();
  }
  static void Unref(grpc_slice_refcount* sref) {
    GPR_DEBUG_ASSERT(sref != nullptr);
    sref->Unref();
  }
};

struct MetadataComparator {
  typedef grpc_mdelem Type;
  static const grpc_mdelem Null() { return {0}; }
  static bool IsNull(const grpc_mdelem md) { return md.payload == 0; }
  static bool Equals(const grpc_mdelem md1, const grpc_mdelem md2) {
    return md1.payload == md2.payload;
  }
  static void Ref(grpc_mdelem md) {
    GPR_DEBUG_ASSERT(md.payload != 0);
    GRPC_MDELEM_REF(md);
  }
  static void Unref(grpc_mdelem md) {
    GPR_DEBUG_ASSERT(md.payload != 0);
    GRPC_MDELEM_UNREF(md);
  }
};

/* Index table management */
template <typename Hashtable>
static HpackEncoderIndex HpackIndex(const Hashtable* hashtable,
                                    HpackEncoderSlotHash hash_index) {
  return hashtable[hash_index].index;
}

template <typename ValueType, typename Hashtable>
static const ValueType& GetEntry(const Hashtable* hashtable,
                                 HpackEncoderSlotHash hash_index) {
  return hashtable[hash_index].value;
}

template <typename Cmp, typename Hashtable>
static bool TableEmptyAt(const Hashtable* hashtable,
                         HpackEncoderSlotHash hash_index) {
  return Cmp::Equals(hashtable[hash_index].value, Cmp::Null());
}

template <typename Cmp, typename Hashtable, typename ValueType>
static bool Matches(const Hashtable* hashtable, const ValueType& value,
                    HpackEncoderSlotHash hash_index) {
  return Cmp::Equals(value, hashtable[hash_index].value);
}

template <typename Hashtable>
static void UpdateIndex(Hashtable* hashtable, HpackEncoderSlotHash hash_index,
                        HpackEncoderIndex hpack_index) {
  hashtable[hash_index].index = hpack_index;
}

template <typename Hashtable, typename ValueType>
static void SetIndex(Hashtable* hashtable, HpackEncoderSlotHash hash_index,
                     const ValueType& value, HpackEncoderIndex hpack_index) {
  hashtable[hash_index].value = value;
  UpdateIndex(hashtable, hash_index, hpack_index);
}

template <typename Cmp, typename Hashtable, typename ValueType>
static bool GetMatchingIndex(Hashtable* hashtable, const ValueType& value,
                             uint32_t value_hash, HpackEncoderIndex* index) {
  const HpackEncoderSlotHash cuckoo_first = HASH_FRAGMENT_2(value_hash);
  if (Matches<Cmp>(hashtable, value, cuckoo_first)) {
    *index = HpackIndex(hashtable, cuckoo_first);
    return true;
  }
#if GRPC_HPACK_ENCODER_USE_CUCKOO_HASH
  const HpackEncoderSlotHash cuckoo_second = HASH_FRAGMENT_3(value_hash);

  if (Matches<Cmp>(hashtable, value, cuckoo_second)) {
    *index = HpackIndex(hashtable, cuckoo_second);
    return true;
  }
#endif
  return false;
}

template <typename Cmp, typename Hashtable, typename ValueType>
static ValueType ReplaceOlderIndex(Hashtable* hashtable, const ValueType& value,
                                   HpackEncoderSlotHash hash_index_a,
                                   HpackEncoderSlotHash hash_index_b,
                                   HpackEncoderIndex new_index) {
  const HpackEncoderIndex hpack_idx_a = hashtable[hash_index_a].index;
  const HpackEncoderIndex hpack_idx_b = hashtable[hash_index_b].index;
  const HpackEncoderSlotHash id =
      hpack_idx_a < hpack_idx_b ? hash_index_a : hash_index_b;
  ValueType old = GetEntry<typename Cmp::Type>(hashtable, id);
  SetIndex(hashtable, id, value, new_index);
  return old;
}

template <typename Cmp, typename Hashtable, typename ValueType>
static void UpdateAddOrEvict(Hashtable hashtable, const ValueType& value,
                             uint32_t value_hash, HpackEncoderIndex new_index) {
  const HpackEncoderSlotHash cuckoo_first = HASH_FRAGMENT_2(value_hash);
  if (Matches<Cmp>(hashtable, value, cuckoo_first)) {
    UpdateIndex(hashtable, cuckoo_first, new_index);
    return;
  }
  if (TableEmptyAt<Cmp>(hashtable, cuckoo_first)) {
    Cmp::Ref(value);
    SetIndex(hashtable, cuckoo_first, value, new_index);
    return;
  }
#if GRPC_HPACK_ENCODER_USE_CUCKOO_HASH
  const HpackEncoderSlotHash cuckoo_second = HASH_FRAGMENT_3(value_hash);
  if (Matches<Cmp>(hashtable, value, cuckoo_second)) {
    UpdateIndex(hashtable, cuckoo_second, new_index);
    return;
  }
  Cmp::Ref(value);
  if (TableEmptyAt<Cmp>(hashtable, cuckoo_second)) {
    SetIndex(hashtable, cuckoo_second, value, new_index);
    return;
  }
  Cmp::Unref(ReplaceOlderIndex<Cmp>(hashtable, value, cuckoo_first,
                                    cuckoo_second, new_index));
#else
  ValueType old = GetEntry<typename Cmp::Type>(hashtable, cuckoo_first);
  SetIndex(hashtable, cuckoo_first, value, new_index);
  Cmp::Unref(old);
#endif
}

/* halve all counts because an element reached max */
static void HalveFilter(uint8_t /*idx*/, uint32_t* sum, uint8_t* elems) {
  *sum = 0;
  for (int i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
    elems[i] /= 2;
    (*sum) += elems[i];
  }
}

/* increment a filter count, halve all counts if one element reaches max */
static void IncrementFilter(uint8_t idx, uint32_t* sum, uint8_t* elems) {
  elems[idx]++;
  if (GPR_LIKELY(elems[idx] < kMaxFilterValue)) {
    (*sum)++;
  } else {
    HalveFilter(idx, sum, elems);
  }
}

static uint32_t UpdateHashtablePopularity(
    grpc_chttp2_hpack_compressor* hpack_compressor, uint32_t elem_hash) {
  const uint32_t popularity_hash = HASH_FRAGMENT_1(elem_hash);
  IncrementFilter(popularity_hash, &hpack_compressor->filter_elems_sum,
                  hpack_compressor->filter_elems);
  return popularity_hash;
}

static bool CanAddToHashtable(grpc_chttp2_hpack_compressor* hpack_compressor,
                              uint32_t popularity_hash) {
  const bool can_add =
      hpack_compressor->filter_elems[popularity_hash] >=
      hpack_compressor->filter_elems_sum / ONE_ON_ADD_PROBABILITY;
  return can_add;
}
} /* namespace */

struct framer_state {
  int is_first_frame;
  /* number of bytes in 'output' when we started the frame - used to calculate
     frame length */
  size_t output_length_at_start_of_frame;
  /* index (in output) of the header for the current frame */
  size_t header_idx;
#ifndef NDEBUG
  /* have we seen a regular (non-colon-prefixed) header yet? */
  uint8_t seen_regular_header;
#endif
  /* output stream id */
  uint32_t stream_id;
  grpc_slice_buffer* output;
  grpc_transport_one_way_stats* stats;
  /* maximum size of a frame */
  size_t max_frame_size;
  bool use_true_binary_metadata;
  bool is_end_of_stream;
};
/* fills p (which is expected to be kDataFrameHeaderSize bytes long)
 * with a data frame header */
static void fill_header(uint8_t* p, uint8_t type, uint32_t id, size_t len,
                        uint8_t flags) {
  /* len is the current frame size (i.e. for the frame we're finishing).
     We finish a frame if:
     1) We called ensure_space(), (i.e. add_tiny_header_data()) and adding
        'need_bytes' to the frame would cause us to exceed st->max_frame_size.
     2) We called add_header_data, and adding the slice would cause us to exceed
        st->max_frame_size.
     3) We're done encoding the header.

     Thus, len is always <= st->max_frame_size.
     st->max_frame_size is derived from GRPC_CHTTP2_SETTINGS_MAX_FRAME_SIZE,
     which has a max allowable value of 16777215 (see chttp_transport.cc).
     Thus, the following assert can be a debug assert. */
  GPR_DEBUG_ASSERT(len < 16777316);
  *p++ = static_cast<uint8_t>(len >> 16);
  *p++ = static_cast<uint8_t>(len >> 8);
  *p++ = static_cast<uint8_t>(len);
  *p++ = type;
  *p++ = flags;
  *p++ = static_cast<uint8_t>(id >> 24);
  *p++ = static_cast<uint8_t>(id >> 16);
  *p++ = static_cast<uint8_t>(id >> 8);
  *p++ = static_cast<uint8_t>(id);
}

static size_t current_frame_size(framer_state* st) {
  const size_t frame_size =
      st->output->length - st->output_length_at_start_of_frame;
  GPR_DEBUG_ASSERT(frame_size <= st->max_frame_size);
  return frame_size;
}

/* finish a frame - fill in the previously reserved header */
static void finish_frame(framer_state* st, int is_header_boundary) {
  uint8_t type = 0xff;
  type =
      static_cast<uint8_t>(st->is_first_frame ? GRPC_CHTTP2_FRAME_HEADER
                                              : GRPC_CHTTP2_FRAME_CONTINUATION);
  uint8_t flags = 0xff;
  /* per the HTTP/2 spec:
       A HEADERS frame carries the END_STREAM flag that signals the end of a
       stream. However, a HEADERS frame with the END_STREAM flag set can be
       followed by CONTINUATION frames on the same stream. Logically, the
       CONTINUATION frames are part of the HEADERS frame.
     Thus, we add the END_STREAM flag to the HEADER frame (the first frame). */
  flags = static_cast<uint8_t>(st->is_first_frame && st->is_end_of_stream
                                   ? GRPC_CHTTP2_DATA_FLAG_END_STREAM
                                   : 0);
  /* per the HTTP/2 spec:
       A HEADERS frame without the END_HEADERS flag set MUST be followed by
       a CONTINUATION frame for the same stream.
     Thus, we add the END_HEADER flag to the last frame. */
  flags |= static_cast<uint8_t>(
      is_header_boundary ? GRPC_CHTTP2_DATA_FLAG_END_HEADERS : 0);
  fill_header(GRPC_SLICE_START_PTR(st->output->slices[st->header_idx]), type,
              st->stream_id, current_frame_size(st), flags);
  st->stats->framing_bytes += kDataFrameHeaderSize;
  st->is_first_frame = 0;
}

/* begin a new frame: reserve off header space, remember how many bytes we'd
   output before beginning */
static void begin_frame(framer_state* st) {
  grpc_slice reserved;
  reserved.refcount = nullptr;
  reserved.data.inlined.length = kDataFrameHeaderSize;
  st->header_idx = grpc_slice_buffer_add_indexed(st->output, reserved);
  st->output_length_at_start_of_frame = st->output->length;
}

/* make sure that the current frame is of the type desired, and has sufficient
   space to add at least about_to_add bytes -- finishes the current frame if
   needed */
static void ensure_space(framer_state* st, size_t need_bytes) {
  if (GPR_LIKELY(current_frame_size(st) + need_bytes <= st->max_frame_size)) {
    return;
  }
  finish_frame(st, 0);
  begin_frame(st);
}

static void add_header_data(framer_state* st, grpc_slice slice) {
  size_t len = GRPC_SLICE_LENGTH(slice);
  size_t remaining;
  if (len == 0) return;
  remaining = st->max_frame_size - current_frame_size(st);
  if (len <= remaining) {
    st->stats->header_bytes += len;
    grpc_slice_buffer_add(st->output, slice);
  } else {
    st->stats->header_bytes += remaining;
    grpc_slice_buffer_add(st->output, grpc_slice_split_head(&slice, remaining));
    finish_frame(st, 0);
    begin_frame(st);
    add_header_data(st, slice);
  }
}

static uint8_t* add_tiny_header_data(framer_state* st, size_t len) {
  ensure_space(st, len);
  st->stats->header_bytes += len;
  return grpc_slice_buffer_tiny_add(st->output, len);
}

static void evict_entry(grpc_chttp2_hpack_compressor* c) {
  c->tail_remote_index++;
  GPR_ASSERT(c->tail_remote_index > 0);
  GPR_ASSERT(c->table_size >=
             c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
  GPR_ASSERT(c->table_elems > 0);
  c->table_size = static_cast<uint16_t>(
      c->table_size -
      c->table_elem_size[c->tail_remote_index % c->cap_table_elems]);
  c->table_elems--;
}

// Reserve space in table for the new element, evict entries if needed.
// Return the new index of the element. Return 0 to indicate not adding to
// table.
static uint32_t prepare_space_for_new_elem(grpc_chttp2_hpack_compressor* c,
                                           size_t elem_size) {
  uint32_t new_index = c->tail_remote_index + c->table_elems + 1;
  GPR_DEBUG_ASSERT(elem_size < 65536);

  // TODO(arjunroy): Re-examine semantics
  if (elem_size > c->max_table_size) {
    while (c->table_size > 0) {
      evict_entry(c);
    }
    return 0;
  }

  /* Reserve space for this element in the remote table: if this overflows
     the current table, drop elements until it fits, matching the decompressor
     algorithm */
  while (c->table_size + elem_size > c->max_table_size) {
    evict_entry(c);
  }
  GPR_ASSERT(c->table_elems < c->max_table_size);
  c->table_elem_size[new_index % c->cap_table_elems] =
      static_cast<uint16_t>(elem_size);
  c->table_size = static_cast<uint16_t>(c->table_size + elem_size);
  c->table_elems++;

  return new_index;
}

// Add a key to the dynamic table. Both key and value will be added to table at
// the decoder.
static void AddKeyWithIndex(grpc_chttp2_hpack_compressor* c,
                            grpc_slice_refcount* key_ref, uint32_t new_index,
                            uint32_t key_hash) {
  UpdateAddOrEvict<SliceRefComparator>(c->key_table.entries, key_ref, key_hash,
                                       new_index);
}

/* add an element to the decoder table */
static void AddElemWithIndex(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
                             uint32_t new_index, uint32_t elem_hash,
                             uint32_t key_hash) {
  GPR_DEBUG_ASSERT(GRPC_MDELEM_IS_INTERNED(elem));
  UpdateAddOrEvict<MetadataComparator>(c->elem_table.entries, elem, elem_hash,
                                       new_index);
  AddKeyWithIndex(c, GRPC_MDKEY(elem).refcount, new_index, key_hash);
}

static void add_elem(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
                     size_t elem_size, uint32_t elem_hash, uint32_t key_hash) {
  uint32_t new_index = prepare_space_for_new_elem(c, elem_size);
  if (new_index != 0) {
    AddElemWithIndex(c, elem, new_index, elem_hash, key_hash);
  }
}

static void add_key(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
                    size_t elem_size, uint32_t key_hash) {
  uint32_t new_index = prepare_space_for_new_elem(c, elem_size);
  if (new_index != 0) {
    AddKeyWithIndex(c, GRPC_MDKEY(elem).refcount, new_index, key_hash);
  }
}

static void emit_indexed(grpc_chttp2_hpack_compressor* /*c*/,
                         uint32_t elem_index, framer_state* st) {
  GRPC_STATS_INC_HPACK_SEND_INDEXED();
  uint32_t len = GRPC_CHTTP2_VARINT_LENGTH(elem_index, 1);
  GRPC_CHTTP2_WRITE_VARINT(elem_index, 1, 0x80, add_tiny_header_data(st, len),
                           len);
}

struct wire_value {
  wire_value(uint8_t huffman_prefix, bool insert_null_before_wire_value,
             const grpc_slice& slice)
      : data(slice),
        huffman_prefix(huffman_prefix),
        insert_null_before_wire_value(insert_null_before_wire_value),
        length(GRPC_SLICE_LENGTH(slice) +
               (insert_null_before_wire_value ? 1 : 0)) {}
  // While wire_value is const from the POV of hpack encoder code, actually
  // adding it to a slice buffer will possibly split the slice.
  const grpc_slice data;
  const uint8_t huffman_prefix;
  const bool insert_null_before_wire_value;
  const size_t length;
};

template <bool mdkey_definitely_interned>
static wire_value get_wire_value(grpc_mdelem elem, bool true_binary_enabled) {
  const bool is_bin_hdr =
      mdkey_definitely_interned
          ? grpc_is_refcounted_slice_binary_header(GRPC_MDKEY(elem))
          : grpc_is_binary_header_internal(GRPC_MDKEY(elem));
  const grpc_slice& value = GRPC_MDVALUE(elem);
  if (is_bin_hdr) {
    if (true_binary_enabled) {
      GRPC_STATS_INC_HPACK_SEND_BINARY();
      return wire_value(0x00, true, grpc_slice_ref_internal(value));
    } else {
      GRPC_STATS_INC_HPACK_SEND_BINARY_BASE64();
      return wire_value(0x80, false,
                        grpc_chttp2_base64_encode_and_huffman_compress(value));
    }
  } else {
    /* TODO(ctiller): opportunistically compress non-binary headers */
    GRPC_STATS_INC_HPACK_SEND_UNCOMPRESSED();
    return wire_value(0x00, false, grpc_slice_ref_internal(value));
  }
}

static uint32_t wire_value_length(const wire_value& v) {
  GPR_DEBUG_ASSERT(v.length <= UINT32_MAX);
  return static_cast<uint32_t>(v.length);
}

namespace {
enum class EmitLitHdrType { INC_IDX, NO_IDX };

enum class EmitLitHdrVType { INC_IDX_V, NO_IDX_V };
}  // namespace

template <EmitLitHdrType type>
static void emit_lithdr(grpc_chttp2_hpack_compressor* /*c*/, uint32_t key_index,
                        grpc_mdelem elem, framer_state* st) {
  switch (type) {
    case EmitLitHdrType::INC_IDX:
      GRPC_STATS_INC_HPACK_SEND_LITHDR_INCIDX();
      break;
    case EmitLitHdrType::NO_IDX:
      GRPC_STATS_INC_HPACK_SEND_LITHDR_NOTIDX();
      break;
  }
  const uint32_t len_pfx = type == EmitLitHdrType::INC_IDX
                               ? GRPC_CHTTP2_VARINT_LENGTH(key_index, 2)
                               : GRPC_CHTTP2_VARINT_LENGTH(key_index, 4);
  const wire_value value =
      get_wire_value<true>(elem, st->use_true_binary_metadata);
  const uint32_t len_val = wire_value_length(value);
  const uint32_t len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
  GPR_DEBUG_ASSERT(len_pfx + len_val_len < GRPC_SLICE_INLINED_SIZE);
  uint8_t* data = add_tiny_header_data(
      st,
      len_pfx + len_val_len + (value.insert_null_before_wire_value ? 1 : 0));
  switch (type) {
    case EmitLitHdrType::INC_IDX:
      GRPC_CHTTP2_WRITE_VARINT(key_index, 2, 0x40, data, len_pfx);
      break;
    case EmitLitHdrType::NO_IDX:
      GRPC_CHTTP2_WRITE_VARINT(key_index, 4, 0x00, data, len_pfx);
      break;
  }
  GRPC_CHTTP2_WRITE_VARINT(len_val, 1, value.huffman_prefix, &data[len_pfx],
                           len_val_len);
  if (value.insert_null_before_wire_value) {
    data[len_pfx + len_val_len] = 0;
  }
  add_header_data(st, value.data);
}

template <EmitLitHdrVType type>
static void emit_lithdr_v(grpc_chttp2_hpack_compressor* /*c*/, grpc_mdelem elem,
                          framer_state* st) {
  switch (type) {
    case EmitLitHdrVType::INC_IDX_V:
      GRPC_STATS_INC_HPACK_SEND_LITHDR_INCIDX_V();
      break;
    case EmitLitHdrVType::NO_IDX_V:
      GRPC_STATS_INC_HPACK_SEND_LITHDR_NOTIDX_V();
      break;
  }
  GRPC_STATS_INC_HPACK_SEND_UNCOMPRESSED();
  const uint32_t len_key =
      static_cast<uint32_t>(GRPC_SLICE_LENGTH(GRPC_MDKEY(elem)));
  const wire_value value =
      type == EmitLitHdrVType::INC_IDX_V
          ? get_wire_value<true>(elem, st->use_true_binary_metadata)
          : get_wire_value<false>(elem, st->use_true_binary_metadata);
  const uint32_t len_val = wire_value_length(value);
  const uint32_t len_key_len = GRPC_CHTTP2_VARINT_LENGTH(len_key, 1);
  const uint32_t len_val_len = GRPC_CHTTP2_VARINT_LENGTH(len_val, 1);
  GPR_DEBUG_ASSERT(len_key <= UINT32_MAX);
  GPR_DEBUG_ASSERT(1 + len_key_len < GRPC_SLICE_INLINED_SIZE);
  uint8_t* key_buf = add_tiny_header_data(st, 1 + len_key_len);
  key_buf[0] = type == EmitLitHdrVType::INC_IDX_V ? 0x40 : 0x00;
  GRPC_CHTTP2_WRITE_VARINT(len_key, 1, 0x00, &key_buf[1], len_key_len);
  add_header_data(st, grpc_slice_ref_internal(GRPC_MDKEY(elem)));
  uint8_t* value_buf = add_tiny_header_data(
      st, len_val_len + (value.insert_null_before_wire_value ? 1 : 0));
  GRPC_CHTTP2_WRITE_VARINT(len_val, 1, value.huffman_prefix, value_buf,
                           len_val_len);
  if (value.insert_null_before_wire_value) {
    value_buf[len_val_len] = 0;
  }
  add_header_data(st, value.data);
}

static void emit_advertise_table_size_change(grpc_chttp2_hpack_compressor* c,
                                             framer_state* st) {
  uint32_t len = GRPC_CHTTP2_VARINT_LENGTH(c->max_table_size, 3);
  GRPC_CHTTP2_WRITE_VARINT(c->max_table_size, 3, 0x20,
                           add_tiny_header_data(st, len), len);
  c->advertise_table_size_change = 0;
}

static void GPR_ATTRIBUTE_NOINLINE hpack_enc_log(grpc_mdelem elem) {
  char* k = grpc_slice_to_c_string(GRPC_MDKEY(elem));
  char* v = nullptr;
  if (grpc_is_binary_header_internal(GRPC_MDKEY(elem))) {
    v = grpc_dump_slice(GRPC_MDVALUE(elem), GPR_DUMP_HEX);
  } else {
    v = grpc_slice_to_c_string(GRPC_MDVALUE(elem));
  }
  gpr_log(
      GPR_INFO,
      "Encode: '%s: %s', elem_interned=%d [%d], k_interned=%d, v_interned=%d",
      k, v, GRPC_MDELEM_IS_INTERNED(elem), GRPC_MDELEM_STORAGE(elem),
      grpc_slice_is_interned(GRPC_MDKEY(elem)),
      grpc_slice_is_interned(GRPC_MDVALUE(elem)));
  gpr_free(k);
  gpr_free(v);
}

static uint32_t dynidx(grpc_chttp2_hpack_compressor* c, uint32_t elem_index) {
  return 1 + GRPC_CHTTP2_LAST_STATIC_ENTRY + c->tail_remote_index +
         c->table_elems - elem_index;
}

struct EmitIndexedStatus {
  EmitIndexedStatus() = default;
  EmitIndexedStatus(uint32_t elem_hash, bool emitted, bool can_add)
      : elem_hash(elem_hash), emitted(emitted), can_add(can_add) {}
  const uint32_t elem_hash = 0;
  const bool emitted = false;
  const bool can_add = false;
};

static EmitIndexedStatus maybe_emit_indexed(grpc_chttp2_hpack_compressor* c,
                                            grpc_mdelem elem,
                                            framer_state* st) {
  const uint32_t elem_hash =
      GRPC_MDELEM_STORAGE(elem) == GRPC_MDELEM_STORAGE_INTERNED
          ? reinterpret_cast<grpc_core::InternedMetadata*>(
                GRPC_MDELEM_DATA(elem))
                ->hash()
          : reinterpret_cast<grpc_core::StaticMetadata*>(GRPC_MDELEM_DATA(elem))
                ->hash();
  /* Update filter to see if we can perhaps add this elem. */
  const uint32_t popularity_hash = UpdateHashtablePopularity(c, elem_hash);
  /* is this elem currently in the decoders table? */
  HpackEncoderIndex indices_key;
  if (GetMatchingIndex<MetadataComparator>(c->elem_table.entries, elem,
                                           elem_hash, &indices_key) &&
      indices_key > c->tail_remote_index) {
    emit_indexed(c, dynidx(c, indices_key), st);
    return EmitIndexedStatus(elem_hash, true, false);
  }
  /* Didn't hit either cuckoo index, so no emit. */
  return EmitIndexedStatus(elem_hash, false,
                           CanAddToHashtable(c, popularity_hash));
}

static void emit_maybe_add(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
                           framer_state* st, uint32_t indices_key,
                           bool should_add_elem, size_t decoder_space_usage,
                           uint32_t elem_hash, uint32_t key_hash) {
  if (should_add_elem) {
    emit_lithdr<EmitLitHdrType::INC_IDX>(c, dynidx(c, indices_key), elem, st);
    add_elem(c, elem, decoder_space_usage, elem_hash, key_hash);
  } else {
    emit_lithdr<EmitLitHdrType::NO_IDX>(c, dynidx(c, indices_key), elem, st);
  }
}

/* encode an mdelem */
static void hpack_enc(grpc_chttp2_hpack_compressor* c, grpc_mdelem elem,
                      framer_state* st) {
  const grpc_slice& elem_key = GRPC_MDKEY(elem);
  /* User-provided key len validated in grpc_validate_header_key_is_legal(). */
  GPR_DEBUG_ASSERT(GRPC_SLICE_LENGTH(elem_key) > 0);
  /* Header ordering: all reserved headers (prefixed with ':') must precede
   * regular headers. This can be a debug assert, since:
   * 1) User cannot give us ':' headers (grpc_validate_header_key_is_legal()).
   * 2) grpc filters/core should be checked during debug builds. */
#ifndef NDEBUG
  if (GRPC_SLICE_START_PTR(elem_key)[0] != ':') { /* regular header */
    st->seen_regular_header = 1;
  } else {
    GPR_DEBUG_ASSERT(
        st->seen_regular_header == 0 &&
        "Reserved header (colon-prefixed) happening after regular ones.");
  }
#endif
  if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
    hpack_enc_log(elem);
  }
  const bool elem_interned = GRPC_MDELEM_IS_INTERNED(elem);
  const bool key_interned = elem_interned || grpc_slice_is_interned(elem_key);
  /* Key is not interned, emit literals. */
  if (!key_interned) {
    emit_lithdr_v<EmitLitHdrVType::NO_IDX_V>(c, elem, st);
    return;
  }
  /* Interned metadata => maybe already indexed. */
  const EmitIndexedStatus ret =
      elem_interned ? maybe_emit_indexed(c, elem, st) : EmitIndexedStatus();
  if (ret.emitted) {
    return;
  }
  /* should this elem be in the table? */
  const size_t decoder_space_usage =
      grpc_chttp2_get_size_in_hpack_table(elem, st->use_true_binary_metadata);
  const bool decoder_space_available =
      decoder_space_usage < kMaxDecoderSpaceUsage;
  const bool should_add_elem =
      elem_interned && decoder_space_available && ret.can_add;
  const uint32_t elem_hash = ret.elem_hash;
  /* no hits for the elem... maybe there's a key? */
  const uint32_t key_hash = elem_key.refcount->Hash(elem_key);
  HpackEncoderIndex indices_key;
  if (GetMatchingIndex<SliceRefComparator>(
          c->key_table.entries, elem_key.refcount, key_hash, &indices_key) &&
      indices_key > c->tail_remote_index) {
    emit_maybe_add(c, elem, st, indices_key, should_add_elem,
                   decoder_space_usage, elem_hash, key_hash);
    return;
  }
  /* no elem, key in the table... fall back to literal emission */
  const bool should_add_key = !elem_interned && decoder_space_available;
  if (should_add_elem || should_add_key) {
    emit_lithdr_v<EmitLitHdrVType::INC_IDX_V>(c, elem, st);
  } else {
    emit_lithdr_v<EmitLitHdrVType::NO_IDX_V>(c, elem, st);
  }
  if (should_add_elem) {
    add_elem(c, elem, decoder_space_usage, elem_hash, key_hash);
  } else if (should_add_key) {
    add_key(c, elem, decoder_space_usage, key_hash);
  }
}

#define STRLEN_LIT(x) (sizeof(x) - 1)
#define TIMEOUT_KEY "grpc-timeout"

static void deadline_enc(grpc_chttp2_hpack_compressor* c, grpc_millis deadline,
                         framer_state* st) {
  char timeout_str[GRPC_HTTP2_TIMEOUT_ENCODE_MIN_BUFSIZE];
  grpc_mdelem mdelem;
  grpc_http2_encode_timeout(deadline - grpc_core::ExecCtx::Get()->Now(),
                            timeout_str);
  mdelem = grpc_mdelem_from_slices(
      GRPC_MDSTR_GRPC_TIMEOUT, grpc_core::UnmanagedMemorySlice(timeout_str));
  hpack_enc(c, mdelem, st);
  GRPC_MDELEM_UNREF(mdelem);
}

static uint32_t elems_for_bytes(uint32_t bytes) { return (bytes + 31) / 32; }

void grpc_chttp2_hpack_compressor_init(grpc_chttp2_hpack_compressor* c) {
  memset(c, 0, sizeof(*c));
  c->max_table_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
  c->cap_table_elems = elems_for_bytes(c->max_table_size);
  c->max_table_elems = c->cap_table_elems;
  c->max_usable_size = GRPC_CHTTP2_HPACKC_INITIAL_TABLE_SIZE;
  const size_t alloc_size = sizeof(*c->table_elem_size) * c->cap_table_elems;
  c->table_elem_size = static_cast<uint16_t*>(gpr_malloc(alloc_size));
  memset(c->table_elem_size, 0, alloc_size);
}

void grpc_chttp2_hpack_compressor_destroy(grpc_chttp2_hpack_compressor* c) {
  for (int i = 0; i < GRPC_CHTTP2_HPACKC_NUM_VALUES; i++) {
    auto* const key = GetEntry<grpc_slice_refcount*>(c->key_table.entries, i);
    if (key != nullptr) {
      key->Unref();
    }
    GRPC_MDELEM_UNREF(GetEntry<grpc_mdelem>(c->elem_table.entries, i));
  }
  gpr_free(c->table_elem_size);
}

void grpc_chttp2_hpack_compressor_set_max_usable_size(
    grpc_chttp2_hpack_compressor* c, uint32_t max_table_size) {
  c->max_usable_size = max_table_size;
  grpc_chttp2_hpack_compressor_set_max_table_size(
      c, GPR_MIN(c->max_table_size, max_table_size));
}

static void rebuild_elems(grpc_chttp2_hpack_compressor* c, uint32_t new_cap) {
  uint16_t* table_elem_size =
      static_cast<uint16_t*>(gpr_malloc(sizeof(*table_elem_size) * new_cap));
  uint32_t i;

  memset(table_elem_size, 0, sizeof(*table_elem_size) * new_cap);
  GPR_ASSERT(c->table_elems <= new_cap);

  for (i = 0; i < c->table_elems; i++) {
    uint32_t ofs = c->tail_remote_index + i + 1;
    table_elem_size[ofs % new_cap] =
        c->table_elem_size[ofs % c->cap_table_elems];
  }

  c->cap_table_elems = new_cap;
  gpr_free(c->table_elem_size);
  c->table_elem_size = table_elem_size;
}

void grpc_chttp2_hpack_compressor_set_max_table_size(
    grpc_chttp2_hpack_compressor* c, uint32_t max_table_size) {
  max_table_size = GPR_MIN(max_table_size, c->max_usable_size);
  if (max_table_size == c->max_table_size) {
    return;
  }
  while (c->table_size > 0 && c->table_size > max_table_size) {
    evict_entry(c);
  }
  c->max_table_size = max_table_size;
  c->max_table_elems = elems_for_bytes(max_table_size);
  if (c->max_table_elems > c->cap_table_elems) {
    rebuild_elems(c, GPR_MAX(c->max_table_elems, 2 * c->cap_table_elems));
  } else if (c->max_table_elems < c->cap_table_elems / 3) {
    uint32_t new_cap = GPR_MAX(c->max_table_elems, 16);
    if (new_cap != c->cap_table_elems) {
      rebuild_elems(c, new_cap);
    }
  }
  c->advertise_table_size_change = 1;
  if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
    gpr_log(GPR_INFO, "set max table size from encoder to %d", max_table_size);
  }
}

void grpc_chttp2_encode_header(grpc_chttp2_hpack_compressor* c,
                               grpc_mdelem** extra_headers,
                               size_t extra_headers_size,
                               grpc_metadata_batch* metadata,
                               const grpc_encode_header_options* options,
                               grpc_slice_buffer* outbuf) {
  /* grpc_chttp2_encode_header is called by FlushInitial/TrailingMetadata in
     writing.cc. Specifically, on streams returned by NextStream(), which
     returns streams from the list GRPC_CHTTP2_LIST_WRITABLE. The only way to be
     added to the list is via  grpc_chttp2_list_add_writable_stream(), which
     validates that stream_id is not 0. So, this can be a debug assert. */
  GPR_DEBUG_ASSERT(options->stream_id != 0);
  framer_state st;
#ifndef NDEBUG
  st.seen_regular_header = 0;
#endif
  st.stream_id = options->stream_id;
  st.output = outbuf;
  st.is_first_frame = 1;
  st.stats = options->stats;
  st.max_frame_size = options->max_frame_size;
  st.use_true_binary_metadata = options->use_true_binary_metadata;
  st.is_end_of_stream = options->is_eof;

  /* Encode a metadata batch; store the returned values, representing
     a metadata element that needs to be unreffed back into the metadata
     slot. THIS MAY NOT BE THE SAME ELEMENT (if a decoder table slot got
     updated). After this loop, we'll do a batch unref of elements. */
  begin_frame(&st);
  if (c->advertise_table_size_change != 0) {
    emit_advertise_table_size_change(c, &st);
  }
  for (size_t i = 0; i < extra_headers_size; ++i) {
    grpc_mdelem md = *extra_headers[i];
    const bool is_static =
        GRPC_MDELEM_STORAGE(md) == GRPC_MDELEM_STORAGE_STATIC;
    uintptr_t static_index;
    if (is_static &&
        (static_index =
             reinterpret_cast<grpc_core::StaticMetadata*>(GRPC_MDELEM_DATA(md))
                 ->StaticIndex()) < GRPC_CHTTP2_LAST_STATIC_ENTRY) {
      emit_indexed(c, static_cast<uint32_t>(static_index + 1), &st);
    } else {
      hpack_enc(c, md, &st);
    }
  }
  grpc_metadata_batch_assert_ok(metadata);
  for (grpc_linked_mdelem* l = metadata->list.head; l; l = l->next) {
    const bool is_static =
        GRPC_MDELEM_STORAGE(l->md) == GRPC_MDELEM_STORAGE_STATIC;
    uintptr_t static_index;
    if (is_static &&
        (static_index = reinterpret_cast<grpc_core::StaticMetadata*>(
                            GRPC_MDELEM_DATA(l->md))
                            ->StaticIndex()) < GRPC_CHTTP2_LAST_STATIC_ENTRY) {
      emit_indexed(c, static_cast<uint32_t>(static_index + 1), &st);
    } else {
      hpack_enc(c, l->md, &st);
    }
  }
  grpc_millis deadline = metadata->deadline;
  if (deadline != GRPC_MILLIS_INF_FUTURE) {
    deadline_enc(c, deadline, &st);
  }

  finish_frame(&st, 1);
}