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 #ifndef GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_TABLE_H
20 #define GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_TABLE_H
21
22 #include <grpc/support/port_platform.h>
23
24 #include <grpc/slice.h>
25 #include "src/core/lib/gprpp/memory.h"
26 #include "src/core/lib/iomgr/error.h"
27 #include "src/core/lib/transport/metadata.h"
28 #include "src/core/lib/transport/static_metadata.h"
29
30 /* HPACK header table */
31
32 /* last index in the static table */
33 #define GRPC_CHTTP2_LAST_STATIC_ENTRY 61
34
35 /* Initial table size as per the spec */
36 #define GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE 4096
37 /* Maximum table size that we'll use */
38 #define GRPC_CHTTP2_MAX_HPACK_TABLE_SIZE GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE
39 /* Per entry overhead bytes as per the spec */
40 #define GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD 32
41 #if 0
42 /* Maximum number of entries we could possibly fit in the table, given defined
43 overheads */
44 #define GRPC_CHTTP2_MAX_TABLE_COUNT \
45 ((GRPC_CHTTP2_MAX_HPACK_TABLE_SIZE + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD - 1) / \
46 GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD)
47 #endif
48
49 /* hpack decoder table */
50 struct grpc_chttp2_hptbl {
entries_for_bytesgrpc_chttp2_hptbl51 static uint32_t entries_for_bytes(uint32_t bytes) {
52 return (bytes + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD - 1) /
53 GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
54 }
55 static constexpr uint32_t kInitialCapacity =
56 (GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD -
57 1) /
58 GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
59
grpc_chttp2_hptblgrpc_chttp2_hptbl60 grpc_chttp2_hptbl() {
61 GPR_DEBUG_ASSERT(!ents);
62 constexpr uint32_t AllocSize = sizeof(*ents) * kInitialCapacity;
63 ents = static_cast<grpc_mdelem*>(gpr_malloc(AllocSize));
64 memset(ents, 0, AllocSize);
65 }
66
67 /* the first used entry in ents */
68 uint32_t first_ent = 0;
69 /* how many entries are in the table */
70 uint32_t num_ents = 0;
71 /* the amount of memory used by the table, according to the hpack algorithm */
72 uint32_t mem_used = 0;
73 /* the max memory allowed to be used by the table, according to the hpack
74 algorithm */
75 uint32_t max_bytes = GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
76 /* the currently agreed size of the table, according to the hpack algorithm */
77 uint32_t current_table_bytes = GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
78 /* Maximum number of entries we could possibly fit in the table, given defined
79 overheads */
80 uint32_t max_entries = kInitialCapacity;
81 /* Number of entries allocated in ents */
82 uint32_t cap_entries = kInitialCapacity;
83 /* a circular buffer of headers - this is stored in the opposite order to
84 what hpack specifies, in order to simplify table management a little...
85 meaning lookups need to SUBTRACT from the end position */
86 grpc_mdelem* ents = nullptr;
87 };
88
89 void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl* tbl);
90 void grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl* tbl,
91 uint32_t max_bytes);
92 grpc_error* grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl* tbl,
93 uint32_t bytes);
94
95 /* lookup a table entry based on its hpack index */
96 grpc_mdelem grpc_chttp2_hptbl_lookup_dynamic_index(const grpc_chttp2_hptbl* tbl,
97 uint32_t tbl_index);
98 grpc_mdelem grpc_chttp2_hptbl_lookup_ref_dynamic_index(
99 const grpc_chttp2_hptbl* tbl, uint32_t tbl_index);
100 template <bool take_ref = false>
grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl * tbl,uint32_t index)101 inline grpc_mdelem grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl* tbl,
102 uint32_t index) {
103 /* Static table comes first, just return an entry from it.
104 NB: This imposes the constraint that the first
105 GRPC_CHTTP2_LAST_STATIC_ENTRY entries in the core static metadata table
106 must follow the hpack standard. If that changes, we *must* not rely on
107 reading the core static metadata table here; at that point we'd need our
108 own singleton static metadata in the correct order. */
109 if (index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
110 return grpc_static_mdelem_manifested()[index - 1];
111 } else {
112 if (take_ref) {
113 return grpc_chttp2_hptbl_lookup_ref_dynamic_index(tbl, index);
114 } else {
115 return grpc_chttp2_hptbl_lookup_dynamic_index(tbl, index);
116 }
117 }
118 }
119 /* add a table entry to the index */
120 grpc_error* grpc_chttp2_hptbl_add(grpc_chttp2_hptbl* tbl,
121 grpc_mdelem md) GRPC_MUST_USE_RESULT;
122
123 size_t grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,
124 bool use_true_binary_metadata);
125
126 /* Returns the static hpack table index that corresponds to /a elem. Returns 0
127 if /a elem is not statically stored or if it is not in the static hpack
128 table */
grpc_chttp2_get_static_hpack_table_index(grpc_mdelem md)129 inline uintptr_t grpc_chttp2_get_static_hpack_table_index(grpc_mdelem md) {
130 uintptr_t index =
131 reinterpret_cast<grpc_core::StaticMetadata*>(GRPC_MDELEM_DATA(md)) -
132 grpc_static_mdelem_table();
133 if (index < GRPC_CHTTP2_LAST_STATIC_ENTRY) {
134 return index + 1; // Hpack static metadata element indices start at 1
135 }
136 return 0;
137 }
138
139 /* Find a key/value pair in the table... returns the index in the table of the
140 most similar entry, or 0 if the value was not found */
141 struct grpc_chttp2_hptbl_find_result {
142 uint32_t index;
143 int has_value;
144 };
145 grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
146 const grpc_chttp2_hptbl* tbl, grpc_mdelem md);
147
148 #endif /* GRPC_CORE_EXT_TRANSPORT_CHTTP2_TRANSPORT_HPACK_TABLE_H */
149