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 <grpc/support/alloc.h>
  27 #include <grpc/support/log.h>
  28 #include <grpc/support/string_util.h>
  29
  30 #include "src/core/lib/debug/trace.h"
  31 #include "src/core/lib/gpr/murmur_hash.h"
  32 #include "src/core/lib/surface/validate_metadata.h"
  33 #include "src/core/lib/transport/static_metadata.h"
  34
  35 extern grpc_core::TraceFlag grpc_http_trace;
  36
  37 static struct {
  38   const char* key;
  39   const char* value;
  40 } static_table[] = {
  41     /* 0: */
  42     {nullptr, nullptr},
  43     /* 1: */
  44     {":authority", ""},
  45     /* 2: */
  46     {":method", "GET"},
  47     /* 3: */
  48     {":method", "POST"},
  49     /* 4: */
  50     {":path", "/"},
  51     /* 5: */
  52     {":path", "/index.html"},
  53     /* 6: */
  54     {":scheme", "http"},
  55     /* 7: */
  56     {":scheme", "https"},
  57     /* 8: */
  58     {":status", "200"},
  59     /* 9: */
  60     {":status", "204"},
  61     /* 10: */
  62     {":status", "206"},
  63     /* 11: */
  64     {":status", "304"},
  65     /* 12: */
  66     {":status", "400"},
  67     /* 13: */
  68     {":status", "404"},
  69     /* 14: */
  70     {":status", "500"},
  71     /* 15: */
  72     {"accept-charset", ""},
  73     /* 16: */
  74     {"accept-encoding", "gzip, deflate"},
  75     /* 17: */
  76     {"accept-language", ""},
  77     /* 18: */
  78     {"accept-ranges", ""},
  79     /* 19: */
  80     {"accept", ""},
  81     /* 20: */
  82     {"access-control-allow-origin", ""},
  83     /* 21: */
  84     {"age", ""},
  85     /* 22: */
  86     {"allow", ""},
  87     /* 23: */
  88     {"authorization", ""},
  89     /* 24: */
  90     {"cache-control", ""},
  91     /* 25: */
  92     {"content-disposition", ""},
  93     /* 26: */
  94     {"content-encoding", ""},
  95     /* 27: */
  96     {"content-language", ""},
  97     /* 28: */
  98     {"content-length", ""},
  99     /* 29: */
 100     {"content-location", ""},
 101     /* 30: */
 102     {"content-range", ""},
 103     /* 31: */
 104     {"content-type", ""},
 105     /* 32: */
 106     {"cookie", ""},
 107     /* 33: */
 108     {"date", ""},
 109     /* 34: */
 110     {"etag", ""},
 111     /* 35: */
 112     {"expect", ""},
 113     /* 36: */
 114     {"expires", ""},
 115     /* 37: */
 116     {"from", ""},
 117     /* 38: */
 118     {"host", ""},
 119     /* 39: */
 120     {"if-match", ""},
 121     /* 40: */
 122     {"if-modified-since", ""},
 123     /* 41: */
 124     {"if-none-match", ""},
 125     /* 42: */
 126     {"if-range", ""},
 127     /* 43: */
 128     {"if-unmodified-since", ""},
 129     /* 44: */
 130     {"last-modified", ""},
 131     /* 45: */
 132     {"link", ""},
 133     /* 46: */
 134     {"location", ""},
 135     /* 47: */
 136     {"max-forwards", ""},
 137     /* 48: */
 138     {"proxy-authenticate", ""},
 139     /* 49: */
 140     {"proxy-authorization", ""},
 141     /* 50: */
 142     {"range", ""},
 143     /* 51: */
 144     {"referer", ""},
 145     /* 52: */
 146     {"refresh", ""},
 147     /* 53: */
 148     {"retry-after", ""},
 149     /* 54: */
 150     {"server", ""},
 151     /* 55: */
 152     {"set-cookie", ""},
 153     /* 56: */
 154     {"strict-transport-security", ""},
 155     /* 57: */
 156     {"transfer-encoding", ""},
 157     /* 58: */
 158     {"user-agent", ""},
 159     /* 59: */
 160     {"vary", ""},
 161     /* 60: */
 162     {"via", ""},
 163     /* 61: */
 164     {"www-authenticate", ""},
 165 };
 166
 167 static uint32_t entries_for_bytes(uint32_t bytes) {
 168   return (bytes + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD - 1) /
 169          GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
 170 }
 171
 172 void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl* tbl) {
 173   size_t i;
 174
 175   memset(tbl, 0, sizeof(*tbl));
 176   tbl->current_table_bytes = tbl->max_bytes =
 177       GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
 178   tbl->max_entries = tbl->cap_entries =
 179       entries_for_bytes(tbl->current_table_bytes);
 180   tbl->ents = static_cast<grpc_mdelem*>(
 181       gpr_malloc(sizeof(*tbl->ents) * tbl->cap_entries));
 182   memset(tbl->ents, 0, sizeof(*tbl->ents) * tbl->cap_entries);
 183   for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
 184     tbl->static_ents[i - 1] = grpc_mdelem_from_slices(
 185         grpc_slice_intern(grpc_slice_from_static_string(static_table[i].key)),
 186         grpc_slice_intern(
 187             grpc_slice_from_static_string(static_table[i].value)));
 188   }
 189 }
 190
 191 void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl* tbl) {
 192   size_t i;
 193   for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
 194     GRPC_MDELEM_UNREF(tbl->static_ents[i]);
 195   }
 196   for (i = 0; i < tbl->num_ents; i++) {
 197     GRPC_MDELEM_UNREF(tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]);
 198   }
 199   gpr_free(tbl->ents);
 200 }
 201
 202 grpc_mdelem grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl* tbl,
 203                                      uint32_t tbl_index) {
 204   /* Static table comes first, just return an entry from it */
 205   if (tbl_index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
 206     return tbl->static_ents[tbl_index - 1];
 207   }
 208   /* Otherwise, find the value in the list of valid entries */
 209   tbl_index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
 210   if (tbl_index < tbl->num_ents) {
 211     uint32_t offset =
 212         (tbl->num_ents - 1u - tbl_index + tbl->first_ent) % tbl->cap_entries;
 213     return tbl->ents[offset];
 214   }
 215   /* Invalid entry: return error */
 216   return GRPC_MDNULL;
 217 }
 218
 219 /* Evict one element from the table */
 220 static void evict1(grpc_chttp2_hptbl* tbl) {
 221   grpc_mdelem first_ent = tbl->ents[tbl->first_ent];
 222   size_t elem_bytes = GRPC_SLICE_LENGTH(GRPC_MDKEY(first_ent)) +
 223                       GRPC_SLICE_LENGTH(GRPC_MDVALUE(first_ent)) +
 224                       GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
 225   GPR_ASSERT(elem_bytes <= tbl->mem_used);
 226   tbl->mem_used -= static_cast<uint32_t>(elem_bytes);
 227   tbl->first_ent = ((tbl->first_ent + 1) % tbl->cap_entries);
 228   tbl->num_ents--;
 229   GRPC_MDELEM_UNREF(first_ent);
 230 }
 231
 232 static void rebuild_ents(grpc_chttp2_hptbl* tbl, uint32_t new_cap) {
 233   grpc_mdelem* ents =
 234       static_cast<grpc_mdelem*>(gpr_malloc(sizeof(*ents) * new_cap));
 235   uint32_t i;
 236
 237   for (i = 0; i < tbl->num_ents; i++) {
 238     ents[i] = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
 239   }
 240   gpr_free(tbl->ents);
 241   tbl->ents = ents;
 242   tbl->cap_entries = new_cap;
 243   tbl->first_ent = 0;
 244 }
 245
 246 void grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl* tbl,
 247                                      uint32_t max_bytes) {
 248   if (tbl->max_bytes == max_bytes) {
 249     return;
 250   }
 251   if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
 252     gpr_log(GPR_INFO, "Update hpack parser max size to %d", max_bytes);
 253   }
 254   while (tbl->mem_used > max_bytes) {
 255     evict1(tbl);
 256   }
 257   tbl->max_bytes = max_bytes;
 258 }
 259
 260 grpc_error* grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl* tbl,
 261                                                      uint32_t bytes) {
 262   if (tbl->current_table_bytes == bytes) {
 263     return GRPC_ERROR_NONE;
 264   }
 265   if (bytes > tbl->max_bytes) {
 266     char* msg;
 267     gpr_asprintf(&msg,
 268                  "Attempt to make hpack table %d bytes when max is %d bytes",
 269                  bytes, tbl->max_bytes);
 270     grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
 271     gpr_free(msg);
 272     return err;
 273   }
 274   if (GRPC_TRACE_FLAG_ENABLED(grpc_http_trace)) {
 275     gpr_log(GPR_INFO, "Update hpack parser table size to %d", bytes);
 276   }
 277   while (tbl->mem_used > bytes) {
 278     evict1(tbl);
 279   }
 280   tbl->current_table_bytes = bytes;
 281   tbl->max_entries = entries_for_bytes(bytes);
 282   if (tbl->max_entries > tbl->cap_entries) {
 283     rebuild_ents(tbl, GPR_MAX(tbl->max_entries, 2 * tbl->cap_entries));
 284   } else if (tbl->max_entries < tbl->cap_entries / 3) {
 285     uint32_t new_cap = GPR_MAX(tbl->max_entries, 16u);
 286     if (new_cap != tbl->cap_entries) {
 287       rebuild_ents(tbl, new_cap);
 288     }
 289   }
 290   return GRPC_ERROR_NONE;
 291 }
 292
 293 grpc_error* grpc_chttp2_hptbl_add(grpc_chttp2_hptbl* tbl, grpc_mdelem md) {
 294   /* determine how many bytes of buffer this entry represents */
 295   size_t elem_bytes = GRPC_SLICE_LENGTH(GRPC_MDKEY(md)) +
 296                       GRPC_SLICE_LENGTH(GRPC_MDVALUE(md)) +
 297                       GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
 298
 299   if (tbl->current_table_bytes > tbl->max_bytes) {
 300     char* msg;
 301     gpr_asprintf(
 302         &msg,
 303         "HPACK max table size reduced to %d but not reflected by hpack "
 304         "stream (still at %d)",
 305         tbl->max_bytes, tbl->current_table_bytes);
 306     grpc_error* err = GRPC_ERROR_CREATE_FROM_COPIED_STRING(msg);
 307     gpr_free(msg);
 308     return err;
 309   }
 310
 311   /* we can't add elements bigger than the max table size */
 312   if (elem_bytes > tbl->current_table_bytes) {
 313     /* HPACK draft 10 section 4.4 states:
 314      * If the size of the new entry is less than or equal to the maximum
 315      * size, that entry is added to the table.  It is not an error to
 316      * attempt to add an entry that is larger than the maximum size; an
 317      * attempt to add an entry larger than the entire table causes
 318      * the table
 319      * to be emptied of all existing entries, and results in an
 320      * empty table.
 321      */
 322     while (tbl->num_ents) {
 323       evict1(tbl);
 324     }
 325     return GRPC_ERROR_NONE;
 326   }
 327
 328   /* evict entries to ensure no overflow */
 329   while (elem_bytes >
 330          static_cast<size_t>(tbl->current_table_bytes) - tbl->mem_used) {
 331     evict1(tbl);
 332   }
 333
 334   /* copy the finalized entry in */
 335   tbl->ents[(tbl->first_ent + tbl->num_ents) % tbl->cap_entries] =
 336       GRPC_MDELEM_REF(md);
 337
 338   /* update accounting values */
 339   tbl->num_ents++;
 340   tbl->mem_used += static_cast<uint32_t>(elem_bytes);
 341   return GRPC_ERROR_NONE;
 342 }
 343
 344 grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
 345     const grpc_chttp2_hptbl* tbl, grpc_mdelem md) {
 346   grpc_chttp2_hptbl_find_result r = {0, 0};
 347   uint32_t i;
 348
 349   /* See if the string is in the static table */
 350   for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
 351     grpc_mdelem ent = tbl->static_ents[i];
 352     if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
 353     r.index = i + 1u;
 354     r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
 355     if (r.has_value) return r;
 356   }
 357
 358   /* Scan the dynamic table */
 359   for (i = 0; i < tbl->num_ents; i++) {
 360     uint32_t idx = static_cast<uint32_t>(tbl->num_ents - i +
 361                                          GRPC_CHTTP2_LAST_STATIC_ENTRY);
 362     grpc_mdelem ent = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
 363     if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
 364     r.index = idx;
 365     r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
 366     if (r.has_value) return r;
 367   }
 368
 369   return r;
 370 }
 371
 372 static size_t get_base64_encoded_size(size_t raw_length) {
 373   static const uint8_t tail_xtra[3] = {0, 2, 3};
 374   return raw_length / 3 * 4 + tail_xtra[raw_length % 3];
 375 }
 376
 377 size_t grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,
 378                                            bool use_true_binary_metadata) {
 379   const uint8_t* key_buf = GRPC_SLICE_START_PTR(GRPC_MDKEY(elem));
 380   size_t key_len = GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
 381   size_t overhead_and_key = 32 + key_len;
 382   size_t value_len = GRPC_SLICE_LENGTH(GRPC_MDVALUE(elem));
 383   if (grpc_key_is_binary_header(key_buf, key_len)) {
 384     return overhead_and_key + (use_true_binary_metadata
 385                                    ? value_len + 1
 386                                    : get_base64_encoded_size(value_len));
 387   } else {
 388     return overhead_and_key + value_len;
 389   }
 390 }