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/ext/transport/chttp2/transport/hpack_mapping.h"
31 #include "src/core/lib/debug/trace.h"
32 #include "src/core/lib/gpr/murmur_hash.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
entries_for_bytes(uint32_t bytes)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
grpc_chttp2_hptbl_init(grpc_chttp2_hptbl * tbl)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
grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl * tbl)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
grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl * tbl,uint32_t tbl_index)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 */
evict1(grpc_chttp2_hptbl * tbl)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
rebuild_ents(grpc_chttp2_hptbl * tbl,uint32_t new_cap)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
grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl * tbl,uint32_t max_bytes)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_http_trace.enabled()) {
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
grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl * tbl,uint32_t bytes)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_http_trace.enabled()) {
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
grpc_chttp2_hptbl_add(grpc_chttp2_hptbl * tbl,grpc_mdelem md)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
grpc_chttp2_hptbl_find(const grpc_chttp2_hptbl * tbl,grpc_mdelem md)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
get_base64_encoded_size(size_t raw_length)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
grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,bool use_true_binary_metadata)377 size_t grpc_chttp2_get_size_in_hpack_table(grpc_mdelem elem,
378 bool use_true_binary_metadata) {
379 size_t overhead_and_key = 32 + GRPC_SLICE_LENGTH(GRPC_MDKEY(elem));
380 size_t value_len = GRPC_SLICE_LENGTH(GRPC_MDVALUE(elem));
381 if (grpc_is_binary_header(GRPC_MDKEY(elem))) {
382 return overhead_and_key + (use_true_binary_metadata
383 ? value_len + 1
384 : get_base64_encoded_size(value_len));
385 } else {
386 return overhead_and_key + value_len;
387 }
388 }
389
grpc_chttp2_get_static_hpack_table_index(grpc_mdelem md)390 uint8_t grpc_chttp2_get_static_hpack_table_index(grpc_mdelem md) {
391 if (GRPC_MDELEM_STORAGE(md) == GRPC_MDELEM_STORAGE_STATIC) {
392 return grpc_hpack_static_mdelem_indices[GRPC_MDELEM_DATA(md) -
393 grpc_static_mdelem_table];
394 } else {
395 return 0;
396 }
397 }
398