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
grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl * tbl)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>
lookup_dynamic_index(const grpc_chttp2_hptbl * tbl,uint32_t tbl_index)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
grpc_chttp2_hptbl_lookup_dynamic_index(const grpc_chttp2_hptbl * tbl,uint32_t tbl_index)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
grpc_chttp2_hptbl_lookup_ref_dynamic_index(const grpc_chttp2_hptbl * tbl,uint32_t tbl_index)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 */
evict1(grpc_chttp2_hptbl * tbl)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
rebuild_ents(grpc_chttp2_hptbl * tbl,uint32_t new_cap)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
grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl * tbl,uint32_t max_bytes)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
grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl * tbl,uint32_t bytes)117 grpc_error* grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl* tbl,
118 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
grpc_chttp2_hptbl_add(grpc_chttp2_hptbl * tbl,grpc_mdelem md)148 grpc_error* grpc_chttp2_hptbl_add(grpc_chttp2_hptbl* tbl, grpc_mdelem md) {
149 /* determine how many bytes of buffer this entry represents */
150 size_t elem_bytes = GRPC_SLICE_LENGTH(GRPC_MDKEY(md)) +
151 GRPC_SLICE_LENGTH(GRPC_MDVALUE(md)) +
152 GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
153
154 if (tbl->current_table_bytes > tbl->max_bytes) {
155 return GRPC_ERROR_CREATE_FROM_COPIED_STRING(
156 absl::StrFormat(
157 "HPACK max table size reduced to %d but not reflected by hpack "
158 "stream (still at %d)",
159 tbl->max_bytes, tbl->current_table_bytes)
160 .c_str());
161 }
162
163 /* we can't add elements bigger than the max table size */
164 if (elem_bytes > tbl->current_table_bytes) {
165 /* HPACK draft 10 section 4.4 states:
166 * If the size of the new entry is less than or equal to the maximum
167 * size, that entry is added to the table. It is not an error to
168 * attempt to add an entry that is larger than the maximum size; an
169 * attempt to add an entry larger than the entire table causes
170 * the table
171 * to be emptied of all existing entries, and results in an
172 * empty table.
173 */
174 while (tbl->num_ents) {
175 evict1(tbl);
176 }
177 return GRPC_ERROR_NONE;
178 }
179
180 /* evict entries to ensure no overflow */
181 while (elem_bytes >
182 static_cast<size_t>(tbl->current_table_bytes) - tbl->mem_used) {
183 evict1(tbl);
184 }
185
186 /* copy the finalized entry in */
187 tbl->ents[(tbl->first_ent + tbl->num_ents) % tbl->cap_entries] =
188 GRPC_MDELEM_REF(md);
189
190 /* update accounting values */
191 tbl->num_ents++;
192 tbl->mem_used += static_cast<uint32_t>(elem_bytes);
193 return GRPC_ERROR_NONE;
194 }
195
grpc_chttp2_hptbl_find(const grpc_chttp2_hptbl * tbl,grpc_mdelem md)196 grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
197 const grpc_chttp2_hptbl* tbl, grpc_mdelem md) {
198 grpc_chttp2_hptbl_find_result r = {0, 0};
199 uint32_t i;
200
201 /* See if the string is in the static table */
202 for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
203 grpc_mdelem ent = grpc_static_mdelem_manifested()[i];
204 if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
205 r.index = i + 1u;
206 r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
207 if (r.has_value) return r;
208 }
209
210 /* Scan the dynamic table */
211 for (i = 0; i < tbl->num_ents; i++) {
212 uint32_t idx = static_cast<uint32_t>(tbl->num_ents - i +
213 GRPC_CHTTP2_LAST_STATIC_ENTRY);
214 grpc_mdelem ent = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
215 if (!grpc_slice_eq(GRPC_MDKEY(md), GRPC_MDKEY(ent))) continue;
216 r.index = idx;
217 r.has_value = grpc_slice_eq(GRPC_MDVALUE(md), GRPC_MDVALUE(ent));
218 if (r.has_value) return r;
219 }
220
221 return r;
222 }
223
get_base64_encoded_size(size_t raw_length)224 static size_t get_base64_encoded_size(size_t raw_length) {
225 static const uint8_t tail_xtra[3] = {0, 2, 3};
226 return raw_length / 3 * 4 + tail_xtra[raw_length % 3];
227 }
228
grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,bool use_true_binary_metadata)229 size_t grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,
230 bool use_true_binary_metadata) {
231 const uint8_t* key_buf = GRPC_SLICE_START_PTR(GRPC_MDKEY(elem));
232 size_t key_len = GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
233 size_t overhead_and_key = 32 + key_len;
234 size_t value_len = GRPC_SLICE_LENGTH(GRPC_MDVALUE(elem));
235 if (grpc_key_is_binary_header(key_buf, key_len)) {
236 return overhead_and_key + (use_true_binary_metadata
237 ? value_len + 1
238 : get_base64_encoded_size(value_len));
239 } else {
240 return overhead_and_key + value_len;
241 }
242 }
243