Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/transport/chttp2/hpack_table.h"
35 :
36 : #include <assert.h>
37 : #include <string.h>
38 :
39 : #include <grpc/support/alloc.h>
40 : #include <grpc/support/log.h>
41 :
42 : #include "src/core/support/murmur_hash.h"
43 :
44 : static struct {
45 : const char *key;
46 : const char *value;
47 : } static_table[] = {
48 : /* 0: */
49 : {NULL, NULL},
50 : /* 1: */
51 : {":authority", ""},
52 : /* 2: */
53 : {":method", "GET"},
54 : /* 3: */
55 : {":method", "POST"},
56 : /* 4: */
57 : {":path", "/"},
58 : /* 5: */
59 : {":path", "/index.html"},
60 : /* 6: */
61 : {":scheme", "http"},
62 : /* 7: */
63 : {":scheme", "https"},
64 : /* 8: */
65 : {":status", "200"},
66 : /* 9: */
67 : {":status", "204"},
68 : /* 10: */
69 : {":status", "206"},
70 : /* 11: */
71 : {":status", "304"},
72 : /* 12: */
73 : {":status", "400"},
74 : /* 13: */
75 : {":status", "404"},
76 : /* 14: */
77 : {":status", "500"},
78 : /* 15: */
79 : {"accept-charset", ""},
80 : /* 16: */
81 : {"accept-encoding", "gzip, deflate"},
82 : /* 17: */
83 : {"accept-language", ""},
84 : /* 18: */
85 : {"accept-ranges", ""},
86 : /* 19: */
87 : {"accept", ""},
88 : /* 20: */
89 : {"access-control-allow-origin", ""},
90 : /* 21: */
91 : {"age", ""},
92 : /* 22: */
93 : {"allow", ""},
94 : /* 23: */
95 : {"authorization", ""},
96 : /* 24: */
97 : {"cache-control", ""},
98 : /* 25: */
99 : {"content-disposition", ""},
100 : /* 26: */
101 : {"content-encoding", ""},
102 : /* 27: */
103 : {"content-language", ""},
104 : /* 28: */
105 : {"content-length", ""},
106 : /* 29: */
107 : {"content-location", ""},
108 : /* 30: */
109 : {"content-range", ""},
110 : /* 31: */
111 : {"content-type", ""},
112 : /* 32: */
113 : {"cookie", ""},
114 : /* 33: */
115 : {"date", ""},
116 : /* 34: */
117 : {"etag", ""},
118 : /* 35: */
119 : {"expect", ""},
120 : /* 36: */
121 : {"expires", ""},
122 : /* 37: */
123 : {"from", ""},
124 : /* 38: */
125 : {"host", ""},
126 : /* 39: */
127 : {"if-match", ""},
128 : /* 40: */
129 : {"if-modified-since", ""},
130 : /* 41: */
131 : {"if-none-match", ""},
132 : /* 42: */
133 : {"if-range", ""},
134 : /* 43: */
135 : {"if-unmodified-since", ""},
136 : /* 44: */
137 : {"last-modified", ""},
138 : /* 45: */
139 : {"link", ""},
140 : /* 46: */
141 : {"location", ""},
142 : /* 47: */
143 : {"max-forwards", ""},
144 : /* 48: */
145 : {"proxy-authenticate", ""},
146 : /* 49: */
147 : {"proxy-authorization", ""},
148 : /* 50: */
149 : {"range", ""},
150 : /* 51: */
151 : {"referer", ""},
152 : /* 52: */
153 : {"refresh", ""},
154 : /* 53: */
155 : {"retry-after", ""},
156 : /* 54: */
157 : {"server", ""},
158 : /* 55: */
159 : {"set-cookie", ""},
160 : /* 56: */
161 : {"strict-transport-security", ""},
162 : /* 57: */
163 : {"transfer-encoding", ""},
164 : /* 58: */
165 : {"user-agent", ""},
166 : /* 59: */
167 : {"vary", ""},
168 : /* 60: */
169 : {"via", ""},
170 : /* 61: */
171 : {"www-authenticate", ""},
172 : };
173 :
174 6641 : static gpr_uint32 entries_for_bytes(gpr_uint32 bytes) {
175 6641 : return (bytes + GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD - 1) /
176 : GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
177 : }
178 :
179 6050 : void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl *tbl) {
180 : size_t i;
181 :
182 6050 : memset(tbl, 0, sizeof(*tbl));
183 6050 : tbl->current_table_bytes = tbl->max_bytes =
184 : GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
185 6050 : tbl->max_entries = tbl->cap_entries =
186 5968 : entries_for_bytes(tbl->current_table_bytes);
187 6050 : tbl->ents = gpr_malloc(sizeof(*tbl->ents) * tbl->cap_entries);
188 6055 : memset(tbl->ents, 0, sizeof(*tbl->ents) * tbl->cap_entries);
189 374821 : for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
190 737535 : tbl->static_ents[i - 1] =
191 368769 : grpc_mdelem_from_strings(static_table[i].key, static_table[i].value);
192 : }
193 6052 : }
194 :
195 5980 : void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl *tbl) {
196 : size_t i;
197 370377 : for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
198 364399 : GRPC_MDELEM_UNREF(tbl->static_ents[i]);
199 : }
200 55612 : for (i = 0; i < tbl->num_ents; i++) {
201 49658 : GRPC_MDELEM_UNREF(tbl->ents[(tbl->first_ent + i) % tbl->cap_entries]);
202 : }
203 5977 : gpr_free(tbl->ents);
204 5977 : }
205 :
206 32268388 : grpc_mdelem *grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl *tbl,
207 : gpr_uint32 tbl_index) {
208 : /* Static table comes first, just return an entry from it */
209 32268388 : if (tbl_index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
210 191 : return tbl->static_ents[tbl_index - 1];
211 : }
212 : /* Otherwise, find the value in the list of valid entries */
213 32268197 : tbl_index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
214 32268197 : if (tbl_index < tbl->num_ents) {
215 32268186 : gpr_uint32 offset =
216 32268186 : (tbl->num_ents - 1u - tbl_index + tbl->first_ent) % tbl->cap_entries;
217 32268186 : return tbl->ents[offset];
218 : }
219 : /* Invalid entry: return error */
220 11 : return NULL;
221 : }
222 :
223 : /* Evict one element from the table */
224 2615638 : static void evict1(grpc_chttp2_hptbl *tbl) {
225 2615638 : grpc_mdelem *first_ent = tbl->ents[tbl->first_ent];
226 5231276 : size_t elem_bytes = GPR_SLICE_LENGTH(first_ent->key->slice) +
227 2615638 : GPR_SLICE_LENGTH(first_ent->value->slice) +
228 : GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
229 2615638 : GPR_ASSERT(elem_bytes <= tbl->mem_used);
230 2615638 : tbl->mem_used -= (gpr_uint32)elem_bytes;
231 2615638 : tbl->first_ent = ((tbl->first_ent + 1) % tbl->cap_entries);
232 2615638 : tbl->num_ents--;
233 2615638 : GRPC_MDELEM_UNREF(first_ent);
234 2615638 : }
235 :
236 658 : static void rebuild_ents(grpc_chttp2_hptbl *tbl, gpr_uint32 new_cap) {
237 658 : grpc_mdelem **ents = gpr_malloc(sizeof(*ents) * new_cap);
238 : gpr_uint32 i;
239 :
240 1942 : for (i = 0; i < tbl->num_ents; i++) {
241 1284 : ents[i] = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
242 : }
243 658 : gpr_free(tbl->ents);
244 658 : tbl->ents = ents;
245 658 : tbl->cap_entries = new_cap;
246 658 : tbl->first_ent = 0;
247 658 : }
248 :
249 5376 : void grpc_chttp2_hptbl_set_max_bytes(grpc_chttp2_hptbl *tbl,
250 : gpr_uint32 max_bytes) {
251 5376 : if (tbl->max_bytes == max_bytes) {
252 10066 : return;
253 : }
254 604 : gpr_log(GPR_DEBUG, "Update hpack parser max size to %d", max_bytes);
255 2605 : while (tbl->mem_used > max_bytes) {
256 1397 : evict1(tbl);
257 : }
258 604 : tbl->max_bytes = max_bytes;
259 : }
260 :
261 676 : int grpc_chttp2_hptbl_set_current_table_size(grpc_chttp2_hptbl *tbl,
262 : gpr_uint32 bytes) {
263 676 : if (tbl->current_table_bytes == bytes) {
264 2 : return 1;
265 : }
266 674 : if (bytes > tbl->max_bytes) {
267 1 : gpr_log(GPR_ERROR,
268 : "Attempt to make hpack table %d bytes when max is %d bytes", bytes,
269 : tbl->max_bytes);
270 1 : return 0;
271 : }
272 673 : gpr_log(GPR_DEBUG, "Update hpack parser table size to %d", bytes);
273 1346 : while (tbl->mem_used > bytes) {
274 0 : evict1(tbl);
275 : }
276 673 : tbl->current_table_bytes = bytes;
277 673 : tbl->max_entries = entries_for_bytes(bytes);
278 673 : if (tbl->max_entries > tbl->cap_entries) {
279 81 : rebuild_ents(tbl, GPR_MAX(tbl->max_entries, 2 * tbl->cap_entries));
280 592 : } else if (tbl->max_entries < tbl->cap_entries / 3) {
281 592 : gpr_uint32 new_cap = GPR_MAX(tbl->max_entries, 16u);
282 592 : if (new_cap != tbl->cap_entries) {
283 577 : rebuild_ents(tbl, new_cap);
284 : }
285 : }
286 673 : return 1;
287 : }
288 :
289 4533979 : int grpc_chttp2_hptbl_add(grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
290 : /* determine how many bytes of buffer this entry represents */
291 9067958 : size_t elem_bytes = GPR_SLICE_LENGTH(md->key->slice) +
292 4533979 : GPR_SLICE_LENGTH(md->value->slice) +
293 : GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
294 :
295 4533979 : if (tbl->current_table_bytes > tbl->max_bytes) {
296 0 : gpr_log(GPR_ERROR,
297 : "HPACK max table size reduced to %d but not reflected by hpack "
298 : "stream (still at %d)",
299 : tbl->max_bytes, tbl->current_table_bytes);
300 0 : return 0;
301 : }
302 :
303 : /* we can't add elements bigger than the max table size */
304 4533979 : if (elem_bytes > tbl->current_table_bytes) {
305 : /* HPACK draft 10 section 4.4 states:
306 : * If the size of the new entry is less than or equal to the maximum
307 : * size, that entry is added to the table. It is not an error to
308 : * attempt to add an entry that is larger than the maximum size; an
309 : * attempt to add an entry larger than the entire table causes
310 : * the table
311 : * to be emptied of all existing entries, and results in an
312 : * empty table.
313 : */
314 3736304 : while (tbl->num_ents) {
315 0 : evict1(tbl);
316 : }
317 1868152 : return 1;
318 : }
319 :
320 : /* evict entries to ensure no overflow */
321 7945343 : while (elem_bytes > (size_t)tbl->current_table_bytes - tbl->mem_used) {
322 2614241 : evict1(tbl);
323 : }
324 :
325 : /* copy the finalized entry in */
326 5331654 : tbl->ents[(tbl->first_ent + tbl->num_ents) % tbl->cap_entries] =
327 2665827 : GRPC_MDELEM_REF(md);
328 :
329 : /* update accounting values */
330 2665827 : tbl->num_ents++;
331 2665827 : tbl->mem_used += (gpr_uint32)elem_bytes;
332 2665827 : return 1;
333 : }
334 :
335 117 : grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
336 : const grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
337 117 : grpc_chttp2_hptbl_find_result r = {0, 0};
338 : gpr_uint32 i;
339 :
340 : /* See if the string is in the static table */
341 7089 : for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
342 6975 : grpc_mdelem *ent = tbl->static_ents[i];
343 6975 : if (md->key != ent->key) continue;
344 8 : r.index = i + 1u;
345 8 : r.has_value = md->value == ent->value;
346 8 : if (r.has_value) return r;
347 : }
348 :
349 : /* Scan the dynamic table */
350 5688 : for (i = 0; i < tbl->num_ents; i++) {
351 5681 : gpr_uint32 idx =
352 5681 : (gpr_uint32)(tbl->num_ents - i + GRPC_CHTTP2_LAST_STATIC_ENTRY);
353 5681 : grpc_mdelem *ent = tbl->ents[(tbl->first_ent + i) % tbl->cap_entries];
354 5681 : if (md->key != ent->key) continue;
355 5563 : r.index = idx;
356 5563 : r.has_value = md->value == ent->value;
357 5563 : if (r.has_value) return r;
358 : }
359 :
360 7 : return r;
361 : }
|
