aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/transport/chttp2/hpack_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/core/transport/chttp2/hpack_table.c')
-rw-r--r--src/core/transport/chttp2/hpack_table.c210
1 files changed, 210 insertions, 0 deletions
diff --git a/src/core/transport/chttp2/hpack_table.c b/src/core/transport/chttp2/hpack_table.c
new file mode 100644
index 0000000000..8f2ebecfeb
--- /dev/null
+++ b/src/core/transport/chttp2/hpack_table.c
@@ -0,0 +1,210 @@
+/*
+ *
+ * Copyright 2014, 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/transport/chttp2/hpack_table.h"
+
+#include <assert.h>
+#include <string.h>
+
+#include <grpc/support/log.h>
+#include "src/core/support/murmur_hash.h"
+
+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", ""},
+};
+
+void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl *tbl, grpc_mdctx *mdctx) {
+ size_t i;
+
+ memset(tbl, 0, sizeof(*tbl));
+ tbl->mdctx = mdctx;
+ tbl->max_bytes = GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
+ for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
+ tbl->static_ents[i - 1] = grpc_mdelem_from_strings(
+ mdctx, 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) % GRPC_CHTTP2_MAX_TABLE_COUNT]);
+ }
+}
+
+grpc_mdelem *grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl *tbl,
+ gpr_uint32 index) {
+ /* Static table comes first, just return an entry from it */
+ if (index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
+ return tbl->static_ents[index - 1];
+ }
+ /* Otherwise, find the value in the list of valid entries */
+ index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
+ if (index < tbl->num_ents) {
+ gpr_uint32 offset = (tbl->num_ents - 1 - index + tbl->first_ent) %
+ GRPC_CHTTP2_MAX_TABLE_COUNT;
+ 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];
+ tbl->mem_used -= GPR_SLICE_LENGTH(first_ent->key->slice) +
+ GPR_SLICE_LENGTH(first_ent->value->slice) +
+ GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
+ tbl->first_ent = (tbl->first_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT;
+ tbl->num_ents--;
+ grpc_mdelem_unref(first_ent);
+}
+
+void grpc_chttp2_hptbl_add(grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
+ /* determine how many bytes of buffer this entry represents */
+ gpr_uint16 elem_bytes = GPR_SLICE_LENGTH(md->key->slice) +
+ GPR_SLICE_LENGTH(md->value->slice) +
+ GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
+
+ /* we can't add elements bigger than the max table size */
+ assert(elem_bytes <= tbl->max_bytes);
+
+ /* evict entries to ensure no overflow */
+ while (elem_bytes > tbl->max_bytes - tbl->mem_used) {
+ evict1(tbl);
+ }
+
+ /* copy the finalized entry in */
+ tbl->ents[tbl->last_ent] = md;
+
+ /* update accounting values */
+ tbl->last_ent = (tbl->last_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT;
+ tbl->num_ents++;
+ tbl->mem_used += elem_bytes;
+}
+
+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};
+ int 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 + 1;
+ 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++) {
+ int idx = tbl->num_ents - i + GRPC_CHTTP2_LAST_STATIC_ENTRY;
+ grpc_mdelem *ent =
+ tbl->ents[(tbl->first_ent + i) % GRPC_CHTTP2_MAX_TABLE_COUNT];
+ if (md->key != ent->key) continue;
+ r.index = idx;
+ r.has_value = md->value == ent->value;
+ if (r.has_value) return r;
+ }
+
+ return r;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 05:15:05 +0000