• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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