src/core/ext/transport/chttp2/transport/hpack_table.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_table.h"
  22
  23 #include <assert.h>
  24 #include <string.h>
  25
  26 #include "absl/strings/str_format.h"
  27
  28 #include <grpc/support/alloc.h>
  29 #include <grpc/support/log.h>
  30
  31 #include "src/core/lib/debug/trace.h"
  32 #include "src/core/lib/gpr/murmur_hash.h"
  33 #include "src/core/lib/slice/slice_internal.h"
  34 #include "src/core/lib/surface/validate_metadata.h"
  35 #include "src/core/lib/transport/static_metadata.h"
  36
  37 extern grpc_core::TraceFlag grpc_http_trace;
  38
  39 void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl* tbl) {
  40   size_t i;
  41   for (i = 0; i < tbl->num_ents; i++) {
  42     GRPC_MDELEM_UNREF(tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]);
  43   }
  44   gpr_free(tbl->ents);
  45   tbl->ents = nullptr;
  46 }
  47
  48 template <bool take_ref>
  49 static grpc_mdelem lookup_dynamic_index(const grpc_chttp2_hptbl* tbl,
  50                                         uint32_t tbl_index) {
  51   /* Not static - find the value in the list of valid entries */
  52   tbl_index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
  53   if (tbl_index < tbl->num_ents) {
  54     uint32_t offset =
  55         (tbl->num_ents - 1u - tbl_index + tbl->first_ent) % tbl->cap_entries;
  56     grpc_mdelem md = tbl->ents[offset];
  57     if (take_ref) {
  58       GRPC_MDELEM_REF(md);
  59     }
  60     return md;
  61   }
  62   /* Invalid entry: return error */
  63   return GRPC_MDNULL;
  64 }
  65
  66 grpc_mdelem grpc_chttp2_hptbl_lookup_dynamic_index(const grpc_chttp2_hptbl* tbl,
  67                                                    uint32_t tbl_index) {
  68   return lookup_dynamic_index<false>(tbl, tbl_index);
  69 }
  70
  71 grpc_mdelem grpc_chttp2_hptbl_lookup_ref_dynamic_index(
  72     const grpc_chttp2_hptbl* tbl, uint32_t tbl_index) {
  73   return lookup_dynamic_index<true>(tbl, tbl_index);
  74 }
  75
  76 /* Evict one element from the table */
  77 static void evict1(grpc_chttp2_hptbl* tbl) {
  78   grpc_mdelem first_ent = tbl->ents[tbl->first_ent];
  79   size_t elem_bytes = GRPC_SLICE_LENGTH(GRPC_MDKEY(first_ent)) +
  80                       GRPC_SLICE_LENGTH(GRPC_MDVALUE(first_ent)) +
  81                       GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
  82   GPR_ASSERT(elem_bytes <= tbl->mem_used);
  83   tbl->mem_used -= static_cast<uint32_t>(elem_bytes);
  84   tbl->first_ent = ((tbl->first_ent + 1) % tbl->cap_entries);
  85   tbl->num_ents--;
  86   GRPC_MDELEM_UNREF(first_ent);
  87 }
  88
  89 static void rebuild_ents(grpc_chttp2_hptbl* tbl, uint32_t new_cap) {
  90   grpc_mdelem* ents =
  91       static_cast<grpc_mdelem*>(gpr_malloc(sizeof(*ents) * new_cap));
  92   uint32_t i;
  93
  94   for (i = 0; i < tbl->num_ents; i++) {
  95     ents[i] = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
  96   }
  97   gpr_free(tbl->ents);
  98   tbl->ents = ents;
  99   tbl->cap_entries = new_cap;
 100   tbl->first_ent = 0;
 101 }
 102
 103 void grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl* tbl,
 104                                      uint32_t max_bytes) {
 105   if (tbl->max_bytes == max_bytes) {
 106     return;
 107   }
 108   if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
 109     gpr_log(GPR_INFO, "Update hpack parser max size to %d", max_bytes);
 110   }
 111   while (tbl->mem_used > max_bytes) {
 112     evict1(tbl);
 113   }
 114   tbl->max_bytes = max_bytes;
 115 }
 116
 117 grpc_error_handle grpc_chttp2_hptbl_set_current_table_size(
 118     grpc_chttp2_hptbl* tbl, uint32_t bytes) {
 119   if (tbl->current_table_bytes == bytes) {
 120     return GRPC_ERROR_NONE;
 121   }
 122   if (bytes > tbl->max_bytes) {
 123     return GRPC_ERROR_CREATE_FROM_COPIED_STRING(
 124         absl::StrFormat(
 125             "Attempt to make hpack table %d bytes when max is %d bytes", bytes,
 126             tbl->max_bytes)
 127             .c_str());
 128   }
 129   if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
 130     gpr_log(GPR_INFO, "Update hpack parser table size to %d", bytes);
 131   }
 132   while (tbl->mem_used > bytes) {
 133     evict1(tbl);
 134   }
 135   tbl->current_table_bytes = bytes;
 136   tbl->max_entries = grpc_chttp2_hptbl::entries_for_bytes(bytes);
 137   if (tbl->max_entries > tbl->cap_entries) {
 138     rebuild_ents(tbl, GPR_MAX(tbl->max_entries, 2 * tbl->cap_entries));
 139   } else if (tbl->max_entries < tbl->cap_entries / 3) {
 140     uint32_t new_cap = GPR_MAX(tbl->max_entries, 16u);
 141     if (new_cap != tbl->cap_entries) {
 142       rebuild_ents(tbl, new_cap);
 143     }
 144   }
 145   return GRPC_ERROR_NONE;
 146 }
 147
 148 grpc_error_handle grpc_chttp2_hptbl_add(grpc_chttp2_hptbl* tbl,
 149                                         grpc_mdelem md) {
 150   /* determine how many bytes of buffer this entry represents */
 151   size_t elem_bytes = GRPC_SLICE_LENGTH(GRPC_MDKEY(md)) +
 152                       GRPC_SLICE_LENGTH(GRPC_MDVALUE(md)) +
 153                       GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
 154
 155   if (tbl->current_table_bytes > tbl->max_bytes) {
 156     return GRPC_ERROR_CREATE_FROM_COPIED_STRING(
 157         absl::StrFormat(
 158             "HPACK max table size reduced to %d but not reflected by hpack "
 159             "stream (still at %d)",
 160             tbl->max_bytes, tbl->current_table_bytes)
 161             .c_str());
 162   }
 163
 164   /* we can't add elements bigger than the max table size */
 165   if (elem_bytes > tbl->current_table_bytes) {
 166     /* HPACK draft 10 section 4.4 states:
 167      * If the size of the new entry is less than or equal to the maximum
 168      * size, that entry is added to the table.  It is not an error to
 169      * attempt to add an entry that is larger than the maximum size; an
 170      * attempt to add an entry larger than the entire table causes
 171      * the table
 172      * to be emptied of all existing entries, and results in an
 173      * empty table.
 174      */
 175     while (tbl->num_ents) {
 176       evict1(tbl);
 177     }
 178     return GRPC_ERROR_NONE;
 179   }
 180
 181   /* evict entries to ensure no overflow */
 182   while (elem_bytes >
 183          static_cast<size_t>(tbl->current_table_bytes) - tbl->mem_used) {
 184     evict1(tbl);
 185   }
 186
 187   /* copy the finalized entry in */
 188   tbl->ents[(tbl->first_ent + tbl->num_ents) % tbl->cap_entries] =
 189       GRPC_MDELEM_REF(md);
 190
 191   /* update accounting values */
 192   tbl->num_ents++;
 193   tbl->mem_used += static_cast<uint32_t>(elem_bytes);
 194   return GRPC_ERROR_NONE;
 195 }
 196
 197 grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
 198     const grpc_chttp2_hptbl* tbl, grpc_mdelem md) {
 199   grpc_chttp2_hptbl_find_result r = {0, 0};
 200   uint32_t i;
 201
 202   /* See if the string is in the static table */
 203   for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
 204     grpc_mdelem ent = grpc_static_mdelem_manifested()[i];
 205     if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
 206     r.index = i + 1u;
 207     r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
 208     if (r.has_value) return r;
 209   }
 210
 211   /* Scan the dynamic table */
 212   for (i = 0; i < tbl->num_ents; i++) {
 213     uint32_t idx = static_cast<uint32_t>(tbl->num_ents - i +
 214                                          GRPC_CHTTP2_LAST_STATIC_ENTRY);
 215     grpc_mdelem ent = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
 216     if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
 217     r.index = idx;
 218     r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
 219     if (r.has_value) return r;
 220   }
 221
 222   return r;
 223 }
 224
 225 static size_t get_base64_encoded_size(size_t raw_length) {
 226   static const uint8_t tail_xtra[3] = {0, 2, 3};
 227   return raw_length / 3 * 4 + tail_xtra[raw_length % 3];
 228 }
 229
 230 size_t grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,
 231                                            bool use_true_binary_metadata) {
 232   const uint8_t* key_buf = GRPC_SLICE_START_PTR(GRPC_MDKEY(elem));
 233   size_t key_len = GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
 234   size_t overhead_and_key = 32 + key_len;
 235   size_t value_len = GRPC_SLICE_LENGTH(GRPC_MDVALUE(elem));
 236   if (grpc_key_is_binary_header(key_buf, key_len)) {
 237     return overhead_and_key + (use_true_binary_metadata
 238                                    ? value_len + 1
 239                                    : get_base64_encoded_size(value_len));
 240   } else {
 241     return overhead_and_key + value_len;
 242   }
 243 }