diff options
Diffstat (limited to 'src/core/ext/transport/chttp2/transport/hpack_table.c')
| -rw-r--r-- | src/core/ext/transport/chttp2/transport/hpack_table.c | 369 |
1 files changed, 369 insertions, 0 deletions
diff --git a/src/core/ext/transport/chttp2/transport/hpack_table.c b/src/core/ext/transport/chttp2/transport/hpack_table.c new file mode 100644 index 0000000000..4d64506de2 --- /dev/null +++ b/src/core/ext/transport/chttp2/transport/hpack_table.c @@ -0,0 +1,369 @@ +/* + * + * Copyright 2015, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + */ + +#include "src/core/ext/transport/chttp2/transport/hpack_table.h" + +#include <assert.h> +#include <string.h> + +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> + +#include "src/core/lib/support/murmur_hash.h" + +extern int grpc_http_trace; + +static struct { + const char *key; + const char *value; +} static_table[] = { + /* 0: */ + {NULL, NULL}, + /* 1: */ + {":authority", ""}, + /* 2: */ + {":method", "GET"}, + /* 3: */ + {":method", "POST"}, + /* 4: */ + {":path", "/"}, + /* 5: */ + {":path", "/index.html"}, + /* 6: */ + {":scheme", "http"}, + /* 7: */ + {":scheme", "https"}, + /* 8: */ + {":status", "200"}, + /* 9: */ + {":status", "204"}, + /* 10: */ + {":status", "206"}, + /* 11: */ + {":status", "304"}, + /* 12: */ + {":status", "400"}, + /* 13: */ + {":status", "404"}, + /* 14: */ + {":status", "500"}, + /* 15: */ + {"accept-charset", ""}, + /* 16: */ + {"accept-encoding", "gzip, deflate"}, + /* 17: */ + {"accept-language", ""}, + /* 18: */ + {"accept-ranges", ""}, + /* 19: */ + {"accept", ""}, + /* 20: */ + {"access-control-allow-origin", ""}, + /* 21: */ + {"age", ""}, + /* 22: */ + {"allow", ""}, + /* 23: */ + {"authorization", ""}, + /* 24: */ + {"cache-control", ""}, + /* 25: */ + {"content-disposition", ""}, + /* 26: */ + {"content-encoding", ""}, + /* 27: */ + {"content-language", ""}, + /* 28: */ + {"content-length", ""}, + /* 29: */ + {"content-location", ""}, + /* 30: */ + {"content-range", ""}, + /* 31: */ + {"content-type", ""}, + /* 32: */ + {"cookie", ""}, + /* 33: */ + {"date", ""}, + /* 34: */ + {"etag", ""}, + /* 35: */ + {"expect", ""}, + /* 36: */ + {"expires", ""}, + /* 37: */ + {"from", ""}, + /* 38: */ + {"host", ""}, + /* 39: */ + {"if-match", ""}, + /* 40: */ + {"if-modified-since", ""}, + /* 41: */ + {"if-none-match", ""}, + /* 42: */ + {"if-range", ""}, + /* 43: */ + {"if-unmodified-since", ""}, + /* 44: */ + {"last-modified", ""}, + /* 45: */ + {"link", ""}, + /* 46: */ + {"location", ""}, + /* 47: */ + {"max-forwards", ""}, + /* 48: */ + {"proxy-authenticate", ""}, + /* 49: */ + {"proxy-authorization", ""}, + /* 50: */ + {"range", ""}, + /* 51: */ + {"referer", ""}, + /* 52: */ + {"refresh", ""}, + /* 53: */ + {"retry-after", ""}, + /* 54: */ + {"server", ""}, + /* 55: */ + {"set-cookie", ""}, + /* 56: */ + {"strict-transport-security", ""}, + /* 57: */ + {"transfer-encoding", ""}, + /* 58: */ + {"user-agent", ""}, + /* 59: */ + {"vary", ""}, + /* 60: */ + {"via", ""}, + /* 61: */ + {"www-authenticate", ""}, +}; + +static uint32_t entries_for_bytes(uint32_t bytes) { + return (bytes + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD - 1) / + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD; +} + +void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl *tbl) { + size_t i; + + memset(tbl, 0, sizeof(*tbl)); + tbl->current_table_bytes = tbl->max_bytes = + GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE; + tbl->max_entries = tbl->cap_entries = + entries_for_bytes(tbl->current_table_bytes); + tbl->ents = gpr_malloc(sizeof(*tbl->ents) * tbl->cap_entries); + memset(tbl->ents, 0, sizeof(*tbl->ents) * tbl->cap_entries); + for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) { + tbl->static_ents[i - 1] = + grpc_mdelem_from_strings(static_table[i].key, static_table[i].value); + } +} + +void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl *tbl) { + size_t i; + for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) { + GRPC_MDELEM_UNREF(tbl->static_ents[i]); + } + for (i = 0; i < tbl->num_ents; i++) { + GRPC_MDELEM_UNREF(tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]); + } + gpr_free(tbl->ents); +} + +grpc_mdelem *grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl *tbl, + uint32_t tbl_index) { + /* Static table comes first, just return an entry from it */ + if (tbl_index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) { + return tbl->static_ents[tbl_index - 1]; + } + /* Otherwise, find the value in the list of valid entries */ + tbl_index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1); + if (tbl_index < tbl->num_ents) { + uint32_t offset = + (tbl->num_ents - 1u - tbl_index + tbl->first_ent) % tbl->cap_entries; + return tbl->ents[offset]; + } + /* Invalid entry: return error */ + return NULL; +} + +/* Evict one element from the table */ +static void evict1(grpc_chttp2_hptbl *tbl) { + grpc_mdelem *first_ent = tbl->ents[tbl->first_ent]; + size_t elem_bytes = GPR_SLICE_LENGTH(first_ent->key->slice) + + GPR_SLICE_LENGTH(first_ent->value->slice) + + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD; + GPR_ASSERT(elem_bytes <= tbl->mem_used); + tbl->mem_used -= (uint32_t)elem_bytes; + tbl->first_ent = ((tbl->first_ent + 1) % tbl->cap_entries); + tbl->num_ents--; + GRPC_MDELEM_UNREF(first_ent); +} + +static void rebuild_ents(grpc_chttp2_hptbl *tbl, uint32_t new_cap) { + grpc_mdelem **ents = gpr_malloc(sizeof(*ents) * new_cap); + uint32_t i; + + for (i = 0; i < tbl->num_ents; i++) { + ents[i] = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]; + } + gpr_free(tbl->ents); + tbl->ents = ents; + tbl->cap_entries = new_cap; + tbl->first_ent = 0; +} + +void grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl *tbl, + uint32_t max_bytes) { + if (tbl->max_bytes == max_bytes) { + return; + } + gpr_log(GPR_DEBUG, "Update hpack parser max size to %d", max_bytes); + while (tbl->mem_used > max_bytes) { + evict1(tbl); + } + tbl->max_bytes = max_bytes; +} + +int grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl *tbl, + uint32_t bytes) { + if (tbl->current_table_bytes == bytes) { + return 1; + } + if (bytes > tbl->max_bytes) { + if (grpc_http_trace) { + gpr_log(GPR_ERROR, + "Attempt to make hpack table %d bytes when max is %d bytes", + bytes, tbl->max_bytes); + } + return 0; + } + if (grpc_http_trace) { + gpr_log(GPR_DEBUG, "Update hpack parser table size to %d", bytes); + } + while (tbl->mem_used > bytes) { + evict1(tbl); + } + tbl->current_table_bytes = bytes; + tbl->max_entries = entries_for_bytes(bytes); + if (tbl->max_entries > tbl->cap_entries) { + rebuild_ents(tbl, GPR_MAX(tbl->max_entries, 2 * tbl->cap_entries)); + } else if (tbl->max_entries < tbl->cap_entries / 3) { + uint32_t new_cap = GPR_MAX(tbl->max_entries, 16u); + if (new_cap != tbl->cap_entries) { + rebuild_ents(tbl, new_cap); + } + } + return 1; +} + +int grpc_chttp2_hptbl_add(grpc_chttp2_hptbl *tbl, grpc_mdelem *md) { + /* determine how many bytes of buffer this entry represents */ + size_t elem_bytes = GPR_SLICE_LENGTH(md->key->slice) + + GPR_SLICE_LENGTH(md->value->slice) + + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD; + + if (tbl->current_table_bytes > tbl->max_bytes) { + if (grpc_http_trace) { + gpr_log(GPR_ERROR, + "HPACK max table size reduced to %d but not reflected by hpack " + "stream (still at %d)", + tbl->max_bytes, tbl->current_table_bytes); + } + return 0; + } + + /* we can't add elements bigger than the max table size */ + if (elem_bytes > tbl->current_table_bytes) { + /* HPACK draft 10 section 4.4 states: + * If the size of the new entry is less than or equal to the maximum + * size, that entry is added to the table. It is not an error to + * attempt to add an entry that is larger than the maximum size; an + * attempt to add an entry larger than the entire table causes + * the table + * to be emptied of all existing entries, and results in an + * empty table. + */ + while (tbl->num_ents) { + evict1(tbl); + } + return 1; + } + + /* evict entries to ensure no overflow */ + while (elem_bytes > (size_t)tbl->current_table_bytes - tbl->mem_used) { + evict1(tbl); + } + + /* copy the finalized entry in */ + tbl->ents[(tbl->first_ent + tbl->num_ents) % tbl->cap_entries] = + GRPC_MDELEM_REF(md); + + /* update accounting values */ + tbl->num_ents++; + tbl->mem_used += (uint32_t)elem_bytes; + return 1; +} + +grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find( + const grpc_chttp2_hptbl *tbl, grpc_mdelem *md) { + grpc_chttp2_hptbl_find_result r = {0, 0}; + uint32_t i; + + /* See if the string is in the static table */ + for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) { + grpc_mdelem *ent = tbl->static_ents[i]; + if (md->key != ent->key) continue; + r.index = i + 1u; + r.has_value = md->value == ent->value; + if (r.has_value) return r; + } + + /* Scan the dynamic table */ + for (i = 0; i < tbl->num_ents; i++) { + uint32_t idx = + (uint32_t)(tbl->num_ents - i + GRPC_CHTTP2_LAST_STATIC_ENTRY); + grpc_mdelem *ent = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]; + if (md->key != ent->key) continue; + r.index = idx; + r.has_value = md->value == ent->value; + if (r.has_value) return r; + } + + return r; +} |