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/log.h>
40 : #include "src/core/support/murmur_hash.h"
41 :
42 : static struct {
43 : const char *key;
44 : const char *value;
45 : } static_table[] = {
46 : /* 0: */
47 : {NULL, NULL},
48 : /* 1: */
49 : {":authority", ""},
50 : /* 2: */
51 : {":method", "GET"},
52 : /* 3: */
53 : {":method", "POST"},
54 : /* 4: */
55 : {":path", "/"},
56 : /* 5: */
57 : {":path", "/index.html"},
58 : /* 6: */
59 : {":scheme", "http"},
60 : /* 7: */
61 : {":scheme", "https"},
62 : /* 8: */
63 : {":status", "200"},
64 : /* 9: */
65 : {":status", "204"},
66 : /* 10: */
67 : {":status", "206"},
68 : /* 11: */
69 : {":status", "304"},
70 : /* 12: */
71 : {":status", "400"},
72 : /* 13: */
73 : {":status", "404"},
74 : /* 14: */
75 : {":status", "500"},
76 : /* 15: */
77 : {"accept-charset", ""},
78 : /* 16: */
79 : {"accept-encoding", "gzip, deflate"},
80 : /* 17: */
81 : {"accept-language", ""},
82 : /* 18: */
83 : {"accept-ranges", ""},
84 : /* 19: */
85 : {"accept", ""},
86 : /* 20: */
87 : {"access-control-allow-origin", ""},
88 : /* 21: */
89 : {"age", ""},
90 : /* 22: */
91 : {"allow", ""},
92 : /* 23: */
93 : {"authorization", ""},
94 : /* 24: */
95 : {"cache-control", ""},
96 : /* 25: */
97 : {"content-disposition", ""},
98 : /* 26: */
99 : {"content-encoding", ""},
100 : /* 27: */
101 : {"content-language", ""},
102 : /* 28: */
103 : {"content-length", ""},
104 : /* 29: */
105 : {"content-location", ""},
106 : /* 30: */
107 : {"content-range", ""},
108 : /* 31: */
109 : {"content-type", ""},
110 : /* 32: */
111 : {"cookie", ""},
112 : /* 33: */
113 : {"date", ""},
114 : /* 34: */
115 : {"etag", ""},
116 : /* 35: */
117 : {"expect", ""},
118 : /* 36: */
119 : {"expires", ""},
120 : /* 37: */
121 : {"from", ""},
122 : /* 38: */
123 : {"host", ""},
124 : /* 39: */
125 : {"if-match", ""},
126 : /* 40: */
127 : {"if-modified-since", ""},
128 : /* 41: */
129 : {"if-none-match", ""},
130 : /* 42: */
131 : {"if-range", ""},
132 : /* 43: */
133 : {"if-unmodified-since", ""},
134 : /* 44: */
135 : {"last-modified", ""},
136 : /* 45: */
137 : {"link", ""},
138 : /* 46: */
139 : {"location", ""},
140 : /* 47: */
141 : {"max-forwards", ""},
142 : /* 48: */
143 : {"proxy-authenticate", ""},
144 : /* 49: */
145 : {"proxy-authorization", ""},
146 : /* 50: */
147 : {"range", ""},
148 : /* 51: */
149 : {"referer", ""},
150 : /* 52: */
151 : {"refresh", ""},
152 : /* 53: */
153 : {"retry-after", ""},
154 : /* 54: */
155 : {"server", ""},
156 : /* 55: */
157 : {"set-cookie", ""},
158 : /* 56: */
159 : {"strict-transport-security", ""},
160 : /* 57: */
161 : {"transfer-encoding", ""},
162 : /* 58: */
163 : {"user-agent", ""},
164 : /* 59: */
165 : {"vary", ""},
166 : /* 60: */
167 : {"via", ""},
168 : /* 61: */
169 : {"www-authenticate", ""},
170 : };
171 :
172 4031 : void grpc_chttp2_hptbl_init(grpc_chttp2_hptbl *tbl, grpc_mdctx *mdctx) {
173 : size_t i;
174 :
175 4031 : memset(tbl, 0, sizeof(*tbl));
176 4031 : tbl->mdctx = mdctx;
177 4031 : tbl->max_bytes = GRPC_CHTTP2_INITIAL_HPACK_TABLE_SIZE;
178 250299 : for (i = 1; i <= GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
179 246261 : tbl->static_ents[i - 1] = grpc_mdelem_from_strings(
180 : mdctx, static_table[i].key, static_table[i].value);
181 : }
182 4038 : }
183 :
184 4036 : void grpc_chttp2_hptbl_destroy(grpc_chttp2_hptbl *tbl) {
185 : size_t i;
186 250351 : for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
187 246313 : GRPC_MDELEM_UNREF(tbl->static_ents[i]);
188 : }
189 34187 : for (i = 0; i < tbl->num_ents; i++) {
190 30149 : GRPC_MDELEM_UNREF(
191 : tbl->ents[(tbl->first_ent + i) % GRPC_CHTTP2_MAX_TABLE_COUNT]);
192 : }
193 4038 : }
194 :
195 20800157 : grpc_mdelem *grpc_chttp2_hptbl_lookup(const grpc_chttp2_hptbl *tbl,
196 : gpr_uint32 tbl_index) {
197 : /* Static table comes first, just return an entry from it */
198 20800157 : if (tbl_index <= GRPC_CHTTP2_LAST_STATIC_ENTRY) {
199 187 : return tbl->static_ents[tbl_index - 1];
200 : }
201 : /* Otherwise, find the value in the list of valid entries */
202 20799970 : tbl_index -= (GRPC_CHTTP2_LAST_STATIC_ENTRY + 1);
203 20799970 : if (tbl_index < tbl->num_ents) {
204 20799970 : gpr_uint32 offset = (tbl->num_ents - 1u - tbl_index + tbl->first_ent) %
205 : GRPC_CHTTP2_MAX_TABLE_COUNT;
206 20799970 : return tbl->ents[offset];
207 : }
208 : /* Invalid entry: return error */
209 0 : return NULL;
210 : }
211 :
212 : /* Evict one element from the table */
213 1017009 : static void evict1(grpc_chttp2_hptbl *tbl) {
214 1017009 : grpc_mdelem *first_ent = tbl->ents[tbl->first_ent];
215 2034018 : size_t elem_bytes = GPR_SLICE_LENGTH(first_ent->key->slice) +
216 1017009 : GPR_SLICE_LENGTH(first_ent->value->slice) +
217 : GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
218 1017009 : GPR_ASSERT(elem_bytes <= tbl->mem_used);
219 1017009 : tbl->mem_used = (gpr_uint16)(tbl->mem_used - elem_bytes);
220 1017009 : tbl->first_ent =
221 1017009 : (gpr_uint16)((tbl->first_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT);
222 1017009 : tbl->num_ents--;
223 1017009 : GRPC_MDELEM_UNREF(first_ent);
224 1017009 : }
225 :
226 1047158 : void grpc_chttp2_hptbl_add(grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
227 : /* determine how many bytes of buffer this entry represents */
228 2094316 : size_t elem_bytes = GPR_SLICE_LENGTH(md->key->slice) +
229 1047158 : GPR_SLICE_LENGTH(md->value->slice) +
230 : GRPC_CHTTP2_HPACK_ENTRY_OVERHEAD;
231 :
232 : /* we can't add elements bigger than the max table size */
233 1047158 : if (elem_bytes > tbl->max_bytes) {
234 : /* HPACK draft 10 section 4.4 states:
235 : * If the size of the new entry is less than or equal to the maximum
236 : * size, that entry is added to the table. It is not an error to
237 : * attempt to add an entry that is larger than the maximum size; an
238 : * attempt to add an entry larger than the entire table causes
239 : * the table
240 : * to be emptied of all existing entries, and results in an
241 : * empty table.
242 : */
243 0 : while (tbl->num_ents) {
244 0 : evict1(tbl);
245 : }
246 1047158 : return;
247 : }
248 :
249 : /* evict entries to ensure no overflow */
250 3111325 : while (elem_bytes > (size_t)tbl->max_bytes - tbl->mem_used) {
251 1017009 : evict1(tbl);
252 : }
253 :
254 : /* copy the finalized entry in */
255 1047158 : tbl->ents[tbl->last_ent] = md;
256 :
257 : /* update accounting values */
258 1047158 : tbl->last_ent =
259 1047158 : (gpr_uint16)((tbl->last_ent + 1) % GRPC_CHTTP2_MAX_TABLE_COUNT);
260 1047158 : tbl->num_ents++;
261 1047158 : tbl->mem_used = (gpr_uint16)(tbl->mem_used + elem_bytes);
262 : }
263 :
264 117 : grpc_chttp2_hptbl_find_result grpc_chttp2_hptbl_find(
265 : const grpc_chttp2_hptbl *tbl, grpc_mdelem *md) {
266 117 : grpc_chttp2_hptbl_find_result r = {0, 0};
267 : gpr_uint16 i;
268 :
269 : /* See if the string is in the static table */
270 7089 : for (i = 0; i < GRPC_CHTTP2_LAST_STATIC_ENTRY; i++) {
271 6975 : grpc_mdelem *ent = tbl->static_ents[i];
272 6975 : if (md->key != ent->key) continue;
273 8 : r.index = (gpr_uint16)(i + 1);
274 8 : r.has_value = md->value == ent->value;
275 8 : if (r.has_value) return r;
276 : }
277 :
278 : /* Scan the dynamic table */
279 5688 : for (i = 0; i < tbl->num_ents; i++) {
280 5681 : gpr_uint16 idx =
281 5681 : (gpr_uint16)(tbl->num_ents - i + GRPC_CHTTP2_LAST_STATIC_ENTRY);
282 5681 : grpc_mdelem *ent =
283 5681 : tbl->ents[(tbl->first_ent + i) % GRPC_CHTTP2_MAX_TABLE_COUNT];
284 5681 : if (md->key != ent->key) continue;
285 5563 : r.index = idx;
286 5563 : r.has_value = md->value == ent->value;
287 5563 : if (r.has_value) return r;
288 : }
289 :
290 7 : return r;
291 : }
|
